Die beiden großen Public-Key Teilbereiche sind Verschlüsselung und digitale Signaturen (= digitale Unterschriften).
... zeigt die Analogie in der Anwendung - die Asymmetrie in der Anwendung (öffentlicher vs geheimer Schlüssel) zeigt sich in den Dingen, die
Nur einer darf die gesendete Nachricht entschlüsseln, nämlich der Besitzer des zum öffentlichen Schlüssel passenden geheimen Schlüssels.
Aber alle dürfen an den einen verschlüsselte Nachrichten senden, das geht, da der dafür notwendige öffentliche Schlüssel allen bekannt ist.
Bei der Signatur gilt:
Nur einer darf die korrekte Signatur (Unterschrift) erzeugen können, nämlich der Besitzer des zum öffentlichen Schlüssel passenden geheimen Schlüssels.
Aber alle dürfen die Signatur überprüfen können das geht, da der zum privaten Schlüssel passende öffentliche Schlüssel allen bekannt ist.
...zeigt, warum das nicht alles gewesen sein kann, was man zum Signieren braucht. Rechnen mod n begrenzt alle Information, die man hat auf die Bitlänge von n
Beispiel:
wir wollen einen langen (Vertrags-)Text (PDF) unterschreiben
00000000 25 50 44 46 2d 31 2e 33 0a 25 c7 ec 8f a2 0a 35 |%PDF-1.3.%Çì...5|
00000010 20 30 20 6f 62 6a 0a 3c 3c 2f 4c 65 6e 67 74 68 | 0 obj.##/Length|
00000020 20 36 20 30 20 52 2f 46 69 6c 74 65 72 20 2f 46 | 6 0 R/Filter /F|
00000030 6c 61 74 65 44 65 63 6f 64 65 3e 3e 0a 73 74 72 |lateDecode>>.str|
00000040 65 61 6d 0a 78 9c ed 5d 4b 73 1c b7 11 be ef af |eam.x.í]Ks....ï.|
00000050 98 5b 76 5d 59 08 ef c7 d1 2e 3b 76 c5 49 2a 16 |.[v]Y.ïÇÑ.;vÅI*.|
00000060 37 52 95 55 3e 2c 49 89 54 b4 e4 c6 a2 36 ae f2 |7R.U>,I.T.äÆ.6.ò|
00000070 1f ca 9f d4 21 c0 3c d0 3d 33 bd 33 43 d1 24 57 |.Ê.Ô!À<Ð=3.3CÑ$W|
00000080 d4 da 55 ae 5e 0c 06 c0 34 ba fb eb 07 40 ff 5a |ÔÚU.^..À4ºûë.@ÿZ|
00000090 70 26 64 c1 d3 bf 0d 71 76 35 7b f6 dc 15 17 37 |p&dÁÓ..qv5{öÜ..7|
...
bei einem Vertragstext von einer DIN A4 Seite (3000 Zeichen) ist das eine Message m von 3000*8=24000 Bits
und wir haben einen starken RSA-Schlüssel von 2048-Bit
n=982596486168164533679068138587450785169755353624059289415533430269902156543301980948452346231423154225707198230814993348325199962226568104628565333075845055110102001513777733822186085910101000971046266247429174698114691926560611342709382763139596083197537103114770536908672391590105944592251557906143423217780862508367523890586749066935355289953519893896713070059149756252671523659055578969907046141090712181640128224480409352033671783234281312447922211039322683639827785375953048086752423328929034805397916713370525669627143719501631537708814980908413840526128966499935897121680247985318025315384432533966964970611
e=65537
Sobald wir modulo n rechnen, kürzen wir alles auf 2048 Bits, d.h. es geht von dem Text 22000 Bits an Information verloren. Oder genauer, wenn man die Message m signiert, dann kommt dasselbe heraus, wenn man die Message m+n oder m+2*n oder m+3*n ... signiert. Man hätte also eine gültige Signatur für einen veränderten Vertragstext.
Man muss es also irgendwie schaffen die gesamte Information aller 24000 Bits in eine 2048-Bit-Signatur zu pressen.
Hierfür hat man in den Datenstrukturen einen Mechanismus: Hashfunktionen bilden ein riesiges Universum aus Werten auf eine überschaubare Menge von Plätzen ab. Man könnte die klassischen Hashfunktionen nehmen, wenn sie nicht dasselbe Problem aufwerfen würden, wie das Rechnen mod n. Die Hashfunktionen aus den Datenstrukturen (diese hier) sind unsicher.
Die Kryptographie hat inzwischen einige sichere Hashfunktionen (secure hash functions) etabliert. Manche sicher geglaubte Funktionen wie MD5 sind gebrochen, die Weiterentwicklungen umfassen
Mit Hilfe einer Hashfunktion h signiert man also nicht die Message m, sondern ihren Hashwert h(m). Die Ausgabelänge der modernen Hashfunktionen besteht meist aus 256 oder 512 Bits.
Bitte den roten Kasten beachten: benutzt man gleichzeitig
braucht man zwei Schlüsselpaare. Am besten sieht man das an RSA, wenn man einen Schlüsselbesitzer dazu verleiten kann, eine Nachricht m' zu signieren. Durch die resultierende Potenzierung von m' hoch d entsteht das Gleiche wie bei der Entschlüsselung. Also die Signatur wäre der entschlüsselte Text.
Die Alternative zu RSA-Signaturen sind diejenigen deren Sicherheit auf dem diskreten Logarithmus basiert (wie Diffie-Hellman oder ElGamal). Der FIPS-186-4 Standard (PDF) definiert eine ans ElGamal-Verschlüsselungssystem angelehnte Vorgehensweise. Diese enthält eine kleine Beschleunigung und eine Schlüsselverkürzung, weswegen ein großer Primteiler q von p-1 eine wichtige Rolle spielt. Die Bitlänge von p wird dort L genannt, die Bitlänge von q heißt N. Bei L=2048 wird also modulo 2048 Bit langen Zahlen gerechnet, die Ergebnisse werden aber in N=256 Bit codiert. Das spart Platz und (da manche Operanden nur 256 Bit haben) auch Rechenzeit
Die Parameter sind p, g, y wie bei ElGamal, der dortige geheime Schlüssel a heißt hier x. Die Parametererzeugung erzwingt, dass g^x=1 mod p, das ist später für die Korrektheit des Verfahrens wichtig.
Lesen Sie die zu den beiden oberen Abschnitten auf der Folie die Abschnitte 4.6 und 4.7 im FIPS-Standard und verfolgen Sie die Rechnungen.
Der letzte Abschnitt auf der Folie zeigt, warum die Verifikation stimmt, falls die Signatur korrekt erzeugt wurde.
Übung: Programmieren Sie! Auch dieses Verfahren versteht man besser, nachdem man es programmiert hat. Sie brauchen die Primzahlen p und q nicht selbst zu erzeugen, sie finden einige p zu einem vorgegebenen q auf dem www-crypto Server.
Ausblick: morgen kommt ein kurzer Abschnitt über die Erzeugung von p und q hinzu, Sie können diese Woche des Selbststudiums und der Nachbereitung also komplett Ihrer DSA-Implementierung widmen. Und bitte rückfragen, wenn etwas unklar.