春秋杯新春战役网络安全公益赛

Posted on

warm_up

题目如下

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

q=getPrime(1024)
p=getPrime(1024)
r=getPrime(1024)
s=getPrime(1500)

e1=125794
e2=42373

n1=p*q
n2=p*r
n3=p*q*s
c1=pow(s,e1,n1)
Key=int(KEY.encode('hex'),16)
key_encode=pow(Key,e2,n3)

with open("enc","a")as f:
    f.write("c1: "+str(c1)+"\n")
    f.write("n1: "+str(n1)+"\n")
    f.write("n2: "+str(n2)+"\n")
    f.write("key_encode: "+str(key_encode)+"\n")

encode.py如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from flag import flag
import os

KEY = os.urandom(len(flag))

dec=int(flag.encode('hex'),16)

assert len(bin(dec)[2:])==335
mask=int('1'*335,2)
dec=(dec^dec<<200 )&mask
enc=dec^bytes_to_long(KEY)
print "enc: "+str(enc)

#enc: 17403902166198774030870481073653666694643312949888760770888896025597904503707411677223946079009696809

由题目可知c1、n1、n2、key_encode，由于n1、n2存在相同的因子p，因此可以计算出p、q、r，那么就要先计算出s再求n3，才能计算出Key从而求出flag

令phi1 = (p-1)*(q-1)，由于gcd(e1,phi1)=2因此不能直接求出

参考https://www.anquanke.com/post/id/164575

可以求出s^2 mod n1的值

那么接下来就是 e=2，n1可被分解的rsa求解，求出n3之后就可以轻松地求出Key，利用z3求出原始dec的值就可以得到flag了

脚本如下

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
# -*- coding:utf8 -*-
import gmpy2
from Crypto.Util.number import long_to_bytes

c1 = 9977992111543474765993146699435780943354123551515555639473990571150196059887059696672744669228084544909025528146255490100789992216506586730653100894938711107779449187833366325936098812758615334617812732956967746820046321447169099942918022803930068529359616171025439714650868454930763815035475473077689115645913895433110149735235210437428625515317444853803605457325117693750834579622201070329710209543724812590086065816764917135636424809464755834786301901125786342127636605411141721732886212695150911960225370999521213349980949049923324623683647865441245309856444824402766736069791224029707519660787841893575575974855
n1 = 15653165971272925436189715950306169488648677427569197436559321968692908786349053303839431043588260338317859397537409728729274630550454731306685369845739785958309492188309739135163206662322980634812713910231189563194520522299672424106135656125893413504868167774287157038801622413798125676071689173117885182987841510070517898710350608725809906704505037866925358298525340393278376093071591988997064894579887906638790394371193617375086245950012269822349986482584060745112453163774290976851732665573217485779016736517696391513031881133151033844438314444107440811148603369668944891577028184130587885396017194863581130429121
n2 = 16489315386189042325770722192051506427349661112741403036117573859132337429264884611622357211389605225298644036805277212706583007338311350354908188224017869204022357980160833603890106564921333757491827877881996534008550579568290954848163873756688735179943313218316121156169277347705100580489857710376956784845139492131491003087888548241338393764269176675849400130460962312511303071508724811323438930655022930044289801178261135747942804968069730574751117952892336466612936801767553879313788406195290612707141092629226262881229776085126595220954398177476898915921943956162959257866832266411559621885794764791161258015571
key_encode = 154190230043753146353030548481259824097315973300626635557077557377724792985967471051038771303021991128148382608945680808938022458604078361850131745923161785422897171143162106718751785423910619082539632583776061636384945874434750267946631953612827762111005810457361526448525422842867001928519321359911975591581818207635923763710541026422076426423704596685256919683190492684987278018502571910294876596243956361277398629634060304624160081587277143907713428490243383194813480543419579737033035126867092469545345710049931834620804229860730306833456574575819681754486527026055566414873480425894862255077897522535758341968447477137256183708467693039633376832871571997148048935811129126086180156680457571784113049835290351001647282189000382279868628184984112626304731043149626327230591704892805774286122197299007823500636066926273430033695532664238665904030038927362086521253828046061437563787421700166850374578569457126653311652359735584860062417872495590142553341805723610473288209629102401412355687033859617593346080141954959333922596227692493410939482451187988507415231993
p = gmpy2.gcd(n1,n2)
q = n1 // p
r = n2 // p

e1 = 125794
e2 = 42373

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

# gmpy2.gcd(e1,phi1) = 2
b = 2
a = e1 // b
b_d = gmpy2.invert(a,phi1)
# s1为 s^2 mod n1 的值
s1 = pow(c1,b_d,n1)

