Multiplikative Verschlüsselung (Euklidischer Alghorithmus)

[Kuonrat]

Hey
Die Multiplikative Verschlüsselung gehört ja zu den monoalphabetischen Chiffren und wird mit einer Zahl codiert. Ich habe zur Zeit ein Problem, mit der Berechnung des Decodier Schlüssels (private key). Der ist ja nicht dersselbe, da das verfahren asymmetrisch ist.
Soweit so gut, möglich über den Euklidischen Algorithmus zur Bestimmung des ggT. Jedoch weiß ich nicht wie es nach der Bestimmung des des ggT weitergeht mit dem Rückwärts einsetzen, kann mir da jemand behilflich sein? Smile

Am Beispiel 26 und 15 (26 ist das Klartextalphabet und 15 ist der public key zur verschlüsslung):

26 = 1 * 15 + 11
15 = 1 * 11 + 4
11 = 2 * 4 + 3
4 = 1 * 3 + 1
3 = 3 * 1 + 0

Also ist wohl der ggT 1, und nun?

[gammatester]

Zitat von Kuonrat:

Hey :)
Die Multiplikative Verschlüsselung gehört ja zu den monoalphabetischen Chiffren und wird mit einer Zahl codiert. Ich habe zur Zeit ein Problem, mit der Berechnung des Decodier Schlüssels (private key). Der ist ja nicht dersselbe, da das verfahren asymmetrisch ist.
Soweit so gut, möglich über den Euklidischen Algorithmus zur Bestimmung des ggT. Jedoch weiß ich nicht wie es nach der Bestimmung des des ggT weitergeht mit dem Rückwärts einsetzen, kann mir da jemand behilflich sein? Smile

Am Beispiel 26 und 15 (26 ist das Klartextalphabet und 15 ist der public key zur verschlüsslung):

26 = 1 * 15 + 11
15 = 1 * 11 + 4
11 = 2 * 4 + 3
4 = 1 * 3 + 1
3 = 3 * 1 + 0

Also ist wohl der ggT 1, und nun? :lol:

Ich nehme an Du meinst folgendes:

Verschlüsseln b = a*15 mod 26
Entschlüsseln a = x*b mod 26

wobei x=15**(-1) mod 26 das multiplikative Inverse von 15 mod 26 ist. Das Stichwort dazu ist dann erweiterter Euklidischer Algorithmus. Allerdings kann man x=15**(-1) mod 26 leicht durch probieren finden: x muß ungerade sein, ungleich 1, 13 (13 hat kein Inverses), also 3*15=19, 5*15=23, 7*15=1 alles selbstverständlich mod 26.

Gruß Gammatester