新春战役部分Crypto题解

尝试做一下简单的Crypto题

easyRSA

题目给出了$n,e_1,e_2,c_1,c_2$,猜测是相同密文相同模数用不同加密指数加密的RSA,使用共模攻击

求解$s$和$t$,使得$se_1+te_2=\mathrm{gcd}(e_1,e_2)$成立,接着可以直接解密

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import gmpy2
from Crypto.Util.number import long_to_bytes
n = 27560959918385616419486273009594513460044316476337842585463553105701869531698366304637678008602799005181601310816935394003041930445509801196554897781529962616349442136039951911764620999116915741924245788988332766182305635804754798018489793066811741026902011980807157882639313892932653620491354630354060462594865874663773934670618930504925812833202047183166423043264815905853486053255310346030416687430724204177468176762512566055165798172418622268751968793997676391170773216291607752885987933866163158257336522567086228092863302685493888839866559622429685925525799985062044536032584132602747754107800116960090941957657
e1 = 464857
e2 = 190529
c1 = 21823306870841016169952481786862436752894840403702198056283357605213928505593301063582851595978932538906067287633295577036042158302374948726749348518563038266373826871950904733691046595387955703305846728530987885075910490362453202598654326947224392718573893241175123285569008519568745153449344966513636585290770127055273442962689462195231016899149101764299663284434805817339348868793709084130862028614587704503862805479792184019334567648078767418576316170976110991128933886639402771294997811025942544455255589081280244545901394681866421223066422484654301298662143648389546410087950190562132305368935595374543145047531
c2 = 9206260935066257829121388953665257330462733292786644374322218835580114859866206824679553444406457919107749074087554277542345820215439646770680403669560474462369400641865810922332023620699210211474208020801386285068698280364369889940167999918586298280468301097349599560130461998493342138792264005228209537462674085410740693861782834212336781821810115004115324470013999092462310414257990310781534056807393206155460371454836230410545171068506044174001172922614805135260670524852139187370335492876094059860576794839704978988507147972109411033377749446821374195721696073748745825273557964015532261000826958288349348269664

g, s, t = gmpy2.gcdext(e1, e2)
if s < 0:
s = -s
c1 = gmpy2.invert(c1, n)
if t < 0:
t = -t
c2 = gmpy2.invert(c2, n)

flag = (pow(c1, s, n) * pow(c2, t, n)) % n
flag = long_to_bytes(flag)
print flag
# flag{WuHanJiaYou!!!!!!}

easy_RSA

题目如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#!/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))

可以看到genkey函数中,生成的$p$,$q$是有关系的,假设$\mathrm{bit}=x$,根据题意有

于是我们得到了方程组

得到一元二次方程

通过对$n$开根,我们可以知道$\sqrt{n}$约为102x位的数,即$p$,$q$也为102x位的数,即$x=102\mathrm{x}$

通过范围遍历,求得满足方程可解的$x$,同时求出$p$,$q$,另一方面

我们可以直接计算出$r$,进一步求出解密指数$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
import gmpy2
from Crypto.Util.number import long_to_bytes
n = 7772032347449135823378220332275440993540311268448333999104955932478564127911903406653058819764738253486720397879672764388694000771405819957057863950453851364451924517697547937666368408217911472655460552229194417053614032700684618244535892388408163789233729235322427060659037127722296126914934811062890693445333579231298411670177246830067908917781430587062195304269374876255855264856219488896495236456732142288991759222315207358866038667591630902141900715954462530027896528684147458995266239039054895859149945968620353933341415087063996651037681752709224486183823035542105003329794626718013206267196812545606103321821
c = 2082303370386500999739407038433364384531268495285382462393864784029350314174833975697290115374382446746560936195242108283558410023998631974392437760920681553607338859157019178565294055755787756920003102506579335103169629546410439497570201554568266074421781047420687173530441469299976286281709526307661219925667082812294328343298836241624597491473793807687939912877432920934022304415340311930199467500833755390490763679081685821950332292303679223444816832000945972744492944044912168217765156110058474974887372388032286968936052010531850687361328326741707441938740295431353926037925950161386891437897990887861853097318
e = 65537
for x in range(1020, 1025):
delta = pow(2 ** x - 65538, 2) - 4 * n
if delta >= 0:
print x
p = ((2 ** x - 65538) + gmpy2.iroot(delta, 2)[0]) / 2
q = n / p
r = (p - 1) * (q - 1)
d = gmpy2.invert(e, r)
flag = long_to_bytes(pow(c, d, n))
print flag

