(57)【特許請求の範囲】
【請求項１】
暗号化装置と復号装置を有する暗号化システムであって、
Ｋを前記暗号化装置と前記復号装置の両方で共有する秘密鍵、Ａを追加認証データ、Ｍをメッセージ、Ｃを暗号文、Ｔをタグ、Ｋ，Ａ，Ｍをビット列、Ｎをすべてのビットが“０”のビット列を除くビット列、ｒ，ｃ，ｂ，Ｐ，Ｑを１以上の整数、ｂ＝ｒ＋ｃ、ｐを１以上Ｐ以下の整数、ｑを１以上Ｑ以下の整数、Ｓをあらかじめ定めた１以上の整数、ｓを１以上Ｓ以下の整数、ｆをｂビットの置換演算、ｇを恒等写像を除くｃビットの置換演算とし、
ステートを、あらかじめ定められたｒビットがレート部分、ｃビットがキャパシティ部分であるｂビットのビット列とし、
前記暗号化装置は、
Ｎを選択し、ＮとＫを用いてｂビットの暗号化用第１初期値と前記暗号化用第１初期値とは異なるｂビットの暗号化用第２初期値を生成し、前記暗号化用第１初期値をｆにより置換した結果を第１ステートとし、前記暗号化用第２初期値をｆにより置換した結果を第２ステートとする暗号化用初期値設定部と、
メッセージＭを、パディングを用いてｒビットごとのメッセージブロックｍ１，…，ｍＰに分割するメッセージ分割部と、
（１）第１ステートのレート部分に対してメッセージブロックｍｐとの排他的論理和を計算し、計算結果をｒビットの暗号ブロックｄｐとするとともに、第１ステートのレート部分を当該計算結果に置き換えた上でｆにより置換した結果を新たな第１ステートとする処理を、ｐ＝１からｐ＝Ｐ−１まで繰り返し、
（２）第１ステートのレート部分に対してメッセージブロックｍＰとの排他的論理和を計算し、計算結果をｒビットの暗号ブロックｄＰとするともに、第１ステートのレート部分を当該計算結果に置き換え、キャパシティ部分をｇにより置換した上で、ｆにより置換した結果を新たな第１ステートとする処理を行い、
（３）暗号ブロックｄ１，…，ｄＰの結合処理を用いて暗号文Ｃを求め、
（４）Ｓ＝１の場合は第１ステートのレート部分からメッセージタグＴＭを求め、Ｓ≧２の場合は、第１ステートのレート部分をメッセージタグブロックｔＭ１とし、さらに、第１ステートをｆにより置換した結果を新たな第１ステートとしてレート部分をメッセージタグブロックｔＭｓとする処理をｓ＝２からｓ＝Ｓまで繰り返し、メッセージタグブロックｔＭ１，…，ｔＭＳを用いてメッセージタグＴＭを求める
暗号化部と、
追加認証データＡを、パディングを用いてｂビットごとの追加認証データブロックａ１，…，ａＱに分割する暗号化用追加認証データ分割部と、
第２ステートに対して追加認証データブロックａｑとの排他的論理和を計算し、さらにｆにより置換した結果を新たな第２ステートとする処理を、ｑ＝１からｑ＝Ｑまで繰り返し、Ｓ＝１の場合は第２ステートのレート部分からメッセージタグＴＭを求め、Ｓ≧２の場合は、第２ステートのレート部分を追加認証データタグブロックｔＡ１とし、さらに、第２ステートをｆにより置換した結果を新たな第２ステートとしてレート部分を追加認証データタグブロックｔＡｓとする処理をｓ＝２からｓ＝Ｓまで繰り返し、追加認証データタグブロックｔＡ１，…，ｔＡＳを用いて追加認証データタグＴＡを求める暗号化用追加認証データタグ計算部と、
メッセージタグＴＭと追加認証データタグＴＡとの排他的論理和を用いてタグＴを求める暗号化用タグ計算部と、
Ｃ，Ｔ，Ａ，Ｎの組を出力する出力部と、
を備え、
前記復号装置は、
Ｃ，Ｔ，Ａ，Ｎの組を取得する入力部と、
ＮとＫを用いてｂビットの復号用第１初期値と前記復号用第１初期値とは異なるｂビットの復号用第２初期値を生成し、前記復号用第１初期値をｆにより置換した結果を第１ステートとし、前記復号用第２初期値をｆにより置換した結果を第２ステートとする復号用初期値設定部と、
暗号文Ｃを、ｒビットごとの暗号ブロックｄ１，…，ｄＰに分割する暗号文分割部と、
（１）第１ステートのレート部分に対して暗号ブロックｄｐとの排他的論理和を計算し、計算結果をｒビットのメッセージブロックｍｐ’とするとともに、第１ステートのレート部分を暗号ブロックｄｐに置き換えた上でｆにより置換した結果を新たな第１ステートとする処理を、ｐ＝１からｐ＝Ｐ−１まで繰り返し、
（２）第１ステートのレート部分に対して暗号ブロックｄＰとの排他的論理和を計算し、計算結果をｒビットのメッセージブロックｍＰ’とするともに、第１ステートのレート部分を暗号ブロックｄＰに置き換え、キャパシティ部分をｇにより置換した上で、ｆにより置換した結果を新たな第１ステートとする処理を行い、
（３）メッセージブロックｍ１’，…，ｍＰ’からパディングで付加されたビットを取り除いた結合をしてメッセージＭ’とし、
（４）Ｓ＝１の場合は第１ステートのレート部分からメッセージタグＴＭ’を求め、Ｓ≧２の場合は、第１ステートのレート部分をメッセージタグブロックｔＭ１’とし、さらに、第１ステートをｆにより置換した結果を新たな第１ステートとしてレート部分をメッセージタグブロックｔＭｓ’とする処理をｓ＝２からｓ＝Ｓまで繰り返し、メッセージタグブロックｔＭ１’，…，ｔＭＳ’を用いてメッセージタグＴＭ’を求める
復号部と、
追加認証データＡを、パディングを用いてｂビットごとの追加認証データブロックａ１，…，ａＱに分割する復号用追加認証データ分割部と、
第２ステートに対して追加認証データブロックａｑとの排他的論理和を計算し、さらにｆにより置換した結果を新たな第２ステートとする処理を、ｑ＝１からｑ＝Ｑまで繰り返し、Ｓ＝１の場合は第２ステートのレート部分からメッセージタグＴＭ’を求め、Ｓ≧２の場合は、第２ステートのレート部分を追加認証データタグブロックｔＡ１’とし、さらに、第２ステートをｆにより置換した結果を新たな第２ステートとしてレート部分を追加認証データタグブロックｔＡｓ’とする処理をｓ＝２からｓ＝Ｓまで繰り返し、追加認証データタグブロックｔＡ１’，…，ｔＡＳ’を用いて追加認証データタグＴＡ’を求める復号用追加認証データタグ計算部と、
メッセージタグＴＭ’と追加認証データタグＴＡ’との排他的論理和を用いてタグＴ’を求める復号用タグ計算部と、
タグＴとタグＴ’とを比較する検証部と
を備える
暗号化システム。
【請求項２】
請求項１記載の暗号化システムであって、
前記暗号化用初期値設定部は、暗号化用第１初期値として、レート部分にＮを埋め込み、キャパシティ部分にＫを埋め込み、暗号化用第２初期値として、レート部分にゼロを埋め込み、キャパシティ部分にＫを埋め込み、
前記復号用初期値設定部は、復号用第１初期値として、レート部分にＮを埋め込み、キャパシティ部分にＫを埋め込み、復号用第２初期値として、レート部分にゼロを埋め込み、キャパシティ部分にＫを埋め込む
ことを特徴とする暗号化システム。
【請求項３】
請求項１または２記載の暗号化システムであって、
置換演算ｇは、（ｃ−１）個の“０”と１個の“１”からなるビット数ｃのビット列との排他的論理和である
ことを特徴とする暗号化システム。
【請求項４】
Ｋを前記暗号化装置と前記復号装置の両方で共有する秘密鍵、Ａを追加認証データ、Ｍをメッセージ、Ｃを暗号文、Ｔをタグ、Ｋ，Ａ，Ｍをビット列、Ｎをすべてのビットが“０”のビット列を除くビット列、ｒ，ｃ，ｂ，Ｐ，Ｑを１以上の整数、ｂ＝ｒ＋ｃ、ｐを１以上Ｐ以下の整数、ｑを１以上Ｑ以下の整数、Ｓをあらかじめ定めた１以上の整数、ｓを１以上Ｓ以下の整数、ｆをｂビットの置換演算、ｇを恒等写像を除くｃビットの置換演算とし、
ステートを、あらかじめ定められたｒビットがレート部分、ｃビットがキャパシティ部分であるｂビットのビット列とし、
Ｎを選択し、ＮとＫを用いてｂビットの第１初期値と前記第１初期値とは異なるｂビットの第２初期値を生成し、前記第１初期値をｆにより置換した結果を第１ステートとし、前記第２初期値をｆにより置換した結果を第２ステートとする初期値設定部と、
メッセージＭを、パディングを用いてｒビットごとのメッセージブロックｍ１，…，ｍＰに分割するメッセージ分割部と、
（１）第１ステートのレート部分に対してメッセージブロックｍｐとの排他的論理和を計算し、計算結果をｒビットの暗号ブロックｄｐとするとともに、第１ステートのレート部分を当該計算結果に置き換えた上でｆにより置換した結果を新たな第１ステートとする処理を、ｐ＝１からｐ＝Ｐ−１まで繰り返し、
（２）第１ステートのレート部分に対してメッセージブロックｍＰとの排他的論理和を計算し、計算結果をｒビットの暗号ブロックｄＰとするともに、第１ステートのレート部分を当該計算結果に置き換え、キャパシティ部分をｇにより置換した上で、ｆにより置換した結果を新たな第１ステートとする処理を行い、
（３）暗号ブロックｄ１，…，ｄＰの結合処理を用いて暗号文Ｃを求め、
（４）Ｓ＝１の場合は第１ステートのレート部分からメッセージタグＴＭを求め、Ｓ≧２の場合は、第１ステートのレート部分をメッセージタグブロックｔＭ１とし、さらに、第１ステートをｆにより置換した結果を新たな第１ステートとしてレート部分をメッセージタグブロックｔＭｓとする処理をｓ＝２からｓ＝Ｓまで繰り返し、メッセージタグブロックｔＭ１，…，ｔＭＳを用いてメッセージタグＴＭを求める
暗号化部と、
追加認証データＡを、パディングを用いてｂビットごとの追加認証データブロックａ１，…，ａＱに分割する暗号化用追加認証データ分割部と、
第２ステートに対して追加認証データブロックａｑとの排他的論理和を計算し、さらにｆにより置換した結果を新たな第２ステートとする処理を、ｑ＝１からｑ＝Ｑまで繰り返し、Ｓ＝１の場合は第２ステートのレート部分からメッセージタグＴＭを求め、Ｓ≧２の場合は、第２ステートのレート部分を追加認証データタグブロックｔＡ１とし、さらに、第２ステートをｆにより置換した結果を新たな第２ステートとしてレート部分を追加認証データタグブロックｔＡｓとする処理をｓ＝２からｓ＝Ｓまで繰り返し、追加認証データタグブロックｔＡ１，…，ｔＡＳを用いて追加認証データタグＴＡを求める暗号化用追加認証データタグ計算部と、
メッセージタグＴＭと追加認証データタグＴＡとの排他的論理和を用いてタグＴを求める暗号化用タグ計算部と、
Ｃ，Ｔ，Ａ，Ｎの組を出力する出力部と
を備える暗号化装置。
【請求項５】
Ｋを前記暗号化装置と前記復号装置の両方で共有する秘密鍵、Ａを追加認証データ、Ｍをメッセージ、Ｃを暗号文、Ｔをタグ、Ｋ，Ａ，Ｍをビット列、Ｎをすべてのビットが“０”のビット列を除くビット列、ｒ，ｃ，ｂ，Ｐ，Ｑを１以上の整数、ｂ＝ｒ＋ｃ、ｐを１以上Ｐ以下の整数、ｑを１以上Ｑ以下の整数、Ｓをあらかじめ定めた１以上の整数、ｓを１以上Ｓ以下の整数、ｆをｂビットの置換演算、ｇを恒等写像を除くｃビットの置換演算とし、
ステートを、あらかじめ定められたｒビットがレート部分、ｃビットがキャパシティ部分であるｂビットのビット列とし、
Ｃ，Ｔ，Ａ，Ｎの組を取得する入力部と
ＮとＫを用いてｂビットの第１初期値と前記第１初期値とは異なるｂビットの第２初期値を生成し、前記第１初期値をｆにより置換した結果を第１ステートとし、前記第２初期値をｆにより置換した結果を第２ステートとする初期値設定部と、
暗号文Ｃを、ｒビットごとの暗号ブロックｄ１，…，ｄＰに分割する暗号文分割部と、
（１）第１ステートのレート部分に対して暗号ブロックｄｐとの排他的論理和を計算し、計算結果をｒビットのメッセージブロックｍｐ’とするとともに、第１ステートのレート部分を暗号ブロックｄｐに置き換えた上でｆにより置換した結果を新たな第１ステートとする処理を、ｐ＝１からｐ＝Ｐ−１まで繰り返し、
（２）第１ステートのレート部分に対して暗号ブロックｄＰとの排他的論理和を計算し、計算結果をｒビットのメッセージブロックｍＰ’とするともに、第１ステートのレート部分を暗号ブロックｄＰに置き換え、キャパシティ部分をｇにより置換した上で、ｆにより置換した結果を新たな第１ステートとする処理を行い、
（３）メッセージブロックｍ１’，…，ｍＰ’からパディングで付加されたビットを取り除いた結合をしてメッセージＭ’とし、
（４）Ｓ＝１の場合は第１ステートのレート部分からメッセージタグＴＭ’を求め、Ｓ≧２の場合は、第１ステートのレート部分をメッセージタグブロックｔＭ１’とし、さらに、第１ステートをｆにより置換した結果を新たな第１ステートとしてレート部分をメッセージタグブロックｔＭｓ’とする処理をｓ＝２からｓ＝Ｓまで繰り返し、メッセージタグブロックｔＭ１’，…，ｔＭＳ’を用いてメッセージタグＴＭ’を求める
復号部と、
追加認証データＡを、パディングを用いてｂビットごとの追加認証データブロックａ１，…，ａＱに分割する復号用追加認証データ分割部と、
第２ステートに対して追加認証データブロックａｑとの排他的論理和を計算し、さらにｆにより置換した結果を新たな第２ステートとする処理を、ｑ＝１からｑ＝Ｑまで繰り返し、Ｓ＝１の場合は第２ステートのレート部分からメッセージタグＴＭ’を求め、Ｓ≧２の場合は、第２ステートのレート部分を追加認証データタグブロックｔＡ１’とし、さらに、第２ステートをｆにより置換した結果を新たな第２ステートとしてレート部分を追加認証データタグブロックｔＡｓ’とする処理をｓ＝２からｓ＝Ｓまで繰り返し、追加認証データタグブロックｔＡ１’，…，ｔＡＳ’を用いて追加認証データタグＴＡ’を求める復号用追加認証データタグ計算部と、
メッセージタグＴＭ’と追加認証データタグＴＡ’との排他的論理和を用いてタグＴ’を求める復号用タグ計算部と、
タグＴとタグＴ’とを比較する検証部と
を備える復号装置。
【請求項６】
暗号化装置と復号装置とで実行する暗号化方法であって、
Ｋを前記暗号化装置と前記復号装置の両方で共有する秘密鍵、Ａを追加認証データ、Ｍをメッセージ、Ｃを暗号文、Ｔをタグ、Ｋ，Ａ，Ｍをビット列、Ｎをすべてのビットが“０”のビット列を除くビット列、ｒ，ｃ，ｂ，Ｐ，Ｑを１以上の整数、ｂ＝ｒ＋ｃ、ｐを１以上Ｐ以下の整数、ｑを１以上Ｑ以下の整数、Ｓをあらかじめ定めた１以上の整数、ｓを１以上Ｓ以下の整数、ｆをｂビットの置換演算、ｇを恒等写像を除くｃビットの置換演算とし、
ステートを、あらかじめ定められたｒビットがレート部分、ｃビットがキャパシティ部分であるｂビットのビット列とし、
前記暗号化装置が、
Ｎを選択し、ＮとＫを用いてｂビットの暗号化用第１初期値と前記暗号化用第１初期値とは異なるｂビットの暗号化用第２初期値を生成し、前記暗号化用第１初期値をｆにより置換した結果を第１ステートとし、前記暗号化用第２初期値をｆにより置換した結果を第２ステートとする暗号化用初期値設定ステップと、
メッセージＭを、パディングを用いてｒビットごとのメッセージブロックｍ１，…，ｍＰに分割するメッセージ分割ステップと、
（１）第１ステートのレート部分に対してメッセージブロックｍｐとの排他的論理和を計算し、計算結果をｒビットの暗号ブロックｄｐとするとともに、第１ステートのレート部分を当該計算結果に置き換えた上でｆにより置換した結果を新たな第１ステートとする処理を、ｐ＝１からｐ＝Ｐ−１まで繰り返し、
（２）第１ステートのレート部分に対してメッセージブロックｍＰとの排他的論理和を計算し、計算結果をｒビットの暗号ブロックｄＰとするともに、第１ステートのレート部分を当該計算結果に置き換え、キャパシティ部分をｇにより置換した上で、ｆにより置換した結果を新たな第１ステートとする処理を行い、
（３）暗号ブロックｄ１，…，ｄＰの結合処理を用いて暗号文Ｃを求め、
（４）Ｓ＝１の場合は第１ステートのレート部分からメッセージタグＴＭを求め、Ｓ≧２の場合は、第１ステートのレート部分をメッセージタグブロックｔＭ１とし、さらに、第１ステートをｆにより置換した結果を新たな第１ステートとしてレート部分をメッセージタグブロックｔＭｓとする処理をｓ＝２からｓ＝Ｓまで繰り返し、メッセージタグブロックｔＭ１，…，ｔＭＳを用いてメッセージタグＴＭを求める
暗号化ステップと、
追加認証データＡを、パディングを用いてｂビットごとの追加認証データブロックａ１，…，ａＱに分割する暗号化用追加認証データ分割ステップと、
第２ステートに対して追加認証データブロックａｑとの排他的論理和を計算し、さらにｆにより置換した結果を新たな第２ステートとする処理を、ｑ＝１からｑ＝Ｑまで繰り返し、Ｓ＝１の場合は第２ステートのレート部分からメッセージタグＴＭを求め、Ｓ≧２の場合は、第２ステートのレート部分を追加認証データタグブロックｔＡ１とし、さらに、第２ステートをｆにより置換した結果を新たな第２ステートとしてレート部分を追加認証データタグブロックｔＡｓとする処理をｓ＝２からｓ＝Ｓまで繰り返し、追加認証データタグブロックｔＡ１，…，ｔＡＳを用いて追加認証データタグＴＡを求める暗号化用追加認証データタグ計算ステップと、
メッセージタグＴＭと追加認証データタグＴＡとの排他的論理和を用いてタグＴを求める暗号化用タグ計算ステップと、
Ｃ，Ｔ，Ａ，Ｎの組を出力する出力ステップと、
を実行し、
前記復号装置が、
Ｃ，Ｔ，Ａ，Ｎの組を取得する入力ステップと、
ＮとＫを用いてｂビットの復号用第１初期値と前記復号用第１初期値とは異なるｂビットの復号用第２初期値を生成し、前記復号用第１初期値をｆにより置換した結果を第１ステートとし、前記復号用第２初期値をｆにより置換した結果を第２ステートとする復号用初期値設定ステップと、
暗号文Ｃを、ｒビットごとの暗号ブロックｄ１，…，ｄＰに分割する暗号文分割ステップと、
（１）第１ステートのレート部分に対して暗号ブロックｄｐとの排他的論理和を計算し、計算結果をｒビットのメッセージブロックｍｐ’とするとともに、第１ステートのレート部分を暗号ブロックｄｐに置き換えた上でｆにより置換した結果を新たな第１ステートとする処理を、ｐ＝１からｐ＝Ｐ−１まで繰り返し、
（２）第１ステートのレート部分に対して暗号ブロックｄＰとの排他的論理和を計算し、計算結果をｒビットのメッセージブロックｍＰ’とするともに、第１ステートのレート部分を暗号ブロックｄＰに置き換え、キャパシティ部分をｇにより置換した上で、ｆにより置換した結果を新たな第１ステートとする処理を行い、
（３）メッセージブロックｍ１’，…，ｍＰ’からパディングで付加されたビットを取り除いた結合をしてメッセージＭ’とし、
（４）Ｓ＝１の場合は第１ステートのレート部分からメッセージタグＴＭ’を求め、Ｓ≧２の場合は、第１ステートのレート部分をメッセージタグブロックｔＭ１’とし、さらに、第１ステートをｆにより置換した結果を新たな第１ステートとしてレート部分をメッセージタグブロックｔＭｓ’とする処理をｓ＝２からｓ＝Ｓまで繰り返し、メッセージタグブロックｔＭ１’，…，ｔＭＳ’を用いてメッセージタグＴＭ’を求める
復号ステップと、
追加認証データＡを、パディングを用いてｂビットごとの追加認証データブロックａ１，…，ａＱに分割する復号用追加認証データ分割ステップと、
第２ステートに対して追加認証データブロックａｑとの排他的論理和を計算し、さらにｆにより置換した結果を新たな第２ステートとする処理を、ｑ＝１からｑ＝Ｑまで繰り返し、Ｓ＝１の場合は第２ステートのレート部分からメッセージタグＴＭ’を求め、Ｓ≧２の場合は、第２ステートのレート部分を追加認証データタグブロックｔＡ１’とし、さらに、第２ステートをｆにより置換した結果を新たな第２ステートとしてレート部分を追加認証データタグブロックｔＡｓ’とする処理をｓ＝２からｓ＝Ｓまで繰り返し、追加認証データタグブロックｔＡ１’，…，ｔＡＳ’を用いて追加認証データタグＴＡ’を求める復号用追加認証データタグ計算ステップと、
メッセージタグＴＭ’と追加認証データタグＴＡ’との排他的論理和を用いてタグＴ’を求める復号用タグ計算ステップと、
タグＴとタグＴ’とを比較する検証ステップと
を実行する
暗号化方法。
【請求項７】
請求項４記載の暗号化装置としてコンピュータを機能させるための暗号化プログラム。
【請求項８】
請求項５記載の復号装置としてコンピュータを機能させるための復号プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、追加認証データ付きの認証暗号を実行する暗号化システム、暗号化装置、復号装置、暗号化方法、暗号化プログラム、復号プログラムに関する。
【背景技術】
【０００２】
追加認証データ付認証暗号とは、メッセージＭの秘匿および、Ｍと追加認証データＡの認証（改ざん検知）を同時に行う共通鍵暗号プリミティブである。暗号化関数と復号関数の２つの関数から構成される。追加認証データ認証暗号では、受信者と送信者はあらかじめ秘密の鍵Ｋを共有しておく。送信者は、メッセージＭ、追加認証データＡに加えて、暗号化関数を呼び出すたびに変化する値（ナンスと呼ばれる）Ｎを選択する。暗号化関数は、Ｍ，Ａ，Ｎに対応する暗号文ＣとタグＴを生成し、（Ｃ，Ｔ，Ａ，Ｎ）の組を受信者に送る。受信者は（Ｃ，Ｔ，Ａ，Ｎ）を受け取るが、この時点でこれらの値が悪意ある第三者によって改ざんされていないという保証がない。受信者は受け取った（Ｃ，Ｔ，Ａ，Ｎ）と自分が保有するＫを用いて復号関数を計算する。復号関数は、メッセージＭ’とタグＴ’を計算する。計算して得られたＴ’と受信したＴが同じ値であれば、受け取った（Ｃ，Ｔ，Ａ，Ｎ）は正しい値であると判断し、復号されたメッセージとしてＭ’を出力する。Ｔ≠Ｔ’であれば、復号に失敗した（データが改ざんされた）という結果を出力する。
【０００３】
非特許文献１に記載されているSPONGEWRAPは、認証暗号の暗号化関数と復号関数の構成法である。保証したい安全性レベル(ビット数)に比べて比較的大きなサイズの置換（bijective map）を用いて暗号化関数、復号関数を構成するという特徴を持つ。
【０００４】
＜SPONGEWRAP＞
SPONGEWRAPの暗号化関数は、ステートと呼ばれるｂビットのデータを、ｂビットの置換ｆ：｛０，１｝ｂ→｛０，１｝ｂと入力データ（Ｎ，Ａ，Ｍ）と鍵Ｋを用いて繰り返しアップデートを行いながらＣとＴを計算する。またｂビットのステートは、レートと呼ばれるｒビットと、キャパシティと呼ばれるｃ（＝ｂ−ｒ）ビットに分割される。暗号化関数の計算の際、ステートの値は予め定められた初期値ＩＶと呼ばれるｂビットの値に初期化され（例えばＩＶ＝０）、ｆによりｂビットの置換が行われ、ステートが更新される。暗号化関数の具体的な計算手順は以下の手順１から手順４で説明される通りである。図１に、SPONGEWRAPの暗号化での計算構造を示す。
【０００５】
＜手順１＞
鍵Ｋをｒ−１ビット毎に分割する。最終ブロックでは１０＊パディングと呼ばれるパディング処理を施す。具体的には、最終ブロックのビット長がｒ−１ビットより短い場合には、１ビットの値“１”を与し、その後ｒ−１ビットになるまでビット“０”を付与する。最終ブロックのビット長が丁度ｒ−１ビットの場合には、次のブロックの先頭のビットとして 1 ビットの値“１”を与し、その後ｒ−１ビットになるまでビット“０”を付与する。
【０００６】
Ｋをｒ−１ビット毎に分割したそれぞれの値に、フレームビットと呼ばれる１ビットの値を連結し、ｒビットにする。具体的には、最初のブロックから最終ブロックの一つ手前のブロックまではフレームビットを“０”とし、最終ブロックのみフレームビットを“１”とする。ｂビットのステートのうちレート部分のｒビットに対し、Ｋとフレームビットを連結したｒビットの値との排他的論理和を計算し、置換ｆを計算する。ｆの出力を新たなステート値とする。この操作をＫの最終ブロックが排他的論理和されるまで続ける。なお、この処理まではあらかじめ行っておくことができるので、手順１までを初期化と呼んでもよい。
【０００７】
＜手順２＞
ナンスＮと追加認証データＡを連結し、ｒ−１ビット毎に分割する。最終ブロックに対しては１０＊パディングを施す。ＮとＡの連結をｒ−１ビット毎に分割したそれぞれの値に、１ビットのフレームビットを連結し、ｒビットにする。具体的には、最初のブロックから最終ブロックの一つ手前のブロックまではフレームビットを“０”とし、最終ブロックのみフレームビットを“１”とする。ｂビットのステートのうち、レート部分のｒビットに対し、ＮもしくはＡとフレームビットを連結した ｒビットの値との排他的論理和を計算し、置換ｆを計算する。ｆの出力を新たなステート値とする。この操作をＮ，Ａの最終ブロックが排他的論理和されるまで続ける。
【０００８】
＜手順３＞
メッセージＭをｒ−１ビット毎に分割する。最終ブロックに対しては１０＊パディングを施す。Ｍの連結をｒ−１ビット毎に分割したそれぞれの値に、１ビットのフレームビットを連結し、ｒビットにする。具体的には、最初のブロックから最終ブロックの一つ手前のブロックまではフレームビットを“１”とし、最終ブロックのみフレームビットを“０”とする。
【０００９】
ｂビットのステートのうち、レート部分のｒビットに対し、Ｍとフレームビットを連結した r ビットの値との排他的論理和を計算する。計算された ｒビットを暗号文のｒビットとして出力する。ステートに対し置換ｆを計算し、ｆの出力を新たなステート値とする。この操作をＭの最終ブロックが排他的論理和されるまで続ける。Ｍのサイズがｒの倍数でない場合、最終ブロックは端数分のみを暗号文として出力し、ステートに排他的論理和する。
【００１０】
＜手順４＞
ｂビットのステートのうち、レート部分のｒビットをタグのｒビットとして出力する。ステートに対し置換ｆを計算し、ｆの出力を新たなステート値とする。この操作をタグのビット数に達するまで続ける。タグ長がｒの倍数でない場合、最後のｒビットの出力を必要な端数に切り捨ててタグの出力とする。
【００１１】
＜復号＞
SPONGEWRAPの復号関数は、暗号化関数とほぼ同様の計算を行う。図２に、SPONGEWRAPの復号での計算構造を示す。ステートはＩＶに初期化され、暗号化関数の手順１，２同じ処理を行う。手順３は暗号化関数と異なっており、ｂビットのステートのうち、レート部分のｒビットとＣのｒビットの排他的論理和をとり、パディングやフレームビット付与の逆手順を通した値をＭ’のｒ−１ビットとする。ｂビットのステートのうち、レート部分のｒビットをＣのｒビットに置き換え、置換ｆを計算する。ｆの出力を新たなステート値とする。この操作をＣの最終ブロックが排他的論理和されるまで続ける。Ｃの最終ブロックのサイズがｒの倍数でない場合、端数分のみをＭ’の生成とステートの置き換えに利用する。手順３終了後、暗号化関数の手順４と同じ処理を行い、タグＴ’を得る。計算したＴ’と受け取ったＴを比較し、同じ値であればＭ’を復号されたメッセージとして出力する。一致しなかった場合は、復号に失敗したという結果を出力する。
【００１２】
＜donkeySponge＞
非特許文献２に示されたdonkeySpongeは、SPONGEWRAPの追加認証データ処理部分を利用してメッセージ認証コードを計算する方法である。図３にdonkeySpongeの計算構造を示す。メッセージ認証コードを生成する目的では、鍵Ｋおよび入力Ａをｂビットステートの全ビットに排他的論理和をしても安全性を損なうことが無く、効率的に入力データを処理することができる。
【００１３】
＜monkeyDuplex＞
非特許文献２に示されたmonkeyDuplexは、SPONGEWRAPのＫとＮの処理方法に工夫を加え、より効率的な計算を可能にする方法である。Ｋのｃビットまでを、ＩＶのｃビットのキャパシティ部分とする。もしくは、Ｋのｃビットまでと、別に定義されたｃビット定数との排他的論理和をＩＶのｃビットのキャパシティ部分とする。いずれの方法も、暗号化関数，復号関数で手順 １（Ｋの処理）におけるｆの計算関数を少なくすることができるため、計算効率が上昇する。なお、Ｋがｃビットに満たない場合、適切なパディングによりＩＶのｃビットがすべて定義されるようにする。
【００１４】
また、Ｎのｒビットまでを、ＩＶのｒビットのレート部分とする。もしくは、Ｎのｒビットまでと、別に定義されたｒビット定数との排他的論理和をＩＶのｒビットのレート部分とする。手順２におけるｆの計算関数を少なくすることができるため、計算効率が上昇する。なお、Ｎがｒビットに満たない場合、適切なパディングによりＩＶのｒビットがすべて定義されるようにする。monkeyDuplexによるステートの初期化およびＫ，Ｎの処理を図 ４に示す。
【００１５】
＜ciphertext translation＞
非特許文献３に示されたciphertext translationはSPONGEWRAPとは異なり、ブロック暗号をベースに設計された追加認証データ付認証暗号で追加認証データＡを処理する汎用的な方法である。タグ長さをｔとする。ciphertext translationでは、メッセージＭのみに依存する暗号文Ｃおよびメッセージ部のタグＴＭの計算と、追加認証データＡのみに依存するｔビットのタグＴＡを独立に計算する。最後に、ＣおよびＴＭから任意のｔビットを選び、ＴＡとの排他的論理和の結果をタグＴとして出力する。
【００１６】
ciphertext translationではＴＡの計算に利用する鍵Ｋ１と、ＴＭの計算に利用する鍵Ｋ２、合計２つの互いに独立な鍵を利用する。ciphertext translationを用いると、Ｍの処理とＡの処理に依存関係がなくなり、ＭとＡがどんな順番で送られてきても、受信者がデータ受け取った瞬間に復号処理を始めることが可能になる。
【先行技術文献】
【非特許文献】
【００１７】
【非特許文献１】Guido Bertoni, Joan Daemen, Michael Peeters and Gilles Van  Assche,“Duplexing the Sponge: Single-Pass Authenticated Encryption and Other Applications”, SAC 2011, (eds.) Ali Miri and Serge Vaudenay, LNCS, Vol. 7118, pages 320-337, Springer, 2012.
【非特許文献２】Guido Bertoni, Joan Daemen, Michael Peeters and Gilles Van Assche,“Permutation-based encryption, authentication and authenticated encryption”, Workshop Records of DIAC 2012.
【非特許文献３】Phillip Rogaway,“Authenticated-encryption with associated-data”, ACM CCS 2002, (ed.) Vijayalakshmi Atluri, pages 98-107, ACM, 2002.
【発明の概要】
【発明が解決しようとする課題】
【００１８】
しかしながら、SPONGEWRAPでは、手順２で追加認証データＡの処理が終わってから手順３でメッセージＭの処理を開始する。Ａを全部送信する前にＭの送信を始める通信プロトコルにおいては、Ｍを受け取っても計算を始められないことになり、無駄が生じる。また、SPONGEWRAPでは、手順１，２，３において、各ブロックでフレームビットを連結するためにレートのｒビット中、ｒ−１ビットまでしか入力データを処理できず非効率である。さらに、ciphertext translationでは、２つの互いに独立な鍵を用いる必要があり、非効率である。
【００１９】
本発明は、上述の状況に鑑み、任意の順番で送信されるＭ，Ａに対して、データを受信後即座に処理を開始できること、各ブロックの処理の効率を１ビット向上させること、計算に必要な鍵の個数を１個にすることを目的とする。
【課題を解決するための手段】
【００２０】
本発明の暗号化システムは、暗号化装置と復号装置を有する。まず、Ｋを暗号化装置と復号装置の両方で共有する秘密鍵、Ａを追加認証データ、Ｍをメッセージ、Ｃを暗号文、Ｔをタグ、Ｋ，Ａ，Ｍをビット列、Ｎをすべてのビットが“０”のビット列を除くビット列、ｒ，ｃ，ｂ，Ｐ，Ｑを１以上の整数、ｂ＝ｒ＋ｃ、ｐを１以上Ｐ以下の整数、ｑを１以上Ｑ以下の整数、Ｓをあらかじめ定めた１以上の整数、ｓを１以上Ｓ以下の整数、ｆをｂビットの置換演算、ｇを恒等写像を除くｃビットの置換演算とする。また、ステートを、あらかじめ定められたｒビットがレート部分、ｃビットがキャパシティ部分であるｂビットのビット列とする。
【００２１】
暗号化装置は、暗号化用初期値設定部、メッセージ分割部、暗号化部、暗号化用追加認証データ分割部、暗号化用追加認証データタグ計算部、暗号化用タグ計算部、出力部を備える。暗号化用初期値設定部は、ナンスＮを選択し、ＮとＫを用いてｂビットの暗号化用第１初期値と暗号化用第１初期値とは異なるｂビットの暗号化用第２初期値を生成し、暗号化用第１初期値をｆにより置換した結果を第１ステートとし、暗号化用第２初期値をｆにより置換した結果を第２ステートとする。メッセージ分割部は、メッセージＭを、パディングを用いてｒビットごとのメッセージブロックｍ１，…，ｍＰに分割する。
【００２２】
暗号化部は、次の（１）〜（４）の処理を行う。
【００２３】
（１）第１ステートのレート部分に対してメッセージブロックｍｐとの排他的論理和を計算し、計算結果をｒビットの暗号ブロックｄｐとするとともに、第１ステートのレート部分を当該計算結果に置き換えた上でｆにより置換した結果を新たな第１ステートとする処理を、ｐ＝１からｐ＝Ｐ−１まで繰り返す。
【００２４】
（２）第１ステートのレート部分に対してメッセージブロックｍＰとの排他的論理和を計算し、計算結果をｒビットの暗号ブロックｄＰとするともに、第１ステートのレート部分を当該計算結果に置き換え、キャパシティ部分をｇにより置換した上で、ｆにより置換した結果を新たな第１ステートとする処理を行う。
【００２５】
（３）暗号ブロックｄ１，…，ｄＰの結合処理を用いて暗号文Ｃを求める。
【００２６】
（４）Ｓ＝１の場合は第１ステートのレート部分からメッセージタグＴＭを求める。Ｓ≧２の場合は、第１ステートのレート部分をメッセージタグブロックｔＭ１とし、さらに、第１ステートをｆにより置換した結果を新たな第１ステートとし、レート部分をメッセージタグブロックｔＭｓとする処理を、ｓ＝２からｓ＝Ｓまで繰り返し、メッセージタグブロックｔＭ１，…，ｔＭＳを用いてメッセージタグＴＭを求める。
【００２７】
暗号化用追加認証データ分割部は、追加認証データＡを、パディングを用いてｂビットごとの追加認証データブロックａ１，…，ａＱに分割する。暗号化用追加認証データタグ計算部は、第２ステートに対して追加認証データブロックａｑとの排他的論理和を計算し、さらにｆにより置換した結果を新たな第２ステートとする処理を、ｑ＝１からｑ＝Ｑまで繰り返す。暗号化用追加認証データタグ計算部は、Ｓ＝１の場合は第２ステートのレート部分からメッセージタグＴＭを求める。暗号化用追加認証データタグ計算部は、Ｓ≧２の場合は、第２ステートのレート部分を追加認証データタグブロックｔＡ１とする。Ｓ≧２の場合はさらに、第２ステートをｆにより置換した結果を新たな第２ステートとし、レート部分を追加認証データタグブロックｔＡｓとする処理を、ｓ＝２からｓ＝Ｓまで繰り返し、追加認証データタグブロックｔＡ１，…，ｔＡＳを用いて追加認証データタグＴＡを求める。暗号化用タグ計算部は、メッセージタグＴＭと追加認証データタグＴＡとの排他的論理和を用いてタグＴを求める。出力部は、Ｃ，Ｔ，Ａ，Ｎの組を出力する。
【００２８】
復号装置は、入力部、復号用初期値設定部、暗号文分割部、復号部、復号用追加認証データ分割部、復号用追加認証データタグ計算部、復号用タグ計算部、検証部を備える。入力部は、Ｃ，Ｔ，Ａ，Ｎの組を取得する。復号用初期値設定部は、ＮとＫを用いてｂビットの復号用第１初期値と復号用第１初期値とは異なるｂビットの復号用第２初期値を生成し、復号用第１初期値をｆにより置換した結果を第１ステートとし、復号用第２初期値をｆにより置換した結果を第２ステートとする。暗号文分割部は、暗号文Ｃを、ｒビットごとの暗号ブロックｄ１，…，ｄＰに分割する。
【００２９】
復号部は、次の（１）〜（４）の処理を行う。
【００３０】
（１）第１ステートのレート部分に対して暗号ブロックｄｐとの排他的論理和を計算し、計算結果をｒビットのメッセージブロックｍｐ’とするとともに、第１ステートのレート部分を暗号ブロックｄｐに置き換えた上でｆにより置換した結果を新たな第１ステートとする処理を、ｐ＝１からｐ＝Ｐ−１まで繰り返す。
【００３１】
（２）第１ステートのレート部分に対して暗号ブロックｄＰとの排他的論理和を計算し、計算結果をｒビットのメッセージブロックｍＰ’とするともに、第１ステートのレート部分を暗号ブロックｄＰに置き換え、キャパシティ部分をｇにより置換した上で、ｆにより置換した結果を新たな第１ステートとする処理を行う。
【００３２】
（３）メッセージブロックｍ１’，…，ｍＰ’からパディングで付加されたビットを取り除いた結合をしてメッセージＭ’とする。
【００３３】
（４）Ｓ＝１の場合は第１ステートのレート部分からメッセージタグＴＭ’を求め、Ｓ≧２の場合は、第１ステートのレート部分をメッセージタグブロックｔＭ１’とし、さらに、第１ステートをｆにより置換した結果を新たな第１ステートとし、レート部分をメッセージタグブロックｔＭｓ’とする処理を、ｓ＝２からｓ＝Ｓまで繰り返し、メッセージタグブロックｔＭ１’，…，ｔＭＳ’を用いてメッセージタグＴＭ’を求める。
【００３４】
復号用追加認証データ分割部は、追加認証データＡを、パディングを用いてｂビットごとの追加認証データブロックａ１，…，ａＱに分割する。復号用追加認証データタグ計算部は、第２ステートに対して追加認証データブロックａｑとの排他的論理和を計算し、さらにｆにより置換した結果を新たな第２ステートとする処理を、ｑ＝１からｑ＝Ｑまで繰り返す。復号用追加認証データタグ計算部は、Ｓ＝１の場合は第２ステートのレート部分からメッセージタグＴＭ’を求める。復号用追加認証データタグ計算部は、Ｓ≧２の場合は、第２ステートのレート部分を追加認証データタグブロックｔＡ１’とする。Ｓ≧２の場合はさらに、第２ステートをｆにより置換した結果を新たな第２ステートとしてレート部分を追加認証データタグブロックｔＡｓ’とする処理をｓ＝２からｓ＝Ｓまで繰り返し、追加認証データタグブロックｔＡ１’，…，ｔＡＳ’を用いて追加認証データタグＴＡ’を求める。復号用タグ計算部は、メッセージタグＴＭ’と追加認証データタグＴＡ’との排他的論理和を用いてタグＴ’を求める。検証部は、タグＴとタグＴ’とを比較する。
【発明の効果】
【００３５】
本発明の暗号化システムによれば、任意の順番で送信されるＭ，Ａに対して、データを受信後即座に処理を開始できる。よって、従来技術よりも広い範囲のプロトコルで演算効率を保つことができる。また、各ブロックの処理の効率を１ビット向上させることができる。さらに、計算に必要な鍵の個数を２個から１個に減らし、システムの鍵管理コストを削減できる。
【図面の簡単な説明】
【００３６】
【図１】SPONGEWRAPの暗号化での計算構造を示す図。
【図２】SPONGEWRAPの復号での計算構造を示す図。
【図３】donkeySpongeの計算構造を示す図。
【図４】monkeyDuplexによるステートの初期化およびＫ，Ｎの処理を示す図。
【図５】本発明の暗号化システムの機能構成例を示す図。
【図６】本発明の暗号化での計算構造の例を示す図。
【図７】本発明の復号での計算構造の例を示す図。
【図８】本発明の暗号化装置の処理フローを示す図。
【図９】本発明の復号装置の処理フローを示す図。
【発明を実施するための形態】
【００３７】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【実施例１】
【００３８】
図５に本発明の暗号化システムの機能構成例を示す。図６は本発明の暗号化での計算構造の例を示す図、図７は本発明の復号での計算構造の例を示す図である。また、図８は本発明の暗号化装置の処理フロー、図９は本発明の復号装置の処理フローを示す図である。本発明の暗号化システムは、ネットワーク８００を介して接続された暗号化装置１００と復号装置２００で構成される。まず、Ｋを暗号化装置１００と復号装置２００の両方で共有する秘密鍵、Ａを追加認証データ、Ｍをメッセージ、Ｃを暗号文、Ｔをタグとする。本発明では、Ｋ，Ａ，Ｍ，Ｃ，Ｔ，Ｎはビット列で表現される。なお、Ｎはすべてのビットが“０”のビット列を除くビット列である。タグＴはあらかじめビット数ＬＴが定められている。ｒ，ｃ，ｂ，Ｐ，Ｑを１以上の整数、ｂ＝ｒ＋ｃ、ｐを１以上Ｐ以下の整数、ｑを１以上Ｑ以下の整数、Ｓをあらかじめ定めた１以上の整数、ｓを１以上Ｓ以下の整数、ｆをｂビットの置換演算、ｇを恒等写像を除くｃビットの置換演算とする。また、ステートを、あらかじめ定められたｒビットがレート部分、ｃビットがキャパシティ部分であるｂビットのビット列とする。
【００３９】
＜暗号化装置＞
暗号化装置１００は、初期値設定部１１０、メッセージ分割部１２０、暗号化部１３０、追加認証データ分割部１４０、追加認証データタグ計算部１５０、タグ計算部１６０、出力部１９０を備える。初期値設定部１１０は、ナンスＮとなるビット列をすべてのビットが“０”のビット列以外から選択する。そして、初期値設定部１１０は、ＮとＫを用いてｂビットの第１初期値と第１初期値とは異なるｂビットの第２初期値を生成し、第１初期値をｆにより置換した結果を第１ステートとし、第２初期値をｆにより置換した結果を第２ステートとする（Ｓ１１０）。例えば、初期値設定部１１０は、第１初期値として、レート部分にＮを埋め込み、キャパシティ部分にＫを埋め込み、第２初期値として、レート部分にゼロを埋め込み、キャパシティ部分にＫを埋め込めばよい。「埋め込む」とは、例えば、Ｎのビット数がｒより小さいときはパディングによってｒビットにした上でレート部分にすることを意味している。また、Ｎのビット数がｒよりも大きい場合はＮからｒビットを切り出す、もしくはハッシュ関数などを用いてｒビットに変換してレート部分にしてもよい。ｆはSPONGEWRAPで説明した置換と同じであり、あらかじめ暗号化装置１００と復号装置２００との間で定めておく。図６では、１１０を付した点線で囲まれた部分が初期値設定部に相当する。
【００４０】
メッセージ分割部１２０は、メッセージＭを、パディングを用いてｒビットごとのメッセージブロックｍ１，…，ｍＰに分割する（Ｓ１２０）。パディングとしては、例えば１０＊パディングを用いればよい。図６では、１２０を付した点線で囲まれた部分がメッセージ分割部に相当する。
【００４１】
暗号化部１３０は、次の（１）〜（４）の処理を行う（Ｓ１３０）。図６では、１３０を付した点線で囲まれた部分が暗号化部に相当する。
【００４２】
（１）第１ステートのレート部分に対してメッセージブロックｍｐとの排他的論理和を計算し、計算結果をｒビットの暗号ブロックｄｐとするとともに、第１ステートのレート部分を当該計算結果に置き換えた上でｆにより置換した結果を新たな第１ステートとする処理を、ｐ＝１からｐ＝Ｐ−１まで繰り返す。「排他的論理和」はビット単位の排他的論理和であり、同じ位置のビット同士の排他的論理和を行う演算である。例えば、ビット列“１０１００”とビット列“００１１０”との排他的論理和の結果は“１００１０”である。
【００４３】
（２）第１ステートのレート部分に対してメッセージブロックｍＰとの排他的論理和を計算し、計算結果をｒビットの暗号ブロックｄＰとするともに、第１ステートのレート部分を当該計算結果に置き換え、キャパシティ部分をｇにより置換した上で、ｆにより置換した結果を新たな第１ステートとする処理を行う。ｇは恒等写像を除くｃビットの置換演算であり、例えば、（ｃ−１）個の“０”と１個の“１”からなるビット数ｃのビット列との排他的論理和をｇとしてもよい。
【００４４】
（３）暗号ブロックｄ１，…，ｄＰの結合処理を用いて暗号文Ｃを求める。「結合処理を用いて暗号文Ｃを求める」とは、単に暗号ブロックｄ１，…，ｄＰを結合して暗号文Ｃとすること、および、結合した上でパディング部分を取り除いて暗号文Ｃとすることを含み意味である。
【００４５】
（４）Ｓ＝１の場合は第１ステートのレート部分からメッセージタグＴＭを求める。Ｓ≧２の場合は、第１ステートのレート部分をメッセージタグブロックｔＭ１とする。Ｓ≧２の場合はさらに、第１ステートをｆにより置換した結果を新たな第１ステートとし、レート部分をメッセージタグブロックｔＭｓとする処理を、ｓ＝２からｓ＝Ｓまで繰り返す。そして、メッセージタグブロックｔＭ１，…，ｔＭＳを用いてメッセージタグＴＭを求める。Ｓ＝１の場合は、レート部分をそのままメッセージタグＴＭとしてもよいし、レート部の中からビット数ＬＴだけを切り出してメッセージタグＴＭとしてもよい。Ｓ≧２の場合は、例えば、メッセージタグブロックｔＭ１，…，ｔＭＳを結合した結果をメッセージタグＴＭとしてもよいし、メッセージタグブロックｔＭ１，…，ｔＭＳを結合した結果からビット数ＬＴよりも多いビット分を切り捨てて（ビット数ＬＴ分を切り出して）メッセージタグＴＭとしてもよい。また、各メッセージタグブロックｔＭｓから所定のビットを切り出した後、それらを結合してメッセージタグＴＭとしてもよい。なお、Ｓは、ｒ×ＳがタグＴのビット数ＬＴ以上となるようにあらかじめ定めておけばよい。
【００４６】
追加認証データ分割部１４０は、追加認証データＡを、パディングを用いてｂビットごとの追加認証データブロックａ１，…，ａＱに分割する（Ｓ１４０）。パディングとしては、例えば１０＊パディングを用いればよい。図６では、１４０を付した点線で囲まれた部分が追加認証データ分割部に相当する。
【００４７】
追加認証データタグ計算部１５０は、第２ステートに対して追加認証データブロックａｑとの排他的論理和を計算し、さらにｆにより置換した結果を新たな第２ステートとする処理を、ｑ＝１からｑ＝Ｑまで繰り返す。追加認証データタグ計算部１５０は、Ｓ＝１の場合は第２ステートのレート部分から追加認証データタグＴＡを求め、Ｓ≧２の場合は、第２ステートのレート部分を追加認証データタグブロックｔＡ１とする。追加認証データタグ計算部１５０は、Ｓ≧２の場合はさらに、第２ステートをｆにより置換した結果を新たな第２ステートとし、レート部分を追加認証データタグブロックｔＡｓとする処理を、ｓ＝２からｓ＝Ｓまで繰り返す。そして、追加認証データタグブロックｔＡ１，…，ｔＡＳを用いて追加認証データタグＴＡを求める（Ｓ１５０）。図６では、１５０を付した点線で囲まれた部分が追加認証データタグ計算部に相当する。Ｓ＝１の場合、レート部分をそのまま追加認証データタグＴＡとしてもよいし、レート部の中からビット数ＬＴだけを切り出して追加認証データタグＴＡとしてもよい。Ｓ≧２の場合は、例えば、追加認証データタグブロックｔＡ１，…，ｔＡＳを結合した結果を追加認証データタグＴＡとしてもよいし、追加認証データタグブロックｔＡ１，…，ｔＡＳを結合した結果からビット数ＬＴよりも多いビット分を切り捨てて（ビット数ＬＴ分を切り出して）追加認証データタグＴＡとしてもよい。また、各追加認証データタグブロックｔＡｓから所定のビットを切り出した後、それらを結合して追加認証データタグＴＡとしてもよい。
【００４８】
タグ計算部１６０は、メッセージタグＴＭと追加認証データタグＴＡとの排他的論理和を用いてタグＴを求める（Ｓ１６０）。メッセージタグＴＭと追加認証データタグＴＡのビット数がそれぞれＬＴのときは、単にメッセージタグＴＭと追加認証データタグＴＡの排他的論理和の演算を行えばよい。メッセージタグＴＭと追加認証データタグＴＡのビット数がＬＴよりも多いときは、排他的論理和の演算の後でＬＴ分のビットを切り出してもいいし、両方からＬＴ分のビットを切り出したのちに排他的論理和の演算を行ってもよい。「排他的論理和を用いて」とは、上述のいくつかのパターンを含むための表現である。図６では、１６０を付した点線で囲まれた部分がタグ計算部に相当する。出力部１９０は、Ｃ，Ｔ，Ａ，Ｎの組を出力する（Ｓ１９０）。出力されたＣ，Ｔ，Ａ，Ｎの組が復号装置２００に送信される。
【００４９】
＜復号装置＞
復号装置２００は、入力部２９０、初期値設定部２１０、暗号文分割部２２０、復号部２３０、追加認証データ分割部２４０、追加認証データタグ計算部２５０、タグ計算部２６０、検証部２７０を備える。入力部２９０は、暗号化装置１００が送信したＣ，Ｔ，Ａ，Ｎの組を取得する（Ｓ２９０）。
【００５０】
初期値設定部２１０は、ＮとＫを用いてｂビットの第１初期値と第１初期値とは異なるｂビットの第２初期値を生成し、第１初期値をｆにより置換した結果を第１ステートとし、第２初期値をｆにより置換した結果を第２ステートとする（Ｓ２１０）。例えば、初期値設定部２１０は、第１初期値として、レート部分にＮを埋め込み、キャパシティ部分にＫを埋め込み、復号用第２初期値として、レート部分にゼロを埋め込み、キャパシティ部分にＫを埋め込めばよい。「埋め込む」とは、例えば、Ｎのビット数がｒより小さいときはパディングによってｒビットにした上でレート部分にすることを意味している。また、Ｎのビット数がｒよりも大きい場合はＮからｒビットを切り出す、もしくはハッシュ関数などを用いてｒビットに変換してレート部分にしてもよい。図７では、２１０を付した点線で囲まれた部分が初期値設定部に相当する。
【００５１】
暗号文分割部２２０は、暗号文Ｃを、ｒビットごとの暗号ブロックｄ１，…，ｄＰに分割する（Ｓ２２０）。暗号文Ｃのビット数がｒの整数倍でないときは、パディングによってｒビットごとの暗号ブロックに分割すればよい。図７では、２２０を付した点線で囲まれた部分が暗号文分割部に相当する。
【００５２】
復号部２３０は、次の（１）〜（４）の処理を行う（Ｓ２３０）。図７では、２３０を付した点線で囲まれた部分が復号部に相当する。
【００５３】
（１）第１ステートのレート部分に対して暗号ブロックｄｐとの排他的論理和を計算し、計算結果をｒビットのメッセージブロックｍｐ’とするとともに、第１ステートのレート部分を暗号ブロックｄｐに置き換えた上でｆにより置換した結果を新たな第１ステートとする処理を、ｐ＝１からｐ＝Ｐ−１まで繰り返す。ここでの「排他的論理和」もビット単位の排他的論理和であり、同じ位置のビット同士の排他的論理和を行う演算である。
【００５４】
（２）第１ステートのレート部分に対して暗号ブロックｄＰとの排他的論理和を計算し、計算結果をｒビットのメッセージブロックｍＰ’とするともに、第１ステートのレート部分を暗号ブロックｄＰに置き換え、キャパシティ部分をｇにより置換した上で、ｆにより置換した結果を新たな第１ステートとする処理を行う。ｇは暗号化装置１００で用いたｃビットの置換演算と同じである。
【００５５】
（３）メッセージブロックｍ１’，…，ｍＰ’からパディングで付加されたビットを取り除いた結合をしてメッセージＭ’とする。
【００５６】
（４）Ｓ＝１の場合は第１ステートのレート部分からメッセージタグＴＭ’を求め、Ｓ≧２の場合は、第１ステートのレート部分をメッセージタグブロックｔＭ１’とする。Ｓ≧２の場合はさらに、第１ステートをｆにより置換した結果を新たな第１ステートとし、レート部分をメッセージタグブロックｔＭｓ’とする処理を、ｓ＝２からｓ＝Ｓまで繰り返す。そして、メッセージタグブロックｔＭ１’，…，ｔＭＳ’を用いてメッセージタグＴＭ’を求める。Ｓ＝１の場合は、レート部分をそのままメッセージタグＴＭ’としてもよいし、レート部の中からビット数ＬＴだけを切り出してメッセージタグＴＭ’としてもよい。Ｓ≧２の場合は、例えば、メッセージタグブロックｔＭ１’，…，ｔＭＳ’を結合した結果をメッセージタグＴＭ’としてもよいし、メッセージタグブロックｔＭ１’，…，ｔＭＳ’を結合した結果からビット数ＬＴよりも多いビット分を切り捨てて（ビット数ＬＴ分を切り出して）メッセージタグＴＭ’としてもよい。また、各メッセージタグブロックｔＭｓ’から所定のビットを切り出した後、それらを結合してメッセージタグＴＭ’としてもよい。いずれの場合も、暗号化装置１００の暗号化部１３０と同じ方法でメッセージタグＴＭ’を求める。
【００５７】
追加認証データ分割部２４０は、追加認証データＡを、パディングを用いてｂビットごとの追加認証データブロックａ１，…，ａＱに分割する（Ｓ２４０）。パディングとしては、例えば１０＊パディングを用いればよい。図７では、２４０を付した点線で囲まれた部分が追加認証データ分割部に相当する。
【００５８】
追加認証データタグ計算部２５０は、第２ステートに対して追加認証データブロックａｑとの排他的論理和を計算し、さらにｆにより置換した結果を新たな第２ステートとする処理を、ｑ＝１からｑ＝Ｑまで繰り返す。追加認証データタグ計算部２５０は、Ｓ＝１の場合は第２ステートのレート部分からメッセージタグＴＭ’を求め、Ｓ≧２の場合は、第２ステートのレート部分を追加認証データタグブロックｔＡ１’とする。Ｓ≧２の場合はさらに、第２ステートをｆにより置換した結果を新たな第２ステートとし、レート部分を追加認証データタグブロックｔＡｓ’とする処理を、ｓ＝２からｓ＝Ｓまで繰り返す。そして、追加認証データタグブロックｔＡ１’，…，ｔＡＳ’を用いて追加認証データタグＴＡ’を求める（Ｓ２５０）。図７では、２５０を付した点線で囲まれた部分が追加認証データタグ計算部に相当する。Ｓ＝１の場合、レート部分をそのままメッセージタグＴＭ’としてもよいし、レート部の中からビット数ＬＴだけを切り出してメッセージタグＴＭとしてもよい。Ｓ≧２の場合は、例えば、追加認証データタグブロックｔＡ１，…，ｔＡＳを結合した結果を追加認証データタグＴＡとしてもよいし、追加認証データタグブロックｔＡ１，…，ｔＡＳを結合した結果からビット数ＬＴよりも多いビット分を切り捨てて（ビット数ＬＴ分を切り出して）追加認証データタグＴＡとしてもよい。また、各追加認証データタグブロックｔＡｓから所定のビットを切り出した後、それらを結合して追加認証データタグＴＡとしてもよい。
【００５９】
タグ計算部２６０は、メッセージタグＴＭ’と追加認証データタグＴＡ’との排他的論理和を用いてタグＴ’を求める（Ｓ２６０）。メッセージタグＴＭ’と追加認証データタグＴＡ’のビット数がそれぞれＬＴのときは、単にメッセージタグＴＭ’と追加認証データタグＴＡ’の排他的論理和の演算を行えばよい。メッセージタグＴＭ’と追加認証データタグＴＡ’のビット数がＬＴよりも多いときは、排他的論理和の演算の後でＬＴ分のビットを切り出してもいいし、両方からＬＴ分のビットを切り出したのちに排他的論理和の演算を行ってもよい。図７では、２６０を付した点線で囲まれた部分がタグ計算部に相当する。検証部２７０は、タグＴとタグＴ’とを比較する（Ｓ２７０）。Ｔ＝Ｔ’のときはメッセージＭ’を復号されたメッセージとする。Ｔ≠Ｔ’のときは復号に失敗したという結果を出力する。
【００６０】
＜効果＞
本発明の暗号化システムによれば、メッセージＭの処理と追加認証データＡの処理とが別々に実行されるフローなので、任意の順番で送信されるＭ，Ａに対して、データを受信後即座に処理を開始できる。よって、従来技術よりも広い範囲のプロトコルで演算効率を保つことができる。また、SPONGEWRAPでは追加認証データＡの処理とメッセージＭの処理とが連続して実行されていたので、追加認証データＡの処理とメッセージＭの処理とを区別するためにフレームビットが必要であった。しかし、本発明の暗号化システムでは、メッセージＭの処理と追加認証データＡの処理とが別々に実行されるので、フレームビットが必要ない。よって、暗号化部や復号部でのｒビット単位の処理において、ｒビットすべてをメッセージＭや暗号文Ｃのために使用できる。したがって、各ブロックでの処理の効率を１ビット向上させる。さらに、フレームビットを必要としないことにより、演算構造を単純化できるので、実装者が実装を誤る可能性を低くできる。さらに、初期値設定部１１０，２１０の工夫により、ciphertext translationでは必要だった鍵の個数を２個から１個に減らすことができるので、システムの鍵管理コストを削減できる。
【００６１】
［プログラム、記録媒体］
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００６２】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【００６３】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００６４】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００６５】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００６６】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【００６７】
１００  暗号化装置                      １１０，２１０  初期値設定部
１２０  メッセージ分割部                １３０  暗号化部
１４０，２４０  追加認証データ分割部
１５０，２５０  追加認証データタグ計算部
１６０，２６０  タグ計算部              １９０  出力部
２００  復号装置                        ２２０  暗号文分割部
２３０  復号部                          ２７０  検証部
２９０  入力部                          ８００  ネットワーク
【図１】
0006273223.tif 000002
【図２】
0006273223.tif 000003
【図３】
0006273223.tif 000004
【図４】
0006273223.tif 000005
【図５】
0006273223.tif 000006
【図６】
0006273223.tif 000007
【図７】
0006273223.tif 000008
【図８】
0006273223.tif 000009
【図９】
0006273223.tif 000010