Crypto-Write-Up-Zh

Posted on 2023-03-09 Edited on 2023-10-12 In Writeup Symbols count in article: 30k Reading time ≈ 27 mins.

As a routine notepad to record some recurrent tasks in Chinese.

These tasks are somewhat special or interesting, which deserve recording.

Timelines are from new to old.

[DASCTF 2023 & 0X401]ezAlgebra

Coppersmith-已知高位攻击
方程组求解-groebner_basis()

$$
n = p\times q\times r
$$

$$
c_1 \equiv (t+p)^{4} + (t+p)^{3} + (t+p)^{2} + (t+p) + 1997 \mod n
$$

$$
c_2 \equiv (mt)^{19} + (mt)^{18} + \cdots +(mt)^{2} + (mt) + 1997 \mod q
$$

$$
c_3 \equiv (m+t)^{19} + (m+t)^{18}+\cdots + (m+t)^{2} + (m+t) + 1997 \mod q
$$

因为$\mod n \rightarrow \mod q $，所以对公式进行变形可以得到：
$$
\Longrightarrow kp = c_1 - (t^{4} + t^{3} + t^{2} + t + 1997)
$$

Coppersmith-已知高位攻击

此处我们假设$(t + p)$为未知数，利用多项式环进行求解：

PR.<x> = PolynomialRing(Zmod(n))
f = x^4 + x^3 + x^2 + x + 1997 - c1
t = f.small_roots(X = 2 ^ 32, beta = 0.4)[0]
# print(t)

small_roots(X, beta)
- X为该式的需要求解根的上限；虽然是根的上限，并不是说上限越高越好，当上限超过某个值的时候就会计算失效，即使已知二进制位数满足条件，也无法用此函数求得结果；所以一般来说X取在给定情况下的最大求解上限。
- beta，当p,q二进制位数相同时一般只能取$0.4$；如果p,q二进制位数不同，就按照之前的方法具体问题具体分析。$p,q \ge n^{\beta}$
经过测试得到，当未知量小于等于$454bits$时（$p$,$q$为$1024bits$），coppersmith定理可以求解。

$$
gcd(kp, n) = p
$$

kp = t^4 + t^3 + t^2 + t + 1997 - c1
p = gcd(mpz(kp), mpz(n))
qr = n // p
assert isPrime(p)

此时，利用倍数关系，直接把$p$利用gcd()函数进行求解。

方程组求解-groebner_basis()

同样的操作，设置未知数。

利用groebner_basis()函数进行求解，此时必须三个方程才能求解对应未知量。

P.<x, t> = PolynomialRing(Zmod(qr))
f1 = t - 2915836867
f2 = 1997 - c2
f3 = 1997 - c3
for i in range(1, 20):
    f2 += (x * t) ^ i
    f3 += (x + t) ^ i
G = [f1, f2, f3]
I = Ideal(G)
B = I.groebner_basis()
print(B)
res = [i.constant_coefficient() for i in B]
print(res)
q = int(res[2])
m = int(-res[0] % q)
tt = -res[1] % q
print(q)
print(m)

求出m转字符，发现得不到结果，结果是m % q，猜测比q大，爆破一下。

for i in range(0x1000000):
    v = long_to_bytes(m + i * q)
    # if b'ctf' in v:
    #     print(v)
    if all(0x20 <= k < 0x7f for k in v):
        print(v,i)
        break

[DASCTF 2023 & 0X401]ezRSA

coppersmith-已知高位求解p
Franklin Reiter 相关信息攻击

coppersmith-已知高位求解p

$$
gift = P (Q >> 16)
$$

$$
c_1 = pow(n, e, N) \equiv n^{e} \mod N
$$

$$
c_2 = pow(secret, e, N) \equiv secret^{e} \mod N
$$

$$
c_3 = pow(flag, e, n) \equiv flag^{e} \mod N
$$

*已知，$N$,$gift$,$c_1$,$c_2$,$c_3$*，求解flag。

只能从gift入手，P高16位已知，又N = P * Q ，那么Q的高位也能得出，考虑到进位问题，可以将Q的高位位数求小一点（假设为x），之后再根据Q的高位和异或性质，又能求出P的高16 + x位，这里取x = 10，如此循环往复，最后大概剩6比特没恢复，枚举下即可。

from Crypto.Util.number import *
from gmpy2 import *

P_h = gift >> (512 - 16)

# def find_p(p, q, q_):
#     if len(p) == (512 - 16):
#         pp = int(p, 2) + P_h * 2 ** (512 - 16)
#         if gcd(N, pp) > 1:
#             print(pp)
#             print(N//pp)
#         else:
#             l = len(p)
#             pp = int(p, 2)
#             qq = int(q, 2)
#             if (pp ^ qq) % (2 ** l) == gift % (2 ** l) and pp*(qq * 2 ** 16 + q_) % (2 ** l) == N % (2 ** l):
#                 find_p('1' + p, '1' + q, q_)
#                 find_p('1' + p, '0' + q, q_)
#                 find_p('0' + p, '1' + q, q_)
#                 find_p('0' + p, '0' + q, q_)
# for q_ in range(2 ** 16):
#     find_p('1', '1', q_)

# while True:
#     try:
#         Q_h = (N >> (1024 - P_h.bit_length() * 2)) // P_h
#         print(Q_h, Q_h.bit_length())
#         Q_h = Q_h >> 6
#         gifts = gift ^ (Q_h << (512 - 16 - Q_h.bit_length()))
#         P_h = gifts >> (512 - 16 - Q_h.bit_length())
#         print(P_h, P_h.bit_length())
#     except:
#         break

# for i in range(64):
#     P = (P_h << 6) + i
#     if N % P == 0:
#         print(P)
#         break

