RSA

RSA
	RSA
Named after	, and
Publication Date
A formula describing a law or theorem

RSA (an abbreviation for the names Rivest, Shamir and Adleman) is a public-key cryptographic algorithm based on the computational complexity of the large integer factorization problem .

The RSA cryptosystem was the first system suitable for both encryption and digital signature . The algorithm is used in a large number of cryptographic applications, including PGP , S / MIME , TLS / SSL , IPSEC / IKE and others ^[3] .

Content

1 History
2 Description of the algorithm
- 2.1 Introduction
- 2.2 Algorithm for creating public and private keys
- 2.3 Encryption and decryption
- 2.4 Session Key Encryption Algorithm
- 2.5 Correctness of the RSA circuit
- 2.6 Example
3 Digital Signature
4 RSA algorithm speed
- 4.1 Using the Chinese remainder theorem to speed up decryption
5 RSA Cryptanalysis
6 Attacks on the RSA Algorithm
- 6.1 Wiener attack on RSA
- 6.2 Generalized Wiener attack
7 RSA Application
8 Notes
9 Literature

History

Published in November 1976, an article by Whitfield Diffie and Martin Hellman, New Directions in Cryptography ^[4], transformed the concept of cryptographic systems, laying the foundation for public-key cryptography . The subsequently developed Diffie-Hellman algorithm allowed the two parties to obtain a shared secret key using an insecure communication channel. However, this algorithm did not solve the authentication problem. Without additional funds, users could not be sure with whom exactly they generated the shared secret key.

After studying this article, three scientists Ronald Rivest , Adi Shamir and Leonard Adleman from the Massachusetts Institute of Technology (MIT) proceeded to search for a mathematical function that would allow implementing the public key cryptographic system model formulated by Whitfield Diffie and Martin Hellman . After working on more than 40 possible options, they managed to find an algorithm based on the difference in how easy it is to find large primes and how difficult it is to factor the product of two large primes, later called RSA. The system was named after the first letters of the names of its creators.

In August 1977, in the column “Mathematical Games” by Martin Gardner in Scientific American , with the permission of Ronald Rivest ^[5] , the first description of the RSA cryptosystem ^{[6] appeared} . Readers were also asked to decrypt the English phrase encrypted with the described algorithm:

9686
1477
8829
7431
0816
3569
8962
1829
9613
1409
0575
9874
2982
3147
8013
9451
7546
2225
9991
6951
2514
6622
3919
5781
2206
4355
1245
2093
5708
8839
9055
5154

As open parameters of the system, the numbers n =1143816 ... 6879541 (129 decimal places, 425 bits , also known as RSA-129 ) and e = 9007. For the decryption, a reward of $ 100 was promised. According to Rivest, it would take more than 40 quadrillion years to factor the number ^[7] ^[3] . However, after more than 15 years, on September 3, 1993, it was announced the launch of a distributed computing project with coordination via e-mail to find the factors of the number RSA-129 and solve the puzzle. For six months, more than 600 volunteers from 20 countries donated 1,600 machines (3 of which were fax machines) ). As a result, simple factors were found and the original message was decoded, which is the phrase “ THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE ” (“Magic words are a fastidious lamb ”) ^[8] ^[9] . The winners donated the award to the Free Software Foundation .

After the publication of Martin Gardner, anyone could get a full description of the new cryptosystem by sending a request by mail to Ronald Rivest with an envelope with a return address and stamps of 35 cents. ^[6] A full description of the new cryptosystem was published in the journal Communications of the ACM in February 1978 ^[10] .

The patent application was filed on December 14, 1977, MIT was indicated as the owner. Patent 4405829 was granted on September 20, 1983 , and on September 21, 2000 it expired ^[11] . However, outside the US, the inventors of the algorithm did not have a patent, since in most countries it was necessary to obtain it before the first publication ^[12] .

In 1982, Rivest, Shamir and Adleman formed the company RSA Data Security (currently - a division of EMC ). In 1989, RSA, along with the symmetric DES cipher, was mentioned in RFC 1115 , thereby starting to use the algorithm on the nascent Internet ^[13] , and in 1990 the US Department of Defense began using the algorithm ^[14] .

In November 1993, version 1.5 of the PKCS1 standard, which describes the use of RSA to encrypt and create an electronic signature, was openly published. The latest versions of the standard are also available as RFC ( RFC 2313 - 1.5, 1993; RFC 2437 - 2.0, 1998; RFC 3447 - 2.1, 2002).

In December 1997, information was released according to which the British mathematician Clifford Cocks, who worked at the Government Communications Center ( GCHQ ) of Great Britain , described a cryptosystem similar to RSA in 1973 ^[15] .

Algorithm Description

Introduction

Public key cryptographic systems use the so-called one - way functions , which have the following property:

if known $x$ ${\ displaystyle x}$ then $f(x)$ ${\ displaystyle f (x)}$ calculate is relatively simple;
if known $y=f(x)$ ${\ displaystyle y = f (x)}$ then to calculate $x$ ${\ displaystyle x}$ there is no easy (efficient) way.

One-sidedness is understood not as theoretical unidirectionality, but as the practical impossibility of calculating the inverse value, using modern computing tools, for a foreseeable time interval.

The RSA public key cryptographic system is based on the complexity of the problem of factorizing the product of two large prime numbers. For encryption, the operation of raising to a power modulo a large number is used. For decryption (reverse operation) in a reasonable time, it is necessary to be able to calculate the Euler function of a given large number, for which it is necessary to know the decomposition of the number into prime factors.

In a public key cryptographic system, each participant has both a public key ( public key ) and a private key ( private key ). In the RSA cryptographic system, each key consists of a pair of integers. Each participant creates their own public and private keys independently. Each of them keeps the private key secret, and public keys can be shared with anyone, or even published. The public and private keys of each messenger in the RSA cryptosystem form a “matched pair” in the sense that they are mutually inverse , that is:

\forall

{\ displaystyle \ forall}

valid pairs of public and private keys

(p,s)

{\ displaystyle (p, s)}

