情報セキュリティ 暗号学

【暗号まとめ】古典暗号・共通鍵暗号・公開鍵暗号・デジタル署名・ハッシュ関数・MACの各プロトコル紹介

暗号学

はじめに

この記事では、広く一般の暗号プロトコルについて簡単にまとめて紹介します。暗号について興味があるが、まずは全体像を掴みたいという方に最適な記事となっています。

コンテンツは以下です。

  • 古典暗号
  • 共通鍵暗号
  • 公開鍵暗号
  • デジタル署名
  • ハッシュ関数
  • メッセージ認証コード(MAC)

コンテンツは順不同ですので、興味のある箇所だけを読んでも理解できるようになっています。ただし、一部の専門用語は説明なしに使用することもあります。それでは、上から順に紹介していきます。

古典暗号

コンピュータが登場する以前の暗号を古典暗号と呼びます。古典暗号では、その仕組みが単純であることが多いため、アルゴリズムが非公開で使用されます。そのため、暗号化・復号化の仕組みそのものが秘密の情報となっている暗号と言えます。現代では暗号化の手法として用いられることは稀です。

シーザー暗号

ジュリアス・シーザーがガリア戦争の時に用いた暗号方式です。アルファベットを三文字ずらして置換するだけの単純な仕組みです。文字の頻度分析を行うことで簡単に対応関係を推測することができるため、非常に脆弱です。

コードブック

任意の単語をそれに対応した符号で置き換える仕組みの簡単な暗号です。対応表(コードブック)自体が秘密情報です。複雑なメッセージをやりとりする場合には、コードブックのサイズが大きくなってしまう欠点があります。

スタキュレー暗号

紀元前5世紀ごろにスパルタ人が使ったとされる暗号です。スタキュレーと呼ばれる棒に細長い羊皮紙を螺旋状に巻きつけて、平文を書きつけます。その後、羊皮紙のみを配布することで、意味不明な状態に見えます。復号は、暗号化に用いたスタキュレーと同じものに巻きつけることで実現できます。

転置式暗号

平文の文字の順番を入れ替える仕組みです。言葉遊びのアナグラムそのものです。入れ替えるルール自体が秘密情報になります。ただし、簡単な平文の場合は適切な入れ替えルールを知らなくても、試行錯誤することで復号できてしまいます。

単一換字式暗号

平文の文字を別の文字に置換する仕組みです。シーザー暗号もこの暗号方式の一つです。文字の出現頻度を分析する頻度分析に対して脆弱です。

多表式暗号

平文をブロックごとに区切った状態で、それぞれのブロックに異なる置換ルールを適用する仕組みです。単一換字式暗号と同じ原理で暗号化しますが、解読が難しくなっています。

エニグマ暗号

古典暗号の集大成とも言える暗号です。ドイツの技師であるアルトゥール・シェルビウスが発明しました。単一換字式暗号と多表式暗号を組み合わせることで頻度分析に対して耐性を持たせた機械式暗号です。ドイツ軍が第二次世界大戦で使用したことが有名です。計算機科学の祖であるアラン・チューリングにより機械を用いて解読されたことも有名です。
なお、アラン・チューリングに関してはこちらの記事で紹介をしています。


共通鍵暗号

共通鍵暗号は、暗号化と復号化に同じ鍵を使用します。この鍵のことを共通鍵や秘密鍵と呼びます。秘密鍵が流出してしまうと誰でも復号できてしまうので、メッセージの送受信者は安全な方法で秘密鍵を共有する必要があります。共通鍵暗号のメリットとして、高速に暗号化、復号化ができるため、比較的大きなサイズの平文をやりとりする場合に向いています。現代では、通信路の暗号化によく使用されています。

暗号化する平文の単位によってストリーム暗号とブロック暗号に大別されます。

ストリーム暗号

ストリーム暗号は平文をビットやバイトなどの小さい単位で順次処理を行っていく方法です。平文と秘密鍵との排他的論理和をとることで暗号化、復号化を行います。

バーナム暗号

