JP6035459B2

JP6035459B2 - 暗号化装置、復号化装置、及びプログラム

Info

Publication number: JP6035459B2
Application number: JP2012084113A
Authority: JP
Inventors: 雅則大矢; 聖史入山; ルイジ・アカルディ; マッシモ・レゴリ
Original assignee: ACTEIIVE CORPORATION; CRYPTO BASIC CORPORATION
Current assignee: ACTEIIVE CORPORATION; CRYPTO BASIC CORPORATION
Priority date: 2012-04-02
Filing date: 2012-04-02
Publication date: 2016-11-30
Anticipated expiration: 2032-04-02
Also published as: JP2013213930A; EP2835932B1; EP2835932A1; CN104303453A; EP2835932A4; US20150110269A1; CN104303453B; TW201404107A; US9467286B2; TWI606714B; WO2013150880A1; KR20140143210A; KR102033196B1

Description

本発明は、暗号化装置、復号化装置、及びプログラムに関する。

従来より、暗号化処理を高速、かつ暗号解読強度を強くする暗号化装置が知られている（特許文献１）。この暗号化装置では、初期処理関数により、平文Ｄを分割し複数の分割データとして出力し、複数の分割データを演算関数により暗号鍵Ｋと同じ大きさに拡大置換し、係数を媒介することにより演算関数を可変にする。その係数は、媒介変数生成部により生成される。そして、非線形暗号化ブロック処理部により、分割データと暗号鍵Ｋとを変数として非線形に暗号化し、暗号化した複数の分割暗号化データを出力する。さらに、後処理関数により、演算関数の逆関数を使い分割暗号化データを分割データと同じ大きさに縮小置換し、分割データを合成し暗号文として出力し、係数を媒介することにより逆関数の演算関数を可変にする。

また、秘密情報ａ，ｂと乱数情報ｍ1，ｍ2とを排他的論理和により加算することによって秘密情報ａ，ｂをマスクし、マスクされた秘密情報Ａ，Ｂを算出する手段と、マスクされた秘密情報Ａ，Ｂと乱数情報ｍ1，ｍ2とを用いて、マスクされた秘密情報Ａ，Ｂのマスクを除去するための中間値Ｔｅｍｐ１〜Ｔｅｍｐ３を算出する手段と、マスクされた秘密情報Ａ，Ｂと中間値Ｔｅｍｐ１〜Ｔｅｍｐ３を用いて、秘密情報ａ，ｂの論理積や論理和に関する演算を行う手段とを備えた暗号処理装置が知られている（特許文献２）。

特許文献１，２によって開示された暗号処理技術は暗号化処理の高速性、安全性の高度化を図るものであるが、理論的に解読が可能であるという潜在的な危険性を有する等の問題を抱えている。この問題を解消するためには容量が大きくなって高速性を犠牲にされる場合があり、「高速」、「安全」、「軽量」という暗号化処理の要求を総合的に満足させる技術はなかった。そこで、理論上は解読不能な非可換関数を元にした暗号方式が提案されている（非特許文献１）。

特開2003-241656号公報特開2009-005164号公報

L.Accardi, M.Regoli, M.Ohya，"The QP-DYN Algorithm"，QP-PQ 28, Quantum Bio-Informatics IV, 1-16, 2011

非特許文献１によって開示された技術では暗号化処理の概念は示されているが、高速性と暗号の頑健性を決定する力学系への変換やベクトル列の導出などを設定すること、さらにはこの暗号化処理を装置に実装することは困難であった。

本発明は、前記課題を鑑み、暗号化対象データのビット数が可変である場合において、暗号化処理を高速化し、かつ暗号解読強度を強くすることができる暗号化装置、復号化装置、及びプログラムを提供することを目的とする。

上記の目的を達成するために第１の発明に係る暗号化装置は、復号化装置と共通に設定されたプライベートデータであるｄ×ｄの行列Ａ、及び２つの素数ｐ１、ｐ２に基づいて、２つの非可換行列Ａ１、Ａ２を生成する行列生成手段と、前記復号化装置と共通に設定されたｄ次元の初期ベクトルｖ₀又は前回求められたｄ次元のベクトルｖ_i-1 ¹に、非可換行列Ａ１を作用させて、ベクトルｖ_i,¹を求めると共に、前記初期ベクトルｖ₀、又は前回求められたｄ次元のベクトルｖ_i-1 ²に、非可換行列Ａ２を作用させて、ベクトルｖ_i ²を求める行列作用手段であって、前記非可換行列Ａ１、Ａ２を作用させる際の和演算及び積演算の少なくとも一方を、予め定められた、複数種類の演算子を組み合わせた演算方法に置換して、非可換行列Ａ１、Ａ２を作用させる行列作用手段と、前記行列作用手段によって求められたベクトルｖ_i ¹に対して非線形変換を行ってビット列に変換し、前回求められたビット列Ｗ１に結合させると共に、ベクトルｖ_i ²に対して非線形変換を行ってビット列に変換し、前回求められたビット列Ｗ２に結合させるビット列変換手段と、前記ビット列Ｗ１及び前記ビット列Ｗ２の各々のビット数が、暗号化対象データを表わすビット列のビット数になるまで、前記行列作用手段による作用及び前記ビット列変換手段による変換を繰り返すビット数判定手段と、前記ビット列Ｗ１及び前記ビット列Ｗ２の排他的論理和を計算して、擬似乱数ビット列を求める擬似乱数列発生手段と、前記擬似乱数列発生手段によって求められた擬似乱数ビット列と、前記暗号化対象データを表わすビット列との排他的論理和を計算することにより、前記暗号化対象データを暗号化する暗号化手段と、を含んで構成されている。

