RSA
Asymmetric scheme based on the difficulty of factoring large integers.
How it works
- RSA keys are generated by choosing two large prime numbers p and q, then computing n = p×q and φ(n) = (p−1)(q−1).
- A public exponent e is chosen so that it is coprime to φ(n). The private exponent d is computed so that e×d ≡ 1 (mod φ(n)).
- The public key is (e, n) and can be shared freely. The private key is (d, n) and must be kept secret.
- To encrypt a small number m (representing data), compute c = m^e mod n. To decrypt, compute m = c^d mod n.
- In practice RSA is mainly used to encrypt symmetric keys or to create digital signatures, not to encrypt long messages directly.
Keys are generated automatically for this demonstration.
What is it?
RSA (Rivest–Shamir–Adleman) is a foundational public-key cryptosystem that revolutionized modern communications. Invented in 1977, it allows for secure data transmission without the need to secretly share a key beforehand. RSA relies on the practical difficulty of factoring the product of two extremely large prime numbers. In an RSA system, the public key is shared openly for anyone to encrypt messages, but only the holder of the private key (which contains the prime factors) can decrypt them. It remains heavily used today for digital signatures and key exchanges.
Try it yourself
Can you decrypt this challenge?
Where this shows up today
To solve the fundamental problem of securely distributing cryptographic keys over an insecure network.