2017-08-21

8/21 サマーウォーズを見てRSA暗号について調べた

普段テレビはほとんど見ないのだけれど, 先日は金曜ロードショーのサマーウォーズを見てました.
相変わらずいつ見てもいい作品だなぁとか夏希先輩かわいいなぁとか思いつつ, Twitterでわいわいしてました.

サマーウォーズが放送されると必ず話題に上がるのが健二が解いているあの暗号の話.
解いている様子の描写からRSA暗号じゃないかと言われています.
RSA暗号というと素因数分解というイメージが強いのですが, あまり暗号化と複合の部分がどういう原理でできているのかについては理解できてませんでした.
というわけで, サマーウォーズを見ながらいろいろと調べて考えてみたことをまとめてみたいと思います.

公開鍵暗号方式

そもそも, RSA暗号は公開鍵暗号方式の一種で, 2つの鍵を用いて暗号化と復号を行います.
簡単に言うと, 以下の2つの性質を持つような暗号です.

1. 片方の鍵で暗号化したら, もう片方の鍵でしか復号できない.
2. 片方の鍵からはもう片方の鍵は(簡単には)推測できない.

RSA暗号の基本的な仕組み

RSA暗号の基本的な仕組みについてはWikipediaなどを参照してもらうと良いと思うのですが, 簡単に書いておきます.
RSA暗号 - Wikipedia

$p$ , $q$ : 任意の素数, $n = pq$
$e$ : $(p - 1)(q - 1)$ と互いに素な任意の正の整数(公開鍵)
$d$ : $ed = 1 \pmod{(p - 1)(q - 1)}$ を満たす正の整数(秘密鍵)
$m$ : 平文, $C$ : 暗号文
暗号化: $C = m^e \pmod{n}$
復号: $m = C^d \pmod{n}$

というわけで, 実は累乗が計算できれば暗号化と復号は簡単にできます...
ってほんまか？となるわけですね.
これってつまり, $m^{ed} = m \pmod{n}$ が成り立つってことに他ならないわけです.
さすがに自明ではないよなぁ......と.

復号がうまくいくのはフェルマーの小定理で説明できる

『高校数学の美しい物語』の説明がわかりやすかったです.

mathtrain.jp

少し補足をすると, 合同式には以下の性質があります.

$a = b \pmod{p}$ かつ $a = b \pmod{q}$ ならば $a = b \pmod{lcm(p, q)}$
( $lcm(p, q)$ は $p$ と $q$ の最小公倍数を表す.)

つまり, $m^{ed} = m \pmod{n}$ を示すためには, $m^{ed} = m \pmod{p}$ を示せば十分ということになります.

興味深いのは, フェルマーの小定理を用いているところです.
これを利用してうまく暗号化ができるようになっているわけですね, 賢い.

素因数分解の困難性が安全を保証している

公開鍵暗号方式なので, 公開鍵 $(e, n)$ から秘密鍵 $(d, n)$ が推測されると暗号を突破されてしまいます.
秘密鍵を推測するためには $ed = 1 \pmod{(p - 1)(q - 1)}$ を満たす $d$ を計算する必要があります.
つまり, $n$ を素因数分解して $p$ , $q$ を求め, $(p - 1)(q - 1)$ を計算する必要があるわけです.

素因数分解は $p$ , $q$ が十分に大きな素数であれば現実的な時間で解くことはできません.
逆に言えば, 素因数分解ができてしまえば暗号を解読することができます.

「RSA暗号 = 素因数分解」というイメージ

サマーウォーズを見ながら, 流れてくるRSA暗号についてのツイートを眺めていたのですが, 「素因数分解する暗号」という説明が結構多かった気がします.
まぁ確かに「ふたつの素数 $(p, q)$ から積 $n$ を求めるのは簡単だけれど, $n$ から $(p, q)$ を計算するのは困難」と言われると, なんとなくわかったような気がしてしまうんですよね.
「素因数分解が効率よくできない」って直感的なのでそういう説明が出てくるのはわかるのですが, それって誤解の原因になりやすいんじゃないかなぁと.

人間って直感的な事柄の次に非直感的な事柄が出てくると, なんとなく理解した気になってしまうところがあると思います.
やはりそういう説明で納得してしまうことのないように気をつけたいなぁと.

まぁ, そんなことを考えていたよ, というお話でした.
(余談ですけど, はてなブログってTeXの数式を書くとMathJaxでレンダリングしてくれるんですね.)

2017-08-11

8/11 AtCoder Regular Contest 080

