HTTPS

Other

はじめに

こんにちは。KMC7回生のcosです。今年度分の部費はすでに払っているのでまだ現役です。
この記事はKMCアドベントカレンダー2013の18日目の記事で、 昨日は2回生のtyage君による 定番SSHクライアント「Google Chrome」 についてでした。KMCにはSSHが趣味な部員たちが多いようで、昨日まではSSHネタが多かったので別な話をしたいと思います。というわけで、今日はTLS/SSLとHTTPSについて書きます。

HTTPSが必要な理由

多くのページHTTP通信を使用していますが、重要情報を扱うGmailとかamazonとかネットバンクは安全性のためにHTTPSを使用しています。HTTP + Digest(Basic)認証を使えばアクセスはできなくなりますが、通信を盗聴したり中間者攻撃ができてしまいます。
そこでSSLを使って盗聴・中間者攻撃を防げるようにしたのがHTTPSです。

HTTPSで保障されていること

HTTPS（というかSSL）を使うと以下の2点が保障されます。

  • 通信を暗号化することにより、クライアントとサーバ間の通信の盗聴を防ぐ
  • PKIを使った認証を行うことにより、中間者攻撃（なりすまし）を防ぐ

それ以外のことは保障されてないので、アクセス制限をしたい場合は別途Basic認証などが必要となります。

通信の暗号化は共通鍵暗号を用いて行い、鍵自体の交換はRSA暗号*1とかでやるので安全、と思いきや鍵の交換からなりすましが行われていた場合、RSA暗号を用いていたとしても中間者攻撃が成立してしまいます。

中間者攻撃という最強の攻撃を防ぐためにPKI*2を用いる必要があります。これは簡単に言うとWindowsとかのインストール時にルートサーバの鍵*3を埋め込んでルートサーバから順々に子サーバ、孫サーバの正当性を検証しつつ鍵を交換していく仕組みです。ルートサーバの鍵が安全に手に入るため、子サーバ・孫サーバの鍵も安全に手に入り中間者攻撃を防げます。

HTTPSを過信すると

以下の様なことが起きます。

  • サイト全体（https://example.com/）をHTTPS+Basic認証にして外部から見れなくしたと思ったらユーザーページ（https://example.com/~cos/とか）が丸見えだった。
  • サイト全体（https://example.com/）をHTTPS+Basic認証にしたらGitWeb（https://example.com/GitWeb/）が丸見えだった。
  • サイト全体がhttpsでhttpとか使ってないから、Cookieのsecure属性とか付けなくてもいいと思ったらhttp://example.com:443/にアクセスが来ていた。
  • HTTPSだから盗聴・改竄は無理なのでサーバの入力バリデーションをてきとうに作ったら、クライアント自身が改竄したデータを送ってきた。
  • 認証機能をてきとうに作ったらオレオレ証明書を信用してた。
  • 政府のページを使用するのになぜかルートCAを入れる必要がある。
  • クライアントもサーバも問題無いと思ったら認証局がハックされてた。

おわりに

時間が無かったので図もない手抜きの記事になってしまいました。特にPKI周りは端折りすぎな気がします。さて、明日はhidesys君がRails4の新機能について書くそうです。お楽しみに。
KEEP YOUR DIGNITY

*1:盗聴が出来ない暗号方法。

*2:という残念な仕組み。個人的には技術の敗北だと思う。

*3:本当は証明書だけど。

TCO 2013 Round1A

Topcoder Online Judge

環境が変わったのでちょっとテストしてから本番へ。

250

  • ループ回すだけ。
    • Round1ってこんなに簡単だったけ？

500

  • かえるジャンプ
    • 1ずつ増やして確かめれば良くない？と思ったら浮動少数だった。
    • 2分探索は使えんよなあ。
    • この手の問題は限界を攻めるのがパターンなんで試してみたらそれっぽい。
    • 書いた。誤差死が怖いけど少しテストした分には大丈夫っぽいので提出。

1000

  • またグリッドですか。
    • これって閉路壊した方が良い場合とかもあるよね…。
    • グラフで考えると…、全ての頂点で入次数が1になればよいのか。なんかフロー臭がする。
    • 普通にMinCostFlowで解けますね。
    • 書いた。提出。

Challenge Phase

  • コーナーケースがあまり思い浮かばなかったので250をながめてみる。
    • 灰色の人のコードは読みづらいですね。

結果

ooo 1316.21pts 11位 2161→2266
実は1000解けたの初めてだけど、あんまり嬉しくない。

Cards shuffing (SPOJ 4390)

SPOJ Online Judge

https://www.spoj.pl/problems/CARDSHUF/

問題

[1,N]までの数列に対して、i番目の数値をj番目に移動するという操作をM回繰り返す。最終的にできた数列を元の数列に戻すのに何回操作を行わないといけないか答えよ。
1<=N,M<=100,000

解法

