本次SCTF的密码学是简单的RSA套餐，涵盖了6种RSA的攻击方法
Code 100
本题有三层，每层给了公钥和密文，和下一层的压缩包，明文为压缩包的密码
第一层和第二层都比较简单，N都可以用工具质因数分解，工具有yafu、sage, 在线的有https://cloud.sagemath.com/
第一层的原理是，其中一个素数太小，这样从小素数开始遍历，很快就能质因数分解出N，第二层的原理是两个素数是相邻的，这样也很容易就被爆破出来了
能分解出p和q，之后的就很简单了，$\phi(N) = (p - 1)*(q - 1)$，通过扩展欧几里得可以计算出d
1
2
3
| from gmpy2 import invert
phiN = (p - 1) * (q - 1)
d = invert(e, phiN)
|
不过并不能通过$c^d\ mod\ N = m$，算出明文，因为在加密的过程中进行了padding，因为我不会用python解padding，所以只好用openssl了，首先生成密钥
1
2
3
4
5
| from Crypto.PublicKey import RSA
a = (n, e, d, p, q)
b = RSA.construct(a)
s = b.exportKey('PEM')
open('/tmp/pri.pem', 'w').write(s)
|
第一层是使用oaep，所以
1
2
| $ openssl rsautl -decrypt -inkey pri.pem -in test1 -oaep
# test1是密文b64decode后的数据
|
第二层用的是默认的pkcs，
1
| $ openssl rsautl -decrypt -inkey pri.pem -in test1
|
第三层发现e特别大，使用的是wiener-attack，在github上找了个脚本https://github.com/pablocelayes/rsa-wiener-attack
解出d，然后可以通过$c^d\ mod\ N$求出明文
Code150
这题很简单，只有一层，给了流量包，拖了两个N(N1, N2)出来，然后求最大公约数gcd(N1, N2) != 1，所以N被质因数分解了，然后跟上面一样，求出d，算出明文。
Code 300
这题有两层，第一层给的N是2048bits，e=3，如果m < N/3则$d = m^3$，直接把d开三次方就是第一层的明文了
第二个同样也是给了一个流量包，有30条公钥，e = 19，使用的是中国剩余定理，随便取19个公钥，用python写了个脚本
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
| #!/usr/bin/env python
# -*- coding:utf-8 -*-
from gmpy2 import invert, gcd
n = [
21778816622407043254249033744556437773178718344170907687035355752306254181495272254316323076827432323583279284697609943296234700945010885010381052459024155936090811012664924674758219163065019349740707282354505096608107707774970709715259835448587834080152409078047162951805940071358655938727249679105305351838950073539149057650448964397736279148746703675407495243942505041731104580156762842345374978325029947055323567120523592936170640156611551704828034384851988154353272897487218723570180022092379408219114849763765186588476489924721044926152006318666687949095907516827647042434514271847608156543261745856327152256691,
16903196746534976770297193591563118819340996326353278926932894774572875445074235633598238073286562040907331827987129504332575088363961056320711957070361568300931751447818086187098450831958791194454471761207974960285694400991565796076896861484262801877894234189007108688232929103575715501208714450050820596757093532908538335247758665436735062990069823263343612343383280128868367115993204155509197451034689222789081909649433189803691801997724286399861059723879464142218791577045451380036235131262854852861711356480129365121825413631051962999057782796860262353799309363207995917585708071851074274505668412220771866627801,
28265280613183354342105753166996328090546389493099576671064332905506043149645894359529530572985221453256974871551423452437262179254048995385871426911106523040024082014701860288597240859367709958593683404815121262284405370456892785825244621855179713916387058136808290106777122592782679759913015048141455589449020109912456204732596642195119782747444413318147656712489309539304507463058220125712352312270109971524224764775787216566974066782153169186108327462634247269028163635556628016922590640886497451631819173964909716933392801888324681183442906718285722236884230908714776131247765432042336528688391266197013577846933,
24987127899477465012251233743493253536476854495637178599192050225313102219411387898487200182441114487612034816488014846231399460666971909474486058085384163710434277132512228943824562960928753528438748273225337688628804876346934893738809200953670621279519453757412491449591854561780627642156687194962761756188282130022320565958645871385780190162615031780472674474233554299969022151520347624742464620679084328782555875295855846135397397113343536139827427341184253483944102522989539698394227074217940278304502858391155867844668912171244350562320306827896547118036618397962042775133094735525961981341552292221448084885029,
20690588543759338459201261102131523557602951858621022352768878495764772818047444561085946463647026323512505467898486038702296544581574454427913943957312980485120682984328258470676756700031559606051601837978676090075103759061046354026481363302764050167452089628379324207470363334371464572866980379277784494909108912432265324937412023179282154446352432584206636315270087668925211674657165676558801771127073793675007651877248218291179047124458484980007843300303269623821337776079296736563393494962515203685309350731743104371337237221338067550042391180955737666453436685882807146647050068939961249283782794859263934790927,
16517102081052861630895919001217675526698277369300591711866049102573903641338088651465353677681314133196137354591046807286864279671925133798556675780456365747859903691818373002538419664235941077881320873723974912890141942864109366960284815031822877720076646042209075936969869701929261677727681050077163026469462157471618274966461347360748386423007148375581277546370022280825631242730771828201301160075215196139318450096889249372085484891067811333463883782678293168327177450855394281994969889305548254268708625415414795510941577246484314728636995608221724256782771789486658328851046459586540232884627529177340560416993,
23846860290279092907572444079539617462214354239782236629759070773513973525414800313619141664302186747496495971163746242055682769265827639472645512416038516482082192479180022255538780293810541273933187169499865844979861261417193700451844441299094590593715164464011149534562230605044072398232865628048059788633187389023568417475139388654021193716658660041159730755563837795152394878078579534655463322616283839623641180779934135529522581271802799149690558550140547741565135720412155964520008772101738405928224251101453422360053273769367642925204442743550811319417756071808630071840203875705299338612909277917097442575231,
17566701282456258503708647404558041579376753416636895921624574676679101724033623273314113990594123807428022978359642275344892917569831939503189948668240865309669039814491983430907110218013111893576410298548024847128844676202137898746346628853860982276196072572409817530124631239728733042716676159813363682748753083182297029995941313117294252250686136554964244869449490234400819447482806975167157303480233831491591302798414444021786972185652092240434726936513164112181591526851025405006672553646267337903731497655811302924232073336996144108764372355652364792853587376409404275388013071072585640297921892859159400948323,
16253121383768278209005558577055644569117707124854929186667128310606493315013449858902615940095488323028876191616816961215480161502334848550714559842262203333048521009972976254796089176241431933391814530903987798419098078087110325298127023185881308297696190844006356371502958261262318737874080358501446648868436314810687974775378172524379297271535579000788274835896943322448320754626535308836129262616406664292901764961851722791991015882750059327988224491748375219523130042075320130650865135318796823056748272833680628813950407501372466385030092017640922132792751107909729923267741621440199097930132480628796900772029,
20290309021976181378150079070647362877361051642116884020698310582404348426365349349830932277074553597811144356035164416874783743981763606447828375623172664133086570212409720630779251662198484608733581283249766121177416927096509366175689816558284636310339765253094030229680886254669960511903436585522016222678724597374152265027493130428700298457508264585197242398693292101535859643883683283228422929797265173483141156963526966092200813029155535719102888182314267564367377779201639949508213735381237773042753101422482552209042450075752883511314469026255991162957376905635040303277884398802599054812153590799774042488237,
20259407522505114352438066790031189161692762499783918150615320203040060613651670031363001854418241949806197697617226051714447759568062273100011096875597755138510617995005919992091359670438072021331669362289193281360914280630669617706120960853381676622726602146361520387706665131232782238093270978205858281738902665202342179262150897459523695977783336806799817685658837013961068870176413359582541169367864085705134004595535049333058874635763188301138178673153768451934569823185195476045661392099691197429028316750422385531970917919762595412998928711638811089289412827922269444823536467731873971772055257114762319315393,
24318293739308347213079240931318897629475758007636953845697423973047760974896821730716872997882728166077874860101084256173936300391518418843018259609362471240020891953344922995571854332425076721361761155823416339736617753479873947815911700571886068424319666101274062537135986686198448291523526831919231309046418709526942081443652930546060758807699063472901121389294694164314428552216115807784803759664471770162896322173399815832732844819985897349926942832673618305532813094961669876922754219436080392413448963260311884490822861732752909321638280022645654810271403290958260903318384943003470764808099607444730775850977,
16767369591676471537411283105560692097106856689402131801972215792616408134559976771743130058361434086714770802148737506939664570683450741935689264391158401406372136118114570763009411773231927726730263665758441518136374811604790203589734839203990618958929058849509041656812300142186514602133644716549714328026432640542797308159792476463973843503510250484074033909180332466382455960693392142248674005373879029496304626751064305166382888538959190215229722452450797037929073904543004398559319989715734497042785049819377997233813308055108035958732985392827704742206908811830255998822273272225412690773092101546168169226819,
21648683502998984705866045484544947641100049872713930000863461784192971714383405382729380364813442059921949950269832215961206992010283135651557788608887439348339240389301966222474702327024746998115526572416766189380119518840255063173477318112489526882961355833769916730074219503525366167101177618366403515625636383142156974729031570176443105921652237316791996836488270564442297923460061659842496051191955963907318267799798504658035464886798097464290990706264173092815972652707781598809590103021822291959985975312561624827085690133099378114061849520500494476184201456743692991277561917289123442703987077003912051254473,
20724767138767480789498994298180270826474867340264049260163785892907430402804218092022338747569186731211486624552452459080681333244461257729270209985208605897018675854065012585533850704650069878363901187359565209404784010532316397910749437579359276642165787498762432075769088961395447855627224959523061844885375539902930820684607575955490491526386161219430904177417445996609987094669288549224732682905930495022194205987692082118583747810531893061045357968782689580940621512543149340026440955519419499409282989934863220231218154774655263793622174595342915351690552470553775562387235255548900912535073932090872225703057,
17212295439640377055688217979984966188585299016873359234729084493184304625628968472723004154564887269917061351983063776908774119426411714704687892967543301227423731385323880537283235940428456928620552423667793662090989179432831677965493935878867379869711402693579656408872825837818475666783698699885664597654744848985400925132991151305007305023587591892065687701737374884121128600523652409581330661535968924899805804262941682210140900815439466983734237563778235377066739355624114219934834825916708748496082834506423403378555482105722324867025910662705141921743047391704562848651183325027149054432694683572014622359313,
23472084745304537438905071529263024519722889277035896476683227577770819544818596032060798859721968043031781686415577272011705809230515019335765899132906313745385382557516479043323335745414952409295722882945395961430938606533533929117934551622303375595866433725626122966500728243718957556236260244044649471741774062107054178507503595912884900120045195140751307319039397273925472618110765991503036390880137235899571639920592610193895790603572008709664626744807262201364463031075469046249809975209872344454149481525610270451281388871236274366093215907300750793051152749369584542316120901131748833946863340674324510840113,
16966451712809405570019731700441708658117157522172037602215253538847704156034447243308997644993188593978969328060823028085625093394067251034019534730107585935365736610970376571337190453031629257247350588200661044866750469751891255339636079377813918834503866490352194434851419800977023620974886628642857558663003924383379088864349155389799474130189328454296627295593123465297469526418130015195915305128989852466829730138443688054686459477827471793857648148054429381404542122378207762553439877527124241535549595614223333073179859071395110332611349804722107130361840138060206231273618825678177660378229205324373334941671,
16371772865482869886487545751875918720227349410350898523261337902433007760724960134070658859447185756919127716802819962207343430388160650608047149901674641208010454873466609600454044683586479844130564525332317252829669954436437422430190710090213393780435449488077843816300027728531084047622538708365772411064244675667055162907660820768433907282749095458015341570802297559287990440496065051486970127291015435906143328670495764979798317390225405587270445353337087497780300666784521757559677764504161208852136474658460018703444718680426309315497887622354795698567555861658547811403340467546724028577910903558187895025517,
]
C = [
0x36a66571751faf3bbf6ad760adbcd1be123d2ab526d2fbf6697ec38c7d4ee7d709d8ab3f154092410f46ae18ac75aa32ec9393a98385cd8d8df3b5a15eeccb2637b353f6808fd39e11faf2b742eb0597f8e7a977196171b031c076140cb05c771d8df2f81d8b904e8bf579da0e568fa67d0a94a7607a002c456824e7ea71df895f1967b12ac36eade287589fd556c71520d2dfdb1a8663dcae615cc40be1ff82ae42ae617db75bb1dd88235fd698b53921a42fa6390854eb1393d24341582ce83bd690ea12d2697bc929a77b51adb04131baee52050340be9a2be6eaf795b6877bcc22d5d8cce3829485340b641585ba3ad169850e780562467fbfb09f4f5235,
0x51bd5b18e527dc109cd202f39841bb39422dcc1f566f59da4c623d7166730dded90963c825ba6300c0dab181f69f12ba40955e68e6040f794ee642aa26acf437ce382a0ebdae8d3c77398a01f55eb2593d243e991427197f6166b117e8bdfa3164d99e5713f18d64947c36afba69d0c9208e79815af20cb4dd201bfcacd485e8cc98cbeee1b75d6d2b1ad81276647b6f7b2137cd9ff9e2594b9ec8952fc2d184ba69e8a17fa5dc865b6e96552d81750e85ef427ad184b2efc5534fb6f70f8d096b3029dd71349b571fa1997fd14002625cbea894811c7bf8f582dba0ec9d03edbf25517179bb7f20288cc2e2ab0b038185ac525e891c15c151d47a14886f947,
0x8df94ca10d136659aab94677d5826184addcef8cc563009822519b157c368d17434b9b6fa08ad783003d0aafc6370938e6c795d93968cf094260ef05f1f65b03be9aef4d0e8b4e5ef8bf9182e382b08a38c04bb448097eb1ee93bd9ddd6abe39f2f356ffae8470f7d63edea2c87b7b7766c57e24086f59825f5f50d5ed7443adfb26dd3bbdf662cbf082a9415b73a8c81581272a4b8f75f656ec03370e53fc88382e842a75f329c510aa09c647afde2fcee7a5924806a4f7b57cb0ed769c4db41f35e48c5812fd75315697e936fdeacd366c851e06b30050cd93205c4fb233233990fc2b5a0c9cd2aee58209fc04c6e782f2639d51fb43d7952b2f8afc1a4403,
0xbe73713e7928b1970d6dd531e0c9a6a3884bef82c3a39a043f226e88cfe54a3dc28c515893463e1039a14e49c8d27154544f9f3f8ff4d750b56ad41ef3c5b1710e889a4d8845722c6588f51f2bf601a0b816489b6afa23e909d4201b570788e0cae3ab521ae2ae507a02a5af46036c496459bc86f34a141fad1802d578c645164b5c0fb91978b07efdb8b9036028d4ea21b4719eae9caf6247daa9c9639f7b79521c7feaf1e9b22852f32f91f93631e03eb7c091d3ae27858faea04481a1404c543b13c9ffef06326d7d6f67db7f05f91611a3d185fb6fc1e1fb07b01c83e46c84495a252ba4eb0aa3a148ca4b6dc61492eb71e3b5bf7473595ed69841ce0b94,
0x321516de98f8d6584adb01d5783d13cee2daf74f2285c693debe3a264c0b9a637b42c17a61a3870c70acdfdcbb3ebe49fb57c40079d4f82fe4051b5374545562baa12d894baa66016c4d025ace559bd7b5d658d70e0e7db5a24a212a48a5e9ba44dc091c4846f60509fe00b780db6101b73cfc2492be2e75bf9e82b727ab6b459df8280e83e59119795a82acd53e982fa3ad82ab80a4213728c41808d53cc75e2a19801943ff1af19e85aaffb1b29a41c0af54ca44335d611713e5ec6ff38675de8704fa2ddaad90b50cf4553174a9ae7fd61e72c5cc8a77df159a21d67539e92ff702ddef11c91eb39c247355426f22f87de33f8d65e5589553405f50a78c84,
0x52cc422ae1012a854e0d29b9b1da6e68ef3a3fa6b8d7551c1c664875e277149411244279eddcf9656fe182c4bfadb33d2d917e7faa580c517d7960e9934813185331e9c9fa3698fa9de3f8aad5786249fc0505db05f01c43dc0dac422c51114aabc5d0451a921e36e47d9c4654574076dc04d2778ff9bcaa7ed3be2432bb515c4721013d98a569b794cf027ab9e356dde48fd06287f78982fac010e5abee0aa71388f270f70c53f0f1ac091fdbbe380c1e67e1079a2a6ea7ae6f2173fd1c39994e4436ad058996b0eed5cbc2ef10e4e6c814fad9b62056d7701976ce88fff49e864ca23b6ff762168436f7aaf0ce379515fd0d4d97367c0cf8ce7242fe6809cb,
0x7a4c0c06b31aa9be92dfcc10af0b4d99429bd0d2465d43c56e7488136db91347f7e40213e82b5bbcafee449614d9c26237dcf6ae1118f345d5f76a7b7fd665146103c4ba9cf63444363631b2e847a9ecd6126931299c30a31582d0fe918e71251d80bb7b3a3c27833379d12ca45fb339b169340335af84131a8848c7ac56533964823ebc1cc78dc69f136e735a46b9af5123b31171ff27e71f7f11e25878451619c199b04a93414effb74e90effd91a24735a77d3364020ae38883addac5c7f71e6a0e57d82d47c255c172f084a707ea565daa9d121693ae94391fa4c0fa0e3ad877b03014469bda192aebe3e4cf8fcc8469636ed8a74659cb4db0e8e5eecd9a,
0x3fc5f6519c720d08da16c2df2112ba76d718329a8a8cdcace3bc2b07d603cad7e492ce13ce537bddef922ee8fabf8261a27dbc0ca94752a2fe8016b99088a4cf794126da4673e7cea14428a7f3bb2a50f489d0a507b3fb3c6541f4d25941558180e28db6938fd6e92856ba10e56d2100f0d12fe6dd64e8d75ff5ad91f446b0481412ab10d08df34cdb7213df180cfa342e38af893750c9df36987f630083985588b7758cb3b83559485f208ac5b8c2df81379b69565adae0ce38ffbe568715cca87381d72508bc278e374acfb0b9db4726630dfdb6771ac3de26c0ec48ce72cec92af4d610f312474d979d7a445cd0aa16d9bfb8c8434449aacf9ea3acd23653,
0x6db31ce529ff59c5e2a06cee7c7ff63b26b5297a359c87edd61d144285a99cb22a311a75dbe8d5a1a7fdcc8eef52a4a1126ef2e09a38b1f5e17ee0c0c1d802e4ff2179ad66336613ca539d1ea76144e832b8faf7f9f09d0b061a8c70e13173037ef1255941deae9942a8bee684c46df73fde2ba15bd925255f61ce3f4748060388b572e914f2e8a7068f026550fb06f283dee852a44ce9d80e572a9a9c84a26d9f35308907ad995bd4bb29893e23b725611c39676cdd9bd953ec2b988d2344d95c96a5cf3f9daf9449ee3e57abad421038d33a14ab9eaa91421cce008c2b7a49085e555fde59a07e4c0bb3da1a487bef263608cf9001c2cb3a0f128f8ffdc4b5,
0x47fc4dec774af58a10a86f32aca278b7333e2a203f32d1c3829f77ee1ca4bb26967d46f2501ebf00f1b7d183245ae9230c27a1b44e77b943e6b666c1eb93d77c400accd3be53637cfcdf42617ec7e49ad7466e779ff1deeb26d055a40d4028845e07225acd900a158e3264301f3f474db2d185f18c7178eb6bb22af198527bf714ca70e4b1b8786595e59db4a1e7666d4f11aab6d8b8cdf92d25fe1371853bc191223dfa1e3a1eb0ddc139b23bdaa34b7b628c420752911689bd2360355e0991e7824ec91fa5a16a04bcdb20b21859c2101187c5901fd83c33842d66accae05e9f8d52390245d154c6f6fd70cc9df06a7cb6beb8e97158dd008b289cc298b5be,
0x3879320d2b72a7d476f911a621a2cde56cb4f11bf6f2092a1d0e37732e39587ea5c8cc8012b865315823bb095513e0aaebf00a1d0bc64ffec621ba88574893741d16a051962eb48e6ce7a7bcd1c200b93d43de4b913fa04a33aa6ecf1cbe8b6224f86acb6fc30e3c9809265e94e89f5d9e86149263ab1e094e47a3b5a11402daad15f1af9f4af6ac6fb5042e46c16b5cd0339c07311bfbc12f5c55d56575d340fe3409fc0cdc53c70ef188de0fa5361f964e3dda4cfa93e4c1dcc2899b54405ab1a86377cbd52c804c8abe1801fb58e07cb4c12ccc7dae2d5fdcd99e7e0b41455a211b418d7d23eec52ab5964a9cf8e4dd644db1643b23162a84acd394315f26,
0x3744c133e79ad8c24d42c184ef789b2e8f98a436413a1759a3d3877a7be779d20237ca9f8795da75101b58f67a5cfe3862c09381b90541f9744b48d0c181d77238e30c5ff3c17b7d61cad61375028a9f5df2ba8ba4b03149932aee7e44a225c0861e6544a1fdf6c9c76f6a3e82d585f82ea9f5db917742d057a6f1cd05173e125f98d10e938cb4a81d963adfd557a4341e361f0ad258cf0898a2f129e84ecb010006f72c56e23d49af995a0c3627c37cd94b4f605834a31297e810ab5edeca323a7ab1a557376cc363918b8fab2391afc2d6fc835d68530aea668e3fa5fad2a820289b2c69fca87b9864b7055aaede029738665807a1234c3438b6df933b5011,
0x80e66bec156f4f23de053a26b431b5c9403b866b9e3db1bff70294fa02b9e2b190784b2c00a80b8ca68ada1a346901b23a18e64e2e72af65e692b682c63104e18705ed660c5bb8a7dc92210dd6b39c9da4ff6dbead8275cda95137e35b827257077089a3b3943cb25475db403246547328d026bf1ae84c0945d4eac09a5b19f3d876fc8a7634db369366d9890794a8420b7f68993176d4ed5b8898b9162220fba24400437af66f5272ae76903af9f20c6e73d64d6d90fb93423a8732883e3f1a73c49865026a5179ced111c830a960444a1000c6e3aaf2d73093979507ac2f8bd44dd3977d27f9092934d43daa7f2054cef40858fcdc4caf9d60b2a930dc9882,
0x32519d4dcbe20762cd311f137403d55f2991779a869854303a92937f1c0ac2b3c8de9462335fbdfcfc80a2d49952036fcc3892599846b17f6becf6623db795c9f1ad6ed43f65de285bb12050f3f81eaa31c7b34e3b748d87d4b4d9789844d1c739c7c5cc1493b23e32953e64bf2fbf2ca403827bc8e23b428f306c0e5072d89bb601e66706af21acb54da8bb5a535ce755028b1a59be3682bdd9b8cff60a36ab486361faf68cde5acf1fe590d2fe8fcd130d0de485f172854a02e53b4d80bb223ee41d1bed624fe7ac2579f329a48de2486de9d19a0232878ce2bfd7b203c4234ab7fd28bd5086c1aec9cfa27653b1742ad2bdcdb82df242ef6c3e5330e4955d,
0x4e4196a7b0c663ed59ad6674fd59f2a26f9e48e10fcc360d78cb35b5dd641402b32a39e828925b0155eb9f814e88bb5ff36cc0def7dd35d3aed96234507b007f0a0c14d477d2f09dee9f67c587877202d8815c424a14f54b5a19f48f1e939ad16b67fa481d9601734ae7e52bba9c5f54f703992d4a94b3bc3f3c7e25a35dcb51ba8b7fc45dea644262be00037724a09c46d0bac70c43555e37332c35a199707c0cdb8bc1da5a97085d073400e1797c36c726d894819154a6fb6f690c1aecc713b90aa5fe551fa56641d967d162332d10ecd267adf4cd5e90d2df6e0aa52ca1dc59f868719b76e309c59877b193018b8ce9ab50248c4a0c5dad1a30f5614a5804,
0x299118bc357f5e546d46209bb096684e336ee29225c2a214537d3a0e0368537e0dfd6780c2890ef87766679e567e388205e34f9cb548afdae574ccae43367e406affc253912972d0f0af7911b0ea9918d80aee4c17e9c21110805fe1bda963cd50c8d58c6a55597195c435b2d923dae945b88baa962bf7ad05fceee1604c29ee27e85d43a5dd0725fbdd721129fda99ff175e9e6e727cfd5e33827f0d0287b950d3866d7b70f31788127499096b5c1067daff65de5c5a0a8f4ab07c75650e222cefe605159f37f57217f5d38521bdee12a1513f75c68963597444ebf33af268e91c5317329fc51f29806c2ad8bdcf1eb46d012258119f4dc23ef8e20c2f10e1a,
0xac28242337642cabf950162a965ab69d9f2e2858e732cb0c97bfeecbc965670dacda76edb6e591e07bab71eef52d1ee4e857c8f30682451d5c3b325b185f3a3b5e4d1eb539d94e134a5792c646f60552a87970549c01514b9e2af63e2dadedfa9f732f3d71ed6301ce54a35e01e5d90bb0cc106b8c2833eeacbbab60ab362a87e7e8435ebef01b7f6aa509c09ac44d7ff8da06b3a04103db2f8928ed04ab838291db8badd859c9b65774dded6269a56fd3eb10cc7d1cb6bd737bfcf65e533245657a2c69710318f83b4543713c3c418436342823afd996b10c8d77c2e2a118d4fb1ecbd1b1f16d675292669d8bccaf86f6c1af02e5f7f9ee5c7aeb81c8a111fe,
0x19d171bf0005dc1f4d11f80d598687610cc6c062a1d2ace2b2e835f528117df7ccc873553bc413b603c1605335bf5d2cf656e804d39e6ede8c8b4a43014db17aa31aafa9998028a2e87b32d3ec35fd16836c133d80f88a8af86fc7d6fa01540ddfb78615a11f143293d4df73307041d8bd28f186bdc099685ed324abac7980680d86261259a666c64c4c5a0dabdaf01e3700dc4e70a74d3869572ce03a9c4dec97edfb04771907bda0683fe189c3d0e2002352a6c5f85bf7455e5717c7cc9ae13217a0ea04c933837a48e3b356151bdae1004b9828d68e03736cf8fad63d74e8778519b5c3f13ef5fc31ab85c11ab4fc8396def7bc6f690675c30fbcbeb86f93,
0x3d81bd9c0aa88eb6bafec40e4198f2c55d56575914d1a7aa81dfb0256b9429f7bcf5a3c7ec01a098a0af98e016b022bec1d035b9f9630938294d3d092328c35f7572c6a8d1c9851ca766c85e4ab676330e7ec1f9f4baa90ca6e5ea3ec024d6af4fcc5f51872037afeceffad441e445155ab8082ff5e0b0291c79ca7ede868a52facfc555ba22b2c75bb2571f3c7916655b9f295a4d87a1cfb554677d646ff813dc59f009345e0a94cbd2075094386c9f10b6aefa28cd3194d3426e10718fea4e3bcb5d1acf6cbe4e586d6bd7332d38f4c53499d80f026166422e15d4ed8e265842423252613b547f8e574c7194c12dd91ef51d31a6671d62ecf8a558d47b1eb6
]
# Calculate N
N = 1
for x in n:
N *= x
# Nx = N/nx
Nx = []
for x in n:
Nx.append(N/x)
# Dx = invert(Nx, nx)
Dx = []
for x in xrange(19):
Dx.append(long(invert(Nx[x], n[x])))
X = 0
for x in xrange(19):
X += C[x]*Nx[x]*Dx[x]
M_19 = X % N
print M_19
|
求出的M_19为$m^{19}$，把M_19开19次方就得到明文.
在这再扯下中国剩余定理，上次写的有点笼统，这次总结一下：
已知 $M^n\ mod\ N_n = C_n$，需要有n条这样的实例，就能求出$M^n$
假设n = 4，然后已知
$$
\begin{cases}
M^4\ mod\ N_1 = C_1\\
M^4\ mod\ N_2 = C_2\\
M^4\ mod\ N_3 = C_3\\
M^4\ mod\ N_4 = C_4\\
\end{cases}
$$
M为我们需要求的数，$N_1, N_2, N_3, N_4, C_1, C_2, C_3, C_4$为已知，这样我们就可以通过中国剩余定理求出$M^4$
- 求出$N(N = N_1 * N_2 * N_3 * N_4)$
- 求出$NN_n(NN_n = N / N_n)$，比如$NN_1 = N / N_1$
- 求出$D_n(D_n * NN_n = 1\ (mod\ N) )$，比如$D_1 * NN_1 = 1\ (mod\ N)$
- 求出$M^4$，$M^4 = (C_1*NN_1*D_1 + C_2*NN_2*D_2 + C_3 * NN_3 * D_3 + C_4 * NN_4 * D_4)\ mod\ N$
