McEliece-Kryptosystem Beispieldurchlauf - Versionsgeschichte

Kowa am 20. Mai 2019 um 11:31 Uhr

2019-05-20T11:31:47Z

← Nächstältere Version		Version vom 20. Mai 2019, 11:31 Uhr
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]]
	~~{{{{SITENAME}}-konformer Artikel}}~~
	~~{{Quellenangaben verbessern~~
	~~\| Formatierung = true~~
	}}

Kowa: /* Quellen */

2007-01-03T16:12:40Z

Quellen

← Nächstältere Version		Version vom 3. Januar 2007, 16:12 Uhr
Zeile 72:		Zeile 72:

	[[Kategorie:Kryptographie]]		[[Kategorie:Kryptographie]]
			[[Kategorie:Beispiel]]
	{{{{SITENAME}}-konformer Artikel}}		{{{{SITENAME}}-konformer Artikel}}
	{{Quellenangaben verbessern		{{Quellenangaben verbessern
	\| Formatierung = true		\| Formatierung = true
	}}		}}

Kowa am 3. Januar 2007 um 12:32 Uhr

2007-01-03T12:32:48Z

← Nächstältere Version		Version vom 3. Januar 2007, 12:32 Uhr
Zeile 72:		Zeile 72:

	[[Kategorie:Kryptographie]]		[[Kategorie:Kryptographie]]
	{{{{SITENAME}}-konformer }}		{{{{SITENAME}}-konformer Artikel}}
	{{Quellenangaben verbessern		{{Quellenangaben verbessern
	\| Formatierung = true		\| Formatierung = true
	}}		}}

Kowa am 3. Januar 2007 um 12:32 Uhr

2007-01-03T12:32:19Z

← Nächstältere Version		Version vom 3. Januar 2007, 12:32 Uhr
Zeile 1:		Zeile 1:
	~~Dieser Artikel zeigt einen~~ Beispieldurchlauf für das[[McEliece-Kryptosystem]].		=Beispieldurchlauf für das [[McEliece-Kryptosystem]]=

	~~==Beispieldurchlauf==~~		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.
	~~Um einen Algorithmus besser verstehen zu können, hilft meist ein praktisches Beispiel.~~ 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==
Zeile 11:		Zeile 10:

	:<math>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}</math>		:<math>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}</math>


	Hier sieht man, daß <math>d=3</math> gilt, denn jede Zeile unterscheidet sich in mindesten 3 Werten voneinander.		Hier sieht man, daß <math>d=3</math> gilt, denn jede Zeile unterscheidet sich in mindesten 3 Werten voneinander.


	Bob erzeugt weiter die zufälligen Matrizen <math>S</math> und <math>P</math>:		Bob erzeugt weiter die zufälligen Matrizen <math>S</math> und <math>P</math>:

	:<math>S=\begin{pmatrix} 1 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 \end{pmatrix}</math>		:<math>S=\begin{pmatrix} 1 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 \end{pmatrix}</math>


	:<math>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}</math>		:<math>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}</math>


	Der erste Teil <math>\hat{G}</math> des öffentlichen Schlüssels berechnet sich wie folgt:		Der erste Teil <math>\hat{G}</math> des öffentlichen Schlüssels berechnet sich wie folgt:

	:<math>\hat{G}=SGP</math>		:<math>\hat{G}=SGP</math>


	:<math>\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}=</math>		:<math>\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}=</math>


	:<math>=\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}=</math>		:<math>=\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}=</math>


	:<math>=\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}</math>		:<math>=\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}</math>


	Bob’s öffentlicher Schlüssel lautet nun:		Bob’s öffentlicher Schlüssel lautet nun:

	:<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==
