1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

def bytes_to_int(data: bytes) -> int:
    """
    Convert a byte sequence to an integer.
    
    Uses big-endian byte order (most significant byte first).
    This is the standard for cryptographic operations.
    """
    return int.from_bytes(data, byteorder='big')
 
def int_to_bytes(n: int, length: int = None) -> bytes:
    """
    Convert an integer to bytes.
    
    If length is specified, pads with leading zeros to reach that length.
    """
    if length is None:
        # Compute required length
        length = (n.bit_length() + 7) // 8
        if length == 0:
            length = 1
    
    return n.to_bytes(length, byteorder='big')
 
def encode_message(message: str, encoding: str = 'utf-8') -> int:
    """
    Encode a string message as an integer for RSA.
    
    Process:
    1. Convert string to bytes using specified encoding
    2. Interpret bytes as a big-endian integer
    """
    message_bytes = message.encode(encoding)
    return bytes_to_int(message_bytes)
 
def decode_message(m: int, encoding: str = 'utf-8') -> str:
    """
    Decode an integer back to a string after RSA decryption.
    """
    message_bytes = int_to_bytes(m)
    return message_bytes.decode(encoding)
 
# Demonstration
if __name__ == "__main__":
    # Example: Encode "Hello, RSA!"
    message = "Hello, RSA!"
    m = encode_message(message)
    
    print(f"Original message: '{message}'")
    print(f"As bytes: {message.encode('utf-8').hex()}")
    print(f"As integer: {m}")
    print(f"Bit length: {m.bit_length()} bits")
    
    # For 2048-bit RSA, n has ~2048 bits
    # m must be < n, so m can have at most ~2047 bits
    # That's approximately 256 bytes maximum (before padding)
    
    # Verify round-trip
    decoded = decode_message(m)
    print(f"Decoded: '{decoded}'")
    assert decoded == message
    
    # Larger example showing bit length constraints
    large_message = "A" * 200  # 200 bytes = 1600 bits
    m_large = encode_message(large_message)
    print(f"\n200-byte message needs {m_large.bit_length()} bits")
    print(f"Fits in 2048-bit RSA: {m_large.bit_length() < 2048}")

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

def rsa_encrypt_raw(message: int, e: int, n: int) -> int:
    """
    Raw RSA encryption: c = m^e mod n
    
    WARNING: This is TEXTBOOK RSA and is NOT secure for direct use!
    Always use padding (OAEP) in production.
    
    Args:
        message: Integer representation of message, must be 0 ≤ m < n
        e: Public exponent
        n: RSA modulus
    
    Returns:
        Ciphertext as integer
    """
    if not (0 <= message < n):
        raise ValueError(f"Message must be in range [0, n). Got {message}, n={n}")
    
    # Python's pow() with 3 arguments uses efficient modular exponentiation
    ciphertext = pow(message, e, n)
    
    return ciphertext
 
def rsa_decrypt_raw(ciphertext: int, d: int, n: int) -> int:
    """
    Raw RSA decryption: m = c^d mod n
    
    Args:
        ciphertext: Encrypted message as integer
        d: Private exponent
        n: RSA modulus
    
    Returns:
        Decrypted message as integer
    """
    message = pow(ciphertext, d, n)
    return message
 
def rsa_decrypt_crt(ciphertext: int, p: int, q: int, dP: int, dQ: int, qInv: int) -> int:
    """
    RSA decryption with Chinese Remainder Theorem optimization.
    
    Approximately 4x faster than standard decryption.
    
    Precomputed values:
        dP = d mod (p-1)
        dQ = d mod (q-1)
        qInv = q^(-1) mod p
    """
    # Partial decryptions with smaller moduli
    m1 = pow(ciphertext, dP, p)
    m2 = pow(ciphertext, dQ, q)
    
    # Combine using Garner's formula
    h = (qInv * (m1 - m2)) % p
    message = m2 + h * q
    
    return message
 
