説明

暗号処理システム、暗号化装置、復号装置、及びプログラム、並びに暗号処理方法

【課題】鍵のビット長を短くでき、巨大素数を用意せずとも高い安全性を容易に実現可能な暗号化技術の提供。
【解決手段】暗号化装置は、N次元空間内の空間充填曲線の鍵曲線Hを複数記憶する鍵曲線記憶手段、鍵番号Kを復号装置と交換する鍵番号交換手段、メッセージ・コードをN次元空間に写像しメッセージ点Yを生成するメッセージ点生成手段、N次元空間の点Aを鍵曲線Hにより1次元序数空間の序数iに単射する関数をL(A)、その逆関数をL−1(i)とすると、点Yに基づきエンコード関数fを用いV=L−1[f(L(Y))]により点Vを算出する暗号コード生成手段を備え、復号装置は、鍵曲線記憶手段、鍵番号交換手段、及び点Vに基づき、Y=L−1[f−1(L(V))]によりメッセージ点Yを算出する復号演算手段を備えた。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、データ通信やデータの秘匿等に使用される暗号化技術に関し、特に、比較的短い鍵長でも高い安全性を実現することが可能な暗号化技術に関する。
【背景技術】
【0002】
秘匿データのデータ通信においては、従来からRSA暗号、Rabin暗号、ElGamal暗号、楕円曲線暗号などが広く用いられている。これらの各暗号方式は、基本的に、桁数が大きい合成数の素因数分解問題の計算困難性を利用して、高い安全性を確保するものである。
【先行技術文献】
【非特許文献】
【0003】
【非特許文献1】Sei-ichiro Kamata, Richard O. Eason, and Yukihiro Bandou, " A New Algorithm for N-Dimensional Hilbert Scanning ", IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 8, NO. 7, JULY 1999.
【非特許文献2】H.ザーガン,「空間充填曲線とフラクタル」,シュプリンガー・フェアラーク東京株式会社,1998年12月,pp.39-58.
【非特許文献3】J.A.ブーフマン,「暗号理論入門」,シュプリンガー・フェアラーク東京株式会社,2001年7月,pp.117-128.
【非特許文献4】黒澤馨、尾形わかは,「電子情報通信レクチャーシリーズD−8 現代暗号の基礎数理」,コロナ社,2004年3月,pp.161-166.
【発明の概要】
【発明が解決しようとする課題】
【0004】
しかしながら、これらの暗号方式では、高い安全性を確保するためには、秘密鍵として使用する巨大桁数の素数を用意する必要があるが、桁数が増えるほどこの素数の発見に困難が伴う。従って、簡便に使用することが難しい。また、それに伴い、公開鍵の桁数も大きくなり、通信などに於けるデータ量が増える。
【0005】
そこで、本発明の目的は、鍵のビット長を従来の暗号化方式よりも短くすることができるとともに、巨大素数を用意せずとも高い安全性を比較的容易に実現することが可能な暗号化技術を提供することにある。
【課題を解決するための手段】
【0006】
本発明に係る暗号処理システムの第1の構成は、入力される平文コードから暗号コードを生成する暗号化装置、及び前記暗号化装置が生成する前記暗号コードを復号して前記平文コードを復元する復号装置を備えた暗号処理システムであって、
前記暗号化装置は、
N次元整数空間内の所定の部分空間HCを充填する空間充填曲線である鍵曲線H(k=1,2,…)を複数記憶する鍵曲線記憶手段又は前記鍵曲線Hを生成する鍵曲線生成手段と、
入力される平文コードを前記N次元整数空間の部分空間HC内の点に単射して平文コード点Yを生成する平文コード点生成手段と、
鍵番号Kを共通鍵とし、前記平文コード点Yを鍵番号Kの前記鍵曲線Hにより一次元序数空間内の序数へ単射し、該序数を所定のエンコード関数により単射変換した後、前記鍵曲線Hにより前記N次元整数空間内の部分空間HC内の点へ逆単射する演算(以下「空間充填曲線暗号化演算」という。)を用いて前記暗号コードの生成を行う暗号コード生成手段と、を備え、
前記復号装置は、
前記暗号化装置と共通の鍵曲線H(k=1,2,…)を複数個記憶する鍵曲線記憶手段又は前記鍵曲線Hを生成する鍵曲線生成手段と、
前記鍵番号Kを共通鍵とし、前記暗号化装置により生成される、前記N次元整数空間の部分空間HC内の前記暗号コードを表す点を、前記鍵番号Kの前記鍵曲線Hにより一次元序数空間内の序数へ単射し、該序数を所定のデコード関数により単射変換した後、前記鍵曲線Hにより前記N次元整数空間内の部分空間HC内の点へ逆単射する演算(以下「空間充填曲線復号演算」という。)を用いて前記平文コードの復元を行う復号演算手段と、
を備えたことを特徴とする。
【0007】
この構成によれば、暗号化において、N次元空間充填曲線の鍵曲線Hを用いて、平文コード点Yを鍵曲線Hにより一次元序数空間内の序数へ単射し、該序数を所定のエンコード関数により単射変換した後、同じ鍵曲線HによりN次元整数空間内の部分空間HC内の点へ逆単射することで、非線形変換がなされ、強度の高い暗号コードを生成することができる。高次元においては、N次元整数空間の部分空間HCを充填する空間充填曲線の種数は極めて多くなるため、鍵番号Kの情報がなければ、総当たりによる暗号攻撃によって解読することは実質的に困難である。また、共通鍵として鍵番号Kがあれば充分であるため、従来のように巨大な桁数の素数などを必要とせず、各種通信装置やプログラムに容易に実装することが可能である。
【0008】
ここで、「N次元整数空間」とは、N個の整数値の組で表されるN次元の整数ベクトル(アドレス)により特定される離散格子点の集合からなるN次元離散空間をいう。「1次元序数空間」とは、N次元整数空間と1対1対応する1次元空間であって、序数により特定される離散点が1次元上に配列した空間である。
「空間充填曲線」とは、N次元整数空間内の所定の部分空間HCが与えられたときに、その部分空間HC内のすべての整数格子点を1回ずつ通過するような曲線をいう。空間充填曲線は、連続であるか不連続であるかは問わない。なお、本発明では使用する空間充填曲線の種類については特に限定する必要はないが、高次元の整数空間において大きな部分空間を充填する空間充填曲線を容易に生成するためには、空間充填曲線としては、ヒルベルト曲線やペアノ型曲線のような自己相似性を有する空間充填曲線を使用することが好適である。自己相似性を有する空間充填曲線であれば、小領域の部分空間を充填する空間充填曲線(種曲線)に基づいて、再帰的に大領域の部分空間を充填する空間充填曲線へ拡張させることが可能であるからである。また、この自己相似性を利用すれば、N次元空間から1次元序数空間への写像、及び1次元序数空間からN次元空間への逆写像が簡単且つ高速に実行することが可能となるからである。
また、エンコード関数、デコード関数としては、暗号コードから平文コードが復元可能な単射写像関数(スカラー関数)の組み合わせであれば、任意に選択して使用することができる。
【0009】
なお、本発明では、暗号化処理及び復号処理において、上記空間充填曲線暗号化演算及び空間充填曲線復号演算が用いられていればよく、これら空間充填曲線暗号化演算及び空間充填曲線復号演算を他の関数と組み合わせて暗号化処理及び復号処理を行うようにしてもよい。例えば、実施例1−3,5−7がその例である。
鍵番号Kについては、予め暗号化装置と復号装置との間で共通に保有しておくようにしてもよいし、暗号化通信を開始する前に別途暗号化して交換するようにしてもよい。
【0010】
本発明に係る暗号処理システムの第2の構成は、前記第1の構成において、前記N次元整数空間の部分空間HC内の点Aを、前記鍵曲線記憶手段に記憶された又は前記鍵曲線生成手段により生成される前記鍵番号Kの鍵曲線Hにより1次元序数空間内の序数iに単射する関数をL(A)、その逆関数をL−1(i)で表し、前記エンコード関数をf、前記デコード関数をgで表すと、
前記復号装置は、前記N次元整数空間の部分空間HC内の点である第一基準点Xを生成し、前記鍵番号Kを共通鍵として、前記第一基準点Xに基づき、前記鍵曲線H、及び前記エンコード関数fに可換な単射関数である前記デコード関数gを用いて、X=L−1[g(L(X))]により第二基準点Xを算出し、前記第一基準点X及び前記第二基準点Xを公開鍵として前記暗号化装置に公開する公開鍵生成手段を備え、
前記暗号コード生成手段は、前記鍵番号Kを共通鍵とし、前記平文コード点Yに基づき、前記鍵曲線記憶手段に記憶された又は前記鍵曲線生成手段により生成される前記鍵曲線H、単射関数である前記エンコード関数f、並びに前記復号装置により、公開鍵として公開される前記第一基準点X及び前記第二基準点Xを用いて、V=Y+L−1[f(L(X))],X=L−1[f(L(X))]により前記暗号コードとして暗号コード点V及び第三基準点Xを算出するものであり、
前記復号演算手段は、前記暗号コード生成手段から送信される前記暗号コード点V及び前記第三基準点Xに基づき、前記鍵曲線H及び前記デコード関数gを用いて、Y=V−L−1[g(L(X))]により前記平文コード点Yを算出するものであり、
前記復号装置は、前記平文コード点Yから前記平文コードを復元する平文コード復元手段を備えたことを特徴とする。
【0011】
この構成により、第一基準点X及び第二基準点Xを公開鍵として、公開鍵方式により平文コードの暗号化処理が可能となる。また、第二基準点X、第三基準点X、暗号コード点Vの生成においてN次元整数空間の空間充填曲線である鍵曲線Hを使用するため、次元数Nを十分に大きな値とすることにより、暗号解読が事実上殆ど不可能となり、安全性を高めることができる。
【0012】
ここで、エンコード関数fとデコード関数gが「可換」とは、合成関数f(g(x))と合成関数g(f(x))が等しくなることをいう。エンコード関数f及びデコード関数gとしては、例えば、f(x)=sx,g(x)=sx(s,sは定数)や、f(x)=xs1,g(x)=xs2(s,sは定数)や、f(x)=x+s,g(x)=x+s(s,sは定数)などがある。
【0013】
また、公開鍵を「公開する」とは、復号装置から暗号化装置に公開鍵を直接送信すること以外に、例えば、復号装置と暗号化装置がインターネットで接続されている場合には、インターネット上のいずれかのサイトに公開鍵をアップロードして暗号化装置から公開鍵をダウンロード可能な状態とすることも含まれる。
【0014】
また、上記本発明の前記第2の構成において、前記公開鍵生成手段は、前記第一基準点X及び所定の整数s並びに前記鍵曲線Hの長さ以下の所定の素数pに基づき、X=L−1[s(X) mod p]により前記第二基準点Xを算出し、これらの2点(X,X)を公開鍵として前記暗号化装置に公開するものとし、
前記暗号コード生成手段は、前記第一基準点X及び所定の整数s並びに前記素数pに基づき、X=L−1[s(X) mod p]により前記第三基準点Xを算出し、前記平文コード点Y、前記第二基準点X及び前記整数s並びに前記素数pに基づき、V=L−1[s(X)mod p]+Yにより前記暗号コード点Vを算出するものとし、
前記復号演算手段は、前記暗号コード点V及び前記整数s並びに前記素数pに基づき、Y=X−L−1[s(V)mod p] mod pにより平文コード点Yを算出するものとすることができる。
【0015】
この構成により、エンコード関数f及びデコード関数gを、基準点(X,X)及び基準点Xにより指定することができる。
【0016】
ここで、「所定の素数p」とは、任意に決められる素数をいい、鍵曲線Hの長さ以下のできるだけ大きな数に設定される。
【0017】
本発明に係る暗号処理システムの第3の構成は、前記第1の構成において、前記N次元整数空間の部分空間HC内の点Aを、前記鍵曲線記憶手段に記憶された又は前記鍵曲線生成手段により生成される前記鍵番号Kの鍵曲線Hにより1次元序数空間内の序数iに単射する関数をL(A)、その逆関数をL−1(i)で表し、前記エンコード関数をfで表すと、
前記暗号コード生成手段は、鍵番号Kを共通鍵とし、前記平文コード点Yに基づき、前記鍵曲線H及び単射関数である前記エンコード関数fを用いてV=L−1[f(L(Y))]により前記暗号コードとして暗号コード点Vを算出するものであり、
前記復号演算手段は、前記鍵番号Kを共通鍵とし、前記暗号コード点Vに基づき、前記鍵曲線記憶手段に記憶された又は前記鍵曲線生成手段により生成される前記鍵曲線H及び前記エンコード関数fの逆関数f−1である前記デコード関数を用いて、Y=L−1[f−1(L(V))]により平文コード点Yを算出するものであり、
前記復号装置は、前記平文コード点Yから前記平文コードを復元する平文コード復元手段を備えたことを特徴とする。
【0018】
この構成によれば、暗号化装置においては、平文コード点生成手段が平文コード点Yを生成し、暗号コード生成手段が、鍵曲線Hに基づき、V=L−1[f(L(Y))]により暗号コード点Vを算出する。この暗号コード点Vが暗号コードとして出力される。一方、復号装置においては、鍵曲線Hと暗号コード点Vに基づき、Y=L−1[f−1(L(V))]により平文コード点Yを算出することで、平文コードを復元する。このように、N次元整数空間の空間充填曲線である鍵曲線H用いることにより、平文コードの秘匿が図られる。N次元整数空間の空間充填曲線は、次元数Nの増加に伴って、その数は飛躍的に増加する。従って、次元数Nを十分に大きな値とすることにより、暗号解読が事実上殆ど不可能となり、安全性を高めることができる。
【0019】
本発明に係る暗号処理システムの第4の構成は、前記1乃至3の何れか一の構成において、前記暗号化装置及び前記復号装置の前記鍵曲線生成手段は、
前記各鍵曲線Hを発生する種となる、分割指数1のN次元空間充填曲線であるシード曲線Cが複数格納されたシード曲線テーブルを記憶するシード曲線記憶手段と、
始点及び終点の組合せが互いに異なる、分割指数1のN次元空間充填曲線からなるターミナル曲線を格納するターミナル・テーブル、並びにN次元空間充填曲線の分割時に前記ターミナル・テーブル内の各ターミナル曲線の各アドレスに対し連結するN次元空間充填曲線を特定するインデックス情報を格納するインダクション・テーブルを記憶する曲線演算テーブル記憶手段と、
前記鍵番号Kに対するシード曲線Cを前記シード曲線テーブルから読み出し、前記ターミナル・テーブルから、該シード曲線Cと始点及び終点が一致するターミナル曲線aξを索出し、前記ターミナル・テーブルの該ターミナル曲線aξを該シード曲線Cに置換するシード曲線設定手段と、
前記シード曲線Cが設定された前記ターミナル・テーブルに基づき、前記インダクション・テーブル内の各インデックス情報を設定するインダクション・テーブル生成手段と、
N次元整数空間内の点Aのアドレスが入力されると、前記シード曲線Cを前記ターミナル・テーブル及び前記インダクション・テーブルにより(M−1)回(Mは2以上の整数)分割して生成される前記鍵曲線Hにより、前記点Aを1次元序数空間に写像した序数iAを算出する1次元写像手段と、
前記鍵曲線H上の序数iAが入力されると、前記シード曲線Cを前記ターミナル・テーブル及び前記インダクション・テーブルにより(M−1)回分割して生成される前記鍵曲線Hにより、前記序数iAをN次元整数空間に写像した点Aを算出するN次元写像手段と、を備えており、
前記暗号コード生成手段は、前記1次元写像手段により前記平文コード点Yを鍵番号Kの前記鍵曲線Hにより一次元序数空間内の序数へ単射し、また、該序数を所定のエンコード関数により単射した後、前記N次元写像手段により前記鍵曲線Hにより前記N次元整数空間内の部分空間HC内の点へ逆単射するものであり、
前記復号演算手段は、前記1次元写像手段により前記暗号コードを表す点を、前記鍵番号Kの前記鍵曲線Hにより一次元序数空間内の序数へ単射し、また、該序数を所定のデコード関数により単射した後、前記N次元写像手段により前記鍵曲線Hにより前記N次元整数空間内の部分空間HC内の点へ逆単射するものであることを特徴とする。
【0020】
この構成によれば、暗号通信を実行する場合、まず、暗号化装置及び復号装置は、共通に入力されるパラメータM,N,Kによりターミナル・テーブルとインダクション・テーブルを構成する。ここで、N,M,Kは予め暗号化装置及び復号装置に与えられたものであってもよいし、暗号化装置及び復号装置の間で通信により交換したものであってもよい。この際、まず、ターミナル・テーブル初期化手段が、曲線演算テーブル記憶手段に格納されたターミナル・テーブルにターミナル曲線の初期値を設定し、次いで、シード曲線設定手段が、ターミナル・テーブルのターミナル曲線aξを該シード曲線Cに置換し、次いで、インダクション・テーブル生成手段が、シード曲線Cが設定されたターミナル・テーブルに基づき、曲線演算テーブル記憶手段に格納されたインダクション・テーブル内の各インデックス情報を設定する。これにより、暗号化装置及び復号装置の双方に、共通のターミナル・テーブル及びインダクション・テーブルが生成される。
このターミナル・テーブル及びインダクション・テーブルを用いることにより、分割指数1のシード曲線Cから分割指数Mの鍵曲線Hを算出することが可能となる。従って、ターミナル・テーブル及びインダクション・テーブルにより算出される鍵曲線Hを用いて暗号化演算や復号演算や各基準点の演算を行えば、N次元整数空間をより広く利用することができる。
【0021】
ここで、「平文コード」とは、通信する平文データをデジタル符号化したコードをいう。平文とは、暗号化されていない文(コード)をいう。
「分割指数」とは、1つのN次元超立方体の各辺をq個(qは基数)の区間に分割することによりqmN個の副超立方体に分割するときの、各辺の分割数qの指数mをいう。例として、図7(c)に分割指数1,1,2の2次元ヒルベルト曲線を示す。なお、基数qは2以上の整数であり、空間充填曲線の種類によって決まる数である。例えば、N次元ヒルベルト曲線の場合にはq=2,N次元3進ペアノ型曲線の場合にはq=3,N次元5進ペアノ型曲線の場合にはq=5となる。
「シード曲線」とは、分割指数1のN次元空間充填曲線であって、ターミナル・テーブル及びインダクション・テーブルにより分割指数MのN次元空間充填曲線を発生させる際の種(シード)となるものをいう。
「インデックス情報」とは、ターミナル・テーブル内の各ターミナル曲線の各アドレスに対し連結するターミナル曲線を特定するためのインデックスの情報をいう。例えば、ターミナル・テーブル内の各ターミナル曲線ak1,N=(ak1,N(1),…,ak1,N(2))(但し、ak1,N(i)(i=1,…,2)はNビットのアドレス)のアドレスak1,N(i)に連結するターミナル曲線をak'1,Nとすると、当該ターミナル曲線ak'1,Nを特定するためのインデックス情報はk’である。
「鍵曲線H上の序数」とは、鍵曲線H上のアドレスの順番を表す数である。例えば、鍵曲線Hのアドレス・シーケンスをH=(hK(1),hK(2),…,hK(2MN))とし、点AがアドレスhK(iA),点BがアドレスhK(iB)に対応するとすれば、点A,Bの鍵曲線H上の序数は、それぞれiA,iBである。
【0022】
また、本発明において、前記ターミナル・テーブルを初期化するターミナル・テーブル初期化手段として、
1次元のターミナル曲線a11,1を(0,1)に設定し、n次元(n=2,…,N)のターミナル曲線a11,nを、(n−1)次元のターミナル曲線a11,(n-1)に基づき、
【0023】
【数1】

により順次生成することにより1番目のターミナル曲線a11,Nを生成する初期ターミナル曲線生成手段と、
1番目のターミナル曲線a11,Nに基づき、(N(i−1)+j)番目(i=1,…,2N−1;j=1,…,N)のターミナル曲線a(N(i-1)+j)1,Nの始点アドレスa(N(i-1)+j)1,N(1)を、1番目のターミナル曲線a1,Nの(2i−1)番目のアドレスa11,N(2i−1)に設定する始点アドレス設定手段と、
1番目のターミナル曲線a11,Nに基づき、(N(i−1)+j)番目(i=1,…,2N−1;j=1,…,N)のターミナル曲線a(N(i-1)+j)1,Nの終点アドレスa(N(i-1)+j)1,N(2)を、1番目のターミナル曲線a11,Nの(2i−1)番目のアドレスa11,N(2i−1)のj番目のビットを反転させたアドレスibit(a11,N(2i−1),j)に設定する終点アドレス設定手段と、
1番目のターミナル曲線a11,Nに基づき、k番目(k=1,…,N)のターミナル曲線ak1,Nのi’番目(i’=2,…,2N−1)の中間点アドレスak1,N(i’)を、
【0024】
【数2】