この前うっかり寝過ごしてで損ねたARC080を解いた.

C: 4-adjacent - AtCoder Regular Contest 080 | AtCoder [解答]
数列の要素を自由に並び替えて隣り合う要素の積が4の倍数になるようにできるか判定する問題. Aiが奇数, (4の倍数でない)偶数, 4の倍数で隣に置かなければならない数の条件が変わることに注目する. Aiが奇数なら, 隣には必ず4の倍数をおく必要がある. Aiが偶数なら, 隣には偶数をおく必要がある. Aiが4の倍数なら, 隣におく数はなんでも良い. ここから考えると, { 奇数, 4の倍数, 奇数, 4の倍数, ..., 4の倍数, 偶数, 偶数, ... }みたいな並びが作れるかを判定すれば良いことになる.
D: Grid Coloring - AtCoder Regular Contest 080 | AtCoder [解答]
1, 1, 1, 2, 2, 3, 3, 3, 3, ...., N, N, Nと左上から順に要素数H * Wのマス目を埋めていき, 奇数番目の行だけreverseして表示すればOK.
E: Young Maids - AtCoder Regular Contest 080 | AtCoder [解答]
辞書順で最小のものを構成するのは後ろから考えるとやりづらいので, 先頭から小さい数字を順に決めていくことを考える. 最初の状態からqの先頭2つの要素を決めるのには, 偶数番目の要素でもっとも小さい値とその要素以降で奇数番目の要素を取るのが最良. この二つの要素がpのi, j番目だとすると, pは[0, i), [i + 1, j), [j + 1, N)の3つの要素に分断される. qの次の2要素はこの3つの領域の偶数番目の値から最小のものを選ぶことになる. これを繰り返していけばO(N^2)でqを求めることができる.
ここから計算量を落とすためには, 偶数番目/奇数番目の要素から最小を求めるのにセグメントツリー, 分割された領域からどれを選ぶかはpriority_queueを用いればよい. 具体的な手順としては,
1. { [0, N), min_odd }をpriority_queueに入れる
2. priority_queueから最小のものを取り出す
3. 3つの領域に分割して, それぞれをpriority_queueに入れる
4. priority_queueが空ならループ終了, そうでないなら2に戻る
という感じ. 結構実装がしんどかった...

2017-08-08

8/8 束の間の夏休み

8/3で無事に春学期の期末試験を全て終えて夏休みに突入した. しばらくは休養がてらアニメ見たりして過ごしてた. 昨日から大学の夏期集中講座でまた学校に来ている. なんだかオープンキャンパスで高校生がいっぱいいたり, 何かのイベントで小学生がいっぱいいたりして普段とはかなり違う雰囲気.

AtCoder

B: Colorful Creatures - AtCoder Grand Contest 011 | AtCoder [解答]
スライムがN個あってそれぞれの大きさA[i]が与えられている. スライムは自分の大きさの2倍以下の大きさのスラムを吸収してその分大きくなることができる. こうしてスライムが吸収を繰り返して最後に残るスライムが1個になる時, 最後に残るスライムは何通り考えられるかという問題.
とりあえず, 大きさの昇順にソートして考えてみる. 昇順に並んでいれば, i番目のスライムは1からi - 1番目までのスライムを吸収することができる. i番目のスライムがそれら全てを吸収すると大きさは, A[1]からA[i]までの和sumとなる. この時A[i + 1] <= sum * 2であればi番目のスライムがi + 1番目のスライムを吸収することができる. A[i + 1] > sum * 2であれば, どう足掻いてもi番目のスライムは全てのスライムを吸収することはできない. よって, A[i + 1] > sum * 2となる最大のiを探せば, 答えはN - iとなる. そのようなiが存在しない場合は答えはNとなる.
実際の実装では降順にソートして, A[i] > sum(A, A + i - 1)となったところでループを抜けるって感じにしてます.
B: Mysterious Light - AtCoder Grand Contest 001 | AtCoder [解答]
光が2個めの反射点に辿りついた直後, 残っている正三角形の領域は平行四辺形になっていることに注目すると考えやすい. このあと何度か光が反射すると再び平行四辺形ができる. この時, 何回光が反射すると次の平行四辺形になるかは二つの辺の長さから計算できる. また, 次の平行四辺形の辺の長さも同様に計算できる. 具体的には辺の長い方をa, 短い方をbとするとa = b, b = a % bになる. これを見てわかる通り, 辺の長さはlogで減っていく. イメージとしてはユークリッドの互除法みたいな感じ. これをbが0になるまで繰り返す.

