15.7.3. 公開鍵暗号と署名の検証

公開鍵暗号について，より深く学びましょう．

鍵の用途 #

公開鍵暗号アルゴリズムでは 公開鍵と秘密鍵 のペアを使います．

通常は，個人ごとに鍵ペアを持ちます．そのため， 2x2x2 で8通りの複雑さがあるので，混同に注意してください

公開鍵と秘密鍵
鍵の作成者と使用者
電子署名と暗号化

	公開鍵	秘密鍵
流通	複製多数	作成者のみ
機能1	検証専用受信側が使用	署名専用送信側が使用
機能2	暗号化専用送信側が使用	復号専用受信側が使用

「公開鍵を使う」場合，たいていは他人の公開鍵です．自分の公開鍵は，ほとんどのケースで相手に使ってもらう，ことが多いです．

公開鍵と秘密鍵は，鍵と名前がつきますが，日常生活の鍵らしさはあまりありません．

暗号化と復号の場合は，錠前 (南京錠) をみんなに配って、自分宛のプレゼントを施錠してもらう，対応する鍵を持つ自分だけが開封できる当てはめると，錠前が複数あって鍵が1つという状況と一応対応します．署名と検証はぴったりくる比喩がないので，固有のマジックインキを持っていて偽札予防のような特殊な書き込みができる，専用眼鏡で見るとそのことが分かる，というような意味合いで，多少強引ですがブラシと眼鏡で示します．

電子証明書とPKI #

公開鍵暗号では，通信相手の正しい公開鍵を持っておく必要があります．

そうでないと...

署名の受信者の立場では，電子署名の検証に成功しても，想定する本人の署名とは限らず騙されてしまうかもしれません
暗号化の送信者の立場では，秘密にしたかった情報を，誰か別の人に送ってしまうかもしれません．

人の場合は，対面で公開鍵を交換すると，この問題は緩和されます．

公開鍵に電子署名をつけると，公開鍵の信頼性を高めることができます．

今が，人物a の公開鍵と称する「鍵?」を受け取りました．この鍵が本当に人物a さんのものか分かりません．つまり，偽物がaさんに成りすまして，偽の鍵を渡してきたかもしれません．ここで，すでに信頼する公開鍵による署名が「鍵?」についていれば，その署名者は，「鍵?」を信頼しているということが分かります．つまり，いかのような状況です．

さんが人物b さんを信頼し，かつ，公開鍵を持っていて
鍵? に人物bさんの署名があり，
その署名を正しく検証できた

事前に，さんは人物b さんとその公開鍵を信頼していました．今回署名の活用で，信頼が延長して，人物a さんの公開鍵を信用することができました．

信頼できない鍵に，迂闊に署名してはいけません．そのような人の署名を信じないことも重要です．

公開鍵とその所有者情報に署名を施したものを 電子証明書 と言います．

HWBのウェブサーバの証明書: Let’s Encrypt という認証局の署名をもらっていることが読み取れます

ウェブブラウザは，URLに相当するウェブサーバが本物であることを確認してから通信を始めます．

そうでないと...

フィッシングサイト (偽サイト) に大切な情報を送ってしまうかもしれません．

ウェブブラウザは，ウェブサーバが提示した電子証明書 (の公開鍵) を使いたいのですが，世界には無数のウェブサイトがあるので，初めて接続するサイトの公開鍵は初見で受け取ることになります．このときに，その公開鍵を信頼して良いかを判断する仕組みが，PKI (public key infrastructure) です．ウェブサーバの電子証明書には， 認証局 が署名します．

この認証局の公開鍵をウェブブラウザが知っていれば，先ほどと同じように，信頼を延長して，ウェブサーバの公開鍵を信頼して使うことができます．ウェブサーバは，ルート証明書と呼ばれる，電子証明書をあらかじめ何枚か持っていて，各証明書には，証明局 (ルート認証局)の名前と公開鍵などが含まれています．

ルート認証局は，中間認証局の電子証明書に署名して権限を委譲することもできます．中間認証局自身も，同様に権限を委譲することもあります．ウェブサーバの電子証明書の署名が中間認証局のものだった場合は，すぐには署名を検証できないかもしれません．しかし，中間認証局の電子証明書には署名がありますから，その認証局をたどっていくと，正常に運用されていればルート認証局にたどりついて検証することができます．

