HÜ A1

R_Egert
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 180
Registriert: 8. Sep 2009 23:27

Re: HÜ A1

Beitrag von R_Egert »

e is zufällig gewählt ;) (Gibt in mancher Literatur bevorzugte Werte, aber das ist hier nicht gefragt^^)

und bei RSA gibt es ja bestimmte Dinge die für d gelten müssen ;)

hilft das weiter?^^

mfg Rolf
Tutor:
  • Einführung in Trusted Systems WS11/12, WS12/13, WS13/14, WS14/15
  • GDI II SS11, SS12, SS13, SS14
  • Einführung in die Kryptographie WS14/15

philipp_m
Mausschubser
Mausschubser
Beiträge: 99
Registriert: 4. Dez 2010 18:10

Re: HÜ A1

Beitrag von philipp_m »

Als kurze Hilfe, bevor sich noch jemand zu sehr hinein steigert:
Es genügen die Bedingungen auf ts-4.pdf Seite 5, der danach erläuterte Algorithmus zur effizienten Exponentiation modulo n sowie der Euklid und der erweiterte Euklid aus den Mathematischen Grundlagen zur Lösung der Aufgabe. Vielleicht noch ein speziellerer Tipp hierzu, der auch beim zweiten Problem von Erich helfen dürfte: Der einfache Euklid genügt für den ggT, der erweiterte Euklid jedoch liefert noch ein Paar Werte mehr, und genau einen davon benötigt man.
Der Rest ist nur modulare Arithmetik und das Generieren von Zufalls- und Primzahlen und dafür dürfen Programmbibliotheken verwendet werden.

kain
Mausschubser
Mausschubser
Beiträge: 92
Registriert: 30. Sep 2009 13:49

Re: HÜ A1

Beitrag von kain »

Mal ne Frage. Die Angabe von "512-bit" ist doch nur eine "obere Schranke"? Also kann man n so wählen, dass n > m und n < 2^512 gilt. Oder?


Danke.

Dennis Albrecht
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 222
Registriert: 4. Okt 2010 18:15

Re: HÜ A1

Beitrag von Dennis Albrecht »

kain hat geschrieben:Mal ne Frage. Die Angabe von "512-bit" ist doch nur eine "obere Schranke"? Also kann man n so wählen, dass n > m und n < 2^512 gilt. Oder?
Danke.
Also ich würde die 512 eher als untere Schranke sehen.
Anders ausgedrückt: mein n hat immer 512 bits. Somit kann ich sicher sein, dass jede 511-bit lange Message verschlüsselt werden kann.
Wenn dein n jetzt auch 511 oder 513 bits lang sein kann (je nachdem wie der Zufall arbeitet etc.) ist das bestimmt nicht schlimm, aber anhand der Länge des Modulus macht sich der Wortraum fest, daher sollte ein Modulus auch mehr oder weniger genau zu der Vorgabe passen.

Gruß

kain
Mausschubser
Mausschubser
Beiträge: 92
Registriert: 30. Sep 2009 13:49

Re: HÜ A1

Beitrag von kain »

OK, danke.

Ich muss aber nochmals nachfragen, ob das so stimmt, wie ich es verstanden habe.

Ich benutze die BigInteger-Klasse und deren Methode probablyPrime. Übergebe eine 256-Bit Zahl (zweimal), damit ich einmal p und einmal q bekomme um anschließend n = p * q zu berechnen.
Stimmt das so und welche Garantie gibt, dass die Methode probablyPrime auch eine Primzahl zurückliefert?

Erich
Mausschubser
Mausschubser
Beiträge: 57
Registriert: 17. Okt 2010 13:29

Re: HÜ A1

Beitrag von Erich »

@kain

in der Methodenbeschreibung steht, dass die Warscheinlichkeit, dass der Output KEINE Primzahl ist, nicht über 2^(-100) liegt.

Dennis Albrecht
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 222
Registriert: 4. Okt 2010 18:15

Re: HÜ A1

Beitrag von Dennis Albrecht »

Erich hat geschrieben:@kain
in der Methodenbeschreibung steht, dass die Warscheinlichkeit, dass der Output KEINE Primzahl ist, nicht über 2^(-100) liegt.
Sprich die Wahrscheinlichkeit reicht für unser Problem aus.

Erich
Mausschubser
Mausschubser
Beiträge: 57
Registriert: 17. Okt 2010 13:29

Re: HÜ A1

Beitrag von Erich »

Frage:

Ist es bei einigen hier auch passiert, dass Ver-und-Entschlüsseln nicht kommutieren wollen?

Ich halte mich streng an das Protokoll von Ts-4, seite 5:

