h2. Breaking 2DES

!<scratch-meet-in-the-middle?2des.png 70%!

!<blog/meet-in-the-middle?2des.png 70%!

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. This approach is susceptible to the meet in the middle attack developed by Diffie Hellman. 3DES is less susceptible as it encrypts the message three times using 3 keys.
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.

bq. Find the shortest path between two nodes nodes in a large graph which you can’t keep in memory, for example the Facebook friendship graph.

!scratch-meet-in-the-middle?12fig26.gif! The usual approach is to use a bread first search algorithm. If the distance between two nodes is $k$ and the average degree in the network is $p$ then we explore $O(p^k^)$ nodes.

!<blog/meet-in-the-middle?12fig26.gif! The usual approach is to use a bread first search algorithm. If the distance between two nodes is $k$ and the average degree in the network is $p$ then we explore $O(p^k^)$ nodes.

One neat idea is instead of starting the search from one node, start from both and see when the two search spaces meet.  This way we only go through $O(p^k/2^)$ nodes.

# Equal partition: Given a set A of 40 real numbers, find out if there is any way to split A in two sets such that the sums of their elements are equal. (Hint: complexity $O(2^n/2^)$)
# Minimal vertex cover: Given a graph of n nodes (n <= 30), find out a set with the smallest number of vertices such that each edge in the  graph has at least one node inside the set. (Hint: complexity $O(3^n/2^)$)
# Square: You're given an array L which represents the sizes of n planks. You have to answer if there's any way to form a square using the planks without breaking them of overlapping them. (Hint: complexity $O(4^n/2^)$)

# 8 puzzle: The 8 puzzle is a sliding tile puzzle of 3x3 slots with 8 tiles and one empty slot. At each step you can move one of the orthogonaly neighbouring tiles to the empty slot. The game starts from a random initial configuration and the purpose is to get to the * in the fewest number of moves. Figure out an efficient algorithm that solves the 8 puzzle. (Hint: Each position is solvable in at most 31 moves) In the picture we see a sequence of moves that solves the puzzle.
!scratch-meet-in-the-middle?8puzzle.png!

# 8 puzzle: The 8 puzzle is a sliding tile puzzle of 3x3 slots with 8 tiles and one empty slot. At each step you can move one of the orthogonally neighbouring tiles to the empty slot. The game starts from a random initial configuration and the purpose is to get to the * in the fewest number of moves. Figure out an efficient algorithm that solves the 8 puzzle. (Hint: Each position is solvable in at most 31 moves) In the picture we see a sequence of moves that solves the puzzle.
!blog/meet-in-the-middle?8puzzle.png!

Try the to solve these problems in the comment section.