フェルマーの小定理やオイラーの定理を使った問題は，CTFのCrypto問題でよく出ます(当社調べ)(そしてこのタイプの問題が一番楽しい)．
それらを使った解いた問題の列挙です．難易度は独断と偏見でつけました．
基本
フェルマーの小定理(Fermat’s little theorem)は素数$p$，整数$a$で
$$
a^p \equiv a \pmod p \quad (pは素数)
$$
が成り立つことを言います．
$a$が$p$と互いに素なことを条件に加えると，両辺を$a$で割った
$$
a^{p-1} \equiv 1 \pmod p \quad (pは素数，aはpと互いに素)
$$
が成り立ちます．さらに両辺を$a$で割ると
$$
a^{p-2} \equiv a^{-1} \pmod p \quad (pは素数，aはpと互いに素)
$$
となり，逆元になります．どの形もよく使います．
オイラーの定理(Euler’s theorem)は先程の$p$を合成数$n$に拡張したもので，
$$
a^{\phi(n)} \equiv 1 \pmod n \quad (nは合成数，aとnは互いに素)
$$
ただし，$\phi(n)$はオイラーのトーシェント関数(Euler’s totient function)と呼ばれる関数で，$1$以上$n$以下の数のうち$n$と互いに素な個数を表します．
式で表すと，合成数$n$の素因数分解が
$$
n = \prod_{i=1}^k p_i^{e_i} \\
$$
のとき
$$
\phi(n) = \prod_{i=1}^k (p_{i}^{e_{i}} - p_{i}^{e_{i}-1})
$$
で定義されます．
なお，注意として，フェルマーの小定理の指数$p-1$やオイラーの定理の$\phi(n)$は$a$を$1$にする最小の数とは限りません．最小の数についてのカーマイケルの定理というものが存在します．
ちなみに，フェルマーの小定理ですが，フェルマーさんではなくゴットフリート・ライプニッツさんによって証明されたらしいです．
また，フェルマーの最終定理と区別するために，「小」ついています．
CakeCTF2022 frozen cake 難易度★★
問題
問題ファイル
素数$p,q$と平文$m$，$n=pq$から次の$a,b,c$の値が与えられる．$n$の値も与えられる．
$$
\begin{align}
a &\equiv m^p \mod n \\
b &\equiv m^q \mod n \\
c &\equiv m^n \mod n
\end{align}
$$
解法
$px+qy=1 \pmod{\phi(n)}$となるような$x,y$が存在すれば，$m$を復元することができるが，
$p$と$q$は$\phi(n)$と互いに素ではないため，この手法は使えない．
$c$を変形してみる．
$$
n = (p-1)(q-1) + p+q-1 = \phi(n) + p+q-1 \\
c \equiv m^n \equiv m^{\phi(n) +p+q-1} \equiv m^{p+q-1} \equiv m^p m^q m^{-1}\pmod n
$$
ここで，$m^p,m^q\pmod n$の値はわかっているので，
$$
c a^{-1} b^{-1} \equiv m^{-1} \pmod n
$$
これで$m^{-1}\mod n$が求まり，これの逆数がフラグである．
1
2
3
4
5
6
7
8
9
10
11
| from Crypto.Util.number import inverse , long_to_bytes
n = 101205131618457490641888226172378900782027938652382007193297646066245321085334424928920128567827889452079884571045344711457176257019858157287424646000972526730522884040459357134430948940886663606586037466289300864147185085616790054121654786459639161527509024925015109654917697542322418538800304501255357308131
a = 38686943509950033726712042913718602015746270494794620817845630744834821038141855935687477445507431250618882887343417719366326751444481151632966047740583539454488232216388308299503129892656814962238386222995387787074530151173515835774172341113153924268653274210010830431617266231895651198976989796620254642528
b = 83977895709438322981595417453453058400465353471362634652936475655371158094363869813512319678334779139681172477729044378942906546785697439730712057649619691929500952253818768414839548038664187232924265128952392200845425064991075296143440829148415481807496095010301335416711112897000382336725454278461965303477
c = 21459707600930866066419234194792759634183685313775248277484460333960658047171300820279668556014320938220170794027117386852057041210320434076253459389230704653466300429747719579911728990434338588576613885658479123772761552010662234507298817973164062457755456249314287213795660922615911433075228241429771610549
ainv = inverse(a,n)
binv = inverse(b,n)
minv = (c * ainv * binv)%n
print(long_to_bytes(inverse(minv,n)))
|
1
| CakeCTF{oh_you_got_a_tepid_cake_sorry}
|
CakeCTF2021 together as one 難易度★★★
問題概要
問題リンクファイル
素数$p,q,r$があり，$e\equiv65537$，フラグを$m$とし，次の値が与えられる．
$$
n \equiv pqr \\
c \equiv m^e \\
x \equiv (p+q)^r \mod n \\
y \equiv (p+qr)^r \mod n
$$
解法
二項定理により，$x$の値について次の計算ができる．
$n=pqr$であり，$0<x<r$のとき${}_r\textrm{C}_x$が$r$の倍数であることを使っている．
$$
\begin{align}
x &\equiv (p+q)^r \mod n \\
&\equiv {}_r\textrm{C}_0 p^rq^0 + {}_r\textrm{C}_1 p^{r-1}q^1 + {}_r \textrm{C}_2 p^{r-2}q^2 + \cdots + {}_r\textrm{C}_{r-1} p^1q^{r-1} + {}_r\textrm{C}_{r} p^0q^{r-1} \mod n \\
&\equiv p^r + q^r \mod n
\end{align}
$$
$y$も同様に，展開をして$n$の倍数になる項を削除する．
$$
\begin{align}
y &\equiv (p+qr)^r \mod n \\
&\equiv p^r + q^rr^r \mod n
\end{align}
$$
法$q$の世界で考える．すると，
$$
\begin{align}
x &\equiv p^r \mod q\\
y &\equiv p^r \mod q
\end{align}
$$
よって，整数$k$を用いると次が成り立つ
$$
\begin{align}
x &\equiv y \mod q\\
x &\equiv y + kq \\
x - y &\equiv kq
\end{align}
$$
$x-y$は$q$の倍数であり，$n$も素因数$q$を持っているため，$q\equiv\textrm{GCD}(x-y,n)$である．
次に，$x$と$y$を法$r$で考える．フェルマーの小定理により，$p^r \mod r\equiv p$が成り立つ(他の変数も同様)．
$$
\begin{align}
x \equiv p + q \mod r\\
y \equiv p \mod r
\end{align}
$$
$q$が邪魔だが既知であるため，$r$について合同な式ができる．
$$
\begin{align}
x - q \equiv y \mod r\\
\end{align}
$$
よって，$r\equiv\textrm{GCD}(x-q-y,n/q)$である．
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| from Crypto.Util.number import long_to_bytes,inverse
def GCD(a,b):
if a%b==0:
return b
return GCD(b,a%b)
def LCM(a,b):
return a//GCD(a,b)*b
n = # 長いので省略
c =
x =
y =
e = 0x10001
q = GCD((x-y)%n,n)
r = GCD((x-y-q)%n,n)//q
p = n//r//q
print(f'{p = :#}')
print(f'{q = :#}')
print(f'{r = :#}')
assert p*q*r == n
phi = (p-1)*(q-1)*(r-1)
d = pow(e,-1,phi)
m = pow(c,d,n)
print(long_to_bytes(m))
|
1
| CakeCTF{This_chall_is_inspired_by_this_music__Check_out!__https://www.youtube.com/watch?v=vLadkYLi8YE_cf49dcb6a31f}
|
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)} &\equiv g^{f\phi(N)} r^{N\phi(N)} \pmod {N^2} \\
&\equiv g^{f\phi(N)} r^{\phi(N^2)} \pmod {N^2} \\
&\equiv g^{f\phi(N)} \pmod {N^2}
\end{align}
$$
これで，あとは$f\phi(N)$が求められれば良いが，これは$N^2$が小さな素数の積であることから，Pohlig–Hellman法が使える．
以下sageでの実装
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| 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))
|
続く
良い問題を見つけ次第追加していきます．