Zeile 47:		Zeile 37:

	:<math>e_K(m,z)=c=m\hat{G}+z</math>		:<math>e_K(m,z)=c=m\hat{G}+z</math>


	:<math>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}=</math>		:<math>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}=</math>


	:<math>=\begin{pmatrix} 0 & 1 & 1 & 0 & 0 & 1 & 0 \end{pmatrix} + \begin{pmatrix} 0 & 0 & 0 & 0 & 1 & 0 & 0 \end{pmatrix}=</math>		:<math>=\begin{pmatrix} 0 & 1 & 1 & 0 & 0 & 1 & 0 \end{pmatrix} + \begin{pmatrix} 0 & 0 & 0 & 0 & 1 & 0 & 0 \end{pmatrix}=</math>


	:<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==
Zeile 62:		Zeile 48:

	:<math>\hat{c}=cP^{-1}=</math>		:<math>\hat{c}=cP^{-1}=</math>


	:<math>=\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}=</math>		:<math>=\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}=</math>


	:<math>=\begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 1 \end{pmatrix}</math>		:<math>=\begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 1 \end{pmatrix}</math>


	Anschließend wird der Hamming-Code dekodiert. Dazu wird für jede Zeile der Generator-Matrix <math>G</math> der Hamming-Abstand <math>d</math> berechnet. Von der ersten zur vierten Zeile beträgt der Abstand <math>\begin{pmatrix} 1 & 3 & 3 & 2 \end{pmatrix}</math>. Damit ist der dekodierte Code <math>\hat{m}=\begin{pmatrix} 1 & 0 & 0 & 0 \end{pmatrix}</math>. Zuletzt wird der Klartext <math>m</math> berechnet:		Anschließend wird der Hamming-Code dekodiert. Dazu wird für jede Zeile der Generator-Matrix <math>G</math> der Hamming-Abstand <math>d</math> berechnet. Von der ersten zur vierten Zeile beträgt der Abstand <math>\begin{pmatrix} 1 & 3 & 3 & 2 \end{pmatrix}</math>. Damit ist der dekodierte Code <math>\hat{m}=\begin{pmatrix} 1 & 0 & 0 & 0 \end{pmatrix}</math>. Zuletzt wird der Klartext <math>m</math> berechnet:


	:<math>m=\hat{m}S^{-1}=</math>		:<math>m=\hat{m}S^{-1}=</math>


	:<math>=\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}=</math>		:<math>=\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}=</math>


	:<math>=\begin{pmatrix} 1 & 1 & 0 & 1 \end{pmatrix}</math>		:<math>=\begin{pmatrix} 1 & 1 & 0 & 1 \end{pmatrix}</math>


	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 94:		Zeile 72:

	[[Kategorie:Kryptographie]]		[[Kategorie:Kryptographie]]
			{{{{SITENAME}}-konformer }}
			{{Quellenangaben verbessern
			\| Formatierung = true
			}}

Chriss am 6. Juli 2006 um 21:46 Uhr

2006-07-06T21:46:52Z

← Nächstältere Version		Version vom 6. Juli 2006, 21:46 Uhr
Zeile 92:		Zeile 92:
	* [En06] ENTROPY, McEliece, Error-correcting Codes als Public Key Verfahren, 01.04.2006, http://entropy.stop1984.com/de/mceliece.html		* [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		* [MOV96] Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, Handbook of Applied Cryptography, CRC Press Inc., 1996, ISBN: 0849385237

			[[Kategorie:Kryptographie]]

Chriss am 6. Juli 2006 um 01:00 Uhr

2006-07-06T01:00:58Z

← Nächstältere Version		Version vom 6. Juli 2006, 01:00 Uhr
Zeile 2:		Zeile 2:

	==Beispieldurchlauf==		==Beispieldurchlauf==
	Um einen Algorithmus besser verstehen zu können, hilft meist ein praktisches Beispiel. Nachfolgend soll ein Bespiel für ein sehr kleines <math>(n,k,d)=(7,4,3)</math> Kryptosystem durchgerechnet werden. Dieses Beispiel baut auf dem in [St95] auf.		Um einen Algorithmus besser verstehen zu können, hilft meist ein praktisches Beispiel. 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==

