ホッケースティック恒等式と負の二項定理

こういうの、どれくらい常識なのかわからなくて困るな そんなに新規性はないです

ホッケースティック恒等式
k, n を非負整数とします。このとき等式
\sum_{i=k}^{n}\binom{i}{k}=\binom{n+1}{k+1}
をホッケースティック恒等式などと言います。第二引数が fix されてる和がとれて、嬉しい！

この赤い丸で囲んだ場所の和が等しいことを主張していて、その形をパスカルの三角形に書くとホッケースティックのような形をしています。私はホッケースティックなんて見たことないのでホッケースティックのような形といえばホッケースティック恒等式の形ですが……
証明は易しく、 \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}（パスカルの三角形で隣り合う数を足したものがその下の数になっていること）を使って数学的帰納法を回すのが一番楽だと思います。組合せ的解釈で証明する方法もあって、知りたければ ABC154F - Many Many Paths の公式解説を読んでください。読んでないので嘘かも。

負の二項定理
k は非負整数とします。適当に二項係数の定義域を拡張してあげれば一般の整数でも成り立ちます。
\frac{1}{(1-x)^{k+1}} = \sum_{n=0}^{\infty}\binom{n+k}{k}x^n
です。形式的べき級数だと思っていますが、 |x| < 1 で収束するので普通のべき級数だと思ってもいいです。第二引数が fix されてて、嬉しい！
証明は、maspy さんいつもありがとうございます。

それらの関係
見るからに似ていますね。まずは負の二項定理の方が強そうな見た目をしているので、
負の二項定理 \Rightarrowホッケースティック恒等式
以下P:形式的べき級数に対して [x^n]P を P の x^n の係数とします。
負の二項定理より
[x^{n-k}]\frac{1}{(1-x)^{k+1}} = \binom{n}{k}。
\frac{1}{1-x} をかけることは累積和をとることに対応していたから、
[x^{n-k}]\left(\frac{1}{1-x}\frac{1}{(1-x)^{k+1}}\right) =[x^n]\frac{1}{(1-x)^{k+2}} =\sum_{i=0}^n\binom{i}{k}。
これと
[x^{n-k}]\frac{1}{(1-x)^{k+2}} = \binom{n+1}{k+1}
を比較することで
\sum_{i=k}^{n}\binom{i}{k}=\binom{n+1}{k+1}
を得ます。
ホッケースティック恒等式 \Rightarrow負の二項定理
実は逆もほぼ同様です。
k に関する数学的帰納法を使います。
[x^{n}]\frac{1}{(1-x)^{k+1}} = \binom{n+k}{k}
が成り立ったとして、\frac{1}{1-x} は累積和より、
[x^{n}]\frac{1}{(1-x)^{k+2}} = [x^{n}]\left(\frac{1}{1-x}\frac{1}{(1-x)^{k+1}}\right) = \sum_{i=0}^n\binom{i+k}{k} = \sum_{i=k}^{n+k}\binom{i}{k}
ここでホッケースティック恒等式を使えば
\sum_{i=k}^{n+k}\binom{i}{k} = \binom{n+k+1}{k+1}
より、示されました。
これは絵を描くとおもしろくて、

累積和をとると係数列が右下にずれるようになってるんですね～すごくない？全然気づかなかった

おわり
おわり

形式的べき級数の合成関数の微分って

ほんとに (P(Q))'=P'(Q)Q' みたいなの成り立つんですか？
P, Q を形式的べき級数とします。いつも通り [x^n]P を P の x^n の係数、P' を P の微分とします。Q は代入したいので、 [x^0]Q = 0 とします。 (P^n)' = nP^{n-1}P'*1を用います。
示したいのは、 (P(Q))'=P'(Q)Q' です。こういうのは泥臭くやると示せて、
\begin{align} [x^n]P(Q)=\sum_{k=0}^{n}[x^k]P\cdot[x^n]Q^k\end{align}
から、
\begin{align} [x^n](P(Q))'&=(n+1)\sum_{k=0}^{n+1}[x^k]P\cdot[x^{n+1}]Q^k \\\\&=\sum_{k=0}^{n+1}[x^k]P\cdot (n+1)[x^{n+1}]Q^k \\\\&=\sum_{k=0}^{n+1}[x^k]P\cdot [x^n](Q^k)' \\\\&=\sum_{k=0}^{n+1}[x^k]P\cdot [x^n](kQ^{k-1}Q') \\\\&=\sum_{k=0}^{n+1}k[x^k]P\cdot \sum_{l=0}^n [x^l]Q^{k-1}\cdot [x^{n-l}]Q' \\\\&= \sum_{l=0}^n(\sum_{k=1}^{n+1}k[x^k]P\cdot [x^l]Q^{k-1}) [x^{n-l}]Q' \\\\&= \sum_{l=0}^n(\sum_{k=1}^{n+1} [x^{k-1}]P'\cdot [x^l]Q^{k-1}) [x^{n-l}]Q' \\\\&= \sum_{l=0}^n(\sum_{k=0}^{n} [x^k]P'\cdot [x^l]Q^k) [x^{n-l}]Q' \\\\&= \sum_{l=0}^n [x^l]P'(Q)\cdot [x^{n-l}]Q' \\\\&= [x^n]P'(Q)Q'\end{align}
これは任意の n について成り立つので、 (P(Q))'=P'(Q)Q' が示せました。
よかったね。

