公開鍵暗号方式

　公開鍵暗号方式は、公開鍵(Public key)と秘密鍵(Private key…共通鍵暗号方式の秘密鍵と区別するためにプライベート鍵と呼ばれることもある)という二つの鍵を使用する暗号方式で、秘密鍵から公開鍵を求めることはできても、公開鍵からは秘密鍵を求めることはできないという性質を持っています。
　更に、公開鍵で暗号化したデータは秘密鍵でしか解読することができず、逆に秘密鍵で暗号化したデータは公開鍵でしか復号できないという性質を持っています。
　共通鍵暗号方式は通信する両者で共通の一つの鍵を持ちましたが、公開鍵暗号方式では、二人が通信する場合はお互いに一セットづつの鍵(合計4つ)が必要となります。それぞれ自分の秘密鍵は他人に知られないように秘密に保管しますが、公開鍵は通信する相手に教えてあげます。通信相手は公開鍵でデータを暗号化し、本人に渡します。データは秘密鍵でしか解読できず、秘密鍵を持っているのは本人だけなので、他人に知られることなくデータを渡すことができます。
　公開鍵暗号方式は、共通鍵暗号方式に比べて以下のメリットがあります。

• 事前に秘密に鍵を交換する必要がない
  　共通鍵暗号方式では、通信を行う両者が同じ鍵を持っている必要があります。この鍵をどうやって共有するかが共通鍵暗号方式では問題でした。公開鍵暗号方式では、通信するときに公開鍵を相手に渡すだけで済みます。
• 鍵の個数が少なくてすむ
  　たとえば100人が相互に通信する場合、共通鍵暗号方式では全体で(100×99÷2)個(=4950個)の鍵が必要になります。ところが、公開鍵暗号方式では(公開鍵と秘密鍵で2個と数えるとしても)200個の鍵があれば大丈夫です。また、共通鍵暗号方式では各人が99個の鍵を秘密に持たないといけないのに比べ、公開鍵暗号方式では自分の秘密鍵だけを秘密に持っていれば済みます。

公開鍵いろいろ

• RSA
  　現在もっとも有名で実際に使用されている公開鍵暗号ということができるでしょう。RSAという名前は発明した3人の数学者の頭文字から取られたもので、それぞれRibest氏、Shamir氏、Adleman氏です。
  　この公開鍵暗号方式は大きな数字の素因数分解が非常に困難であるということをその根拠としています。
• E-SIGN
  　NTTが開発した暗号方式です。RSAと同様に素因数分解の困難性を根拠としています。RSAよりも処理が高速であることが特長です。正当性の評価に不等式を用いるため、鍵の交換には使用することができず、署名のみに使用することになります。
  　詳しい数式については私も良く分からないのですが、その数式の中のkという値が小さいものについては破られたとの報告がされているため、E-SIGNを使用する場合はkの値を大きくする必要があります。
• 楕円暗号
  　楕円曲線が持つ特性をうまく利用した暗号方式です。最初に発明された方式は破られましたが、その後も改良され続け、RSAの代替と成りうるか注目されています。RSA方式に比較して、同等の暗号強度を実現するのに鍵の長さが短くてすむという利点があります。そのため、一般に処理が高速になります。
• ElGamal
• Diffie-Helman
• Knapsack暗号
• DSA(Digital Signature Algorithm)
  　DSS(Digital Signature Standard)とも。米国の政府関係における電子署名の標準方式で、これから広く使われていく可能性があります。政府系ではハッシュにSHA-1、署名にDSAというのが基本的な署名アルゴリズムになります。