Chrome の場合，アドレスバー左端を右クリックして，Connection is secure のサブメニュー keyboard_arrow_right から

Certificate is valid のメニュー open_in_new を選ぶと，ウェブサーバの電子証明書が表示されます．

RSAのアイデア #

公開鍵暗号では，暗号化と復号に別の会議を使うのでした．公開鍵を配っても暗号文が安全なんて，そんな暗号方式が可能なのか? という疑問ももっともです．

そこで，実現できそうな雰囲気をつかむために，有名な RSA 暗号のアイデアを紹介します。 RSA の登場は，公開鍵暗号アルゴリズム全般の発展のきっかけとなりました．

整数 1つを暗号化する前提で、以下のような数 $(e, d, n)$ を用意します。

$ (m^e)^d \equiv m \pmod n \quad \forall m\le n-1 $

$d$ は $\mod n$ の世界で $e$ 乗の逆演算になっていることを上の式は示しています。
ここで

公開鍵 $(e, n)$ 、
秘密鍵 $d$

とします。

暗号化は送りたい数 (平文) を $e$ で冪乗します

$$\text{暗号文} \gets \left(\text{平文}^e\right) \quad \mod n$$

復号は暗号文を秘密鍵 $d$ で冪乗します

$$\text{平文} \gets \left(\text{暗号文}^d\right) \quad \mod n$$

観察 #

この手順は，必要な性質をもっているでしょうか?

公開鍵だけからは復号ができない
公開鍵から，秘密鍵の予想が難しい

$\mod n$ の世界で $e$ 乗するという手順と，公開鍵 $e, n$ が公開されているので，底を $e$ として $\log_e\text{暗号文}$ を $\mod n$ の世界で計算できれば平文を復元できます。これを 離散対数問題 と言います。

現時点では $(e, d, n)$ を大きな数でうまくつくると、効率の良い攻撃方法は知られていません。以下のように， $n$ を素数の積で作っているので，大きな数の素因数分解ができるかどうかが，秘密鍵を予想したり暗号を解読できるかと密接に関わります．量子コンピュータが実用化されたら，大きな数の素因数分解も効率よく解けると予想され、その場合は別の公開鍵暗号手順に切り替える必要があります．

数学 #

概略としては以下のような流れで作成できます．

大きな素数 $p$ と $q$ を用意して， $n = p\cdot q$ とします．
鍵ペア $(e, d)$ を作る準備として， $\ell=\operatorname{lcm}(p-1,q-1)$ を作ります．
$\operatorname{gcd}(e, \ell) =1$ となるように $e$ をとります．
秘密鍵 $d$ を $de \equiv 1 \mod \ell$ となるようにとります．これは拡張ユークリッド互除法で求められます．
つまり， $\ell$ が分かると，公開鍵 $e$ から $d$ を作れてしまいます．数が沢山出てきますが， $n$ と $\ell$ は異なることに注意してください．

復号できることは次のように追えます

$ \begin{aligned} &\text{平文}^{ed}\equiv \text{平文} \pmod n\\ \iff& \text{平文}^{ed-1}\equiv 1 \pmod n\\ \iff& \text{平文}^{(k\ell+1)-1} \equiv 1 \pmod n\\ \iff& \text{平文}^{k\underbrace{\text{lcm}(p-1, q-1)}_{\ell}} = k' \underbrace{(pq)}_n + 1\\ \end{aligned} $

$ \begin{aligned} \text{lhs} \equiv& 1 \pmod p \qquad \text{--- Fermat's little theorem}\\ \equiv& 1 \pmod q\\ \end{aligned} $

効率や安全性の注意などの詳細は割愛します．

参考書籍 #

興味があれば，以下の書籍等もお勧めです．

『暗号技術入門第 3 版』結城浩（SB クリエイティブ）

「暗号と認証のしくみと理論がこれ1冊でしっかりわかる教科書」光成滋生（技術評論社）

Wikipedia: Fermat's little theorem Wikipedia: RSA cryptosystem

量子コンピューティング・ワークブック東京大学素粒子物理国際研究センター