题目附件

from Crypto.Util.number import *
from secret import flag

def genKey(nbits):
    p = getPrime(nbits)
    q = getPrime(nbits)
    
    N = p*p*q
    d = inverse(N, (p-1)*(q-1)//GCD(p-1, q-1))
    return N,d

def encrypt(message,N):
    m = bytes_to_long(flag)
    c = pow(m, N, N)
    return c

nbits = 1024
m = bytes_to_long(flag)
N,d = genKey(nbits)
c = encrypt(m,N)

print('c =', c)
print('N =', N)
print('d =', d)

"""
c = 29897791365314067508830838449733707533227957127276785142837008063510003132596050393885548439564070678838696563164574990811756434599732001622138564176327233154381380717648392357672642893142367607369679906940371540867456654151408884171467638060523066406441697453971996011548195499549200103123841556085936672833238264876038160712793697159776332101536779874757463509294968879216810485825310481778472384531442206034564488532399171243463881900578407746982324779260941957792455217641883334131366614310644607114128868153897806362954456585661855569432513785225453501792356175649676419772626548071916379318631677869452985829916084336045071072493567871623113923140668031380684940109024609167449291380675124701557542736834722898328082888430566229322840781411336263268594978558564310744076581639469210462567543585251718744340216155557606004995449505782302864725856877289388008819135023371948017425832082773421030256964953984562211638060
N = 3231913372897424708803097969843687520868057190788284975066875241636436021279559026753076528399891936983240045179193386905918743759145596242896507856007669217275515235051689758768735530529408948098860529277921046146065473333357110158008648799207873976745048714516868561754202543130629713461365314627535982379718931633528922076268531363809414255082933615667770491818402126891370106045838695484124212397783571579791558324350069782623908757815983802849109451590357380624488436968737140312471089662428308113246310588336044438265822574558816510054763215983649467009345458480077882624118620789015758507736272402998721366662352794082495441303895025585316667229865533166614969641012195668280586477033200418153345241668242651407009849656745509386158276185301334443855737552801531617549980843398648751032649895403939319648954908487619711555700124294191702406981128355348449748466449951568451135718146828444185238617155432417897711198169
d = 220908195398117048628110042133057032501548264225985823161565460390793825899523662424732910718579350524590368287207857059670558852106434615134645183432670023784725430385048028248108677670095524205518013647694485975996499747580966911259433184798952372110628624294686853944766950244209186984164963987120416687012811346656498861438432610431705868541829977481875385468143747334359481673214618931159403123892213161430602430294790913847722073762999311674428134241956293914716183107414340330449465142849402354034926378025006749405210014879947411570380433942279355488861684317611066949685697268714760755591128598654573304969
"""

思路

定义模数 $N$ 和 解密指数 $d$ 之间的关系

$N \equiv 1 \mod \left( \frac{(p - 1) \ast (q - 1)}{\gcd(p - 1, q - 1)} \right)$

解密指数 $d$ 的计算公式

$L = \frac{(p - 1) \ast (q - 1)}{\gcd(p - 1, q - 1)} \\ N \cdot d = 1 + k \cdot L, k \in \mathbb{Z}$

对于任意整数 $a (> 1)$，计算 $a$ 的 $N \cdot d$ 次幂模 $N$

$a^{N \cdot d} \equiv a \mod n \\ n = p \ast q$

题目中对公钥 $N$ 的构造

$N = p^2 \ast q = p \ast n$

模数 $N$ 和欧拉函数 $\phi(n)$ 之间的关系

$\phi(n) = (p - 1) \ast (q - 1) \\ N \cdot d \equiv 1 \mod \phi(n)$

$a$ 的 $N \cdot d$ 次幂模 $n$

$a^{N \cdot d} \equiv a^{1+k\cdot\phi(n)} \mod n \\ a^{\phi(n)} \equiv 1 \mod n \text{ 欧拉定理}$

从而

$a^{N \cdot d} \equiv a \mod n$

恒等式转为等式且对 $a$ 移项得

$a^{N \cdot d} - a = k_2 \ast n$

模数 $N$，解密指数 $d$，和 $n$ 之间的关系

$N = p^2 \ast q = p \ast (p \ast q) = p \ast n$

求解 $p$

$p = \frac{N}{n}$

求解 $q$

$q = \frac{n}{p}$

加密指数 与 phi 不互素，可以尝试非预期

Sage

a = 2 # 取 a > 1, 例如 2, 符合条件且相对好算
k2n = power_mod(a, (N * d), N) - a # 但是为什么 mod N 是对的, 见下方
n = GCD(k2n, N)
p = N / n
q = n / p
assert p * p * q == N
phi = (p - 1) * (q - 1) * p
# assert GCD(phi, N) == 1 # 不互素
# dd = inverse_mod(N, phi) 
# m = power_mod(c, dd, N)
# m = long_to_bytes(m)
# print(m)
ans_list = Mod(c, p * p * q).nth_root(p * p * q, all=True)
print('完成枚举')
print('len: ' + len(ans_list))
for ans in ans_list:
    if b'ISCTF' in long_to_bytes(ans):
        print(long_to_bytes(ans))
        break

思路补充

为什么 k2n = power_mod(a, (N * d), N) - a 中进行 $\pmod N$ 是对的？

因为接下来操作是求最大公约数，需要 $gcd(p * p * q, p * q) == p * q$, 且 $p * q < N$ 所以可以取模来触发快速幂，否则会很慢

不过这里的 $k_2$ 就不真实了，但意义也不大，因为核心在 $p*q$ 也就是 $n$

Exploit

更优雅的办法, $n$ 是 $N$ 的真因子，在较小的模数下解密

a = 2
k2n = power_mod(a, (N * d), N) - a 
n = GCD(k2n, N)
p = N / n
q = n / p
assert p * p * q == N
m = power_mod(c, d, n)
print(long_to_bytes(m)) # b'ISCTF{aeb8be10-ff19-42cf-8cfd-2ce71ac418e8}'

出题者(Dexter)说

考虑 Schmidt-Samoa 密码系统：

• $N * d \equiv 1 \mod (p - 1)(q - 1)$
• 任意整数 $a$，有 $a^{N \cdot d} \equiv a^{k(p-1)(q-1)+1} \equiv a \pmod{p * q}$
• 因此 $k \times (p \times q) = a^{Nd} - a$

给定 $N$ 来公然发送即可得到 $p \times q$，再用 $d$ 解密即可

参考

[虚空] [ISCTF2023] Crypto方向全wp

[ISCTF2023] Crypto/PWN/Reverse