Verschlüsselung : RSA-Algorithmus
Ich bin Implementierung des RSA Algorithmus für die Verschlüsselung und Entschlüsselung, wie Sie hier angegeben:
http://www.di-mgt.com.au/rsa_alg.html
Aber nicht verstehen konnte, die random prime number generation Teil in der Schlüssel-Generierung.
Also ich nehme zwei Primzahlen, die als Eingabe vom Benutzer. Ich hatte Schwierigkeiten mit der Generierung der e auch. also machte ich es-Konstante (e= 17)
Einige prime Anzahl Eingänge arbeiten korrekt ( ich.e-Codierung und-Decodierung korrekt) in gcc unter linux, aber nicht in devcpp unter windows. (e.g 53,61)
Hier ist der Schlüssel-Generierung code:
/* Generates private and public keys and saves into two separate files */
void keygen()
{
int p,q,phi,d,e,n,s;
printf("\n Enter two prime numbers: ");
scanf("%d%d",&p,&q);
n = p*q;
phi=(p-1)*(q-1);
e=17;
//selec d such that d*e = 1+ k*phi for some integer k.
d = 0;
do
{
d++;
s = (d*e)%phi;
}while(s!=1);
printf("\n public key: { e=%d n=%d }",e,n);
printf("\n private key: { d=%d n=%d }\n",d,n);
}
Brauchen Hilfe und Anregungen in der Primzahl-und e-generation.
- pastebin ist nicht verwendet auf Stackoverflow. Bitte geben Sie Ihren code in der Frage selbst und versuchen, es zu begrenzen, die Teile, die Sie beunruhigen.
- Tun Sie dies für Ihre eigene Unterhaltung und Bildung oder für eine Produktion Anwendung? Falls letzteres zutrifft, verwenden Sie eine vorhandene Bibliothek wie openssl.
- Wenn Sie möchten, dass der code geeignet für Sicherheits-Anwendungen, die dann zusätzlich zu prime generation-problem, das Sie implementieren müssen, um arithmetische Operationen, die für sehr lange zahlen. Mehr oder weniger sichere Schlüssellänge von 2048 bits (noch kann geknackt werden, wenn Sie genügend Ressourcen haben, wenn). Damit Ihre 32-bit-Schlüssel (n = p*q) ist einfach nur lächerlich. Wenn Sie möchten, spielen Sie einfach mit - es ist OK.
- Ihre while-Schleife nicht garantiert, um zu beenden. Für
e
haben eine inverse modphi
GCD(e,phi)=1, ein Zustand, nicht garantiert, um wahr zu sein.
Du musst angemeldet sein, um einen Kommentar abzugeben.
so dass Sie bereits wissen, dass e * d zu sein, muss kongruent zu 1 mod phi(n)
da Sie wissen, phi(n) ein Tupel (e,d) kann berechnet werden, indem mit Hilfe des erweiterten euklidischen Algorithmus (EEA):
wähle eine ganze Zahl e (meist eine kleine ganze Zahl ist; dies ist der öffentliche exponent Verschlüsselung wird schneller mit kleineren Exponenten), der kleiner als phi(n) und größer als 2 (?... ich denke, dass)
wenn Sie ein Kandidat für e, berechnen Sie den größten gemeinsamen Teiler (gcd) von e und phi(n) ... 1 ... wenn nicht, wählen Sie einen neuen Kandidaten für e und wiederholen (da gäbe es keine modulare inverse, in anderen Worten kein privater exponent d, existiert für diese e und phi(n))
nachdem Sie wissen, dass gcd(e,phi(n))==1 berechnen Sie d mit dem EWR (oder als shortcut, berechnen EWR direkt, da es auch den GCD ... wenn das keine 1 ist, wählen Sie einen neuen Wert für e)
EWR (quick and dirty für die Berechnung der modularen inversen):
stellen Sie sich eine Tabelle mit 3 Spalten:
lässt sagen diesen Spalten genannt werden: b, f und t
also die Zeilen, die Tabelle wird wie folgt Aussehen:
b0, q0, t0
b1, q1, t1
...
(und so weiter)
den ersten 2 Zeilen werden zuerst gefüllt.
für alle anderen Zeilen gibt es eine itterative Regel, die angewendet werden können, um die vorherigen zwei Zeilen führen, in der die Werte für die nächste Zeile
den ersten 2 Zeilen sind:
phi(n), NO_VALUE, 0
e, Boden(phi(n)/e), 1
den itterative Regel zu erstellen, die die nächste Zeile ist: (wobei [] der index-operator für die Auswahl der Zeile)
b[i] = b[i-2] mod b[i-1]
q[i] = b[i-1] /b[i] (integer-division, Brüche ... )
t[i] = t[i-2] - ( q[i-1] * t[i-1] )
können Sie Abbrechen die Regelung, wenn b[i] wird zu 0 oder 1 ... die Sie nicht wirklich brauchen q für die Letzte Zeile ...
also, wenn b[i] 0, b[i-1] kann nicht 1 sein, da Sie haben sollte, abgebrochen wird, wenn Sie berechnet, b[i-1], wenn 1 ...
wenn Sie erreichen, b[i]==0, b[i-1] ist die gcd ... da ist es nicht 1 Sie benötigen einen neuen Wert für e
wenn b[i]==1 Ihr ggT 1 ist, und es gibt eine inverse ... und das ist t[i] (wenn t negativ ist, fügen Sie phi(n))
Beispiel mit echten Werten:
sagen wir mal phi(n) ist 120
sagen wir, wir wählen 23 als Kandidat für e
unserem Tisch Aussehen wird:
dem letzten berechneten b ist 1, also => ggT(23,120) == 1 (Beweis: die inverse existiert)
die zuletzt berechnete t 47 => 23*47 mod 120 == 1 (t ist die inverse)
Ich weiß es nicht, aber wenn der gleiche code, kompiliert mit zwei verschiedenen Compilern gibt unterschiedliche Antworten würde ich vermuten, dass einige der Arten sind von verschiedener Größe oder Sie sind implizit sich auf Undefiniertes Verhalten irgendwo.
Das erste, was Sie tun sollten, ist, die gleiche Primzahl-Paare, überprüfen Sie, dass alle Konstanten, die Sie erzeugen aus der gleichen in beiden Implementierungen. Wenn nicht, ist Ihr Schlüsselpaar generation algorithmen sind Schuld.
Die nächste Sache ist, um sicherzustellen, dass Sie Ihren input-Daten für die Verschlüsselung ist absolut identisch auf beiden Systemen. Achten Sie insbesondere auf, wie der Umgang mit end-of-line-Zeichen. Bedenken Sie, dass, auf Windows, das Ende der Zeile ist
\r\n
und auf Linux ist es\n
. Die meisten Windows-Bibliothek Implementierungen konvertieren\r\n
zu\n
wie die Datei eingelesen wird, wenn"r"
angegeben wird, als parameter modefopen()
. Ihre Umsetzung könnte anders sein.Schließlich, was auch immer das problem ist, auf keinen Fall jemals
gets()
Wenn Sie auch fangen, selbst darüber nachzudenken, erneut zu verwenden, entfernen Sie die Frontallappen des Gehirns mit einem Eispickel.Folgenden die praktischen Hinweise am Ende der verlinkten Seite würden Sie ankommen, so etwas wie dies für die prime generation:
test_prime
soll eine Umsetzung der Miller-Rabin-test. Die obige Funktion macht bestimmte Annahmen und hat einige Nachteile:int
ist 32 bitrand()
ist in der Regel nicht ein guter Zufallszahlengenerator zu verwenden, für ernsthafte VerschlüsselungVerwenden Sie nicht diese in einem Produktions code.
Laut dem Artikel scheint es ok zu wählen
e
behoben.