第２の発明に係るプログラムは、コンピュータを、復号化装置と共通に設定されたプライベートデータであるｄ×ｄの行列Ａ、及び２つの素数ｐ１、ｐ２に基づいて、２つの非可換行列Ａ１、Ａ２を生成する行列生成手段、前記復号化装置と共通に設定されたｄ次元の初期ベクトルｖ₀又は前回求められたｄ次元のベクトルｖ_i-1 ¹に、非可換行列Ａ１を作用させて、ベクトルｖ_i,¹を求めると共に、前記初期ベクトルｖ₀、又は前回求められたｄ次元のベクトルｖ_i-1 ²に、非可換行列Ａ２を作用させて、ベクトルｖ_i ²を求める行列作用手段であって、前記非可換行列Ａ１、Ａ２を作用させる際の和演算及び積演算の少なくとも一方を、予め定められた、複数種類の演算子を組み合わせた演算方法に置換して、非可換行列Ａ１、Ａ２を作用させる行列作用手段、前記行列作用手段によって求められたベクトルｖ_i ¹に対して非線形変換を行ってビット列に変換し、前回求められたビット列Ｗ１に結合させると共に、ベクトルｖ_i ²に対して非線形変換を行ってビット列に変換し、前回求められたビット列Ｗ２に結合させるビット列変換手段、前記ビット列Ｗ１及び前記ビット列Ｗ２の各々のビット数が、暗号化対象データを表わすビット列のビット数になるまで、前記行列作用手段による作用及び前記ビット列変換手段による変換を繰り返すビット数判定手段、前記ビット列Ｗ１及び前記ビット列Ｗ２の排他的論理和を計算して、擬似乱数ビット列を求める擬似乱数列発生手段、及び前記擬似乱数列発生手段によって求められた擬似乱数ビット列と、前記暗号化対象データを表わすビット列との排他的論理和を計算することにより、前記暗号化対象データを暗号化する暗号化手段として機能させるためのプログラムである。

このように、非可換行列Ａ１、Ａ２を作用させる際の和演算及び積演算の少なくとも一方を、複数種類の演算子を組み合わせた演算方法に置換して、ベクトルに、非可換行列Ａ１、Ａ２を繰り返し作用させると共に非線形変換を行って、得られるビット列Ｗ１、Ｗ２の排他的論理和を計算して、擬似乱数ビット列を求め、擬似乱数ビット列を用いて暗号化することにより、暗号化対象データのビット数が可変である場合において、暗号化処理を高速化し、かつ暗号解読強度を強くすることができる。

第１の発明に係る行列作用手段は、前記初期ベクトルｖ₀、又は前回求められたベクトルｖ_i-1 ¹に、非可換行列Ａ１を作用させて、前記ベクトルｖ_i ¹を求める際に、ベクトルｖ_i ¹の要素毎に、既に求められたベクトルｖ_i ¹の要素に置き換えた初期ベクトルｖ₀、又は前記ベクトルｖ_i-1 ¹に、非可換行列Ａ１を作用させて、ベクトルｖ_i ¹の前記要素を計算し、前記初期ベクトルｖ₀、又は前回求められたベクトルｖ_i-1 ²に、非可換行列Ａ２を作用させて、前記ベクトルｖ_i ²を求める際に、ベクトルｖ_i ²の要素毎に、既に求められたベクトルｖ_i ²の要素に置き換えた初期ベクトルｖ₀、又は前記ベクトルｖ_i-1 ²に、非可換行列Ａ２を作用させて、ベクトルｖ_i ²の前記要素を計算するようにすることができる。これによって、暗号解読強度をより強くすることができる。

第１の発明に係るビット列変換手段は、前記非線形変換として、前記行列作用手段によって求められたベクトルｖ_i,¹をビット列に変換し、変換されたビット列に対して、所定ビット数の先頭ビット列をカットするカットオフ処理を行い、前回求められたビット列Ｗ１に結合させると共に、ベクトルｖ_i,²をビット列に変換し、変換されたビット列に対して、前記カットオフ処理を行い、前回求められたビット列Ｗ２に結合させるようにすることができる。これによって、暗号解読強度をより強くすることができる。

また、上記のビット列変換手段は、前記カットオフ処理として、前記変換されたビット列に対して、先頭から連続する０と、先頭から最初に出現する１とからなる先頭ビット列をカットすると共に、前記先頭ビット列がカットされた前記ビット列から、予め定められたビット数の先頭ビット列をカットする処理を行うようにすることができる。これによって、暗号解読強度をより強くすることができる。

第３の発明に係る復号化装置は、暗号化装置と共通に設定されたプライベートデータであるｄ×ｄの行列Ａ、及び２つの素数ｐ１、ｐ２とに基づいて、２つの非可換行列Ａ１、Ａ２を生成する行列生成手段と、前記暗号化装置と共通に設定されたｄ次元の初期ベクトルｖ₀又は前回求められたｄ次元のベクトルｖ_i-1 ¹に、非可換行列Ａ１を作用させて、ベクトルｖ_i ¹を求めると共に、前記初期ベクトルｖ₀、又は前回求められたｄ次元のベクトルｖ_i-1 ²に、非可換行列Ａ２を作用させて、ベクトルｖ_i,²を求める行列作用手段であって、前記非可換行列Ａ１、Ａ２を作用させる際の和演算及び積演算の少なくとも一方を、予め定められた、複数種類の演算子を組み合わせた演算方法に置換して、非可換行列Ａ１、Ａ２を作用させる行列作用手段と、前記行列作用手段によって求められたベクトルｖ_i ¹に対して非線形変換を行ってビット列に変換し、前回求められたビット列Ｗ１に結合させると共に、ベクトルｖ_i ²に対して非線形変換を行ってビット列に変換し、前回求められたビット列Ｗ２に結合させるビット列変換手段と、前記ビット列Ｗ１及び前記ビット列Ｗ２の各々のビット数が、復号化対象データを表わすビット列のビット数になるまで、前記行列作用手段による作用及び前記ビット列変換手段による変換を繰り返すビット数判定手段と、

