狗儿

热爱的话就坚持吧~

0%

两道密码题 - 上海市大学生网络安全大赛

发表于 分类于 ，

菜鸡刚开始学密码学，本文如果谬误，劳请师傅们轻点骂orz~

baby_dsa

给出task.py和data.

task.py:

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
#!/usr/bin/env python
from Crypto.Util.number import *
from hashlib import sha512,md5
from os import urandom
import random

def hash(message):
	return int(sha512(message).hexdigest(), 16)

def key_gen():
	q = getPrime(256)
	while True:
		p = random.getrandbits(2816)*q + 1
		if isPrime(p):
			print(p.bit_length())
			break
	while True:
		g = pow(random.randrange(1, p-1), (p-1)/q, p)
		if g != 1:
			break
	x = random.randrange(1, q)
	y = pow(g, x, p)
	pubkey = (p, q, g, y)
	privkey = x
	return pubkey, privkey

def sign(message, pubkey, privkey):
	p, q, g, y = pubkey
	x = privkey
	k = pow(y, x, g) * random.randrange(1, 512) % q
	r = pow(g, k, p) % q
	s = inverse(k, q) * (hash(message) + x * r) % q
	return r, s

def verify(message, signature, pubkey):
	p, q, g, y = pubkey
	r, s = signature
	if not (0 < r < q) or not (0 < s < q):
		return False
	w = inverse(s, q)
	u1 = (hash(message) * w) % q
	u2 = (r * w) % q
	v = ((pow(g, u1, p) * pow(y, u2, p)) % p) % q
	return v == r

pubkey, privkey = key_gen()
print(pubkey)

message1 = urandom(16).encode('hex')
signature1 = sign(message1, pubkey, privkey)
print(message1,signature1)
print(verify(message1, signature1, pubkey))

message2 = urandom(16).encode('hex')
signature2 = sign(message2, pubkey, privkey)
print(message2,signature2)
print(verify(message2, signature2, pubkey))

flag = 'flag{'+md5(long_to_bytes(privkey)).hexdigest()+'}'

data:

1
2
3
4
5
(3297226463037324458008837284498963372649038889390685051849680175016505646001761220109858921624266044035133134135402561235635833428206886888308027772353030767400921078346868377298401213812053250316002033941692272192644613252296579884516731560436501073253924457646558698855484781747029397755111633297587215976579633451933658235385386539518006570069653575146060016811911140614606471930327341368582979836042585406811352236326065292636484550807213756482153084427714549694264685695977531537425682212155553568848666088576932888234659355213664909753781753917401161977762663658097504411914908081677033980915039079517766159760522261279115347385813009437510156898969769563687869495721977265444799585634019880951532080217960456901788918439265788169910062822889580199366417455186595489973000351770200485095008494228829300145039695936946379585625051402553034971207474762463147744467360158847593356030745194143276254949463650698210515569533L, 82302835442112137125891403368151249910268706824854786126600390413622302196443L, 1156233264299340971106498371495495695225880592354374034142195518472540521911699506391311324676590685365234887170345722135060009885002334748836477169806166169806180231794918961214520698361874839110454610266388341977984902756569838594616255112661600466818870137432772800368859461445854700956291885576855069405183771903076277144927769029433730710613058788277691211698675287829143272152835171859480781061918556840079857761203012054552142555673071865310355331986288606422711525790877591376770834180618492794265362178603111236615495225612101250344421932588038244804199229449738675082560512062564365473035097263889257937140778993389305893378514344032352806521972367991027459721160744835688761657797398841523104074451793557924512992305640697344011520550723893828185707635141404445213445935586965289450282024222064488965878769991566367115153619761583843561579531705057955933288008556165952066173304891391375100346312776539530448611005L, 290999623787731812697719691852061290246619413463636312382146969900546384514710782843153962704851916091601679028830866176332331519515156301401537173069908181509028464322647352256632424684809349121024262597006913707483811117644197481959053785475083406472583099140506505071300193356002443007750220524932219191932969202270343323955035291396808472686684787610559114702054784699365490860392737061056233160308943296478540798353134878937088336672928162894332961762277559345860479916248086821117811990391025187125193074059001086441305977133252774698996653122297123447837449168657347308016270030881395674066421144002959751936839166935726200833785132736328859710351871352567511516142170956091885352178579302299634322254818383978585773136692588922976043617337904545396146755609284163743476297772686548475170197605412847689587171522453229055932712714154869989454808561458852031769119489235598402066924082778376081494632258448434048562053L)
('0234e7971889def7e60348f77db94b7a', (10859236269959765735236393779936305217305574331839234502190226708929991582386L, 13707557323895695260471053137828523837745895683218331343360027380310980108819L))
True
('16c5ac270b72f70319657b4410d985d4', (41960642246379067640524709416001536058292817319109764317369777224426218746518L, 74676725322515593502346275468843411563746982149373670021082686341369076719088L))
True

