RSA cryptosystem

RSA is an asymmetric cryptographic method that can be used both for encryption and for digital signing . It uses a key pair consisting of a private key , which is used to decrypt or sign data, and a public key, which is used to encrypt or verify signatures. The private key is kept secret and cannot be calculated from the public key with realistic effort.

history

After Whitfield Diffie and Martin Hellman published a theory on public key cryptography in 1976, three mathematicians Rivest , Shamir and Adleman at MIT tried to refute Diffie and Hellman's assumptions. After performing the evidence on various procedures, they eventually came across one that they found no point of attack. This resulted in RSA in 1977 , the first published asymmetric encryption method. The name RSA stands for the first letters of their family names. Since Adleman assessed his share as low and initially did not want to be named as the author, the non-alphabetical order of the authors and thus the abbreviation RSA was used.

As early as the early 1970s , a similar asymmetrical method had been developed in the British GCHQ by Ellis , Cocks and Williamson , but it was not of great practical importance and was not scientifically published for reasons of secrecy. RSA was therefore able to apply for a patent in 1983 , although it was not the first process of its kind. The patent expired on September 21, 2000.

Procedure

The method is related to the Rabin encryption method . Because it is deterministic, it may be vulnerable to certain attacks. In practice, RSA is therefore combined with Optimal Asymmetric Encryption Padding .

One-way functions

→ Main article : One-way function

Functions , in which a direction of light, the other (reverse function) is difficult to calculate, is called one-way functions ( engl. One-way function ). For example, according to the current state of knowledge, the factoring of a large number, i.e. its decomposition into its prime factors, is very time-consuming, while the generation of a number by multiplying prime numbers is very easy and quick. Special functions are one-way trapdoor functions (engl. Trapdoor one-way function ), which are also easy to calculate backwards with the aid of an additional information.

The encryption and signature with RSA is based on a one-way permutation with a trapdoor ( TOWP for short ), a trapdoor function that is simultaneously bijective , i.e. a permutation . The one-way property explains why decryption (or signing) is difficult without the secret key (the trap door).

Generation of the public and private key

The public key is a pair of numbers and the private key is also a pair of numbers , both keys being the same. One calls the RSA module , the encryption exponent and the decryption exponent . These numbers are generated by the following procedure: ${\displaystyle (e,N)}$ ${\displaystyle (d,N)}$ ${\displaystyle N}$ ${\displaystyle N}$ ${\displaystyle e}$ ${\displaystyle d}$

1. Randomly and stochastically independently choose two prime numbers . These are the same order of magnitude, but not too close together, so that the following frame is approximately observed: . (In practice, this is done by generating numbers of the desired length and then performing a prime number test with them until two prime numbers have been found.) ${\displaystyle p\neq q}$ ${\displaystyle 0{,}1<|\log _{2}p-\log _{2}q|<30}$
2. Calculate the RSA modulus

   ${\displaystyle N=p\cdot q}$

3. Calculate the Euler φ function of ${\displaystyle N}$

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

4. Choose a number that is too prime for which applies . ${\displaystyle \varphi (N)}$ ${\displaystyle e}$ ${\displaystyle 1<e<\varphi (N)}$
5. Calculate the decryption exponent as the multiplicative inverse of with respect to the module . So the following congruence should apply ${\displaystyle d}$ ${\displaystyle e}$ ${\displaystyle \varphi (N)}$

   ${\displaystyle e\cdot d\equiv 1{\pmod {\varphi (N)}}}$

The numbers , and are no longer required and can be deleted after the key has been created. However, it is relatively easy to reconstruct these values ​​from , and . For reasons of efficiency, the choice is small; the fourth Fermat number is common . Smaller values ​​of can lead to attack possibilities, for example in the form of the "broadcast" attack published by Johan Håstad , in which sending a message to several recipients can lead to decryption using the Chinese remainder of the sentence . If one with less than a quarter of the bits of the RSA module is selected, it can be determined efficiently using a method based on continued fractions , provided certain additional conditions are not met . ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle \varphi (N)}$ ${\displaystyle e}$ ${\displaystyle d}$ ${\displaystyle N}$ ${\displaystyle e}$ ${\displaystyle 2^{16}+1=65537}$ ${\displaystyle e}$ ${\displaystyle d}$ ${\displaystyle d}$

