Triode的RSA学习笔记（1）

Triode_Lzx2023-11-172023-11-17

在进行RSA解密之前，我们先要理解RSA的加密原理：

已知明文 $a$ ，公钥对 $(n,e)$ ，加密过程如下:

$b\equiv a^e\ (mod\ n)$

若要对已知的密文进行解密，我们就需要得到私钥(Private Key)：

设对于上述加密过程所得出的私钥为 $d$ ，则：

$a\equiv b^d\ (mod\ n)$

很明显：

$b^{ed}\equiv a^e\equiv b\ (mod\ n)$

所以：

$b^{ed-1}\equiv 1\ (mod\ n)$

一般情况下， $gcd(n,b)=1$ ，故先对这种情况进行考虑

由欧拉定理：我们知道

$b^{\varphi(n)}\equiv 1\ (mod\ n)$

很显然：

$ed-1=k\varphi(n)$

可以看出：

$ed\equiv1\ (mod\ \varphi(n))$

所以：

$d=inv(e,\varphi(n))\ (inv(e,\varphi(n))为e模\varphi(n)的乘法逆元)$

已知n,e,c在一般情况下（n可通过软件进行质因数分解）的解密

此时，我们有：

$n=p_1^{\alpha_1}p_2^{\alpha_2}p_3^{\alpha_3}\cdots p_k^{\alpha_k}(p_1,p_2,p_3,\cdots ,p_k为k个不同质数)$

此时，由欧拉函数的性质，我们有：

$\varphi(n)=\varphi(p_1^{\alpha_1}) \varphi(p_2^{\alpha_2}) \varphi(p_3^{\alpha_3}) \cdots \varphi(p_k^{\alpha_k})(p_1,p_2,p_3,\cdots p_k是n的不同质因数，且有p_1^{\alpha_1}p_2^{\alpha_2}p_3^{\alpha_3}\cdots p_k^{\alpha_k}=n)$

由欧拉函数的计算公式我们可以知道：

$\varphi(p^k)=p^k\prod_{i=1}^{k}\bigg(1-\frac{1}{p^i}\bigg)$

所以对于 $n$ ，有：

$\varphi(n)=\prod_{i=1}^{k}p_i^{\alpha_i}\prod_{j = 1}^{\alpha_i}\bigg(1-\frac{1}{p_i^j}\bigg)$

特别的，对于质数 $p$ ，有：

$\varphi(p)=p\bigg(1-\frac{1}{p}\bigg)=p-1$

若 $n$ 为 $k$ 个不相同质数相乘，即：

$n=p_1p_2p_3\cdots p_k$

有：

$\varphi(n)=(p_1-1)(p_2-1)(p_3-1)\cdots(p_k-1)$

在一般情况下 $n$ 只有两个质因数 $p$ 和 $q$ ，例如下题：

from Crypto.Util.number import getPrime,bytes_to_long,long_to_bytes
from gmpy2 import gcd,invert
from secret import flag

m=bytes_to_long(flag)
p=274327862430236019688316864082249987313
q=206961224895267889099693426679050192439
n=p*q
phi=(p-1)*(q-1)
e=65537
c=pow(m,e,n)
print("c =",c)
# c = 54831930044859946955044417597501651143196043923856762253170140444376354297816

这题直接给出了 $p$ 和 $q$ ，故我们只需要写出如下代码即可解决：

from Crypto.Util.number import *
import gmpy2
p = 274327862430236019688316864082249987313
q = 206961224895267889099693426679050192439
c = 54831930044859946955044417597501651143196043923856762253170140444376354297816
e = 65537
n = p * q
phi = (p-1) * (q-1)
d = gmpy2.invert(e,phi)#求e模phi的乘法逆元
m = gmpy2.powmod(c,d,n)#等价于c^d mod n
print(long_to_bytes(m))

运行即可得出flag：

1	flag{how_excellent_you_are!}

这就是最基本的RSA类型了。

在已知e以及e组(n,c)的广播攻击

此类型攻击属于CRT（Chinese remainder theorem，中国剩余定理，又称孙子定理）类型。