很明显，两次加密用了相同的私钥。去网上搜，搜到了这两篇：

原理讲得很清楚，复用私钥的话可以实现攻击。

上面两篇文章针对的是原版dsa，算是本题的弱化版，不过原理是相同的。

原版dsa的sign中k = pow(y, x, g) % q

而此题k = pow(y, x, g) * random.randrange(1, 512) % q

多乘了一个随机数。

重点看：

1
2
3
4
5
6
7
def sign(message, pubkey, privkey):
	p, q, g, y = pubkey
	x = privkey
	k = pow(y, x, g) * random.randrange(1, 512) % q
	r = pow(g, k, p) % q
	s = inverse(k, q) * (hash(message) + x * r) % q
	return r, s

码公式太麻烦了，菜鸡选择手写推导过程：

QQ图片20201116123625

QQ图片20201116123621

最后把除法换成乘法逆就好啦。

最终脚本如下：

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

def hash(message):
	return int(sha512(message).hexdigest(), 16)


def sign(message, pubkey, privkey, random1):
	p, q, g, y = pubkey
	x = privkey
	k = pow(y, x, g) * random1 % q
	r = pow(g, k, p) % q
	s = inverse(k, q) * (hash(message) + x * r) % q
	return r, s

public = (3297226463037324458008837284498963372649038889390685051849680175016505646001761220109858921624266044035133134135402561235635833428206886888308027772353030767400921078346868377298401213812053250316002033941692272192644613252296579884516731560436501073253924457646558698855484781747029397755111633297587215976579633451933658235385386539518006570069653575146060016811911140614606471930327341368582979836042585406811352236326065292636484550807213756482153084427714549694264685695977531537425682212155553568848666088576932888234659355213664909753781753917401161977762663658097504411914908081677033980915039079517766159760522261279115347385813009437510156898969769563687869495721977265444799585634019880951532080217960456901788918439265788169910062822889580199366417455186595489973000351770200485095008494228829300145039695936946379585625051402553034971207474762463147744467360158847593356030745194143276254949463650698210515569533, 82302835442112137125891403368151249910268706824854786126600390413622302196443, 1156233264299340971106498371495495695225880592354374034142195518472540521911699506391311324676590685365234887170345722135060009885002334748836477169806166169806180231794918961214520698361874839110454610266388341977984902756569838594616255112661600466818870137432772800368859461445854700956291885576855069405183771903076277144927769029433730710613058788277691211698675287829143272152835171859480781061918556840079857761203012054552142555673071865310355331986288606422711525790877591376770834180618492794265362178603111236615495225612101250344421932588038244804199229449738675082560512062564365473035097263889257937140778993389305893378514344032352806521972367991027459721160744835688761657797398841523104074451793557924512992305640697344011520550723893828185707635141404445213445935586965289450282024222064488965878769991566367115153619761583843561579531705057955933288008556165952066173304891391375100346312776539530448611005, 290999623787731812697719691852061290246619413463636312382146969900546384514710782843153962704851916091601679028830866176332331519515156301401537173069908181509028464322647352256632424684809349121024262597006913707483811117644197481959053785475083406472583099140506505071300193356002443007750220524932219191932969202270343323955035291396808472686684787610559114702054784699365490860392737061056233160308943296478540798353134878937088336672928162894332961762277559345860479916248086821117811990391025187125193074059001086441305977133252774698996653122297123447837449168657347308016270030881395674066421144002959751936839166935726200833785132736328859710351871352567511516142170956091885352178579302299634322254818383978585773136692588922976043617337904545396146755609284163743476297772686548475170197605412847689587171522453229055932712714154869989454808561458852031769119489235598402066924082778376081494632258448434048562053)
p, q, g, y = public

