RSA: Entschlüsseln ohne geheimen Schlüssel
Neue Frage »

21.01.2010, 18:47 mainfield Auf diesen Beitrag antworten »
RSA: Entschlüsseln ohne geheimen Schlüssel
Hallo,

Es sollen Buchstaben entschlüsselt werden. Hierbei wurde A durch 0, B durch 1, C durch 2 usw. kodiert.

Ich habe nur die zwei öffentlichen Schlüssel n (18 Stellen), e (8 Stellen) und die verschlüsselten Botschaften gegeben (den privaten Schlüssel soll ich nicht bestimmen).

Meine Idee war:
Ich berechne für alle Buchstaben (0 <= x <= 25) die zugehörige geheime Zahl (y = x ^ e mod n). Danach vergleiche ich diese 25 berechneten Zahlen mit den gegebenen Botschaften. Wenn sie gleich sind, dann kann ich den entschlüsselten Wert aus der Tabelle ablesen.

Allerdings ist e 8-Stellig. Somit würde das Berechnen von x ^ e ewig dauern.

Ist meine Idee, wie ich die Botschaften entschlüsseln kann OK, oder gibt es bessere Möglichkeiten?

Vielen Dank für Eure Hilfe,
mainfield
23.01.2010, 00:40 Abakus Auf diesen Beitrag antworten »
RE: RSA: Entschlüsseln ohne geheimen Schlüssel
Hallo!

Wenn es so gegeben ist, kannst du ggf. mit der Häufigkeitsverteilung die Buchstaben raten, etwa nach dem Prinzip, e ist häufigster Buchstabe usw.

Natürlich kannst du auch rechnen, und so lange dauert es nicht (sukzessive modulo rechnen).

Grüße Abakus smile
23.01.2010, 12:38 Mystic Auf diesen Beitrag antworten »
RE: RSA: Entschlüsseln ohne geheimen Schlüssel
Zitat:
Original von mainfield
Allerdings ist e 8-Stellig. Somit würde das Berechnen von x ^ e ewig dauern.
Ist meine Idee, wie ich die Botschaften entschlüsseln kann OK, oder gibt es bessere Möglichkeiten?


Deine Idee ist im Prinzip ok, ob es bessere Möglichkeiten gibt, darüber kann man unmöglich etwas sagen ohne die konkreten Angaben, was e und n (die Stelligkeit allein ist zuwenig!), sowie auch die Chiffrate betrifft... Warum stellst du eigentlich nicht die vollständige Aufgabe hier rein? verwirrt
23.01.2010, 12:42 kiste Auf diesen Beitrag antworten »

Ich glaube kaum dass der Fragesteller sich noch mal um die Aufgabe kümmern will. Die Abgabe von dem Übungsblatt war gestern Big Laugh
Die Lösung einfach x^e mod n auszurechnen war natürlich richtig und die Aufgabe auch so gedacht(von Informatikern kann man erwarten dass sie dafür ein kleines Programm schreiben und nicht es in den nächstbesseren Taschenrechner eingeben Big Laugh )
23.01.2010, 17:36 mainfield Auf diesen Beitrag antworten »

Zitat:
von Informatikern kann man erwarten dass sie dafür ein kleines Programm schreiben und nicht es in den nächstbesseren Taschenrechner eingeben

Und wie sieht das Programm Deiner Meinung nach aus bzw. wie lange würde es für die Berechnung brauchen?
23.01.2010, 18:28 kiste Auf diesen Beitrag antworten »

code: 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:

(define (fastexp x e n) 
  (if (= e 0) 
      1 
      (if (= e 1) 
          x 
          (if (even? e)
              (let ((a (fastexp x (/ e 2) n))) (modulo (* a a) n))
              (let ((a (fastexp x (/ (- e 1) 2) n))) (modulo (* (modulo (* a a) n) x) n))
              )
          )
      )
  )

mit Aufruf
code: 
1:

(fastexp 2 78964867 382578193981090189)
liefert das Ergebnis 209306962383811566 in für mich nicht messbarer Zeit.

(Funktional in Scheme geschrieben weil ich dann mitbekomme wenn du versuchst das noch abzugeben Big Laugh )
 Anzeige 
 
24.01.2010, 01:39 mainfield Auf diesen Beitrag antworten »

Habe Deine Funktion in Java umgeschrieben. Und da ist mir klar geworden, was sie macht und ... dass ich da eigentlich auch selber hätte drauf kommen können. unglücklich


Zitat:
Ich glaube kaum dass der Fragesteller sich noch mal um die Aufgabe kümmern will.

Nö, mir ging's eigentlich nicht mehr um die Aufgabe. Wollte einfach noch wissen, wie man sowas schneller berechnet.


Zitat:
(Funktional in Scheme geschrieben weil ich dann mitbekomme wenn du versuchst das noch abzugeben Big Laugh )

Hehe, wird wohl nicht passieren - allein schon weil ich Dich nicht weiters kenne. Big Laugh

Nochmals Danke an alle für Eure Hilfe.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »


MatheBoard » Hochschulmathematik » Sonstiges » RSA: Entschlüsseln ohne geheimen Schlüssel