公開鍵暗号方式の仕組みを分かりやすく解説

公開鍵暗号方式は、暗号化して通信を行うために現代には欠かせない技術です。
本記事では、公開鍵方式についての概要や説明を対となる共通鍵暗号方式と合わせて、画像付きで紹介します。
IPA(独立行政法人情報処理推進機構)主催の情報処理技術者試験でもよく問われるので、学習や復習にも活用ください。

はじめに

公開鍵暗号方式は、コンピュータ間の通信を暗号化するための方式の1つです。
「非対称暗号（Asymmetric Encryption）」とも呼ばれます。名前の通り、暗号化と復号化に異なる鍵が使われます。

公開鍵暗号を用いる主なプロトコル

代表として、以下のようなプロトコルがあります。有名どころのプロトコルにはほとんど使われています。
ただし、実際は公開鍵暗号だけを利用したプロトコルはほんの一部のみで、共通鍵暗号も利用するハイブリッド方式のものがほとんどです。

TLS(Transport Layer Security)

TLSは、インターネット上で安全な通信を行うために使用される暗号プロトコルです。
TLSは公開鍵暗号を使用して、クライアントとサーバーの間に安全なチャネルを確立し、サーバーを認証するために使用されます。
共通鍵暗号方式(対象暗号)も利用するので、正確にはハイブリッド方式です。

SSH(Secure SHell)

SSHは、サーバーやその他のネットワークデバイスへの安全なリモートアクセスを提供するために使用されるネットワークプロトコルです。
SSHは、認証に公開鍵暗号を使用し、クライアントとサーバー間の安全なチャネルを確立するために使用されます。
こちらも共通鍵暗号方式(対象暗号)も利用するので正確にはハイブリッド方式です。

公開鍵暗号方式が誕生した理由

公開鍵暗号方式が登場するまで利用されていたものは、「共通鍵暗号方式(対称暗号方式)」と呼ばれます。公開鍵暗号方式は、共通鍵暗号方式の問題点を解決するために作られました。

共通鍵暗号方式(対象暗号方式)の問題点

鍵を盗まれる可能性がある

共通鍵暗号方式は、データの暗号化と復号化に1つの同じ鍵(共通鍵)を利用する方式です。

送信者も受信者は共通鍵を利用しますが、その共通鍵を用いて通信を行う前に、どちらもが共通鍵を保有している必要があります。
鍵を渡すために、その鍵で暗号化してはだめなので、共通鍵を渡す際通信を利用する場合は、通信を傍受されてはいけません(物理的に渡すか閉じられたネットワークで渡すなど)。
このように共通鍵暗号方式の場合、どうにかして傍受されない状態で共通鍵を相手に渡す必要があり、相手がインターネット上だと物理的に渡すのはほぼ不可能です。

他にも、以下のような問題点があります。

鍵を配布する必要がある

送信側と受信側で同じ鍵が必要なので、通信を行うために配布する必要があります。
鍵を管理するユーザが増えれば増えるほど、指数関数的に管理が必要な鍵が増えます。
これは大規模になればなるほど大きな負担になります。

※公開鍵方式を使うという前提で、共通鍵を作成し、安全に渡す方式(共通鍵共有)は存在します。

公開鍵暗号方式の仕組み

公開鍵暗号方式でも鍵を使って送りたいデータを暗号化または復号化しますが、鍵の種類として、公開鍵と秘密鍵という2つの鍵を用います。

公開鍵について

公開鍵は文字通り公開されている鍵で、誰でも自由に知ることができます。
公開鍵は、データを送信する際に用いられます。

秘密鍵について

秘密鍵は、データの受信者だけが持っているもので、意図した受信者だけが持つものです。
秘密鍵は、受信したデータを復号する際に用いられます。

データを送信する際は、送信者が公開鍵を用いてデータを暗号化して、受信者に送信します。
受信者は、受信したデータを秘密鍵で復号化し、データを取り出します。

公開鍵と秘密鍵の関係

初めにデータを受信したい側は、秘密鍵を作成します。
秘密鍵は適当に作られるわけではなく、数学的な処理が行われたうえで、作成されます。
次に公開鍵を作成しますが、公開鍵も適当に作られるわけではなく、また、秘密鍵を基にして数学的に処理したのちに作られます。
作成された公開鍵は自由に共有されます。

公開鍵と秘密鍵の数学的な話

公開鍵と秘密鍵には数学的な関係があると上記で説明しました。代表として以下のような様々な数学的理論を利用して作られています。
他にも様々な数学的な理論に基づいた方式があり、それぞれにメリット・デメリットが存在します。