平衡二分木でO(logN)で操作を行い最後の数列を作る。最後の数列から最初の数列に戻すのに必要な操作の回数は N-最長増加部分列の長さ なのでこれをO(NlogN)で計算してやれば良い。
TLEが異常に厳しいので平衡二分木の高速化が必要。具体的にやった高速化は、randをXorシフトに変更、Splitを使わないEraseにした、最初の数列を完全二分木で作ってやったなど。

O(sqrt(N))のアルゴリズム

Other

これはCompetitive Programming Advent Calendar Div2012に投稿された記事です。
さて、N=1,000,000,000みたいな数値を見ると、O(N)は無理だからO(\log N)かとか、もしくはN=100,000だとO(N\log N)と思ってしまう人は多いでしょう。ですが、\log Nまで行かなくてももう少し悪い計算量が想定解の場合もあります。というわけで、今回はO(\sqrt{N})だとかO(N^{1.5})という、ルートが入ったあまり見ない計算量のアルゴリズムを紹介します。

等差数列の和

N=\sum_{x=1}^yax+bとなるようなyを見つける問題はO(1)で解けますが、Nになるまで愚直に足していけばO(\sqrt{N})で解けます。こんなもんどこで使うんだと思う人もいるかもしれませんが、手計算が面倒な場合とか証明したい場合に使います。

素数判定

素数判定はO(\sqrt{N})までの数値で試し割りすることによって判定できます。もちろんミラーラビン法などを使えばもっと高速に判定できますが*1手軽に使えるというメリットがあります。

floorの分割

f(N)=\sum_{x=1}^Ng({\rm floor}(N/x))みたいな式があったとしましょう。ただし、g({\rm floor}(N/x))はO(1)で計算できるとします。
この式を愚直に計算すると、もちろんO(N)かかってしまいます。ここで{\rm floor}(N/x)が同一のものをまとめて処理することにします。するとf(N)=\sum_{y\in S}c(y)g(y)となります。ただしSはfloor(N/x)の値域、c(y)はfloor(N/x)=yとなるxの個数とします。
Sのサイズを計算すると実はO(\sqrt{N})で抑えることができます。なぜ、SのサイズがO(\sqrt{N})で抑えることができるかとういと、{\rm floor}(N/x)=y \le \sqrt{N}となるyはもちろん\sqrt{N}個以下しか存在しません。一方で{\rm floor}(N/x)=y > \sqrt{N}となるにはx < \sqrt{N}という条件を満たさなければならないのでこれも\sqrt{N}個以下しか存在しません。なのでこの式をO(\sqrt{N})で計算することができます。
問題例：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3558

離散対数問題

離散対数問題とはa,b,Nがgivenの下でa^m \equiv b {\rm mod} Nとなるようなmを見つける問題です。
この問題は効率的な解法が見つかってませんが*2、baby-step giant-stepを使えばO(\sqrt{N})で解くことができます。
まず、m=x+y\sqrt{N}と分割し、a^0, a^1, \ldots, a^{\sqrt{N}}までは普通に計算しハッシュなどに結果を保持しておきます。次にa^x\equiv ba^{-y\sqrt{N}} {\rm mod} Nを考えます。yを[0,\sqrt{N}]の範囲で全探索すると右辺は値が固定されるので、先程計算しておいたハッシュに値が含まれているかどうか確認すればxが求まります。
前処理も全探索の処理も両方O(\sqrt{N})なので、O(\sqrt{N})で答えが見つかります。
問題例：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=229&page=show_problem&problem=3067

平方根分割

