Ex 08 Homework (NTRU)

Moderator: Post Quantum Cryptography

Benutzeravatar
\Hannes
Mausschubser
Mausschubser
Beiträge: 57
Registriert: 18. Nov 2005 17:24

Ex 08 Homework (NTRU)

Beitrag von \Hannes » 15. Dez 2009 18:22

Heidiho.
Ich habe mal versucht, die Enc-/Decryption nachzurechnen und bin dabei auf folgendes Problem gestoßen:

1. Wozu wird \(f_q\) benutzt?

2. Müsste es nicht \(h := pf_q * g \, \mbox{mod} \, q\) heißen (\(f_q\) statt \(f_p\)), was auch Frage 1 erklären würde? Sonst kommt man auch, wenn man sich in a) die Decryption (nicht die Encryption, wie in a) steht) zusammenbaut, nicht auf das gewünschte für \(f*e\)..? Was mich allerdings direkt zu folgendem führt:

3. In \(h\) steckt eine Multiplikation mit \(p\). Wir nehmen später das \(b \, \mbox{mod} \, q\), wo \(h\) drinsteckt. Ist es damit nicht ab diesem Schritt völlig irrelevant, was genau in \(h\) (ausser der Multiplikation mit \(p\) natürlich) steht? Ich sehe irgendwie nicht richtig den Nutzen von diesem \(h\). Damit passiert doch quasi nix spannendes, es wird für die Ciphertextberechnung mit dem zufällig gewählten \(r\) gefaltet, aber wegen der angesprochenen Multiplikation mit \(p\) und anschließendem modulo, fällt das doch aus der eigentlichen Berechnung genauso raus wie \(r\). Dass man \(r\) braucht, sehe ich durchaus ein (Störfaktor), genauso, dass es später rausfällt, unabhängig davon was es eigentlich war aber wozu das \(h\) so kompliziert machen? Soll das einfach nur den Störfaktor \(r\) in der Verschlüsselung noch verbessern?
(Die gemeine Antwort wäre jetzt natürlich, dass es wirklich wurst ist was in \(h\) steht, und deshalb auch das \(f_p\) nicht stört, aber dann kommt man immerhin immer noch nicht auf das in der a) angegebene \(f*e\) :mrgreen:)

4. Es müsste \(c\) modulo \(p\) (statt \(q\)) genommen werden, right? Wir wollen da doch \(f_p * f \equiv 1 \, \mbox{mod} \, p\) ausnutzen..? Sonst kommt man da doch auch nicht auf \(m\) (und das mod \(p\) wäre auch konsistent mit der Abbildung von \(m\) in \(R\) mit Koeffizienten zwischen \(-\frac{p}{2}\) und \(\frac{p}{2}\)).

(Wieso kann man hier \mod oder so nicht mehr benutzen? :/)
Schwabbeldiwapp hier kommt die Grütze.

Benutzeravatar
Patr0rc
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 260
Registriert: 8. Feb 2008 11:43

Re: Ex 08 Homework (NTRU)

Beitrag von Patr0rc » 15. Dez 2009 18:48

Hallo an alle.
Zu Hannes' Fragen ein paar Korrekturen auf dem Übungsblatt:
Zu 2.: Da hast du vollkommen Recht. Es muss hier \(h=p\cdot f_q*g \text{ mod } q\) heißen.
Zu 3.: Das angegebene c ist auch falsch. Es muss modulo p gerechnet werden, nicht modulo q.

Vielleicht erübrigen sich deine Fragen damit ja schon. Wenn nicht, können sich gerne alle anderen an dieser Diskussion beteiligen...

Eine neue Version des Übungsblatts ist online.

Benutzeravatar
\Hannes
Mausschubser
Mausschubser
Beiträge: 57
Registriert: 18. Nov 2005 17:24

Re: Ex 08 Homework (NTRU)

Beitrag von \Hannes » 15. Dez 2009 19:19

Danke schonmal für die suuuperschnelle Antwort. Ich würde hier gern nochmal Frage 3 nochmal konkretisieren:

Ich bin mittlerweile zu der Erkenntnis gekommen, dass das \(h\) ein in der Tat essentieller Teil des PKs ist (ist ja auch irgendwo relativ klar ersichtlich), und zwar insofern, als dass das \(h\) quasi der individuelle, 'geheim' gestaltete Teil des Public Keys ist. Wäre das \(h\) nicht existent, respektive trivial-dämlich gewählt, so könnte man sich zu jedem PK \((n,p,q)\) Polynome \(f,f_p\) erstellen, die \(f*f_p \equiv 1 \, \mbox{mod} \, p\) erfüllen und damit jeglichen Ciphertext für diesen PK entschlüsseln. Also muss das \(h\) eben jenes verhindern (klingt auch sinnvoll, da in dem \(h\) eben 'geheime' bzw. individuelle Informationen, nämlich \(g,p_q\) stecken).
Die Frage ist nur: Wie. :) Die Tatsache, dass jegliche Beteiligung von \(h\) in der Entschlüsselung ab dem Berechnen von \(b\) durch das modulo \(p\) entfernt ist, bleibt ja weiterhin bestehen. Jemand 'ne Idee? :)
Schwabbeldiwapp hier kommt die Grütze.

Benutzeravatar
blowfish
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 241
Registriert: 18. Okt 2006 16:00

Re: Ex 08 Homework (NTRU)

Beitrag von blowfish » 10. Jan 2010 20:06

hi,
ich hab mich grad auch mal mit dem ntru-scheme beschäftigt. ich hab zwar keine antwort auf deine frage, aber selber eine, welche ich dann hier mal dranhänge:
was spricht eigentlich dagegen, e direkt mod p zu reduzieren und daraus m zu erhalten?

/EDIT: nach weiterem nachdenken glaube ich, das wird wohl durch das mod\(q\) vermieden. ich erkläre mir den aufbau von \(h\) folgendermaßen: \(h\) ist ja dazu da, in den term \(r*h\) ein vielfaches von \(p\) reinzubringen, was man später "rausreduzieren" kann, um dann \(m\) zu erhalten. dazu würde aber prinzipiell \(h=3*k\) für irgendein \(k\) reichen. allerdings muss man ja dafür sorgen, dass nicht jeder das \(e\) zu \(m\) mittels \(p\) reduzieren kann. dazu ist das \(f_q\), denke ich, denn es sorgt dafür, dass \((r*h+m)\) größer als \(q\) ist und nur, wer \(f\) kennt, kann das \(f_q\) eliminieren und \(p r*g + f*m\) ist dann ja kleiner als \(q\). also kann man mittels mod\(p\) sich da des ersten summanden entledigen. das \(g\) ist nun dazu da, das geheime \(f_q\) zu verstecken, sonst könnte man sich leicht aus \(h\) den geheimen schlüssel berechnen.
macht das alles irgendwie sinn?
Ein Hemd ist Einstellungssache!

Benutzeravatar
\Hannes
Mausschubser
Mausschubser
Beiträge: 57
Registriert: 18. Nov 2005 17:24

Re: Ex 08 Homework (NTRU)

Beitrag von \Hannes » 11. Jan 2010 18:36

Yo, nach einigem Nachfragen in der Übung war ich auch bei sowas in der Art angekommen.
Schwabbeldiwapp hier kommt die Grütze.

Antworten

Zurück zu „Post-Quantum Cryptography“