密码学笔记（一）

对称加密密码：加密密钥与解密密钥相同。如分组密码，流密码。

非对称加密密码：加密密钥与解密密钥不同。如公钥加密，数字签名。

Yusa的日常生活—美国大选

先放源码：

from Crypto.Util.number import *
from secret import p,q
def gcd(a, b):
    while b:
        a, b = b, a%b
    return a
   
flag='DASCTF{********************************}'
e=3
phi = (p-1)*(q-1)
assert gcd(e,phi)==1

d = inverse(e,phi)
print r"Form of vote:{voter}:{votee}! eg: "
print "Yusa:Trump!"
vote = pow(bytes_to_long("Yusa:Trump!"),d,p*q)
print "vote:",vote
try:
    yusa = int(raw_input("Your vote: "))
    vote = long_to_bytes(pow(yusa,e,p*q)).split(":")
    print vote
    if vote[-1] == "Trump!":
        print flag[:10]
    elif vote[-1] == "Biden!":
        print flag[10:]
except Exception as e:
    print str(e)
    exit()

分析源码可以知道，这道题用私钥d进行签名，公钥e进行解签，是一道RSA签名题。前半段flag发送题目给出的信息就得到了，重点是后半段flag。分析可知，发送一段以”:Biden!”结尾的字节流密文让他解密，就得到了后半段flag。
即找出$signiture^{3}\equiv “:Biden!”(modn)$，并且n未知。
但是由于e很小，所以$signiture^{e}$也远小于n，就可以伪造一个假的签名$f^{3}$的低位等于”:Biden!”就可以了。即找到$f^{3}\equiv m(mod2^{56})$，其中m=bytes_to_long(b”:Biden!”)。转换成了一个基本的RSA问题，$e=3$，$n=2^{56}$。
$\varphi (2^{56})=2^{56}-2^{55}=2^{55}$得到phi，d=invert(e,phi)，c=pow(m,d,n)。就出来了。

Yusa的密码学课堂—CBC第二课

什么是CBC

在CBC模式中，每个明文块先与前一个密文块进行异或后，再进行加密。在这种方法中，每个密文块都依赖于它前面的所有明文块。同时，为了保证每条消息的唯一性，在第一个块中需要使用初始化向量。

题目文件：

from Crypto.Cipher import AES
import os
flag='DASCTF{********************************}'
BLOCKSIZE = 16


def pad(data):
	pad_len = BLOCKSIZE - (len(data) % BLOCKSIZE) if  len(data) % BLOCKSIZE != 0 else 0
	return data + chr(pad_len) * pad_len


def unpad(data):
	num = ord(data[-1])
	return data[:-num]


def _enc(data,key,iv):
	cipher = AES.new(key,AES.MODE_CBC,iv)
	encrypt = cipher.encrypt(pad(data))
	return encrypt


def enc(data,key):
	try:
	iv = raw_input("Your iv: ").decode('hex')
	cipher = AES.new(key,AES.MODE_CBC,iv)
	encrypt = cipher.encrypt(pad(data))
	return encrypt
	except:
		exit()

def dec(data,key,iv):
	try:
		cipher = AES.new(key,AES.MODE_CBC,iv)
		encrypt = cipher.decrypt(data)
		return unpad(encrypt)
	except:
		exit()
	    

def task():
	try:
		key = os.urandom(16)
		iv = os.urandom(16)
		cipher = _enc(flag,key,iv).encode('hex')
		print cipher
		paintext = raw_input("Amazing function: ").decode('hex')
		print enc(paintext,key).encode('hex')

		backdoor = raw_input("Another amazing function: ")
		assert backdoor != cipher 

		if dec(backdoor.decode('hex'),key,iv) == flag:
			print flag
		else:
			print "Wow, amazing results."
			
	except Exception as e:
		print str(e)
		exit()
		
		
if __name__ == "__main__":
	task()

主要代码如下：

def task():
	try:
		key = os.urandom(16)
		iv = os.urandom(16)
		cipher = _enc(flag,key,iv).encode('hex')
		print cipher
		paintext = raw_input("Amazing function: ").decode('hex')
		print enc(paintext,key).encode('hex')

		backdoor = raw_input("Another amazing function: ")
		assert backdoor != cipher 

		if dec(backdoor.decode('hex'),key,iv) == flag:
			print flag
		else:
			print "Wow, amazing results."

首先加密他的flag，将密文输出。我们输入自己的iv和paintext进行加密，得到。然后输入我们的密文backdoor进行解密，并且输入的密文不能等于题干加密后的密文cipher。但是backdoor解密出来的明文要等于flag。

为什么不同的密文可以解密出相同的明文？关键在于pad和unpad函数。由于是分块传输，所以需要规定每块的长度。pad函数就是用于规范长度的，定义了blocksize为16。如最后一块的长度不足16，则进行填充。unpad则会将填充位减去。

os.urandom函数用来获取一个指定长度的随机bytes对象，即用于加密的

dp泄露

已知：

e = 65537
n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657

c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751

若已知dp、e、n、c，则可计算出p
计算过程：
$dp = d mod(p-1)$
$dp \equiv d (mod p-1)$
$dp \times e \equiv de (mod p-1)$
$dp \times e = k(p-1)+de$
又因为$de \equiv 1 mod(p-1)(q-1)$
即$de = 1 + k(p-1)(q-1)$
所以$dp \times e = k_{1}(p-1)+k_{2}(p-1)(q-1)+1$
$dp \times e = [k_{1}+k_{2}(q-1)] \times (p-1)+1$
$dp $e>k_{1}+k_{2}(q-1)$
从（0，e）遍历，找出可以整除的$k_{1}+k_{2}(q-1)$，即可求出p，进而求出d，进而求出m

dp、dq泄露

这次没有泄露e。

p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229 
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469 
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929 
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041 
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852

推导过程：
$dp \equiv d mod(p-1)$
$dq \equiv d mod(q-1)$
$m \equiv c^{d}modn$ => $m = c^{d} +kp*q$
两边同时对p取模
$m \% p = c^{d}\%p$
令$mp = c^{d}\%p$，$mq = c^{d}\%q$
由$dp \equiv d mod(p-1)$ 可得 $dp = k(p-1)+d$，移项得$d = dp+k(p-1)$，代入$mp = c^{d}\%p$得：
$mp=(c^{dp} \times c^{k(p-1)}) \%p$

根据欧拉定理$c^{p-1} \equiv 1(mod p)$
=> $mp = c^{dp} \% p$，同理$mq = c^{dq} \% q$
=> $c^{d}=mp+k_{1}p$。代入$mq = c^{dq} \% q$
=> $mq = c^{d}+k_{2}q=mp+k_1p+k_{2}q$
$k_{1}p = (mp-mq)-k_{2}q$ ①

设$p^{-1}$为p关于q的乘法逆元，即$pp^{-1} \equiv 1 (mod q)$
$pp^{-1} = k_{3}q+1$
=> $p^{-1} = \frac{k_{3}q+1}{p} $

①式两边同乘$p^{-1}$得
$k_{1}pp^{-1} = (mp-mq)p^{-1}-k_{2}qp^{-1}$
$k_{1}k_{3}q+k_{1} = (mq-mp)p^{-1}+k_{2}qp^{-1}$
$k_{1} = (mq-mp)*p^{-1}-(k_{2}p^{-1}+k_{1}k_{3})q$

两边同乘p
$k_{1}p = (mq-mp)p^{-1}p-(k_{2}p^{-1}+k_{1}k_{3})q*p$

又因为$c^{d}=mp+k_{1}p$
代入得：
$c^{d}=mp+(mq-mp)p^{-1}p-(k_{2}p^{-1}+k_{1}k_{3})q*p$

两边同时对n取模得：
$c^{d} \% n=mp \% n+[(mq-mp)p^{-1}p] \% n$
消去了一系列的k参数，得到m。

下面写程序试试：

import gmpy2
from Crypto.Util.number import *

p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852

i = gmpy2.invert(p, q)
mp = pow(c, dp, p)
mq = pow(c, dq, q)
n = p*q
m = (mp+(mq-mp)*i*p) % n
print(long_to_bytes(m))

孙子定理python

import gmpy2
from Crypto.Util.number import *


