imported>Took No edit summary |
imported>Took m (typo) |
||
Line 1: | Line 1: | ||
Der RSA- |
Der RSA-Algorithmus (Ronald Rivest, Adi Sharmiv, Len Adelmans, 1976/77) ist ein Verschlüsselungs-Algorithmus und zwar ein sogenannter "Public-Key-Algorithmus". Zum ver- und entschlüsseln werden verschiedene Keys benutzt. Es ist nicht möglich mit "vertretbarem Aufwand" den einen aus dem anderen Schlüssel zu berechnen. Beide Schlüssel sind natürlich mathematisch verwandt... |
||
Der öffnetliche Public-Key (V-Schlüssel) wird öffentlich zugänglich gemacht, der Secret-Key (E-Schlüssel) ist dagegen geheim. |
Der öffnetliche Public-Key (V-Schlüssel) wird öffentlich zugänglich gemacht, der Secret-Key (E-Schlüssel) ist dagegen geheim. |
||
Line 9: | Line 9: | ||
== Satz 1 (RSA-Algo) == |
== Satz 1 (RSA-Algo) == |
||
Es seien p, q Primzahlen (P), q |
Es seien p, q Primzahlen (<math>\Bbb{P}</math>), q <math/ne</math> 0, n := pq, m := (p-1)*(q-1), e <math>\in \{1, .., m-1\}</math> mit ggT(e, m) = 1 und d <math>\in \{1, .., m-1\}</math> sei Representant von <math>\overline{d}</math> := <math>\overline{e^{-1}} \in \Bbb{P}_m</math>. |
||
(e, n) ist der V-Key, (d, n) der E-Key. |
Das Tupel (e, n) ist der V-Key, (d, n) der E-Key. |
||
Sei nun a |
Sei nun a <math>\in \{1, .., n-1\}</math> die zu übermittelnde Nachricht. |
||
Dann heist der Representant c Chiffre zu a. c ist aus 1,.., n-1 von Restklasse c def durch (Restklasse a)<sup>e</sup> element von Z<sub>n</sub>. (Verschlüsseln) |
Dann heist der Representant c Chiffre zu a. c ist aus 1,.., n-1 von Restklasse c def durch (Restklasse a)<sup>e</sup> element von Z<sub>n</sub>. (Verschlüsseln) |
||
und es gilt: a |
und es gilt: <math>a \equiv c_d \pmod{n}</math> (Entschlüsseln) |
||
== Beispiel == |
== Beispiel == |
||
Das Verfahren soll anhand eines Beispiels verdeutlicht werden. Die hier benutzten Primzahlen (1- bzw. 2-stellig) sind natürlich viel zu klein um das Verfahren sicher zu machen, da ja die Sicherheit eben daher kommt, das die Primzahlen derart groß sind (z.B. 100-stellig), das eine Faktorisierung der Schlüssel praktisch nicht möglich ist. |
|||
Key-Paar erzeuigen: |
|||
=== Key-Paar erzeugen === |
|||
p sei def durch 7, q def durch 11 |
|||
Sei p := 7, q := 11 |
|||
damit ist n = 77, m = 60 |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
a<sub>0</sub>=60<br> |
a<sub>0</sub>=60<br> |
||
Line 37: | Line 39: | ||
60=8*7+4 <=> 4 = 60- 8*7 = a<sub>2</sub><br> |
60=8*7+4 <=> 4 = 60- 8*7 = a<sub>2</sub><br> |
||
7=1*4+3 <=> 3 = 7- 1*4 = a<sub>3</sub><br> |
7=1*4+3 <=> 3 = 7- 1*4 = a<sub>3</sub><br> |
||
4=1*3+1 <=> 1 = 4- 1*3 = a<sub>4</sub |
4=1*3+1 <=> 1 = 4- 1*3 = a<sub>4</sub> |
||
1=4- 1*3 = 4- 1*(7-1*4) =<br> |
1=4- 1*3 = 4- 1*(7-1*4) =<br> |
||
Line 43: | Line 45: | ||
2*60 - 17*7 |
2*60 - 17*7 |
||
<math>-17 \equiv 43 \pmod{60} </math><br>=><br> |
|||
-17 ist kongurent zu 43 bzgl. modulo 60 |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
V-Key (Public) (e, n) = (7, 77)<br> |
V-Key (Public) (e, n) = (7, 77)<br> |
||
E-Key (Secret) (d, n) = (43, 77) |
E-Key (Secret) (d, n) = (43, 77) |
||
=== Verschlüsseln === |
|||
Nun will ein Versender die Nachricht a=42 mit dem V-Key (7, 77) verschlüsseln: |
Nun will ein Versender die Nachricht a = 42 mit dem V-Key (7, 77) verschlüsseln: |
||
c \equiv 42<sup>7</sup> \pmod{77} |
c \equiv 42<sup>7</sup> \pmod{77} |
||
Line 65: | Line 67: | ||
Die Chiffre c=70 geht nun auf die Reise |
Die Chiffre c=70 geht nun auf die Reise |
||
=== Entschlüsseln === |
|||
⚫ | |||
⚫ | |||
a \equiv 70<sup>43</sup> \pmod{77}<br> |
a \equiv 70<sup>43</sup> \pmod{77}<br> |
||
Line 79: | Line 80: | ||
== Sicherheit == |
== Sicherheit == |
||
Ein böser Bube, der den Public-Key und die Chiffre abgehört hat, kann die Chiffre nicht zur Nachricht entschlüsseln, denn insbesondere fehlt ihm d |
Ein böser Bube, der den Public-Key und die Chiffre abgehört hat, kann die Chiffre nicht zur Nachricht entschlüsseln, denn insbesondere fehlt ihm d. |
||
d kann er aus e nur erhalten, wenn er m kennt. Um aber m aus dem Public-Key zu erhalten, müsste er n faktorisieren und das ist für große n auch mit größter Rechenleistung bisher nicht möglich. |
d kann er aus e nur erhalten, wenn er m kennt. Um aber m aus dem Public-Key zu erhalten, müsste er n faktorisieren und das ist für große n auch mit größter Rechenleistung bisher nicht möglich. |
||
=== Beispiel === |
|||
Wie lange brauchen 100 Mio StandartPC's um Schlüssel einer gewissen länge zu knacken? |
|||
{| border="1" cellpadding="2" cellspacing="0" style="background: #f9f9f9; border: 1px solid #aaaaaa; border-collapse: collapse; white-space: nowrap; text-align: left" |
{| border="1" cellpadding="2" cellspacing="0" style="background: #f9f9f9; border: 1px solid #aaaaaa; border-collapse: collapse; white-space: nowrap; text-align: left" |
||
|- |
|- |
||
Line 102: | Line 104: | ||
|} |
|} |
||
Achtung: In letzter Zeit wurden dann doch verfahren entdeckt die diese faktorisierung schneller als in diesem Beispiel angenommen durchführen können. Effektiv hat sich aber dadurch bei aussreichend langen Schlüsseln nichts an der Sicherheit des RSA-Verfahrens geändert. |
'''Achtung:''' In letzter Zeit wurden dann doch verfahren entdeckt die diese faktorisierung schneller als in diesem Beispiel angenommen durchführen können. Effektiv hat sich aber dadurch bei aussreichend langen Schlüsseln nichts an der Sicherheit des RSA-Verfahrens geändert. |
||
Revision as of 05:30, 25 February 2006
Der RSA-Algorithmus (Ronald Rivest, Adi Sharmiv, Len Adelmans, 1976/77) ist ein Verschlüsselungs-Algorithmus und zwar ein sogenannter "Public-Key-Algorithmus". Zum ver- und entschlüsseln werden verschiedene Keys benutzt. Es ist nicht möglich mit "vertretbarem Aufwand" den einen aus dem anderen Schlüssel zu berechnen. Beide Schlüssel sind natürlich mathematisch verwandt...
Der öffnetliche Public-Key (V-Schlüssel) wird öffentlich zugänglich gemacht, der Secret-Key (E-Schlüssel) ist dagegen geheim.
SSL und PGP arbeiten mit dem RSA-Algo.
Die zugrundeliegende Idee ist, das es äusserst schwierig ist, das Produkt zweier großen Primzahlen (z.B. 100 Stellen) in die Primfaktoren zu zerlegen.
Satz 1 (RSA-Algo)
Es seien p, q Primzahlen (<math>\Bbb{P}</math>), q <math/ne</math> 0, n := pq, m := (p-1)*(q-1), e <math>\in \{1, .., m-1\}</math> mit ggT(e, m) = 1 und d <math>\in \{1, .., m-1\}</math> sei Representant von <math>\overline{d}</math> := <math>\overline{e^{-1}} \in \Bbb{P}_m</math>.
Das Tupel (e, n) ist der V-Key, (d, n) der E-Key.
Sei nun a <math>\in \{1, .., n-1\}</math> die zu übermittelnde Nachricht.
Dann heist der Representant c Chiffre zu a. c ist aus 1,.., n-1 von Restklasse c def durch (Restklasse a)e element von Zn. (Verschlüsseln)
und es gilt: <math>a \equiv c_d \pmod{n}</math> (Entschlüsseln)
Beispiel
Das Verfahren soll anhand eines Beispiels verdeutlicht werden. Die hier benutzten Primzahlen (1- bzw. 2-stellig) sind natürlich viel zu klein um das Verfahren sicher zu machen, da ja die Sicherheit eben daher kommt, das die Primzahlen derart groß sind (z.B. 100-stellig), das eine Faktorisierung der Schlüssel praktisch nicht möglich ist.
Key-Paar erzeugen
Sei p := 7, q := 11
damit ist n = 77, m = 60
Wir wählen z.B. e = 7
Nun muss das d bestimmt werden mit Hilfe des Euklidischen Algorithmus:
a0=60
a1=7
60=8*7+4 <=> 4 = 60- 8*7 = a2
7=1*4+3 <=> 3 = 7- 1*4 = a3
4=1*3+1 <=> 1 = 4- 1*3 = a4
1=4- 1*3 = 4- 1*(7-1*4) =
2*4 - 1*7 = 2(60-8*7) - 1*7 =
2*60 - 17*7
<math>-17 \equiv 43 \pmod{60} </math>
=>
d = 43
Damit haben wir die Keys:
V-Key (Public) (e, n) = (7, 77)
E-Key (Secret) (d, n) = (43, 77)
Verschlüsseln
Nun will ein Versender die Nachricht a = 42 mit dem V-Key (7, 77) verschlüsseln:
c \equiv 427 \pmod{77}
424 \equiv 1764 \equiv -7 \pmod{77}
423 \equiv 42* (-7) \equiv 14 \pmod{77}
Aus 424 \equiv 49 \pmod{77}
und 423 \equiv 14 \pmod{77}
folgt nun => 427 \equiv 14*49 \equiv 70 \pmod{77}
Die Chiffre c=70 geht nun auf die Reise
Entschlüsseln
Wir haben nun die Chiffre c=70 erhalten und wollen sie entschlüsseln mit Hilfe des E-Key(Secret) (d, n) = (43, 77).
a \equiv 7043 \pmod{77}
7043 = 703*2*7+1
703 \equiv 42 \pmod{77} (Bemerkung: das hier wieder 42 steht ist Zufall in diesem Beispiel und hat nix mit der Nachricht a=42 zu tuen.)
706 \equiv 422 \equiv -7 \pmod{77}
7042 \equiv (-7)7 \equiv -28 \pmod{77}
7045 \equiv (-28)*70 \equiv 42 \pmod{77}
Damit haben wir die Nachricht a=42 erhalten.
Sicherheit
Ein böser Bube, der den Public-Key und die Chiffre abgehört hat, kann die Chiffre nicht zur Nachricht entschlüsseln, denn insbesondere fehlt ihm d.
d kann er aus e nur erhalten, wenn er m kennt. Um aber m aus dem Public-Key zu erhalten, müsste er n faktorisieren und das ist für große n auch mit größter Rechenleistung bisher nicht möglich.
Beispiel
Wie lange brauchen 100 Mio StandartPC's um Schlüssel einer gewissen länge zu knacken?
Länge | Zeit |
429 | 14,5 sek |
512 | 22 Minuten |
700 | 153 Tage |
1024 | 280.000 Jahre |
Achtung: In letzter Zeit wurden dann doch verfahren entdeckt die diese faktorisierung schneller als in diesem Beispiel angenommen durchführen können. Effektiv hat sich aber dadurch bei aussreichend langen Schlüsseln nichts an der Sicherheit des RSA-Verfahrens geändert.
Beweiss vom Satz 1
Will den jemand sehen? Ist sehr lang und kompliziert...