Hacken bei RSA-Verfahren

[Meisterschmied]

Schönen Abend,

Hab da gerad ein Problem mit der RSA-Verschlüsselung, wie schon so oft in den letzten Tagen! Es klappt eigentlich schon alles, bedeutet er verschlüsselt und entschlüsselt alles korrekt. Nur etwa jedes 7 - 8 mal (nicht periodisch, total zufällig) wird falsch ver- oder entschlüsselt. Dabei scheint der Schlüssel, bestehend aus den beiden Primzahlen p und q, dem Verschlüsselungsexponenten e und dem Entschlüsselungsexponenten in Ordnung zu sein (zumindest innerhalb der Grenzen, die ich kenne).
Ich hab mal ein Exemplar rausgegriffen und alle Werte dokumentiert:

p = 227
q = 251
n = p*q = 56977
e = 3
d = 37667
k (Blocklänge: Log28(n)) = 3
Zeichen im Alphabet (N)= 28

Verschlüsselt werden sollte der Text:
Klartext: adadada

Aufgeteilt in Blöcke der Länge k ergeben sich drei Blöcke zu
1) ada
2) dad
3) a00

wobei die Nullen am Schluss als Rest des letzten Blocks korrekt eingefügt wurde. Die Blöcke werden dann in numerische Zeichen umgewandelt zu (m1*N^2+m2*N^1+ m3*N^0), wobei die Zeichen a=1, d=4, 0=0
1) 897
2) 3168
3) 784

Diese Blöcke werden verschlüsselt zu (m^e mod n)
1) 6614
2) 53253
3) 35815

und entschlüsselt zu (c^d mod n)
1) 40612
2) 15587
3) 6730

Bei der Erzeugung des Schlüssels wurden folgende Vorgaben beachtet:

p und q sind Primzahlen
n ist das Produkt aus p und q
1 < e < (p-1)(q-1)
gcd(e,(p-1)(q-1)) = 1
de = 1 mod n <=> (de-1) mod n = 0
k wird immer abgerundet

So, eigentlich müsste alles gehen, aber es funktioniert trotzdem nicht . Hat jemand eine Idee, wo es hacken könnte? Wäre euch echt dankbar.

Thanks ,

Meisterschmied

[negaH]

Hi

Wenn der Encrypton Exponent E auf 3 fixiert wird dann müssen die Primzahlen P,Q kongruent 2 mod 3 sein. Der Exponent 3 ist der kleinstmögliche Exponent, hat aber auch ziemlich große Sicherheitsrisiken.

Der Decryption Exponent D sollte D = E^-1 mod LCM(P -1, Q -1) und GCD(D, P * Q) = 1.
LCM ist das größte gemeinsamme Vielfache.

Im deinem Beispiel komme ich auf D = 9417.

Delphi-Quellcode:

function LCM(A,B: Integer): Integer;
begin
  if A = B then Result := Abs(A) else
    if (A = 0) or (B = 0) then Result := 0 
      else Result := Abs(A div GCD(A, B) * B);
end;

Gruß Hagen

[Meisterschmied]

Danke Hagen,

scheint es aber nicht zu sein. Ich komm zwar auch auf deinen Wert, aber die Verschlüsselung klappt nicht besser. Bei diesen Werten bekomme ich (wenn ich 26 verschlüsseln will) für

m^e mod n = 26^3 mod p*q = 17576

und

c^d mod n = 32184

Ich hab mal meinen Code reingeschrieben (das ist die Kurzform, dich ich aus Codeschnipseln in eine neue Anwendung geschrieben habe - ist sonst sehr viel länger...). Ich muss außerdem noch kurz warnen, dass er fürchterlich ist, trotzdem scheint er zu funktionieren. Das war oberste Priorität. Schönheit und Effizienz kommt später (für Tipps bin ich aber natürlich immer zu haben ).

Delphi-Quellcode:

procedure TForm1.Button1Click(Sender: TObject);
var
  a, b, d, p, q : integer;
