Choose two large random prime numbers p and q. Compute the public modulus: n = p × q Compute Carmichael's totient using LCM instead of Euler's φ: λ(n) = lcm(p−1, q−1) Choose public exponent e = 65537 (standard — prime, fast in binary). Compute private key d as the modular inverse of e: d × e ≡ 1 (mod λ(n)) ▸ Public key is (n, e). Private key is (n, d). p and q are discarded.

Convert plaintext to integer blocks m. Each block is prepended with 0xFF to prevent leading zero issues. Block size is k = ⌊(log₂(n) − 1) / 8⌋ bytes. c = m^e mod n The result c is the ciphertext — a large number written as hex. ▸ Anyone with the public key (n, e) can encrypt. Only the holder of d can decrypt.

Read each hex line of ciphertext as integer c. Apply the private key exponent d: m = c^d mod n This works because: m^(e×d) ≡ m (mod n) Strip the prepended 0xFF byte, write remaining bytes to output. ▸ This identity holds by Euler's theorem when gcd(m, n) = 1.

To sign a message m (e.g. the username), the key holder uses their private key: s = m^d mod n Anyone can verify the signature using the public key: s^e mod n == m ? This proves the message came from the holder of d without revealing d. ▸ Used in this program to authenticate the username embedded in the public key file.

To find large primes, candidate numbers are tested probabilistically. Write n−1 = 2^s × r where r is odd. Then for random a: y = a^r mod n If y ≠ 1 and y ≠ n−1, repeatedly square y up to s−1 times. If we never reach n−1, n is composite. ▸ Running 50 iterations gives error probability < 4⁻⁵⁰ ≈ 10⁻³⁰.