22-11-04-RSA

JUST conclude the attacks about RSA.

Make a record for myself.

RSA

Algorithm

• produce large primes $p$ and $q$
• calculate $n=p\times q$
• use Euler’s totient function to get $\phi (n)=(p-1)\times (q-1)$, in code we usually use $N$ or $phi$
• define $e$ which satisfies the condition that $gcd(e,\phi (n))=1$, and the $e$ is between 1 and $\phi (n)$
• calculate $d$ and the $d$ comes from $de\equiv 1\mathrm{mod}\phi (n)$
• encrypt: $c\equiv m^e\mathrm{mod}n$
• decrypt: $m\equiv c^d\mathrm{mod}n$
• PUBLICKEY: PU{e, n}
• PRIVATEKEY: PR{p, q, d}

Proof

$$m\equiv c^d\mathrm{mod}n\equiv m^{de}\mathrm{mod}n\equiv m^{k\phi (n)+1}\mathrm{mod}n\equiv m\mathrm{mod}n$$

use the Fermat’s little theorem deduce:
$$m^n\equiv m\mathrm{mod}n$$

$$m^{n-1}\equiv m^{\phi (n)}\equiv 1\mathrm{mod}n$$

$m$, $n$ are relatively-prime

the $m^{k\phi (n)}$:
$$m^{k\phi (n)}\equiv 1\mathrm{mod}n$$

$$⟹m^{k\phi (n)+1}\equiv m\mathrm{mod}n$$

$m$,$n$ not relatively-prime

preparation:
$$gcd(m,n)\ne 1$$
$$n=p\times q$$

$$⟹n=kp$$

$$k,parerelatively-prime$$

also Fermat’s little theorem:
$$(kp{)}^{q-1}\equiv 1\mathrm{mod}q$$
based on the properties of con-gruences multiplication property:
$$(kp{)}^{(p-1)\times (q-1)\times k}(kp)\equiv (kp)\mathrm{mod}q$$
substitute the $\phi (n)$ and $de\equiv 1\mathrm{mod}\phi (n)$:
$$\phi (n)=(p-1)\times (q-1)$$
$$de=1+k\times \phi (n)$$

$$⟹(kp{)}^{de}\equiv (kp)\mathrm{mod}q$$

$$⟹(kp{)}^{de}=kp+tq$$

thus, $tq|kq$ and $t|p$ for $q$ is prime:
$$assume:t=t\times p$$
$$(kp{)}^{de}=tq+kp=t\times p\times q+k\times p=tn+kp$$

$$(kp{)}^{de}=m+tn\equiv m\mathrm{mod}n$$

proved.

Preparation

• gmpy2
• python3.7+
• pycharm
• sagemath

NC CHALLENGE

Before nc real connection, you need to receive the challenge and make a solution about it.

# 1
import hashlib
import itertools
from string import digits, ascii_letters, punctuation
alpha_bet = digits+ascii_letters+punctuation
strlist = itertools.product(alpha_bet, repeat=4)
sha256 = '9a579edf6cdd9ed39efc1ccc754e7bb15d52e3d9cabcd66c7042fa1a59fc2836'
tail = 'j60BfGY9sSnkMi9H'
xxxx = ''
for i in strlist:
    data = i[0]+i[1]+i[2]+i[3]
    data_sha = hashlib.sha256((data+str(tail)).encode('utf-8')).hexdigest()
    if(data_sha == sha256):
        xxxx = data
        break
print(xxxx)

# 2
import codecs
import itertools
import hashlib
# 爆破sha256+hex
def phase1(pre, target):
    pre = codecs.decode(pre.encode(), 'hex')
    for x in itertools.product(range(256), repeat=3):
        skr = pre + b''.join([t.to_bytes(1, 'big') for t in x])
        if hashlib.sha256(skr).hexdigest() == target:
            print(f'find {skr}')
            return codecs.encode(skr, 'hex').decode()

change sha256/tail and crack xxxx

Or use the connecting function:

# 3
from pwn import *
from Crypto.Util.number import *
import gmpy2
import string
import hashlib
table = string.ascii_letters + string.digits
r = remote('1.14.71.254',28826)
def proof():
    r.recvuntil(b'sha256(XXXX')
    line = r.recvline()[:-1].decode()
    print(line)
    tmp = line[line.find('+') + 1:line.find(')')]
    print(tmp)
    aim = line[line.find('== ') + 3:]
    print(aim)
    for i in table:
        for j in table:
            for k in table:
                for l in table:
                    ans = i + j + k + l
                    if hashlib.sha256((ans + tmp).encode()).hexdigest() == aim:
                        print(ans)
                        r.recvuntil(b'Give me XXXX: ')
                        r.sendline(ans.encode())
                        return
proof()
r.interactive()

MODULUS FACTORIZATION

Or we can call it Original_RSA.

The main target in RSA problems is to factorize n to p and q.

Here is the code of Original_RSA which is the basic attack among RSA attacks.

