看雪一道RSA

Crypto

Word count: 443Reading time: 2 min

 2020/05/09   Share

思考的时间太久了…为什么我如此地菜…我还要花时间学挖洞怎么学…

参考：https://bbs.pediy.com/thread-251190.htm

题目

#!/usr/bin/env python
# -*- coding: utf-8 -*-

from Crypto.PublicKey import RSA
#https://github.com/hellman/libnum
import libnum
import uuid
'''
[+]c: 11622542882315246110198381780183915609885519794877638505888594318562049026875880773537475606421060851429089552521799855057027886903089045577109813131337411921487337465750533590631207496479099488188299062942178796174555168674712568378658858077222180944610864942429506071933825243631320461029402707050914749156857671955119372825884795180000144215132575842540467844284302164343073962738640412159437432082145434169104637104493153922807815726660347039567345441510659262739472851333525285962666179396710551064200850498123897201656365809967826085971401423720719968392295754099890208333604214557262123433949228347513816601858942270105905028665541583348520387445357850609498889211150135260431118281908911786331560514084002109424387727057040008628088391762000037896541315584868057004565383762789933210314395498347130144686602708726062407595082308912297303979962192896001591877838171018700151256900172437013887608913521641241205521734522794951440636550705178589005728250181715006876150918012968184851855731273296965605183204816253195084613324490885963526865525299044530681913885694303639328847246147837870731896624166657669627218280799351074582104102789652580089543558488110230582552692122452677137682052196370567053767353002469899164906203524
[+]N: 587968709539058313408360344694175927521393435295867041552138836606960116863153627892312711153444067023197048186735303913044122621915045595629336179214144182446538243466715834788299906377841573446054648074403456659034364370317810535639221958019488280674690299403030279034786147112205845689053851316875209287768229591403395364697513328405136562784999789757383283588143659042259431257123353856954190780441115046949767558439078366241457066877382475754158382409736522845698996533956491214258865232971655580947034295973684267291517478631677398758172903115326862798759208382421878492675176885274168199265667769069598506141732479397548393084018568565807729340314773768180197401175943611466390257275211756053220458003475758090694483667816464266328983297319762108936501126103556538051197300127945603910572127418577927453087498829225758576754701560706108903918961457819158694038438844261753477862389295231995570079982815866588639648009619532021364274990501839112831858171797039899325481102398448835637957957459508761469632465528770464341746877892783955689295070505140454641584801559515858363095788553686755947134361627356046897478967408989088014417477413794585473915127799859415216061461677004314432371582508650893848080925431008351355550152007
[+]g: 13687797836288679153470514913607716390506304947283858895417177644617977497889490618478125297714629372001506903805031551586875936223725525654940903258032589976321090510242035896440327719990180830470876971374300547060229575827116755853365035922025013391258548160205751904588941484849014624286544168015159637397041426885730692000178417792429534072915561797567703567303112138061929961912896209854470052675348624854143392625380453115758095231546499614292015518026583476816594200501256973716245005187995459385544286205456854077514855765298028625413107944401620765972570158961128150918149196080876157775025322093170149476396577062472842743913042563886868214359985484725077407837700954980617210638094102914647887027651477766533834650123562149779914938828201079611405866005738631120225623386211991062745976174810473880890008785707421499725522649037000040322498207639419474616435759375343499333340375771200572128962006825666899736998990417116279580541474375252742063939982374907374364979109435935335255797938262324738887658234277982055814962875063181268619501475173315921248738265304609605405256568393060613560961415365219659386650074175184062689645977864277139302709935390235796431788831377615036052532360778649053010355032315203680097382427813377816739880854417886162628922799338852518273958881330838668155325304900209508779583738213848243670088766519961161693232457045880024843819530093376731876449976282236412779228497424289717087178247731066079336521431896601464971225717450766734888527559985150837482175845367148607905956395212451673061412164439986008055704341195216491700802850635239198031365269154336835028904031328596974614842402229723764044153287297309033112761791456392305755469723939924594337531849107437026285961770248575126198290035220628533791779487534575997602039033539953397358706048378707330202870647220908704914154287806034576068616259170534
'''
flag = "flag{" + str(uuid.uuid4()) + "}"
rsa = RSA.generate(4096, e=65537)
p = rsa.p
d = rsa.d
e = rsa.e
N = rsa.n
m = libnum.s2n(flag)
c = pow(m, e, N)
g = d*(p - libnum.s2n("welcome"))
print "[+]c:",c
print "[+]N:",N
print "[+]g:",g

构造也是挺有意思的

我们令libnum.s2n("welcome")为w，也就是g=d*（p-w）

可以知道w=33607038427688293

那么怎么构造等式求解呢？

首先第一个式子我就想了半天，不知道为什么成立…

$c^{ed}\equiv c\ mod\ n$

想要证明，一开始就走进死胡同

$c^{ed-1}\equiv 0\ mod\ n，\ c^{ed-1}=kn$

不知道怎么推

想了半天，电脑太烫关个机，就有点思路了

应该是这样的：

$c\equiv m^{e}\equiv\ (c^d)^emod\ n$

也就是

$c^{ed}\equiv c\ mod\ n$

真的挺简单的但是想半天…

接下来就挺顺的

$c^{eg} \equiv c^{(ed* (p - w))}\equiv{(c^{ed})}^{p - w}\equiv c^{p-w} mod\ n$

两边同时乘 $c^w$

