bq. Given an array of integers, find out if there are any four numbers such that the sum of the first three equal to the fourth (you can use the same number more than once).
The naive algorithm is $O(N^4^)$ try all the possible combinations of four numbers. A less naive algorithm brute forces through all $n^3^$ combinations of three numbers and then efficiently checks if their sum is in the original array by using a hash table.

By now, you’ve probably started thinking how meet in the middle can be applied to this problem. The trick is to rewrite the equation as $a + b = d - c$. Store all the $n^2^$ sums $a + b$ in a hash set $S$. Then iterate through all $n^2^$ combinations for c and d and check if $S$ contains $d - c$. This algorithm has $O(n^2^)$ time and space complexity.

But by now you’ve probably started thinking how meet in the middle can be applied for this problem. The trick is to rewrite the equation as $a + b = d - c$. Store all the $n^2^$ sums $a + b$ in a hash set $S$. Then iterate through all $n^2^$ combinations for c and d and check if $S$ contains $d - c$. This algorithm has $O(n^2^)$ time and space complexity.

h2. Breaking 2DES

DES is an encryption standard which uses 56 bit keys. Today computers can use a brute force approach to break the encryption. One simple approach to make the encryption more secure is to apply it twice, using two different keys. Even this approach is susceptible to the meet in the middle attack developed by Diffie Hellman. 3DES is currently used, and it encrypts the message three times using 3 keys.

DES is a encryption standard which uses 56 bit keys. This was enough when the algorithm got invented but currently computers can use a brute force approach to break the encryption.  One simple idea to make the encryption more secure is to apply the encryption twice using two different keys. This approach is susceptible to the meet in the middle attack developed by Diffie Hellman. So currently 3DES is used which uses three keys and encrypts the message three times.

Let’s see why 2DES is vulnerable. Let Ek be the encryption function using the secret key k and Dk the decryption function using the secret key k. 2DES uses Ek1(Ek2(p)) = s to encrypt and Dk2(Dk1(s)) = p to decrypt.

Let’s see why 2DES is bad. We call Ek the encryption function using the secret key k and Dk the decryption function using the secret key k. 2DES uses Ek1(Ek2(p)) = s to encrypt and Dk2(Dk1(s)) = p to decrypt.

Diffie Hellman’s meet in the middle attack trades off space for time to find out the two secret keys.

Diffie Hellman’s meet in the middle attack trades of 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.