CryptoBook
  • CryptoBook
  • Book Plan
  • Style Guide
    • Sample Page
  • Contributors
  • Fundamentals
    • Mathematical Notation
    • Division and Greatest common divisor
      • Euclidean Algorithm
    • Modular Arithmetic
      • Theorems of Wilson, Euler, and Fermat
        • Fermat's Little Theorem in Detail
        • Euler's Theorem in Detail
      • Quadratic Residues
    • Continued Fractions
  • Number Theory
  • Ideals
  • Polynomials With Shared Roots
  • Integer Factorization
    • Pollard rho
    • Sieves
  • Abstract algebra
    • Groups
      • Another take on groups
      • Discrete Log Problem
    • Rings
    • Fields
    • Polynomials
  • Elliptic Curves
    • Untitled
  • Lattices
    • Introduction
    • LLL reduction
      • Gram-Schmidt Orthogonalization
      • Lagrange's algorithm
      • LLL reduction
    • Lattice reduction
      • Minkowski reduced
      • HKZ reduced
      • LLL reduced
    • Applications
      • Coppersmith algorithm
      • Extensions of Coppersmith algorithm
    • Hard lattice problems
    • Lattices of interest
    • Cryptographic lattice problems
      • Short integer solutions (SIS)
      • Learning with errors (LWE)
      • Ring-LWE
      • NTRU
    • Interactive fun
    • Resources and notations
  • Asymmetric Cryptography
  • RSA
    • Proof of correctness
    • RSA application
    • Low Private Component Attacks
      • Wiener's Attack
      • Boneh-Durfee Attack
    • Common Modulus Attack
    • Recovering the Modulus
  • Diffie-Hellman
    • MITM
  • Elliptic Curve Cryptography
  • Symmetric Cryptography
    • Encryption
    • The One Time Pad
    • AES
      • Rijndael Finite Field
      • Round Transformations
  • Hashes
    • Introduction / overview
    • The Birthday paradox / attack
  • Isogeny Based Cryptography
    • Introduction to Isogeny Cryptography
    • Isogenies
    • Isogeny and Ramanujan Graphs
  • Appendices
    • Sets and Functions
    • Probability Theory
Powered by GitBook
On this page
  • Introduction
  • XOR as a One-Time Pad
  • Generalized One-Time Pad

Was this helpful?

Export as PDF
  1. Symmetric Cryptography

The One Time Pad

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 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.

import os

def xor(a,b):
    res = bytes([x^y for (x,y) in zip(a,b)])
    return res
    
message = b"YELLOW SUBMARINE"
key = os.urandom(len(message))
ciphertext = xor(message, key)
recovered = xor(ciphertext, key)
print(f"Message: {message}\nKey: {key}\nCiphertext: {ciphertext}\nrecovered: {recovered}")
# A possible ouput might be as below
# Message: b'YELLOW SUBMARINE'
# Key: b'\x8e<3\xc9\x8d\xbaD\x16Zb\x1b\xbb\xb3\x0c@<'
# Ciphertext: b'\xd7y\x7f\x85\xc2\xeddE\x0f V\xfa\xe1E\x0ey'
# recovered: b'YELLOW SUBMARINE'

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)

PreviousEncryptionNextAES

Last updated 4 years ago

Was this helpful?