# Complete example with small numbers
if __name__ == "__main__":
    # Generate a small RSA key pair for demonstration
    p, q = 61, 53
    n = p * q  # 3233
    e = 17
    phi_n = (p - 1) * (q - 1)  # 3120
    d = pow(e, -1, phi_n)  # 2753
    
    # Precompute CRT parameters
    dP = d % (p - 1)
    dQ = d % (q - 1)
    qInv = pow(q, -1, p)
    
    print(f"RSA Key Pair (demonstration only - keys are too small!):")
    print(f"  Public:  (e={e}, n={n})")
    print(f"  Private: (d={d}, n={n})")
    print(f"  CRT params: dP={dP}, dQ={dQ}, qInv={qInv}")
    print()
    
    # Encrypt and decrypt
    message = 123
    print(f"Original message: m = {message}")
    
    # Encrypt
    ciphertext = rsa_encrypt_raw(message, e, n)
    print(f"Ciphertext: c = m^e mod n = {message}^{e} mod {n} = {ciphertext}")
    
    # Decrypt (standard method)
    decrypted_standard = rsa_decrypt_raw(ciphertext, d, n)
    print(f"Decrypted (standard): m = c^d mod n = {ciphertext}^{d} mod {n} = {decrypted_standard}")
    
    # Decrypt (CRT method)
    decrypted_crt = rsa_decrypt_crt(ciphertext, p, q, dP, dQ, qInv)
    print(f"Decrypted (CRT): m = {decrypted_crt}")
    
    print(f"\nAll methods agree: {message == decrypted_standard == decrypted_crt}")

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156

# Demonstrations of Textbook RSA Vulnerabilities
# These are educational examples - NEVER use textbook RSA in production!
 
import secrets
from math import gcd
 
def demo_deterministic_attack():
    """
    Demonstrate how deterministic encryption allows confirmation attacks.
    
    Scenario: Alice encrypts either "yes" or "no" and sends to Bob.
    Eve intercepts the ciphertext but can test which it is.
    """
    print("=== Deterministic Encryption Attack ===")
    
    # Small RSA for demonstration
    p, q = 61, 53
    n = p * q
    e = 17
    
    # Alice encrypts her message (let's say "yes" = 121 in our encoding)
    alice_message = 121  # "yes"
    ciphertext = pow(alice_message, e, n)
    
    print(f"Eve intercepts ciphertext: {ciphertext}")
    
    # Eve doesn't know the message, but she can guess!
    guess_yes = 121
    guess_no = 110
    
    encrypted_yes = pow(guess_yes, e, n)
    encrypted_no = pow(guess_no, e, n)
    
    print(f"Eve encrypts 'yes': {encrypted_yes}")
    print(f"Eve encrypts 'no': {encrypted_no}")
    
    if ciphertext == encrypted_yes:
        print("Eve concludes: Alice sent 'yes'!")
    elif ciphertext == encrypted_no:
        print("Eve concludes: Alice sent 'no'!")
    
    print()
 
def demo_malleability_attack():
    """
    Demonstrate how malleability allows ciphertext manipulation.
    
    Scenario: Attacker can double the encrypted amount without decrypting.
    """
    print("=== Malleability Attack ===")
    
    p, q = 61, 53
    n = p * q
    e = 17
    d = pow(e, -1, (p-1)*(q-1))
    
    # Bank encrypts transaction: $100
    amount = 100
    ciphertext = pow(amount, e, n)
    print(f"Original transaction: ${amount}")
    print(f"Encrypted ciphertext: {ciphertext}")
    
    # Attacker modifies ciphertext to double the amount
    # If c = m^e, then c' = c * 2^e = (2m)^e
    factor = 2
    modified_ciphertext = (ciphertext * pow(factor, e, n)) % n
    print(f"Modified ciphertext: {modified_ciphertext}")
    
    # Bank decrypts
    decrypted = pow(modified_ciphertext, d, n)
    print(f"Bank decrypts: ${decrypted}")
    print(f"Attacker doubled the amount without knowing it!")
    
    print()
 
def demo_small_message_attack():
    """
    Demonstrate the small message attack with e=3.
    
    If m^e < n, there's no modular reduction, so c = m^e.
    Attacker simply takes the e-th root.
    """
    print("=== Small Message Attack (e=3) ===")
    
    # Use e=3 and 2048-bit n
    n = 2 ** 2048  # Simplified; in practice n would be a semiprime
    e = 3
    
    # Small message (like a 256-bit AES key)
    message = 2 ** 128  # 128-bit value
    
    # Encrypt
    ciphertext = pow(message, e, n)
    
    # Since m^3 < n, ciphertext = message^3 exactly (no mod reduction)
    # Attacker computes cube root
    recovered = round(ciphertext ** (1/3))
    
    print(f"Message: {message}")
    print(f"m^3: {message**3}")
    print(f"n: {n}")
    print(f"m^3 < n: {message**3 < n}")
    print(f"Recovered message (cube root): {recovered}")
    print(f"Attack successful: {recovered == message}")
    
    print()
 
