[ACTF 2022]RSA Leak

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
from sage.all import *
from secret import flag
from Crypto.Util.number import bytes_to_long


def leak(a, b):
    p = random_prime(pow(2, 64))
    q = random_prime(pow(2, 64))
    n = p*q
    e = 65537
    print(n)
    print((pow(a, e) + pow(b, e) + 0xdeadbeef) % n)


def gen_key():
    a = randrange(0, pow(2,256))
    b = randrange(0, pow(2,256))
    p = pow(a, 4)
    q = pow(b, 4)
    rp = randrange(0, pow(2,24))
    rq = randrange(0, pow(2,24))
    pp = next_prime(p+rp)
    qq = next_prime(q+rq)
    if pp % pow(2, 4) == (pp-p) % pow(2, 4) and qq % pow(2, 4) == (qq-q) % pow(2, 4):
        n = pp*qq
        rp = pp-p
        rq = qq-q
        return n, rp, rq
    
n, rp, rq = gen_key()
e = 65537
c = pow(bytes_to_long(flag), e, n)
print("n =", n)
print("e =", e)
print("c =", c)
print("=======leak=======")
leak(rp, rq)

'''
n = 3183573836769699313763043722513486503160533089470716348487649113450828830224151824106050562868640291712433283679799855890306945562430572137128269318944453041825476154913676849658599642113896525291798525533722805116041675462675732995881671359593602584751304602244415149859346875340361740775463623467503186824385780851920136368593725535779854726168687179051303851797111239451264183276544616736820298054063232641359775128753071340474714720534858295660426278356630743758247422916519687362426114443660989774519751234591819547129288719863041972824405872212208118093577184659446552017086531002340663509215501866212294702743
e = 65537
c = 48433948078708266558408900822131846839473472350405274958254566291017137879542806238459456400958349315245447486509633749276746053786868315163583443030289607980449076267295483248068122553237802668045588106193692102901936355277693449867608379899254200590252441986645643511838233803828204450622023993363140246583650322952060860867801081687288233255776380790653361695125971596448862744165007007840033270102756536056501059098523990991260352123691349393725158028931174218091973919457078350257978338294099849690514328273829474324145569140386584429042884336459789499705672633475010234403132893629856284982320249119974872840
=======leak=======
122146249659110799196678177080657779971
90846368443479079691227824315092288065
'''

破解leak

先把leak的n直接用yafu分解出来，解leak找到两种方法，一种是打表爆破（在程序中一次性计算出所有用到的结果，之后的查询直接取这些结果，和中间相遇攻击类似）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from tqdm import tqdm

def de_leak():
    n=122146249659110799196678177080657779971
    p=8949458376079230661
    q=13648451618657980711
    e=65537
    c=90846368443479079691227824315092288065
    c=c-0xdeadbeef
    dict={}
    for rp in tqdm(range(1,2**24)):
        tmp=(c-pow(rp,e,n))%n
        dict[tmp]=rp
    for rq in tqdm(range(1,2**24)):
        tmp=pow(rq,e,n)
        if tmp in dict.keys():
            print(rq,dict[tmp])
            break

de_leak()

另一种可以直接一遍计算，求逆元寻找符合要求的rp,rq：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import gmpy2

n1 = 122146249659110799196678177080657779971
p1 = 8949458376079230661
q1 = 13648451618657980711
e1 = 65537
d1 = gmpy2.invert(e1,(p1-1)*(q1-1))
c1 = 90846368443479079691227824315092288065

for i in range(2**24):
    c11 = (c1 - 0xdeadbeef - pow(i,e1,n1))%n1
    rp = pow(c11,d1,n1)
    if len(bin(rp))<=26:
        rq = i
        print(rp,i)
        break

得flag

由于一些参数数值过小可以忽略，所以以下可以直接推出：

直接开方就可以得到$ab$，进而得到$pq$的准确值。

实际上：

得到$n-rprq-(ab)^4=prq+qrp=M$，求出$M$，同时乘$q$：

二次方程求解，然后得到$qq=q+rq$，同理能得到$pp$：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import gmpy2
from Crypto.Util.number import *

