Re: Encryption key longer than text to encrypt

rossum wrote:
On 5 Jan 2007 13:31:41 -0800, "Jean-François Michaud"
<cometaj@xxxxxxxxxxx> wrote:

Hmmm, I can't help but notice the similarity between a synchronous
stream cipher where the keystream generation is independant from the
acutal XORing process.

In such a context, the OTP key and the keystream share the same idea,
notably that a large key/keystream will be XORed against plaintext.
This is why I'm coming back to OTP, because, the OTP being a perfect
case and being contextually clear and well understood, I feel it makes
thinking easier than to lay down the context of a synchronous stream
cipher in which the keystream generation is independant from the XORing
There is a fundamental difference between an OTP and a keystream
generated from a key. Say you have a 128 bit key, then there are
2**128 possible keys, each of which generates a different keystream.
Hence there are 2**128 different keystreams possible in this cypher.
Say we have a 2KB message to encrypt. We use the first 2KB of one of
our 2**128 keystreams.

Now think about an OTP encrypting a 2KB message. There is no
generated keystream, just a random key as long as the message (or
message + padding). That means that in the OTP there are 2**2048
possible different 'keys', which equates to 2**2048 possible different
keystreams. As soon as you move from an OTP to a generated keystream
you have a drop in the possible number of different keys allowed. In
the OPT case the attacker has 2**2048 different keystreams to try,
with a keyed cypher she only has 2**128 different keystreams to try.

With the keyed cypher, all the entropy is in the key - once you know
(or guess) the key, there is no additional entropy in the generated
keystream. Working out the keystream from the key is a matter of pure
computatation, as it has to be if decryption is to work correctly.
With the OTP the key is identical to the keystream so all of the
keystream is entropy. That is why for an OTP you need to send the
keystream in its entirety as it cannot be generated by any algorithm.

A stream cypher is certainly more practical than an OTP, but it is not
merely a version of an OTP - it is an entirely different animal.

Right, I clearly understand the difference between both, and I also
clearly understand that the bottleneck for a stream cipher is the key
and not the generated keystream and that the strenght of the key varies
with the lenght of the message for the OTP (so does the strenght of the
key in this case); those differences set asside, the OTP key and the
keystream are used for the same purpose (being XORed against
plaintext). So, an otherwise interresting idea for OTP, could also most
probably be directly applied to stream ciphers, hence the idea of
concealing the lenght of the message by having a message that is
smaller than the OTP key or stream cipher keystream.

Jean-Francois Michaud