威尔逊定理

2022-04-15

威尔逊定理：

$(p-1)!\equiv -1(modp)$

有时候可以用这个结论来化简一些式子达到简化运算的目的。之前遇到过很多次，总结一下。

比如[长安杯 2021]checkin。

from Crypto.Util.number import *
from secret import flag
p = getPrime(1024)
q = getPrime(16)
n = p*q
m = bytes_to_long(flag)
for i in range(1,p-q):
    m = m*i%n
e = 1049
print(pow(2,e,n))
print(pow(m,e,n))
#4513855932190587780512692251070948513905472536079140708186519998265613363916408288602023081671609336332823271976169443708346965729874135535872958782973382975364993581165018591335971709648749814573285241290480406050308656233944927823668976933579733318618949138978777831374262042028072274386196484449175052332019377
#3303523331971096467930886326777599963627226774247658707743111351666869650815726173155008595010291772118253071226982001526457616278548388482820628617705073304972902604395335278436888382882457685710065067829657299760804647364231959804889954665450340608878490911738748836150745677968305248021749608323124958372559270

1.由c1 = pow(2,e,n)得2^e-c1=kn，又由于q是一个16位的素数，所以可以直接枚举q进行分解。得到q以后，可以算出kp=kn//q。

2.分解kp（factor或者简单遍历）

3.求私钥d以后解出m，m和flag的关系为：

$m=flag*(p-q-1)!$

4.构造威尔逊定理的格式：

$m*(p-q)*(p-q+1)...*(p-1)\equiv flag*(p-1)!\equiv -flag(modp)$

5.对结果求modp的逆得到flag

exp：

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

# 简单的分解算法
def yaf(kp):
    for i in range(2,1000):
        if kp % i == 0:
            p = kp // i
            if isPrime(p):
                return p
            else:
                return  yaf(p)

c1 = 4513855932190587780512692251070948513905472536079140708186519998265613363916408288602023081671609336332823271976169443708346965729874135535872958782973382975364993581165018591335971709648749814573285241290480406050308656233944927823668976933579733318618949138978777831374262042028072274386196484449175052332019377
c2 = 3303523331971096467930886326777599963627226774247658707743111351666869650815726173155008595010291772118253071226982001526457616278548388482820628617705073304972902604395335278436888382882457685710065067829657299760804647364231959804889954665450340608878490911738748836150745677968305248021749608323124958372559270

e = 1049
kn = 2**e - c1

for i in range(2**15,2**16):
    if kn % i == 0 and isPrime(i):
        q = i
        kp = kn // q

p = yaf(kp)
n = p*q
phi = (p-1)*(q-1)
d = invert(e,phi)
m = pow(c2,d,n)


for i in range(p-q, p):
    m = m * i % p
print(long_to_bytes(m*invert(-1, p) %p))
# b"flag{7h3_73rr1b13_7h1ng_15_7h47_7h3_p457_c4n'7_b3_70rn_0u7_by_175_r0075}"