kotori - RSA - \(d-q\)
推导
\(a ^ {\phi(n)} \equiv 1 \pmod{n}\) (欧拉定理)
\[\begin{aligned}
ed & \equiv 1 \pmod{\phi(n)} \\
ed & = 1 + k \times \phi(n) \\
\end{aligned}
\]
\[\begin{aligned}
m ^ {e(d - q)} & \equiv m ^ {ed - eq} \pmod{n} \\
& \equiv m ^ {1 + k \times \phi(n) - eq} \pmod{n} \\
& \equiv m ^ {1 - eq} \pmod{n} \\
& \equiv m \times m ^ {-eq} \pmod{n} \\
& \equiv m \times (m ^ {-e}) \pmod{q} \\
\end{aligned}
\]
上式最后一步转换 \(\pmod{q}\) 的过程
\[\begin{align}
a ^ {\phi(p)} & \equiv 1 \pmod{p} \\
\because \phi(p) & = p - 1 \quad \text{欧拉函数} \\
\therefore a ^ {p - 1} & \equiv 1 \pmod{p} \\
\therefore a ^ {p} / a & \equiv 1 \pmod{p} \\
\therefore a ^ {p} / a * a & \equiv 1 * a \pmod{p} \\
\therefore a ^ p & \equiv a \pmod{p} \quad \text{费马小定理} \\
\text{把} m ^ {-e} \text{代入} a \\
m ^ {-ep} & \equiv m ^ {-e} \pmod{p} \\
\end{align}
\]
from Crypto.Util.number import *
print('[+] Enc')
e = 0x10001
p = getPrime(1024)
q = getPrime(1024)
n = p * q
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
print(f'{d.bit_length() = }')
m = bytes_to_long(b'flag{this_is_a_flag}')
print(f'{m.bit_length() = }')
c = pow(m, e, n)
d_sub_q = d - q
print(f'{d_sub_q = }')
print(f'{d_sub_q.bit_length() = }')
print(f'{c = }')
print(f'{n = }')
print('[+] Dec')
g1 = 2 * pow(2, -e, n) - pow(2, e * (d_sub_q), n) # 用未知数推导，计算时带入小值方便计算
print(f'{g1 = }')
def gcd(a, b):
while b:
a, b = b, a % b
return a
g1_n_gcd = gcd(g1, n)
p = g1_n_gcd
q = n // p
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
m = pow(c, d, n)
print(f'{long_to_bytes(m) = }')