(57)【特許請求の範囲】
【請求項１】
入力値Ｍに値を付加して（ｎ×Ｌ）ビット長のパディング値Ｍ’を生成するパディング部であって、前記入力値Ｍの後に値Ｌをビット表現したＢ（Ｍ）を付加し、さらに後にＢ（Ｍ）のビット長をビット表現したＢ１（Ｂ（Ｍ））を付加してパディング値Ｍ’を生成するパディング部と、
前記パディング部が生成したパディング値Ｍ’を先頭から順にｎビット毎に分割したＬ個の値を入力としてハッシュ値を計算するハッシュ値計算部と
を備えることを特徴とするハッシュ値計算装置。
【請求項２】
前記パディング部は、前記入力値Ｍの後にビット値を１ビット付加し、さらに後に前記ビット値とは異なるビット値を０ビット以上付加し、さらに後に前記Ｂ（Ｍ）を付加し、さらに後に前記Ｂ１（Ｂ（Ｍ））を付加してパディング値Ｍ’を生成する
ことを特徴とする請求項１に記載のハッシュ値計算装置。
【請求項３】
前記Ｂ（Ｍ）は、最上位ビットが１であり、
前記Ｂ１（Ｂ（Ｍ））は、固定長Ｔビットである
ことを特徴とする請求項１又は２に記載のハッシュ値計算装置。
【請求項４】
前記ハッシュ値計算部は、Ｍｅｒｋｌｅ−Ｄａｍｇａｒｄ構造を持つハッシュ関数を用いてハッシュ値を計算する
ことを特徴とする請求項１から３までのいずれかに記載のハッシュ値計算装置。
【請求項５】
前記ハッシュ値計算部は、ＳＨＡ−２５６又はＳＨＡ−２２４を用いてハッシュ値を計算し、
前記固定長Ｔは、６ビットである
ことを特徴とする請求項３に記載のハッシュ値計算装置。
【請求項６】
前記ハッシュ値計算部は、ＳＨＡ−５１２又はＳＨＡ−３８４又はＳＨＡ５１２／２２４又はＳＨＡ−５１２／２５６を用いてハッシュ値を計算し、
前記固定長Ｔは、７ビットである
ことを特徴とする請求項３に記載のハッシュ値計算装置。
【請求項７】
入力値Ｍに値を付加して（ｎ×Ｌ）バイト長のパディング値Ｍ’を生成するパディング部であって、前記入力値Ｍの後に値Ｌをバイト表現したＢ（Ｍ）を付加し、さらに後にＢ（Ｍ）のバイト長をバイト表現したＢ１（Ｂ（Ｍ））を付加してパディング値Ｍ’を生成するパディング部と、
前記パディング部が生成したパディング値Ｍ’を先頭から順にｎバイト毎に分割したＬ個の値を入力としてハッシュ値を計算するハッシュ値計算部と
を備えることを特徴とするハッシュ値計算装置。
【請求項８】
前記パディング部は、前記入力値Ｍの後にバイト値を１バイト付加し、さらに後に前記バイト値と異なるバイト値を０バイト以上付加し、さらに後に前記Ｂ（Ｍ）を付加し、さらに後に前記Ｂ１（Ｂ（Ｍ））を付加してパディング値Ｍ’を生成する
ことを特徴とする請求項７に記載のハッシュ値計算装置。
【請求項９】
前記Ｂ（Ｍ）は、最上位バイトが０ｘ００以外の値であり、
前記Ｂ１（Ｂ（Ｍ））は、固定長Ｔバイトである
ことを特徴とする請求項７又は８に記載のハッシュ値計算装置。
【請求項１０】
前記ハッシュ値計算部は、Ｍｅｒｋｌｅ−Ｄａｍｇａｒｄ構造を持つハッシュ関数を用いてハッシュ値を計算する
ことを特徴とする請求項７から９までのいずれかに記載のハッシュ値計算装置。
【請求項１１】
前記ハッシュ値計算部は、ＳＨＡ−２５６又はＳＨＡ−２２４又はＳＨＡ−５１２又はＳＨＡ−３８４又はＳＨＡ５１２／２２４又はＳＨＡ−５１２／２５６を用いてハッシュ値を計算し、
前記固定長Ｔは、１バイトである
ことを特徴とする請求項９に記載のハッシュ値計算装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、入力値をハッシュ関数への入力用に加工するパディング技術に関する。
【背景技術】
【０００２】
ハッシュ関数は、任意長の値を入力として、固定長のハッシュ値を出力する関数である。
【０００３】
非特許文献１，２には、Ｍｅｒｋｌｅ−Ｄａｍｇａｒｄ構造を持つハッシュ関数について記載されている。
非特許文献１，２に記載されたＭｅｒｋｌｅ−Ｄａｍｇａｒｄ構造を持つハッシュ関数では、ｎ＋ｍビット長の値を入力とし、ｍビット長の値を出力する圧縮関数ｈと、任意のビット長の値とを入力とし、（ｎ×Ｌ）ビット長のパディング値を出力するパディング関数ｐａｄとが用いられる。ここで、ｎ，ｍ，Ｌは１以上の整数である。
非特許文献１，２に記載されたＭｅｒｋｌｅ−Ｄａｍｇａｒｄ構造を持つハッシュ関数では、以下の（１）〜（５）が計算され、ハッシュ値が計算される。
（１）任意のビット長の入力値Ｍがパディング関数ｐａｄに入力され、（ｎ×Ｌ）ビット長のパディング値Ｍ’が出力される。つまり、Ｍ’＝ｐａｄ（Ｍ）である。
（２）パディング値Ｍ’が先頭から順にｎビット毎にＬ個の値Ｍ［１］，Ｍ［２］，．．．，Ｍ［Ｌ］に分割される。つまり、Ｍ’＝Ｍ［１］｜｜Ｍ［２］｜｜・・・｜｜Ｍ［Ｌ］である。
（３）ｍビット長の固定値ＩＶがｃｖ［０］に設定される。
（４）ｉ＝１，．．．，Ｌの各整数ｉについて、ｃｖ［ｉ］＝ｈ（ｃｖ［ｉ−１］，Ｍ［ｉ］）が計算される。
（５）ｃｖ［Ｌ］がハッシュ値として出力される。
【０００４】
Ｍｅｒｋｌｅ−Ｄａｍｇａｒｄ構造を持つハッシュ関数が衝突困難性の性質を有するためには、パディング関数ｐａｄに以下の性質Ａが要求される。
（性質Ａ）
長さが異なる任意の２つの値ｘと値ｙとに対して、Ｘ＝ｐａｄ（ｘ），Ｙ＝ｐａｄ（ｙ）、Ｘ＝Ｘ［１］｜｜．．．｜｜Ｘ［ｖ］、Ｙ＝Ｙ［１］｜｜．．．｜｜Ｙ［ｗ］とする。このとき、ｖ≠ｗならば、Ｘ［ｖ］≠Ｙ［ｗ］、ｖ＝ｗならば、あるｊについてＸ［ｊ］≠Ｙ［ｊ］である。ここで、ｉ＝１，．．．，ｖの各整数ｉについてのＸ［ｉ］と、ｉ＝１，．．．，ｗの各整数ｉについてのＹ［ｉ］とは、ｎビット長である。
【０００５】
非特許文献３には、入力値Ｍの後ろに１を付加し、その後に０ビット以上の０を付加し、最後にｓビットのビット列＜Ｍ＞を付加して、パディング値Ｍ’を生成することについて記載されている。つまり、Ｍ’＝Ｍ｜｜１｜｜０．．．０｜｜＜Ｍ＞である。ここで、０については、パディング値Ｍ’がｎの倍数となる最少のビットだけ付加される。また、＜Ｍ＞は、入力値Ｍのビット長をｓビット列で表現した値となる。値ｓは、ＳＨＡ−２２４，  ＳＨＡ−２５６の場合、６４であり、ＳＨＡ−３８４，  ＳＨＡ−５１２，  ＳＨＡ−５１２／２２４，  ＳＨＡ−５１２／２５６の場合、１２８である。
【０００６】
非特許文献４には、入力値Ｍの後ろに０ビット以上の０を付加し、最後にｓビットのビット列＜Ｍ＞を付加して、パディング値Ｍ’を生成することについて記載されている。つまり、Ｍ’＝Ｍ｜｜０．．．０｜｜＜Ｍ＞である。ここで、０については、パディング値Ｍ’がｎの倍数となる最少のビットだけ付加される。
非特許文献４のパディング方法は、パディングするビット列を非特許文献３のパディング方法よりも短くすることができる。
【０００７】
特許文献１には、入力値Ｍの後ろに１を付加し、次に０を付加し、最後にビット列ｂ（Ｍ）を付加して、パディング値Ｍ’を生成することについて記載されている。つまり、Ｍ’＝Ｍ｜｜１｜｜０．．．０｜｜ｂ（Ｍ）である。ここで、０については、パディング値Ｍ’がｎの倍数となる最少のビットだけ付加される。また、ｂ（Ｍ）は、パディング値Ｍ’のブロック長Ｌを予め定められたｔビット長でビット表現したものである。
また、特許文献１では、ｂ（Ｍ）のビット長を短くするために、次の方法が提案されている。ｂ１（Ｍ）をパディング値Ｍ’のブロック長Ｌをｔ１（ｔ１＜ｔ）ビット長でビット表現したものとする。入力値Ｍに対して、ブロック長Ｌがｔ１ビット以内で表現可能ならば、Ｍ’＝Ｍ｜｜１｜｜０．．．０｜｜ｂ１（Ｍ）｜｜０とし、ブロック長Ｌがｔ１ビット以内で表現不可能ならば、Ｍ’＝Ｍ｜｜１｜｜０．．．０｜｜ｂ（Ｍ）｜｜１とする。ここで、例えば、ｔは５６ビット、ｔ１はｔの半分の２８ビットである。
特許文献１のパディング方法は、パディングするビット列を非特許文献４のパディング方法より短くすることができる。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２０１０−１５２４６８号公報
【非特許文献】
【０００９】
【非特許文献１】Ｒ．  Ｍｅｒｋｌｅ，  Ｏｎｅ  Ｗａｙ  Ｈａｓｈ  Ｆｕｎｃｔｉｏｎｓ  ａｎｄ  ＤＥＳ，  ＣＲＹＰＴＯ’８９
【非特許文献２】Ｉ．  Ｄａｍｇａｒｄ，  Ａ  Ｄｅｓｉｇｎ  Ｐｒｉｎｃｉｐｌｅ  ｆｏｒ  Ｈａｓｈ  Ｆｕｎｃｔｉｏｎｓ，  ＣＲＹＰＴＯ’８９
【非特許文献３】ＦＩＰＳ  １８０−４  −  Ｎａｔｉｏｎａｌ  Ｉｎｓｔｉｔｕｔｅ  ｏｆ  Ｓｔａｎｄａｒｄｓ  ａｎｄ  Ｔｅｃｈｎｏｌｏｇｙ
【非特許文献４】ＮＩＳＴ  ｈａｓｈ  ｗｏｒｋｓｈｏｐ  Ｉｍｐｒｏｖｉｎｇ  Ｈａｓｈ  Ｆｕｎｃｔｉｏｎ  Ｐａｄｄｉｎｇ
【発明の概要】
【発明が解決しようとする課題】
【００１０】
パディングするビット列を短くすることにより、パディング値Ｍ’のブロック長Ｌが短くなり、圧縮関数ｈの計算回数を減らすことができる場合がある。その結果、ハッシュ値を計算するための計算量を少なくすることができる場合がある。
この発明は、パディングするビット列（バイト列）をより短くすることを目的とする。
【課題を解決するための手段】
【００１１】
この発明に係るハッシュ値計算装置は、
入力値Ｍに値を付加して（ｎ×Ｌ）ビット長のパディング値Ｍ’を生成するパディング部であって、前記入力値Ｍの後に値Ｌをビット表現したＢ（Ｍ）を付加し、さらに後にＢ（Ｍ）のビット長をビット表現したＢ１（Ｂ（Ｍ））を付加してパディング値Ｍ’を生成するパディング部と、
前記パディング部が生成したパディング値Ｍ’を先頭から順にｎビット毎に分割したＬ個の値を入力としてハッシュ値を計算するハッシュ値計算部と
を備えることを特徴とする。
【発明の効果】
【００１２】
この発明に係るハッシュ値計算装置では、入力値Ｍに、値Ｌのビット表現Ｂ（Ｍ）を付加し、Ｂ（Ｍ）のビット長のビット表現Ｂ１（Ｂ（Ｍ））を付加してパディング値Ｍ’を生成する。これにより、パディングするビット列を短くできる。
【図面の簡単な説明】
【００１３】
【図１】実施の形態１に係るハッシュ値計算装置１０の構成図。
【図２】実施の形態１に係るハッシュ値計算装置１０の処理の流れを示すフローチャート。
【図３】ハッシュ関数の構成図。
【発明を実施するための形態】
【００１４】
実施の形態１．
図１は、実施の形態１に係るハッシュ値計算装置１０の構成図である。
ハッシュ値計算装置１０は、任意長値受付部１１、パディング部１２、分割部１３、ハッシュ値計算部１４を備える。
【００１５】
図２は、実施の形態１に係るハッシュ値計算装置１０の処理の流れを示すフローチャートである。
（Ｓ１：任意長値受付処理）
任意長値受付部１１は、入力装置から、任意のビット長の入力値Ｍの入力を受け付ける。
【００１６】
（Ｓ２：パディング処理）
パディング部１２は、処理装置により、Ｓ１で受け付けられた入力値Ｍに値を付加して（ｎ×Ｌ）ビット長のパディング値Ｍ’を生成する。
具体的には、パディング部１２は、入力値Ｍの後ろに１を付加し、その後ろに０ビット以上の０を付加し、その後ろにパディング値Ｍ’のブロック長Ｌをビット表現したＢ（Ｍ）を付加し、その後ろにＢ（Ｍ）のビット長をビット表現したＢ１（Ｂ（Ｍ））を付加して、パディング値Ｍ’を生成する。
つまり、Ｍ’＝Ｍ｜｜１｜｜０．．．０｜｜Ｂ（Ｍ）｜｜Ｂ１（Ｂ（Ｍ））である。
【００１７】
ここで、Ｂ１（Ｂ（Ｍ））は、Ｂ（Ｍ）のビット長が、予め定められた固定長Ｔビットでビット表現されたものである。
また、Ｂ（Ｍ）は、パディング値Ｍ’のブロック長Ｌが、最上位ビットが１となるようにビット表現されたものである。そのため、Ｂ（Ｍ）は、２Ｔ−１ビット以下の可変長である。
また、０については、パディング値Ｍ’がｎの倍数となる最少のビットだけ付加される。
【００１８】
なお、パディング値Ｍ’のブロック長Ｌは、入力値Ｍに応じて、できる限り短くなるように設定される。具体的には、以下のように、パディング値Ｍ’のブロック長Ｌは設定される。
パディング値Ｍ’のビット長は、入力値Ｍのビット長（ｐビットとする）と、付加される１のビット長（１ビット）と、付加される０のビット長（０ビット以上）と、Ｂ（Ｍ）のビット長（２Ｔ−１ビット以下の可変長）と、Ｂ１（Ｂ（Ｍ））のビット長（固定長Ｔ）との和である。入力値Ｍを受け付けた時点で、入力値Ｍのビット長（ｐビット）と、付加される１のビット長（１ビット）と、Ｂ１（Ｂ（Ｍ））のビット長（固定長Ｔ）とは決定している。残りの、付加される０のビット長は０ビット以上の任意長であり、Ｂ（Ｍ）のビット長はパディング値Ｍ’のブロック長Ｌにより定まる。そのため、入力値Ｍのビット長（ｐビット）と、付加される１のビット長（１ビット）と、Ｂ１（Ｂ（Ｍ））のビット長（固定長Ｔ）との和（ｐ＋１＋Ｔビット）と、ｎとの関係から、パディング値Ｍ’のブロック長Ｌを定めることができる。つまり、パディング値Ｍ’のビット長はｎ×Ｌビットであるから、和（ｐ＋１＋Ｔビット）にＢ（Ｍ）を付加した場合のビット長が、（ｎ×Ｌ）ビット以下になる最小の値Ｌを計算すればよい。
【００１９】
パディング値Ｍ’のブロック長Ｌが定まれば、Ｂ（Ｍ）のビット長も定まり、付加される０のビット長も定まる。
【００２０】
（Ｓ３：分割処理）
分割部１３は、処理装置により、Ｓ２で生成されたパディング値Ｍ’を、先頭から順にｎビット毎にＬ個の値Ｍ［１］，Ｍ［２］，．．．，Ｍ［Ｌ］に分割する。つまり、Ｍ’＝Ｍ［１］｜｜Ｍ［２］｜｜・・・｜｜Ｍ［Ｌ］である。
【００２１】
（Ｓ４：ハッシュ値計算処理）
ハッシュ値計算部１４は、処理装置により、図３に示すように、ｎ＋ｍビット長の値を入力とし、ｍビット長の値を出力する圧縮関数ｈを用いて、ｉ＝１，．．．，Ｌの各整数ｉについて順に、ｃｖ［ｉ］＝ｈ（ｃｖ［ｉ−１］，Ｍ［ｉ］）を計算する。つまり、ハッシュ値計算部１４は、ｉ＝１，．．．，Ｌの各整数ｉについて順に、ｃｖ［ｉ−１］及びＭ［ｉ］を入力として圧縮関数ｈを計算する。ここで、ｃｖ［０］は、ｍビット長の固定値ＩＶである。
そして、ハッシュ値計算部１４は、ｃｖ［Ｌ］をハッシュ値として出力装置へ出力する。
【００２２】
以上のように、実施の形態１に係るハッシュ値計算装置１０では、パディング値Ｍ’のブロック長Ｌをビット表現したＢ（Ｍ）のビット長をビット表現したＢ１（Ｂ（Ｍ））を付加する。これにより、Ｂ（Ｍ）のビット長を可変にすることが可能になり、その結果、従来よりもパディングするビット列を短くできる。
そのため、パディング値Ｍ’のブロック長Ｌが短くなり、圧縮関数ｈの計算回数を減らすことができる場合がある。その結果、ハッシュ値を計算するための計算量を少なくすることができる場合がある。
【００２３】
なお、Ｓ２では、パディング部１２は、入力値Ｍの後ろに１を付加し、その後ろに０ビット以上の０を付加し、その後ろにＢ（Ｍ）を付加し、その後ろにＢ１（Ｂ（Ｍ））を付加してパディング値Ｍ’を生成した。しかし、パディング部１２は、入力値Ｍの後ろに付加する０と１とを反転させてもよい。つまり、パディング部１２は、入力値Ｍの後ろに０を付加し、その後ろに０ビット以上の１を付加し、その後ろにＢ（Ｍ）を付加し、その後ろにＢ１（Ｂ（Ｍ））を付加してパディング値Ｍ’を生成してもよい。
また、安全性は低くなるかもしれないが、パディング部１２は、入力値Ｍの後ろに１と０とからなる０ビット以上のビット列を付加し、その後ろにＢ（Ｍ）を付加し、その後ろにＢ１（Ｂ（Ｍ））を付加してパディング値Ｍ’を生成してもよい。
【００２４】
また、Ｓ４では、非特許文献１，２に記載されたハッシュ関数を用いてハッシュ値を計算する例を説明した。しかし、Ｍｅｒｋｌｅ−Ｄａｍｇａｒｄ構造を持つハッシュ関数であれば、他のハッシュ関数を用いてもよい。例えば、ｃｖ［Ｌ］に何らかの計算を行ったものをハッシュ値とするとしてもよい。
【００２５】
また、Ｍｅｒｋｌｅ−Ｄａｍｇａｒｄ構造を持つハッシュ関数として、ＳＨＡ−２５６又はＳＨＡ−２２４を採用することが可能である。この場合、入力値Ｍの最大長は、２６４−１ビットに制限されており、値ｎは５１２ビットである。そのため、ブロック長Ｌは、最大でも２５６ビットになる。つまり、Ｂ（Ｍ）は最大でも５６ビットである。したがって、どのような場合であっても、６ビットあればＢ１（Ｂ（Ｍ））を表現することが可能であるので、Ｔ＝６とすることができる。
【００２６】
同様に、Ｍｅｒｋｌｅ−Ｄａｍｇａｒｄ構造を持つハッシュ関数として、ＳＨＡ−５１２又はＳＨＡ−３８４又はＳＨＡ−５１２／２２４又はＳＨＡ−５１２／２５６を採用することが可能である。この場合、入力値Ｍの最大長は、２１２８−１ビットに制限されており、値ｎは１０２４ビットである。この場合、どのような場合であっても、７ビットあればＢ１（Ｂ（Ｍ））を表現することが可能であるので、Ｔ＝７とすることができる。
【００２７】
実施の形態２．
実施の形態１では、ビット単位に処理する場合の例を説明した。実施の形態２では、バイト単位に処理する場合に例を説明する。
実施の形態２では、実施の形態１と異なる部分を説明する。
【００２８】
ハッシュ値計算装置１０の構成は、図１に示す実施の形態１に係るハッシュ値計算装置１０の構成と同じである。また、ハッシュ値計算装置１０の処理の流れは、図２に示す実施の形態１に係るハッシュ値計算装置１０の処理の流れと同じである。
但し、Ｓ１〜Ｓ４において、実施の形態１ではビット単位に処理が行われていたのに対して、実施の形態２ではバイト単位に処理が行われる点が異なる。
【００２９】
（Ｓ１：任意長値受付処理）
任意長値受付部１１は、入力装置から、任意のバイト長の入力値Ｍの入力を受け付ける。
【００３０】
（Ｓ２：パディング処理）
パディング部１２は、処理装置により、Ｓ１で受け付けられた入力値Ｍに値を付加して（ｎ×Ｌ）バイト長のパディング値Ｍ’を生成する。
具体的には、パディング部１２は、入力値Ｍの後ろに１バイトの０ｘ８０を付加し、その後ろに０バイト以上の０ｘ００を付加し、その後ろにパディング値Ｍ’のブロック長Ｌをバイト表現したＢ（Ｍ）を付加し、その後ろにＢ（Ｍ）のバイト長をバイト表現したＢ１（Ｂ（Ｍ））を付加して、パディング値Ｍ’を生成する。
つまり、Ｍ’＝Ｍ｜｜０ｘ８０｜｜０ｘ００．．．０ｘ００｜｜Ｂ（Ｍ）｜｜Ｂ１（Ｂ（Ｍ））である。
【００３１】
ここで、Ｂ１（Ｂ（Ｍ））は、Ｂ（Ｍ）のバイト長を、予め定められた固定長Ｔバイトでバイト表現されたものである。
また、Ｂ（Ｍ）は、パディング値Ｍ’のブロック長Ｌを、最上位バイトが０ｘ００以外のバイト値となるようにバイト表現したものである。そのため、Ｂ（Ｍ）は、２Ｔ−１バイト以下の可変長である。
また、０ｘ００については、パディング値Ｍ’がｎの倍数となる最少のバイトだけ付加される。
【００３２】
（Ｓ３：分割処理）
分割部１３は、処理装置により、Ｓ２で生成されたパディング値Ｍ’を、先頭から順にｎバイト毎にＬ個の値Ｍ［１］，Ｍ［２］，．．．，Ｍ［Ｌ］に分割する。つまり、Ｍ’＝Ｍ［１］｜｜Ｍ［２］｜｜・・・｜｜Ｍ［Ｌ］である。
【００３３】
（Ｓ４：ハッシュ値計算処理）
ハッシュ値計算部１４は、処理装置により、ｎ＋ｍバイト長の値を入力とし、ｍバイト長の値を出力する圧縮関数ｈを用いて、ｉ＝１，．．．，Ｌの各整数ｉについて順に、ｃｖ［ｉ］＝ｈ（ｃｖ［ｉ−１］，Ｍ［ｉ］）を計算する。つまり、ハッシュ値計算部１４は、ｉ＝１，．．．，Ｌの各整数ｉについて順に、ｃｖ［ｉ−１］及びＭ［ｉ］を入力として圧縮関数ｈを計算する。ここで、ｃｖ［０］は、ｍバイト長の固定値ＩＶである。
そして、ハッシュ値計算部１４は、ｃｖ［Ｌ］をハッシュ値として出力装置へ出力する。
【００３４】
以上のように、実施の形態２に係るハッシュ値計算装置１０では、実施の形態１に係るハッシュ値計算装置１０と同様に、従来よりもパディングするバイト列を短くできる。
そのため、パディング値Ｍ’のブロック長Ｌが短くなり、圧縮関数ｈの計算回数を減らすことができる場合がある。その結果、ハッシュ値を計算するための計算量を少なくすることができる場合がある。
【００３５】
なお、Ｓ２では、パディング部１２は、入力値Ｍの後ろに１バイトの０ｘ８０を付加し、その後ろに０バイト以上の０ｘ００を付加し、その後ろにＢ（Ｍ）を付加し、その後ろにＢ１（Ｂ（Ｍ））を付加してパディング値Ｍ’を生成した。しかし、パディング部１２は、入力値Ｍの後ろに付加する０ｘ８０と０ｘ００とを他のバイト値に変更してもよい。つまり、パディング部１２は、入力値Ｍの後ろに１バイトの何らかのバイト値を付加し、その後ろに前記バイト値とは異なるバイト値を０バイト以上付加し、その後ろにＢ（Ｍ）を付加し、その後ろにＢ１（Ｂ（Ｍ））を付加してパディング値Ｍ’を生成してもよい。
また、安全性は低くなるかもしれないが、パディング部１２は、入力値Ｍの後ろに０バイト以上の何らかのバイト値の列を付加し、その後ろにＢ（Ｍ）を付加し、その後ろにＢ１（Ｂ（Ｍ））を付加してパディング値Ｍ’を生成してもよい。
【００３６】
また、Ｍｅｒｋｌｅ−Ｄａｍｇａｒｄ構造を持つハッシュ関数として、ＳＨＡ−２５６又はＳＨＡ−２２４又はＳＨＡ−５１２又はＳＨＡ−３８４又はＳＨＡ−５１２／２２４又はＳＨＡ−５１２／２５６を採用することが可能である。この場合、どのような場合であっても、１バイトあればＢ１（Ｂ（Ｍ））を表現することが可能であるので、Ｔ＝１とすることができる。
【００３７】
以上に説明したハッシュ値計算装置１０は、例えば、回路やソフトウェア等で構成される。回路で構成される場合には、上記説明における処理装置は、例えば演算回路であり、メモリは、例えばレジスタである。また、ソフトウェアで構成される場合には、上記説明における処理装置は、例えばＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）であり、メモリは、例えばＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）である。また、上記説明における入力装置は、例えばキーボード、通信ボードであり、出力装置は、例えばＬＣＤ（Ｌｉｑｕｉｄ  Ｃｒｙｓｔａｌ  Ｄｉｓｐｌａｙ）等の表示装置、通信ボード、レジスタやＲＡＭ等のメモリである。もちろん、これらに限定されるものではない。
なお、ハッシュ値計算装置１０を回路で構成する場合、上述した「〜部」を「〜回路」と読み変えてもよい。また、上述した「〜部」は、「〜処理」、「〜装置」、「〜機器」、「〜手段」、「〜手順」、「〜機能」と読み替えてもよい。つまり、「〜部」として説明するものは、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）に記憶されたファームウェアで実現されていても構わない。或いは、ソフトウェアのみ、或いは、素子・デバイス・基板・配線などのハードウェアのみ、或いは、ソフトウェアとハードウェアとの組み合わせ、さらには、ファームウェアとの組み合わせで実現されても構わない。
【符号の説明】
【００３８】
１０  ハッシュ値計算装置、１１  任意長値受付部、１２  パディング部、１３  分割部、１４  ハッシュ値計算部。
【図１】
0006257464.tif 000002
【図２】
0006257464.tif 000003
【図３】
0006257464.tif 000004