-
- いいね！0
ぜんぶまるでわからん
@5her0
頑張ってみる。例えば、ある暗号の鍵長を k としたとき、攻撃するのには最低でも 2^k 回の掛け算が必要だとします（ちょっと嘘だけどそういうことにします）。するとこの暗号は計算量的に安全と言います。
2011-11-09 15:21:36
ぜんぶまるでわからん
@5her0
でも実際に使うときは鍵長を決めます（例えば1024）。すると、2^{1024} 回掛け算ができれば攻撃可能だということになります。暗号の鍵長を決めるときには、この 2^{1024} がコンピュータでは計算できないくらい大きくなるように決めます。
2011-11-09 15:23:21
ぜんぶまるでわからん
@5her0
しかし、その後コンピュータが進化していくと、 2^{1024} 回掛け算しちゃうようなすごいコンピュータが出てきます。この状態が俗に言う危殆化（だと思う）です。
2011-11-09 15:24:43
ぜんぶまるでわからん
@5her0
ではこの状態は暗号が「鍵長の多項式時間で解ける」状態かというと、そんなことはありません。なぜなら、暗号を解くためには鍵長の指数回の計算をしているからです。（1024ビットで2^{1024}回の計算をしている）
2011-11-09 15:28:12
ぜんぶまるでわからん
@5her0
「多項式時間で解ける」とは、あくまで鍵長の多項式倍の計算をすれば（ちょっと嘘）解けるということを指しています。今回は、鍵長の指数倍（2^{1024}）だけ計算しているので、多項式時間では解けていません。
2011-11-09 15:33:45
ぜんぶまるでわからん
@5her0
つまり、暗号が危殆化している状態とは、鍵長の多項式時間では解けていないけれども、鍵長が短いので、（たとえ解くのに鍵長の指数時間かかろうが）現実的な時間内で解ける状態を指します。
2011-11-09 15:41:51
ぜんぶまるでわからん
@5her0
例えば鍵長 k のとき、解くためには2^k回計算しなくてはいけない暗号があったとします。これは"安全な"暗号ではありますが、例えば鍵長が2ビットだったりすると、2^2=4 回計算すれば解けてしまう。これは「指数時間かかっている（多項式時間ではない）けど現実的に解ける状態」。
2011-11-09 15:45:10危殆化と脆弱化
Masaki SHIMAOKA
@4ma_
@5her0 私の認識は逆で、2^1024の計算量が現実的な計算コストで可能になるのが脆弱化、2^1024未満の計算量で計算できるようになってしまうのが危殆化、という認識でした。
2011-11-09 15:43:43
ぜんぶまるでわからん
@5her0
おっと、俺の顔真っ赤フラグが立ったぞｗ脆弱化ってなんだろうｗ RT @4ma_: @5her0 私の認識は逆で、2^1024の計算量が現実的な計算コストで可能になるのが脆弱化、2^1024未満の計算量で計算できるようになってしまうのが危殆化、という認識でした。
2011-11-09 15:45:58
Masaki SHIMAOKA
@4ma_
@5her0 設定した計算量より少ない計算量で解けるのは、暗号学的な想定強度を下回ってしまっているという意味で危殆化。設定した計算量が想定した(ややこし)絶対時間よりも短い時間で計算可能になるのが脆弱化。という認識(私的定義)です。
2011-11-09 15:46:56
Masaki SHIMAOKA
@4ma_
@5her0 あ゛ぁ゛ぁ゛、失礼しました。。。世間の認識がどうかはわからんです。あくまで私の認識ですが。 いずれにしても両者が別物であり、違う名称で識別しようという点は共通してると信じてますw
2011-11-09 15:49:01
菅野 哲 / GMOイエラエ 取締役CTO
@satorukanno
@4ma_ @5her0 脆弱って言葉が出てくるシチュって，そのアルゴリズム自体に対する攻撃が発見されるなどの欠陥が見つかった場合に使うなぁーと印象です． 脆弱性がある結果，危殆化する的なイメージです． 感覚的な話で申し訳ないです．
2011-11-09 15:53:20
ぜんぶまるでわからん
@5her0
設定とかを使うとこう言い換えられるのか。 暗号は最初に「解くのにこれぐらい計算が必要なら、現在のコンピュータでは解けないだろう」という”難しさ”を決めます。その後コンピュータが進化して、ゴリ押しで計算できてしまうようになるのが危殆化。解くのにもっと簡単な方法が見つかるのが脆弱化。
2011-11-09 15:56:41
Masaki SHIMAOKA
@4ma_
@satorukanno @5her0 危殆化と脆弱化は別物なのかスコープの大小の違いなのか、という見方も確かにありますね。
2011-11-09 16:00:54
Masaki SHIMAOKA
@4ma_
えと、脆弱化と危殆化の定義については完全に私の認識が逆でした(勘違いレベル)すみません。一方で、危殆化が脆弱化を含むものかどうかという論点はどうなんだろう?
2011-11-09 16:06:14
Masaki SHIMAOKA
@4ma_
.@satorukanno さんの論点も尤もで、本来の安全性を保てなくなることが危殆化というならば、「もっと簡単な方法が見つかる」のも「ゴリ押しで計算できるようになる」のもどちらも危殆化。前者は脆弱化で合意したとして後者はなんと呼べばよいか?
2011-11-09 16:11:38