Ex. 10, Homework, Teil c

Moderator: Post Quantum Cryptography

defolt
Neuling
Neuling
Beiträge: 6
Registriert: 8. Jan 2006 16:36

Ex. 10, Homework, Teil c

Beitrag von defolt » 20. Jan 2010 12:51

Hi!
Für Teil c der 10 HÜ (Version vom 18.01) steht im Skript:
It is hard to find x for given H, s and wt(x) (this is known as NP-complete).
Ich habe mit Pari für alle \(\small{\begin{pmatrix} 10 \\ 6 \end{pmatrix}}\) Wörter aus \(x~\in~\mathbb{F}_{2}^{10}\) mit wt(x)=6 ausprobiert, ob sie zu dem angegebenen syndrome passen (mit der Gleichung \(s = Hx^T\)).

Raus kamen 4 Wörter, die jedoch alle nicht in der vom Generator erzeugten Code-Menge liegen. Mein H sollte stimmen, denn \(GH^{T}\equiv~0~(\text{mod}~2)\) ist erfüllt.

Gibt es nur ein Wort oder mehrere Wörter als Lösung und ist das überhaupt der richtige Ansatz?

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

Re: Ex. 10, Homework, Teil c

Beitrag von Patr0rc » 20. Jan 2010 13:42

Da die Matrix H linear abhängige Spalten haben wird, gibt es nicht nur eine Möglichkeit, oder...?!
Es ist dir überlassen, ob du ein Wort angibst, was dies erfüllt, oder mehrere/alle. (Ein Teil dieser Aufgabe besteht/bestand auch darin, das zu sehen, was dir aufgefallen ist.)

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

Re: Ex. 10, Homework, Teil c

Beitrag von blowfish » 20. Jan 2010 16:43

defolt hat geschrieben:...
Raus kamen 4 Wörter, die jedoch alle nicht in der vom Generator erzeugten Code-Menge liegen.
...
können sie ja auch nicht, sonst wäre das entsprechende syndrom ja nicht s sondern 0, glaub ich.
Ein Hemd ist Einstellungssache!

Antworten

Zurück zu „Post-Quantum Cryptography“