begin
  p := 227;
  q := 251;
  a := lcm(226,250);
  d := 3;

  repeat
  Inc(d);
  until ((3*d - 1) mod a) = 0;

  Edit1.Text := IntToStr(d);   // 9417

  Edit2.Text := IntToStr(FastExponation(26,3,p*q)); // 17576
  Edit3.Text := IntToStr(FastExponation(StrToInt(Edit2.Text),d,p*q));  // 32184 

end;

function lcm(A, B: Integer): Integer;
begin
  if A = B then Result := Abs(A) else
    if (A = 0) or (B = 0) then Result := 0
      else Result := Abs(A div gcd(A, B) * B);
end;

function gcd(a, b : integer): Integer;
var
  H : Integer;
begin
// Wir verwenden den Euklidischen Algorithmus zur Bestimmung des größten
// gemeinsamen Teilers (gcd = greatest common divisor)

while b > 0 do
  begin
    H := a mod b;
    a := b;
    b := H;
  end;

  Result := a;

end;

function FastExponation(J, exp, n : integer): Integer;
var
  Base, I, T : integer;
begin
  IntToBin(exp);

  Base := J;
  T := Base;
  For I := 2 To length(Bin)-1 do begin
    T := (T*T) mod n;
    If Bin[I] = 1 Then T := (T*Base) mod n;
  end;
  Result := T;
end;

function IntToBin(Int: integer): string;
var
  I : integer;
begin
  BinS := '';
  // Erzeugung eines Binärstrings
  repeat
    BinS := IntToStr(Int mod 2) + BinS;
    Int := Int div 2;
  until Int = 0;

  Setlength(Bin, Length(BinS)+1);

  // In ein Array zerlegen
  For I := 1 To Length(BinS) do
  Bin[I] := StrToInt(Copy(BinS,I,1));

end;

Danke schon mal,

Wieland

[Meisterschmied]

Noch mal kurz,

ich hab mir gerade unter

http://www.informatik.tu-darmstadt.d...e_I/kl-lsg.pdf

Aufgabe 3 angeguckt. Du kennst dich ja so super aus , ich versteh nicht, wie er/ sie sich in der Lösung der Entschlüsselungsexponenten ausrechnet. Ich kann aus seiner Liste und dem, was er darunter schreibt, absolut nichts entnehmen. Ich hab das auch mal mit meinem Buch verglichen, wo es ähnlich (allerdings in einem anderen Zusammenhang) drinne steht. Aber das ist ungefähr genauso unklar beschrieben. Verstehst du, was er da meint? Und kommt unter diesem Aspekt ein anderes Ergebnis für d raus?

Thanks

Wieland

[Meisterschmied]

Und nochmal,

ich habs jetzt mal ganz brutal ausprobiert und geguckt, für welches d der Klartext wieder erscheint

Delphi-Quellcode:

  Edit2.Text := IntToStr(FastExponation(26,3,p*q));

  repeat
  Inc(d);

  until FastExponation(StrToInt(Edit2.Text),d,p*q) = 26;

Je nach dem, welchen Wert ich entschlüsseln will, ändert sich aber d, was aber eigentlich gar nicht sein dürfte. Also entweder, ich hab einen Fehler in meiner schnellen Exponention oder ich glaub an überhaupt nichts mehr. Gleicht irgendwie der Nadel im Heuhaufen... ich bin verwirrt

Bin für jede Hilfe dankbar (und ganz ausdrücklich Hagen),

Wieland

[negaH]

Deine Exponentation scheint mir nicht richtig zu sein. Hier mal die beiden möglichen Varianten. Beachte auch das diese Verfahren nur mit M,B < 2^16 korrekt arbeiten können. Wird stattdessen Int64 benutzt so liegt die Schranke bei 2^31. Größere Zahlen erzeugen in den Multiplikationen Überläufe.
Exponent E mus größer 1 sein, es sind also keine speziellen Abfragen drin für E <= 0 !