tmp1 = (b'0234e7971889def7e60348f77db94b7a', (10859236269959765735236393779936305217305574331839234502190226708929991582386, 13707557323895695260471053137828523837745895683218331343360027380310980108819))
tmp2 = (b'16c5ac270b72f70319657b4410d985d4', (41960642246379067640524709416001536058292817319109764317369777224426218746518, 74676725322515593502346275468843411563746982149373670021082686341369076719088))
message1, r1, s1 = tmp1[0], tmp1[1][0], tmp1[1][1]
message2, r2, s2 = tmp2[0], tmp2[1][0], tmp2[1][1]
hm1, hm2 = hash(message1), hash(message2)
#print(hm1, hm2)


for random1 in range(1, 512):
    for random2 in range(1, 512):
        random1_inv = inverse(random1, q)
        random_mul = random1_inv * random2
        x = (s1 * hm2 - s2 * hm1 * random_mul) * inverse(s2 * r1 * random_mul - s1 * r2, q)
        x = x % q
        #print(x)
        #print(sign(message1, public, x, random1))
        #print(tmp1[1])
        if sign(message1, public, x, random1) == tmp1[1]:
            print(x)
            flag = 'flag{'+md5(long_to_bytes(x)).hexdigest()+'}'
            print(flag)
            print(random2)
            exit()
    print(random1)


# 成功拿到flag后可以知道random1 = 36, random2 = 58 ^_^

baby_rsa

给出task.py和data.

task.py:

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
#!/usr/bin/env python
from Crypto.Util.number import *
from secret import FLAG,BIT
p = getPrime(BIT)
q = getPrime(BIT)
n = p*q

m = bytes_to_long(FLAG)
n=p*q
e = 65537
c = pow(m,e,n)

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


p1 = getPrime(BIT)
q1 = getPrime(BIT)
n1 = p1*q1
e1 = 264769
c1 = pow(p,e1,n1)
print('n1={}'.format(n1))
print('c1={}'.format(c1))
hint1 = pow(233*p1+q1,123,n1)
hint2 = pow(p1+q1,321,n1)
print('hint1={}'.format(hint1))
print('hint2={}'.format(hint2))


p2 = getPrime(BIT)
q2 = getPrime(BIT)
n2 = p2*q2
e2 = 467237
c2 = pow(p,e2,n2)
hint3 = (p2^q2+23333)*(p2**2+q2**2)
print('n2={}'.format(n2))
print('c2={}'.format(c2))
print('hint3={}'.format(hint3))

data:

1
2
3
4
5
6
7
8
9
10
11
12
13
n=17649959524397760997121068808256580843504587497910149453915162267396485718887518595291066193109877306674118444195689568088263844046660375223625289837992862053279345177671592293911174778827999488542179620983366850016034027115530276422989943300228066482304416809472413052663535805445730178026554076921827725694259203653909224978173857255494234555062560049936771927672590813681897238186260507539943545237569643120449213465796499750961465626495972566123774033404378255591053613115928255568749091129063492156842873395480632444228696955053141918113950854532182678159336565263274798149079981609244430557152399984535126235363
c=15029318220576201468560263535467919662488860043345492393144032736965870242713450606659777890850505132225711280093046172524095525322154673926523304203423191705454071359296529857716754655771123283983880428698763018843822679367577019725819696194151686979021896785125371586584321924453460309048191160124062645590495288978330433202359745254888236717638151156562967968775572180730587161672905799413277059329869890946648167796801765219831746094281346814783939724111424859058879220880599487372955861808493657218563898884555812145492576092463968720535434333471337338652526644364433874563267556126777216068855825634384513829424


