RSA

Question 1

Kerkhoff’s Principle

Answer 1

encryption and decryption are known only keys k1, k2, are secret

Question 2

Group Definition

Answer 2

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)

Question 3

Abelian Group

Answer 3

If in addition to being a group o is commutative we call G an abelian group

Question 4

commutative

Answer 4

changing the order does not change the result

Question 5

associative

Answer 5

the grouping of inputs will never change the result

Question 6

Ring

Answer 6

A ring is a structure R= (R, +, . , -(*), 0) such that :

• (R, +, -(*), 0) is abelian group
• . is associative
• distributive laws

Question 7

Field

Answer 7

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

Question 8

Theorem (Extended Euclidian Algorithm)

Answer 8

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)

Question 9

Theorem (Chinese Remainder Theorem (CRT))

Answer 9

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

Question 10

Fermat’s Little Theorem

Answer 10

Let P prime, a arbitrary then a^p = a mod p

Question 11

Fermat’s littler theorem - alternative formulation

Answer 11

p prime, a coprime to p (i.e. no multiple), then a

p−1 ≡ 1 mod p

Question 12

Theorem (Prime-Number-Theorem)

Answer 12

Let π(n) denote the number of primes up to n. Then π(n)∼n/ln(n)
.

Question 13

RSA Set up

Answer 13

• 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)

Question 14

RSA Keys

Answer 14

public key = (n, e)

private key = (n, d), possibly p,q, p(n)

Question 15

RSA Usage

Answer 15

encrypt c = m^e mod n

decrypt m= c^d mod n

Question 16

Modular Exponentiation in RSA

Answer 16

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

Question 17

An addition chain

Answer 17

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

Question 18

Theorem (Downey, Leong, Seth, 1981)

Answer 18

Given a1, . . . , ak , find smallest chain containing them all is
NP-complete.

Question 19

RSA parameter size

Answer 19

• 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

Question 20

coprime

Answer 20

two numbers are co-prime if they no common factor other than 1

Question 21

Partial Key Exposure

Answer 21

Given one entry of the private key (p, q, p(n), d) and the public key,
we can efficiently compute the full private key.

Question 22

Partial key exposure corollary

Answer 22

If d is known, it is not sufficient to just replace e and d.

Question 23

Insecure Special cases of RSA

Answer 23

• 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)

Question 24

Padding

Answer 24

Artificially enlarge message to m0 = Pad (m), such that m0 ≈ n.

Question 25

RSA is multiplicative

Answer 25

If we know enc (m), then we also know enc (x · m) for any x.

Question 26

Theorem (Coppersmith, 1996

Answer 26

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.

Question 27

Coppersmith Corollary (Application in RSA)

Answer 27

If m has (significantly) fewer than log(n)/e bits, and we have any
fixed padding, we can compute m.

Question 28

H˚astad Broadcast

Answer 28

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)

Question 29

Any fixed padding

Answer 29

Any fixed padding scheme becomes dangerous, given enough

messages. Use randomised padding

Question 30

Franklin-Reiter-Related-Message-Attack

Answer 30

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

Question 31

Common Modulus of e

Answer 31

If we have keys (n, e1) and (n, e2) with gcd(e1, e2) = 1, then we can
read any message sent to both.

Question 32

common modulus corolarry

Answer 32

Every key needs is own modulus n , i.e its own primes

Question 33

Fixes for RSA problems

Answer 33

-randomised padding and sufficiently long

- same modulus allowed reading every message
Fix delete second key just use first both can read both messages anyway

Question 34

Theorem (Wiener, 1989) - small private Exponent d

Answer 34

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 .

Question 35

Extension to Wiener’s Attack

Answer 35

via lattice methods breakable for d < n
^0.292
assumed to work up to d

Question 36

Digital Signatures

Answer 36

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

Question 37

Signature Oracle Attack

Answer 37

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

Question 38

Signature Attack Scenarios, What does eve know

Answer 38

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

Question 39

Attack scenarios, what is success?

Answer 39

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

Question 40

Strongest Security for Signatures (GOAL)

Answer 40

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

Question 41

Improved plain RSA signature

Answer 41

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