Delphi-Quellcode:

function ExpModLR(B,E,M: Integer): Integer;
// Bottomup Exponentation, wie im PDF beschrieben
var
  T: Integer;
begin
  Result := 1;
  T := B;
  while E > 1 do
  begin
    T := (T * T) mod M;
    E := E shr 1;
    if Odd(E) then Result := (Result * T) mod M;
  end;
end;

function ExpModRL(B,E,M: Integer): Integer;
// Topdown Exponentation, wie die meisten math. Bibliotheken sie nutzen
// Beachte Basis B bleibt konstant, dadurch sind spezielle Optimierungen möglich.
// Es wird eine Multiplikation weniger durchgeführt als obige Exponentation
// Die Abfragen Log2(E) und IsBitSet(E) sind in math. Bibliotheken sehr effizient
// durchzuführen. Dadurch wird Exponent E ebenfalls konstant.

  function Lg2(V: Cardinal): Integer;
  // Result := Trunc(Log2(V))
  asm
      BSR  EAX,EAX
  end;
  {begin
    Result := 0;
    while V > 1 do
    begin
      Inc(Result);
      V := V shr 1;
    end;
  end;}

  function IsBitSet(V: Cardinal; Index: Integer): Boolean;
  asm
     BT   EAX,EDX
     SETC AL
  end;
{  begin
    Result := Odd(V shr Index);
  end;}

var
  I: Integer;
begin
  Result := B;
  for I := Lg2(E) -1 downto 0 do
  begin
    Result := (Result * Result) mod M;
    if IsBitSet(E, I) then
      Result := (Result * B) mod M;
  end;
end;

Gruß Hagen

[negaH]

Den Entschlüselungsexponenten D einfach per "Brute Force" zu erzeugen, wie in deinem Beispiel reicht nicht aus.
1.) E und D sollten zufällig gewählt werden damit RSA sicher ist.
2.) (e * d) mod N = 1 mod N ist zwar die richtige Kongruenz, aber nicht gleichbedeutend mit D = E^-1 mod N.

D = E^-1 mod N ist das multiplikative Inverse von E. Multipliziert man also eine gegebene Zahl mit D so ist dies eine modulare Division durch E.

Zur Berechnung D = E^-1 mod N benutzt man den Erweiterten Euklidschen Algorithmus, also den erweiterten GCD. Wenn GCD(A, B) = D so erzeugt der erweiterte GCD dann D = U*A + V*B , also D,U,V als Ausgabe. U ist dann das multiplikative Inverse.


Wie gesagt, gib mir deine EMail Adresse und die Info ob due D5,D6,D7 benutzt, dann maile ich dir meine math. Library. Sie ist dann zwar für die nur ein Vergleichobjekt, da ich dir nicht die vollen Sourcen geben kann. Aber besser eine einfache und korrkte Library zur Überprüfung der eigenen Resultate als garnichts.

Gruß Hagen

[Meisterschmied]

Hi Hagen,

a) ich hab dir eine pn mit meiner Mailadresse geschrieben. b) zu dem, was du geschrieben hast. Ich versteh nicht so ganz, was du mit

Zitat:

Wenn GCD(A, B) = D so erzeugt der erweiterte GCD dann D = U*A + V*B , also D,U,V als Ausgabe. U ist dann das multiplikative Inverse.

Was sind plötzlich A, B und versteh ich es richtig, dass dann U das multiplikative Inverse von D ist. Weil es ist ja immer das Problem, dass D aus dem Euklidischen Alorithmus negativ sein kann, und dann ja schwerlich als Exponent eingesetzt werden kann. Genauso

Zitat:

D = E^-1 mod N

E^-1 ist doch eine Zahl <= 1, wie kann dann für D ein vernünftiges Ergebnis rauskommen. Ich dachte außerdem, der Erweiterte Euklidische Algorithmus würde nur Koeffizienten der Art Ax+By = 1 hervorbringen. Wie kann er dann solche der Form Ax+By=D berechnen ? Ich weiß, ich bin schwierig

