blob: 7ed1e5726e553da0a1ea9c3fdbcf0ff5b3f0e4c7 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
$A$ und $B$ einigen sich darauf, das Diffie-Hellman-Verfahren für
$p=2027$ durchzuführen und mit $g=3$ zu arbeiten.
$A$ verwenden $a=49$ als privaten Schlüssel und erhält von $B$
den öffentlichen Schlüssel $y=1772$.
Welchen gemeinsamen Schlüssel verwenden $A$ und $B$?
\begin{loesung}
Der zu verwendende gemeinsame Schlüssel ist
$g^{ab}=(g^b)^a = y^a\in\mathbb{F}_{2027}$.
Diese Potenz kann man mit dem Divide-and-Conquer-Algorithmus effizient
berechnen.
Die Binärdarstellung des privaten Schlüssels von $A$ ist
$a=49_{10}=\texttt{110001}_2$.
Der Algorithmus verläuft wie folgt:
\begin{center}
\begin{tabular}{|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|}
\hline
i&g^{2^i}&a_i& x\\
\hline
0& 3& 1& 3\\
1& 9& 0& 3\\
2& 81& 0& 3\\
3& 480& 0& 3\\
4& 1349& 1& 2020\\
5& 1582& 1& 1088\\
\hline
\end{tabular}
\end{center}
Der gemeinsame Schlüssel ist daher $s=1088$.
\end{loesung}
|
