数论小芝士

欧拉定理：https://oi-wiki.org/math/number-theory/fermat/

#[LitCTF 2023]Euler
from Crypto.Util.number import *
from secret import flag

m = bytes_to_long(flag)
p = getPrime(512)
q = getPrime(512)
n = p*q
c = pow(m,n-p-q+3,n)
print(f'n = {n}')
print(f'c = {c}')
"""
n = 
c = 
"""

$phi = n-p-q+1$，故 $c=m^{phi+2} mod \ n$ ，由欧拉定理可得 $c^{phi}\equiv 1 \ mod n $

则 $c\equiv m^{2} mod \ n $

直接开根即可

import gmpy2
from Crypto.Util.number import long_to_bytes
c = 
print( long_to_bytes(gmpy2.iroot(c,2)[0]) )

---

威尔逊定理：$(p-1)!\equiv -1\ mod\ p$

#[长安杯 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

第一步爆破n：

hint1 = 
hint2 = 
e = 1049
for k in range( 1 , 1000000 ):
    if ( 2**e - hint1 ) % k == 0:
        n = ( 2**e - hint1 ) // k
        print( k , n.bit_length() , n  )

得到 $n$，直接分解得到 $p$ 和 $q$

第二步：

已知 $M\equiv m*(p-q-1)\ mod\ n$

因为 $p\mid n$，所以 $M\equiv m*(p-q-1)\ mod\ p$（放缩）

得到方程

$$\begin{cases} (p-1)! \equiv -1\ mod\ p\\ M\equiv m*(p-q-1)\ mod\ p \end{cases}$$

$\therefore m\equiv \dfrac{M(p-1)!}{(-1)(p-q-1)!}$

import gmpy2
from Crypto.Util.number import long_to_bytes

hint2 = 33035...
e = 1049
n = 58237...

p = 17022...
q = 34211

phi = (p-1)*(q-1)
assert p*q == n
d = gmpy2.invert( e , phi )
m = pow( hint2 , d , n )
print( m )
m = -1*m
for i in range( p-q , p ):
    m = m * i % p
print( long_to_bytes(m) )

---