之前做LineCTF2021-babycrypto3题时，知道明显是RSA的大整数分解，使用了各种方式，未果，事后了解到GGNFS和MSIEVE分解因数
本文就各种可能状况的分解进行简单介绍，并详细介绍一些工具的安装使用，以及针对带有pub.pem的公钥文件的RSA题进行简单总结

Table of Contents

知道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较小，直接分解

  • 若n较大，在线分解：http://factordb.com

  • yafu工具分解
    适用情况：p和q相差较大或相差较小时，可快速分解

  • GGNFS和MSIEVE分解

  • 可使用RsaCtfTool

  • 一般题目中，若是可分解，使用yafu或者msieve即可分解。若是有迹可寻，也即特殊情况下，可使用相关脚本解

n较小，直接分解几种算法

短除法

  • 短除法1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# -*- 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]
  • 短除法2
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
# -*- 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]

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

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

下面内容摘自上面参考博客

简单介绍

代码

  • python2代码
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
# -*- 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!'
('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)

    # 根据p,q求phi_n也即N的欧拉函数值
    phi_n=(p-1)*(q-1)
    # 求d
    d= libnum.invmod(e,phi_n)
    
    # 用d解密
    flag=libnum.n2s(pow(c,d,N))
    print(flag)
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测试结果：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

  • 再下载ggnfs

下载地址：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
C:\Users\xxx>wmic
wmic:root\cli>cpu get

滑动底部得到，如图所示：

修改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工作目录运行：

C:xxxx\ggnfs\example> python ..\factmsieve.py example

如下图：

至此windows下已安装完成

Linux下安装

下载msieve：https://github.com/MersenneForum/msieve
其中包含了gnfs我们就直接在该文件夹下,终端输入make all即可

我使用的是kail所以命令如下：

root@kali:~/myctf/msieve# make all

CADO-NFS安装

CADO-NFS是C / C ++中数字字段筛选（NFS）算法的完整实现，用于分解整数并计算有限字段中的离散对数。它包含与算法所有阶段相对应的各种程序，以及可能在计算机网络上并行运行它们的通用脚本

下载镜像

下载mitchelldehaven/cado-nfs镜像，大约1个G

docker pull mitchelldehaven/cado-nfs

  • 运行容器，打开交互界面，进入/bin/bash目录，然后再进入/cado-nfs-2.3.0目录

    docker run -it mitchelldehaven/cado-nfs /bin/bash

  • 这个镜像预先是没有make的，所以需要make，等一会即可

简单测试：分解

90377629292003121684002147101760858109247336549001090677693

1
./cado-nfs.py 90377629292003121684002147101760858109247336549001090677693

260938498861057 588120598053661 760926063870977 773951836515617

题目-LineCTF2021-babycrypto3

Plesase decrypt and get flag.

Flag is LINECTF{} and
decrypted text is human-readable text.

  • 附件：ciphertext.txt和pub.pem

题解

分析密文

  • ciphertext.txt文件内容
1
2
3
with open('ciphertext.txt','rb') as f:
    hex_c=f.read()
print(hex_c)
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
10879776433900426660843740332190892429769159527203392037251077478777616065501519198653853699716123394455804888854401574

解析公钥文件

方式1：OpenSSL软件

命令：rsa -pubin -in pub.pem -text -modulus

如图

方式2：Python库RSA

  • 获取公钥（e,n）
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
(65537,
 31864103015143373750025799158312253992115354944560440908105912458749205531455987590931871433911971516176954193675507337)

分解n

查看n的位数

1
len(bin(n))-2# bit
394

说明可分，首先在http://factordb.com 查找，比赛时是查不出来的，目前已经有提交给这个网站，故现在是可查的

由于本机线程过小，跑的时间过长就直接粘贴网址查询的p和q

1
2
p = 291664785919250248097148750343149685985101
q = 109249057662947381148470526527596255527988598887891132224092529799478353198637

解密

  • 由上文已知，n,e,p,q

直接利用RSA加解密原理

1
2
3
4
import libnum
d= libnum.invmod(e,(p-1)*(q-1))
m=pow(cipher,d,n)
long_to_bytes(m)
b'\x02`g\xff\x85\x1e\xcd\xcba\xe5\x0b\x83\xa5\x15\xe3\x00Q0xPU0lORyBUSEUgRElTVEFOQ0UuCg==\n'
  • 观察到有base64编码
1
2
import base64
print(base64.b64decode('Q0xPU0lORyBUSEUgRElTVEFOQ0UuCg=='.encode()))
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
d= libnum.invmod(e,(p-1)*(q-1))
m =pow(cipher,d,n)
print(long_to_bytes(m))
31864103015143373750025799158312253992115354944560440908105912458749205531455987590931871433911971516176954193675507337 65537
b'\x02`g\xff\x85\x1e\xcd\xcba\xe5\x0b\x83\xa5\x15\xe3\x00Q0xPU0lORyBUSEUgRElTVEFOQ0UuCg==\n'

参考文献


博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://fishni.github.io/2021/03/24/Crypto-04-RSA%E5%A4%A7%E6%95%B4%E6%95%B0%E5%88%86%E8%A7%A3-LineCTF2021-babycrypto3/