def CRT(rList, mList):
    M = 1
    for i in mList:
        M *= i
    x = 0
    for i in range(len(mList)):
        Mi = M // mList[i]
        Mi_inverse = gmpy2.invert(Mi, mList[i])
        x += rList[i]*Mi*Mi_inverse
    x = x % M
    return x


if __name__ == "__main__":
    N1 = 331310324212000030020214312244232222400142410423413104441140203003243002104333214202031202212403400220031202142322434104143104244241214204444443323000244130122022422310201104411044030113302323014101331214303223312402430402404413033243132101010422240133122211400434023222214231402403403200012221023341333340042343122302113410210110221233241303024431330001303404020104442443120130000334110042432010203401440404010003442001223042211442001413004
    c1 = 310020004234033304244200421414413320341301002123030311202340222410301423440312412440240244110200112141140201224032402232131204213012303204422003300004011434102141321223311243242010014140422411342304322201241112402132203101131221223004022003120002110230023341143201404311340311134230140231412201333333142402423134333211302102413111111424430032440123340034044314223400401224111323000242234420441240411021023100222003123214343030122032301042243

    N2 = 302240000040421410144422133334143140011011044322223144412002220243001141141114123223331331304421113021231204322233120121444434210041232214144413244434424302311222143224402302432102242132244032010020113224011121043232143221203424243134044314022212024343100042342002432331144300214212414033414120004344211330224020301223033334324244031204240122301242232011303211220044222411134403012132420311110302442344021122101224411230002203344140143044114
    c2 = 112200203404013430330214124004404423210041321043000303233141423344144222343401042200334033203124030011440014210112103234440312134032123400444344144233020130110134042102220302002413321102022414130443041144240310121020100310104334204234412411424420321211112232031121330310333414423433343322024400121200333330432223421433344122023012440013041401423202210124024431040013414313121123433424113113414422043330422002314144111134142044333404112240344

    N3 = 332200324410041111434222123043121331442103233332422341041340412034230003314420311333101344231212130200312041044324431141033004333110021013020140020011222012300020041342040004002220210223122111314112124333211132230332124022423141214031303144444134403024420111423244424030030003340213032121303213343020401304243330001314023030121034113334404440421242240113103203013341231330004332040302440011324004130324034323430143102401440130242321424020323
    c3 = 10013444120141130322433204124002242224332334011124210012440241402342100410331131441303242011002101323040403311120421304422222200324402244243322422444414043342130111111330022213203030324422101133032212042042243101434342203204121042113212104212423330331134311311114143200011240002111312122234340003403312040401043021433112031334324322123304112340014030132021432101130211241134422413442312013042141212003102211300321404043012124332013240431242

    cList = [int(str(c1), 5), int(str(c2), 5), int(str(c3), 5)]
    nList = [int(str(N1), 5), int(str(N2), 5), int(str(N3), 5)]
    m_e = CRT(cList, nList)
    for e in range(1, 10):
        m, k = gmpy2.iroot(m_e, e)
        print("e =", e)
        print(long_to_bytes(m))

《从零到一》上大佬写的简洁明了优越的CRT代码：

def CRT(rList, mList):
    prod = reduce(lambda a, b: a*b, mList)
    x = 0
    for r_i, n_i in zip(rList, mList):
        p = prod // n_i
        x += r_i*gmpy2.invert(p, n_i)*p
    return x % prod

有的时候孙子定理解不出来又很多n和密文的广播攻击，这时候可以寻找n之间的最大公因数。

import gmpy2
from Crypto.Util.number import *
from functools import reduce


def CRT(rList, mList):
    prod = reduce(lambda a, b: a*b, mList)
    x = 0
    for r_i, n_i in zip(rList, mList):
        p = prod // n_i
        x += r_i*gmpy2.invert(p, n_i)*p
    return x % prod


