public key cryptography Flashcards
public key crypto system
for each k, e_k is the inverse of d_k
e_k(x) and d_k(y) are easy to compute
computationally infeasible to derive d_k from e_k
feasible to compute e_k and d_k from k
one-way function
easy to compute f(x)
but computationally infeasible to find x from y
trap-door one way function
given trapdoor Information it becomes feasible
Euler phi-function
φ(n)=number of integers less than n and relatively prime to n
Fermat’s little theorem
suppose p prime and b in invertible in Zp then b^p=b mod p
Euler
for all b in Zn*, b^φ(n)=1 mod n
public key (RSA)
(n,b) where b is the encryption exponent
private key (RSA)
(p,q,a) where a is the decryption exponent
basic method for generating big primes
generate a large number and test for primality
RSA problem
recover x given x^b mod n, n and b
splitting
find n=ab where a,b are non-trivial factors of n
strong prime
p-1 has a large prime factor, say r
p+1 has a large prime factor
r-1 has a large prime factor
when do strong primes offer no protection?
Elliptic curve method
x is B-smooth
all prime factors of x are <=B
factor base
set of primes below some bound B
framework for congruent squares algorithm
select the factor base
collect relations between elements of the factor base producing squares
find dependencies: reduce exponents modulo 2 and use linear algebra to find a dependency modulo 2
Dixon’s random squares
select z at random
Is RSA semantically secure?
No, because the attacker can distinguish cipher texts
how is decryption if we use small private exponent?
use CRT
broadcast attack
Oscar is an external attacker. He doesn’t have a key
Coppersmith’s theorem
let p be monic polynomial of degree d in one variable modulo n (of unknown factorisation)
one can find in time polynomial (long,d) all integers x0 such that p(x0)=0 mod n and |x0|<=n^{1/d}
coppersmith’s short padding
let n be l bits long and x be at most l-[l/b^2] bits
if the message is sent twice with different random paddings of length less than [l/b^2] then an attacker can efficiently recover x given only the ciphertexts
cryptographic primitive
basic RSA
protocols
built of many primitives to achieve secure communication (perhaps data integrity too)
