RSA (cryptosystem)

(RSA, Rivest, Shamir and Adleman ) is an asymmetric cryptographic method that may be used for both encryption and digital signature. It uses a pair of keys consisting of a private key that is used to decrypt or sign data, and a public key with which to encrypt or signatures verified. The private key is kept secret and can only be calculated with extremely high cost of the public key.

  • 2.3.1 example
  • 2.4.1 example
  • 3.1 Relationship between RSA and the factorisation
  • 3.2 difficulty of factoring
  • 3.3 Difficulty of the RSA problem
  • 3.4 assaults against the unmodified RSA method
  • 3.5 Padding
  • 3.6 chosen-ciphertext attack
  • 3.7 Safety of symmetric methods
  • 4.1 preliminary work
  • 4.2 Key Generation
  • 4.3 encryption
  • 4.4 decryption
  • 4.5 signature
  • 4.6 verification
  • 5.1 Hybrid Methods
  • 5.2 Areas of application

History

After Whitfield Diffie and Martin Hellman had published a theory of public-key cryptography, tried the three mathematicians Rivest, Shamir and Adleman at MIT, to refute the assumptions of Diffie and Hellman. After they were able to perform the proof in different methods, they finally came across one in which they found no attack points. From this, emerged in 1977 RSA, the first published asymmetric encryption method. The name RSA stands for the initials of their surnames.

In the early 1970s, a similar asymmetric method was developed in the Government Communications Headquarters of Ellis, Cocks and Williamson, but which did not achieve any great practical importance and has not been scientifically published for reasons of confidentiality. RSA could therefore be applied for a patent in 1983, although it was not the first method of this type. The patent expired on 21 September 2000.

Method

The method is related to the Rabin encryption method. Since it operates deterministically, it is susceptible to simple attacks. In practice, RSA is therefore combined with the Optimal Asymmetric Encryption Padding.

One-way functions

Functions for which a direction slightly, which is difficult to calculate other is referred to as one-way functions ( engl. one-way function). For example, according to current knowledge, the factorization of a large number, so its decomposition into its prime factors, very time-consuming, while generating a number by multiplying prime numbers is quite simple. Special one-way functions are trapdoor functions (English trapdoor one-way function), which are with the aid of additional information backwards easy to calculate.

The encryption and signature with RSA based on a Einwegpermutation with trapdoor (English trapdoor one-way permutation, short TOWP ), a trapdoor function that simultaneously bijective, ie a permutation. The one-way property justified why the decryption (or signing ) without the secret key ( the trapdoor ) is difficult.

Generation of public and private key

The public key (public key ) is a pair of numbers and the private key ( private key) a pair of numbers, where both keys are the same. This is called the RSA modulus, the encryption exponent and the decryption exponent. These numbers are generated by the following method:

The numbers, and are no longer needed and can be deleted after the key creation. However, it is relatively easy these values ​​, and to reconstruct. For efficiency reasons, it is chosen to be small, common is the fourth Fermat number. Smaller values ​​of can lead to opportunities for attack, in the form of published by Johan Håstad "Broadcast " attack, in which the sending of a message can lead to multiple recipients to a decryption on the Chinese remainder theorem. If you choose one with less than a quarter of the bits of the RSA modulus can - unless certain additional conditions are met - are determined with a building on continued fractions method efficiently.

Example

Encrypting messages

To encrypt a message, the sender uses the formula

And obtains from the message the ciphertext. The number must be smaller than the RSA modulus.

Example

It is to be encrypted, the number 7. The message sender uses the published key, and expects

The cipher is so.

Decrypt messages

The ciphertext can be decrypted by modular exponentiation back to plain text. The receiver uses the formula

With the value known only to him as well.

Example

For a given is calculated

The plaintext is then.

Sign Messages

To sign a message, applies the RSA function with its own private key from the sender to the message. For testing the receiver turns on the signature using the public key of the transmitter, the inverse function, and compares it with the additional transmitted unencrypted message. If both match, the signature is valid and the recipient can be sure that the person who signed the document, also owns the private key and that no one has modified the document since it was signed. It is the integrity and authenticity guaranteed, provided that the private key remains in the actual secret. Due to the Homomorphieeigenschaft of RSA can be signed with this method, only a message. Lying namely two signatures before, so an attacker can calculate therefrom the signature of the message by Multipizieren.

