Vernam Cipher and Onetime pad
The ultimate defense against such a cryptanalysis is to choose a keyword that is as long as the plaintext and has no statistical relationship to it. Such a system was introduced by an AT&T engineer named Gilbert Vernam in 1918. His system works on binary data (bits) rather than letters.The system can be expressed succinctly as follows
$c_i=p_i \bigoplus k_i$
where
$p_i$ i'th binary digit of plaintext
$k_i$ i'th binary digit of key
$c_i$ i'th binary digit of ciphertext
$\bigoplus$ excilusive-or (XOR) operation
Thus, the ciphertext is generated by performing the bitwise XOR of the plaintext and the key. Because of the properties of the XOR, decryption simply involves the same bitwise operation
$p_i=c_i \bigoplus k_i$
The essence of this technique is the means of construction of the key. Vernam proposed the use of a running loop of tape that eventually repeated the key, so that in fact the system worked with a very long but repeating keyword. Although such a scheme, with a long key, presents formidable cryptanalytic difficulties, it can be broken with sufficient ciphertext, the use of known or probable plaintext sequences, or both.
One-Time Pad
An Army Signal Corp officer, Joseph Mauborgne, proposed an improvement to the Vernam cipher that yields the ultimate in security. Mauborgne suggested using a random key that is as long as the message, so that the key need not be repeated. In addition, the key is to be used to encrypt and decrypt a single message, and then is discarded. Each new message requires a new key of the same length as the new message. Such a scheme, known as a one-time pad, is unbreakable. It produces random output that bears no statistical relationship to the plaintext. Because the ciphertext contains no information whatsoever about the plaintext, there is simply no way to break the code.
Key Features
Symmetric Cipher: The same key is used for both encryption and decryption.
One-Time Use: The key must be as long as the message and used only once. Reusing keys compromises security.
Unbreakable: When used with a truly random key that is kept secret, the cipher is theoretically unbreakable due to its perfect secrecy.
Binary Operation: The encryption and decryption processes involve a bitwise XOR operation between the plaintext and the key.
Key Generation: A random key is generated, which is the same length as the plaintext message.
Encryption:
- Convert the plaintext into binary form.
- Convert the key into binary form.
- Perform a bitwise XOR operation between the plaintext and the key to produce the ciphertext.
Decryption:
- Perform a bitwise XOR operation between the ciphertext and the key to recover the plaintext.
Suppose the plaintext is "HELLO" and the key is "XMCKL".
Convert to Binary:
- Plaintext:
HELLO→01001000 01000101 01001100 01001100 01001111 - Key:
XMCKL→01011000 01001101 01000011 01001011 01001100
- Plaintext:
Encryption (XOR each bit):
- Ciphertext:
00010000 00001000 00001111 00000111 00000011
- Ciphertext:
Decryption (XOR with the same key):
- Recover the original plaintext from the ciphertext.
- Perfect Security: Offers perfect secrecy if the key is truly random, used only once, and kept secret.
- Key Management: The key must be as long as the message and securely shared between the sender and receiver, which can be impractical for large messages.
- Key Reuse: Reusing a key for multiple messages can lead to security vulnerabilities.
While the Vernam cipher is impractical for most modern communication due to key management challenges, it is used in situations where absolute security is required, such as diplomatic communications.
Overall, the Vernam cipher is a fundamental concept in cryptography that demonstrates the importance of key management and randomness in achieving secure communication.
Suppose that we are using a Vigenère scheme with 27 characters in which the twenty-seventh character is the space character, but with a one-time key that is as long as the message. Consider the ciphertext
ANKYODKYUREPFJBYOJDSPLREYIUNOFDOIUERFPLUYTS
We now show two different decryptions using two different keys:
ciphertext: ANKYODKYUREPFJBYOJDSPLREYIUNOFDOIUERFPLUYTS
key: pxlmvmsydofuyrvzwc tnlebnecvgdupahfzzlmnyih
plaintext: mr mustard with the candlestick in the hall
ciphertext: ANKYODKYUREPFJBYOJDSPLREYIUNOFDOIUERFPLUYTS
key: mfugpmiydgaxgoufhklllmhsqdqogtewbqfgyovuhwt
plaintext: miss scarlet with the knife in the library
Suppose that a cryptanalyst had managed to find these two keys.Two plausible plaintexts are produced. How is the cryptanalyst to decide which is the correct decryption (i.e., which is the correct key)? If the actual key were produced in a truly random fashion, then the cryptanalyst cannot say that one of these two keys is more likely than the other.Thus, there is no way to decide which key is correct and therefore
which plaintext is correct.
In fact, given any plaintext of equal length to the ciphertext, there is a key that produces that plaintext. Therefore, if you did an exhaustive search of all possible keys, you would end up with many legible plaintexts, with no way of knowing which was the intended plaintext.Therefore, the code is unbreakable.
The security of the one-time pad is entirely due to the randomness of the key.If the stream of characters that constitute the key is truly random, then the stream of characters that constitute the ciphertext will be truly random. Thus, there are no patterns or regularities that a cryptanalyst can use to attack the ciphertext.
In theory, we need look no further for a cipher.The one-time pad offers complete security but, in practice, has two fundamental difficulties:
1. There is the practical problem of making large quantities of random keys.Any heavily used system might require millions of random characters on a regular basis. Supplying truly random characters in this volume is a significant task.
2. Even more daunting is the problem of key distribution and protection. For every message to be sent, a key of equal length is needed by both sender and receiver.Thus, a mammoth key distribution problem exists.
Because of these difficulties, the one-time pad is of limited utility and is useful primarily for low-bandwidth channels requiring very high security.The one-time pad is the only cryptosystem that exhibits what is referred to as perfect secrecy.
Python Code - Vernam Cipher
def vernam_cipher_encrypt(plaintext, key):
"""
Encrypts the plaintext using the Vernam cipher with the given key.
"""
if len(plaintext) != len(key):
raise ValueError("Plaintext and key must be of the same length.")
# Encrypt each character by XOR-ing it with the corresponding key character
ciphertext = ''.join(chr(ord(p) ^ ord(k)) for p, k in zip(plaintext, key))
return ciphertext
def vernam_cipher_decrypt(ciphertext, key):
"""
Decrypts the ciphertext using the Vernam cipher with the given key.
"""
# Decrypt by XOR-ing each character with the corresponding key character
plaintext = ''.join(chr(ord(c) ^ ord(k)) for c, k in zip(ciphertext, key))
return plaintext
# Example usage:
plaintext ="HELLO"
key="XMCKL"
# Encrypt the plaintext
ciphertext = vernam_cipher_encrypt(plaintext, key)
print("Ciphertext:", ciphertext)
# Decrypt the ciphertext
decrypted_text = vernam_cipher_decrypt(ciphertext, key)
print("Decrypted text:", decrypted_text)
Comments
Post a Comment