if __name__ == "__main__":
    e = 65537
    n1 = 20474918894051778533305262345601880928088284471121823754049725354072477155873778848055073843345820697886641086842612486541250183965966001591342031562953561793332341641334302847996108417466360688139866505179689516589305636902137210185624650854906780037204412206309949199080005576922775773722438863762117750429327585792093447423980002401200613302943834212820909269713876683465817369158585822294675056978970612202885426436071950214538262921077409076160417436699836138801162621314845608796870206834704116707763169847387223307828908570944984416973019427529790029089766264949078038669523465243837675263858062854739083634207
    c1 = 974463908243330865728978769213595400782053398596897741316275722596415018912929508637393850919224969271766388710025195039896961956062895570062146947736340342927974992616678893372744261954172873490878805483241196345881721164078651156067119957816422768524442025688079462656755605982104174001635345874022133045402344010045961111720151990412034477755851802769069309069018738541854130183692204758761427121279982002993939745343695671900015296790637464880337375511536424796890996526681200633086841036320395847725935744757993013352804650575068136129295591306569213300156333650910795946800820067494143364885842896291126137320

    n2 = 20918819960648891349438263046954902210959146407860980742165930253781318759285692492511475263234242002509419079545644051755251311392635763412553499744506421566074721268822337321637265942226790343839856182100575539845358877493718334237585821263388181126545189723429262149630651289446553402190531135520836104217160268349688525168375213462570213612845898989694324269410202496871688649978370284661017399056903931840656757330859626183773396574056413017367606446540199973155630466239453637232936904063706551160650295031273385619470740593510267285957905801566362502262757750629162937373721291789527659531499435235261620309759
    c2 = 15819636201971185538694880505120469332582151856714070824521803121848292387556864177196229718923770810072104155432038682511434979353089791861087415144087855679134383396897817458726543883093567600325204596156649305930352575274039425470836355002691145864435755333821133969266951545158052745938252574301327696822347115053614052423028835532509220641378760800693351542633860702225772638930501021571415907348128269681224178300248272689705308911282208685459668200507057183420662959113956077584781737983254788703048275698921427029884282557468334399677849962342196140864403989162117738206246183665814938783122909930082802031855

    n3 = 25033254625906757272369609119214202033162128625171246436639570615263949157363273213121556825878737923265290579551873824374870957467163989542063489416636713654642486717219231225074115269684119428086352535471683359486248203644461465935500517901513233739152882943010177276545128308412934555830087776128355125932914846459470221102007666912211992310538890654396487111705385730502843589727289829692152177134753098649781412247065660637826282055169991824099110916576856188876975621376606634258927784025787142263367152947108720757222446686415627479703666031871635656314282727051189190889008763055811680040315277078928068816491
    c3 = 4185308529416874005831230781014092407198451385955677399668501833902623478395669279404883990725184332709152443372583701076198786635291739356770857286702107156730020004358955622511061410661058982622055199736820808203841446796305284394651714430918690389486920560834672316158146453183789412140939029029324756035358081754426645160033262924330248675216108270980157049705488620263485129480952814764002865280019185127662449318324279383277766416258142275143923532168798413011028271543085249029048997452212503111742302302065401051458066585395360468447460658672952851643547193822775218387853623453638025492389122204507555908862

    n4 = 21206968097314131007183427944486801953583151151443627943113736996776787181111063957960698092696800555044199156765677935373149598221184792286812213294617749834607696302116136745662816658117055427803315230042700695125718401646810484873064775005221089174056824724922160855810527236751389605017579545235876864998419873065217294820244730785120525126565815560229001887622837549118168081685183371092395128598125004730268910276024806808565802081366898904032509920453785997056150497645234925528883879419642189109649009132381586673390027614766605038951015853086721168018787523459264932165046816881682774229243688581614306480751
    c4 = 4521038011044758441891128468467233088493885750850588985708519911154778090597136126150289041893454126674468141393472662337350361712212694867311622970440707727941113263832357173141775855227973742571088974593476302084111770625764222838366277559560887042948859892138551472680654517814916609279748365580610712259856677740518477086531592233107175470068291903607505799432931989663707477017904611426213770238397005743730386080031955694158466558475599751940245039167629126576784024482348452868313417471542956778285567779435940267140679906686531862467627238401003459101637191297209422470388121802536569761414457618258343550613

    n5 = 22822039733049388110936778173014765663663303811791283234361230649775805923902173438553927805407463106104699773994158375704033093471761387799852168337898526980521753614307899669015931387819927421875316304591521901592823814417756447695701045846773508629371397013053684553042185725059996791532391626429712416994990889693732805181947970071429309599614973772736556299404246424791660679253884940021728846906344198854779191951739719342908761330661910477119933428550774242910420952496929605686154799487839923424336353747442153571678064520763149793294360787821751703543288696726923909670396821551053048035619499706391118145067
    c5 = 15406498580761780108625891878008526815145372096234083936681442225155097299264808624358826686906535594853622687379268969468433072388149786607395396424104318820879443743112358706546753935215756078345959375299650718555759698887852318017597503074317356745122514481807843745626429797861463012940172797612589031686718185390345389295851075279278516147076602270178540690147808314172798987497259330037810328523464851895621851859027823681655934104713689539848047163088666896473665500158179046196538210778897730209572708430067658411755959866033531700460551556380993982706171848970460224304996455600503982223448904878212849412357

    n6 = 21574139855341432908474064784318462018475296809327285532337706940126942575349507668289214078026102682252713757703081553093108823214063791518482289846780197329821139507974763780260290309600884920811959842925540583967085670848765317877441480914852329276375776405689784571404635852204097622600656222714808541872252335877037561388406257181715278766652824786376262249274960467193961956690974853679795249158751078422296580367506219719738762159965958877806187461070689071290948181949561254144310776943334859775121650186245846031720507944987838489723127897223416802436021278671237227993686791944711422345000479751187704426369
    c6 = 20366856150710305124583065375297661819795242238376485264951185336996083744604593418983336285185491197426018595031444652123288461491879021096028203694136683203441692987069563513026001861435722117985559909692670907347563594578265880806540396777223906955491026286843168637367593400342814725694366078337030937104035993569672959361347287894143027186846856772983058328919716702982222142848848117768499996617588305301483085428547267337070998767412540225911508196842253134355901263861121500650240296746702967594224401650220168780537141654489215019142122284308116284129004257364769474080721001708734051264841350424152506027932

    n7 = 25360227412666612490102161131174584819240931803196448481224305250583841439581008528535930814167338381983764991296575637231916547647970573758269411168219302370541684789125112505021148506809643081950237623703181025696585998044695691322012183660424636496897073045557400768745943787342548267386564625462143150176113656264450210023925571945961405709276631990731602198104287528528055650050486159837612279600415259486306154947514005408907590083747758953115486124865486720633820559135063440942528031402951958557630833503775112010715604278114325528993771081233535247118481765852273252404963430792898948219539473312462979849137
    c7 = 19892772524651452341027595619482734356243435671592398172680379981502759695784087900669089919987705675899945658648623800090272599154590123082189645021800958076861518397325439521139995652026377132368232502108620033400051346127757698623886142621793423225749240286511666556091787851683978017506983310073524398287279737680091787333547538239920607761080988243639547570818363788673249582783015475682109984715293163137324439862838574460108793714172603672477766831356411304446881998674779501188163600664488032943639694828698984739492200699684462748922883550002652913518229322945040819064133350314536378694523704793396169065179

    n8 = 22726855244632356029159691753451822163331519237547639938779517751496498713174588935566576167329576494790219360727877166074136496129927296296996970048082870488804456564986667129388136556137013346228118981936899510687589585286517151323048293150257036847475424044378109168179412287889340596394755257704938006162677656581509375471102546261355748251869048003600520034656264521931808651038524134185732929570384705918563982065684145766427962502261522481994191989820110575981906998431553107525542001187655703534683231777988419268338249547641335718393312295800044734534761692799403469497954062897856299031257454735945867491191
    c8 = 6040119795175856407541082360023532204614723858688636724822712717572759793960246341800308149739809871234313049629732934797569781053000686185666374833978403290525072598774001731350244744590772795701065129561898116576499984185920661271123665356132719193665474235596884239108030605882777868856122378222681140570519180321286976947154042272622411303981011302586225630859892731724640574658125478287115198406253847367979883768000812605395482952698689604477719478947595442185921480652637868335673233200662100621025061500895729605305665864693122952557361871523165300206070325660353095592778037767395360329231331322823610060006

    n9 = 23297333791443053297363000786835336095252290818461950054542658327484507406594632785712767459958917943095522594228205423428207345128899745800927319147257669773812669542782839237744305180098276578841929496345963997512244219376701787616046235397139381894837435562662591060768476997333538748065294033141610502252325292801816812268934171361934399951548627267791401089703937389012586581080223313060159456238857080740699528666411303029934807011214953984169785844714159627792016926490955282697877141614638806397689306795328344778478692084754216753425842557818899467945102646776342655167655384224860504086083147841252232760941
    c9 = 5418120301208378713115889465579964257871814114515046096090960159737859076829258516920361577853903925954198406843757303687557848302302200229295916902430205737843601806700738234756698575708612424928480440868739120075888681672062206529156566421276611107802917418993625029690627196813830326369874249777619239603300605876865967515719079797115910578653562787899019310139945904958024882417833736304894765433489476234575356755275147256577387022873348906900149634940747104513850154118106991137072643308620284663108283052245750945228995387803432128842152251549292698947407663643895853432650029352092018372834457054271102816934

    n10 = 28873667904715682722987234293493200306976947898711255064125115933666968678742598858722431426218914462903521596341771131695619382266194233561677824357379805303885993804266436810606263022097900266975250431575654686915049693091467864820512767070713267708993899899011156106766178906700336111712803362113039613548672937053397875663144794018087017731949087794894903737682383916173267421403408140967713071026001874733487295007501068871044649170615709891451856792232315526696220161842742664778581287321318748202431466508948902745314372299799561625186955234673012098210919745879882268512656931714326782335211089576897310591491
    c10 = 9919880463786836684987957979091527477471444996392375244075527841865509160181666543016317634963512437510324198702416322841377489417029572388474450075801462996825244657530286107428186354172836716502817609070590929769261932324275353289939302536440310628698349244872064005700644520223727670950787924296004296883032978941200883362653993351638545860207179022472492671256630427228461852668118035317021428675954874947015197745916918197725121122236369382741533983023462255913924692806249387449016629865823316402366017657844166919846683497851842388058283856219900535567427103603869955066193425501385255322097901531402103883869

    n11 = 22324685947539653722499932469409607533065419157347813961958075689047690465266404384199483683908594787312445528159635527833904475801890381455653807265501217328757871352731293000303438205315816792663917579066674842307743845261771032363928568844669895768092515658328756229245837025261744260614860746997931503548788509983868038349720225305730985576293675269073709022350700836510054067641753713212999954307022524495885583361707378513742162566339010134354907863733205921845038918224463903789841881400814074587261720283879760122070901466517118265422863420376921536734845502100251460872499122236686832189549698020737176683019
    c11 = 1491527050203294989882829248560395184804977277747126143103957219164624187528441047837351263580440686474767380464005540264627910126483129930668344095814547592115061057843470131498075060420395111008619027199037019925701236660166563068245683975787762804359520164701691690916482591026138582705558246869496162759780878437137960823000043988227303003876410503121370163303711603359430764539337597866862508451528158285103251810058741879687875218384160282506172706613359477657215420734816049393339593755489218588796607060261897905233453268671411610631047340459487937479511933450369462213795738933019001471803157607791738538467

    n12 = 27646746423759020111007828653264027999257847645666129907789026054594393648800236117046769112762641778865620892443423100189619327585811384883515424918752749559627553637785037359639801125213256163008431942593727931931898199727552768626775618479833029101249692573716030706695702510982283555740851047022672485743432464647772882314215176114732257497240284164016914018689044557218920300262234652840632406067273375269301008409860193180822366735877288205783314326102263756503786736122321348320031950012144905869556204017430593656052867939493633163499580242224763404338807022510136217187779084917996171602737036564991036724299
    c12 = 21991524128957260536043771284854920393105808126700128222125856775506885721971193109361315961129190814674647136464887087893990660894961612838205086401018885457667488911898654270235561980111174603323721280911197488286585269356849579263043456316319476495888696219344219866516861187654180509247881251251278919346267129904739277386289240394384575124331135655943513831009934023397457082184699737734388823763306805326430395849935770213817533387235486307008892410920611669932693018165569417445885810825749609388627231235840912644654685819620931663346297596334834498661789016450371769203650109994771872404185770230172934013971

    n13 = 20545487405816928731738988374475012686827933709789784391855706835136270270933401203019329136937650878386117187776530639342572123237188053978622697282521473917978282830432161153221216194169879669541998840691383025487220850872075436064308499924958517979727954402965612196081404341651517326364041519250125036424822634354268773895465698920883439222996581226358595873993976604699830613932320720554130011671297944433515047180565484495191003887599891289037982010216357831078328159028953222056918189365840711588671093333013117454034313622855082795813122338562446223041211192277089225078324682108033843023903550172891959673551
    c13 = 14227439188191029461250476692790539654619199888487319429114414557975376308688908028140817157205579804059783807641305577385724758530138514972962209062230576107406142402603484375626077345190883094097636019771377866339531511965136650567412363889183159616188449263752475328663245311059988337996047359263288837436305588848044572937759424466586870280512424336807064729894515840552404756879590698797046333336445465120445087587621743906624279621779634772378802959109714400516183718323267273824736540168545946444437586299214110424738159957388350785999348535171553569373088251552712391288365295267665691357719616011613628772175

    n14 = 27359727711584277234897157724055852794019216845229798938655814269460046384353568138598567755392559653460949444557879120040796798142218939251844762461270251672399546774067275348291003962551964648742053215424620256999345448398805278592777049668281558312871773979931343097806878701114056030041506690476954254006592555275342579529625231194321357904668512121539514880704046969974898412095675082585315458267591016734924646294357666924293908418345508902112711075232047998775303603175363964055048589769318562104883659754974955561725694779754279606726358588862479198815999276839234952142017210593887371950645418417355912567987
    c14 = 3788529784248255027081674540877016372807848222776887920453488878247137930578296797437647922494510483767651150492933356093288965943741570268943861987024276610712717409139946409513963043114463933146088430004237747163422802959250296602570649363016151581364006795894226599584708072582696996740518887606785460775851029814280359385763091078902301957226484620428513604630585131511167015763190591225884202772840456563643159507805711004113901417503751181050823638207803533111429510911616160851391754754434764819568054850823810901159821297849790005646102129354035735350124476838786661542089045509656910348676742844957008857457

    n15 = 27545937603751737248785220891735796468973329738076209144079921449967292572349424539010502287564030116831261268197384650511043068738911429169730640135947800885987171539267214611907687570587001933829208655100828045651391618089603288456570334500533178695238407684702251252671579371018651675054368606282524673369983034682330578308769886456335818733827237294570476853673552685361689144261552895758266522393004116017849397346259119221063821663280935820440671825601452417487330105280889520007917979115568067161590058277418371493228631232457972494285014767469893647892888681433965857496916110704944758070268626897045014782837
    c15 = 14069112970608895732417039977542732665796601893762401500878786871680645798754783315693511261740059725171342404186571066972546332813667711135661176659424619936101038903439144294886379322591635766682645179888058617577572409307484708171144488708410543462972008179994594087473935638026612679389759756811490524127195628741262871304427908481214992471182859308828778119005750928935764927967212343526503410515793717201360360437981322576798056276657140363332700714732224848346808963992302409037706094588964170239521193589470070839790404597252990818583717869140229811712295005710540476356743378906642267045723633874011649259842

    n16 = 25746162075697911560263181791216433062574178572424600336856278176112733054431463253903433128232709054141607100891177804285813783247735063753406524678030561284491481221681954564804141454666928657549670266775659862814924386584148785453647316864935942772919140563506305666207816897601862713092809234429096584753263707828899780979223118181009293655563146526792388913462557306433664296966331469906428665127438829399703002867800269947855869262036714256550075520193125987011945192273531732276641728008406855871598678936585324782438668746810516660152018244253008092470066555687277138937298747951929576231036251316270602513451
    c16 = 17344284860275489477491525819922855326792275128719709401292545608122859829827462088390044612234967551682879954301458425842831995513832410355328065562098763660326163262033200347338773439095709944202252494552172589503915965931524326523663289777583152664722241920800537867331030623906674081852296232306336271542832728410803631170229642717524942332390842467035143631504401140727083270732464237443915263865880580308776111219718961746378842924644142127243573824972533819479079381023103585862099063382129757560124074676150622288706094110075567706403442920696472627797607697962873026112240527498308535903232663939028587036724

    n17 = 23288486934117120315036919418588136227028485494137930196323715336208849327833965693894670567217971727921243839129969128783853015760155446770590696037582684845937132790047363216362087277861336964760890214059732779383020349204803205725870225429985939570141508220041286857810048164696707018663758416807708910671477407366098883430811861933014973409390179948577712579749352299440310543689035651465399867908428885541237776143404376333442949397063249223702355051571790555151203866821867908531733788784978667478707672984539512431549558672467752712004519300318999208102076732501412589104904734983789895358753664077486894529499
    c17 = 10738254418114076548071448844964046468141621740603214384986354189105236977071001429271560636428075970459890958274941762528116445171161040040833357876134689749846940052619392750394683504816081193432350669452446113285638982551762586656329109007214019944975816434827768882704630460001209452239162896576191876324662333153835533956600295255158377025198426950944040643235430211011063586032467724329735785947372051759042138171054165854842472990583800899984893232549092766400510300083585513014171220423103452292891496141806956300396540682381668367564569427813092064053993103537635994311143010708814851867239706492577203899024

    n18 = 19591441383958529435598729113936346657001352578357909347657257239777540424811749817783061233235817916560689138344041497732749011519736303038986277394036718790971374656832741054547056417771501234494768509780369075443550907847298246275717420562375114406055733620258777905222169702036494045086017381084272496162770259955811174440490126514747876661317750649488774992348005044389081101686016446219264069971370646319546429782904810063020324704138495608761532563310699753322444871060383693044481932265801505819646998535192083036872551683405766123968487907648980900712118052346174533513978009131757167547595857552370586353973
    c18 = 3834917098887202931981968704659119341624432294759361919553937551053499607440333234018189141970246302299385742548278589896033282894981200353270637127213483172182529890495903425649116755901631101665876301799865612717750360089085179142750664603454193642053016384714515855868368723508922271767190285521137785688075622832924829248362774476456232826885801046969384519549385428259591566716890844604696258783639390854153039329480726205147199247183621535172450825979047132495439603840806501254997167051142427157381799890725323765558803808030109468048682252028720241357478614704610089120810367192414352034177484688502364022887

    n19 = 19254242571588430171308191757871261075358521158624745702744057556054652332495961196795369630484782930292003238730267396462491733557715379956969694238267908985251699834707734400775311452868924330866502429576951934279223234676654749272932769107390976321208605516299532560054081301829440688796904635446986081691156842271268059970762004259219036753174909942343204432795076377432107630203621754552804124408792358220071862369443201584155711893388877350138023238624566616551246804054720492816226651467017802504094070614892556444425915920269485861799532473383304622064493223627552558344088839860178294589481899206318863310603
    c19 = 6790553533991297205804561991225493105312398825187682250780197510784765226429663284220400480563039341938599783346724051076211265663468643826430109013245014035811178295081939958687087477312867720289964506097819762095244479129359998867671811819738196687884696680463458661374310994610760009474264115750204920875527434486437536623589684519411519100170291423367424938566820315486507444202022408003879118465761273916755290898112991525546114191064022991329724370064632569903856189236177894007766690782630247443895358893983735822824243487181851098787271270256780891094405121947631088729917398317652320497765101790132679171889

    n20 = 26809700251171279102974962949184411136459372267620535198421449833298448092580497485301953796619185339316064387798092220298630428207556482805739803420279056191194360049651767412572609187680508073074653291350998253938793269214230457117194434853888765303403385824786231859450351212449404870776320297419712486574804794325602760347306432927281716160368830187944940128907971027838510079519466846176106565164730963988892400240063089397720414921398936399927948235195085202171264728816184532651138221862240969655185596628285814057082448321749567943946273776184657698104465062749244327092588237927996419620170254423837876806659
    c20 = 386213556608434013769864727123879412041991271528990528548507451210692618986652870424632219424601677524265011043146748309774067894985069288067952546139416819404039688454756044862784630882833496090822568580572859029800646671301748901528132153712913301179254879877441322285914544974519727307311002330350534857867516466612474769753577858660075830592891403551867246057397839688329172530177187042229028685862036140779065771061933528137423019407311473581832405899089709251747002788032002094495379614686544672969073249309703482556386024622814731015767810042969813752548617464974915714425595351940266077021672409858645427346

    cList = [c1, c2, c3, c4, c5, c6, c7, c8, c9, c10, c11, c12, c13, c14, c15, c16, c17, c18, c19, c20]
    nList = [n1, n2, n3, n4, n5, n6, n7, n8, n9, n10, n11, n12, n13, n14, n15, n16, n17, n18, n19, n20]
    print(len(cList), len(nList))
    for i in range(len(nList)):
        for j in range(len(nList)):
            if i != j:
                if gmpy2.gcd(nList[i], nList[j]) != 1:
                    print(i+1, j+1)
                    p = gmpy2.gcd(nList[i], nList[j])
                    # print(gmpy2.gcd(nList[i], nList[j]))
    q = n5 // p
    phi = (p-1)*(q-1)
    d = gmpy2.invert(e, phi)
    m = pow(c5, d, n5)
    print(long_to_bytes(m))

