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

部分位已知

通过分析题目附件中的代码发现：素数总是隐藏了 50%bit，反过来就是 50%bit 已知

DFS + 枚举状态 + 通过 $N$ 的低部分位来 Check 枚举的 $p,q$ 低位是否准确即可解出 $p,q$

随后即为常规 RSA

模不互素

SageMath's Code

p = GCD(n1, n2)
q = n1 // p

这时已知 $p$ $q$ 常规 RSA

CryptoCTF RM2

交互 $+$ 分析代码，分析出 encrypt() 核心逻辑如下

c_1 \equiv m_1^e \pmod{(p - 1) * (q - 1)}

c_2 \equiv m_2^e \pmod {(2*p + 1) * (2*q + 1)}

要求 $p, q$ 为 $1024 \text{bit}$ 素数，且 $p \neq q$ ， $m_1 + m_2 = s$ ，题目要求回传 $s$ ，正确即返回 flag

不难发现构造 $f \coloneqq 2*a+1$ ，其中 $a, f \in \text{Prime}$

即可将题目中的 encrypt() 核心代码中的模幂运算转变为 RSA

$m_{比特长度} \leq 256$ 于是我们只需要其中最小素因子大于 $256\text{bit}$ 即可

而受到 $c_2$ 加密过程的启发，发现虽然 $p-1$ 不可能为素数，但可以让 $p-1$ 为大素数构成的合数

注意区分 $\varphi$ 与模数的配对状态，避免搞混

from sympy import isprime, primerange
from Crypto.Util.number import getPrime

def generate_large_prime(bits=1023):
    q = getPrime(bits) 
    p = 2 * q + 1
    while not isprime(p):
        q = getPrime(bits)
        p = 2 * q + 1
    return p

def phi_of_p_minus_1(p):
    q = (p - 1) // 2
    return q - 1


p = generate_large_prime()
print(f"Generated prime p: {p}")
phi = phi_of_p_minus_1(p)
print(f"Phi(p-1): {phi}")

可以使用 Pwntools 加速整个流程

RSA 单因数

已知 $p$ ，且加密过程为 $m^e\equiv c \pmod{p}$

单因子解密，如下

p = 
e = 
c = 
phi = p - 1
d = pow(e, -1, phi)
m = pow(c, d, p)

RSA 泄露部分因数

泄露 $N$ 的其中一个素因子，且猜测 $m < p$

单因字解密， $\varphi(p) = (p - 1)$

m\equiv c^d \pmod p

solved

RSA $dp,dq$ 泄露

import gmpy2
from Crypto.Util.number import long_to_bytes
from functools import reduce

def CRT(r, mod):
    M = reduce(lambda x,y:x*y, mod)

    ans = 0
    
    for i in range(len(r)):
        m = M // mod[i]
        ans += r[i] * m * gmpy2.invert(m, mod[i])
    
    return ans % M


p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229 
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469 
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929 
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041 
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852

cdModP = gmpy2.powmod(c, dp, p)
cdModQ = gmpy2.powmod(c, dq, q)

m = CRT([cdModP, cdModQ], [p, q])
print(long_to_bytes(m))

RSA 共模攻击

如果 $e_1$ 与 $e_2$ 互素，则用拓展欧几里得解 $r, s$

满足

\begin{aligned} r \cdot e1 + s \cdot e2 &= 1 \\ r \cdot e1 &\equiv 1 \pmod{e2} \\ s \cdot e2 &\equiv 1 \pmod{e1} \\ \end{aligned}

得出 $e_1, e_2$ ，接着我们计算 $m$

\begin{aligned} c_1^r * c_2^s &\equiv {m^{e_1}}^r * {m^{e_2}}^s \pmod {n} \\ c_1^r * c_2^s &\equiv m^{e_1*r} * m^{e_2*s} \pmod {n} \\ c_1^r * c_2^s &\equiv m^{e_1*r + e_2*s} \pmod {n} \\ \end{aligned}

而我们又有 $e_1*r + e_2*s = 1$ ，证毕

SageMath's Code

from Crypto.Util.number import long_to_bytes
gcd, r, s = xgcd(e1, e2)
m = pow(c1, r, n) * pow(c2, s, n) % n
print(long_to_bytes(int(m)))

RSA 数论推导之已知 $(p+1)∗(q+1)$

已知 $p+q$ 与 $(p+1)(q+1)$ 的值

后者展开为 $p*q + p + q + 1$

于是可求出 $p*q = (p+1) * (q+1) - (p+q) - 1$

这时 $p, q$ 已知，常规 RSA 解密

RSA 数论推导之已知 $p + q$ 使用 Z3-Solver 求解

已知 $p+q$ 与 $n$ ，即为 $p * q$ ，推导如下

同时有 $\varphi{(n)} = (p - 1) * (q - 1)$

展开为 $\varphi(n) = p * q - p - q + 1$

可写为 $\varphi(n) = p * q - (p + q) + 1$

于是可推出 $\varphi(n)$

此时可解，或者我们也可用解方程的方式求解，如下

pip install z3-solver

from z3 import *
from Crypto.Util.number import long_to_bytes

pADDq = 0x1314b184dbfce7f1b0d89ae26798cd5e3cce874da95faa3b815a13c871581969f819cba0b4604c1455da83104a66a4dbe2a502ed7a65d6b0f7d73e680c7b0d4f8
e = 0x10001
n = 0x5b04d2d0b300397c148674e6ec0afd48775303c26712d08f8bcf312671d2484889a628c9f31ec967a242213299886355971c368ccdda6a21853df9b4543d56f491f2edbe5b019dd309170ce8038b40d974f813f54562b3cd278e5afe29bbc297ac1e0f347382e191a12de09716e1d54ba229cb44f154d28814b4f128bd07434f
c = 0xbfb773fb8e977aac089068ec4ec6f8d9f04410d5c0be5f95f21ca08125ab3563d9a2a87bed1c37f5e829b808f0a88b88770ebd3bc4130c8973df62eb0309c5d7d65e1584b73fd7b477b9b2707b0992ee3f88c338b6ddc67c85f725967fbb90d1e419741fe81fda42079203f48999ea1b21192ecfc81f90bdc0b3808c6b3f22c


p = Int('p')
q = Int('q')

eq1 = p + q == pADDq
eq2 = p * q == n

s = Solver()
s.add(eq1)
s.add(eq2)
s.check()
m = s.model()
p = m[p].as_long()
q = m[q].as_long()
phi = (p-1)*(q-1)
d = pow(e, -1, phi) # 报错(且确认e, phi互素)则使用 Crypto.Util.number.inverse(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))

LOV3 -> OV3