Public Key Cryptography Flashcards
Primality Testing, why?
RSA needs big primes
Simple Prime Number Generation
Create random number and check
Efficient Prime Checker
Miller Rabin (Method of Choice) Just as fast as fermat, less error.
______________
Fermat Test
quick O(||n||) operations per run
run t times with different a
correct answer if n prime
may give false answer for composite number
Fermat Test Lemma
if p is prime and gcd(a,p)=1 then aˆ(p-1)=1 (mod p)
Fermat Test
- pick random a< n
- check gcd(a,n)=1
- check wether n satisfies Fermat test lemma.
Carmichael Number
is a composite number that passes the Fermat test for every base a. (561 is the smallest Carmichael number)
Composite Number
A composite number is a positive integer that can be formed by multiplying two smaller positive integers. Equivalently, it is a positive integer that has at least one divisor other than 1 and itself. Every positive integer is composite, prime, or the unit 1, so the composite numbers are exactly the numbers that are not prime and not a unit.
How many Carmichael Numbers exist
infinite (Lemma Alford, Granville, Pomerance, 1994)
Miller-Rabin Test versus Fermat
Miller -rabin : Primality test without the problem of Carmichael numbers (that occur in Fermats test)
Miller-Rabin Test
Idea:
if n prime, then xˆ2=1 mod n only has x = +1
in Fermat aˆ(n-1) is an even power
taking roots we should arrive at -1
for odd powers, we cannot compute root (Find root equivalent to factoring), so we must stop
Miller-Rabin Test Properties
if n not prime <= p(n)/4 choices of a failed
run test t times, takes O(t * ||n||) arithmetic operations
—-> error chance <= (1/4)ˆt
Prime and Prejudice
- usually testing few small numbers suffices
- many implementation fix(ed?) t or bases a_i
- but error chance needs randomness
- in crypto always consider adversarial input
Failure chance against adversary implementations
OpenSSl 1.1.1pre6 fix t=2 for log n >=1300, failure chance 1/16
GNU GMP bases a_i depend deterministically on n, 100% failure for t<=15
LibTomMath t<= 256 use first t primes as bases 100 % failure
AKS Primality Test
“Primes in P” -2002 paper- first provable polynomial-time algorithm
Idea Let a,n in Natural numbers.
We have (x+a)ˆn= xˆn + a in Z[x] if n is prime
reduce this modulo smaller polynomial
takes time O(||n||ˆ(6+e)). —> too long
Sieve of Erathosthenes
- Not a primality test
- Good method to generate all primes p<=n
Function E(n):
create array a_i= 1 for i<=n
i=2
while iˆ2 <=n do
if a_i = 1 then
for j =2 , ...., round_down(n/i) do
a_(i*j) =0
return {p: a_p=1}
_________________
running time O(n log log n) space O(n)
Primality Tests- Overview
Fermat : easy, fast, can have errors, fails for some numbers
Miller -Rabin: Method of choice
as fast as fermat
also one sided error
repeated independent calls reduce error to a direction of 0
in most libraries, but many implementations were (are?) vulnerable to malicious input (prime and prejudice)
AKS: no error, slow
Erathosthenes: no test, but a method to generate all primes.
only recommended for n
Prime Generation
The chance of primality is about 1/log n
improve factor by ruling out small primes as divisors
The Factorisation problem
Task: Given n in Natural number find a non-trivial divisor d of n.
-wether such d exists is primality testing
___________
problem is neither known to be in P nor NP-complete
some variants lie in intersection of NP and coNP
Decision Problem
Given n,l,u in Natural numbers does n have a divisor d with l<=d<=u?
Fermat - Factorisation
Let n=pq, if p, q are close, we can factor n.
General Factorisation
- primality test
- Check whether n is (prime)power
- assume n has two different divisors
- look for any non trivial factor
- recursively yields prime factorisation
Group Bases Cryptography Motivation
- RSA works in Z_n for n=pq
- mathematical problem is e-th root
- now we regard systems that work in arbitray groups but regard cyclic subgroup (g)<=G for some g in G
- the underlying problem is the discrete logarithm problem (DLP)
- framework for cryptosystem until we decide which group comparable to abstract classes in programming
- keywords- Diffe-Hellman, Ellipitic, Curves, DSA , ElGamal
The discrete Logarithm Problem (DLP)
given g, g ˆx= a in G find min x in Natural Numbers
Diffie-Hellman Key exchange
Ideas
- First published idea of public Key cryptography
- no crypto system, but key exchange
- we do not encode messages (yet), but get a common key
- also solves problem from symmetric encryption
Diffie-Hellman Key exchange
Method
Alices chooses a < o(g), computes A= g^a sends A to Bob
Bob chooses b< o(g) computes B= g^b, sends B to alice
Alice computes key K= B^a
Bob computes key K= A^b
------------------------------- works because (g^a)^b= g^(ab)= g^(ba)= (g^b)^a
Elgamal (1985)
secret key: choose random a < o(g)
public key A= g^a
Usage:
Encrypt: choose random b < o(g), send (B, c)= (g^b, m * A^b)
send (B, c)= (g^b, m* A^b)
Decrypt: get (B, c), compute m= c* (B^a) ^-1
__________________________
in fact a special case of Diffie -Hellman
Attack Scenarios on Diffie-Hellman
Discrete Logarithm (DLP) given g, g^x find x secret key
Computational DH (CDH)
given g, g^a, g^b find g^(ab)
find session key
Decisional DH (DDH): given g, g^a, g^b, h decide g^(ab) =h decide which cipher belongs to message
trivially have hierarchy
DDH<=_p CDH <=_p <=_p DLP
Shanks Baby - Step - Giant - Step
Attack on DH-key exchange
let n=o(g), pick step size k secret x has unique representation x - ki+j with j
Pohlig - Hellman Algorithm
attack on diffie Hellman
-improve computation of n= o(g) is known
-solve problem for subgroups of prime power size
-compose with CRT
-let p be largest prime division of n, running time
O(poly (||n||)* square_root(p))
protection:
ensure n has large prime divisor
“safe prime” p: select p such that (p-1)/2 also is prime, if G=Z_p^* then n=p-1 ensured n=2 * p’,
Breaking Prime Powers (Hensel Lifting)
Attack on diffie Hellman
Common example of finite groups
- additive group (Z_n, +)
- multiplicative group (Z_n ^*, *)
- symmetric group S_n (permutations)
- invertible matrices GL(n, p^k)={M in GF(p^k)^(n x m) : det M not equal 0}
Do not yield Significant cryptographic advantage over RSA
Elliptic Curves
y^2 = x^3 -x +1
What can Quantum computers break in crypto?
Can solve both factoring and DLP
Both RSA and DH scheme are broken
Even qauntum computers cannot solve NP-hard problems
Post Quantum Crypto Schemes
base crypto scheme on NP-hard problem
Most common candidates:
- Lattice problems - multivariate polynomials - problem from coding theory
Lattice problem
Given a base of vectors B = {v_1, ….., v_n}, their lattice is
L=span_Z(B) = BZ^n= {sum(a_i* v_i : a_i in Z}) for i=1->n}
Lattice Problem Properties
Bases A,B create same lattice if A=UB for some U in Z^(nxm)
with det U=+1 (U is unimodular)
isomorphism l aprox Z^n for every lattice but isomorphism destroys angles and distances
Shortest Vector Problem (SVP)
A Lattice Problem:
given B, find a vector v in L with ||v|| minimal
NP hard under randomised reduction, with n calls on SVP can solve CVP, short base makes both problems much easier
Closest Vector Problem (CVP)
A Lattice Problem:
given B and u in Z^n find a vector v in L, with ||u-v|| minimal
Shortest Base Problem (SBP)
A Lattice Problem:
given B find base B= {v_1, ….v_n} with BZ^n = BZ^n such that Product ||v_i`|| minimal
NTRU N-th Degree Truncated Polynomial Ring
feasible key size, still unbroken
Post quantum crypto
Multivariate Crypto
post quantum
Given finite field K, polynomial f_i in K[x_1,….x_n] of degree 2
Task: find x in K^n with f_i(x)=0 for all i
can encode SAT, easiest for K = Z_2, via x ∧ y = x · y and
x ∨ y = x + y − xy and auxiliary variables ⇒ NP-hard
Basic Idea
additional secret information allows to solve hard problem
symmetric versus asymmetric crypto
symmetric- both have the same key (secure channel?)
asymmetric- public and private key
