Hallo liebe leute,
Legende:
N = Modul,
e = Verschlüsselungsexponent,
p, = die erste Primzahl,
q = die zweite Primzahl,
Ich habe mir gerade zur Aufgabe gemacht den RSA Algorithmus nachzuprogrammieren. Beim RSA handelt es sich um ein asymmetrisches Kryptosystem. Dies beudetet, dass es immer ein public + privatekey geben muss.
Also:
N = p * q ist , bzw phi(n) = (p-1) * (q-1)
Um N zu berechnen habe ich nun einen primzahlenteilung durchgeführt. Dies ist soweit kein problem. Nehmen wir nun an, dass wir die zwei primzahlen haben. Ihr fragt euch bestimmt warum ich p-1 gerechnet habe. Ganz einfach, jede teilfremde reste von der eulrischen Phi-Funktion einer Primzahl ist immer -1. Nehmen wir an, wir haben p = 5, somit sind die teilfremde reste 1,2,3,4. Haben wir p=4 , sind die teilfremde reste 1 und 3 = schwer zu berechnen. Deshalb spalten wir alles auf primzahlen auf. D.h (p-1) ist nichts anderes als phi(p).
zu beachten: "e" muss zu phi(n) teilfremd sein! e und N bilden dann logischerweise den "publickey".
Um die Inverse von e zu berechnen brauche ich jedoch noch k. Für das muss ich den erweiterten euklidischen Algorithmus anwenden. Genau damit habe ich probleme. Könnte mir jemand diesen Algorithmus erklären? Mit diesem Algorithmus kommt man dann auf den Private key sowie auf k.
Das problem bei diesem ganzen RSA-Knack-Algorithmus ist der punkt, indem man die Primzahlen sucht. Versucht mal von eienr 1024bit zahl die primzahlenteilung durchzuführen und ihr merkt was ich meine. Das ganze verhält sich nämlich exponentiel. Aber macht nichts, es ist eine nette herausfodering dies nachzuprogrammieren :).
Nunja, da ich erst 16 jahre alt bin ist es sehr schwer für mich mit einem altersgenossen darüber zu diskutieren da dies meist über die Durchschnittsverhältnisse der jeweiligen Person geht und sie nur "bahnhof" verstehen. Darum versuche ich hier mein glück ;)
Bisheriger Sourcecode:
Code:bool RSA::IsPrimzahl(__int64 nr)
{
for(__int64 d = 2; d*d <= nr; d++)
{
if (!(nr % d))
return false;
}
return true;
}
__int64 RSA::phiVonN(__int64 *pq)
{
return ((pq[0] -1) * (pq[1]-1));
}
void RSA::Primzahlenzerlegen(__int64 Number, __int64* pq)
{
__int64 p;
for(__int64 q = 3; (q*q) <= Number; q += 2)
{
if (Number % q == 0)
{
if (IsPrimzahl(q))
{
p = Number / q;
if (IsPrimzahl(p))
{
pq[0] = p;
pq[1] = q;
break;
}
}
}
}
}
