知道RSA算法的应该都知道公钥(n,e),如果能有效分解模数n,那么其私钥(d,p,q)我们就能获得,所以这时其就不具备安全性。但是当n为较大整数时,基于大整数分解困难,又能保证RSA是安全的。但是对大整数的分解一直被研究,相关算法有Pollard Rho算法、连分数算法(Continued fracion,CFRAC)、二次筛法(Quadratic Sieve,QS)、平方型分解法(SQUFOF)、椭圆曲线(ECM)和数域筛法(Number Field Sieve,NFS)等,有感兴趣的可以了解相关算法。根据参考文献【1】,目前有700多位(二进制)被分解,但耗时也是非常非常长的。
之前做LineCTF2021-babycrypto3题时,知道明显是RSA的大整数分解,使用了各种方式,未果,事后了解到GGNFS和MSIEVE 分解因数 本文就各种可能状况的分解进行简单介绍,并详细介绍一些工具的安装使用,以及针对带有pub.pem
的公钥文件的RSA题进行简单总结
RSA整数分解场景假设我们从题目获得了公钥(N,e)和待解密的密文c,由RSA的加解密过程,我们知道,如果要解密密文,我们要得到e的逆元d,而d是要我们去求解的。
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
def
factorization(n):
i
=
2
ret
=
[]
while
i
*
i <
=
n:
while
n
%
i
=
=
0
:
ret.append(i)
n
/
/
=
i
i
+
=
1
if
n >
1
:
ret.append(n)
return
ret
if
__name__
=
=
'__main__'
:
print
(factorization(
int
(
input
())))
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
pri
=
[]
MX
=
int
(
1e6
)
isprime
=
[
True
]
*
MX
def
init():
global
a, MX
for
i
in
range
(
2
, MX):
if
isprime[i]:
pri.append(i)
for
j
in
range
(i
+
i, MX, i):
isprime[j]
=
False
def
factorization(n):
global
pri
ret
=
[]
for
i
in
pri:
if
i
*
i > n:
break
while
n
%
i
=
=
0
:
ret.append(i)
n
/
/
=
i
ret.append(n)
return
ret
if
__name__
=
=
'__main__'
:
init()
print
(factorization(
int
(
input
())))
Miller-Rabin素性测试和离散对数Pollard_rho分解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
90
91
92
93
94
95
96
import
random
from
math
import
log, log10
from
collections
import
Counter
def
gcd(x, y):
return
x
if
y
=
=
0
else
gcd(y, x
%
y)
def
fpow(a, x, n):
ans
=
1
while
x >
0
:
if
x &
1
:
ans
=
ans
*
a
%
n
a
=
a
*
a
%
n
x >>
=
1
return
ans
TIMES
=
10
def
is_prime(n):
def
check(a, n, x, t):
ret
=
fpow(a, x, n)
last
=
ret
for
i
in
range
(
0
, t):
ret
=
ret
*
ret
%
n
if
ret
=
=
1
and
last !
=
1
and
last !
=
n
-
1
:
return
True
last
=
ret
if
ret !
=
1
:
return
True
return
False
if
not
isinstance
(n,
int
):
raise
TypeError(
str
(n)
+
' is not an integer!'
)
if
n <
=
0
:
raise
ValueError(
'%d <= 0'
%
n)
if
n
in
{
2
,
3
,
5
,
7
,
11
}:
return
True
for
i
in
{
2
,
3
,
5
,
7
,
11
}:
if
n
%
i
=
=
0
:
return
False
x
=
n
-
1
t
=
0
while
not
x &
1
:
x >>
=
1
t
+
=
1
for
i
in
range
(
0
, TIMES):
a
=
random.randint(
1
, n
-
2
)
if
check(a, n, x, t):
return
False
return
True
def
pollard_rho_2(n, c):
x
=
random.randint(
0
, n)
i, k, y
=
1
,
2
, x
while
True
:
i
+
=
1
x
=
(x
*
x)
%
n
+
c
d
=
gcd(y
-
x, n)
if
d !
=
1
and
d !
=
n:
return
d
if
y
=
=
x:
return
n
if
i
=
=
k:
y
=
x
k <<
=
1
def
pollard_rho_1(n):
if
not
isinstance
(n,
int
):
raise
TypeError(
str
(n)
+
' is not an integer!'
)
if
n
=
=
1
:
return
None
if
is_prime(n):
return
[n]
ans
=
[]
p
=
n
while
p >
=
n:
p
=
pollard_rho_2(p, random.randint(
1
, n
-
1
))
ans.extend(pollard_rho_1(p))
ans.extend(pollard_rho_1(n
/
/
p))
return
ans
def
factorization(n):
return
Counter(pollard_rho_1(n))
if
__name__
=
=
'__main__'
:
n
=
int
(
input
())
print
(
'len:'
,
len
(
str
(n)))
print
(factorization(n))
1
2
3
33
len
:
2
Counter({
3
:
1
,
11
:
1
})
n较大,在线查找当n较大时,若用常用的工具无法分解,可利用在线网站:http://factordb.com
Wiener's attack 适用情况适用情况:e过大或过小。 在e过大或过小的情况下,可使用算法从e中快速推断出d的值。详细的算法原理可以阅读:低解密指数攻击 https://www.tr0y.wang/2017/11/06/CTFRSA/index.html#%E4%BD%8E%E8%A7%A3%E5%AF%86%E6%8C%87%E6%95%B0%E6%94%BB%E5%87%BB
wiener's attack代码参考:https://github.com/pablocelayes/rsa-wiener-attack
下面内容摘自上面参考博客
简单介绍
代码
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
import
gmpy2
import
time
def
continuedFra(x, y):
cF
=
[]
while
y:
cF
+
=
[x
/
y]
x, y
=
y, x
%
y
return
cF
def
Simplify(ctnf):
numerator
=
0
denominator
=
1
for
x
in
ctnf[::
-
1
]:
numerator, denominator
=
denominator, x
*
denominator
+
numerator
return
(numerator, denominator)
def
calculateFrac(x, y):
cF
=
continuedFra(x, y)
cF
=
map
(Simplify, (cF[
0
:i]
for
i
in
xrange
(
1
,
len
(cF))))
return
cF
def
solve_pq(a, b, c):
par
=
gmpy2.isqrt(b
*
b
-
4
*
a
*
c)
return
(
-
b
+
par)
/
(
2
*
a), (
-
b
-
par)
/
(
2
*
a)
def
wienerAttack(e, n):
for
(d, k)
in
calculateFrac(e, n):
if
k
=
=
0
:
continue
if
(e
*
d
-
1
)
%
k !
=
0
:
continue
phi
=
(e
*
d
-
1
)
/
k
p, q
=
solve_pq(
1
, n
-
phi
+
1
, n)
if
p
*
q
=
=
n:
return
abs
(
int
(p)),
abs
(
int
(q))
print
'not find!'
time.clock()
n
=
0x92411fa0c93c1b27f89e436d8c4698bcf554938396803a5b62bd10c9bfcbf85a483bd87bb2d6a8dc00c32d8a7caf30d8899d90cb8f5838cae95f7ff5358847db1244006c140edfcc36adbdcaa16cd27432b4d50d2348b5c15c209364d7914ef50425e4c3da07612cc34e9b93b98d394b43f3eb0a5a806c70f06697b6189606eb9707104a7b6ff059011bac957e2aae9ec406a4ff8f8062400d2312a207a9e018f4b4e961c943dfc410a26828d2e88b24e4100162228a5bbf0824cf2f1c8e7b915efa385efeb505a9746e5d19967766618007ddf0d99525e9a41997217484d64c6a879d762098b9807bee46a219be76941b9ff31465463981e230eecec69691d1
e
=
0x6f6b385dd0f06043c20a7d8e5920802265e1baab9d692e7c20b69391cc5635dbcaae59726ec5882f168b3a292bd52c976533d3ad498b7f561c3dc01a76597e47cfe60614f247551b3dbe200e2196eaa001a1d183886eeacddfe82d80b38aea24de1a337177683ed802942827ce4d28e20efef92f38f1b1a18c66f9b45f5148cceabfd736de8ac4a49e63a8d35a83b664f9f3b00f822b6f11ff13257ee6e0c00ca5c98e661ea594a9e66f2bd56b33d9a13f5c997e67a37fcf9a0c7f04d119fe1ba261127357e64a4b069aefed3049c1c1fe4f964fd078b88bedd064abea385cfebd65e563f93c12d34eb6426e8aa321033cfd8fe8855b9e74d07fe4f9d70de46f
c
=
0x558b353e0bff6f006eddf2ee35bf7114a60f22228462e0b6289bc9d824fa4d5988b68d41960b16f89bd33b7a51d5de6ad9afe9e1e5fa778d7d44f3df5b4b482c00913fc2fb78a3fb4714b651e6fde2df8f2adffd7c4a6a344d112938c1818cae8439615ac9dbe5ebf6d0ee4a672664f4067389e38eedc900d3874424a29234b1bbd736468506427d81bfa4080c1f114a9165feec1b5b721bafcdf33b4ce5b84881192d7b84246c73aca1e570e1805a522b3f0693590fb14a49bbdbf856155b4f37f3432532b9e9fe615d1f90011319d13de9c224c6f709b497538f705f95374172f7ee423ef0db6b3969ac4aab780d630d2bed75f140a276fddfccd224ee024
print
(
'e'
,e,
'n'
,n)
p, q
=
wienerAttack(e, n)
print
'[+]Found!'
print
' [-]p ='
,p
print
' [-]q ='
,q
print
' [-]n ='
,p
*
q
d
=
gmpy2.invert(e,(p
-
1
)
*
(q
-
1
))
print
' [-]d ='
, d
print
' [-]m is:'
+
'{:x}'
.
format
(
pow
(c,d,n)).decode(
'hex'
)
print
'\n[!]Timer:'
,
round
(time.clock(),
2
),
's'
print
'[!]All Done!'
1
2
3
4
5
6
7
8
9
10
(
'e'
,
14065324093316017945695720258347429532521523200228598193322667338820770590989154977786981894794588594064536009186732255775035804405327706425255296803855527639374329558376563095664859692148197185703687276097309462020144376262777557533944519562049109221719648126706993033163993490190085491702629251352329396471456129542825658446009162968346786594848548139595669836329358788165100849817671092568134531593182392252696719165573226130084180843486935720502707239300540428534291779101061922644007823991998086019198292035392258539304441052201138357754863223836486846439513422901513872417295274198920142360883876210212927825007L
,
'n'
,
18462906143035540993814517057095163128283817787230664517838986634801013392767711846485937113330072380038567780269061919808605648774959966319179757205173372523095161810322702620470126948608656351385935375720727519176775110406692586449768317335765421930399299578230419560189633716571287406027463911286833332787737419540756653612611709926058384814812935770145166745335145087323852211057246522872067333040272572190577262813212787729743380140592301701193918348912668992966189995193003441075512789075254845693251194059243188025613215624222354768281910170062917473229700929505219308776883069798326608764552258161920559190481L
)
[
+
]Found!
[
-
]p
=
104235442847969552884769987994197297422543352176802940317177677000499807722195632069286150361214879780730339973882703487096199834739930880687593938040395436586345480730212942206420793142692112306639438014319225266407401819137390988067078857106773391577174349673013152862143650835518682246788303050611999452911
[
-
]q
=
177126950666523578738984064380839651168608739644946060823792396091708111322051866642111785827074573440159197219479475538437582278979185941268904558179007415168216637577906599474105547898107223364283435084419522228187779674837611069387527478313869377950991632158274789401880909076604812300066218450595389655871
[
-
]n
=
18462906143035540993814517057095163128283817787230664517838986634801013392767711846485937113330072380038567780269061919808605648774959966319179757205173372523095161810322702620470126948608656351385935375720727519176775110406692586449768317335765421930399299578230419560189633716571287406027463911286833332787737419540756653612611709926058384814812935770145166745335145087323852211057246522872067333040272572190577262813212787729743380140592301701193918348912668992966189995193003441075512789075254845693251194059243188025613215624222354768281910170062917473229700929505219308776883069798326608764552258161920559190481
[
-
]d
=
42043
[
-
]m
is
:flag{w13n3r_4tt4ck_d_1s_10w}
[!]Timer:
40.97
s
[!]
All
Done!
费马分解 适用情况当大整数N的两个因子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
from
isqrt
import
isqrt
def
fermat(n):
a
=
isqrt(n)
b2
=
a
*
a
-
n
b
=
isqrt(n)
count
=
0
while
b
*
b !
=
b2:
a
=
a
+
1
b2
=
a
*
a
-
n
b
=
isqrt(b2)
count
+
=
1
p
=
a
+
b
q
=
a
-
b
assert
n
=
=
p
*
q
return
p, q
if
__name__
=
=
'__main__'
:
import
libnum
N
=
966808932627497190635859236054960349099463975227350564265384373280336699853387254070662881265937565163000758606154308757944030571837175048514574473061401566330836334647176655282619268592560172726526643074499534129878217409046045533656897050117438496357231575999185527675071002803951800635220029015932007465117818739948903750200830856115668691007706836952244842719419452946259275251773298338162389930518838272704908887016474007051397194588396039111216708866214614779627566959335170676055025850932631053641576566165694121420546081043285806783239296799795655191121966377590175780618944910532816988143056757054052679968538901460893571204904394975714081055455240523895653305315517745729334114549756695334171142876080477105070409544777981602152762154610738540163796164295222810243309051503090866674634440359226192530724635477051576515179864461174911975667162597286769079380660782647952944808596310476973939156187472076952935728249061137481887589103973591082872988641958270285169650803792395556363304056290077801453980822097583574309682935697260204862756923865556397686696854239564541407185709940107806536773160263764483443859425726953142964148216209968437587044617613518058779287167853349364533716458676066734216877566181514607693882375533
e
=
65537
c
=
168502910088858295634315070244377409556567637139736308082186369003227771936407321783557795624279162162305200436446903976385948677897665466290852769877562167487142385308027341639816401055081820497002018908896202860342391029082581621987305533097386652183849657065952062433988387640990383623264405525144003500286531262674315900537001845043225363148359766771033899680111076181672797077410584747509581932045540801777738548872747597899965366950827505529432483779821158152928899947837196391555666165486441878183288008753561108995715961920472927844877569855940505148843530998878113722830427807926679324241141182238903567682042410145345551889442158895157875798990903715105782682083886461661307063583447696168828687126956147955886493383805513557604179029050981678755054945607866353195793654108403939242723861651919152369923904002966873994811826391080318146260416978499377182540684409790357257490816203138499369634490897553227763563553981246891677613446390134477832143175248992161641698011195968792105201847976082322786623390242470226740685822218140263182024226228692159380557661591633072091945077334191987860262448385123599459647228562137369178069072804498049463136233856337817385977990145571042231795332995523988174895432819872832170029690848
p,q
=
fermat(N)
print
(
"p:"
,p)
print
(
"q:"
,q)
phi_n
=
(p
-
1
)
*
(q
-
1
)
d
=
libnum.invmod(e,phi_n)
flag
=
libnum.n2s(
pow
(c,d,N))
print
(flag)
1
2
3
p:
31093551302922880999883020803665536616272147022877428745314830867519351013248914244880101094365815998050115415308439610066700139164376274980650005150267949853671653233491784289493988946869396093730966325659249796545878080119206283512342980854475734097108975670778836003822789405498941374798016753689377992355122774401780930185598458240894362246194248623911382284169677595864501475308194644140602272961699230282993020507668939980205079239221924230430230318076991507619960330144745307022538024878444458717587446601559546292026245318907293584609320115374632235270795633933755350928537598242214216674496409625928997877221
q:
31093551302922880999883020803665536616272147022877428745314830867519351013248914244880101094365815998050115415308439610066700139164376274980650005150267949853671653233491784289493988946869396093730966325659249796545878080119206283512342980854475734097108975670778836003822789405498941374798016753689377992355122774401780930185598458240894362246194248623911382284169677595864501475308194644140602272961699230282993020507668939980205079239221924230430230318076991507619960330144745307022538024878444458717587446601559546292026245318907293584609320115374632235270795633933755350928537598242214216674496409625928797450473
flag{d1fference_between_p_And_q_1s_t00_5mall}
GGNFS和MSIEVE分解 windows下安装官网:http://gilchrist.ca/jeff/factoring/nfs_beginners_guide_perl.html
以及翻译:https://bbs.pediy.com/thread-156206.htm
使用Number Field Sieve(NFS)算法分解大于90位的数字,我们可使用GGNFS和MSIEVE软件工具来完成此任务。
对于小于90位的数字,应将二次筛(QS)与MSIEVE或YAFU之类的程序一起使用。
为要分解的数字大小选择一个合理的分解算法很重要。例如,下面的100位整数使用ECM算法花费了将近80天的时间,而GNFS仅需几个小时。同样,少数数据应使用除GNFS之外的其他因素(例如ECM或QS)进行分解。
下面示例:如何使用通用数字字段筛(GNFS)和Brian Gladman的factmsieve.py python脚本同时使用ggnfs和msieve工具对以下100位整数进行因子分解:2881039827457895971881627053137530734638790825166127496066674320241571446494762386620429538
ECM在线和windows下yafu分解测试
ECM在线分解大整数:https://www.alpertron.com.ar/ECM.HTM
ECM和SIQS(二次筛法)结合
在线ECM测试结果:2 881039 827457 895971 881627 053137 530734 638790 825166 127496 066674 320241 571446 494762 386620 429538(91个数字)= 2×59×107×283×100469 ×25212824 127811 771907 702100 117027 070259(38个数字)×318305309 664993 (42位数字)
用时:12m 21.4s
yafu分解测试
输入.yafu-x64.exe后回车再输入factor(number)
用时285.2031秒
下载msieve下载地址:https://sourceforge.net/projects/msieve/
下载完后将其内容复制添加至ggnfs文件夹中
下载ggnfs
先下载:factmsieve.py
参考链接:http://brg.a2hosted.com/oldsite/computing/factmsieve.py
下载地址:https://sourceforge.net/projects/ggnfs/
因为我的电脑是windows自动检测下载的exe文件,然后下载即可
下载完成ggnfs文件夹内容如下图:下载后并没有def-nm-params.txt和def-par.txt这两个文件 可从网站:https://github.com/MersenneForum/ggnfs/tree/master/bin 中下载这两个文件
创建一个工作目录C:xxxxxx\ggnfs\example
修改factmsieve.py文件
使用notepad++修改factmsieve.py文件
Change lines 63-64 from: 注:Set binary directory paths GGNFS_PATH = 'C:/Users/brg\Documents/Visual Studio 2015/Projects/ggnfs/bin/x64/Release' MSIEVE_PATH = 'C:/Users/brg/Documents/Visual Studio 2015/Projects/msieve/bin/x64/Release'
to:
注:Set binary directory paths GGNFS_PATH = '../' MSIEVE_PATH = '../'
查看自己电脑的CPU核数,命令行输入 wmic ,再输入cpu get
1
2
C:\Users\xxx>wmic
wmic:root\cli>cpu get
滑动底部得到,如图所示:
1
2
3
4
修改
67
from
:
NUM_CPUS
=
4
to 若你的CPU为双核,可选
1
或
2
;若为四核,则可选
1
,
2
,
3
,
4
NUM_CPUS
=
4
默认情况下,factmsieve.py将使用msieve进行多项式选择。普通用户应该保留这个设置。如果出于某些原因,你想使用pol51多项式选择工具更做下面更改
change lines 89-90 from: USE_KLEINJUNG_FRANKE_PS = False USE_MSIEVE_POLY = True to: USE_KLEINJUNG_FRANKE_PS = True USE_MSIEVE_POLY = False
GPU
如果您使用的是启用了 GPU 的 msieve 版本,并且希望使用 GPU 启用多项式选择,请修改第 70 行,确保它写着。 USE_CUDA = True 如果您没有使用GPU,请确保它写着: USE_CUDA = False
在第104行,如果你使用的不是'msieve',请确保你的msieve可执行文件被正确命名。我的是msieve153故这里改为msieve153 MSIEVE = 'msieve153'
由于我的本机运行出错,故将CUDA设置False
进入下一步
多项式选择NFS算法采用了3个阶段的方法,首先是多项式选择,然后是筛分,最后是线性代数 。 在分解开始之前,必须先选择一个多项式。 factmsieve.py脚本将运行适当的工具为你选择一个。
windows下在上面创建的example文件夹中,创建example.n文件,该文件内容为: n:2881039827457895971881627053137530734638790825166127496066674320241571446494762386620442953820735453
windows在example工作目录运行:
1
C:xxxx\ggnfs\example> python ..\factmsieve.py example
如下图:
至此windows下已安装完成
Linux下安装下载msieve:https://github.com/MersenneForum/msieve 其中包含了gnfs我们就直接在该文件夹下,终端输入make all即可
我使用的是kail所以命令如下:
题目-LineCTF2021-babycrypto3Plesase decrypt and get flag.
Flag is LINECTF{<decryped text>} and decrypted text is human-readable text.
附件:ciphertext.txt和pub.pem
题解 分析密文
1
2
3
with
open
(
'ciphertext.txt'
,
'rb'
) as f:
hex_c
=
f.read()
print
(hex_c)
1
b
'\x01\x14\x1fUxa\xaa\xb3C\x9b\xe1\xeb\x87\xa0\x12`\x156e\x8a\x05\xf4\xf3x\xf7\xb9\xda\xe5J\x08Cn\\C]V\xdd\x1bH\x96\xb74\xae\xcd\x83\x88A\xd5\x92&'
1
2
3
from
Crypto.Util.number
import
long_to_bytes, bytes_to_long
cipher
=
bytes_to_long(hex_c)
cipher
1
10879776433900426660843740332190892429769159527203392037251077478777616065501519198653853699716123394455804888854401574
解析公钥文件 方式1:OpenSSL软件1
命令:rsa
-
pubin
-
in
pub.pem
-
text
-
modulus
如图
方式2:Python库RSA
1
2
3
4
5
6
from
Crypto.PublicKey
import
RSA
with
open
(
'pub.pem'
,
'r'
) as f:
pubkey
=
f.read()
key
=
RSA.importKey(pubkey)
e,n
=
key.e,key.n
e,n
1
2
(
65537
,
31864103015143373750025799158312253992115354944560440908105912458749205531455987590931871433911971516176954193675507337
)
分解n查看n的位数
说明可分,首先在http://factordb.com 查找,比赛时是查不出来的,目前已经有提交给这个网站,故现在是可查的
由于本机线程过小,跑的时间过长就直接粘贴网址查询的p和q
1
2
p
=
291664785919250248097148750343149685985101
q
=
109249057662947381148470526527596255527988598887891132224092529799478353198637
解密
直接利用RSA加解密原理
1
2
3
4
import
libnum
d
=
libnum.invmod(e,(p
-
1
)
*
(q
-
1
))
m
=
pow
(cipher,d,n)
long_to_bytes(m)
1
b
'\x02`g\xff\x85\x1e\xcd\xcba\xe5\x0b\x83\xa5\x15\xe3\x00Q0xPU0lORyBUSEUgRElTVEFOQ0UuCg==\n'
1
2
import
base64
print
(base64.b64decode(
'Q0xPU0lORyBUSEUgRElTVEFOQ0UuCg=='
.encode()))
1
b
'CLOSING THE DISTANCE.\n'
可知flag为:LINECTF{CLOSING THE DISTANCE.}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from
Crypto.PublicKey
import
RSA
from
Crypto.Util.number
import
long_to_bytes,bytes_to_long
import
base64
import
libnum
with
open
(
'ciphertext.txt'
,
'rb'
) as f:
cipher
=
bytes_to_long(f.read())
with
open
(
'pub.pem'
,
'r'
) as fp:
key
=
RSA.importKey(fp.read())
n,e
=
key.n,key.e
print
(n,e)
p
=
291664785919250248097148750343149685985101
q
=
109249057662947381148470526527596255527988598887891132224092529799478353198637
d
=
libnum.invmod(e,(p
-
1
)
*
(q
-
1
))
m
=
pow
(cipher,d,n)
print
(long_to_bytes(m))
1
2
31864103015143373750025799158312253992115354944560440908105912458749205531455987590931871433911971516176954193675507337
65537
b
'\x02`g\xff\x85\x1e\xcd\xcba\xe5\x0b\x83\xa5\x15\xe3\x00Q0xPU0lORyBUSEUgRElTVEFOQ0UuCg==\n'
参考文献
[1]王兴波,唐春明,李建辉.公钥密码体制中大整数分解算法研究[J].现代信息科技,2020,4(16):125-133.
https://github.com/x-vespiary/writeup/blob/master/2021/03-line/crypto-babycrypto3.md
http://gilchrist.ca/jeff/factoring/nfs_beginners_guide.html
【看雪培训】《Adroid高级研修班》2022年夏季班招生中!
最后于 2021-3-24 22:13
被fishmouse编辑
,原因:
上传的附件: