HNY-Programmieraufgabe

[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]

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

[Ranco]

Ach ja richtig, hatte da was verwechselt.

Danke

[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?

[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.

[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

[plane]

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

[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..