[Verse 1]
Two primes walking into the spotlight, massive digits gleaming
P and Q, the secret architects of cryptographic dreaming
Multiply these titans, birth an N that towers high
Public modulus standing guard while private factors hide
Check they're coprime, relatively speaking, no shared divisors lurking
Euler's totient function calculates the playground where we're working
Phi of N equals P minus one times Q minus one
Foundation mathematics before the real encryption's begun
[Chorus]
Pick your primes, multiply, get your N so high
Choose an E that's coprime, public key will fly
Calculate the inverse, D must satisfy
E times D mod phi equals one, decryption amplified
RSA generation, mathematical equation
Prime factorization's the key to our salvation
[Verse 2]
Choose exponent E, convention says sixty-five thirty-seven
Small and coprime to our phi, computational heaven
Extended Euclidean algorithm sweats to find the D
Modular multiplicative inverse, private key that holds the fee
Three values dance together, N and E go public facing
While D stays locked in vaults, never caught embracing
Encryption takes your message, raises it to power E
Modulo N completes the spell, ciphertext runs free
[Chorus]
Pick your primes, multiply, get your N so high
Choose an E that's coprime, public key will fly
Calculate the inverse, D must satisfy
E times D mod phi equals one, decryption amplified
RSA generation, mathematical equation
Prime factorization's the key to our salvation
[Bridge]
Miller-Rabin tests those candidates, pseudoprimes get caught
Probabilistic algorithms sift through what time has brought
Bit length determines strength, one-oh-two-four minimum
Two-oh-four-eight recommended when adversaries come
Key pair spawned from entropy, randomness supreme
Cryptographic handshake born from number theory's dream
[Outro]
Generate those primes with care, security depends
On mathematical foundations where factorization ends
Public N, public E, but D you never share
RSA's elegant armor built from computational prayer