前記ビット列Ｗ１及び前記ビット列Ｗ２の排他的論理和を計算して、擬似乱数ビット列を求める擬似乱数列発生手段と、前記擬似乱数列発生手段によって求められた擬似乱数ビット列と、前記復号化対象データを表わすビット列との排他的論理和を計算することにより、前記復号化対象データを復号化する復号化手段と、を含んで構成されている。

第４の発明に係るプログラムは、コンピュータを、暗号化装置と共通に設定されたプライベートデータであるｄ×ｄの行列Ａ、及び２つの素数ｐ１、ｐ２とに基づいて、２つの非可換行列Ａ１、Ａ２を生成する行列生成手段、前記暗号化装置と共通に設定されたｄ次元の初期ベクトルｖ₀又は前回求められたｄ次元のベクトルｖ_i-1 ¹に、非可換行列Ａ１を作用させて、ベクトルｖ_i ¹を求めると共に、前記初期ベクトルｖ₀、又は前回求められたｄ次元のベクトルｖ_i-1 ²に、非可換行列Ａ２を作用させて、ベクトルｖ_i ²を求める行列作用手段であって、前記非可換行列Ａ１、Ａ２を作用させる際の和演算及び積演算の少なくとも一方を、予め定められた、複数種類の演算子を組み合わせた演算方法に置換して、非可換行列Ａ１、Ａ２を作用させる行列作用手段、前記行列作用手段によって求められたベクトルｖ_i ¹に対して非線形変換を行ってビット列に変換し、前回求められたビット列Ｗ１に結合させると共に、ベクトルｖ_i ²に対して非線形変換を行ってビット列に変換し、前回求められたビット列Ｗ２に結合させるビット列変換手段、前記ビット列Ｗ１及び前記ビット列Ｗ２の各々のビット数が、復号化対象データを表わすビット列のビット数になるまで、前記行列作用手段による作用及び前記ビット列変換手段による変換を繰り返すビット数判定手段、前記ビット列Ｗ１及び前記ビット列Ｗ２の排他的論理和を計算して、擬似乱数ビット列を求める擬似乱数列発生手段、及び前記擬似乱数列発生手段によって求められた擬似乱数ビット列と、前記復号化対象データを表わすビット列との排他的論理和を計算することにより、前記復号化対象データを復号化する復号化手段として機能させるためのプログラムである。

このように、非可換行列Ａ１、Ａ２を作用させる際の和演算及び積演算の少なくとも一方を、複数種類の演算子を組み合わせた演算方法に置換して、ベクトルに、非可換行列Ａ１、Ａ２を繰り返し作用させると共に非線形変換を行って、得られるビット列Ｗ１、Ｗ２の排他的論理和を計算して、擬似乱数ビット列を求め、擬似乱数ビット列を用いて復号化することにより、復号化対象データのビット数が可変である場合において、復号化処理を高速化し、かつ暗号解読強度を強くすることができる。

本発明に係る暗号化装置、復号化装置、及びプログラムによれば、非可換行列Ａ１、Ａ２を作用させる際の和演算及び積演算の少なくとも一方を、複数種類の演算子を組み合わせた演算方法に置換して、ベクトルに、非可換行列Ａ１、Ａ２を繰り返し作用させると共に非線形変換を行って、得られるビット列Ｗ１、Ｗ２の排他的論理和を計算して、擬似乱数ビット列を求め、擬似乱数ビット列を用いて暗号化又は復号化することにより、暗号化対象データ又は復号化対象データのビット数が可変である場合において、暗号化処理又は復号化処理を高速化し、かつ暗号解読強度を強くすることができる。

本発明の実施の形態に係る暗号化処理システムの構成を示す概略図である。本発明の実施の形態に係る暗号復号装置の構成を示す概略図である。（Ａ）暗号化方法を説明するための図、及び（Ｂ）復号化方法を説明するための図である。本発明の実施の形態に係る暗号復号装置における擬似乱数列発生処理ルーチンの内容を示すフローチャートである。実験結果を示すグラフである。

以下、図面を参照して本発明の実施の形態を詳細に説明する。

＜システム構成＞
図１に示すように、本発明の実施の形態に係る暗号化処理システム１０は、暗号復号装置１２Ａ、１２Ｂと、複数のユーザ端末１４Ａと、複数のユーザ端末１４Ｂと、インターネットアクセス網１６とを備えている。なお、暗号復号装置１２Ａ、１２Ｂは、暗号化装置、復号化装置の一例である。

複数のユーザ端末１４Ａは、暗号復号装置１２Ａと接続されており、暗号復号装置１２Ａは、インターネットアクセス網１６に接続されている。また、複数のユーザ端末１４Ｂは、暗号復号装置１２Ｂと接続されており、暗号復号装置１２Ｂは、インターネットアクセス網１６に接続されている。暗号復号装置１２Ａ、１２Ｂは、インターネットアクセス網１６を介して相互に接続されている。

ユーザ端末１４Ａは、インターネットアクセス網１６を介したデータ送信を行う場合に、暗号復号装置１２Ａを介して、送信データがインターネットアクセス網１６に出力され、一方、インターネットアクセス網１６を介したデータ受信を行う場合に、暗号復号装置１２Ａを介して、受信データがインターネットアクセス網１６から入力される。

また、ユーザ端末１４Ｂは、インターネットアクセス網１６を介したデータ送信を行う場合に、暗号復号装置１２Ｂを介して、送信データがインターネットアクセス網１６へ出力され、一方、インターネットアクセス網１６を介したデータ受信を行う場合に、暗号復号装置１２Ｂを介して、受信データがインターネットアクセス網１６から入力される。