This problem can be circumvented by not the message itself is signed. Instead, the hash value of the message is calculated with a method specified in addition to the signature collision resistant hash function. This is signed with the private key to obtain the actual signature. The recipient can verify the resulting signature with the public key, and then receives a hash value. This compares with the formed his own hash value of this message to him. If the two hash values ​​match, it can be assumed with a high probability that the message was transmitted without errors, and is not forged. However, this modification does not meet the modern safety requirements, therefore methods are used, such as RSA -PSS to sign with RSA.

RSA with the Chinese Remainder Theorem

Using the Chinese remainder theorem messages can be efficiently decrypted or signed. Because the module is very large, the bit representations used in the computer of the numbers are very long. The Chinese Remainder Theorem allows to place in a group of size at the same time in the two smaller groups to perform the size and the calculations and then reassemble the result back. Here, since the numbers are much smaller, this calculation is faster overall. This variant is (Chinese remainder theorem ) also known by the English name of the Chinese Remainder Theorem CRT CRT - RSA.

The private key is then in contrast to what is assumed in the remainder of this article, the following components:

  • , The RSA modulus,
  • , The decryption exponent,
  • , The first prime number,
  • , The second prime,
  • , Often called DMP1,
  • , Often called dmq1 and
  • , Often called IQMP.

A signature of a message is then performed as follows.

From the last equation one can immediately see that and. Thus, the signature does both with consistent, therefore, after the Chinese remainder theorem.

RSA is not a prime number test

If primes are, does the RSA method. Conversely, however, from the functioning RSA method can not be concluded that the modulus of two primes and assembled is because at Carmichael numbers does the procedure, although Carmichael numbers do not match the standard form.

Security

Public - key encryption techniques such as RSA are always used in practice as a hybrid method in conjunction with symmetric methods. In the analysis of security in practical use, the safety of the public- key cryptography and the practical security of the entire system must be considered. Attacks on the RSA method often done via the side channels. The overall system can be unsafe if only one component, such as a computer has been compromised.

Relationship between RSA and the factorisation

In the cryptanalysis of the RSA algorithm, there are two problems:

  • RSA problem (): Given the public key and the ciphertext. The clear text is sought where:
  • RSA key problem (): Given the public key. The secret key is sought where:

The following relations between the RSA and problems, the factorisation, are known:

The relationship is trivial, because if you have the private key, you can order as above decrypt any ciphertext. Whether the converse is also true, is currently unknown.

Also the relationship is trivial, because if you factored, one can thus easily be calculated, and then efficiently compute the Euclidean algorithm to a given public key, the corresponding private key, as in the key generation.

A probabilistic polynomial time algorithm has long been known for the relationship. Recently it was shown that it is possible this reduction in the balanced RSA (ie, and have the same bit length ) also perform deterministic. The proof uses the Coppersmith method for the determination of zeros of an irreducible bivariate polynomial with integer coefficients, which can be attributed to a lattice basis reduction.

As all common implementations use RSA balanced, the breaking of the secret key is only with the knowledge of the public key as difficult as factoring in practice. Because, in the case of the additional knowledge of a secret text the difficulty of the factorization problem of central interest.

Difficulty of factoring

One would like for very large prime numbers and factoring. This factorization is not practical for large numbers with the methods known today. However, it is not proven that it is a difficult problem in principle with the prime factorization.

With the quadratic sieve, the number RSA -129 was in 1994 with 129 decimal places in 8 months factorized by about 600 volunteers. Using the method of Zahlkörpersiebs was the default in the RSA Factoring Challenge of RSA Laboratories 200 - digit decimal number RSA -200 broken down into its two large prime factors in 2005 by scientists from the Friedrich- Wilhelms-Universität Bonn. ( The first RSA numbers to RSA -500 were named according to the number of decimal places, more RSA figures on the number of binary digits. ) The factorization began in late 2003 and lasted until May 2005. Among other things came to a computer network of 80 commercial computers the University of Bonn for use. In November 2005, RSA Laboratories paid for the factorization of RSA -640, a number with 640 bits or 193 decimal places, a premium of $ 20,000. Although now no more premiums are paid for the factorization of the RSA challenge numbers, the number RSA -768 was factored in December 2009.