$c^{eg}*c^w \equiv c^{p-w}*c^w mod\ n$

也就是

$c^{eg}*c^w \equiv c^p mod\ n$

这个式子很关键

接下来我们就要利用费马小定理了，可以知道有下面这个关系式

$c^{p-1} \equiv 1\ mod\ p$

所以

$c^p \equiv c\ mod\ p$

也就是

$c^p - c \equiv 0\ mod\ p$

这说明什么？说明 $c^p - c$ 是p的倍数

那如果 $c^p - c$ 和 $n$ gcd一下，就可以得到p了

这里 $c^p - c=c^{eg}*c^w \ mod\ n$



A= (c^e)^g *c^w mod n =
382141886864987308712417586085910706698771279375086451092726661839223487734520078633477081709732720290423641877981892520892113421592544980399655300931886103530286563862965475533564430306344078677595855655030788754938039694446657877996476427696301070187055289812118977936197499043495473343804934938392522317093776125411365553573957742476749963725540547089912943143835009296253734607879416459767974815399094402622011573874236710084175071473052000674933649409764838748595950978332859398007884454462076950785664736932903155379640575220118139462907188351350981174359809978289891331145204446561841305982790451277575751847307025251038709436717291293489523255573511316620691412233217940114951311060018315488483085834092596926394188220412445317525238756649605959435428786008344882258507520976487770865864615068446684838169574074371713986275689202288141053906898881179278664396991492862084739168540376134968302505394849111526859083621365152305540972782921663117480295073687437353941717419708291929081965755844337194817460705609134065901074176148321744780286582524562911792005763181917328603486874580031903402363732000786987191028423813004092704835762929929727263019614015378294642929448473445740912968382817165290942517731294289884105427871787

A-c= 370519343982672062602219204305726791088885759580208812586838067520661438707644197859939606103311659438994552325460092665835085534689455934822545487800548691608799226397214941942933222809864979189407556592088609958763484525771945309617817569619078889242444424869689471864263673799864152882775532231341607567936918453456246180748072947296749819510407971247372475299550707131910660645140776047608537383316948968452906936769743556161367255746391653635366303968254179485856478126999334112045218275065366399721463886434779258177984209410150313376935786927630261205967514224190001122811600232004579182548841222930061935245448082980932804408051749710141002868128153466011192523022067804854520192778109403702151525320008594816969800493355405308897150364887605921538887470423476825253942137213697837655550219570099554693482971365645651578680606893375843749926936688283277072519153321843384587911640203697954414896481327470285653561886842357354100336232216484528474566823505722347065566501695323744230110024571040229212277500792880870816460851657435781253421057225518381110091877487613689274639628432194032670467107834129317563810143013653018122731660140277147173476055527268064060376756350993063775286330620794723888750378291819984940521668263

p = gcd(A-c, N) =
23658856578566664036074501485429989229455255516521292212959419992149510519356671554795698662654628692053900089792393475218409910408344452879588770173081769770320270512822300780941160922817303688693928118157032899864579509909174844148460266860491370340877842968271910736819183160271817262857958140204473419785812025774484915797179815146246088754035908262746993793208465849630916811013982500911032146632563811803652243833261155445760670498827351358579952017846756896116504118614786540976807658494096254787782221936877352811354405828384364405688582283337469223364051449717177972827813998362406921041521587441458932542779

q= N/p=
24851949526238664338611899087073156378901501538457150925032350137121033161937359929077259595668363332110563044885605929437453685507111041051811632837720922027595220259046162273538453908783279801556003518826645020095508452031712240986754040076410300803211509243489288677395647935061355472814982579273381817695054375333011308040149912373530319912197574688979302503690852764814673678709936983186197776200567023649023158200165794968924491126994907164381184838800721298655915460238965954896597356588137128303303060657925718782380814767864374969680835189795113335493411826863656213063627023223927318463484894232154685605733

d =
578548578238937599474570602076587622840107091595962248936826176911867144607690129268833938144134573601551917945862635510329681485564422316025283461082785539366005641186476403222501732801133246056666098392878155996935304563051171826781306840514560336235542568893956293454327391684465544210904003995778439985661684569950268655618178159037826594508694042175936887693190413669502478652945873631283166773857609991800809627249658156519414100000332082853325779429279325400164657971607675800447250290349621640424972162968322891570076256839967963344649526270627025974694982543559205919665900663757500109343502409692100628126993516373291768674156690559371408999771620821771396233379516920095622914850099520946999591315831765648905525643842412431675457683208867062603322250485716729226778522665751355453970091081319071366274107687659109439167405391512776895919976540258847805596654038082729634561963877943466255970558782346029466626207603386686033981029259959416838835654138533910307591597909919748753104366874665390999193169824888425594237640779137818318564615315021934374501186592213150310735448602774858378648172926067739019215578294471645835297231530475626607874412908814016634674801073144336123810987074144546647620301187366706860917788569

m=pow(c, d, n) =
56006392793406553292769797366390438674411080408462327899182934918087372261966594651588266724494501501

print(long_to_bytes(m))

Author：DGZ

原文链接：https://dgz-cyber.github.io/2020/05/09/%E7%9C%8B%E9%9B%AA%E4%B8%80%E9%81%93RSA/

发表日期：May 9th 2020, 12:48:20 am

更新日期：May 9th 2020, 12:48:23 am

Next Post

Upload-labs （看缘分填坑）
Previous Post

Vmware用任务管理器强制关闭后处理方法

CATALOG

