When clicking on the padlock in the address bar of an internet session, a window appears with the message: “Safari uses an encrypted connection with …”. [red. this message may look slightly different for other browsers]

After pressing the buttons ‘Show certificate’ and ‘detail’, a lot more is shown. The typically used security algorithm nowadays at most news sites etc. at the opening session is: public key with elliptic curve.

But for the sites where security really is an issue, e.g. a login session into your bank account or a large online store, RSA is the encryption algorithm. And RSA encryption is the subject of my contribution this time.

In a previous essay that I published in the math section of this blog, I addressed the famous computer science problem: P vs NP.

As I explained then, there are many cases to be found under this problem, most of them hard to grasp, so I chose for number factorization because this particular example is rather easy to understand.

Remember that factoring a large number is a hell of a job but once the factors are known it is a piece of cake to multiply them and get the original number back. On this principle RSA is based.

RSA is an asymmetric encryption/decryption algorithm designed by Rivest, Shamir, and Adleman hence the abbreviation.

Articles in the science sections of numerous news papers has pointed this out, along with the warning that quantum computers in the near future will be capable of performing such challenging calculations in a fraction of the time the nowadays supercomputers can do it.

The writers of those articles then mention that the RSA approach involves asymmetric encryption, at which a public and a private key are used.

Some of them proceed by telling that a message encrypted with the public key, cannot be decrypted by use of this key, that merely can be done by using the private key. So even if the public key is intercepted by a malicious person, no harm can be inflicted.

At this point their explanation stops, leaving most readers puzzled.

What does this asymmetric encryption actually mean and how can it be that a message that is encrypted with a key, cannot be decrypted by this key?

Let me try to shed some light on this.

In order to follow the elaboration of these issues, high school level with mathematics included is an advantage.

RSA, the basics.

Abundant examples of how to RSA encrypt/decrypt can be found on the internet, all of them avoiding the use of larger numbers examples.

Nevertheless, these small-scale examples are illuminating enough to provide answers on our early questions on the topic.

Let us first zoom in on some concepts that play an important role in the RSA calculations.

• Modulo function

Gives the integer ‘leftover’ from a division.

Examples: 67 mod 5 = 2, 92 mod 11= 4,

15 mod 7 = 1

This is often written as 15 ≡ 1 mod(n)  // e.g. for n = 7

The three bar symbol ≡ means: is equivalent to. It is not exactly the same thing but it is congruent to it.

The old analog clock gives a good example of the modulo function.

The hour hand counts the hours modulo 12 and the minute hand does that for the minutes modulo 60. After each completed cycle they restart counting at 1.

No matter how many cycles, the hands will not go beyond their modulo limit.

• Eulers Totiënt function

In number theory the totiënt (aka indicator) is the number of positive integers  ≤ n – written as φ(n) –  that are relative prime with n.

Numbers being relative prime or coprime means: the numbers do not contain any factor in common. The totiënt of 12 is 4 => 1, 5, 7 and 11. The number 1 is not considered to be a factor of other numbers.

The totiënt of a prime number p is p -1 since the only common factor is p.

For a prime q this works the same so the totiënt is q -1.

