简述RSA工作原理
- 要加密的信息为m，加密后的信息为c
- 模n，计算出两个质数p和q，p和q计算欧拉函数值φ(n)
- 欧拉函数值φ(n)，$φ(n)=(p-1)(q-1)$
- 公钥参数e和私钥参数d，可由欧拉函数值计算出，$ed≡1 (mod φ(n))$
- 加密：$m^e ≡ c (mod n)$
- 解密：$c^d ≡ m (mod n)$
算法基础
裴蜀定理
因为翻译版本的不同，这个定理可能还会被叫做贝祖定理等。
裴蜀定理是这样被描述的：
满足
文字描述：对于任意整数a,b，都存在一对整数x,y，使得$ax+by=gcd(a,b)$成立
证明：
用欧几里得算法求解这个函数的过程：
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
|
显然是一个递归求解的函数，在递归到最后时，$b=0$,不管$a$等于多少，这是必定有一组整数$x=1,y=0$使得：
0和任何数的最大公约数都等于原数
那么通过这个递归的过程进行回溯。当$b>0$时，程序继续运行：$gcd(b,a\%b)=gcd(a,b)$，因为$a\%b=a-b[a/b]$，所以有以下推导：
令$x’=y,y’=x-[a/b]y$，得出
因为欧几里得算法的实现是递归的，而我们已经推出其中一个递归过程的实现，那么其他的递归过程就可以借助数学归纳法，一层层地向上推，必然会得出最终结论。
证毕
应用
裴蜀定理：
那么可以推出：如果一个数m满足：$ax+by=m$，那么这个m一定是$gcd(a,b)$的倍数。
那么对于一个经典方程$ax+by=1$，利用裴蜀定理，我们有：$gcd(a,b)=1$，即a,b一定互质。
扩展欧几里得算法
回到裴蜀定理：
对于这个不定方程，如果存在一组合法的解$(x,y)$，那么一定会有$gcd(a,b)|m$，即m是$gcd(a,b)$的倍数。那么现在我不仅想知道到底有没有解，而是想知道在有解的情况下，这个解到底是多少。
这就是求解不定方程的过程。这个解决的算法就叫做扩展欧几里得算法。
可以发现，我们求解不定方程其实就是要求解一组合法的$(x,y)$，那么根据裴蜀定理的证明（基于欧几里得算法，采用递归的数学归纳），可以发现$x,y$的互相推导的关系。
这种采取递归来求解$x,y$的方法就叫做扩展欧几里得算法。
int exgcd(int a,int b,int &x,int &y)
{
if(b==0)
{
x=1,y=0;
return a;
}
int d=exgcd(b,a%b,x,y);
int k=x;
x=y;
y=k-a/b*y;
return d;
}
|
扩展欧几里得算法的实现基于裴蜀定理的证明。实质上相当于在做欧几里得算法（普通GCD）的时候对不定方程$ax+by=m$的$x,y$也做了更改。所以经过扩展欧几里得算法处理过的$x,y$就已经是一组合法的可行解了。
共模攻击
当n不变的情况下，知道n,e1,e2,c1,c2 可以在不知道d1,d2的情况下，解出m
假设，e1和e2互质，即$gcd(e1,e2)=1$,则一定有,式中s1,s2均为整数，但是一正一负。
通过扩展欧几里得算法，我们可以的到式子的一组解(s1,s2)，假设s1为正数，s2为负数
因为
所以
根据模运算的性质可以简化为
即
之前提到，所以
即
在数论模运算中，要求一个数的负数次幂，与常规方法并不一样。比如此处要求c2的s2次幂，就要先计算c2的模反元素c2r，然后求c2r的-s2次幂，找到s1的模反元素
题目——[BJDCTF2020]rsa_output
{21058339337354287847534107544613605305015441090508924094198816691219103399526800112802416383088995253908857460266726925615826895303377801614829364034624475195859997943146305588315939130777450485196290766249612340054354622516207681542973756257677388091926549655162490873849955783768663029138647079874278240867932127196686258800146911620730706734103611833179733264096475286491988063990431085380499075005629807702406676707841324660971173253100956362528346684752959937473852630145893796056675793646430793578265418255919376323796044588559726703858429311784705245069845938316802681575653653770883615525735690306674635167111,2767}
{21058339337354287847534107544613605305015441090508924094198816691219103399526800112802416383088995253908857460266726925615826895303377801614829364034624475195859997943146305588315939130777450485196290766249612340054354622516207681542973756257677388091926549655162490873849955783768663029138647079874278240867932127196686258800146911620730706734103611833179733264096475286491988063990431085380499075005629807702406676707841324660971173253100956362528346684752959937473852630145893796056675793646430793578265418255919376323796044588559726703858429311784705245069845938316802681575653653770883615525735690306674635167111,3659}
message1=20152490165522401747723193966902181151098731763998057421967155300933719378216342043730801302534978403741086887969040721959533190058342762057359432663717825826365444996915469039056428416166173920958243044831404924113442512617599426876141184212121677500371236937127571802891321706587610393639446868836987170301813018218408886968263882123084155607494076330256934285171370758586535415136162861138898728910585138378884530819857478609791126971308624318454905992919405355751492789110009313138417265126117273710813843923143381276204802515910527468883224274829962479636527422350190210717694762908096944600267033351813929448599
message2=11298697323140988812057735324285908480504721454145796535014418738959035245600679947297874517818928181509081545027056523790022598233918011261011973196386395689371526774785582326121959186195586069851592467637819366624044133661016373360885158956955263645614345881350494012328275215821306955212788282617812686548883151066866149060363482958708364726982908798340182288702101023393839781427386537230459436512613047311585875068008210818996941460156589314135010438362447522428206884944952639826677247819066812706835773107059567082822312300721049827013660418610265189288840247186598145741724084351633508492707755206886202876227
|
有了以上的知识基础，这个题目就迎刃而解了
import gmpy2
from Crypto.Util.number import *
n = 21058339337354287847534107544613605305015441090508924094198816691219103399526800112802416383088995253908857460266726925615826895303377801614829364034624475195859997943146305588315939130777450485196290766249612340054354622516207681542973756257677388091926549655162490873849955783768663029138647079874278240867932127196686258800146911620730706734103611833179733264096475286491988063990431085380499075005629807702406676707841324660971173253100956362528346684752959937473852630145893796056675793646430793578265418255919376323796044588559726703858429311784705245069845938316802681575653653770883615525735690306674635167111
e1 = 2767
e2 = 3659
c1 = 20152490165522401747723193966902181151098731763998057421967155300933719378216342043730801302534978403741086887969040721959533190058342762057359432663717825826365444996915469039056428416166173920958243044831404924113442512617599426876141184212121677500371236937127571802891321706587610393639446868836987170301813018218408886968263882123084155607494076330256934285171370758586535415136162861138898728910585138378884530819857478609791126971308624318454905992919405355751492789110009313138417265126117273710813843923143381276204802515910527468883224274829962479636527422350190210717694762908096944600267033351813929448599
c2 = 11298697323140988812057735324285908480504721454145796535014418738959035245600679947297874517818928181509081545027056523790022598233918011261011973196386395689371526774785582326121959186195586069851592467637819366624044133661016373360885158956955263645614345881350494012328275215821306955212788282617812686548883151066866149060363482958708364726982908798340182288702101023393839781427386537230459436512613047311585875068008210818996941460156589314135010438362447522428206884944952639826677247819066812706835773107059567082822312300721049827013660418610265189288840247186598145741724084351633508492707755206886202876227
s = gmpy2.gcdext(e1,e2)
c1=gmpy2.invert(c1,n)
m=(pow(c1,-s[1])*pow(c2,s[2]))%n
print(long_to_bytes(m))
|
wechat
alipay