example

1. We choose and for the two prime numbers. ${\displaystyle p=11}$ ${\displaystyle q=13}$
2. The RSA module is . ${\displaystyle N=p\cdot q=143}$
3. The Euler φ function thus has the value . ${\displaystyle \varphi (N)=\varphi (143)=(p-1)(q-1)=120}$
4. The number must be relatively prime to 120. We choose . So form and the public key. ${\displaystyle e}$ ${\displaystyle e=23}$ ${\displaystyle e=23}$ ${\displaystyle N=143}$
5. Calculating the inverse to modulo : The following applies: , in the specific example . With the extended Euclidean algorithm , one now calculates the factors and , and thus the private key is no longer needed. ${\displaystyle e}$ ${\displaystyle \varphi (N)}$
   ${\displaystyle e\cdot d+k\cdot \varphi (N)=1=\operatorname {ggT} (e,\varphi (N))}$
   ${\displaystyle 23\cdot d+k\cdot 120=1=\operatorname {ggT} (23,120)}$
   ${\displaystyle d=47}$ ${\displaystyle k=-9}$ ${\displaystyle d=47}$ ${\displaystyle k}$

Encrypt messages

Encryption

To encrypt a message , the sender uses the formula ${\displaystyle m}$

${\displaystyle c\equiv m^{e}{\pmod {N}}}$

and thus receives the ciphertext from the message . The number must be smaller than the RSA module . ${\displaystyle m}$ ${\displaystyle c}$ ${\displaystyle m}$ ${\displaystyle N}$

example

The number 7 should be encrypted. The transmitter uses the published key of the recipient , and expects ${\displaystyle N=143}$ ${\displaystyle e=23}$

${\displaystyle 2\equiv 7^{23}{\pmod {143}}}$

The cipher is so . ${\displaystyle c=2}$

Decrypt messages

Decryption

The ciphertext can be decoded back to plain text by modular exponentiation . The recipient uses the formula ${\displaystyle c}$ ${\displaystyle m}$

${\displaystyle m\equiv c^{d}{\pmod {N}}}$

with the value known only to him as well . ${\displaystyle d}$ ${\displaystyle N}$

example

For given is calculated ${\displaystyle c=2}$

${\displaystyle 7\equiv 2^{47}{\pmod {143}}}$

So the plaintext is . ${\displaystyle m=7}$

Signing messages

In order to sign a message , the sender uses the RSA function on the message with its own private key . To check the signature, the recipient applies the reverse function to the signature with the help of the sender's public key and compares it with the unencrypted message that was also transmitted . If both match, the signature is valid and the recipient can be sure that the person who signed the document also has the private key and that no one has changed the document since it was signed. The integrity and authenticity are guaranteed, provided the private key has really remained secret. Due to the homomorphism of RSA, only one message can be signed with this method. If there are two signatures , an attacker can calculate the signature of the message by multiplying them . ${\displaystyle m}$ ${\displaystyle d}$ ${\displaystyle m^{d}{\bmod {\ }}N}$ ${\displaystyle e}$ ${\displaystyle m}$ ${\displaystyle m_{1}^{d}}$ ${\displaystyle m_{2}^{d}}$ ${\displaystyle m_{1}m_{2}}$

The workaround for this problem is to not self-sign the message. Instead, the hash value of the message is calculated using a collision-resistant hash function specified in addition to the signature process . This is signed with the private key in order to receive the actual signature. The recipient can verify the signature obtained in this way with the public key and receives a value in the process . He compares this with the hash value of the message he has generated himself . If both values match, it can be assumed with a high degree of probability that the message was transmitted without errors and was not forged. However, this modification also does not meet modern security requirements, which is why methods such as RSA- PSS are used to sign with RSA. ${\displaystyle H}$ ${\displaystyle H(m)}$ ${\displaystyle m}$ ${\displaystyle h'}$ ${\displaystyle H(m)}$ ${\displaystyle m}$ ${\displaystyle H(m)=h'}$