Thanks ,

Wieland

PS: Es heißt natürlich "Haken [..]"

[negaH]

1. Frage Extended GCD(),

richtig D = Ax + By = Au + Bv, dabei sollte der GCD Algorithmus bestimmte Regeln beachten. Er swapt A,B wenn A > B ist. Wenn es den einfachen GCD von A,B gibt und dieser dann D <> 1 zurückliefert, so heisst das das beim Erweiterten GCD von A,B ebenfalls D <> 1 sein wird. Mathematisch gesehen heist dies dann das es kein eindeutiges Multiplikatives Inverses von A,B gibt. D.h. man berechnet D = GDCExt(A,B, x,y) und wenn D <> 1 dann gibt es kein A^-1 mod B. Somit heisst dies das A und B zueinander NICHT teilerfremd sind (relativ prime zueinander), was aber eine Vorraussetzung dafür ist das A im modularen Ring B invertiert werden kann. Natürlich kann X,U < 0 sein aber dies spielt keine Rolle, den in modularen Ringen -> mod M, wird aus dem negativen U sehr leicht ein positives und korrektes U indem man U' = U + M rechnet.

2. multiplikatives Inverse, A^-1 mod M

Richtig es würden negative Zahlen entstehen. Aber beachte das wir im Modularen Ring arbeiten. Z.b. 2 mod 3 == -1 mod 3. Somit ist es durchaus möglich neagtive Zahlen zu beschreiben, über 3 + -1 == 2 mod 3.
Wir haben hier aber einen negative Exponenten, was nicht gleichbedeutend mit negativem A ist. Ein Negativer Exponent wird bei Ganzzahlen diese Zahl A zu einer gebrochenen Zahl mit Nachkommmastellen machen. Aber wir arbeiten in modularen Ringen ! und dort kann man sehr wohl mit negativem Exponenten arbeiten und das Resultat wird denoch eine Zahl im Bereich -M < 0 < M sein. Vorausgesetzt A ist relativ teilerfremd zu M. Deshalb wird bei allen Kryptoverfahren meistens M als Primzahl oder Produkt zweier großer Primzahlen definiert. Da M nun eine Primzahl ist ist jede Zahl kleiner M automatisch teilerfremd zu M. Logisch, da die erste Zahl die nicht teilerfremd zu M ist eben 1*M bzw. 2*M ist.

So, was macht nun das multiplikative Inverse ?
Am besten ist hier ein Vergleich zu den Gebrochenen Zahlen. Wir haben eine Zahl R = 4 und benötigen das Reziproke, den Kehrwert. Dieser ist 1/R = R^-1 = 0.25. Jetzt wollen wir eine Zahl X = 12 durch 4 dividieren. Es gibt zwei Wege dazu 1.) X / R = Y oder eben X * R^-1 = Y.
Nun in Modularen Ringen wird X / R == Y mod M über X * R^-1 == Y mod M gerechnet. Es gibt nur eine Lösung wenn R relativ teilerfremd zu M ist.

Also, wie der Name "multiplikatives Inverse" besagt ist das nichts anderes als der Kehrwert einer Zahl in mpdularen Ringen.

