1976 年に戻って未来へ

NIST PQC 標準化プロセスに関連した知識の体系化

 

Abstract

1. 可換アルゴリズム

1.1 Diffie-Hellman-Markle
1.2 RSA

2. 鍵生成は「うそ」をつかねばならない。

3. 非可換アルゴリズム

3.1 リヴエストの思考回路は受信者を出発点に置く...しかし、
3.2 関数 Y1()と Y2()各々は一方向関数ではない。
3.3 バックドアを塞ぐための「確率計算式」
3.4 一対の変換{Y1(), Y2()}は一方向関数である、なぜなら、
3.5 公開鍵互換 PQC を見る準備

4.上記、知識の体系から見た PQC

謝意

CRYPTOGRAPHY by DOUGLAS R. STINSON CHAPMAN & HALL/CRC
The Code Book by Simon Singh

 

Abstract

1976 年 Diffie-Hellman-Markle は鍵配送のジレンマを解決した。それ以前に鍵配送の現実的なシナリオは有るには有ったが、そのシナリオは「DES に二重に鍵をかけたら、逆順に鍵を外さねばならない」という逆順のルールに邪魔されて情報技術として実現しなかった。しかし、Diffie-Hellman- Markle は DES の逆順のルールに縛られなかった訳である。この数学は可換アルゴリズムである。そして RSAも可換アルゴリズムであることが容易に判る。可換アルゴリズムは逆順のルールに邪魔されない、これは画期的な発明である。が、Shannonの数学は量子耐性を保証しない:このシステムを量子耐性にしたいなら鍵生成が「うそ」をつかねばならない。2014~18 年筆者は、逆順のルールに潜んでいる AES のShannonエントロピーから、一方向関数を創ることに成功した:実装もした。 非可換アルゴリズムの誕生である。非可換アルゴリズムは可換ではないから公開鍵に互換ではないが、その安全性は現実の習慣に寄り添う。NIST の Post-quantum cryptosystem(PQC)は可換アルゴリズムに属するだろう。本ペーパは非可換アルゴリズムの光に照らして見たところの PQC の着地点を議論する。本論はここから 1976 年にさかのぼる。

1. 可換アルゴリズム

1.1 Diffie-Hellman-Markle
Fig,1: 可換アルゴリズムで結ばれるアリスとボブ

Fig,1 は D-H プロトコルが可換アルゴリズムであることを示そうとしている。Yα(mod P)という形式の一方向関数が活躍する。αは内部変数である:アリスはα1 を手元に置き、ボブはα2 を手元に置き、外部変数 Y と P の値をアリスとボブが取り決める:取り決めに際し、大声を出しても問題ない。 第三者から見るとα1 とα2 は確率変数であるので、計算 Yα1 (mod P)と Yα2 (mod P)を関数の形で下記のように表現する:

Yα1 (mod P)≡F1(Y)
Yα2 (mod P)≡F2(Y)

Fig.1 の S2 と S1 は各々次のように関数形で与えられる:

S1= {Yα1 (mod P)}α2 (mod P)= F2(F1(Y))
S2= {Yα2 (mod P)}α1 (mod P)= F1(F2(Y))

結局、Diffie-Hellman-Markle 鍵配送は次のように要約される;

