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?
