[RC5] DES-II question

Joe Zbiciak j-zbiciak1 at ti.com
Sat Mar 28 02:17:01 EST 1998


'Ted Rathkopf' said previously:

| So, statistically, there should not have been ANY false positives.

That's not entirely true -- there is a standard deviation to consider.

Your conjecture corresponds to the "expected value", but that's a bit
like saying "If the odds are 1 in 2 that something will happen, doing
it 2 times ensures it will happen exactly once."  A good analogy here
would be tossing a coin:  If the quoted statement were true, then coins
would always alternate between heads and tails whenever they were
tossed, since there is a 1 in 2 chance that a flipped coin will come up
heads.

In reality, this corresponds to a "binomial probability distribution."
For each "trial", we have a probability "p" that an event occurs, and a
complementary probability "1-p" that the event will not occur.

According to Knuth (Volume 2, pp136-137): 

    If some event occurs with probability 'p', and we carry out 't' 
    independent trials, the total number 'N' of occurences equals 'n'
    with probability  

           / t \   n           t - n
          (     ) p  ( 1 - p )
           \ n /

(For those of you who are having as tough a time as I am at reading
that ASCII mangling of that formula, here is an English pronounciation,
approximately: " 't' choose 'n' times 'p' to the 'n' times the quantity
'1' minus 'p', quantity raised to the 't' minus 'n'".  The operation
't' choose 'n' refers to the combinatorial operator, which gives the
number of unique combinations of 'n' items there are when choosing from
a set of 't' items)

So, based on this, we can calculate exactly what the probability would
be that we had a given number of false positives in our search of the
keyspace.  An easy one would be 'n' == 1, since it is highly unlikely
that we would have more than one false positive in a block.

For 2^56 keys, t = 2^56, and p = 2^-64.  That gives us:

              56        1              56
           / 2   \   -64         -64  2  - 1
          (       ) 2     ( 1 - 2   )
           \  1  /

Eeek.  :-)  Fortunately, 2^56 choose 1 is easy.. that's 2^56.
2^56 * 2^-64 == 2^-8.  That leaves us with

                                     56
                     -8        -64  2  - 1
                    2   ( 1 - 2   )
                  
Nasty, isn't it?  Using bc, I calculated this out to be about a 1
in 257 chance that we had one false positive.  (It's not exactly
1 in 256 because of that nasty term on the right which isn't quite 1.0.
This corresponds to the miniscule chance that we might have more than
one false positive, which wasn't taken into account by this formula.)


An interesting twist comes about when we set 'n' equal to 0, which
asks the question, "What is the probability that we had 0 false 
positives?"  The equation decays to this one term:

                             56
                       -64  2 
                ( 1 - 2   )

Once again, I turn to 'bc' for the answer.  It says there's a 99.61%
chance we had NO false positives.  Whew.  It's large, but it's not
100%.

:-)

So, can anyone with a Statistics background (or suitable textbook 
reference) point out where I screwed up?  ;^)

Regards,

--Joe

-- 
 +----------- Joseph Zbiciak ----------+
 | - - - -  j-zbiciak1 at ti.com  - - - - |      Don't answer, don't ask,
 |- http://www.primenet.com/~im14u2c/ -|      Don't try to make sense.
 | - - -Texas Instruments, Dallas- - - |          -- "Numb", U2
 +-----#include "std_disclaimer.h"-----+
--
To unsubscribe, send 'unsubscribe rc5' to majordomo at lists.distributed.net
rc5-digest subscribers replace rc5 with rc5-digest



More information about the rc5 mailing list