当 p 和 q 选取不当时,例如 q 选取了 p 的 t 倍的后几个素数,甚至 q 就是 p 的后几个素数,可以在较短时间内分解 n。
原理
不妨设:
q=tp+k
那么:
n=pq=p(tp+k)=tp2+pk
即:
tp2+kp−n=0
则:
p=2t−k+k2+4tn
由于 p 是整数,所以 k2+4tn 是整数,即 k2+4tn 开方后是整数。
寻找到符合条件的 k,那么:
pq=2t−k+k2+4tn=tp+k
如果 pq==n,那么已成功分解。否则继续寻找 k。
代码
大数精确开方需要用到 gmpy2 库中的 iroot。
1 2 3 4 5 6 7 8 9 10 11 12
deffactor(): n_4t = n*4*t for k in range(100000): delta = k**2 + n_4t if gmpy2.iroot(delta, 2)[1]: print'k =', k p = (-k + gmpy2.iroot(delta, 2)[0]) / (2*t) q = t*p + k if p*q == n: print'p =', p print'q =', q return p, q
例子
2018 柏鹭杯:simple RSA
题目:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
from flag import flag from Crypto.Util.number import * import random defnext_prime(n): num = n + 1 whileTrue: if isPrime(num): return num num += 1 p = random.randint(1<<3071,1<<3072) p = next_prime(p) q = next_prime(p*10)
N = p*q e = 65537 c = pow(bytes_to_long(flag),e,N) print N#247157208312655169175097941364280738161257111976460225724719907081110265510517450181419502794457206227461600647913804553439171851865273449559295717229024951735351965745325255241561391509015823198303928588939850683031392486366218841593013566932215141428061199015117025898704736991786081007198271335363347647516874679013119543722851148642512142186199102168074461255284546705588056994149297326331376082141145137980534967406372164077378650248545875219877244489040506317293082270408705203779841533080244655519849164084793887915122847280359452339072498784918027724621588636245527176960457003310429876627882173282069366037431766179722648353575718417895929519296072344510519198593252963273537190447967056699273665756186541135880261688073100218736960343554003491651502334045257343825793705434779809139021362473746587814528428007114308414633338220797896397738142172067161950968365434368211510967904096253326804711795198906393597153228365711080786247894858858419136771806150038968465644512536135428099037524022644906606239281576512245480765249280626544900781649017542649977530381598608436485399917576052247750573936190833224008929770080605906041913084656134359260509037195783858871830359437278131656343708211575987756873026171223324073191307367943843353573378426157170935012284820053625264544030714057464690450568057598110227083895395913850243271935830358181622027323185508807486853971929523201869477689585619024238113916052252320578711256593537267591407960305853736136636628575478996733430026632486500743561965770413140633948002705696925426367918545515713035754606128166993229587155817506068035187995926746472892280477401942441831391756895131543049750847590716935278314226902082626392655666615086297442052602217416486188297831289978272258543231414975069191549588547253936829655332588805672513945883351937495650167502066292697223592894483418517613405613285519159 print c#152721025887735064764471379084548069204525956728140596238274397757947415316727016281416993518884790524343567541799262176820909148208728616947040227306302164641933331109468512979068186962047716308015535717796123080303496277784765187481185086876434873226524784636408104495312136956587251145463229424950634548624036265557622592089071331292811066840281494102799063634204855779210798330603868025111521826209601342683209160845433746624786171189961029265101816540639855230011618388675527443511618729301028631422873421421991470450059414988968787693753741941765791793672069240992955177930884210118700416564364129283739917229225845073750451244070534919112957275948312337882004219145847493047815403283126471638320784008475284616178697542301935170768573588093196019976675846311280356987370969400610196847990069257614148181804915868273001764028563852238142447411811579695265293746037324400494199877368049162903819737962946786971556872009326814914717430484711885484790156341127433550909206551293806568904858726942820132521566970376839336895645431303013575622422180179687172859250687080526393904583834607514619581478966664406178290247731116920836372943133394640322159512633671870473674514938423231596849301615200001553851411828993918474534316510609878376462094608058640335426907349648369552864820322464995077358198844334320833893207364879282292959161203675080110629771237503657412087961891443054530286088807186134851425688726147108076040204500951624929585070273336203814962656253259257806100191430918121713005141607192112560560371475173081441671613602480052062955279287813475764285469835557663176529059039540417149792518941598550609678298901186032272305421028365295602810159191055078633881059737011784127699357480578433240110432805495328517379885306237631225477566136721077348329866885731002878563684349453668924250445128775992616650275173644658245397235667490402628
由题目可知,p 是一个 3000 多位的素数,q 是 10 倍 p 的下一个素数。
直接可由上方法分解 n:
1 2 3
k = 1171 p = 4971490805710648894784063900603982138103528416416093113682856149525895474391965093292856360186270533203485404384261736770807923420477678768335595268260058770929420214670794184479653642688593773001265441972139034999789321709099375988424776953616924996952770970955016095518058970453801153351600603001621188113472370286189729979231943525793160692844078376540082324198649179890017101800683049489232021392715915700831833371902425005874555370189042455321691195416425399507551235346773377429357933240695935997956969841660473107352934178051894901298644110556291216221039424250078546978571086275993790666829060240691673857284132895978717935677825502362997789971900863003499701755174512295162461514926135376073693593713246781021035797102243028802222257489266812730745381990847604727619717567202686948267842932198278066304365500430012440700948799107940169074390644763691400614036677335457180241108468029814414775113509028739480597728319 q = 49714908057106488947840639006039821381035284164160931136828561495258954743919650932928563601862705332034854043842617367708079234204776787683355952682600587709294202146707941844796536426885937730012654419721390349997893217090993759884247769536169249969527709709550160955180589704538011533516006030016211881134723702861897299792319435257931606928440783765400823241986491798900171018006830494892320213927159157008318333719024250058745553701890424553216911954164253995075512353467733774293579332406959359979569698416604731073529341780518949012986441105562912162210394242500785469785710862759937906668290602406916738572841328959787179356778255023629977899719008630034997017551745122951624615149261353760736935937132467810210357971022430288022222574892668127307453819908476047276197175672026869482678429321982780663043655004300124407009487991079401690743906447636914006140366773354571802411084680298144147751135090287394805977284361
得到 flag:ISEC{simp13_crypt0}
模不互素
适用情况:
当存在两个公钥的 n 不互素时,显然可以直接对这两个数求最大公因数,直接获得 p 和 q。
代码
1 2 3 4 5 6 7 8 9
deffactor(): p = gmpy2.gcd(n1, n2) q1 = n1 / p q2 = n2 / p assert p*q1 == n1 assert p*q2 == n2 print'p =', p print'q1 =', q1 print'q2 =', q2
defPollards_p_1(N): a = 2 n = 2 whileTrue: a = pow(a, n, N) res = gmpy2.gcd(a-1, N) if res != 1and res != N: print'n =', n print'p =', res return res n += 1
例子
[NCTF2019] childRSA
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
from random import choice from Crypto.Util.number import isPrime, sieve_base as primes from flag import flag
defgetPrime(bits): whileTrue: n = 2 while n.bit_length() < bits: n *= choice(primes) if isPrime(n + 1): return n + 1
e = 0x10001 m = int.from_bytes(flag.encode(), 'big') p, q = [getPrime(2048) for _ in range(2)] n = p * q c = pow(m, e, n) # n = 32849718197337581823002243717057659218502519004386996660885100592872201948834155543125924395614928962750579667346279456710633774501407292473006312537723894221717638059058796679686953564471994009285384798450493756900459225040360430847240975678450171551048783818642467506711424027848778367427338647282428667393241157151675410661015044633282064056800913282016363415202171926089293431012379261585078566301060173689328363696699811123592090204578098276704877408688525618732848817623879899628629300385790344366046641825507767709276622692835393219811283244303899850483748651722336996164724553364097066493953127153066970594638491950199605713033004684970381605908909693802373826516622872100822213645899846325022476318425889580091613323747640467299866189070780620292627043349618839126919699862580579994887507733838561768581933029077488033326056066378869170169389819542928899483936705521710423905128732013121538495096959944889076705471928490092476616709838980562233255542325528398956185421193665359897664110835645928646616337700617883946369110702443135980068553511927115723157704586595844927607636003501038871748639417378062348085980873502535098755568810971926925447913858894180171498580131088992227637341857123607600275137768132347158657063692388249513 # c = 26308018356739853895382240109968894175166731283702927002165268998773708335216338997058314157717147131083296551313334042509806229853341488461087009955203854253313827608275460592785607739091992591431080342664081962030557042784864074533380701014585315663218783130162376176094773010478159362434331787279303302718098735574605469803801873109982473258207444342330633191849040553550708886593340770753064322410889048135425025715982196600650740987076486540674090923181664281515197679745907830107684777248532278645343716263686014941081417914622724906314960249945105011301731247324601620886782967217339340393853616450077105125391982689986178342417223392217085276465471102737594719932347242482670320801063191869471318313514407997326350065187904154229557706351355052446027159972546737213451422978211055778164578782156428466626894026103053360431281644645515155471301826844754338802352846095293421718249819728205538534652212984831283642472071669494851823123552827380737798609829706225744376667082534026874483482483127491533474306552210039386256062116345785870668331513725792053302188276682550672663353937781055621860101624242216671635824311412793495965628876036344731733142759495348248970313655381407241457118743532311394697763283681852908564387282605279108
可以发现 p 和 q 是由前 10000 个随机的许多小质数乘积加 1 得到, 即 p−1 为许多小质数的乘积。那么可以利用 Pollard’s p − 1 算法来分解 N。
1 2 3 4 5 6 7 8 9 10
e = 0x10001 n = 32849718197337581823002243717057659218502519004386996660885100592872201948834155543125924395614928962750579667346279456710633774501407292473006312537723894221717638059058796679686953564471994009285384798450493756900459225040360430847240975678450171551048783818642467506711424027848778367427338647282428667393241157151675410661015044633282064056800913282016363415202171926089293431012379261585078566301060173689328363696699811123592090204578098276704877408688525618732848817623879899628629300385790344366046641825507767709276622692835393219811283244303899850483748651722336996164724553364097066493953127153066970594638491950199605713033004684970381605908909693802373826516622872100822213645899846325022476318425889580091613323747640467299866189070780620292627043349618839126919699862580579994887507733838561768581933029077488033326056066378869170169389819542928899483936705521710423905128732013121538495096959944889076705471928490092476616709838980562233255542325528398956185421193665359897664110835645928646616337700617883946369110702443135980068553511927115723157704586595844927607636003501038871748639417378062348085980873502535098755568810971926925447913858894180171498580131088992227637341857123607600275137768132347158657063692388249513 c = 26308018356739853895382240109968894175166731283702927002165268998773708335216338997058314157717147131083296551313334042509806229853341488461087009955203854253313827608275460592785607739091992591431080342664081962030557042784864074533380701014585315663218783130162376176094773010478159362434331787279303302718098735574605469803801873109982473258207444342330633191849040553550708886593340770753064322410889048135425025715982196600650740987076486540674090923181664281515197679745907830107684777248532278645343716263686014941081417914622724906314960249945105011301731247324601620886782967217339340393853616450077105125391982689986178342417223392217085276465471102737594719932347242482670320801063191869471318313514407997326350065187904154229557706351355052446027159972546737213451422978211055778164578782156428466626894026103053360431281644645515155471301826844754338802352846095293421718249819728205538534652212984831283642472071669494851823123552827380737798609829706225744376667082534026874483482483127491533474306552210039386256062116345785870668331513725792053302188276682550672663353937781055621860101624242216671635824311412793495965628876036344731733142759495348248970313655381407241457118743532311394697763283681852908564387282605279108
p = pollards_p_1(n) q = n // p assert p*q == n d = gmpy2.invert(e, (p-1)*(q-1)) m = pow(c, d, n) print long_to_bytes(m)