中国剩余定理(CRT)

我们设正整数$m_1,m_2,…,m_k$两两互素，得到同余方程组：

$x\equiv a_1\ (\bmod m_1)$ $\ \ \ \ \ \ \ x\equiv a_2\ (\bmod m_2)\ \ ...$ $x\equiv a_k\ (\bmod m_k)$

有整数解，在模$M=m_1m_2…m_k$下的解唯一，解为：

$x\equiv (a_1M_1{M_1}^{-1}+a_2M_2{M_2}^{-1}+...+a_kM_k{M_k}^{-1})\bmod M$

$Mi=\frac{M}{m_i}，M_i^{-1}$是$M_i$模$m_i$的逆元。

$∏$是求积运算符号，类似于$Σ$，求多个数的积。

历史背景

“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”

韩信点兵，士兵站成三人一列，多出来两人；站成五人一列，多出来三人；站成七人一列，多两人。问共有多少人；

　　满足第一条：2,5,8,11,14,17,20,23,26,29….

　　满足第二条：8,13,18,23,28……

　　满足第三条：9,16,23,30……

23同时满足，但是如何去求后面重复的数值？

相当于加上一个数n，n为3,5,7的倍数，在这里，n最小为105，得所有解为：23+105i，i取某个整数就可以得到所有解。

那么，如何让这个结论推广到所有的情况上呢？

当然，几个数求最小公倍数很好求，那么这个23该怎么处理呢？

基本原理

我们的祖先想出了一首诗用来求解：

三人同行七十稀，五树梅花廿一支，七子团圆正半月，除百零五使得知。

三人同行七十稀，把除以3所得的余数用70乘。
五树梅花廿一枝，把除以5所得的余数用21乘。
七子团圆正半月，把除以7所得的余数用15乘。
除百零五便得知，把上述三个积加起来，减去105的倍数，所得的差即为所求。

2×70＋3×21＋2×15=233

233 % 105 =23

在上面的理论中：70是5，7的倍数，21是3,7的倍数，15是3,5的倍数

所找的三个数中，拿70来说，70在作为5,7倍数的同时，还需要满足模3余1，同样，3,7的倍数需要模5余1，3,5的倍数需要模7余1。

原理推广

对于两两互质的一组数$a_1,a_2,a_3……a_n$（数组$A$）；让一个解$x$对于所有在$[1,n]$的整数同时满足$x\bmod a_i = m_i$（$m_i$数组每个元素也为两两互质），这里就可以应用中国剩余定理。

在这里，A就相当于刚才每列站的3, 5, 7人。

$m_i$就相当于余下的2, 3, 2人。

x就是我们求的总人数。

我们可以设$M$为$A$数组所有元素的乘积，找出一个$B$数组使得$b_i$是 $\frac M{a_i}$ 的倍数，而且$b_i\bmod a_i=1$，n直接求最小公倍数可以求出。

这里的B数组中的每一个数就相当于刚才的70, 21, 15。

怎么求B？

由B的意思，我们可以知道bi为M/ai的倍数，$b_i\bmod a_i=1$，就有：$b_i=\frac{M}{a_i} k$，$\frac{M}{a_i} k ≡ 1(\bmod a_i)$。

转换一下：$\frac{M}{a_i} k + a_i j = 1$

A两两互质，M为A中所有数的乘积，$\frac M{a_i}$和$a_i$互质，我们这里可以使用拓展欧几里得解出。

经过上面的推导：我们就可以找到一个解：$x_0 = m_1b_1 + m_2b_2 + m_3b_3+ ….. + m_nb_n$，也就相当于$233=70×2+21×3+152$

要找到其他的解，就增加或减少$nt$ ，$t$为随意的一个整数。

RSA引入CRT

题目给出三组n和c（这里的nc只出现01234，为五进制）：

N = 331310324212000030020214312244232222400142410423413104441140203003243002104333214202031202212403400220031202142322434104143104244241214204444443323000244130122022422310201104411044030113302323014101331214303223312402430402404413033243132101010422240133122211400434023222214231402403403200012221023341333340042343122302113410210110221233241303024431330001303404020104442443120130000334110042432010203401440404010003442001223042211442001413004 
c = 310020004234033304244200421414413320341301002123030311202340222410301423440312412440240244110200112141140201224032402232131204213012303204422003300004011434102141321223311243242010014140422411342304322201241112402132203101131221223004022003120002110230023341143201404311340311134230140231412201333333142402423134333211302102413111111424430032440123340034044314223400401224111323000242234420441240411021023100222003123214343030122032301042243

N = 302240000040421410144422133334143140011011044322223144412002220243001141141114123223331331304421113021231204322233120121444434210041232214144413244434424302311222143224402302432102242132244032010020113224011121043232143221203424243134044314022212024343100042342002432331144300214212414033414120004344211330224020301223033334324244031204240122301242232011303211220044222411134403012132420311110302442344021122101224411230002203344140143044114 
c = 112200203404013430330214124004404423210041321043000303233141423344144222343401042200334033203124030011440014210112103234440312134032123400444344144233020130110134042102220302002413321102022414130443041144240310121020100310104334204234412411424420321211112232031121330310333414423433343322024400121200333330432223421433344122023012440013041401423202210124024431040013414313121123433424113113414422043330422002314144111134142044333404112240344

