Developing a secure encryption system in the age of supercomputers is not easy. However, scientists R. Rivest, A. Shamir and L. Adleman have developed a public-key cryptosystem called “RSA” that has been inviolable. This cryptosystem depends on the mathematical knowledge of prime numbers and their properties.

As we saw in the previous columns, the work of the mathematical community was very important in the elaboration of this system. The German mathematician C. F. Gauss formulated the notion of congruences, which is fundamental in the coding and decoding of keys in the RSA system. On the other hand, the proposed method is justified because of a Swiss mathematician L. Euler theorem, which is a generalization of a congruence result of the French mathematician P. de Fermat, known as “Fermat's Little Theorem”. As with Fermat's Last Theorem, the French mathematician only stated this result and it was up to Euler to demonstrate and generalize Fermat's Little Theorem. This result states that:

“If *P* is a prime number, and *m* is an integer that is not divisible by *P*,

So *m ^{P}*

^{ - 1 }≡ 1 (

*mod*

*P*), that is, the rest of the division of

*m*

^{P}^{ - 1 }by cousin

*P*é 1.”

For example, the rest of the division of 1,024 = 2^{10} = 2^{11 - 1} by 11 is 1.

Euler's generalization of this theorem applies to any module. Therefore, we will use the required version to justify the RSA system, where the module consists of the product of two prime numbers.

Euler-Fermat Theorem:

“If *P* and *what * are a prime numbers, and *m* is an integer that is not divisible even by *P* and not for *what*,

So *m *^{(P-1)×(what-1)} ^{}≡ 1 (*mod* *P*•*what*), that is, the rest of the division of *m *^{(P-1)×(what-1) }per *P*•*what* é 1.”

For example, the rest of the division of 256 = 2^{8} = 2^{2.4} by 15 = 3.5 is 1.

As we saw earlier, to encode a text, according to the RSA system, you need:

(1) a large number ** N**which is the product of two distinct cousins

**and**

*P***, that is,**

*what***=**

*N***•**

*P***.**

*what* (2) an integer ** AND**, known as a coding key, which satisfies the following properties: the greatest common divisor (MDC) between

**and the product (**

*AND***- 1)•(**

*P***-1) is 1, and the MDC between**

*what***and**

*AND***is also 1.**

*N*To decode a text, according to the RSA system, you need:

(3) an integer ** D**, known as a decryption key, which satisfies the condition:

** AND**•

**≡ 1(**

*D**mod*(

**-1)•(**

*P***- 1)).**

*what* The relationship between ** AND **and

**is symmetrical, that is, if**

*D***is decryption key for**

*D***, then**

*AND***is decryption key for**

*AND***.**

*D* In the previous columns we coded the message **PUBLIC KEY** using the RSA system where we choose

* N *= 2.537 = 43•59,

**= 43,**

*P***= 59 and coding key**

*what***= 13.**

*AND*First, we note that the number ** N **= 2.537 has 4 digits and so we break the text into pairs of letters:

**PU BL IC KE Y**

and complete the last block with the letter **Ç** getting:

**<>**

**PU BL IC KE YC**<>

.

Using the conversion table that associates natural number alphabet letters, the converted message blocks are:

**1520 **** 0111 0802 1004 2402**.

This way, the receiver will receive the encrypted message:

**0095 1648 1410 1299 0811**.

To decrypt this message we need the public decryption key, ** D**. In the previous column we obtained

**= 937 as the decryption key.**

*D* We encode each block, ** P**, of the message in an encrypted block

**using the relation**

*Q**<>*

** Q**<>

≡ *P*^{13} (*mod* 2.537).

To decode the block ** Q** of this encrypted message we must use the relation

** P** ≡

*Q*^{937}(

*mod*2.537), 0 ≤

**< 2.537.**

*P*We note that this relationship is valid because

** Q** ≡

*P*^{13}(

*mod*2.537) impliesin

*<>*

*Q *^{<>}

937<>

≡ (*P*^{13})^{937} (*mod *2.537) ≡* P*^{12.181 } (*mod *2.537).

<>

As 13۰937 = 12.181 = 5۰2.436 + 1, we get

*<>*

*Q *^{<>}

937<>

≡ (*P*^{13})^{937} (*mod *2.537) ≡ *P*^{12.181 } (*mod *2.537) ≡ (*P*^{2.436})^{5} ** P** (

*mod*2.537).

