# Choosing 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

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

First, we give the example itself with pages 313-315 from the above manual.

The recipient sets the code with the characteristics

Since

Check:

A text message is presented as a sequence of numbers contained in the interval

Then

The blocks of the source text

Here we took advantage of the fact that:

The cipher text as the original, we obtain in the form of two blocks:

Calculations exponentiation

Using this representation of the exponent

and finally

The value

The transition to the alphabetic representation of the decrypted message gives:

After examining the example, the manual discusses the stability of the RSA system. The need for caution in choosing the RSA cipher module (number

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 (

Each encrypted block is attacked individually, first we attack

Далее формируется путем многократного зашифрования с сохранением результатов двух последовательных шагов алгоритма атаки и с использованием открытого ключа последовательность числовых значений

В алгоритме атаки на шифрованный текст определяется такой номер шага

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

Substantially in the ring of residues modulo

Again, in the third step, the source text block was received (

Substantially in the ring of residues modulo

We form power residues

The result of the attack (source text

Continuing the discussion of the choice of the module and other parameters of the cipher, we can add that the cipher module (

None of the given e can encrypt the source texts represented by the numbers

Let the source texts be represented by four blocks

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.

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)**. Splitting text into blocks of limited length gives a view of two blocks:

_{2}**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 encryptedHere we took advantage of the fact that:

**297**,

^{7}= ((297^{2})^{3}) 297≡ (mod527) = (200^{3}(mod527) 297) (mod527) = 474**y**.

_{2}= E_{k}(M_{2}) = M_{2 }^{e}≡33^{7}(mod527) = 407The 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

**d**it 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**

474

474

474

474

474

474

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) = 297The value

**407**calculated in the same way .

^{343}(mod527) = 33 isThe 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**, для которого

**y**,

_{i}^{ej}(mod n)=(y_{i}^{ej–1}(mod n))^{e}(mod n)=y_{i}**i>1**. From the last relation we see that when raising to a power of

**e the**value

**(y**, the initial ciphertext

_{i }^{e j – 1}(mod n))**y**obtained .

_{i}= y_{1 is}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**, from which the cycle was started.

_{1}*Attack on the first block*

**at**ciphertext._{1}= 474**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**received the initial (first) ciphertext block. The attack on the first block was completed successfully

^{7}(mod527) = 474**at**. The previous result of step 3 is equal to the plaintext

_{1}= 474**M**.

_{1}= 297Substantially in the ring of residues modulo

**n = 527**realized short processing cycle subtracting

**r = 297**modulo

**n = 527**. This is written as

**y**. We form power residues

_{i}= y_{1}= 297**(((297**.

^{7}(mod527))^{7}(mod527))^{7}(mod527))^{7}= 297*Attack on the second block*

**at**ciphertext._{2}= 407**Step 1**:

**407**;

^{7}(mod527) = 16**Step 2**:

**16**;

^{7}(mod527) = 101**Step 3**:

**101**;

^{7}(mod527) = 33**Step 4**:

**33**.

^{7}(mod527) = 407Again, in the third step, the source text block was received (

**M**), but this is not known to the attacker, and he performs the next (fourth step), the result of which (

_{2}= 33**407**) coincides with the initial ciphertext

**for**.

_{2}= 407Substantially 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}= 33We form power residues

**((33**.

^{7}(mod527))^{7}(mod527))^{7}(mod527) = 33The result of the attack (source text

**M**,

_{1}= 297**M**) was obtained by triple encryption of the given ciphertext. Greater success for an attacker ciphertext is hard to imagine.

_{2}= 33Continuing 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 module

**n = 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**. The exponent

_{1}= 154, y_{2}= 187, y_{3}= 341, y_{4}= 373)**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**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) = 373A 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.