Ronin-Verschlüsselung in Java Script

[RichardBrook]

Hallo, ich beschäftige mich gerade ein bisschen für Kryptologie und bin dabei relativ schnell auf das Rabin Kryptosystem gekommen(Link: http://www2.cs.uni-paderborn.de/cs/ag-bloemer/lehre/proseminar_WS2005/materia/Czernik_DasRabinVerschluesselungssystem.pdf?PHPSESSID=d996c6367f702c91f68f64bb5e5785c6).
Das ganze mit der Verschlüsselung habe ich auch schon in JavaScript geschrieben; hier der ungefähre Code:

var q = 17; //Secret Pass 1
var p = 19; //Secret Pass 2
var m = 65; //Message ("a" im UNICODE)
var c = 0; //Verschlüsselte Nachricht
var n = p*q; //Public Pass
[..]
function encrypt() {
c = m^2 % n; // => c=m*m modulo n
document.getElementByID("output").innerHTML = c; //c ausgeben
}

Doch wie entschlüsselt man das ganze?! Im Netz habe ich nichts mehr verstanden(Bin erst 15; meine Mathe Kenntnisse sind daher etwas beschränkt:wink.

Würde mich über Hilfe freuen.

PS: Checkt jemand die anspielung auf den Namen(SH)?

 

[GrafZahl]

als erstes... der gute Mann heißt Rabin nicht Ronin...

also die entschlüsselung einmal zerrupfen:

das verfahren dreht sich um modular-arithmetische quadratwurzeln... davon gibt es wie bei normalen quadratwurzeln praktisch immer 2 (sofern sie überhaupt lösungen haben, spezialfälle interessieren hier gerade nicht)

zum berechnen der einen echten lösung und der 3 nieten gibt es 3 grobe teile:

schritt 1 ... wurzel mod p
schritt 2 ... wurzel mod q
schritt 3 ... kombination der beiden teillösungen mittels chin. restsatz

1 und 2 sind defacto beidesmal das selbe, nur dass sich die zahlen ändern ...

also jeweils:

1.1) finde b, quad. nichtrest mod p, mit 1<=b<=p-1

die große frage ist ... wann ist eine zahl ein quad. nichtrest? ...
wenn b hoch (p-1)/2 mod p gleich -1 ist ... -> schleife für b von 1 bis p-1 ... jeweils die formel berechnen... abbrechen wenn -1 rauskommt ... b gefunden

1.2) finde s, t, mit t ungerade und p-1=t*(2 hoch s)

2 hoch s ist ... 2,4,8,16,32,64... bilde die reihe und teile solange (p-1) durch (2 hoch s) bis das ergebnis eine ganze ungerade zahl ist

1.3) berechne c hoch -1 mod p

hoch -1 mod p heißt auch: bilde die modulare inverse...
das tut der erweiterte euklidische algorithmus ... kurz eea ... siehe wikipedia

für die inverse gilt: c * (c hoch -1) mod p = 1 ... das kannst du also machen um dein ergebnis zu testen...

1.4) berechne x = log_b_hoch_t(c hoch t)
exponenzieren und logarithmieren wirst du hinkriegen... auch wenn dieser wert scheinbar im verlauf der weiteren entschlüsselung keine verwendung mehr findet ... hey... immerhin kann man ihn ausrechnen...

1.5) der algorithmus dafür ist ausführlich auf seite 17 im PDF

anmerkung: auf seite 18 im PDF kannst du sehen warum man beim schlüssel erzeugen schon von vorneherein darauf achten sollte dass p mod 4 = q mod 4 = 3 sein sollte ... der ganze quatsch schrumpft zusammen auf eine formel ... in dem fall streiche 1.1 bis 1.5 und berechne nur diese formel ...


sooo .... bis hier hin solltest du in der lage sein schritt 1 und schritt 2 zu machen ...

schritt 3 ... der chinesische Restsatz sieht komplizierter aus als er ist ...

berechne den EEA den du oben schon gebraucht hast für p und q um die beiden zahlen a und b zu erhalten so dass a*p+b*q=1

ab jetzt berechnest du nur noch 2 formeln:

x=(a*p*s + b*q*r) mod (p*q)
y=(a*p*s - b*q*r) mod (p*q)

jetzt gibt es 4 ergebnisse:

x
-x
y
-y

jeweils mod n (also mod (p*q))

eines dieser ergebnisse ist dein klartext ... die anderen 3 sind schrott...

der nachteil dieses Verschlüsselungsverfahrens ist, dass du nicht sagen kannst welches dieser 4 ergebnisse das richtige ist ...

in der praxis bietet sich an, dem ergebnis eine bestimmte struktur zu geben(z.B. die letzten x bit des klartextes nochmals anhängen), um es anschließend erkennbar zu machen... der nachteil ist jedoch dass dadurch auch die sicherheit des verfahrens möglicherweise sinkt ...

 

[Shalec]

schritt 3 ... der chinesische Restsatz sieht komplizierter aus als er ist ...

berechne den EEA den du oben schon gebraucht hast für p und q um die beiden zahlen a und b zu erhalten so dass a*p+b*q=1

ab jetzt berechnest du nur noch 2 formeln:

x=(a*p*s + b*q*r) mod (p*q)
y=(a*p*s - b*q*r) mod (p*q)

jetzt gibt es 4 ergebnisse:

x
-x
y
-y

jeweils mod n (also mod (p*q))

eines dieser ergebnisse ist dein klartext ... die anderen 3 sind schrott...

der nachteil dieses Verschlüsselungsverfahrens ist, dass du nicht sagen kannst welches dieser 4 ergebnisse das richtige ist ...

in der praxis bietet sich an, dem ergebnis eine bestimmte struktur zu geben(z.B. die letzten x bit des klartextes nochmals anhängen), um es anschließend erkennbar zu machen... der nachteil ist jedoch dass dadurch auch die sicherheit des verfahrens möglicherweise sinkt ...

Hallo,
Du hast dir hier aber wirklich viel Mühe gegeben Ich möchte aber noch eine "Ergänzung" wagen. Ich bin ja fasziniert von den Vorlesungen von Christian Spannagel auf Youtube. Würden sich an unserer Uni mal die Dozenten die Zeit für die Teilaspekte nehmen, wie er, dann würden wir mehr Langzeitkönner erzeugen.

Also um die Mathematik hinter dem chinesischen Restsatz zu verstehen, empfehle ich dir (Threadersteller) ein paar Videos von diesen hier anzuschauen:
https://www.youtube.com/user/pharithmetik/playlists

In einem ist sogar GrafZahl erwähnt (Count count)

Um den Satz zu verstehen, solltest du lernen, wie man in z.B. Z/pZ rechnet (d.h. alle ganzen Zahlen modulo p, p prim). Es gibt hier ein paar besondere Eigenschaften.

Versuche doch, wenn dein Programm läuft, die Nutzbarkeit des Programms zu erweitern. Z.B. für große Zahlen im Bereich von 2^{2048}.