欧拉定理

这里直接盗用百度百科上的图片：

缩系：简化剩余系(reduced residue system)也称既约剩余系或缩系，是m的完全剩余系中与m互素的数构成的子集，如果模m的一个剩余类里所有数都与m互素，就把它叫做与模m互素的剩余类。在与模m互素的全体剩余类中，从每一个类中各任取一个数作为代表组成的集合，叫做模m的一个简化剩余系。例如，模5的一个简化剩余系是1，2，3，4，模10的一个简化剩余系是1，3，7，9，模18的一个简化剩余系是1，5，7，11，13，17 。

好了，简单介绍完欧拉定理，费马小定理其实就是在欧拉定理的基础上，把模数改为素数。很显然它也满足欧拉定理。

下面给个例题：

2021巅峰极客crtrsa

题目如下：

from secret import flagn,p,q
#p and q are two primes generated by getPrime
import random
def key_gen():
	while True:
		dp = random.randint(1,1<<20)
		dq = random.randint(1,q-1)
		if gcd(dp, p - 1) == 1 and gcd(dq, q - 1) == 1:
			d = crt([dp,dq],[p-1,q-1])
			phi = (p-1)*(q-1)
			R = Integers(phi)
			e = R(d)^-1
			return p*q,e
n,e = key_gen()
print e
print n
print pow(flagn,int(e),n)
------------------------------------------------------------------------------------------------------------
e = 2953544268002866703872076551930953722572317122777861299293407053391808199220655289235983088986372630141821049118015752017412642148934113723174855236142887
N = 6006128121276172470274143101473619963750725942458450119252491144009018469845917986523007748831362674341219814935241703026024431390531323127620970750816983
flag = 4082777468662493175049853412968913980472986215497247773911290709560282223053863513029985115855416847643274608394467813391117463817805000754191093158289399

推导过程：

dp = d mod (p - 1) ------------①
dq = d mod (q - 1) ------------②
e * d = 1 mod (p - 1) * (q - 1) ------------③
==>
e * dp = (e * d) mod (p - 1) ------------④
这里可以把③式中的(q - 1)当作是(p - 1)的一个系数设为k，所以e * d - 1就是(p - 1)的k倍
同理在④式中(e * d) mod (p - 1)等于1
==>
e * dp = 1 mod (p - 1) -----------⑤
根据费马小定理：
a^Φ(p) ≡ 1 mod p，这里的Φ(p)就是(p - 1)，因为p是素数所以Φ(p)等于(p - 1)。
⑤式中(e * dp - 1)是(p - 1)的k倍，将其代入到费马小定理中
a^(k1 * (e * dp - 1)) - 1 = k2 * p
gcd(a^(k1 * (e * dp - 1)) - 1, N)可求得p
因为题目告诉了我们dp的范围，所以可以爆破dp。

脚本如下：

from Crypto.Util.number import *
import gmpy2

e = 2953544268002866703872076551930953722572317122777861299293407053391808199220655289235983088986372630141821049118015752017412642148934113723174855236142887
N = 6006128121276172470274143101473619963750725942458450119252491144009018469845917986523007748831362674341219814935241703026024431390531323127620970750816983
flag = 4082777468662493175049853412968913980472986215497247773911290709560282223053863513029985115855416847643274608394467813391117463817805000754191093158289399

for i in range(1, pow(2, 20) + 1):
    mul_p_1 = e * i - 1
    mul_p = pow(123, mul_p_1, N) - 1;
    p = gmpy2.gcd(mul_p, N)
    if (p == 1):
        continue
    q = N // p
    assert  p * q == N
    print(p, q)
    phin = (p - 1) * (q - 1)
    d = inverse(e, phin)
    print(long_to_bytes(pow(flag, d, N)))
    break

flag{d67fde91-f6c0-484d-88a4-1778f7fa0c05}

---