N = 332200324410041111434222123043121331442103233332422341041340412034230003314420311333101344231212130200312041044324431141033004333110021013020140020011222012300020041342040004002220210223122111314112124333211132230332124022423141214031303144444134403024420111423244424030030003340213032121303213343020401304243330001314023030121034113334404440421242240113103203013341231330004332040302440011324004130324034323430143102401440130242321424020323 
c = 10013444120141130322433204124002242224332334011124210012440241402342100410331131441303242011002101323040403311120421304422222200324402244243322422444414043342130111111330022213203030324422101133032212042042243101434342203204121042113212104212423330331134311311114143200011240002111312122234340003403312040401043021433112031334324322123304112340014030132021432101130211241134422413442312013042141212003102211300321404043012124332013240431242

根据上面给的三组数，我们可以得到：

$m^e ≡ c_1 (\bmod n_1)$

$m^e ≡ c_2 (\bmod n_2)$

$m^e ≡ c_3 (\bmod n_3)$

求整数的乘积：$N=n_1n_2n_3$

求除ni以外的整数乘积：$N_1=\frac N{n_1},N_2=\frac N{n_2},N_3=\frac N{n_3}$

此时，我们可以使用中国剩余定理求解出其中的$m^e$，进而求出$m$。

由于这里模$n$，当$m^e<N$时，才可以用这个方法。因为最终求得的是将同余式转换为了等式，等式两边都不超过$N$：
$c=m^e(\bmod N)$

在模$N$的意义下，方程组只有唯一解：

$m^e=(\sum c_iN_iN_i')\bmod N$

所以可以求得$m^e$，并且对$m$开$e$次方可得到最终的$m$。

import gmpy2
from Crypto.Util.number import *

n1 = int('331310324212000030020214312244232222400142410423413104441140203003243002104333214202031202212403400220031202142322434104143104244241214204444443323000244130122022422310201104411044030113302323014101331214303223312402430402404413033243132101010422240133122211400434023222214231402403403200012221023341333340042343122302113410210110221233241303024431330001303404020104442443120130000334110042432010203401440404010003442001223042211442001413004',5)
c1 = int('310020004234033304244200421414413320341301002123030311202340222410301423440312412440240244110200112141140201224032402232131204213012303204422003300004011434102141321223311243242010014140422411342304322201241112402132203101131221223004022003120002110230023341143201404311340311134230140231412201333333142402423134333211302102413111111424430032440123340034044314223400401224111323000242234420441240411021023100222003123214343030122032301042243',5)

n2 = int('302240000040421410144422133334143140011011044322223144412002220243001141141114123223331331304421113021231204322233120121444434210041232214144413244434424302311222143224402302432102242132244032010020113224011121043232143221203424243134044314022212024343100042342002432331144300214212414033414120004344211330224020301223033334324244031204240122301242232011303211220044222411134403012132420311110302442344021122101224411230002203344140143044114',5)
c2 = int('112200203404013430330214124004404423210041321043000303233141423344144222343401042200334033203124030011440014210112103234440312134032123400444344144233020130110134042102220302002413321102022414130443041144240310121020100310104334204234412411424420321211112232031121330310333414423433343322024400121200333330432223421433344122023012440013041401423202210124024431040013414313121123433424113113414422043330422002314144111134142044333404112240344',5)

n3 = int('332200324410041111434222123043121331442103233332422341041340412034230003314420311333101344231212130200312041044324431141033004333110021013020140020011222012300020041342040004002220210223122111314112124333211132230332124022423141214031303144444134403024420111423244424030030003340213032121303213343020401304243330001314023030121034113334404440421242240113103203013341231330004332040302440011324004130324034323430143102401440130242321424020323',5)
c3 = int('10013444120141130322433204124002242224332334011124210012440241402342100410331131441303242011002101323040403311120421304422222200324402244243322422444414043342130111111330022213203030324422101133032212042042243101434342203204121042113212104212423330331134311311114143200011240002111312122234340003403312040401043021433112031334324322123304112340014030132021432101130211241134422413442312013042141212003102211300321404043012124332013240431242',5)

N=n1*n2*n3
N1=N//n1;N2=N//n2;N3=N//n3
m_e=(c1*N1*gmpy2.invert(N1,n1)+c2*N2*gmpy2.invert(N2,n2)+c3*N3*gmpy2.invert(N3,n3))%N
for e in range(1,100):#e未知，低位爆破一下
  flag=long_to_bytes(gmpy2.iroot(m_e,e)[0])
  if flag[-1]==125:
        print(flag)#b'noxCTF{D4mn_y0u_h4s74d_wh47_4_b100dy_b4s74rd!}'

long_to_bytes转换的本质还是ASCII码，”}”ASCII为125，可以用这个筛选出符合条件的flag。