暗号復号装置１２Ａ、１２Ｂは、ＣＰＵ（ＣｅｎｔｒａｌＰｒｏｃｅｓｓｉｎｇＵｎｉｔ）と、ＲＡＭ（ＲａｎｄｏｍＡｃｃｅｓｓＭｅｍｏｒｙ）と、後述する擬似乱数列発生処理ルーチンを実行するためのプログラムを記憶したＲＯＭ（ＲｅａｄＯｎｌｙＭｅｍｏｒｙ）とを備えたコンピュータで構成され、機能的には次に示すように構成されている。図２に示すように、暗号復号装置１２Ａ、１２Ｂは、通信部２０、データ入出力部２２、共通データ設定部２４、擬似乱数列発生部２６、暗号化部２８、及び復号化部３０を備えている。なお、擬似乱数列発生部２６は、行列生成手段、行列作用手段、ビット列変換手段、ビット数判定手段、及び擬似乱数発生列手段の一例である。

通信部２０は、インターネットアクセス網１６を介してデータの送受信を行う。

データ入出力部２２は、ユーザ端末１４Ａ、１４Ｂから出力されたデータが入力されると共に、ユーザ端末１４Ａ、１４Ｂに対してデータを出力する。

共通データ設定部２４は、暗号復号装置１２Ａ、１２Ｂで共通のデータを設定する。具体的には、プライベートデータであるｄ×ｄの行列Ａ、素数ｐ１、ｐ２、初期ベクトルｖ0が共通のデータとして設定される。

擬似乱数列発生部２６は、後述する手法により、プライベートデータであるｄ×ｄの行列Ａ、素数ｐ１、ｐ２、及び初期ベクトルｖ0を用いて、擬似乱数ビット列を発生させる。

暗号化部２８は、擬似乱数列発生部２６によって発生した擬似乱数ビット列を、ワンタイムパッド暗号の鍵として用いることで、データ入出力部２２により入力された暗号化対象データに対して、ストリーム暗号を行う。例えば、図３（Ａ）に示すように、ビット列で表した平文（plain text）と、暗号化の鍵としての擬似乱数ビット列とのＸＯＲを演算することにより、前から１ビット毎に（あるいは1バイト毎に）暗号化する。暗号化部２８により暗号化されたデータは、通信部２０によりデータ送信される。

復号化部３０は、擬似乱数列発生部２６によって発生した擬似乱数ビット列を、ワンタイムパッド暗号の鍵として用いることで、通信部２０により受信された復号化対象データに対して、復号化を行う。例えば、図３（Ｂ）に示すように、ビット列で表した暗号化文（cypher text）と、暗号化の鍵としての擬似乱数ビット列とのＸＯＲを演算することにより、前から１ビット毎に（あるいは1バイト毎に）復号化する。復号化部３０により復号化されたデータは、データ入出力部２２により、データ端末１４Ａ、１４Ｂへ出力される。

次に、本実施の形態における擬似乱数ビット列を発生させる原理について説明する。

まず、共通のプライベートデータとして設定されたｄ×ｄの行列Ａ及び素数ｐ１、ｐ２とを用いて、以下のように、２つの非可換行列Ａ１、Ａ２を生成する。なお、以下では、行列Ａが、２×２の行列である場合を例に説明する。

以下の（１）式に示すように、行列Ａと素数ｐ１とを用いて、行列Ａ１’を計算する。

そして、＜ｇ＞＝｛１，…，ｐ_１−１｝となるジェネレータｇを求める。例えば、ｐ₁＝７のジェネレータは、以下のように、＜３＞＝｛１，…，６｝である。

３^１＝３，３^２＝９ｍｏｄ７＝２，３^３＝２７ｍｏｄ７＝６，３^４＝８１ｍｏｄ７＝４，

３^５＝２４３ｍｏｄ７＝５，・・・

そして、Ａ１”を、以下の（２）式で表わすとすると、ｄｅｔＡ_１”＝ｇになるようにｄ’を変更し、ｄ’を変更したＡ”_１を、非可換行列Ａ１とする。

また、以下の（３）式に示すように、行列Ａと素数ｐ２とを用いて、行列Ａ２’を計算し、上記と同様に、非可換行列Ａ２を生成する。

ここで、非可換行列Ａ１、Ａ２を用いて生成される擬似乱数列の周期の長さＯ（Ａ）は、非可換行列Ａ１、Ａ２の生成に用いる、任意の素数ｐを用いて、以下の（４）式のように書ける。

Ｏ（Ａ）≧ｐ・・・（４）

たとえば、ｐを１０００００ビットの素数とした場合、Ａの周期はそれ以上に長くなる。

また、共通に設定された初期ベクトルｖ_０に対して、生成された非可換行列Ａ_１を用いて変換を行い、ベクトルｖ_１を得る。また、ベクトルｖ_１に対して、非可換行列Ａ_１を用いた変換を繰り返し、ベクトル列Ｖ=｛ｖ_０,ｖ_１,...,ｖ_ｔ｝を得る。ここでｖ_ｉ＝Ａ_１ ^ｉｖ_０である。

そして、得られたベクトル列Ｖから非線形変換により、ビット列Ｗ_１を得る。ベクトル列Ｖからビット列Ｗを得る非線形変換として、Ｖの要素をｖ_ｉ＝（ｖ_ｉ,０,ｖ_ｉ,１，...，ｖ_ｉ，ｎ）とし、ｖ_ｉ，０をバイナリ変換したビット列から、先頭ビットから続く０と次に現われた１とからなるビット列を含む先頭ビット列を取り除くカットオフ処理を行う。ここで、カットオフの後、残ったビット列は高い乱数性を持つことが知られている。

本実施の形態では、カットオフ処理において、Random cut及びFixed cut の2種類のカットオフを使用している。

