[Cryptography] quantum computers & crypto

Viktor Dukhovni cryptography at dukhovni.org
Sun Nov 7 00:39:55 EDT 2021

On Sat, Nov 06, 2021 at 07:17:45PM -0400, Jerry Leichter wrote:

> You need to determine K.  Well, *any* K.  Since K, P, and C are all
> the same length, and AES "looks random," collisions are inevitable and
> multiple K's will produce a givn (P,C) pair.

* In AES 256, the plaintext and ciphertext are 128 bits and the key
  is 256 bits.  There are indeed many keys that produce the same
  (P,C) pair.

* In AES 128, there are all 128 bits long as you suggest.  In which the
  probability of a random permutation of 2^{128} bit strings mapping a
  given bit string P to bit string C are 2^{-128}.  Since there are
  also 2^{128} keys (random permutations), the expected number of
  permutations mapping P to C is 1.  With low odds and many trials,
  the distribution should be close to Poisson.  Given that one key
  is believed to produce (P, C) on average there should be just
  one more.

  P(unique key)     = 1/e   = ~37%.
  P(two keys)       = 1/e   = ~37%
  P(three keys)     = 1/2!e = ~18%
  P(four keys)      = 1/3!e = ~6%
  P(five keys)      = 1/4!e = ~1.5%

So, with AES128, collisions for a single (P,C) pair aren't quite
inevitable, but they are not infrequent.  With just two (plaintext,
ciphertext) pairs AES128 key collisions are extremely improbable.

With AES256, we'd want at least two (P,C) pairs to have a reasonable
chance of unique keys, and three pairs are sufficient to make collisions
exceedingly unlikely.


More information about the cryptography mailing list