关于RSA素数生成漏洞的CTF题

|
| 字数统计: 1.7k

Google CTF – CHUNK NORRIS

题目

image-20200824003337195

下载附件后是两个文件

image-20200824003505866

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
#!/usr/bin/python3 -u

import random
from Crypto.Util.number import *
import gmpy2

a = 0xe64a5f84e2762be5
chunk_size = 64

def gen_prime(bits):
    s = random.getrandbits(chunk_size)
    
    while True:
    	s |= 0xc000000000000001
    	p = 0
    	for _ in range(bits // chunk_size):
      		p = (p << chunk_size) + s
      		s = a * s % 2**chunk_size
    	if gmpy2.is_prime(p):
      		return p

n = gen_prime(1024) * gen_prime(1024)
e = 65537
flag = open("flag.txt", "rb").read()
print('n =', hex(n))
print('e =', hex(e))
print('c =', hex(pow(bytes_to_long(flag), e, n)))
1
2
3
n = 0xab802dca026b18251449baece42ba2162bf1f8f5dda60da5f8baef3e5dd49d155c1701a21c2bd5dfee142fd3a240f429878c8d4402f5c4c7f4bc630c74a4d263db3674669a18c9a7f5018c2f32cb4732acf448c95de86fcd6f312287cebff378125f12458932722ca2f1a891f319ec672da65ea03d0e74e7b601a04435598e2994423362ec605ef5968456970cb367f6b6e55f9d713d82f89aca0b633e7643ddb0ec263dc29f0946cfc28ccbf8e65c2da1b67b18a3fbc8cee3305a25841dfa31990f9aab219c85a2149e51dff2ab7e0989a50d988ca9ccdce34892eb27686fa985f96061620e6902e42bdd00d2768b14a9eb39b3feee51e80273d3d4255f6b19
e = 0x10001
c = 0x6a12d56e26e460f456102c83c68b5cf355b2e57d5b176b32658d07619ce8e542d927bbea12fb8f90d7a1922fe68077af0f3794bfd26e7d560031c7c9238198685ad9ef1ac1966da39936b33c7bb00bdb13bec27b23f87028e99fdea0fbee4df721fd487d491e9d3087e986a79106f9d6f5431522270200c5d545d19df446dee6baa3051be6332ad7e4e6f44260b1594ec8a588c0450bcc8f23abb0121bcabf7551fd0ec11cd61c55ea89ae5d9bcc91f46b39d84f808562a42bb87a8854373b234e71fe6688021672c271c22aad0887304f7dd2b5f77136271a571591c48f438e6f1c08ed65d0088da562e0d8ae2dadd1234e72a40141429f5746d2d41452d916

Writeup

通过分析线性同余方法生成的随机质数，找到分解n的方法:

首先研究pq的生成，可知

\begin{align} B &= 2 ^ {64}\\ p &= s_1 << 960 + (s_1 * a \% B) << 896 + (s_1 * a^2 \% B) << 832 + ... + (s_1 * a^{14} \% B) << 64 + (s_1 * a^{15} \% B)\\ &= s_1 << 960 + k_1 << 64 + (s_1 * a^{15} \% B)\\ q &= s_2 << 960 + (s_2 * a \% B) << 896 + (s_2 * a^2 \% B) << 832 + ... + (s_2 * a^{14} \% B) << 64 + (s_2 * a^{15} \% B)\\ &= s_2 << 960 + k_2 << 64 + (s_2 * a^{15} \% B)\\ pq &= p * q\\ &= (s_1 << 960 + k_1 << 64 + (s_1 * a^{15} \% B))*(s_2 << 960 + k_2 << 64 + (s_2 * a^{15} \% B))\\ &= s_1s_2 << 1920 + s_1k_2 << 64 + (s_2 * a^{15} \% B)s_1 << 960 + k_1s_2 << 1024 + k_1k_2 << 128 \\ &+ (s_2 * a^{15} \% B)k_1 << 64 + (s_1 * a^{15} \% B)s_2 << 960 + (s_1 * a^{15} \% B)k_2 << 64 + (s_1 * a^{15} \% B)(s_2 * a^{15} \% B)\\ \end{align}

去掉不重叠的位数部分

可知 s1s2s_1s_2等于pq的高64位或者其减一（由于进位），s1s2∗a30%Bs_1s_2*a^{30}\%B等于低64位

因此可计算出s1s2s_1s_2的值，分别考虑进位和不进位，可计算出两个值

得到s1s2s_1s_2的两个乘积，接下来用yafu分别进行质因数分解

已知s |= 0xc000000000000001可知s & 0xc000000000000001 != 0，由于分解后的质因数太多，产生的因数也太多，无法马上确定哪个因数和s匹配，我们利用质因数集生成其所有子集，再借用上式条件和p为质数的条件找到正确的s1和s2

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
97
98
99
100
#!/usr/bin/python3 -u

import random
from Crypto.Util.number import *
import gmpy2
from gmpy2 import *

n = 0xab802dca026b18251449baece42ba2162bf1f8f5dda60da5f8baef3e5dd49d155c1701a21c2bd5dfee142fd3a240f429878c8d4402f5c4c7f4bc630c74a4d263db3674669a18c9a7f5018c2f32cb4732acf448c95de86fcd6f312287cebff378125f12458932722ca2f1a891f319ec672da65ea03d0e74e7b601a04435598e2994423362ec605ef5968456970cb367f6b6e55f9d713d82f89aca0b633e7643ddb0ec263dc29f0946cfc28ccbf8e65c2da1b67b18a3fbc8cee3305a25841dfa31990f9aab219c85a2149e51dff2ab7e0989a50d988ca9ccdce34892eb27686fa985f96061620e6902e42bdd00d2768b14a9eb39b3feee51e80273d3d4255f6b19
e = 0x10001
c = 0x6a12d56e26e460f456102c83c68b5cf355b2e57d5b176b32658d07619ce8e542d927bbea12fb8f90d7a1922fe68077af0f3794bfd26e7d560031c7c9238198685ad9ef1ac1966da39936b33c7bb00bdb13bec27b23f87028e99fdea0fbee4df721fd487d491e9d3087e986a79106f9d6f5431522270200c5d545d19df446dee6baa3051be6332ad7e4e6f44260b1594ec8a588c0450bcc8f23abb0121bcabf7551fd0ec11cd61c55ea89ae5d9bcc91f46b39d84f808562a42bb87a8854373b234e71fe6688021672c271c22aad0887304f7dd2b5f77136271a571591c48f438e6f1c08ed65d0088da562e0d8ae2dadd1234e72a40141429f5746d2d41452d916

a = 0xe64a5f84e2762be5
chunk_size = 64
bits = 1024

n1 = mpz(int('0b'+bin(n)[2:66],2))
n2_star = mpz(int('0b'+(bin(n)[-64:]),2))

n2 = n2_star*invert(pow(a,15+15),2**64)%(2**64)

s12_1 = (n1<<64)+n2
s12_2 = (n1<<64)+n2-(1<<64)

k = 0xc000000000000001 # s的下限
j = 0xffffffffffffffff # s的上限

print(s12_1)
print(s12_2)

# yafu-x64.exe  factor(227963529990382503519930590718284598961)

factors1 = [11, 61, 443 ,21751 , 1933727 , 53523187 , 340661278587863]
factors2 = [3, 5 , 41 , 43 , 509 , 787 , 31601 , 258737 , 28110221 , 93627982031]


def subsets(nums):
    # 计算子集
    res = [[]]
    for num in nums: 
        res += [ i + [num] for i in res]
    return res

def mul(nums):
    # 计算list中所有元素的积
    if len(nums)==0:
        return 0
    else:
        s = 1
        for i in nums:
            s *= i
        return s

def judge(s):
    # 判断s是不是正确的
    p = 0
    for _ in range(bits // chunk_size):
      	p = (p << chunk_size) + s
      	s = a * s % 2**chunk_size
    if gmpy2.is_prime(p):
        return p
    else:
        return 0

def solve_pq(nums,s12):
    nums_set=subsets(nums)
    for nums in nums_set:
        s=mul(nums)
        if s>=k and s<=j and (s12//s)>=k and (s12//s)<=j:
            if (s&0xc000000000000001)!=0 and ((s12//s)&0xc000000000000001)!=0:
                p = judge(s)
                if p!=0:
                    print('factors: ',nums)
                    print('p =',p)
                    print('q =',n//p)
                    

solve_pq(factors1,s12_1)
solve_pq(factors2,s12_2)

#factors:  [3, 41, 43, 31601, 93627982031]
p = 152502124356100186048786584829816790951655306938554698381698516601140428798527485382577251685142660191666259802101357483152615284884054484645840626070726530443669580292854859145584666559430830034877567195195160870921467137859654581026067555226827127667674180022694309303154807908193178891551927991884659577259
q = 141964956842752227248825926479699850723242530500694299313985420916497490762457584872482228917124059114703818621232802014903763726586933292312009226271853350101621181936884771804789258383198041375410984842224059398802858374416574235073826923494095170442408144974244355981836859001182779710177024561285836339787
'''
因此s12=(n1<<64)+n2-(1<<64)
'''
assert(p*q==n)

c = 0x6a12d56e26e460f456102c83c68b5cf355b2e57d5b176b32658d07619ce8e542d927bbea12fb8f90d7a1922fe68077af0f3794bfd26e7d560031c7c9238198685ad9ef1ac1966da39936b33c7bb00bdb13bec27b23f87028e99fdea0fbee4df721fd487d491e9d3087e986a79106f9d6f5431522270200c5d545d19df446dee6baa3051be6332ad7e4e6f44260b1594ec8a588c0450bcc8f23abb0121bcabf7551fd0ec11cd61c55ea89ae5d9bcc91f46b39d84f808562a42bb87a8854373b234e71fe6688021672c271c22aad0887304f7dd2b5f77136271a571591c48f438e6f1c08ed65d0088da562e0d8ae2dadd1234e72a40141429f5746d2d41452d916

def decryto(p, q, e, c):
    d = gmpy2.invert(e,(p-1)*(q-1))
    flag = pow(c,d,n)
    flag = long_to_bytes(flag)
    return flag

print(decryto(p, q, e, c))

'''
CTF{__donald_knuths_lcg_would_be_better_well_i_dont_think_s0__}
'''

另一道类似赛题

百越杯赛题 - math

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from libnum import *
from Crypto.Util.number import *
from gmpy2 import next_prime
from flags import Flags
flag = s2n(flag)
a = getRandomRange(pow(10,499),pow(10,500))
b = getRandomRange(pow(10,499),pow(10,500))
p = a*pow(10,500)+b
q = b*pow(10,500)+a
print p*q
e = 65537
c = getRandomInteger(100)
p = next_prime(p+c)
q = next_prime(q+c)
n = p*q
print n
flag = pow(flag,e,n)
print flag

以上代码的输出如下:

1
2
3
4
5
37290153165969298170747767487987767106604956327590459309623310884436645867385405226836923826439760402232182199047042298740970941114757402758035338227352981884345194304183079410512904720516197002459598643659802383718137698974557870280366585586392385470235597777672593360788744398375690898546971801388821194234775373952698134335885991694714949974679482564600815766377388895037809222168800554222619940240853717965637149897765149770956991503459995786889995461520332980787566967767243445754450380553166156028030513979079301998632175402072502016282327825403961392784400687386536170117841528456263456021394359662685873080287765689757030352392386374307257266677811647633925457228036341541693812765785784057781251815707260401922647083928541835257244409503393940374048782722357915189148582407507806733352268172024029303953342827905707727300151171157623562387977156106983516547443642151573456682745626175061369310982040554116369983687552560719792717887667637107087090897681039368534492698712183905213300675019880169669159964289135274268951386122314246699412166656323475268623240778461031327966634628420986855022944785421496251349486099392411145566566437986155875600117002222032846697544656901210849382567936904958595228620017066673190455548617917273881089052468844830306632804733848750820391807100094948772492402636422551350516389981409116121666282434777976293668265700614707939438561465158100805697922866599682141928964956895065357677209698826476508887966210560085802544989199042295263908880764987497015388183619829914488242002252489035055312547747792033076017959711401664024465093007341377103124755426567781873434171576297409356302054965976819782564966567852321032108507478998871390301458143582617644492262165902951270805160376459476885522275531457938661136508391452032625051782015102833218959697470722331233350397631435041061401412630047713991858871735035714326218833998760244965866341087147750123869855038366992182962371334384526411144813368418246803652025254206189223834187719880012103660703380187226220860

37290153165969298170747767487987767106604956327590459309623310884436645867385405226836923826439760402232182199047042298740970941114757402758035338227352981884345194304183079410512904720516197002459598643659802383718137698974557870280366585586392385470235597777672593360788744398375690898546971801388821194234775373952698134335885991694714949974679482564600815766377388895037809222168800554222619940240853717965637149897765149770956991503459995786889995461520332980787566967767243445754450380553166156028030513979079301998632175402072502016282327825403961392784400687386536170117841528456263456021394359662685873080287765689757030352392386374307257266677811647633925457228036341541693812765785784057781251815707260401922647083928541835257244409503393940374048782722357915189148582407507806733352268172024029303953342827905707727300151171157623562387977156106983516547443642151573456682745626175061369310982040554116369983687552560719792717887667637107087090897681039368537631451824008445150593322916621649220131918968381060182780056625981084043051299820111816407714077085179863978735943069017108793879580065214612325438873475463670028900700692331942940752758392673078381358679392924527642317471983718497708036815480999969876652686414859011578133113730930542513696962965675847727315009182439824295556392013537952480748938928408290671107333656277905126915134701713932190005567660746756601077906025437341247344713253422720837604831207936303137369977025954243957891577406266667226864293421045998499026349073973676803568161225217742238807019077558158505566968246373749202724739826733649675118977232613022754175080279658222551375134841038576853604493545070340911086664690452703289923302725433846272032435289554345937247024060157309603467510583043117535674355137280615256893616267247008324272285381171004240649782585733382066689782757882726882857063752626302302445421988032917071576855484653938018800413715950664940531918933498765096986757431159488734247146715664409455285656746712809269599736842704425915921

37184996108096167233025618263505757153157343097156888579791591678112798126919291822117280574121886798076450090988956975942694991748710209332101082905159257360206646364269758967180975253962825625943696420172327932961625085719678913462057142665457670366149034781204452807008455874986258694889544297820868505385801547530471600056912582928858038944066247597538813265625994454536879142936629149425871030836276097612443965190900147217177268273320302968487288289500066066413057425060274495415705347775452378126322700828792271046010263910271491830733016822853700053524052302275780619672110356657862368196424416287062999248715568046365255257809392739368556770263662626707604374137827085932252100188620626033333675559976574305831148764403296339508944436482748296238651395448197460974036742794395872850277918173344274773788864080695651830624419146757315446431269176300228703998177892985982388577831521216077129479998846266657008240203501406588349129137285647942569321607846013589344817050392650458477423460119297842938591617558953789224928692831245011187614395138305116091095517452781922364575105441246935183151829079785593965595659385764661764536534314109799011221376335166825363745468702289956019189691732841787948543771767552418889945812912952844388135828118570454948482278617042826378637743128777368607901501702388930246381982139634661483616105908175895785968677045741141086145187314146524800384426347813569795767829229399693985449649456073846347751123890326703399205472967773736717062282465272801543616851680865089979007872017576434756441977097817456958807489726277542047228572876003573562220328683701400744899648300227399574965938796721337143228465728576794734241148236493866791812420360737798058399689694043617192496134725512211166304050577572889549976404923415229865890151512800020112421854251196729060158218415862519607464231622361159436715876677889457900668694738243191441657050304632774189736769141333132873006921328644347784442609254582911864794147017850676177776316795316841373510481580805823659839

Writeup

\begin{align} p & = a \cdot 10^{500} + b \\ q & = b \cdot 10^{500} + a \\ p \cdot q & = (a \cdot 10^{500} + b) \cdot (b \cdot 10^{500} + a) \\ & = ab \cdot 10^{1000} + (a^2+b^2) \cdot 10^{500} +ab\\ & \end{align}

因为a和b的位数都是500位，由此可知

ab⋅101000ab \cdot 10^{1000}的有效位数范围为1001~2000

a2⋅10500a^2 \cdot 10^{500}和b2⋅10500b^2 \cdot 10^{500}的有效位数范围是501~1500

abab的有效位数范围1~500

由此可知

abab的前500位等于p⋅qp \cdot q的前500位或其减一

abab的后500位等于p⋅qp \cdot q的后500位

(a2+b2)(a^2+b^2)的前500位+abab的后500位等于p⋅qp \cdot q的中间1001~1500位或其加上10100010^{1000}

(a2+b2)(a^2+b^2)的后500位+abab的前500位等于p⋅qp \cdot q的中间501~1000位

根据上述发现可计算出a、b的值,其中利用(a+b)2(a+b)^2的值是否为完全平方数判断ab的正确性

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
from libnum import *
import gmpy2
from Crypto.Util.number import *
from gmpy2 import next_prime
import math
#37290153165969298170747767487987767106604956327590459309623310884436645867385405226836923826439760402232182199047042298740970941114757402758035338227352981884345194304183079410512904720516197002459598643659802383718137698974557870280366585586392385470235597777672593360788744398375690898546971801388821194234775373952698134335885991694714949974679482564600815766377388895037809222168800554222619940240853717965637149897765149770956991503459995786889995461520332980787566967767243445754450380553166156028030513979079301998632175402072502016282327825403961392784400687386536170117841528456263456021394359662685873080287765689757030352392386374307257266677811647633925457228036341541693812765785784057781251815707260401922647083928541835257244409503393940374048782722357915189148582407507806733352268172024029303953342827905707727300151171157623562387977156106983516547443642151573456682745626175061369310982040554116369983687552560719792717887667637107087090897681039368534492698712183905213300675019880169669159964289135274268951386122314246699412166656323475268623240778461031327966634628420986855022944785421496251349486099392411145566566437986155875600117002222032846697544656901210849382567936904958595228620017066673190455548617917273881089052468844830306632804733848750820391807100094948772492402636422551350516389981409116121666282434777976293668265700614707939438561465158100805697922866599682141928964956895065357677209698826476508887966210560085802544989199042295263908880764987497015388183619829914488242002252489035055312547747792033076017959711401664024465093007341377103124755426567781873434171576297409356302054965976819782564966567852321032108507478998871390301458143582617644492262165902951270805160376459476885522275531457938661136508391452032625051782015102833218959697470722331233350397631435041061401412630047713991858871735035714326218833998760244965866341087147750123869855038366992182962371334384526411144813368418246803652025254206189223834187719880012103660703380187226220860
#37290153165969298170747767487987767106604956327590459309623310884436645867385405226836923826439760402232182199047042298740970941114757402758035338227352981884345194304183079410512904720516197002459598643659802383718137698974557870280366585586392385470235597777672593360788744398375690898546971801388821194234775373952698134335885991694714949974679482564600815766377388895037809222168800554222619940240853717965637149897765149770956991503459995786889995461520332980787566967767243445754450380553166156028030513979079301998632175402072502016282327825403961392784400687386536170117841528456263456021394359662685873080287765689757030352392386374307257266677811647633925457228036341541693812765785784057781251815707260401922647083928541835257244409503393940374048782722357915189148582407507806733352268172024029303953342827905707727300151171157623562387977156106983516547443642151573456682745626175061369310982040554116369983687552560719792717887667637107087090897681039368537631451824008445150593322916621649220131918968381060182780056625981084043051299820111816407714077085179863978735943069017108793879580065214612325438873475463670028900700692331942940752758392673078381358679392924527642317471983718497708036815480999969876652686414859011578133113730930542513696962965675847727315009182439824295556392013537952480748938928408290671107333656277905126915134701713932190005567660746756601077906025437341247344713253422720837604831207936303137369977025954243957891577406266667226864293421045998499026349073973676803568161225217742238807019077558158505566968246373749202724739826733649675118977232613022754175080279658222551375134841038576853604493545070340911086664690452703289923302725433846272032435289554345937247024060157309603467510583043117535674355137280615256893616267247008324272285381171004240649782585733382066689782757882726882857063752626302302445421988032917071576855484653938018800413715950664940531918933498765096986757431159488734247146715664409455285656746712809269599736842704425915921
#37184996108096167233025618263505757153157343097156888579791591678112798126919291822117280574121886798076450090988956975942694991748710209332101082905159257360206646364269758967180975253962825625943696420172327932961625085719678913462057142665457670366149034781204452807008455874986258694889544297820868505385801547530471600056912582928858038944066247597538813265625994454536879142936629149425871030836276097612443965190900147217177268273320302968487288289500066066413057425060274495415705347775452378126322700828792271046010263910271491830733016822853700053524052302275780619672110356657862368196424416287062999248715568046365255257809392739368556770263662626707604374137827085932252100188620626033333675559976574305831148764403296339508944436482748296238651395448197460974036742794395872850277918173344274773788864080695651830624419146757315446431269176300228703998177892985982388577831521216077129479998846266657008240203501406588349129137285647942569321607846013589344817050392650458477423460119297842938591617558953789224928692831245011187614395138305116091095517452781922364575105441246935183151829079785593965595659385764661764536534314109799011221376335166825363745468702289956019189691732841787948543771767552418889945812912952844388135828118570454948482278617042826378637743128777368607901501702388930246381982139634661483616105908175895785968677045741141086145187314146524800384426347813569795767829229399693985449649456073846347751123890326703399205472967773736717062282465272801543616851680865089979007872017576434756441977097817456958807489726277542047228572876003573562220328683701400744899648300227399574965938796721337143228465728576794734241148236493866791812420360737798058399689694043617192496134725512211166304050577572889549976404923415229865890151512800020112421854251196729060158218415862519607464231622361159436715876677889457900668694738243191441657050304632774189736769141333132873006921328644347784442609254582911864794147017850676177776316795316841373510481580805823659839
pq = gmpy2.mpz(37290153165969298170747767487987767106604956327590459309623310884436645867385405226836923826439760402232182199047042298740970941114757402758035338227352981884345194304183079410512904720516197002459598643659802383718137698974557870280366585586392385470235597777672593360788744398375690898546971801388821194234775373952698134335885991694714949974679482564600815766377388895037809222168800554222619940240853717965637149897765149770956991503459995786889995461520332980787566967767243445754450380553166156028030513979079301998632175402072502016282327825403961392784400687386536170117841528456263456021394359662685873080287765689757030352392386374307257266677811647633925457228036341541693812765785784057781251815707260401922647083928541835257244409503393940374048782722357915189148582407507806733352268172024029303953342827905707727300151171157623562387977156106983516547443642151573456682745626175061369310982040554116369983687552560719792717887667637107087090897681039368534492698712183905213300675019880169669159964289135274268951386122314246699412166656323475268623240778461031327966634628420986855022944785421496251349486099392411145566566437986155875600117002222032846697544656901210849382567936904958595228620017066673190455548617917273881089052468844830306632804733848750820391807100094948772492402636422551350516389981409116121666282434777976293668265700614707939438561465158100805697922866599682141928964956895065357677209698826476508887966210560085802544989199042295263908880764987497015388183619829914488242002252489035055312547747792033076017959711401664024465093007341377103124755426567781873434171576297409356302054965976819782564966567852321032108507478998871390301458143582617644492262165902951270805160376459476885522275531457938661136508391452032625051782015102833218959697470722331233350397631435041061401412630047713991858871735035714326218833998760244965866341087147750123869855038366992182962371334384526411144813368418246803652025254206189223834187719880012103660703380187226220860)
#不存在进位
ab_1 = int(str(pq)[:500]+str(pq)[-500:]) 
#存在进位
ab_2 = ab_1 - 10**500 
#不存在进位
a2Tb2_1 = int(str(pq)[500:1500])-int(str(ab_1)[500:1000]+str(ab_1)[0:500])
#存在进位
a2Tb2_2 = int(str(pq)[500:1500])-int(str(ab_2)[500:1000]+str(ab_2)[0:500])+10**1000
#存在进位
aTb2_1 = a2Tb2_1+2*ab_1
#不存在进位
aTb2_2 = a2Tb2_2+2*ab_2
if gmpy2.iroot(aTb2_1,2)[1]==True:
    print('不存在进位')
if gmpy2.iroot(aTb2_2,2)[1]==True:
    print('存在进位')

输出如下：

存在进位

因此存在进位

利用开方求得(a+b)(a+b)的值，又已知abab，再利用一元二次方程的求根公式求出a和b的值

1
2
3
4
5
6
7
8
9
10
ab = ab_2
aTb2 = aTb2_2
aTb = gmpy2.iroot(aTb2,2)[0]
delta = gmpy2.iroot(aTb**2-4*ab,2)[0]
print('delta =',delta)
a = gmpy2.mpz(aTb+delta)//2
b = gmpy2.mpz(aTb-delta)//2
p = a*pow(10,500)+b
q = b*pow(10,500)+a
print(p*q==pq)

输出如下：

1
2
delta = 28970382423653526230782087428394120199094608888807510969672174008572263444342743452382065495452410979665183590859836472860381842418270886250846330507167646674351905885014449434182842316793842355041032703945358809543746947830533653096857965009150717206961368552309542092906822247898706652989394172510971441082397663739139074168863166474942514453940979697271097233244125249898829123427276166705668136075753341362350636336479869531538499746880132398933374584887892784910782260556527383469248578187483469
    True

由于

1
2
3
p = next_prime(p+c)
q = next_prime(q+c)
n = p*q

假设

\begin{align} p' & = p+c+x \\ q' & = q+c+y \\ \end{align}

则有

\begin{align} n & = p' \cdot q' \\ & = (p+c+x) \cdot (q+c+y)\\ & = c^2+(p+x+q+y)c+(p+x)(q+y)\\ \Delta & = (p+x+q+y)^2-4(p+x)(q+y)+4n \\ \end{align}

显然x、y并不大，可进行爆破，终止条件为Δ\Delta是一个完全平方数

1
2
3
4
5
6
7
8
9
10
11
12
n=37290153165969298170747767487987767106604956327590459309623310884436645867385405226836923826439760402232182199047042298740970941114757402758035338227352981884345194304183079410512904720516197002459598643659802383718137698974557870280366585586392385470235597777672593360788744398375690898546971801388821194234775373952698134335885991694714949974679482564600815766377388895037809222168800554222619940240853717965637149897765149770956991503459995786889995461520332980787566967767243445754450380553166156028030513979079301998632175402072502016282327825403961392784400687386536170117841528456263456021394359662685873080287765689757030352392386374307257266677811647633925457228036341541693812765785784057781251815707260401922647083928541835257244409503393940374048782722357915189148582407507806733352268172024029303953342827905707727300151171157623562387977156106983516547443642151573456682745626175061369310982040554116369983687552560719792717887667637107087090897681039368537631451824008445150593322916621649220131918968381060182780056625981084043051299820111816407714077085179863978735943069017108793879580065214612325438873475463670028900700692331942940752758392673078381358679392924527642317471983718497708036815480999969876652686414859011578133113730930542513696962965675847727315009182439824295556392013537952480748938928408290671107333656277905126915134701713932190005567660746756601077906025437341247344713253422720837604831207936303137369977025954243957891577406266667226864293421045998499026349073973676803568161225217742238807019077558158505566968246373749202724739826733649675118977232613022754175080279658222551375134841038576853604493545070340911086664690452703289923302725433846272032435289554345937247024060157309603467510583043117535674355137280615256893616267247008324272285381171004240649782585733382066689782757882726882857063752626302302445421988032917071576855484653938018800413715950664940531918933498765096986757431159488734247146715664409455285656746712809269599736842704425915921

for x in range(1,10000):
    stop=0
    for y in range(1,10000):
        delta=gmpy2.mpz((p+q+x+y)**2-4*(p+x)*(q+y)+4*n)
        if gmpy2.iroot(delta,2)[1]==True:
            print('x, y = %d, %d'%(x,y))
            stop=1
            break
    if stop:
        break

输出如下

1
x, y = 1, 1836

用求根公式算出c的值，进而算出p和q的值

1
2
3
4
5
6
7
8
x, y = 1, 1836
delta =gmpy2.mpz((p+q+x+y)**2-4*(p+x)*(q+y)+4*n)
c = gmpy2.iroot(delta,2)[0]
c = gmpy2.mpz(-p-q-x-y+c)//2
print('c = ',c)
p = p+c+x
q = q+c+y
print(p * q == n)

输出如下：

1
2
c =  250059412706552500264745576027
True

最后利用RSA解密算法解密

1
2
3
4
5
6
7
8
9
10
e = 65537
c = gmpy2.mpz(37184996108096167233025618263505757153157343097156888579791591678112798126919291822117280574121886798076450090988956975942694991748710209332101082905159257360206646364269758967180975253962825625943696420172327932961625085719678913462057142665457670366149034781204452807008455874986258694889544297820868505385801547530471600056912582928858038944066247597538813265625994454536879142936629149425871030836276097612443965190900147217177268273320302968487288289500066066413057425060274495415705347775452378126322700828792271046010263910271491830733016822853700053524052302275780619672110356657862368196424416287062999248715568046365255257809392739368556770263662626707604374137827085932252100188620626033333675559976574305831148764403296339508944436482748296238651395448197460974036742794395872850277918173344274773788864080695651830624419146757315446431269176300228703998177892985982388577831521216077129479998846266657008240203501406588349129137285647942569321607846013589344817050392650458477423460119297842938591617558953789224928692831245011187614395138305116091095517452781922364575105441246935183151829079785593965595659385764661764536534314109799011221376335166825363745468702289956019189691732841787948543771767552418889945812912952844388135828118570454948482278617042826378637743128777368607901501702388930246381982139634661483616105908175895785968677045741141086145187314146524800384426347813569795767829229399693985449649456073846347751123890326703399205472967773736717062282465272801543616851680865089979007872017576434756441977097817456958807489726277542047228572876003573562220328683701400744899648300227399574965938796721337143228465728576794734241148236493866791812420360737798058399689694043617192496134725512211166304050577572889549976404923415229865890151512800020112421854251196729060158218415862519607464231622361159436715876677889457900668694738243191441657050304632774189736769141333132873006921328644347784442609254582911864794147017850676177776316795316841373510481580805823659839)

def decrypto(p, q, e, c):
    d = gmpy2.invert(e,(p-1)*(q-1))
    flag = pow(c,d,n)
    flag = long_to_bytes(flag)
    return flag

print(decrypto(p, q, e, c))
b'flag{ddc4205ecd6c22035acae589113bb8aa}'

得到flag{ddc4205ecd6c22035acae589113bb8aa}