1. Aufgabenblatt, Aufgabe 3
1. Aufgabenblatt, Aufgabe 3
Hallo zusammen,
wie aus den Vorlesungsfolien bekannt kann man einen affin liniearen Chiffre knacken wenn man zwei Paare Klartext / Schlüsseltext besitzt.
In der Aufgabe sind die beiden Paare (14,11) und (7,10), wobei ich davon ausgehe, dass der Klartext zuerst genannt wird und dann der Schlüsseltext.
Die Formel a = (c1 - c2)(m1 - m2)^-1 mod n liefert mir:
(11 - 10)(14 - 7)^-1 mod 27 = 1 / 7 mod 27
So, und welche Zahl ist nun kongruent zu 1/7 mod 27?
Eigentlich wäre das ja 1/7, weil 1/7 - 1/7 = 0 und 27|0 da 0 = 0*27. Aber mit dem Bruch kann ich doch nicht wirklich etwas anfangen, oder?
Grüße
wie aus den Vorlesungsfolien bekannt kann man einen affin liniearen Chiffre knacken wenn man zwei Paare Klartext / Schlüsseltext besitzt.
In der Aufgabe sind die beiden Paare (14,11) und (7,10), wobei ich davon ausgehe, dass der Klartext zuerst genannt wird und dann der Schlüsseltext.
Die Formel a = (c1 - c2)(m1 - m2)^-1 mod n liefert mir:
(11 - 10)(14 - 7)^-1 mod 27 = 1 / 7 mod 27
So, und welche Zahl ist nun kongruent zu 1/7 mod 27?
Eigentlich wäre das ja 1/7, weil 1/7 - 1/7 = 0 und 27|0 da 0 = 0*27. Aber mit dem Bruch kann ich doch nicht wirklich etwas anfangen, oder?
Grüße
- SM
- Endlosschleifenbastler
- Beiträge: 167
- Registriert: 10. Okt 2005 18:11
- Wohnort: Darmstadt
- Kontaktdaten:
Vorsicht: 7^-1 ist (hier) nicht 1/7
Was Du suchen musst, ist die Inverse:
a = 7^-1 mod 27
Also: Womit muss 7 multipliziert werden, damit der Rest mod 27 = 1 ist? (siehe Definition der Inversen)
Die Antwort liefert Dir entweder die Intuition oder der xgcd-Algorithmus in Form des y-Anteil der zurückgegebenen Linearkombination. (Siehe buchmann1.pdf - Seite 9 und 10)
Hoffe, das hilft ein wenig.
So long,
SM
Was Du suchen musst, ist die Inverse:
a = 7^-1 mod 27
Also: Womit muss 7 multipliziert werden, damit der Rest mod 27 = 1 ist? (siehe Definition der Inversen)
Die Antwort liefert Dir entweder die Intuition oder der xgcd-Algorithmus in Form des y-Anteil der zurückgegebenen Linearkombination. (Siehe buchmann1.pdf - Seite 9 und 10)
Hoffe, das hilft ein wenig.
So long,
SM
~ Per aspera ad astra. ~
Aha, habe ich etwas in der Vorlesung nicht mtbekommen, oder wann hat er das erklärt?
Ich bin durch Überlegen und durch den xgcd Algorithmus auf 4 gekommen. Das heißt 4 ist das Inverse zu 7 mod 27, weil 4*7 kongruent 1 mod 27 ist? a ist dann was? 4?
Und b ergibt sich dann zu 9 weil: 9 kongruent 11 - 4*14 mod 27 ist?
Grüße
Ich bin durch Überlegen und durch den xgcd Algorithmus auf 4 gekommen. Das heißt 4 ist das Inverse zu 7 mod 27, weil 4*7 kongruent 1 mod 27 ist? a ist dann was? 4?
Und b ergibt sich dann zu 9 weil: 9 kongruent 11 - 4*14 mod 27 ist?
Grüße
Ja, ok das leuchtet ein.
Es ist nur so, dass ich ja eigentlich ein a und ein b herausrechnen möchte um den Schlüssel (a,b,n) zu bekommen. n ist wohl bekannt, also errechne ich a. Wenn ich aber schon nachdem da steht
a kongruent 7^-1 mod 27
weiß, dass a = 7 ist wozu noch das Inverse bestimmen?
Nach dem a ausgerechnet wurde errechnet sich ja b mit
b kongruent c1 - a*m1 mod n
Welches a setze ich denn dann da ein? Wenn es 7 ist, dann verstehe ich nicht warum das Inverse errechnet wird, oder setze ich da 7*4 ein?
7*4 geht doch auch gar nicht, weil 28 > 27 und a muss doch kleiner sein als n, oder?
Es ist nur so, dass ich ja eigentlich ein a und ein b herausrechnen möchte um den Schlüssel (a,b,n) zu bekommen. n ist wohl bekannt, also errechne ich a. Wenn ich aber schon nachdem da steht
a kongruent 7^-1 mod 27
weiß, dass a = 7 ist wozu noch das Inverse bestimmen?
Nach dem a ausgerechnet wurde errechnet sich ja b mit
b kongruent c1 - a*m1 mod n
Welches a setze ich denn dann da ein? Wenn es 7 ist, dann verstehe ich nicht warum das Inverse errechnet wird, oder setze ich da 7*4 ein?
7*4 geht doch auch gar nicht, weil 28 > 27 und a muss doch kleiner sein als n, oder?