for x in range(1020, 1025):
delta = pow(2 ** x - 65538, 2) - 4 * n
if delta >= 0:
r = n - (2 ** x - 65538) + 1
d = gmpy2.invert(e, r)
flag = long_to_bytes(pow(c, d, n))
print flag
# 1024
# flag{8edf268a85202e540aaa070ac8ff63d2}
# flag{8edf268a85202e540aaa070ac8ff63d2}

warm_up

题目如下,challenge.py

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")

先从challenge入手,对n1和n2取公因数可以得到p,进一步得到q,由于

只剩$s$为未知数,但是这里的$e_1$并不是质数,且$\mathrm{gcd}(e_1,\mathrm{phi})=2$,选取$e_3=e_1/2$,计算其模逆,即$d\cdot e_3\equiv 1 \mathrm{mod\ phi}$ ,由此可得

同时也发现$p$,$q$都是模4余3的数,这时候就是一个Rabin密码,利用Rabin密码解

使用拓展欧几里得算法,求解

最后使用中国剩余定理,求得四个可能解

得到了$s$的可能取值后,$n_3$就可以求出,进而求出key

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

再看到encode,先异或求回第10行的dec,第10行中,将dec与dec左移200位异或再取回低355位,可以知道,得到的dec的低200位是由0与原dec低200位异或得到的,这里直接异或回去就可以得到原dec低200位,再拿这原dec低200位左移200位与现dec异或再取355-200位,就是原dec的高位

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
import gmpy2
from Crypto.Util.number import long_to_bytes
c1 = 9977992111543474765993146699435780943354123551515555639473990571150196059887059696672744669228084544909025528146255490100789992216506586730653100894938711107779449187833366325936098812758615334617812732956967746820046321447169099942918022803930068529359616171025439714650868454930763815035475473077689115645913895433110149735235210437428625515317444853803605457325117693750834579622201070329710209543724812590086065816764917135636424809464755834786301901125786342127636605411141721732886212695150911960225370999521213349980949049923324623683647865441245309856444824402766736069791224029707519660787841893575575974855
n1 = 15653165971272925436189715950306169488648677427569197436559321968692908786349053303839431043588260338317859397537409728729274630550454731306685369845739785958309492188309739135163206662322980634812713910231189563194520522299672424106135656125893413504868167774287157038801622413798125676071689173117885182987841510070517898710350608725809906704505037866925358298525340393278376093071591988997064894579887906638790394371193617375086245950012269822349986482584060745112453163774290976851732665573217485779016736517696391513031881133151033844438314444107440811148603369668944891577028184130587885396017194863581130429121
n2 = 16489315386189042325770722192051506427349661112741403036117573859132337429264884611622357211389605225298644036805277212706583007338311350354908188224017869204022357980160833603890106564921333757491827877881996534008550579568290954848163873756688735179943313218316121156169277347705100580489857710376956784845139492131491003087888548241338393764269176675849400130460962312511303071508724811323438930655022930044289801178261135747942804968069730574751117952892336466612936801767553879313788406195290612707141092629226262881229776085126595220954398177476898915921943956162959257866832266411559621885794764791161258015571
key_encode = 154190230043753146353030548481259824097315973300626635557077557377724792985967471051038771303021991128148382608945680808938022458604078361850131745923161785422897171143162106718751785423910619082539632583776061636384945874434750267946631953612827762111005810457361526448525422842867001928519321359911975591581818207635923763710541026422076426423704596685256919683190492684987278018502571910294876596243956361277398629634060304624160081587277143907713428490243383194813480543419579737033035126867092469545345710049931834620804229860730306833456574575819681754486527026055566414873480425894862255077897522535758341968447477137256183708467693039633376832871571997148048935811129126086180156680457571784113049835290351001647282189000382279868628184984112626304731043149626327230591704892805774286122197299007823500636066926273430033695532664238665904030038927362086521253828046061437563787421700166850374578569457126653311652359735584860062417872495590142553341805723610473288209629102401412355687033859617593346080141954959333922596227692493410939482451187988507415231993
e1 = 125794
e2 = 42373
enc = 17403902166198774030870481073653666694643312949888760770888896025597904503707411677223946079009696809
p = gmpy2.gcd(n1, n2)
q = n1 / p
r = n2 / p
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e1 / 2, phi)
s_2 = pow(c1, d, n1)
m_p = pow(s_2, (p + 1) / 4, p)
m_q = pow(s_2, (q + 1) / 4, q)
g, y_p, y_q = gmpy2.gcdext(p, q)
s = [1,1,1,1]
s[0] = (y_p * p * m_q + y_q * q * m_p) % n1
s[1] = n1 - s[0]
s[2] = (y_p * p * m_q - y_q * q * m_p) % n1
s[3] = n1 - s[2]
for i in s:
n3 = p * q * i
r = (p - 1) * (q - 1) * (i - 1)
d2 = gmpy2.invert(e2, r)
key = pow(key_encode, int(d2), n3)
dec = enc ^ key
mask = int('1' * 335, 2)
mask_low = int('1' * 200, 2)
source_low = (dec ^ 0) & mask_low
source_high = ((source_low << 200) ^ dec) & mask
source_high >>= 200
source_high <<= 200
source = source_high | source_low
print long_to_bytes(source)
# flag{79cef3d7-2c49-4cc6-94a3-e058c6c42835}