主にクエリの平方根分割と配列の平方根分割があります。
クエリの平方根分割はクエリを\sqrt{Q}個処理するごとにデータ構造を作り直し、それぞれの区間で使われていない値を無視することにより各クエリをO({\sqrt{Q})くらいで処理できるようにします。
配列の平方根分割は配列を\sqrt{N}のブロックごとに分割し、[l,r]の範囲クエリが来た時にブロックを全て含む部分は高速に処理し、端っこの部分は愚直に処理します。ブロックの数はO(\sqrt{N})個しかないし、端っこの部分はO(\sqrt{N})個のデータしかないので1つのクエリあたりO(\sqrt{N})で処理できます。
ここらは毎回使うデータ構造が微妙に異なってくるので、回数をこなして慣れましょう。ちなみに平方根分割の問題はだいたい平衡二分木や動的木などを使えば計算量が落ちる上に、ライブラリを持っているとそっちの方が実装が楽になります。

問題例（クエリの平方根分割）：http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2235
問題例（クエリの平方根分割）：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=288&page=show_problem&problem=1962
問題例（配列の平方根分割）：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=242&page=show_problem&problem=3154
問題例（配列の平方根分割）：http://codeforces.com/problemset/problem/121/E
問題例（Block Linked List）：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=229&page=show_problem&problem=3073

二部マッチング

Hopcroft-Karpアルゴリズムを使えば二部マッチングはO(E\sqrt{V})で解けます。
Hopcroft-KarpとはDinicのアルゴリズムを二部マッチングに適用したものです。つまり、フェーズごとにレベルグラフ*3を作り、各フェーズで増加パスが存在する限りフローを流すアルゴリズムです。
計算量の解析としては、まず容量が1なので各フェーズの処理がO(E)に落ちます。次に、\sqrt{V}のフェーズを過ぎると増加パスの長さが\sqrt{V}以上になりますが、解のマッチングとの対象差(辺集合のxor)を比べた時に残る点素な増加パスはたかだか\sqrt{V}個なので*4、残りのフェーズの数はO(\sqrt{V})個で抑えられます。両方を合わせるとO(E\sqrt{V})となります。
問題例：http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2279

最大流問題

最大流問題のアルゴリズムはEdmonds-KarpやDinic、藤重のアルゴリズムなど色々あります。
そして、Goldberg-Tarjanアルゴリズムは最大流問題をO(V^2\sqrt{E})で解きます。
藤重のアルゴリズム（O(VE\log u_{\rm max})）は計算量に容量がはいっていて、ナイーブなDinicはO(V^2E)なので、これらのアルゴリズムよりも理論上は高速に動きます*5。計算量の証明をすると長くなるので省略しますが、各フェーズで不飽和プッシュの起こる回数を\sqrt{E}以下と以上に分割することにより\sqrt{E}がかかっています。
さて、Dinicの計算量はO(V^2E)と書きましたが辺の容量が1であるという制約がかかっている場合はO(\min (V^{2/3},\sqrt{E})E)まで計算量が落ちます。なぜ\sqrt{E}になっているかというと、\sqrt{E}回目のフェーズであればレベルグラフのd層目とd+1層目の間に辺が\sqrt{E}以下しかない所が出てくるため*6、残りの増加パスはたかだか\sqrt{E}個しかない、つまり残りフェーズがたかだか\sqrt{E}個しかないことが言えるからです。V^{2/3}も辺が頂点に変わっただけでほぼ同じ証明でできます。

まとめ

\sqrt{N}が入っているアルゴリズムを色々紹介しました。
\log Nの方はたびたび出ますが、時々でいいから\sqrt{N}のことも思い出してやってください。
たまに出てくるので。

参考文献

Wikipedia Baby-step giant-step：http://en.wikipedia.org/wiki/Baby-step_giant-step
Wikipedia Hopcroft-Karp：http://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm
組合せ最適化：http://www.amazon.co.jp/dp/4431100210
どっかの大学の講義資料：http://people.orie.cornell.edu/dpw/orie633/LectureNotes/lecture9.pdf

*1:感覚的にはN\le 10^9でO(100)くらい

*2:入力ビット数について多項式時間で解く方法は見つかっていない

*3:全頂点について始点からの距離がを求めておいて、距離が+1される箇所にのみ辺を張ったグラフ

*4:頂点の数÷増加パスの長さ≧点素な増加パスの個数なのでV / \sqrt{V} = \sqrt{V}となり\sqrt{V}個以下になる

*5:最大流問題の計算量の解析はフェーズがV-1個あるとか、ブロックフローの計算にO(VE)かかるとか、不飽和プッシュがO(V^2\sqrt{E})回行われるとか普通起こらないことを前提としているため、実際に動かすと計算量以上に速く動く。競技プログラミングではDinicで十分なことがほとんど。

*6:辺の数÷層の数＝E/\sqrt{E}=\sqrt{E}≧各層で使われている辺の数の最小値なので

Dungeon (AOJ 0553)

AOJ Online Judge

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0553

問題

略

解法

尺取メソッドでやる。
潜れる場合は何も考えずに潜る。潜ると死ぬ場合は、headとtailの間で回復量最大の泉で回復する。HPの上限に達する場合は2番目に回復量が大きい泉と比較して良さげなら回復する。

Location for a Power Generator (UVa Live Archive Asia - 2009 Hsinchu(Taiwan))

UVa Live Archive Online Judge

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=350&page=show_problem&problem=2531

問題

携帯型原子力発電機で街の各家庭に電力を供給したい。発電機からの距離がl以下の時にその家には電力が供給される。1台の発電機で同時に電力を供給できる家庭の数と、その場所の選び方の数を答えよ。
家の数<=1100

解法

要するに、なるべく多くの点を含む円を見つければ良い。これは極座標平面での平面走査を使えばO(n^2logn)で求めることができる。
具体的には、ある点iを極座標の中心として、点iからl離れた円周上で円を動かすことを考える。こうすると点jは角度θで円に入り、θ'で円から出ると計算できる。全てのjでこれを計算し角度をソートしてどの点が円に入っているかを計算すればO(nlogn)で点iについての計算ができる。
場所の選び方の数は実際に円に入っている点の集合を全て列挙すれば良い。
最後に無駄な改行を入れないとWAになるので注意。