n1=11941055546120835541933837916957535027223641642056156743752345801163456170772591807989846005495118671627583480778591488285910051133125545781378893719554427584148075540206612251653456701817071613890721071975616517809857996246607186607334395902967699076560894499607006508473605653089963092771854212576322017350805147649094768237953455009748131863337396511143680074932058392590124680763754449521538152648826051051725262170054340100951449328841662181738885435084388023374118710392556656584562494466181529819874959240003672308773193993983011133478065179503497212335076082903214298387572478483167372666139510894330498063363
c1=6581154435167641787433706075004561388301805860331946235823513860405803778235872737931884851831035226083382029584246800645018019413127765759061141252000392053167257633079915212463877266874219355926577661560935087214076228489015179444896502239970526394611817785461522402281447698895527412078173938006497062776091893518267645893781893160963255732937916279470200335626401698825349254177657209090710482565606571789980792435731381726512181109745347022096351073206312644630716411754744858295344041386540535791304586399357404127194796021552916370709209765337503596373097584818783365858724366310222037341353418913289811053095
hint1=1833359454277884547260964954436531463268066576658722989627564649033696969709536217088486700312933027950428272129950495535027288886651991915165684324611000436088979018485688408816231521968453936075696805751053276363477053225197411503384438465457747778257828546056452288773844510523924632927812430649476760238174873630670747649726829664710227729046538241685027106636190022704674813914658555522704254026934170921180880364524978980605216421102751036031187837852845145176233340544629656075196693935478996314670725777034314862269533476603759021249576881724904714872278034418134979560765768103587371983746026587223025082701
hint2=9228372398106611678286602895979417641404959178255543814408337636177265187498562357680073193750915958259886134885485814072189036077766844561767759359250327303362810094050654309593039106720830526510922411657244536811556192653039479590127726241656703727857177346638244353889205681446185783145149422115271311856344478861088252744224041700828934971839656845962952500398770632343211042957147026294673482712989723897728337948158121202913573351729397106490347537538903650384995023749669582138437808423835983027756877883503757939832290271053227076409279478395525689458736619490567940661071408166381129935073856561201013361053


n2=23455941227615775239443656539308297643982180829894484654402049952011754902910673016959293180763361297198028854846363769063194531340669913995607156520854107236145047519578431507504734946246387233119717455988604342629143169157458584024447539175522986194131420361207058659457842367747225416115718224096447064601381167752066587897491480906570491639285673739647530780716845522767589953844752161693528538842719783969776712946980214527220333249829977678665044026275482383388141550463655788551517246509583964301299148891187023831298370935139952329286769019479750190899942260635809156294531533965944585308646875084207341309299
c2=10715530306324673951548363119599726709032302490502503621262820402900708789479621786122202992270558740188089762633055937315273764776127007864314674666166396689989930966418725350921051566929420570800769227599053763394381881199633177787353312804172567883872711505640718496347152167195080365353610444414595776482688285765982794405522837470961426021769204869380013321460287585054427869064253751275281437353126670344963886123242042442941517661063614551338654515719677153884859086613947232523675577273003475854186999077452645748496990780555934158380320022165991608812421649555260206052852131416556798379301864938588470069672
hint3=1654703003093197323980549268127925734263220180218064821197891025480097895203898772683216556991095679066676330439571583420844073504061955914501552694851614664535404506850987626495748207864609522112425305618610542301021476293897450207456755153556758668114136827972390250711416496872911351908708498414711360774971803573424205005228478582765383952861132873141928265470739139939621697690745206102955277335631722299407771944405392356152203059038634579646087719909219308328870723043866071044134819385941485815488954689419436803675260443857367260605145787282706903883937049863141720288267973088830357903178618320711954941279581318770659585316616595448063292922358711609246297827512125769079432138746015092937410075719218112875217464130311880766565746303930574642167673189222237455675759570092101319641817787110871628322729294716699165480945617248862043371295021999756247543649749491705260692788753355626196854460802924198436342429850

先下结论再推导：

pow(hint2, 123, n1) - pow(hint1, 321, n1) 与 n1有公因子p1。

