Chinesischer Restsatz, pseudocode gesucht

[qwertz543221]

ich möchte die rsa-entschlüsselung durch den crt beschleunigen.

wo finde ich einen - verständlichen - pseudocode dafür?

folgendes habe ich schon gefunden(die idee, der code ist von mir), weiß jedoch nicht,wie es weitergeht:

Delphi-Quellcode:

var k,kp,kq,d,n,c,p,q,cp,cq,dp,dq,yp,yq;//typen unwichtig (sind zahlen)

begin
//p,q:primes;
//c:ciphertext,k:klartext;
//d: privater exponent
 
cp:=c mod p;
cq:=c mod q;

dp:=d mod (p-1);
dq:=d mod (q-1);

kp:=cp^dp mod p;//modular potenziert
kq:=cq^dq mod q;//''

yp:=modularinvers( );//hier weiß ich nicht, von was
yq:=modularinvers( );

k:=kp*yq*q; //zusammengesetzer klartext =>result
end;

[BUG]

Rein nach dem Namen könnte es das hier sein: modular multiplicative inverse

MfG,
Bug

[gammatester]

Da du Dein Ziel (selbst programmiertes RSA) nicht aus den Augen verlierst, solltes Du Dir vielleicht das frei herunterladbare HAC = Handbuch der angewandten Kryptographie besorgen (A. Menezes, P. van Oorschot, S. Vanstone: Handbook of Applied Cryptography). Dort findest Pseudocode unter Alg. 14.71 für Garner's CRT Algorithmus.

Wie üblich, kannst Du allerdings auch Pascal-Code für CRT und RSA-CRT aus meinee MPArith verwenden und die dort angegebenen Referenzen.

Gruß Gammatester

[gammatester]

Deine Formeln scheinen allerdings nicht richtig, speziell die für dp, dq. Die sind das Inverse von e mod p-1 bzw q-1 nicht von d.

Direkt aus der Quelle: Abschnitt 5.1.2 RSADP, im RFC 3447 PKCS #1: RSA Encryption Version 2.1:

Code:

Mit 

e * dp == 1 (mod (p-1))   also dp = InvMod(e, p-1)
e * dq == 1 (mod (q-1))   also dq = InvMod(e, q-1)
q * qInv == 1 (mod p).    also qInv = InvMod(q, p)

dann

m_1 = c^dp mod p and m_2 = c^dq mod q
h = (m_1 - m_2) * qInv mod p
m= m_2 + q * h

m ist dann Dein Klartext k. Ich gehe davon aus, daß Du weißt wie man modulare Inverse berechnet (Stichwort: erweiterter Euklidischer Algorithmus).

Gruß Gammatester

[qwertz543221]

Das ergebnis der entschlüsselung ist jedoch inkorrekt oder undurchführbar, und die schlüsselerstellung dauert ca 2x so lange wie zuvor.

Delphi-Quellcode:

procedure  tform1.rsageneratekey;
var
limit,d,phi,n:ansistring;
prime:boolean;
mathe:tmathe;
i:longint;

  function modinvers(x,y:ansistring):ansistring;
        var z,k:ansistring;
        begin
        k:='1';
        z:='1';
        while mathe.Modulo(z,x)<>'0'  do
        begin
        z:=mathe.produkt(k,phi);
        mathe.Plus1(z);
        mathe.Plus1(k);
        end;
        result:=mathe.Quotient(z,x);
        end;

begin
mathe:=tmathe.Create;
application.ProcessMessages;
    InputQuery('Primzahlgrenze', 'Limit (65792<=x)', limit);
    if (limit='')or (mathe.Vergleich(limit,'65792')<0)
    then showmessage('Dieser Schlüssel kann wegen zu kleinem Modul n nicht gewählt werden.');
   begin
    prime:=false;
    while prime=false  do
    begin
    p:=mathe.Zufall(mathe,'1',limit);
    Prime:=miller_rabin(p,30);
    end;
    prime:=false;
    while prime=false  do
    begin
    q:=mathe.Zufall(mathe,'1',limit);
    prime:=miller_rabin(q,30);
    end;

    begin
    n:=mathe.Produkt(p,q);
    if (vergleich(n,'65792')<0) or (vergleich(limit,'256')<0)
     then showmessage('Modulus zu klein.')
     else
       begin
       mathe.Minus1(p);
       mathe.Minus1(q);
        phi:=mathe.Produkt(p,q);

        d:=modinvers(e,n);
        dp:=modinvers(e,mathe.Differenz(p,'1'));
        dq:=modinvers(e,mathe.Differenz(q,'1'));
        qinv:=modinvers(mathe.Summe(p,'1'),mathe.Summe(q,'1'));

        LabeledEdit1.Text:=d;
        LabeledEdit2.Text:=n;
        end;
        end;
        end;
        end;


function tform1.rsadec(text:ansistring;d,n:ansistring):ansistring;
var 
textneu:ansistring;
i:int64;
wa,zahl,m_1,m_2,h:ansistring;//wa ist deine variable c
mathe:tmathe;

begin
textneu:='';
result:='';
mathe:=tmathe.Create;
i:=1;

