Entwickler-Ecke
Algorithmen, Optimierung und Assembler - RSA-Verschlüsselung
Tigu - Mo 25.12.06 18:42
Titel: RSA-Verschlüsselung
Hallo!
Ich muss am ersten Schultag einen Vortrag zum Thema RSA-Verschlüsselung halten.
In der Theorie habe ich das Verfahren ja auch verstanden, aber ich habe keine Idee, wie man das in einen Quelltext verwandeln kann. :gruebel:
Hat jemand vielleicht ein Beispiel, was er mir mal zeigen könnte, damit ich sehe wie es geht (es geht sowohl um Ver-, als auch um Entschlüsselung) oder einen Tipp zur Programierung für mich?
Vielen Dank für eure Hilfe
Tigu
ConditionZero - Mo 25.12.06 18:48
Verschlüsselung:
Um eine Nachricht K zu verschlüsseln, verwendet der Absender die Formel
C \equiv K^e \mod N
und erhält so aus dem Klartext K den Geheimtext C.
Beispiel:
Es soll die Zahl 7 verschlüsselt werden.
Der Nachrichtenabsender benutzt den veröffentlichten Schlüssel N = 143, e = 23 und rechnet
C \equiv 7^{23} \mod 143
Zur Berechnung von 723mod 143 kann die Kongruenzarithmetik verwendet werden. Mit Hilfe der modularen Exponentiation berechnet man schnell:
7^{23} \ \bmod \ 143 \ = \ ((( 7^2 )^2\cdot 7)^2\cdot 7)^2\cdot 7 \ \bmod \ 143 = 2
Dabei wendet man nach jedem Rechenschritt auf die zu handhabenden Zahlen die Modulo-Operation (kurz: mod) an, um die Ergebnisse möglichst „klein“ zu halten.
Aus dem Klartext 7 ist somit der Geheimtext 2 geworden.
Entschlüsselung:
Der Geheimtext C kann durch modulare Exponentiation wieder zum Klartext K entschlüsselt werden. Der Empfänger benutzt die Formel
K \equiv C^d \mod N
mit dem nur ihm bekannten Wert d sowie N.
Beispiel:
K \equiv 2^{47} \ \bmod\ 143 = ((((2^2)^2 \cdot 2)^2 \cdot 2)^2 \cdot 2)^2 \cdot 2 \ \bmod\ 143 = 7
Aus C = 2 wird also wieder K = 7.
Q
http://www.wikipedia.de
Tigu - Mo 25.12.06 19:22
Danke!
Bei Wikipedia bin ich aber vorher schon gewesen.
ConditionZero - Mo 25.12.06 19:24
Hm also du weißt nur nicht wie du es Delphi beibringen sollst?
Also mit Stift und einem Blatt Papier könntest du Ver- und Entschlüsseln?
Die Formeln hast du also verstanden?
Tigu - Mo 25.12.06 19:28
So auf anhieb würde ich deine Frage mal mit ja beantworten.
Habe mich schon eine ganze Weile damit beschäftigt, auch Arbeiten zu dem Thema gelesen, aber wie ichs in Delphi schreibe? :gruebel:
ConditionZero - Mo 25.12.06 19:41
Also ich versuche das jetzt sleber zu verstehen, dann schreib ich mal ne kleine Beispielanwendung an der du dich orientieren kannst.
Tigu - Mo 25.12.06 19:44
Super, Vielen Dank. :zustimm:
Zum Verstehen, fand ich das Beispiel im Anhang ganz gut.
BenBE - Mo 25.12.06 19:46
Ne andere Beispielanwendung findest Du aber auch bei dem Link oben in meinem ersten Post.
Tigu - Mo 25.12.06 19:48
Ja, danke auch dir, bin am Durcharbeiten. :les:
ConditionZero - Mo 25.12.06 20:54
Moment mal...
In dem Link von
BenBE ist ja schon ein Sample drinnen *WandgegenKopfHau* (Ich weiß den Smilie-Code ned :P)
Naja dann kann ich mir das ja sparen weil meins sieht momentan auch so aus.
LG
Tigu - So 07.01.07 01:09
Mein Problem ist, wie komme ich auf e? e*d=n das ist klar, aber ist e eine Zufallszahl<n oder lässt man den Benutzer eine Zahl eingebn, durch die n teilbar ist? Sollten ja glatte Zahlen für e und d rauskommen.
Sirke - So 07.01.07 13:34
Du gehst relativ vorschnell an die ganze Sache ran, weil es dabei noch sehr viele Stellen gibt, an denen es Probleme gibt, z.B. wie interpretiert man die Buchstaben in Zahlen und umgekehrt bei einem so großen N! Es gibt sehr viele Tücken, die diese Umsetztung sehr schwer machen, vorallem für größere Zahlen und Texte.
Aber zu deinem Problem:
e * d = N ist Falsch! Die Gleichungen lauten mod( e * d, Phi(N) ) = 1 oder e * d + k + Phi(N) = 1! Außerdem hat e als Bedingung 1 < e < Phi(N) und muss teilerfremd zu Phi(N) sein. Also bilde eine Zufallszahl und zähle immer einen dazu und prüfe beide Bedingungen. (Optimal: Bilde eine ungerade Zufallszahl und zähle immer zwei dazu ;))
Das d wird über diese Gelichung ermittelt: e * d + k + Phi(N) = 1!
MfG Sirke
Tigu - Mo 08.01.07 20:13
Hallo ihr, ja immer noch ein Problem mit dem Programm.
Kann mir mal bitte jemand etwas aus BenBe´s Quelltext erklären?
Die Funktion, die er für den Primzahltest geschrieben hat, verstehe ich nicht so wirklich.
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
| Function isPrim(Value: integer): Boolean;
Var
i, t: Integer;
Begin
t := round(sqrt(Value));
For i := 2 To t Do
If Value Mod i = 0 Then Begin
result := false;
exit;
End;
result := true;
End; |
value steht doch für den Inhalt,des Edit-Feldes, welches später, beim Aufruf der Funktion, eingesetzt wird.
Was bewirkt aber das Exit (beenden des aktuell aktivierten?) und warum muss ich von i=2 ausgehen?
Danke für eure Hilfe
Tigu
Dragonclaw - Mo 08.01.07 20:57
| Tigu hat folgendes geschrieben: |
value steht doch für den Inhalt,des Edit-Feldes, welches später, beim Aufruf der Funktion, eingesetzt wird.
Was bewirkt aber das Exit (beenden des aktuell aktivierten?) und warum muss ich von i=2 ausgehen?
|
Exit bewirkt das er abbricht, sobald er eine zahl gefunden hat durch die die gesuchte Zahl teilbar ist, dadurch ist die Zahl auf JEDENFALL keine Primzahl, daher ist die weitere Überprüfung notwendig. i ist am Anfang 2 weil sonst JEDE Zahl als NICHT primzahl beurteilt würde.
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!