Vernam Cipher with Blum-Blum-Shub Generator

A cryptographically secure implementation of the Vernam Cipher (one-time pad) using the Blum-Blum-Shub (BBS) pseudorandom number generator for key generation.

Overview

This project demonstrates a practical implementation of the Vernam cipher, also known as the one-time pad, which is theoretically unbreakable when used correctly. The encryption key is generated using the Blum-Blum-Shub algorithm, a cryptographically secure pseudorandom number generator based on the computational difficulty of factoring large numbers.

Features

• Blum-Blum-Shub Generator: Cryptographically secure PRNG implementation
• Vernam Cipher Encryption/Decryption: XOR-based encryption with generated keys
• NIST Statistical Tests: Randomness verification using official NIST test suite
  • Frequency (Monobit) Test
  • Runs Test
• Miller-Rabin Primality Testing: Efficient generation of large Blum primes
• Text-to-Binary Conversion: Full text encryption support

How It Works

1. Blum-Blum-Shub Generator

The BBS generator is based on the following mathematical properties:

p ≡ 3 (mod 4) and q ≡ 3 (mod 4)  (Blum primes)
n = p × q  (Blum integer)
X(i+1) = X(i)² mod n
Output bit = X(i) mod 2  (least significant bit)

Security: The BBS generator's security is based on the computational hardness of factoring n into p and q.

2. Vernam Cipher

The Vernam cipher performs XOR operations between plaintext and key:

Encryption: C = P ⊕ K
Decryption: P = C ⊕ K

Where:

• P = Plaintext (message)
• K = Key (pseudorandom bits from BBS)
• C = Ciphertext (encrypted message)
• ⊕ = XOR operation

3. NIST Statistical Tests

The generated key stream is validated using NIST SP 800-22 tests to ensure cryptographic quality:

• Frequency Test: Verifies balanced distribution of 0s and 1s
• Runs Test: Checks for appropriate randomness in bit transitions

Project Structure

vernam-cipher/
│
├── blum-blum-shub.py    # BBS generator implementation
├── main.py              # Main encryption/decryption pipeline
├── nist_tests.py        # NIST statistical test suite
├── message.txt          # Input message file
└── README.md            # This file

Installation

Prerequisites

• Python 3.7 or higher
• No external dependencies required (uses only standard library)

Setup

git clone <repository-url>
cd vernam-cipher

Usage

Basic Usage

1. Create or modify message.txt with your message:

echo "Your secret message here" > message.txt

2. Run the encryption/decryption:

python main.py

Example Output

Reading message from file...
   Read 25 characters

Converting text to bits...
   Message length in bits: 200 bits

Generating key using Blum-Blum-Shub generator...
Generating prime number p...
Generating prime number q...
Generating seed s...
BBS Generator initialized:
  p = 340282366920938463463374607431768211297
  q = 340282366920938463463374607431768211507
  n = 115792089237316195423570985008687907852589419931798687112530834793049593217279
  s = 12345678901234567890

   Generating key of length 200 bits...
   First 100 bits of key: 1010110101...

NIST statistical tests - verifying key randomness...

TEST 1: Frequency Test (Frequency / Monobit Test)
Test PASSED (p-value = 0.835910 >= α = 0.01). Sequence appears random.

TEST 2: Runs Test
Test PASSED (p-value = 0.762341 >= α = 0.01). Sequence appears random.

Encrypting message...
   Encrypted message length: 200 bits

Decrypting message...
   Decrypted message length: 200 bits

Consistency check...
   Bits match:  YES
   Text match: YES
   Message was successfully decrypted.

API Reference

BlumBlumShubGenerator Class

from blum_blum_shub import BlumBlumShubGenerator

# Initialize with auto-generated parameters (recommended)
bbs = BlumBlumShubGenerator(bits=256)

# Or specify custom parameters
bbs = BlumBlumShubGenerator(p=23, q=31, s=7, bits=128)

# Generate random bits
key_bits = bbs.generate_bits(1000)  # Generate 1000 random bits

Parameters:

• p (int, optional): Blum prime (p ≡ 3 mod 4). Auto-generated if None.
• q (int, optional): Blum prime (q ≡ 3 mod 4). Auto-generated if None.
• s (int, optional): Seed coprime to n. Auto-generated if None.
• bits (int): Size of prime numbers in bits (default: 256)

NISTTests Class

from nist_tests import NISTTests

# Initialize with significance level
nist = NISTTests(alpha=0.01)

# Run all tests
results = nist.run_all_tests(bit_sequence)

# Run individual tests
p_value, passed, interpretation = nist.frequency_test(bit_sequence)
p_value, passed, interpretation = nist.runs_test(bit_sequence)

Security Considerations

Strengths

1. Cryptographically Secure PRNG: BBS is proven to be cryptographically secure under the quadratic residuosity assumption
2. Vernam Cipher: Theoretically unbreakable with truly random keys
3. Statistical Validation: NIST tests ensure key quality

Limitations

1. Key Reuse: Never reuse the same key for multiple messages (breaks Vernam security)
2. PRNG vs True Randomness: BBS is pseudorandom, not truly random
3. Key Length: Key must be at least as long as the message
4. Computational Cost: Generating large Blum primes can be time-consuming

Best Practices

• Generate new BBS parameters for each encryption session
• Use at least 256-bit primes for production use
• Store seeds and parameters securely
• Never transmit the seed over insecure channels
• Implement proper key distribution mechanisms

Mathematical Background

Miller-Rabin Primality Test

Used to efficiently test if a number is prime with high probability. For k=5 rounds, the error probability is less than (1/4)^5 ≈ 0.098%.

Blum Primes

Special primes where p ≡ 3 (mod 4). These primes ensure that the BBS generator has a long period and good statistical properties.

Quadratic Residuosity

The security of BBS relies on the difficulty of determining whether a number is a quadratic residue modulo n without knowing the factorization of n.