(57)【要約】【課題】処理量や送信量を抑えることができる暗号化データ生成装置等を提供する。【解決手段】暗号化データ生成装置は、追加データAを秘匿対象の|Ax|ビット分の値Axと(|A|-|Ax|)ビット分の値A'とに分割し、値A'を用いて得られる暗号化ステートのキャパシティ部分と、値Axを含むビット列との排他的論理和を計算し、暗号化ステートのキャパシティ部分を排他的論理和に置換えたビット列を新たな暗号化ステートとし、暗号化ステートとメッセージMを用いて、暗号化データCとタグTとを生成し、暗号化データCとタグTと値A'とを出力する。【選択図】図４
2019015918.tif 000002
【特許請求の範囲】
【請求項１】
秘密鍵Kのビット長をcビットとし、rビットのレート部分とcビットのキャパシティ部分とを含むbビットの情報をステートとし、メッセージMのビット長を|M|とし、追加データAのビット長を|A|とし、
|Ax|を1以上c/2以下の整数の何れかとし、追加データAを秘匿対象の|Ax|ビット分の値Axと(|A|-|Ax|)ビット分の値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と、前記値Axと(c-|Ax|)ビット分の所定のビット列gとを連結して得られるビット列Ax||gとの排他的論理和SC,|A'|/rxor Ax||gを計算し、前記暗号化ステートS|A'|/rのキャパシティ部分SC,|A'|/rを前記排他的論理和SC,|A'|/rxor Ax||gに置換えたビット列を新たな前記暗号化ステートS|A'|/rとする境界設定部と、
m=1,2,…,|M|/rとし、前記メッセージMを|M|/r個に分割して得られる各値をMmとし、bビットの暗号化ステートS|A'|/r+m-1のレート部分SR,|A'|/r+m-1のrビットに対し、メッセージMmとの排他的論理和SR,|A'|/r+m-1xor Mmを求める第二排他的論理和部と、
前記暗号化ステートS|A'|/r+m-1のレート部分SR,|A'|/r+m-1を前記排他的論理和SR,|A'|/r+m-1xor Mmに置換えたビット列を置換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'とを出力する出力部を含む、
暗号化データ生成装置。
【請求項２】
秘密鍵Kのビット長をcビットとし、rビットのレート部分とcビットのキャパシティ部分とを含むbビットの情報をステートとし、メッセージMのビット長を|M|とし、追加データAのビット長を|A|とし、
|Ax|を1以上c/2以下の整数の何れかとし、暗号化データCとタグTと追加データAに含まれる(|A|-|Ax|)ビット分の値A'とを受け取る入力部と、
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|/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,…,(|M|/r)-1において、ステートSmのレート部分SR,mと、暗号化データCmとの排他的論理和SR,m xor Cmを復号データMm+1,Dとして出力する第四排他的論理和部と、
前記ステートSmのレート部分SR,mを暗号化データCmに置換えたビット列を逆関数f-1を用いて置換し、ステートSm-1を求める第四置換部と、
値A'のビット長を|A'|とし、n=1,2,…,|A'|/rとし、前記値A'を|A'|/r個に分割して得られる各値をA'nとし、予め定めたビット列と秘密鍵Kとを連結した値を復号ステートの初期値S0,Dとし、bビットの復号ステートSn-1,Dのレート部分SR,n-1,Dのrビットに対し、値A'nとの排他的論理和SR,n-1,D xor A'nを求める第五排他的論理和部と、
前記復号ステートSn-1,Dのレート部分SR,n-1,Dを前記排他的論理和SR,n-1,Dxor A'nに置換えたビット列を置換fを用いて置換し、復号ステートSn,Dを求める第五置換部と、
復号ステートS|A'|/r,Dのキャパシティ部分SC,|A'|/r,Dと、|Ax|ビット分の0からなるビット列と(c-|Ax|)ビット分の所定のビット列gとを連結して得られるビット列00…0||gとの排他的論理和SC,|A'|/r,D xor 00…0||gを計算し、計算結果により復号ステートS|A'|/r,Dを更新する境界除去部と、
更新された復号ステートS|A'|/r,Dのキャパシティ部分SC,|A'|/r,Dのビット列gに対応する部分と、ステートS0のキャパシティ部分SC,0のビット列gに対応する部分とが一致するか否かによりメッセージ認証を行い、一致する場合には、前記キャパシティ部分SC,|A'|/r,Dの|Ax|ビット分の0からなるビット列に対応する部分と、前記キャパシティ部分SC,0の|Ax|ビット分の0からなるビット列に対応する部分との排他的論理和をAxとして出力し、復号ステートS|A'|/r,Dのレート部分SR,|A'|/r,DとステートS0のレート部分SR,0との排他的論理和を復号データM1,Dとして出力する認証部とを含む、
復号データ生成装置。
【請求項３】
暗号化データ生成装置と復号データ生成装置とを含む追加データ付き認証暗号システムであって、
前記暗号化データ生成装置は、
秘密鍵Kのビット長をcビットとし、rビットのレート部分とcビットのキャパシティ部分とを含むbビットの情報をステートとし、メッセージMのビット長を|M|とし、追加データAのビット長を|A|とし、
|Ax|を1以上c/2以下の整数の何れかとし、追加データAを秘匿対象の|Ax|ビット分の値Axと(|A|-|Ax|)ビット分の値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と、前記値Axと(c-|Ax|)ビット分の所定のビット列gとを連結して得られるビット列Ax||gとの排他的論理和SC,|A'|/rxor Ax||gを計算し、前記暗号化ステートS|A'|/rのキャパシティ部分SC,|A'|/rを前記排他的論理和SC,|A'|/rxor Ax||gに置換えたビット列を新たな前記暗号化ステートS|A'|/rとする境界設定部と、
m=1,2,…,|M|/rとし、前記メッセージMを|M|/r個に分割して得られる各値をMmとし、bビットの暗号化ステートS|A'|/r+m-1のレート部分SR,|A'|/r+m-1のrビットに対し、メッセージMmとの排他的論理和SR,|A'|/r+m-1xor Mmを求める第二排他的論理和部と、
前記暗号化ステートS|A'|/r+m-1のレート部分SR,|A'|/r+m-1を前記排他的論理和SR,|A'|/r+m-1xor Mmに置換えたビット列を置換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'とを出力する出力部を含み、
前記復号データ生成装置は、
前記暗号化データCと前記タグTと前記追加データAに含まれる(|A|-|Ax|)ビット分の前記値A'とを受け取る入力部と、
前記暗号化データ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,…,(|M|/r)-1において、ステートSmのレート部分SR,mと、暗号化データCmとの排他的論理和SR,m xor Cmを復号データMm+1,Dとして出力する第四排他的論理和部と、
前記ステートSmのレート部分SR,mを暗号化データCmに置換えたビット列を逆関数f-1を用いて置換し、ステートSm-1を求める第四置換部と、
予め定めたビット列と秘密鍵Kとを連結した値を復号ステートの初期値S0,Dとし、bビットの復号ステートSn-1,Dのレート部分SR,n-1,Dのrビットに対し、値A'nとの排他的論理和SR,n-1,D xor A'nを求める第五排他的論理和部と、
前記復号ステートSn-1,Dのレート部分SR,n-1,Dを前記排他的論理和SR,n-1,Dxor A'nに置換えたビット列を置換fを用いて置換し、復号ステートSn,Dを求める第五置換部と、
復号ステートS|A'|/r,Dのキャパシティ部分SC,|A'|/r,Dと、|Ax|ビット分の0からなるビット列と(c-|Ax|)ビット分の所定のビット列gとを連結して得られるビット列00…0||gとの排他的論理和SC,|A'|/r,D xor 00…0||gを計算し、計算結果により復号ステートS|A'|/r,Dを更新する境界除去部と、
更新された復号ステートS|A'|/r,Dのキャパシティ部分SC,|A'|/r,Dのビット列gに対応する部分と、ステートS0のキャパシティ部分SC,0のビット列gに対応する部分とが一致するか否かによりメッセージ認証を行い、一致する場合には、前記キャパシティ部分SC,|A'|/r,Dの|Ax|ビット分の0からなるビット列に対応する部分と、前記キャパシティ部分SC,0の|Ax|ビット分の0からなるビット列に対応する部分との排他的論理和をAxとして出力し、復号ステートS|A'|/r,Dのレート部分SR,|A'|/r,DとステートS0のレート部分SR,0との排他的論理和を復号データM1,Dとして出力する認証部とを含む、
追加データ付き認証暗号システム。
【請求項４】
秘密鍵Kのビット長をcビットとし、rビットのレート部分とcビットのキャパシティ部分とを含むbビットの情報をステートとし、メッセージMのビット長を|M|とし、追加データAのビット長を|A|とし、
暗号化データ生成装置が、
|Ax|を1以上c/2以下の整数の何れかとし、追加データAを秘匿対象の|Ax|ビット分の値Axと(|A|-|Ax|)ビット分の値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と、前記値Axと(c-|Ax|)ビット分の所定のビット列gとを連結して得られるビット列Ax||gとの排他的論理和SC,|A'|/rxor Ax||gを計算し、前記暗号化ステートS|A'|/rのキャパシティ部分SC,|A'|/rを前記排他的論理和SC,|A'|/rxor Ax||gに置換えたビット列を新たな前記暗号化ステートS|A'|/rとする境界設定ステップと、
m=1,2,…,|M|/rとし、前記メッセージMを|M|/r個に分割して得られる各値をMmとし、bビットの暗号化ステートS|A'|/r+m-1のレート部分SR,|A'|/r+m-1のrビットに対し、メッセージMmとの排他的論理和SR,|A'|/r+m-1xor Mmを求める第二排他的論理和ステップと、
前記暗号化ステートS|A'|/r+m-1のレート部分SR,|A'|/r+m-1を前記排他的論理和SR,|A'|/r+m-1xor Mmに置換えたビット列を置換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'とを出力する出力ステップを含む、
暗号化データ生成方法。
【請求項５】
秘密鍵Kのビット長をcビットとし、rビットのレート部分とcビットのキャパシティ部分とを含むbビットの情報をステートとし、メッセージMのビット長を|M|とし、追加データAのビット長を|A|とし、
復号データ生成装置が、
|Ax|を1以上c/2以下の整数の何れかとし、暗号化データCとタグTと追加データAに含まれる(|A|-|Ax|)ビット分の値A'とを受け取る入力ステップと、
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|/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,…,(|M|/r)-1において、ステートSmのレート部分SR,mと、暗号化データCmとの排他的論理和SR,m xor Cmを復号データMm+1,Dとして出力する第四排他的論理和ステップと、
前記ステートSmのレート部分SR,mを暗号化データCmに置換えたビット列を逆関数f-1を用いて置換し、ステートSm-1を求める第四置換ステップと、
値A'のビット長を|A'|とし、n=1,2,…,|A'|/rとし、前記値A'を|A'|/r個に分割して得られる各値をA'nとし、予め定めたビット列と秘密鍵Kとを連結した値を復号ステートの初期値S0,Dとし、bビットの復号ステートSn-1,Dのレート部分SR,n-1,Dのrビットに対し、値A'nとの排他的論理和SR,n-1,D xor A'nを求める第五排他的論理和ステップと、
前記復号ステートSn-1,Dのレート部分SR,n-1,Dを前記排他的論理和SR,n-1,Dxor A'nに置換えたビット列を置換fを用いて置換し、復号ステートSn,Dを求める第五置換ステップと、
復号ステートS|A'|/r,Dのキャパシティ部分SC,|A'|/r,Dと、|Ax|ビット分の0からなるビット列と(c-|Ax|)ビット分の所定のビット列gとを連結して得られるビット列00…0||gとの排他的論理和SC,|A'|/r,D xor 00…0||gを計算し、計算結果により復号ステートS|A'|/r,Dを更新する境界除去ステップと、
更新された復号ステートS|A'|/r,Dのキャパシティ部分SC,|A'|/r,Dのビット列gに対応する部分と、ステートS0のキャパシティ部分SC,0のビット列gに対応する部分とが一致するか否かによりメッセージ認証を行い、一致する場合には、前記キャパシティ部分SC,|A'|/r,Dの|Ax|ビット分の0からなるビット列に対応する部分と、前記キャパシティ部分SC,0の|Ax|ビット分の0からなるビット列に対応する部分との排他的論理和をAxとして出力し、復号ステートS|A'|/r,Dのレート部分SR,|A'|/r,DとステートS0のレート部分SR,0との排他的論理和を復号データM1,Dとして出力する認証ステップとを含む、
復号データ生成方法。
【請求項６】
暗号化データ生成装置と復号データ生成装置とを用いた追加データ付き認証暗号方法であって、
前記暗号化データ生成装置が、
秘密鍵Kのビット長をcビットとし、rビットのレート部分とcビットのキャパシティ部分とを含むbビットの情報をステートとし、メッセージMのビット長を|M|とし、追加データAのビット長を|A|とし、
|Ax|を1以上c/2以下の整数の何れかとし、追加データAを秘匿対象の|Ax|ビット分の値Axと(|A|-|Ax|)ビット分の値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と、前記値Axと(c-|Ax|)ビット分の所定のビット列gとを連結して得られるビット列Ax||gとの排他的論理和SC,|A'|/rxor Ax||gを計算し、前記暗号化ステートS|A'|/rのキャパシティ部分SC,|A'|/rを前記排他的論理和SC,|A'|/rxor Ax||gに置換えたビット列を新たな前記暗号化ステートS|A'|/rとする境界設定ステップと、
m=1,2,…,|M|/rとし、前記メッセージMを|M|/r個に分割して得られる各値をMmとし、bビットの暗号化ステートS|A'|/r+m-1のレート部分SR,|A'|/r+m-1のrビットに対し、メッセージMmとの排他的論理和SR,|A'|/r+m-1xor Mmを求める第二排他的論理和ステップと、
前記暗号化ステートS|A'|/r+m-1のレート部分SR,|A'|/r+m-1を前記排他的論理和SR,|A'|/r+m-1xor Mmに置換えたビット列を置換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'とを出力する出力ステップを実行し、
前記復号データ生成装置が、
前記暗号化データCと前記タグTと前記追加データAに含まれる(|A|-|Ax|)ビット分の前記値A'とを受け取る入力ステップと、
前記暗号化データ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,…,(|M|/r)-1において、ステートSmのレート部分SR,mと、暗号化データCmとの排他的論理和SR,m xor Cmを復号データMm+1,Dとして出力する第四排他的論理和ステップと、
前記ステートSmのレート部分SR,mを暗号化データCmに置換えたビット列を逆関数f-1を用いて置換し、ステートSm-1を求める第四置換ステップと、
予め定めたビット列と秘密鍵Kとを連結した値を復号ステートの初期値S0,Dとし、bビットの復号ステートSn-1,Dのレート部分SR,n-1,Dのrビットに対し、値A'nとの排他的論理和SR,n-1,D xor A'nを求める第五排他的論理和ステップと、
前記復号ステートSn-1,Dのレート部分SR,n-1,Dを前記排他的論理和SR,n-1,Dxor A'nに置換えたビット列を置換fを用いて置換し、復号ステートSn,Dを求める第五置換ステップと、
復号ステートS|A'|/r,Dのキャパシティ部分SC,|A'|/r,Dと、|Ax|ビット分の0からなるビット列と(c-|Ax|)ビット分の所定のビット列gとを連結して得られるビット列00…0||gとの排他的論理和SC,|A'|/r,D xor 00…0||gを計算し、計算結果により復号ステートS|A'|/r,Dを更新する境界除去ステップと、
更新された復号ステートS|A'|/r,Dのキャパシティ部分SC,|A'|/r,Dのビット列gに対応する部分と、ステートS0のキャパシティ部分SC,0のビット列gに対応する部分とが一致するか否かによりメッセージ認証を行い、一致する場合には、前記キャパシティ部分SC,|A'|/r,Dの|Ax|ビット分の0からなるビット列に対応する部分と、前記キャパシティ部分SC,0の|Ax|ビット分の0からなるビット列に対応する部分との排他的論理和をAxとして出力し、復号ステートS|A'|/r,Dのレート部分SR,|A'|/r,DとステートS0のレート部分SR,0との排他的論理和を復号データM1,Dとして出力する認証ステップとを実行する、
追加データ付き認証暗号方法。
【請求項７】
暗号化データ生成装置と復号データ生成装置とを含む追加データ付き認証暗号システムであって、
前記暗号化データ生成装置は、
秘密鍵Kのビット長をcビットとし、rビットのレート部分とcビットのキャパシティ部分とを含むbビットの情報をステートとし、メッセージMのビット長を|M|とし、追加データAのビット長を|A|とし、
|Mx|を1以上c/2以下の整数の何れかとし、メッセージMを|Mx|ビット分の値Mxと(|M|-|Mx|)ビット分の値M'とに分割する分割部と、
n=1,2,…,|A|/rとし、前記メッセージAを|A|/r個に分割して得られる各値をAnとし、予め定めたビット列と秘密鍵Kとを連結した値を暗号化ステートの初期値S0とし、bビットの暗号化ステートSn-1のレート部分SR,n-1のrビットに対し、値Anとの排他的論理和SR,n-1 xor Anを求める第一排他的論理和部と、
bビットのビット列dをbビットのビット列eに置換する関数を置換fとし、前記暗号化ステートSn-1のレート部分SR,n-1を前記排他的論理和SR,n-1 xor Anに置換えたビット列を置換fを用いて置換し、暗号化ステートSnを求める第一置換部と、
暗号化ステートS|A|/rのキャパシティ部分SC,|A|/rと、前記値Mxと(c-|Mx|)ビット分の所定のビット列g2とを連結して得られるビット列Mx||g2との排他的論理和SC,|A|/rxor Mx||g2を計算し、前記暗号化ステートS|A|/rのキャパシティ部分SC,|A|/rを前記排他的論理和SC,|A|/rxor Mx||g2に置換えたビット列を新たな前記暗号化ステートS|A|/rとする境界設定部と、
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とを出力する出力部を含み、
前記復号データ生成装置は、
前記暗号化データCと前記タグTと前記追加データAとを受け取る入力部と、
前記暗号化データ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,…,(|M'|/r)-1において、ステートSmのレート部分SR,mと、暗号化データCmとの排他的論理和SR,m xor Cmを復号データMm+1,Dとして出力する第四排他的論理和部と、
前記ステートSmのレート部分SR,mを暗号化データCmに置換えたビット列を逆関数f-1を用いて置換し、ステートSm-1を求める第四置換部と、
予め定めたビット列と秘密鍵Kとを連結した値を復号ステートの初期値S0,Dとし、bビットの復号ステートSn-1,Dのレート部分SR,n-1,Dのrビットに対し、値Anとの排他的論理和SR,n-1,D xor Anを求める第五排他的論理和部と、
前記復号ステートSn-1,Dのレート部分SR,n-1,Dを前記排他的論理和SR,n-1,Dxor Anに置換えたビット列を置換fを用いて置換し、復号ステートSn,Dを求める第五置換部と、
復号ステートS|A|/r,Dのキャパシティ部分SC,|A|/r,Dと、|Mx|ビット分の0からなるビット列と(c-|Mx|)ビット分の所定のビット列g2とを連結して得られるビット列00…0||g2との排他的論理和SC,|A|/r,Dxor 00…0||g2を計算し、計算結果により復号ステートS|A|/r,Dを更新する境界除去部と、
更新された復号ステートS|A|/r,Dのキャパシティ部分SC,|A|/r,Dのビット列g2に対応する部分と、ステートS0のキャパシティ部分SC,0のビット列g2に対応する部分とが一致するか否かによりメッセージ認証を行い、一致する場合には、前記キャパシティ部分SC,|A|/r,Dの|Mx|ビット分の0からなるビット列に対応する部分と、前記キャパシティ部分SC,0の|Mx|ビット分の0からなるビット列に対応する部分との排他的論理和をMxとして出力し、復号ステートS|A|/r,Dのレート部分SR,|A|/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-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は出力せず、復号に失敗した旨を表すエラーコードのみを出力する。
【００１９】
また、秘密ナンスを実現する追加データ付き認証暗号としてProtected IV (PIV)方式が存在する(非特許文献３参照)。秘密ナンスとは、ナンスの一種であり、値が暗号化されてから通信路を流れる値のことを言う。これまでに通信したパケット数等をナンスとして用いる場合、ナンスにプライバシー情報を含むため、ナンスを暗号化してから送ることが望ましい。
【００２０】
通常のナンスを利用する追加データ付き認証暗号では、送信者は入力データ(N,A,M)と鍵Kを用いて(C,T)を計算し、(C,T,A,N)を受信者に送る。つまり、Nは暗号化されない。PIV方式では、(N,A,M)と鍵Kを用いて(C,T)を計算する他、Nを暗号化して復元情報RIに変換し、(C,T,A,RI)を受信者に送る。受信者は復号の途中でRIからNを復元する。
【先行技術文献】
【非特許文献】
【００２１】
【非特許文献１】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.
【非特許文献３】Thomas Shrimpton and R. Seth Terashima, \AModular Framework for Building Variable-Input-Length Tweakable Ciphers," ASIACRYPT 2013 , (eds.) Kazue Sako and Palash Sarkar, LNCS, Vol. 8269, pages 405-423, Springer, 2013.
【発明の概要】
【発明が解決しようとする課題】
【００２２】
しかしながら、従来技術のAPEでは、ナンスを利用する場合はA の一部とみなされ、暗号化されずに受信者に送られる。従って、秘密ナンスを利用することができない。また、非特許文献３では、メッセージMとは別にNを暗号化し、復元情報RIを送信する必要がある。そのため、処理量や送信量が大きくなるという問題がある。
【００２３】
本発明は、処理量や送信量を抑えることができる暗号化データ生成装置、復号データ生成装置、追加データ付き認証暗号システム、その方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００２４】
上記の課題を解決するために、本発明の一態様によれば、追加データ付き認証暗号システムは、暗号化データ生成装置と復号データ生成装置とを含む。暗号化データ生成装置は、秘密鍵Kのビット長をcビットとし、rビットのレート部分とcビットのキャパシティ部分とを含むbビットの情報をステートとし、メッセージMのビット長を|M|とし、追加データAのビット長を|A|とし、|Ax|を1以上c/2以下の整数の何れかとし、追加データAを秘匿対象の|Ax|ビット分の値Axと(|A|-|Ax|)ビット分の値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と、値Axと(c-|Ax|)ビット分の所定のビット列gとを連結して得られるビット列Ax||gとの排他的論理和SC,|A'|/r xor Ax||gを計算し、暗号化ステートS|A'|/rのキャパシティ部分SC,|A'|/rを排他的論理和SC,|A'|/r xor Ax||gに置換えたビット列を新たな暗号化ステートS|A'|/rとする境界設定部と、m=1,2,…,|M|/rとし、メッセージMを|M|/r個に分割して得られる各値をMmとし、bビットの暗号化ステートS|A'|/r+m-1のレート部分SR,|A'|/r+m-1のrビットに対し、メッセージMmとの排他的論理和SR,|A'|/r+m-1 xor Mmを求める第二排他的論理和部と、暗号化ステートS|A'|/r+m-1のレート部分SR,|A'|/r+m-1を排他的論理和SR,|A'|/r+m-1 xor Mmに置換えたビット列を置換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'とを出力する出力部を含む。復号データ生成装置は、暗号化データCとタグTと追加データAに含まれる(|A|-|Ax|)ビット分の値A'とを受け取る入力部と、暗号化データ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,…,(|M|/r)-1において、ステートSmのレート部分SR,mと、暗号化データCmとの排他的論理和SR,m xor Cmを復号データMm+1,Dとして出力する第四排他的論理和部と、ステートSmのレート部分SR,mを暗号化データCmに置換えたビット列を逆関数f-1を用いて置換し、ステートSm-1を求める第四置換部と、予め定めたビット列と秘密鍵Kとを連結した値を復号ステートの初期値S0,Dとし、bビットの復号ステートSn-1,Dのレート部分SR,n-1,Dのrビットに対し、値A'nとの排他的論理和SR,n-1,D xor A'nを求める第五排他的論理和部と、復号ステートSn-1,Dのレート部分SR,n-1,Dを排他的論理和SR,n-1,D xor A'nに置換えたビット列を置換fを用いて置換し、復号ステートSn,Dを求める第五置換部と、復号ステートS|A'|/r,Dのキャパシティ部分SC,|A'|/r,Dと、|Ax|ビット分の0からなるビット列と(c-|Ax|)ビット分の所定のビット列gとを連結して得られるビット列00…0||gとの排他的論理和SC,|A'|/r,Dxor 00…0||gを計算し、計算結果により復号ステートS|A'|/r,Dを更新する境界除去部と、更新された復号ステートS|A'|/r,Dのキャパシティ部分SC,|A'|/r,Dのビット列gに対応する部分と、ステートS0のキャパシティ部分SC,0のビット列gに対応する部分とが一致するか否かによりメッセージ認証を行い、一致する場合には、キャパシティ部分SC,|A'|/r,Dの|Ax|ビット分の0からなるビット列に対応する部分と、キャパシティ部分SC,0の|Ax|ビット分の0からなるビット列に対応する部分との排他的論理和をAxとして出力し、復号ステートS|A'|/r,Dのレート部分SR,|A'|/r,DとステートS0のレート部分SR,0との排他的論理和を復号データM1,Dとして出力する認証部とを含む。
【００２５】
上記の課題を解決するために、本発明の他の態様によれば、追加データ付き認証暗号システムは、暗号化データ生成装置と復号データ生成装置とを含む。暗号化データ生成装置は、秘密鍵Kのビット長をcビットとし、rビットのレート部分とcビットのキャパシティ部分とを含むbビットの情報をステートとし、メッセージMのビット長を|M|とし、追加データAのビット長を|A|とし、|Mx|を1以上c/2以下の整数の何れかとし、メッセージMを|Mx|ビット分の値Mxと(|M|-|Mx|)ビット分の値M'とに分割する分割部と、n=1,2,…,|A|/rとし、メッセージAを|A|/r個に分割して得られる各値をAnとし、予め定めたビット列と秘密鍵Kとを連結した値を暗号化ステートの初期値S0とし、bビットの暗号化ステートSn-1のレート部分SR,n-1のrビットに対し、値Anとの排他的論理和SR,n-1 xor Anを求める第一排他的論理和部と、bビットのビット列dをbビットのビット列eに置換する関数を置換fとし、暗号化ステートSn-1のレート部分SR,n-1を排他的論理和SR,n-1 xor Anに置換えたビット列を置換fを用いて置換し、暗号化ステートSnを求める第一置換部と、暗号化ステートS|A|/rのキャパシティ部分SC,|A|/rと、値Mxと(c-|Mx|)ビット分の所定のビット列g2とを連結して得られるビット列Mx||g2との排他的論理和SC,|A|/r xor Mx||g2を計算し、暗号化ステートS|A|/rのキャパシティ部分SC,|A|/rを排他的論理和SC,|A|/r xor Mx||g2に置換えたビット列を新たな暗号化ステートS|A|/rとする境界設定部と、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のレート部分の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とを受け取る入力部と、暗号化データ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,…,(|M'|/r)-1において、ステートSmのレート部分SR,mと、暗号化データCmとの排他的論理和SR,m xor Cmを復号データMm+1,Dとして出力する第四排他的論理和部と、ステートSmのレート部分SR,mを暗号化データCmに置換えたビット列を逆関数f-1を用いて置換し、ステートSm-1を求める第四置換部と、予め定めたビット列と秘密鍵Kとを連結した値を復号ステートの初期値S0,Dとし、bビットの復号ステートSn-1,Dのレート部分SR,n-1,Dのrビットに対し、値Anとの排他的論理和SR,n-1,D xor Anを求める第五排他的論理和部と、復号ステートSn-1,Dのレート部分SR,n-1,Dを排他的論理和SR,n-1,D xor Anに置換えたビット列を置換fを用いて置換し、復号ステートSn,Dを求める第五置換部と、復号ステートS|A|/r,Dのキャパシティ部分SC,|A|/r,Dと、|Mx|ビット分の0からなるビット列と(c-|Mx|)ビット分の所定のビット列g2とを連結して得られるビット列00…0||g2との排他的論理和SC,|A|/r,D xor 00…0||g2を計算し、計算結果により復号ステートS|A|/r,Dを更新する境界除去部と、更新された復号ステートS|A|/r,Dのキャパシティ部分SC,|A|/r,Dのビット列g2に対応する部分と、ステートS0のキャパシティ部分SC,0のビット列g2に対応する部分とが一致するか否かによりメッセージ認証を行い、一致する場合には、キャパシティ部分SC,|A|/r,Dの|Mx|ビット分の0からなるビット列に対応する部分と、キャパシティ部分SC,0の|Mx|ビット分の0からなるビット列に対応する部分との排他的論理和をMxとして出力し、復号ステートS|A|/r,Dのレート部分SR,|A|/r,DとステートS0のレート部分SR,0との排他的論理和を復号データM1,Dとして出力する認証部とを含む。
【発明の効果】
【００２６】
本発明によれば、処理量や送信量を抑えることができるという効果を奏する。
【図面の簡単な説明】
【００２７】
【図１】従来の暗号化関数を説明するための図。
【図２】従来の復号関数を説明するための図。
【図３】追加データ付き認証暗号システムの機能構成を例示する図。
【図４】暗号化装置の機能構成を例示する図。
【図５】追加データ計算部の機能構成を例示する図。
【図６】メッセージ計算部の機能構成を例示する図。
【図７】復号装置の機能構成を例示する図。
【図８】暗号化データ逆計算部の機能構成を例示する図。
【図９】追加データ計算部の機能構成を例示する図。
【図１０】第一実施形態の暗号化方法の処理手続きを例示する図。
【図１１】第一実施形態の暗号化関数の一例を説明するための図。
【図１２】第一実施形態の復号方法の処理手続きを例示する図。
【図１３】第一実施形態の復号関数の一例を説明するための図。
【図１４】第二実施形態の暗号化方法の処理手続きを例示する図。
【図１５】第二実施形態の暗号化関数の一例を説明するための図。
【図１６】第二実施形態の復号方法の処理手続きを例示する図。
【図１７】第二実施形態の復号関数の一例を説明するための図。
【発明を実施するための形態】
【００２８】
以下、本発明の実施形態について、説明する。なお、以下の説明に用いる図面では、同じ機能を持つ構成部や同じ処理を行うステップには同一の符号を記し、重複説明を省略する。
【００２９】
＜第一実施形態＞
この発明の実施形態は、暗号化処理の手順２．において、追加データAの下位c/2ビットの値をキャパシティ部分に排他的論理和する。また、追加データAの下位c/2ビットは受信者に別途送る必要が無く、暗号文CとタグTの中に組み込むことで、受信者が復号の途中で復元する。このような構成とすることで、追加データAの下位c/2ビットを秘密ナンスとして利用し、秘密ナンスを利用できるAPEを実現することができる。
【００３０】
実施形態の追加データ付き認証暗号システムは、図３に示すように、追加データ付き認証暗号の暗号化関数を実行する暗号化装置１と、追加データ付き認証暗号の復号関数を実行する復号装置２とを含む。この実施形態では、暗号化装置１および復号装置２はそれぞれ通信網３へ接続される。通信網３は、接続される各装置が相互に通信可能なように構成された回線交換方式もしくはパケット交換方式の通信網であり、例えばインターネットや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(以下、秘密鍵Kともいう)とが記憶されている。例えば、ステートは512ビットとし、レート部分は256ビット、キャパシティ部分は256ビットに構成する（すなわち、b=512, r=256, c=256）。レート部分とキャパシティ部分の長さの比は、処理速度と安全性のトレードオフの関係となっている。レート部分の長さが大きくなると、処理速度は向上するが安全性は低下する。逆に、キャパシティ部分の長さが大きくなると、安全性が向上するが処理速度が低下する。したがって、b, r, cの各値は、所望の処理速度と安全性のバランスを鑑みて適宜設計すればよい。
【００３７】
＜入力部１１＞
ステップＳ１１において、暗号化装置１の入力部１１へ、追加データAとメッセージMとの組(A, M)が入力される。追加データAとメッセージMとはいずれもr ビットの倍長のデータとする。なお、追加データAとメッセージMとをr ビットの倍長のデータに限定するものではなく、r ビットの倍長ではない場合には、例えば、10*パディングを施して、r ビットの倍長のデータに変更して本実施形態を適用してもよい。入力部１１は、メッセージMをメッセージ計算部１６へ、追加データAを分割部１３へ入力する。
【００３８】
＜初期化部１２＞
ステップＳ１２において、暗号化装置１の初期化部１２は、予め定めたビット列と秘密鍵Kとを連結した値を暗号化ステートの初期値S0として設定する。例えば、初期化部１２は、記憶部１０に記憶されている暗号化ステートのうち、レート部分の値を0（すなわち、すべてのビットが0のビット列）に、キャパシティ部分の値を秘密鍵Kの値に設定して初期化する。
【００３９】
＜分割部１３＞
ステップＳ１３において、暗号化装置１の分割部１３は、入力部１１から追加データAを受け取り、追加データAを秘匿対象の|Ax|ビット分の値Axと(|A|-|Ax|)ビット分の値A'とに分割する。ここで、|Ax|を1以上c/2以下の整数の何れかとする。本実施形態では、|Ax|をc/2とし、追加データAを上位(|A|-(c/2)|)ビット分の値A'と、下位c/2ビット分の値Axとに分割する。値Axを例えば秘密ナンスとして利用することができる。|Ax|と(|A|-|Ax|)との比は、秘密ナンスとして利用できる大きさ(情報量)と安全性のトレードオフの関係となっている。|Ax|が大きくなると、より大きな情報量の秘密ナンスを利用できるが安全性は低下する。逆に、|Ax|が小さくなると、安全性が向上するが情報量が小さくなる。したがって、|Ax|の値は、所望の秘密ナンスの情報量と安全性のバランスを鑑みて適宜設計すればよい。なお、(|A|-|Ax|)ビット分の値A'はr ビットの倍長のデータとする。ただし、値A'をr ビットの倍長のデータに限定するものではなく、r ビットの倍長ではない場合には、例えば、10*パディングを施して、r ビットの倍長のデータに変更して本実施形態を適用してもよい。
【００４０】
＜追加データ計算部１４＞
ステップＳ１４において、暗号化装置１の追加データ計算部１４は、分割部１３から値A'を受け取り、その値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-1 xor 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を、分割部１３から値Axを受け取り、暗号化ステートS|A'|/rのキャパシティ部分SC,|A'|/rと、値Axと(c-|Ax|)ビット分の所定のビット列gとを連結して得られるビット列Ax||gとの排他的論理和SC,|A'|/r xor Ax||gを計算し、暗号化ステートS|A'|/rのキャパシティ部分SC,|A'|/rを排他的論理和SC,|A'|/r xor Ax||gに置換えたビット列を新たな暗号化ステートS|A'|/rとする。本実施形態では、(c-|Ax|)=c/2とし、ビット列gは、1ビットの1、(c/2)-1ビットの0からなるビット列である。本実施形態では、c/2ビットの値Ax、1ビットの1、(c/2)-1ビットの0の順番で上位ビットから連結する。この操作は、受信者が暗号化データCと追加データAとの境界を判別できるようにするために行われるものである。なお、ビット列gは復号処理に先立ち予め暗号化装置１と復号装置２との間であらかじめ共有しておく。
【００４６】
＜メッセージ計算部１６＞
ステップＳ１６において、暗号化装置１のメッセージ計算部１６は、入力部１１からメッセージMを受け取り、そのメッセージMを用いて記憶部１０に記憶された暗号化ステートの値を更新する。
【００４７】
（分割部１６１）
メッセージ計算部１６の分割部１６１は、メッセージMをrビットのブロックに分割する。メッセージMのビット長を|M|とし、m=1,2,…,|M|/rとし、メッセージMを|M|/r個に分割して得られる各値をMmとする。
【００４８】
（排他的論理和部１６２）
メッセージ計算部１６の排他的論理和部１６２は、bビットの暗号化ステートS|A'|/r+m-1のレート部分SR,|A'|/r+m-1のrビットに対し、メッセージMmとの排他的論理和SR,|A'|/r+m-1 xor Mmを求める。
【００４９】
（置換部１６３）
メッセージ計算部１６の置換部１６３は、暗号化ステートS|A'|/r+m-1のレート部分SR,|A'|/r+m-1を排他的論理和SR,|A'|/r+m-1xor Mmに置換えたビット列を置換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をメッセージ計算部１６から受け取り、秘密鍵Kを記憶部１０から取り出し、暗号化ステートS|A'|/r+|M|/rのキャパシティ部分SC,|A'|/r+|M|/rと秘密鍵Kとの排他的論理和を計算し、その計算結果をタグTとして出力する。
【００５１】
＜出力部１８＞
ステップＳ１８において、暗号化装置１の出力部１８は、暗号化データCをメッセージ計算部１６から、タグTをタグ生成部１７から、値A'を分割部から受け取り、暗号化データCとタグTと追加データAに含まれる(|A|-|Ax|)ビット分の値A'との組(C, T, A')を復号装置２へ送信する。
【００５２】
＜復号装置２＞
図１２から図１３を参照して、実施形態の追加データ付き認証暗号システムが実行する追加データ付き認証暗号方法のうち、復号装置２が実行する復号方法について説明する。
【００５３】
＜記憶部２０＞
復号装置２の記憶部２０には、rビットのレート部分とcビットのキャパシティ部分とからなるbビットの2つのステート（以下、暗号化装置１の記憶部１０に記憶される暗号化ステートと区別するために、一方のステートを単にステートと呼び、他方を復号ステートと呼ぶ）と、暗号化装置１との間であらかじめ共有した秘密鍵Kとが記憶されている。b, r, cの各値は、暗号化装置１の記憶部１０に記憶されたステートと同じものとする。
【００５４】
＜入力部２１＞
ステップＳ２１において、復号装置２の入力部２１へ、暗号化装置１から受信した暗号化データCとタグTと追加データAに含まれる(|A|-|Ax|)ビット分の値A'との組(C, T, A')が入力される。本実施形態では、値A'は追加データAに含まれる上位(|A|-(c/2)|)ビット分のデータである。入力部２１は、暗号化データCの最終ブロックとタグTとを第一初期化部２２へ、値A'を追加データ計算部２６へ、暗号化データCの最終ブロック以外の各ブロックを暗号化データ逆計算部２４へそれぞれ入力する。
【００５５】
＜第一初期化部２２＞
ステップＳ２２において、復号装置２の第一初期化部２２は、入力部２１から暗号化データ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-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の逆関数fであり、bビットのビット列eをbビットのビット列dに置換する関数である。
【００５９】
（排他的論理和部２４２）
m=|M|/r-1,(|M|/r)-2,…,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)とする。ただし、復号データM1,D(第一ブロックの暗号化データを復号したもの)は、後述する認証部２９において得られる値を用いる。改ざん等なされていなければM=MDとなる。
【００６０】
＜追加データ計算部２６＞
ステップＳ２６において、復号装置２の追加データ計算部２６は、入力部２１から値A'を受け取り、その値A'を用いて記憶部２０に記憶された復号ステートの値を更新する。この場合、追加データ計算部２６は以下のように構成する。
【００６１】
（分割部２６１）
追加データ計算部２６の分割部２６１は、値A'をrビットのブロックに分割する。なお、値A'のビット長を|A'|とし、n=1,2,…,|A'|/rとし、|A'|/r個に分割された値A'をA'nとする。
【００６２】
（排他的論理和部２６３）
追加データ計算部２６の排他的論理和部２６３は、bビットの復号ステートSn-1,Dのレート部分SR,n-1,Dのrビットに対し、値A'nとの排他的論理和SR,n-1,D xor A'nを求める。なお、復号ステートSn-1,Dの初期値S0,Dは、暗号化装置１で用いた初期値S0と同じ値を用いる。
【００６３】
（置換部２６４）
追加データ計算部２６の置換部２６４は、復号ステートSn-1,Dのレート部分SR,n-1,Dを排他的論理和SR,n-1,Dxor A'nに置換えたビット列を置換fを用いて置換し、復号ステートSn,Dを求める。置換部１６３と同様の方法により置換することができる。
【００６４】
追加データ計算部２６は、n=1から順にn=|A'|/rまで排他的論理和部２６３及び置換部２６４の処理を繰り返す。
【００６５】
＜境界除去部２７＞
ステップＳ２７において、復号装置２の境界除去部２７は、追加データ計算部２６から復号ステートS|A'|/r,Dを受け取り、復号ステートS|A'|/r,Dのキャパシティ部分SC,|A'|/r,Dと、|Ax|ビット分の0からなるビット列と(c-|Ax|)ビット分の所定のビット列gとを連結して得られるビット列00…0||gとの排他的論理和SC,|A'|/r,D xor 00…0||gを計算し、その計算結果により復号ステートS|A'|/r,Dを更新する。なお、本実施形態では、前述の通り、|Ax|=c/2であり、ビット列gは、1ビットの1、(c/2)-1ビットの0からなるビット列である。
【００６６】
＜認証部２９＞
ステップＳ２９において、復号装置２の認証部２９は、境界除去部２７で更新された復号ステートS|A'|/r,Dのキャパシティ部分SC,|A'|/r,D(復号ステートS|A'|/r,Dのキャパシティ部分SC,|A'|/r,Dと、|Ax|ビット分の0からなるビット列と(c-|Ax|)ビット分の所定のビット列gとを連結して得られるビット列00…0||gとの排他的論理和SC,|A'|/r,Dxor 00…0||g)のビット列gに対応する部分と、ステートS0のキャパシティ部分SC,0のビット列gに対応する部分とが一致するか否かによりメッセージ認証を行う。例えば、復号ステートS|A'|/r,DとステートS0とを例えば記憶部２０などに記憶する。その後、記憶部２０に記憶されたSC,|A'|/r,Dのビット列gに対応する部分と、SC,0のビット列gに対応する部分とを比較する。２つの値が等しい場合は、ステップＳ３０１へ処理を進め、復号ステートS|A'|/r,Dのレート部分SR,|A'|/r,DとステートS0のレート部分SR,0との排他的論理和を、復号データMDの第一ブロック(復号データM1,D)として、更新された復号ステートS|A'|/r,Dのキャパシティ部分SC,|A'|/r,Dの|Ax|ビット分の0からなるビット列に対応する部分と、ステートS0のキャパシティ部分SC,0の|Ax|ビット分の0からなるビット列に対応する部分との排他的論理和をAxとして、出力部３０から出力する。二つの値が等しくない場合は、ステップＳ３０２へ処理を進め、復号に失敗した旨を表すエラーコードを出力部３０から出力する。
【００６７】
本実施形態では、復号ステートS|A'|/r,Dのキャパシティ部分SC,|A'|/r,Dの下位c/2ビットと、ステートS0のキャパシティ部分SC,0の下位c/2ビットとを比較し、一致する場合には、復号ステートS|A'|/r,Dのレート部分SR,|A'|/r,DとステートS0のレート部分SR,0との排他的論理和を、復号データM1,Dとして出力し、キャパシティ部分SC,|A'|/r,Dの上位c/2ビットと、ステートS0のキャパシティ部分SC,0の上位c/2ビットとの排他的論理和をAxとして出力する。
【００６８】
＜効果＞
以上の構成により、処理量や送信量を抑えつつ、秘密ナンスを利用できるAPEを実現することができる。また、APEでは、(C,T,A)の全ビットを受信者に送らなければならないため、通信コストが大きいが、本実施形態では、(C,T,A)に代えて、(C,T,A')を送信するため、c/2ビット(|Ax|=|A|-|A'|)分だけ通信コストを抑えることができる。さらに、従来のAPEでは、Aの長さを|A|としたとき、暗号化でAを処理する際に|A|/r回の置換fを計算する必要があり、計算コストが大きいが、本実施形態では、r<c/2の場合、暗号化処理でAxはメッセージの第一ブロックと同時に計算されるため、置換fを計算する回数が減る。これにより、計算コストが改善される。同様に、復号処理ではAではなくA'しか計算されないため、関数fを計算する回数が減る。これにより、計算コストが改善される。
【００６９】
なお、本実施形態に係る暗号化装置のことを暗号化データを生成するという意味で暗号化データ生成装置ともいい、本実施形態に係る復号装置のことを復号データを生成するという意味で復号データ生成装置ともいう。なお、暗号化データ及び復号データは電子計算機による処理の用に供する情報であり、(i)暗号化データ生成装置を用いた暗号化データ生成方法に係る発明及び(ii)復号データ生成装置を用いた復号データ生成方法に係る発明が、特許法第二条第三項第三号の「物を生産する方法の発明」に該当することは言うまでもない。
【００７０】
＜第二実施形態＞
第一実施形態と異なる部分を中心に説明する。
【００７１】
本実施形態では、暗号化処理の手順２．(bビットのステートのうちキャパシティ部分のcビットに対し、整数値1（すなわち、最下位ビットのみが1のビット列）との排他的論理和を計算する)において、メッセージMに含まれる何れかのc/2ビット(この値をMxとする)の値をキャパシティ部分に排他的論理和する。また、値Mxは受信者に別途送る必要が無く、暗号文CとタグTの中に組み込むことで、受信者が復号の途中で復元する。このような構成とすることで、第一実施形態と同様に、処理量や送信量を抑えることができる。つまり、APEでは、メッセージMから生成される暗号化データCを受信者に送らなければならないため、通信コストが大きいが、本実施形態では、値Mxから生成される暗号化データCを送信するため、通信コストを抑えることができる。さらに、従来のAPEでは、Mの長さを|M|としたとき、暗号化でMを処理する際に|M|/r回の置換fを計算する必要があり、計算コストが大きいが、本実施形態では、r<c/2の場合、暗号化処理で値Mxはメッセージの第一ブロックと同時に計算されるため、置換fを計算する回数が減る。これにより、計算コストが改善される。同様に、復号処理ではMではなくM'しか計算されないため、関数fを計算する回数が減る。これにより、計算コストが改善される。
【００７２】
＜暗号化装置１＞
図１４、図１５を参照して、実施形態の追加データ付き認証暗号システムが実行する追加データ付き認証暗号方法のうち、暗号化装置１が実行する暗号化方法について説明する。
【００７３】
＜入力部１１＞
ステップＳ１１において、暗号化装置１の入力部１１へ、追加データAとメッセージMとの組(A, M)が入力される。入力部１１は、メッセージMを分割部１３へ、追加データAを追加データ計算部１４及び出力部１８へ入力する。
【００７４】
＜初期化部１２＞
ステップＳ１２において、暗号化装置１の初期化部１２は、予め定めたビット列と秘密鍵Kとを連結した値を暗号化ステートの初期値S0として設定する。
【００７５】
＜分割部１３＞
ステップＳ１３において、暗号化装置１の分割部１３は、入力部１１からメッセージMを受け取り、メッセージMを|Mx|ビット分の値Mxと(|M|-|Mx|)ビット分の値M'とに分割する。ここで、|Mx|を1以上c/2以下の整数の何れかとする。本実施形態では、|Mx|をc/2とし、メッセージMを上位(|M|-(c/2)|)ビット分の値M'と、下位c/2ビット分の値Mxとに分割する。|Mx|と(|M|-|Mx|)との比は、抑えることができる処理量や送信量と安全性のトレードオフの関係となっている。|Mx|が大きくなると、より大きく処理量や送信量を抑えることができるが安全性は低下する。逆に、|Mx|が小さくなると、安全性が向上するが処理量や送信量を抑える量が小さくなる。したがって、|Mx|の値は、所望の抑制量と安全性のバランスを鑑みて適宜設計すればよい。なお、(|M|-|Mx|)ビット分の値M'はr ビットの倍長のデータとする。ただし、値M'をr ビットの倍長のデータに限定するものではなく、r ビットの倍長ではない場合には、例えば、10*パディングを施して、r ビットの倍長のデータに変更して本実施形態を適用してもよい。
【００７６】
＜追加データ計算部１４＞
ステップＳ１４において、暗号化装置１の追加データ計算部１４は、入力部１１から追加データAを受け取り、追加データAを用いて記憶部１０に記憶された暗号化ステートの値を更新する。この構成は従来技術と同様の方法により実現できる。例えば、追加データ計算部１４は以下のように構成する。
【００７７】
（分割部１４１）
追加データ計算部１４の分割部１４１は、追加メッセージAをrビットのブロックに分割する。なお、追加メッセージAのビット長を|A|とし、n=1,2,…,|A|/rとし、追加メッセージAを|A|/r個に分割して得られる各値をAnとする。
【００７８】
（排他的論理和部１４２）
追加データ計算部１４の排他的論理和部１４２は、bビットのステートSn-1のレート部分SR,n-1のrビットに対し、値Anとの排他的論理和SR,n-1 xor Anを求める。
【００７９】
（置換部１４３）
追加データ計算部１４の置換部１４３は、暗号化ステートSn-1のレート部分SR,n-1を排他的論理和SR,n-1 xor Anに置換えたビット列を置換fを用いて置換し、暗号化ステートSnを求める。n=1から順にn=|A|/rまで排他的論理和部１４２及び置換部１４３の処理を繰り返す。
【００８０】
＜境界設定部１５＞
ステップＳ１５において、暗号化装置１の境界設定部１５は、追加データ計算部１４から暗号化ステートS|A|/rを、分割部１３から値Mxを受け取り、暗号化ステートS|A|/rのキャパシティ部分SC,|A|/rと、値Mxと(c-|Mx|)ビット分の所定のビット列g2とを連結して得られるビット列Mx||g2との排他的論理和SC,|A|/r xor Mx||g2を計算し、暗号化ステートS|A|/rのキャパシティ部分SC,|A|/rを排他的論理和SC,|A|/r xor Mx||g2に置換えたビット列を新たな暗号化ステートS|A|/rとする。本実施形態では、(c-|Mx|)=c/2とし、ビット列g2は、1ビットの1、(c/2)-1ビットの0からなるビット列である。本実施形態では、c/2ビットの値Mx、1ビットの1、(c/2)-1ビットの0の順番で上位ビットから連結する。なお、ビット列g2は復号処理に先立ち予め暗号化装置１と復号装置２との間であらかじめ共有しておく。
【００８１】
＜メッセージ計算部１６＞
ステップＳ１６において、暗号化装置１のメッセージ計算部１６は、分割部１３から値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をメッセージ計算部１６から受け取り、秘密鍵Kを記憶部１０から取り出し、暗号化ステートS|A|/r+|M'|/rのキャパシティ部分SC,|A|/r+|M'|/rと秘密鍵Kとの排他的論理和を計算し、その計算結果をタグTとして出力する。
【００８６】
＜出力部１８＞
ステップＳ１８において、暗号化装置１の出力部１８は、暗号化データCをメッセージ計算部１６から、タグTをタグ生成部１７から、追加データAを入力部１１から受け取り、暗号化データCとタグTと追加データAとの組(C, T, A)を復号装置２へ送信する。
【００８７】
＜復号装置２＞
図１６から図１７を参照して、実施形態の追加データ付き認証暗号システムが実行する追加データ付き認証暗号方法のうち、復号装置２が実行する復号方法について説明する。
【００８８】
＜入力部２１＞
ステップＳ２１において、復号装置２の入力部２１へ、暗号化装置１から受信した暗号化データCとタグTと追加データAとの組(C, T, A)が入力される。入力部２１は、暗号化データCの最終ブロックとタグTとを第一初期化部２２へ、追加データAを追加データ計算部２６へ、暗号化データCの最終ブロック以外の各ブロックを暗号化データ逆計算部２４へそれぞれ入力する。
【００８９】
＜第一初期化部２２＞
ステップＳ２２において、復号装置２の第一初期化部２２は、入力部２１から暗号化データ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-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を求める。
【００９３】
（排他的論理和部２４２）
m=|M'|/r-1,(|M'|/r)-2,…,2,1において、暗号化データ逆計算部２４の排他的論理和部２４２は、ステートSmのレート部分SR,mと、暗号化データCmとの排他的論理和SR,m xor Cmを計算し、計算結果を復号データMm+1,Dとして出力部３０から出力する。なお、((|M'|/r)+1)個の復号データMm,Dを結合したものを最終的に出力する復号データMD=(MxD||M1,D||M2,D||…||M|M'|/r,D)とする。ただし、復号データMxD,M1,D(第一ブロックの暗号化データを復号したもの)は、後述する認証部２９において得られる値を用いる。改ざん等なされていなければM=MDとなる。
【００９４】
＜追加データ計算部２６＞
ステップＳ２６において、復号装置２の追加データ計算部２６は、入力部２１から追加データAを受け取り、その追加データAを用いて記憶部２０に記憶された復号ステートの値を更新する。この場合、追加データ計算部２６は以下のように構成する。
【００９５】
（分割部２６１）
追加データ計算部２６の分割部２６１は、追加データAをrビットのブロックに分割する。なお、追加データAのビット長を|A|とし、n=1,2,…,|A|/rとし、|A|/r個に分割された追加データAを値Anとする。
【００９６】
（排他的論理和部２６３）
追加データ計算部２６の排他的論理和部２６３は、bビットの復号ステートSn-1,Dのレート部分SR,n-1,Dのrビットに対し、値Anとの排他的論理和SR,n-1,D xor Anを求める。なお、復号ステートSn-1,Dの初期値S0,Dは、暗号化装置１で用いた初期値S0と同じ値を用いる。
【００９７】
（置換部２６４）
追加データ計算部２６の置換部２６４は、復号ステートSn-1,Dのレート部分SR,n-1,Dを排他的論理和SR,n-1,Dxor Anに置換えたビット列を置換fを用いて置換し、復号ステートSn,Dを求める。置換部１６３と同様の方法により置換することができる。
【００９８】
追加データ計算部２６は、n=1から順にn=|A|/rまで排他的論理和部２６３及び置換部２６４の処理を繰り返す。
【００９９】
＜境界除去部２７＞
ステップＳ２７において、復号装置２の境界除去部２７は、追加データ計算部２６から復号ステートS|A|/r,Dを受け取り、復号ステートS|A|/r,Dのキャパシティ部分SC,|A|/r,Dと、|Mx|ビット分の0からなるビット列と(c-|Mx|)ビット分の所定のビット列g2とを連結して得られるビット列00…0||g2との排他的論理和SC,|A|/r,Dxor 00…0||g2を計算し、その計算結果により復号ステートS|A|/r,Dを更新する。なお、本実施形態では、前述の通り、|Mx|=c/2であり、ビット列g2は、1ビットの1、(c/2)-1ビットの0からなるビット列である。
【０１００】
＜認証部２９＞
ステップＳ２９において、復号装置２の認証部２９は、境界除去部２７で更新された復号ステートS|A|/r,Dのキャパシティ部分SC,|A|/r,D(復号ステートS|A|/r,Dのキャパシティ部分SC,|A|/r,Dと、|Mx|ビット分の0からなるビット列と(c-|Mx|)ビット分の所定のビット列g2とを連結して得られるビット列00…0||g2との排他的論理和SC,|A|/r,D xor 00…0||g2)のビット列g2に対応する部分と、ステートS0のキャパシティ部分SC,0のビット列g2に対応する部分とが一致するか否かによりメッセージ認証を行う。例えば、復号ステートS|A|/r,DとステートS0とを例えば記憶部２０などに記憶する。その後、記憶部２０に記憶されたSC,|A|/r,Dのビット列g2に対応する部分と、SC,0のビット列g2に対応する部分とを比較する。２つの値が等しい場合は、ステップＳ３０１へ処理を進め、復号ステートS|A|/r,Dのレート部分SR,|A|/r,DとステートS0のレート部分SR,0との排他的論理和を、復号データMDの第一ブロック(復号データM1,D)として、更新された復号ステートS|A|/r,Dのキャパシティ部分SC,|A|/r,Dの|Mx|ビット分の0からなるビット列に対応する部分と、ステートS0のキャパシティ部分SC,0の|Mx|ビット分の0からなるビット列に対応する部分との排他的論理和をMxとして、出力部３０から出力する。二つの値が等しくない場合は、ステップＳ３０２へ処理を進め、復号に失敗した旨を表すエラーコードを出力部３０から出力する。
【０１０１】
本実施形態では、復号ステートS|A|/r,Dのキャパシティ部分SC,|A|/r,Dの下位c/2ビットと、ステートS0のキャパシティ部分SC,0の下位c/2ビットとを比較し、一致する場合には、復号ステートS|A|/r,Dのレート部分SR,|A|/r,DとステートS0のレート部分SR,0との排他的論理和を、復号データM1,Dとして出力し、キャパシティ部分SC,|A|/r,Dの上位c/2ビットと、ステートS0のキャパシティ部分SC,0の上位c/2ビットとの排他的論理和をMxとして出力する。
【０１０２】
＜効果＞
以上の構成により、第一実施形態と同様に、処理量や送信量を抑えることができる。
【０１０３】
＜その他の変形例＞
本発明は上記の実施形態及び変形例に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。
【０１０４】
＜プログラム及び記録媒体＞
また、上記の実施形態及び変形例で説明した各装置における各種の処理機能をコンピュータによって実現してもよい。その場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【０１０５】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１０６】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させてもよい。
【０１０７】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶部に格納する。そして、処理の実行時、このコンピュータは、自己の記憶部に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実施形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよい。さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、プログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１０８】
また、コンピュータ上で所定のプログラムを実行させることにより、各装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【図１】
2019015918.tif 000003
【図２】
2019015918.tif 000004
【図３】
2019015918.tif 000005
【図４】
2019015918.tif 000006
【図５】
2019015918.tif 000007
【図６】
2019015918.tif 000008
【図７】
2019015918.tif 000009
【図８】
2019015918.tif 000010
【図９】
2019015918.tif 000011
【図１０】
2019015918.tif 000012
【図１１】
2019015918.tif 000013
【図１２】
2019015918.tif 000014
【図１３】
2019015918.tif 000015
【図１４】
2019015918.tif 000016
【図１５】
2019015918.tif 000017
【図１６】
2019015918.tif 000018
【図１７】
2019015918.tif 000019