公開鍵暗号方式において、暗号化は公開鍵を用いて行われ、受信者は秘密鍵を用いて暗号化されたデータを復号する。

このとき公開鍵と秘密鍵はペアであり、データを暗号化して送信する者をA、データを受信して復号する者をBとすると、公開鍵はBが作成して公開した鍵であり、秘密鍵はBが作成して自分で保持している鍵である。

公開鍵を公開しないと暗号化することができないし、
秘密鍵を公開してしまうと誰でも復号化できてしまう。

公開鍵暗号方式では署名と検証ということも行われる。

署名と検証においては送信者が秘密鍵を用いて署名し、
受信者が公開鍵を用いて検証する。

この話を聞くと、
『要するに暗号化は公開鍵で暗号化して、署名は秘密鍵で暗号化するってことだね？』
と言いたくなってしまうのだが、そうではない。

とりあえず、「署名は秘密鍵で暗号化するということではない」と覚えておけば、
会話して笑われたり怒られたりすることはない。

が、そこで『じゃあいったい署名ってどんな処理なの？そしてそれを検証するってどういう処理なの？』
と考えてほしい。

というか、私はそれを考えて軽く調べてみたのだがよくわからないのである。

公開鍵暗号方式は、ある程度大きな数の素因数分解が困難であることを利用している。
ある程度大きな桁数の素数を掛けることは容易であるが、
結果からもとの二つの素数を求めることはコンピュータを使っても事実上不可能である。

d1をもとのデータ、d2を暗号化したデータ、k1を公開鍵、Eを暗号化する演算とすると、

d1 E k1 = d2

k2を秘密鍵、Dを復号する演算とすると

d2 D k2 = d1

となればよい。

このとき、Eが単なる掛け算であったら、k1は公開されているので、
d1を求めるにはd2を k1で割ればよいことになってしまう。

だから、Eはk2を使わないと復号できないような演算でなければならない。

それはどういう方法だろうか？

RSA暗号のwikipediaを見る

鍵のペア（公開鍵と秘密鍵）を作成して公開鍵を公開する。
まず、適当な正整数 e を選択する。
また、大きな2つの素数の組み{p,q}を生成し、
それらの積 n=pq を求めて、
組み{e,n}を平文の暗号化に使用する鍵（公開鍵）とする。
2つの素数{p,q} は秘密に保管し、
暗号文の復号に使用する鍵（秘密鍵）d の生成にも使用する
d=e^-1 mod Φ
ここで
Φ=lcm(p-1,q-1)
※lcmは最小公倍数
暗号化（平文 m から暗号文 c を作成する）：
c=m^e mod n
復号（暗号文 c から元の平文 m を得る）：
m=c^d mod n
暗号化（e 乗）は公開鍵 {e,n} があれば容易に計算でき、
復号（d 乗）も容易に計算できる。
しかし、秘密鍵 d を知らずに解読（法 n の下で e 乗根を計算）するのは、
「n の素因数を知らないと難しい（大きい合成数の素因数分解も難しい）」
と考えられている。
つまり、「秘密鍵を用いずに暗号文から平文を得ることは難しい」と信じられている。
これがRSA暗号の安全性の根拠である。

鍵生成

k をセキュリティパラメータとする。
p,q（ただしp≠q）をk/2ビットの素数とし、
n=pqとする。
eをΦ(n)未満の正の整数で、
Φ(n)と互いに素な数とし、
dを、Φ(n)を法としたeの逆数 ( deΞ1 (mod Φ(n)) )とする。
ただしここでΦはオイラーのφ関数で、
この場合は
Φ(n)=(p-1)(q-1)
である。
dは、e,Φ(n)が既知の時には拡張されたユークリッドの互除法を使えば容易に求まる。
deをΦ(n)で割った整数商をxとした場合、
de+(-x)Φ(n)=1
が成り立ち、
かつ
eの取り方から
gcd(e,Φ(n)) = 1
であるのでこれを解けばよい、
dを秘密鍵とし
n, eを公開鍵とする
pとqが漏れるとdが計算で求まるため、pとqは安全に破棄すること

暗号化

aを平文空間Znの元とする。
b=a^e mod n を計算し、bを出力する。

復号化

bを暗号文とする。
a' = b^d mod n を計算し、a'を出力する。
ここでa'=aとなり、復号できる。

ちなみに公開鍵暗号方式は最初RSA暗号方式なしに考案されて、
それを実現するためにRSA暗号方式が考えられたらしい。

さて。

では署名と検証である。

だいたい、以下のように説明されている。

送信者がデータのハッシュ値を計算して秘密鍵で暗号化し添付（これが署名）
受信者が暗号化されたハッシュ値を公開鍵で復号
受信者が自分でデータのハッシュ値を計算して、復号したハッシュ値と等しいかどうかを確認

wikipediaに書いてある通り、暗号化も復号化もおこなっている演算はある数について
ある数の累乗を求めそれをある数で割った余りを計算している。

同じ計算を違うパラメータでおこなうことによって暗号化になり復号化になるのである。

デジタル署名においては先に秘密鍵による演算がなされてその結果に対して公開鍵による演算がなされる。

これを、『秘密鍵により暗号化し公開鍵により復号化する』と言ってはいけないのだ。

そう言うと怒る人がいる。

怒る理由は、私が調べて理解したところでは以下の2点である。

それはRSA暗号方式にしかあてはまらない
署名で「暗号化」するのはデータではなくデータのハッシュである

以下はRSA暗号方式を使うこと前提にした話である。

私が調べて理解した知識によれば、「秘密鍵でも暗号化できる」。
ただし、デジタル署名で暗号化するのはデータそのものではなくデータのハッシュである。
秘密鍵で暗号化されたデータのハッシュを公開鍵で復号化し、
自分でデータのハッシュを計算してその結果を復号化したハッシュと比較する、
これが「署名の検証」である。

では、データのハッシュを公開鍵で暗号化して秘密鍵の保持者に送信したら「署名」になるか？

ならない。

なぜなら公開鍵は公開されているので誰でもそれを使ってハッシュを暗号化することはできるからだ。

では、ハッシュではなくデータそのものを秘密鍵で暗号化して公開鍵で復号化させたらどうか？
暗号化というのは、「鍵を生成した人」ではなく、「鍵を生成した人に暗号化したデータを送信する人」が行う。
では、逆の場合は？「鍵を生成した人」が、誰かに暗号化したデータを送りたいときにはどうすればいいのか？

その場合は、データを送りたい相手に鍵ペアを生成してもらうのか。

秘密鍵でハッシュを暗号化し復号できるなら、秘密鍵でデータそのものも暗号化できるはずだが、
そういう話は聞かない。

それをしないひとつの理由として、秘密鍵は公開鍵より鍵長が長くて演算に時間がかかる、ということが説明されていたが、

時間がかかるからやらない、ということなら不可能ではないということだ。
（未完）