4 more

NUMBER THEORYExploratoryMathematics Calculator

🔐

RSA Cryptography — Public-Key Encryption

Rivest–Shamir–Adleman (1977). n = pq, φ(n) = (p−1)(q−1). Encrypt: c ≡ m^e mod n. Decrypt: m ≡ c^d mod n where ed ≡ 1 mod φ(n).

Concept Fundamentals

(p−1)(q−1)

φ(n)

public

private

Encrypt & DecryptModular Exponentiation

Why This Mathematical Concept Matters

Why: RSA security relies on difficulty of factoring n = pq. Public key (n,e), private key d. Only d (from φ(n)) can decrypt. Used in TLS, SSH, PGP.

How: Choose primes p,q. n = pq, φ = (p−1)(q−1). Pick e coprime to φ. Find d: ed ≡ 1 mod φ. Encrypt: c = m^e mod n. Decrypt: m = c^d mod n = m^(ed) ≡ m mod n.

●Euler's theorem: m^φ(n) ≡ 1 mod n when gcd(m,n)=1.
●ed ≡ 1 mod φ(n) ensures m^(ed) ≡ m mod n.
●Factoring n is believed computationally hard; that's the security.

Sources:RSA (cryptosystem)Euler's Theorem

🔐

CRYPTOGRAPHYSecurity & Encryption

RSA Calculator — Public-Key Cryptography

Generate keys, encrypt, decrypt. Euler's theorem, modular exponentiation. Understand the math behind HTTPS, SSH, PGP.

Modular Arithmetic →

Sample Examples

Small Primes Example

Simple example using small prime numbers p=3, q=11

p=3, q=11, e=7, message=5

Secure Message Example

Example with medium-sized primes for more secure encryption

p=17, q=23, e=3, message=123

Decryption Demo

Example starting with an encrypted message that needs decryption

p=5, q=11, e=3, encrypted=14

RSA Key Generation

Understanding Prime Numbers in RSA

RSA begins with two distinct prime numbers. The security of RSA relies on the difficulty of factoring the product of these two primes. In practice, these primes would be very large (hundreds of digits), but for educational purposes, we'll use smaller values.

Prime Number pEnter a prime number (e.g., 3, 5, 7, 11). This will be one of the two primes used to generate the RSA key pair.

A prime number is a natural number greater than 1 that is not a product of two smaller natural numbers. For example, 3 is prime because its only factors are 1 and 3.

Prime Number qEnter a prime number different from p. The product of p and q (n = p×q) will be part of both public and private keys.

Choose a different prime number than p. The security of RSA depends on keeping the individual prime factors (p and q) private while publishing their product (n).

Public Exponent eMust be coprime to (p-1)(q-1), meaning they share no common factors except 1.

The public exponent is part of your public key. Common values are 3, 5, 17, or 65537 (2¹⁶+1). It must be coprime with λ(n), which means their greatest common divisor (GCD) must be 1.

Generated Keys

Below are your RSA key pair. The public key is shared openly, while the private key must be kept secret.

Public Key (e, n):

(7, 33)

This key is used for encryption and can be freely distributed.

Private Key (d, n):

(3, 33)

This key is used for decryption and must be kept secret.

Encryption/Decryption

Using Your RSA Keys

To encrypt a message, you use the recipient's public key. To decrypt a message, you use your private key. In this calculator, we're working with numerical values only, but in practice, messages would be converted to numbers using various encoding schemes before encryption.

Message (Plain Text)Enter a numerical message to encrypt. This must be less than n (which is {results ? results.n : 'calculated from p and q'}).

In RSA, messages must be represented as numbers. For actual text messages, each character would be converted to its numerical equivalent before encryption. The message value must be less than n for RSA to work properly.

Results

rsa.sh

KEYS GENERATED

$ rsa_generate --p=3 --q=11 --e=7

Public (e,n)

(7, 33)

Private (d,n)

(3, 33)

Encrypted

Decrypted

RSA Calculator

n = 33 • d = 3

C = 14

numbervibe.com/calculators/mathematics/exploratory/rsa-calculator

Understanding Your RSA Results

The calculations below show how your keys were generated and how they're used for encryption or decryption. RSA's security comes from the mathematical relationship between the public and private keys, which are linked through modular arithmetic.

Key Generation Result

Public Key (e, n)

(7, 33)

This is your public key pair. The value 'e' is the encryption exponent, and 'n' is the modulus (product of primes p and q). You can freely share this with anyone who wants to send you encrypted messages.

Private Key (d, n)

(3, 33)

This is your private key pair. The value 'd' is the decryption exponent, calculated as the modular multiplicative inverse of e modulo λ(n). Keep this secret, as it allows you to decrypt messages encrypted with your public key.