while i<=length(text) do
  begin
  application.ProcessMessages;
  zahl:=copy(text,i,length(n));
  wa:=zahl;
  {
  m_1 = c^dp mod p and m_2 = c^dq mod q
  h = (m_1 - m_2) * qInv mod p
  m= m_2 + q * h
  }
  m_1:=mathe.PotenzModulo(wa,dp,p);
  m_2:=mathe.PotenzModulo(wa,dq,q);
  h:=mathe.Produkt(mathe.Differenz(m_1,m_2),mathe.Modulo(qinv,p));

  wa:=mathe.Summe(m_2,mathe.Produkt(q,h));
  textneu:=textneu+chr(strtoint(mathe.Quotient(wa,'256')))+chr(strtoint(mathe.Modulo(wa,'256')));
  i:=i+length(n)
  end;
result:=textneu;
end;

vielleicht habe ich deine anweisungen misverstanden

[gammatester]

Da sind noch ziemlich schlimme Bugs drin:

1. modinvers ist total daneben, obwohl ich nicht weiß, was Du da eigentlich vorgehabt hast. Du solltest Dir wirklich angewöhnen, in Kommentare zu schreiben, was Deine Funktionen machen. Auf jeden Fall hat phi da nix zu suchen.

z := modinvers(x,y) soll z berechnen mit z*x == 1 mod, also ProduktModulo(z,x,y) muss 1 sein.

Du solltest zuerst modinvers debuggen, bis Du folgende Ergebisse hast mit p=763542356462783642401

modinvers(36542354527354,p) = 119609365025838791859
modinvers(675423754723541,p) = 733615848005635595127

2. h = (m_1 - m_2) * qInv mod p ist falsch berechnet. Einzelschritte:
h = m_1 - m_2
h = Modulo(h,p)
h = ProduktModulo(h, qInv, p)

3. Der Exponent e ist nicht definiert

4. Bei der Schlüsselerzeugung muss geprüft werden, daß
a) gcd(e,p-1) = 1
b) gcd(e,q-1) = 1
c) und p<>q
Ansonsten ist es sehr wahrscheinlich, daß die Entschlüsselung nicht funktionieren. Wenn c nicht erfüllt ist, ist das ganze auch total unsicher.

5. phi:=mathe.Produkt(p,q) ist völlig falsch! phi = (p-1)*(q-1) wäre OK, besser ist phi = lcm(p-1,q-1) = (p-1)*(q-1)/gcd(p-1,q-1).


Weitere Vorschläge: Schreibe folgende Funktionen für die StringMatheLib: SummeModulo, DifferenzModulo, gcd = ggt = größter gemeinsamer Teiler.

Gruß Gammatester

[gammatester]

Ich sehr gerade noch folgende Anweisungen:

mathe.Minus1(p);
mathe.Minus1(q);

Damit wäre phi Phi:=mathe.Produkt(p,q) richtig, aber der Rest immer noch falsch:

1. falsch d:=modinvers(e,n);
richtig d:=modinvers(e,phi)

2. falsch dp:=modinvers(e,mathe.Differenz(p,'1'));
richtig dp:=modinvers(e,p);

3. falsch dq:=modinvers(e,mathe.Differenz(q,'1'));
richtig dp:=modinvers(e,q);

4. falsch qinv:=modinvers(mathe.Summe(p,'1'),mathe.Summe(q,' 1'));
richtig qinv:=modinvers(mathe.Summe(q,'1'),mathe.Summe(p,' 1'));

Allerdings rate ich dringend davon ab p-1 als p und q-1 als q zuverwenden, daß bettelt geradezu um Bugs.

Gruß Gammatester

[mquadrat]

Ich würde die Buchempfehlung um Einführung in die Kryptographie von Prof. Buchmann erweitern. Ist das Begleitbuch zu seiner Vorlesung und ich hab's (damals zumindest) verstanden ;)

Pseudocode und Grundlagen für alles mögliche. Hab's leider nicht im Büro stehen, sonst hätte ich mal geschaut was er da genau dazu drin stehen hat.

[qwertz543221]

danke für die tips, leute!

1) e ist eine konstante primzahl (frag mich nicht welche) und global deklariert, um sie für alle fkt's nutzen zu können. damit fällt auch die prüfung mit dem ggt(e,...) weg.

2) p und q werden automatisch durch unterschiedliche primzahlen belegt, um der erwähnten unsicherheit zu entgegnen.

noch eine frage:
3) wieso kann ich p und q nicht mit p-1 und q-1 neu belegen?? - ist das dann so fehleranfällig?

[gammatester]

Zitat:

Zitat von qwertz543221

danke für die tips, leute!

1) e ist eine konstante primzahl (frag mich nicht welche) und global deklariert, um sie für alle fkt's nutzen zu können. damit fällt auch die prüfung mit dem ggt(e,...) weg.

2) p und q werden automatisch durch unterschiedliche primzahlen belegt, um der erwähnten unsicherheit zu entgegnen.

noch eine frage:
3) wieso kann ich p und q nicht mit p-1 und q-1 neu belegen?? - ist das dann so fehleranfällig?

Zu 1: Wie Du weißt selbst nicht was e ist???? Und selbst wenn e ein Primzahl ist, kann ggt(e,p-1) > 1 sein. Beispiel p=61, q=59, e=3. Was ist dann d? (e=3 ist gar nicht so selten, wie's aussieht!)

Zu 2: Wieso automatisch? Das sollt Du mit Deinem Code ja gerade gewährleisten!

Zu 3: Wie fehleranfällig das ist, sieht man doch an Deinem Code. Selbst Du bringst p und p-1 bzw. q und q-1 ja durcheinander in Deiem Code. Außerdem erschwert es ungemein ein gemeinsames Sprechen über den RSA-Algorithmus.


Aber wenn Du sonst keine Probleme mehr hast ....

Gammatester