一、RSA密码算法简介 RSA （Rivest-Shamir-Adleman ）是最早的公钥密码系统之一，广泛用于安全数据传输。公钥密码系统中，加密密钥是公共的（公钥），且它与保密的解密密钥（私钥）不同。在RSA中，这种不对称性算法的可靠性是基于两个大质数乘积的因子分解难题 。
1.算法流程 密钥生成
选择两个大素数p，q，计算$$N = pq$$（p,q为大素数）
$$
选择随机数 $e$, $$ 1<e<\varphi(n) $$，$$ gcd(e,\varphi(n))=1 $$，
计算私钥 $$ d = e^{-1} mod\varphi(n) $$
公开密钥（e，n），保密私钥（d，p，q）
加密 $$
解密 $$
2.数字签名中的应用 签名 对消息字符串的散列值，使用 RSA 的私钥计算签名（实际上仍然是加密消息）后，得到一个签名字符串，与消息一并发送。
验证 接收方使用对应的公钥可以从签名字符串中解密出原来的散列值，同时对原始消息再计算一次散列值。二者相比较，假如两者相符的话，则认为发信人持有正确的私钥，发信人的身份得到认证，并且这个消息在传播路径上没有被篡改过。
3.密钥长度 用户应使用 1024 位密钥，证书认证机构应用 2048 位或以上。
4.OpenSSL 使用详见参考资料。
二、关于RSA的攻击 1.因数分解攻击 RSA的安全性依附于质因数分解的难度，若是密钥选用的整数不当，便可能遭受因数分解攻击。
针对因子分解的攻击：
Pollard’s Rho算法：可以快速找到合数的较小因子
Pollard’s P-1算法
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 import mathimport stringn = input() e = input() c = input() def gcd (a,b) :trueif b == 0 : truetruereturn a truereturn gcd(b,a%b) def exgcd (a,b) :trueif b==0 : truetruereturn 1 ,0 truex,y = exgcd(b,a%b) truetem = y truey = x-(a//b)*y truex = tem truereturn x,y def Rho (x,y) :trueglobal n truewhile 1 : truetrueg = gcd(x-y,n) truetrueif g>1 and g<n: truetruetruereturn g truetrueelif g == n: truetruetruereturn 0 truetrueelif g == 1 : truetruetruex = (x*x+1 )%n truetruetruey = ((y*y+1 )*(y*y+1 )+1 )%n def getd (p) :trueglobal n trueglobal e trueq = n//p truephi = (p-1 )*(q-1 ) truex,y = exgcd(e,phi) truereturn x for x in xrange(2 ,10 ):truey = x*x+1 truep = Rho(x,y) trueif p != 0 and p != 1 : truetrued = getd(p) truetruem = pow(c,d,n) truetrueprint(m) truetruebreak
2.选择密文攻击 若签名密钥对与加密解密密钥对相同的话，可进行一种类似“欺骗”的攻击，将明文加入盲化因子，骗取对方签名，再去盲化因子得到明文。
窃听者已知李四发给张三$ c $（$ c=m^e $）
选$ r<n $，计算$ t=r^{-1} mod n $，$ x=r^e mod n $，$ y=x*c mod n $
将$ y $发给张三，“欺骗”张三对$ y $进行签名，窃听者得到签名$ u=y^d mod n $
计算$ tu=r^{-1}y^d=r^{-1}(x c)^d=r^{-1}r m mod n $得到明文m
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 import mathdef exgcd (a,b) :trueif b==0 : truetruereturn 1 ,0 truex,y = exgcd(b,a%b) truetem = y truey = x-(a//b)*y truex = tem truereturn x,y n = input() e = input() c = input() m1 = 2 c1 = pow(m1,e,n) x,y = exgcd(m1,n) re_m1 = x v = (c1*c)%n print(v) u = input() m = (re_m1*u)%n print(m)
3.共用模数攻击 共用模数n时，攻击者可获得$ n,e_1,e_2,c_1,c_2 $
$$
若$e_1$和$e_2$互素，则有$ re_1+se_2=1 $
可以根据$ c_1^r*c_2^s=m^{re_1+se_2}=m mod n $
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 import syssys.setrecursionlimit(1000000 ) def exgcd (a,b) :trueif b==0 : truetruereturn 1 ,0 truex,y = exgcd(b,a%b) truetem = y truey = (x-(a//b)*y) truex = tem truereturn x,y n = input() e1 = input() c1 = input() e2 = input() c2 = input() r,s = exgcd(e1,e2) if r<0 :truer = -r truec1,y = exgcd(c1,n) if s<0 :trues = -s truec2,y = exgcd(c2,n) m = (pow(c1,r,n)*pow(c2,s,n))%n print(m)
4.CRT优化分解(加速RSA)失败时引起私钥泄露 CRT加速原理 $$(q-1) (q-1)^{-1}mod(p-1)}mod p(p-1) (p-1)^{-1}mod(q-1)}modq)(q^{-1} (y_1-y_2) modp)
通过上述 CRT，底数和指数均减小了，加快了运算速度。
私钥泄露 若$y_1$或$y_2$产生了计算错误，可能性较大是在$y_1$或$y_2$的计算过程时产生了错误。
$$q q^{-1}modp+y_2^ep p^{-1}modq)modnq^{p-1}+y_2^e p^{q-1})mod n
假设$ y_1 $发生计算错误，错误算为$ y_1’ $，则$ x $误算为$ x’ $
$$q^{p-1}+y_2^e p^{q-1})mod n
所以，
大概率存在$ gcd(x’-x, n) = gcd(y^e-x, n) = q $
解得q后可进行接下来的破解运算。
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 import gmpy2n = 317414783130165821045808930175617487601464670537823074592040709814439313429421170598096208692643181034555847239250461818568337890685803184993214355150334258064652250655643333567514373079127819952425740240056923848357657994723714554195062350207713120421222489778323142892993955679298208610869154670046475006253088141064370916548439054432244743695401792118444879262315002312654072545614448386852556641363183630761461501385451019411338842456735465115965319263560063646358653409938833605815022512370580090225483411694647809348209846840068278422177226702772182355075508529105926757724838388693883383910738155331571978924637416651098643111761325536420929467467295222943383203775975904926536083720347352981017431212906798517062595435424372927242747868846532427770029518638490921 e = 65537 m = 1066524364 c = 193482739944681472166649268398841256432266736840779533320141478366146561102433051287906778400856535734640533589535380018088047120252613168623083863627090014951883162534169365088522364459198619069204933607573820078075082411998324694346565612621424283800812109520139228816207125011379396420082030271744450911746811589257699610824438265850554262393906867550020386206426106295536511787488224220918456147396849783633623105573269317052260483910319720500504712711893111986143781088719391027185642831811927521318923707568350575988573880413630407329415277711875326921962451030666529992050768662684524216881840010936765724472307998320454246486649271134011152290057160437983027614696753184949072167115560166832457100113730862782304985106517460772420790481451071438951798306995834912 y = gmpy2.mpz(c) x = gmpy2.mpz(m) e = gmpy2.mpz(e) n = gmpy2.mpz(n) q = gmpy2.gcd(pow(y,e,n)-x,n) p = n//q print(p) print(q) phi = (p-1 )*(q-1 ) d = gmpy2.invert(e,phi) print(d)
5.低加密指数广播攻击 广播攻击发生在加密使用的e 、m 相同，而n 不同的时候。
当e比较小时例如e=3时，
$$
利用中国剩余定理CRT计算可得到$ m^3 $，开三次根在一定条件下可以得到明文。
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 import gmpy2import gmpyn1 = 19851375730109702147410111547354144221875457321031223697134537152662954284778035659726777836419173602074243675379474758042251574628709204015344630121722181081357947554864577012170759352751954056863634879277235566401052896903737915168025406120485821600575222177565339908483871231963345316325883880725805183642711886174973831560524323612262245625356867125808729291910241533822929104554191436887669275590954686677553317406770308567916811827616983415494452891552691357470886986580784689791637773270366691010488804490695335088232109363335726209752067510335487027948414237789259493071147119114207873564472255092787796548757 e1 = 3 c1 = 13454882946725216336041450149747912801345150897738269747319625457896248720170984223193236484534898137077301146985964053694050587114190081392420937926436398915166732221806147601326052804974598044401237369173872313727529418915224956452544247250395436614772904692858338345883362615830546358880178712003244051534635046041882852867263201374871209754801875383118920093306257191680420637858437331213661376601491056259663126310104282784895433487635261665632335398264707493652353887185570468343007234872853922612324354135362251045303050159390094257102957492540509071506452893423235001402946205906541435403199551892986374804920 n2 = 26173521773502483247597089125243271820677225372183032349481812213016725381309207331835749003553831554633140540489226837866262707465143723936787003842437739219695454025969846598168174437311116014531279790307600380343936852182714366426205276301534919963285316772313717938106432099542920318855434061615067172765247575458191567464963759236522075416365378512744932616647264073550477949168527127402025096578055512157336517624334623370255903913904590248155257738134523374649246351120963720090091717538463753218892797487756700017617593544916093999491492264335912330825446605892101262194414610122257588430781728196281222326651 e2 = 3 c2 = 13505913121068470220847964312710175156127986501306214129578806436961037400323893789715303603187803738093907369047899145934457596188311642310861028144773439633531605220508808140662455716670082475842080321970571163395148402130729296994642849239816204269873047205730800760989269793676473215155256331437661051503440037546831165029304263381250709273274732332158416367294821131012710190159262730579799708286031962242459049360890723076878496179124292728671677882488465347042310943034512325729185236397374244668132954343101850740961483761474738710909332537524142175876638720302151108710719145864015333307963483395995537718237 n3 = 21202818797998627515352334625994038311482995714221672591450790765515673401535030894775203361099711195656344673329068886519004082528476627094716954416561909940135293365319683026068015518128387635258888254158981811317777785864346252540152216898844697734341077863453519579609431124462134201561065624730763893560814943258405090316816207636751619251737723450504065388791809103078820291564967984392756678881814377646778632427962036034448591000014370204337562273165150667491895831948436446074304718602008919196536063662377670980534229222981374594541340748663430129312248249332521398553163699869169510362600703426150991680327 e3 = 3 c3 = 2635549585896987063596747996023030662880935298112353023391070236788009696866126812856463364148603345293543937750291213077386941083306976983900924726863039062657867962813245750120467702651250543524273657372522053114010217848432895770161412721991002769186252112683680365847580401603924973909985759574698735663384486805551640031571297336457567716862973639891400022554522747237776054570299366418332408201620428338348053622395238810600517412562626967908191234817960510861906168470293686081083205722204699391858263306642439567802298290619076110468756807006508224515918448157214084863411103786533238277029555517164882404883 n1 = gmpy2.mpz(n1) n2 = gmpy2.mpz(n2) n3 = gmpy2.mpz(n3) c1 = gmpy2.mpz(c1) c2 = gmpy2.mpz(c2) c3 = gmpy2.mpz(c3) n = n1*n2*n3 w1 = n//n1 w2 = n//n2 w3 = n//n3 t1 = gmpy2.invert(w1,n1) t2 = gmpy2.invert(w2,n2) t3 = gmpy2.invert(w3,n3) c = (c1*w1*t1+c2*w2*t2+c3*w3*t3)%n c = int(c) print(c) m = gmpy.mpz(c).root(3 )[0 ].digits() print(m)
三、RSA相关CTF题目（待后续填坑继续挖坑） 参考文献： [1] RSA(cryptosystem) WIKI
[2] 段段PPT
[3] RSA-原理、特点（加解密及签名验签）及公钥和私钥的生成
[4] OpenSSL用法详解
[5] RSA-CRT leaks__因使用中国余数定理计算RSA所引起的私钥泄露
