flag * 2^{10000} mod 10^{175} == val という形で、val が分かっている。
剰余の定義から
flag * 2^{10000} - k * 10^{175} == val
がわかる。
まず、全ての項は 2^{175} の倍数のはずなので割る。
flag * 2^{10000-175} - k * 5^{175} == val / 2^{175}
ここで 2^{10000-175} と 5^{175} は互いに素となる。
mod 5^{175} の世界に戻せば、
flag * 2^{10000-175} == val / 2^{175} (mod 5^{175})
後は逆元をかければ良い。
flag == (val / 2^{175}) * inv(2^{10000-175}) (mod 5^{175})
Python の Decimal を使って計算されているが、結局やっていることは enc == sin(flag % pi) である。
まず、二分探索なりを使うことで arcsin(enc) = flag % pi を計算する。
剰余の定義から arcsin(enc) + k pi == flag であり、この k が求まれば良い。
全て300桁精度で実行されていることを考えると、10^300 倍して整数の世界で考えると復元が可能である。
具体的には、正しい k の時には arcsin(enc) + k pi の小数点以下が全て 0 になる必要があり、これは整数で扱うことで下の桁から 1 桁ずつ k を決定できる。
後は最下位桁の多少の誤差と、arcsin が2つの値を取りうることに注意して全部試すと、フラグが得られる。
ルービックキューブを乗法群としたElGamal暗号。 群の位数が比較的小さく、また素因数分解によって更に小さくなるため、やることはただのPohlig-Hellman。
ただ、要素がルービックキューブなので、扱いが厄介。それだけ。 utils.js から cube2number もエクスポートしておくと等価判定とかBaby-step Giant-stepでのハッシュテーブルの構築につかえて楽。
pubkey.json を一番最初に確認すると e,n,cf がエクスポートされてるように見える。
で、rsa.rb を見ると cf = q^{-1} mod p であることがわかる。
ここまでの情報でググると、TWCTFのHappy!という問題が(cfという変数名も一致して)出てくる。 ということで似たようなことを考えてCoppersmith's attackを適用……
というのは罠で、rsa.rb をよく見るとエクスポートされてるのは n ではなくて d。 ということでこの問題はHappy!とは全然違い、e,d,cf が与えられた時に n を復元する問題。
まず、e と d が分かっているので、ed - 1 = k(p-1)(q-1) が考えられる。ここでビット数を数えてみると、k はたかだか 2^{17} 以下の値であることが予想できる。
なので、k を全探索出来る。以降、適切な k が選ばれていると仮定する。
この時、(ed-1)/k = (p-1)(q-1) = phi(N) である。
次に cf に関する条件を見る。
cf * q = 1 (mod p)
これに合わせるように、先程の式を (mod p) で計算すると、
(ed - 1)/k = -(q-1) (mod p)
となる。q を削除すると、以下の等式が得られる。
1 + cf * (ed-1)/k - cf = 0 (mod p)
これは、左辺が p の倍数であることを意味している。
更に、phi(N) が分かっていることから、適当な数 a を取ってくると
a^{phi(N)} - 1 = 0 (mod n)
が成り立つ。これは左辺が n の倍数であり、当然 p の倍数でもあることになる。
以上より、1 + cf * (ed-1)/k - cf と a^{phi(N)} - 1 の gcd を取り続けることで、p (または n) が計算できることになる。
なお、a^{phi(N)} は非常に大きな値になるので、前者の値での剰余で計算することで高速に求まる。
最終的に p が求まれば q も phi(N) の式から求まり、n が計算できるため、d,n を用いて暗号文の復号が出来るようになる。
azon君によると特殊な文字列で数式を構成して math.pi を作れば良い。 足し算と割り算が出来るので、小さい数を作ってそれを何回も足すことで微調整をして構成すれば良い。
プログラムで、条件式に合致する入力だけ正答するようなものを提出することで、条件に対するテストケース数を得ることが出来る。 普通に範囲を狭める二分探索だと、32×50=1600で、1000クエリには間にあわない。 問題点として、二分探索をしていくと最終的に1個の値の位置を決めるために二分探索をすることになり、この時得られる情報量が1ビットになってしまうことが挙げられる。 なので、複数のテストケースに対して条件を設定することで2ビットの情報を得るクエリに変換したい。
十分な回数の二分探索の後、各探索区間に1つのテストケースしか無くなった状況を考える。 この時、2つの区間に入ったテストケースの内、下からkビット目が1である、という条件でクエリを投げることを考える。 0または2が返ってきた場合、両方の下位kビット目が確定するため、2ビットの情報が得られたことになる。 1が返ってきた場合、さらにもう一つ区間を追加してクエリを投げることで、3つの下位kビット目を確定させることができ、2クエリで3ビットの情報が得られる。 このようにすることで、1クエリで期待値1.5ビットの情報が得られる。
二分探索の序盤は2ビット以上の情報を得ているため、これらを合わせることで1000クエリ以内に各テストケースの数値を特定することが出来、フラグが得られる。
GCD(P) の値で分けて数え上げることを考える。
ある i について、GCD(P)=v かつ P[i]=x である P の数 cnt(i,v,x) が分かれば、cnt(i,v,x) * v * c[x] * i の総和を計算すれば良いことになる。
また、cnt(i,v,x) == cnt(i',v,x) であることが分かるため、cnt(v,x) := cnt(0,v,x) として cnt(v,x) * v * c[x] * (N-1)*N/2 として良い。
肝心の cnt(0,v,x) の数え方は、まず x を固定する。
次に v を大きい順に見ていく。
全ての P の要素は必ず v の倍数である必要があるため、x が v で割り切れることが条件となる。
また cnt(0,v,x) は、他の N-1 個の要素が v の倍数である数 (floor((N-1)/v)+1)^{N-1} から、cnt(0,2v,x), cnt(0,3v,x), ... を引いた数になる(除原理)。
以上を実装すれば答えが求まる。
なお、P の全要素が 0 となる場合のみ、数え上げのコーナーケースとなるため、v=0 の時は適切に調整する必要がある。
計算量はナイーブに実装することで O(N^2 log N) 回の多倍長演算が必要になる。(log N は調和級数)
v として x の約数のみ見る形にすることで多少は速くなる。
どちらにせよかなり時間がかかるため、C++とgmpなど高速な環境を利用すると便利。