RSA Kryptosystem

RSA is a procedure or an algorithm for the coding of electronic data, which uses different keys to the en and decoding, whereby the key to decoding is not calculable or only at high expenditure from the key to coding. The key toCoding can be published therefore. Such procedures become public as asymmetrical or keys - procedure marks. It is after its inventors Ronald L. R ivest, Adi S hamir and Leonard A dleman designated.

Table of contents

dish distribution

to thatAdvantage of asymmetrical procedures exists in the simplification of the dish distribution. With symmetrical procedures the exchange of a secret key is necessary, which transmitters and receivers use together. The exchange must take place thereby surely. This means the exchange must be. Itis however also surely to be placed that the key actually comes from the person, with which secret message to be exchanged are.

Through publicly keys - systems is void the necessity the key exchange against hearing to harden, there only the public key exchangedwill must. However a substantial problem remains, since further to be guaranteed it is that the public key actually comes from the person, with which secret messages to be exchanged is. In practice this often even if at the same time those is possibleSecrecy to be ensured can.

If communication is not, but no doubt about the identity of the partner exists and the message not of third to be changed can, is problem-free the key exchange with publicly the key procedure. However is this also with other procedures possible.

In addition the key can be built up from many partial keys. A Hashfunktion such as SHA-1 permits to calculate it by many longer partial keys a Komprimat, which can be used as keys for the symmetrical coding. ThosePartial keys can be exchanged at different times and with most different methods.

history

the key exchange is a logistic weak point and with several intergovernmental arguments and wars the exit (along) decided, so by activities e.g. of Alan Turingand others in Bletchley park in the Second World War. Therefore at the beginning of the 1970er became years in the Government Communications Headquarters of Ellis, Cocks and Williamson the later procedure of Diffie - Hellman similar asymmetrical procedure develops, which however nonegreat practical importance had and for secrecy reasons not (scientifically) was published. RSA could be announced therefore to the patent, although it was not the first procedure of this kind.

hybrid procedure

RSA is compared with 3DES, AES and SHA-1 around at least one factor 1,000 more slowly. For the coding of larger data sets therefore symmetrical procedures are used. It is sufficient to use however RSA for the change of a key for the symmetrical coding. Accordingly it is sufficient for one with the signature procedure SHA-1 - Worth instead of marking the entire message. Therefore practically always hybrid procedures are used.

procedures

after to the public key Kryptografie had published , tried Whitfield Diffie and Martin Hellman a theory the three mathematicians R ivest, Shamir and A dleman to disprove the acceptance from Diffie and light man to. After they could accomplish the proof with different procedures, they finally discovered one, with which they did not find any points of attack. From this then RSA developed.

The procedure became it develops and is based 1977 on the up-to-date knowledge conditions that the factorizing of a large number, thus their dismantling into its prime factors, is a very aufwändige affair, while producing of a number by multiplication of two prime numbers is quite simple. If now oneMessage a receiver to be coded transmitted is, generates these a public key. The message sender uses this publicly announced key, by coding thereby its message. Only the receiver can “decode” this, there only he the “composition” from himproduced (public) key knows.

one-way functions

functions like the multiplication/the factorizing, with which, one calls a direction easily, which is to be computed others with difficulty one-way functions (English. one way function). Over however the decoding actually possible toomake, must it itself around drop door functions (English. trap door function) act, which are to be computed with the help of additional information also backwards easily.

The procedure is related to the Rabin Verschlüsselungsverfahren.

