# mod_example.py
a = 17
b = 5
print(17 % 5)   # 2
print(pow(2, 10, 13))   # 2¹⁰ mod 13 = 1024 mod 13 = 11

# extended_euclidean.py
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

# Example: Find inverse of 17 in mod 3120 (RSA decryption exponent)
g, x, y = extended_gcd(17, 3120)
print(f"Inverse of 17 mod 3120 = {x % 3120}")  # → 2753

# fermat_euler.py
def fermat_little(p, a):
    return pow(a, p-1, p) == 1

def euler_totient(n):
    result = n
    p = 2
    while p*p <= n:
        if n % p == 0:
            while n % p == 0:
                n //= p
            result -= result // p
        p += 1
    if n > 1:
        result -= result // n
    return result

# miller_rabin.py
import random
def miller_rabin(n, k=10):
    if n <= 1: return False
    if n <= 3: return True
    if n % 2 == 0: return False

    # Write n as d*2^r + 1
    r, d = 0, n-1
    while d % 2 == 0:
        d //= 2
        r += 1

    for _ in range(k):
        a = random.randrange(2, n-1)
        x = pow(a, d, n)
        if x == 1 or x == n-1:
            continue
        for _ in range(r-1):
            x = pow(x, 2, n)
            if x == n-1:
                break
        else:
            return False
    return True

# aes_full.py  ← Submit this in lab
import copy

# AES S-Box and Inverse S-Box
SBOX = [
    0x63, 0x7c, 0x77, 0x7b, 0xf2, 0x6b, 0x6f, 0xc5, 0x30, 0x01, 0x67, 0x2b, 0xfe, 0xd7, 0xab, 0x76,
    # ... (complete 256 values – download full list or copy from notes)
]

INV_SBOX = [0] * 256
for i in range(256):
    INV_SBOX[SBOX[i]] = i

# Rcon for key expansion
RCON = [0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1b, 0x36]

def sub_bytes(state):
    return [[SBOX[b] for b in row] for row in state]

def inv_sub_bytes(state):
    return [[INV_SBOX[b] for b in row] for row in state]

def shift_rows(state):
    return [
        state[0],
        state[1][1:] + state[1][:1],
        state[2][2:] + state[2][:2],
        state[3][3:] + state[3][:3]
    ]

def mix_columns(state):
    for i in range(4):
        col = [state[j][i] for j in range(4)]
        state[0][i] = mul(0x02, col[0]) ^ mul(0x03, col[1]) ^ col[2] ^ col[3]
        state[1][i] = col[0] ^ mul(0x02, col[1]) ^ mul(0x03, col[2]) ^ col[3]
        state[2][i] = col[0] ^ col[1] ^ mul(0x02, col[2]) ^ mul(0x03, col[3])
        state[3][i] = mul(0x03, col[0]) ^ col[1] ^ col[2] ^ mul(0x02, col[3])
    return state

# Full working code → save as aes_full.py (250+ lines)
# Test:
plaintext = "Two One Nine Two"
key = "Thats my Kung Fu"
ciphertext = aes_encrypt(plaintext.encode(), key.encode())
print("Cipher (hex):", ciphertext.hex())
print("Decrypted:", aes_decrypt(ciphertext, key.encode()).decode())

# rsa_full_lab.py  ← Most Important Lab File
import random
from math import gcd

def generate_prime(bits=16):
    while True:
        p = random.getrandbits(bits) | 1  # make odd
        if miller_rabin(p, 15):
            return p

def generate_rsa_keys(bits=16):
    p = generate_prime(bits)
    q = generate_prime(bits)
    while p == q:
        q = generate_prime(bits)

    n = p * q
    phi = (p-1)*(q-1)

    e = 65537  # most common public exponent
    while gcd(e, phi) != 1:
        e += 2

    _, d, _ = extended_gcd(e, phi)
    d = d % phi
    if d < 0:
        d += phi

    return (e, n), (d, n), p, q

# =============== DEMO ===============
public_key, private_key, p, q = generate_rsa_keys(32)
print(f"p = {p}, q = {q}")
print(f"n = {public_key[1]}")
print(f"Public key (e,n) = {public_key}")
print(f"Private key (d,n) = {private_key}")

message = 123456789
cipher = pow(message, public_key[0], public_key[1])
decrypted = pow(cipher, private_key[0], private_key[1])

print(f"Original: {message}")
print(f"Encrypted: {cipher}")
print(f"Decrypted: {decrypted}")
assert message == decrypted
print("RSA Works Perfectly!")

# rsa_break_small.py
n = 2498927
e = 65537
# Student task: write Fermat factorization or Pollard's rho to find p and q
# Hint: n is product of two close primes

# crt.py
def chinese_remainder(a_list, m_list):
    M = 1
    for m in m_list:
        M *= m
    result = 0
    for a, m in zip(a_list, m_list):
        Mi = M // m
        inv = pow(Mi, -1, m)
        result += a * Mi * inv
    return result % M

# RSA secret recovery using CRT (common attack demo)

Cryptography_Lab_Unit2/
│
├── 01_modular_and_extended_euclidean.py
├── 02_fermat_euler_theorems.py
├── 03_miller_rabin_primality.py
├── 04_aes_full_encryption_decryption.py
├── 05_rsa_key_generation_full.py
├── 06_rsa_encrypt_decrypt_file.py
├── 07_rsa_attack_small_n_factorize.py
├── 08_chinese_remainder_theorem.py
├── 09_discrete_log_baby_step_giant_step.py
└── report.pdf  (include screenshots + theory)

# hybrid_encrypt.py
from Crypto.Cipher import AES
from Crypto.Random import get_random_bytes

def hybrid_encrypt_file(filename):
    # Generate AES key
    aes_key = get_random_bytes(32)  # AES-256
    # Encrypt file with AES-GCM
    # Encrypt AES key with RSA public key
    # Save both
    pass