RSA: Privaten Schlüssel schneller berechnen

[negaH]

Das stimmt ja auch:

1 = U * A + V * B, umgestellt zu unseren Parametern

1 = (E^-1) * E + V * Phi(N)

1 = -83 * 229 + 66 * 288

e^-1 = d = -83

da wir aber im modularem Ring von Phi(N) == 288 arbeiten und das negative Vorzeichen von d = -83 nicht erwünscht ist rechnen wir noch

d = e^-1 mod Phi(N) was bei negativem d identisch ist zu
d = e^-1 + Phi(N) also

d = -83 mod 288 == -83 + 288 = 205

also

d = 205.

So, nun zeige mal den Funktionrumpf deiner erwetereten ggT() Funktion. Diese sollte 2 Eingabeparamater A,B haben und 3 Ausgabeparameter R,U,V.

R = eggt(out U,V, in A,B)

R = U * A + V * B umgestellt auf unsere Variablennamen wäre dies dann

1 = D * E + V * Phi(N) wobei

D = E^-1 ist also

1 = E^-1 * E + V * Phi(N)

und da E^-1 das multiplikative Inverse von E ist muß demzufolge

E^-1 * E = 1 sein. Somit ergibt sich für den Rest der Formel logischerweise

1 = 1 + V * Phi(N) und der formale Teil V * Phi(N) muß selber 0 ergeben damit der Rest der Formel stimmt, also

1 = 1 + 0

Verifizieren wir das

1 = D * E + V * Phi(N) -> 1 == -83 * 229 + 66 * 288 mod Phi(N)

66 * 288 == 19008 mod Phi(N) == 0 mod 288 und

-83 * 229 == -19007 mod Phi(N) == 205 mod 288

Das heist

1.) wir arbeiten in modularen Ringen und das bedeutet das wir JEDE Operation in einer solchen Formel (Kongruenzklasse) immer modulo Phi(N) rechnen müssen. Um den Unterschied zwischen normalen Formel und modularen Formeln hervorzuheben benutzt man das doppelte Gleichheitszeichen.
Beispiel:

1 == d * e mod Phi(N) bedeutet ausgeschrieben

1 mod Phi(N) = ((d mod Phi(N)) * (e mod Phi(N))) mod Phi(N)

und

d == e^-1 mod Phi(N) wäre

d mod Phi(N) = (e mod Phi(N))^-1 mod Phi(N).

2.) der erweiterte ggT() muß also als Rückgabewert immer 1 ergeben, was bedeutet das eine Inversion rechnerisch durchführbar ist. Sollte also 1 != D * E + v * Phi(N) rauskommen, der ggT() also NICHT 1 als Resultat liefern dann ist die Berechnung des modularen multiplikativen Inversen in dem gewählten Ring zum Modul Phi(N) nicht eindeutig. Das bedeutet E ist nicht teilerfremd zu Phi(N). Im Falle von RSA und der bekannten Faktorization von N in die zwei Primzahlen P,Q bedeutet dies das P oder/und Q keine richtigen Primzahlen sind. Liefert der erweiteret ggT() also nicht 1 so wissen wir das unsere Primzahlen P,Q falsch sind.


Fazit:

Du hast

1 == D * E mod Phi(N) in Worten also, D mal E ist kongruent zu 1 mod Phi(N). Das bedeutet D muß identisch zum modularen multiplikativen Inversen von E sein, als D == E^-1 mod Phi(N). Ergo:

1 == D * E mod Phi(N) ist identisch zu
1 == E^-1 * E mod Phi(N) und umgestellt ergibt das

D = E^-1 mod Phi(N).

Der private Decryption Exponent D ist einfach nur das Multiplkative Inverse im modularen Ring Z(N) vom public Encryption Exponenten E.

Da wir zur Berechnung von D die Faktorization von N in P,Q kennen müssen um Phi(N) berechen zu können entsteht eine "Trapdoor" Funktion (Hintertür Funktion). Denn ein Angreifer der aus N den privaten Decryption Exponenten berechnen will muß erstmal Phi(N) berechnen und dazu muß er N in P,Q faktorisieren.

Kennt man P,Q so kennt man Phi(N) und kann über den eggT() sehr einfach D berechnen aus E. Das geht sehr schnell.
Kennt man nur N so muß man N faktorisieren in P,Q was bei goßen P,Q (>= 512 Bit) eben praktisch unmöglich ist.

Eine Trapdoor Funktion ist also eine Funktion die mathematisch beweisbar mindestens 2 Wege bietet um ein Resulat zu berechnen. Der eine Weg, bei dem alle wichtigen Parameter bekannt sind, ist ein sehr leicht mathematisch zu berechnender Weg.
Der andere Weg bei dem bestimmte Parameter NICHT bekannt sind (hier P,Q und D und Phi(P*Q)) ist zwar auch mathemqtisch berechenbar, die dafür nötigen Algorithmen sind aber so komplex das sie mit berechenbar großen Parametern (P,Q) parktisch undurchführbar sind. (bzw. mann kan es versuchen wird aber mit heutiger Technik viele tausende Jahre benötigen).

Das Geheimnis vom RSA ist also diese Trapdoor Funktion und die gezielte Verteilung des RSA Schlüssels in ZWEI Teile: dem privaten Schlüsselteil und dem öffentlichen Schlüsselteil.