algorithm

  1. selects two coincidentally and stochastically independently Prime numbers <math> p \ neq q< /math>, and compute the product <math> N = p \ cdot q< /math>.
    In practice these prime numbers are determined by rates of a number and whereupon the following use of a prime number test.
  2. Compute <math> \ varphi (N) = (P1) \ cdot (q-1)< /math>, whereby <math> \ varphi< /math> for those Euler φ-function stands.
  3. Select a number <math> e< /math>, to applies <math> for 1 < e < \ varphi (N)< /math>, those divisor-strangely too <math> \ varphi (N)< /math> is.
  4. Compute the number <math> D< /math> so that the product <cdot> math e \ D< /math> congruently 1 concerning the Modulus< math> \ varphi (N)< /math> it is that thus<math> e \ cdot D \ equiv 1 \ pmod {\ varphi (N)}</math> applies.

    The public key (public keys) exists then out
    • <math> N< /math>, the prime number product as well as
    • <math> e< /math>, the public exponent.

    The private key (private keys) consists of
    • <math> D< /math>, the private exponent as well as
    • <math> N< /math>, which however already admits by the public key is.

    <math> p< /math>, <math> q< /math> and <math> \ varphi (N)< /math> are not no more needed and should be deleted after the key production in safe way.


A numerical example:

  1. For the two prime numbers <math> p< /math> and <math> q< /math> one selects<math> p = 11< /math> and <math> q = 13< /math>. Thus math <N> = 143 becomes< /math>.
  2. The Euler φ-function takes thereby the value <math> \ varphi (N) = \ varphi (143) = (P1) (q-1) = 120< /math> on.
  3. For too <math> \ varphi (143) = 120< /math> divisor-strange new number <math> e< /math> one selects <math> e= 23< /math>.
  4. With the extended Euclidean algorithm one computes now the number <math> d=47< /math> with <math> e \ D cdot \ equiv 1 \ pmod {\ varphi (N)}</math>. Thus math <D> = 47 becomes< /math> the private key, <math> e = 23< /math> and <math> N = 143< /math> the public key.

Excursion: More alternativelyprivate key

Usually in practice the private key is somewhat in more detail stored, since this form of storage makes a decoding of Krypttexten more efficient (with the help of the Chinese remainder set). The private key exists therefore then contrary to that,which in the remainder of this article is accepted from the following components:

  • <math> N< /math>, the modulos,
  • <math> D< /math>, the so-called private exponent,
  • <math> p< /math>, the first prime number,
  • <math> q< /math>, the second prime number,
  • <math> D \ bmod (P1)< /math>, frequently dmp1 mentioned,
  • <math> D \ bmod (q-1)< /math>, frequently dmq1 mentioned and
  • <math> (1/q) \ bmod p< /math>, frequently iqmp mentioned.

coding message

Verschlüsselung
coding

around a message <math> K< /math> to code, the sender uses the formula

< math> C \ equiv K^e \ operator name {mod} N< /math>

and in such a way K /math receives from <>the plain language< math> that Geheimtext <math> C< /math>.

example

it is to be coded the number of 7.
The message sender uses the published key <math> N = 143< /math>, <math> e = 23< /math> and math

< C> counts \ equiv 7^ {23} \ \ operator name {mod} \ 143< /math>

To the computation of <math> 7^ {23} \ bmod 143< /math>congruence arithmetic can be used. With the help of the modular Exponentiation one computes fast:
<math> 7^ {23} \ \ operator name {mod} \ 143 \ = \ (((7^2) ^2 \ cdot 7) ^2 \ cdot 7) ^2 \ cdot 7 \ \ operator name {mod} \ 143 = 2< /math>

One spends after each calculation stepthe numbers the modulo which can be handled - operation (short: mod) on, in order to keep the results “as small as possible”.

From the plain language 7 thus the Geheimtext 2 became.

decoding message (decoding)

Entschlüsselung
decoding

the Geheimtext <math> C< /math> can by modular Exponentiation again to the plain language <math> K< /math> are decoded. The receiver uses the formula

< math> K \ equiv C^d \ operator name {mod} N< /math>

with only it value admitted <math> D< /math> as well as <math> N< /math>.

example