原理不赘述，实质上即为已知 $e$ 组 $(n,c)$ 时利用CRT在不对任何一个 $n$ 进行分解的情况下求解明文

在这里，我们设明文为 $m$ ，有：

$\begin{cases} m^e\equiv c_1\ (mod\ n_1) \\m^e\equiv c_1\ (mod\ n_1) \\\ \ \ \ \ \ \ \ \ \ \ \ \ \vdots \\m^e\equiv c_e\ (mod\ n_e) \end{cases} \\\ \ \ (其中(n_1,c_1),(n_2,c_2),\cdots,(n_e,c_e)为e组不同的n与c)$

再通过CRT求解出 $m^e$ 后对其开 $e$ 次方根即可得到明文 $m$

例题

[鹤城杯 2021]Crazy_Rsa_Tech

题目代码：

from Crypto.Util.number import *
from Crypto.Util.Padding import *

FLAG = bytes_to_long(pad(b"flag{??????}",64))
def init_key():
    p, q = getPrime(512), getPrime(512)
    n = p*q
    e = 9
    while(GCD((p-1)*(q-1),e)!=1):
        p, q = getPrime(512), getPrime(512)
        n = p*q
    d = inverse(e,(p-1)*(q-1))
    return n,e,d

n_list=list()
c_list=list()
for i in range(9):
    N,e,d=init_key()
    n_list.append(N)
    c=pow(FLAG,e,N)
    c_list.append(pow(FLAG,e,N))
    assert(pow(c,d,N)==FLAG)
print("n_list:",n_list)
print("c_list:",c_list)
#n_list= [71189786319102608575263218254922479901008514616376166401353025325668690465852130559783959409002115897148828732231478529655075366072137059589917001875303598680931962384468363842379833044123189276199264340224973914079447846845897807085694711541719515881377391200011269924562049643835131619086349617062034608799, 92503831027754984321994282254005318198418454777812045042619263533423066848097985191386666241913483806726751133691867010696758828674382946375162423033994046273252417389169779506788545647848951018539441971140081528915876529645525880324658212147388232683347292192795975558548712504744297104487514691170935149949, 100993952830138414466948640139083231443558390127247779484027818354177479632421980458019929149817002579508423291678953554090956334137167905685261724759487245658147039684536216616744746196651390112540237050493468689520465897258378216693418610879245129435268327315158194612110422630337395790254881602124839071919, 59138293747457431012165762343997972673625934330232909935732464725128776212729547237438509546925172847581735769773563840639187946741161318153031173864953372796950422229629824699580131369991913883136821374596762214064774480548532035315344368010507644630655604478651898097886873485265848973185431559958627423847, 66827868958054485359731420968595906328820823695638132426084478524423658597714990545142120448668257273436546456116147999073797943388584861050133103137697812149742551913704341990467090049650721713913812069904136198912314243175309387952328961054617877059134151915723594900209641163321839502908705301293546584147, 120940513339890268554625391482989102665030083707530690312336379356969219966820079510946652021721814016286307318930536030308296265425674637215009052078834615196224917417698019787514831973471113022781129000531459800329018133248426080717653298100515701379374786486337920294380753805825328119757649844054966712377, 72186594495190221129349814154999705524005203343018940547856004977368023856950836974465616291478257156860734574686154136925776069045232149725101769594505766718123155028300703627531567850035682448632166309129911061492630709698934310123778699316856399909549674138453085885820110724923723830686564968967391721281, 69105037583161467265649176715175579387938714721653281201847973223975467813529036844308693237404592381480367515044829190066606146105800243199497182114398931410844901178842049915914390117503986044951461783780327749665912369177733246873697481544777183820939967036346862056795919812693669387731294595126647751951, 76194219445824867986050004226602973283400885106636660263597964027139613163638212828932901192009131346530898961165310615466747046710743013409318156266326090650584190382130795884514074647833949281109675170830565650006906028402714868781834693473191228256626654011772428115359653448111208831188721505467497494581]
#c_list=[62580922178008480377006528793506649089253164524883696044759651305970802215270721223149734532870729533611357047595181907404222690394917605617029675103788705320032707977225447998111744887898039756375876685711148857676502670812333076878964148863713993853526715855758799502735753454247721711366497722251078739585, 46186240819076690248235492196228128599822002268014359444368898414937734806009161030424589993541799877081745454934484263188270879142125136786221625234555265815513136730416539407710862948861531339065039071959576035606192732936477944770308784472646015244527805057990939765708793705044236665364664490419874206900, 85756449024868529058704599481168414715291172247059370174556127800630896693021701121075838517372920466708826412897794900729896389468152213884232173410022054605870785910461728567377769960823103334874807744107855490558726013068890632637193410610478514663078901021307258078678427928255699031215654693270240640198, 14388767329946097216670270960679686032536707277732968784379505904021622612991917314721678940833050736745004078559116326396233622519356703639737886289595860359630019239654690312132039876082685046329079266785042428947147658321799501605837784127004536996628492065409017175037161261039765340032473048737319069656, 1143736792108232890306863524988028098730927600066491485326214420279375304665896453544100447027809433141790331191324806205845009336228331138326163746853197990596700523328423791764843694671580875538251166864957646807184041817863314204516355683663859246677105132100377322669627893863885482167305919925159944839, 2978800921927631161807562509445310353414810029862911925227583943849942080514132963605492727604495513988707849133045851539412276254555228149742924149242124724864770049898278052042163392380895275970574317984638058768854065506927848951716677514095183559625442889028813635385408810698294574175092159389388091981, 16200944263352278316040095503540249310705602580329203494665614035841657418101517016718103326928336623132935178377208651067093136976383774189554806135146237406248538919915426183225265103769259990252162411307338473817114996409705345401251435268136647166395894099897737607312110866874944619080871831772376466376, 31551601425575677138046998360378916515711528548963089502535903329268089950335615563205720969393649713416910860593823506545030969355111753902391336139384464585775439245735448030993755229554555004154084649002801255396359097917380427525820249562148313977941413268787799534165652742114031759562268691233834820996, 25288164985739570635307839193110091356864302148147148153228604718807817833935053919412276187989509493755136905193728864674684139319708358686431424793278248263545370628718355096523088238513079652226028236137381367215156975121794485995030822902933639803569133458328681148758392333073624280222354763268512333515]