低解密指数（Wiener攻击）

这类攻击的特征是e很大，接近于N，导致d较小。
两篇文章可供阅读，攻击脚本下载地址：rsa-wiener-attack

以buuctf上的一道题为例：

N = 101991809777553253470276751399264740131157682329252673501792154507006158434432009141995367241962525705950046253400188884658262496534706438791515071885860897552736656899566915731297225817250639873643376310103992170646906557242832893914902053581087502512787303322747780420210884852166586717636559058152544979471
e = 46731919563265721307105180410302518676676135509737992912625092976849075262192092549323082367518264378630543338219025744820916471913696072050291990620486581719410354385121760761374229374847695148230596005409978383369740305816082770283909611956355972181848077519920922059268376958811713365106925235218265173085

import hashlib
flag = "flag{" + hashlib.md5(hex(d)).hexdigest() + "}"

一看e、n都很大，就想到维纳攻击了。

攻击原理

知识储备：

连分数

$\begin{equation}
x = a_1 + \cfrac{1}{a_2

      + \cfrac{1}{a_3 
      + \cfrac{1}{a_4 + ...
      + \cfrac{1}{a_{n}} } } }

\end{equation}$
成为连分数，通常用$[a_{1},a_{2},…,a_{n}]$表示。

实数的连分数表示

