RSA

Rivest, Shamir e Adleman.

Public key: (e, N) Private key: (d, N)

CIPHER = MSG^e mod N

MSG = CIPHER^d mod N

Where

0 ≤ MSG < N
p, q are 2 large prime
N = p*q
ϕ(N) = (p-1)(q-1)
1 < e < ϕ(N)
0 ≤ d ≤ N
e*d = 1 mod ϕ(N) 
d = e^-1 mod ϕ(N) 
d = mod_inverse(e, ϕ(N))

Standard e

• decimal = 65537

• bit = 10000000000000001

• hex = 10001

Tools

Tool	Details
RsaCtfTool	RSA attack tool (mainly for ctf)

Factorize the module

One of the best known algorithms is the General Number Field Sieve (GNFS), cado-nfs.

Use Online Database: factor.db e tool YAFU.

Common Prime Attack

N1 = p * q and N2 = p * r

p = GCD(N1, N2)

q = N1 / p and r = N2 / p

Common Modules Attack

Bézout's identity: Let a and b be integers with gcd(a,b) = d. Then there exist two integers x and y such that ax + by = d.

(N, e1) and (N, e2) with gcd(e1, e2) = 1 and same M

gcd, x, y = extended_euclidean(e1, e2) C1^x * C2^y mod n = M

Note! That this can be a problem even with GCD(e1,e2) > 1 but small! (Low exponent Attack)

Oracles

Modulus Recovery

Scenario: We have an oracle that encrypts with a secret key.

From HERE, we can recover the modulus N like this:

• Encrypt x and y

• Based on the fact that the standard e = 65537 and noting that x^e - Enc(x) is a multiple of N: gcd(x^e - Enc(x), y^e - Enc(y)) to find small multiples of N (or even N).

• Repeat with different values ​​if necessary.

def extractmod_eunknown(_encrypt, limit=4):
    try:
        assert limit <= 4
    except AssertionError:
        print("[+] Limit too big!")
        return -1
    try:
        m_list = [2, 3, 5, 7]
        ct_list = [_encrypt(m_list[i]**2) for i in range(limit)]
        ct_list2 = [_encrypt(m_list[i]) for i in range(limit)]
        assert len(ct_list) == len(ct_list2)
        mod_list = [(ct_list2[i]**2 - ct_list[i]) for i in range(limit)]
        _gcd = mod_list[0]
        for i in mod_list:
            _gcd = GCD(_gcd, i)
        return _gcd
    except Exception as ex:
        print("[+] Exception: ", ex)

Homomorphic properties

Scenario: We have an oracle that does not allow decryption of messages containing sensitive information.

• Create C = x^e * c mod N

• Get the decryption of C = P’

• P’ = x * c^e → c^e = P’ * x^-1

Note! Fractions for x mod n “make sense” in modular arithmetic, as long as x is coprime with n.

LSB

Scenario: We have an oracle that performs partial decryption of messages, ex. returns only the Least Significant Bit.

The idea is to perform a “binary search” on the answer using the fact that N is odd. We decrypt 2^e * c → 2m: = 1 → N/2 < m < N (is located in the second half) = 0 → 0 < m < N/2 (is located in the first half) At this point just repeat with 4^e * c, 8^e * c, etc. for 𝑙𝑜𝑔2 𝑁 times (dichotomous search, binary search)

LB = 0 
UB = n
for i in range(int(math.log(n, 2))):   # add to increase precision
    if ( pow(2**i, e, N)*ENCFLAG %2 == 0):
        UB = (UB + LB)/2;
    else:
        LB = (UB + LB)/2;
print((UB + LB)/2)

Padding

• Coppermith's attack against short padding schemes (1997)

• Bleichenbacher's attack against PKCS#1 v1.5 (1998)

• Manger's attack against PKCS#1 v2.0 (2001)

Low Public Exponent Attack

If a small exponent is used (ex. e = 3) and the message is relatively short (ex. < 𝑙𝑜𝑔2 𝑁 / 3) then the modulus has no effect and decrypting the message is trivial.

Common Low Public Exponent Attack

If we have X parts with different RSA keys but the same exponent, and we have the encryption of the same message without padding, then it is possible to trace the message through the Chinese Remainder Theorem and the application of a root. It is important, however, that the parts are equal to the exponent: X = e

(N1, e) (N2, e) (N3, e)

If N1, N2, N3 are coprime, then we can trace m^3 mod N1*N2*N3, and hence m. If, on the other hand, N1, N2, N3 are not coprime, then we can find the gcd between them, break a key, and find the message.

Low Private Exponent Attack

A large value of e (how much N) suggests a low value of d.

Wiener's Attack. Boneh-Durfee Attack.

If 3 * d < N^(1/4) then d can be efficiently recovered. d < N^0.292

The details of this attack are tedious.

Prime close to each other

p = a + b and q = a - b N = (a + b)(a - b) = a^2 * b^2 b^2 = a^2 - N

If b is small enough, we can perform brute force on a or b to get the factorization. This is done through Fermat's factorization method, inplemented in YAFU as the “fermat” function.

import gmpy2

def fermat_factorization(n):
    a = gmpy2.isqrt(n)
    b2 = gmpy2.square(a) - n
    while not gmpy2.is_square(b2):
        a += 1
        b2 = gmpy2.square(a) - n
    p = a + gmpy2.isqrt(b2)
    q = a - gmpy2.isqrt(b2)
    return p, q

Franklin–Reiter related-message attack

This attack works in a scenario where two messages differ only by a known fixed difference and are encrypted using the public key and the same module N.

An example might be using a known padding of a and b

$$cipher\ =\ (a*m+b)^e\ mod\ n$$

Code Attack 1

import sys
sys.path.append("/Library/Frameworks/Python.framework/Versions/3.11/lib/python3.11/site-packages/")
from sage.all import *

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a.monic()

def franklin(n, pad1, pad2, c1, c2, a1, a2):
    R.<X> = PolynomialRing(Zmod(n))
    f1 = (a1*X + pad1)^257 - c1
    f2 = (a2*X + pad2)^257 - c2
    return -gcd(f1, f2).coefficients()[0]

result = franklin(n, b1, b2, ct1, ct2, a1, a2)

Code Attack 2

import sys
sys.path.append("/Library/Frameworks/Python.framework/Versions/3.11/lib/python3.11/site-packages/")
from sage.all import *

def gcd(a, b): 
    while b:
        a, b = b, a % b
    return a.monic()

def franklin(n, pad1, pad2, c1, c2):
    R.<X> = PolynomialRing(Zmod(n))
    f1 = (X + pad1)^3 - c1
    f2 = (X + pad2)^3 - c2
    return -gcd(f1, f2).coefficients()[0]
 
result = franklin(n, b1, b2, ct1, ct2, a1, a2)

Coppersmith attack (partial know message)