实际上，long_to_bytes是在函数内部自行做了先把数字转16进制再将16进制数两两一组转换成ASCII码对应字符。

在libnum库里，有solve_crt函数帮助我们计算中国剩余定理：以上代码可以简化如下：

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

n1 = int('331310324212000030020214312244232222400142410423413104441140203003243002104333214202031202212403400220031202142322434104143104244241214204444443323000244130122022422310201104411044030113302323014101331214303223312402430402404413033243132101010422240133122211400434023222214231402403403200012221023341333340042343122302113410210110221233241303024431330001303404020104442443120130000334110042432010203401440404010003442001223042211442001413004',5)
c1 = int('310020004234033304244200421414413320341301002123030311202340222410301423440312412440240244110200112141140201224032402232131204213012303204422003300004011434102141321223311243242010014140422411342304322201241112402132203101131221223004022003120002110230023341143201404311340311134230140231412201333333142402423134333211302102413111111424430032440123340034044314223400401224111323000242234420441240411021023100222003123214343030122032301042243',5)

n2 = int('302240000040421410144422133334143140011011044322223144412002220243001141141114123223331331304421113021231204322233120121444434210041232214144413244434424302311222143224402302432102242132244032010020113224011121043232143221203424243134044314022212024343100042342002432331144300214212414033414120004344211330224020301223033334324244031204240122301242232011303211220044222411134403012132420311110302442344021122101224411230002203344140143044114',5)
c2 = int('112200203404013430330214124004404423210041321043000303233141423344144222343401042200334033203124030011440014210112103234440312134032123400444344144233020130110134042102220302002413321102022414130443041144240310121020100310104334204234412411424420321211112232031121330310333414423433343322024400121200333330432223421433344122023012440013041401423202210124024431040013414313121123433424113113414422043330422002314144111134142044333404112240344',5)

n3 = int('332200324410041111434222123043121331442103233332422341041340412034230003314420311333101344231212130200312041044324431141033004333110021013020140020011222012300020041342040004002220210223122111314112124333211132230332124022423141214031303144444134403024420111423244424030030003340213032121303213343020401304243330001314023030121034113334404440421242240113103203013341231330004332040302440011324004130324034323430143102401440130242321424020323',5)
c3 = int('10013444120141130322433204124002242224332334011124210012440241402342100410331131441303242011002101323040403311120421304422222200324402244243322422444414043342130111111330022213203030324422101133032212042042243101434342203204121042113212104212423330331134311311114143200011240002111312122234340003403312040401043021433112031334324322123304112340014030132021432101130211241134422413442312013042141212003102211300321404043012124332013240431242',5)

m_e=solve_crt([c1,c2,c3],[n1,n2,n3])#理论上只要两组数据就能求解中国剩余定理，solve_crt([c1,c2],[n1,n2])也能求解
for e in range(1,100):
    flag=long_to_bytes(gmpy2.iroot(m_e,e)[0])
    if flag[-1]==125:
        print(flag)#b'noxCTF{D4mn_y0u_h4s74d_wh47_4_b100dy_b4s74rd!}'

低加密指数广播攻击

广播就是发送方将一份明文进行多份加密，每份使用不同的n，但是指数e相同且很小，因此我们只要得到多份密文和对应的n就可以利用中国剩余定理进行解密。

例题

