13. Übungsblatt

Benutzeravatar
bruse
Kernelcompilierer
Kernelcompilierer
Beiträge: 412
Registriert: 2. Aug 2006 22:42

Re: 13. Übungsblatt

Beitrag von bruse »

Ja. Generell ist dieser Hinweis nicht nötig, aber er verkürzt die Sache etwas. Falls du dir den Algorithmus im Buch anschaust, ist n die Gruppenordnung (deren Größe du ja einfach bestimmen kannst). In der von dir zitierten Klausur (btw aus 2006) wird zusätzlich als HIlfestellung gegeben, dass die von 28 generierte Gruppe nur 13 Elemente umfasst. Da 28^x definitiv in dieser Gruppe liegt, kann man sich auf die Untersuchung von weniger Elementen beschränken, d.h. m kleiner wählen, weniger Babysteps machen etc. Man kann den DL aber halt auch bestimmen (und das ist der Normalfall), wenn man die Elementordnung nicht kennt, wie zB in der Übungsaufgabe. Du hast dir mal wieder zielstrebig einen Spezialfall ausgesucht.
Un hombre de frente a una ventana
Súper lúcida la mirada
Recorre el paisaje y no,
no es su interior, es luna.

Benutzeravatar
oren78
BSc Spammer
BSc Spammer
Beiträge: 1373
Registriert: 17. Nov 2006 17:47
Wohnort: Darmstadt

Re: 13. Übungsblatt

Beitrag von oren78 »

bruse hat geschrieben: Du hast dir mal wieder zielstrebig einen Spezialfall ausgesucht.
so bin ich nunmal, detailverliebt halt ;-)

also nochmal zum mitschreiben, der hinweis verkürzt die laufschritte des Algos, ansonsten wenn dieser nicht gegeben ist, nehme ich einfach die abgerundete wurzel aus der gruppenordnung und thats it, right ??
"Unter allen menschlichen Entdeckungen sollte die Entdeckung der Fehler die wichtigste sein.", Stanisław Jerzy Lec

ZERG
Mausschubser
Mausschubser
Beiträge: 59
Registriert: 19. Apr 2005 16:37

Re: 13. Übungsblatt

Beitrag von ZERG »

ob die verkürzung von 8 auf 5 schritte so viel mehr bringt ist fraglich.... aber gut

erik.tews
Computerversteher
Computerversteher
Beiträge: 326
Registriert: 5. Jan 2004 20:48

Re: 13. Übungsblatt

Beitrag von erik.tews »

Bei DSA tritt genau dieser Spezialfall auf, die Elemente von denen man dort die Logarithmen als Angreifer berechnen will liegen in einer merklich kleineren Untergruppe.

Benutzeravatar
oren78
BSc Spammer
BSc Spammer
Beiträge: 1373
Registriert: 17. Nov 2006 17:47
Wohnort: Darmstadt

Re: 13. Übungsblatt

Beitrag von oren78 »

ZERG hat geschrieben:ob die verkürzung von 8 auf 5 schritte so viel mehr bringt ist fraglich.... aber gut
noch was, das m durch die Elementordnung ist NICHT zwingnd = m durch die bestimmung der wurzel(gruppenordnung)

konkret bedeutet das du erhälst FALSCHE werte für dein q da ja die Giant Steps Paare vom m abhängig sind !

rechne die gepostete aufgabe selbst nach, einmal mit dem gegebenen n = 13 und einmal mit der gruppenordnung(53) = 52 --> aufrunden(wurzel(52)) = 7
q würde mit dem zweiteren 3 ergeben, mit dem ersteren widerum wäre q = 2 !


auszug von Pari (m ist hier = 7)

Code: Alles auswählen

(14:24) gp > for(i = 0, 6, print( Mod(16*36^(i), 53) ))
Mod(16, 53)
Mod(46, 53)
Mod(13, 53)
Mod(44, 53)
Mod(47, 53)
Mod(49, 53)
Mod(15, 53)
(14:24) gp > for(i = 0, 6, print( Mod(28^(i*7), 53) ))
Mod(1, 53)
Mod(44, 53)
Mod(28, 53)
Mod(13, 53)
Mod(42, 53)
Mod(46, 53)
Mod(10, 53)
"Unter allen menschlichen Entdeckungen sollte die Entdeckung der Fehler die wichtigste sein.", Stanisław Jerzy Lec

