Welcome to part 2 of my posts on the material from the “Cryptography I” course. In this course the material is designed to teach students about how to scientifically determine what concepts/algorithms are and are not cryptographically secure. I am continuing this series of posts so that I can have some way to review the information at a later time as well as to provide my interpretation of the material for others to read and comment on. Enjoy!
In the first part I cover topics like Probability Distributions (Uniform and Point), Events, Randomized Algorithms and Independence.
XOR proves to be a very important aspect of cryptography and is actually use in many ciphers like OTP, DES and AES. Therefore if you are not familiar with the concept of XOR, now would be a good time to read up on it. Basically the following truth table provides the mapping for XOR given X and Y inputs.
(X, Y) | Z
(0, 0) | 0
(0, 1) | 1
(1, 0) | 1
(1, 1) | 0
A Symmetric Cipher is one that uses the same key (k) for the sender and receiver. For example if Alice sends Bob a message, both Alice and Bob must use the same key to be able to securely send and receive messages.
More formally we can define it such that over a key space of all possible keys (K), a message space of all possible messages (M) and a cipher text space of all possible CT (C) the cipher is efficient where encryption (E) and decryption (D):
E: K x M -> C
D: K x C -> M
such that... ∀ m in M, k in K: D(k, E(k, m)) = m
∀ = For all
Note that E is often randomized but D is always deterministic!
The One Time Pad (OTP)
First described by Frank Miller in 1882, the one-time pad was re-invented in 1917. On July 22, 1919, U.S. Patent 1,310,719 was issued to Gilbert S. Vernam for the XOR operation used for the encryption of a one-time pad. It is derived from the Vernam cipher, named after Gilbert Vernam, one of its inventors. Vernam’s system was a cipher that combined a message with a key read from a punched tape.
OTP uses a very simple concept of XORing the plaintext message with the key to produce some ciphertext (c) that cannot easily be decrypted.
ciphertext: E(k, m) = k ⊕ m
plaintext: D(k, c) = k ⊕ c
Note: D(k, E(k, m)) = D(k, k ⊕ m) = k ⊕ (k ⊕ m) = (k ⊕ k) ⊕ m = m
m = 0110001
k = 1101110
c = 1011111
Note that k must be at least as long as m to securely encrypt m
As we can see OTP is a very fast encryption and decryption cipher but it needs long keys. Now however we really need to ask what defines a “good” cipher?
The basic idea to secure a plaintext (PT) message is that the …