Chinesischer Restsatz, pseudocode gesucht

[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 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.