将明文\(m\)加密成密文\(c\)，加密算法为： \[
c=E(m)=m^e\ mod\ n
\]
将密文\(c\)解密为明文\(m\)，解密算法为： \[
m=D(c)=c^d\ mod\ n
\]
RSA 必要算法
拓展欧几里得算法
1 2 3 4 5 6 7 8 9
defextendedGCD(a, b): # a*xi + b*yi = ri if b == 0: return1, 0, a else: x, y, q = extendedGCD(b, a % b) # q = gcd(a, b) = gcd(b, a%b) x, y = y, (x - (a // b) * y) return x, y, q
flag = list(b'watevr{RSA_from_ikea_is_fun_but_insecure#k20944uehdjfnjd335uro}') p = 43753 ## Univariate Polynomial Ring in y over Finite Field of size p R.<y> = GF(p)[]
## Analogous to the primes in Z defgen_irreducable_poly(deg): whileTrue: out = R.random_element(degree=deg) if out.is_irreducible(): return out
fac: factoring 911934970359 fac: using pretesting plan: normal fac: no tune info: using qs/gnfs crossover of 95 digits div: primes less than 10000 fmt: 1000000 iterations Total factoring time = 0.0080 seconds
import gmpy2 n= 22885480907469109159947272333565375109310485067211461543881386718201442106967914852474989176175269612229966461160065872310916096148216253429849921988412342732706875998100337754561586600637594798877898552625378551427864501926224989873772743227733285336042475675299391051376624685754547818835551263597996620383338263448888107691240136257201191331617560711786674975909597833383395574686942099700631002290836152972352041024137872983284691831292216787307841877839674258086005814225532597955826353796634417780156185485054141684249037538570742860026295194559710972266059844824388916869414355952432189722465103299013237588737 e = 3 c= 15685364647213619014219110070569189770745535885901269792039052046431067708991036961644224230125219358149236447900927116989931929305133870392430610563331490276096858863490412102016758082433435355613099047001069687409209484751075897343335693872741 m, flag = gmpy2.iroot(c, e) if flag: print(f"m={m}") else: print("could not decode m")
若\(m^3>n\)但并非\(m^3\gg n\) (这里需要跑比较久)
1 2 3 4 5 6 7 8 9 10 11
import gmpy2 n = 114976915747243387792157708464120735018971336213935438953074748276198282761939060395482051056351068439137722626185590043024556656813730840050547350912425438364703854627760482842307943026011880815011654341047422453012558617703411700393668892701036222135444420377515575624398723436532681305293727164639582093389 e = 3 c = 5828813410620741112500628876643872258919868379601617907887884191584237969605489971465692568848339200057188383649365078832766143513766368216471491824042974016773526107276856706832404477882581400769791378958901067683158857990261489285951805740071223765359992165262854641069674603160977034446644199945940251030 i = 0 while1: m, flag = gmpy2.iroot(c + i * n, e) if flag: print(f"m={m}") break i += 1
\(e=1\) 攻击
实现
1 2 3 4 5 6 7 8 9
n = 0x180be86dc898a3c3a710e52b31de460f8f350610bf63e6b2203c08fddad44601d96eb454a34dab7684589bc32b19eb27cffff8c07179e349ddb62898ae896f8c681796052ae1598bd41f35491175c9b60ae2260d0d4ebac05b4b6f2677a7609c2fe6194fe7b63841cec632e3a2f55d0cb09df08eacea34394ad473577dea5131552b0b30efac31c59087bfe603d2b13bed7d14967bfd489157aa01b14b4e1bd08d9b92ec0c319aeb8fedd535c56770aac95247d116d59cae2f99c3b51f43093fd39c10f93830c1ece75ee37e5fcdc5b174052eccadcadeda2f1b3a4a87184041d5c1a6a0b2eeaa3c3a1227bc27e130e67ac397b375ffe7c873e9b1c649812edcd e = 0x1 c = 0x4963654354467b66616c6c735f61706172745f736f5f656173696c795f616e645f7265617373656d626c65645f736f5f63727564656c797d i = 0 # i 可以取很多 while i < 10: m = c + i * n print(m) i += 1
import gmpy2 from functools import reduce defCRT(clist, nlist): N = reduce(lambda x, y: x * y, nlist) result = 0 for c, n inzip(clist, nlist): m = N // n d, r, s = gmpy2.gcdext(n, m) if d != 1: raise Exception("Input not pairwise co-prime") result += c * s * m return result % N, N e = 9 n = [142782424368849674771976671955176187834932417027468006479038058385550042422280158726561712259205616626939123504489410624745195777853423961104590708231562726165590769610040722589287393102301338152085670464005026301781192671834390892019478189768725018303217559795377795540494239283891894830166363576205812991157, 153610425077816156109768509904751446801233412970601397035720458311275245730833227428213917577405780162151444202393431444812010569489900435979730559895340377469612234558042643742219128033827948585534761030527275423811282367831985007507137144308704413007806012914286105842311420933479771294576841956749281552971, 152540067782701001222493009941492423063369171831039847414320547494725020441901272486665728360741395415762864872737675660423920609681185809510355937534756399208661762715484879562585724584849261266873624875852300611683382543315580370484972470694466195837255994159609193239840228218925381488410059939975556977947, 125842716702134814646356078531900645012495638692517778270527426844383063904041812273637776798591687732598509470005151551320457132061693618473039437320011446697406190781306264437609046721508738109650829547010385875425097336266103994639126319889016342284747700714199556143378526590058467791687837422897022829661, 116144389285266462769913139639175922392318396923181100785008570884082681963637784423143843845816350379438789947802939701820129805341796427821894273985551331666719808355412080909245720551238149511778060242720419584504473490216670437024863860559347959698828131475160058721701582089480924088773887932997353631767, 127833907448946785858374094953899556339175475846831397383049660262333005992005484987913355932559627279178940862787593749842796469355336182379062826441222705075178971785791223706944120681105575965622931327112817747065200324610697178273898956820957640413744954233327851461318200323486469677469950386824833536523, 130561613227079478921314550968562766645507834694262831586725464124109153306162445639759476845681271537955934718244296904503168256991962908095007040044300188572466395275317838178325500238288302672390013747102961340256309124310478931896245221622317302428447389760864327859640573452084295225059466376349115703119, 115953389401040751013569404909249958538962411171147823610874077094621794755967854844224923689925397631692572916641171075740839099217316101334941033937183815345038898177087515909675028366437302462022970987947264115373697445950951595479758872029099661065186221250394358255523574834723958546450323357472451930993, 143437107845384843564651522639125300763388830136500260725097766445883003928355325003575359566631064630487365774344508496878731109174874449170057678821440711511966073934025028100604234445470976333825866939923998344367645612128590820812489407412175198698290167077116185959180877334222693344630253253476594907313] c = [85033868418784308573673709960700777350314426427677627319697346811123742342359072170220428874952996988431950989321281905284522596263957356289624365171732095210045916218066135140320107686084053271623461104022705353814233772164502775939590711842361956121603943483040254727995655776263673058788416722141673409688, 66065963470666895005407449599703926269325406456711861190876894466341571726360462706664546294453572319565476664348345756905411939632955966517708138047546806602828064213238537646393524578984547577761559965654539771172357089802682793169968961304179886652390277814477825753096636750388350662980872556701402397564, 116011740820520887443111656288411611070614127688662643257265381793048354928820176624229624692124188995846076431510548507016903260774215950803926107831505634778278712070141663189086436127990584944132764896694777031370995058271038329228336417590284517922855284619653301817355115583540545182119702335431334401666, 97640420284096094887471273365295984332267897927392169402918423863919914002451127544715668846623138003564829254309568918651163254043205129883843425179687841236818720463784828905460885026290909768599562386370732119591181513319548915478512030197629196018254041500662654260834562708620760373487652389789200792120, 8112507653841374573057048967617108909055624101437903775740427861003476480616929517639719198652146909660899632120639789106782550275648578142883715280547602249589837441805676364041484345030575130408744621981440093280624046635769338568542048839419939250444929802135605724150484414516536378791500915047844188300, 36792148360808115566234645242678223867680969786675055638670907933041180936164293809961667801099516457636164692292891528415720085345494773373966277807505798679784807614784581861287048096977968620964436947452527540958289441390882589051225367658014709290392321808926567572528170531844664734909469690750971883323, 53043093283305492238903255767698153246673671181809989362223466090875767705978690531154079519999671834688647277179370374802495005937892824566602423646978168777735383632928274082669949750078161820002768640908750005814934158829006019656592134357897586040866207754535586785064545866404380204728594863102313407789, 88499407133762624445946519155722583633934260410706930537441122463087556094734626189377091740335667052378955691250910459790202385799502439716173363179773811920751410726795431402796346647688144853156900427797933862087074385441977254140336390678022955770879265490567987868532251217565094093318626424653599450992, 138337520305048557335599940473834485492131424901034295018189264168040969172072024612859307499682986987325414798210700710891033749119834960687318156171051379643844580970963540418974136891389303624057726575516576726845229494107327508855516437230240365759885913142671816868762838801720492804671259709458388192984] x, n = CRT(c, n) m, flag = gmpy2.iroot(x, e) if flag: print(f"m={m}") else: print("could not decode m")
Fs = [] for i inrange(cnt): f = (A[i] * x + B[i]) ** e - Cs[i] Fs.append(f) F = crt(Fs, Ns) M = prod(Ns) FF = F.change_ring(Zmod(M)) m = FF.monic().small_roots() print(m)
import gmpy2 from Crypto.Util.number import long_to_bytes
deftransform(x, y): # 使用辗转相处将分数 x/y 转为连分数的形式 res = [] while y: res.append(x//y) x, y = y, x % y return res
defcontinued_fraction(sub_res): numerator, denominator = 1, 0 for i in sub_res[::-1]: # 从sublist的后面往前循环 denominator, numerator = numerator, i*numerator+denominator return denominator, numerator # 得到渐进分数的分母和分子，并返回
# 求解每个渐进分数 defsub_fraction(x, y): res = transform(x, y) # 将连分数的结果逐一截取以求渐进分数 res = list(map(continued_fraction, (res[0:i] for i inrange(1, len(res))))) return res
defwienerAttack(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
n = 507419170088344932990702256911694788408493968749527614421614568612944144764889717229444020813658893362983714454159980719026366361318789415279417172858536381938870379267670180128174798344744371725609827872339512302232610590888649555446972990419313445687852636305518801236132032618350847705234643521557851434711389664130274468354405273873218264222293858509477860634889001898462547712800153111774564939279190835857445378261920532206352364005840238252284065587291779196975457288580812526597185332036342330147250312262816994625317482869849388424397437470502449815132000588425028055964432298176942124697105509057090546600330760364385753313923003549670107599757996810939165300581847068233156887269181096893089415302163770884312255957584660964506028002922164767453287973102961910781312351686488047510932997937700597992705557881172640175117476017503918294534205898046483981707558521558992058512940087192655700351675718815723840568640509355338482631416345193176708501897458649841539192993142790402734898948352382350766125000186026261167277014748183012844440603384989647664190074853086693408529737767147592432979469020671772152652865219092597717869942730499507426269170189547020660681363276871874469322437194397171763927907099922324375991793759 e = 77310199867448677782081572109343472783781135641712597643597122591443011229091533516758925238949755491395489408922437493670252550920826641442189683907973926843505436730014899918587477913032286153545247063493885982941194996251799882984145155733050069564485120660716110828110738784644223519725613280140006783618393995138076030616463398284819550627612102010214315235269945251741407899692274978642663650687157736417831290404871181902463904311095448368498432147292938825418930527188720696497596867575843476810225152659244529481480993843168383016583068747733118703000287423374094051895724494193455175131120243097065270804457787026492578916584536863548445813916819417857064037664101684455000184987531252344582899589746272173970083733130106407810619258077266603898529285634495710846838011858287024329514491058790557305041389614650730267774482954666726949886313386881066593946789460028399523245777171320319444673551268379126203862576627540177888290265714418064334752499940587750374552330008143708562065940245637685833371348603338834447212248648869514585047871442060412622164276894766238383894693759347590977926306581080390685360615407766600573527565016914830132066428454738135380178959590692145577418811677639050929791996313180297924833690095 c = 165251729917394529793163344300848992394021337429474789711805041655116845722480301677817165053253655027459227404782607373107477419083333844871948673626672704233977397989843349633720167495862807995411682262559392496273163155214888276398332204954185252030616473235814999366132031184631541209554169938146205402400412307638567132128690379079483633171535375278689326189057930259534983374296873110199636558962144635514392282351103900375366360933088605794654279480277782805401749872568584335215630740265944133347038070337891035560658434763924576508969938866566235926587685108811154229747423410476421860059769485356567301897413767088823807510568561254627099309752215808220067495561412081320541540679503218232020279947159175547517811501280846596226165148013762293861131544331444165070186672186027410082671602892508739473724143698396105392623164025712124329254933353509384748403154342322725203183050328143736631333990445537119855865348221215277608372952942702104088940952142851523651639574409075484106857403651453121036577767672430612728022444370874223001778580387635197325043524719396707713385963432915855227152371800527536048555551237729690663544828830627192867570345853910196397851763591543484023134551876591248557980182981967782409054277224 d = wienerAttack(e, n) m = pow(c, d, n)
n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113 e = 65537 dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657 c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751
p = gcd(pow(2, e * dp, n) - 2, n) assert n % p == 0 q = n // p d = pow(e, -1, (p - 1) * (q - 1)) m = pow(c, d, n)
n = 80642592772746398646558097588687958541171131704233319344980232942965050635113860017117519166348100569115174644678997805783380130114530824798808098237628247236574959152847903491509751809336988273823686988619679739640305091291330211169194377552925908412183162787327977125388852329089751737463948165202565859373 e = 13521 d = 14218766449983537783699024084862960813708451888387858392014856544340557703876299258990323621963898510226357248200187173211121827541826897886277531706124228848229095880229718049075745233893843373402201077890407507625110061976931591596708901741146750809962128820611844426759462132623616118530705745098783140913
defn_with_kphi(n, e, d): kphi = e * d - 1
k = kphi // n while kphi % k != 0: k += 1 phi = kphi // k # 构建方程 x^2+(\varphi(N)-N-1)x+N=0 a = 1 b = phi - n - 1 c = n delta = b ** 2 - 4 * a * c if delta < 0: return0, 0 from math import isqrt sqrt_delta = isqrt(delta) p = (-b + sqrt_delta) // (2 * a) q = (-b - sqrt_delta) // (2 * a) if p * q != n: return0, 0 return p, q print(n_with_kphi(n, e, d))
n = 80642592772746398646558097588687958541171131704233319344980232942965050635113860017117519166348100569115174644678997805783380130114530824798808098237628247236574959152847903491509751809336988273823686988619679739640305091291330211169194377552925908412183162787327977125388852329089751737463948165202565859373 e = 13521 d = 14218766449983537783699024084862960813708451888387858392014856544340557703876299258990323621963898510226357248200187173211121827541826897886277531706124228848229095880229718049075745233893843373402201077890407507625110061976931591596708901741146750809962128820611844426759462132623616118530705745098783140913
defkphi_2st(n, e, d): kphi = e * d - 1 s = 0 while kphi % (2 ** s) == 0: s += 1 from random import randint from math import gcd for _ inrange(e): a = randint(2, n - 1) for i inrange(1, s + 1): r = pow(a, kphi // (2 ** i), n) p = gcd(r - 1, n) if1 < p < n and n % p == 0: return p, n // p
# step 2 while rho ** ((q - 1) // r) == 1: rho = Fq.random_element() # step 3 # step 3.1 t = 0 s = q - 1 while s % r == 0: t += 1 s //= r # step 3.2 k = 1 while (k * s + 1) % r != 0: k += 1 alpha = (k * s + 1) // r # step 3.3 a = rho ** (r ** t - 1 * s) b = delta ** (r * alpha - 1) c = rho ** s h = 1 # step 4 for i inrange(1, t): d = b ** pow(r, t - 1 - i, q - 1) j = 0if d == 1else -d.log(a) b *= (c ** r) ** j h *= c ** j c **= r
# step 5 root = int(delta ** alpha * h) ifnotall: return root # if all is True, generate all roots to return # 2 ^ (q - 1) == 1 (mod q) because of Fermat's little theorem g = pow(2, (q - 1) // r, q) # find all primitive i-th roots of 1 ith_roots = [pow(g, i, q) for i inrange(r)] return [int(root * ith_root % q) for ith_root in ith_roots]
defdecrypt(c, e, p): k = gcd(e, p - 1) dp = pow(e // k, -1, p - 1) mp = pow(c, dp, p) returnlist(set(AMM(mp, k, p, True)))
p = 90015842079287188147863599089252975950229149674532065188179308662941668349067 q = 115639966729427613784046359856154071033236356854800852136894409690977637028073 e = 458759 c = 9377489940941407443668888914142468523442868076408679603369421619879641628020535221060883892082291144102991625695716628752564422493350476912185008866541091
n =
20143874513891625472763023083725333814544365923300648765753585512236262936134576226420495156390118451084859695988018681103828733472481714477702312584392200607513775527941225389450524064860609500522646820403150136601325693755011504371254765148925814568051337093873243247759130508598378247848927825303243080348476280520682747234144016534355268883431
e = 65537 c =
9099248209700870107517981697995437593126643973286742880366239649474438147247165218637687381898125380392681666447352387825995403531162271411514111581358141144178855022212666392579294107956774766000410956462804204065293225382573948622209661112442721208408763210528401826636309622296148093801229149917160087959002855064445785159864465696643561701308
from gmpy2 import gcd, invert from Crypto.Util.number import getPrime, long_to_bytes, bytes_to_long
# 仅在p域下
defdec(n, e, phi, c): d = invert(e, phi) returnpow(c, d, n)
if __name__ == "__main__": p = 297342668339361548416629796745639177971 q = 67746329937757624632404631102047546126139910162127525807142364896504844830533422758326696949629668349819199912570222748973935637740283799230746144014458722401719184655996325043824137789180083286215748548298177270209171461643103260188864468982281090005047122016817287399362453731379535534001682626445843123261
n = p * q phi = (p - 1) * (q - 1)
e = 0x10001 c = 9099248209700870107517981697995437593126643973286742880366239649474438147247165218637687381898125380392681666447352387825995403531162271411514111581358141144178855022212666392579294107956774766000410956462804204065293225382573948622209661112442721208408763210528401826636309622296148093801229149917160087959002855064445785159864465696643561701308
m = dec(n, e, p-1, c) t = 256**112 t = invert(t, p) m = m*t % p print(long_to_bytes(int(m)).decode())
defCRT(r,d): M = 1 l = len(r) for i inrange(0,l): M = d[i] * M x = 0 for i inrange(0,l): md = M//d[i] x = (x + gmpy2.invert(md, d[i]) * md *r[i] )%M returnint(M+x% M)%M
p = 109935857933867829728985398563235455481120300859311421762540858762721955038310117609456763338082237907005937380873151279351831600225270995344096532750271070807051984097524900957809427861441436796934012393707770012556604479065826879107677002380580866325868240270494148512743861326447181476633546419262340100453
defcheck(something): if long_to_bytes(int(something)).startswith(b'NCTF'): print(long_to_bytes(int(something))) returnTrue returnFalse
defCRT_threading(mps, mqs, p, q): global flag for mp, mq in itertools.product(mps, mqs): m = CRT([mp, mq], [p, q]) if check(m): print(long_to_bytes(int(m))) flag = not flag print("[-] Done.")
# step 2 while rho ** ((q - 1) // r) == 1: rho = Fq.random_element() # step 3 # step 3.1 t = 0 s = q - 1 while s % r == 0: t += 1 s //= r # step 3.2 k = 1 while (k * s + 1) % r != 0: k += 1 alpha = (k * s + 1) // r # step 3.3 a = rho ** (r ** t - 1 * s) b = delta ** (r * alpha - 1) c = rho ** s h = 1 # step 4 for i inrange(1, t): d = b ** pow(r, t - 1 - i, q - 1) j = 0if d == 1else -d.log(a) b *= (c ** r) ** j h *= c ** j c **= r
# step 5 root = int(delta ** alpha * h) ifnotall: return root # if all is True, generate all roots to return # 2 ^ (q - 1) == 1 (mod q) because of Fermat's little theorem g = pow(2, (q - 1) // r, q) # find all primitive i-th roots of 1 ith_roots = [pow(g, i, q) for i inrange(r)] return [int(root * ith_root % q) for ith_root in ith_roots]
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 _ inrange(2)] n = p * q c = pow(m, e, n)
# n = 32849718197337581823002243717057659218502519004386996660885100592872201948834155543125924395614928962750579667346279456710633774501407292473006312537723894221717638059058796679686953564471994009285384798450493756900459225040360430847240975678450171551048783818642467506711424027848778367427338647282428667393241157151675410661015044633282064056800913282016363415202171926089293431012379261585078566301060173689328363696699811123592090204578098276704877408688525618732848817623879899628629300385790344366046641825507767709276622692835393219811283244303899850483748651722336996164724553364097066493953127153066970594638491950199605713033004684970381605908909693802373826516622872100822213645899846325022476318425889580091613323747640467299866189070780620292627043349618839126919699862580579994887507733838561768581933029077488033326056066378869170169389819542928899483936705521710423905128732013121538495096959944889076705471928490092476616709838980562233255542325528398956185421193665359897664110835645928646616337700617883946369110702443135980068553511927115723157704586595844927607636003501038871748639417378062348085980873502535098755568810971926925447913858894180171498580131088992227637341857123607600275137768132347158657063692388249513 # c = 26308018356739853895382240109968894175166731283702927002165268998773708335216338997058314157717147131083296551313334042509806229853341488461087009955203854253313827608275460592785607739091992591431080342664081962030557042784864074533380701014585315663218783130162376176094773010478159362434331787279303302718098735574605469803801873109982473258207444342330633191849040553550708886593340770753064322410889048135425025715982196600650740987076486540674090923181664281515197679745907830107684777248532278645343716263686014941081417914622724906314960249945105011301731247324601620886782967217339340393853616450077105125391982689986178342417223392217085276465471102737594719932347242482670320801063191869471318313514407997326350065187904154229557706351355052446027159972546737213451422978211055778164578782156428466626894026103053360431281644645515155471301826844754338802352846095293421718249819728205538534652212984831283642472071669494851823123552827380737798609829706225744376667082534026874483482483127491533474306552210039386256062116345785870668331513725792053302188276682550672663353937781055621860101624242216671635824311412793495965628876036344731733142759495348248970313655381407241457118743532311394697763283681852908564387282605279108
代码
1 2 3 4 5 6 7 8 9 10 11 12 13
n = 32849718197337581823002243717057659218502519004386996660885100592872201948834155543125924395614928962750579667346279456710633774501407292473006312537723894221717638059058796679686953564471994009285384798450493756900459225040360430847240975678450171551048783818642467506711424027848778367427338647282428667393241157151675410661015044633282064056800913282016363415202171926089293431012379261585078566301060173689328363696699811123592090204578098276704877408688525618732848817623879899628629300385790344366046641825507767709276622692835393219811283244303899850483748651722336996164724553364097066493953127153066970594638491950199605713033004684970381605908909693802373826516622872100822213645899846325022476318425889580091613323747640467299866189070780620292627043349618839126919699862580579994887507733838561768581933029077488033326056066378869170169389819542928899483936705521710423905128732013121538495096959944889076705471928490092476616709838980562233255542325528398956185421193665359897664110835645928646616337700617883946369110702443135980068553511927115723157704586595844927607636003501038871748639417378062348085980873502535098755568810971926925447913858894180171498580131088992227637341857123607600275137768132347158657063692388249513 c = 26308018356739853895382240109968894175166731283702927002165268998773708335216338997058314157717147131083296551313334042509806229853341488461087009955203854253313827608275460592785607739091992591431080342664081962030557042784864074533380701014585315663218783130162376176094773010478159362434331787279303302718098735574605469803801873109982473258207444342330633191849040553550708886593340770753064322410889048135425025715982196600650740987076486540674090923181664281515197679745907830107684777248532278645343716263686014941081417914622724906314960249945105011301731247324601620886782967217339340393853616450077105125391982689986178342417223392217085276465471102737594719932347242482670320801063191869471318313514407997326350065187904154229557706351355052446027159972546737213451422978211055778164578782156428466626894026103053360431281644645515155471301826844754338802352846095293421718249819728205538534652212984831283642472071669494851823123552827380737798609829706225744376667082534026874483482483127491533474306552210039386256062116345785870668331513725792053302188276682550672663353937781055621860101624242216671635824311412793495965628876036344731733142759495348248970313655381407241457118743532311394697763283681852908564387282605279108 e = 0x10001 P = prod(primes)
# 这里的3是任取的 pp = pow(3, P, n) - 1 p = gcd(pp, n) q = n // int(p) assert p * q == n phi = (p - 1) * (q - 1) d = inverse_mod(e, phi) m = pow(c, d, n)
import itertools N = 32849718197337581823002243717057659218502519004386996660885100592872201948834155543125924395614928962750579667346279456710633774501407292473006312537723894221717638059058796679686953564471994009285384798450493756900459225040360430847240975678450171551048783818642467506711424027848778367427338647282428667393241157151675410661015044633282064056800913282016363415202171926089293431012379261585078566301060173689328363696699811123592090204578098276704877408688525618732848817623879899628629300385790344366046641825507767709276622692835393219811283244303899850483748651722336996164724553364097066493953127153066970594638491950199605713033004684970381605908909693802373826516622872100822213645899846325022476318425889580091613323747640467299866189070780620292627043349618839126919699862580579994887507733838561768581933029077488033326056066378869170169389819542928899483936705521710423905128732013121538495096959944889076705471928490092476616709838980562233255542325528398956185421193665359897664110835645928646616337700617883946369110702443135980068553511927115723157704586595844927607636003501038871748639417378062348085980873502535098755568810971926925447913858894180171498580131088992227637341857123607600275137768132347158657063692388249513
defPollardMethod(N: int): """ Pollard p-1 method `Parameters`: N - 要分解的大素数 `Returns`: N的一个因子 """ a = 2 for n in itertools.count(2): a = pow(a, n, N) g = gcd(a - 1, N) if g == 1: continue elif g == N: a += 1 else: return g
N = 264048827496427248021277383801027180195275776366915828865010362454006394906519399441496561006668252031429735502465174250525698696973129422193405161920872162928097673289330345041221985548078586423910246601720647996170161319016119241836415788315729493164331517547663558380515400720081995290120793014108439083514403659082115510258023834737471488528527557960636984676435543300074504679264476413252780514962473070445293528877641502742438571110744667739728450283295649865745629276142949963507003094791773183928894536793857609738113546410753895719242547720815692998871947957214118354127328586542848234994500987288641595105
代码
1 2 3 4 5 6 7 8 9 10 11
N = 264048827496427248021277383801027180195275776366915828865010362454006394906519399441496561006668252031429735502465174250525698696973129422193405161920872162928097673289330345041221985548078586423910246601720647996170161319016119241836415788315729493164331517547663558380515400720081995290120793014108439083514403659082115510258023834737471488528527557960636984676435543300074504679264476413252780514962473070445293528877641502742438571110744667739728450283295649865745629276142949963507003094791773183928894536793857609738113546410753895719242547720815692998871947957214118354127328586542848234994500987288641595105 base = 11
P.<x> = ZZ[] f = P(N.digits(base)) # (x^295 + 2*x^249 + x^196 + 1) * (x^295 + 2*x^281 + 2*x^192 + x^100 + 2*x^37 + 1) F_factor = factor(f) factors = [] for fac in F_factor: factors.append(fac[0](base)) print(factors)
from Crypto.Util.number import getPrime from Crypto.Util.Padding import pad import random
p = getPrime(1024) q = getPrime(1024) n = p * q e = 5
flag = b'flag{qsdz_1s_yyds_qsdz_1s_yyds}' flag = pad(flag, 48) m = [int.from_bytes(flag[i * 16:i * 16 + 16]) for i inrange(3)] S = sum(m) % n cnt = len(m) A = [random.getrandbits(16) for i inrange(cnt)] B = [random.getrandbits(32) for i inrange(cnt)] C = [random.getrandbits(32) for i inrange(cnt)] Cs = [int(pow((A[i] * m[i]**2 + B[i] * m[i] + C[i]), e, n)) for i inrange(cnt)] print(f'{S = }') print(f'{A = }') print(f'{B = }') print(f'{C = }') print(f'{e = }') print(f'{n = }') print(f'{Cs = }')