ストリーム暗号の代表的な暗号化プロトコルです。平文と同じ大きさをもつ秘密鍵で排他的論理和を計算することで暗号化する仕組みです。非常にシンプルながら、情報理論的安全性をもつ解読不能の暗号です。総当たりで復号を試みても、真の平文を識別することができません。

ブロック暗号

ブロック暗号はブロックと呼ばれる一定の大きさに平文を区切って処理する暗号化方法です。暗号化時のブロックの区切り方と暗号化の方法により、いくつかの暗号化モードがあります。ブロック暗号の一つであるAESは現在でも通信時などに利用されている有名な暗号です。

DES(Data Encryption Standard)

米国国立標準技術研究所(NIST)が公表したブロック暗号です。IBMが開発したLuciferを元にして作られました。現在は脆弱性が見つかっているので、機密情報の暗号化に使用してはいけません。

トリプルDES

上述のDESを3回繰り返し適用する方式です。使用する鍵の個数に応じて、2鍵トリプルDESと3鍵トリプルDESがあります。現在でも致命的な脆弱性は見つかっていませんが、AESの方が安全かつ計算コストも安いため、使用は推奨されていません。

AES(Advanced Encryption Standard)

コンピュータの発展に伴い、DESでは解読されてしまう可能性が高くなったため、NISTが次の標準暗号として募集したものがAESです。コンペティションの結果、ラインダール暗号が選ばれました。現在の通信路の暗号化(TLS/SSL)によく用いられています。


公開鍵暗号

受信者の公開鍵で暗号化し、受信者の秘密鍵で復号する暗号方式です。公開鍵は第三者に公開して使用し、秘密鍵は自分自身で管理します。公開鍵暗号は、共通鍵暗号を用いた通信を実現する場合の課題であった、秘密鍵を事前共有しなければならない問題を解決するために、ディフィとヘルマンによって提案されました。現代のインターネットのように、不特定多数の相手と通信を行う場合に利用され、今では不可欠の暗号です。インターネットを介した通信では、公開鍵暗号によって共通鍵暗号の秘密鍵を配送し、共有された秘密鍵を用いてその後の通信を暗号化するのが一般的です。
秘密計算の手法の一つでもある準同型暗号は公開鍵暗号に含まれます。

DH鍵共有

ディフィとヘルマンによって提案された、共通鍵暗号に使用する秘密鍵を安全に共有する方法です。公開された情報のみでは、秘密鍵を推定することができません。共通鍵の配送方法の一つとして現在も使われています。

RSA暗号

最初に具体的な構成方法が公表された公開鍵暗号です。リベスト、シャミア、エーデルマンによって提案されました。大きな素数を法とした素因数分解問題の困難性を用いて実現しています。公開された情報から秘密鍵を推定するには大きな数字の素因数分解を行う必要があります。一般的に、多項式時間でこの問題を解くアルゴリズムはまだ見つかっていません。共通鍵の配送に現在も使われています。

ElGamal暗号

1984年にエルガマルによって提案された方法です。離散対数問題の困難性に基づいて実現されています。平文に対して乱数を混ぜてマスク処理を行っているため、より安全性が高まっています。しかし、暗号文は平文の2倍のサイズになってしまいます。また、乗法準同型性を持っているため、暗号文同士の乗算を行うことができます。

modified-ElGamal暗号(修正ElGamal暗号)

上記のElGamal暗号を修正して、加法準同型性を持つようにした暗号です。暗号文同士の和算を行うことができます。ただし、乗法準同型性は持ちません。

一般ElGamal暗号

一般化した離散対数問題の困難性に基づいて実現された暗号です。ElGamal暗号は乗法群を用いた方法でしたが、それを一般の有限群を用いて構築できるように拡張したものです。楕円曲線上の加法群に対応できます。

楕円ElGamal暗号(楕円曲線暗号)

楕円曲線上の加法群を用いて一般ElGamal暗号を構成した暗号です。楕円曲線上の離散対数問題の困難性に基づいて実現されています。一般的に離散対数問題よりも、楕円曲線上の離散対数問題の方が解くのが難しいと言われています。そのため、ElGamal暗号と比較してより少ない鍵長で同じ安全性を確保できます。また、計算時間も比較的小さくなります。

Rabin暗号

