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

[qwertz543221]

habe jetzt p-1 und q-1 durch neue variablen erstzt
mit automatisch meinte ich, dass ich dafür zufallszahlen wählen lasse und dann auf primalität prüfe.
Es werden solange primzahlen gesucht bis p<>q

und modinvers habe ich berichtigt:

Delphi-Quellcode:

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

h wird jetzt in einzelschritten berechnet


....

und trotzdem dauert die erstellung der schlüssel jetz über 30 sekunden( bei n=391.198.919)
das ergebnis der entschlüsselung ist... - falsch


so sieht der qt momentan aus:

Delphi-Quellcode:

//global:
d,p,q,phi,n,dp,dq,qinv:ansistring; //chin RS


function tform1.GGT(n, m: ansistring): ansistring;
var mathe:tmathe;
begin
mathe:=tmathe.Create;
  if m = '0' then Result := n
  else Result := ggt(m, mathe.Modulo(n,m));
end;

function tform1.rsadec(text:ansistring;d,n:ansistring):ansistring;

var textneu:ansistring;
i:int64;
wa,z1,z2,z3,m_1,m_2,m,h:ansistring;
mathe:tmathe;

begin
textneu:='';
result:='';
m_1:='0';
m_2:='0';
m:='0';
h:='0';
mathe:=tmathe.Create;
i:=1;

