知道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题进行简单总结
假设我们从题目获得了公钥(N,e)和待解密的密文c,由RSA的加解密过程,我们知道,如果要解密密文,我们要得到e的逆元d,而d是要我们去求解的。
yafu工具分解 适用情况:p和q相差较大或相差较小时,可快速分解
GGNFS和MSIEVE分解
当n较大时,若用常用的工具无法分解,可利用在线网站:http://factordb.com
适用情况: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
下面内容摘自上面参考博客
当大整数N的两个因子p和q相近时,我们可以通过费马分解的办法很快分解大整数
官网:http://gilchrist.ca/jeff/factoring/nfs_beginners_guide_perl.html
以及翻译:https://bbs.pediy.com/thread-156206.htm
下面示例:如何使用通用数字字段筛(GNFS)和Brian Gladman的factmsieve.py python脚本同时使用ggnfs和msieve工具对以下100位整数进行因子分解:2881039827457895971881627053137530734638790825166127496066674320241571446494762386620429538
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-x64.exe后回车再输入factor(number)
用时285.2031秒
下载地址:https://sourceforge.net/projects/msieve/
下载完后将其内容复制添加至ggnfs文件夹中
参考链接: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 中下载这两个文件
使用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 = '../'
滑动底部得到,如图所示:
默认情况下,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工作目录运行:
如下图:
至此windows下已安装完成
下载msieve:https://github.com/MersenneForum/msieve 其中包含了gnfs我们就直接在该文件夹下,终端输入make all即可
我使用的是kail所以命令如下:
Plesase decrypt and get flag.
Flag is LINECTF{<decryped text>} and decrypted text is human-readable text.
如图
查看n的位数
说明可分,首先在http://factordb.com 查找,比赛时是查不出来的,目前已经有提交给这个网站,故现在是可查的
由于本机线程过小,跑的时间过长就直接粘贴网址查询的p和q
直接利用RSA加解密原理
可知flag为:LINECTF{CLOSING THE DISTANCE.}
[1]王兴波,唐春明,李建辉.公钥密码体制中大整数分解算法研究[J].现代信息科技,2020,4(16):125-133.
https://github.com/x-vespiary/writeup/blob/master/2021/03-line/crypto-babycrypto3.md
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
())))
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
())))
24
[
2
,
2
,
2
,
3
]
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
())))
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
())))
21
[
3
,
7
]
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))
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))
33
len
:
2
Counter({
3
:
1
,
11
:
1
})
33
len
:
2
Counter({
3
:
1
,
11
:
1
})
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!'
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
[培训]内核驱动高级班,冲击BAT一流互联网大厂工作,每周日13:00-18:00直播授课
最后于 2021-3-24 22:13
被fishmouse编辑
,原因:
上传的附件: