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.
RSA is multiplicative
If we know enc (m), then we also know enc (x · m) for any x.
Theorem (Coppersmith, 1996
Let f ∈ Z[x] normalised, e = deg f . Then we can compute all x0 ∈ Z with f (x0) ≡ 0 mod n and |x0| ≤ √e n in polynomial time.
Coppersmith Corollary (Application in RSA)
If m has (significantly) fewer than log(n)/e bits, and we have any
fixed padding, we can compute m.
H˚astad Broadcast
If a message is encrypted with the same exponent e but e different
moduli ni
, we can recover the message
(Scenario send an invitation to an event)
Any fixed padding
Any fixed padding scheme becomes dangerous, given enough
messages. Use randomised padding
Franklin-Reiter-Related-Message-Attack
Theorem
If two messages are related via m2 = f (m1) for some known
polynomial f , we often can recover them from ci = me
i mod n. The
time is O((e · deg f )^2)
arithmetic operations.
If f is linear and e = 3 the attack is guaranteed to work
Common Modulus of e
If we have keys (n, e1) and (n, e2) with gcd(e1, e2) = 1, then we can
read any message sent to both.
common modulus corolarry
Every key needs is own modulus n , i.e its own primes
Fixes for RSA problems
-randomised padding and sufficiently long
- same modulus allowed reading every message
Fix delete second key just use first both can read both messages anyway
Theorem (Wiener, 1989) - small private Exponent d
Assume q < p < 2q, e < ϕ(n) and d <1/3n^1/4 . Then we can compute d from (n, e) in O(log(n)^2)arithmetic steps .
Extension to Wiener’s Attack
via lattice methods breakable for d < n
^0.292
assumed to work up to d
Digital Signatures
Authentication: sender only has to convince recipient
Signature: recipient can also convince ”judge“
must depend both on sender and message
if not message: use old signature from other message
if not sender: recipient can forge
Signature Oracle Attack
Assumptions Assume we sign with plain-RSA want to forge signature for message m Have access to online oracle, that signs any m0 6= m (or some restricted subset)
Attack
factor m = m1 . . . mk mod n such that all mi accepted by oracle (not necessarily prime factors)
e.g. pick some m1 < n and put m2 := m · m
−1
1 mod n
get si = md
i mod n for i = 1, . . . ,k have signature s = Q sifor m
Signature Attack Scenarios, What does eve know
No Message, just public key
Signatures, Eve has some message - signature pairs (m_i, s_i), e.g observing traffic
Chosen Message: Eve can choose messages m_i to be signed impersonating authentication server
Attack scenarios, what is success?
Total break: find private key
Universal Forgeability: forge signature for every message
Selective Forgeability: Forge signature m given by Alice
Existential Forgeability: forge signature for m chosen by Eve
Strongest Security for Signatures (GOAL)
EUF_CMA Existential Unforgeability under Chosen message Attack
Eve may request signatures s_i for m-1, … m_k
forges signatures s for some m not in {m_1, m_k}
sEUF-CMA strong EUF-CMA
Eve may request signatures s_i = sign (m_i)
forges pair (m,s ) not in {(m_i, s_i): i =1,…..}
i.e m may be among requested messages but must find different valid signature
Improved plain RSA signature
Alice computes s= sign (m, (n,d))= m^d mod n
send(m,s) to Bob
Bob gets (m’, s’) checks m’=s’^e mod n, if yes he accepts
