e-dokumen.id

Kryptographie27. Juli 2014Christian StrateSommersemester 2014Dozent: Prof. RuppertDiese Art des Faktorisierens nennen wir ”naives Faktoriesierungsverfahren“Bemerkung: Die Bedingung t2 n ist äquivalent mit t n, also t b nc. Kann man schnell t b nc berechnen, so kann man t2 n durch die Bedingung t b nc ersetzen.Bemerkung:Primzahlen. Wie lange braucht man um festzustellen, dass n eine Primzahl ist? Man muss mit t bis ungefähr n gehen.Es folgen eine etwas merkwürdige Definition der Polynomial- und Exponentiallaufzeit,sowie die Definitionen gT, ggT, gV, kgV. Seite 5Achtung:gT (0, 0) Z; und insbesondereggT (0, 0) 03.3 Der euklidische AlgorithmusSeite 7ff.3.4 Fibonacci-ZahlenSeite 10ff.Laufzeit des euklidischen Algorithmus:ggT (a, b), a, b N, a b benötigt maximal 4.785 log10 a Divisionen mit Rest3.5 Der erweiterte euklidische AlgorithmusSeite 12ff.Beispiel zum ersten Satz; Satz 2 Mathe3-Skript:ggT (15, 9) ggT (3 · 5, 32 ) 3 ( 1) · 15 2 · 9Für ”kleine“ Zahlen kann man auch manchmal folgendes Verfahren finden: Schreibe anim euklidischen Algorithmus von ”unten nach oben“ bis man an als Linearkombinationvon a0 und a1 erhält.ggT (12345, 987)Beispiel:3 15 2 · 6 (501 1 · 486) 2 · (486 32 · 15) 501 3 · 486 64 · (501 1 · 486) 65 · (12345 12 · 987) 67 · (987 1 · 501) 65 · 12345 847 · 987 67(12345 12 · 987)xi xi 2 qi 2 · xi 1 ,yi yi 2 qi 2 · yi 110 501 3 · 486 64 · 15 65 · 501 67 · 486 132 · 12345 1651 · 987

Kryptographie27. Juli 2014Christian StrateSommersemester 2014Dozent: Prof. Ruppert3.6 Die Gleichung ax by cSeite 14f.Vorbemerkung zum ersten Satz:Sind x0 , y0 Z mit ggT (a, b) x0 a y0 b,so gilt für alle k Z :ggT (a, b) (x0 kb) · a (y0 ka) · berster Teil des besagten Satzes:a, b Z, (a, b) 6 (0, 0) ax by c ist genau dann Lösbar, wenn ggT (a, b) cessenzielle Folgerung:a, b Z, ggT (a, b) 1 x0 , y0 Z. ax0 by0 1,{(x, y) Z Z : ax by 1} {(x0 bm, y0 am) : m Z}a · x b · y c, seien a 4, b 2, c 1, x 1, y 1.5 4 3 1 aber ggT (4, 2) 2und a 1 a 1 6 23.7 KongruenzenSeite 15ff.Verträglichkeit der Äquivalenzrelation mit Addition und Multiplikation.a b a bab abVorbemerkung zum ersten Satz:Seien m1 , m2 N mit ggT (m1 , m2 ) 1 und a1 , a2 Z. Mit dem erweiterteneuklidischen Algorithmus findet man u, v Z mit um1 vm2 1. Dann lösta a2 um1 a1 vm2 das Gleichungssystem x a1 mod m1 , x a2 mod m21 um1 vm2a a2 um1 a1 vm2Beispiel:Bestimme die kleinste Lösung von x 2 mod 25, x 5 mod 52 in natürlichenZahlen. Es ist ggT (25, 52) 1, das Gleichungssystem ist lösbar, Eindeutigkeitmodulo 25 · 52 1300Wir wenden den euklidischen Algorithmus auf 52 und 25 an:52 2 · 25 225 12 · 2 12 2·1 01 25 12 · 2 25 12 · (52 2 · 25)11 ( 12) · 52 25 · 25

