RSA

The extended Euclidean algorithm

Each row keeps r = x·φ(n) + y·e. Dividing the two previous remainders gives the quotient and the next row. When the remainder reaches 1, its y is an inverse of e modulo φ(n).

Whoever knows p and q can repeat this calculation, which is why the factors of n must stay secret in real RSA. Here they are on the page on purpose.

Square-and-multiply reads the exponent in binary from its last bit. The base is squared at every step and reduced modulo n; where the bit is 1 the result is multiplied by the current base. No number ever grows beyond n², and the power itself is never written out.

Decrypting an encrypted message computes (m^e)^d = m^ed, and the key was built so that ed ≡ 1 (mod φ(n)), that is, ed = 1 + k(p − 1)(q − 1) for some whole number k.

Modulo p. If p does not divide m, Fermat’s little theorem gives m^p−1 ≡ 1, so m^ed = m · (m^p−1)^k(q−1) ≡ m. If p does divide m, both sides are 0 modulo p. Either way m^ed ≡ m (mod p).

Modulo q. The same argument gives m^ed ≡ m (mod q).

Together. m^ed − m is divisible by both p and q, which are different primes, so it is divisible by pq = n (the Chinese remainder theorem). Hence m^ed ≡ m (mod n) for every 0 ≤ m < n, including the messages that share a factor with n. Try m = p.

• It is deterministic. There is no randomness, so equal messages always give equal ciphertexts, and anyone can encrypt a guess with the public key and compare.
• There is no padding. Modern RSA encryption first encodes the message with a randomized padding such as RSA-OAEP; textbook RSA exponentiates the bare number.
• It has algebraic structure. The product of two ciphertexts is the ciphertext of the product of their messages, E(a)·E(b) ≡ E(ab), which an attacker can exploit; and a small message with a small exponent may not even wrap around the modulus.
• These moduli are tiny. A modulus below 10¹² is factored at once, and its factors give d. Explore factoring this modulus in the Prime Factorization calculator: enter n = —.

Larger primes fix only the last point. Unpadded RSA stays insecure at any size; the RSA-OAEP view shows the padded scheme that is actually used.

Randomized encryption normally produces different ciphertexts for the same message. Before the RSA operation, OAEP mixes the message with fresh random bytes, so each encryption exponentiates a different number. Every one of those ciphertexts decrypts to the same message with the matching private key. Use Encrypt again to see it.

Textbook RSA has no such step: in the RSA Mathematics view, the same m always gives the same c = m^e mod n, which lets an eavesdropper recognize repeated messages and test guesses.

1. The message bytes are padded to the length of the modulus, together with a hash of an (empty) label.
2. A random seed is drawn. A mask derived from the seed with SHA-256 (the function MGF1) is combined with the padded message, and a mask derived from the result is combined with the seed.
3. The encoded block is read as one integer M < n and only then exponentiated: c = M^e mod n, with e = 65537.
4. Decryption computes c^d mod n, undoes the masks and checks the padding; if anything is wrong it reports failure without saying what.

So the number that is exponentiated is the randomized encoding, not the message read as an integer: an OAEP ciphertext is not m^e mod n of your text. All of this, and the generation of the primes, is done by the browser (crypto.subtle); this page implements none of it.

maximum bytes = k − 2·hLen − 2  ·  2048 bits: 256 − 64 − 2 = 190  ·  3072 bits: 384 − 64 − 2 = 318

Here k is the length of the modulus in bytes and hLen = 32 for SHA-256. The limit counts UTF-8 bytes, not characters: é takes 2 bytes, most emoji 4. A ciphertext is always exactly k bytes.

RSA-OAEP is designed to encrypt small payloads. Larger messages are normally encrypted using a hybrid system combining public-key cryptography with symmetric encryption. This page does not split a long message into several RSA blocks.

• RSA Mathematics is deliberately insecure; RSA-OAEP uses the browser’s native cryptographic operations.
• The private key is non-extractable and lasts only for this page session. Reloading the page loses it, and with it the ability to decrypt earlier ciphertexts. Generating a new pair replaces the old one.
• Nothing is stored or sent: no key, message or ciphertext goes into the address, into browser storage or to a server.
• An exported public key can be shared freely. This page does not verify who owns an imported public key, and the fingerprint shown is only a label for telling keys apart.
• A compromised browser, extension or website can undermine confidentiality whatever the mathematics.
• This is a learning tool, not a complete secure messaging protocol: it has no authentication, no key management and no protection against replayed or forged ciphertexts.

RSA is also used for digital signatures, but with a different scheme: RSA-OAEP is for encryption and RSA-PSS for signatures, and one must not be used for the other. Signatures belong to the Digital Signatures calculator Coming soon.