Substitution ciphers - vernam and one-time pad

Question 1

What is the vernam cipher?

Answer 1

1. a system where keyword/key is as long as plaintext and has no statistical relationship to it.
2. Works on binary data (bits) rather than letters, using XOR ⊕.
3. It is a stream cipher - Ciphertext is generated by bitwise XOR of plaintext pi and key ki (each bit of the plaintext is XORed with each bit of the key)

Question 2

How does XOR work?

Answer 2

0 ⊕ 0 = 0
0 ⊕ 1 = 1
1 ⊕ 0 = 1
1 ⊕ 1 = 0

More rules:
a ⊕ a = 0
a ⊕ 0 = a
a ⊕ b = b ⊕ a
a ⊕ b ⊕ b = a
(a ⊕ b) ⊕ c = a ⊕ (b ⊕ c)

XOR can be used as polyalphabetic cipher:
P ⊕ K = C -> ci = pi ⊕ ki
C ⊕ K = P -> pi = ci ⊕ ki

pi/ci/ki = ith binary digit of plaintext/ciphertext/key.

Question 3

What is the security of the vernam cipher?

Answer 3

Difficult to break if key is long, BUT still breakable with sufficient ciphertext, use of known or probable plaintext sequences, or both.

Question 4

Example of how perfect secrecy can be achieved?

Answer 4

1. CANNOT USE A SUBSTITUTION CIPHER as its easy to break as the message is really small.
2. Use a system with two keys K1 and K2 and these two keys are EQUALLY LIKELY.
   a. K1 encrypts “buy” to 0 and “sell” to 1:
   EK1(”buy”) = 0 and EK1(”sell”) = 1.
   b. K2 encrypts “buy” to 1 and “sell” to 0:
   EK2(”buy”) = 1 and EK2(”sell”) = 0
3. If the attacker intercepts a 0, then all that he can deduce is that the message might be “sell” if K2
   was used, or “buy” if K1 was used.
4. Since each key is equally likely, the attacker is forced to guess which key was used: the chances of guessing correctly are 50%.
5. THIS IS PERFECT SECRECY - NEVER 100% OF GETTING IT RIGHT BUT THIS COMES AT A PRICE (ONE TIME PAD)

Question 5

What is one-time pad?

Answer 5

1. Use a truly random key:
   a. that is as long as the message, so that the key need not be repeated,
   b. the same key is used to encrypt and decrypt a single message, and then discarded.

KEY IS NOT REPEATED TO MATCH LENGTH OF PLAINTEXT MSG LIKE IT IS IN VIGENERE OR VERNAM CIPHERS.

Question 6

Other properties of one-time pad

Answer 6

1. Each new message P requires a new key of same length as P.
2. Produces random output with no statistical relation to plaintext.
3. Unbreakable: C contains no information whatsoever about P.
4. Only cryptosystem that exhibits so-called perfect secrecy.

Question 7

Why is one-time pad unbreakable?

Answer 7

1. For the same ciphertext -> to decrypt you need a key k that is the same length as the ciphertext -> obtain the plaintext.
2. To decrypt the same ciphertext again -> a new key should be used -> new plaintext obtained.
3. You will have many plaintexts for a single ciphertext and there is no way to know what the intended one is. What is the correct decryption using K1 and K2 to decrypt the same ciphertext?
4. no patterns or irregularities: If the stream of keys produced is RANDOM then, the CIPHERTEXT produced using this key is also RANDOM.

Question 8

What are some of the difficulties of one-time pad?

Answer 8

1. You will have to make large quantities of keys - one for every message you want to send.
2. Key distribution and protection, where for every message to be sent, a key of equal length is needed by both sender and receiver.
3. therefore, it has limited utility (useful primarily for low-bandwidth channels that need very high security)