[{"c": 7366067574741171461722065133242916080495505913663250330082747465383676893970411476550748394841437418105312353971095003424322679616940371123028982189502042, "e": 10, "n": 25162507052339714421839688873734596177751124036723831003300959761137811490715205742941738406548150240861779301784133652165908227917415483137585388986274803},
{"c": 21962825323300469151795920289886886562790942771546858500842179806566435767103803978885148772139305484319688249368999503784441507383476095946258011317951461, "e": 10, "n": 23976859589904419798320812097681858652325473791891232710431997202897819580634937070900625213218095330766877190212418023297341732808839488308551126409983193},
{"c": 6569689420274066957835983390583585286570087619048110141187700584193792695235405077811544355169290382357149374107076406086154103351897890793598997687053983, "e": 10, "n": 18503782836858540043974558035601654610948915505645219820150251062305120148745545906567548650191832090823482852604346478335353784501076761922605361848703623},
{"c": 4508246168044513518452493882713536390636741541551805821790338973797615971271867248584379813114125478195284692695928668946553625483179633266057122967547052, "e": 10, "n": 23383087478545512218713157932934746110721706819077423418060220083657713428503582801909807142802647367994289775015595100541168367083097506193809451365010723},
{"c": 22966105670291282335588843018244161552764486373117942865966904076191122337435542553276743938817686729554714315494818922753880198945897222422137268427611672, "e": 10, "n": 31775649089861428671057909076144152870796722528112580479442073365053916012507273433028451755436987054722496057749731758475958301164082755003195632005308493},
{"c": 17963313063405045742968136916219838352135561785389534381262979264585397896844470879023686508540355160998533122970239261072020689217153126649390825646712087, "e": 10, "n": 22246342022943432820696190444155665289928378653841172632283227888174495402248633061010615572642126584591103750338919213945646074833823905521643025879053949},
{"c": 1652417534709029450380570653973705320986117679597563873022683140800507482560482948310131540948227797045505390333146191586749269249548168247316404074014639, "e": 10, "n": 25395461142670631268156106136028325744393358436617528677967249347353524924655001151849544022201772500033280822372661344352607434738696051779095736547813043},
{"c": 15585771734488351039456631394040497759568679429510619219766191780807675361741859290490732451112648776648126779759368428205194684721516497026290981786239352, "e": 10, "n": 32056508892744184901289413287728039891303832311548608141088227876326753674154124775132776928481935378184756756785107540781632570295330486738268173167809047},
{"c": 8965123421637694050044216844523379163347478029124815032832813225050732558524239660648746284884140746788823681886010577342254841014594570067467905682359797, "e": 10, "n": 52849766269541827474228189428820648574162539595985395992261649809907435742263020551050064268890333392877173572811691599841253150460219986817964461970736553},
{"c": 13560945756543023008529388108446940847137853038437095244573035888531288577370829065666320069397898394848484847030321018915638381833935580958342719988978247, "e": 10, "n": 30415984800307578932946399987559088968355638354344823359397204419191241802721772499486615661699080998502439901585573950889047918537906687840725005496238621}]

题目给出了多组n和c，以及相同的e，我们可以使用中国剩余定理对其进行攻击：

在这里，由于组数过多，如果不用库函数的话不方便像上面那样挨个计算，可以建立数组遍历进行计算：

import gmpy2
from Crypto.Util.number import *

e = 10
c = [7366067574741171461722065133242916080495505913663250330082747465383676893970411476550748394841437418105312353971095003424322679616940371123028982189502042,
21962825323300469151795920289886886562790942771546858500842179806566435767103803978885148772139305484319688249368999503784441507383476095946258011317951461,
6569689420274066957835983390583585286570087619048110141187700584193792695235405077811544355169290382357149374107076406086154103351897890793598997687053983,
4508246168044513518452493882713536390636741541551805821790338973797615971271867248584379813114125478195284692695928668946553625483179633266057122967547052,
22966105670291282335588843018244161552764486373117942865966904076191122337435542553276743938817686729554714315494818922753880198945897222422137268427611672,
17963313063405045742968136916219838352135561785389534381262979264585397896844470879023686508540355160998533122970239261072020689217153126649390825646712087,
1652417534709029450380570653973705320986117679597563873022683140800507482560482948310131540948227797045505390333146191586749269249548168247316404074014639,
15585771734488351039456631394040497759568679429510619219766191780807675361741859290490732451112648776648126779759368428205194684721516497026290981786239352,
8965123421637694050044216844523379163347478029124815032832813225050732558524239660648746284884140746788823681886010577342254841014594570067467905682359797,
13560945756543023008529388108446940847137853038437095244573035888531288577370829065666320069397898394848484847030321018915638381833935580958342719988978247]

n = [25162507052339714421839688873734596177751124036723831003300959761137811490715205742941738406548150240861779301784133652165908227917415483137585388986274803,
23976859589904419798320812097681858652325473791891232710431997202897819580634937070900625213218095330766877190212418023297341732808839488308551126409983193,
18503782836858540043974558035601654610948915505645219820150251062305120148745545906567548650191832090823482852604346478335353784501076761922605361848703623,
23383087478545512218713157932934746110721706819077423418060220083657713428503582801909807142802647367994289775015595100541168367083097506193809451365010723,
31775649089861428671057909076144152870796722528112580479442073365053916012507273433028451755436987054722496057749731758475958301164082755003195632005308493,
22246342022943432820696190444155665289928378653841172632283227888174495402248633061010615572642126584591103750338919213945646074833823905521643025879053949,
25395461142670631268156106136028325744393358436617528677967249347353524924655001151849544022201772500033280822372661344352607434738696051779095736547813043,
32056508892744184901289413287728039891303832311548608141088227876326753674154124775132776928481935378184756756785107540781632570295330486738268173167809047,
52849766269541827474228189428820648574162539595985395992261649809907435742263020551050064268890333392877173572811691599841253150460219986817964461970736553,
30415984800307578932946399987559088968355638354344823359397204419191241802721772499486615661699080998502439901585573950889047918537906687840725005496238621]

N=1
m_e=0
for i in range(len(n)):#计算n数组所有数的乘积
  N*=n[i]
for i in range(len(n)):#计算m^e,采用中国剩余定理
  m_e=m_e+c[i]*N//n[i]*gmpy2.invert(N//n[i],n[i])
