Wiederholungsübung

(Lösungen)

Frage 1

Gegeben sei p=11241659497250818732348359021137395733246852310796060981482644946707957057312721965105620365678269358100573132136562094657250680734491742344181871725697667

und der Erzeuger g=2.

Welchen gemeinsamen geheimen Schlüssel errechnen Alice und Bob beim Diffie-Hellman-Schlüsselaustausch, wenn Alice als geheime Zufallszahl

a=3262610409399946198928104852809963025247127478649409434062299966966653815439779184369210263570092361692624903461713238301405159818603236428164843921843

und Bob

b=5250238377167511458501797026452986161879419069498358414257114153728458279826838843005562203127824641678849549431177648301552342168438729200439790960739

wählt?

Bitte nur die Zahl angeben, wird automatisiert geprüft.

Die richtige Antwort ist: 11026410694914715281540223738656738337931641751785060686233369783671368247644723717603781464923215441712577844343497762161427126120424752067767435252026107

Lösung:

• man muss 2^(a*b) mod p ausrechnen
• hierbei ist zu beachten, dass die Zwischenergebnisse nicht zu groß werden
  • also nicht 2^(a*b) ausrechnen (das hätte 10^300 Bits!) und danach mod p, sondern
  • eine Programmiersprache benutzen und die repeated-squaring-methode implementieren, oder
  • in PARI/GP für diese Werte a, b, p den Ausdruck Mod(2,p)^(a*b) eingeben

Frage 2

Gegeben sei p=23 und der Erzeuger g=5.

Welchen gemeinsamen geheimen Schlüssel errechnen Alice und Bob beim Diffie-Hellman-Schlüsselaustausch, wenn Alice als geheime Zufallszahl a=7 und Bob b=9 wählt?

Bitte nur die Zahl angeben, wird automatisiert geprüft.

Die richtige Antwort ist: 7

Lösung:

• man muss 5^(a*b) mod p ausrechnen
• die Zahlen sind so gewählt, dass dies mit Papier und Bleistift funktionieren sollte
  • also wie oben nicht erst 5^(a*b) ausrechnen, sondern
  • (5*5)=2 mod 23 benutzen, dann ist 5^(7*9) mod 23 = 2^31*5 mod 23.
  • man kann den kleinen Fermat'schen Satz benutzen: 2^22 = 1 mod 23
  • das lässt noch 2^9*5 mod 23 übrig, und mit 2^6 = (-5) mod 23 hat man
  • 2^3*(-5)*5 = -40*5 = 6*5 = 30 = 7 mod 23

Frage 3

Finden Sie den kleinsten Erzeuger mod 31.

Die richtige Antwort ist: 3

Lösung:

Man muss das Erzeugerkriterium überprüfen.

Zunächst zerlegt man p-1 = 30 = 2 * 3 * 5.

Danach spielen 2, 3, 5 nacheinander die Rolle von q in der Formel

g^((p-1)/q) = 1 mod p.

Ist für irgendein q diese Gleichung erfüllt, dann ist das betreffende g kein Erzeuger.

g=1 kann nie Erzeuger sein, weil dann die Gleichung für alle Exponenten erfüllt wäre.

Für g=2 erhält man 2^((30-1)/2) = 2^15 = (2^5)^3 = 1^3 = 1 mod 31.

Also ist 2 kein Erzeuger.

Für g=3 erhält man

• für q=2: 3^((30-1)/2) = 3^15 = (3^3)^5 = (-4)^5 = -2^10 = -(2^5)^2 = -1^2 = -1 = 30 mod 31.
• für q=3: 3^((30-1)/3) = 3^10 = (3^3)^3 * 3 = (-4)^3 * 3 = -2 * 3 = -6 = 25 mod 31
• für q=5: 3^((30-1)/5) = 3^6 = (3^3)^2 = (-4)^2 = 16 mod 31

alle drei Ergebnisse sind != 1, also ist 3 ein Erzeuger

(bei den Rechnungen sind mehrere Wege möglich, am besten so gut es geht die Zahlen klein halten)

Frage 4

Fragetext

