RSA

In cryptography, RSA (Rivest, Shamir and Adleman) is a public-key cryptographic system developed in 1979, which uses factorization of integer numbers. It is the first and most widely used algorithm of its kind and is valid for both encryption and digital signing.

The security of this algorithm lies in the problem of factoring in whole numbers. The messages sent are represented by numbers, and the operation is based on the product, known, of two large prime numbers chosen randomly and kept secret. Currently these cousins are of the order of 10300{displaystyle 10^{300}, and its size is expected to always grow with increased computing capacity.

As in any public key system, each user has two encryption keys: one public and one private. When you want to send a confidential message, the sender looks for the receiver's public key, encrypts his message with that key, and once the encrypted message reaches the receiver, he takes care of decrypting it using his private key.

In the case of wanting to sign (authenticity, integrity and non-repudiation properties), the sender obtains a hash of the message to be signed and processes it with his private key, thus obtaining the signature; the message and signature are sent; the receiver recalculates the hash and decrypts the original hash with the sender's public key, thus validating (or not) the signature of the message.

It is believed that RSA will be safe as long as fast ways of decomposing a large number into products of primes are not known. Although it is believed that quantum computing could provide a solution to the factorization problem, some researchers doubt that such advances will make these algorithms obsolete.

History

Adi Shamir, one of the three RSA inventors (the other two are Ron Rivest and Leonard Adleman).

The algorithm was described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman of the Massachusetts Institute of Technology (MIT); the letters RSA are the initials of their last names. Clifford Cocks, a British mathematician working for the British intelligence agency GCHQ, had described an equivalent system in an internal document in 1973. Due to the high cost of the computers needed to implement it at the time, his idea did not get out. The discovery of it, however, was not revealed until 1997 as it was confidential, so Rivest, Shamir and Adleman independently developed RSA.

The algorithm was patented by MIT in 1983 in the United States under number 4,405,829. This patent expired on September 21, 2000. As the algorithm was published before the application was patented, this prevented it from being patented in other parts of the world. Since Cocks worked at a government agency, a US patent would not have been possible either.

It is a purely asymmetric algorithm, along with DSA. This algorithm, as its name indicates, is used to sign (authenticate) and to encrypt information. One disadvantage of the DSA algorithm is that it requires much more computation time than RSA.

RSA Algorithm

The algorithm consists of three steps: key generation, encryption and decryption

Algorithm Idea

Suppose Bob wants to send Alice a secret message that only she can read.

Alice sends Bob a box with an unlocked padlock, to which only Alice has the key. Bob receives the box, writes the message, puts it in the box and locks it with his own padlock (now Bob can't read the message). Bob sends the box to Alicia and she opens it with her key. In this example, the box with the lock is Alice's "public key," and the key to the lock is Alice's "private key."

Technically, Bob sends Alicia a "Land message" M{displaystyle M} in the form of a number m{displaystyle m} lower than other n{displaystyle n}through a reversible protocol known as padding scheme (“fill pattern”). Next it generates the « encrypted message» c{displaystyle c} through the following operation:

c=me(modn){displaystyle c=m^{pmod {n}} },

where e{displaystyle e} is Alicia's public key.

Now Alicia deciphers the key message c{displaystyle c} through reverse operation

m=cd(modn){displaystyle m=c^{d}{pmod {n}} },

where d{displaystyle d} It's the private key that only Alicia knows.

Key generation

1. Two different prime numbers are chosen p{displaystyle p } and q{displaystyle q }.
   • For security reasons, these numbers should be randomly chosen and should have a similar bit length. Cousin can be easily found by primality test.
2. Estimated n=p⋅ ⋅ q{displaystyle n=pcdot q }.
   • n{displaystyle n } is used as the module for both keys, public and private.
3. With φ φ {displaystyle varphi } is the φ function of Euler calculated φ φ (n)=(p− − 1)⋅ ⋅ (q− − 1){displaystyle varphi (n)=(p-1)cdot (q-1)} taking advantage of the following two properties of the Euler function:
   • φ φ (p)=p− − 1{displaystyle varphi (p)=p-1} Yeah. p{displaystyle p} He's a cousin.
   • Yeah. m and n They're cousins to each other, then φ φ (mn)=φ φ (m)φ φ (n){displaystyle varphi (mn)=varphi (m)varphi (n)}.
4. Choose a positive integer e{displaystyle e } lower than φ φ (n){displaystyle varphi (n)}, to be copressed with φ φ (n){displaystyle varphi (n)}.
   • e{displaystyle e} it becomes known as the exponent of the public key.
   • If you choose a e{displaystyle e} with a short chained sum, the encryption will be more effective. An exponent e{displaystyle e } very small (e.g. e=3{displaystyle e=3 }) could pose a security risk.
5. A determination d{displaystyle d } (by modular arithmetic) that meets consistency e⋅ ⋅ d≡ ≡ 1(modφ φ (n)){displaystyle ecdot dequiv 1{pmod {varphi}}}}I mean, d{displaystyle d } be the reverse modular multiplier emodφ φ (n){displaystyle emod varphi (n) }
   • Expressed otherwise, d⋅ ⋅ e− − 1{displaystyle dcdot e-1 } is divided exactly by φ φ (n)=(p− − 1)⋅ ⋅ (q− − 1){displaystyle varphi (n)=(p-1)cdot (q-1) }.
   • This is usually calculated by the extended Euclides algorithm.
   • d{displaystyle d } is saved as the exponent of the private key.

La Public key That's it. (n,e){displaystyle(n,e) }, that is, the module and the encryption exponent. La Private key That's it. (n,d){displaystyle(n,d) }, that is, the module and the decryption exponent, which must be kept secret.

Using the properties of the function of Euler, the Theorem of Euler and the Theorem of the Chinese rest can be shown that x≡ ≡ xed(modn),Русский Русский x한 한 Zn{displaystyle xequiv x^{ed}{pmod {n}}forall xin mathbf {Z} _{n}}

Notes

• PKCS#1 v2.0 and PKCS#1 v2.1 are specified by the Carmichael function λ λ (n)=mcm(p− − 1,q− − 1){displaystyle lambda (n)={rm {mcm}(p-1,q-1) } instead of the function φ φ {displaystyle varphi } from Euler, where mcm{displaystyle mathrm {mcm} } indicates the minimum common multiple.
• For greater efficiency the following values are calculated in advance and stored as part of the private key:
  • p{displaystyle p } and q{displaystyle q }: cousins for the generation of keys,
  • dmod(p− − 1){displaystyle dmod (p-1) } and dmod(q− − 1){displaystyle dmod (q-1) },
  • q− − 1mod(p){displaystyle q^{-1mod (p) }.

Encryption

Alicia communicates her public key (n,e){displaystyle (n,e)} to Bob and keep the private key in secret. Now Bob wants to send a message M{displaystyle M} Alicia.

First, Bob turns M{displaystyle M} in an integer m{displaystyle m} lower than n{displaystyle n}. Then calculate the encrypted text c{displaystyle c} through operation

c≡ ≡ me(modn){displaystyle cequiv m^{e}{pmod {n}}}}.

This can be done quickly through the binary exposure method. Now Bob transmits c{displaystyle c} Alicia.

Decryption

Alicia can get back. m{displaystyle m } from c{displaystyle c } using your exponent d{displaystyle d } of the private key through the following calculation:

m≡ ≡ cd(modn){displaystyle mequiv c^{d} {pmod {n}} }.

Now that you have m{displaystyle m } in your power, you can recover the original message M{displaystyle M } investing in padding scheme.

The above procedure works because

cd=(me)d≡ ≡ med(modn){displaystyle c^{d}=(m^{e}{d}{d}equiv m^{ed}{pmod {n}}{n}}}{ }{ }.

This is because, as we have chosen d{displaystyle d } and e{displaystyle e } so that ed=1+kφ φ (n){displaystyle ed=1+kvarphi (n)}It's done.

med=m1+kφ φ (n)=m(mφ φ (n))k≡ ≡ m(modn){displaystyle m^{ed}=m^{1+kvarphi (n)}=m(m^{varphi})}^{k}equiv m{pmod {n}}}}}}.

