Im Wesentlichen Cryptography and Network Security - Principles and Practice, 8th Edition, William Stallings
Ein \(b\) ungleich Null teilt \(a\) wenn \(a = mb\) für ein beliebiges \(m\) und \(a\), \(b\) und \(m\) ganze Zahlen sind.
\(b\) teilt \(a\) wenn es keinen Rest bei der Division gibt.
Die Notation \(b|a\) bedeutet, dass \(b\) \(a\) teilt.
Wenn \(b|a\) gilt, dann sagen wir auch, dass \(b\) ein Teiler von \(a\) ist.
Wenn \(a|1\), dann gilt \(a = \pm 1\).
Wenn \(a | b\) und \(b|a\), dann gilt \(a = \pm b\).
Jedes \(b \neq 0\) teilt \(0\).
Wenn \(a | b\) und \(b|c\), dann \(a|c\).
Wenn \(b | g\) und \(b|h\), dann \(b|(mg+nh)\) für beliebige ganze Zahlen \(m\) und \(n\).
Sei eine beliebige positive ganze Zahl \(n\) gegeben und eine beliebige ganze Zahl \(a \geq 0\), so erhält man bei der Division von \(a\) durch \(n\):
einen ganzzahligen Quotienten \(q\) und
einen nicht negativen, ganzzahligen Rest \(r\),
die der folgenden Beziehung gehorchen:
Eine der grundlegenden Techniken der Zahlentheorie.
Verfahren zur Bestimmung des größten gemeinsamen Teilers (GGT) von zwei positiven ganzen Zahlen.
(Greatest Common Divisor (GCD))
Der größte gemeinsame Teiler von zwei ganzen Zahlen \(a\) und \(b\) ist die größte ganze Zahl, die sowohl \(a\) als auch \(b\) teilt.
Wir verwenden die Schreibweise \(ggt(a,b)\) für den GGT von \(a\) und \(b\).
Wir definieren \(ggt(0,0) = 0\).
Die positive ganze Zahl \(c\) wird als GGT von \(a\) und \(b\) bezeichnet, wenn:
\(c\) ein Teiler von \(a\) und \(b\) ist
jeder Teiler von \(a\) und \(b\) ein Teiler von \(c\) ist
Wir stellten fest:
Zwei ganze Zahlen \(a\) und \(b\) sind relativ prim, wenn ihr einziger gemeinsamer positiver ganzzahliger Faktor 1 ist.
\(\Leftrightarrow\)
\(a\) und \(b\) sind relativ prim wenn \(ggt(a,b)=1\)
Schritt |
Dividend |
Divisor |
Quotient |
Rest |
|---|---|---|---|---|
1 |
1.160.718.174 |
316.258.250 |
3 |
211.943.424 |
2 |
316.258.250 |
211.943.424 |
1 |
10.431.4826 |
3 |
211.943.424 |
104.314.826 |
2 |
3.313.772 |
4 |
104.314.826 |
3.313.772 |
31 |
1.587.894 |
5 |
3.313.772 |
1.587.894 |
2 |
137.984 |
6 |
1.587.894 |
137.984 |
11 |
70.070 |
7 |
137.984 |
70.070 |
1 |
67.914 |
8 |
70.070 |
67.914 |
1 |
2.156 |
9 |
67.914 |
2.156 |
31 |
1.078 |
10 |
2.156 |
1.078 |
2 |
0 |
Wenn \(a\) eine ganze Zahl und \(n\) eine positive ganze Zahl ist, dann definieren wir \(a\; mod\; n\) als Rest der Division von \(a\) durch \(n\). Die ganze Zahl \(n\) wird als Modulus bezeichnet.
Somit gilt für jede ganze Zahl \(a\):
Zwei ganze Zahlen \(a\) und \(b\) werden als kongruent modulo \(n\) bezeichnet, wenn \((a\; mod\; n) = (b\; mod\; n)\)
Wir verwenden die Schreibweise \(a \equiv b(mod\; n)\).
Beachten Sie, dass, wenn \(a \equiv 0 (mod\; n)\) ist, dann gilt \(n|a\).
Hinweis:
\(21 \equiv -9 (mod\, 10) \Leftrightarrow 21\, mod\, 10 = -9\, mod\, 10 = 1\)
\(-9\, mod\, 10 \rightarrow -9 = n * 10 + 1\)
\(a \equiv b (mod\; n)\) wenn \(n|(a-b)\) (Siehe nächste Folie.)
\(a \equiv b (mod\; n) \Rightarrow b \equiv a (mod\; n)\)
\(a \equiv b (mod\; n)\) und \(b \equiv c (mod\; n) \Rightarrow a \equiv c (mod\; n)\)
Wenn \(n|(a - b)\), dann gilt \((a - b) = kn\) für ein \(k\)
Wir können also schreiben \(a=b+kn\).
Deshalb gilt \((a\; mod\; n)\) =
(Rest wenn \(b + kn\) geteilt wird durch \(n\)) =
(Rest wenn \(b\) geteilt wird durch \(n\)) =
\((b\; mod\; n)\)
Im zweiten Schritt haben wir \(mod\; n\) auf beide Seiten angewendet.
d. h. \((b + kn) mod\; n\) \(\hat{=}\) (Rest wenn \(b + kn\) geteilt wird durch \(n\)).
\([(a\; mod\; n) + (b\; mod\; n)]\; mod\; n = (a + b)\; mod\; n\)
\([(a\; mod\; n) - (b\; mod\; n)]\; mod\; n = (a - b)\; mod\; n\)
\([(a\; mod\; n) \times (b\; mod\; n)]\; mod\; n = (a \times b)\; mod\; n\)
Definiere \((a\; mod\; n) = r_a\) und \((b\; mod\; n) = r_b\).
Dann können wir:
\(a = r_a + jn\) für eine ganze Zahl \(j\) und
\(b = r_b + kn\) für eine ganze Zahl \(k\) schreiben.
Dann gilt:
Im vorletzten Schritt setzen wir die Definition vom Anfang ein und erhalten das Ergebnis.
\(+\) |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
0 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
1 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
0 |
2 |
2 |
3 |
4 |
5 |
6 |
7 |
0 |
1 |
3 |
3 |
4 |
5 |
6 |
7 |
0 |
1 |
2 |
4 |
4 |
5 |
6 |
7 |
0 |
1 |
2 |
3 |
5 |
5 |
6 |
7 |
0 |
1 |
2 |
3 |
4 |
6 |
6 |
7 |
0 |
1 |
2 |
3 |
4 |
5 |
7 |
7 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
\(\times\) |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
2 |
0 |
2 |
4 |
6 |
0 |
2 |
4 |
6 |
3 |
0 |
3 |
6 |
1 |
4 |
7 |
2 |
5 |
4 |
0 |
4 |
0 |
4 |
0 |
4 |
0 |
4 |
5 |
0 |
5 |
2 |
7 |
4 |
1 |
6 |
3 |
6 |
0 |
6 |
4 |
2 |
0 |
6 |
4 |
2 |
7 |
0 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
Generator in Python:
for i in range(0,8):
print(str(i)+", ",end="")
for j in range(0,8):
v = (i*j) % 8
if v == 1:
v = "*"+str(v)+"*"
else:
v = str(v)
print(v+",",end="")
print()\(w\) |
\(-w\) |
\(w^{-1}\) |
|---|---|---|
0 |
0 |
\(-\) |
1 |
7 |
1 |
2 |
6 |
\(-\) |
3 |
5 |
3 |
4 |
4 |
\(-\) |
5 |
3 |
5 |
6 |
2 |
\(-\) |
7 |
1 |
7 |
\((w + x)\; mod\; n = (x + w)\; mod\; n\)
\((w \times x)\; mod\; n = (x \times w)\; mod\; n\)
\([(w + x) + y]\; mod\; n = [w + (x + y)]\; mod\; n\)
\([(w \times x) \times y]\; mod\; n = [w \times (x \times y)]\; mod\; n\)
\([w \times (x + y)]\; mod\; n = [(w \times x) + (w \times y)]\; mod\; n\)
\((0 + w)\; mod\; n = w\; mod\; n\)
\((1 \times w)\; mod\; n = w\; mod\; n\)
Für jedes \(w \in Z_n\) gibt es ein \(z\), so dass \(w + z \equiv 0\; (mod\; n)\)
Algorithmus
def Euclid(a,b):
if (b = 0) then
return a;
else
return Euclid(b, a mod b);Beispiel
ggt(10,6)
↳ ggt(6,4)
↳ ggt(4,2)
↳ ggt(2,0)
2 ↩︎Um welche Art von rekursivem Algorithmus handelt es sich hierbei?
In der gegebenen Formulierung ist der Algorithmus endrekursiv (tail recursive).
Erforderlich für Berechnungen im Bereich der endlichen Körper und Verschlüsselungsalgorithmen wie RSA.
Für zwei ganze Zahlen \(a\) und \(b\) berechnet der erweiterte euklidische Algorithmus den GGT \(d\), aber auch zwei zusätzliche ganze Zahlen \(x\) und \(y\), die die folgende Gleichung erfüllen:
Notwendigerweise haben \(x\) und \(y\) gegensätzliche Vorzeichen, da sonst \((x \times a + y \times b) > a\; ( > b )\) gelten würde und somit nicht den GGT darstellen könnte.
Der erweiterte euklidische Algorithmus kann auf jeden Ring angewandt werden, in welchem eine Division mit kleinstem Rest durchgeführt werden kann. Ein Beispiel ist der Polynomring in einer Variablen mit rationalen oder reellen Koeffizienten wie sie bei der Verschlüsselung angewandt werden. Wir werden dies später wieder aufgreifen.
Der erweiterte Algo. dient insbesondere der Berechnung der inversen Elemente in ganzzahligen Restklassenringen. (Beides werden wir später in der Vorlesung betrachten).
Werfen wir einen Blick auf \(x \times a + y \times b\) für einige \(x\) und \(y\):
\(_у \\ ^x\) |
-3 |
-2 |
-1 |
0 |
1 |
2 |
3 |
-3 |
-216 |
-174 |
-132 |
-90 |
-48 |
-6 |
36 |
-2 |
-186 |
-144 |
-102 |
-60 |
-18 |
24 |
66 |
-1 |
-156 |
-114 |
-72 |
-30 |
12 |
54 |
96 |
0 |
-126 |
-84 |
-42 |
0 |
42 |
84 |
126 |
1 |
-96 |
-54 |
-12 |
30 |
72 |
114 |
156 |
2 |
-66 |
-24 |
18 |
60 |
102 |
144 |
186 |
3 |
-36 |
6 |
48 |
90 |
132 |
174 |
216 |
Umgestellt:
Aufgrund der Umstellung z. B. von \(710 = 2 \times 310 + 90\) nach \(90 = 710 - 2 \times 310\) können wir dann im nächsten Schritt/der nächsten Formel die \(90\) durch \(710 - 2 \times 310\) ersetzen und werden dann \(310 - 3 \times(710 - 2 \times 310) = 40\) erhalten.
D. h. betrachten wir \(710\) als \(a\) und \(310\) als \(b\), erhalten wir durch die Umstellung eine Formel, die nur aus \(a\)s und \(b\)s zuzüglich zweiter Koeffizienten und dem Rest r besteht.
\(x = 7\) und \(y = -16\)
Wir nehmen an, dass wir bei jedem Schritt \(i\) die ganzen Zahlen \(x_i\) und \(y_i\) finden können, die folgende Bedingung erfüllen: \(r_i = ax_i + by_i\).
Berechne |
Was erfüllt |
Berechne |
Was erfüllt |
|---|---|---|---|
\(r_{-1} = a\) |
\(x_{-1}=1;\quad y_{-1}=0\) |
\(a = ax_{-1} + by_{-1}\) |
|
\(r_{0} = b\) |
\(x_0=0;\quad y_{0}=1\) |
\(b = ax_{0} + by_{0}\) |
|
\(r_{1} = a\;mod\;b;\quad q_1= \lfloor a/b \rfloor\) |
\(a=q_1b+r_1\) |
\(x_1=x_{-1} -q_1x_0 = 1\); \(y_1=y_{-1} -q_1y_0 = -q_1\) |
\(r_1 = ax_{1} + by_{1}\) |
\(r_{2} = b\;mod\;r_1;\quad q_2= \lfloor b/r_1 \rfloor\) |
\(b=q_2r_1+r_2\) |
\(x_2=x_{0} -q_2x_1;\quad y_2=y_{0} -q_2y_1\) |
\(r_2 = ax_{2} + by_{2}\) |
\(r_{3} = r_1\;mod\;r_2;\quad q_3= \lfloor r_1/r_2 \rfloor\) |
\(r_1=q_3r_2+r_3\) |
\(x_3=x_{1} -q_3x_2;\quad y_3=y_{1} -q_3y_2\) |
\(r_3 = ax_{3} + by_{3}\) |
\(\vdots\) |
\(\vdots\) |
\(\vdots\) |
\(\vdots\) |
\(r_{n} = r_{n-2}\;mod\;r_{n-1}\); \(q_n= \lfloor r_{n-2}/r_{n-1} \rfloor\) |
\(r_{n-2}=q_nr_{n-1}+r_n\) |
\(x_n=x_{n-2} -q_nx_{n-1}\); \(y_n=y_{n-2} -q_ny_{n-1}\) |
\(r_n = ax_{n} + by_{n}\) |
\(r_{n+1} = r_{n-1}\;mod\;r_{n} = 0\); \(q_{n+1}= \lfloor r_{n-1}/r_{n} \rfloor\) |
\(r_{n-1}=q_{n+1}r_{n}+0\) |
Lösung
\(d = ggt(a,b) = r_n; x = x_n; y = y_n\)
\(i\) |
\(r_i\) |
\(q_i\) |
\(x_i\) |
\(y_i\) |
|---|---|---|---|---|
-1 |
1759 |
1 |
0 |
|
0 |
550 |
0 |
1 |
|
1 |
109 |
3 |
1 |
-3 |
2 |
5 |
5 |
-5 |
16 |
3 |
4 |
21 |
106 |
-339 |
4 |
1 |
1 |
-111 |
355 |
5 |
0 |
4 |
Resultat: \(d=1; x= -111; y = 355\)
Primzahlen haben als Teiler nur 1 und sich selbst.
Sie können nicht als Produkt von anderen Zahlen geschrieben werden.
Jede ganze Zahl \(a > 1\) kann auf eindeutige Weise faktorisiert werden als: \(a=p_1^{a_1} \times p_2^{a_2} \times \ldots \times p_t^{a_t}\) wobei \(p_1 < p_2 < \ldots < p_t\) Primzahlen sind und wobei jedes \(a_i\) eine positive ganze Zahl ist.
\(a = \displaystyle \prod_{p \in P} p^{a_p}\qquad wenn\; a_p \geq 0\)
Dies ist als Fundamentalsatz der Arithmetik bekannt.
Primzahlen spielen in der Zahlentheorie eine zentrale Rolle. Wir betrachten sie hier aber nur insoweit es für das Verständnis der Kryptographie notwendig ist.
Wichtig in der Public-Key-Kryptographie.
Besagt folgendes:
Wenn \(p\) eine Primzahl und \(a\) eine positive ganze Zahl ist, die nicht durch \(p\) teilbar ist, dann \(a^{p-1} \equiv 1 (mod\;p)\)
Alternative form:
Wenn \(p\) eine Primzahl und \(a\) eine positive ganze Zahl ist, dann ist \(a^p \equiv a(mod\; p)\)
Mit anderen Worten: \(a\) ist kein vielfaches von \(p\).
Herleitung der alternativen Form:
Einige Werte von \(\phi(n)\):
𝜑(n) |
+0 |
+1 |
+2 |
+3 |
+4 |
+5 |
+6 |
+7 |
+8 |
+9 |
0+ |
/ |
1 |
1 |
2 |
2 |
4 |
2 |
6 |
4 |
6 |
10+ |
4 |
10 |
4 |
12 |
6 |
8 |
8 |
16 |
6 |
18 |
20+ |
8 |
12 |
10 |
22 |
8 |
20 |
12 |
18 |
12 |
28 |
30+ |
8 |
30 |
16 |
20 |
16 |
24 |
12 |
36 |
18 |
24 |
40+ |
16 |
40 |
12 |
42 |
20 |
24 |
22 |
46 |
16 |
42 |
50+ |
20 |
32 |
24 |
52 |
18 |
40 |
24 |
36 |
28 |
58 |
60+ |
16 |
60 |
30 |
36 |
32 |
48 |
20 |
66 |
32 |
44 |
70+ |
24 |
70 |
24 |
72 |
36 |
40 |
36 |
60 |
24 |
78 |
80+ |
32 |
54 |
40 |
82 |
24 |
64 |
42 |
56 |
40 |
88 |
90+ |
24 |
72 |
44 |
60 |
46 |
72 |
32 |
96 |
42 |
60 |
besagt, dass für jedes \(a\) und \(n\), die relativ prim sind:
Eine alternative Form ist:
Viele kryptografische Algorithmen erfordern eine oder mehrere sehr große Primzahlen nach dem Zufallsprinzip.
Der Miller-Rabin-Primzahltest ist ein probabilistischer Primzahltest, der schnell und einfach ist.
Hintergrund: Jede positive ungerade ganze Zahl \(n \geq 3\) kann ausgedrückt werden als:
\(n-1 = 2^kq \qquad mit\; k > 0, q\; ungerade\)
TEST(n, k) # n > 2, eine ungerade ganze Zahl,
# die auf Primalität geprüft wird
# k, die Anzahl der Testrunden
let s > 0 and d odd > 0 such that n−1 = pow(2,s)*d
repeat k times:
a ← random(2, n−2)
x ← pow(a,d) mod n
repeat s times:
y ← sqr(x) mod n
if y = 1 and x ≠ 1 and x ≠ n−1 then return “composite”
x ← y
if y ≠ 1 then return “composite”
return “probably prime”Vor 2002 gab es keine bekannte Methode, um für sehr große Zahlen effizient zu beweisen, dass diese Primzahlen sind.
Alle verwendeten Algorithmen lieferten ein probabilistisches Ergebnis.
Im Jahr 2002 entwickelten Agrawal, Kayal und Saxena einen Algorithmus, der „effizient“ bestimmt, ob eine gegebene große Zahl eine Primzahl ist:
Auch bekannt als AKS-Algorithmus.
Er scheint nicht so effizient zu sein wie der Miller-Rabin-Algorithmus.
(Chinese Remainder Theorem (CRT))
Bietet eine Möglichkeit, (potenziell sehr große) Zahlen \(mod\; M\) in Form von Tupeln kleinerer Zahlen zu manipulieren.
Dies kann nützlich sein, wenn \(M\) 150 Ziffern oder mehr hat.
Es ist jedoch notwendig, die Faktorisierung von \(M\) im Voraus zu kennen.
Wurde vermutlich von dem chinesischen Mathematiker Sun-Tsu um 100 n. Chr. entdeckt [1].
Eines der nützlichsten Ergebnisse der Zahlentheorie.
Es besagt, dass es möglich ist, ganze Zahlen in einem bestimmten Bereich aus ihren Residuen modulo einer Menge von paarweise relativ primen Moduli zu rekonstruieren.
Kann auf verschiedene Weise formuliert werden.
Bei RSA rechnen wir mit Zahlen mit weit über 300 Ziffern.
Von der Menge der paarweise relativ primen Moduli interessieren wir uns aber „nur“ für ein paar im Folgenden.
Nehmen wir an, dass die (relativ prim/koprimalen) Faktoren einer Zahl \(x\):
\(m_1 = 2\) und \(m_2 = 5\) sind.
Weiterhin seien die bekannten Reste der Division von \(x\) durch \(m_1\) bzw. \(m_2\): \(a_1 = r_{m_1} = 0\) und \(a_2 = r_{m_2} = 3\) sind.
D. h. \(x\; mod \;2 = 0\) und \(x\; mod\; 5 = 3\); bzw. \(x \equiv 0 (mod\; 2)\) und \(x \equiv 3 (mod\; 5)\).
Da \(x\; mod \;2 = 0\) ist muss \(x\) eine gerade Zahl sein; außerdem ist \(x\; mod\; 5 = 3\).
Die eindeutige Lösung in \(Z_{10}\) ist: \(8\).
Berechnung einer Lösung in \(Z\):
Man könnte auch folgendes Problem versuchen zu lösen: Wir haben x Schokoladentafeln. Wenn wir diese fair auf zwei Personen verteilen, dann haben wir keinen Rest. Wenn wir diese jedoch auf 5 Personen aufteilen, dann haben wir 3 Tafeln übrig. Wieviele Schokoladentafeln haben wir?
(Zur Erinnerung: zwei Zahlen \(x\) und \(y\) sind relativ prim, wenn ihr größter gemeinsamer Teiler 1 ist.)
Der chinesische Restsatz wird häufig für Berechnungen mit großen ganzen Zahlen verwendet, da er es ermöglicht, eine Berechnung, für die man eine Grenze für die Größe des Ergebnisses kennt, durch mehrere ähnliche Berechnungen mit kleinen ganzen Zahlen zu ersetzen.
Das CRT findet in der Public-Key-Kryptographie Einsatz.
Berechne \(5^9\, mod\, 7\) ohne die Zuhilfenahme eines Taschenrechners.
Welche Zahlen sind relativ prim zu \(21\)?
Berechne \(ggt(1037,768)\) mit Hilfe des Euklidischen Algorithmus.
Bestimme das Ergebnis von Euler's Totient Funktion \(\phi\) für den Wert \(37\) ohne das Ergebnis nachzuschlagen.
Überzeugen Sie sich davon, dass der (kleine) Satz von Fermat gilt. Zum Beispiel für die Zahlen: \(a = 9\) und \(p = 7\).
Überzeugen Sie sich davon, dass der Satz von Euler gilt. Zum Beispiel für die Werte \(a=7\) und \(n=9\).
Führen Sie den Miller-Rabin Algorithmus für \(n = 37\) aus.
In einer Tüte sind x Gummibärchen. Wenn Sie diese auf 4 Personen verteilen, dann haben Sie einen Rest von 2, verteilen Sie diese auf 7 Personen, dann haben Sie einen Rest von 3. Wie viele Gummibärchen sind in der Tüte? Wenden Sie den chinesischen Restsatz an.