Cryptology Mathematical Topics ordered by subject areas

a7Hzq .#5r< kÜ\as TâÆK$ ûj(Ö2 ñw%h: Úk{4R f~`z8 ¤˜Æ+Ô „&¢Dø

Set theory

• Alphabets and languages
  • mathematical model of cryptography
• Category theory (implicit)
  • similarity of ciphers

Algebra

• Finite fields
  • prime fields (follow the link appendix)
  • XOR encryption, see also here.
  • bitblock ciphers
  • finite fields
  • polynomials and polynomial functions
  • Boolean functions and Boolean maps [example: Lucifer, example: DES]
  • Boolean circuits
  • the algebraic normal form
  • Fourier analysis of Boolean maps
  • the field with 256 elements
  • cyclicity of the multiplicative group
  • the structure of the multiplicative group
  • roots of unity, see also here
  • the discrete logarithm
    • application to one-way functions
    • complexity, see also here
    • pseudorandom generator
  • square roots
  • primitive roots
• Rings
  • homomorphy theorem
• Semigroups
  • subsemigroups of finite groups
  • the binary power algorithm
  • homomorphism
• Groups
  • order and exponent:
    • Carmichael function
    • RSA iteration
  • multiple ciphers and group structures
  • subgroups, see also here
  • homomorphisms and homomorphy theorem:
    • factoring RSA modules
    • iterating RSA
    • discrete logarithm
  • group actions, orbits, and stabilizers, see also here
  • shift ciphers
  • the number of invertible matrices over a residue class ring
  • Feistel networks
  • modes of operation of block ciphers
• Permutation groups
  • permutations and Rejewski's theorem
  • the monoalphabetic substitution (symmetric group)
  • cylinder ciphers (cyclic permutations)
  • rotors (conjugation and cycle decomposition)
  • the number of involutions
  • cryptanalysis of the Enigma (cycle decomposition)
  • systems of generators of the symmetric group (generation by two random elements, without proof)
  • even permutations (proof of quadratic reciprocity)
• Linear algebra
  • interpolation polynomials
  • binary vector spaces, Boolean linear forms
  • linear shift registers, see also:
    • statistical properties
    • prediction
    • linear complexity
    • feedback polynomial
    • Berlekamp-Massey algorithm
  • companion matrix, see also here.
  • minimal and characteristic polynomials
  • rank
• Linear algebra over rings
  • algebraic cryptanalysis of autokey ciphers
  • permutation matrices
  • matrices over rings
  • elimination over the integers
    • example
    • application
  • the Hill cipher
  • the number of invertible matrices over a residue class ring
  • cryptanalysis of the Hill cipher
  • general linear random generator, see also here.
  • Noetherian modules.
  • nearest lattice point (implicit).
• Polynomials und systems of polynomial equations
  • algebraic cryptanalysis
    • examples
    • conditions
  • Newton interpolation
  • discriminant
  • primitive polynomial
    • example

Number theory

• Prime decomposition (elementary)
  • Kasiski analysis
  • pairwise coprime periods, see also here
• Prime numbers
  • the prime number theorem
  • Germain primes, see also here
  and here
  • primality tests
  • application, also here and here
  • construction of random primes
• Prime decomposition
  • factoring and phi function
  • equivalent problems
  • Blum integers
    • application
    • the BBS sequence
    • the BBS generator
• Divisibility and residue classes
  • the Euclidean algorithm and congruence division
  • application (prediction of congruence generators), see also here
  • application (ElGamal cipher)
  • Fermat's little theorem, applications:
    • pseudoprime test
    • AKS prime test
    • period of congruence generators
  • chinese reminder theorem
  • multiplicative group of a residue class ring
  • Carmichael function
  • RSA parameters
  • Euler's phi function
    • complexity
    • application (probability of flops in decomposing an RSA module)
    • application (strong pseudoprime test)
    • the AKS primality test
  • Carmichael's function, Euler's theorem
    • complexity of Carmichael's function
    • iteration attack on RSA
    • breaking single ciphertexts
    • Carmichael numbers
    • RSA and pseudoprimes
    • the period of multiplicative congruence generators
  • Hensel lift (mention), see also here
  • primitive elements, see also here
    • period of multiplicative congruence generators
