(57)【要約】【課題】任意長の追加データA,メッセージMを受け付けるとともに、通信コストの増加を抑制することができる暗号化データ生成装置等を提供する。【解決手段】暗号化データ生成装置は、追加データAに含まれるxビット分のデータAxをメッセージMに埋め込み、埋め込み後のメッセージM'を求め、追加データAが、rの最小の整数倍のビット長となるように所定のビット列を付加し、付加後の値A'を求め、メッセージM'と値A'とを用いて、暗号化データCとタグTとを生成し、暗号化データCとタグTと追加データAからデータAxを除いた部分A''とを出力する。【選択図】図５
2019015915.tif 000002
【特許請求の範囲】
【請求項１】
秘密鍵Kのビット長をcビットとし、rビットのレート部分とcビットのキャパシティ部分とを含むbビットの情報をステートとし、
メッセージMのビット長|M|をrビットで割ったときの剰余を(r-x)とし、追加データAに含まれるxビット分のデータAxをメッセージMに埋め込み、埋め込み後のメッセージM'を求める埋め込み部と、
前記追加データAまたは前記追加データAから前記データAxを除いた部分A''が、rの最小の整数倍のビット長となるように所定のビット列を付加し、付加後の値A'を求めるパディング部と、
前記値A'のビット長を|A'|とし、n=1,2,…,|A'|/rとし、前記値A'を|A'|/r個に分割して得られる各値をA'nとし、予め定めたビット列と秘密鍵Kとを連結した値を暗号化ステートの初期値S0とし、bビットの暗号化ステートSn-1のレート部分SR,n-1のrビットに対し、値A'nとの排他的論理和SR,n-1 XOR A'nを求める第一排他的論理和部と、
bビットのビット列dをbビットのビット列eに置換する関数を置換fとし、前記暗号化ステートSn-1の前記レート部分SR,n-1を前記排他的論理和SR,n-1 XOR A'nに置換えたビット列を置換fを用いて置換し、暗号化ステートSnを求める第一置換部と、
暗号化ステートS|A'|/rのキャパシティ部分SC,|A'|/rの所定のビットを反転させる境界設定部と、
前記メッセージM'のビット長を|M'|とし、m=1,2,…,|M'|/rとし、前記メッセージM'を|M'|/r個に分割して得られる各値をM'mとし、bビットの暗号化ステートS|A'|/r+m-1のレート部分SR,|A'|/r+m-1のrビットに対し、メッセージM'mとの排他的論理和SR,|A'|/r+m-1 XOR M'mを求める第二排他的論理和部と、
前記暗号化ステートS|A'|/r+m-1の前記レート部分SR,|A'|/r+m-1を前記排他的論理和SR,|A'|/r+m-1XOR M'mに置換えたビット列を前記置換fを用いて置換し、暗号化ステートS|A'|/r+mを求め、前記暗号化ステートS|A'|/r+mのレート部分SR,|A'|/r+mのrビットを暗号化データCmとし、|M'|/r個の前記暗号化データCmを含む暗号化データC=(C1,C2,…,C|M'|/r)を出力する第二置換部と、
暗号化ステートS|A'|/r+|M'|/rのキャパシティ部分SC,|A'|/r+|M'|/rと前記秘密鍵Kとの排他的論理和をタグTとして出力するタグ生成部と、
前記暗号化データCと前記タグTと前記部分A''とを出力する出力部を含む、
暗号化データ生成装置。
【請求項２】
秘密鍵Kのビット長をcビットとし、rビットのレート部分とcビットのキャパシティ部分とを含むbビットの情報をステートとし、メッセージMのビット長を|M|とし、
暗号化データCとタグTと追加データAからデータAxを除いた部分A''とを受け取る入力部と、
前記追加データAのビット長|A|と前記部分A''のビット長|A''|とに基づき前記データAxのビット長|Ax|を求める削除ビット長計算部と、
ビット長|M|をrビットで割ったときの剰余を(r-x)とし、前記メッセージMに前記追加データAに含まれるxビット分の前記データAxを埋め込んで得られるデータをM'とし、データM'のビット長を|M'|とし、m=1,2,…,|M'|/rとし、|M'|/r個の暗号化データCmを含む暗号化データC=(C1,C2,…,C|M'|/r)に含まれる暗号化データC|M'|/rとcビットの前記タグTとを連結した値をステートSmの初期値S|M'|/rとし、ステートS|M'|/rのキャパシティ部分SC,|M'|/rとcビットの前記秘密鍵Kとの排他的論理和SC,|M'|/rXOR Kを求める第三排他的論理和部と、
暗号化する際に用いた置換fの逆関数をf-1とし、前記ステートS|M'|/rの前記キャパシティ部分SC,|M'|/rを前記排他的論理和SC,|M'|/r XOR Kに置換えたビット列を逆関数f-1を用いて置換し、ステートS|M'|/r-1を求める第三置換部と、
m=1,2,3,…,|M'|/r-2において、ステートSmのレート部分SR,mと、暗号化データCmとの排他的論理和SR,m XOR Cmを復号データMm+1,Dとして出力する第四排他的論理和部と、
m=1,2,…,|M'|/r-1において、前記ステートSmの前記レート部分SR,mを暗号化データCmに置換えたビット列を前記逆関数f-1を用いて置換し、ステートSm-1を求める第四置換部と、
ステートS|M'|/rのレート部分SR,|M'|/rと、暗号化データC|M'|/rとの排他的論理和SR,|M'|/r XOR C|M'|/rを、ビット長|Ax|を用いて、データAxに対応するxビットとその他のr-xビットとに分割し、排他的論理和SR,|M'|/r XOR C|M'|/rからxビットを削除したr-xビットのデータを復号データM|M'|/r,Dとして出力する分割部と、
前記排他的論理和SR,|M'|/r XOR C|M'|/rのxビットを前記部分A''に結合し、復号追加データADとする結合部と、
前記復号追加データADが、rの最小の整数倍のビット長となるように所定のビット列を付加し、付加後の値A'Dを求めるパディング部と、
前記値A'Dのビット長を|A'D|とし、n=1,2,…,|A'D|/rとし、前記値A'Dを|A'D|/r個に分割して得られる各値をA'n,Dとし、予め定めたビット列と前記秘密鍵Kとを連結した値を復号ステートの初期値S0,Dとし、bビットの復号ステートSn-1,Dのレート部分SR,n-1,Dのrビットに対し、値A'n,Dとの排他的論理和SR,n-1,DXOR A'D,nを求める第五排他的論理和部と、
前記復号ステートSn-1,Dの前記レート部分SR,n-1,Dを前記排他的論理和SR,n-1,DXOR A'n,Dに置換えたビット列を前記置換fを用いて置換し、復号ステートSn,Dを求める第五置換部と、
復号ステートS|A'_D|/r,Dのキャパシティ部分SC,|A'_D|/r,Dの所定のビットを反転させ、復号ステートS|A'_D|/r,Dを更新する境界除去部と、
更新された前記復号ステートS|A'_D|/r,Dのキャパシティ部分SC,|A'_D|/r,DとステートS0のキャパシティ部分SC,0とが一致するか否かによりメッセージ認証を行い、一致する場合には、前記復号ステートS|A'_D|/r,Dのレート部分SR,|A'_D|/r,Dと前記ステートS0のレート部分SR,0との排他的論理和を復号データM1,Dとして出力する認証部とを含む、
復号データ生成装置。
【請求項３】
暗号化データ生成装置と復号データ生成装置とを含む追加データ付き認証暗号システムであって、
前記暗号化データ生成装置は、
秘密鍵Kのビット長をcビットとし、rビットのレート部分とcビットのキャパシティ部分とを含むbビットの情報をステートとし、
メッセージMのビット長|M|をrビットで割ったときの剰余を(r-x)とし、追加データAに含まれるxビット分のデータAxをメッセージMに埋め込み、埋め込み後のメッセージM'を求める埋め込み部と、
前記追加データAまたは前記追加データAから前記データAxを除いた部分A''が、rの最小の整数倍のビット長となるように所定のビット列を付加し、付加後の値A'を求めるパディング部と、
前記値A'のビット長を|A'|とし、n=1,2,…,|A'|/rとし、前記値A'を|A'|/r個に分割して得られる各値をA'nとし、予め定めたビット列と秘密鍵Kとを連結した値を暗号化ステートの初期値S0とし、bビットの暗号化ステートSn-1のレート部分SR,n-1のrビットに対し、値A'nとの排他的論理和SR,n-1 XOR A'nを求める第一排他的論理和部と、
bビットのビット列dをbビットのビット列eに置換する関数を置換fとし、前記暗号化ステートSn-1の前記レート部分SR,n-1を前記排他的論理和SR,n-1 XOR A'nに置換えたビット列を置換fを用いて置換し、暗号化ステートSnを求める第一置換部と、
暗号化ステートS|A'|/rのキャパシティ部分SC,|A'|/rの所定のビットを反転させる境界設定部と、
前記メッセージM'のビット長を|M'|とし、m=1,2,…,|M'|/rとし、前記メッセージM'を|M'|/r個に分割して得られる各値をM'mとし、bビットの暗号化ステートS|A'|/r+m-1のレート部分SR,|A'|/r+m-1のrビットに対し、メッセージM'mとの排他的論理和SR,|A'|/r+m-1 XOR M'mを求める第二排他的論理和部と、
前記暗号化ステートS|A'|/r+m-1の前記レート部分SR,|A'|/r+m-1を前記排他的論理和SR,|A'|/r+m-1XOR M'mに置換えたビット列を前記置換fを用いて置換し、暗号化ステートS|A'|/r+mを求め、前記暗号化ステートS|A'|/r+mのレート部分SR,|A'|/r+mのrビットを暗号化データCmとし、|M'|/r個の前記暗号化データCmを含む暗号化データC=(C1,C2,…,C|M'|/r)を出力する第二置換部と、
暗号化ステートS|A'|/r+|M'|/rのキャパシティ部分SC,|A'|/r+|M'|/rと前記秘密鍵Kとの排他的論理和をタグTとして出力するタグ生成部と、
前記暗号化データCと前記タグTと前記部分A''とを出力する出力部を含み、
前記復号データ生成装置は、
前記暗号化データCと前記タグTと前記部分A''とを受け取る入力部と、
前記追加データAのビット長|A|と前記部分A''のビット長|A''|とに基づき前記データAxのビット長|Ax|を求める削除ビット長計算部と、
前記暗号化データC=(C1,C2,…,C|M'|/r)に含まれる暗号化データC|M'|/rとcビットの前記タグTとを連結した値をステートSmの初期値S|M'|/rとし、ステートS|M'|/rのキャパシティ部分SC,|M'|/rとcビットの前記秘密鍵Kとの排他的論理和SC,|M'|/rXOR Kを求める第三排他的論理和部と、
前記置換fの逆関数をf-1とし、前記ステートS|M'|/rの前記キャパシティ部分SC,|M'|/rを前記排他的論理和SC,|M'|/r XOR Kに置換えたビット列を逆関数f-1を用いて置換し、ステートS|M'|/r-1を求める第三置換部と、
m=1,2,3,…,|M'|/r-2において、ステートSmのレート部分SR,mと、暗号化データCmとの排他的論理和SR,m XOR Cmを復号データMm+1,Dとして出力する第四排他的論理和部と、
m=1,2,…,|M'|/r-1において、前記ステートSmの前記レート部分SR,mを暗号化データCmに置換えたビット列を前記逆関数f-1を用いて置換し、ステートSm-1を求める第四置換部と、
ステートS|M'|/rのレート部分SR,|M'|/rと、暗号化データC|M'|/rとの排他的論理和SR,|M'|/r XOR C|M'|/rを、ビット長|Ax|を用いて、データAxに対応するxビットとその他のr-xビットとに分割し、排他的論理和SR,|M'|/r XOR C|M'|/rからxビットを削除したr-xビットのデータを復号データM|M'|/r,Dとして出力する分割部と、
前記排他的論理和SR,|M'|/r XOR C|M'|/rのxビットを前記部分A''に結合し、復号追加データADとする結合部と、
前記復号追加データADが、rの最小の整数倍のビット長となるように所定のビット列を付加し、付加後の値A'Dを求めるパディング部と、
前記値A'Dのビット長を|A'D|とし、n=1,2,…,|A'D|/rとし、前記値A'Dを|A'D|/r個に分割して得られる各値をA'n,Dとし、予め定めたビット列と前記秘密鍵Kとを連結した値を復号ステートの初期値S0,Dとし、bビットの復号ステートSn-1,Dのレート部分SR,n-1,Dのrビットに対し、値A'n,Dとの排他的論理和SR,n-1,DXOR A'D,nを求める第五排他的論理和部と、
前記復号ステートSn-1,Dの前記レート部分SR,n-1,Dを前記排他的論理和SR,n-1,DXOR A'n,Dに置換えたビット列を前記置換fを用いて置換し、復号ステートSn,Dを求める第五置換部と、
復号ステートS|A'_D|/r,Dのキャパシティ部分SC,|A'_D|/r,Dの所定のビットを反転させ、復号ステートS|A'_D|/r,Dを更新する境界除去部と、
更新された前記復号ステートS|A'_D|/r,Dのキャパシティ部分SC,|A'_D|/r,DとステートS0のキャパシティ部分SC,0とが一致するか否かによりメッセージ認証を行い、一致する場合には、前記復号ステートS|A'_D|/r,Dのレート部分SR,|A'_D|/r,Dと前記ステートS0のレート部分SR,0との排他的論理和を復号データM1,Dとして出力する認証部とを含む、
追加データ付き認証暗号システム。
【請求項４】
秘密鍵Kのビット長をcビットとし、rビットのレート部分とcビットのキャパシティ部分とを含むbビットの情報をステートとし、
暗号化データ生成装置が、
メッセージMのビット長|M|をrビットで割ったときの剰余を(r-x)とし、追加データAに含まれるxビット分のデータAxをメッセージMに埋め込み、埋め込み後のメッセージM'を求める埋め込みステップと、
前記追加データAまたは前記追加データAから前記データAxを除いた部分A''が、rの最小の整数倍のビット長となるように所定のビット列を付加し、付加後の値A'を求めるパディングステップと、
前記値A'のビット長を|A'|とし、n=1,2,…,|A'|/rとし、前記値A'を|A'|/r個に分割して得られる各値をA'nとし、予め定めたビット列と秘密鍵Kとを連結した値を暗号化ステートの初期値S0とし、bビットの暗号化ステートSn-1のレート部分SR,n-1のrビットに対し、値A'nとの排他的論理和SR,n-1 XOR A'nを求める第一排他的論理和ステップと、
bビットのビット列dをbビットのビット列eに置換する関数を置換fとし、前記暗号化ステートSn-1の前記レート部分SR,n-1を前記排他的論理和SR,n-1 XOR A'nに置換えたビット列を置換fを用いて置換し、暗号化ステートSnを求める第一置換ステップと、
暗号化ステートS|A'|/rのキャパシティ部分SC,|A'|/rの所定のビットを反転させる境界設定ステップと、
前記メッセージM'のビット長を|M'|とし、m=1,2,…,|M'|/rとし、前記メッセージM'を|M'|/r個に分割して得られる各値をM'mとし、bビットの暗号化ステートS|A'|/r+m-1のレート部分SR,|A'|/r+m-1のrビットに対し、メッセージM'mとの排他的論理和SR,|A'|/r+m-1 XOR M'mを求める第二排他的論理和ステップと、
前記暗号化ステートS|A'|/r+m-1の前記レート部分SR,|A'|/r+m-1を前記排他的論理和SR,|A'|/r+m-1XOR M'mに置換えたビット列を前記置換fを用いて置換し、暗号化ステートS|A'|/r+mを求め、前記暗号化ステートS|A'|/r+mのレート部分SR,|A'|/r+mのrビットを暗号化データCmとし、|M'|/r個の前記暗号化データCmを含む暗号化データC=(C1,C2,…,C|M'|/r)を出力する第二置換ステップと、
暗号化ステートS|A'|/r+|M'|/rのキャパシティ部分SC,|A'|/r+|M'|/rと前記秘密鍵Kとの排他的論理和をタグTとして出力するタグ生成ステップと、
前記暗号化データCと前記タグTと前記部分A''とを出力する出力ステップを実行する、
暗号化データ生成方法。
【請求項５】
秘密鍵Kのビット長をcビットとし、rビットのレート部分とcビットのキャパシティ部分とを含むbビットの情報をステートとし、メッセージMのビット長を|M|とし、
復号データ生成装置が、
暗号化データCとタグTと追加データAからデータAxを除いた部分A''とを受け取る入力ステップと、
前記追加データAのビット長|A|と前記部分A''のビット長|A''|とに基づき前記データAxのビット長|Ax|を求める削除ビット長計算ステップと、
ビット長|M|をrビットで割ったときの剰余を(r-x)とし、前記メッセージMに前記追加データAに含まれるxビット分の前記データAxを埋め込んで得られるデータをM'とし、データM'のビット長を|M'|とし、m=1,2,…,|M'|/rとし、|M'|/r個の暗号化データCmを含む暗号化データC=(C1,C2,…,C|M'|/r)に含まれる暗号化データC|M'|/rとcビットの前記タグTとを連結した値をステートSmの初期値S|M'|/rとし、ステートS|M'|/rのキャパシティ部分SC,|M'|/rとcビットの前記秘密鍵Kとの排他的論理和SC,|M'|/rXOR Kを求める第三排他的論理和ステップと、
暗号化する際に用いた置換fの逆関数をf-1とし、前記ステートS|M'|/rの前記キャパシティ部分SC,|M'|/rを前記排他的論理和SC,|M'|/r XOR Kに置換えたビット列を逆関数f-1を用いて置換し、ステートS|M'|/r-1を求める第三置換ステップと、
m=1,2,3,…,|M'|/r-2において、ステートSmのレート部分SR,mと、暗号化データCmとの排他的論理和SR,m XOR Cmを復号データMm+1,Dとして出力する第四排他的論理和ステップと、
m=1,2,…,|M'|/r-1において、前記ステートSmの前記レート部分SR,mを暗号化データCmに置換えたビット列を前記逆関数f-1を用いて置換し、ステートSm-1を求める第四置換ステップと、
ステートS|M'|/rのレート部分SR,|M'|/rと、暗号化データC|M'|/rとの排他的論理和SR,|M'|/r XOR C|M'|/rを、ビット長|Ax|を用いて、データAxに対応するxビットとその他のr-xビットとに分割し、排他的論理和SR,|M'|/r XOR C|M'|/rからxビットを削除したr-xビットのデータを復号データM|M'|/r,Dとして出力する分割ステップと、
前記排他的論理和SR,|M'|/r XOR C|M'|/rのxビットを前記部分A''に結合し、復号追加データADとする結合ステップと、
前記復号追加データADが、rの最小の整数倍のビット長となるように所定のビット列を付加し、付加後の値A'Dを求めるパディングステップと、
前記値A'Dのビット長を|A'D|とし、n=1,2,…,|A'D|/rとし、前記値A'Dを|A'D|/r個に分割して得られる各値をA'n,Dとし、予め定めたビット列と前記秘密鍵Kとを連結した値を復号ステートの初期値S0,Dとし、bビットの復号ステートSn-1,Dのレート部分SR,n-1,Dのrビットに対し、値A'n,Dとの排他的論理和SR,n-1,DXOR A'D,nを求める第五排他的論理和ステップと、
前記復号ステートSn-1,Dの前記レート部分SR,n-1,Dを前記排他的論理和SR,n-1,DXOR A'n,Dに置換えたビット列を前記置換fを用いて置換し、復号ステートSn,Dを求める第五置換ステップと、
復号ステートS|A'_D|/r,Dのキャパシティ部分SC,|A'_D|/r,Dの所定のビットを反転させ、復号ステートS|A'_D|/r,Dを更新する境界除去ステップと、
更新された前記復号ステートS|A'_D|/r,Dのキャパシティ部分SC,|A'_D|/r,DとステートS0のキャパシティ部分SC,0とが一致するか否かによりメッセージ認証を行い、一致する場合には、前記復号ステートS|A'_D|/r,Dのレート部分SR,|A'_D|/r,Dと前記ステートS0のレート部分SR,0との排他的論理和を復号データM1,Dとして出力する認証ステップとを実行する、
復号データ生成方法。
【請求項６】
暗号化データ生成装置と復号データ生成装置とを用いる追加データ付き認証暗号方法であって、
前記暗号化データ生成装置が、
秘密鍵Kのビット長をcビットとし、rビットのレート部分とcビットのキャパシティ部分とを含むbビットの情報をステートとし、
メッセージMのビット長|M|をrビットで割ったときの剰余を(r-x)とし、追加データAに含まれるxビット分のデータAxをメッセージMに埋め込み、埋め込み後のメッセージM'を求める埋め込みステップと、
前記追加データAまたは前記追加データAから前記データAxを除いた部分A''が、rの最小の整数倍のビット長となるように所定のビット列を付加し、付加後の値A'を求めるパディングステップと、
前記値A'のビット長を|A'|とし、n=1,2,…,|A'|/rとし、前記値A'を|A'|/r個に分割して得られる各値をA'nとし、予め定めたビット列と秘密鍵Kとを連結した値を暗号化ステートの初期値S0とし、bビットの暗号化ステートSn-1のレート部分SR,n-1のrビットに対し、値A'nとの排他的論理和SR,n-1 XOR A'nを求める第一排他的論理和ステップと、
bビットのビット列dをbビットのビット列eに置換する関数を置換fとし、前記暗号化ステートSn-1の前記レート部分SR,n-1を前記排他的論理和SR,n-1 XOR A'nに置換えたビット列を置換fを用いて置換し、暗号化ステートSnを求める第一置換ステップと、
暗号化ステートS|A'|/rのキャパシティ部分SC,|A'|/rの所定のビットを反転させる境界設定ステップと、
前記メッセージM'のビット長を|M'|とし、m=1,2,…,|M'|/rとし、前記メッセージM'を|M'|/r個に分割して得られる各値をM'mとし、bビットの暗号化ステートS|A'|/r+m-1のレート部分SR,|A'|/r+m-1のrビットに対し、メッセージM'mとの排他的論理和SR,|A'|/r+m-1 XOR M'mを求める第二排他的論理和ステップと、
前記暗号化ステートS|A'|/r+m-1の前記レート部分SR,|A'|/r+m-1を前記排他的論理和SR,|A'|/r+m-1XOR M'mに置換えたビット列を前記置換fを用いて置換し、暗号化ステートS|A'|/r+mを求め、前記暗号化ステートS|A'|/r+mのレート部分SR,|A'|/r+mのrビットを暗号化データCmとし、|M'|/r個の前記暗号化データCmを含む暗号化データC=(C1,C2,…,C|M'|/r)を出力する第二置換ステップと、
暗号化ステートS|A'|/r+|M'|/rのキャパシティ部分SC,|A'|/r+|M'|/rと前記秘密鍵Kとの排他的論理和をタグTとして出力するタグ生成ステップと、
前記暗号化データCと前記タグTと前記部分A''とを出力する出力ステップを実行し、
前記復号データ生成装置が、
前記暗号化データCと前記タグTと前記部分A''とを受け取る入力ステップと、
前記追加データAのビット長|A|と前記部分A''のビット長|A''|とに基づき前記データAxのビット長|Ax|を求める削除ビット長計算ステップと、
前記暗号化データC=(C1,C2,…,C|M'|/r)に含まれる暗号化データC|M'|/rとcビットの前記タグTとを連結した値をステートSmの初期値S|M'|/rとし、ステートS|M'|/rのキャパシティ部分SC,|M'|/rとcビットの前記秘密鍵Kとの排他的論理和SC,|M'|/rXOR Kを求める第三排他的論理和ステップと、
前記置換fの逆関数をf-1とし、前記ステートS|M'|/rの前記キャパシティ部分SC,|M'|/rを前記排他的論理和SC,|M'|/r XOR Kに置換えたビット列を逆関数f-1を用いて置換し、ステートS|M'|/r-1を求める第三置換ステップと、
m=1,2,3,…,|M'|/r-2において、ステートSmのレート部分SR,mと、暗号化データCmとの排他的論理和SR,m XOR Cmを復号データMm+1,Dとして出力する第四排他的論理和ステップと、
m=1,2,…,|M'|/r-1において、前記ステートSmの前記レート部分SR,mを暗号化データCmに置換えたビット列を前記逆関数f-1を用いて置換し、ステートSm-1を求める第四置換ステップと、
ステートS|M'|/rのレート部分SR,|M'|/rと、暗号化データC|M'|/rとの排他的論理和SR,|M'|/r XOR C|M'|/rを、ビット長|Ax|を用いて、データAxに対応するxビットとその他のr-xビットとに分割し、排他的論理和SR,|M'|/r XOR C|M'|/rからxビットを削除したr-xビットのデータを復号データM|M'|/r,Dとして出力する分割ステップと、
前記排他的論理和SR,|M'|/r XOR C|M'|/rのxビットを前記部分A''に結合し、復号追加データADとする結合ステップと、
前記復号追加データADが、rの最小の整数倍のビット長となるように所定のビット列を付加し、付加後の値A'Dを求めるパディングステップと、
前記値A'Dのビット長を|A'D|とし、n=1,2,…,|A'D|/rとし、前記値A'Dを|A'D|/r個に分割して得られる各値をA'n,Dとし、予め定めたビット列と前記秘密鍵Kとを連結した値を復号ステートの初期値S0,Dとし、bビットの復号ステートSn-1,Dのレート部分SR,n-1,Dのrビットに対し、値A'n,Dとの排他的論理和SR,n-1,DXOR A'D,nを求める第五排他的論理和ステップと、
前記復号ステートSn-1,Dの前記レート部分SR,n-1,Dを前記排他的論理和SR,n-1,DXOR A'n,Dに置換えたビット列を前記置換fを用いて置換し、復号ステートSn,Dを求める第五置換ステップと、
復号ステートS|A'_D|/r,Dのキャパシティ部分SC,|A'_D|/r,Dの所定のビットを反転させ、復号ステートS|A'_D|/r,Dを更新する境界除去ステップと、
更新された前記復号ステートS|A'_D|/r,Dのキャパシティ部分SC,|A'_D|/r,DとステートS0のキャパシティ部分SC,0とが一致するか否かによりメッセージ認証を行い、一致する場合には、前記復号ステートS|A'_D|/r,Dのレート部分SR,|A'_D|/r,Dと前記ステートS0のレート部分SR,0との排他的論理和を復号データM1,Dとして出力する認証ステップとを実行する、
追加データ付き認証暗号方法。
【請求項７】
請求項１の暗号化データ生成装置、または、請求項２の復号データ生成装置として、コンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、メッセージの秘匿と改ざん検知を同時に行う追加データ付き認証暗号技術に関する。
【背景技術】
【０００２】
追加データ付き認証暗号とは、メッセージMの秘匿、および、メッセージMと追加データAの認証（改ざん検知）を同時に行う共通鍵暗号プリミティブである。従来の追加データ付き認証暗号としては、例えば、非特許文献１および非特許文献２に記載されたAPE（Authenticated Permutation-Based Encryption）が挙げられる。追加データ付き認証暗号は、暗号化関数および復号関数の二つの関数から構成される。追加データ付き認証暗号では、受信者と送信者との間であらかじめ秘密の鍵Kを共有しておく。
【０００３】
送信者は、メッセージMと追加データAに加えて、暗号化関数を呼び出すたびに変化するナンスと呼ばれる値Nを選択する。暗号化関数は、メッセージM、追加データA、およびナンスNに対応する暗号化データCおよびタグTを生成し、(C,T,A,N)の組を受信者に送る。
【０００４】
受信者は(C,T,A,N)の組を受け取るが、この時点ではこれらの値が悪意ある第三者によって改ざんされていないという保証はない。受信者は受け取った(C,T,A,N)の組と自分が保有する鍵Kとを用いて検証を同時に行う復号関数を計算する。
【０００５】
検証を同時に行う復号関数にはいくつかの種類がある。多くの追加データ付き認証暗号では、受信者が再計算したタグT'が送信者から受け取ったタグTと一致するかどうかで検証を行う。APEでは、受信者が再計算した中間ステートの値がある値に一致するかどうかで検証を行う。いずれにせよ値が一致しなかった場合は復号に失敗した（データが改ざんされた）という結果を出力する。
【０００６】
APEは追加データ付き認証暗号の暗号化関数と復号関数の構成法である。保証したい安全性レベル（ビット数）に比べて比較的大きなサイズの置換（bijective map）を用いて暗号化関数と復号関数を構成するという特徴を持つ。APEの復号関数は、上記のとおり、従来の復号関数とは異なる特殊な方法で検証を行う。
【０００７】
図１を参照しながら、APEの暗号化関数の具体的な計算手順を説明する。APEの暗号化関数は、ステートと呼ばれるbビットのデータを、bビットの置換f:{0,1}b→{0,1}b、入力データ(N,A,M)、および鍵Kを用いて繰り返し更新しながら、暗号化データCおよびタグTを計算する。置換fの詳細は非特許文献２に記載されている。なお、ナンスNの入力は必須ではなく、ナンスNがある場合も、ナンスNは追加データAの一部となる。したがって、入力データは追加データA、メッセージM、および鍵Kを考慮すれば十分である。また、追加データAはメッセージMよりも先に処理される。そのような追加データAはヘッダと呼ばれる。追加データAとメッセージMの長さはいずれもrビットの倍長に限られる。
【０００８】
bビットのステートは、レートと呼ばれるrビットと、キャパシティと呼ばれるc（=b-r）ビットに分割される。暗号化関数を計算する場合、bビットのステートの値を、レート部分のrビットは0（すなわち、すべてのビットが0のビット列）に、キャパシティ部分のcビットは鍵Kの値に初期化する。
【０００９】
手順１．追加データAをrビットのブロックに分割する。bビットのステートのうちレート部分のrビットに対し、追加データAの第一ブロックとの排他的論理和を計算し、bビットのステートに対し、置換fを計算する。この置換fの出力を新たなステートの値とする。この操作を追加データAの最終ブロックが排他的論理和されるまで繰り返す。
【００１０】
手順２．bビットのステートのうちキャパシティ部分のcビットに対し、整数値1（すなわち、最下位ビットのみが1のビット列）との排他的論理和を計算する。
【００１１】
手順３．メッセージMをrビットのブロックに分割する。bビットのステートのうちレート部分のrビットに対し、メッセージMの第一ブロックとの排他的論理和を計算し、bビットのステートに対し、置換fを計算する。この置換fの出力を新たなステートの値とし、レート部分のrビットを暗号化データCの第一ブロックとして出力する。この操作をメッセージMの最終ブロックが排他的論理和されるまで繰り返す。
【００１２】
手順４．bビットのステートのうちキャパシティ部分のcビットに対し、cビットの鍵Kとの排他的論理和を計算し、計算結果をcビットのタグTとして出力する。
図２を参照しながら、APEの復号関数の具体的な計算手順を説明する。APEの復号関数は、APEの暗号化関数の計算をほぼ逆順に行う。復号関数は、通常(C,T,A,N)の組を入力にとるが、APEではナンスNは追加データAの一部とみなすことができるため、(C,T,A)の組を入力にとるとみなす。
【００１３】
復号関数を計算する場合、bビットのステートの値を、rビットの暗号化データCの最終ブロック（図２の例ではC2）とcビットのタグTとを連結した値に初期化する。
【００１４】
手順１．bビットのステートのうちキャパシティ部分のcビットに対し、cビットの鍵Kとの排他的論理和を計算し、計算結果によりキャパシティ部分のcビットを更新する。
【００１５】
手順２．bビットのステートに対し、置換fの逆関数f-1:{0,1}b→{0,1}bを計算する。この置換fの逆関数f-1の出力を新たなステートの値とする。レート部分のrビットに対し、暗号化データCの最終ブロックの一つ前のブロック（図２の例ではC1）との排他的論理和を計算し、計算結果をメッセージMの最終ブロック（図２の例ではM2）として出力する。また、レート部分のrビットを、暗号化データCの最終ブロックの一つ前のブロック（図２の例ではC1）により更新し、更新されたステートを新たなステートの値とする。この操作を暗号化データCの第一ブロック（図２の例ではC0）が処理されるまで繰り返す。これにより、メッセージMの最終ブロック（図２の例ではM2）から第二ブロック（図２の例ではM1）までが復元される。最後に更新されたステートのうち、レート部分のrビットの値をSr、キャパシティ部分のcビットの値をScとする。
【００１６】
手順３．メッセージMの第一ブロック（図２の例ではM0）の復元方法は、それ以外のブロックとは異なる。まず、暗号化関数の手順１から手順２までと同じ計算を行う。更新されたステートのうち、レート部分のrビットの値をS'r、キャパシティ部分のcビットの値をS'cとする。rビットの値Srとrビットの値S'rとの排他的論理和を計算し、計算結果をメッセージMの第一ブロック（図２の例ではM0）として出力する。
【００１７】
手順４．cビットの値Scとcビットの値S'cとを比較し、値が一致すれば復号されたメッセージM(図２の例ではM=M0||M1||M2)を出力する。なお、復号されたメッセージMを復号データともいう。一致しなかった場合は、メッセージMは出力せず、復号に失敗した旨を表すエラーコードのみを出力する。
【先行技術文献】
【非特許文献】
【００１８】
【非特許文献１】Elena Andreeva, Begul Bilgin, Andrey Bogdanov, Atul Luykx, Bart Mennink, Nicky Mouha and Kan Yasuda, "APE: Authenticated Permutation-Based Encryption for Lightweight Cryptography," FSE 2014, (eds.) Carlos Cid and Christian Rechberger, LNCS, Vol. 8540, pages 168-186, Springer, 2015.
【非特許文献２】Elena Andreeva, Begul Bilgin, Andrey Bogdanov, Atul Luykx, Florian Mendel, Bart Mennink, Nicky Mouha, Qingju Wang and Kan Yasuda, "PRIMATEs v1 | Submission to the CAESAR Competition," Submitted to CAESAR, 2014.
【発明の概要】
【発明が解決しようとする課題】
【００１９】
しかしながら、従来技術のAPEは仕様上、追加データA（ナンスNを含んでもよい）もメッセージMもレート部分のビット数rの倍長であることを前提にしている。そのため、応用先に制限がでてしまう。
【００２０】
例えば、任意長のA,Mを受け付ける方法として以下の方法が考えられる。A,Mのそれぞれに対し、サイズがrの倍数ではない場合、ビット1を付与し、その後rの倍数になるまでビット0を付与する。この操作を10*パディングと呼ぶ。10*パディングでは最大でr-1ビットの情報が付与される。
【００２１】
10*パディングを含んだ、任意長のA,Mを受け付けるように改変されたAPEの暗号化処理を図３に示す。この暗号化処理では、Mの長さがrの倍数でなかった場合に、暗号化データCの長さがメッセージMの長さよりも長くなり通信コストが増加する。
【００２２】
本発明は、任意長の追加データA,メッセージMを受け付けるとともに、通信コストの増加を抑制することができる暗号化データ生成装置、復号データ生成装置、追加データ付き認証暗号システム、その方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００２３】
上記の課題を解決するために、本発明の一態様によれば、追加データ付き認証暗号システムは、暗号化データ生成装置と復号データ生成装置とを含む。暗号化データ生成装置は、秘密鍵Kのビット長をcビットとし、rビットのレート部分とcビットのキャパシティ部分とを含むbビットの情報をステートとし、メッセージMのビット長|M|をrビットで割ったときの剰余を(r-x)とし、追加データAに含まれるxビット分のデータAxをメッセージMに埋め込み、埋め込み後のメッセージM'を求める埋め込み部と、追加データAまたは追加データAからデータAxを除いた部分A''が、rの最小の整数倍のビット長となるように所定のビット列を付加し、付加後の値A'を求めるパディング部と、値A'のビット長を|A'|とし、n=1,2,…,|A'|/rとし、値A'を|A'|/r個に分割して得られる各値をA'nとし、予め定めたビット列と秘密鍵Kとを連結した値を暗号化ステートの初期値S0とし、bビットの暗号化ステートSn-1のレート部分SR,n-1のrビットに対し、値A'nとの排他的論理和SR,n-1 XOR A'nを求める第一排他的論理和部と、bビットのビット列dをbビットのビット列eに置換する関数を置換fとし、暗号化ステートSn-1のレート部分SR,n-1を排他的論理和SR,n-1 XOR A'nに置換えたビット列を置換fを用いて置換し、暗号化ステートSnを求める第一置換部と、暗号化ステートS|A'|/rのキャパシティ部分SC,|A'|/rの所定のビットを反転させる境界設定部と、メッセージM'のビット長を|M'|とし、m=1,2,…,|M'|/rとし、メッセージM'を|M'|/r個に分割して得られる各値をM'mとし、bビットの暗号化ステートS|A'|/r+m-1のレート部分SR,|A'|/r+m-1のrビットに対し、メッセージM'mとの排他的論理和SR,|A'|/r+m-1 XOR M'mを求める第二排他的論理和部と、暗号化ステートS|A'|/r+m-1のレート部分SR,|A'|/r+m-1を排他的論理和SR,|A'|/r+m-1 XOR M'mに置換えたビット列を置換fを用いて置換し、暗号化ステートS|A'|/r+mを求め、暗号化ステートS|A'|/r+mのレート部分SR,|A'|/r+mのrビットを暗号化データCmとし、|M'|/r個の暗号化データCmを含む暗号化データC=(C1,C2,…,C|M'|/r)を出力する第二置換部と、暗号化ステートS|A'|/r+|M'|/rのキャパシティ部分SC,|A'|/r+|M'|/rと秘密鍵Kとの排他的論理和をタグTとして出力するタグ生成部と、暗号化データCとタグTと部分A''とを出力する出力部を含む。復号データ生成装置は、暗号化データCとタグTと部分A''とを受け取る入力部と、追加データAのビット長|A|と部分A''のビット長|A''|とに基づきデータAxのビット長|Ax|を求める削除ビット長計算部と、暗号化データC=(C1,C2,…,C|M'|/r)に含まれる暗号化データC|M'|/rとcビットのタグTとを連結した値をステートSmの初期値S|M'|/rとし、ステートS|M'|/rのキャパシティ部分SC,|M'|/rとcビットの秘密鍵Kとの排他的論理和SC,|M'|/r XOR Kを求める第三排他的論理和部と、置換fの逆関数をf-1とし、ステートS|M'|/rのキャパシティ部分SC,|M'|/rを排他的論理和SC,|M'|/r XOR Kに置換えたビット列を逆関数f-1を用いて置換し、ステートS|M'|/r-1を求める第三置換部と、m=1,2,3,…,|M'|/r-2において、ステートSmのレート部分SR,mと、暗号化データCmとの排他的論理和SR,m XOR Cmを復号データMm+1,Dとして出力する第四排他的論理和部と、m=1,2,…,|M'|/r-1において、ステートSmのレート部分SR,mを暗号化データCmに置換えたビット列を逆関数f-1を用いて置換し、ステートSm-1を求める第四置換部と、ステートS|M'|/rのレート部分SR,|M'|/rと、暗号化データC|M'|/rとの排他的論理和SR,|M'|/r XOR C|M'|/rを、ビット長|Ax|を用いて、データAxに対応するxビットとその他のr-xビットとに分割し、排他的論理和SR,|M'|/r XOR C|M'|/rからxビットを削除したr-xビットのデータを復号データM|M'|/r,Dとして出力する分割部と、排他的論理和SR,|M'|/rXOR C|M'|/rのxビットを部分A''に結合し、復号追加データADとする結合部と、復号追加データADが、rの最小の整数倍のビット長となるように所定のビット列を付加し、付加後の値A'Dを求めるパディング部と、値A'Dのビット長を|A'D|とし、n=1,2,…,|A'D|/rとし、値A'Dを|A'D|/r個に分割して得られる各値をA'n,Dとし、予め定めたビット列と秘密鍵Kとを連結した値を復号ステートの初期値S0,Dとし、bビットの復号ステートSn-1,Dのレート部分SR,n-1,Dのrビットに対し、値A'n,Dとの排他的論理和SR,n-1,D XOR A'D,nを求める第五排他的論理和部と、復号ステートSn-1,Dのレート部分SR,n-1,Dを排他的論理和SR,n-1,D XOR A'n,Dに置換えたビット列を置換fを用いて置換し、復号ステートSn,Dを求める第五置換部と、復号ステートS|A'_D|/r,Dのキャパシティ部分SC,|A'_D|/r,Dの所定のビットを反転させ、復号ステートS|A'_D|/r,Dを更新する境界除去部と、更新された復号ステートS|A'_D|/r,Dのキャパシティ部分SC,|A'_D|/r,DとステートS0のキャパシティ部分SC,0とが一致するか否かによりメッセージ認証を行い、一致する場合には、復号ステートS|A'_D|/r,Dのレート部分SR,|A'_D|/r,DとステートS0のレート部分SR,0との排他的論理和を復号データM1,Dとして出力する認証部とを含む。
【発明の効果】
【００２４】
本発明によれば、任意長の追加データA,メッセージMを受け付けるとともに、通信コストの増加を抑制することができるという効果を奏する。
【図面の簡単な説明】
【００２５】
【図１】従来の暗号化関数を説明するための図。
【図２】従来の復号関数を説明するための図。
【図３】従来の暗号化関数を説明するための図。
【図４】追加データ付き認証暗号システムの機能構成を例示する図。
【図５】暗号化装置の機能構成を例示する図。
【図６】追加データ計算部の機能構成を例示する図。
【図７】メッセージ計算部の機能構成を例示する図。
【図８】復号装置の機能構成を例示する図。
【図９】暗号化データ逆計算部の機能構成を例示する図。
【図１０】追加データ計算部の機能構成を例示する図。
【図１１】暗号化方法の処理手続きを例示する図。
【図１２】実施形態の暗号化関数の一例を説明するための図。
【図１３】復号方法の処理手続きを例示する図。
【図１４】実施形態の復号関数の一例を説明するための図。
【発明を実施するための形態】
【００２６】
以下、本発明の実施形態について、説明する。なお、以下の説明に用いる図面では、同じ機能を持つ構成部や同じ処理を行うステップには同一の符号を記し、重複説明を省略する。
【００２７】
＜第一実施形態＞
この発明の実施形態は、APEを任意長のメッセージMに自明に拡張した方式で、A（もしくはAの一部であるナンスN）の長さが復号処理の前に復号をする受信者と共有できている場合に、メッセージMの長さがステートのレート部分の長さrの倍数でなかった場合のパディングとして10*パディングを施すのではなく、A（もしくはAの一部であるナンスN）の一部をメッセージMの最後尾にレート部分の長さrの倍長になるまで埋め込む。埋め込んだデータは別途受信者に送信されず、受信者が復号処理の途中に復元する。
【００２８】
実施形態の追加データ付き認証暗号システムは、図４に示すように、追加データ付き認証暗号の暗号化関数を実行する暗号化装置１と、追加データ付き認証暗号の復号関数を実行する復号装置２とを含む。この実施形態では、暗号化装置１および復号装置２はそれぞれ通信網３へ接続される。通信網３は、接続される各装置が相互に通信可能なように構成された回線交換方式もしくはパケット交換方式の通信網であり、例えばインターネットやLAN（Local Area Network）、WAN（Wide Area Network）などを用いることができる。なお、各装置は必ずしも通信網３を介してオンラインで通信可能である必要はない。例えば、暗号化装置１が出力する情報を磁気テープやUSBメモリなどの可搬型記録媒体に記憶し、その可搬型記録媒体から復号装置２へオフラインで入力するように構成してもよい。
【００２９】
追加データ付き認証暗号システムに含まれる暗号化装置１は、図５に示すように、記憶部１０、入力部１１、初期化部１２、埋め込み部１３、追加データ計算部１４、境界設定部１５、メッセージ計算部１６、タグ生成部１７、および出力部１８を含む。暗号化装置１に含まれる追加データ計算部１４は、図６に示すように、パディング部１４０、分割部１４１、排他的論理和部１４２、および置換部１４３を含む。暗号化装置１に含まれるメッセージ計算部１６は、図７に示すように、分割部１６１、排他的論理和部１６２、置換部１６３を含む。
【００３０】
追加データ付き認証暗号システムに含まれる復号装置２は、図８に示すように、例えば、記憶部２０、入力部２１、削除ビット長計算部２１１、第一初期化部２２、タグ復号部２３、暗号化データ逆計算部２４、分割部２５１、結合部２５２、パディング部２５３、追加データ計算部２６、境界除去部２７、認証部２９、および出力部３０を含む。復号装置２に含まれる暗号化データ逆計算部２４は、図９に示すように、逆置換部２４１、および排他的論理和部２４２を含む。復号装置２に含まれる追加データ計算部２６は、図１０に示すように、分割部２６１、排他的論理和部２６３、および置換部２６４を含む。
【００３１】
暗号化装置１が図１１に示す各ステップの処理を行い、復号装置２が図１３に示す各ステップの処理を行うことにより実施形態の追加データ付き認証暗号方法が実現される。なお、追加データ付き認証暗号方法のうち暗号化装置１が実行する部分を暗号化方法とも呼び、復号装置２が実行する部分を復号方法とも呼ぶ。
【００３２】
暗号化装置１および復号装置２は、例えば、中央演算処理装置（CPU: Central Processing Unit）、主記憶装置（RAM: Random Access Memory）などを有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。暗号化装置１および復号装置２は、例えば、中央演算処理装置の制御のもとで各処理を実行する。暗号化装置１および復号装置２に入力されたデータや各処理で得られたデータは、例えば、主記憶装置に格納され、主記憶装置に格納されたデータは必要に応じて中央演算処理装置へ読み出されて他の処理に利用される。暗号化装置１および復号装置２の各処理部は、少なくとも一部が集積回路等のハードウェアによって構成されていてもよい。暗号化装置１および復号装置２が備える各記憶部は、例えば、RAM（Random Access Memory）などの主記憶装置、ハードディスクや光ディスクもしくはフラッシュメモリ（Flash Memory）のような半導体メモリ素子により構成される補助記憶装置、またはリレーショナルデータベースやキーバリューストアなどのミドルウェアにより構成することができる。
【００３３】
＜暗号化装置１＞
図１１、図１２を参照して、実施形態の追加データ付き認証暗号システムが実行する追加データ付き認証暗号方法のうち、暗号化装置１が実行する暗号化方法について説明する。
【００３４】
＜記憶部１０＞
暗号化装置１の記憶部１０には、rビットのレート部分とcビットのキャパシティ部分とからなるbビットのステート（以下、復号装置２の記憶部２０に記憶されるステートと区別するために、暗号化ステートとも呼ぶ）と、復号装置２との間であらかじめ共有した共通鍵Kとが記憶されている。例えば、ステートは512ビットとし、レート部分は256ビット、キャパシティ部分は256ビットに構成する（すなわち、b=512,r=256,c=256）。レート部分とキャパシティ部分の長さの比は、処理速度と安全性のトレードオフの関係となっている。レート部分の長さが大きくなると、処理速度は向上するが安全性は低下する。逆に、キャパシティ部分の長さが大きくなると、安全性が向上するが処理速度が低下する。したがって、b,r,cの各値は、所望の処理速度と安全性のバランスを鑑みて適宜設計すればよい。
【００３５】
＜入力部１１＞
ステップＳ１１において、暗号化装置１の入力部１１へ、追加データAとメッセージMとの組(A,M)が入力される。なお、ナンスNが従来のAPEと同様に追加データの一部として入力されてもよい。追加データAとメッセージMとはいずれも任意長のデータとする。入力部１１は、メッセージM及び追加データAを埋め込み部１３へ入力する。
【００３６】
＜初期化部１２＞
ステップＳ１２において、暗号化装置１の初期化部１２は、予め定めたビット列と秘密鍵Kとを連結した値を暗号化ステートの初期値S0として設定する。例えば、初期化部１２は、記憶部１０に記憶されている暗号化ステートのうち、レート部分の値を0（すなわち、すべてのビットが0のビット列）に、キャパシティ部分の値を共通鍵Kの値に設定して初期化する。
【００３７】
＜埋め込み部１３＞
ステップＳ１３において、暗号化装置１の埋め込み部１３は、入力部１１からメッセージM及び追加データAを受け取り、追加データAに含まれるxビット分のデータAxをメッセージMに埋め込み、埋め込み後のメッセージM'と、追加データAからデータAxを除いた部分A''とを求める。ここで、メッセージMのビット長|M|をrビットで割ったときの剰余を(r-x)とする。例えば、埋め込み部１３は、メッセージMがrビットの倍長よりもxビット（1≦x≦r-1）不足していた場合、メッセージMの最後尾に追加データAの最後尾xビット(データAx)を埋め込み、メッセージM'と部分A''とを求める。
【００３８】
＜追加データ計算部１４＞
ステップＳ１４において、暗号化装置１の追加データ計算部１４は、入力部１１から追加データAまたは埋め込み部１３から部分A''を受け取り、その追加データAまたは部分A''を用いて記憶部１０に記憶された暗号化ステートの値を更新する。
【００３９】
この場合、追加データ計算部１４は以下のように構成する。
【００４０】
（パディング部１４０）
パディング部１４０は、入力部１１から追加データAまたは埋め込み部１３から部分A''を受け取り、追加データAまたは部分A''が、rの最小の整数倍のビット長となるように所定のビット列を付加し、付加後の値A'を求める。例えば、追加データAがrビットの倍長でなかった場合、Aを10*パディングが施された値に更新する。更新され、rの倍長になった値をA'とする。なお、ナンス性が部分A''で保証されている場合、部分A''だけに対して10*パディングを施し値A'とする。
【００４１】
（分割部１４１）
追加データ計算部１４の分割部１４１は、値A'をrビットのブロックに分割する。なお、値A'のビット長を|A'|とし、n=1,2,…,|A'|/rとし、値A'を|A'|/r個に分割して得られる各値をA'nとする。
【００４２】
（排他的論理和部１４２）
追加データ計算部１４の排他的論理和部１４２は、bビットのステートSn-1のレート部分SR,n-1のrビットに対し、値A'nとの排他的論理和SR,n-1 XOR A'nを求める。
【００４３】
（置換部１４３）
追加データ計算部１４の置換部１４３は、暗号化ステートSn-1のレート部分SR,n-1を排他的論理和SR,n-1XOR A'nに置換えたビット列を置換fを用いて置換し、暗号化ステートSnを求める。なお、置換f:{0,1}b→{0,1}bは、bビットのビット列dをbビットのビット列eに置換する関数であり、入力された値を復元する逆関数f-1:{0,1}b→{0,1}b(bビットのビット列eをbビットのビット列dに置換する関数)を定義できる関数である。置換fとしては、例えば、非特許文献２に記載されている技術を用いることができる。n=1から順にn=|A'|/rまで排他的論理和部１４２及び置換部１４３の処理を繰り返す。
【００４４】
＜境界設定部１５＞
ステップＳ１５において、暗号化装置１の境界設定部１５は、追加データ計算部１４から暗号化ステートS|A'|/rを受け取り、暗号化ステートS|A'|/rのキャパシティ部分SC,|A'|/rの所定のビットを反転させ、暗号化ステートS|A'|/rを更新する。例えば、境界設定部１５は、暗号化ステートのキャパシティ部分と整数値1（すなわち、最下位ビットのみが1のビット列）との排他的論理和を計算し、その計算結果により暗号化ステートのキャパシティ部分を更新する。言い換えると、境界設定部１５は、暗号化ステートの最下位ビットのみを反転させる。この操作は、受信者が暗号化データCと追加データAとの境界を判別できるようにするために行われるものである。
【００４５】
＜メッセージ計算部１６＞
ステップＳ１６において、暗号化装置１のメッセージ計算部１６は、埋め込み部１３からメッセージM'を受け取り、そのメッセージM'を用いて記憶部１０に記憶された暗号化ステートの値を更新する。
【００４６】
（分割部１６１）
メッセージ計算部１６の分割部１６１は、メッセージM'をrビットのブロックに分割する。メッセージM'のビット長を|M'|とし、m=1,2,…,|M'|/rとし、メッセージM'を|M'|/r個に分割して得られる各値をM'mとする。
【００４７】
（排他的論理和部１６２）
メッセージ計算部１６の排他的論理和部１６２は、bビットの暗号化ステートS|A'|/r+m-1のレート部分SR,|A'|/r+m-1のrビットに対し、メッセージM'mとの排他的論理和SR,|A'|/r+m-1 XOR M'mを求める。
【００４８】
（置換部１６３）
メッセージ計算部１６の置換部１６３は、暗号化ステートS|A'|/r+m-1のレート部分SR,|A'|/r+m-1を排他的論理和SR,|A'|/r+m-1XOR M'mに置換えたビット列を置換fを用いて置換し、暗号化ステートS|A'|/r+mを求め、暗号化ステートS|A'|/r+mのレート部分のrビットを暗号化データCmとし、|M'|/r個の暗号化データCmを含む暗号化データC=(C1,C2,…,C|M'|/r)を出力する。
【００４９】
＜タグ生成部１７＞
ステップＳ１７において、暗号化装置１のタグ生成部１７は、暗号化ステートS|A'|/r+|M'|/rのキャパシティ部分SC,|A'|/r+|M'|/rと秘密鍵Kとの排他的論理和を計算し、その計算結果をタグTとして出力する。
【００５０】
＜出力部１８＞
ステップＳ１８において、暗号化装置１の出力部１８は、暗号化データCとタグTと追加データAからデータAxを除いた部分A''との組(C,T,A'')を復号装置２へ送信する。
【００５１】
＜復号装置２＞
図１３から図１４を参照して、実施形態の追加データ付き認証暗号システムが実行する追加データ付き認証暗号方法のうち、復号装置２が実行する復号方法について説明する。
【００５２】
＜記憶部２０＞
復号装置２の記憶部２０には、rビットのレート部分とcビットのキャパシティ部分とからなるbビットの2つのステート（以下、暗号化装置１の記憶部１０に記憶される暗号化ステートと区別するために、一方のステートを単にステートと呼び、他方を復号ステートと呼ぶ）と、暗号化装置１との間であらかじめ共有した共通鍵Kと追加データAのビット長|A|とが記憶されている。b,r,cの各値は、暗号化装置１の記憶部１０に記憶されたステートと同じものとする。なお、追加データAのビット長|A|は、復号処理に先立ち暗号化装置１と復号装置２との間(または送信者と受信者の間)で共有できているものとする。
【００５３】
＜入力部２１＞
ステップＳ２１において、復号装置２の入力部２１へ、暗号化装置１から受信した暗号化データCとタグTと追加データAからデータAxを除いた部分A''との組(C,T,A'')が入力される。入力部２１は、暗号化データCの最終ブロックとタグTとを第一初期化部２２へ、部分A''を追加データ計算部２６及び削除ビット長計算部２１１へ、暗号化データCの最終ブロック以外の各ブロックを暗号化データ逆計算部２４へそれぞれ入力する。
【００５４】
＜削除ビット長計算部２１１＞
ステップＳ２１１において、復号装置２の削除ビット長計算部２１１は、入力部２１から部分A''を受け取り、記憶部２０から追加データAのビット長|A|を取り出し、ビット長|A|とビット長|A''|とに基づきデータAxのビット長|Ax|(=|A|-|A''|)を求める。このような構成により、本来のAの長さと、実際に受信したA''の長さから、Aのうち最後尾の何ビットがMに埋め込まれたかを（つまりxの値を）計算することができる。
【００５５】
＜第一初期化部２２＞
ステップＳ２２において、復号装置２の第一初期化部２２は、入力部２１から暗号化データCの最終ブロックとタグTとを受け取り、記憶部２０に記憶されているステートのうち、レート部分の値を暗号化データCの最終ブロックの値に、キャパシティ部分の値をタグTの値に設定して初期化する。言い換えると、第一初期化部２２は、暗号化データC=(C1,C2,…,C|M'|/r)に含まれる暗号化データC|M'|/rとcビットのタグTとを連結した値をステートSmの初期値S|M'|/rとして設定する。なお、以降の処理において、m=|M'|/r,(|M'|/r)-1,…,0の順でステートSmを更新していく。
【００５６】
＜タグ復号部２３＞
ステップＳ２３において、復号装置２のタグ復号部２３は、第一初期化部２２からステートS|M'|/rを受け取り、そのキャパシティ部分SC,|M'|/rとcビットの秘密鍵Kとの排他的論理和SC,|M'|/r XOR Kを求める。
【００５７】
＜暗号化データ逆計算部２４＞
ステップＳ２４において、復号装置２の暗号化データ逆計算部２４は、入力部２１から暗号化データCの最終ブロック以外の各ブロックを受け取り、その暗号化データCの各ブロックCmを用いて記憶部２０に記憶されたステートSmの値を更新する。
【００５８】
（逆置換部２４１）
暗号化データ逆計算部２４の逆置換部２４１は、bビットのステート全体に対し、置換fの置換fの逆関数f-1を計算し、その計算結果を新たなステートの値とする。例えば、m=|M'|/r(暗号化データCの最終ブロック)において、逆置換部２４１は、ステートS|M'|/rのキャパシティ部分SC,|M'|/rを排他的論理和SC,|M'|/rXOR Kに置換えたビット列を逆関数f-1を用いて置換し、ステートS|M'|/r-1を求める。また、m=(|M'|/r)-1,(|M'|/r)-2,…,1において、逆置換部２４１は、ステートSmのレート部分SR,mを暗号化データCmに置換えたビット列を逆関数f-1を用いて置換し、ステートSm-1を求める。なお、逆関数f-1:{0,1}b→{0,1}bは、置換fの逆関数であり、bビットのビット列eをbビットのビット列dに置換する関数である。
【００５９】
（排他的論理和部２４２）
m=(|M'|/r)-2,(|M'|/r)-3,…,3,2,1において、暗号化データ逆計算部２４の排他的論理和部２４２は、ステートSmのレート部分SR,mと、暗号化データCmとの排他的論理和SR,m XOR Cmを計算し、計算結果を復号データMm+1,Dとして出力部３０から出力する。なお、|M'|/r個の復号データMm,Dを結合したものを最終的に出力する復号データMD=(M1,D||M2,D||…||M|M'|/r,D)とする。ただし、復号データM|M'|/r,Dは、排他的論理和SR,M'|/r XOR CM'|/r-1をそのまま用いるのではなく、後述する分割部２５１において分割された値を用いる。また、復号データM1,Dは、後述する認証部２９において得られる値を用いる。改ざん等なされていなければM=MDとなる。
【００６０】
＜分割部２５１＞
Ｓ２５１において、分割部２５１は、排他的論理和SR,|M'|/rXOR C|M'|/rを排他的論理和部２４２から、ビット長|Ax|を削除長計算部２１１から受け取り、ビット長|Ax|を用いて、排他的論理和SR,|M'|/rXOR C|M'|/rをデータAxに対応するxビット(例えば最後尾xビット)とその他のr-xビットとに分割し、排他的論理和SR,|M'|/r XOR C|M'|/rからxビット(例えば最後尾xビット)を削除したr-xビットのデータを復号データM|M'|/r,Dとして出力する。
【００６１】
＜結合部２５２＞
Ｓ２５２において、結合部２５２は、部分A''を入力部２１から、排他的論理和SR,|M'|/r XOR C|M'|/rをデータAxに対応するxビットを分割部２５１から受け取り、排他的論理和SR,|M'|/r XOR C|M'|/rのxビットを部分A''に結合し、復号追加データADとし、出力する。例えば、排他的論理和SR,|M'|/r XOR C|M'|/rの最後尾のxビットを部分A''の最後尾に追加する。
【００６２】
＜パディング部２５３＞
Ｓ２５３において、パディング部２５３は、結合部２５２から復号追加データADを受け取り、復号追加データADが、rの最小の整数倍のビット長となるように所定のビット列を付加し、付加後の値A'Dを求める。例えば、復号追加データADがrビットの倍長でなかった場合、復号追加データADを10*パディングが施された値に更新する。
【００６３】
＜追加データ計算部２６＞
ステップＳ２６において、復号装置２の追加データ計算部２６は、パディング部２５３から値A'Dを受け取り、その値A'Dを用いて記憶部２０に記憶された復号ステートの値を更新する。この場合、追加データ計算部２６は以下のように構成する。
【００６４】
（分割部２６１）
追加データ計算部２６の分割部２６１は、値A'Dをrビットのブロックに分割する。なお、値A'Dのビット長を|A'D|とし、n=1,2,…,|A'D|/rとし、値A'Dを|A'D|/r個に分割して得られる各値をA'n,Dとする。
【００６５】
（排他的論理和部２６３）
追加データ計算部２６の排他的論理和部２６３は、bビットの復号ステートSn-1,Dのレート部分SR,n-1,Dのrビットに対し、値A'n,Dとの排他的論理和SR,n-1,D XOR A'D,nを求める。なお、復号ステートSn-1,Dの初期値S0,Dは、暗号化装置１で用いた初期値S0と同じ値を用いる。
【００６６】
（置換部２６４）
追加データ計算部２６の置換部２６４は、復号ステートSn-1,Dのレート部分SR,n-1,Dを排他的論理和SR,n-1,DXOR A'n,Dに置換えたビット列を置換fを用いて置換し、復号ステートSn,Dを求める。置換部１６３と同様の方法により置換することができる。
【００６７】
追加データ計算部２６は、n=1から順にn=|A'D|/rまで排他的論理和部２６３及び置換部２６４の処理を繰り返す。
【００６８】
＜境界除去部２７＞
ステップＳ２７において、復号装置２の境界除去部２７は、復号ステートS|A'_D|/r,Dのキャパシティ部分SC,|A'_D|/r,Dの所定のビットを反転させる。なお、下付き添え字A'_Dは、A'Dを意味する。例えば、復号ステートのキャパシティ部分と整数値1との排他的論理和を計算し、その計算結果により復号ステートのキャパシティ部分を更新する。すなわち、境界除去部２７は、復号ステートの最下位ビットのみを反転させる。
【００６９】
＜認証部２９＞
ステップＳ２９において、復号装置２の認証部２９は、暗号化データ逆計算部２４からステートS0を受け取り、境界除去部２７から更新されたキャパシティ部分SC,|A'_D|/r,D(元のキャパシティ部分SC,|A'_D|/r,Dの所定のビットを反転させたビット列)を受け取り、キャパシティ部分SC,|A'_D|/r,DとステートS0のキャパシティ部分SC,0とが一致するか否かによりメッセージ認証を行う。例えば、復号ステートS|A'_D|/r,DとステートS0とを記憶部２０などに記憶する。その後、記憶部２０に記憶されたSC,|A'_D|/r,DとSC,0とを比較する。２つの値が等しい場合は、ステップＳ３０１へ処理を進め、復号ステートS|A'_D|/r,Dのレート部分SR,|A'_D|/r,DとステートS0のレート部分SR,0との排他的論理和を、復号データMDの第一ブロック(復号データM1,D)として出力部３０から出力する。二つの値が等しくない場合は、ステップＳ３０２へ処理を進め、復号に失敗した旨を表すエラーコードを出力部３０から出力する。
【００７０】
＜効果＞
以上の構成により、埋め込んだA（もしくはAの一部であるナンスN）の一部Axは受信者に送信されないため、埋め込んだxビット分、通信コストが改善される。
【００７１】
なお、本実施形態に係る暗号化装置のことを暗号化データを生成するという意味で暗号化データ生成装置ともいい、本実施形態に係る復号装置のことを復号データを生成するという意味で復号データ生成装置ともいう。なお、暗号化データ及び復号データは電子計算機による処理の用に供する情報であり、(i)暗号化データ生成装置を用いた暗号化データ生成方法に係る発明及び(ii)復号データ生成装置を用いた復号データ生成方法に係る発明が、特許法第二条第三項第三号の「物を生産する方法の発明」に該当することは言うまでもない。
【００７２】
＜その他の変形例＞
本発明は上記の実施形態及び変形例に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。
【００７３】
＜プログラム及び記録媒体＞
また、上記の実施形態及び変形例で説明した各装置における各種の処理機能をコンピュータによって実現してもよい。その場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【００７４】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００７５】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させてもよい。
【００７６】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶部に格納する。そして、処理の実行時、このコンピュータは、自己の記憶部に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実施形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよい。さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、プログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００７７】
また、コンピュータ上で所定のプログラムを実行させることにより、各装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【図１】
2019015915.tif 000003
【図２】
2019015915.tif 000004
【図３】
2019015915.tif 000005
【図４】
2019015915.tif 000006
【図５】
2019015915.tif 000007
【図６】
2019015915.tif 000008
【図７】
2019015915.tif 000009
【図８】
2019015915.tif 000010
【図９】
2019015915.tif 000011
【図１０】
2019015915.tif 000012
【図１１】
2019015915.tif 000013
【図１２】
2019015915.tif 000014
【図１３】
2019015915.tif 000015
【図１４】
2019015915.tif 000016