Selection of RSA cipher parameters and possible consequences
Under the cat are described examples of the choice of "bad" parameters of the RSA cipher.
Let us quote the authors of the textbook “Fundamentals of Cryptography” by A.P. Alferov, A.Yu. Zubov, A.S. Kuzmin, A.V. Cheryomushkin, Moscow. Helios ARV, 2001, on page 316:
“It is necessary to emphasize the need for caution in choosing the RSA module ( n numbers) for each correspondent in the network. In this regard, we can say the following. The reader can verify for himself that knowing one of the three values of p , q or φ (n) , you can easily find the RSA secret key ... ".
')
Let's add this text. If the RSA cipher module is unsuccessful, as is done in the example of the manual below, you can decrypt the text without having a secret key, i.e. without knowing any of these three quantities.
To do this, it is enough to have the cipher text specified by the cipher module n , the public key e of the cipher and perform only three steps of the “keyless reading” attack. After the fourth attacking step, it is established that at the previous step the source code was received, it can be read. We show how easy it is.
First we give an example from pp. 313-315 of the mentioned manual.
Short source text message encryption : RSA .
The recipient sets a cipher with the characteristics n = pq = 527 , where p = 17 , q = 31 and φ (n) = (p –1) (q - 1) = 480 . As a public key, e is a number that is mutually simple with φ (n) , e = 7 . For this number, using the Euclidean extended algorithm, the integers u and v are found that satisfy the relation e ∙ u + φ (n) v = 1 :
480 = 7 ∙ 68 + 4,
7 = 4 ∙ 1 + 3,
4 = 3 ∙ 1 + 1,
1 = 4–3 ∙ 1 = 4– (7–4 ∙ 1) ∙ 1 = 4 2–7 ∙ 1 = (480–7 ∙ 68) 2–7 1 = 480 2–7 137,
v = 2, u = –137 .
Since –137≡343 (mod480) , then d = 343 .
Check: 7 ∙ 343 = 2401≡1 (mod480) .
A text message is represented as a sequence of numbers contained in the interval [0, 526] . For this, the letters R , S, and A are encoded with five-digit binary numbers. The sequence numbers of these letters in the English alphabet are used for their binary representation:
R = 18 10 = (10010) 2 , S = 19 10 = (10011) 2 ,
A = 1 10 = (00001) 2 .
Then RSA = (100101001100001) 2 . Splitting text into blocks of limited length gives an idea of two blocks: RSA = (100101001), (100001) = (M 1 = 297, M 2 = 33) .
Blocks of the source text M 1 = 297 , M 2 = 33 are sequentially encrypted:
y 1 = k ( 1 ) = 1 e ≡297 7 (mod527) = 474 .
It took advantage of the fact that:
297 7 = ((297 2 ) 3 ) 297≡ (mod527) = (200 3 (mod527) 297) (mod527) = 474 ,
y 2 = k ( 2 ) = M 2 e ≡33 7 (mod527) = 407 .
The cipher text, as well as the source, is obtained in the form of two blocks: 1 = 474 ; y 2 = 407 .
Decryption is represented by a sequence of actions D k (y i ) = (y i ) d = (y i ) 343 (mod 527) , i = 1,2 .
It is more convenient to carry out calculations of raising to the power d by first representing the exponent by the sum of the powers of 2 , namely: 343 = 256 + 64 + 16 + 4 + 2 + 1 .
Using this representation of the exponent d = 343 , we get:
474 2 ≡ 174 (mod527),
474 4 ≡ 237 (mod527),
474 8 ≡307 (mod527),
474 16 ≡ 443 (mod527),
474 32 ≡205 (mod527),
474 64 ≡392 (mod527),
474,128 ≡307 (mod527),
474,256 ≡443 (mod527),
and finally 474,343 (mod527) = (443 ∙ 392 443 ∙ 237 ∙ 174 ∙ 474) (mod527) = 297 .
Similarly, the value 407 343 (mod527) = 33 is calculated.
The transition to the letter representation of the decrypted message gives: RSA .
After reviewing the example, the handbook discusses the resilience of the RSA system. It emphasizes the need for caution in choosing the RSA cipher module ( n numbers) for each of the network correspondents. Indicates the inadmissibility of ignoring the requirements for the selected characteristics of the encryption system. Among such requirements, unfortunately, is not specified the violation of which is illustrated by the given example.
Consider an example of an attack on the RSA cipher. We will use the data of the example given on page 313-315 in the textbook "Fundamentals of Cryptography" by A.P. Alferov, A.Yu. Zubov, A.S. Kuzmin, A.V. Cheryomushkin, Moscow. Helios ARV, 2001.
The failure (inadmissibility) of the selected system parameters in this example is easily shown by calculations that implement the attack of the keyless reading of the source text. The essence of such an attack is as follows. The public key of the RSA cipher ( = 7 , n = 527 ) and the cipher text are given. In the example, the cipher text is represented by two blocks.
y = (y 1 = 474, y 2 = 407) .
Each encrypted block is attacked individually, first we attack at 1 = 474 , after decrypting it, we attack another block at 2 = 407 .
Further, it is formed by repeated encryption with preservation of the results of two successive steps of the attack algorithm and using the public key a sequence of numerical values for i , for 1 = for the existing ciphertext.
In the cipher text attack algorithm, the step number j is defined for which y i e j (mod n) = (y i e j – 1 (mod n)) e (mod n) = y i , i> 1 . From the last relation, we see that when raising to the power e the value (y i e j – 1 (mod n)) we get the initial code text y i = y 1 .
But this means that the plaintext was encrypted at this step. By direct calculations (there are very few of them) using the on-screen calculator, we find the value j , at which the encryption cycle ends with the value y 1 , from which the cycle was started.
Attack on the first block at 1 = 474 ciphertext.
Step 1 : 474 7 (mod527) = 382 ;
Step 2 : 382 7 (mod527) = 423 ;
Step 3 : 423 7 (mod527) = 297 ;
Step 4 : in this step, the already found source code is encrypted, but it must be performed, because the attacker does not know the source text. A sign of the completion of the attack is the coincidence of the initial value of the ciphertext ( 474 ) and the result of the 4th step of encryption. It is such a coincidence that takes place.
297 7 (mod527) = 474 received the initial (first) ciphertext block. The attack on the first block was completed successfully at 1 = 474 . The preceding result of step 3 is the plaintext M 1 = 297 .
Essentially, in the residue ring modulo n = 527 , a short cycle of processing the residue r = 297 modulo n = 527 was realized. This is written as y i = y 1 = 297 . Form power deductions
(((297 7 (mod527)) 7 (mod527)) 7 (mod527)) 7 = 297 .
Attack on the second block at 2 = 407 ciphertext.
Step 1 : 407 7 (mod527) = 16 ;
Step 2 : 16 7 (mod527) = 101 ;
Step 3 : 101 7 (mod527) = 33 ;
Step 4 : 33 7 (mod527) = 407 .
Again, in the third step, the source text block ( M 2 = 33 ) was obtained, but the attacker is unknown, and he performs the next (fourth step), the result of which ( 407 ) coincides with the initial ciphertext at 2 = 407 .
Essentially, in the residue ring modulo n = 527 , a short cycle of processing the residue r = 33 modulo n = 527 was realized. This is written as y i = y 2 = 33 .
We form power residues ((33 7 (mod527)) 7 (mod527)) 7 (mod527) = 33 .
The result of the attack (source text M 1 = 297 , M 2 = 33 ) was obtained by triple encryption of the given ciphertext. Greater success for the attacker ciphertext is hard to imagine.
Continuing the discussion on the choice of the module and other parameters of the cipher, you can add that the cipher module ( n = 527 ) does not allow any ciphers to be encrypted at all. At the same time, the choice of the public key value is not important. There are source code values that cannot be encrypted at all with the selected cipher with the n = 527 module.
None of the specified e can not encrypt the source code, represented by numbers
187 , 341 , 154 and 373 .
Let the source texts be represented by four blocks y = (y 1 = 154, y 2 = 187, y 3 = 341, y 4 = 373) . The cipher public key exponent e can be any mutually simple number with the Euler function φ (n) = φ (527) = 480 . However, for the case in question, the public key e can be set arbitrarily. Indeed, let e = 2, 4, 7, 9, 17, 111 then:
154 2 (mod527) = 1 ;
154 4 (mod527) = 1 ;
154 7 (mod527) = 154 ;
154 9 (mod527) = 154 ;
154 17 (mod527) = 154 ;
154 111 (mod527) = 154 ;
187 2 (mod527) = 187 ;
187 4 (mod527) = 187 ;
187 7 (mod527) = 187 ;
187 9 (mod527) = 187 ;
187 17 (mod527) = 187 ;
187,111 (mod527) = 187 ;
341 2 (mod527) = 341 ;
341 4 (mod527) = 1 ;
341 7 (mod527) = 341 ;
341 9 (mod527) = 341 ;
341 17 (mod527) = 341 ;
341 111 (mod527) = 341 ;
373 2 (mod527) = 1 ;
373 4 (mod527) = 373 ;
373 7 (mod527) = 373 ;
373 9 (mod527) = 373 ;
373 17 (mod527) = 373 ;
373,111 (mod527) = 373 .
From the considered example follows a simple conclusion. Indeed, the choice of the parameters of the encryption process must be approached very carefully and a thorough preliminary analysis of such parameters must be carried out. How to do this is a separate issue, and in the framework of this work it is not considered.
Let us quote the authors of the textbook “Fundamentals of Cryptography” by A.P. Alferov, A.Yu. Zubov, A.S. Kuzmin, A.V. Cheryomushkin, Moscow. Helios ARV, 2001, on page 316:
“It is necessary to emphasize the need for caution in choosing the RSA module ( n numbers) for each correspondent in the network. In this regard, we can say the following. The reader can verify for himself that knowing one of the three values of p , q or φ (n) , you can easily find the RSA secret key ... ".
')
Let's add this text. If the RSA cipher module is unsuccessful, as is done in the example of the manual below, you can decrypt the text without having a secret key, i.e. without knowing any of these three quantities.
To do this, it is enough to have the cipher text specified by the cipher module n , the public key e of the cipher and perform only three steps of the “keyless reading” attack. After the fourth attacking step, it is established that at the previous step the source code was received, it can be read. We show how easy it is.
First we give an example from pp. 313-315 of the mentioned manual.
Example
Short source text message encryption : RSA .
The recipient sets a cipher with the characteristics n = pq = 527 , where p = 17 , q = 31 and φ (n) = (p –1) (q - 1) = 480 . As a public key, e is a number that is mutually simple with φ (n) , e = 7 . For this number, using the Euclidean extended algorithm, the integers u and v are found that satisfy the relation e ∙ u + φ (n) v = 1 :
480 = 7 ∙ 68 + 4,
7 = 4 ∙ 1 + 3,
4 = 3 ∙ 1 + 1,
1 = 4–3 ∙ 1 = 4– (7–4 ∙ 1) ∙ 1 = 4 2–7 ∙ 1 = (480–7 ∙ 68) 2–7 1 = 480 2–7 137,
v = 2, u = –137 .
Since –137≡343 (mod480) , then d = 343 .
Check: 7 ∙ 343 = 2401≡1 (mod480) .
A text message is represented as a sequence of numbers contained in the interval [0, 526] . For this, the letters R , S, and A are encoded with five-digit binary numbers. The sequence numbers of these letters in the English alphabet are used for their binary representation:
R = 18 10 = (10010) 2 , S = 19 10 = (10011) 2 ,
A = 1 10 = (00001) 2 .
Then RSA = (100101001100001) 2 . Splitting text into blocks of limited length gives an idea of two blocks: RSA = (100101001), (100001) = (M 1 = 297, M 2 = 33) .
Blocks of the source text M 1 = 297 , M 2 = 33 are sequentially encrypted:
y 1 = k ( 1 ) = 1 e ≡297 7 (mod527) = 474 .
It took advantage of the fact that:
297 7 = ((297 2 ) 3 ) 297≡ (mod527) = (200 3 (mod527) 297) (mod527) = 474 ,
y 2 = k ( 2 ) = M 2 e ≡33 7 (mod527) = 407 .
The cipher text, as well as the source, is obtained in the form of two blocks: 1 = 474 ; y 2 = 407 .
Decryption is represented by a sequence of actions D k (y i ) = (y i ) d = (y i ) 343 (mod 527) , i = 1,2 .
It is more convenient to carry out calculations of raising to the power d by first representing the exponent by the sum of the powers of 2 , namely: 343 = 256 + 64 + 16 + 4 + 2 + 1 .
Using this representation of the exponent d = 343 , we get:
474 2 ≡ 174 (mod527),
474 4 ≡ 237 (mod527),
474 8 ≡307 (mod527),
474 16 ≡ 443 (mod527),
474 32 ≡205 (mod527),
474 64 ≡392 (mod527),
474,128 ≡307 (mod527),
474,256 ≡443 (mod527),
and finally 474,343 (mod527) = (443 ∙ 392 443 ∙ 237 ∙ 174 ∙ 474) (mod527) = 297 .
Similarly, the value 407 343 (mod527) = 33 is calculated.
The transition to the letter representation of the decrypted message gives: RSA .
After reviewing the example, the handbook discusses the resilience of the RSA system. It emphasizes the need for caution in choosing the RSA cipher module ( n numbers) for each of the network correspondents. Indicates the inadmissibility of ignoring the requirements for the selected characteristics of the encryption system. Among such requirements, unfortunately, is not specified the violation of which is illustrated by the given example.
RSA attack
Consider an example of an attack on the RSA cipher. We will use the data of the example given on page 313-315 in the textbook "Fundamentals of Cryptography" by A.P. Alferov, A.Yu. Zubov, A.S. Kuzmin, A.V. Cheryomushkin, Moscow. Helios ARV, 2001.
The failure (inadmissibility) of the selected system parameters in this example is easily shown by calculations that implement the attack of the keyless reading of the source text. The essence of such an attack is as follows. The public key of the RSA cipher ( = 7 , n = 527 ) and the cipher text are given. In the example, the cipher text is represented by two blocks.
y = (y 1 = 474, y 2 = 407) .
Each encrypted block is attacked individually, first we attack at 1 = 474 , after decrypting it, we attack another block at 2 = 407 .
Further, it is formed by repeated encryption with preservation of the results of two successive steps of the attack algorithm and using the public key a sequence of numerical values for i , for 1 = for the existing ciphertext.
In the cipher text attack algorithm, the step number j is defined for which y i e j (mod n) = (y i e j – 1 (mod n)) e (mod n) = y i , i> 1 . From the last relation, we see that when raising to the power e the value (y i e j – 1 (mod n)) we get the initial code text y i = y 1 .
But this means that the plaintext was encrypted at this step. By direct calculations (there are very few of them) using the on-screen calculator, we find the value j , at which the encryption cycle ends with the value y 1 , from which the cycle was started.
Attack on the first block at 1 = 474 ciphertext.
Step 1 : 474 7 (mod527) = 382 ;
Step 2 : 382 7 (mod527) = 423 ;
Step 3 : 423 7 (mod527) = 297 ;
Step 4 : in this step, the already found source code is encrypted, but it must be performed, because the attacker does not know the source text. A sign of the completion of the attack is the coincidence of the initial value of the ciphertext ( 474 ) and the result of the 4th step of encryption. It is such a coincidence that takes place.
297 7 (mod527) = 474 received the initial (first) ciphertext block. The attack on the first block was completed successfully at 1 = 474 . The preceding result of step 3 is the plaintext M 1 = 297 .
Essentially, in the residue ring modulo n = 527 , a short cycle of processing the residue r = 297 modulo n = 527 was realized. This is written as y i = y 1 = 297 . Form power deductions
(((297 7 (mod527)) 7 (mod527)) 7 (mod527)) 7 = 297 .
Attack on the second block at 2 = 407 ciphertext.
Step 1 : 407 7 (mod527) = 16 ;
Step 2 : 16 7 (mod527) = 101 ;
Step 3 : 101 7 (mod527) = 33 ;
Step 4 : 33 7 (mod527) = 407 .
Again, in the third step, the source text block ( M 2 = 33 ) was obtained, but the attacker is unknown, and he performs the next (fourth step), the result of which ( 407 ) coincides with the initial ciphertext at 2 = 407 .
Essentially, in the residue ring modulo n = 527 , a short cycle of processing the residue r = 33 modulo n = 527 was realized. This is written as y i = y 2 = 33 .
We form power residues ((33 7 (mod527)) 7 (mod527)) 7 (mod527) = 33 .
The result of the attack (source text M 1 = 297 , M 2 = 33 ) was obtained by triple encryption of the given ciphertext. Greater success for the attacker ciphertext is hard to imagine.
Continuing the discussion on the choice of the module and other parameters of the cipher, you can add that the cipher module ( n = 527 ) does not allow any ciphers to be encrypted at all. At the same time, the choice of the public key value is not important. There are source code values that cannot be encrypted at all with the selected cipher with the n = 527 module.
None of the specified e can not encrypt the source code, represented by numbers
187 , 341 , 154 and 373 .
Example (inability to encrypt the values of some source texts)
Let the source texts be represented by four blocks y = (y 1 = 154, y 2 = 187, y 3 = 341, y 4 = 373) . The cipher public key exponent e can be any mutually simple number with the Euler function φ (n) = φ (527) = 480 . However, for the case in question, the public key e can be set arbitrarily. Indeed, let e = 2, 4, 7, 9, 17, 111 then:
154 2 (mod527) = 1 ;
154 4 (mod527) = 1 ;
154 7 (mod527) = 154 ;
154 9 (mod527) = 154 ;
154 17 (mod527) = 154 ;
154 111 (mod527) = 154 ;
187 2 (mod527) = 187 ;
187 4 (mod527) = 187 ;
187 7 (mod527) = 187 ;
187 9 (mod527) = 187 ;
187 17 (mod527) = 187 ;
187,111 (mod527) = 187 ;
341 2 (mod527) = 341 ;
341 4 (mod527) = 1 ;
341 7 (mod527) = 341 ;
341 9 (mod527) = 341 ;
341 17 (mod527) = 341 ;
341 111 (mod527) = 341 ;
373 2 (mod527) = 1 ;
373 4 (mod527) = 373 ;
373 7 (mod527) = 373 ;
373 9 (mod527) = 373 ;
373 17 (mod527) = 373 ;
373,111 (mod527) = 373 .
From the considered example follows a simple conclusion. Indeed, the choice of the parameters of the encryption process must be approached very carefully and a thorough preliminary analysis of such parameters must be carried out. How to do this is a separate issue, and in the framework of this work it is not considered.
Source: https://habr.com/ru/post/224523/
All Articles