# Textbook RSA meet in the middle time complexity

Hello,
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
do
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:
DES: FEFEFEFEFEFEFEF7
Skipjack: FFFFFFFFFFFFFFFFFFBF
AES: FFFFFFFFFFFFFFFFFFFFFFFFFFFFFF61

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?

• Average? 1/2 half of the keys have 1 on their MSB. Oct 22 at 21:56