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

Mary Conner trif at serv.net
Thu Jan 22 19:40:22 EST 1998


An alternative explanation:

DES has the property that if you encrypt plaintext P with key K and
get ciphertext C, then encrypting ~P (the complement of P) with key
~K (the complement of K), you will get ~C (the complement of C).  In
DES, one takes a key, and calculates a series of key schedules from
it.  You then decrypt C and see if what you get is P.  You can then
take the same key schedules (no need to recalculate, saves a *lot*
of time and/or memory accesses), decrypt ~C and see if you get ~P.
If you do, then that means that the key that decrypts C into P must
be ~K.

On Thu, 22 Jan 1998 gindrup at okway.okstate.edu wrote:

> 
>      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
> 
> 

--
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