def demo_hastad_broadcast_attack():
    """
    Demonstrate Håstad's broadcast attack.
    
    If the same message is encrypted to 3 recipients with different n's
    and e=3, CRT can recover the message.
    """
    print("=== Håstad's Broadcast Attack (e=3) ===")
    
    # Three recipients with different moduli
    n1, n2, n3 = 3233, 2773, 1711  # Small primes for demo
    e = 3  # Same small exponent
    
    # Same message sent to all three
    message = 10  # Small for demonstration
    
    c1 = pow(message, e, n1)
    c2 = pow(message, e, n2)
    c3 = pow(message, e, n3)
    
    print(f"Message: {message}")
    print(f"c1 = {message}^3 mod {n1} = {c1}")
    print(f"c2 = {message}^3 mod {n2} = {c2}")
    print(f"c3 = {message}^3 mod {n3} = {c3}")
    
    # CRT: find x such that x ≡ c1 mod n1, x ≡ c2 mod n2, x ≡ c3 mod n3
    # Then x = m^3 (exactly, since m^3 < n1*n2*n3)
    
    N = n1 * n2 * n3
    N1, N2, N3 = N // n1, N // n2, N // n3
    
    y1 = pow(N1, -1, n1)
    y2 = pow(N2, -1, n2)
    y3 = pow(N3, -1, n3)
    
    x = (c1 * N1 * y1 + c2 * N2 * y2 + c3 * N3 * y3) % N
    
    # x = m^3, so take cube root
    recovered = round(x ** (1/3))
    
    print(f"CRT solution: {x}")
    print(f"Cube root: {recovered}")
    print(f"Attack successful: {recovered == message}")
 
if __name__ == "__main__":
    demo_deterministic_attack()
    demo_malleability_attack()
    demo_small_message_attack()
    demo_hastad_broadcast_attack()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183

"""
RSA-OAEP Implementation (Educational)
 
OAEP provides IND-CCA2 security when used with RSA.
Always use a vetted library (like PyCryptodome) for production.
"""
 
import hashlib
import secrets
 
def mgf1(seed: bytes, length: int, hash_func=hashlib.sha256) -> bytes:
    """
    Mask Generation Function 1 (MGF1).
    
    Generates a mask of specified length from a seed using a hash function.
    Used in OAEP to create pseudorandom masks.
    """
    hash_len = hash_func().digest_size
    mask = b''
    counter = 0
    
    while len(mask) < length:
        C = counter.to_bytes(4, byteorder='big')
        mask += hash_func(seed + C).digest()
        counter += 1
    
    return mask[:length]
 
def xor_bytes(a: bytes, b: bytes) -> bytes:
    """XOR two byte strings of equal length."""
    return bytes(x ^ y for x, y in zip(a, b))
 
def oaep_encode(message: bytes, k: int, label: bytes = b"", 
                hash_func=hashlib.sha256) -> bytes:
    """
    OAEP encoding as per PKCS#1 v2.2.
    
    Args:
        message: Message to encode (mLen <= k - 2*hLen - 2)
        k: RSA modulus byte length (e.g., 256 for 2048-bit RSA)
        label: Optional label (default empty)
        hash_func: Hash function to use (default SHA-256)
    
    Returns:
        Encoded message EM of length k
    """
    hLen = hash_func().digest_size  # 32 for SHA-256
    mLen = len(message)
    
    # Check message length
    if mLen > k - 2 * hLen - 2:
        raise ValueError(f"Message too long. Max: {k - 2*hLen - 2}, got: {mLen}")
    
    # Step 1: Construct data block DB = lHash || PS || 0x01 || M
    lHash = hash_func(label).digest()
    PS = b'\x00' * (k - mLen - 2 * hLen - 2)  # Zero padding
    DB = lHash + PS + b'\x01' + message
    
    # Step 2: Generate random seed
    seed = secrets.token_bytes(hLen)
    
    # Step 3: Let dbMask = MGF(seed, k - hLen - 1)
    dbMask = mgf1(seed, k - hLen - 1, hash_func)
    
    # Step 4: Let maskedDB = DB ⊕ dbMask
    maskedDB = xor_bytes(DB, dbMask)
    
    # Step 5: Let seedMask = MGF(maskedDB, hLen)
    seedMask = mgf1(maskedDB, hLen, hash_func)
    
    # Step 6: Let maskedSeed = seed ⊕ seedMask
    maskedSeed = xor_bytes(seed, seedMask)
    
    # Step 7: EM = 0x00 || maskedSeed || maskedDB
    EM = b'\x00' + maskedSeed + maskedDB
    
    return EM
 