For the factorization of RSA - 1024 (309 decimal places) or even RSA - 2048 (617 decimal places) were $ 100,000 or $ 200,000 awarded; RSA Laboratories have completed the RSA Factoring Challenge in May 2007, after the above-mentioned scientists at the University of Bonn, a 1039- bit Mersenne number (312 decimal places) have factored in the same month. Because of the unequal number of digits of the factors but it was much easier than to factor an RSA number of equal length. The growing computational power of modern computer provides for short-term security of RSA is essentially not a problem, especially since this development is predictable: The user can look for in the production of his key that he can not be factored over the duration of the intended use. Unforeseeable developments, such as the development significantly faster algorithms, or even a powerful quantum computer that could perform the factorization of numbers by using the Shor algorithm efficient, involve certain risks, at least for the medium-and long -term security of the encrypted data.

For specific safety level of certain key lengths, there are different statements. According to the Federal Network Agency are for RSA - based signatures to the end of 2020 with a minimum key length of 1976 bits suitable (Recommendation 2048 bits ). For signature process according to the requirements of § 17 para 1 to 3 Signatures, " for which the best known attacks on the problem of factoring large numbers or on the problem of computing discrete logarithms in finite fields based (RSA and DSA), key lengths of at least 3000 bits are required "to perspective to establish at least a security level of 120 bits.

Difficulty of the RSA problem

In some special cases, one can break the RSA method to have solved without factorization. The attack of Vienna with Balanced Power RSA solves the RSA key problem efficiently under the assumption that the private key has only a small bit length, more precisely. Wiener used here, the fact that under the estimate of the fracture appears ( an integer ) in the chain fracture development. The barrier was improved by means of lattice basis reduction to.

Also, the RSA problem can be solved efficiently without factoring under some assumptions. The attack of Håstad determines a plain text, the small encryption exponent ( approximately ) has been specially prepared for multiple recipients prior to encryption, such as when the recipient's number was encoded in the plaintext. This attack uses the Coppersmith method to calculate small roots of a polynomial in one variable, which in turn is based on lattice reduction.

Attacks against the unmodified RSA method

In practice, the RSA method is as described above is not used because it has several shortcomings.

The RSA encryption is deterministic. This allows an attacker to guess a plaintext, encrypt it with the public key, and then compare it with a cipher. Since the attacker can create a large table such plaintext Chiffratpaare, the plain text must not be easy to guess. This means that unmodified RSA IND - CPA is not secure, now a minimum requirement for public-key encryption method.

If the plaintext and the encryption exponent are so small, that is, an attacker can attract the nth root of and decrypt the cipher text in this way. Square root extraction is difficult only modulo a large number, in this case, but may be regarded as in the integers.

If the same message is sent to multiple recipients, although all different ( and prime ) moduli use, but as public keys have the same exponent, then can be calculated from messages with the Chinese remainder theorem. Because ( by assumption for all ), this number can be thought of as lying in the integers and square roots is simply there again. This attack is called after its discoverer Johan Håstad as " Håstads attack ".

Since the RSA function is multiplicative (ie true ), you can generate another valid ciphertext from any ciphertext. If you can convince the owner of the corresponding private key of it to decode this number or sign, you can easily gain from the result.

The same property also allows an attack on the signature scheme. From known plaintext - signature pairs is more valid signatures can

Calculate.

Padding

To prevent such attacks, called padding scheme are used in RSA encryption and RSA signature. Standards for padding scheme for RSA are defined eg in PKCS # 1 or ISO 9796. This made ​​use that the length of the plaintext and the hash value is significantly smaller than the length of, and add the plaintext and the hash value before encrypting or signing a string R with a given structure, the randomly among several possible is chosen randomly and thus the cipher. It is not applied to the message or on the hash value, the RSA function, but on the plaintext (or its hash value) with attached R. In general, contains an indication of the length of the message or the hash value or a unique string that identifies the beginning of. This not only facilitates the decoding, but also complicates attacks. Padding scheme can be used for the calculation of even random numbers and hash functions. Some modern Padding - for example, the Optimal Asymmetric Encryption Padding ( OAEP ) or the Probabilistic Signature Scheme (PSS ) - use cryptographic hash functions to the plaintext before encryption to further randomize and are under idealizing assumptions on the hash function used provably secure under the RSA assumption.

