McEliece-Kryptosystem Beispieldurchlauf: Unterschied zwischen den Versionen
Kowa (Diskussion | Beiträge) |
Kowa (Diskussion | Beiträge) Keine Bearbeitungszusammenfassung |
||
Zeile 1: | Zeile 1: | ||
=Beispieldurchlauf für das [[McEliece-Kryptosystem]]= | {{Qualität | ||
|correctness =1 | |||
|extent = 4 | |||
|numberOfReferences = 5 | |||
|qualityOfReferences = 4 | |||
|conformance = 4 | |||
}} | |||
==Beispieldurchlauf für das [[McEliece-Kryptosystem]]== | |||
Nachfolgend soll ein Bespiel für ein sehr kleines <math>(n,k,d)=(7,4,3)</math> [[McEliece-Kryptosystem]] durchgerechnet werden. Dieses Beispiel baut auf dem in [St95] auf. | Nachfolgend soll ein Bespiel für ein sehr kleines <math>(n,k,d)=(7,4,3)</math> [[McEliece-Kryptosystem]] durchgerechnet werden. Dieses Beispiel baut auf dem in [St95] auf. | ||
==Systemparameter== | ===Systemparameter=== | ||
Die Systemparameter wurden mit <math>n=7</math>, <math>k=4</math> und <math>d=3</math> festgelegt. Damit werden 4 Klartext-Bit auf 7 Chiffre-Bit abgebildet. Weiter braucht der verwendete Code einen Hamming-Abstand von 3. Damit lassen sich <math>t=(d-1)/2=1</math> Bitfehler korrigieren. | Die Systemparameter wurden mit <math>n=7</math>, <math>k=4</math> und <math>d=3</math> festgelegt. Damit werden 4 Klartext-Bit auf 7 Chiffre-Bit abgebildet. Weiter braucht der verwendete Code einen Hamming-Abstand von 3. Damit lassen sich <math>t=(d-1)/2=1</math> Bitfehler korrigieren. | ||
==Schlüssel-Erzeugung== | ===Schlüssel-Erzeugung=== | ||
Um das nachfolgende Beispiel einfacher zu halten, erzeugt die Generator-Matrix <math>G</math> keinen Goppa-Code sondern einen Hamming-Code: | Um das nachfolgende Beispiel einfacher zu halten, erzeugt die Generator-Matrix <math>G</math> keinen Goppa-Code sondern einen Hamming-Code: | ||
Zeile 33: | Zeile 41: | ||
:<math>K_{pub}=(\hat{G},t)=\left(\begin{pmatrix} 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 & 1 & 0 \end{pmatrix},1\right)</math> | :<math>K_{pub}=(\hat{G},t)=\left(\begin{pmatrix} 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 & 1 & 0 \end{pmatrix},1\right)</math> | ||
==Verschlüsselung== | ===Verschlüsselung=== | ||
Alice möchte ihre Nachricht <math>m=\begin{pmatrix} 1 & 1 & 0 & 1 \end{pmatrix}</math> nun verschlüsseln. Dazu muß noch ein beliebiger Fehlervektor <math>z</math> mit dem maximalen Gewicht <math>t=1</math> und der Länge <math>n=7</math> gewählt werden. In diesem Durchlauf soll <math>z=\begin{pmatrix} 0 & 0 & 0 & 0 & 1 & 0 & 0 \end{pmatrix}</math> sein. Die Chiffre <math>c</math> berechnet sich nun mit | Alice möchte ihre Nachricht <math>m=\begin{pmatrix} 1 & 1 & 0 & 1 \end{pmatrix}</math> nun verschlüsseln. Dazu muß noch ein beliebiger Fehlervektor <math>z</math> mit dem maximalen Gewicht <math>t=1</math> und der Länge <math>n=7</math> gewählt werden. In diesem Durchlauf soll <math>z=\begin{pmatrix} 0 & 0 & 0 & 0 & 1 & 0 & 0 \end{pmatrix}</math> sein. Die Chiffre <math>c</math> berechnet sich nun mit | ||
Zeile 44: | Zeile 52: | ||
:<math>=\begin{pmatrix} 0 & 1 & 1 & 0 & 1 & 1 & 0 \end{pmatrix}=c</math> | :<math>=\begin{pmatrix} 0 & 1 & 1 & 0 & 1 & 1 & 0 \end{pmatrix}=c</math> | ||
==Entschlüsselung== | ===Entschlüsselung=== | ||
Nach dem Empfang der Chiffre muß Bob zuerst die Permutation rückgängig machen: | Nach dem Empfang der Chiffre muß Bob zuerst die Permutation rückgängig machen: | ||
Zeile 63: | Zeile 71: | ||
Damit wurde Alice’s Klartext <math>\begin{pmatrix} 1 & 1 & 0 & 1 \end{pmatrix}</math> erfolgreich wiederhergestellt. | Damit wurde Alice’s Klartext <math>\begin{pmatrix} 1 & 1 & 0 & 1 \end{pmatrix}</math> erfolgreich wiederhergestellt. | ||
=Quellen= | ==Quellen== | ||
* [[McEliece-Kryptosystem]] | * [[McEliece-Kryptosystem]] | ||
* [St95] Douglas Stinson, Cryptography. Theory and Practice, CRC Press, 1995, ISBN: 0-84938-521-0, Seite 193 ff. | * [St95] Douglas Stinson, Cryptography. Theory and Practice, CRC Press, 1995, ISBN: 0-84938-521-0, Seite 193 ff. | ||
Zeile 73: | Zeile 81: | ||
[[Kategorie:Kryptographie]] | [[Kategorie:Kryptographie]] | ||
[[Kategorie:Beispiel]] | [[Kategorie:Beispiel]] | ||
Aktuelle Version vom 20. Mai 2019, 12:31 Uhr
Dieser Artikel erfüllt die GlossarWiki-Qualitätsanforderungen nur teilweise:
Korrektheit: 1 (nur rudimäntär überprüft) |
Umfang: 4 (unwichtige Fakten fehlen) |
Quellenangaben: 5 (vollständig vorhanden) |
Quellenarten: 4 (sehr gut) |
Konformität: 4 (sehr gut) |
Beispieldurchlauf für das McEliece-Kryptosystem
Nachfolgend soll ein Bespiel für ein sehr kleines $ (n,k,d)=(7,4,3) $ McEliece-Kryptosystem durchgerechnet werden. Dieses Beispiel baut auf dem in [St95] auf.
Systemparameter
Die Systemparameter wurden mit $ n=7 $, $ k=4 $ und $ d=3 $ festgelegt. Damit werden 4 Klartext-Bit auf 7 Chiffre-Bit abgebildet. Weiter braucht der verwendete Code einen Hamming-Abstand von 3. Damit lassen sich $ t=(d-1)/2=1 $ Bitfehler korrigieren.
Schlüssel-Erzeugung
Um das nachfolgende Beispiel einfacher zu halten, erzeugt die Generator-Matrix $ G $ keinen Goppa-Code sondern einen Hamming-Code:
- $ G=\begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{pmatrix} $
Hier sieht man, daß $ d=3 $ gilt, denn jede Zeile unterscheidet sich in mindesten 3 Werten voneinander.
Bob erzeugt weiter die zufälligen Matrizen $ S $ und $ P $:
- $ S=\begin{pmatrix} 1 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 \end{pmatrix} $
- $ P=\begin{pmatrix} 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 \end{pmatrix} $
Der erste Teil $ \hat{G} $ des öffentlichen Schlüssels berechnet sich wie folgt:
- $ \hat{G}=SGP $
- $ \hat{G}=\begin{pmatrix} 1 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 \end{pmatrix} \cdot \begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{pmatrix} \cdot \begin{pmatrix} 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 \end{pmatrix}= $
- $ =\begin{pmatrix} 1 & 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 & 0 & 1 & 1 \end{pmatrix} \cdot \begin{pmatrix} 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 \end{pmatrix}= $
- $ =\begin{pmatrix} 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 & 1 & 0 \end{pmatrix}=\hat{G} $
Bob’s öffentlicher Schlüssel lautet nun:
- $ K_{pub}=(\hat{G},t)=\left(\begin{pmatrix} 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 & 1 & 0 \end{pmatrix},1\right) $
Verschlüsselung
Alice möchte ihre Nachricht $ m=\begin{pmatrix} 1 & 1 & 0 & 1 \end{pmatrix} $ nun verschlüsseln. Dazu muß noch ein beliebiger Fehlervektor $ z $ mit dem maximalen Gewicht $ t=1 $ und der Länge $ n=7 $ gewählt werden. In diesem Durchlauf soll $ z=\begin{pmatrix} 0 & 0 & 0 & 0 & 1 & 0 & 0 \end{pmatrix} $ sein. Die Chiffre $ c $ berechnet sich nun mit
- $ e_K(m,z)=c=m\hat{G}+z $
- $ m=\begin{pmatrix} 1 & 1 & 0 & 1 \end{pmatrix} \cdot \begin{pmatrix} 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 & 1 & 0 \end{pmatrix} + \begin{pmatrix} 0 & 0 & 0 & 0 & 1 & 0 & 0 \end{pmatrix}= $
- $ =\begin{pmatrix} 0 & 1 & 1 & 0 & 0 & 1 & 0 \end{pmatrix} + \begin{pmatrix} 0 & 0 & 0 & 0 & 1 & 0 & 0 \end{pmatrix}= $
- $ =\begin{pmatrix} 0 & 1 & 1 & 0 & 1 & 1 & 0 \end{pmatrix}=c $
Entschlüsselung
Nach dem Empfang der Chiffre muß Bob zuerst die Permutation rückgängig machen:
- $ \hat{c}=cP^{-1}= $
- $ =\begin{pmatrix} 0 & 1 & 1 & 0 & 1 & 1 & 0 \end{pmatrix} \cdot \begin{pmatrix} 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \end{pmatrix}= $
- $ =\begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 1 \end{pmatrix} $
Anschließend wird der Hamming-Code dekodiert. Dazu wird für jede Zeile der Generator-Matrix $ G $ der Hamming-Abstand $ d $ berechnet. Von der ersten zur vierten Zeile beträgt der Abstand $ \begin{pmatrix} 1 & 3 & 3 & 2 \end{pmatrix} $. Damit ist der dekodierte Code $ \hat{m}=\begin{pmatrix} 1 & 0 & 0 & 0 \end{pmatrix} $. Zuletzt wird der Klartext $ m $ berechnet:
- $ m=\hat{m}S^{-1}= $
- $ =\begin{pmatrix} 1 & 0 & 0 & 0 \end{pmatrix} \cdot \begin{pmatrix} 1 & 1 & 0 & 1 \\ 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 \end{pmatrix}= $
- $ =\begin{pmatrix} 1 & 1 & 0 & 1 \end{pmatrix} $
Damit wurde Alice’s Klartext $ \begin{pmatrix} 1 & 1 & 0 & 1 \end{pmatrix} $ erfolgreich wiederhergestellt.
Quellen
- McEliece-Kryptosystem
- [St95] Douglas Stinson, Cryptography. Theory and Practice, CRC Press, 1995, ISBN: 0-84938-521-0, Seite 193 ff.
- [Sch96] Bruce Schneier, Applied Cryptography, Protocols, Algorithms and Source Code in C, 2nd ed., John Wiley & Sons Inc., 1996, ISBN: 0-471-12845-7, Seite 479 ff.
- [WiME05] Wikipedia, McEliece Cryptosystem, Wikipedia, The Free Encyclopedia, 23. Dec. 2005 10:39 UTC, http://en.wikipedia.org/w/index.php?title=McEliece_cryptosystem&oldid=32471204
- [En06] ENTROPY, McEliece, Error-correcting Codes als Public Key Verfahren, 01.04.2006, http://entropy.stop1984.com/de/mceliece.html
- [MOV96] Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, Handbook of Applied Cryptography, CRC Press Inc., 1996, ISBN: 0849385237