重要なデータを守るため、もう一度暗号化技術をおさらいしよう：クラウド時代の暗号化技術論（1）（2/2 ページ）

[光成滋生，＠IT]

RSA暗号と確率的アルゴリズム

　公開鍵暗号として有名な「RSA暗号」を紹介します。RSA暗号は1977年にロナルド・リベスト（Ronald Linn Rivest）、アディ・シャミア（Adi Shamir）、レオナルド・エーデルマン（Leonard Max Adleman）たちにより初めて公開鍵暗号を実現したものとして広く知られています。ただイギリスの通信電子セキュリティグループ（CESG）によると、1970代初頭にクリフォード・コックス（Clifford Cocks）たちが彼らよりも先に公開鍵暗号の概念やRSA暗号などを考えていたそうです。

【関連リンク】

A NOTE ON 'NON-SECRET ENCRYPTION' by C C Cocks（マサリク大学情報学部）

http://www.cesg.gov.uk/publications/Documents/nonsecret_encryption.pdf

　RSA暗号における鍵生成、暗号化、復号は下記のように行われます。

鍵生成

　各自が相異なる素数p、qを選んでn=pqとする。整数dとeでde - 1が(p - 1)(q - 1)で割り切れるような組を選ぶ。(n, e)が公開鍵でdが秘密鍵である。

暗号化

　平文mに対して

　　　　　Enc(m) = m^e mod n 　　　　　　　　　　　　　(1)

を暗号文とする。

復号

　暗号文c に対してDec(c) = c^d mod nで復号とする。

　ここで、x mod nはxをnで割った余りを表す記号です。

　適切にパラメータを選んでいる限り、公開されている情報n、e、cから元の平文mを求められないという仮定を「RSA仮定」といいます。RSA仮定は正しいと広く信じられています。

RSA暗号は場合によっては破れてしまう？

　よく紹介されるこの方式ですが、実は安全ではありません。

　例えばAさんがネットオークションに参加していて自分の落札額m = 10000を暗号化してc = m^e mod nをBさんに送信したとしましょう。CさんはAさんのネットワークを監視していて暗号文cを盗聴しました。

　商品から落札金額はそれほど大きな値ではないと推測できたとします。CさんはBさんの公開鍵K_Bを使ってm = 1000から1ずつ増やしながら、暗号文Enc(K_B,m) を作ります。するとm = 10000 のときにEnc(K_Bm) = cとなることが分かり、Aさんの落札額が判明してしまいます。

攻撃者

C = Enc(K_A, 10000)を取得

　Aの公開鍵K_Aを使って自分で暗号文を作る

　　C ≠ Enc(K_A, 1000)

　　C ≠ Enc(K_A, 1001)

　　...

　　C ≠ Enc(K_A, 9999)

　　C = Enc(K_A, 10000)←見つけた！

図2 暗号文cから元のmを解読する

　式（1）は平文mに対して常に同じ暗号文cができることを意味します。従って、平文の取り得る範囲が限定的なら破られてしまうのです。

　この状況は、パスワードのハッシュ値から元のパスワードを推測する辞書攻撃と同じ構図です。本来、ハッシュ関数のハッシュ値から元のパスワードを求めることは困難です。しかし、パスワードの取り得る範囲が限定されていれば、その集合を順にハッシュ関数に入れて同じ値になるのを探すのは難しくありません。

　これがもし「mは2000ビットの整数である」という情報しかなかったら、mを一つずつ増やして試す方法は時間がかかってしまい、終わらないでしょう。RSA仮定が正しい限り、mを現実的な時間で求める方法はありません。

　しかし、もしmを求められなかったとしてもオークションが終わってmが公開されると、Cさんはcがmを暗号化したものだと分かります。すると次回Aさんが同じmを暗号化してcを送信すれば、Cさんはその中身はmだと分かってしまいます。これはこれで問題です。

　攻撃者が自分の好きな平文を選び、対応する暗号文を取得することで攻撃する手法を「選択平文攻撃」（CPA：Chosen Plaintext Attack）といいます。公開鍵暗号の場合、誰もが公開鍵を使って暗号文を作ることができます。そのためCPAに対して安全でなければなりません。単に暗号文から平文に戻せないという性質だけでは駄目なのです。

　入力に対して常に同じ値が返るアルゴリズムを「決定的」といいます。それに対して、同じmを暗号化しても毎回異なる暗号文になるときを「確率的」といいます。もちろん異なるといっても復号すると同じmになる必要があります。公開鍵暗号の暗号化アルゴリズムEncは確率的でなければなりません。（単純な）RSA暗号は決定的なので安全ではないのです。

今回のまとめ：

• 情報セキュリティでは「機密性」と「完全性」と「可用性」を維持する必要がある。
• 選択平文攻撃（CPA）を受ける公開鍵暗号は確率的アルゴリズムでなければならない。
• （よく知られた単純な）RSA暗号は決定的アルゴリズムなので安全ではない。

「クラウド時代の暗号化技術論」バックナンバー

• まだまだ広く深い、暗号の世界――匿名認証や電子投票に利用される「ブラインド署名」「グループ署名」「ゼロ知識証明」
• マイナンバーの漏えい対策にも利用される「検索可能暗号」とは――安全性と利便性の両立を目指す注目の暗号技術
• 動画配信サービスにも応用できる暗号とは――アクセス権を制御する「属性ベース暗号」
• メールアドレスを公開鍵にする――「ペアリング」とその応用例
• クラウドサービスに最適な暗号方式とは？――暗号化したまま計算する「準同型暗号」
• 鍵が漏れることも想定せよ――クラウド時代における「楕円曲線暗号」の必然性
• “安全な暗号”とは何か――「強秘匿性」「頑強性」という概念
• 重要なデータを守るため、もう一度暗号化技術をおさらいしよう

光成滋生（みつなり　しげお）

サイボウズ・ラボ株式会社

サイボウズ・ラボ株式会社にてセキュリティとインフラ周りの研究開発に携わる。「数論アルゴリズムとその応用」研究部会（JANT）幹事。

• 2004年放送型暗号の実装でIPA未踏スーパークリエータ認定、
• 2005年ストリーム暗号Toyocryptの解読で情報化月間推進会議議長表彰、
• 2010年ベクトル分解問題についての論文で電子情報通信学会論文賞受賞。

近著に「応用数理ハンドブック」（朝倉書店、2013：楕円曲線暗号、ペアリング暗号の項目担当）、「クラウドを支えるこれからの暗号技術」（秀和システム、2015）がある。