Kryptographie27. Juli 2014Christian StrateSommersemester 2014Dozent: Prof. RuppertAlso: 1 ( 12) · 52 25 · 25Sei a 2 · ( 12) · 52 5 · 25 · 25 1877a löst die Kongruenzgleichungen. 1877 1300 577 ist die kleinste Lösung in dennatürlichen Zahlen.Nicht jedes Kongruenzgleichungssystem ist lösbar.Beispiel:x 4 mod 45, x 5 mod 54Hier ist ggT (45, 54) 9. Wir betrachten die Gleichungen modulo 9, dem ggT.x 4 mod 45 x 4 mod 9x 5 mod 54 x 5 mod 9Das geht nicht gleichzeitig!Einheit a Z/mZ, also ein Element von (Z/mZ) 3 :(Z/mZ) {a : 0 a m 1, ggT (a, m) 1}Eulersche ϕ-Funktion Definition - Seite 17, Eigenschaften - Seite 18 bzw. Seite 423.8 Der chinesische RestsatzSeite 18ff.Satz:(Zusammenfassung von Kongruenzgleichungen)Seien m1 , . . . , mr paarweise teilerfremd, a1 , . . . , ar Z und a Z mit a ai mod mi für i 1, . . . , r (wie im chinesischen Restsatz). Für x Z sindäquivalent: x ai mod mi x a mod m1 . . . mrBeweis:” ”Sei x Z mit x ai mod mi für i 1, . . . , r. Wegen a ai mod mi , folgtx ai a mod mi , mi x a, m1 . . . mr x a, x a mod m1 . . . mr” ”x a mod m1 . . . mr x a mod mia ai mod mi x ai mod mi .Beweisskizze für φ(mn) φ(m)φ(n) im Fall ggT (m, n) 1.3Nochmal zur Erinnerung: Z/mZ bezeichnet den Restklassenring modulo m12

Kryptographie27. Juli 2014Christian StrateSommersemester 2014Dozent: Prof. RuppertMan zeigt, dass die Abbildung{0 a mn 1 : ggT (mn, a) 1} {0 b m 1 : ggT (m, b) 1} {0 c n 1 : ggT (n, c) 1}a (a mod m, a mod n)wohldefiniert und injektiv ist; der chinesiche Restsatz liefert, dass sie surjektiv ist. Da die Abbildung also bijektiv ist, sind die Mächtigkeiten vonDefinitionsmenge und Bild gleich, ergo φ(mn) φ(m)φ(n).In der Algebra taucht der chinesische Restsatz manchmal in folgender Form auf:Satz:Seien m1 , . . . , mr N paarweise teilerfremd.Dann definiertZ/m1 .mr Z Z/m1 Z . . . Z/mr Zeinen Ringisomorphismus.Beispiel:Z/60Z Z/(4 3 5)Z . . .13

Kryptographie27. Juli 2014Christian StrateSommersemester 2014Dozent: Prof. Ruppert4 PrimzahltestsKapitel 44.1 Kleine TeilerSeite 1f.4.2 Die Sätze von Fermat und EulerSeite 2ff.Die Ordnung einer Gruppe G (Z/nZ) wird repräsentiert durch #(Z/nZ) Lemma:Für eine Primzahl p und a, b, Z gilt(a b)p ap bp mod pKleiner Satz von Fermat:Für eine Primzahl p und a Z gelten die folgenden zwei Aussagen, sowie die dritteunmittelbar hieraus gefolgerte: ap a mod p gcd(a, p) 1 ap 1 1 mod p an 1 6 1 mod n n zusammengesetztSatz von Euler:Seien n N und a Z gegeben mit gcd(a, n) 1, so giltaϕ(n) 1 mod n4.3 Schnelles Potenzieren - Die square-and-multiply-MethodeSeite 4ff.4.4 Der Fermatsche PrimzahltestSeite 6ff.Definitionen einer Pseudoprimzahl (Seite 7) sowie einer wahrscheinlichen Primzahl(Seite 8) und insbesondere (Seite 11).zusätzliche Bemerkung:(2) Es gilt limx π(x)xlog x 1,d.h. π(x) π (x)lim F,ax π(x)xlog x(Primzahlsatz)Man kann zeigen: 0Im Verhältnis zu Primzahlen gibt es wenige Pseudoprimzahlen.14

