素のRSAの安全性の評価 - ちりもつもればミルキーウェイ

はじめに

RSAの基本的なしくみがわかったところで、RSAの安全性がどの要素に依拠しているのか紹介しその困難性について紹介します。 RSA自体の困難性はおもに素因数分解の困難さに依拠しているので、かるくそのあたりのトピックの紹介もします。素因数分解アルゴリズムの紹介とかはまた今度です

あと、素のRSA暗号の安全性を暗号の攻撃モデルなどと組み合わせて評価してみます。

これを読めば、いままで何度か言ってるように素のRSAは安全でないからあんまり使わないほうがよい！といってるのがきっと理解できるはず！

それではやっていきます

RSAはなぜ安全？

RSAはここでかいてるように、

$ed \equiv 1\pmod {(p-1)(q-1)}$

となる $e$ の逆元 $d$ を求められると秘密鍵がバレちゃうのでした。

でユークリッド互除法で剰余環の逆元が効率よく求められるので、単に $(p-1)(q-1)$ を計算するための $p, q$ の値さえわかれば秘密鍵が得られます。(というか $p, q$ がわかっていたらそれは秘密鍵のissuerと知ってる情報同じなので簡単に発行できるのはそれはそう)

RSA自体の困難さは素因数分解の難しさに依拠してます。素因数分解が解かれると公開情報である $e, n$ からサクッと秘密鍵を生成されて通信の内容が全部バレます。

つまり素因数分解が難しいから難しいんや！

素因数分解の困難性

RSAは素因数分解の困難性に依拠していることがわかったので、素因数分解なんでそんなに難しいん？ということを軽く掘ります。(素因数分解アルゴリズムの紹介とかは別日で書くのでさわりだけ)

素因数分解にはいくつかありますが、いくつか紹介すると

入力された素数に好ましい条件を仮定したときにつかえるアルゴリズム
- p法
  - やることは単純。雑に説明する
  - てきとうにx, yをサイコロふってきめてそれをシードに乱数取る
  - $gcd(x-y, n)$ が見つかれば俺のかち！みたいなやつ
  - 素因数に小さい数が含まれてるとそこそこ早く見つかる
- p-1法
  - フェルマーの小定理をもちいた考え方
  - 適当なMをポンポンみつけてそれについて計算してみて見つかったらラッキー！みたいな脳筋なやつ
  - 原理はそう難しくないけど効率のいいMの探索の仕方がむずい
  - p-1が小さな素数の積だとうまくブンまわせる
- 楕円曲線法
  - フェルマーの小定理と楕円曲線の加法群の操作でうまいことやる
  - 詳しい内容はいずれ触れたい
  - 楕円曲線の概念は暗号とかでも出てくるしね
  - p-1法ではでかい素因数があるとMを大きくする必要があり探索コストがたかいけど、楕円曲線法はほかにいじれるパラメータがあるので素因数がそこそこ大きくてもいける
入力された素数の性質に依存しない汎用的なアルゴリズム
- 二次ふるい法
  - むずいのであまりよくわかっていない。いつかちゃんと勉強するぞ
- 数体ふるい法
  - もっとむずい。触りだけ論文とか読んでみたけど気合い入れて読まないとわけわからん
  - 一般には安全な素数に対してはこれが効率いいとされてる

数体ふるい法というアルゴリズムが入力された素数になにも前提を置かない場合は(現実的なアルゴリズムの中では)最も効率が良いとされています。またこのような効率よく素因数分解できない素数を安全素数とよんだりします。数体ふるい法は効率がよいとはいえ指数時間のアルゴリズムで十分な桁数 $n$ があれば事実上計算不可です。

量子計算機までに目をむければ、ジョアの素因数分解アルゴリズムが多項式時間で素因数分解が解けますが、量子コンピュータはまだ実用化に至っていないません。

そんなこんなでコンピュータの発展とともに計算機の処理能力は向上していくので、今使ってる暗号、今使ってる鍵長はいずれ安全でなくなるかもしれません。実際に短い鍵長の検証問題とかは解かれていってます。

計算能力の向上や未知の素因数分解アルゴリズムの発見などにより、長い鍵長のRSAでも危殆化(安全性が下がること)しますが、まあ安全素数の2048bit RSAなら現段階では大丈夫そうだよねと言われています

一方向性関数について

RSAでは巨大な素数 $p, q$ の積 $pq$ を求めることは簡単ですが、それを素因数分解するのは難しいです。

このように逆向きの計算が難しい処理のことを一方向性関数といいます。

また、RSAにおいては秘密鍵 $d$ を知っていれば逆向きの計算も簡単に行えます。

このように、条件を満たせば逆向きの計算が簡単に行える一方向性関数のことを落とし戸付き一方向性関数といいます。

暗号の安全性評価

さて素因数分解の困難性はわかったところで、暗号としてのRSAの安全性を評価していきましょう。

暗号の安全性の評価は

攻撃モデル(暗号への攻撃方法をモデル化したもの)
解読モデル(暗号文の解読パターンをモデル化したもの)

の2つで評価されます。

攻撃モデルの雑な紹介

ほかにもいくつかあるけど、今回は以下の3つだけ触れる