により設定する第1の中間点アドレス生成手段と、
1番目からN番目の前記ターミナル曲線a11,N,…,aN1,Nに基づき、(Ni+j)番目(i=1,…,2N-1−1;j=1,…,N)のターミナル曲線aNi+j1,Nのi’番目(i’=2,…,2N−1)の中間点アドレスak1,N(i’)を、
【0025】
【数3】

により設定する第2の中間点アドレス生成手段と、を備えた構成とすることができる。
【0026】
この構成によれば、ターミナル・テーブル初期化手段がターミナル・テーブルを初期化する際に、まず、初期ターミナル曲線生成手段が、1次元のターミナル曲線a11,1を(0,1)に設定し、n次元(n=2,…,N)のターミナル曲線a11,nを、(数1)により順次生成することにより1番目のターミナル曲線a11,Nを生成する。次いで、始点アドレス設定手段が、ターミナル曲線a11,Nに基づき、(N(i−1)+j)番目(i=1,…,2N−1;j=1,…,N)のターミナル曲線a(N(i-1)+j)1,Nの始点アドレスa(N(i-1)+j)1,N(1)をアドレスa11,N(2i−1)に設定する。次いで、終点アドレス設定手段が、ターミナル曲線a11,Nに基づき、(N(i−1)+j)番目(i=1,…,2N−1;j=1,…,N)のターミナル曲線a(N(i-1)+j)1,Nの終点アドレスa(N(i-1)+j)1,N(2)を、アドレスibit(a11,N(2i−1),j)に設定する。次いで、第1の中間点アドレス生成手段が、ターミナル曲線a11,Nに基づき、k番目(k=1,…,N)のターミナル曲線ak1,Nのi’番目(i’=2,…,2N−1)の中間点アドレスak1,N(i’)を、(数2)により設定する。最後に、第2の中間点アドレス生成手段が、ターミナル曲線a11,N,…,aN1,Nに基づき、(Ni+j)番目(i=1,…,2N-1−1;j=1,…,N)のターミナル曲線aNi+j1,Nのi’番目(i’=2,…,2N−1)の中間点アドレスak1,N(i’)を、(数3)により設定する。これにより、ターミナル・テーブルに初期値を設定することができる。
【0027】
また、本発明において、前記インダクション・テーブル生成手段は、
前記ターミナル・テーブルを参照して、N次元空間充填曲線の分割時に、k番目(k=1,…,N2)のターミナル曲線ak1,Nの始点アドレスak1,N(1)に連結するN次元空間充填曲線のインデックス情報wk1,N(1)を設定する始点連結情報設定手段と、
前記インデックス情報wk1,N(1)が設定された後、前記ターミナル・テーブルを参照して、前記ターミナル曲線ak1,Nの中間点アドレスak1,N(i’)(i’=2,…,2N−1)に連結するN次元空間充填曲線のインデックス情報wk1,N(i’)を設定する中間点連結情報設定手段と、
前記各インデックス情報wk1,N(i’)(i’=2,…,2N−1)が設定された後、前記ターミナル・テーブルを参照して、前記ターミナル曲線ak1,Nの終点アドレスak1,N(2)に連結するN次元空間充填曲線のインデックス情報wk1,N(2)を設定する終点連結情報設定手段と、を備え、
前記始点連結情報設定手段は、始点アドレスak1,N(1)に対し、連結曲線の始点アドレスsをターミナル曲線ak1,Nの始点アドレスak1,N(1)に設定し、連結曲線の終点アドレスeを
【0028】
【数4】

に設定し、前記ターミナル・テーブルから、始点アドレスが該始点アドレスsと一致し且つ終点アドレスが該終点アドレスeと一致するターミナル曲線ak*1,Nを索出し、該ターミナル曲線ak*1,Nのインデックス情報kを、前記インデックス情報wk1,N(1)に設定するものであり、
前記中間点連結情報設定手段は、中間点アドレスak1,N(2i−2),ak1,N(2i−1)(i=2,…,2N−1)に対し、連結曲線の始点アドレスsを
【0029】
【数5】

に変更し、連結曲線の終点アドレスeを
【0030】
【数6】

に変更し、前記ターミナル・テーブルから、始点アドレスが該始点アドレスsと一致し且つ終点アドレスが該終点アドレスeと一致するターミナル曲線ak*1,Nを索出し、該ターミナル曲線ak*1,Nのインデックス情報kを、前記インデックス情報wk1,N(2i−2),wk1,N(2i−1)に設定する処理を、iの昇順に順次実行するものであり、
前記終点連結情報設定手段は、終点アドレスak1,N(2)に対し、連結曲線の始点アドレスsを
【0031】
【数7】