By the Euler-Fermat Theorem, since 13 and 59 are prime numbers, we get

*<>*

** P**<>

^{(13 - 1) (59 -1) }=* P*^{2.436} ≡ 1 (*mod* 2.537)

and then,

<>

(*P*^{2.436})^{5} ** P** ≡

**(**

*P**mod*2.537).

Therefore, by transitivity, we obtain

*<>*

*Q*^{<>}

937<>

≡ ** P** (

*mod*2.537), 0 ≤

**< 2.537**

*P*when MDC (** P**, 2.537) = 1.

Note that the relationship

*<>*

*Q*^{<>}

937<>

≡ ** P** (

*mod*2537), 0 ≤

**<2,537, MDC (**

*P***, 2.537) = 1**

*P*is true for all blocks in this example.

Now let's take ** Q** like block 0095. So we have to solve the congruence

95 ^{937} ≡ ** P** (

*mod*2.537),

that is, determine the rest of the division of 95^{937} for 2,537.

First, we note that this congruence is easier to solve if we take 937 as the sum of base powers 2:

937 = 512 + 256 + 128 + 32 + 8 + 1 = 2^{9} + 2^{8} + 2^{7} + 2^{5 } + 2^{3} + 1.

Therefore, we have:

95^{2} = 9.025 = 3<>

۰2.537 + 1.414 ≡ 1.414 (*mod* 2.537);

soon,

95^{4} ≡ (1.414)^{2} (*mod* 2.537).

How (1,414)^{2} = 1.999.396 = 788<>

372,537 + 240, it follows that

95^{4} ≡ 240 (*mod* 2.537).

In the same way we get:

95^{8} ≡ 1.786 (*mod* 2.537);

95^{16} ≡ 787 (*mod *2.537);

95^{32} ≡ 341 (*mod* 2.537);

95^{64} ≡ 2.116 (*mod *2.537);

95^{128} ≡ 2.188 (*mod *2.537);

95^{256} ≡ 25 (*mod* 2.537);

95^{512} ≡ 625 (*mod *2.537);

Therefore:

(95)^{937} =

(95)^{512} <>

۰ ^{}(95)^{256}<>

۰^{}(95)^{128}<>

۰^{}(95)^{32}<>

۰ (95)^{8}<>

۰^{}(95) ^{}≡

625<>

۰25<>

۰2188<>

۰341<>

۰1786<>

۰95 (*mod* 2.537).

Taking the products two by two, we get:

625<>

۰25 = 15.625 = 6<>

۰2.537 + 403 ≡ 403(*mod* 2.537)

2.188<>

۰341 = 746.108 = 294<>

۰2.537 + 230 ≡ 230(*mod* 2.537)

1.786<>

۰95 = 169.670 = 66<>

۰2.537 + 2.228 ≡ 2.228(*mod *2.537).

Soon,

625<>

۰25<>

۰2.188<>

۰341<>

۰1.786<>

۰95 (mod 2.537) ≡

403<>

۰ 230<>

۰ 2.228 (*mod* 2.537).

How

403<>

۰230 =

92.690 =

36<>

۰2.537 + 1.358 ≡

1.358(*mod* 2.537)

follow that

1,358۰ 2,228 = 3,025,624 = 1,192۰2,537 + 1,520 ≡ 1,520 (mod 2537).

We concluded that

625<>

۰25<>

۰2.188<>

۰341<>

۰1.786<>

۰95 =

1.358۰ 2.228 =

3.025.624 =

1.192۰2.537 + 1.520 ≡

1.520 (*mod* 2.537).

Therefore, ** Q** corresponds to block 1.520.

Research on the Riemann Hypothesis provides such precious information about the prime number pattern that advances in this investigation could lead us to substantial progress in factoring techniques and, consequently, to a breach of security in data transmission over the Internet.

We emphasize that the development of the RSA cryptosystem represents another outstanding example of the need for mathematical research, as it represents the work of countless generations of mathematicians. In fact, it is worth remembering that it was Euclid, more than two thousand and three hundred years ago, who showed ingeniously that there are infinite prime numbers.

Despite all the power and power that mathematics shows, there is still a rather poor and inconsistent idea that identifies it only with a language in the service of science…

Mathematics is one of the greatest creations of the human spirit and we close with the words of one of the creators of Differential and Integral Calculus, the German mathematician Leibniz:

"Mathematics is the honor of the human spirit."

Back to columns

<