暗号の鍵をなぜ公開するのか？

インターネットでは他人に見られたくない文章や情報は暗号化して送ったり、受取側では暗号を元の文章などに戻したりすることができます。途中で第三者が暗号文を入手しても暗号を解くことが出来なければ安全な通信手段となります。この暗号化したり復号（暗号文を元に戻すこと）したりするには鍵を利用します。インターネットでの暗号の鍵は文字列（数字のデータ）です。ところが、「鍵を公開」する場合があり、公開してしまうと鍵としての役割は失われると思われるかも知れません。ここでは、暗号の作り方と戻し方についての説明を通して、公開する鍵とはどのようなものかとその役割についてお話しします。

ローマ時代のジュリアス・シーザーが使用したと言われるシーザー暗号があります。ABC・・・を3文字ずらせてDEF・・・とし、最後のXYZをABCにする方法です。例えば、DOGはGRJとなります。暗号化の方法（アルゴリズム）は「文字をずらす」ことで、3 文字ずらすことから暗号化の鍵（データ）は「3」となります。暗号化のために使う鍵と復号のために使う鍵が同じもので、これを共通鍵暗号方式と言い、第三者へは秘密にすることから秘密鍵暗号方式とも言われます。第三者が文字ずらし暗号であると知っていれば、この鍵「3」を知らなくても、アルファベットは26文字なので25回試してみれば解読（第三者が暗号文を解くこと）ができます。各文字をランダムに並び替えると鍵の数は無数（26の階乗）にあるので解読は困難と思われますが、暗号文の文字の使用頻度や並びにより実際には解読がなされているようです。

昔から種々の暗号方式が開発されてきましたが、コンピューターにより現実的な時間内に暗号解読が行われるようになってきたため、新しい暗号方式が必要になりました。米国でDES（Data Encryption Standard）暗号と言う共通鍵暗号方式が開発され、1977年以降、米国標準の暗号方式として使われています。DES暗号方式は複雑な処理を行いますが、ここでは簡単に説明します。

図１初期転置の仕方

共通鍵は64ビットのデータ（そのうち8ビットはパリティチェック用で実質的には56ビット）で、送信者あるいは受信者のどちらかが作成して相手に連絡します。この共通鍵を、手順に従い（この手順は公開されています）16個の内部鍵（各48ビット）を作成します。この手順を以下に示しますが、詳しい説明が必要であれば「DES暗号」などで検索してみて下さい。転置という言葉が何度か出てきますが、これはデータ場所の入れ替えを行う操作のことです。初期転置を例にして転置の仕方を図１に示します。なお転置表は全て公開されています。

縮約型転置：共通鍵の各ビットの入れ替えを行い、パリティビットを取り去り56ビット列にする。

循環シフト1：この転置された56ビット列を28ビット列ずつに分けて、それぞれ循環シフトする。循環シフト表も公開されている。

循環シフト2：循環シフト1で得た28ビット列ずつを、上記循環シフト表の2番目に指定されたシフト量でシフトする。以降、同じように循環シフトを計16回繰り返す。

繋ぎ合わせ：各シフトで得た2組の28ビット列を繋ぎ合わせて56ビット列にする。16組に対しそれぞれ行う。

縮約型転置：繋ぎ合わせた各56ビット列を縮約型転置して48ビット列にする。この各48ビット列が16個の内部鍵K(1)~K(16)となる。

次にこの内部鍵を使って暗号化する方法について説明します。
最初の文章（平文［ひらぶん］と言います）は英語や漢字などですが、コンピューターの中では全て２進数で処理するので、アルファベットや数字の各文字は8ビット（1バイト）、漢字や全角かなは16ビット（2バイト）の文字列（0か1の数値）になります（シフトJISの場合）。例えば「暗号」という文字は1000100011000011と1000110110000110になります。
２進数文字列になった平文を暗号化することになります。その先の手順を以下に示します。

ブロック化：２進数平文を64ビット毎のブロックに区切る。

初期転置：各ブロックに対し、初期転置を行う。その後、32ビットずつの2つに分け、L(0)とR(0)とする。

拡大転置：R(0)を48ビットへ拡大転置し、それをE{R(0)}とする。下記の関数処理を内部鍵48ビットとの間で行うため。

関数処理：E{R(0)}と内部鍵K(1)を関数処理（XOR^*1、換字選択関数表による換字処理、転置）
　　　　　*1 XOR：Exclusive OR、排他的論理和

XOR処理：上記関数処理をして得た32ビット列とL(0)のXOR処理を行い、その結果をR(1)とする。

次の段階：L(1)= R(0)とし、R(1)の拡大転置、内部鍵K(2)との関数処理、XOR処理を行う。以降、計16回同じことを繰り返す。

最終転置：32ビットのL(16)とR(16)を繋ぎ合わせて64ビット列にし、最終転置を行う。

このようにして得たものが1ブロック分の64ビット暗号文で、他のブロックでも同じ手順で暗号化します。
復号には同じ共通鍵を用います。暗号化と同じ手順ですが、内部鍵はK(16)、K(15)、・・・、K(1)の順番で使用します。
内部鍵の作成や暗号化、復号の仕方を記載しましたが、この部分は読み飛ばしても構いません。複雑な処理を行うということだけを覚えていただくだけで結構です。