に設定し、連結曲線の終点アドレスeをターミナル曲線ak1,Nの終点アドレスak1,N(2)に設定し、前記ターミナル・テーブルから、始点アドレスが該始点アドレスsと一致し且つ終点アドレスが該終点アドレスeと一致するターミナル曲線ak*1,Nを索出し、該ターミナル曲線ak*1,Nのインデックス情報kを、前記インデックス情報wk1,N(2)に設定するように構成することができる。
【0032】
この構成によれば、インダクション・テーブル生成手段がインダクション・テーブルの作成を行う場合、まず、始点連結情報設定手段が、始点アドレスsをアドレスak1,N(1)に設定し、連結曲線の終点アドレスeを(数4)により設定し、ターミナル・テーブルから、始点アドレスak*1,N(1)が該始点アドレスsと一致し且つ終点アドレスak*1,N(2)が該終点アドレスeと一致するターミナル曲線ak*1,Nを索出し、該ターミナル曲線ak*1,Nのインデックス情報kを、前記インデックス情報wk1,N(1)に設定する。次に、中間点連結情報設定手段が、中間点アドレスak1,N(2i−2),ak1,N(2i−1)(i=2,…,2N−1)に対し、連結曲線の始点アドレスsを(数5)により変更し、連結曲線の終点アドレスeを(数6)により変更し、ターミナル・テーブルから、始点アドレスak*1,N(1)が該始点アドレスsと一致し且つ終点アドレスak*1,N(2)が該終点アドレスeと一致するターミナル曲線ak*1,Nを索出し、該ターミナル曲線ak*1,Nのインデックス情報kを、インデックス情報wk1,N(2i−2),wk1,N(2i−1)に設定する処理を、iの昇順に順次実行する。次に、終点連結情報設定手段が、終点アドレスak1,N(2)に対し、連結曲線の始点アドレスsを(数7)により設定し、連結曲線の終点アドレスeをアドレスak1,N(2)に設定し、ターミナル・テーブルから、始点アドレスak*1,N(1)が該始点アドレスsと一致し且つ終点アドレスak*1,N(2)が該終点アドレスeと一致するターミナル曲線ak*1,Nを索出し、該ターミナル曲線ak*1,Nのインデックス情報kを、インデックス情報wk1,N(2)に設定する。これにより、N次元空間充填曲線の分割時に前記ターミナル・テーブル内の各ターミナル曲線の各アドレスに対し連結するターミナル曲線を特定するインデックス情報を作成することができる。
【0033】
本発明に係る暗号化装置の第1の構成は、入力される平文コードから暗号コードを生成する暗号化装置であって、
N次元整数空間内の所定の部分空間HCを充填する空間充填曲線である鍵曲線H(k=1,2,…)を複数記憶する鍵曲線記憶手段又は前記鍵曲線Hを生成する鍵曲線生成手段と、
入力される平文コードを前記N次元整数空間の部分空間HC内の点に写像して平文コード点Yを生成する平文コード点生成手段と、
鍵番号Kを共通鍵とし、前記平文コード点Yを鍵番号Kの前記鍵曲線Hにより一次元序数空間内の序数へ単射し、該序数を所定のエンコード関数により単射変換した後、前記鍵曲線Hにより前記N次元整数空間内の部分空間HC内の点へ逆単射する演算を用いて暗号化を行う暗号コード生成手段と、を備えたことを特徴とする。
【0034】
この構成により、本発明に係る上記暗号化通信システムの第1の構成において用いることのできる暗号化装置が実現される。
【0035】
本発明に係る暗号化装置の第2の構成は、前記N次元整数空間の部分空間HC内の点Aを、前記鍵曲線記憶手段に記憶された又は前記鍵曲線生成手段により生成される前記鍵番号Kの鍵曲線Hにより1次元序数空間内の序数iに単射する関数をL(A)、その逆関数をL−1(i)で表し、前記エンコード関数をfで表すと、
前記暗号コード生成手段は、鍵番号Kを共通鍵とし、前記平文コード点Yに基づき、前記鍵曲線記憶手段に記憶された又は前記鍵曲線生成手段により生成される前記鍵曲線H、単射関数である前記エンコード関数f、並びに公開鍵として公開されている前記N次元整数空間の部分空間HC内の点である第一基準点X及び第二基準点Xを用いて、V=Y+L−1[f(L(X))],X=L−1[f(L(X))]により前記暗号コードとして暗号コード点V及び第三基準点Xを算出するものであることを特徴とする。
【0036】
この構成により、本発明に係る上記暗号化通信システムの第2の構成において用いることのできる暗号化装置が実現される。
【0037】
本発明に係る暗号化装置の第3の構成は、前記N次元整数空間の部分空間HC内の点Aを、前記鍵曲線記憶手段に記憶された又は前記鍵曲線生成手段により生成される前記鍵番号Kの鍵曲線Hにより1次元序数空間内の序数iに単射する関数をL(A)、その逆関数をL−1(i)で表し、前記エンコード関数をfで表すと、
前記暗号コード生成手段は、鍵番号Kを共通鍵とし、前記平文コード点Yに基づき、前記鍵曲線H及び単射関数である前記エンコード関数fを用いてV=L−1[f(L(Y))]により前記暗号コードとして暗号コード点Vを算出することを特徴とする。
【0038】
この構成により、本発明に係る上記暗号化通信システムの第3の構成において用いることのできる暗号化装置が実現される。
【0039】
本発明に係る復号装置の第1の構成は、前記第1の構成の暗号化装置により生成される暗号コードを復号し平文コードを復元する復号装置であって、前記暗号化装置と共通の鍵曲線H(k=1,2,…)を複数個記憶する鍵曲線記憶手段又は前記鍵曲線Hを生成する鍵曲線生成手段と、
前記暗号化装置において共通鍵として使用した鍵番号と共通の鍵番号Kを共通鍵とし、前記暗号化装置により生成される、前記N次元整数空間の部分空間HC内の暗号コードを表す点を、前記鍵曲線Hにより一次元序数空間内の序数へ単射し、該序数を所定のデコード関数により単射変換した後、前記鍵曲線Hにより前記N次元整数空間内の部分空間HC内の点へ逆単射する演算を用いて前記平文コードの復元を行う復号演算手段と、を備えたことを特徴とする。
【0040】
この構成により、本発明に係る上記暗号化通信システムの第1の構成において用いることのできる復号装置が実現される。
【0041】
本発明に係る復号装置の第2の構成は、前記第2の構成の暗号化装置により生成される暗号コードを復号し平文コードを復元する前記第1の構成の復号装置であって、
前記N次元整数空間の部分空間HC内の点Aを、前記鍵曲線記憶手段に記憶された又は前記鍵曲線生成手段により生成される前記鍵番号Kの鍵曲線Hにより1次元序数空間内の序数iに単射する関数をL(A)、その逆関数をL−1(i)で表し、前記暗号化装置で使用されるエンコード関数をf、前記デコード関数をg、前記暗号化装置が前記暗号コードとして生成する暗号コード点をV,第三基準点をXで表すと、
前記N次元整数空間の部分空間HC内の点である第一基準点Xを生成し、前記鍵番号Kを共通鍵として、前記第一基準点Xに基づき、前記鍵曲線H、及び前記エンコード関数fに可換な単射関数である前記デコード関数gを用いて、X=L−1[g(L(X))]により第二基準点Xを算出し、前記第一基準点X及び前記第二基準点Xを公開鍵として前記暗号化装置に公開する公開鍵生成手段を備え、
前記復号演算手段は、前記暗号コード点V及び前記第三基準点Xに基づき、前記鍵曲線H及び前記デコード関数gを用いて、Y=V−L−1[g(L(X))]により前記平文コード点Yを算出するものであり、
前記平文コード点Yから前記平文コードを復元する平文コード復元手段を備えたことを特徴とする。
【0042】
この構成により、本発明に係る上記暗号化通信システムの第2の構成において用いることのできる復号装置が実現される。
【0043】
本発明に係る復号装置の第3の構成は、前記第3の構成の暗号化装置により生成される暗号コードを復号し平文コードを復元する前記第1の構成の復号装置であって、
前記N次元整数空間の部分空間HC内の点Aを、前記鍵曲線記憶手段に記憶された又は前記鍵曲線生成手段により生成される前記鍵番号Kの鍵曲線Hにより1次元序数空間内の序数iに単射する関数をL(A)、その逆関数をL−1(i)で表し、前記暗号化装置で使用されるエンコード関数をf、前記暗号化装置が前記暗号コードとして生成する暗号コード点をVで表すと、
前記復号演算手段は、前記鍵番号Kを共通鍵とし、前記暗号コード点Vに基づき、前記鍵曲線記憶手段に記憶された又は前記鍵曲線生成手段により生成される前記鍵曲線H及び前記エンコード関数fの逆関数f−1である前記デコード関数を用いて、Y=L−1[f−1(L(V))]により平文コード点Yを算出するものであり、
前記復号装置は、前記平文コード点Yから前記平文コードを復元する平文コード復元手段を備えたことを特徴とする。
【0044】
この構成により、本発明に係る上記暗号化通信システムの第2の構成において用いることのできる復号装置が実現される。
【0045】
本発明に係るプログラムの第1の構成は、コンピュータに読み込ませて実行することにより、コンピュータを前記第1乃至3の何れか一の構成の暗号化装置として機能させることを特徴とする。
【0046】
また、本発明に係るプログラムの第2の構成は、コンピュータに読み込ませて実行することにより、コンピュータを前記第1乃至3の何れか一の構成の復号装置として機能させることを特徴とする。
【0047】
本発明に係る暗号処理方法の第1の構成は、電気通信回線で接続された暗号化装置及び復号装置の間において、前記暗号化装置から平文コードを暗号化した暗号コードを送信し、前記復号装置において前記暗号コードを受信して復号し前記平文コードを復元する暗号処理方法であって、
前記暗号化装置及び前記復号装置は、N次元整数空間内の所定の部分空間HCを充填する空間充填曲線である鍵曲線H(k=1,2,…)を複数記憶する鍵曲線記憶手段又は前記鍵曲線Hを生成する鍵曲線生成手段を共通に備えており、
前記暗号化装置において、入力される平文コードを前記N次元整数空間の部分空間HC内の点に写像して平文コード点Yを生成する平文コード点生成ステップと、
前記暗号化装置において、鍵番号Kを共通鍵とし、前記平文コード点Yを鍵番号Kの前記鍵曲線Hにより一次元序数空間内の序数へ単射し、該序数を所定のエンコード関数により単射変換した後、前記鍵曲線Hにより前記N次元整数空間内の部分空間HC内の点へ逆単射する演算を用いて暗号化を行う暗号コード生成ステップと、
前記復号装置において、前記鍵番号Kを共通鍵とし、前記暗号化装置により生成される、前記N次元整数空間の部分空間HC内の暗号コードを表す点を、前記鍵番号Kの前記鍵曲線Hにより一次元序数空間内の序数へ単射し、該序数を所定のデコード関数により単射変換した後、前記鍵曲線Hにより前記N次元整数空間内の部分空間HC内の点へ逆単射する演算を用いて前記平文コードの復元を行う復号演算ステップと、を備えたことを特徴とする。
【0048】
本発明に係る暗号処理方法の第2の構成は、前記第1の構成において、前記N次元整数空間の部分空間HC内の点Aを、前記鍵曲線記憶手段に記憶された又は前記鍵曲線生成手段により生成される前記鍵番号Kの鍵曲線Hにより1次元序数空間内の序数iに単射する関数をL(A)、その逆関数をL−1(i)で表し、前記エンコード関数をf、前記デコード関数をgで表すと、
前記復号装置が、前記N次元整数空間の部分空間HC内の点である第一基準点Xを生成し、前記鍵番号Kを共通鍵として、前記第一基準点Xに基づき、前記鍵曲線H、及び前記エンコード関数fに可換な単射関数である前記デコード関数gを用いて、X=L−1[g(L(X))]により第二基準点Xを算出し、前記第一基準点X及び前記第二基準点Xを公開鍵として前記暗号化装置に公開する公開鍵生成ステップを有し、
前記暗号コード生成ステップにおいては、前記暗号化装置において、前記鍵番号Kを共通鍵とし、前記平文コード点Yに基づき、前記鍵曲線記憶手段に記憶された又は前記鍵曲線生成手段により生成される前記鍵曲線H、単射関数である前記エンコード関数f、並びに前記復号装置により、公開鍵として公開される前記第一基準点X及び前記第二基準点Xを用いて、V=Y+L−1[f(L(X))],X=L−1[f(L(X))]により前記暗号コードとして暗号コード点V及び第三基準点Xを算出し前記復号装置へ送信する処理が実行され、
前記復号演算ステップにおいては、前記復号装置において、前記暗号化装置から送信される前記暗号コード点V及び前記第三基準点Xに基づき、前記鍵曲線H及び前記デコード関数gを用いて、Y=V−L−1[g(L(X))]により前記平文コード点Yを算出し、前記平文コード点Yから前記平文コードを復元する処理が実行されることを特徴とする。
【0049】
本発明に係る暗号処理方法の第3の構成は、前記第1の構成において、前記N次元整数空間の部分空間HC内の点Aを、前記鍵曲線記憶手段に記憶された又は前記鍵曲線生成手段により生成される前記鍵番号Kの鍵曲線Hにより1次元序数空間内の序数iに単射する関数をL(A)、その逆関数をL−1(i)で表し、前記エンコード関数をfで表すと、
前記暗号コード生成ステップにおいては、前記暗号化装置において、鍵番号Kを共通鍵とし、前記平文コード点Yに基づき、前記鍵曲線H及び単射関数である前記エンコード関数fを用いてV=L−1[f(L(Y))]により前記暗号コードとして暗号コード点Vを算出し前記復号装置へ送信する処理が実行され、
前記復号演算ステップにおいては、前記復号装置において、前記鍵番号Kを共通鍵とし、前記暗号化装置から送信される前記暗号コード点Vに基づき、前記鍵曲線記憶手段に記憶された又は前記鍵曲線生成手段により生成される前記鍵曲線H及び前記エンコード関数fの逆関数f−1である前記デコード関数を用いて、Y=L−1[f−1(L(V))]により平文コード点Yを算出し、前記平文コード点Yから前記平文コードを復元する処理が実行されることを特徴とする。
【発明の効果】
【0050】
以上のように、本発明によれば、鍵番号Kを共通鍵として使用して、鍵番号Kの鍵曲線Hを秘密鍵に使用し、この鍵曲線HによりN次元整数空間内の点を1次元序数空間内の序数に単射し、1次元序数空間内でエンコードやデコード演算を行い、その結果を鍵曲線Hにより再びN次元整数空間内の点に単射する演算を用いて暗号化や復号を行うことによって、従来よりも短い鍵(鍵番号K)とすることができる。また、鍵曲線Hの次元数Nを6以上とすれば、選択可能な鍵曲線Hの種類の数は極めて大きな値となるため、鍵曲線Hの情報なくしては復号が困難となり、高い頑健性を実現することができる。また、RSA暗号方式にように、巨大な素数を必要としないため、比較的容易に本発明の暗号化方式を実施することが可能となる。
【図面の簡単な説明】
【0051】
【図1】本発明の実施例1に係る暗号処理システムの全体構成を示す図である。
【図2】暗号処理装置2の暗号化機能部分の機能構成を表すブロック図である。
【図3】暗号処理装置2の復号機能部分の機能構成を表すブロック図である。
【図4】シード曲線テーブルの構造を表す図である。
【図5】ターミナル・テーブルの構造を表す図である。
【図6】インダクション・テーブルの構造を表す図である。
【図7】2次元,3次元ヒルベルト曲線のアドレス順序の例である。
【図8】暗号処理システム1による暗号化装置2e(メッセージ送信側の暗号処理装置2)と復号装置2d(メッセージ受信側の暗号処理装置2)との間の暗号化通信の動作を表すフローチャートである。
【図9】N次元空間点と分割指数mのN次元のヒルベルト曲線との1対1対応関係を示す図である。
【図10】鍵番号Kの交換動作を表すフローチャートである。
【図11】各曲線演算テーブルの設定方法の全体動作を表すフローチャートである。
【図12】ターミナル・テーブル初期化部13によるターミナル・テーブルの初期値の設定処理を表すフローチャートである。
【図13】ターミナル・テーブル初期化部13による逆ターミナル・テーブルの初期値の設定処理を表すフローチャートである。
【図14】インダクション・テーブル生成部15によるインダクション・テーブルの作成処理を表すフローチャートである。
【図15】本発明の実施例2に係る暗号化装置2e(メッセージ送信側の暗号処理装置2)の構成を表すブロック図である。
【図16】本発明の実施例2に係る復号装置2d(メッセージ受信側の暗号処理装置2)の構成を表すブロック図である。
【図17】実施例2で使用する空間充填曲線(2次元)の例を表す図である。(a)ペアノ曲線、(b)シェルピンスキー曲線、(c)ムーア曲線
【図18】実施例2の暗号処理システム1による暗号化装置2e(メッセージ送信側の暗号処理装置2)と復号装置2d(メッセージ受信側の暗号処理装置2)との間の暗号化通信の全体動作を表すフローチャートである。
【図19】本発明の実施例3に係る暗号化装置2e(メッセージ送信側の暗号処理装置2)の構成を表すブロック図である。
【図20】本発明の実施例3に係る復号装置2d(メッセージ受信側の暗号処理装置2)の構成を表すブロック図である。
【図21】実施例3の暗号処理システム1による暗号化装置2e(メッセージ送信側の暗号処理装置2)と復号装置2d(メッセージ受信側の暗号処理装置2)との間の暗号化通信の全体動作を表すフローチャートである。
【図22】写像f(2,n):[0,32n]→[0,3によって生成される2次元ペアノ曲線の一例を示す図である。
【図23】写像f(3,n):[0,33n]→[0,3によって生成される3次元ペアノ曲線の一例を示す図である。
【図24】式(43a),(43b)による分割指数nのN次元q進ペアノ型曲線の生成方法を具体的に示したフローチャートである。
【図25】2次元5進ペアノ型曲線の例を示す図である。
【図26】2次元7進ペアノ型曲線の例を示す図である。
【図27】N次元q進ペアノ型曲線C(n,N)のターミナル・テーブルの計算アルゴリズムを示すPAD図である。
【図28】N次元q進ペアノ型曲線C(n,N)のインダクション・テーブルの計算アルゴリズムを示すPAD図である。
【図29】DES方式による暗号化アルゴリズムの流れを示すブロック図である。
【図30】内部ブロック暗号Fのアルゴリズムの流れを示すブロック図である。
【図31】巡回鍵Kの生成アルゴリズムの流れを示すブロック図である。
【図32】DES暗号の復号アルゴリズムの流れを示すブロック図である。
【図33】DES暗号化方式に本発明を適用した暗号化方式(実施例5)のアルゴリズムの流れを示すブロック図である。
【図34】DES暗号化方式に本発明を適用した復号方式(実施例5)のアルゴリズムの流れを示すブロック図である。
【図35】実施例5に係る暗号処理装置の構成を表すブロック図である。
【図36】図35における内部ブロック関数G演算部50の構成を表すブロック図である。
【図37】AES方式による暗号化アルゴリズムの流れを示すブロック図である。
【図38】図37の各ラウンド関数RFにおける暗号処理アルゴリズムを表すブロック図である。
【図39】AES方式による復号アルゴリズムの流れを示すブロック図である。
【図40】図39の各ラウンド関数RF−1における暗号処理アルゴリズムを表すブロック図である。
【図41】実施例6の暗号化アルゴリズムにおける各ラウンド関数RFのアルゴリズムのブロック図である。
【図42】実施例6の復号アルゴリズムにおける各ラウンド関数RF−1のアルゴリズムのブロック図である。
【図43】実施例6の暗号処理装置の構成を表すブロック図である。
【発明を実施するための形態】
【0052】
〔用語の定義〕
最初に、以下で使用する用語の概念を明確にするために、いくつかの用語について定義しておく。
(定義1)〔空間充填曲線〕
N次元空間内の一辺の長さがnの単位超立方体を考える。この超立方体の各辺を(n−1)区間に分割し、n×n個の整数格子点からなる超立方体格子としたとき、当該超立方体格子内のすべての整数格子点を1点につき1回通過するような曲線を「空間充填曲線」という。
(定義終り)
【0053】
(定義2)〔連続空間充填曲線〕
N次元空間における空間充填曲線C(N)について、当該空間充填曲線C(N)が充填する超立方体格子の格子点間のユークリッド距離は1である。曲線C(N)上のi番目の整数格子点P(N)と(i+1)番目の整数格子点Pi+1(N)との間のユークリッド距離を「隣接点間距離」とする。曲線上のすべての整数格子点間の隣接点間距離がすべて1である空間充填曲線を「連続空間充填曲線」いい、連続空間充填曲線でない空間充填曲線を「不連続空間充填曲線」という。
(定義終り)
【0054】
次に、本発明を実施するための形態について、図面を参照しながら説明する。
【実施例1】
【0055】
〔1〕暗号処理システムの構成
(1)システムの全体構成
図1は、本発明の実施例1に係る暗号処理システムの全体構成を示す図である。暗号処理システム1は、複数の暗号処理装置2が、イントラネットやインターネット等の通信ネットワーク3を介して、互いに通信可能に接続された構成を有する。
【0056】
各暗号処理装置2は、内部構成として、共通モジュール4、暗号コード生成モジュール5、復号モジュール6、通信インタフェース7、平文コード入力部8、及び平文コード出力部9を備えている。尚、各暗号処理装置2は、ハードウェア的に暗号化通信の専用装置として構成することも可能であるが、パーソナル・コンピュータ等の汎用のコンピュータにプログラムをロードして実行することによりソフトウェア的に暗号処理装置2を実現するようにしてもよい。
【0057】
(2)暗号処理装置の内部構成
図2は、暗号処理装置2の暗号化機能部分の機能構成を表すブロック図である。以下では、通信する平文コードを暗号化して送信する側の暗号処理装置2を暗号化装置2e、当該平文コードを受信して復号する側の暗号処理装置2を復号装置2dと呼ぶ。
【0058】
暗号化装置2eは、共通モジュール4、暗号コード生成モジュール5、通信インタフェース7、及び平文コード入力部8を備え、これらは図1の同符号の構成部分に対応している。
【0059】
平文コード入力部8は、送信する平文コードを入力する構成部分である。平文コード入力部8は、キーボード等のヒューマン・インタフェースや、CD−ROM,DVD−ROM,メモリ・スティック,ハードディスク等の平文コードが記憶された各種記憶装置から構成される。
【0060】
共通モジュール4は、シード曲線テーブル記憶部11、曲線演算テーブル記憶部12、ターミナル・テーブル初期化部13、シード曲線設定部14、インダクション・テーブル生成部15、曲線上演算部16、及びパラメータ交換部17を備えている。
【0061】
パラメータ交換部17は、復号装置2dとの間で、分割指数M,次元数N,素数p,及び鍵番号Kの交換を行う。
【0062】
シード曲線テーブル記憶部11は、分割指数1のN次元(Nは2以上の整数)ヒルベルト曲線からなるシード曲線を複数種類格納したシード曲線テーブルを記憶する。尚、各暗号処理装置2のシード曲線テーブル記憶部11には、共通のシード曲線テーブルが、予め記憶されているものとする。
【0063】
図4に、シード曲線テーブルの構造を示す。1つのシード曲線C(i=1,2,…)は、分割指数1のN次元のヒルベルト曲線(ci1,N(1),ci1,N(2),…,ci1,N(2N))から構成される。ここで、ci1,N(k)(k=1.…,2)は、Nビットのビット配列からなるアドレスである。分割指数1のN次元のヒルベルト曲線は、2N個のアドレス・シーケンスからなる。シード曲線テーブルには、互いに異なるN個のシード曲線C(i=1,2,…,N)が格納されている。Nは、シード曲線の組合せ総数以下の数に設定されるが、できるだけ大きな数に設定される。
【0064】
例えば、2次元(N=2)の場合には、始点ci1,2(1)と終点ci1,2(4)を固定すれば、シード曲線の数は1通りに決まってしまう。例えば、始点ci1,2(1)を00,終点ci1,2(4)を10とした場合、シード曲線は(00,01,11,10)となる。
【0065】
しかし、3次元の場合には、始点ci1,3(1)と終点ci1,3(8)を固定すると、シード曲線の組合せ総数は4通りとなる。次元数をさらに上げると、4次元(N=4)の場合には、始点ci1,4(1)と終点ci1,4(16)を固定したときのシード曲線の組合せ総数は627通り、5次元(N=5)の場合には、始点ci1,5(1)と終点ci1,5(32)を固定したときのシード曲線の組合せ総数は151,732,224通りとなり、次元数Nの増加とともにシード曲線の組合せ総数は急激に増加する。一般にN次元の場合において、始点ci1,N(1)と終点ci1,N(2)を固定したときのシード曲線の組合せ総数F(N)がどのような式で表されるかは、現在のところ分かっていないが、本発明者が計算機による数え上げにより求めた近似結果では、
【0066】
【数8】

となることが分かっている。従って、この特徴を用いて、6次元以上のヒルベルト曲線を利用すれば、使用可能なシード曲線の組合せ総数F(N)は極めて大きな値となるため、秘密鍵としてこのシード曲線を使用すれば、国際標準化RSA暗号方式や楕円暗号方式よりも頑健性の高い暗号方式を構成することが可能となる。
【0067】
曲線演算テーブル記憶部12は、ターミナル・テーブル、インダクション・テーブル、及び逆ターミナル・テーブルを記憶する。ここで、ターミナル・テーブルは、始点及び終点の組合せが互いに異なる、分割指数1のN次元ヒルベルト曲線からなるターミナル曲線を、N2N−1個格納するルックアップ・テーブルである。インダクション・テーブルは、N次元ヒルベルト曲線の分割時に前記ターミナル・テーブル内の各ターミナル曲線の各アドレスに対し連結するターミナル曲線を特定するインデックス情報を格納するルックアップ・テーブルである。逆ターミナル・テーブルは、ターミナル・テーブルの逆演算を行うためのルックアップ・テーブルである。基本的には、ターミナル・テーブルとインダクション・テーブルを用いれば、任意の分割指数のN次元ヒルベルト曲線を発生させることができる(非特許文献1参照)。逆ターミナル・テーブルは、ターミナル曲線ak1,Nが入力されたときに、そのインデックス情報kを高速に索出するために用意されたものである。
【0068】
尚、以下では、ターミナル・テーブル、インダクション・テーブル、及び逆ターミナル・テーブルを総称して「曲線演算テーブル」と呼ぶ。
【0069】
図5にターミナル・テーブルの構造を、図6にインダクション・テーブルの構造を示す。ターミナル・テーブル及びインダクション・テーブルは、それぞれ、N2個のレコード(行)を備えている。
【0070】
ターミナル・テーブルの各レコードには、ターミナル曲線ak1,N(k=1,…,N2N−1)のインデックス情報kと、当該ターミナル曲線ak1,Nのアドレス・シーケンス(ak1,N(1),ak1,N(2),…,ak1,N(2))が格納されている。従って、ターミナル・テーブルは、インデックス情報kが入力されると、ターミナル曲線ak1,N=(ak1,N(1),ak1,N(2),…,ak1,N(2))を出力する。
【0071】
インデックス・テーブルの各レコードには、ターミナル曲線ak1,N(k=1,…,N2N−1)のインデックス情報kと、当該ターミナル曲線ak1,Nの各アドレスak1,N(i)(i=1,…,2)に連結するターミナル曲線aki1,Nのインデックスk=wk1,N(i)の配列(wk1,N(1),wk1,N(2),…,wk1,N(2))が格納されている。
【0072】
(例1)
N=2の場合、ターミナル・テーブル及びインデックス・テーブルは、例えば、(表1),(表2)のようになる。
【0073】
【表1】

【0074】
【表2】

【0075】
(表1)のターミナル・テーブルの各レコードのターミナル曲線a11,2,a21,2,a31,2,a41,2は、それぞれ、図7(a)に示した2次元ヒルベルト曲線のアドレス順序を表している。また、(表2)のインダクション・テーブルの各インデックスは、分割指数mの2次元ヒルベルト曲線akm,2(k=1,2,3,4)を分割して分割指数(m+1)の2次元ヒルベルト曲線ak(m+1),2を生成する際に、ターミナル曲線ak1,2の要素の各アドレスak1,2(1),ak1,2(2),ak1,2(3),ak1,2(4)の各々に連結する分割指数mのヒルベルト曲線aξm,2のインデックスξを表す。例えば、m=1の場合においてa11,2を分割してa12,2を生成する場合、(表1),(表2)より、
【0076】
【数9】

のように帰納的に生成することができる。
(例終り)
【0077】
(例2)
N=3の場合、ターミナル・テーブル及びインデックス・テーブルは、例えば、(表3),(表4)のようになる。
【0078】
【表3】

【0079】
【表4】

【0080】
(表3)のターミナル・テーブルのターミナル曲線a11,3,a41,3,a71,3,a101,3は、それぞれ、図7(b)に示した2次元ヒルベルト曲線のアドレス順序を表している。また、(表4)のインダクション・テーブルの各インデックスは、分割指数mの3次元ヒルベルト曲線akm,3(k=1,2,…,12)を分割して分割指数(m+1)の3次元ヒルベルト曲線ak(m+1),3を生成する際に、ターミナル曲線ak1,3の要素の各アドレスak1,3(1),ak1,3(2),…,ak1,3(8)の各々に連結する分割指数mのヒルベルト曲線aξm,3のインデックスξを表す。例えば、m=1の場合においてa5m,3を分割してa5(m+1),3を生成する場合、(表1),(表2)より、
【0081】
【数10】

のように帰納的に生成することができる。
(例終り)
【0082】
ターミナル・テーブル初期化部13は、曲線演算テーブル記憶部12のターミナル・テーブルにターミナル曲線の初期値を設定する。
【0083】
シード曲線設定部14は、鍵番号Kに対するシード曲線Cをシード曲線テーブル記憶部11のシード曲線テーブルから読み出し、曲線演算テーブル記憶部12のターミナル・テーブルから、該シード曲線Cと始点及び終点が一致するターミナル曲線aξを索出し、ターミナル・テーブルの該ターミナル曲線aξを該シード曲線Cに置換する。
【0084】
インダクション・テーブル生成部15は、シード曲線設定部14によりシード曲線Cが設定されたターミナル・テーブルに基づき、インダクション・テーブル内の各インデックス情報を設定する。
【0085】
曲線上演算部16は、N次元整数空間内の2点A,Bが入力されると、各点A,Bに対し、シード曲線Cをターミナル・テーブル及びインダクション・テーブルにより(M−1)回分割して生成される分割指数MのN次元ヒルベルト曲線である鍵曲線Hにより、1次元序数空間内の序数iA,iBに単射する1次元写像手段、素数pを法とする各序数iA,iBの和iZ=iA+iB mod pを算出する和算手段、及びこの序数iZをN次元整数空間内の点Zに単射するN次元写像手段から構成されている(図示せず)。そして、この出力される点Zが点A,Bの和算点となる。
【0086】
暗号コード生成モジュール5は、公開鍵入力部21、暗号化倍数生成部22、平文コード点生成部23、暗号コード生成部24、及び暗号コード出力部25を備えている。
【0087】
公開鍵入力部21は、復号装置2dから送信される、N次元整数空間内の点である第一基準点X1及び第二基準点X2を受信する。
【0088】
暗号化倍数生成部22は、乱数により倍率数sを生成する。
【0089】
平文コード点生成部23は、平文コード入力部8から平文コードが入力されると、それに対応するN次元整数空間内の点である平文コード点Yを算出する。
【0090】
暗号コード生成部24は、曲線上演算部16により、第一基準点X1をs回和算した積算点である第三基準点X、及び第二基準点X2をs回和算した積算点に、素数pを法として平文コード点Yをベクトル加算した暗号コード点Vを算出する。
【0091】
暗号コード出力部25は、暗号コード生成部24が算出する点の組(X,V)を暗号コードとして復号装置2dへ送信する。ここで、第三基準点Xは、エンコード関数の逆関数f−1を特定するデコード情報であり、暗号コード点Vは暗号コードに相当する。
【0092】
(3)復号装置の内部構成
図3は、暗号処理装置2の復号機能部分(復号装置2d)の機能構成を表すブロック図である。共通モジュール4については、図2のものと同様である。
【0093】
復号モジュール6は、復号倍率数生成部31、公開鍵生成部32、暗号コード入力部33、及び復号演算部34を備えている。
【0094】
復号倍率数生成部31は、乱数により倍率数sを生成する。
【0095】
公開鍵生成部32は、乱数により第一基準点X1を生成し、曲線上演算部16により、第一基準点X1をs回和算した積算点である第二基準点X2を算出し、該第一基準点X1及び該第二基準点X2を、エンコード関数fを特定するエンコード情報として暗号化装置2eに送信する。
【0096】
暗号コード入力部33は、暗号化装置2eから送信される、第三基準点X及び暗号コード点Vを受信する。
【0097】
復号演算部34は、曲線上演算部16により、第三基準点Xをs回曲線上和算した積算点Xを算出し、素数pを法として暗号コード点Vから点Xをベクトル減算して得られる点Yを算出する。
【0098】
平文コード出力部9は、復号演算部34により算出された点Yに対応する平文コードを算出する。
【0099】
〔2〕暗号処理システムによる暗号処理方法
以上のように構成された本実施例の暗号処理システム1について、以下その動作を説明する。
(1)全体動作
図8は、暗号処理システム1による暗号化装置2e(メッセージ送信側の暗号処理装置2)と復号装置2d(メッセージ受信側の暗号処理装置2)との間の暗号化通信の動作を表すフローチャートである。
【0100】
まず、ステップS1,S21において、暗号化装置2e及び復号装置2dのパラメータ交換部17は、初期パラメータである分割指数M,次元数N,素数pを読み出し、互いに交換することにより共通化する。
【0101】
次に、ステップS2において、復号装置2dの復号倍率数生成部31は、乱数により倍率数sを生成し、ステップS22において、暗号化装置2eの暗号化倍数生成部22は、乱数により倍率数sを生成する。
【0102】
次に、ステップS3,S23において、パラメータ交換部17は鍵番号Kの交換を行う。鍵番号Kの交換は、非暗号化通信により行うことも可能であるが、本実施例においては、後述するDiffie Hellman暗号化方式により鍵番号Kの交換を行う例を示す(図10参照)。
【0103】
次に、ステップS4,S24において、復号装置2d及び暗号化装置2eの双方におけるターミナル・テーブル初期化部13、シード曲線設定部14、及びインダクション・テーブル生成部15は、それぞれ、次元数N,素数p,及び鍵番号Kに基づき、図4のシード曲線テーブルを参照して、曲線演算テーブル(図5のターミナル・テーブル、図6のインダクション・テーブル、及び逆ターミナル・テーブル)を生成し、曲線演算テーブル記憶部12に格納する。曲線演算テーブルの生成方法については、非特許文献1に記載の方法を応用するが、その詳細については後述する。
【0104】
次に、ステップS5において、復号装置2dの公開鍵生成部32は、乱数により(M×N)ビットのビット・シーケンスを発生させることにより、N次元整数空間内の点を生成し、これを第一基準点X1に設定する。
【0105】
次に、ステップS6において、復号装置2dの公開鍵生成部32は、曲線上演算部16により、第一基準点X1をs回曲線上和算した積算点を算出し、これを第二基準点X2に設定する。曲線上演算部16による曲線上和算の具体的な演算処理に関しては、後述する。ここで、点X2は次式によって表される。
【0106】
【数11】

【0107】
ここで、関数L(X)は、N次元整数空間内の点Xを、鍵番号Kの鍵曲線Hにより1次元序数空間内の序数iに単射する関数を表し、L−1(i)はその逆関数を表す。ここで、鍵曲線Hは、分割指数1のシード曲線Cを、ターミナル・テーブル及びインダクション・テーブルを用いて(M−1)回分割することにより得られるヒルベルト曲線である。本明細書では、一般に、N次元整数空間内の2点A,Bに対して、C=L−1[L(A)+L(B)]によりN次元整数空間内の点Cを算出する演算を「曲線上和算」と呼ぶ。
【0108】
図9にN次元空間点と分割指数mのN次元のヒルベルト曲線との単射関係を示す。N次元空間は、直交するN本の座標軸を有するが、図9(b)ではそのうちの2本の座標軸y,yを示している。各座標軸の区間[0,1]は長さ1/2の2個の小区間に分割されている。座標軸y上の区間[x/2,(x+1)/2]を座標点x、座標軸y上の区間[x/2,(x+1)/2]を座標点xのように表し、N個の座標点(x,x,…,x)で特定される点(図9(b)の領域Sm,2)をN次元空間内の点X=(x,x,…,x)とする。この点Xは、m×Nビットのアドレスにより特定することができる。従って、この点Xは、一辺の長さが1の超立方体を充填する分割指数mのヒルベルト曲線(図9(a))との1対1対応させることができる。尚、分割指数mのヒルベルト曲線は、長さ2mNのアドレス・シーケンスであり、各アドレスはm×Nビットで表される。
【0109】
次に、ステップS7において、復号装置2dの公開鍵生成部32は、生成した第一基準点X1及び該第二基準点X2をエンコード情報{X1,X2}として、通信インタフェース7により通信ネットワーク3を介して暗号化装置2eへ送信する。
【0110】
次に、ステップS25において、暗号化装置2eの公開鍵入力部21は、復号装置2dから送信されるエンコード情報{X1,X2}を受信する。このエンコード情報{X1,X2}が公開鍵に相当する。
【0111】
次に、ステップS26において、暗号化装置2eの平文コード入力部8から、復号装置2dへ送信する平文コードMesが入力される。
【0112】
次に、ステップS27において、暗号化装置2eの平文コード点生成部23は、平文コードMesを(M×N)ビットのビット・シーケンスに分割し、それぞれのビット・シーケンスをN次元整数空間内の点に対応させることにより、平文コード点Y,Y,…を生成する。平文コード点Yの数は、平文コードMesの長さにより決まるが、ここでは簡単のために平文コード点Yの数を1個として説明する。
【0113】
次に、ステップS28において、暗号化装置2eの暗号コード生成部24は、曲線上演算部16により、第一基準点X1をs回曲線上和算した積算点である第三基準点Xを算出する。また、曲線上演算部16により、第二基準点X2をs回曲線上和算した積算点V’を算出し、この点V’に対し素数pを法として平文コード点Yをベクトル加算した暗号コード点Vを算出する。そして、算出された第三基準点Xを、エンコード関数の逆関数f−1を特定するデコード情報とし、暗号コード点Vを暗号コードとする。ここで、各点(X,V)は次式によって表される。
【0114】
【数12】

ここで、f(L(X);s,p)はエンコード関数である。
【0115】
次に、ステップS29において、暗号化装置2eの暗号コード出力部25は、暗号コード生成部24が算出する第三基準点X及び暗号コード点Vを、通信インタフェース7により通信ネットワーク3を介して復号装置2dへ送信する。
【0116】
次に、ステップS8において、復号装置2dの暗号コード入力部33は、暗号化装置2eから送信される、点(X,V)を受信する。
【0117】
次に、ステップS9において、復号装置2dの復号演算部34は、曲線上演算部16により、点Xをs回曲線上和算した積算点Vを算出し、素数pを法として点Vから前記点Vをベクトル減算して得られる点Yを算出する。これにより、もとの平文コード点Yが復元される。復号演算部34を式により表すと、次式のようになる。
【0118】
【数13】

ここで、g(L(X);s,p)はエンコード関数fと可換なデコード関数である。式(13)に式(12a)(12b)を代入すれば、可換関数となっていることが分かる。
【0119】
次に、ステップS10において、復号装置2dの復号演算部34は、平文コード点Yに対応する平文コードMesを算出する。
【0120】
最後に、ステップS11において、復号装置2dの平文コード出力部9は、平文コードMesを出力し、復号処理を終了する。
【0121】
(2)曲線上演算部16による曲線上和算
次に、式(11),(12a),(12b),(13)において用いる曲線上演算部16による曲線上和算について具体的に説明する。曲線上和算とは、N次元整数空間内の加算する2点X,Yについて、各点X,Yを鍵曲線Hにより1次元序数空間内の序数iX,iYに単射し、所定の素数pを法とする各序数iX,iYの和iZ=iX+iY mod pを算出し、この序数iZを鍵曲線HによりN次元整数空間内の点Zに単射することにより得られる点Zを点X,Yの和算点とする演算をいう。ここで、鍵曲線Hは、鍵番号Kのシード曲線Cをターミナル・テーブル及びインダクション・テーブルにより(M−1)回分割して得られる分割指数MのN次元ヒルベルト曲線である。
【0122】
今、上記3つの点の座標をX=(x,x,…,x),Y=(y,y,…,y),Z=(z,z,…,z)とおく。シード曲線Cを(M−1)回分割して生成される分割指数MのN次元ヒルベルト曲線を「鍵曲線」といい、Hと記す。鍵曲線Hは、曲線発生の種となるシード曲線Cの種類により決まり、その総数F(N)は、式(8)で説明したように非常に大きな数となる。ここで、鍵曲線Hの分割指数MのN次元ヒルベルト曲線の種類(インデックス)をγと記す。
【0123】
曲線γの鍵曲線Hにおける曲線上和算Z=L−1[L(X)+L(Y)]は、次のようにして算出することができる。
【0124】
(2−1)〔曲線上和算のアルゴリズム〕
0)準備
上記ステップS4,S24において、シード曲線Cを設定したターミナル・テーブルTtermNを生成し、ターミナル・テーブルTtermNから逆ターミナル・テーブルITtermN及びインダクション・テーブルTindNを生成しておく。
【0125】
1)まず、点Xの座標であるアドレス(x,x,…,x)を用いて、序数iXを次式により計算する。
【0126】
【数14】

