RSA: How Maths will protect us while P!=NP

Introduction

In a previous post we talked about how mathematics could help us become better programmers, this time we will talk about how mathematics is the basis of global cybersecurity thanks to RSA cryptography.

The importance of cryptography has been very large through history. Mainly it has been used by military and governments, being able to keep secrets with the enemies can be the main factor of victory.

There are many examples and stories about its use in history. Caesar’s cipher, used by Julius Caesar to hide his military secrets, the famous Zimmermann Telegram that accelerated the entry of the United States in the First World War, or work of Alan Turing, who worked on decrypting the Nazi codes, particularly those of the Enigma machine which shortened the Second World War about two years (historians estimation). And many more examples…

Now it is not only used in war conflicts, but also in security conflicts (both personal and corporate) and in the fight for the defense of personal privacy. Phil Zimmermann (creator of PGP) summed it up in a statement whose first (and very good) sentence is “It’s personal. It’s private. And it’s no one’s business but yours.”.

The main objective of this post is to explain two things: one, how the RSA algorithm works and on what lies his complexity and (two) why mathematics right now supports its security, that is, we will talk about the famous and very important question P = NP?

Public Key Cryptography

Since cryptography existed up to thousands of years later, the importance of the encryption system lays in the complexity of the algorithm and in the distribution of the key to decrypt it. More and more complex algorithms were built, which required an increasingly complex key, in turn, to be decrypted. But these algorithms always had the same problem. What happens if the key is found? How could you distribute the password without compromising your privacy? In a small part of cases, this caused real logistical problems, for example when distributing the thousands of key books generated by a large army. In the end, the sophistication of the algorithm did not matter, all were vulnerable if the key to decryption was found.

So the cryptographic community began to focus on the distribution of the keys, and with it began to work theoretically in something that seems contradictory: a system of exchange of keys.

In 1976, at the historic National Computing Congress, Whitfield Diffie and Monte Hellman presented the Diffie-Hellman algorithm. They came up with a way for two individuals to exchange encrypted messages without having to exchange any key. This method used modular arithmetic as well as the properties of the prime numbers of the operations that imply them.

Diffie and Hellman proposed the bases that were soon taken and developed in 1977 by Ronald Rivest, Adi Shamir and Leonard Adleman, who determined that the ideal mathematical function to create an asymmetrical cryptography system with the public key was factorization. This is the origin of the RSA.

How does RSA work?

Recall that the RSA algorithm is asymmetric cryptography, also called public-key cryptography.

In short, a public-key algorithm works as if each of us had an open box (of which only the owner has the key) so that anyone could enter a message. When someone wants to send us something, he or she enters the message in the box and closes it. Now only the owner can open it. That way, if I want to send a message to Bob, I’ll just have to look for his box, enter the message inside and close his box.

Later we will explain the functions that are used to encrypt the messages but we will start explaining above, how it works and what the mechanism is.

We could do it with the classic example of Alice and Bob, but you can find many examples with these characters and we prefer to do it, because we like it much more, with Star Wars.

Encryption example with RSA:

1. Leia records the message explaining to Obi-Wan that the R2D2 unit includes fundamental information for the Rebel Alliance, which should reach Alderaan as soon as possible.

2. Leia asks R2D2 to encrypt the message with the public key of Obi-Wan Kenobi.

1. Leia sends R2D2 with this message to find Obi-Wan and show it to him.

1. Obi-Wan receives the message, thanks to Luke, and decrypts it with his private key.

2. Obi-Wan can already understand Leia’s message and get down to work with Luke to help the Rebel Alliance.

Digital signature example with RSA:

1. Read the message (same as the previous example).

2. Leia asks R2D2 to digitally message with his private key.

3. Leia sends this message with R2D2 to find Obi-Wan and show it to him.

4. Obi-Wan receives the digitally signed message and verifies that the message is effectively from the princess using Leia’s public key.

5. Obi-Wan can now listen to the message in complete confidence that the person who has recorded it has been read.

