RSA
题目如下
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
| from Crypto.Util.number import *
from secret import flag
n_2 = 675835056744450121024004008337170937331109883435712066354955474563267257037603081555653829598886559337325172694278764741403348512872239277008719548968016702852609803016353158454788807563316656327979897318887566108985783153878668451688372252234938716250621575338314779485058267785731636967957494369458211599823364746908763588582489400785865427060804408606617016267936273888743392372620816053927031794575978032607311497491069242347165424963308662091557862342478844612402720375931726316909635118113432836702120449010
n_3 = 91294511667572917673898699346231897684542006136956966126836916292947639514392684487940336406038086150289315439796780158189004157494824987037667065310517044311794725172075653186677331434123198117797575528982908532086038107428540586044471407073066169603930082133459486076777574046803264038780927350142555712567
e_1 = 65537
e_2 = 3
c_1 = 47029848959680138397125259006172340325269302342762903311733700258745280761154948381409328053449580957972265859283407071931484707002138926840483316880087281153554181290481533
c_2 = 332431
c_3 = 11951299411967534922967467740790967733301092706094553308467975774492025797106594440070380723007894861454249455013202734019215071856834943490096156048504952328784989777263664832098681831398770963056616417301705739505187754236801407014715780468333977293887519001724078504320344074325196167699818117367329779609
m = 9530454742891231590945778054072843874837824815724564463369259282490619049557772650832818763768769359762168560563265763313176741847581931364
k = 8139616873420730499092246564709331937498029453340099806219977060224838957080870950877930756958455278369862703151353509623205172658012437573652818022676431
def encrypt1(n):
n1 = hex(n>>200).encode()
n2 = str(hex(n))[20:].encode()
return n1,n2
def encrypt2(m , n_1):
c_1 = pow(m,e_1,n_1)
print('c_1 = '+str(c_1))
def encrypt3(m , n_2):
c_2 = pow( m , e_2 , n_2)
print('c_2 = '+str(c_2))
def encrypt4(m):
k = getPrime(512)
m = m % k
c_3 = pow(m, e_2, n_3)
print('c_3 = ' + str(c_3))
print('m = ' + str(m))
print('k = ' + str(k))
m1,m2 = encrypt1(flag)
m1 = bytes_to_long(m1)
m2 = bytes_to_long(m2)
print('n_2 = ' + str(n_2))
print('n_3 = ' + str(n_3))
print('e_1 = ' + str(e_1))
print('e_2 = ' + str(e_2))
encrypt2(m1,n_1)
encrypt3(n_1,n_2)
encrypt4(m2)
|
题目分析
该题的加密顺序是：
1、加密flag，分为两部分m1、m2
2、加密m1
3、加密m2
同理我们解密的顺序应该也是
1、解出m1、m2
2、解出flag
求m2
先观察一下encrypt4函数
虽然说e_2=3，按理来说使用低加密指数攻击，但并不可行。
又因为m = m % k
可通过这点和c_3 = pow(m, e_2, n_3)做遍历求出m
最后发现m即为m2，m2 < k
求m1
发现m1加密方式采用RSA，但是n_1未知
n_1又通过一次RSA加密，已知n_1对应的密文
利用低加密指数攻击解出n1
发现n1可分解为3个素数乘积
故phi可求，即求出m1
求flag
观察encryt1
m1是flag右移200位之后转为字节
m2是flag的20位之后转成字节
所以来说m2是没什么问题，主要找到flag的前20位，再把m2拼到后面即可。
由于m1是flag右移200位，因此flag的低位缺失，但高位还在，由于不知道flag总长度，抱着试一试的心态，猜测一下它的高位前20位没有缺失
我们将m1和m2转为字节发现
m1:b'0x666c61677b3230366538353964'
m2:b'383539643865383534633466363030636231323735376262663966357d'
发现m1和m2有重叠部分，即38353开始
可以证实m1前20位确实没有缺失
因此取m1前20位，加m2，即可解出flag
EXP
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
| import math
from typing import ByteString
import gmpy2
from Crypto.Util.number import *
n_2 = 675835056744450121024004008337170937331109883435712066354955474563267257037603081555653829598886559337325172694278764741403348512872239277008719548968016702852609803016353158454788807563316656327979897318887566108985783153878668451688372252234938716250621575338314779485058267785731636967957494369458211599823364746908763588582489400785865427060804408606617016267936273888743392372620816053927031794575978032607311497491069242347165424963308662091557862342478844612402720375931726316909635118113432836702120449010
e_2=3
c_1 = 47029848959680138397125259006172340325269302342762903311733700258745280761154948381409328053449580957972265859283407071931484707002138926840483316880087281153554181290481533
c_2 = 332431
def dec(c,e,n):
i=0
while(1):
m1=c+n*i
result,flag=gmpy2.iroot(m1,e)
if flag==True:
return result
i+=1
n_1=70406706457855863712635967741447303613971473150228480705119773604469794649140239446237334040048504811343327173817296308781190911727763110615393368497803655390445303946160971
p_1=2732337821
e_1 = 65537
t_1=2224243981
q_1=11585031296201346891716939633970482508158508580350404805965250133832632323150440185890235814142601827544669601048550999405490149435265122374459158586377571
phi_1=(p_1-1)*(q_1-1)*(t_1-1)
d_1=gmpy2.invert(e_1,phi_1)
m1=pow(c_1,d_1,n_1)
c=pow(m1,e_1,n_1)
n_3 = 91294511667572917673898699346231897684542006136956966126836916292947639514392684487940336406038086150289315439796780158189004157494824987037667065310517044311794725172075653186677331434123198117797575528982908532086038107428540586044471407073066169603930082133459486076777574046803264038780927350142555712567
c_3 = 11951299411967534922967467740790967733301092706094553308467975774492025797106594440070380723007894861454249455013202734019215071856834943490096156048504952328784989777263664832098681831398770963056616417301705739505187754236801407014715780468333977293887519001724078504320344074325196167699818117367329779609
m = 9530454742891231590945778054072843874837824815724564463369259282490619049557772650832818763768769359762168560563265763313176741847581931364
k = 8139616873420730499092246564709331937498029453340099806219977060224838957080870950877930756958455278369862703151353509623205172658012437573652818022676431
m2=long_to_bytes(m)
print(m2)
print(long_to_bytes(m1)[:20])
m=0x666c61677b32303665383539643865383534633466363030636231323735376262663966357d
print(long_to_bytes(m))
|