In 1977, scientists R. Rivest, A. Shamir and L. Adleman proposed a public-key crypto system called RSA. This system uses some elementary ideas from Number Theory.

Although the ideas used are elementary, this does not mean that they are trivial. Indeed one of the greatest mathematicians of all time, the German mathematician Gauss (1777-1855), created and developed the notion of congruences that is fundamental in the coding and decoding of keys in the RSA system. Congruences, and the consequent development called Modular Arithmetic, make a major contribution to Number Theory. In particular, the questions of divisibility, because when there is a need to work with the remains of the Euclidean division, congruences are the appropriate instruments.

Gauss introduced the concept of congruence in the first chapter of his work “Disquisitiones Arithmeticae” published in 1801. Gauss introduced, simultaneously with the concept of congruence, the notation “≡”, which made the concept a powerful technique in Algebra and Number Theory. Let's go to the definitions.

We consider two integers *The*, *B* and *no* a positive integer. If *no* divide *The* - *B*, then we say that *The* is congruent to *B* module *no*, and we wrote *The* ≡ *B* (mod *no*).

For example:

37 ≡ 2 (mod 5), because 5 divides 37 - 2 = 35,

27 ≡ 3 (mod 4), because 4 divides 27 - 3 = 24,

7 ≡ 7 (mod 4), therefore 4 divides 7 - 7 = 0.

Therefore, *The* ≡ *B* (mod *no*) it means that *no* divide *The* - *B*; so there is an integer *k* such that *The* - *B* = *kn* by the definition of divisibility. For example, 37 ≡ 2 (mod 5) implies that there is *k* (= 7) such that 37 - 2 = 35 = 7 • 5.

Given the integers *The* and *no*, we know from the Division Algorithm that there are integers *what* and *r* respectively, quotient and remainder, such that: *The* = *when* + *r*where 0 ≤ *r* < *no*; soon, *The* - *r* = *when*, that is, *no* divide *The* - *r*. Therefore, by the definition of congruence *The* ≡ *r* (mod *no*).

The rest *r* can assume any value between 0 and *no* - 1. Thus, we conclude that every integer *The* is congruent module *no* to exactly one of the values between 0, 1, 2,…, *no* - 1. The set {0, 1, 2,…, *no* - 1} of integers *m* which are the remains of the module divisions *no*, is called the module waste class *no*. If we fix *no* = 7, so module 7 has exactly 7 elements, namely: 0, 1, 2,…, 6. Therefore, whatever the integer, it is congruent to a single element of module 7.

For example, 20 is represented by 6 in the mod 7 residue class, since 20 ≡ 6 (mod 7).

The idea of congruence is present in our daily life if we think that clocks mark the hours module 12, days of the week are measured module 4, months of the year follow a module 12 pattern. Due to the many similar properties between congruences and equality, Gauss chose the “≡” symbol for the matching signal.

Notice that *The* ≡ *The* (mod *no*) what if *The* ≡ *B *(mod *no*), then * B* ≡ *The*(mod *no*). The addition, multiplication, and potentiation operations behave as follows.

If *The* ≡ *B* (mod *no*) and *ç* ≡ *d* (mod *no*) then:

*The* *+ c *≡ *B* *+ d* (mod *no*),

*The *•* ç * ≡ *B *•* d* (mod *no*),

*The ^{r}* ≡

*B*(mod

^{r}*no*).

The method presented in the following example is fundamental in our handling of key encoding and decoding in the RSA system. Moreover, it is a very interesting example of applying the notion of congruences.

To determine the rest of the division of *The* per *no* it is enough to find an integer *r* such that *The* ≡ *r* (mod *no*) where 0 *r* < *no*. For example, to determine the rest of the division of 3^{10 } by 13 we made 3^{10} and then divide it by 13, which is not easy. However, the notion of congruence greatly facilitates this procedure. Firstly we note that:

3^{3} ≡ 1 (mod 13), this is easy!

Now by elevating everything to the cube, we get

(3^{3})^{3} ≡ (1)^{3} mod 13 ie 3^{9} ≡ 1 (mod 13).

If we multiply both sides of the congruence by 3, then we get 3^{10} ≡ 3 (mod 13).

Today's computers have reached such sophisticated levels that any crypto system must be robust enough to withstand the attacks of individuals who want to break the security of their transactions.

In 1975, mathematicians W. Diffie and M. Hellman proposed a whole new system of encryption: public key cryptography. In this encoder method two keys are used: one for encoding and one for decoding. Some specific methods were developed to implement the ideas of Diffie and Hellmann. However, the most supported method that remains the default is the RSA system.

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 • q* (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:

** E • D** ≡ 1 (mod (

**-1) (**

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

*what*We observed that the relationship between** AND **and

**is symmetrical, that is, if**

*D***is the decryption key for**

*D***, then**

*AND***is the decryption key for**

*AND***.**

*D*Let's encode the message **PUBLIC KEY **using the RSA system with ** N** = 2537 and encryption key

**= 13. First, we note that**

*AND***= 43.59 where 43 and 59 are prime numbers.**

*N*Thus, MDC (13, (43 - 1) • (59 - 1)) = MDC (13, 42 • 58) = 1, since integer 13 does not divide 42 nor 58; MDC (13, 2537) = 1, because 13, 43, and 59 (2537 = 43 • 59) are prime numbers. Now we convert the text using the letter-number matching table:

A = 00, B = 01, C = 02, D = 03,…, X = 23, Y = 24, Z = 25.

How ** N** = 2537 contains 4 digits, we wrap 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 above, the 5 converted message blocks are:

**1520 0111 0802 1004 2402**.

We will call B the four-digit block. The next step is to calculate the value of each of the four digit blocks raised to exponent 13 (mod 3127), that is, given a block B, we want to determine C such that C = P^{13 }(mod 2537).

For example, when we code the first block, we have to solve C ≡ 1520^{13 } ≡ *r *(mod 2537). Then we proceed as follows:

<>

1520^{2} = 2,310,400 = 910 • 2537 + 1730 ≡ 1730 (mod 2537);

<>

1520^{4} = 1730^{2 }= 2,992,900 = 1179 • 2537 + 1777 ≡ 1777 (mod 2537);

<>

1520^{8} = 1777^{2 }= 3,157,729 = 1244 • 2537 + 1701 ≡ 1701 (mod 2537);

<>

1520^{12} = 1520^{8}.• 1520^{4} = 1701 • 1777 = 3.022.677 = 1191 • 2537 + 1110 =

<>

= 1110 (mod 2537);

1520^{13} = 1520^{12} • 1520 = 1110 • 1520 = 1,687.200 = 665 • 2537 + 95 = 95 (mod 2537).

Thus, the coding of 1520 is 0095.

The other message blocks are encoded in the same manner, that is, each block consisting of four digits rising to the power 13 (mod 2537). Therefore, the receiver will receive the encrypted message:

**0095 1648 1410 1299 0811**.

Note that we cannot convert this message to letters as some pairs of block constituent digits are greater than 25. In the next column we will take the steps to decode messages according to the RSA system and decode the message from this example.

Back to columns

<