RSA暗号

非常に大きな整数を因数分解するのは難しいという原理に基づいて作られた公開鍵暗号システムです。
RSAという名称は発明者の名前にちなんで命名されています(Ron Rivest、Adi Shamir、Leonard Adleman)。
今回の記事は、特段記載のない限りはすべてこのRSA暗号方式での公開鍵暗号方式についての記事です。

楕円曲線暗号(ECC)

楕円曲線の数学に基づいた、比較的新しい公開鍵暗号システムです。
RSAと同レベルのセキュリティを提供しますが、鍵長が短く、計算時間が速いため、スマートフォンやIoT機器などリソースに制約のあるデバイスでよく使われています。

Digital Signature Algorithm(DSA)

デジタル署名に使用される公開鍵暗号システムです。
ソフトウェアの配布や金融取引など、デジタル署名の検証が必要なアプリケーションで広く使用されています。

ElGamal Encryption(エルガマル暗号)

暗号化に使用される公開鍵暗号システムです。
有限体における離散対数問題の解法の難しさに基づき、安全な電子メールやファイル共有などのアプリケーションで一般的に使用されています。

公開鍵から秘密鍵の解読について

公開鍵と秘密鍵には数学的な関係があるということで、公開鍵から秘密鍵が分かるのではないかと思う方もいると思います。
というか筆者は、初めて公開鍵方式の話を見たとき、データを送信する際、公開鍵を利用するなら、復号化する際も公開鍵を使えばいいのではと思いました。
ですが、暗号化されたデータは公開鍵からは復号することが極めて困難になるように設計されています。このような仕組みを一方向性関数と呼びます。
※解読が可能か不可能かでいうと可能です。ただし、解読するのに膨大な計算と時間がかかるというのが正しいです(適切な鍵を選択していれば)。

公開鍵暗号方式の機密性

公開鍵暗号方式で暗号化されたデータは、秘密鍵以外では復号することができません。
従って、暗号化されたデータを第三者が不正にアクセスや閲覧して入手したとしても、(秘密鍵を持っていない限りは)データを復元することができません。
このように暗号化によって不正なアクセスや閲覧からデータを保護できることを機密性が確保されている状態といいます。

電子(デジタル)署名

公開鍵暗号方式は、データを安全に送受信すること以外に、「データ送信者が本当に意図した人(サーバ)である」という確認と「自分のところに来るまでに送信されたデータが改ざんされていない」という確認にも使えます。
電子(デジタル)署名は、公開鍵暗号方式を利用して「データ送信者が意図した人(サーバ)である」「受信データ送信データと同一(改ざんされていない)」という2つを証明するためのものです。
データを暗号復号化する際は、データを公開鍵で暗号化し、秘密鍵で復号化してデータを取り出すというものでした。
デジタル署名は先ほどの説明とは逆に、秘密鍵で暗号化し、公開鍵で復号化します。
また、データ暗号化復号化時とデジタル署名時では、データ送信者と受信者が逆になっています。
(筆者はここが混乱のもとだなと感じました。。。)

電子(以下、デジタル)署名は、まず送信したいデータからハッシュ値を求めます。次に、求めたハッシュ値を秘密鍵で暗号化します。最後にデータと一緒に(データとは別に)相手に送信します。
受信者は受信したデータをデータと電子署名に分割し、まずデータのハッシュ値を計算します。次に、デジタル署名を公開鍵で復号化します(=元データのハッシュ値になる)。
計算したデータのハッシュ値とデジタル署名を復号化したものは同じ値になるはずです。

秘密鍵と公開鍵は対になっているので、同じ値になったということは、送信者はその人であるということが分かります。
また、データ自体のハッシュ値も同じものなので、送信されたデータと同じデータが来たということもわかります。

暗号方式による可否

交換鍵暗号方式では、利用する暗号方式によって暗号化、デジタル署名のそれぞれできることが異なります。
例として出した方式ですと、以下の通りになります。

完全性と真正性

公開鍵からデータと署名が一致したということは、2つのことが分かります。
一つ目は、「送信されたデータと受信したデータが一致している(データが改ざんされていない)」ということです。
このような状態のことを完全性が保たれていると言います。
二つ目は、「データの送信者が意図した人(サーバ)である」ということです。
このような状態のことを真正性が保たれていると言います。
また、この真正性が保たれるということは、「このデータは間違いなくあなたが送信した」という証明にもなります。
このようなことを否認防止と言います。

まとめ

公開鍵暗号方式について概要や説明を対となる共通鍵暗号方式と合わせて、画像付きで紹介しました。