m_e=m_e%N
print(long_to_bytes(gmpy2.iroot(m_e,e)[0]))

扩展中国剩余定理

在学习CRT中我们了解到构成求解CRT的方程组模数需要两两互质，如果模数是不互质的，可以通过合并相邻两组方程的方式进行逐步求解，这就是扩展中国剩余定理。

扩展中国剩余定理跟中国剩余定理几乎没有关系，扩展CRT是用扩展欧几里得，CRT是用构造的思想。

根据同样的同余方程组，但是模数不互素：

$\begin{cases}x\equiv a_1(\bmod m_1)\\x\equiv a_2(\bmod m_2)\\x\equiv a_3(\bmod m_3)\\...\\x\equiv a_n(\bmod m_n)\end{cases}$

选择前两个式子，转换成等式：

$\begin{cases}x=k_1m_1+a_1\\x=k_2m_2+a_2\end{cases}$

两式子相减得到$k_1m_1-k_2m_2=a_2-a_1$，把$k_1,-k_2$看做$x_k,y_k$，式子就能转化为：

$x_km_1+y_km_2=a_2-a_1$

根据裴蜀定理，当$\gcd(m_1,m_2)|(a_2-a_1)$时，就可以使用扩展欧几里得算法求出系数$x_k,y_k$，这里计算得到的式子为：

$x_0m_1+y_0m_2=\gcd(m_1,m_2)$

为了求得$x_k,y_k$，可以对式子两边同时乘$\frac {a_2-a_1}{\gcd(m_1,m_2)}$，得到特解：

$\begin{cases}x_{k_1}=x_0\frac {a_2-a_1}{\gcd(m_1,m_2)}\\y_{k_1}=y_0\frac {a_2-a_1}{\gcd(m_1,m_2)}\end{cases}$

我们需要用过特殊解来构造一般解，一般式子为：

$x_0m_1+y_0m_2=n\gcd(m_1,m_2)$

特殊解变形为：

$\begin{cases}x_{k}=x_{k_1}+n\frac {m_2}{\gcd(m_1,m_2)}\\y_{k}=y_{k_1}-n\frac {m_1}{\gcd(m_1,m_2)}\end{cases}$

代入$x_0m_1+y_0m_2=\gcd(m_1,m_2)$仍成立，此时构造的$x_k,y_k$就是通解。

现在将得到的通解代入到最开始的式子$x=k_1m_1+a_1$：

$x=n\frac {m_1m_2}{\gcd(m_1,m_2)}+x_{k_1}m_1+a_1$

根据数论的有关知识可以知道$\mathrm{lcm}(m_1,m_2)=\frac{m_1m_2}{\gcd(m_1,m_2)}$，原式可以进一步化为：

$x=n\mathrm{lcm}(m_1,m_2)+x_{k_1}m_1+a_1$

化为同余式子：

$x\equiv k_1m_1+a_1(\bmod \mathrm{lcm}(m_1,m_2))$ $\begin{cases}r=k_1m_1+a_1\\m=\mathrm{lcm}(m_1,m_2)\end{cases}$

现在，我们就把两个同余式合并为了一个同余方程：

$x\equiv r(\bmod m)$

那么，如果我们不断的合并，进行$n-1$次合并，就能将$n$个同余方程合并为一个同余方程，如果只有一个同余方程，就可以使用扩展欧几里得算法进行计算。

求$d$

import gmpy2
from Crypto.Util.number import *

p = getPrime(512)
q = getPrime(512)
r = getPrime(512)
e = getPrime(32)
print(e)
n = p*q*r
phi = (p-1)*(q-1)*(r-1)
d = gmpy2.invert(e,phi)
dp = d%((q-1)*(r-1))
dq = d%((p-1)*(r-1))
dr = d%((p-1)*(q-1))
flag = 'flag{XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX}'
m = bytes_to_long(flag.encode())
c = pow(m,e,n)

print(p)
print(q)
print(r)
print(dp)
print(dq)
print(dr)
print(c)

p=12922128058767029848676385650461975663483632970994721128398090402671357430399910236576943902580268365115559040908171487273491136108931171215963673857907721
q=10395910293559541454979782434227114401257890224810826672485874938639616819909368963527556812339196570118998080877100587760101646884011742783881592586607483
r=8104533688439480164488403019957173637520526666352540480766865791142556044817828133446063428255474375204188144310967625626318466189746446739697284656837499
dp=73360412924315743410612858109886169233122608813546859531995431159702281180116580962235297605024326120716590757069707814371806343766956894408106019058184354279568525768909190843389534908163730972765221403797428735591146943727032277163147380538250142612444372315262195455266292156566943804557623319253942627829
dq=40011003982913118920477233564329052389422276107266243287367766124357736739027781899850422097218506350119257015460291153483339485727984512959771805645640899525080850525273304988145509506962755664208407488807873672040970416096459662677968243781070751482234692575943914243633982505045357475070019527351586080273
dr=21504040939112983125383942214187695383459556831904800061168077060846983552476434854825475457749096404504088696171780970907072305495623953811379179449789142049817703543458498244186699984858401903729236362439659600561895931051597248170420055792553353578915848063216831827095100173180270649367917678965552672673
c=220428832901130282093087304800127910055992783874826238869471313726515822196746908777026147887315019800546695346099376727742597231512404648514329911088048902389321230640565683145565701498095660019604419213310866468276943241155853029934366950674139215056682438149221374543291202295130547776549069333898123270448986380025937093195496539532193583979030254746589985556996040224572481200667498253900563663950531345601763949337787268884688982469744380006435119997310653