n1 = 122146249659110799196678177080657779971
p1 = 8949458376079230661
q1 = 13648451618657980711
e1 = 65537
d1 = gmpy2.invert(e1, (p1 - 1) * (q1 - 1))
c1 = 90846368443479079691227824315092288065
n = 3183573836769699313763043722513486503160533089470716348487649113450828830224151824106050562868640291712433283679799855890306945562430572137128269318944453041825476154913676849658599642113896525291798525533722805116041675462675732995881671359593602584751304602244415149859346875340361740775463623467503186824385780851920136368593725535779854726168687179051303851797111239451264183276544616736820298054063232641359775128753071340474714720534858295660426278356630743758247422916519687362426114443660989774519751234591819547129288719863041972824405872212208118093577184659446552017086531002340663509215501866212294702743
e = 65537
c = 48433948078708266558408900822131846839473472350405274958254566291017137879542806238459456400958349315245447486509633749276746053786868315163583443030289607980449076267295483248068122553237802668045588106193692102901936355277693449867608379899254200590252441986645643511838233803828204450622023993363140246583650322952060860867801081687288233255776380790653361695125971596448862744165007007840033270102756536056501059098523990991260352123691349393725158028931174218091973919457078350257978338294099849690514328273829474324145569140386584429042884336459789499705672633475010234403132893629856284982320249119974872840


for i in range(2**24):
    c11 = (c1 - 0xDEADBEEF - pow(i, e1, n1)) % n1
    rp = pow(c11, d1, n1)
    if len(bin(rp)) <= 26:
        rq = i
        break

a_mul_b = (gmpy2.iroot(n, 4)[0]) ** 4
s = n - rp * rq - a_mul_b
delta = s**2 - 4 * rq * rp * a_mul_b
p = (s - gmpy2.iroot(delta, 2)[0]) // (2 * rq)
pp = p + rp
qq = n // pp
print(pp * qq == n)
d = gmpy2.invert(65537, (pp - 1) * (qq - 1))
print(long_to_bytes(pow(c, d, n)))

[羊城杯 2020]GMC

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
from Crypto.Util.number import getPrime,bytes_to_long,getRandomNBitInteger
from secret import flag
from gmpy2 import gcd


def gmc(a, p):
    if pow(a, (p-1)//2, p) == 1:
        return 1
    else:
        return -1


def gen_key():
    [gp,gq] = [getPrime(512) for i in range(2)]
    gN = gp * gq
    return gN, gq, gp


def gen_x(gq,gp):
    while True:
        x = getRandomNBitInteger(512)
        if gmc(x,gp) ^ gmc(x,gq) == -2:
            return x


def gen_y(gN):
    gy_list = []
    while len(gy_list) != F_LEN:
        ty = getRandomNBitInteger(768)
        if gcd(ty,gN) == 1:
            gy_list.append(ty)
    return gy_list


if __name__ == '__main__':

    flag = bin(bytes_to_long(flag))[2:]
    F_LEN = len(flag)
    N, q, p = gen_key()
    x = gen_x(q, p)
    y_list = gen_y(N)
    ciphertext = []

    for i in range(F_LEN):
        tc = pow(y_list[i],2) * pow(x,int(flag[i])) % N
        ciphertext.append(tc)

    with open('./output.txt','w') as f:
        f.write(str(N) + '\n')
        for i in range(F_LEN):
            f.write(str(ciphertext[i]) + '\n')

这道题牵扯到有关二次剩余和雅可比符号的相关知识，太久没看了再复习一下：

设$a\in Z_n$且互素有逆元，如果$b^2\equiv a\pmod n,b\in Z$，那么$a$为模$n$下的二次剩余（勒让德符号值为$1$），反之称为二次非剩余（勒让德符号值为$-1$）。

有一个比较常用的性质：

设$a\in Z$，$n$为正奇数，$n=p_1…p_t$，$p_i$都为奇素数（彼此可以相等），雅可比符号定义为：

回到这个题目：

1
2
3
4
5
def gmc(a, p):
    if pow(a, (p-1)//2, p) == 1:
        return 1
    else:
        return -1

根据$gx$的生成方式，发现$gx$和$gn$的两个因子的其中一个是二次剩余，另一个不是二次剩余，对于关键的加密函数：

1
tc = pow(y_list[i],2) * pow(x,int(flag[i])) % N

$y^2\bmod n$是和$n$满足二次剩余的，$y$就是模幂结果在$n$下的平方根，勒让德符号值为$1$，对于后半部分：$x^i\bmod n$，如果对于二进制flag位$i$为$0$，那么$c$的雅可比符号就是$1$，如果二进制flag位$i$为$1$的话，根据雅克比符号可知，后半部分的雅可比符号值就是$-1$，$c$的雅可比符号就是$-1$。

所以为了得到flag的每个二进制位，我们可以计算$c$和$n$的雅可比符号值，如果$(\frac cn)=1$，那么当前位为$1$，如果为$-1$，二进制位得$0$：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Util.number import *
import gmpy2

with open("output.txt","rb") as f:
    f=f.readlines()
    n=int(f[0])
    flag=""
    for i in f:
        if int(i)!=n:
            res=gmpy2.jacobi(int(i),n)
            if res == -1:
                flag+='1'
            else:
                flag+='0'

print(long_to_bytes(int(flag,2)))