-
-
[原创]Crypto-RSA大整数分解-LineCTF2021-babycrypto3
-
发表于: 2021-3-24 22:09
-
知道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
# -*- coding: utf-8 -*-"""短除法-1从i为2开始枚举，一直枚举到，一旦n % i == 0成立，则i为n的因子，然后进行n //= i使运行速度加快并使i为质数才可能有n % i == 0。复杂度：0（n^1/2）适用范围：n: 2-10^16"""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())))
# -*- coding: utf-8 -*-"""短除法-1从i为2开始枚举，一直枚举到，一旦n % i == 0成立，则i为n的因子，然后进行n //= i使运行速度加快并使i为质数才可能有n % i == 0。复杂度：0（n^1/2）适用范围：n: 2-10^16"""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]
24[2, 2, 2, 3]
# -*- coding: utf-8 -*-"""短除法2我们可以打表出2到n^1/2之间的质数再进行试除，这样在解决多个数的质因数分解时才会免除大部分合数的影响。用素数筛进行打表复杂度为O(n)，我们也只需要从2到n^1/2打表到即可。复杂度：0（n^1/2）适用范围：n 2-10^12"""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())))
# -*- coding: utf-8 -*-"""短除法2我们可以打表出2到n^1/2之间的质数再进行试除，这样在解决多个数的质因数分解时才会免除大部分合数的影响。用素数筛进行打表复杂度为O(n)，我们也只需要从2到n^1/2打表到即可。复杂度：0（n^1/2）适用范围：n 2-10^12"""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]
21[3, 7]
# -*- coding: utf-8 -*-"""用Miller-Rabin素性测试和离散对数Pollard_rho算法进行大数因数分解：复杂度：0(n^1/4)适用范围：n 2-10^33"""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
# there change the times of Rabin-MillerTIMES = 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))
# -*- coding: utf-8 -*-"""用Miller-Rabin素性测试和离散对数Pollard_rho算法进行大数因数分解：复杂度：0(n^1/4)适用范围：n 2-10^33"""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
# there change the times of Rabin-MillerTIMES = 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))
33len: 2
Counter({3: 1, 11: 1})
33len: 2
Counter({3: 1, 11: 1})
# -*- coding: utf-8 -*-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!'
# -*- coding: utf-8 -*-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
[招生]科锐逆向工程师培训(2024年11月15日实地，远程教学同时开班, 第51期)