def oaep_decode(EM: bytes, k: int, label: bytes = b"",
                hash_func=hashlib.sha256) -> bytes:
    """
    OAEP decoding as per PKCS#1 v2.2.
    
    Returns the original message, or raises ValueError if decoding fails.
    
    SECURITY NOTE: In production, all checks must be done in constant time
    to prevent timing attacks. This implementation is for education only.
    """
    hLen = hash_func().digest_size
    
    # Check lengths
    if len(EM) != k:
        raise ValueError("Incorrect encoded message length")
    if k < 2 * hLen + 2:
        raise ValueError("Modulus too short")
    
    # Split EM into components
    Y = EM[0:1]
    maskedSeed = EM[1:1+hLen]
    maskedDB = EM[1+hLen:]
    
    # Check Y == 0x00
    if Y != b'\x00':
        raise ValueError("Decoding error: Y != 0x00")
    
    # Recover seed
    seedMask = mgf1(maskedDB, hLen, hash_func)
    seed = xor_bytes(maskedSeed, seedMask)
    
    # Recover DB
    dbMask = mgf1(seed, k - hLen - 1, hash_func)
    DB = xor_bytes(maskedDB, dbMask)
    
    # Parse DB = lHash' || PS || 0x01 || M
    lHash_prime = DB[:hLen]
    
    # Verify lHash
    lHash = hash_func(label).digest()
    if lHash_prime != lHash:
        raise ValueError("Decoding error: label hash mismatch")
    
    # Find 0x01 separator
    rest = DB[hLen:]
    separator_index = rest.find(b'\x01')
    if separator_index == -1:
        raise ValueError("Decoding error: separator not found")
    
    # Verify PS is all zeros
    PS = rest[:separator_index]
    if PS != b'\x00' * len(PS):
        raise ValueError("Decoding error: invalid padding")
    
    # Extract message
    message = rest[separator_index + 1:]
    
    return message
 
def rsa_oaep_encrypt(message: bytes, e: int, n: int) -> int:
    """Complete RSA-OAEP encryption."""
    k = (n.bit_length() + 7) // 8  # Modulus byte length
    EM = oaep_encode(message, k)
    m = int.from_bytes(EM, byteorder='big')
    c = pow(m, e, n)
    return c
 
def rsa_oaep_decrypt(ciphertext: int, d: int, n: int) -> bytes:
    """Complete RSA-OAEP decryption."""
    k = (n.bit_length() + 7) // 8
    m = pow(ciphertext, d, n)
    EM = m.to_bytes(k, byteorder='big')
    message = oaep_decode(EM, k)
    return message
 
# Demonstration
if __name__ == "__main__":
    # Simulated 2048-bit RSA key (in practice, use proper key generation)
    from demo_rsa_key import generate_rsa_keypair
    
    # For this demo, use smaller key
    p, q = 0xd4bcd52406f2264b4587e6f8b43fa66d, 0xc3e7f82a9314db1b6a77298a1552f7e1
    n = p * q
    e = 65537
    d = pow(e, -1, (p-1)*(q-1))
    
    k = (n.bit_length() + 7) // 8
    max_message_len = k - 2 * 32 - 2  # SHA-256 has 32-byte digest
    
    print(f"RSA modulus: {n.bit_length()} bits ({k} bytes)")
    print(f"Maximum message length with SHA-256: {max_message_len} bytes")
    print()
    
    # Encrypt a message
    message = b"Secret AES key!"
    print(f"Original message: {message}")
    
    ciphertext = rsa_oaep_encrypt(message, e, n)
    print(f"OAEP ciphertext: {ciphertext}")
    
    decrypted = rsa_oaep_decrypt(ciphertext, d, n)
    print(f"Decrypted message: {decrypted}")
    
    assert decrypted == message, "Decryption failed!"
    print("\n✓ RSA-OAEP encryption/decryption successful!")

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130

"""
Hybrid Encryption: RSA + AES
 
This is how real systems (TLS, S/MIME, PGP) actually use RSA.
RSA encrypts a symmetric key; AES encrypts the data.
"""
 
import secrets
import hashlib
from cryptography.hazmat.primitives.ciphers.aead import AESGCM
 
