一些入门的常见的 CTF Crypto 题型[1]

RSA是什么

特征：给出 `p`、`q`，考察 RSA 解密原理

SageMath's Code

from Crypto.Util.number import long_to_bytes

p = 
q = 
phi = (p - 1) * (q - 1)
n = p * q
e = 
d = inverse_mod(e, phi)
m = power_mod(c, d, n)
print(long_to_bytes(int(m)))  # 强制类型转换

RSA $e=3$

特征： $e$ (公钥指数) 很小

from gmpy2 import iroot
import itertools

n = 
e = 3
c = 

"""
m = iroot(c, e)
if m[1]:
    print(long_to_bytes(m[0]))
"""

for i in itertools.count(0):
    m = iroot(c + i * n, e)
    if m[1]:
        print(long_to_bytes(m[0]))
        break

RSA 因数分解

特征： $N$ 的因子很小

这里为 ( $80\text{bit} * 80\text{bit}$ )

使用 yafu (不兼容 arm 设备) 或者 SageMath 的 factor() 分解

分解后即为常规的已知 $p, q$ 解密

from Crypto.Util.number import long_to_bytes

p = 
q = 
phi = (p - 1) * (q - 1)
n = p * q
e = 
d = inverse_mod(e, phi)
m = power_mod(c, d, n)
print(long_to_bytes(int(m)))  # 强制类型转换

RSA $p q$ 过近

特征 $p - q$ 较小

过近选择开平方根后枚举下/上一个素数

选择 gmpy2.iroot(n, 2)

from gmpy2 import iroot
from sympy import nextprime, prevprime

temp = iroot(n, 2)
if temp[1]:
	temp = temp[0]
	print('开平方根后无需查找')
	exit()
else:
	temp = temp[0]

p = nextprime(temp)
q = prevprime(p)

print(f'{p = }')
print(f'{q = }')

接着即为常规 RSA 解密，不在赘述

RSA $PQR$

特征：不止两个因子

计算 $\varphi{(N)}$ 时分别减一，类似两个因子的常规情况

p = 
q = 
r = 

phi = (p - 1) * (q - 1) * (r - 1)

RSA $PPR$

特征：不止两个因子，且因子有重复

计算 $\varphi{(N)}$ ，可以套用

\phi(n) = (p - 1) * (q - 1) * (p^{\text{p的原始幂数}-1}) * (q^{\text{q的原始幂数}-1})

此题情况 $n = p * p * q$ ，也就是 $n = p^2 * q$

p = 
q = 

phi = (p - 1) * (q - 1) * (p ** (2 - 1)) * (p ** (1 - 1))

已知 $\varphi{(N)}$ ，又有 $e$ ，可计算出 $d$ ，有了私钥，常规 RSA