• Quadratic residues
  • quadratic reciprocity law
  • application
  • square roots for prime modules, prime power modules, composite modules
  • quadratic non-residues
    • application
    • complexity
  • quadratic residuosity conjecture
    • application to random generators, see also here
• Additive number theory
  • addition chains
  • Fibonacci numbers
  • Lucas sequence
  • simple recurrence relations
  • knapsack problem
    • NP completeness
    • pseudorandom generator
• Exponential sums
  • Walsh and Fourier transformations

• Elliptic curves
  • application (square roots in finite fields, mention only)
  • pseudorandom generator

Analysis

• Inequalities
  • Stirling's formula
  • the birthday paradox
  • Hadamard's inequality
• Measure theory
  • translation invariant measures
  • Fubini's theorem
• Special functions
  • RIEMANN's zeta function
    • elementary
    • Riemann's hypothesis
  • L-functions and extended Riemann hypothesis
    • square roots in finite fields
    • searching for quadratic nonresidues
    • searching for primitive roots

Probability theory

• Combinatorics
  • Stirling's formula
  • the birthday paradox, applications:
    • Kasiski's search for repetitions
    • block length of bitblock ciphers
    • collisions for cipher block chaining
    • hash functions
  • the number of involutions
  • bent functions,
• Stochastic
  • uniformly distributed random variables in groups
  • Bayes' formula (application: attack with known ciphertext)
    • probabilistic primality test
  • probability of a linear relation
  • hypergeometric distribution, applications:
    • linear cryptanalysis
    • approximation by the normal distribution
    • success probability of linear cryptanalysis
  • Matsui's piling-up lemma, application to linear cryptanalysis
  • probabilistic circuits
  • statistical properties of linear shift registers, runs and autocorrelation
  • the mean value of linear complexity
  • correlation attacks
• Language statistics
  • statistical analysis of ciphertexts (with frequency tables)
  • coincidences of two texts, empirical values
  • autocoincidence of a text
  • the inner coincidence index of a text
  • stochastic languages
  • Sinkov's formula
  • cryptanalysis of running-text ciphers
  • anagramming
  • bigram frequencies
  • entropy and redundancy
• Goodness of fit tests (implicit)
  • column analysis of polyalphabetic ciphers
  • coincidence index of a natural language
  • cryptanalysis of rotor machines

Algorithms

• Pattern recognition
  • pattern search for monoalphabetic ciphers
  • pattern search with Perl
  • breaking the Bazeries cylinder
  • cryptanalysis of Enigma (negative pattern search)
• Finte automata
  • states of a rotor machine
  • the control logic of a rotor machine
  • OFB mode
• Algebraic algorithms
  • computer algebra
  • the binary power algorithm
    • Miller's primality test
  • the Euclidean algorithm and its analysis
  • elimination over the integers
  • the chinese remainder algorithm, relation with Newton interpolation
  • linear congruence generators
  • multistep generators
  • Berlekamp-Massey algorithm
  • BBS generator, with Mathematica code
• BOOLEan maps
  • recursive evaluation and algebraic normal form
  • Walsh transformation (including convolution, linear profile, differential profile)
  • linear shift registers, with Mathematica code
  • nonlinear shift registers
  • nonlinear combiners, see also here and here
• Encryption
  • monoalphabetic substitution
  • Porta's cipher disk
  • Feistel scheme
• Probabilistic algorithms
  • factoring using a known RSA key
  • probabilistic circuits
  • polynomial families of probabilistic circuits
  • probabilistic test for randomness

Complexity theory

• Analysis of algorithms
  • Binary power algorithm
  • Euklidean algorithm
  • chinese remainder algorithm
  • integer elimination
  • recursive evaluation of Boolean functions
  • Walsh transformation and convolution
  • AKS algorithm
• Machine models
  • Turing machines, also here
  • circuit complexity
    • amplification of advantage
    • perfect random generators
  • efficient prediction, see also here and here
  • linear complexity
    • comparision with Turing complexity
  • Turing-Kolmogorov-Chaitin complexity
• Hard and NP-complete problems
  • binary polynomial equations
  • basic cryptographic functions, see also here
  • NP
  • knapsack problem
    • NP-completeness
    • pseudorandom generator
• One-way functions
  • informal definition
  • application
  • difficulty
  • formal definition