The encryption schemes in Part I are fun to play with but they are not effective enough to protect passwords and messages in the modern world. With huge computing power and far faster machines, we can brute force most of these techniques. The others can be cracked by using statistical techniques. So how can we protect our messages in this age where every week seems to bring some new security leak?
Block Ciphers
Encryption
The approach is to use more and more complicated techniques of obfuscating the data using a class of ciphers, named block ciphers. Block ciphers have a series of steps (say 35) which perform a sequence of operations, such as xoring the input value with a key or shifting the values or permuting the digits. However, the block ciphers only work on a fixed number of bits.
Consider a block cipher that has a block size of 64 and a key size of 56: then we would divide the message we wish to send into 64-bit chunks. We would encrypt each of these chunks separately using the given block cipher and then send off the encrypted message. For example, say we were encoding the message ABRACADABRA and the block size was two letters long, then the message would be divided into AB|RA|CA|DA|BR|A_ (where _ is some padding value to make sure we fill the end of the last block).
This leads to one final question: how do we encrypt the chunks? Do we do them completely separately (e.g. encrypt AB, and then RA, and so on)? No, since then a given message will always output the same value. Consider if we wanted to either send “Attack” or “Retreat”. If the “Attack”/“Retreat” encrypted message always gives the same value, the enemy will always know whether we are attacking/retreating following the first encounter.
Instead, we must ‘chain’ the blocks together. This is accomplished by randomly creating a bit-string of the same length as the block size of the block cipher. This is then xor-ed with the initial chunk of the input message. Then, we encrypt this value to give the first block of the cipher text. This result is xor-ed onto the second block and the result is encrypted. The chain continues until the end of the message.
For example, say the initialisation vector was 10 and the message 01|10|11(the block size is 2) then we would have (where the encryption function of the block cipher just gives the original value — clearly this would not be the case in reality):
10 xor 01 = 11 — encrypted —> 11
11 xor 10 = 01 — encrypted —> 01
01 xor 11 = 10 — encrypted —> 10
so the cipher text is 10|11|01|10 (we put the initialisation vector as the first block).
This is only an example method of chaining (there are others).
Decryption
To decrypt, we basically just do the same thing in reverse. We decrypt the cipher text and xor the result with the previous cipher text to get the original message
Using the example above:
11 — decrypted —> 11 xor 10 = 01
01 — decrypted —> 01 xor 11 = 10
10 — decrypted —> 10 xor 01 = 11
so the original message was 01|10|11!
Real Life Examples
Some practical implementations of these block ciphers are DES by the US government (but this has been found to be insecure due to its small block size) and the more secure, more complicated cipher AES (again constructed by the US).
Generating private keys
The ciphers I have described in this post and before have relied on having a common private key between the participants, but how can such a key be transmitted without the two participants physically meeting up? We could imagine a perfectly secure wire down which Alice sends Bob the message (it is always Alice and Bob). However, this is clearly impractical.
Diffie-Hellman Public Key Encryption
This is a pretty elegant, simple scheme for generating such private keys. Imagine we have two values a and b (a for Alice and b for Bob), which Alice and Bob hold securely. Then, we have some other value g (g may be known to everyone, including eavesdropper Eve). Then:
1. Alice sends Bob g^a
2. Bob sends Alice g^b
3. The key is now g^(ab) (or a hash of this value)
Alice and Bob can easily determine the key (Alice does (g^b)^a since she knows a and has received g^b and Bob works similarly).
However, Eve cannot determine g^(ba) because determining g^ba from g^b, g^a, and g is an extremely difficult problem provided that g satisfies certain mathematical properties.
Using this technique, we can now exchange keys securely!
Tunney Ideas 