Sorry for using broken English:bow: Welcome :yum: Merkle Hellman Since all of possible charactors are encoded to number one-to-one, we can just create the table of the encoded number. pub = [7352, 2356, 7579, 19235, 1944, 14029, 1084] priv = ([184, 332, 713, 1255, 2688, 5243, 10448], 20910)

まえおき これは2020年8月に競プロのリハビリをしようと思った際に、あまりにも終わりみたいな気持ちになったのではてなブログに書き散らした下書きです。要するに競技プログラミングを楽しめなくなった拗らせ終わり人間の末路。誤字とかは修正してますが、それ以外は原文ママです。みんなはこれを反面教師にして、健全なメンタルで健全に競技プログラミングを楽しもう！ 当時のステータス B1 AtCoder 2300くらい 本編 前提

概要 FSB があるが、一度しかできない(+文字数制限 160 文字) コード #include <stdio.h> int x = 0xc0ffee; int main(void) { char buf[160]; scanf("%159s", buf);

Overview You can write 0x1f bytes data to: buffer alloced on stack buffer alloced on heap /dev/null stdout Analysis

問題概要 $e=20000$ と 20 bit のランダムな素数 $p$, $q$ を用いて $b$ bit の数 $m$ を RSA 暗号で暗号化したものが 2×200 個与えられる。$m$ を解読せよ。 問題: https://github.com/kurenaif/kurenaif_2000_subscrivers_challenge 解法 まず、$p$ と $q$ が十分小さいので素因数分解が簡単にできる。なので、$p$ と $q$ は与えられるとして良い。 すると $m \bmod pq$ は容易に求めることができそうであるが、今回はそれをすることができない。なぜならば、$\phi(p\cdot q)=(p-1)(q-1)$ と $e$ が互いに素でないため、複数個の候補が出てきてしまうからである。しかしこの複数個の候補は十分高速に求めることができる[^1]。なので、これらから flag を復元することを考えよう。$m \bmod n_1$ と $m \bmod n_2$ が分かっているとするとき、中国剰余定理から $m \bmod n_1n_2$ を求めることができる。そのため、候補のうち正解を選ぶ組み合わせを全て試せば理論的には解読できることになる。しかし候補は 2000 個近くあるため、これではうまくいかない。しかし、$m < 2^b$ だったことを思い出せば、$2^b \le M$ ならば $(m \bmod M) < 2^b$ が成り立つことが分かる。これを用いて枝刈りをすると、そこそこの時間で $m$ を求めることができる。 [^1]: Tonelli-Shanks のアルゴリズム等