See also : electronic signature  and full-domain hash

RSA with the Chinese remainder

With the help of the Chinese remainder of the sentence , messages can be decrypted or signed more efficiently. Because the module is very large, the bit representations of the numbers used in the computer are also very long. The Chinese remainder of the law allows the calculations to be carried out in the two smaller groups of size and at the same time instead of in one group of size and then reassembling the result. Since the numbers are much smaller here, this calculation is faster overall. This variant is also called CRT-RSA after the English name of the Chinese remainder theorem (CRT). ${\displaystyle N}$ ${\displaystyle N}$ ${\displaystyle p}$ ${\displaystyle q}$

The private key then, contrary to what is assumed in the rest of this article, consists of the following components:

• ${\displaystyle N}$, the RSA module ,
• ${\displaystyle d}$, the decryption exponent ,
• ${\displaystyle p}$, the first prime number ,
• ${\displaystyle q}$, the second prime number ,
• ${\displaystyle d_{p}=d{\bmod {(}}p-1)}$, often called dmp1 ,
• ${\displaystyle d_{q}=d{\bmod {(}}q-1)}$, often called dmq1 and
• ${\displaystyle q_{Inv}=q^{-1}{\bmod {p}}}$, often called iqmp .

A message is then signed as follows: ${\displaystyle m}$

• ${\displaystyle m_{1}=m^{d_{p}}{\bmod {p}}}$
• ${\displaystyle m_{2}=m^{d_{q}}{\bmod {q}}}$
• ${\displaystyle s=(q_{Inv}(m_{1}-m_{2}){\bmod {p}})q+m_{2}}$