从而可以分解n1，求得第二次加密的m，即第一次加密的p。从而分解n。

然后是推导过程。这个推导是我自己琢磨的，很可能有更简单的推导而我不知道。如果师傅们知道更简单的推导思路，还请教教我这个菜鸡。

先说下这个公式，等下需要两次用到：

image-20201116124945152

然后同样是手写的推导过程：

QQ图片20201116161748

脚本：

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 libnum
import gmpy2

n1= 11941055546120835541933837916957535027223641642056156743752345801163456170772591807989846005495118671627583480778591488285910051133125545781378893719554427584148075540206612251653456701817071613890721071975616517809857996246607186607334395902967699076560894499607006508473605653089963092771854212576322017350805147649094768237953455009748131863337396511143680074932058392590124680763754449521538152648826051051725262170054340100951449328841662181738885435084388023374118710392556656584562494466181529819874959240003672308773193993983011133478065179503497212335076082903214298387572478483167372666139510894330498063363
hint1=1833359454277884547260964954436531463268066576658722989627564649033696969709536217088486700312933027950428272129950495535027288886651991915165684324611000436088979018485688408816231521968453936075696805751053276363477053225197411503384438465457747778257828546056452288773844510523924632927812430649476760238174873630670747649726829664710227729046538241685027106636190022704674813914658555522704254026934170921180880364524978980605216421102751036031187837852845145176233340544629656075196693935478996314670725777034314862269533476603759021249576881724904714872278034418134979560765768103587371983746026587223025082701
hint2=9228372398106611678286602895979417641404959178255543814408337636177265187498562357680073193750915958259886134885485814072189036077766844561767759359250327303362810094050654309593039106720830526510922411657244536811556192653039479590127726241656703727857177346638244353889205681446185783145149422115271311856344478861088252744224041700828934971839656845962952500398770632343211042957147026294673482712989723897728337948158121202913573351729397106490347537538903650384995023749669582138437808423835983027756877883503757939832290271053227076409279478395525689458736619490567940661071408166381129935073856561201013361053
p1 = int(gmpy2.gcd(pow(hint1, 321, n1) - pow(hint2, 123, n1), n1))

c1 = 6581154435167641787433706075004561388301805860331946235823513860405803778235872737931884851831035226083382029584246800645018019413127765759061141252000392053167257633079915212463877266874219355926577661560935087214076228489015179444896502239970526394611817785461522402281447698895527412078173938006497062776091893518267645893781893160963255732937916279470200335626401698825349254177657209090710482565606571789980792435731381726512181109745347022096351073206312644630716411754744858295344041386540535791304586399357404127194796021552916370709209765337503596373097584818783365858724366310222037341353418913289811053095
e1 = 264769
q1 = n1//p1
phi = (p1-1)*(q1-1)
d1 = inverse(e1, phi)
p = pow(c1, d1, n1)

n=17649959524397760997121068808256580843504587497910149453915162267396485718887518595291066193109877306674118444195689568088263844046660375223625289837992862053279345177671592293911174778827999488542179620983366850016034027115530276422989943300228066482304416809472413052663535805445730178026554076921827725694259203653909224978173857255494234555062560049936771927672590813681897238186260507539943545237569643120449213465796499750961465626495972566123774033404378255591053613115928255568749091129063492156842873395480632444228696955053141918113950854532182678159336565263274798149079981609244430557152399984535126235363
c=15029318220576201468560263535467919662488860043345492393144032736965870242713450606659777890850505132225711280093046172524095525322154673926523304203423191705454071359296529857716754655771123283983880428698763018843822679367577019725819696194151686979021896785125371586584321924453460309048191160124062645590495288978330433202359745254888236717638151156562967968775572180730587161672905799413277059329869890946648167796801765219831746094281346814783939724111424859058879220880599487372955861808493657218563898884555812145492576092463968720535434333471337338652526644364433874563267556126777216068855825634384513829424
e = 65537
q = n//p
phi = (p-1)*(q-1)
d = inverse(e, phi)
m = pow(c, d, n)
print(m)
msg = libnum.n2s(m)
print(msg)