[Verse 1]
Started with two primes, secret and discrete
Call them p and q, foundation concrete
Multiply together, get the modulus n
This becomes the key that locks data in
Random number picking, cryptographic grade
Hundreds digits long, security's blade
Euler's totient function, phi of n we seek
P minus one times q minus one, technique
[Chorus]
Pick your primes, multiply them clean
Choose your e, make it coprime
Extended algorithm finds the d
RSA generation, mathematically
Public key broadcasts, private stays inside
Modular arithmetic where secrets hide
Factor the product, crack the design
But with large primes, you're running out of time
[Verse 2]
Public exponent e, commonly sixty-five-five-three-seven
Small and efficient, binary heaven
Greatest common divisor with phi must be one
Coprimality check before we're done
Extended Euclidean runs the inverse dance
Finding private d through mathematical chance
Modular arithmetic keeps numbers bound
Integer solutions can always be found
[Chorus]
Pick your primes, multiply them clean
Choose your e, make it coprime
Extended algorithm finds the d
RSA generation, mathematically
Public key broadcasts, private stays inside
Modular arithmetic where secrets hide
Factor the product, crack the design
But with large primes, you're running out of time
[Bridge]
Key pair complete, asymmetric might
Public encrypts, private decrypts right
Digital signatures flip the game around
Private signs messages, public validates sound
[Outro]
Prime generation, Miller-Rabin test
Probabilistic proof puts strength to rest
Thousand-bit minimum, security grade
RSA foundation, mathematically made