RSA加密算法

rsa基本组成

在RSA加密算法中，以下是常用的符号和对应的含义：

e：公钥指数（exponent），用于加密操作。通常为一个较小的固定值，例如65537。

p和q：两个不同的大素数，用于生成RSA密钥对。它们的乘积n (n = p * q) 是模数（modulus），用于加密和解密操作。

d：私钥指数（exponent），用于解密操作。它通过使用扩展欧几里得算法计算得到，满足 e * d ≡ 1 (mod φ(n))，其中 φ(n) 是欧拉函数值。

n：模数（modulus），也是公钥和私钥共享的一个参数。它是两个素数 p 和 q 的乘积，即 n = p * q。

φ(n)即phi：欧拉函数（Euler’s totient function）的值，表示与 n 互质的正整数的数量。对于两个素数 p 和 q 的乘积 n，φ(n) = (p-1)*(q-1)。

m：明文（plaintext），需要被加密的消息或数据。m=c^d mod n

c: 密文，c=m^e mod n

总结：
e是公钥指数，p和q是素数，d是私钥指数，n是模数，phi是欧拉函数值，m是明文。

已知p,q,e求d（rsa）

我们导入python的gmpy2库，这个库求rsa超好用

1
2
3
4
5
6
7
8
from gmpy2 import invert
p=473398607161
q=4511491
e=17
phi=(p-1)*(q-1)
d=invert(e,phi)
print(d)
#flag{125631357777427553}

成功得到flag

已知p,q,e,c 求明文m [buu rsarsa题]

1
2
3
4
5
6
7
8
9
10
11
12
from libnum import n2s,s2n
from gmpy2 import *
p =9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483
q =11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407
e =65537
phi=(p-1)*(q-1)
n=p*q
c =83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034
d=invert(e,phi)
m=pow(c,d,n)
print((int(m)))
#flag{5577446633554466577768879988}

已知p,q,dp,dq,c 求明文m [buu RSA1题]

http://t.csdnimg.cn/KOuWf

小记一下：在RSA密码中，dp和dq是私钥的参数，用于加速中国剩余定理（Chinese Remainder Theorem, CRT）解密算法。

dp：是d对p-1的模反元素（modular inverse）。即 dp = d mod (p-1)。

dq：是d对q-1的模反元素。即 dq = d mod (q-1)。

这两个参数在CRT解密算法中起到加速解密过程的作用，通过使用CRT算法可以减少模幂运算的计算量，提高解密效率。具体来说，当进行解密时，先对密文进行两次模幂运算，分别使用dp和dq，并分别取得结果m1和m2。然后根据CRT算法，使用p、q、dp、dq以及模数n计算出明文m。这种方式相比于直接使用d进行模幂运算，能够大大提高解密速度。

m = (m1 + (I * (m2 - m1)) * p) % n

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from libnum import n2s,s2n
from gmpy2 import *
p=8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229
q=12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469
dp=6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929
dq=783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041
c=24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852
I=invert(p,q) //求p和q的逆元
n=p*q
m1=pow(c,dp,p)
m2=pow(c,dq,q)
m = (m1 + (I * (m2 - m1)) * p) % n    #求明文公式
print(n2s(int(m)))
#noxCTF{W31c0m3_70_Ch1n470wn}——>flag{W31c0m3_70_Ch1n470wn}

逆元

给定整数 𝑎a 和模数 𝑚m，如果存在一个整数 𝑥x，使得：

𝑎⋅𝑥≡1(mod𝑚)a⋅x≡1(modm)

那么这个 𝑥x 就是 𝑎a 的模 𝑚m 下的乘法逆元，记作 𝑎−1(mod 𝑚)a−1(mod m)。