simple_math

题目有点长,慢慢看,首先是main

1
2
3
4
5
6
7
8
if __name__=="__main__":
_E=65537
_P=gen_p()
_Q=gen_q()
assert(gcd(_E,(_P-1)*(_Q-1))==1)
_M=bytes_to_long(flag)
_C=pow(_M,_E,_P*_Q)
print("ciphertext:",_C)

加密指数$e$是已知的,$p$,$q$由指定函数生成

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)

先生成$ABC$三个数,会打印出来,再取两个模数$N_1$,$N_2$,这里也调用指定函数

1
2
3
4
5
6
7
8
9
10
11
12
13
def gen_prime(N):
A=0
while 1:
A=getPrime(N)
if A%4==3:
break
return A

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

是一个迭代乘取模的过程,即

取到两个模数后,生成一个seed1,然后用nextprime取到这个$p$

由于参数都已知,可以直接代进去跑,但是数太大了,有限时间内求不出来,考虑其他解法

可以发现,gen_prime是要求这个质数模4余3的

由Wilson定理可知,设$p$是一个素数,则有

以及它的推论,设$p$是一个素数且 $p\equiv 3(\mathrm{mod\ 4})$,则有

这里的$B$就满足$\frac{A-1}{2}$,所以$N_1=\pm1$,再取正就是$N_1=1$

假设$R=\mathrm{randint}(1e3,1e5)=A-C$,$N_2$求解过程如下

由于

可得

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)

$q$的生成比较麻烦,先取1024位的$p$,$q$,再取到模数$n$,打印出来,$e$是一个50比特位的与phi互质的数,也给出了$e\cdot d$,接着生成一个seed2,然后用nextprime取到这个$q$

在知道$e\cdot q$的情况下,是可以分解$n$的(已知d分解n),于是就能求出$q$

当$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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
import sympy
from gmpy2 import gcd,invert
from random import randint
from Crypto.Util.number import *


