(57)【要約】【課題】高速に、安全な共有秘密鍵を生成することができるようにする。【解決手段】公開データ取得部２２によって、素数ｐ、自然数ｄ、行列Ｑ、及び行列Ｓを含む公開データを取得し、秘密鍵生成部２４によって、自然数ｎA、ｋAを含む秘密鍵を生成する。非可換行列生成部２６によって、行列ＭA（ＭA＝Ｓ-kAＱnAＳkA）を計算し、通信相手へ送信し、通信相手から行列ＭB（ＭB＝Ｓ-kBＱnBＳkB）を取得する。共有秘密鍵算出部２８によって、行列ＭAB（ＭAB＝Ｓ-kAＭBnAＳkA）を共有秘密鍵として算出する。【選択図】図２
2014017556.tif 000002
【特許請求の範囲】
【請求項１】
素数ｐ、自然数ｄ、行列式の値が１ではないｄ×ｄの行列Ｑ（ｍｏｄ  ｐ）、及び逆行列が存在するｄ×ｄの行列Ｓ（ｍｏｄ  ｐ）を含む公開データを設定する公開データ設定手段と、
自然数ｎA（ｍｏｄ  ｐ）、ｋA（ｍｏｄ  ｐ）を含む秘密鍵を生成する秘密鍵生成手段と、
前記秘密鍵を用いて、以下の（１）式に従って、ｄ×ｄの行列ＭA（ｍｏｄ  ｐ）を計算し、通信相手へ送信する行列計算手段と、
前記通信相手の秘密鍵に含まれる自然数ｎB（ｍｏｄ  ｐ）、ｋB（ｍｏｄ  ｐ）を用いて以下の（２）式に従って計算される、ｄ×ｄの行列ＭB（ｍｏｄ  ｐ）を取得する行列取得手段と、
前記行列取得手段によって取得された行列ＭBを用いて、以下の（３）式に従ってｄ×ｄの行列ＭAB（ｍｏｄ  ｐ）を共有秘密鍵として算出する共有秘密鍵算出手段と、
を含む共有秘密鍵生成装置。
ＭA＝Ｓ-kAＱnAＳkA      ・・・（１）
ＭB＝Ｓ-kBＱnBＳkB      ・・・（２）
ＭAB＝Ｓ-kAＭBnAＳkA      ・・・（３）
【請求項２】
前記秘密鍵生成手段は、前記通信相手との通信毎に、自然数ｎA（ｍｏｄ  ｐ）、ｋA（ｍｏｄ  ｐ）を含む秘密鍵を生成して更新する請求項１記載の共有秘密鍵生成装置。
【請求項３】
復号化装置と共通に設定された、請求項１又は２の共有秘密鍵生成装置によって生成された共有秘密鍵ＭAB、及び２つの素数ｐ１、ｐ２に基づいて、２つの非可換行列Ａ１、Ａ２を生成する行列生成手段と、
前記復号化装置と共通に設定されたｄ次元の初期ベクトルｖ0又は前回求められたｄ次元のベクトルｖi-11に、非可換行列Ａ１を作用させて、ベクトルｖi1を求めると共に、前記初期ベクトルｖ0、又は前回求められたｄ次元のベクトルｖi-12に、非可換行列Ａ２を作用させて、ベクトルｖi2を求める行列作用手段であって、前記非可換行列Ａ１、Ａ２を作用させる際の和演算及び積演算の少なくとも一方を、予め定められた、複数種類の演算子を組み合わせた演算方法に置換して、非可換行列Ａ１、Ａ２を作用させる行列作用手段と、
前記行列作用手段によって求められたベクトルｖi1に対して非線形変換を行ってビット列に変換し、前回求められたビット列Ｗ１に結合させると共に、ベクトルｖi2に対して非線形変換を行ってビット列に変換し、前回求められたビット列Ｗ２に結合させるビット列変換手段と、
前記ビット列Ｗ１及び前記ビット列Ｗ２の各々のビット数が、暗号化対象データを表わすビット列のビット数になるまで、前記行列作用手段による作用及び前記ビット列変換手段による変換を繰り返すビット数判定手段と、
前記ビット列Ｗ１及び前記ビット列Ｗ２の排他的論理和を計算して、擬似乱数ビット列を求める擬似乱数列発生手段と、
前記擬似乱数列発生手段によって求められた擬似乱数ビット列と、前記暗号化対象データを表わすビット列との排他的論理和を計算することにより、前記暗号化対象データを暗号化する暗号化手段と、
を含む暗号化装置。
【請求項４】
暗号化装置と共通に設定された、請求項１又は２の共有秘密鍵生成装置によって生成された共有秘密鍵ＭAB、及び２つの素数ｐ１、ｐ２に基づいて、２つの非可換行列Ａ１、Ａ２を生成する行列生成手段と、
前記暗号化装置と共通に設定されたｄ次元の初期ベクトルｖ0又は前回求められたｄ次元のベクトルｖi-11に、非可換行列Ａ１を作用させて、ベクトルｖi1を求めると共に、前記初期ベクトルｖ0、又は前回求められたｄ次元のベクトルｖi-12に、非可換行列Ａ２を作用させて、ベクトルｖi2を求める行列作用手段であって、前記非可換行列Ａ１、Ａ２を作用させる際の和演算及び積演算の少なくとも一方を、予め定められた、複数種類の演算子を組み合わせた演算方法に置換して、非可換行列Ａ１、Ａ２を作用させる行列作用手段と、
前記行列作用手段によって求められたベクトルｖi1に対して非線形変換を行ってビット列に変換し、前回求められたビット列Ｗ１に結合させると共に、ベクトルｖi2に対して非線形変換を行ってビット列に変換し、前回求められたビット列Ｗ２に結合させるビット列変換手段と、
前記ビット列Ｗ１及び前記ビット列Ｗ２の各々のビット数が、復号化対象データを表わすビット列のビット数になるまで、前記行列作用手段による作用及び前記ビット列変換手段による変換を繰り返すビット数判定手段と、
前記ビット列Ｗ１及び前記ビット列Ｗ２の排他的論理和を計算して、擬似乱数ビット列を求める擬似乱数列発生手段と、
前記擬似乱数列発生手段によって求められた擬似乱数ビット列と、前記復号化対象データを表わすビット列との排他的論理和を計算することにより、前記復号化対象データを復号化する復号化手段と、
を含む復号化装置。
【請求項５】
コンピュータを、
素数ｐ、自然数ｄ、行列式の値が１ではないｄ×ｄの行列Ｑ（ｍｏｄ  ｐ）、及び逆行列が存在するｄ×ｄの行列Ｓ（ｍｏｄ  ｐ）を含む公開データを設定する公開データ設定手段、
自然数ｎA（ｍｏｄ  ｐ）、ｋA（ｍｏｄ  ｐ）を含む秘密鍵を生成する秘密鍵生成手段、
前記秘密鍵を用いて、以下の（４）式に従って、ｄ×ｄの行列ＭA（ｍｏｄ  ｐ）を計算し、通信相手へ送信する行列計算手段、
前記通信相手の秘密鍵に含まれる自然数ｎB（ｍｏｄ  ｐ）、ｋB（ｍｏｄ  ｐ）を用いて以下の（５）式に従って計算される、ｄ×ｄの行列ＭB（ｍｏｄ  ｐ）を取得する行列取得手段、及び
前記行列取得手段によって取得された行列ＭBを用いて、以下の（６）式に従ってｄ×ｄの行列ＭAB（ｍｏｄ  ｐ）を共有秘密鍵として算出する共有秘密鍵算出手段
として機能させるためのプログラム。
ＭA＝Ｓ-kAＱnAＳkA      ・・・（４）
ＭB＝Ｓ-kBＱnBＳkB      ・・・（５）
ＭAB＝Ｓ-kAＭBnAＳkA      ・・・（６）
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、共有秘密鍵生成装置、暗号化装置、復号化装置、及びプログラムに関する。
【背景技術】
【０００２】
従来より、メッセージの公開型且つ非可換性の符号化方法及び暗号化方法が知られている（特許文献１）。また、有限非可換群を用いた公開鍵暗号システムや、非可換体である環Ｒを用いた公開鍵暗号システムが知られている（特許文献２、３）。
【０００３】
また、公開鍵暗号方式によるネットワーク上での相互認証および公開鍵の相互交換システムや、制御ベクトルに基づく公開鍵暗号システムの鍵管理が知られている（特許文献４、５）。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開2001-202010号公報
【特許文献２】特表2004-534971号公報
【特許文献３】特表2000-516733号公報
【特許文献４】特開2006-262425号公報
【特許文献５】特開平5-216409号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
本発明は、高速に、安全な共有秘密鍵を生成することができる共有秘密鍵生成装置、暗号化装置、復号化装置、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
上記の目的を達成するために本発明に係る共有秘密鍵生成装置は、素数ｐ、自然数ｄ、行列式の値が１ではないｄ×ｄの行列Ｑ（ｍｏｄ  ｐ）、及び逆行列が存在するｄ×ｄの行列Ｓ（ｍｏｄ  ｐ）を含む公開データを設定する公開データ設定手段と、自然数ｎA（ｍｏｄ  ｐ）、ｋA（ｍｏｄ  ｐ）を含む秘密鍵を生成する秘密鍵生成手段と、前記秘密鍵を用いて、以下の（Ｉ）式に従って、ｄ×ｄの行列ＭA（ｍｏｄ  ｐ）を計算し、通信相手へ送信する行列計算手段と、前記通信相手の秘密鍵に含まれる自然数ｎB（ｍｏｄ  ｐ）、ｋB（ｍｏｄ  ｐ）を用いて以下の（ＩＩ）式に従って計算される、ｄ×ｄの行列ＭB（ｍｏｄ  ｐ）を取得する行列取得手段と、前記行列取得手段によって取得された行列ＭBを用いて、以下の（ＩＩＩ）式に従ってｄ×ｄの行列ＭAB（ｍｏｄ  ｐ）を共有秘密鍵として算出する共有秘密鍵算出手段と、を含んで構成されている。
【０００７】
ＭA＝Ｓ-kAＱnAＳkA      ・・・（Ｉ）
ＭB＝Ｓ-kBＱnBＳkB      ・・・（ＩＩ）
ＭAB＝Ｓ-kAＭBnAＳkA      ・・・（ＩＩＩ）
【０００８】
本発明に係るプログラムは、コンピュータを、素数ｐ、自然数ｄ、行列式の値が１ではないｄ×ｄの行列Ｑ（ｍｏｄ  ｐ）、及び逆行列が存在するｄ×ｄの行列Ｓ（ｍｏｄ  ｐ）を含む公開データを設定する公開データ設定手段、自然数ｎA（ｍｏｄ  ｐ）、ｋA（ｍｏｄ  ｐ）を含む秘密鍵を生成する秘密鍵生成手段、前記秘密鍵を用いて、以下の（ＩＶ）式に従って、ｄ×ｄの行列ＭA（ｍｏｄ  ｐ）を計算し、通信相手へ送信する行列計算手段、前記通信相手の秘密鍵に含まれる自然数ｎB（ｍｏｄ  ｐ）、ｋB（ｍｏｄ  ｐ）を用いて以下の（Ｖ）式に従って計算される、ｄ×ｄの行列ＭB（ｍｏｄ  ｐ）を取得する行列取得手段、及び前記行列取得手段によって取得された行列ＭBを用いて、以下の（ＶＩ）式に従ってｄ×ｄの行列ＭAB（ｍｏｄ  ｐ）を共有秘密鍵として算出する共有秘密鍵算出手段として機能させるためのプログラムである。
【０００９】
ＭA＝Ｓ-kAＱnAＳkA      ・・・（ＩＶ）
ＭB＝Ｓ-kBＱnBＳkB      ・・・（Ｖ）
ＭAB＝Ｓ-kAＭBnAＳkA      ・・・（ＶＩ）
【００１０】
このように、公開データと秘密鍵を用いて計算した行列を、通信相手と交換し、通信相手から得られた行列を用いて、共有秘密鍵を算出することにより、高速に、安全な共有秘密鍵を生成することができる。
【００１１】
本発明に係る秘密鍵生成手段は、前記通信相手との通信毎に、自然数ｎA（ｍｏｄ  ｐ）、ｋA（ｍｏｄ  ｐ）を含む秘密鍵を生成して更新するようにすることができる。これによって、より安全な共有秘密鍵を生成することができる。
【００１２】
また、本発明に係る暗号化装置は、復号化装置と共通に設定された、上記の共有秘密鍵生成装置によって生成された共有秘密鍵ＭAB、及び２つの素数ｐ１、ｐ２に基づいて、２つの非可換行列Ａ１、Ａ２を生成する行列生成手段と、前記復号化装置と共通に設定されたｄ次元の初期ベクトルｖ0又は前回求められたｄ次元のベクトルｖi-11に、非可換行列Ａ１を作用させて、ベクトルｖi1を求めると共に、前記初期ベクトルｖ0、又は前回求められたｄ次元のベクトルｖi-12に、非可換行列Ａ２を作用させて、ベクトルｖi2を求める行列作用手段であって、前記非可換行列Ａ１、Ａ２を作用させる際の和演算及び積演算の少なくとも一方を、予め定められた、複数種類の演算子を組み合わせた演算方法に置換して、非可換行列Ａ１、Ａ２を作用させる行列作用手段と、前記行列作用手段によって求められたベクトルｖi1に対して非線形変換を行ってビット列に変換し、前回求められたビット列Ｗ１に結合させると共に、ベクトルｖi2に対して非線形変換を行ってビット列に変換し、前回求められたビット列Ｗ２に結合させるビット列変換手段と、前記ビット列Ｗ１及び前記ビット列Ｗ２の各々のビット数が、暗号化対象データを表わすビット列のビット数になるまで、前記行列作用手段による作用及び前記ビット列変換手段による変換を繰り返すビット数判定手段と、前記ビット列Ｗ１及び前記ビット列Ｗ２の排他的論理和を計算して、擬似乱数ビット列を求める擬似乱数列発生手段と、前記擬似乱数列発生手段によって求められた擬似乱数ビット列と、前記暗号化対象データを表わすビット列との排他的論理和を計算することにより、前記暗号化対象データを暗号化する暗号化手段と、を含んで構成されている。
【００１３】
このように、非可換行列Ａ１、Ａ２を作用させる際の和演算及び積演算の少なくとも一方を、複数種類の演算子を組み合わせた演算方法に置換して、ベクトルに、非可換行列Ａ１、Ａ２を繰り返し作用させると共に非線形変換を行って、得られるビット列Ｗ１、Ｗ２の排他的論理和を計算して、擬似乱数ビット列を求め、擬似乱数ビット列を用いて暗号化することにより、暗号化対象データのビット数が可変である場合において、暗号化処理を高速化し、かつ暗号解読強度を強くすることができる。
【００１４】
上記の暗号化装置に係る行列作用手段は、前記初期ベクトルｖ0、又は前回求められたベクトルｖi-11に、非可換行列Ａ１を作用させて、前記ベクトルｖi1を求める際に、ベクトルｖi1の要素毎に、既に求められたベクトルｖi1の要素に置き換えた初期ベクトルｖ0、又は前記ベクトルｖi-11に、非可換行列Ａ１を作用させて、ベクトルｖi1の前記要素を計算し、前記初期ベクトルｖ0、又は前回求められたベクトルｖi-12に、非可換行列Ａ２を作用させて、前記ベクトルｖi2を求める際に、ベクトルｖi2の要素毎に、既に求められたベクトルｖi2の要素に置き換えた初期ベクトルｖ0、又は前記ベクトルｖi-12に、非可換行列Ａ２を作用させて、ベクトルｖi2の前記要素を計算するようにすることができる。これによって、暗号解読強度をより強くすることができる。
【００１５】
上記の暗号化装置に係るビット列変換手段は、前記非線形変換として、前記行列作用手段によって求められたベクトルｖi1をビット列に変換し、変換されたビット列に対して、所定ビット数の先頭ビット列をカットするカットオフ処理を行い、前回求められたビット列Ｗ１に結合させると共に、ベクトルｖi2をビット列に変換し、変換されたビット列に対して、前記カットオフ処理を行い、前回求められたビット列Ｗ２に結合させるようにすることができる。これによって、暗号解読強度をより強くすることができる。
【００１６】
また、上記のビット列変換手段は、前記カットオフ処理として、前記変換されたビット列に対して、先頭から連続する０と、先頭から最初に出現する１とからなる先頭ビット列をカットすると共に、前記先頭ビット列がカットされた前記ビット列から、予め定められたビット数の先頭ビット列をカットする処理を行うようにすることができる。これによって、暗号解読強度をより強くすることができる。
【００１７】
本発明に係る復号化装置は、暗号化装置と共通に設定された、上記の共有秘密鍵生成装置によって生成された共有秘密鍵ＭAB、及び２つの素数ｐ１、ｐ２とに基づいて、２つの非可換行列Ａ１、Ａ２を生成する行列生成手段と、前記暗号化装置と共通に設定されたｄ次元の初期ベクトルｖ0又は前回求められたｄ次元のベクトルｖi-11に、非可換行列Ａ１を作用させて、ベクトルｖi1を求めると共に、前記初期ベクトルｖ0、又は前回求められたｄ次元のベクトルｖi-12に、非可換行列Ａ２を作用させて、ベクトルｖi2を求める行列作用手段であって、前記非可換行列Ａ１、Ａ２を作用させる際の和演算及び積演算の少なくとも一方を、予め定められた、複数種類の演算子を組み合わせた演算方法に置換して、非可換行列Ａ１、Ａ２を作用させる行列作用手段と、前記行列作用手段によって求められたベクトルｖi1に対して非線形変換を行ってビット列に変換し、前回求められたビット列Ｗ１に結合させると共に、ベクトルｖi2に対して非線形変換を行ってビット列に変換し、前回求められたビット列Ｗ２に結合させるビット列変換手段と、前記ビット列Ｗ１及び前記ビット列Ｗ２の各々のビット数が、復号化対象データを表わすビット列のビット数になるまで、前記行列作用手段による作用及び前記ビット列変換手段による変換を繰り返すビット数判定手段と、前記ビット列Ｗ１及び前記ビット列Ｗ２の排他的論理和を計算して、擬似乱数ビット列を求める擬似乱数列発生手段と、前記擬似乱数列発生手段によって求められた擬似乱数ビット列と、前記復号化対象データを表わすビット列との排他的論理和を計算することにより、前記復号化対象データを復号化する復号化手段と、を含んで構成されている。
【発明の効果】
【００１８】
本発明に係る共有秘密鍵生成装置及びプログラムによれば、公開データと秘密鍵を用いて計算した行列を、通信相手と交換し、通信相手から得られた行列を用いて、共有秘密鍵を算出することにより、高速に、安全な共有秘密鍵を生成することができる。
【００１９】
本発明に係る暗号化装置及び復号化装置によれば、非可換行列Ａ１、Ａ２を作用させる際の和演算及び積演算の少なくとも一方を、複数種類の演算子を組み合わせた演算方法に置換して、ベクトルに、非可換行列Ａ１、Ａ２を繰り返し作用させると共に非線形変換を行って、得られるビット列Ｗ１、Ｗ２の排他的論理和を計算して、擬似乱数ビット列を求め、擬似乱数ビット列を用いて暗号化又は復号化することにより、暗号化対象データ又は復号化対象データのビット数が可変である場合において、暗号化処理又は復号化処理を高速化し、かつ暗号解読強度を強くすることができる。
【図面の簡単な説明】
【００２０】
【図１】本発明の実施の形態に係る暗号化処理システムの構成を示す概略図である。
【図２】本発明の実施の形態に係る暗号復号装置の構成を示す概略図である。
【図３】共有秘密鍵を算出する方法を説明するための図である。
【図４】（Ａ）暗号化方法を説明するための図、及び（Ｂ）復号化方法を説明するための図である。
【図５】本発明の実施の形態に係る暗号復号装置における共有秘密鍵算出処理ルーチンの内容を示すフローチャートである。
【図６】本発明の実施の形態に係る暗号復号装置における擬似乱数列発生処理ルーチンの内容を示すフローチャートである。
【図７】コンピュータ上での実験結果を示すグラフである。
【図８】モバイル端末上での実験結果を示すグラフである。
【発明を実施するための形態】
【００２１】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００２２】
＜システム構成＞
図１に示すように、本発明の実施の形態に係る暗号化処理システム１０は、暗号復号装置１２Ａ、１２Ｂと、複数のユーザ端末１４Ａと、複数のユーザ端末１４Ｂと、インターネットアクセス網１６とを備えている。なお、暗号復号装置１２Ａ、１２Ｂは、暗号化装置、復号化装置の一例である。
【００２３】
複数のユーザ端末１４Ａは、暗号復号装置１２Ａと接続されており、暗号復号装置１２Ａは、インターネットアクセス網１６に接続されている。また、複数のユーザ端末１４Ｂは、暗号復号装置１２Ｂと接続されており、暗号復号装置１２Ｂは、インターネットアクセス網１６に接続されている。暗号復号装置１２Ａ、１２Ｂは、インターネットアクセス網１６を介して相互に接続されている。
【００２４】
ユーザ端末１４Ａは、インターネットアクセス網１６を介したデータ送信を行う場合に、暗号復号装置１２Ａを介して、送信データがインターネットアクセス網１６に出力され、一方、インターネットアクセス網１６を介したデータ受信を行う場合に、暗号復号装置１２Ａを介して、受信データがインターネットアクセス網１６から入力される。
【００２５】
また、ユーザ端末１４Ｂは、インターネットアクセス網１６を介したデータ送信を行う場合に、暗号復号装置１２Ｂを介して、送信データがインターネットアクセス網１６へ出力され、一方、インターネットアクセス網１６を介したデータ受信を行う場合に、暗号復号装置１２Ｂを介して、受信データがインターネットアクセス網１６から入力される。
【００２６】
暗号復号装置１２Ａ、１２Ｂは、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）と、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）と、後述する共有秘密鍵生成処理ルーチン及び擬似乱数列発生処理ルーチンを実行するためのプログラムを記憶したＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）とを備えたコンピュータで構成され、機能的には次に示すように構成されている。図２に示すように、暗号復号装置１２Ａ、１２Ｂは、通信部２０、公開データ取得部２２、秘密鍵生成部２４、非可換行列生成部２６、共有秘密鍵算出部２８、データ入出力部３２、共通データ設定部３４、擬似乱数列発生部３６、暗号化部３８、及び復号化部４０を備えている。なお、非可換行列生成部２６は、行列計算手段の一例であり、共有秘密鍵算出部２８は、行列取得手段及び共有秘密鍵算出手段の一例である。また、擬似乱数列発生部３６は、行列生成手段、行列作用手段、ビット列変換手段、ビット数判定手段、及び擬似乱数発生列手段の一例である。
【００２７】
通信部２０は、インターネットアクセス網１６を介してデータの送受信を行う。
【００２８】
データ入出力部３２は、ユーザ端末１４Ａ、１４Ｂから出力されたデータが入力されると共に、ユーザ端末１４Ａ、１４Ｂに対してデータを出力する。
【００２９】
暗号復号装置１２Ａ、１２Ｂの公開データ取得部２２は、通信部２０を介して、通信相手との通信で用いる公開データとして、素数ｐ、自然数ｄ、ｄ×ｄの行列Ｑ（ｍｏｄ  ｐ）、及び逆行列が存在するｄ×ｄの行列Ｓ（ｍｏｄ  ｐ）を取得する。ただし、ｄｅｔ  Ｑ≠１であり、（ｍｏｄ  ｐ）は、変数あるいは行列の要素の値が、素数ｐの法であることを示す。
【００３０】
暗号復号装置１２Ａの秘密鍵生成部２４は、自然数ｎA（ｍｏｄ  ｐ）、ｋA（ｍｏｄ  ｐ）からなる秘密鍵を生成する。
【００３１】
暗号復号装置１２Ｂの秘密鍵生成部２４は、自然数ｎB（ｍｏｄ  ｐ）、ｋB（ｍｏｄ  ｐ）からなる秘密鍵を生成する。
【００３２】
秘密鍵生成部２４は、通信を行う毎に、新たな秘密鍵を生成し、秘密鍵を更新する。
【００３３】
暗号復号装置１２Ａの非可換行列生成部２６は、秘密鍵ｎA、ｋAを用いて、以下の（１）式に従って、ｄ×ｄの行列ＭA（ｍｏｄ  ｐ）を計算し、通信部２０を介して、通信相手である暗号復号装置１２Ｂへ、行列ＭAを送信する。
【００３４】
ＭA＝Ｓ-kAＱnAＳkA      ・・・（１）
【００３５】
暗号復号装置１２Ｂの非可換行列生成部２６は、秘密鍵ｎB、ｋBを用いて、以下の（２）式に従って、ｄ×ｄの行列ＭB（ｍｏｄ  ｐ）を計算し、通信部２０を介して、通信相手である暗号復号装置１２Ａへ、行列ＭBを送信する。
【００３６】
ＭB＝Ｓ-kBＱnBＳkB      ・・・（２）
【００３７】
暗号復号装置１２Ａの共有秘密鍵算出部２８は、通信部２０によって受信した行列ＭBを取得し、取得された行列ＭBを用いて、以下の（３）式に従ってｄ×ｄの行列ＭAB（ｍｏｄ  ｐ）を算出する。
【００３８】
ＭAB＝Ｓ-kAＭBnAＳkA      ・・・（３）
【００３９】
暗号復号装置１２Ｂの共有秘密鍵算出部２８は、通信部２０によって受信した行列ＭAを取得し、取得された行列ＭAを用いて、以下の（４）式に従ってｄ×ｄの行列ＭBA（ｍｏｄ  ｐ）を算出する。
【００４０】
ＭBA＝Ｓ-kBＭAnBＳkB      ・・・（４）
【００４１】
ここで、図３に示すように、上記（３）式は、以下のように、（５）式に変換される。
【００４２】
ＭＡＢ＝Ｓ−ＫＡＭＢｎＡＳＫＡ
ＭＡＢ＝Ｓ−ＫＡ（Ｓ−ＫＢＱｎBＳＫＢ）ｎＡＳＫＡ
ＭＡＢ＝Ｓ−ＫＡＳ−ＫＢ（ＱｎB）ｎＡＳＫＢＳＫＡ
ＭＡＢ＝Ｓ−（ＫＡ＋ＫＢ）ＱｎＢｎＡＳ（ＫＡ＋ＫＢ）      ・・・（５）
【００４３】
また、上記（４）式は、以下のように、（６）式に変換される。
【００４４】
Ｓ−ＫＢＭＡｎＢＳＫＢ＝ＭＢＡ
Ｓ−ＫＢ（Ｓ−ＫＡＱｎＡＳＫＡ）ｎＢＳＫＢ＝ＭＢＡ
Ｓ−ＫＢＳ−ＫＡ（ＱｎＡ）ｎＢＳＫＡＳＫＢ＝ＭＢＡ
Ｓ−（ＫＡ＋ＫＢ）ＱｎＡｎＢＳ（ＫＡ＋ＫＢ）＝ＭＢＡ      ・・・（６）
【００４５】
上記（５）式、（６）式により、以下の（７）式が得られ、ＭABとＭBAとが等しいことが証明される。
【００４６】
ＭＡＢ＝Ｓ−（ＫＡ＋ＫＢ）ＱｎＡｎＢＳ（ＫＡ＋ＫＢ）＝Ｓ−（ＫＢ＋ＫＡ）ＱｎＡｎＢＳ（ＫＢ＋ＫＡ）＝ＭＢＡ
・・・（７）
【００４７】
そこで、暗号復号装置１２Ａ、１２Ｂの共有秘密鍵算出部２８は、算出した行列ＭAB、ＭBAを、共有秘密鍵として、共通データ設定部３４へ出力する。
【００４８】
共通データ設定部３４は、暗号復号装置１２Ａ、１２Ｂで共通のデータを設定する。具体的には、共有秘密鍵である行列ＭAB（ＭBA）、プライベートデータである素数ｐ１、ｐ２、及び初期ベクトルｖ0が共通のデータとして設定される。
【００４９】
擬似乱数列発生部３６は、後述する手法により、共有秘密鍵である行列ＭAB（ＭBA）、プライベートデータである素数ｐ１、ｐ２、及び初期ベクトルｖ0を用いて、擬似乱数ビット列を発生させる。
【００５０】
暗号化部３８は、擬似乱数列発生部３６によって発生した擬似乱数ビット列を、ワンタイムパッド暗号の鍵として用いることで、データ入出力部３２により入力された暗号化対象データに対して、ストリーム暗号化を行う。例えば、図４（Ａ）に示すように、ビット列で表した平文（plain text）と、暗号化の鍵としての擬似乱数ビット列とのＸＯＲを演算することにより、前から１ビット毎に（あるいは1バイト毎に）暗号化する。暗号化部３８により暗号化されたデータは、通信部２０によりデータ送信される。
【００５１】
復号化部４０は、擬似乱数列発生部３６によって発生した擬似乱数ビット列を、ワンタイムパッド暗号の鍵として用いることで、通信部２０により受信された復号化対象データに対して、復号化を行う。例えば、図４（Ｂ）に示すように、ビット列で表した暗号化文（cypher text）と、暗号化の鍵としての擬似乱数ビット列とのＸＯＲを演算することにより、前から１ビット毎に（あるいは1バイト毎に）復号化する。復号化部４０により復号化されたデータは、データ入出力部３２により、データ端末１４Ａ、１４Ｂへ出力される。
【００５２】
次に、本実施の形態における擬似乱数ビット列を発生させる原理について説明する。
【００５３】
まず、共通秘密鍵として生成されたｄ×ｄの行列ＭAB（またはＭBA）及び共通のプライベートデータとして設定された素数ｐ１、ｐ２とを用いて、以下のように、２つの非可換行列Ａ１、Ａ２を生成する。なお、以下では、行列ＭABが、２×２の行列である場合を例に説明する。
【００５４】
以下の（８）式に示すように、行列ＭABと素数ｐ１とを用いて、行列Ａ１’を計算する。
【００５５】
【数１】
2014017556.tif 000003
【００５６】
そして、＜ｇ＞＝｛１，…，ｐ１−１｝となるジェネレータｇを求める。例えば、ｐ1＝７のジェネレータは、以下のように、＜３＞＝｛１，…，６｝である。
【００５７】
３１＝３，３２＝９ｍｏｄ７＝２，３３＝２７ｍｏｄ７＝６，３４＝８１ｍｏｄ７＝４，
３５＝２４３ｍｏｄ７＝５，・・・
【００５８】
そして、Ａ１”を、以下の（９）式で表わすとすると、ｄｅｔ  Ａ１”＝ｇになるようにｄ’を変更し、ｄ’を変更したＡ”１を、非可換行列Ａ１とする。
【００５９】
【数２】
2014017556.tif 000004
【００６０】
また、以下の（１０）式に示すように、行列ＭABと素数ｐ２とを用いて、行列Ａ２’を計算し、上記と同様に、非可換行列Ａ２を生成する。
【００６１】
【数３】
2014017556.tif 000005
【００６２】
ここで、非可換行列Ａ１、Ａ２を用いて生成される擬似乱数列の周期の長さＯ（Ａ）は、非可換行列Ａ１、Ａ２の生成に用いる、任意の素数ｐを用いて、以下の（１１）式のように書ける。
【００６３】
Ｏ（Ａ）≧ｐ      ・・・（１１）
【００６４】
たとえば、ｐを１０００００ビットの素数とした場合、Ａの周期はそれ以上に長くなる。
【００６５】
また、共通に設定された初期ベクトルｖ０に対して、生成された非可換行列Ａ１を用いて変換を行い、ベクトルｖ１を得る。また、ベクトルｖ１に対して、非可換行列Ａ１を用いた変換を繰り返し、ベクトル列Ｖ=｛ｖ０,ｖ１,...,ｖｔ｝を得る。ここでｖｉ＝Ａ１ｉｖ０である。
【００６６】
そして、得られたベクトル列Ｖから非線形変換により、ビット列Ｗ１を得る。ベクトル列Ｖからビット列Ｗを得る非線形変換として、Ｖの要素をｖｉ＝（ｖｉ,０,ｖｉ,１，...，ｖｉ，ｎ）とし、ｖｉ，０をバイナリ変換したビット列から、先頭ビットから続く０と次に現われた１とからなるビット列を含む先頭ビット列を取り除くカットオフ処理を行う。ここで、カットオフの後、残ったビット列は高い乱数性を持つことが知られている。
【００６７】
本実施の形態では、カットオフ処理において、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 232に置き換える。また、（積演算）a×b を、 a<< (b / 227) xorbに置き換える。ここで、a<< (b / 227)は、a を 、bを227で割った商だけずらすことを表わし、xorはビットごとの排他的論理和を表わす。
【００７３】
また、ベクトルｖiに、非可換行列Ａ１、Ａ２を作用させて、新しいベクトルｖi+1を得る際に、更に、行列の作用の方法を以下のように置き換えてもよい。
【００７４】
例えば、ｖi＝（ｖi1, ｖi2,..., ｖid）を、行列Ａを初期ベクトルｖ0にi回作用させたものとする（dはＡの次元）と、ｖi+1＝（ｖi+11, ｖi+12,..., ｖi+1d）を得る方法を以下のようにする。
【００７５】
まず、ｖi+11＝（Ａｖi）1とする。これはベクトルＡｖiの1番目の要素だけである。また、必要な計算は1番目の要素の計算だけである。2x2行列で書くと、
【００７６】
【数４】
2014017556.tif 000006
【００７７】
となるが、和演算と積演算は、上述したように、別の演算で置き換えられている。
【００７８】
そして、ｖi+12＝（Ａ（ｖi+11, ｖi2,..., ｖid））2とする。これは非可換行列Ａを、ｖiの1番目の要素をｖi+11に置き換えたものに作用させ、２番目の要素を取り出したものである。なお、ここで必要な計算は、2番目の要素の計算だけである。
【００７９】
そして、ｖi+13＝（Ａ（ｖi+11, ｖi+12,..., ｖid））2とする。これは上記と同様に、ｖiの１番目、２番目の要素を置き換えて、非可換行列Ａを作用させ、3番目の要素を抜き出したものである。
【００８０】
以降、d番目の要素まで同様に行い、ｖi+1を得る。
【００８１】
また、暗号化する平文のビット数をｎとすると、ビット列Ｗ１のビット数がnに到達した瞬間、ビット列Ｗ１に対する処理は中断され、ビット列Ｗ１の余った部分は捨てられる。
【００８２】
非可換行列Ａ２に対しても同様に、ベクトルへの作用及びカットオフ処理を繰り返し行い、ビット列Ｗ２を生成する。また、ビット列Ｗ２のビット数がnに到達した瞬間、ビット列Ｗ２に対する処理は中断され、ビット列Ｗ２の余った部分は捨てられる。
【００８３】
そして、最終的に得られたビット列Ｗ１とビット列Ｗ２とのＸＯＲを計算し、得られたビット列を、擬似乱数ビット列とする。なお、ビット列Ｗ１とビット列Ｗ２とのＸＯＲにより得られたビット列に対して、更に非線形変換を行って、その結果を、擬似乱数ビット列としてもよい。
【００８４】
擬似乱数列発生部３６は、上記のように、暗号化対象データのビット数又は復号化対象データのビット数と同じビット数の擬似乱数ビット列を発生させる。
【００８５】
＜暗号化処理システムの動作＞
次に、本実施の形態に係る暗号化処理システム１０の動作について説明する。
【００８６】
まず、ユーザ端末１４Ａから、データをユーザ端末１４Ｂへ送信する場合に、ユーザ端末１４Ａが、送信データを、暗号復号装置１２Ａに出力する。
【００８７】
次に、暗号復号装置１２Ａは、通信相手の暗号復号装置１２Ｂに対して、通信開始要求を送信し、暗号復号装置１２Ｂから応答信号を受信すると、暗号復号装置１２Ａにおいて、図５に示す共有秘密鍵算出処理ルーチンが実行される。また、暗号復号装置１２Ｂにおいても、同様に、図５に示す共有秘密鍵算出処理ルーチンが実行される。なお、以下では、暗号復号装置１２Ａにおいて、共有秘密鍵算出処理ルーチンを実行する場合について説明する。
【００８８】
まず、ステップ１００において、暗号復号装置１２Ａ、１２Ｂの間の通信において用いる公開データ（ｐ、ｄ、Ｑ、Ｓ）を取得する。例えば、Ｗｅｂ上に公開された公開データにアクセスして取得する。
【００８９】
そして、ステップ１０２において、秘密鍵ｎA、ｋAを生成する。次のステップ１０４では、上記ステップ１００で取得した公開データと、上記ステップ１０２で生成した秘密鍵とに基づいて、上記（１）式に従って、非可換行列ＭAを算出する。
【００９０】
ステップ１０６では、上記ステップ１０４で算出した非可換行列ＭAを、通信相手の暗号復号装置１２Ｂへ送信する。次のステップ１０８では、暗号復号装置１２Ｂから、非可換行列ＭBを受信したか否かを判定する。暗号復号装置１２Ｂによって同様に算出された非可換行列ＭBを受信すると、ステップ１１０へ進む。
【００９１】
ステップ１１０では、上記ステップ１００で取得した公開データと、上記ステップ１０２で生成した秘密鍵と、上記ステップ１０８で受信した非可換行列ＭBとに基づいて、上記（３）式に従って、行列ＭABを算出して、暗号復号装置１２Ｂとの通信における共有秘密鍵として設定し、共有秘密鍵算出処理ルーチンを終了する。
【００９２】
上記共有秘密鍵算出処理ルーチンは、通信が開始される毎に実行され、その度に、新しい秘密鍵が生成され、新しい共有秘密鍵が設定される。
【００９３】
また、暗号復号装置１２Ａにおいて、図６に示す擬似乱数列発生処理ルーチンが実行される。
【００９４】
まず、ステップ１２０において、暗号復号装置１２Ｂと共通に設定された共有秘密鍵ＭAB、素数ｐ１、ｐ２を用いて、非可換行列Ａ１、Ａ２を生成する。ステップ１２２では、ベクトルを識別する変数ｉを初期値である０に設定する。また、初期ベクトルｖ0を設定する。
【００９５】
次のステップ１２４では、ベクトルｖiに、非可換行列Ａ１、Ａ２をそれぞれ作用させて、ベクトルｖi+11、ｖi+12を計算する。ステップ１２６では、上記ステップ１２４で計算されたベクトルｖi+11、ｖi+12の各々を、ビット列に変換すると共に、それぞれのビット列に対して、カットオフ処理を行い、先頭ビット列をカットオフする。そして、ステップ１２８において、上記ステップ１２６で得られたビット列の各々を、ビット列Ｗ１、Ｗ２に対して更に並べるように追加する。
【００９６】
ステップ１３０では、ビット列Ｗ１、Ｗ２の各々のビット数が、送信データ（暗号化対象データ）のビット列のビット数に到達したか否かを判定する。ビット列Ｗ１、Ｗ２の各々のビット数が、ユーザ端末１４Ａから入力された送信データ（暗号化対象データ）のビット列のビット数に到達していない場合には、ステップ１３２において、変数ｉを１インクリメントして、上記ステップ１２４へ戻って、ステップ１２４以降の処理を繰り返す。ここで、ビット列Ｗ１のみについて、ビット数が、送信データのビット列のビット数に到達した場合には、上記ステップ１２４以降の処理において、非可換行列Ａ１を用いた処理は行わない。また、ビット列Ｗ２のみについて、ビット数が、送信データのビット列のビット数に到達した場合には、上記ステップ１２４以降の処理において、非可換行列Ａ２を用いた処理は行わない。
【００９７】
また、上記ステップ１３０において、ビット列Ｗ１、Ｗ２の双方のビット数が、送信データのビット列のビット数に到達したと判定された場合には、ステップ１３４へ進む。
【００９８】
ステップ１３４では、ビット列Ｗ１、Ｗ２のＸＯＲを演算して、擬似乱数ビット列Ｓを生成し、擬似乱数列発生処理ルーチンを終了する。
【００９９】
そして、暗号復号装置１２Ａは、上記の擬似乱数列発生処理ルーチンによって生成された擬似乱数ビット列Ｓと、ユーザ端末１４から入力された送信データのビット列とのＸＯＲを演算することにより、暗号化された送信データを生成する。また、暗号復号装置１２Ａは、暗号化された送信データを、インターネットアクセス網１６を介してユーザ端末１４Ｂへ送信する。
【０１００】
暗号化された送信データは、暗号復号装置１２Ｂによって受信され、暗号復号装置１２Ｂにおいて、上記図６の擬似乱数列発生処理ルーチンが同様に実行され、暗号化された送信データと同じビット数の擬似乱数ビット列Ｓが生成される。
【０１０１】
そして、暗号復号装置１２Ｂは、生成された擬似乱数ビット列Ｓと、暗号化された送信データのビット列とのＸＯＲを演算することにより、暗号化された送信データの平文を生成する。また、暗号復号装置１２Ｂは、送信データの平文を、送信先として指定されたユーザ端末Ｂへ出力する。
【０１０２】
次に、上記の実施の形態で説明した共有秘密鍵の算出アルゴリズムを用いた実験を行った結果について説明する。
【０１０３】
２者間における鍵共有の速度を検証した。秘密鍵を生成し、交換が終了するまでの計算時間を計測した。
【０１０４】
また、以下の環境でテストを行った。Ｗｉｎｄｏｗｓ７（登録商標）上のパフォーマンスは、以下の表１に示す。
【０１０５】
【表１】
2014017556.tif 000007
（ＲＳＡ公開鍵暗号（図７のRSA参照)）、Diffie‐Hellman型暗号（図７のDH参照)、Elliptic Curve（楕円）暗号（図７のECC参照）を比較対象として、速度の比較を行い、鍵生成、公開情報生成、鍵共有の速度をプロットした。図７に示すグラフより、本実施の形態で提案した手法（図７のQP-kex参照）は他の方式より圧倒的に速く、特に、RSAと比較して約10 倍の速度であることが分かった。
【０１０６】
また、以下の表２に示すようなモバイル端末上で、実装実験を行った。
【０１０７】
【表２】
2014017556.tif 000008
この端末はNokia（Ｒ） N70 platform である。比較とする対象は、Diffie‐Hellman型暗号（図８のDH参照)、Elliptic Curve（楕円）暗号（図８のECC参照） である。ＲＳＡ公開鍵暗号は非常に実行時間がかかるため割愛した。横軸に方式名と鍵長をとり、縦軸を実行時間とした。図８に示すグラフより、本実施の形態で提案した手法（図８のQP参照）は小型デバイスでも他の方式と比べ、圧倒的に実行時間が速く、鍵長を長くとっても実行時間は大きくならないということが分かった。
【０１０８】
以上説明したように、本発明の実施の形態に係る暗号化処理システムは、公開データと秘密鍵を用いて計算した非可換行列を、通信相手と交換し、通信相手から得られた非可換行列を用いて、共有秘密鍵を算出することにより、高速に、安全な共有秘密鍵を生成することができる。
【０１０９】
また、高速な処理で、長い鍵を共有することができる。
【０１１０】
また、共通秘密鍵への攻撃に対する強さについては、攻撃者は公開されている情報（ｐ、ｄ、Ｑ，Ｓ）と公開鍵ＭＡ、ＭＢから、次の問題を解き、秘密鍵ｎＡ、ｋＡ、（若しくはｎＢ、ｋＢ）を得る必要がある。
【０１１１】
[問題]次を満たすｎＡ、ｋＡを求めよ。
ＭＡ＝Ｓ−ＫＡＱｎＡＳＫＡ
【０１１２】
これは、ＤＨ型（離散対数問題）よりはるかに難しい問題となる。仮にｎＡを得ることができても、それからｋＡを得るには、非線形問題を解かねばならない。このとき、不定方程式が出現し、数学的には解を得る確率は０となる。従って、生成される共有秘密鍵は、D-H より数学的に厳密に安全である。
【０１１３】
また、非可換行列Ａ１、Ａ２を作用させる際の和演算及び積演算を、複数種類の演算子を組み合わせた演算方法に置換して、初期ベクトルに、非可換行列Ａ１、Ａ２を繰り返し作用させると共に非線形変換を行って、得られるビット列Ｗ１、Ｗ２のＸＯＲを計算して、擬似乱数ビット列を求め、擬似乱数ビット列を用いて暗号化又は復号化することにより、暗号化対象データ又は復号化対象データのビット数が可変である場合において、暗号化処理又は復号化処理を高速化し、かつ暗号解読強度を強くすることができる。また、共有秘密鍵の生成方法と、乱数を用いた暗号化・復号化方法とを組み合わせることで、高速かつ安全にストリーム暗号を開始することができる。
【０１１４】
また、他のストリーム暗号より高速で、計算能力の低い小型デバイス上でも実装が可能である。
【０１１５】
また、擬似乱数列発生アルゴリズムにおいて、いくつかの非線形変換を用いることにより、擬似乱数列の統計的ランダム性と長周期を保証することができ、生成された擬似乱数列を用いることにより、安全な使い捨て暗号鍵（One-Time-Padキー）を生成することができる。
【０１１６】
また、ストリーミング暗号を実現することができるため、音声・動画などのマルチメディア・ファイルを安全にかつ高速に転送することができる。
【０１１７】
なお、本発明は、上述した実施形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【０１１８】
例えば、サーバとモバイルとの間の通信を行うようにしてもよい。上記の共有秘密鍵の生成方法は、モバイル環境でも高速に動作し、鍵交換を行う２者間で計算量を偏らせることができるため、サーバとモバイル間通信に適している。
【０１１９】
また、ストリーミング暗号以外に、本発明を適用してもよく、自動車のキーレスエントリーなどへ応用してもよい。また、HDD(hard disk drive)の暗号化に応用してもよい。例えば、本実施の形態で説明した暗号化方法により、HDDに保存されるすべてのデータが暗号化され、正当なユーザしか読み出しできないようにしてもよい。また、Cloudサービスのセキュリティに、本発明を応用してもよい。
【０１２０】
また、本願明細書中において、プログラムが予めインストールされている実施形態として説明したが、当該プログラムを、コンピュータ読み取り可能な記録媒体に格納して提供することも可能である。
【符号の説明】
【０１２１】
１０   暗号化処理システム
１２Ａ、１２Ｂ       暗号復号装置
１４Ａ、１４Ｂ       ユーザ端末
１６   インターネットアクセス網
２０   通信部
２２   公開データ取得部
２４   秘密鍵生成部
２６   非可換行列生成部
２８   共有秘密鍵算出部
３２   データ入出力部
３４   共通データ設定部
３６   擬似乱数列発生部
３８   暗号化部
４０   復号化部
【図１】
2014017556.tif 000009
【図２】
2014017556.tif 000010
【図５】
2014017556.tif 000011
【図６】
2014017556.tif 000012
【図３】
2014017556.tif 000013
【図４】
2014017556.tif 000014
【図７】
2014017556.tif 000015
【図８】
2014017556.tif 000016