这里很容易可以知道 $e=9$ （显而易见， $n$ 和 $c$ 也有九组），所以很显然，这题要用到 $e=9$ 的广播攻击

将上面给出的n_list和c_list用sagemath利用CRT求解得出：

m9=3678337284039442047026947312380394506988284605153398380909870598085147736828709178219597429308046538374273111663234962853201175297522552444068549756304348183089003998584929250444862897734669616839072634559776823068102560978738392642133409979083241310818961120830565330801827594023873873703163937572703881578432281109467318674533265052430906776650900523035132668203491899352234368836316318216812572637893433384928785981896373747430646617935503364537613820302679656375356094380483213814869276308187497478084540603362678580814022322799191778371368875742773945120383365613028633102737056410926701477700008313642639347163933146129361496566648131161287075292980980083166106192999528561889437021539352391671756010617540361596164032486633114877739259434431765044242037641759566659268290619705700083536966807192023377334915872207418596226819579720241509860110741821630775501873143209229299530346706612248414951753383716954165108266753409813119293227854442685830689203424064786691447734948037502729127922328149002842971722645909768174575776908113523451541199095073733017029558396658874593357205426105429760517295964966905772455366037986657671195106462661190327510507460112791663031458690187525393979689469548319821181450874331998372947479866557921497942728807505035932385939931524294822439633516457845581452433022749099648076725811489217888688273759202726271093237450290814247396662589614216704#m9为m的9次方

再对 $m9$ 开9次方根可得：

1	m=5364346700993245916083351542951836466599376039702798829478182513243184146028312538778801523615449405915572188751896617305936540801999004614344621214275094

再通过Crypto库中long_to_bytes函数可得：

1	flag{H0w_Fun_13_HAstads_broadca5t_AtTack!}

gcd类型

这种类型主要考察数学推导的能力，直接上例题。