这个题目中我们并不知道$e,d$，直接进行求解肯定是解不出来的，但是给了$dp,dq,dr$，先观察一下三个式子，尝试使用扩展中国剩余定理：

$\begin{cases}dp\equiv d(\bmod (q-1)(r-1))\\dq\equiv d(\bmod (p-1)(r-1))\\dr\equiv d(\bmod (p-1)(q-1))\end{cases}$

from Crypto.Util.number import *
import gmpy2


p=12922128058767029848676385650461975663483632970994721128398090402671357430399910236576943902580268365115559040908171487273491136108931171215963673857907721
q=10395910293559541454979782434227114401257890224810826672485874938639616819909368963527556812339196570118998080877100587760101646884011742783881592586607483
r=8104533688439480164488403019957173637520526666352540480766865791142556044817828133446063428255474375204188144310967625626318466189746446739697284656837499
dp=73360412924315743410612858109886169233122608813546859531995431159702281180116580962235297605024326120716590757069707814371806343766956894408106019058184354279568525768909190843389534908163730972765221403797428735591146943727032277163147380538250142612444372315262195455266292156566943804557623319253942627829
dq=40011003982913118920477233564329052389422276107266243287367766124357736739027781899850422097218506350119257015460291153483339485727984512959771805645640899525080850525273304988145509506962755664208407488807873672040970416096459662677968243781070751482234692575943914243633982505045357475070019527351586080273
dr=21504040939112983125383942214187695383459556831904800061168077060846983552476434854825475457749096404504088696171780970907072305495623953811379179449789142049817703543458498244186699984858401903729236362439659600561895931051597248170420055792553353578915848063216831827095100173180270649367917678965552672673
c=220428832901130282093087304800127910055992783874826238869471313726515822196746908777026147887315019800546695346099376727742597231512404648514329911088048902389321230640565683145565701498095660019604419213310866468276943241155853029934366950674139215056682438149221374543291202295130547776549069333898123270448986380025937093195496539532193583979030254746589985556996040224572481200667498253900563663950531345601763949337787268884688982469744380006435119997310653

n = 3
a = [dp,dq,dr]
m=[(q-1)*(r-1),(p-1)*(r-1),(p-1)*(q-1)]

def CRText():
    if n == 1:
        return a[0]

    for i in range(n):
        gcd ,x ,y = gmpy2.gcdext(m[0], m[i])

        lcm = m[i] // gcd
        x = (a[i] - a[0]) // gcd * x % lcm
        a[0] = x * m[0] + a[0]
        m[0] = m[0] * m[i] // gcd
        a[0] = (a[0] % m[0] + m[0]) % m[0]
    return a[0]

d = CRText()
m=pow(c,d,p*q*r)
print(long_to_bytes(m))

求$c$

from Crypto.Util.number import *
import random
# from secret import flag
flag=''
table='abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'
pad=100-len(flag)
for i in range(pad):
    flag+=random.choice(table).encode()
e=343284449
m=bytes_to_long(flag)
assert m>(1<<512)
assert m<(1<<1024)
p=getPrime(512)
q=getPrime(512)
r=getPrime(512)
print('p=',p)
print('q=',q)
print('r=',r)
n1=p*q
n2=q*r
c1=pow(m,e,n1)
c2=pow(m,e,n2)
print('c1=',c1)
print('c2=',c2)


p= 11820891196647569262137841192985418014377132106496147254821784946481523526822939129065042819464351666077658751406165276121125571355594004514547517855730743
q= 10450390015864176713581330969519712299844487112687677452105216477861582967322473997670559995588440097951786576039009337782247912476227937589298529580432797
r= 9484954066160968219229920429258150817546418633451929876581842443665029377287119340232501682142185708534413073877473741393278935479791561681402673403009771

c1= 69574855207460025252857869494766338442370688922127811393280455950372371842144946699073877876005649281006116543528211809466226185922844601714337317797534664683681334132261584497953105754257846471069875622054326463757746293958069752489458646460121725019594141157667480846709081917530190233900184428943585065316
c2= 66183492015178047844987766781469734325646160179923242098082430373061510938987908656007752256556018402101435698352339429316390909525615464024332856855411414576031970267795270882896721069952171988506477519737923165566896609181813523905810373359029413963666924039857159685161563252396502381297700252749204993228

