easyrsa

点击此处获得更好的阅读体验

---

WriteUp来源

https://xz.aliyun.com/t/8581

题目考点

• RSA

解题思路

这道题首先将加密脚本给加密了,可以很明显的看出是python脚本的仿射加密

通过查找关键词可以对比出a = 9,b = 9,从而解出加密脚本

这道题一共有三个rsa的问题,对应的思路如下:

• hint1 = 2 * d + 246810 * e* phi，根据数论知识,其实只要d满足e * dmodϕ(n)=1即可解密，所以在这里d = hint1 // 2

• 解出的q非素数,把q分解成素数积来求得phi

• 穷据两位十进制数字达到coppersmith攻击最低攻击条件

#!/usr/bin/python
import gmpy2
from Crypto.Util.number import long_to_bytes
import math
n = 10050095014547257781432719892909820612730955980465259676378711053379530637537082959157449310691856567584792956476780977871348290765339769265796235196183464082153542864869953748019765139619014752579378866972354738500054872580260903258315293588496063613299656519940131695232458799137629873477475091085854962677524091351680654318535417344913749322340318860437103597983101958967342493037991934758199221146242955689392875557192192462927253635018175615991531184323989958707271442555251694945958064367263082416655380103916187441214474502905504694440020491633862067243768930954759333735863069851757070183172950390134463839187
c = 522627051172673216607019738378749874116772877858344748349627321977492158105699887369893079581450048789131578556338186004983533975454988450450635141267157135506032849129152411194539350100279698888357898902460651973610161382266600081865609650174137113252711515464274593530115825189780860732147803369868525723790644619452538755225868382505974710418995847979384726953915873857530098330095151094837190566851416540540805185485212577333604309698822785682707412587829684108913753204398552196441996201678339688766979634246337855516220753995430266970473808724410357458278585135750810810484678948146374963838334596646926215341
hint = 134805774328615624446574490322803283547316698647214138487576352482438867186094276263735342558169004773286779632939369099910639984165263724781958841009573156241531958373198729926012152201548649349842790727259831232277600944618096069835436884888782994513452252257103877595707828731260669076400456300668581565291455061609385003064649522735776446930209884653223939689686840631001863143579575759834304817613040932998629846110770749941179601474484275548912570668460216633586988225562794026430881265344731575650165992321629617982004131413202026628777742093026476064486873565664625105013298396598413667761372217260994853420062861590358
d = hint // 2
q = gmpy2.powmod(c,d,n)

# ------------------
n = 133561991523711714238641512987809330530212246892569593026319411449791084194115873781301422593495806927875828290629679020098834182528012835469352471635087375406306534880352693134486855968468946334439553553593196889196239169351375517588892769598963002098115826389220099548938169095670740942251209102500450728442583559710183771974489284632651296188035458586935211952691589627681567274801028577256215269233875203212438263987034556969968774119389693056239796736659926866707857937025200924828822267781445721099763436020785585453958594470906716195030613615725126057391084801585533926767137218524047259398886392592317910204988634868663634415285507325190415658931169841182499733179254162060738994027842088553562013488445789594342451823783136881968032197575016845492231433684884872631894561254381663562267075103417879327236182565223877901300392217967589154857009356640377622996801781797109089687661697856930394706016954531077165127402008444818092498106642068414208190583373314287381712963712098566595399301400378116274132918572709221391531621228936206630829355801192700264684469488261781954165940553346889395507153750291402535330239420975542926664420153925171757944018621411265539452424569343708318070259746118326558005521868356304582694159507379335214599839668805877215983938986674084063185863612335339836810044252829401409522709997562887276661672718820881541500852400369184737236082178767653725044900394959369367604992512713490494168594433000695046297712977059205623777990102604073885527049867682390577577616773090662829024271568456346362315351643767420198116229892060385453123572533267805396437865025639093881944841521458804810097550625853182396288247815370818578103543117466070812804267915674186488979548392193291727228018246788487524292081389142018151246889408421936865224469589631518283230229213787648552632437566756058034131355439709320923876063030896228165897498746898125821639893238387694549304110003941329763552493326245073779912107372271854798616245416264801377068163622812994786201580895459712414134184992440395336131037558976058298521312536969408724436512019410835904564817724243688308776888170183074838453466914170790840559860531933430176605716828492670093771129301541861534595181565621644268739349035133062776852304594204220291667924128313579203359827093150911871520605180797438668872585571501531844999598674037998642821148417473110716470439750642781609483016636419373004760601783594025036152924259863627732874940148083408474700265895269165869619971810103499607445649821
p = 689159326758330864205993810270646658558112329195746149991184055909755461246626153920231796960903018393806410715812453949253930576368274228434916375544579284365205241766136566047482065208442992856658212126772417415403473480889927931481129434854332858754668120563818975006384512615022532233244596546830392476321031156328699572283946257730515089543367929326280871305776349305346159311591820455943842203357066465523558715870586535188343603460826231817622511283563179065036619023415848694281294463836320838105950552498785365535923041927491743402053568747113507098917091780797009380675587381805253390649630338055131031679595664055361678114747608302944715308343764678875659039394225950479683967885912291399162609094622980318391045105733088508798371414996479107970975717563552614856114065668728607215268431341079233630995168600896375314067716366181300081684353583326214062788182429536300917720999423489104723824360299238754986351169209709892739317096741609428484854087163771300777717883057028145424827875496235567904291417092378448353222179114362314382900648079547647848024440220204768433974038004942869937932015294078073975703156613070125753344841550872429670559866184492945262960524545894823245933714684747784492095876370443994948425495841
c = 65553658155452064459040687299632299415295760116470555100400688788937893101658136830409082198753928673469636810831761104117535054304536941814523449491308187105740319828511969750359402834799486354958723098881095067882833993358468923611118977258293638107874383059048015701807718209929028151240509801801995570592890519253676774278321334154528938199389248563657673061299152526380072934917964488153875744843855913524788571997024947738868563951687976817548296078497817264410193882661874749304071168979787307490320366615899942861059615405569154961435894469325778407081182151320629413711622905703628430999201763846682516985530373643176026602901129520439581385946775511292435206913016381293219606333035648747877313424616408338829137581998558399694071257787294948211441360283876078405831210625321012072477187438320944119825970347654743794743846351762763177440045084761025728597526592892602263484022280653040195670941221493307430623213388669939114424884078502946247136016528925968280034099568454876076717790529204207317485416329062672971939549478648687894958552760953682796211975576320713576155031581257782352223857605149825435939889497465805857339911597479498085071301601506276220487493620870555545057189236870008182212284992968466451864806648279032294546676543599599279519394341289357968292292966055189578253350591765186079486142930848439238134776982658066494378507873003509820326863340562093906137812952544399266821679905073464535234547335867090392493005792528534561846391285698943396889671437127470587837989050518266365099789392584686615435440486086402941357614369171354355307532351370775920044953381482310949663868493911752104873824099597326393857349237228788875273525189373323552519106738497767546337587947368062413334887230166285909705065920918078052826480092129173127887307158867274895914733110276134124505178182548094607594799978378381804502097507167978950926067243870989514735314054362049917668015341349933704885009878192354865067520219676784278082055728039064858769077997521541853184489175120623176481708269464933868222226748491078319156602229948646960513946846417957356535995079525993783278312017766715177078804065822913241465133977233398851120059496221650357891946344151601586169979516826622503491746992282716591488199657450776596383692706657692673860134555990821730412919497018889046615548520878486492644159735144935329502984929679831356967030870226422768447430410031028770529758721438528263719267616233686813781828066547393953352033364851486926368090757420184816634373721