def Original_RSA(p, q, e, c, n):
    N = (p-1)*(q-1)    
    d = int(gmpy2.invert(e,N))  # mpz() may run error, convert to int()
    # d = gmpy2.invert(e,N)
    m = gmpy2.powmod(c,d,n)
    return m

BUT HOW TO FACTORIZE THE $n$?

It is the significant question. Follows are some solutions that I met.

Factorize

factordb

factordb.com

A database contains many $n$ that has been factorized.

yafu-x64

The $p$,$q$ differ very well or a little or $p$,$q$ are smooth and produced by $\rho -1$or $\rho +1$.

usage

• yafu-x64 factor()

• yafu-x64 factor(@) -batchfile [filename] !remember the number saved in file and need a \n

msieve153

Which is similar to yafu-x64

RSAConverter

Based on CRT.

usage

• $n$, $d$ convert to hex and delete 0x

• $e$ convert to hex and delete x

fermath factorization

p,q have a little difference

• p or q created by next_prime()
  • find the Reference Substance n_2 which can be produced by iroot(n, 2)[0]
  • p and q are primes, and $p<n_2<q$
  • we can get $q$ by next_prime(n_2)
  • and p = n // q
• p and q are similar but not neighbors
  • also find the n_2
  • with n_2 as a center, step size 1 and right
  • if find $p$ and $q$ satisfied the condition, and we get the true $p$ and $q$

# Fermat Factorization 2
def Fermat_Factor(n):
    """
    Fermat Factorization
    conditon:
        1. n is odd
        2. satisfy the equation (p-q)(p+q)
    :param n:
    :return: result
    """
    a = gmpy2.iroot(n, 2)[0]

    while True:
        a += 1
        b_2 = a*a - n
        b, index = gmpy2.iroot(b_2, 2)
        if index == True:
            result = [int(a + b), int(a - b)]
            break
    return result

backdoor

https://asecuritysite.com/encryption/copper

$$Prime=k\times M+{65537}^a\mathrm{mod}M$$

