作者：0431实验室
公众号：吉林省信睿网络

一、欧拉函数（phi）

函数内容

通式：

其中p1, p2……pn为x的所有质因数，x是不为0的整数。

φ(1)=1（和1互质的数(小于等于1)就是1本身）。

注意：每种质因数只一个。比如12=223那么φ（12）=φ（43）=φ（2^23^1）=（2^2-2^1）*（3^1-3^0）=4

若n是质数p的k次幂，

因为除了p的倍数外，其他数都跟n互质。

设n为正整数，以 φ(n)表示不超过n且与n互素的正整数的个数，称为n的欧拉函数值

φ：N→N，n→φ(n)称为欧拉函数。

欧拉函数是积性函数——若m,n互质，

如：φ(15)=φ(3)·φ(5)=2·4=8

特殊性质：当n为奇质数时，

证明与上述类似。

若n为质数则

函数表

0~100欧拉函数表（“x?”代表十位数，“x”代表个位数）

φ(100)=40

二、费马小定理

版本一：

若a为一个整数，p为一个素数

那么a的p次方再减去a一定为p的倍数（同余）

记为

版本二：

把a提出来

当a不是p的倍数时，可以写成（p必须为一个素数）

三、费马欧拉定理

1736年欧拉证明费马小定理是对的，给出更一般的定理：

若满足a为一个整数，n为一个与a互素的整数，即a⊥n，那么

所以有了费马欧拉定理（在数论中命名）

四、模反函数

如果两个正整数e和n互质，那么一定可以找到整数d，使得 e * d - 1 被n整除，或者说e * d被n除的余数是1。这时，d就叫做e的“模反元素”。欧拉定理可以用来证明模反元素必然存在。两个整数a,b，它们除以整数M所得的余数相等：a ≡ b(mod m)，比如说5除3余数为2，11除3余数也为2，于是可写成11 ≡ 5(mod 3)。

五、欧几里得算法（辗转相除法-求最大公约数）

欧几里得算法是求最大公约数的算法, 也就是辗转相除法。记 gcd(a,b) 为a和b的最大公约数，欧几里得算法的基本原理是gcd(a,b)==gcd(b,a%b),(b!=0) 和 gcd(a,0)==a 。

基本原理证明：

第一步：令c=gcd(a,b)，则设a=mc，b=nc

第二步：可知r =a-kb=mc-knc=(m-kn)c 【r=a%b】

第三步：根据第二步结果可知c也是r的因数

第四步：可以断定m-kn与n互素【否则，可设m-kn=xd,n=yd,(d>1)，则m=kn+xd=kyd+xd=(ky+x)d，则a=mc=(ky+x)dc，b=nc=ycd，故a与b最大公约数≥cd，而非c，与前面结论矛盾】

从而可知gcd(b,r)=c，继而gcd(a,b)=gcd(b,r)，得证

扩展欧几里得算法

扩展欧几里得算法基于欧几里得算法，能够求出使得 ax+by=gcd(a,b) 的一组x,y。

对照下图更容易理解

同样按照欧几里得算法的递归过程一样，到边界的时候b=0，这时候整数解非常好找，就是x=1，y=0。

六、RSA

①找两素数p和q，取n=p*q （N）

②r=φ(n)=φ(p)φ(q)=(p-1)(q-1)

③e∈Z，e＜r 且 e⊥r (必须)

。。。。。。公钥（N，e）

④d（模逆元），满足ed-1=r的倍数

d*e%r=1

求d令ed ≡ 1 (mod r)

。。。。。。私钥（N，d）

加密：

Bob用公钥加密给Alice传数 Bob 传 m 给 Alice，要求m＜N

Alice得到密文c

解密：

Alice用私钥破解密文得到明文

？即是明文m

解释：

差个正负号，但是都是N的倍数，都成立

两边同时做d次方

最后一步根据费马欧拉定理得来

所以得到解密式子：

对明文m进行加密：c = pow(m, e, N),可以得到密文c。

对密文c进行解密：m = pow(c, d, N),可以得到明文m。

pow(x, y, z)：效果等效pow(x, y)1% z， 先计算x的y次方，如果存在另一个参数z，需要再对结果进行取模。即pow(x,y,z)=x^y(mod z)

七、实例-共模攻击