<math> K \ equiv 2^ {47} \ bmod 143 = ((((2^2) ^2 \ cdot2) ^2 \ 2) ^2 cdot \ cdot 2) ^2 \ cdot 2 \ bmod 143 = 7< /math>

Out <math> C = 2< /math> becomes thus again <math> K = 7< /math>.

See also fast strengthening

to marking messages

around a message <math> K< /math> to mark, this becomes alsothe own private key codes. For examining the signature the receiver decodes the message with the public key of the transmitter and compares these with the received <math> K< /math>. If they do not agree, the signature is invalid. If the signature is valid, thenthe receiver can be safe that that, which marked the document, also the private key possesses and that since the mark the document did not change anybody. The integrity and authenticity are thus guaranteed, presupposed the private keyremained really secret.

There asymmetrical procedures suitably are not to be coded around larger data sets, in practice not the message with the private key are coded. Instead the Hashwert becomes< math> H< /math> the message computes. This forms, usually togetherwith some technically necessary information, like z. B. the used Hashverfahren, the input <math> K^*< /math> the coding with the private key. This supplies the actual signature. The receiver knows now with the public key and the signature <math> K^*< /math> determine. Subsequently, can it the Hashwert of the message determine and with in <math> K^*< /math> stored compare. If the two values agree, can be assumed with high security the message became to transfer error free and is not not falsified.

See also electronic signature

security

publication IC key procedure such as RSA are in practice always used as hybrid procedures in connection with symmetrical procedures. With the analysis of security must be regarded the security publication IC key procedures and the practical security of the overall system.

security by RSA

accepted, the aggressor know only the public key, thus the values <math> N< /math> and <math> e< /math>. In order to decode the Geheimtext, it needs additionally <math> D< /math> or one too <math> D< /math> modulo <math> \ varphi (N)< /math> congruent value.

If the aggressor <math> \ varphi (N)< /math>, could he would know <math> D< /math> compute easily. A possibility for it is the dismantling of <math> N< /math> into its two prime factors <math> p< /math> and <math> q< /math>. This prime factorization is for large numbers with that today admitted procedures practically not feasible. It is however not proven that it concerns during the prime factorization difficult an in principle problem. On the contrary, with that square filter numbers were already faktorisiert also over 100 places. Thus it succeeded to z. B. Mathematicians of the University of Bonn 2005, within the frameworkto faktorisieren a competition a particular 200-stellige decimal number given of the RSA Laboratories. The factorizing began at the end of of 2003 and lasted until May 2005. Among other things a computer network of 80 commercial computers at the University of Bonn was used. This is still another good piece of that at least 300 decimal places today usual key removes. In November 2005 RSA Laboratories paid a number with 640 bits for the factorizing of RSA-640, and/or. 193 decimal places, a premium of 20.000 US-$. For the factorizingfrom RSA-1024 (309 decimal places) or RSA-2048 (617 decimal places) are 100,000 $ and/or. 200,000 $ expenditure-praises. The increasing arithmetic performance of modern computers does not represent a problem for the security of RSA, particularly since this development is foreseeable: The user can with thatIt respects production of its pair of keys on the fact that the number which can be divided is large enough to be able in order is not computed during the duration of the intended use. Not foreseeable developments such as z. B. the completion of an efficient quantum computer or the discovery onereally new high-efficient algorithm are insignificant thereby. Both is at short notice seen very improbable.

We already saw that it is not compellingly necessary the factorizing problem to solve, in order to decode a message. Actually it is sufficient <math> \ varphi (N)< for /math> or more exactly a multipleto know kgV from P1 and q-1 to. From this completely a suitable exponent D can be computed similar to as during the generation of key, since with this computation by means of the extended Euclidean algorithm the prime factorization is not needed.

Assumed to a Nbecame several pairs of exponent (e, D) and/or. (e', d') used. Then such a multiple could easily from possibly a pair (e', d') to be computed.

