[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