Kryptographie27. Juli 2014Christian StrateSommersemester 2014Dozent: Prof. Ruppert(3) Überlegung: n bestehe den Fermat-Test zur Basis a, d.h. an 1 1 mod nDann gibt es zwei Möglichkeiten:i) n primii) n Fermat-Pseudoprimzahl zur Basis a Fall ii) ist unwahrscheinlich wegen (2). n ist also wahrscheinlich prim. (2) Skript-Bemerkung der Seite 8Eigenschaften der Carmicheael-Zahlen:Seite 1f. sind quadratfrei, d.h. p n p2 - n, haben mindestens drei Primteiler und sindungerade. Es gibt unendlich viele Carmichael-Zahlen n Carmichael-Zahl a Z.an a mod nSatz (Korselt-Kriterium): Seite 1f.n N ist genau dann eine Carmichael-Zahl, wenn gilt:1. n zusammengesetzt2. n quadratfrei3. p n p 1 n 1 für alle Primteiler p von nBeispiel:n 561 3 · 11 · 17,1, 2X3: 2 560, 10 560, 16 560XFolgerung:Sei n N, p1 6u 1, p2 12u 1, p3 18u 1n p1 p2 p3 1296u3 396u2 36u 1Sind p1 , p2 , p3 Primzahlen, so ist n eine Carmichael-Zahl.Beweis:Seien p1 p2 p3 Primzahlen.Korselt-Kriterium: 1, 2X3:n 1 24 · 34 · u3 22 · 32 · 11 · u2 22 · 32 · up1 1 6u, p2 1 12u, p3 1 18up1 1 n 1, p2 1 n 1,p3 1 n 1.XKorselt-Kriterium ist erfüllt, also handelt es sich bei n um eine Carmichael-Zahl.Mit der Folgerung kann man praktisch leicht Carmichael-Zahlen konstruieren:u 1, p1 7, p2 13, p1 9, n 1729u 10100 289351und die zugehörigen p1 , p2 , p3 sind prim, also das zugehörige n eine CarmichaelZahl.15

Kryptographie27. Juli 2014Christian StrateSommersemester 2014Dozent: Prof. Ruppert4.5 Der Miller-Rabin-TestSeite 9ff.Lemma:Seien p eine Primzahl, a eine Zahl mit a2 1 mod p und a 6 1 mod p a 1 mod pLemma:lqp ungerade prim, p 1 2 q, q 1 mod 2 i und b a mod p, gcd(a, p) 12 b 1 mod p i {0, . . . , l 1}. b 1 mod pDefinition starke Pseudoprimzahl zur Basis a Seite 10.Erweiterte Riemansche Vermutung4 auf Seite 12.4Rieman Vermutung macht Aussagen über NS der meromorphe Fortsetzung von I(s) Pn 1161,nss C

Kryptographie27. Juli 2014Christian StrateSommersemester 2014Dozent: Prof. Ruppert5 Public-Key-KryptosystemeKapitel 55.1 ErinnerungSeite 15.2 Eine IdeeSeite 1fDieses Unterkapitel erklärt im Grunde die Idee und die notwendigen Eigenschaften derasymmetrischen Verschlüsselungsverfahren.5.3 RSASeite 2ff5.3.1 Mathematische GrundlagenSeite 2p, q P, p 6 q,N pq,ed 1 mod (p 1)(q 1), e, d N b ae mod N a bd mod N a Z.aed a mod N5.3.2 Das RSA-KryptosystemSeite 2ff. eA 1, gcd(eA , (pA 1)(qA 1)) 1 public key: (NA , eA ), private key: (NA , dA ) bi aei A mod NA (B sendet an A) ai bdi A mod NABeispiele auf Seite 4f5.4 Ein Angriff auf RSA mit dem chinesischen RestsatzSeite 5f17a, b Z

Kryptographie27. Juli 2014Christian StrateSommersemester 2014Dozent: Prof. Ruppert5.5 Faktorisierung einer RSA-Zahl N bei Kenntnis des öffentlichen undprivaten SchlüsselsSeite 6ffDer Pseudocode für die Anwendung unter bestimmten Gegebenheiten ist auf Seite 8beschrieben.5.6 Die Fermatsche FaktorisierungsmethodeSeite 8ffDie ungerade zu faktorisierende natürliche Zahl N wird als Differenz zweier Quadratzahlen dargestellt.Der Fall N pq als RSA-Zahl wird auf Seite 10f behandelt.Seite 11ff betrachtet bis zum Ende des Unterkapitels die Laufzeiten dieses Verfahrens.RSA-Zahlen sind mit der Fermatschen Faktorisierungsmethode günstig zu faktorisie1ren, wenn p q / N 4 und ungünstig, wenn q λp, λ 1. Für große RSA-Zahlengenügt q 1.1p.18

Kryptographie27. Juli 2014Christian StrateSommersemester 2014Dozent: Prof. Ruppert6 Die Pollardsche rho-Methode zur FaktorisierungKapitel 6 entfällt aus Zeitgründen.19

