Marcs Notes

MOC - Kryptographie 1

6 min read

MOC - Kryptographie 1

Einführung und klassische Chiffrierverfahren

Verfahren

Modulo

Kapitel 3 - Grundeigenschaften der Ringe und

Landau Symbole

b-adische Darstellung

Integritätsring Modulo Euklidischer Ring Teilbarkeit Primzahl Fundamentalsatz der Arithmetik

Naives Faktorisierungsverfahren

Wir definieren die gemeinsamen Teiler von und als die Menge an Zahlen , die sowohl als auch teilen. Wir sehen daraus sofort, dass die gemeinsamen Teiler von und alle Teiler von sind und mit nur , da man eben nur mit und teilen kann. Wenn eine Primfaktorzerlegung leicht zu berechnen ist, dann lassen sich auch schnell alle gemeinsamen Teiler bestimmen indem man alle möglichen Zerlegungen mit Exponenten macht, die kleiner gleich der Exponenten aus der ursprünglichen Zerlegung sind.

Mit dem Größter Gemeinsamer Teiler könenn wir auch feststellen ob zwei Zahlen Teilerfremd sind.

Genauso lassen sich gemeinsame Vielfache und das Kleinstes Gemeinsames Vielfaches definieren.

Der euklidische Algorithmus kann den ggT bestimmen ohne explizit eine Primfaktorzerlegung berechnen zu müssen. Wir verwenden die Fibonacci-Zahlen um zu zeigen wie die Laufzeit des Algorithmus ist.

Wir wissen, dass die Gleichung mit dem erweitertem euklidischen Algorithmus lösbar ist. Wir wollen diese Aussage nun verallgemeinern indem wir zeigen wie wir Lösungen für die Gleichung finden können.

Wenn und gilt, dann sind die Lösungen der oben genannten Gleichung:

Diese können in Python zum Beispiel mit dem EEA wie folgt berechnet werden:

a, b, c = 12345, 987, 9
ggt, u, v = eea(a, b)
 
if c % ggt == 0:
    for m in range(0, 10):
        x = c / ggt * u + b / ggt * m
        y = c / ggt * v - a / ggt * m
        print(f"{a} * {x} + {b} * {y} = {c}", end="\t -> ")
        print(a * x + b * y == c)```
 
 
[[Kongruenz]] ist ein hilfreiches Konzept in der Zahlentheorie.
 
[[Modulo Invertierbarkeit]]
 
 
[[Eulersche Funktion]]
 
 
Wir wollen nun die [[Modulo Invertierbarkeit]] verallgemeinern, indem wir Lösungen für die Gleichung
$$ax\equiv b \bmod m$$
suchen. Dabei entspricht die Version mit $b=1$ der normalen Invertierbarkeit.
 
Gilt
$$ggT(a,m)|b$$
, dann ist die Gleichung lösbar und
$$x_0=\frac{b}{ggT(a,m)}u$$
erfüllt die Gleichung.
 
Gilt zudem
$$ax_0\equiv b \bmod m$$
, dann gilt außerdem
$$ggT(a,m)|b$$
und es gibt
$$ggT(a,m) \bmod m$$
verschiedene Lösungen der Form
$$x_0+i \frac{m}{\operatorname{ggT}(a, m)} \quad \text { für } \quad i=0, \ldots, \operatorname{ggT}(a, m)-1.$$
 
Eine beispielhafte Implementierung in [[Python]]
 
```python
a = 6
b = 4
m = 10
ggt, u, v = eea(a, m)
 
if b % ggt == 0:
    x0 = b / ggt * u
    if a*x0 % m == b % m:
        for i in range(0, ggt):
            print((x0 + i * m / ggt) % m)

Der Chinesische Restsatz kann verwendet werden um ein Kongruenzgleichungssystem zu lösen.

Algorithmus zur Berechnung der abgerundeten Wurzel

Kapitel 4 - Primzahltests

Wir wollen in diesem Kapitel zwei Grundprobleme lösen:

  • Überprüfe ob eine große Zahl eine Primzahl ist
  • Konstruiere eine Primzahl einer bestimmten Größenordnung (mit bestimmten Eigenschaften)