Chosen-ciphertext attack

Daniel Bleichenbacher presented in 1998 before an attack on the specified in PKCS # 1 v1 RSA encryption. He took advantage of that PKCS # 1 v1 is a message format pretending and some implementations spend after decryption error messages, if that format was not complied with. To perform the attack against a cipher, to choose a number and calculates a new cipher. In the message format, the first two bytes 00 and 02, so if comes no error message, it is known that both the original message and the new message in the first two bytes are 00 02. Multiple repetition with cleverly chosen allow to gradually uncover after the entire plaintext. RSA is immune to this attack according to PKCS # 1 version 2.

Security of symmetric methods

BSA is usually combined in a hybrid process with symmetric encryption method. Here, a session key for a symmetric encryption is randomly generated, which is then encrypted using RSA and transmitted along with the message. With a signature, not the entire message, but only a hash value is signed.

The hash value and the symmetric key is relatively short, in any case shorter than the RSA modulus. Therefore, the symmetric key may be encrypted with a single RSA encryption. For the security of RSA prime numbers with hundreds of digits ( 2048 bits) are required. Therefore, symmetric key at any usual length can be encrypted.

As a very safe classified algorithms for symmetric encryption 3DES and AES apply. These use 112, 128, 168 or 256 bits. This corresponds to about 77 decimal places at 256 bit. Thus, a brute -force attack is virtually excluded. A secure hash function such as SHA -256 generates function values ​​with a length of also 256 bits. This signature scheme can be implemented using RSA, which only require an encryption step.

The safety and performance of the overall system are limited by the security of the public- key method, provided be used only as safe classified algorithms and the choice of the key can be considered a sufficiently random.

Complete Example

Preparatory work

The above steps will now be explained on a complete example. To encrypt a text, first letter must be converted to numbers. For this use in practice, for example, the ASCII code. Here, the following assignment is arbitrary chosen:

A = 01 B = 02 C = 03, etc. (00 = space ) In addition, it is assumed that three characters are grouped into a number. The letters AX is thus to 012,420th The smallest number to be encrypted is then 000000 ( three spaces), the largest 262626 ( ZZZ ). Thus, the modulus must be greater than 262626.

Clear Text: W I K I P E D I A Encoding: 23 09 11 09 16 05 04 09 01 key generation

First of two prime numbers be a secret chosen as an example. This results in:

( random, relatively prime to )

( the multiplicative inverse using the extended Euclidean algorithm)

Public key and

Private key: and

Encoding

Cn = Kne mod N for n = 1,2,3 ( ...) C1 = 2309111721 mod 263 713 = 001 715 C2 = 0916051721 mod 263 713 = 184304 C3 = 0409011721 mod 263 713 = 219 983 decryption

Kn = Cnd mod N for n = 1,2,3 ( ...) K1 = 0017151373 mod 263 713 = 230911 K2 = 1843041373 mod 263 713 = 091 605 K3 = 2199831373 mod 263 713 = 040 901 signature

Cn = Knd mod N C1 = 2309111373 mod 263 713 = 219611 C2 = 0916051373 mod 263 713 = 121243 C3 = 0409011373 mod 263 713 = 138 570 verification

Kn = Cne mod N K1 = 2196111721 mod 263 713 = 230911 K2 = 1212431721 mod 263 713 = 091 605 K3 = 1385701721 mod 263 713 = 040 901 The computation of modular exponentiation can be accelerated by binary exponentiation ( square-and - multiply ).

This one turns after each computational step on the manageable numbers, the modulo operation "mod " to hold the intermediate results as small as possible. From the plain language "7", we thus obtain the ciphertext "2".

Application

Hybrid Methods

RSA is slower compared to processes such as 3DES and AES by at least a factor of 1000. In practice, RSA is therefore usually used only replace a key for symmetric encryption. Then symmetric algorithms are used for the encryption of the data. They combine the advantages of both systems are combined: a simple and efficient encryption key exchange.

Areas of application

  • Internet and telephony infrastructure: X.509 certificates
  • Transmission protocols: IPSec, TLS, SSH, WASTE
  • E -mail encryption: PGP, S / MIME
  • Authentication French phone cards
  • Card payment: EMC
  • RFID chip on the German passport
  • Electronic banking: HBCI
695887
de