Kryptographie27. Juli 2014Christian StrateSommersemester 2014Dozent: Prof. Ruppert7 Kryptographische Anwendungen diskreter LogarithmenKapitel 7Vorbemerkung:Die Sicherheit von RSA beruht darauf, dass man praktisch ganz schlecht faktorisieren kann, dass man andererseits leicht und schnell potenzieren kann, (wahrscheinliche) Primzahlen erzeugen kann, ggT und ax m berechnen kann, . . .Frage:Gibt es auch andere Stellen in der Mathematik, wo Ähnliches passiert?7.1 Die multiplikative Ordnung einer Zahl a Z mod m NSeite 1Ist a Z mit ggT (a, m) 1, so gilt aϕ(m) 1 mod m. (Satz von Euler)Daher ist folgende Definition sinnvoll:ordm (a) min{n N : an 1 mod m}(Ordnung von a mod m)Beispiele:1.2.m 5, a 2; ord5 (2) 421 2 mod 5,22 4 mod 5,m 8, a 5; ord8 (5) 251 1 mod 8,52 1 mod 823 3 mod 5,24 1 mod 5Lemma:m N, a Z mit ggT (a, m) 11. Für n N0 sind äquivalent: an 1 mod m ordm (a) n2. Für n1 , n2 N0 sind äquivalent: an1 an2 mod m n1 n2 mod ordm (a)Beweis:1. “ ”Teile n durch ordm (a) mit Rest r,0 r ordm (a) 1.20n k · ordm (a) r mit k, r N0 und

Kryptographie27. Juli 2014Christian StrateSommersemester 2014Dozent: Prof. Ruppert k Daher 1 an ak·ordm (a) r aordm (a) · ar ar mod m.Aus 0 r ordm (a) folgt r 0, also n k · ordm (a), d.h. ordm (a) n“ ” k ordm (a) ordm (a) n n k · ordm (a) für ein k N0 , also an a {z } 11 mod m2.O.E. n2 n1 , n2 n1 n. Dann an1 an2 mod m n1a {z} teilerfremd zu m1an1 · an mod m 1 an mod m ordm (a) n ordm (a) n2 n1 n1 n2 mod ordm (a)Insbesondere: n1 n2 mod ordm (a) an1 an2 mod m, d.h. im Exponenten von adarf man mod ordm (a) rechnen. Was weiß man über die Ordnung ordm (a)?1. ordm (a) ϕ(m) (Folgt aus aϕ(m) 1 mod m)2. Ist p Primzahl, so gilt ordp (a) p 1 (Folgt aus kleinem Satz von Fermat ap 1 1 mod m)Aus 2 folgt: ordp (a) p 1a Z heißt Primitivwurzel modulo p, wenn ordp (a) p 1 ist.Satz:Zu jeder Primzahl p gibt es Primitivwurzeln modulo p.Beispiele:gp sei kleinste Primitivwurzel modulo p mit gp Npgp213252731121321731922352923133724167.2 Die multiplikative Gruppe des Körpers Fp - Diskrete Logarithmen5Seite 1ff.Naive Methode zur Berechnung diskreter Logarithmen Seite 2. gesucht: logg (a) mod p 2 g,a p 1 für x {0, . . . p 1} ausprobieren, ob g x a mod p gilt. min{x g x a mod p}– g x a x logg (a) mod p5Fp bezeichnet hierbei eine andere Schreibweise für Z/pZ, wobei p eine Primzahl21

Kryptographie27. Juli 2014Christian StrateSommersemester 2014Dozent: Prof. Ruppert– g x 1 es existiert keine LösungBestimmung der Ordnung eines Elements aus Fp Seite 3.7.3 Schlüsselaustausch nach Diffie-HellmannSeite 4 p P,g {2, . . . , p 2}, fA g eA mod p,eA , eB {0, . . . , p 2}fB g eB mod p kAB g eA eB mod p fBeA mod p fAeB mod p7.4 Die ElGamal-VerschlüsselungSeite 5f.Das Verfahren selbst ist nicht weiter spannend. Der interessante Teil beschränkt sich aufdie Verwendung des DH-Austauschs.Wichtig für die Sicherheit der ElGamal-Verschlüsselung ist insbesondere die ersteÜberlegung auf Seite 5, die nicht 100% äquivalent zu der Bemerkung auf Seite 6f. ist.eA public key: (pA , gA , fA ), fA gAmod pA ,Zufallszahl zi {0, . . . , pA 2} 3 eA , gA {2, . . . , p 2}zi bi gAmod pA ,ki fAzi mod pA bei A mod pA ,ci ai · ki mod pA Chiffretext: (bi , ci )A ai ci · b emod pA bipA 1 eA · ci mod pAi7.5 Massey-Omura-VerschlüsselungSeite 7f.Hierbei dürfte es sich m.E. wohl um ein lediglich für die Theorie interessantes Verfahrenhandeln, da Mechanismen eingesetzt werden müssten, um MITM-Angriffen vorzubeugen,welche sämtliche Vorteile gegenüber üblich praktizierten Verfahren zunichte machen. p P,gcd(eA , p 1) 1,dA eA 1 mod p 1, bi aeA mod p ci bei B mod p di cdi A mod p ei ddi B mod p ai mod p22eA , dA beide geheim!