Modulus n

The modulus n = p × q = 3 × 11 = 33. This value is part of both your public and private keys, but the individual prime factors (p and q) must remain secret.

Carmichael's Function λ(n)

λ(n) = lcm(p-1, q-1) = lcm(2, 10) = 10. This value is used to calculate the private key 'd' and must remain secret.

Encryption Result

Input Message (M)

This is your original plaintext message represented as a number. In practical RSA implementations, text messages are converted to numerical values using encoding schemes.

Encrypted Message (C)

C = M^e mod n = 5^7 mod 33 = 14. This is the ciphertext that can only be decrypted with the private key.

Security Note: The encrypted message can only be decrypted using the private key (d, n). Even if someone knows the public key and the encrypted message, they cannot feasibly recover the original message without the private key due to the mathematical difficulty of factoring large numbers.

Step-by-Step Explanation

Understanding the RSA Algorithm Steps

The following steps show exactly how RSA encryption and decryption work, from key generation to message processing. Each step includes the mathematical operation and its meaning in the context of cryptography.

Key Generation Steps

The RSA algorithm requires two prime numbers to generate the public and private keys:

Historical Note: RSA was invented in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman (hence the name "RSA") at MIT. It was one of the first practical public-key cryptosystems and is widely used for secure data transmission.

We have chosen two prime numbers: p = 3 and q = 11

Step 1: Calculate n = p × q

n = 3 \times 11 = 33

Security Insight: The modulus n is public knowledge, but factoring n into its prime components (p and q) is computationally infeasible for very large numbers, which is the basis of RSA's security.

Step 2: Calculate λ(n), which is the Carmichael's function

\lambda(n) = \text{lcm}(p-1, q-1) = \text{lcm}(2, 10) = 10

Mathematical Note: Carmichael's function λ(n) gives the smallest positive integer m such that a^m ≡ 1 (mod n) for all a coprime to n. For a product of two primes, it equals the least common multiple (LCM) of (p-1) and (q-1).

Step 3: Choose e = 7, which is coprime to λ(n) = 10

\gcd(e, \lambda(n)) = \gcd(7, 10) = 1

Practical Consideration: In real-world applications, e is often chosen as 65537 (2^16 + 1), which is large enough to be secure and has a convenient binary representation that makes encryption efficient.

Step 4: Calculate the private exponent d, which is the modular multiplicative inverse of e modulo λ(n)

d = e^{-1} \bmod \lambda(n) = 7^{-1} \bmod 10 = 3

Computational Note: The private exponent d is calculated using the Extended Euclidean Algorithm, which efficiently finds the modular multiplicative inverse of e modulo λ(n).

Step 5: The public key is (e, n) and the private key is (d, n)

\text{Public Key} = (7, 33) \quad \text{Private Key} = (3, 33)

Encryption Steps

Encrypting a message using the public key (e, n):

Message (M) = 5

The encryption formula is C = M^e mod n, where C is the ciphertext

C = M^e \bmod n = 5^{7} \bmod 33

Performance Note: For large exponents, direct computation of M^e would result in enormous numbers. The square-and-multiply algorithm efficiently computes modular exponentiation without generating these large intermediate values.

Computing this using the square and multiply algorithm:

Initial: 5^1 mod 33 = 5

Square: 5^2 mod 33 = 25

Square: 5^4 mod 33 = 31

Multiply with 5^3 mod 33 = 26

Final: 31 × 26 mod 33 = 14

Therefore, the encrypted message (ciphertext) is:

C = 14

⚠️For educational and informational purposes only. Verify with a qualified professional.

🧮 Fascinating Math Facts

🔐

RSA (1977): n = pq public, d private. Security = hardness of factoring

— Cryptography

📐

Euler: m^φ(n) ≡ 1 mod n. RSA uses m^(ed) ≡ m when ed ≡ 1 mod φ(n)

— Number Theory

What is the RSA Algorithm?

The RSA algorithm is an asymmetric cryptography protocol used to securely transmit data between parties. It uses a pair of keys: a public key for encryption, and a private key for decryption. Named after its inventors (Rivest, Shamir, and Adleman), RSA remains one of the most widely used cryptographic algorithms since its development in 1977.

Mathematical Principles

Euler's Theorem

For any coprime integers a and n:

a^{\phi(n)} \equiv 1 \pmod{n}

Where φ(n) is Euler's totient function, counting the positive integers up to n that are coprime to n.

RSA Key Generation

Choose primes p and q, then compute:

n = p \times q

Calculate Carmichael's totient function:

\lambda(n) = \text{lcm}(p-1, q-1)

Choose e (public exponent) such that:

1 < e < \lambda(n) \text{ and } \gcd(e, \lambda(n)) = 1

