CryptoBook
Search…
Author: chuck_bartowski

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(addition modulo 2) can be used as an encryption scheme as follows: The message space is
$\mathcal M \subseteq \{0, 1\}^n$
(i.e.: length n bit strings), the key space is
$\mathcal K = \{0, 1\}$
and the ciphertext space is also
$\{0,1\}$
Encryption:
$\text{Enc}(m,k) = m \oplus k$
Decryption:
$\text{Dec}(c,k) = c \oplus k$
The correctness of the schemes is easily verifiable. If the encryption produces
$c = m \oplus k$
, then the decryption produces
$m' = c \oplus k = m \oplus k \oplus 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