(57)【要約】      （修正有）【課題】２剰余環Ｚ／ＮＺ（但し、Ｎ＝２Ｗ、ｗは３以上の整数）上でｄ次のチェビシェフ多項式Ｔｄ（ｘ）を考えることにより構成される次数決定問題（但し、当該次数決定問題とは、パラメータＮとパラメータｘと（但し、ｘとＮは整数、０≦ｘ＜Ｎ）と整数ｙ（但し、０≦ｙ＜Ｎ）とから、ｙ＝Ｔｄ（ｘ）ｍｏｄＮを満たす正の整数ｄを求める問題とする。）を解くことを困難にするパラメータｘを生成する。【解決手段】次数決定問題のパラメータＮと適切に設定した所定値と用いて、ｑ＝ｘ２−１  ｍｏｄＮで定義される整数ｑが因数４の個数を前記所定値以上有するという条件を満たすパラメータｘを計算して生成する。【選択図】図１
2010002786.tif 000002
【特許請求の範囲】
【請求項１】
２冪剰余環Ｚ／ＮＺ（但し、Ｎ＝２Ｗ、ｗは３以上の整数）上でｄ次のチェビシェフ多項式Ｔｄ（ｘ）を考えることにより構成される次数決定問題（但し、当該次数決定問題とは、パラメータＮとパラメータｘと（但し、ｘとＮは整数、０≦ｘ＜Ｎ）と整数ｙ（但し、０≦ｙ＜Ｎ）とから、ｙ＝Ｔｄ（ｘ）  ｍｏｄ  Ｎを満たす正の整数ｄを求める問題とする。）を解くことを困難にするパラメータｘを生成する生成装置であって、
前記パラメータＮを格納するパラメータＮ格納部と、
第１の所定値を格納する第１の所定値格納部と、
前記パラメータＮ格納部に格納された前記パラメータＮと前記第１の所定値格納部に格納された前記第１の所定値とを読み出して、
ｑ＝ｘ２−１  ｍｏｄ  Ｎで定義される整数ｑが因数４の個数を前記第１の所定値以上有するという第１の条件を満たすパラメータｘを計算して生成する計算部と、
前記計算部において生成された前記パラメータｘを少なくとも出力する出力部と、
を有することを特徴とするパラメータ生成装置。
【請求項２】
請求項１に記載のパラメータ生成装置において、
更に、第２の所定値を格納する第２の所定値格納部を有し、
前記計算部は、前記パラメータＮ格納部に格納された前記パラメータＮと前記第１の所定値格納部に格納された前記第１の所定値と第２の所定値格納部に格納された前記第２の所定値とを読み出して、前記第１の条件と、更に、ｘ＝Ｔ２ｅ−１（ｘ）  ｍｏｄ  Ｎを満たす２以上の最小の整数ｅが前記第２の所定値以上であるという第２の条件を満たすパラメータｘを計算して生成するパラメータ生成装置。
【請求項３】
コンピュータ又は専用計算装置で実行される、２冪剰余環Ｚ／ＮＺ（但し、Ｎ＝２Ｗ、ｗは３以上の整数）上でｄ次のチェビシェフ多項式Ｔｄ（ｘ）を考えることにより構成される次数決定問題（但し、当該次数決定問題とは、パラメータＮとパラメータｘと（但し、ｘとＮは整数、０≦ｘ＜Ｎ）と整数ｙ（但し、０≦ｙ＜Ｎ）とから、ｙ＝Ｔｄ（ｘ）  ｍｏｄ  Ｎを満たす正の整数ｄを求める問題とする。）を解くことを困難にするパラメータｘを生成する生成方法であって、
前記コンピュータ又は専用計算装置に格納された前記パラメータＮと第１の所定値とを読み出す読み出し工程と、
ｑ＝ｘ２−１  ｍｏｄ  Ｎで定義される整数ｑが因数４の個数を前記第１の所定値以上有するという第１の条件を満たすパラメータｘを計算して生成する計算工程と、
前記計算工程において生成された前記パラメータｘを少なくとも出力する出力工程と、
を有することを特徴とするパラメータ生成方法。
【請求項４】
請求項３に記載のパラメータ生成方法において、
前記読み出し工程は、更に、コンピュータ又は専用計算装置に格納された第２の所定値を読み出し、
前記計算工程は、前記第１の条件と、更に、ｘ＝Ｔ２ｅ−１（ｘ）  ｍｏｄ  Ｎを満たす２以上の最小の整数ｅが前記第２の所定値以上であるという第２の条件を満たすパラメータｘを計算して生成するパラメータ生成方法。
【請求項５】
請求項１に記載されたパラメータ生成装置、請求項２に記載されたパラメータ生成装置、請求項３に記載されたパラメータ生成方法及び請求項４に記載されたパラメータ生成方法のいずれかによって生成されたパラメータｘと、パラメータＮとを用いた鍵共有システムであって、
送付鍵生成装置と、第１の鍵共有装置と、第２の鍵共有装置とを有し、
前記送付鍵生成装置は、
正の整数ｓを取得する整数取得部と、
前記パラメータｘと前記パラメータＮと取得した前記整数ｓとから、
Ｔ＝Ｔｓ（ｘ）  ｍｏｄ  Ｎ
により送付鍵Ｔを計算する送付鍵計算部と、
計算された前記送付鍵Ｔを前記第１の鍵共有装置に出力する第１送付鍵出力部と、
前記整数ｓを送付鍵として前記第２の鍵共有装置に出力する第２送付鍵出力部と、
を有し、
前記第１の鍵共有装置は、
正の整数ｔを取得する整数取得部と、
前記整数ｔと前記パラメータｘと前記パラメータＮとから、
Ｕ＝Ｔｔ（ｘ）  ｍｏｄ  Ｎ
により送付鍵Ｕを計算する送付鍵計算部と、
計算された前記送付鍵Ｕを前記第２の鍵共有装置に出力する送付鍵出力部と、
前記送付鍵生成装置が出力した前記送付鍵Ｔを入力する送付鍵入力部と、
入力された前記送付鍵Ｔから、
Ｖ’＝Ｔｔ（Ｔ）  ｍｏｄ  Ｎ
により共有鍵Ｖ’を計算する共有鍵計算部と、
を有し、
前記第２の鍵共有装置は、
前記第１の鍵共有装置が出力した前記送付鍵Ｕを入力する第１送付鍵入力部と、
前記送付鍵生成装置が送付鍵として出力した前記整数ｓを入力する第２送付鍵入力部と、
前記パラメータＮと前記整数ｓと前記送付鍵Ｕとから、
Ｖ＝Ｔｓ（Ｕ）  ｍｏｄ  Ｎ
により共有鍵Ｖを計算する共有鍵計算部と、
を有することを特徴とする鍵共有システム。
【請求項６】
請求項５に記載の鍵共有システムを用いた公開鍵暗号システムであって、
前記第１の鍵共有装置は、更に、
平文のメッセージを前記共有鍵Ｖ’により暗号化して暗号化メッセージを得る暗号化部と、
前記第２の鍵共有装置に前記暗号化メッセージを送信する暗号化メッセージ送信部と、
を有し、
前記第２の鍵共有装置は、更に、
前記第１の鍵共有装置が送信した前記暗号化メッセージを受信する暗号化メッセージ受信部と、
受信された前記暗号化メッセージを前記共有鍵Ｖにより復号化して、前記平文のメッセージを得る復号化部と、
を有することを特徴とする公開鍵暗号システム。
【請求項７】
請求項１に記載されたパラメータ生成装置、請求項２に記載されたパラメータ生成装置、請求項３に記載されたパラメータ生成方法及び請求項４に記載されたパラメータ生成方法のいずれかによって生成されたパラメータｘと、パラメータＮとを用いた公開鍵暗号システムであって、
鍵対生成装置と、暗号化装置と、復号化装置とを有し、
前記鍵対生成装置は、
正の奇数である整数ｓを取得する整数取得部と、
取得した前記整数ｓと前記パラメータｘと前記パラメータＮとから、
Ｔ＝Ｔｓ（ｘ）  ｍｏｄ  Ｎ    
により公開鍵Ｔを計算する公開鍵計算部と、
計算された前記公開鍵Ｔを前記暗号化装置に公開する公開鍵公開部と、
前記整数ｓを秘密鍵として前記復号化装置に出力する秘密鍵出力部と、
を有し、
前記暗号化装置は、
前記鍵対生成装置が公開した公開鍵Ｔを受け付ける公開鍵受付部と、
正の奇数である整数ｒを取得する整数取得部と、
奇数であるメッセージｍ（０＜ｍ＜Ｎ）と取得した前記整数ｒと前記パラメータｘと前記パラメータＮとから、
ｃ１＝Ｔｒ（ｘ）  ｍｏｄ  Ｎ
ｃ２＝ｍＴｒ（Ｔ）  ｍｏｄ  Ｎ
により整数の組である暗号化メッセージ（ｃ１，ｃ２）を計算する暗号化部と、
前記暗号化メッセージ（ｃ１，ｃ２）を前記復号化装置へ送信する暗号化メッセージ送信部と、
を有し、
前記復号化装置は、
前記暗号化装置が送信した前記暗号化メッセージ（ｃ１，ｃ２）を受信する暗号化メッセージ受信部と、
前記鍵対生成装置が秘密鍵として出力した前記整数ｓを入力する秘密鍵入力部と、
入力された前記整数ｓと受信された前記暗号化メッセージ（ｃ１，ｃ２）の第１成分ｃ１と前記パラメータＮとから、
１＝αＴｓ（ｃ１）  ｍｏｄ  Ｎ
を満たす中間整数αを求める中間整数計算部と、
受信された前記暗号化メッセージ（ｃ１，ｃ２）の第２成分ｃ２と前記中間整数αと前記パラメータＮとから、
ｍ’＝αｃ２  ｍｏｄ  Ｎ
によりメッセージｍ’を得る復号化部と、
を有することを特徴とする公開鍵暗号システム。
【請求項８】
請求項１に記載されたパラメータ生成装置、請求項２に記載されたパラメータ生成装置、請求項３に記載されたパラメータ生成方法及び請求項４に記載されたパラメータ生成方法のいずれかによって生成されたパラメータｘと、パラメータＮとを用いた公開鍵暗号システムであって、
鍵対生成装置と暗号化装置と復号化装置を有し、
前記鍵対生成装置は、
正の整数ｓを取得する整数取得部と、
前記整数ｓと前記パラメータｘと前記パラメータＮとから、
Ｔ＝Ｔｓ（ｘ）  ｍｏｄ  Ｎ
により公開鍵Ｔを計算する公開鍵計算部と、
計算された前記公開鍵Ｔを前記暗号化装置に公開する公開鍵公開部と、
前記整数ｓを秘密鍵として前記復号化装置に出力する秘密鍵出力部と、
を有し、
前記暗号化装置は、
前記鍵対生成装置が公開した前記公開鍵Ｔを受け付ける公開鍵受付部と、
正の整数ｒを取得する整数取得部と、
整数であるメッセージｍ（０≦ｍ＜Ｎ）と前記整数ｒと前記パラメータｘと前記パラメータＮとから、
ｃ１＝Ｔｒ（ｘ）  ｍｏｄ  Ｎ
ｃ２＝（Ｔｒ（Ｔ）  ｍｏｄ  Ｎ） ｘｏｒ ｍ
により整数の組である暗号化メッセージ（ｃ１，ｃ２）を計算する暗号化部と、
前記暗号化メッセージ（ｃ１，ｃ２）を前記復号化装置へ送信する暗号化メッセージ送信部と、
を有し、
前記復号化装置は、
前記暗号化装置が送信した前記暗号化メッセージ（ｃ１，ｃ２）を受信する暗号化メッセージ受信部と、
前記鍵対生成装置が秘密鍵として出力した前記整数ｓを入力する秘密鍵入力部と、
入力された前記整数ｓと受信された前記暗号化メッセージ（ｃ１，ｃ２）と前記パラメータＮとから、
ｍ’＝（Ｔｓ（ｃ１）  ｍｏｄ  Ｎ）  ｘｏｒ  ｃ２
によりメッセージｍ’を得る復号化部と、
を有することを特徴とする公開鍵暗号システム。
（但し、Ａ  ｘｏｒ  Ｂは、２進数ＡとＢのビット毎の排他的論理和演算を表わす。）
【請求項９】
請求項１に記載されたパラメータ生成装置、請求項２に記載されたパラメータ生成装置、請求項３に記載されたパラメータ生成方法及び請求項４に記載されたパラメータ生成方法のいずれかによって生成されたパラメータｘと、パラメータＮとを用いた電子署名システムであって、
鍵対生成装置と、署名装置と、認証装置とを有し、
前記鍵対生成装置は、
正の整数ｓを取得する整数取得部と、
前記整数ｓと前記パラメータｘと前記パラメータＮとから、
Ｔ＝Ｔｓ（ｘ）  ｍｏｄ  Ｎ
により公開鍵Ｔを計算する公開鍵計算部と、
計算された前記公開鍵Ｔを前記認証装置に公開する公開鍵公開部と、
前記整数ｓを秘密鍵として前記署名装置に出力する秘密鍵出力部と、
を有し、
前記署名装置は、
整数Ｍを２ｅの倍数であってＮ以下のものとし（ｅは、ｘ＝Ｔ２ｅ−１（ｘ）  ｍｏｄ  Ｎを満たす２以上の最小の整数）、Ｍと互いに素な正の整数ｋと、前記整数ｋから１
＝ ｋ’ｋ  ｍｏｄ Ｍを満たす正の整数ｋ’を発生させる整数発生部と、
前記鍵対生成装置が秘密鍵として出力した整数ｓを入力する秘密鍵入力部と、
前記パラメータｘと前記パラメータＮと整数ｓと整数であるメッセージｍ（０≦ｍ＜Ｎ）とから、
ａ＝Ｔｋ（ｘ）  ｍｏｄ  Ｎ
ｂ＝ｋ’（ｓａ＋ｈ（ｍ））  ｍｏｄ  Ｍ
（但し、ｈ（ｍ）は正の整数であって、ｍ自身又はｍのハッシュ関数値とする。）
により署名付メッセージ（ａ，ｂ，ｍ）を計算する署名部と、
前記署名付メッセージ（ａ，ｂ，ｍ）を前記認証装置へ送信する署名付メッセージ送信部と、
を有し、
前記認証装置は、
前記鍵対生成装置が公開した前記公開鍵Ｔを受け付ける公開鍵受付部と、
前記署名装置が送信した前記署名付メッセージ（ａ，ｂ，ｍ）を受信する署名付メッセージ受信部と、
受け付けられた前記公開鍵Ｔと前記受信された署名付メッセージ（ａ，ｂ，ｍ）と前記パラメータｘと前記パラメータＮから、前記整数ｈ（ｍ）を設定し整数Ｗを、
Ｗ＝Ｔｈ（ｍ）（ｘ）２−２Ｔｈ（ｍ）（ｘ）Ｔａ（Ｔ）Ｔｂ（ａ）＋Ｔａ（Ｔ）２＋Ｔｂ（ａ）２−１  ｍｏｄ  Ｎ
により計算する整数計算部と、
前記整数Ｗが０に等しい場合、前記署名付メッセージ（ａ，ｂ，ｍ）を認証する認証部と、
を有することを特徴とする電子署名システム。
【請求項１０】
請求項５に記載された鍵共有システムの送付鍵生成装置。
【請求項１１】
請求項５に記載された鍵共有システムの第１の鍵共有装置。
【請求項１２】
請求項５に記載された鍵共有システムの第２の鍵共有装置。
【請求項１３】
請求項６に記載された公開鍵暗号システムの第１の鍵共有装置。
【請求項１４】
請求項６に記載された公開鍵暗号システムの第２の鍵共有装置。
【請求項１５】
請求項８に記載された公開鍵暗号システムの暗号化装置。
【請求項１６】
請求項８に記載された公開鍵暗号システムの復号化装置。
【請求項１７】
請求項９に記載された電子署名システムの署名装置。
【請求項１８】
請求項９に記載された電子署名システムの認証装置。
【請求項１９】
コンピュータ又は専用計算装置で実行される、請求項１に記載されたパラメータ生成装置、請求項２に記載されたパラメータ生成装置、請求項３に記載されたパラメータ生成方法及び請求項４に記載されたパラメータ生成方法のいずれかによって生成されたパラメータｘと、パラメータＮとを用いて共有鍵を生成するのに必要な送付鍵Ｔを生成する方法であって、
正の整数ｓを取得する整数取得工程と、
前記パラメータｘと前記パラメータＮと取得した前記整数ｓとから、
Ｔ＝Ｔｓ（ｘ）  ｍｏｄ  Ｎ
により送付鍵Ｔを計算する送付鍵計算工程と、
を有することを特徴とする送付鍵生成方法。
【請求項２０】
コンピュータ又は専用計算装置で実行される、請求項１に記載されたパラメータ生成装置、請求項２に記載されたパラメータ生成装置、請求項３に記載されたパラメータ生成方法及び請求項４に記載されたパラメータ生成方法のいずれかによって生成されたパラメータｘと、パラメータＮとを用いた鍵共有方法であって、
正の整数ｔを取得する整数取得工程と、
前記整数ｔと前記パラメータｘと前記パラメータＮとから、
Ｕ＝Ｔｔ（ｘ）  ｍｏｄ  Ｎ
により送付鍵Ｕを計算する送付鍵計算工程と、
計算された前記送付鍵Ｕを他の鍵共有装置に出力する送付鍵出力工程と、
請求項１９に記載された送付鍵生成方法において生成された前記送付鍵Ｔを入力する送付鍵入力工程と、
入力された前記送付鍵Ｔから、
Ｖ’＝Ｔｔ（Ｔ）  ｍｏｄ  Ｎ
により共有鍵Ｖ’を計算する共有鍵計算工程と、
を有することを特徴とする鍵共有方法。
【請求項２１】
コンピュータ又は専用計算装置で実行される、請求項１に記載されたパラメータ生成装置、請求項２に記載されたパラメータ生成装置、請求項３に記載されたパラメータ生成方法及び請求項４に記載されたパラメータ生成方法のいずれかによって生成されたパラメータｘに対応するパラメータＮを用いた鍵共有方法であって、
請求項２０に記載の鍵共有方法において計算された前記送付鍵Ｕを入力する第１送付鍵入力工程と、
請求項１９に記載された送付鍵生成方法において取得された前記整数ｓを送付鍵として入力する第２送付鍵入力工程と、
前記パラメータＮと前記整数ｓと前記送付鍵Ｕとから、
Ｖ＝Ｔｓ（Ｕ）  ｍｏｄ  Ｎ
により共有鍵Ｖを計算する共有鍵計算工程と、
を有することを特徴とする鍵共有方法。
【請求項２２】
請求項２０に記載された鍵共有方法を用いた暗号化方法であって、
更に、平文のメッセージを前記共有鍵Ｖ’により暗号化して暗号化メッセージを得る暗号化工程を有することを特徴とする暗号化方法。
【請求項２３】
請求項２１に記載された鍵共有方法を用いた復号化方法であって、
更に、請求項２２に記載された暗号化された暗号化メッセージを前記共有鍵Ｖにより復号化して、前記平文のメッセージを得る復号化工程を有することを特徴とする復号化方法。
【請求項２４】
コンピュータ又は専用計算装置で実行される、請求項１に記載されたパラメータ生成装置、請求項２に記載されたパラメータ生成装置、請求項３に記載されたパラメータ生成方法及び請求項４に記載されたパラメータ生成方法のいずれかによって生成されたパラメータｘと、パラメータＮとを用いた鍵対生成方法であって、
正の整数ｓを取得する整数取得工程と、
取得した前記整数ｓと前記パラメータｘと前記パラメータＮとから、
Ｔ＝Ｔｓ（ｘ）  ｍｏｄ  Ｎ    
により公開鍵Ｔを計算する公開鍵計算工程と、
計算された前記公開鍵Ｔを公開する公開鍵公開工程と、
前記整数ｓを秘密鍵として出力する秘密鍵出力工程と、
を有することを特徴とする鍵対生成方法。
【請求項２５】
コンピュータ又は専用計算装置で実行される、請求項１に記載されたパラメータ生成装置、請求項２に記載されたパラメータ生成装置、請求項３に記載されたパラメータ生成方法及び請求項４に記載されたパラメータ生成方法のいずれかによって生成されたパラメータｘと、パラメータＮとを用いた暗号化方法であって、
請求項２４に記載された鍵対生成方法で前記整数ｓを奇数としたものにおいて公開され
た公開鍵Ｔを受け付ける公開鍵受付工程と、
正の奇数である整数ｒを取得する整数取得工程と、
奇数であるメッセージｍ（０＜ｍ＜Ｎ）と取得した前記整数ｒと前記パラメータｘと前記パラメータＮとから、
ｃ１＝Ｔｒ（ｘ）  ｍｏｄ  Ｎ
ｃ２＝ｍＴｒ（Ｔ）  ｍｏｄ  Ｎ
により整数の組である暗号化メッセージ（ｃ１，ｃ２）を計算する暗号化工程と、
を有することを特徴とする暗号化方法。
【請求項２６】
コンピュータ又は専用計算装置で実行される、請求項１に記載されたパラメータ生成装置、請求項２に記載されたパラメータ生成装置、請求項３に記載されたパラメータ生成方法及び請求項４に記載されたパラメータ生成方法のいずれかによって生成されたパラメータｘに対応するパラメータＮを用いた復号化方法であって、
請求項２５に記載された暗号化方法において計算された前記暗号化メッセージ（ｃ１，ｃ２）を受信する暗号化メッセージ受信工程と、
請求項２４に記載された鍵対生成方法で前記整数ｓを奇数としたものにおいて秘密鍵として出力された前記整数ｓを入力する秘密鍵入力工程と、
入力された前記整数ｓと受信された前記暗号化メッセージ（ｃ１，ｃ２）の第１成分ｃ１と前記パラメータＮとから、
１＝αＴｓ（ｃ１）  ｍｏｄ  Ｎ
を満たす中間整数αを求める中間整数計算工程と、
受信された前記暗号化メッセージ（ｃ１，ｃ２）の第２成分ｃ２と前記中間整数αと前記パラメータＮとから、
ｍ’＝αｃ２  ｍｏｄ  Ｎ
によりメッセージｍ’を得る復号化工程と、
を有することを特徴とする復号化方法。
【請求項２７】
コンピュータ又は専用計算装置で実行される、請求項１に記載されたパラメータ生成装置、請求項２に記載されたパラメータ生成装置、請求項３に記載されたパラメータ生成方法及び請求項４に記載されたパラメータ生成方法のいずれかによって生成されたパラメータｘと、パラメータＮとを用いた暗号化方法であって、
請求項２４に記載された鍵対生成方法において公開された前記公開鍵Ｔを受け付ける公開鍵受付工程と、
正の整数ｒを取得する整数取得工程と、
整数であるメッセージｍ（０≦ｍ＜Ｎ）と前記整数ｒと前記パラメータｘと前記パラメータＮとから、
ｃ１＝Ｔｒ（ｘ）  ｍｏｄ  Ｎ
ｃ２＝（Ｔｒ（Ｔ）  ｍｏｄ  Ｎ） ｘｏｒ ｍ
により整数の組である暗号化メッセージ（ｃ１，ｃ２）を計算する暗号化工程と、
を有することを特徴とする暗号化方法。
【請求項２８】
コンピュータ又は専用計算装置で実行される、請求項１に記載されたパラメータ生成装置、請求項２に記載されたパラメータ生成装置、請求項３に記載されたパラメータ生成方法及び請求項４に記載されたパラメータ生成方法のいずれかによって生成されたパラメータｘに対応するパラメータＮを用いた復号化方法であって、
請求項２７に記載された暗号化方法において計算された前記暗号化メッセージ（ｃ１，ｃ２）を受信する暗号化メッセージ受信工程と、
請求項２４に記載された鍵対生成方法において秘密鍵として出力された前記整数ｓを入力する秘密鍵入力工程と、
入力された前記整数ｓと受信された前記暗号化メッセージ（ｃ１，ｃ２）と前記パラメータＮとから、
ｍ’＝（Ｔｓ（ｃ１）  ｍｏｄ  Ｎ）  ｘｏｒ  ｃ２
によりメッセージｍ’を得る復号化工程と、
を有することを特徴とする復号化方法。
（但し、Ａ  ｘｏｒ  Ｂは、２進数ＡとＢのビット毎の排他的論理和演算を表わす。）
【請求項２９】
コンピュータ又は専用計算装置で実行される、請求項１に記載されたパラメータ生成装置、請求項２に記載されたパラメータ生成装置、請求項３に記載されたパラメータ生成方法及び請求項４に記載されたパラメータ生成方法のいずれかによって生成されたパラメータｘと、パラメータＮとを用いた署名方法であって、
整数Ｍを２ｅの倍数であってＮ以下のものとし（ｅは、ｘ＝Ｔ２ｅ−１（ｘ）  ｍｏｄ  Ｎを満たす２以上の最小の整数）、Ｍと互いに素な正の整数ｋと、前記整数ｋから１
＝ ｋ’ｋ  ｍｏｄ Ｍを満たす正の整数ｋ’を発生させる整数発生工程と、
請求項２４に記載された鍵対生成方法において秘密鍵として出力された整数ｓを入力する秘密鍵入力工程と、
前記パラメータｘと前記パラメータＮと整数ｓと整数であるメッセージｍ（０≦ｍ＜Ｎ）とから、
ａ＝Ｔｋ（ｘ）  ｍｏｄ  Ｎ
ｂ＝ｋ’（ｓａ＋ｈ（ｍ））  ｍｏｄ  Ｍ
（但し、ｈ（ｍ）は正の整数であって、ｍ自身又はｍのハッシュ関数値とする。）
により署名付メッセージ（ａ，ｂ，ｍ）を計算する署名工程と、
を有することを特徴とする署名方法。
【請求項３０】
コンピュータ又は専用計算装置で実行される、請求項１に記載されたパラメータ生成装置、請求項２に記載されたパラメータ生成装置、請求項３に記載されたパラメータ生成方法及び請求項４に記載されたパラメータ生成方法のいずれかによって生成されたパラメータｘと、パラメータＮとを用いた認証方法であって、
請求項２４に記載された鍵対生成方法において公開された前記公開鍵Ｔを受け付ける公開鍵受付工程と、
請求項２９に記載された署名方法において計算された署名付メッセージ（ａ，ｂ，ｍ）を受信する署名付メッセージ受信工程と、
受け付けられた前記公開鍵Ｔと前記受信された署名付メッセージ（ａ，ｂ，ｍ）と前記パラメータｘと前記パラメータＮから、前記整数ｈ（ｍ）を設定し整数Ｗを、
Ｗ＝Ｔｈ（ｍ）（ｘ）２−２Ｔｈ（ｍ）（ｘ）Ｔａ（Ｔ）Ｔｂ（ａ）＋Ｔａ（Ｔ）２＋Ｔｂ（ａ）２−１  ｍｏｄ  Ｎ
により計算する整数計算工程と、
前記整数Ｗが０に等しい場合、前記署名付メッセージ（ａ，ｂ，ｍ）を認証する認証工程と、
を有することを特徴とする認証方法。
【請求項３１】
コンピュータを、
請求項１又は２に記載されたパラメータ生成装置、
請求項５に記載された鍵共有システムの送付鍵生成装置、
請求項５に記載された鍵共有システムの第１の鍵共有装置、
請求項５に記載された鍵共有システムの第２の鍵共有装置、
請求項６に記載された公開鍵暗号システムの第１の鍵共有装置、
請求項６に記載された公開鍵暗号システムの第２の鍵共有装置、
請求項７又は８に記載された公開鍵暗号システムの鍵対生成装置、
請求項６、７及び８のいずれか１項に記載された公開鍵暗号システムの暗号化装置、
請求項６、７及び８のいずれか１項に記載された公開鍵暗号システムの復号化装置、
請求項９に記載された電子署名システムの鍵対生成装置、
請求項９に記載された電子署名システムの署名装置、
若しくは請求項９に記載された電子署名システムの認証装置のいずれか１つとして機能させることを特徴とするプログラム。
【請求項３２】
コンピュータに、
請求項３又は４に記載されたパラメータ生成方法、
請求項１９に記載された送付鍵生成方法、
請求項２０又は２１に記載された鍵共有方法、
請求項２２、２５及び２７のいずれか１項に記載された暗号化方法、
請求項２３、２６及び２８のいずれか１項に記載された復号化方法、
請求項２４に記載された鍵対生成方法、
請求項２９に記載された署名方法、
若しくは請求項３０に記載された認証方法のいずれか１つを実行させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パラメータ生成装置、鍵共有システム、公開鍵暗号システム、電子署名システム、送付鍵生成装置、第１の鍵共有装置、第２の鍵共有装置、暗号化装置、復号化装置、署名装置、認証装置、パラメータ生成方法、送付鍵生成方法、鍵共有方法、暗号化方法、復号化方法、鍵対生成方法、署名方法、認証方法及びプログラムに関するものである。
【背景技術】
【０００２】
公開鍵暗号は、今日の情報化社会において、認証、決済等に欠かせない基幹技術の１つになっている。但し、現在主流の公開鍵暗号方式であるＲＳＡ暗号方式やＥｌＧａｍａｌ暗号方式をコンピュータ上で動作させる場合、そのメッセージの暗号化や復号化には、対称鍵暗号方式の１００倍程度の時間を要し、長いメッセージを交換する事は実質的に不可能である。また、携帯電話等に用いられるような計算速度の低いＣＰＵを用いた装置では、公開鍵暗号をソフトウェアとして使用することができない。
【０００３】
そこで、楕円曲線の理論を利用してＥｌＧａｍａｌ暗号方式を高速化した楕円曲線暗号方式の研究が進んでいる。この楕円曲線暗号方式を利用することにより、メッセージを暗号化したり、暗号化されたメッセージを復号化したりする処理速度は、上述したＲＳＡ暗号方式やＥｌＧａｍａｌ暗号方式を用いた公開鍵暗号方式の１０倍から数十倍程度の高速にすることができる。しかし、この楕円曲線暗号方式においては、楕円曲線の選択がデリケートであり、また、この楕円曲線暗号方式を実装するのが困難であるという問題がある。
【０００４】
ここでＥｌＧａｍａｌ暗号方式とは、剰余環Ｚ／ＮＺ上の離散対数問題、つまり或る適当な正の整数Ｎ（通常は大きな素数）を法として，与えられた正の整数ｘ（０≦ｘ＜Ｎ）と正の整数ｙ（０≦ｙ＜Ｎ）から、
ｙ＝ｘｄ  ｍｏｄ  Ｎ
を満たすｄを求める問題が効率的に解けないことを利用した公開鍵暗号方式である。正の整数ｘと正の整数ｄから正の整数ｙを計算する事は容易であるため、一方向性が存在する。
【０００５】
ＥｌＧａｍａｌ暗号方式においては、大きな（２進数で１０００桁以上の）素数Ｎを法とした剰余環を考えるため、この剰余計算に多大な計算時間を要する。もしこの剰余計算を高速化することが可能であれば、対称鍵暗号方式のように長いメッセージを交換できたり、携帯電話等に用いられるような計算速度の低いＣＰＵを用いた装置においても公開鍵暗号をソフトウェアとして使用することができることが期待される。
【０００６】
大きな整数による剰余を高速化する一つの方法として、剰余環Ｚ／ＮＺの法Ｎを２の羃とするという方法が挙げられる。この剰余環を２冪剰余環という。即ち、正の整数ｗについて、Ｎ=２ｗでの剰余計算を行うことにすれば、２進数を利用する通常のコンピュータの特性を上手く利用した高速化が可能である。剰余計算を受ける数をｗビットの２進数として与えておけば、計算過程におけるｗビットの固定長処理，すなわちｗビットを超えた桁溢れの無視が自動的にＮ=２ｗに関する剰余計算となるためである。
【０００７】
しかしながら、２羃剰余環上の離散対数問題は、Ｐｏｈｌｉｇ−Ｈｅｌｌｍａｎ法により多項式時間で解かれてしまう事が知られており、公開鍵暗号方式に適用することができない。
【０００８】
他方、チェビシェフ多項式の性質を利用した公開鍵暗号方式が、特許文献１及び非特許文献１において開示されている。上記の離散対数問題の困難性を安全性の根拠とするのがＥｌＧａｍａｌ暗号方式であるが、この離散対数問題の困難性を剰余環上のチェビシェフ多項式の次数決定問題の困難性に置き換えるのである。
【０００９】
ここで、チェビシェフ多項式とは、０以上の整数ｄに対して定義される、ｘについてｄ次の整数係数の多項式Ｔｄ（ｘ）であって次を満たすものである。
Ｔｄ（ｃｏｓθ）＝ｃｏｓ（ｄθ）．
例えば、Ｔ０（ｘ）＝１、Ｔ１（ｘ）＝ｘ、Ｔ２（ｘ）＝２ｘ２−１である。
【００１０】
そして、このチェビシェフ多項式には、
Ｔａ（Ｔｂ（ｘ））＝Ｔａｂ（ｘ）
という性質がある。
【００１１】
特許文献１には、ガロア有限体上のチェビシェフ多項式に関する次数決定問題の困難性を利用した公開鍵暗号システム、非特許文献１及び２には、剰余環上のチェビシェフ多項式に関する次数決定問題の困難性を利用した公開鍵暗号システムに関する記載がある。
【００１２】
ここで、剰余環上のチェビシェフ多項式に関する次数決定問題を説明する。Ｎを適当な正の整数、ｘとｙとを０以上でＮ未満の整数として、次の式を考える。
ｙ＝Ｔｄ（ｘ）  ｍｏｄ  Ｎ．
【００１３】
上記の式において、既知のｘ、ｄ及びΝから未知のｙを計算する事は容易、言い換えれば、多項式時間で計算可能であることが知られている。しかし、ｘ、ｙ、Ｎを既知で、ｄを未知として、このｘ、ｙ、Ｎからｄを効率的に解くアルゴリズムは、現在までのところ知られていない。即ち、既知のｘ、ｙ及びΝからｄを計算する事は困難であるという一方向性を有する。
【００１４】
チェビシェフ多項式の次数決定問題とは、適当な正の整数Νと、整数ｘ及び整数ｙ（０≦ｘ，ｙ＜Ｎ）に対し、ｙ＝Ｔｄ（ｘ）  ｍｏｄ  Ｎを満たすｄを求める問題である。上述のように、この問題を適当なＮに対し解くことは困難である。
【００１５】
即ち、これらの文献は、ＥｌＧａｍａｌ暗号方式における離散対数問題を、剰余環上のチェビシェフ多項式の次数決定問題に置き換えた公開鍵暗号方式に関するものである。これらの公開鍵暗号システムをプログラム化してコンピュータ等の計算機に実装する場合、ＥｌＧａｍａｌ暗号方式における冪乗多項式ｘｄの計算の代わりに、チェビシェフ多項式Ｔｄ（ｘ）を計算することになる。
【００１６】
チェビシェフ多項式Ｔｄ（ｘ）を用いた暗号方式は、楕円曲線暗号方式に比べるとプログラムの作成についてははるかに容易であるが、しかし、ＥｌＧａｍａｌ暗号方式に比べると、暗号化や復号化に一般に多くの時間がかかり、またプログラムの作成も若干面倒となる。
【００１７】
実際、特許文献１の公開鍵暗号システムは、チェビシェフ多項式の計算に時間を要し、ＥｌＧａｍａｌ暗号方式に比べ、１０倍前後低速である。
【００１８】
非特許文献１では、公開鍵暗号システムの１つである鍵交換システムが開示されている。これはＤｉｆｆｉｅ−Ｈｅｌｌｍａｎ鍵交換法を基にしたものであり、２羃剰余環を利用して、特許文献１に記載の鍵交換システムの高速化を図ったものである。
【００１９】
非特許文献１で説明された鍵交換法は、以下の通りである。この鍵交換法の説明では、この鍵交換法を用いて鍵を交換する者を甲及び乙とする。そして、Ｎ＝２Ｗ（但し、ｗは３以上の整数）とする。
（１）甲と乙は，正の整数ｘ（１＜ｘ＜Ｎ）をとり、ｘとＮをシステムの共通パラメータとして公開する。
（２）甲は、正の奇数ｓを秘密鍵とする。そして、Ｔ＝Ｔｓ（ｘ）  ｍｏｄ  Ｎを求めて、Ｔを乙に配送する。
（３）乙は、正の奇数ｔを秘密鍵とする。そして、Ｕ＝Ｔｔ（ｘ）  ｍｏｄ  Ｎを求め、Ｕを甲に配送する。
（４）甲は、Ｖ  ＝  Ｔｓ（Ｕ）  ｍｏｄ  Ｎを共有鍵とする。乙は、Ｖ’＝Ｔｔ（Ｔ）  ｍｏｄ  Ｎを共有鍵とする。
この鍵交換法では、（４）で示したＶとＶ’はＶ＝Ｖ’となるので、甲と乙は共通鍵を持つことができる。
【００２０】
２羃剰余環以外の通常の剰余環では、計算の多くが剰余計算に占められているが、非特許文献１の鍵交換システムが利用している２羃剰余環では、２進数表現の装置上で或るビット以上の桁上がりを無視することがそのまま剰余計算となる上に、計算の際、一時的な桁数の倍加も発生しないので、コンピュータのハードウェア資源が著しく効率的に使用され、高速化が可能になる。
【００２１】
しかしながら、非特許文献１の鍵交換システムにおいては、暗号鍵生成のパラメータが偶数である場合に、Ｐｏｈｌｉｇ−Ｈｅｌｌｍａｎ法の直接的な応用により、秘密鍵が多項式時間で容易に解読できてしまうという致命的な問題点が、つまり、ｘが偶数の場合には、Ｎとｘを利用することで、Ｔからｓ、そしてＵからｔを多項式時間で計算する方法が、非特許文献２で開示されている。
【００２２】
このように、暗号化・復号化の処理が高速で、暗号システム等をプログラム化してコンピュータ等の計算機に実装することが容易で、かつ、暗号解読が困難という３つの要件を満たす公開鍵暗号システムの研究は様々に進められているが、上述したように、問題を抱えている。
【特許文献１】特開２００３−８５６４号公報
【非特許文献１】Ken Umeno、"Key Exchange byChebyshev Polynomials Modulo 2w、INA-CISC-2005、（インドネシア）、２００５年３月、pp.95-97
【非特許文献２】石井雅治、吉本明宣、「２冪剰余環の既約剰余類群の構造とその応用」、椙山女学園大学現代マネジメント学部ディスカッションペーパー、２００７年、No.１２ Dec. pp.1-9
【発明の開示】
【発明が解決しようとする課題】
【００２３】
現在、一般に公開鍵暗号システムや電子署名システムをコンピュータ上のプログラムとして動作させる際、２進数で１０００桁以上の整数を法とする剰余計算が必要となる。
【００２４】
この剰余計算は、加算や乗算に比べ少なくとも数倍の計算コストがかかり、これが公開鍵暗号システムや電子認証システムの律速過程となっている。もし、この剰余計算を高速に行うことが可能ならば、暗号システムや電子認証を大幅に高速化することができる。
【００２５】
ところで、現代のコンピュータのほとんどが、２進数に基づく計算を行っている。従って、上で述べたように、正の整数ｗについて、Ｎ=２ｗを法とする剰余計算を行う場合、高速化が可能である。即ち、剰余計算を受ける数をｗビットの２進数として与えておけば、計算過程におけるｗビットの固定長処理、即ちｗビットを超えた桁溢れの無視が自動的にＮ=２ｗに関する剰余計算となる。
【００２６】
しかし、Ｎを上記のように２の冪乗とすると、問題が生じる場合がある。ＲＳＡ暗号方式はその定義によりΝは大きな素数２つの積（Ｎ＝ｐｑ，ｐ及びｑは２進数５００桁程度以上の素数）でなければならないので、そもそもＮを２の冪乗には出来ない。また、ＥｌＧａｍａｌ暗号方式の場合、Ｐｏｈｌｉｇ−Ｈｅｌｌｍａｎ法により離散対数問題が多項式時間で解けてしまうため、暗号としての安全性に欠ける。
【００２７】
また、チェビシェフ多項式の次数決定問題を利用する手法が考えられるが、この手法においても、剰余の法Νを２の冪乗とした場合には、上述したように、共通パラメータ（ｘとＮ）のひとつであるｘが偶数である場合に多項式時間で解けてしまうことが、非特許文献２に示されている。
【００２８】
そこで、本発明の目的は、上記の問題点、特に非特許文献２の問題点を鑑みたものであって、２羃剰余環上のチェビシェフ多項式に関する次数決定問題を解くことを困難とするようなパラメータを高速に生成するシステム、方法及びプログラムを提供することにある。
【００２９】
また、本発明の目的は、このパラメータを利用した鍵共有システム、公開鍵暗号システム、電子署名システム、送付鍵生成装置、第１の鍵共有装置、第２の鍵共有装置、暗号化装置、復号化装置、署名装置、認証装置、パラメータ生成方法、送付鍵生成方法、鍵共有方法、暗号化方法、復号化方法、鍵対生成方法、署名方法、認証方法及びこれらのプログラムを提供することにある。
【課題を解決するための手段】
【００３０】
本発明では、法Ｎを２ｗ（但し、ｗは３以上の整数）とした２冪剰余環Ｚ／ＮＺで考えられたｄ次のチェビシェフ多項式に関する次数決定問題のパラメータｘとして適切な奇数を選ぶことによって、上記課題を解決するものである。ここで、パラメータｘを奇数としたのは、上述したように、偶数の場合には２羃剰余環上のチェビシェフ多項式に関する次数決定問題を解けてしまうからである。
【００３１】
即ち、本発明のパラメータ生成装置は、２冪剰余環上でｄ次のチェビシェフ多項式Ｔｄ（ｘ）を考えることにより構成される次数決定問題を解くことを困難にするパラメータｘを生成する生成装置である。
【００３２】
但し、当該次数決定問題とは、パラメータＮとパラメータｘと（但し、ｘとＮは整数、０≦ｘ＜Ｎ）と整数ｙ（但し、０≦ｙ＜Ｎ）とから、ｙ＝Ｔｄ（ｘ）  ｍｏｄ  Ｎを満たす正の整数ｄを求める問題である。
【００３３】
ここで、剰余環Ｚ／ＮＺ上で考えるとは、整数及びその演算結果をすべてＮで割った余りで同一視して考えるという意味である。本明細書では、整数ＰをＱで割った正の余りを、２項演算子ｍｏｄにより、Ｐ
ｍｏｄ Ｑで表す。ｍｏｄの結合強度は四則演算や冪より弱いものとする。例えばＮ＝２５６の場合、剰余環Ｚ／ＮＺは２冪剰余環であり、０以上２５５以下の整数のみからなり、２５６は０と、また、２５７は１と置き換えられる。これを数式では、
２５６  ｍｏｄ  ２５６  ＝  ０
２５７  ｍｏｄ  ２５６  ＝  １
等と表現する。剰余環上では加算と乗算が定義される。例えば、
１００  ＋  ２００  ｍｏｄ  ２５６  ＝  ３００  ｍｏｄ  ２５６  ＝  ４４
３  ×  ２００  ｍｏｄ  ２５６  ＝  ６００  ｍｏｄ  ２５６  ＝  ８８
等となる。
【００３４】
２冪剰余環上でのチェビシェフ多項式の計算も全く同様であり、チェビシェフ多項式
Ｔ２（ｘ）＝２ｘ２−１
について、Ｎ＝２５６（＝２８）としたとき、例えばｘ＝３０に対し、
Ｔ２（３０）  ｍｏｄ  ２５６  ＝  ２×３０２−１ ｍｏｄ  ２５６  ＝  ２×９００−１  ｍｏｄ  ２５６  ＝  １８００−１  ｍｏｄ  ２５６  ＝  ７
となる。
【００３５】
なお上記の計算は、最後にｍｏｄ  ２５６としたが、計算途中においてｍｏｄ  ２５６を行っても計算結果は同じとなる。即ち、
２×３０２−１ ｍｏｄ  ２５６  ＝  ２×９００−１ ｍｏｄ  ２５６  ＝ ２×１３２−１
ｍｏｄ  ２５６  ＝  ２６４−１ ｍｏｄ  ２５６  ＝  ７
である。ここで９００  ｍｏｄ  ２５６＝１３２を用いた。
【００３６】
２冪剰余環において、すべての数をｗビットの固定長２進数として表現することが好ましい。何故なら、演算を行った結果がｗビット以内で納まる場合はもちろん問題ないが、結果がｗビットで納まらない場合、上位桁へ溢れる値を無視する事が２冪剰余環Ｚ／ＮＺ上で考える事と一致するからである。
【００３７】
これをもう少し詳しく説明する。例えばｗ＝８とし、すべての数は最大８ビットの２進数として表現するとする。このとき、上記の例と同じくＮ＝２５６なる。また、（＊＊…＊）２（ただし＊は０か１）で２進数を表現する。１００＝（１１００１００）２、２００＝（１１００１０００）２であり、
１００＋２００＝（１１００１００）２＋（１１００１０００）２＝（１００１０１１００）２
と９ビットの２進数となるが、この９ビット目を無視した２進数（００１０１１００）２は、１００＋２００  ｍｏｄ  ２５６の解である４４と等しい。これは２進数（１００００００００）２が２５６に等しく、ｍｏｄ  ２５６という演算、即ち２冪剰余環Ｚ／ＮＺの性質が２進数のある桁数以上を無視することと同値である、という事実の帰結である。
【００３８】
一般に、剰余環上における計算を行う場合、剰余を行う処理が最も計算時間がかかるが、本発明においては２羃剰余環に限定するので、ｗビットの２進数を用いることにより、剰余処理は実質的に何もしない事と等価となる。
【００３９】
更に、一般の２羃でない剰余環を用いて乗算を行う場合、一時的に桁数が増加するため、必要なビット数（扱う最大数を格納するために必要なビット数）の倍のビット数を準備する必要があるが、２羃剰余環の場合、各２項演算又は単項演算ごとに溢れた桁を無視する事により剰余処理が行われるため、桁数の一時的増加も考える必要がない。
【００４０】
このように２羃剰余環を用いる事は、コンピュータのハードウェア特性を活かし、かつ高速な剰余計算が実現される。このことは、通常の（２羃でない）剰余環上で行う計算に比べ、大幅な処理速度の向上が期待される。
【００４１】
本発明に係るパラメータ生成装置は、２冪剰余環Ｚ／ＮＺ上でチェビシェフ多項式Ｔを考えるときに、その次数決定問題を解くことを困難にするパラメータｘを生成する生成装置であって、パラメータＮ格納部と、第１の所定値格納部と、計算部と、出力部と、を有し、以下のように構成する。
【００４２】
パラメータＮ格納部は、次数決定問題のパラメータＮを格納する。ここでＮ＝２ｗであるから、必ずしもＮ自体の数値を格納するのではなく、代替的にｗの数値を格納することができる。即ち、パラメータＮは２ｗで定義されるのであり、２進数で処理される計算システムでは、ｗが決まれば計算長がｗビットに決まることになる。
【００４３】
第１の所定値格納部は、予め設定した第１の所定値を格納する。
【００４４】
計算部は、パラメータＮ格納部に格納されたパラメータＮと第１所定値格納部に格納された第１の所定値とを読み出して、
ｑ＝ｘ２−１  ｍｏｄ  Ｎ
で定義される整数ｑが因数４の個数を第１の所定値以上有するという第１の条件を満たすパラメータｘを計算して生成する。
【００４５】
このように計算されたパラメータｘは、ｑが偶数であり、パラメータＮも偶数であることから、必ず奇数となる。
【００４６】
ここで第１の条件は、非特許文献２で開示されている、２羃剰余環上のチェビシェフ多項式の次数決定問題を、Ｐｏｈｌｉｇ−Ｈｅｌｌｍａｎ法により多項式時間で解く方法の適用を困難とする条件である。即ち、Ｐｏｈｌｉｇ−Ｈｅｌｌｍａｎ法の適用には、２羃剰余環上でｘ２−１の平方根の計算が不可欠であるが、上記の整数ｑ＝ｘ２−１  ｍｏｄ  Ｎが因数４を多数持つ事によりｘ２−１の平方根に多数の分岐が生じ、現在のところ、計算に非常に長時間を必要とする。つまり、次数決定問題を解く事が困難となるのである。
【００４７】
上記の分岐が多数になるほど次数決定問題を解く事は困難となるため、第１の所定値は、出来る限り大きく設定する事が望ましい。但し、余り大きくしすぎると、計算部の処理時間が長くなるという状況や、場合によっては第１の条件を満たすパラメータｘが全く存在しないという状況も起こり得る。従って、パラメータＮに応じて適切な値を設定すればよい。
【００４８】
出力部は、計算部において生成されたパラメータｘを少なくとも出力する。ここで、「少なくとも」としたのは、出力部はパラメータｘを出力するが、それ以外の数値も出力するように構成することができるという趣旨である。
【００４９】
従って、出力部は、必要に応じて、パラメータＮも出力することができるように構成することができる。
【００５０】
また本発明のパラメータ生成装置は、予め設定した第２の所定値を格納する第２の所定値格納部を更に有し、計算部が更に以下の条件を満たすようなパラメータｘを生成する事が好ましい。
【００５１】
即ち、計算部は、パラメータＮ格納部に格納されたパラメータＮと第１所定値格納部に格納された第１の所定値と第２の所定値格納部に格納された第２の所定値とを読み出して、上記の第１の条件と、更に、次数が２ｅ−１であるチェビシェフ多項式Ｔ２ｅ−１（ｘ）について、ｘ＝Ｔ２ｅ−１（ｘ）  ｍｏｄ  Ｎを満たす２以上の最小の整数ｅが第２の所定値以上であるという第２の条件を満たすパラメータｘを計算して生成する。
【００５２】
ここで第２の所定値が大きいほど、２羃剰余環上のチェビシェフ多項式の次数決定問題は、総当たり法による攻撃に対する強度が上がる。総当たり法とは、既知のパラメータｘとパラメータＮから、
Ｔ１（ｘ）  ｍｏｄ  Ｎ
Ｔ２（ｘ）  ｍｏｄ  Ｎ
Ｔ３（ｘ）  ｍｏｄ  Ｎ
：
を逐次計算し、初めてｙ＝Ｔｄ（ｘ）  ｍｏｄ  Ｎとなるｄを次数決定問題の解として得る手法である。この解は、時間さえかければ必ず見付けることができる。次数ｄは、チェビシェフ多項式の周期性により、２ｅ−１以下にしかとれないので、ｅが小さい場合には、このような総当たり法により簡単に次数決定問題が解かれてしまうのである。
【００５３】
よって、第２の所定値も、出来る限り大きく設定する事が望ましい。但し、余り大きくしすぎると、計算部の処理時間が長くなるという状況や、場合によっては第２の条件を満たすパラメータｘが全く存在しないという状況も起こり得る。従って、パラメータＮに応じて適切な値を設定すればよい。
【００５４】
２羃剰余環上のチェビシェフ多項式において、３つの条件
（１）ｘ＝Ｔ２ｅ−１（ｘ）  ｍｏｄ  Ｎ
（２）１＝Ｔ２ｅ（ｘ）  ｍｏｄ  Ｎ
（３）ｘ＝Ｔ２ｅ＋１（ｘ）  ｍｏｄ  Ｎ
は互いに同値である。従って、上記の第２の条件「ｘ＝Ｔ２ｅ−１（ｘ）  ｍｏｄ  Ｎを満たす２以上の最小の整数ｅが第２の所定値以上である」は、「１＝Ｔ２ｅ（ｘ）  ｍｏｄ  Ｎを満たす２以上の最小の整数ｅが第２の所定値以上である」及び「ｘ＝Ｔ２ｅ+１（ｘ）  ｍｏｄ  Ｎを満たす２以上の最小の整数ｅが第２の所定値以上である」と同値である。つまり、このように第２の条件が書き換えられても、本発明の技術的範囲に含まれる。
【００５５】
本発明の他の観点に係るパラメータ生成方法は、コンピュータ又は専用計算装置で実行され、２冪剰余環Ｚ／ＮＺ（但し、Ｎ＝２Ｗ、ｗは３以上の整数）上でｄ次のチェビシェフ多項式Ｔｄ（ｘ）を考えることにより構成される次数決定問題を解くことを困難にするパラメータｘを生成する生成方法であって、読み出し工程と、計算工程と、出力工程と、を備え、以下のように構成する。
【００５６】
なお、方法の発明に関し、対応する装置と同様な数学的根拠の詳細な説明については省略する。
【００５７】
読み出し工程は、コンピュータ又は専用計算装置に格納されたパラメータＮと第１の所定値とを読み出す。
【００５８】
計算工程は、ｑ＝ｘ２−１  ｍｏｄ  Ｎで定義される整数ｑが因数４の個数を前記第１の所定値以上有するという第１の条件を満たすパラメータｘを計算して生成する。
【００５９】
このように計算されたパラメータｘは、上述したように、ｑが偶数であり、パラメータＮも偶数であることから、必ず奇数となる。また、第１の所定値は、出来る限り大きく設定されている事が望ましい。但し、余り大きくしすぎると、計算工程の処理時間が長くなるという状況や、場合によっては第１の条件を満たすパラメータｘが全く存在しないという状況も起こり得る。従って、パラメータＮに応じて適切な値を設定すればよい。
【００６０】
出力工程は、計算工程において生成された前記パラメータｘを少なくとも出力する。ここで、「少なくとも」としたのは、出力部はパラメータｘを出力するが、それ以外の数値も出力するように構成してもよいという趣旨である。
【００６１】
ここで出力工程は、必要に応じて、パラメータＮも出力することができるように構成することができる。
【００６２】
また本発明のパラメータ生成方法は、読み出し工程はコンピュータ又は専用計算装置に格納された第２の所定値を更に読み出し、計算工程が更に以下の条件を満たすようなパラメータｘを生成する事が好ましい。
【００６３】
即ち、計算工程は、第１の条件と、更に、ｘ＝Ｔ２ｅ−１（ｘ）  ｍｏｄ  Ｎを満たす２以上の最小の整数ｅが前記第２の所定値以上であるという第２の条件を満たすパラメータｘを計算して生成する。
【００６４】
ここにおいても、第２の所定値は、出来る限り大きく設定されている事が望ましい。但し、余り大きくしすぎると、計算工程の処理時間が長くなるという状況や、場合によっては第２の条件を満たすパラメータｘが全く存在しないという状況も起こり得る。従って、パラメータＮに応じて適切な値を設定すればよい。
【００６５】
上述のパラメータ生成装置、パラメータ生成方法において、生成されたパラメータｘは、２冪剰余環上で考えられたチェビシェフ多項式の次数決定問題を解くことを困難にするパラメータである。従って、この生成されたパラメータｘを、２冪剰余環を利用した鍵共有システムやその方法、公開鍵暗号システムやその方法、電子認証システムやその方法等に用いた場合には、システムや方法をプログラム化してコンピュータ等の計算機に実装することが容易にでき、かつ、解くことが困難なので外部からの攻撃に強く、システムや方法における演算の処理を高速にすることができる。
【００６６】
本発明の他の観点に係る鍵共有システムは、上記のパラメータ生成装置のいずれか又はパラメータ生成方法のいずれかによって生成されたパラメータｘと、パラメータＮを用いた鍵共有システムであって、送付鍵生成装置と、第１の鍵共有装置と、第２の鍵共有装置とを備え、以下のように構成する。
【００６７】
なお、ここで「上記のパラメータ生成装置のいずれか又はパラメータ生成方法のいずれかによって生成されたパラメータｘと、パラメータＮを用いた」としたのは、ここで用いられるパラメータｘは、あくまでも、上記のパラメータ生成装置のいずれか又はパラメータ生成方法のいずれかによって生成されたパラメータｘに限定する趣旨であり、パラメータＮは、この生成されたパラメータｘに対応するパラメータＮ、つまり、このパラメータｘを生成する際に用いたパラメータＮを意味する。以下の同様の記載においても、同様に解すべきである。
【００６８】
以下では、整数を取得する整数取得部又は整数取得工程について記載されるが、これは乱数を発生させる、日付と時刻のハッシュ関数値を用いる、等、動作の度に異なる整数値を発生させる装置又は工程によって構成することができる。
【００６９】
送付鍵生成装置は、整数取得部と、送付鍵計算部と、第１送付鍵出力部と、第２送付鍵出力部とを備え、以下のように構成する。
【００７０】
整数取得部は正の整数ｓを取得する。
【００７１】
送付鍵計算部は、パラメータｘとパラメータＮと取得した整数ｓとから
Ｔ＝Ｔｓ（ｘ）  ｍｏｄ  Ｎ
により送付鍵Ｔを計算する。
【００７２】
第１送付鍵出力部は、計算された送付鍵Ｔを第１の鍵共有装置に出力する。
【００７３】
第２送付鍵出力部は、整数ｓを送付鍵として第２の鍵共有装置に出力する。
【００７４】
また、第１の鍵共有装置は、整数取得部と、送付鍵計算部と、送付鍵出力部と、送付鍵入力部と、共有鍵計算部とを備え、以下のように構成する。
【００７５】
整数取得部は、正の整数ｔを取得する。
【００７６】
送付鍵計算部は、整数ｔとパラメータｘとパラメータＮとから
Ｕ＝Ｔｔ（ｘ）  ｍｏｄ  Ｎ
により送付鍵Ｕを計算する。
【００７７】
送付鍵出力部は、計算された送付鍵Ｕを第２の鍵共有装置に出力する。
【００７８】
送付鍵入力部は、送付鍵生成装置が出力した送付鍵Ｔを入力する。
【００７９】
共有鍵計算部は、入力された送付鍵Ｔから
Ｖ’＝Ｔｔ（Ｔ）  ｍｏｄ  Ｎ
により共有鍵Ｖ’を計算する。
【００８０】
さらに第２の鍵共有装置は、第１送付鍵入力部と、第２送付鍵入力部と、共有鍵計算部とを備え、以下のように構成する。
【００８１】
第１送付鍵入力部は、第１の鍵共有装置が出力した送付鍵Ｕを入力する。
【００８２】
第２送付鍵入力部は、送付鍵生成装置が送付鍵として出力した整数ｓを入力する。
【００８３】
共有鍵計算部は、パラメータＮと整数ｓと送付鍵Ｕとから
Ｖ＝Ｔｓ（Ｕ）  ｍｏｄ  Ｎ
により共有鍵Ｖを計算する。
【００８４】
ここで、チェビシェフ多項式の性質より、
Ｖ＝Ｔｓ（Ｔｔ（ｘ））  ｍｏｄ  Ｎ＝Ｔｓｔ（ｘ）ｍｏｄ  Ｎ
及び、
Ｖ’＝Ｔｔ（Ｔｓ（ｘ））  ｍｏｄ  Ｎ＝Ｔｓｔ（ｘ）  ｍｏｄ  Ｎ
となることから、Ｖ＝Ｖ’が成立する。即ち、Ｖ（＝Ｖ’）が共有鍵として、第１の鍵共有装置及び第２の鍵共有装置に共有される。
【００８５】
この鍵共有システムにおいて、送付鍵Ｔ、送付鍵Ｕ、パラメータｘ及びパラメータNのみから共有鍵Ｖを得る事は容易でない。なぜなら、Ｔ＝Ｔｓ（ｘ）  ｍｏｄ  Ｎ、Ｕ＝Ｔｔ（ｘ）  ｍｏｄ  Ｎに基づいて、整数ｓと整数ｔを求める次数決定問題は、パラメータｘの性質によって容易に解く事が出来ず、また共有鍵Ｖは整数ｓと整数ｔなしには計算出来ないからである。
【００８６】
またこの鍵共有システムは、２羃剰余環における演算を用いて構成されているため、２進数を用いた計算を行う装置を用いた場合、非常に高速に動作し、また作成も容易である。
【００８７】
なお、送付鍵生成装置の整数取得部で取得される整数ｓ、また、第１の鍵共有装置の整数取得部で取得される整数ｔは、奇数である事が望ましい。このとき、異なるパラメータｘに対し異なる送付鍵Ｕ及びＶが生成できる確率が高まる。
【００８８】
本発明の鍵共有システムは、以下のように構成することにより、公開鍵暗号システムとすることができる。
【００８９】
上記の通り、共有鍵Ｖと共有鍵Ｖ’は等しく、かつ、第三者は容易に得る事が出来ない。従って、この共有鍵Ｖ（＝Ｖ’）を対称鍵暗号方式の対称鍵として用いる事が出来る。
【００９０】
即ち、本第１の公開鍵暗号システムは、送付鍵生成装置と、第１の鍵共有装置と、第２の鍵共有装置を備え、以下のように構成する。
【００９１】
第１の鍵共有装置は、更に、暗号化部と暗号化メッセージ送信部とを備える。
【００９２】
暗号化部は、平文のメッセージを共有鍵Ｖ’により暗号化して暗号化メッセージを得る。
【００９３】
暗号化メッセージ送信部は、第２の鍵共有装置に暗号化メッセージを送信する。
【００９４】
第２の鍵共有装置は、更に、暗号化メッセージ受信部と復号化部とを備え、以下のように構成する。
【００９５】
暗号化メッセージ受信部は、第１の鍵共有装置が送信した暗号化メッセージを受信する。
【００９６】
復号化部は、受信された暗号化メッセージを共有鍵Ｖにより復号化して、平文のメッセージを得る。
【００９７】
本発明の他の観点に係る第２の公開鍵暗号システムは、上記のパラメータ生成装置のいずれか又はパラメータ生成方法のいずれかによって生成されたパラメータｘと、パラメータＮとを用いた公開鍵暗号システムであって、鍵対生成装置と、暗号化装置と、復号化装置とを備え、以下のように構成する。
【００９８】
鍵対生成装置は、整数取得部と、公開鍵計算部と、公開鍵公開部と、秘密鍵出力部と、を備え、以下のように構成する。
【００９９】
整数取得部は、正の奇数である整数ｓを取得する。
【０１００】
公開鍵計算部は、取得した整数ｓとパラメータｘとパラメータＮとから、
Ｔ＝Ｔｓ（ｘ）  ｍｏｄ  Ｎ    
により公開鍵Ｔを計算する。
【０１０１】
公開鍵公開部は、計算された公開鍵Ｔを暗号化装置に公開する。
【０１０２】
秘密鍵出力部は、整数ｓを秘密鍵として復号化装置に出力する。
【０１０３】
また暗号化装置は、公開鍵受付部と、整数取得部と、暗号化部と、暗号化メッセージ送信部と、を備え、以下のように構成する。
【０１０４】
公開鍵受付部は、鍵対生成装置が公開した公開鍵Ｔを受け付ける。
【０１０５】
整数取得部は、正の奇数である整数ｒを取得する。
【０１０６】
暗号化部は、奇数であるメッセージｍ（０＜ｍ＜Ｎ）と取得した整数ｒとパラメータｘとパラメータＮとから、
ｃ１＝Ｔｒ（ｘ）  ｍｏｄ  Ｎ
ｃ２＝ｍＴｒ（Ｔ）  ｍｏｄ  Ｎ
により整数の組である暗号化メッセージ（ｃ１，ｃ２）を計算する。
【０１０７】
暗号化メッセージ送信部は、暗号化メッセージ（ｃ１，ｃ２）を復号化装置へ送信する。
【０１０８】
一方、復号化装置は、暗号化メッセージ受信部と、秘密鍵入力部と、中間整数計算部と、復号化部と、を備え、以下のように構成する。
【０１０９】
暗号化メッセージ受信部は、暗号化装置が送信した暗号化メッセージ（ｃ１，ｃ２）を受信する。
【０１１０】
秘密鍵入力部は、鍵対生成装置が秘密鍵として出力した整数ｓを入力する。
【０１１１】
中間整数計算部は、入力された整数ｓと受信された暗号化メッセージ（ｃ１，ｃ２）の第１成分ｃ１とパラメータＮとから、
１＝αＴｓ（ｃ１）  ｍｏｄ  Ｎ
を満たす中間整数αを求める。
【０１１２】
ここで、パラメータｘ、整数ｓ、整数ｔがいずれも奇数であることから、
Ｔｓ（ｃ１）＝Ｔｓ（Ｔｒ（ｘ））ｍｏｄ  Ｎ
も奇数となり、この中間整数αは必ず存在し、拡張ユークリッドの互除法やフェルマーの小定理よる適当な冪乗を用いれば高速に計算することができる。
【０１１３】
復号化部は、受信された暗号化メッセージ（ｃ１，ｃ２）の第２成分ｃ２と中間整数αとパラメータＮとから
ｍ’＝αｃ２  ｍｏｄ  Ｎ
によりメッセージｍ’を得る。
【０１１４】
このメッセージｍ’は、暗号化装置が送信した元のメッセージｍと等しい。
【０１１５】
本第２の公開鍵暗号システムにおいて、公開鍵Ｔ、パラメータｘ及びパラメータＮのみを用いて暗号化メッセージ（ｃ１，ｃ２）から元のメッセージｍを得る事は容易でない。なぜなら、復号化においてＴｓ（ｃ１）を計算する必要があり、この秘密鍵ｓは次数決定問題の困難性により容易に計算できないからである。
【０１１６】
また本第２の公開鍵暗号システムは、すべての計算を２羃剰余環上で行うため、２進数を用いた計算を行う装置を用いた場合、非常に高速に動作し、また作成も容易である。
【０１１７】
本発明の他の観点に係る第３の公開鍵暗号システムは、上記のパラメータ生成装置のいずれか又はパラメータ生成方法のいずれかによって生成されたパラメータｘと、パラメータＮとを用いた公開鍵暗号システムであって、鍵対生成装置と暗号化装置と復号化装置とを備え、以下のように構成する。
【０１１８】
鍵対生成装置は、整数取得部と、公開鍵計算部と、公開鍵公開部と、秘密鍵出力部と、を備え、以下のように構成する。
【０１１９】
整数取得部は、正の整数ｓを取得する。
【０１２０】
公開鍵計算部は、整数ｓとパラメータｘとパラメータＮとから、
Ｔ＝Ｔｓ（ｘ）  ｍｏｄ  Ｎ
により公開鍵Ｔを計算する。
【０１２１】
公開鍵公開部は、計算された公開鍵Ｔを暗号化装置に公開する。
【０１２２】
秘密鍵出力部は、整数ｓを秘密鍵として復号化装置に出力する。
【０１２３】
一方、暗号化装置は、公開鍵受付部と、整数取得部と、暗号化部と、暗号化メッセージ送信部と、を備え、以下のように構成する。
【０１２４】
公開鍵受付部は、鍵対生成装置が公開した公開鍵Ｔを受け付ける。
【０１２５】
整数取得部は、正の整数ｒを取得する。
【０１２６】
暗号化部は、整数であるメッセージｍ（０≦ｍ＜Ｎ）と整数ｒとパラメータｘとパラメータＮとから
ｃ１＝Ｔｒ（ｘ）  ｍｏｄ  Ｎ
ｃ２＝（Ｔｒ（Ｔ）  ｍｏｄ  Ｎ）  ｘｏｒ  ｍ
により整数の組である暗号化メッセージ（ｃ１，ｃ２）を計算する。
【０１２７】
但し、Ａ  ｘｏｒ  Ｂは、２進数ＡとＢのビット毎の排他的論理和演算を表わす。例えば、Ａ＝０１１００１０１，Ｂ＝１０１１０１１０である時、Ａ  ｘｏｒ  Ｂ＝１１０１００１１となる。
【０１２８】
暗号化メッセージ送信部は、暗号化メッセージ（ｃ１，ｃ２）を復号化装置へ送信する。
【０１２９】
更に復号化装置は、暗号化メッセージ受信部と、秘密鍵入力部と、復号化部と、を備え、以下のように構成する。
【０１３０】
暗号化メッセージ受信部は、暗号化装置が送信した暗号化メッセージ（ｃ１，ｃ２）を受信する。
【０１３１】
秘密鍵入力部は、鍵対生成装置が秘密鍵として出力した整数ｓを入力する。
【０１３２】
復号化部は、入力された整数ｓと受信された暗号化メッセージ（ｃ１，ｃ２）とパラメータＮとから
ｍ’＝（Ｔｓ（ｃ１）  ｍｏｄ  Ｎ）  ｘｏｒ  ｃ２
によりメッセージｍ’を得る。
【０１３３】
このメッセージｍ’は、暗号化装置の送信したメッセージｍに等しい。
【０１３４】
本第３の公開鍵暗号システムにおいて、公開鍵Ｔ、パラメータｘ及びパラメータＮのみを用いて暗号化メッセージ（ｃ１，ｃ２）から元のメッセージｍを得る事は容易でない。なぜなら、復号化においてＴｓ（ｃ１）を計算する必要があり、この秘密鍵ｓは次数決定問題の困難性により容易に計算できないからである。
【０１３５】
また本第３の公開鍵暗号システムは、すべての計算を２羃剰余環上で行うため、２進数を用いた計算を行う装置を用いた場合、非常に高速に動作し、また作成も容易である。
【０１３６】
鍵対生成装置の整数取得部で取得される整数ｓ、また、暗号化装置の生成取得部で取得される整数ｒは奇数であることが望ましい。このとき、非特許文献１において初めて示されたように、２羃剰余環上でチェビシェフ多項式Ｔｓ及びＴｒが全単射となるためである。ただし両者が奇数の場合、２羃剰余環上でＴｒ（Ｔ）＝Ｔｓ（ｃ１）も奇数となるため、最下位ビットを解読されてしまう。これを避けるには、メッセージｍの最下位ビットには情報を与えず定数（０でも１でもよい）とし、復号化されたメッセージｍ’の最下位ビットを無視すればよい。
【０１３７】
本発明の他の観点に係る電子署名システムは、上記のパラメータ生成装置のいずれか又はパラメータ生成方法のいずれかによって生成されたパラメータｘと、パラメータＮとを用いた電子署名システムであって、鍵対生成装置と、署名装置と、認証装置とを備え、以下のように構成する。
【０１３８】
鍵対生成装置は、整数取得部と、公開鍵計算部と、公開鍵公開部と、秘密鍵出力部と、を備え、以下のように構成する。
【０１３９】
整数取得部は、正の整数ｓを取得する。
【０１４０】
公開鍵計算部は、整数ｓとパラメータｘとパラメータＮとから、
Ｔ＝Ｔｓ（ｘ）  ｍｏｄ  Ｎ
により公開鍵Ｔを計算する。
【０１４１】
公開鍵公開部は、計算された公開鍵Ｔを認証装置に公開する。
【０１４２】
秘密鍵出力部は、整数ｓを秘密鍵として署名装置に出力する。
【０１４３】
一方、署名装置は、整数発生部と、秘密鍵入力部と、署名部と、署名付メッセージ送信部と、を備え、以下のように構成する。
【０１４４】
整数発生部は、整数Ｍを２ｅの倍数であってＮ以下のものとし、Ｍと互いに素な正の整数ｋと、整数ｋから１
＝ ｋ’ｋ  ｍｏｄ Ｍを満たす正の整数ｋ’を発生させる。但し、ｅは、ｘ＝Ｔ２ｅ−１（ｘ）  ｍｏｄ  Ｎを満たす２以上の最小の整数とする。整数Ｍと整数ｋが互いに素であるため、この正の整数ｋ’は必ず存在し、拡張ユークリッドの互除法等を用いる事により高速に計算できる。
【０１４５】
秘密鍵入力部は、鍵対生成装置が秘密鍵として出力した整数ｓを入力する。
【０１４６】
署名部は、パラメータｘとパラメータＮと整数ｓと整数であるメッセージｍ（０≦ｍ＜Ｎ）とから、
ａ＝Ｔｋ（ｘ）  ｍｏｄ  Ｎ
ｂ＝ｋ’（ｓａ＋ｈ（ｍ））  ｍｏｄ  Ｍ
により署名付メッセージ（ａ，ｂ，ｍ）を計算する。但し、ｈ（ｍ）は正の整数であって、メッセージｍ自身又はメッセージｍのハッシュ関数値とする。
【０１４７】
メッセージｍは、Ｍ以上の値となっても構わない。但し、０≦ｍ＜Ｍである方が異なるメッセージを同じであると認証する確率が減って望ましい。
【０１４８】
ここで関数ｈを恒等関数にとれば整数ｈ（ｍ）はメッセージｍ自身となる。そして、関数ｈをハッシュ関数にとれば、整数ｈ（ｍ）として、ｍのハッシュ値を用いることになる。存在的偽造不可能性に関する安全性を高めることができると期待されるため、ｈとしてはハッシュ関数を用いる事が望ましい。
【０１４９】
なお、ハッシュ関数ｈは、パラメータに依存するハッシュ関数を用いるのが更に望ましい。このことにより、存在的偽造不可能性に関する安全性を更に高めることができると期待される。このためには、署名装置の署名部で計算されたａを用い、ハッシュ関数ｈをパラメータ付きハッシュ関数ｈａに置き換えればよい。
【０１５０】
署名付メッセージ送信部は、署名付メッセージ（ａ，ｂ，ｍ）を認証装置へ送信する。
【０１５１】
なお、この署名装置の整数発生部におけるＭは、必ずしも２ｅを使用して設定する必要はない。例えばＭ＝Ｎ／４とすることができる（ｅは常にｗ−２以下となる）。但し、計算時間の短縮のために、Ｍは小さい方が望ましい。
【０１５２】
またＭを２ｅを利用して設定する場合で、かつ、パラメータ生成装置がｅをｘ＝Ｔ２ｅ−１（ｘ）  ｍｏｄ  Ｎを満たす２以上の最小の整数として発生させているとき又はパラメータ生成方法によりｅがｘ＝Ｔ２ｅ−１（ｘ）  ｍｏｄ  Ｎを満たす２以上の最小の整数として発生させられているときは、そのｅを受け付け利用する事により、更に計算を高速化することができる。
【０１５３】
またＭは、２の冪乗にとるのが望ましい。これは、署名装置として、２進数を用いた計算を行う装置を用いた場合、非常に高速に動作し、また作成も容易となるからである。
【０１５４】
更に、Ｍが２の冪乗である場合、整数ｋは単に正の奇数として選ぶことができる。
【０１５５】
上記整数ｋ’は、拡張ユークリッドの互除法以外でも、フェルマーの小定理により、ある整数ｃを用いて、ｋ’＝ｋｃ  ｍｏｄ  Ｍで高速に求めることができる。
【０１５６】
また認証装置は、公開鍵受付部と、署名付メッセージ受信部と、整数計算部と、認証部と、を備え、以下のように構成する。
【０１５７】
公開鍵受付部は、鍵対生成装置が公開した公開鍵Ｔを受け付ける。
【０１５８】
署名付メッセージ受信部は、署名装置が送信した署名付メッセージ（ａ，ｂ，ｍ）を受信する。
【０１５９】
整数計算部は、受け付けられた公開鍵Ｔと受信された署名付メッセージ（ａ，ｂ，ｍ）とパラメータｘとパラメータＮから、整数ｈ（ｍ）を設定し、整数Ｗを、
Ｗ＝Ｔｈ（ｍ）（ｘ）２−２Ｔｈ（ｍ）（ｘ）Ｔａ（Ｔ）Ｔｂ（ａ）＋Ｔａ（Ｔ）２＋Ｔｂ（ａ）２−１  ｍｏｄ  Ｎにより計算する。
【０１６０】
認証部は、整数Ｗが０に等しい場合、署名付メッセージ（ａ，ｂ，ｍ）を認証する。
【０１６１】
本署名システムにおいて、公開鍵Ｔ、パラメータｘ及びパラメータＮのみを用いて秘密鍵である整数ｓを計算することは困難である。このため署名付メッセージ（ａ，ｂ，ｍ）の第２成分ｂは秘密鍵である整数ｓを知っている署名装置によってしか作成できない。
【０１６２】
本発明の他の観点に係る送付鍵生成装置は、上記の鍵共有システムの送付鍵生成装置である。
【０１６３】
本発明の他の観点に係る第１の鍵共有装置は、上記の鍵共有システムの第１の鍵共有装置である。
【０１６４】
本発明の他の観点に係る第２の鍵共有装置は、上記の鍵共有システムの第２の鍵共有装置である。
【０１６５】
本発明の他の観点に係る第１の鍵共有装置は、上記の第１の公開鍵暗号システムの第１の鍵共有装置である。
【０１６６】
本発明の他の観点に係る第２の鍵共有装置は、上記の第１の公開鍵暗号システムの第２の鍵共有装置である。
【０１６７】
本発明の他の観点に係る暗号化装置は、上記の第２の公開鍵暗号システムの暗号化装置である。
【０１６８】
本発明の他の観点に係る復号化装置は、上記の第２の公開鍵暗号システムの復号化装置である。
【０１６９】
本発明の他の観点に係る署名装置は、上記の電子署名システムの署名装置である。
【０１７０】
本発明の他の観点に係る認証装置は、上記の電子署名システムの認証装置である。
【０１７１】
本発明の他の観点に係る送付鍵生成方法は、コンピュータ又は専用計算装置で実行される、上記のパラメータ生成装置のいずれか又は上記のパラメータ生成方法のいずれかによって生成されたパラメータｘと、パラメータＮとを用いて共有鍵を生成するのに必要な送付鍵Ｔを生成する方法であって、整数取得工程と、送付鍵計算工程と、を備え、以下のように構成する。
【０１７２】
整数取得工程は、正の整数ｓを取得する。
【０１７３】
送付鍵計算工程は、パラメータｘとパラメータＮと取得した整数ｓとから、
Ｔ＝Ｔｓ（ｘ）  ｍｏｄ  Ｎ
により送付鍵Ｔを計算する。
【０１７４】
本送付鍵生成方法は、２進数を用いて計算を行った場合、非常に高速に動作し、また、プログラム化も容易である。
【０１７５】
本発明の他の観点に係る第１の鍵共有方法は、コンピュータ又は専用計算装置で実行される、上記のパラメータ生成装置のいずれか又は上記のパラメータ生成方法のいずれかによって生成されたパラメータｘと、パラメータＮとを用いた鍵共有方法であって、整数取得工程と、送付鍵計算工程と、送付鍵出力工程と、送付鍵入力工程と、共有鍵計算工程と、を備え、以下のように構成する。
【０１７６】
整数取得工程は、正の整数ｔを取得する。
【０１７７】
送付鍵計算工程は、整数ｔとパラメータｘとパラメータＮとから、
Ｕ＝Ｔｔ（ｘ）  ｍｏｄ  Ｎ
により送付鍵Ｕを計算する。
【０１７８】
送付鍵出力工程は、計算された送付鍵Ｕを他の鍵共有装置に出力する。
【０１７９】
送付鍵入力工程は、上記の送付鍵生成方法において生成され送付鍵Ｔを入力する。
【０１８０】
共有鍵計算工程は、入力された送付鍵Ｔから
Ｖ’＝Ｔｔ（Ｔ）  ｍｏｄ  Ｎ
により共有鍵Ｖ’を計算する。
【０１８１】
本第１の鍵共有方法は、２進数を用いて計算を行った場合、非常に高速に動作し、プログラム化も容易である。
【０１８２】
本発明の他の観点に係る第２の鍵共有方法は、コンピュータ又は専用計算装置で実行される、上記のパラメータ生成装置のいずれか又は上記のパラメータ生成方法のいずれかによって生成されたパラメータｘに対応したパラメータＮを用いた鍵共有方法であって、第１送付鍵入力工程と、第２送付鍵入力工程と、共有鍵計算工程と、を備え、以下のように構成する。
【０１８３】
なお、ここでいう「パラメータｘに対応したパラメータＮ」とは、生成されたパラメータｘを対応するパラメータＮ、つまり、パラメータｘを生成する際に用いたパラメータＮをいう。以下においても同様である。
【０１８４】
第１送付鍵入力工程は、上記の第１の鍵共有方法において計算され送付鍵Ｕを入力する。
【０１８５】
第２送付鍵入力工程は、上記の送付鍵生成方法において取得され整数ｓを送付鍵として入力する。
【０１８６】
共有鍵計算工程は、パラメータＮと整数ｓと送付鍵Ｕとから、
Ｖ＝Ｔｓ（Ｕ）  ｍｏｄ  Ｎ
により共有鍵Ｖを計算する。
【０１８７】
ここで、チェビシェフ多項式の性質より、Ｖ＝Ｖ’が成立する。即ち、Ｖ（＝Ｖ’）が共有鍵として作成される。
【０１８８】
本第２の鍵共有方法は、２進数を用いて計算を行った場合、非常に高速に動作し、プログラム化も容易である。
【０１８９】
上記の第１の鍵共有方法と本第２の鍵共有方法を組み合わせて実施した場合において、送付鍵Ｔ、送付鍵Ｕ、パラメータｘ及びパラメータＮのみから共有鍵Ｖ（＝Ｖ’）を得る事は容易でない。
【０１９０】
なお、上記の送付鍵生成方法の整数取得工程で取得される整数ｓ、また、第１の鍵共有方法の整数取得工程で取得される整数ｔは、奇数である事が望ましい。
【０１９１】
本発明の他の観点に係る第１の暗号化方法は、上記の第１の鍵共有方法を用いた暗号化方法であって、更に、平文のメッセージを共有鍵Ｖ’により暗号化して暗号化メッセージを得る暗号化工程を有することを特徴とする。
【０１９２】
本発明の他の観点に係る第１の復号化方法は、上記の第２の鍵共有方法を用いた復号化方法であって、更に、上記の第１の暗号化方法により暗号化された暗号化メッセージを共有鍵Ｖにより復号化して、上記の第１の暗号化方法で用いられた平文のメッセージを得る復号化工程を有することを特徴とする。
【０１９３】
本発明の他の観点に係る鍵対生成方法は、コンピュータ又は専用計算装置で実行される、上記のパラメータ生成装置のいずれか又は上記のパラメータ生成方法のいずれかによって生成されたパラメータｘと、パラメータＮとを用いた鍵対生成方法であって、整数取得工程と、公開鍵計算工程と、公開鍵公開工程と、秘密鍵出力工程と、を備え、以下のように構成する。
【０１９４】
整数取得工程は、正の整数ｓを取得する。
【０１９５】
公開鍵計算工程は、取得した整数ｓとパラメータｘとパラメータＮとから、
Ｔ＝Ｔｓ（ｘ）  ｍｏｄ  Ｎ    
により公開鍵Ｔを計算する。
【０１９６】
公開鍵公開工程は、計算された公開鍵Ｔを公開する。
【０１９７】
秘密鍵出力工程は、整数ｓを秘密鍵として出力する。
【０１９８】
本鍵対生成方法は、２進数を用いて計算を行った場合、非常に高速に動作し、またプログラム化も容易である。
【０１９９】
本発明の他の観点に係る第２の暗号化方法は、コンピュータ又は専用計算装置で実行される、上記のパラメータ生成装置のいずれか又は上記のパラメータ生成方法のいずれかによって生成されたパラメータｘと、パラメータＮとを用いた暗号化方法であって、公開鍵受付工程と、整数取得工程と、暗号化工程と、を備え、以下のように構成する。
【０２００】
公開鍵受付工程は、上記の鍵対生成方法で整数ｓを奇数としたものにおいて公開された公開鍵Ｔを受け付ける。
【０２０１】
整数取得工程は、正の奇数である整数ｒを取得する。
【０２０２】
暗号化工程は、奇数であるメッセージｍ（０＜ｍ＜Ｎ）と取得した前記整数ｒと前記パラメータｘと前記パラメータＮとから、
ｃ１＝Ｔｒ（ｘ）  ｍｏｄ  Ｎ
ｃ２＝ｍＴｒ（Ｔ）  ｍｏｄ  Ｎ
により整数の組である暗号化メッセージ（ｃ１，ｃ２）を計算する。
【０２０３】
本第２の暗号化方法は、２進数を用いて計算を行った場合、非常に高速に動作し、またプログラム化も容易である。
【０２０４】
本発明の他の観点に係る第２の復号化方法は、コンピュータ又は専用計算装置で実行される、上記のパラメータ生成装置のいずれか又は上記のパラメータ生成方法のいずれかによって生成されたパラメータｘに対応したパラメータＮを用いた復号化方法であって、暗号化メッセージ受信工程と、秘密鍵入力工程と、中間整数計算工程と、復号化工程と、を備え、以下のように構成する。
【０２０５】
暗号化メッセージ受信工程は、上記の第１の暗号化方法において計算された暗号化メッセージ（ｃ１，ｃ２）を受信する。
【０２０６】
秘密鍵入力工程は、上記の鍵対生成方法整数ｓを奇数としたものにおいて秘密鍵として出力された整数ｓを入力する。
【０２０７】
中間整数計算工程は、入力された整数ｓと受信された暗号化メッセージ（ｃ１，ｃ２）の第１成分ｃ１とパラメータＮとから、
１＝αＴｓ（ｃ１）  ｍｏｄ  Ｎ
を満たす中間整数αを求める。
【０２０８】
復号化工程は、受信された暗号化メッセージ（ｃ１，ｃ２）の第２成分ｃ２と中間整数αとパラメータＮとから
ｍ’＝αｃ２  ｍｏｄ  Ｎ
によりメッセージｍ’を得る。
【０２０９】
このメッセージｍ’は、上記の第２の暗号化装置の送信したメッセージｍに等しい。
【０２１０】
上記の第２の暗号化方法と本第２の復号化方法を組み合わせて実施した場合において、公開鍵Ｔ、パラメータｘ及びパラメータＮのみを用いて暗号化メッセージ（ｃ１，ｃ２）から元のメッセージｍを得る事は容易でない。
【０２１１】
また、本第２の復号化方法は、２進数を用いて計算を行った場合、非常に高速に動作し、またプログラム化も容易である。
【０２１２】
本発明に係る第３の暗号化方法は、コンピュータ又は専用計算装置で実行される、上記のパラメータ生成装置のいずれか又は上記のパラメータ生成方法のいずれかによって生成されたパラメータｘと、パラメータＮとを用いた暗号化方法であって、公開鍵受付工程と、整数取得工程と、暗号化工程と、を備え、以下のように構成する。
【０２１３】
公開鍵受付工程は、上記の鍵対生成方法において公開された公開鍵Ｔを受け付ける。
【０２１４】
整数取得工程は、正の整数ｒを取得する。
【０２１５】
暗号化工程は、整数であるメッセージｍ（０≦ｍ＜Ｎ）と整数ｒとパラメータｘとパラメータＮとから
ｃ１＝Ｔｒ（ｘ）  ｍｏｄ  Ｎ
ｃ２＝（Ｔｒ（Ｔ）  ｍｏｄ  Ｎ） ｘｏｒ ｍ
により整数の組である暗号化メッセージ（ｃ１，ｃ２）を計算する。
【０２１６】
本第３の暗号化方法は、２進数を用いて計算を行った場合、非常に高速に動作し、またプログラム化も容易である。
【０２１７】
本発明の他の観点に係る第３の復号化方法は、コンピュータ又は専用計算装置で実行される、上記のパラメータ生成装置のいずれか又は上記のパラメータ生成方法のいずれかによって生成されたパラメータｘに対応したパラメータＮとを用いた復号化方法であって、暗号化メッセージ受信工程と、秘密鍵入力工程と、復号化工程と、を備え、以下のように構成する。
【０２１８】
暗号化メッセージ受信工程は、上記の第３の暗号化方法において計算され暗号化メッセージ（ｃ１，ｃ２）を受信する。
【０２１９】
秘密鍵入力工程は、上記の鍵対生成方法において秘密鍵として出力され整数ｓを入力する。
【０２２０】
復号化工程は、入力された整数ｓと受信された暗号化メッセージ（ｃ１，ｃ２）とパラメータＮとから、
ｍ’＝（Ｔｓ（ｃ１）  ｍｏｄ  Ｎ）  ｘｏｒ  ｃ２
によりメッセージｍ’を得る。
【０２２１】
このメッセージｍ’は、上記の第３の暗号化方法の送信したメッセージｍに等しい。
【０２２２】
上記の第３の暗号化方法と本第３の復号化方法を組み合わせて実施した場合において、公開鍵Ｔ、パラメータｘ及びパラメータＮのみを用いて暗号化メッセージ（ｃ１，ｃ２）から元のメッセージｍを得る事は容易でない。
【０２２３】
また、本第３の復号化方法は、２進数を用いて計算を行った場合、非常に高速に動作し、またプログラム化も容易である。
【０２２４】
鍵対生成方法の整数取得工程で取得される整数ｓ、また、暗号化方法の整数取得工程で取得される整数ｒは奇数であることが望ましい。このときは、メッセージｍの最下位ビットには情報を与えず定数（０でも１でもよい）とし、復号化されたメッセージｍ’の最下位ビットを無視することが望ましい。
【０２２５】
本発明の他の観点に係る署名方法は、コンピュータ又は専用計算装置で実行される、上記のパラメータ生成装置のいずれか又は上記のパラメータ生成方法のいずれかによって生成されたパラメータｘと、パラメータＮとを用いた署名方法であって、整数発生工程と、秘密鍵入力工程と、署名工程と、を備え、以下のように構成する。
【０２２６】
整数発生工程は、整数Ｍを２ｅの倍数であってＮ以下のものとし、Ｍと互いに素な正の整数ｋと、前記整数ｋから１
＝ ｋ’ｋ  ｍｏｄ Ｍを満たす正の整数ｋ’を発生させる。但しｅは、ｘ＝Ｔ２ｅ−１（ｘ）  ｍｏｄ  Ｎを満たす２以上の最小の整数である。整数Ｍと整数ｋが互いに素であるため、この正の整数ｋ’は必ず存在し、拡張ユークリッドの互除法等を用いる事により高速に計算できる。
【０２２７】
秘密鍵入力工程は、上記の鍵対生成方法において秘密鍵として出力された整数ｓを入力する。
【０２２８】
署名工程は、パラメータｘとパラメータＮと整数ｓと整数であるメッセージｍ（０≦ｍ＜Ｎ）とから、
ａ＝Ｔｋ（ｘ）  ｍｏｄ  Ｎ
ｂ＝ｋ’(ｓａ＋ｈ（ｍ）)  ｍｏｄ  Ｍ
により署名付メッセージ（ａ，ｂ，ｍ）を計算する。但し、ｈ（ｍ）は正の整数であって、ｍ自身又はｍのハッシュ関数値とする。
【０２２９】
メッセージｍは、Ｍ以上の値となっても構わない。但し、０≦ｍ＜Ｍである方が異なるメッセージを同じであると認証する確率が減って望ましい。
【０２３０】
ここで関数ｈを恒等関数にとれば整数ｈ（ｍ）はメッセージｍ自身となる。そして、関数ｈをハッシュ関数にとれば、整数ｈ（ｍ）として、ｍのハッシュ値を用いることになる。存在的偽造不可能性に関する安全性を高めることができると期待されるため、ｈとしてはハッシュ関数を用いる事が望ましい。
【０２３１】
なお、ハッシュ関数ｈは、パラメータに依存するハッシュ関数を用いるのが更に望ましい。このことにより、存在的偽造不可能性に関する安全性を更に高めることができると期待される。このためには、上記の署名工程で計算されたａを用い、ハッシュ関数ｈをパラメータ付きハッシュ関数ｈａに置き換えればよい。
【０２３２】
なお、整数発生工程におけるＭは、必ずしも２ｅを使用して設定する必要はない。例えばＭ＝Ｎ／４とすることができる。ただし計算時間の短縮のために、Ｍは小さい方が望ましい。
【０２３３】
またＭを２ｅを利用して設定する場合で、かつ、パラメータ生成装置がｅをｘ＝Ｔ２ｅ−１（ｘ）  ｍｏｄ  Ｎを満たす２以上の最小の整数として発生させているとき又はパラメータ生成方法によりｅがｘ＝Ｔ２ｅ−１（ｘ）  ｍｏｄ  Ｎを満たす２以上の最小の整数として発生させられているときは、そのｅを受け付け利用する事により、更に計算を高速化することができる。
【０２３４】
またＭは、２の冪乗にとるのが望ましい。２進数を用いて計算を行った場合、非常に高速に動作し、またプログラム化も容易となるからである。
【０２３５】
更に、Ｍが２の冪乗である場合、整数ｋは単に正の奇数として選ぶことができる。
【０２３６】
上記整数ｋ’は、拡張ユークリッドの互除法以外でも、フェルマーの小定理により、ある整数ｃを用いて、ｋ’＝ｋｃ  ｍｏｄ  Ｍで高速に求めることができる。
【０２３７】
本発明の他の観点に係る認証方法は、コンピュータ又は専用計算装置で実行される、上記のパラメータ生成装置のいずれか又は上記のパラメータ生成方法のいずれかによって生成されたパラメータｘと、パラメータＮとを用いた認証方法であって、公開鍵受付工程と、署名付メッセージ受信工程と、整数計算工程と，認証工程と、を備え、以下のように構成する。
【０２３８】
公開鍵受付工程は、上記の鍵対生成方法において公開された公開鍵Ｔを受け付ける。
【０２３９】
署名付メッセージ受信工程は、上記の署名方法において計算された署名付メッセージ（ａ，ｂ，ｍ）を受信する。
【０２４０】
整数計算工程は、受け付けられた公開鍵Ｔと受信された署名付メッセージ（ａ，ｂ，ｍ）とパラメータｘとパラメータＮから、整数ｈ（ｍ）を設定し整数Ｗを
Ｗ＝Ｔｈ（ｍ）（ｘ）２−２Ｔｈ（ｍ）（ｘ）Ｔａ（Ｔ）Ｔｂ（ａ）＋Ｔａ（Ｔ）２＋Ｔｂ（ａ）２−１  ｍｏｄ  Ｎ
により計算する。
【０２４１】
認証工程は、整数Ｗが０に等しい場合、前記署名付メッセージ（ａ，ｂ，ｍ）を認証する。
【０２４２】
上記署名方法と本認証方法を組み合わせて実施した場合において、署名付メッセージ（ａ，ｂ，ｍ）の第２成分ｂは秘密鍵である整数ｓを知っている署名方法によってしか作成できない。
【０２４３】
本発明の他の観点に係るプログラムは、コンピュータを、上記のパラメータ生成装置のいずれか、上記の鍵共有システムの送付鍵生成装置、上記の鍵共有システムの第１の鍵共有装置、上記の鍵共有システムの第２の鍵共有装置、上記の第１の公開鍵暗号システムの第１の鍵共有装置、上記の第１の公開鍵暗号システムの第２の鍵共有装置、上記の公開鍵暗号システムのいずれかの鍵対生成装置、上記の公開鍵暗号システムのいずれかの暗号化装置、上記の公開鍵暗号システムのいずれかの復号化装置、上記の電子署名システムの鍵対生成装置、上記の電子署名システムの署名装置、上記の電子署名システムの認証装置のいずれか少なくとも１つとして機能させ、又は、コンピュータに、上記のパラメータ生成方法、上記の送付鍵生成方法、上記いずれかの鍵共有方法、上記いずれかの暗号化方法、
上記いずれかの復号化方法、上記の鍵対生成方法、上記の署名方法、上記の認証方法のいずれか少なくとも１つを実行させるように構成する。
【０２４４】
なお、上記プログラムは、コンパクトディスク、フレキシブルディスク、ハードディスク、光磁気ディスク、ディジタルビデオディスク、磁気テープ、半導体メモリ等のコンピュータ読取可能な情報記憶媒体に記録することができる。また、上記プログラムは、プログラムが実行されるコンピュータやディジタル信号プロセッサとは独立して、コンピュータ通信網を介して配布・販売することができる。また、上記情報記憶媒体は、コンピュータやディジタル信号プロセッサとは独立して配布・販売することができる。
【発明を実施するための最良の形態】
【０２４５】
以下において、本発明の実施形態を説明する。なお、以下に説明する実施形態は、説明のためであって、本発明の範囲を限定するものと解されるべきではない。また、下記の実施形態の構成要素、要件を均等なものに置換することができるが、これらの形態も本発明に含まれるものとする。
【０２４６】
以下において、パラメータである剰余環の法Ｎを、２ｗ（但し、ｗは３以上の整数）に限定し、剰余環を２冪剰余環Ｚ／ＮＺに限定する。なお、Ｎとｗは関係式Ｎ＝２ｗ、ｗ＝ｌｏｇ２Ｎによって相互に容易に変換できるので、等価であり、Ｎの代わりにｗを用いた構成も、Ｎを用いた構成とみなす。例えば、格納部にＮの代わりに、ｗが格納されていても構わない。
【０２４７】
更に、以下において、次数決定問題とは、この２冪のパラメータＮとパラメータｘと（但し、ｘは整数、０≦ｘ＜Ｎ）と整数ｙ（但し、０≦ｙ＜Ｎ）とから、ｙ＝Ｔｄ（ｘ）  ｍｏｄ  Ｎを満たす正の整数ｄを求める問題とする。
【０２４８】
更に、以下において、各部は２進数で表現された数を扱い、そのビット数はｗ以上である。２冪剰余環上では、平方根を除いた全ての計算は、加算、乗算と剰余の組み合わせとして実行されるが、前述のように、桁溢れを持たない又は無視したｗビットの加算と乗算によって、結果的に剰余が実現される。以下における剰余を、この構成で実現し計算を高速化する。疑義のないよう数式上はｍｏｄ  Ｎと表記するが、実際にはこれを行わない。
【０２４９】
更に、以下において、頻繁にチェビシェフ多項式Ｔｄ（ｘ）の値を計算するが、この計算部は、全て上述のｗビットの加算と乗算を組み合わせたバイナリー指数法によって構成し、高速化する。例として、ｄ＝７としたＴ７（ｘ）をとって、このバイナリー指数法を詳しく述べる。
【０２５０】
まず、整数Ｄを
Ｄ＝ｘ２−１  ｍｏｄ  Ｎ
により計算し、一時メモリ内の適当な領域に格納する。更に、整数ａ１及びｂ１を、
ａ１＝ｘ，ｂ１＝1
とし、中間結果として一時メモリ内の別の適当な領域に格納する。これらの整数Ｄ、ａ１、ｂ１及びＮを用い、整数ａ２及びｂ２を、
ａ２＝ａ１２＋ｂ１２Ｄ  ｍｏｄ  Ｎ
ｂ２＝２ａ１ｂ１  ｍｏｄ  Ｎ
により計算し、別の中間結果として一時メモリ内の別の適当な領域に格納する。更に、整数ａ４及びｂ４を、
ａ４＝ａ２２＋ｂ２２Ｄ  ｍｏｄ  Ｎ
ｂ４＝２ａ２ｂ２  ｍｏｄ  Ｎ
により計算し、別の中間結果として一時メモリ内の別の適当な領域に格納する。次に、整数ａ６及びｂ６を、
ａ６＝ａ２ａ４＋ｂ２ｂ４Ｄ  ｍｏｄ  Ｎ
ｂ６＝ａ２ｂ４＋ａ４ｂ２  ｍｏｄ  Ｎ
により計算し、別の中間結果として一時メモリ内の別の適当な領域に格納する。最後に、
ａ７＝ａ６ａ１＋ｂ６ｂ１Ｄ  ｍｏｄ  Ｎ
により整数ａ７を計算すれば、Ｔ７（ｘ）＝ａ７となる。
【０２５１】
一般のｄについても、このようにしてＴｄ（ｘ）の値を高速に計算する。ここで利用する一時メモリは，その計算部に備わっている場合もあるし、汎用のものである場合もある。よって、Ｔｄ（ｘ）の計算部において一時メモリとの関係に言及しないときがある。
【０２５２】
＜第１の実施形態＞
第１の実施形態として、本発明のパラメータ生成装置の実施形態を説明する。図１はパラメータ生成装置の概要構成を示すブロック図である。以下、本図を参照しつつ本実施形態のパラメータ生成装置１００について説明する。なお、本実施形態のパラメータ生成装置を使用することで、本発明のパラメータ生成方法を実施することができる。
【０２５３】
（全体の構成）
本実施形態のパラメータ生成装置１００は、２冪剰余環Ｚ／ＮＺ（但し、Ｎ＝２Ｗ、ｗは３以上の整数）上でｄ次のチェビシェフ多項式Ｔｄ（ｘ）を考えることにより構成される次数決定問題を解くことを困難にするパラメータｘを生成する生成装置であって、パラメータＮ格納部１１０と第１の所定値格納部１２０と計算部１３０と出力部１４０と第２の所定値格納部１５０を備えている。
【０２５４】
本実施形態のパラメータ生成装置１００は、上記以外に、メモリ１６０、一時メモリ１７０、制御部１８０等を備えている。本実施形態では、パラメータＮ格納部１１０と第１の所定値格納部１２０と第２の所定値格納部１５０は、メモリ１６０内の領域として構成されている。
【０２５５】
なお、本実施形態のパラメータ生成装置１００は、通常のコンピュータを用いて実現されている。但し、加算器・乗算器等を備えた専用計算装置としても実現できる。
【０２５６】
（パラメータＮ格納部の構成）
パラメータＮ格納部１１０は、パラメータＮを予め記憶しており、上述したようにメモリ１６０内の領域として構成されている。
【０２５７】
また、パラメータＮ格納部１１０は、擬似乱数発生部１３１、ｑ計算部１３２、ｚ計算部１３６及び出力部１４０にＮを出力することができるように構成されている。
【０２５８】
（第１の所定値格納部の構成）
第１の所定値格納部１２０は、予め第１の所定値ｎ１を記憶しており、メモリ１６０内の領域として構成されている。
【０２５９】
また、第１の所定値格納部１２０は、後述するｎ１判定部１３４に第１の所定値ｎ１を出力することができるように構成されている。
【０２６０】
（第２の所定値格納部の構成）
第２の所定値格納部１５０は、予め第２の所定値ｎ２を記憶しており、メモリ１６０内の領域として構成されている。
【０２６１】
また、第２の所定値格納部１５０は、後述するｎ２判定部１３８に第２の所定値ｎ２を出力することができるように構成されている。
【０２６２】
（計算部の構成）
【０２６３】
計算部１３０は、擬似乱数発生部１３１、ｑ計算部１３２、ｎｑ計数部１３３、ｎ１判定部１３４、初期値設定部１３５、ｚ計算部１３６、等否判定部１３７、ｎ２判定部１３８及びｅ制御部１３９を備えることで、ｑ＝ｘ２−１  ｍｏｄ  Ｎで定義される整数ｑが因数４の個数を第１の所定値以上有するという第１の条件とｘ＝Ｔ２ｅ−１（ｘ）  ｍｏｄ  Ｎを満たす最小の正の整数ｅが第２の所定値以上であるという第２の条件とを満たすパラメータｘを計算し生成することできるように構成されている。
【０２６４】
擬似乱数発生部１３１は、３以上Ｎ未満の奇数の乱数を生成できるようになっており、制御部１８０に要求される度に、パラメータＮ格納部１１０に格納されたパラメータＮを読み出し、擬似乱数を発生し、整数ｘとしてメモリ１６０内の領域１６１に格納するように構成されている。
【０２６５】
ｑ計算部１３２は、計算式ｑ＝ｘ２−１  ｍｏｄ  Ｎを記憶しており、パラメータＮ格納部１１０に格納されたパラメータＮと領域１６１に格納された整数ｘとから、ｑ＝ｘ２−１  ｍｏｄ  Ｎを計算して、メモリ１６０内の領域１６２に格納するように構成されている。
【０２６６】
ｎｑ計数部１３３は、領域１６２に格納された整数ｑに関し、含まれる因数４の個数ｎｑを計数して、メモリ内の領域１６３に格納するように構成されている。
【０２６７】
このｎｑの計数は、最下位ビットから順に並んでいる０の個数を計数し、その個数が偶数であった場合それを２で割った値をｎｑ、奇数であった場合はそこから１を引いた値を２で割った値をｎｑとすることで実現することができる。例えばｑ＝４８のとき、２進数表現はｑ＝（１１００００）２であり、整数ｑの下位ビットから連続した０の個数＝４となるため、ｎｑ＝２となる。実際、４８＝２４×３＝４２×３であり、因数４の数は２個である。
【０２６８】
ｎ１判定部１３４は、領域１６３に格納された因数４の個数ｎｑと第１の所定値格納部１２０に格納された第１の所定値ｎ１に関して、不等式ｎｑ≧ｎ１が成り立つかどうかを判定し、その結果を制御部１８０に伝達することができるように構成されている。
【０２６９】
初期値設定部１３５は、メモリ１６０内の領域１６４に整数ｅとして２を格納できるように構成されている。
【０２７０】
ｚ計算部１３６は、予め、数式ｚ＝Ｔ２ｅ−１（ｘ）  ｍｏｄ  Ｎを記憶しており、領域１６１に格納された整数ｘとパラメータＮ格納部１１０に格納されたパラメータＮと領域１６４に格納された整数ｅとから、整数
ｚ＝Ｔ２ｅ−１（ｘ）  ｍｏｄ  Ｎ
を計算し、計算された整数ｚをメモリ１６０内の領域１６５に格納できるように構成されている。
【０２７１】
ここにおいて、補助的に整数２ｅ−１が必要となるが、この値は一時メモリ１７０に格納することができるように構成されている。
【０２７２】
なお、ｚ計算部１３６では、チェビシェフ多項式の計算の際、中間結果を一時メモリ１７０に格納する。
【０２７３】
等否判定部１３７は、領域１６１に格納された整数ｘと領域１６５に格納された整数ｚが等しいかどうかを判定し、その結果を制御部１８０に伝達することができるように構成されている。
【０２７４】
ｎ２判定部１３８は、第２の所定値格納部１５０に格納された第２の所定値ｎ２と領域１６４に格納された整数ｅに関して、不等式ｅ≧ｎ２が成り立つかどうかを判定し、その結果を制御部１８０に伝達することができるように構成されている。
【０２７５】
ｅ制御部１３９は、制御部１８０に要求される度に、領域１６４に格納された整数ｅの値を１だけ増やし、領域１６４に格納することができるように構成されている。
【０２７６】
（出力部の構成）
出力部１４０は、上述の計算部１３０において生成された整数ｘをパラメータｘとして、本パラメータ生成装置１００の外部に出力するように構成されている。また、出力部１４０は、必要に応じて、パラメータＮ格納部１１０に格納されているパラメータＮや領域１６４に格納されている整数ｅも本パラメータ生成装置１００の外部に出力するように構成されている。
【０２７７】
（その他の部材の構成）
制御部１８０は、後述する本パラメータ生成装置１００の動作に基づき、本パラメータ生成装置１００に含まれる各部の動作を制御するように構成されている。また、一時メモリ１７０は、制御部１８０の指示に応じて、計算部１３０の動作に必要となる中間結果を一時的に保存することができるように構成されている。
【０２７８】
（構成のまとめ）
このように、本実施形態のパラメータ生成装置は、コンピュータを用いて上述のように構成されており、必要な計算をしてパラメータｘを生成することができる。また、加算器・乗算器等を備えた専用計算装置により同様に構成して、必要な計算をしてパラメータｘを生成することもできる。
【０２７９】
なお、上述の構成では、パラメータＮ格納部１１０、第１の所定値格納部１２０及び第２の所定値格納部１５０は、いずれもメモリ１６０内の領域として構成されているが、少なくともｗビットの２進数を格納できる記憶領域であれば、メモリ１６０内でなくとも、構成することができる。
【０２８０】
（動作）
以下、本パラメータ生成装置１００の動作について説明する。図２は本パラメータ生成装置１００の動作全体の流れを示すフローチャートである。また、図３は図２のステップＳ１００の詳細を説明するためのフローチャートである。また、図４は図２のステップＳ２００の詳細を説明するためのフローチャートである。以下、図２から図４を用い、本第１の実施形態の動作を説明する。
【０２８１】
（動作と構成の対応）
尚、ステップＳ１００の動作は、上記の計算部１３０内の擬似乱数生成部１３１、ｑ計算部１３２、ｎｑ計数部１３３及びｎ１判定部１３４で処理され、ステップＳ２００の動作は、初期値設定部１３５、ｚ計算部１３６、等否判定部１３７及びｅ制御部１３９で処理され、ステップＳ３００の動作はｎ２判定部１３８で処理される。又、以下に述べる各処理は、制御部１８０の制御の下で実行される。また特に明示しないが、各演算処理によって得られたデータは逐一一時メモリ１７０に格納され、格納された各データはその後の演算処理に利用される。
【０２８２】
（前処理）
まず前処理として、パラメータＮがパラメータＮ格納部１１０に、第１の所定値ｎ１が第１の所定値格納部１２０に、第２の所定値ｎ２が第２の所定値格納部１５０に格納される。
【０２８３】
（ステップＳ１００の詳細）
本パラメータ生成装置１００の計算部１３０に備えられた擬似乱数生成部１３１は、パラメータＮ格納部１１０に格納されたパラメータＮを読み出し、３以上Ｎ未満の奇数の乱数を生成して、整数ｘとしてメモリ１６０内の領域１６１に格納する（ステップＳ１０１）。
【０２８４】
次にｑ計算部１３２は、領域１６１に格納された整数ｘとパラメータＮ格納部１１０に格納されたパラメータＮを読み出し、
ｑ＝ｘ２−１  ｍｏｄ  Ｎ
を計算する。そして、計算した整数ｑをメモリ１６０内の領域１６２に格納する（ステップＳ１０３）。
【０２８５】
ｎｑ計数部１３３は、領域１６２に格納された整数ｑを読み出し、整数ｑに含まれる因数４の個数ｎｑを計数し、これをメモリ１６０内の領域１６３に格納する（ステップＳ１０３）。
【０２８６】
そしてｎ１判定部１３４は、領域１６３に格納された整数ｎｑと第１の所定値格納部１２０に格納された第１の所定値ｎ１を読み出し、不等式
ｎｑ≧ｎ１
が成立するかどうか判定する（ステップＳ１０４）。
【０２８７】
判定の結果、ｎｑ≧ｎ１が成立していた場合、次のステップＳ２００へ進む。成立していなかった場合、ステップＳ１０１へ戻り、ステップＳ１０１からステップＳ１０４の動作を繰り返す。
【０２８８】
上記の判定を通過した場合、整数ｘは、ｑ＝ｘ２−１  ｍｏｄ  Ｎによって定義される整数ｑが因数４を第１の所定値ｎ１以上有するという第１の条件を満たす。２羃剰余環上のチェビシェフ多項式の次数決定問題を解く事を困難にするため、第１の所定値は、出来る限り大きく設定する事が望ましい。但し、余り大きくしすぎると、上記の反復動作が多数繰り返され計算部１３０の処理時間が長くなるばかりでなく、場合によっては第１の条件を満たす整数ｘが全く存在しないという状況も起こり得る。従って、パラメータＮに応じて適切な値を設定しておく。
【０２８９】
（ステップＳ２００の詳細）
上記の処理が終わった状態において、即ち、第１の条件を満たす整数ｘが領域１６１に格納された後、以下の処理を行う。
【０２９０】
まず、初期値設定部１３５は、メモリ１６０内の領域１６４の値を２に設定する。これは整数ｅの値を２に設定するという動作である（ステップＳ２０１）。
【０２９１】
次に、ｚ計算部１３６は、領域１６１に格納された整数ｘとパラメータＮ格納部１１０に格納されたパラメータＮと領域１６４に格納された整数ｅを読み出し、
ｚ＝Ｔ２ｅ−１（ｘ）  ｍｏｄ  Ｎ
により整数ｚを計算し、メモリ１６０内の領域１６５に格納する（ステップＳ２０２）。
【０２９２】
等否判定部１３７は、領域１６１に格納されている整数ｘと領域１６５に格納されている整数ｚを読み出し、これら２つの整数の値が等しいかどうか判定する（ステップＳ２０３）。
【０２９３】
判定の結果、これら２つの整数が等しかった場合、次のステップＳ３００へ進む。等しくなかった場合、ステップＳ２０４へ進む。
【０２９４】
上記の判定は、整数ｅが、ｘ＝Ｔ２ｅ−１（ｘ）  ｍｏｄ  Ｎを満たすかどうか判定する。
【０２９５】
上記の判定を通過しなかった場合、ｅ制御部１３９は、領域１６４に格納された整数ｅを読み出し、その値を１だけ増加させた整数を領域１６４に格納する（ステップＳ２０４）。この動作は、ｅをインクリメントすることに対応する。そして整数ｚが整数ｘになるまでステップＳ２０２からステップＳ２０４の動作が繰り返されることになる。ｚ＝ｘが成立したとき、ステップＳ２００が終了する。
【０２９６】
（ステップＳ３００）
ｎ２判定部１３８は、領域１６４に格納された整数ｅと第２の所定値格納部１５０に格納された第２の所定値ｎ２を読み出し、不等式
ｅ≧ｎ２
が成立するかどうか判定する（ステップＳ３００）。
【０２９７】
判定の結果、ｅ≧ｎ２が成立していた場合、処理を終了し、出力部１４０を後述のように動作させる。
【０２９８】
ｅ≧ｎ２が成立していなかった場合、ステップＳ１００へ戻り、ステップＳ１００からステップＳ３００の動作を繰り返す。
【０２９９】
上記のステップＳ３００の判定を通過した場合、ｅは第２の所定値ｎ２以上であるという第２の条件を満たす。ｅが大きいほど２羃剰余環上のチェビシェフ多項式ｙ＝Ｔｄ（ｘ）  ｍｏｄ  Ｎの次数決定問題に対する総当たり法による攻撃に対する強度が上がるため、第２の所定値は、出来る限り大きく設定する事が望ましい。但し、余り大きくしすぎると、上記の反復動作が多数繰り返され計算部１３０の処理時間が長くなるばかりでなく、場合によっては第２の条件を満たす整数ｘが全く存在しないという状況も起こり得る。従って、パラメータＮに応じて適切な値を設定しておく。
【０３００】
また、第２の所定値ｎ２を０と設定しておけば、ｎ２判定部１３８は実質的になにも処理せず、無条件で通過する。この場合、本パラメータ生成装置１００は、上記の第１の条件のみでパラメータｘを生成する装置となる。
【０３０１】
（出力部の動作）
出力部１４０は、少なくともメモリ１６０内の領域１６１に格納された整数ｘをパラメータｘとして本パラメータ生成装置１００の外部へ出力する。また制御部１８０の指示により、パラメータＮ格納部１１０に格納されたパラメータＮや領域１６４に格納された整数ｅも本パラメータ生成装置１００の外部へ出力することができる。
【０３０２】
（動作のまとめ）
上記のように本パラメータ生成装置１００を動作させる事により、第１及び第２の条件を満たすパラメータｘを高速に生成し、出力することができる。
【０３０３】
＜第２の実施形態＞
第２の実施形態として、本発明のパラメータ生成装置の第１の実施形態とは異なる実施形態を説明する。図５は本パラメータ生成装置の概要構成を示すブロック図である。以下、本図を参照しつつ本実施形態のパラメータ生成装置２００について説明する。なお、本実施形態の本パラメータ生成装置２００を使用することで、本発明のパラメータ生成方法を実施することができる。
【０３０４】
（全体の構成）
本実施形態のパラメータ生成装置２００は、上記のパラメータ生成装置１００と同様、剰余環Ｚ／ＮＺ（但し、Ｎ＝２Ｗ、ｗは３以上の整数）上でｄ次のチェビシェフ多項式Ｔｄ（ｘ）を考えることにより構成される次数決定問題を解くことを困難にするパラメータｘを生成する生成装置であって、パラメータＮ格納部２１０と第１の所定値格納部２２０と計算部２３０と出力部２４０と第２の所定値格納部２５０を備えている。
【０３０５】
本実施形態のパラメータ生成装置２００は、上記以外に、メモリ２６０、一時メモリ２７０、制御部２８０等を備えている。本実施形態では、パラメータＮ格納部２１０と第１の所定値格納部２２０と第２の所定値格納部２５０は、上記の第１の実施形態と同様、メモリ２６０内の領域として構成されている。
【０３０６】
なお、本実施形態のパラメータ生成装置２００も上記の第１の実施形態と同様、通常のコンピュータを用いて実現されている。但し、加算器・乗算器等を備えた専用計算装置としても実現できる。
【０３０７】
（パラメータＮ格納部の構成）
パラメータＮ格納部２１０は、パラメータＮを予め記憶しており、上述したようにメモリ２６０内の領域として構成されている。
【０３０８】
また、パラメータＮ格納部２１０は、擬似乱数発生部２３１、Ｘ計算部２３２、ｚ’計算部２３６及び出力部２４０にＮを出力することができるように構成されている。
【０３０９】
（第１の所定値格納部の構成）
第１の所定値格納部２２０は、予め第１の所定値ｎ１を記憶しており、メモリ２６０内の領域として構成されている。
【０３１０】
また、第１の所定値格納部２２０は、後述するｋ設定部２３４に第１の所定値ｎ１を出力することができるように構成されている。
【０３１１】
（第２の所定値格納部の構成）
第２の所定値格納部２５０は、予め第２の所定値ｎ２を記憶しており、メモリ２６０内の領域として構成されている。
【０３１２】
また、第２の所定値格納部２５０は、後述するｎ３判定部２３８に第２の所定値ｎ２を出力することができるように構成されている。
【０３１３】
（計算部の構成）
【０３１４】
計算部２３０は、擬似乱数発生部２３１、Ｘ計算部２３２、平方根計算部２３３−１、平方剰余判定部２３３−２、ｋ設定部２３４、ｄ初期値設定部２３５、ｚ’計算部２３６、等否判定部２３７、ｎ３判定部２３８及びｄ制御部２３９を備えることで、ｑ＝ｘ２−１  ｍｏｄ  Ｎで定義される整数ｑが因数４の個数を第１の所定値以上有するという第１の条件とｘ＝Ｔ２ｅ−１（ｘ）  ｍｏｄ  Ｎを満たす最小の正の整数ｅが第２の所定値以上であるという第２の条件とを満たすパラメータｘを計算し生成することできるように構成されている。
【０３１５】
擬似乱数発生部２３１は、３以上Ｎ未満の奇数の乱数を生成できるようになっており、制御部２８０に要求される度に、パラメータＮ格納部２１０に格納されたパラメータＮを読み出し、擬似乱数を発生し、整数ｙとしてメモリ２６０内の領域２６４に格納するように構成されている。
【０３１６】
Ｘ計算部２３２は、計算式Ｘ＝４ｋｙ＋１  ｍｏｄ  Ｎを記憶しており、パラメータＮ格納部２１０に格納されたパラメータＮとメモリ２６０内の領域２６２に格納された整数ｋと領域２６４に格納された整数ｙとから、Ｘ＝４ｋｙ＋１  ｍｏｄ  Ｎを計算して、メモリ２６０内の領域２６６に整数Ｘを格納するように構成されている。
【０３１７】
平方根計算部２３３−１は、領域２６６に格納された整数Ｘに関し、パラメータＮ格納部２１０に格納されたパラメータＮを読み出し、２冪剰余環Ｚ／ＮＺ上でＸの平方根を計算し、平方根がこの２冪剰余環の要素にならない場合は０を、なる場合は整数値の平方根の１つ√Ｘ（０≦√Ｘ＜Ｎ）をメモリ内の領域２６１に格納するように構成されている。２冪剰余環上で平方根を計算する方法としては、非特許文献２の第３章にＰｏｈｌｉｎｇ−Ｈｅｌｌｍａｎ法を利用したものが記載されており、平方根計算部２３３−１はこの方法による計算を実行するように構成されている。
【０３１８】
平方剰余判定部２３３−２は、領域２６１に格納された整数ｘを読み出し、その値が０に等しいかどうかを判定し、その結果を制御部２８０に伝達することができるように構成されている。
【０３１９】
このように計算された整数の平方根√Ｘから
ｑ＝（√Ｘ）２−１  ｍｏｄ  Ｎ
を計算したとき、整数ｑは因数４を第１の所定値ｎ１と同じ個数だけ持つ。これは、
ｑ＝Ｘ−１  ｍｏｄ  Ｎ＝４ｋｙ  ｍｏｄ  Ｎ
より明らかである。
【０３２０】
ｋ設定部２３４は、第１の所定値格納部２２０に格納された第１の所定値ｎ１に関して、その値を整数ｋとして設定し、領域２６２に格納するように構成されている。
【０３２１】
ｄ初期値設定部２３５は、メモリ２６０内の領域２６３に整数ｄとして４を格納できるように構成されている。
【０３２２】
ｚ’計算部２３６は、予め、数式ｚ’＝Ｔｄ−１（ｘ）  ｍｏｄ  Ｎを記憶しており、領域２６１に格納された整数ｘとパラメータＮ格納部２１０に格納されたパラメータＮと領域２６３に格納された整数ｄとから、整数
ｚ’＝Ｔｄ−１（ｘ）  ｍｏｄ  Ｎ
を計算し、計算された整数ｚ’をメモリ２６０内の領域２６５に格納できるように構成されている。
【０３２３】
ここにおいて、補助的に整数ｄ−１が必要となるが、この値は一時メモリ１７０に格納することができるように構成されている。
【０３２４】
なお、本実施形態では、チェビシェフ多項式の計算の際、中間結果を一時メモリ２７０に格納する。
【０３２５】
等否判定部２３７は、領域２６１に格納された整数ｘと領域２６５に格納された整数ｚ’が等しいかどうかを判定し、その結果を制御部２８０に伝達することができるように構成されている。
【０３２６】
ｎ３判定部２３８は、第２の所定値格納部２５０に格納された第２の所定値ｎ２と領域２６３に格納された整数ｄに関して、不等式ｄ≧２ｎ２が成り立つかどうかを判定し、その結果を制御部２８０に伝達することができるように構成されている。但し、ここで、ｎ２とはｎ２のことである。
【０３２７】
ｄ制御部２３９は、制御部２８０に要求される度に、領域２６３に格納された整数ｄの値を２倍し、領域２６３に格納することができるように構成されている。
【０３２８】
（出力部の構成）
出力部２４０は、上述の計算部２３０において生成された整数ｘをパラメータｘとして、本パラメータ生成装置２００の外部に出力するように構成されている。また、出力部２４０は、必要に応じて、パラメータＮ格納部２１０に格納されているパラメータＮや、整数ｅ（但し、ｅは領域２６３に格納されている整数ｄから計算される整数ｌｏｇ２ｄ）を、本パラメータ生成装置２００の外部に出力するように構成されている。
【０３２９】
（その他の部材の構成）
制御部２８０は、後述する本パラメータ生成装置２００の動作に基づき、本パラメータ生成装置２００に含まれる各部の動作を制御するように構成されている。また、一時メモリ２７０は、制御部２８０の指示に応じて、計算部２３０の動作に必要となる中間結果を一時的に保存することができるように構成されている。
【０３３０】
（構成のまとめ）
このように、本実施形態のパラメータ生成装置は、コンピュータを用いて上述のように構成されており、必要な計算をしてパラメータｘを生成することができる。また、加算器・乗算器等を備えた専用計算装置により同様に構成して、必要な計算をしてパラメータｘを生成することもできる。
【０３３１】
なお、上述の構成では、パラメータＮ格納部２１０、第１の所定値格納部２２０及び第２の所定値格納部２５０は、いずれもメモリ２６０内の領域として構成されているが、少なくともｗビットの２進数を格納できる記憶領域であれば、メモリ２６０内でなくとも、構成することができる。
【０３３２】
（動作）
以下、本パラメータ生成装置２００の動作について説明する。図６は本パラメータ生成装置２００の動作全体の流れを示すフローチャートである。以下、図６を用い、本第２の実施形態の動作を説明する。
【０３３３】
（動作と構成の対応）
尚、ステップＳ４０１の動作は上記の計算部２３０内のｋ設定部２３４で、ステップＳ４０２の動作はｄ初期値設定部２３５で、ステップＳ４０３の動作は擬似乱数発生部２３１で、ステップＳ４０４の動作はＸ計算部２３２で、ステップＳ４０５−１の動作は平方根計算部２３３−１で、ステップＳ４０５−２の動作は平方剰余判定部２３３−２で、ステップＳ４０６の動作はｚ’計算部２３６で、ステップＳ４０７の動作は等否判定部２３７で、ステップＳ４０８の動作はｄ制御部２３９で、ステップＳ４０９の動作はｎ３判定部２３８でそれぞれ処理される。また、以下に述べる各処理は、制御部２８０の制御の下で実行される。また特に明示しないが、各演算処理によって得られたデータは逐一一時メモリ２７０に格納され、格納された各データはその後の演算処理に利用される。
【０３３４】
（前処理）
まず前処理として、パラメータＮがパラメータＮ格納部２１０に、第１の所定値ｎ１が第１の所定値格納部２２０に、第２の所定値ｎ２が第２の所定値格納部２５０に格納される。
【０３３５】
（各ステップの詳細）
本パラメータ生成装置２００の計算部２３０に備えられたｋ設定部２３４は、第１の所定値格納部２２０に格納された第１の所定値ｎ１を読み出し、整数ｋの値をｎ１とし、メモリ２６０内の領域２６２に格納する（ステップＳ４０１）。
【０３３６】
次にｄ初期値設定部２３５は、メモリ２６０内の領域２６３に値４を格納する。これはｄ＝４という処理を行った事に対応する（ステップＳ４０２）。
【０３３７】
擬似乱数生成部２３１は、パラメータＮ格納部２１０に格納されたパラメータＮを読み出し、３以上Ｎ未満の奇数の乱数を生成して、整数ｙとしてメモリ２６０内の領域２６４に格納する（ステップＳ４０３）。
【０３３８】
続いてＸ計算部２３２は、領域２６１に格納された整数ｘと領域２６２に格納された整数ｋとパラメータＮ格納部２１０に格納されたパラメータＮを読み出し、
Ｘ＝４ｋｙ＋１  ｍｏｄ  Ｎ
を計算する。そして、計算した整数Ｘをメモリ２６０内の領域２６６に格納する（ステップＳ４０４）。
【０３３９】
そして平方根計算部２３３−１は、パラメータＮ格納部２１０に格納されたパラメータＮと領域２６６に格納された整数Ｘを読み出し、２冪剰余環上で平方根を計算し、平方根がこの２冪剰余環の要素にならない場合は０を、なる場合は整数値の平方根の１つｘを、メモリ２６０内の領域２６１に格納する（ステップＳ４０５−１）。
【０３４０】
平方剰余判定部２３３−２は、領域２６１から整数ｘを読み出し、整数ｘが０に等しいかどうか判定する（ステップＳ４０５−２）。
【０３４１】
判定の結果、整数ｘが０に等しい場合、ステップＳ４０３に戻る。整数ｘが０以外の値になるまで、即ち、ｘが上記の整数Ｘの２羃剰余環上での平方根になるまで、ステップＳ４０３からステップＳ４０５−２の動作が繰り返されることになる。ｘ≠０が成立したとき、ステップＳ４０６へ進む。
【０３４２】
更に、ｚ’計算部２３６は、領域２６１に格納された整数ｘとパラメータＮ格納部２１０に格納されたパラメータＮと領域２６３に格納された整数ｄを読み出し、
ｚ’＝Ｔ２ｄ−１（ｘ）  ｍｏｄ  Ｎ
により整数ｚ’を計算し、メモリ２６０内の領域２６５に格納する（ステップＳ４０６）。
【０３４３】
等否判定部２３７は、領域２６１に格納されている整数ｘと領域２６５に格納されている整数ｚ’を読み出し、これら２つの整数の値が等しいかどうか判定する（ステップＳ４０７）。
【０３４４】
判定の結果、これら２つの整数が等しかった場合、次のステップＳ４０９へ進む。等しくなかった場合、ステップＳ４０８へ進む。
【０３４５】
上記の判定は、整数ｄが、ｘ＝Ｔｄ−１（ｘ）  ｍｏｄ  Ｎを満たすかどうか判定する。
【０３４６】
上記の判定を通過しなかった場合、ｄ制御部２３９は、領域２６３に格納された整数ｄを読み出し、その値を２倍した整数を領域２６３に格納する（ステップＳ４０８）。整数ｚ’が整数ｘになるまでステップＳ４０６からステップＳ４０８の動作が繰り返されることになる。ｚ’＝ｘが成立したとき、ステップＳ４０９へ進む。
【０３４７】
ｎ３判定部２３８は、領域２６３に格納された整数ｄと第２の所定値格納部２５０に格納された第２の所定値ｎ２を読み出し、不等式
ｄ≧２ｎ２
が成立するかどうか判定する（ステップＳ４０９）。ここで、ｎ２とは、第２の所定値ｎ２を意味する。
【０３４８】
判定の結果、ｄ≧２ｎ２が成立していた場合、処理を終了し、出力部２４０を後述のように動作させる。
【０３４９】
ｄ≧２ｎ２が成立していなかった場合、ステップＳ４０２へ戻り、ステップＳ４０２からステップＳ４０９の動作を繰り返す。
【０３５０】
上記のステップＳ４０９の判定を通過した場合、ｌｏｇ２ｄ（＝ｅ）は、第２の所定値ｎ２以上であるという第２の条件を満たす。ｌｏｇ２ｄが大きいほど２羃剰余環上のチェビシェフ多項式ｙ＝Ｔｄ（ｘ）  ｍｏｄ  Ｎの次数決定問題に対する総当たり法による攻撃に対する強度が上がるため、第２の所定値は、出来る限り大きく設定する事が望ましい。但し、余り大きくしすぎると、上記の反復動作が多数繰り返され計算部２３０の処理時間が長くなるばかりでなく、場合によっては第２の条件を満たす整数ｘが全く存在しないという状況も起こり得る。従って、パラメータＮに応じて適切な値を設定しておく。
【０３５１】
また、第２の所定値ｎ２を０と設定しておけば、ｎ３判定部２３８は実質的になにも処理せず、無条件で通過する。この場合、本パラメータ生成装置２００は、上記の第１の条件のみでパラメータｘを生成する装置となる。
【０３５２】
（出力部の動作）
出力部２４０は、メモリ２６０内の領域２６１に格納された整数ｘをパラメータｘとして本パラメータ生成装置２００の外部へ出力する。また制御部２８０の指示により、パラメータＮ格納部２１０に格納されたパラメータＮを出力し、領域２６３に格納された整数ｄを読み出し、整数ｅ＝ｌｏｇ２ｄを計算し出力することができる。
【０３５３】
（動作のまとめ）
上記のように本パラメータ生成装置２００を動作させる事により、第１及び第２の条件を満たすパラメータｘを高速に生成し、出力することができる。
【０３５４】
＜第３の実施形態＞
第３の実施形態として、本発明の第１の公開鍵暗号システムの実施形態を説明する。本発明の公開暗号鍵システムは、本発明のパラメータ生成装置又はパラメータ生成方法によって生成されたパラメータｘと、パラメータＮとを用いた公開鍵暗号システムである。図７は公開鍵暗号システムの概要構成を示す模式図である。以下、本図を参照しつつ本実施形態の公開鍵暗号システム３００について説明する。なお、本実施形態の公開鍵暗号システム３００は、本発明の鍵共有システムを用いたものである。
【０３５５】
（システム全体の構成）
本実施形態の公開鍵暗号システム３００は、３台のコンピュータＰＣ  Ａ３１０、ＰＣ  Ｂ３２０及びＰＣ  Ｃ３３０がインターネット３４０を介して相互に接続されている。ここでは３台のコンピュータを考えているが、ＰＣ  Ｃ３３０は、ＰＣ  Ａ３１０又はＰＣ  Ｂ３２０のどちらかに含むように構成することもできる。図８はＰＣ  Ａの構成を示すブロック図、図９はＰＣ  Ｂの構成を示すブロック図である。以下、これらの図も参照しながら説明する。
【０３５６】
ＰＣ  Ｃ３３０は、パラメータｘとパラメータＮとを出力するパラメータ生成装置である。ＰＣ  Ａ３１０は、本発明の鍵暗号システムに含まれる第１の鍵共有装置であって、ＰＣ  Ｂ３２０は、本発明の鍵暗号システムに含まれる送付鍵生成装置と第２の鍵共有装置を兼ねている。なお、本実施形態では、本発明のパラメータ生成装置が生成し出力したパラメータｘと、それに対応するパラメータＮとを用いるために、パラメータ生成装置であるＰＣ  Ｃ３３０が、公開鍵暗号システムの一部を構成している。但し、本発明の公開鍵暗号システムとしては、パラメータ生成装置がシステムの一部を構成しなくても、パラメータ生成装置が生成し出力したパラメータｘと、それに対応するパラメータＮとを本システムが用いていればよい。
【０３５７】
また、本実施形態の公開鍵暗号システムは、３台のコンピュータを用いているが、それぞれについて、コンピュータに代えて、加算器・乗算器等を備えた専用計算装置としても実現できる。
【０３５８】
（パラメータ生成装置（ＰＣ  Ｃ３３０）の構成）
ＰＣ  Ｃ３３０は、上記の第１の実施形態又は第２の実施形態で示したパラメータ生成装置であって、パラメータｘとパラメータＮとを出力するように構成されている。
【０３５９】
（第１の鍵共有装置（ＰＣ  Ａ３１０）の構成）
ＰＣ  Ａ３１０は、本発明の公開鍵暗号システムを構成する第１の鍵共有装置であって、図８に示すように構成されている。即ち、メモリ３１１、整数取得部３１２、送付鍵計算部３１３、送付鍵出力部３１４、送付鍵入力部３１５、共有鍵計算部３１６、暗号化部３１７、暗号化メッセージ送信部３１８、一時メモリ３１１ｉ、制御部３１９を備える。一時メモリ３１１ｉは、各部の計算過程を一時的に格納することができるように構成されている。また制御部３１９は全体の動作を制御できるように構成されている。
【０３６０】
尚、本発明の第１の鍵共有装置を構成することができる。また、本ＰＣ  Ａ３１０を使用することで、本発明の第１の鍵共有方法及び第１の暗号化方法を実施することができる。
【０３６１】
（第１の鍵共有装置（ＰＣ  Ａ３１０）の各部の構成）
メモリ３１１は、ＰＣ  Ｃ３３０の出力したパラメータｘとパラメータＮ、整数ｔ、送付鍵Ｕ、送付鍵Ｔ、共有鍵Ｖ’、メッセージｍ及び暗号化メッセージｃを格納できるよう構成されている。
【０３６２】
整数取得部３１２は、大きな奇数ｔを取得し、メモリ３１１の領域３１１ｂに格納できるように構成されている。
【０３６３】
送付鍵計算部３１３は、予め計算式Ｕ＝Ｔｔ（ｘ）  ｍｏｄ  Ｎを記憶しており、メモリ３１１内の領域３１１ｃに格納されたパラメータｔと領域３１１ａに格納されたパラメータｘと領域３１１ｂに格納されたパラメータＮとから、
Ｕ＝Ｔｔ（ｘ）  ｍｏｄ  Ｎ
により送付鍵Ｕを計算し、メモリ３１１内の領域３１１ｄに格納できるように構成されている。
【０３６４】
送付鍵出力部３１４は、領域３１１ｄに格納されている送付鍵ＵをＰＣ  Ａ３１０の外部に出力できるよう構成されている。
【０３６５】
送付鍵入力部３１５は、ＰＣ  Ａ３１０の外部から入力された送付鍵Ｔを入力し、メモリ３１１内の領域３１１ｅに格納できるように構成されている。
【０３６６】
共有鍵計算部３１６は、予め計算式Ｖ’＝Ｔｔ（Ｔ）  ｍｏｄ  Ｎを記憶しており、領域３１１ｃに格納された整数ｔと領域３１１ｅに格納された送付鍵Ｔと領域３１１ｂに格納されたパラメータＮとから、
Ｖ’＝Ｔｔ（Ｔ）  ｍｏｄ  Ｎ
により共有鍵Ｖ’を計算し、メモリ内の領域３１１ｆに格納できるように構成されている。
【０３６７】
暗号化部３１７は、予め記憶された対称鍵暗号方式の暗号化式と領域３１１ｆに格納された共有鍵Ｖ’を用いて、領域３１１ｇに格納されたメッセージｍから暗号化メッセージｃを計算し、メモリ３１１内の領域３１１ｈに格納できるように構成されている。
【０３６８】
暗号化メッセージ送信部３１８は、領域３１１ｈに格納された暗号化メッセージｃをＰＣ  Ａ３１０の外部に出力できるよう構成されている。
【０３６９】
（送付鍵生成装置兼第２の鍵共有装置（ＰＣ  Ｂ３２０）の構成）
ＰＣ  Ｂ３２０は、本発明の公開鍵暗号システムを構成する送付鍵生成装置と第２の鍵共有装置を兼ねており、図９に示すように構成されている。即ち、メモリ３２１、整数取得部３２２ａ、送付鍵計算部３２２ｂ、第１送付鍵出力部３２２ｃ、第２送付鍵出力部３２２ｄ、第１送付鍵入力部３２３ａ、第２送付鍵入力部３２３ｂ、共有鍵計算部３２３ｃ、暗号化メッセージ受信部３２３ｄ、復号化部３２３ｅ、一時メモリ３２１ｉ、制御部３２４を備えている。一時メモリ３２１ｉは、各部の計算過程を一時的に格納することができるように構成されている。また制御部３２４は全体の動作を制御できるように構成されている。
【０３７０】
なお、送付鍵生成装置に対応する部分としては、メモリ３２１内の領域３２１ａ、３２１ｂ、３２１ｃ及び３２１ｄ、整数取得部３２２ａ、送付鍵計算部３２２ｂ、第１送付鍵出力部３２２ｃ、第２送付鍵出力部３２２ｄ等であり、第２の鍵共有装置に対応する部分としては、メモリ３２１内の３２１ｅ、３２１ｆ、３２１ｇ及び３２１ｈ、第１送付鍵入力部３２３ａ、第２送付鍵入力部３２３ｂ、共有鍵計算部３２３ｃ、暗号化メッセージ受信部３２３ｄ、復号化部３２３ｅ等である。
【０３７１】
また、本ＰＣ  Ａ３２０を使用することで、本発明の送付鍵生成方法、第２の鍵共有方法及び第１の復号化方法を実施することができる。
【０３７２】
（送付鍵生成装置兼第２の鍵共有装置（ＰＣ  Ｂ）の各部の構成）
メモリ３２１は、ＰＣ  Ｃ３３０の出力したパラメータｘとパラメータＮ、整数ｓ、送付鍵Ｔ、送付鍵Ｕ、共有鍵Ｖ、暗号化メッセージｃ及びメッセージｍ’を格納できるよう構成されている。
【０３７３】
整数取得部３２２ａは、大きな奇数ｓを取得し、メモリ３２１の領域３２１ｃに格納できるように構成されている。
【０３７４】
送付鍵計算部３２２ｂは、予め計算式Ｔ＝Ｔｓ（ｘ）  ｍｏｄ  Ｎを記憶しており、メモリ３２１内の領域３２１ｃに格納されたパラメータｓと領域３２１ａに格納されたパラメータｘと領域３２１ｂに格納されたパラメータＮとから、
Ｔ＝Ｔｓ（ｘ）  ｍｏｄ  Ｎ
により送付鍵Ｔを計算し、メモリ３２１内の領域３２１ｄに格納できるように構成されている。
【０３７５】
第１送付鍵出力部３２２ｃは、領域３２１ｄに格納されている送付鍵ＴをＰＣ  Ｂ３２０の外部に出力できるよう構成されている。
【０３７６】
第２送付鍵出力部３２２ｄは、領域３２１ｃに格納されている整数ｓを送付鍵として送付鍵生成装置３２２の外部に出力できるよう構成されている。
【０３７７】
第１送付鍵入力部３２３ａは、ＰＣ  Ｂ３２０の外部から入力された送付鍵Ｕを入力し、メモリ３２１内の領域３２１ｅに格納できるように構成されている。
【０３７８】
第２送付鍵入力部３２３ｂは、第２の鍵共有装置３２３の外部から入力された送付鍵ｓを入力し、メモリ３２１内の領域３２１ｃに格納できるように構成されている。
【０３７９】
共有鍵計算部３２３ｃは、予め計算式Ｖ＝Ｔｓ（Ｕ）  ｍｏｄ  Ｎを記憶しており、領域３２１ｃに格納された送付鍵ｓと領域３２１ｅに格納された送付鍵Ｕと領域３２１ｂに格納されたパラメータＮとから、
Ｖ＝Ｔｓ（Ｕ）  ｍｏｄ  Ｎ
により共有鍵Ｖを計算し、メモリ内の領域３２１ｆに格納できるように構成されている。
【０３８０】
暗号化メッセージ受信部３２３ｄは、ＰＣ  Ｂ３２０の外部から入力された暗号化メッセージｃを領域３２１ｇに格納できるよう構成されている。
【０３８１】
復号化部３２３ｅは、予め記憶された対称鍵暗号方式の復号化式と領域３２１ｆに格納された共有鍵Ｖを用いて、領域３２１ｇに格納された暗号化メッセージｃからメッセージｍ’を計算し、メモリ３２１内の領域３２１ｈに格納できるように構成されている。
【０３８２】
（構成のまとめ）
このように、本実施形態の公開鍵暗号システムは、３台のコンピュータを用いて上述のように構成されており、ＰＣ  Ｃ３３０の生成したパラメータｘとパラメータＮを用い、ＰＣ  Ａ３１０が作成した暗号化メッセージをＰＣ  Ｂ３２０で復号化することができる。また、ＰＣ  Ａ３１０とＰＣ  Ｂ３２０でそれぞれ作成された共有鍵Ｖ’とＶは等しい。
【０３８３】
（鍵共有システムとしての動作）
以下、本公開鍵暗号システム３００の動作について説明する。図１０は本公開鍵暗号システム３００の鍵共有システムとしての動作の流れを示すフローチャートである。以下、図１０を用い、本第３の実施形態の動作を説明する。
【０３８４】
（ステップＳ４１０）
ＰＣ  Ｃ３３０の動作により、パラメータｘとパラメータＮが生成され、インターネット３４０を通じＰＣ  Ａ３１０及びＰＣ  Ｂ３２０に配信される。
【０３８５】
ＰＣ  Ａ３１０は、配信されたパラメータｘをメモリ３１１内の領域３１１ａに、パラメータＮを領域３１１ｂに格納する。
【０３８６】
ＰＣ  Ｂ３２０は、配信されたパラメータｘをメモリ３２１内の領域３２１ａに、パラメータＮを領域３２１ｂに格納する。
【０３８７】
（ステップＳ４２０）
ＰＣ  Ａ３１０の整数取得部３１２は、大きな奇数である整数ｔを生成してメモリ３１１内の領域３１１ｃに整数ｔとして格納する。
【０３８８】
送付鍵計算部３１３は、領域３１１ａに格納されたパラメータｘと領域３１１ｂに格納されたパラメータＮと領域３１１ｃに格納された整数ｔを読み出し、
Ｕ＝Ｔｔ（ｘ）  ｍｏｄ  Ｎ
により送付鍵Ｕを計算し、領域３１１ｄに格納する。
【０３８９】
送付鍵出力部３１４は、領域３１１ｄに格納された送付鍵Ｕを読み出し、インターネット３４０を通じＰＣ  Ｂ３２０の第１送付鍵入力部３２３ａに出力する。
【０３９０】
（ステップＳ４３０）
ＰＣ  Ｂ３２０の整数取得部３２２ａは、大きな奇数である整数ｓを生成してメモリ３２１内の領域３２１ａに整数ｓとして格納する。
【０３９１】
送付鍵計算部３２２ｂは、領域３２１ｃに格納された整数ｓと領域３２１ａに格納されたパラメータｘと領域３２１ｂに格納されたパラメータＮを読み出し、
Ｔ＝Ｔｓ（ｘ）  ｍｏｄ  Ｎ
により送付鍵Ｔを計算し、領域３２１ｄに格納する。
【０３９２】
第１送付鍵出力部３２２ｃは、領域３２１ｄに格納された送付鍵Ｔを読み出し、インターネット３４０を通じＰＣ  Ａ３１０の送付鍵入力部３１５に出力する。
【０３９３】
第２送付鍵出力部３２２ｄは、領域３２１ｃに格納された整数ｓを読み出し、送付鍵として第２送付鍵入力部３２３ｂに出力する。
【０３９４】
第１送付鍵入力部３２３ａは、ＰＣ  Ａ３１０の送付鍵出力部３１４が出力した送付鍵Ｕを入力し、領域３２１ｅに格納する。
【０３９５】
第２送付鍵入力部３２３ｂは、第２送付鍵出力部３２２ｄが送付鍵として出力した整数ｓを入力し、領域３２１ｃに格納する。
【０３９６】
共有鍵計算部３２３ｃは、領域３２１ｃに格納された整数ｓと領域３２１ｅに格納された送付鍵Ｕと領域３２１ｂに格納されたパラメータＮとから、
Ｖ＝Ｔｓ（Ｕ）  ｍｏｄ  Ｎ
により共有鍵Ｖを計算し、領域３２１ｆに格納する。
【０３９７】
（ステップＳ４４０）
ＰＣ  Ａ３１０の送付鍵入力部３１５は、ＰＣ  Ｂ３２０の第１送付鍵出力部３２２ｃが出力した送付鍵Ｔを入力し、メモリ３１１の領域３１１ｅに格納する。
【０３９８】
共有鍵計算部３１６は、領域３１１ｅに格納された送付鍵Ｔから、
Ｖ’＝Ｔｔ（Ｔ）  ｍｏｄ  Ｎ
により共有鍵Ｖ’を計算し、領域３１１ｆに格納する。
【０３９９】
（鍵共有システムとしての動作のまとめ）
ここで、チェビシェフ多項式の性質より、
Ｖ＝Ｔｓ（Ｔｔ（ｘ））  ｍｏｄ  Ｎ＝Ｔｓｔ（ｘ）ｍｏｄ  Ｎ
及び、
Ｖ’＝Ｔｔ（Ｔｓ（ｘ））  ｍｏｄ  Ｎ＝Ｔｓｔ（ｘ）  ｍｏｄ  Ｎ
となることから、Ｖ＝Ｖ’が成立する。即ち、Ｖ（＝Ｖ’）が共有鍵として、ＰＣ  Ａ３１０及びＰＣ  Ｂ３２０に共有される。
【０４００】
（公開鍵暗号システムとしての動作）
上記の鍵共有システムとしての動作の後に、次の動作を加えることによって、本第３の実施形態を、公開鍵暗号システムとして動作させることができる。
【０４０１】
ＰＣ  Ａ３１０のメモリ３１１には、領域３１１ｇに予め平文のメッセージｍが格納されている。
【０４０２】
ＰＣ  Ａ３１０の暗号化部３１７は、メモリ３１１内の領域３１１ｇに格納された平文のメッセージｍと領域３１１ｆに格納された共有鍵Ｖ’を読み出し、予め記憶されている対称鍵暗号方式の暗号化計算式により、メッセージｍを共有鍵Ｖ’を用いて暗号化し、暗号化メッセージｃを得、領域３１１ｈに格納する。
【０４０３】
暗号化メッセージ送信部３１８は、インターネット３４０を通し、ＰＣ  Ｂ３２０の暗号化メッセージ受信部３２３ｄに領域３１１ｈに格納された暗号化メッセージｃを送信する。
【０４０４】
ＰＣ  Ｂ３２０の暗号化メッセージ受信部３２３ｄは、ＰＣ  Ａ３１０が送信した暗号化メッセージｃを受信し、メモリ３２１内の領域３２１ｇに格納する。
【０４０５】
復号化部３２３ｅは、領域３２１ｇに格納された暗号化メッセージｃと領域３２１ｆに格納された共有鍵Ｖを読み出し、予め記憶されている対称鍵暗号方式の復号化計算式により、暗号化メッセージｃを共有鍵Ｖを用いて復号化し、平文のメッセージｍ’を得、領域３２１ｈに格納する。
【０４０６】
このように本第３の実施形態は、パラメータｘ、パラメータＮ及び送付鍵Ｔを公開鍵とみて、整数ｓを秘密鍵とみて、全体としての暗号化メッセージを（ｃ，Ｕ）とみれば、公開鍵暗号システムとして用いる事ができる。
【０４０７】
（第３の実施形態の変形例）
本第３の実施形態では、ＰＣ  Ｂ３２０が本発明の送付鍵生成装置と第２の鍵共有装置を兼ねた形態であるが、変形例は、送付鍵生成装置と第２の鍵共有装置とを別々の装置とする形態である。
【０４０８】
この変形例では、便宜上、図９を用いて説明すると、送付鍵生成装置は、領域３２１ａ、３２１ｂ、３２１ｃ及び３２１ｄを有するメモリ、整数取得部３２２ａ、送付鍵計算部３２２ｂ、第１送付鍵出力部３２２ｃ、第２送付鍵出力部３２２ｄ等を備えた装置であり、第２の鍵共有装置に対応する部分としては、領域３２１ｅ、３２１ｆ、３２１ｇ及び３２１ｈを有するメモリ、第１送付鍵入力部３２３ａ、第２送付鍵入力部３２３ｂ、共有鍵計算部３２３ｃ、暗号化メッセージ受信部３２３ｄ、復号化部３２３ｅ等を備えた装置である。
【０４０９】
送付鍵生成装置の動作、及び、第２の鍵共有装置の動作は、装置が分離したことに伴う違いを除けば、基本的には、第３の実施形態と同様である。
【０４１０】
＜第４の実施形態＞
第４の実施形態として、本発明の第２の公開鍵暗号システムの実施形態を説明する。本発明の公開暗号鍵システムは、本発明のパラメータ生成装置又はパラメータ生成方法によって生成されたパラメータｘと、パラメータＮとを用いた公開鍵暗号システムである。図１１は公開鍵暗号システムの概要構成を示す模式図である。以下、本図を参照しつつ本実施形態の公開鍵暗号システム４００について説明する。
【０４１１】
（システム全体の構成）
本実施形態の公開鍵暗号システム４００は、３台のコンピュータＰＣ  Ａ４１０、ＰＣ  Ｂ４２０及びＰＣ  Ｃ４３０がインターネット４４０を介して相互に接続されている。ここでは３台のコンピュータを考えているが、ＰＣ  Ｃ４３０は、ＰＣ  Ａ４１０又はＰＣ  Ｂ４２０のどちらかに含むように構成することもできる。図１２はＰＣ  Ａの構成を示すブロック図、図１３はＰＣ  Ｂの構成を示すブロック図である。以下、これらの図も参照しながら説明する。
【０４１２】
ＰＣ  Ｃ４３０は、パラメータｘとパラメータＮとを出力するパラメータ生成装置である。ＰＣ  Ａ４１０は、本発明の公開鍵暗号システムに含まれる暗号化装置であって、ＰＣ  Ｂ４２０は、本発明の公開鍵暗号システムに含まれる鍵対生成装置と復号化装置を兼ねている。なお、本実施形態では、本発明のパラメータ生成装置が生成し出力したパラメータｘと、それに対応するパラメータＮとを用いるために、パラメータ生成装置であるＰＣ  Ｃ４３０が、公開鍵暗号システムの一部を構成している。但し、本発明の公開鍵暗号システムとしては、パラメータ生成装置がシステムの一部を構成しなくても、パラメータ生成装置が生成し出力したパラメータｘと、それに対応するパラメータＮとを本システムが用いていればよい。
【０４１３】
また、本実施形態の公開鍵暗号システムは、３台のコンピュータを用いているが、それぞれについて、コンピュータに代えて、加算器・乗算器等を備えた専用計算装置としても実現できる。
【０４１４】
（パラメータ生成装置（ＰＣ  Ｃ４３０）の構成）
ＰＣ  Ｃ４３０は、上記の第１の実施形態又は第２の実施形態で示したパラメータ生成装置であって、パラメータｘとパラメータＮとを出力するように構成されている。
【０４１５】
（暗号化装置（ＰＣ  Ａ４１０）の構成）
ＰＣ  Ａ４１０は、本発明の公開鍵暗号システムを構成する暗号化装置であって、図１２に示すように構成されている。即ち、メモリ４１１、整数取得部４１３、公開鍵受付部４１２、暗号化部４１４、暗号化メッセージ送信部４１５、一時メモリ４１１ｈ、制御部４１６を備える。一時メモリ４１１ｈは、各部の計算過程を一時的に格納することができるように構成されている。また制御部４１６は、全体の動作を制御できるように構成されている。
【０４１６】
尚、本ＰＣ  Ａ４１０を上述のように構成する事で、本発明の暗号化装置を実現することができる。また、本ＰＣ  Ａ４１０を使用することで、本発明の第２の暗号化方法を実施することができる。
【０４１７】
（暗号化装置（ＰＣ  Ａ４１０）の各部の構成）
メモリ４１１は、ＰＣ  Ｃ４３０の出力したパラメータｘとパラメータＮ、整数ｒ、公開鍵Ｔ、メッセージｍ及び暗号化メッセージ（ｃ１，ｃ２）を格納できるよう構成されている。
【０４１８】
整数取得部４１３は、大きな奇数である整数ｒを取得し、メモリ４１１の領域４１１ｄに格納できるよう構成されている。
【０４１９】
公開鍵受付部４１２は、ＰＣ  Ａ４１０の外部に公開されている公開鍵Ｔを受け付け、領域４１１ｃに格納できるよう構成されている。
【０４２０】
暗号化部４１４は、予め計算式ｃ１＝Ｔｒ（ｘ）  ｍｏｄ  Ｎ及びｃ２＝ｍＴｒ（Ｔ）  ｍｏｄ  Ｎが記憶されており、領域４１１ｅに格納されている奇数であるメッセージｍ（０＜ｍ＜Ｎ）と、領域４１１ｄに格納されている整数ｒと、領域４１１ａに格納されているパラメータｘと、領域４１１ｂに格納されているパラメータＮと、領域４１１ｃに格納されている公開鍵Ｔとから、
ｃ１＝Ｔｒ（ｘ）  ｍｏｄ  Ｎ
ｃ２＝ｍＴｒ（Ｔ）  ｍｏｄ  Ｎ
により整数の組である暗号化メッセージ（ｃ１，ｃ２）を計算し、ｃ１を領域４１１ｆに、ｃ２を領域４１１ｇに格納できるよう構成されている。
【０４２１】
暗号化メッセージ送信部４１５は、領域４１１ｆ及び４１１ｇに格納されている暗号化メッセージ（ｃ１，ｃ２）を、ＰＣ  Ａ４1０の外部へ送信できるよう構成されている。
【０４２２】
（鍵対生成装置兼復号化装置（ＰＣ  Ｂ４２０）の構成）
ＰＣ  Ｂ４２０は、本発明の公開鍵暗号システムを構成する鍵対生成装置と復号化装置を兼ねており、図１３に示すように構成されている。即ち、メモリ４２１、整数取得部４２２ａ、公開鍵計算部４２２ｂ、公開鍵公開部４２２ｃ、秘密鍵出力部４２２ｄ、暗号化メッセージ受信部４２３ａ、秘密鍵入力部４２３ｂ、中間整数計算部４２３ｃ、復号化部４２３ｄ、一時メモリ４２１ｉ、制御部４２４を備える。一時メモリ４２１ｉは、各部の計算過程を一時的に格納することができるように構成されている。また制御部４２４は、全体の動作を制御できるように構成されている。
【０４２３】
なお、鍵対生成装置に対応する部分としては、メモリ４２１内の領域４２１ａ、４２１ｂ及び４２１ｃ、整数取得部４２２ａ、公開鍵計算部４２２ｂ、公開鍵公開部４２２ｃ、秘密鍵出力部４２２ｄ等であり、復号化装置に対応する部分としては、メモリ４２１内の領域４２１ｄ、４２１ｅ、４２１ｆ、４２１ｇ及び４２１ｈ、暗号化メッセージ受信部４２３ａ、秘密鍵入力部４２３ｂ、中間整数計算部４２３ｃ、復号化部４２３ｄ等である。
【０４２４】
また、本ＰＣ  Ｂ４２０を使用することで、本発明の鍵対生成方法、復号化方法を実施することができる。
【０４２５】
（鍵対生成装置兼復号化装置（ＰＣ  Ｂ４２０）の各部の構成）
メモリ４２１は、ＰＣ  Ｃ４３０の出力したパラメータｘとパラメータＮ、整数ｓ、暗号化メッセージｃ１及びｃ２、中間整数α、公開鍵Ｔ及びメッセージｍ’を格納できるよう構成されている。
【０４２６】
整数取得部４２２ａは、大きな奇数である整数ｓを取得し、メモリ４２１の領域４２１ｃに格納できるように構成されている。
【０４２７】
公開鍵計算部４２２ｂは、予め計算式Ｔ＝Ｔｓ（ｘ）  ｍｏｄ  Ｎを記憶しており、メモリ４２１内の領域４２１ｃに格納されたパラメータｓと領域４２１ａに格納されたパラメータｘと領域４２１ｂに格納されたパラメータＮとから、
Ｔ＝Ｔｓ（ｘ）  ｍｏｄ  Ｎ
により公開鍵Ｔを計算し、メモリ４２１内の領域４２１ｈに格納できるように構成されている。
【０４２８】
公開鍵公開部４２２ｃは、領域４２１ｈに格納されている公開鍵ＴをＰＣ  Ｂ４２０の外部に公開できるよう構成されている。
【０４２９】
秘密鍵出力部４２２ｄは、領域４２１ｃに格納されている整数ｓを秘密鍵として秘密鍵入力部４２３ｂに出力できるよう構成されている。
【０４３０】
暗号化メッセージ受信部４２３ａは、ＰＣ  Ｂ４２０の外部から入力された暗号化メッセージ（ｃ１，ｃ２）を入力し、メモリ４２１内の領域４２１ｄ及び４２１ｅに格納できるように構成されている。
【０４３１】
秘密鍵入力部４２３ｂは、秘密鍵出力部４２２ｄから入力された秘密鍵である整数ｓを入力し、メモリ４２１内の領域４２１ｃに格納できるように構成されている。
【０４３２】
中間整数計算部４２３ｃは、予め拡張ユークリッドの互除法が実現できるよう構成されており、領域４２１ｃに格納された秘密鍵である整数ｓと領域４２１ｄに格納された暗号化メッセージの第１成分ｃ１と領域４２１ｂに格納されたパラメータＮとから、
１＝αＴｓ（ｃ１）  ｍｏｄ  Ｎ
を満たす中間整数αを計算し、メモリ４２１内の領域４２１ｆに格納できるように構成されている。なお、拡張ユークリッドの互除法の代わりに、フェルマーの小定理を用いてＴｓ（ｃ１）の適当な冪乗を計算してもこれを満たすαが得られる。
【０４３３】
復号化部４２３ｅは、予め計算式ｍ’＝αｃ２  ｍｏｄ  Ｎが記憶されており、領域４２１ｆに格納された中間整数αと領域４２１ｅに格納された暗号化メッセージの第２成分ｃ２と領域４２１ｂに格納されたパラメータＮとから、
ｍ’＝αｃ２  ｍｏｄ  Ｎ
を計算してメッセージｍ’を計算し、メモリ４２１内の領域４２１ｇに格納できるように構成されている。
【０４３４】
（構成のまとめ）
このように、本実施形態の公開鍵暗号システムは、３台のコンピュータを用いて上述のように構成されており、ＰＣ  Ｃ４３０の生成したパラメータｘとパラメータＮを用い、ＰＣ  Ａ４１０が作成した暗号化メッセージをＰＣ  Ｂ４２０で復号化することができる。
【０４３５】
（動作）
以下、本公開鍵暗号システム４００の動作について説明する。図１４は本公開鍵暗号システム４００の動作全体の流れを示すフローチャートである。以下、図１４を用い、本第４の実施形態の動作を説明する。
【０４３６】
（事前処理）
ＰＣ  Ａ４１０に備えられているメモリ４１１の領域４１１ｅには、予め奇数であるメッセージｍ（０＜ｍ＜Ｎ）が格納されている。
【０４３７】
（ステップＳ５１０）
ＰＣ  Ｃ４３０の動作により、パラメータｘとパラメータＮが生成され、インターネット４４０を通じＰＣ  Ａ４１０及びＰＣ  Ｂ４２０に配信される。
【０４３８】
（ステップＳ５２０）
ＰＣ  Ｂ４２０は、インターネット４４０を通じＰＣ  Ｃ４３０から受け取ったパラメータｘをメモリ４２１内の領域４２１ａに、パラメータＮを領域４２１ｂに格納する。
【０４３９】
ＰＣ  Ｂ４２０内の整数取得部４２２ａは、正の奇数である整数ｓを取得し、メモリ４２１内の領域４２１ｃに格納する。
【０４４０】
公開鍵計算部４２２ｂは、領域４２１ｃに格納されている整数ｓと領域４２１ａに格納されているパラメータｘと領域４２１ｂに格納されているパラメータＮを読み出し、
Ｔ＝Ｔｓ（ｘ）  ｍｏｄ  Ｎ    
により公開鍵Ｔを計算し、領域４２１ｈに格納する。
【０４４１】
公開鍵公開部４２２ｃは、領域４２１ｈに格納されている公開鍵Ｔを読み出し、インターネット４４０へ公開する。
【０４４２】
秘密鍵出力部４２２ｄは、領域４２１ｃに格納されている整数ｓを読み出し、秘密鍵として秘密鍵入力部４２３ｂに出力する。
【０４４３】
（ステップＳ５３０）
一方、ＰＣ  Ａ４１０は、インターネット４４０を通じＰＣ  Ｃ４３０から受け取ったパラメータｘをメモリ４１１内の領域４１１ａに、パラメータＮを領域４１１ｂに格納する。
【０４４４】
公開鍵受付部４１２は、ＰＣ  Ｂ４２０内の公開鍵公開部４２２ｃが公開した公開鍵Ｔを受け付け、メモリ４１１内の領域４１１ｃに格納する。
【０４４５】
整数取得部４１３は、正の奇数である整数ｒを取得し、メモリ４１１内の領域４１１ｄに格納する。
【０４４６】
暗号化部４１４は、領域４１１ｅに格納されているメッセージｍと、領域４１１ｄに格納されている整数ｒと、領域４１１ａに格納されているパラメータｘと、領域４１１ｂに格納されているパラメータＮと、領域４１１ｃに格納されている公開鍵Ｔとを読み出し、
ｃ１＝Ｔｒ（ｘ）  ｍｏｄ  Ｎ
ｃ２＝ｍＴｒ（Ｔ）  ｍｏｄ  Ｎ
により整数の組である暗号化メッセージ（ｃ１，ｃ２）を計算し、第１成分ｃ１を領域４１１ｆに、第２成分ｃ２を領域４１１ｇに格納する。
【０４４７】
暗号化メッセージ送信部４１５は、領域４１１ｆ及び４１１ｇに格納されている暗号化メッセージ（ｃ１，ｃ２）を読み出し、ＰＣ  Ｂ４２０内の暗号化メッセージ受信部４２３ａへ送信する。
【０４４８】
（ステップＳ５４０）
ＰＣ  Ｂ４２０の暗号化メッセージ受信部４２３ａは、ＰＣ  Ａ４１０の暗号化メッセージ送信部４１５が送信した暗号化メッセージ（ｃ１，ｃ２）を受信し、メモリ４２１内の領域４２１ｄに第１成分ｃ１を、領域４２１ｅに第２成分ｃ２を格納する。
【０４４９】
秘密鍵入力部４２３ｂは、秘密鍵出力部４２２ｄが秘密鍵として出力した整数ｓを入力し、メモリ４２１上の領域４２１ｃに格納する。
【０４５０】
中間整数計算部４２３ｃは、領域４２１ｃに格納されている整数ｓと領域４２１ｄに格納されている暗号化メッセージ（ｃ１，ｃ２）の第１成分ｃ１と領域４２１ｂに格納されているパラメータＮとを読み出し、
１＝αＴｓ（ｃ１）  ｍｏｄ  Ｎ
を満たす中間整数αを求め、メモリ４２１内の領域４２１ｆに格納する。
【０４５１】
復号化部４２３ｄは、領域４２１ｅに格納されている暗号化メッセージ（ｃ１，ｃ２）の第２成分ｃ２と領域４２１ｆに格納されている中間整数αと領域４２１ｂに格納されているパラメータＮを読み出し、
ｍ’＝αｃ２  ｍｏｄ  Ｎ
によりメッセージｍ’を得、領域４２１ｇに格納する。
【０４５２】
（動作のまとめ）
このメッセージｍ’は、暗号化装置が送信した元のメッセージｍと等しく、本第４の実施形態は、公開鍵暗号システムとして用いる事ができる。
【０４５３】
（第４の実施形態の変形例）
本第４の実施形態では、ＰＣ  Ｂ４２０が本発明の鍵対生成装置と復号化装置を兼ねた形態であるが、変形例は、鍵対生成装置と復号化装置とを別々の装置とする形態である。
【０４５４】
本変形例では、便宜上、図１３を用いて説明すると、鍵対生成装置は、領域４２１ａ、４２１ｂ及び４２１ｃを有するメモリ、整数取得部４２２ａ、公開鍵計算部４２２ｂ、公開鍵公開部４２２ｃ、秘密鍵出力部４２２ｄ等を備えた装置であり、復号化装置に対応する部分としては、領域４２１ｄ、４２１ｅ、４２１ｆ、４２１ｇ及び４２１ｈを有するメモリ、暗号化メッセージ受信部４２３ａ、秘密鍵入力部４２３ｂ、中間整数計算部４２３ｃ、復号化部４２３ｄ等を備えた装置である。
【０４５５】
鍵対生成装置の動作、及び、復号化装置の動作は、装置が分離したことに伴う違いを除けば、基本的には、第４の実施形態と同様である。
【０４５６】
（第４の実施形態の第２の変形例）
また本第４の実施形態の第２の変形例は、暗号化と復号化を第４の実施形態と異なる方式で行う公開鍵暗号システムとする形態である。即ち、本発明の第３の公開暗号鍵システムの実施形態である。
【０４５７】
この変形例は、全体を図１０と同様な、又は、上記の変形例と同様な形態とし、暗号化部４１４及び復号化部４２３ｄの構成を変える事により実施する。これを便宜上、図１２と図１３を用いて説明する。
【０４５８】
暗号化部４１４は、予め計算式ｃ１＝Ｔｒ（ｘ）  ｍｏｄ  Ｎ及びｃ２＝（Ｔｒ（Ｔ）  ｍｏｄ  Ｎ）  ｘｏｒ  ｍを記憶しており、メモリ４１１内の領域４１１ｅに格納された整数であるメッセージｍ（０≦ｍ＜Ｎ）と、領域４１１ｄに格納された整数ｒと、領域４１１ａに格納されたパラメータｘと、領域４１１ｂに格納されたパラメータＮと、領域４１１ｃに格納されている公開鍵Ｔとから、
ｃ１＝Ｔｒ（ｘ）  ｍｏｄ  Ｎ
ｃ２＝（Ｔｒ（Ｔ）  ｍｏｄ  Ｎ）  ｘｏｒ  ｍ
により整数の組である暗号化メッセージ（ｃ１，ｃ２）を計算し、第１成分ｃ１をメモリ４１１内の領域４１１ｆに、第２成分ｃ２を領域４１１ｇに格納できるように構成されている。
【０４５９】
また復号化部４２３ｄは、予め計算式ｍ’＝（Ｔｓ（ｃ１）  ｍｏｄ  Ｎ）  ｘｏｒ  ｃ２を記憶しており、メモリ４２１内の領域４２１ｃに格納された整数ｓと、領域４２１ｄ及び４２１ｅに格納された暗号化メッセージ（ｃ１，ｃ２）と、領域４２１ｂに格納されたパラメータＮとから、
ｍ’＝（Ｔｓ（ｃ１）  ｍｏｄ  Ｎ）  ｘｏｒ  ｃ２
によりメッセージｍ’を得、メモリ４２１内の領域４２１ｇに格納できるように構成されている。
【０４６０】
本変形例の動作は、上記のように構成された暗号化部４１４と復号化部４２３ｄが動作する事以外は第４の実施形態と同じであるため、説明は省略する。尚、本変形例において、中間整数計算部４２３ｃは抹消したものとする。
【０４６１】
復号化装置４２３ｄで計算されたメッセージｍ’は、暗号化装置の送信したメッセージｍに等しい。このように本変形例は、暗号化装置の送信した暗号化メッセージを復号化装置で復号するという、公開鍵暗号システムとして用いることができる。
【０４６２】
＜第５の実施形態＞
第５の実施形態として、本発明の電子署名システムの実施形態を説明する。本発明の電子署名システムは、本発明のパラメータ生成装置又はパラメータ生成方法によって生成されたパラメータｘと、パラメータＮと、更に整数ｅを用いた電子署名システムである。図１５は電子署名システムの概要構成を示す模式図である。以下、本図を参照しつつ本実施形態の電子署名システム５００について説明する。
【０４６３】
（システム全体の構成）
本実施形態の電子署名システム５００は、３台のコンピュータＰＣ  Ａ５１０、ＰＣ  Ｂ５２０及びＰＣ  Ｃ５３０がインターネット５４０を介して相互に接続されている。ここでは３台のコンピュータを考えているが、ＰＣ  Ｃ５３０は、ＰＣ  Ａ５１０又はＰＣ  Ｂ５２０のどちらかに含むように構成することもできる。図１６はＰＣ  Ａの構成を示すブロック図、図１７はＰＣ  Ｂの構成を示すブロック図である。以下、これらの図も参照しながら説明する。
【０４６４】
ＰＣ  Ｃ５３０は、パラメータｘとパラメータＮと整数ｅを出力するパラメータ生成装置である。ＰＣ  Ａ５１０は、本発明の電子署名システムに含まれる認証装置であって、ＰＣ  Ｂ５２０は、本発明の電子署名システムに含まれる鍵対生成装置と署名装置を兼ねている。なお、本実施形態では、本発明のパラメータ生成装置が生成し出力したパラメータｘと、それに対応するパラメータＮとを用いるために、パラメータ生成装置であるＰＣ  Ｃ５３０が、電子署名システムの一部を構成している。但し、本発明の電子署名システムとしては、パラメータ生成装置がシステムの一部を構成しなくても、パラメータ生成装置が生成し出力したパラメータｘと、それに対応するパラメータＮとを本システムが用いていればよい。
【０４６５】
また、本実施形態の電子署名システムは、３台のコンピュータを用いているが、それぞれについて、コンピュータに代えて、加算器・乗算器等を備えた専用計算装置としても実現できる。
【０４６６】
（パラメータ生成装置（ＰＣ  Ｃ５３０）の構成）
ＰＣ  Ｃ５３０は、上記の第１の実施形態又は第２の実施形態で示したパラメータ生成装置であって、パラメータｘとパラメータＮと整数ｅを出力するように構成されている。
【０４６７】
（認証装置（ＰＣ  Ａ５１０）の構成）
ＰＣ  Ａ５１０は、本発明の電子署名システムを構成する認証装置であって、図１６に示すように構成されている。即ち、メモリ５１１、公開鍵受付部５１２、署名付メッセージ受信部５１３、整数計算部５１４、認証部５１５、一時メモリ５１１ｈ、制御部５１６を備える。一時メモリ５１１ｈは、各部の計算過程を一時的に格納することができるように構成されている。また制御部５１６は、全体の動作を制御できるように構成されている。
【０４６８】
尚、本ＰＣ  Ａ５１０を上述のように構成する事で、本発明の認証装置を実現することができる。また、本ＰＣ  Ａ５１０を使用することで、本発明の認証方法を実施することができる。
【０４６９】
（認証装置（ＰＣ  Ａ５１０）の各部の構成）
メモリ５１１は、ＰＣ  Ｃ５３０の出力したパラメータｘとパラメータＮ、公開鍵Ｔ、メッセージｍ及び署名付メッセージ（ａ，ｂ，ｍ）を格納できるよう構成されている。
【０４７０】
公開鍵受付部５１２は、ＰＣ  Ａ５１０の外部に公開されている公開鍵Ｔを受け付け、領域５１１ｃに格納できるよう構成されている。
【０４７１】
署名付メッセージ受信部５１３は、ＰＣ  Ｂ５２０内の署名付メッセージ送信部５２３ｄが送信した署名付メッセージ（ａ，ｂ，ｍ）を受信し、第１成分ａを領域５１１ｄに、第２成分ｂを領域５１１ｅに、第３成分ｍを領域５１１ｆに格納できるように構成されている。
【０４７２】
整数計算部５１４は、予めハッシュ関数ｈと計算式Ｗ＝Ｔｈ（ｍ）（ｘ）２−２Ｔｈ（ｍ）（ｘ）Ｔａ（Ｔ）Ｔｂ（ａ）＋Ｔａ（Ｔ）２＋Ｔｂ（ａ）２−１  ｍｏｄ  Ｎが記憶されており、領域５１１ｄ、５１１ｅ及び５１１ｆに格納されている署名付メッセージ（ａ，ｂ，ｍ）と、領域５１１ａに格納されているパラメータｘと、領域５１１ｃに格納されている公開鍵Ｔと、領域５１１ｂに格納されているパラメータＮを読み出し、整数ｈ（ｍ）をハッシュ関数ｈを用いて計算し、更に、整数Ｗを前記計算式を用いて計算し、整数Ｗを領域５１１ｇに格納できるように構成されている。
【０４７３】
認証部５１５は、領域５１１ｇに格納された整数Ｗを読み出し、その値が０に等しい場合、署名付メッセージ（ａ，ｂ，ｍ）を認証することができるように構成されている。
【０４７４】
（鍵対生成装置兼署名装置（ＰＣ  Ｂ５２０）の構成）
ＰＣ  Ｂ５２０は、本発明の電子署名システムを構成する鍵対生成装置と署名装置を兼ねており、図１７に示すように構成されている。即ち、メモリ５２１、整数取得部５２２ａ、公開鍵計算部５２２ｂ、公開鍵公開部５２２ｃ、秘密鍵出力部５２２ｄ、整数発生部５２３ａ、秘密鍵入力部５２３ｂ、署名部５２３ｃ、署名付メッセージ送信部５２３ｄ、一時メモリ５２１ｌ、制御部５２４を備える。一時メモリ５２１ｌは、各部の計算過程を一時的に格納することができるように構成されている。また制御部５２４は、全体の動作を制御できるように構成されている。
【０４７５】
なお、鍵対生成装置に対応する部分としては、メモリ５２１内の領域５２１ａ、５２１ｂ、５２１ｃ及び５２１ｉ、整数取得部５２２ａ、公開鍵計算部５２２ｂ、公開鍵公開部５２２ｃ、秘密鍵出力部５２２ｄ等であり、署名装置に対応する部分としては、メモリ５２１内の領域５２１ｄ、５２１ｅ、５２１ｆ、５２１ｇ、５２１ｈ、５２１ｊ及び５２１ｋ、整数発生部５２３ａ、秘密鍵入力部５２３ｂ、署名部５２３ｃ、署名付メッセージ送信部５２３ｄ等である。
【０４７６】
また、本ＰＣ  Ｂ５２０を使用することで、本発明の鍵対生成方法、署名方法を実施することができる。
【０４７７】
（鍵対生成装置兼署名装置（ＰＣ  Ｂ５２０）の各部の構成）
メモリ５２１は、ＰＣ  Ｃ５３０の出力したパラメータｘとパラメータＮと整数ｅ、整数ｓ、署名付メッセージ（ａ，ｂ，ｍ）、整数ｋ、整数ｋ’、公開鍵Ｔ及び整数Ｍを格納できるよう構成されている。
【０４７８】
整数発生部５２３ａは、メモリ５２１内の領域５２１ｊから整数ｅを読み出し、整数Ｍを２ｅに設定し、領域５２１ｋに格納することができるように構成されている。ここで、Ｍは、２ｅ倍数であってＮ以下のものであれば何でもよいが、高速化のために最小の２ｅに設定する。また整数発生部５２３ａは、設定した整数Ｍと互いに素な正の整数ｋを発生させ、領域５２１ｇに格納できるように構成されている。ここで、整数Ｍは２の冪乗なので、正の奇数ｋを発生すれば、Ｍと互いに素になっている。整数発生部５２３ａは更に、計算式１
＝ ｋ’ｋ  ｍｏｄ Ｍを予め記憶しており、上記の設定した整数Ｍと発生させた整数ｋとから拡張ユークリッドの互除法を用いて、
１ ＝
ｋ’ｋ  ｍｏｄ Ｍ
を満たす正の整数ｋ’を発生させ、領域５２１ｈに格納することができるように構成されている。なお、拡張ユークリッドの互除法の代わりに、フェルマーの小定理を用いてｋの適当な冪乗を計算してもこれを満たすｋ’が得られる。
【０４７９】
秘密鍵入力部５２３ｂは、秘密鍵出力部５２２ｄが秘密鍵として出力した整数ｓを入力し、領域５２１ｃに格納することができるように構成されている。
【０４８０】
署名部５２３ｃは、予めハッシュ関数ｈと計算式ａ＝Ｔｋ（ｘ）  ｍｏｄ  Ｎ及びｂ＝ｋ’（ｓａ＋ｈ（ｍ））  ｍｏｄ  Ｍが記憶されており、領域５２１ｇに格納されている整数ｋと、領域５２１ｈに格納されている整数ｋ’と、領域５２１ａに格納されているパラメータｘと、領域５２１ｃに格納されている秘密鍵である整数ｓと、領域５２１ｆに格納されている整数であるメッセージｍ（０≦ｍ＜Ｎ）と、領域５２１ｋに格納されている整数Ｍと、領域５２１ｂに格納されているパラメータＮとを読み出し、
ａ＝Ｔｋ（ｘ）  ｍｏｄ  Ｎ
ｂ＝ｋ’（ｓａ＋ｈ（ｍ））  ｍｏｄ  Ｍ
により署名付メッセージ（ａ，ｂ，ｍ）を計算し、整数ａ、整数ｂ及び整数ｍをそれぞれ領域５２１ｄ、５２１ｅ及び５２１ｆに格納できるように構成されている。
【０４８１】
署名付メッセージ送信部５２３ｄは、領域５２１ｄ、５２１ｅ及び５２１ｆにそれぞれ格納されている整数ａ、ｂ及びｍを読み出し、署名付メッセージ（ａ，ｂ，ｍ）としてＰＣ  Ａ５１０の署名付メッセージ受信部５１３へ送信することができるように構成されている。
【０４８２】
（構成のまとめ）
このように、本実施形態の電子署名システムは、３台のコンピュータを用いて上述のように構成されており、ＰＣ  Ｃ５３０の生成したパラメータｘとパラメータＮを用い、ＰＣ  Ｂ５２０が作成した署名付メッセージをＰＣ  Ａ５１０で認証することができる。
【０４８３】
（動作）
以下、本電子署名システム５００の動作について説明する。図１８は本電子署名システム５００の動作全体の流れを示すフローチャートである。以下、図１８を用い、本第５の実施形態の動作を説明する。
【０４８４】
（事前処理）
ＰＣ  Ｂ５２０内に備えられたメモリ５２１内の領域５２１ｆには予め正の整数であるメッセージｍが格納されている。
【０４８５】
（ステップＳ６１０）
ＰＣ  Ｃ５３０の動作により、パラメータｘとパラメータＮと整数ｅが生成され、インターネット５４０を通じ、ＰＣ  Ａ５１０にパラメータｘとパラメータＮが、ＰＣ  Ｂ５２０にパラメータｘとパラメータＮと整数ｅが配信される。
【０４８６】
（ステップＳ６２０）
ＰＣ  Ｂ５２０は、インターネット５４０を通じＰＣ  Ｃ５３０から受け取ったパラメータｘをメモリ５２１内の領域５２１ａに、パラメータＮを領域５２１ｂに、整数ｅを領域５２１ｊに格納する。
【０４８７】
整数取得部５２２ａは、大きい正の整数ｓを取得し、メモリ５２１内の領域５２１ｃに格納する。
【０４８８】
公開鍵計算部５２２ｂは、メモリ５２１内の領域５２１ｃに格納されている整数ｓと、領域５２１ａに格納されているパラメータｘと、領域５２１ｂに格納されているパラメータＮを読み込み、
Ｔ＝Ｔｓ（ｘ）  ｍｏｄ  Ｎ
により公開鍵Ｔを計算し、領域５２１ｉに格納する。
【０４８９】
公開鍵公開部５２２ｃは、領域５２１ｉに格納されている公開鍵Ｔを読み出し、ＰＣ  Ａ５１０内の公開鍵受付部５１２に公開する。
【０４９０】
秘密鍵出力部５２２ｄは、領域５２１ｓに格納されている整数ｓを読み出し、秘密鍵として秘密鍵入力部５２３ｂに出力する。
【０４９１】
（ステップＳ６２０）
整数発生部５２３ａは、メモリ５２１内の領域５２１ｊから整数ｅを読み出し、整数Ｍを２ｅに設定し、領域５２１ｋに格納する。
【０４９２】
整数発生部５２３ａは引き続き、上記の設定した整数Ｍと互いに素な正の整数ｋを発生させ、領域５２１ｇに格納する。
【０４９３】
整数発生部５２３ａは更に、上記の設定した整数Ｍと、発生させた整数ｋとから、
１ ＝
ｋ’ｋ  ｍｏｄ Ｍ
を満たす正の整数ｋ’を発生させ、領域５２１ｈに格納する。
【０４９４】
秘密鍵入力部５２３ｂは、秘密鍵出力部５２２ｄが秘密鍵として出力した整数ｓを入力し、メモリ５２１内の領域５２１ｃに格納する。
【０４９５】
署名部５２３ｃは、領域５２１ｇに格納されている整数ｋと、領域５２１ｈに格納されている整数ｋ’と、領域５２１ａに格納されているパラメータｘと、領域５２１ｃに格納されている秘密鍵である整数ｓと、領域５２１ｆに格納されているメッセージｍと、領域５２１ｋに格納されている整数Ｍと、領域５２１ｂに格納されているパラメータＮとを読み出し、
ａ＝Ｔｋ（ｘ）  ｍｏｄ  Ｎ
ｂ＝ｋ’（ｓａ＋ｈ（ｍ））  ｍｏｄ  Ｍ
により署名付メッセージ（ａ，ｂ，ｍ）を計算し、整数ａを領域５２１ｄに、整数ｂを領域５２１ｅに、整数ｍを５２１ｆに格納する。
【０４９６】
署名付メッセージ送信部５２３ｄは、メモリ５２１内の領域５２１ｄに格納されている整数ａと、領域５２１ｅに格納されている整数ｂと、領域５２１ｆに格納されている整数ｍを読み出し、署名付メッセージとして（ａ，ｂ，ｍ）をＰＣ  Ａ５１０内の署名付メッセージ受信部５１３に送信する。
【０４９７】
（ステップＳ６４０）
ＰＣ  Ａ５１０の公開鍵受付部５１２は、ＰＣ  Ｂ５２０の公開鍵公開部５２２ｃが公開した公開鍵Ｔを受け付け、メモリ５１１内の領域５１１ｃに格納する。
【０４９８】
署名付メッセージ受信部５１３は、ＰＣ  Ｂ５２０の署名付メッセージ送信部５２３ｄが送信した署名付メッセージ（ａ，ｂ，ｍ）を受信し、整数ａをメモリ５１１内の領域５１１ｄに、整数ｂを領域５１１ｅに、整数ｍを領域５１１ｆにそれぞれ格納する。
【０４９９】
整数計算部５１４は、メモリ５１１内の領域５１１ｄに格納されている整数ａと、領域５１１ｅに格納されている整数ｂと、領域５１１ｆに格納されている整数ｍと、領域５１１ａに格納されているパラメータｘと、領域５１１ｃに格納されている公開鍵Ｔと、領域５１１ｂに格納されているパラメータＮとを読み出し、ハッシュ関数ｈの計算により整数整数ｈ（ｍ）を計算し、更に整数Ｗを、記憶されている計算式により計算し、メモリ５１１内の領域５１１ｇに格納する。
【０５００】
認証部５１５は、領域５１１ｇに格納された整数Ｗを読み出し、その値が０に等しい場合、署名付メッセージ（ａ，ｂ，ｍ）を認証する。
【０５０１】
（動作のまとめ）
本署名システム５００において、ＰＣ  Ｂ５２０が作成した署名付メッセージ（ａ，ｂ，ｍ）の第２成分ｂは、秘密鍵である整数ｓを知っている装置によってしか作成できない。このため、ＰＣ  Ｂ５２０の作成した署名付メッセージをＰＣ  Ａ５１０が認証するという本第５の実施形態は、電子署名システムとして用いることができる。
【０５０２】
（第５の実施形態の変形例）
本第５の実施形態では、ＰＣ  Ｂ５２０が本発明の鍵対生成装置と署名装置を兼ねた形態であるが、変形例は、鍵対生成装置と署名装置とを別々の装置とする形態である。
【０５０３】
本変形例では、便宜上、図１７を用いて説明すると、鍵対生成装置は、領域５２１ａ、５２１ｂ、５２１ｃ及び５２１ｉを有するメモリ、整数取得部５２２ａ、公開鍵計算部５２２ｂ、公開鍵公開部５２２ｃ、秘密鍵出力部５２２ｄ等を備えた装置であり、署名装置に対応する部分としては、領域５２１ｄ、５２１ｅ、５２１ｆ、５２１ｇ、５２１ｈ、５２１ｊ及び５２１ｋを有するメモリ、整数発生部５２３ａ、秘密鍵入力部５２３ｂ、署名部５２３ｃ、署名付メッセージ送信部５２３ｄ等を備えた装置である。
【０５０４】
鍵対生成装置の動作、及び、復号化装置の動作は、装置が分離したことに伴う違いを除けば、基本的には、第５の実施形態と同様である。
【図面の簡単な説明】
【０５０５】
【図１】図１は、本発明の第１の実施形態に係るパラメータ生成装置の構成を例示したブロック図である。
【図２】図２は、本発明の第１の実施形態に係るパラメータ生成装置の処理の全体を説明するためのフローチャートである。
【図３】図３は、図２のステップＳ１００の詳細を説明するためのフローチャートである。
【図４】図４は、図２のステップＳ２００の詳細を説明するためのフローチャートである。
【図５】図５は、本発明の第２の実施形態に係るパラメータ生成装置の構成を例示したブロック図である。
【図６】図６は、本発明の第２の実施形態に係るパラメータ生成装置の処理を説明するためのフローチャートである。
【図７】図７は、本発明の第３の実施形態に係る公開鍵暗号システムの構成を例示した模式図である。
【図８】図８は、本発明の第３の実施形態に係るコンピュータを用いて実現した第１の鍵共有装置の構成を例示したブロック図である。
【図９】図９は、本発明の第３の実施形態に係るコンピュータを用いて実現した送付鍵生成装置及び第２の鍵共有装置の構成を例示したブロック図である。
【図１０】図１０は、本発明の第３の実施形態に係る公開鍵暗号システムの処理の全体を説明するためのフローチャートである。
【図１１】図１１は、本発明の第４の実施形態に係る公開鍵暗号システムの構成を例示した模式図である。
【図１２】図１２は、本発明の第４の実施形態に係るコンピュータを用いて実現した暗号化装置の構成を例示したブロック図である。
【図１３】図１３は、本発明の第４の実施形態に係るコンピュータを用いて実現した鍵対生成装置及び復号化装置の構成を例示したブロック図である。
【図１４】図１４は、本発明の第４の実施形態に係る公開鍵暗号システムの処理の全体を説明するためのフローチャートである。
【図１５】図１５は、本発明の第５の実施形態に係る電子署名システムの構成を例示した模式図である。
【図１６】図１６は、本発明の第５の実施形態に係るコンピュータを用いて実現した認証装置の構成を例示したブロック図である。
【図１７】図１７は、本発明の第５の実施形態に係るコンピュータを用いて実現した鍵対生成装置及び署名装置の構成を例示したブロック図である。
【図１８】図１８は、本発明の第５の実施形態に係る電子署名システムの処理の全体を説明するためのフローチャートである。
【符号の説明】
【０５０６】
１００  パラメータ生成装置
１１０  パラメータＮ格納部          １２０  第１の所定値格納部
１３０  計算部                      １４０  出力部
１５０  第２の所定値格納部          １６０  メモリ
２００  パラメータ生成装置
２１０  パラメータＮ格納部          ２２０  第１の所定値格納部
２３０  計算部                      ２４０  出力部
２５０  第２の所定値格納部          ２６０  メモリ
３００  公開鍵暗号システム
３１０  ＰＣ  Ａ（第１の鍵共有装置）
３１１  メモリ                      ３１２  整数取得部
３１３  送付鍵計算部                ３１４  送付鍵出力部
３１５  送付鍵入力部                ３１６  共有鍵計算部
３１７  暗号化部                    ３１８  暗号化メッセージ送信部
３２０  ＰＣ  Ｂ（送付鍵生成装置兼第２の鍵共有装置）
３２１  メモリ
３２２ａ  整数取得部                ３２２ｂ  送付鍵計算部
３２２ｃ  第１送付鍵出力部          ３２２ｄ  第２送付鍵出力部
３２３ａ  第１送付鍵入力部          ３２３ｂ  第２送付鍵入力部
３２３ｃ  共有鍵計算部              ３２３ｄ  暗号化メッセージ受信部
３２３ｅ  復号化部
３３０  ＰＣ  Ｃ（パラメータ生成装置）
３４０  インターネット
４００  公開鍵暗号システム
４１０  ＰＣ  Ａ（暗号化装置）
４１１  メモリ                      ４１２  公開鍵受付部
４１３  整数取得部                  ４１４  暗号化部
４１５  暗号化メッセージ送信部
４２０  ＰＣ  Ｂ（鍵対生成装置兼復号化装置）
４２１  メモリ
４２２ａ  整数取得部                ４２２ｂ  公開鍵計算部
４２２ｃ  公開鍵公開部              ４２２ｄ  秘密鍵出力部
４２３ａ  暗号化メッセージ受信部    ４２３ｂ  秘密鍵入力部
４２３ｃ  中間整数計算部            ４２３ｄ  復号化部
４３０  ＰＣ  Ｃ（パラメータ生成装置）
４４０  インターネット
５００  電子署名システム
５１０  ＰＣ  Ａ（認証装置）
５１１  メモリ                      ５１２  公開鍵受付部
５１３  署名付メッセージ受信部      ５１４  整数計算部
５１５  認証部
５２０  ＰＣ  Ｂ（鍵対生成装置兼署名装置）
５２１  メモリ
５２２ａ  整数取得部                ５２２ｂ  公開鍵計算部
５２２ｃ  公開鍵公開部              ５２２ｄ  秘密鍵出力部
５２３ａ  整数発生部                ５２３ｂ  秘密鍵入力部
５２３ｃ  署名部                    ５２３ｄ  署名付メッセージ部
５３０  ＰＣ  Ｃ（パラメータ生成装置）
５４０  インターネット
【図１】
2010002786.tif 000003
【図２】
2010002786.tif 000004
【図３】
2010002786.tif 000005
【図４】
2010002786.tif 000006
【図５】
2010002786.tif 000007
【図６】
2010002786.tif 000008
【図７】
2010002786.tif 000009
【図８】
2010002786.tif 000010
【図９】
2010002786.tif 000011
【図１０】
2010002786.tif 000012
【図１１】
2010002786.tif 000013
【図１２】
2010002786.tif 000014
【図１３】
2010002786.tif 000015
【図１４】
2010002786.tif 000016
【図１５】
2010002786.tif 000017
【図１６】
2010002786.tif 000018
【図１７】
2010002786.tif 000019
【図１８】
2010002786.tif 000020