知道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较大时,若用常用的工具无法分解,可利用在线网站:f7cK9s2c8@1M7q4)9K6b7g2)9J5c8W2)9J5c8X3k6S2j5%4c8G2M7X3c8T1i4K6u0W2j5$3!0E0
适用情况:e过大或过小。 在e过大或过小的情况下,可使用算法从e中快速推断出d的值。详细的算法原理可以阅读:低解密指数攻击047K9s2c8@1M7s2y4Q4x3@1q4Q4x3V1k6Q4x3V1k6%4N6%4N6Q4x3X3g2@1M7U0m8&6i4K6u0W2N6$3q4F1k6#2)9J5c8U0t1H3x3e0N6Q4x3V1j5I4x3g2)9J5c8U0l9$3i4K6u0r3b7#2c8r3f1W2y4m8i4K6u0r3K9h3&6V1k6i4S2Q4x3X3g2Z5N6r3#2D9i4K6t1K6i4K6t1#2c8e0c8Q4x3U0g2n7c8q4)9J5y4e0S2q4i4K6t1#2c8e0S2Q4x3U0g2m8y4#2)9J5y4f1p5K6i4K6t1#2c8e0g2Q4x3U0g2m8c8W2)9J5y4e0R3$3i4K6t1#2c8e0k6Q4x3U0f1^5b7#2)9J5y4e0R3%4i4K6t1#2c8e0k6Q4x3U0f1&6y4g2)9J5y4f1t1H3i4K6t1#2c8e0k6Q4x3U0f1&6y4q4)9J5y4f1u0n7i4K6t1#2c8e0g2Q4x3U0f1^5y4#2)9J5y4f1u0n7
wiener's attack代码参考:34fK9s2c8@1M7s2y4Q4x3@1q4Q4x3V1k6Q4x3V1k6Y4K9i4c8Z5N6h3u0Q4x3X3g2U0L8$3#2Q4x3V1k6H3j5h3u0D9L8$3y4W2L8r3q4&6k6i4y4Q4x3V1k6J5M7$3q4Q4x3X3c8%4K9h3g2F1k6i4u0Q4x3X3c8S2N6s2c8S2j5$3D9`.
下面内容摘自上面参考博客
当大整数N的两个因子p和q相近时,我们可以通过费马分解的办法很快分解大整数
官网:860K9s2c8@1M7q4)9K6b7g2)9J5c8W2)9J5c8X3N6A6L8r3y4Z5M7X3W2K6N6q4)9J5k6h3y4S2i4K6u0r3K9X3g2X3k6W2)9J5c8X3k6S2j5%4c8G2M7X3W2F1k6#2)9J5c8X3&6X3M7#2)9#2k6X3u0W2k6$3W2F1L8X3g2J5M7#2)9#2k6X3N6#2K9h3c8W2i4K6g2X3M7r3g2J5L8q4)9J5k6h3S2@1L8h3H3`.
以及翻译: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秒
下载地址:2ebK9s2c8@1M7s2y4Q4x3@1q4Q4x3V1k6Q4x3V1k6K6L8%4g2J5j5$3g2X3L8%4u0Y4k6g2)9J5k6h3&6W2N6q4)9J5c8Y4m8J5L8$3A6W2j5%4c8K6i4K6u0r3L8i4y4A6k6i4k6W2i4K6u0r3
下载完后将其内容复制添加至ggnfs文件夹中
参考链接:396K9s2c8@1M7q4)9K6b7g2)9J5c8W2)9J5c8X3u0J5k6#2)9J5k6h3p5J5K9r3!0K6N6r3g2V1i4K6u0W2j5$3!0E0i4K6u0r3L8$3I4V1M7$3W2@1k6g2)9J5c8X3y4G2L8i4m8#2N6r3W2F1k6#2)9J5c8X3k6S2j5%4c8E0M7$3W2W2N6X3g2Q4x3X3g2H3P5b7`.`.
下载地址:1e2K9s2c8@1M7s2y4Q4x3@1q4Q4x3V1k6Q4x3V1k6K6L8%4g2J5j5$3g2X3L8%4u0Y4k6g2)9J5k6h3&6W2N6q4)9J5c8Y4m8J5L8$3A6W2j5%4c8K6i4K6u0r3k6$3N6F1k6Y4y4Q4x3V1j5`.
因为我的电脑是windows自动检测下载的exe文件,然后下载即可
下载完成ggnfs文件夹内容如下图:下载后并没有def-nm-params.txt和def-par.txt这两个文件 可从网站:44dK9s2c8@1M7s2y4Q4x3@1q4Q4x3V1k6Q4x3V1k6Y4K9i4c8Z5N6h3u0Q4x3X3g2U0L8$3#2Q4x3V1k6y4k6i4u0K6k6h3&6F1k6f1k6G2M7Y4g2E0i4K6u0r3k6$3N6F1k6Y4y4Q4x3V1k6@1M7X3g2W2i4K6u0r3L8h3q4K6N6r3g2J5i4K6u0r3j5X3W2F1 中下载这两个文件
使用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:b8dK9s2c8@1M7s2y4Q4x3@1q4Q4x3V1k6Q4x3V1k6Y4K9i4c8Z5N6h3u0Q4x3X3g2U0L8$3#2Q4x3V1k6y4k6i4u0K6k6h3&6F1k6f1k6G2M7Y4g2E0i4K6u0r3L8i4y4A6k6i4k6W2 其中包含了gnfs我们就直接在该文件夹下,终端输入make all即可
我使用的是kail所以命令如下:
Plesase decrypt and get flag.
Flag is LINECTF{<decryped text>} and decrypted text is human-readable text.
如图
查看n的位数
说明可分,首先在cf5K9s2c8@1M7q4)9K6b7g2)9J5c8W2)9J5c8X3k6S2j5%4c8G2M7X3c8T1i4K6u0W2j5$3!0E0 查找,比赛时是查不出来的,目前已经有提交给这个网站,故现在是可查的
由于本机线程过小,跑的时间过长就直接粘贴网址查询的p和q
直接利用RSA加解密原理
可知flag为:LINECTF{CLOSING THE DISTANCE.}
[1]王兴波,唐春明,李建辉.公钥密码体制中大整数分解算法研究[J].现代信息科技,2020,4(16):125-133.
60cK9s2c8@1M7s2y4Q4x3@1q4Q4x3V1k6Q4x3V1k6Y4K9i4c8Z5N6h3u0Q4x3X3g2U0L8$3#2Q4x3V1k6^5i4K6u0V1N6X3g2K6M7r3W2S2M7Y4W2Q4x3V1k6%4M7X3W2@1k6i4g2H3i4K6u0r3j5X3I4G2j5W2)9J5c8X3#2S2M7%4c8W2M7W2)9J5c8U0t1H3x3U0q4Q4x3V1j5H3x3#2)9J5k6r3I4A6L8X3g2Q4x3V1k6U0M7Y4W2H3N6r3!0Q4x3X3c8T1j5h3u0&6j5%4u0&6M7s2c8G2x3#2)9J5k6h3#2V1
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
[培训]科锐逆向工程师培训第53期2025年7月8日开班!
最后于 2021-3-24 22:13
被fishmouse编辑
,原因:
上传的附件: