crypto-RSA-常用解密代码块

已知n、e、c，基础解先分解n，在线分解：http://www.factordb.com/index.phpimport gmpy2from Crypto.Util.number import long_to_bytese = 547223n = 1708394123021348970042663648448773828242647149460709884729533533963817758368

无名函数

3940人浏览 · 2021-09-09 17:45:30

无名函数 · 2021-09-09 17:45:30 发布

已知n、e、c，基础解

先分解n，在线分解：http://www.factordb.com/index.php

import gmpy2
from Crypto.Util.number import long_to_bytes 

e = 547223
n = 17083941230213489700426636484487738282426471494607098847295335339638177583685457921198569105417734668692072727759139358207667248703952436680183153327606147421932365889983347282046439156176685765143620637107347870401946946501620531665573668068349080410807996582297505889946205052879002028936125315312256470583622913646319779125559691270916064588684997382451412747432722966919513413709987353038375477178385125453567111965259721484997156799355617642131569095810304077131053588483057244340742751804935494087687363416921314041547093118565767609667033859583125275322077617576783247853718516166743858265291135353895239981121
c = 3738960639194737957667684143565005503596276451617922474669745529299929395507971435311181578387223323429323286927370576955078618335757508161263585164126047545413028829873269342924092339298957635079736446851837414357757312525158356579607212496060244403765822636515347192211817658170822313646743520831977673861869637519843133863288550058359429455052676323196728280408508614527953057214779165450356577820378810467527006377296194102671360302059901897977339728292345132827184227155061326328585640019916328847372295754472832318258636054663091475801235050657401857262960415898483713074139212596685365780269667500271108538319
p = 106021448991021391444550749375115277080844281746248845802565680557785009341952320484175568763707424932172033597514861602114171459176440279045761846695231788376075050452154924141266290931413542110639081792550648106240966552406813059396358355737185354885474455248579946190266152416149137616855791805617206153497
q = 161136651053130509602530659420755324119806487925813087617466818245407407797561810253722204813002837916779909309520498985459703212021249251124954613236122142746302911323565396331355397916764254680629384957057354297855676493062493901977415968666512459829211010720514167083018352796496733697235524845188512914793

phi = (q-1) * (p-1)
d = gmpy2.invert(e,phi)
m = gmpy2.powmod(c,d,n)

print(m)
print(long_to_bytes(m))

已知n、e、c，但n不能分解

m = sympy.nthroot_mod(c,e,n)

已知n、e、c，但e与phi不互素

分为两种情况：
1：gcd(e,phi) = t
主要思路：

d = inverse(e//t,phi)
m = pow(m,d,n)
m = gmpy2.iroot(m,t)[0]

例如

import gmpy2
from Crypto.Util.number import long_to_bytes 

e = 54722
n = 17083941230213489700426636484487738282426471494607098847295335339638177583685457921198569105417734668692072727759139358207667248703952436680183153327606147421932365889983347282046439156176685765143620637107347870401946946501620531665573668068349080410807996582297505889946205052879002028936125315312256470583622913646319779125559691270916064588684997382451412747432722966919513413709987353038375477178385125453567111965259721484997156799355617642131569095810304077131053588483057244340742751804935494087687363416921314041547093118565767609667033859583125275322077617576783247853718516166743858265291135353895239981121
c = 3738960639194737957667684143565005503596276451617922474669745529299929395507971435311181578387223323429323286927370576955078618335757508161263585164126047545413028829873269342924092339298957635079736446851837414357757312525158356579607212496060244403765822636515347192211817658170822313646743520831977673861869637519843133863288550058359429455052676323196728280408508614527953057214779165450356577820378810467527006377296194102671360302059901897977339728292345132827184227155061326328585640019916328847372295754472832318258636054663091475801235050657401857262960415898483713074139212596685365780269667500271108538319
p = 106021448991021391444550749375115277080844281746248845802565680557785009341952320484175568763707424932172033597514861602114171459176440279045761846695231788376075050452154924141266290931413542110639081792550648106240966552406813059396358355737185354885474455248579946190266152416149137616855791805617206153497
q = 161136651053130509602530659420755324119806487925813087617466818245407407797561810253722204813002837916779909309520498985459703212021249251124954613236122142746302911323565396331355397916764254680629384957057354297855676493062493901977415968666512459829211010720514167083018352796496733697235524845188512914793

phi = (q-1) * (p-1)
d=gmpy2.invert(e//2,phi)
m=gmpy2.powmod(c,int(d),n)
m=gmpy2.iroot(m,2)[0]
print (long_to_bytes(m))

2：gcd(e,phi)=e

# 破解时间较长
def e_phi(e,c,p,q,flag_prefix):
    '''
    flag_prefix = b'buuctf' 二进制字符串
    '''
    n = p*q
    c_p = powmod(c,(1+3307*(p-1)//e)//e,p)
    print("find one")
    C1=solution(p,c_p)
    print("find all")
    c_q = powmod(c,(1+(2649*(q-1)//e))//e,q)
    print("find another")
    C2=solution(q,c_q)
    print("find all")
    a = invert(p,q)
    b = invert(q,p)
    #x = (b*q*c_p+a*p*c_q)%n
    flag=0
    for i in C1:
        for j in C2:
            flag+=1
            if flag%1000000 == 0:
                print(flag)
            x = (b*q*i+a*p*j)%n
            if(flag_prefix in n2s(x)):
                print(n2s(x))

                
def n2s(x):
    try:
        try:
            # flag = hex(x)[2:].decode("hex")
            flag = long_to_bytes(x)
        except:
            # flag = hex(x)[2:-1].decode("hex")
            flag = long_to_bytes(x)
    except:
        flag=''
    return flag


def onemod(p,r):
    t=p-2
    while powmod(t,(p-1)//r,p)==1: t-=1
    return powmod(t,(p-1)//r,p)


def solution(p,root):
    g=onemod(p,0x1337)
    may=[]
    for i in range(0x1337):
        if i%100 == 0:
            print(i)
        may.append(root*pow(g,i,p)%p)
    return may

例题：[NCTF2019]easyRSA （e=4919）

特殊的，e = $2^t$ 且e比较小（e = 256）

m = sympy.nthroot_mod(c,e,n,all_roots=True)
for i in m:
    print(long_to_bytes(i))

或者 sage

#多项式环求解
e = 256
n=107316975771284342108362954945096489708900302633734520943905283655283318535709
c = 19384002358725759679198917686763310349050988223627625096050800369760484237557
R.<x>=Zmod(n)[]
f = x^e-c
f.roots()

dp泄露，已知n、e、c和dp

from Crypto.Util.number import *
import gmpy2

e = 65537
n = 156808343598578774957375696815188980682166740609302831099696492068246337198792510898818496239166339015207305102101431634283168544492984586566799996471150252382144148257236707247267506165670877506370253127695314163987084076462560095456635833650720606337852199362362120808707925913897956527780930423574343287847
c = 108542078809057774666748066235473292495343753790443966020636060807418393737258696352569345621488958094856305865603100885838672591764072157183336139243588435583104423268921439473113244493821692560960443688048994557463526099985303667243623711454841573922233051289561865599722004107134302070301237345400354257869
dp = 734763139918837027274765680404546851353356952885439663987181004382601658386317353877499122276686150509151221546249750373865024485652349719427182780275825

#先爆破K得到p、q
temp=dp*e
for i in range(1,e) :
    if (temp-1)%i==0:
        x=(temp-1)//i+1
        y=n%x
        if y==0:
            p=x
            break
q = n // p
assert isPrime(p)
assert isPrime(q)
#print(f"p={p}\nq={q}")

phi = (q-1) * (p-1)
d = gmpy2.invert(e,phi)
#print(d)
m = pow(c,d,n)
m = long_to_bytes(m)
print(m)

公钥解析

import Crypto.PublicKey.RSA as RSA
with open("pubkey.pem", "r") as f:
   key = RSA.importKey(f.read())
n = key.n
e = key.e
print (n)
print (e)

pq相似

import gmpy2
import sympy
from Crypto.Util.number import long_to_bytes

n=177606504836499246970959030226871608885969321778211051080524634084516973331441644993898029573612290095853069264036530459253652875586267946877831055147546910227100566496658148381834683037366134553848011903251252726474047661274223137727688689535823533046778793131902143444408735610821167838717488859902242863683
e = 65537
c=1457390378511382354771000540945361168984775052693073641682375071407490851289703070905749525830483035988737117653971428424612332020925926617395558868160380601912498299922825914229510166957910451841730028919883807634489834128830801407228447221775264711349928156290102782374379406719292116047581560530382210049

n2=gmpy2.iroot(n,2)[0]
p=sympy.nextprime(n2)
q=n//p
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))

共模攻击

原理：扩展欧几里得

import gmpy2
from Crypto.Util.number import long_to_bytes

e1 = 2767
e2 = 3659

n = 21058339337354287847534107544613605305015441090508924094198816691219103399526800112802416383088995253908857460266726925615826895303377801614829364034624475195859997943146305588315939130777450485196290766249612340054354622516207681542973756257677388091926549655162490873849955783768663029138647079874278240867932127196686258800146911620730706734103611833179733264096475286491988063990431085380499075005629807702406676707841324660971173253100956362528346684752959937473852630145893796056675793646430793578265418255919376323796044588559726703858429311784705245069845938316802681575653653770883615525735690306674635167111

c1 = 20152490165522401747723193966902181151098731763998057421967155300933719378216342043730801302534978403741086887969040721959533190058342762057359432663717825826365444996915469039056428416166173920958243044831404924113442512617599426876141184212121677500371236937127571802891321706587610393639446868836987170301813018218408886968263882123084155607494076330256934285171370758586535415136162861138898728910585138378884530819857478609791126971308624318454905992919405355751492789110009313138417265126117273710813843923143381276204802515910527468883224274829962479636527422350190210717694762908096944600267033351813929448599
c2 = 11298697323140988812057735324285908480504721454145796535014418738959035245600679947297874517818928181509081545027056523790022598233918011261011973196386395689371526774785582326121959186195586069851592467637819366624044133661016373360885158956955263645614345881350494012328275215821306955212788282617812686548883151066866149060363482958708364726982908798340182288702101023393839781427386537230459436512613047311585875068008210818996941460156589314135010438362447522428206884944952639826677247819066812706835773107059567082822312300721049827013660418610265189288840247186598145741724084351633508492707755206886202876227

_, r, s = gmpy2.gcdext(e1, e2)

m = pow(c1, r, n) * pow(c2, s, n) % n
print(long_to_bytes(m))

小明文攻击

import gmpy2
from Crypto.Util.number import long_to_bytes

e = 0x10001
f=open('rsa_16m.txt',"r")
f.readline()
c=int(f.readline().split("=")[1],16)
m = gmpy2.iroot(c,e)[0]
print(long_to_bytes(m))

已知e、d、c，不知道n

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

e = 0x10001
d = 19275778946037899718035455438175509175723911466127462154506916564101519923603308900331427601983476886255849200332374081996442976307058597390881168155862238533018621944733299208108185814179466844504468163200369996564265921022888670062554504758512453217434777820468049494313818291727050400752551716550403647148197148884408264686846693842118387217753516963449753809860354047619256787869400297858568139700396567519469825398575103885487624463424429913017729585620877168171603444111464692841379661112075123399343270610272287865200880398193573260848268633461983435015031227070217852728240847398084414687146397303110709214913
c = 5382723168073828110696168558294206681757991149022777821127563301413483223874527233300721180839298617076705685041174247415826157096583055069337393987892262764211225227035880754417457056723909135525244957935906902665679777101130111392780237502928656225705262431431953003520093932924375902111280077255205118217436744112064069429678632923259898627997145803892753989255615273140300021040654505901442787810653626524305706316663169341797205752938755590056568986738227803487467274114398257187962140796551136220532809687606867385639367743705527511680719955380746377631156468689844150878381460560990755652899449340045313521804

kphi = e*d - 1

for k in range(1, e):
    if kphi % k == 0:
        phi = kphi // k
        root = iroot(phi, 2)[0]
        for p in range(root - 2000, root + 2000):
            if phi % (p-1) == 0: break
        else: continue
        break

q = phi//(p-1) + 1
m = pow(c, d, p*q)
print(long_to_bytes(m))

已知n、c，推理公式然后爆破e

例

'''
A=(((y%x)**5)%(x%y))**2019+y**316+(y+1)/x
p=next_prime(z*x*y)
q=next_prime(z)
'''
A =  2683349182678714524247469512793476009861014781004924905484127480308161377768192868061561886577048646432382128960881487463427414176114486885830693959404989743229103516924432512724195654425703453612710310587164417035878308390676612592848750287387318129424195208623440294647817367740878211949147526287091298307480502897462279102572556822231669438279317474828479089719046386411971105448723910594710418093977044179949800373224354729179833393219827789389078869290217569511230868967647963089430594258815146362187250855166897553056073744582946148472068334167445499314471518357535261186318756327890016183228412253724
n =  117930806043507374325982291823027285148807239117987369609583515353889814856088099671454394340816761242974462268435911765045576377767711593100416932019831889059333166946263184861287975722954992219766493089630810876984781113645362450398009234556085330943125568377741065242183073882558834603430862598066786475299918395341014877416901185392905676043795425126968745185649565106322336954427505104906770493155723995382318346714944184577894150229037758434597242564815299174950147754426950251419204917376517360505024549691723683358170823416757973059354784142601436519500811159036795034676360028928301979780528294114933347127
c =  41971850275428383625653350824107291609587853887037624239544762751558838294718672159979929266922528917912189124713273673948051464226519605803745171340724343705832198554680196798623263806617998072496026019940476324971696928551159371970207365741517064295956376809297272541800647747885170905737868568000101029143923792003486793278197051326716680212726111099439262589341050943913401067673851885114314709706016622157285023272496793595281054074260451116213815934843317894898883215362289599366101018081513215120728297131352439066930452281829446586562062242527329672575620261776042653626411730955819001674118193293313612128

import sympy
from gmpy2 import *
from Crypto.Util.number import long_to_bytes

p = 842868045681390934539739959201847552284980179958879667933078453950968566151662147267006293571765463137270594151138695778986165111380428806545593588078365331313084230014618714412959584843421586674162688321942889369912392031882620994944241987153078156389470370195514285850736541078623854327959382156753458569
q = 139916095583110895133596833227506693679306709873174024876891023355860781981175916446323044732913066880786918629089023499311703408489151181886568535621008644997971982182426706592551291084007983387911006261442519635405457077292515085160744169867410973960652081452455371451222265819051559818441257438021073941183
phi=(p-1)*(q-1)

e=2
str1="RoarCTF{"
while(e<100000):
    e=next_prime(e)
    try:
        d=invert(e,phi)
        m=pow(c,d,n)
    except:
        print (e)
    else:
        d=invert(e,phi)
        m=pow(c,d,n)
        str2=str(long_to_bytes(m))
        if str1 in str2:
            print(long_to_bytes(m))
            break

只有三组c、n，中国剩余定理

from gmpy2 import *
from Crypto.Util.number import *
from functools import reduce

N1 = int(str(331310324212000030020214312244232222400142410423413104441140203003243002104333214202031202212403400220031202142322434104143104244241214204444443323000244130122022422310201104411044030113302323014101331214303223312402430402404413033243132101010422240133122211400434023222214231402403403200012221023341333340042343122302113410210110221233241303024431330001303404020104442443120130000334110042432010203401440404010003442001223042211442001413004),5)
c1 = int(str(310020004234033304244200421414413320341301002123030311202340222410301423440312412440240244110200112141140201224032402232131204213012303204422003300004011434102141321223311243242010014140422411342304322201241112402132203101131221223004022003120002110230023341143201404311340311134230140231412201333333142402423134333211302102413111111424430032440123340034044314223400401224111323000242234420441240411021023100222003123214343030122032301042243),5)
N2 = int(str(302240000040421410144422133334143140011011044322223144412002220243001141141114123223331331304421113021231204322233120121444434210041232214144413244434424302311222143224402302432102242132244032010020113224011121043232143221203424243134044314022212024343100042342002432331144300214212414033414120004344211330224020301223033334324244031204240122301242232011303211220044222411134403012132420311110302442344021122101224411230002203344140143044114),5)
c2 = int(str(112200203404013430330214124004404423210041321043000303233141423344144222343401042200334033203124030011440014210112103234440312134032123400444344144233020130110134042102220302002413321102022414130443041144240310121020100310104334204234412411424420321211112232031121330310333414423433343322024400121200333330432223421433344122023012440013041401423202210124024431040013414313121123433424113113414422043330422002314144111134142044333404112240344),5)
N3 = int(str(332200324410041111434222123043121331442103233332422341041340412034230003314420311333101344231212130200312041044324431141033004333110021013020140020011222012300020041342040004002220210223122111314112124333211132230332124022423141214031303144444134403024420111423244424030030003340213032121303213343020401304243330001314023030121034113334404440421242240113103203013341231330004332040302440011324004130324034323430143102401440130242321424020323),5)
c3 = int(str(10013444120141130322433204124002242224332334011124210012440241402342100410331131441303242011002101323040403311120421304422222200324402244243322422444414043342130111111330022213203030324422101133032212042042243101434342203204121042113212104212423330331134311311114143200011240002111312122234340003403312040401043021433112031334324322123304112340014030132021432101130211241134422413442312013042141212003102211300321404043012124332013240431242),5)

N = [N1,N2,N3]
c = [c1,c2,c3]

def chinese_remainder(modulus, remainders):
    Sum = 0
    prod = reduce(lambda a, b: a*b, modulus)
    for m_i, r_i in zip(modulus, remainders):
        p = prod // m_i
        Sum += r_i * (inverse(p,m_i)*p)
    return Sum % prod
e = 3
# print(chinese_remainder(N,c))
pow_m_e = chinese_remainder(N,c)
# pow_m_e = 17446992834638639179129969961058029457462398677361658450137832328330435503838651797276948890990069700515669656391607670623897280684064423087023742140145529356863469816868212911716782075239982647322703714504545802436551322108638975695013439206776300941300053940942685511792851350404139366581130688518772175108412341696958930756520037
m = iroot(pow_m_e,3)[0]
print(long_to_bytes(m))

只知道三组m、c，不知道n、e

from Crypto.Util.number import *
from gmpy2 import *
from sympy import *
#from secret import flag
'''
p = getPrime(25)
e = # Hidden
q = getPrime(25)
n = p * q
m = bytes_to_long(flag.strip(b"npuctf{").strip(b"}"))

c = pow(m, e, n)
print(c)
print(pow(2, e, n))
print(pow(4, e, n))
print(pow(8, e, n))

'''
c = 169169912654178
c1 = 128509160179202
c2 = 518818742414340
c3 = 358553002064450
m1 = 2
m2 = 4
m3 = 8

n = gcd(pow(c1,2)-c2,c1*c2-c3)
#1054494004042394<16> = 2 · 18195301 · 28977097

e = discrete_log(n//2,c1,2)

p = 18195301
q = 28977097
phi = (q-1) * (p-1)
d = invert(e,phi)
m = pow(c,int(d),int(n//2))

print(long_to_bytes(m))

已知c、e、p、q，但是不互素

但是，由于不互素，所以按常规求不出d
需要换一种方法来解

from gmpy2 import *
from Crypto.Util.number import *
from tqdm import tqdm
def onemod(p,r):
    t = p-2
    while pow(t, (p-1) // r, p) == 1: t -= 1
    return pow(t, (p-1) // r, p)
def solution(p,root): 
    g = onemod(p, 0x1337)
    may = []
    for i in range(0x1337):
        if i % 100 == 0:
            print(i)
        may.append(root * pow(g,i,p) % p)
    return may
c = 10562302690541901187975815594605242014385201583329309191736952454310803387032252007244962585846519762051885640856082157060593829013572592812958261432327975138581784360302599265408134332094134880789013207382277849503344042487389850373487656200657856862096900860792273206447552132458430989534820256156021128891296387414689693952047302604774923411425863612316726417214819110981605912408620996068520823370069362751149060142640529571400977787330956486849449005402750224992048562898004309319577192693315658275912449198365737965570035264841782399978307388920681068646219895287752359564029778568376881425070363592696751183359
p = 199138677823743837339927520157607820029746574557746549094921488292877226509198315016018919385259781238148402833316033634968163276198999279327827901879426429664674358844084491830543271625147280950273934405879341438429171453002453838897458102128836690385604150324972907981960626767679153125735677417397078196059
q = 112213695905472142415221444515326532320352429478341683352811183503269676555434601229013679319423878238944956830244386653674413411658696751173844443394608246716053086226910581400528167848306119179879115809778793093611381764939789057524575349501163689452810148280625226541609383166347879832134495444706697124741
e = 0x1337
n = p * q
c_p = pow(c, (1 + 3307 * (p - 1) // e) // e, p)
C1 = solution(p, c_p)
c_q = pow(c, (1 + (2649 * (q - 1) // e)) // e, q)
C2 = solution(q, c_q)
a = invert(p, q)
b = invert(q, p)
flag=0
for i in tqdm(C1):
    for j in tqdm(C2):
        flag += 1
        if flag % 1000000 == 0:
            print(flag)
        x = (b * q * i + a * p * j) % n
        if b"NCTF{" in long_to_bytes(x):
            print(long_to_bytes(x))
            exit()

维纳攻击

import gmpy2
def transform(x,y):       #使用辗转相处将分数 x/y 转为连分数的形式
    res=[]
    while y:
        res.append(x//y)
        x,y=y,x%y
    return res
    
def continued_fraction(sub_res):
    numerator,denominator=1,0
    for i in sub_res[::-1]:      #从sublist的后面往前循环
        denominator,numerator=numerator,i*numerator+denominator
    return denominator,numerator   #得到渐进分数的分母和分子，并返回

    
#求解每个渐进分数
def sub_fraction(x,y):
    res=transform(x,y)
    res=list(map(continued_fraction,(res[0:i] for i in range(1,len(res)))))  #将连分数的结果逐一截取以求渐进分数
    return res

def get_pq(a,b,c):      #由p+q和pq的值通过维达定理来求解p和q
    par=gmpy2.isqrt(b*b-4*a*c)   #由上述可得，开根号一定是整数，因为有解
    x1,x2=(-b+par)//(2*a),(-b-par)//(2*a)
    return x1,x2

def wienerAttack(e,n):
    for (d,k) in sub_fraction(e,n):  #用一个for循环来注意试探e/n的连续函数的渐进分数，直到找到一个满足条件的渐进分数
        if k==0:                     #可能会出现连分数的第一个为0的情况，排除
            continue
        if (e*d-1)%k!=0:             #ed=1 (mod φ(n)) 因此如果找到了d的话，(ed-1)会整除φ(n),也就是存在k使得(e*d-1)//k=φ(n)
            continue
        
        phi=(e*d-1)//k               #这个结果就是 φ(n)
        px,qy=get_pq(1,n-phi+1,n)
        if px*qy==n:
            p,q=abs(int(px)),abs(int(qy))     #可能会得到两个负数，负负得正未尝不会出现
            d=gmpy2.invert(e,(p-1)*(q-1))     #求ed=1 (mod  φ(n))的结果，也就是e关于 φ(n)的乘法逆元d
            return d
    print("该方法不适用")
    
    
e = 14058695417015334071588010346586749790539913287499707802938898719199384604316115908373997739604466972535533733290829894940306314501336291780396644520926473
n = 33608051123287760315508423639768587307044110783252538766412788814888567164438282747809126528707329215122915093543085008547092423658991866313471837522758159
d=wienerAttack(e,n)
print("d=",d)

已知c、m、n，求e（离散对数问题）

n = 2 ** 256
m = 73964803637492582853353338913523546944627084372081477892312545091623069227301
c = 21572244511100216966799370397791432119463715616349800194229377843045443048821
e=discrete_log(Mod(c,n),Mod(m,n))
print(e)

已知高位攻击

详见另一篇博客，传送门

q = next_prime(p + (1 << int(nbits * beta)))

#sage
nbits = 1024
beta = 0.44

n = 59969098213446598961510550233718258878862148298191323654672950330070587404726715299685997489142290693126366408044603303463518341243526241117556011994804902686998166238333549719269703453450958140262475942580009981324936992976252832887660977703209225426388975233018602730303262439218292062822981478737257836581
e = 970698965238639683403205181589498135440069660016843488485401994654202837058754446853559143754852628922125327583411039117445415303888796067576548626904070971514824878024057391507617988385537930417136322298476467215300995795105008488692961624917433064070351961856959734368784774555385603000155569897078026670993484466622344106374637350023474339105113172687604783395923403613555236693496567851779400707953027457705617050061193750124237055690801725151098972239120476113241310088089420901051617493693842562637896252448161948655455277146925913049354086353328749354876619287042077221173795354616472050669799421983520421287
c = 2757297249371055260112176788534868300821961060153993508569437878576838431569949051806118959108641317578931985550844206475198216543139472405873345269094341570473142756599117266569746703013099627523306340748466413993624965897996985230542275127290795414763432332819334757831671028121489964563214463689614865416498886490980692515184662350519034273510244222407505570929178897273048405431658365659592815446583970229985655015539079874797518564867199632672678818617933927005198847206019475149998468493858071672920824599672525667187482558622701227716212254925837398813278836428805193481064316937182435285668656233017810444672

myR = RealField(1000)
x = polygen(myR)
f = x * (x + (1 << int(nbits * beta))) - n
p = int(f.roots()[1][0])
print(p)
while n % p != 0:
    p = p - 1

q = n // p
print(f"p = {p}")
print(f"q = {q}")

phi = (p² - 1) * (q² - 1)

from Crypto.Util.number import inverse, long_to_bytes

p = 7743971733771153102128801312798743998017713722732925283466018690899116898707556486947918196848489007935614742583856884731087798825462330340492923214926391
q = 7743971733771153105036156209981171560215008954284943420880584133648389139833517283670475349302080701240378945438911146974137885250527042074631329729385091
n = p * q
MOD = n * n
phi = (p**2 - 1) * (q**2 - 1)


def seq(r, k):
    A = matrix(Zmod(MOD), [[r, -1], [1, 0]])
    x = matrix(Zmod(MOD), [[2], [r]])
    return int((A**k * x)[0, 0])


def L(x):
    return (x % MOD - 1) // n


e = 970698965238639683403205181589498135440069660016843488485401994654202837058754446853559143754852628922125327583411039117445415303888796067576548626904070971514824878024057391507617988385537930417136322298476467215300995795105008488692961624917433064070351961856959734368784774555385603000155569897078026670993484466622344106374637350023474339105113172687604783395923403613555236693496567851779400707953027457705617050061193750124237055690801725151098972239120476113241310088089420901051617493693842562637896252448161948655455277146925913049354086353328749354876619287042077221173795354616472050669799421983520421287
c = 2757297249371055260112176788534868300821961060153993508569437878576838431569949051806118959108641317578931985550844206475198216543139472405873345269094341570473142756599117266569746703013099627523306340748466413993624965897996985230542275127290795414763432332819334757831671028121489964563214463689614865416498886490980692515184662350519034273510244222407505570929178897273048405431658365659592815446583970229985655015539079874797518564867199632672678818617933927005198847206019475149998468493858071672920824599672525667187482558622701227716212254925837398813278836428805193481064316937182435285668656233017810444672

d = inverse(e, phi)
r = seq(c, d) % n
v = seq(r, e)
print(long_to_bytes(L(c * inverse(v, MOD))))

N = p⁷*q，并且p和q有部分有效位相同

例题及解法

n=pqrs

可以直接求phi用其中的两个，结果是一样的

import gmpy2
from Crypto.Util.number import *


n = 8250871280281573979365095715711359115372504458973444367083195431861307534563246537364248104106494598081988216584432003199198805753721448450911308558041115465900179230798939615583517756265557814710419157462721793864532239042758808298575522666358352726060578194045804198551989679722201244547561044646931280001
e = 3
c = 945272793717722090962030960824180726576357481511799904903841312265308706852971155205003971821843069272938250385935597609059700446530436381124650731751982419593070224310399320617914955227288662661442416421725698368791013785074809691867988444306279231013360024747585261790352627234450209996422862329513284149

n1=gmpy2.iroot(n,2)[0]
p = 225933944608558304529179430753170813347
r = 223213222467584072959434495118689164399
s = 260594583349478633632570848336184053653
q = 218566259296037866647273372633238739089


for a in (p,q,r,s):
    for b in (p,q,r,s):
        if a==b:
            continue
        try:
            phi=a*(a-1)*b*(b-1)
            d=gmpy2.invert(e,phi)
            m=pow(c,d,a**2*b**2)
            print(long_to_bytes(m))
        except:
            continue

p、q = sympy.nextprime((B!)%A)

威尔逊定理解rsa详解

pq相差大，已知p2+q2,不知道n，求p、q

题目

from secret import flag

m = libnum.s2n(flag)

p = libnum.generate_prime(1024)
q = libnum.generate_prime(200)
a = p**2+q**2

e1=libnum.generate_prime(16)
e2=gmpy2.next_prime(e1)
n=p*q
c1=pow(m,e1,n)
c2=pow(m**3,e2,3*n)

print("a=",a)
print("c1=",c1)
print("c2=",c2)

a= 24206265871435822703437518362958531356211626642007253784650483176562422122875340827288772819943478120095206127359525474074270229930748107117372266160892473927182468441245406239260325825983178681264861898227398697570877226191045205101392758306677352447609463242377314079908674367312467009340725296069934982237938083953835511845988528740319671339681988454341775949773782599028758795858243892505801751373271145879675219676812982346718542627999285987122318375982631166086424677380378329616021990407324172009541237668232705741580914256004477070860164426099061412907214192878993303911745798633464333183684318013108481194330
c1= 126859631077098611901511232008797051138574124478480730639144977155143424488144265276530078952871200528973257851214276765041293928258819231377836450311630167556457808627111669654324359435794012547994299283010757231576308562368663215764193973190892053938581481578656240077555108821408787703658040501252208210069312753866895619962762868562608316860640231777068617867166147
c2= 11826835748339980863398980051042008082750935496082618268555582889298555680769555714450413403033938771160762505072342684767000980792793194857952806136430859946630518327736718530548802427141716474368099142576512330275210929488407696914896855868077026602082934281710567654604010065436992743237842728041335992414634519294554988610297895321490267356849938289132035975812904

#libnum.generate_prime(n)：产生长度为n位的伪素数

由题目可知，p的位数为1024，q的位数为200。在各自平方之后，p的平方远远大于q的平方，所以a开平方的值可近似看作p，然后（a-p**2）开平方得到q。又因为e1 = libnum.generate_prime(16)，是一个长度为16位的伪素数，在这个范围内我们可以对e1进行爆破，找到满足条件的e1,再求Phi和d，最终得到flag。

import gmpy2
from Crypto.Util.number import *

a= 24206265871435822703437518362958531356211626642007253784650483176562422122875340827288772819943478120095206127359525474074270229930748107117372266160892473927182468441245406239260325825983178681264861898227398697570877226191045205101392758306677352447609463242377314079908674367312467009340725296069934982237938083953835511845988528740319671339681988454341775949773782599028758795858243892505801751373271145879675219676812982346718542627999285987122318375982631166086424677380378329616021990407324172009541237668232705741580914256004477070860164426099061412907214192878993303911745798633464333183684318013108481194330
c1= 126859631077098611901511232008797051138574124478480730639144977155143424488144265276530078952871200528973257851214276765041293928258819231377836450311630167556457808627111669654324359435794012547994299283010757231576308562368663215764193973190892053938581481578656240077555108821408787703658040501252208210069312753866895619962762868562608316860640231777068617867166147
c2= 11826835748339980863398980051042008082750935496082618268555582889298555680769555714450413403033938771160762505072342684767000980792793194857952806136430859946630518327736718530548802427141716474368099142576512330275210929488407696914896855868077026602082934281710567654604010065436992743237842728041335992414634519294554988610297895321490267356849938289132035975812904

p = gmpy2.iroot(a,2)[0]
q = gmpy2.iroot(a-p**2,2)[0]
n = p*q
phi = (p-1)*(q-1)
for e in range(2**15,2**16):
    if gmpy2.is_prime(e):
        try:
            d = gmpy2.invert(e,phi)
            m = pow(c1,d,n)
            flag = long_to_bytes(m)
            if b'flag' in flag:
                print(flag)
                break
        except:
            pass