選択平文攻撃(CPA Chosen-plaintext attack) 任意の平文に対して暗号文が得られるよ！というモデル
選択暗号文攻撃(CCA Chosen-ciphertext attack) 攻撃対象以外の任意の暗号文に対して平文が得られるよ！というモデル
適応的選択暗号文攻撃(CCA2 Adaptive chosen-ciphertext attack) 攻撃対象以外の任意の暗号文に対して平文が得られるし、攻撃対象の暗号文もらってからも、攻撃対象以外だったら任意の暗号文を復号できる！というよくばりセットなモデル

下に行くほどより攻撃者に有利なモデルなので、下を弾けるほど安全

解読モデルの雑な紹介

だいたい以下の3つが言及される

一方向性(OW Onewayness) 暗号文から平文は求めることが難しいよ
識別不可能性(IND Indistinguishability) 2つの暗号文とその平文のペアが並べられたとき、どっちの平文がどっちの暗号文か判断できないよ。とくに情報がないからおみくじ引いて決めるのと同じだよ
頑強性(NM Non-Malleability) ある暗号文から改ざんした別の暗号文を作ることができないよ

下に行くほど守られる情報が多いので、下を守るほど安全

で、攻撃モデルと解読モデルの組み合わせで安全性は以下のように表現されます

OW-CPA 選択平文攻撃(CPA)に対して一方向性を満たす
IND-CPA 選択平文攻撃(CPA)に対して識別不可能性を満たす
NM-CPA 選択平文攻撃(CPA)に対して頑強性を満たす
OW-CCA1 選択暗号文攻撃(CCA1)に対して一方向性を満たす
IND-CCA1 選択暗号文攻撃(CCA1)に対して識別不可能性を満たす
NM-CCA1 選択暗号文攻撃(CCA1)に対して頑強性を満たす
OW-CCA2 適応選択暗号文攻撃(CCA2)に対して一方向性を満たす
IND-CCA2 適応選択暗号文攻撃(CCA2)に対して識別不可能性を満たす
NM-CCA2 適応選択暗号文攻撃(CCA2)に対して頑強性を満たす

で、一般にIND-CCA2とNM-CCA2は等価であり安全であるとされているので、そこまであれば使っても大丈夫だろうという感じです。現代的な暗号において安全であるとされる暗号はIND-CCA2を満たします

素のRSAの安全性評価

これをふまえてRSAを評価すると

素のRSAはOW-CPAを満たす
- 事前に平文から暗号文が得られても攻撃対象の暗号文から平文を得ることは難しい。そもそも公開鍵暗号なのでこれを満たしてなかったらガバガバである
素のRSAはIND-CPAを満たさない。暗号結果が決定的(同じ入力に対して毎回同じ)なので、平文を公開鍵を使って暗号化すれば100%どっちか判定できる
素のRSAはOW-CCA2を満たさない。手順は以下
- 攻撃対象のある暗号文 $c$ を得る
- 適当な $r$ を選んで $r^e c = r^e m^e = (rm)^e$ となる暗号文を得る
- ↑をdecrypt(CCA2は攻撃対象の暗号文を得たあとに任意の暗号文を復号することが可能)
- 復号結果は $rm$ なので $\frac {rm} r$ すれば直ちに平文mが得られる

ということで、素のRSAの安全性は OW-CPA に対して安全だぜ！となります。やつは四天王の中でも最弱...

なので安全なpaddingとか使わんとあぶないでよ！ということになってます。 padding指定したやつとその安全性については、それぞれのpadding解説にてやりたいのであとまわし！

素のRSAに適応選択暗号文攻撃(CCA2)ぶちかますぞ！

やっていくぞ！手順をおさらい

攻撃対象のある暗号文 $c = m^e$ を得る
適当な $r$ を選んで $r^e c = r^e m^e = (rm)^e$ となる暗号文を得る
↑をdecrypt(CCA2は攻撃対象の暗号文を得たあとに任意の暗号文を復号することが可能)
復号結果は $rm$ なので $\frac {rm} r$ すれば直ちに平文mが得られる

難しい話は特に無いっすね。見ればみるほどそうですねと言った感じ

サクッとコード書くとこんなかんじ

func main() {
    plaintext := "The magic words are squeamish ossifrage"
    fmt.Printf("plaintext: %s\n", plaintext)
    m := new(big.Int).SetBytes([]byte(plaintext))

    n, e, d := genKey()

    // 攻撃対象の暗号文を取得！plain RSA はこの暗号文に対応する平文はCCA2だとバレてしまうぞ
    c := new(big.Int).Exp(m, e, n)
    fmt.Printf("ciphertext: %v\n", c)

    // CCA2のための (rm)^e となる暗号文を生成。これは公開鍵の情報だけ知っていれば可能。rは適当でよい
    r := big.NewInt(5)
    c2 := new(big.Int).Mul(c, new(big.Int).Exp(r, e, n))

    // CCA2なので攻撃対象の暗号文を受け取ったあとに、攻撃対象以外の任意の暗号文の平文が取得可能
    m2 := new(big.Int).Exp(c2, d, n)

    // rm / r をすると平文がお出まし
    m, _ = new(big.Int).DivMod(m2, r, n)
    fmt.Printf("plaintext: %s\n", string(m.Bytes()))
}

go.dev

よっしゃボコボコにできたぞ！

まあこんな素人にも割れるくらいだと使い物にならないので、安全にするべくいろんな人が考えてPKCS#1 v1.5とかOEAPとかが産まれたので、良い子のみんなはそっちを使いましょう