Kryptographie27. Juli 2014Christian StrateSommersemester 2014Dozent: Prof. Ruppert8 Kryptographische HashfunktionenKapitel 8 Dieses Kapitel scheint lediglich erwähnt worden zu sein.23

Kryptographie27. Juli 2014Christian StrateSommersemester 2014Dozent: Prof. Ruppert9 Digitale SignaturenKapitel 99.1 EinführungSeite 1 Eigenschaften von Signaturen.9.2 Allgemeine VerfahrenSeite 1f.Unterschreiben mit einem eiben mit einem Public-Key-Verfahren unter Verwendung einer Hash-Funktion.Digitale Signatur mit Verschlüsselung.9.3 Die RSA-SignaturSeite 3(1) Schlüsselerzeugung:a) A konstruiert sich ein RSA-Schlüsselpaar: (NA , eA ) öffentlich, (NA , dA ) geheim (y xeA mod NA x y dA mod NA )b) A legt sich auf eine Hashfunktion h fest. (Praktisch: Die Hashwerte sollten NA sein)(2) Unterschreiben/Signieren eines Dokuments M:a) A berechnet den Hashwert h(M )b) Mit seinem privaten Schlüssel (NA , dA ) berechnet A die Zahl s h(M )dA mod NADie Zahl s ist die RSA-Signatur von A für das Dokument M(3) Signaturüberprüfung:Wie testet man, ob eine Signatur s für M von A stammt?a) Man berechnet den Hashwert h(M ) und mit dem öffentlichen Schlüssel (NA , eA )von A die Zahl h0 seA mod NA .b) Gilt h0 h(M ), so wird die Signatur als gültig anerkannt, andernfalls nichts h(M )dA mod NA h(M ) seA mod NA9.4 Das ElGamal-Signatur-VerfahrenSeite 3ff.Auch hier findet das DH-Verfahren wieder seine Verwendung. Daher ist das Prinzip ganzähnlich der ElGamal-Verschlüsselung. ggT (z, p 1) 124

Kryptographie27. Juli 2014Christian StrateSommersemester 2014Dozent: Prof. Ruppert c z 1 (h be) mod p 1 (2)Zu (3), der Signaturprüfung: Warum muss man 1 b pA 1 überprüfen?Weil man sonst Unterschriften fälschen kann! Sei M ein Dokument mit dem Hashwerth(M ) und (pA , gA , fA ) der öffentliche Schlüssel von A. Sei weiterhin b (pA 1) · (pA gA ), c h(M ). Es ist b ( 1) · ( gA ) gA mod pA und b 0 mod (pA 1) (Imc Exponenten rechnet man mod pA 1, in der Basis mod pA ) Dann: fAb · bc fAb · gAh(M)c gfA0 · gAmod pA d.h. (b, c) erfüllt die zweite Bedingung der Signaturüberprüfung,Aobwohl (b, c) nicht von A stammt. Wegen b pA 1 ist die Bedingung 1 b pA 1wichtig.Überlegung zur Sicherheit: Öffentlicher Schlüssel: (p, g, f ), privat e mit f g e mod p(2) Sei (b, c) gültige Signatur, dann gilt: eb zc h mod (p 1) und b g z mod p .a) Könnte man diskrete Logarithmen berechnen, so könnte man z bestimmenund dann aus der Kongruenzgleichung eb) Sonst hat man eine Gleichung mit zwei Unbekannten e, z, was ungenügendist.c) z muss auf jeden Fall geheim bleiben, sonst eine Gleichung, eine Unbekanntee lösbar.d) Selbiges gilt bei Mehrfachverwendung gleicher Zufallszahlen.Folglich braucht man einen guten Zufallsgenerator(3) Hier lediglich der Beweis dafür, dass die Zufallszahlen z1 , z2 identisch sind, derRest steht im offiziellen Skript. Angenommen, wir erhalten zwei Dokumente mitden Hashwerten h1 , h2 , den Signaturen (b1 , c1 ), (b2 , c2 ) und es gilt b1 b2a) Es ist b1 g z1 mod p, b2 g z2 mod p, also, da g Primitivwurzel mod p ist,folgt aus g z1 g z2 mod p sofort z1 z2 mod(p 1), also o.E. z z1 z2b) vgl. Skript Seite 5(4) Rest siehe Skript.Satz:a, b Z, m N.(u, v Z mit au mv gcd(a, m))1. ax b mod m lösbar gcd(a, m) bbm2. Sei gcd(a, m) b erfüllt, seien weiterhin x0 gcd(a,u)u und xi x0 i · gcd(a,m)für i 0, . . . , gcd(a, m) 1. Dann sind x0 , . . . , xgcd(a,m) 1 alle Lösungen vonax b mod n (und paarweise verschieden).25