From the last equation you can immediately see that and . The signature therefore matches both and with , hence the remaining sentence after the Chinese . (Note: One sees the identity as follows: Modulo p applies . The last identity follows from Fermat's small theorem . One obtains analogously .) ${\displaystyle s{\bmod {q}}=m_{2}}$ ${\displaystyle s{\bmod {p}}=q_{Inv}q(m_{1}-m_{2})+m_{2}{\bmod {p}}=m_{1}}$ ${\displaystyle s}$ ${\displaystyle {\bmod {p}}}$ ${\displaystyle {\bmod {q}}}$ ${\displaystyle m^{d}}$ ${\displaystyle s=m^{d}{\bmod {N}}}$ ${\displaystyle s=m^{d}{\bmod {p}}}$ ${\displaystyle s=m^{d_{p}}=m^{d+k(p-1)}=m^{d}(m^{p-1})^{k}=m^{d}}$ ${\displaystyle s=m^{d}{\bmod {q}}}$

RSA is not a prime number test

When numbers are prime , the RSA method works. Conversely, however, it cannot be concluded from the functioning RSA procedure that the module is composed of two prime numbers and , because the procedure works with Carmichael numbers , although Carmichael numbers do not correspond to the standard form. ${\displaystyle p\neq q}$ ${\displaystyle N}$ ${\displaystyle p}$ ${\displaystyle q}$

safety

Public key encryption methods such as RSA are always used in practice as hybrid methods in conjunction with symmetrical methods. When analyzing security in practical use, the security of the public key process and the practical security of the overall system must be considered. Attacks on the RSA method often take place via side channels . The overall system can be unsafe if only one component, for example a computer, has been compromised.

Relationship between RSA and the factorization problem

In the cryptanalysis of the RSA method, a distinction is made between two problems:

• RSA problem ( ): The public key and the ciphertext are given . The plain text is searched , whereby the following applies: ${\displaystyle \mathrm {RSAP} }$ ${\displaystyle (N,e)}$ ${\displaystyle c}$ ${\displaystyle m}$ ${\displaystyle m^{e}\equiv c{\pmod {N}}}$

The problem here lies in the difficulty of pulling -th roots modulo , which is necessary to determine the message . ${\displaystyle e}$ ${\displaystyle N}$ ${\displaystyle m}$

• RSA key problem ( ): The public key is given . The secret key is searched for , whereby the following applies: ${\displaystyle \mathrm {RSAP^{*}} }$ ${\displaystyle (N,e)}$ ${\displaystyle d}$ ${\displaystyle ed\equiv 1{\pmod {\varphi (N)}}}$

The problem lies in the difficulty of the Euler φ function of without knowledge of the factors p and q to calculate. ${\displaystyle N}$

The following relationships between the RSA problems and the factorization problem are known: ${\displaystyle \mathrm {FACTORING} }$

${\displaystyle \mathrm {RSAP} \leq _{p}\mathrm {RSAP^{*}} =_{p}\mathrm {FACTORING} }$

The relationship is trivial, because if you have the private key, you can use it to decrypt any ciphertext like above. It is currently unknown whether the reverse is true. ${\displaystyle \mathrm {RSAP} \leq _{p}\mathrm {RSAP^{*}} }$

The relationship is also trivial, because if you have factored you can easily calculate with it, and then efficiently calculate the associated private key for a given public key using the Euclidean algorithm, as in key generation. ${\displaystyle \mathrm {RSAP^{*}} \leq _{p}\mathrm {FACTORING} }$ ${\displaystyle N=pq}$ ${\displaystyle \varphi (N)=(p-1)(q-1)}$

A probabilistic polynomial time algorithm has long been known for the relationship . It was recently shown that this reduction can also be carried out deterministically in the balanced RSA (i.e. and have the same bit length) . The proof uses the Coppersmith method to determine the zeros of an irreducible bivariate polynomial with integer coefficients, which can be traced back to a lattice base reduction . ${\displaystyle \mathrm {FACTORING} \leq _{p}\mathrm {RSAP^{*}} }$ ${\displaystyle p}$ ${\displaystyle q}$

Since all popular implementations use balanced RSA, in practice breaking the secret key with just knowing the public key is just as difficult as factoring . Because of the additional knowledge of a ciphertext, the difficulty of the factorization problem is of central interest. ${\displaystyle N}$ ${\displaystyle \mathrm {RSAP} \leq _{p}\mathrm {FACTORING} }$

Difficulty of the factoring problem

One would like to factorize and for very large prime numbers . This prime factorization is practically impracticable for large numbers with the methods known today. However, it has not been proven that prime factorization is a fundamentally difficult problem. ${\displaystyle N=pq}$ ${\displaystyle p}$ ${\displaystyle q}$

With the square sieve in 1994 the number RSA-129 was factored to 129 decimal places in 8 months by approx. 600 volunteers. In 2005, scientists at the Friedrich-Wilhelms-Universität Bonn used the number body sieve method to break down the 200-digit decimal number RSA-200 specified by RSA Laboratories as part of the RSA Factoring Challenge into its two major prime factors. The first RSA numbers up to RSA-500 were named according to the number of decimal places, further RSA numbers according to the number of binary places. Factoring began at the end of 2003 and lasted until May 2005. Among other things, a computer network of 80 commercially available computers was used at the University of Bonn. In November 2005, RSA Laboratories paid a $ 20,000 premium to factorize RSA-640, a number with 640 bits or 193 decimal places. Although rewards are no longer paid for factoring 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) $ 100,000 and $ 200,000 respectively were offered; RSA Laboratories ended the RSA Factoring Challenge in May 2007 after the above-mentioned scientists from the University of Bonn factored a 1039-bit Mersenne number (312 decimal places) in the same month . Due to the unequal number of digits in the factors, this was much easier than factoring an RSA number of the same length. The growing computing power of modern computers is essentially no problem for the short-term security of RSA, especially since this development is foreseeable: When generating the key, the user can ensure that it cannot be factored for the duration of the intended use. Unpredictable developments such as the discovery of significantly faster algorithms or even the creation of a powerful quantum computer that could efficiently factorize numbers using the Shor algorithm harbor certain risks, at least for the medium and long-term security of the encrypted data.