In this special case the decoding would be far less difficult than the factorizing problem. It is open whether this alsogenerally case applies. The system of Rabin is contrary to RSA a publication IC key system, it is proven for which that it is at least as difficult as the factorizing problem.

practical security

RSA usually becomes in hybrid procedureswith symmetrical coding procedures combines. Coincidentally a meeting key for a symmetrical coding is generated, which by RSA coded and together with the message will then transfer.

With the signature not the entire message but only a Hashwert is marked. Thatsymmetrical keys and/or. the Hashwert are relatively short thereby. To the symmetrical key thus math

< K_> applies {sym} < N = p \ q /math< cdot>.

Therefore the symmetrical key with only one RSA coding can be coded. For security from RSA are prime numbers alsoover 100 places necessarily. Therefore a symmetrical key could be coded also over 200 places.

As very surely classified algorithms for symmetrical coding are 3DES and AES. These use 112, 128 or maximally 168 bits or about 40 decimal places.Thus breed Force attack is to be excluded actually. A safe Hashfunktion such as SHA-1 produces function values with only 160 bits according to approximately 50 decimal places and/or. 40 hexadecimal digits. Thus signature procedures can be realized by means of RSA, which needs only one coding step.

Security and thosePerformance of the overall system is limited by the security of the publication IC key procedure, if only as surely classified algorithms and the choice keys are used as sufficiently coincidental be regarded can.

to show

proof around the correctness of the RSA procedure,the following congruence must be proven:

<math> a^ {OD} \ equiv A \ mod N< /math> for all <math> A< /math> with <math> 0 \ leq A < N< /math>

Is

  • <math> A< /math> the plain language, which is decoded en and afterwards again,
  • < math> N=pq< /math> the product of two prime numbers <math> p \ neq q< /math>,
  • < math> e< /math> the coding exponentwith <math> \ operator name {ggT} (e, \ varphi (N)) = 1< /math>,
  • < math> D< /math> the clear decoding exponent with <math> OD \ equiv 1 \ mod {\ varphi (N)}</math>.

The statement that <math> OD \ equiv 1 \ mod {\ varphi (N)}</math> , is equivalent to the existence of a whole number math <u> /math< applies> with <math> u \ varphi (N) =ed-1< /math>. In addition is <math> \ varphi (N) = (P1) (q-1)< /math> because of the Multiplikativität of <math> \ varphi< /math>.

After choiceby <math> A< /math> and <math> N< /math> now math <\> operator name is {ggT} (A, N) \ in \ {1, p, q \}< /math>, because for <math> A \ equiv 0 \ mod N< /math> nothing is to be shown.


In the case <math> \ operator name {ggT} (A, N) =1< /math> math

< a^> {OD} \ equiv a^ {u applies \, \ varphi (N) for +1} \ equiv (a^ {\ varphi (N)}) ^ua \ equiv A \ mod N< /math>,

there <math> a^ {\ varphi (N)} \ equiv 1 \ mod N< /math> afterthe sentence of Euler.


In the case <math> \ operator name {ggT} (A, N) \ neq 1< /math> we may assume without restriction that <math> \ operator name {ggT} (A, N) =p< /math>. We receive the following two congruences:

  • <math> a^ {OD} \ equiv A \ mod p< /math>, there <math> A \ equiv 0 \ mod p< /math> because of <math> p|A< /math>
  • <math> a^ {OD} \ equiv a^ {u \, \ varphi (N) +1} \ equiv a^ {u (P1) (q-1) +1} \ equiv(a^ {q-1}) ^ {u (P1)}A \ equiv A \ mod q< /math>, there <math> a^ {q-1} \ equiv 1 \ mod q< /math> after the small sentence of Fermat

with that Chinese remainder set now math <a^> {OD} \ equiv A follows \ mod N< /math>.

optimization

it is not necessarily <math> e< /math> to determine in such a manner,that the congruence <math> \ operator name {ggT} (e, \ varphi (n)) = 1< /math> one fulfills.