实例：
$\frac{159}{231}=\frac{1}{\frac{231}{159}}=\frac{1}{1+\frac{72}{159}}=\frac{1}{1+\frac{1}{2+\frac{15}{72}}}=\frac{1}{1+\frac{1}{2+\frac{1}{4+\frac{12}{15} } } } = \frac{1}{1+\frac{1}{2+\frac{1}{4+\frac{1}{1+\frac{1}{4} } } } }$

连分数的渐近分数

定义$[a_{1},a_{2},…,a_{k}]=\frac{p_{k}}{q_{k}} $为连分数的第k个渐近分数。
定理：
若连分数$[a_{1},a_{2},…,a_{n}]$的渐近分数是$\frac{p_{1}}{q_{1}} $，$\frac{p_{2}}{q_{2}} $，…，$\frac{p_{n}}{q_{n}} $，则这些渐近分数之间下列关系成立：
（注：在这里已经假定各渐近分数是存在的。事实上当$a_{2}=0$或者$a_{2}a_{3}+1=0$时，$\frac{p_{2}}{q_{2}} $或者$\frac{p_{3}}{q_{3}} $不存在。）
$p_{1}=a_{1},p_{2}=a_{2}a_{1}+1,p_{k}=a_{k}p_{k-1}+p_{k-2}$
$q_{1}=1,q_{2}=a_{2},q_{k}=a_{k}q_{k-1}+q_{k-2}$
（$3\le k\le n$）

例：
$\pi=[3,7,15,1,292,1,1,…]$，$\pi$的渐近分数为：
$\frac{p_{1}}{q_{1}}=\frac{a_{1}}{1}=\frac{3}{1} $
$\frac{p_{2}}{q_{2}}=a_{1}+\frac{1}{a_{2}}=\frac{a_{1}a_{2}+1}{a_{2}} =3+\frac{1}{7} =\frac{22}{7} $
$\begin{equation} \frac{p_{3}}{q_{3}} = a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3} }\end{equation}=\frac{a_{3}(a_{2}a_{1}+1)+a_{1}}{a_{3}a_{2}+1} = $ $\begin{equation} 3 + \cfrac{1}{7 + \cfrac{1}{15} }\end{equation}=\frac{15\times (7\times 3+1)+3}{15\times 7+1} =\frac{333}{106} $

维纳攻击需要满足的条件

典型的情况就是$e<n$，$gcd(p-1,q-1)$很小，p、q相差不大。
$3d < n^{\frac{1}{4}}$且$q<p<2q$。

连分数的收敛子

设$gcd(a,b)=gcd(c,d)=1$且$\left | \frac{a}{b}-\frac{c}{d} \right | <\frac{1}{2d^{2}} $，则称$\frac{c}{d} $是$\frac{a}{b}$的一个收敛子。

推导过程

由于$ed \equiv 1(mod \varphi(n))$，则$ed =1+k\varphi(n)$。
$n=pq>q^{2}$ => $q < \sqrt{n} $，=>
$0<n-\varphi (n)=p+q-1<2q+q-1<3q<3\sqrt{n} $
现在考虑：
$\left | \frac{e}{n}-\frac{k}{d} \right | $

$= \left | \frac{ed-kn}{nd} \right | $

$=\left | \frac{k\varphi (n)+1-kn}{nd} \right | $

$=\left | \frac{1+k(\varphi (n)-n)}{nd} \right | $

$<\frac{3k\sqrt{n}}{nd} =\frac{3k}{\sqrt{n}d } $

由于$k $\left | \frac{e}{n}-\frac{k}{d} \right |<\frac{1}{dn^{\frac{1}{4} }} $

又因为$3d $\left | \frac{e}{n}-\frac{k}{d} \right |<\frac{1}{3d^{2}} $。

所以$\frac{k}{d}$是$ \frac{e}{n}$连分数展开的收敛子。通过计算连分数$ \frac{e}{n}$的渐近分数的收敛，可以找到一组能正确分解n的$\frac{k}{d}$，从而恢复d。

由于$p+q=n-\varphi (n)+1$，故计算$x^{2}-(p+q)x+pq=0$这个方程有没有整数解，即可得到n是否能够分解。如果能分解n，那么d就是正确的。
代码分析：
分析一下 github 上求d的代码，其实过程就是上面写的那样，学习一下大佬怎么写的代码。
运算核心应该是这个文件：ContinuedFractions.py
第一个函数用于将实数变成连分数的数组表示形式。

def rational_to_contfrac(x,y):
    '''
    Converts a rational x/y fraction into
    a list of partial quotients [a0, ..., an]
    '''
    a = x//y
    pquotients = [a]
    while a * y != x:
        x,y = y,x-a*y
        a = x//y
        pquotients.append(a)
    return pquotients

第二个函数，用于分割原实数的连分数数组，因为求渐进分数的时候是一个个p、q逐渐求的。

def convergents_from_contfrac(frac):
	'''
	computes the list of convergents
	using the list of partial quotients
	'''
	convs = [];
	for i in range(len(frac)):
		convs.append(contfrac_to_rational(frac[0:i]))
	return convs

第三个函数，用于求出所给数组的渐进分数。

def contfrac_to_rational (frac):
    '''Converts a finite continued fraction [a0, ..., an]
     to an x/y rational.
     '''
    if len(frac) == 0:
        return (0,1)
    num = frac[-1]
    denom = 1
    for _ in range(-2,-len(frac)-1,-1):
        num, denom = frac[_]*num+denom, num
    return (num,denom)

这样，convs数组就是保存连分数的渐近分数的数组，遍历frac逐渐求出渐进分数。

直接修改RSAwienerHacker.py即可。

'''
Created on Dec 14, 2011

@author: pablocelayes
'''

import ContinuedFractions, Arithmetic, RSAvulnerableKeyGenerator

def hack_RSA(e,n):
    '''
    Finds d knowing (e,n)
    applying the Wiener continued fraction attack
    '''
    frac = ContinuedFractions.rational_to_contfrac(e, n)
    convergents = ContinuedFractions.convergents_from_contfrac(frac)
    
    for (k, d) in convergents:
        
        #check if d is actually the key
        if k != 0 and (e*d-1) % k == 0:
            phi = (e*d-1)//k
            s = n - phi + 1
            # check if the equation x^2 - s*x + n = 0
            # has integer roots
            discr = s*s - 4*n
            if discr >= 0:
                t = Arithmetic.is_perfect_square(discr)
                if t != -1 and (s+t) % 2 == 0:
                    print("Hacked!")
                    return d