Kryptographie27. Juli 2014Christian StrateSommersemester 2014Dozent: Prof. RuppertIn gpg Version 1.2.3, konnte man die ElGamal-Signatur verwenden. Damit das Signieren schneller geht, wurde aber eA und die Zufallszahl z deutlich kleiner als p gewählt,natürlich nicht so klein, dass man die Logarithmenberechnung erhalten konnte (b z mod , f g eA mod p ) Nguyen fand, dass man dann aus cz be h(M ) mod (p gAA AAAAA1) mit Gitermethoden eA und z schnell berechnen kann: cz beA h(M ) mod (pA 1).Gilt gA pA 1, so ist die ElGamal-Signatur nicht sicher.Hier die Beweisidee des ersten Satz des Anhangs Unsicherheit bei ElGamal-SignaturSeite 11f.Fälle der Beweisidee:f b 1 mod p:p 3f b bc g h mod p bc 2h mod p 2 2 ·c 2h mod p p 32·2 2 Primitivwurzel mod p p 3 2h mod ordp (2)· c h mod (p 1) Dies ist eine Gleichungdes Typs ax b mod m, die man gut lösen kann.f b 1 mod p:AnalogEs gibt verschiedene Weiterentwicklungen der ElGamal-Signatur, die auch praktischvon Bedeutung sind: DSA und ECDSA . Die Frage: Wie kommt man von der ElGamalSignatur zu DSA wird im offiziellen Skript behandeln.Wie kann man die ElGamal-Signatur verallgemeinern?(1) Ein Problem: b kommt in der Basis vor (Rechnen mod pA ), aber auch im Exponenten (Rechnen mod (pA 1)). Bei der Basis rechnen wir in der Gruppe(Z/pA Z) . Wir definieren l : (Z/pA Z) Z mit x 7 x mit 0 x p 1 (Auswahl eines Repräsentanten). Die Gleichungen schreiben sich nun b g z mod pA ; c 1(h(M ) l(b)eA ) mod (pA 1);z{z}{z}Rechnen in (Z/pA Z) l(b)h(M )fA bc gA Rechnen mit ganzen Zahlenmod pA{zRechnen in (Z/pA Z) )}(2) Wir versuchen (Z/pA Z) durch eine Gruppe zu ersetzen:Sei G multiplikativ geschriebene Gruppe (Bsp.: Q , Ghn (Q), . . .) g G mitordg (g) n, n N. Wähle eA N geheim, fA g eA G öffentlich.(G, g, fA )Unterschreiben eine Nachricht M mit Hashwert h(M ):Wähle Zufallszahl z mit gcd(z, n) 1, berechne b g z G,c z1 (h(M ) l(b)eA ) mod n. {z}zc h(M ) l(b)eA mod n26

Kryptographie27. Juli 2014Christian StrateSommersemester 2014Dozent: Prof. RuppertSignatur:(b, c) G ZSignatur-Test:l(b)fA bc (g eA )l(b) (g z )c g eA l(b) zcord(g) n g h(M )(3) Man kann (2) auch mit additiver Gruppe (G, ) aufschreiben. Ein Beispi

27. Juli 2014 Christian Strate Kryptographie Sommersemester 2014 Dozent: Prof. Ruppert 1.5 Blockchiffren Kryptosystem ALBC-2 -Seite 10f. ALBC-2: 5. d Z, alle l xzus atzli