Cryptography

Last updated: December 2024

Disclaimer: These are my personal notes compiled for my own reference and learning. They may contain errors, incomplete information, or personal interpretations. While I strive for accuracy, these notes are not peer-reviewed and should not be considered authoritative sources. Please consult official textbooks, research papers, or other reliable sources for academic or professional purposes.

1. Introduction to Cryptography

Cryptography is the science of secure communication in the presence of adversaries.

Key concepts:

2. Classical Cryptography

2.1 Caesar Cipher

Shift each letter by a fixed amount $k$:

$$E_k(x) = (x + k) \bmod 26$$ $$D_k(c) = (c - k) \bmod 26$$

2.2 Affine Cipher

Use linear transformation:

$$E_{a,b}(x) = (ax + b) \bmod 26$$ $$D_{a,b}(c) = a^{-1}(c - b) \bmod 26$$

where $\gcd(a, 26) = 1$ and $a^{-1}$ is the modular inverse of $a$.

2.3 Vigenère Cipher

Use a keyword to determine shifts for each position.

3. Symmetric Cryptography

Same key used for encryption and decryption.

3.1 Block Ciphers

3.2 Stream Ciphers

Encrypt one bit/byte at a time using a keystream.

4. Public Key Cryptography

Different keys for encryption and decryption.

5. RSA Cryptosystem

5.1 Key Generation

  1. Choose two large primes $p$ and $q$
  2. Compute $n = pq$ and $\phi(n) = (p-1)(q-1)$
  3. Choose $e$ such that $\gcd(e, \phi(n)) = 1$
  4. Compute $d \equiv e^{-1} \pmod{\phi(n)}$
  5. Public key: $(n, e)$, Private key: $(n, d)$

5.2 Encryption and Decryption

$$\text{Encryption: } c \equiv m^e \pmod{n}$$ $$\text{Decryption: } m \equiv c^d \pmod{n}$$

5.3 Security

Security relies on the difficulty of factoring large integers.

6. Discrete Logarithm Problem

Given $g$, $p$, and $y = g^x \bmod p$, find $x$.

This is believed to be computationally hard for large primes $p$.

7. Diffie-Hellman Key Exchange

  1. Alice and Bob agree on prime $p$ and generator $g$
  2. Alice chooses secret $a$, sends $A = g^a \bmod p$
  3. Bob chooses secret $b$, sends $B = g^b \bmod p$
  4. Shared secret: $K = g^{ab} \bmod p$

8. ElGamal Cryptosystem

8.1 Key Generation

  1. Choose prime $p$ and generator $g$
  2. Choose private key $x$
  3. Compute public key $y = g^x \bmod p$

8.2 Encryption

To encrypt message $m$:

  1. Choose random $k$
  2. Compute $c_1 = g^k \bmod p$
  3. Compute $c_2 = my^k \bmod p$
  4. Ciphertext: $(c_1, c_2)$

8.3 Decryption

$$m = c_2 \cdot (c_1^x)^{-1} \bmod p$$

9. Elliptic Curve Cryptography

Uses elliptic curves over finite fields. Curve equation:

$$y^2 = x^3 + ax + b \pmod{p}$$

Provides same security as RSA with smaller key sizes.

10. Digital Signatures

10.1 RSA Signatures

$$\text{Sign: } s \equiv m^d \pmod{n}$$ $$\text{Verify: } m \stackrel{?}{=} s^e \pmod{n}$$

10.2 DSA (Digital Signature Algorithm)

Based on discrete logarithm problem in subgroups.

11. Hash Functions

One-way functions that compress arbitrary input to fixed-size output.

Properties:

12. Security Considerations

12.1 Key Management

Secure generation, distribution, and storage of keys.

12.2 Side-Channel Attacks

Attacks based on timing, power consumption, or electromagnetic emissions.

12.3 Quantum Cryptography

Quantum computers threaten current public key systems. Post-quantum cryptography develops quantum-resistant algorithms.

13. Code Example

# Python code for basic cryptographic operations
import random
import math

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def mod_inverse(a, m):
    """Extended Euclidean algorithm for modular inverse"""
    if gcd(a, m) != 1:
        return None
    
    def extended_gcd(a, b):
        if a == 0:
            return b, 0, 1
        gcd, x1, y1 = extended_gcd(b % a, a)
        x = y1 - (b // a) * x1
        y = x1
        return gcd, x, y
    
    _, x, _ = extended_gcd(a, m)
    return (x % m + m) % m

def mod_exp(base, exp, mod):
    """Fast modular exponentiation"""
    result = 1
    base = base % mod
    while exp > 0:
        if exp % 2 == 1:
            result = (result * base) % mod
        exp = exp >> 1
        base = (base * base) % mod
    return result

def is_prime(n):
    """Simple primality test"""
    if n < 2:
        return False
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

def generate_keypair(keysize):
    """Generate RSA key pair"""
    # Generate two random primes
    def get_prime(bits):
        while True:
            p = random.getrandbits(bits)
            if is_prime(p):
                return p
    
    p = get_prime(keysize // 2)
    q = get_prime(keysize // 2)
    
    n = p * q
    phi = (p - 1) * (q - 1)
    
    # Choose e
    e = 65537  # Common choice
    
    # Compute d
    d = mod_inverse(e, phi)
    
    return (n, e), (n, d)  # public, private

def rsa_encrypt(message, public_key):
    """RSA encryption"""
    n, e = public_key
    return mod_exp(message, e, n)

def rsa_decrypt(ciphertext, private_key):
    """RSA decryption"""
    n, d = private_key
    return mod_exp(ciphertext, d, n)

def caesar_cipher(text, shift):
    """Caesar cipher implementation"""
    result = ""
    for char in text:
        if char.isalpha():
            ascii_offset = 65 if char.isupper() else 97
            shifted = (ord(char) - ascii_offset + shift) % 26
            result += chr(shifted + ascii_offset)
        else:
            result += char
    return result

# Example usage
print("Caesar Cipher:")
plaintext = "HELLO WORLD"
shift = 3
encrypted = caesar_cipher(plaintext, shift)
decrypted = caesar_cipher(encrypted, -shift)
print(f"Original: {plaintext}")
print(f"Encrypted: {encrypted}")
print(f"Decrypted: {decrypted}")

print("\nRSA Example:")
# Generate small keys for demonstration
public_key, private_key = generate_keypair(16)
message = 42
ciphertext = rsa_encrypt(message, public_key)
decrypted_message = rsa_decrypt(ciphertext, private_key)
print(f"Original message: {message}")
print(f"Encrypted: {ciphertext}")
print(f"Decrypted: {decrypted_message}")

14. References