S1 - S2 = F2(F1(Y)) - F1(F2(Y)≡F2F1 - F1F2 =0 -----------(1)

ここで F2(F1(Y))と F1(F2(Y)は Y に関する各々多重暗号である。多重暗号の差分(S1 - S2)をエントロピー常数と定義する。

(S1 - S2)≡エントロピー常数-----------(2)

F2F1 - F1F2 =0 なる式が可換アルゴリズムです:可換アルゴリズムが有れば、アリスとボブは秘密の共有関係を創れる:これには認証機能が欠落していて、秘密の共有関係を任意の二人に保証するのは難しい。エントロピー常数ゼロは二者間に Shannon エントロピーの壁が無いことを意味する。エントロピーの壁が無いことは当然、秘密の共有関係を危機に陥れる原因となる。

1.2 RSA

1975 年の夏、Diffie は非対称鍵の構想を発表した。リヴエストの思考回路はそこに止まった、「Diffie の言う非対称鍵は実際に有るのだろうか?」と。今、受信者アリスが持つ特別の情報(鍵)を K1 と 表し、送信者ボブが持つ鍵を K2 と表す。
 

Fig.1: 錠前が二つ付いたカバン Bag with two locks

 
 
1976 年当時、鍵配送の現実的なシナリオが既に有った:錠前の二つ付いたカバンが主役である。対応する鍵はK1とK2である: 鍵K1はアリスが持ち、鍵K2はボブが持つ。ここには共通鍵が無いし、特別の情報も無いことに注目する。 
 
 

鍵配送の現実的なシナリオでは、ボブが最初に、乱数 x1 を振り出し、これに K2 で鍵かけをしてから暗号をアリスに送る。さらに受信者アリスがその暗号に K1 で鍵をかけて下記の(3)をボブに返送する。二重に鍵の掛かった暗号を確率変数 P で表すと:

P2=K1(K2(x1)) -----------(3)

これは確率変数 P で二重に鍵の掛かった暗号を表す。ここから鍵配送のシナリオは鍵を外すプロトコルに入る。もし、DES なら「逆順に鍵を外さねばならない」というルールに邪魔されてボブは(3) の鍵 K2 を外せない。もう一つのやり方は、アリスが送信者になり、乱数 x1 を振り出し、これに鍵 K1 を掛けてボブに送る場合である。今度は受信者ボブが鍵 K2 を掛けてアリスに返送する:そうすると アリスも又「逆順に鍵を外さねばならない」ルールに邪魔されて(4)の鍵 K1 を外せない:てから暗号をアリスに送る。さらに受信者アリスがその暗号に K1 で鍵をかけて下記の(3)をボブに返送する。二重に鍵の掛かった暗号を確率変数 P で表すと:

P1=K2(K1(x1)) -----------(4)

ここでもアリスは鍵 K1 を(4)から外せない。このように逆順のルールに邪魔されて(3)/(4)を復号する アルゴリズムが無い。
リヴエストはなお考えた「受信者が特別な情報を持っている時に限り、一方向関数の逆向き計算が可能になる、そのようなアルゴリズムが見つかるだろうか?」と。これが見つかった時、「受信者アリスはボブに P2 を返送する必要が無い」:なぜなら、特別な情報としての鍵 K1 を掛けた時点で、 アリスはボブの乱数 x1 を手に入れるからである:次の通り、:

P2=K1(K2(x1)) =x1-----------(5)

ボブも特別な情報としての鍵 K2 を掛けた時点で P1 を返送する必要が無く、アリスの乱数 x1 を手に入れることが出来る:

P1=K2(K1(x1)) =x1-----------(6)

上記の通りであれば、D-H プロトコルと同じ成り行きになる:

P1 - P2 = K2(K1(x1)) - K2(K1(x1)) = x1 – x1 = 0-----------(7)

ここでもエントロピー常数はゼロになり、関数 K1()と K2 ()は可換になる。アリスとボブは秘密を共有する関係を創ることが出来る。しかし、アリスとボブの間に Shannon エントロピーの壁は無い、それで壁の欠落はシステムを危機に陥れる原因になる。

このように可換アルゴリズムは鍵を公開する技術ではなく、鍵を配送する技術である。それゆえ Post-quantum cryptosystem(PQC)が公開鍵に互換であろうとするなら、PQC は当然、可換アルゴリズムのルールに従うことになる。そうすると、鍵 K1 と K2 のどちらかをネットに公開するためには鍵生成は「ウソ」をつかねばならない。

2. 鍵生成は「ウソ」をつかねばならない。

PQC が公開鍵と互換である限り、いかなる数学技巧が駆使されようとも、PQC は下記 Shannon entropy の数学に拘束される。ここで H()は Shannon エントロピーを計算する。

今、鍵 K1 から K2 への計算は容易だという:➡H(K2|K1)=0。他方、:鍵 K2 から K1 への計算は複雑でプログラムの開発が難しい、と言う。難しいと言っても、計算困難性の Shannon エントロピーもまた H(K1|K2)=0 である。この計算困難性を H(K1|K2)>0 のごとく言うとしたら、それは「ウソ」です。もっと詳細に「ウソ」を見てみましょう。鍵 K2 と K1 の同時確率エントロピーには、二通りの表現が有る:

H(K1, K2)=H(K1) + H(K2|K1) ---------(12-1)
=H(K2) + H(K1|K2) ---------(12-2)

最初の鍵 K1 から K2 の計算は容易だというのは(12-1)にて H(K2|K1)=0 になる。それで(12-1)は(13) になる:

H(K1, K2)= H(K1) ---------(13)

もう一つは(12-2)、鍵 K2 から K1 への計算は複雑だと言うが、H(K1|K2)≠0 には成らない。なぜならその計算に不確定は無いから H(K1|K2)=0 になる。
ここで筆者は「ウソ」をつく:鍵 K2 を公開し➡H(K2)=0、鍵 K2 を条件とする K1 の Shannon エントロピーH(K1|K2)はゼロにならない、と「ウソ」をつく:

H(K1, K2)= H(K2) + H(K1|K2)= H(K1|K2)≠0 ---------(14)

これが正しくないことは、(13)と(14)から(15)式が出て来るから判る:

H(K1)= H(K1|K2) ---------(15)

これは鍵 K2 と K1 は独立であるという式です。先に鍵 K1 から K2 への計算は容易だと定義したから、 (14)式は「ウソ」をついていることが判る。ただ、下記の不等式に「ウソ」が隠れる場合が有る:

H(K1)> H(K1|K2)>0 ---------(16)

長い時間なら H(K1|K2)=0 になり、短い時間なら H(K1|K2)>0 である。

(16)式が「ウソ」をついている事実を積極的に隠している訳ではなく、「ウソ」が隠れるように 標準化プロセスが知恵を出す努力を認める、そういう不等式である。実際、PQC-forum はそういう 議論をしているし、標準化プロセスは最適化の議論を歓迎している。

この不等式から学ぶことがもう一つ有る:候補者が実装環境のサポートを求めていたら、それを欠点と見るのではなく、「ウソ」を隠す環境を求めていると考えてみる。又、候補者はいずれも長所と欠点を帯びているように見えるけれど、それは客観的な事実ではなく、不等式(16)の中だけに存在する PQC に過大な期待をしているからである、と考えて見てはどうか?私がこのように述べる背景には、非可換アルゴリズムが有る。

3. 非可換アルゴリズム

非可換アルゴリズムは現実的な鍵配送シナリオ(Fig,1)を DES 又は AES で表現したプロトコルとして定義することが出来る。このプロトコルは逆順のルールに従うことを我々に強制する。ここから脱出に成功した者が D-H プロトコルと RSA です。歴史はそのように教えている。再び、先の(3)と (4)をここに掲載する:

P2=K1(K2(x1)) -----------(3)
P1=K2(K1(x1)) -----------(4)

ボブは逆順のルールに当面し、(3)の鍵 K2 を外せない(K1 はアリスが持っている)。アリスも逆順の ルールに当面し、(4)の鍵 K1 を外せない(K2 はボブが持っている)。ボブにとってもアリスにとって も第三者にとっても暗号 P を復号する鍵が手に入らない。それで、(3)と(4)の差分{P1- P2}はゼロに ならない、圧倒的な確率で次式を満足する:

{P1 - P2}≠0 ---------(17)

ここではゼロエントロピー常数は現れない。したがって、関数 K1 と K2 は非可換。これの売りはアリスとボブの間にShannonエントロピーの壁が在ることです。この壁が在るゆえに、システムが危機に陥ることを防ぎ、また、この不等式(17)から一方向関数が立ち上がることです。説明します。

3.1 リヴエストの思考回路は受信者を出発点に置く...しかし、

リヴエストの思考回路は...受信者が特別な情報を持っている時に限り...と、受信者が出発点である。 しかし、ここでは送信者アリスが出発点である。送信者アリスは、(3)/(4)の鍵 K1 と K2 をランダムに 選び(鍵生成を行い)、任意の文書のハッシュ値 x1 からコード P1 と P2を作る、又は、複数のノード から来た乱数の合計を入力に持つハッシュ値 x1 からコード P1 と P2 を作る:

P1= K2(K1(x1)) ---------(19-1)
P2= K1(K2(x1)) ---------(19-2)

この作り方は次の通り:アリスはデータ x1 を AES1 のノードに移動し K1(x1)を出力し、次に K1(x1) を AES2 のノードに移動し P1 を出力する。P2 についても同じ、ただ移動の順序が異なる。要するに、 K1(x1)と K2(x1)が仮想ネットワークの中を移動してコード P を出力する訳である。コードを P1 と P2 の二つだけにする理由は特に無い、n 個用意できる。(19)式はたまたま2個である。(19)式を関数の形式に表す。AES 鍵空間の一点を Y1、他の一点を Y2 と定義する:そうすると、鍵 Y1 を掛ける変換 が Y1() で表され、鍵 Y2 を掛ける変換が Y2()で表される。以下の通りになる:

P1=Y1(x1) ---------(20-1)
P2=Y2(x1) ---------(20-2)

特筆すべきこと:アリスが生成した鍵 K1 と K2 はデータとして存在するが、鍵 Y のデータはどこに も無い:つまり Y は AES 鍵空間に確かに存在するが、データとしては取り出せないこと。

3.2 関数 Y1()と Y2()各々は一方向関数ではない_

式(20)の変換ペア{Y1(), Y2()}はハッシュ値 x1 をコードペア1, P2>に変換する:変換ペア{Y1(), Y2()} は鍵 Y をセットされた暗号関数と見える。その復号鍵が無いから、新しい一方向関数かも知れないと期待する。しかし、Y1()と Y2()各々は一方向関数に成らない:コード Y(x1)から x1 を取り出す方法 が有る:それが逆順のルートである。

(20-1):Y1(x1)が AES2 から AES1 へ移動すれば x1 が姿を現す:(20-2):Y2 (x1)が AES1 から AES2 へ移動すれば x1 が姿を現す。それで Y1()のバックドアを Y1-1()と表し、Y2()のバックドアを Y2-1()と 表すと、下記のようになる

x1= Y1-1(P1) ---------(21-1)
x1= Y2-1(P2) ---------(21-2)

バックドア(21)が有るので、逆向き計算が可能になる。

3.3 バックドアを塞ぐための「確率計算式」

コード P1 と P2 が「同期」して(21)に入ると、各々のバックドアが塞がれる:コード P1 と P2 の同期入力を1, P2>と表す。すると、コードペア1, P2>は x1 で「衝突」する。その他の任意のコード を{P1, P2}と表記すると、{P1, P2}は衝突しない。下記 Fig.2 は正確な図解である。

Fig.2: 確率計算式

図中、左側が1, P2>の衝突、右側が{P1, P2}の衝突である。衝突を検査する式が(22)である:

Y1-1(P1) =Y2-1(P2) =x1 ---------(22)

(22)に記入されたイコールはイコールにするペア1, P2>を求める代数式ではなく、x1 に衝突する か否かを検査せよ、というプログラム要件である。このように、衝突が確率=1 のイベントと確率 =1/2256 のイベントに分かれるので、(22)を確率計算式と言う。確率=1/2256 のイベントを起こす任意 コード{P1, P2}についてはハッシュ関数への第二原像攻撃と同じ動作になる:第二原像攻撃の場合は、 Birthday bound(2n/2 回の探索)で x1 に衝突する。

3.4 関数ペア{Y1(), Y2()}が一方向関数である、なぜなら、

任意コード{P1, P2}は確率=1/2256 の衝突を起こすが、コードペア1, P2>は確率=1 で衝突を起こす。 コードペア1, P2>を運用するアリスは確率=1 で x1 を手に入れるが、その他の人は入手できない。 したがって、アリス以外の人にとって、関数ペア{Y1(), Y2()}は一方向関数である:これを「知識分割」 と言う。このように「知識分割」は送信者アリスが行う。

知識分割は「全単射かつ一方向」の関数アンサンブル1(), Y2()...Yn()>である。確率計算式について は、天国へ通じる「針の孔」に喩えることが出来る: 1)所定のルールを守って来た者には、針の孔はたった 1 回の計算で「針の孔」を通過する。 2)所定のルールを守らなかった者には、針の孔は 2256 回の労働を課す。この 2256 回の労働は量子計算 機にも課せられる、なぜなら、量子計算機は「知識分割」に関与していないからである。