2017-07-30

7/30 ISUCONの練習始めました

今年こそISUCONに出たい

前々からISUCONにチャレンジしてみたいなぁーと思っていたのもあって, 今年こそはちゃんと練習しようと思っています. 夏休みに入って時間も取れるようになってきたので.

とりあえず, Vagrant使って過去問を触ってみる. ISUCON過去問とほぼ同じサーバー環境をVagrantで構築するためのVagrantファイルを公開してくださっている方がいるので, それを使う. 圧倒的感謝.

d.hatena.ne.jp

github.com

環境構築の手順

リポジトリをgit cloneして立ち上げたい問題のディレクトリに移動, vagrant upするとサーバーが起動する. ちなみに, 起動には結構時間がかかるので注意. あと, なぜかISUCON6のqualifyはうまく立ち上げられなかった. というわけで, isucon5-qualifyを立ち上げてとりあえずベンチを取ってみるところまでメモしておきます.

1. Virtualbox, Vagrantのインストール

brew cask install virtualbox
brew cask install vagrant

すでにインストールしている場合は, バージョンが古いとエラーが出ることがあるようなので再インストールしておくといいと思います.

brew cask reinstall virtualbox
brew cask reinstall vagrant

2. Vagrantfileが入っているリポジトリをcloneしてくる.

git clone https://github.com/matsuu/vagrant-isucon.git

3. 立ち上げたい問題のディレクトリに移動してvagrant up

cd vagrant-isucon/isucon5-qualifier/
vagrant up

これが結構時間かかります. 気長に待ちます. 諸々の準備が終わるとimageというサーバーとbenchというサーバーが起動しているはずです. きちんと把握してないですが, imageは問題を解く用, benchは負荷走行用かなと思っています. おそらく, 予選本番ではimageの方だけが参加者には与えられていて, benchサーバーにはベンチマーク取ってくださいってリクエストをするだけなのかと.

もしかしたらstandaloneは両方立ち上げないのかも. そうだとしたらそっちの方が早く起動できる(？).

4. imageサーバーにsshで接続する

vagrant ssh image

5. ユーザーを切り替える

ログインするとvagrantユーザーになっていると思うので, isuconというユーザーに切り替えます.

sudo su - isucon

そこでlsしてもらうといろいろファイルがあるのがわかると思います. 基本的にはアプリケーションなどの中身は/home/isucon以下に置かれてます.

6. とりあえずベンチを取ってみる

/home/isucon以下にbench.shというスクリプトがあるのでそれを実行します.

./bench.sh

しばらく待っているとベンチが終わって, 以下のような結果が標準出力に出てきます. これがスコアになるようです.

...
Isucon5Checker
done
success
114.1
{"success"=>206, "redirect"=>81, "failure"=>1, "error"=>0, "exception"=>0}
アプリケーションが 3000 ミリ秒以内に応答しませんでした

ここからやること

基本的にはNginxとMySQLのログを見ながらボトルネックになっている箇所を探していくことになるかなぁと考えています. MySLQはベンチ取った時のログをざっと見る限りでは結構N+1クエリがありそう. 他にもいくつか時間かかっているクエリもあったのでそのあたりを中心に見ていくことになりそう. あと, 実際にブラウザからアクセスもしてみるとどういうお題なのかわかりやすくていいかなぁと.

チームメンバーに競プロerがいるので, C++でゴリゴリ書き直すみたいな戦略も面白いかなぁって思っている. ちなみに, 昨年はC++で予選を突破したチームが1つだけいた模様. と思って調べてみたらまさかのこのチームで爆笑してしまった.

ISUCON6予選をC++で参加して予選通過した話 - いもす研 (imos laboratory)

さすがに自前でC++のWebサーバーを作るのは険しすぎるのでC++でCGIとか作ってみるのはどうかなぁなんて考えているところ. どれぐらい速度出るか全くわからないけれど.

2017-07-30

7/29 ARC079

AtCoder Regular Contest 079

C, Dを解いて2完. Eはにぶたんとかいろいろ試したけれどダメだった. Fは問題さらっとしか読んでないです.

