# [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
>
>
> _________________________________
> 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

```