Calculate d (private exponent):

d \equiv e^{-1} \pmod{\lambda(n)}

Encryption and Decryption

Encryption of message M to ciphertext C:

C \equiv M^e \pmod{n}

Decryption of ciphertext C to message M:

M \equiv C^d \pmod{n}

The key property that makes RSA work:

(M^e)^d \equiv M^{ed} \equiv M \pmod{n}

This works because:

ed \equiv 1 \pmod{\lambda(n)}

Interactive Key Generation

Watch how RSA keys are generated step-by-step with this interactive visualization:

RSA Key Generation Visualization

Prime p

Prime q

Modulus n = p × q

\lambda(n) = \text{lcm}(p-1, q-1) = \text{lcm}(2, 10) = 20

Carmichael's totient function

This value is kept private and used to calculate the private key.

Choose e such that 1 < e < λ(n) and gcd(e, λ(n)) = 1

Public exponent e

This will be part of your public key (e, n)

d \cdot e \equiv 1 \pmod{\lambda(n)}

Private exponent d

This will be part of your private key (d, n)

Public Key

(e, n) = (7, 33)

Share publicly

Private Key

(d, n) = (••••, ••••)

Keep secret

The public key is used for encryption, while the private key is used for decryption.

Step 1: Start with two prime numbers p and q

Interactive Encryption and Decryption

See how messages are encrypted and decrypted using RSA keys:

RSA Encryption/Decryption Visualization

Enter a message (0-32):

Message must be less than the modulus n = 33

Alice (Sender)

Original Message

Using Bob's Public Key

(e, n) = (7, 33)

Bob (Recipient)

Bob's Private Key

(d, n) = (•••, •••)

Decrypted Message

Encryption Formula

C = M^e \bmod n = 5^7 \bmod 33

Decryption Formula

M = C^d \bmod n = C^? \bmod 33

Encrypted Message

...

This ciphertext can be safely transmitted over insecure channels

Enter a message and click 'Encrypt' to begin the RSA encryption process.

The Security of RSA: Try to Break It!

RSA's security is based on the difficulty of factoring large numbers. Try this interactive challenge:

The Security of RSA: Factoring Challenge

RSA security relies on the difficulty of factoring large numbers. Try to find the two prime numbers (p and q) that multiply to give n:

697

Modulus n = 697 (10 bits)

Estimated real-world factoring time: Almost instant

Find the prime factors:

Prime p:

Prime q:

Why This Matters for RSA Security:

Key Size: 10 bits (Toy example only, extremely insecure)

Factoring Challenge: Far smaller than any real-world application

The Security Principle: While multiplying two prime numbers is easy, factoring their product becomes exponentially harder as the numbers increase in size.

Quantum Threat: Quantum computers using Shor's algorithm could theoretically break RSA encryption by efficiently factoring large numbers, but practical quantum computers capable of this don't exist yet.

Mathematical Foundation

RSA's security is based on the mathematical difficulty of factoring large composite numbers into their prime factors. While multiplying two large primes is computationally easy, finding the prime factors of their product is extremely difficult with current technology.

Security Strength

RSA security depends on key size. Modern implementations use 2048 or 4096-bit keys. For educational purposes, this calculator uses small primes to make the calculations comprehensible, but in practice, much larger primes are necessary.

Key Components of RSA

Key Generation

Select two large prime numbers p and q
Compute n = p × q
Calculate λ(n) = lcm(p-1, q-1)
Choose e coprime to λ(n)
Compute d such that d·e ≡ 1 (mod λ(n))

Encryption

Public key: (e, n)
Message: M (must be less than n)
Encryption formula: C = M^e mod n
Encrypted message: C

Decryption

Private key: (d, n)
Encrypted message: C
Decryption formula: M = C^d mod n
Original message: M

Applications of RSA

Secure Communications

Email encryption (PGP, S/MIME)
Secure browsing (HTTPS/TLS)
Secure shell (SSH) connections
Virtual private networks (VPNs)

Digital Signatures

Document verification
Software authenticity
Certificate authorities
Secure electronic transactions

Limitations and Considerations

Security Considerations

Key Size: Modern RSA implementations use at least 2048-bit keys for adequate security. This calculator uses small numbers for educational purposes.
Performance: RSA is computationally intensive and slower than symmetric encryption methods, especially for large data sets.
Quantum Computing: Quantum computers could theoretically break RSA encryption using Shor's algorithm, which efficiently factors large numbers.
Implementation: Proper implementation is critical; vulnerabilities often arise from implementation errors rather than the algorithm itself.

Frequently Asked Questions

Why is RSA considered secure?