【0127】
ここで、関数Hil2(γ,M,(x,x,…,x))は、分割指数Mの曲線γ上の点(x,x,…,x)の順番を求める関数である。関数Hil2の具体的な演算については、後述する。
【0128】
2)次に、点Yの座標であるアドレス(y,y,…,y)を用いて、序数iYを次式により計算する
【0129】
【数15】

【0130】
3)次に、序数iX,iYを用いて
【0131】
【数16】

を計算する。
【0132】
4)最後に、次式により、序数iZから点Zの座標であるアドレス(z,z,…,z)を求める。
【0133】
【数17】

【0134】
ここで、関数Hil1(γ,M,iZ)は、分割指数Mの曲線γ上の点Zの序数iZから点Zの座標(z,z,…,z)を求める関数である。関数Hil1の具体的な演算については、後述する。
【0135】
(2−2)〔関数Hil1の計算〕
今、N次元空間内の点Aのアドレスaを
【0136】
【数18】

とする。ここで、zA,i(i=1,…,M)は、式(18b)のようなNビットのビット・シーケンスである。zA,i,jが0又は1のリテラルを表す。式(18c)は、アドレスaのシーケンスとN次元空間の点座標(z,z,…,z)との関係を示している。また、点Aを分割指数Mのヒルベルト曲線γ上に写像したときに、ヒルベルト曲線γ上における点Aの序数をiAとし、iAを次式のように表す。
【0137】
【数19】

【0138】
このとき、zA,1,zA,2,…,zA,Mは、ターミナル・テーブルTtermN及びインダクション・テーブルTindNを用いて、以下のように逐次求めることができる。
【0139】
【数20】

【0140】
これにより、点Aのアドレスaを算出することができる。ここで、TtermNk][i]は、図5のターミナル・テーブルにおいて曲線γkに対応するレコードのi番目のアドレスを表し、TindNk][i]は、図6のインダクション・テーブルにおいて曲線γkに対応するレコードのi番目のインデックスを表す。
【0141】
(2−3)〔関数Hil2の計算〕
前述のN次元空間内の点Aのアドレスaから、点Aを分割指数Mのヒルベルト曲線γ上に写像したときの、ヒルベルト曲線γ上における点Aの序数iAの演算(関数Hil2)は、逆ターミナル・テーブルITtermN及びインダクション・テーブルTindNを用いて、以下のように逐次行うことができる。
【0142】
【数21】

【0143】
(3)鍵番号Kの交換
次に、図8のステップS3,S23における暗号化装置2eと復号装置2dとの間の鍵番号Kの交換について説明する。鍵番号Kの交換方法については、本発明ではどのような方法を用いてもよいが、データ通信の秘匿性をより頑健なものとするためには、既存の公開鍵暗号方式を用いるのがよい。本実施例では、Diffie Hellman暗号化方式を用いた例について示す。
【0144】
図10は、鍵番号Kの交換動作を表すフローチャートである。
【0145】
まず、ステップS31,S41において、復号装置2d,暗号化装置2eのパラメータ交換部17は、内部メモリから初期パラメータとしてD,qを読み出す。ここで、Dは原始元、qは素数であり、復号装置2d及び暗号化装置2eにおいて、予め決められた共通の値が与えられているものとする。
【0146】
次に、ステップS32,S42において、復号装置2d,暗号化装置2eのパラメータ交換部17は、それぞれ、乱数r,rを生成する。
【0147】
次に、ステップS33,S43において、復号装置2d,暗号化装置2eのパラメータ交換部17は、それぞれ、公開鍵b,bを次式により生成する。
【0148】
【数22】

【0149】
次に、ステップS44において、暗号化装置2eのパラメータ交換部17は、公開鍵bを復号装置2dに送信し、ステップS34において、復号装置2dのパラメータ交換部17は、当該公開鍵bを受信する。
【0150】
次に、ステップS35において、復号装置2dのパラメータ交換部17は、公開鍵bを暗号化装置2eに送信し、ステップS45において、暗号化装置2eのパラメータ交換部17は、当該公開鍵bを受信する。
【0151】
最後に、ステップS36,S46において、復号装置2d,暗号化装置2eのパラメータ交換部17は、それぞれ、次式により鍵番号Kを算出する。
【0152】
【数23】

【0153】
以上により、復号装置2dと暗号化装置2eにおいて、共通の鍵番号Kが交換される。
【0154】
(4)曲線演算テーブルの生成
次に、ステップS4における各曲線演算テーブルの設定方法について説明する。図11は、各曲線演算テーブルの設定方法の全体動作を表すフローチャートである。
【0155】
まず、ステップS50において、ターミナル・テーブル初期化部13により、曲線演算テーブル記憶部12内のターミナル・テーブルの初期化が行われる。ターミナル・テーブルの初期化処理の詳細については後述する。これにより、ターミナル・テーブルには、初期値として、分割指数1のN次ヒルベルト曲線である各ターミナル曲線が設定される。
【0156】
次に、ステップS51において、ターミナル・テーブル初期化部13により、曲線演算テーブル記憶部12内の逆ターミナル・テーブルの初期化が行われる。
【0157】
次に、ステップS52において、シード曲線設定部14は、シード曲線テーブル記憶部11内のシード曲線テーブから、鍵番号Kのシード曲線Cを索出する。そして、シード曲線Cの先頭のアドレスcK1,N(1)と最後のアドレスcK1,N(2)を読み出し、このアドレスcK1,N(1),cK1,N(2)を検索キーとしてターミナル・テーブルを検索し、始点及び終点がアドレスcK1,N(1),cK1,N(2)に一致するターミナル曲線aξ1,Nを索出する。ここで、ターミナル・テーブルに格納された各ターミナル曲線は、始点と終点の組合せが全て異なる。従って、始点及び終点がアドレスcK1,N(1),cK1,N(2)に一致するターミナル曲線は唯1つに特定される。
【0158】
ステップS53,S54において、ターミナル曲線aξ1,Nが索出されると、シード曲線設定部14は、ターミナル・テーブルのターミナル曲線aξ1,Nをシード曲線Cに置換する。すなわち、TtermN[ξ][i](=aξ1,N(i))=cK1,N(i)(i=1,…,2)に設定する。
【0159】
次に、ステップS55,S56において、シード曲線設定部14は、逆ターミナル・テーブルのインデックスITtermN[ξ][cK1,N(i)]をシード曲線CのアドレスcK1,N(i)のインデックスiに置換する。すなわち、ITtermN[ξ][cK1,N(i)]=i(i=1,…,2)に設定する。
【0160】
最後に、ステップS57において、インダクション・テーブル生成部15により、曲線演算テーブル記憶部12内のインダクション・テーブルの生成が行われる。インダクション・テーブルの生成処理の詳細については後述する。これにより、インダクション・テーブルには、連結曲線を指定する各インデックス値が設定される。
【0161】
以上の処理により、曲線演算テーブル記憶部12に、ターミナル・テーブル,逆ターミナル・テーブル,インダクション・テーブルがそれぞれ生成される。
【0162】
(4−1)ターミナル・テーブルの初期化
次に、図11のステップS50におけるターミナル・テーブル初期化部13によるターミナル・テーブルの初期値の処理方法について説明する(非特許文献1参照)。図12は、ターミナル・テーブル初期化部13によるターミナル・テーブルの初期値の設定処理を表すフローチャートである。尚、図12のフローチャートはPAD(Problem Analysis Diagram;JIS X0128参照)により表している。
【0163】
まず、ステップS61において、ターミナル・テーブル初期化部13は、1番目のターミナル曲線a11,Nを生成する種となる分割指数1の1次元ヒルベルト曲線a11,1を(0,1)に設定する。
【0164】
次に、ステップS62,S63において、ターミナル・テーブル初期化部13は、分割指数1の1次元ヒルベルト曲線a11,1から分割指数1の1次元ヒルベルト曲線a11,Nを、次の逐次式によって生成する。
【0165】
【数24】

【0166】
次に、ステップS64,S65,S66において、ターミナル・テーブル初期化部13は、先に生成した1番目のターミナル曲線a11,Nの各アドレス値を用いて、(N(i-1)+j)番目(i=1,…,2N−1;j=1,…,N)のターミナル曲線aN(i-1)+j1,Nの先頭のアドレスaN(i-1)+j1,N(1)を、ターミナル曲線a11,Nの(2i−1)番目のアドレス値a11,N(2i−1)に設定する。
【0167】
【数25】

【0168】
次に、ステップS67,S68,S69において、ターミナル・テーブル初期化部13は、先に生成したターミナル曲線aN(i-1)+j1,Nの先頭のアドレス値aN(i-1)+j1,N(1)を用いて、(N(i-1)+j)番目(i=1,…,2N−1;j=1,…,N)のターミナル曲線aN(i-1)+j1,Nの最後のアドレスaN(i-1)+j1,N(2)を、当該ターミナル曲線aN(i-1)+j1,Nの1番目のアドレス値aN(i-1)+j1,N(1)のj番目のビットを反転したアドレス値ibit(aN(i-1)+j1,N(1))に設定する。
【0169】
【数26】