ph = bin(gift)[2:][:16] + '0'*(512-16)
ph = int(ph,2)
x = bin(gift)[2:][17:]
 
def fac(x,tp,tq):
    if len(x) == 0:
        return
    if tp*tq>N:
        return 
    if N%(tp+1)==0:
        print(tp+1)
        return
    
    v = x[0]
    r = x[1:]
    l = len(r)
    
    if (tp+(1<<(l+1)))*(tq+(1<<(l+17)))<N:
        print(bin(tp)[:50])
        print(bin(tq)[:50])
        print(l)
        return
        
        
    if v == '0':
       fac(r, tp, tq)
       fac(r, tp+(1<<l), tq+(1<<(l+16)))
    else:
       fac(r, tp+(1<<l), tq)
       fac(r, tp, tq+(1<<(l+16)))
 
#q第1位为1 x[0]=='0'
tq = 1<<511
tp = ph + (1<<(512-16-1))
 
fac(x,tp,tq)

之后来到 flag == b"dasctf{" + secret + b"}"这一步。

已知bytes转long型相当于256进制，假设secret的长度为i，那么。

1
2
3

c2 = x ^ 11 
c3 = (bytes_to_long(b'dasctf{' + b'\00' * i + b'}' ) * 256 ** (i + 1) + 256 * x) ^ 11
(其中x = secret , i = len(secret))

Franklin Reiter 相关信息攻击

把$n$先确定下来。

P = 8006847171912577069085166877758626954304824756138758266557706391662987806065132448544117840031499707938227955094109779732609035310252723066470330862622641
Q = N // P
n = powmod(c1, int(invert(e, (P - 1) * (Q - 1))), N)
# n = n + N
# print(n)
k = 0
while True:
    n = n + k * N
    if n % 2 == 1:
        print(n)
        break
    else:
        k += 1

[宁波天一杯]rsa

构造满足条件的$f$，进行根的求解
Pollard_rho 算法
方程化简，模数分解
Relating: 羊城杯2021-easy_rsa

法1——构造$f$

构造$f = 2 \cdot g \cdot x + 1$ 在模$n$情况下有解。

R.<x> = Zmod(n)[]
f = 2 * a * x + 1
g = int(f.monic().small_roots(X=2^51, beta=0.4)[0])
phi = (a - 1) * (g - 1)
n = a * g
d = invert(e, phi)

法2——pollard’s rho

$p - 1$以及$q - 1$存在较大公因数，Pollard’s rho 分解n

def f(x, n):
    return (pow(x, n - 1, n) + 3) % n