ここで特筆すべきことが有る:知識分割は一方向の暗号関数である一方、確率計算式にはコードペア1, P2>を x1 に復号する機能と認証する機能が有る:つまり、復号機能は認証機能を伴い、復号と 認証が一体である:知識分割はそういう内容を持っている。さらに、認証にも特筆すべきことが有る: 第三者の証明書に代わり、コード P1 と P2 が互いに他を認証する。それ故、PKI のような第三者基盤 が要らない。

3.5 公開鍵互換の PQC を見る準備

非可換アルゴリズムは、まず、
◆量子コンピュータに-2256 個の任意コード{P1, P2}を与える:言い換えると 2256 回の労働を課す。 次に、
◆知識分割は実装環境を選ばない。
三番目に、
◆それ自体は鍵配送を行えない。
四番目に、
◆確率計算式が与えられ、複数のコード1, P2...Pn>が互いに他を認証する。
五番目に、
◆知識分割の利用は従来のアプリケーションと互換ではない:従来のアプリケーションのセキュリ テイ・ホールを埋めて余りある。たとえば、
1) 1, P2>をパスワードとして運用する:➡「非対称パスワード」という。パスワードの理想を追い求める人が居れば、彼は非対称パスワードに100%満足するだろう。
2) 1, P2>と確率計算式でハッシュ値 x1 を再現する(➡衝突)。これで文書の改ざんを検証する:
その際、検証者は署名が唯一であることを検証する。
3) 知識分割サービスを2人以上、何人にも行える。➡社内データベースへのアクセス制御に最適