There are different statements about the specific security level of certain key lengths. According to the Federal Network Agency , keys with a minimum length of 1976 bits are suitable for RSA-based signatures until the end of 2020 (recommendation 2048 bits). For signature procedures according to the requirements of § 17 Paragraph 1 to 3 SigG, "for which the best known attacks are based on the problem of factoring large numbers or on the problem of calculating discrete logarithms in finite fields (RSA and DSA ), key lengths of at least 3,000 bits will become mandatory ”in order to establish a security level of at least 120 bits in the future.

Difficulty of the RSA problem

In some special cases the RSA procedure can be broken without having solved the factorization problem. Wiener’s attack on balanced RSA solves the RSA key problem efficiently under the assumption that the private key has only a small bit length, more precisely . Wiener used the fact that under the estimate for the fraction (for an integer ) appears in the continued fraction expansion of . The barrier was improved by means of the lattice base reduction . ${\displaystyle d<{\tfrac {1}{3}}{\sqrt[{4}]{N}}}$ ${\displaystyle d}$ ${\displaystyle {\tfrac {k}{d}}}$ ${\displaystyle k}$ ${\displaystyle {\tfrac {e}{N}}}$ ${\displaystyle d<N^{0{,}292}}$

The RSA problem can also be solved efficiently without factoring under a few assumptions. Håstad's attack determined a plain text that was specially prepared with a small encryption exponent (for example ) for several recipients before encryption, for example if the recipient's number was encoded in plain text. This attack uses the Coppersmith method to compute small roots of a polynomial in an indeterminate, which in turn is based on lattice base reduction. ${\displaystyle e=3}$

Attacks against the unmodified RSA method ("Textbook RSA")

In the version described above, which is also known as "Textbook-RSA", RSA is neither suitable as an encryption nor as a signature method, since in both cases it is seriously insecure and as a signature method it cannot sign long messages.

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. This can be very workable and devastating, especially with very short messages like “yes” and “no”. It follows from this that unmodified RSA is not IND-CPA -secure, an absolute minimum requirement for encryption methods today.

If the plaintext and the encryption exponent are so small that is, then an attacker can pull the -th root of and decrypt the cipher in this way. Extracting the square root is only difficult modulo a large number, but in this case it can be viewed as lying in the whole numbers. ${\displaystyle m}$ ${\displaystyle e}$ ${\displaystyle c=m^{e}<N}$ ${\displaystyle e}$ ${\displaystyle c}$ ${\displaystyle c}$

If the same message is sent to several recipients who all use different (and partially prime) moduli , but the same exponent as the public key , then messages can be calculated using the Chinese remainder . Because (according to the requirement is for everyone ), this number can again be understood as lying in the whole numbers and taking the root is easy there. This attack is called "Håstad's attack" after its discoverer Johan Håstad. ${\displaystyle m}$ ${\displaystyle N_{i}}$ ${\displaystyle e}$ ${\displaystyle e}$ ${\displaystyle m^{e}{\bmod {N}}_{1},\ldots ,m^{e}{\bmod {N}}_{l}}$ ${\displaystyle m^{e}{\bmod {\prod }}N_{i}}$ ${\displaystyle m^{e}<\prod N_{i}}$ ${\displaystyle m<N_{i}}$ ${\displaystyle i}$

Since the RSA function is multiplicative (i.e. applies), one can generate another valid cipher from each cipher . If one can convince the owner of the associated secret key to decrypt or sign this number, one can easily gain from the result . ${\displaystyle x\mapsto x^{d}{\bmod {N}}}$ ${\displaystyle (xy)^{d}=x^{d}y^{d}{\bmod {N}}}$ ${\displaystyle m^{e}}$ ${\displaystyle m^{e}r^{e}=(mr)^{e}}$ ${\displaystyle mr}$ ${\displaystyle m}$

The same property also allows an attack on the signature process. Other valid signatures can be created from known plaintext signature pairs ${\displaystyle s_{1}=m_{1}^{d},\ldots ,s_{k}=m_{k}^{d}}$