# TEST functions


def test_hack_RSA():
    print("Testing Wiener Attack")
    times = 5
    
    while times>0:
        # e,n,d = RSAvulnerableKeyGenerator.generateKeys(1024)
        n = 101991809777553253470276751399264740131157682329252673501792154507006158434432009141995367241962525705950046253400188884658262496534706438791515071885860897552736656899566915731297225817250639873643376310103992170646906557242832893914902053581087502512787303322747780420210884852166586717636559058152544979471
        e = 46731919563265721307105180410302518676676135509737992912625092976849075262192092549323082367518264378630543338219025744820916471913696072050291990620486581719410354385121760761374229374847695148230596005409978383369740305816082770283909611956355972181848077519920922059268376958811713365106925235218265173085

        print("(e,n) is (", e, ", ", n, ")")
        # print("d = ", d)
    
        hacked_d = hack_RSA(e, n)
    
        # if d == hacked_d:
        #     print("Hack WORKED!")
        # else:
        #     print("Hack FAILED")
        
        # print("d = ", d, ", hacked_d = ", hacked_d)
        print("hacked_d = ", hacked_d)
        print("-------------------------")
        times -= 1


if __name__ == "__main__":
    # test_is_perfect_square()
    # print("-------------------------")
    test_hack_RSA()

求出d后

已知p高位

对RSA-Factoring with High Bits Known理解
这篇文章把原理讲解了，我只会用脚本，格基规约还在学习中…..
以这道CTF题目为例：

from Crypto.Util.number import *
import binascii
import gmpy2
flag = '*****************************************'
hex_flag=int(flag.encode("hex"),16)

p=getPrime(256)
q=getPrime(256)
n=p*q

e=getPrime(100)

c=pow(hex_flag,e,n)

p=((p>>60)<<60)

print("n=",hex(n))
print("p=",hex(p))
print("e=",hex(e))
print("c=",hex(c))
'''
('n=', '0x558477ce1d081f831cfa159290ee4fd14888422c216a16ad86e2b2d4335e3cb18ed0120a955f970b17b229a8e7d0ae1b6f0c40213ad0e127eba99ae0d8a82397L')
('p=', '0x8fbcbb7d1e9f393ee21b537d6e0bd2cf8629e315f4e356c1e000000000000000L')
('e=', '0xf7278179324b11fd83d08aa6fL')
('c=', '0x36e1c09ccad45cd63a0f07e704d3811c39d70cdfdad999d2df90255a76c58cf6fe99ac1ab1d5d99a4ce1a2ebdbfbc49ce72df2a0b90766ff84ab0ef62068d46bL')
'''

首先通过sage分解n：
在线运行sage

n = 0x558477ce1d081f831cfa159290ee4fd14888422c216a16ad86e2b2d4335e3cb18ed0120a955f970b17b229a8e7d0ae1b6f0c40213ad0e127eba99ae0d8a82397L
p_fake = 0x8fbcbb7d1e9f393ee21b537d6e0bd2cf8629e315f4e356c1e000000000000000L

# pbits = p_fake.nbits()
pbits = 256
kbits = 60  #p失去的低位
pbar = p_fake & (2^pbits-2^kbits)
print("upper %d bits (of %d bits) is given" % (pbits-kbits, pbits))
 
PR.<x> = PolynomialRing(Zmod(n))
f = x + pbar
 
x0 = f.small_roots(X=2^kbits, beta=0.4)[0]  # find root < 2^kbits with factor >= n^0.3
p= x0 + pbar
print(p)

这样就得到了p，接下来就是常规解题了：

from Crypto.Util.number import *
import gmpy2
import binascii
# from sage import *

n = 0x558477ce1d081f831cfa159290ee4fd14888422c216a16ad86e2b2d4335e3cb18ed0120a955f970b17b229a8e7d0ae1b6f0c40213ad0e127eba99ae0d8a82397
p = 65014198595370482567008424566891688124621484545138665561606519358457336776131
e = 0xf7278179324b11fd83d08aa6f
c = 0x36e1c09ccad45cd63a0f07e704d3811c39d70cdfdad999d2df90255a76c58cf6fe99ac1ab1d5d99a4ce1a2ebdbfbc49ce72df2a0b90766ff84ab0ef62068d46b
pp = binascii.b2a_hex(long_to_bytes(p)).decode()
print(pp)
ppp = 0x8fbcbb7d1e9f393ee21b537d6e0bd2cf8629e315f4e356c1e7c5e22d8cff45c3
q = n // ppp
phi = (ppp-1)*(q-1)
d = gmpy2.invert(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))

已知n、e、d，分解n

这是我在学校的比赛中遇到的一道题，我把n分解出来了，最后flag不对？？我也不知道为嘛，学校密码选手太少了，没得人讨论，老师也不给wp（难受.jpg）
原题目：

from gmpy2 import invert
from md5 import md5
from secret import p, q

e = ?????
n = p*q
phi = (p-1)*(q-1)
d = invert(e, phi)
ans = gcd(e,phi)

print n, e, d
print "Flag: flag{%s}" %md5(str(p + q)).hexdigest()

"""
n = 75314708877985876609891002668743876625554190294166511210009550179954413879734907287395890885734882006305000064658341495591490553852990740634932819033664336759786999376788951906380623027099236652601832025317652283419527455478573200079725665895206177368408570970326643545210806238705537263439737999272322484393
d = 10304874744787654147496365278986478201114950968434882459767596171356827577657686449351556699845391000049127292331775147314862622929371560548378501236023888087293532591829210438002936193106686968965664061672386720994287123226920682554316401724229936815553418464587344630901327534059887918508779592213104601681
"""

分解n的步骤：
$ed-1=k\varphi (n)$
选取$g<n$，$g^{ed-1}=g^{k\varphi (n)}$。
根据欧拉定理，若$(a,m)=1$，则$a^{\varphi (m)}\equiv 1(modm)$。
所以$g^{ed-1} \equiv g^{k\varphi (n)} \equiv 1(modn)$
所以$n = pq \equiv g^{ed-1}-1 \equiv 0(modn)$。
令$k=ed-1$，则$pq=g^{ed-1}-1=g^{k}-1=(g^{\frac{k}{2} }+1)(g^{\frac{k}{2} }-1)=0(modn)$。
若$((g^{\frac{k}{2} }-1),n)\ne 1$，就说明n被分解掉了。

脚本：

import random
import gmpy2
from Crypto.Util.number import *


def getpq(n, d):
    for e in range(0, 100000):
        k = e * d - 1
        g = random.randint(0, n)
        while gmpy2.gcd(g, n) != 1:
            g = random.randint(0, n)
        while k % 2 == 0:
            k = k//2
            temp = gmpy2.powmod(g, k, n)-1
            if gmpy2.gcd(temp, n) > 1 and temp != 0:
                print(e)
                return gmpy2.gcd(temp, n)


if __name__ == '__main__':
    n = 75314708877985876609891002668743876625554190294166511210009550179954413879734907287395890885734882006305000064658341495591490553852990740634932819033664336759786999376788951906380623027099236652601832025317652283419527455478573200079725665895206177368408570970326643545210806238705537263439737999272322484393
    d = 10304874744787654147496365278986478201114950968434882459767596171356827577657686449351556699845391000049127292331775147314862622929371560548378501236023888087293532591829210438002936193106686968965664061672386720994287123226920682554316401724229936815553418464587344630901327534059887918508779592213104601681
    p = getpq(n, d)
    print(p)
    q = n // p
    c = p+q
    print(c)

2021赣网杯密码1

e1，e2 不互素的共模攻击
题干：

