Math and theory
Contents
Math
Branches in mathematics
- Abstract algebra (how to specify sets, groups, rings, fields, how to compute with their elements)
- Abstract Algebra - great overview + Sage exercises, covering:
- The Integers
- Groups
- Cyclic Groups
- Permutation Groups
- Cosets and Lagrange’s Theorem
- Introduction to Cryptography
- Algebraic Coding Theory
- Isomorphisms
- Normal Subgroups and Factor Groups
- Homomorphisms
- Matrix Groups and Symmetry
- The Structure of Groups
- Group Actions
- The Sylow Theorems
- Rings
- Polynomials
- Integral Domains
- Lattices and Boolean Algebras
- Vector Spaces
- Fields
- Finite Fields
- Galois Theory
Recall:
- Sets and cosets
- Groups
- Group G - set with 1 binary operation * such that following properties holds: * is associative, there is an identity element, each element has an inverse element
- If a * b = b * a then the group is called abelian or commutative
- If there exists a generator g such that for any element b there is an integer j such that gj = b then the group is cyclic
- Ring R - set with 2 binary operations (+ and *) such that R is abelian with respect to +, * is associative, and + and * are distributive
- If there is a multiplicative identity the ring is called a ring with identity
- A ring is called commutative if * is commutative
- A ring is called an integral domain if it is a commutative ring with identiy e ¬ = 0 in which ab=0 implies a=0 or b=0
- A ring is called a diision ring if the nonzero elemnts form a group under *
- Four common rings: the integers Zn, the rationals, the reals, the complex numbers
- A commutative division ring is called a field
- Fields
- Set F with 2 binary operations (+ and *)
- Has two distinguished elements: zero element 0 and identity element e such that e ¬ = 0
- Is an abelian group with regard to + with 0 as identity element
- The elements of F that are ¬ = 0 form an abelian group with regard to *, with e as identity element
- The distributive laws hold on + and *
- Zp is a finite field, Zp = {0,1,...,p-1}
Hard problems and complexity
Hard problems in cryptography
Hidden supgroup problem
The hidden subgroup problem (HSP) is a topic of research in mathematics and theoretical computer science.
The framework captures problems like factoring, discrete logarithm, graph isomorphism, and the shortest vector problem.
This makes it especially important in the theory of quantum computing because Shor's quantum algorithm for factoring is
essentially equivalent to the hidden subgroup problem for finite Abelian groups, while the other problems correspond
to finite groups that are not Abelian.
Factorisation
- NFS, role of Legendre and Jacobi
- New approaches from PQ such as Shor
Discrete Logarithm Problem
In any group G, powers bk can be defined for all integers k, and the discrete logarithm logb a
is an integer k such that bk = a.
Diffie-Hellman
The Diffie–Hellman problem is related to the DLP. The DH problem is stated informally as follows:
Given an element g and the values of gx and gy, what is the value of gxy?
- Decisional DH - Wikipedia
- The DDH assumption states that, given ga and gb for uniformly and independently chosen a, b in Zq,
the value gab "looks like" a random element in G.
- The DDH assumption is related to the discrete log assumption.
If it were possible to efficiently compute discrete logs in G, then the DDH assumption would not hold in G.
- Computational DH - Wikipedia
- The CDH assumption states that, given ga and gb for a randomly chosen generator g and random
a, b in { 0 , … , q − 1 } it is computationally intractable to compute the value gxy.
Lattices
It is e.g. the basis of the lattice-based public-key encryption scheme, NTRU.
PQ - Post Quantum
Shor and Grover
- Shor's algorithm - a polynomial-time quantum computer algorithm for integer factorization
- Grover's algorithm - a quantum algorithm that finds with high probability the unique input to a black box function that produces a particular output value
ETSI
Techniques
- SageMath - a computer algebra system with features covering many aspects of mathematics, including algebra, combinatorics, graph theory, numerical analysis, number theory, calculus and statistics
- Mission: Creating a viable free open source alternative to Magma, Maple, Mathematica and Matlab.
- Free open-source mathematics software building on NumPy, SciPy, matplotlib, Sympy, Maxima, GAP, FLINT, R and more.
- Access through a common, Python-based language or directly via interfaces or wrappers.
- DE - TU Darmstadt - Lindner - links to Jalgebra
- Project Everest - Microsoft, INREA, CMU
- aims to build and deploy a verified HTTPS stack
- formally verified implementation of components in HTTPS ecosystem, including TLS and
AES, SHA2 and X25519 (DH function on Curve25519)
- Everest consists of:
- F*- a verification language for effectful programs
- By default F* only verifies the input code, it does not execute it.
To execute F* code one needs to extract it to OCaml or F# and then compile it using the OCaml or F# compiler
- miTLS, reference implementation of the TLS protocol in F*
- KreMLin, a compiler from a subset of F* to C
- HACL*, a verified library of cryptographic primitives written in F*
- Vale, a domain-specific language for verified cryptographic primitives in assembly
- EverCrypt, a verified crypto provider that combines HACL* and Vale via an agile, multi-platform,
self-configuring cryptographic API
- EverParse, a library and tool to automatically generate verified parsers and serializers for binary data formats
- => When combined together, the projects above generate a mixture of C and assembly code that implements TLS 1.3,
with proofs of safety, correctness, security and various forms of side-channel resistance
Concepts
Models of computation and proof of security
Cryptographic schemes are usually based on complexity assumptions, which state that some problems,
such as factorisation, cannot be solved in polynomial time.
Schemes which can be proven secure using only complexity assumptions are said to be secure in the standard model.
Security proofs are notoriously difficult to achieve in the standard model, so in many proofs,
cryptographic primitives are replaced by idealized versions.
The most common example of this technique, known as the random oracle model, involves replacing a cryptographic hash function
with a genuinely random function.
Another example is the generic group model where the adversary is given access
to a randomly chosen encoding of a group, instead of the finite field or elliptic curve groups used in practice.
Standard model
- The Standard model
- The model of computation in which the adversary is only limited by the amount of time and computational power
available.
- This is challenged by PQ computing.
Random oracle model
- The Random Oracle model - Wikipedia
- A random oracle is an oracle (a theoretical black box) that responds to every unique query with a (truly) random response chosen uniformly from its output domain.
If a query is repeated, it responds the same way every time that query is submitted.
- Random Oracles are practical - M. Bellare and P. Rogaway - 1993
Cryptographic strength
The cryptographic strength is usually measured in bits, corresponding to an upper bound for operations needed for an
attack against the signature algorithm.
E.g. breaking a signature algorithm means, that given the public verification key and some signatures for some data, the
attacker can create a signature for another document without the signature creation data.
If the attack requires 2n operations, then the cryptographic strength is denoted by n.
Cryptanalysis
Other
- EFF - 1999-01-19 56 bit DES crack in 22 1/4 h.
- Copacobana - Cost-Optimized Parallel COde Breaker for e.g. DES (FPGA-based machine)
- CWI - Lenstra, Te Riel, Montgomery - cracking RSA-155/512 bits
- MD5Crack - Gregory Duchemin
- DeCSS - decryption of DVD CSS - Dave Touretzky - Carnegie Mellon University - note that originally this seems to have been done by MoRE, a Norwegian group - Masters of Reverse Engineering