1. Aufgabenblatt, Aufgabe 3

[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

[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

[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]

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]

4 ist korrekt, a=7.

[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]

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]

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]

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

[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.