Benutzen Sie Ihre eigene Implementierung, um den Fermat-Test für die angegebenen p's und g=2 bzw 3 durchzuführen.

5458897790854103887727171711636804970587935514611785503989825512185702142628571525781781025640182400756332716568650635590296175242383776131262749694933 5458897790854103887727171711636804970587935514611785503989825512185702142628571525781781025640182400756332716568650635590296175242383776131262749694935 5458897790854103887727171711636804970587935514611785503989825512185702142628571525781781025640182400756332716568650635590296175242383776131262749694937 5458897790854103887727171711636804970587935514611785503989825512185702142628571525781781025640182400756332716568650635590296175242383776131262749694939 5458897790854103887727171711636804970587935514611785503989825512185702142628571525781781025640182400756332716568650635590296175242383776131262749694941

geben Sie im Antwortfeld die Primzahl unter den angegebenen Zahlen an.

Die richtige Antwort ist: 5458897790854103887727171711636804970587935514611785503989825512185702142628571525781781025640182400756332716568650635590296175242383776131262749694939

Lösung

bei solch großen zufällig gewählten Zahlen bringt praktisch immer das erste a, das man wählt, einen Beweis, dass die Zahl keine Primzahl ist

der kleine Fermat'sche Satz sagt, für eine Primzahl p und jedes a mit 1 <= a <= p-1 gilt: a^(p-1) = 1 mod p

Ihre Implementierung sollte für a=2 und die gegebenen Zahlen p nacheinander die Werte

• 5005741159069247532905053699519453125277775706655780467015013403377391991385788666061166981060646367890865449696382335275959606516509866369933565643416
• 809786783099039014484662404659973760021165542353260093823461910649389300883144000463645924618917935532070011696424848554509410798271826628460918616989
• 4501072821722231999253002936556395243695163103509125013045036587634704654465166967211096898020254936999905720739779439259039318151601815244203699073019
• 1
• 2481616966344742002611486428598741756835948673565478947776658878048490818385411974656418043395529377691886022874898834598347638369083782530236403082123

herausbringen. Also ist der vierte Wert die Primzahl.

Frage 5

Benutzen Sie Ihre Implementierung von Pollard-Rho, um folgendes Problem zu lösen

2^x = 3 mod 1004040827267

Geben Sie x an, für x soll 1 <= x <= p-1 gelten.

Die richtige Antwort ist: 322903237928

Lösung

Sehen Sie sich die auf der Moodle-Seite stehende Pollard-Rho Implementierung an und wiederholen Sie README-04 und README-05.

Frage 6

Bob hat Alice eine Nachricht im ElGamal-Verschlüsselungssystem geschickt.

Die öffentlichen Schlüsselparameter von Alice sind

g=5

p=649495102007

y=567045375870

Bob sendet an Alice die Werte (c,d) als

( 284413716907 , 24628819227 )

Rechnen Sie mit Hilfe Ihrer Pollard-Rho-Implementierung aus, welchen geheimen Schlüssel Alice hat und welche Zahl Bob als Klartext benutzt hat.

Tragen Sie ins Antwortfeld den Klartext m ein.

Die richtige Antwort ist: 333333333333

Lösung

Der Klartext ergibt sich aus c^(p-1-a)*d mod p. Dazu braucht man a.

Den Wert a rechnet man aus g^x = y mod p aus. Also starten Sie Pollard-Rho mit diesen Ausgangsdaten.

Frage 7

Alice wählt n=33 und als Verschlüsselungsexponent e=3.

Von Bob erhält sie die Nachricht m'=19 geschickt.

Welchen Klartext m hat Bob benutzt?

Die richtige Antwort ist: 13

Lösung

Das RSA-Verfahren mit n=33 und e=3 führt auf geheime Primzahlen p=3 und q=11. Der Wert phi(n) = (p-1)*(q-1) = 2 * 10 = 20.

Jetzt kann man d ausrechnen d = 1/e mod phi(n). Also rechnet man den Euklidischen Algorithmus für e=3 und phi(n)=20. Das ergibt d=7.

Nun ist 19^7 = 13 mod 33 , also ist 13 der Klartext.