RSSSSSA

平台   Crypto   已通过

题目作者: 树木有点绿

一　　血: ‌‌‌‌‌volcano

一血奖励: 3金币

解　　决: 543

提　　示:

描　　述: 这是一个非常简单的RSA

附　　件: 下载

站长题解:

import libnum


#生成随机素数
def rsa_def(e, m):
    p = libnum.generate_prime(1024)
    q = libnum.generate_prime(1024)
    #字符串转数字
    m = libnum.s2n(m)
    n = p * q
    c = pow(m,e,n)
    n_lt.append(n)
    c_lt.append(c)

n_lt = []
c_lt = []
e = 23
m = 'flag{2cb2eb4b2c7fdf4e94e10344be856446}'
for i in range(7):
    rsa_def(e,m)

print("e = ", e)
print("n = ", n_lt)
print("c = ", c_lt)




# 解密脚本1
from gmpy2 import invert, gcd, iroot

def op(x):
    res = 1
    for i in x:
        res *= i
    return res

def CRT(m, a):
    assert (len(m) == len(a))
    M = op(m)
    sum = 0
    for m, a in zip(m, a):
        Mi = M // m
        ti = invert(Mi, m)
        sum += a * ti * Mi
    return sum % M

def GCRT(m, a):
    assert (len(m) == len(a))
    curm, cura = m[0], a[0]
    for m, a in zip(m[1:], a[1:]):
        d = gcd(curm, m)
        c = a - cura
        assert (c % d == 0)
        K = c // d * invert(curm // d, m // d)
        cura += curm * K
        curm = curm * m // d
    return cura % curm