while i<=length(text) do
  begin
  application.ProcessMessages;
  wa:=copy(text,i,length(n));
  //wa:=mathe.PotenzModulo(wa,d,n);
  {
  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.Differenz(m_1,m_2);
  h:=mathe.modulo(h,p);
  h:=mathe.ProduktModulo(h,qinv,p);

  m:=mathe.summe(m_2,mathe.Produkt(q,h));
  wa:=m;

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

[gammatester]

Ich sehe keine Berichtigung von modinvers. Wie ich schon in Beitrag #6 geschrieben habe, hat phi darin absolut nichts suchen, und merkwürdigerweise wird dafür n irgends verwendet.

Ich habe nicht den Schimmer einer Ahnung, was Du in dieser Funktion eigentlich machst.

Noch ein letztes Mal mit Deiner Bezeichnung function modinvers(e,n:ansistring):ansistring: Die Anweisung x := modinvers(e,n) muss x so berechnen, daß ProduktModulo(x,e,n)='1' ist. Wenn das nicht erfüllt ist, brauchst Du nicht weiterzumachen! Und da n keine Primzahl ist, wirst Du es (wahrscheinlich) ohne erweiterten Euklidischen Algorithmus (EEA) nicht schaffen. Für Primzahlen p könnte man notfalls modinvers(e,p) = e^(p-2) mod p rechnen, weil nach dem kleinen Fermatschen Satz gilt: 1 = e^(p-1)=e*e^(p-2) mod p. Das ist aber hier nicht möglich, da weder p-1, q-1, phi keine Primzahlen sind.

Also noch einmal: Schreib die Funktion modinvers mit dem EEA und verifiziere Deine Implementation mindestens für diese Beispiele mit p=763542356462783642401:

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


Gammatester

[qwertz543221]

Zitat:

Noch ein letztes Mal mit Deiner Bezeichnung function modinvers(e,n:ansistring):ansistring: Die Anweisung x := modinvers(e,n) muss x so berechnen, daß ProduktModulo(x,e,n)='1' ist. Wenn das nicht erfüllt ist, brauchst Du nicht weiterzumachen!

ich habe genau das getestet, und habe keinen widerspruch gefunden.
außerdem, wieso soll ich phi für die erstellung des privaten exponenten nicht benötigen?

(quelle: http://de.wikipedia.org/wiki/RSA-Kry...chl.C3.BCssels):

Zitat:

Wir wählen p und q
Der RSA-Modul ist n:=pq .
Die eulersche φ-Funktion nimmt damit den Wert (p-1) (q-1) an.
Die Zahl e muss zu phi teilerfremd sein. Damit bilden e und N den öffentlichen Schlüssel.
Berechnung der Inversen zu e:
Es gilt:
e*d+k*phi=ggt(e,phi)=1.
d ist der private Schlüssel, während k nicht weiter benötigt wird.

will sagen: deine bedingung ist erfüllt, auch wenn ich - vorerst - ohne den eea gearbeitet habe.
Also daran kann es eigentlich nicht liegen, dass die umwandlung zur berechnung mit dem chin RS nicht funktioniert. (die entschlüsselung ohne chin.RS bringt ja auch korrekte ergebnisse)

Meine frage bezog sich ursprünglich nur auf die impl. des chin.RS, die die decyrption um ca 4 beschleunigen soll. - dafür hatte ich den anfang der fkt eingestellt, im ersten post sind stellen markiert, an denen ich nicht wusste, wie es weitergeht(allein vom algorithmus her):
=>

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;

[gammatester]

Umso dringender zu sagen, was Dein modularinvers eingentlich macht! Damit wir weiterkommen gib uns mal folgendene Werte für Dein Beispiel:

n = 391198919
p = ?
q = ?
e = ?
d = ?
dp = e^-1 mod (p-1) = InvMod(e, p-1) = ?
dq = e^-1 mod (q-1) = InvMod(e, q-1) = ?
qInv = q^-^ mod p = InvMod(q, p) = ?

und für

m = 276543785
c = ?
m_1 = ?
m_2 = ?
h = ?

[gammatester]

Noch ein paar Zusatzanmerkungen:

Vielleicht war es ja ein merkwürdiger Zufall, daß Du in Deiner ursprünglichen Frage dp, dq im Zusammenhang mit CRT-RSA in einer ganz anderen Bedeutung verwendest als es Standard ist.

Vielleicht willst Du ja Deinen eigenen Weg gehen. Aber Dein Ansatz ist nicht durchsichtig und trotzdem schlichtweg falsch. Selbst bei einer Adhoc-Bedeutung von modularinvers ist er nicht zuretten. ZB ist Dein entschlüsselter Text immer ein Vielfaches von q! Damit kann Deine Rechnung höchsten für Klartexte richtig sein, die auch ein Vielfaches von q sind.

Meine Empfehlungen kennst Du ja inzwischen. Nimm die Formeln aus dem RFC und schreib in richtiges InvMod; dann sollte der Rest einfach sein und wir können Dir notfalls weiterhelfen.

Gammatester

[qwertz543221]

habe jetzt den crt mal erstellt, mit functionierendem invmod - die ergebnisse sind entsprechend der normalen vorgehensweise, nur sollte doch ein zeitgewinn (literatur: bis zu 4x schneller) durch die verwendung des crt ermöglicht werden, dies ist jedoch nicht der fall. Woran liegt das?

[gammatester]

Zitat:

Zitat von qwertz543221

habe jetzt den crt mal erstellt, mit functionierendem invmod - die ergebnisse sind entsprechend der normalen vorgehensweise, nur sollte doch ein zeitgewinn (literatur: bis zu 4x schneller) durch die verwendung des crt ermöglicht werden, dies ist jedoch nicht der fall. Woran liegt das?

Das liegt unter anderem daran, daß Du gar kein RSA benutzt!!! Noch nicht mal ein einziges PotenzModulo taucht auf, geschweige denn, daß es richtig benutzt wird.

Gammatester

[qwertz543221]

Das ganze soll auch nicht nach dem original schema x°d mod n berechnet werden, da genau dies zu langsam ist., Deshalb erfolgt eine aufteilung.

Delphi-Quellcode:

 function tform1.rsadec2(text:ansistring;d,n:ansistring):ansistring;
var
i,j:int64;
wa,h:ansistring;

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

 while i<=length(text) do
  begin
  application.ProcessMessages;
wa:='';
 j:=i;
 while j<i+length(n) do
 begin
 wa:=wa+text[j];
 j:=j+1;
 end;
 cp:=mathe.Modulo(wa,p);
 cq:=mathe.Modulo(wa,q);
dp:= mathe.modulo(d, mathe.differenz(p,'1');
dq:= mathe.modulo(d, mathe.differenz(q,'1');

//hier ist doch potenzmod(), der quelle nach ist insgesamt nur zweimal potenzmod anzuwenden:

 mp:=mathe.PotenzModulo(cp,dp,p);
 mq:=mathe.PotenzModulo(cq,dq,q) ;

 wa:=mathe.Modulo(mathe.Summe(mathe.Produkt(mathe.Produkt(mp,yq),q),mathe.Produkt(mathe.Produkt(mq,yp),p)),n);
 //  result:=result+numtotext(wa);
  i:=i+length(n)
  end;
   end;

procedure Tform1.DECmitChinRS1Click(Sender: TObject);
var d,n:ansistring;
function rsadec2(text:ansistring;d,n:ansistring):ansistring;
var
i,j:int64;
c,h,m:ansistring;

begin
result:='';
mathe:=tmathe.Create;
i:=1;
 while i<=length(text) do
  begin
  application.ProcessMessages;
c:='';
 j:=i;
 while j<i+length(n) do
 begin
 c:=c+text[j];
 j:=j+1;
 end;
 cp:=mathe.Modulo(c,p);
 cq:=mathe.Modulo(c,q);
 m:=mathe.modulo(mathe.Summe((mathe.produkt(mathe.produkt(mp,yq),q)),(mathe.produkt(mathe.produkt(mq,yp),p))),n) ;

 result:=result+numtocomb(strtoint(m));
 i:=i+length(n);

  end;
   end;
  begin
try
d:=(labeledEdit1.Text);
n:=(LabeledEdit2.Text);
memo2.Lines.add(datetimetostr(now)+': RSA - Starte Dechiffrierung mit chin RS.');
memo1.Text:=rsadec(memo1.Text,d,n);
memo2.Lines.add(datetimetostr(now)+': RSA - Dechiffriert mit chin RS.');
memo2.lines.add('---------------------------------------------------');
except
on e:exception do
begin
e.Message;
memo2.Lines.add(datetimetostr(now)+': RSA - Dechiffrierung fehlgeschlagen.');
memo2.lines.add('---------------------------------------------------');
end;
 end;
end;

[gammatester]

Du brauchst mir nicht zu erklären, wie RSA/CRT funktioniert! Da Du allerdings immer noch die Unsitte pflegst, Sourcecode zu posten, der dann im nächsten Beitrag (ätsch!) doch wieder anders ist (und es war definitiv kein Potenzieren in Deinem Anhang), mußt Du Dir leider jemanden anderes suchen, der Dir masochistisch genug ist, um Dir auf diese Art weiterzuhelfen.

Wie schon vor Wochen gesagt, fühlt man sich durch dieses Vorgehen vera****t.