Chriss am 6. Juli 2006 um 01:00 Uhr

2006-07-06T01:00:10Z

← Nächstältere Version		Version vom 6. Juli 2006, 01:00 Uhr
Zeile 83:		Zeile 83:

	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==

Chriss am 6. Juli 2006 um 00:59 Uhr

2006-07-06T00:59:32Z

← Nächstältere Version		Version vom 6. Juli 2006, 00:59 Uhr
Zeile 83:		Zeile 83:

	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==
			* [[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

Chriss am 6. Juli 2006 um 00:58 Uhr

2006-07-06T00:58:54Z

← Nächstältere Version		Version vom 6. Juli 2006, 00:58 Uhr
Zeile 41:		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==
			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

			:<math>e_K(m,z)=c=m\hat{G}+z</math>


			:<math>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}=</math>


			:<math>=\begin{pmatrix} 0 & 1 & 1 & 0 & 0 & 1 & 0 \end{pmatrix} + \begin{pmatrix} 0 & 0 & 0 & 0 & 1 & 0 & 0 \end{pmatrix}=</math>


			:<math>=\begin{pmatrix} 0 & 1 & 1 & 0 & 1 & 1 & 0 \end{pmatrix}=c</math>


			==Entschlüsselung==
			Nach dem Empfang der Chiffre muß Bob zuerst die Permutation rückgängig machen:

			:<math>\hat{c}=cP^{-1}=</math>


			:<math>=\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}=</math>


			:<math>=\begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 1 \end{pmatrix}</math>


			Anschließend wird der Hamming-Code dekodiert. Dazu wird für jede Zeile der Generator-Matrix <math>G</math> der Hamming-Abstand <math>d</math> berechnet. Von der ersten zur vierten Zeile beträgt der Abstand <math>\begin{pmatrix} 1 & 3 & 3 & 2 \end{pmatrix}</math>. Damit ist der dekodierte Code <math>\hat{m}=\begin{pmatrix} 1 & 0 & 0 & 0 \end{pmatrix}</math>. Zuletzt wird der Klartext <math>m</math> berechnet:


			:<math>m=\hat{m}S^{-1}=</math>


			:<math>=\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}=</math>


			:<math>=\begin{pmatrix} 1 & 1 & 0 & 1 \end{pmatrix}</math>


			Damit wurde Alice’s Klartext <math>\begin{pmatrix} 1 & 1 & 0 & 1 \end{pmatrix}</math> erfolgreich wiederhergestellt.

Chriss am 6. Juli 2006 um 00:41 Uhr

2006-07-06T00:41:40Z

Neue Seite

Dieser Artikel zeigt einen Beispieldurchlauf für das[[McEliece-Kryptosystem]].

==Beispieldurchlauf==
Um einen Algorithmus besser verstehen zu können, hilft meist ein praktisches Beispiel. Nachfolgend soll ein Bespiel für ein sehr kleines <math>(n,k,d)=(7,4,3)</math> Kryptosystem durchgerechnet werden. Dieses Beispiel baut auf dem in [St95] auf.

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

==Schlüssel-Erzeugung==
Um das nachfolgende Beispiel einfacher zu halten, erzeugt die Generator-Matrix <math>G</math> keinen Goppa-Code sondern einen Hamming-Code:

:<math>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}</math>

Hier sieht man, daß <math>d=3</math> gilt, denn jede Zeile unterscheidet sich in mindesten 3 Werten voneinander.

Bob erzeugt weiter die zufälligen Matrizen <math>S</math> und <math>P</math>:

:<math>S=\begin{pmatrix} 1 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 \end{pmatrix}</math>

:<math>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}</math>

Der erste Teil <math>\hat{G}</math> des öffentlichen Schlüssels berechnet sich wie folgt:

:<math>\hat{G}=SGP</math>

:<math>\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}=</math>

:<math>=\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}=</math>

:<math>=\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}</math>

Bob’s öffentlicher Schlüssel lautet nun:

:<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>