4. 上記、知識の体系から見た PQC

このように本ペーパは互換のアルゴリズムと鍵生成、そして前者の対極の非互換のアルゴリズムを 論じて来たが、筆者が立てた仮説は何も無い。1976 年に戻って、鍵配送の現実的なシナリオを公理 にして、首尾一貫して公理から定理を論じてきただけである。それで、互換と非互換はワンセットで あることが判る、丁度プラスが有ればマイナスも有るように。

先に、公開鍵互換である限り、PQC は鍵生成が「ウソ」をつかねばならないことを述べた:➡ see (16)。「ウソ」を許容するのはこの不等式(16)です。ここには PQC 標準を一つに絞る数学的な 基準は無く、複数になる方が理屈に叶う:賛否両論、欠点と長所を裁定する情報理論の支援が無い。 それで非可換アルゴリズムから手がかりを得たいと思った。

上記 3.5 から公開鍵互換 PQC を眺めると、PQC に期待したいことが出て来る:非可換アルゴリ ズムには出来ないことが有る、それは鍵交換です。特に、公衆網における鍵交換は可換アルゴリズムにしか出来ない。これについてはマニアックに考える必要は無い。ここから先は筆者の主観が混じる が、たとえば、Forward secrecy まで考えた鍵交換プロトコルを考える。このためには公開鍵は長い 時間「ウソ」をつかねばならない。利便性を犠牲にしてでも、公開鍵(PQC)が長い「うそ」をつく ことの方が重要である。もっと言えば、PQC の適用分野を広げる必要は無い。IoT のためには軽い PQC が必要だと仮定してみると、このような考え方が邪魔をして絞り込みが上手く行かなくなる。 というのは、私は IoT のための優れたプロトコルを知っており、それは勿論、量子耐性、かつ公開鍵 と独立なプロトコルです。以上、PQC の絞り込みの参考になれば幸いです。

May 30, 2019 EIJI WATANABE 全8ページ

謝意

本調査の論旨に下記の著作が多大な貢献をした。
CRYPTOGRAPHY by DOUGLAS R. STINSON The Code Book by Simon Singh

 

この記事の来歴
NIST へ提供した記事の日本語への翻訳

 
印刷用PDFはこちらからダウンロードできます