RSA-Verschlüsselung im Maple < Mathe-Software < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:15 So 03.12.2006 | | Autor: | epsilon1 |
| Aufgabe | | Erzeugen Sie zwei große Primzahlen. Schreiben Sie eine Prozedur verschluesseln und eine Prozedur entschluesseln, die mit der Hilfe der oben erzeugeten Primzahlen die RSA-Ver/Ent-Schlüsselung durchführt. |
Hi.
Die Primzahlen konnte ich noch erzeugen. Ich habe einfach gesagt
---
> Z = 100000000000000000;
> p := nextprime(Z);
> q := nextprime(p);
----
Nur jetzt weiß ich überhaupt nicht mehr weiter und hoffe, dass mir jemand einen Tipp geben kann, wie ich überhaupt anfangen muss.
Danke!!
|
|
| |
|
Hallo,
ich mache das mal kurz, die Theorie dahinter müsstest du ja kennen. Mein Vorschlag wäre:
p := nextprime(rand());
q := nextprime(rand());
n := p*q;
e := nextprime((p-1)*(q-1)); #public key, muss prim sein zu (p-1)*(q-1)
d := LinearAlgebra[Modular][Inverse]((p-1)*(q-1),<<e>>)[1,1];
verschl := x -> x&^e mod n;
entschl := x -> x&^d mod n;
Eine mögliche Anwendung könnte so aussehen:
klartext := "Hallihallo";
klarbytes := convert(klartext, 'bytes');
geheimbytes := map(verschl, klarbytes);
klarbytes2 := map(entschl, geheimbytes);
klartext2 := convert(klarbytes2, 'bytes');
Am Ende sollte in klartext2 dasselbe stehen wie in klartext.
Gruß
Martin
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 07:02 Mo 04.12.2006 | | Autor: | epsilon1 |
Hallo.
Ich habe das jetzt mal versucht zu machen und bin im Internet auf eine Homepage gestoßen, welche das Prinzip erklären in Maple.
Nun wollte ich dich nochmal fragen, ob ich das so jetzt richtig gemacht habe bzw. warum funktioniert das eigentlich so?
Wie kann ich das ganze jetzt auf Buchstaben anwenden? Zur Zeit geht das ja nur mit Zahlen...
zahl := 123456789123456789;
zahl := 123456789123456789
>
> p := nextprime(zahl);
p := 123456789123456823
> q := nextprime(p);
q := 123456789123456889
>
> n := p * q;
n := 15241578780673695058832363293403647
>
> m := (p - 1) * (q - 1);
m := 15241578780673694811918785046489936
>
> e := 7;
e := 7
>
>
> ifactor(m);
4 5 2
(2) (3) (11) (47) (59) (3366776419) (6245934377)
(555593)
>
>
> d := e^(-1) mod m;
d := 8709473588956397035382162883708535
>
> message:=1234;
message := 1234
>
> code:=Power(message,e) mod n; #message kodieren
code := 4357186184021382204544
>
>
> decode:=Power(code,d) mod n; #und wieder dekodieren
decode := 1234
>
|
|
|
| |
|
Hmmm, steht alles in meinem Beitrag...
Das Umwandeln von Text nach Zahlenliste und umgekehrt geht per convert.
Das Anwenden einer Funktion auf eine ganze Liste geht per map.
> ifactor(m);
Was willst du damit?
Warum das so funktioniert? Das steckt etwas Theorie dahinter und ich dachte, die müsstest du eigentlich kennen. Oder geht es dir um die Maple-Funktionen?
Gruß
Martin
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 08:53 Mo 04.12.2006 | | Autor: | epsilon1 |
Hi Martin,
danke für deine Nachricht. Ist es dann so, dass ich das was ich jetzt code und decode genannt habe in einer Prozedur speichern muss und dann bei map der erste Punkte diese Prozedur dann ist?
Wie kann ich das denn in einer Prozedure umsetzen? Du weisst doch, dass ich mich bei den Prozeduren noch sehr schwer tue...
Danke!
|
|
|
| |
|
Hallo,
eine Prozedur wäre vielleicht etwas zuviel Aufwand. Man kann es auch einfacher haben:
Schreib code und decode in Funktionen um wie ich oben verschl und entschl.
Dann schreibst du zwei Funktionen codeAll und decodeAll, die Folgendes machen:
codeAll konvertiert per convert (s. mein Beitrag) einen String in eine Liste von Zahlen um und wendet darauf per map die Funktion code an.
decodeAll wendet per map die Funktion decode auf die Liste der Zahlen an und konvertiert dann per convert die erhaltene Lsite von Zahlen in einen String.
Schon kannst du Strings kodieren und dekodieren.
Gruß
Martin
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 09:07 Mo 04.12.2006 | | Autor: | epsilon1 |
Hi Martin,
danke. Doch irgendwie wird mir nicht klar, wie ich das machen soll. Ich habe das ganze jetzt zunächst mal so geschrieben:
>
> code := proc ( a , b , n ) local verschluesselt;
> verschluesselt := Power(a , b) mod n;
> end;
>
>
> decode := proc ( a , b, n ) local entschluesselt;
> entschluesselt := Power(a , b) mod n;
> end;
>
und wenn ich das mit meinem Zahlenbeispiele mache, dann funktioniert das ganze auch.
Wäre super, wenn du mir nochmal auf die Sprünge helfen könntest.
|
|
|
| |
|
Hallo,
bitte probier doch mal die Funktionen convert und map auf einfachen Beispielen aus. Und lass das mit den Prozeduren, es geht einfacher.
Eine Funktion kannst du erzeugen mit
f := x -> x^2;
Eine Funktion, die eine Zahl verschlüsselt, wäre nach deinem Programmcode:
codeSingleNum := a -> Power(a , b) mod n;
Eine Funktion, die eine andere Funktion auf eine ganze Liste von Zahlen anwendet, ist map, also:
codeAllNum := liste -> map(codeSingleNum, liste);
Jetzt musst du nur noch vorher die Liste aus einem String erzeugen, was eben mit convert geht. Also:
codeString := klartext -> map(codeSingleNum, convert(klartext, 'bytes'));
Ähnlich geht das Dekodieren, nur dass man hier zuerst rechnet und erst dann konvertiert. Bitte beschäftige dich damit, probier es aus.
Gruß
Martin
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 09:37 Mo 04.12.2006 | | Autor: | epsilon1 |
Irgendwie will das alles nicht so richtig wie ich das möchte.
Außerdem finde ich das schon toll, dass ich das für Zahlen schon einmal hinbekommen habe.
Das mit dem String aus deinem Post läuft aber nicht, er meinte immer n muss eine ganze zahl sein. Das ist sie aber...
|
|
|
| |
|
Ach, es muss natürlich
codeSingleNum := a -> Power(a , e) mod n;
heißen!
Es ist ja gut, dass du es für eine Zahl hinbekommen hast, aber ob du es mit einer Prozedur oder mit einer Funktion machst, ist jetzt egal. Es geht in erster Linie darum, es auf eine Liste von Zahlen (per map) zu erweitern und vorher natürlich die Liste aus einem String (per convert) zu erzeugen.
Mach es ruhig mit einer Prozedur, aber dann musst du dir vorher überlegen, was du ihr überhaupt übergeben willst.
Gruß
Martin
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 09:54 Mo 04.12.2006 | | Autor: | epsilon1 |
Hi.
Das kodieren funktioniert nun, nun hänge ich am Dekodieren. Kannst du mir da noch mal kurz auf die Sprünge helfen?
Wäre echt super.
Wie kann ich denn aus binary wieder einen string machen, zum Beispiel. Wie rechne nich mit dem codeString.
Hilfe...
|
|
|
| |
|
Hallo,
das Dekodieren einer Liste von Zahlen funkioniert genauso wie das Kodieren, nur ersetzt man hier e durch d.
Das Konvertieren von Liste nach String funktioniert haargenau wie das Konvertieren von String nach Liste.
Also: Zuerst dekodieren, dann konvertieren.
Es steht übrigens alles in meinem ersten Beitrag, es lässt sich sogar recht simpel in deinen Code einfügen.
Gruß
Martin
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:47 Mo 04.12.2006 | | Autor: | epsilon1 |
Hi.
Ich habe mich nochmal rangesetzt und habe nun insgesamt das folgende:
>
>
> codeSingleNum := a -> Power(a , e) mod n;
codeSingleNum := a -> Power(a, e) mod n
>
> codeAllNum := liste -> map(codeSingleNum, liste);
codeAllNum := liste -> map(codeSingleNum, liste)
>
> codeString := klartext -> map(codeSingleNum, convert(klartext, 'bytes'));
codeString :=
klartext -> map(codeSingleNum, convert(klartext, 'bytes'))
>
>
> decodeSingleNum := a -> Power(a , d) mod n;
decodeSingleNum := a -> Power(a, d) mod n
>
> decodeAllNum := liste -> map(decodeSingleNum, liste);
decodeAllNum := liste -> map(decodeSingleNum, liste)
>
> decodeString := codetext -> map(decodeSingleNum, convert(codetext, 'string'));
decodeString :=
codetext -> map(decodeSingleNum, convert(codetext, 'string'))
>
>
> m := "Hallo";
m := "Hallo"
>
> code1 := codeString(m);
code := [10030613004288, 80798284478113, 171382426877952,
171382426877952, 207616015289871]
> decodeString(code1);
Error, (in mod/Expand) polynomial over a finite field expected
Warum erhalte ich beim Decodieren eine Fehlermeldung?
|
|
|
| |
|
Hallo,
beachte die Reihenfolge:
> Also: Zuerst dekodieren, dann konvertieren.
Das ist anders als bei Kodieren, denn du entschlüsselst zuerst die Zahlen und wandelst dann in eine andere Darstellung um.
Übrigens muss es immer noch 'bytes' heißen und nicht 'string'.
Gruß
Martin
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:56 Mo 04.12.2006 | | Autor: | epsilon1 |
Aber ich mache doch zuerst DecodeSingelNum und Konvertiere dann....
Wie soll ich das denn umdrehen ....
|
|
|
| |
|
Nein,
du machst es genau falsch herum. Du wendest zuerst convert auf deine Liste an und dann erst map auf das Ergebnis an. Es geht nicht um die Reihenfolge in der Schreibweise sondern um die Reihenfolge der Ausführung, also, was die innere (zuerst ausgeführte) und was die äußere Funktion sind. Du musst also map und convert geschickt vertauschen, so dass zuerst dekodiert wird und das Dekodierte dann von einer umschließenden Funktion in einen String umgewandelt wird.
Gruß
Martin
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:05 Mo 04.12.2006 | | Autor: | epsilon1 |
Danke!!!
Es geht!!!! Mit der Hilfe dieser kleinen Zeile:
decodeString := codetext -> convert( map (decodeSingleNum, codetext), 'bytes');
Vielen, vielen Dank!
|
|
|
|
