Algorithmus umkehren?

[mP765]

Hallo alle zusammen,

ich schreibe zur Zeit an einer Facharbeit im Mathe LK.
Habe mich ein wenig hier ein wenig umgesehen und mich ziemlich geärgert, dass ich das nicht schon viel früher getan habe, wo doch in http://www.hackerboard.de/cryptography-encryption/39404-arbeit-ueber-kryptologie-ca-15-seiten.html eine wirklich gute Arbeit beschrieben ist. Naja seis drum, ich hab mich ja entschieden.

Bin auch so weit fertig mit dem groben Gerüst, aber mein Lehrer hat noch einen Extrawunsch.
Er würde gerne wissen, ob und wie man meinen Algorithmus umkehren kann, also vom verschlüsselten Text wieder zum entschlüsselten kommt.

Mein Algo sieht derzeit so aus:
http://img15.imageshack.us/i/algoj.jpg/

Was dazu noch zu sagen ist:
B = Basis (irgendeine Zahl)
S = Schlüssel (irgendeine Zahl ungleich 31)
P = Position im Text (kann theoretisch auch jede beliebige Zahl sein)
K = Klartextbuchstabe
G = Geheimtextbuchstabe
X und Z sind nur Platzhalter.

Mit der Schreibweise wusste mein Lehrer auch nicht so genau wie man das vernünftig und übersichtlich schreiben kann. Bin also offen für Vorschläge.

Hat jemand eine Idee, wie man von G wieder auf K kommt? Ich stehe da leider ziemlich auf dem Schlauch...


Viele Grüße und schonmal Dankeschön
mP765

 

[farhaven]

Deine Notation scheint mir etwas merkwuerdig... Wie ist z.b. G(mod 31) zu lesen? Ist das G modulo 31 oder ist das G von irgendwas modulo 31?

 

[Elderan]

Naja einen Verschlüsselungsalgorithmus zu entwerfen, bei dem man die Entschlüsselung nicht kennt scheint ja etwas nutzlos zu sein.

Umkehren sollte sich das wie folgt lassen:

(G - X) - K= 0
G - ZPB^S - K = 0
G - KSPB^S - K = 0
G - K (1+SPB^S) = 0
K = G / (1+SPB^S)


Dabei sind alle Operationen modulo 31 zu verstehen, also insbesondere auch die Division am Schluss.


PS:
Die "Oder in einem Schritt" Notation macht keinen Sinn. Das Kongruenz-Zeichen gibt eine Relation zwischen zwei Variablen/Werten an. Sprich, K*S steht in Relation zu Z. Darum kann man dies auch nicht in eine Kettengleichung einsetzen.

Deswegen wäre es Empfehlenswert, wenn man über den ganzen Kongruenzgleichungen noch schreibt:
Seien Z, X und G so gewählt dass gilt:
....


Wenn du es in einem Schritt haben möchtest, dann wäre das wie folgt:
KSPB^S + K = G (mod 31)

Wobei das = ein Kongruenzzeichen sein sollte.

 

[mP765]

Erstmal vielen lieben Dank für die schnellen Antworten.

Naja einen Verschlüsselungsalgorithmus zu entwerfen, bei dem man die Entschlüsselung nicht kennt scheint ja etwas nutzlos zu sein.

Als ich das geschrieben habe, war mir ja noch nicht klar, dass mein Lehrer das haben wollte, da es zuerst nur hieß, dass ich ver- und nicht entschlüsseln soll.

K = G / (1+SPB^S)

Tjaaaa, ich steh wohl immer noch auf dem Schlauch, verzeih bitte.

Wenn ich jetzt z.B.
K = 12
S = 4
P = 114
B = 8
nehme, ist
G = 14

Wenn ich das jetzt so umkehre ist
K = G / 1867777
mit

Dabei sind alle Operationen modulo 31 zu verstehen, also insbesondere auch die Division am Schluss.

K = 14 / 27 = 0,5185

Ich befürchte zwar langsam, ein paar grundlegende Wissenslücken in der Modulorechnung zu haben, aber vllt könntest du es mir dennoch kurz erklären?

KSPB^S + K = G (mod 31)

Hört sich gut an, nehme ich. Danke

 

[Elderan]

Hallo,
14 / 27 ist eben nicht 0,5.... in modulo 31!

a / b ist definiert als a*b^-1, mit b*b^-1 = 1 (mod 31). Du musst also zu 1867777 die Zahl b^-1 finden, mit 1867777*b^-1 = 1 (mod 31).


Hast du diese Zahl gefunden, so berechnest du 14*b^-1


b^-1 lässt sich mittels dem erweiterten euklidischen Algorithmus finden, oder aber man testet alle Zahlen von 1 bis 30 aus und schaut ob 1867777*[1...30] = 1

 

[mP765]

Da hab ich das wohl trotz Hinweis nicht wirklich als [FONT=&quot][/FONT]modulo betrachtet...

Vielen lieben Dank für die Hilfe