1. Aufgabenblatt, Aufgabe 3

mherrmann
Mausschubser
Mausschubser
Beiträge: 49
Registriert: 12. Nov 2005 10:10

1. Aufgabenblatt, Aufgabe 3

Beitrag von mherrmann »

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

Benutzeravatar
SM
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 167
Registriert: 10. Okt 2005 18:11
Wohnort: Darmstadt
Kontaktdaten:

Beitrag von SM »

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
~ Per aspera ad astra. ~

dahmen
Mausschubser
Mausschubser
Beiträge: 70
Registriert: 26. Apr 2006 18:54

Beitrag von dahmen »

Wichtig ist, dass ihr es hier nur mit ganzen Zahlen zu tun habt.
Bei der definition des Inversen fehlt das leider.

Über den rationalen Zahlen ist 1/7 schon das Inverse zu 7. (1/7 * 7 = 1).
Wir rechnen aber im Restklassenring mod n (nächste Vorlesung) und da gibt es keine Brüche.

mherrmann
Mausschubser
Mausschubser
Beiträge: 49
Registriert: 12. Nov 2005 10:10

Beitrag von mherrmann »

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

dahmen
Mausschubser
Mausschubser
Beiträge: 70
Registriert: 26. Apr 2006 18:54

Beitrag von dahmen »

4 ist korrekt, a=7.

mherrmann
Mausschubser
Mausschubser
Beiträge: 49
Registriert: 12. Nov 2005 10:10

Beitrag von mherrmann »

Und wozu brauche ich dann überhaupt das Inverse, die 4?

Wird das in der nächsten Vorlesung noch einmal genauer erklärt, dann warte ich nämlich vielleicht lieber noch bis nach der Vorlesung.

dahmen
Mausschubser
Mausschubser
Beiträge: 70
Registriert: 26. Apr 2006 18:54

Beitrag von dahmen »

du suchst

a^{-1} = das Inverse von a = x für das gilt (ax = 1 mod n)

also

7^{-1} = das Inverse von 7 = 4, da (7*4 = 28 = 1 mod 27)!

Ihr müsst davon wegkommen das "hoch minus eins" als Operation aufzufassen. Es ist vielmehr eine Bezeichnung für das Inverse.

mherrmann
Mausschubser
Mausschubser
Beiträge: 49
Registriert: 12. Nov 2005 10:10

Beitrag von mherrmann »

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?

Heinz
Mausschubser
Mausschubser
Beiträge: 91
Registriert: 10. Nov 2005 20:25

Beitrag von Heinz »

Ja, das ist ne gute Frage... ich finde auch das Durcheinander mit den Variablen auf den Folien sehr verwirrend... besonders Folie 22...

dahmen
Mausschubser
Mausschubser
Beiträge: 70
Registriert: 26. Apr 2006 18:54

Beitrag von dahmen »

Mein Fehler!

Mit a habe ich die Zahl bezeichnet die invertiert werden soll, wie auf der Folie.

Im Kontext der Aufgabe ist das natürlich Quatsch, da ja a=7^{-1} mod 27 berechnet werden soll. Also ist a=4 richtig.

Antworten

Zurück zu „Archiv“