(57)【特許請求の範囲】
【請求項１】
共通鍵暗号の復号装置であって，
冗長データとメッセージとからなる平文を暗号化した暗号文を入力とし，特定の長さで区切った複数の暗号文ブロックを生成する回路と，
秘密鍵を入力とし，少なくとも二つの前記暗号文ブロックの各々に対して，第一と第二の乱数ブロックを生成する乱数ブロック生成回路と，
前記複数の暗号文ブロックに対応する複数の平文ブロックを生成する復号演算回路とからなり，
前記復号演算回路は，
一つの前記暗号文ブロックを用いた第一の演算を行う第一の回路と，
前記第一の回路による前記第一の演算の結果と，前記乱数ブロック生成回路が生成する第一の前記乱数ブロックと，を用いた第二の演算を行う第二の回路と，
前記第二の回路による前記第二の演算の結果と，前記乱数ブロック生成回路が生成する第二の前記乱数ブロックと，を用いた第三の演算を行い，前記第三の演算の結果を，一つの前記暗号文ブロックに対応する一つの前記平文ブロックとして出力する第三の回路と，を備え，
前記第一の回路は，前記第二の回路が他の前記暗号文ブロックに基づいて行う前記第二の演算の結果と，一つの前記暗号文ブロックと，を用いて前記第一の演算を行い，
前記乱数ブロック生成回路が生成する第一と第二の前記乱数ブロックは，前記暗号文ブロックのいずれにも依存せず，前記第一の回路による前記第一の演算の結果にも依存しない
ことを特徴とする共通鍵暗号の復号装置。
【請求項２】
請求項１記載の共通鍵暗号の復号装置であって，
前記乱数ブロック生成回路は，前記暗号文より長い乱数列を区切って，前記暗号文ブロックのいずれにも依存しない前記乱数ブロックを生成する
ことを特徴とする共通鍵暗号の復号装置。
【請求項３】
請求項１または２記載の共通鍵暗号の復号装置であって，
前記平文ブロックを複数連結して平文を生成する回路と，
前記平文に含まれる前記冗長データを抽出する回路と，
前記冗長データを検査して前記暗号文への改ざんの有無を検出する回路とを備える
ことを特徴とする共通鍵暗号の復号装置。
【請求項４】
請求項３記載の共通鍵暗号の復号装置であって，
さらに，前記平文に含まれる，前記冗長データと，前記メッセージとは異なる，前記秘密鍵に基づき生成した秘密データを抽出する回路を備え，
前記暗号文への改ざんの有無を検出する回路は，前記秘密データと前記冗長データとを検査して，前記暗号文への改ざんの有無を検出する
ことを特徴とする共通鍵暗号の復号装置。
【請求項５】
請求項２記載の共通鍵復号装置であって，
前記乱数ブロック生成回路は，前記秘密鍵から前記乱数列を生成する擬似乱数生成器と，
前記乱数列から前記乱数ブロックを生成する回路と，を備える
ことを特徴とする共通鍵復号装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は,秘密情報のセキュリティを確保する技術に関する。
【０００２】
【従来の技術】
従来の暗号処理装置は,データを秘匿する目的のブロック暗号やストリーム暗号が提案されていた。ブロック暗号にはDES,IDEAなど非常にいろいろな方式が提案されている。DES,IDEAについては以下の文献で扱っている。
文献1:Menezes, van Oorschot, Vanstone, Handbook of Applied Cryptography, CRC Press, 1996, pp.250-259, pp.263-266。
【０００３】
ブロック暗号はECB,CBC,CFB,OFB,カウンタモードなどのブロック暗号操作モードにより全体の暗号処理の安全性や性質を議論するが,これまでに暗号化処理と改ざん検出を同時に行う操作モードは,iaPCBCモードが知られているだけで,残りのモードは改ざんの検出がそれ自身では不可能である。ブロック暗号の操作モードについては以下の文献で扱っている。
文献2:Schneier, Applied Cryptography, Second Edition, John Wiley Sons, Inc。, 1996, pp.189-209。
iaPCBCモードは以下の文献で扱っている。
文献3:Gligor, Donescu, ”Integrity-Aware PCBC Encryption Schemes,” Preproceedings in  Secure Protocol Workshop, Cambridge, 1999, to appear in Lecture Notes in Computer Science series, Springer-Verlag。
【０００４】
iaPCBCモードはブロック暗号を用いた操作モードであり,暗号化処理では並列処理が不可能,事前計算などが不可能,などの点で非常に高速な処理が要求される環境への実装が非常に困難であった。
これに対して,メッセージ認証子と呼ばれる改ざん検出のための暗号学的チェックサム(以下，MACという)を生成する方式が提案され,ブロック暗号の上記操作モードの暗号処理でも必要に応じてMAC生成処理を同時にかつまったく独立の機構として実装することで,暗号処理と改ざん検出が同時に可能となった。しかし,この場合にはまったく独立な暗号学的鍵を2度,すなわち,暗号化用と改ざん検出用,共有する必要があるという点,それから暗号化されるデータを2度処理,つまり,暗号化処理とMAC生成処理,にかける必要があり,システムが複雑になったり,長いデータの処理に向かないなどの懸念があった。さらにブロック暗号の処理速度が現在の通信の速度に比べて低速であり,これらブロック暗号とMACの組み合わせ技術は,ギガビットやテラビット処理への応用が困難であった。MACについての記述は以下の文献にある。
文献4:Menezes, van Oorschot, Vanstone, Handbook of Applied Cryptography, CRC Press, 1996, pp.352-368。
【０００５】
これに対してストリーム暗号は,さまざま提案された暗号学的擬似乱数生成器を用いて暗号化を行うメカニズムで,擬似乱数生成器の安全性や性質とは無関係に改ざんの検出はそれ自身では不可能だった。ストリーム暗号,またはストリーム暗号に用いる擬似乱数生成器としてよく知られているものに,SEAL,非線形コンバイナを用いた線形フィードバックシフトレジスタ,非線形フィルタを用いた線形フィードバックシフトレジスタ,クロック制御方式の線形フィードバックシフトレジスタなどがある。SEALについては以下の文献で扱っている。
文献5:Schneier, Applied Cryptography, Second Edition, John Wiley Sons, Inc。, 1996, pp.398-400。
【０００６】
その他のフィードバックシフトレジスタに基づく方式については以下の文献で扱っている。
文献6:Menezes, van Oorschot, Vanstone, Handbook of Applied Cryptography, CRC Press, 1996, pp.203-212。
【０００７】
ストリーム暗号とMACを組み合わせた技術により暗号処理と改ざん検出を同時に行えるほか,上記ブロック暗号の処理にくらべて,2倍〜20倍の比率でストリーム暗号がより高速であるが,どのMAC生成方式についても,ブロック暗号とMACの組み合わせ同様,ふたつの異なる鍵の共有が必要であったり,ひとつのメッセージについて2度の処理を行う必要などがあった。より詳しくMAC生成方式を考えると,本来のストリーム暗号に,付帯的に必要となるメカニズムや計算量が非常に大きい。例えば,HMAC,UMACなどのMAC生成方式では暗号学的に衝突なしで一方向性を保証している安全なハッシュ関数を必要であり,ストリーム暗号にさらに前述のハッシュ関数を実装する必要がある。HMACは前述の文献4,pp.355のExample 9.67で扱っている。またUMACは以下の文献で扱っている。
文献7:Black, Halevi, Krawczyk, Krovetz, Rogaway, ”UMAC: Fast and Secure Message Authentication,” Advances in Cryptology, - CRYPTO'99, Lecture Notes in Computer Science, Vol. 1666, Springer-Verlag, 1999。
【０００８】
しかし,一般にSHA-1, MD5などのハッシュ関数は非常に複雑であり,実装も容易でない。これらのハッシュ関数については以下の文献で扱っている。
文献8:Menezes, van Oorschot, Vanstone, Handbook of Applied Cryptography, CRC Press, 1996, pp.347-349。
【０００９】
ハッシュ関数の安全性の面についても,ブロック暗号のそれに比べて議論が行われておらず,ユーザによってはハッシュ関数を信頼できず,組み込めないこともある。またMAC生成方式の中で擬似乱数生成器のみを用いる方式であるMMHのMAC生成では非常に少ない追加の資源,回路やプログラム,で暗号処理に改ざん検出の機能を付け加えることができるが,メッセージの長さに対してその2倍の長さの擬似乱数を必要とし,必要な乱数生成に時間がかかってしまう。MMHは以下の文献で扱っている。
文献9:Halevi, Krawczyk, ”MMH: Software Message Authentication in the Gbit/Second Rates,” Fast Software Encryption, 4th International Workshop, FSE'97, Lecture Notes in Computer Science, Vol。 1267, Springer-Verlag, 1997。
【００１０】
【発明が解決しようとする課題】
従来の暗号技術のほとんどは,復号化の際,改ざん検出をそれ自身ではすることができなかった。改ざん検出を行うとき,異なるふたつの鍵共有の必要性や,独立の処理,別の暗号学的要素関数の追加実装などが必要であった。
本発明は改ざん検出も復号化と同時に可能であり,またデータ秘匿,データ改ざんに対する安全性については,証明可能なものを提供することを目的とする。
処理速度の面についての課題として,ブロック暗号のこれまで知られた操作モードでは並列度や事前計算等の可能性がなく,高並列処理や高速処理には向いていないという点があった。
本発明は擬似乱数生成器の高速処理性能を生かしながら,事前計算や並列処理の利点をもつ,高速処理可能な共通鍵暗号の方法を提供することを目的とする。
本発明は従来のブロック暗号よりも高速な処理が可能というだけではなく,資源が許される場合にはそれだけより高速な処理が可能であり,高い並列度を達成できるような高速処理に向けたものを提供することを目的とする。
本発明は非常に短いメッセージについても処理速度が落ちないような方式を提供することを目的とする。
本発明はストリーム暗号に非常に小さな追加の回路,またはプログラムで実装可能な方式を提供することを目的とする。
【００１１】
【課題を解決するための手段】
本発明では，擬似乱数列を鍵ストリームとして用いてブロック毎に処理を行い，かつ，改ざん検出を可能にする共通鍵暗号方法を提供する。
本発明の第一の態様は,平文P,鍵ストリームS,冗長性データ(以下，冗長性と略す)R,初期値Vから暗号文Cを得る暗号処理方法であって，鍵ストリームSの長さが暗号文Cより真に長い。
具体的には，冗長性の長さをbビット,平文の長さを
L=n×b+t (tは0以上b未満の整数、nは0以上の整数) ビットとしたとき,平文の最後にビット文字列`0'を ((b-t) mod b) 個付加し,
冗長性Rを付加し,全体で
L+((b-t) mod b)+bビットの文字列とする。これはbの倍数である。
これをbビットのブロックに分割し,Pi(1≦i≦m)とする。表記Xi (1≦i≦n)は、変数Xiについて、要素数がnで引数が1からnまで、の列を表すものとする。このとき必要な鍵ストリームの長さは2mbビットである。
この鍵ストリームは，暗号化装置側と復号化装置側とで，秘密裏に事前に共有しておくか，または，事前に共有した秘密鍵(例えば擬似乱数生成器の入力に相当する)から生成する。
上記長さの鍵ストリームを,2つのブロック列,Ai,Bi(1≦i≦m,それぞれbビット)に分割する。
フィードバック値の初期値F0=Vとして,以下により暗号文ブロックCiを得る。(この初期値Vも事前に共有しておく。ただし，秘密にしておく必要はない)
Fi=Pi^Ai,  Ci=(Fi*Bi)^Fi-1(1≦i≦m).
得られたCiをならべ,一つの文字列としたものを暗号文Cとして出力する。ここで,演算子「*」,「^」は,それぞれ有限体F(2b)上での乗算,加算を示す。
【００１２】
対応する復号化は以下のとおりである。
暗号文C'の長さがbビットの倍数でない場合,非受理を出力する。もしbビットの倍数であったなら,bビットのブロックに分割し,C'i(1≦i≦m')とする。
鍵ストリームブロックAi,Bi(1≦i≦m'),フィードバック値F'0=Vをセットして,以下の処理を行う。
F'i=(C'i^F'i-1)/Bi,  P'i=Ai^F'i (1≦i≦m').
得られたP'iをならべ,一つの文字列としたものを復号化結果P'として保存する。演算子「/」は有限体F(2b)上での除算を示す。
bビット文字列P'mは,改ざんが起こらない場合,冗長性Rが復元されるべきである。また鍵を知らない攻撃者が改ざんを試みて,P'mが改ざん後にも変化しないような攻撃は1/2b以上で成功しないことが保証されている。よってこれを根拠に,bが十分に大きい(32以上)場合には,P'mが冗長性Rと同じかどうかを検査することにより改ざんの検出が可能となる。
【００１３】
本態様によれば，暗号文のいずれのブロックに改ざんが施されても，その影響が復号化時に最終ブロックまで伝播するという特徴がある。したがって，冗長データが変化しないような改ざんを，攻撃者が試みても防ぐことが可能になるという効果がある。
より具体的には，暗号化処理において，次のブロックのためのフィードバック値を生成，保存したのち，前のブロックの演算にて生成されたフィードバック値を用いて演算するものである。すなわち，暗号化処理において，t番目ブロックで生成される中間値を，生成される順にX1,X2,…,Xnとすると，次のt+1番目ブロックのためのフィードバック値FtとなるXiと，前のブロックからのフィードバック値Ft-1が作用する中間値Xjとの引数i,jについてi≦jが成り立つ(必要条件)。
本態様によれば，改ざんが改ざん検査をパスする確率が1/2bであるが,復号化において有限体での除算が生じ,また，平文の2倍の乱数を消費する。
【００１４】
第二の態様では安全性を少しゆるめて,さらに効率的な処理が可能な方法を示す。
第二の態様でも同様にメッセージ,冗長性の操作を同じように行う。冗長性付き平文がmブロックのとき,必要な鍵ストリームの長さはb×(m+1)ビットであり,これをAi (1≦i≦m) ,Bに分割する。
フィードバック値の初期値F0=Vとして,以下により暗号文ブロックCiを得る。
Fi=Pi^Ai,  Ci=(Fi*B)^Fi-1(1≦i≦m).
得られたCiをならべ,一つの文字列としたものを暗号文Cとして出力する。
【００１５】
対応する復号化は以下のとおりである。暗号文C'の長さがbビットの倍数でない場合,非受理を出力する。もしbビットの倍数であったなら,bビットのブロックに分割し,C'i(1≦i≦m')とする。暗号化と同様に鍵ストリームブロックAi (1≦i≦m') ,B,フィードバック値F'0=Vをセットして,以下の処理を行う。
F'i=(C'i^F'i-1)/B,  P'i=Ai^F'i (1≦i≦m').
得られたP'iから冗長性の部分を取り出し,決められた冗長性が得られたかどうかを検査する。もしそうであるなら,残りのP' iの部分をメッセージとして出力し,そうでないなら,非受理を出力する。
ここでbビット文字列P'mは,改ざんが起こらない場合,冗長性が復元されるべきである。
本態様によれば，i番目ブロックで使う複数の擬似乱数列(鍵ストリーム)のうちいずれかをブロック毎に変化させ，いずれかは共通に用いる。より具体的には，i番目のブロックで，暗号処理に与える疑似乱数列を, Ai, Biとすると,Aiは毎ブロックごとに変化し，Biはすべてのブロックを通して変化しない。
この第二の態様では,鍵を知らない攻撃者が改ざん後に改ざん検出で検出されない確率は(m-1)/2bとなる。一般的な改ざん検出確率は1/232以下であることが望ましく,mは232程度が実際の実装でのデータ長の上限であるので,b=64以上が望ましい。この場合,暗号化,復号化では有限体F(264)上の乗算を行うことにになる。この演算はハードウェア実装ならば非常に高速かつ低コストで実現可能であるが,ソフトウェア実装の場合,次のような態様による高速化も考えられる。
【００１６】
第三の態様では,より長い冗長性についての方法を示す。まず,以降の処理をbビット単位で行うのを前提として,冗長性をb×dビットとする。第一,第二の態様と同様にメッセージ,冗長性の操作を同じように行い,bビットのメッセージと冗長性によるブロック列,Pi (1≦i≦m,m≦d)が生成される。そして鍵ストリームの長さをb×(m+d)ビットとし,これをbビットのブロック列Ai (1≦i≦m) ,Bi (≠0,1≦i≦d)に分割する。
フィードバック値の初期値F(i)0=Vi(1≦i≦d)として,以下により暗号文ブロックCiを得る。
F(1)i=Pi^Ai,
F(j+1)i=(F(j)i*Bj)^F(j)i-1(1≦j≦d),
Ci=F(d+1)i(1≦i≦m).
得られたCiをならべ,一つの文字列としたものを暗号文Cとして出力する。
【００１７】
これに対応する復号化は以下のとおりである。暗号文C'の長さがbビットの倍数でない場合,非受理を出力する。もしbビットの倍数であったなら,bビットのブロックに分割し,C'i(1≦i≦m')とする。暗号化と同様に鍵ストリームブロックAi (1≦i≦m') ,Bi (≠0,1≦i≦d),フィードバック値F(i)0=Vi(1≦i≦d)をセットして,以下の処理を行う。
F'(d+1)i=C'i,
F'(j)i=(F'(j+1)i^F'(j)i-1)/Bj(1≦j≦d),
P'i=Ai^F'(1)i (1≦i≦m).
得られたP' iから冗長性の部分を取り出し,決められた冗長性が得られたかどうかを検査する。もしそうであるなら,残りのP' iの部分をメッセージとして出力し,そうでないなら,非受理を出力する。
【００１８】
第三の態様では,冗長性の長さがb×dビットでありながら,暗号化や復号化に必要な処理は有限体F(2b)上の演算であり,これは有限体F(2b×d)上の乗算に比べて一般に1/d2倍となる。しかし,乗算の回数がd倍になることから,この高速化方式は同じ冗長性の長さについて,乗算の演算速度が約1/dの時間で処理可能となる。
【００１９】
第四の態様では,これまで挙げた第一から第三の態様の暗号処理で用いられる有限体F(2b)上の乗算をFeistelの3段構造に組み込んだものである。つまりこれまでのA*Bの演算を,
M1=AL^(AR*BL),  M2=AR^(M1*BR),  M3=M1^(M2*BL),
によりM3||M2を出力する関数に置き換える(BLとBR,ALとAR,M2とM3は,それぞれ入れ替わっても可)。これらの演算は自己逆演算となっており,復号化の際,同じ演算を用いることができる。
【００２０】
第五の態様では,メッセージの分割処理である。平文Pを送信者受信者間の決まりに従ってt個の文字列に分割し,それぞれをPi(1≦i≦t)とする。これまで述べた態様のひとつによりそれぞれ相異なる冗長性Ri(1≦i≦t)を用いて暗号化を行い暗号文Ciを得る。またこれとは別にRiの列のすべて,すなわち,
(R1||R2||R3||…||Rt)を平文としてさらに送信者受信者間で共有された冗長性Rを用いて暗号化し,暗号文Ct+1を得る。これら,暗号文ブロックの列の連結  (C1||C2||C3||…||Ct+1)を最終的な暗号文Cとする。
【００２１】
対応する復号化は,暗号文を決められた方式に従ってt個の文字列に分割し,それぞれを独立に復号化する。どの復号化結果も非受理でなく,冗長性Riすべてが,冗長性を平文に見立てた部分の復号化結果に含まれていれば受理として,冗長性の含まれる順番で復号化結果である平文を連結する。どれかの復号化で非受理ならば,非受理とする。
【００２２】
第六の態様では，上記五つの態様について，有限体F(2b)上の乗算のかわりに，有限体F(p)上の乗算に基づいたものを考える(pはある整数kによって2k+1と表すことができる素数である)。
具体的にはF(2b)上の乗算 a*b の代わりとして，F(p)上の演算 a*(b+1)+1 を行う。この演算は2bビットレジスタ上で，乗算１回，加算２回，シフト1回で処理可能なため，汎用的なプロセッサ上で乗算を高速に行うことができる。
上記演算は，F(2b)の乗算が，排他的論理和b回，シフトb回の計算を要し，一般の素数pにおけるF(p)の乗算が，乗算1回と除算1回(除算は，通常，加算やシフトの数十倍の時間がかかる)を要するのと比較して高速な処理が可能である。
【００２３】
本発明では擬似乱数を用いていることから,ユーザが最も信頼する暗号学的要素アルゴリズムは擬似乱数生成器として，ブロック暗号,ハッシュ関数，ストリーム暗号のどれかを用いることができ,安全性をユーザの選んだ暗号要素アルゴリズムに容易に帰着できる。さらに、擬似乱数生成処理は，平文処理や暗号文処理とは独立に行うことが可能であるため、並列処理や事前計算が可能になり、高速処理が可能になる。
実装コストについては,ハッシュ関数の追加実装といった困難な追加実装を避けることができる。
【００２４】
【発明の実施の形態】
(実施例1)
図1はネットワーク10001によって接続されたコンピュータA10002,コンピュータB10003を含む,コンピュータA10002からコンピュータB10003への暗号通信を目的としたシステム構成を示すものである。コンピュータA10002は内部に演算装置(以下CPUという)10004,記憶装置(揮発性，不揮発性を問わない。以下RAMという)10005,ネットワークインターフェース10006を装備しており,外部にはコンピュータA10002をユーザが操作するためのディスプレイ10007とキーボード10008が接続されている。RAM10005には暗号化処理プログラム(以下プログラムをPROGともいう)PROG1_10009,乱数生成処理プログラムPROG2_10010,コンピュータA10002とコンピュータB10003間のみで共有されている秘密情報である秘密鍵K10011,コンピュータA10002とコンピュータB10003間で共有されているデータである冗長性R10012と初期値V10013,それに暗号化してコンピュータB10003に送信したいデータ10014が保存されている。コンピュータB10003は内部にCPU10015,RAM10016,ネットワークインターフェース10017を装備しており,外部にはコンピュータB10003をユーザが操作するためのディスプレイ10018とキーボード10019が接続されている。RAM10016には復号化処理プログラムPROG3_10020,乱数生成処理プログラムPROG2_10021,秘密鍵K10011,冗長性R10012,それに初期値V10013が保存されている。
【００２５】
コンピュータA10002は,暗号化処理プログラムPROG1_10009を実行し,メッセージM1001４の暗号文C10022を作成し,ネットワークインターフェース10006を通してネットワーク10001へ送信する。コンピュータB10003は,ネットワークインターフェース10017を通して受信したあと,復号化処理プログラムPROG3_10020を実行し,もし改ざんが検出されなければ復号化結果をRAM10016に保存する。
【００２６】
各プログラムは，互いのコンピュータまたは他のコンピュータからネットワーク10001上の伝送媒体である伝送信号により，またはCD,FDなど可搬型記憶媒体を介してRAMに導入することができる。各プログラムは，各コンピュータのオペレーティングシステム(図示していない)の元で動作するように構成することも可能である。
暗号化処理プログラムPROG1_10009は,コンピュータA10002において,RAM10005から読み出されて,CPU10004により実行される。暗号化処理プログラムPROG1_10009は,サブルーチンとして乱数生成処理PROG2_10010を内部で呼び出し,入力秘密鍵K10011,冗長性R10012,初期値V10013,メッセージM10014に対して,暗号文C10022を出力する。
復号化処理プログラムPROG3_10020は,コンピュータB10003において，RAM10016から読み出されてCPU10015により実行される。復号化処理プログラムPROG3_10020は,サブルーチンとして乱数生成処理PROG2_10021を内部で呼び出し,入力秘密鍵K10011,冗長性R10012,初期値V10013,暗号文C10022に対して,メッセージ,または改ざん検知警告を出力する。
【００２７】
暗号化処理プログラムPROG1_10009の処理の流れを説明する。
ステップ20002:データセットサブルーチン。初期値V,冗長性R,秘密鍵Kの入力を待つ。
ステップ20003:平文準備サブルーチン。平文の入力を待ち,平文が与えられたあと決められたパディングを行い,冗長性を付加して,最後に64ビットごとに区切って平文ブロックの列Pi(1≦i≦n)を出力する。
ステップ20004:乱数生成サブルーチン。秘密鍵Kから,擬似乱数列Ai,Bi(1≦i≦n)を出力する。
ステップ20005:暗号化サブルーチン。擬似乱数列Ai,Bi,平文ブロック列Pi(1≦i≦n),初期値Vを使って,暗号文ブロック列Ci(1≦i≦n)を出力する。
ステップ20006:ステップ20005で得られた暗号文ブロック列Ci(1≦i≦n)を順にビット連結し,暗号文Cとして出力する。
【００２８】
上述のように，主となるデータに付属的なデータを付加することを本明細書ではパディングと呼ぶ。デジタルデータの場合のパディングでは，主となるデータに付属的なデータを単にビット連結することが多い。
【００２９】
平文準備サブルーチンの処理を図2を用いて説明する。
【００３０】
ステップ20202:暗号処理に用いるメッセージMの入力を待つ。メッセージMは，キーボード10008から入力されたり，RAM内に保存されていたり，他の媒体から導入されたりする。
ステップ20203:メッセージの長さを示すデータをパディング。メッセージMの先頭にメッセージMのビット長を表す64ビット二進数データを付加する。
ステップ20204:メッセージ長をそろえるパディング。後の暗号処理のためパディング後のデータを64ビットの整数倍にする。メッセージMの長さをLビットとすると64―L(mod 64)個の0をステップ20203で長さデータを付加されたメッセージの末尾にパディングする。
ステップ20205:冗長性データのパディング。64ビットデータとして与えられる冗長性Rをさらに末尾にパディングする。
ステップ20206:メッセージデータの平文ブロックへ分割。ステップ20205の結果得られたデータを64ビットのブロックに区切り順にP1,P2,…,Pnとする。
【００３１】
乱数生成サブルーチンの処理を図3を用いて説明する。
ステップ20302:必要パラメータの入力。パディング後のメッセージブロック数nと,秘密鍵Kを得る。
ステップ20303:擬似乱数列Aの生成。乱数生成処理プログラムPROG2を呼び出し,長さ64nビットの擬似乱数列を生成,出力をAとする。
ステップ20304:乱数列Aをブロックに分割。擬似乱数列Aを64ビットごとに区切り順にA1,A2,…,Anとする。
ステップ20305:カウンタiの初期化。カウンタi=1とする。
ステップ20306:乱数Biの生成。秘密鍵Kを使ってPROG2を実行することにより64ビットの乱数Biを生成する。
ステップ20307:ステップ20306で生成されたBiが0ならば,ステップ20306に戻る。
ステップ20308:i=nならばステップ20310を実行。
ステップ20309:カウンタiをインクリメントしステップ20306へ戻る。
【００３２】
暗号化サブルーチンの処理を図4を用いて説明する。
ステップ20402:初期値セット。F0=Vとする。
ステップ20403:カウンタ初期化。i=1とする。
ステップ20404:フィードバック値Fi計算。
Fi=Pi^Aiとする。
ステップ20405:暗号文ブロックCi計算。
Ci=(Fi*Bi)^Fi-1とする。
ステップ20406:i=nならばステップ20408を実行。
ステップ20407:カウンタiをインクリメントしステップ20404へ戻る。
【００３３】
復号化処理プログラムPROG3_10020の処理の流れを図5を用いて説明する。
ステップ20502:データセットサブルーチン。初期値V,冗長性R,秘密鍵Kの入力を待つ。
ステップ20503:暗号文準備サブルーチン。暗号文C'の入力を待ち,暗号文C'が与えられたあと64ビットごとに区切って暗号文ブロックの列C'i(1≦i≦n)を出力する。
ステップ20504:乱数生成サブルーチン。秘密鍵Kから,擬似乱数列Ai,Bi(1≦i≦n)を出力する。
ステップ20505:復号化サブルーチン。擬似乱数列Ai,Bi,暗号文ブロック列C'i(1≦i≦n),初期値Vを使って,平文ブロック列P'i(1≦i≦n)を出力する。
ステップ20506:平文切り出しサブルーチン。平文ブロックの列P'iを3つのデータ列,L',M',Z'に分割する。
ステップ20507:冗長性切り出しサブルーチン。Z'をR'とT'に分割する。
ステップ20508:T=0かつR'=Rならばステップ20510に進む。
ステップ20509:拒否(非受理)を出力。ステップ20511に進む。
ステップ20510:M'をRAMへ格納する。
ステップ20509,20510では，復号化処理プログラムは，結果(受理/非受理あるいは復号結果)をディスプレイ10018に出力して，ユーザに結果を通知する。
【００３４】
暗号文準備サブルーチンの処理を図6を用いて説明する。
ステップ20602:暗号文C'の入力を待つ。
ステップ20603:暗号文C'を64ビットごとに区切り,順にC'1,C'2,…,C'nとする。
【００３５】
復号化サブルーチンの処理を図7を用いて説明する。
【００３６】
ステップ20702:初期値セット。F'0=Vとする。
ステップ20703:カウンタ初期化。i=1とする。
ステップ20704:フィードバック値F'i計算。
F'i=(C'i^F'i-1)/Biとする。
ステップ20705:平文ブロックP'i計算。P'i=F'i^Aiとする。
ステップ20706:i=nならばステップ20708を実行。
ステップ20707:カウンタiをインクリメントしステップ20704へ戻る。
【００３７】
平文切り出しサブルーチンの処理を図8を用いて説明する。
ステップ20802:L'を最初の64ビットの平文ブロックとする。
ステップ20803:復号文ブロックのうちP'2最上位ビットからL'ビットのデータをM'とする。
ステップ20804:M'を切り取った残りのデータをZ'とする。
【００３８】
冗長性切出しサブルーチンの処理を図9を用いて説明する。
ステップ20902:R'をZ'の下位64ビットのデータとする。
ステップ20903:R'を切り取った後の残りのデータをT'とする。
【００３９】
図10は，暗号化処理の説明図である。○印の中に+が入った記号は64ビット幅の二つのデータによる排他的論理和演算を表し,○印の中に×が入った記号は64ビット幅の二つのデータによる有限体F(264)上での乗算を示す。
メッセージM20931に長さ20930,適当なパディング20932,冗長性R20933をそれぞれ付加し,平文P20934を生成する。
これを64ビットに分割したものをそれぞれP1_20935,P2_20936,P3_20937,Pn_20938とする。
P1_20935はA1_20940と排他論理和を取り,フィードバック値F1_20941とし，B1_20942と有限体上の乗算を行い,その結果と初期値F0_20939の排他論理和により暗号文ブロックC1_20943を得る。
P2_20936はA2_20946と排他論理和を取り,フィードバック値F2_20945とし，B2_20946と有限体上の乗算を行い,その結果とフィードバック値F1_20941の排他論理和により暗号文ブロックC2_20947を得る。
同様にしてPn_20938まで処理を行い,暗号文ブロックC1_20943,C2_20947,C3_20951,…,Cn_20955を得たあと,これらをこの順で連結し,暗号文C_20956を得る。
【００４０】
図11は,復号化処理の説明図である。○印の中に/が入った記号は64ビット幅の二つのデータによる有限体F(264)上での除算を示す。該記号の上から入るデータが割られる数,該記号の左から入るデータが割る数である。
暗号文C'_20960を64ビットのブロックに分割し,C'1_20962,C'2_20963,C'3_20964, …,C'n_20965とする。
C'1は初期値F'0_20961と排他的論理和をとり,その結果をB1_20966で割る。この結果をフィードバック値F'1_20967とする。平文ブロックP'1_20969はフィードバック値F'1_20967とA1_20968との排他論理和により得られる。
C'2_20963,C'3_20964, …,C'n_20965も同様に処理を行い,得られた平文ブロックP'1_20969,P'2_20972,P'3_20977, …,P'n_20981を連結し平文P'_20982とする。これをL'_20983,M'_20984,Z'_209985に分割後,さらにZ'_209985をT'_20988とR'_20989に分割し,冗長性のチェックを行う。
【００４１】
実施例1では,メッセージの長さの約2倍の長さだけの擬似乱数を暗号処理に使った。擬似乱数はブロック暗号に比較して高速ではあるものの,この暗号処理で最も計算量のかかる処理であり,消費する乱数の数を減らすことが望ましい。
(実施例2)
以下に示す実施例2では，別の関数を使うことにより,より少ない擬似乱数の消費で行え,また復号化の際の割る数も変化せず,逆数の事前計算によりほぼ乗算と同じ速度で達成できるため,極めて効率的な処理が可能となる。
実施例2では，暗号化処理PROG1,復号化処理PROG3の代わりに暗号化処理PROG1A,復号化処理PROG3Aをそれぞれ使う。
暗号化処理PROG1Aを示す。PROG1Aは,図1のPROG1_10009において,乱数生成サブルーチン20004と暗号化サブルーチン20005をそれぞれ乱数生成2サブルーチン21004と暗号化2サブルーチン21005に置き換えたものである。
【００４２】
乱数生成2サブルーチン2100４の処理を図12を用いて説明する。
【００４３】
ステップ21102:必要パラメータの入力。パディング後のメッセージブロック数nと,秘密鍵Kを得る。
ステップ21103:擬似乱数列Aの生成。乱数生成処理プログラムPROG2を呼び出し,長さ64nビットの擬似乱数列を生成,出力をAとする。
ステップ21104:乱数列Aをブロックに分割。擬似乱数列Aを64ビットごとに区切り順にA1,A2, …,Anとする。
ステップ21105:乱数Bの生成。秘密鍵Kを使ってPROG2を実行することにより64ビットの乱数Bを生成する。
ステップ21106:ステップ21105で生成されたBが0ならば,ステップ21105に戻る。
【００４４】
暗号化2サブルーチン21005の処理を図13を用いて説明する。
ステップ21202:初期値セット。F0=Vとする。
ステップ21203:カウンタ初期化。i=1とする。
ステップ21204:フィードバック値Fi計算。
Fi=Pi^Aiとする。
ステップ21205:暗号文ブロックCi計算。
Ci=(Fi*B)^Fi-1とする。
ステップ21206:もし,i=nならばステップ21208を実行。
ステップ21207:カウンタiをインクリメントしステップ21204へ戻る。
【００４５】
PROG1Aと対となる,復号化処理PROG3Aの処理の流れを図14を用いて説明する。PROG3Aは,PROG3_10020において,乱数生成サブルーチン20504と復号化サブルーチン20505をそれぞれ乱数生成2サブルーチン21304と復号化2サブルーチン21305に置き換えたものである。
【００４６】
ステップ21302:データセットサブルーチン。初期値V,冗長性R,秘密鍵Kの入力を待つ。
ステップ21303:暗号文準備サブルーチン。暗号文C'の入力を待ち,暗号文C'が与えられたあと64ビットごとに区切って暗号文ブロックの列C'i(1≦i≦n)を出力する。
ステップ21304:乱数生成サブルーチン。秘密鍵Kから,擬似乱数列Ai(1≦i≦n), Bを出力する。
ステップ21305: 復号化サブルーチン。擬似乱数列Ai,B,暗号文ブロック列C'i(1≦i≦n),初期値Vを使って,平文ブロック列P'i(1≦i≦n)を出力する。
ステップ21306:平文切り出しサブルーチン。平文ブロックの列P'iを3つのデータ列,L',M',Z'に分割する。
ステップ21307:冗長性切り出しサブルーチン。Z'をR'とT'に分割する。
ステップ21308:T=0かつR'=Rならばステップ21310に進む。
ステップ21309:拒否を出力。ステップ21311に進む。
ステップ21310:M'をRAMへ格納する。
【００４７】
図1４の復号化2サブルーチン21305の処理を図15を用いて説明する。
ステップ21402:初期値セット。F'0=Vとする。
ステップ21403:1/Bを事前計算しておく。
ステップ21404:カウンタ初期化。i=1とする。
ステップ21405:フィードバック値F'i計算。F'i=(C'i^F'i-1)*(1/B)とする。
ステップ21406:平文ブロックP'i計算。P'i=F'i^Aiとする。
ステップ21407:i=nならばステップ21409を実行。
ステップ21408:カウンタiをインクリメントしステップ21405へ戻る。
【００４８】
図16は，上述の高速化手法で用いた暗号化処理の説明図である。
メッセージM21421に長さ21420,適当なパディング21422,冗長性R21423をそれぞれ付加し,平文P21424を生成する。
これを64ビットに分割したものをそれぞれP1_21425,P2_21426,P3_21427,Pn_21428とする。
P1_21425はA1_21431と排他論理和を取り,フィードバック値F1_21432とし，B_21429と有限体上の乗算を行い,その結果と初期値F0_21430の排他論理和により暗号文ブロックC1_21433を得る。
P2_21426はA2_21434と排他論理和を取り,フィードバック値F2_21435とし，B_21429と有限体上の乗算を行い,その結果とフィードバック値F1_21432の排他論理和により暗号文ブロックC2_21436を得る。
同様にしてPn_21428まで処理を行い,暗号文ブロックC1_21433,C2_21436,C3_21439, …,Cn_21442を得たあと,これらをこの順で連結し
,暗号文C_21443を得る。
【００４９】
図17は,対応する復号化処理の説明図である。
暗号文C'_21450は64ビットのブロックに分割し,C'1_21453,C'2_21454,C'3_21455, …,C'n_212456とする。
C'1は初期値F'0_21451と排他的論理和をとり,その結果と1/B_21452の乗算を計算する。この結果をフィードバック値F'1_21457とする。平文ブロックP'1_21459はフィードバック値F'1_21457とA1_21458との排他論理和により得られる。
C'2_21454,C'3_21455, …,C'n_21456も同様に処理を行い,得られた平文ブロックP'1_21459,P'2_21462,P'3_21465, …,P'n_21468を連結し平文P'_21476とする。これをL'_21469,M'_21470,Z'_21471に分割後,さらにZ'_21471をT'_21474とR'_21475に分割し,冗長性のチェックを行う。
実施例2では,64ビットの冗長性を用いるために有限体F(264)上の加算,乗算を用いている。
この実施例に示した効率化を施すことにより,高速な暗号処理が実現可能となる。C言語による実装の例では,600メガヘルツのクロック周波数の64ビットプロセッサ上で,暗号処理で202メガビット/秒の処理速度を達成することを確認した。復号化処理では207メガビット／秒の処理速度で動作することも確認した。
上記実装で用いられている演算は擬似乱数生成,排他的論理和及び有限体F(264)上の乗算であり,特にハードウェア実装した場合に効率的である。その例として0.35μｍプロセスのゲートアレイによる実装では,擬似乱数生成器に3キロゲートの付加回路で実現可能である見積もりが得られている。また,擬似乱数生成器は並列処理が可能であるので,要求される処理速度を達成するだけの並列計算装置の実現も容易である。この場合,並列擬似乱数生成器に36キロゲート程度の回路を付加することで,最大9.6ギガビット/秒の処理速度を実現することができる。
(実施例3)
以下に示す実施例3では，別の高速な関数を使うことにより同じ安全性かつより高速な処理が可能となる。観点を変え，これまでと同じF(264)上の演算を使った場合には(F(2128)の演算相当の)より高い安全性を提供することができる。
高速化の観点では，一般にF(264)上の乗算はF(232)上のそれに比べ4倍の計算量がかかるが,実施例3では
1/４の計算量の演算を2回繰り返すので事実上2倍の高速処理が可能となる。
安全性の補強という観点では，F(264)上の演算と64ビットのフィードバック値を2度用いることで，改ざんの成功確率を，上記手法の2-64から2-128へより小さくすることができる。
この高速化手法として暗号化処理PROG1の代わりに同じく暗号化処理PROG1B,復号化処理PROG3の代わりに同じく復号化処理PROG3Bをそれぞれ使う装置を考える。
【００５０】
暗号化処理PROG1Bは,図1に示すPROG1_1009において,乱数生成サブルーチン(ステップ20004)と暗号化サブルーチン(ステップ20005)をそれぞれ乱数生成3サブルーチン21504と暗号化3サブルーチン21505に置き換えたものである。暗号化処理PROG1Bの処理の流れを図18を用いて説明する。
ステップ21502:データセットサブルーチン。初期値V,冗長性R,秘密鍵Kの入力を待つ。
ステップ21503:平文準備サブルーチン。平文の入力を待ち,平文が与えられたあと決められたパディングを行い,冗長性を付加して,最後に32ビットごとに区切って平文ブロックの列Pi(1≦i≦n)を出力する。
ステップ21504:乱数生成3サブルーチン。秘密鍵Kから,擬似乱数列Ai(1≦i≦n),Ba,Bbを出力する。
ステップ21505:暗号化3サブルーチン。擬似乱数列Ai,Ba,Bb,平文ブロック列Pi (1≦i≦n),初期値Vを使って,暗号文ブロック列Ci(1≦i≦n)を出力する。
ステップ21506:ステップ21505で得られた暗号文ブロックCi(1≦i≦n)を順にビット連結し,暗号文Cとして出力する。
【００５１】
乱数生成3サブルーチン2150４の処理を図19を用いて説明する。
ステップ21602:必要パラメータの入力。パディング後のメッセージブロック数nと,秘密鍵Kを得る。
ステップ21603:擬似乱数列Aの生成。乱数生成処理プログラムPROG2を呼び出し,長さ32nビットの擬似乱数列を生成,出力をAとする。
ステップ21604:乱数列Aをブロックに分割。擬似乱数列Aを32ビットごとに区切り順にA1,A2, …,Anとする。
ステップ21605:乱数Baの生成。秘密鍵Kを使ってPROG2を実行することにより32ビットの乱数Baを生成する。
ステップ21606:ステップ21605で生成されたBaが0ならば,ステップ21605に戻る。
ステップ21607:乱数Bbの生成。秘密鍵Kを使ってPROG2を実行することにより32ビットの乱数Bbを生成する。
ステップ21608:ステップ21607で生成されたBbが0ならば,ステップ21607に戻る。
【００５２】
暗号化3サブルーチン21505の処理を図20を用いて説明する。記号「*」,「^」はそれぞれ有限体F(232)上での乗算,加算を表す。
ステップ21702:初期値セット。FA0=FB0=Vとする。
ステップ21703:カウンタ初期化。i=1とする。
ステップ21704:フィードバック値FAi計算。
FAi=Pi^Aiとする。
ステップ21705:フィードバック値FBi計算。
FBi=(FAi*Ba)^FAi-1とする。
ステップ21706:暗号文ブロックCi計算。
Ci=(FBi*Bb)^FBi-1とする。
ステップ21707:i=nならばステップ21709を実行。
ステップ21708:カウンタiをインクリメントしステップ21704へ戻る。
【００５３】
復号化処理PROG3Bの処理の流れを図21を用いて説明する。PROG3Bは,PROG3_10020において，乱数生成サブルーチン20504と復号化サブルーチン20505をそれぞれ乱数生成3サブルーチン21804と復号化3サブルーチン21805に置き換えたものである。
ステップ21802:データセットサブルーチン。初期値V,冗長性R,秘密鍵Kの入力を待つ。
ステップ21803: 暗号文準備サブルーチン。暗号文C'の入力を待ち,暗号文C'が与えられたあと32ビットごとに区切って暗号文ブロックの列C'i(1≦i≦n)を出力する。
ステップ21804:乱数生成サブルーチン。秘密鍵Kから,擬似乱数列Ai(1≦i≦n), Ba,Bbを出力する。
ステップ21805:復号化サブルーチン。擬似乱数列Ai,Ba,Bb,暗号文ブロック列C'i(1≦i≦n),初期値Vを使って,平文ブロック列P'i(1≦i≦n)を出力する。
ステップ21806:平文切り出しサブルーチン。平文ブロックの列P'iを3つのデータ列,L',M',Z'に分割する。
ステップ21807:冗長性切り出しサブルーチン。Z'をR'とT'に分割する。
ステップ21808:T=0かつR'=Rならばステップ21810に進む。
ステップ21809:拒否を出力。ステップ21811に進む。
ステップ21810:M'をRAMへ格納する。
【００５４】
図21の復号化3サブルーチン21805の処理を図22を用いて説明する。記号「/」は有限体F(232)上での除算を表す。
ステップ21902:初期値セット。FA'0=FB'0=Vとする。
ステップ21903:1/Ba,1/Bbを事前計算しておく。
ステップ21904:カウンタ初期化。i=1とする。
ステップ21905:フィードバック値FB'i計算。
FB'i=(C'i^FB'i-1)*(1/Bb)とする。
ステップ21906:フィードバック値FA'i計算。
FA'i=(FB'i^FA'i-1)*(1/Ba)とする。
ステップ21907:平文ブロックP'i計算。P'i=FA'i^Aiとする。
ステップ21908:i=nならばステップ21910を実行。
ステップ21909:カウンタiをインクリメントしステップ21905へ戻る。
【００５５】
図23は，上述の高速化手法で用いた暗号化処理の説明図である。
メッセージM21921に長さL21920,適当なパディング21922,冗長性R21923をそれぞれ付加し,平文P21924を生成する。
これを32ビットに分割したものをそれぞれP1_21925,P2_21926,P3_21927,Pn_21928とする。
P1_21925はA1_21933と排他論理和を取り,フィードバック値FA1_21934とし，Ba_21929と有限体上の乗算を行い,その結果と初期値FA0_21930の排他論理和により,フィードバック値FB1_21939を得る。これをBb_21931と有限体上の乗算を行い,その結果と初期値FB0_21932の排他論理和により暗号文ブロックC1_21936を得る。  P2_21926はA2_21937と排他論理和を取り,フィードバック値FA2_21942とし，Ba_21929と有限体上の乗算を行い,その結果とフィードバック値FA1_21934の排他論理和により,フィードバック値FB2_21943を得る。これをBb_21931と有限体上の乗算を行い,その結果とフィードバック値FB1_21939の排他論理和により暗号文ブロックC2_21940を得る。
同様にしてPn_21928まで処理を行い,暗号文ブロックC1_21936,C2_21940,C3_21944, …,Cn_21950を得たあと,これらをこの順で連結し
,暗号文C_21951を得る。
【００５６】
図24は，対応する復号化処理の説明図である。
暗号文C'_21960は32ビットのブロックに分割し,C'1_21961,C'2_21962,C'3_21963, …,C'n_21964とする。
C'1は初期値FB'0_21965と排他的論理和をとり,その結果と1/Bb_21966の乗算を計算する。この結果をフィードバック値FB'1_21969とする。さらに,初期値FA'0_21967と排他的論理和をとり,その結果と1/Ba_21968の乗算を計算する。平文ブロックP'1_21972はフィードバック値FA'1_21970とA1_21971との排他論理和により得られる。
C'2_21962,C'3_21976, …,C'n_21964も同様に処理を行い,得られた平文ブロックP'1_21972,P'2_21976,P'3_21980, …,P'n_21985を連結し平文P'_21986とする。これをL'_21987,M'_21988,Z'_21989に分割後,さらにZ'_21989をT'_21992とR'_21993に分割し,冗長性のチェックを行う。
【００５７】
(実施例4)  以下に示す実施例4では，上述の平文準備において，平文にパディングする情報として，メッセージの長さ情報を使うことなく，暗号処理の開始を可能にする方法である。  実施例4では，実施例2における暗号化処理PROG1A中の乱数生成2サブルーチン，平文準備サブルーチン,および復号化処理プログラムPROG3Aのかわりに，それぞれ乱数生成サブルーチン4，平文準備サブルーチン2，復号化処理プログラムPROG6を使う。
【００５８】
乱数生成4サブルーチンの処理を図29を用いて説明する。
ステップ40212:必要パラメータの入力。パディング後のメッセージブロック数nと,秘密鍵Kを得る。
ステップ40213:擬似乱数列Aの生成。乱数生成処理プログラムPROG2を呼び出し,長さ64nビットの擬似乱数列を生成,出力をAとする。
ステップ40214:乱数列Aをブロックに分割。擬似乱数列Aを64ビットごとに区切り順にA1,A2, …,Anとする。
ステップ40215:乱数Bの生成。秘密鍵Kを使ってPROG2を実行することにより64ビットの乱数Bを生成する。
ステップ40216:ステップ40105で生成されたBが0ならば,ステップ40105に戻る。
ステップ40217:乱数Qの生成。秘密鍵Kを使ってPROG2を実行することにより64ビットの乱数Qを生成する。
【００５９】
次に、平文準備2サブルーチンの処理を図30，図31を用いて説明する。
ステップ40202:暗号化処理対象となるメッセージM40300の入力を待つ。メッセージM40300は，キーボード10008から入力されたり，RAM内に保存されていたり，他の媒体から導入されたりする。
ステップ40203:メッセージ長をそろえるパディング。のちの暗号処理のため、パディング後のデータを64ビットの整数倍にする。メッセージM40300の長さをLビットとすると64―L(mod 64)個の0をメッセージの末尾にパディングする。
ステップ40204:秘密データのパディング。64ビット秘密データとして与えられる秘密データQ40302をさらに末尾にパディングする。この秘密データQ40302は鍵を知るものだけが知る情報であり、例えば秘密鍵Kから生成される乱数などが考えられる。上記ステップ40217はこのための処理である。
ステップ40205:冗長性データのパディング。64ビットデータとして与えられる冗長性R40303をさらに末尾にパディングする。
ステップ40206:メッセージデータの平文ブロックへ分割。ステップ40205の結果得られたデータP40304を64ビットのブロックに区切り順にP1,P2, …,Pnとする。
【００６０】
復号化処理PROG６の処理の流れを図32,図34を用いて説明する。
ステップ40402:データセットサブルーチン。初期値V,冗長性R,秘密鍵Kの入力を待つ。
ステップ40403:暗号文準備サブルーチン。暗号文C'の入力を待ち,暗号文C'が与えられたあと32ビットごとに区切って暗号文ブロックの列C'i(1≦i≦n)を出力する。
ステップ40404:乱数生成4サブルーチン。秘密鍵Kから,擬似乱数列Ai(1≦i≦n),Bを出力する。
ステップ40405:復号化3サブルーチン。擬似乱数列Ai,B,Q,暗号文ブロック列C'i(1≦i≦n),初期値Vを使って,平文ブロック列P'i(1≦i≦n)を出力する。
ステップ40406:平文切り出し2サブルーチン。平文ブロックの列P'i40601を3つのデータ列,M'40602,Q'40603,R'40604に分割する。
ステップ40407:Q'40603=Q40302 かつR'40604=R40303ならばステップ40409に進む。
ステップ40408:拒否を出力。ステップ40410に進む。
ステップ40409:M'をRAMへ格納する。
ステップ40410:終了。
【００６１】
次に平文切り出し2サブルーチンの処理を図33を用いて説明する。
ステップ40502:復号文のうち、最後の128ビットを除く全データを、平文ブロックM'とする。
ステップ40503:処理40502の残りの128ビットのうち、上位64ビットをQ'とする。
ステップ20804:さらに残りのデータ(64ビット)をR'とする。
【００６２】
(実施例5)
上記実施例1から4は並列計算を考えない単一プロセッサによる処理の実施形態であった。実施例5において，本発明が並列処理への応用も簡単であることを示す。
実施例5のシステム構成(図示していない)が，図１の構成と異なるのは，コンピュータA10002については，CPU1000４の代わりにCPU1_30004,CPU2_30005を装備しており,RAM10005には，図１の構成に加えて並列暗号処理プログラムPROG4_30016が保存されている点である。コンピュータB10003については，
CPU10015の代わりにCPU1_30017,CPU2_30018を装備しており,RAM10016には，図１の構成に加えて並列復号処理プログラムPROG5_30025が保存されている点が異なる。
コンピュータA10002は,並列暗号化処理プログラムPROG4_30016を実行し,メッセージM1001４の暗号文C10022を作成し,送信する。コンピュータB10003は,暗号文C10022を受信したあと,並列復号化処理プログラムPROG5_30025を実行し,もし改ざんが検出されなければ復号化結果をRAM10016に保存する。
並列暗号化処理プログラムPROG4_30016は,コンピュータA10002において，RAM10005から読み出されて,CPU1_30004とCPU2_30005により実行されることで実現される。並列暗号化処理プログラムPROG4_30016は，サブルーチンとして暗号化処理プログラムPROG1_10009,乱数生成処理PROG2_10010を内部で呼び出し,実行する。
並列復号化処理プログラムPROG5_30025は,コンピュータB10003において，RAM10016から読み出されてCPU1_30017とCPU2_30018により実行される。並列復号化処理プログラムPROG5_30025は,サブルーチンとして復号化処理プログラムPROG3_10020,乱数生成処理PROG2_10021を内部で呼び出し,実行する。
その他の構成，動作は図１と同じである。
【００６３】
並列暗号化処理プログラムPROG4_3001６の処理の流れを図25を用いて説明する。記号「A||B」はビット列AとBの連結を示す。
ステップ40002:CPU1の実行するメッセージ処理によりメッセージMをM1,M2に2分割する。
ステップ40003:CPU1が実行するPROG1_10009による暗号化処理により,初期値V+1,冗長性R+1,秘密鍵K,平文M1,を使って,暗号文C1を出力する。
ステップ40004:CPU2が実行するPROG1_10009による暗号化処理により,初期値V+2,冗長性R+2,秘密鍵K,平文M2,を使って,暗号文C2を出力する。
ステップ40005:CPU1が実行するPROG1_10009による暗号化処理により,初期値V,冗長性R,秘密鍵K,平文(R1||R2),を使って,暗号文C3を出力する。
ステップ40006:暗号文Cの生成。C=C1||C2||C3とする。
ステップ40007:暗号文Cをメモリへ保存
並列復号化処理プログラムPROG5_30025の処理の流れを図26を用いて説明する。
ステップ40102:CPU1の実行する暗号文処理により暗号文C'をC'1,C'2,C'3に3分割する。C'3は192ビットであり,C'1,C'2は同じ長さ,かつC'=C'1||C'2||C'3である。
ステップ40103:CPU1が実行するPROG3_10020による復号化処理により,初期値V+1,冗長性R+1,秘密鍵K,暗号文ブロックC'1,を使って,復号化を行い結果を保存する。
ステップ40104:CPU2が実行するPROG3_10020による復号化処理により,初期値V+2,冗長性R+2,秘密鍵K,暗号文ブロックC'2を使って,復号化を行い,結果を保存する。
ステップ40105:ステップ40103の復号化結果,ステップ4010４の復号化結果のうち少なくともひとつが非受理ならばステップ40111を実行する。
ステップ40106: CPU1が実行するPROG3_10020による復号化処理により,初期値V,冗長性R,秘密鍵K,暗号文ブロックC'3を使って,復号化を行い,結果を保存する。
ステップ40107:ステップ4010６の復号化結果が非受理ならばステップ40111を実行する。
ステップ40108:ステップ4010６の復号化結果が(R+1)||(R+2)でないなら,ステップ40111を実行する。
ステップ40109:復号化結果M'=M'1||M'2とする。
ステップ40110:M'をメモリへ格納し,ステップ40112を実行する。
ステップ40111:非受理を出力する。
【００６４】
実施例5により独立な二つのプロセッサを使った並列暗号処理が可能となる。
図27は，上述の並列化手法で用いた暗号化処理の説明図である。
メッセージM401402を分割して生成したM1_40141,M2_40142にそれぞれ冗長性,R+1,R+2を付加した,40143,40144を暗号化処理40146,40147により暗号化,暗号文ブロックC1_40149,C2_40150を得る。
さらに冗長性R+1,R+2をメッセージとして冗長性をR使って暗号化し,暗号文ブロックC3_40151を得る。
暗号文ブロックC1_40149,C2_40150,C3_40151を連結し暗号文C40152として出力する。
【００６５】
図28は,対応する並列復号化処理の説明図である。
暗号文C'40160を3分割し,C'1_40161,C'2_40162,C'3_40163を生成する。
それぞれを復号化処理40164,40165,40166により復号化,平文ブロック40167,40168,40169を得る。
【００６６】
これらすべてが受理であって,平文ブロック40167,40168の冗長性が,平文ブロック40169のメッセージ部と同じであり,さらに平文ブロック40169が予め共有されている冗長性であれば,平文ブロック40167,40168からそれぞれメッセージ部M'1_40170,M'2_40171を取り出し,これらを連結してメッセージM'40172を得る。
【００６７】
以上の各実施例におけるCPUはプログラムを実行するものであれば，汎用，専用を問わず用いることができる。また，各実施例は，CPUがプログラムを実行することにより実現される例であったが，各処理を専用のハードウェアを用いても，高速にかつ，低価格で実現することも可能である。
【００６８】
以上の各実施例での擬似乱数生成器として，これまで知られている擬似乱数生成器はどれも適用可能である。線形フィードバックレジスタ(LFSR)に基づく非線形フィルタによる擬似乱数生成器、非線形フィードバックシフトレジスタ、結合生成器、縮小生成器、クロック制御式擬似乱数生成器、Geffe生成器、相互ステップ生成器、RC4、SEAL、PANAMA、ブロック暗号のOFBモード、ブロック暗号のカウンタモード、その他ハッシュ関数を使った擬似乱数生成器などを用いることができる。
【００６９】
(実施例6)
上記実施例1から実施例5は暗号処理を目的とした実施形態であった。実施例6以降において，本発明がさまざまな情報システムへの応用も可能であることを示す。
図35はネットワーク50009によって接続されたコンピュータA50016,コンピュータB50017を含む,コンピュータA50009からコンピュータB50016への暗号通信を目的としたシステム構成を示すものである。コンピュータA50009は内部にCPU50007, RAM50001,ネットワークインターフェース装置50008を装備している。RAM50001には鍵交換プロトコルを行うための鍵交換プロトコルソフトウェア_50002,センターの公開鍵50004、秘密鍵生成プログラム50003、暗号プログラム50006、そして暗号通信を行いたい通信データ50005(上記各実施例におけるメッセージMに相当)が保存されている。コンピュータB50017は内部にCPU50014,RAM50010,ネットワークインターフェース装置50015を装備している。RAM50010には鍵交換プロトコルソフトウェア_50011,復号化プログラム50013が保存されている。
【００７０】
コンピュータAは秘密鍵生成プログラム50003を実行することにより、コンピュータB50017との暗号通信に用いる秘密鍵を生成する。次に、コンピュータA50016とコンピュータB50017は、それぞれ各々の鍵交換プロトコルソフトウェア50002、50011を実行することで、コンピュータAが生成した秘密鍵を共有する。
【００７１】
秘密鍵を共有した後，コンピュータA50016は本発明に基づく暗号プログラム50006を実行することで、通信データ50005を高速に暗号処理する。コンピュータA50016は結果得られた暗号処理結果をネットワークインターフェース装置50008を用いて、ネットワーク50009を通じてコンピュータB50017に送信する。
【００７２】
コンピュータB50017は本発明による復号プログラム50013を実行することで、受信した暗号文を高速に復号処理し、通信データを復号化する。
【００７３】
本実施例では本発明を使うことにより、ハードウェア資源が限られた場合であっても、高速かつ安全な暗号通信が可能となる例を示している。つまり、従来の暗号方式よりも高速であり、かつ、秘匿のみならず数学的に証明された改竄検知の機能を備える高い安全性を備えた暗号通信システムを実現可能である。
【００７４】
(実施例7)
上記実施例6は暗号処理をソフトウェアによる実装の実施形態であった。実施例7において，本発明がハードウェア実装も可能であることを示す。
図36はネットワークを用いた暗号通信システムにおける暗号化処理装置の構成図を示している。コンピュータ50110は内部に、RAM50101、CPU50104、ネットワークインターフェース装置50105を装備し、ネットワーク50106に接続されている。RAM50101には暗号化するための通信データ50103(上記各実施例におけるメッセージMに相当)、通信プログラム50102が保存されており、CPU50104は通信プログラム50102を実行することで通信データ50103をネットワークインターフェース装置50105に出力する。ネットワークインターフェース装置50105は秘密鍵生成回路50107、暗号処理回路50109、鍵交換プロトコル回路50108を装備しており、センターの公開鍵50110が記憶領域に書き込まれている。ネットワークインターフェース装置50105は、通信プログラム50102の実行に応じて、秘密鍵生成回路50107により秘密鍵を生成し、鍵交換プロトコル回路50108により、ネットワーク上の別の機器との鍵交換を行い、上記生成された秘密鍵を通信相手機器と共有する。ネットワークインターフェース装置50105は、暗号処理回路50109により、入力された通信データ50103に対して、生成、共有された秘密鍵を用いて高速に暗号処理を行い暗号文を生成し，ネットワーク50106へ送信する。
【００７５】
本実施例では本発明を使うことにより、限られたハードウェア資源を使って、高速かつ安全な暗号通信が可能となる例を示している。特に暗号処理として実施例2の方式を使えばより効率的かつ安全な暗号通信が可能となる。これは、実施例2に示した，有限体F264上の加算や乗算が、ハードウェア実装に向いているからである。復号処理についても同様にハードウェア実装が可能である。
本実施例が示すように、本発明は少ないゲート数でのハードウェア実装や、非常に高速な処理が可能なハードウェア実装を実現可能とする。
【００７６】
(実施例8)
上記実施例6および7に示した暗号処理可能なコンピュータを使うことで、暗号により保護されるコンテンツ配送などを簡単に実現することができる。実施例8ではコンテンツ配送の実施例を示す。
【００７７】
図37に示すように，デジタル情報としてのコンテンツ50201を保存した記憶装置（半導体記憶装置、ハードディスク，テープなど磁気記録装置、DVD、MOなど光記録装置などメディアは限定されない）は、本発明による暗号処理可能なコンピュータ50202へ接続されている。当該また，コンテンツを再生したい、物理的に離れた場所にあるかもしれない情報再生装置50205（MPEG再生装置やデジタルテレビ、パソコンなど）は本発明による復号処理可能な外部符号化装置50204へ接続されている。コンピュータ50202と外部符号化装置とはネットワーク50203を介して接続されている。
【００７８】
コンテンツ50201は暗号処理可能なコンピュータ50202により暗号化されてネットワーク50203へ送信される。復号処理可能な外部符号化装置50204は暗号化されたコンテンツを復号化したあと、復号化結果を情報再生装置50205へ出力する。情報再生装置50205は入力情報を保存、再生する。
【００７９】
情報再生装置50205が扱うコンテンツ50201には，電子ファイルのみならず、電子計算機用ソフトウェア、音声や画像といったマルチメディアデータも含まれる。音声や画像など、リアルタイム性が要求されるようなコンテンツの場合には、本発明を用いることにより高速な暗号処理や復号処理が可能となり、安全でスムーズなリアルタイム画像伝送が可能となる。また、伝送路中の改竄や雑音によるデータの破壊に対しても受信装置はこれを検知することができるため、伝送エラーのないことが保証された通信が実現できる。
【００８０】
(実施例9)
実施例8ではコンテンツを、ネットワークを介して送信していた。しかし、非常に大容量の情報の場合、DVDなどによる暗号文の事前配送のあと、復号化用の鍵を復号許可時に送信する手法が効率的である。このようなシステムを実施例9に示す。
【００８１】
図38に示すように，コンテンツは暗号文として、予め消費者へDVD-ROM50307などのメディアを用いて配信されている。消費者はコンテンツの代金支払いに関する情報(振り込み情報という)50306を、消費者のパソコン50304で実行されるコンテンツ鍵入手プログラム50305に入力し、コンテンツ鍵入手プログラム50305はネットワーク50303を介して鍵サーバ50302のコンテンツ鍵テーブル中の鍵を得る。復号化プログラム50308は得られた鍵を用いてDVD-ROM50307に記録されたコンテンツ暗号文を復号する。復号結果は情報再生装置50309へ出力され、コンテンツが再生される。
【００８２】
本実施例ではコンテンツを情報再生装置50309への出力せず、パソコン50304自身で再生を行うことも可能である。この典型の例として、コンテンツがパソコンで実行されるプログラムの場合に，このような再生方法が有効である。また、DVD-ROMに記録されている暗号コンテンツがいくつかの部分に分割可能で、それぞれの部分が異なる鍵で暗号化されている場合、コンテンツ鍵入手プログラム50305へ配送される鍵を制御することにより消費者が復号化できるコンテンツを制限することも可能である。
【００８３】
実施例9では、DVD-ROM50307に記録されたデータの読み出しを想定しているが、一般にDVD-ROM503070へ書き込まれるデータの大きさは非常に大きく(数10メガバイト〜数100メガバイト)処理の速い暗号方式が必須である。本発明は、高速な復号処理を実現可能とするため、DVDメディアを使った有料コンテンツ配信への応用に適している。
【００８４】
(実施例10)
実施例10はネットワークのパケット配送を制御する、ルータに適用した例を示している。このルータはネットワーク送信時、行き先のルータに応じてパケットに異なる暗号処理を行う。
【００８５】
図39は暗号ルータの構造を示した図である。ネットワークルータ50401は、内部にルーティングテーブル50402とパケット切り替え器50403、ネットワークインターフェースA50404, 同じくB50405、同じくC50406、及び内蔵並列暗号処理装置50410を装備している。ネットワークインターフェースA50404, B50405、C50406は、それぞれ外部のネットワークA50407、B50408、C50409に接続している。
【００８６】
内部並列暗号処理装置50410は、内部に秘密鍵テーブル50411、ルータ鍵保存領域50412、並列暗号処理回路50413を装備している。
【００８７】
ネットワークA50407より送られてきたパケットはネットワークインターフェースA50404を通じて内部並列暗号処理装置50410へと送信される。内部並列暗号処理装置50410では、送られてきたパケットがネットワークA50407からであることを認識した後に、秘密鍵テーブル50411を参照しネットワークA50407に対応する秘密鍵を得て、ルータ鍵保存領域50412に保存して並列暗号処理回路50413で復号処理を行う。復号化の結果をパケット切り替え器50403へ送信する。
【００８８】
このパケットがネットワークBに送信されるべきものであると仮定すると、パケット切り替え器50403は内部並列暗号処理装置50410へパケットを渡す。内部並列暗号処理装置50410は秘密鍵テーブル50411を参照し，ネットワークB50408に対応する秘密鍵を得て、ルータ鍵保存領域50412に保存して並列暗号処理回路50413で暗号処理を行う。暗号化の結果をネットワークインターフェースB50405へ送信し、ネットワークインターフェースB50405はネットワークB50408へ暗号パケットを送信する。
【００８９】
本実施例は、非常に豊かなハードウェア資源の使用が許され、非常に高速な暗号通信が要求される環境での応用例である。ブロック暗号のCBCモードでは、並列処理が困難であるため、仮にハードウェア資源が豊富な場合にも処理速度をあげることが難しい。これに対して、本発明では、擬似乱数生成処理が平文や暗号文処理と独立であるため、並列処理性が非常に高い。すなわち並列処理に向いたハードウェア資源が豊富に使用できる環境では、より一層高速な通信速度を達成することができる。
【００９０】
【発明の効果】
より安全で高速な共通鍵暗号技術を提供することが可能となる。
【図面の簡単な説明】
【図１】各実施例のシステム構成図を示す。
【図２】平文準備サブルーチンのフロー図を示す。
【図３】乱数生成サブルーチンのフロー図を示す。
【図４】暗号化サブルーチンのフロー図を示す。
【図５】図1の復号化処理プログラムのフロー図を示す。
【図６】図7の暗号文準備サブルーチンのフロー図を示す。
【図７】図7の復号化サブルーチンのフロー図を示す。
【図８】図7の平文切出しサブルーチンのフロー図を示す。
【図９】図７の冗長性切出しサブルーチンのフロー図を示す。
【図１０】暗号化処理の,データブロックによる図を示す。
【図１１】図7で示した復号化処理の,データブロックによる図を示す。
【図１２】実施例2の乱数生成2サブルーチンのフロー図を示す。
【図１３】実施例2の暗号化2サブルーチンのフロー図を示す。
【図１４】実施例2の復号化処理プログラムのフロー図を示す。
【図１５】実施例2の復号化2サブルーチンのフロー図を示す。
【図１６】実施例2の暗号化処理の,データブロックによる図を示す。
【図１７】実施例2の復号化処理の,データブロックによる図を示す。
【図１８】実施例3の暗号化処理プログラムのフロー図を示す。
【図１９】実施例3の乱数生成3サブルーチンのフロー図を示す。
【図２０】実施例3の暗号化3サブルーチンのフロー図を示す。
【図２１】実施例3の復号化処理プログラムのフロー図を示す。
【図２２】実施例3の復号化3サブルーチンのフロー図を示す。
【図２３】実施例3の暗号化処理の,データブロックによる図を示す。
【図２４】実施例3の復号化処理の，データブロックによる図を示す。
【図２５】実施例5の並列暗号化処理プログラムのフロー図を示す。
【図２６】実施例5の並列復号化処理プログラムのフロー図を示す。
【図２７】実施例5の暗号化処理の，データブロックによる図を示す。
【図２８】実施例5の復号化処理の，データブロックによる図を示す。
【図２９】実施例4の乱数生成4サブルーチンのフロー図を示す。
【図３０】実施例4の平文準備2サブルーチンのフロー図を示す。
【図３１】実施例4のメッセージに対するパディング処理の説明図を示す。
【図３２】実施例4の復号化処理プログラムのフロー図を示す。
【図３３】図32の平文切り出し2サブルーチンのフロー図を示す。
【図３４】実施例4の復号文に対する切り出し処理の説明図を示す。
【図３５】実施例6の暗号通信を目的としたシステム構成図を示す。
【図３６】実施例7の暗号通信システムにおける暗号化処理装置の構成図を示す。
【図３７】実施例8のコンテンツ配送システム構成図を示す。
【図３８】実施例9のシステム構成図を示す。
【図３９】実施例10の暗号ルータの構成図を示す。
【符号の説明】
10001,30001:ネットワーク
10002,10003,30002,30003:コンピュータ
10004,10015,30004,40005,30017,30018:CPU
10005,10016,30006,30019:メモリ
10006,10017,30007,30020:ネットワークインターフェース
10007,10018,30008,30021:ディスプレイ
10008,10019,30009,30022:キーボード
【図１】
0003864798.tif 000002
【図２】
0003864798.tif 000003
【図３】
0003864798.tif 000004
【図４】
0003864798.tif 000005
【図５】
0003864798.tif 000006
【図６】
0003864798.tif 000007
【図７】
0003864798.tif 000008
【図８】
0003864798.tif 000009
【図９】
0003864798.tif 000010
【図１０】
0003864798.tif 000011
【図１１】
0003864798.tif 000012
【図１２】
0003864798.tif 000013
【図１３】
0003864798.tif 000014
【図１４】
0003864798.tif 000015
【図１５】
0003864798.tif 000016
【図１６】
0003864798.tif 000017
【図１７】
0003864798.tif 000018
【図１８】
0003864798.tif 000019
【図１９】
0003864798.tif 000020
【図２０】
0003864798.tif 000021
【図２１】
0003864798.tif 000022
【図２２】
0003864798.tif 000023
【図２３】
0003864798.tif 000024
【図２４】
0003864798.tif 000025
【図２５】
0003864798.tif 000026
【図２６】
0003864798.tif 000027
【図２７】
0003864798.tif 000028
【図２８】
0003864798.tif 000029
【図２９】
0003864798.tif 000030
【図３０】
0003864798.tif 000031
【図３１】
0003864798.tif 000032
【図３２】
0003864798.tif 000033
【図３３】
0003864798.tif 000034
【図３４】
0003864798.tif 000035
【図３５】
0003864798.tif 000036
【図３６】
0003864798.tif 000037
【図３７】
0003864798.tif 000038
【図３８】
0003864798.tif 000039
【図３９】
0003864798.tif 000040