Kryptologie
Anwendungen der Mathematik
nach Fachgebiet geordnet
a7Hzq .#5r<
kÜ\as TâÆK$
ûj(Ö2 ñw%h:
Úk{4R f~`z8
¤˜Æ+Ô „&¢Dø
Mengenlehre
Alphabete und Sprachen
Mathematisches Modell der Chiffrierung
Rekursionsformeln
Perioden von einfachen Rekursionen
Kategorien
(nicht explizit)
Ähnlichkeit von Chiffren
Algebra
Endliche Körper
Primkörper
XOR-Chiffrierung
, auch
hier
.
Bitblock-Chiffren
Polynome über endlichen Körpern
Algebraische Normalform BOOLEscher Funktionen
, siehe auch
hier
BOOLEsche Abbildungen
[
Beispiele
,
Beispiele
,
Beispiele und Konstruktionsmethoden
]
Potenz-Abbildungen
, auch: Spur einer Körper-Erweiterung, FROBENIUS-Automorphismus, Normalbasen, zugehörige Grundlagen
hier
Körper mit 2
8
Elementen
Zyklizität der multiplikativen Gruppe
Einheitswurzeln
Diskreter Logarithmus
Anwendung
Komplexität
Pseudozufallsgenerator
Quadratwurzeln
Primitivwurzeln
Ringe
Homomorphiesatz
, auch
hier
voller Quotientenring
Halbgruppen
Unter-Halbgruppen endlicher Gruppen
Potenzieren in Halbgruppen
Homomorphismus
Unabhängigkeit der Charaktere
Gruppen
Ordnung und Exponent:
CARMICHAEL-Funktion
RSA-Iteration
Quadratwurzeln
Untergruppen
, auch
hier
Homomorphismus und Homomorphiesatz:
Faktorisierung von RSA-Moduln
RSA-Iteration
diskreter Logarithmus
Gruppen-Operationen, Bahnen und Stabilisatoren
, siehe auch
hier
Gruppenoperationen auf BOOLEschen Abbildungen
Verschiebechiffren
Die Anzahl invertierbarer Matrizen über Restklassenringen
(ohne Beweis)
FEISTEL-Schema
Betriebsarten von Blockchiffren
Permutationsgruppen
Mathematischer Exkurs über Permutationen
Die monoalphabetische Substitution
(symmetrische Gruppe)
Zylinder-Chiffriergeräte
(zyklische Permutationen)
Rotoren
(Konjugation und Zykelzerlegung)
Anzahl von Involutionen
Kryptoanalyse der Enigma
(Zykel-Zerlegung)
Erzeugung der symmetrischen Gruppe
(durch zwei zufällige Elemente, ohne Beweis)
Gerade Permutationen
(in A.7, Beweis des quadratischen Reziprozitätsgesetzes)
Lineare Algebra
Interpolations-Polynome
Binäre Vektorräume, BOOLEsche Linearformen
Lineare Schieberegister
, siehe auch:
statistische Eigenschaften
Vorhersage
lineare Komplexität
Rückkopplungspolynom
BERLEKAMP-MASSEY-Algorithmus
Begleitmatrix
, siehe auch
hier
.
Minimalpolynom und charakteristisches Polynom
Rang
Lineare Algebra über Ringen
Algebraische Kryptoanalyse von Autokey-Chiffren
Permutationsmatrizen
Matrizen über Ringen
Ganzzahlige Elimination
Beispiel
Anwendung
Die HILL-Chiffre
Die Anzahl invertierbarer Matrizen über Restklassenringen
Die Kryptoanalyse der HILL-Chiffre
Allgemeiner linearer Zufallsgenerator
, siehe auch
hier
.
NOETHERsche Moduln
.
nächster Gitterpunkt
(implizit).
Polynome und Gleichungssysteme
Algebraische Kryptoanalyse
Beispiele
Bedingungen
AES
Binäre quadratische Formen
Differenzenfunktion
Quadratische Gleichungen in Charakteristik 2
Anwendungen
Relinearisierung überdefinierter Gleichungssysteme
NEWTONsches Interpolationsverfahren
Diskriminante
primitives Polynom
Beispiel
Zahlentheorie
Primzerlegung elementar
Kasiski-Analyse
Perioden von Schlüsselerzeugern
Primzahlen
Der Primzahlsatz
GERMAIN-Primzahlen
, auch
hier
Primzahltests
Anwendung
, auch
hier
und
hier
Konstruktion zufälliger Primzahlen
Faktorisierung
Faktorisierung und Phi-Funktion
Äquivalente Probleme
BLUM-Zahlen
Anwendung
BBS-Generator
Teilbarkeit und Restklassen
Der EUKLIDische Algorithmus
Anwendung
(Vorhersage von Kongruenzgeneratoren)
MERSENNE-Zahlen
Kongruenz-Division
Anwendung
(ElGamal-Chiffre)
Anwendung
(Vorhersage von Kongruenzgeneratoren) mit
C-Programm
Kleiner Satz von FERMAT
, Anwendungen:
Pseudoprimzahltest
AKS-Primzahltest
Periode von Kongruenzgeneratoren
Chinesischer Restsatz
Multiplikative Gruppe eines Restklassenrings
Anwendung
Struktur
Die EULERsche Phi-Funktion
Komplexität
Anwendung
(Wahrscheinlichkeit der Faktorisierung bei RSA-Analyse)
Anwendung
(Iterationsangriff auf RSA)
Anwendung
(strenger Pseudoprimzahltest)
Die CARMICHAEL-Funktion, Satz von EULER
Komplexität der CARMICHAEL-Funktion
Anwendung
(Iterationsangriff auf RSA)
Anwendung
(Brechen von RSA)
CARMICHAEL-Zahlen
, auch
hier
Geschichte und Periode multiplikativer Kongruenzgeneratoren
HENSEL-Lift
(Erwähnung), auch
hier
Primitive Elemente
Anwendung
(Periode multiplikativer Kongruenzgeneratoren)
Quadratreste
Reziprozitätsgesetz
Anwendung
Quadratwurzeln für
Primmoduln
,
Primpotenz-Moduln
,
zusammengesetzte Moduln
Quadratische Nichtreste
Anwendung
Komplexität
Quadratrest-Vermutung
Anwendung auf Pseudozufallsfolgen
, siehe auch
hier
Additive Zahlentheorie
Additionsketten
FIBONACCI-Zahlen
LUCAS-Folge
Einfache Rekursionsfolgen
Rucksack-Problem
NP-Vollständigkeit
Pseudozufallsgenerator
Exponentialsummen
WALSH- und FOURIER-Transformation
KLOOSTERMAN-Summen
Anwendung
(Analyse der Inversionsabbildung)
Algebraische Geometrie
Elliptische Kurven
Normalformen in Charakteristik 2
Satz von HASSE
Satz von HONDA
Anwendung
(Analyse der Inversionsabbildung)
Anwendung
(Quadratwurzeln in endlichen Körpern, nur erwähnt)
Pseudozufallsgenerator
Polynomgleichungssyteme
Relinearisierung überdefinierter Gleichungssysteme
(nur erwähnt)
Analysis
Elementare Abschätzungen
Die Stirling-Formel
Das Geburtstagsphänomen
Ungleichungen
Ungleichung von HADAMARD
Maßtheorie
Translationsinvariante Maße
Satz von FUBINI
Spezielle Funktionen
RIEMANNsche Zeta-Funktion
elementar
RIEMANNsche Vermutung
L-Funktionen
und erweiterte RIEMANNsche Vermutung
Anwendung
(Quadratwurzeln in endlichen Körpern)
Anwendung
(Suche nach Primitivwurzeln, nach quadratischem Nichtrest)
Wahrscheinlichkeitstheorie
Kombinatorik
Die Stirling-Formel
Das Geburtstagsphänomen
, Anwendungen:
Parallelstellenanalyse nach KASIKI
Blocklänge für Bitblock-Chiffren
Kollisionen beim Cipher Block Chaining
Hash-Funktionen
Anzahl von Involutionen
Korrelation und Autokorrelation BOOLEscher Funktionen
Krumme Funktionen
(bent functions),
Charakterisierung
Ein- und Ausschlussprinzip
(DE MOIVRE)
Stochastik
Gleichverteilte Zufallsvariablen in Gruppen
Formel von Bayes
(Anwendung: Angriff mit bekanntem Geheimtext)
Anwendung:
probabilistischer Primzahltest
Wahrscheinlichkeit einer linearen Relation
Hypergeometrische Verteilung
, Anwendungen:
lineare Kryptoanalyse
Approximation durch Normalverteilung
Erfolgswahrscheinlichkeit der linearen Kryptoanalyse
Piling-Up-Lemma
, Anwendung:
Lineare Kryptoanalyse
Probabilistische Schaltnetze
Run
Autokorrelation
Statistische Eigenschaften von linearen Schieberegistern
Erwartungswert und Varianz der linearen Komplexität
Korrelationsattacken
Sprachen-Statistik
Statistische Geheimtextanalyse
(mit Häufigkeitstabellen)
Zeichen-Koinzidenz
Autokoinzidenz
Koinzidenzindex eines Textes
Stochastische Sprachen
Mittlere Zeichen-Koinzidenz
Koinzidenzindex einer Sprache
Die Formel von Sinkov
Kryptoanalyse von Lauftext-Chiffren
Anagramme
Bigramm-Häufigkeiten
Entropie und Redundanz
Anpassungstests
(nicht explizit)
Kolonnen-Analyse bei polyalphabetischen Chiffren
Koinzidenzindex einer Sprache
Kryptoanalyse von Rotor-Maschinen
Algorithmen
Mustersuche
Zeichenmuster bei monoalphabetischen Chiffren
Mustersuche mit Perl
Brechen der Bazeries-Zylinderchiffrierung
Kryptoanalyse von Rotor-Maschinen
(negative Mustersuche)
Endliche Automaten
Zustände einer Rotormaschine
Steuerlogik von Rotormaschinen
OFB-Modus
Algebraische Algorithmen
Computeralgebra
Der binäre Potenzalgorithmus
Anwendung auf Primzahltest
Der EUKLIDische Algorithmus
Analyse
Ganzzahlige Elimination
Chinesischer Restalgorithmus
NEWTONsches Interpolationsverfahren
Lineare Kongruenzgeneratoren
Mehrstufige Kongruenzgeneratoren
BERLEKAMP-MASSEY-Algorithmus
BBS-Generator
, siehe auch
Mathematica-Programm
BOOLEsche Abbildungen
Rekursive Evaluation und algebraische Normalform
WALSH-Transformation
(auch Berechnung der Faltung)
Berechnung des Differenzenprofils
Analyse BOOLEscher Abbildungen
Lineare Schieberegister
Implementation
Nichtlineare Schieberegister
Nichtlineare Kombinierer
, siehe auch
hier
und
hier
Verschlüsselung
Monoalphabetische Substitution
PORTAs Drehscheiben-Chiffre
FEISTEL-Schema
Probabilistische Algorithmen
Faktorisierung bei bekanntem RSA-Schlüssel
probabilistische Schaltnetze
polynomiale Schaltnetzfamilien
probabilistischer Test
Komplexitätstheorie
Analyse von Algorithmen
Binärer Potenzalgorithmus
EUKLIDischer Algorithmus
Chinesischer Restalgorithmus
Ganzzahlige Elimination
Rekursive Evaluation
WALSH-Transformation und Faltung
Primzahltest
Maschinenmodelle
TURING-Maschinen
, auch
hier
und
hier
Schaltnetz-Komplexität
Vorteilsverdichtung
perfekter Zufallsgenerator
effizientes Vorhersageverfahren
, siehe auch
hier
und
hier
lineare Komplexität
Vergleich mit TURING-Komplexität
TURING-KOLMOGOROV-CHAITIN-Komplexität
Harte und NP-vollständige Probleme
Binäre Polynomgleichungen
Kryptographische Basisfunktionen
NP
, auch
hier
Rucksack-Problem
NP-Vollständigkeit
Pseudozufallsgenerator
Einweg-Funktionen
Informelle Definition
Anwendung
Schwierigkeit
Formale Definition
Autor:
Klaus Pommerening
, 9. Juli 2002; letzte Änderung: 21. Oktober 2008.