【0170】
次に、ステップS70〜S74において、ターミナル・テーブル初期化部13は、k番目(k=2,…,N)のターミナル曲線ak1,Nのi’番目(i’=2,…,2−1)の中間点アドレスak1,N(i')を次式により設定する。
【0171】
【数27】

【0172】
次に、ステップS75〜S78において、ターミナル・テーブル初期化部13は、(Ni+j)番目(i=1,…,2N−1−1;j=1,…,N)のターミナル曲線a(Ni+j)1,Nのi’番目(i’=2,…,2−1)の中間点アドレスa(Ni+j)1,N(i')を次式により設定する。
【0173】
【数28】

【0174】
最後に、ステップS79〜S81において、ターミナル・テーブル初期化部13は、生成したアドレスak1,N(i)を、ターミナル・テーブルの要素TtermN[k][i]に格納して、ターミナル・テーブルの初期化処理を終了する。生成されたターミナル・テーブルは、図5のようになる。このターミナル・テーブルの初期値は、次元数Nを特定すれば、一意的に生成することができる。
【0175】
(4−2)逆ターミナル・テーブルの生成
次に、図11のステップS51における、ターミナル・テーブル初期化部13による逆ターミナル・テーブルの初期値の設定方法について説明する。図13は、ターミナル・テーブル初期化部13による逆ターミナル・テーブルの初期値の設定処理を表すフローチャートである。尚、図13のフローチャートもPADにより表している。この処理は極めて簡単であり、ターミナル・テーブルのk番目(k=1,…,N2)のターミナル曲線ak1,Nのi番目(i=1,…,2)のアドレスak1,N(i)をTtermN[k][i]から読み出して(S93)、このインデックスiを逆ターミナル・テーブルの要素ITtermN[k][ak1,N(i)]に格納する(S94)という操作を、すべてのk,iについて繰り返し行うことにより実行される。
【0176】
(4−3)インダクション・テーブルの生成
最後に、図11のステップS57における、インダクション・テーブル生成部15によるインダクション・テーブルの生成方法について説明する(非特許文献1参照)。図14は、インダクション・テーブル生成部15によるインダクション・テーブルの作成処理を表すフローチャートである。
【0177】
ステップS100において、インダクション・テーブル生成部15は、インデックスkを1からN2まで1ずつ増加させながら、以下のステップS101からS113までの処理を行う。
【0178】
(4−3−1)最初のアドレスの連結パスの設定処理
まず、インダクション・テーブル生成部15は、以下のステップS101〜S104において、インダクション・テーブルにおけるターミナル曲線ak1,Nの最初のアドレスに連結するパスの設定処理を行う。
【0179】
ステップS101において、インダクション・テーブル生成部15は、ターミナル・テーブルからk番目のターミナル曲線ak1,Nの1番目のアドレスak1,N(1)を読み出して、これを始点アドレス変数sに設定する。
【0180】
次に、ステップS102において、インダクション・テーブル生成部15は、ターミナル・テーブルからk番目のターミナル曲線ak1,Nの2番目のアドレスak1,N(2)を読み出して、次式の演算により、終点アドレス変数eに設定する。
【0181】
【数29】

【0182】
次に、ステップS103において、インダクション・テーブル生成部15は、始点アドレス変数s及び終点アドレス変数eを検索キーとして、ターミナル・テーブルを検索し、始点アドレスak*1,N(1)が始点アドレス変数sと一致し、終点アドレスak*1,N(2)が終点アドレス変数eと一致するターミナル曲線ak*1,Nを索出し、そのインデックスkを取得する。
【0183】
最後に、ステップS104において、インダクション・テーブル生成部15は、インダクション・テーブルのk番目のレコードの最初のインデックスTindN[k][1]をインデックスkに設定する。
【0184】
(4−3−2)中間の連結パスの設定処理
次に、ステップS105において、インダクション・テーブル生成部15は、序数指定変数iを2から2N−1まで1ずつ増加させながら、以下のステップS106〜S109の中間の連結パスの設定処理を繰り返し実行する。
【0185】
まず、ステップS106において、インダクション・テーブル生成部15は、先に設定した終点アドレス変数eと、ターミナル・テーブルから読み出されるk番目のターミナル曲線ak1,Nのアドレスak1,N(2i−2),ak1,N(2i−3)から、次式により始点アドレス変数sを変更する。
【0186】
【数30】

【0187】
次に、ステップS107において、インダクション・テーブル生成部15は、新たに設定した始点アドレス変数sと、ターミナル・テーブルから読み出されるk番目のターミナル曲線ak1,Nのアドレスak1,N(2i−1),ak1,N(2i−2)から、次式により終点アドレス変数eを変更する。
【0188】
【数31】

【0189】
次に、ステップS108において、インダクション・テーブル生成部15は、新たに再設定された始点アドレス変数s及び終点アドレス変数eを検索キーとして、ターミナル・テーブルを検索し、始点アドレスak*1,N(1)が始点アドレス変数sと一致し、終点アドレスak*1,N(2)が終点アドレス変数eと一致するターミナル曲線ak*1,Nを索出し、そのインデックスkを取得する。
【0190】
最後に、ステップS109において、インダクション・テーブル生成部15は、インダクション・テーブルのk番目のレコードの(2i−2)番目及び(2i−1)番目のインデックスTindN[k][2i-2],TindN[k][2i-1]をインデックスkに設定する。尚、ヒルベルト曲線の対称性によって、インダクション・テーブルの(2i−2)番目のインデックスと(2i−1)番目のインデックスは、常に同じ値となる(表2,表4参照)。
【0191】
(4−3−3)最後の連結パスの設定処理
最後に、インダクション・テーブル生成部15は、以下のステップS110〜S113において、インダクション・テーブルにおけるターミナル曲線ak1,Nの最後のアドレスに連結するパスの設定処理を行う。
まず、ステップS110において、インダクション・テーブル生成部15は、先に設定した終点アドレス変数eと、ターミナル・テーブルから読み出されるk番目のターミナル曲線ak1,Nのアドレスak1,N(2),ak1,N(2−1)から、次式により始点アドレス変数sを変更する。
【0192】
【数32】

【0193】
次に、ステップS111において、インダクション・テーブル生成部15は、終点アドレス変数eをターミナル・テーブルから読み出されるk番目のターミナル曲線ak1,Nのアドレスak1,N(2)に変更する。
【0194】
次に、ステップS112において、インダクション・テーブル生成部15は、新たに再設定された始点アドレス変数s及び終点アドレス変数eを検索キーとして、ターミナル・テーブルを検索し、始点アドレスak*1,N(1)が始点アドレス変数sと一致し、終点アドレスak*1,N(2)が終点アドレス変数eと一致するターミナル曲線ak*1,Nを索出し、そのインデックスkを取得する。
【0195】
最後に、ステップS113において、インダクション・テーブル生成部15は、インダクション・テーブルのk番目のレコードの最後のインデックスTindN[k][2N]をインデックスkに設定する。以上の処理によって、インダクション・テーブルを作成することができる。
【実施例2】
【0196】
図15は、本発明の実施例2に係る暗号化装置2e(メッセージ送信側の暗号処理装置2)の構成を表すブロック図、図16は、本発明の実施例2に係る復号装置2d(メッセージ受信側の暗号処理装置2)の構成を表すブロック図である。尚、本実施例において、暗号処理システムの全体構成は図1と同様であるとする。本実施例は、実施例1の暗号処理装置2の構成を、さらに単純化したものである。
【0197】
図15,図16において、共通モジュール4、暗号コード生成モジュール5、復号モジュール6、通信インタフェース7、平文コード入力部8、平文コード出力部9、曲線上演算部16、公開鍵入力部21、暗号化倍数生成部22、平文コード点生成部23、暗号コード生成部24、暗号コード出力部25、復号倍率数生成部31、公開鍵生成部32、暗号コード入力部33、及び復号演算部34は、実施例1の図2,図3の同符号の構成部分に対応している。
【0198】
本実施例では、図2,図3のシード曲線テーブル記憶部11に代えて、鍵曲線記憶部11’を備えており、図2,図3の曲線演算テーブル記憶部12、ターミナル・テーブル初期化部13、シード曲線設定部14、及びインダクション・テーブル生成部15は省略されている。また、本実施例では、パラメータM,N,pは、各暗号処理装置2において予め与えられており、図2,図3のパラメータ交換部17の代わりに鍵番号交換部17’を備えている。
【0199】
本実施例では、鍵曲線記憶部11’には、N次元整数空間内の所定の部分空間を充填する空間充填曲線である鍵曲線H(k=1,2,…)そのものが複数記憶されている。ここで、空間充填曲線としては、実施例1と同様に、分割指数Mのヒルベルト曲線を使用することもできるが、本実施例では他の例として、分割指数MのN次元ペアノ曲線、分割指数MのN次元シェルピンスキー曲線、及び分割指数MのN次元ムーア曲線を使用することとする。図17に、2次元に於けるペアノ曲線、シェルピンスキー曲線、及びムーア曲線の例を示す。これらの空間充填曲線も、M回分割することにより、自己相似的に拡張することができる。
【0200】
鍵番号交換部17’は、他の暗号処理装置2との間で、鍵曲線を特定する鍵番号Kを交換する。鍵番号Kの交換処理については、実施例1の図10で説明したDiffie Hellman暗号化方式による鍵番号Kの交換処理が行われるものとする。
【0201】
以上のように構成された本実施例の暗号処理システム1について、以下その動作を説明する。
【0202】
図18は、実施例2の暗号処理システム1による暗号化装置2e(メッセージ送信側の暗号処理装置2)と復号装置2d(メッセージ受信側の暗号処理装置2)との間の暗号化通信の動作を表すフローチャートである。
【0203】
ステップS1〜S3,S21〜S23は、図8と同様であるため説明は省略する。尚、本実施例では、パラメータM,N,pは、各暗号処理装置2に予め与えられているので、ステップS1,S21ではパラメータM,N,pの交換は行われない。
【0204】
ステップS3において、鍵番号Kの交換が行われることによって、暗号化装置2eと復号装置2dの双方において共通の鍵番号Kが保有される。
【0205】
次に、ステップS5において、復号装置2dの公開鍵生成部32は、乱数により(qM×N)ビットのビット・シーケンスを発生させることにより、N次元整数空間内の点を生成し、これを第一基準点X1に設定する。ここで、qは使用する空間充填曲線により決まる定数であり、ペアノ曲線の場合にはq=2,シェルピンスキー曲線、ムーア曲線の場合にはq=1である。
【0206】
次に、ステップS6において、復号装置2dの公開鍵生成部32は、曲線上演算部16により、第一基準点X1に基づき、次式により第二基準点Xを算出する。
【0207】
【数33】

尚、本実施例では、エンコード関数fとして、実施例1と異なる関数の例を示すが、実施例1と同様のエンコード関数fを使用してもよい。その場合、式(33)の代わりに式(11)を使用すればよい。
【0208】
次に、ステップS7において、復号装置2dの公開鍵生成部32は、生成した第一基準点X1及び該第二基準点X2をエンコード情報{X1,X2}として、通信インタフェース7により通信ネットワーク3を介して暗号化装置2eへ送信する。
【0209】
次に、ステップS25において、暗号化装置2eの公開鍵入力部21は、復号装置2dから送信されるエンコード情報{X1,X2}を受信する。
【0210】
次に、ステップS26において、暗号化装置2eの平文コード入力部8から、復号装置2dへ送信する平文コードMesが入力される。
【0211】
次に、ステップS27において、暗号化装置2eの平文コード点生成部23は、平文コードMesを(qM×N)ビットのビット・シーケンスに分割し、それぞれのビット・シーケンスをN次元整数空間内の点に対応させることにより、平文コード点Y,Y,…を生成する。平文コード点Yの数は、平文コードMesの長さにより決まるが、ここでは簡単のために平文コード点Yの数を1個として説明する。
【0212】
次に、ステップS28において、暗号化装置2eの暗号コード生成部24は、曲線上演算部16により、次式により第三基準点X及び暗号コード点Vを算出する。そして、算出された第三基準点Xを、エンコード関数の逆関数f−1を特定するデコード情報とし、暗号コード点Vを暗号コードとする。
【0213】
【数34】

ここで、f(L(X);s,p)はエンコード関数である。尚、実施例1と同様のエンコード関数fを使用する場合、式(34a)(34b)の代わりに式(12a)(12b)を使用すればよい。
【0214】
次に、ステップS29において、暗号化装置2eの暗号コード出力部25は、暗号コード生成部24が算出する第三基準点X及び暗号コード点Vを、通信インタフェース7により通信ネットワーク3を介して復号装置2dへ送信する。
【0215】
次に、ステップS8において、復号装置2dの暗号コード入力部33は、暗号化装置2eから送信される、点(X,V)を受信する。
【0216】
次に、ステップS9において、復号装置2dの復号演算部34は、曲線上演算部16により、次式により得られる点Yを算出する。これにより、もとの平文コード点Yが復元される。
【0217】
【数35】

ここで、g(L(X);s,p)はエンコード関数fと可換なデコード関数である。尚、実施例1と同様のエンコード関数gを使用する場合、式(35)の代わりに式(13)を使用すればよい。
【0218】
次に、ステップS10において、復号装置2dの復号演算部34は、平文コード点Yに対応する平文コードMesを算出する。
【0219】
最後に、ステップS11において、復号装置2dの平文コード出力部9は、平文コードMesを出力し、復号処理を終了する。
【実施例3】
【0220】
図19は、本発明の実施例3に係る暗号化装置2e(メッセージ送信側の暗号処理装置2)の構成を表すブロック図、図20は、本発明の実施例3に係る復号装置2d(メッセージ受信側の暗号処理装置2)の構成を表すブロック図である。尚、本実施例においても、暗号処理システムの全体構成は図1と同様であるとする。本実施例は、実施例2の暗号処理装置2の構成を、さらに単純化したものである。
【0221】
図19,図20において、共通モジュール4、暗号コード生成モジュール5、復号モジュール6、通信インタフェース7、平文コード入力部8、平文コード出力部9、曲線上演算部16、平文コード点生成部23、暗号コード生成部24、暗号コード出力部25、暗号コード入力部33、及び復号演算部34は、実施例1の図2,図3の同符号の構成部分に対応している。
【0222】
本実施例では、図2,図3のシード曲線テーブル記憶部11に代えて、鍵曲線記憶部11’を備えており、図2,図3の曲線演算テーブル記憶部12、ターミナル・テーブル初期化部13、シード曲線設定部14、及びインダクション・テーブル生成部15は省略されている。また、本実施例では、パラメータM,N,pは、各暗号処理装置2において予め与えられており、図2,図3のパラメータ交換部17の代わりに鍵番号交換部17’を備えている。
【0223】
また、本実施例では、第一基準点X,第二基準点X,第三基準点Xを使用しないので、図2,図3の公開鍵入力部21、暗号化倍数生成部22、復号倍率数生成部31、公開鍵生成部32は省略されている。
【0224】
本実施例では、実施例2と同様、鍵曲線記憶部11’には、N次元整数空間内の所定の部分空間を充填する空間充填曲線である鍵曲線H(k=1,2,…)そのものが複数記憶されている。
【0225】
鍵番号交換部17’は、他の暗号処理装置2との間で、鍵曲線を特定する鍵番号Kを交換する。鍵番号Kの交換処理については、実施例1の図10で説明したDiffie Hellman暗号化方式による鍵番号Kの交換処理が行われるものとする。
【0226】
以上のように構成された本実施例の暗号処理システム1について、以下その動作を説明する。
【0227】
図21は、実施例3の暗号処理システム1による暗号化装置2e(メッセージ送信側の暗号処理装置2)と復号装置2d(メッセージ受信側の暗号処理装置2)との間の暗号化通信の動作を表すフローチャートである。
【0228】
ステップS1〜S3,S21〜S23は、図8と同様であるため説明は省略する。尚、本実施例では、パラメータM,N,pは、各暗号処理装置2に予め与えられているので、ステップS1,S21ではパラメータM,N,pの交換は行われない。
【0229】
ステップS3において、鍵番号Kの交換が行われることによって、暗号化装置2eと復号装置2dの双方において共通の鍵番号Kが保有される。
【0230】
次に、ステップS26において、暗号化装置2eの平文コード入力部8から、復号装置2dへ送信する平文コードMesが入力される。
【0231】
次に、ステップS27において、暗号化装置2eの平文コード点生成部23は、平文コードMesを(qM×N)ビットのビット・シーケンスに分割し、それぞれのビット・シーケンスをN次元整数空間内の点に対応させることにより、平文コード点Y,Y,…を生成する。平文コード点Yの数は、平文コードMesの長さにより決まるが、ここでは簡単のために平文コード点Yの数を1個として説明する。
【0232】
次に、ステップS28において、暗号化装置2eの暗号コード生成部24は、曲線上演算部16により、次式により暗号コード点Vを算出し、この暗号コード点Vを暗号コードとする。
【0233】
【数36】

ここで、f(L(Y))はエンコード関数である。関数f(x)としては、任意の単射関数を使用することができる。
【0234】
次に、ステップS29において、暗号化装置2eの暗号コード出力部25は、暗号コード生成部24が算出する暗号コード点Vを、通信インタフェース7により通信ネットワーク3を介して復号装置2dへ送信する。
【0235】
次に、ステップS8において、復号装置2dの暗号コード入力部33は、暗号化装置2eから送信される、暗号コード点Vを受信する。
【0236】
次に、ステップS9において、復号装置2dの復号演算部34は、曲線上演算部16により、次式により得られる点Yを算出する。これにより、もとの平文コード点Yが復元される。
【0237】
【数37】

ここで、f−1(L(V))はエンコード関数fの逆関数である。
【0238】
次に、ステップS10において、復号装置2dの復号演算部34は、平文コード点Yに対応する平文コードMesを算出する。
【0239】
最後に、ステップS11において、復号装置2dの平文コード出力部9は、平文コードMesを出力し、復号処理を終了する。
【実施例4】
【0240】
本実施例では、空間充填曲線として、実施例1で示したヒルベルト曲線以外のものを使用する例について説明する。空間充填曲線としては、様々なものがあり、本発明においてはどのような種類の空間充填曲線を使用することも可能であるが、ここではわかりやすい例として、ペアノ曲線及びペアノ曲線から発展させたペアノ型曲線を使用する例を挙げて説明する。
【0241】
(1)N次元ペアノ曲線
閉単位区間をI=[0,1],閉単位正方形をQ=[0,1]とする。区間[0,1]内の点の値のq進数表現を0.tq,1q,2q,3…のように表す。例えば、区間[0,1]内の中点を2進数表現で表記する場合0.1…、3進数表現で表記する場合0.1…、4進数表現で表記する場合0.2…のように表す。tq,1,tq,2,tq,3,…は各桁のリテラルを表し0〜(q−1)までの値をとる。
IからQへの写像関数f(2)を次式により定義する。
【0242】
【数38】

【0243】
ここで、tの添字の1番目は3進数であること、2番目は桁番号を表す。sの添字の1番目は3進数であること、2番目は座標軸の番号、3番目は桁番号を表している。また、関数Kは3進数リテラル反転関数である。一般に、q進数リテラル反転関数Kは次式により定義される(非特許文献2,p.40参照)。
【0244】
【数39】

また、関数Kのν回の合成は次のように定義される。
【0245】
【数40】

【0246】
以下では写像関数f(2)の式(38)のような定義式を次式(41a)(41b)のように簡略表記することとする。ここで、nは写像する2次元ベクトルsの各成分の桁数であり、「分割指数」という。n→∞とすると式(41a)は式(38)と等価となる。
【0247】
【数41】

【0248】
ここで、式(41b)の最初の和の記号は、1以上でk−1以下のすべてのiについての和をとることを表し、2番目の和の記号は、j=1から2までj=mを除き和をとることを表している。
【0249】
式(41a)で定義された写像f(2,n):[0,1]→[0,1]によって生成される2次元空間の曲線を2次元ペアノ曲線という(非特許文献2,p.42参照)。式(41a)のf(2)は区間[0,32n]の各整数点を2次元空間の正方形[0,3n2の各整数格子点に写像する写像関数f(2,n):[0,32n]→[0,3n2と考えることもできる。
【0250】
そこで、この写像関数f(2,n)をN次元に拡張し、一般に、N次元ペアノ曲線を生成する写像関数f(N,n)を次式(42a)で定義する。写像関数f(N,n)が単射であること、及び写像f(N,n):[0,3Nn]→[0,3Nによって生成されるN次元空間曲線が連続空間充填曲線であることは数学的に証明することができる。
【0251】
【数42】

【0252】
図22に写像f(2,n):[0,32n]→[0,3によって生成される2次元ペアノ曲線の一例を示す。図23に写像f(3,n):[0,33n]→[0,3によって生成される3次元ペアノ曲線の一例を示す。
【0253】
(2)N次元ペアノ型曲線
式(42a),(42b)は、各リテラルが3進数で表現されているが、これを一般のq進数にまで拡張した写像関数fq(N,n)を次式により定義する。
【0254】
【数43】

【0255】
式(43a)で定義された写像f(N,n):[0,qNn]→[0,qNによって生成されるN次元空間の曲線を「N次元q進ペアノ型曲線」と呼ぶ。qが奇数の場合、N次元q進ペアノ型曲線は連続空間充填曲線であることが数学的に証明される。qが偶数の場合には、N次元q進ペアノ型曲線は不連続空間充填曲線となる。q=3の場合がN次元ペアノ曲線である。
【0256】
図24は、式(43a),(43b)による分割指数nのN次元q進ペアノ型曲線の生成方法を具体的に示したフローチャートである。図25は、2次元5進ペアノ型曲線、図26は、2次元7進ペアノ型曲線の例を示す図である。尚、図24のフローチャートはPADにより表している。
【0257】
(3)ターミナル/インダクション・テーブルによるN次元q進ペアノ型曲線の生成
点sを起点とする分割指数nのN次元q進ペアノ型曲線をC(n,N)と記す(qは固定値として省略する)。曲線C(n,N)は、一辺の長さがqのN次元超立方体HC(n,N)内のqnN個の整数格子点を充填する曲線である。従って、曲線C(n,N)はこれらのqnN個の整数格子点の点列として、次のように表すことができる。
【0258】
【数44】

【0259】
ここで、各c(n,N)(a)(a=0,1,…,qnN−1)は超立方体HC(n,N)内の整数格子点の位置ベクトル、sは曲線C(n,N)の始点の位置ベクトル、eは曲線C(n,N)の終点の位置ベクトルを表す。sは超立方体HC(n,N)の2個の頂点のうちの何れかである。また、ペアノ型曲線の性質により、eはsに対して対角位置の頂点となる。
【0260】
今、分割指数nの曲線C(n,N)[s]が与えられているとする。分割指数(n+1)の曲線C(n+1,N)[s]は、曲線C(n,N)[s]の各整数格子点を分割指数1のN次元q進ペアノ型曲線で置き換えることによって生成することができる。従って、曲線C(n+1,N)[s]は次式のように表すことができる。
【0261】
【数45】

【0262】
ここで、演算子「‖」はリテラル連結演算子である(例えば、01‖201=01201)。
【0263】
それぞれの曲線C(1,N)[s](k=0,1,…,qnN−1)の選び方は任意であるが、曲線C(n+1,N)[s]が連続であるという条件を課した場合(この場合、qは奇数でなければならない。)には、各曲線C(1,N)[s]の始点sと終点eは一意的に決定される。尚、始点sと終点eが同じ曲線C(1,N)[s]の種類の数(位数)は、N次元超立方体の1つの頂点から出る辺の数Nに等しい。
【0264】
今、整数格子点c(n,N)(k)から整数格子点c(n,N)(k+1)へ向かう単位ベクトルをv=c(n,N)(k+1)−c(n,N)(k)とする。曲線C(n+1,N)[s]が連続の場合、曲線C(1,N)[sk+1]の始点sk+1は曲線C(1,N)[s]の終点eのv方向の座標成分を超立方体HC(1,N)内で反転させたものであるので、始点sk+1は次式により決定される。
【0265】
【数46】

【0266】
ここで、関数K[v](e)はベクトルeのv方向の成分のリテラルを反転するリテラル反転関数を表す。尚、式(46)において、vの成分が負の場合、e+vの成分が負となる場合があるが、その場合にはqを加えてsk+1の各成分は区間[0,q−1]内の値となるように規格化するものとする。
【0267】
また、曲線C(1,N)[s]の終点eは始点sの対角頂点なので、終点eは次式により決定される。
【0268】
【数47】

ここで、関数K(s)はベクトルsのすべての成分のリテラルを反転するリテラル反転関数を表す。
【0269】
従って、曲線C(n+1,N)[s]が連続であるという条件を課した場合には、曲線C(1,N)[sk+1]の始点sk+1は次式によって一意的に決定される。
【0270】
【数48】

【0271】
このように、ペアノ型曲線の場合、始点が決まると終点が一意的に決まるので、生成可能な曲線数はヒルベルト曲線よりも少なく、次式のようになる。
【0272】
【数49】

【0273】
尚、始点の変更は、式(23a),(23b)により生成されるN次元q進ペアノ型曲線C(n,N)[0]の座標軸を置換すれば、容易に行うことができる。また、始点から出る方向ベクトルの変更は、元となるN次元q進ペアノ型曲線C(n,N)[s]の始点から2番目の格子点への方向ベクトルの軸の座標と、変更したい軸の座標について、q進数リテラル反転をすることにより、容易に行うことができる。
【0274】
以上のようなペアノ型曲線の自己相似性を利用することにより、ヒルベルト曲線の場合と同様に、以下のようにターミナル/インダクション・テーブルを用いて分割指数nのN次元q進ペアノ型曲線を生成することができる。図27に、N次元q進ペアノ型曲線C(n,N)のターミナル・テーブルの計算アルゴリズム、図28に、N次元q進ペアノ型曲線C(n,N)のインダクション・テーブルの計算アルゴリズムを示す。図27,図28のフローチャートはPADにより表している。尚、図27において、原始曲線sは、図24のアルゴリズムにより分割指数1のN次元q進ペアノ型曲線を計算することにより求めることができる。
【0275】
(例3)
q=3,N=2の場合、ターミナル・テーブル及びインダクション・テーブルは、例えば、(表5),(表6)のようになる。
【0276】
【表5】

【0277】
【表6】

【0278】
この場合、シード曲線の数は2×N=8であり、シード曲線テーブルは(表7)のようになる。
【0279】
【表7】

(例終り)
【0280】
(例4)
q=3,N=3の場合、ターミナル・テーブル及びインダクション・テーブルは、例えば、(表8),(表9)のようになる。
【0281】
【表8】

【0282】
【表9】

この場合、シード曲線の数は2×N=24であり、シード曲線テーブルは(表10)のようになる。
【0283】
【表10】

(例終り)
【0284】
ターミナル/インダクション・テーブルを用いた、1次元序数空間内の序数iと、これをN次元q進ペアノ型曲線により写像したN次元空間内の点Aとの間の変換は、実施例1で説明した関数Hil1(γM, M, iA),Hil1(γM, M, a)と全く同様にして行うことができる。すなわち、ヒルベルト曲線のターミナル/インダクション・テーブルを、N次元q進ペアノ型曲線のターミナル/インダクション・テーブルに置き換えるだけでよい。尚、この場合、アドレスa及び序数iの各リテラルはq進数のリテラルであるので、式(19)は次式(50)のように書き換えられることになる。
【0285】
【数50】

【0286】
(4)さらなる一般化
ここまでは、暗号処理に使用する空間充填曲線を連続空間充填曲線に限定して説明してきたが、本発明に係る暗号処理技術で利用する空間充填曲線は、必ずしも連続である必要はない。不連続空間充填曲線を使用する場合にも、上述のシード曲線テーブル及びターミナル/インダクション・テーブルを用いた自己相似曲線の生成手法をそのまま適用することが可能である。なぜならば、上述のターミナル/インダクション・テーブルによる再帰的な曲線生成演算は、ターミナル曲線の始点と終点さえ確定していれば、その中間の格子点の配列が如何なるものであるかは問われないからである。
【0287】
例えば、(表10)のシード曲線テーブルにおいて、各行の曲線について始点(アドレス1)と終点(アドレス27)以外の中間格子点をランダムに置換することにより、任意の自己相似な空間充填曲線に変更することができる。この場合、シード曲線の全数は、2に(3−2)個の数の置換の数を掛けた値となり、全部で2・(3−2)!となる。
【0288】
なお、シード曲線テーブル又はターミナル・テーブルの曲線を不連続空間充填曲線とする場合には、インダクション・テーブルの生成の際に注意が必要である。例えば、ターミナル・テーブル内のターミナル曲線T(term)が不連続空間充填曲線であったとする(図27(a)参照)。この場合、ターミナル曲線T(term)上には、隣接点間の距離が1より大きい不連続隣接点ペアが必ず2組以上生じる。そこで、このような不連続隣接点ペアを(Tm,i(term),Tm,i+1(term))とする。点Tm,i(term)と点Tm,i+1(term)はN次元整数空間では隣接していないため、不連続点Tm,i+1(term)を置き換えるターミナル曲線Tm,i+1(ind)(図28参照)の始点の位置は、予め決められた何らかの始点決定規則なくしては、一意的には決定できないことに注意する必要がある(なお、ペアノ型曲線では、不連続点Tm,i(term)を置き換えるターミナル曲線Tm,i(ind)(図28参照)の終点の位置は始点から一意的に決定されるが、ヒルベルト曲線の場合には、ターミナル曲線Tm,i(ind)の終点の位置も一意的には決定できないことになる)。
【0289】
そこで、例えば、図28のようなインダクション・テーブル生成のアルゴリズムを使用する場合には、図28のステップS90における「v←Tm,i+1(term)−Tm,i(term)」の計算を「v←(Tm,i+1(term)−Tm,i(term)) mod 2(但し、mod演算はベクトルの各成分に対して行う)」に変更し、ステップS91の後に「if s=q−1 thens←q」(S91−1)及び「if s=1 thens←0」(S91−2)の条件演算式を追加すればよい。「mod 2」演算により、方向ベクトルvの各成分vは0,1,−1のいずれかとなるため、ステップS91〜S92の演算により、不連続隣接点ペア(Tm,i(term),Tm,i+1(term))が生じた場合でも、不連続点Tm,i+1(term)を置き換えるターミナル曲線Tm,i+1(ind)の始点は一意的に決定され、このような始点不確定の問題は回避される。
【実施例5】
【0290】
実施例5及び実施例6では、本発明に係る暗号処理技術を共通鍵暗号方式に適用した例について説明する。本実施例5では、共通鍵暗号方式として、DES(Data Encryption Standard)アルゴリズム(非特許文献3参照)に本発明を適用した例を説明する。
【0291】
〔1〕通常のDES方式による暗号化アルゴリズム
(1)DES暗号化アルゴリズム
最初に、標準的な暗号化方式として広く使用されているDES方式の暗号化アルゴリズムについて簡単に説明する(非特許文献3参照)。DES方式では、2進数数字{0,1}の列からなるブロック長64ビットの平文p∈{0,1}64が、ブロック長64ビットの暗号文c∈{0,1}64に暗号化される。DES方式は、Feistel暗号を改良したものとなっている。
【0292】
図29は、DES方式による暗号化アルゴリズムの流れを示すブロック図である。図29において、平文p及び暗号文cはブロック長64ビットの2進数字列{0,1}64、鍵Kはブロック長64ビットの2進数字列{0,1}64である。図中において矢印に付された数値は、各矢印に沿って送られる数字ブロックのブロック長(ビット数)を表している。また、矩形ボックスは数値ブロック、グレーで塗られた帯直円形ボックスは関数を表している。DES方式による暗号化アルゴリズムは、大きく分けて、初期置換、Feistel構造による暗号化、最終置換の3段階から構成される。各段階の概略は、以下の通りである。
【0293】
(1.1)初期置換
最初の段階として、平文pに対して初期置換IPを行う。初期置換IPは固定されており、次式で表される64ビットのビット置換である。ここで、次式の置換関数IP(p)の演算式の表記法は、平文pを2進数表記したときのリテラルをp=p...p6364とすると、IP(p)=p585042...p15に置換されることを意味している。
【0294】
【数51】

【0295】
(1.2)Feistel構造
次に、IP(p)をブロック長32ビットの2つのブロックL,Rに分割する。すなわち、次式で表されるようなブロックL,Rに分割する。演算子「‖」はリテラル連結演算子である。
【0296】
【数52】

【0297】
次いで、ブロックL,Rを、16巡回のFeistel構造の暗号方式により暗号化し、暗号化ブロックL16,R16を生成する。この暗号化は、次のようにして反復実行される(図29参照)。
【0298】
【数53】

【0299】
ここで、K(j=0,1,2,…,15)は鍵Kから生成される巡回鍵、関数F(R,K)は内部ブロック暗号の暗号化関数である。これらは後述する。
【0300】
(1.3)最終置換
最後に、ブロック長32ビットの暗号化ブロックL16,R16を連結してブロック長64ビットの数字列L16‖R16とし、この数字列L16‖R16に対して最終置換IP−1を行うことにより暗号文c∈{0,1}64を生成する。
【0301】
【数54】

【0302】
最終置換IP−1(x)は、次式により表され、置換IPの逆置換である。ここで、変数xを2進数表記したときのリテラルをx=x...x6364とすると、IP−1(x)=x4048...x5725となる。
【0303】
【数55】

【0304】
(2)内部ブロック暗号F
図29の各内部ブロック暗号Fは、図30に示すアルゴリズムにより表される。図30において、変数R及び巡回鍵K(i=0,1,…,15)は、図29の変数R及び巡回鍵Kにそれぞれ相当する。また、図中において矢印に付された数値は、各矢印に沿って送られる数字ブロックのブロック長(ビット数)を表している。変数Rはブロック長32のビット列であり、巡回鍵Kはブロック長48のビット列である。
【0305】
(2.1) まず、拡大関数E:{0,1}32→{0,1}48により、ブロック長32の変数R∈{0,1}32をブロック長48の変数R(R)∈{0,1}48に拡大する。拡大関数Eは、次式により表されるビット写像関数である。ここで、次式の写像関数E(R)の演算式の表記法は、変数Rを2進数表記したときのリテラルをR=Ri,1i,2i,3...Ri,31i,32とすると、E(R)=Ri,32i,1i,2...Ri,32i,1に各ビットが写像されることを意味している。
【0306】
【数56】

【0307】
(2.2) 次に、ブロック長48ビットの変数E(R)とブロック長48ビットの巡回鍵Kとの(ビット毎の)排他的論理和を計算することにより、ブロック長48ビットの変数Bを生成する。
【0308】
【数57】

【0309】
(2.3) 変数Bをブロック長6ビットの8個のブロックB,B,B,B,B,B,B,Bに分割する。
【0310】
【数58】

【0311】
(2.4) ブロック長6ビットの各ブロックB(j=1,2,…,8)を、それぞれ、Sボックスと呼ばれる関数S:{0,1}→{0,1}(j=1,2,…,8)により、ブロック長4ビットの変数C(j=1,2,…,8)に変換する。ここで、各Sボックスは、次のような4行16列の次式で表される非線形写像関数である。なお、下記の各SボックスSの各成分は10進数で表示している。
【0312】
【数59】

【0313】
上記Sボックスによる演算は次のように行われる。上式のSボックスSのα行β列の成分をS[α,β]と記す。変数B(j=1,2,…,8)の2進数表記したリテラルをB=bj,1j,2j,3j,4j,5j,6と記す。bj,k∈{0,1}(k=1,2,…,6)である。これらのリテラルを用いて行指数ξ=bj,1j,6及び列指数η=bj,2j,3j,4j,5を構成し、次式によって変数Cを算出する。なお、変数Cは、上式のSボックスSの成分S[ξ,η]を4ビットの2進数で表記したものである。
【0314】
【数60】

【0315】
(2.5) 8個の変数C(j=1,2,…,8)を連結し、ブロック長32ビットの変数Cを生成する。
【0316】
【数61】

【0317】
(2.6) 最後に、変数Cの各ビットの順序を次式の置換関数Pによりビット置換し、暗号化した変数F(R,K)=P(C)を算出する。ここで、変数Cを2進数表記したときのリテラルをC=c...c3132とすると、P(C)=c1610...c25となる。
【0318】
【数62】

【0319】
(3)巡回鍵Kの生成
図29の各巡回鍵K(i=0,1,…,15)は、鍵Kに基づいて、図31のアルゴリズムによって生成される。図31において、RK〜RK15の部分は、図29の同符号を付した関数ボックスの部分に相当する。図31において、関数ボックスLSは、左巡回シフト関数を表している。
【0320】
(3.1) まず、ブロック長64ビットの鍵K∈{0,1}64に対して、次式のようなビット写像関数PC1:{0,1}64→{0,1}28×{0,1}28により、ブロック長28ビットの2つの変数(C,D)=PC1(K)を生成する。
【0321】
【数63】

【0322】
(3.2) 得られた変数(C,D)を連結し、ブロック長56ビットの変数C‖Dに対して、次式のようなビット写像関数PC2により、ブロック長48ビットの巡回鍵K=PC2(C‖D)を生成する。
【0323】
【数64】

【0324】
(3.3) 次に、以下の(3.3.1)〜(3.3.3)の処理を15巡反復して繰り返すことにより、鍵K(i=1,2,…,15)を順次生成する。
【0325】
(3.3.1) 変数Ci−1(i=1,2,…,15)に対し、左巡回シフトを施すことにより、変数Cを生成する。ここで、シフト量は、i∈{1,2,9,16}のときは1、それ以外のときは2とする。
【0326】
【数65】

【0327】
(3.3.2) 同様に、変数Di−1(i=1,2,…,15)に対し、左巡回シフトを施すことにより、変数D=LS(Di−1)を生成する。ここで、シフト量は、i∈{1,2,9,16}のときは1、それ以外のときは2とする。
【0328】
(3.3.3) 得られた変数(C,D)を連結し、ブロック長56ビットの変数C‖Dに対して、上述のビット写像関数PC2により、ブロック長48ビットの巡回鍵K=PC2(C,D)を生成する。
【0329】
(4)DES復号アルゴリズム
DES暗号の復号は、巡回鍵K〜K15を逆方向の順序で使用すればよい。図32にDES暗号の復号アルゴリズムを示す。
【0330】
〔2〕本発明を適用した改良DES方式による暗号化アルゴリズム
(1)改良DES暗号化アルゴリズム
次に、上述のDES暗号化方式に本発明を適用した実施例5の暗号化方式について説明する。図33はDES暗号化方式に本発明を適用した暗号化方式のアルゴリズムの流れを示すブロック図である。本実施例に係る暗号化方式においては、上述のDES方式のFeistel構造の格段において、内部ブロック暗号Fにより変数R(i=0,1,…,15)を変換した後、生成された変数F(R,K)を、鍵曲線Hを用いて暗号化を行う内部ブロック暗号Gによりさらに変換した後に、G(F(R),H)と変数Lとの排他的論理和をとることにより次段の変数Ri+1又はL16を生成する。すなわち、式(53a),(53b)が、それぞれ次式(66a),(66b)に置き換えられる。それ以外は、上述したDES方式と同様である。
【0331】
【数66】

【0332】
(内部ブロック暗号G)
ここで、新たに追加した内部ブロック暗号Gにおいて、本発明に係る空間充填曲線を使用した暗号化方法が使用される。以下、内部ブロック暗号Gにおける演算方法について具体的に説明する。
【0333】
まず、内部ブロック暗号関数Gに入力される変数F(R,K)をYとおく。Y∈{0,1}32である。最初に、変数Yをブロック長MビットのN個のブロックY,…,Yに等分割する。Nは32の約数2,4,8,16の何れかを選択可能であるが、ここではN=8とするのが適当である。そして、分割した各ブロックを成分とするN次元のベクトルYを生成する。
【0334】
次に、鍵曲線HによりN次元ベクトルYを1次元序数空間内の序数iに写像する関数L(Y)により、ベクトルYから序数iを算出する。ここで、序数iは32ビットのスカラー変数である。関数L(Y)は、ベクトルYを、鍵曲線Hにより生成される、一辺の長さがM(=4)のN次元超立方体を充填する空間充填曲線C(M,N)におけるベクトルYに対応する点の序数iに写像する関数である。関数L(Y)としては、例えば、実施例1で説明したようなヒルベルト曲線を用いた写像関数を用いることができる。また、ヒルベルト曲線の代わりに、実施例4で説明したペアノ型曲線やその他の空間充填曲線を使用した写像関数を用いることもできる。
【0335】
次いで、序数iをスカラー関数であるエンコード関数fにより変換した後、f(i)を、関数Lの逆関数L−1により変換し、N次元ベクトルV=(V,…,V)を生成する。そして、ベクトルVの各成分V,…,Vを連結してこれをG(Y,H)とする。即ち、次式(67a)〜(67d)の演算によってG(Y,H)は計算される。
【0336】
【数67】

尚、エンコード関数fとしては、例えば、実施例1で説明したような関数を使用することができる。
【0337】
(2)改良DES復号アルゴリズム
図34はDES暗号化方式に本発明を適用した復号方式のアルゴリズムの流れを示すブロック図である。復号についても、同様に、上述のDES方式のFeistel構造の格段において、内部ブロック暗号Fにより変数R(i=16,15,…,1)を変換した後、生成された変数F(R,K)を、鍵Hを用いて暗号化を行う内部ブロック暗号Gによりさらに変換した後に、G(F(R),H)と変数Lとの排他的論理和をとることにより次段の変数Ri−1又はLを生成する。すなわち、次式のようになる。
【0338】
【数68】

【0339】
〔3〕実施例5に係る暗号化装置及び復号装置
図36は、実施例5に係る暗号処理装置の構成を表すブロック図である。尚、図33,図34から分かるように、本実施例の暗号化方式と復号方式のアルゴリズムは対照的な構造をしているため、暗号化装置及び復号装置は図35のように同じ構成となる。
【0340】
実施例5に係る暗号処理装置2は、データ入力部41、処理データ記憶部42、巡回鍵記憶部43、鍵曲線記憶部44、左ブロック記憶部45、右ブロック記憶部46、初期置換部47、巡回鍵生成部48、内部ブロック関数F演算部49、内部ブロック関数G演算部50、EXOR演算部51、ブロック交換部52、最終置換部53、及びデータ出力部54を備えている。尚、暗号処理装置2は、ハードウェア的に暗号化通信の専用装置として構成することも可能であるが、パーソナル・コンピュータ等の汎用のコンピュータにプログラムをロードして実行することによりソフトウェア的に暗号処理装置2を実現するようにしてもよい。
【0341】
データ入力部41は、暗号化を行う平文p、復号を行う暗号文c、DES暗号で使用するDES暗号鍵K,K’、本発明に係る暗号方式で使用する曲線鍵Hを入力する部分である。先に説明した通り、平文p及び暗号文cは二進数数字{0,1}からなるブロック長64ビットの数字ブロックである。DES暗号鍵K,K’は二進数数字{0,1}からなるブロック長64ビットの数字ブロックである。曲線鍵Hは二進数数字{0,1}からなるブロック長32ビットの数字ブロックである。
【0342】
処理データ記憶部42は、データ入力部41から入力された平文p又は暗号文cを記憶する。巡回鍵記憶部43は、データ入力部41から入力されたDES暗号鍵K,K’を記憶する。鍵曲線記憶部44は、データ入力部41から入力された曲線鍵Hを記憶する。また、左ブロック記憶部45及び右ブロック記憶部46は、先に説明したFeistel構造の格段で使用するブロック長32ビットの2つのブロックL,R(i=0,1,…,16)を記憶する。
【0343】
初期置換部47は、図33,図34における初期置換IPの演算を行うモジュールである。巡回鍵生成部48は、図33,図34における関数ボックスRK〜RK15の部分の演算(即ち、DES暗号鍵K,K’に基づき巡回鍵K〜K15を生成する演算)を行うモジュールである。
【0344】
内部ブロック関数F演算部49は、図33,図34における内部ブロック関数Fの演算を行うモジュールである。内部ブロック関数F(R,K)(i=0,1,…,15)の演算については、上記〔1〕(2)において説明した通りである。尚、暗号化の際には、図33のようにi=0,1,…,15に対してそれぞれj=0,1,…,15となり、復号の際には図34のようにi=0,1,…,15に対してそれぞれj=15,14,…,0となる。
【0345】
内部ブロック関数G演算部50は、図33,図34における内部ブロック関数Gの演算を行うモジュールである。内部ブロック関数Gの演算については、上記〔2〕(1),(2)において説明した通りである。
【0346】
EXOR演算部51は、図33,図34におけるEXORブロックに相当し、式(66a),(66b)及び式(68b),(68c)に示したように、左ブロック記憶部45に記憶された数字ブロックLと、内部ブロック関数G演算部50が出力する数字ブロックZ=G(F(R,K),H)との排他的論理和の演算を行うモジュールである。
【0347】
ブロック交換部52は、図33,図34又は式(66a),(66b)及び式(68b),(68c)に示したように、i=0,1,…,14の場合には右ブロック記憶部46に記憶された数字ブロックRを左ブロック記憶部45に格納するとともに、EXOR演算部51が出力する排他的論理和を右ブロック記憶部46に格納する。i=15の場合には、数字ブロックRの移動は行わず、EXOR演算部51が出力する排他的論理和を左ブロック記憶部45に格納する。
【0348】
最終置換部53は、図33,図34における最終置換IP−1の演算を行うモジュールである。
【0349】
データ出力部54は、最終置換部53の演算結果を、暗号化文c又は平文pとして出力する。
【0350】
これら各部の処理動作については、図33,図34のアルゴリズムで説明した通りであり、重複するため省略する。
【0351】
図36は、図35における内部ブロック関数G演算部50の構成を表すブロック図である。内部ブロック関数G演算部50は、共通モジュール4、共通鍵入力部21’、暗号化倍数生成部22、平文コード点生成部23、暗号コード生成部24、及び暗号コード出力部25を備えている。共通モジュール4、暗号化倍数生成部22、平文コード点生成部23、暗号コード生成部24、及び暗号コード出力部25については、実施例1の図2において同符号を付した構成部分と同様のものであり、説明は省略する。
【0352】
共通鍵入力部21’は、鍵曲線記憶部44に記憶された曲線鍵Hを読み出して暗号コード生成部24へ入力するモジュールである。
【0353】
内部ブロック関数F演算部49が生成するブロック長32ビットの数字ブロックY=F(R,K)は平文コード点生成部23へ入力される。平文コード点生成部23は、数字ブロックYを式(67a)のように、ブロック長4ビットの数字ブロックY,Y,…,Yに等分割し、式(67b)のように各数字ブロックY,Y,…,Yを成分とする8次元ベクトルYを生成する。これが、実施例1で説明した平文コード点に相当する。
【0354】
暗号コード生成部24は、ベクトルYと曲線鍵Hに基づいて、式(67c)により暗号化点の8次元ベクトルV=(V,V,…,V)を算出し、ベクトルVの各成分を式(67d)により連結してZ=G(Y,H)を算出する。暗号コード生成部24における具体的な演算処理は、実施例1で説明した通りである。
【0355】
暗号コード出力部25は、暗号コード生成部24が算出した数字ブロックZ=G(Y,H)をEXOR演算部51へ出力する。
【0356】
DES方式においては、Sボックス演算が唯一の非線形な部分であり、このSボックスの非線形性が暗号の安全性を向上させている。本発明に係る空間充填曲線を利用した暗号方式も非線形写像が利用されているため、本発明に係る空間充填曲線を利用した暗号方式を、共通鍵暗号であるDES暗号方式のFeistel構造の格段に適用することによって、暗号の安全性をさらに向上させることができる。
【0357】
なお、本実施例では、DES暗号のFeistel構造(図33,図34)におけるF関数の後に、本発明の空間充填曲線暗号化演算を行うG関数を追加した構成としたが、F関数の代わりにG関数を使用する構成とすることもできる。この場合、図33,図34におけるF関数を除けばよい。空間充填曲線暗号化演算は非線形演算であるため、F関数の代わりにG関数を使用する構成としても、暗号の安全性は十分に確保される。
【実施例6】
【0358】
本実施例6では、共通鍵暗号方式として、AES(Advanced Encryption Standard)アルゴリズム(非特許文献4参照)に本発明を適用した例について説明する。
【0359】
〔1〕通常のAES方式による暗号化アルゴリズム
(1)暗号化アルゴリズム
最初に、標準的な暗号化方式として広く使用されているAES方式の暗号化アルゴリズムについて簡単に説明する(非特許文献4参照)。AES方式では、2進数数字{0,1}の列からなるブロック長128ビットの平文p∈{0,1}128が、ブロック長128ビットの暗号文c∈{0,1}128に暗号化される。共通鍵Kとしては、鍵長Nが128ビット,192ビット,256ビットのものの何れかを選択することができる。鍵長Nに応じて、内部ブロック暗号(ラウンド関数)の繰り返し実行回数であるラウンド数Nが決められており、鍵長Nが128ビット,192ビット,256ビットに対し、ラウンド数Nがそれぞれ10,12,18となる。
【0360】
(1.1)全体の流れ
図37は、AES方式による暗号化アルゴリズムの流れを示すブロック図である。図37において、平文p及び暗号文cはブロック長128ビットの2進数字列{0,1}128、鍵Kはブロック長Nビットの2進数字列{0,1}NKである。図中において矢印に付された数値は、各矢印に沿って送られる数字ブロックのブロック長(ビット数又はバイト数)を表している。また、矩形ボックスは数値ブロック、グレーで塗られた帯直円形ボックスは関数を表している。AES方式による暗号化アルゴリズムは、大きく分けて、初期処理、ラウンド処理の2段階から構成される。各段階の概略は、以下の通りである。
【0361】
(1.2)初期処理
最初の段階として、ブロック長128ビットの平文pを、次式のように、16個の1バイト数字列pi,j(i,j=0,1,2,3)に分割し、各数字列pi,jを成分とする4行4列の状態配列Pを構成する。AES方式では、このような4行4列の状態配列が処理単位となる。
【0362】
【数69】

【0363】
上記状態配列Pと4×4バイトの巡回鍵配列RKとのビット毎の排他的論理和をとることにより、次式のように初期の状態配列Bを算出する。なお、巡回鍵配列RK(r=0,1,…,N)は、共通鍵Kに基づき鍵拡張関数により算出される。鍵拡張関数の詳細については、本発明とは直接関係ないため説明は省略する。
【0364】
【数70】

【0365】
(1.3)ラウンド処理
次に、図37のラウンド処理における各ラウンド関数RF(r=1,2,…,N)について説明する。図38は、図37の各ラウンド関数RFにおける暗号処理アルゴリズムを表すブロック図である。各ラウンドr(r=1,2,…,N)においては、ラウンド関数RFには4×4バイトの状態配列Br−1が入力される。ラウンド関数RF(1≦r≦N−1)では、状態配列Br−1に対して、(a)バイト置換(BubByte),(b)行シフト(ShiftRows),(c)列内ミックス(MixColumns),(d)巡回鍵加算(AddRoundKey)の4つの操作が順次実行される(図38(a))。最後のラウンド関数RFNrでは、(a),(b),(d)の処理のみが実行される(図38(b))。以下、(a)〜(d)の各処理について簡単に説明する。
【0366】
(1.3.1)バイト置換(SubByte)
図38(a),(b)のSubByte関数は、状態配列Br−1の各成分に対して、Sボックス置換により非線形変換を行い状態配列Mを生成する。生成される状態配列Mの各成分をm1(i,j)(i,j=0,1,2,3)と記す。このSボックス置換は次のようにして行われる。
【0367】
まず、入力される1バイト(8ビット)の数字b∈{0,1}(b=br−1(i,j)(i,j=0,1,2,3))を、P(X)=X+X+X+X+1を法多項式とする拡大体GF(2)の元とみなして、その逆元xを算出する。次に、逆元x∈{0,1}を体GF(2)上の8次元ベクトルx=(x,x,x,x,x,x,x,x)と考えて、次式(71b)により体GF(2)上の8次元ベクトルy=(y,y,y,y,y,y,y,y)を算出し、ベクトルyの各成分を連結して得られる8ビットのy=yをSボックス置換の出力とする。
【0368】
【数71】

【0369】
実際に実装する場合には、上記式(71a),(71b)を予め計算して求められる、次表のようなルックアップ・テーブルを使用する。
【0370】
【表11】

【0371】
表11のi行j列(i,j=0,1,…,15)の要素をS[i,j]と記す。表11において各要素の数値は16進数で表記されている。入力数字b(b=br−1(i,j)(i,j=0,1,2,3))を2進数で表記したときのリテラルをb=bとし、行指数をξ=b、列指数をη=bを構成し、m=S[ξ,η]により出力変数m(m=m1(i,j)(i,j=0,1,2,3))を算出する。尚、出力変数mは、表要素S[ξ,η]を2進数で表記した数字列である。こうして求められた各変数m1(i,j)(i,j=0,1,2,3)を(i,j)成分とする4×4配列を状態配列Mとする。
【0372】
(1.3.2)行シフト(ShiftRows)
図38(a),(b)のShiftRows関数は、上記状態配列Mの各行に対して左巡回シフトを行う関数である。状態配列MをShiftRows関数により変換して得られる状態配列をM、状態配列Mの各(i,j)成分をm2(i,j)と記す。ShiftRows関数は、状態配列Mの2行目は左へ1、3行目は左へ2、4行目は左へ3だけ巡回シフトする。すなわち、ShiftRows関数をLSRと記すと、ShiftRows関数は次式で表される。
【0373】
【数72】

【0374】
(1.3.3)列内ミックス(MixColumns)
図38(a)のMixColumns関数は、上記状態行列Mの各列に対して成分混合を行う。MixColumn関数をMXCと記す。状態配列MをMixColumns関数により変換して得られる状態配列をMと記す。MixColumns関数は、状態配列Mの4つの列に対して、それぞれ、次のような操作を行う関数である。
【0375】
状態配列Mの第j列の成分を(m2(0,j),m2(1,j),m2(2,j),m2(3,j))(m2(i,j)∈{0,1})とする。この4つの要素のそれぞれをGF(2)の元とみなす。また、要素(m2(0,j),m2(1,j),m2(2,j),m2(3,j))を係数とする3次多項式をM(X)とし、3次多項式M(X)を次式により算出する。
【0376】
【数73】

【0377】
このようにして計算される3次多項式M(X)の各係数(m3(0,j),m3(1,j),m3(2,j),m3(3,j))を、新たな状態配列Mの第j列の4つの成分とする。実際に実装する場合には、MixColumns関数MXCは、上記計算と等価な次式の計算により算出される。
【0378】
【数74】

【0379】
(1.3.4)巡回鍵加算(AddRoundKey)
図38(a),(b)のAddRoundKey関数は、入力される状態配列M(r=Nのときは状態配列M)と巡回鍵配列RKとの排他的論理和をとり、次段の状態配列Bを生成する。配列B,RKの各要素をbr(i,j),kr(i,j)∈{0,1}(i,j=0,1,2,3)と記す。状態配列Bは次式により算出される。
【0380】
【数75】

【0381】
(2)復号アルゴリズム
図39は、AES方式による復号アルゴリズムの流れを示すブロック図である。図40は、図39の各ラウンド関数RF−1における暗号処理アルゴリズムを表すブロック図である。
【0382】
復号は、暗号化処理の逆を行えばよい。図39において、関数RF−1は、図37,図38のラウンド関数RFの逆関数であり、図40のようなアルゴリズムで表される。図40において、InvMixColumns関数、InvShiftRows関数、InvSubByte関数は、それぞれ、図38のMixColumns関数、ShiftRows関数、SubByte関数の逆関数である。尚、InvSubByte関数では、Sボックス置換の逆置換を実行するが、次表のようなルックアップ・テーブルが使用される。
【0383】
【表12】

【0384】
表12において、i行j列の表要素をS−1[i,j]と記す。表12の各要素は16進数で表記されている。入力数字m(m=m1(i,j)(i,j=0,1,2,3))を2進数で表記したときのリテラルをm=mとし、行指数をΞ=m、列指数をZ=mを構成し、b=S[Ξ,Z]により出力変数b(b=br−1(i,j)(i,j=0,1,2,3))を算出する。尚、出力変数bは、表要素S[Ξ,Z]を2進数で表記した数字列である。こうして求められた各変数br−1(i,j)(i,j=0,1,2,3)を(i,j)成分とする4×4配列を状態配列Br−1とする。
【0385】
〔2〕AES方式に本発明を適用した暗号化アルゴリズム
本発明に係る空間充填曲線を利用した暗号方式を、上記AES方式に組み込む場合、各ラウンド関数のSubByte関数の後段に、空間充填曲線を使用した非線形変換による内部ブロック暗号化関数Gを挿入すればよい。内部ブロック暗号化関数Gは、実施例5で説明したものと同様である。
【0386】
図41に、本実施例6の暗号化アルゴリズムにおける各ラウンド関数RFのアルゴリズムのブロック図を示す。図42に、本実施例6の復号アルゴリズムにおける各ラウンド関数RF−1のアルゴリズムのブロック図を示す。尚、暗号化アルゴリズム及び復号アルゴリズムの全体の流れは、図37,図39と同様であるため説明は省略する。図41におけるSubByte関数、ShiftRows関数、MixColumns関数、AddRoundKey関数は、図38と同様である。図42におけるInvSubByte関数、InvShiftRows関数、InvMixColumns関数、AddRoundKey関数は、図40と同様である。
【0387】
本実施例の暗号化アルゴリズムにおけるラウンド関数RFでは、SubByte関数により算出される状態配列Mを、内部ブロック暗号化関数Gにより4行4列の状態配列M’に変換し、この状態配列M’をShiftRows関数の入力とする。また、本実施例の復号アルゴリズムにおけるラウンド関数RF−1では、InvShiftRows関数により算出される状態配列M’を、内部ブロック暗号化関数Gの逆関数G−1により4行4列の状態配列Mに変換し、この状態配列MをInvSubByte関数の入力とする。それ以外については、通常のAES方式のラウンド関数RF,RF−1と同様である。
【0388】
図43は、実施例6の暗号処理装置の構成を表すブロック図である。図43の暗号処理装置は、暗号化処理機能と復号処理機能の両方の機能を有する。図43において、図35と同様の部分については、同符号を付している。巡回鍵生成部60は、図37,図39における鍵拡張関数を演算する部分であり、AES鍵Kから各巡回鍵Kを算出するモジュールである。初期・最終処理部61は、図37における初期処理及び図39における最終処理の演算を行うモジュールである。ラウンド処理部62は、図37,図38,図39,図40におけるラウンド関数RF,RF−1の演算を行うモジュールである。ラウンド処理部62は、状態配列記憶部63、バイト置換部64、行シフト部65、列内ミックス部66、及び巡回鍵加算部67から構成されている。状態配列記憶部63は、図37,図39における各状態配列B(r=0,1,…,N)及び状態配列Pを記憶する。バイト置換部64は、図41におけるSubByte関数及び図42におけるInvSubByte関数の演算を行う。暗号処理装置2は、図41における内部ブロック暗号化関数G及び図42における逆内部ブロック暗号化関数G−1関数の演算を行う。行シフト部65は、図41におけるShiftRows関数及び図42におけるInvShiftRows関数の演算を行う。列内ミックス部66は、図41におけるMixColumns関数及び図42におけるInvMixColumns関数の演算を行う。巡回鍵加算部67は、図41及び図42におけるAddRoundKey関数の演算を行う。
【0389】
図43の暗号処理装置2の構成は、図36に示した構成と同様である。暗号処理装置2は、暗号化の際には内部ブロック暗号化関数Gの演算を行い、復号の際には、内部ブロック暗号化関数Gの逆関数G−1の演算を行う。
【0390】
本実施例の場合、暗号化処理において、内部ブロック暗号化関数Gには、4行4列の状態配列Mが入力される。平文コード点生成部23は、状態配列Mの16個の成分m1(i,j)∈{0,1}(i,j=0,1,2,3)を用いて16次元のベクトルYを構成し、これを平文コード点Yとして出力する。次に、暗号コード生成部24は、鍵曲線Hにより16次元ベクトルYを1次元序数空間内の序数iに写像する関数L(Y)により、ベクトルYから序数iを算出する。ここで、序数iは32ビットのスカラー変数である。関数L(Y)は、ベクトルYを、鍵曲線Hにより生成される一辺の長さがM(=2)の16次元超立方体を充填する空間充填曲線C(M,N)におけるベクトルYに対応する点の序数iに写像する関数である。関数L(Y)としては、例えば、実施例1で説明したようなヒルベルト曲線を用いた写像関数を用いることができる。また、ヒルベルト曲線の代わりに、実施例4で説明したペアノ型曲線やその他の空間充填曲線を使用した写像関数を用いることもできる。次いで、序数iをスカラー関数であるエンコード関数fにより変換した後、f(i)を、関数Lの逆関数L−1により変換し、16次元ベクトルV=(V,V,…,V15)を生成する。そして、ベクトルVの各成分V,V,…,V15を連結してこれを出力G(M,H)とする。即ち、G(M,H)は、次式の演算によって計算される。
【0391】
【数76】

【0392】
復号の際には、内部ブロック暗号化関数Gの逆関数G−1では上記演算の逆演算が実行される。
【0393】
このように、本発明に係る空間充填曲線を利用した暗号方式を、共通鍵暗号であるSES暗号方式のラウンド処理の格段に適用することによって、暗号の安全性をさらに向上させることができる。
【実施例7】
【0394】
本実施例においては、実施例1,2で示したような公開鍵方式の暗号処理システムにおける曲線上演算部16(図2,図3参照)の演算処理に関して、他の例を用いる場合についての説明を行う。尚、本実施例における暗号化処理システムの構成については、曲線上演算部16の演算処理以外は実施例1の図1〜図3に示したものと同様であるため説明は省略する。
【0395】
〔1〕実施例1,2の暗号処理システムの動作
上述の実施例1,2の暗号処理システムの動作アルゴリズムを要約すると、次の通りである。
【0396】
(動作アルゴリズム1)
(Step1)[メッセージ送信側・メッセージ受信側]
空間充填曲線の鍵番号Kを交換。
【0397】
(Step2)[メッセージ受信側]
(1)N次元空間点Xをランダムに生成。
(2)N次元空間点Xを次式により生成。
【0398】
【数77】

【0399】
(3)X,Xを公開鍵として送信(公開)
【0400】
(Step3)[メッセージ送信側]
(1)平文コードMes(平文)をN次元空間点Y(平文点)に単射。
(2)N次元空間点V(暗号文点),X(復号鍵)を次式により生成。
【0401】
【数78】

(3)V(暗号文点),X(復号鍵)を送信。
【0402】
(Step4)[メッセージ受信側]
(1)V(暗号文点),X(復号鍵)からY(平文点)を次式により復元。
【0403】
【数79】

(2)Y(平文点)を平文コードMes(平文)に単射。
(アルゴリズム終わり)
【0404】
上記式(79)に式(77a),(78a),(78b)を代入することにより、Y(平文点)が完全に復元できるためには、エンコード関数fとデコード関数gとは互いに可換な単射関数であれば、どのような関数を選択してもよいことが分かる。
【0405】
〔2〕曲線上演算部16の演算処理の他の例1
上記動作アルゴリズム1を変形し、可換な単射関数fe2,ge2と逆関数を有する単射関数(可逆単射関数)fe1を用いて、次のような動作アルゴリズムとしても、V(暗号文点)からY(平文点)を完全に復元することが可能である。
【0406】
(動作アルゴリズム2)
(Step1)[メッセージ送信側・メッセージ受信側]
空間充填曲線の鍵番号Kを交換。
【0407】
(Step2)[メッセージ受信側]
(1)N次元空間点Xをランダムに生成。
(2)N次元空間点Xを次式により生成。
【0408】
【数80】

【0409】
(3)X,Xを公開鍵として送信(公開)
【0410】
(Step3)[メッセージ送信側]
(1)平文コードMes(平文)をN次元空間点Y(平文点)に単射。
(2)N次元空間点V(暗号文点),X(復号鍵)を次式により生成。
【0411】
【数81】

ここで、関数fe1としては、例えば、fe1(x)=ax+b mod p(a,bは定数)などの可逆単射関数を用いることができる。
(3)V(暗号文点),X(復号鍵)及び関数fe1を送信。
【0412】
(Step4)[メッセージ受信側]
(1)V(暗号文点),X(復号鍵)及び関数fe1の逆関数fe1−1からY(平文点)を次式により復元。
【0413】
【数82】

(2)Y(平文点)を平文コードMes(平文)に単射。
(アルゴリズム終わり)
【0414】
従って、実施例1において、式(11)の代わりに式(80)、式(12a),(12b)の代わりに式(81a),(81b)、式(13)の代わりに式(82a),(82b)の演算を行うように変更することが可能である。
【0415】
〔2〕曲線上演算部16の演算処理の他の例2
上記動作アルゴリズム1を変形し、次のような動作アルゴリズムとしても、V(暗号文点)からY(平文点)を完全に復元することが可能である。
【0416】
(動作アルゴリズム3)
(Step1)[メッセージ送信側・メッセージ受信側]
空間充填曲線の鍵番号Kを交換。
【0417】
(Step2)[メッセージ受信側]
(1)N次元空間点Xをランダムに生成。但し、Xは次の正則条件を満たすものとする。
【0418】
【数83】

(2)N次元空間点Xを次式により生成。
【0419】
【数84】

【0420】
(3)X,Xを公開鍵として送信(公開)
【0421】
(Step3)[メッセージ送信側]
(1)平文コードMes(平文)をN次元空間点Y(平文点)に単射。
(2)X,XからN次元空間点V(暗号文点),X(復号鍵)を次式により生成。
【0422】
【数85】

(3)V(暗号文点),X(復号鍵)を送信。
【0423】
(Step4)[メッセージ受信側]
(1)V(暗号文点),X(復号鍵),XからY(平文点)を次式により復元。
【0424】
【数86】

(2)Y(平文点)を平文コードMes(平文)に単射。
(アルゴリズム終わり)
【0425】
従って、実施例1において、式(11)の代わりに式(84)、式(12a),(12b)の代わりに式(85a)〜(85c)、式(13)の代わりに式(86a)〜(86c)の演算を行うように変更することが可能である。
【符号の説明】
【0426】
1 暗号処理システム
2 暗号処理装置
2e 暗号化装置
2d 復号装置
3 通信ネットワーク
4 共通モジュール
5 暗号コード生成モジュール
6 復号モジュール
7 通信インタフェース
8 平文コード入力部
9 平文コード出力部
11 シード曲線テーブル記憶部
11’ 鍵曲線記憶部
12 曲線演算テーブル記憶部
13 ターミナル・テーブル初期化部
14 シード曲線設定部
15 インダクション・テーブル生成部
16 曲線上演算部
17 パラメータ交換部
17’ 鍵番号交換部
21 公開鍵入力部
21’ 共通鍵入力部
22 暗号化倍数生成部
23 平文コード点生成部
24 暗号コード生成部
25 暗号コード出力部
31 復号倍率数生成部
32 公開鍵生成部
33 暗号コード入力部
34 復号演算部
41 データ入力部
42 処理データ記憶部
43 巡回鍵記憶部
44 鍵曲線記憶部
45 左ブロック記憶部
46 右ブロック記憶部
47 初期置換部
48 巡回鍵生成部
49 内部ブロック関数F演算部
50 内部ブロック関数G演算部
51 EXOR演算部
52 ブロック交換部
53 最終置換部
54 データ出力部
60 巡回鍵生成部
61 初期・最終処理部
62 ラウンド処理部
63 状態配列記憶部
64 バイト置換部
65 行シフト部
66 列内ミックス部
67 巡回鍵加算部

【特許請求の範囲】
【請求項1】
入力される平文コードから暗号コードを生成する暗号化装置、及び前記暗号化装置が生成する前記暗号コードを復号して前記平文コードを復元する復号装置を備えた暗号処理システムであって、
前記暗号化装置は、
N次元整数空間内の所定の部分空間HCを充填する空間充填曲線である鍵曲線H(k=1,2,…)を複数記憶する鍵曲線記憶手段又は前記鍵曲線Hを生成する鍵曲線生成手段と、
入力される平文コードを前記N次元整数空間の部分空間HC内の点に単射して平文コード点Yを生成する平文コード点生成手段と、
鍵番号Kを共通鍵とし、前記平文コード点Yを鍵番号Kの前記鍵曲線Hにより一次元序数空間内の序数へ単射し、該序数を所定のエンコード関数により単射変換した後、前記鍵曲線Hにより前記N次元整数空間内の部分空間HC内の点へ逆単射する演算を用いて前記暗号コードの生成を行う暗号コード生成手段と、を備え、
前記復号装置は、
前記暗号化装置と共通の鍵曲線H(k=1,2,…)を複数個記憶する鍵曲線記憶手段又は前記鍵曲線Hを生成する鍵曲線生成手段と、
前記鍵番号Kを共通鍵とし、前記暗号化装置により生成される、前記N次元整数空間の部分空間HC内の前記暗号コードを表す点を、前記鍵番号Kの前記鍵曲線Hにより一次元序数空間内の序数へ単射し、該序数を所定のデコード関数により単射変換した後、前記鍵曲線Hにより前記N次元整数空間内の部分空間HC内の点へ逆単射する演算を用いて前記平文コードの復元を行う復号演算手段と、
を備えたことを特徴とする暗号処理システム。
【請求項2】
前記N次元整数空間の部分空間HC内の点Aを、前記鍵曲線記憶手段に記憶された又は前記鍵曲線生成手段により生成される前記鍵番号Kの鍵曲線Hにより1次元序数空間内の序数iに単射する関数をL(A)、その逆関数をL−1(i)で表し、前記エンコード関数をf、前記デコード関数をgで表すと、
前記復号装置は、前記N次元整数空間の部分空間HC内の点である第一基準点Xを生成し、前記鍵番号Kを共通鍵として、前記第一基準点Xに基づき、前記鍵曲線H、及び前記エンコード関数fに可換な単射関数である前記デコード関数gを用いて、X=L−1[g(L(X))]により第二基準点Xを算出し、前記第一基準点X及び前記第二基準点Xを公開鍵として前記暗号化装置に公開する公開鍵生成手段を備え、
前記暗号コード生成手段は、前記鍵番号Kを共通鍵とし、前記平文コード点Yに基づき、前記鍵曲線記憶手段に記憶された又は前記鍵曲線生成手段により生成される前記鍵曲線H、単射関数である前記エンコード関数f、並びに前記復号装置により、公開鍵として公開される前記第一基準点X及び前記第二基準点Xを用いて、V=Y+L−1[f(L(X))],X=L−1[f(L(X))]により前記暗号コードとして暗号コード点V及び第三基準点Xを算出するものであり、
前記復号演算手段は、前記暗号コード生成手段から送信される前記暗号コード点V及び前記第三基準点Xに基づき、前記鍵曲線H及び前記デコード関数gを用いて、Y=V−L−1[g(L(X))]により前記平文コード点Yを算出するものであり、
前記復号装置は、前記平文コード点Yから前記平文コードを復元する平文コード復元手段を備えたことを特徴とする請求項1記載の暗号処理システム。
【請求項3】
前記N次元整数空間の部分空間HC内の点Aを、前記鍵曲線記憶手段に記憶された又は前記鍵曲線生成手段により生成される前記鍵番号Kの鍵曲線Hにより1次元序数空間内の序数iに単射する関数をL(A)、その逆関数をL−1(i)で表し、前記エンコード関数をfで表すと、
前記暗号コード生成手段は、鍵番号Kを共通鍵とし、前記平文コード点Yに基づき、前記鍵曲線H及び単射関数である前記エンコード関数fを用いてV=L−1[f(L(Y))]により前記暗号コードとして暗号コード点Vを算出するものであり、
前記復号演算手段は、前記鍵番号Kを共通鍵とし、前記暗号コード点Vに基づき、前記鍵曲線記憶手段に記憶された又は前記鍵曲線生成手段により生成される前記鍵曲線H及び前記エンコード関数fの逆関数f−1である前記デコード関数を用いて、Y=L−1[f−1(L(V))]により平文コード点Yを算出するものであり、
前記復号装置は、前記平文コード点Yから前記平文コードを復元する平文コード復元手段を備えたことを特徴とする請求項1記載の暗号処理システム。
【請求項4】
前記暗号化装置及び前記復号装置の前記鍵曲線生成手段は、
前記各鍵曲線Hを発生する種となる、分割指数1のN次元空間充填曲線であるシード曲線Cが複数格納されたシード曲線テーブルを記憶するシード曲線記憶手段と、
始点及び終点の組合せが互いに異なる、分割指数1のN次元空間充填曲線からなるターミナル曲線を格納するターミナル・テーブル、並びにN次元空間充填曲線の分割時に前記ターミナル・テーブル内の各ターミナル曲線の各アドレスに対し連結するN次元空間充填曲線を特定するインデックス情報を格納するインダクション・テーブルを記憶する曲線演算テーブル記憶手段と、
前記鍵番号Kに対するシード曲線Cを前記シード曲線テーブルから読み出し、前記ターミナル・テーブルから、該シード曲線Cと始点及び終点が一致するターミナル曲線aξを索出し、前記ターミナル・テーブルの該ターミナル曲線aξを該シード曲線Cに置換するシード曲線設定手段と、
前記シード曲線Cが設定された前記ターミナル・テーブルに基づき、前記インダクション・テーブル内の各インデックス情報を設定するインダクション・テーブル生成手段と、
N次元整数空間内の点Aのアドレスが入力されると、前記シード曲線Cを前記ターミナル・テーブル及び前記インダクション・テーブルにより(M−1)回(Mは2以上の整数)分割して生成される前記鍵曲線Hにより、前記点Aを1次元序数空間に写像した序数iAを算出する1次元写像手段と、
前記鍵曲線H上の序数iAが入力されると、前記シード曲線Cを前記ターミナル・テーブル及び前記インダクション・テーブルにより(M−1)回分割して生成される前記鍵曲線Hにより、前記序数iAをN次元整数空間に写像した点Aを算出するN次元写像手段と、を備えており、
前記暗号コード生成手段は、前記1次元写像手段により前記平文コード点Yを鍵番号Kの前記鍵曲線Hにより一次元序数空間内の序数へ単射し、また、該序数を所定のエンコード関数により単射した後、前記N次元写像手段により前記鍵曲線Hにより前記N次元整数空間内の部分空間HC内の点へ逆単射するものであり、
前記復号演算手段は、前記1次元写像手段により前記暗号コードを表す点を、前記鍵番号Kの前記鍵曲線Hにより一次元序数空間内の序数へ単射し、また、該序数を所定のデコード関数により単射した後、前記N次元写像手段により前記鍵曲線Hにより前記N次元整数空間内の部分空間HC内の点へ逆単射するものであることを特徴とする請求項1乃至3の何れか一に記載の暗号処理システム。
【請求項5】
入力される平文コードから暗号コードを生成する暗号化装置であって、
N次元整数空間内の所定の部分空間HCを充填する空間充填曲線である鍵曲線H(k=1,2,…)を複数記憶する鍵曲線記憶手段又は前記鍵曲線Hを生成する鍵曲線生成手段と、
入力される平文コードを前記N次元整数空間の部分空間HC内の点に写像して平文コード点Yを生成する平文コード点生成手段と、
鍵番号Kを共通鍵とし、前記平文コード点Yを鍵番号Kの前記鍵曲線Hにより一次元序数空間内の序数へ単射し、該序数を所定のエンコード関数により単射変換した後、前記鍵曲線Hにより前記N次元整数空間内の部分空間HC内の点へ逆単射する演算を用いて暗号化を行う暗号コード生成手段と、を備えたことを特徴とする暗号化装置。
【請求項6】
前記N次元整数空間の部分空間HC内の点Aを、前記鍵曲線記憶手段に記憶された又は前記鍵曲線生成手段により生成される前記鍵番号Kの鍵曲線Hにより1次元序数空間内の序数iに単射する関数をL(A)、その逆関数をL−1(i)で表し、前記エンコード関数をfで表すと、
前記暗号コード生成手段は、鍵番号Kを共通鍵とし、前記平文コード点Yに基づき、前記鍵曲線記憶手段に記憶された又は前記鍵曲線生成手段により生成される前記鍵曲線H、単射関数である前記エンコード関数f、並びに公開鍵として公開されている前記N次元整数空間の部分空間HC内の点である第一基準点X及び第二基準点Xを用いて、V=Y+L−1[f(L(X))],X=L−1[f(L(X))]により前記暗号コードとして暗号コード点V及び第三基準点Xを算出するものであることを特徴とする請求項5記載の暗号化装置。
【請求項7】
前記N次元整数空間の部分空間HC内の点Aを、前記鍵曲線記憶手段に記憶された又は前記鍵曲線生成手段により生成される前記鍵番号Kの鍵曲線Hにより1次元序数空間内の序数iに単射する関数をL(A)、その逆関数をL−1(i)で表し、前記エンコード関数をfで表すと、
前記暗号コード生成手段は、鍵番号Kを共通鍵とし、前記平文コード点Yに基づき、前記鍵曲線H及び単射関数である前記エンコード関数fを用いてV=L−1[f(L(Y))]により前記暗号コードとして暗号コード点Vを算出することを特徴とする請求項5記載の暗号化装置。
【請求項8】
請求項5に記載の暗号化装置により生成される暗号コードを復号し平文コードを復元する復号装置であって、
前記暗号化装置と共通の鍵曲線H(k=1,2,…)を複数個記憶する鍵曲線記憶手段又は前記鍵曲線Hを生成する鍵曲線生成手段と、
前記暗号化装置において共通鍵として使用した鍵番号と共通の鍵番号Kを共通鍵とし、前記暗号化装置により生成される、前記N次元整数空間の部分空間HC内の暗号コードを表す点を、前記鍵曲線Hにより一次元序数空間内の序数へ単射し、該序数を所定のデコード関数により単射変換した後、前記鍵曲線Hにより前記N次元整数空間内の部分空間HC内の点へ逆単射する演算を用いて前記平文コードの復元を行う復号演算手段と、を備えたことを特徴とする復号装置。
【請求項9】
請求項6に記載の暗号化装置により生成される暗号コードを復号し平文コードを復元する復号装置であって、
前記N次元整数空間の部分空間HC内の点Aを、前記鍵曲線記憶手段に記憶された又は前記鍵曲線生成手段により生成される前記鍵番号Kの鍵曲線Hにより1次元序数空間内の序数iに単射する関数をL(A)、その逆関数をL−1(i)で表し、前記暗号化装置で使用されるエンコード関数をf、前記デコード関数をg、前記暗号化装置が前記暗号コードとして生成する暗号コード点をV,第三基準点をXで表すと、
前記N次元整数空間の部分空間HC内の点である第一基準点Xを生成し、前記鍵番号Kを共通鍵として、前記第一基準点Xに基づき、前記鍵曲線H、及び前記エンコード関数fに可換な単射関数である前記デコード関数gを用いて、X=L−1[g(L(X))]により第二基準点Xを算出し、前記第一基準点X及び前記第二基準点Xを公開鍵として前記暗号化装置に公開する公開鍵生成手段を備え、
前記復号演算手段は、前記暗号コード点V及び前記第三基準点Xに基づき、前記鍵曲線H及び前記デコード関数gを用いて、Y=V−L−1[g(L(X))]により前記平文コード点Yを算出するものであり、
前記平文コード点Yから前記平文コードを復元する平文コード復元手段を備えたことを特徴とする請求項8記載の復号装置。
【請求項10】
請求項7に記載の暗号化装置により生成される暗号コードを復号し平文コードを復元する復号装置であって、
前記N次元整数空間の部分空間HC内の点Aを、前記鍵曲線記憶手段に記憶された又は前記鍵曲線生成手段により生成される前記鍵番号Kの鍵曲線Hにより1次元序数空間内の序数iに単射する関数をL(A)、その逆関数をL−1(i)で表し、前記暗号化装置で使用されるエンコード関数をf、前記暗号化装置が前記暗号コードとして生成する暗号コード点をVで表すと、
前記復号演算手段は、前記鍵番号Kを共通鍵とし、前記暗号コード点Vに基づき、前記鍵曲線記憶手段に記憶された又は前記鍵曲線生成手段により生成される前記鍵曲線H及び前記エンコード関数fの逆関数f−1である前記デコード関数を用いて、Y=L−1[f−1(L(V))]により平文コード点Yを算出するものであり、
前記復号装置は、前記平文コード点Yから前記平文コードを復元する平文コード復元手段を備えたことを特徴とする請求項8記載の復号装置。
【請求項11】
コンピュータに読み込ませて実行することにより、コンピュータを請求項5乃至7の何れか一に記載の暗号化装置として機能させることを特徴とするプログラム。
【請求項12】
コンピュータに読み込ませて実行することにより、コンピュータを請求項8乃至10の何れか一に記載の復号装置として機能させることを特徴とするプログラム。
【請求項13】
電気通信回線で接続された暗号化装置及び復号装置の間において、前記暗号化装置から平文コードを暗号化した暗号コードを送信し、前記復号装置において前記暗号コードを受信して復号し前記平文コードを復元する暗号処理方法であって、
前記暗号化装置及び前記復号装置は、N次元整数空間内の所定の部分空間HCを充填する空間充填曲線である鍵曲線H(k=1,2,…)を複数記憶する鍵曲線記憶手段又は前記鍵曲線Hを生成する鍵曲線生成手段を共通に備えており、
前記暗号化装置において、入力される平文コードを前記N次元整数空間の部分空間HC内の点に写像して平文コード点Yを生成する平文コード点生成ステップと、
前記暗号化装置において、鍵番号Kを共通鍵とし、前記平文コード点Yを鍵番号Kの前記鍵曲線Hにより一次元序数空間内の序数へ単射し、該序数を所定のエンコード関数により単射変換した後、前記鍵曲線Hにより前記N次元整数空間内の部分空間HC内の点へ逆単射する演算を用いて暗号化を行う暗号コード生成ステップと、
前記復号装置において、前記鍵番号Kを共通鍵とし、前記暗号化装置により生成される、前記N次元整数空間の部分空間HC内の暗号コードを表す点を、前記鍵番号Kの前記鍵曲線Hにより一次元序数空間内の序数へ単射し、該序数を所定のデコード関数により単射変換した後、前記鍵曲線Hにより前記N次元整数空間内の部分空間HC内の点へ逆単射する演算を用いて前記平文コードの復元を行う復号演算ステップと、
を備えたことを特徴とする暗号処理方法。
【請求項14】
前記N次元整数空間の部分空間HC内の点Aを、前記鍵曲線記憶手段に記憶された又は前記鍵曲線生成手段により生成される前記鍵番号Kの鍵曲線Hにより1次元序数空間内の序数iに単射する関数をL(A)、その逆関数をL−1(i)で表し、前記エンコード関数をf、前記デコード関数をgで表すと、
前記復号装置が、前記N次元整数空間の部分空間HC内の点である第一基準点Xを生成し、前記鍵番号Kを共通鍵として、前記第一基準点Xに基づき、前記鍵曲線H、及び前記エンコード関数fに可換な単射関数である前記デコード関数gを用いて、X=L−1[g(L(X))]により第二基準点Xを算出し、前記第一基準点X及び前記第二基準点Xを公開鍵として前記暗号化装置に公開する公開鍵生成ステップを有し、
前記暗号コード生成ステップにおいては、前記暗号化装置において、前記鍵番号Kを共通鍵とし、前記平文コード点Yに基づき、前記鍵曲線記憶手段に記憶された又は前記鍵曲線生成手段により生成される前記鍵曲線H、単射関数である前記エンコード関数f、並びに前記復号装置により、公開鍵として公開される前記第一基準点X及び前記第二基準点Xを用いて、V=Y+L−1[f(L(X))],X=L−1[f(L(X))]により前記暗号コードとして暗号コード点V及び第三基準点Xを算出し前記復号装置へ送信する処理が実行され、
前記復号演算ステップにおいては、前記復号装置において、前記暗号化装置から送信される前記暗号コード点V及び前記第三基準点Xに基づき、前記鍵曲線H及び前記デコード関数gを用いて、Y=V−L−1[g(L(X))]により前記平文コード点Yを算出し、前記平文コード点Yから前記平文コードを復元する処理が実行されることを特徴とする請求項13記載の暗号処理方法。
【請求項15】
前記N次元整数空間の部分空間HC内の点Aを、前記鍵曲線記憶手段に記憶された又は前記鍵曲線生成手段により生成される前記鍵番号Kの鍵曲線Hにより1次元序数空間内の序数iに単射する関数をL(A)、その逆関数をL−1(i)で表し、前記エンコード関数をfで表すと、
前記暗号コード生成ステップにおいては、前記暗号化装置において、鍵番号Kを共通鍵とし、前記平文コード点Yに基づき、前記鍵曲線H及び単射関数である前記エンコード関数fを用いてV=L−1[f(L(Y))]により前記暗号コードとして暗号コード点Vを算出し前記復号装置へ送信する処理が実行され、
前記復号演算ステップにおいては、前記復号装置において、前記鍵番号Kを共通鍵とし、前記暗号化装置から送信される前記暗号コード点Vに基づき、前記鍵曲線記憶手段に記憶された又は前記鍵曲線生成手段により生成される前記鍵曲線H及び前記エンコード関数fの逆関数f−1である前記デコード関数を用いて、Y=L−1[f−1(L(V))]により平文コード点Yを算出し、前記平文コード点Yから前記平文コードを復元する処理が実行されることを特徴とする請求項13記載の暗号処理方法。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図10】
image rotate

【図11】
image rotate

【図12】
image rotate

【図13】
image rotate

【図14】
image rotate

【図15】
image rotate

【図16】
image rotate

【図17】
image rotate

【図18】
image rotate

【図19】
image rotate

【図20】
image rotate

【図21】
image rotate

【図22】
image rotate

【図23】
image rotate

【図24】
image rotate

【図25】
image rotate

【図26】
image rotate

【図27】
image rotate

【図28】
image rotate

【図29】
image rotate

【図30】
image rotate

【図31】
image rotate

【図32】
image rotate

【図33】
image rotate

【図34】
image rotate

【図35】
image rotate

【図36】
image rotate

【図37】
image rotate

【図38】
image rotate

【図39】
image rotate

【図40】
image rotate

【図41】
image rotate

【図42】
image rotate

【図43】
image rotate


【公開番号】特開2012−177893(P2012−177893A)
【公開日】平成24年9月13日(2012.9.13)
【国際特許分類】
【出願番号】特願2011−268023(P2011−268023)
【出願日】平成23年12月7日(2011.12.7)
【出願人】(899000068)学校法人早稲田大学 (602)
【Fターム(参考)】