(57)【特許請求の範囲】
【請求項１】
鍵ＫとメッセージＭとを入力としてｅビットのｉ倍のビット数の値Ｅを生成し、前記値Ｅをｅビット毎に分割して、値Ｍ［１］，．．．，Ｍ［ｉ］を生成する入力値生成部であって、前記値Ｍ［１］，．．．，Ｍ［ｉ］のうちの値Ｍ［１］と値Ｍ［ｉ］とに前記鍵Ｋの少なくとも一部のビットが含まれるように前記値Ｅを生成する入力値生成部と、
固定値を値Ｓ［０］として、ｊ＝１，．．．，ｉの各整数ｊについて昇順に、値Ｓ［ｊ−１］と前記入力値生成部によって生成された値Ｍ［ｊ］とを入力として関数ｇ［ｊ］によって値Ｒ［ｊ］を計算し、計算された値Ｒ［ｊ］を置換関数Ｐ［ｊ］で置換して値Ｓ［ｊ］を計算する関数計算部と、
前記関数計算部によって計算された値Ｓ［ｉ］を用いて前記メッセージＭの認証子Ｔを生成する認証子生成部と
を備えるメッセージ認証子生成装置。
【請求項２】
前記認証子生成部は、前記値Ｓ［ｉ］を入力として圧縮関数ｆ［１］によって計算された値ｓ［１］を値Ｚとし、前記値Ｓ［ｉ］を値Ｑ［１］として、前記値Ｚがｎビット以上になるまでｊ＝１から昇順に、前記値Ｑ［ｊ］を置換関数Ｐ’［ｊ］で置換した値Ｑ［ｊ＋１］を入力として圧縮関数ｆ［ｊ＋１］によって計算された値ｓ［ｊ＋１］を前記値Ｚに付加し、前記値Ｚがｎビット以上になった場合に、前記値Ｚのうちのｎビットを前記認証子Ｔとする
請求項１に記載のメッセージ認証子生成装置。
【請求項３】
前記入力値生成部は、前記鍵Ｋの後に、前記メッセージＭを付加して値Ａを生成し、前記値Ａの後に値Ｘを付加してｅビットの倍数のビット数の値Ｃを生成し、前記値Ｃの後に前記鍵Ｋを付加して値Ｄを生成し、前記値Ｄの後に値Ｙを付加して前記値Ｅを生成する
請求項１又は２に記載のメッセージ認証子生成装置。
【請求項４】
ｊ＝１，．．．，ｉの各整数ｊについての前記関数ｇ［ｊ］は、排他的論理和を計算する関数である
請求項１から３までのいずれか１項に記載のメッセージ認証子生成装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、置換を用いて安全かつ効率的にメッセージの認証子を生成する技術に関する。
【背景技術】
【０００２】
メッセージ認証アルゴリズムを用いると、２者間でメッセージをやり取りする場合に、送信したメッセージが改ざんされているか否かを受信者が確認できる。
メッセージ認証アルゴリズムを用いて改ざん検出をチェックする場合、２者間で予め鍵Ｋを共有しておく。メッセージの送信者は、メッセージＭと鍵ＫとからメッセージＭの認証子Ｔを生成し、メッセージＭと認証子Ｔとを受信者に送信する。メッセージの受信者は受け取ったメッセージＭと鍵Ｋとから認証子Ｔ’を生成する。受信者は、認証子Ｔと認証子Ｔ’とが一致すれば改ざんされていないと判断し、一致しなければ改ざんされていると判断する。【０００３】
メッセージ認証アルゴリズムの安全性は、ランダム関数との識別不可能性で示される。
メッセージ認証アルゴリズムＦが識別不可能性を満たすとは、現実世界または理想世界のどちらか一方と対話する識別者Ｄを考え、識別者Ｄがどちらと対話しているかを当てることができないことを意味する。【０００４】
現実世界では、鍵Ｋがランダムに選ばれ、識別者ＤはメッセージＭを選んで、Ｆ（Ｋ，Ｍ）のメッセージ認証子を得ることができる。理想世界では、ランダム関数Ｒに対して、識別者ＤはメッセージＭを選んで、Ｒ（Ｍ）の出力値を得ることができる。ここで、識別者ＤはメッセージＭを何度も選択することができ、選択したメッセージＭに対応するＦ（Ｋ，Ｍ）又はＲ（Ｍ）の出力値を得ることができる。【０００５】
より厳密には、１ビットの値を出力する識別者Ｄを考える。識別者Ｄが現実世界で１を出力する確率と、識別者Ｄが理想世界で１を出力する確率との差によってメッセージ認証アルゴリズムＦの識別不可能性が評価される。
識別者Ｄは、現実世界ではメッセージ認証アルゴリズムＦの出力を複数得ることができ、理想世界ではランダム関数Ｒの出力を複数得ることができる。この時のメッセージＭの総ビット数をσとすると、上記確率の差は、σを用いた確率ｐ（σ）によって評価される。そして、確率ｐ（σ）＝１となるビット数σの値を識別計算量と呼ぶ。このビット数σの値は識別に必要な計算量となり、この値が大きいほど安全性は高くなる。
ｌｏｇ２σは、識別不可能性の安全性ビットと呼ばれる。例えば、σ＝２１２８の場合、安全性ビットはｌｏｇ２２１２８＝１２８ビットとなる。【０００６】
関数Ｆが識別不可能性の安全性を満たす場合、関数Ｆはメッセージ認証アルゴリズムとして使うことができるとともに、疑似乱数生成アルゴリズムとしても使うことができる。したがって、Ｋｅｙ  Ｄｅｒｉｖａｔｉｏｎ  Ｆｕｎｃｔｉｏｎやストリーム暗号などで用いる関数として関数Ｆを使うことができる。【０００７】
非特許文献５には、非特許文献７に記載されたハッシュ関数であって、置換関数を用いたスポンジ構造のハッシュ関数を用いたメッセージ認証アルゴリズムが記載されている。【０００８】
非特許文献８には、非特許文献５に記載されたメッセージ認証アルゴリズムを高速化したメッセージ認証アルゴリズムが記載されている。【０００９】
非特許文献９のハッシュ関数Ｈとして、非特許文献７に記載されたハッシュ関数であって、置換関数を用いたスポンジ構造のハッシュ関数を用いることで、メッセージ認証アルゴリズムが構成される。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】特開２００９−１２９３９１号公報
【特許文献２】特開２００９−５１６３号公報
【非特許文献】
【００１１】
【非特許文献１】Ｍｉｈｉｒ  Ｂｅｌｌａｒｅ，  Ｒａｎ  Ｃａｎｅｔｔｉ，  ａｎｄ  Ｈｕｇｏ  Ｋｒａｗｃｚｙｋ．  Ｋｅｙｉｎｇ  Ｈａｓｈ  Ｆｕｎｃｔｉｏｎｓ  ｆｏｒ  Ｍｅｓｓａｇｅ  Ａｕｔｈｅｎｔｉｃａｔｉｏｎ．  ＣＲＹＰＴＯ  １９９６．  ｐ１−１５．
【非特許文献２】Ｍｉｈｉｒ  Ｂｅｌｌａｒｅ．  Ｎｅｗ  Ｐｒｏｏｆｓ  ｆｏｒ  ＮＭＡＣ  ａｎｄ  ＨＭＡＣ：  Ｓｅｃｕｒｉｔｙ  ｗｉｔｈｏｕｔ  Ｃｏｌｌｉｓｉｏｎ−Ｒｅｓｉｓｔａｎｃｅ．  ＣＲＹＰＴＯ  ２００６．  ｐ６０２−６１９
【非特許文献３】Ｒａｌｐｈ  Ｃ．  Ｍｅｒｋｌｅ．  Ｏｎｅ  Ｗａｙ  Ｈａｓｈ  Ｆｕｎｃｔｉｏｎｓ  ａｎｄ  ＤＥＳ．  ＣＲＹＰＴＯ  １９８９．  ｐ４２８−４４６
【非特許文献４】Ｉｖａｎ  Ｄａｍｇａｒｄ．  Ａ  Ｄｅｓｉｇｎ  Ｐｒｉｎｃｉｐｌｅ  ｆｏｒ  Ｈａｓｈ  Ｆｕｎｃｔｉｏｎｓ．  ＣＲＹＰＴＯ  １９８９．  ｐ４１６−４２７
【非特許文献５】Ｇ．  Ｂｅｒｔｏｎｉ，  Ｊ．  Ｄａｅｍｅｎ，  Ｍ．  Ｐｅｅｔｅｒｓ，  ａｎｄ  Ｇ．  Ｖ．  Ａｓｓｃｈｅ．  Ｏｎ  ｔｈｅ  ｓｅｃｕｒｉｔｙ  ｏｆ  ｔｈｅ  ｋｅｙｅｄ  ｓｐｏｎｇｅ  ｃｏｎｓｔｒｕｃｔｉｏｎ．  Ｓｙｍｍｅｔｒｉｃ  Ｋｅｙ  Ｅｎｃｒｙｐｔｉｏｎ  Ｗｏｒｋｓｈｏｐ  （ＳＫＥＷ）
【非特許文献６】Ｓｅｃｕｒｉｔｙ  ｏｆ  Ｋｅｙｅｄ  Ｓｐｏｎｇｅ  Ｃｏｎｓｔｒｕｃｔｉｏｎｓ  Ｕｓｉｎｇ  ａ  Ｍｏｄｕｌａｒ  Ｐｒｏｏｆ  Ａｐｐｒｏａｃｈ．  Ｅｌｅｎａ  Ａｎｄｒｅｅｖａ，  Ｊｏａｎ  Ｄａｅｍｅｎ，  Ｂａｒｔ  Ｍｅｎｎｉｎｋ，  ａｎｄ  Ｇｉｌｌｅｓ  Ｖａｎ  Ａｓｓｃｈｅ．  Ｆａｓｔ  Ｓｏｆｔｗａｒｅ  Ｅｎｃｒｙｐｔｉｏｎ  ２０１５  （ＦＳＥ  ２０１５）．
【非特許文献７】Ｇ．  Ｂｅｒｔｏｎｉ，  Ｊ．  Ｄａｅｍｅｎ，  ａｎｄ  Ｍ．  Ｐｅｅｔｅｒｓ．  Ｓｐｏｎｇｅ  ｆｕｎｃｔｉｏｎｓ．  Ｅｃｒｙｐｔ  Ｈａｓｈ  Ｗｏｒｋｓｈｏｐ  ２００７
【非特許文献８】Ｇ．  Ｂｅｒｔｏｎｉ，  Ｊ．  Ｄａｅｍｅｎ，  ａｎｄ  Ｍ．  Ｐｅｅｔｅｒｓ．  Ｐｅｒｍｕｔａｔｉｏｎ−ｂａｓｅｄ  ｅｎｃｒｙｐｔｉｏｎ，  ａｕｔｈｅｎｔｉｃａｔｉｏｎ  ａｎｄ  ａｕｔｈｅｎｔｉｃａｔｅｄ  ｅｎｃｒｙｐｔｉｏｎ．  Ｄｉｒｅｃｔｉｏｎｓ  ｉｎ  Ａｕｔｈｅｎｔｉｃａｔｅｄ  Ｃｉｐｈｅｒｓ  ２０１２
【非特許文献９】ＦＩＰＳ  ＰＵＢ  １９８−１．  Ｔｈｅ  Ｋｅｙｅｄ−Ｈａｓｈ  Ｍｅｓｓａｇｅ  Ａｕｔｈｅｎｔｉｃａｔｉｏｎ  Ｃｏｄｅ  （ＨＭＡＣ）．
【非特許文献１０】Ｇｕｉｄｏ  Ｂｅｒｔｏｎｉ，  Ｊｏａｎ  Ｄａｅｍｅｎ，  Ｍｉｃｈａｅｌ  Ｐｅｅｔｅｒｓ，  ａｎｄ  Ｇｉｌｌｅｓ  Ｖａｎ  Ａｓｓｃｈｅ．  Ｏｎ  ｔｈｅ  Ｉｎｄｉｆｆｅｒｅｎｔｉａｂｉｌｉｔｙ  ｏｆ  ｔｈｅ  Ｓｐｏｎｇｅ  Ｃｏｎｓｔｒｕｃｔｉｏｎ．  ＥＵＲＯＣＲＹＰＴ  ２００８．  ｐ１８１−１９７．
【発明の概要】
【発明が解決しようとする課題】
【００１２】
非特許文献６には、非特許文献５，８に記載されたメッセージ認証アルゴリズムは、置換関数がランダム置換である場合、安全性ビットがｍｉｎ｛ｋ，ｃ／２，ｂ／２｝であることが示されている。非特許文献１０には、非特許文献９のハッシュ関数Ｈとして非特許文献７に記載されたハッシュ関数を用いたメッセージ認証アルゴリズムは、置換関数がランダム置換である場合、安全性ビットがｍｉｎ｛ｃ／２，ｂ／２，ｎ／２，ｋ｝であることが示されている。
ここで、ｋは鍵Ｋのビット数である。ｂは置換関数の入出力のビット数である。ｃはキャパシティのビット数であり、ｂ＝ｃ＋ｒである。ｒはレートのビット数である。ｎは認証子のビット数である。
この発明は、置換関数を用いたメッセージ認証アルゴリズムについての安全性を改善することと、計算量を少なくすることとの少なくともいずれかを目的とする。
【課題を解決するための手段】
【００１３】
この発明に係るメッセージ認証子生成装置は、
鍵ＫとメッセージＭとを入力としてｅビットのｉ倍のビット数の値Ｅを生成し、前記値Ｅをｅビット毎に分割して、値Ｍ［１］，．．．，Ｍ［ｉ］を生成する入力値生成部であって、前記値Ｍ［１］，．．．，Ｍ［ｉ］のうちの値Ｍ［１］と値Ｍ［ｉ］とに前記鍵Ｋの少なくとも一部のビットが含まれるように前記値Ｅを生成する入力値生成部と、
任意の値を値Ｓ［０］として、ｊ＝１，．．．，ｉの各整数ｊについて昇順に、値Ｓ［ｊ−１］と値Ｍ［ｊ］とを入力として関数ｇ［ｊ］によって値Ｒ［ｊ］を計算し、計算された値Ｒ［ｊ］を置換関数Ｐ［ｊ］で置換して値Ｓ［ｊ］を計算する関数計算部と、
前記関数計算部によって計算された値Ｓ［ｉ］を用いて前記メッセージＭの認証子Ｔを生成する認証子生成部と
を備える。
【発明の効果】
【００１４】
この発明では、置換関数Ｐ［ｊ］がランダム置換である場合、安全性ビットがｍｉｎ｛ｃ，ｂ／２，ｋ｝であるメッセージ認証アルゴリズムを実現できる。
【図面の簡単な説明】
【００１５】
【図１】実施の形態１に係るメッセージ認証子生成装置１００の構成図。
【図２】実施の形態１に係るメッセージ認証子生成装置１００の動作を示すフローチャート。
【図３】実施の形態１に係るメッセージ認証アルゴリズムの説明図。
【図４】実施の形態１に係るメッセージ認証アルゴリズムの説明図。
【図５】実施の形態２に係るメッセージ認証子生成装置１００の構成図。
【図６】実施の形態２に係るメッセージ認証子生成装置１００の動作を示すフローチャート。
【図７】実施の形態２に係るメッセージ認証アルゴリズムの説明図。
【図８】実施の形態２に係るメッセージ認証アルゴリズムの説明図。
【図９】実施の形態２に係るメッセージ認証アルゴリズムの説明図。
【図１０】実施の形態２に係るメッセージ認証アルゴリズムの説明図。
【図１１】メッセージ認証子生成装置１００の機能がソフトウェアで実現される場合のハードウェア構成例を示す図。
【図１２】メッセージ認証子生成装置１００の機能がハードウェアで実現される場合のハードウェア構成例を示す図。
【発明を実施するための形態】
【００１６】
実施の形態１．
＊＊＊構成の説明＊＊＊
図１に基づき、実施の形態１に係るメッセージ認証子生成装置１００の構成を説明する。
メッセージ認証子生成装置１００は、ｋビットの鍵Ｋと、メッセージＭに対して、ｎビットの認証子Ｔを生成する。メッセージＭは、送信対象のデータである。鍵Ｋは、メッセージＭの送信先と予め共有されている秘密鍵である。ｋ，ｎは１以上の整数である。
メッセージ認証子生成装置１００は、入力値生成部１１０と、関数計算部１２０と、認証子生成部１３０とを備える。
【００１７】
入力値生成部１１０は、鍵ＫとメッセージＭとを入力として、ｉ個のｅビットの値Ｍ［１］，．．．，Ｍ［ｉ］を生成する。ｉ，ｅは１以上の整数である。
【００１８】
関数計算部１２０は、入力値生成部１１０によって生成された値Ｍ［１］，．．．，Ｍ［ｉ］を入力として、置換関数を用いたスポンジ構造のハッシュ関数Ｈにより、ハッシュ値である値Ｓ［ｉ］を計算する。
【００１９】
認証子生成部１３０は、関数計算部１２０によって計算された値Ｓ［ｉ］を用いてメッセージＭの認証子Ｔを生成する。
【００２０】
＊＊＊動作の説明＊＊＊
図２及び図３に基づき、実施の形態１に係るメッセージ認証子生成装置１００の動作を説明する。
実施の形態１に係るメッセージ認証子生成装置１００の動作は、実施の形態１に係るメッセージ認証子生成方法に相当する。また、実施の形態１に係るメッセージ認証子生成装置１００の動作は、実施の形態１に係るメッセージ認証子生成プログラムの処理に相当する。
【００２１】
ここでは、０≦ｄ＜ｂであり、ｅ＝ｂ−ｄである。
【００２２】
Ｓ１１のパディング処理では、入力値生成部１１０は、鍵ＫとメッセージＭとをパディング関数の入力としてｅビットのｉ倍のビット数の値Ｅを生成する。特に、入力値生成部１１０は、後述する値Ｍ［１］，．．．，Ｍ［ｉ］のうちの値Ｍ［１］と値Ｍ［ｉ］とに鍵Ｋの少なくとも一部のビットが含まれるように値Ｅを生成する。
パディング関数とは、入力値にビット列を付加する関数である。
【００２３】
Ｓ１２の分割処理では、入力値生成部１１０は、値Ｅを先頭からｅビット毎に分割して、値Ｍ［１］，．．．，Ｍ［ｉ］を生成する。
【００２４】
Ｓ１３の値Ｓ［０］設定処理では、関数計算部１２０は、ｂビットの固定値ＩＶを値Ｓ［０］に設定する。
【００２５】
Ｓ１４のハッシュ値計算処理では、関数計算部１２０は、ｊ＝１，．．．，ｉの各整数ｊについて昇順に、Ｒ［ｊ］＝ｇ［ｊ］（Ｓ［ｊ−１］，Ｍ［ｊ］）、Ｓ［ｊ］＝Ｐ［ｊ］（Ｒ［ｊ］）を計算する。つまり、関数計算部１２０は、ｊ＝１，．．．，ｉの各整数ｊについて昇順に、値Ｓ［ｊ−１］と入力値生成部１１０によって生成された値Ｍ［ｊ］とを入力として関数ｇ［ｊ］によって値Ｒ［ｊ］を計算し、計算された値Ｒ［ｊ］を置換関数Ｐ［ｊ］で置換して値Ｓ［ｊ］を計算する。
ここで、各関数ｇ［ｊ］は、ｂビットとｅビットとの２つの値を入力として、ｂビットの値を出力する関数であって、ｅビットの値を固定するとｂビットの置換関数となる関数である。各関数ｇ［ｊ］は、同じ関数であってもよいし、異なる関数であってもよい。各置換関数Ｐ［ｊ］は、ｂビットの置換関数である。各置換関数Ｐ［ｊ］は、同じ置換関数であってもよいし、異なる関数であってもよい。
【００２６】
Ｓ１５の値Ｚ計算処理では、認証子生成部１３０は、値Ｓ［ｉ］を入力として圧縮関数ｆ［１］によって計算された値ｓ［１］を値Ｚとする。そして、認証子生成部１３０は、値Ｓ［ｉ］を値Ｑ［１］として、値Ｚがｎビット以上になるまでｊ＝１から昇順に、値Ｑ［ｊ］を置換関数Ｐ’［ｊ］で置換した値Ｑ［ｊ＋１］を入力として圧縮関数ｆ［ｊ＋１］によって計算された値ｓ［ｊ＋１］を値Ｚに付加する。
ここで、各圧縮関数ｆ［ｊ］は、ｂビットの値をｒビットの値に圧縮する関数である。各圧縮関数ｆ［ｊ］は、同じ関数であってもよいし、異なる関数であってもよい。各置換関数Ｐ’［ｊ］は、ｂビットの置換関数である。各置換関数Ｐ’［ｊ］は、同じ関数であってもよいし、異なる関数であってもよい。
【００２７】
Ｓ１６の認証子抽出処理では、認証子生成部１３０は、値Ｚがｎビット以上になった場合に、値Ｚのうちのｎビットを認証子Ｔとする。
【００２８】
なお、Ｓ１１からＳ１２の処理が入力値生成処理であり、Ｓ１３からＳ１４の処理が関数計算処理であり、Ｓ１５からＳ１６の処理が認証子生成処理である。
【００２９】
＊＊＊実施の形態１の効果＊＊＊
実施の形態１に係るメッセージ認証子生成装置１００は、置換関数を用いたメッセージ認証アルゴリズムを実現できる。そして、実現されたメッセージ認証アルゴリズムは、置換関数Ｐ［ｊ］がランダム置換である場合、安全性ビットがｍｉｎ｛ｃ，ｂ／２，ｋ｝である。
【００３０】
非特許文献５，８に記載されたメッセージ認証アルゴリズムは、安全性ビットがｍｉｎ｛ｋ，ｃ／２，ｂ／２｝である。ここで、ｃ／２＜ｂ／２である。また、ｋの値は鍵の長さであるため、鍵を長くすれば大きな値になる。そのため、安全性ビットを長くするには、ｃ／２の値を大きくする必要がある。
実施の形態１に係るメッセージ認証子生成装置１００によって実現されたメッセージ認証アルゴリズムは、安全性ビットがｍｉｎ｛ｃ，ｂ／２，ｋ｝である。そのため、非特許文献５，８に記載されたメッセージ認証アルゴリズムに比べて安全性ビットを容易に長くすることができる。
【００３１】
＊＊＊他の構成＊＊＊
Ｓ１１では、入力値生成部１１０は、次のように値Ｅを生成してもよい。
入力値生成部１１０は、鍵Ｋの後に、メッセージＭを付加して値Ａを生成する。入力値生成部１１０は、値Ａの後に値Ｘを付加してｅビットの倍数のビット数の値Ｃを生成する。入力値生成部１１０は、値Ｃの後に鍵Ｋを付加して値Ｄを生成する。入力値生成部１１０は、値Ｄの後に値Ｙを付加してｅビットのｉ倍のビット数の値Ｅを生成する。つまり、Ｅ＝Ｋ｜｜Ｍ｜｜Ｘ｜｜Ｋ｜｜Ｙである。“｜｜”は、連結を意味する記号である。
ここで、値Ｘ及び値Ｙの具体例としては、先頭ビットと最終ビットとが１でその他のビットが０であるビット列である。つまり、Ｘ＝１｜｜０・・・０｜｜１、Ｙ＝１｜｜０・・・０｜｜１である。また、値Ｙは、値Ｅがｅビットの倍数のビット数となるような最も短いビット列であり、値Ｄがｅビットの倍数のビット数である場合にはビット数０のビット列である。
【００３２】
各関数ｇ［ｊ］は、排他的論理和を計算する関数であってもよい。つまり、Ｓ１４では、関数計算部１２０は、ｊ＝１，．．．，ｉの各整数ｊについて昇順に、Ｒ［ｊ］＝Ｓ［ｊ−１］  ｘｏｒ  （Ｍ［ｊ］｜｜０ｄ）、Ｓ［ｊ］＝Ｐ［ｊ］（Ｒ［ｊ］）を計算してもよい。
なお、入力値と０との排他的論理和を計算すると、入力値がそのまま得られる。そのため、図４に示すように、Ｓ［ｊ−１］のうちのｅビットと、Ｍ［ｊ］との排他的論理和と、Ｓ［ｊ−１］のうちの残りのｄビットとを合わせた値が値Ｒ［ｊ］としてもよい。つまり、Ｓ［ｊ−１］のうちのｄビットと０ｄとの排他的論理和の計算を省略してもよい。
また、ここでは、Ｍ［ｊ］｜｜０ｄとした。つまり、値Ｍ［ｊ］の後に、ｄビットの０が付加されるとした。しかし、０が付加される位置は値Ｍ［ｊ］の後でなくてもよい。具体的には、値Ｍ［ｊ］の前にｄビットの０が付加されてもよい。つまり、０ｄ｜｜Ｍ［ｊ］であってもよい。
【００３３】
圧縮関数ｆ［ｊ］は、入力値からｒビットを抽出する関数であってもよい。つまり、Ｓ１５では、認証子生成部１３０は、値Ｓ［ｉ］のうちのｒビットを値Ｚとし、値Ｓ［ｉ］を値Ｑ［１］として、値Ｚがｎビット以上になるまでｊ＝１から昇順に、値Ｑ［ｊ］を置換関数Ｐ’［ｊ］で置換した値Ｑ［ｊ＋１］のうちのｒビットを値Ｚに付加してもよい。
【００３４】
つまり、図３に示したメッセージ認証アルゴリズムを、図４に示すように構成してもよい。図４では、値Ｅの計算を、Ｅ＝Ｋ｜｜Ｍ｜｜Ｘ｜｜Ｋ｜｜Ｙとしている。また、値Ｒ［ｊ］の計算を、Ｒ［ｊ］＝Ｓ［ｊ−１］  ｘｏｒ  （Ｍ［ｊ］｜｜０ｄ）としている。また、圧縮関数ｆ［ｊ］を入力値からｒビットを抽出する関数としている。
【００３５】
実施の形態２．
＊＊＊構成の説明＊＊＊
図５に基づき、実施の形態２に係るメッセージ認証子生成装置１００の構成を説明する。
メッセージ認証子生成装置１００は、ｋビットの鍵Ｋと、メッセージＭに対して、ｎビットの認証子Ｔを生成する。メッセージＭは、送信対象のデータである。鍵Ｋは、メッセージＭの送信先と予め共有されている秘密鍵である。ｋ，ｎは１以上の整数である。
メッセージ認証子生成装置１００は、第１入力値生成部１１１と、第２入力値生成部１１２と、第１関数計算部１２１と、第２関数計算部１２２と、計算値生成部１３１と、認証子生成部１３２とを備える。
【００３６】
第１入力値生成部１１１は、鍵ＫとメッセージＭとを入力として、ｅ１ビットの値Ｍ［１］，．．．，Ｍ［ｉ］を生成する。ｅ１は１以上の整数である。
【００３７】
第２入力値生成部１１２は、鍵Ｋと、後述する計算値生成部１３１によって計算された値Ｎとを入力として、ｅ３ビットの値Ｎ［１］，．．．，Ｎ［ｉ’］を生成する。ｉ’は１以上の整数である。ｅ３は１以上の整数である。
【００３８】
第１関数計算部１２１は、第１入力値生成部１１１によって生成された値Ｍ［１］，．．．，Ｍ［ｉ］を入力として、置換関数を用いたスポンジ構造のハッシュ関数Ｈにより、ハッシュ値である値Ｓ１［ｉ］を計算する。
【００３９】
第２関数計算部１２２は、第２入力値生成部１１２によって生成された値Ｎ［１］，．．．，Ｎ［ｉ’］を入力として、置換関数を用いたスポンジ構造のハッシュ関数Ｈ’により、ハッシュ値である値Ｓ２［ｉ’］を計算する。
【００４０】
計算値生成部１３１は、第１関数計算部１２１によって計算された値Ｓ１［ｉ］を用いて値Ｎを生成する。
【００４１】
認証子生成部１３２は、第２関数計算部１２２によって計算された値Ｓ２［ｉ’］を用いてメッセージＭの認証子Ｔを生成する。
【００４２】
＊＊＊動作の説明＊＊＊
図６から図８に基づき、実施の形態２に係るメッセージ認証子生成装置１００の動作を説明する。
実施の形態２に係るメッセージ認証子生成装置１００の動作は、実施の形態２に係るメッセージ認証子生成方法に相当する。また、実施の形態２に係るメッセージ認証子生成装置１００の動作は、実施の形態２に係るメッセージ認証子生成プログラムの処理に相当する。
【００４３】
ここでは、０≦ｄ１，ｄ２，ｄ３＜ｂであり、ｅ１＝ｂ−ｄ１，ｅ２＝ｂ−ｄ２，ｅ３＝ｂ−ｄ３である。ｅ２は１以上の整数である。また、ｖは、１以上の整数である。
【００４４】
Ｓ２１の第１パディング処理では、第１入力値生成部１１１は、鍵ＫとメッセージＭとをパディング関数の入力としてｅ１ビットのｉ倍のビット数の値Ｃを生成する。特に、第１入力値生成部１１１は、後述する値Ｍ［１］，．．．，Ｍ［ｉ］のうちの値Ｍ［１］に鍵Ｋの少なくとも一部のビットが含まれるように値Ｃを生成する。
パディング関数とは、入力値にビット列を付加する関数である。
【００４５】
Ｓ２２の第１分割処理では、第１入力値生成部１１１は、値Ｃを先頭からｅ１ビット毎に分割して、値Ｍ［１］，．．．，Ｍ［ｉ］を生成する。
【００４６】
Ｓ２３の値Ｓ１［０］設定処理では、第１関数計算部１２１は、ｂビットの固定値ＩＶ１を値Ｓ１［０］に設定する。
【００４７】
Ｓ２４の第１ハッシュ値計算処理では、第１関数計算部１２１は、ｊ＝１，．．．，ｉの各整数ｊについて昇順に、Ｒ１［ｊ］＝ｇ１［ｊ］（Ｓ１［ｊ−１］，Ｍ［ｊ］）、Ｓ１［ｊ］＝Ｐ１［ｊ］（Ｒ１［ｊ］）を計算する。つまり、第１関数計算部１２１は、ｊ＝１，．．．，ｉの各整数ｊについて昇順に、値Ｓ１［ｊ−１］と第１入力値生成部１１１によって生成された値Ｍ［ｊ］とを入力として関数ｇ１［ｊ］によって値Ｒ１［ｊ］を計算し、計算された値Ｒ１［ｊ］を置換関数Ｐ１［ｊ］で置換して値Ｓ１［ｊ］を計算する。
ここで、各関数ｇ１［ｊ］は、ｂビットとｅ１ビットとの２つの値を入力として、ｂビットの値を出力する関数であって、ｅ１ビットの値を固定するとｂビットの置換関数となる関数である。各関数ｇ１［ｊ］は、同じ関数であってもよいし、異なる関数であってもよい。各置換関数Ｐ１［ｊ］は、ｂビットの置換関数である。各置換関数Ｐ１［ｊ］は、同じ置換関数であってもよいし、異なる関数であってもよい。
【００４８】
Ｓ２５の値Ｚ計算処理では、計算値生成部１３１は、値Ｓ１［ｉ］を入力として圧縮関数ｆ１［１］によって計算された値ｓ１［１］を値Ｚとする。そして、計算値生成部１３１は、値Ｓ１［ｉ］を値Ｑ１［１］として、値Ｚがｖビット以上になるまでｊ＝１から昇順に、値Ｑ１［ｊ］を置換関数Ｐ１’［ｊ］で置換した値Ｑ１［ｊ＋１］を入力として圧縮関数ｆ１［ｊ＋１］によって計算された値ｓ１［ｊ＋１］を値Ｚに付加する。
ここで、各圧縮関数ｆ１［ｊ］は、ｂビットの値をｅ２ビットの値に圧縮する関数である。各圧縮関数ｆ１［ｊ］は、同じ関数であってもよいし、異なる関数であってもよい。各置換関数Ｐ１’［ｊ］は、ｂビットの置換関数である。各置換関数Ｐ１’［ｊ］は、同じ関数であってもよいし、異なる関数であってもよい。
【００４９】
Ｓ２６の計算値抽出処理では、計算値生成部１３１は、値Ｚがｖビット以上になった場合に、値Ｚのうちのｖビットを値Ｎとする。
【００５０】
Ｓ２７の第２パディング処理では、第２入力値生成部１１２は、鍵Ｋと値Ｎとをパディング関数の入力としてｅ３ビットのｉ’倍のビット数の値Ｅを生成する。特に、第２入力値生成部１１２は、値Ｎ［１］，．．．，Ｎ［ｉ’］のうちの値Ｎ［１］に鍵Ｋの少なくとも一部のビットが含まれるように値Ｅを生成する。
【００５１】
Ｓ２８の第２分割処理では、第２入力値生成部１１２は、値Ｅを先頭からｅ３ビット毎に分割して、値Ｎ［１］，．．．，Ｎ［ｉ’］を生成する。
【００５２】
Ｓ２９の値Ｓ２［０］設定処理では、第２関数計算部１２２は、ｂビットの固定値ＩＶ２を値Ｓ２［０］に設定する。
【００５３】
Ｓ３０の第２ハッシュ値計算処理では、第２関数計算部１２２は、ｊ＝１，．．．，ｉ’の各整数ｊについて昇順に、Ｒ２［ｊ］＝ｇ２［ｊ］（Ｓ２［ｊ−１］，Ｎ［ｊ］）、Ｓ２［ｊ］＝Ｐ２［ｊ］（Ｒ２［ｊ］）を計算する。つまり、第２関数計算部１２２は、ｊ＝１，．．．，ｉ’の各整数ｊについて昇順に、値Ｓ２［ｊ−１］と第２入力値生成部１１２によって生成された値Ｎ［ｊ］とを入力として関数ｇ２［ｊ］によって値Ｒ２［ｊ］を計算し、計算された値Ｒ２［ｊ］を置換関数Ｐ２［ｊ］で置換して値Ｓ２［ｊ］を計算する。
ここで、各関数ｇ２［ｊ］は、ｂビットとｅ３ビットとの２つの値を入力として、ｂビットの値を出力する関数であって、ｅ３ビットの値を固定するとｂビットの置換関数となる関数である。各関数ｇ２［ｊ］は、同じ関数であってもよいし、異なる関数であってもよい。各置換関数Ｐ２［ｊ］は、ｂビットの置換関数である。各置換関数Ｐ２［ｊ］は、同じ置換関数であってもよいし、異なる関数であってもよい。
【００５４】
Ｓ３１の値Ｗ計算処理では、認証子生成部１３２は、値Ｓ２［ｉ’］を入力として圧縮関数ｆ２［１］によって計算された値ｓ２［１］を値Ｗとする。そして、認証子生成部１３２は、値Ｓ２［ｉ’］を値Ｑ２［１］として、値Ｗがｎビット以上になるまでｊ＝１から昇順に、値Ｑ２［ｊ］を置換関数Ｐ２’［ｊ］で置換した値Ｑ２［ｊ＋１］を入力として圧縮関数ｆ２［ｊ＋１］によって計算された値ｓ２［ｊ＋１］を値Ｗに付加する。
ここで、各圧縮関数ｆ２［ｊ］は、ｂビットの値をｒビットの値に圧縮する関数である。各圧縮関数ｆ２［ｊ］は、同じ関数であってもよいし、異なる関数であってもよい。各置換関数Ｐ２’［ｊ］は、ｂビットの置換関数である。各置換関数Ｐ２’［ｊ］は、同じ関数であってもよいし、異なる関数であってもよい。
【００５５】
Ｓ３２の認証子抽出処理では、認証子生成部１３２は、値Ｗがｎビット以上になった場合に、値Ｗのうちのｎビットを認証子Ｔとする。
【００５６】
なお、Ｓ２１からＳ２２の処理が第１入力値生成処理であり、Ｓ２３からＳ２４の処理が第１関数計算処理であり、Ｓ２５からＳ２６の処理が計算値生成処理である。また、Ｓ２７からＳ２８の処理が第２入力値生成処理であり、Ｓ２９からＳ３０の処理が第２関数計算処理であり、Ｓ３１からＳ３２の処理が認証子生成処理である。
【００５７】
＊＊＊実施の形態２の効果＊＊＊
実施の形態２に係るメッセージ認証子生成装置１００は、置換関数を用いたメッセージ認証アルゴリズムを実現できる。そして、実現されたメッセージ認証アルゴリズムは、置換関数Ｐ１［ｊ］及び置換関数Ｐ２［ｊ］がランダム置換である場合、安全性ビットがｍｉｎ｛ｃ，ｂ／２，ｖ／２，ｋ｝である。
【００５８】
＊＊＊他の構成＊＊＊
Ｓ２１では、第１入力値生成部１１１は、次のように値Ｃを生成してもよい。
第１入力値生成部１１１は、鍵Ｋとｋビットの固定値ｉｐａｄとの排他的論理和を計算して、値Ｋ１とする。第１入力値生成部１１１は、値Ｋ１の後に、メッセージＭを付加して値Ａを生成する。第１入力値生成部１１１は、値Ａの後に値Ｘを付加してｅ１ビットのｉ倍のビット数の値Ｃを生成する。つまり、Ｃ＝Ｋ１｜｜Ｍ｜｜Ｘである。
ここで、値Ｘの具体例としては、先頭ビットと最終ビットとが１でその他のビットが０であるビット列である。つまり、Ｘ＝１｜｜０・・・０｜｜１である。また、値Ｘは、値Ｃがｅ１ビットの倍数のビット数となるような最も短いビット列であり、値Ａがｅ１ビットの倍数のビット数である場合にはビット数０のビット列である。
【００５９】
各関数ｇ１［ｊ］は、排他的論理和を計算する関数であってもよい。つまり、Ｓ２４では、第１関数計算部１２１は、ｊ＝１，．．．，ｉの各整数ｊについて昇順に、Ｒ１［ｊ］＝Ｓ１［ｊ−１］  ｘｏｒ  （Ｍ［ｊ］｜｜０ｄ１）、Ｓ１［ｊ］＝Ｐ１［ｊ］（Ｒ１［ｊ］）を計算してもよい。
なお、入力値と０との排他的論理和を計算すると、入力値がそのまま得られる。そのため、図９に示すように、Ｓ１［ｊ−１］のうちのｅ１ビットと、Ｍ［ｊ］との排他的論理和と、Ｓ１［ｊ−１］のうちの残りのｄ１ビットとを合わせた値が値Ｒ［ｊ］としてもよい。つまり、Ｓ１［ｊ−１］のうちのｄ１ビットと０ｄ１との排他的論理和の計算を省略してもよい。
また、ここでは、Ｍ［ｊ］｜｜０ｄ１とした。つまり、値Ｍ［ｊ］の後に、ｄ１ビットの０が付加されるとした。しかし、０が付加される位置は値Ｍ［ｊ］の後でなくてもよい。具体的には、値Ｍ［ｊ］の前にｄ１ビットの０が付加されてもよい。つまり、０ｄ１｜｜Ｍ［ｊ］であってもよい。
【００６０】
圧縮関数ｆ１［ｊ］は、入力値からｅ２ビットを抽出する関数であってもよい。つまり、Ｓ２５では、計算値生成部１３１は、値Ｓ１［ｉ］のうちのｅ２ビットを値Ｚとし、値Ｓ１［ｉ］を値Ｑ１［１］として、値Ｚがｖビット以上になるまでｊ＝１から昇順に、値Ｑ１［ｊ］を置換関数Ｐ１’［ｊ］で置換した値Ｑ１［ｊ＋１］のうちのｅ２ビットを値Ｚに付加してもよい。
【００６１】
Ｓ２７では、第２入力値生成部１１２は、次のように値Ｅを生成してもよい。
第２入力値生成部１１２は、鍵Ｋとｋビットの固定値ｏｐａｄとの排他的論理和を計算して、値Ｋ２とする。第２入力値生成部１１２は、値Ｋ２の後に、値Ｎを付加して値Ｄを生成する。第２入力値生成部１１２は、値Ｄの後に値Ｙを付加してｅ３ビットのｉ’倍のビット数の値Ｅを生成する。つまり、Ｅ＝Ｋ２｜｜Ｎ｜｜Ｙである。
ここで、値Ｙの具体例としては、先頭ビットと最終ビットとが１でその他のビットが０であるビット列である。つまり、Ｙ＝１｜｜０・・・０｜｜１である。また、値Ｙは、値Ｅがｅ３ビットの倍数のビット数となるような最も短いビット列であり、値Ｄがｅ３ビットの倍数のビット数である場合にはビット数０のビット列である。また、固定値ｏｐａｄは、固定値ｉｐａｄとは異なる値である。
【００６２】
各関数ｇ２［ｊ］は、排他的論理和を計算する関数であってもよい。つまり、Ｓ３０では、第２関数計算部１２２は、ｊ＝１，．．．，ｉ’の各整数ｊについて昇順に、Ｒ２［ｊ］＝Ｓ２［ｊ−１］  ｘｏｒ  （Ｎ［ｊ］｜｜０ｄ３）、Ｓ２［ｊ］＝Ｐ２［ｊ］（Ｒ２［ｊ］）を計算してもよい。
なお、入力値と０との排他的論理和を計算すると、入力値がそのまま得られる。そのため、図１０に示すように、Ｓ２［ｊ−１］のうちのｅ３ビットと、Ｎ［ｊ］との排他的論理和と、Ｓ２［ｊ−１］のうちの残りのｄ３ビットとが値Ｒ［ｊ］としてもよい。つまり、Ｓ２［ｊ−１］のうちのｄ３ビットと０ｄ３との排他的論理和の計算を省略してもよい。
また、ここでは、Ｎ［ｊ］｜｜０ｄ３とした。つまり、値Ｎ［ｊ］の後に、ｄ３ビットの０が付加されるとした。しかし、０が付加される位置は値Ｎ［ｊ］の後でなくてもよい。具体的には、値Ｎ［ｊ］の前にｄ３ビットの０が付加されてもよい。つまり、０ｄ３｜｜Ｎ［ｊ］であってもよい。
【００６３】
圧縮関数ｆ２［ｊ］は、入力値からｒビットを抽出する関数であってもよい。つまり、Ｓ３１では、認証子生成部１３２は、値Ｓ２［ｉ］のうちのｒビットを値Ｗとし、値Ｓ２［ｉ］を値Ｑ２［１］として、値Ｗがｎビット以上になるまでｊ＝１から昇順に、値Ｑ２［ｊ］を置換関数Ｐ２’［ｊ］で置換した値Ｑ２［ｊ＋１］のうちのｒビットを値Ｗに付加してもよい。
【００６４】
つまり、図７及び図８に示したメッセージ認証アルゴリズムを、図９及び図１０に示すように構成してもよい。図９及び図１０では、値Ｃの計算を、Ｃ＝Ｋ１｜｜Ｍ｜｜Ｘとしている。また、値Ｒ１［ｊ］の計算を、Ｒ１［ｊ］＝Ｓ１［ｊ−１］  ｘｏｒ  （Ｍ［ｊ］｜｜０ｄ１）としている。また、圧縮関数ｆ１［ｊ］を入力値からｅ２ビットを抽出する関数としている。また、値Ｅの計算を、Ｅ＝Ｋ２｜｜Ｎ｜｜Ｙとしている。また、値Ｒ２［ｊ］の計算を、Ｒ２［ｊ］＝Ｓ２［ｊ−１］  ｘｏｒ  （Ｎ［ｊ］｜｜０ｄ３）としている。また、圧縮関数ｆ２［ｊ］を入力値からｒビットを抽出する関数としている。
【００６５】
＊＊＊ハードウェア構成例の説明＊＊＊
最後に、メッセージ認証子生成装置１００のハードウェア構成例を説明する。
メッセージ認証子生成装置１００はコンピュータである。
メッセージ認証子生成装置１００の機能は、ソフトウェアで実現することもできるし、ハードウェアで実現することもできる。
図１１は、メッセージ認証子生成装置１００の機能がソフトウェアで実現される場合のハードウェア構成例を示す。
図１２は、メッセージ認証子生成装置１００の機能がハードウェアで実現される場合のハードウェア構成例を示す。
以下、図１１及び図１２を参照して、メッセージ認証子生成装置１００のハードウェア構成例を説明する。
【００６６】
＊＊メッセージ認証子生成装置１００の機能がソフトウェアで実現される場合＊＊
メッセージ認証子生成装置１００の機能がソフトウェアで実現される場合は、図１１に示すように、メッセージ認証子生成装置１００は、プロセッサ９０１、補助記憶装置９０２、メモリ９０３、通信装置９０４、入力装置９０７、ディスプレイ９０８といったハードウェアを備える。
プロセッサ９０１は、信号線９１０を介して他のハードウェアと接続され、これら他のハードウェアを制御する。
【００６７】
プロセッサ９０１は、プロセッシングを行うＩＣ（Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）である。プロセッサ９０１は、具体的には、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）、ＤＳＰ（Ｄｉｇｉｔａｌ  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｏｒ）、ＧＰＵ（Ｇｒａｐｈｉｃｓ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）である。
補助記憶装置９０２は、具体的には、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、フラッシュメモリ、ＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）である。
メモリ９０３は、具体的には、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）である。
通信装置９０４は、データを受信するレシーバー９０４１及びデータを送信するトランスミッター９０４２を含む。通信装置９０４は、具体的には、通信チップ又はＮＩＣ（Ｎｅｔｗｏｒｋ  Ｉｎｔｅｒｆａｃｅ  Ｃａｒｄ）である。
【００６８】
プロセッサ９０１は、入力インタフェースを介して、入力装置９０７に接続されている。入力インタフェースは、入力装置９０７のケーブルが接続されるポートである。また、プロセッサ９０１は、ディスプレイインタフェースを介して、ディスプレイ９０８に接続されている。ディスプレイインタフェースは、ディスプレイ９０８のケーブルが接続されるポートである。
入力装置９０７は、具体的には、マウス、キーボード又はタッチパネルである。
ディスプレイ９０８は、具体的には、ＬＣＤ（Ｌｉｑｕｉｄ  Ｃｒｙｓｔａｌ  Ｄｉｓｐｌａｙ）である。
【００６９】
補助記憶装置９０２には、入力値生成部１１０と、関数計算部１２０と、認証子生成部１３０と、第１入力値生成部１１１と、第２入力値生成部１１２と、第１関数計算部１２１と、第２関数計算部１２２と、計算値生成部１３１と、認証子生成部１３２との機能を実現するプログラムが記憶されている。以下、入力値生成部１１０と、関数計算部１２０と、認証子生成部１３０と、第１入力値生成部１１１と、第２入力値生成部１１２と、第１関数計算部１２１と、第２関数計算部１２２と、計算値生成部１３１と、認証子生成部１３２とをまとめて「部」と表記する。
このプログラムは、メモリ９０３にロードされ、プロセッサ９０１に読み込まれ、プロセッサ９０１によって実行される。
更に、補助記憶装置９０２には、ＯＳ（Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ）も記憶されている。そして、ＯＳの少なくとも一部がメモリ９０３にロードされ、プロセッサ９０１はＯＳを実行しながら、「部」の機能を実現するプログラムを実行する。
【００７０】
図１１では、１つのプロセッサ９０１が図示されているが、メッセージ認証子生成装置１００が複数のプロセッサ９０１を備えていてもよい。そして、複数のプロセッサ９０１が「部」の機能を実現するプログラムを連携して実行してもよい。
また、「部」の処理の結果を示す情報やデータや信号値や変数値が、メモリ９０３、補助記憶装置９０２、又は、プロセッサ９０１内のレジスタ又はキャッシュメモリに記憶される。また、「部」の機能を実現するプログラムは、磁気ディスク、フレキシブルディスク、光ディスク、コンパクトディスク、ブルーレイ（登録商標）ディスク、ＤＶＤ等の可搬記憶媒体に記憶されてもよい。
【００７１】
＊＊メッセージ認証子生成装置１００の機能がハードウェアで実現される場合＊＊
メッセージ認証子生成装置１００の機能がハードウェアで実現される場合は、図１２に示すように、メッセージ認証子生成装置１００は、処理回路９９０、通信装置９０４、入力装置９０７、ディスプレイ９０８といったハードウェアを備える。
通信装置９０４、入力装置９０７、ディスプレイ９０８及び信号線９１０は、図１１で説明したものと同じであるため、説明を省略する。
処理回路９９０は、「部」の機能を実現する専用の電子回路である。処理回路９９０は、単一回路、複合回路、プログラム化したプロセッサ、並列プログラム化したプロセッサ、ロジックＩＣ、ＧＡ（Ｇａｔｅ  Ａｒｒａｙ）、ＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ  Ｓｐｅｃｉｆｉｃ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）、ＦＰＧＡ（Ｆｉｅｌｄ−Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙ）が想定される。
「部」の機能を１つの処理回路９９０で実現してもよいし、「部」の機能を複数の処理回路９９０に分散させて実現してもよい。
【００７２】
＊＊メッセージ認証子生成装置１００の機能がソフトウェアとハードウェアの組み合わせで実現される場合＊＊
メッセージ認証子生成装置１００の一部の機能を専用のハードウェアで実現し、他の機能をソフトウェア（プログラム）で実現するようにしてもよい。
【００７３】
＊＊付記＊＊
プロセッサ９０１、補助記憶装置９０２及びメモリ９０３と、処理回路９９０を、総称して「プロセッシングサーキットリー」という。
つまり、メッセージ認証子生成装置１００のハードウェア構成が図１１のハードウェア構成、図１２のハードウェア構成のいずれであっても、「部」の機能は、プロセッシングサーキットリーにより実現される。
また、「部」を「工程」又は「手順」又は「処理」に読み替えてもよい。
また、「部」の機能をファームウェアで実現してもよい。
【符号の説明】
【００７４】
１００  メッセージ認証子生成装置、１１０  入力値生成部、１１１  第１入力値生成部、１１２  第２入力値生成部、１２０  関数計算部、１２１  第１関数計算部、１２２  第２関数計算部、１３０  認証子生成部、１３１  計算値生成部、１３２  認証子生成部。
【要約】
メッセージ認証子生成装置は、鍵ＫとメッセージＭとを入力としてｅビットのｉ倍のビット数の値Ｅを生成し、値Ｅをｅビット毎に分割して、値Ｍ［１］，．．．，Ｍ［ｉ］を生成する。この際、メッセージ認証子生成装置は、値Ｍ［１］，．．．，Ｍ［ｉ］のうちの値Ｍ［１］と値Ｍ［ｉ］とに鍵Ｋの少なくとも一部のビットが含まれるように値Ｅを生成する。メッセージ認証子生成装置は、任意の値を値Ｓ［０］として、ｊ＝１，．．．，ｉの各整数ｊについて昇順に、値Ｓ［ｊ−１］と値Ｍ［ｊ］とを入力として関数ｇ［ｊ］によって値Ｒ［ｊ］を計算し、計算された値Ｒ［ｊ］を置換関数Ｐ［ｊ］で置換して値Ｓ［ｊ］を計算する。メッセージ認証子生成装置は、値Ｓ［ｉ］を用いてメッセージＭの認証子Ｔを生成する。【図１】
0006033504.tif 000002
【図２】
0006033504.tif 000003
【図３】
0006033504.tif 000004
【図４】
0006033504.tif 000005
【図５】
0006033504.tif 000006
【図６】
0006033504.tif 000007
【図７】
0006033504.tif 000008
【図８】
0006033504.tif 000009
【図９】
0006033504.tif 000010
【図１０】
0006033504.tif 000011
【図１１】
0006033504.tif 000012
【図１２】
0006033504.tif 000013