Random cutでは、上述したように、最初に現れる連続した0と、次に出現する1とからなる先頭ビット列をカットする。また、Fixed cutでは、あらかじめ決めておいたビット数だけカットする。例えば、Fixed cutでカットするビット数が3である場合、Random cutの結果として得られるビット列の先頭3ビットをカットする。

ｖ_ｉの要素すべてにこのカットオフ処理を行い、カットオフ処理後の要素を全て並べたビット列をＷとする。

攻撃者は、すべてのカットオフの可能性を検証しなければ、非可換行列Ａ_１とＡ_２を復元することはできないため、攻撃に対する強さを向上させることができる。

また、本実施の形態では、ベクトルｖiに、非可換行列Ａ１、Ａ２を作用させて、新しいベクトルｖi+1を得る際に、数同士の和演算及び積演算を、以下のように複数の演算子を組み合わせた演算に置き換える。

例えば、a、bを32bitの数とし、記号a<<kを、aをkビットずらす記号とすると、（和演算）a+bを、a+b mod 2³²に置き換える。また、（積演算）a×b を、 a<< (b / 2²⁷) xor bに置き換える。ここで、a<< (b / 2²⁷)は、a を、bを2²⁷で割った商だけずらすことを表わし、xorはビットごとの排他的論理和を表わす。

また、ベクトルｖiに、非可換行列Ａ１、Ａ２を作用させて、新しいベクトルｖi+1を得る際に、更に、行列の作用の方法を以下のように置き換えてもよい。

例えば、ｖ_i＝（ｖ_i ¹, ｖ_i ²,..., ｖ_i ^d）を、行列Ａを初期ベクトルｖ0にi回作用させたものとする（dはＡの次元）と、ｖ_i+1＝（ｖ_i+1 ¹, ｖ_i+1 ²,..., ｖ_i+1 ^d）を得る方法を以下のようにする。

まず、ｖ_i+1 ¹＝（Ａｖ_i）¹とする。これはベクトルＡｖ_iの1番目の要素だけである。また、必要な計算は1番目の要素の計算だけである。2x2行列で書くと、

となるが、和演算と積演算は、上述したように、別の演算で置き換えられている。

そして、ｖ_i+1 ²＝（Ａ（ｖ_i+1 ¹, ｖ_i ²,..., ｖ_i ^d））²とする。これは非可換行列Ａを、ｖ_iの1番目の要素をｖ_i+1 ¹に置き換えたものに作用させ、２番目の要素を取り出したものである。なお、ここで必要な計算は、2番目の要素の計算だけである。

そして、ｖ_i+1 ³＝（Ａ（ｖ_i+1 ¹, ｖ_i+1 ²,..., ｖ_i ^d））²とする。これは上記と同様に、ｖ_iの１番目、２番目の要素を置き換えて、非可換行列Ａを作用させ、3番目の要素を抜き出したものである。

以降、d番目の要素まで同様に行い、ｖ_i+1を得る。

また、暗号化する平文のビット数をｎとすると、ビット列Ｗ1のビット数がnに到達した瞬間、ビット列Ｗ１に対する処理は中断され、ビット列Ｗ１の余った部分は捨てられる。

非可換行列Ａ_２に対しても同様に、ベクトルへの作用及びカットオフ処理を繰り返し行い、ビット列Ｗ_２を生成する。また、ビット列Ｗ２のビット数がnに到達した瞬間、ビット列Ｗ２に対する処理は中断され、ビット列Ｗ２の余った部分は捨てられる。

そして、最終的に得られたビット列Ｗ_１とビット列Ｗ₂とのＸＯＲを計算し、得られたビット列を、擬似乱数ビット列とする。なお、ビット列Ｗ_１とビット列Ｗ₂とのＸＯＲにより得られたビット列に対して、更に非線形変換を行って、その結果を、擬似乱数ビット列としてもよい。

擬似乱数列発生部２６は、上記のように、暗号化対象データのビット数又は復号化対象データのビット数と同じビット数の擬似乱数ビット列を発生させる。

＜暗号化処理システムの動作＞
次に、本実施の形態に係る暗号化処理システム１０の動作について説明する。

まず、ユーザ端末１４Ａから、データをユーザ端末１４Ｂへ送信する場合に、ユーザ端末１４Ａが、送信データを、暗号復号装置１２Ａに出力する。

また、暗号復号装置１２Ａにおいて、図４に示す擬似乱数列発生処理ルーチンが実行される。

まず、ステップ１００において、暗号復号装置１２Ｂと共通に設定された非可換行列Ａ、素数ｐ１、ｐ２を用いて、非可換行列Ａ１、Ａ２を生成する。ステップ１０２では、ベクトルを識別する変数ｉを初期値である０に設定する。また、初期ベクトルｖ0を設定する。

次のステップ１０４では、ベクトルｖiに、非可換行列Ａ１、Ａ２をそれぞれ作用させて、ベクトルｖ_i+1 ¹、ｖ_i+1 ²を計算する。ステップ１０６では、上記ステップ１０４で計算されたベクトルｖ_i+1 ¹、ｖ_i+1 ²の各々を、ビット列に変換すると共に、それぞれのビット列に対して、カットオフ処理を行い、先頭ビット列をカットオフする。そして、ステップ１０８において、上記ステップ１０６で得られたビット列の各々を、ビット列Ｗ１、Ｗ２に対して更に並べるように追加する。

ステップ１１０では、ビット列Ｗ１、Ｗ２の各々のビット数が、送信データ（暗号化対象データ）のビット列のビット数に到達したか否かを判定する。ビット列Ｗ１、Ｗ２の各々のビット数が、ユーザ端末１４Ａから入力された送信データ（暗号化対象データ）のビット列のビット数に到達していない場合には、ステップ１１２において、変数ｉを１インクリメントして、上記ステップ１０４へ戻って、ステップ１０４以降の処理を繰り返す。ここで、ビット列Ｗ１のみについて、ビット数が、送信データのビット列のビット数に到達した場合には、上記ステップ１０４以降の処理において、非可換行列Ａ１を用いた処理は行わない。また、ビット列Ｗ２のみについて、ビット数が、送信データのビット列のビット数に到達した場合には、上記ステップ１０４以降の処理において、非可換行列Ａ２を用いた処理は行わない。

