Diffie Hellman’s meet in the middle attack trades off space for time to find out the two secret keys.
For the pattern p it tries all the possible keys to obtain a set of numbers corresponding $Ek(p)$. Also for the pattern s it uses all the possible keys to decrypt s, $Dk(s)$.
If we find any match in the two sets it means that $Ek1(p) = Dk2(s)$ so the secret keys are k1 and k2.

The naive brute force algorithm would go through $2^56^ * 2^56^$ iterations by brute forcing through all possible values of k1 and k2 while this algorithm uses $2^56^ * 56$ memory to store $Ek(p)$ and does $O(2^56^)$ work to find a match.

The naive brute force algorithm would go through $2^56^ * 2^56^$ iterations by brute forcing through all possible values of k1 and k2 while this algorithm uses $2^56^ * 56$ memory to store $Ek(p)$ and does $2^56^$ work to find a match.

h2. Discrete logarithm

bq. Given n a prime number and p, q two integers between 0 and n-1, find k such that  p^k^ = q modulo n.

bq. Given n a prime number and p, q two integers between 0 and n-1, find k such that  p^k^ = q (mod n).

This problem can be solved using the baby step, giant step algorithm which uses the meet in the middle trick.
We can write k = $i([sqrt(n)] + 1) + j$
Notice that $i <= sqrt(n)$ and $j <= sqrt(n)$.

Now our equality looks like this $p^(i ([sqrt(n)] + 1) + j)^ = q modulo n$.
We can divide by $p^j^$ and get $p^(i[sqrt(n)] + 1)^ = qp^-j^ modulo n$.

Replacing k in the equality we get $p^(i ([sqrt(n)] + 1) + j)^ = q (mod n)$.
Dividing by $p^j^$ we get $p^(i[sqrt(n)] + 1)^ = qp^-j^ (mod n)$.

Using meet in the middle becomes obvious. We can brute force through the numbers on each side of the equality and find a colision.

The algorithm takes O(sqrt(n)) space and O(sqrt(n)) time.

The algorithm takes $O(sqrt(n))$ space and $O(sqrt(n))$ time.

h2. Bidirectional search