def rho(n):
    i = 1
    while True:
        a = getRandomRange(2, n)
        b = f(a, n)
        j = 1
        while True:
            p = GCD(abs(a - b), n)
            # print('{} in {} circle'.format(j, i))
            if p == n:
                break
            elif p > 1:
                return (p, n // p)
            else:
                a = f(a, n)
                b = f(f(b, n), n)
            j += 1
        i += 1

p, q = rho(n)
d = invert(e, (p - 1)*(q - 1))

法3——非预期

神奇非预期

1 2	d = invert(e, a - 1) m = powmod(c, d, a)

法4——化简进行分解

直接利用等式进行分解，化简可得$p\cdot q - 1 = 2gh$，g为51bit，h约为972bit，两者相差非常大，利用factordb/yafu进行分解

gh = (n - 1) // 2
# print(gh)
h = 13570850594633462506426369052182298554140635599543685835372377476383038708650421475723391142118956001358520246769650699398490037618758005241062608387057439283872260149565854577827352267289963736282502923131251179400580891491236925451166755184695335564693793568286112036468975877609637392241679
g = 1346104232461691
phi = (a - 1) * (g - 1)
n = a * g
d = invert(e, phi)

总exp

# %%
n = 36535558847082719901201561031181835346574576610950713924924272947759193576365817762980927638691696601293089537315055413746788190208875234794229119049056299551864869870291634941246362436491006904347559559494705922259007299126640817275929491680601926404543198957206717290905220235571289759182878331893962038379
c = 532997872940452282189043430008002793694788439822465302532208754231005799057972378308576109082463996551992533174546386979606697890310597738637156771564229
a = 2694858406312563434474553988904403597551484373358339092528913028454100111881368126493990657117571672510331411186745639563619323775673115439
e = 65537

# %%
# 法1
# 构造f = 2 * g * x + 1 在模n情况下有解
from Crypto.Util.number import *
from gmpy2 import *

R.<x> = Zmod(n)[]
f = 2 * a * x + 1
g = int(f.monic().small_roots(X=2^51, beta=0.4)[0])
phi = (a - 1) * (g - 1)
n = a * g
d = invert(e, phi)
m = powmod(c, d, n)
print(m)
print(long_to_bytes(m))


# %%
# 法2
# Pollard's rho 分解n
def f(x, n):
    return (pow(x, n - 1, n) + 3) % n


def rho(n):
    i = 1
    while True:
        a = getRandomRange(2, n)
        b = f(a, n)
        j = 1
        while True:
            p = GCD(abs(a - b), n)
            print('{} in {} circle'.format(j, i))
            if p == n:
                break
            elif p > 1:
                return (p, n // p)
            else:
                a = f(a, n)
                b = f(f(b, n), n)
            j += 1
        i += 1



# %%
# 法3
# 神奇非预期
d = invert(e, a - 1)
m = powmod(c, d, a)
print(m)
print(long_to_bytes(m))

# %%
# 法4
# 直接利用等式进行分解，化简可得p*q - 1 = 2gh，g为51bit，h约为972bit，两者相差非常大，利用factordb/yafu进行分解
gh = (n - 1) // 2
# print(gh)
h = 13570850594633462506426369052182298554140635599543685835372377476383038708650421475723391142118956001358520246769650699398490037618758005241062608387057439283872260149565854577827352267289963736282502923131251179400580891491236925451166755184695335564693793568286112036468975877609637392241679
g = 1346104232461691
phi = (a - 1) * (g - 1)
n = a * g
d = invert(e, phi)
m = powmod(c, d, n)
print(m)
print(long_to_bytes(m))

[CryptoCTF2021]HAMUL

规约位数
爆破
Relating: HaM3多一层爆破

已知信息

推导
$$
P = 10^{t}p + q
$$

$$
Q = 10^{s}q + p
$$

$$
PP = 10^{s + t}P + Q = 10^{s + t}(10^{t}P + Q) + 10^{s}Q + P
$$

$$
QQ = 10^{s + t}Q + P = 10^{s + t}(10^{t}Q + P) + 10^{s}P + Q
$$

$$
N = PP \cdot QQ = 10^{3(t+s)}pq + \dots + pq
$$

$$
\Longrightarrow (10^{s + t}(10^{t}p + q) + 10^{s}q + p)(10^{t + s}(10^{s}q + p) + 10^{t}p + q)
$$

对$N$进行整除和求模分析，从而得到$pq$十进制的高位和低位。

大致确定$p$，$q$的位数进行爆破。

从而$str(N)[:?] <—> str(pq)[:?]$

str(N)[:18] = str(pq)[:?]
str(N)[-18:] = str(pq)[-18:]
len(str(pq)) = 38

-> 爆破 2 digits

# %%
n = 
c = 

from Crypto.Util.number import *
from gmpy2 import *
from tqdm import tqdm
low = str(n)[-18:]
high = str(n)[:18]
pq_prob = []

for i in range(10):
    for j in range(10):
        pq_prob.append(int(high + str(i) + str(j) + low))
# print(pq_prob)

for pq in tqdm(pq_prob):
    f = factor(pq)
#     print(f)
    if (len(f) == 2 and f[0][0].nbits() == 64):
        p, q = f[0][0], f[1][0]
        break

P = int(str(p) + str(q))
Q = int(str(q) + str(p))
PP = int(str(P) + str(Q))
QQ = int(str(Q) + str(P))
assert n == PP*QQ


# %%
d = invert(65537, (PP-1)*(QQ-1))
m = powmod(c, d, n)
print(long_to_bytes(m).decode())

[DCIC2023-final]easybag

LLL规约

背包，但是模比较小，所以用常见的那几个格都打不了，可能的方法有二：一是用babai求解cvp，二是把原来的格子多加一维，放个模数进去规约，这里用的第二种：

# 构造格子
A = Matrix(ZZ, 66, 66)
# print(A)
for i in range(64):
    A[i,i] = 1
    A[i,65] = -pubkey[i]
    
A[64,64] = 1
A[64,65] = c
A[65,65] = p
# print(A)
print(A.LLL()[0])
# (0, -1, 0, 0, 0, -1, 0, -1, -1, -1, 0, 0, 0, -1, -1, -1, 0, -1, -1, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, -1, 0, -1, -1, -1, 0, 0, 0, 0, 0, 0, -1, -1, 0, -1, 0, 0, -1, 0, 0, 0, -1, -1, -1, 0, 0, -1, -1, 0, 0, 0, -1, 0, -1, -1, -1, 0)

LLL算法计算出来的长度为66，强制使用固定长度为64的向量进行计算。

所以概括一下，先多加一维进行规约，再使用原来固定长度的向量继续计算，保证一致。

# k = (0, -1, 0, 0, 0, -1, 0, -1, -1, -1, 0, 0, 0, -1, -1, -1, 0, -1, -1, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, -1, 0, -1, -1, -1, 0, 0, 0, 0, 0, 0, -1, -1, 0, -1, 0, 0, -1, 0, 0, 0, -1, -1, -1, 0, 0, -1, -1, 0, 0, 0, -1, 0, -1, -1)
k = A.LLL()[0][0:64]
from Crypto.Cipher import AES
key = ''

for i in k:
    if i:
        key += '1'
    else:
        key += '0'
print(len(key))
print(hex(int(key, 2))[2:])
key = bytes.fromhex(hex(int(key, 2))[2:])
print(len(key))
aes = AES.new(key = key*2, mode=AES.MODE_ECB)
print(aes.decrypt(enc))
# 64
# 45c76015c0d2398b
# 8
# b'flag{e42f0ab28e1c5fb04bbb0c797a2cd951}\n\n\n\n\n\n\n\n\n\n'

[DCIC2023-final]ddddhm

条件判断得到part_d
Coppersmith-lowd

part_d的求解

本题的关键在于fault_signature函数。注意到在该函数中，每次进行加密使用的$d$是由$d2$变化得来的，且每次仅变化1位。由于$d2$肯定是奇数，所以第一次变换时，使用的结果肯定是$d2-1$，即：

1	msg_fault_sigs[0] = pow(msg, d2 - 1, n)

剩下部分依旧按照该思路进行判断，由于存在不确定性，利用计算出msg_fault_sigs[0]进行辅助判断，从而计算出part_d：

字符串连接顺序需要注意，从低位到高位。

msg = bytes_to_long(b'ddddhm')
pows = 2
part_d = "1"
for i in range(1, len(msg_fault_sigs)):
    # here should pay attention to the string's order
    if((msg_fault_sigs[i] * pow(msg, pows-1, n) - msg_fault_sigs[0]) % n)==0:
        part_d = "1" + part_d
    else:
        part_d = "0" + part_d
    pows *= 2
part_d = int(part_d, 2)
print(part_d.bit_length())
print(part_d)
# 681
# 9519637250511849605092115946924531911819643854022344770386391196998091816870433223070160919249620469852108874736739746738237759468821919367674447147826813269165414967606625427817526475380034928092527497223

coppersmith攻击-已知d低位

使用通用脚本计算得$p$。

def partial_p(p0, kbits, n):
    PR.<x> = PolynomialRing(Zmod(n))
    nbits = n.nbits()

    f = 2^kbits*x + p0
    f = f.monic()
    roots = f.small_roots(X=2^(nbits//2-kbits), beta=0.3)  # find root < 2^(nbits//2-kbits) with factor >= n^0.3
    if roots:
        x0 = roots[0]
        p = gcd(mpz(2^kbits*x0 + p0), mpz(n))
        return ZZ(p)

def find_p(d0, kbits, e, n):
    X = var('X')

    for k in range(1, e+1):
        results = solve_mod([e*d0*X - k*X*(n-X+1) + k*n == X], 2^kbits)
        for x in results:
            p0 = ZZ(x[0])
            p = partial_p(p0, kbits, n)
            if p:
                return p

p = find_p(part_d, 1024-part_d.bit_length(), 7, n)
# 12800335172378590918875662486524333103691215133150369430200420149970735808370081784433007260276277361253378071964953226360740601994258142232798414547092861

已知$p$之后那就直接转换成基础RSA了。

q = n // p
d = invert(0x10001, (p-1)*(q-1))
m = powmod(c, d, n)
print(m)
print(unpad(long_to_bytes(m)).decode())
# 280953633736431747947064628051293908189096295024698457307220800187630550375386320255208827601751935813552184196283101709554718133038728081799604794900708412174536625884689548714026681568503654577602432205861968756823980122854293696554980209163635856940269021305243235482137890575873848821429361178108376901
# flag{54b5dc19-5037-46c3-8afe-45394f236852}

[HDCTF2023]math_rsa

二次剩余

主要通过生成参数的满足条件进行判定的。

r=getPrime(1024)
assert r%4==3
# 可得r模4余3
p=getPrime(1024)
assert pow(p,(r-1)//2,r)==1
# 满足二次剩余相关，勒让德符号为1，则，p是r的二次剩余
# 即 p = x^2 mod r
a=pow(p,2,r)
# a = p^2 mod r，

欧拉准则，“$a$是模$p$的二次剩余“是”$a^{\frac{p - 1}{2}} \equiv 1\mod p$“的充要条件。

判定为二次剩余类的，直接使用Tonelli_Shanks()求解$p$即可。

def Tonelli_Shanks(a, p):
    """
    no satisfy 3mod4，to calculate remainder
    or p is prime
    references:
    - https://rosettacode.org/wiki/Tonelli-Shanks_algorithm
    - [V&N2020]Easy RSA
    - 可等价于from sympy.ntheory.residue_ntheory import nthroot_mod(c, 2, r)-> x^2 = c mod r
    - 可等价于sagemath: f.roots()
    :param a: remainder
    :param p: modulo
    :return: r
    """
    # STEP0
    assert pow(a, (p-1)//2, p) == 1
    if p % 4 == 3:
        return Fermat_2remainder(a, p)
    # STEP1
    q = p - 1
    s = 0
    while q % 2 == 0:
        q = q // 2
        s += 1
    # STEP2
    for z in range(2, p):
        if Legendre_Symbol(z, p) == p - 1:
            c = pow(z, q, p)
            break
    # STEP3
    r = pow(a, (q+1)//2, p)
    t = pow(a, q, p)
    m = s
    # STEP4
    if t % p == 1:
        return r
    else:
        i = 0
        while t % p != 1:
            temp = pow(t, 2**(i + 1), p)
            i += 1
            if temp % p == 1:
                b = pow(c, 2**(m - i - 1), p)
                r = r*b % p
                c = b*b % p
                t = t*c % p
                m = i
                i = 0
        return r

p = Tonelli_Shanks(a, r)
assert isPrime(p) == 1
# -> 基础RSA

[HUBUCTF 2022 新生赛]ezMath

pwn交互

很直接，跟靶机交互，做100道简单数学题。惯例先过哈希，然后交互做题。

适合作为交互题目的练习题。

from pwn import *
import string
from hashlib import sha256

def proof_of_work(known: bytes,hashcode):
	"""
	know sha256(XXXX+known) == hashcode
	get the XXXX
	charset = letter + digits
	XXXX has four char
	"""
	charset = string.ascii_letters + string.digits
	for a in charset:
		for b in charset:
			for c in charset:
				for d in charset:
					guess = a + b + c + d
					if sha256(guess.encode()+known).hexdigest() == hashcode:
						return guess

context.log_level = 'debug'
link = remote('', )

# 过SHA256
# 接收
"""
[+] sha256(XXXX+B79N1NIZWlK7gHKB) == 40183d93c30a0316b45ebfabb07db7dc951e143e3fa3c4a004667e2f081c144b
[+] Plz Tell Me XXXX :Hvoc
"""
# 读取到一直读到 sha256(XXXX+ 的 pattern 出现为止
link.recvuntil(b'sha256(XXXX+')
str1 = link.recvuntil(b')', drop=True)
link.recvuntil(b'== ')
str2 = link.recvuntil(b'\n', drop=True)
send_XXXX = proof_of_work(str1, str2.decode()).encode()

# 发送
link.sendlineafter(b'Plz Tell Me XXXX :', send_XXXX)

# 100次数学计算
for i in range(100):
    link.recvline(keepends=True)
    link.recvuntil(b' ', drop=True)
    s = link.recvuntil(b'= ', drop=True)
    sol_out = str(eval(s)).encode()
    send_sol_out = link.sendlineafter(b'?', sol_out)
    link.recvline()

# 结束连接
link.recvall()
# NSSCTF{c629810b-e1b2-40f6-ac92-c88fb041d422}

[NSSCTF-round11]ez_fac

论文题

KEY

1 2	assert pow(a0,2) + e * pow(b0,2) == n assert pow(a1,2) + e * pow(b1,2) == n

$$
a_0^{2} + e \times b_0^{2} =n
$$

$$
a_1^{2} + e\times b_1^{2} = n
$$

根据论文中总结算法。

$N$存在两种形式的分解，那么$gcd(N, ad -bc)=p$一定成立。

from gmpy2 import *
from Crypto.Util.number import *
temp = a0 * b1 - a1 * b0
p = gcd(n, temp)
q = n // p
assert p.bit_length() == 512
assert q.bit_length() == 512
e = (n - a0*a0)//(b0*b0)
assert e.bit_length() == 128
d = invert(e, (p - 1)*(q - 1))
m = powmod(c, d, n)
print(long_to_bytes(m))

[DCIC2023]math_exam

challenge 1

deduction

KEY
$$
leak \equiv (n + p) \mod (q-1)
$$

$$
n = p \times q
$$

DEDUCTION-1
$$
leak \equiv (p \times q + p )\mod (q-1) \equiv p(q + 1) \mod (q-1) \equiv 2p \mod (q-1)
$$

$$
\because p > q
$$

$$
\therefore p \mod (q-1) = p - (q - 1)
$$

$$
\Longrightarrow leak = 2(p-(q-1))
$$

利用sympy中的solve()计算p以及q。

p1 = var('p1')
q1 = var('q1')
sol1 = solve([2*p1 - 2*(q1-1) - leak1, p1*q1 - n1], [p1, q1])
# p1 = 11060083511635869933802569808428381768947206326091523957729804139074727442704400779515603361330886302679144280198610157348614007053927945774770324805383761
# q1 = 10951764080317305242419751556869357195913698564129507860483453991974582578672251918471161965453710637975575181911693960925380203354175653252256241955673123

DEDUCTION-2

依旧先得到:
$$
leak \equiv 2p \mod (q-1)
$$

$$
leak = 2p + k(q-1)
$$

一般来说，$k$ 的量级不会太大，可以直接爆破。而且$p > q$，基本情况下可简化为$p - (q - 1)$。

P.<x> = PolynomialRing(ZZ)
for k in range(1, 4):
    f = k * (x - 1) * x + leak1 * x - 2 * n1
    try:
        q1 = f.roots()[0][0]
        # print(q1)
        break
    except:
        pass

p1 = n1 // q1

challenge 2

crack
limitation

KEY
$$
leak = d + p + q
$$

$$
e\cdot d \equiv 1 \mod phi
$$

DEDUCTION-1
$$
\because phi = (p-1) \times (q-1) = n - (p + q) + 1
$$

$$
\therefore p + q = n + 1 - phi
$$

利用KEY-1以及KEY-2进行代入处理：
$$
e\cdot(leak - (p + q)) = 1 + k \times phi
$$

$$
\Longrightarrow e \cdot (leak - n - 1 + phi) = 1 + k\times phi
$$

$$
\Longrightarrow (e - k)\times phi = e(n + 1 - leak) + 1
$$

$$
\therefore phi = (e(n + 1 - leak) + 1) // (e - k)
$$

所以，存在$k \in [1, e-1]$，使得上式成立，再利用flag的特殊格式进行判断，因此，我们可以得到两个判断条件。

$phi \mod (e - k) == 0$
flag[4:5] == '-' and flag[9:10] == '-'

for k in range(1, 65537):
    if (e2 * (n2 - leak2 + 1) + 1) % (e2 - k) == 0:
        phi = (e2 * (n2 - leak2 + 1) + 1) // (e2 - k)
        d2 = int(invert(e2, phi))
        try:
            m2 = pow(c2, d2, n2)
            flag2 = (long_to_bytes(m2)[:14]).decode()
            if flag2[4:5] == '-' and flag2[9:10] == '-':
                print(flag2)
                break
        except:
            pass

DEDUCTION-2

可得：
$$
(e - k)\times phi = e(n + 1 - leak) + 1
$$
简化一下，即为：
$$
Kphi = e(n + 1 - leak) + 1
$$
此时可以直接利用求逆元的方式求解私钥$d$：

1 2	K_phi = e2 * (n2 - leak2 + 1) + 1 d2 = int(invert(e2, K_phi))

模phi以及模Kphi，等价

challenge 3

fermat

KEY
$$
leak \equiv (p^{q} \mod n + q^{p} \mod n) \mod n
$$

$$
\mod n \rightarrow \mod p /\mod q
$$

DEDUCTION-1
$$
leak \equiv p^{q} \mod n + q^{p}\mod n
$$

$$
\Longrightarrow leak \equiv p^{q} \mod q + q^{p} \mod p
$$

利用费马小定理$a^p \equiv a \mod p$，我们可以得到：
$$
\Longrightarrow leak = p + q
$$
跟$n = p \times q$ 联立方程，可求解出$p$以及$q$。

1
2
3

p3, q3 = var('p3 q3')
sol3 = solve([p3 + q3 - leak3, p3 * q3 - n3], [p3, q3])
print(sol3[1])

DEDUCTION-2

可得：
$$
leak \equiv p^{q} \mod n + q^{p}\mod n
$$

$$
\rightarrow leak = p + k_1 q
$$

$$
\rightarrow leak = q + k_2 p
$$

$$
\Longrightarrow p + k_1 q = q + k_2 p
$$

$$
\therefore k_1 = 1, k_2 = 1
$$

$$
\Longrightarrow leak = p + q
$$

回归上面的代码，联立方程求解$p$以及$q$。

CODE

sagemath

# %%
from Crypto.Util.number import *
from gmpy2 import *

def unpad(msg):
    return msg.split(b'\x00')[0]

# challenge 1
e1 = 65537
c1 = 112742443814287255411540092433156061065388404049949520959549377871297566383025041892192679147481155020865118811016470498351633875090973546567374001852295013083192495299811476604405637385307524194793969533646755764136014187430115618114840780368311166911900457224593131166970676797547489278410997707815915932756
n1 = 121127425328043404860413278637978444801342472819958112597540188142689720655042880213001676368390521140660355813910726809125567752172921410143437643574528335234973793653775043030021036875866776532570781661875022102733555943967261003246543180935987772711036868216508554536086688819118597075508026787867088355603
leak1 = 216638862637129382765636503118049146067015523924032194492700294200289728064297722088882791754351329407138196573832392846467607399504585045028165699421278

P.<x> = PolynomialRing(ZZ)
for k in range(1, 4):
    f = k * (x - 1) * x + leak1 * x - 2 * n1
    try:
        q1 = f.roots()[0][0]
        # print(q1)
        break
    except:
        pass

p1 = n1 // q1
d1 = invert(e1, (p1 - 1)*(q1 - 1))
m1 = int(powmod(c1, d1, n1))
flag1 = unpad(long_to_bytes(m1)).decode()
print(flag1)

# %%
# challenge 2
e2 = 65537
c2 = 7964477910021153997178145480752641882728907630831216554750778499596527781702830885213467912351097301767341858663701574005489585561370961723264247818377063081744522471774208105250855114831033452448184392499682147532404562876275189577321587660597603848038824026981539659156304028998137796242331160312370913038
n2 = 140571013522095816880929287025269553867630639381779595547026503691829940612178900269986625350464874598461222087427155791855120339533208468121389480964471710028253589422629569889402475311387750348466199387760629889238062977271925350490110043385800605640905324122017637306715108727700910035925728362455954862209
leak2 = 58442382248753295429370894053397615609981110383986887405127350139482893508400422595729520437678203735054593866306478994471465948872565590901376309380029015549809468112086393107585011072503638322671608471684607214064187044372418770555236721845694224676090744181562673509234801011420696349507624867568099759003

K_phi = e2 * (n2 - leak2 + 1) + 1
d2 = int(invert(e2, K_phi))
m2 = int(pow(c2, d2, n2))
flag2 = unpad(long_to_bytes(m2)).decode()
print(flag2)

# %%
# challenge 3
e3 = 65537
c3 = 54161995127842474543974770981473422085334044100057089719350274921419091368361244533281599379235907845996678762379778310924192757650322930707785543132446159092950451255660204858292974657119337026589911330412367633761103944916751660957776230135927005700707688661350641600954072696774954805514477330339449799540
n3 = 88207747624007183083381863279444163105330473097729276113333026679597864128605555600000789783468271680476780366740448641311570797876037993255307716167149079618302706650018518487351604778857406170722209469765782625409279109832638886179654096975665134276856272488090272822541461702907181545730309689190333058151
leak3 = 19596671928335648228117128090384865424885102632642665068992144783391306491716530155291726644158221224616817878768426330717188403310818678195631582453246848

# p3, q3 = var('p3 q3')
# sol3 = solve([p3 + q3 - leak3, p3 * q3 - n3], [p3, q3])
# print(sol3)
p3 = 12591119529483514723681507251180531324926419443874102860338530066728710197246719851038994673567739600391874839712324936583490370533180101117667257937826949
q3 = 7005552398852133504435620839204334099958683188768562208653614716662596294469810304252731970590481624224943039056101394133698032777638577077964324515419899
d3 = invert(e3, (p3 - 1)*(q3 - 1))
m3 = int(powmod(c3, d3, n3))
flag3 = unpad(long_to_bytes(m3)).decode()
print(flag3)

# %%
flag = flag1 + flag2 + flag3
assert len(flag) == 42
print(flag)

python

from gmpy2 import *
from Crypto.Util.number import *
# chall 1
e1 = 65537
c1 = 112742443814287255411540092433156061065388404049949520959549377871297566383025041892192679147481155020865118811016470498351633875090973546567374001852295013083192495299811476604405637385307524194793969533646755764136014187430115618114840780368311166911900457224593131166970676797547489278410997707815915932756
n1 = 121127425328043404860413278637978444801342472819958112597540188142689720655042880213001676368390521140660355813910726809125567752172921410143437643574528335234973793653775043030021036875866776532570781661875022102733555943967261003246543180935987772711036868216508554536086688819118597075508026787867088355603
leak1 = 216638862637129382765636503118049146067015523924032194492700294200289728064297722088882791754351329407138196573832392846467607399504585045028165699421278

from sympy import *
"""
法1
"""
# p1 = var('p1')
# q1 = var('q1')
# sol1 = solve([2*p1 - 2*(q1-1) - leak1, p1*q1 - n1], [p1, q1])
p1 = 11060083511635869933802569808428381768947206326091523957729804139074727442704400779515603361330886302679144280198610157348614007053927945774770324805383761
q1 = 10951764080317305242419751556869357195913698564129507860483453991974582578672251918471161965453710637975575181911693960925380203354175653252256241955673123
assert p1 > q1
from Functions_Eurynome import Original_RSA
from Crypto.Util.number import *
m1 = Original_RSA(p1, q1, e1, c1, n1)
flag1 = (long_to_bytes(m1)[:14]).decode()
print(flag1)

# chall 2
e2 = 65537
c2 = 7964477910021153997178145480752641882728907630831216554750778499596527781702830885213467912351097301767341858663701574005489585561370961723264247818377063081744522471774208105250855114831033452448184392499682147532404562876275189577321587660597603848038824026981539659156304028998137796242331160312370913038
n2 = 140571013522095816880929287025269553867630639381779595547026503691829940612178900269986625350464874598461222087427155791855120339533208468121389480964471710028253589422629569889402475311387750348466199387760629889238062977271925350490110043385800605640905324122017637306715108727700910035925728362455954862209
leak2 = 58442382248753295429370894053397615609981110383986887405127350139482893508400422595729520437678203735054593866306478994471465948872565590901376309380029015549809468112086393107585011072503638322671608471684607214064187044372418770555236721845694224676090744181562673509234801011420696349507624867568099759003
"""
法1
"""
# for k in range(1, 65537):
#     if (e2 * (n2 - leak2 + 1) + 1) % (e2 - k) == 0:
#         phi = (e2 * (n2 - leak2 + 1) + 1) // (e2 - k)
#         d2 = int(invert(e2, phi))
#         try:
#             m2 = pow(c2, d2, n2)
#             flag2 = (long_to_bytes(m2)[:14]).decode()
#             if flag2[4:5] == '-' and flag2[9:10] == '-':
#                 print(flag2)
#                 break
#         except:
#             pass
"""
法2
"""
K_phi = e2 * (n2 - leak2 + 1) + 1
d2 = int(invert(e2, K_phi))
m2 = pow(c2, d2, n2)
flag2 = (long_to_bytes(m2)[:14]).decode()
print(flag2)

# chall 3
e3 = 65537
c3 = 54161995127842474543974770981473422085334044100057089719350274921419091368361244533281599379235907845996678762379778310924192757650322930707785543132446159092950451255660204858292974657119337026589911330412367633761103944916751660957776230135927005700707688661350641600954072696774954805514477330339449799540
n3 = 88207747624007183083381863279444163105330473097729276113333026679597864128605555600000789783468271680476780366740448641311570797876037993255307716167149079618302706650018518487351604778857406170722209469765782625409279109832638886179654096975665134276856272488090272822541461702907181545730309689190333058151
leak3 = 19596671928335648228117128090384865424885102632642665068992144783391306491716530155291726644158221224616817878768426330717188403310818678195631582453246848
# p3, q3 = var('p3 q3')
# sol3 = solve([p3 + q3 - leak3, p3 * q3 - n3], [p3, q3])
# print(sol3[1])
p3 = 12591119529483514723681507251180531324926419443874102860338530066728710197246719851038994673567739600391874839712324936583490370533180101117667257937826949
q3 = 7005552398852133504435620839204334099958683188768562208653614716662596294469810304252731970590481624224943039056101394133698032777638577077964324515419899
m3 = Original_RSA(p3, q3, e3, c3, n3)
flag3 = (long_to_bytes(m3)[:14]).decode()
print(flag3)

flag = flag1 + flag2 + flag3
print(flag)

basic
deduction
rabin

$$
num1 \equiv p^e \mod - q^e \mod n \equiv p^e - q^e \mod n
$$

利用二项式展开定理对其进行展开以及模运算：
$$
num2 \equiv (p + q)^e \mod n \equiv p^e + q^e \mod n
$$

{1}式 + {2}式可得：
$$
num1 + num2 \equiv 2 p^e \mod n
$$
又从题目得到$n = p \times q$，利用gcd()可得p：
$$
p = gcd(num1 + num2, n)
$$
而q即为$q = n // p$.

得到p以及q后，发现$p\equiv q \equiv 3 \mod 4$，而$e = 65536 = 2^{16}$，可得下一个知识点为Rabin算法，且循环使用16次。

所以我们对原始的c先进行一次Rabin，所得的四个明文作为c继续循环使用Rabin。

num1 = 134186458247304184975418956047750205959249518467116558944535042073046353646812210914711656218265319503240074967140027248278994209294869476247136854741631971975560846483033205230015783696055443897579440474585892990793595602095853960468928457703619205343030230201261058516219352855127626321847429189498666288452
num2 = 142252615203395148320392930915384149783801592719030740337592034613073131106036364733480644482188684184951026866672011061092572389846929838149296357261088256882232316029199097203257003822750826537629358422813658558008420810100860520289261141533787464661186681371090873356089237613080052677646446751824502044253
n = 154128165952806886790805410291540694477027958542517309121222164274741570806324940112942356615458298064007096476638232940977238598879453357856259085001745763666030177657087772721079761302637352680091939676709372354103177660093164629417313468356185431895723026835950366030712541994019375251534778666996491342313
c = 9061020000447780498751583220055526057707259079063266050917693522289697419950637286020502996753375864826169562714946009146452528404466989211057548905704856329650955828939737304126685040898740775635547039660982064419976700425595503919207903099686497044429265908046033565745195837408532764433870408185128447965

from gmpy2 import *
from Crypto.Util.number import long_to_bytes
p = gcd(num1 + num2, n)
q = n // p
assert is_prime(p)
assert is_prime(q)
assert p % 4 == 3
assert q % 4 == 3
# print(p)
# print(q)
# print(p.bit_length())
# print(q.bit_length())


# 65536 == 2**16
cs = [c]

gcd, yp, yq = gcdext(p, q)
for i in range(16):
    ps = []
    for cc in cs:
        mp = powmod(cc, (p + 1) // 4, p)
        mq = powmod(cc, (q + 1) // 4, q)

        m1 = (yp * p * mq + yq * q * mp) % n
        m2 = n - m1
        m3 = (yp * p * mq - yq * q * mp) % n
        m4 = n - m3
        if m1 not in ps:
            ps.append(m1)
        if m2 not in ps:
            ps.append(m2)
        if m3 not in ps:
            ps.append(m3)
        if m4 not in ps:
            ps.append(m4)

    cs = ps

    for m in ps:
        flag = long_to_bytes(m)
        if b'nss' in flag:
            print(flag)
            break
# nssctf{W3lc0me_t0_nssctf_R0undll_w15h_U_can_have_Fun_t0day!!!#0919}

[DASCTF2020-4]not RSA

relating: [网鼎杯2020华南区复赛]paillier

paillier-2

$n$比较小，直接yafu分解或者费马分解都可以。

c = 29088911054711509252215615231015162998042579425917914434962376243477176757448053722602422672251758332052330100944900171067962180230120924963561223495629695702541446456981441239486190458125750543542379899722558637306740763104274377031599875275807723323394379557227060332005571272240560453811389162371812183549
n = 6401013954612445818165507289870580041358569258817613282142852881965884799988941535910939664068503367303343695466899335792545332690862283029809823423608093

from gmpy2 import *
from Crypto.Util.number import *
# yafu
p = 80006336965345725157774618059504992841841040207998249416678435780577798937819
q = 80006336965345725157774618059504992841841040207998249416678435780577798937447

L = lambda x: (x - 1) // n
lam = (p - 1)*(q - 1)
miu = invert(lam, n)

m = L(pow(c, int(lam), n*n)) * miu % n
print(m)
print(long_to_bytes(m))

[GKCTF2020]Backdoor

1
2
3

1. cve查看漏洞，对n进行爆破，求解p,q
2. pub.pem提取e,n flag.enc提取c
3. ==> Original_RSA()

1	p=kM+(65537*a %M)

$p = k \times M + (65537^{a} mod M)$BackdoorCVE求解p,q

https://asecuritysite.com/encryption/copper

[NepCTF2022]中学数学

1
2
3

# 核心生成
p = getPrime(1024)
q = next_prime(p + (p >> 500))

q = next_prime(p+(p>>500))

转换成数学公式$q = p + \frac{1}{2^{500}}\cdot{p} + r = (1 + \frac{1}{2^{500}})p + r$

此时：$r$为凑到素数的最小整数

n = p*q

代入$q$得到：
$$
n = p\cdot q
$$

$$
n = p\cdot((1+\frac{1}{2^{500}})p + r)
$$

$$
n = (1+\frac{1}{2^{500}})\cdot p^{2} + r\cdot p
$$

凑平方

等式左右两边同时乘上$(1+\frac{1}{2^{500}})$，凑出平方：
$$
(1+ \frac{1}{2^{500}})n = ((1+\frac{1}{2^{500}})p)^{2}+(1+\frac{1}{2^{500}})rp
\ > ((1+\frac{1}{2^{500}})p)^{2}
$$

进行约束计算

$$
(1+ \frac{1}{2^{500}})n = ((1+\frac{1}{2^{500}})p)^{2}+(1+\frac{1}{2^{500}})rp \tag1
$$

$$
q^{2} = ((1+\frac{1}{2^{500}})p + r)^{2}=((1+ \frac{1}{2^{500}})p)^{2} + (1+\frac{1}{2^{500}})rp + (1+\frac{1}{2^{500}})rp + r^{2} \tag2\
$$

显然$(2)$大于$(1)$

结论

$$
(1+\frac{1}{2^{500}})p < \sqrt{n(1+\frac{1}{2^{500}}}) < (1+\frac{1}{2^{500}})p+r = q
$$

此时next_prime(iroot(n+(n>>500))[0])为$q$，然后转换成基础RSA。

根据结论得到q，转换成基础RSA

1
2
3

q = next_prime(iroot(n+(n>>500), 2)[0])
p = n // q
# 转换成基础RSA

[NewStarCTF2022]RSA_begin

Level5-ppq型hint/简单数学推导

已知：

e = 0x10001
n = p * p * q
N = (p-1)*(q-1)*(p)
d = inverse(e, N)

$$
c \equiv m^{e} \mod n
$$

$$
hint \equiv d^{e} \mod n
$$

$$
de \equiv 1 \mod \varphi(n)
$$

根据已知条件进行推导
$$
d^{e} = hint + k_{1} \cdot p\ \tag{1}
$$

$$
d\cdot e = 1 + k_{2}\cdot p \tag{2}
$$

通过同余性对（2）式进行变形，并代入（1）式
$$
(d\cdot e)^{e} = 1 + k_{3}\cdot p \tag{3}
$$

$$
d^{e}\cdot e^{e} = hint\cdot e^{e} + k_{4}\cdot p
$$

整理得（5），即左边含$p$因子
$$
hint\cdot e^{e} - 1 = k_{5}\cdot p \tag{5}
$$
又因为$n = p\cdot p\cdot q$

所以最终可得到
$$
gcd(hint\cdot e^{e} - 1, n) = p \tag{6}
$$
通过（6），即可把关键因素$p$求解出来。

-------------THE END-------------

[DASCTF 2023 & 0X401]ezAlgebra

Coppersmith-已知高位攻击

方程组求解-groebner_basis()

[DASCTF 2023 & 0X401]ezRSA

coppersmith-已知高位求解p

Franklin Reiter 相关信息攻击

[宁波天一杯]rsa

法1——构造$f$

法2——pollard’s rho

法3——非预期

法4——化简进行分解

总exp

[CryptoCTF2021]HAMUL

[DCIC2023-final]easybag

[DCIC2023-final]ddddhm

part_d的求解

coppersmith攻击-已知d低位

[HDCTF2023]math_rsa

[HUBUCTF 2022 新生赛]ezMath

[NSSCTF-round11]ez_fac

[DCIC2023]math_exam

challenge 1

challenge 2

challenge 3

CODE

[NSSCTF-round11]ez_signin

[DASCTF2020-4]not RSA

[GKCTF2020]Backdoor

$p = k \times M + (65537^{a} mod M)$BackdoorCVE求解p,q

[NepCTF2022]中学数学

q = next_prime(p+(p>>500))

n = p*q

凑平方

进行约束计算

结论

根据结论得到q，转换成基础RSA

[NewStarCTF2022]RSA_begin

Level5-ppq型hint/简单数学推导