また、上記ステップ１１０において、ビット列Ｗ１、Ｗ２の双方のビット数が、送信データのビット列のビット数に到達したと判定された場合には、ステップ１１４へ進む。

ステップ１１４では、ビット列Ｗ１、Ｗ２のＸＯＲを演算して、擬似乱数ビット列Ｓを生成し、擬似乱数列発生処理ルーチンを終了する。

そして、暗号復号装置１２Ａは、上記の擬似乱数列発生処理ルーチンによって生成された擬似乱数ビット列Ｓと、ユーザ端末１４から入力された送信データのビット列とのＸＯＲを演算することにより、暗号化された送信データを生成する。また、暗号復号装置１２Ａは、暗号化された送信データを、インターネットアクセス網１６を介してユーザ端末１４Ｂへ送信する。

暗号化された送信データは、暗号復号装置１２Ｂによって受信され、暗号復号装置１２Ｂにおいて、上記図４の擬似乱数列発生処理ルーチンが同様に実行され、暗号化された送信データと同じビット数の擬似乱数ビット列Ｓが生成される。

そして、暗号復号装置１２Ｂは、生成された擬似乱数ビット列Ｓと、暗号化された送信データのビット列とのＸＯＲを演算することにより、暗号化された送信データの平文を生成する。また、暗号復号装置１２Ｂは、送信データの平文を、送信先として指定されたユーザ端末Ｂへ出力する。

前記した実施形態の一構成要素にあたる擬似乱数列は本発明を創作する過程で統計テスト（ＮＩＳＴＵ０１テスト）を実施している（非特許文献２参照）。以下、ＮＩＳＴＵ０１テストの結果について簡単に説明するが、本テストは、プログラムソースがクローズされた状態で入出力の状態のみを取得して行っているものである。ここで、ＮＩＳＴとは米国立標準技術研究所であって、ＮＩＳＴＵ０１テストは、ＮＩＳＴが米国の政府機関での使用を認める暗号アルゴリズムおよび実装の要件を課す目的で実施しているテストの一つであり、疑似乱数列の安全性を評価するものである。

非特許文献２：Ｆ．Ｇｉｕｓｅｐｐｅ，“ＢｅｎｃｈｍａｒｋｉｎｇｆｏｒｔｈｅＱＰＣｒｙｐｔｏｇｒａｐｈｉｃＳｕｉｔｅ”，ＤｉｐａｒｔｍｅｎｔｏｄｉＩｎｆｏｒｍａｔｉｃａ，ＳｉｓｔｅｍｉｅＰｒｏｄｕｚｉｏｎｅ，ＵｎｉｖｅｒｓｉｔａｄｉＲｏｍａ “ＴｏｒＶｅｒｇａｔａ”（イタリア語）、２００９

Ｕ０１はＣライブラリで提供されているものを用いた。テストには、ＳｍａｌｌＣｒｕｓｈ，ＢｉｇＣｒａｓｈ，Ｒａｂｂｉｔ，Ａｌｐｈａｂｉｔ，ＦＩＰＳ−１４０−２，ｐｓｅｕｄｏＤＩＥＨＡＲＤが含まれている。ここで、現在広く用いられている擬似乱数列発生アルゴリズムＲＣ４を比較対象とした。

前記した実施形態の一構成要素にあたる擬似乱数列は、全ての統計テストをパスしたが、比較対象であるＲＣ４は、多くのテストをパスできなかった。これにより、実施の形態で説明した擬似乱数列の発生アルゴリズムでは、統計的に安全な擬似乱数列を生成できることが分かった。

続いて、前記した実施形態の一構成要素にあたる暗号化方法（以下、ＱＰ−ＤＹＮとも称する。）についても本発明を創作する過程で実施した実験結果について説明する。

この実験は、暗号化速度を検証することを目的に、ストリーム暗号の暗号化速度の検証を実施している（非特許文献３）。なお、この実験についても、前記したＮＩＳＴＵ０１テストと同様に、プログラムソースがクローズされた状態で入出力の状態のみを取得して行っているものである。

非特許文献３：ＰｅｒｆｏｒｍａｎｃｅＡｎａｌｙｓｉｓｏｆＡｌｇｏｒｉｔｈｍｓａｎｄＳｔａｔｉｓｔｉｃａｌＴｅｓｔｓ，（イタリア語），２０１１

実験の環境は以下の通りである。Ｗｉｎｄｏｗｓ７（登録商標）上のパフォーマンスは、以下の表１に示す。

いくつかのファイル（１０ＭＢ、１００ＭＢ、ｐｄｆファイル、ディスクイメージ（ｕｂｕｎｔｕ−１０．１０−ｄｅｓｋｔｏｐ−ｉ３８６．ｉｓｏ），ｍｐ４ビデオ３．５Ｇ，Ｗｏｒｄドキュメント等）でデータの暗号化の実験を行い、読み書きのプロセスまで含めた１秒あたりの暗号化データ量の計測を行った。

比較対象として、ＡＥＳとＴｗｏＦｉｓｈを用いた。仕様を以下の表２に示す。

各テストデータに対して暗号化における１秒あたりの暗号化データ量を計測し、平均を求めると、図５に示す実験結果が得られた。これより、２５６ビットの鍵長のＡＥＳとＴｗｏＦｉｓｈより、ＱＰ−ＤＹＮ２８８ビットと１１５６ビットのほうが、１秒あたりの暗号化データ量が多いことが分かった。

