Modern encryption relies on the fact that some math problems are easy to do but hard to undo. One of the most famous examples is RSA encryption, which is built on the mathematics of prime numbers and modular exponentiation.
At its core, encryption is the process of converting readable information, called "plaintext," into an unreadable format known as "ciphertext" to protect it from unauthorized access. Think of it as putting your data in a locked box that can only be opened with the right key. This transformation uses mathematical algorithms combined with secret keys to scramble data in a way that makes it meaningless to anyone who doesn't possess the corresponding decryption key.
The fundamental principle behind modern cryptographic systems is mathematical asymmetry - certain mathematical operations are computationally easy to perform in one direction but extremely difficult to reverse without additional information. For instance, multiplying two large prime numbers together is straightforward, but factoring the resulting product back into its original prime components becomes practically impossible as the numbers grow larger. This mathematical one-way property forms the foundation of cryptographic security.
There are two primary approaches to encryption. Symmetric encryption uses the same key for both encrypting and decrypting data. While this method is fast and efficient - making it ideal for encrypting large amounts of data - it presents the challenge of securely sharing the secret key between communicating parties. Common symmetric algorithms include the Advanced Encryption Standard (AES), which secures everything from your Wi-Fi connection to government communications.
Asymmetric encryption, on the other hand, employs a mathematically related pair of keys: a public key that can be freely shared and a private key that must be kept secret. Data encrypted with the public key can only be decrypted with the corresponding private key, and vice versa. This elegant solution resolves the key distribution problem inherent in symmetric systems, though it operates more slowly and is typically used for smaller amounts of data or for securely exchanging symmetric keys.
Encryption has become the invisible foundation of our digital world. It protects your online banking transactions, secures your messaging applications, safeguards stored passwords, and enables secure web browsing - that familiar "https" in web addresses indicates that encryption is protecting your connection. Without these mathematical safeguards, digital communication and commerce as we know them would be impossible, leaving sensitive information vulnerable to interception and theft by malicious actors.
A prime number is a number greater than 1 that has no positive divisors other than 1 and itself.
Examples: \[ 2, 3, 5, 7, 11, 13, 17, 19, 23, \ldots \]
Composite numbers are numbers that have more than two factors (e.g., 4, 6, 8, 9, 10...).
When you multiply two large prime numbers together, the result is easy to compute. But doing the reverse - factoring that large number back into primes - is extremely difficult. This "one-way" nature is what makes RSA encryption secure.
RSA uses three key ideas:
The public key is \( (e, n) \). The private key is \( (d, n) \).
Let's encrypt the message "I LOVE YOU" using small primes for clarity.
Let's pick: \[ p = 17, \quad q = 11 \] Then: \[ n = p \cdot q = 187 \] \[ \phi(n) = (p - 1)(q - 1) = 16 \cdot 10 = 160 \]
We choose \( e = 7 \), which satisfies: \[ 1 < e < \phi(n), \quad \gcd(e, \phi(n)) = 1 \]
We find \( d \) such that: \[ e \cdot d \equiv 1 \mod \phi(n) \Rightarrow 7 \cdot d \equiv 1 \mod 160 \] Two possible methods to find \( d \):
1) Trial and Error (for small numbers)
2) Using the extended Euclidean algorithm method.
We need to find \( d \) suchn that \[ 7 \cdot d \equiv 1 \mod 160 \quad (I) \] We also know (from above ) that \[ \gcd(7, 160) = 1 \] We can therefore write equation (I) as \[ 7 \cdot d \equiv \gcd(7, 160) \mod 160 \quad (II) \] which equivalent to finding
\( d \) and \( k \) such that \[ 7 \cdot d + 160 k = \gcd(7, 160) \quad (III) \]
Step 1: Apply the Euclidean algorithm to find gcd(7, 160)
Divide 160 by 7 and write: \[ 160 = 7 \times 22 + 6 \]
Divide the last quotient 7 by the last remainder 6 and write: \[ 7 = 6 \times 1 + 1 \]
Divide the last quotient 6 by the last remainder 1 and write: \[ 6 = 1 \times 6 + 0 \]
The remainder is zero, we therefore stop.
Step 2: Work backwards to express \( 1 \) as a linear combination using the equations \( 7 = 6 \times 1 + 1 \) and \( 160 = 7 \times 22 + 6 \) found above:
Step 3: Extract the result
From \(7 \times 23 - 160 \times 1 = 1 \), we can see that:
\( 7 \times 23 = 1 (mod 160) \)
Therefore, \[ d = 23 \].
We use a simple letter-to-number conversion:
A = 01, B = 02, ..., Z = 26, space = 00
Message: "I LOVE YOU" becomes: \[ 09,\ 00,\ 12,\ 15,\ 22,\ 05,\ 00,\ 25,\ 15,\ 21 \]
Encrypt each number \( M \) using: \[ C = M^e \mod n \] With \( e = 7 \) and \( n = 187 \)
Encrypted values (using modular exponentiation):
Encrypted message: \[ [84, 0, 95, 137, 47, 106, 0, 116, 137, 154] \]
To decrypt, use: \[ M = C^d \mod n \quad \text{(with } d = 23,\ n = 187\text{)} \]
In RSA, encryption is: \[ C = M^e \mod n \]
Decryption is: \[ M = C^d \mod n \] So: \[ M = (M^e)^d \mod n = M^{ed} \mod n \]
If we set up \( e \cdot d \equiv 1 \mod \phi(n) \), Euler's theorem guarantees that this equation brings us back to the original message: \[ M^{ed} \equiv M \mod n \]
This is what makes RSA work: raising to the power \( e \) encrypts, and raising to power \( d \) decrypts - because of the math of modular exponentiation and number theory.
Even if someone knows \( n = 187 \) and \( e = 7 \), they can't easily decrypt the message without knowing \( d \). To find \( d \), they'd have to factor 187 into \( 17 \cdot 11 \), then compute \( \phi(n) \) and solve for \( d \). That's easy here - but for a 2048-bit key, it would take billions of years.
Enter your message (supports letters, numbers, and special characters) and RSA parameters:
Enter the encrypted numbers (comma-separated) and RSA parameters:
These questions use small numbers for educational clarity. Real RSA implementations use much larger primes (1024-4096 bits) corresponding to decimals in the range 309 to 124 digits and additional security measures to prevent various attacks.
To check if 29 is prime, we need to test divisibility by all primes up to \(\sqrt{29} \approx 5.4\).
Testing divisors: 2, 3, 5
Testing divisors: 2, 3, 5, 7 (since \(\sqrt{91} \approx 9.5\))
Since \(91 = 7 \times 13\),
We need to find \(d\) such that:
\[7 \cdot d \equiv 1 \pmod{120}\]First, verify that \(\gcd(7, 120) = 1\):
So \(\gcd(7, 120) = 1\) ?
This gives us: \(7 \times (-17) + 120 \times 1 = 1\)
Therefore: \(7 \times (-17) \equiv 1 \pmod{120}\)
Since \(-17 < 0\), we add 120: \(d = -17 + 120 = 103\)
Where:
Computing \(4^7\):
Where:
This is a large computation, so we'll use modular exponentiation by repeated squaring:
\[82^{103} = 82^{(64+32+4+2+1)} = 82^{64} \times 82^{32} \times 82^4 \times 82^2 \times 82^1\]Computing powers of 82 mod 143:
Therefore:
\[82^{103} \equiv 9 \times 3 \times 9 \times 3 \times 82 \equiv 81 \times 9 \times 82 \equiv 729 \times 82 \pmod{143}\]Simplifying:
The RSA encryption/decryption process successfully worked:
The message was successfully recovered, confirming our RSA implementation is correct.