aboutsummaryrefslogtreecommitdiffstats
path: root/buch/chapters/90-crypto
diff options
context:
space:
mode:
authorJODBaer <JODBaer@github.com>2021-07-27 13:20:19 +0200
committerJODBaer <JODBaer@github.com>2021-07-27 13:20:19 +0200
commit058ff7a7400c321861da6d2b5156bf957cb09fd3 (patch)
tree776ef99b73444e731609237e4982b45027a90b02 /buch/chapters/90-crypto
parentsave (diff)
parentMerge pull request #49 from Kuehnee/master (diff)
downloadSeminarMatrizen-058ff7a7400c321861da6d2b5156bf957cb09fd3.tar.gz
SeminarMatrizen-058ff7a7400c321861da6d2b5156bf957cb09fd3.zip
Merge remote-tracking branch 'upstream/master' into Baer
Diffstat (limited to 'buch/chapters/90-crypto')
-rw-r--r--buch/chapters/90-crypto/Makefile.inc1
-rw-r--r--buch/chapters/90-crypto/arith.tex1
-rw-r--r--buch/chapters/90-crypto/ff.tex53
-rw-r--r--buch/chapters/90-crypto/rs.tex41
4 files changed, 48 insertions, 48 deletions
diff --git a/buch/chapters/90-crypto/Makefile.inc b/buch/chapters/90-crypto/Makefile.inc
index 9543ce1..508add5 100644
--- a/buch/chapters/90-crypto/Makefile.inc
+++ b/buch/chapters/90-crypto/Makefile.inc
@@ -8,5 +8,4 @@ CHAPTERFILES = $(CHAPTERFILES) \
chapters/90-crypto/arith.tex \
chapters/90-crypto/ff.tex \
chapters/90-crypto/aes.tex \
- chapters/90-crypto/rs.tex \
chapters/90-crypto/chapter.tex
diff --git a/buch/chapters/90-crypto/arith.tex b/buch/chapters/90-crypto/arith.tex
index dcc31b8..b05110f 100644
--- a/buch/chapters/90-crypto/arith.tex
+++ b/buch/chapters/90-crypto/arith.tex
@@ -91,6 +91,7 @@ Die Berechnung der Quadratwurzel lässt sich in Hardware effizient
implementieren.
\begin{algorithmus}
+\label{buch:crypto:teile-und-hersche}
Der folgende Algorithmus berechnet $a^k$ in $O(\log_2(k))$
Multiplikationen
\begin{enumerate}
diff --git a/buch/chapters/90-crypto/ff.tex b/buch/chapters/90-crypto/ff.tex
index 535b359..a1cb747 100644
--- a/buch/chapters/90-crypto/ff.tex
+++ b/buch/chapters/90-crypto/ff.tex
@@ -7,6 +7,15 @@
\section{Kryptographie und endliche Körper
\label{buch:section:kryptographie-und-endliche-koerper}}
\rhead{Kryptographie und endliche Körper}
+In diesem Abschnitt soll illustriert werden, wie die Arithmetik in
+endlichen Körpern Algorithmen zu konstruieren erlaubt, mit denen sich
+zum Beispiel sehr effizient kryptographische Schlüssel aushandeln
+lassen.
+Der klassische Diffie-Hellmann-Algorithmus in einem Galois-Körper
+$\mathbb{F}_p$ wird in Abschnitt~\ref{buch:subsection:elliptische-kurven}
+verallgemeinert auf eine sogenannte elliptische Kurve.
+Diese Version des Algorithmus ist sehr effizient was die Bitlänge der
+Schlüssel betrifft.
\subsection{Potenzen in $\mathbb{F}_p$ und diskreter Logarithmus
\label{buch:subsection:potenzen-diskreter-logarithmus}}
@@ -439,6 +448,7 @@ Das Polynom ist
\[
p(t)
=
+XXX
\]
Nach Division durch $t(t-1)$ erhält man als den Quotienten
\begin{align*}
@@ -652,13 +662,44 @@ Diese Operationen machen $E_{a,b}(\mathbb{F}_{p^l})$ zu einer endlichen
abelschen Gruppe.
\end{satz}
-\subsubsection{Beispiele}
-% XXX
-TODO: elliptische Kurven in IPsec: Oakley Gruppen
-
\subsubsection{Diffie-Hellman in einer elliptischen Kurve}
-% XXX
-TODO: $g^x$ in einer elliptischen Kurve
+Der klassische Diffie-Hellmann-Schlüsselalgorithmus in einem Körper
+$\mathbb{F}_p$ basiert darauf, dass man beliebige Potenzen eines
+Elementes berechnen kann, und dass es schwierig ist, diese Operation
+umzukehren.
+Die Addition in $\mathbb{F}_p$ wird für diesen Algorithmus überhaupt
+nicht benötigt.
+
+In einer elliptischen Kurve gibt es ebenfalls eine Multiplikation,
+aus der sich mit dem
+Algorithmus~\ref{buch:crypto:teile-und-hersche} eine effizienter
+Potenzieralgorithmus konstruieren lässt.
+
+Die im Internet Key Exchange Protokol
+in RFC 2409
+\cite{buch:rfc2409}
+definierte Oakley-Gruppe 4
+zum Beispiel verwendet einen Galois-Körper $\mathbb{F}_{2^{185}}$
+mit dem Minimalpolynom $m(x)=x^{185}+x^{69}+1\in \mathbb{F}_2[x]$
+und den Koeffizienten
+\begin{align*}
+a&=0\\
+b&=x^{12}+x^{11} + x^{10} + x^9 + x^7 + x^6 + x^5 + x^3 +1,
+\end{align*}
+die die elliptische Kurve definieren.
+
+Als Elemente $g$ für den Diffie-Hellmann-Algorithmus wird ein Punkt
+der elliptischen Kurve verwendet, dessen $X$-Koordinaten durch das
+Polynom $g_x = x^4+x^3$ gegeben ist.
+Der Standard spezifiziert die $Y$-Koordinate nicht, diese kann aus
+den gegebenen Daten abgeleitet werden.
+Die entstehende Gruppe hat etwa $4.9040\cdot10^{55}$ Elemente, die
+für einen brute-force-Angriff durchprobiert werden müssten.
+
+
+
+
+
diff --git a/buch/chapters/90-crypto/rs.tex b/buch/chapters/90-crypto/rs.tex
deleted file mode 100644
index ec8ec8c..0000000
--- a/buch/chapters/90-crypto/rs.tex
+++ /dev/null
@@ -1,41 +0,0 @@
-%
-% rs.tex -- Reed-Solomon-Code
-%
-% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
-%
-\section{Fehlerkorrigierende Codes nach Reed-Solomon
-\label{buch:section:reed-solomon}}
-\rhead{Fehlerkorrigierende Codes}
-Jede Art von Datenübertragung muss sich mit dem Problem der Fehler befassen,
-die auf dem Übertragungskanal entstehen können.
-Die einfachste Lösung dieses Problem versucht, Fehler zu erkennen und
-dann eine erneute Übermittelung zu veranlassen.
-Dies ist zum Beispiel bei der Datenübertragung von einer Raumsonde
-wie Voyager~1 nicht möglich, die Signallaufzeit von der Sonde und wieder
-zurück ist über 40 Stunden.
-Es ist auch nicht sinnvoll beim Lesen eines optischen Mediums wie einer
-CD oder DVD, wenn ein Fehler durch eine Beschädigung der Oberfläche
-des Mediums verursacht wird.
-Erneutes Lesen würde das Resultat auch nicht ändern.
-Es wird also eine Möglichkeit gesucht, die Daten so zu codieren, dass
-ein Fehler nicht nur erkannt sondern auch korrigiert werden kann.
-
-In diesem Abschnitt werden die algebraisch besonders interessanten
-Reed-Solmon-Codes beschrieben.
-Ihren ersten Einsatz hatten Sie bei den Voyager-Raumsonden, die 1977
-gestartet wurden.
-Sie befinden sich im Moment in einer Entfernung von
-Zum ersten mal kommerziell verwendet wurden sie für die optischen
-Medien CD und DVD.
-
-% https://www.youtube.com/watch?v=uOLW43OIZJ0
-% https://www.youtube.com/watch?v=4BfCmZgOKP8
-
-\subsection{Was ist ein Code?
-\label{buch:subsection:was-ist-ein-code}}
-
-\subsection{Reed-Solomon-Code
-\label{buch:subsection:reed-solomon-code}}
-
-\subsection{Decodierung
-\label{buch:subsection:decodierung}}