${\displaystyle s=\prod s_{i}{\bmod {N}}}$ to news ${\displaystyle m=\prod m_{i}{\bmod {N}}}$

to calculate.

Padding

In order to prevent such attacks, so-called padding processes are used with RSA encryption and RSA signature . Standards for padding methods for RSA are e.g. B. defined in PKCS # 1 or ISO 9796. These take advantage of the fact that the length of the plain text or hash value is significantly smaller than the length of and add a character string R with a predetermined structure to the plain text or hash value before encryption or signature, which is random among several possible is chosen and thereby randomizes the cipher. The RSA function is not applied to the message or the hash value , but to the plain text (or its hash value) with an appended . Usually contains information about the length of the message or the hash value or a unique character string that identifies the beginning of . This not only makes decoding easier, it also makes attacks more difficult. Padding methods can also be used to calculate random numbers and hash functions. Some modern padding methods - for example the Optimal Asymmetric Encryption Padding (OAEP) or the Probabilistic Signature Scheme (PSS) - use cryptographic hash functions to further randomize the plaintext before encryption, and are provably secure under the RSA under idealizing assumptions about the hash function used -Adoption. ${\displaystyle N}$ ${\displaystyle M}$ ${\displaystyle h(M)}$ ${\displaystyle R}$ ${\displaystyle R}$ ${\displaystyle R}$ ${\displaystyle R}$

Chosen ciphertext attack

In 1998 Daniel Bleichenbacher presented an attack on the RSA encryption specified in PKCS # 1 v1 . He took advantage of the fact that PKCS # 1 v1 specifies a message format and some implementations issue error messages after decryption if this format was not adhered to. To attack a cipher , choose a number and use it to calculate a new cipher . In the message format, the first two bytes are 00 and 02, so if there is no error message, you know that the first two bytes are 00 02 for both the original message and the new message . Multiple repetitions with cleverly chosen ones make it possible to gradually uncover the entire plaintext. RSA according to PKCS # 1 from version 2 is immune to this attack. ${\displaystyle c}$ ${\displaystyle s}$ ${\displaystyle s^{e}c}$ ${\displaystyle m}$ ${\displaystyle sm}$ ${\displaystyle s}$

Hybrid process security

For reasons of efficiency, RSA is usually combined in hybrid processes with symmetrical processes. For hybrid encryption, a session key is randomly generated for a symmetrical encryption method, which is then encrypted via RSA and transmitted together with the message. Only a hash value is not signed for signing the entire message.

For the security of RSA, prime numbers with several hundred decimal places (at least 2048 bits) are required. This means that symmetric keys of any conventional length can be encrypted. Common methods for symmetrical encryption are based, for example, on the AES block cipher with a key length of 128, 192 or a maximum of 256 bits.

A secure hash function like SHA-2 generates hash values ​​with a length of 224 to 512 bits. This allows signature processes to be implemented using RSA that only require one signature step.

The security of the overall system depends on the security of both methods used, both in the case of encryption and signature. Since RSA requires significantly longer keys for a level of security similar to that of the symmetrical process, the security of the hybrid process is mostly determined by the security of the public key process.

Complete example

annotation

• Applying RSA directly to texts involves considerable risks. Unlike in the example, RSA is therefore only used in practice in combination with other methods. (See: Hybrid encryption and the section on attacks against the unmodified RSA method )
• To keep the example clear, relatively small prime numbers were used. At least 600 digits are typically recommended for secure encryption . ${\displaystyle N}$

Preliminary work

The above steps will now be explained using a complete example. In order to encrypt a text, letters must first be converted into numbers. In practice, for example, the ASCII code is used for this. Here the following assignment is chosen arbitrarily:

A=01 B=02 C=03 usw. (00 = Leerzeichen)

It is also assumed that three characters are combined into a number. The letter sequence AXT becomes 012420. The smallest number to be encrypted is then 000000 (three spaces), the largest is 262626 (ZZZ). The modulus must therefore be greater than 262626. ${\displaystyle N=p\cdot q}$

Klartext:   W  I  K   I  P  E   D  I  A
Kodierung: 23 09 11  09 16 05  04 09 01