Commander
Neuling
Neuling
Beiträge: 10
Registriert: 11. Mai 2005 17:37

Re: 13. Übungsblatt

Beitrag von Commander »

Hi, ich hab nochmal ne andere Frage zur Aufgabe G3. Und zwar muss man ja dann 3^43 mod 1823 berechnen. Wie macht ihr das? Selbst mit schneller Exponentation kommen bei mir da noch Werte raus (3^32) raus, aus denen ich mit Hilfe meines Taschenrechnes keine Reste mod 1823 bestimmen kann...das selbe Problem hab ich logischer Weise auch noch an anderen Stellen - stehe ich da irgendwie auf dem Schlauch oder ist das nur mit Hilfe des Rechners zu lösen?

erik.tews
Computerversteher
Computerversteher
Beiträge: 326
Registriert: 5. Jan 2004 20:48

Re: 13. Übungsblatt

Beitrag von erik.tews »

Es gilt gcd(a,b) = gcd(a mod b, b), damit kann man früher reduzieren.

ZERG
Mausschubser
Mausschubser
Beiträge: 59
Registriert: 19. Apr 2005 16:37

Re: 13. Übungsblatt

Beitrag von ZERG »

oder mit http://www.saar.de/~awa/03_Rechnen_Zn.htm ausrechnen.... was in der klausur natürlich nicht hilf - aber ich hoffe mal einfach, dass solche zahlen nicht drankommen...


SOOOOOOOOO

und jetzt du dir oren....

28^x=16 mod 53
m=AUFRUNDEN(sqr(n)) = 8

g^-1 = 36

r | a* g^-r mod 53
--------------
0 | 16
1 | 46
2 | 13


g^m = 28^8 mod 53
= 13
-> q | g^m *q
---------------
1 | 13

damit ist: q=r gefunden mit der 13 und du hast q=1 und r=2
x=m*q + r
= 8*1 +2
ergibt nach adam riese 10

aufgabe gelöst

Benutzeravatar
Tristan
Windoof-User
Windoof-User
Beiträge: 29
Registriert: 22. Okt 2008 20:32

Re: 13. Übungsblatt

Beitrag von Tristan »

ergibt nach adam riese 10
Der Mann hieß Adam Ries!

Benutzeravatar
bruse
Kernelcompilierer
Kernelcompilierer
Beiträge: 412
Registriert: 2. Aug 2006 22:42

Re: 13. Übungsblatt

Beitrag von bruse »

Tristan hat geschrieben:
ergibt nach adam riese 10
Der Mann hieß Adam Ries!
Ist das auch klausurrelevant?

SCNR
Un hombre de frente a una ventana
Súper lúcida la mirada
Recorre el paisaje y no,
no es su interior, es luna.

Benutzeravatar
oren78
BSc Spammer
BSc Spammer
Beiträge: 1373
Registriert: 17. Nov 2006 17:47
Wohnort: Darmstadt

Re: 13. Übungsblatt

Beitrag von oren78 »

ZERG hat geschrieben: SOOOOOOOOO

und jetzt du dir oren....
ohoo...gleich auf die bedrohliche art oder wie...? das sind mir die liebsten 8)
"Unter allen menschlichen Entdeckungen sollte die Entdeckung der Fehler die wichtigste sein.", Stanisław Jerzy Lec

Xelord
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 225
Registriert: 23. Okt 2004 09:49

Re: 13. Übungsblatt

Beitrag von Xelord »

Das wollte ich die Tage schonmal schreiben: STREITET EUCH ! ;)

jno
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 144
Registriert: 18. Mai 2007 09:41

Re: 13. Übungsblatt

Beitrag von jno »

Zur G2: Ich seh doch richtig, dass die angegebene Lösung zur DSA-Fälschung genau die Gleiche ist, wie die für El Gamal-Signaturen im Buch angegeben ist oder nicht? Hätte jetzt mal spontan gesagt, dass da schon irgendwas anders sein sollte, vielleicht dass man hier dann auch stattdessen modulo q rechnet oder so... Oder wo liegt sonst der didaktische Nährwert?

EDIT: Bei der Lösung zur G3 müsste es imo \(m=\lceil \sqrt{1822} \rceil\) statt \(m=\lceil \sqrt{1823}\rceil\) heißen, was aber ja zum Glück das Gleiche ist.

Antworten

Zurück zu „Archiv“