Rather it is enough out <math> to e< /math> to determine in such a manner that the congruence <math> \ operator name {ggT} (e, \ operator name {kgV} (P1, q-1)) = 1< /math> one fulfills. The advantage with this procedure is in the size of the Modulus for the computationby <math> D< /math>, because this now and thus the computation of math D </math> became< smaller> faster to be accomplished can.

For the numbers <math> p=11< /math> and <math> q=13< /math> math <\> varphi (p \ cdot q) /math< results in> 120. The smallest common multiple of <math> P1< /math> and <math> q-1< /math> is only 60(it must be a divisor of 120) and thus maximally half as largely as the result of the φ-function, there <math> P1< /math> and <math> q-1< /math> have at least the factor 2 together. In binary notation is thus kgV at least around a bitmore briefly.

Proof

the proof runs majority similar to the proof for the original RSA system. It exists the only following difference.

There kgV the multiple of <math> P1< /math> and <math> q-1< /math> is, the following two rules apply:

  • <math> \ operator name {kgV} (P1, q-1) = r \ cdot (P1)< /math>
  • <math> \ operator name {kgV} (P1, q-1) = s \ cdot (q-1)< /math>

We differentiate between three cases.

Case 1: <math> \ operator name {ggT} (A, n) =1< /math>

Here we receive two congruences:

  • <math> a^ {e \ cdot D} \ equiv a^ {u \ cdot \ operator name {kgV} (P1, q-1) +1} \ equiv a^ {u \ cdot \ operator name {kgV} (P1, q-1)} \ cdot A \ equiv a^ {u \ cdot (P1) \ cdot r} \ cdot A \ equiv A \ mod p< /math>, after the small sentence of Fermat
  • < math> a^ {e\ cdot D} \ equiv a^ {u \ cdot \ operator name {kgV} (P1, q-1) +1} \ equiv a^ {u \ cdot \ operator name {kgV} (P1, q-1)} \ cdot A \ equiv a^ {u \ cdot s \ cdot (q-1)} \ cdot A \ equiv A \ mod q< /math>, after the small sentence from Fermat

to that Chinese remainder set follows now <math> a^ {e \ cdot D} \ equiv A \ mod n< /math>.

Case 2: <math> p|A< /math>

  • <math> a^ {e \ cdot D} \ equiv 0 \ equiv A \ mod p< /math>, there <math> A< /math> by <math> p< /math> one divides.
  • <math> a^ {e \ cdot D} \ equiv a^ {u \ cdot \ operator name {kgV} (P1, q-1) +1} \ equiv a^ {u \ cdot \ operator name {kgV} (P1, q-1)} \ cdot A \ equiv a^ {u \ cdot s \ cdot (q-1)} \ A cdot \ equiv A \ mod q< /math>, afterthe small sentence of Fermat

after the Chinese remainder set again math <a^> {e follows \ cdot D} \ equiv A \ mod n< /math>.

Case 3: <math> q|A< /math>

similar to case 2

< math> \ Rightarrow q.e.d< /math>

RSA is not a prime number test

if <math> p< /math> and <math> q< /math> Prime numbers are,functions the RSA procedure. Turned around it cannot be concluded however from the functioning RSA procedure that <math> p< /math> and <math> q< /math>Prime numbers are, because with Carmichael numbers the procedure functions, although Carmichael numbers are not prime numbers.

Proof

given:

  • <math> n=p \ C /math< cdot>, whereby <math> c= \ prod q_i< /math> a Carmichael numberis
  • <math> q_i - 1 | c1< /math>, Eigenschaft von Carmichael Number
  • < math> \ varphi (n) = (P1) (c1)< /math>, false acceptance, since it is accepted that <math> C< /math> a prime number is
  • <math> (P1) (c1) = (q_i-1) \ b_i /math< cdot>, because <math> c1< /math> by <math> q_i-1< /math> math
  • < \> operator name is divided {ggT} (e, (P1) (c1))=1< /math>
  • <math> D \ cdot e \ equiv 1 \ mod {(P1) (c1)}</math>

