In details

Riemann's hypothesis and the Internet II


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 TheB (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, TheB (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 + rwhere 0 ≤ r < no; soon, The - r = when, that is, no divide The - r. Therefore, by the definition of congruence Ther (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 TheThe (mod no) what if TheB (mod no), then BThe(mod no). The addition, multiplication, and potentiation operations behave as follows.

If TheB (mod no) and çd (mod no) then:

The + c B + d (mod no),

The ç B d (mod no),

TherBr (mod 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 Ther (mod no) where 0 r < no. For example, to determine the rest of the division of 310 by 13 we made 310 and then divide it by 13, which is not easy. However, the notion of congruence greatly facilitates this procedure. Firstly we note that:

33 ≡ 1 (mod 13), this is easy!

Now by elevating everything to the cube, we get

(33)3 ≡ (1)3 mod 13 ie 39 ≡ 1 (mod 13).

If we multiply both sides of the congruence by 3, then we get 310 ≡ 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 Nwhich is the product of two distinct cousins P and what, that is, N = p • q.

(2) an integer AND, known as a coding key, which satisfies the following properties: the greatest common divisor (MDC) between AND and the product (P - 1) (what - 1) is 1, and the MDC between AND and N is also 1.

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 (P -1) (what -1)).

We observed that the relationship between AND and D is symmetrical, that is, if D is the decryption key for AND, then AND is the decryption key for D.

Let's encode the message PUBLIC KEY using the RSA system with N = 2537 and encryption key AND = 13. First, we note that N = 43.59 where 43 and 59 are prime numbers.

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 = P13 (mod 2537).

For example, when we code the first block, we have to solve C ≡ 152013 r (mod 2537). Then we proceed as follows:

<>

15202 = 2,310,400 = 910 • 2537 + 1730 ≡ 1730 (mod 2537);

<>

15204 = 17302 = 2,992,900 = 1179 • 2537 + 1777 ≡ 1777 (mod 2537);

<>

15208 = 17772 = 3,157,729 = 1244 • 2537 + 1701 ≡ 1701 (mod 2537);

<>

152012 = 15208.• 15204 = 1701 • 1777 = 3.022.677 = 1191 • 2537 + 1110 =

<>

= 1110 (mod 2537);

152013 = 152012 • 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

<