Wir wollen also zum Beispiel eine Primzahl der Gestalt konstruieren.

Wir verwenden die Eulersche Funktion um die Zahlen in einem Intervall zu bestimmen, die keine kleinen Teiler haben. Damit können wir große Zahlen bestimmen, die so gut wie keine kleinen Teiler haben und somit wahrscheinlich Primzahlen sind. Das heißt uns fehlt jetzt nur noch die Möglichkeit zu bestimmen ob diese Zahlen wirklich alles prim sind.

Für eine Primzahl und ganze Zahlen gilt:

Wir nutzen dieses Lemma um den Kleinen Satz von Fermat zu beweisen. Dieser lässt sich auch aus dem Satz von Euler herleiten.

Mit dem Satz von Euler können wir außedem folgende Folgerung zeigen. Wenn , dann gilt Durch und faches potenzieren von verschwindet also die eulersche Funktion.

Wir wissen jetzt also

und können damit ausschließen, dass eine Primzahl ist, wenn wir ein finden, sodass Um diese Überlegung als Primzahltest auszunutzen müssen wir die Potenz sehr schnell berechnen können. Wir nutzen die binäre Darstellung des Exponenten aus und kommen somit auf die Square-And-Multiply-Methode zum Potenzieren.

Mit dem Fermat-Test lassen sich Primzahlen und Pseudoprimzahlen bestimmen beziehungsweise testen.

Spezialfall: Carmichael-Zahl mit Korselt-Kriterium.

Dieser ungünstige Spezialfall führt uns auf den Miller-Rabin-Primzahltest.

Exkurs: Sieb des Erathosthenes

Sieb des Erathosthenes

Kapitel 5 - Public-Key-Verschlüsselung - RSA

RSA ist ein Verschlüsselungsverfahren bei dem der Schlüsselaustausch sehr sicher ist, da ein Public Key von jedem gesehen werden darf, während der Private Key bei einem selbst bleibt.

Angriffe auf RSA

Der RSA-Exponent ist Teil des Public Key. Wird ein zu kleiner Exponent, von mehreren Personen gleichzeitig verwendet kann man bei Kentniss des Public Key und des Chiffretext diesen mit dem Chinesischen Restsatz entschlüsseln.

Bei drei Personen mit wird der Klartext zum Beispiel so verschlüsselt Man berechnet mit dem chinesischen Restsatz

Und erhält die Ausgangsfolge mit

Algorithmus zur Berechnung der abgerundeten k-ten Wurzel

Fermat-Faktorisierung

Exkurs: Kettenbrüche

Kettenbruch Kettenbruchentwicklung

Näherungsbruch

Approximation irrationaler Zahlen

Kapitel 6 - Die Pollardsche rho-Methode zur Faktorisierung

Pollardsche Rho-Methode

Kapitel 7 - Kryptographische Anwendung diskreter Logarithmen

Wir definieren die Ordnung.

Exkurs zur Funktion

Primitivwurzel

Diskreter Logarithmus

Schlüsselaustausch nach Diffie-Hellmann

ElGamal-Verschlüsselung Massey-Omura-Verschlüsselung

Kapitel 8 - Kryptographische Hashfunktionen

Ein Beispiel einer Hash-Funktion ist SHA-1. Eine typische Attacke auf Hash-Funktionen ist die Geburtstagsattacke, welche die Eigenschaft ausnutzt, dass Hash-Funktionen nie komplett injektiv sind. Message Authentication Codes sind spezielle Hashfunktionen mit denen man die Authentizität einer Nachricht überprüfen kann.

Kapitel 9 - Digitale Signaturen

Eigenschaften, die eine Signatur haben sollte:

  • authentisch
  • fälschungssicher
  • nicht wiederverwendbar
  • Das Dokument ist unveränderbar nach Unterzeichnung
  • Die Unterschrift kann nicht zurückgenommen werden

Allgemeine Verfahren:

Explizite Algorithmen:

Kapitel 10 - Methoden zur Berechnung diskreter Logarithmen

Silver-Pohlig-Hellman-Methode

Baby-Step-Giant-Step-Methode Index-Calculus-Methode

Graphansicht