Wenn wir also beim RSA vom

öffentlichen Schlüssel E,N und vom
privaten Schlüssel D,N reden

so stimmt das eigentlich garnicht. Denn in beiden Fällen handelt es sich nur um EINEN Schlüssel aber in unterschiedlichen Formen !!

Denn in Wahrheit ist der

öffentliche Schlüssel E, P*Q
private Schlüssel E^-1, P*Q

der RSA Schüssel ist also E und P*Q denn wir können davon ZWEI unterschiedliche Formen ableiten

öffentliche Schlüsselform E und N
private Schlüsselform E^-1 und P*Q

Auf Grund das wir im öffenbtlichen Schlüssel nur E und N publizieren muß ein Angreifer sehr umständlich N faktorisieren in P * Q um dann Phi(P*Q) berechnen zu können und finaly aus E den pivaten Exponneten D = E^-1

Also poste mal den Funktionsrumpf deiner eggT() Funktion, damit ich beurteilen kann ob du die richtige Funktion benutzt.

Gruß Hagen

[Micha88]

Leider geht aus diesem Thread nicht hervor, wie man den private key mit Hilfe des public keys findet.

Geht das überhaupt?

[Namenloser]

Zitat von Micha88:

Leider geht aus diesem Thread nicht hervor, wie man den private key mit Hilfe des public keys findet.

Geht das überhaupt?

Ich bin wirklich kein Krypto-Experte, aber eins weiß ich mit Sicherheit: Man kann den Private Key nicht aus dem Public Key errechnen, denn das ist ja gerade der Sinn der Sache.

[Micha88]

Möglich ist es, "soll" es aber nicht. So habe ich es gelesen.

Mhh.. Demnach kann man RSA-verschlüsselte Texte ja niemals einsehen, wenn man den private key nicht weiß.

Das Problem sind die riesen (Prim)zahlen.

[Namenloser]

Zitat von Micha88:

Möglich ist es, "soll" es aber nicht.

Also zumindest mit unseren heutigen Computern geht es wohl nicht in absehbarer Zeit.

[Bjoerk]

Zitat von NamenLozer:

Zitat von Micha88:

Leider geht aus diesem Thread nicht hervor, wie man den private key mit Hilfe des public keys findet.

Geht das überhaupt?

Ich bin wirklich kein Krypto-Experte, aber eins weiß ich mit Sicherheit: Man kann den Private Key nicht aus dem Public Key errechnen, denn das ist ja gerade der Sinn der Sache.

Das ist leider nicht richtig.

RSA-Encryption:
2 Prime P, Q
P <> Q
N = P*Q
M = (P-1)*(Q-1)
Find an E and a D so that is:
S * M + 1 = E * D, E <> D, E relatively prime to M, D 1..M, E 1..M, S > 0
Encrypt: J = I^E mod N, I 0..N
Decrypt: I = J^D mod N

N, E = Public
M, P, Q, D = Private

Der Private Schlüssel D lässt sich sogar direkt aus N und E berechnen.
Guckst du hier:

Delphi-Quellcode:

procedure TRSAEncryption.FindD(const N, E: int64); // get the private Key D
var
  P, Q, M: int64;
begin
  FE:= 0;
  FD:= 0;
  FN:= 0;
  FM:= 0;
  FP:= 0;
  FQ:= 0;
  P:= 2;
  while P < N do
  begin
    if IsPrimeNumber(P) then
    begin
      Q:= N div P;
      if IsPrimeNumber(Q) then
      begin
        if P*Q = N then
        begin
          M:= (P-1)*(Q-1);
          if GreatestCommonDivisor(M, E) = 1 then
          begin
            FD:= InversMod(E, M);
            FE:= E;
            FN:= N;
            FM:= M;
            FP:= P;
            FQ:= Q;
            Break;
          end;
        end;
      end;
    end;
    P:= P+1;
  end;
end;

Fazit: Der einzige Schutz, den man bei der RSA Verschlüsselung hat, ist, das bei großen Zahlen, empfohlen sind 155 Stellen (int512), diese Procedure Jahre dauert. Für Zahlen im int64 Bereich ist die RSA Verschlüsselung nicht geeignet.

[Bummi]

Dann sind wir alle jetzt beruhigter...

[negaH]

Zitat von Bjoerk:

Das ist leider nicht richtig.

Leider ist das was du als Beispiel bringst ebenfalls nicht richtig. Du berechnest nicht direkt aus dem öffentlichen Schlüssel den privaten sondern du testest alle Kandidaten durch bis es stimmt. Das ist ein Unterschied.

Man kann N faktorisieren und das wird letzendlich, nach meinem Wissenstand, immer ein Such-Algorithmus sein der letzendlich per Trial&Error funktioniert.

Ich kenne kein praktisches Verfahren um eine zusammengesetzte Zahl, wie beim RSA notwendig, direkt in ihre Primzahlfaktoren zu zerlegen.

Gruß Hagen

[Bjoerk]

Doch, da N das Produkt von 2 Primzahlen ist, gibt es genau eine Möglichkeit. Und D = InversMod(E, M)

[Micha88]

Ich bekomme es fast kompiliert.

Nur findet er InversMod() nicht.
Gibt es dazu einen Code? Möchte nur ungern eine komplette Komponente nur für eine Funktion installieren.