2023红明谷-Crypto

Match

Created At : 2023-04-20 14:42

Count:772 Views 👀 :

It Takes Two!

It Takes Two!

from sage.all import *
from Crypto.Util.number import *
from os import urandom
from secret import flag

n = 16
bound = 2 ^ 15

A = [ZZ.random_element(-bound, bound) for _ in range(n * n)]
A = Matrix(ZZ, n, n, A)

B = [ZZ.random_element(-bound, bound) for _ in range(n * n)]
B = Matrix(ZZ, n, n, B)

res = []
for i in range(5):
    bound = 2 ^ 15
    S = [ZZ.random_element(-bound, bound) for _ in range(n * n)]
    S = Matrix(ZZ, n, n, S)

    tmp = []
    for i in range(0, 60):
        S = S * A + B
        bound = 2 ^ (int(S[0, 0]).bit_length())
        if i % 3 == 2:
            tmp.append(Matrix(ZZ, n, n, [ZZ.random_element(-bound, bound) for _ in range(n * n)]))
            continue
        tmp.append(S)
    res.append(tmp)

e = A.LLL().determinant()

p = getPrime(512)
q = getPrime(512)
n = p * q
m = bytes_to_long(urandom(int(n).bit_length() // 8 - len(flag) - 1) + flag)
c = pow(m, e, n)
h1 = pow(p + q, e, n)
h2 = pow(p - q, e, n)

f = open('双人成行.txt', 'w')
f.writelines(str(res) + '\n')
f.writelines(str(n) + '\n')
f.writelines(str(c) + '\n')
f.writelines(str(h1) + '\n')
f.writelines(str(h2) + '\n')
f.close()

先利用res中S和A、B矩阵的关系解出A来，进一步求e：

$S_2 = S_1A + B$

$S_5 = S_4A + B$

$相减\Rightarrow A = (S_4-S_1)^{-1}(S_5-S_2)$

（$S_3$是未知的）这里我搞不懂怎么从文本给的数据里进行转换，总不能一个一个手动换吧。

参考大佬的做法：

with open('C:\\Users\\lenovo\\Desktop\\双人成行.txt', 'r') as f:
    s = f.read()
s = s.replace('[',' ').replace('\n','').replace(']',' ').replace(',',' ')
res = []
num = ''
for i in s:
    if i == ' ' and num != '':
        res.append(int(num))
        num = ''
        continue
    if i == ' ' and num == '':
        continue
    else:
        num += i

s1 = res[:256]
s2 = res[256:512]
s4 = res[768:1024]
s5 = res[1024:1280]
print(res_S1)
print(res_S2)
print(res_S4)
print(res_S5)

#sage
S1 = Matrix(ZZ,16,16,s1)
S2 = Matrix(ZZ,16,16,s2)
S4 = Matrix(ZZ,16,16,s4)
S5 = Matrix(ZZ,16,16,s5)
A = (S4-S1).inverse()*(S5-S2)
e = A.LLL().determinant()
print(e)
#183183094232895496570030296666322746922054965594187733500344545328263827233

接着运用二项式定理，通过h1和h2推p、q：

$h_1 = p^e+q^e +k_1n$

$h_2 = p^e-q^e + k_2n$

$\Rightarrow h_1+h_2 = 2p^e mod n$

故$p = gcd(h1+h2,n)$。接着解RSA，发现$gcd(e,(p-1)*(q-1)) == 21$，做过e与$\phi(n)$不互素的，但这里似乎是新的类型，值得记录。

先除公因数21，再在有限域开方。

#sage
def decrypt(p, q, e, c):
    res = []
    R.< x > = Zmod(p)[]
    f = x ^ e - c
    f = f.monic()
    res1 = f.roots()

    R.< x > = Zmod(q)[]
    f = x ^ e - c
    f = f.monic()
    res2 = f.roots()

    for i in res1:
        for j in res2:
            m = CRT(int(i[0]), int(j[0]), p, q)
            res.append(m)
    return res
n = 126930298936285661712486297662920895162569606037310367763354747221281175771655642407136326621695910623038808779778530112406355314071209370688157872928010633181351390724545013677593062556323119308457918805555312069055604237211117650220178416298165021603211366843640334616217695418858036626587483782452105122653
c = 113627841667808982839757084973426219545127121566516056267404541633803040730885409234473068650543791446730694746311695177758797711077000091232969424826171863685060090359260225102836081852105845748467870581394884564134418376982186965340367386781824886506478939204791426457255483148486730526127180397268053506840
h1 = 87021607670080656750728189202811647321664825322085967432146885995538140004901574830625347954724344331514731852873721100175299656618161173874818773415684739773055620673258848991693719847569489515642296650035465632567910004553054397894647697286044465567405142149926303968235362573821060105908856127568162452912
h2 = 70528801000055618659638315463133504198238507722722570127215098017082205934290867816695737682738831717228470799826957490782948760796844881508632060312080331264474968266753069687287034453036854258618280625776346633340081217397502423530180647548747144401922660710323623212890923488339464759360304751017490144695
e = 183183094232895496570030296666322746922054965594187733500344545328263827233
p = gcd(h1+h2,n)
q = n // p
phi_n = (p-1)*(q-1)
d = inverse_mod(e//21, phi_n)
m = pow(c,d,n)

flag = decrypt(p, q, 21, m)

因为我在kali上用的sage，还没安转字节串的函数（准确的说我没有仔细了解过，只顾着用了），只能把m存下来，在py上运行了，很蠢的做法：

flag = [...]
for i in flag:
    m = long_to_bytes(i)
    if b'flag' in m:
        print(m)
#flag{5a6814eb-8848-11ed-aee3-d812656dd8d8}

另外一种做法是用AMM算法，还没学过，待补充。。。

大佬写的更详细：

2023红明谷-WriteUp (qq.com)

(3条消息) 2023第三届红明谷CTF Crypto_无趣的浅的博客-CSDN博客

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1666739907@qq.com