C: Cat Snuke and a Voyage - AtCoder Regular Contest 079 | AtCoder [解答]
島1から繋がっている島すべてに対して, Nと繋がっているかどうかを調べる.
D: Decrease (Contestant ver.) - AtCoder Regular Contest 079 | AtCoder [解答]
K回操作を行った後に0, 1, 2, 3, ..., N - 1という長さNの数列になるような数列を作る. 1回操作を行ってこの数列が得られるような列の中にはN, 0, 1, 2, ..., N - 2という列がある. 同様に, 2回操作を行ってこの数列が得られるような列の中にはN - 1, N, 0, 1, ..., N - 3というものがある. これを一般化すると, A[i] = K / N + (N - i - 1) + (i < K % N)とすれば良い. Nはとりあえず50にしておいた.
E: Decrease (Judge ver.) - AtCoder Regular Contest 079 | AtCoder [解答]
最大になるものを選んでとあるが, 実は操作する順番を変えても答えは一緒になる. なので, A[i]がN未満になるまで減らして他の要素には+1をするというのを全要素がN未満になるまで繰り返せば良い.
コンテスト中は二分探索をしようと思ったのだけれどどうやら, 解の付近で単調性が崩れるらしくて正しく答えが求められなかった. ちなみに, 解の範囲をある程度絞った後で範囲のしたから解を探すってことをしたら通った(提出コード).
周辺まで見る二分探索をしているレッドコーダーの方もいたみたいで, その正当性をTwitterで話していたけれど正直よくわからなかった.

2017-07-27

7/27 久々に.vimrcを整理したい

今までずっと補完というものを使わずにプログラムを書いてきた. なのだけれど, 英単語のスペルミスがあまりにも多かったり, 特定の単語を特定の間違い方することが多いので補完を使ってみることにした. とりあえず, vimの標準の補完機能(ctrl + p)を使ってみたけれど, 普通に慣れていないと押すのを忘れそう. というわけで, NeoCompleteというプラグインを入れてみた.

github.com

設定を.vimrcに書いておけば, プログラム書いてると勝手に補完窓が出てくるのでひたすらTabを押せばOK. これなら慣れてなくても使えそう. あとは言語ごとに辞書ファイルとか追加しておくと便利そう.

ちなみに, このプラグインはluaを使っているらしく, 自分の使っているvimにはluaを入れていなかったため, brewでインストールし直した. brew install vim --with-luaでlua付きでコンパイルされる. 途中pyenvと何かがコンフリクトしたっぽく, インストールするときだけ.bash_profileからpyenvのパスを通している部分をコメントアウトした.

他に最近ほしいなと思った機能が, vimでcsvファイルを開いた時にコンマで整列させるスクリプトとか. これないとさすがにデータの中身を覗くのがしんどいので. 今は普通にExcelでファイルを開いているけれど, csvの中身を見るためだけにいちいちExcel起動させるの面倒だし.

その他でvimrcをきちんと整理したいと思っているのが, quickrunの設定. 何かの言語を実行する時に非同期実行だと結果がうまく得られなくてオフにしているのだけれど, やっぱりほしいなと.

2017-07-25

7/24 AGC018とか

AtCoder Grand Contest 018

安定の1完(). A問題が難しくて普通にお葬式になるところだった. Bは言われれば貪欲だなぁ〜って感じ.

A: Getting Difference - AtCoder Grand Contest 018 | AtCoder [解答]
A問題なのに難しい. A[i]が{ dm | m = 1, 2, 3, ... }の部分列となるような最小のdを求めると, max(A[i])以下のdmで表される数は全て表現することができる. このようなdはd = gcd(A[0], A[1], ..., A[N - 1])で計算できる. ちゃんとした証明はしてないです.
B: Sports Festival - AtCoder Grand Contest 018 | AtCoder [解答]
全部のスポーツを開催した状態から一番参加者が多いスポーツを減らしていくgreedy. 1個ずつ減らしながら最大の最小をとる.

ABC/ARC D問題埋め

D: No Need - AtCoder Regular Contest 070 | AtCoder [解答]
部分点解法は, ある1枚のカードを抜いて部分和を列挙する. 和がK未満の部分集合に抜いたカードを入れて和がK以上になれば, そのカードは不要ではない. 抜くカードの選び方がN, 部分和の列挙がO(NK)なので, 全体で計算量はO(N^2 * K).
満点解法は, しばらく考えたのだけれどわからなくて解説を見てしまった. 実はカードを書かれている数字の昇順でソートすると, カードiが不要ならカード(i - 1)も不要となる. なので, 必要なカードと不要なカードの境界を二分探索する. もちろん, 二分探索の判定部分では部分和のDPをする. 全体としての計算量はO(logN * NK)になる.

0x19f (Shinya Kato) の日報

主にプログラミング関連の話をします