这个题可以发现$e$是$q$的因子，而且还对flag做了填充处理，直接解密是肯定不行的，思想是通过扩展中国剩余定理求出$n=pr$的对应的密文进行解密：

$\begin{cases}c_1\equiv m^e(\bmod n_1)\\c_2\equiv m^e(\bmod n_2)\end{cases}$

最后求得的$m^e$可以放在模$pr$域中，进行求解：

from Crypto.Util.number import *
import gmpy2


p = 11820891196647569262137841192985418014377132106496147254821784946481523526822939129065042819464351666077658751406165276121125571355594004514547517855730743
q = 10450390015864176713581330969519712299844487112687677452105216477861582967322473997670559995588440097951786576039009337782247912476227937589298529580432797
r = 9484954066160968219229920429258150817546418633451929876581842443665029377287119340232501682142185708534413073877473741393278935479791561681402673403009771
e = 343284449
c1 = 69574855207460025252857869494766338442370688922127811393280455950372371842144946699073877876005649281006116543528211809466226185922844601714337317797534664683681334132261584497953105754257846471069875622054326463757746293958069752489458646460121725019594141157667480846709081917530190233900184428943585065316
c2 = 66183492015178047844987766781469734325646160179923242098082430373061510938987908656007752256556018402101435698352339429316390909525615464024332856855411414576031970267795270882896721069952171988506477519737923165566896609181813523905810373359029413963666924039857159685161563252396502381297700252749204993228
n = 2
a = [c1, c2]
m = [p * q, q * r]


def CRText():
    if n == 1:
        return a[0]

    for i in range(n):
        gcd, x, y = gmpy2.gcdext(m[0], m[i])

        lcm = m[i] // gcd
        x = (a[i] - a[0]) // gcd * x % lcm
        a[0] = x * m[0] + a[0]
        m[0] = m[0] * m[i] // gcd
        a[0] = (a[0] % m[0] + m[0]) % m[0]
    return a[0]


c = CRText()
n = p * r
phi = (p - 1) * (r - 1)
d = gmpy2.invert(e, phi)
print(long_to_bytes(pow(c, d, n)))

公钥解析和加密协议

SSH和SSL都是加密协议，用于保护网络通信的安全性和完整性。

SSH（Secure Shell）是一种网络协议，用于远程访问和管理服务器。它提供了加密的连接和认证机制，使得数据传输更加安全。SSH通常用于远程登录、文件传输和远程执行命令等操作。SSH通常基于TCP/IP，使用公钥加密和私钥解密的方式来保护通信的安全性。

SSL（Secure Sockets Layer）是一种协议，用于在互联网上建立安全的通信通道。它可以在客户端和服务器之间建立加密的连接，保护数据的隐私和完整性。SSL最初是由网景公司开发的，后来被标准化为TLS（Transport Layer Security）。SSL/TLS通常用于保护Web浏览器和Web服务器之间的通信，以及其他类型的网络应用程序。

虽然SSH和SSL/TLS都提供了加密和认证机制，但它们的应用场景和安全需求有所不同。SSH通常用于远程管理和维护服务器，需要保护管理者的身份和服务器的机密信息；而SSL/TLS通常用于保护Web应用程序和电子商务等网络应用，需要保护用户的身份和敏感信息。

PEM（Privacy-Enhanced Mail）是一种常见的文件格式，通常用于存储加密证书、私钥和其他与网络安全相关的敏感信息。

对于SSL的公钥解析，这种题目会提供两个文件，一个key文件，一个enc文件，我们需要利用key文件提取n和e，进而破解enc文件。

用记事本打开key文件，可以得到如下加密信息：

——-BEGIN PUBLIC KEY——-
MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhAMAzLFxkrkcYL2wch21CM2kQVFpY9+7+
/AvKr1rzQczdAgMBAAE=
——-END PUBLIC KEY——-

如何破解这段加密后的文本，一种方式是可以使用公钥解析网站来解析：

SSL在线工具-公钥解析 (hiencode.com)

或者导入Crypto库直接获得n和e（注意函数末尾添加的内容区别决定输出对象）：

from Crypto.PublicKey import RSA
key = RSA.import_key(open("pub.key").read()).export_key#先补全key路径信息
print(key)
#<bound method RsaKey.export_key of RsaKey(n=86934482296048119190666062003494800588905656017203025617216654058378322103517, e=65537)>
key = RSA.import_key(open("pub.key").read()).n
print(key)
#86934482296048119190666062003494800588905656017203025617216654058378322103517
key = RSA.import_key(open("pub.key").read()).e
print(key)
#65537

获得了n和e之后，我们想办法分解模数后，使用rsa库直接解密，用法如下：

import gmpy2
import rsa

e=65537
p = 285960468890451637935629440372639283459
q = 304008741604601924494328155975272418463
n=p*q
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
key = rsa.PrivateKey(n,e,d,q,p)         
with open("flag.enc","rb+") as f:      
    f = f.read()
    print(rsa.decrypt(f,key))