To show:

<math> a^ {D \ cdot e} \ equiv A\ mod n< /math>

We regard now the prime divisor <math> p< /math>

Case 1: <math> p | A< /math>

<math> a^ {D \ cdot e} \ equiv 0 \ equiv A \ mod p< /math>

Case 2: <math> p \ nmid A< /math>

<math> a^ {D \ cdot e} \ equiv a^ {(P1) (c1)} \ A cdot \ equiv A \ mod p< /math>

We regard nowthe prime divisors <math> q_i< /math> by <math> c_i< /math>

Case 1: <math> q_i | A< /math>

<math> a^ {D \ cdot e} \ equiv 0 \ equiv A \ mod {q_i}< /math>

Case 2: <math> q_i \ nmid A< /math>

<math> a^ {D \ cdot e} \ equiv a^ {(q_i-1) (b_i)} \ A cdot \ equiv A \ mod {q_i}< /math>

Independently of the number <math> A< /math> follows that from that Chinese remainder set that <math> a^ {e cdot \ D} \ equiv A \ mod n< /math>.

<math> \ Rightarrow q.e.d< /math>

This proof withstands obviously also if <math> n< /math> the product from two Carmichael numbers is.

complete example

pre-working

specified the aboveSteps are to be described now by a complete example. In order to code a text, first letters must be converted in figures. In addition one uses in practice z. B. the ASCII - Code. Here arbitrarily the following allocation is selected:

A=01B=02 C=03 etc. (00 = blank)

in addition it is accepted that in each case three indications are combined into a number. The letter sequence AXE reaches thus 012420. The smallest number which can be coded is then 000000 (three blanks), the largest 262626 (ZZZ). ThatModulus <math> N = p \ cdot q< /math> 262626 must be thus larger.

Plain language:  W I K I P E D IN GENERAL coding: 230911 091605 040901

key production

first is selected secretly two prime numbers, e.g. <math> p=307< /math> and <math> q=859< /math>. Thusarises:

<math> N = p \ cdot q = 263713< /math>

<math> \ varphi (N) = (P1) \ cdot (q-1) = 262548< /math>

<math> e = 1721< /math> (coincidentally, divisor-strangely too <math> \ varphi (N)< /math>)

< math> D = 1373< /math> (the multiplicative inverse too <math> e \ bmod \ varphi (N)< /math> with the help of the extended one Euclidean algorithm)

Public key: <math> e = 1721< /math> and <math> N = 263713< /math>

Secret key: <math> D = 1373< /math> and <math> N = 263713< /math>

coding

C n = K n e mod N   for n=1,2,3 (,…) C 1 = 230911 1721 mod 263713 C1 = 001715 C 2 = 091605 1721 mod 263713 C 2 = 184304 C 3 = 040901 1721 mod 263713 C 3 = 219983

decoding

K n = C n D mod N   for n=1,2,3 (,…) K1 = 001715 1373 mod 263713 K 1 = 230911 K 2 = 184304 1373 mod 263713 K 2 = 091605 K 3 = 219983 1373 mod 263713 K 3 = 040901

signature (coding with the secretKey)

 C n = K n D mod N C 1 = 230911 1373 mod 263713 C 1 = 219611 C 2 = 091605 1373 mod 263713 C 2 = 121243 C 3 = 040901 1373 mod 263713 C 3 = 138570

verification (decoding with the public key)

 K n = C n e mod N K 1 = 219611 1721 mod 263713 K 1 = 230911 K 2 = 121243 1721 mod 263713 K 2 =091605 K 3 = 138570 1721 mod 263713 K of 3 = 040901

areas of application

See also

Web on the left of

 

  > German to English > de.wikipedia.org (Machine translated into English)