13518219792
性质① m是素数时，有φ(m)=m-1
创新互联专注于企业营销型网站建设、网站重做改版、昭阳网站定制设计、自适应品牌网站建设、H5场景定制、商城网站制作、集团公司官网建设、成都外贸网站建设公司、高端网站制作、响应式网页设计等建站业务，价格优惠性价比高，为昭阳等各大城市提供网站开发制作服务。
性质② 当m、n互素时，φ(m*n)=φ(m)*φ(n)
性质③ 对一切正整数n，有φ(p^n)=[p^(n-1)]*(p-1)
它于1640年由Descartes首先给出证明，后来Euler(欧拉)于1752年又独立地给出证明，我们称其为欧拉定理，在国外也有人称其为Descartes定理，R+V-E=2就是欧拉公式。
在任何一个规则球面地图上，用R记区域个数，V记顶点个数，E记边界个数，则R+V-E=2，这就是欧拉定理。
当R=2时。
由说明1这两个区域可想象为以赤道为边界的两个半球面，赤道上有两个“顶点”将赤道分成两条“边界”。
即R=2，V=2，E=2于是R+V-E=2,欧拉定理成立。
本文参考 为对其知识进行掌握，写此文章来梳理和加深记忆
前言：理解基本概念，本文将每种攻击方式实现方法提炼成了一个函数，便于理解原理也可以直接调用。
基础：
RSA概要：
在开始前可以通过 《RSA算法详解》 这篇文章了解关于RSA的基础知识，包括加解密方法，算法原理和可行性证明等。（特详细）
应用流程：
1.选取两个较大的互不相等的质数p和q 计算n =p q。
2.计算phi =（p-1） （q-1）。
3.选取任意的e，使得e满足1ephi 且 gcd(e,phi) ==1 .
4.计算e关于phi的模逆元d，即d满足（e*d）%phi ==1.
5.加解密：c=(m^e)%n ,m =(c^d)%n.其中m为明文，c为密文 （n,e）为公钥，d为私钥，要求0=mn.
求模逆可直接利用gmpy2库。如 import gmpy2 print gmpy2.invert(47,30) 可求得47模30的逆为23。
扩展欧几里得算法基于欧几里得算法，能够求出使得 ax+by=gcd(a,b) 的一组x,y。
常见攻击方式实践
准备工具
python gmpy2库 libnum库
yafu
RSATool2v17.exe
RSA解密
若已知私钥d，则可以直接解密：m=pow(c,d,n).
若已知质数p和q,则通过依次计算欧拉函数值phi、私钥d可解密。简易实现如下：
在选取加密指数e时要求phi，e互质，也就是gcd(phi,e)==1 ，如果不满足是无法直接解密的。
SCTF2018的Crypto - a number problem，题目是： x**33=1926041757553905692219721422025224638913707 mod 3436415358139016629092568198745009225773259 tell me the smallest answer of x
其中n=3436415358139016629092568198745009225773259 可以直接分解得到p,q，出phi=(p-1)*(q-1) ，然后惊奇地发现gcd(phi,33)==3 。这时如果对加密过程比较熟悉的话，就可以想到实际上公钥e=11 ，明文是m=x^3 ，应该先求出m。然后再爆破x。
n2，n3已知，利用共模攻击得到n1，由gcd(n1,n2)==p1 分解n1，n2，就可解密得到两部分msg，拼接即可。
小明文攻击
适用情况：e较小，一般为3。
公钥e很小，明文m也不大的话，于是 m^e=k*n+m 中的的k值很小甚至为0，爆破k或直接开三次方即可。Python实现：
例子：Extremely hard RSA
题目提供的n是4096位的，e=3。
Rabin加密中的N可被分解
适用情况：e==2
Rabin加密是RSA的衍生算法，e==2是Rabin加密典型特征，可以百度或阅读 以了解到详细的说明，这里只关注解密方法。一般先通过其他方法分解得到p，q，然后解密。
Python实现：
函数返回四个数，这其中只有一个是我们想要的明文，需要通过其他方式验证，当然CTF中显然就是flag字眼了。
Wiener’s Attack
适用情况：e过大或过小。
工具：
在e过大或过小的情况下，可使用算法从e中快速推断出d的值。详细的算法原理可以阅读： 低解密指数攻击 。
例子：2018强网杯nextrsa-Level2
**私钥文件修复
适用情况：提供破损的私钥文件。 **
参考 修复存储私钥的文件，得到p和q。
**私钥修复
Python 脚本：**
从缺失的私钥中，我们可以分析出各部分数据代表的数字。
改动原脚本中的各部分内容即可恢复出私钥，大致算法为：
**LSB Oracle Attack
适用情况：可以选择密文并泄露最低位。 **
在一次RSA加密中，明文为m，模数为n，加密指数为e，密文为c。我们可以构造出 c'=((2^e)*c)%n=((2^e)*(m^e))%n=((2*m)^e)%n ， 因为m的两倍可能大于n，所以经过解密得到的明文是 m'=(2*m)%n 。我们还能够知道 m' 的最低位 lsb 是1还是0。 因为n是奇数，而 2*m 是偶数，所以如果 lsb 是0，说明 (2*m)%n 是偶数，没有超过n，即 mn/2.0 ，反之则 mn/2.0 。举个例子就能明白 2%3=2 是偶数，而 4%3=1 是奇数。以此类推，构造密文 c"=(4^e)*c)%n 使其解密后为 m"=(4*m)%n ，判断 m" 的奇偶性可以知道 m 和 n/4 的大小关系。所以我们就有了一个二分算法，可以在对数时间内将m的范围逼近到一个足够狭窄的空间。
更多信息可参考： RSA Least-Significant-Bit Oracle Attack 和 RSA least significant bit oracle attack 。
Python实现：
欧拉常数(Euler-Mascheroniconstant)。
学过高等数学的人都知道，调和级数S=1+1/2+1/3+..是发散的这时引用欧拉常数。
在数论，对正整数n，欧拉函数是小于n的正整数中与n互质的数的数目（因此φ(1)=1）此函数以其首名研究者欧拉命名(Euler’stotientfunction)，它又称为Euler’stotientfunction、φ函数、欧拉商数等例如φ(8)=4，因为1，3，5，7均和8互质。
φ函数的值 通式：φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),其中p1, p2……pn为x的所有质因数，x是不为0的整数。φ(1)=1（唯一和1互质的数(小于等于1)就是1本身）。 (注意：每种质因数只一个。比如12=2*2*3那么φ
欧拉函数21计算：
分解质因数：21=2^3*3*5。
欧拉函数：φ(21)=21*(1-1/2)(1-1/3)(1-1/5)=120*1/2*2/3*4/5=32。
小于或等于n的正整数中与n互质的数的数目（因此φ(1)=1）。设n为正整数，以 φ(n)表示不超过n且与n互素的正整数的个数，称为n的欧拉函数值φ：N→N，n→φ(n)称为欧拉函数。
函数的近代定义
是给定一个数集A，假设其中的元素为x，对A中的元素x施加对应法则f，记作f（x），得到另一数集B，假设B中的元素为y，则y与x之间的等量关系可以用y=f（x）表示，函数概念含有三个要素：定义域A、值域B和对应法则f。其中核心是对应法则f，它是函数关系的本质特征。
