I have a question regarding time complexity of meet in the middle attack on textbook RSA encryption. Let's suppose that I try to encrypt symmetric keys of different length with no padding using RSA algorithm. Example keys:

  • 56 bit DES key (with parity bits): DA13511CAB329E32 (without parity bits can be factored: BC6AF11×12864009)
  • 80 bit Skipjack key: 54C22E82E4E2F5FD9A5D (can be factored: 3537×197BF2D963817B70B)
  • 128 bit AES key: CF15C540E2E43F764B1F995E30BBE883 (can be factored: BBC80693039D7291×11A51051306064BD3)

Now, each symmetric key will be encrypted with RSA public key:
exponent: 65537, modulus: random and different for each encryption

I know: c (RSA ciphertext), e (exponent), n (modulus) from the following equation:
$c=k^e\bmod n$
and I try to find k (symmetric key)

To perform meet in the middle I have to do the following: For symmetric key with keyspace equal to n (for DES $n=2^{56}$, for Skipjack $n=2^{80}$, for AES $n=2^{128}$) I have to generate associative array A (pseudocode):

for i := 1 to √n do
  append (c × (i−e mod n) mod n ⇨ i) to A
Now I try to find two factors of k, one is already somewhere in A array, the other will be searched in a loop (pseudocode):
i := 0
  i := i + 1
while (array key (ie mod n) doesn't exist in A)
return k := A[ie mod n] × i

In the best case, the key will be less than $\sqrt n$ and will be found in the first iteration. The whole process will have complexity of $\sqrt n$ (needed for generation of A array). Example keys of this kind:
DES: 010101011585C746
Skipjack: 000000000001290F5F8E
AES: 000000000000000008DE5D490B6ED5B9

In the worst case the key will be a prime number slightly less than maximum allowed key so the time complexity will be n. Example keys of this kind:

Now I am most interested in average case. I did some symbolic calculations in wolfram mathematica and came to a conclusion that for a random key the second loop will end on average after $\frac{\sqrt n\times \log(n)}4$ iterations (n is keyspace size) and this is also the time complexity of the whole meet in the middle attack. Is this result correct?

  • 1
    $\begingroup$ Average? 1/2 half of the keys have 1 on their MSB. $\endgroup$
    – kelalaka
    Oct 22 at 21:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.