RSA原理、算法、应用

大三第一学期学的RSA加解密算法当时把原理和各种细节搞得门清，课程还拿了优。然而时隔一年有点忘了。。。自己整理一下能比看别人整理的记得更牢，还能以备后用

原理

1、欧拉函数：\(\varphi (n)=n(1-\frac{1}{p_{1}})(1-\frac{1}{p_{2}})...(1-\frac{1}{p_{m}})\) 计算与n互质且小于n的正整数的个数。其中\(p_{1}、p_{2}、...、p_{m}\)为n的各质因数。

2、缩系：所有与正整数n互质且互不同余的数组成的集合称为n的缩系。显然集合有\(\varphi (n)\)个元素。

它有一条性质：若\(\left\{ a_1,a_2,...,a_{\varphi(n)} \right\}\)是n的缩系，则对于与n互质的正整数k满足\(\left\{ k*a_1,k*a_2,...,k*a_{\varphi(n)} \right\}\)也是n的缩系

证明：若存在\(k*a_i\equiv k*a_j(mod\: n)\)（其中i≠j），由于n与k互质，则满足\(a_i\equiv a_j(mod\: n)\)，矛盾，因此\(\left\{ k*a_1,k*a_2,...,k*a_{\varphi(n)} \right\}\)也是n的缩系

3、欧拉定理：对于互质的正整数a与n满足\(a^{\varphi (n)}\equiv 1(mod\: n)\)

证明：若\(\left\{ x_1,x_2,...,x_{\varphi(n)} \right\}\)是n的缩系，对与n互质的正整数a运用上述缩系性质有\[x_1*x_2*...*x_{\varphi(n)}\equiv a\,x_1*a\,x_2*...*a\,x_{\varphi(n)}(mod\: n)\]由于缩系元素均与n互质，可两边消去\(x_1*x_2*...*x_{\varphi(n)}\)。即可得\[a^{\varphi (n)}\equiv 1(mod\: n)\]

算法

1、任取两不同质数p、q并计算n=p*q，计算\(\varphi (n)=(p-1)(q-1)\)

2、取一与\(\varphi (n)\)互质且小于\(\varphi (n)\)的正整数e，(e,n)即为公钥对，对于小于n的明文m可用\(c=m^e(mod\:n)\)算法加密得到密文c

3、使用辗转相除法计算满足\(e*d\equiv 1(mod\: \varphi (n))\)的d，(d,n)即为私钥对，对于密文c用\(m=c^d(mod\:n)\)算法解密得到明文m。这是因为：\[e*d\equiv 1(mod\: \varphi (n))\]\[\Rightarrow e*d\equiv 1(mod\: (p-1)(q-1))\]\[\Rightarrow e*d\equiv 1(mod\: (p-1))\]\[\Rightarrow e*d\equiv 1(mod\: \varphi (p))\]由于p为质数，\(m^{\varphi (n)}\equiv 1(mod\: p)\)，则有\(m^{e*d}\equiv m(mod\: p)\)。同理\(m^{e*d}\equiv m(mod\: q)\)
由于p、q为不同质数，\(m^{e*d}\equiv m(mod\:n)\)

应用

1、简单的一个例子：p=7、q=11，则n=77、\(\varphi (n)\)=60。任取满足条件的e，这里取e=13，计算出d=37，得到公钥对(13,77)与私钥对(37,77)。

对明文m=35试验一下，客户端使用服务端公开的公钥对加密得到密文\(c=m^e(mod\:n)=63\)。密文传输到服务端后服务端使用私钥对解密得到明文\(m=c^d(mod\:n)=35\)

2、在CTF中RSA题出得也很多，南京邮电大学CTF平台有一题叫RSA Easy如下

初中数学，了解一下
n = 24585768801100871989460458412563674690545986652089097718040761783186739174559136657307807040444318337561194142282186006216583089898423180103199568738639814413601595196467099996734334212909157604318709957690532885862891927163713619932622153281344607898846228206181834468325246573910857887714824338949742479585089251882243488454602710292507668577598274622372304293403731722318890268908300308478539449464617438721833942643889296634768118375076052778833640986893990732882252524850152650060780854621796349622086656401914022236044924841914313726991826438982902866584892213702893596657746111940812657202364588469026832387629
p - q = 14048479366496281701869293063643750801596179514889914988732592464154208813942939793532694949932787548745769133200541469022315588864587160064703369956054828780928008235304461825448872454098086255531582368864754318040219023548966787642948010656526691472780392631956031751285174567712974691729142190835749586660
e = 65537
c = 13043206753625359891696429504613068427529111016070088678736297291041435652992434742862062899975037273524389833567258051170507686131853178642412748377655159798601888072877427570380109085131089494464136940524560062629558966202744902709909907514127527274581612606840291391818050072220256661680141666883565331886278443012064173917218991474525642412407692187407537171479651983318468186723172013439034765279464665108704671733067907815695414348312753594497823099115037082352616886076617491904991917443093071262488786475411319592529466108485884029307606114810451140886975584959872328937471166255190940884805476899976523580343

由于n=p*q，而p-q也已经给出了，那么在gmpy2中运用初中数学的知识就可求得p=163979993780473228636250944509658100304105288291161815533296974391197924208241177469979929848925840413549589001337016682107921402071171221384247679860925727646585534725356410523705767408370013103023547625067109338180880560875828450693640775629005283101707663609483220395891338395873247794351441082424506156057，q=149931514413976946934381651446014349502509108776271900544564381927043715394298237676447234898993052864803819868136475213085605813206584061319544309904870898865657526490051948698256894954271926847491965256202355020140661537326861663050692764972478591628927270977527188644606163828160273102622298891588756569397

从而算出d=15965350086779237837060869266549962120332882187765808942801451698565104380592455221656555106691323982024341979450467248311111938903170631838991214830996738053527880256515355320826705455437202333408542630565843699842119026446638146956567032353441015349483463997416520611303322454376890763772639794574410492487737750211922714971375668135707460689481628330081094374625545738075523816561554115971558579321196525580719968206838699026608106116830125651773717344702712739046567019445007362703792126984224077495196983779416071748175102961790733139029659623866158497571348723386999049370811394057199543508015681679826472033857，明文m=45411192849370852342508097771685415309715836886014345394100707709，在python中执行bytearray.fromhex(hex(m)[2:])将其转为16进制后ASCII解码，即可得flag为nctf{my_M4th_1s_t00_b4d!!!}

最后，放一个我觉得挺好用的在线工具：https://www.cryptool.org/en/cto-highlights/rsa-step-by-step，给出p、q、e就能加解密。