Digd0g's Blog

Nextprime

发表于 更新于 分类于 ，
本文字数： 1k 阅读时长 ≈ 4 分钟
       
-------------已经到底啦！-------------
 

关于nextprime经常卡壳的一些内容

题目

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
from Crypto.Util.number import *
from sympy import *
from hashlib import sha1
import random

flag = 'tel{***********}'
m = bytes_to_long(flag.encode())
p = getPrime(1024)
q = getPrime(160)
while (p - 1) % q == 0:
    q = getPrime(160)


def gen():
    for i in range(random.randint(1, q-1), q):
        if gcd(i, (p-1)*(q-1)) == 1:
            return i


h = random.randint(1, p-1)
g = pow(h, (p-1)//q, p)
x = gen()
k = random.randint(1, q)
H = bytes_to_long(sha1(flag.encode()).digest())
r = pow(g, k, p) % q
s = (H + x*r) * invert(k, q) % q
print(p, q, g, s, H, sep=',')

p0, q0 = getPrime(1024), getPrime(1024)
p1, q1 = nextprime(p0), nextprime(q0)
e = getPrime(16)
n0 = (p0 % p1)**(e//5637)
n = p0*q0*p1*q1
ck = pow(k, e, n)
c = pow(m, x, p*q)
print(n0, n, ck, c, sep=',')


p, q, g, s, H = 167152400052330636346320132474196399981485183855007441218521822021033172668890515419690619550715086376934078917395958246700175704904096450747792045288207000491822878094930223385021015320715846394946079117295937830038961592066441789729666270923990098523645201742761215223889009378932935603856789937248925872997,1199933100939355756218555953043416081113540194437,124365042194951196352380755345625808501635962842149249871280257067004505788030068052615281482740085362358429247858294122017292747188651374538061698354846361888732033022717751215447360266227599887533117408396674688028725784359277154137004907559691781204263914751107185156226855868178946011464397643974458411810,124068214599718272092552707811707030439004414247,136881193005467965920239886193201315444115257672
n0, n, ck, c = 376322076375252252933679912807784549789275049581905520066712144066558442533601240421688069277230135509041509220775221063263331055394442046091586940634447085038137179588203079703847476833338327933854239375747693121662894733855598031256589548756638552165117224773675749468790465239582497394319371534414478432713989794887327406405965158791557563672328777418791267825625403502453401011548799860432606046773420061067052617978235625435355866472956671872591702301958766068800625925843262531552334673608872171819458832703160620371160156802421034880202180536087124572902236496800728564938952539287681964844870438074423719328049737080277780789691676663815934241865444422199931616328017893032385701886012314722764701538547417475338369703472102230306432818930193022509576576463583260859229013889264162630696858522945308957633004772459646501926394088177925060947209801406170608742115937895013814430523501952959458541489274074765332843881825718634233314859276360904834205120320463132394072481016027544796645824411628042259718880489111976132193868220748037142556727540475230384795420854131925030598653570009177282876455901282409715247680073978495001946606770555023601062267632534677701379397531678109423946108114901909613476879833185687071386745068158256734988199239375893198879754294803228641978255114842683164590616231455772573899927251848722538851376709517740260387471379675860017067408834330073376211891419948553615172649160444250646417636510857996636611628993610663303556694932076729767435207568097843386676224203695885491688415538938182158665679382036721720094605704900484884348074938469722219942927892518873631489855785109222620232168743007817223243332298925985576021760437927611662717891342497483612725794532883964011053662803680354674515694464791378634783753975226070619896432791834990092463596399801624377104845587803150447162877093856321549242908110329605253485931890798950181187332710379263713061648356041703380653951422799213503357426110171348670057443969412582363615973722640244394478835621627461587166983565586708666463574987291452344265103610115304271622152338884435077161977659148573149906984498569440756159344121848992473433914550412261981268149070551490599814527715539086492468250758697035136634161092983803038352163697704405271148024273368056893848975238470451632780936282191474883370199083580689816144610657996850598080255473029024932038350801562288592557955346797691830583545225944352980105743770290895259029939421017098247771576087669673194197556922981954401,380348357285976594643429831047564412552681231441375019410900644866412744345551071273292881053802821293150358478519364233440796288733165409975832499378247442855845586549247667058810640701556403606095111091681192458303625872629189992162882522761444964329074176415653888452232843940978941825083159013593099334009999404829067492937726590157529346279033137646190062658771774498954826215509787468691240555654930961479581189562736798517089780193421175445748522857595496936220272962633105511255638334602384164573842191198969993798329452630369976858378138162298950393994186226521206342842893903615021584857279036864137566813952688061089724921454229155878053653422851199348902921271176680201391961149452533427775370653568130833795217198602036900822865440971664043918368222921660410938708510160718513187790593784394498564118070907909419081341066880889540009331069232195465542027225227203372514628024678147239957876045158125833645874965806323000438193502310602537955292275099174629956977424416541914072531687729468209591568637108702557067100923645958892638555528060942334606300485297176210180988278981071197916784257256514231989374167813144271961723279579992185197968601416679240052266221460207280921361301918901622071039011035413827180993458979,245763156033844640072245809787296441329706337844883873645415699074637459426480036431936163686940722693327152870708128645036533961441966721344463413201170714177337450769841695239747712838589091525264120845175096946441174145278339576578857557947663230006024170139378762596438966577963487294128626823739956083118470456181029381436617294541963749556363061233937238707158210451709565487300465808774365770725410790697056986804026387846786341479131491378232216109198274292910193595771916655203014799612875848024254365954465397199579596084752502333740623585437595156110126012032776550857901690778264168543698673456207910980421971015400549703885524499248095580280484030666038629267458286263841012438005685771249893475244021503342713699978543076051947318927800456207496663260629496651841412099602551872406799913061837947042556445814923735692429424847553559657067182081567875049422524339726367906801621377527717771166334011425706850190836302882278379161448922081290375361577169649055663623110713917049211822904877108411447299918653875335582832142692407269643915858385013964873020889207762534038357871530949856458144674788987525937682527655064884977194812103750013253537231383609926909891108697284455300375194911704898117854518551644208273783485,22569160702692844240326201559378281298786127476800228277559236934070318412272848566691625221803075721522848393618350359623336091086422563219623954834198929010797802268304168990754628185736502742792488426872615095138931613518347813358990285994691510830998932182211929661002609348260911495849145653088718656315854967618432655937215231475733750664589907497981

​ 这道题考察的地方分两点，RSA上的多因子和DSA的公式转换

​ 还好有大佬博客

​ 

1
s = (h + x*r) * invert(k, q) % q

​ 那么我们可以化为

1
x = ((s * k - h) * invert(r, q)) % q

​ 并且求r也需要用到

1
r = pow(g, k, p) % q

​ 最关键一步就是求k咯

​ 从下面RSA部分看

1
ck = pow(k, e, n)

​ 倒过来

1
k = pow(ck,dk,n)

​ 开始转换成求d方案了；继续

1
dk = inverse(e,phi1)
1
phi1 = (p0-1)*(p1-1)*(q0-1)*(q1-1)

​ 由此看来，兜兜转转总归就是要先求出n的四个因子的值，Nextprime则是关键函数

MY_wp

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
import gmpy2
from Crypto.Util.number import *
from alive_progress import alive_bar
import time

p = 167152400052330636346320132474196399981485183855007441218521822021033172668890515419690619550715086376934078917395958246700175704904096450747792045288207000491822878094930223385021015320715846394946079117295937830038961592066441789729666270923990098523645201742761215223889009378932935603856789937248925872997
q = 1199933100939355756218555953043416081113540194437
g = 124365042194951196352380755345625808501635962842149249871280257067004505788030068052615281482740085362358429247858294122017292747188651374538061698354846361888732033022717751215447360266227599887533117408396674688028725784359277154137004907559691781204263914751107185156226855868178946011464397643974458411810
h = 136881193005467965920239886193201315444115257672
s = 124068214599718272092552707811707030439004414247
c = 22569160702692844240326201559378281298786127476800228277559236934070318412272848566691625221803075721522848393618350359623336091086422563219623954834198929010797802268304168990754628185736502742792488426872615095138931613518347813358990285994691510830998932182211929661002609348260911495849145653088718656315854967618432655937215231475733750664589907497981

n0 = 376322076375252252933679912807784549789275049581905520066712144066558442533601240421688069277230135509041509220775221063263331055394442046091586940634447085038137179588203079703847476833338327933854239375747693121662894733855598031256589548756638552165117224773675749468790465239582497394319371534414478432713989794887327406405965158791557563672328777418791267825625403502453401011548799860432606046773420061067052617978235625435355866472956671872591702301958766068800625925843262531552334673608872171819458832703160620371160156802421034880202180536087124572902236496800728564938952539287681964844870438074423719328049737080277780789691676663815934241865444422199931616328017893032385701886012314722764701538547417475338369703472102230306432818930193022509576576463583260859229013889264162630696858522945308957633004772459646501926394088177925060947209801406170608742115937895013814430523501952959458541489274074765332843881825718634233314859276360904834205120320463132394072481016027544796645824411628042259718880489111976132193868220748037142556727540475230384795420854131925030598653570009177282876455901282409715247680073978495001946606770555023601062267632534677701379397531678109423946108114901909613476879833185687071386745068158256734988199239375893198879754294803228641978255114842683164590616231455772573899927251848722538851376709517740260387471379675860017067408834330073376211891419948553615172649160444250646417636510857996636611628993610663303556694932076729767435207568097843386676224203695885491688415538938182158665679382036721720094605704900484884348074938469722219942927892518873631489855785109222620232168743007817223243332298925985576021760437927611662717891342497483612725794532883964011053662803680354674515694464791378634783753975226070619896432791834990092463596399801624377104845587803150447162877093856321549242908110329605253485931890798950181187332710379263713061648356041703380653951422799213503357426110171348670057443969412582363615973722640244394478835621627461587166983565586708666463574987291452344265103610115304271622152338884435077161977659148573149906984498569440756159344121848992473433914550412261981268149070551490599814527715539086492468250758697035136634161092983803038352163697704405271148024273368056893848975238470451632780936282191474883370199083580689816144610657996850598080255473029024932038350801562288592557955346797691830583545225944352980105743770290895259029939421017098247771576087669673194197556922981954401
n = 380348357285976594643429831047564412552681231441375019410900644866412744345551071273292881053802821293150358478519364233440796288733165409975832499378247442855845586549247667058810640701556403606095111091681192458303625872629189992162882522761444964329074176415653888452232843940978941825083159013593099334009999404829067492937726590157529346279033137646190062658771774498954826215509787468691240555654930961479581189562736798517089780193421175445748522857595496936220272962633105511255638334602384164573842191198969993798329452630369976858378138162298950393994186226521206342842893903615021584857279036864137566813952688061089724921454229155878053653422851199348902921271176680201391961149452533427775370653568130833795217198602036900822865440971664043918368222921660410938708510160718513187790593784394498564118070907909419081341066880889540009331069232195465542027225227203372514628024678147239957876045158125833645874965806323000438193502310602537955292275099174629956977424416541914072531687729468209591568637108702557067100923645958892638555528060942334606300485297176210180988278981071197916784257256514231989374167813144271961723279579992185197968601416679240052266221460207280921361301918901622071039011035413827180993458979
ck = 245763156033844640072245809787296441329706337844883873645415699074637459426480036431936163686940722693327152870708128645036533961441966721344463413201170714177337450769841695239747712838589091525264120845175096946441174145278339576578857557947663230006024170139378762596438966577963487294128626823739956083118470456181029381436617294541963749556363061233937238707158210451709565487300465808774365770725410790697056986804026387846786341479131491378232216109198274292910193595771916655203014799612875848024254365954465397199579596084752502333740623585437595156110126012032776550857901690778264168543698673456207910980421971015400549703885524499248095580280484030666038629267458286263841012438005685771249893475244021503342713699978543076051947318927800456207496663260629496651841412099602551872406799913061837947042556445814923735692429424847553559657067182081567875049422524339726367906801621377527717771166334011425706850190836302882278379161448922081290375361577169649055663623110713917049211822904877108411447299918653875335582832142692407269643915858385013964873020889207762534038357871530949856458144674788987525937682527655064884977194812103750013253537231383609926909891108697284455300375194911704898117854518551644208273783485

p1 = 157378340690221345724884055256019929308665281370898794949340597440988439040828219883228487474401125930237704691599311010542905984129165788310900270604296055006733125244270781471315581595209670001588165982688467953060846544566078261352197628587972062504613553356437260636051140979438240736360653567470108559387
p0 = 157378340690221345724884055256019929308665281370898794949340597440988439040828219883228487474401125930237704691599311010542905984129165788310900270604296055006733125244270781471315581595209670001588165982688467953060846544566078261352197628587972062504613553356437260636051140979438240736360653567470108559093
p_f = p1*p0
#print(p_f)
q_f = n//p_f
#print(q_f)
q0 = 123921257099882577644215281182572578721836139110835485413386781183545854040413492898575322443770453842041056565305337785244723390062046014781722906687190642791874781439898407577737795682479670080906313063578033414378609833711131373926694270172677624459679474245241910511014228142804222498895050770956800311133
q1 = 123921257099882577644215281182572578721836139110835485413386781183545854040413492898575322443770453842041056565305337785244723390062046014781722906687190642791874781439898407577737795682479670080906313063578033414378609833711131373926694270172677624459679474245241910511014228142804222498895050770956800311193


phi1 = (p0-1)*(p1-1)*(q0-1)*(q1-1)
#print(phi1)
n2 = p * q
phi = (p-1) * (q-1)

with alive_bar(10000) as bar:
    for e in range (45100,99999):
        if isPrime(e):
                time.sleep(.1)
                bar()
                dk = int(inverse(e,phi1))
                #print(d0)
                k = pow(ck,dk,n)
                print(k.bit_length())
                r = pow(g, k, p) % q
                #s = (h + x*r) *inverse(k, q) % q
                x = (s * k -h)*inverse(r,q)%q
                #print(x.bit_length())
                d = inverse(x,phi)
                m = pow(c,d,n2)
                flag = long_to_bytes(m)
                if b'tel' in flag:
                    print(flag)
                    break

​ 起初我的想法是由于nextprime使p0和p1过于接近近似于一个值所以n=(p0*q0)**2

​ 开根

1
nn = gmpy2.iroot(n,2)[0] # p0*q0

得出来的结果和正确的phi其实高位蛮相近

1
2
3
4
phi_right:
380348357285976594643429831047564412552681231441375019410900644866412744345551071273292881053802821293150358478519364233440796288733165409975832499378247442855845586549247667058810640701556403606095111091681192458303625872629189992162882522761444964329074176415653888452232843940978941825083159013593099333999027301742123148162078596234505077634952155597973343407940700150575879866350618533720186045358173754512626450864959704429309558866909178064130380894114901658722940426410286967088565017327700675038697496215018219357033280630991153158745446419679093421117675327240987021940286329745996563689205429556067737693908123623555013577171400771575445779879336787731250741363935582919552589638290030073614468207386104751868436267843685487686298487134526572143835086811531535612331815832862467132498450675308341904835907900544058015448489971910485141017954565156712818442398767737384130586757964049426581846058602554797703951768706270308134133656912499349348957152687800878542955642991057494329547608187307339511442642020621713566848310603569392345914759348430723941503184149822068595502134883343783122657290960381952644430477203634469684149384915700316625469309156446890205283460784955038377864458645927174543545694510587393403198672128
phi_nn:
380348357285976594643429831047564412552681231441375019410900644866412744345551071273292881053802821293150358478519364233440796288733165409975832499378247442855845586549247667058810640701556403606095111091681192458303625872629189992162882522761444964329074176415653888452232843940978941825083159013593099334009999404829067492937726590157529346279033137646190062658771774498954826215509787468691240555654930961479581189562736798517089780193421175445748522857595496936220272962633105511255638334602384164573842191198969993798329452630369976858378138162298950393994186226521206342842893903615021584857279036864137566813896669483491864990797620032620055146672280852145764898196251429388597055172666948327990606680164175657275077234255627571814784285149943997664671287518969057885530750094862218307225720996992521694499537924811570797836839300207311261159249118844428401417294696120184282594489521577407713449087261773887705721550019264917349702934333513048998295843199977696062068171642374050053137884229356666458637145189445553459929037727507601502210499785262288073028996274150096456950804855741525446842141735456139910359658461908165852835113640496989387288113354611271548990269274988056194807687331721735746278419345974346859253174560

​ 跑了一千多还没出来想必是错的了，有能跑出来的友友记得教教我哦；

​ 更快的做法其实是用欧几里得，p0是n和n0的公因子

​ 但是往往我就是不善于记诵玉律金科，自己想出来了一个更为繁琐但是直观的过程。

​ 首先要抓住已给的已知量，比如这里的n0，且p1>p0，最关键的一点是n0可分解

1
n0 = (p0 % p1)**(e//5637)

​

​ 这就好办了，指数用来求e，底数用来求p0

​ 所以p0%p1=p0，也就是n0的底数

​ 得到p0就能求出p1

1
p1 = gmpy2.next_prime(p0)

​ 合二为一，用n除去合并后的大p得到大q的值，再继续细分

​ 这里需要用到费马定理了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from sympy.ntheory.primetest import is_square
from Crypto.Util.number import long_to_bytes,inverse
import sympy
def fermat(n):
    a = int(sympy.sqrt(n)) # Fermat's Algorithm
    b = (a*a) - n
    while not is_square(b):
        a += 1
        b = (a*a) - n
    else:
        p = int(a - (sympy.sqrt(b)))
        q = n//p
        if p * q == n:
            return p,q
        else:
            return "No Luck"

n=15356477961215198158119042162358375167486017226968962079202907802792862808172346619680067865314512375304555428282500684314814991683795581624495536179223754260963428917528860755711760424617503835694938561487246185858190282754148672734487949382545119525931728791777664266383763279964535906195732387398362229961430870577143229878819205222239515739928306220491551649842926847034962173804775725262346972889869770110535293977765464000006236123844336079373851588128042495564012735483845750715951310385709853195841334530005956230738097141716071864062207735561253392941217116928566268484266173543732901748832326461613622411669
p,q = fermat(n)
print(p)
print(q)

​ 得到q0和q1

​ 万事俱备，可以求出phi啦

​ 最终结果

​

官方wp

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
from Crypto.Util.number import *
from sympy import *


p, q, g, s, H = 167152400052330636346320132474196399981485183855007441218521822021033172668890515419690619550715086376934078917395958246700175704904096450747792045288207000491822878094930223385021015320715846394946079117295937830038961592066441789729666270923990098523645201742761215223889009378932935603856789937248925872997,1199933100939355756218555953043416081113540194437,124365042194951196352380755345625808501635962842149249871280257067004505788030068052615281482740085362358429247858294122017292747188651374538061698354846361888732033022717751215447360266227599887533117408396674688028725784359277154137004907559691781204263914751107185156226855868178946011464397643974458411810,124068214599718272092552707811707030439004414247,136881193005467965920239886193201315444115257672
n0, n, ck, c = 376322076375252252933679912807784549789275049581905520066712144066558442533601240421688069277230135509041509220775221063263331055394442046091586940634447085038137179588203079703847476833338327933854239375747693121662894733855598031256589548756638552165117224773675749468790465239582497394319371534414478432713989794887327406405965158791557563672328777418791267825625403502453401011548799860432606046773420061067052617978235625435355866472956671872591702301958766068800625925843262531552334673608872171819458832703160620371160156802421034880202180536087124572902236496800728564938952539287681964844870438074423719328049737080277780789691676663815934241865444422199931616328017893032385701886012314722764701538547417475338369703472102230306432818930193022509576576463583260859229013889264162630696858522945308957633004772459646501926394088177925060947209801406170608742115937895013814430523501952959458541489274074765332843881825718634233314859276360904834205120320463132394072481016027544796645824411628042259718880489111976132193868220748037142556727540475230384795420854131925030598653570009177282876455901282409715247680073978495001946606770555023601062267632534677701379397531678109423946108114901909613476879833185687071386745068158256734988199239375893198879754294803228641978255114842683164590616231455772573899927251848722538851376709517740260387471379675860017067408834330073376211891419948553615172649160444250646417636510857996636611628993610663303556694932076729767435207568097843386676224203695885491688415538938182158665679382036721720094605704900484884348074938469722219942927892518873631489855785109222620232168743007817223243332298925985576021760437927611662717891342497483612725794532883964011053662803680354674515694464791378634783753975226070619896432791834990092463596399801624377104845587803150447162877093856321549242908110329605253485931890798950181187332710379263713061648356041703380653951422799213503357426110171348670057443969412582363615973722640244394478835621627461587166983565586708666463574987291452344265103610115304271622152338884435077161977659148573149906984498569440756159344121848992473433914550412261981268149070551490599814527715539086492468250758697035136634161092983803038352163697704405271148024273368056893848975238470451632780936282191474883370199083580689816144610657996850598080255473029024932038350801562288592557955346797691830583545225944352980105743770290895259029939421017098247771576087669673194197556922981954401,380348357285976594643429831047564412552681231441375019410900644866412744345551071273292881053802821293150358478519364233440796288733165409975832499378247442855845586549247667058810640701556403606095111091681192458303625872629189992162882522761444964329074176415653888452232843940978941825083159013593099334009999404829067492937726590157529346279033137646190062658771774498954826215509787468691240555654930961479581189562736798517089780193421175445748522857595496936220272962633105511255638334602384164573842191198969993798329452630369976858378138162298950393994186226521206342842893903615021584857279036864137566813952688061089724921454229155878053653422851199348902921271176680201391961149452533427775370653568130833795217198602036900822865440971664043918368222921660410938708510160718513187790593784394498564118070907909419081341066880889540009331069232195465542027225227203372514628024678147239957876045158125833645874965806323000438193502310602537955292275099174629956977424416541914072531687729468209591568637108702557067100923645958892638555528060942334606300485297176210180988278981071197916784257256514231989374167813144271961723279579992185197968601416679240052266221460207280921361301918901622071039011035413827180993458979,245763156033844640072245809787296441329706337844883873645415699074637459426480036431936163686940722693327152870708128645036533961441966721344463413201170714177337450769841695239747712838589091525264120845175096946441174145278339576578857557947663230006024170139378762596438966577963487294128626823739956083118470456181029381436617294541963749556363061233937238707158210451709565487300465808774365770725410790697056986804026387846786341479131491378232216109198274292910193595771916655203014799612875848024254365954465397199579596084752502333740623585437595156110126012032776550857901690778264168543698673456207910980421971015400549703885524499248095580280484030666038629267458286263841012438005685771249893475244021503342713699978543076051947318927800456207496663260629496651841412099602551872406799913061837947042556445814923735692429424847553559657067182081567875049422524339726367906801621377527717771166334011425706850190836302882278379161448922081290375361577169649055663623110713917049211822904877108411447299918653875335582832142692407269643915858385013964873020889207762534038357871530949856458144674788987525937682527655064884977194812103750013253537231383609926909891108697284455300375194911704898117854518551644208273783485,22569160702692844240326201559378281298786127476800228277559236934070318412272848566691625221803075721522848393618350359623336091086422563219623954834198929010797802268304168990754628185736502742792488426872615095138931613518347813358990285994691510830998932182211929661002609348260911495849145653088718656315854967618432655937215231475733750664589907497981

p0 = gcd(n, n0)
p1 = nextprime(p0)

# yafu分解得t
t = 19502521818625831103968007017790446605294322614744621081419457053687749929799458950955113407754882127199864854428717277201468767003848422481002375100528454438916223222178557090916740358725773102717922659730448397065542731028760646510851294840260517042392082647044868154726616656447008742718948504415645177769618495143218910918729679379014433710988525136920612315926552247094304296582510296148133830229155036424023671950458003960564215194066084956872030359018935175147491539156959354086800409203536300879899563754878760008960931164958787378135419887888025316908429888526575247189920980290790466243551355288768007755471
if gcd(t, p0) == 1:
    q0 = t // p1
    #print(q0)
    q1 = nextprime(q0)
else:
    q1 = t // p0
    q0 = prevprime(q1)

phi = (p0-1)*(p1-1)*(q0-1)*(q1-1)
#print(phi)
e0 = log(n0, p0)*5637
#print(e0)
for e in range(e0, 99999):
    if isPrime(e):
            dk = int(invert(e, phi))
            #print(dk)
            k = pow(ck, dk, n)
            r = pow(g, k, p) % q
            x = (s * k - H) * invert(r, q) % q
            try:
                d = int(invert(x, (p - 1) * (q - 1)))
            except:
                print('Error')
            else:
                m = pow(c, d, p * q)
                flag = long_to_bytes(m)
                if b'tel' in flag:
                    print(flag)
                    break

小结

还有一处也是十分关键

1
if isPrime(e):

关于e的性质没有太深刻的印象，暴力枚举的时候需要规定是素数才可，不然程序会一个个枚举到宇宙大爆炸。