(57)【要約】【課題】  ＩＣカードなどの計算能力の低い装置を含むシステムにおいて有効な、効率性が高くかつ安全なディジタル署名方法を提供する。【解決手段】  ディジタル署名を構成する落とし戸付き一方向性関数には、ｐを、３を法として２と合同、ｑを、９を法として４または７と合同な素数とするときＮ＝ｐ２ｑの形の合成数を法とする３乗関数を用いる。また署名生成において必要になる上記３乗関数の逆像計算には、中間値を利用しながらｐやｑを法とした逆元演算を行わずに逆像計算を行う方法を用いる。【選択図】図３
2005167525.tif 000002
【特許請求の範囲】
【請求項１】
電子化されたデータに署名生成装置が署名をするディジタル署名方法において、
前記署名生成装置は、
ｐを、９を法として２または５または８と合同な素数とし、
ｑを、９を法として４または７と合同な素数とし、
Ｎ＝ｐ２ｑとするとき、
署名生成時にＮを法とした３乗剰余関数の逆像計算を用い、
署名検証時にＮを法とした３乗剰余関数の順像計算を用いる
ことを特徴とするディジタル署名方法。
【請求項２】
請求項１に記載のディジタル署名方法において、
前記素数ｐ、前記素数ｑを署名生成鍵とし、Ｎ、圧縮関数Ｈ、ｑを法とした３乗非剰余数ａを署名検証鍵とするものであって、
前記署名生成装置は、
電子化されたデータＭの圧縮関数値Ｈ（Ｍ）を計算し、
ｗ＝Ｈ（Ｍ）とするとき、ｗ、ａ＊ｗ、ａ２＊ｗのうちｑを法とした３乗剰余であるものをｙとし、
ｙの、Ｎを法とした３乗根ｘを計算し、
ｘをデータＭに対する署名とする
ことを特徴とするディジタル署名方法。
【請求項３】
請求項２に記載のディジタル署名方法を用いて生成した、ディジタル署名の検証方法であって、
前記署名検証装置は、
データＭから圧縮関数値Ｈ（Ｍ）を計算し、
ｗ＝Ｈ（Ｍ）とするとき、Ｎを法としてｙ’＝ｘ３を計算し、
ｙ’がｗ、ａ＊ｗ、ａ２＊ｗのうちいずれか一つと一致するとき、ｘをＭに対する正当な署名として認証し、
一致しないとき、ｘをＭに対する正当でない署名とする
ことを特徴とするディジタル署名の検証方法。
【請求項４】
請求項１に記載のディジタル署名方法において、
素数ｐ、素数ｑを署名生成鍵とし、Ｎ、圧縮関数ＨとＧ、ｑを法とした３乗非剰余数ａを署名検証鍵とするものであって、
前記署名生成装置は、
電子化されたデータＭの圧縮関数値ｓ＝Ｈ（Ｍ）と圧縮関数値ｔ＝Ｇ（ｓ）を計算し、
連結データｗ＝ｓ｜｜ｔに対し、
ｗ、ａ＊ｗ、ａ２＊ｗのうちｑを法とした３乗剰余であるものをｙとし、
ｙのＮを法とした３乗根ｘを計算し、
ｘをデータＭに対する署名とする
ことを特徴とするディジタル署名方法。
【請求項５】
請求項４に記載のディジタル署名方法を用いて生成した、ディジタル署名の検証方法であって、
前記署名検証装置は、
データＭから圧縮関数値ｓ’＝Ｈ（Ｍ）と圧縮関数値ｔ’＝Ｇ（ｓ’）とを計算し、
連結データｗ’＝ｓ’｜｜ｔ’を計算し、
Ｎを法としてｙ’＝ｘ３を計算し、
ｙ’がｗ’、ａ＊ｗ’、ａ２＊ｗ’のうちいずれか一つと一致するとき、ｘをＭに対する正当な署名として認証し、
一致しないとき、ｘをＭに対する正当でない署名とする
ことを特徴とするディジタル署名の検証方法。
【請求項６】
請求項１に記載のディジタル署名方法において、
素数ｐ、素数ｑを署名生成鍵とし、Ｎ、圧縮関数ＨとＧであって、ＨとＧの出力長の和がＮの長さを等しいもの、およびｑを法とした３乗非剰余数ａを署名検証鍵とするものであって、
前記署名生成装置は、
電子化されたビット長がＧの出力長と同じ長さのデータＭの圧縮関数値ｓ＝Ｈ（Ｍ）を計算し、
圧縮関数値Ｇ（ｓ）とＭとのビットごとの排他的論理和をｔとし、
それらの連結データｗ＝ｓ｜｜ｔに対し、
ｗ、ａ＊ｗ、ａ２＊ｗのうちｑを法とした３乗剰余であるものをｙとし、
ｙのＮを法とした３乗根ｘを計算し、
ｘをデータＭに対する署名とする
ことを特徴とするディジタル署名方法。
【請求項７】
請求項６に記載のディジタル署名方法を用いて生成した、ディジタル署名の検証方法であって、
前記署名検証装置は、
Ｎを法としてｙ’＝ｘ３を計算し、
ｉ＝１、２、３に対し、
Ｎを法としてｙｉ＝ａｉ＊ｙ’を計算し、
ｙｉを、上位からＨの出力長と同じ長さのビット列ｓｉと残りのビット列ｔｉとに分割し、
ｔｉと圧縮関数値Ｇ（ｓｉ）とのビットごとの排他的論理和Ｍｉを計算し、
ｉ＝１、２、３のうちいずれかにおいてｓｉ＝Ｈ（Ｍｉ）が成り立つとき、ｉに対するＭｉを回復されたデータとし、
ｘはＭｉに対する正当な署名として認証し、
成り立たないとき、正当でない署名とする
ことを特徴とするディジタル署名の検証方法。
【請求項８】
請求項２に記載のディジタル署名方法において、
前記署名生成装置は、
前記ｗに対し、
ｑが、９を法として４と合同ならばζ＝ａ（ｑ−１）／３ ｍｏｄ ｑ、Ｂ＝（２＊ｑ−８）／９とし、
ｑが、９を法として７と合同ならばζ＝ａ（２＊（ｑ−１））／３ ｍｏｄ ｑ、Ｂ＝（ｑ−７）／９とし、
ｂ＝ａＢ＋１ ｍｏｄ ｑ、ｚ＝１／ｐ ｍｏｄ ｑを計算し、
ｖ＝ｗ ｍｏｄ ｑ、ｓ＝ｖＢ ｍｏｄ ｑ、ｈ＝ｓ＊ｖ ｍｏｄ ｑ、α＝ｓ＊ｈ２ ｍｏｄ ｑを計算し、
αが、ｑを法として１と異なるならばｈ＝ｂ＊ｈ ｍｏｄ ｑ、ｗ＝ｗ＊ａ ｍｏｄ Ｎとし、
αが、ｑを法としてζと異なるならばｈ＝ｂ＊ｈ ｍｏｄ ｑ、ｗ＝ａ＊ｗ ｍｏｄ Ｎを計算し、
Ｃ＝（２＊ｐ−４）／３とし、
ｕ＝ｗ ｍｏｄ ｐ、ｄ＝ｕＣ ｍｏｄ ｐ、ｇ＝ｕ＊ｄ ｍｏｄ ｐ、η＝γ＊ｄ ｍｏｄ ｐ、を計算し、
ｅ＝ｇ＋ｐ＊（（ｈ−ｇ）＊ｚ ｍｏｄ ｑ）を計算し、
ｘ＝ｅ＋η＊（ｗ−ｅ３）ｍｏｄ Ｎとする
ことを特徴とするディジタル署名方法。
【請求項９】
請求項４に記載のディジタル署名方法において、
前記署名生成装置は、
請求項８に記載の方法により、ｗに対しｘを計算する
ことを特徴とするディジタル署名方法。
【請求項１０】
請求項７に記載のディジタル署名方法において、
前記署名生成装置は、
請求項８に記載の方法により、ｗに対しｘを計算する
ことを特徴とするディジタル署名方法。
【請求項１１】
請求項１に記載のディジタル署名方法において、
素数ｐ、素数ｑを署名生成鍵とし、Ｎ、圧縮関数ＨとＧ、ｑを法とした３乗非剰余数ａ、及び、Ｎを法とした可逆元と乱数を入力として持ち、その出力と入力の可逆元とのビットごとの排他的論理和がＮを法とした３乗剰余元となるような関数ψを署名検証鍵とするものであって、
前記署名生成装置は、
乱数ｒを生成し、
データＭの圧縮関数値Ｈ（Ｍ）を計算し、
ｒとＨ（Ｍ）から関数値ｒ’＝ψ（ｒ、Ｈ（Ｍ））を計算し、
連結ｙ＝Ｈ（Ｍ）｜｜ｒ’のＮを法とした、３乗根ｘを計算し、
ｘをデータＭに対する署名する
ことを特徴とするディジタル署名方法。
【請求項１２】
請求項１１に記載のディジタル署名方法を用いて生成した、ディジタル署名の検証方法であって、
前記署名検証装置は、
Ｍの圧縮関数値Ｈ（Ｍ）を計算し、
Ｎを法としてｙ’＝ｘ３を計算し、
ｙを、上位からＨの出力長と同じ長さのビット列ｗ’と残りｒ’とに分割し、
ｗ’と圧縮関数値Ｈ（Ｍ）とが一致するとき、ｘはＭに対する正当な署名として認証し、
一致しないとき、正当でない署名とする
ことを特徴とするディジタル署名の検証方法。
【請求項１３】
請求項１１に記載のディジタル署名方法において、
署名生成装置は、
前記圧縮関数値Ｈ（Ｍ）に対し、
ｑが、９を法として４と合同ならばζ＝ａ（ｑ−１）／３ ｍｏｄ ｑ、Ｂ＝（２＊ｑ−８）／９とし、
ｑが、９を法として７と合同ならばζ＝ａ（２＊（ｑ−１））／３ ｍｏｄ ｑ、Ｂ＝（ｑ−７）／９とし、
ｂ＝ａＢ＋１ ｍｏｄ ｑ、ｚ＝１／ｐ ｍｏｄ ｑを計算し、
Ｈ（Ｍ）とｋ個の０ビットを連結したものを法ｑで計算したものをＺ＝（Ｈ（Ｍ）｜｜０ｋ） ｍｏｄ ｑとし、
Ｈ（Ｍ）とｒの連結をｗ＝Ｈ（Ｍ）｜｜ｒとし、
ｖ＝ｗ ｍｏｄ ｑ、ｓ＝ｖＢ ｍｏｄ ｑ、ｈ＝ｓ＊ｖ ｍｏｄ ｑ、α＝ｓ＊ｈ２ ｍｏｄ ｑを計算し、
αがｑを法として１と異なるならｈ＝Ｂ＊ｈ ｍｏｄ ｑ、ｗ＝Ｈ（Ｍ）｜｜（ｈ３−Ｚ ｍｏｄ ｑ）とし、
さらにαがｑを法としてζと異なるならばｈ＝ｂ＊ｈ ｍｏｄ ｑ、ｗ＝Ｈ（Ｍ）｜｜（ｈ３−Ｚ ｍｏｄ ｑ）を計算し、
Ｃ＝（２＊ｐ−４）／３とし、
ｕ＝ｗ ｍｏｄ ｐ、ｄ＝ｕＣ ｍｏｄ ｐ、ｇ＝ｕ＊ｄ ｍｏｄ ｐ、η＝γ＊ｄ ｍｏｄ ｐ、を計算し、
さらに、ｅ＝ｇ＋ｐ＊（（ｈ−ｇ）＊ｚ ｍｏｄ ｑ）を計算し、
ｘ＝ｅ＋η＊（ｗ−ｅ３）ｍｏｄ Ｎとする
ことを特徴とするディジタル署名方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ディジタル署名方法及びディジタル署名を用いた認証方法に関する。
【背景技術】
【０００２】
ディジタル署名は電子的なデータに対する印鑑の役割を持つ。署名対象の電子的なデータに対し、署名者Ａは秘密の署名生成鍵を用いて署名データを生成し、もとのデータとともに署名検証者Ｂに送る。署名検証者は公開さている署名検証鍵を用いてそのデータが確かに署名者Ａにより作成されたかどうかを検証する。従って、署名データは署名生成鍵を持つものしか生成できず、また正当に生成された署名データは検証時に受け入れられ、そうでないものは受け入れられないような仕組みになっていなければならない。
【０００３】
このような署名方法は公開鍵暗号技術を用いて１９７０年代後半に初めて構築されて以来、多くの方法が提案されてきている。また、ディジタル署名に対する安全性の概念整備や、効率性向上の技術などが数多く研究されている。
【０００４】
安全性の概念に対しては、１９９０年代に安全性証明理論が整備され、素因数分解問題などの数論問題の困難性を仮定して安全性が証明可能ないわゆる安全性証明可能方法がいくつか提案された。今なお安全性概念整備は研究されているが、実用署名方法として満たすべき安全性の概念はある程度充実し、定着していく方向になっている。一般的となっている満たすべき安全性レベルは、「適応的選択文書攻撃に対して存在的偽造不可」というものである。これらを満たしている方法として代表的なものとしては非特許文献１記載のＲＳＡ−ＰＳＳがある。
【０００５】
安全性証明理論では、安全性の根拠とする数論問題の困難性を仮定する。例えば素因数分解問題の困難性や離散対数問題の困難性などである。これらの数論問題のうち、暗号の安全性の根拠とするにふさわしいものの代表は素因数分解問題である。素因数分解問題はその研究の歴史がもっとも長く、数多くの解法が研究されて来ているが、それらの解法にも耐えうるようパラメータ長などを設定することにより完全に安全な数論問題と考えることができる。素因数分解問題を安全性の根拠におく署名方法として非特許文献１記載のＲａｂｉｎ−ＰＳＳ方法や非特許文献２記載のＲａｂｉｎ署名方法などが知られている。
【０００６】
これに対し、上記ＲＳＡ−ＰＳＳは安全性の根拠とする問題が厳密には素因数分解問題ではなく、ＲＳＡ問題と呼ばれる問題となっている。素因数分解問題が解ければＲＳＡ問題を解くことが出来るが、逆については証明されていない。すなわちＲＳＡ問題の安全性は素因数分解問題以下ということができ、より高い安全性を求める暗号技術においては、より信頼性の高い、素因数分解問題などを安全性の根拠におく方法が望まれている。  一方、効率性の問題は、ディジタル署名のみならず、公開鍵暗号技術全体が抱える問題である。公開鍵暗号技術の構築のためには、ある種の数学的構造を必要とすることから、その処理には数学的関数の計算を避けることが出来ず、それが効率性を悪化させる大きな原因となっている。上記ＲＳＡ−ＰＳＳ方法では、署名検証時にある程度大きな数を法としたべき乗計算が複数回必要で、種々の高速化方法が提案されているものの、ＩＣカードなどの計算能力の低い装置ではなお処理効率のボトルネックになっている。暗号や署名の処理に時間がかかることは本来実行すべき種々のアプリケーションの実行時間へ大きな悪影響を与え、全体の処理時間の制約から、場合によっては暗号処理部分を使用しないことも起こりえる。当然ながら安全面で深刻な損害を与えかねない事態となってしまうので、このようなことを避けるために効率性のよい方法の開発は極めて重要な問題となっている。
【０００７】
【非特許文献１】Ｍ．Ｂｅｌｌａｒｅ ａｎｄ Ｐ．Ｒｏｇａｗａｙ， Ｏｐｔｉｍａｌ Ａｓｙｍｍｅｔｒｉｃ Ｅｎｃｒｙｐｔｉｏｎ−Ｈｏｗ ｔｏ Ｅｎｃｒｙｐｔ ｗｉｔｈ ＲＳＡ， Ｐｒｏｃ．ｏｆ Ｅｕｒｏｃｒｙｐｔ’９４，ＬＮＣＳ９５０，Ｓｐｒｉｎｇｅｒ Ｖｅｒｌａｇ， ｐｐ．９２−１１１（１９９４）．
【０００８】
【非特許文献２】Ｍ．Ｒａｂｉｎ， Ｄｉｇｉｔａｌ Ｓｉｇｎａｔｕｒｅｓ ａｎｄ Ｐｕｂｌｉｃ−Ｋｅｙ Ｅｎｃｒｙｐｔｉｏｎｓ ａｓ Ｉｎｔｒａｃｔａｂｌｅ ａｓ Ｆａｃｔｏｒｉｚａｔｉｏｎ，ＭＩＴ，Ｔｅｃｈｎｉｃａｌ Ｒｅｐｏｒｔ， ＭＩＴ／ＬＣＳ／ＴＲ−２１２（１９７９）．
【発明の開示】
【発明が解決しようとする課題】
【０００９】
上述の通り、より信頼性の高い、素因数分解問題などを安全性の根拠におく方法が望まれているが、素因数分解問題を安全性の根拠におく署名方法である上述のＲａｂｉｎ−ＰＳＳ方法Ｒａｂｉｎ署名方法は、ＲＳＡ−ＰＳＳと同様、署名生成時には大きな法でのべき乗剰余算が必要である。さらに、Ｒａｂｉｎ方法の基本となる関数が平方剰余関数で、これは写像として４対１、すなわち同じ像に写像される入力は相異なるものが４つ存在するような関数となっており、このことが、署名生成時の効率性を極端に落とす理由になっている。Ｒａｂｉｎ−ＰＳＳではランダムな値を生成し、ある種のパディングを施した後、それが平方剰余関数の値域に入っているか否かをチェックし、入っていなかったら最初の処理からやり直さなければならない。これは効率性には望ましくなく、特にＩＣカードでは実用に耐えられないほどの悪影響を持つ。
【００１０】
このように現状では、信頼性の高い数論問題である素因数分解問題を安全性の根拠において安全性証明可能であるディジタル署名方法の中で、計算能力の低い装置で実用的な効率性を持つ方法が存在しておらず、これらを満たすディジタル署名方法が望まれている。
【課題を解決するための手段】
【００１１】
素因数分解問題を安全性の根拠に置くためには、ディジタル署名を構成する落とし戸付き一方向性関数に写像として合成数を法とするべき乗関数であって、ｎ対１、ｎ＞１であるものを用いる必要がある。このとき、効率性を向上させるには、ｎはなるべく小さいほうが望ましい（Ｒａｂｉｎ署名の場合はｎ＝４）。数学的にｎ＞２であることが示されており、よって本発明ではｎ＝３となるものを選択する。また、署名生成時に必要なべき乗計算をより効率的に行う必要があるため、一方向性関数の法としてはｐ２ｑ（ｐ、ｑは素数）の形の合成数を用いる。ｐを、３を法として２と合同、ｑを、９を法として４または７と合同な素数とするときＮ＝ｐ２ｑの形の合成数を法とする３乗関数を用いれば上記を満たす一方向性関数を構成することができる。
【００１２】
さらに、署名生成時においてはこの３乗関数の逆像計算が必要であるが、ここで中間値を利用しながらｐやｑを法とした逆元演算を行わずに逆像計算を行う方法を用いる。これらの方法により、長さの比較的短いｐ、ｑを法としたべき乗剰余算をそれぞれ一回ずつ行う程度の計算量で逆像計算が可能になる。  具体的なディジタル署名方法の実現方法の１つを以下に示す。
【００１３】
鍵生成
圧縮関数Ｈを選択し、固定する。９を法として２または５または８と合同な素数ｐ及び９を法として４または７と合同な素数ｑをランダムに生成し、Ｎ＝ｐ２ｑとする。ｑを法とした三乗非剰余数ａを任意に一つ固定し、（ｐ、ｑ）を署名生成鍵、（Ｎ、Ｈ、ａ）を署名検証鍵とする。ここで圧縮関数は暗号学的ハッシュ関数を意味し、一方向性と衝突困難性とを持つものをいう。
【００１４】
署名生成
電子化されたデータＭの圧縮関数値Ｈ（Ｍ）に対しＨ（Ｍ）、ａ＊Ｈ（Ｍ）、ａ２＊Ｈ（Ｍ）のうちｑを法とした三乗剰余であるものをｙとする。
ｙのＮを法とした三乗根ｘを計算し、ｘをデータＭに対する署名とする。
【００１５】
署名検証
データＭから圧縮関数値Ｈ（Ｍ）を計算し、Ｎを法としてｙ’＝ｘ３を計算し、ｙ’がＨ（Ｍ）、ａ＊Ｈ（Ｍ）、ａ２＊Ｈ（Ｍ）のうちいずれか一つと一致するとき、ｘをＭに対する正当な署名として認証し、一致しないとき、正当でない署名とする。なお、記号＊は乗算を表す。
【００１６】
この方法では法Ｎの素因数分解問題の困難性を前提に、適応的選択文書攻撃に対し存在的偽造不可であることが証明され、実用面で必要な安全性のレベルを達成している。
【発明の効果】
【００１７】
本発明により、最も強力な攻撃法である適応的選択文書攻撃に対して安全であることが保証されたディジタル署名を効率的に生成、検証することが可能となる。効率性が高いことにより、計算能力の低い装置であっても高速な署名処理が可能である。
【発明を実施するための最良の形態】
【００１８】
以下、図面を用いて、本発明の実施例について説明する。
【実施例１】
【００１９】
図１はネットワーク１００１によって接続されたコンピュータＡ１００２、コンピュータＢ１００３を含む、コンピュータＡ１００２からコンピュータＢ１００３への通信を目的としたシステム構成を示すものである。
【００２０】
コンピュータＡ１００２は内部に演算装置（以下ＣＰＵという）１００４、記憶装置（揮発性、不揮発性を問わない。以下メモリという。）１００５、ネットワークインターフェース１００６を装備しており、外部にはコンピュータＡ１００２をユーザが操作するためのディスプレイ１００７とキーボード１００８が接続されている。メモリ１００５には署名生成プログラム（以下プログラムをＰＲＯＧともいう）ＰＲＯＧ１（１００９）、署名生成のための秘密鍵Ｓ１０１０、署名対象のデータＭ１０１１が保存されている。
【００２１】
コンピュータＢ１００３は内部にＣＰＵ１０１２、メモリ１０１３、ネットワークインターフェース１０１４、を装備しており、外部にはコンピュータＢ１００３をユーザが操作するためのディスプレイ１０１５とキーボード１０１６が接続されている。メモリ１０１３には署名検証プログラムＰＲＯＧ２（１０１７）と、署名検証用鍵Ｋ１０１８が保存されている。
【００２２】
コンピュータＡ１００２は署名生成プログラムＰＲＯＧ１（１００９）を実行し、データＭ１０１１に対する署名データ１０１９を作成し、ネットワークインターフェース１００６を通してネットワーク１００１へ送信する。
【００２３】
コンピュータＢ１００３はネットワークインターフェース１０１４を通して受信したあと、署名検証プログラムＰＲＯＧ２（１０１７）を実行し、検証結果をメモリ１０１３に保存する。
【００２４】
以下の各実施例で説明するプログラムは、互いのコンピュータまたは他のコンピュータからネットワーク１００１上の伝送媒体である伝送信号により、またはＣＤ−ＲＯＭ、フレキシブルディスクなどの可搬型記憶媒体を介してメモリにデータを導入することができる。各コンピュータは、各コンピュータのオペレーションシステム（図示していない）の元で動作するように構成することも可能である。
【００２５】
署名生成プログラムＰＲＯＧ１（１００９）はコンピュータＡ１００２において、メモリ１００５から読み出されて、ＣＰＵ１００４により実行され、コンピュータＡ１００２上に署名生成処理部を実現する。署名生成プログラムＰＲＯＧ１（１００９）は、署名生成鍵Ｓ１０１０、データＭ１０１１に対し、署名データ１０１９を出力する。
【００２６】
署名検証プログラムＰＲＯＧ２（１０１７）はコンピュータＢ１００３において、メモリ１０１３から読み出されＣＰＵ１０１２により実行され、コンピュータＢ１００３上に署名検証処理部を実現する。署名プログラムＰＲＯＧ２（１０１７）は署名検証鍵Ｋ１０１８、署名データ１０１９から検証結果を出力する。
【００２７】
署名生成プログラムＰＲＯＧ１（１００９）と署名検証プログラムＰＲＯＧ２（１０１７）で用いられる一方向性関数ｆは、ｐを、９を法として２または５または８と合同な素数、ｑを、９を法として４または７と合同な素数とし、Ｎ＝ｐ２ｑとするとき、Ｎを法とした３乗剰余関数であるとする。
【００２８】
署名生成プログラムＰＲＯＧ１（１００９）の処理の流れを図２を用いて説明する。
ステップ２１０１：署名生成鍵と署名対象のデータを入力する。
ステップ２１０２：署名生成のための前処理を行う。データの圧縮値の計算などを含む。
ステップ２１０３：３乗剰余関数ｆの逆像計算を行う。
ステップ２１０４：署名生成のための後処理を行う。
ステップ２１０５：署名データを出力する。
【００２９】
署名検証プログラムＰＲＯＧ２（１０１７）の処理の流れを図３を用いて説明する。
ステップ２２０１：署名検証鍵と署名対象のデータを入力する。
ステップ２２０２：署名検証のための前処理を行う。データの圧縮値の計算などを含む。
ステップ２２０３：３乗剰余関数ｆの順像計算を行う。
ステップ２２０４：署名検証のための後処理を行う。
ステップ２２０５：合否を出力する。
【００３０】
署名生成鍵、署名検証鍵の生成手順を図４を用いて説明する。
ステップ３１０１：素数生成。９を法として２または５または８と合同な素数ｐ、及び９を法として４または７と合同な、ｐと異なる素数ｑをランダムに生成する。
ステップ３１０２：合成数計算。Ｎ＝ｐ２ｑを計算する。
ステップ３１０３：ｑを法として３乗剰余でない数ａを選択する。
ステップ３１０４：出力長がＮの長さと等しい圧縮関数Ｈを選択する。
ステップ３１０５：鍵の出力。署名検証鍵として（Ｎ、Ｈ、ａ）を、署名生成鍵として（ｐ、ｑ）を出力する。
【００３１】
署名生成鍵、署名検証鍵の生成は通信を行う前に実施され、各装置のメモリに記録されているものとする。各パラメータの長さも装置間で合意されているものとする。
本実施例では秘密にすべき素数ｐ、ｑのみを署名生成鍵として説明したが、署名検証鍵は公開することから、署名検証鍵も署名生成時の鍵の一部として用いることとし、署名生成時の入力などに単に署名生成鍵と記載していても、署名検証鍵も入力されているものとする。
【００３２】
署名生成プログラムＰＲＯＧ１（１００９）におけるステップ２１０２：署名生成のための前処理、ステップ２１０３：３乗剰余関数ｆの逆像計算、およびステップ２１０４：署名生成のための後処理について、図５を用いて説明する。
ステップ３２０１：署名対象のデータＭと、署名生成鍵を入力する。
ステップ３２０２：圧縮関数ＨにデータＭを入力し、圧縮値ｗ＝Ｈ（Ｍ）を計算する。
ステップ３２０３：ｗ、ａ＊ｗ ｍｏｄ Ｎ、ａ２＊ｗ ｍｏｄ Ｎのうち、Ｎを法として３乗剰余であるものを探し、それをｙとおく。記号ｍｏｄは剰余を表す。すなわちＡ ｍｏｄ Ｎは、ＡをＮで割った余りを表す。
ステップ３２０４：署名値の計算。Ｎを法としたｙの３乗根を計算し、それをｘとおく。
ステップ３２０５：署名対象のデータＭと、署名値ｘとの連結を署名データＷとする。
ステップ３２０６：署名データとしてＷを出力する。
【００３３】
ここで、ステップ３２０２、３２０３がステップ２１０２に対応し、ステップ３２０４がステップ２１０３に対応し、ステップ３２０５がステップ２１０４に対応している。
【００３４】
ステップ３２０５において、署名データＷは、Ｍとｘとの連結として説明したが、署名データＷは、Ｗから誰もが容易にＭとｘを導くことが出来るならば他の方法で構成されていてもよい。
【００３５】
署名検証プログラムＰＲＯＧ２（１０１７）におけるステップ２２０２：署名検証のための前処理、ステップ２２０３：３乗剰余関数ｆの順像計算、およびステップ２２０４：署名検証のための後処理について、図６を用いて説明する。
ステップ３３０１：署名データＷと署名検証鍵を入力する。
ステップ３３０２：署名データＷからＭとｘを取り出す。署名データがステップ３２０５のように作成されている場合、Ｗの下位から署名値の長さ分を取り出し、ｘとおき、残りをＭとする。
ステップ３３０３：圧縮関数ＨにデータＭを入力し、圧縮値ｗ’＝Ｈ（Ｍ）を計算する。
ステップ３３０４：Ｎを法としてｘ３を計算し、それをｙ’とおく。
ステップ３３０５：Ｎを法としてｙ’＝ｗ’ならばステップ３３０９へ行く。
ステップ３３０６：Ｎを法としてｙ’＝ａ＊ｗ’ならばステップ３３０９へ行く。
ステップ３３０７：Ｎを法としてｙ’＝ａ２＊ｗ’ならばステップ３３０９へ行く。
ステップ３３０８：「不合格」を出力して終了する。
ステップ３３０９：「合格」を出力して終了する。
【００３６】
ここで、ステップ３３０２、３３０３がステップ２２０２に対応し、ステップ３３０４がステップ２２０３に対応し、ステップ３３０５、３３０６、３３０７がステップ２２０４に対応している。
【００３７】
署名生成プログラムの実施におけるステップ３２０３、ステップ３２０４の実施方法を、図７を用いて説明する。
【００３８】
Ｃ＝（２＊ｐ−４）／３を計算する。ｑが９を法として４と合同ならばζ＝ａ（ｑ−１）／３ ｍｏｄ ｑ、Ｂ＝（２＊ｑ−８）／９を計算し、ｑが９を法として７と合同ならばζ＝ａ（２＊（ｑ−１））／３ ｍｏｄ ｑ、Ｂ＝（ｑ−７）／９を計算する。さらに、ｂ＝ａＢ＋１ ｍｏｄ ｑ、ｚ＝１／ｐ ｍｏｄ ｑを計算する。これらの値は事前に計算しておき、署名生成鍵に含めてもよい。
ステップ３４０１：署名生成鍵（署名検証鍵も含む）と上記値ζ、Ｃ、Ｂを入力する。
ステップ３４０２：ｖ＝ｗ ｍｏｄ ｑを計算する。
ステップ３４０３：ｓ＝ｖＢ ｍｏｄ ｑを計算する。
ステップ３４０４：ｈ＝ｓ＊ｖ ｍｏｄ ｑを計算する。
ステップ３４０５：α＝ｓ＊ｈ２ ｍｏｄ ｑを計算する。
ステップ３４０６：αがｑを法として１と等しければステップ３４１０に行く。
ステップ３４０７：ｈ＝ｂ＊ｈ ｍｏｄ ｑを計算し、ｗ＝ａ＊ｗ ｍｏｄ Ｎとおく。
ステップ３４０８：αがｑを法としてζと等しければステップ３４１０に行く。
ステップ３４０９：ｈ＝ｂ＊ｈ ｍｏｄ ｑを計算し、ｗ＝ａ＊ｗ ｍｏｄ Ｎとおく。
ステップ３４１０１２：ｕ＝ｗ ｍｏｄ ｐを計算する。
ステップ３４１１：ｄ＝ｕＣ ｍｏｄ ｐを計算する。
ステップ３４１２：ｇ＝ｕ＊ｄ ｍｏｄ ｐを計算する。
ステップ３４１３：η＝γ＊ｄ ｍｏｄ ｐを計算する。
ステップ３４１４：ｅ＝ｇ＋ｐ＊（（ｈ−ｇ）＊ｚ ｍｏｄ ｑ）を計算する。
ステップ３４１５：ｘ＝ｅ＋η＊（ｗ−ｅ３） ｍｏｄ Ｎを計算する。
ステップ３４１６：ｘを出力する。
【実施例２】
【００３９】
実施例１で図１を用いて説明した通信システムにおいて、次の方法でディジタル署名方法を実施することができる。
【００４０】
まず、署名生成鍵、署名検証鍵の生成手順を図８を用いて説明する。
ステップ４１０１：素数生成。９を法として２または５または８と合同な素数ｐ、及び９を法として４または７と合同な、ｐと異なる素数ｑをランダムに生成する。
ステップ４１０２：合成数計算。Ｎ＝ｐ２ｑを計算する。
ステップ４１０３：ｑを法として３乗剰余でない数ａを選択する。
ステップ４１０４：圧縮関数Ｈと圧縮関数Ｇを選択する。
ステップ４１０５：鍵の出力。署名検証鍵として（Ｎ、Ｈ、Ｇ、ａ）を、署名生成鍵として（ｐ、ｑ）を出力する。
【００４１】
上記圧縮関数Ｈ、Ｇについては、Ｈの出力長とＧの出力長の和がＮの長さと等しくなるように選択する。
【００４２】
署名生成鍵、署名検証鍵の生成は通信を行う前に実施され、各装置のメモリに記録されているものとする。各パラメータの長さも装置間で合意されているものとする。
本実施例では秘密にすべき素数ｐ、ｑのみを署名生成鍵として説明したが、署名検証鍵は公開することから、署名検証鍵も署名生成時の鍵の一部として用いることとし、署名生成時の入力などに単に署名生成鍵と記載していても、署名検証鍵も入力されているものとする。
【００４３】
署名生成プログラムＰＲＯＧ１（１００９）におけるステップ２１０２：署名生成のための前処理、ステップ２１０３：３乗剰余関数ｆの逆像計算、およびステップ２１０４：署名生成のための後処理について、図９を用いて説明する。
ステップ４２０１：署名対象のデータＭと署名生成鍵を入力する。
ステップ４２０２：圧縮関数ＨにデータＭを入力し、圧縮値ｓ＝Ｈ（Ｍ）を計算する。
ステップ４２０３：圧縮関数Ｇにｓを入力し、圧縮値ｔ＝Ｇ（ｓ）を計算する。
ステップ４２０４：ｓとｔの連結をｗとする。
ステップ４２０５：ｗ、ａ＊ｗ ｍｏｄ Ｎ、ａ２＊ｗ ｍｏｄ Ｎのうち、Ｎを法として３乗剰余であるものを探し、それをｙとおく。
ステップ４２０６：署名値の計算。Ｎを法としたｙの３乗根を計算し、それをｘとおく。
ステップ４２０７：署名対象のデータＭと、署名値ｘとの連結を署名データＷとする。
ステップ４２０８：署名データとしてＷを出力する。
【００４４】
ここで、ステップ４２０２、４２０３、４２０４、４２０５がステップ２１０２に対応し、ステップ４２０６がステップ２１０３に対応し、ステップ４２０７がステップ２１０４に対応している。
【００４５】
ステップ４２０７において、署名データＷは、Ｍとｘとの連結として説明したが、署名データＷは、Ｗから誰もが容易にＭとｘを導くことが出来るならば他の方法で構成されていてもよい。
【００４６】
ステップ４２０５とステップ４２０６は図７を用いて説明したステップ３４０１からステップ３４１６を実施することにより実行することができる。
【００４７】
署名検証プログラムＰＲＯＧ２（１０１７）におけるステップ２２０２：署名検証のための前処理、ステップ２２０３：３乗剰余関数ｆの順像計算、およびステップ２２０４：署名検証のための後処理について図１０を用いて説明する。
ステップ４３０１：署名データＷと署名検証鍵を入力する。
ステップ４３０２：署名データＷからＭとｘを取り出す。署名データがステップ４２０７のように作成されている場合、Ｗの下位から署名値の長さ分を取り出し、ｘとおき、残りをＭとする。
ステップ４３０３：圧縮関数ＨにデータＭを入力し、圧縮値ｓ’＝Ｈ（Ｍ）を計算する。
ステップ４３０４：圧縮関数Ｇにデータｓ’を入力し、圧縮値ｔ’＝Ｇ（ｓ’）を計算する。
ステップ４３０５：ｓ’とｔ’の連結をｗ’とする。
ステップ４３０６：Ｎを法としてｘ３を計算し、それをｙ’とおく。
ステップ４３０７：Ｎを法としてｙ’＝ｗ’ならばステップ４３１１へ行く。
ステップ４３０８：Ｎを法としてｙ’＝ａ＊ｗ’ならばステップ４３１１へ行く。
ステップ４３０９：Ｎを法としてｙ’＝ａ２＊ｗ’ならばステップ４３１１へ行く。
ステップ４３１０：「不合格」を出力して終了する。
ステップ４３１１：「合格」を出力して終了する。
【００４８】
ここで、ステップ４３０２、４３０３、４３０４、４３０５がステップ２２０２に対応し、ステップ４３０６がステップ２２０３に対応し、ステップ４３０７、４３０８、４３０９がステップ２２０４に対応している。
【実施例３】
【００４９】
実施例１で図１を用いて説明した通信システムにおいて、次の方法でディジタル署名方法を実施することができる。
【００５０】
署名生成プログラムＰＲＯＧ１（１００９）におけるステップ２１０２：署名生成のための前処理、ステップ２１０３：３乗剰余関数ｆの逆像計算、およびステップ２１０４：署名生成のための後処理について、図１１を用いて説明する。
ただし、署名生成鍵、署名検証鍵は、図８を用いて説明した、ステップ４１０１からステップ４１０５を実施することで生成される。
ステップ５２０１：署名対象のデータＭと署名生成鍵を入力する。
ステップ５２０２：圧縮関数ＨにデータＭを入力し、圧縮値ｓ＝Ｈ（Ｍ）を計算する。
ステップ５２０３：圧縮関数Ｇにｓを入力し、圧縮値Ｇ（ｓ）とＭとの排他的論理和をｗとする。
ステップ５２０４：ｓとｔの連結をｗとする。
ステップ５２０５：ｗ、ａ＊ｗ ｍｏｄ Ｎ、ａ２＊ｗ ｍｏｄ Ｎのうち、Ｎを法として３乗剰余であるものを探し、それをｙとおく。
ステップ５２０６：署名値の計算。Ｎを法としたｙの３乗根を計算し、それをｘとおく。
ステップ５２０７：署名値ｘを署名データＷとする。
ステップ５２０８：署名データとしてＷを出力する。
【００５１】
ここで、ステップ５２０２、５２０３、５２０４、５２０５がステップ２１０２に対応し、ステップ５２０６がステップ２１０３に対応し、ステップ５２０７がステップ２１０４に対応している。
【００５２】
上記説明において、署名対象のデータＭの長さはＧの出力長と等しいとする。一般にはＭの長さはＧの出力長以下ならばよく、短い場合には、適当なパディングを行ってＧの長さと等しくしたものを改めてＭと置けばよい。例えばＭの最下位にビット１を連結し、さらにＧの出力長と等しくなるまでビット０を繰り返し連結すればよい。
【００５３】
署名検証プログラムＰＲＯＧ２（１０１７）におけるステップ２２０２：署名検証のための前処理、ステップ２２０３：３乗剰余関数ｆの順像計算、およびステップ２２０４：署名検証のための後処理について、図１２を用いて説明する。
ステップ５３０１：署名データＷと署名検証鍵を入力する。
ステップ５３０２：Ｎを法としてΑを計算し、それをｙ０’とおく。
ステップ５３０３：Ｎを法としてａ＊ｙ０’を計算し、それをｙ１’とおく。
ステップ５３０４：Ｎを法としてａ＊ｙ１’を計算し、それをｙ２’とおく。
ステップ５３０５：ｉ＝０、１、２に対し、ｙｉ’をｓｉと、ｔｉとに分割する。
ステップ５３０６：ｉ＝０、１、２に対し、圧縮関数Ｇにｓｉを入力し、その出力Ｇ（ｓｉ）とｔｉとの排他的論理和をＭｉとする。
ステップ５３０７：圧縮値Ｈ（ｓ０）とＭ０が異なっているならステップ５３０９に行く。
ステップ５３０８：Ｍ＝Ｍ０とおいて、ステップ５３１４に行く。
ステップ５３０９：圧縮値Ｈ（ｓ１）とＭ１が異なっているならステップ５３１１に行く。
ステップ５３１０：Ｍ＝Ｍ１とおいて、ステップ５３１４に行く。
ステップ５３１１：圧縮値Ｈ（ｓ２）とＭ２が異なっているならステップ５３１３に行く。
ステップ５３１２：Ｍ＝Ｍ２とおいて、ステップ５３１４に行く。
ステップ５３１３：「不合格」を出力して終了する。
ステップ５３１４：「合格」と、Ｍを出力して終了する。
【００５４】
ここで、ステップ５３０２、５３０３、５３０４がステップ１２０３に対応し、ステップ５３０５から５３１２がステップ１２０４に対応している。
【００５５】
本実施例のディジタル署名方法は、メッセージ回復型で、署名データＷから直接は署名対象のデータＭはわからないが、署名検証手順の終了後、合格ならばデータＭも同時に出力される。
【実施例４】
【００５６】
実施例１で図１を用いて説明した通信システムにおいて、次の方法でディジタル署名方法を実施することができる。
【００５７】
署名生成プログラムＰＲＯＧ１（１００９）におけるステップ２１０２：署名生成のための前処理、ステップ２１０３：３乗剰余関数ｆの逆像計算、およびステップ２１０４：署名生成のための後処理について、図１３を用いて説明する。
ただし、署名生成鍵、署名検証鍵は、図４を用いて説明した、ステップ４１０１からステップ４１０５を実施することに加え、圧縮関数Ｈの出力長はＮの長さからｑの長さを引いたものであるとし、関数ψを、Ｎを法とした可逆元と、ｑの長さと同じ長さで、整数値としてｑより小さい乱数を入力とし、その出力と、入力の可逆元とのビットごとの排他的論理和がＮを法として３乗剰余となるような関数とし、署名生成鍵に加える。
ステップ６２０１：署名対象のデータＭと署名生成鍵を入力する。
ステップ６２０２：乱数ｒを生成する。
ステップ６２０３：圧縮関数ＨにデータＭを入力し、圧縮値ｗ＝Ｈ（Ｍ）を計算する。
ステップ６２０４：関数ψにｗとｒを入力し、出力値ｒ’を求める。
ステップ６２０５：ｗとｒ’の連結をｙとおく。
ステップ６２０６：署名値の計算。Ｎを法としたｙの３乗根を計算し、それをｘとおく。
ステップ６２０７：署名対象のデータＭと、署名値ｘとの連結を署名データＷとする。
ステップ６２０８：署名データとしてＷを出力する。
【００５８】
ここで、ステップ６２０２、６２０３、６２０４、６２０５がステップ２１０２に対応し、ステップ６２０６がステップ２１０３に対応し、ステップ６２０７がステップ２１０４に対応している。
【００５９】
ステップ６２０７において、署名データＷは、Ｍとｘとの連結として説明したが、署名データＷは、Ｗから誰もが容易にＭとｘを導くことが出来るならば他の方法で構成されていてもよい。
【００６０】
署名検証プログラムＰＲＯＧ２（１０１７）におけるステップ２２０２：署名検証のための前処理、ステップ２２０３：３乗剰余関数ｆの順像計算、およびステップ２２０４：署名検証のための後処理について、図１４を用いて説明する。
ステップ６３０１：署名データＷと署名検証鍵を入力する。
ステップ６３０２：署名データＷからＭとｘを取り出す。署名データがステップ６２０７のように作成されている場合、Ｗの下位から署名値の長さ分を取り出し、ｘとおき、残りをＭとする。
ステップ６３０３：圧縮関数ＨにデータＭを入力し、圧縮値ｗ＝Ｈ（Ｍ）を計算する。
ステップ６３０４：Ｎを法としてｘ３を計算し、それをｙ’とおく。
ステップ６３０５：ｙ’をｗ’とｒ’とに分割する。
ステップ６３０６：ｗ＝ｗ’ならばステップ６３０８へ行く。
ステップ６３０７：「不合格」を出力して終了する。
ステップ６３０８：「合格」を出力して終了する。
【００６１】
ここで、ステップ６３０２、６３０３がステップ２２０２に対応し、ステップ６３０４がステップ２２０３に対応し、ステップ６３０５、６３０６がステップ２２０４に対応している。
【００６２】
署名生成プログラムの実施におけるステップ６２０４、ステップ６２０５、ステップ６２０６は、図７を用いて説明したステップ３４０１からステップ３４１６において、
ｋをｑのビット長とするとき、入力としてＺ＝（Ｈ（Ｍ）｜｜０ｋ） ｍｏｄ ｑを加え（ただし、０ｋは、ビット０がｋ個並んだビット列を表す。また｜｜はビット列の連結を表す。）、
ステップ３４０７と、ステップ３４０９において、ｗ＝Ｈ（Ｍ）｜｜（ｈ３−Ｚ ｍｏｄ ｑ）とすることにより実行される。
【実施例５】
【００６３】
図１５はネットワーク７００１によって接続されたコンピュータＡ７００２、コンピュータＢ７００３、ＩＣカード７００４、ＩＣカードリーダライタ７００５を含む、コンピュータＡ７００２からコンピュータＢ７００３への通信を目的としたシステム構成を示すものである。
【００６４】
コンピュータＡ７００２は内部にＣＰＵ７００６、メモリ７００７、ネットワークインターフェース７００８、ＩＣカードとの通信で用いるインターフェース７００９を装備しており、外部にはコンピュータＡ７００２をユーザが操作するためのディスプレイ７０１０とキーボード７０１１が接続されている。
【００６５】
さらに、ＩＣカード７００４との通信を行うことが可能なＩＣカードリーダライタ７００５も接続されている。コンピュータＡ７００２のメモリ７００７にはデータ圧縮プログラムＰＲＯＧ３（７０１２）と署名対象のデータＭ７０１３、署名生成後処理プログラムＰＲＯＧ５（７０１４）が保存されている。
【００６６】
ＩＣカード７００４は内部にＣＰＵ７０１５、メモリ７０１６、インターフェース７０１７を装備しており、メモリ７０１６には署名生成プログラムＰＲＯＧ４（７０１８）、署名生成のための秘密鍵Ｓ１０１０が保存されている。
【００６７】
コンピュータＢ７００３には内部にＣＰＵ７０１９、メモリ７０２０、ネットワークインターフェース７０２１を装備しており、外部にはコンピュータＢ７００３をユーザが操作するためのディスプレイ７０２２とキーボード７０２３が接続されている。メモリ７０２０には署名検証プログラムＰＲＯＧ２（１０１７）と、署名検証用鍵１０１８が保存されている。
【００６８】
コンピュータＡ７００２はデータ圧縮プログラムＰＲＯＧ３（７０１２）を実行し、データＭ７０１３の圧縮値７０２３を作成し、インターフェース７００９を通して署名生成命令と共にＩＣカード７００４に送信する。
【００６９】
ＩＣカード７００４はインターフェース７０１７を通して受信したあと、署名生成プログラムＰＲＯＧ４（７０１８）を実行し、署名値７０２５を作成し、再びインターフェース７００９を通してコンピュータＡ７００２に送信する。
【００７０】
コンピュータＡ７００２はインターフェース７００９と通して受信した後、署名生成後処理プログラムＰＲＯＧ５（７０１４）を実行し、データＭ７０１３と署名値７０２５から署名データ７０２６を作成し、それをネットワークインターフェース７００８を通してネットワーク７００１へ送信する。
【００７１】
コンピュータＢ７００３はネットワークインターフェース７０２１を通して受信したあと、署名検証プログラムＰＲＯＧ２（１０１７）を実行し、検証結果をメモリ７０２０に保存する。
【００７２】
各プログラムは、互いのコンピュータまたは他のコンピュータからネットワーク７００１上の伝送媒体である伝送信号により、またはＣＤ-ＲＯＭ、フレキシブルディスクなどの可搬型記憶媒体を介してメモリにデータを導入することができる。各コンピュータおよびＩＣカードは、各装置のオペレーションシステム（図示していない）の元で動作するように構成することも可能である。
【００７３】
データ圧縮プログラムＰＲＯＧ３（７０１２）はコンピュータＡ７００２において、メモリ７００７から読み出されＣＰＵ７００６により実行され、コンピュータＡ７００２上にデータ圧縮処理部を実現する。データ圧縮プログラムＰＲＯＧ３（７０１２）はデータＭ７０１４から圧縮値７０２４を出力する。
【００７４】
署名生成後処理プログラムＰＲＯＧ５（７０１４）はコンピュータＡ７００２において、メモリ７００７から読み出されＣＰＵ７００６により実行され、コンピュータＡ７００２上に署名生成後処理部を実現する。署名生成後処理プログラムＰＲＯＧ５（７０１４）はデータＭ７０１４と署名値７０２５から署名データ７０２６を出力する。
【００７５】
署名生成プログラムＰＲＯＧ４（７０１８）はＩＣカード７００４において、メモリ７０１６から読み出されて、ＣＰＵ７０１５により実行され、ＩＣカード７００４上に署名生成処理部を実現する。署名生成プログラムＰＲＯＧ４（７０１８）は、署名生成鍵Ｓ１０１０、圧縮値７０２４に対し、署名値７０２５を出力する。
【００７６】
署名検証プログラムＰＲＯＧ２（１０１７）はコンピュータＢ７００３において、メモリ７０２０から読み出されＣＰＵ７０１９により実行され、コンピュータＢ７００３上に署名検証処理部を実現する。署名プログラムＰＲＯＧ２（１０１７）は署名検証鍵Ｋ１０１８、署名データ７０２６から検証結果を出力する。
【００７７】
データ圧縮プログラムＰＲＯＧ３（７０１２）は、署名生成方法として実施例１の方法を用いた場合には、ステップ３２０２を実行し、圧縮値としてｗを出力する。
【００７８】
署名生成方法として実施例２の方法を用いた場合には、ステップ４２０２〜ステップ４２０４を実行し、圧縮値としてｗを出力する。
【００７９】
署名生成方法として実施例３の方法を用いた場合には、ステップ５２０２〜ステップ５２０４を実行し、圧縮値としてｗを出力する。
【００８０】
署名生成方法として実施例４の方法を用いた場合には、ステップ６２０３を実行し、圧縮値としてｗを出力する。
【００８１】
署名生成プログラムＰＲＯＧ４（７０１８）は、データ圧縮以外の署名生成処理を行う。
【００８２】
実施例１の方法で署名生成を実施した場合には、ステップ３２０３、ステップ３２０４を実行し、署名値としてｘを出力する。
【００８３】
実施例２の方法で署名生成を実施した場合には、ステップ４２０５、ステップ４２０６を実行し、署名値としてｘを出力する。
【００８４】
実施例３の方法で署名生成を実施した場合には、ステップ５２０５、ステップ５２０６を実行し、署名値としてｘを出力する。
【００８５】
実施例４の方法で署名生成を実施した場合には、ステップ６２０２、ステップ６２０４〜ステップ６２０６を実行し、署名値としてｘを出力する。
【００８６】
署名生成後処理プログラムＰＲＯＧ５（７０１４）は、実施例１の方法で署名生成を実施した場合には署名生成手順におけるステップ３２０５を実行し、署名データとしてＷを出力する。
【００８７】
実施例２の方法で署名生成を実施した場合には、ステップ４２０７を実行し、署名データとしてＷを出力する。
【００８８】
実施例３の方法で署名生成を実施した場合には、ステップ５２０７を実行し、署名データとしてＷを出力する。
【００８９】
実施例４の方法で署名生成を実施した場合には、ステップ６２０７を実行し、署名データとしてＷを出力する。
【実施例６】
【００９０】
図１６は回線８００１で接続された装置Ａ８００２が装置Ｂ８００３の正当性を認証することを目的としたしステム構成を示すものである。装置Ａ８００２は内部にＣＰＵ８００４、メモリ８００５、インターフェース８００６を装備している。装置Ａ８００２のメモリ８００５には乱数生成プログラムＰＲＯＧ６（８００７）と署名検証プログラムＰＲＯＧ２（１０１７）と署名検証鍵Ｋ１０１８が保存されている。
【００９１】
装置Ｂ８００３は内部にＣＰＵ８００８、メモリ８００９、インターフェース８０１０を装備している。装置Ｂ８００３のメモリ８００９には署名生成プログラムＰＲＯＧ１（１００９）と署名生成鍵Ｓ１０１０が保存されている。
【００９２】
装置Ａ８００２は装置Ｂ８００３の正当性を認証する場合、乱数生成プログラムＰＲＯＧ６（８００７）を実行し、乱数８０１１を生成し、インターフェース８００６を通して装置Ｂ８００３に送信する。
【００９３】
装置Ｂ８００３はインターフェース８０１０を通して受信したあと、署名生成プログラムＰＲＯＧ１（１００９）を実行し、受信した乱数８０１１に対する署名データ８０１２を作成し、再びインターフェース８０１０を通して装置Ａ８００２に送信する。
【００９４】
装置Ａ８００２はインターフェース８００６を通して受信したのち、署名検証プログラムＰＲＯＧ２（１０１７）を実行し、署名データ８０１２に含まれる署名値が、乱数８０１１を署名対象データとしたときの署名として正しいかどうか、署名検証鍵１０１８により検証する。署名が正しく生成されているならば装置Ｂ８００３を正当であると判断し、正しく生成されていなければ装置Ｂ８００３を正当でないと判断し、その結果をメモリ８００５に保存する。
【００９５】
署名生成プログラムＰＲＯＧ１（１００９）は装置Ｂ８００３において、メモリ８００９から読み出されて、ＣＰＵ８００８により実行され、装置Ｂ８００３上に署名生成処理部を実現する。署名生成プログラムＰＲＯＧ１（１００９）は、署名生成鍵Ｓ１０１０、署名対象データとしての乱数８０１１に対し、署名データ８０１３を出力する。
【００９６】
署名検証プログラムＰＲＯＧ２（１０１７）は装置Ａ８００２において、メモリ８００４から読み出されＣＰＵ８００４により実行され、装置Ａ８００２上に署名検証処理部を実現する。署名プログラムＰＲＯＧ２（１０１７）は署名検証鍵Ｋ１０１８、署名データ８０１２および署名対象データとしての乱数８０１１から検証結果を出力する。
【００９７】
乱数生成プログラムＰＲＯＧ６（８００７）は装置Ａ８００２において、メモリ８００５から読み出されＣＰＵ８００４により実行され、装置Ａ８００２上に乱数生成処理部を実現する。乱数生成プログラムＰＲＯＧ６（８００７）は乱数列を出力する。
【００９８】
本実施例における各計算は、ＣＰＵがメモリ内の各プログラムを実行することにより行われるものとして説明したが、プログラムだけではなく、いずれかがハードウエア化された演算装置であって、他の演算装置や、ＣＰＵと、データのやりとりを行うものであってもよい。
【００９９】
装置Ａや装置ＢはコンピュータやＩＣカード、ネットワークルータなどでもよい。また、各装置は回線で接続されているものとして説明したが、コンピュータとリーダライタを介してつながれるＩＣカードや、インターネットで接続されるコンピュータであってもよい。
【０１００】
各実施例では、送信者と受信者が各々の装置を利用して通信を行うという一般形で述べたが、具体的には様々なシステムに適用される。
【０１０１】
例えば、電子商取引システム、電子ショッピングシステムでは、送信者はユーザであり、送信者側装置はパソコンなどの計算機であり、受信者は小売店またはその従業者、受信者側装置は小売店側装置、具体的には当該店舗におけるパソコンなどの計算機となる。このとき、ユーザが注文した商品等の注文書に対して本実施例による方法で署名を生成し、注文書と署名データが小売店側装置に送信される。
【０１０２】
また、電子メールシステムでは、各々の装置はパソコンなどの計算機であり、送信者のメッセージまたはメッセージに対して本実施例による方法で署名を生成し、メッセージと署名データが受信者の計算機に送信される。
【図面の簡単な説明】
【０１０３】
【図１】実施例１〜４のシステム構成を示す図である。
【図２】各実施例の署名生成処理の概略手順を示す図である。
【図３】各実施例の署名検証処理の概略手順を示す図である。
【図４】実施例１で用いる署名生成鍵と署名検証鍵の生成手順を示す図である。
【図５】実施例１の署名生成処理の詳細を示す図である。
【図６】実施例１の署名検証処理の詳細を示す図である。
【図７】実施例１の署名生成処理の一部の詳細を示す図である。
【図８】実施例２で用いる署名生成鍵と署名検証鍵の生成手順を示す図である。
【図９】実施例２の署名生成処理の詳細を示す図である。
【図１０】実施例２の署名検証処理の詳細を示す図である。
【図１１】実施例３の署名生成処理の詳細を示す図である。
【図１２】実施例３の署名検証処理の詳細を示す図である。
【図１３】実施例４の署名生成処理の詳細を示す図である。
【図１４】実施例４の署名検証処理の詳細を示す図である。
【図１５】実施例５のシステム構成を示す図である。
【図１６】実施例６のシステム構成を示す図である。
【符号の説明】
【０１０４】
１００１、７００１：ネットワーク
１００９：署名生成プログラムＰＲＯＧ１
１０１０：署名生成鍵 Ｓ
１０１１：データＭ
１０１７：署名検証プログラムＰＲＯＧ２
１０１８：署名検証鍵 Ｋ
７０１８：署名検証プログラムＰＲＯＧ４
１００２、１００３、７００２、７００３：コンピュータ
１００４、１０１２、７００６、７０１４、７０１８、８００４、８００８：ＣＰＵ
１００５、１０１３、７００７、７０１６、７０２０、８００５、８００９：メモリ
１００６、１０１４、７００８、７０２１：ネットワークインターフェース
１００７、１０１５、７０１０、７０２２：ディスプレイ
１００８、１０１６、７０１１、７０２３：キーボード
７００４：ＩＣカード
７００５：ＩＣカードリーダライタ
７００９、７０１７、８００６、８０１０：インターフェース
８００１：回線
８００２、８００３：装置
【図１】
2005167525.tif 000003
【図２】
2005167525.tif 000004
【図３】
2005167525.tif 000005
【図４】
2005167525.tif 000006
【図５】
2005167525.tif 000007
【図６】
2005167525.tif 000008
【図７】
2005167525.tif 000009
【図８】
2005167525.tif 000010
【図９】
2005167525.tif 000011
【図１０】
2005167525.tif 000012
【図１１】
2005167525.tif 000013
【図１２】
2005167525.tif 000014
【図１３】
2005167525.tif 000015
【図１４】
2005167525.tif 000016
【図１５】
2005167525.tif 000017
【図１６】
2005167525.tif 000018