RSA 维纳 (Wiener's Attack)

特征： $e$ 很大，这时隐含信息是 $d$ 很小，还应满足 $q < p < 2q$ 与 $N=p*q$

d < \frac{1}{3}N^{\frac{1}{4}}

Code

计算连分数

# Continued Fraction Expansion of Rationals

def cf_expansion(n, d):
    e = []

    q = n // d
    r = n % d
    e.append(q)

    while r != 0:
        n, d = d, r
        q = n // d
        r = n % d
        e.append(q)

    return e

无理数到有理数的近似

def convergents(e):
    n = [] # Nominators
    d = [] # Denominators

    for i in range(len(e)):
        if i == 0:
            ni = e[i]
            di = 1
        elif i == 1:
            ni = e[i]*e[i-1] + 1
            di = e[i]
        else: # i > 1
            ni = e[i]*n[i-1] + n[i-2]
            di = e[i]*d[i-1] + d[i-2]

        n.append(ni)
        d.append(di)
        yield (ni, di)

完整代码：

SageMath's Code

# 定义求解私钥的函数
def extended_wiener_attack(e, n):
    # 使用连分数逼近 e/n
    for frac in continued_fraction(Integer(e)/Integer(n)).convergents():
        # 尝试从连分数逼近中恢复出私钥 d
        k_d = frac.numerator()
        d = frac.denominator()
        
        # 检查是否是有效的私钥
        if k_d > 0 and (e*d - 1) % k_d == 0:
            phi = (e*d - 1) // k_d
            s = n - phi + 1
            # 检查 s 是否符合二次方程的条件
            disc = s*s - 4*n
            if disc >= 0 and sqrt(disc) == floor(sqrt(disc)):
                return d
    return None

n,e,c=(101535826348700839777412791318907703837248114538536718053781117832940383410028745845826270619583551915174157542563311983390992814052497202746443869124755151562224860279737964122434730661839727564816343218962118648553179532462828415407360644610357769612634961132108401167747147316924764552971111417381022946547, 99901003520309695748811674558564118589566039321460021970280229029894617428872213620641671990396500401480247078628403242703584441907708285019342075210873385129159673855071624825665811580906882181475929073562571095845562827116032077224739604371740265886970298585825056938126654850130103056182933121891941545331, 100335364920535236958764747290227670638358920869695722364908473704209105274847407865645124857803311262346559364298029931116715366772625869090871739013600153982860500239656458368508728248970865572389714597368323858046602585952171052353815396449663748832067728984741122360254695121239997011483416874071653274759)

d = extended_wiener_attack(e, n)
print(f'd = {d}')
from Crypto.Util.number import long_to_bytes
print(long_to_bytes(power_mod(c, d, n)))

引用文献链接🔗

Extending Wiener’s Attack in the Presence of Many Decrypting Exponents. Secure Networking — CQRE [Secure] ’ 99, 153–166 | 10.1007/3-540-46701-7_14_Scihub

拓展：也可以用 Guo's 方法，来解决不止一个 $e$ 的一些情况

RSA 博纳

特征： $e$ 很大，这时隐含信息依旧是 $d$ 很小，但 $d$ 的上界大于维纳的方法

参数选择于临界维纳的临界点，可直接套用维纳攻击的代码，不赘述

具体实现看下一道题

RSA 博纳 revenge (Boneh Durfee)

特征： $e$ 很大，这时隐含信息依旧是 $d$ 很小 ( $d<N^{0.292}$ )，但 $d$ 的上界大于维纳的方法

证明：

首先

ed \equiv 1 \bmod \varphi(N)/2

进而有

ed +k\varphi(N)/2=1

即

k \varphi(N)/2 \equiv 1 \bmod e

又

\varphi(N)=(p-1)(q-1)=qp-p-q+1=N-p-q+1

所以

k(N-p-q+1)/2 \equiv 1 \bmod e

假设 $A=\frac{N+1}{2}$ ， $y=\frac{-p-q}{2}$ ，原式可化为

f(k,y)=k(A+y) \equiv 1 \bmod e

其中

|k|<\frac{2ed}{\varphi(N)}<\frac{3ed}{N}=3*\frac{e}{N}*d<3*\frac{e}{N}*N^{delta}

|y|<2*N^{0.5}

$y$ 的估算用到了 $p$ 、 $q$ 比较均匀的假设。这里 delta 为预估的小于 $0.292$ 的值。

如果我们求得了该二元方程的根，那么我们自然也就可以解一元二次方程 $N=pq,p+q=-2y$ 来得到 $p$ 与 $q$ 。

更加具体的推导，参考 New Results on the Cryptanalysis of Low Exponent RSA.

攻击代码

SageMath's Code
引用自 RSA-and-LLL-attacks/boneh_durfee.sage at master · mimoo/RSA-and-LLL-attacks · GitHub

from __future__ import print_function
import time

############################################
# Config
##########################################

"""
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 = 0xc2fd2913bae61f845ac94e4ee1bb10d8531dda830d31bb221dac5f179a8f883f15046d7aa179aff848db2734b8f88cc73d09f35c445c74ee35b01a96eb7b0a6ad9cb9ccd6c02c3f8c55ecabb55501bb2c318a38cac2db69d510e152756054aaed064ac2a454e46d9b3b755b67b46906fbff8dd9aeca6755909333f5f81bf74db
    # the public exponent
    e = 0x19441f679c9609f2484eb9b2658d7138252b847b2ed8ad182be7976ed57a3e441af14897ce041f3e07916445b88181c22f510150584eee4b0f776a5a487a4472a99f2ddc95efdd2b380ab4480533808b8c92e63ace57fb42bac8315fa487d03bec86d854314bc2ec4f99b192bb98710be151599d60f224114f6b33f47e357517

    # the hypothesis on the private exponent (the theoretical maximum is 0.292)
    delta = .18 # 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)
        print("private key found:", d)
    else:
        print("=== no solution was found ===")

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

if __name__ == "__main__":
    example()

注意格密度参数 $m$ 的选择，建议从 $1$ 往上加

拓展

已知 $d$ 、 $N$ ，得到 $N$ 的分解

首先当 $d$ 泄露之后，我们自然可以解密密文。还可以通过 $d$ 对模数 $N$ 进行分解。其基本原理如下

我们知道 $ed \equiv 1 \bmod \varphi(n)$ ，那么存在一个 $k$ 使得

ed-1= \lambda * \varphi(n)

注意到 $d<\varphi (N)$ ，于是 $\lambda \leq e$ 。只需枚举 $\lambda$ ，得到 $\varphi(N)$ ，通过已知 $\varphi(N)$ 与 $N$ 来得到分解

而在 $e$ 很大时，我们也可以高效分解

考虑 $k \coloneqq ed-1$ ， $k$ 为 $\varphi (N)$ 的倍数，那么 $\forall a\in {Z}_n^*$ ，满足 $a^{ed-1}\equiv1(\bmod n)$ 。显然有 $g^k \equiv 1 \pmod N$ 。令

ed-1=2^st

其中， $t$ 是一个奇数。然后可以证明对于至少一半的 $a\in {Z}_n^*$ ，存在一个 $i\in[1,s]$ ，使得

a^{2^{i-1}t}\not\equiv\pm1(\bmod n),a^{2^{i}t}\equiv1(\bmod n)

成立。如果 $a,i$ 满足上述条件， $\gcd(a^{2^{i-1}t}-1,n)$ 是 $n$ 的一个非平凡因子，所以可以对 $n$ 进行暴力分解

思考题

如何在已知 $N$ 与 $\varphi (N)$ 时得到 $N$ 的分解

引用

CTF Wiki

Crypto Classics: Wiener's RSA Attack

RSA-and-LLL-attacks/boneh_durfee.sage at master · mimoo/RSA-and-LLL-attacks · GitHub

LOV3