所谓共模攻击，是指多个用户共用一个模数n，各自有自己的e和d，在几个用户之间共用n会使攻击者能够不用分解n而恢复明文。 例如假设m为信息明文，两个加密密钥为e1和e2，公共模数为n，则：

c1 = pow(m, e1, n) – c1 = m^e1%n
c2 = pow(m, e2, n) – c2 = m^e2%n

分别拿对应的私钥来加密，可以得到相同的明文m

m = pow(c1, d1, n) – m = c1^d1%n
m = pow(c2, d2, n) – m = c2^d2%n

假设攻击者已知n,e1,e2,c1,c2，即可得到明文p，因为e1和e2互质，所以使用欧几里得算法可以找到能够满足以下条件的x，y：

pow(x,e1)+pow(y,e2)=1 – x^e1+y^e2=1（式中，x、y皆为整数，但是一正一负）

因为：c1 = m^e1%n ；c2 = m^e2%n

所以：(c1^xc2^y)%n = ((m^e1%n)^x(m^e2%n)^y)%n

根据模运算性质，可以化简为：(c1^xc2^y)%n = ((m^e1)^x(m^e2)^y)%n

即：(c1^x*c2^y)%n = (m^(e1x+e2y))%n

有前面提到：e1x+e2y = 1

所以 (c1^xc2^y)%n = (m^(1))%n (c1^xc2^y)%n = m%n

即 c1^x*c2^y ≡ m （mod n）

假设x为负数，需再使用欧几里得算法来计算pow(c1,-1)，则可以得到

pow(pow(c1,-1),-x) * pow(c2,y) = m mod(n) – {[c1^(-1)]^(-x)}*(c2^y) = m mod n

m = c1^x*c2^y mod N

在数论模运算中，要求一个数的负数次幂，与常规方法并不一样。

比如此处要求c1的x次幂，就要先计算c1的模反元素c1r，然后求c1r的-x次幂

如果m＜n，则m可以被计算出来。

例题：

某次ctf比赛中的题

共模攻击的脚本+测试代码

题中给了n,e1,e2,c1,c2

运行脚本解出10进制的m，转换成hex，再转换成字符串即可得到flag。

总的脚本如下：

# -*- coding:utf-8 -*-
from gmpy2 import invert
def gongmogongji(n, c1, c2, e1, e2):
    def egcd(a, b):
        if b == 0:
            return a, 0
        else:
            x, y = egcd(b, a % b)
            return y, x - (a // b) * y
    s = egcd(e1, e2)
    s1 = s[0]
    s2 = s[1]

    # 求模反元素
    if s1 < 0:
        s1 = - s1
        c1 = invert(c1, n)
    elif s2 < 0:
        s2 = - s2
        c2 = invert(c2, n)
    m = pow(c1, s1, n) * pow(c2, s2, n) % n
    return m

n= 103109065902334620226101162008793963504256027939117020091876799039690801944735604259018655534860183205031069083254290258577291605287053538752280231959857465853228851714786887294961873006234153079187216285516823832102424110934062954272346111907571393964363630079343598511602013316604641904852018969178919051627
e1= 13
e2= 15
c1= 13981765388145083997703333682243956434148306954774120760845671024723583618341148528952063316653588928138430524040717841543528568326674293677228449651281422762216853098529425814740156575513620513245005576508982103360592761380293006244528169193632346512170599896471850340765607466109228426538780591853882736654
c2= 79459949016924442856959059325390894723232586275925931898929445938338123216278271333902062872565058205136627757713051954083968874644581902371182266588247653857616029881453100387797111559677392017415298580136496204898016797180386402171968931958365160589774450964944023720256848731202333789801071962338635072065

result = gongmogongji(n, c1, c2, e1, e2)
print result
m1=hex(50937517501984079318479184180525081694999782691988219077509947184814275476037417455150384)
print m1
import binascii
m2=binascii.unhexlify(b'666c61672d3534643364623563316566636437616661353739633337626362353630616530')
print m2

最后得到flag：

flag-54d3db5c1efcd7afa579c37bcb560ae0

参考文献

https://blog.csdn.net/qq_23077403/article/details/86099229 https://blog.csdn.net/qq_23077403/article/details/86099229

本文由 Seebug Paper 发布，如需转载请注明来源。本文地址：https://paper.seebug.org/1055/