2 256b-Primzahlen p und q, n = p*q, (phi(n)) = (p-1)*(q-1), öffentlicher Schlüssel e mit ggT(e, phi(n)) =1 ( e ist bei mir ein fixer Wert, beim dem dies aber die allermeiste Zeit passt ).
und ein privater Schlüssel d, wobei d das x vom erw.Euklid ist ( aber auch beim y funktioniert es nicht ).

Der erw.Euklid bei mir stimmt, ich habs getestet ( zugegeben: an nur 2 stelligen Zahlen ).
Die effiziente Exponentiation müsste ich auch richtig implementiert haben, diese ist ja alles andere als kompliziert.

Weiß einer, wo sich hier ein Fehlerteufel einschleichen könnte?

Dennis Albrecht
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 222
Registriert: 4. Okt 2010 18:15

Re: HÜ A1

Beitrag von Dennis Albrecht »

Ein paar Einfälle hätte ich, aber ne Ferndiagnose ist da recht schwer:

-hast du zur Berechnung von n und phi die Werte p und q genutzt oder vielleicht zweimal p oder zweimal q (den Fehler hatte ich auch schon bei nem Kommilitonen entdeckt)?
-wählst du in den Fällen, in denen dein e nicht passt einen anderen Wert?
-als d musst du den Wert wählen, der zu e gehört: sei x*e+y*phi=ggt(e,phi), dann ist d=x mod phi

Gruß

Erich
Mausschubser
Mausschubser
Beiträge: 57
Registriert: 17. Okt 2010 13:29

Re: HÜ A1

Beitrag von Erich »

Dennis Albrecht hat geschrieben:Ein paar Einfälle hätte ich, aber ne Ferndiagnose ist da recht schwer:

-hast du zur Berechnung von n und phi die Werte p und q genutzt oder vielleicht zweimal p oder zweimal q (den Fehler hatte ich auch schon bei nem Kommilitonen entdeckt)?
Nein.
-wählst du in den Fällen, in denen dein e nicht passt einen anderen Wert?
[/qote]

Bei mir werden mit jedem Durchlauf neue Zahlen gewürfelt, also würfele ich einfach neu ( und wie gesagt: es passt fast immer und auch bei den "passenden" fällen funktioniert es nicht )
-als d musst du den Wert wählen, der zu e gehört: sei x*e+y*phi=ggt(e,phi), dann ist d=x mod phi

Gruß
mach ich, genau so. ( soweit ich sehen kann ) :?

Aber danke für die Hilfe um die Uhrzeit ;)

philipp_m
Mausschubser
Mausschubser
Beiträge: 99
Registriert: 4. Dez 2010 18:10

Re: HÜ A1

Beitrag von philipp_m »

Also erstens einmal habe ich die Aufgabenstellung so verstanden, dass e zufällig gewählt sein muss, also gäbe eine Lösung mit fixem e wohl nicht die vollen Punkte.
Wie behandelst du negative d-Werte? Wenn man alle Algorithmen einfach übernimmt, ist d in der Hälfte der Fälle (geschätzt) negativ, womit dann der Standardalgorithmus zum Dekodieren nicht mehr arbeiten kann. Die einfachste Möglichkeit, dennoch richtig zu dekodieren, ist, in diesem Fall einfach phi zu d hinzuzuaddieren.
Sonst muss in einem deiner Algorithmen ein Fehler sein, denn wie oben beschrieben habe ich auch nicht mehr als die 3 Algorithmen für sämtliche Berechnungen benötigt.
Da ich deinen Code nicht kenne, hier ein paar mögliche Fehlerquellen:
Falls du BigInteger nutzt, solltest du mit ".equals" vergleichen, "==" liefert nicht die hier erwünschten Ergebnisse.
Falls dein Algorithmus die Eingangsparameter verändert (das war glaube ich beim erweiterten Euklid so), sollte man diese zuerst in neue Variablen kopieren und damit arbeiten, sonst ist der Algorithmus fehlerhaft, sobald es mehr als einen Iterationsschritt gibt.

mrzb6
Mausschubser
Mausschubser
Beiträge: 54
Registriert: 4. Okt 2010 21:50
Wohnort: Darmstadt

Re: HÜ A1

Beitrag von mrzb6 »

Ein Fehler, der mir untergekommen war, war zu vergessen, dass BigInteger immutable ist. ...soll heißen, Subtraktionen auf den BigIntegers müssen z.B. als p = p-1 geschrieben werden.

x539
Windoof-User
Windoof-User
Beiträge: 30
Registriert: 24. Nov 2010 15:52

Re: HÜ A1

Beitrag von x539 »

Test mal ob
\(ed \equiv 1 (mod \varphi(N))\)
und
\(d \gt 0\)

Tipp: assert() wird in Java standardmäßig nicht ausgewertet.
„Reality is that which, when you stop believing in it, doesn't go away.“ Philip K. Dick

Antworten

Zurück zu „Archiv“