#b'flag{decrypt_256}\n'

了解了上面的大致理论之后，下面介绍几种和密钥相关的题目。

私钥泄露问题

from Crypto.PublicKey import RSA
import libnum
import gmpy2
import uuid

flag = "flag{" + str(uuid.uuid4()) + "}"
print(flag)
m = libnum.s2n(flag)

p = libnum.generate_prime(1024)
q = gmpy2.next_prime(p)
n = p * q
e = 65537
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi)
m = libnum.s2n(flag)
c = pow(m, e, n)
c1 = libnum.n2s(int(c))

with open("flag.pem", "wb") as f:
    f.write(c1)
rsa_components = (int(n), int(e), int(d), int(p), int(q))
keypair = RSA.construct(rsa_components)
with open("pubckey.pem", "wb") as f:
    f.write(keypair.exportKey())

得到两个文件，一个flag.pem，一个pubckey.pem，使用RSA库进行的加密，直接用RSA库的importKey就可以进行解密：

from Crypto.PublicKey import RSA
import libnum

with open("flag.pem", 'rb') as f:
    c = int(f.read().hex(),16)

with open("pubckey.pem", 'rb') as f:
    key = f.read()

rsakey = RSA.importKey(key)
# print(rsakey)

d = rsakey.d
n = rsakey.n
m = pow(c,d,n)
print(libnum.n2s(m))

模数分解问题

实际上题目才不会傻到连私钥都提供给我们，通常是提供模数和$e$，如果针对特定情况生成的$n$，可以进行分解并破解：

from Crypto.PublicKey import RSA
import libnum
import gmpy2
import uuid

flag = "flag{" + str(uuid.uuid4()) + "}"
print(flag)
m = libnum.s2n(flag)

p = libnum.generate_prime(1024)
q = gmpy2.next_prime(p)
n = p * q
e = 65537
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi)
m = libnum.s2n(flag)
c = pow(m, e, n)
c1 = libnum.n2s(int(c))

with open("flag1.pem", "wb") as f:
    f.write(c1)
rsa_components = (int(n), int(e))
keypair = RSA.construct(rsa_components)
with open('pubckey1.pem', 'wb') as f:
    f.write(keypair.exportKey())

from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
import libnum, sympy, gmpy2

with open("flag1.pem", "rb") as f:
    c = f.read()
c = libnum.s2n(c)
with open("pubckey1.pem", "rb") as f:
    key = f.read()
rsakey = RSA.importKey(key)
n = rsakey.n
e = rsakey.e
phi = int(sympy.totient(n))
d = gmpy2.invert(e, phi)
m = pow(c, d, n)
print(libnum.n2s(int(m)))

OAEP

OAEP（Optimal Asymmetric Encryption Padding）在加密过程中，使用RSA等非对称加密算法加密数据。为了增加安全性，需要对待加密的数据进行填充。OAEP利用随机数和哈希函数的特性来增加加密数据的复杂性和随机性。

使用OAEP填充时，待加密的数据会先经过一个哈希函数，生成一个哈希值（通常用SHA-1或SHA-256等）。然后，将该哈希值与随机生成的填充数据进行异或运算。最后，将结果与原始数据进行拼接，形成一个新的数据块，再使用非对称加密算法进行加密。

在解密过程中，同样使用OAEP填充方案。解密时，首先对密文进行解密得到一个新的数据块，然后对该数据块进行逆操作，还原填充前的数据。最后，从还原后的数据中提取出原始数据。

OAEP填充方案提供了比传统的非对称加密更高的安全性，并且能够防范对抗选择明文攻击等攻击方式。它被广泛应用于各种加密协议和算法中。

from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
import libnum
import gmpy2
import uuid

flag = "flag{" + str(uuid.uuid4()) + "}"
print(flag)
flag = flag.encode()

p = libnum.generate_prime(1024)
q = gmpy2.next_prime(p)
n = p * q
e = 65537
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi)

rsa_components = (int(n), int(e), int(d))
keypair = RSA.construct(rsa_components)
with open('prikey2.pem', 'wb') as f:
    f.write(keypair.exportKey())

rsa_components = (int(n), e)
arsa = RSA.construct(rsa_components)
rsakey = RSA.importKey(arsa.exportKey())
rsakey = PKCS1_OAEP.new(rsakey)
c = rsakey.encrypt(flag)
with open("flag2.pem", "wb") as f:
    f.write(c)

pycryptodome库提供了进行OAEP加密的操作，当然也提供了解密的操作，需要提供公私钥：

from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP

with open("flag2.pem", 'rb') as f:
    ciphertext = f.read()
with open("prikey2.pem", 'rb') as f:
    key = f.read()

rsakey = RSA.importKey(key)
cipher = PKCS1_OAEP.new(rsakey)
message = cipher.decrypt(ciphertext)
print(message)

RSA学习笔记（三）