ZnJvbSBzZWNyZXQgaW1wb3J0IGZsYWcKZnJvbSBDcnlwdG8uVXRpbC5udW1iZXIgaW1wb3J0ICoKCm0gPSBieXRlc190b19sb25nKGZsYWcpCgplMSA9IDY2NzQzMDEwNDg2NTI4OQplMiA9IDUzNzQwOTkzMDUyMzQyMQpwID0gZ2V0UHJpbWUoNTEyKQpxID0gZ2V0UHJpbWUoNTEyKQpuID0gcCpxCmMxID0gcG93KG0sIGUxLCBuKQpjMiA9IHBvdyhtLCBlMiwgbikKCnByaW50KGYnYzEgPSB7YzF9JykKcHJpbnQoZidjMiA9IHtjMn0nKQpwcmludChmJ24gPSB7bn0nKQoiIiIKYzEgPSA2NTkwMjY3ODU3MjcyNzcyNDE3OTE3NjQ5NjU3Mzk2ODk5NzE4MjcxMjA2MzMxNzA4MjI4OTEyMDQ1MzA5NDA2ODE5OTMyNTQxOTk4OTY4ODM4MjE3NzgwODUyOTA0MjMyMjIxNzg4NzMzNDAwNTA4NDUwNDc5NjM5NzIyMDgwNDg1NjE2NzI1NTE3NjQxNTY5MDIxNzM0ODI1MjEyNjA5NzgwOTEzMDE5NTIwODAyMDY5NDAyNjI1MDE5NDA0NzQ2MDU4MTE2NTAyNDE3ODM1ODQzNDMwNTQ5NTM2NDk4MzgzMDc1NjU1MjM3OTMzNTk4NTM5OTg3NjUyODkyMjA3NjAzMDU5NTIzMjY3OTA0Njk0MTMxMDc4NjYzNzI2MDc2NDk5MjQ5OTM3NTQyMTQ2NDUyOQpjMiA9IDg1ODA5NDAzNjc4MjUwMTUwMTUzMjkxNDcxMTg1OTk5ODA1ODcwODU4MTIzMDAxMjczMDM0MjEyNTgyODQ3NzMxODI1Mjk2ODkxMDE2ODEwODcxMzk3NTQ2MTM0MTE3MDEyMTk3NTk5NjUxNzI5NDAxNTkwOTgwMDIwMDI4MzgyODg0MDY4NTEzMjAxNzU4OTI2NDE2MTkyMjExODIxOTIyNTkzNjg2MjMyNDc1OTY3ODA4OTY0MDA2Nzg2MDc2NDYwMTYwNDI4NjM5MzUzMTUzNjU4MzIzMjA4MTE5NDUzMDU1MDcwMTk5MjQzMjk1MzMwNTIyODA0OTc0ODQ5MzMwOTI2NTAxMDkxNDMwNDE5Nzc1MTU1NjcwMjY0MzA2MjIyOTYyNDEzMjg5NjE2OTU3NTE5Cm4gPSA5MzAxMjM3OTk0OTU5NjY3OTg3NDAxMDgzNjUyMDk3MjQ2MzQzODE1NTE3NTk2MTI4MzI3Nzc0MzUxNDIwMzg3MTExNDMyOTAwODA0NDczNTUwMDcyNjQ0MDAxMjQ2NDAyOTE0NDIwNDgxMzQxMzkwOTMyMjM4OTU4NTk2NjMxMzQyNjYxMTQ4ODkyNzI5Mjg3NDMxOTYyODA2MzUyNjAwOTQwNTE0NDQzNjYwNTk5NjM4OTk4NTk3NzM0MDI4MDk4MzQ2OTgwMzQxMjExOTQ1ODE4NTA0NzQ3NTI1MzA1OTYzNjEyNjU1NTQ1MTU1NzM0ODE2OTUxNDk3NTI0OTcxMDkwMTg5OTUyNjk3NDI0NjEzOTU1OTczMDQ2MTU0MDY2MDk5MDM3NTAzNDY2OTA0Mjk1OQoiIiI=

base64解码之后：

from secret import flag
from Crypto.Util.number import *

m = bytes_to_long(flag)

e1 = 667430104865289
e2 = 537409930523421
p = getPrime(512)
q = getPrime(512)
n = p*q
c1 = pow(m, e1, n)
c2 = pow(m, e2, n)

print(f'c1 = {c1}')
print(f'c2 = {c2}')
print(f'n = {n}')
"""
c1 = 65902678572727724179176496573968997182712063317082289120453094068199325419989688382177808529042322217887334005084504796397220804856167255176415690217348252126097809130195208020694026250194047460581165024178358434305495364983830756552379335985399876528922076030595232679046941310786637260764992499375421464529
c2 = 85809403678250150153291471185999805870858123001273034212582847731825296891016810871397546134117012197599651729401590980020028382884068513201758926416192211821922593686232475967808964006786076460160428639353153658323208119453055070199243295330522804974849330926501091430419775155670264306222962413289616957519
n = 93012379949596679874010836520972463438155175961283277743514203871114329008044735500726440012464029144204813413909322389585966313426611488927292874319628063526009405144436605996389985977340280983469803412119458185047475253059636126555451557348169514975249710901899526974246139559730461540660990375034669042959
"""

但是e1，e2不互素，原理如下。
$c_1=(m^{e_{1}^{‘} })^3modn$
$c_2=(m^{e_{2}^{‘} })^3modn$
$xe_{1}^{‘}+ye_{2}^{‘}=1$
${c_{1}}^{x}{c_{2}}^{y} modn$
$=({(m^{e_{1}^{‘} })^3})^{x}({(m^{e_{2}^{‘} })^3})^{y} modn$
$=m^{3xe_{1}^{‘}+3ye_{2}^{‘}}modn$
$=m^3modn$
所以解出来的明文再开三次方根就可以了，写出解密脚本：

import gmpy2
from Crypto.Util.number import *

c1 = 65902678572727724179176496573968997182712063317082289120453094068199325419989688382177808529042322217887334005084504796397220804856167255176415690217348252126097809130195208020694026250194047460581165024178358434305495364983830756552379335985399876528922076030595232679046941310786637260764992499375421464529
c2 = 85809403678250150153291471185999805870858123001273034212582847731825296891016810871397546134117012197599651729401590980020028382884068513201758926416192211821922593686232475967808964006786076460160428639353153658323208119453055070199243295330522804974849330926501091430419775155670264306222962413289616957519
n = 93012379949596679874010836520972463438155175961283277743514203871114329008044735500726440012464029144204813413909322389585966313426611488927292874319628063526009405144436605996389985977340280983469803412119458185047475253059636126555451557348169514975249710901899526974246139559730461540660990375034669042959

e1 = 667430104865289
e2 = 537409930523421