RSA security is based on the computational difficulty of factoring large numbers. While multiplying two prime numbers is easy, finding which two specific primes were multiplied to get a large number is computationally infeasible with current technology.

n = p \times q \quad \text{is easy, but} \quad p, q = \text{?} \quad \text{given only } n \text{ is hard}

What is asymmetric encryption?

Asymmetric encryption uses a pair of related keys: a public key for encryption and a private key for decryption. Anyone can encrypt a message using the recipient's public key, but only the recipient with the matching private key can decrypt it. This differs from symmetric encryption, which uses the same key for both encryption and decryption.

\begin{align} \text{Encrypt: } & C = E_{pub}(M) \\ \text{Decrypt: } & M = D_{priv}(C) \end{align}

Is RSA still used today?

Yes, RSA remains widely used in modern cryptography, especially for secure communications and digital signatures. However, it's often used in combination with symmetric encryption algorithms for better performance, with RSA encrypting a symmetric key that then encrypts the actual data.

How does RSA compare to other encryption algorithms?

RSA is computationally intensive compared to symmetric algorithms like AES. It's typically used to securely exchange symmetric keys, which are then used for bulk data encryption. Elliptic Curve Cryptography (ECC) offers similar security with smaller key sizes, making it more efficient for some applications.

\begin{array}{|c|c|c|} \hline \text{RSA Key Size} & \text{ECC Key Size} & \text{Security Level} \\ \hline \text{1024 bits} & \text{160 bits} & \text{80 bits} \\ \text{2048 bits} & \text{224 bits} & \text{112 bits} \\ \text{3072 bits} & \text{256 bits} & \text{128 bits} \\ \text{7680 bits} & \text{384 bits} & \text{192 bits} \\ \text{15360 bits} & \text{521 bits} & \text{256 bits} \\ \hline \end{array}

Historical Context

RSA was publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT. Its development represented a solution to the key distribution problem in cryptography, allowing secure communication without a pre-shared secret key. It was one of the first practical public-key cryptosystems and revolutionized the field of cryptography.

Interestingly, a similar system was developed earlier in 1973 by Clifford Cocks, a British mathematician working for the UK intelligence agency GCHQ, but it remained classified until 1997.

RSA Key Size Evolution

As computing power increases, RSA key sizes must grow to maintain security. This timeline shows the evolution of recommended minimum key sizes:

\begin{array}{|c|c|} \hline \text{Year} & \text{Recommended Minimum RSA Key Size} \\ \hline 1977 & 300-400 \text{ bits} \\ 1990 & 512 \text{ bits} \\ 2000 & 1024 \text{ bits} \\ 2010 & 2048 \text{ bits} \\ 2020 & 3072 \text{ bits} \\ \hline \end{array}

Factoring Progress

The security of RSA depends on the difficulty of factoring large numbers. This shows the largest numbers factored over time:

\begin{align} 1977 & : 45 \text{ digits} \\ 1994 & : \text{RSA-129 (129 digits)} \\ 2009 & : \text{RSA-768 (232 digits)} \\ 2020 & : \text{RSA-250 (250 digits)} \\ \end{align}

Today's recommended 2048-bit RSA keys (about 617 digits) remain well beyond current factoring capabilities.

👈 START HERE

⬅️Jump in and explore the concept!

RSA Cryptography — Public-Key Encryption

Why This Mathematical Concept Matters

RSA Calculator — Public-Key Cryptography

Sample Examples

Small Primes Example

Secure Message Example

Decryption Demo

RSA Key Generation

Understanding Prime Numbers in RSA

Generated Keys

Encryption/Decryption

Using Your RSA Keys

Results

Understanding Your RSA Results

Key Generation Result

Encryption Result

Step-by-Step Explanation

Understanding the RSA Algorithm Steps

Key Generation Steps

Encryption Steps

🧮 Fascinating Math Facts

What is the RSA Algorithm?

Mathematical Principles

Euler's Theorem

RSA Key Generation

Encryption and Decryption

Interactive Key Generation

RSA Key Generation Visualization

Public Key

Private Key

Interactive Encryption and Decryption

RSA Encryption/Decryption Visualization

Alice (Sender)

Bob (Recipient)

The Security of RSA: Try to Break It!

The Security of RSA: Factoring Challenge

Find the prime factors:

Why This Matters for RSA Security:

Mathematical Foundation

Security Strength

Key Components of RSA

Key Generation

Encryption

Decryption

Applications of RSA

Secure Communications

Digital Signatures

Limitations and Considerations

Security Considerations

Frequently Asked Questions

Why is RSA considered secure?

What is asymmetric encryption?

Is RSA still used today?

How does RSA compare to other encryption algorithms?

Historical Context

RSA Key Size Evolution

Factoring Progress

We Value Your Privacy