\exists

{\ displaystyle \ exists}

corresponding encryption functions

E_{p}(x)

{\ displaystyle E_ {p} (x)}

and decryption

D_{s}(x)

{\ displaystyle D_ {s} (x)}

such that

\forall

{\ displaystyle \ forall}

posts

m\in M

{\ displaystyle m \ in M}

where

M

{\ displaystyle M}

- many valid messages

m=D_{s}(E_{p}(m))=E_{p}(D_{s}(m)).

{\ displaystyle m = D_ {s} (E_ {p} (m)) = E_ {p} (D_ {s} (m)).}

Algorithm for creating public and private keys

RSA keys are generated as follows: ^[16]

Two different random primes are chosen $p$ ${\ displaystyle p}$ and $q$ ${\ displaystyle q}$ a given size (for example, 1024 bits each).
Their product is calculated $n=p\cdot q$ ${\ displaystyle n = p \ cdot q}$ called a module .
The value of the Euler function of the number is calculated $n$ ${\ displaystyle n}$ :
$\varphi (n)=(p-1)\cdot (q-1).$ ${\ displaystyle \ varphi (n) = (p-1) \ cdot (q-1).}$
Select integer $e$ {\ displaystyle e} ( $one$ $<$ $e$ $<$ $φ$ $($ $n$ $)$ {\ displaystyle 1 <e <\ varphi (n)} ), mutually prime with the function value $φ$ $($ $n$ $)$ {\ displaystyle \ varphi (n)} .
- Number $e$ ${\ displaystyle e}$ called an open exponent
- Usually as $e$ ${\ displaystyle e}$ they take primes containing a small number of unit bits in binary notation , for example, primes from Fermat numbers : 17, 257, or 65537, since in this case the time required for encryption using fast exponentiation will be less.
- Too small values $e$ ${\ displaystyle e}$ 3, for example, could potentially weaken the security of the RSA circuit. ^[17]
The number is calculated $d$ {\ displaystyle d} multiplicatively inverse to the number $e$ {\ displaystyle e} modulo $φ$ $($ $n$ $)$ {\ displaystyle \ varphi (n)} , that is, a number satisfying the comparison :
$d\cdot e\equiv 1{\pmod {\varphi (n)}}.$ ${\ displaystyle d \ cdot e \ equiv 1 {\ pmod {\ varphi (n)}}.}$
- Number $d$ ${\ displaystyle d}$ called a secret exponent . It is usually calculated using the extended Euclidean algorithm .
Couple $(e,n)$ ${\ displaystyle (e, n)}$ published as an RSA public key .
Couple $(d,n)$ ${\ displaystyle (d, n)}$ plays the role of the RSA private key ( RSA private key ) and is kept secret.

Encryption and Decryption

Suppose Bob wants to send Alice a message $m$ ${\ displaystyle m}$ .

Messages are integers ranging from $0$ ${\ displaystyle 0}$ before $n-1$ ${\ displaystyle n-1}$ i.e. $m\in \mathbb {Z} _{n}$ ${\ displaystyle m \ in \ mathbb {Z} _ {n}}$ .

Encryption Algorithm ^[16] :

Take the public key $(e,n)$ ${\ displaystyle (e, n)}$ Alice
Take plain text $m$ ${\ displaystyle m}$
Encrypt the message using Alice’s public key:
$c=E(m)=m^{e}\mod n~~~~(1)$ ${\ displaystyle c = E (m) = m ^ {e} \ mod n ~~~~ (1)}$

Decryption Algorithm :

Receive encrypted message $c$ ${\ displaystyle c}$
Take your private key $(d,n)$ ${\ displaystyle (d, n)}$
Apply the private key to decrypt the message:
$m=D(c)=c^{d}\mod n~~~~(2)$ {\ displaystyle m = D (c) = c ^ {d} \ mod n ~~~~ (2)}

This scheme is not used in practice due to the fact that it is not practically reliable (semantically secured). Indeed, the one-way function E (m) is deterministic - for the same values of the input parameters (key and message) it gives the same result. This means that the necessary condition for the practical (semantic) reliability of the cipher is not fulfilled.

Session Key Encryption Algorithm

The most used currently is a mixed encryption algorithm, in which the session key is first encrypted, and then with it, participants encrypt their messages with symmetric systems. After the session ends, the session key is usually destroyed.

The session key encryption algorithm is as follows ^[18] :

Algorithm :

Take the public key $(e,n)$ ${\ displaystyle (e, n)}$ Alice
Create a random session key $m$ ${\ displaystyle m}$
Encrypt the session key using Alice's public key:
$c=E(m)=m^{e}\mod n$ ${\ displaystyle c = E (m) = m ^ {e} \ mod n}$
Decrypt message $C$ ${\ displaystyle C}$ using a session key with a symmetric algorithm:
$M_{A}=D_{m}(C)$ ${\ displaystyle M_ {A} = D_ {m} (C)}$

Algorithm :

Accept Bob's encrypted session key $c$ ${\ displaystyle c}$
Take your private key $(d,n)$ ${\ displaystyle (d, n)}$
Apply the private key to decrypt the session key:
$m=D(c)=c^{d}\mod n$ ${\ displaystyle m = D (c) = c ^ {d} \ mod n}$
Encrypt message $M_{A}$ ${\ displaystyle M_ {A}}$ using a session key with a symmetric algorithm:
$C=E_{m}(M_{A})$ ${\ displaystyle C = E_ {m} (M_ {A})}$

In the case where the session key is larger than the module $n$ ${\ displaystyle n}$ , the session key is divided into blocks of the desired length (if necessary, supplemented with zeros) and each block is encrypted.

RSA circuit correctness

Equations

(one)

{\ displaystyle (1)}

and

(2)

{\ displaystyle (2)}

on which the RSA scheme is based determine mutually inverse transformations of the set

\mathbb {Z} _{n}

{\ displaystyle \ mathbb {Z} _ {n}}

Proof ^[16] ^[19]