r = (n // p )// q
e = 65537
assert r*p*q == n

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

load("coppersmith.sage")
N = 14857387925078594782296815160632343246361073432459148990826882280149636079353743233970188012712079179396872746334143946166398665205889211414809061990804629906990919975187761209638578624750977626427334126665295876888197889611807587476285991599511809796600855689969285611439780660503760599419522224129074956376232480894299044645423966132497814477710701209588359243945406653547034819927990978087967107865071898215805154003530311865483912924517801551052430227039259201082691698480830966567550828053196299423168934840697637891311424286534363837640448614727396254288829197614805073711893711252067987576745683317789020760081L

c = 14035143725862612299576867857272911865951893239411969382153274945929406881665641140566462510177132511558933111728871930062074990934496715765999564244916409345156132996227113853067808126894818934327468582686975383715892108247084995817427624992232755966398834682079985297050358462588989699096264155802168300026093598601350106309023915300973067720164567785360383234519093637882582163398344514810028120555511836375795523327469278186235781844951253058134566846816114359878325011207064300185611905609820210904126312524631330083758585084521500322528017455972299008481301204209945411774541553636405290572228575790342839240414L
e = 5

#相差52位
m_start = 11239443406846515682004397310032293056196968050880696884154193656922259582646354037672076691689208477252910368708578177585615543361661522949580970926775441873118707711939955434559752380028881505457190152150478041765407640575502385319246850488337861927516356807100066882854088505873269444400308838674080495033363033991690519164414435127535585042743674610057871427247713644547353814013986225161074642240309387099685117406015368485154286173113005157000515600312732288515034433615484030112726976498694980213882676667079898254165734852012201534408980237760171665298653255766622300299965621344582683558980205175837414319653422202527631026998128129244251471772428535748417136102640398417683727976117490109918895485047000000000000000000000000000000000000000000000000000000
m_end = 11239443406846515682004397310032293056196968050880696884154193656922259582646354037672076691689208477252910368708578177585615543361661522949580970926775441873118707711939955434559752380028881505457190152150478041765407640575502385319246850488337861927516356807100066882854088505873269444400308838674080495033363033991690519164414435127535585042743674610057871427247713644547353814013986225161074642240309387099685117406015368485154286173113005157000515600312732288515034433615484030112726976498694980213882676667079898254165734852012201534408980237760171665298653255766622300299965621344582683558980205175837414319653422202527631026998128129244251471772428535748417136102640398417683727976117490109918895485047990000000000000000000000000000000000000000000000000000

step = 10000000000000000000000000000000000000000000000000000

for m in range(m_start,m_end,step):
    try:
        ZmodN = Zmod(N)
        P.<x> = PolynomialRing(ZmodN)
        f = (m + x)^e - c
        dd = f.degree()
        beta = 1
        epsilon = beta / 7
        mm = ceil(beta**2 / (dd * epsilon))
        tt = floor(dd * mm * ((1/beta) - 1))
        XX = ceil(N**((beta**2/dd) - epsilon))
        roots = coppersmith_howgrave_univariate(f, N, beta, mm, tt, XX)
        print(bytes.fromhex(hex(m+roots[0])[2:]))
        break
    except:
        continue

Flag