aboutsummaryrefslogtreecommitdiffstats
path: root/buch/papers/mceliece
diff options
context:
space:
mode:
authorReto <reto.fritsche@ost.ch>2021-07-29 23:07:18 +0200
committerReto <reto.fritsche@ost.ch>2021-07-29 23:07:18 +0200
commita310c9290f64d938e87226db84d524a7a817ec68 (patch)
treeb2a83ced8e2f57de530c28ce12e8d86d13118f14 /buch/papers/mceliece
parentMerge pull request #51 from paschost/patch-1 (diff)
downloadSeminarMatrizen-a310c9290f64d938e87226db84d524a7a817ec68.tar.gz
SeminarMatrizen-a310c9290f64d938e87226db84d524a7a817ec68.zip
reorganized files, started work on Einleitung, Aufbau
Diffstat (limited to '')
-rw-r--r--buch/papers/mceliece/Makefile.inc8
-rw-r--r--buch/papers/mceliece/aufbau.tex128
-rw-r--r--buch/papers/mceliece/einleitung.tex14
-rw-r--r--buch/papers/mceliece/fazit.tex (renamed from buch/papers/mceliece/teil3.tex)6
-rw-r--r--buch/papers/mceliece/funktionsweise.tex (renamed from buch/papers/mceliece/teil2.tex)6
-rw-r--r--buch/papers/mceliece/main.tex27
-rw-r--r--buch/papers/mceliece/references.bib22
-rw-r--r--buch/papers/mceliece/teil0.tex22
-rw-r--r--buch/papers/mceliece/teil1.tex55
9 files changed, 171 insertions, 117 deletions
diff --git a/buch/papers/mceliece/Makefile.inc b/buch/papers/mceliece/Makefile.inc
index ed1affa..53ecf7a 100644
--- a/buch/papers/mceliece/Makefile.inc
+++ b/buch/papers/mceliece/Makefile.inc
@@ -7,8 +7,8 @@ dependencies-mceliece = \
papers/mceliece/packages.tex \
papers/mceliece/main.tex \
papers/mceliece/references.bib \
- papers/mceliece/teil0.tex \
- papers/mceliece/teil1.tex \
- papers/mceliece/teil2.tex \
- papers/mceliece/teil3.tex
+ papers/mceliece/einleitung.tex \
+ papers/mceliece/aufbau.tex \
+ papers/mceliece/funktionsweise.tex \
+ papers/mceliece/fazit.tex
diff --git a/buch/papers/mceliece/aufbau.tex b/buch/papers/mceliece/aufbau.tex
new file mode 100644
index 0000000..08ef037
--- /dev/null
+++ b/buch/papers/mceliece/aufbau.tex
@@ -0,0 +1,128 @@
+%
+% einleitung.tex -- Beispiel-File für die Einleitung
+%
+% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
+%
+\section{Aufbau\label{mceliece:section:Aufbau}}
+\rhead{Aufbau}
+Das McEliece-Kryptosystem besteht aus folgenden Elementen:
+
+\subsection{Datenvektor $d_k$
+\label{mceliece:subsection:d_k}}
+In diesem Vektor der Länge $k$ sind die zu verschlüsselnden Daten enthalten.
+Beispielsweise
+\[d_4=
+\begin{pmatrix}
+ 1\\
+ 1\\
+ 1\\
+ 0
+\end{pmatrix}
+\]
+
+\subsection{Binäre Zufallsmatrix $S_k$
+\label{mceliece:subsection:s_k}}
+$S_k$ ist eine Binäre Zufallsmatrix der Grösse $k \times k$.
+Auch muss diese Matrix in $\mathbb{F}_2$ invertierbar sein.
+Für kleine Matrizen kann durchaus jedes Matrizenelement zufällig generiert werden,
+wobei danach mithilfe des Gauss-Algorythmusses deren Inverse bestimmt werden kann.
+Da eine solche Matrix möglicherweise singulär ist, muss in diesem Fall eine neue Zufallsmatrix erzeugt werden.
+Für grössere Matrizen existieren bessere Methoden, auf welche hier nicht weiter eingegangen wird \cite{mceliece:GenerationRandMatrix}.
+Beispielsweise
+\[S_4=
+\begin{pmatrix}
+ 0 & 1 & 1 & 1\\
+ 0 & 1 & 1 & 0\\
+ 0 & 0 & 1 & 1\\
+ 1 & 0 & 0 & 1
+\end{pmatrix}
+\]
+
+\[
+ S_4^{-1}=
+ \begin{pmatrix}
+ 1 & 0 & 1 & 0\\
+ 1 & 1 & 0 & 1\\
+ 1 & 1 & 1 & 0\\
+ 1 & 1 & 0 & 0
+ \end{pmatrix}
+\]
+
+\subsection{Linear-Code-Generatormatrix $G_{n,k}$
+\label{mceliece:subsection:g_m}}
+Das wichtigste Element des McEliece-Systems ist ein fehlerkorrigierender Code,
+der in der Lage ist, $t$ Fehler zu korrigieren.
+Im Zusammenhang mit McEliece werden dabei meist Goppa-Codes verwendet,
+es können prinzipiell auch andere Codes wie beispielsweise Reed-Solomin verwendet werden,
+jedoch besitzen einige Codes Schwachstellen \cite{mceliece:lorenz}.
+Das Codieren mit diesem linearen Code kann mithilfe dessen Generatormatrix $G_{n,k}$ erfolgen.
+Da es sich um einen fehlerkorrigierenden Code handelt,
+wird das Codewort länger als das Datenwort,
+es wird also Redundanz hinzugefügt,
+um die Fehlerkorrektur möglich zu machen.
+
+Beispiel
+\[
+ G_{7,4}=
+ \begin{pmatrix}
+ 1 & 0 & 0 & 0\\
+ 1 & 1 & 0 & 0\\
+ 0 & 1 & 1 & 0\\
+ 1 & 0 & 1 & 1\\
+ 0 & 1 & 0 & 1\\
+ 0 & 0 & 1 & 0\\
+ 0 & 0 & 0 & 1
+ \end{pmatrix}
+\]
+
+\subsection{Permutations-Matrix $P_n$
+\label{mceliece:subsection:p_m}}
+Mit der zufällig generierten Permutationsmatrix $P_n$ wird die Reihenfolge der Bits geändert.
+Mit der Inversen $P_n^{-1}$ kann die Bitvertauschung rückgängig gemacht werden.
+Beispiel
+\[
+ P_7=
+ \begin{pmatrix}
+ 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\\
+ 0 & 0 & 0 & 1 & 0 & 0 & 0\\
+ 1 & 0 & 0 & 0 & 0 & 0 & 0\\
+ 0 & 0 & 0 & 0 & 1 & 0 & 0
+ \end{pmatrix}
+\]
+,
+\[
+ P_7^{-1}=P_7^t=
+ \begin{pmatrix}
+ 0 & 0 & 0 & 0 & 0 & 1 & 0\\
+ 1 & 0 & 0 & 0 & 0 & 0 & 0\\
+ 0 & 0 & 0 & 1 & 0 & 0 & 0\\
+ 0 & 0 & 0 & 0 & 1 & 0 & 0\\
+ 0 & 0 & 0 & 0 & 0 & 0 & 1\\
+ 0 & 0 & 1 & 0 & 0 & 0 & 0\\
+ 0 & 1 & 0 & 0 & 0 & 0 & 0
+ \end{pmatrix}
+\]
+
+\subsection{Fehler-Vektor $e_n$
+\label{mceliece:subsection:p_m}}
+Dieser Vektor der Länge $n$ besteht aus $t$ Einsen, welche zufällig innerhalb des Vektors angeordnet sind,
+alle anderen Einträge sind Null.
+Dieser Fehlervektor besitzt also gleich viele Einer,
+wie die Anzahl Fehler, die der Linearcode zu korrigieren vermag.
+
+Beispiel
+\[
+ E_7=
+ \begin{pmatrix}
+ 0\\
+ 0\\
+ 1\\
+ 0\\
+ 0\\
+ 0\\
+ 0
+ \end{pmatrix}
+\]
diff --git a/buch/papers/mceliece/einleitung.tex b/buch/papers/mceliece/einleitung.tex
new file mode 100644
index 0000000..48b55b0
--- /dev/null
+++ b/buch/papers/mceliece/einleitung.tex
@@ -0,0 +1,14 @@
+%
+% teil1.tex -- Beispiel-File für das Paper
+%
+% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
+%
+\section{Einleitung
+\label{mceliece:section:einleitung}}
+\rhead{Einleitung}
+Das McEliece-Kryptosystem ist eine Variante zum Austausch
+von Schlüsselpaaren über ein Netzwerk analog dem Diffie-Hellman-Schlüsseltausch \ref{buch:subsection:diffie-hellman},
+wobei das McEliece-System als Quantencomputerresistent gilt.
+Das Verschlüsseln/Entschlüsseln von Nachrichten wird bei diesem System hauptsächlich mit Matrizenoperationen durchgeführt.
+
+
diff --git a/buch/papers/mceliece/teil3.tex b/buch/papers/mceliece/fazit.tex
index 421b331..37152bf 100644
--- a/buch/papers/mceliece/teil3.tex
+++ b/buch/papers/mceliece/fazit.tex
@@ -3,9 +3,9 @@
%
% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
%
-\section{Teil 3
-\label{mceliece:section:teil3}}
-\rhead{Teil 3}
+\section{Fazit
+\label{mceliece:section:fazit}}
+\rhead{Fazit}
Sed ut perspiciatis unde omnis iste natus error sit voluptatem
accusantium doloremque laudantium, totam rem aperiam, eaque ipsa
quae ab illo inventore veritatis et quasi architecto beatae vitae
diff --git a/buch/papers/mceliece/teil2.tex b/buch/papers/mceliece/funktionsweise.tex
index fd247c7..0e2ed1b 100644
--- a/buch/papers/mceliece/teil2.tex
+++ b/buch/papers/mceliece/funktionsweise.tex
@@ -3,9 +3,9 @@
%
% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
%
-\section{Teil 2
-\label{mceliece:section:teil2}}
-\rhead{Teil 2}
+\section{Funktionsweise
+\label{mceliece:section:funktionsweise}}
+\rhead{Funktionsweise}
Sed ut perspiciatis unde omnis iste natus error sit voluptatem
accusantium doloremque laudantium, totam rem aperiam, eaque ipsa
quae ab illo inventore veritatis et quasi architecto beatae vitae
diff --git a/buch/papers/mceliece/main.tex b/buch/papers/mceliece/main.tex
index dbbaaac..352a6be 100644
--- a/buch/papers/mceliece/main.tex
+++ b/buch/papers/mceliece/main.tex
@@ -8,29 +8,10 @@
\begin{refsection}
\chapterauthor{Reto Fritsche}
-Ein paar Hinweise für die korrekte Formatierung des Textes
-\begin{itemize}
-\item
-Absätze werden gebildet, indem man eine Leerzeile einfügt.
-Die Verwendung von \verb+\\+ ist nur in Tabellen und Arrays gestattet.
-\item
-Die explizite Platzierung von Bildern ist nicht erlaubt, entsprechende
-Optionen werden gelöscht.
-Verwenden Sie Labels und Verweise, um auf Bilder hinzuweisen.
-\item
-Beginnen Sie jeden Satz auf einer neuen Zeile.
-Damit ermöglichen Sie dem Versionsverwaltungssysteme, Änderungen
-in verschiedenen Sätzen von verschiedenen Autoren ohne Konflikt
-anzuwenden.
-\item
-Bilden Sie auch für Formeln kurze Zeilen, einerseits der besseren
-Übersicht wegen, aber auch um GIT die Arbeit zu erleichtern.
-\end{itemize}
-
-\input{papers/mceliece/teil0.tex}
-\input{papers/mceliece/teil1.tex}
-\input{papers/mceliece/teil2.tex}
-\input{papers/mceliece/teil3.tex}
+\input{papers/mceliece/einleitung.tex}
+\input{papers/mceliece/aufbau.tex}
+\input{papers/mceliece/funktionsweise.tex}
+\input{papers/mceliece/fazit.tex}
\printbibliography[heading=subbibliography]
\end{refsection}
diff --git a/buch/papers/mceliece/references.bib b/buch/papers/mceliece/references.bib
index 47798d3..56f2d19 100644
--- a/buch/papers/mceliece/references.bib
+++ b/buch/papers/mceliece/references.bib
@@ -4,13 +4,13 @@
% (c) 2020 Autor, Hochschule Rapperswil
%
-@online{mceliece:bibtex,
- title = {BibTeX},
- url = {https://de.wikipedia.org/wiki/BibTeX},
- date = {2020-02-06},
- year = {2020},
- month = {2},
- day = {6}
+@online{mceliece:GenerationRandMatrix,
+ title = {Efficient Generation of Random Nonsingular Matrices},
+ url = {https://www.researchgate.net/publication/2729950_Efficient_Generation_of_Random_Nonsingular_Matrices},
+ date = {Januar 1993},
+ year = {2021},
+ month = {7},
+ day = {29}
}
@book{mceliece:numerical-analysis,
@@ -33,3 +33,11 @@
url = {https://doi.org/10.1016/j.acha.2017.11.004}
}
+@online{mceliece:lorenz,
+ title = {Cryptography based on error correcting codes},
+ url = {https://algo.epfl.ch/_media/en/projects/lorenz_thesis.pdf},
+ date = {2007-07-27},
+ year = {2021},
+ month = {7},
+ day = {29}
+} \ No newline at end of file
diff --git a/buch/papers/mceliece/teil0.tex b/buch/papers/mceliece/teil0.tex
deleted file mode 100644
index b98f8be..0000000
--- a/buch/papers/mceliece/teil0.tex
+++ /dev/null
@@ -1,22 +0,0 @@
-%
-% einleitung.tex -- Beispiel-File für die Einleitung
-%
-% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
-%
-\section{Teil 0\label{mceliece:section:teil0}}
-\rhead{Teil 0}
-Lorem ipsum dolor sit amet, consetetur sadipscing elitr, sed diam
-nonumy eirmod tempor invidunt ut labore et dolore magna aliquyam
-erat, sed diam voluptua \cite{mceliece:bibtex}.
-At vero eos et accusam et justo duo dolores et ea rebum.
-Stet clita kasd gubergren, no sea takimata sanctus est Lorem ipsum
-dolor sit amet.
-
-Lorem ipsum dolor sit amet, consetetur sadipscing elitr, sed diam
-nonumy eirmod tempor invidunt ut labore et dolore magna aliquyam
-erat, sed diam voluptua.
-At vero eos et accusam et justo duo dolores et ea rebum. Stet clita
-kasd gubergren, no sea takimata sanctus est Lorem ipsum dolor sit
-amet.
-
-
diff --git a/buch/papers/mceliece/teil1.tex b/buch/papers/mceliece/teil1.tex
deleted file mode 100644
index 06035a6..0000000
--- a/buch/papers/mceliece/teil1.tex
+++ /dev/null
@@ -1,55 +0,0 @@
-%
-% teil1.tex -- Beispiel-File für das Paper
-%
-% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
-%
-\section{Teil 1
-\label{mceliece:section:teil1}}
-\rhead{Problemstellung}
-Sed ut perspiciatis unde omnis iste natus error sit voluptatem
-accusantium doloremque laudantium, totam rem aperiam, eaque ipsa
-quae ab illo inventore veritatis et quasi architecto beatae vitae
-dicta sunt explicabo.
-Nemo enim ipsam voluptatem quia voluptas sit aspernatur aut odit
-aut fugit, sed quia consequuntur magni dolores eos qui ratione
-voluptatem sequi nesciunt
-\begin{equation}
-\int_a^b x^2\, dx
-=
-\left[ \frac13 x^3 \right]_a^b
-=
-\frac{b^3-a^3}3.
-\label{mceliece:equation1}
-\end{equation}
-Neque porro quisquam est, qui dolorem ipsum quia dolor sit amet,
-consectetur, adipisci velit, sed quia non numquam eius modi tempora
-incidunt ut labore et dolore magnam aliquam quaerat voluptatem.
-
-Ut enim ad minima veniam, quis nostrum exercitationem ullam corporis
-suscipit laboriosam, nisi ut aliquid ex ea commodi consequatur?
-Quis autem vel eum iure reprehenderit qui in ea voluptate velit
-esse quam nihil molestiae consequatur, vel illum qui dolorem eum
-fugiat quo voluptas nulla pariatur?
-
-\subsection{De finibus bonorum et malorum
-\label{mceliece:subsection:finibus}}
-At vero eos et accusamus et iusto odio dignissimos ducimus qui
-blanditiis praesentium voluptatum deleniti atque corrupti quos
-dolores et quas molestias excepturi sint occaecati cupiditate non
-provident, similique sunt in culpa qui officia deserunt mollitia
-animi, id est laborum et dolorum fuga \eqref{000tempmlate:equation1}.
-
-Et harum quidem rerum facilis est et expedita distinctio
-\ref{mceliece:section:loesung}.
-Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil
-impedit quo minus id quod maxime placeat facere possimus, omnis
-voluptas assumenda est, omnis dolor repellendus
-\ref{mceliece:section:folgerung}.
-Temporibus autem quibusdam et aut officiis debitis aut rerum
-necessitatibus saepe eveniet ut et voluptates repudiandae sint et
-molestiae non recusandae.
-Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis
-voluptatibus maiores alias consequatur aut perferendis doloribus
-asperiores repellat.
-
-