In the real world, sadly Leia, Obi-Wan, and R2D2 don’t exist :_( , so we can change Leia and Obi-Wan for random people (or anything that needs to send a message) and R2D2 by Internet to give sense to the example.

Let´s learn RSA´s maths (only for the brave ones)

First of all, if you are not a maths lover or you can´t wait to know more about P=NP? (or you are just tired) jump to the next chapter.

Let’s start by the beginning. We have to choose two prime numbers that are big … how big? Of the order of 10200. Neither can be very close to each other, let’s say they have to have at least a difference of the order of 1090.

The number n = p * q is half of our public key! To find the other half we have to do some more operations. First, we find the number φ(n) = (p-1) (q-1) what is called fi of Euler.

Now we have to find a number such that the greatest common divisor of φ(n) and that number is 1, ie, be coprime. There are many possibilities, there are even people who prefer to always take the same: 216 + 1 = 65537. No matter what you choose, the important thing is to be coprime (we’ll see why). We call this number e and it is the other half of our public key. That is, the public key is: (n, e).

And the private key? The private key d is the modular inverse of e in the module φ(n). This inverse exists and is unique because φ(n) and e are coprimes.

Now, let’s say that we have published somewhere our public key (n,e) = (46927,39423) and now a friend wants to send us the message m = “YES”. How would he encrypt it?

1. The first thing is to convert the letters to a number, that is, in the 26-letter alphabet put m in base 26. In our example: YES = (24,4,18) → x = 24 * 262 + 4 * 26 + 18 * 260 = 16346.

2. We now use the formula y=xe(mod n). That is, we raise x to e and find the remainder of that number by dividing by n. In our example: y = 1634639423 (mod 46927) then y = 21166.

3. We only have to put that number again on base 26: c = (y)2626. In our example: 21166 = 1 * 263+ 5 * 262 + 8 * 261 + 2 = (1582) 26 → BFIC.

So he send us the text c = “BFIC” … ok … how do we decrypt it? That is, with the private key, simply by doing: m = cd (mod n).

Observations:

• If we public d then anyone can decrypt the message.

• If we public p or q then anyone could calculate φ(n) so could calculate d. So knowing φ(n) is the same as knowing p and q. ¹

• We could decrypt the message without stealing anything, “only” finding p and q by factorizing n. This is the main point of the next section.

P=NP?

This is the question that is on everyone’s lips. But… why?

Broadly speaking, if this equality were met, world security would be compromised because many algorithms (also the RSA) would be able to be solved in reasonably small times.

But we are not going to stay in these few lines, we are going to explain with a little more depth what this equation??? means. Go for it.

The first thing we need to know is that we are focusing on decision problems. These problems are those where the possible answers are “yes” or “no“.

We can classify these problems into classes of complexity, two of these classes are in which we are going to focus: P and NP.

The P class compose those problems that are solved in a polynomial time ². The variable that defines the time that will take the algorithm is the input data. An example of an algorithm: Game of Life — Given an initial configuration of Conway’s Game of Life, a particular cell, and a time T (in unary), is that cell alive after T steps? ³

The NP class is composed of those problems in which the solution can be checked in a polynomial time. Remark that is the verification, not the resolution of the problem that is solved in polynomial time. We already have a lot of NP class, all the problems of class P! This is because the class P is contained in the class NP because if we delay in solving them in a polynomial time will also take a polynomial time to verify them.

Let’s think about the RSA. We know that the factorization of numbers takes an exponential timebut verification can be done in a polynomial time (simply checking if the division between each of the primes in which it is factored has zero rest). There are other examples of NP problems such as the traveler problem (belongs to the NP-complete class). These problems are NP, but … Are they in class P? If they were, we would have a big problem.

From here comes our initial question, will be P = NP? Are the two classes really the same class? Can we solve NP problems in a polynomial time?

If we finally proved that these problems are in class P (and therefore P = NP), many things would change. One way to prove this would be to see that a NP-complete class problem belongs to class P, so all NP problems would be P … but that’s another story.

On the one hand we could solve these problems in a much smaller time, but on the other hand, this would mean that global security would be compromised since algorithms like the RSA would not be effective, and we would have to look for other ways to protect ourselves.

With quantum computation, these algorithms will no longer make sense since, for example, the Shor algorithm 4 can break RSA in polynomial time. But in the meantime (it seems that quantum computing is not nearly as close as we thought a few years ago), we are safe. And when we are not mathematics will give us another solution to be.

Notes:

1. ϕ(N) = (p − 1)(q − 1) = pq − p − q + 1 = N − p − q + 1 so p + q = N + 1 − ϕ(N). As we know that pq = N, we have the sum and the product of numbers p and q (you can solve the equation by yourself).

2. A polynomial is a sum of terms of type k * xn where n > = 0. For example 3x3 + 5x2. An example of a non-polynomial would be 1/x or 2x.

3. P-complete page in Wikipedia: https://en.wikipedia.org/wiki/P-complete

4. With the quantum algorithm of Shor the factorial decomposition would take O((log N)3) instead of O((log N)k). From exponential to polynomial.

*This post originally appeared on Datio’s Blog on July 31, 2017.