# 接下来就是 e=2，n1可被分解的rsa求解
inv_p = gmpy2.invert(p, q)
inv_q = gmpy2.invert(q, p)
mp = pow(s1, (p + 1) / 4, p)
mq = pow(s1, (q + 1) / 4, q)
a = (inv_p * p * mq + inv_q * q * mp) % n1
b = n1 - int(a)
c = (inv_p * p * mq - inv_q * q * mp) % n1
d = n1 - int(c)
s = 0
for i in (a, b, c, d):
    res = '%x' % i
    if len(res) % 2 != 0:
        res = '0' + res
    # 判断s
    if len(bin(int(res,16))[2:]) == 1500:
        s = int(res,16)

n3 = p * q * s
phi2 = (p-1)*(q-1)*(s-1)
d2 = gmpy2.invert(e2,phi2)

key = pow(key_encode,d2,n3)

mask = int('1'*335,2)
enc = 17403902166198774030870481073653666694643312949888760770888896025597904503707411677223946079009696809
dec = (enc ^ key) & mask
print dec

# z3求解出dec
# from z3 import *
# dec = BitVec('dec',335)
# s = Solver()
# s.add(dec^dec<<200 == 44867094288539703398303699988301529578853803185235251266149334568627427478369642905826739191805064573)
# s.check()
# model = s.model()
# print model

init_dec = 56006392793406559099439443677783485635981102966187108024917485809998586420617423745948662502526236029
print long_to_bytes(init_dec)

simple_math

由题目可知，要想求出M那就要先求出P、Q，要求P就要先知道N1、N2

1
2
3
4
5
6
7
8
9
10
11
12
13
def gen_p():
    A=gen_prime(513)
    print("A:",A)
    B=(A-1)//2
    C=A-randint(1e3,1e5)
    print("C:",C)
    
    N1=gen_N(A,B)
    if N1<0:
        N1=(-1)*N1
    N2=gen_N(A,C)
    seed1=2019*N1+2020*N2
    return sympy.nextprime(seed1)

由gen_N()函数可知，result = B! % A

1
2
3
4
5
def gen_N(A,B):
    result=1
    for i in range(2,B+1):
        result=(result*i)%A
    return result

看到阶层就可以联想到wilson定理，在之前的博客中也大概写了一下wilson定理，即对于质数p，有

1
2
3
(p-1)! mod p = -1
(p-2)! mod p = 1
(p-1) mod p = -1

N1推导过程