已知e1,e2,c1,c2,n 求明文m(共模攻击）[buu RSA3]

小记一下：

根据给定的参数 e1、e2、c1、c2 和模数 n，下面是求解明文 m 的一般步骤：

使用扩展欧几里得算法计算 e1 和 e2 的最大公约数 gcd(e1, e2)。确保它等于 1，否则无法进行共模攻击。

计算 e1 在模 e2 下的模反元素 s1 = e1^-1 mod e2，以及 e2 在模 e1 下的模反元素 s2 = e2^-1 mod e1。

计算明文 m：

计算 x = (c1^s1 * c2^s2) mod n。
计算 m = x mod n。
需要注意的是，在实际计算过程中，可以使用模幂运算算法和模反元素算法来进行计算。

此外，如果 m 不在 0 到 n-1 的范围内，还需要对结果进行适当的调整，以保证明文 m 在正确的范围内。

1
2
3
4
5
6
7
8
9
10
11
12
13
from gmpy2 import *
c1 = 22322035275663237041646893770451933509324701913484303338076210603542612758956262869640822486470121149424485571361007421293675516338822195280313794991136048140918842471219840263536338886250492682739436410013436651161720725855484866690084788721349555662019879081501113222996123305533009325964377798892703161521852805956811219563883312896330156298621674684353919547558127920925706842808914762199011054955816534977675267395009575347820387073483928425066536361482774892370969520740304287456555508933372782327506569010772537497541764311429052216291198932092617792645253901478910801592878203564861118912045464959832566051361
n = 22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819052430779004755846649044001024141485283286483130702616057274698473611149508798869706347501931583117632710700787228016480127677393649929530416598686027354216422565934459015161927613607902831542857977859612596282353679327773303727004407262197231586324599181983572622404590354084541788062262164510140605868122410388090174420147752408554129789760902300898046273909007852818474030770699647647363015102118956737673941354217692696044969695308506436573142565573487583507037356944848039864382339216266670673567488871508925311154801
e1 = 11187289
c2 = 18702010045187015556548691642394982835669262147230212731309938675226458555210425972429418449273410535387985931036711854265623905066805665751803269106880746769003478900791099590239513925449748814075904017471585572848473556490565450062664706449128415834787961947266259789785962922238701134079720414228414066193071495304612341052987455615930023536823801499269773357186087452747500840640419365011554421183037505653461286732740983702740822671148045619497667184586123657285604061875653909567822328914065337797733444640351518775487649819978262363617265797982843179630888729407238496650987720428708217115257989007867331698397
e2 = 9647291
# 扩展欧几里得算法
# return (r,s1,s2) 其中，r为e1和e2的最大公约数，s1 s2满足e1*s1 + e2*s2 = 1
r,s1, s2 = gcdext(e1, e2)  # 计算s1，s2,此处r=1,符合共模攻击
m = (powmod(c1, s1, n) * powmod(c2, s2, n)) % n  # 计算明文m
m = hex(m)[2:] # 例如 "0x1f",通过切片操作 [2:]，我们去掉了前两个字符，即 "0x"，只保留了后面的部分，例如 "1f"。
print(bytes.fromhex(m).decode())
#flag{49d91077a1abcb14f1a9d546c80be9ef}

已知e,n,dp,c 求明文m（dp泄露）[buu RSA2题]

小记一下:

dp=d%(p-1)

dq=d%(q-1)

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from gmpy2 import *
e = 65537
n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657

c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751

for i in range(1, e):  # 在范围(1,e)之间进行遍历
    if (dp * e - 1) % i == 0:
        if n % (((dp * e - 1) // i) + 1) == 0:  # 存在p，使得n能被p整除
            p = ((dp * e - 1) // i) + 1
            q = n // (((dp * e - 1) // i) + 1)
            phi = (q - 1) * (p - 1)  # 欧拉定理
            d =invert(e, phi)  # 求模逆
            m = pow(c, d, n)  # 快速求幂取模运算
m=hex(m)[2:]
print(bytes.fromhex(m).decode())

#flag{wow_leaking_dp_breaks_rsa?_98924743502}

已知p,q,e,n,文件加密密文 求密文m [buu RSA题]

在这里插入图片描述在这里插入图片描述

公钥解析后得到e和n，分解质因数得到p,q，顺势得到d

e= 65537

n=86934482296048119190666062003494800588905656017203025617216654058378322103517

p= 285960468890451637935629440372639283459

q= 304008741604601924494328155975272418463

d=81176168860169991027846870170527607562179635470395365333547868786951080991441
enc文件不能直接读，应该用代码读

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Util.number import bytes_to_long
with open("C:\\Users\\11\\Downloads\\0eaf8d6c-3fe5-4549-9e81-94ac42535e7b\\flag.enc","rb") as f:  #以二进制读模式，读取密文
    f = f.read()
    print(bytes_to_long(f))
    #c=29666689760194689065394649908301285751747553295673979512822807815563732622178
from Crypto.Util.number import bytes_to_long
from libnum import n2s
e= 65537
n=86934482296048119190666062003494800588905656017203025617216654058378322103517
p= 285960468890451637935629440372639283459
q= 304008741604601924494328155975272418463
d=81176168860169991027846870170527607562179635470395365333547868786951080991441
c=29666689760194689065394649908301285751747553295673979512822807815563732622178
m=pow(c,d,n)
print(n2s(m))
//b'\x02\x9d {zR\x1e\x08\xe4\xe6\x18\x06\x00flag{decrypt_256}\n'

已知p+q，(p+1)*(q+1),c,d求明文m（[GUET-CTF2019]BabyRSA ）

(p+1)(q+1)=pq+1+p+q

n=p*q

m=c^d mod n

写个脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
from libnum import n2s
a=0x1232fecb92adead91613e7d9ae5e36fe6bb765317d6ed38ad890b4073539a6231a6620584cea5730b5af83a3e80cf30141282c97be4400e33307573af6b25e2ea
b= 0x5248becef1d925d45705a7302700d6a0ffe5877fddf9451a9c1181c4d82365806085fd86fbaab08b6fc66a967b2566d743c626547203b34ea3fdb1bc06dd3bb765fd8b919e3bd2cb15bc175c9498f9d9a0e216c2dde64d81255fa4c05a1ee619fc1fc505285a239e7bc655ec6605d9693078b800ee80931a7a0c84f33c851740
e =0xe6b1bee47bd63f615c7d0a43c529d219
d =0x2dde7fbaed477f6d62838d55b0d0964868cf6efb2c282a5f13e6008ce7317a24cb57aec49ef0d738919f47cdcd9677cd52ac2293ec5938aa198f962678b5cd0da344453f521a69b2ac03647cdd8339f4e38cec452d54e60698833d67f9315c02ddaa4c79ebaa902c605d7bda32ce970541b2d9a17d62b52df813b2fb0c5ab1a5
c =0x50ae00623211ba6089ddfae21e204ab616f6c9d294e913550af3d66e85d0c0693ed53ed55c46d8cca1d7c2ad44839030df26b70f22a8567171a759b76fe5f07b3c5a6ec89117ed0a36c0950956b9cde880c575737f779143f921d745ac3bb0e379c05d9a3cc6bf0bea8aa91e4d5e752c7eb46b2e023edbc07d24a7c460a34a9a

n=b-1-a

flag=pow(c,d,n)
print(n2s(flag))

//b'flag{cc7490e-78ab-11e9-b422-8ba97e5da1fd}'

Dangerous RSA（低加密指数攻击）

sa 的加密 为 c = m ^ e mod n

当e 很小，n很大 时，有两种情况

  1. m ^ e 有可能小于 n 。 此时， c = m ^ e 。 密文 m = c 开e次方

  2. 当 m ^ e > n 。 此时。 m ^ e = kn + c 。 k 是整数 。对 k 进行爆破，就能找到对应的m

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#python3
## -*- coding: utf-8 -*-#
from gmpy2 import iroot
import libnum
e = 0x3
n = 0x52d483c27cd806550fbe0e37a61af2e7cf5e0efb723dfc81174c918a27627779b21fa3c851e9e94188eaee3d5cd6f752406a43fbecb53e80836ff1e185d3ccd7782ea846c2e91a7b0808986666e0bdadbfb7bdd65670a589a4d2478e9adcafe97c6ee23614bcb2ecc23580f4d2e3cc1ecfec25c50da4bc754dde6c8bfd8d1fc16956c74d8e9196046a01dc9f3024e11461c294f29d7421140732fedacac97b8fe50999117d27943c953f18c4ff4f8c258d839764078d4b6ef6e8591e0ff5563b31a39e6374d0d41c8c46921c25e5904a817ef8e39e5c9b71225a83269693e0b7e3218fc5e5a1e8412ba16e588b3d6ac536dce39fcdfce81eec79979ea6872793
c = 0x10652cdfaa6b63f6d7bd1109da08181e500e5643f5b240a9024bfa84d5f2cac9310562978347bb232d63e7289283871efab83d84ff5a7b64a94a79d34cfbd4ef121723ba1f663e514f83f6f01492b4e13e1bb4296d96ea5a353d3bf2edd2f449c03c4a3e995237985a596908adc741f32365
 
k = 0
while 1:
    res = iroot(c+k*n,e)  #c+k*n 开3次方根 能开3次方即可
    #print(res)
    #res = (mpz(13040004482819713819817340524563023159919305047824600478799740488797710355579494486728991357), True)
    if(res[1] == True):
        print(libnum.n2s(int(res[0]))) #转为字符串
        break
    k=k+1
    
#b'flag{25df8caf006ee5db94d48144c33b2c3b}'

iroot(c+k*n,e)为c+k*n开e次方

mpz用来处理大整数和需要高精度运算

RSAROLL（rsa）

image-20240604171521223

题目信息没看懂，找大佬的wp才知道{920139713,19}，一个是n，一个是e，后面那一大串是拆分的c

我们通过网站分解n得到

p= 18443

q=49891

所以已知信息有

p= 18443

q=49891

n=920139713

e=19

我们写脚本来爆c

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
52
53
54
import libnum
from Crypto.Util.number import long_to_bytes
from gmpy2 import *
list1 = [704796792,
         752211152,
         274704164,
         18414022,
         368270835,
         483295235,
         263072905,
         459788476,
         483295235,
         459788476,
         663551792,
         475206804,
         459788476,
         428313374,
         475206804,
         459788476,
         425392137,
         704796792,
         458265677,
         341524652,
         483295235,
         534149509,
         425392137,
         428313374,
         425392137,
         341524652,
         458265677,
         263072905,
         483295235,
         828509797,
         341524652,
         425392137,
         475206804,
         428313374,
         483295235,
         475206804,
         459788476,
         306220148]
flag = ""
n = 920139713
p = 49891
q = 18443
e = 19

for i in list1:
    c = i
    d = invert(e, (p - 1) * (q - 1))
    m = pow(c, d, n)
    string = long_to_bytes(m)
    flag += string.decode()
print(flag)

得到flag

1
flag{13212je2ue28fy71w8u87y31r78eu1e2}

rsa2

image-20240617213459641

源码长这样，我们需要将N分解为p和q

p=9046853915223503351787031888977627106934564043204783593118678181991596316582877057556463152579621699010610569526573031954779520781448550677767565207407183

q=11273732364123571293429600400343309403733952146912318879993851141423284675797325272321856863528776914709992821287788339848962916204774010644058033316303937

然后改一下代码

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

N = 101991809777553253470276751399264740131157682329252673501792154507006158434432009141995367241962525705950046253400188884658262496534706438791515071885860897552736656899566915731297225817250639873643376310103992170646906557242832893914902053581087502512787303322747780420210884852166586717636559058152544979471
e = 46731919563265721307105180410302518676676135509737992912625092976849075262192092549323082367518264378630543338219025744820916471913696072050291990620486581719410354385121760761374229374847695148230596005409978383369740305816082770283909611956355972181848077519920922059268376958811713365106925235218265173085
p=9046853915223503351787031888977627106934564043204783593118678181991596316582877057556463152579621699010610569526573031954779520781448550677767565207407183

q=11273732364123571293429600400343309403733952146912318879993851141423284675797325272321856863528776914709992821287788339848962916204774010644058033316303937
import hashlib
from gmpy2 import invert

phi=(p-1)*(q-1)

d=hex(invert(e,phi)).encode('utf-8')

print(d)
flag = "flag{" + hashlib.md5(b'0x13b8f87d588e2aa4a27296cf2898f56ab4c8deb5a1222ec080e23afecaf7f975L').hexdigest() + "}"

print(flag)

根据原题处理d值并输出

这里就是按照原题给的计算式去处理d值，这里有个小坑，就是由于Python2和Python3有一点区别，在Python3中，hex(d)得到的值在输出形式上相比Python2少了一个末尾的L，再用这个值去做hash得到的md5值也就不同了。经实验发现，正确的结果可以用Python2直接得到，或在Python3中做hash时给参数末尾加上L。

rsa5（低加密指数广播攻击）

低加密指数广播攻击特点

1
2
3
4
加密指数e非常小
一份明文使用不同的模数n，相同的加密指数e进行多次加密
可以拿到每一份加密后的密文和对应的模数n、加密指数e

此题给出的e很小且不变，给出了不同的公钥(e,n)和对应的密文c，也就是用不同的公钥加密相同的明文m

image-20240617220040055

解题思路：

不同的模数n中可能存在相同的p或者说q

求出不同n之间的最大公约数 gcd()

得到p或q 可得d

有私钥d就能得到明文

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
import gmpy2
import libnum

e = 65537

n0 = 20474918894051778533305262345601880928088284471121823754049725354072477155873778848055073843345820697886641086842612486541250183965966001591342031562953561793332341641334302847996108417466360688139866505179689516589305636902137210185624650854906780037204412206309949199080005576922775773722438863762117750429327585792093447423980002401200613302943834212820909269713876683465817369158585822294675056978970612202885426436071950214538262921077409076160417436699836138801162621314845608796870206834704116707763169847387223307828908570944984416973019427529790029089766264949078038669523465243837675263858062854739083634207
c0 = 974463908243330865728978769213595400782053398596897741316275722596415018912929508637393850919224969271766388710025195039896961956062895570062146947736340342927974992616678893372744261954172873490878805483241196345881721164078651156067119957816422768524442025688079462656755605982104174001635345874022133045402344010045961111720151990412034477755851802769069309069018738541854130183692204758761427121279982002993939745343695671900015296790637464880337375511536424796890996526681200633086841036320395847725935744757993013352804650575068136129295591306569213300156333650910795946800820067494143364885842896291126137320

n1 = 20918819960648891349438263046954902210959146407860980742165930253781318759285692492511475263234242002509419079545644051755251311392635763412553499744506421566074721268822337321637265942226790343839856182100575539845358877493718334237585821263388181126545189723429262149630651289446553402190531135520836104217160268349688525168375213462570213612845898989694324269410202496871688649978370284661017399056903931840656757330859626183773396574056413017367606446540199973155630466239453637232936904063706551160650295031273385619470740593510267285957905801566362502262757750629162937373721291789527659531499435235261620309759
c1 = 15819636201971185538694880505120469332582151856714070824521803121848292387556864177196229718923770810072104155432038682511434979353089791861087415144087855679134383396897817458726543883093567600325204596156649305930352575274039425470836355002691145864435755333821133969266951545158052745938252574301327696822347115053614052423028835532509220641378760800693351542633860702225772638930501021571415907348128269681224178300248272689705308911282208685459668200507057183420662959113956077584781737983254788703048275698921427029884282557468334399677849962342196140864403989162117738206246183665814938783122909930082802031855

n2 = 25033254625906757272369609119214202033162128625171246436639570615263949157363273213121556825878737923265290579551873824374870957467163989542063489416636713654642486717219231225074115269684119428086352535471683359486248203644461465935500517901513233739152882943010177276545128308412934555830087776128355125932914846459470221102007666912211992310538890654396487111705385730502843589727289829692152177134753098649781412247065660637826282055169991824099110916576856188876975621376606634258927784025787142263367152947108720757222446686415627479703666031871635656314282727051189190889008763055811680040315277078928068816491
c2 = 4185308529416874005831230781014092407198451385955677399668501833902623478395669279404883990725184332709152443372583701076198786635291739356770857286702107156730020004358955622511061410661058982622055199736820808203841446796305284394651714430918690389486920560834672316158146453183789412140939029029324756035358081754426645160033262924330248675216108270980157049705488620263485129480952814764002865280019185127662449318324279383277766416258142275143923532168798413011028271543085249029048997452212503111742302302065401051458066585395360468447460658672952851643547193822775218387853623453638025492389122204507555908862

n3 = 21206968097314131007183427944486801953583151151443627943113736996776787181111063957960698092696800555044199156765677935373149598221184792286812213294617749834607696302116136745662816658117055427803315230042700695125718401646810484873064775005221089174056824724922160855810527236751389605017579545235876864998419873065217294820244730785120525126565815560229001887622837549118168081685183371092395128598125004730268910276024806808565802081366898904032509920453785997056150497645234925528883879419642189109649009132381586673390027614766605038951015853086721168018787523459264932165046816881682774229243688581614306480751
c3 = 4521038011044758441891128468467233088493885750850588985708519911154778090597136126150289041893454126674468141393472662337350361712212694867311622970440707727941113263832357173141775855227973742571088974593476302084111770625764222838366277559560887042948859892138551472680654517814916609279748365580610712259856677740518477086531592233107175470068291903607505799432931989663707477017904611426213770238397005743730386080031955694158466558475599751940245039167629126576784024482348452868313417471542956778285567779435940267140679906686531862467627238401003459101637191297209422470388121802536569761414457618258343550613

n4 = 22822039733049388110936778173014765663663303811791283234361230649775805923902173438553927805407463106104699773994158375704033093471761387799852168337898526980521753614307899669015931387819927421875316304591521901592823814417756447695701045846773508629371397013053684553042185725059996791532391626429712416994990889693732805181947970071429309599614973772736556299404246424791660679253884940021728846906344198854779191951739719342908761330661910477119933428550774242910420952496929605686154799487839923424336353747442153571678064520763149793294360787821751703543288696726923909670396821551053048035619499706391118145067
c4 = 15406498580761780108625891878008526815145372096234083936681442225155097299264808624358826686906535594853622687379268969468433072388149786607395396424104318820879443743112358706546753935215756078345959375299650718555759698887852318017597503074317356745122514481807843745626429797861463012940172797612589031686718185390345389295851075279278516147076602270178540690147808314172798987497259330037810328523464851895621851859027823681655934104713689539848047163088666896473665500158179046196538210778897730209572708430067658411755959866033531700460551556380993982706171848970460224304996455600503982223448904878212849412357

n5 = 21574139855341432908474064784318462018475296809327285532337706940126942575349507668289214078026102682252713757703081553093108823214063791518482289846780197329821139507974763780260290309600884920811959842925540583967085670848765317877441480914852329276375776405689784571404635852204097622600656222714808541872252335877037561388406257181715278766652824786376262249274960467193961956690974853679795249158751078422296580367506219719738762159965958877806187461070689071290948181949561254144310776943334859775121650186245846031720507944987838489723127897223416802436021278671237227993686791944711422345000479751187704426369
c5 = 20366856150710305124583065375297661819795242238376485264951185336996083744604593418983336285185491197426018595031444652123288461491879021096028203694136683203441692987069563513026001861435722117985559909692670907347563594578265880806540396777223906955491026286843168637367593400342814725694366078337030937104035993569672959361347287894143027186846856772983058328919716702982222142848848117768499996617588305301483085428547267337070998767412540225911508196842253134355901263861121500650240296746702967594224401650220168780537141654489215019142122284308116284129004257364769474080721001708734051264841350424152506027932

n6 = 25360227412666612490102161131174584819240931803196448481224305250583841439581008528535930814167338381983764991296575637231916547647970573758269411168219302370541684789125112505021148506809643081950237623703181025696585998044695691322012183660424636496897073045557400768745943787342548267386564625462143150176113656264450210023925571945961405709276631990731602198104287528528055650050486159837612279600415259486306154947514005408907590083747758953115486124865486720633820559135063440942528031402951958557630833503775112010715604278114325528993771081233535247118481765852273252404963430792898948219539473312462979849137
c6 = 19892772524651452341027595619482734356243435671592398172680379981502759695784087900669089919987705675899945658648623800090272599154590123082189645021800958076861518397325439521139995652026377132368232502108620033400051346127757698623886142621793423225749240286511666556091787851683978017506983310073524398287279737680091787333547538239920607761080988243639547570818363788673249582783015475682109984715293163137324439862838574460108793714172603672477766831356411304446881998674779501188163600664488032943639694828698984739492200699684462748922883550002652913518229322945040819064133350314536378694523704793396169065179

n7 = 22726855244632356029159691753451822163331519237547639938779517751496498713174588935566576167329576494790219360727877166074136496129927296296996970048082870488804456564986667129388136556137013346228118981936899510687589585286517151323048293150257036847475424044378109168179412287889340596394755257704938006162677656581509375471102546261355748251869048003600520034656264521931808651038524134185732929570384705918563982065684145766427962502261522481994191989820110575981906998431553107525542001187655703534683231777988419268338249547641335718393312295800044734534761692799403469497954062897856299031257454735945867491191
c7 = 6040119795175856407541082360023532204614723858688636724822712717572759793960246341800308149739809871234313049629732934797569781053000686185666374833978403290525072598774001731350244744590772795701065129561898116576499984185920661271123665356132719193665474235596884239108030605882777868856122378222681140570519180321286976947154042272622411303981011302586225630859892731724640574658125478287115198406253847367979883768000812605395482952698689604477719478947595442185921480652637868335673233200662100621025061500895729605305665864693122952557361871523165300206070325660353095592778037767395360329231331322823610060006

n8 = 23297333791443053297363000786835336095252290818461950054542658327484507406594632785712767459958917943095522594228205423428207345128899745800927319147257669773812669542782839237744305180098276578841929496345963997512244219376701787616046235397139381894837435562662591060768476997333538748065294033141610502252325292801816812268934171361934399951548627267791401089703937389012586581080223313060159456238857080740699528666411303029934807011214953984169785844714159627792016926490955282697877141614638806397689306795328344778478692084754216753425842557818899467945102646776342655167655384224860504086083147841252232760941
c8 = 5418120301208378713115889465579964257871814114515046096090960159737859076829258516920361577853903925954198406843757303687557848302302200229295916902430205737843601806700738234756698575708612424928480440868739120075888681672062206529156566421276611107802917418993625029690627196813830326369874249777619239603300605876865967515719079797115910578653562787899019310139945904958024882417833736304894765433489476234575356755275147256577387022873348906900149634940747104513850154118106991137072643308620284663108283052245750945228995387803432128842152251549292698947407663643895853432650029352092018372834457054271102816934

n9 = 28873667904715682722987234293493200306976947898711255064125115933666968678742598858722431426218914462903521596341771131695619382266194233561677824357379805303885993804266436810606263022097900266975250431575654686915049693091467864820512767070713267708993899899011156106766178906700336111712803362113039613548672937053397875663144794018087017731949087794894903737682383916173267421403408140967713071026001874733487295007501068871044649170615709891451856792232315526696220161842742664778581287321318748202431466508948902745314372299799561625186955234673012098210919745879882268512656931714326782335211089576897310591491
c9 = 9919880463786836684987957979091527477471444996392375244075527841865509160181666543016317634963512437510324198702416322841377489417029572388474450075801462996825244657530286107428186354172836716502817609070590929769261932324275353289939302536440310628698349244872064005700644520223727670950787924296004296883032978941200883362653993351638545860207179022472492671256630427228461852668118035317021428675954874947015197745916918197725121122236369382741533983023462255913924692806249387449016629865823316402366017657844166919846683497851842388058283856219900535567427103603869955066193425501385255322097901531402103883869

n10 = 22324685947539653722499932469409607533065419157347813961958075689047690465266404384199483683908594787312445528159635527833904475801890381455653807265501217328757871352731293000303438205315816792663917579066674842307743845261771032363928568844669895768092515658328756229245837025261744260614860746997931503548788509983868038349720225305730985576293675269073709022350700836510054067641753713212999954307022524495885583361707378513742162566339010134354907863733205921845038918224463903789841881400814074587261720283879760122070901466517118265422863420376921536734845502100251460872499122236686832189549698020737176683019
c10 = 1491527050203294989882829248560395184804977277747126143103957219164624187528441047837351263580440686474767380464005540264627910126483129930668344095814547592115061057843470131498075060420395111008619027199037019925701236660166563068245683975787762804359520164701691690916482591026138582705558246869496162759780878437137960823000043988227303003876410503121370163303711603359430764539337597866862508451528158285103251810058741879687875218384160282506172706613359477657215420734816049393339593755489218588796607060261897905233453268671411610631047340459487937479511933450369462213795738933019001471803157607791738538467
 
n11 = 27646746423759020111007828653264027999257847645666129907789026054594393648800236117046769112762641778865620892443423100189619327585811384883515424918752749559627553637785037359639801125213256163008431942593727931931898199727552768626775618479833029101249692573716030706695702510982283555740851047022672485743432464647772882314215176114732257497240284164016914018689044557218920300262234652840632406067273375269301008409860193180822366735877288205783314326102263756503786736122321348320031950012144905869556204017430593656052867939493633163499580242224763404338807022510136217187779084917996171602737036564991036724299
c11 = 21991524128957260536043771284854920393105808126700128222125856775506885721971193109361315961129190814674647136464887087893990660894961612838205086401018885457667488911898654270235561980111174603323721280911197488286585269356849579263043456316319476495888696219344219866516861187654180509247881251251278919346267129904739277386289240394384575124331135655943513831009934023397457082184699737734388823763306805326430395849935770213817533387235486307008892410920611669932693018165569417445885810825749609388627231235840912644654685819620931663346297596334834498661789016450371769203650109994771872404185770230172934013971

n12 = 20545487405816928731738988374475012686827933709789784391855706835136270270933401203019329136937650878386117187776530639342572123237188053978622697282521473917978282830432161153221216194169879669541998840691383025487220850872075436064308499924958517979727954402965612196081404341651517326364041519250125036424822634354268773895465698920883439222996581226358595873993976604699830613932320720554130011671297944433515047180565484495191003887599891289037982010216357831078328159028953222056918189365840711588671093333013117454034313622855082795813122338562446223041211192277089225078324682108033843023903550172891959673551
c12 = 14227439188191029461250476692790539654619199888487319429114414557975376308688908028140817157205579804059783807641305577385724758530138514972962209062230576107406142402603484375626077345190883094097636019771377866339531511965136650567412363889183159616188449263752475328663245311059988337996047359263288837436305588848044572937759424466586870280512424336807064729894515840552404756879590698797046333336445465120445087587621743906624279621779634772378802959109714400516183718323267273824736540168545946444437586299214110424738159957388350785999348535171553569373088251552712391288365295267665691357719616011613628772175

n13 = 27359727711584277234897157724055852794019216845229798938655814269460046384353568138598567755392559653460949444557879120040796798142218939251844762461270251672399546774067275348291003962551964648742053215424620256999345448398805278592777049668281558312871773979931343097806878701114056030041506690476954254006592555275342579529625231194321357904668512121539514880704046969974898412095675082585315458267591016734924646294357666924293908418345508902112711075232047998775303603175363964055048589769318562104883659754974955561725694779754279606726358588862479198815999276839234952142017210593887371950645418417355912567987
c13 = 3788529784248255027081674540877016372807848222776887920453488878247137930578296797437647922494510483767651150492933356093288965943741570268943861987024276610712717409139946409513963043114463933146088430004237747163422802959250296602570649363016151581364006795894226599584708072582696996740518887606785460775851029814280359385763091078902301957226484620428513604630585131511167015763190591225884202772840456563643159507805711004113901417503751181050823638207803533111429510911616160851391754754434764819568054850823810901159821297849790005646102129354035735350124476838786661542089045509656910348676742844957008857457

n14 = 27545937603751737248785220891735796468973329738076209144079921449967292572349424539010502287564030116831261268197384650511043068738911429169730640135947800885987171539267214611907687570587001933829208655100828045651391618089603288456570334500533178695238407684702251252671579371018651675054368606282524673369983034682330578308769886456335818733827237294570476853673552685361689144261552895758266522393004116017849397346259119221063821663280935820440671825601452417487330105280889520007917979115568067161590058277418371493228631232457972494285014767469893647892888681433965857496916110704944758070268626897045014782837
c14 = 14069112970608895732417039977542732665796601893762401500878786871680645798754783315693511261740059725171342404186571066972546332813667711135661176659424619936101038903439144294886379322591635766682645179888058617577572409307484708171144488708410543462972008179994594087473935638026612679389759756811490524127195628741262871304427908481214992471182859308828778119005750928935764927967212343526503410515793717201360360437981322576798056276657140363332700714732224848346808963992302409037706094588964170239521193589470070839790404597252990818583717869140229811712295005710540476356743378906642267045723633874011649259842

n15 = 25746162075697911560263181791216433062574178572424600336856278176112733054431463253903433128232709054141607100891177804285813783247735063753406524678030561284491481221681954564804141454666928657549670266775659862814924386584148785453647316864935942772919140563506305666207816897601862713092809234429096584753263707828899780979223118181009293655563146526792388913462557306433664296966331469906428665127438829399703002867800269947855869262036714256550075520193125987011945192273531732276641728008406855871598678936585324782438668746810516660152018244253008092470066555687277138937298747951929576231036251316270602513451
c15 = 17344284860275489477491525819922855326792275128719709401292545608122859829827462088390044612234967551682879954301458425842831995513832410355328065562098763660326163262033200347338773439095709944202252494552172589503915965931524326523663289777583152664722241920800537867331030623906674081852296232306336271542832728410803631170229642717524942332390842467035143631504401140727083270732464237443915263865880580308776111219718961746378842924644142127243573824972533819479079381023103585862099063382129757560124074676150622288706094110075567706403442920696472627797607697962873026112240527498308535903232663939028587036724

n16 = 23288486934117120315036919418588136227028485494137930196323715336208849327833965693894670567217971727921243839129969128783853015760155446770590696037582684845937132790047363216362087277861336964760890214059732779383020349204803205725870225429985939570141508220041286857810048164696707018663758416807708910671477407366098883430811861933014973409390179948577712579749352299440310543689035651465399867908428885541237776143404376333442949397063249223702355051571790555151203866821867908531733788784978667478707672984539512431549558672467752712004519300318999208102076732501412589104904734983789895358753664077486894529499
c16 = 10738254418114076548071448844964046468141621740603214384986354189105236977071001429271560636428075970459890958274941762528116445171161040040833357876134689749846940052619392750394683504816081193432350669452446113285638982551762586656329109007214019944975816434827768882704630460001209452239162896576191876324662333153835533956600295255158377025198426950944040643235430211011063586032467724329735785947372051759042138171054165854842472990583800899984893232549092766400510300083585513014171220423103452292891496141806956300396540682381668367564569427813092064053993103537635994311143010708814851867239706492577203899024

n17 = 19591441383958529435598729113936346657001352578357909347657257239777540424811749817783061233235817916560689138344041497732749011519736303038986277394036718790971374656832741054547056417771501234494768509780369075443550907847298246275717420562375114406055733620258777905222169702036494045086017381084272496162770259955811174440490126514747876661317750649488774992348005044389081101686016446219264069971370646319546429782904810063020324704138495608761532563310699753322444871060383693044481932265801505819646998535192083036872551683405766123968487907648980900712118052346174533513978009131757167547595857552370586353973
c17 = 3834917098887202931981968704659119341624432294759361919553937551053499607440333234018189141970246302299385742548278589896033282894981200353270637127213483172182529890495903425649116755901631101665876301799865612717750360089085179142750664603454193642053016384714515855868368723508922271767190285521137785688075622832924829248362774476456232826885801046969384519549385428259591566716890844604696258783639390854153039329480726205147199247183621535172450825979047132495439603840806501254997167051142427157381799890725323765558803808030109468048682252028720241357478614704610089120810367192414352034177484688502364022887

n18 = 19254242571588430171308191757871261075358521158624745702744057556054652332495961196795369630484782930292003238730267396462491733557715379956969694238267908985251699834707734400775311452868924330866502429576951934279223234676654749272932769107390976321208605516299532560054081301829440688796904635446986081691156842271268059970762004259219036753174909942343204432795076377432107630203621754552804124408792358220071862369443201584155711893388877350138023238624566616551246804054720492816226651467017802504094070614892556444425915920269485861799532473383304622064493223627552558344088839860178294589481899206318863310603
c18 = 6790553533991297205804561991225493105312398825187682250780197510784765226429663284220400480563039341938599783346724051076211265663468643826430109013245014035811178295081939958687087477312867720289964506097819762095244479129359998867671811819738196687884696680463458661374310994610760009474264115750204920875527434486437536623589684519411519100170291423367424938566820315486507444202022408003879118465761273916755290898112991525546114191064022991329724370064632569903856189236177894007766690782630247443895358893983735822824243487181851098787271270256780891094405121947631088729917398317652320497765101790132679171889

n19 = 26809700251171279102974962949184411136459372267620535198421449833298448092580497485301953796619185339316064387798092220298630428207556482805739803420279056191194360049651767412572609187680508073074653291350998253938793269214230457117194434853888765303403385824786231859450351212449404870776320297419712486574804794325602760347306432927281716160368830187944940128907971027838510079519466846176106565164730963988892400240063089397720414921398936399927948235195085202171264728816184532651138221862240969655185596628285814057082448321749567943946273776184657698104465062749244327092588237927996419620170254423837876806659
c19 = 386213556608434013769864727123879412041991271528990528548507451210692618986652870424632219424601677524265011043146748309774067894985069288067952546139416819404039688454756044862784630882833496090822568580572859029800646671301748901528132153712913301179254879877441322285914544974519727307311002330350534857867516466612474769753577858660075830592891403551867246057397839688329172530177187042229028685862036140779065771061933528137423019407311473581832405899089709251747002788032002094495379614686544672969073249309703482556386024622814731015767810042969813752548617464974915714425595351940266077021672409858645427346

n=[n0,n1,n2,n3,n4,n5,n6,n7,n8,n9,n10,n11,n12,n13,n14,n15,n16,n17,n18,n19]
c=[c0,c1,c2,c3,c4,c5,c6,c7,c8,c9,c10,c11,c12,c13,c14,c15,c16,c17,c18,c19]

for i in range(len(n)):
    for j in range(len(n)):
        if(i!=j):
            if(gmpy2.gcd(n[i],n[j])!=1):   #对不同的n进行 欧几里得算法，以求出最大公约数(p)
                print(i,j)                 #输出对应的n的序号            
                p = gmpy2.gcd(n[i],n[j])
                print("p = ",p)
                q = n[i] // p
                print("q = ",q)
                d = gmpy2.invert(e , (p-1)*(q-1))
                print("d = ",d)
                m = pow(c[i],d,n[i])
                print("m = ",m)
# 4 17
# p =  132585806383798600305426957307612567604223562626764190211333136246643723811046149337852966828729052476725552361132437370521548707664977123165279305052971868012755509160408641100548744046621516877981864180076497524093201404558036301820216274968638825245150755772559259575544101918590311068466601618472464832499
# q =  172130338499326278748088659642118539903263306644625489813269854049704514120598134934786316771912260248369075948864036229605563950070491992643125838594149381631362120542615545158696925360916086470107987771246645459433841320759048661246016875180635458357799131806734777129141845728102816378815607663660131827433
# d =  10255762274410447979846484489272592025276530212873111105713911284717751198023145855606019924577798738695538597187877966993598709672960993516539454197162664114978503222530508768362729378865140035425026175847611448858053529432493784291104132035847332081780017599698552936076497425709781734095556186428757196589872934330029936289432604149394663566703657427009973329681704667429413105717095832162998561559367314637614478597021229692702783695719313128949842371770106722991377377048130193746157144666295125327151620068015029385410313912716206956605407434839741405536764244140055959056916717996815600672095481030331533580401
# m =  13040004482825176402070107903979416267670062118522537076883968693524598900675425175282673277
print(libnum.n2s(int(m)))
#b'flag{abdcbe5fd94e23b3de429223ab9c2fdf}'

[NCTF2019]childRSA(费马小定理)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from random import choice
from Crypto.Util.number import isPrime, sieve_base as primes
from flag import flag

def getPrime(bits):
    while True:
        n = 2
        while n.bit_length() < bits:
            n *= choice(primes)
        if isPrime(n + 1):
            return n + 1

e = 0x10001
m = int.from_bytes(flag.encode(), 'big')
p, q = [getPrime(2048) for _ in range(2)]
n = p * q
c = pow(m, e, n)

# n = 32849718197337581823002243717057659218502519004386996660885100592872201948834155543125924395614928962750579667346279456710633774501407292473006312537723894221717638059058796679686953564471994009285384798450493756900459225040360430847240975678450171551048783818642467506711424027848778367427338647282428667393241157151675410661015044633282064056800913282016363415202171926089293431012379261585078566301060173689328363696699811123592090204578098276704877408688525618732848817623879899628629300385790344366046641825507767709276622692835393219811283244303899850483748651722336996164724553364097066493953127153066970594638491950199605713033004684970381605908909693802373826516622872100822213645899846325022476318425889580091613323747640467299866189070780620292627043349618839126919699862580579994887507733838561768581933029077488033326056066378869170169389819542928899483936705521710423905128732013121538495096959944889076705471928490092476616709838980562233255542325528398956185421193665359897664110835645928646616337700617883946369110702443135980068553511927115723157704586595844927607636003501038871748639417378062348085980873502535098755568810971926925447913858894180171498580131088992227637341857123607600275137768132347158657063692388249513
# c = 26308018356739853895382240109968894175166731283702927002165268998773708335216338997058314157717147131083296551313334042509806229853341488461087009955203854253313827608275460592785607739091992591431080342664081962030557042784864074533380701014585315663218783130162376176094773010478159362434331787279303302718098735574605469803801873109982473258207444342330633191849040553550708886593340770753064322410889048135425025715982196600650740987076486540674090923181664281515197679745907830107684777248532278645343716263686014941081417914622724906314960249945105011301731247324601620886782967217339340393853616450077105125391982689986178342417223392217085276465471102737594719932347242482670320801063191869471318313514407997326350065187904154229557706351355052446027159972546737213451422978211055778164578782156428466626894026103053360431281644645515155471301826844754338802352846095293421718249819728205538534652212984831283642472071669494851823123552827380737798609829706225744376667082534026874483482483127491533474306552210039386256062116345785870668331513725792053302188276682550672663353937781055621860101624242216671635824311412793495965628876036344731733142759495348248970313655381407241457118743532311394697763283681852908564387282605279108

只在基础的RSA上修改了大素数的生成过程。choice()函数从小于10000的素数中随机挑选一个

1
这里primes为前10000个素数的列表

p,q的生成方式是一个突破口，分析函数getprime(),p,q就是在前10000个素数列表里面随机找几个素数相乘再加一得到的，所以这10000个素数的乘积x是p-1和q-1的倍数,x=k*(p-1),n=p*q，这里就要从n和x得到p。

费马小定理

1
若b为一个素数，则对于任意整数a，有a^(b-1) = 1 (mod b),即a^k*(b-1) = 1 (mod b)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
x=k*(p-1),n=p*q

2^k*(p-1)=1 mod p

2^k*(p-1)-1=k*p

2^x-1=k*p

这里2^x-1是p的倍数，n也是p的倍数，他们的公因数就是p。
用gcd(2^x-1,n)=p,但是x太大了，直接计算公因数运行时间太久了。
我是这样想的p比n小，把2^x-1 mod n 再求公因数应该也可以吧。
下面看看证明：
2^x= 1 (mod p)，即2^x = 1 + k1*p
而2^x% n = 2^x - k2n = 2^x - k2pq
两边同时% p，有2^x% n = 2^x (mod p)
所以同样有2^x % n = 1 (mod p)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import gmpy2
import libnum
from Crypto.Util.number import isPrime, sieve_base as primes
 
c = 26308018356739853895382240109968894175166731283702927002165268998773708335216338997058314157717147131083296551313334042509806229853341488461087009955203854253313827608275460592785607739091992591431080342664081962030557042784864074533380701014585315663218783130162376176094773010478159362434331787279303302718098735574605469803801873109982473258207444342330633191849040553550708886593340770753064322410889048135425025715982196600650740987076486540674090923181664281515197679745907830107684777248532278645343716263686014941081417914622724906314960249945105011301731247324601620886782967217339340393853616450077105125391982689986178342417223392217085276465471102737594719932347242482670320801063191869471318313514407997326350065187904154229557706351355052446027159972546737213451422978211055778164578782156428466626894026103053360431281644645515155471301826844754338802352846095293421718249819728205538534652212984831283642472071669494851823123552827380737798609829706225744376667082534026874483482483127491533474306552210039386256062116345785870668331513725792053302188276682550672663353937781055621860101624242216671635824311412793495965628876036344731733142759495348248970313655381407241457118743532311394697763283681852908564387282605279108
n=32849718197337581823002243717057659218502519004386996660885100592872201948834155543125924395614928962750579667346279456710633774501407292473006312537723894221717638059058796679686953564471994009285384798450493756900459225040360430847240975678450171551048783818642467506711424027848778367427338647282428667393241157151675410661015044633282064056800913282016363415202171926089293431012379261585078566301060173689328363696699811123592090204578098276704877408688525618732848817623879899628629300385790344366046641825507767709276622692835393219811283244303899850483748651722336996164724553364097066493953127153066970594638491950199605713033004684970381605908909693802373826516622872100822213645899846325022476318425889580091613323747640467299866189070780620292627043349618839126919699862580579994887507733838561768581933029077488033326056066378869170169389819542928899483936705521710423905128732013121538495096959944889076705471928490092476616709838980562233255542325528398956185421193665359897664110835645928646616337700617883946369110702443135980068553511927115723157704586595844927607636003501038871748639417378062348085980873502535098755568810971926925447913858894180171498580131088992227637341857123607600275137768132347158657063692388249513
e=0x10001
x=1
for i in primes:
    x=i*x
 
p=gmpy2.gcd(pow(2,x,n)-1,n)
q=n//p
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
m=pow(c,d,n)
flag=libnum.n2s(int(m))
print(flag)
# b'NCTF{Th3r3_ar3_1ns3cure_RSA_m0duli_7hat_at_f1rst_gl4nce_appe4r_t0_be_s3cur3}'

总结：当知道某一个数x是p-1,q-1的倍数时，就用gcd(2^x-1,n)=p，进一步gcd(pow(2,x,n)-1,n)=p。

[HDCTF2019]bbbbbbrsa

image-20240901214820323

可以明显的看到c是逆过来的，我们重新把c进行排序，在进行base64解码得到c

image-20240901214954598

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from base64 import b64encode as b32encode
from base64 import b64decode
from gmpy2 import invert, gcd, iroot
from Crypto.Util.number import *

p = 177077389675257695042507998165006460849
n = 37421829509887796274897162249367329400988647145613325367337968063341372726061
c64 = '==gMzYDNzIjMxUTNyIzNzIjMyYTM4MDM0gTMwEjNzgTM2UTN4cjNwIjN2QzM5ADMwIDNyMTO4UzM2cTM5kDN2MTOyUTO5YDM0czM3MjM'
c = int(b64decode(str(c64)[::-1]))
print(c)
q = n // p
phi = (p - 1) * (q - 1)
for e in range(50000, 70000):
	if gcd(e, phi) == 1:
		d = invert(e, phi)
		m = pow(c, d, n)
		flag = str(long_to_bytes(m))
		if 'flag' in flag or 'CTF' in flag or ("{" in flag and '}' in flag):
			print(flag)

rsa4(低加密指数广播攻击)

image-20240901221446106

另外有两点需要注意：
1、此题中的N、c均是以5进制表示，要先用int(“*****”,5)转换为十进制才能计算(开始运行半天都不出结果，看了其他师傅博客才发现原来是五进制)。
2、题目没有给出加密指数e，但是根据低加密指数广播攻击的特性猜e=3、10、17等

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
from Crypto.Util.number import *
import primefac
import gmpy2

e = 3

def modinv(a,n):
    return primefac.modinv(a,n) % n

def CRT(n1,c1,n2,c2,n3,c3):
    n = n1*n2*n3
    m_e = 0
    m_e = m_e + c1*(n2*n3)*modinv(n2*n3,n1)
    m_e = m_e + c2*(n1*n3)*modinv(n1*n3,n2)
    m_e = m_e + c3*(n1*n2)*modinv(n2*n1,n3)
    return m_e % n

n1 = int('331310324212000030020214312244232222400142410423413104441140203003243002104333214202031202212403400220031202142322434104143104244241214204444443323000244130122022422310201104411044030113302323014101331214303223312402430402404413033243132101010422240133122211400434023222214231402403403200012221023341333340042343122302113410210110221233241303024431330001303404020104442443120130000334110042432010203401440404010003442001223042211442001413004',5)
c1 = int('310020004234033304244200421414413320341301002123030311202340222410301423440312412440240244110200112141140201224032402232131204213012303204422003300004011434102141321223311243242010014140422411342304322201241112402132203101131221223004022003120002110230023341143201404311340311134230140231412201333333142402423134333211302102413111111424430032440123340034044314223400401224111323000242234420441240411021023100222003123214343030122032301042243',5)
n2 = int('302240000040421410144422133334143140011011044322223144412002220243001141141114123223331331304421113021231204322233120121444434210041232214144413244434424302311222143224402302432102242132244032010020113224011121043232143221203424243134044314022212024343100042342002432331144300214212414033414120004344211330224020301223033334324244031204240122301242232011303211220044222411134403012132420311110302442344021122101224411230002203344140143044114',5)
c2 = int('112200203404013430330214124004404423210041321043000303233141423344144222343401042200334033203124030011440014210112103234440312134032123400444344144233020130110134042102220302002413321102022414130443041144240310121020100310104334204234412411424420321211112232031121330310333414423433343322024400121200333330432223421433344122023012440013041401423202210124024431040013414313121123433424113113414422043330422002314144111134142044333404112240344',5)
n3 = int('332200324410041111434222123043121331442103233332422341041340412034230003314420311333101344231212130200312041044324431141033004333110021013020140020011222012300020041342040004002220210223122111314112124333211132230332124022423141214031303144444134403024420111423244424030030003340213032121303213343020401304243330001314023030121034113334404440421242240113103203013341231330004332040302440011324004130324034323430143102401440130242321424020323',5)
c3 = int('10013444120141130322433204124002242224332334011124210012440241402342100410331131441303242011002101323040403311120421304422222200324402244243322422444414043342130111111330022213203030324422101133032212042042243101434342203204121042113212104212423330331134311311114143200011240002111312122234340003403312040401043021433112031334324322123304112340014030132021432101130211241134422413442312013042141212003102211300321404043012124332013240431242',5)
m_e = CRT(n1,c1,n2,c2,n3,c3)
m = gmpy2.iroot(m_e,e)[0]
print(long_to_bytes(m))

primefac.modinv(a, n): 这个部分使用primefac库中的modinv函数，来计算a在模n意义下的逆元素。这意味着找到一个数x，使得 (a * x) % n = 1

[BJDCTF2020]rsa_output

我们审计题目，发现题目给了我们两个一样的m和两个不一样的e和c，我们考虑共模攻击，

c1 = m^e1 mod n =>c1^s1 = m^(e1*s1) mod n

c2 = m^e2 mod n =>c2^s2 = m^(e2*s2) mod n

两者相乘，通过扩展欧几里得定理，我们可知e1与e2互质，必存在s1和s2使e1s1+e2s2=1

由此可求出相对应的s1和s2.

m=（c1*s1+c2*s2）%n

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
n=21058339337354287847534107544613605305015441090508924094198816691219103399526800112802416383088995253908857460266726925615826895303377801614829364034624475195859997943146305588315939130777450485196290766249612340054354622516207681542973756257677388091926549655162490873849955783768663029138647079874278240867932127196686258800146911620730706734103611833179733264096475286491988063990431085380499075005629807702406676707841324660971173253100956362528346684752959937473852630145893796056675793646430793578265418255919376323796044588559726703858429311784705245069845938316802681575653653770883615525735690306674635167111
e1=2767
e2=3659
c1=20152490165522401747723193966902181151098731763998057421967155300933719378216342043730801302534978403741086887969040721959533190058342762057359432663717825826365444996915469039056428416166173920958243044831404924113442512617599426876141184212121677500371236937127571802891321706587610393639446868836987170301813018218408886968263882123084155607494076330256934285171370758586535415136162861138898728910585138378884530819857478609791126971308624318454905992919405355751492789110009313138417265126117273710813843923143381276204802515910527468883224274829962479636527422350190210717694762908096944600267033351813929448599
c2=11298697323140988812057735324285908480504721454145796535014418738959035245600679947297874517818928181509081545027056523790022598233918011261011973196386395689371526774785582326121959186195586069851592467637819366624044133661016373360885158956955263645614345881350494012328275215821306955212788282617812686548883151066866149060363482958708364726982908798340182288702101023393839781427386537230459436512613047311585875068008210818996941460156589314135010438362447522428206884944952639826677247819066812706835773107059567082822312300721049827013660418610265189288840247186598145741724084351633508492707755206886202876227
 
#已知两者n相同，e不同，共模攻击
 
import gmpy2
from Crypto.Util.number import isPrime, sieve_base as primes,long_to_bytes
 
def egcd(a,b):
    if b==0:
        return a,0;
    else:
        x,y=egcd(b,a%b)
        return y,x-(a//b)*y #扩展欧几里得算法
 
s=egcd(e1,e2)
s1=s[0]
s2=s[1]
print(s[0],s[1])
m = gmpy2.powmod(c1, s1, n) *gmpy2.powmod(c2, s2, n) % n
 
print(long_to_bytes(m))

//

[BJDCTF2020]RSA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from Crypto.Util.number import getPrime,bytes_to_long

flag=open("flag","rb").read()

p=getPrime(1024)
q=getPrime(1024)
assert(e<100000)
n=p*q
m=bytes_to_long(flag)
c=pow(m,e,n)
print c,n
print pow(294,e,n)

p=getPrime(1024)
n=p*q
m=bytes_to_long("BJD"*32)
c=pow(m,e,n)
print c,n

我们发现第一个n和第二个n共用一个q，因此我们通过gcd可以得到q的值，从而得到p的值，又已知pow(294,e,n)的值，因此我们可以爆破出e的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes
from math import gcd
from gmpy2 import invert
c=12641635617803746150332232646354596292707861480200207537199141183624438303757120570096741248020236666965755798009656547738616399025300123043766255518596149348930444599820675230046423373053051631932557230849083426859490183732303751744004874183062594856870318614289991675980063548316499486908923209627563871554875612702079100567018698992935818206109087568166097392314105717555482926141030505639571708876213167112187962584484065321545727594135175369233925922507794999607323536976824183162923385005669930403448853465141405846835919842908469787547341752365471892495204307644586161393228776042015534147913888338316244169120
n=13508774104460209743306714034546704137247627344981133461801953479736017021401725818808462898375994767375627749494839671944543822403059978073813122441407612530658168942987820256786583006947001711749230193542370570950705530167921702835627122401475251039000775017381633900222474727396823708695063136246115652622259769634591309421761269548260984426148824641285010730983215377509255011298737827621611158032976420011662547854515610597955628898073569684158225678333474543920326532893446849808112837476684390030976472053905069855522297850688026960701186543428139843783907624317274796926248829543413464754127208843070331063037
a=381631268825806469518166370387352035475775677163615730759454343913563615970881967332407709901235637718936184198930226303761876517101208677107311006065728014220477966000620964056616058676999878976943319063836649085085377577273214792371548775204594097887078898598463892440141577974544939268247818937936607013100808169758675042264568547764031628431414727922168580998494695800403043312406643527637667466318473669542326169218665366423043579003388486634167642663495896607282155808331902351188500197960905672207046579647052764579411814305689137519860880916467272056778641442758940135016400808740387144508156358067955215018
BJDc=979153370552535153498477459720877329811204688208387543826122582132404214848454954722487086658061408795223805022202997613522014736983452121073860054851302343517756732701026667062765906277626879215457936330799698812755973057557620930172778859116538571207100424990838508255127616637334499680058645411786925302368790414768248611809358160197554369255458675450109457987698749584630551177577492043403656419968285163536823819817573531356497236154342689914525321673807925458651854768512396355389740863270148775362744448115581639629326362342160548500035000156097215446881251055505465713854173913142040976382500435185442521721
BJDn=12806210903061368369054309575159360374022344774547459345216907128193957592938071815865954073287532545947370671838372144806539753829484356064919357285623305209600680570975224639214396805124350862772159272362778768036844634760917612708721787320159318432456050806227784435091161119982613987303255995543165395426658059462110056431392517548717447898084915167661172362984251201688639469652283452307712821398857016487590794996544468826705600332208535201443322267298747117528882985955375246424812616478327182399461709978893464093245135530135430007842223389360212803439850867615121148050034887767584693608776323252233254261047
q=gcd(n,BJDn)
p=n//q
phi=(p-1)*(q-1)
e=0
for i in range(100000):
    if pow(294,i,n)==a:
        print(i)
        e=i
        break

d=invert(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))

[GWCTF 2019]BabyRSA(解方程)

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
import hashlib
import sympy
from Crypto.Util.number import *

flag = 'GWHT{******}'
secret = '******'

assert(len(flag) == 38)

half = len(flag) / 2

flag1 = flag[:half]
flag2 = flag[half:]

secret_num = getPrime(1024) * bytes_to_long(secret)

p = sympy.nextprime(secret_num)
q = sympy.nextprime(p)
//说明p,q接近，可用yafu求解

N = p * q

e = 0x10001

F1 = bytes_to_long(flag1)
F2 = bytes_to_long(flag2)
//flag被加密

c1 = F1 + F2
c2 = pow(F1, 3) + pow(F2, 3)
//设方程组，可解F1，F2
assert(c2 < N)

m1 = pow(c1, e, N)
m2 = pow(c2, e, N)
可逆模求c1，c2

output = open('secret', 'w')
output.write('N=' + str(N) + '\n')
output.write('m1=' + str(m1) + '\n')
output.write('m2=' + str(m2) + '\n')
output.close()

求得p和q

image-20240912214215556

接着求d

1
d=gmpy2.invert(e,(p-1)*(q-1))

然后可以求c1,c2

1
2
c1=pow(m1,d,N)
c2=pow(m2,d,N)

然后联立方程，求得F1，F2

1
2
3
4
5
F1=Symbol('F1')
F2=Symbol('F2')
x = F1 + F2-c1
y = pow(F1, 3) + pow(F2, 3)-c2
a=solve([x,y],[F1,F2])

最后转为字节

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import gmpy2
from Crypto.Util.number import bytes_to_long, long_to_bytes
from sympy import *
e=0x10001
N=636585149594574746909030160182690866222909256464847291783000651837227921337237899651287943597773270944384034858925295744880727101606841413640006527614873110651410155893776548737823152943797884729130149758279127430044739254000426610922834573094957082589539445610828279428814524313491262061930512829074466232633130599104490893572093943832740301809630847541592548921200288222432789208650949937638303429456468889100192613859073752923812454212239908948930178355331390933536771065791817643978763045030833712326162883810638120029378337092938662174119747687899484603628344079493556601422498405360731958162719296160584042671057160241284852522913676264596201906163
m1=90009974341452243216986938028371257528604943208941176518717463554774967878152694586469377765296113165659498726012712288670458884373971419842750929287658640266219686646956929872115782173093979742958745121671928568709468526098715927189829600497283118051641107305128852697032053368115181216069626606165503465125725204875578701237789292966211824002761481815276666236869005129138862782476859103086726091860497614883282949955023222414333243193268564781621699870412557822404381213804026685831221430728290755597819259339616650158674713248841654338515199405532003173732520457813901170264713085107077001478083341339002069870585378257051150217511755761491021553239
m2=487443985757405173426628188375657117604235507936967522993257972108872283698305238454465723214226871414276788912058186197039821242912736742824080627680971802511206914394672159240206910735850651999316100014691067295708138639363203596244693995562780286637116394738250774129759021080197323724805414668042318806010652814405078769738548913675466181551005527065309515364950610137206393257148357659666687091662749848560225453826362271704292692847596339533229088038820532086109421158575841077601268713175097874083536249006018948789413238783922845633494023608865256071962856581229890043896939025613600564283391329331452199062858930374565991634191495137939574539546
p=797862863902421984951231350430312260517773269684958456342860983236184129602390919026048496119757187702076499551310794177917920137646835888862706126924088411570997141257159563952725882214181185531209186972351469946269508511312863779123205322378452194261217016552527754513215520329499967108196968833163329724620251096080377748737
q=797862863902421984951231350430312260517773269684958456342860983236184129602390919026048496119757187702076499551310794177917920137646835888862706126924088411570997141257159563952725882214181185531209186972351469946269508511312863779123205322378452194261217016552527754513215520329499967108196968833163329724620251096080377747699
d=gmpy2.invert(e,(p-1)*(q-1))
c1=pow(m1,d,N)
c2=pow(m2,d,N)
F1=Symbol('F1')
F2=Symbol('F2')
x = F1 + F2-c1
y = pow(F1, 3) + pow(F2, 3)-c2
a=solve([x,y],[F1,F2])
#F1=1590956290598033029862556611630426044507841845
#F2=1141553212031156130619789508463772513350070909
print(long_to_bytes(F1)+long_to_bytes(F2))
#b'GWHT{f709e0e2cfe7e530ca8972959a1033b2}'

SameMod（共模攻击）

模攻击

共模是指：就是明文m,相同。用两个公钥e1,e2加密得到两个私钥d1,d2 和两个密文c1,c2

共模攻击，即当m不变的情况下，知道n,e1,e2,c1,c2, 可以在不知道d1,d2的情况下，解出m

利用条件为=> gcd(e1,e2)=1

根据扩展欧几里得 算法得

可以得到该式子的一组解(s1,s2) 假设s1为正数，s2为负数

有整数s1,s2(一正一负)

存在e1s1+e2s2==1

1
2
3
4
5
6
7
8
9
10
11
12
from Crypto.Util.number import long_to_bytes
from gmpy2 import gcdext

n=6266565720726907265997241358331585417095726146341989755538017122981360742813498401533594757088796536341941659691259323065631249
e1=773
e2=839
c1=3453520592723443935451151545245025864232388871721682326408915024349804062041976702364728660682912396903968193981131553111537349
c2=5672818026816293344070119332536629619457163570036305296869053532293105379690793386019065754465292867769521736414170803238309535
s,s1,s2=gcdext(e1,e2)
m = ((pow(c1,s1,n)*pow(c2,s2,n)) % n)
print(m)
print(long_to_bytes(m))

image-20240914144918614

我们发现输出是一串乱码，但当我们看到m的值，发现里面有ascii码的影子

我们进行解码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from Crypto.Util.number import long_to_bytes
from gmpy2 import gcdext

n=6266565720726907265997241358331585417095726146341989755538017122981360742813498401533594757088796536341941659691259323065631249
e1=773
e2=839
c1=3453520592723443935451151545245025864232388871721682326408915024349804062041976702364728660682912396903968193981131553111537349
c2=5672818026816293344070119332536629619457163570036305296869053532293105379690793386019065754465292867769521736414170803238309535
s,s1,s2=gcdext(e1,e2)
m = str((pow(c1,s1,n)*pow(c2,s2,n)) % n)
print(m)

flag=""
i=0
while i < len(m):
    if m[i]=='1':
        c=chr(int(m[i:i+3]))
        i+=3
    else:
        c=chr(int(m[i:i+2]))
        i+=2
    flag+=c

print(flag)

得到flag

image-20240914145033644

[AFCTF2018]可怜的RSA（rsa公钥加密）

我们先利用Crypto.PublicKey的RSA模块从key文件中获取公钥信息n,e

1
2
3
4
5
6
7
8
from Crypto.PublicKey import RSA
f = open("C:\\Users\\11\\Downloads\\attachment\public.key","rb").read()
pub = RSA.importKey(f)
print(pub.n,pub.e)

# n = 79832181757332818552764610761349592984614744432279135328398999801627880283610900361281249973175805069916210179560506497075132524902086881120372213626641879468491936860976686933630869673826972619938321951599146744807653301076026577949579618331502776303983485566046485431039541708467141408260220098592761245010678592347501894176269580510459729633673468068467144199744563731826362102608811033400887813754780282628099443490170016087838606998017490456601315802448567772411623826281747245660954245413781519794295336197555688543537992197142258053220453757666537840276416475602759374950715283890232230741542737319569819793988431443
# e = 65537

得到n，e的值后，对n进行分解，得到p和q

1
2
p = 3133337
q = 25478326064937419292200172136399497719081842914528228316455906211693118321971399936004729134841162974144246271486439695786036588117424611881955950996219646807378822278285638261582099108339438949573034101215141156156408742843820048066830863814362379885720395082318462850002901605689761876319151147352730090957556940842144299887394678743607766937828094478336401159449035878306853716216548374273462386508307367713112073004011383418967894930554067582453248981022011922883374442736848045920676341361871231787163441467533076890081721882179369168787287724769642665399992556052144845878600126283968890273067575342061776244939

利用gmpy2库通过p,q,ep,q,e求d

1
2
3
4
5
from gmpy2 import *
d = int(invert(e, (p-1)*(q-1)))
print(d)
# d = 406853230956379689450620815713768871010712825839536410687962650677800895818003893712259622281477453292088146173840036827322518131453630576229976208523593618949818777897059256426591560532784635697190752924923710375949616954069804342573867253630978123632384795587951365482103468722384133084798614863870775897915929475258974188300927376911833763105616386167881813301748585233563049693794370642976326692672223638908164822104832415788577945314264232531947860576966629150456995512932232264881080618006698700677529111454508900582785420549466798020451488168615035256292977390692401388790460066327347700109341639992159475755036449

打包密钥对flag.pnc解密（由于是Base64编码后的密文，因此还需解码）

1
2
3
4
5
6
7
8
9
10
11
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
from base64 import b64decode
key_info = RSA.construct((n, e, d, p, q))
key = RSA.importKey(key_info.exportKey())
key = PKCS1_OAEP.new(key)
f = open('D:\\Download\\flag.enc', 'r').read()
c = b64decode(f)
flag = key.decrypt(c)
print(flag)

[RoarCTF2019]babyRSA(威尔逊定理)

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
import sympy
import random

def myGetPrime():
    A= getPrime(513)
    print(A)
    B=A-random.randint(1e3,1e5)
    print(B)
    return sympy.nextPrime((B!)%A)
p=myGetPrime()
#A1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467234407
#B1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467140596

q=myGetPrime()
#A2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858418927
#B2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858351026

r=myGetPrime()

n=p*q*r
#n=85492663786275292159831603391083876175149354309327673008716627650718160585639723100793347534649628330416631255660901307533909900431413447524262332232659153047067908693481947121069070451562822417357656432171870951184673132554213690123308042697361969986360375060954702920656364144154145812838558365334172935931441424096270206140691814662318562696925767991937369782627908408239087358033165410020690152067715711112732252038588432896758405898709010342467882264362733
c=pow(flag,e,n)
#e=0x1001
#c=75700883021669577739329316795450706204502635802310731477156998834710820770245219468703245302009998932067080383977560299708060476222089630209972629755965140317526034680452483360917378812244365884527186056341888615564335560765053550155758362271622330017433403027261127561225585912484777829588501213961110690451987625502701331485141639684356427316905122995759825241133872734362716041819819948645662803292418802204430874521342108413623635150475963121220095236776428
#so,what is the flag?

分析

从代码中可以知道：

p=(B1!)%A1p=(B1!)%A1

q=(B2!)%A2q=(B2!)%A2

又由威尔逊定理知道，

(A−1)!≡ −1 mod A(A−1)!≡ −1 mod A

而B=A-random.randint(1e3,1e5)，所以在B的前面补上

(A−1)(A−2)(A−3)…(B+1)(A−1)(A−2)(A−3)…(B+1)

就有

(A−1)(A−2)(A−3)…(B+1)∗(B!)%A=−1%A(A−1)(A−2)(A−3)…(B+1)∗(B!)%A=−1%A

于是再整理一下又有

(A−2)(A−3)…(B+1)∗(B!)%A=1%A(A−2)(A−3)…(B+1)∗(B!)%A=1%A

这就意味这可由(A−2)(A−3)…(B+1)(A−2)(A−3)…(B+1)模A的逆元求得(B!)%A(B!)%A的值。再取nextprime(sympy.ntheory.generate模块里的nextprime不是nextPrime)即可得到p或q的值。

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
from sympy import nextprime
from Crypto.Util.number import *
from gmpy2 import invert

def get_p_q(A,B):
    tmp = 1
    # calculate remain value (mod A) of (A−1)(A−2)(A−3)...(B+1)
    for i in range(B+1,A-1):
        tmp *= i
        tmp %= A

    tmp_inv = invert(tmp,A)
    result = nextprime(tmp_inv)
    return result

A1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467234407
B1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467140596

A2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858418927
B2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858351026

n=85492663786275292159831603391083876175149354309327673008716627650718160585639723100793347534649628330416631255660901307533909900431413447524262332232659153047067908693481947121069070451562822417357656432171870951184673132554213690123308042697361969986360375060954702920656364144154145812838558365334172935931441424096270206140691814662318562696925767991937369782627908408239087358033165410020690152067715711112732252038588432896758405898709010342467882264362733
e=0x1001
c=75700883021669577739329316795450706204502635802310731477156998834710820770245219468703245302009998932067080383977560299708060476222089630209972629755965140317526034680452483360917378812244365884527186056341888615564335560765053550155758362271622330017433403027261127561225585912484777829588501213961110690451987625502701331485141639684356427316905122995759825241133872734362716041819819948645662803292418802204430874521342108413623635150475963121220095236776428

p = get_p_q(A1,B1)
q = get_p_q(A2,B2)
print(p)
print(q)
# p = 1276519424397216455160791032620569392845781005616561979809403385593761615670426423039762716291920053306063214548359656555809123127361539475238435285654851
# q = 13242175493583584108411324143773780862426183382017753129633978933213674770487765387985282956574197274056162861584407275172775868763712231230219112670015751

r = n // p // q
print(r)
# r = 5057572094237208127867754008134739503717927865750318894982404287656747895573075881186030840558129423864679886646066477437020450654848839861455661385205433

phn = (p - 1) * (q - 1) * (r - 1)
d = invert(e, phn)
print(d)
# d = 23245991568931089935575398139533179902151911325504278186895368123724684132878362590745372016987963378102056924287587028702166372731411906405181410326380814220943063812165970658883369631308421395770179828382024820676516261188276456737434776404340381374859304944884947772697915445301641449023374627214573292539161320959779418043275889202421521069705878414823578781441160766914068377017428380775625886023385019623499784980822629415795884228504498888092721097658433
m = pow(c,d,n)
print(m)
# 49562188096458630410563044417358818341913265571373725266976612126526106528404944745044614126232074073813936259453
print(long_to_bytes(m))

RoarCTF{wm-CongrAtu1ation4-1t4-ju4t-A-bAby-R4A}

RSA & what（共模攻击&base64隐写）

我们仔细观察两个文件，发现有两个e和多个c，n是一样的，我们想到共模攻击

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
from Crypto.Util.number import*
import base64

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def CMA(n,e1,e2,c1,c2):
    s = egcd(e1, e2)
    s1 = s[1]
    s2 = s[2]
    if s1<0:
        s1 = - s1
        c1 = inverse(c1, n)
    elif s2<0:
        s2 = - s2
        c2 = inverse(c2, n)
    m = pow(c1,s1,n)*pow(c2,s2,n) % n
    return m

f1=open("C:\\Users\\11\\Downloads\\2e37d2da-1cda-45a5-bb73-413c37864fa1\\rsawhat\\HUB1")
f2=open("C:\\Users\\11\\Downloads\\2e37d2da-1cda-45a5-bb73-413c37864fa1\\rsawhat\\HUB2")
N=f1.readline()
N=f2.readline()
e1,e2=f1.readline(),f2.readline()
f1.readline()
f2.readline()
c1,c2=f1.readline(),f2.readline()
ans=b''
cnt=0
while len(c1)!=0:
    cnt+=1
    ans+=long_to_bytes(CMA(int(N),int(e1),int(e2),int(c1),int(c2)))
    #print(base64.b64decode(temp))
    c1,c2=f1.readline(),f2.readline()
temp=b''
M=b''
print(ans)
for i in ans:
    k=long_to_bytes(i)
    #print(i," ",end="")
    if k==b'\n':
        M+=base64.b64decode(temp)
        temp=b''
        continue
    temp+=k
print(M)

得到的明文为base64编码，解码后是对base54的介绍，没啥用

我们主要看base64编码是一段一段的

不难想到base64隐写。

我们到网上找一段base64隐写脚本

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
from Crypto.Util.number import*
import base64
c = b'VEhJUz==\nRkxBR3==\nSVN=\nSElEREVOLo==\nQ0FO\nWU9V\nRklORM==\nSVT=\nT1VUP4==\nRE8=\nWU9V\nS05PV9==\nQkFTRTY0P5==\nWW91bmdD\nVEhJTku=\nWU9V\nQVJF\nTk9U\nVEhBVE==\nRkFNSUxJQVI=\nV0lUSO==\nQkFTRTY0Lh==\nQmFzZTY0\naXO=\nYW==\nZ3JvdXA=\nb2b=\nc2ltaWxhcn==\nYmluYXJ5LXRvLXRleHR=\nZW5jb2Rpbme=\nc2NoZW1lc0==\ndGhhdD==\ncmVwcmVzZW50\nYmluYXJ5\nZGF0YW==\naW5=\nYW6=\nQVNDSUl=\nc3RyaW5n\nZm9ybWF0\nYnk=\ndHJhbnNsYXRpbmd=\naXS=\naW50b1==\nYT==\ncmFkaXgtNjQ=\ncmVwcmVzZW50YXRpb24u\nVGhl\ndGVybc==\nQmFzZTY0\nb3JpZ2luYXRlc8==\nZnJvbd==\nYY==\nc3BlY2lmaWN=\nTUlNRT==\nY29udGVudI==\ndHJhbnNmZXI=\nZW5jb2Rpbmcu\nVGhl\ncGFydGljdWxhct==\nc2V0\nb2b=\nNjR=\nY2hhcmFjdGVyc5==\nY2hvc2Vu\ndG+=\ncmVwcmVzZW50\ndGhl\nNjQ=\ncGxhY2UtdmFsdWVz\nZm9y\ndGhl\nYmFzZd==\ndmFyaWVz\nYmV0d2Vlbt==\naW1wbGVtZW50YXRpb25zLp==\nVGhl\nZ2VuZXJhbI==\nc3RyYXRlZ3n=\naXO=\ndG9=\nY2hvb3Nl\nNjR=\nY2hhcmFjdGVyc5==\ndGhhdA==\nYXJl\nYm90aN==\nbWVtYmVyc5==\nb2a=\nYS==\nc3Vic2V0\nY29tbW9u\ndG8=\nbW9zdM==\nZW5jb2RpbmdzLA==\nYW5k\nYWxzb8==\ncHJpbnRhYmxlLg==\nVGhpc9==\nY29tYmluYXRpb25=\nbGVhdmVz\ndGhl\nZGF0YW==\ndW5saWtlbHk=\ndG/=\nYmV=\nbW9kaWZpZWS=\naW5=\ndHJhbnNpdE==\ndGhyb3VnaN==\naW5mb3JtYXRpb26=\nc3lzdGVtcyw=\nc3VjaN==\nYXM=\nRS1tYWlsLD==\ndGhhdA==\nd2VyZQ==\ndHJhZGl0aW9uYWxseQ==\nbm90\nOC1iaXQ=\nY2xlYW4uWzFd\nRm9y\nZXhhbXBsZSw=\nTUlNRSdz\nQmFzZTY0\naW1wbGVtZW50YXRpb24=\ndXNlcw==\nQahDWiw=\nYahDeiw=\nYW5k\nMKhDOQ==\nZm9y\ndGhl\nZmlyc3Q=\nNjI=\ndmFsdWVzLg==\nT3RoZXI=\ndmFyaWF0aW9ucw==\nc2hhcmU=\ndGhpcw==\ncHJvcGVydHk=\nYnV0\nZGlmZmVy\naW4=\ndGhl\nc3ltYm9scw==\nY2hvc2Vu\nZm9y\ndGhl\nbGFzdA==\ndHdv\ndmFsdWVzOw==\nYW4=\nZXhhbXBsZQ==\naXM=\nVVRGLTcu'

def get_base64_diff_value(s1, s2):
    base64chars = b'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/'
    res = 0
    for i in range(len(s2)):
        if s1[i] != s2[i]:
            return abs(base64chars.index(s1[i]) - base64chars.index(s2[i]))
    return res

def solve_stego():
    line=b''
    bin_str=''
    for i in c:
        k=long_to_bytes(i)
        if k==b'\n':
            steg_line = line
            norm_line = base64.b64encode(base64.b64decode(line))
            diff = get_base64_diff_value(steg_line, norm_line)
            #print(diff)
            pads_num = steg_line.count(b'=')
            if diff:
                bin_str += bin(diff)[2:].zfill(pads_num * 2)
            else:
                bin_str += '0' * pads_num * 2
            print(goflag(bin_str))
            line=b''
            continue
        line+=k

def goflag(bin_str):
    res_str = ''
    for i in range(0, len(bin_str), 8):
        res_str += chr(int(bin_str[i:i + 8], 2))
    return res_str


if __name__ == '__main__':
    solve_stego()

//7c86d8f7d6de33a87f7f9d6b005ce640

flag吧数字包起来就行了

[NPUCTF2020]EzRSA

根据题设，我们得到以下关系

1
2
3
4
gift=lcm((p-1)*(q-1)) 
gmpy2.lcm求最小公倍数
n=p*q
c=m^e mod n

由小学五年级的知识，有

1
最小公倍数(p,q) ∗ 最大公因数(p,q) = p∗q

所以对于gift

有
$$
g
i
f
t
∗
g
c
d
(
p
−
1
,
q
−
1
)

(
p
−
1
)
∗
(
q
−
1
)

ϕ
(
n
)
$$
我们可以求的gift的二进制位数为2045

1
print(len(bin(gift)[2:]))

同时我们知道ϕ(n)的位数为2048，因此gcd(p−1,q−1)gcd(p−1,q−1)占3bits，因此最大公因数的范围（十进制）为[4,8]

我们在此范围内遍历最大公因数的值，然后与最小公倍数相乘得到ϕ(n)的值，然后通过逆模运算求得d，然后就可得·明文

但需要注意这里的e不是素数，分解可得e=2*27361

所以在计算时，我们要先将e除以2

值的变化可通过以下表达式体现
$$
c

(
m
2
)
^
{e/
2}
m
o
d
%23
n
$$
所以解出的明文需要开根号再转为字节流

注意：遍历过程中不是所有的值都符合条件，可能会报ZeroDivisionError，因此需要加异常处理

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
from Crypto.Util.number import *
import gmpy2

e = 54722
# e = 2*27361
n = 17083941230213489700426636484487738282426471494607098847295335339638177583685457921198569105417734668692072727759139358207667248703952436680183153327606147421932365889983347282046439156176685765143620637107347870401946946501620531665573668068349080410807996582297505889946205052879002028936125315312256470583622913646319779125559691270916064588684997382451412747432722966919513413709987353038375477178385125453567111965259721484997156799355617642131569095810304077131053588483057244340742751804935494087687363416921314041547093118565767609667033859583125275322077617576783247853718516166743858265291135353895239981121
gift = 2135492653776686212553329560560967285303308936825887355911916917454772197960682240149821138177216833586509090969892419775958406087994054585022894165950768427741545736247918410255804894522085720642952579638418483800243368312702566458196708508543635051350999572787188236243275631609875253617015664414032058822919469443284453403064076232765024248435543326597418851751586308514540124571309152787559712950209357825576896132278045112177910266019741013995106579484868768251084453338417115483515132869594712162052362083414163954681306259137057581036657441897428432575924018950961141822554251369262248368899977337886190114104
c = 3738960639194737957667684143565005503596276451617922474669745529299929395507971435311181578387223323429323286927370576955078618335757508161263585164126047545413028829873269342924092339298957635079736446851837414357757312525158356579607212496060244403765822636515347192211817658170822313646743520831977673861869637519843133863288550058359429455052676323196728280408508614527953057214779165450356577820378810467527006377296194102671360302059901897977339728292345132827184227155061326328585640019916328847372295754472832318258636054663091475801235050657401857262960415898483713074139212596685365780269667500271108538319
# gift = 8 * 11 * 97 * 9601 * 26057167557433418766727399341516665922795024485718296827775927226598694152064298989740080209950805089159979564300359652085874056289167084685303669920341402021998569251561854184586912056788515477034039863935829715784489123437315798902409373317578932823488000322365526936227790036245092665207472438169954702748857842187299166976320465787901470261800372425345547560303561842376571751928531743505412746346436473024093575122041981043859827477404447458211341273671273506575488189374812217939984540494633634622813448773520886788206836310702581026986331011987344147901504555559723572981774237352245997308787165273589

print(len(bin(gift)[2:]))
print(len(bin(n)[2:]))

# gift * gcd = (p-1) * (q-1)
# gift % gcd = 0
for gcd_val in range(4, 8):
    phi = gift * gcd_val
    try:
        d = gmpy2.invert(e // 2, phi)
        m_2 = pow(c, int(d), n)
        flag = long_to_bytes(gmpy2.isqrt(m_2))
        print(flag)
    except ZeroDivisionError:
        continue

//NPUCTF{diff1cult_rsa_1s_e@sy}

DES

[ACTF新生赛2020]crypto-des

encryptedkey.txt

1
2
3
4
5
6
7
72143238992041641000000.000000,
77135357178006504000000000000000.000000,
1125868345616435400000000.000000,
67378029765916820000000.000000,
75553486092184703000000000000.000000,
4397611913739958700000.000000,
76209378028621039000000000000000.000000

hint.txt

1
To solve the key, Maybe you know some interesting data format about C language?

附件1考的是数据在内存中的存储，我们用struct库中的pack函数打包数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from libnum import*
import struct
import binascii

s = [72143238992041641000000.000000,77135357178006504000000000000000.000000,1125868345616435400000000.000000,67378029765916820000000.000000,75553486092184703000000000000.000000,4397611913739958700000.000000,76209378028621039000000000000000.000000]
a = ''
b = ''
for i in s:
    i = float(i)
    a += struct.pack('<f',i).hex()        #小端
print(a)

for j in s:
    i = float(i)
    b += struct.pack('>f',i).hex()        #小端
print(b)

a = 0x496e74657265737472696e67204964656120746f20656e6372797074
b = 0x74707972747079727470797274707972747079727470797274707972
print(n2s(a))
print(n2s(b))

我们得到压缩包密码为

1
Interestring Idea to encrypt

得到一个加密文件，密钥都给出来了，直接base64解码后，decrypt()解密就行了。

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
import pyDes
import base64
from Crypto.Util.number  import*
deskey  = "********"
DES = pyDes.des(deskey)
DES.setMode('ECB')
DES.Kn = [
			[1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0],
			[1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0], 
			[0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0],
			[1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1], 
			[0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1],
			[0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0],
			[0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0],
			[0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0],
			[1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0],
			[0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0],
			[0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1],
			[0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0],
			[1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0],
			[1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1],
			[1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1],
			[1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1]
		]
# cipher_list = base64.b64encode(DES.encrypt(flag))

k = b'vrkgBqeK7+h7mPyWujP8r5FqH5yyVlqv0CXudqoNHVAVdNO8ML4lM4zgez7weQXo'
data = base64.b64decode(k)
# print(data)
flag = DES.decrypt(data)
print(flag)

数论

[网鼎杯 2020 青龙组]you_raise_me_up（大步小步算法）

首先，我们审计题目，可以发现题目中给予了我们m、c和n的值，其中n=2**512,m则是在（2，m）之间的值，c是m^flag = c mod n

可以看出，这是一道求指标的题目，我们可以通过以下方法进行计算，已知的条件为：

2^e = c1 mod n 在这其中，除了e其余条件我们都已知，在这里，我们需要使用离散对数求解的思路：

Shanks’s Babystep-Giantstep Algorithm算法：
1、n=[ √n ]+1

2、构造两个列表

list1=[1,g,g^2,g^3,……,g^n]

list2=[h,hg^(-n),hg^(-2n),……,hg^(-n**2)]

3、在两个列表中，找到两个相同的数 g^i=hg^(-jn)

=>g^(i+jn)=h mod n

4、我们所求的e=i+jn
python库应用：

python(sympy库) x=sympy.discrete_log(n,a,g)

exp

1
2
3
4
5
6
7
8
9
10
m = 391190709124527428959489662565274039318305952172936859403855079581402770986890308469084735451207885386318986881041563704825943945069343345307381099559075
c = 6665851394203214245856789450723658632520816791621796775909766895233000234023642878786025644953797995373211308485605397024123180085924117610802485972584499
n=2**512
 
 
import gmpy2
from Crypto.Util.number import *
import sympy
x=sympy.discrete_log(n,c,m)
print(long_to_bytes(x))

丢失的md5(暴力求解)

将代码修改

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

# 迭代指定范围内的ASCII字符
for i in range(32, 127):
    for j in range(32, 127):
        for k in range(32, 127):
            # 创建要进行哈希运算的字符串
            test_string = 'TASC' + chr(i) + 'O3RJMV' + chr(j) + 'WDJKX' + chr(k) + 'ZM'
            m = hashlib.md5()
            # 将字符串编码为字节并更新哈希对象
            hashlib 模块中的 update 方法用于将数据传递给哈希对象，以便生成哈希值。在使用 update 方法时，需要传入一个字             节类型的数据。
            m.update(test_string.encode('utf-8'))
            des = m.hexdigest()
            # 检查哈希值是否包含指定的子字符串
            if 'e9032' in des and 'da' in des and '911513' in des:
                print(des)

//e9032994dabac08080091151380478a2

得到flag

Alice and Bob（质因数分离）

https://zh.numberempire.com/numberfactorizer.php

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
import hashlib
def prime_factors(n):
    """
    分解给定整数n的质因数。
    返回一个列表，其中包含n的所有质因数。
    """
    # 初始化一个空列表来存储质因数
    factors = []

    # 从2开始，逐个检查每个数是否是n的因数
    for i in range(2, int(n ** 0.5) + 1):
        # 如果i是n的因数，将其添加到质因数列表中
        if n % i == 0:
            factors.append(i)
            # 如果i不是质数，则n/i也是一个因数，将其也添加到质因数列表中
            if i != n // i:
                factors.append(n // i)

                # 如果n是偶数且大于2，则它本身不是质数，需要特别处理
    if n > 2 and n % 2 == 0:
        factors.append(2)

    return factors
# 测试函数
print(prime_factors(98554799767))  # 输出: [101999, 966233]

a=hashlib.md5()
a.update("101999966233".encode('utf-8'))
print(a.hexdigest().lower())

//d450209323a847c8d01c6be47c81811a

大帝的密码武器（凯撒密码）

https://www.lddgo.net/encrypt/caesar-cipher

image-20240602144536344

下载下来的文件长这样，我们给它加上.zip后缀就能打开文件了

image-20240602144656911

从已知信息可知为凯撒密码，我们用工具进行移位

image-20240602144735700

第13位出现单词，我们把附件的字符串也移位

image-20240602144809987

得到flag{PbzrPuvan}

Windows系统密码（md5解密）

https://www.cmd5.com/

将下载的附件解压后，发现文件的后缀为hash，即原文本使用了哈希加密，众所周知，哈希密码的加密的过程被认为是不可逆的，

也就是说，人们认为从哈希串中是不可能还原出原口令的。这里我们使用记事本打开文件，得到以下内容：

image-20240602150144576

解题思路

由于哈希密码的不可逆性，我们只能借用一些工具来进行操作，这里我使用的工具网址是：MD5解密。分别对第二行的三段文字进行

求解，便可得到答案为：good-luck

信息化时代的步伐（中文电码）

image-20240602150614823

这是一串中文代码（别问我为什么知道）

找个网站解密

https://dianma.bmcx.com/

image-20240602150712490

flag出来了

凯撒？替换？呵呵!（凯撒密码爆破）

凯撒密码一般就是26个字母经过单纯的按字母顺序来位移的加密方法（一般）

如：abc=def

进阶版的凯撒就不按照字母顺序的加密

如：abc=dhj

所以就要经过暴力破解出每一种可能的对应加密

image-20240602151935377

前面的MTHJ和字符串中间的{}是明显的flag{}的格式，所以就推断这里的

MTHJ对应的明文就是flag

然后就对字符串中的其他20个字母进行爆破对比，可以写脚本（不会哈哈哈）

用工具吧

quipqiup

image-20240602151946218

flag要去空格，在两边加{}

萌萌哒的八戒（猪圈密码）

打开图片，在下面发现一些图案

image-20240602152506490

经过查询，为猪圈密码

img

对照密码表依次代入即可，得到答案为：flag{whenthepigwanttoeat}

权限获得第一步(md5解密)

image-20240602152801553

拿去md5解密就能得到flag了

传统知识+古典密码

小明某一天收到一封密信，信中写了几个不同的年份
辛卯，癸巳，丙戌，辛未，庚辰，癸酉，己卯，癸巳。
信的背面还写有“+甲子”，请解出这段密文。

key值：CTF{XXX}

img

查表可得序号：28，30，23，8，17，10，16，30

且一甲子为60，所以每个加上60

88，90，83，68，77，70，76，90

对应ascii字符为

XZSDMFLZ

1
2
3
4
5
a=[88,90,83,68,77,70,76,90]
b=''
for i in a:
    b+=chr(i)
print(b)

由于古典密码只有栅栏密码和凯撒密码

我们先进行凯撒密码，移动5位进行解密得到SUNYHAGU

image-20240602155404900

再将SUNYHAGU进行栅栏密码解密

image-20240602155448691

得到flag{SHUANGYU}

世上无难事(暴力破解)

image-20240602171546125

打开页面发现一大堆字母，我们直接暴力破解

image-20240602171617317

flag记得把字母改为小写

[AFCTF2018]Morse（摩斯密码&16进制解码）

image-20240603215538129

压缩包里一看就是摩斯密码，但要把/改为空格

image-20240603215630058

解码后还需16进制解码才能得到flag

image-20240603215659800

还原大师(md5爆破).

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

mystery_md5 = "E903???4DAB????08?????51?80??8A?"
for i in range(65, 91):
    for j in range(65, 91):
        for k in range(65, 91):
            # print(f"TASC{chr(i)}O3RJMV{chr(j)}WDJKX{chr(k)}ZMd", end=";")
            # 计算候选字符串的MD5哈希值
            plaintext = f"TASC{chr(i)}O3RJMV{chr(j)}WDJKX{chr(k)}ZM"
            md5_hash = hashlib.md5(plaintext.encode('utf8')).hexdigest().upper()  # 注意大小写
            # print(md5_hash[:4])
            # 比较MD5码的部分
            if md5_hash[:4] == mystery_md5[:4]:
                print(plaintext)
                print(md5_hash)

异性相吸(二进制异或)

提起异性我们可以想到01，也就是二进制，我们用010把文件内容转化成二进制再异或

1
2
3
4
5
6
7
8
9
10
a = '0110000101110011011000010110010001110011011000010111001101100100011000010111001101100100011000010111001101100100011000010111001101100100011000010111001101100100011000010111001101100100011000010111001101100100011000010111001101100100011000010111001101100100011100010111011101100101011100110111000101100110'
b = '0000011100011111000000000000001100001000000001000001001001010101000000110001000001010100010110000100101101011100010110000100101001010110010100110100010001010010000000110100010000000010010110000100011000000110010101000100011100000101010101100100011101010111010001000001001001011101010010100001010000011011'
c = ''

for i in range(len(a)):
    if a[i] == b[i]:
        c += '0'
    else:
        c += '1'
print(c)

得到

1
0110011001101100011000010110011101111011011001010110000100110001011000100110001100110000001110010011100000111000001110010011100100110010001100100011011100110110011000100011011101100110001110010011010101100010001101010011010001100001001101110011010000110011001101010110010100111000001110010110010101111101

我们再解码得到flag

1
flag{ea1bc0988992276b7f95b54a7435e89e}

[GXYCTF2019]CheckIn（ROT-N加密）

image-20240611170339389

出现了两个等号，我们先base64解密

image-20240611170402562

里面没有{}可以知道不是凯撒加密，没有=不是base64

但可以发现这里的每一个字符的ASCII在33-126

可以发现是ROT-N加密

ROT-N在线加密

得到flag

image-20240611170522341

Cipher（playfair解密）

题目提示：公平的玩吧，也就是playfair，正好有这一种加密为普莱菲尔密码，以playfair为密钥进行普莱菲尔密码解密（要不是我看了wp，鬼知道这玩意）

playfair解密

image-20240611171809161

用flag{}包裹住，得到flag{itisnotaproblemhavefun}

[BJDCTF2020]这是base??（字符替换）

这题的题目是base，我们可以想到base64，但txt文档给出了2个数据，不难想到字符替代

image-20240616212448415

我们将chipertext的字符与dict的字符一一对应，得到每一个字符在dict中的下标

我们查找base64的标准字典

在这里插入图片描述

将每一个字符在dict中的下标与标准字典的字符相对应

写脚本

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

a={0: 'J', 1: 'K', 2: 'L', 3: 'M', 4: 'N', 5: 'O', 6: 'x', 7: 'y', 8: 'U', 9: 'V', 10: 'z', 11: 'A', 12: 'B', 13: 'C', 14: 'D', 15: 'E', 16: 'F', 17: 'G', 18: 'H', 19: '7', 20: '8', 21: '9', 22: 'P', 23: 'Q', 24: 'I', 25: 'a', 26: 'b', 27: 'c', 28: 'd', 29: 'e', 30: 'f', 31: 'g', 32: 'h', 33: 'i', 34: 'j', 35: 'k', 36: 'l', 37: 'm', 38: 'W', 39: 'X', 40: 'Y', 41: 'Z', 42: '0', 43: '1', 44: '2', 45: '3', 46: '4', 47: '5', 48: '6', 49: 'R', 50: 'S', 51: 'T', 52: 'n', 53: 'o', 54: 'p', 55: 'q', 56: 'r', 57: 's', 58: 't', 59: 'u', 60: 'v', 61: 'w', 62: '+', 63: '/', 64: '='}
b="FlZNfnF6Qol6e9w17WwQQoGYBQCgIkGTa9w3IQKw"
base64_list = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P','Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z', 'a', 'b', 'c', 'd', 'e', 'f','g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v','w', 'x', 'y', 'z', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '+', '/']
flag=''

for i in b:
    for j in a:
        if i == a[j]:
            flag+=base64_list[j]

print(base64.b64decode(flag))

//b'BJD{D0_Y0u_kNoW_Th1s_b4se_map}'

robomunication（音频摩斯密码）

下载文件后，发现是个音频，用Audacity打开，发现它在哔哔哔哔 哔 哔波哔哔。。。原来是摩斯密码

整理后得到：…. . .-.. .-.. — .– …. .- - .. … - …. . -.- . -.– .. - .. … -… — — .–. -… . . .–.

解码得

密码是：HELLOWHATISTHEKEYITISBOOPBEEP

最终解得flag为BOOPBEEP

[WUSTCTF2020]佛说：只能四天（解密大礼包）

image-20240818202237098

佛曰加密网站解密——http://hi.pcmoe.net/buddha.html，得到

image-20240818202346306

马上去核心价值观解密——http://www.hiencode.com/cvencode.html得到

image-20240818202511160

解密内容提示栅栏密码，我们用栅栏密码解密

要去掉后面的__doyouknowfence

栅栏密码_栅栏密码在线加密解密【W型】-ME2在线工具 (metools.info)

image-20240818204034605

我们用凯撒密码解密

image-20240818204511820

我们观察枚举后的结果都没有小写字母，我们考虑base32

在偏移为3是得到flag

img

达芬奇密码（脑洞题）

image-20240818205419252

我们观察数字列发现跟斐波那契数列的数字一样但是位置不一样

我们对比来看看

1
2
3
4
5
6
7
8
def fib_loop_for(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a
for i in range(1,33):
    print(fib_loop_for(i))

1
2
3
4
5
6
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309

1 233 3 2584 1346269 144 5 196418 21 1597 610 377 10946 89 514229 987 8 55 6765 2178309 121393 317811 46368 4181 1 832040 2 28657 75025 34 13 17711  

c="36968853882116725547342176952286"

我们发现数字列和神秘数字串的个数一样，所以我们猜测要通过比对斐波那契数列，来将c进行排序

例如：1在斐波那契数列中排第一位，那3就在第一位

​ 233在斐波那契数列中排第12位，那6在12位上

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
a = "0 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309"
b = "0 233 3 2584 1346269 144 5 196418 21 1597 610 377 10946 89 514229 987 8 55 6765 2178309 121393 317811 46368 4181 1 832040 2 28657 75025 34 13 17711"
a = a.split(" ")
b = b.split(" ")
flag = []
m = "36968853882116725547342176952286"
for i in range(len(a)):
    for j in range(len(a)):    
        if a[i] == b[j]:        #a[i]中的值在b中的索引为j
            #print(j)
            flag.append(m[j])   #将m[j]中的值添加到flag中
print(len(flag))
print(''.join(flag))
#37995588256861228614165223347687

[MRCTF2020]古典密码知多少（古典密码图形）

image-20240818205933301

观察图中信息，可以发现用到了CTF中的图形密码，包括猪圈密码的变形、标准银河字母的加密、和圣堂武士密码。

标准银河字母的加密

在这里插入图片描述

圣堂武士密码

在这里插入图片描述

解密出来得到

1
FGCPFLIRTUASYON

题目信息还提到了fence，我们考虑栅栏密码

img

可得到有用信息：FLAGISCRYPTOFUN，去掉前面信息得最终结果为：

1
flag{CRYPTOFUN}

rot(rot原理)

1
2
3
4
5
破解下面的密文：

83 89 78 84 45 86 96 45 115 121 110 116 136 132 132 132 108 128 117 118 134 110 123 111 110 127 108 112 124 122 108 118 128 108 131 114 127 134 108 116 124 124 113 108 76 76 76 76 138 23 90 81 66 71 64 69 114 65 112 64 66 63 69 61 70 114 62 66 61 62 69 67 70 63 61 110 110 112 64 68 62 70 61 112 111 112

flag格式flag{}

看着像是 ascii 码。

但是有大于 127 的数字存在，所以要先处理。

题目名称为 rot，

1
2
3
4
5
6
7
ROT5、ROT13、ROT18、ROT47 编码是一种简单的码元位置顺序替换暗码。此类编码具有可逆性，可以自我解密，主要用于应对快速浏览，或者是机器的读取，而不让其理解其意。
 
ROT5 是 rotate by 5 places 的简写，意思是旋转5个位置，其它皆同。下面分别说说它们的编码方式：
ROT5：只对数字进行编码，用当前数字往前数的第5个数字替换当前数字，例如当前为0，编码后变成5，当前为1，编码后变成6，以此类推顺序循环。
ROT13：只对字母进行编码，用当前字母往前数的第13个字母替换当前字母，例如当前为A，编码后变成N，当前为B，编码后变成O，以此类推顺序循环。
ROT18：这是一个异类，本来没有，它是将ROT5和ROT13组合在一起，为了好称呼，将其命名为ROT18。
ROT47：对数字、字母、常用符号进行编码，按照它们的ASCII值进行位置替换，用当前字符ASCII值往前数的第47位对应字符替换当前字符，例如当前为小写字母z，编码后变成大写字母K，当前为数字0，编码后变成符号_。用于ROT47编码的字符其ASCII值范围是33－126，具体可参考ASCII编码。

参考rot原理，将所有数字减13，再转ascii码

1
2
3
4
s='83 89 78 84 45 86 96 45 115 121 110 116 136 132 132 132 108 128 117 118 134 110 123 111 110 127 108 112 124 122 108 118 128 108 131 114 127 134 108 116 124 124 113 108 76 76 76 76 138 23 90 81 66 71 64 69 114 65 112 64 66 63 69 61 70 114 62 66 61 62 69 67 70 63 61 110 110 112 64 68 62 70 61 112 111 112'
l = s.split(" ")
for i in l:
    print(chr(int(i) - 13), end='')
1
2
FLAG IS flag{www_shiyanbar_com_is_very_good_????}
MD5:38e4c352809e150186920aac37190cbc

看样子我们需要对flag的最后4位进行爆破

1
2
3
4
5
6
7
8
9
10
11
12
demo='flag{www_shiyanbar_com_is_very_good_'
check = '38e4c352809e150186920aac37190cbc'
 
for i in range(32,126):
    for j in range(32,126):
        for k in range(32,126):
            for m in range(32,126):
                tmp = demo + chr(i) + chr(j) + chr(k) + chr(m) + '}'
                hash = hashlib.md5(tmp.encode('utf8')).hexdigest()
                if check == hash:
                    print(tmp)
                    exit()

得到flag

这是什么(jsfuck)

我们将apk文件修改为txt文件

我们在文件中发现

image-20240818212431110

我们考虑jsfuck解密

我们f12打开控制台，将括号复制进去

image-20240818212531846

得到flag

[MRCTF2020]天干地支+甲子（天干地支）

image-20240902205011081

1
2
3
4
5
6
7
8
9
10
11
12
13
14
六十年甲子（干支表）
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	     52	     53	     54	     55	     56	     57	     58	     59      60
甲寅	乙卯	丙辰	丁巳	戊午	己未	庚申	辛酉	壬戌	癸亥

我们对照得到

1
11  51  51  40  46  51  38

都加一个甲子(60)得到

1
71 111 111 100 106 111 98

我们对照ascii表得到

ASCII码表

1
2
Goodjob

得到flag

1
flag{Goodjob}

[NCTF2019]Keyboard(脑洞)

image-20240902210112608

题目提示键盘，我们发现每一个字母都对应上面的一个数字，我们猜测9键盘，而字母个数就是对应的9键盘上的对应的字母

1
2
youaresosmartthatthisisjustapieceofcake

1
2
3
4
5
6
7
8
cipher="ooo yyy ii w uuu ee uuuu yyy uuuu y w uuu i i rr w i i rr rrr uuuu rrr uuuu t ii uuuu i w u rrr ee www ee yyy eee www w tt ee"
base=" qwertyuiop"
a=[" "," ","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"]
for part in cipher.split(" "):
    s=base.index(part[0])
    count=len(part)
    print(a[s][count-1],end="")

[BJDCTF2020]signin

image-20240902214954471

我们观察，密文为16进制，我们将其转换为字符

1
2
3
4
from Crypto.Util.number import *
a=0x424a447b57653163306d655f74345f424a444354467d
c=long_to_bytes((a))
print(c.decode("utf-8"))

得到flag

1
BJD{We1c0me_t4_BJDCTF}

[MRCTF2020]vigenere（维吉尼亚解密）

我们找一个在线网站

https://www.guballa.de/vigenere-solver

把文本放上去，直接破解，flag是最后一行

image-20240905212644646

[ACTF新生赛2020]crypto-rsa0(zip伪加密)

我们把文件下下来后，在hint.txt提示，文件进行了zip伪加密

image-20240905215448375

一个ZIP文件由三个部分组成：

压缩源文件数据区+压缩源文件目录区+压缩源文件目录结束标志。

伪加密原理：zip伪加密是在文件头的加密标志位做修改，进而再打开文件时识被别为加密压缩包。 一般来说，文件各个区域开头就是50 4B，然后后面两个字节是版本，再后面两个就是判断是否有加密的关键了

伪加密：

压缩源文件数据区的全局加密应当为 00 00

且压缩文件目录区的全局方式标记应当为 09 00

原理

ZIP伪加密是在文件头的加密标志位做修改，进而再打开文件时识别为加密压缩包。
在参考了网上多数文章无果后，在西普的一个小题找到了可以复现的方法。
给出西普的某个示例：

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
压缩源文件数据区 
50 4B 03 04：这是头文件标记（0x04034b50）
14 00：解压文件所需 pkware 版本 
00 00：全局方式位标记（有无加密） 
08 00：压缩方式 
5A 7E：最后修改文件时间 
F7 46：最后修改文件日期 
16 B5 80 14：CRC-32校验（1480B516）
19 00 00 00：压缩后尺寸（25）
17 00 00 00：未压缩尺寸（23）
07 00：文件名长度 
00 00：扩展记录长度 
6B65792E7478740BCECC750E71ABCE48CDC9C95728CECC2DC849AD284DAD0500  
压缩源文件目录区 
50 4B 01 02：目录中文件文件头标记(0x02014b50)  
3F 00：压缩使用的 pkware 版本 
14 00：解压文件所需 pkware 版本 
00 00：全局方式位标记（有无加密，这个更改这里进行伪加密，改为09 00打开就会提示有密码了） 
08 00：压缩方式 
5A 7E：最后修改文件时间 
F7 46：最后修改文件日期 
16 B5 80 14：CRC-32校验（1480B516）
19 00 00 00：压缩后尺寸（25）
17 00 00 00：未压缩尺寸（23）
07 00：文件名长度 
24 00：扩展字段长度 
00 00：文件注释长度 
00 00：磁盘开始号 
00 00：内部文件属性 
20 00 00 00：外部文件属性 
00 00 00 00：局部头部偏移量 
6B65792E7478740A00200000000000010018006558F04A1CC5D001BDEBDD3B1CC5D001BDEBDD3B1CC5D001  
压缩源文件目录结束标志 
50 4B 05 06：目录结束标记 
00 00：当前磁盘编号 
00 00：目录区开始磁盘编号 
01 00：本磁盘上纪录总数 
01 00：目录区中纪录总数 
59 00 00 00：目录区尺寸大小 
3E 00 00 00：目录区对第一张磁盘的偏移量 
00 00：ZIP 文件注释长度
		我们用010打开zip文件，把所有的50 4B后的09 00都改成00 00

image-20240905215619133

保存之后打开压缩包，发发现就可以顺利打开rsa.py文件了

然后就是个rsa解密了

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

p = 9018588066434206377240277162476739271386240173088676526295315163990968347022922841299128274551482926490908399237153883494964743436193853978459947060210411
q = 7547005673877738257835729760037765213340036696350766324229143613179932145122130685778504062410137043635958208805698698169847293520149572605026492751740223
c = 50996206925961019415256003394743594106061473865032792073035954925875056079762626648452348856255575840166640519334862690063949316515750256545937498213476286637455803452890781264446030732369871044870359838568618176586206041055000297981733272816089806014400846392307742065559331874972274844992047849472203390350
e = 65537

n = p * q
phi_n = (q - 1) * (p - 1)
d = gmpy2.invert(e, phi_n)
m = gmpy2.powmod(c, d, n)

print(binascii.unhexlify(hex(m)[10:]))

传感器（曼彻斯特编码）

Wiki

曼彻斯特编码（Manchester Encoding），也叫做相位编码（ Phase Encode，简写PE），是一个同步时钟编码技术，被物理层使用来编码一个同步位流的时钟和数据。它在以太网媒介系统中的应用属于数据通信中的两种位同步方法里的自同步法（另一种是外同步法），即接收方利用包含有同步信号的特殊编码从信号自身提取同步信号来锁定自己的时钟脉冲频率，达到同步目的。

Encode and Decode

IEEE 802.4（令牌总线）和低速版的IEEE 802.3（以太网）中规定, 按照这样的说法, 01电平跳变表示1, 10的电平跳变表示0。

Ideas
1
2
3
4
5
6
7
8
9
5555555595555A65556AA696AA6666666955`转为二进制，根据01->1,10->0。可得到
0101->11
0110->10
1010->00
1001->01
decode得到
`11111111 11111111 01111111 11001011 11111000 00100110 00001010 10101010 10011111`
bin->hex，对比ID并不重合，根据八位倒序传输协议将二进制每八位reverse，转hex即可
flag：`FFFFFED31F645055F9
1
2
3
4
5
6
7
8
9
10
11
cipher='5555555595555A65556AA696AA6666666955'
def iee(cipher):
    tmp=''
    for i in range(len(cipher)):
        a=bin(eval('0x'+cipher[i]))[2:].zfill(4)
        tmp=tmp+a[1]+a[3]
        print(tmp)
    plain=[hex(int(tmp[i:i+8][::-1],2))[2:] for i in range(0,len(tmp),8)]
    print(''.join(plain).upper())

iee(cipher)

[NPUCTF2020]这是什么觅🐎（观察）

用记事本打开是个乱码·

image-20240909151824355

但我们看到开头那个pk，我们想到zip文件，我们将后缀改为zip，成功打开文件

image-20240909151910551

看到有一个字条和日历，猜测是类似矩阵的原理,

1
F1 W1 S22 S21 T12 S11 W1 S13

两个s应该是s1对应周六，s2对应周日

字母最后的数字对应所在的行数

例如F1，第一行的星期五

1
3 1 12 5 14 4 1 18

对照字母表 calendar，flag{calendar}

浪里淘沙（脑洞）

打开txt文档发现大量的单词，再结合题目给到的一串数字4、8、11、15、16可以考虑到是跟字频有关

我们打开万能的wps进行查询

image-20240914150507182

然后放到excel进行排序

image-20240914150532083

标注起题目要求的编号组合起字符串即可得到flag

flag{weshouldlearnthecrypto}

[WUSTCTF2020]B@se（base64变表）

题目附件内容：

img

首先通过观察题目字符特征很明显是base64编码，第一行的密文是通过下面给的base64的变表，但是仔细观察缺少了四个字符，因此我们需要写脚本把缺少的字符给还原出来

爆破脚本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import string
c = 'JASGBWcQPRXEFLbCDIlmnHUVKTYZdMovwipatNOefghq56rs****kxyz012789+/'
for i in string.ascii_letters + string.digits:  # string.ascii_letters所有字母  string.digits所有数字
    if(i not in c):
        print(i,end='')
# ju34

很明显爆破出来的是“ju34”，但是我们还不知道他的原始排列的顺序是什么？，因此需要我们对着四个字符与密文进行一个排列组合，并可以解出明文。
代码如下（这里是参考了一些大佬的脚本）：
import binascii
import itertools
cipher = 'MyLkTaP3FaA7KOWjTmKkVjWjVzKjdeNvTnAjoH9iZOIvTeHbvD' # 全排列组合
s = ['j','u','3','4']
for i in itertools.permutations(s,4): # 4就是把s列表里的字母4个为一组排列
    k = "JASGBWcQPRXEFLbCDIlmnHUVKTYZdMovwipatNOefghq56rs"+ "".join(i) + "kxyz012789+/"  # "".join(i)排列的结果（join() 方法用于将序列中的元素以指定的字符连接生成一个新的字符串）
    a = ""
    for j in cipher:
        a += bin(k.index(j))[2:].zfill(6)
    print(binascii.a2b_hex(hex(eval("0b"+a))[2:-1]))  # a2b_hex和binascii.unhexlify可以为16进制的 bytes 类型，也可以为十六进制 str 类型
                                                      # 举例：这里转为16进制后会出现0x471L，所以只有去掉0x和L就有了[2:-1]

运行结果：

img

很明显图中框出来的地方就是最后的flag值

总结：此题考察了缺损的base64变表，需要使用爆破脚本破解出明文。

[AFCTF2018]Single（爆破）

我们下载附件，发现里面有个c语言程序和一个文件

通过代码分析，我们发现Cipher.txt是一个加密后的文件，仔细观察，很明显示是一个无规律替换加密，我们使用词频分析

网站：http://quipqiup.com/

得到flag

image-20240926192619737

或者我们逆向输出

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
#include <bits/stdc++.h>
using namespace std;
int main()
{
	freopen("Cipher.txt","r",stdin);//输入输出换一下
	freopen("Plain.txt","w",stdout);//输入输出换一下
	map<char, char> f;
	int arr[26];
	for(int i=0;i<26;++i){
		arr[i]=i;
	}
	random_shuffle(arr,arr+26);
	for(int i=0;i<26;++i){
		f['a'+i]='a'+arr[i];
		f['A'+i]='A'+arr[i];
	}
	char ch;
	while((ch=getchar())!=EOF){
		if(f.count(ch)){
            //反向转换一下，通过value>>key
			for(map<char,char>::iterator it = f.begin();it!=f.end();it++)
			{
				if(it->second == ch)
				{
				  putchar(it->first);
				  break;
				}
			}
		}else{
			putchar(ch);
		}
	}
	return 0;
}

得到加密前的文件，找到flag

鸡藕椒盐味（海明校验码）

image-20241009211038399

1.分析校验位数

从题目可知验证码为110010100000共12位，校验位一般都是在2^n的位置，所以共有4位校验码在1，2，4，8位置

拓展：海明验证码公式：2^r≥k+r+1 （r为校验位 ，k为信息位），如本验证码本来有8位信息码，带入公式可得r=4，所以在1，2，4，8位置添加相应校验码

2.画表

题目中提到打印的时候倒了一下，所以将信息位倒着填入表中

1 2 3 4 5 6 7 8 9 10 11 12 位数
0 0 1 0 0 0 1 1 信息位（D）
R1 R2 R3 R4 校验位（R）

3.求校验位的值

例如：1由第一位R1来校验；2由第二位R2来校验；由于3=1+2（1和2指的是位数，都是2的n次方）所以3由第一位R1和第二位R2校验，4由第四位R3校验，5和3道理是一样的，5=1+4（2^0+2^2）;6=2+4;7=1+2+4，依次类推。得出下表：

海明码位号 占用的校验位号 校验位
1 1 R1
2 2 R2
3 1、2 R1、R2
4 4 R3
5 1、4 R1、R3
6 2、4 R2、R3
7 1、2、4 R1、R2、R3
8 8 R4
9 1、8 R1、R4
10 2、8 R2、R4
11 1、2、8 R1、R2、R4
12 4、8 R3、R4

进行汇总，看每个校验位都确定了哪一位。

R1：1、3、5、7、9、11

R2：2、3、6、7、10、11

R3：4、5、6、7、12

R4：9、10、11、12

最后用异或运算求出R1、R2、R3、R4、R5的值（以R1为例）：

R1=D1⊕D3⊕D5⊕D7⊕D9⊕D11=1

以此类推：R1=1,R2=0,R3=0,R4=0

可以看到P1P2P3P4=0001,R1R2R3R4=1000

可以求得监督位（异或）：

0 0 0 1 验证码中的校验码
1 0 0 0 求得的校验码
1 0 0 1 监督位

监督位不为0000，说明接收方生成的校验位和收到的校验位不同，错误的位数是监督位的十进制即9，所以把D9就是题目中提到的错误，得到正确验证码110110100000，然后根据提示MD5hash一下就出来了。

1
2
3
4
5
6
7
8
1 import hashlib
2 c="110110100000"
3 md=hashlib.md5()
4 md.update(c.encode("utf8"))
5 flag = md.hexdigest()
6 print(flag)
7 
8 #d14084c7ceca6359eaac6df3c234dd3b

套入flag{}即可得到答案flag{d14084c7ceca6359eaac6df3c234dd3b}

[AFCTF2018]BASE

我们随便截取文件的一段内容，发现能进行多段解密

1