以上説明したように、本発明の実施の形態に係る検索条件提示システムは、非可換行列Ａ１、Ａ２を作用させる際の和演算及び積演算を、複数種類の演算子を組み合わせた演算方法に置換して、初期ベクトルに、非可換行列Ａ１、Ａ２を繰り返し作用させると共に非線形変換を行って、得られるビット列Ｗ１、Ｗ２のＸＯＲを計算して、擬似乱数ビット列を求め、擬似乱数ビット列を用いて暗号化又は復号化することにより、暗号化対象データ又は復号化対象データのビット数が可変である場合において、暗号化処理又は復号化処理を高速化し、かつ暗号解読強度を強くすることができる。

また、他のストリーム暗号より高速で、計算能力の低い小型デバイス上でも実装が可能である。

また、擬似乱数列発生アルゴリズムにおいて、いくつかの非線形変換を用いることにより、擬似乱数列の統計的ランダム性と長周期を保証することができ、生成された擬似乱数列を用いることにより、安全な使い捨て暗号鍵（One-Time-Padキー）を生成することができる。

また、ストリーミング暗号を実現することができるため、音声・動画などのマルチメディア・ファイルを安全にかつ高速に転送することができる。

なお、本発明は、上述した実施形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。

例えば、ストリーミング暗号以外に、本発明を適用してもよく、自動車のキーレスエントリーなどへ応用してもよい。また、HDD(hard disk drive)の暗号化に応用してもよい。例えば、本実施の形態で説明した暗号化方法により、HDDに保存されるすべてのデータが暗号化され、正当なユーザしか読み出しできないようにしてもよい。また、Cloudサービスのセキュリティに、本発明を応用してもよい。

また、本願明細書中において、プログラムが予めインストールされている実施形態として説明したが、当該プログラムを、コンピュータ読み取り可能な記録媒体に格納して提供することも可能である。

１０暗号化処理システム
１２Ａ、１２Ｂ暗号復号装置
１４Ａ、１４Ｂユーザ端末
１６インターネットアクセス網
２０通信部
２２データ入出力部
２４共通データ設定部
２６擬似乱数列発生部
２８暗号化部
３０復号化部

Claims

