RSA 2: Attacks

​

Johnny Pesavento

Follow along at tiny.cc/tjcsc.

m

normal message (plaintext)

c

ciphertext

e

public exponent

n

public modulus

d

private key

public key

• n = pq
• tot(n) = λ(n) = lcm(p - 1, q - 1)
• Choose e ∋ 1 < e < λ(n) and gcd(e, λ(n)) = 1
• Choose d ∋ (de) % λ(n) = 1
• c = m^e % n
• m = c^d % n

In theory, m can only be retrieved from c when d is known.

In reality, this is not true.

​

There are several ways to exploit improper RSA techniques.

Weak n attack (factor n)

• The basic security principle behind RSA is that the public cannot know p and q, which are used to compute d
• If n is small, it can easily be factored into p and q, exposing d

Weak n attack (factor n)

• Secure n values have several hundred digits
• Numbers in the 200 digit range take several years to factor
• Quantum computers will be able to do this in seconds
• https://factordb.com

RSA factoring challenge

• In 1991, RSA released several n values and challenged people to factor them
• A 240 digit number released then was only factored 9 days ago (12/2/19), many still remain unfactored

RSA factoring challenge

• In 1991, RSA released several n values and challenged people to factor them
• A 240 digit number released then was only factored 9 days ago (12/2/19), many still remain unfactored

Another vulnerability occurs when a small public exponent is used.

​

The most common example: e = 3.

Recall c = m^e mod n. If n is greater than m^e, then m^e = c because mod n does nothing. Therefore, m = √c .

e

• This attack is called Hastad’s
• 3rd root can be taken easily ✔
• 65537th root cannot ✘

picoCTF example problem:

N: 374159235470172130988938196520880526947952521620932362050308663243595788308583992120881359365258949723819911758198013202644666489247987314025169670926273213367237020188587742716017314320191350666762541039238241984934473188656610615918474673963331992408750047451253205158436452814354564283003696666945950908549197175404580533132142111356931324330631843602412540295482841975783884766801266552337129105407869020730226041538750535628619717708838029286366761470986056335230171148734027536820544543251801093230809186222940806718221638845816521738601843083746103374974120575519418797642878012234163709518203946599836959811

e: 3

​

ciphertext (c): 2205316413931134031046440767620541984801091216351222789180967130585669043554866325905770867150377611820746759815247778516899403229047066700396787852388511389893043279713280998235746440322483431305358901578692935378439077796777060321410661

e seems small enough, we can try eth root ✔

​

​

​

​

​

​

​

​

​

​

e: 3

​

ciphertext (c): 2205316413931134031046440767620541984801091216351222789180967130585669043554866325905770867150377611820746759815247778516899403229047066700396787852388511389893043279713280998235746440322483431305358901578692935378439077796777060321410661

Use a script to compute the root

e: 3

​

ciphertext (c): 2205316413931134031046440767620541984801091216351222789180967130585669043554866325905770867150377611820746759815247778516899403229047066700396787852388511389893043279713280998235746440322483431305358901578692935378439077796777060321410661

​

​

​

​

√c: 13016382529449106065839070830454998857466392684017754632233814825405652260960637

0x7069636F4354467B655F7734795F7430305F736D346C6C5F33343039353235397D

picoCTF{e_w4y_t00_sm4ll_34095259} ✔

e

Prevention strategies

​

• use padding: add filler characters to make m long enough to that m^e > n

​

• use a larger public exponent: e = 65537 may cause slightly slower encryption and use more resources but it is safer

What if m^e is larger than n? Does that make it completely safe?

No. An attacker can still recover m if the same message is encrypted and sent e times with e relatively prime different n values.

Let’s say e = 3.

​

You are able to recover three different c values encrypted with three relatively prime n values that you also know.

What we know

• e (3)
• First transmission: c₁ and n₁
• Second transmission: c₂ and n₂
• Third transmission: c₃ and n₃

​

We want to recover m using this information.

c₁ = m³ mod n₁

c₂ = m³ mod n₂

c₃ = m³ mod n₃

Using the Chinese Remainder Theorem (CRT):

​

c = m³ (mod n₁n₂n₃)

We know m is less than n₁, n₂, and n₃. Therefore, m³ < n₁n₂n₃ and we can use the cube root strategy!

Final CRT equation:

​

m = √c mod n₁n₂n₃

e

Prevention strategies

​

• Change m if you need to send it more than one time

​

• Just use a larger e value

Small d attacks

​

• Wiener’s: if q < p < 2q and d < 1/3n^0.25, then d can be efficiently estimated using continued fractions
• Boneh Durfee: similar to Hastad’s, works when d < n^1/4

Factoring attacks

​

• Elliptic-curve factoring: best when n is less than 60 digits
• Mersenne primes factoring (primes with form 2^k - 1, efficient but common)
• Londahl’s: p and q are close (close to square root of n)

RsaCtfTool

​

• Popular python script that automatically determines the best attack given RSA components
• https://github.com/Ganapati/RsaCtfTool
• Usage: RsaCtfTool.py -n n -e e --uncipher c

Our winter competition has begun

​

• https://csc-ctf.sites.tjhsst.edu
• Must sign up with @tjhsst.edu email
• Prizes for 1st-3rd place
• Sign up for our party next week now on ION so you don’t miss out
• Competition participation is required if you want pizza
• Competition ends at 2:25PM next Wednesday (12/18/19)
• Practice lecture problems are at https://tiny.cc/tjcsc