How Useless Numbers Keep Your Data Safe

Imagine being told that the same useless numbers which you consistently label as redundant in the real world are in fact key to keeping your data safe from prying eyes. Every time someone sends a message, numbers keep your information safe and hidden so only the receiver can see it. At the heart of this is the RSA algorithm which uses prime numbers as its foundation.

The RSA algorithm is a widely used public-key cryptosystem for secure data transmission. It is named after its inventors: Rivest, Shamir, and Adleman. It transforms seemingly mundane and boring numbers into an impenetrable shield around your data, making them a key part of cryptography. How does the RSA algorithm work?

The RSA algorithm is based on two keys: a public key which is used for encryption which everyone can see, and a private key, used for decryption which is only known by the receiver. Let’s say Jack wants to send a message to James. Jack uses James’ public key to encrypt his message. This public key is available for everyone to see. However, the only way that the original message can be retrieved is by using James’ private key, something only he knows and uses when he receives the encrypted message. Without the private key, even if the message is intercepted it cannot be deciphered and the information is useless.

The maths behind RSA

So how are numbers actually used in encryption? Let’s take a look at an example.

Encryption

First we generate two prime numbers, let’s say p and q. We set them to be 5 and 11 respectively. Multiply p and q to get n, e.g., the first part of the public key: \[pq = n = 11\times5 = 55\] Then, calculate the totient of n. \[ϕ(n) = (p − 1)(q − 1) = (5 − 1)(11 − 1) = 4\times10 = 40\]
We calculate the encryption exponent e. The value of e has to be bigger than 1, but smaller than the totient and the greatest common divisor (gcd) of e and the totient is 1, so e and ϕ(n) are co-prime. In other words, we choose e such that:
\[1 < e < ϕ(n)\]\[gcd[e, ϕ(n)] = 1\]
A suitable choice for e here would be 7 as it is co-prime to 40. We get the public key (55,7). This is available for everyone to see. Next you have to calculate the private key d such that:
\[e\times d ≡ 1 (mod~ ϕ(n))\]
To solve d, we use the Euclidean algorithm. Use the following equation, where a is initially ϕ(n) and b is initially e. \[a = b\times c + r\] Make c as large as possible while still maintaining a non-negative value for r. Replace a and b with b and r respectively after each usage of the equation, and repeat. Since e and the ϕ(n) are co-prime, the last non-zero remainder will always reduce to 1. Then, you perform backwards substitution starting from the number 1. Eventually you will get 1 in terms of e and ϕ(n) in the form: \[1 = k\times ϕ(n) + k'\times e\] Now k′ is equal to the private key. If it is negative simply add ϕ(n) to it. Hence, in this case, performing the algorithm as follows.
(a) Perform the Euclidean algorithm:
\[40 = 7\times5 + 5\]\[7 = 5\times1 + 2\]\[5 = 2\times2 + 1\]\[2 = 1\times2 + 0\]
The last non-zero remainder is 1, which proves that gcd(7, 40) = 1.
(b) Work backwards to express 1 in terms of 7 and 40:
\[1 = 5 − 2\times 2\]
Substitute 2 = 7 − 5:
\[1 = 5 − 2(7 − 5) = 5 − 2\times7+2\times5 = 3\times5 − 2\times7\]
Substitute 5 = 40 − 7 × 5:
\[1 = 3(40 − 7\times5) − 2\times7 = 3\times40 − 17\times7\]
So we have:
\[1 = 3 \times40 − 17\times7\]
This means that: \(-17 \times 7 \equiv 1 \pmod{40}\) Therefore, d = −17. Since d = −17 is negative, we add 40 to make it positive:
\[d = −17 + 40 = 23\]
Thus, the private key is d = 23.
After that, we need to encrypt our message. Let the original message be m and the encrypted message be c. Let’s say the message we want to send is 7. We use the following encryption formula.
\[c = m^e \pmod{n}\]
Substitute your values and get value of c:
\[c = 7^7 \pmod{55}\]
Work out \(7^7\pmod{55}\).
Calculate \(7^4 \pmod{55}\):
\[7^4= 49 \times 49 = 2401 \pmod{55}\]
Divide 2401 by 55:
\[2401 \div 55 = 43 \times 55 + 36\]
So \(7^4= 36 \pmod{55}\).

Now calculate \(7^7 \pmod {55}\):
Calculate \(36 \times 49 \times 7 \pmod {55}\):
\[36 \times 49 \times 7 = 12348 \pmod {55}\]\[12348 = 224 \times 55 + 28\]
Hence the encrypted message is c = 28.

Decryption

Once the message is received, we decrypt the message and use the decryption formula:
\[m = c^d\pmod {n}\]
Substitute the values of c and d below.
\[m = 28^{23} \pmod{55}\]
The decryption procedure follows.
First, calculate \(28^4\pmod {55}\):
\[28^4 = 14 ^2 \pmod{55}= 196\pmod{55} = 196 − 3\times55 = 196 − 165 = 31\pmod {55}\]
Next, calculate \(28^8 \pmod {55}\):
\[28^8 = 31 ^2 = 961 \pmod {55} = 961 − 17\times55 = 961 − 935 = 26 \pmod {55}\]
Then, calculate \(28^{16} \pmod {55}\):
\[28^{16} = 26 ^2 = 676 \pmod {55}) = 676 − 12\times55 = 676 − 660 = 16 \pmod {55}\]
Now calculate \(28^{23} \pmod {55}\):
\[28^{23} = 16 × 31 × 14 × 28 \pmod {55}\]
Calculate \(16 \times31 \pmod{55}\):
\[16 × 31 = 496 \pmod {55} = 496 − 9 × 55 = 496 − 495 = 1 \pmod {55}\]
Then calculate \(14 × 28 \pmod {55}\):
\[14 × 28 = 392 \pmod {55} = 392 − 7 × 55 = 392 − 385 = 7 \pmod {55}\]
So:
\[1 × 7 = 7 \pmod {55}\]
The decrypted message is 7, which matches the original message.

Mathematical Formulation

We can demonstrate that the RSA algorithm will always work mathematically. Let the encrypted message be c and the original message be m.
\[c = m^e \pmod {n}\]
\[m = c^d \pmod {n}\]
\[m = m^{e\times d} \pmod {n}\]
Since \(e \cdot d ≡ 1 \pmod {ϕ(n)}\), we can write for some non - negative integer k:
\[e \times d = kϕ(n) + 1\]
Substitute \(kϕ(n) + 1\) into the exponent:
\[m ≡ m^{kϕ(n)+1} \pmod{n}\]
Split the exponent:
\[m ≡ m^{kϕ(n)}\cdot m ^1 \pmod {n}\]
Using Euler’s theorem, \(m^{ϕ(n)} ≡ 1 \pmod {n}\) (valid when m is co-prime to n), so:
\[m^{kϕ(n)} ≡ 1 ^k ≡ 1 \pmod {n}\]
Thus:
\[m ≡ 1 \times m ≡ m \pmod {n}\]
Hence the decrypted message is always equivalent to the original message m.

Why is RSA unbreakable?

RSA relies on the fact that multiplying two prime numbers is easy but breaking down a number into two prime factors is extremely difficult. A RSA key nowadays is normally 2048 bits or 4096 bits, making it computationally impossible to break n down into p and q.

What is RSA used for?

RSA is used to securely transmit data across the internet and protect your sensitive information. Despite RSA being invented in 1977, it is still widely used across the world. So next time you send that important email or receive a text, thank the humble numbers behind it.