The last congruence follows directly from the Euler theorem when m{displaystyle m} It's coprim with n{displaystyle n}. It can be shown that equations are fulfilled for all m{displaystyle m} using congruence and the Chinese theorem of the rest.

This shows that the original message is obtained:

m=cd(modn){displaystyle m=c^{d}{pmod {n}} }.

Example

Here is an example of encryption/decryption with RSA. The parameters used here are small and indicative of what the algorithm handles, but we can also use OpenSSL to generate and examine a real key pair.

The public key is (e, n). The private key is (d, n). The encryption function is:

encrypt(m)=me(modn)=m17(mod3233){displaystyle {mbox{encrypt}}(m)=m^{{e}{pmod {n}}}=m^{17}{pmod {3233}}}}}}}

Where m is the cleartext. The decryption function is:

decrypt(c)=cd(modn)=c2753(mod3233){displaystyle {mbox{decrypt(c)}}=c^{d}{pmod {nn}}}=c^{2753}{pmod {3233}}}}}}}}{

Where c is the ciphertext. To encrypt the plaintext value 123, we compute:

encrypt(123)=12317(mod3233)=855{displaystyle {mbox{encrypt(123)}}=123^{17}{pmod {3233}}=855}

To decrypt the ciphertext value, we calculate:

decrypt(855)=8552753(mod3233)=123{displaystyle {mbox{decrypt(855)}}=855^{2753}{pmod {3233}}=123}

Large power and modulus calculations can be efficiently performed by the quadratic multiplication algorithm for modular exponentiation.

Schemes

RSA must be combined with some padding scheme, otherwise the value of M can lead to insecure ciphertexts.

• The value m=0, m= 1 or m=n-1 always produces equal encrypted texts for 0, 1 or n-1 respectively, due to the properties of the exponents.
• When we encrypt with small exponents (e=3) and small values m, the result of m could be strictly lower than the module n. In this case, the encrypted text could easily be decrypted, taking the e-sima root of the encrypted text without taking into account the module.

• Since the RSA encryption is a determinist algorithm (no random components) an attacker can successfully launch a chosen text attack against the cryptosystem, building a probable text dictionary with the public key, and storing the encrypted result. Noting the texts encrypted in a communication channel, the attacker can use this dictionary to decipher the content of the message.

In practice, the first of the two problems could arise when sending small ASCII messages where m is the concatenation of one or more ASCII encoded character(s). A message consisting of a single ASCII NUL character (whose value is 0) would be encoded as m=0, producing a ciphertext of 0 no matter what values of e and N are used. Probably, a single ASCII SOH (whose value is 1) would always produce a ciphertext of 1. For conventional systems using small values of e, such as 3, a single character ASCII message encoded using this scheme would be unsafe, since the maximum value of m would be 255, and 255³ is less than any reasonable modulus. In this way the cleartexts could be recovered simply by taking the cube root of the ciphertext. To avoid these problems, the practical implementation of RSA relies on some structures, use of random padding inside the value of m before encryption. This technique ensures that m will not fall into the insecure cleartext range, and that given a message, once it is padded, it will encrypt one of the large numbers of possible ciphertexts. The last feature is the dictionary increment making it intractable when carrying out an attack.

The RSA-padding scheme must be carefully designed to prevent sophisticated attacks which could be facilitated by the predictability of the message structure. Examples of padding scheme used with RSA:

• RSA-OAEP (Optimal Asymetric Encryption Padding) or RSA-OAEP+. This type of filling is used for example in PKCS#1 and in the TOR anonymity network
• RSA-SAEP+ (Simplified Asymmetric Encryption Padding)
• RSA-REACT
• RSA-PSS (Probabilistic Signature Scheme). Used for example in PKCS#1

Some of these padding schemes, for example RSA-OAEP and RSA-PSS, find their 'justification' theory in the controversial random oracle model.

Message authentication

RSA can also be used to authenticate a message. Suppose Alice wants to send an authenticated message to Bob. She produces a hash value of the message, raises it to the power of d≡ mod n (as she does when she decrypts messages), and attaches it to the message as a "signature". When Bob receives the authenticated message, she uses the same hash algorithm in conjunction with Alice's public key. She raises the received signature to the power of e≡ mod n (as she does when she encrypts messages), and compares the obtained hash result with the hash value of the message. If both match, he knows that the author of the message was in possession of Alice's secret key, and that the message has not been tampered with (he has not been attacked).

It should be noted that security padding-schemes such as RSA-PSS are essential for both signature security and message encryption, and that the same key should never be used for encryption and authentication purposes.

Security

The security of the RSA cryptosystem is based on two mathematical problems: the problem of factoring large numbers and the RSA problem. The complete decryption of an RSA ciphertext is computationally intractable, an efficient algorithm has not yet been found for both problems. Providing security against partial decryption might require the addition of a security padding scheme.

The RSA problem is defined as the task of taking eth roots modulo to compose n: retrieving a value m such that m>^e≡c (mod n), where (e , n) is an RSA public key and c is the RSA ciphertext. Currently the approximation to solve the RSA problem is the factor of the module n. With the ability to retrieve prime factors, an attacker can calculate the secret exponent d from a public key (e, n), then decrypt c using the standard procedure. To achieve this, an attacker must factor n into p and q, and compute (p-1)(q-1) with which allows you to determine d and e. No method has been found in polynomial time for the factorization of long integers. See factoring integers for a discussion of this problem.

The factorization of large numbers, usually propose methods having 663 bits in length using advanced distributed methods. RSA keys are typically between 1024-2048 bits in length. Some experts believe that 1024-bit keys could start to get weak before long; 4096 bit keys could be broken in the future. Therefore, if n is large enough the RSA algorithm is safe. If n is 256 bits or less, it can be factored in a few hours on a personal computer, using free software. If n is 512 bits or less, it can be factored by several hundred computers as in 1999. A theoretical hardware device called TWIRL described by Shamir and Tromer in 2003 questioned the security of 1024-bit keys.. It is currently recommended that n be at least 2048 bits long.

In 1993, Peter Shor published his algorithm, showing that a quantum computer could in principle improve factorization in polynomial time, showing RSA as an obsolete algorithm. However, quantum computers are not expected to finish their development for many years.

Practical considerations

Key generation

Looking for large prime numbers p and q by the randomness test and performing probabilistic primality tests which eliminate virtually all non-primes (efficiently).

The numbers p and q should not be close enough for the Fermat factorization for n to be successful. Also, if any p-1 or q-1 has only small prime factors, n can be factored quickly, so these values of p or q must be discarded.

You should not use a cousin search method that gives any information about the cousins to the attacker. In particular, a good random prime number generator should be used for the value used. Note that the requirement is that both be random and unpredictable. They are not the same criteria; a number could have been chosen by a random process, but if it is predictable in any way (or partially predictable), the method used will result in low security. For example: The Rand Corp table of random numbers in 1950 could serve very well as an example of true random criteria, but it has been published and is accessible to the attacker. If the attacker can guess half the digits of p or q, he could quickly guess the other half. (See Coppersmith in 1997).

It is important that the secret key d be very large. Wiener showed in 1990 that if p is between q and 2q (it is typical) and d < n^1/4/3, then d can be computed efficiently from n and e. Although values of e as low as 3 have been used in the past, small exponents in RSA are currently deprecated, for reasons including no cleartext padding, a vulnerability listed above. 65537 is normally used as the value of e, considered too large to avoid small exponentiation attacks, in fact it has enough Hamming weight to facilitate efficient exponentiation.

Speed

RSA is much slower than DES and other symmetric cryptosystems. In practice, Bob normally encrypts messages with symmetric algorithms, encrypts the symmetric key with RSA, and transmits both said key (ie RSA encrypted) and the symmetrically encrypted message to Alice.

This also raises additional security issues, for example, it is of great importance to use a strong random generator for symmetric keys, because otherwise Eve (an attacker wanting to find out the content of the message) could bypass the RSA asymmetric key by guessing the symmetric key.

Key distribution

As with all encryption, it is important how the RSA public keys are distributed. The distribution of the key must be secure against an attacker trying to spy on the channel to carry out a replay attack. Suppose Eve (attacker) has some way of arbitrarily giving Bob keys and making him believe they came from Alice. Suppose Eve can intercept transmissions between Alice and Bob. Eve sends Bob her own public key, as Bob believes it is Alice's, Eve can then intercept any encrypted text Bob sends, decrypt it with her own secret key, save a copy of the message, encrypt the message with Alice's public key, and send the new ciphertext to Alice. Initially, neither Alicia nor Bob have detected Eve's presence. Against the defense of attacks some are based on digital certificates or other components of infrastructures of the public key.