Tauschchiffre < Krypt.+Kod.+Compalg. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Ich hätte nochmal eine frage zur Tauschchiffre.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Welche Vorausseztungen müssen die Buchstabenpaare haben die ich zur Entschlüsselung brauche (ich rechne mit mod36).
Denn auch wenn ich Buchstabenpaare nehme, deren Abstand zueinander teilerfremd zu 36 ist, erhalte ich keine eindeutige Lösung. Beispiel:
14 -> 13; 19 -> 32. (der Schlüssel ist s=11 u. t=3)
[mm] 19\equiv5t [/mm] (mod36). Kann ich so eine Gleichung doch irgendwie lösen?
Hat dies eventuell was mit dem inveresen Element zu tun? Ich würde mich auch hier über einen Lösungsvorschlag freuen.
Liebe Grüße Blaufisch
|
|
| |
|
Hallo,
da kommst du mit dem erweiterten euklidischen Algorithmus weiter. Du suchst eine Lösung der Gleichung:
$19 = 36*x + 5*t$
Die Zerlegung nach dem euklidischen Algorithmus für ggT(36,5) fällt recht kurz aus:
$36 = 5*7 + 1$
Entsprechend leicht kommen wir auf die Lösung:
$1 = 36 - 5*7$
Mit 19 multipliziert:
$19 = (36 - 5*7)*19 = 36*19 - 5*7*19 = 36*19 + 5*(-133)$
Nun rechnest du diese -133 mod 36 und kommst auf 11.
Gruß
Martin
|
|
|
| |
|
Das hieße, dass um die Tauschchiffre lösen zu können der Abstand zwischen den Geheimtext Buchstaben ein inverses Element haben muss, mit dem sich x [mm] \equiv [/mm] 1 mod 36 ergibt.
Dazu hätte ich dann nochmal eine Frage. Liegt immer nur dann ein inverses Element vor, wenn die Zahl und 36 teilerfremd sind?
|
|
|
| |
|
Wie sähe denn dann der euklidische Algorithmus für 19 [mm] \equiv [/mm] 13t (mod 36) aus?
Vielen Dank
|
|
|
| |
|
Du meinst doch hier eher
$19 [mm] \eqiv [/mm] 13s mod 36$? (Ich meine nur s statt t)
Gesucht ist also ein s, das $36x + 13s = 19$ erfüllt.
"Zerlegen":
36 = 13*2 + 10 (a)
13 = 10*1 + 3 (b)
10 = 3*3 + 1 (c)
"Zusammensetzen":
19 = 19 * (10 - 3*3) [(c) einsetzen]
= 19 * (10 - (13 - 10*1) * 3) [(b) einsetzen]
= 19 * (13 * (-3) + 10 * 4) [nach 10 und 13 sortieren]
= 19 * (13 * (-3) + (36 - 13 * 2) * 4) [(a) einsetzen]
= 19 * (36 * 4 + 13 * (-11)) [nach 13 und 36 sortieren]
= 36 * 76 + 13*(-209)
Also mit mod 36:
$s = 13 [mm] \equiv [/mm] -209$
Gruß
Martin
|
|
|
| |
|
Hallo,
> Das hieße, dass um die Tauschchiffre lösen zu können der Abstand zwischen den Geheimtext Buchstaben ein inverses Element haben muss, mit dem sich x 1 mod 36 ergibt.
Hmmm, sieht so aus. Beispiel (für dein (s, t)):
3 -> 0, 6 -> 33
also:
$3s [mm] \equiv [/mm] 33 [mm] \mod [/mm] 36$
Hier kommen für s zwei Werte in Frage: 11 und 23, also keine Eindeutigkeit!
> Dazu hätte ich dann nochmal eine Frage. Liegt immer nur dann ein inverses Element vor, wenn die Zahl und 36 teilerfremd sind?
Ja, genau. Hätte man z.B. ein Alphabet mit 37 Zeichen (Primzahl!), dann müsste man darüber gar nicht nachdenken.
Gruß
Martin
|
|
|
|