1979年にラビンが発表したRSAに似た暗号です。素因数分解の困難性に基づいて実現されています。暗号文を復号すると平文の候補が4つ出力されるため、どの文が元の文章であるかを決めるための工夫が別途必要です。

RSA-OAEP(Optimal Asymmetric Encryption Padding)

1994年にベラーレとロガウェイによって発表された、RSA暗号をさらに改良して安全性を高めたものです。適応的選択暗号文攻撃者に対して、不適切な暗号文の復号を行った場合にエラーメッセージを返す仕組みを持ちます。この仕組みにより、攻撃者は不適切な暗号文の復号結果から情報を得ることができなくなります。


デジタル署名

デジタル署名は、メッセージに暗号学的な署名を付与することで、現実世界での捺印と同じようなことを実現する仕組みです。文書と本人のもつ秘密鍵からデジタルな署名と検証鍵を生成し、検証者は検証鍵を用いて署名の検証をすることができます。

RSA署名

公開鍵暗号の一つであるRSA暗号を応用したデジタル署名です。最初に実装されたデジタル署名であり、仕組みが単純であるため脆弱です。RSA署名の性質として、秘密鍵を用いて生成された署名に対して、検証鍵を用いることで、元の平文が生成できます。これは、RSA署名がRSA暗号と対称性を持っているために見られる特別な性質です。

RSA-FDH署名

RSA-FDH署名(RSA-Full Domain Hash)はべラーレとロガウェイにより提案されたデジタル署名です。RSA署名にハッシュ関数を組み合わせて改良した方法です。RSA署名ではメッセージそのものに対して指数計算を行いますが、RSA-FDH署名ではメッセージのハッシュ値に対して指数計算を行います。ただし、ハッシュ値の値域がメッセージ空間と同じ大きさを持つ(Full Domain Hash)必要があるため、特殊なハッシュ関数を用いる必要性があり、効率が良いとは言えません。

ElGamal署名

ElGamalによって提案されたデジタル署名方式であり、ElGamal暗号とは別物です。離散対数問題の困難性に基づいています。既知の攻撃方法が複数存在しており脆弱であるため、そのまま使用することはほとんどありません。改良版であるDSA署名を使用することが推奨されています。また、一般化ElGamal署名に拡張することで、任意の巡回群に対応可能です。楕円曲線上に構築したElGamal署名を楕円ElGamal署名といいます。

DSA署名

DSA(Digital Signature Algorithm)署名はNISTによって提案された方法です。ElGamal署名をSchnorr署名の技法を用いて改良したものです。ElGamal署名よりも署名のサイズが小さくなっています。これは、署名生成に用いる計算空間(法)がより小さくなるように設計されているためです。メッセージのハッシュ値を生成する処理に、乱数を含めることで安全性を高めたもの(変形DSA署名)を使用することが推奨されています。

Schnorr署名

1991年にSchnorrが提案したデジタル署名で、離散対数問題の困難性に基づきます。「Schnorrの証明プロトコル」にハッシュ関数を組み合わせて構成されています。ランダムオラクル(ハッシュ関数が十分ランダムに振舞う)の存在を仮定すると、選択メッセージ攻撃に対して安全であることが証明されています。

ECDSA署名(楕円曲線DSA)

DSA署名を楕円曲線上で構築したデジタル署名で、楕円離散対数問題の困難性に基づいています。DSA署名などの有限体上で構築される仕組みよりも、楕円曲線上で構築される仕組みの方が、必要な鍵長を短くできることが大きなメリットです。現代のインターネット通信の暗号化に必要なデジタル証明書に使用されています。


ハッシュ関数

ハッシュ関数は、任意の入力を与えると入力の値に対応した固定長の値を出力する関数です。同一の入力には同一の出力を返し、大きなサイズの入力に対しても高速に計算できます。さらに、出力から入力を計算できない一方向性を持つことや、同じハッシュ値を出力しないような衝突困難性を持っています。主な活用例にデジタル署名や擬似乱数生成、データの改ざんチェックが挙げられます。他の暗号の構成要素として使用されることが多いです。

MD4/MD5

リベストにより提案された128bitのハッシュ値を出力するハッシュ関数です。既に衝突困難性が破られているため、別のハッシュ関数を使用することが推奨されています。

