【手続補正書】
【提出日】平成27年4月2日(2015.4.2)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】０００６
【補正方法】変更
【補正の内容】
【０００６】
上記の目的を達成するために本発明に係る共有秘密鍵生成装置は、素数ｐ、自然数ｄ、行列式の値が１であるｄ×ｄの行列Ｑ（ｍｏｄ  ｐ）、及び逆行列が存在するｄ×ｄの行列Ｓ（ｍｏｄ  ｐ）を含む公開データを設定する公開データ設定手段と、自然数ｎA（ｍｏｄ  ｐ）、ｋA（ｍｏｄ  ｐ）を含む秘密鍵を生成する秘密鍵生成手段と、前記秘密鍵を用いて、以下の（Ｉ）式に従って、ｄ×ｄの行列ＭA（ｍｏｄ  ｐ）を計算し、通信相手へ送信する行列計算手段と、前記通信相手の秘密鍵に含まれる自然数ｎB（ｍｏｄ  ｐ）、ｋB（ｍｏｄ  ｐ）を用いて以下の（ＩＩ）式に従って計算される、ｄ×ｄの行列ＭB（ｍｏｄ  ｐ）を取得する行列取得手段と、前記行列取得手段によって取得された行列ＭBを用いて、以下の（ＩＩＩ）式に従ってｄ×ｄの行列ＭAB（ｍｏｄ  ｐ）を共有秘密鍵として算出する共有秘密鍵算出手段と、を含んで構成されている。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００８
【補正方法】変更
【補正の内容】
【０００８】
本発明に係るプログラムは、コンピュータを、素数ｐ、自然数ｄ、行列式の値が１であるｄ×ｄの行列Ｑ（ｍｏｄ  ｐ）、及び逆行列が存在するｄ×ｄの行列Ｓ（ｍｏｄ  ｐ）を含む公開データを設定する公開データ設定手段、自然数ｎA（ｍｏｄ  ｐ）、ｋA（ｍｏｄ  ｐ）を含む秘密鍵を生成する秘密鍵生成手段、前記秘密鍵を用いて、以下の（ＩＶ）式に従って、ｄ×ｄの行列ＭA（ｍｏｄ  ｐ）を計算し、通信相手へ送信する行列計算手段、前記通信相手の秘密鍵に含まれる自然数ｎB（ｍｏｄ  ｐ）、ｋB（ｍｏｄ  ｐ）を用いて以下の（Ｖ）式に従って計算される、ｄ×ｄの行列ＭB（ｍｏｄ  ｐ）を取得する行列取得手段、及び前記行列取得手段によって取得された行列ＭBを用いて、以下の（ＶＩ）式に従ってｄ×ｄの行列ＭAB（ｍｏｄ  ｐ）を共有秘密鍵として算出する共有秘密鍵算出手段として機能させるためのプログラムである。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００２９
【補正方法】変更
【補正の内容】
【００２９】
暗号復号装置１２Ａ、１２Ｂの公開データ取得部２２は、通信部２０を介して、通信相手との通信で用いる公開データとして、素数ｐ、自然数ｄ、ｄ×ｄの行列Ｑ（ｍｏｄ  ｐ）、及び逆行列が存在するｄ×ｄの行列Ｓ（ｍｏｄ  ｐ）を取得する。ただし、ｄｅｔ  Ｑ＝１であり、（ｍｏｄ  ｐ）は、変数あるいは行列の要素の値が、素数ｐの法であることを示す。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００５１
【補正方法】変更
【補正の内容】
【００５１】
復号化部４０は、擬似乱数列発生部３６によって発生した擬似乱数ビット列を、ワンタイムパッド暗号の鍵として用いることで、通信部２０により受信された復号化対象データに対して、復号化を行う。例えば、図４（Ｂ）に示すように、ビット列で表した暗号化文（cypher text）と、暗号化の鍵としての擬似乱数ビット列とのＸＯＲを演算することにより、前から１ビット毎に（あるいは1バイト毎に）復号化する。復号化部４０により復号化されたデータは、データ入出力部３２により、ユーザ端末１４Ａ、１４Ｂへ出力される。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００９９
【補正方法】変更
【補正の内容】
【００９９】
そして、暗号復号装置１２Ａは、上記の擬似乱数列発生処理ルーチンによって生成された擬似乱数ビット列Ｓと、ユーザ端末１４Ａから入力された送信データのビット列とのＸＯＲを演算することにより、暗号化された送信データを生成する。また、暗号復号装置１２Ａは、暗号化された送信データを、インターネットアクセス網１６を介してユーザ端末１４Ｂへ送信する。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】０１０１
【補正方法】変更
【補正の内容】
【０１０１】
そして、暗号復号装置１２Ｂは、生成された擬似乱数ビット列Ｓと、暗号化された送信データのビット列とのＸＯＲを演算することにより、暗号化された送信データの平文を生成する。また、暗号復号装置１２Ｂは、送信データの平文を、送信先として指定されたユーザ端末１４Ｂへ出力する。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】０１１０
【補正方法】変更
【補正の内容】
【０１１０】
また、共通秘密鍵への攻撃に対する強さについては、攻撃者は公開されている情報（ｐ、ｄ、Ｑ，Ｓ）と公開鍵ＭＡ、ＭＢから、次の問題を解き、秘密鍵ｎＡ、ｋＡ、（若しくはｎＢ、ｋＢ）を得る必要がある。
【手続補正８】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
素数ｐ、自然数ｄ、行列式の値が１であるｄ×ｄの行列Ｑ（ｍｏｄ  ｐ）、及び逆行列が存在するｄ×ｄの行列Ｓ（ｍｏｄ  ｐ）を含む公開データを設定する公開データ設定手段と、
自然数ｎ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      ・・・（６）