Buuctf刷题 Crypto 3day

来源：恒创科技编辑：恒创科技编辑部

2024-02-11 09:09:59

1、RSA3

类型：共模攻击，其原理是：

两个及以上的公钥来加密同一条信息m，即

c1 = pow(m, e1, n)=(m^e1)%n
c2 = pow(m, e2, n)=(m^e2)%n
其中e1,e2互质，即最大公约数为1，gcd(e1,e2)=1

根据扩展欧几里德算法对于不完全为 0 的整数 a，b，gcd（a，b）表示 a，b 的最大公约数。那么一定存在整数 x，y 使得 gcd（a，b）=ax+by

e1*s1+e2*s2 = 1

s1、s2皆为整数，但是一正一负，假设s1为正数,s2为负数

推导过程：

这里需要用到两条幂运算的性质：

(a * b) % p = (a % p * b % p) % p
a ^ b % p = ((a % p) ^ b) % p

因为c1 = m^e1%n，c2 = m^e2%n，需要证明m=(c1^s1*c2^s2)%n

代入可得：

(c1^s1*c2^s2)%n = ((m^e1%n)^s1(m^e2%n)^s2)%n

                =((m^e1%n)^s1*(m^e2%n)^s2)%n

                =((m^e1)^s1%n*(m^e2)^s2%n)%n   //消掉%n

                =((m^e1)^s1*(m^e2)^s2)%n

                =((m^(e1*s1)*(m^(e2*s2))%n   //幂的乘方，底数不变，指数相乘

                =(m^(e1*s1+e2*s2))%n   //同底数幂相乘，底数不变，指数相加

又因为m<n，所以(c1^s1*c2^s2)%n=m%n=m

脚本：

import gmpy2
from gmpy2 import *
from Crypto.Util.number import *
n = 22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819052430779004755846649044001024141485283286483130702616057274698473611149508798869706347501931583117632710700787228016480127677393649929530416598686027354216422565934459015161927613607902831542857977859612596282353679327773303727004407262197231586324599181983572622404590354084541788062262164510140605868122410388090174420147752408554129789760902300898046273909007852818474030770699647647363015102118956737673941354217692696044969695308506436573142565573487583507037356944848039864382339216266670673567488871508925311154801
c1 = 22322035275663237041646893770451933509324701913484303338076210603542612758956262869640822486470121149424485571361007421293675516338822195280313794991136048140918842471219840263536338886250492682739436410013436651161720725855484866690084788721349555662019879081501113222996123305533009325964377798892703161521852805956811219563883312896330156298621674684353919547558127920925706842808914762199011054955816534977675267395009575347820387073483928425066536361482774892370969520740304287456555508933372782327506569010772537497541764311429052216291198932092617792645253901478910801592878203564861118912045464959832566051361
c2 = 18702010045187015556548691642394982835669262147230212731309938675226458555210425972429418449273410535387985931036711854265623905066805665751803269106880746769003478900791099590239513925449748814075904017471585572848473556490565450062664706449128415834787961947266259789785962922238701134079720414228414066193071495304612341052987455615930023536823801499269773357186087452747500840640419365011554421183037505653461286732740983702740822671148045619497667184586123657285604061875653909567822328914065337797733444640351518775487649819978262363617265797982843179630888729407238496650987720428708217115257989007867331698397
e1 = 11187289
e2 = 9647291
s = gmpy2.gcdext(e1,e2) #扩展欧几里得算法(e1, e2),在已知x，y时，求解一组解a,b，使得ax+by = gcd(x，y)=1
s1 = s[1]
s2 = s[2]
# 求模反元素
if s1<0:
    s1 = - s1
    c1 = invert(c1, n)

elif s2<0:
    s2 = - s2
    c2 = invert(c2, n)

m = pow(c1,s1,n)*pow(c2,s2,n) % n
print(long_to_bytes(m))

得到最终答案flag{49d91077a1abcb14f1a9d546c80be9ef}

2、RSA2

类型：dp+n+e+c = m dp泄露

e = 65537
n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657
c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751

原理：

dp≡d mod (p-1)

dp*e≡d*e mod (p-1)

d*e≡k*(p-1)+dp*e ⑴

变形后的公式与下式结合

d*e≡1 mod φ(n)

因为φ(n)=(p-1)*(q-1)

所以：d*e≡1 mod (p-1)*(q-1) ⑵

根据⑴式和⑵式得：k*(p-1)+dp*e=1 mod (p-1)*(q-1)

将式子化为整式可以得到：k1*(p-1)+dp*e=k2*(p-1)*(q-1)+1

将p-1提出来：dp*e=[k2*(q-1)-k1]*(p-1)+1

设I=k2*(p-1)-k1

dp*e=I*(p-1)+1

因为dp<p-1,所以I<e,所以I∈(0,e)

遍历X （65537种可能）,求出( p − 1 ) 得到p且能被n整除；接下来就是常规RSA的解法:

import gmpy2
from Crypto.Util.number import *
e =65537
n =248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
dp =905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657
c =140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751
for i in range(1,e):
    if (dp*e-1)%i==0:
        if n%(((dp*e-1)//i)+1)==0:
            p=((dp*e-1)//i)+1
            q=n//(((dp*e-1)//i)+1)
            phi=(p-1)*(q-1)
            d=gmpy2.invert(e,phi)
            m=pow(c,d,n)
print(m)  # 10进制明文
print(long_to_bytes(m))

得到答案为flag{wow_leaking_dp_breaks_rsa?_98924743502}

3、Unencode

利用在线Uuencode编码转换工具：https://www.qqxiuzi.cn/bianma/uuencode.php，得到答案flag{dsdasdsa99877LLLKK}

4、[AFCTF2018]Morse

直接用摩斯密码解码，得到一串字符，提交答案发现不对，看到大写字母到F，所以想到16进制，所以考虑一下用16进制转文本https://www.bejson.com/convert/ox2str/，得到答案afctf{1s't_s0_345y}，因为用flag{}形式提交，所以修改为flag{1s't_s0_345y}

Buuctf刷题 Crypto 3day_buuctf

5、异性相吸

刚开始拿到这个题一头雾水，这个密文是乱码的文本，又读了一遍题目，‘异性’在计算机中可能是0和1，所以考虑异或运算

直接写脚本：

a=open('D:\key.txt','rb').read()
b=open('D:\密文.txt','rb').read()
c=''
for i in range(0,len(a)):
    res=(list(a)[i])^(list(b)[i])
    c=c+chr(res)
print(c)

得到答案flag{ea1bc0988992276b7f95b54a7435e89e}

6、还原大师

题目：

我们得到了一串神秘字符串：TASC?O3RJMV?WDJKX?ZM,问号部分是未知大写字母，为了确定这个神秘字符串，我们通过了其他途径获得了这个字串的32位MD5码。但是我们获得它的32位MD5码也是残缺不全，E903???4DAB????08?????51?80??8A?,请猜出神秘字符串的原本模样，并且提交这个字串的32位MD5码作为答案。

注意：得到的 flag 请包上 flag{} 提交

可以通过编写脚本暴力破解：

import hashlib
k='TASC?O3RJMV?WDJKX?ZM'for i in range(26):
    a=k.replace('?',str(chr(65+i)),1)
    for j in range(26):
        b=a.replace('?',str(chr(65+j)),1)
        for n in range(26):
            c=b.replace('?',str(chr(65+n)),1)
            s=hashlib.md5(c.encode('utf8')).hexdigest().upper()
            if s[:4]=='E903':
                print(s)

得到答案flag{E9032994DABAC08080091151380478A2}

7、RSA

看到有公钥，先将公钥解析一下：http://www.hiencode.com/pub_asys.html

Buuctf刷题 Crypto 3day_buuctf_02

将n进行大因数分解：http://www.factordb.com/index.php?query=++8693448229604811919066606200349480058890565601720302561721665405+8378322103517

剩下的交给脚本完成（我是将flag.enc修改为了flag.txt，并放在了脚本目录下）：

import gmpy2
import rsa
p=285960468890451637935629440372639283459
q=304008741604601924494328155975272418463
n=86934482296048119190666062003494800588905656017203025617216654058378322103517
e=65537
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
#print(d)
d=81176168860169991027846870170527607562179635470395365333547868786951080991441
key=rsa.PrivateKey(n,e,d,q,p)  #在pkcs标准中,pkcs#1规定,私钥包含(n,e,d,p,q)
with open('flag.txt','rb') as file:
    file=file.read()
    print(rsa.decrypt(file,key))

得到答案flag{decrypt_256}

8、RSAROLL

先进行质因数分解

Buuctf刷题 Crypto 3day_buuctf_03

得到18443和49891分别对应着p和q，已知e=19

写脚本，data.txt是删除原来文件的第一行，且放在脚本同目录

import gmpy2
n=920139713
p=18443
q=49891e=19
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
result=[]
with open('data.txt','r') as f:
    for i in f.readlines():
        i=i.strip('\n') #去掉列表中的换行符        
        result.append(chr(pow(int(i),d,n)))
for i in result:
    print(i,end='')

得到答案flag{13212je2ue28fy71w8u87y31r78eu1e2}

9、Dangerous RSA

类型：小公钥指数攻击，e很小，n又很大不好分解，这种题目通常有两种类型，一种是直接爆破，另一种是低指数广播攻击

首先介绍一下gmpy2中的iroot(x,n)函数，计算x的第n次根的一个近似的一个整数.如果是整数，第二列是TRUE，否则是FALSE

print(gmpy2.iroot(4, 2))  # (mpz(2), True)
print(gmpy2.iroot(5, 2))  # (mpz(2), False)

思路：

有RSA加密公式： C=M^e % n (C密文，M明文)

则Ｍ^e = kn + C，对K进行爆破，只要k满足 kn + C能够开e次方就可以得明文

from gmpy2 import *
import libnum
n=0x52d483c27cd806550fbe0e37a61af2e7cf5e0efb723dfc81174c918a27627779b21fa3c851e9e94188eaee3d5cd6f752406a43fbecb53e80836ff1e185d3ccd7782ea846c2e91a7b0808986666e0bdadbfb7bdd65670a589a4d2478e9adcafe97c6ee23614bcb2ecc23580f4d2e3cc1ecfec25c50da4bc754dde6c8bfd8d1fc16956c74d8e9196046a01dc9f3024e11461c294f29d7421140732fedacac97b8fe50999117d27943c953f18c4ff4f8c258d839764078d4b6ef6e8591e0ff5563b31a39e6374d0d41c8c46921c25e5904a817ef8e39e5c9b71225a83269693e0b7e3218fc5e5a1e8412ba16e588b3d6ac536dce39fcdfce81eec79979ea6872793e= 0x3c=0x10652cdfaa6b63f6d7bd1109da08181e500e5643f5b240a9024bfa84d5f2cac9310562978347bb232d63e7289283871efab83d84ff5a7b64a94a79d34cfbd4ef121723ba1f663e514f83f6f01492b4e13e1bb4296d96ea5a353d3bf2edd2f449c03c4a3e995237985a596908adc741f32365
k=0
while 1:
    res=iroot(c+k*n,3)  #c+k*n 开3次方根 能开3次方即可    
    if(res[1]==True):
        print(libnum.n2s(int(res[0])))  #转为字符串        
        break    
        k=k+1

运行得到答案flag{25df8caf006ee5db94d48144c33b2c3b}

10、[HDCTF2019]basic rsa

题目给了一串代码：

import gmpy2
from Crypto.Util.number import *
from binascii import a2b_hex,b2a_hex
flag = "*****************"
p = 262248800182277040650192055439906580479
q = 262854994239322828547925595487519915551
e = 65533
n = p*q
c = pow(int(b2a_hex(flag),16),e,n)
print(c)
# 27565231154623519221597938803435789010285480123476977081867877272451638645710

这是最基础的RSA，可以直接写脚本：

from Crypto.Util.number import *
import gmpy2
p = 262248800182277040650192055439906580479
q = 262854994239322828547925595487519915551
c=27565231154623519221597938803435789010285480123476977081867877272451638645710
e = 65533
n=p*q
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))