(57)【要約】【課題】一方向性が破られた理想的な圧縮関数を用いて構成した場合であっても、ランダムオラクルと強識別不可能であるハッシュ関数であって、計算効率がよいハッシュ関数を構成することを目的とする。【解決手段】ハッシュ関数で用いられる圧縮関数への入力値を、入力された値に所定の固定値を付加した値として、ハッシュ関数を構成する。【選択図】図３
2010276629.tif 000002
【特許請求の範囲】
【請求項１】
ｉ個の値ｐ［１］，．．．，値ｐ［ｉ］を入力する既定長値入力部と、
前記既定長値入力部が入力した値ｐ［１］，．．．，値ｐ［ｉ］のうち、ｉ−１個の値ｐ［１］，．．．，値ｐ［ｉ−１］それぞれに対して、固定値ｃｏｎｓｔ［１］，．．．，固定値ｃｏｎｓｔ［ｉ−１］を付加して、値ｘ［１］，．．．，値ｘ［ｉ−１］を生成して記憶装置に記憶する固定値付加部と、
ｊ＝１からｉ−１まで順に、値ｃ［ｊ−１］（値ｃ［０］は固定値ＩＶ１とする）と、前記固定値付加部が生成した値ｘ［ｊ］とを入力として、圧縮関数ｈを計算した結果である値ｃ［ｊ］を得ることにより、値ｃ［ｉ−１］を得て記憶装置に記憶し、
固定値ＩＶ２と、値ｐ［ｉ］に値ｃ［ｉ−１］を付加した値ｘ［ｉ］とを入力として、圧縮関数ｈを計算した結果である値ｃ［ｉ］を得て記憶装置に記憶する圧縮関数計算部と、
前記圧縮関数計算部が得た値ｃ［ｉ］を出力する出力部と
を備えることを特徴とするハッシュ値演算装置。
【請求項２】
前記既定長値入力部は、所定の自然数ｍと、自然数ｍよりも小さい自然数ｎとについて、ｉ個の値であって、ｍ−ｎビット長の値ｐ［１］，．．．，値ｐ［ｉ］を入力し、
前記固定値付加部は、前記既定長値入力部が入力したｍ−ｎビット長の値ｐ［１］，．．．，値ｐ［ｉ］のうち、ｉ−１個の値ｐ［１］，．．．，値ｐ［ｉ−１］それぞれに対して、ｎビット長の固定値ｃｏｎｓｔ［１］，．．．，固定値ｃｏｎｓｔ［ｉ−１］を付加して、ｍビット長の値ｘ［１］，．．．，値ｘ［ｉ−１］を生成し、
前記圧縮関数計算部は、ｊ＝１からｉ−１まで順に、ｎビット長の値ｃ［ｊ−１］（値ｃ［０］はｎビット長の固定値ＩＶ１とする）と、前記固定値付加部が生成したｍビット長の値ｘ［ｊ］とを入力として、圧縮関数ｈを計算した結果であるｎビット長の値ｃ［ｊ］を得ることにより、ｎビット長の値ｃ［ｉ−１］を得て、
ｎビット長の固定値ＩＶ２と、ｍ−ｎビット長の値ｐ［ｉ］にｎビット長の値ｃ［ｉ−１］を付加したｍビット長の値ｘ［ｉ］とを入力として、圧縮関数ｈを計算した結果であるｎビット長の値ｃ［ｉ］を得る
ことを特徴とする請求項１に記載のハッシュ値演算装置。
【請求項３】
前記ハッシュ値演算装置は、さらに、
任意ビット長の値Ｍを入力する任意長値入力部と、
前記任意長値入力部が入力した値Ｍに対して、所定の値を付加してｍ−ｎビット長のｉ倍のビット長の値Ｍ’を生成して記憶装置に記憶するパディング部と、
前記パディング部が生成した値Ｍ’を分割して、ｍ−ｎビット長の値ｐ［１］，．．．，値ｐ［ｉ］を生成して記憶装置に記憶する分割部とを備え、
前記既定長値入力部は、前記分割部が生成した値ｐ［１］，．．．，値ｐ［ｉ］を入力する
ことを特徴とする請求項２に記載のハッシュ値演算装置。
【請求項４】
入力装置が、ｉ個の値ｐ［１］，．．．，値ｐ［ｉ］を入力する既定長値入力ステップと、
処理装置が、前記既定長値入力ステップで入力した値ｐ［１］，．．．，値ｐ［ｉ］のうち、ｉ−１個の値ｐ［１］，．．．，値ｐ［ｉ−１］それぞれに対して、固定値ｃｏｎｓｔ［１］，．．．，固定値ｃｏｎｓｔ［ｉ−１］を付加して、値ｘ［１］，．．．，値ｘ［ｉ−１］を生成する固定値付加ステップと、
処理装置が、ｊ＝１からｉ−１まで順に、値ｃ［ｊ−１］（値ｃ［０］は固定値ＩＶ１とする）と、前記固定値付加ステップで生成した値ｘ［ｊ］とを入力として、圧縮関数ｈを計算した結果である値ｃ［ｊ］を得ることにより、値ｃ［ｉ−１］を得て、
固定値ＩＶ２と、値ｐ［ｉ］に値ｃ［ｉ−１］を付加した値ｘ［ｉ］とを入力として、圧縮関数ｈを計算した結果である値ｃ［ｉ］を得る圧縮関数計算ステップと、
出力装置が、前記圧縮関数計算ステップで得た値ｃ［ｉ］を出力する出力ステップと
を備えることを特徴とするハッシュ値演算方法。
【請求項５】
ｉ個の値ｐ［１］，．．．，値ｐ［ｉ］を入力する既定長値入力処理と、
前記既定長値入力処理で入力した値ｐ［１］，．．．，値ｐ［ｉ］のうち、ｉ−１個の値ｐ［１］，．．．，値ｐ［ｉ−１］それぞれに対して、固定値ｃｏｎｓｔ［１］，．．．，固定値ｃｏｎｓｔ［ｉ−１］を付加して、値ｘ［１］，．．．，値ｘ［ｉ−１］を生成する固定値付加処理と、
ｊ＝１からｉ−１まで順に、値ｃ［ｊ−１］（値ｃ［０］は固定値ＩＶ１とする）と、前記固定値付加処理で生成した値ｘ［ｊ］とを入力として、圧縮関数ｈを計算した結果である値ｃ［ｊ］を得ることにより、値ｃ［ｉ−１］を得て、
固定値ＩＶ２と、値ｐ［ｉ］に値ｃ［ｉ−１］を付加した値ｘ［ｉ］とを入力として、圧縮関数ｈを計算した結果である値ｃ［ｉ］を得る圧縮関数計算処理と、
前記圧縮関数計算処理で得た値ｃ［ｉ］を出力する出力処理と
をコンピュータに実行させることを特徴とするハッシュ値演算プログラム。
【請求項６】
ｉ個の値ｐ［１］，．．．，値ｐ［ｉ］を入力する既定長値入力部と、
前記既定長値入力部が入力した値ｐ［１］，．．．，ｐ［ｉ］と、固定値ｙとを排他的論理和演算の入力として、ｓｕｍ＝ｐ［１］  ｘｏｒ，．．．，ｘｏｒ  ｐ［ｉ］  ｘｏｒ  ｙを計算した結果である値ｓｕｍを得て記憶装置に記憶する排他的論理和計算部と、
前記既定長値入力部が入力した値ｐ［１］，．．．，値ｐ［ｉ］それぞれに対して、固定値ｃｏｎｓｔ［１］，．．．，固定値ｃｏｎｓｔ［ｉ］を付加して、値ｘ［１］，．．．，値ｘ［ｉ］を生成して記憶装置に記憶する固定値付加部と、
ｊ＝１からｉまで順に、値ｃ［ｊ−１］（値ｃ［０］は固定値ＩＶ１とする）と、前記固定値付加部が生成した値ｘ［ｊ］とを入力として、圧縮関数ｈを計算した結果である値ｃ［ｊ］を得ることにより、値ｃ［ｉ］を得て記憶装置に記憶し、
値ｃ［ｉ］と、前記排他的論理和計算部が得た値ｓｕｍに固定値ｃｏｎｓｔ［ｉ＋１］を付加した値ｘ［ｉ＋１］とを入力として、圧縮関数ｈを計算した結果である値ｃ［ｉ＋１］を得て記憶装置に記憶し、
固定値ＩＶ２と、値ｃ［ｉ＋１］に固定値ｃｏｎｓｔ［ｉ＋２］を付加した値ｘ［ｉ＋２］とを入力として、圧縮関数ｈを計算した結果である値ｃ［ｉ＋２］を得て記憶装置に記憶する圧縮関数計算部と、
前記圧縮関数計算部が計算した値ｃ［ｉ＋２］を出力する出力部と
を備えることを特徴とするハッシュ値演算装置。
【請求項７】
前記既定長値入力部は、所定の自然数ｍと、自然数ｍよりも小さい自然数ｓとについて、ｉ個の値であって、ｍ−ｓビット長の値ｐ［１］，．．．，値ｐ［ｉ］を入力し、
前記排他的論理和計算部は、前記既定長値入力部が入力したｍ−ｓビット長の値ｐ［１］，．．．，ｐ［ｉ］と、ｍ−ｓビット長の固定値ｙとを排他的論理和演算の入力として、ｓｕｍ＝ｐ［１］  ｘｏｒ，．．．，ｘｏｒ  ｐ［ｉ］  ｘｏｒ  ｙを計算した結果であるｍ−ｓビット長の値ｓｕｍを得て、
前記固定値付加部は、前記既定長値入力部が入力したｍ−ｓビット長の値ｐ［１］，．．．，値ｐ［ｉ］それぞれに対して、ｓビット長の固定値ｃｏｎｓｔ［１］，．．．，固定値ｃｏｎｓｔ［ｉ］を付加して、ｍビット長の値ｘ［１］，．．．，値ｘ［ｉ］を生成し、
前記圧縮関数計算部は、ｊ＝１からｉまで順に、自然数ｍよりも小さい自然数ｎビット長の値ｃ［ｊ−１］（値ｃ［０］はｎビット長の固定値ＩＶ１とする）と、前記固定値付加部が生成したｍビット長の値ｘ［ｊ］とを入力として、圧縮関数ｈを計算した結果であるｎビット長の値ｃ［ｊ］を得ることにより、ｎビット長の値ｃ［ｉ］を得て、
ｎビット長の値ｃ［ｉ］と、前記排他的論理和計算部が得たｍ−ｓビット長の値ｓｕｍにｓビット長の固定値ｃｏｎｓｔ［ｉ＋１］を付加したｍビット長の値ｘ［ｉ＋１］とを入力として、圧縮関数ｈを計算した結果であるｎビット長の値ｃ［ｉ＋１］を得て、
ｎビット長の固定値ＩＶ２と、ｎビット長の値ｃ［ｉ＋１］にｍ−ｎビット長の固定値ｃｏｎｓｔ［ｉ＋２］を付加したｍビット長の値ｘ［ｉ＋２］とを入力として、圧縮関数ｈを計算した結果であるｎビット長の値ｃ［ｉ＋２］を得る
ことを特徴とする請求項６に記載のハッシュ値演算装置。
【請求項８】
前記ハッシュ値演算装置は、さらに、
任意ビット長の値Ｍを入力する任意長値入力部と、
前記任意長値入力部が入力した値Ｍに対して、所定の値を付加してｍ−ｓビット長のｉ倍のビット長の値Ｍ’を生成して記憶装置に記憶するパディング部と、
前記パディング部が生成した値Ｍ’を分割して、ｍ−ｓビット長の値ｐ［１］，．．．，値ｐ［ｉ］を生成して記憶装置に記憶する分割部とを備え、
前記既定長値入力部は、前記分割部が生成した値ｐ［１］，．．．，値ｐ［ｉ］を入力する
ことを特徴とする請求項７に記載のハッシュ値演算装置。
【請求項９】
入力装置が、ｉ個の値ｐ［１］，．．．，値ｐ［ｉ］を入力する既定長値入力ステップと、
処理装置が、前記既定長値入力ステップで入力した値ｐ［１］，．．．，ｐ［ｉ］と、固定値ｙとを排他的論理和演算の入力として、ｓｕｍ＝ｐ［１］  ｘｏｒ，．．．，ｘｏｒ  ｐ［ｉ］  ｘｏｒ  ｙを計算した結果である値ｓｕｍを得る排他的論理和計算ステップと、
処理装置が、前記既定長値入力ステップで入力した値ｐ［１］，．．．，値ｐ［ｉ］それぞれに対して、固定値ｃｏｎｓｔ［１］，．．．，固定値ｃｏｎｓｔ［ｉ］を付加して、値ｘ［１］，．．．，値ｘ［ｉ］を生成する固定値付加ステップと、
処理装置が、ｊ＝１からｉまで順に、値ｃ［ｊ−１］（値ｃ［０］は固定値ＩＶ１とする）と、前記固定値付加ステップで生成した値ｘ［ｊ］とを入力として、圧縮関数ｈを計算した結果である値ｃ［ｊ］を得ることにより、値ｃ［ｉ］を得て、
値ｃ［ｉ］と、前記排他的論理和計算ステップで得た値ｓｕｍに固定値ｃｏｎｓｔ［ｉ＋１］を付加した値ｘ［ｉ＋１］とを入力として、圧縮関数ｈを計算した結果である値ｃ［ｉ＋１］を得て、
固定値ＩＶ２と、値ｃ［ｉ＋１］に固定値ｃｏｎｓｔ［ｉ＋２］を付加した値ｘ［ｉ＋２］とを入力として、圧縮関数ｈを計算した結果である値ｃ［ｉ＋２］を得る圧縮関数計算ステップと、
出力装置が、前記圧縮関数計算ステップで計算した値ｃ［ｉ＋２］を出力する出力ステップと
を備えることを特徴とするハッシュ値演算方法。
【請求項１０】
ｉ個の値ｐ［１］，．．．，値ｐ［ｉ］を入力する既定長値入力処理と、
前記既定長値入力処理で入力した値ｐ［１］，．．．，ｐ［ｉ］と、固定値ｙとを排他的論理和演算の入力として、ｓｕｍ＝ｐ［１］  ｘｏｒ，．．．，ｘｏｒ  ｐ［ｉ］  ｘｏｒ  ｙを計算した結果である値ｓｕｍを得る排他的論理和計算処理と、
前記既定長値入力処理で入力した値ｐ［１］，．．．，値ｐ［ｉ］それぞれに対して、固定値ｃｏｎｓｔ［１］，．．．，固定値ｃｏｎｓｔ［ｉ］を付加して、値ｘ［１］，．．．，値ｘ［ｉ］を生成する固定値付加処理と、
ｊ＝１からｉまで順に、値ｃ［ｊ−１］（値ｃ［０］は固定値ＩＶ１とする）と、前記固定値付加処理で生成した値ｘ［ｊ］とを入力として、圧縮関数ｈを計算した結果である値ｃ［ｊ］を得ることにより、値ｃ［ｉ］を得て、
値ｃ［ｉ］と、前記排他的論理和計算処理で得た値ｓｕｍに固定値ｃｏｎｓｔ［ｉ＋１］を付加した値ｘ［ｉ＋１］とを入力として、圧縮関数ｈを計算した結果である値ｃ［ｉ＋１］を得て、
固定値ＩＶ２と、値ｃ［ｉ＋１］に固定値ｃｏｎｓｔ［ｉ＋２］を付加した値ｘ［ｉ＋２］とを入力として、圧縮関数ｈを計算した結果である値ｃ［ｉ＋２］を得る圧縮関数計算処理と、
前記圧縮関数計算処理で計算した値ｃ［ｉ＋２］を出力する出力処理と
をコンピュータに実行させることを特徴とするハッシュ値演算プログラム。
【請求項１１】
ｉ＋１個の値ｐ［１］，．．．，値ｐ［ｉ＋１］を入力する既定長値入力部と、
前記既定長値入力部が入力したｉ＋１個の値ｐ［１］，．．．，値ｐ［ｉ＋１］のうち、ｉ個の値ｐ［１］，．．．，ｐ［ｉ］と、固定値ｙとを排他的論理和演算の入力として、ｓｕｍ＝ｐ［１］  ｘｏｒ，．．．，ｘｏｒ  ｐ［ｉ］  ｘｏｒ  ｙを計算した結果である値ｓｕｍを得て記憶装置に記憶する排他的論理和計算部と、
前記既定長値入力部が入力したｉ＋１個の値ｐ［１］，．．．，値ｐ［ｉ＋１］のうち、ｉ個の値ｐ［１］，．．．，値ｐ［ｉ］それぞれに対して、固定値ｃｏｎｓｔ［１］，．．．，固定値ｃｏｎｓｔ［ｉ］を付加して、値ｘ［１］，．．．，値ｘ［ｉ］を生成して記憶装置に記憶する固定値付加部と、
ｊ＝１からｉまで順に、値ｃ［ｊ−１］（値ｃ［０］は固定値ＩＶ１とする）と、前記固定値付加部が生成した値ｘ［ｊ］とを入力として、圧縮関数ｈを計算した結果である値ｃ［ｊ］を得ることにより、値ｃ［ｉ］を得て記憶装置に記憶し、
値ｃ［ｉ］と、前記排他的論理和計算部が得た値ｓｕｍに固定値ｃｏｎｓｔ［ｉ＋１］を付加した値ｘ［ｉ＋１］とを入力として、圧縮関数ｈを計算した結果である値ｃ［ｉ＋１］を得て記憶装置に記憶し、
固定値ＩＶ２と、値ｃ［ｉ＋１］に値ｐ［ｉ＋１］を付加した値ｘ［ｉ＋２］とを入力として、圧縮関数ｈを計算した結果である値ｃ［ｉ＋２］を得て記憶装置に記憶する圧縮関数計算部と、
前記圧縮関数計算部が計算した値ｃ［ｉ＋２］を出力する出力部と
を備えることを特徴とするハッシュ値演算装置。
【請求項１２】
前記既定長値入力部は、所定の自然数ｍと、自然数ｍよりも小さい自然数ｎと、自然数ｍよりも小さい自然数ｓとについて、ｉ個の値であって、ｍ−ｓビット長の値ｐ［１］，．．．，値ｐ［ｉ］と、１個の値であって、ｍ−ｎビットの値ｐ［ｉ＋１］を入力し、
前記排他的論理和計算部は、前記既定長値入力部が入力したｍ−ｓビット長の値ｐ［１］，．．．，ｐ［ｉ］と、ｍ−ｓビット長の固定値ｙとを排他的論理和演算の入力として、ｓｕｍ＝ｐ［１］  ｘｏｒ，．．．，ｘｏｒ  ｐ［ｉ］  ｘｏｒ  ｙを計算した結果であるｍ−ｓビット長の値ｓｕｍを得て、
前記固定値付加部は、前記既定長値入力部が入力したｍ−ｓビット長の値ｐ［１］，．．．，値ｐ［ｉ］それぞれに対して、ｓビット長の固定値ｃｏｎｓｔ［１］，．．．，固定値ｃｏｎｓｔ［ｉ］を付加して、ｍビット長の値ｘ［１］，．．．，値ｘ［ｉ］を生成し、
前記圧縮関数計算部は、ｊ＝１からｉまで順に、ｎビット長の値ｃ［ｊ−１］（値ｃ［０］はｎビット長の固定値ＩＶ１とする）と、前記固定値付加部が生成したｍビット長の値ｘ［ｊ］とを入力として、圧縮関数ｈを計算した結果であるｎビット長の値ｃ［ｊ］を得ることにより、ｎビット長の値ｃ［ｉ］を得て、
ｎビット長の値ｃ［ｉ］と、前記排他的論理和計算部が得たｍ−ｓビット長の値ｓｕｍにｓビット長の固定値ｃｏｎｓｔ［ｉ＋１］を付加したｍビット長の値ｘ［ｉ＋１］とを入力として、圧縮関数ｈを計算した結果であるｎビット長の値ｃ［ｉ＋１］を得て、
ｎビット長の固定値ＩＶ２と、ｎビット長の値ｃ［ｉ＋１］にｍ−ｎビット長の値ｐ［ｉ＋１］を付加したｍビット長の値ｘ［ｉ＋２］とを入力として、圧縮関数ｈを計算した結果であるｎビット長の値ｃ［ｉ＋２］を得る
ことを特徴とする請求項１１に記載のハッシュ値演算装置。
【請求項１３】
前記ハッシュ値演算装置は、さらに、
任意ビット長の値Ｍを入力する任意長値入力部と、
前記任意長値入力部が入力した値Ｍに対して、所定の値を付加して（（ｍ−ｓ）×ｉ＋（ｍ−ｎ））ビット長の値Ｍ’を生成して記憶装置に記憶するパディング部と、
前記パディング部が生成した値Ｍ’を分割して、ｍ−ｓビット長の値ｐ［１］，．．．，値ｐ［ｉ］とｍ−ｎビット長の値ｐ［ｉ＋１］とを生成して記憶装置に記憶する分割部とを備え、
前記既定長値入力部は、前記分割部が生成した値ｐ［１］，．．．，値ｐ［ｉ］と値ｐ［ｉ＋１］とを入力する
ことを特徴とする請求項１２に記載のハッシュ値演算装置。
【請求項１４】
入力装置が、ｉ＋１個の値ｐ［１］，．．．，値ｐ［ｉ＋１］を入力する既定長値入力ステップと、
処理装置が、前記既定長値入力ステップで入力したｉ＋１個の値ｐ［１］，．．．，値ｐ［ｉ＋１］のうち、ｉ個の値ｐ［１］，．．．，ｐ［ｉ］と、固定値ｙとを排他的論理和演算の入力として、ｓｕｍ＝ｐ［１］  ｘｏｒ，．．．，ｘｏｒ  ｐ［ｉ］  ｘｏｒ  ｙを計算した結果である値ｓｕｍを得る排他的論理和計算ステップと、
処理装置が、前記既定長値入力ステップで入力したｉ＋１個の値ｐ［１］，．．．，値ｐ［ｉ＋１］のうち、ｉ個の値ｐ［１］，．．．，値ｐ［ｉ］それぞれに対して、固定値ｃｏｎｓｔ［１］，．．．，固定値ｃｏｎｓｔ［ｉ］を付加して、値ｘ［１］，．．．，値ｘ［ｉ］を生成する固定値付加ステップと、
処理装置が、ｊ＝１からｉまで順に、値ｃ［ｊ−１］（値ｃ［０］は固定値ＩＶ１とする）と、前記固定値付加ステップで生成した値ｘ［ｊ］とを入力として、圧縮関数ｈを計算した結果である値ｃ［ｊ］を得ることにより、値ｃ［ｉ］を得て、
値ｃ［ｉ］と、前記排他的論理和計算ステップで得た値ｓｕｍに固定値ｃｏｎｓｔ［ｉ＋１］を付加した値ｘ［ｉ＋１］とを入力として、圧縮関数ｈを計算した結果である値ｃ［ｉ＋１］を得て、
固定値ＩＶ２と、値ｃ［ｉ＋１］に値ｐ［ｉ＋１］を付加した値ｘ［ｉ＋２］とを入力として、圧縮関数ｈを計算した結果である値ｃ［ｉ＋２］を得る圧縮関数計算ステップと、
出力装置が、前記圧縮関数計算ステップで計算した値ｃ［ｉ＋２］を出力する出力ステップと
を備えることを特徴とするハッシュ値演算方法。
【請求項１５】
ｉ＋１個の値ｐ［１］，．．．，値ｐ［ｉ＋１］を入力する既定長値入力処理と、
前記既定長値入力処理で入力したｉ＋１個の値ｐ［１］，．．．，値ｐ［ｉ＋１］のうち、ｉ個の値ｐ［１］，．．．，ｐ［ｉ］と、固定値ｙとを排他的論理和演算の入力として、ｓｕｍ＝ｐ［１］  ｘｏｒ，．．．，ｘｏｒ  ｐ［ｉ］  ｘｏｒ  ｙを計算した結果である値ｓｕｍを得る排他的論理和計算処理と、
前記既定長値入力処理で入力したｉ＋１個の値ｐ［１］，．．．，値ｐ［ｉ＋１］のうち、ｉ個の値ｐ［１］，．．．，値ｐ［ｉ］それぞれに対して、固定値ｃｏｎｓｔ［１］，．．．，固定値ｃｏｎｓｔ［ｉ］を付加して、値ｘ［１］，．．．，値ｘ［ｉ］を生成する固定値付加処理と、
ｊ＝１からｉまで順に、値ｃ［ｊ−１］（値ｃ［０］は固定値ＩＶ１とする）と、前記固定値付加処理で生成した値ｘ［ｊ］とを入力として、圧縮関数ｈを計算した結果である値ｃ［ｊ］を得ることにより、値ｃ［ｉ］を得て、
値ｃ［ｉ］と、前記排他的論理和計算処理で得た値ｓｕｍに固定値ｃｏｎｓｔ［ｉ＋１］を付加した値ｘ［ｉ＋１］とを入力として、圧縮関数ｈを計算した結果である値ｃ［ｉ＋１］を得て、
固定値ＩＶ２と、値ｃ［ｉ＋１］に値ｐ［ｉ＋１］を付加した値ｘ［ｉ＋２］とを入力として、圧縮関数ｈを計算した結果である値ｃ［ｉ＋２］を得る圧縮関数計算処理と、
前記圧縮関数計算処理で計算した値ｃ［ｉ＋２］を出力する出力処理と
をコンピュータに実行させることを特徴とするハッシュ値演算プログラム。
【請求項１６】
ハッシュ値を計算するハッシュ値演算装置であり、
ｉ個の値ｐ［１］，．．．，値ｐ［ｉ］を入力する既定長値入力部と、
前記既定長値入力部が入力した値ｐ［１］，．．．，値ｐ［ｉ］それぞれに対して、固定値ｃｏｎｓｔ［１］，．．．，固定値ｃｏｎｓｔ［ｉ］を付加して、値ｘ［１］，．．．，値ｘ［ｉ］を生成して記憶装置に記憶する固定値付加部と、
ｊ＝１からｉ−１まで順に、値ｃ［ｊ−１］（値ｃ［０］は固定値ＩＶ１とする）と、前記固定値付加部が生成した値ｘ［ｊ］とを入力として、圧縮関数ｈを計算した結果である値ｃ［ｊ］を得ることにより、値ｃ［ｉ−１］を得て記憶装置に記憶する圧縮関数計算部と、
前記圧縮関数計算部が得た値ｃ［ｉ−１］を入力として、置換関数πを計算した結果である値ｃ’［ｉ−１］を得て記憶装置に記憶する置換関数計算部とを備え、
前記圧縮関数計算部は、さらに、前記置換関数計算部が得た値ｃ’［ｉ−１］と値ｘ［ｉ］とを入力として、圧縮関数ｈを計算した結果である値ｃ［ｉ］を得て記憶装置に記憶し、
前記ハッシュ値演算装置は、さらに、
前記圧縮関数計算部が計算した値ｃ［ｉ］を出力する出力部
を備えることを特徴とするハッシュ値演算装置。
【請求項１７】
前記既定長値入力部は、所定の自然数ｍと、自然数ｍよりも小さい自然数ｎとについて、ｉ個の値であって、ｍ−ｎビット長の値ｐ［１］，．．．，値ｐ［ｉ］を入力し、
前記固定値付加部は、前記既定長値入力部が入力したｍ−ｎビット長の値ｐ［１］，．．．，値ｐ［ｉ］それぞれに対して、ｎビット長の固定値ｃｏｎｓｔ［１］，．．．，固定値ｃｏｎｓｔ［ｉ］を付加して、ｍビット長の値ｘ［１］，．．．，値ｘ［ｉ］を生成し、
前記圧縮関数計算部は、ｊ＝１からｉ−１まで順に、ｎビット長の値ｃ［ｊ−１］（値ｃ［０］はｎビット長の固定値ＩＶ１とする）と、前記固定値付加部が生成したｍビット長の値ｘ［ｊ］とを入力として、圧縮関数ｈを計算した結果であるｎビット長の値ｃ［ｊ］を得ることにより、ｎビット長の値ｃ［ｉ−１］を得て、
前記置換関数計算部は、前記圧縮関数計算部が得たｎビット長の値ｃ［ｉ−１］を入力として、置換関数πを計算した結果であるｎビット長の値ｃ’［ｉ−１］を得て、
前記圧縮関数計算部は、さらに、前記置換関数計算部が得たｎビット長の値ｃ’［ｉ−１］とｍビット長の値ｘ［ｉ］とを入力として、圧縮関数ｈを計算した結果であるｎビット長の値ｃ［ｉ］を得る
ことを特徴とする請求項１６に記載のハッシュ値演算装置。
【請求項１８】
前記ハッシュ値演算装置は、さらに、
任意ビット長の値Ｍを入力する任意長値入力部と、
前記任意長値入力部が入力した値Ｍに対して、所定の値を付加してｍ−ｎビット長のｉ倍のビット長の値Ｍ’を生成して記憶装置に記憶するパディング部と、
前記パディング部が生成した値Ｍ’を分割して、ｍ−ｎビット長の値ｐ［１］，．．．，値ｐ［ｉ］を生成して記憶装置に記憶する分割部とを備え、
前記既定長値入力部は、前記分割部が生成した値ｐ［１］，．．．，値ｐ［ｉ］を入力する
ことを特徴とする請求項１７に記載のハッシュ値演算装置。
【請求項１９】
ハッシュ値を計算するハッシュ値演算方法であり、
入力装置が、ｉ個の値ｐ［１］，．．．，値ｐ［ｉ］を入力する既定長値入力ステップと、
処理装置が、前記既定長値入力ステップで入力した値ｐ［１］，．．．，値ｐ［ｉ］それぞれに対して、固定値ｃｏｎｓｔ［１］，．．．，固定値ｃｏｎｓｔ［ｉ］を付加して、値ｘ［１］，．．．，値ｘ［ｉ］を生成する固定値付加ステップと、
処理装置が、ｊ＝１からｉ−１まで順に、値ｃ［ｊ−１］（値ｃ［０］は固定値ＩＶ１とする）と、前記固定値付加ステップで生成した値ｘ［ｊ］とを入力として、圧縮関数ｈを計算した結果である値ｃ［ｊ］を得ることにより、値ｃ［ｉ−１］を得る圧縮関数計算ステップと、
処理装置が、前記圧縮関数計算ステップで得た値ｃ［ｉ−１］を入力として、置換関数πを計算した結果である値ｃ’［ｉ−１］を得る置換関数計算ステップとを備え、
前記圧縮関数計算ステップでは、さらに、処理装置が、前記置換関数計算ステップで得た値ｃ’［ｉ−１］と値ｘ［ｉ］とを入力として、圧縮関数ｈを計算した結果である値ｃ［ｉ］を得て、
前記ハッシュ値演算方法は、さらに、
出力装置が、前記圧縮関数計算ステップで計算した値ｃ［ｉ］を出力する出力ステップ
を備えることを特徴とするハッシュ値演算方法。
【請求項２０】
ハッシュ値を計算するハッシュ値演算プログラムであり、
ｉ個の値ｐ［１］，．．．，値ｐ［ｉ］を入力する既定長値入力処理と、
前記既定長値入力処理で入力した値ｐ［１］，．．．，値ｐ［ｉ］それぞれに対して、固定値ｃｏｎｓｔ［１］，．．．，固定値ｃｏｎｓｔ［ｉ］を付加して、値ｘ［１］，．．．，値ｘ［ｉ］を生成する固定値付加処理と、
ｊ＝１からｉ−１まで順に、値ｃ［ｊ−１］（値ｃ［０］は固定値ＩＶ１とする）と、前記固定値付加処理で生成した［ｊ］とを入力として、圧縮関数ｈを計算した結果である値ｃ［ｊ］を得ることにより、値ｃ［ｉ−１］を得る圧縮関数計算処理と、
前記圧縮関数計算処理で得た値ｃ［ｉ−１］を入力として、置換関数πを計算した結果である値ｃ’［ｉ−１］を得る置換関数計算処理とをコンピュータに実行させ、
前記圧縮関数計算処理では、さらに、前記置換関数計算処理で得た値ｃ’［ｉ−１］と値ｘ［ｉ］とを入力として、圧縮関数ｈを計算した結果である値ｃ［ｉ］を得て、
前記ハッシュ値演算プログラムは、さらに、
前記圧縮関数計算処理で計算した値ｃ［ｉ］を出力する出力処理
をコンピュータに実行させることを特徴とするハッシュ値演算プログラム。
【請求項２１】
ハッシュ値を計算するハッシュ値演算装置であり、
ｉ個の値ｐ［１］，．．．，値ｐ［ｉ］を入力する既定長値入力部と、
前記既定長値入力部が入力した値ｐ［１］，．．．，値ｐ［ｉ］と、固定値ｙとを排他的論理和演算の入力として、ｓｕｍ＝ｐ［１］  ｘｏｒ，．．．，ｘｏｒ  ｐ［ｉ］  ｘｏｒ  ｙを計算した結果である値ｓｕｍを得て記憶装置に記憶する排他的論理和計算部と、
前記既定長値入力部が入力した値ｐ［１］，．．．，値ｐ［ｉ］それぞれに対して、固定値ｃｏｎｓｔ［１］，．．．，固定値ｃｏｎｓｔ［ｉ］を付加して、値ｘ［１］，．．．，値ｘ［ｉ］を生成して記憶装置に記憶する固定値付加部と、
ｊ＝１からｉまで順に、値ｃ［ｊ−１］（値ｃ［０］は固定値ＩＶ１とする）と、前記固定値付加部が生成した値ｘ［ｊ］とを入力として、圧縮関数ｈを計算した結果である値ｃ［ｊ］を得ることにより、値ｃ［ｉ］を得て記憶装置に記憶する圧縮関数計算部と、
前記圧縮関数計算部が得た値ｃ［ｉ］を入力として、置換関数πを計算した結果である値ｃ’［ｉ］を得て記憶装置に記憶する置換関数計算部とを備え、
前記圧縮関数計算部は、さらに、前記置換関数計算部が得た値ｃ’［ｉ］と、前記排他的論理和計算部が得た値ｓｕｍに固定値ｃｏｎｓｔ［ｉ＋１］を付加したｘ［ｉ＋１］を入力として、圧縮関数ｈを計算した結果である値ｃ［ｉ＋１］を得て記憶装置に記憶し、
前記ハッシュ値演算装置は、さらに、
前記圧縮関数計算部が計算した値ｃ［ｉ＋１］を出力する出力部
を備えることを特徴とするハッシュ値演算装置。
【請求項２２】
前記既定長値入力部は、所定の自然数ｍと、自然数ｍよりも小さい自然数ｓとについて、ｉ個の値であって、ｍ−ｓビット長の値ｐ［１］，．．．，値ｐ［ｉ］を入力し、
前記排他的論理和計算部は、前記既定長値入力部が入力したｍ−ｓビット長の値ｐ［１］，．．．，値ｐ［ｉ］と、ｍ−ｓビット長の固定値ｙとを排他的論理和演算の入力として、ｓｕｍ＝ｐ［１］  ｘｏｒ，．．．，ｘｏｒ  ｐ［ｉ］  ｘｏｒ  ｙを計算した結果であるｍ−ｓビット長の値ｓｕｍを得て、
前記固定値付加部は、前記既定長値入力部が入力したｍ−ｓビット長の値ｐ［１］，．．．，値ｐ［ｉ］それぞれに対して、ｓビット長の固定値ｃｏｎｓｔ［１］，．．．，固定値ｃｏｎｓｔ［ｉ］を付加して、ｍビット長の値ｘ［１］，．．．，値ｘ［ｉ］を生成し、
前記圧縮関数計算部は、ｊ＝１からｉまで順に、自然数ｍよりも小さい自然数ｎビット長の値ｃ［ｊ−１］（値ｃ［０］はｎビット長の固定値ＩＶ１とする）と、前記固定値付加部が生成したｍビット長の値ｘ［ｊ］とを入力として、圧縮関数ｈを計算した結果であるｎビット長の値ｃ［ｊ］を得ることにより、ｎビット長の値ｃ［ｉ］を得て、
前記置換関数計算部は、前記圧縮関数計算部が得たｎビット長の値ｃ［ｉ］を入力として、置換関数πを計算した結果であるｎビット長の値ｃ’［ｉ］を得て、
前記圧縮関数計算部は、さらに、前記置換関数計算部が得たｎビット長の値ｃ’［ｉ］と、前記排他的論理和計算部が得たｍ−ｓビット長の値ｓｕｍにｓビット長の固定値ｃｏｎｓｔ［ｉ＋１］を付加したｍビット長のｘ［ｉ＋１］を入力として、圧縮関数ｈを計算した結果であるｎビット長の値ｃ［ｉ＋１］を得る
を備えることを特徴とする請求項２１に記載のハッシュ値演算装置。
【請求項２３】
前記ハッシュ値演算装置は、さらに、
任意ビット長の値Ｍを入力する任意長値入力部と、
前記任意長値入力部が入力した値Ｍに対して、所定の値を付加してｍ−ｓビット長のｉ倍のビット長の値Ｍ’を生成して記憶装置に記憶するパディング部と、
前記パディング部が生成した値Ｍ’を分割して、ｍ−ｓビット長の値ｐ［１］，．．．，値ｐ［ｉ］を生成して記憶装置に記憶する分割部とを備え、
前記既定長値入力部は、前記分割部が生成した値ｐ［１］，．．．，値ｐ［ｉ］を入力する
ことを特徴とする請求項２２に記載のハッシュ値演算装置。
【請求項２４】
ハッシュ値を計算するハッシュ値演算方法であり、
入力装置が、ｉ個の値ｐ［１］，．．．，値ｐ［ｉ］を入力する既定長値入力ステップと、
処理装置が、前記既定長値入力ステップで入力した値ｐ［１］，．．．，値ｐ［ｉ］と、固定値ｙとを排他的論理和演算の入力として、ｓｕｍ＝ｐ［１］  ｘｏｒ，．．．，ｘｏｒ  ｐ［ｉ］  ｘｏｒ  ｙを計算した結果である値ｓｕｍを得る排他的論理和計算ステップと、
処理装置が、前記既定長値入力ステップで入力した値ｐ［１］，．．．，値ｐ［ｉ］それぞれに対して、固定値ｃｏｎｓｔ［１］，．．．，固定値ｃｏｎｓｔ［ｉ］を付加して、値ｘ［１］，．．．，値ｘ［ｉ］を生成する固定値付加ステップと、
処理装置が、ｊ＝１からｉまで順に、値ｃ［ｊ−１］（値ｃ［０］は固定値ＩＶ１とする）と、前記固定値付加ステップで生成した値ｘ［ｊ］とを入力として、圧縮関数ｈを計算した結果である値ｃ［ｊ］を得ることにより、値ｃ［ｉ］を得る圧縮関数計算ステップと、
処理装置が、前記圧縮関数計算ステップで得た値ｃ［ｉ］を入力として、置換関数πを計算した結果である値ｃ’［ｉ］を得る置換関数計算ステップとを備え、
前記圧縮関数計算ステップでは、さらに、処理装置が、前記置換関数計算ステップで得た値ｃ’［ｉ］と、前記排他的論理和計算ステップで得た値ｓｕｍに固定値ｃｏｎｓｔ［ｉ＋１］を付加したｘ［ｉ＋１］を入力として、圧縮関数ｈを計算した結果である値ｃ［ｉ＋１］を得て、
前記ハッシュ値演算方法は、さらに、
出力装置が、前記圧縮関数計算ステップで計算した値ｃ［ｉ＋１］を出力する出力ステップ
を備えることを特徴とするハッシュ値演算方法。
【請求項２５】
ハッシュ値を計算するハッシュ値演算プログラムであり、
ｉ個の値ｐ［１］，．．．，値ｐ［ｉ］を入力する既定長値入力処理と、
前記既定長値入力処理で入力した値ｐ［１］，．．．，値ｐ［ｉ］と、固定値ｙとを排他的論理和演算の入力として、ｓｕｍ＝ｐ［１］  ｘｏｒ，．．．，ｘｏｒ  ｐ［ｉ］  ｘｏｒ  ｙを計算した結果である値ｓｕｍを得る排他的論理和計算処理と、
前記既定長値入力処理で入力した値ｐ［１］，．．．，値ｐ［ｉ］それぞれに対して、固定値ｃｏｎｓｔ［１］，．．．，固定値ｃｏｎｓｔ［ｉ］を付加して、値ｘ［１］，．．．，値ｘ［ｉ］を生成する固定値付加処理と、
ｊ＝１からｉまで順に、値ｃ［ｊ−１］（値ｃ［０］は固定値ＩＶ１とする）と、前記固定値付加処理で生成した値ｘ［ｊ］とを入力として、圧縮関数ｈを計算した結果である値ｃ［ｊ］を得ることにより、値ｃ［ｉ］を得る圧縮関数計算処理と、
前記圧縮関数計算処理で得た値ｃ［ｉ］を入力として、置換関数πを計算した結果である値ｃ’［ｉ］を得る置換関数計算処理とをコンピュータに実行させ、
前記圧縮関数計算処理は、さらに、前記置換関数計算処理で得た値ｃ’［ｉ］と、前記排他的論理和計算処理で得た値ｓｕｍに固定値ｃｏｎｓｔ［ｉ＋１］を付加したｘ［ｉ＋１］を入力として、圧縮関数ｈを計算した結果である値ｃ［ｉ＋１］を得て、
前記ハッシュ値演算プログラムは、さらに、
前記圧縮関数計算処理で計算した値ｃ［ｉ＋１］を出力する出力処理
をコンピュータに実行させることを特徴とするハッシュ値演算プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、例えば、効率的にハッシュ値を計算する技術に関する。
【背景技術】
【０００２】
非特許文献１には、一方向性が破られた理想的な圧縮関数（ＷＦＩＬＲＯ（Ｗｅａｋｅｎｅｄ  Ｆｉｘｅｄ  Ｉｎｐｕｔ  Ｌｅｎｇｔｈ  Ｒａｎｄｏｍ  Ｏｒａｃｌｅ））を用いて構成した場合であっても、ランダムオラクルといわゆる強識別不可能なハッシュ関数であるジッパーハッシュ関数（ｚｉｐｐｅｒハッシュ関数）についての記載がある。
【０００３】
非特許文献２には、一方向性が破られた理想的な圧縮関数を用いて構成した場合であっても、ランダムオラクルといわゆる強識別不可能なハッシュ関数であるダブルパイプハッシュ関数（ｄｏｕｂｌｅ  ｐｉｐｅハッシュ関数）についての記載がある。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Ｍｏｓｅｓ  Ｌｉｓｋｏｖ：  Ｃｏｎｓｔｒｕｃｔｉｎｇ  ａｎ  Ｉｄｅａｌ  Ｈａｓｈ  Ｆｕｎｃｔｉｏｎ  ｆｒｏｍ  Ｗｅａｋ  Ｉｄｅａｌ  Ｃｏｍｐｒｅｓｓｉｏｎ  Ｆｕｎｃｔｉｏｎｓ．  Ｓｅｌｅｃｔｅｄ  Ａｒｅａｓ  ｉｎ  Ｃｒｙｐｔｏｇｒａｐｈｙ  ２００６：  ３５８−３７５
【非特許文献２】Ｓｔｅｆａｎ  Ｌｕｃｋｓ：  Ａ  Ｆａｉｌｕｒｅ−Ｆｒｉｅｎｄｌｙ  Ｄｅｓｉｇｎ  Ｐｒｉｎｃｉｐｌｅ  ｆｏｒ  Ｈａｓｈ  Ｆｕｎｃｔｉｏｎｓ．  ＡＳＩＡＣＲＹＰＴ  ２００５：  ４７４−４９４
【非特許文献３】Ｍｉｈｉｒ  Ｂｅｌｌａｒｅ，  Ｔｈｏｍａｓ  Ｒｉｓｔｅｎｐａｒｔ：  Ｍｕｌｔｉ−Ｐｒｏｐｅｒｔｙ−Ｐｒｅｓｅｒｖｉｎｇ  Ｈａｓｈ  Ｄｏｍａｉｎ  Ｅｘｔｅｎｓｉｏｎ  ａｎｄ  ｔｈｅ  ＥＭＤ  Ｔｒａｎｓｆｏｒｍ．  ＡＳＩＡＣＲＹＰＴ  ２００６：  ２９９−３１４
【非特許文献４】Ｓｈｏｉｃｈｉ  Ｈｉｒｏｓｅ，  Ｊｅ  Ｈｏｎｇ  Ｐａｒｋ，  Ａａｒａｍ  Ｙｕｎ：  Ａ  Ｓｉｍｐｌｅ  Ｖａｒｉａｎｔ  ｏｆ  ｔｈｅ  Ｍｅｒｋｌｅ−Ｄａｍｇａｒｄ  Ｓｃｈｅｍｅ  ｗｉｔｈ  ａ  Ｐｅｒｍｕｔａｔｉｏｎ．  ＡＳＩＡＣＲＹＰＴ  ２００７：  １１３−１２９
【非特許文献５】Ｕｅｌｉ  Ｍａｕｒｅｒ，  Ｒｅｎａｔｏ  Ｒｅｎｎｅｒ，  ａｎｄ  Ｃｌｅｍｅｎｓ  Ｈｏｌｅｎｓｔｅｉｎｉｎｄｉｆｆｅｒｅｎｔｉａｂｉｌｉｔｙ  ｉｍｐｏｓｓｉｂｉｌｉｔｙ  ｒｅｓｕｌｔｓ  ｏｎ  ｒｅｄｕｃｔｉｏｎｓ  ａｎｄ  ａｐｐｌｉｃａｔｉｏｎｓｔｏ  ｔｈｅ  ｒａｎｄｏｍ  ｏｒａｃｌｅ  ｍｅｔｈｏｄｏｌｏｇｙＴＣＣ  ２００４，  ｐｐ  ２１−３９，  ＬＮＣＳ  ２９５１  Ｓｐｒｉｎｇｅｒ  ２００４，  ＩＳＢＮ  ３−５４０−２１０００−８
【非特許文献６】Ｒａｌｐｈ  Ｃ．  Ｍｅｒｋｌｅ／Ｏｎｅ  Ｗａｙ  Ｈａｓｈ  Ｆｕｎｃｔｉｏｎｓ  ａｎｄ  ＤＥＳ／，Ｃｒｙｐｔｏ  １９８９，  ｐｐ  ４２８−４４６，  ＬＮＣＳ  ４３５  Ｓｐｒｉｎｇｅｒ  １９９０，  ＩＳＢＮ  ３−５４０−９７３１７−６
【発明の概要】
【発明が解決しようとする課題】
【０００５】
非特許文献１，２に記載されたジッパーハッシュ関数とダブルパイプハッシュ関数とは、一方向性が破られた理想的な圧縮関数を用い、ランダムオラクルと強識別不可能なハッシュ関数であるものの、計算効率が悪い。
この発明は、例えば、一方向性が破られた理想的な圧縮関数を用いて構成した場合であっても、ランダムオラクルと強識別不可能であるハッシュ関数であって、ジッパーハッシュ関数やダブルパイプハッシュ関数よりも計算効率がよいハッシュ関数を構成することを目的とする。
【課題を解決するための手段】
【０００６】
この発明に係るハッシュ値演算装置は、例えば、
ｉ個の値ｐ［１］，．．．，値ｐ［ｉ］を入力する既定長値入力部と、
前記既定長値入力部が入力した値ｐ［１］，．．．，値ｐ［ｉ］のうち、ｉ−１個の値ｐ［１］，．．．，値ｐ［ｉ−１］それぞれに対して、固定値ｃｏｎｓｔ［１］，．．．，固定値ｃｏｎｓｔ［ｉ−１］を付加して、値ｘ［１］，．．．，値ｘ［ｉ−１］を生成して記憶装置に記憶する固定値付加部と、
ｊ＝１からｉ−１まで順に、値ｃ［ｊ−１］（値ｃ［０］は固定値ＩＶ１とする）と、前記固定値付加部が生成した値ｘ［ｊ］とを入力として、圧縮関数ｈを計算した結果である値ｃ［ｊ］を得ることにより、値ｃ［ｉ−１］を得て記憶装置に記憶し、
固定値ＩＶ２と、値ｐ［ｉ］に値ｃ［ｉ−１］を付加した値ｘ［ｉ］とを入力として、圧縮関数ｈを計算した結果である値ｃ［ｉ］を得て記憶装置に記憶する圧縮関数計算部と、
前記圧縮関数計算部が得た値ｃ［ｉ］を出力する出力部と
を備えることを特徴とする。
【発明の効果】
【０００７】
この発明に係るハッシュ値演算装置では、圧縮関数への入力値に固定値を付加しする。これにより、一方向性が破られた理想的な圧縮関数を用いて構成した場合であっても、ランダムオラクルと強識別不可能であるハッシュ関数を構成することができる。そして、このハッシュ関数は、ジッパーハッシュ関数やダブルパイプハッシュ関数よりも効率がよい。
【図面の簡単な説明】
【０００８】
【図１】実施の形態１に係るハッシュ値演算装置１０の機能を示す機能ブロック図。
【図２】図１に示すハッシュ値演算装置１０の動作を示すフローチャート。
【図３】図１に示すハッシュ値演算装置１０により実現されるハッシュ関数の構造図。
【図４】値ｐ［１］，．．．，値ｐ［ｉ］を生成する機能を追加した実施の形態１に係るハッシュ値演算装置１０の機能を示す機能ブロック図。
【図５】図４に示すハッシュ値演算装置１０の動作を示すフローチャート。
【図６】図４に示すハッシュ値演算装置１０により実現されるハッシュ関数の構造図。
【図７】所定のパディング処理を行う場合の図４に示すハッシュ値演算装置１０により実現されるハッシュ関数の構造図。
【図８】圧縮関数としてＳＨＡ−２５６を用いる場合の図４に示すハッシュ値演算装置１０により実現されるハッシュ関数の構造図。
【図９】実施の形態２に係るハッシュ値演算装置１０の機能を示す機能ブロック図。
【図１０】図９に示すハッシュ値演算装置１０の動作を示すフローチャート。
【図１１】図９に示すハッシュ値演算装置１０により実現されるハッシュ関数の構造図。
【図１２】値ｐ［１］，．．．，値ｐ［ｉ］を生成する機能を追加した実施の形態２に係るハッシュ値演算装置１０の機能を示す機能ブロック図。
【図１３】図１２に示すハッシュ値演算装置１０の動作を示すフローチャート。
【図１４】図１２に示すハッシュ値演算装置１０により実現されるハッシュ関数の構造図。
【図１５】所定のパディング処理を行う場合の図１２に示すハッシュ値演算装置１０により実現されるハッシュ関数の構造図。
【図１６】所定のパディング処理を行う場合の図１２に示すハッシュ値演算装置１０により実現されるハッシュ関数の構造図。
【図１７】圧縮関数としてＳＨＡ−２５６を用いる場合の図１２に示すハッシュ値演算装置１０により実現されるハッシュ関数の構造図。
【図１８】実施の形態３に係るハッシュ値演算装置１０の機能を示す機能ブロック図。
【図１９】図１８に示すハッシュ値演算装置１０の動作を示すフローチャート。
【図２０】図１８に示すハッシュ値演算装置１０により実現されるハッシュ関数の構造図。
【図２１】値ｐ［１］，．．．，値ｐ［ｉ＋１］を生成する機能を追加した実施の形態３に係るハッシュ値演算装置１０の機能を示す機能ブロック図。
【図２２】図２１に示すハッシュ値演算装置１０の動作を示すフローチャート。
【図２３】図２１に示すハッシュ値演算装置１０により実現されるハッシュ関数の構造図。
【図２４】所定のパディング処理を行う場合の図２１に示すハッシュ値演算装置１０により実現されるハッシュ関数の構造図。
【図２５】圧縮関数としてＳＨＡ−２５６を用いる場合の図２１に示すハッシュ値演算装置１０により実現されるハッシュ関数の構造図。
【図２６】実施の形態４に係るハッシュ値演算装置１０の機能を示す機能ブロック図。
【図２７】図２６に示すハッシュ値演算装置１０の動作を示すフローチャート。
【図２８】図２６に示すハッシュ値演算装置１０により実現されるハッシュ関数の構造図。
【図２９】値ｐ［１］，．．．，値ｐ［ｉ］を生成する機能を追加した実施の形態２に係るハッシュ値演算装置１０の機能を示す機能ブロック図。
【図３０】図２９に示すハッシュ値演算装置１０の動作を示すフローチャート。
【図３１】図２９に示すハッシュ値演算装置１０により実現されるハッシュ関数の構造図。
【図３２】所定のパディング処理を行う場合の図２９に示すハッシュ値演算装置１０により実現されるハッシュ関数の構造図。
【図３３】圧縮関数としてＳＨＡ−２５６を用いる場合の図２９に示すハッシュ値演算装置１０により実現されるハッシュ関数の構造図。
【図３４】実施の形態５に係るハッシュ値演算装置１０の機能を示す機能ブロック図。
【図３５】図３４に示すハッシュ値演算装置１０の動作を示すフローチャート。
【図３６】図３４に示すハッシュ値演算装置１０により実現されるハッシュ関数の構造図。
【図３７】値ｐ［１］，．．．，値ｐ［ｉ］を生成する機能を追加した実施の形態５に係るハッシュ値演算装置１０の機能を示す機能ブロック図。
【図３８】図３７に示すハッシュ値演算装置１０の動作を示すフローチャート。
【図３９】図３７に示すハッシュ値演算装置１０により実現されるハッシュ関数の構造図。
【図４０】所定のパディング処理を行う場合の図３７に示すハッシュ値演算装置１０により実現されるハッシュ関数の構造図。
【図４１】所定のパディング処理を行う場合の図３７に示すハッシュ値演算装置１０により実現されるハッシュ関数の構造図。
【図４２】圧縮関数としてＳＨＡ−２５６を用いる場合の図３７に示すハッシュ値演算装置１０により実現されるハッシュ関数の構造図。
【図４３】ハッシュ値演算装置１０のハードウェア構成の一例を示す図。
【発明を実施するための形態】
【０００９】
まず、ハッシュ関数の安全性の概念について説明する。
【００１０】
ハッシュ関数は、任意長の値を入力として、固定長の値を出力する関数である。
ハッシュ関数の満たすべき性質として、以下の３つの性質がある。以下、ハッシュ関数をＨとする。
１．衝突困難性（ｃｏｌｌｉｓｉｏｎ  ｒｅｓｉｓｔａｎｃｅ）：Ｈ（Ｍ）＝Ｈ（Ｍ’）となる２つの値Ｍ，Ｍ’を見つけることが困難であること。
２．第２現像計算困難性（ｓｅｃｏｎｄ  ｐｒｅｉｍａｇｅ  ｒｅｓｉｓｔａｎｃｅ）：ランダムな値Ｍに対して、Ｈ（Ｍ）＝Ｈ（Ｍ’）となる値Ｍとは異なる値Ｍ’を見つけることが困難であること。
３．現像計算困難性（ｐｒｅｉｍａｇｅ  ｒｅｓｉｓｔａｎｃｅ）：ランダムな値ｚに対して、ｚ＝Ｈ（Ｍ）となる値Ｍを見つけることが困難であること。
【００１１】
ハッシュ関数は、入力長、出力長が固定された圧縮関数と呼ばれる関数から構成される。ハッシュ関数の代表的な構成として、ＭＤ（Ｍｅｒｋｌｅ−Ｄａｍｇａｒｄ）構造がある。
ＭＤ構造は、以下のような構成である。
（Ｓｔｅｐ１）入力Ｍにｓｔｒｅｎｇｔｈｅｎ  ＭＤパディングを適用し、長さがｍの倍数となる値Ｍ’を作る。
（Ｓｔｅｐ２）Ｍ’をｍビットの値ｐ［１］，．．．，ｐ［ｉ］に分割する。
（Ｓｔｅｐ３）値ｐ［１］，．．．，ｐ［ｉ］のそれぞれに対し、ｃ［ｊ］＝ｈ（ｃ［ｊ−１］，ｐ［ｊ］）を計算する。ここで、ｃ［０］はｎビットの固定値である。また、ｈは圧縮関数である。圧縮関数ｈは、入力として、ｎビットの値とｍビットの値との２つの値を入力として、ｎビットの値を出力する関数である。
（Ｓｔｅｐ４）Ｃ［ｉ］を出力する。
【００１２】
ハッシュ関数を用いるＯＡＥＰ（Ｏｐｔｉｍａｌ  Ａｓｙｍｍｅｔｒｉｃ  Ｅｎｃｒｙｐｔｉｏｎ  Ｐａｄｄｉｎｇ）やＰＳＳ（Ｐｒｏｂａｂｉｌｉｓｔｉｃ  Ｓｉｇｎａｔｕｒｅ  Ｓｃｈｅｍｅ）等の暗号アルゴリズムは、ハッシュ関数ではなく、理想関数であるランダムオラクルを用いた場合に安全であることが証明されている。
ランダムオラクルとは、予め全ての入力値と、各入力値に対してランダムに選択された出力値とのペアをリスト（メモリ）に記録しておき、入力値に対する出力値は、予め記録したリストを引いて決定する関数である。
【００１３】
ランダムオラクルモデルを用いた場合に安全な暗号アルゴリズムは、ランダムオラクルに代えて安全なハッシュ関数を用いても、安全であると考えられている。ここで、安全なハッシュ関数とは、上述した３つの性質を満たすハッシュ関数である。
【００１４】
しかし、実際には、ランダムオラクルを用いた場合に安全である暗号アルゴリズムが、ランダムオラクルに代えて安全なハッシュ関数を用いた場合にも安全であるとは限らない。つまり、ランダムオラクルを用いた暗号アルゴリズムが安全であっても、安全なハッシュ関数を用いた暗号アルゴリズムが安全であるとは限らない。
実際には、ランダムオラクルを用いた場合に安全である暗号アルゴリズムに対して、ランダムオラクルに代えてハッシュ関数を用いた場合に、その暗号アルゴリズムが安全であるというためには、用いたハッシュ関数がランダムオラクルといわゆる強識別不可能（非特許文献５参照）である必要がある。
つまり、ランダムオラクルを用いた場合に安全であることが証明されている暗号アルゴリズムが、ランダムオラクルと強識別不可能であるハッシュ関数を用いた場合には安全である。すなわち、ランダムオラクルを用いた暗号アルゴリズムが安全であれば、ランダムオラクルと強識別不可能であるハッシュ関数を用いた暗号アルゴリズムは安全である。
【００１５】
ランダムオラクルと強識別不可能であるハッシュ関数とは、例えば、ＥＭＤ（Ｅｍｐｌｏｙｅｄ  Ｍｅｒｋｌｅ−Ｄａｍｇａｒｄ），ＭＤＰ（Ｍｅｒｋｌｅ−Ｄａｍｇａｒｄ  ｗｉｔｈ  Ｐｅｒｍｕｔａｔｉｏｎ）等である。
【００１６】
一般に、ＥＭＤやＭＤＰのように、ランダムオラクルといわゆる強識別不可能であるハッシュ関数は、圧縮関数として理想化された圧縮関数（ＦＩＬＲＯ（Ｆｉｘｅｄ  Ｉｎｐｕｔ  Ｌｅｎｇｔｈ  Ｒａｎｄｏｍ  Ｏｒａｃｌｅ））を用いて構成される。つまり、ＥＭＤやＭＤＰに代表されるハッシュ関数は、圧縮関数として理想化された圧縮関数（ＦＩＬＲＯ）を用いた場合に、ランダムオラクルといわゆる強識別不可能である。
理想化された圧縮関数（ＦＩＬＲＯ）とは、以下の１，２が与えられた圧縮関数である。
１．（リスト）：全ての入力値と、各入力値に対してランダムに選択した出力値とのペアを記録したリストを持つ。
２．（順方向の値を出力するオラクル）：入力値（ｘ，ｙ）に対し、リストから入力に対する出力値ｚを検索して、値ｚを出力する。つまり、ｆ１（ｘ，ｙ）＝ｚとなる値ｚを出力する。
【００１７】
また、背景技術として記載したように、理想化された圧縮関数（ＦＩＬＲＯ）ではなく、一方向性が破られた理想的な圧縮関数（ＷＦＩＬＲＯ）を用いて構成した場合であっても、ランダムオラクルといわゆる強識別不可能であるハッシュ関数がある（非特許文献１，２参照）。
一方向性が破られた理想的な圧縮関数（ＷＦＩＬＲＯ）とは、１−５が与えられた圧縮関数である。
１．（リスト）：全ての入力値と、各入力値に対してランダムに選択した出力値とのペアを記録したリストを持つ。
２．（順方向の値を出力するオラクル）：入力値（ｘ，ｙ）に対し、リストから入力に対する出力値ｚを検索して、値ｚを出力する。つまり、ｆ１（ｘ，ｙ）＝ｚとなる値ｚを出力する。
３．（一方向性を破るオラクル１）：入力値ｚに対して、ｆ１（ｘ，ｙ）＝ｚを満たす全ての値（ｘ，ｙ）のペアからランダムに１つのペア選択して、選択したペアを出力する。
４．（一方向性を破るオラクル２）：入力値ｘ，ｚに対して、ｆ１（ｘ，ｙ）＝ｚを満たす全ての値ｙからランダムに１つの値を選択して、選択した値を出力する。入力値ｘ，ｚに対して、ｆ１（ｘ，ｙ）＝ｚを満たす値ｙが存在しない場合は、識別情報⊥を出力する。
５．（一方向性を破るオラクル３）：入力値ｙ，ｚに対して、ｆ１（ｘ，ｙ）＝ｚを満たす全ての値ｘからランダムに１つの値を選択して、選択した値を出力する。入力値ｙ，ｚに対して、ｆ１（ｘ，ｙ）＝ｚを満たす値ｘが存在しない場合は、識別情報⊥を出力する。
【００１８】
一方向性が破られた理想的な圧縮関数（ＷＦＩＬＲＯ）とは、理想化された圧縮関数（ＦＩＬＲＯ）に加え、さらに上記３−５が与えられた圧縮関数である。理想化された圧縮関数（ＦＩＬＲＯ）に比べ、一方向性が破られた理想的な圧縮関数（ＷＦＩＬＲＯ）の方が、上記３−５が与えられた分、安全性が低い圧縮関数であると言える。
例えば、攻撃者Ａがいた場合、理想化された圧縮関数（ＦＩＬＲＯ）であれば、攻撃者Ａが上記１，２のみを用いることができる状態であり、一方向性が破られた理想的な圧縮関数（ＷＦＩＬＲＯ）であれば、攻撃者Ａが上記１−５を用いることができる状態である。すなわち、理想化された圧縮関数（ＦＩＬＲＯ）に比べ、一方向性が破られた理想的な圧縮関数（ＷＦＩＬＲＯ）の方が、攻撃者Ａに与えられる機能が多い分、攻撃者Ａはより容易に攻撃することができる。そのため、理想化された圧縮関数（ＦＩＬＲＯ）に比べ、一方向性が破られた理想的な圧縮関数（ＷＦＩＬＲＯ）の方が、上記３−５が与えられた分、安全性が低い圧縮関数であると言える。
【００１９】
安全性の低い圧縮関数を用いて構成した場合であっても、ランダムオラクルと強識別不可能であるハッシュ関数は、安全性の高い圧縮関数を用いて構成した場合にのみ、ランダムオラクルと強識別不可能であるハッシュ関数よりも、ハッシュ関数の構成として、安全性の観点から優れていると言える。
つまり、一方向性が破られた理想的な圧縮関数（ＷＦＩＬＲＯ））を用いて構成した場合であっても、ランダムオラクルといわゆる強識別不可能であるハッシュ関数の方が、理想化された圧縮関数（ＦＩＬＲＯ）を用いて構成した場合にのみ、ランダムオラクルといわゆる強識別不可能であるハッシュ関数よりも、ハッシュ関数の構成として、安全性の観点から優れていると言える。
【００２０】
以下の実施の形態において、非特許文献１，２に記載されたジッパーハッシュ関数とダブルパイプハッシュ関数と同様に、一方向性が破られた理想的な圧縮関数（ＷＦＩＬＲＯ））を用いて構成した場合であっても、ランダムオラクルといわゆる強識別不可能である新たなハッシュ関数を構成するハッシュ値演算装置１０について説明する。特に、非特許文献１，２に記載されたジッパーハッシュ関数とダブルパイプハッシュ関数よりも、効率的に計算可能なハッシュ関数を構成するハッシュ値演算装置１０について説明する。
【００２１】
また、以下の実施の形態において、一方向性が破られた理想的な圧縮関数（ＷＦＩＬＲＯ）のうち、５．（一方向性を破るオラクル３）が与えられていない圧縮関数（以下、準一方向性が破られた理想的な圧縮関数と呼ぶ）を用いて構成した場合であっても、ランダムオラクルといわゆる強識別不可能である新たなハッシュ関数を構成するハッシュ値演算装置１０について説明する。
準一方向性が破られた理想的な圧縮関数は、一方向性が破られた理想的な圧縮関数（ＷＦＩＬＲＯ）よりも安全性が高い圧縮関数である。そのため、準一方向性が破られた理想的な圧縮関数を用いて構成した場合に、ランダムオラクルといわゆる強識別不可能であるハッシュ関数よりも、一方向性が破られた理想的な圧縮関数（ＷＦＩＬＲＯ））を用いて構成した場合に、ランダムオラクルといわゆる強識別不可能であるハッシュ関数の方が、ハッシュ関数の構成として、安全性の観点から優れていると言える。しかし、準一方向性が破られた理想的な圧縮関数を用いて構成した場合であっても、ランダムオラクルといわゆる強識別不可能であるハッシュ関数は、理想的な圧縮関数（ＦＩＬＲＯ））を用いて構成した場合にのみ、ランダムオラクルといわゆる強識別不可能であるハッシュ関数よりも、ハッシュ関数の構成として、安全性の観点から優れていると言える。そこで、以下の実施の形態では、準一方向性が破られた理想的な圧縮関数を用いて構成した場合であっても、ランダムオラクルといわゆる強識別不可能である新たなハッシュ関数を構成するハッシュ値演算装置１０についても説明する。
【００２２】
まず、実施の形態１−３で、一方向性が破られた理想的な圧縮関数（ＷＦＩＬＲＯ））を用いて構成した場合であっても、ランダムオラクルといわゆる強識別不可能である３つの新たなハッシュ関数を構成するハッシュ値演算装置１０について説明する。
次に、実施の形態４，５で、準一方向性が破られた理想的な圧縮関数を用いて構成した場合であっても、ランダムオラクルといわゆる強識別不可能である２つの新たなハッシュ関数を構成するハッシュ値演算装置１０について説明する。
【００２３】
なお、以下の実施の形態において、圧縮関数ｈは、ｎビットの値とｍビットの値との２つの値が入力された場合にｎビットの値を出力する圧縮関数である。ここで、ｍは所定の自然数であり、ｎはｍよりも小さい自然数である。
【００２４】
また、以下の説明において、処理装置は後述するＣＰＵ９１１、演算回路等である。記憶装置は後述するＲＯＭ９１３、ＲＡＭ９１４（メモリ，キャッシュメモリ）、磁気ディスク９２０等である。入力装置は後述するキーボード９０２、通信ボード９１５等である。出力装置は後述するＲＡＭ９１４、磁気ディスク９２０、通信ボード９１５、ＬＣＤ９０１等である。つまり、処理装置、記憶装置、入力装置、出力装置はハードウェアである。また、記憶装置とは、上記の通り、ＲＡＭ９１４（メモリ，キャッシュメモリ）等を含むものであるから、以下の説明において記憶装置に記憶するとは、ＲＡＭ９１４（メモリ，キャッシュメモリ）に一時記憶することを意味する場合もある。
【００２５】
実施の形態１．
実施の形態１では、一方向性が破られた理想的な圧縮関数（ＷＦＩＬＲＯ））を用いて構成した場合であっても、ランダムオラクルといわゆる強識別不可能である新たなハッシュ関数を構成するハッシュ値演算装置１０について説明する。
【００２６】
図１は、実施の形態１に係るハッシュ値演算装置１０の機能を示す機能ブロック図である。
図２は、図１に示すハッシュ値演算装置１０の動作を示すフローチャートである。
図３は、図１に示すハッシュ値演算装置１０により実現されるハッシュ関数の構造図である。
【００２７】
図１に示すハッシュ値演算装置１０の機能と動作について説明する。
図１に示すハッシュ値演算装置１０は、既定長値入力部１１、固定値付加部１２、圧縮関数計算部１３、出力部１４を備える。
【００２８】
（Ｓ１０１：既定長値入力ステップ）
既定長値入力部１１は、ｍ−ｎビット長のｉ個の値ｐ［１］，．．．，値ｐ［ｉ］を入力装置により入力して記憶装置に記憶する。
【００２９】
（Ｓ１０２：固定値付加ステップ）
固定値付加部１２は、（Ｓ１０１）で入力されたｍ−ｎビット長のｉ個の値ｐ［１］，．．．，値ｐ［ｉ］のうち、ｉ−１個の値ｐ［１］，．．．，値ｐ［ｉ−１］のそれぞれに対して、予め記憶装置に記憶したｎビット長の固定値ｃｏｎｓｔ［１］，．．．，固定値ｃｏｎｓｔ［ｉ−１］を付加して、ｍビット長の値ｘ［１］，．．．，値ｘ［ｉ−１］を処理装置により生成して記憶装置に記憶する。
つまり、固定値付加部１２は、値ｐ［１］に固定値ｃｏｎｓｔ［１］を付加して、値ｘ［１］を生成する。固定値付加部１２は、値ｐ［２］に固定値ｃｏｎｓｔ［２］を付加して、値ｘ［２］を生成する。以下同様に、ｊ＝３，．．．，ｉ−１に対して、固定値付加部１２は、値ｐ［ｊ］に固定値ｃｏｎｓｔ［ｊ］を付加して、値ｘ［ｊ］を生成する。
なお、ｊ＝１，．．．，ｉ−１について、値ｐ［ｊ］に固定値ｃｏｎｓｔ［ｊ］を付加する位置は、どこであってもよい。つまり、固定値ｃｏｎｓｔ［ｊ］は、値ｐ［ｊ］の前や後に追加してもよいし、値ｐ［ｊ］の間に挿入してもよい。
また、固定値ｃｏｎｓｔ［１］＝固定値ｃｏｎｓｔ［２］＝．．．＝固定値ｃｏｎｓｔ［ｉ−１］でもよいし、固定値ｃｏｎｓｔ［１］≠固定値ｃｏｎｓｔ［２］≠．．．≠固定値ｃｏｎｓｔ［ｉ−１］でもよい。
【００３０】
（Ｓ１０３：第１圧縮関数計算ステップ）
圧縮関数計算部１３は、予め記憶装置に記憶したｎビット長の固定値ＩＶ１と、（Ｓ１０２）で生成されたｍビット長の値ｘ［１］とを圧縮関数ｈの入力として、ｃ［１］＝ｈ（ＩＶ１，ｘ［１］）を処理装置により計算してｎビット長の値ｃ［１］を得て記憶装置に記憶する。
【００３１】
（Ｓ１０４：第２圧縮関数計算ステップ）
圧縮関数計算部１３は、ｊ＝２からｉ−１まで順に、ｎビット長の値ｃ［ｊ−１］とｍビット長の値ｘ［ｊ］とを圧縮関数ｈの入力として、ｃ［ｊ］＝ｈ（ｃ［ｊ−１］，ｘ［ｊ］）を処理装置により計算してｎビット長の値ｃ［ｊ］を得て記憶装置に記憶する。
つまり、まず、圧縮関数計算部１３は、（Ｓ１０３）で計算したｎビット長の値ｃ［１］と、（Ｓ１０２）で生成されたｍビット長の値ｘ［２］とを入力として、ｃ［２］＝ｈ（ｃ［１］，ｘ［２］）を処理装置により計算して値ｃ［２］を得る。
次に、圧縮関数計算部１３は、計算したｎビット長の値ｃ［２］と、（Ｓ１０２）で生成されたｍビット長の値ｘ［３］とを入力として、ｃ［３］＝ｈ（ｃ［２］，ｘ［３］）を処理装置により計算してｎビット長の値ｃ［３］を得る。
これを繰り返して、最終的に、圧縮関数計算部１３は、計算したｎビット長の値ｃ［ｉ−２］と、（Ｓ１０２）で生成されたｍビット長の値ｘ［ｉ−１］とを入力として、ｃ［ｉ−１］＝ｈ（ｃ［ｉ−２］，ｘ［ｉ−１］）を処理装置により計算してｎビット長の値ｃ［ｉ−１］を得る。
【００３２】
（Ｓ１０５：第３圧縮関数計算ステップ）
圧縮関数計算部１３は、予め記憶装置に記憶したｎビット長の固定値ＩＶ２と、ｍ−ｎビット長の値ｐ［ｉ］に（Ｓ１０４）で計算したｎビット長の値ｃ［ｉ−１］を付加したｍビット長の値ｘ［ｉ］とを圧縮関数ｈの入力として、ｃ［ｉ］＝ｈ（ＩＶ２，ｘ［ｉ］）を処理装置により計算して値ｃ［ｉ］を得て記憶装置に記憶する。
なお、値ｐ［ｉ］に値ｃ［ｉ−１］を付加する位置は、どこであってもよい。つまり、値ｃ［ｉ−１］は、値ｐ［ｉ］の前や後に追加してもよいし、値ｐ［ｉ］の間に挿入してもよい。
【００３３】
（Ｓ１０６：出力ステップ）
出力部１４は、（Ｓ１０５）で計算された値ｃ［ｉ］を出力装置により出力する。
【００３４】
なお、ｉ＝２の場合、つまり（Ｓ１０１）で２個の値ｐ［１］と値ｐ［２］とのみが入力された場合には、（Ｓ１０４）は実行されない。つまり、（Ｓ１０３）で値ｃ［１］を得た後、（Ｓ１０５）で固定値ＩＶ２と、値ｐ［２］に値ｃ［１］を付加した値ｘ［２］とを入力として、値ｃ［２］を得る。そして、（Ｓ１０６）で値ｃ［２］を出力する。
【００３５】
また、ｉ＝１の場合、つまり（Ｓ１０１）で１個の値ｐ［１］のみが入力された場合には、（Ｓ１０２）から（Ｓ１０４）までは実行されない。つまり、（Ｓ１０１）で値ｐ［１］が入力された後、（Ｓ１０５）で固定値ＩＶ２と、値ｐ［１］に固定値ＩＶ１を付加した値ｘ［１］とを入力として、値ｃ［１］を得る。そして、（Ｓ１０６）で値ｃ［１］を出力する。
【００３６】
以上をまとめると、次のようになる。
まず、ハッシュ値演算装置１０は、ｊ＝１からｉ−１まで順に、ｃ［ｊ］＝ｈ（ｃ［ｊ−１］，ｐ［ｊ］｜｜ｃｏｎｓｔ［ｊ］）を計算する。ここで、ｃ［０］は、ＩＶ１とする。
次に、ハッシュ値演算装置１０は、ｃ［ｉ］＝ｈ（ＩＶ２，ｐ［ｉ］｜｜ｃ［ｉ−１］）を計算する。
そして、ハッシュ値演算装置１０は、値ｃ［ｉ］を出力する。
【００３７】
上記説明では、（Ｓ１０１）で既定長値入力部１１が、ｍ−ｎビット長のｉ個の値ｐ［１］，．．．，値ｐ［ｉ］を入力するとした。しかし、通常、ハッシュ関数へ入力される値は、１個の任意ビット長の値である。つまり、上記説明では、１個の任意ビット長の値が入力された場合に、どのようにｍ−ｎビット長のｉ個の値ｐ［１］，．．．，値ｐ［ｉ］を生成するのかについては説明を省略した。
次に、任意ビット長の値が入力された場合に、ｍ−ｎビット長のｉ個の値ｐ［１］，．．．，値ｐ［ｉ］を生成する機能を追加したハッシュ値演算装置１０について説明する。
【００３８】
図４は、図１に示すハッシュ値演算装置１０に、任意ビット長の値が入力された場合に、ｍ−ｎビット長のｉ個の値ｐ［１］，．．．，値ｐ［ｉ］を生成する機能を追加したハッシュ値演算装置１０の機能を示す機能ブロック図である。
図５は、図４に示すハッシュ値演算装置１０の動作を示すフローチャートである。
図６は、図４に示すハッシュ値演算装置１０により実現されるハッシュ関数の構造図である。
【００３９】
図４に示すハッシュ値演算装置１０の機能と動作について説明する。
図４に示すハッシュ値演算装置１０は、図１に示すハッシュ値演算装置１０が備える機能に加え、任意長値入力部１５、パディング部１６、分割部１７を備える。
【００４０】
（Ｓ１１１：任意長値入力ステップ）
任意長値入力部１５は、任意ビット長の値Ｍを入力装置により入力する。
【００４１】
（Ｓ１１２：パディングステップ）
パディング部１６は、（Ｓ１１１）で入力された値Ｍに対して、パディング関数ｐａｄを用いて、所定の値を付加してｍ−ｎビット長のｉ倍のビット長の値Ｍ’を処理装置により生成して記憶装置に記憶する。つまり、パディング部１６は、Ｍ’＝ｐａｄ（Ｍ）を処理装置により計算して値Ｍ’を得る。
【００４２】
（Ｓ１１３：分割ステップ）
分割部１７は、（Ｓ１１２）で生成された値Ｍ’を処理装置によりｉ個に分割して、ｍ−ｎビット長の値ｐ［１］，．．．，値ｐ［ｉ］を生成して記憶装置に記憶する。つまり、分割部１７は、Ｍ’＝ｐ［１］｜｜．．．｜｜ｐ［ｉ］を処理装置により計算して値ｐ［１］，．．．，値ｐ［ｉ］を得る。
【００４３】
（Ｓ１１４：既定長値入力ステップ）
既定長値入力部１１は、（Ｓ１１３）で生成された値ｐ［１］，．．．，値ｐ［ｉ］を入力装置により入力する。
【００４４】
（Ｓ１１５）から（Ｓ１１９）までの処理は、（Ｓ１０２）から（Ｓ１０６）までの処理と同一である。
【００４５】
（Ｓ１１２）におけるパディング方法の一例を説明する。
図７は、以下に説明するパディング処理を行う場合の図４に示すハッシュ値演算装置１０により実現されるハッシュ関数の構造図である。
（Ｓ１１２）でパディング部１６は、（Ｓ１１１）で入力された値Ｍに対して、“１｜｜０・・・０｜｜＜Ｍ＞を付加して、ｍ−ｎビット長のｉ倍のビット長の値Ｍ’を処理装置により生成する。ここで、＜Ｍ＞は、Ｍのビット長｜Ｍ｜の６４ビット表現である。
つまり、パディング部１６は、先頭が“１”で、その後が複数の“０”で、最後に＜Ｍ＞となるビット列を生成して、値Ｍに付加して、値Ｍ’を生成する。
なお、上記説明では、ｍ−ｎビット長のｉ倍のビット長になるようにパディングすると説明した。しかし、予めｉの値を決めておくのではなく、ｉの値は、入力された任意ビット長の値Ｍに応じて決定されるとしてもよい。例えば、上記パディング方法であれば、最少の０の個数で、ｍ−ｎビット長の倍数のビット長となるようにパディングし、パディングをした結果得られた値Ｍ’のビット長がｍ−ｎビット長の何倍かをｉの値としてもよい。
【００４６】
パディングの方法は、例えば、全て“０”を付加する方法や、全て“１”を付加する方法等、どのような方法であっても構わない。しかし、上記説明のように、パディングして値Ｍ’を生成することにより、衝突困難性を高くすることができる。
【００４７】
次に、図４に示すハッシュ値演算装置１０の圧縮関数としてＳＨＡ−２５６（Ｓｅｃｕｒｅ  Ｈａｓｈ  Ａｌｇｏｒｉｔｈｍ−２５６）を用いた場合の例を説明する。なお、ＳＨＡ−２５６の圧縮関数をＳＨＡ２５６と呼ぶ。ＳＨＡ２５６は、２５６ビット長の値と５１２ビット長の値との２つの値が入力された場合に、２５６ビット長の値を出力する関数である。
図８は、圧縮関数としてＳＨＡ−２５６を用いる場合の図４に示すハッシュ値演算装置１０により実現されるハッシュ関数の構造図である。
【００４８】
（Ｓ１１１）では、任意長値入力部１５は、任意ビット長の値Ｍを入力する。
（Ｓ１１２）では、パディング部１６は、（Ｓ１１１）で入力された値Ｍに対して、パディング関数ｐａｄを用いて、所定の値を付加して２５６（＝５１２−２５６）ビット長のｉ倍のビット長の値Ｍ’を生成する。
（Ｓ１１３）では、分割部１７は、（Ｓ１１２）で生成された値Ｍ’をｉ個に分割して、２５６ビット長の値ｐ［１］，．．．，値ｐ［ｉ］を生成する。
（Ｓ１１４）では、既定長値入力部１１は、（Ｓ１１３）で生成された２５６ビット長のｉ個の値ｐ［１］，．．．，値ｐ［ｉ］を入力する。
（Ｓ１１５）では、固定値付加部１２は、（Ｓ１１４）で入力された２５６ビット長のｉ個の値ｐ［１］，．．．，値ｐ［ｉ］のうち、ｉ−１個の値ｐ［１］，．．．，値ｐ［ｉ−１］のそれぞれに対して、２５６ビット長の固定値ｃｏｎｓｔ［１］，．．．，固定値ｃｏｎｓｔ［ｉ−１］を付加して、５１２ビット長の値ｘ［１］，．．．，値ｘ［ｉ−１］を生成する。
（Ｓ１１６）では、圧縮関数計算部１３は、２５６ビット長の固定値ＩＶ１と、（Ｓ１１５）で生成された５１２ビット長の値ｘ［１］を圧縮関数ｈの入力として、ｃ［１］＝ｈ（ＩＶ１，ｘ［１］）を計算して２５６ビット長の値ｃ［１］を得る。
（Ｓ１１７）では、圧縮関数計算部１３は、ｊ＝２からｉ−１まで順に、２５６ビット長の値ｃ［ｊ−１］と５１２ビット長の値ｘ［ｊ］とを圧縮関数ｈの入力として、ｃ［ｊ］＝ｈ（ｃ［ｊ−１］，ｘ［ｊ］）を計算して２５６ビット長の値ｃ［ｊ］を得る。
（Ｓ１１８）では、圧縮関数計算部１３は、２５６ビット長の固定値ＩＶ２と、２５６ビット長の値ｐ［ｉ］に２５６ビット長の値ｃ［ｉ−１］を付加した５１２ビット長の値ｘ［ｉ］とを圧縮関数ｈの入力として、ｃ［ｉ］＝ｈ（ＩＶ２，ｘ［ｉ］）を計算して値ｃ［ｉ］を得る。
（Ｓ１１９）では、出力部１４は、（Ｓ１１８）で計算された値ｃ［ｉ］を出力する。
【００４９】
実施の形態１に係るハッシュ値演算装置１０により構成されたハッシュ関数は、圧縮関数ｈが一方向性が破られた理想的な圧縮関数の場合であっても、ランダムオラクルと強識別不可能性を満たすハッシュ関数となる。
【００５０】
なお、必ずしも上述した処理順序通りに計算する必要はなく、ストリーム処理ができる場合には、ストリーム処理で計算してもよい。なお、ストリーム処理とは、入力された先頭のビットから到着順に処理を行う方法であり、並列処理の一類型である。
【００５１】
また、上記説明では、圧縮関数計算部１３は所定の入力値に対して、処理装置により圧縮関数ｈを計算して、圧縮関数ｈを計算した結果を得るとした。しかし、圧縮関数計算部１３は、ハッシュ値演算装置１０の外部に備える圧縮関数計算装置に入力値を入力して、圧縮関数計算装置に圧縮関数ｈを計算させることにより、圧縮関数ｈを計算した結果を得てもよい。
【００５２】
また、圧縮関数計算部１３が値ｃ［１］，．．．，値ｃ［ｉ］を計算するのに用いる圧縮関数ｈは、同一の圧縮関数ｈであってもよいし、それぞれ異なる圧縮関数ｈであってもよい。
【００５３】
つまり、実施の形態１に係るハッシュ値演算装置１０をまとめると次のようになる。
ハッシュ値演算装置１０は、ｉ個のｍ−ｎビットの入力値ｐ［１］，．．．，ｐ［ｉ］に対して、圧縮関数演算装置に、ｎビット固定値ＩＶ１、第１メッセージｐ［１］、ｎビット固定値ｃｏｎｓｔ［１］を入力し、その出力ｃ［１］を得る。次に、圧縮関数演算装置に、ｎビット値ｃ［１］、第２メッセージｐ［２］、ｎビット固定値ｃｏｎｓｔ［２］を入力し、その出力ｃ［２］を得る。この処理を、第ｉ−１メッセージまで同様に行い、その出力値ｃ［ｉ−１］を得る。圧縮関数演算装置に、初期値ＩＶ２、ｉ番目のメッセージｐ［ｉ］、ｎビット値ｃ［ｉ−１］を入力し、その出力ｃ［ｉ］を得る。そして、ｃ［ｉ］を出力することを特徴とする。
【００５４】
また、ハッシュ値演算装置１０は、任意長の値Ｍから、任意長の値を入力とし、長さがｍ−ｎの倍数の値を出力する任意のパディング処理装置を用いて、ｍ−ｎビットの倍数となるメッセージＭ’を生成する。そして、分割処理装置を用いてＭ’をｉ個のｍ−ｎビットの値ｐ［１］，．．．，ｐ［ｉ］に分割することを特徴とする。
【００５５】
さらに、ハッシュ値演算装置１０は、パディング処理装置を、Ｍ｜｜１｜｜０．．．０｜｜＜Ｍ＞とすることを特徴とする。但し、＜Ｍ＞はＭのビット長を６４ビットで表したものである。
【００５６】
また、さらに、ハッシュ値演算装置１０は、圧縮関数演算装置として、ＳＨＡ−２５６の圧縮関数演算装置を用いたことを特徴とする。
【００５７】
実施の形態２．
実施の形態２では、実施の形態１とは異なるハッシュ関数であって、一方向性が破られた理想的な圧縮関数（ＷＦＩＬＲＯ））を用いて構成した場合であっても、ランダムオラクルといわゆる強識別不可能である新たなハッシュ関数を構成するハッシュ値演算装置１０について説明する。
【００５８】
図９は、実施の形態２に係るハッシュ値演算装置１０の機能を示す機能ブロック図である。
図１０は、図９に示すハッシュ値演算装置１０の動作を示すフローチャートである。
図１１は、図９に示すハッシュ値演算装置１０により実現されるハッシュ関数の構造図である。
【００５９】
図９に示すハッシュ値演算装置１０の機能と動作について説明する。
図９に示すハッシュ値演算装置１０は、既定長値入力部１１、固定値付加部１２、圧縮関数計算部１３、出力部１４、排他的論理和計算部１８を備える。
【００６０】
（Ｓ２０１：既定長値入力ステップ）
既定長値入力部１１は、ｍ−ｓビット長のｉ個の値ｐ［１］，．．．，値ｐ［ｉ］を入力装置により入力して記憶装置に記憶する。
【００６１】
（Ｓ２０２：排他的論理和計算ステップ）
排他的論理和計算部１８は、（Ｓ２０１）で入力されたｍ−ｓビット長の値ｐ［１］，．．．，ｐ［ｉ］と、予め記憶装置に記憶したｍ−ｓビット長の固定値ｙとを排他的論理和演算の入力として、ｓｕｍ＝ｐ［１］  ｘｏｒ，．．．，ｘｏｒ  ｐ［ｉ］  ｘｏｒ  ｙを処理装置により計算してｍ−ｓビット長の値ｓｕｍを得て記憶装置に記憶する。
【００６２】
（Ｓ２０３：固定値付加ステップ）
固定値付加部１２は、（Ｓ２０１）で入力されたｍ−ｓビット長のｉ個の値ｐ［１］，．．．，値ｐ［ｉ］のそれぞれに対して、予め記憶装置に記憶したｓビット長の固定値ｃｏｎｓｔ［１］，．．．，固定値ｃｏｎｓｔ［ｉ］を付加して、ｍビット長の値ｘ［１］，．．．，値ｘ［ｉ］を処理装置により生成して記憶装置に記憶する。
つまり、固定値付加部１２は、値ｐ［１］に固定値ｃｏｎｓｔ［１］を付加して、値ｘ［１］を生成する。固定値付加部１２は、値ｐ［２］に固定値ｃｏｎｓｔ［２］を付加して、値ｘ［２］を生成する。以下同様に、ｊ＝３，．．．，ｉに対して、固定値付加部１２は、値ｐ［ｊ］に固定値ｃｏｎｓｔ［ｊ］を付加して、値ｘ［ｊ］を生成する。
なお、ｊ＝１，．．．，ｉ−１について、値ｐ［ｊ］に固定値ｃｏｎｓｔ［ｊ］を付加する位置は、どこであってもよい。つまり、固定値ｃｏｎｓｔ［ｊ］は、値ｐ［ｊ］の前や後に追加してもよいし、値ｐ［ｊ］の間に挿入してもよい。
また、固定値ｃｏｎｓｔ［１］≠固定値ｃｏｎｓｔ［２］≠．．．≠固定値ｃｏｎｓｔ［ｉ］である。例えば、ｊ＝１，．．．，ｉについて、固定値ｃｏｎｓｔ［ｊ］は、ｊをｓビットで表現した値＜ｊ＞である。
【００６３】
（Ｓ２０４：第１圧縮関数計算ステップ）
圧縮関数計算部１３は、予め記憶装置に記憶したｎビット長の固定値ＩＶ１と、（Ｓ２０３）で生成されたｍビット長の値ｘ［１］を圧縮関数ｈの入力として、ｃ［１］＝ｈ（ＩＶ１，ｘ［１］）を処理装置により計算してｎビット長の値ｃ［１］を得て記憶装置に記憶する。
【００６４】
（Ｓ２０５：第２圧縮関数計算ステップ）
圧縮関数計算部１３は、ｊ＝２からｉまで順に、ｎビット長の値ｃ［ｊ−１］とｍビット長の値ｘ［ｊ］とを圧縮関数ｈの入力として、ｃ［ｊ］＝ｈ（ｃ［ｊ−１］，ｘ［ｊ］）を処理装置により計算してｎビット長の値ｃ［ｊ］を得て記憶装置に記憶する。
つまり、まず、圧縮関数計算部１３は、（Ｓ２０４）で計算したｎビット長の値ｃ［１］と、（Ｓ２０３）で生成されたｍビット長の値ｘ［２］とを入力として、ｃ［２］＝ｈ（ｃ［１］，ｘ［２］）を処理装置により計算してｎビット長の値ｃ［２］を得る。
次に、圧縮関数計算部１３は、計算したｎビット長の値ｃ［２］と、（Ｓ２０３）で生成されたｍビット長の値ｘ［３］とを入力として、ｃ［３］＝ｈ（ｃ［２］，ｘ［３］）を処理装置により計算してｎビット長の値ｃ［３］を得る。
これを繰り返して、最終的に、圧縮関数計算部１３は、計算したｎビット長の値ｃ［ｉ−１］と、（Ｓ２０３）で生成されたｍビット長の値ｘ［ｉ］とを入力として、ｃ［ｉ］＝ｈ（ｃ［ｉ−１］，ｘ［ｉ］）を処理装置により計算してｎビット長の値ｃ［ｉ］を得る。
【００６５】
（Ｓ２０６：第３圧縮関数計算ステップ）
圧縮関数計算部１３は、（Ｓ２０５）で計算したｎビット長の値ｃ［ｉ］と、（Ｓ２０２）で計算されたｍ−ｓビット長の値ｓｕｍにｓビット長の固定値ｃｏｎｓｔ［ｉ＋１］を付加したｍビット長の値ｘ［ｉ＋１］とを圧縮関数ｈの入力として、ｃ［ｉ＋１］＝ｈ（ｃ［ｉ］，ｘ［ｉ＋１］）を処理装置により計算してｎビット長の値ｃ［ｉ＋１］を得て記憶装置に記憶する。
なお、固定値ｃｏｎｓｔ［ｉ＋１］≠固定値ｃｏｎｓｔ［１］≠．．．≠固定値ｃｏｎｓｔ［ｉ］である。例えば、固定値ｃｏｎｓｔ［ｉ＋１］は、ｉ＋１をｓビットで表現した値＜ｉ＋１＞である。
また、値ｓｕｍに固定値ｃｏｎｓｔ［ｉ＋１］を付加する位置は、どこであってもよい。つまり、固定値ｃｏｎｓｔ［ｉ＋１］は、値ｓｕｍの前や後に追加してもよいし、値ｓｕｍの間に挿入してもよい。
【００６６】
（Ｓ２０７：第４圧縮関数計算ステップ）
圧縮関数計算部１３は、予め記憶装置に記憶したｎビット長の固定値ＩＶ２と、（Ｓ２０６）で計算したｎビット長の値ｃ［ｉ＋１］にｍ−ｎビット長の固定値ｃｏｎｓｔ［ｉ＋２］を付加した値ｘ［ｉ＋２］とを圧縮関数ｈの入力として、ｃ［ｉ＋２］＝ｈ（ＩＶ２，ｘ［ｉ＋２］）を処理装置により計算してｎビット長の値ｃ［ｉ＋２］を得て記憶装置に記憶する。
なお、値ｃ［ｉ＋１］に固定値ｃｏｎｓｔ［ｉ＋２］を付加する位置は、どこであってもよい。つまり、固定値ｃｏｎｓｔ［ｉ＋２］は、値ｃ［ｉ＋１］の前や後に追加してもよいし、値ｃ［ｉ＋１］の間に挿入してもよい。
また、例えば、固定値ｃｏｎｓｔ［ｉ＋２］は、ｍ−ｎ−ｓビット長の固定値ｃｏｎｓｔと、ｉ＋２をｓビットで表現した値＜ｉ＋２＞との２つの値であってもよい。固定値ｃｏｎｓｔ［ｉ＋２］が固定値ｃｏｎｓｔと＜ｉ＋２＞とである場合には、どのように値ｃ［ｉ＋１］に固定値ｃｏｎｓｔと＜ｉ＋２＞とを付加してもよい。例えば、ｘ［ｉ＋２］＝＜ｉ＋２＞｜｜ｃｏｎｓｔ｜｜ｃ［ｉ＋１］としてもよい。
【００６７】
（Ｓ２０８：出力ステップ）
出力部１４は、（Ｓ２０７）で計算された値ｃ［ｉ＋２］を出力装置により出力する。
【００６８】
なお、ｉ＝１の場合、つまり（Ｓ２０１）で１個の値ｐ［１］のみが入力された場合には、（Ｓ２０５）は実行されない。つまり、（Ｓ２０４）で値ｃ［１］を得た後、（Ｓ２０６）で値ｃ［１］と、値ｓｕｍに固定値ｃｏｎｓｔ［２］を付加した値ｘ［２］とを入力として、値ｃ［２］を得る。そして、（Ｓ２０７）へ進む。
【００６９】
以上をまとめると、次のようになる。
まず、ハッシュ値演算装置１０は、ｓｕｍ＝ｐ［１］  ｘｏｒ，．．．，ｘｏｒ  ｐ［ｉ］  ｘｏｒ  ｙを処理装置により計算する。
また、ハッシュ値演算装置１０は、ｊ＝１からｉまで順に、ｃ［ｊ］＝ｈ（ｃ［ｊ−１］，ｐ［ｊ］｜｜＜ｊ＞）を計算する。ここで、ｃ［０］は、ＩＶ１とする。
次に、ハッシュ値演算装置１０は、ｃ［ｉ＋１］＝ｈ（ｃ［ｉ］，ｓｕｍ｜｜＜ｉ＋１＞）を計算する。
次に、ハッシュ値演算装置１０は、ｃ［ｉ＋２］＝ｈ（ＩＶ，ｃ［ｉ＋１］｜｜ｃｏｎｓｔ｜｜＜ｉ＋２＞）を計算する。
そして、ハッシュ値演算装置１０は、値ｃ［ｉ＋２］を出力する。
【００７０】
上記説明では、（Ｓ２０１）で既定長値入力部１１が、ｍ−ｓビット長のｉ個の値ｐ［１］，．．．，値ｐ［ｉ］を入力するとした。しかし、通常、ハッシュ関数へ入力される値は、１個の任意ビット長の値である。つまり、上記説明では、１個の任意ビット長の値が入力された場合に、どのようにｍ−ｓビット長のｉ個の値ｐ［１］，．．．，値ｐ［ｉ］を生成するのかについては説明を省略した。
次に、任意ビット長の値が入力された場合に、ｍ−ｓビット長のｉ個の値ｐ［１］，．．．，値ｐ［ｉ］を生成する機能を追加したハッシュ値演算装置１０について説明する。
【００７１】
図１２は、図９に示すハッシュ値演算装置１０に、任意ビット長の値が入力された場合に、ｍ−ｓビット長のｉ個の値ｐ［１］，．．．，値ｐ［ｉ］を生成する機能を追加したハッシュ値演算装置１０の機能を示す機能ブロック図である。
図１３は、図１２に示すハッシュ値演算装置１０の動作を示すフローチャートである。
図１４は、図１２に示すハッシュ値演算装置１０により実現されるハッシュ関数の構造図である。
【００７２】
図１２に示すハッシュ値演算装置１０の機能と動作について説明する。
図１２に示すハッシュ値演算装置１０は、図９に示すハッシュ値演算装置１０が備える機能に加え、任意長値入力部１５、パディング部１６、分割部１７を備える。
【００７３】
（Ｓ２１１：任意長値入力ステップ）
任意長値入力部１５は、任意ビット長の値Ｍを入力装置により入力する。
【００７４】
（Ｓ２１２：パディングステップ）
パディング部１６は、（Ｓ２１１）で入力された値Ｍに対して、パディング関数ｐａｄを用いて、所定の値を付加してｍ−ｓビット長のｉ倍のビット長の値Ｍ’を処理装置により生成して記憶装置に記憶する。つまり、パディング部１６は、Ｍ’＝ｐａｄ（Ｍ）を処理装置により計算して値Ｍ’を得る。
【００７５】
（Ｓ２１３：分割ステップ）
分割部１７は、（Ｓ２１２）で生成された値Ｍ’を処理装置によりｉ個に分割して、ｍ−ｓビット長の値ｐ［１］，．．．，値ｐ［ｉ］を生成して記憶装置に記憶する。つまり、分割部１７は、Ｍ’＝ｐ［１］｜｜．．．｜｜ｐ［ｉ］を処理装置により計算して値ｐ［１］，．．．，値ｐ［ｉ］を得る。
【００７６】
（Ｓ２１４：既定長値入力ステップ）
既定長値入力部１１は、（Ｓ２１３）で生成された値ｐ［１］，．．．，値ｐ［ｉ］を入力装置により入力する。
【００７７】
（Ｓ２１５）から（Ｓ２２１）までの処理は、（Ｓ２０２）から（Ｓ２０８）までの処理と同一である。
【００７８】
（Ｓ２１２）におけるパディング方法の一例を説明する。
図１５は、以下に説明するパディング処理を行う場合の図１２に示すハッシュ値演算装置１０により実現されるハッシュ関数の構造図である。
（Ｓ２１２）でパディング部１６は、実施の形態１で説明した（Ｓ１１２）におけるパディング方法と同様に、（Ｓ２１１）で入力された値Ｍに対して、“１｜｜０・・・０｜｜＜Ｍ＞を付加して、ｍ−ｓビット長のｉ倍のビット長の値Ｍ’を処理装置により生成する。ここで、＜Ｍ＞は、Ｍのビット長｜Ｍ｜の６４ビット表現である。
このように、パディングして値Ｍ’を生成することにより、衝突困難性を高くすることができる。
【００７９】
図１６は、以下に説明するパディング処理を行う場合の図１２に示すハッシュ値演算装置１０により実現されるハッシュ関数の構造図である。
（Ｓ２１２）でパディング部１６は、（Ｓ２１１）で入力された値Ｍに対して、“１｜｜０・・・０を付加して、ｍ−ｓビット長のｉ倍のビット長の値Ｍ’を処理装置により生成する。
このように、パディングして値Ｍ’を生成しても、衝突困難性を高くすることができる。
【００８０】
なお、実施の形態１と同様に、予めｉの値を決めておくのではなく、ｉの値は、入力された任意ビット長の値Ｍに応じて決定されるとしてもよい。
【００８１】
次に、図１２に示すハッシュ値演算装置１０の圧縮関数としてＳＨＡ−２５６を用いた場合の例を説明する。なお、ＳＨＡ−２５６の圧縮関数をＳＨＡ２５６と呼ぶ。ＳＨＡ２５６は、２５６ビット長の値と５１２ビット長の値との２つの値が入力された場合に、２５６ビット長の値を出力する関数である。
図１７は、圧縮関数としてＳＨＡ−２５６を用いる場合の図１２に示すハッシュ値演算装置１０により実現されるハッシュ関数の構造図である。
なお、以下の説明では、値ｓを５６として説明する。
【００８２】
（Ｓ２１１）では、任意長値入力部１５は、任意ビット長の値Ｍを入力する。
（Ｓ２１２）では、パディング部１６は、（Ｓ２１１）で入力された値Ｍに対して、パディング関数ｐａｄを用いて、所定の値を付加して４５６（＝５１２−５６）ビット長のｉ倍のビット長の値Ｍ’を生成する。
（Ｓ２１３）では、分割部１７は、（Ｓ２１２）で生成された値Ｍ’をｉ個に分割して、４５６ビット長の値ｐ［１］，．．．，値ｐ［ｉ］を生成する。
（Ｓ２１４）では、既定長値入力部１１は、（Ｓ２１３）で生成された４５６ビット長の値ｐ［１］，．．．，値ｐ［ｉ］を入力する。
（Ｓ２１５）では、排他的論理和計算部１８は、（Ｓ２１４）で入力された４５６ビット長の値ｐ［１］，．．．，ｐ［ｉ］と、４５６ビット長の固定値ｙとを排他的論理和演算の入力として、ｓｕｍ＝ｐ［１］  ｘｏｒ，．．．，ｘｏｒ  ｐ［ｉ］  ｘｏｒ  ｙを計算して４５６ビット長の値ｓｕｍを得る。
（Ｓ２１６）では、固定値付加部１２は、（Ｓ２１１）で入力された４５６ビット長の値ｐ［１］，．．．，値ｐ［ｉ］のそれぞれに対して、５６ビット長の固定値ｃｏｎｓｔ［１］，．．．，固定値ｃｏｎｓｔ［ｉ］を付加して、５１２ビット長の値ｘ［１］，．．．，値ｘ［ｉ］を生成する。
（Ｓ２１７）では、圧縮関数計算部１３は、２５６ビット長の固定値ＩＶ１と、（Ｓ２１６）で生成された５１２ビット長の値ｘ［１］を圧縮関数ｈの入力として、ｃ［１］＝ｈ（ＩＶ１，ｘ［１］）を計算して２５６ビット長の値ｃ［１］を得る。
（Ｓ２１８）では、圧縮関数計算部１３は、ｊ＝２からｉまで順に、２５６ビット長の値ｃ［ｊ−１］と５１２ビット長の値ｘ［ｊ］とを圧縮関数ｈの入力として、ｃ［ｊ］＝ｈ（ｃ［ｊ−１］，ｘ［ｊ］）を計算して２５６ビット長の値ｃ［ｊ］を得る。
（Ｓ２１９）では、圧縮関数計算部１３は、（Ｓ２１８）で計算した２５６ビット長の値ｃ［ｉ］と、（Ｓ２１５）で計算された４５６ビット長の値ｓｕｍに５６ビット長の固定値ｃｏｎｓｔ［ｉ＋１］を付加した５１２ビット長の値ｘ［ｉ＋１］とを圧縮関数ｈの入力として、ｃ［ｉ＋１］＝ｈ（ｃ［ｉ］，ｘ［ｉ＋１］）を計算して２５６ビット長の値ｃ［ｉ＋１］を得る。
（Ｓ２２０）では、圧縮関数計算部１３は、２５６ビット長の固定値ＩＶ２と、（Ｓ２１５）で計算した２５６ビット長の値ｃ［ｉ＋１］に２５６ビット長の固定値ｃｏｎｓｔ［ｉ＋２］を付加した値ｘ［ｉ＋２］とを圧縮関数ｈの入力として、ｃ［ｉ＋２］＝ｈ（ＩＶ２，ｘ［ｉ＋２］）を計算して２５６ビット長の値ｃ［ｉ＋２］を得る。
（Ｓ２２１）では、出力部１４は、（Ｓ２２０）で計算された値ｃ［ｉ＋２］を出力する。
【００８３】
実施の形態２に係るハッシュ値演算装置１０により構成されたハッシュ関数は、圧縮関数ｈが一方向性が破られた理想的な圧縮関数の場合であっても、ランダムオラクルと強識別不可能性を満たすハッシュ関数となる。
【００８４】
なお、実施の形態１と同様に、必ずしも上述した処理順序通りに計算する必要はなく、ストリーム処理ができる場合には、ストリーム処理で計算してもよい。
【００８５】
また、実施の形態１と同様に、圧縮関数計算部１３は、ハッシュ値演算装置１０の外部に備える圧縮関数計算装置に入力値を入力して、圧縮関数計算装置に圧縮関数ｈを計算させることにより、圧縮関数ｈを計算した結果を得てもよい。
また、同様に、排他的論理和計算部１８は、ハッシュ値演算装置１０の外部に備える排他的論理和計算装置に入力値を入力して、排他的論理和計算装置に排他的論理和演算を計算させることにより、排他的論理和演算を計算した結果を得てもよい。
【００８６】
また、圧縮関数計算部１３が値ｃ［１］，．．．，値ｃ［ｉ＋２］を計算するのに用いる圧縮関数ｈは、同一の圧縮関数ｈであってもよいし、それぞれ異なる圧縮関数ｈであってもよい。
【００８７】
つまり、実施の形態２に係るハッシュ値演算装置１０をまとめると次のようになる。
ハッシュ値演算装置１０は、ｉ個のｍ−ｓビットの入力値ｐ［１］，．．．，ｐ［ｉ］に対して、圧縮関数演算装置に、ｎビット固定値ＩＶ１、第１メッセージｐ［１］、１のｓビット表現値を入力し、その出力ｃ［１］を得る。次に、圧縮関数演算装置に、ｎビット値ｃ［１］、第２メッセージｐ［２］、２のｓビット表現値を入力し、その出力ｃ［２］を得る。この処理を、第ｉメッセージまで同様に行い、その出力値ｃ［ｉ］を得る。圧縮関数演算装置に、ｎビット値ｃ［ｉ］、ｓｕｍ＝ｐ［１］  ｘｏｒ  ．．．  ｘｏｒ  ｐ［ｉ］  ｘｏｒ  ｙ、ｉ＋１のｓビットの表現値を入力し、その出力ｃ［ｉ＋１］を得る。圧縮関数演算装置に、初期値ＩＶ２、ｎビット値ｃ［ｉ−１］、ｍ−ｎ−ｓビット固定値ｃｏｎｓｔ、ｉ＋２のｓビット表現値を入力し、その出力ｃ［ｉ＋２］を得る。そして、ｃ［ｉ＋２］を出力することを特徴とする。ここで、ｙはｍ−ｓビット固定値である。
【００８８】
また、ハッシュ値演算装置１０は、任意長の値Ｍから、任意長の値を入力とし、ｍ−ｓビットの値を出力する任意のパディング処理装置を用いて、ｍ−ｓビットの倍数となるメッセージＭ’を生成する。分割処理装置を用いてＭ’をｉ個のｍ−ｓビットの値ｐ［１］，．．．，ｐ［ｉ］に分割することを特徴とする。
【００８９】
さらに、ハッシュ値演算装置１０は、パディング処理装置を、Ｍ｜｜１｜｜０．．．０｜｜＜Ｍ＞とし、ｓ＝５６とすることを特徴とする。但し、＜Ｍ＞はＭのビット長を６４ビットで表したものである。
【００９０】
また、さらに、ハッシュ値演算装置１０は、パディング処理装置を、Ｍ｜｜１｜｜０．．．０とし、ｓ＝５６とすることを特徴とする。
【００９１】
また、ハッシュ値演算装置１０は、圧縮関数演算装置として、ＳＨＡ−２５６の圧縮関数演算装置を用いたことを特徴とする。
【００９２】
実施の形態３．
実施の形態３では、実施の形態１，２とは異なるハッシュ関数であって、一方向性が破られた理想的な圧縮関数（ＷＦＩＬＲＯ））を用いて構成した場合であっても、ランダムオラクルといわゆる強識別不可能である新たなハッシュ関数を構成するハッシュ値演算装置１０について説明する。
【００９３】
図１８は、実施の形態３に係るハッシュ値演算装置１０の機能を示す機能ブロック図である。
図１９は、図１８に示すハッシュ値演算装置１０の動作を示すフローチャートである。
図２０は、図１８に示すハッシュ値演算装置１０により実現されるハッシュ関数の構造図である。
【００９４】
図１８に示すハッシュ値演算装置１０の機能と動作について説明する。
図１８に示すハッシュ値演算装置１０は、既定長値入力部１１、固定値付加部１２、圧縮関数計算部１３、出力部１４、排他的論理和計算部１８を備える。
【００９５】
（Ｓ３０１：既定長値入力ステップ）
既定長値入力部１１は、ｍ−ｓビット長のｉ個の値ｐ［１］，．．．，値ｐ［ｉ］と、ｍ−ｎビット長の１個の値ｐ［ｉ＋１］との合計ｉ＋１個の値を入力装置により入力して記憶装置に記憶する。
【００９６】
（Ｓ３０２：排他的論理和計算ステップ）
排他的論理和計算部１８は、（Ｓ３０１）で入力されたｍ−ｓビット長のｉ個の値ｐ［１］，．．．，ｐ［ｉ］と、予め記憶装置に記憶したｍ−ｓビット長の固定値ｙとを排他的論理和演算の入力として、ｓｕｍ＝ｐ［１］  ｘｏｒ，．．．，ｘｏｒ  ｐ［ｉ］  ｘｏｒ  ｙを処理装置により計算してｍ−ｓビット長の値ｓｕｍを得て記憶装置に記憶する。
【００９７】
（Ｓ３０３：固定値付加ステップ）
固定値付加部１２は、（Ｓ３０１）で入力されたｍ−ｓビット長のｉ個の値ｐ［１］，．．．，値ｐ［ｉ］のそれぞれに対して、予め記憶装置に記憶したｓビット長の固定値ｃｏｎｓｔ［１］，．．．，固定値ｃｏｎｓｔ［ｉ］を付加して、ｍビット長の値ｘ［１］，．．．，値ｘ［ｉ］を処理装置により生成して記憶装置に記憶する。
つまり、固定値付加部１２は、値ｐ［１］に固定値ｃｏｎｓｔ［１］を付加して、値ｘ［１］を生成する。固定値付加部１２は、値ｐ［２］に固定値ｃｏｎｓｔ［２］を付加して、値ｘ［２］を生成する。以下同様に、ｊ＝３，．．．，ｉに対して、固定値付加部１２は、値ｐ［ｊ］に固定値ｃｏｎｓｔ［ｊ］を付加して、値ｘ［ｊ］を生成する。
なお、ｊ＝１，．．．，ｉ−１について、値ｐ［ｊ］に固定値ｃｏｎｓｔ［ｊ］を付加する位置は、どこであってもよい。つまり、固定値ｃｏｎｓｔ［ｊ］は、値ｐ［ｊ］の前や後に追加してもよいし、値ｐ［ｊ］の間に挿入してもよい。
また、固定値ｃｏｎｓｔ［１］≠固定値ｃｏｎｓｔ［２］≠．．．≠固定値ｃｏｎｓｔ［ｉ］である。例えば、ｊ＝１，．．．，ｉについて、固定値ｃｏｎｓｔ［ｊ］は、ｊをｓビットで表現した値＜ｊ＞である。
【００９８】
（Ｓ３０４：第１圧縮関数計算ステップ）
圧縮関数計算部１３は、予め記憶装置に記憶したｎビット長の固定値ＩＶ１と、（Ｓ３０３）で生成されたｍビット長の値ｘ［１］を圧縮関数ｈの入力として、ｃ［１］＝ｈ（ＩＶ１，ｘ［１］）を処理装置により計算してｎビット長の値ｃ［１］を得て記憶装置に記憶する。
【００９９】
（Ｓ３０５：第２圧縮関数計算ステップ）
圧縮関数計算部１３は、ｊ＝２からｉまで順に、ｎビット長の値ｃ［ｊ−１］とｍビット長の値ｘ［ｊ］とを圧縮関数ｈの入力として、ｃ［ｊ］＝ｈ（ｃ［ｊ−１］，ｘ［ｊ］）を処理装置により計算してｎビット長の値ｃ［ｊ］を得て記憶装置に記憶する。
つまり、まず、圧縮関数計算部１３は、（Ｓ３０４）で計算したｎビット長の値ｃ［１］と、（Ｓ３０３）で生成されたｍビット長の値ｘ［２］とを入力として、ｃ［２］＝ｈ（ｃ［１］，ｘ［２］）を処理装置により計算してｎビット長の値ｃ［２］を得る。
次に、圧縮関数計算部１３は、計算したｎビット長の値ｃ［２］と、（Ｓ３０３）で生成されたｍビット長の値ｘ［３］とを入力として、ｃ［３］＝ｈ（ｃ［２］，ｘ［３］）を処理装置により計算してｎビット長の値ｃ［３］を得る。
これを繰り返して、最終的に、圧縮関数計算部１３は、計算したｎビット長の値ｃ［ｉ−１］と、（Ｓ３０３）で生成されたｍビット長の値ｘ［ｉ］とを入力として、ｃ［ｉ］＝ｈ（ｃ［ｉ−１］，ｘ［ｉ］）を処理装置により計算してｎビット長の値ｃ［ｉ］を得る。
【０１００】
（Ｓ３０６：第３圧縮関数計算ステップ）
圧縮関数計算部１３は、（Ｓ３０５）で計算したｎビット長の値ｃ［ｉ］と、（Ｓ３０２）で計算されたｍ−ｓビット長の値ｓｕｍにｓビット長の固定値ｃｏｎｓｔ［ｉ＋１］を付加したｍビット長の値ｘ［ｉ＋１］とを圧縮関数ｈの入力として、ｃ［ｉ＋１］＝ｈ（ｃ［ｉ］，ｘ［ｉ＋１］）を処理装置により計算してｎビット長の値ｃ［ｉ＋１］を得て記憶装置に記憶する。
なお、固定値ｃｏｎｓｔ［ｉ＋１］≠固定値ｃｏｎｓｔ［１］≠．．．≠固定値ｃｏｎｓｔ［ｉ］である。例えば、固定値ｃｏｎｓｔ［ｉ＋１］は、ｉ＋１をｓビットで表現した値＜ｉ＋１＞である。
また、値ｓｕｍに固定値ｃｏｎｓｔ［ｉ＋１］を付加する位置は、どこであってもよい。つまり、固定値ｃｏｎｓｔ［ｉ＋１］は、値ｓｕｍの前や後に追加してもよいし、値ｓｕｍの間に挿入してもよい。
【０１０１】
（Ｓ３０７：第４圧縮関数計算ステップ）
圧縮関数計算部１３は、予め記憶装置に記憶したｎビット長の固定値ＩＶ２と、（Ｓ３０６）で計算したｎビット長の値ｃ［ｉ＋１］に（Ｓ３０１）で入力されたｍ−ｎビット長の値ｐ［ｉ＋１］を付加した値ｘ［ｉ＋２］とを圧縮関数ｈの入力として、ｃ［ｉ＋２］＝ｈ（ＩＶ２，ｘ［ｉ＋２］）を処理装置により計算してｎビット長の値ｃ［ｉ＋２］を得て記憶装置に記憶する。
なお、値ｃ［ｉ＋１］に値ｐ［ｉ＋１］を付加する位置は、どこであってもよい。つまり、値ｐ［ｉ＋１］は、値ｃ［ｉ＋１］の前や後に追加してもよいし、値ｃ［ｉ＋１］の間に挿入してもよい。
【０１０２】
（Ｓ３０８：出力ステップ）
出力部１４は、（Ｓ３０７）で計算された値ｃ［ｉ＋２］を出力装置により出力する。
【０１０３】
なお、ｉ＝１の場合、つまり（Ｓ３０１）で２個の値ｐ［１］（値ｐ［ｉ］）と値ｐ［２］（値ｐ［ｉ＋１］）とのみが入力された場合には、（Ｓ３０５）は実行されない。つまり、（Ｓ３０４）で値ｃ［１］を得た後、（Ｓ３０６）で値ｃ［１］と、値ｓｕｍに固定値ｃｏｎｓｔ［２］を付加した値ｘ［２］とを入力として、値ｃ［２］を得る。そして、（Ｓ３０７）へ進む。
【０１０４】
以上をまとめると、次のようになる。
まず、ハッシュ値演算装置１０は、ｓｕｍ＝ｐ［１］  ｘｏｒ，．．．，ｘｏｒ  ｐ［ｉ］  ｘｏｒ  ｙを処理装置により計算する。
また、ハッシュ値演算装置１０は、ｊ＝１からｉまで順に、ｃ［ｊ］＝ｈ（ｃ［ｊ−１］，ｐ［ｊ］｜｜＜ｊ＞）を計算する。ここで、ｃ［０］は、ＩＶ１とする。
次に、ハッシュ値演算装置１０は、ｃ［ｉ＋１］＝ｈ（ｃ［ｉ］，ｓｕｍ｜｜＜ｉ＋１＞）を計算する。
次に、ハッシュ値演算装置１０は、ｃ［ｉ＋２］＝ｈ（ＩＶ，ｃ［ｉ＋１］｜｜ｐ［ｉ＋１］）を計算する。
そして、ハッシュ値演算装置１０は、値ｃ［ｉ＋２］を出力する。
【０１０５】
上記説明では、（Ｓ３０１）で既定長値入力部１１が、ｍ−ｓビット長のｉ個の値ｐ［１］，．．．，値ｐ［ｉ］と、ｍ−ｎビット長の１個の値ｐ［ｉ＋１］とを入力するとした。しかし、通常、ハッシュ関数へ入力される値は、１個の任意ビット長の値である。つまり、上記説明では、１個の任意ビット長の値が入力された場合に、どのようにｍ−ｓビット長のｉ個の値ｐ［１］，．．．，値ｐ［ｉ］と、ｍ−ｎビット長の１個の値ｐ［ｉ＋１］とを生成するのかについては説明を省略した。
次に、任意ビット長の値が入力された場合に、ｍ−ｓビット長のｉ個の値ｐ［１］，．．．，値ｐ［ｉ］と、ｍ−ｎビット長の１個の値ｐ［ｉ＋１］とを生成する機能を追加したハッシュ値演算装置１０について説明する。
【０１０６】
図２１は、図１８に示すハッシュ値演算装置１０に、任意ビット長の値が入力された場合に、ｍ−ｓビット長のｉ個の値ｐ［１］，．．．，値ｐ［ｉ］と、ｍ−ｎビット長の１個の値ｐ［ｉ＋１］とを生成する機能を追加したハッシュ値演算装置１０の機能を示す機能ブロック図である。
図２２は、図２１に示すハッシュ値演算装置１０の動作を示すフローチャートである。
図２３は、図２１に示すハッシュ値演算装置１０により実現されるハッシュ関数の構造図である。
【０１０７】
図２１に示すハッシュ値演算装置１０の機能と動作について説明する。
図２１に示すハッシュ値演算装置１０は、図１８に示すハッシュ値演算装置１０が備える機能に加え、任意長値入力部１５、パディング部１６、分割部１７を備える。
【０１０８】
（Ｓ３１１：任意長値入力ステップ）
任意長値入力部１５は、任意ビット長の値Ｍを入力装置により入力する。
【０１０９】
（Ｓ３１２：パディングステップ）
パディング部１６は、（Ｓ３１１）で入力された値Ｍに対して、パディング関数ｐａｄを用いて、所定の値を付加して（（ｍ−ｓ）×ｉ＋（ｍ−ｎ））ビット長の値Ｍ’を処理装置により生成して記憶装置に記憶する。つまり、パディング部１６は、Ｍ’＝ｐａｄ（Ｍ）を処理装置により計算して値Ｍ’を得る。
【０１１０】
（Ｓ３１３：分割ステップ）
分割部１７は、（Ｓ３１２）で生成された値Ｍ’を処理装置によりｉ＋１個に分割して、ｍ−ｓビット長の値ｐ［１］，．．．，値ｐ［ｉ］と、ｍ−ｎビット長の１個の値ｐ［ｉ＋１］とを生成して記憶装置に記憶する。つまり、分割部１７は、Ｍ’＝ｐ［１］｜｜．．．｜｜ｐ［ｉ］｜｜ｐ［ｉ＋１］を処理装置により計算して値ｐ［１］，．．．，値ｐ［ｉ］と、値ｐ［ｉ＋１］とを得る。
【０１１１】
（Ｓ３１４：既定長値入力ステップ）
既定長値入力部１１は、（Ｓ３１３）で生成された値ｐ［１］，．．．，値ｐ［ｉ］と、値ｐ［ｉ＋１］とを入力装置により入力する。
【０１１２】
（Ｓ３１５）から（Ｓ３２１）までの処理は、（Ｓ３０２）から（Ｓ３０８）までの処理と同一である。
【０１１３】
（Ｓ３１２）におけるパディング方法の一例を説明する。
図２４は、以下に説明するパディング処理を行う場合の図２１に示すハッシュ値演算装置１０により実現されるハッシュ関数の構造図である。
（Ｓ３１２）でパディング部１６は、実施の形態１で説明した（Ｓ１１２）におけるパディング方法と同様に、（Ｓ３１１）で入力された値Ｍに対して、“１｜｜０・・・０｜｜＜Ｍ＞を付加して、ｍ−ｓビット長のｉ倍のビット長の値Ｍ’を処理装置により生成する。ここで、＜Ｍ＞は、Ｍのビット長｜Ｍ｜の６４ビット表現である。
このように、パディングして値Ｍ’を生成することにより、衝突困難性を高くすることができる。
【０１１４】
なお、実施の形態１と同様に、予めｉの値を決めておくのではなく、ｉの値は、入力された任意ビット長の値Ｍに応じて決定されるとしてもよい。この場合、値Ｍ’のビット長｜Ｍ’｜が「｜Ｍ’｜  ｍｏｄ  ｍ−ｓ＝ｍ−ｎ」となるように、値Ｍ’を生成すればよい。
【０１１５】
次に、図２１に示すハッシュ値演算装置１０の圧縮関数としてＳＨＡ−２５６を用いた場合の例を説明する。なお、ＳＨＡ−２５６の圧縮関数をＳＨＡ２５６と呼ぶ。ＳＨＡ２５６は、２５６ビット長の値と５１２ビット長の値との２つの値が入力された場合に、２５６ビット長の値を出力する関数である。
図２５は、圧縮関数としてＳＨＡ−２５６を用いる場合の図１２に示すハッシュ値演算装置１０により実現されるハッシュ関数の構造図である。
なお、以下の説明では、値ｓを５６として説明する。
【０１１６】
（Ｓ３１１）では、任意長値入力部１５は、任意ビット長の値Ｍを入力する。
（Ｓ３１２）では、パディング部１６は、（Ｓ３１１）で入力された値Ｍに対して、パディング関数ｐａｄを用いて、所定の値を付加して（（５１２−５６）×ｉ＋（５１２−２５６））ビット長の値Ｍ’を生成する。
（Ｓ３１３）では、分割部１７は、（Ｓ３１２）で生成された値Ｍ’をｉ個の４５６ビット長の値ｐ［１］，．．．，値ｐ［ｉ］と、１個の２５６ビット長の値ｐ［ｉ＋１］とに分割する。
（Ｓ３１４）では、既定長値入力部１１は、（Ｓ３１３）で生成されたｉ個の４５６ビット長の値ｐ［１］，．．．，値ｐ［ｉ］と、１個の２５６ビット長の値ｐ［ｉ＋１］とを入力する。
（Ｓ３１５）では、排他的論理和計算部１８は、（Ｓ３１４）で入力された４５６ビット長の値ｐ［１］，．．．，ｐ［ｉ］と、４５６ビット長の固定値ｙとを排他的論理和演算の入力として、ｓｕｍ＝ｐ［１］  ｘｏｒ，．．．，ｘｏｒ  ｐ［ｉ］  ｘｏｒ  ｙを計算して４５６ビット長の値ｓｕｍを得る。
（Ｓ３１６）では、固定値付加部１２は、（Ｓ３１１）で入力された４５６ビット長の値ｐ［１］，．．．，値ｐ［ｉ］のそれぞれに対して、５６ビット長の固定値ｃｏｎｓｔ［１］，．．．，固定値ｃｏｎｓｔ［ｉ］を付加して、５１２ビット長の値ｘ［１］，．．．，値ｘ［ｉ］を生成する。
（Ｓ３１７）では、圧縮関数計算部１３は、２５６ビット長の固定値ＩＶ１と、（Ｓ３１６）で生成された５１２ビット長の値ｘ［１］を圧縮関数ｈの入力として、ｃ［１］＝ｈ（ＩＶ１，ｘ［１］）を計算して２５６ビット長の値ｃ［１］を得る。
（Ｓ３１８）では、圧縮関数計算部１３は、ｊ＝２からｉまで順に、２５６ビット長の値ｃ［ｊ−１］と５１２ビット長の値ｘ［ｊ］とを圧縮関数ｈの入力として、ｃ［ｊ］＝ｈ（ｃ［ｊ−１］，ｘ［ｊ］）を計算して２５６ビット長の値ｃ［ｊ］を得る。
（Ｓ３１９）では、圧縮関数計算部１３は、（Ｓ３１８）で計算した２５６ビット長の値ｃ［ｉ］と、（Ｓ３１５）で計算された４５６ビット長の値ｓｕｍに５６ビット長の固定値ｃｏｎｓｔ［ｉ＋１］を付加した５１２ビット長の値ｘ［ｉ＋１］とを圧縮関数ｈの入力として、ｃ［ｉ＋１］＝ｈ（ｃ［ｉ］，ｘ［ｉ＋１］）を計算して２５６ビット長の値ｃ［ｉ＋１］を得る。
（Ｓ３２０）では、圧縮関数計算部１３は、２５６ビット長の固定値ＩＶ２と、（Ｓ３１５）で計算した２５６ビット長の値ｃ［ｉ＋１］に、（Ｓ３１４）で入力された２５６ビット長の値ｐ［ｉ＋１］を付加した値ｘ［ｉ＋２］とを圧縮関数ｈの入力として、ｃ［ｉ＋２］＝ｈ（ＩＶ２，ｘ［ｉ＋２］）を計算して２５６ビット長の値ｃ［ｉ＋２］を得る。
（Ｓ３２１）では、出力部１４は、（Ｓ３２０）で計算された値ｃ［ｉ＋２］を出力する。
【０１１７】
実施の形態３に係るハッシュ値演算装置１０により構成されたハッシュ関数は、圧縮関数ｈが一方向性が破られた理想的な圧縮関数の場合であっても、ランダムオラクルと強識別不可能性を満たすハッシュ関数となる。
【０１１８】
なお、実施の形態１と同様に、必ずしも上述した処理順序通りに計算する必要はなく、ストリーム処理ができる場合には、ストリーム処理で計算してもよい。
【０１１９】
また、実施の形態１と同様に、圧縮関数計算部１３は、ハッシュ値演算装置１０の外部に備える圧縮関数計算装置に入力値を入力して、圧縮関数計算装置に圧縮関数ｈを計算させることにより、圧縮関数ｈを計算した結果を得てもよい。
また、同様に、排他的論理和計算部１８は、ハッシュ値演算装置１０の外部に備える排他的論理和計算装置に入力値を入力して、排他的論理和計算装置に排他的論理和演算を計算させることにより、排他的論理和演算を計算した結果を得てもよい。
【０１２０】
また、圧縮関数計算部１３が値ｃ［１］，．．．，値ｃ［ｉ＋２］を計算するのに用いる圧縮関数ｈは、同一の圧縮関数ｈであってもよいし、それぞれ異なる圧縮関数ｈであってもよい。
【０１２１】
つまり、実施の形態３に係るハッシュ値演算装置１０をまとめると次のようになる。
ハッシュ値演算装置１０は、ｉ個のｍ−ｓビットの入力値ｍ［１］，…，ｍ［ｉ］とｍ−ｎビットの入力ｍ［ｉ＋１］に対して、圧縮関数演算装置に、ｎビット固定値ＩＶ１、第一メッセージｍ［１］、１のｓビット表現値を入力し、その出力ｃ［１］を得る。次に、圧縮関数演算装置に、ｎビット値ｃ［１］、第２メッセージｍ［２］、２のｓビット表現値を入力し、その出力ｃ［２］を得る。この処理を、第ｉメッセージまで同様に行い、その出力値ｃ［ｉ］を得る。圧縮関数演算装置に、ｎビット値ｃ［ｉ］、ｓｕｍ＝ｍ［１］  ｘｏｒ  …  ｘｏｒ  ｍ［ｉ］  ｘｏｒ  ｙ、ｉ＋１のｓビットの表現値を入力し、その出力ｃ［ｉ＋１］を得る。圧縮関数演算装置に、初期値ＩＶ２、ｍ−ｎビットのメッセージｍ［ｉ＋１］、ｎビット値ｃ［ｉ−１］を入力し、その出力ｃ［ｉ＋２］を得る。そして、ｃ［ｉ＋２］を出力することを特徴とする。ここで、ｙはｍ−ｓビット固定値である。
【０１２２】
また、ハッシュ値演算装置１０は、任意長の値Ｍから、任意長の値を入力とし、任意のパディング処理装置を用いて、メッセージＭ’を生成する。ただし、｜Ｍ’｜  ｍｏｄ  ｍ−ｓ＝  ｍ−ｎとなるようにする。分割処理装置を用いてＭ’をｉ個のｍ−ｓビットの値ｍ［１］，…，ｍ［ｉ］、ｍ−ｎビットの値ｍ［ｉ］に分割することを特徴とする。
【０１２３】
さらに、ハッシュ値演算装置１０は、パディング処理装置を、Ｍ｜｜１｜｜０…０｜｜＜Ｍ＞とし、ｓ＝５６とすることを特徴とする。但し、＜Ｍ＞はＭのビット長を６４ビットで表したものである。
【０１２４】
また、さらに、ハッシュ値演算装置１０は、圧縮関数演算装置として、ＳＨＡ−２５６の圧縮関数演算装置を用いたことを特徴とする。
【０１２５】
実施の形態４．
実施の形態４では、準一方向性が破られた理想的な圧縮関数を用いて構成した場合であっても、ランダムオラクルといわゆる強識別不可能である新たなハッシュ関数を構成するハッシュ値演算装置１０について説明する。
【０１２６】
図２６は、実施の形態４に係るハッシュ値演算装置１０の機能を示す機能ブロック図である。
図２７は、図２６に示すハッシュ値演算装置１０の動作を示すフローチャートである。
図２８は、図２６に示すハッシュ値演算装置１０により実現されるハッシュ関数の構造図である。
【０１２７】
図２６に示すハッシュ値演算装置１０の機能と動作について説明する。
図２６に示すハッシュ値演算装置１０は、既定長値入力部１１、固定値付加部１２、圧縮関数計算部１３、出力部１４、置換関数計算部１９を備える。
【０１２８】
（Ｓ４０１：既定長値入力ステップ）
既定長値入力部１１は、ｍ−ｎビット長のｉ個の値ｐ［１］，．．．，値ｐ［ｉ］を入力装置により入力して記憶装置に記憶する。
【０１２９】
（Ｓ４０２：固定値付加ステップ）
固定値付加部１２は、（Ｓ４０１）で入力されたｍ−ｎビット長のｉ個の値ｐ［１］，．．．，値ｐ［ｉ］のそれぞれに対して、予め記憶装置に記憶したｎビット長の固定値ｃｏｎｓｔ［１］，．．．，固定値ｃｏｎｓｔ［ｉ］を付加して、ｍビット長の値ｘ［１］，．．．，値ｘ［ｉ］を処理装置により生成して記憶装置に記憶する。
つまり、固定値付加部１２は、値ｐ［１］に固定値ｃｏｎｓｔ［１］を付加して、値ｘ［１］を生成する。固定値付加部１２は、値ｐ［２］に固定値ｃｏｎｓｔ［２］を付加して、値ｘ［２］を生成する。以下同様に、ｊ＝３，．．．，ｉに対して、固定値付加部１２は、値ｐ［ｊ］に固定値ｃｏｎｓｔ［ｊ］を付加して、値ｘ［ｊ］を生成する。
なお、ｊ＝１，．．．，ｉについて、値ｐ［ｊ］に固定値ｃｏｎｓｔ［ｊ］を付加する位置は、どこであってもよい。つまり、固定値ｃｏｎｓｔ［ｊ］は、値ｐ［ｊ］の前や後に追加してもよいし、値ｐ［ｊ］の間に挿入してもよい。
また、固定値ｃｏｎｓｔ［１］＝固定値ｃｏｎｓｔ［２］＝．．．＝固定値ｃｏｎｓｔ［ｉ］でもよいし、固定値ｃｏｎｓｔ［１］≠固定値ｃｏｎｓｔ［２］≠．．．≠固定値ｃｏｎｓｔ［ｉ］でもよい。
【０１３０】
（Ｓ４０３：第１圧縮関数計算ステップ）
圧縮関数計算部１３は、予め記憶装置に記憶したｎビット長の固定値ＩＶ１と、（Ｓ４０２）で生成されたｍビット長の値ｘ［１］を圧縮関数ｈの入力として、ｃ［１］＝ｈ（ＩＶ１，ｘ［１］）を処理装置により計算してｎビット長の値ｃ［１］を得て記憶装置に記憶する。
【０１３１】
（Ｓ４０４：第２圧縮関数計算ステップ）
圧縮関数計算部１３は、ｊ＝２からｉ−１まで順に、ｎビット長の値ｃ［ｊ−１］とｍビット長の値ｘ［ｊ］とを圧縮関数ｈの入力として、ｃ［ｊ］＝ｈ（ｃ［ｊ−１］，ｘ［ｊ］）を処理装置により計算してｎビット長の値ｃ［ｊ］を得て記憶装置に記憶する。
つまり、まず、圧縮関数計算部１３は、（Ｓ４０３）で計算したｎビット長の値ｃ［１］と、（Ｓ４０２）で生成されたｍビット長の値ｘ［２］とを入力として、ｃ［２］＝ｈ（ｃ［１］，ｘ［２］）を処理装置により計算してｎビット長の値ｃ［２］を得る。
次に、圧縮関数計算部１３は、計算したｎビット長の値ｃ［２］と、（Ｓ４０２）で生成されたｍビット長の値ｘ［３］とを入力として、ｃ［３］＝ｈ（ｃ［２］，ｘ［３］）を処理装置により計算してｎビット長の値ｃ［３］を得る。
これを繰り返して、最終的に、圧縮関数計算部１３は、計算したｎビット長の値ｃ［ｉ−２］と、（Ｓ４０２）で生成されたｍビット長の値ｘ［ｉ−１］とを入力として、ｃ［ｉ−１］＝ｈ（ｃ［ｉ−２］，ｘ［ｉ−１］）を処理装置により計算してｎビット長の値ｃ［ｉ−１］を得る。
【０１３２】
（Ｓ４０５：置換関数計算ステップ）
置換関数計算部１９は、（Ｓ４０４）で計算されたｎビット長の値ｃ［ｉ−１］を置換関数πの入力として、ｃ’［ｉ−１］＝π（ｃ［ｉ−１］）を処理装置により計算してｎビット長の値ｃ’［ｉ−１］を得て記憶装置に記憶する。
なお、置換関数πは、任意の値ａを入力した場合に値ａとは異なる値ａ’に置換する置換関数であって、値ａを入力した場合に入力した値ａがそのまま出力されることのない置換関数である。つまり、置換関数πは、π（ａ）＝ａとなるような固定点（Ｆｉｘｅｄ  Ｐｏｉｎｔ）を有さない置換関数である。
【０１３３】
（Ｓ４０６：第３圧縮関数計算ステップ）
圧縮関数計算部１３は、（Ｓ４０５）で計算されたｎビット長の値ｃ’［ｉ−１］と、（Ｓ４０２）で生成されたｍビット長の値ｘ［ｉ］とを圧縮関数ｈの入力として、ｃ［ｉ］＝ｈ（ｃ’［ｉ−１］，ｘ［ｉ］）を処理装置により計算してｎビット長の値ｃ［ｉ］を得て記憶装置に記憶する。
【０１３４】
（Ｓ４０７：出力ステップ）
出力部１４は、（Ｓ４０６）で計算された値ｃ［ｉ］を出力装置により出力する。
【０１３５】
なお、ｉ＝２の場合、つまり（Ｓ４０１）で２個の値ｐ［１］と値ｐ［２］とのみが入力された場合には、（Ｓ４０４）は実行されない。つまり、（Ｓ４０３）で値ｃ［１］を得た後、（Ｓ４０５）で値ｃ［１］を入力として、値ｃ’［１］を得る。そして、（Ｓ４０６）で値ｃ’［１］と値ｘ［２］とを入力として、値ｃ［２］を得る。
【０１３６】
また、ｉ＝１の場合、つまり（Ｓ４０１）で１個の値ｐ［１］のみが入力された場合には、（Ｓ４０３）と（Ｓ４０４）とは実行されない。つまり、（Ｓ４０２）で値ｘ［１］が生成された後、（Ｓ４０５）で固定値ＩＶ１を入力として、値ＩＶ１’を得る。そして、（Ｓ４０６）で値ＩＶ１’と値ｘ［１］とを入力として、値ｃ［１］を得る。
【０１３７】
以上をまとめると、次のようになる。
まず、ハッシュ値演算装置１０は、ｊ＝１からｉ−１まで順に、ｃ［ｊ］＝ｈ（ｃ［ｊ−１］，ｐ［ｊ］｜｜ｃｏｎｓｔ［ｊ］）を計算する。ここで、ｃ［０］は、ＩＶ１とする。
次に、ハッシュ値演算装置１０は、ｃ［ｉ］＝ｈ（π（ｃ［ｉ−１］），ｐ［ｉ］｜｜ｃｏｎｓｔ［ｉ］）を計算する。
そして、ハッシュ値演算装置１０は、値ｃ［ｉ］を出力する。
【０１３８】
上記説明では、（Ｓ４０１）で既定長値入力部１１が、ｍ−ｎビット長のｉ個の値ｐ［１］，．．．，値ｐ［ｉ］を入力するとした。しかし、通常、ハッシュ関数へ入力される値は、１個の任意ビット長の値である。つまり、上記説明では、１個の任意ビット長の値が入力された場合に、どのようにｍ−ｎビット長のｉ個の値ｐ［１］，．．．，値ｐ［ｉ］を生成するのかについては説明を省略した。
次に、任意ビット長の値が入力された場合に、ｍ−ｎビット長のｉ個の値ｐ［１］，．．．，値ｐ［ｉ］を生成する機能を追加したハッシュ値演算装置１０について説明する。
【０１３９】
図２９は、図２６に示すハッシュ値演算装置１０に、任意ビット長の値が入力された場合に、ｍ−ｎビット長のｉ個の値ｐ［１］，．．．，値ｐ［ｉ］を生成する機能を追加したハッシュ値演算装置１０の機能を示す機能ブロック図である。
図３０は、図２９に示すハッシュ値演算装置１０の動作を示すフローチャートである。
図３１は、図２９に示すハッシュ値演算装置１０により実現されるハッシュ関数の構造図である。
【０１４０】
図２９に示すハッシュ値演算装置１０の機能と動作について説明する。
図２９に示すハッシュ値演算装置１０は、図１に示すハッシュ値演算装置１０が備える機能に加え、任意長値入力部１５、パディング部１６、分割部１７を備える。
【０１４１】
（Ｓ４１１：任意長値入力ステップ）
任意長値入力部１５は、任意ビット長の値Ｍを入力装置により入力する。
【０１４２】
（Ｓ４１２：パディングステップ）
パディング部１６は、（Ｓ４１１）で入力された値Ｍに対して、パディング関数ｐａｄを用いて、所定の値を付加してｍ−ｎビット長のｉ倍のビット長の値Ｍ’を処理装置により生成して記憶装置に記憶する。つまり、パディング部１６は、Ｍ’＝ｐａｄ（Ｍ）を処理装置により計算して値Ｍ’を得る。
【０１４３】
（Ｓ４１３：分割ステップ）
分割部１７は、（Ｓ４１２）で生成された値Ｍ’を処理装置によりｉ個に分割して、ｍ−ｎビット長の値ｐ［１］，．．．，値ｐ［ｉ］を生成して記憶装置に記憶する。つまり、分割部１７は、Ｍ’＝ｐ［１］｜｜．．．｜｜ｐ［ｉ］を処理装置により計算して値ｐ［１］，．．．，値ｐ［ｉ］を得る。
【０１４４】
（Ｓ４１４：既定長値入力ステップ）
既定長値入力部１１は、（Ｓ４１３）で生成された値ｐ［１］，．．．，値ｐ［ｉ］を入力装置により入力する。
【０１４５】
（Ｓ４１５）から（Ｓ４２０）までの処理は、（Ｓ４０２）から（Ｓ４０７）までの処理と同一である。
【０１４６】
（Ｓ４１２）におけるパディング方法の一例を説明する。
図３２は、以下に説明する所定のパディング処理を行う場合の図２９に示すハッシュ値演算装置１０により実現されるハッシュ関数の構造図である。
（Ｓ４１２）でパディング部１６は、（Ｓ４１１）で入力された値Ｍに対して、“１｜｜０・・・０｜｜＜Ｍ＞を付加して、ｍ−ｎビット長のｉ倍のビット長の値Ｍ’を処理装置により生成する。ここで、＜Ｍ＞は、Ｍのビット長｜Ｍ｜の６４ビット表現である。
このように、パディングして値Ｍ’を生成することにより、衝突困難性を高くすることができる。
【０１４７】
なお、実施の形態１と同様に、予めｉの値を決めておくのではなく、ｉの値は、入力された任意ビット長の値Ｍに応じて決定されるとしてもよい。
【０１４８】
次に、図３２に示すハッシュ値演算装置１０の圧縮関数としてＳＨＡ−２５６を用いた場合の例を説明する。なお、ＳＨＡ−２５６の圧縮関数をＳＨＡ２５６と呼ぶ。ＳＨＡ２５６は、２５６ビット長の値と５１２ビット長の値との２つの値が入力された場合に、２５６ビット長の値を出力する関数である。
図３３は、圧縮関数としてＳＨＡ−２５６を用いる場合の図２９に示すハッシュ値演算装置１０により実現されるハッシュ関数の構造図である。
【０１４９】
（Ｓ４１１）では、任意長値入力部１５は、任意ビット長の値Ｍを入力する。
（Ｓ４１２）では、パディング部１６は、（Ｓ４１１）で入力された値Ｍに対して、パディング関数ｐａｄを用いて、所定の値を付加して２５６（＝５１２−２５６）ビット長のｉ倍のビット長の値Ｍ’を生成する。
（Ｓ４１３）では、分割部１７は、（Ｓ４１２）で生成された値Ｍ’をｉ個に分割して、２５６ビット長の値ｐ［１］，．．．，値ｐ［ｉ］を生成する。
（Ｓ４１４）では、既定長値入力部１１は、（Ｓ４１３）で生成された２５６ビット長の値ｐ［１］，．．．，値ｐ［ｉ］を入力する。
（Ｓ４１５）では、固定値付加部１２は、（Ｓ４１４）で入力された２５６ビット長の値ｐ［１］，．．．，値ｐ［ｉ］のそれぞれに対して、２５６ビット長の固定値ｃｏｎｓｔ［１］，．．．，固定値ｃｏｎｓｔ［ｉ］を付加して、５１２ビット長の値ｘ［１］，．．．，値ｘ［ｉ］を生成する。
（Ｓ４１６）では、圧縮関数計算部１３は、２５６ビット長の固定値ＩＶ１と、（Ｓ４１５）で生成された５１２ビット長の値ｘ［１］を圧縮関数ｈの入力として、ｃ［１］＝ｈ（ＩＶ１，ｘ［１］）を計算して２５６ビット長の値ｃ［１］を得る。
（Ｓ４１７）では、圧縮関数計算部１３は、ｊ＝２からｉ−１まで順に、２５６ビット長の値ｃ［ｊ−１］と５１２ビット長の値ｘ［ｊ］とを圧縮関数ｈの入力として、ｃ［ｊ］＝ｈ（ｃ［ｊ−１］，ｘ［ｊ］）を計算して２５６ビット長の値ｃ［ｊ］を得る。
（Ｓ４１８）では、置換関数計算部１９は、（Ｓ４１７）で計算された２５６ビット長の値ｃ［ｉ−１］を置換関数πの入力として、ｃ’［ｉ−１］＝π（ｃ［ｉ−１］）を計算して２５６ビット長の値ｃ’［ｉ−１］を得る。
（Ｓ４１９）では、圧縮関数計算部１３は、（Ｓ４１８）で計算された２５６ビット長の値ｃ’［ｉ−１］と、（Ｓ４１５）で生成された５１２ビット長の値ｘ［ｉ］とを圧縮関数ｈの入力として、ｃ［ｉ］＝ｈ（ｃ’［ｉ−１］，ｘ［ｉ］）を計算して２５６ビット長の値ｃ［ｉ］を得る。
（Ｓ４２０）では、出力部１４は、（Ｓ４１９）で計算された値ｃ［ｉ］を出力する。
【０１５０】
実施の形態４に係るハッシュ値演算装置１０により構成されたハッシュ関数は、圧縮関数ｈが準一方向性が破られた理想的な圧縮関数の場合であっても、ランダムオラクルと強識別不可能性を満たすハッシュ関数となる。
【０１５１】
なお、実施の形態１と同様に、必ずしも上述した処理順序通りに計算する必要はなく、ストリーム処理ができる場合には、ストリーム処理で計算してもよい。
【０１５２】
また、実施の形態１と同様に、圧縮関数計算部１３は、ハッシュ値演算装置１０の外部に備える圧縮関数計算装置に入力値を入力して、圧縮関数計算装置に圧縮関数ｈを計算させることにより、圧縮関数ｈを計算した結果を得てもよい。
また、同様に、置換関数計算部１９は、ハッシュ値演算装置１０の外部に備える置換関数演算装置に入力値を入力して、置換関数演算装置に置換関数πを計算させることにより、置換関数演算を計算した結果を得てもよい。
【０１５３】
また、圧縮関数計算部１３が値ｃ［１］，．．．，値ｃ［ｉ］を計算するのに用いる圧縮関数ｈは、同一の圧縮関数ｈであってもよいし、それぞれ異なる圧縮関数ｈであってもよい。
【０１５４】
つまり、実施の形態４に係るハッシュ値演算装置１０をまとめると次のようになる。
ハッシュ値演算装置１０は、ｉ個のｍ−ｓビットの入力値ｐ［１］，．．．，ｐ［ｉ］に対して、圧縮関数演算装置に、ｎビット固定値ＩＶ１、第１メッセージｐ［１］、ｎビット固定値ｃｏｎｓｔ［１］を入力し、その出力ｃ［１］を得る。次に、圧縮関数演算装置に、ｎビット値ｃ［１］、第２メッセージｐ［２］、ｎビット固定値ｃｏｎｓｔ［２］を入力し、その出力ｃ［２］を得る。この処理を、第ｉ−１メッセージまで同様に行い、その出力値ｃ［ｉ−１］を得る。ｆｉｘｅｄ  ｐｏｉｎｔを持たないｎビット上の任意の置換関数πを用いて、ｃ＝π（ｃ［ｉ−１］）を計算する。圧縮関数演算装置に、ｎビット値ｃ、第ｉメッセージｐ［ｉ］、ｎビット固定値ｃｏｎｓｔ［ｉ］を入力し、その出力ｃ［ｉ］を得る。そして、ｃ［ｉ］を出力することを特徴とする。
【０１５５】
また、ハッシュ値演算装置１０は、任意長の値Ｍから、任意長の値を入力とし、ｍ−ｎビットの値を出力する任意のパディング処理装置を用いて、ｍ−ｎビットの倍数となるメッセージＭ’を生成する。分割処理装置を用いてＭ’をｉ個のｍ−ｎビットの値ｐ［１］，．．．，ｐ［ｉ］に分割することを特徴とする。
【０１５６】
さらに、ハッシュ値演算装置１０は、パディング処理装置を、Ｍ｜｜１｜｜０．．．０｜｜＜Ｍ＞とすることを特徴とする。但し、＜Ｍ＞はＭのビット長を６４ビットで表したものである。
【０１５７】
また、さらに、ハッシュ値演算装置１０は、圧縮関数演算装置として、ＳＨＡ−２５６の圧縮関数演算装置を用いたことを特徴とする。
【０１５８】
実施の形態５．
実施の形態５では、実施の形態４とは異なるハッシュ関数であって、準一方向性が破られた理想的な圧縮関数を用いて構成した場合であっても、ランダムオラクルといわゆる強識別不可能である新たなハッシュ関数を構成するハッシュ値演算装置１０について説明する。
【０１５９】
図３４は、実施の形態５に係るハッシュ値演算装置１０の機能を示す機能ブロック図である。
図３５は、図３４に示すハッシュ値演算装置１０の動作を示すフローチャートである。
図３６は、図３４に示すハッシュ値演算装置１０により実現されるハッシュ関数の構造図である。
【０１６０】
図３４に示すハッシュ値演算装置１０の機能と動作について説明する。
図３４に示すハッシュ値演算装置１０は、既定長値入力部１１、固定値付加部１２、圧縮関数計算部１３、出力部１４、排他的論理和計算部１８、置換関数計算部１９を備える。
【０１６１】
（Ｓ５０１：既定長値入力ステップ）
既定長値入力部１１は、ｍ−ｓビット長のｉ個の値ｐ［１］，．．．，値ｐ［ｉ］を入力装置により入力して記憶装置に記憶する。
【０１６２】
（Ｓ５０２：排他的論理和計算ステップ）
排他的論理和計算部１８は、（Ｓ５０１）で入力されたｍ−ｓビット長の値ｐ［１］，．．．，ｐ［ｉ］と、予め記憶装置に記憶したｍ−ｓビット長の固定値ｙとを排他的論理和演算の入力として、ｓｕｍ＝ｐ［１］  ｘｏｒ，．．．，ｘｏｒ  ｐ［ｉ］  ｘｏｒ  ｙを処理装置により計算してｍ−ｓビット長の値ｓｕｍを得て記憶装置に記憶する。
【０１６３】
（Ｓ５０３：固定値付加ステップ）
固定値付加部１２は、（Ｓ５０１）で入力されたｍ−ｓビット長の値ｐ［１］，．．．，値ｐ［ｉ］のそれぞれに対して、予め記憶装置に記憶したｓビット長の固定値ｃｏｎｓｔ［１］，．．．，固定値ｃｏｎｓｔ［ｉ］を付加して、ｍビット長の値ｘ［１］，．．．，値ｘ［ｉ］を処理装置により生成して記憶装置に記憶する。
つまり、固定値付加部１２は、値ｐ［１］に固定値ｃｏｎｓｔ［１］を付加して、値ｘ［１］を生成する。固定値付加部１２は、値ｐ［２］に固定値ｃｏｎｓｔ［２］を付加して、値ｘ［２］を生成する。以下同様に、ｊ＝３，．．．，ｉに対して、固定値付加部１２は、値ｐ［ｊ］に固定値ｃｏｎｓｔ［ｊ］を付加して、値ｘ［ｊ］を生成する。
なお、ｊ＝１，．．．，ｉ−１について、値ｐ［ｊ］に固定値ｃｏｎｓｔ［ｊ］を付加する位置は、どこであってもよい。つまり、固定値ｃｏｎｓｔ［ｊ］は、値ｐ［ｊ］の前や後に追加してもよいし、値ｐ［ｊ］の間に挿入してもよい。
また、固定値ｃｏｎｓｔ［１］≠固定値ｃｏｎｓｔ［２］≠．．．≠固定値ｃｏｎｓｔ［ｉ］である。例えば、ｊ＝１，．．．，ｉについて、固定値ｃｏｎｓｔ［ｊ］は、ｊをｓビットで表現した値＜ｊ＞である。
【０１６４】
（Ｓ５０４：第１圧縮関数計算ステップ）
圧縮関数計算部１３は、予め記憶装置に記憶したｎビット長の固定値ＩＶ１と、（Ｓ５０３）で生成されたｍビット長の値ｘ［１］を圧縮関数ｈの入力として、ｃ［１］＝ｈ（ＩＶ１，ｘ［１］）を処理装置により計算してｎビット長の値ｃ［１］を得て記憶装置に記憶する。
【０１６５】
（Ｓ５０５：第２圧縮関数計算ステップ）
圧縮関数計算部１３は、ｊ＝２からｉまで順に、ｎビット長の値ｃ［ｊ−１］とｍビット長の値ｘ［ｊ］とを圧縮関数ｈの入力として、ｃ［ｊ］＝ｈ（ｃ［ｊ−１］，ｘ［ｊ］）を処理装置により計算してｎビット長の値ｃ［ｊ］を得て記憶装置に記憶する。
つまり、まず、圧縮関数計算部１３は、（Ｓ５０４）で計算したｎビット長の値ｃ［１］と、（Ｓ５０３）で生成されたｍビット長の値ｘ［２］とを入力として、ｃ［２］＝ｈ（ｃ［１］，ｘ［２］）を処理装置により計算してｎビット長の値ｃ［２］を得る。
次に、圧縮関数計算部１３は、計算したｎビット長の値ｃ［２］と、（Ｓ５０３）で生成されたｍビット長の値ｘ［３］とを入力として、ｃ［３］＝ｈ（ｃ［２］，ｘ［３］）を処理装置により計算してｎビット長の値ｃ［３］を得る。
これを繰り返して、最終的に、圧縮関数計算部１３は、計算したｎビット長の値ｃ［ｉ−１］と、（Ｓ５０３）で生成されたｍビット長の値ｘ［ｉ］とを入力として、ｃ［ｉ］＝ｈ（ｃ［ｉ−１］，ｘ［ｉ］）を処理装置により計算してｎビット長の値ｃ［ｉ］を得る。
【０１６６】
（Ｓ５０６：置換関数計算ステップ）
置換関数計算部１９は、（Ｓ５０５）で計算されたｎビット長の値ｃ［ｉ］を置換関数πの入力として、ｃ’［ｉ］＝π（ｃ［ｉ］）を処理装置により計算してｎビット長の値ｃ’［ｉ］を得て記憶装置に記憶する。
なお、置換関数πは、任意の値ａを入力した場合に値ａとは異なる値ａ’に置換する置換関数であって、値ａを入力した場合に入力した値ａがそのまま出力されることのない置換関数である。つまり、置換関数πは、π（ａ）＝ａとなるような固定点（Ｆｉｘｅｄ  Ｐｏｉｎｔ）を有さない置換関数である。
【０１６７】
（Ｓ５０７：第３圧縮関数計算ステップ）
圧縮関数計算部１３は、（Ｓ５０６）で計算されたｎビット長の値ｃ’［ｉ］と、（Ｓ５０２）で計算されたｍ−ｓビット長の値ｓｕｍにｓビット長の固定値ｃｏｎｓｔ［ｉ＋１］を付加したｍビット長のｘ［ｉ＋１］を圧縮関数ｈの入力として、ｃ［ｉ＋１］＝ｈ（ｃ’［ｉ］，ｘ［ｉ＋１］）を処理装置により計算してｎビット長の値ｃ［ｉ＋１］を得て記憶装置に記憶する。
なお、固定値ｃｏｎｓｔ［ｉ＋１］≠固定値ｃｏｎｓｔ［１］≠．．．≠固定値ｃｏｎｓｔ［ｉ］である。例えば、固定値ｃｏｎｓｔ［ｉ＋１］は、ｉ＋１をｓビットで表現した値＜ｉ＋１＞である。
また、値ｓｕｍに固定値ｃｏｎｓｔ［ｉ＋１］を付加する位置は、どこであってもよい。つまり、固定値ｃｏｎｓｔ［ｉ＋１］は、値ｓｕｍの前や後に追加してもよいし、値ｓｕｍの間に挿入してもよい。
【０１６８】
（Ｓ５０８：出力ステップ）
出力部１４は、（Ｓ５０７）で計算された値ｃ［ｉ＋１］を出力装置により出力する。
【０１６９】
なお、ｉ＝１の場合、つまり（Ｓ５０１）で１個の値ｐ［１］のみが入力された場合には、（Ｓ５０５）は実行されない。つまり、（Ｓ５０４）で値ｃ［１］を得た後、（Ｓ５０６）で値ｃ［１］を入力として、値ｃ’［１］を得る。そして、（Ｓ５０７）で値ｃ’［１］と値ｓｕｍに固定値ｃｏｎｓｔ［ｉ＋１］を付加した値ｘ［２］とを入力として、値ｃ［２］を得る。
【０１７０】
以上をまとめると、次のようになる。
まず、ハッシュ値演算装置１０は、ｓｕｍ＝ｐ［１］  ｘｏｒ，．．．，ｘｏｒ  ｐ［ｉ］  ｘｏｒ  ｙを処理装置により計算する。
また、ハッシュ値演算装置１０は、ｊ＝１からｉまで順に、ｃ［ｊ］＝ｈ（ｃ［ｊ−１］，ｐ［ｊ］｜｜＜ｊ＞）を計算する。ここで、ｃ［０］は、ＩＶ１とする。
次に、ハッシュ値演算装置１０は、ｃ［ｉ＋１］＝ｈ（π（ｃ［ｉ］），ｓｕｍ｜｜＜ｉ＋１＞）を計算する。
そして、ハッシュ値演算装置１０は、値ｃ［ｉ＋１］を出力する。
【０１７１】
上記説明では、（Ｓ５０１）で既定長値入力部１１が、ｍ−ｓビット長のｉ個の値ｐ［１］，．．．，値ｐ［ｉ］を入力するとした。しかし、通常、ハッシュ関数へ入力される値は、１個の任意ビット長の値である。つまり、上記説明では、１個の任意ビット長の値が入力された場合に、どのようにｍ−ｓビット長のｉ個の値ｐ［１］，．．．，値ｐ［ｉ］を生成するのかについては説明を省略した。
次に、任意ビット長の値が入力された場合に、ｍ−ｓビット長のｉ個の値ｐ［１］，．．．，値ｐ［ｉ］を生成する機能を追加したハッシュ値演算装置１０について説明する。
【０１７２】
図３７は、図３４に示すハッシュ値演算装置１０に、任意ビット長の値が入力された場合に、ｍ−ｓビット長のｉ個の値ｐ［１］，．．．，値ｐ［ｉ］を生成する機能を追加したハッシュ値演算装置１０の機能を示す機能ブロック図である。
図３８は、図３７に示すハッシュ値演算装置１０の動作を示すフローチャートである。
図３９は、図３７に示すハッシュ値演算装置１０により実現されるハッシュ関数の構造図である。
【０１７３】
図３７に示すハッシュ値演算装置１０の機能と動作について説明する。
図３７に示すハッシュ値演算装置１０は、図３４に示すハッシュ値演算装置１０が備える機能に加え、任意長値入力部１５、パディング部１６、分割部１７を備える。
【０１７４】
（Ｓ５１１：任意長値入力ステップ）
任意長値入力部１５は、任意ビット長の値Ｍを入力装置により入力する。
【０１７５】
（Ｓ５１２：パディングステップ）
パディング部１６は、（Ｓ５１１）で入力された値Ｍに対して、パディング関数ｐａｄを用いて、所定の値を付加してｍ−ｓビット長のｉ倍のビット長の値Ｍ’を処理装置により生成して記憶装置に記憶する。つまり、パディング部１６は、Ｍ’＝ｐａｄ（Ｍ）を処理装置により計算して値Ｍ’を得る。
【０１７６】
（Ｓ５１３：分割ステップ）
分割部１７は、（Ｓ５１２）で生成された値Ｍ’を処理装置によりｉ個に分割して、ｍ−ｓビット長の値ｐ［１］，．．．，値ｐ［ｉ］を生成して記憶装置に記憶する。つまり、分割部１７は、Ｍ’＝ｐ［１］｜｜．．．｜｜ｐ［ｉ］を処理装置により計算して値ｐ［１］，．．．，値ｐ［ｉ］を得る。
【０１７７】
（Ｓ５１４：既定長値入力ステップ）
既定長値入力部１１は、（Ｓ５１３）で生成された値ｐ［１］，．．．，値ｐ［ｉ］を入力装置により入力する。
【０１７８】
（Ｓ５１５）から（Ｓ５２１）までの処理は、（Ｓ５０２）から（Ｓ５０８）までの処理と同一である。
【０１７９】
（Ｓ５１２）におけるパディング方法の一例を説明する。
図４０は、以下に説明するパディング処理を行う場合の図３７に示すハッシュ値演算装置１０により実現されるハッシュ関数の構造図である。
（Ｓ５１２）でパディング部１６は、実施の形態１で説明した（Ｓ１１２）におけるパディング方法と同様に、（Ｓ５１１）で入力された値Ｍに対して、“１｜｜０・・・０｜｜＜Ｍ＞を付加して、ｍ−ｓビット長のｉ倍のビット長の値Ｍ’を処理装置により生成する。ここで、＜Ｍ＞は、Ｍのビット長｜Ｍ｜の６４ビット表現である。
このように、パディングして値Ｍ’を生成することにより、衝突困難性を高くすることができる。
【０１８０】
図４１は、以下に説明するパディング処理を行う場合の図３７に示すハッシュ値演算装置１０により実現されるハッシュ関数の構造図である。
（Ｓ５１２）でパディング部１６は、（Ｓ５１１）で入力された値Ｍに対して、“１｜｜０・・・０を付加して、ｍ−ｓビット長のｉ倍のビット長の値Ｍ’を処理装置により生成する。
このように、パディングして値Ｍ’を生成しても、衝突困難性を高くすることができる。
【０１８１】
なお、実施の形態１と同様に、予めｉの値を決めておくのではなく、ｉの値は、入力された任意ビット長の値Ｍに応じて決定されるとしてもよい。
【０１８２】
次に、図３７に示すハッシュ値演算装置１０の圧縮関数としてＳＨＡ−２５６を用いた場合の例を説明する。なお、ＳＨＡ−２５６の圧縮関数をＳＨＡ２５６と呼ぶ。ＳＨＡ２５６は、２５６ビット長の値と５１２ビット長の値との２つの値が入力された場合に、２５６ビット長の値を出力する関数である。
図４２は、圧縮関数としてＳＨＡ−２５６を用いる場合の図３７に示すハッシュ値演算装置１０により実現されるハッシュ関数の構造図である。
なお、以下の説明では、値ｓを５６として説明する。
【０１８３】
（Ｓ５１１）では、任意長値入力部１５は、任意ビット長の値Ｍを入力する。
（Ｓ５１２）では、パディング部１６は、（Ｓ５１１）で入力された値Ｍに対して、パディング関数ｐａｄを用いて、所定の値を付加して４５６（＝５１２−５６）ビット長のｉ倍のビット長の値Ｍ’を生成する。
（Ｓ５１３）では、分割部１７は、（Ｓ５１２）で生成された値Ｍ’をｉ個に分割して、４５６ビット長の値ｐ［１］，．．．，値ｐ［ｉ］を生成する。
（Ｓ５１４）では、既定長値入力部１１は、（Ｓ５１３）で生成された４５６ビット長の値ｐ［１］，．．．，値ｐ［ｉ］を入力する。
（Ｓ５１５）では、排他的論理和計算部１８は、（Ｓ５１４）で入力された４５６ビット長の値ｐ［１］，．．．，ｐ［ｉ］と、４５６ビット長の固定値ｙとを排他的論理和演算の入力として、ｓｕｍ＝ｐ［１］  ｘｏｒ，．．．，ｘｏｒ  ｐ［ｉ］  ｘｏｒ  ｙを計算して４５６ビット長の値ｓｕｍを得る。
（Ｓ５１６）では、固定値付加部１２は、（Ｓ５１１）で入力された４５６ビット長の値ｐ［１］，．．．，値ｐ［ｉ］のそれぞれに対して、５６ビット長の固定値ｃｏｎｓｔ［１］，．．．，固定値ｃｏｎｓｔ［ｉ］を付加して、５１２ビット長の値ｘ［１］，．．．，値ｘ［ｉ］を生成する。
（Ｓ５１７）では、圧縮関数計算部１３は、２５６ビット長の固定値ＩＶ１と、（Ｓ５１６）で生成された５１２ビット長の値ｘ［１］を圧縮関数ｈの入力として、ｃ［１］＝ｈ（ＩＶ１，ｘ［１］）を計算して２５６ビット長の値ｃ［１］を得る。
（Ｓ５１８）では、圧縮関数計算部１３は、ｊ＝２からｉまで順に、２５６ビット長の値ｃ［ｊ−１］と５１２ビット長の値ｘ［ｊ］とを圧縮関数ｈの入力として、ｃ［ｊ］＝ｈ（ｃ［ｊ−１］，ｘ［ｊ］）を計算して２５６ビット長の値ｃ［ｊ］を得る。
（Ｓ５１９）では、置換関数計算部１９は、（Ｓ５１８）で計算された２５６ビット長の値ｃ［ｉ］を置換関数πの入力として、ｃ’［ｉ］＝π（ｃ［ｉ］）を計算して２５６ビット長の値ｃ’［ｉ］を得る。
（Ｓ５２０）では、圧縮関数計算部１３は、（Ｓ５１９）で計算された２５６ビット長の値ｃ’［ｉ］と、（Ｓ５１５）で計算された４５６ビット長の値ｓｕｍに５６ビット長の固定値ｃｏｎｓｔ［ｉ＋１］を付加した５１２ビット長のｘ［ｉ＋１］を圧縮関数ｈの入力として、ｃ［ｉ＋１］＝ｈ（ｃ’［ｉ］，ｘ［ｉ＋１］）を計算して２５６ビット長の値ｃ［ｉ＋１］を得る。
（Ｓ５２１）では、出力部１４は、（Ｓ５２０）で計算された値ｃ［ｉ＋１］を出力する。
【０１８４】
実施の形態５に係るハッシュ値演算装置１０により構成されたハッシュ関数は、圧縮関数ｈが準一方向性が破られた理想的な圧縮関数の場合であっても、ランダムオラクルと強識別不可能性を満たすハッシュ関数となる。
【０１８５】
なお、実施の形態１と同様に、必ずしも上述した処理順序通りに計算する必要はなく、ストリーム処理ができる場合には、ストリーム処理で計算してもよい。
【０１８６】
また、実施の形態１と同様に、圧縮関数計算部１３は、ハッシュ値演算装置１０の外部に備える圧縮関数計算装置に入力値を入力して、圧縮関数計算装置に圧縮関数ｈを計算させることにより、圧縮関数ｈを計算した結果を得てもよい。
また、同様に、排他的論理和計算部１８は、ハッシュ値演算装置１０の外部に備える排他的論理和計算装置に入力値を入力して、排他的論理和計算装置に排他的論理和演算を計算させることにより、排他的論理和演算を計算した結果を得てもよい。同様に、置換関数計算部１９は、ハッシュ値演算装置１０の外部に備える置換関数演算装置に入力値を入力して、置換関数演算装置に置換関数πを計算させることにより、置換関数演算を計算した結果を得てもよい。
【０１８７】
また、圧縮関数計算部１３が値ｃ［１］，．．．，値ｃ［ｉ＋１］を計算するのに用いる圧縮関数ｈは、同一の圧縮関数ｈであってもよいし、それぞれ異なる圧縮関数ｈであってもよい。
【０１８８】
つまり、実施の形態５に係るハッシュ値演算装置１０をまとめると次のようになる。
ハッシュ値演算装置１０は、ｉ個のｍ−ｓビットの入力値ｐ［１］，．．．，ｐ［ｉ］に対して、圧縮関数演算装置に、ｎビット固定値ＩＶ１、第１メッセージｐ［１］、１のｓビット表現値を入力し、その出力ｃ［１］を得る。次に、圧縮関数演算装置に、ｎビット値ｃ［１］、第２メッセージｐ［２］、２のｓビット表現値を入力し、その出力ｃ［２］を得る。この処理を、第ｉメッセージまで同様に行い、その出力値ｃ［ｉ］を得る。ｆｉｘｅｄ  ｐｏｉｎｔを持たないｎビット上の任意の置換関数πを用いて、ｃ＝π（ｃ［ｉ］）を計算する。圧縮関数演算装置に、ｎビット値ｃ、ｓｕｍ＝ｐ［１］  ｘｏｒ  ．．．  ｘｏｒ  ｐ［ｉ］  ｘｏｒ  ｙ、ｉ＋１のｓビットの表現値を入力し、その出力ｃ［ｉ＋１］を得る。ｃ［ｉ＋１］を出力することを特徴とする。ここで、ｙはｍ−ｓビット固定値である。
【０１８９】
また、ハッシュ値演算装置１０は、任意長の値Ｍから、任意長の値を入力とし、ｍ−ｓビットの値を出力する任意のパディング処理装置を用いて、ｍ−ｓビットの倍数となるメッセージＭ’を生成する。分割処理装置を用いてＭ’をｉ個のｍ−ｓビットの値ｐ［１］，．．．，ｐ［ｉ］に分割することを特徴とする。
【０１９０】
さらに、ハッシュ値演算装置１０は、パディング処理装置を、Ｍ｜｜１｜｜０．．．０｜｜＜Ｍ＞とし、ｓ＝５６とすることを特徴とする。但し、＜Ｍ＞はＭのビット長を６４ビットで表したものである。
【０１９１】
また、さらに、ハッシュ値演算装置１０は、パディング処理装置を、Ｍ｜｜１｜｜０．．．０とし、ｓ＝５６とすることを特徴とする。
【０１９２】
また、ハッシュ値演算装置１０は、圧縮関数演算装置として、ＳＨＡ−２５６の圧縮関数演算装置を用いたことを特徴とする。
【０１９３】
すなわち、以上の実施の形態に係るハッシュ値演算装置１０は、ＥＭＤ構造、ＭＤＰ構造、圧縮関数に固定値を入力する操作、圧縮関数に圧縮関数番号を入力する操作、メッセージの排他的論理輪値を圧縮関数の入力とする操作を利用してハッシュ関数を構成する。これにより、一方向性が破られた圧縮関数または準一方向性が破られた圧縮関数から、ランダムオラクルと強識別不可能性を満たす、効率的なハッシュ関数を構成する。
【０１９４】
なお、以上の実施の形態に係るハッシュ値演算装置１０は、暗号処理（署名処理を含む）を行う暗号処理装置等において用いられるハッシュ値を計算するための装置である。
【０１９５】
次に、実施の形態におけるハッシュ値演算装置１０のハードウェア構成について説明する。
図４３は、ハッシュ値演算装置１０のハードウェア構成の一例を示す図である。
図４３に示すように、ハッシュ値演算装置１０は、プログラムを実行するＣＰＵ９１１（Ｃｅｎｔｒａｌ・Ｐｒｏｃｅｓｓｉｎｇ・Ｕｎｉｔ、中央処理装置、処理装置、演算装置、演算回路、マイクロプロセッサ、マイクロコンピュータ、プロセッサともいう）を備えている。ＣＰＵ９１１は、バス９１２を介してＲＯＭ９１３、ＲＡＭ９１４、ＬＣＤ９０１（Ｌｉｑｕｉｄ  Ｃｒｙｓｔａｌ  Ｄｉｓｐｌａｙ）、キーボード９０２（Ｋ／Ｂ）、通信ボード９１５、磁気ディスク装置９２０と接続され、これらのハードウェアデバイスを制御する。磁気ディスク装置９２０（固定ディスク装置）の代わりに、光ディスク装置、メモリカード読み書き装置などの記憶装置でもよい。磁気ディスク装置９２０は、所定の固定ディスクインタフェースを介して接続される。
【０１９６】
ＲＯＭ９１３、磁気ディスク装置９２０は、不揮発性メモリの一例である。ＲＡＭ９１４は、揮発性メモリの一例である。ＲＯＭ９１３とＲＡＭ９１４と磁気ディスク装置９２０とは、記憶装置の一例である。また、キーボード９０２、通信ボード９１５は、入力装置の一例である。また、通信ボード９１５は、通信装置（ネットワークインタフェース）の一例である。さらに、ＬＣＤ９０１は、表示装置の一例である。
【０１９７】
磁気ディスク装置９２０又はＲＯＭ９１３などには、オペレーティングシステム９２１（ＯＳ）、ウィンドウシステム９２２、プログラム群９２３、ファイル群９２４が記憶されている。プログラム群９２３のプログラムは、ＣＰＵ９１１、オペレーティングシステム９２１、ウィンドウシステム９２２により実行される。
【０１９８】
プログラム群９２３には、上記の説明において「既定長値入力部１１」、「固定値付加部１２」、「圧縮関数計算部１３」、「出力部１４」、「任意長値入力部１５」、「パディング部１６」、「分割部１７」、「排他的論理和計算部１８」、「置換関数計算部１９」等として説明した機能を実行するソフトウェアやプログラムやその他のプログラムが記憶されている。プログラムは、ＣＰＵ９１１により読み出され実行される。
ファイル群９２４には、上記の説明において固定値や途中計算結果等の情報やデータや信号値や変数値やパラメータが、「ファイル」や「データベース」の各項目として記憶される。「ファイル」や「データベース」は、ディスクやメモリなどの記録媒体に記憶される。ディスクやメモリなどの記憶媒体に記憶された情報やデータや信号値や変数値やパラメータは、読み書き回路を介してＣＰＵ９１１によりメインメモリやキャッシュメモリに読み出され、抽出・検索・参照・比較・演算・計算・処理・出力・印刷・表示などのＣＰＵ９１１の動作に用いられる。抽出・検索・参照・比較・演算・計算・処理・出力・印刷・表示のＣＰＵ９１１の動作の間、情報やデータや信号値や変数値やパラメータは、メインメモリやキャッシュメモリやバッファメモリに一時的に記憶される。
【０１９９】
また、上記の説明におけるフローチャートの矢印の部分は主としてデータや信号の入出力を示し、データや信号値は、ＲＡＭ９１４のメモリ、その他光ディスク等の記録媒体やＩＣチップに記録される。また、データや信号は、バス９１２や信号線やケーブルその他の伝送媒体や電波によりオンライン伝送される。
また、上記の説明において「〜部」として説明するものは、「〜回路」、「〜装置」、「〜機器」、「〜手段」、「〜機能」であってもよく、また、「〜ステップ」、「〜手順」、「〜処理」であってもよい。また、「〜装置」として説明するものは、「〜回路」、「〜装置」、「〜機器」、「〜手段」、「〜機能」であってもよく、また、「〜ステップ」、「〜手順」、「〜処理」であってもよい。さらに、「〜処理」として説明するものは「〜ステップ」であっても構わない。すなわち、「〜部」として説明するものは、ＲＯＭ９１３に記憶されたファームウェアで実現されていても構わない。或いは、ソフトウェアのみ、或いは、素子・デバイス・基板・配線などのハードウェアのみ、或いは、ソフトウェアとハードウェアとの組み合わせ、さらには、ファームウェアとの組み合わせで実施されても構わない。ファームウェアとソフトウェアは、プログラムとして、ＲＯＭ９１３等の記録媒体に記憶される。プログラムはＣＰＵ９１１により読み出され、ＣＰＵ９１１により実行される。すなわち、プログラムは、上記で述べた「〜部」としてコンピュータ等を機能させるものである。あるいは、上記で述べた「〜部」の手順や方法をコンピュータ等に実行させるものである。
【符号の説明】
【０２００】
１０  ハッシュ値演算装置、１１  既定長値入力部、１２  固定値付加部、１３  圧縮関数計算部、１４  出力部、１５  任意長値入力部、１６  パディング部、１７  分割部、１８  排他的論理和計算部、１９  置換関数計算部。
【図１】
2010276629.tif 000003
【図２】
2010276629.tif 000004
【図３】
2010276629.tif 000005
【図４】
2010276629.tif 000006
【図５】
2010276629.tif 000007
【図６】
2010276629.tif 000008
【図７】
2010276629.tif 000009
【図８】
2010276629.tif 000010
【図９】
2010276629.tif 000011
【図１０】
2010276629.tif 000012
【図１１】
2010276629.tif 000013
【図１２】
2010276629.tif 000014
【図１３】
2010276629.tif 000015
【図１４】
2010276629.tif 000016
【図１５】
2010276629.tif 000017
【図１６】
2010276629.tif 000018
【図１７】
2010276629.tif 000019
【図１８】
2010276629.tif 000020
【図１９】
2010276629.tif 000021
【図２０】
2010276629.tif 000022
【図２１】
2010276629.tif 000023
【図２２】
2010276629.tif 000024
【図２３】
2010276629.tif 000025
【図２４】
2010276629.tif 000026
【図２５】
2010276629.tif 000027
【図２６】
2010276629.tif 000028
【図２７】
2010276629.tif 000029
【図２８】
2010276629.tif 000030
【図２９】
2010276629.tif 000031
【図３０】
2010276629.tif 000032
【図３１】
2010276629.tif 000033
【図３２】
2010276629.tif 000034
【図３３】
2010276629.tif 000035
【図３４】
2010276629.tif 000036
【図３５】
2010276629.tif 000037
【図３６】
2010276629.tif 000038
【図３７】
2010276629.tif 000039
【図３８】
2010276629.tif 000040
【図３９】
2010276629.tif 000041
【図４０】
2010276629.tif 000042
【図４１】
2010276629.tif 000043
【図４２】
2010276629.tif 000044
【図４３】
2010276629.tif 000045