Key generation

First, two prime numbers are secretly chosen, for example and . This results in: ${\displaystyle p=307}$ ${\displaystyle q=859}$

${\displaystyle N=p\cdot q=263713}$

${\displaystyle \varphi (N)=(p-1)\cdot (q-1)=262548}$

${\displaystyle e=1721}$    (random, coprime to ) ${\displaystyle \varphi (N)}$

${\displaystyle d=1373}$    (the multiplicative inverse to using the extended Euclidean algorithm ) ${\displaystyle e{\pmod {\varphi (N)}}}$

Public key:

${\displaystyle e=1721}$  and  ${\displaystyle N=263713}$

Private key:

${\displaystyle d=1373}$  and  ${\displaystyle N=263713}$

Encryption

Cn = Kne mod N  für n=1,2,3(,...)
C1 = 2309111721 mod 263713 = 001715
C2 = 0916051721 mod 263713 = 184304
C3 = 0409011721 mod 263713 = 219983

Decryption

Kn = Cnd mod N  für n=1,2,3(,...)
K1 = 0017151373 mod 263713 = 230911
K2 = 1843041373 mod 263713 = 091605
K3 = 2199831373 mod 263713 = 040901

signature

Cn = Knd mod N
C1 = 2309111373 mod 263713 = 219611
C2 = 0916051373 mod 263713 = 121243
C3 = 0409011373 mod 263713 = 138570

verification

Kn = Cne mod N
K1 = 2196111721 mod 263713 = 230911
K2 = 1212431721 mod 263713 = 091605
K3 = 1385701721 mod 263713 = 040901

The calculation of the modular exponentiation can be accelerated by binary exponentiation (square-and-multiply).

${\displaystyle 7^{23}\ {\bmod {\ }}143\ =\ \left(\left(\left(7^{2}\right)^{2}\cdot 7\right)^{2}\cdot 7\right)^{2}\cdot 7\ {\bmod {\ }}143=2}$

After each calculation step, the modulo operation "mod" is applied to the numbers to be handled in order to keep the intermediate results as small as possible. From the plain text “7” we thus get the ciphertext “2”.

application

Hybrid processes

→ Main article : Hybrid encryption

Compared to methods such as 3DES and AES, RSA is at least 100 times slower. In practice, RSA is therefore mostly only used to exchange a key for symmetric encryption . Symmetrical procedures are then used to encrypt the data. This combines the advantages of both systems: simple key exchange and efficient encryption.

application areas

• Internet and telephony infrastructure: X.509 certificates
• Transmission protocols: IPsec , TLS , SSH , WASTE
• Email encryption: OpenPGP , S / MIME
• Authentication of French calling cards
• Card payment: EMV
• RFID chip on the German passport
• Electronic banking: HBCI

literature

• Johannes Buchmann: Introduction to Cryptography . Springer-Verlag, Berlin 1999, ISBN 3-540-66059-3 .
• The dialogue of the sisters . In: c't . No. 25 , 1999 (Also included with the CrypTool e-learning program ).
• Alexander May: Computing the RSA Secret Key is Deterministic Polynomial Time Equivalent to Factoring . In: Advances in Cryptology (Crypto 2004), Lecture Notes in Computer Science . tape 3152 . Springer Verlag, 2004, p. 213-219 .
• Dan Boneh: Twenty Years of Attacks on the RSA Cryptosystem . In: Notices of the American Mathematical Society (AMS) . tape 46 , no. 2 , 1999, p. 203-213 .

Web links

Wikibooks: Evidence Archive: Correctness of the RSA Cryptosystem  - Learning and Teaching Materials