A = 17837832555368308689786098708027973117794970348203719986383141676940062201987761202777419099369816828481341695174601689881519219806887761505932440928699539
C = 17837832555368308689786098708027973117794970348203719986383141676940062201987761202777419099369816828481341695174601689881519219806887761505932440928632158
n = 641840878174982655326850312496169636378455577115347500957057267640600977102280072913438154955029114771051709087809927454279064916870408880749853740239718248642560401110078626938726443568692572803490357236810832674229312155746539894173791356805341671586393273678865952155249500341932905426105470392415353610397045835698808163501258474762363712287163328526252399904787053101799058499120606154737990300449437479282435046167055009692493712202386368849122605419812883126887833074654434641607372149411668612504466768080306339558792828063148576123738980431264608446603326193849200810553196864085478463086993422774817059853949748247896512719994166090254440232652496451104455075071560127966288341488523110118075041150491577844082366096788215046025436488554795141938458493258409150407281215473354273599246314944034941237527510171900646139987019380766717951556307441871365874564881565374638513827494801194029940895912077179028101890662760455651864691251980479400416227456995236912364846811949410786643764713673564022863007331006828562341241738846980912184411395632790556038655767763976115640962139547171909279164623846000835333857705944581269631616760405747716520672142021728850694537269211784578408601266217928819863736428173736140161826738813
ed = 534634151124279413732259524933495479098721499860333007593590357554306358799023578194908726136928354695079848972480649724456088941906723794709312712191247045425297126517594344899286925836796680956816064609089090503579894117057252969264121691849003333804607728687046319857910698511132867345476426833313854575436202087209472834349551593011689755514138197238955298350562839877955001729313715223006875793667570760703418551390980455326976431990257513342820095246552412287184147009729875110446230949824384166464485840066906862476445054049749692262294734099027915906839812656254886862402603631321290156949953461665657610306709058617222159635281067103921037090824796905267992798715820128476225045484793453227511548884919811033318570386881936137713666127231317606909893143214808788822341878386939352957962886113639632559883992777992209148001401767753558732492213499792179169681405789041595765504039612494711563472885565786566625643290565526077483663342991770220261962082523632475094223960703649343802215392245948547397211539801128773253646005228684994277460378625729491412757387260415740823541731482803143732545953736392746596116269262129834845033889284145602522548909021358829175225208236295389454408336909318816490014229410357900614079212880259236238467905
ciphertext = 183288709028723976658160448336519698700398459340947322152692016513169599029222514445118399653225032641541100129985101994918772329046946295962244096646038598600865786096896989355554955041779941259413115779915405468832327321189345505283184153652727885422718280179025251186380977491993641792341259672566237363655347151343020354489781675539571788934759950303331075098574759853670802171054084321131703969504258663714257549258635956184694450566287845760701724862418909255930636298209146539578608879672058346906370035692078859844402832322545368347681121504910035471822137023626638953992968941166744998545450662434365836169688461834868137046528403401190395486501502489519341656581057940794141420456022102711505759074332049547354944074402136763186087462931985682293826106916791831371302
R = A - C
N1 = 1
R = R - 1
N2 = -1
while R >= 1:
N2 = (N2) * invert(A - R, A) % A
R = R - 1
seed1 = 2019 * N1 + 2020 * N2
_P = sympy.nextprime(seed1)
print "p: %d" % _P

def cal_from_d(N, ed):
r = ed - 1
s = 2
while r % s == 0:
s *= 2
r = r / (s / 2)
w = getRandomRange(1, N)
x = GCD(w, N)
if 1 < x and x < N:
return x, N / x
v = pow(w, r, N)
if v % N == 1:
return -1, -1
v_ = 0
while v % N != 1:
v_ = v
v = pow(v, 2, N)
if v_ % N == N - 1:
return -1, -1
p = GCD(v_ + 1, N)
return p, N / p

q, p = cal_from_d(n, ed)
while p == -1 and q == -1:
q, p = cal_from_d(n, ed)
seed2 = 2020 * p - 2019 * q
if seed2 < 0:
seed2 = (-1) * seed2
_Q = sympy.nextprime(seed2)
print "q: %d" % _Q

_E = 65537

_PHI = (_P - 1) * (_Q - 1)

print "invert(%d, %d)" % (_E, _PHI)
_D = invert(_E, _PHI)
flag = pow(ciphertext, _D, _P * _Q)
print long_to_bytes(flag)
# flag{152ab12f-655a-ce34-98ea-1268acb6e862}

TODO

还有几道暂时不会


  cryptorsa

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×