ImaginaryCTF October 2022 More pale

問題

$N$と互いに素な$g,r$とフラグ$f$を使って$c$が計算される． $$ c = g^f\times r^N \pmod{N^2} $$

ただし，$N$は$32$ビット程度の素数を$32$個掛け算したものである(簡単のため，それぞれの素数は異なると考える)．

$$ N = \prod^{32}_{i=1} p_i \quad (p_iは素数) $$

解答

$r^N$が邪魔なのでどうにかして消したい． $\pmod{N^2}$で$1$にするには，$\phi(N^2)$乗する必要がある．$\phi(N^2)$を計算してみると，$N$が出てくる．

$$ \begin{align} \phi(N^2) &= \prod^{32}_{i=1} (p_i^2 - p_i) \\ &= \prod^{32}_{i=1} p_i(p_i-1) \\ &= \prod^{32}_{i=1} p_i \prod^{32}_{i=1} (p_i -1) \\ &= N \cdot \phi(N) \end{align} $$ そのまま$c$を$\phi(N^2)$乗すると$1$になってしまうが，既に$r$の$N$乗がかかっていることに注目すると，

$$ \begin{align} c^{\phi(N)} &= g^{f\phi(N)} r^{N\phi(N)} \pmod {N^2} \\ &= g^{f\phi(N)} r^{\phi(N^2)} \pmod {N^2} \\ &= g^{f\phi(N)} \pmod {N^2} \end{align} $$

これで，あとは$f\phi(N)$が求められれば良いが，これは$N^2$が小さな素数の積であることから，Pohlig–Hellman法が使える．

以下sageでの実装

from Crypto.Util.number import *
from math import prod, gcd

N = 11426418812422762280036571700606763567947231773425157536629183225870745966201878199993626829615844927248091186921905998387334803393170756953004161976126607998422555566085789763646344981574364094148009230033109930017512774396115010409334288433850791978891238028784308896039614097042863945347168542666985383
g = 102370043738570361147512561430113690669375642568113520628837722692535092928991996894608072640673225251693957175347411184948751047776938223584014537703671208333116611432564769157326548350590167502807755716922970968951558696873031064519102939250266955847456094728415069300661910400192469539174495731756070447257875542560705682612568014282820199452851866020583046932239921789544226454615507571093721529079064029065323857243515917042869595396534609090834939823155439780919449771486541020286445222568415793241204876414692960607993360820654693596638939971884431900128125455066876042896836557800131056640691313737106
c = 103068079671149839873789585083110486503075572741609832823748309905209629934629965848822090939508870383106139073177857845426077799194203506965719179522047046491489575280275678232439148170329359273033661524521427411191787421596981639709353868254044119073231599736765796677163779301047698718070665219409437641669086148533724636988276093326307749151410207387960521848243363050042170628112380019384839142543642612905997234757798225958950399201463485580893790906185150849471016251892565658403504413779544907210377992966457602587448233119477078937422459927927859270682518316711143908453374720529830188577849652582868

ps = factor(N)
phi = 1
phi2 = 1
for p,e in ps:
    phi *= p - 1
    phi2 *= p**2 - p


gf = pow(c,phi,N*N)
print(gf)
f = discrete_log(gf,Mod(g,N*N))
f = f//phi
print(long_to_bytes(f))

コメント

楽しい