Indeed, for $\forall m\in \mathbb {Z} _{n}$ ${\ displaystyle \ forall m \ in \ mathbb {Z} _ {n}}$

D\left({E\left(m\right)}\right)=E\left({D\left(m\right)}\right)=m^{ed}\mod n

{\ displaystyle D \ left ({E \ left (m \ right)} \ right) = E \ left ({D \ left (m \ right)} \ right) = m ^ {ed} \ mod n}

We show that:

\forall m\in \mathbb {Z} _{n}:m^{ed}\equiv m\mod p

{\ displaystyle \ forall m \ in \ mathbb {Z} _ {n}: m ^ {ed} \ equiv m \ mod p}

.

Two cases are possible:

$m\not \equiv 0\mod p$ ${\ displaystyle m \ not \ equiv 0 \ mod p}$ .

Since the numbers $e$ ${\ displaystyle e}$ and $d$ ${\ displaystyle d}$ are mutually inverse with respect to modulation $\varphi (n)=(p-1)(q-1)$ ${\ displaystyle \ varphi (n) = (p-1) (q-1)}$ , i.e.

ed=1+k(p-1)(q-1)

{\ displaystyle ed = 1 + k (p-1) (q-1)}

for some whole

k

{\ displaystyle k}

,

then:

{\begin{aligned}m^{ed}&\equiv m^{1+k\left({p-1}\right)\left({q-1}\right)}&\equiv &\mod p\\&\equiv m\left({m^{p-1}}\right)^{k\left({q-1}\right)}&\equiv &\mod p\\&\equiv m\left(1\right)^{k\left({q-1}\right)}&\equiv m&\mod p\end{aligned}}

{\ displaystyle {\ begin {aligned} m ^ {ed} & \ equiv m ^ {1 + k \ left ({p-1} \ right) \ left ({q-1} \ right)} & \ equiv & \ mod p \\ & \ equiv m \ left ({m ^ {p-1}} \ right) ^ {k \ left ({q-1} \ right)} & \ equiv & \ mod p \\ & \ equiv m \ left (1 \ right) ^ {k \ left ({q-1} \ right)} & \ equiv m & \ mod p \ end {aligned}}}

where the second identity follows from Fermat's theorem .

Consider the second case:

m\equiv 0\mod p

{\ displaystyle m \ equiv 0 \ mod p}

,

then

m^{ed}\equiv 0\equiv m\mod p

{\ displaystyle m ^ {ed} \ equiv 0 \ equiv m \ mod p}

Thus, for all $m$ ${\ displaystyle m}$ equality holds

m^{ed}\equiv m\mod p

{\ displaystyle m ^ {ed} \ equiv m \ mod p}

Similarly, we can show that:

\forall m\in \mathbb {Z} _{n}:m^{ed}\equiv m\mod q

{\ displaystyle \ forall m \ in \ mathbb {Z} _ {n}: m ^ {ed} \ equiv m \ mod q}

.

Then, from the Chinese remainder theorem

\forall m\in \mathbb {Z} _{n}:m^{ed}\equiv m\mod n

{\ displaystyle \ forall m \ in \ mathbb {Z} _ {n}: m ^ {ed} \ equiv m \ mod n}

Example

Stage	Operation description	Operation result
Key generation	Choose two prime different numbers	$p=3557$ ${\ displaystyle p = 3557}$ , $q=2579$ ${\ displaystyle q = 2579}$
	Calculate product	$n=p\cdot q=3557\cdot 2579=9173503$ ${\ displaystyle n = p \ cdot q = 3557 \ cdot 2579 = 9173503}$
	Calculate Euler Function	$\varphi (n)=(p-1)(q-1)=9167368$ ${\ displaystyle \ varphi (n) = (p-1) (q-1) = 9167368}$
	Choose an open exhibitor	$e=3$ ${\ displaystyle e = 3}$
	Calculate the secret exponent	$d\equiv e^{-1}{\pmod {\varphi (n)}}$ ${\ displaystyle d \ equiv e ^ {- 1} {\ pmod {\ varphi (n)}}}$ $d=6111579$ ${\ displaystyle d = 6111579}$
	Publish Public Key	$\{e,n\}=\{3,9173503\}$ ${\ displaystyle \ {e, n \} = \ {3,9173503 \}}$
	Save Private Key	$\{d,n\}=\{6111579,9173503\}$ ${\ displaystyle \ {d, n \} = \ {6111579,9173503 \}}$
Encryption	Select text to encrypt	$m=111111$ ${\ displaystyle m = 111111}$
Encryption	Calculate ciphertext	${\begin{aligned}c&=E(m)\\&=m^{e}\mod n\\&=111111^{3}\mod 9173503\\&=4051753\end{aligned}}$ ${\ displaystyle {\ begin {aligned} c & = E (m) \\ & = m ^ {e} \ mod n \\ & = 111111 ^ {3} \ mod 9173503 \\ & = 4051753 \ end {aligned}} }$
Decryption	Calculate original message	${\begin{aligned}m&=D(c)=\\&=c^{d}\mod n\\&=4051753^{6111579}\mod 9173503\\&=111111\end{aligned}}$ {\ displaystyle {\ begin {aligned} m & = D (c) = \\ & = c ^ {d} \ mod n \\ & = 4051753 ^ {6111579} \ mod 9173503 \\ & = 111111 \ end {aligned} }}

Digital Signature

The RSA system can be used not only for encryption, but also for digital signature .

Suppose Alice (side $A$ ${\ displaystyle A}$ ) need to be sent to Bob (side $B$ ${\ displaystyle B}$ ) message $m$ ${\ displaystyle m}$ confirmed by electronic digital signature .

Algorithm :

Take plain text $m$ ${\ displaystyle m}$
Create Digital Signature $s$ ${\ displaystyle s}$ using your private key $\left\{d,n\right\}$ ${\ displaystyle \ left \ {d, n \ right \}}$ :

s=S_{A}\left(m\right)=m^{d}\mod n

{\ displaystyle s = S_ {A} \ left (m \ right) = m ^ {d} \ mod n}