g = gmpy2.gcd(e1, e2)
print(g)
# g = 3
l, x, y = gmpy2.gcdext(e1//3, e2//3)
print(x, y)

m = pow(c1, x, n)*pow(c2, y, n) % n
m = gmpy2.iroot(m, 3)
m = 56006392793429430154056421945568912277006938354753284086685860659829848328383664134484234657728574333
print(long_to_bytes(m))

Wilson定理

Wilson定理：若p是素数，则$(p-1)!+1\equiv 0modp$
看到阶乘，想到威尔逊定理
计算过程：
A是素数，所以满足$(A-1)!+1\equiv 0modA$，而B是A减去一部分值得到的，所以可以推出：
$B!\times (B+1)\times (B+2)\times …\times(A-1)+1\equiv 0modA$。
设$M=(B+1)\times (B+2)\times …\times(A-1)$，即$B!\times M\equiv -1modA$。设M关于A的模逆元素为C，即$C\times M\equiv 1modA$。
联立两式得：$C+ B!\equiv 0modA$，即$B!\equiv -CmodA$。

完整脚本：

import gmpy2
from Crypto.Util.number import *
import sympy

# 求M
def Wilson(a, b):
    c=1
    b = b+1
    while b<a:
        c = c*b
        c = c%a
        b = b+1
    return c


A1 = 21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467234407
B1 = 21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467140596
m1 = Wilson(A1, B1)
c1 = gmpy2.invert(m1,A1)
p = sympy.nextprime((c1*(-1)%A1),ith=1)
print(p)

A2 = 16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858418927
B2 = 16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858351026
m2 = (Wilson(A2,B2))*(-1)%A2
c2 = gmpy2.invert(m2,A2)
q = sympy.nextprime(c2,ith=1)
print(q)
n=85492663786275292159831603391083876175149354309327673008716627650718160585639723100793347534649628330416631255660901307533909900431413447524262332232659153047067908693481947121069070451562822417357656432171870951184673132554213690123308042697361969986360375060954702920656364144154145812838558365334172935931441424096270206140691814662318562696925767991937369782627908408239087358033165410020690152067715711112732252038588432896758405898709010342467882264362733

r=n//p//q

phi = (p-1)*(q-1)*(r-1)
e=0x1001
d = gmpy2.invert(e,phi)
c=75700883021669577739329316795450706204502635802310731477156998834710820770245219468703245302009998932067080383977560299708060476222089630209972629755965140317526034680452483360917378812244365884527186056341888615564335560765053550155758362271622330017433403027261127561225585912484777829588501213961110690451987625502701331485141639684356427316905122995759825241133872734362716041819819948645662803292418802204430874521342108413623635150475963121220095236776428
m = pow(c,d,n)
print(long_to_bytes(m))

sympy专业解方程工具

学到了一个很好用的解方程工具
题目源码：

import hashlib
import sympy
from Crypto.Util.number import *

flag = 'GWHT{******}'
secret = '******'

assert(len(flag) == 38)

half = len(flag) / 2

flag1 = flag[:half]
flag2 = flag[half:]

secret_num = getPrime(1024) * bytes_to_long(secret)

p = sympy.nextprime(secret_num)
q = sympy.nextprime(p)

N = p * q

e = 0x10001

F1 = bytes_to_long(flag1)
F2 = bytes_to_long(flag2)

c1 = F1 + F2
c2 = pow(F1, 3) + pow(F2, 3)
assert(c2 < N)

m1 = pow(c1, e, N)
m2 = pow(c2, e, N)

output = open('secret', 'w')
output.write('N=' + str(N) + '\n')
output.write('m1=' + str(m1) + '\n')
output.write('m2=' + str(m2) + '\n')
output.close()

经过一系列计算得到两个方程：
$c1=f1+f2$
$c2=f1^3+f2^3$
然后用sympy.solve解方程即可，不用自己推导，超级方便。
注意要提前格式化根a和b

a = sympy.Symbol("a")
b = sympy.Symbol("b")

解密脚本：

import gmpy2
from Crypto.Util.number import *
import sympy

N=636585149594574746909030160182690866222909256464847291783000651837227921337237899651287943597773270944384034858925295744880727101606841413640006527614873110651410155893776548737823152943797884729130149758279127430044739254000426610922834573094957082589539445610828279428814524313491262061930512829074466232633130599104490893572093943832740301809630847541592548921200288222432789208650949937638303429456468889100192613859073752923812454212239908948930178355331390933536771065791817643978763045030833712326162883810638120029378337092938662174119747687899484603628344079493556601422498405360731958162719296160584042671057160241284852522913676264596201906163
p = 797862863902421984951231350430312260517773269684958456342860983236184129602390919026048496119757187702076499551310794177917920137646835888862706126924088411570997141257159563952725882214181185531209186972351469946269508511312863779123205322378452194261217016552527754513215520329499967108196968833163329724620251096080377747699
q = 797862863902421984951231350430312260517773269684958456342860983236184129602390919026048496119757187702076499551310794177917920137646835888862706126924088411570997141257159563952725882214181185531209186972351469946269508511312863779123205322378452194261217016552527754513215520329499967108196968833163329724620251096080377748737
phi = (p-1)*(q-1)
e = 0x10001
d = gmpy2.invert(e, phi)
c1=90009974341452243216986938028371257528604943208941176518717463554774967878152694586469377765296113165659498726012712288670458884373971419842750929287658640266219686646956929872115782173093979742958745121671928568709468526098715927189829600497283118051641107305128852697032053368115181216069626606165503465125725204875578701237789292966211824002761481815276666236869005129138862782476859103086726091860497614883282949955023222414333243193268564781621699870412557822404381213804026685831221430728290755597819259339616650158674713248841654338515199405532003173732520457813901170264713085107077001478083341339002069870585378257051150217511755761491021553239
c2=487443985757405173426628188375657117604235507936967522993257972108872283698305238454465723214226871414276788912058186197039821242912736742824080627680971802511206914394672159240206910735850651999316100014691067295708138639363203596244693995562780286637116394738250774129759021080197323724805414668042318806010652814405078769738548913675466181551005527065309515364950610137206393257148357659666687091662749848560225453826362271704292692847596339533229088038820532086109421158575841077601268713175097874083536249006018948789413238783922845633494023608865256071962856581229890043896939025613600564283391329331452199062858930374565991634191495137939574539546

m1 = pow(c1,d,N)
m2 = pow(c2,d,N)
a = sympy.Symbol("a")
b = sympy.Symbol("b")
res = sympy.solve([a+b-m1,pow(a,3)+pow(b,3)-m2],[a,b])

f1 = long_to_bytes(res[0][0])
f2 = long_to_bytes(res[0][1])

print(f2+f1)

了解了关于位的知识点

from Crypto.Util.number import *
from flag import flag

def nextPrime(n):
    n += 2 if n & 1 else 1
    while not isPrime(n):
        n += 2
    return n

p = getPrime(1024)
q = nextPrime(p)
n = p * q
e = 0x10001                                                                                                                                                                                                                                                                                                                                                                                                                   
d = inverse(e, (p-1) * (q-1))
c = pow(bytes_to_long(flag.encode()), e, n)

# d = 19275778946037899718035455438175509175723911466127462154506916564101519923603308900331427601983476886255849200332374081996442976307058597390881168155862238533018621944733299208108185814179466844504468163200369996564265921022888670062554504758512453217434777820468049494313818291727050400752551716550403647148197148884408264686846693842118387217753516963449753809860354047619256787869400297858568139700396567519469825398575103885487624463424429913017729585620877168171603444111464692841379661112075123399343270610272287865200880398193573260848268633461983435015031227070217852728240847398084414687146397303110709214913
# c = 5382723168073828110696168558294206681757991149022777821127563301413483223874527233300721180839298617076705685041174247415826157096583055069337393987892262764211225227035880754417457056723909135525244957935906902665679777101130111392780237502928656225705262431431953003520093932924375902111280077255205118217436744112064069429678632923259898627997145803892753989255615273140300021040654505901442787810653626524305706316663169341797205752938755590056568986738227803487467274114398257187962140796551136220532809687606867385639367743705527511680719955380746377631156468689844150878381460560990755652899449340045313521804

关于位，1024位最大能表示$2^{1024}$。也就是说，要求一个十进制数n是多少位，要通过$\log_{2}{n} $来计算。
这里我们不知道n，但是知道e和d，于是可以求出$k\varphi (n)$。p和q都是1024位，乘积在2048位。而求得的$k\varphi (n)$的位数是$\log_{2}{k\varphi (n)} =2064$，所以k应该在$2^{16}$左右，从$2^{15}$爆破到$2^{16}$即可。
解密脚本：

from Crypto.Util.number import *
import gmpy2
import math
import sympy

d = 19275778946037899718035455438175509175723911466127462154506916564101519923603308900331427601983476886255849200332374081996442976307058597390881168155862238533018621944733299208108185814179466844504468163200369996564265921022888670062554504758512453217434777820468049494313818291727050400752551716550403647148197148884408264686846693842118387217753516963449753809860354047619256787869400297858568139700396567519469825398575103885487624463424429913017729585620877168171603444111464692841379661112075123399343270610272287865200880398193573260848268633461983435015031227070217852728240847398084414687146397303110709214913
c = 5382723168073828110696168558294206681757991149022777821127563301413483223874527233300721180839298617076705685041174247415826157096583055069337393987892262764211225227035880754417457056723909135525244957935906902665679777101130111392780237502928656225705262431431953003520093932924375902111280077255205118217436744112064069429678632923259898627997145803892753989255615273140300021040654505901442787810653626524305706316663169341797205752938755590056568986738227803487467274114398257187962140796551136220532809687606867385639367743705527511680719955380746377631156468689844150878381460560990755652899449340045313521804
e = 0x10001
kphi = e*d-1
x = math.log2(kphi)
print(x)
for k in range(pow(2,15),pow(2,16)):
    if kphi%k == 0:
        phi = kphi // k
        p = sympy.prevprime(gmpy2.iroot(phi,2)[0])
        q = sympy.nextprime(p)
        if (p - 1) * (q - 1) * k == kphi:
            break
n = p*q
m = pow(c,d,n)
print(long_to_bytes(m))

https://ddaa.tw/gctf_crypto_201_rsa_ctf_challenge.html
https://blog.csdn.net/weixin_26636643/article/details/108899088
http://archiv.infsec.ethz.ch/education/fs08/secsem/Bleichenbacher98.pdf
https://ishare.iask.sina.com.cn/f/13930857.html