May 29, 2014 at 12:13Choosing RSA Cipher Settings and Possible Consequences
Under the cut, examples of selecting “bad” RSA cipher parameters are described.
We quote the authors of the textbook "Fundamentals of Cryptography" A.P. Alferov, A.Yu. Zubov, A.S. Kuzmin, A.V. Cheremushkin, Moscow. Helios ARV, 2001, on page 316:
“The need to be careful in choosing the RSA module (number n ) for each of the network correspondents should be emphasized . In this regard, the following can be said. The reader can independently verify that knowing one of the three values p , q or φ (n) , one can easily find the RSA secret key ... ”
Supplement this text. If the RSA cipher module is unsuccessfully selected, as was done in the example of the manual below, you can decrypt the text even without a secret key, i.e. not knowing any of the three named quantities.
To do this, it is enough to have the ciphertext specified by the cipher module n , the cipher public key e and perform only three steps of the “keyless reading” attack. After the fourth attacking step, it is established that in the previous step the source code was received, it can be read. We show how easy it is.
First, we give the example itself with pages 313-315 from the above manual.
Encryption of Short Source Text Message: RSA .
The recipient sets the code with the characteristics n = pq = 527 , where p = 17 , q = 31 and φ (n) = (p –1) (q - 1) = 480 . As a public key e, a number is chosen that is coprime to φ (n) , e = 7 . For this number, using the extended Euclidean algorithm, 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 presented 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 serial numbers of these letters in the English alphabet are used in 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 a view of two blocks: RSA = (100101001), (100001) = (M 1 = 297, M 2 = 33) .
The blocks of the source text M 1 = 297 , M 2 = 33 :
y 1 = Е k (M 1 ) = M 1 e ≡297 7 (mod527) = 474 are sequentially encrypted .
Here we took advantage of the fact that:
297 7 = ((297 2 ) 3 ) 297≡ (mod527) = (200 3 (mod527) 297) (mod527) = 474 ,
y2 = E k (M 2 ) = M 2 e ≡33 7 (mod527) = 407 .
The cipher text as the original, we obtain in the form of two blocks: y 1 = 474 ; y 2 = 407 .
Decryption is represented by the sequence of actions D k (y i ) = (y i ) d = (y i ) 343 (mod 527) , i = 1,2 .
Calculations exponentiation dit is more convenient to carry out, previously representing the exponent by the sum of the degrees of the number 2 , namely: 343 = 256 + 64 + 16 + 4 + 2 + 1 .
Using this representation of the exponent d = 343 , we obtain:
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 .
The value 407 343 (mod527) = 33 is calculated in the same way .
The transition to the alphabetic representation of the decrypted message gives: RSA .
After examining the example, the manual discusses the stability of the RSA system. The need for caution in choosing the RSA cipher module (number n ) for each of the network correspondents is emphasized . Indicates the inadmissibility of ignoring the requirements for the selected characteristics of the encryption system. Among such requirements, unfortunately, is not indicated the violation of which the given example illustrates.
Consider an example of an attack on an RSA cipher. We will use the data of the example given on page 313-315 in the training manual “Fundamentals of Cryptography” A.P. Alferov, A.Yu. Zubov, A.S. Kuzmin, A.V. Cheremushkin, 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 keyless reading of the source text. The essence of such an attack is as follows. The RSA cipher public key ( e = 7 , n = 527 ) and encrypted text are specified. In the example, the ciphertext is represented by two blocks
y = (y 1 = 474, y 2 = 407) .
Each encrypted block is attacked individually, first we attack at 1 = 474, после его дешифрования, атакуем другой блок у2=407.
Далее формируется путем многократного зашифрования с сохранением результатов двух последовательных шагов алгоритма атаки и с использованием открытого ключа последовательность числовых значений уi, у1=у имеющийся шифрованный текст.
В алгоритме атаки на шифрованный текст определяется такой номер шага j, для которого yiej(mod n)=(yiej–1(mod n))e(mod n)=yi, i>1. From the last relation we see that when raising to a power of e the value (y i e j – 1 (mod n)) , the initial ciphertext y i = y 1 is obtained .
But this also means that plain text was encrypted at this step. By direct calculations (there are very few of them) using the on-screen calculator, we find the value of 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 : at this step, the already found source text is encrypted, but it must be completed since the attacker does not know the source text. A sign of the completion of the attack is the coincidence of the initial ciphertext value ( 474 ) and the result of the 4th encryption step. 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 previous result of step 3 is equal to the plaintext M1 = 297 .
Substantially in the ring of residues modulo n = 527 realized short processing cycle subtracting r = 297 modulo n = 527 . This is written as y i = y 1 = 297 . We form power residues
(((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 was received ( M 2 = 33 ), but this is not known to the attacker, and he performs the next (fourth step), the result of which ( 407 ) coincides with the initial ciphertext for 2 = 407 .
Substantially in the ring of residues modulo n = 527 realized short processing cycle subtracting r = 33 modulo n = 527 . 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 an attacker ciphertext is hard to imagine.
Continuing the discussion of the choice of the module and other parameters of the cipher, we can add that the cipher module ( n = 527 ) does not allow encryption of some source texts at all. Moreover, the choice of the value of the public key e does not play a big role. There are values of the source texts that are generally impossible to encrypt with the selected cipher with the modulen = 527 .
None of the given e can encrypt the source texts represented by the 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 exponent e of the cipher public key can be any coprime number with the Euler function φ (n) = φ (527) = 480 . However, for the case under consideration, 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 ;
34117 (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 .
A simple conclusion follows from the considered example. Indeed, the choice of parameters for the encryption process must be approached very carefully and a thorough preliminary analysis of such parameters should be carried out. How to do this is a separate issue, and it is not considered in the framework of this work.
We quote the authors of the textbook "Fundamentals of Cryptography" A.P. Alferov, A.Yu. Zubov, A.S. Kuzmin, A.V. Cheremushkin, Moscow. Helios ARV, 2001, on page 316:
“The need to be careful in choosing the RSA module (number n ) for each of the network correspondents should be emphasized . In this regard, the following can be said. The reader can independently verify that knowing one of the three values p , q or φ (n) , one can easily find the RSA secret key ... ”
Supplement this text. If the RSA cipher module is unsuccessfully selected, as was done in the example of the manual below, you can decrypt the text even without a secret key, i.e. not knowing any of the three named quantities.
To do this, it is enough to have the ciphertext specified by the cipher module n , the cipher public key e and perform only three steps of the “keyless reading” attack. After the fourth attacking step, it is established that in the previous step the source code was received, it can be read. We show how easy it is.
First, we give the example itself with pages 313-315 from the above manual.
Example
Encryption of Short Source Text Message: RSA .
The recipient sets the code with the characteristics n = pq = 527 , where p = 17 , q = 31 and φ (n) = (p –1) (q - 1) = 480 . As a public key e, a number is chosen that is coprime to φ (n) , e = 7 . For this number, using the extended Euclidean algorithm, 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 presented 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 serial numbers of these letters in the English alphabet are used in 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 a view of two blocks: RSA = (100101001), (100001) = (M 1 = 297, M 2 = 33) .
The blocks of the source text M 1 = 297 , M 2 = 33 :
y 1 = Е k (M 1 ) = M 1 e ≡297 7 (mod527) = 474 are sequentially encrypted .
Here we took advantage of the fact that:
297 7 = ((297 2 ) 3 ) 297≡ (mod527) = (200 3 (mod527) 297) (mod527) = 474 ,
y2 = E k (M 2 ) = M 2 e ≡33 7 (mod527) = 407 .
The cipher text as the original, we obtain in the form of two blocks: y 1 = 474 ; y 2 = 407 .
Decryption is represented by the sequence of actions D k (y i ) = (y i ) d = (y i ) 343 (mod 527) , i = 1,2 .
Calculations exponentiation dit is more convenient to carry out, previously representing the exponent by the sum of the degrees of the number 2 , namely: 343 = 256 + 64 + 16 + 4 + 2 + 1 .
Using this representation of the exponent d = 343 , we obtain:
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 .
The value 407 343 (mod527) = 33 is calculated in the same way .
The transition to the alphabetic representation of the decrypted message gives: RSA .
After examining the example, the manual discusses the stability of the RSA system. The need for caution in choosing the RSA cipher module (number n ) for each of the network correspondents is emphasized . Indicates the inadmissibility of ignoring the requirements for the selected characteristics of the encryption system. Among such requirements, unfortunately, is not indicated the violation of which the given example illustrates.
Attack on RSA Cipher
Consider an example of an attack on an RSA cipher. We will use the data of the example given on page 313-315 in the training manual “Fundamentals of Cryptography” A.P. Alferov, A.Yu. Zubov, A.S. Kuzmin, A.V. Cheremushkin, 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 keyless reading of the source text. The essence of such an attack is as follows. The RSA cipher public key ( e = 7 , n = 527 ) and encrypted text are specified. In the example, the ciphertext is represented by two blocks
y = (y 1 = 474, y 2 = 407) .
Each encrypted block is attacked individually, first we attack at 1 = 474, после его дешифрования, атакуем другой блок у2=407.
Далее формируется путем многократного зашифрования с сохранением результатов двух последовательных шагов алгоритма атаки и с использованием открытого ключа последовательность числовых значений уi, у1=у имеющийся шифрованный текст.
В алгоритме атаки на шифрованный текст определяется такой номер шага j, для которого yiej(mod n)=(yiej–1(mod n))e(mod n)=yi, i>1. From the last relation we see that when raising to a power of e the value (y i e j – 1 (mod n)) , the initial ciphertext y i = y 1 is obtained .
But this also means that plain text was encrypted at this step. By direct calculations (there are very few of them) using the on-screen calculator, we find the value of 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 : at this step, the already found source text is encrypted, but it must be completed since the attacker does not know the source text. A sign of the completion of the attack is the coincidence of the initial ciphertext value ( 474 ) and the result of the 4th encryption step. 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 previous result of step 3 is equal to the plaintext M1 = 297 .
Substantially in the ring of residues modulo n = 527 realized short processing cycle subtracting r = 297 modulo n = 527 . This is written as y i = y 1 = 297 . We form power residues
(((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 was received ( M 2 = 33 ), but this is not known to the attacker, and he performs the next (fourth step), the result of which ( 407 ) coincides with the initial ciphertext for 2 = 407 .
Substantially in the ring of residues modulo n = 527 realized short processing cycle subtracting r = 33 modulo n = 527 . 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 an attacker ciphertext is hard to imagine.
Continuing the discussion of the choice of the module and other parameters of the cipher, we can add that the cipher module ( n = 527 ) does not allow encryption of some source texts at all. Moreover, the choice of the value of the public key e does not play a big role. There are values of the source texts that are generally impossible to encrypt with the selected cipher with the modulen = 527 .
None of the given e can encrypt the source texts represented by the numbers
187 , 341 , 154 and 373 .
Example (the impossibility of encrypting 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 exponent e of the cipher public key can be any coprime number with the Euler function φ (n) = φ (527) = 480 . However, for the case under consideration, 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 ;
34117 (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 .
A simple conclusion follows from the considered example. Indeed, the choice of parameters for the encryption process must be approached very carefully and a thorough preliminary analysis of such parameters should be carried out. How to do this is a separate issue, and it is not considered in the framework of this work.