復号化装置と共通に設定されたプライベートデータであるｄ×ｄの行列Ａ、及び２つの素数ｐ１、ｐ２に基づいて、２つの非可換行列Ａ１、Ａ２を生成する行列生成手段と、
前記復号化装置と共通に設定されたｄ次元の初期ベクトルｖ₀又は前回求められたｄ次元のベクトルｖ_i-1 ¹に、非可換行列Ａ１を作用させて、ベクトルｖ_i,¹を求めると共に、前記初期ベクトルｖ₀、又は前回求められたｄ次元のベクトルｖ_i-1 ²に、非可換行列Ａ２を作用させて、ベクトルｖ_i ²を求める行列作用手段であって、前記非可換行列Ａ１、Ａ２を作用させる際の和演算及び積演算の少なくとも一方を、予め定められた、複数種類の演算子を組み合わせた演算方法に置換して、非可換行列Ａ１、Ａ２を作用させる行列作用手段と、
前記行列作用手段によって求められたベクトルｖ_i ¹に対して非線形変換を行ってビット列に変換し、前回求められたビット列Ｗ１に結合させると共に、ベクトルｖ_i ²に対して非線形変換を行ってビット列に変換し、前回求められたビット列Ｗ２に結合させるビット列変換手段と、
前記ビット列Ｗ１及び前記ビット列Ｗ２の各々のビット数が、暗号化対象データを表わすビット列のビット数になるまで、前記行列作用手段による作用及び前記ビット列変換手段による変換を繰り返すビット数判定手段と、
前記ビット列Ｗ１及び前記ビット列Ｗ２の排他的論理和を計算して、擬似乱数ビット列を求める擬似乱数列発生手段と、
前記擬似乱数列発生手段によって求められた擬似乱数ビット列と、前記暗号化対象データを表わすビット列との排他的論理和を計算することにより、前記暗号化対象データを暗号化する暗号化手段と、
を含む暗号化装置。
前記行列作用手段は、
前記初期ベクトルｖ₀、又は前回求められたベクトルｖ_i-1 ¹に、非可換行列Ａ１を作用させて、前記ベクトルｖ_i ¹を求める際に、ベクトルｖ_i ¹の要素毎に、既に求められたベクトルｖ_i ¹の要素に置き換えた初期ベクトルｖ₀、又は前記ベクトルｖ_i-1 ¹に、非可換行列Ａ１を作用させて、ベクトルｖ_i ¹の前記要素を計算し、
前記初期ベクトルｖ₀、又は前回求められたベクトルｖ_i-1 ²に、非可換行列Ａ２を作用させて、前記ベクトルｖ_i ²を求める際に、ベクトルｖ_i ²の要素毎に、既に求められたベクトルｖ_i ²の要素に置き換えた初期ベクトルｖ₀、又は前記ベクトルｖ_i-1 ²に、非可換行列Ａ２を作用させて、ベクトルｖ_i ²の前記要素を計算する請求項１記載の暗号化装置。
前記ビット列変換手段は、
前記非線形変換として、前記行列作用手段によって求められたベクトルｖ_i,¹をビット列に変換し、変換されたビット列に対して、所定ビット数の先頭ビット列をカットするカットオフ処理を行い、前回求められたビット列Ｗ１に結合させると共に、ベクトルｖ_i,²をビット列に変換し、変換されたビット列に対して、前記カットオフ処理を行い、前回求められたビット列Ｗ２に結合させる請求項１又は２記載の暗号化装置。
前記ビット列変換手段は、前記カットオフ処理として、前記変換されたビット列に対して、先頭から連続する０と、先頭から最初に出現する１とからなる先頭ビット列をカットすると共に、前記先頭ビット列がカットされた前記ビット列から、予め定められたビット数の先頭ビット列をカットする処理を行う請求項３記載の暗号化装置。
暗号化装置と共通に設定されたプライベートデータであるｄ×ｄの行列Ａ、及び２つの素数ｐ１、ｐ２に基づいて、２つの非可換行列Ａ１、Ａ２を生成する行列生成手段と、
前記暗号化装置と共通に設定されたｄ次元の初期ベクトルｖ₀又は前回求められたｄ次元のベクトルｖ_i-1 ¹に、非可換行列Ａ１を作用させて、ベクトルｖ_i ¹を求めると共に、前記初期ベクトルｖ₀、又は前回求められたｄ次元のベクトルｖ_i-1 ²に、非可換行列Ａ２を作用させて、ベクトルｖ_i,²を求める行列作用手段であって、前記非可換行列Ａ１、Ａ２を作用させる際の和演算及び積演算の少なくとも一方を、予め定められた、複数種類の演算子を組み合わせた演算方法に置換して、非可換行列Ａ１、Ａ２を作用させる行列作用手段と、
前記行列作用手段によって求められたベクトルｖ_i ¹に対して非線形変換を行ってビット列に変換し、前回求められたビット列Ｗ１に結合させると共に、ベクトルｖ_i ²に対して非線形変換を行ってビット列に変換し、前回求められたビット列Ｗ２に結合させるビット列変換手段と、
前記ビット列Ｗ１及び前記ビット列Ｗ２の各々のビット数が、復号化対象データを表わすビット列のビット数になるまで、前記行列作用手段による作用及び前記ビット列変換手段による変換を繰り返すビット数判定手段と、
前記ビット列Ｗ１及び前記ビット列Ｗ２の排他的論理和を計算して、擬似乱数ビット列を求める擬似乱数列発生手段と、
前記擬似乱数列発生手段によって求められた擬似乱数ビット列と、前記復号化対象データを表わすビット列との排他的論理和を計算することにより、前記復号化対象データを復号化する復号化手段と、
を含む復号化装置。
コンピュータを、
復号化装置と共通に設定されたプライベートデータであるｄ×ｄの行列Ａ、及び２つの素数ｐ１、ｐ２に基づいて、２つの非可換行列Ａ１、Ａ２を生成する行列生成手段、
前記復号化装置と共通に設定されたｄ次元の初期ベクトルｖ₀又は前回求められたｄ次元のベクトルｖ_i-1 ¹に、非可換行列Ａ１を作用させて、ベクトルｖ_i,¹を求めると共に、前記初期ベクトルｖ₀、又は前回求められたｄ次元のベクトルｖ_i-1 ²に、非可換行列Ａ２を作用させて、ベクトルｖ_i ²を求める行列作用手段であって、前記非可換行列Ａ１、Ａ２を作用させる際の和演算及び積演算の少なくとも一方を、予め定められた、複数種類の演算子を組み合わせた演算方法に置換して、非可換行列Ａ１、Ａ２を作用させる行列作用手段、
前記行列作用手段によって求められたベクトルｖ_i ¹に対して非線形変換を行ってビット列に変換し、前回求められたビット列Ｗ１に結合させると共に、ベクトルｖ_i ²に対して非線形変換を行ってビット列に変換し、前回求められたビット列Ｗ２に結合させるビット列変換手段、
前記ビット列Ｗ１及び前記ビット列Ｗ２の各々のビット数が、暗号化対象データを表わすビット列のビット数になるまで、前記行列作用手段による作用及び前記ビット列変換手段による変換を繰り返すビット数判定手段、
前記ビット列Ｗ１及び前記ビット列Ｗ２の排他的論理和を計算して、擬似乱数ビット列を求める擬似乱数列発生手段、及び
前記擬似乱数列発生手段によって求められた擬似乱数ビット列と、前記暗号化対象データを表わすビット列との排他的論理和を計算することにより、前記暗号化対象データを暗号化する暗号化手段
として機能させるためのプログラム。
コンピュータを、
暗号化装置と共通に設定されたプライベートデータであるｄ×ｄの行列Ａ、及び２つの素数ｐ１、ｐ２に基づいて、２つの非可換行列Ａ１、Ａ２を生成する行列生成手段、
前記暗号化装置と共通に設定されたｄ次元の初期ベクトルｖ₀又は前回求められたｄ次元のベクトルｖ_i-1 ¹に、非可換行列Ａ１を作用させて、ベクトルｖ_i ¹を求めると共に、前記初期ベクトルｖ₀、又は前回求められたｄ次元のベクトルｖ_i-1 ²に、非可換行列Ａ２を作用させて、ベクトルｖ_i ²を求める行列作用手段であって、前記非可換行列Ａ１、Ａ２を作用させる際の和演算及び積演算の少なくとも一方を、予め定められた、複数種類の演算子を組み合わせた演算方法に置換して、非可換行列Ａ１、Ａ２を作用させる行列作用手段、
前記行列作用手段によって求められたベクトルｖ_i ¹に対して非線形変換を行ってビット列に変換し、前回求められたビット列Ｗ１に結合させると共に、ベクトルｖ_i ²に対して非線形変換を行ってビット列に変換し、前回求められたビット列Ｗ２に結合させるビット列変換手段、
前記ビット列Ｗ１及び前記ビット列Ｗ２の各々のビット数が、復号化対象データを表わすビット列のビット数になるまで、前記行列作用手段による作用及び前記ビット列変換手段による変換を繰り返すビット数判定手段、
前記ビット列Ｗ１及び前記ビット列Ｗ２の排他的論理和を計算して、擬似乱数ビット列を求める擬似乱数列発生手段、及び
前記擬似乱数列発生手段によって求められた擬似乱数ビット列と、前記復号化対象データを表わすビット列との排他的論理和を計算することにより、前記復号化対象データを復号化する復号化手段
として機能させるためのプログラム。