e = 29
n = [30327806559308143170251580709344293187241377730282921872781575442079759214585250363018838833645033147048274099882927502135822532658361986843089038971809699440265951177983452623836631182131316783838858410002798162604085127069663694047960859197275399255233610031615817404372364349637055800705223698180870067436988096453852212302215116141417320041306889953482862584091194471138823690888819261753453934793173621702326066309884946089600954181869152898879815596750534117681142535676578782280108274188679221706983417414010745084946761574988283779791817969892384961589321416872995532377690950727835973399647956491090102555409, 21201945432185822273274384690776217497058902883149769388717005633136179247488270702594230376181288768858812012728332675867062647184506694171059959523739358150427193785288862325490483145892589156285417654675409522395461778047750713685913892924628709666682898716590870448590373784915689173142592010032611604863227130433544024508077340982534157235155525782725897976772958969688875400789351919632303930452916408599309209320071861151825269791353531470198408880292345886431587538581009065968803858039954194364023302947597373427552936469472639511930960050054058074397349282354505376836608524919420271358644040625272611834141, 22066722902445052583751020956045490471001229482392491124491605354676847417172264621341464938604744547196288089839857467414993454346487337649230414610787992018112868327537703873968574017809192037003789320466268844177192403612544118218277599434212247848173311593650429895564484864389688450385022488374534161927558878171030816097844863947341831453646609936063871558801826304657779664413322335636640541461530342335752307248094073705764721946570652851209785138013258495645549732438232440380725327458972312411697319199017195198686877941387699409525165884596929130086232751883272627080260637468553554114550895128931332556731, 22201854184449819277142185267444382273897841368693102934683821764656962395743826157719287435432760269046740745554089225345079284556882054478011586504345324432037743900501514661174050074095054738909658615769021337525829263909874107830437595890817773992121956416657353703784722839247395770361048793369307710079965231303120658766595423843609770605074056488132086912631857454296414163240447182566834479775710868231123976843543989150070863055009604342636257860806777650229259057896505901924417615469387152636729167180379751548900559610148369495057752373605259839922528981148145028120068953655171238962097381144518051147647, 23083840233620992224264526611828536460163558999895002497626591923027006640369297896797243966752151170505775381864181314027021495993588967339108820520528972816379841269197877268187639445751437743759925034716110259215833511647315164717603384871571434294945499053929574035111488209616165563966647430661297795173473421242368063748311843339991310650516321423828411278303633083702771322000349673510635860126984256969661571754688788776209025080804889751723316765593984981235995307564443348633486717797511234178142487310778666548407208267425343907584339092352000989025888560813696453621147789642611872568202165905056714548393, 23218822553600624275851570918327600443202628196986792799225558073420180848161120578874626283971398879263850567245985782927539083923897342980706479709569579629418591343916765139087666874177802508777776627037319228004136490718510415593236575453393195566284309655647871922536044561206875353630359295663312099218766232095780724182736486077598036512073334536846225792741359530446751954255489310204542643379502811042809497521182466190499994814904710462792494798490083908932248164953870969612782940162469775904944210724177461134898671189252356405455733124848794067548040801451291259009951270923040763880342053172756399581161, 15537621716770448782502134748692657546482394987891814167799488723003580500457315182184780510271452262025473252065075152671351786862081823121704341999623090322622893909472600153140827895279392030437881151726836273881483138361166633444702898613389403354997826623821941237846412179222285546753657710048063757827302566538233983504273873252358216792306525072453406699162260561047287090285490165275142295462447156551127598082848917540871566229207376989948730655600666112133543582179171414297735210520886697976984424647098383547804465263579778326244367614695099540268893495474464880528394459062149362976029449912614166126761]
c = [6046094125227689870033870506917812276305436053796436442363822401342062726188042561670757795460948077415972706427946093618320717744079441259077874700893204459036501380012163686628771354515016380758564221578468509762354597066344146672996248499856111282865676568650895987550682149774776905594210993204175895358464315828610392955454920047755436033052407392579110231386427222684373442110938309074563238848319417352567379700597401198483471415807726938645013860932841996827926718400267742249916874079269259123794751964917045940979213140450626289795549071713337129466329394763935853156424248229732551544822323764365359825485, 5845552286578226566598806127534836409831300694599972428266617271147189508983086233231766595846029052663890341733882461545982026551439575193608090205669127833427025577685774642780332691084053603909859869193052420285065348378657385164191605378649460509586471212644006322411828860570889277856429353408252263239239828396565949357208821626888694650997167695580553398057963048443171407094467284923234982142222808183498767632834628360161922076588397865384233638848062174627983119799111822718694488311274624762022407317556646065445367315918249540635444036633880194363965914260210883151429898423440605220973034396774973125632, 15903392352203298605877945674465143966769721737532685945162112598239954843499500918942681985964024463454447115748161245918002002655617193080894539813344429249706695035313266913563071057661003650948948239324748886703222675088558181086755212852968181312257303494407773363350004731534848190264255069536036133029778028229221293469762527695954265711168400217935692988501544247020837424584759831204521029707454822146517072769268420888169838807185669690437151962231817248323732857623620673773191557407520247312964435867860663874242179929967218588152288202476576081222176785925045418916462303292404117304143574686336544149629, 9669717038949021329020108540640237663067756966280810642417630134992373130879787768749181913381401511774773393506456589516952861294673561533008751071662723277608866325874519278507984666760149692092823573606053373801025601646795839172562607132726532904679698936251789947925155456255628127932509101557747423647220724762995217296493861282238350001729340519429193525028741636093329396359178973155083792632330011484299821599210312002159965537430090985352568581714148228760952230630659713444400585630168629530652207170759737992501963831886075598264013355139219445863531555822055994574891400262563108434859568651780227557975, 7914090642636266923294026791261427849044695562739254282481166732020837928041454353817133871854948761397284836379753705671724947241779482598081203575216043223216563037754382992648875469848870865515423794755447621640988585802308628444956443228403796584499863761840901610073862093944795357445536465073500157568848798543720484354000858578319564737563857043549861785205215491288782410945294230845471220683129677585701046542907136512616807429274294758158965956146717352157078092334387660733724142855367118044193694310952976603009653011262032422467651663006916850935081716939520365535884320814471253649009945816472423048447, 11988310991395265980081594718856590638441631362665678269045945813797124375621091172731397011814305000162712601455584541005431841875115788140698346738764417691906578333694503756521160780120138569779573589730959145320537390172280626510886154211649716255438845119004751973530199741765756641003306339421117668796100661313571568100843237996562080095649017634551873879219917272328238629844657368364890324594141674498942544827428056492747949043332622214494766621587698339619576784948756333563714427524714670635509179215190783959390410232309595570890592221268445440689742423642145049491551659385729937300897657450196112613804, 13758385300968829470189169449584800778823082473607121434049610051116374924292341244419430157132107552964735632092568046439074559673147580828760077490267517852677562615547566840913903686439783964549498803731879665085652815249977620067028187162008373600851339874309707587214786555705953533197711132611955125553398328736012543728815790951625456481002420603689802771155816294782083229750332438335093308789359642911367376579780093093577929312234635979675059828551040384269343053231849182709709271027703443106568079145606579815607660891685636327906452992083196131013003312334278998794497774078191519059014857427818993752773]


m = CRT(n, c)
m1 = iroot(m, e)  # 开e次方
print(m1)
print(libnum.n2s(int(m1[0])).decode())


# 解密脚本2
import binascii
from functools import reduce


def CRT2(mi, ai):
    assert(reduce(gcd, mi)==1)
    assert (isinstance(mi, list) and isinstance(ai, list))
    M = reduce(lambda x, y: x * y, mi)
    ai_ti_Mi = [a * (M // m) * invert(M // m, m) for (m, a) in zip(mi, ai)]
    return reduce(lambda x, y: x + y, ai_ti_Mi) % M


m = iroot(CRT2(n, c), e)[0]
print(m)
print(libnum.n2s(int(m)).decode())

去做题