RSA Flashcards
Kerkhoff’s Principle
encryption and decryption are known only keys k1, k2, are secret
Group Definition
A group is strucute G= (G, o, *^-1, 1) such that:
- o is associative
- For all g in G. 1 o g = g=g o 1 (neutral element)
- for all g in G. g o g^-1 = 1 = g^-1 (inverse)
Abelian Group
If in addition to being a group o is commutative we call G an abelian group
commutative
changing the order does not change the result
associative
the grouping of inputs will never change the result
Ring
A ring is a structure R= (R, +, . , -(*), 0) such that :
- (R, +, -(*), 0) is abelian group
- . is associative
- distributive laws
Field
a field is a structure K= (K, +, . , -(x), (x)^-1, 0, 1) such that:
- (K, +, . , -(x), (x)^-1, 0, 1) is a commutative ring with 1
- (K\ {0}, . , (*)^-1, 1) is a group
Theorem (Extended Euclidian Algorithm)
For all a, b ∈ Z there are λ, µ ∈ Z such that
λa + µb = gcd(a, b)
def EEA(a,b):
if b == 0: return (a,1,0)
d,s,t = EEA(b, a % b)
return (d, t, s - (a//b) * t)
Theorem (Chinese Remainder Theorem (CRT))
Let ni ∈ Z (pairwise) coprime, ai ∈ Z arbitrary for i = 1, . . . , k. Then the system ai ≡ x mod ni i = 1, . . . , k has a unique solution 0 ≤ x < Sum n_i
Fermat’s Little Theorem
Let P prime, a arbitrary then a^p = a mod p
Fermat’s littler theorem - alternative formulation
p prime, a coprime to p (i.e. no multiple), then a
p−1 ≡ 1 mod p
Theorem (Prime-Number-Theorem)
Let π(n) denote the number of primes up to n. Then π(n)∼n/ln(n)
.
RSA Set up
- p,q primes
- n= p* q => p(n)= (p-1) (q-1)
- choose e coprime to p(n)
- d= e^-1 mod p(n) (extended Euclidean Algorithm)
RSA Keys
public key = (n, e)
private key = (n, d), possibly p,q, p(n)
RSA Usage
encrypt c = m^e mod n
decrypt m= c^d mod n
Modular Exponentiation in RSA
Need to compute a b mod n Naive approach -b multiplications, one modulo -huge intermediate results, size b · log a instead of log n
speed up with square and multiply algorithm
An addition chain
An addition chain for integer n of length l is a sequence
1 = a0, a1, . . . , al = n
such that every entry is a sum of 2 previous ones
Theorem (Downey, Leong, Seth, 1981)
Given a1, . . . , ak , find smallest chain containing them all is
NP-complete.
RSA parameter size
- strength of key given in bit size of n
- ssh-keygen currently has default 2048
- secure key should have 4096 more threatened by quantum Computers, than classical factoring
- p,q should have same bitlength
- e often equals 65537
coprime
two numbers are co-prime if they no common factor other than 1
Partial Key Exposure
Given one entry of the private key (p, q, p(n), d) and the public key,
we can efficiently compute the full private key.
Partial key exposure corollary
If d is known, it is not sufficient to just replace e and d.
Insecure Special cases of RSA
- e is small: find m
- same n but different e : find m
- m is very small: find m
- d is small: find d, thus everything
- p,q are too close: factor n, thus everything
Standard to avoid all of these
Public Key Cryptography Standard (PKCS)
Padding
Artificially enlarge message to m0 = Pad (m), such that m0 ≈ n.
