RSA暗号
『暗号技術のすべて』の第4章を参考にしました。 初めての具体的な公開鍵暗号であるRSA暗号について書いていきます。
RSA暗号とは
数学的基礎知識
- GCD(x,y)：xとyの最大公約数（GCD(x,y)=1のとき、xとyは互いに素である）
mod：モジュロ演算 → a=b mod m：aとbは法mで合同
法mとは、mで割った余りのこと。
（例）法7のもとでは、3と10は合同（3÷7=0...3，10÷7=1...3）
- フェルマーの小定理
- 中国人剰余定理
アルゴリズム
鍵生成、暗号化、復号の3つのアルゴリズムに分けられます。
鍵生成アルゴリズム
入力：k，出力：公開鍵pk，秘密鍵sk
- kビットの素数p, qをランダムで生成する。 ここで、p, ｑは十分大きな素数でなければならない（pqが簡単に素因数分解されない）。
- N = pqを計算し，φ(N) = (p - 1)(q - 1)とする。
- GCD(φ(N), e) = 1となるようなe（1 < e < φ(N)）をランダムに選ぶ。
- ed = 1 mod φ(N)を満たすようなd(> 0)を計算する。
- pk=(N, e)，sk=dとして出力する。
暗号化アルゴリズム
入力：平文m, pk、出力：暗号文c
c=me mod N
を計算し、出力する。
復号アルゴリズム
入力：暗号文c, pk, sk、出力：平文m
m=cd mod N
を計算し、出力する。
正当性の検証
ed = 1 mod φ(N)（鍵生成アルゴリズムステップ4）より、 ある整数k(≧ 0)に対してed = kφ(N) + 1となる。よって、m'は以下のように展開できる。
m' = cd = (me)d = med = mkφ(N)+1 = mkφ(N)・m
ここでmとNが互いに素かどうかで場合分けする。
(1) GCD(m,N) = 1のとき
オイラーの定理より、次のように変形できる。
m' = mkφ(N)・m = 1k・m = m mod N
(2) GCD(m,N) ≠ 1のとき
N = pqより、GCD(m, N) = p or qとなる。
(i) GCD(m,N) = pのとき
法Nではなく、法p, qで考え、出力をa, bとする。 mはpの倍数であるため、a = 0となる。 また、qは素数かつGCD(m,q)=1（互いに素）より、フェルマーの小定理を用いてb = mとなる。
a = m' = med = 0ed = 0 modｐ
b = m' = med = mk(p-1)(q-1)+1 = m・(mq-1)k(p-1) = m・1k(p-1) = m mod q
中国人剰余定理より、px+qy=1となるx, yを用いて、m'は以下のように計算できる。
m' = aqy + bpx mod pq
= 0・py + m・px mod N
= mpx mod N
= m(1 - py) mod N
= m - mpy mod N
= m mod N（mはpの倍数なので、mqはNの倍数）
(ii) GCD(m,N) = qのとき
(i)と同様に算出できる。
正当性の検証のまとめ
(1), (2)より、m'= m mod Nとなるので、正当性が成り立つ。
RSA暗号の安全性
RSA暗号は、「公開鍵がわかっても、秘密鍵を求めることが困難である」ことを安全性の根拠としています（公開情報から秘密の情報が漏洩したらダメですよね）。素因数分解は困難であるので、Nを知っていても効率的にp, qを求めることは出来ません。したがって、(p - 1)(q - 1)も効率的に求めることが出来ないので、秘密鍵dも効率的に求めることが出来ません。
RSA問題、RSA仮定とは
素因数分解問題とRSA問題
[問題]
素因数分解問題が解けると、RSA問題が効率的に解けてしまうことを証明せよ。
[証明]
整数Nを素因数分解するアルゴリズムAが存在したと仮定します。 つまり、アルゴリズムAとは、入力がNに対して、出力がp, qとなるブラックボックスのアルゴリズムです。
このAを用いて、RSA問題を解くアルゴリズムBを構成できれば、問題の関係性を証明できたことになります。アルゴリズムBは、入力p, qから鍵生成アルゴリズムと同様にdを計算できます。dが計算できたので、cd mod Nより、mを求めることが出来ました。
よって、素因数分解問題が解ければ、RSA問題が解けることがわかりました。一方、RSA問題が解けても、素因数分解問題が解けるかはわかっていないので，RSA仮定は、「素因数分解問題が困難」という仮定よりも強いことになります。
[結論]
感想
参考文献にはこのような記述があります。
実は、「素因数分解が難しい」ならば「ＲＳＡ暗号の解読も難しい」という関係には完全な証明がされているわけではありません。真正面からＲＳＡ暗号を解読しようとすれば素因数分解を行う必要があり、それが「素因数分解が難しければＲＳＡ暗号の解読も難しいだろう」という根拠になっているだけなのです。つまり、現在のところ素因数分解は困難ですが、その素因数分解をせずにＲＳＡ暗号を解読できる抜け道が、もしかしたら存在するかもしれないのです。
こういう未知なものにロマンを感じざるを得ない...
参考文献
公開鍵暗号
『暗号技術のすべて』の第4章を参考にしました。 この章は、公開鍵暗号について書かれています。
公開鍵暗号とは
これまでに紹介したDESやAESのような共通鍵暗号は、事前に送受信者間で共通鍵を共有しなければならないという問題がありました。こうした問題を解決する手法として提案されたのが、公開鍵暗号です。
公開鍵暗号は、通信相手の公開鍵で暗号化し、自身の秘密鍵で復号する暗号です。その名の通り、公開鍵とは公開されているので誰でも参照できます。送信者は、相手の公開鍵で平文を暗号化し、暗号文を生成します。秘密鍵は、秘密に管理されるべき鍵のことで、自身に暗号文が送られてきたら、秘密鍵を使って復号します。
このような仕組みにより鍵の共有をすることなく、Bobから送られてくるメッセージは、Aliceしか復号できないということになります。
公開鍵暗号の安全性指標
公開鍵暗号の安全性レベルは攻撃モデルと解読モデルの組み合わせで決定されます。 例えば、解読モデルが一方向性、攻撃モデルが選択平文攻撃であるとき、OW-CPA安全といいます。
攻撃モデル
選択平文攻撃（CPA）
あらかじめ選択した平文と、それに対応した暗号文を利用した攻撃。
選択暗号文攻撃（CCA）
あらかじめ選択した暗号文と、それに対応した平文を利用した攻撃。一度のみ復号オラクルにアクセスできる。
適応的選択暗号文攻撃（CCA2）
あらかじめ選択した暗号文と、それに対応した平文を利用した攻撃。いつでも復号オラクルにアクセスできる。
解読モデル
一方向性（OW）
秘密鍵を用いずに復号することは困難であること。
識別不可能性（IND）
2つの平文m0、m1のどちらかの暗号文cが与えられたとき、その暗号文がどちらの平文を暗号化したものかを識別することが不可能であること。
公開鍵に対する攻撃
公開鍵のすり替え
公開鍵が正しいか（本当に通信相手のものかどうか）をどのように保証するのかという問題があります。この問題を解決する手段として、公開鍵基盤（PKI）というものがあります。インターネット上に存在する認証局と呼ばれる機関にユーザーと公開鍵の関係を保証する証明書を発行してもらい、公開鍵を使用するユーザーは、これを参照することで、公開鍵の正当性を検証することができます。
全数探索攻撃
公開鍵暗号の秘密鍵に対して、全数探索攻撃を行ったとします。鍵長がkビットであったとしても、実際に使われている鍵は2k個よりはるかに少ないです。それは、鍵の仕様が定められているからです。 このことから、全数探索攻撃において、共通鍵暗号と公開鍵暗号の鍵長が同じであった場合、公開鍵暗号の方が検査すべき計算回数が少なくて済みます。
公開鍵暗号の具体例
まとめ
米国国家基準暗号 - DESとAES
『暗号技術のすべて』第3章を参考にしました。 共通鍵暗号のDESやAESについての章ですが、アルゴリズムは様々なサイトで詳細な説明がされているので、私が興味を持ったことのみ書いていきます。
DES
- Data Ecryption Standard（データ暗号化標準）の略
- 米国の旧国家標準のブロック暗号（Feistel構造）
- ブロック長64ビット、鍵長64ビット（実質56ビット）
実質56ビットの理由
56ビットの鍵を7ビットずつ8つに分け、それぞれにパリティビット（誤り検出符号）を付け、64ビットとしている。このことから、当時のインターネット通信では、誤りが起こりやすい不完全な環境だったことが予想される。現在では、誤り検出の機能は、暗号方式ではなくインターネットが担っているため、後続のAESには、パリティビットは付けられていない。
DESの弱点
DESには、構造上の弱点（ビット数が少ない、弱鍵等）が多々あります。DESの解読手法の中の線形解読法という方法は、1993年に三菱電機の松井充氏によって発明された解読法です。
なんと、日本人によって、DESが解読可能であることが示されたのです！
このことがきっかけで、米国国立標準技術研究所（NIST）はAESを公募することになりました。
AES
- Advanced Encryption Standard（高度暗号化標準）の略
- 米国の新国家基準のブロック暗号（SPN構造）
- DESの安全性が懸念されたため、2001年に採用
- ブロック長128ビット、鍵長128、196、256ビット
DESとの比較
- SPN構造を用いていることにより、ラウンド数が少なく、並列処理に向いている。
- AESは、鍵長によって3つのタイプに分類されるが、どれもDESよりも長いので、安全性が高い。
- DESの設計にはNSA（米国国家安全保障局）が深く関わっており、NSAの都合の良い要件が仕様に組み込まれているのではないかという疑惑があったが、AESはコンペティションによって、選定された。
ブロック暗号の安全性
- ブロック暗号の安全性を確実に保証する理論的な手法は存在しない。
- 現時点で知られている攻撃に対して、耐性を持つかでしか判断できない。
- 将来的に新しい攻撃手法が提案されると安全性が破られる可能性もある。
- セキュリティマージン
- 未知の攻撃手法に対してブロック暗号がどの程度の耐性を持つかを評価する概念
まとめ
- 共通鍵暗号方式：暗号化と復号に共通の鍵を用いる
- ブロック暗号：共通鍵暗号方式の暗号化アルゴリズムのうち、平文をある一定のまとまり（ブロック）ごとに暗号化するもの
- DES：旧米国国家基準のブロック暗号
- AES：新米国国家基準のブロック暗号
感想
こちらのサイトに記載されてあるように、2023年には3DES（DESを三層に拡張した暗号）の使用が禁止される。これまでDESで暗号化されていたものがAESに置き換わっているのかとても気になる。
最強の暗号？バーナム暗号
バーナム暗号とは
アルゴリズム
バーナム暗号の暗号化、復号には、排他的論理和という演算が用いられています。
排他的論理和
排他的論理和とは、ビット演算といわれる0と1だけの世界での演算です。演算子は⊕と表されます。
| a | b | a⊕b |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
例えば、a=1010 1010、b=1111 0000とすると、以下のようにa⊕bが計算されます。
暗号化と復号
平文をm、暗号文をc、秘密鍵をkとします。
暗号化は以下のように定義されます。
c = m ⊕ k
また、復号は以下のように定義されます。
m = c ⊕ k
例
m = ”hello"、k = aa bb cc dd ee（16進数）として、暗号化、復号をします。
自然言語（普段使っている日本語や英語）をそのままビット演算することは出来ません。そこで、ASCIIコードと呼ばれる文字データを2進数に変換する対応表を用いて変換します。
平文をASCIIコードによって、16進数に変換
m' = 68 65 6c 6c 6f
m'とkで排他的論理和を演算
c = m' ⊕ k = c2 de a0 b1 81
暗号文cを送信
暗号文cを受信
cとkで排他的論理和を演算
m' = c ⊕ k = 68 65 6c 6c 6f
m'をASCIIコードによって、変換
m = "hello"
1~3まではメッセージの送信側が、4~6まではメッセージの受信側が行う操作です。このようにして、暗号化した文章を送ることが出来ます。鍵であるk（aa bb cc dd ee）は、予め送信側と受信側で共有されている情報で、平文と同じ長さである（同じ長さに加工する）必要があります。
バーナム暗号の安全性
バーナム暗号は、解読不可能である。
→「探索すべき鍵数が多くて現実的に解読できない」
→「すべての鍵候補の計算が可能である無限の能力を持つ攻撃者であっても、解読できない」
攻撃者は、暗号文を入手したと仮定します。攻撃者は、その暗号文と同じ長さの候補鍵を用意し、総当たりで暗号文と候補鍵との排他的論理和を取り、復号します。このとき、平文と一致しますが、攻撃者にとってそれが正しい平文であるかは判断が付きません。
よって、バーナム暗号の場合、平文・暗号文・鍵という3つの情報のうち2つの情報が特定できなければ、残りの1つは特定できないということです。
バーナム暗号の死角
バーナム暗号は、最高の安全性を持ちますが、様々な課題があるため限定的な場面でしか使用されていません。
鍵の配送
バーナム暗号の秘密鍵は、平文と同じ長さ以上である必要があります。この鍵を安全に配送できるのであれば、わざわざ平文を暗号化せずともそのまま配送できます。
鍵の同期
暗号文の送信中に1ビットでも欠けてしまうと、それ以降の復号が正しく行われないため、送信側と受信側で完全に同期していなければなりません。
鍵の生成
バーナム暗号の秘密鍵はランダムなビット列でなければなりません（上の例では簡略化のためにランダムなビット列にしませんでしたが、これは悪い秘密鍵です）。つまり、長い秘密鍵を作るにはとても手間がかかります。
まとめ
バーナム暗号は、安全性は最強だが、効率性と利便性に欠けているので、あまり使用されていない。
共通鍵暗号まとめ
『暗号技術のすべて』の第3章を参考にしました。
古典暗号では、利用シーンが軍事や外交に限られていました。しかし、コンピュータやインターネットが発達した現代では、様々なシーンにおいて、顔を知らない相手とやり取りする必要があります。また、ディジタルデータは、インターネットを通じて即時的にやりとりをすることが可能です。つまり、現代においては、民間企業や個人も暗号を利用しなければなりません。
共通鍵暗号とは
暗号化と復号を同一の秘密鍵によって行う暗号
正当性：暗号文を復号すると元の平文に戻る
→ ちゃんと暗号化、復号できる
秘匿性：暗号文から平文に関する情報を得られないこと
→ 他の人には見られない
共通鍵暗号の安全性指標
攻撃モデルを設定し、その仮定下で解読されるかを議論する
オラクル
暗号理論の世界でよく登場する言葉の中にオラクルという言葉があります。『暗号技術のすべて』では、以下のように説明されてます。
オラクルとは、要求に応じて、データを返してくれる仮想的な存在のことです。例えば、関数fを実現するオラクルであれば、質問xをオラクルに送信するとf(x)を返してくれます。
なるほど、わからん…
例えば、平文に対する暗号文を入手するには、秘密鍵とその暗号化アルゴリズムを知る必要があります。しかし、暗号化オラクルにアクセスすることが可能であれば、平文をオラクルに送信するとそれに対する暗号文が返ってきます。つまり、暗号文を得るために秘密鍵やアルゴリズムを知る必要がないということです。現実世界でいうと、暗号化装置を入手することなどに相当します。
5つの攻撃モデル
暗号文単独攻撃（COA）
盗聴などによって得た暗号文を利用した攻撃
既知平文攻撃（KPA）
過去の解析などによって得た平文と暗号文のペアを利用した攻撃
選択平文攻撃（CPA）
任意のタイミングで、任意の平文に対する暗号文を入手できる（暗号化オラクルにアクセスできる）状況下での攻撃
選択暗号文攻撃（CCA）
解読対象の暗号文を入手する前に、任意の暗号文に対する平文を入手できる（復号オラクルにアクセスできる）状況下での攻撃
適応的選択暗号文攻撃（CCA2）
任意のタイミングで、任意の暗号文に対する平文を入手できる（復号オラクルにアクセスできる）状況下での攻撃
攻撃モデルの強弱
- 共通鍵暗号の場合、CPAは誰でもできるわけではない（暗号化オラクルにアクセスできる状況なんて現実的にありえない）ので平文と暗号文は、それぞれ分けて考える
- 下に行くほど強力（解読する力が強い）な攻撃モデル
- 例えば、「この暗号は、CCAを満たす」という言葉の意味は、「CCAされても解読されない暗号であると同時にCCAよりも弱い攻撃モデルであるCPAも満たす」ということである。
（暗号化オラクルと復号オラクルにアクセスできても対象の暗号文を平文に戻すことが出来ないって最強過ぎないか...）
共通鍵暗号は安全 ≠ 解読できない
秘密鍵がkビットの場合、秘密鍵の候補は2k個あります。よって、2k回探索すれば必ず秘密鍵を特定することが出来ます。このような攻撃を鍵全数探索攻撃といいます。共通鍵暗号では、「鍵全数探索攻撃よりも効率的な秘密鍵を求めるアルゴリズムは存在しない」という条件が求められます。 つまり、共通鍵暗号が安全ということは、秘密鍵を求めるのに鍵全数探索攻撃よりも効率的なアルゴリズムは存在しないということであり、解読できないということではないのです。
共通鍵暗号の分類
- ストリーム暗号：平文を小さい単位で逐次的に暗号化
- ブロック暗号：平文を一定の大きさのブロックごとに暗号化
- Feistel構造（DESに用いられる）
- SPN構造（AESに用いられる）
まとめ
『暗号技術のすべて』には、このような記述があります。
共通鍵暗号のアルゴリズムは、古典暗号のアルゴリズムに非常によく似ています。特に、暗号化アルゴリズムと復号アルゴリズムの入出力は同一です。
この記述の意図することは、「平文と秘密鍵 → 暗号文」や「暗号文と秘密鍵 → 平文」のような入出力に着目すると、現代暗号の一種である共通鍵暗号は、古典暗号をモチーフにしているということです。以前の記事で紹介したシーザー暗号も共通鍵（＝3文字ずらすという共通の情報）を利用した暗号といえるでしょう。
次回以降で、バーナム暗号やDES、AESについて触れていきたいと思ってます！！
難攻不落の暗号 - エニグマ
個人的に、暗号＝エニグマという印象が強かったので、今回はエニグマについて調べていきます。
エニグマとは
アルゴリズム
暗号化と復号はこのような同一なアルゴリズムである。
- 平文（暗号文）を入力
- 内部の3つのローターが異なる文字を出力
- 反転ローターによって逆方向に送信
- 再び3つのローターを経由
- ランプボード上で暗号文（平文）が点灯
- 最初のローターが1目盛り分回転
このような処理により、1文字が暗号化（復号）され、これを繰り返すことで全体を変換することができる。
また、手順6によって、同じ文字を連続で入力しても前回と同じ出力にならないようになっている。
強力なのに簡単に使える暗号
ローター1が26目盛り回転すると、2番目のローターも1目盛り分回転する。同様に、ローター2が26目盛り回転するとローター3が1目盛り分回転する。この結果、同じローターの組み合わせとなるために17,576（=26 ^3)種類存在することになる。
このような複雑な仕組みであるにも関わらず、3つのローターの配置と順序、プラグの配置だけ知っていれば暗号化して通信を行うことができる。しかし、この組み合わせ数は、159,000,000,000,000,000,000（1垓5900京）通りあるので、解読に要する時間が膨大にかかってしまう。エニグマの鍵は日替わりで変更されていたため、解読に1日以上かかってしまっては意味がないのである。
天才数学者チューリング
コンピュータの概念を初めて理論化したことで有名なイギリスの数学者アラン・チューリングによって、エニグマは解読された。エニグマが解読されたことで、第二次世界大戦は連合国軍の勝利となった。
まとめ
- 機械式暗号エニグマは、機械さえ入手できれば誰でも暗号化できる
- アルゴリズムは公開
- ローター（暗号円盤）による多表式暗号
- エニグマは古典暗号の一種
- 古典暗号なのにアルゴリズムが公開されている
- 組み合わせ数が膨大だから
- 天才数学者アラン．チューリングによって解読される
雑談
現在、話題となっている仮想通貨の中にもエニグマというものがあります。
とてもおもしろい技術なので、興味のある方はこちら のサイトを参考にすると良いと思います。
参考
古典暗号まとめ
『暗号技術のすべて』という本の第2章を参考にしました。
古典暗号とは
- 暗号
- 古典暗号
- 現代暗号
- 『暗号技術のすべて』においては...
- コンピュータ誕生以前の暗号 → 古典暗号
- それ以降の暗号 → 現代暗号
古典暗号の種類
- ヒエログラフ
- シーザー暗号
- コード
- スキュタレー暗号
- 転置式暗号
- 単一換字式暗号
- 多表式暗号
古典暗号アルゴリズムの特徴
- アルゴリズム（平文を暗号化する方法）は、暗号を使用しない人には非公開
- コンピュータを使うと簡単に解読（暗号文から平文を見つけること）できる
（例）前々回の記事で紹介したシーザー暗号は、鍵である3という情報を知らなくてもアルゴリズムを知ってさえすれば、鍵を知らなくても簡単に解読できる（アルファベットは26種類なので、25回試行すれば平文を見つけることが可能）
古典アルゴリズムの使用例
主に、軍事や外交（「重要な情報を送り手と受け手以外の人間に分からないよう伝える」が必要な場面）で使用
まとめ
古典暗号は、現代においては簡単に解読されてしまうが、現代暗号の基礎となっている。 今後は、現代暗号について書いていこうと思います。
