← Back to practices Practice 11 · Handcrafted

RSA with CRT

Generate schoolbook RSA keys, encrypt integers and decrypt with the Chinese remainder theorem, showing every intermediate value. Selected Topics in Cryptography Lab 06.

Schoolbook RSA with Handcrafted C17 arithmetic. OpenSSL only generates the primes p and q; e, d, dp, dq, encryption and CRT decryption are computed by hand. Square and Multiply (Algorithm 1) computes every modular power.

1. Key pair generation

|p| = |q| · n = pq · e random, gcd(e, φ(n)) = 1 · d = e⁻¹ mod φ(n)
dp = d mod (p − 1) · dq = d mod (q − 1)

Bits per prime (4 to 1024)

2. Encryption

c = m^e mod n · 0 < m < n

Message men

3. CRT decryption

0 < c < n · n = pq · dp = d mod (p − 1) · dq = d mod (q − 1)

Ciphertext c

Educational practice: unpadded RSA and variable-time arithmetic. Calculations stay in this browser; do not use these keys to protect real data.