• Declaration by RSA from the Mathematics Department of the University of Wuppertal
• Simple explanation of RSA with online examples from Hans-G. Mekelburg
• Work on RSA with a focus on computer science. Archived from the original on August 18, 2012 ; Retrieved August 18, 2012 . 
• RSA code example in Scheme from the Massachusetts Institute of Technology
• Example of RSA encryption calculated by Joachim Mohr
• Interactive presentation of the RSA process from CrypTool
• Whitfield Diffie and Martin E. Hellman: New Directions in Cryptography , IEEE Transactions on Information Theory, Vol. IT-22, No. November 6, 1976
• Video: RSA: Introduction . Christian Spannagel 2012, made available by the Technical Information Library (TIB), doi : 10.5446 / 19815 .
• Video: RSA: Building the Keys . Christian Spannagel 2012, made available by the Technical Information Library (TIB), doi : 10.5446 / 19816 .
• Video: RSA: Encryption and Decryption . Christian Spannagel 2012, made available by the Technical Information Library (TIB), doi : 10.5446 / 19817 .
• Video: RSA: Example Part 1 . Christian Spannagel 2012, made available by the Technical Information Library (TIB), doi : 10.5446 / 19813 .
• Video: RSA: Example Part 2 . Christian Spannagel 2012, made available by the Technical Information Library (TIB), doi : 10.5446 / 19814 .

Individual evidence

1. ^ RL Rivest, A. Shamir, and L. Adleman: A Method for Obtaining Digital Signatures and Public-Key Cryptosystems . ( with.edu [PDF]).
2. ^ Whitfield Diffie, Martin E. Hellman: New Directions in Cryptography . ( stanford.edu [PDF]).
3. ^ Gina Kolata: Leonard Adleman; Hitting the High Spots Of Computer Theory . In: The New York Times . December 13, 1994, ISSN  0362-4331 ( nytimes.com ).
4. ^ CC Cocks: A note on 'non-secret encryption'. 1973 ( Memento of February 27, 2008 in the Internet Archive )
5. ↑ Patent US4405829 : Cryptographic communications system and method. Published September 20, 1983 , Applicant: Massachusetts Institute of Technology, Inventor: Ronald L. Rivest, Adi Shamir, Leonard Adleman. ‌
6. ↑ ^{a b} Federal Network Agency for Electricity, Gas, Telecommunications, Post and Railways: Announcement on the electronic signature according to the Signature Act and the Signature Ordinance (overview of suitable algorithms) of January 21, 2014 ( BAnz AT 02/20/2014 B4 )
7. ↑ D. Boneh: Twenty Years of Attacks on the RSA Cryptosystem . In: Notes of the AMS . tape 46 , no. 2 , February 1999, p. 203-213 ( PDF ).
8. ^ MJ Wiener: Cryptanalysis of short RSA secret exponents . In: IEEE Transactions on information theory . tape 36 , no. 3 , May 1990, pp. 553-558 , doi : 10.1109 / 18.54902 .
9. ↑ RSA Labs: RSA-200 is factored! ( Memento of the original from November 18, 2007 in the Internet Archive ) Info: The archive link was automatically inserted and not yet checked. Please check the original and archive link according to the instructions and then remove this notice. 
10. ^ MathWorld: RSA-640 Factored
11. ↑ RSA Labs: RSA-768 is factored!
12. ↑ Archived copy ( memento of the original dated February 22, 2015 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. 
13. ↑ http://www.keylength.com/en/compare/
14. ^ Johan Håstad: Solving Simultaneous Modular Equations of Low Degree . In: SIAM Journal on Computing . tape 17 , no. 2 , 1988, p. 336-341 ( Solving Simultaneous Modular Equations of Low Degree ).
15. ↑ What is OAEP? (English)
16. ↑ What is PSS / PSS-R? (English)
17. ^ Daniel Bleichenbacher: Chosen Ciphertext Attacks Against Protocols Based on the RSA Encryption Standard PKCS # 1 . In: CRYPTO '98 . 1998, p. 1-12 .
18. ↑ Cryptographic Procedures: Recommendations and Key Lengths. (PDF 1.4 (830kiB)) (No longer available online.) In: BSI. Federal Office for Information Security, February 10, 2014, pp. 15, 28 , archived from the original on February 22, 2014 ; Retrieved on July 13, 2014 (Table 1.2 and Table 3.1 recommend key lengths of 2000Bit for RSA).