[RC5] FAQ rough draft (was: Client Documentation)

gindrup at okway.okstate.edu gindrup at okway.okstate.edu
Thu Jan 22 11:11:02 EST 1998


     Clarification of the complementary key issue.
     
        It turns out that DES has an interesting property that makes it 
     half as hard to search the keyspace for a decryption key.  And that 
     property is that the complement of a key decrypts a given ciphertext 
     block into the complement of the plaintext block that the normal key 
     generated.
        What does that mean?
        That means that if I decrypt a ciphertext block with a given key, 
a 
     process that is somewhat laborious, I can decrypt with the 
complement 
     of the key almost instantaneously.  Since, the complement of the key 
     decrypts to the complement of the plaintext, once the plaintext has 
     been generated for the key, the plaintext for the complement key can 
     be generated *without* doing all the normal bit-fiddling.
        An example:
        Suppose the key I was attempting was (in 56 bits)
     0001110 0110101 1100011 0100110 1011101 0100110 1010101 1010011
        As a simplification for explanation, assume this key decrypted 
the 
     first 8 bits of the ciphertext into 11001011.  This is a 
     simplification because DES works in 64-bit pieces of cipher- and 
     plain-text, not 8-bit pieces.
        Now, the interesting property of DES is that if we were to 
decrypt 
     the exact same ciphertext using the complement key:
     1110001 1001010 0011100 1011001 0100010 1011001 0101010 0101100
     the resulting first 8 bits would be the complement of what we got 
     before: 00110100 (ASCII code for "T").  So instead of doing the 
     decryption twice, we can do it once, cracking one key, and then take 
     the complement of what we just got, cracking the complementary key.
     
        The process of taking the complement is pretty trivial for a 
     computer -- for each bit in the string of bits, if the bit is a "1", 
     replace it with a "0", otherwise (since the bit is a "0") replace it 
     with a "1".  This replaces each bit with its opposite, its 
complement.
     
        Thus, after spending many minutes cracking with a block of keys, 
     only a few seconds are used cracking the complementary set of keys.  
     So, twice the number of keys can be cracked at very little time 
cost.  
     This is why there is the occasional x2 difference between block 
sizes 
     and number of keys cracked in a block.
            -- Eric Gindrup ! gindrup at Okway.okstate.edu
     
     52 = 00110100


______________________________ Reply Separator 
_________________________________
Subject: [RC5] FAQ rough draft (was: Client Documentation) 
Author:  <rc5 at llamas.net > at SMTP
Date:    1/21/98 1:47 AM


     [snip]
Q: I thought cracking DES keys was supposed to be much faster than 
cracking RC5 keys.  So why does it take as long or longer to crack a 
block of DES keys?
A: For each key in a DES block, the client cracks the key AND its 
compliment (a logical XOR of the primary key).  This means that the DES 
core is cracking twice as many keys as an RC5 block of the same size. 
The reason is that it's apparently more efficient to check a key and its 
complement in the same calculation rather than checking the two keys 
separately.
     
Q: What's all this business with the block size (2^28, 2^29, 2^30,2^31) 
of DES keys?
A: Just what the terminology suggests.  The block size is the size of a 
block of keys in terms of the number of keys in that block.  Therefore, 
a 2^28 block represents 2^28 keys (268435456).  Keep in mind, however, 
that the DES client would actually have to crack 2^29 keys in order to 
complete this block (see previous question).  All RC5 blocks are 2^28 
keys in length.  DES blocks are of variable size, presumably, so faster 
clients don't have to buffer as many blocks as they might otherwise have 
to do given the increased speed efficiency of cracking DES keys (versus 
cracking RC5 keys).
     
Q: The number of keys in a block is wrong in the log file.  A block size 
of 2^28 is 268435456 keys, not 536870912 as reported in the log file.
A: This is not a bug.  See the previous two questions.
     [snip]


--
To unsubcribe, send 'unsubscribe rc5' to majordomo at lists.distributed.net
rc5-digest subscribers replace rc5 with rc5-digest



More information about the rc5 mailing list