DEV Community: Juan López

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

Juan López — Mon, 31 Dec 2018 09:01:37 +0000

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:

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.
Leia asks R2D2 to encrypt the message with the public key of Obi-Wan Kenobi.

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

Obi-Wan receives the message, thanks to Luke, and decrypts it with his private key.
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:

Read the message (same as the previous example).
Leia asks R2D2 to digitally message with his private key.
Leia sends this message with R2D2 to find Obi-Wan and show it to him.
Obi-Wan receives the digitally signed message and verifies that the message is effectively from the princess using Leia’s public key.
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?

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.
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.
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.

Knowing Monads Through The Category Theory

Juan López — Wed, 26 Dec 2018 22:17:18 +0000

We all know that programming is based on math, what is perhaps not so clear is that knowing more math is going to help us become better developers. And although in all types of programming, math is fundamental, it is even more so in functional programming.

A very widespread concept which I’m sure you have heard lately is the monad. It is a mathematical concept of the category theory applied later in functional programming.

I first heard the term when I started programming in Scala. After much searching on the Internet, I only found articles explained by and for mathematicians or articles that talked about programming and not math. On the other hand, some abuse of language is done to refer to things that are not monads as such. So we will try to talk here, without losing the mathematical rigor, about what the monads are, and then how and why they will help us become better developers. Although they are very abstract and complex terms we will try to do it all in a simple way.

In order to understand the monads, we must first learn about two concepts, categories and functors.

Monads in functional programming

History:

Philip Wadler, who is the greatest contributor to the theory behind functional programming and the use of monads, was inspired by the use of Eugenio Moggi’s monads to give semantics to programming languages. The monads introduced the idea of sequence into the functional paradigm, but without contradicting it, thanks to the composition of functions.⁵

Many common programming concepts can be described in terms of monad structures, including side effects, I/O, exception handling…

This allows such concepts to be defined in purely functional ways without the need to add new terms to language semantics and without resorting to imperative programming. There are languages like Haskell that provide monads in the standard kernel and, although Scala does not provide it in the kernel, you are familiar with Cats and Scalaz libraries that help us develop with monads (although we can always implement our own).

Functors and monads in FP:

It has been nice explaining how the category theory in mathematics works but, as developers, we already want to see an example applied to functional programming:

This drawing⁶ represents a functor, in this case, composed of List and map. Surely you have already linked this example with the one of the Lord of the Rings and Game of Thrones´s functor.

You may have read online that List is a functor per se, just like the Scala Option class is a monad. Both are type constructors (that would be equivalent to the transformer of towns) but… where is the transformer of roads/arrows? This is a very frequent abuse of language that you will no longer see with the same eyes.
If in the previous drawing we had used flatMap instead of map (flatMap’s output is in the same category), we would have drawn a monad (although we need to check the monadic laws) instead of a functor.

There are many reasons to use monads in our programs, but I will list the top 3 main reasons (in my humble opinion) to use them:

At the end of the day, we only want to use functions (remember: functional programming).
Imagine that you have a program that performs these two functions:

f(x) = x+3

g(x,y) = List(x, y)

We want these two functions to be executed in order, sequentially, and we want to do it using only functions. So, how could we do it? Using composition of functions. If we first want to execute g and then f on the result, we compose the functions in the next way: f ∘ g (x, y).
If instead of the previous g, we use g(x, y) = x / y, we have two problems:

If the type that accepts f is different from the one that returns g (g could return a float since it is a division, and f accepts an Int) we would clearly have a problem.
What would happen if the function g passed the values 2 and 0? Indeed, there would be a failure since it can not be divided by 0. We do not want exceptions in functional programming since an exception is not a function.

What I mean is that the composition of functions needs one more ingredient to be 100% functional (this ingredient will also solve the two problems above). This ingredient, obviously (judging by the title of the post ;)), is the use of monads.

The idea is to allow functions to return two types of results, so g would no longer be: g: Int, Int → Float, but we would do that g: Int, Int → Some | None and f(x): Some | None → Some | None.

For example, we are going to undo the functions with the previous example:

def g(x: Int, y: Int): Option[Float] = {
    y match {
        case 0 => return None
        case y => return Some(x.toFloat/y)
    }
}

And the same with f(x):

def f(x: Option[Float]): Option[Int] = {
    x match {
        case None => None
        case Some(x) => Some(x.asInstanceOf[Int]+3)
    }
}

So our code would be g(x, y).flatMap (x => f (Option (x))). In this way, we have composed the two functions and avoided the exceptions, since if y is equal to 0 the result will be None.

Summary and conclusions

In short, we can say that a monad is an endofunctor which holds monadic laws. We can also say that thanks to the monads, we can compose functions, solving type problems and exceptions.

Now that we know the category theory a little better and how some of these concepts are used in functional programming, we can use the tools provided in our programs to make a better code.

Go, you can already tell your friends “I’ve seen things you people wouldn’t believe”.

Notes

1. That is, if Frodo goes from The Shire to Erebor (f) and then stays in Erebor (identity) is the same as if he goes directly to Erebor.

2. That is, if we take five paths, for example that one which goes from The Shire to Erebor (f), that one which goes from Rivendell to the Shire (g), that one which goes from Mordor to Rivendell (h), that one which goes from Rivendell to Erebor (j) and that one which goes from Mordor to The Shire (k). Then (f ∘ g) ∘ h = f ∘ (g ∘ h) since f ∘ g = j and g ∘ h = k.

3. Obviously, the paths of these maps are carefully invented so that everything fits perfectly.

4. Monadic laws with composition operation:

F ∘ id = F (Left identity)
Id ∘ F = F (Right identity)
(F ∘ G) ∘ H = F ∘ (G ∘ H) (Associativity)

5. De Euclides a Java — Ricardo Peña Mari

6. Based on Nikolay Grozev’s one

Resources and links

*This post originally appeared on Datio’s Blog on June 26, 2017.