（2022/08/31 追記）P が多項式の時も合成が定義できるみたいです。

*1:[多項式・形式的べき級数]（３）線形漸化式と形式的べき級数 | maspyのHP で示されています

zer0pts CTF 2022 writeup

人々もすなる writeup といふものを私もしてみむとするなり

こういうのは堂々としていたほうがいいらしいです

 

Anti-Fermat

いつものみたいな RSA が置いてあって、素数を生成する方法だけ怪しくて、q と p の xor が下数桁以外違うみたい。ここに至るまでに 33 時間かかった（ HUPC とか ARC とかが悪いよ）。

結局素因数分解をすれば良くて、n の下数桁と p, q の下数桁の積が等しいような p, q は全探索することにして、あと xor の情報から下数桁以外が復元できたらいいんだけど、これはできる。

p, q の bit を下から立てていくことにすると、p * q の i 番目の bit は畳み込みみたいな感じで求まって、例えば p, q の最下位 bit が違う場合だと p, q のどちらかの i 番目の bit を立てるかで p * q の i 番目の bit が変わってくるので、はい。最下位 bit が異なることは実はないので、うまくやらないとだめ。

ところで、実は繰り上がりっていうのがあって、困る。

 

なんか適当な writeup をみると賢いことをしていて賢いねになった。

OK

助かりまくり。問題は長くて、まず nc に v を渡すと k1 = (v - x1)**d mod n, k2 = (v - x2)**d mod n として k1 + key mod n と k2 + ciphertext mod n を返してくれる。こういうの典型として v = (x1 + x2)/2 とすると、k1 = -k2 になる（ d は奇数 ）。返してくれるものを足すと、 key + ciphertext mod n みたいなのが得られる。実は 0 <= key + ciphertext < 2*n なので、key + ciphertext は 2 択になる。実は ciphertext は flag を暗号化したやつ = f と key の xor なので f ^ key + key が得られた。

2 択なのは嫌なので絞っておくと、＾key + key によって偶奇は変わらない（睨めばわかる）ので f と偶奇が同じ方があたり。nc をいっぱいすると key が毎回変わって f ^ key + key がいっぱい得られる。偶奇が同じ f ^ key + key を集めておくとどちらかが全部本物でどちらかが全部偽物です。

f ^ key + key いっぱいから f を求めるパート。ありがたい話として、xor では繰り上がりは起こらず、+ では繰り上がりは 1 つしか起こらない。

f:id:w2w2_2:20220323040942p:plain

表

表を書くと、こんな感じになる。f の i bit 目に着目すると、1 のときは key の i bit 目によらない。0 のときはよって、これを使って決定していきたい。あといい感じの性質として i bit 目自体は key によらず、0 のときの繰り上がりにのみ関係する。これらの観察から、

  • まず f ^ key + key の i bit 目が同じものを集める。
  • もし、i bit 目が同じなのに i+1 bit 目が違っていたら、繰り上がりの有無が異なるということなので、f の i bit 目は 0。
  • 同じだったら、2 択を当てまくるのは確率的にすごいことなので、高確率で 1。

というように復元できる。

あとは f を復号してやれば ok（しゃれ）。

コードとか貼れるのか？f を求めるパートは C++ で頑張ればよかったんだけど、nc をいっぱい叩くパートで Python を書いたのがちょっと辛かった。

感想

おもしれ～。CTF、crypto 以外もやりたいね。ところで句点を書くのすごい抵抗ある