Oben benutze ich zwei verschiedene Gleichheitszeichen. 1.) = -> ist gleiche und 2.) == -> ist kongruent. In modularen Ringen wird immer == benutzt. Da 3 mod 4 == -1 mod 4 == -5 mod 4 == 7 mod 4 == 11 mod 4 usw. usw. ist. D.h. in modularen Ringen zu M einer Primzahl wird jede Zahl in das Set der Zahlen S = {0 <= E < M} mod M gemappt. Die Anzahl der teilerfremenden Elemente E in S ist M -1 = Phi(M). Sollte M = P * Q sein, also zwei Primzahlen P * Q, dann ist die Anzahl der Elemente E in S mod M = Phi(P, Q) = LCM(P -1, Q -1). D.h. der Ring M = PQ enthält nun die Menge aller teilerfremden Elemente der Subringe Sp = {0 <= Ep < P} mod P und Sq = {0 <= Eq < Q} mod Q mit Sp || Sq = Phi(P, Q) = LCM(P -1, Q -1).
Das || steht für die Vereinigungsmenge. Ich habe absichtlich diese Schreibweise genommen das normalerweise das + dafür richtig wäre. Aber man verwechselt dann die Addition zweier Sets mit der Addition zweier Zahlen. Denn wenn wie zB. zwei Sets haben {1,2,3,4} und {3,4,5,6} dann ist {1,2,3,4} + {3,4,5,6} = {1,2,3,4,5,6}, und somit die Anzahl der Element der Sets 4 + 4 = 6 -> 4 || 4 = 6.

3.) Empfehlung von mir
Kaufe dir das Buch "Einführung in die Kryptographie" von Johannes Buchmann ISBN 3-540-66059-3. Buchmann geht in diesem Buch sehr ausführlich und einfach verständlich in die nötige Mathematik ein. Das Buch ist leicht mißverständlich benamt und sollte heissen "Einführungn in die Mathematik der Kryptographie". Denn Buchmann konzentriert sich vor allem auf z.B. obige Fragen, statt auf symmetrische Verfahren.

4.) Fragen
Wenn der erweiterete GCD zweier Zahlen A,B ein D <> 1 zuckrückgibt und somit A,B nicht teilerfremd zueinander sind, WIE wird dann PHI(A, B) berechnet ??
Bei RSA ist N = P*Q, warum muß man nun überprüfen ob GCD(E, N) = GCD(D, N) = 1 ist ??

Gruß Hagen

[Meisterschmied]

Hi Hagen,

ich nehme deine Fragen jetzt mal als Test, ob ich mich auch wirklich mit dem Thema beschäftige und du nicht meine halbe Facharbeit schreibst (was nicht der Fall ist, denn die ist im mathematischen Teil bereits komplett fertig). Meine Hauptquelle war dabei aber übrigens das Buch, was du oben nanntest, und es ist natürlich relativ gut beschrieben, ist aber trotzdem für Mathematik- und Informatikstudenten des dritten Semesters, nicht zu vergessen. Und obwohl ich einer der besten in Mathe bin, ist es nicht ganz einfach, wenn sich nie mit irgendetwas in der Art beschäftigt hat, ganz besonders die Rechnungen in Restklassenringen, der Rest ist ja im Prinzip ganz simpel. Da ich die in meiner Facharbeit (aus Platzgründen) sowie fast ganz raus geschmissen hab, hatte mich das bis jetzt nicht ganz so gestört (auch wenn ich Dinge gerne vollständig verstehen will).

Aber zu deinen Fragen:

1) Ich verstehe zwar den Sinn nicht so ganz, aber da A und B ja auf jeden Fall keine Primzahlen sind, ist PHI(A) mit Sicherheit nicht A-1, sondern ein sehr viel kleinerer Wert. Bzw. es ist die Anzahl der ganzen Zahlen a, für die gilt, dass gcd(A,a)=1. Jetzt müsste doch PHI(A,B) = PHI(A)*PHI(B), oder?

2) Weil E*D == 1 mod n nur lösbar ist, wenn gcd(E,D) = 1. Man muss doch aber nicht überprüfen, ob GCD(E, N) = GCD(D, N) = 1, denn das wird ja dadurch impliziert, dass p und q Primzahlen sind. Aber E und D sind ja kleiner als P und Q, also muss GCD(E, N) = GCD(D, N) = 1 gelten

Ich hoffe du bist den Antworten einigermaßen zufrieden (wahrscheinlich nicht... ). Aber mal ehrlich: Hast du nun Informatik (oder Mathematik) studiert, oder bist du Autodidakt? Ach ja, und kannst du mir die Bibliothek zuschicken?

Danke,

Wieland