RSA Algorithmus - Geheimer Schlüssel

[d4rkf]

Hallo zusammen!

Mal wieder ein kleines Problem. Mittlerweile steht fest, dass ich den RSA-Algorithmus im Abi als Präsentationsthema hab. Den Algorithmus hab ich soweit verstanden und auch begonnen ihn umzusetzen. Mein Problem ist jetzt der private Schlüssel.

So wie ichs verstanden hab müsste das ganze so aussehen:

e·d ≡ 1 mod φ(N)

e und φ(N) hab ich ja schon, die Frage ist jetzt nur wie ich das in Delphi umsetzen kann?
Hat irgendjemand nen Quellcodefetzen um mir das zu veranschaulichen?

Danke im vorraus!
Gruß d4rkf

[CalganX]

Hi,
Codefetzen habe ich jetzt direkt keine, aber ich verstehe gerade deine Frage nicht. ;)
Willst du Modulo-Arithmetik und das Eulersche Phi umsetzen?

Für Ersteres: einfach per mod. Dein Beispiel würde also ungefähr so aussehen:

Delphi-Quellcode:

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

Und wenn du das Eulers. Phi umsetzen willst. Überlege dir einfach, wie du alle Zahlen zwischen 1 und n herausfindest, die mit n den ggT 1 haben. Das sollte also soweit klar sein (für den ggT kannst du dir den euklidischen Algorithmus ansehen).

Hope that helps,
Chris

[BenjaminH]

Die Eulerfunktion ergibt sich, wenn N als Produkt zweier Primzahlen gewählt wird so:

Code:

(p-1)*(q-1)

Ich hoffe mich da richtig zu erinnern, ich hab da letztes Jahr ne AG drüber belegt.
[Edit="Zu schnell gelesen"]

Zitat:

Zitat von d4rkf

e und φ(N) hab ich ja schon

[d4rkf]

Erstmal danke für die Antwort!
Ich versuchs mal genauer zu schildern:

Zitat:

1. Für die beiden Primzahlen p und q nehmen wir p = 11 und q = 13. Damit wird N = 143.
2. Die Eulerfunktion nimmt damit den Wert φ(N) = φ(143) = (p-1)(q-1) = 120 an.
3. Für die zu φ(143) = 120 teilerfremde neue Zahl e wähle man e = 23.
4. Mit diesen Werten erhalten wir die Bedingung: 23·d ≡ 1 mod 120. Das heißt: Das Produkt soll bei Division durch 120 den Rest 1 lassen. Man kann damit die Kongruenz als Gleichung schreiben: 23·d = k·120 + 1. Dabei ist k eine ganze Zahl. Als eine Lösung dieser diophantischen Gleichung 120·k - 23·d = -1 ergibt sich d = 47 und k = 9. Damit wird d = 47 der geheime Schlüssel, e = 23 und N = 143 der öffentliche Schlüssel.

*Stammt von Wikipedia

Also ich will noch den 4. Punkt (s.o.) in Delphi umsetzen und hab eigentlich nur Probleme mit dem Aufbau des Codes. Mitm Taschenrechner klappt alles prima, nur in Delphi wills nicht!

[d4rkf]

Problem hat sich erledigt!
Jetzt muss ich nur noch mit großen Zahlen arbeiten können... 1000^1000 und mehr ;)

[alzaimar]

Such mal nach TBigNum

[TeronG]

Zitat:

Zitat von d4rkf

Jetzt muss ich nur noch mit großen Zahlen arbeiten können... 1000^1000 und mehr ;)

warum muss ich nun Plötzlich an Hagen denken ??? :gruebel: :zwinker:

[d4rkf]

hab mich schon an ihn gewendet!

ich brauch nur ne möglichst einfache möglichkeit, schnell muss das programm nicht rechnen, nur genau!
da ich relativer delphi-neuling bin, weiß ich nicht wie ich zum beispiel die TBigNumber benutzen muss... könnte mir das jemand erklären?

[TeronG]

Hab mit Delphi noch net so viel gerechnet ... aber evtl. hilft dir DAS weiter ... (da findest du auch die 3 DECMath's drinnen ..)

[d4rkf]

der beitrag wurde mir von hagen auch schon empfohlen, mein problem is nur, dass ich vermutlich vor lauter bäumen den wald nicht seh und nicht weiß wie ich das in meinem projekt integrieren kann...