首页
社区
课程
招聘
[原创]Crypto-RSA大整数分解-LineCTF2021-babycrypto3
发表于: 2021-3-24 22:09 52061

[原创]Crypto-RSA大整数分解-LineCTF2021-babycrypto3

2021-3-24 22:09
52061

知道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-Miller
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))
# -*- 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-Miller
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})
 
 
 
# -*- 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

[培训]内核驱动高级班,冲击BAT一流互联网大厂工作,每周日13:00-18:00直播授课

最后于 2021-3-24 22:13 被fishmouse编辑 ,原因:
上传的附件:
收藏
免费 3
支持
分享
最新回复 (4)
雪    币: 6
活跃值: (113)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
2
512的可以分解出来吗?大概要多久
2021-3-27 09:05
0
雪    币: 1119
活跃值: (2030)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
3
shark凯 512的可以分解出来吗?大概要多久
分解出来了吗?
2021-8-10 15:39
0
雪    币: 3241
活跃值: (2074)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
4
很有收货,嗯,获,但是,逐渐高深,理解可以,做到掌握还得以后再多看。
2022-5-25 23:40
0
雪    币: 0
能力值: ( LV1,RANK:0 )
在线值:
发帖
回帖
粉丝
5
shark凯 512的可以分解出来吗?大概要多久
有大佬做过,大概35天出结果
2023-6-5 15:32
0
游客
登录 | 注册 方可回帖
返回
//