# Assume we have RSA functions from previous examples
# from rsa_oaep import rsa_oaep_encrypt, rsa_oaep_decrypt
 
def hybrid_encrypt(plaintext: bytes, rsa_public_key: tuple) -> dict:
    """
    Hybrid encryption using RSA + AES-GCM.
    
    Args:
        plaintext: Data to encrypt (any size)
        rsa_public_key: (e, n) tuple
    
    Returns:
        Dictionary with encrypted_key, nonce, and ciphertext
    """
    e, n = rsa_public_key
    
    # Step 1: Generate random AES-256 key (32 bytes)
    aes_key = secrets.token_bytes(32)
    
    # Step 2: Encrypt data with AES-GCM
    nonce = secrets.token_bytes(12)  # 96-bit nonce for GCM
    aesgcm = AESGCM(aes_key)
    ciphertext = aesgcm.encrypt(nonce, plaintext, None)
    # GCM appends authentication tag to ciphertext
    
    # Step 3: Encrypt AES key with RSA-OAEP
    encrypted_key = rsa_oaep_encrypt(aes_key, e, n)
    
    return {
        'encrypted_key': encrypted_key,  # RSA-encrypted AES key
        'nonce': nonce,                    # AES-GCM nonce
        'ciphertext': ciphertext,          # AES-encrypted data + auth tag
    }
 
def hybrid_decrypt(encrypted_data: dict, rsa_private_key: tuple) -> bytes:
    """
    Hybrid decryption using RSA + AES-GCM.
    
    Args:
        encrypted_data: Dictionary from hybrid_encrypt
        rsa_private_key: (d, n) tuple
    
    Returns:
        Original plaintext
    """
    d, n = rsa_private_key
    
    # Step 1: Decrypt AES key with RSA-OAEP
    aes_key = rsa_oaep_decrypt(encrypted_data['encrypted_key'], d, n)
    
    # Step 2: Decrypt data with AES-GCM
    aesgcm = AESGCM(aes_key)
    plaintext = aesgcm.decrypt(
        encrypted_data['nonce'],
        encrypted_data['ciphertext'],
        None
    )
    
    return plaintext
 
# Demonstration
def demo_hybrid_encryption():
    """
    Demonstrate hybrid encryption with a 10MB file.
    
    RSA alone would require ~50,000 blocks and take minutes.
    Hybrid encryption takes milliseconds for any size data.
    """
    import time
    
    # Generate RSA key pair (use proper generation in practice)
    p, q = generate_large_primes()  # Assume this exists
    n = p * q
    e = 65537
    d = pow(e, -1, (p-1)*(q-1))
    
    public_key = (e, n)
    private_key = (d, n)
    
    # Generate a 10 MB random "file"
    large_data = secrets.token_bytes(10 * 1024 * 1024)  # 10 MB
    
    print(f"Encrypting {len(large_data):,} bytes of data...")
    
    start = time.time()
    encrypted = hybrid_encrypt(large_data, public_key)
    encrypt_time = time.time() - start
    
    print(f"Encryption took {encrypt_time:.3f} seconds")
    print(f"  RSA-encrypted key: {encrypted['encrypted_key']}")
    print(f"  Nonce: {encrypted['nonce'].hex()}")
    print(f"  Ciphertext length: {len(encrypted['ciphertext']):,} bytes")
    
    start = time.time()
    decrypted = hybrid_decrypt(encrypted, private_key)
    decrypt_time = time.time() - start
    
    print(f"Decryption took {decrypt_time:.3f} seconds")
    print(f"Decryption successful: {decrypted == large_data}")
 
# Performance comparison
def compare_rsa_vs_hybrid():
    """
    Compare encrypting 1000 bytes with pure RSA vs hybrid.
    """
    # RSA alone: Need 6 blocks of 190 bytes = 6 RSA operations
    # Each RSA encryption ~1ms = 6ms total
    
    # Hybrid: 1 RSA operation (32-byte key) + negligible AES time
    # Total: ~1ms
    
    print("\nPerformance comparison for 1KB data:")
    print("  Pure RSA (6 blocks): ~6ms")
    print("  Hybrid (RSA+AES): ~1ms")
    print("  Speedup: 6x")
    print("\nFor 10MB data:")
    print("  Pure RSA: ~50,000 blocks = ~50 seconds")
    print("  Hybrid: 1 RSA + ~10ms AES = ~11ms")
    print("  Speedup: ~4500x")