1990年代後半になると、コンピューターの処理性能向上により総当たり攻撃による解読の成功例が報告されるようになりました。DESを改良した3DES（鍵のビット数を増やす）が使われるようになりましたが、近年、3DES も含めDES暗号方式の安全性が低下したため、米国国立標準技術研究所から2023年以降の使用禁止が提案されました。次世代の暗号方式としてAES（Advanced Encryption Standard）が2001年に標準暗号となりました。現時点では現実時間内の解読は困難とされていますが、いずれは解読されると思われます。

共通鍵暗号方式では同一の共通鍵を暗号化と復号化の両方で使用します。この鍵を渡す時に鍵が第三者へ漏洩する可能性があります。鍵の送付を行わないで済む方法が開発されました。信じられない方法と思われますが、これが公開鍵暗号方式です。
公開鍵暗号方式では、受信者が公開鍵と秘密鍵の両方を作成し、公開鍵は公開します。一方、秘密鍵は送付を行わないで秘密裡に自分の所で保管します。送信者は公開された鍵で暗号文を作り、受信者へ送ります。受信者は秘密鍵を持っているので、復号することができます。しかし第三者は秘密鍵を持っていないので復号ができません。どうしてこのようなことが出来るのかについて、公開鍵暗号方式の基本であるRSA暗号について説明します。なおRSAは発明者の名前の頭文字を取ったものです。

最初に公開鍵e、n、秘密鍵p、q、dを作成します。これらの鍵は全て文字列（数値）です。以下に示す鍵や暗号化、復号の理論には数学的な考えが必要で、本ブログの範囲からは離れるため、計算方法の要点だけを記載します。また、条件があるものもありますがこれも割愛します。

図２　合同式（mod）

1) ２つの大きな素数p，qを選択する。
[実用上] p、qは10の150乗くらいの数値。

2) n＝pqを計算（掛け算）する。
[実用上] nは10の150～300乗くらいで十分であるが、最近では10の600乗が推奨されている。

3) (p－1)(q－1）と互いに素な数eを選択する。
[実用上] よく利用されるeの値は3と65537。

4) de≡1 (mod(p－1)(q－1))となるdを計算する。拡張ユークリッド互除法によりdを求めることができる。modの合同式は図２を参照。

次に公開鍵e、nを使って平文を暗号文Cに変換します。

1) 平文を数値で表現した文Mへ置き換える。

[例1] 漢字文→[文字コード変換表]→16進数→[16進数から10進数への変換ツール]→10進数

[例2] a→01、b→04、c→03、・・・等の自分達（送信者、受信者、グループ）で作った変換表

2) Mがnよりも大きいときにはn以下の数になるように分割し、それぞれを暗号化する。

3) C≡M^e(mod n) 　Mをe乗^*2した数をnで割った余りとCをnで割った余りが等しくなるようにCを求める。このCが暗号文となる。

*2 「Mのe乗」は、実際には何100桁の大きな数になることもあるのでそのままの計算は不可能。mod演算式 ab(mod n)＝(a(mod n)×b(mod n))(mod n) の活用や、べき乗計算の工夫（バイナリ法、中国の剰余定理など）で桁数や計算回数を削減する。なお、暗号化計算のアプリケーションソフトが利用可能である。

暗合文を送った後、受信者は暗号文Cを平文M’に復号し、漢字文等へ変換します。ここでは公開鍵nと秘密鍵dを用います。

1) M’≡C^d(mod n) 　Cをd乗した数をnで割った余りとM’をnで割った余りとが等しくなるようにM’を求める。このM’が復号文となる。

2) M’を漢字文等へ置き換えると元の平文になる。

公開鍵e、nを知っていればRSA暗号を作ることは誰にでも可能です。しかし秘密鍵dを知らなければ復号はできません。公開鍵を作る時に一緒に秘密鍵を作ることができるのに、第三者（第ニ者も）が公開鍵を知っていても秘密鍵を見つけることが何故できないのでしょうか。
２つの素数p，qを掛け合わせた数n（＝pq）を作るには単に掛け算をするだけ良いのですが、nから素数のpとqを見つけるのは簡単にはできません（「一方向性」と言います）。例えば、素数ｐ＝1231、ｑ＝4567とすればn＝5621977となりますが、逆に5621977から因数分解を行って素数p、qを求めるにはかなりの時間がかかります。大きな数になればなるほど大きなコンピューターを使ってもなかなか解が出てきません。素因数分解の世界記録（2023年3月時点）は2010年の232桁（768ビット）と言われていますが、300台のパソコンの並列計算処理を行って約3年がかかったとのことです。
RSA暗号は秘密鍵dを探すのにnの素因数分解（p、q）に時間がかかるので安全性が高いと言われています。鍵長を大きくすればするほど安全性は高まりますが、暗号化や復号の処理にはより時間がかかります。更に進んだ暗号方式として楕円曲線暗号が使われています。RSA暗号より短い鍵長で同程度の安全性を確保でき計算処理等が効率的に行えるという利点があります。

共通鍵方式は旧式と思われがちですが、そうではありません。公開鍵方式に比べ共通鍵方式は短い時間で暗号化や復号の処理ができます。共通鍵方式の難点は鍵を送る時の漏洩ですが、公開鍵により共通鍵を先方に送ると漏洩の危険は下げることができます。この両者を使用する方式はハイブリッド暗号方式と呼ばれています。