def RSA_Backdoor(n):
    """
    primes list can produced by primes_first_n() in sagemath
    reference:[GKCTF2020]Backdoor

    :param n:modulo
    :return:p,q
    """
    val = 39 # edit
    M = 1
    primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103,
              107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223,
              227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347,
              349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463,
              467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607,
              613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743,
              751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883,
              887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031,
              1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151,
              1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279,
              1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423,
              1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523,
              1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627,
              1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777,
              1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907,
              1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039,
              2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161,
              2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309,
              2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423,
              2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591,
              2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707,
              2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833,
              2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969,
              2971, 2999]
    # print(primes)

    for i in range(0, val):
        M = M * primes[i]

    for a in range(1, 20):
        for k in range(50):
            p = gmpy2.mpz(k * M + (pow(65537, a, M)))
            if gmpy2.is_prime(p):
                q = gmpy2.mpz(n // p)
                if gmpy2.is_prime(q):
                    return p, q
                    # print(q)

xor factorization

GitHub - sliedes/xor_factor: Given p xor q and n=p*q for two unknown primes p and q, factor n and output p and q.

usage

xor_factor.py n x

pollard’s p-1

This part only give the solution.

Detailed introduction needs time to be written.

$$(p-1)|B!$$

$$2^{B!}\equiv 1\mathrm{mod}p$$

from primefac import pollard_pm1
p = pollard_pm1(n)
# May it cost a lot of time, just wait. 

williams’s p+1

As above.

from primefac import williams_pp1
p = williams_pp1(n)
# Similar to Pollard's p-1

known phi

from math import gcd
from math import isqrt
from random import randrange

from sage.all import is_prime


def factorize(N, phi):
    """
    Recovers the prime factors from a modulus if Euler's totient is known.
    This method only works for a modulus consisting of 2 primes!
    :param N: the modulus
    :param phi: Euler's totient, the order of the multiplicative group modulo N
    :return: a tuple containing the prime factors, or None if the factors were not found
    """
    s = N + 1 - phi
    d = s ** 2 - 4 * N
    p = int(s - isqrt(d)) // 2
    q = int(s + isqrt(d)) // 2
    return p, q


def factorize_multi_prime(N, phi):
    """
    Recovers the prime factors from a modulus if Euler's totient is known.
    This method works for a modulus consisting of any number of primes, but is considerably be slower than factorize.
    More information: Hinek M. J., Low M. K., Teske E., "On Some Attacks on Multi-prime RSA" (Section 3)
    :param N: the modulus
    :param phi: Euler's totient, the order of the multiplicative group modulo N
    :return: a tuple containing the prime factors
    """
    prime_factors = set()
    factors = [N]
    while len(factors) > 0:
        # Element to factorize.
        N = factors[0]

        w = randrange(2, N - 1)
        i = 1
        while phi % (2 ** i) == 0:
            sqrt_1 = pow(w, phi // (2 ** i), N)
            if sqrt_1 > 1 and sqrt_1 != N - 1:
                # We can remove the element to factorize now, because we have a factorization.
                factors = factors[1:]

                p = gcd(N, sqrt_1 + 1)
                q = N // p

                if is_prime(p):
                    prime_factors.add(p)
                elif p > 1:
                    factors.append(p)

                if is_prime(q):
                    prime_factors.add(q)
                elif q > 1:
                    factors.append(q)

                # Continue in the outer loop
                break

            i += 1

    return tuple(prime_factors)

sage

$n=a^2+b^2$

two_squares(n)

$n=a^2+b^2+c^2$

three_squares(n)

Quadratic Sieve

qsieve()

find prime factors

• elliptic curve factorize

ecm()

• just prime factorize

prime_divisors()

Others

整数因子分解 - maTHμ - 计算机代数系统 (mathmu.github.io)

• lenstra elliptic curve factorization
• birthday attack
• ……

SAME MOD

The attack is based on the Homomorphic Encryption and Extended Euclidean Algorithm.

Usually, we have two pairs of $c$ and $e$ and both them have the same modulo.

*REMEMBER that the encrypted m should be same. *

$$c_1\equiv m^{e_1}\mathrm{mod}n$$

$$c_2\equiv m^{e_2}\mathrm{mod}n$$

Use Extended Euclidean Algorithm, the eqution follows:
$$r\times e_1+s\times e_2=gcd(e1,e2)$$
Based on the Multiplicative homomorphism, and we can make a conversion.

$$c_1^s\times c_2^r\equiv m^{r\times e_1+s\times e_2}\mathrm{mod}n$$

$e_1$, $e_2$ are primes

If $e_1$ and $e_2$ are primes, $gcd(e_1,e_2)=1$, and we can substitute the integer into the equation above.
$$c_1^s\times c_2^r\equiv m\mathrm{mod}n$$

$e_1$, $e_2$ not primes

1. $gcd(e1,e2)$ and $\phi (n)$ are not relatively-prime.

May use Rabin Algorithm to solve this problem. For another word, the problem converts to the Low_Exponent_e2 problem.

2. $gcd(e1,e2)$ and $\phi (n)$ are relatively-prime.

Thus, just use iroot(m, g) and we get the true $m$. REMEMBER that before the calculation we ought to % n first.

def Same_Mod_RSA(e1, e2, c1, c2, n):
    g, r, s = gmpy2.gcdext(e1, e2)
    if r < 0:
        r = -r
        c1 = gmpy2.invert(c1, n)
    elif s < 0:
        s = -s
        c2 = gmpy2.invert(c2, n)
    m = gmpy2.powmod(c1, r, n)*gmpy2.powmod(c2, s, n) % n # keypoint
    if g == 1:
        return m
    else:
        return gmpy2.iroot(m, g)[0]

The code ignores that gcd($e_1$, $e_2$) and $\phi (n)$ are not relatively-prime.

Multiplicative congruence

We use multiplicative congruence to simplify our calculation.

It usually gives us one same modulo $n$ and two more pairs of $c$, $e$.

FOR EXAMPLE:

N = 
c1 = 
e1 = 
c2 = 
e2 = 
c3 = 
e3 = 

The deduction is as follows:
$$g_1\equiv e_1\cdot r_1+e_2\cdot s_1$$
$$g_2\equiv g_1\cdot r_2+e_3\cdot s_2$$

The three public keys satisfy $gcd(e_1,e_2,e_3)=1$, so $g_2=1$.

We can get the equation that $1\equiv (e_1\cdot r_1+e_2\cdot s_1)\cdot r_2+e_3\cdot s_2$.

Expand it:
$$1\equiv (r_2\cdot r_1)\cdot e_1+(s_1\cdot r_2)\cdot e_2+s_2\cdot e_3$$

$$c_1\equiv m^{e_1}\mathrm{mod}n$$

$$c_2\equiv m^{e_2}\mathrm{mod}n$$

$$c_3\equiv m^{e_3}\mathrm{mod}n$$

$$⟹c_1^{r_2\cdot r_1}\cdot c_2^{s_1\cdot r_2}\cdot c_3^{s_2}\equiv m\mathrm{mod}n$$

……
from gmpy2 import *
g1, r1, s1 = gcdext(e1, e2)
g2, r2, s2 = gcdext(g1, e3)
# print(g2)
m = powmod(c1, r2*r1, n)*powmod(c2, s1*r2, n)*powmod(c3, s2, n) % n # keypoint

MODULO RELATED

$n_1$ and $n_2$ are relatively-primes

When they encrypt the same message $m$，it exists THE MODULO RELATED ATTACK.

Deduction
$$n_1=p\times q_1$$

$$n_2=p\times q_2$$

Ignore the possibility that $1\times n_1$ and $1\times n_2$
$$p=gcd(n_1,n_2)$$

$$q_1=n_1//p$$

$$q_2=n_2//p$$

$p$ can be calculated with function gcd() , and use division to solve out the $q_1$ and $q_2$.

The problem converts to the Original_RSA.

Solution

def RSA_NPM(n1,n2,e,c1):
    p = gmpy2.gcd(n1,n2)
    q1 = n1//p  # keypoint
    N = (p-1)*(q1-1)
    d = gmpy2.invert(e,int(N))
    m = gmpy2.powmod(c1,d,n1)
    return m

Remember that $n_1$ and $c_1$ are one-to-one!

LOW EXPONENT

e = 3

or one-to-one function

JUST Bruck.

1. $m^e<n$, means that $k=0$ in code below
2. $m^e>n$

def RSA_Low_Exponent_e3(c,e,n):
    k = 0 # one
    while 1: # the other
        cm = c + n*k
        m, index = gmpy2.iroot(cm, e)
        if index == True:
            return m
        k += 1

$e$ and $\phi (n)$ are not relatively-prime

e = 2

Rabin

PART1 $m_p$ and $m_q$

Split into two scenarios for discussion:

1. $p$ and $q$ are satisfied $p\equiv q\equiv 3\mathrm{mod}4$.

$$m_p\equiv c^{\frac{1}{4}(p+1)}\mathrm{mod}p$$

$$m_q\equiv c^{\frac{1}{4}(q+1)}\mathrm{mod}q$$

2. $p$ and $q$ are different to 1.

$$m_p\equiv c^{\frac{1}{2}}\mathrm{mod}p$$

$$m_q\equiv c^{\frac{1}{2}}\mathrm{mod}q$$

PART2 Calculated $y_p$ and $y_q$ with Extended Euclidean Algorithm whose function is gmpy2.gcdext().
$$y_p\cdot p+y_q\cdot q=1$$
PART3 Solve out four plaintexts.
$$a\equiv (y_p\cdot p\cdot m_q+y_q\cdot q\cdot m_p)\mathrm{mod}n$$

$$b\equiv n-a$$

$$c\equiv (y_p\cdot p\cdot m_q-y_q\cdot q\cdot m_p)\mathrm{mod}n$$

$$d\equiv n-c$$

Thus, we will get four different plaintext, and one of them is the true plaintext.

Here is the complete code:

def RSA_Rabin_e2(c,n,p,q):
    mp = gmpy2.powmod(c,(p+1)//4,p)
    mq = gmpy2.powmod(c,(q+1)//4,q)
    """
    mp = gmpy2.powmod(c,1/2,p)
    mq = gmpy2.powmod(c,1/2,q)
    """

    gcd,yp,yq = gmpy2.gcdext(p,q)

    m1 = (yp * p * mq + yq * q * mp) % n
    m2 = n - m1
    m3 = (yp * p * mq - yq * q * mp) % n
    m4 = n - m3
    return m1, m2, m3, m4

e != 2

If $e$ is not equal to 2, we use another way to calculate the final $m$.

For example, $gcd(e,\phi (n))=a$. We can divide $e$ to get the equation $gcd(e//a,\phi (n))=1$ to solve the private key $d$.

Finally, we get the $m^a$. We use iroot($m^{a}$, a)[0] to get the final plaintext $m$.

# We define phi as N
a = gcd(e, N)
d = invert(e//a, N)
m = iroot(powmod(c, d, n), a)[0]

AMM

The same $e$ is too large to solve out.

import random
import math
def GF(a):
    global p
    p = a

def g(a,b):
    global p
    return pow(a,b,p)

def AMM(x,e,p):
    GF(p)
    y = random.randint(1, p-1)
    while g(y, (p-1)//e) == 1:
        y = random.randint(1, p-1)
        print(y)
    print("find")
    #p-1 = e^t*s
    t = 1
    s = 0
    while p % e == 0:
        t += 1
        print(t)
    s = p // (e**t)
    print('e', e)
    print('p', p)
    print('s', s)
    print('t', t)
    # s|ralpha-1
    k = 1
    while((s * k + 1) % e != 0):
        k += 1
    alpha = (s * k + 1) // e
    a = g(y, (e ** (t - 1) ) * s)
    b = g(x, e * alpha - 1)
    c = g(y, s)
    h = 1
    #
    for i in range(1, t-1):
        d = g(b,e**(t-1-i))
        if d == 1:
            j = 0
        else:
            j = -math.log(d,a)
        b = b * (g(g(c, e), j))
        h = h * g(c, j)
        c = g(c, e)
    root = (g(x, alpha * h)) % p
    roots = set()
    for i in range(e):
        mp2 = root * g(a,i) % p
        roots.add(mp2)
    return roots
def check(m):
    if 'flag' in m: # edit
        print(m)
        return True
    else:
        return False

RSA_LEAKAGE

Leakage_d

Use RSAConverter.

• $n$, $d$, hex(), delete 0x
• $e$, hex(), delete x

Leakage_dp&dq

Dedection and keypoint!

Prepare and make a definition to $d_p$ and $d_q$.
$$d_p\equiv d\mathrm{mod}p-1$$

$$d_q\equiv d\mathrm{mod}q-1$$

After deductions, we can get four significant equations or relations.
$$q\times InvQ\equiv 1\mathrm{mod}p$$

$$m_p\equiv c^{d_p}\mathrm{mod}p$$

$$m_q\equiv c^{d_q}\mathrm{mod}q$$

$$m\equiv (((m_p-m_q)\times InvQ)\mathrm{mod}p)\times q+m_q$$

And make the equations convert to codes. Here is the main function:

def RSA_Leakage_dp_dq(dp, dq, p, q, c):
    InvQ = gmpy2.invert(q, p)
    mp = gmpy2.powmod(c, dp, p)
    mq = gmpy2.powmod(c, dq, q)
    m = (((mp-mq)*InvQ)%p)*q + mq
    return m

Leakage_dp

basic

Known:
$$d_p\equiv d\mathrm{mod}(p-1)$$

$$\begin{array}{}\text{(1)}& d\times e\equiv 1\mathrm{mod}N\equiv 1\mathrm{mod}(p-1)(q-1)\end{array}$$

Make full use of the two known equations and deduce the key condition to obtain the final $p$ and $q$.
$$\begin{array}{}\text{(2)}& d_p\times e\equiv d\times e\mathrm{mod}(p-1)\equiv de+k_1(p-1)\end{array}$$
Substitute (2) to (1):
$$k_1(p-1)+d_{p}e=1+k_2(p-1)(q-1)$$

$$d_{p}e-1=(p-1)[k_2(q-1)-k_1]$$

Assume $k_2(q-1)-k_1$ is $x$, and $x$ is range from 0 and $e$, and we can figure out the $p$ from the equation:
$$p=\frac{d_{p}e-1}{x}+1$$
If we brute the $p$ in range(0, e) and $q=n÷p$ is prime or Integer, we will get the true $p$ and $q$. The code is as follows:

def RSA_Leakage_dp(n,e,dp,c):
     for i in range(1,e):  # start with 1
        p = (dp*e - 1)//i + 1
        if n%p == 0:
            q = n//p
        else:
            continue
        N = (p-1)*(q-1)
        d = gmpy2.invert(e, N)
        m = gmpy2.powmod(c, d, n)
        return m

dp_extension-1 $n=p^b\cdot q$

reference: Larrozo

relate: [2020YCB]Power

def dp_hensel(c, e, dp, p, b):
    """
    :param b: p^b*q
    :return:
    """
    mp_ = pow(c, dp, p)
    mp = pow(c, dp - 1, p)
    for i in range(1, b - 2):
        x = pow(c - pow(mp_, e), 1, p**(i + 1))
        y = pow(x * mp * invert(e, p), 1, p**(i + 1))
        mp_ = mp_ + y
    return mp_

dp_extension-2 coppersmith known dp high

Given: $n,e,d{p}_0,c,k$

the $d{p}_0$ is the high-digits$(nbits-k)$ of dp, meaning that $d{p}_0=dp>>k$

Solve: use the coppersmith-high p

dp_extension-3 $p=gcd(m^{e\cdot dp}-m,n)$

LARGE $e$

Wiener Attack

$d<N^{0.25}$

original deduction

From the RSA proof, we have a DEFAULT RULE:
$$e\times d\equiv 1\mathrm{mod}\phi (n)$$
If satisfied conditions, we will get the deduced equation:
$$e\times d=k\times \phi (n)+1\approx k\times \phi (n)$$
In cryptography, the $n$ is usually very large. So, we can make a connection with $\phi (n)$:
$$\phi (n)\approx n$$
Thus, we can get the final deduction:
$$e\times d\approx k\times n$$

$$\frac{e}{n}\approx \frac{k}{d}$$

continued fraction

Use Extended Euclidean Algorithm, and we will get the equation. Here is the proof-picture:

For the example, we can get the continued fraction that 34/99 -> [0, 2, 1, 10, 3].

def continued_fra(x,y):
    """
    continued fraction expansion
    :param x: 分子
    :param y: 分母
    :return: 连分数展开列表cf[]
    """
    cf = []
    while y:
        cf.append(x // y)
        x, y = y, x % y
    # print(cf)
    return cf

gradual fraction

def gradual_fra(cf):
    """
    :param cf: 连分数展开
    :return: 最后的收敛子,收敛子列表 gf[]
    """
    c = []
    d = []
    c.append(1) # c[0] = 1
    c.append(cf[0]) # c[1] = cf[0]
    d.append(0) # d[0] = 0
    d.append(1) # d[1]
    gf = []
    gf.append(cf[0])
    for i in range(2, len(cf)+1):
        c.append(cf[i-1]*c[i-1] + c[i-2])
        d.append(cf[i-1]*d[i-1] + d[i-2])
        gf.append((c[i], d[i]))
    # print(gf)
    return c[len(cf)], d[len(cf)], gf

Veda’s theorem

def solve_pq(a,b,c):
    """
    韦达定理，求解方程：x^2+(p+q)x+pq = 0
    :param a: x^2系数
    :param b: x系数
    :param c: pq
    :return: p,q
    """
    # par = gmpy2.isqrt(b * b - 4 * a * c)
    par = gmpy2.iroot(b * b - 4 * a * c, 2)[0]
    return (-b + par) // (2 * a), (-b - par) // (2 * a)

main Wiener

def RSA_Wiener_Attack(e,n):
    """
    具体实现
    :param e:
    :param n:
    :return: d
    """
    cf = continued_fra(e, n)
    gf = gradual_fra(cf)[2]
    for k, d in gf[1:]:
        if (e * d - 1) % k != 0:
            continue
        N = (e * d - 1) // k
        p, q = solve_pq(1, n - N + 1, n)
        if p * q == n:
            return d

Boneh-Durfee Attack

$d<N^{0.29}$

COPPPERSMITH

high m

# high m
def phase2(high_m, n, c):
    R.<x> = PolynomialRing(Zmod(n), implementation = 'NTL')
    m = high_m + x
    M = m((m^3 - c).small_roots()[0])
    return hex(int(M))[2:]

high p

# high p
def phase3(high_p, n ,c):
    R.<x> = PolynomialRing(Zmod(n), implementation = 'NTL')
    p = high_p + x
    x0 = p.small_roots(X = 2^128, beta = 0.1)[0]
    
    P = int(p(x0))
    Q = n // P
    assert P*Q == n
    d = inverse_mod(e, (P-1)*(Q-1))
    return hex(power_mod(c, d, n))[2:]

low d

# low d
def getFullP(low_p, n):
    R.<x> = PolynomialRing(Zmod(n), implementation='NTL')
    p = x*2^512 + low_p
    root = (p-n).monic().small_roots(X = 2^128, beta = 0.4)
    if root:
        return p(root[0])
    return None
    
def phase4(low_d, n, c):
    maybe_p = []
    for k in range(1, 4):
        p = var('p')
        p0 = solve_mod([3*p*low_d  == p + k*(n*p - p^2 - n + p)], 2^512)
        maybe_p += [int(x[0]) for x in p0]
    # print(maybe_p)
    
    for x in maybe_p:
        P = getFullP(x, n)
        if P: break
    
    P = int(P)
    Q = n // P
    
    assert P*Q == n
    
    d = inverse_mod(3, (P-1)*(Q-1))
    return hex(power_mod(c, d, n))[2:]

crt/broadcast

# crt/broadcast
def phase5(n1, c1, n2, c2, n3, c3):
    r = CRT([c1, c2, c3], [n1, n2, n3])
    m = int(r)^(1/3)
    return hex(m)[2:]

Franklin–Reiter related-message attack

n  =
c1 = 
c2 = 
e = 3

R.<x> = PolynomialRing(Zmod(n))
g1 = x^e - c1
g2 = (x+1)^e - c2
def MyGcd(x, y):
    if y == 0:
        return x.monic()
    return MyGcd(y, x%y)

v = MyGcd(g2, g1)
M = n - v.coefficients()[0]
assert g1(M) == 0
print(hex(M)[2:])

Boneh Burfee Attack

# Boneh Burfee Attack
import time

"""
Setting debug to true will display more informations
about the lattice, the bounds, the vectors...
"""
debug = True

"""
Setting strict to true will stop the algorithm (and
return (-1, -1)) if we don't have a correct 
upperbound on the determinant. Note that this 
doesn't necesseraly mean that no solutions 
will be found since the theoretical upperbound is
usualy far away from actual results. That is why
you should probably use `strict = False`
"""
strict = False

"""
This is experimental, but has provided remarkable results
so far. It tries to reduce the lattice as much as it can
while keeping its efficiency. I see no reason not to use
this option, but if things don't work, you should try
disabling it
"""
helpful_only = True
dimension_min = 7 # stop removing if lattice reaches that dimension

############################################
# Functions
##########################################

# display stats on helpful vectors
def helpful_vectors(BB, modulus):
    nothelpful = 0
    for ii in range(BB.dimensions()[0]):
        if BB[ii,ii] >= modulus:
            nothelpful += 1

    print (nothelpful, "/", BB.dimensions()[0], " vectors are not helpful")

# display matrix picture with 0 and X
def matrix_overview(BB, bound):
    for ii in range(BB.dimensions()[0]):
        a = ('%02d ' % ii)
        for jj in range(BB.dimensions()[1]):
            a += '0' if BB[ii,jj] == 0 else 'X'
            if BB.dimensions()[0] < 60:
                a += ' '
        if BB[ii, ii] >= bound:
            a += '~'
        print (a)

# tries to remove unhelpful vectors
# we start at current = n-1 (last vector)
def remove_unhelpful(BB, monomials, bound, current):
    # end of our recursive function
    if current == -1 or BB.dimensions()[0] <= dimension_min:
        return BB

    # we start by checking from the end
    for ii in range(current, -1, -1):
        # if it is unhelpful:
        if BB[ii, ii] >= bound:
            affected_vectors = 0
            affected_vector_index = 0
            # let's check if it affects other vectors
            for jj in range(ii + 1, BB.dimensions()[0]):
                # if another vector is affected:
                # we increase the count
                if BB[jj, ii] != 0:
                    affected_vectors += 1
                    affected_vector_index = jj

            # level:0
            # if no other vectors end up affected
            # we remove it
            if affected_vectors == 0:
                print ("* removing unhelpful vector", ii)
                BB = BB.delete_columns([ii])
                BB = BB.delete_rows([ii])
                monomials.pop(ii)
                BB = remove_unhelpful(BB, monomials, bound, ii-1)
                return BB

            # level:1
            # if just one was affected we check
            # if it is affecting someone else
            elif affected_vectors == 1:
                affected_deeper = True
                for kk in range(affected_vector_index + 1, BB.dimensions()[0]):
                    # if it is affecting even one vector
                    # we give up on this one
                    if BB[kk, affected_vector_index] != 0:
                        affected_deeper = False
                # remove both it if no other vector was affected and
                # this helpful vector is not helpful enough
                # compared to our unhelpful one
                if affected_deeper and abs(bound - BB[affected_vector_index, affected_vector_index]) < abs(bound - BB[ii, ii]):
                    print ("* removing unhelpful vectors", ii, "and", affected_vector_index)
                    BB = BB.delete_columns([affected_vector_index, ii])
                    BB = BB.delete_rows([affected_vector_index, ii])
                    monomials.pop(affected_vector_index)
                    monomials.pop(ii)
                    BB = remove_unhelpful(BB, monomials, bound, ii-1)
                    return BB
    # nothing happened
    return BB

""" 
Returns:
* 0,0   if it fails
* -1,-1 if `strict=true`, and determinant doesn't bound
* x0,y0 the solutions of `pol`
"""
def boneh_durfee(pol, modulus, mm, tt, XX, YY):
    """
    Boneh and Durfee revisited by Herrmann and May
    
    finds a solution if:
    * d < N^delta
    * |x| < e^delta
    * |y| < e^0.5
    whenever delta < 1 - sqrt(2)/2 ~ 0.292
    """

    # substitution (Herrman and May)
    PR.<u, x, y> = PolynomialRing(ZZ)
    Q = PR.quotient(x*y + 1 - u) # u = xy + 1
    polZ = Q(pol).lift()

    UU = XX*YY + 1

    # x-shifts
    gg = []
    for kk in range(mm + 1):
        for ii in range(mm - kk + 1):
            xshift = x^ii * modulus^(mm - kk) * polZ(u, x, y)^kk
            gg.append(xshift)
    gg.sort()

    # x-shifts list of monomials
    monomials = []
    for polynomial in gg:
        for monomial in polynomial.monomials():
            if monomial not in monomials:
                monomials.append(monomial)
    monomials.sort()
    
    # y-shifts (selected by Herrman and May)
    for jj in range(1, tt + 1):
        for kk in range(floor(mm/tt) * jj, mm + 1):
            yshift = y^jj * polZ(u, x, y)^kk * modulus^(mm - kk)
            yshift = Q(yshift).lift()
            gg.append(yshift) # substitution
    
    # y-shifts list of monomials
    for jj in range(1, tt + 1):
        for kk in range(floor(mm/tt) * jj, mm + 1):
            monomials.append(u^kk * y^jj)

    # construct lattice B
    nn = len(monomials)
    BB = Matrix(ZZ, nn)
    for ii in range(nn):
        BB[ii, 0] = gg[ii](0, 0, 0)
        for jj in range(1, ii + 1):
            if monomials[jj] in gg[ii].monomials():
                BB[ii, jj] = gg[ii].monomial_coefficient(monomials[jj]) * monomials[jj](UU,XX,YY)

    # Prototype to reduce the lattice
    if helpful_only:
        # automatically remove
        BB = remove_unhelpful(BB, monomials, modulus^mm, nn-1)
        # reset dimension
        nn = BB.dimensions()[0]
        if nn == 0:
            print ("failure")
            return 0,0

    # check if vectors are helpful
    if debug:
        helpful_vectors(BB, modulus^mm)
    
    # check if determinant is correctly bounded
    det = BB.det()
    bound = modulus^(mm*nn)
    if det >= bound:
        print ("We do not have det < bound. Solutions might not be found.")
        print ("Try with highers m and t.")
        if debug:
            diff = (log(det) - log(bound)) / log(2)
            print ("size det(L) - size e^(m*n) = ", floor(diff))
        if strict:
            return -1, -1
    else:
        print ("det(L) < e^(m*n) (good! If a solution exists < N^delta, it will be found)")

    # display the lattice basis
    if debug:
        matrix_overview(BB, modulus^mm)

    # LLL
    if debug:
        print ("optimizing basis of the lattice via LLL, this can take a long time")

    BB = BB.LLL()

    if debug:
        print ("LLL is done!")

    # transform vector i & j -> polynomials 1 & 2
    if debug:
        print ("looking for independent vectors in the lattice")
    found_polynomials = False
    
    for pol1_idx in range(nn - 1):
        for pol2_idx in range(pol1_idx + 1, nn):
            # for i and j, create the two polynomials
            PR.<w,z> = PolynomialRing(ZZ)
            pol1 = pol2 = 0
            for jj in range(nn):
                pol1 += monomials[jj](w*z+1,w,z) * BB[pol1_idx, jj] / monomials[jj](UU,XX,YY)
                pol2 += monomials[jj](w*z+1,w,z) * BB[pol2_idx, jj] / monomials[jj](UU,XX,YY)

            # resultant
            PR.<q> = PolynomialRing(ZZ)
            rr = pol1.resultant(pol2)

            # are these good polynomials?
            if rr.is_zero() or rr.monomials() == [1]:
                continue
            else:
                print ("found them, using vectors", pol1_idx, "and", pol2_idx)
                found_polynomials = True
                break
        if found_polynomials:
            break

    if not found_polynomials:
        print ("no independant vectors could be found. This should very rarely happen...")
        return 0, 0
    
    rr = rr(q, q)

    # solutions
    soly = rr.roots()

    if len(soly) == 0:
        print ("Your prediction (delta) is too small")
        return 0, 0

    soly = soly[0][0]
    ss = pol1(q, soly)
    solx = ss.roots()[0][0]

    #
    return solx, soly

def example():
    ############################################
    # How To Use This Script
    ##########################################

    #
    # The problem to solve (edit the following values)
    #

    # the modulus
    N = 0xbadd260d14ea665b62e7d2e634f20a6382ac369cd44017305b69cf3a2694667ee651acded7085e0757d169b090f29f3f86fec255746674ffa8a6a3e1c9e1861003eb39f82cf74d84cc18e345f60865f998b33fc182a1a4ffa71f5ae48a1b5cb4c5f154b0997dc9b001e441815ce59c6c825f064fdca678858758dc2cebbc4d27    # the public exponent
    e = 0x11722b54dd6f3ad9ce81da6f6ecb0acaf2cbc3885841d08b32abc0672d1a7293f9856db8f9407dc05f6f373a2d9246752a7cc7b1b6923f1827adfaeefc811e6e5989cce9f00897cfc1fc57987cce4862b5343bc8e91ddf2bd9e23aea9316a69f28f407cfe324d546a7dde13eb0bd052f694aefe8ec0f5298800277dbab4a33bb
    c = 0xe3505f41ec936cf6bd8ae344bfec85746dc7d87a5943b3a7136482dd7b980f68f52c887585d1c7ca099310c4da2f70d4d5345d3641428797030177da6cc0d41e7b28d0abce694157c611697df8d0add3d900c00f778ac3428f341f47ecc4d868c6c5de0724b0c3403296d84f26736aa66f7905d498fa1862ca59e97f8f866c
    # the hypothesis on the private exponent (the theoretical maximum is 0.292)
    delta = 0.270 # this means that d < N^delta

    #
    # Lattice (tweak those values)
    #

    # you should tweak this (after a first run), (e.g. increment it until a solution is found)
    m = 4 # size of the lattice (bigger the better/slower)

    # you need to be a lattice master to tweak these
    t = int((1-2*delta) * m)  # optimization from Herrmann and May
    X = 2*floor(N^delta)  # this _might_ be too much
    Y = floor(N^(1/2))    # correct if p, q are ~ same size

    #
    # Don't touch anything below
    #

    # Problem put in equation
    P.<x,y> = PolynomialRing(ZZ)
    A = int((N+1)/2)
    pol = 1 + x * (A + y)

    #
    # Find the solutions!
    #

    # Checking bounds
    if debug:
        print ("=== checking values ===")
        print ("* delta:", delta)
        print ("* delta < 0.292", delta < 0.292)
        print ("* size of e:", int(log(e)/log(2)))
        print ("* size of N:", int(log(N)/log(2)))
        print ("* m:", m, ", t:", t)

    # boneh_durfee
    if debug:
        print ("=== running algorithm ===")
        start_time = time.time()

    solx, soly = boneh_durfee(pol, e, m, t, X, Y)

    # found a solution?
    if solx > 0:
        print ("=== solution found ===")
        if False:
            print ("x:", solx)
            print ("y:", soly)

        d = int(pol(solx, soly) / e)
        m = pow(c, d, N)
        print ("[+] d:" + str(d))
        print ("[+] m:" + str(m))
        
    else:
        print ("=== no solution was found ===")

    if debug:
        print("=== %s seconds ===" % (time.time() - start_time))
        print("=== ALL DONE!")

if __name__ == "__main__":
    example()

Addiction

When we obtain the $m$, there are different ways to get flag.

• long_to_bytes()

Long integer converts to bytes.

• ASCII

The beginning of $m$ is 1, and it may convert to some invisible characters.

TBC