Pass a pair $\left\{m,s\right\}$ ${\ displaystyle \ left \ {m, s \ right \}}$ consisting of message and signature.

Algorithm :

Take a pair $\left\{m,s\right\}$ ${\ displaystyle \ left \ {m, s \ right \}}$
Take the public key $\left\{e,n\right\}$ ${\ displaystyle \ left \ {e, n \ right \}}$ Alice
Calculate the prototype of the message from the signature:

m'=P_{A}\left(s\right)=s^{e}\mod n

{\ displaystyle m '= P_ {A} \ left (s \ right) = s ^ {e} \ mod n}

Verify signature authenticity (and message immutability) by comparing $m$ ${\ displaystyle m}$ and $m^{'}$ ${\ displaystyle m '}$

Since the digital signature provides both authentication of the author of the message and confirmation of the integrity of the contents of the signed message, it serves as an analogue of the signature made by hand at the end of the handwritten document.

An important property of a digital signature is that it can be verified by anyone who has access to its author’s public key. After a digital signature is authenticated, one of the messaging participants can transfer the signed message to someone else who is also able to verify this signature. For example, side $A$ ${\ displaystyle A}$ can forward to side $B$ ${\ displaystyle B}$ electronic check. After the party $B$ ${\ displaystyle B}$ will verify the signature of the party $A$ ${\ displaystyle A}$ on the check, she can transfer it to her bank, whose employees also have the opportunity to verify the signature and carry out the corresponding monetary transaction.

Note that the signed message $m$ ${\ displaystyle m}$ not encrypted . It is sent in its original form and its contents are not protected from confidentiality. By joint application of the above encryption schemes and digital signatures in the RSA system, you can create messages that will be encrypted and contain a digital signature. To do this, the author must first add his digital signature to the message, and then encrypt the resulting pair (consisting of the message itself and the signature) with the public key belonging to the recipient. The recipient decrypts the received message using his secret key ^[18] . If we draw an analogy with sending ordinary paper documents, then this process is similar to the fact that the author of the document put his seal under it, then put it in a paper envelope and sealed so that the envelope would be printed only by the person to whom the message is addressed .

RSA algorithm speed

Since key generation occurs much less frequently than operations that implement encryption, decryption, and the creation and verification of digital signatures, the task of computing $a=b^{c}{\bmod {n}}$ ${\ displaystyle a = b ^ {c} {\ bmod {n}}}$ represents the main computational complexity. This problem can be solved using the fast exponentiation algorithm . Using this algorithm to calculate $m^{e}{\bmod {n}}$ ${\ displaystyle m ^ {e} {\ bmod {n}}}$ required $O\left(\ln e\right)$ ${\ displaystyle O \ left (\ ln e \ right)}$ multiplication operations modulo ^[20] .

More details

imagine $e$ ${\ displaystyle e}$ in binary notation:

e=e_{k}\cdot 2^{k}+e_{k-1}\cdot 2^{k-1}+\dots +e_{1}\cdot 2+e_{0}

{\ displaystyle e = e_ {k} \ cdot 2 ^ {k} + e_ {k-1} \ cdot 2 ^ {k-1} + \ dots + e_ {1} \ cdot 2 + e_ {0}}

where

e_{k}=1,e_{i}\in \left\{0,1\right\}

{\ displaystyle e_ {k} = 1, e_ {i} \ in \ left \ {0,1 \ right \}}

put $m_{0}=m$ ${\ displaystyle m_ {0} = m}$ and then for $i=1,\dots ,k$ ${\ displaystyle i = 1, \ dots, k}$ we calculate

m_{i}=\left(m_{i-1}^{2}\cdot m^{e_{k-i}}\right){\bmod {n}}

{\ displaystyle m_ {i} = \ left (m_ {i-1} ^ {2} \ cdot m ^ {e_ {ki}} \ right) {\ bmod {n}}}

found $m_{k}$ ${\ displaystyle m_ {k}}$ and will be the desired value $m^{e}{\bmod {n}}$ ${\ displaystyle m ^ {e} {\ bmod {n}}}$

Since each calculation in step 2 requires no more than three multiplications modulo $n$ ${\ displaystyle n}$ and this step is performed $k\leq \log _{2}e$ ${\ displaystyle k \ leq \ log _ {2} e}$ times, then the complexity of the algorithm can be estimated by the value $O(\ln e)$ ${\ displaystyle O (\ ln e)}$ .

To analyze the execution time of operations with public and private keys, suppose that the public key $\left\{e,n\right\}$ ${\ displaystyle \ left \ {e, n \ right \}}$ and private key $\left\{d,n\right\}$ ${\ displaystyle \ left \ {d, n \ right \}}$ satisfy the relations $\log _{2}e=O(1)$ ${\ displaystyle \ log _ {2} e = O (1)}$ , $\log _{2}d\leq \beta$ ${\ displaystyle \ log _ {2} d \ leq \ beta}$ . Then in the processes of their application is performed accordingly $O\left(1\right)$ ${\ displaystyle O \ left (1 \ right)}$ and $O\left(\beta \right)$ ${\ displaystyle O \ left (\ beta \ right)}$ multiplications modulo.

Thus, the execution time of operations increases with the number of nonzero bits in the binary representation of the open exponent e . To increase the encryption speed, the value of e is often chosen equal to 17, 257, or 65537 - primes whose binary representation contains only two units: 17 ₁₀ = 10001 ₂ , 257 ₁₀ = 100000001 ₂ , 65537 ₁₀ = 10000000000000001 ₂ ( Fermat primes).

According to heuristic estimates, the length of the secret exponent $d$ ${\ displaystyle d}$ depending nontrivially on an open exponent $e$ ${\ displaystyle e}$ and module $n$ ${\ displaystyle n}$ is likely to be close to length $n$ ${\ displaystyle n}$ . Therefore, data decryption is slower than encryption, and signature verification is faster than creating it.

The RSA algorithm is much slower than AES and other algorithms using symmetric block ciphers .

Using the Chinese Residue Theorem to Speed Decryption

When decrypting or signing a message in the RSA algorithm, the exponent will be a rather large number (about 1000 bits). Therefore, an algorithm is needed that reduces the number of operations. Since the numbers $p$ ${\ displaystyle p}$ and $q$ ${\ displaystyle q}$ in decomposition $N=pq$ ${\ displaystyle N = pq}$ known to the owner of the private key, then you can calculate:

m_{p}=C^{d}{\bmod {p}}=C^{d{\bmod {p-1}}}{\bmod {p}},

{\ displaystyle m_ {p} = C ^ {d} {\ bmod {p}} = C ^ {d {\ bmod {p-1}}} {\ bmod {p}},}

m_{q}=C^{d}{\bmod {q}}=C^{d{\bmod {q-1}}}{\bmod {q}}.

{\ displaystyle m_ {q} = C ^ {d} {\ bmod {q}} = C ^ {d {\ bmod {q-1}}} {\ bmod {q}}.}

Insofar as $p$ ${\ displaystyle p}$ and $q$ ${\ displaystyle q}$ - order numbers $2^{512},$ ${\ displaystyle 2 ^ {512},}$ these steps require two expansions of the number into a 512-bit power modulo a 512-bit number. This is significant (for 1024 bits, testing showed 3 times) faster than one raising to a 1024-bit degree modulo a 1024-bit number. Next, it remains to recover $m$ ${\ displaystyle m}$ by $m_{p}$ ${\ displaystyle m_ {p}}$ and $m_{q},$ ${\ displaystyle m_ {q},}$ what can be done using the Chinese remainder theorem ^[21] .

RSA Cryptanalysis

The stability of the algorithm is based on the complexity of computing the inverse function of the encryption function ^[22]

c=E(m)=m^{e}\mod n

{\ displaystyle c = E (m) = m ^ {e} \ mod n}

.

To calculate $m$ ${\ displaystyle m}$ by famous $c, e, n$ ${\ displaystyle c, e, n}$ need to find one $d$ ${\ displaystyle d}$ to

e\cdot d\equiv 1{\pmod {\varphi (n)}},

{\ displaystyle e \ cdot d \ equiv 1 {\ pmod {\ varphi (n)}},}

i.e

d\equiv e^{-1}{\pmod {\varphi (n)}}.

{\ displaystyle d \ equiv e ^ {- 1} {\ pmod {\ varphi (n)}}.}

The inverse element calculation modulo is not a difficult task, but the value is unknown to the attacker $\varphi (n)$ ${\ displaystyle \ varphi (n)}$ . To calculate the Euler function of a known number $n$ ${\ displaystyle n}$ you need to know the decomposition of this number into prime factors. Finding such factors is a difficult task, and knowing these factors is a “ backdoor ” ( English backdoor ), which is used to calculate $d$ ${\ displaystyle d}$ the owner of the key. There are many algorithms for finding simple factors, the so-called factorization , the fastest of which today is the general method of sieving a number field , the speed of which for a k-bit integer is

\exp((c+o(1))k^{\frac {1}{3}}\log ^{\frac {2}{3}}k)

{\ displaystyle \ exp ((c + o (1)) k ^ {\ frac {1} {3}} \ log ^ {\ frac {2} {3}} k)}

for some

c<2

{\ displaystyle c <2} .

In 2010, a group of scientists from Switzerland, Japan, France, the Netherlands, Germany and the USA managed to successfully calculate data encrypted using a 768-bit RSA cryptographic key. Simple factors were found by the general method of sifting a numerical field ^[23] . According to the researchers, after their work, only RSA keys with a length of 1024 bits or more can be considered as a reliable encryption system. Moreover, encryption with a key length of 1024 bits should be abandoned in the next three to four years ^[24] . Since December 31, 2013, Mozilla browsers have ceased to support certificates of certificate authorities with RSA keys less than 2048 bits ^[25] .

In addition, in case of incorrect or non-optimal implementation or use of the algorithm, special cryptographic attacks are possible, such as attacks on schemes with a small secret exponent or on schemes with a common selected module value.

Attacks on the RSA Algorithm

Wiener Attack on RSA

Some applications need to speed up the decryption process in the RSA algorithm. Therefore, a small decoding exponent is selected. In the case when the decoding exponent $d<N^{\frac {1}{4}}$ ${\ displaystyle d <N ^ {\ frac {1} {4}}}$ can determine $d$ ${\ displaystyle d}$ in polynomial time using the Wiener attack ^[21] , based on continuous fractions .

More details

By real number

\alpha \in \mathbb {R}

{\ displaystyle \ alpha \ in \ mathbb {R}}

define the sequence:

$\alpha _{0}=\alpha ,p_{0}=q_{0}=1,p_{1}=a_{0}a_{1}+1,q_{1}=a_{1},$ ${\ displaystyle \ alpha _ {0} = \ alpha, p_ {0} = q_ {0} = 1, p_ {1} = a_ {0} a_ {1} + 1, q_ {1} = a_ {1} ,}$
$\alpha _{i}=\lfloor \alpha _{i}\rfloor ,\alpha _{i+1}={\frac {1}{\alpha _{i}-a_{i}}},$ ${\ displaystyle \ alpha _ {i} = \ lfloor \ alpha _ {i} \ rfloor, \ alpha _ {i + 1} = {\ frac {1} {\ alpha _ {i} -a_ {i}}} ,}$
$p_{i}=a_{i}p_{i-1}+p_{i-1}$ ${\ displaystyle p_ {i} = a_ {i} p_ {i-1} + p_ {i-1}}$ at $i\geq 2,$ ${\ displaystyle i \ geq 2,}$

q_{i}=a_{i}q_{i-1}+q_{i-1}

{\ displaystyle q_ {i} = a_ {i} q_ {i-1} + q_ {i-1}}

at

i\geq 2.

{\ displaystyle i \ geq 2.}

Whole numbers $a_{0},a_{1},a_{2},...$ ${\ displaystyle a_ {0}, a_ {1}, a_ {2}, ...}$ called continuous fraction representing $\alpha ,$ ${\ displaystyle \ alpha,}$ and rational numbers ${\frac {p_{i}}{q_{i}}}-$ ${\ displaystyle {\ frac {p_ {i}} {q_ {i}}} -}$ suitable fractions. Each of the suitable fractions is irreducible, and the growth rate of their denominators is comparable to the exponential. One of the important results of the theory of continued fractions :

If the irreducible fraction

{\frac {p}{q}}

{\ displaystyle {\ frac {p} {q}}}

satisfies the inequality:

\left|\alpha -{\frac {p}{q}}\right|\leq {\frac {1}{2q^{2}}},

{\ displaystyle \ left | \ alpha - {\ frac {p} {q}} \ right | \ leq {\ frac {1} {2q ^ {2}}},}

then ${\frac {p}{q}}-$ ${\ displaystyle {\ frac {p} {q}} -}$ one of the suitable fractions in the decomposition $\alpha$ ${\ displaystyle \ alpha}$ into a continuous fraction .

Suppose we have a module

N=pq,

{\ displaystyle N = pq,}

moreover

{\displaystyle q<semantics><mrow class=

{\ displaystyle q <p <2q.}

Let the attacker know the encryption exponent E, which has the property

Ed=1\mod \varphi ,

{\ displaystyle Ed = 1 \ mod \ varphi,}

Where

\varphi =\varphi (N)=(p-1)(q-1).

{\ displaystyle \ varphi = \ varphi (N) = (p-1) (q-1).}

We also assume that

E<\varphi ,

{\ displaystyle E <\ varphi,}

since this is done in most applications. It follows from the assumptions that

Ed-k\varphi =1.

{\ displaystyle Ed-k \ varphi = 1.}

Hence,

$\left|{\frac {E}{\varphi }}-{\frac {k}{d}}\right|={\frac {1}{d\varphi }}.$ ${\ displaystyle \ left | {\ frac {E} {\ varphi}} - {\ frac {k} {d}} \ right | = {\ frac {1} {d \ varphi}}.}$

\left|N-\varphi \right|=\left|p+q-1\right|<3N^{\frac {1}{2}}.

{\ displaystyle \ left | N- \ varphi \ right | = \ left | p + q-1 \ right | <3N ^ {\ frac {1} {2}}.}

This shows that

{\frac {E}{N}}-

{\ displaystyle {\ frac {E} {N}} -}

pretty good approximation for

{\frac {k}{d}}.

{\ displaystyle {\ frac {k} {d}}.}

Really,

\left|{\frac {E}{N}}-{\frac {k}{d}}\right|=\left|{\frac {Ed-Nk}{dN}}\right|=\left|{\frac {Ed-k\varphi -Nk+k\varphi }{dN}}\right|=\left|{\frac {1-k(N-\varphi )}{dN}}\right|\leq \left|{\frac {3kN^{\frac {1}{2}}}{dN}}\right|={\frac {3k}{dN^{\frac {1}{2}}}}.

{\ displaystyle \ left | {\ frac {E} {N}} - {\ frac {k} {d}} \ right | = \ left | {\ frac {Ed-Nk} {dN}} \ right | = \ left | {\ frac {Ed-k \ varphi -Nk + k \ varphi} {dN}} \ right | = \ left | {\ frac {1-k (N- \ varphi)} {dN}} \ right | \ leq \ left | {\ frac {3kN ^ {\ frac {1} {2}}} {dN}} \ right | = {\ frac {3k} {dN ^ {\ frac {1} {2}} }}.}

As $E<\varphi ,$ ${\ displaystyle E <\ varphi,}$ obviously $,k<d.$ ${\ displaystyle, k <d.}$ In addition, since it was assumed that $d<{\frac {1}{4}}N^{\frac {1}{4}}.$ ${\ displaystyle d <{\ frac {1} {4}} N ^ {\ frac {1} {4}}.}$ Means

\left|{\frac {E}{N}}-{\frac {k}{d}}\right|<{\frac {1}{2d^{2}}}.

{\ displaystyle \ left | {\ frac {E} {N}} - {\ frac {k} {d}} \ right | <{\ frac {1} {2d ^ {2}}}.}

Since GCD $(k,d)=1,$ ${\ displaystyle (k, d) = 1,}$ then ${\frac {k}{d}}-$ ${\ displaystyle {\ frac {k} {d}} -}$ suitable fraction in the decomposition of the fraction ${\frac {E}{N}}$ ${\ displaystyle {\ frac {E} {N}}}$ in continuous . Thus, you can find the decoding exponent by substituting the denominators of the suitable fractions in the expression:

(M^{E})^{d}=M\mod N

{\ displaystyle (M ^ {E}) ^ {d} = M \ mod N}

for some random number $M .$ ${\ displaystyle M.}$ Having equality, we find $d .$ ${\ displaystyle d.}$ The total number of suitable fractions to be checked is estimated as $O(lnN).$ ${\ displaystyle O (lnN).}$

Generalized Wiener attack

The Wiener attack described above is possible only when the attacker is aware of the inequality

d\leq {\frac {1}{3}}N^{\frac {1}{4}},

{\ displaystyle d \ leq {\ frac {1} {3}} N ^ {\ frac {1} {4}},}

Where $d$ ${\ displaystyle d}$ - secret exhibitor, and $N$ ${\ displaystyle N}$ - RSA module. Boneh and Derfi, using a two-dimensional analogue of Koppersmith’s Theorem , were able to generalize Wiener's attack ^[21] to the case when

d\leq N^{0,292}.

{\ displaystyle d \ leq N ^ {0.292}.}

RSA Application

The RSA system is used to protect software and digital signature schemes.

It is also used in the open PGP encryption system and other encryption systems (for example, DarkCryptTC and xdc format) in combination with symmetric algorithms .

Due to the low encryption speed (about 30 kbit / s with a 512-bit key on a 2 GHz processor), messages are usually encrypted using more powerful symmetric algorithms with a random session key (for example, AES , IDEA , Serpent , Twofish ), and with using RSA, only this key is encrypted, thus a hybrid cryptosystem is implemented. Such a mechanism has potential vulnerabilities due to the need to use a cryptographically robust pseudo random number generator to generate a random symmetric encryption session key.

Notes

↑ Still Guarding Secrets after Years of Attacks, RSA Earns Accolades for its Founders - Society for Industrial and Applied Mathematics .
<a href=" https://wikidata.org/wiki/Track:Q782100 "> </a>
↑ Introduction to Modern Cryptography - 2 - CRC Press , 2015 .-- P. 411. - 583 p. - ISBN 978-1-4665-7026-9
<a href=" https://wikidata.org/wiki/Track:Q29014817 "> </a> <a href=" https://wikidata.org/wiki/Track:Q954828 "> </a>
↑ ¹ ² Bakhtiari, Maarof, 2012 , p. 175.
↑ Diffie, Hellman, 1976 .
↑ A Quarter Century of Recreational Mathematics, by Martin Gardner . Scientific American. - "Ronald L. Rivest of the Massachusetts Institute of Technology allowed me to be the first to reveal — in the August 1977 column — the" publickey "cipher system that he co-invented." Date of treatment March 3, 2012. Archived June 23, 2012.
↑ ¹ ² Gardner, 1977 .
↑ Bruce Schneier. Factoring - State of the Art and Predictions (English) (February 12, 1995). Date of treatment March 3, 2012. Archived June 23, 2012.
↑ Donald T. Davis. A Discussion of RSA-129 Activity ( November 25, 2003). Date of treatment March 3, 2012. Archived June 23, 2012.
↑ Chmora A. L. 4.6.4. Power attack based on distributed computing // Modern Applied Cryptography. - 2002. - 2000 copies. - ISBN 5-85438-046-3 .
↑ Rivest, Shamir, Adleman, 1978 .
↑ Ronald L. Rivest et al. Cryptographic communications system and method
↑ Adam Back. PGP Timeline Date of treatment March 3, 2012. Archived June 23, 2012.
↑ J. Linn. Privacy Enhancement for Internet Electronic Mail: Part III - Algorithms, Modes, and Identifiers (August 1989). Date of treatment March 18, 2012. Archived June 23, 2012.
↑ RSA Security Inc. Company history . FundingUniverse. Date of treatment March 18, 2012. Archived June 23, 2012.
↑ CC Cocks A note on “non-secret encryption” Archived on August 4, 2009. (Eng.) November 20, 1973
↑ ¹ ² ³ Menezes, Oorschot, Vanstone, 1996 , 8.2. RSA public-key encryption.
↑ Boneh, 1999 .
↑ ¹ ² Bruce Schneier. Applied Cryptography 2nd Edition Protocols, Algorithms, and C ++ Source Code
↑ Rivest, Shamir, Adleman, 1978 , pp. 7-8.
↑ Rivest, Shamir, Adleman, 1978 , p. 8.
↑ ¹ ² ³ N. SMART. The world of programming. Cryptography - ed. Technosphere, Moscow 2006
↑ Jan S. Y. RSA Cryptanalysis. - M. — Izhevsk: Research Center “Regular and Chaotic Dynamics”, Izhevsk Institute for Computer Research, 2011. - 312 p.
↑ RSA-768 Factorization Announcement
↑ Factorization of RSA-768 (eng.)
↑ Dates for Phasing out MD5-based signatures and 1024-bit moduli

Literature

Diffie W. , Hellman M. E. New Directions in Cryptography // IEEE Trans. Inf. Theory / F. Kschischang - IEEE , 1976. - Vol. 22, Iss. 6. - P. 644–654. - ISSN 0018-9448 - doi: 10.1109 / TIT.1976.1055638
<a href=" https://wikidata.org/wiki/Track:Q16194641 "> </a> <a href=" https://wikidata.org/wiki/Track:Q27178858 "> </a> <a href = " https://wikidata.org/wiki/Track:Q127793 "> </a> <a href=" https://wikidata.org/wiki/Track:Q476466 "> </a> <a href = " https://wikidata.org/wiki/Track:Q462089 "> </a>
Gardner M. A New Kind of Cipher that Would Take Millions of Years to Break // Sci. Amer. - New York City : Nature Publishing Group , 1977. - Iss. 237. - P. 120–124. - ISSN 0036-8733
<a href=" https://wikidata.org/wiki/Track:Q60 "> </a> <a href=" https://wikidata.org/wiki/Track:Q39379 "> </a> <a href = " https://wikidata.org/wiki/Track:Q677706 "> </a> <a href=" https://wikidata.org/wiki/Track:Q180419 "> </a> <a href = " https://wikidata.org/wiki/Track:Q27209317 "> </a>
Rivest R. , Shamir A. , Adleman L. A method for obtaining digital signatures and public-key cryptosystems // Commun. ACM - New York City : ACM , 1978. - Vol. 21, Iss. 2. - P. 120–126. - ISSN 0001-0782 ; 1557-7317 - doi: 10.1145 / 359340.359342
<a href=" https://wikidata.org/wiki/Track:Q127992 "> </a> <a href=" https://wikidata.org/wiki/Track:Q60 "> </a> <a href = " https://wikidata.org/wiki/Track:Q918650 "> </a> <a href=" https://wikidata.org/wiki/Track:Q320624 "> </a> <a href = " https://wikidata.org/wiki/Track:Q1120519 "> </a> <a href=" https://wikidata.org/wiki/Track:Q578036 "> </a> <a href = " https : //wikidata.org/wiki/Track: Q27177229 "> </a>
Menezes A. J. , Oorschot P. v. , Vanstone S. A. Handbook of Applied Cryptography - CRC Press , 1996 .-- 816 p. - ( Discrete Mathematics and Its Applications ) - ISBN 978-0-8493-8523-0
<a href=" https://wikidata.org/wiki/Track:Q27123086 "> </a> <a href=" https://wikidata.org/wiki/Track:Q4723156 "> </a> <a href = " https://wikidata.org/wiki/Track:Q15262410 "> </a> <a href=" https://wikidata.org/wiki/Track:Q954828 "> </a> <a href = " https://wikidata.org/wiki/Track:Q21725116 "> </a> <a href=" https://wikidata.org/wiki/Track:Q7437437 "> </a>
Boneh D. Twenty Years of attacks on the RSA Cryptosystem // Notices Amer. Math. Soc. / F. Morgan - AMS , 1999 .-- Vol. 46, Iss. 2. - P. 203–213. - ISSN 0002-9920
<a href=" https://wikidata.org/wiki/Track:Q3751884 "> </a> <a href=" https://wikidata.org/wiki/Track:Q27210308 "> </a> <a href = " https://wikidata.org/wiki/Track:Q24158 "> </a> <a href=" https://wikidata.org/wiki/Track:Q2896470 "> </a>
Bakhtiari M. , Maarof M. A. Serious Security Weakness in RSA Cryptosystem // IJCSI - 2012 .-- Vol. 9, Iss. 1, No 3. - P. 175–178. - ISSN 1694-0814 ; 1694-0784
<a href=" https://wikidata.org/wiki/Track:Q27209082 "> </a> <a href=" https://wikidata.org/wiki/Track:Q27209093 "> </a> <a href = " https://wikidata.org/wiki/Track:Q27209141 "> </a> <a href=" https://wikidata.org/wiki/Track:Q27209155 "> </a>

Niels Ferguson , Bruce Schneier . Practical Cryptography = Practical Cryptography: Designing and Implementing Secure Cryptographic Systems. - M .: Dialectics, 2004 .-- 432 p. - 3000 copies. - ISBN 5-8459-0733-0 , ISBN 0-4712-2357-3 .
Schneier B. Applied Cryptography. Protocols, algorithms, C source code = Applied Cryptography. Protocols, Algorithms and Source Code in C. - M .: Triumph, 2002 .-- 816 p. - 3000 copies. - ISBN 5-89392-055-4 .

[_d190ac6c80be82fb-1] Still Guarding Secrets after Years of Attacks, RSA Earns Accolades for its Founders - Society for Industrial and Applied Mathematics .
<a href=" https://wikidata.org/wiki/Track:Q782100 "> </a>

[_91ea0c70c16aea20-2] Introduction to Modern Cryptography - 2 - CRC Press , 2015 .-- P. 411. - 583 p. - ISBN 978-1-4665-7026-9
<a href=" https://wikidata.org/wiki/Track:Q29014817 "> </a> <a href=" https://wikidata.org/wiki/Track:Q954828 "> </a>

[_7363aa0714d3f6f6-3] ¹ ² Bakhtiari, Maarof, 2012 , p. 175.

[_08b07f1facd8ea80-4] Diffie, Hellman, 1976 .

[5] A Quarter Century of Recreational Mathematics, by Martin Gardner . Scientific American. - "Ronald L. Rivest of the Massachusetts Institute of Technology allowed me to be the first to reveal — in the August 1977 column — the" publickey "cipher system that he co-invented." Date of treatment March 3, 2012. Archived June 23, 2012.

[_aa6c7f30194f3484-6] ¹ ² Gardner, 1977 .

[7] Bruce Schneier. Factoring - State of the Art and Predictions (English) (February 12, 1995). Date of treatment March 3, 2012. Archived June 23, 2012.

[8] Donald T. Davis. A Discussion of RSA-129 Activity ( November 25, 2003). Date of treatment March 3, 2012. Archived June 23, 2012.

[9] Chmora A. L. 4.6.4. Power attack based on distributed computing // Modern Applied Cryptography. - 2002. - 2000 copies. - ISBN 5-85438-046-3 .

[_446f86ba7b0dd94d-10] Rivest, Shamir, Adleman, 1978 .

[11] Ronald L. Rivest et al. Cryptographic communications system and method

[12] Adam Back. PGP Timeline Date of treatment March 3, 2012. Archived June 23, 2012.

[13] J. Linn. Privacy Enhancement for Internet Electronic Mail: Part III - Algorithms, Modes, and Identifiers (August 1989). Date of treatment March 18, 2012. Archived June 23, 2012.

[14] RSA Security Inc. Company history . FundingUniverse. Date of treatment March 18, 2012. Archived June 23, 2012.

[15] CC Cocks A note on “non-secret encryption” Archived on August 4, 2009. (Eng.) November 20, 1973

[_0ca773cfe4c06ed0-16] ¹ ² ³ Menezes, Oorschot, Vanstone, 1996 , 8.2. RSA public-key encryption.

[_dd37a5ba3f09df55-17] Boneh, 1999 .

[Shnaer-18] ¹ ² Bruce Schneier. Applied Cryptography 2nd Edition Protocols, Algorithms, and C ++ Source Code

[_801f515d363e628a-19] Rivest, Shamir, Adleman, 1978 , pp. 7-8.

[_575b3bdf18883def-20] Rivest, Shamir, Adleman, 1978 , p. 8.

[Smart-21] ¹ ² ³ N. SMART. The world of programming. Cryptography - ed. Technosphere, Moscow 2006

[22] Jan S. Y. RSA Cryptanalysis. - M. — Izhevsk: Research Center “Regular and Chaotic Dynamics”, Izhevsk Institute for Computer Research, 2011. - 312 p.

[23] RSA-768 Factorization Announcement

[24] Factorization of RSA-768 (eng.)

[25] Dates for Phasing out MD5-based signatures and 1024-bit moduli

RSA

Content

History

Algorithm Description

Introduction

Algorithm for creating public and private keys

Encryption and Decryption

Session Key Encryption Algorithm

RSA circuit correctness

Example

Digital Signature

RSA algorithm speed

Using the Chinese Residue Theorem to Speed ​​Decryption

RSA Cryptanalysis

Attacks on the RSA Algorithm

Wiener Attack on RSA

Generalized Wiener attack

RSA Application

Notes

Literature

More articles:

Using the Chinese Residue Theorem to Speed Decryption