[GKCTF 2021]RRRRsa 1（部分）

题目代码：

pbits = 512
p, q = getPrime(pbits), getPrime(pbits)
n = p * q
hint1 = pow(2020 * p + q, 202020, n)
hint2 = pow(2121 * p + 212121, q, n)
print(f'{n = }')
print(f'{hint1 = }')
print(f'{hint2 = }')
"""
n =
72480597722768310802103225074022304502987810353239303491995392556828592827312126864102279719480413772239054950810362120660174703790228376146053986053171930937388580526219104498648291397309599209554202670080978901954049943834889894306222459711036629282482760872552358198065124168348275611897584923869319730917
hint1 =
70685159982753618117937078087626553902610663214529331305611406765104333038200912863267956767277081926123480288270862897047313253820275507292683667878994502600957911694615683337770022569861106230373836250952155917286151237134316356851059293688768775787985566372022900108303136666429150678266857778726967849907
hint2 =
59397395285145715354919882069200896861665631746130494855994590508589325004636436593048816842106180115714527211321251497281171549276111388361451000025849056493942252398618018816656979043710894623882099581494083699322411790446784391932055982624616996747139852037848608960801937270797966812928286289985647495610
"""

我们可以知道：

$hint1\equiv (2020p+q)^{202020}\ (mod\ n)\\ hint2\equiv (2121p+212121)^{q}\ (mod\ n)$

我们要从上面两个方程中求解 $p$ 和 $q$ ，下面进行数学推导：

首先观察hint1，由二项式定理有：

$(2020p+q)^{202020}=(2020p)^{202020}+(2020p)^{202019}q+\cdots+2020pq^{202019}+q^{202020}$

显然的，右式除 $(2020p)^{202020}$ 与 $q^{202020}$ 两项外均能被 $n$ 整除

所以有：

$hint1\equiv (2020p)^{202020}+q^{202020}\ (mod\ n)$

进一步的，有：

$hint1\equiv(2020p)^{202020}\ (mod\ q)$

现在看到hint2，有：

$hint2\equiv (2121p+212121)^q\ (mod\ q)$

由费马小定理，可以得到：

$hint2\equiv 2121p+212121\ (mod\ q)$

所以：

$(hint2-212121)^{202020}(2020)^{202020}\equiv (2020\cdot2021p)^{202020}\ (mod\ q)$

对于hint1：

$hint1(2121)^{202020}\equiv (2020\cdot2021p)^{202020}\ (mod\ q)$

故：

$hint1(2121)^{202020}-(hint2-212121)^{202020}(2020)^{202020}\equiv 0\ (mod\ q)$

所以有：

$kq=hint1(2121)^{202020}-(hint2-212121)^{202020}(2020)^{202020}$

由于 $n=pq$

所以 $gcd(kq,n)=$

代码如下：

from Crypto.Util.number import *
import gmpy2
n = 72480597722768310802103225074022304502987810353239303491995392556828592827312126864102279719480413772239054950810362120660174703790228376146053986053171930937388580526219104498648291397309599209554202670080978901954049943834889894306222459711036629282482760872552358198065124168348275611897584923869319730917
hint1 = 70685159982753618117937078087626553902610663214529331305611406765104333038200912863267956767277081926123480288270862897047313253820275507292683667878994502600957911694615683337770022569861106230373836250952155917286151237134316356851059293688768775787985566372022900108303136666429150678266857778726967849907
hint2 = 59397395285145715354919882069200896861665631746130494855994590508589325004636436593048816842106180115714527211321251497281171549276111388361451000025849056493942252398618018816656979043710894623882099581494083699322411790446784391932055982624616996747139852037848608960801937270797966812928286289985647495610
kq = gmpy2.powmod(2121,202020,n)*hint1-gmpy2.powmod((hint2-212121)*2020,202020,n)
q = gmpy2.gcd(kq,n)
print(q)

这样就得出了 $q$ ，由此我们就可以顺带求出 $p$ 了。

（还有道题是Geek Challenge 2023的Poly_RSA，但是在写笔记的时候比赛还没结束，就不放出来了，后面写wp的时候再讲推导过程）