SHA-1/SHA-2

SHA(Secure Hash Algorithm)はNISTによって標準化されたハッシュアルゴリズムの総称です。SHA-1は160bitのハッシュ値を出力します。その後、SHA-2として4つのハッシュ関数(SHA-224、SHA-256、SHA-384、SHA-512)が標準化されています。それぞれの数字が出力bit数に対応しています。多様な場面で使用されています。

SHA-3/Keccak

SHA-1の安全性が脅かされたため、NISTが次世代のSHAを選定するために作られものがSHA-3です。コンペティション形式で選ばれたKeccakという手法が現在SHA-3として標準化されています。224bit、256bit、384bit、512bit、可変長のハッシュ値を出力できます。安全性の高いハッシュ関数として、広く使用されています。

RIPEMD-160

ヨーロッパのRIPEプロジェクトの一部として提案されたハッシュ関数です。 NISTとは対照的に学術コミュニティから生まれた技術です。オリジナルのRIPEMDは128bitのハッシュ値を出力し、RIPEMD-160は160bitのハッシュ値を出力します。


メッセージ認証コード(Message Authentication Code:MAC)

メッセージ認証コード(MAC)は、送信者が送ったメッセージの完全性を保証するための仕組みです。メッセージが通信路の途中で改ざんされていないことを受信者がチェックできるようになります。MACでは、事前に共通の秘密鍵を所持する必要があります。注意点として、MACはメッセージが改竄されていないことを保証しますが、メッセージの送信者が本人であることは保証しません。

CBC-MAC

ブロック暗号で用いられるCBCモードをベースにして作られた最も基本的なMACです。CBCモードは、メッセージを複数のブロックに分割して、各ブロックを暗号化し、その結果を用いて次のブロックの暗号化を行う、連鎖的な暗号文生成方法です。CBC-MACでは、最後のブロックの出力文を認証子とします。ただし、可変長のメッセージに対して脆弱性があります。

EMAC

EMAC(Encrypted MAC)はCBC-MACを改良したMACです。可変長のメッセージに対しても対応可能です。CBC-MACの最後の出力を別の鍵で暗号化することで実現されています。異なる二つの秘密鍵が必要になります。

CMAC

CMAC(Cipher-based MAC)はCBC-MACを改良したものです。上記のEMACと同様に、可変長のメッセージに対応しています。さらに、一つの秘密鍵のみを用いて認証子の生成を行うことができるため、EMACよりも鍵の管理コストを低減させることができます。CBC-MACの最後の処理に、秘密鍵依存の値を含める処理を行っています。

HMAC

HMAC(Hash function-based MAC)はハッシュ関数を2回使用するMACです。NISTにより米国標準として定められています。内部で使用されるハッシュ関数は、暗号学的に安全なものであれば何を使用しても良いため、ハッシュ関数の改良に簡単に対応できます。SSHやSSLプロトコルの内部で使用されています。

まとめ

以上が暗号プロトコルの簡単な紹介でした。

この記事では以下の内容を紹介しました。

  • 古典暗号
  • 共通鍵暗号
  • 公開鍵暗号
  • デジタル署名
  • ハッシュ関数
  • メッセージ認証コード(MAC)

参考文献

「現代暗号の誕生と発展 ポスト量子暗号・仮想通貨・新しい暗号」(岡本龍明、近代科学社、2019)

「クラウドを支えるこれからの暗号技術」(光成滋生、秀和システム、2015)

「暗号技術の全て」(IPUSIRON、翔泳社、2017)


メンバー募集

Acompanyでは、秘密計算の社会実装に向けてメンバーを絶賛募集中です!
優秀なメンバーが集まる環境で世の中に新しい価値を作る挑戦を僕らとしませんか?
以下の分野のメンバーを募集中です!

✅ MPCエンジニア
✅ マーケティング
✅ バックオフィス

興味がある方は、まずは軽くお話しするだけでも大丈夫ですので、ぜひご連絡ください!😎

話を聞きたい!

-情報セキュリティ, 暗号学
-, , , ,

© 2020 Blog | Acompany Co., Ltd