hal at finney.org
Wed Aug 27 15:36:45 EDT 2008
I like Greg Rose's solution best:
> There is a fairly standard technique for handling things like this.
> 1. encode your number N into a 133-bit string S
> 2. encrypt S with your favourite 133-bit block cipher (see below)
> 3. decode S to a number N'
> 4. if N' >= 10^40, goto 2 (that is, re-encrypt until it is in range)
> 5. N' is your answer.
This is Rich Schroeppel's trick from his Hasty Pudding cipher, a somewhat
under-rated AES submission IMO. HPC originated not only this trick,
but also the idea of tweakable encryption, which has turned out to be
important for disk encryption. The Black-Rogaway paper referenced earlier
has a proof of security of this construction.
> So, you don't have a 133-bit block cipher lying around? No worries, I'll
> sell you one ;-). Actually that is easy too. Take a trustworthy 128-bit
> block cipher like AES. To encrypt, do:
> 1. Encrypt the first 128 bits (ECB mode)
> 2. Encrypt the last 128 bits (also ECB mode).
I didn't understand this at first, but I finally saw that the point is to
do the encryptions in-place; step 1 replaces the first 128 bits of the
data with the encryption, and similarly for step 2. This is equivalent
to doing CBC mode with a fixed IV of 0, and ciphertext stealing for the
final partial block of 5 bits.
> To decrypt, do decryptions in the reverse order, obviously. It's easy to
> see that this is a secure permutation if AES itself is, depending on
> your definition of secure; if you add a third step, to re-encrypt the
> first 128 bits, it is truly secure. (Without the third step, tweaking a
> bit in the first 5 bits will often leave the last 5 unchanged on
> decryption, which is clearly a distinguishing attack; the third
> encryption makes it an all-or-nothing transform.)
I am not familiar with the security proof here, do you have a reference?
Or is it an exercise for the student?
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com
More information about the cryptography