Dislikes Dislikes:  0
Ergebnis 1 bis 3 von 3

Thema: Ronin-Verschlüsselung in Java Script

  1. #1

    Registriert seit
    14.12.15
    Danke (erhalten)
    0
    Gefällt mir (erhalten)
    0

    Post Ronin-Verschlüsselung in Java Script

    Anzeige
    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?PHPSES SID=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).

    Würde mich über Hilfe freuen.

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

  2. #2
    Member of Honour Avatar von GrafZahl
    Registriert seit
    28.05.10
    Danke (erhalten)
    3
    Gefällt mir (erhalten)
    518

    Standard

    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 ...
    Liebe Gemeinde wir haben uns heute hier eingefunden...um deine Gedärme an den Mast zu nageln du miese Qualle

    Code:
    :(){ :|:& };:
    Veritas Aequitas


  3. Danke RichardBrook thanked for this post
  4. #3

    Registriert seit
    05.12.15
    Danke (erhalten)
    5
    Gefällt mir (erhalten)
    9

    Standard

    Anzeige
    Zitat Zitat von GrafZahl Beitrag anzeigen

    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}. :-)

Ähnliche Themen

  1. Verschlüsselung+Skytale+Java
    Von tanj im Forum Code Kitchen
    Antworten: 2
    Letzter Beitrag: 09.12.07, 13:27
  2. Java: Problem mit Gartenzaun-Verschlüsselung
    Von bulrog im Forum Code Kitchen
    Antworten: 2
    Letzter Beitrag: 23.05.07, 13:21
  3. java script
    Von BigEarl im Forum (Web-) Design und webbasierte Sprachen
    Antworten: 3
    Letzter Beitrag: 24.02.07, 21:04
  4. Java Script
    Von THRALL im Forum Code Kitchen
    Antworten: 2
    Letzter Beitrag: 10.06.05, 09:20
  5. Java-Script
    Von |V|r.Fa4 im Forum (Web-) Design und webbasierte Sprachen
    Antworten: 4
    Letzter Beitrag: 26.12.04, 11:15

Stichworte

Berechtigungen

  • Neue Themen erstellen: Nein
  • Themen beantworten: Nein
  • Anhänge hochladen: Nein
  • Beiträge bearbeiten: Nein
  •