\documentclass[12pt,a4paper]{article} \input{OhneKapitelVorspann} %\input{VorspannArtNetz} \begin{document} \section{"Offentliches Vereinbaren geheimer Schl"ussel} Wir bilden vier Gruppen zu je 5-6 Personen. Jede Gruppe ben"otigt mindestens einen 10-stelligen Taschenrechner und setzt sich zusammen in einer Ecke des Raums. Gruppen, die sich diagonal gegen"ubersitzen, bilden zusammen jeweils ein B"undnis. Jede der vier Gruppen einigt sich auf einen Gruppennamen. Nach M"oglichkeit sollten die Anfangsbuchstaben dieser Gruppennamen paarweise verschieden sein, bitte eintragen in die zweite Zeile der entsprechenden Tabelle auf Seite 3. Ich erkl"are das Weitere f"ur ein hypothetisches B"undnis mit den Gruppen {\bf Alice} und {\bf Bob}. In jedem B"undnis sollen nun durch Zurufen geheime Nachrichten von $\sim$ 20 Buchstaben ausgetauscht werden. Das andere B"undnis h"ort mit und versucht, die Nachrichten zu entschl"usseln. \vspace{0,5cm} \noindent Unser Verfahren (frei nach Diffie-Hellmann) besteht aus zwei Schritten: (1) dem "offentlichen Vereinbaren eines gemeinsamen geheimen Schl"ussels (bei uns einer f"unfstelligen Zahl $S$) und (2) dem Verschl"usseln der Nachricht mithilfe dieses Schl"ussels. Alice und Bob gehen vor wie folgt: \begin{enumerate} \item[(1)] \begin{itemize} \item Alice nennt "offentlich eine Zahl $N$ mit 4 Stellen, die zu 10 teilerfremd ist. Eintragen in die erste Zeile der entsprechenden Tabelle auf Seite 3! \item Alice und Bob w"ahlen im Geheimen dreistellige zu 10 teilerfremde Zahlen $a=g(\text{Alice})$ bzw. $b=g(\text{Bob})$, die Geheimzahl von Alice bzw.\ die Geheimzahl von Bob, die nicht einmal der B"undnispartner kennt. Sie berechnen nun die letzten f"unf Stellen von $N^{a}$ bzw.\ $N^{b}$. Die letzten 5 Stellen von $N^{a}$ nennen wir die Restzahl $R(\text{Alice}),$ das ist n"amlich der Rest von $N^{g(\text{Alice})}$ bei Division durch 100 000. Analog erkl"aren wir $R(\text{Bob}).$ Bemerkung: Die letzten 5 Stellen von $n m$ sowie von $n+m$ h"angen nur ab von den letzten 5 Stellen von $n$ und $m$. Um die letzten f"unf Stellen von $N^{a}$ zu finden, berechnet man zuerst die letzten f"unf Stellen von $N^{2},N^{4}, N^{8} \ldots,$ man benutze dazu eine freie Spalte der Tabelle auf Seite 4, berechnet parallel eine Darstellung von $a$ als Summe von Zweierpotenzen und kombiniert. Zum Beispiel haben wir $N^{14}=N^8 N^4 N^2.$ \item Jetzt werden die Restzahlen $R(\text{Alice})$ und $R(\text{Bob})$ "offentlich ausgetauscht (mitschreiben im Formular). \item Schlie"slich berechnet Alice die letzten 5 Stellen von $R(\text{Bob})^{g(\text{Alice})}$ und Bob berechnet die letzten 5 Stellen von $R(\text{Alice})^{g(\text{Bob})}$. Da gilt $(N^{b})^{a} = N^{ba} = (N^{a})^{b}$ stimmen diese beiden letzten 5 Stellen "uberein. Das ist dann der gemeinsame geheime Schl"ussel $S=S$(Alice, Bob) des B"undnisses, den wir auffassen als eine nat"urliche Zahl zwischen Null und 100 000. \end{itemize} \item[(2)] \begin{itemize} \item Seien nun $s_{1}, s_{2}, \ldots, s_{r}$ die Ziffern von $(S+3456)S$, bei $S=13423$ h"atten wir also $(S+3456)S=226566817,$ Stellenanzahl $r=9$ und Ziffern $s_1=2, $ $s_{2}=2, $ $s_{3}=6,$ etc. Nun gehe man vom ersten Buchstaben der Nachricht $s_{1}$ Schritte durch das Alphabet, vom zweiten $s_{2}$ Schritte etc.\, vom $(r+1)$-ten dann wieder $s_{1}$ Schritte und so weiter bis zum Ende der Nachricht. (Wenn man beim Gehen durch das Alphabet bei Z angekommt, so gehe man im n"achsten Schritt nach A weiter.) Die Nachricht BEIMESSENANGRIFF wird so verschl"usselt zu DGORKYAFOCPMWOLN. \end{itemize} \end{enumerate} \begin{Bemerkung} Dies elementare Vorgehen hat den Vorteil, da"s es sich mit einem Taschenrechner gut implementieren l"a"st. Das unter 1 beschriebenen Verfahren f"ur das "offentliche Vereinbaren eines gemeinsamen geheimen Schl"ussels kann zwar mit etwas Mathematik geknackt werden, wie wir uns sp"ater "uberlegen werden. Wenn man jedoch statt den letzten f"unf Stellen, d.h.\ dem Rest bei Division durch 100 000, jeweils den Rest bei Division durch eine Primzahl derselben Gr"o"senordnung nimmt, so ist es ein ziemlich gutes Verfahren. Eine Variante davon liegt dem ``Digital Signature Standard'' (DSS) der US-Regierung zugrunde. Hier arbeitet man jedoch mit Primzahlen, die so an die 160 Stellen haben. \end{Bemerkung} \begin{Bemerkung} Das unter 2 beschriebenen Verfahren f"ur das Verschl"usseln einer Nachricht mittels unseres Schl"ussels $S$ ist untauglich f"ur l"angere Nachrichten, da es angreifbar ist durch ``Frequenzanalyse''. Hier findet man leicht bessere Verschl"usselungsalgorithmen, aber wir wollen heute unsere Zeit und Energie auf das "offentliche Vereinbaren geheimer Schl"ussel konzentrieren. \end{Bemerkung} \begin{Bemerkung} Das Verfahren beruht darauf, da"s es sehr schwer ist, sogenannte ``diskrete Logarithmen'' zu berechnen: Ersetzen wir in unserem Verfahren 100000 durch eine gro"se Primzahl $p$ und ver"offentlichen Zahlen $N$ und $N^g$ ``modulo $p$'', so ist kein Algorithmus bekannt, der in vertretbarer Zeit ein m"ogliches $g$ liefern k"onnte. \end{Bemerkung} \vfill \begin{itemize} \item K"onnen Sie die letzte Stelle des feindlichen Schl"ussels $S$ herauskriegen? \item Die letzten beiden Stellen? \item Einige Buchstaben der geheimen Nachrichten (zumindest mit einer guten Wahrscheinlichkeit)? \end{itemize} \newpage $$ABCDEFGHIJKLMNOPQRSTUVWXYZ$$ \noindent \begin{tabular}{|c|l|l|}\hline {\bf Eigenes B"undnis}& \multicolumn{2}{l|}{$N=$}\\[3mm] \hline\hline Gruppennamen&{$\hspace{50mm}$}&$\hspace{50mm}$\\[3mm]\hline Geheimzahlen $g$&&\\[3mm]\hline Restzahlen $R$&&\\[3mm]\hline\hline $S=$\hspace{20mm} &\multicolumn{2}{l|}{$(S+3456)S=$}\\[3mm]\hline\hline Gesendete Nachricht&\multicolumn{2}{l|}{}\\[3mm] &\multicolumn{2}{l|}{}\\[2mm] Verschl"usselt&\multicolumn{2}{l|}{}\\[3mm]\hline Empfangene Nachricht &\multicolumn{2}{l|}{}\\[3mm] &\multicolumn{2}{l|}{}\\[2mm] Entschl"usselt&\multicolumn{2}{l|}{}\\[3mm]\hline \end{tabular}\\[1.5cm] \begin{tabular}{|c|l|l|}\hline \;\;{\bf Fremdes B"undnis}\;\;\;\!& \multicolumn{2}{l|}{$N=$}\\[3mm] \hline\hline Gruppennamen&{$\hspace{50mm}$}&$\hspace{50mm}$\\[3mm]\hline Geheimzahlen $g$&&\\[3mm]\hline Restzahlen $R$&&\\[3mm]\hline\hline $S=$\hspace{20mm} &\multicolumn{2}{l|}{$(S+3456)S=$}\\[3mm]\hline\hline Nachricht von &\multicolumn{2}{l|}{}\\[3mm] \dotfill&\multicolumn{2}{l|}{}\\[2mm] Entschl"usselt&\multicolumn{2}{l|}{}\\[3mm]\hline Nachricht von &\multicolumn{2}{l|}{}\\[3mm] \dotfill&\multicolumn{2}{l|}{}\\[2mm] Entschl"usselt&\multicolumn{2}{l|}{}\\[3mm]\hline \end{tabular} \newpage $$\begin{array}{r|r|c|c|c|c|} n&2^n&N^{2^n}\text{\tiny (letzte f"unf Stellen)}&\hspace{27mm}&\hspace{27mm}&\hspace{27mm}\\ \hline 0&1\;&&&&\\[6mm]\hline 1&2\;&&&&\\[6mm]\hline 2&4\;&&&&\\[6mm]\hline 3&8\;&&&&\\[6mm]\hline 4&16\;&&&&\\[6mm]\hline 5&32\;&&&&\\[6mm]\hline 6&64\;&&&&\\[6mm]\hline 7&128\;&&&&\\[6mm]\hline 8&256\;&&&&\\[6mm]\hline 9&512\;&&&&\\[6mm]\hline 10&1024\;&&&&\\[6mm]\hline 11&2048\;&&&&\\[6mm]\hline 12&4096\;&&&&\\[6mm]\hline \end{array}$$ \newpage \newpage \section{Knacken des Schl"ussels} Sie sollen nun versuchen, den geheimen Schl"ussel des jeweils anderen B"undnisses zu knacken. Um zu erkl"aren, wie man das angeht, brauche ich eine effektive Notation. Gegeben ganze Zahlen $a,b, K$ schreibt man $$a \equiv b \pmod{K}$$ und sagt, $a$ sei {\bf kongruent zu $b$ modulo $K$} genau dann, wenn $a-b$ ein Vielfaches von $K$ ist. F"ur $a,b,K \in \Bbb{N}$ bedeutet das genau, da"s $a$ und $b$ beim Teilen durch $K$ denselben Rest lassen. Zum Beispiel bedeutet $a \equiv b \pmod{10^5}$ f"ur $ a,b \geq 0$ genau, da"s die letzten 5 Stellen von $a$ und $b$ "ubereinstimmen. F"ur beliebige $a, b, c\in \Bbb{Z}$ haben wir $$a \equiv b \pmod{K} \;\;\Rightarrow\;\; \begin{array}[c]{cccc} a + c &\equiv& b + c &\pmod {K}\\ a \cdot c &\equiv& b \cdot c &\pmod {K} \end{array} $$ \subsection{Algorithmus zum Schl"usselknacken} \emph{Erst nach und nach verraten!} Wir kennen zum Beispiel $N,R=R(\text{Alice})$ mit $N$ teilerfremd zu $10$ und suchen in dieser Notation einen Exponenten $g\in\DN$ mit $$N^{g} \equiv R \pmod{10^{5}}$$ Dieses $g$ ist nicht eindeutig bestimmt, aber f"ur jede L"osung $g$ wird gelten $R(\text{Bob})^g\equiv S \pmod{10^{5}}.$ Wir betrachten erst mal unsere Gleichung $N^{g} \equiv R \pmod{10^{5}}$ modulo $10.$ Sei zum Beispiel $N=8437$ und $R=63133.$ Modulo 10 vereinfacht sich unsere Gleichung zu $7^g\equiv 3 \pmod{10}.$ Die Potenzen von $7$ modulo 10 sind der Reihe nach $1,7,9,3,1,7,9,3,1,7,\ldots$ und wir folgern $g=3+4n$ f"ur eine nat"urliche Zahl $n.$ Modulo 100 wird unsere Gleichung zu $37^g\equiv 33 \pmod{100}.$ Die ersten Potenzen von $37$ modulo $100$ sind $1,37, 69, 53, 61, \ldots.$ Setzen wir $g=3+4n$ ein, so vereinfacht sich unsere Gleichung modulo 100 zu $ 37^3 (37^4)^n \equiv 33 \pmod{100}$ und dann zu $53\cdot 61^n\equiv 33 \pmod{100}.$ Die ersten Potenzen von $61$ modulo $100$ sind $1,61, 21, 81, 41, 01, 61, 21, \ldots$ Probieren liefert $n=1+5m$ und damit $g=7+20m.$ Modulo 1000 wird unsere Gleichung zu$\ldots$ \newpage \noindent Ich will versuchen, das Verfahren von Diffie-Hellman zum "offentlichen Vereinbaren geheimer Schl"ussel f"ur Mathematiker anhand des folgenden Schemas zu erkl"aren. Wir arbeiten vorne mit der Gruppe $G=\DZ/10000\DZ.$ \vspace{0,5cm} \noindent \begin{tabular}{|p{4.2cm}||p{3.9cm}||p{4cm}|}\hline Geheimbereich Alice& "Offentlicher Bereich & Geheimbereich Bob\\ \hline &Bekanntgemacht wird eine Gruppe $G$ und ein Element $g\in G.$ & \\ \hline Alice w"ahlt $a \in \Bbb{N},$ berechnet $g^{a}$ und macht es "offentlich.& & Bob w"ahlt $b \in \Bbb{N},$ berechnet $g^{b}$ und macht es "offentlich.\\ \hline & \hspace{1.3cm}$g^{a},$ $g^{b}$\hfill&\\ \hline Nach dem "offentlichen Austausch berechnet Alice $(g^{b})^{a} = g^{ba} = g^{ab}.$& & Nach dem "offentlichen Austauch berechnet Bob $(g^{a})^{b} = g^{ab}=g^{ba}.$\\ \hline \end{tabular} \vspace{0,5cm} \noindent Das Gruppenelement $g^{ba} = g^{ab}$ ist dann der gemeinsame hoffentlich geheime Schl"ussel. Der Trick hierbei besteht darin, da"s bei geeigneten Paaren $(G,g)$ und geeigneten Zahlen $a$, zum Beispiel im Fall einer elliptischen Kurve $G$, einem nichttrivialen Element $g \in G$ gro"ser Ordnung und den meisten $a,$ kein schneller Algorithmus bekannt ist, der aus der Kenntnis von $G, g$ und $g^{a}$ ein m"ogliches $a$ bestimmt, der also, wie man auch sagt, einen \defind{diskreten Logarithmus} {\bf von $g^{a}$ zur Basis $g$} findet. Dahingegen ist die Berechnung von $g^{a}$ unproblematisch. Deshalb kann Alice $g^{a}$ ver"offentlichen und dennoch $a$ geheim halten. Nun ist es nat"urlich denkbar, da"s man aus der Kenntnis von $g^{a}$ und $g^{b}$ direkt $g^{ab}$ berechnen kann, ohne zuvor $a$ zu bestimmen, aber auch f"ur die L"osung dieses sogenannten \defind{Diffie-Hellman-Problems} ist im Fall elliptischer Kurven kein schneller Algorithmus bekannt. Mit den derzeitig verf"ugbaren Rechenmaschinen k"onnen also Alice und Bob mit einer Rechenzeit von unter einer Minute einen geheimen Schl"ussel vereinbaren, dessen Entschl"usselung auf derselben Maschine beim gegenw"artigen Stand der ver"offentlichten Forschung Millionen von Jahren br"auchte. Allerdings ist auch wieder nicht bewiesen, da"s es im Fall elliptischer Kurven nicht doch einen effizienten Algorithmus zur L"osung des Diffie-Hellman-Problems gibt. \end{document} %pdflatex "\PassOptionsToPackage{final}{showkeys}\PassOptionsToPackage{final}{ifdraft}\input{Verschluesselung}"