The One Time Pad

Introduction
The One Time Pad (OTP) is a well known example of encryption schemes that provide "perfect secrecy". Informally, this means that observing a ciphertext does no give any information to the eavesdropper. A proof of this fact will be provided later. Crucially we will assume that the sender and the receiver have both access to a common source of random bits. 
XOR as a One-Time Pad
XOR(addition modulo 2) can be used as an encryption scheme as follows: The message space is M⊆{0,1}n\mathcal M \subseteq \{0, 1\}^nM⊆{0,1}n
(i.e.: length n bit strings), the key space is K={0,1}\mathcal K = \{0, 1\}K={0,1}
 and the ciphertext space is also {0,1}\{0,1\}{0,1}
​
Encryption: Enc(m,k)=m⊕k\text{Enc}(m,k) = m \oplus kEnc(m,k)=m⊕k
​
Decryption:Dec(c,k)=c⊕k\text{Dec}(c,k) = c \oplus kDec(c,k)=c⊕k
​
The correctness of the schemes is easily verifiable. If the encryption produces c=m⊕kc = m \oplus kc=m⊕k
, then the decryption produces m′=c⊕k=m⊕k⊕k=mm' = c \oplus k = m \oplus k \oplus k = mm′=c⊕k=m⊕k⊕k=m
.
In the Python snippet below with use to os module to generate random bits. 
1
import os
2
​
3
def xor(a,b):
4
    res = bytes([x^y for (x,y) in zip(a,b)])
5
    return res
6
    
7
message = b"YELLOW SUBMARINE"
8
key = os.urandom(len(message))
9
ciphertext = xor(message, key)
10
recovered = xor(ciphertext, key)
11
print(f"Message: {message}\nKey: {key}\nCiphertext: {ciphertext}\nrecovered: {recovered}")
12
# A possible ouput might be as below
13
# Message: b'YELLOW SUBMARINE'
14
# Key: b'\x8e<3\xc9\x8d\xbaD\x16Zb\x1b\xbb\xb3\[email protected]<'
15
# Ciphertext: b'\xd7y\x7f\x85\xc2\xeddE\x0f V\xfa\xe1E\x0ey'
16
# recovered: b'YELLOW SUBMARINE'
Copied!
As seen above the receiver with access to the same key can recover the message. 
Generalized One-Time Pad
Although XOR is commonly used for the OTP, OTP can be made out of more general objects. If fact We can define an OTP if the message and the keys are objects from a set with a group like structure. (see GroupTheorySection #TODO)

Symmetric Cryptography - Previous

Encryption

Next - Symmetric Cryptography

AES

Last modified 5mo ago

Export as PDF

Copy link

Contents

Introduction

XOR as a One-Time Pad

Generalized One-Time Pad