1
2
3
4
5
6
7
8
9
10
11
12
13
A为质数，B = ((A-1)//2 )! mod A ，
N1 = gen_N(A,B) = result = ((A-1)//2 )! mod A
(A-1)! = (A-1)(A-2)...(A-(A-1)//2)((A-1)//2 )! = -1 mod A
又因为 
A-1 = -1 mod A  A-2 = -2 mod A  A-(A-1)//2 = -(A-1)//2 mod A
所以
(A-1)! = (-1)^((A-1)//2)((A-1)//2 )!((A-1)//2 )! mod A = -1 mod A
由于(A-1)//2为奇数，所以(-1)^((A-1)//2) = -1，化简得
((A-1)//2 )!((A-1)//2 )! = 1 mod A
令x = ((A-1)//2 )!，有 x^2 - 1 = 0 mod A
即 (x+1)(x-1) = 0 mod A
所以 x = 1 或 x = -1
因为N1 > 0，所以 N1 = 1

N2推导过程

1
2
3
4
5
6
A为质数，存在 (A-2)! = 1 mod A 
C = A-randint(1e3,1e5)  //以下用 C = A - X 代替
N2 = gen_N(A,C) = result = C! mod A = (A - X)! mod A
(A-2)! = (A-2)(A-3)...(A-X+1)(A-X)! = (A-2)(A-3)...(C+1)C! = 1 mod A
因此
N2 = C! mod A = gmpy2.invert((A-2)(A-3)...(C+1),A)

求出N1、N2，P就求出来了，接下来求Q

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def gen_q():
    p=getPrime(1024)
    q=getPrime(1024)
    assert(p<q)
    n=p*q
    print("n:",n)
    e=getRandomNBitInteger(50)
    phi=(p-1)*(q-1)
    while gcd(e,phi)!=1:
        e=getRandomNBitInteger(50)
    d=invert(e,phi)
    print("e*d:",e*d)
    seed2=2020*p-2019*q
    if seed2<0:
        seed2=(-1)*seed2
    return sympy.nextprime(seed2)

已知ed，n，求p、q，参考如下文章

[http://soreatu.com/ctf/writeups/Writeup%20for%20easyRSA%20in%202019%E7%A5%9E%E7%9B%BE%E6%9D%AF.html#writeup-for-easyrsa-in-2019%E7%A5%9E%E7%9B%BE%E6%9D%AF](http://soreatu.com/ctf/writeups/Writeup for easyRSA in 2019神盾杯.html#writeup-for-easyrsa-in-2019神盾杯)

最终脚本如下

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
# -*- coding:utf8 -*-
import sympy
import gmpy2
from Crypto.Util.number import long_to_bytes

A = 17837832555368308689786098708027973117794970348203719986383141676940062201987761202777419099369816828481341695174601689881519219806887761505932440928699539
C = 17837832555368308689786098708027973117794970348203719986383141676940062201987761202777419099369816828481341695174601689881519219806887761505932440928632158
n = 641840878174982655326850312496169636378455577115347500957057267640600977102280072913438154955029114771051709087809927454279064916870408880749853740239718248642560401110078626938726443568692572803490357236810832674229312155746539894173791356805341671586393273678865952155249500341932905426105470392415353610397045835698808163501258474762363712287163328526252399904787053101799058499120606154737990300449437479282435046167055009692493712202386368849122605419812883126887833074654434641607372149411668612504466768080306339558792828063148576123738980431264608446603326193849200810553196864085478463086993422774817059853949748247896512719994166090254440232652496451104455075071560127966288341488523110118075041150491577844082366096788215046025436488554795141938458493258409150407281215473354273599246314944034941237527510171900646139987019380766717951556307441871365874564881565374638513827494801194029940895912077179028101890662760455651864691251980479400416227456995236912364846811949410786643764713673564022863007331006828562341241738846980912184411395632790556038655767763976115640962139547171909279164623846000835333857705944581269631616760405747716520672142021728850694537269211784578408601266217928819863736428173736140161826738813
ed = 534634151124279413732259524933495479098721499860333007593590357554306358799023578194908726136928354695079848972480649724456088941906723794709312712191247045425297126517594344899286925836796680956816064609089090503579894117057252969264121691849003333804607728687046319857910698511132867345476426833313854575436202087209472834349551593011689755514138197238955298350562839877955001729313715223006875793667570760703418551390980455326976431990257513342820095246552412287184147009729875110446230949824384166464485840066906862476445054049749692262294734099027915906839812656254886862402603631321290156949953461665657610306709058617222159635281067103921037090824796905267992798715820128476225045484793453227511548884919811033318570386881936137713666127231317606909893143214808788822341878386939352957962886113639632559883992777992209148001401767753558732492213499792179169681405789041595765504039612494711563472885565786566625643290565526077483663342991770220261962082523632475094223960703649343802215392245948547397211539801128773253646005228684994277460378625729491412757387260415740823541731482803143732545953736392746596116269262129834845033889284145602522548909021358829175225208236295389454408336909318816490014229410357900614079212880259236238467905

# 求_P
def cal_N2(A,C):
    result = 1
    for i in range(C+1,A-1):
        result = (result * i) % A
    result = gmpy2.invert(result,A)
    return result

N1 = 1
N2 = cal_N2(A,C)
seed1 = 2019*N1+2020*N2
_P = sympy.nextprime(seed1)

# 求_Q
k = ed - 1
x = pow(2, k // (2**6), n)
assert x != 1
p = gmpy2.gcd(x-1,n)
q = n // p
if p > q:
    p,q = q,p
seed2 = 2020*p-2019*q
if seed2 < 0:
    seed2 = (-1)*seed2
_Q = sympy.nextprime(seed2)

# 求flag
_E = 65537
_N = _P * _Q
assert(gmpy2.gcd(_E,(_P-1)*(_Q-1)) == 1)
phi = (_P-1)*(_Q-1)
_D = gmpy2.invert(_E,phi)
_C = 183288709028723976658160448336519698700398459340947322152692016513169599029222514445118399653225032641541100129985101994918772329046946295962244096646038598600865786096896989355554955041779941259413115779915405468832327321189345505283184153652727885422718280179025251186380977491993641792341259672566237363655347151343020354489781675539571788934759950303331075098574759853670802171054084321131703969504258663714257549258635956184694450566287845760701724862418909255930636298209146539578608879672058346906370035692078859844402832322545368347681121504910035471822137023626638953992968941166744998545450662434365836169688461834868137046528403401190395486501502489519341656581057940794141420456022102711505759074332049547354944074402136763186087462931985682293826106916791831371302
_M = pow(_C,_D,_N)
print long_to_bytes(_M)

easy_RSA

题目如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#!/usr/bin/env python
from Crypto.Util.number import *
from secret import FLAG,BIT
def genkey(bit):
	while True:
		p = getPrime(bit)
		q = (2 ** bit - 1) ^ p + 65537
		if isPrime(q):
			return p, q

p, q = genkey(BIT)
m = bytes_to_long(flag)
e = 65537
n = p*q
c = pow(m,e,n)

print('n={}'.format(n))
print('c={}'.format(c))

#n=7772032347449135823378220332275440993540311268448333999104955932478564127911903406653058819764738253486720397879672764388694000771405819957057863950453851364451924517697547937666368408217911472655460552229194417053614032700684618244535892388408163789233729235322427060659037127722296126914934811062890693445333579231298411670177246830067908917781430587062195304269374876255855264856219488896495236456732142288991759222315207358866038667591630902141900715954462530027896528684147458995266239039054895859149945968620353933341415087063996651037681752709224486183823035542105003329794626718013206267196812545606103321821
#c=2082303370386500999739407038433364384531268495285382462393864784029350314174833975697290115374382446746560936195242108283558410023998631974392437760920681553607338859157019178565294055755787756920003102506579335103169629546410439497570201554568266074421781047420687173530441469299976286281709526307661219925667082812294328343298836241624597491473793807687939912877432920934022304415340311930199467500833755390490763679081685821950332292303679223444816832000945972744492944044912168217765156110058474974887372388032286968936052010531850687361328326741707441938740295431353926037925950161386891437897990887861853097318

容易得知BIT=1024，这里有一点需要注意的是异或（p+65537），不是异或p再加65537

1
q = (2 ** bit - 1) ^ p + 65537 = (2 ** bit - 1) ^ (p + 65537)

由于(2 ** bit - 1)的二进制全是1，因此

1
q = (2 ** bit - 1) ^ p + 65537 = (2 ** bit - 1) - (p + 65537)

然后通过z3求出p，就可以解出了

1
2
3
4
5
6
7
from z3 import *
p = Int('p')
s = Solver()
s.add( p * ((2 ** 1024 - 1) - p - 65537) == 7772032347449135823378220332275440993540311268448333999104955932478564127911903406653058819764738253486720397879672764388694000771405819957057863950453851364451924517697547937666368408217911472655460552229194417053614032700684618244535892388408163789233729235322427060659037127722296126914934811062890693445333579231298411670177246830067908917781430587062195304269374876255855264856219488896495236456732142288991759222315207358866038667591630902141900715954462530027896528684147458995266239039054895859149945968620353933341415087063996651037681752709224486183823035542105003329794626718013206267196812545606103321821)
s.check()
model = s.model()
print model

EasyRSA

普通的共模攻击

1
2
3
4
5
6
7
8
9
10
11
12
import gmpy2
from Crypto.Util.number import long_to_bytes
n = 27560959918385616419486273009594513460044316476337842585463553105701869531698366304637678008602799005181601310816935394003041930445509801196554897781529962616349442136039951911764620999116915741924245788988332766182305635804754798018489793066811741026902011980807157882639313892932653620491354630354060462594865874663773934670618930504925812833202047183166423043264815905853486053255310346030416687430724204177468176762512566055165798172418622268751968793997676391170773216291607752885987933866163158257336522567086228092863302685493888839866559622429685925525799985062044536032584132602747754107800116960090941957657
e1 = 464857
e2 = 190529
c1 = 21823306870841016169952481786862436752894840403702198056283357605213928505593301063582851595978932538906067287633295577036042158302374948726749348518563038266373826871950904733691046595387955703305846728530987885075910490362453202598654326947224392718573893241175123285569008519568745153449344966513636585290770127055273442962689462195231016899149101764299663284434805817339348868793709084130862028614587704503862805479792184019334567648078767418576316170976110991128933886639402771294997811025942544455255589081280244545901394681866421223066422484654301298662143648389546410087950190562132305368935595374543145047531
c2 = 9206260935066257829121388953665257330462733292786644374322218835580114859866206824679553444406457919107749074087554277542345820215439646770680403669560474462369400641865810922332023620699210211474208020801386285068698280364369889940167999918586298280468301097349599560130461998493342138792264005228209537462674085410740693861782834212336781821810115004115324470013999092462310414257990310781534056807393206155460371454836230410545171068506044174001172922614805135260670524852139187370335492876094059860576794839704978988507147972109411033377749446821374195721696073748745825273557964015532261000826958288349348269664

_, r, s = gmpy2.gcdext(e1, e2)

m = pow(c1, r, n) * pow(c2, s, n) % n
print long_to_bytes(m)