Comments

Riemann's hypothesis and the Internet- III


The German mathematician C. F. Gauss introduced the concept of congruence in the first chapter of his work “Disquisitiones Arithmeticae”, published in 1801. This concept is fundamental in the coding and decoding of keys in the RSA system. The public key cryptosystem, called RSA, was developed by scientists R. Rivest, A. Shamir and L. Adleman.

To encode a text according to the RSA system you need:

(1) a large number Nwhich is the product of two distinct prime numbers P and what, that is, N = P۰what.

(2) an integer AND, known as a coding key, which satisfies the following properties:

the maximum common divider (MDC) between AND and the product (P - 1)۰(what -1) is 1, and the MDC

in 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:

AND۰D ≡ 1 (mod (P -1)۰(what - 1)).

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.

In the previous column we coded the message PUBLIC KEY using the RSA system with

N = 2.537 = 43•59, P = 43, what = 59 and with the encryption key AND = 13.

First, we observed that 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 C getting: PU BL IC KE YC.

Using the conversion table that associates natural numbers with letters of the alphabet, the converted blocks of the message are: 1520 0111 0802 1004 2402. This way, the receiver will receive the encrypted message: 0095 1648 1410 1299 0811.

Our goal is to take the necessary steps to decode this message according to the RSA cryptosystem. To decrypt this message we need the public key D of decoding.

Is there a method for determining Dif AND, P and what They are known. However, if P and what are not known, D cannot be determined. The security of the RSA cryptosystem lies in this fact.

If P and what are extremely large for example larger than 10200then determine these prime numbers in a reasonable time, which is equivalent to factoring N = P۰what,may be beyond the capacity of the fastest supercomputers.

Our goal is to determine Dsuch that AND۰D ≡ 1 (mod (P - 1)۰(what - 1)), in other words D is the inverse of AND module (P - 1)۰(what - 1).

The method consists of using Euclid's algorithm applied to the key AND coding and number (P - 1)۰(what - 1). How AND and (P - 1)۰(what - 1) are prime to each other, the MDC among them is 1. First, we go through all the steps of Euclid's Algorithm to determine the MDC which in this case is 1.

By the Euclidean Algorithm we have to

(P - 1)۰(what - 1) = what1۰AND+ r2, 0 ≤ r2< AND.

How do we know that MDC ((P - 1)۰(what - 1), AND) = 1, we continue applying the Euclidean Algorithm until we get the remainder of the division equal to 1. Therefore, we perform the division of AND per r2 and so on until we get the rest of 1:

AND = what2۰ r2 + r3, 0 ≤ r3< r2

r2 = what3۰ r3+ r4,0 ≤ r4< r3

rn-4 = whatn-3۰ rn-3 + rn-2,0 ≤ rn-2 < rn-3

rn-3 = whatn-2۰ rn-2 + rn-1,0 ≤ rn-1 < rn-2

rn-2 = whatn-1۰ rn-1 + 1,0 ≤ 1< rn-1.

Now using the Euclidean algorithm in reverse we can calculate D such that

AND۰D ≡ 1 (mod (P -1)۰(what - 1)).

Therefore, D It is the decryption key.

Note that:

<>

1 = rn-2 - whatn-1۰<>

r<>

n-1<>

(1)

<>

r<>

n-1<>

= rn-3 - whatn-2۰<>

r<>

n-2<>

(2)

<>

r<>

n-2 <>

= rn-4 - whatn-3۰<>

r<>

n-3<>

(3)

r4 = r2-what3۰ r3 (no - 3)

r3= AND - what2۰ r2, (no - 2)

r2 = (P - 1)۰(what - 1) - what1AND (no - 1)

Overriding the value of rn-1 from (2) to (1) we get

1 = (1 + whatn-1۰whatn-2rn-2 - whatn-1۰rn-3

and substituting in this equality the value of rn-2 from (3) we get

rno = - (whatn-3 + whatn-1۰whatn-2۰whatn-3 + whatn-1rn-3 + (1 + whatn-1۰whatn-2rn-4.

So we proceed successively until we get the integer at the end D such that

AND۰D ≡ 1 (mod (P -1)۰(what - 1)).

In our example we have:

N = 2.537 = 43۰59, P = 43, what = 59 and (P - 1)۰(what - 1) = 42۰58 = 2,436 and AND = 13.

Using Euclid's Algorithm to determine the MDC between (P - 1)۰(what - 1) = 2,436 and AND = 13 we get:

2.436 = 187۰13 + 5, 13 = 2۰5 + 3, 5 = 1۰3 + 2, 3 = 1۰2 + 1.

Now, using Euclid's Algorithm in reverse, we get:

1 = 3 - 1۰2, 2 = 5 - 1۰3, 3 = 13 - 2۰5, 5 = 2436 - 187۰13

Therefore, substituting as explained above, we have:

1 = 3 - 1۰2 = 3 - 1۰( 5 - 1۰3) = 3 - 1۰5 + 1۰3 = - 5 + 2۰3;

1 = - 5 + 2۰3 = - 5 + 2۰( 13 - 2۰5) = - 5 + 2۰13 - 4۰5 = 2۰13 - 5۰5;

1 = 2۰13 - 5۰5 = 2۰13 - 5۰( 2.436 - 187۰13) = 2۰13 - 5۰2.436 + 935.۰13 =

= 937۰13 - 5۰2.436.

Thus we get 1 = 937۰13 - 5۰2.436 which implies 937۰13 = 5۰2.436 +1.

Therefore, 13۰937 ≡ 1 (mod 2.436), ie AND37937 ≡ 1 (mod (P -1)۰(what - 1)).

We concluded that D = 937.

In the next column we will decode the message.

Back to columns

<