And of course, the product n = p x q has as totiënt (p-1) x (q-1). We now know that this is written as φ(n = (p-1) x (q-1).

I like to show here and now Eulers theorem which goes:

a^Φ(n) ≡ 1 mod(n)

This theorem lies in the heart of RSA and it is this equation that makes its calculations spin.

But we are getting far, far ahead of ourselves.

It is time for an example.[br]

•  The protocol

When the techniques and protocols behind a two-side communication – from a simple telephone call up to entangled quantum information exchange – are explained on the internet, the ‘conversation’ is invariably conducted by the persons Alice and Bob.

Let us stick to this habit and describe a data exchange among them under RSA-security.

Alice initiates the session by sending the word ‘HELLO’.

The RSA protocol works, as stated earlier, with two keys: one public and one private, so Alices computer generates a public key and a private key.

It chooses two large prime numbers, p and q.

Their product n=p x q will be half of the public key. The totiënt of n = φ(n = (p-1) x (q-1).

The other half of the public key is e (at encryption time to be used as exponent). This number must be coprime to φ(n).

Then the modular inverse of e modulo φ(n) is calculated. We call this number d. It is half of the private key. I will come back on this step later in great detail.

Now let’s do the setup.

The ‘real’ RSA uses 2048-bit numbers but this is impractical for our goal.

Remember, such numbers are big! They have 617 decimal digits!

We just want to understand the procedures behind. In this essay we use larger numbers in our description than most of the internet examples but not that large.

We kindly ask Alices computer to use the following values for the encryption/decryption processes.

This can’t be done in reality of course but we fake it for examples sake.
We want to use:
p = 191 // prime number 1
q = 233 // prime number 2
n = p x q = 44503 // obviously a 2 factor number)
𝛗 = (p – 1) x (q – 1) = 44080 // is totiënt of the 2 factor number n
e = 7 // is a randomly chosen number 1 < e < 𝛗(n ) and e is coprime to 𝛗(n)

This means that Alices public key is twofold: n and 7.
The private key, also twofold: n and d = 37783 —> 37783 x e  ≡ 1 mod(𝛗). I’ll explain the role of d later.

Alices computer sends in plain text the greeting “Hello Bob” along with the public key. She keeps the private key to herself.

Bob wants to send back the message “Hello Alice” and encrypts this message with Alices public key. Bob also makes his own pair of public and private keys and makes his public key part of the message to send. He will keep his private key to himself. His message is encrypted with Alices public key.

Encryption of the message:

Because Bobs cheap computer is limited in performance, it encrypts and sends one letter at a time so it starts with the letter H of “Hello Alice”. Besides the message may not be longer than the value of n.

H = ascii value 72. We call this value M from M)message.

The computer uses Alices public key values:  // n = 44503 and e=7 The encrypted value C is M^e mod n = 72⁷ mod 44503 = 37774.

Once again: C=37774.

Bob send this result to Alice and Alices computer starts the decryption: RSA knows how to do this: it wants to calculate M= C^d mod n but here we run immediately into a problem, so I take over the role of her computer.

•  Modular arithmetic

C^d = 37774³⁷⁷⁸³ =1.20840237544473711326829460169129099… × 10^172940 and from that number we are supposed to take the modulo(n) but this insanely large number has 172941 decimal digits, now what?

I fed the calculation 37774³⁷⁷⁸³  modulo 44503 into WolframAlpha’s supercomputer and the answer came promptly: 72 which indeed is the ascii value of ‘H’.

I agree that supercomputers can do amazing things but this kind of calculations are supposed to be performed on smartphones and tablets.

Then I discovered the .Net function Math.BigInteger.ModPow, exactly what I need for C^d mod n. I wrote some code and applied the values to the ModPow function. In a split second it came back with the answer: 72.

I am certain that my ancient MacBook Air running Windows10 and Visual Studio isn’t capable of matching WolframAlpha’s Cray model Hyper17, so what is the trick here? Digging the internet brought me a way out of this wrestling with unimaginable large numbers: modular arithmetic comes to the rescue.

Modular Arithmetic has this amazing property:

if a mod(N) ≡ b mod(N),

then a^k mod(N) ≡  b^k mod(N) for any positive  integer k

This means, whenever we raise a to a power and apply the modulo on it, the equivalence with b mod… will remain when we raise b to this power and apply the modulo. And when we do this power raising in small steps rather than in one leap, the modulo function will prevent from the absurd growth of numbers.

Let me show this in a working-out by calculating 37774³⁷⁷⁸³  modulo 44503.

Our exponent 37783 can be built up from the powers 1 + 2 + 4 + 16 + 128 + 256 + 512 + 4096 + 32768.

When we keep applying the modulo function on each part we will end up with this list:

37774  mod 44503	≡	37774	≡	(377741  mod 44503)
377742 mod 44503	≡	19890	≡	(377742 modulo 44503)
377744 mod 44503	≡	24933	≡	(198902 modulo 44503)
3777416 mod 44503	≡	34500	≡	(249334 modulo 44503)
37774128 mod 44503	≡	43113	≡	(345008 modulo 44503)
37774256 mod 44503	≡	18471	≡	(431132 modulo 44503)
37774512 mod 44503	≡	17843	≡	(184712 modulo 44503)
377744096 mod 44503	≡	26375	≡	(178438 modulo 44503)
3777432768 mod 44503	≡	1006 ≡	(263758 modulo 44503)

This demonstrates that the values in the center never get to large.

The left side of this list acts merely as guide lines for the right side, where the actual calculations are done.

In doing so the modulo function prevents from juggling with gargantuan numbers like

37774³²⁷⁶⁸.

Each next step is done by raising the last value to a relative modest power, where the continuous applying of the modulo keeps the result small.

So 37774³²⁷⁶⁸  mod 44503 comes down to (37774 x 19890 x 24933 x 34500 x         43113 x 18471 x 17843 x 26375 x 1006) mod 44503

If this calculation is still too awkward we may split it further into e.g.

((37774 x 19890 x 24933) mod 44503) x ((34500 x 43113 x 18471) mod 44503) x

((17843 x 26375 x 1006) mod 44503) mod 44503

The result of all this is 72. Just the ascii value of the letter H.

Of course this modular arithmetic is exactly what Alices computer does when calculating the decryption.

We now can see clearly why the public key cannot be used for decrypting the message.

The encrypted value C is safely put behind the modulo wall.

It is not impossible to ‘brute force’ the decryption but by using this very large numbers, it is not possible in a practical sense.

We really need the private key to be able to read the message.

But how can our private key achieve this goal?

Let us proceed with our research. RSA is about to reveal its secrets.

•  The modular inverse

It is time that we zoom in on the private key and especially the d part of it.

In our example this d had a value of 37783. How did we obtain this value? We got the value by calculating the modular inverse of e mod 𝛗 (n).

The formal definition of modular multiplicative inverse (modular inverse for short) is: a modular multiplicative inverse is an integer x such that the product ab is congruent to 1 with respect to the modulus m.

Well, that is extremely formal but written down it reads a lot easier: ab ≡ 1 mod(m) or a x b(mod m) = 1.

So a is the number that makes the equation a x b(mod m) = 1 true.

But we are not looking for a, we are looking for d, the non-trivial part of the private key (it’s trivial part is n, the 2-factor number p x q).

Again formally: d is the modular inverse of e with respect to modulus 𝛗 (n).

Now d is the value that makes the equation d x e mod 𝛗 (n) = 1 true. Where 𝛗(n) is Eulers totiënt function of n, as explained earlier. And let us not forget that 𝛗(n) = (p-1) x (q-1).

Our d can be calculated by using extended Euclidean algorithm. There are numerous code snippets on the internet to help with this. I used such code fragment myself for the RSA example and that gave me the value 37783.

• Euler’s Theorem

Euler’s Theorem states that a^Φ(n) ≡ 1 mod(n), where n and a are coprime positive integers and Φ is Euler’s totiënt function.

Earlier in this essay I said: “This theorem lies in the heart of RSA and it is this equation that makes its calculations spin.”

That remark came a bit too soon, but now we have the ingredients to tie it all together.

In our example we had a message M (the ascii value of H, which is 72) and it was encrypted into C by raising M to the power e and confront it with modulo(n).

C was decrypted by raising it to the power d, and apply modulo(n) to the result whereafter a neat output appeared: 72.

Once more: d is the non-trivial part of the private key.

But how is this even possible? Let’s see.

In the modular inverse section we learned that d x e ≡ 1 (mod 𝛗 (n)).

This implies that d x e – 1 is a multiple of 𝛗 (n).

How many multiples? For this we use k and we rewrite the equation as

e x d = 1 + k x 𝛗 (n)

We also can rewrite C as M^e and C^d as (M^e)^d which is the same as M^ed. All this rewriting brings us to:

M^ed mod(n) ≡ M^{1 + kΦ(n)} ≡ M x M^kΦ(n) ≡ M x (M^Φ(n))^k ≡ M x M^Φ(n) ≡ M x 1(mod n) = M mod n = M.

It is Euler’s Theorem that creates this bridge between the public key and the private key.

There are some unexpected steps in this equation chain. Let me explain.

• In RSA, M is chosen so that, M < n and M and n are coprimes. That is required in order to get at Euler’s theorem a^Φ(n) ≡ 1 mod(n) which we achieve at the step: M x M^Φ(n). From that point on we may say that M^Φ(n) ≡ 1 mod (n).
• The sudden disappearance of k can be justified by the fact that a modulo result with value 1 is transparent to exponentiation. Whatever value k has, it makes no difference to k = 1, so the exponent k drops out.
• The equation M mod n = M is here correct because M is always smaller than n. So mod n does not affect M.

• The conversation continues

The other letters of the phrase ‘Hello Alice’ go through the same procedure and Alice can respond by using Bob’s public key for the encryption of her answer.

What they probably do first is switch to a symmetric encryption protocol which is less demanding for the hardware.

The symmetric key that they both share is exchanged under the protection of RSA and this key can frequently be renewed by briefly switching back to RSA for creation and exchange of a new symmetric key.  Used this way, symmetric encryption/decryption is secure and not too burdensome on the hardware.

• Finally

I asked ChatGPT about the actual handling of the extreme large RSA used numbers and how to optimize the math behind them. He answered extensively.

Me:
Arty, what about the real large 2048-bit numbers, numbers of 617 decimal digits long?
This can yield an enormous private key. Is there another approach rather than modular arithmetic?

ChatGPT:
In practical RSA implementations with large numbers (like 2048-bit keys), direct computation becomes impractical due to the sheer size of the numbers involved. Instead, several mathematical techniques and optimizations are used:

• Modular Exponentiation:

The most critical technique is modular exponentiation, which allows for the computation of a^b mod n without having to compute a^b first, which would be impractically large.

This is done using algorithms like the Square-and-Multiply algorithm (also known as Exponentiation by Squaring).

The basic idea is to break down the exponentiation into a series of squares and multiplies, applying the modulus at each step to keep the intermediate results manageable.

• Chinese Remainder Theorem (CRT):

In the decryption process, the Chinese Remainder Theorem can significantly speed up the computation. Since the private key holder knows the prime factors p and q of n they can compute the decrypted message modulo p and modulo q separately, and then combine these results to get the final plaintext.

This method is much faster because p and q are roughly half the size of n making the exponentiation operations less computationally intensive.

• Optimized Algorithms and Hardware:

Practical implementations of RSA often use optimized algorithms that can handle large numbers more efficiently.

Additionally, specialized hardware and software optimizations are used for cryptographic calculations, especially in environments where encryption and decryption operations are performed frequently.

 

Summary

In summary, while the basic principles of RSA encryption and decryption remain the same regardless of the key size, the practical implementation of these principles for large numbers like those used in 2048-bit RSA keys requires advanced mathematical techniques and computational optimizations. These methods ensure that RSA encryption and decryption remain computationally feasible, even with the very large numbers used in real-world applications.

Me:

Thanks for this contribution. I can end my RSA research now.
My intention is to write an article on the topic for a public with modest mathematical skills in an attempt to help them understand.
Your help was of great importance to this goal.
If you want I send you a copy of my text when ready.

ChatGPT:

I’d be more than happy to review your text or provide feedback if you’d like.
Thank you for your kind words, and best of luck with your article! I’m here to help anytime you need.

 

Eef
2024-01

–––––––––––––––––––––––––––

Sources:

• Geeks for Geeks
• Wikipedia several articles
• And of course my friend Arty the AI.

Click here for all math essays on this site

 

---

Ever considered reading my books?