HNY-Programmieraufgabe

Moderator: Einführung in die Kryptographie

Ranco
Erstie
Erstie
Beiträge: 22
Registriert: 27. Feb 2007 11:13

HNY-Programmieraufgabe

Beitrag von Ranco »

Habe ein Problem mit den Funktionen encode und decode.
Wenn ich b = 11 zu p = 23 codiere, kommt 6 raus:
\(11^2 \equiv 6 \bmod 23\)
wenn ich das aber wieder decodiere, kommt bei mir 12 raus, nicht 11:
\(6^{(23 + 1)/4} \equiv 12 \bmod 23\)

Findet jemand den Fehler?

Osterlaus
BSc Spammer
BSc Spammer
Beiträge: 1263
Registriert: 23. Aug 2007 12:46
Wohnort: DA

Re: HNY-Programmieraufgabe

Beitrag von Osterlaus »

Überleg mal, was 12 + 11 ist und lies dir den Hinweis auf die Zahlentheorie (im Hinblick auf zwei Wurzeln) durch.

Ranco
Erstie
Erstie
Beiträge: 22
Registriert: 27. Feb 2007 11:13

Re: HNY-Programmieraufgabe

Beitrag von Ranco »

Ach ja richtig, hatte da was verwechselt.

Danke :-)

Benutzeravatar
Demmi
Kernelcompilierer
Kernelcompilierer
Beiträge: 423
Registriert: 1. Okt 2007 12:56
Wohnort: Darmstadt

Re: HNY-Programmieraufgabe

Beitrag von Demmi »

Nochwas anderes: Im Skriptteil 8 auf Seite 21 wird vor dem Quadrieren noch m+1 gerechnet. Analog müsste man nach dem Wurzelziehen wieder -1 rechnen.
Mir ist nicht ganz klar wieso das im Skript überhaupt gemacht wird. m liegt nicht mehr zwischen 0 und Q-1, sondern halt zwischen 1 und Q, aber wieso?
Außerdem hat das ja eine Auswirkung auf das Decode der gegeben Werte für c1,c2 und x. Das Ergebnis wäre dann logischerweise eins kleiner, wenn man noch -1 rechnen würde.

Meine Fragen also:
Sollen wir das +/-1 in der HNY-Aufgabe bewusst weglassen?
Wieso macht man das überhaupt?
Saying that Java is nice because it works on all Plattforms is like saying that anal sex is nice because it works on all genders.

vinzenz
Neuling
Neuling
Beiträge: 9
Registriert: 22. Okt 2009 00:35

Re: HNY-Programmieraufgabe

Beitrag von vinzenz »

wegen der 0, die gehört nämlich laut definition (teil 7, seite 24) nicht zu \(Z_n^*\) und auch nicht zu den quadratischen resten modulo p (QR(p) siehe aufgabenblatt hny). einfach 1 addieren, und die 0 kann nicht mehr vorkommen und macht auch keine probleme. dann muss man eben auch am ende wieder 1 abziehen.

Benutzeravatar
Demmi
Kernelcompilierer
Kernelcompilierer
Beiträge: 423
Registriert: 1. Okt 2007 12:56
Wohnort: Darmstadt

Re: HNY-Programmieraufgabe

Beitrag von Demmi »

Wenn man beim Decode aber noch -1 rechnet, macht das Ergenis der Entschlüsselung der gegeben Werte aber irgendwie weniger Sinn, als wenn man nur die Wurzel zieht, finde ich. Ich weiß halt nicht, ob das vom Veranstalter wirlich so gedacht war ;)
Saying that Java is nice because it works on all Plattforms is like saying that anal sex is nice because it works on all genders.

Benutzeravatar
plane
Computerversteher
Computerversteher
Beiträge: 337
Registriert: 21. Okt 2005 00:18

Re: HNY-Programmieraufgabe

Beitrag von plane »

Genau das denke ich auch! Ohne -1 wäre das ganze sinnvoller...vielleicht kann jemand offizielles dazu nochmal was posten...

poetter
Windoof-User
Windoof-User
Beiträge: 34
Registriert: 22. Sep 2009 16:20

Re: HNY-Programmieraufgabe

Beitrag von poetter »

Das auf seite 21 beschriebene en/decodingverfahren besteht aus zwei teilen:
(1) Darstellen eines Strings aus {0,1}^(l-1) als element aus {1...q}
(2) Abbilden eines elements aus {1...q} nach QR(p).
Beide abbildungen muessen natuerlich injektiv sein, sonst kann nicht dekodiert werden.

Um (1) zu implementieren werden zunächst aus einem string die einzelnen bits herausgetrennt
und daraus eine zahl aus 0...q-1 zusammengebaut. Anschliessende addition von 1 ergibt die
gewuenschte zahl aus 1...q

Um (2) zu implementieren wird einfach modulo p quadriert. Invertiert wird diese operation durch
wurzelziehen, wie beschrieben. Das mit dem quadrieren/wurzelziehen funktioniert aber nur fuer elemente
aus Zp*, deshalb darf die eingabemenge eben keine 0 enthalten!

Nun zur weihnachtsaufgabe: Der teil (1) wurde bewusst weggelassen, weil er (a) nichts mit kryptographie
zu tun hat, und (b) kompliziert zu spezifizieren gewesen wäre (stringdarstellung als ascii?, MSB vorne/hinten?
was passiert, wenn l-1 nicht durch 8 teilbar ist, usw). Zu programmieren ist nur teil (2), also die abbildungen
{1...q} <-> QR(p).

Kürzere Antwort auf deine frage: ja, lass das +/- 1 weg und verzichte ebenso auf die darstellung von m als
binärstring. Wenn du teil (2) korrekt implementiert hast, wirst du eh erkennen, ob von dem (zwischen-)ergebnis
wohl noch 1 addiert oder abgezogen werden sollte..

Antworten

Zurück zu „Einführung in die Kryptographie“