(57)【特許請求の範囲】
【請求項１】
送信者側の装置が受信者の公開鍵を用いて送信データを暗号化し、受信者側の装置へ送信する公開鍵暗号通信方法であって、
【数１】
0004230162.tif 000186
を受信者の秘密鍵(p,q)とし、
【数２】
0004230162.tif 000187
を受信者の公開鍵(N,k,G,H,H')として、
（１）前記送信者側の装置において、
平文x(x∈{0,1}n)に対して乱数ｒ∈{0,1}k0を選び、
この乱数ｒと受信者の公開鍵とを用いて、
【数３】
0004230162.tif 000188
を計算し(但し、n+k0+k1=k)、その結果s,tを用いて、
【数４】
0004230162.tif 000189
を計算し、さらにその結果wと受信者の公開鍵とを用いて、
【数５】
0004230162.tif 000190
を計算し、その結果yを暗号文として、前記受信者側の装置に送信し、
(２)前記受信者側の装置において、
受信者の秘密鍵を用いて、前記送信者側の装置より受信した暗号文ｙから、
【数６】
0004230162.tif 000191
を計算し、その結果を用いて、
【数７】
0004230162.tif 000192
を計算し、また、
【数８】
0004230162.tif 000193
を計算し、それから、φ(xp,xq),φ(-xp,xq),φ(xp,-xq),φ(-xp,-xq)の各々(但し、φは中国人の剰余定理によるＺ／（ｐ）×Ｚ／（ｑ）からZ/(pq)への環同型写像を表す)について、
【数９】
0004230162.tif 000194
に示すように置いて、
【数１０】
0004230162.tif 000195
を計算することで、
【数１１】
0004230162.tif 000196
に示す復号化結果(但し、復号化結果が「*」の場合、この暗号文を拒否するものとする)を算出すること
を特徴とする公開鍵暗号通信方法。
【請求項２】
請求項１記載の公開鍵暗号通信方法であって、
前記送信者側の装置において、
Jacobi記号(w/N)を公開または前記受信者側の装置に送信すること
を特徴とする公開鍵暗号通信方法。
【請求項３】
請求項１または２記載の公開鍵暗号通信方法であって、
前記送信者側の装置において、
前記wの値と前記Nの半分の値N/2との大小関係を表わす情報を公開または前記受信者側の装置に送信すること
を特徴とする公開鍵暗号通信方法。
【請求項４】
請求項１、２または３記載の公開鍵暗号通信方法であって、
前記受信者の秘密鍵を構成する素数p,qとして、これとは別の素数p',q'に対して2p'+1,2q'+1で表される素数を選ぶこと
を特徴とする公開鍵暗号通信方法。
【請求項５】
請求項１、２、３または４記載の公開鍵暗号通信方法であって、
前記ｄ(ｄ≧１)の値を可変とすること
を特徴とする公開鍵暗号通信方法。
【請求項６】
請求項１、２、３、４または５記載の公開鍵暗号通信方法であって、
前記受信者側の装置において、
前記公開情報を生成し公開すること
を特徴とする公開鍵暗号通信方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、暗号通信技術に関し、特に、適応的選択暗号文攻撃に対して強秘匿であることが証明可能な公開鍵暗号を用いた通信通信技術に関する。
【０００２】
【従来の技術】
従来より、様々な公開鍵暗号方法が提案されている。なかでも、「R.L. Rivest, A. Shamir, L. Adleman : A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, Commun. of the ACM, Vol.21, No.2, pp.120-126, 1978.」（以下、文献１と呼ぶ）に掲載されている方法が有名であり、最も普及している公開鍵暗号方法である。
【０００３】
その他には、「V.S. Miller : Use of Elliptic Curves in Cryptography, Proc. of Crypto'85, LNCS218, Springer-Verlag, pp.417-426 (1985)」（以下、文献２と呼ぶ）や、「N. Koblitz : Elliptic Curve Cryptosystems, Math. Comp., 48, 177, pp.203-209 (1987)」（以下、文献３と呼ぶ）などに記載の楕円曲線を用いた公開鍵暗号方法が知られている。
【０００４】
また、選択平文攻撃に対して安全性証明可能な公開鍵暗号方法として、「M.O. Rabin : Digital Signatures and Public-Key Encryptions as Intractable as Factorization, MIT, Technical Report, MIT/LCS/TR-212 (1979)」（以下、文献４と呼ぶ）に記載されている公開鍵暗号方法や、「T. El Gamal : A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms, IEEE Trans. On Information Theory, IT-31, 4, pp.469-472(1985)」（以下、文献５と呼ぶ）に記載されている公開鍵暗号方法や、「S. Goldwasser and S. Micali : Probabilistic Encryption, JCSS, 28, 2, pp.270-299 (1984)」（以下、文献６と呼ぶ）に記載されている公開鍵暗号方法や、「M. Blum and S. Goldwasser : An Efficient Probabilistic Public-Key Encryption Scheme which Hides All Partial Information, Proc. of Crypto'84, LNCS196, Springer-Verlag, pp.289-299 (1985)」（以下、文献７と呼ぶ）に記載されている公開鍵暗号方法や、「S. Goldwasser and M. Bellare : Lecture Notes on Cryptography, http:/www-cse.ucsd.edu/users/ mihir/ (1997)」（以下、文献８と呼ぶ）に記載されている公開鍵暗号方法や、「T. Okamoto and S. Uchiyama : A New Public-Key Cryptosystem as Secure as Factoring, Proc. of Eurocrypt'98, LNCS1403, Springer Verlag, pp.308-318 (1998)」（以下、文献９と呼ぶ）に記載されている公開鍵暗号方法などが知られている。
【０００５】
また、選択暗号文攻撃に対して安全性証明可能な公開鍵暗号方法として、「D. Dolve, C. Dwork and M. Naor : Non-Malleable Cryptography, In 23rd Annual ACM Symposium on Theory of Computing, pp.542-552 (1991)」（以下、文献１０と呼ぶ）に記載されている公開鍵暗号方法や、「M. Naor and M. Yung : Public-Key Cryptosystems Provably Secure against Chosen Ciphertext Attacks, Proc. of STOC, ACM Press, pp.427-437 (1990)」（以下、文献１１と呼ぶ）に記載されている公開鍵暗号方法や、「R. Cramer and V. Shoup : A Practical Public Key Cryptosystem Provably Secure against Adaptive Chosen Ciphertext Attack, Proc. of Crypto98, LNCS1462, Springer-Verlag, pp.13-25 (1998)」（以下、文献１２と呼ぶ）に記載されている公開鍵暗号方法などが知られている。
【０００６】
また、「M. Bellare, A. Desai, D. Pointcheval and P. Rogaway : Relations Among Notions of Security for Public-Key Encryption Schemes, Proc. of Crypto'98, LNCS1462, Springer Verlag, pp.26-45 (1998)」（以下、文献１３と呼ぶ）では、IND-CCA2(適応的選択暗号文攻撃に対して強秘匿であること)と、NM-CCA2(適応的選択暗号文攻撃に対して頑強であること)との等価性が示されている。現在、この条件を満たす公開鍵暗号方法が最も安全な暗号方法であると考えられている。
【０００７】
なお、「M. Bellare and P. Rogaway : Optimal Asymmetric Encryption  How to Encrypt with RSA, Proc. of Eurocrypt'94, LNCS950, Springer Verlag, pp.92-111 (1994)」（以下、文献１４と呼ぶ）に記載されている公開鍵暗号方法が、一方向性置換の逆関数を計算することの困難性を前提に、適応的選択暗号文攻撃に対して強秘匿であると考えられてきた。しかし、最近、「V. Shoup : OAEP Reconsidered. Available on the e-print library (2000/060), November 2000」（以下、文献１５と呼ぶ）にて、その問題点および一般的な見地からは安全性の証明が不十分であることが指摘され、その解決方法も提案されている。
【０００８】
【発明が解決しようとする課題】
さて、文献４に記載されている公開鍵暗号方法は、選択平文攻撃に対して一方向であることが当該文献において証明されている。このことは、文献４に記載されている公開鍵暗号方法が選択暗号文攻撃に弱いことを意味している。また、文献４に記載されている公開鍵暗号方法は、暗号化処理の高速性に優れているが、高速な復号化処理は期待できないという問題がある。
【０００９】
また、一般に、暗号通信では、共通鍵暗号を用いて送信データを暗号化し、この送信データの暗号化に用いた共通鍵を、公開鍵暗号を用いて暗号化することが多い。上記の各文献に記載されている公開鍵暗号方法では、一度に暗号化処理できる平文の長さが短く且つ鍵長に比例して制限されるためである。
【００１０】
例えば、文献１に記載の公開鍵暗号方法では、鍵長が１０２４ビットの場合、一度に暗号化処理できる平文の長さは１０２４ビットである。また、文献３に記載の公開鍵暗号方法では、底ｐが１６０ビットの場合、一度に暗号化処理できる平文の長さは１６０ビットである。
【００１１】
しかし、実用的な暗号通信システムでは、共通鍵の他にユーザの識別情報(ＩＤ情報)等をも一緒に送ることが多い。また、計算機能力の進歩に伴って、送信すべき鍵長は長くなる一方である。このため、一度に暗号化処理できる平文の長さが短いと、複数回に分けて暗号化する必要が生じる。複数回に分けた場合、各暗号文の平文との対応の正当性を保証する必要が生じる。このため、余計な手間がかかる。このようなことから、より長い平文を一度に暗号化することが可能な、安全性を証明可能な暗号方法が望まれている。
【００１２】
本発明は、上記事情に鑑みてなされたものであり、安全性を証明可能な公開鍵暗号通信技術を提供することにある。
【００１３】
例えば、選択暗号文攻撃に対して安全性を証明可能であり、且つ、高速な復号化処理が可能な公開鍵暗号通信技術を提供する。
【００１４】
また、送信データを暗復号化する際の計算負荷を小さくすることが可能な公開鍵暗号通信技術を提供する。
【００１５】
また、一方向性置換の逆関数を計算することの困難性（例えば素因数分解問題の困難性）を前提に、IND-CCA2であることが証明可能な公開鍵暗号通信技術を提供する。
【００１６】
【課題を解決するための手段】
上記課題を解決するために本発明の公開鍵暗号通信方法は、以下のとおりである。
【００１７】
本発明の一態様では、上記の文献４に記載されている公開鍵暗号方法をベースとし、選択暗号文攻撃に対して安全性を証明可能であり、且つ、高速な復号化処理が可能な公開鍵暗号通信方法を提供する。
【００１８】
上記の文献４に記載されている公開鍵暗号方法では、公開鍵である合成数NをN=pqと選ぶのに対して、本態様では、合成数NをN=pdq（d>1）とする。これにより、高速な復号化処理を可能とする。
【００１９】
また、上記の文献１４や文献１５に記載されている公開鍵暗号方法は、落し戸付き一方向性置換を利用することを前提としている。しかし、暗号化関数としてx2 mod N（Nは合成数）を用いる場合は一方向性置換にならない。この点について、本態様では、ハッシュ関数を復号化一意性に利用しながら、文献１４に記載されている公開鍵暗号方法と組み合わせている。これにより、選択暗号文攻撃に対する安全性を強化した。
【００２０】
本態様の公開鍵暗号通信方法の具体例は次のとおりである。
【００２１】
すなわち、送信者側の装置が受信者の公開鍵を用いて送信データを暗号化し、受信者側の装置へ送信する公開鍵暗号通信方法であって、
【００２２】
【数１６１】
0004230162.tif 000002
【００２３】
を受信者の秘密鍵(p,q)とし、
【００２４】
【数１６２】
0004230162.tif 000003
【００２５】
を受信者の公開鍵(N,k,G,H)として、
（１）前記送信者側の装置において、
平文x(x∈{0,1}n)に対して乱数ｒ∈{0,1}k0を選び、
この乱数ｒと受信者の公開鍵とを用いて、
【００２６】
【数１６３】
0004230162.tif 000004
【００２７】
を計算し(但し、n+k0+k1=k)、その結果s,tを用いて、
【００２８】
【数１６４】
0004230162.tif 000005
【００２９】
を計算し、さらにその結果wと受信者の公開鍵とを用いて、
【００３０】
【数１６５】
0004230162.tif 000006
【００３１】
を計算し、その結果yを暗号文として、前記受信者側の装置に送信し、
(２)前記受信者側の装置において、
受信者の秘密鍵を用いて、前記送信者側の装置より受信した暗号文ｙから、
【００３２】
【数１６６】
0004230162.tif 000007
【００３３】
を計算し、その結果を用いて、
【００３４】
【数１６７】
0004230162.tif 000008
【００３５】
を計算し、また、
【００３６】
【数１６８】
0004230162.tif 000009
【００３７】
を計算し、それから、φ(xp,xq),φ(-xp,xq),φ(xp,-xq),φ(-xp,-xq)の各々(但し、φは中国人の剰余定理によるZ/(p)×Z/(q)からZ/(pq)への環同型写像を表す)について、
【００３８】
【数１６９】
0004230162.tif 000010
【００３９】
に示すように置いて、
【００４０】
【数１７０】
0004230162.tif 000011
【００４１】
を計算することで、
【００４２】
【数１７１】
0004230162.tif 000012
【００４３】
に示す復号化結果を算出する。
【００４４】
ある暗号文に対して、復号化結果が「*」である場合、それは正しい復号ができなかったことを意味する。この場合、その暗号文が攻撃のためのものである可能性がある。そこで、前記受信者側の装置において、復号化結果が「*」の場合、この暗号文を拒否するものとする。つまり、前記受信者側の装置は、選択暗号文攻撃を不可能とするために、暗号文の復号を拒否し、復号化結果である平文を出力しない。このとき、前記受信者側の装置は、復号化結果を何も出力しない構成にしてもよいし、あるいは、復号できなかった旨を操作者に通知する構成にしてもよい。
【００４５】
また、本発明の別の態様は、以下のとおりである。
【００４６】
すなわち、送信者側の装置が受信者の公開鍵を用いて送信データを暗号化し、受信者側の装置へ送信する公開鍵暗号通信方法であって、
【００４７】
【数１７２】
0004230162.tif 000013
【００４８】
を受信者の公開鍵とし、
【００４９】
【数１７３】
0004230162.tif 000014
【００５０】
を受信者の秘密鍵(但し、k=k0+k1+n)として、
（１）前記送信者側の装置において、
平文x(x∈{0,1}n)に対して乱数ｒ∈{0,1}k0を選び、
この乱数ｒと受信者の公開鍵とを用いて、
【００５１】
【数１７４】
0004230162.tif 000015
【００５２】
を計算し、その結果s,tと受信者の公開鍵とを用いて、
【００５３】
【数１７５】
0004230162.tif 000016
【００５４】
を計算し、その結果y1,y2を暗号文として前記受信者の装置に送信し、
（２）前記受信者側の装置において、
受信者の秘密鍵を用いて、前記送信者側の装置より受信した暗号文y1,y2から、
【００５５】
【数１７６】
0004230162.tif 000017
【００５６】
を計算し、その結果を用いて、
【００５７】
【数１７７】
0004230162.tif 000018
【００５８】
を計算し、さらにその結果を用いて、
【００５９】
【数１７８】
0004230162.tif 000019
【００６０】
に示す復号化結果(但し、復号化結果が「*」の場合、この暗号文を拒否するものとする。また、[a]nおよび[a]nは、それぞれaの上位および下位nビットを表す)を算出する。
【００６１】
ある暗号文に対して、復号化結果が「*」である場合、それは正しい復号ができなかったことを意味する。この場合、その暗号文が攻撃のためのものである可能性がある。そこで、前記受信者側の装置において、復号化結果が「*」の場合、この暗号文を拒否するものとする。つまり、前記受信者側の装置は、選択暗号文攻撃を不可能とするために、暗号文の復号を拒否し、復号化結果である平文を出力しない。このとき、前記受信者側の装置は、復号化結果を何も出力しない構成にしてもよいし、あるいは、復号できなかった旨を操作者に通知する構成にしてもよい。
【００６２】
本態様の公開鍵暗号通信方法の具体例は次のとおりである。
【００６３】
すなわち、送信者側の装置が受信者の公開鍵を用いて送信データを暗号化し、受信者側の装置へ送信する公開鍵暗号通信方法であって、
【００６４】
【数１７９】
0004230162.tif 000020
【００６５】
を受信者の秘密鍵(p,q)とし、
【００６６】
【数１８０】
0004230162.tif 000021
【００６７】
を受信者の公開鍵(N,k,G,H)として、
（１）前記送信者側の装置において、
平文x(x∈{0,1}n)に対して乱数ｒ∈{0,1}k0を選び、
この乱数ｒと受信者の公開鍵とを用いて、
【００６８】
【数１８１】
0004230162.tif 000022
【００６９】
を計算し(但し、n+k0+k1<k-2)、その結果s,tと受信者の公開鍵とを用いて、
【００７０】
【数１８２】
0004230162.tif 000023
【００７１】
を計算し（但し、a=(m/N)はJacobi記号を表す）、その結果y1,y2,y3を暗号文として、前記受信者の装置に送信し、
（２）前記受信者側の装置において、
受信者の秘密鍵を用いて、前記送信者側の装置より受信した暗号文y1,y2,y3から、
【００７２】
【数１８３】
0004230162.tif 000024
【００７３】
を計算し、それから、φ(x1,p,x1,q),φ(-x1,p,x1,q),φ(x1,p,-x1,q),φ(-x1,p,-x1,q)のうち(但し、φは中国人の剰余定理によるZ/(p)×Z/(q)からZ/(pq)への環同型写像を表す)、(x/N)=y3かつ0<x<2k-2を満たすものをs'として、
【００７４】
【数１８４】
0004230162.tif 000025
【００７５】
を計算することで、
【００７６】
【数１８５】
0004230162.tif 000026
【００７７】
に示す復号化結果(但し、復号化結果が「*」の場合、この暗号文を拒否するものとする。また、[a]nおよび[a]nは、それぞれaの上位および下位nビットを表す)を算出する。
【００７８】
本態様は、安全性の証明が可能であり、且つ、従来の公開鍵暗号方法(安全性証明が可能であるもの)と比べて、効率よく平文空間を大きくすることが可能である。つまり、より長い平文を１回の暗号化で処理でき、したがって、効率的な処理が可能となる。
【００７９】
なお、本発明において、暗号化対象となる平文(メッセージともいう)は、文字列のみならず、画像や音、あるいは、送信データの暗号化のために使用する共通鍵など、あらゆるディジタルデータが該当する。
【００８０】
なお、本明細書および図面において、“＋”を円で囲んだ記号は、排他的論理和を示している。
【００８１】
【発明の実施の形態】
以下に、本発明の実施の形態について説明する。
【００８２】
まず、以下の各実施形態に共通する公開鍵暗号通信システムの構成について説明する。
【００８３】
図１は、本発明の各実施形態に共通する公開鍵暗号通信システムの概略構成図である。図示するように、公開鍵暗号通信システムは、暗号化処理を行なって暗号文を作成する送信者側装置１００と、復号化処理を行なって平文を復元する受信者側装置２００とが、通信回線３００を介して接続された構成を有している。
【００８４】
図２は、図１に示す送信者側装置１００の概略構成図である。図示するように、暗号化対象の平文を含む各種情報の入力を受け付ける入力部１０７と、乱数生成部１０１と、べき乗算部１０２と、演算部１０３と、剰余演算部１０４と、記憶部１０５と、暗号化部１０８と、通信回線３００を介して受信者側装置２００と通信を行なう通信部１０６と、を備えている。
【００８５】
図３は、図１に示す受信者側装置２００の概略構成図である。図示するように、通信回線３００を介して送信者側装置１００と通信を行なう通信部２０６と、鍵生成部２０１と、べき乗算部２０２と、演算部２０３と、剰余演算部２０４と、記憶部２０５と、復号化部２０８と、復号結果を含む各種情報を出力する出力部２０７と、を備えている。
【００８６】
上記構成の送信者側装置１００および受信者側装置２００は、図４に示すような、ＣＰＵ４０１と、メモリ４０２と、ＨＤＤ等の外部記憶装置４０３と、ＣＤ-ＲＯＭやＤＶＤ-ＲＯＭ等の可搬性を有する記憶媒体４０４から情報を読み出す読取装置４０５と、キーボードやマウスなどの入力装置４０６と、ディスプレイなどの出力装置４０７と、通信回線３００を介して相手装置と通信を行なうための通信装置４０８と、を備えた一般的なコンピュータシステムにおいて、ＣＰＵ４０１がメモリ４０２上にロードされた所定のプログラムを実行することにより実現することができる。
【００８７】
この所定のプログラムは、読取装置４０５を介して記憶媒体４０４から、あるいは、通信装置４０８を介して通信回線３００から、外部記憶装置４０３にダウンロードされ、それから、メモリ４０２上にロードされてＣＰＵ４０１により実行されるようにしてもよい。また、読取装置４０５を介して記憶媒体４０４から、あるいは、通信装置４０８を介して通信回線３００から、メモリ４０２上に直接ロードされ、ＣＰＵ４０１により実行されるようにしてもよい。
【００８８】
（第１実施形態）
次に、本発明の第１実施形態について、送信者が受信者に対して、送信データとなるメッセージ（長さn）を暗号通信によって送信する場合を例にとり説明する。図５は、本発明の第１実施形態の動作手順を説明するための図である。
【００８９】
１．鍵生成処理
受信者側装置２００において、鍵生成部２０１は、操作者（受信者）よりの指示に従い、受信者の秘密鍵(p,q)と、受信者の公開鍵(N,k,G,H)とを、それぞれ数１８６、数１８７により生成する。そして、生成情報を記憶部２０５に記憶する（ＳＴ１１００）。
【００９０】
【数１８６】
0004230162.tif 000027
【００９１】
【数１８７】
0004230162.tif 000028
【００９２】
ここで、n+k0+k1=kである。また、dの値は、本システムの管理者あるいは受信者が、予めまたは必要に応じて決定するものとし、鍵生成部２０１は、この決定されたdの値を取り込んで、受信者の秘密鍵および公開鍵の生成を行なうものとする。
【００９３】
次に、受信者は、受信者側装置２００の鍵生成部２０１が生成した受信者の公開鍵(N,k,G,H)を含む公開情報を、送信者（送信者側装置１００の操作者）に知らせる（ＳＴ１１０１）。例えば、受信者側装置２００において、鍵生成部２０１は、受信者よりの指示に従い、公開情報を、通信部２０６を介して送信者側装置１００へ送信する。あるいは、受信者は、例えば第３者(公開情報管理機関)への登録などの周知の方法により、公開情報を公開する。この公開情報は、送信者側装置１００の記憶部１０５に記憶される。
【００９４】
なお、秘密鍵（p,q）は、これらとは別の素数p',q'から、p=2p'+1,q=2q'+1となる素数を選ぶことにより作成することも可能である。
【００９５】
２．暗号化処理
送信者側装置１００において、入力部１０７は、操作者（送信者）よりメッセージx(x∈{0,1}n)の入力を受け付ける（ＳＴ１２００）。これを受けて、乱数生成部１０１は、メッセージxに対して乱数ｒ∈{0,1}k0を選ぶ。それから、演算部１０３は、この乱数ｒと、予め記憶部１０５に記憶しておいた受信者の公開鍵(N,k,G,H)とを用いて、べき乗算部１０２を利用して数１８８を計算する（ＳＴ１２０１）。
【００９６】
【数１８８】
0004230162.tif 000029
【００９７】
次に、演算部１０３は、数１８８の計算結果s,tを用いて、数１８９を計算する（ＳＴ１２０２）。
【００９８】
【数１８９】
0004230162.tif 000030
【００９９】
さらに、演算部１０３は、数１８９の計算結果wと受信者の公開鍵とを用いて、べき乗算部１０２および剰余演算部１０４を利用して数１９０を計算する（ＳＴ１２０３）。
【０１００】
【数１９０】
0004230162.tif 000031
【０１０１】
通信部１０６は、数１９０の計算結果yを、メッセージxの暗号文として、通信回線３００を介して、受信者側装置２００に送信する（ＳＴ１２０４）。
【０１０２】
３．復号化処理
受信者側装置２００において、通信部２０６は、通信回線３００を介して送信者側装置１００より暗号文yを受け取り、これを記憶部２０５に記憶する。さて、演算部２０３は、操作者（送信者）よりの指示に従い、べき乗算部２０２および剰余演算部２０４を利用して、記憶部２０５に記憶されている受信者の秘密鍵(p,q)を用いて、記憶部２０５に記憶されている暗号文yから数１９１を計算する。
【０１０３】
【数１９１】
0004230162.tif 000032
【０１０４】
次に、演算部２０３は、数１９１の計算結果を用いて、べき乗算部２０２および剰余演算部２０４を利用して、数１９２および数１９３を計算する（ＳＴ１３００）。
【０１０５】
【数１９２】
0004230162.tif 000033
【０１０６】
【数１９３】
0004230162.tif 000034
【０１０７】
それから、演算部２０３は、φ(xp,xq),φ(-xp,xq),φ(xp,-xq),φ(-xp,-xq)の各々(但し、φは中国人の剰余定理によるZ/(p)×Z/(q)からZ/(pq)への環同型写像を表す)について、数１９４に示すように置く（ＳＴ１３０１、ＳＴ１３０２）。
【０１０８】
【数１９４】
0004230162.tif 000035
【０１０９】
次に、演算部２０３は、数１９５を計算することで（ＳＴ１３０３）、数１９６に示す暗号文yの復号結果x'（つまりメッセージx）を算出する（ＳＴ１３０４）。
【０１１０】
【数１９５】
0004230162.tif 000036
【０１１１】
【数１９６】
0004230162.tif 000037
【０１１２】
それから、演算部２０３は、復号結果x'を出力部２０７から出力する。但し、復号化結果が「*」の場合、演算部２０３は、この暗号文yの復号を拒否し、その旨を出力部２０７から出力する（ＳＴ１３０５）。
【０１１３】
本実施形態において、上述のd(d≧1)の値は変更可能である。例えば、メッセージのビット長が常に小さい場合、上述のNの素因数分解が困難である範囲においてｄの値を大きくすることにより、復号化処理を高速にすることが可能である。
【０１１４】
また、本実施形態では、上述のNの素因数分解問題の困難性を前提にして、選択暗号文攻撃に対して強秘匿であることが証明できる（IND-CCA2）。証明のアウトラインを以下に示す。
【０１１５】
適応的選択暗号文攻撃における強秘匿性の意味において、本実施形態の公開鍵暗号通信方法を破ることができるアルゴリズムが存在したと仮定する(その定義は、例えば文献１４に記載されている)。このアルゴリズムを用いて、Nの素因数分解を行うアルゴリズムを構築できる。これより、本実施形態による公開鍵暗号通信方法は、素因数分解問題の困難性を前提として、IND-CCA2であることが証明できる。
【０１１６】
本実施形態において、上述のwの値およびN/2の値の大小関係を表わす情報（例えばwの値がN/2よりも小さい場合は−１、大きい場合は１とする情報）を、送信者側装置１００は、公開するかあるいは受信者側装置２００に送信するようにしてもよい。受信者側装置２００が復号化処理において上記の情報を用いることにより、４個のφ(xp,xq),φ(-xp,xq),φ(xp,-xq),φ(-xp,-xq)のうちの２つに限定して、復号化を行なうことができる。
【０１１７】
また、上述のdの値が奇数の場合、送信者側装置１００がJacobi記号(w/N)を公開または受信者側装置２００に送信することにより、φ(xp,xq),φ(-xp,xq),φ(xp,-xq),φ(-xp,-xq)のJacobi記号の値を計算することにより、これらのうちの２つに限定して、復号化を行なうことができる。
【０１１８】
このような工夫により、復号化処理における効率性を向上させることができる。
【０１１９】
なお、Jacobi記号の定義および計算方法については、例えば「A.J. Menezes, P.C. van Oorschot, S.A. Vanstone: Jacobi Symbol: Definition & Algorithm, Handbook of Applied Cryptography, CRC Press, pp.73, 1996」（以下、文献１６と呼ぶ）や、「H. Cohen: Jacobi Symbol : Definition & Algorithm, A Course in Computational Algebraic Number Theory, Graduate Texts in Math. 138, Springer-Verlag, New York, pp.27-31, 1993」（以下、文献１７と呼ぶ）に記載されている。
【０１２０】
また、本実施形態において、暗号文yからφ(xp,xq),φ(-xp,xq),φ(xp,-xq),φ(-xp,-xq)を計算する方法は、n=pdqを法として平方根を求める高速な計算方法もある。この計算方法は、n=pdqを法として平方根(またはm乗根)を求める計算を行う他システムへ適用可能である。これにより、高速な累乗根の計算が可能となる。
【０１２１】
ところで、本実施形態の公開鍵暗号通信方法は、共通鍵暗号におけるデータ暗号化鍵の配送を目的として、共通鍵暗号と一緒に使用することも可能である。この場合、メッセージxの代わりに、データ暗号化鍵（共通鍵）K(K∈{0,1}n)が、上述の暗復号化対象となる。そして、このデータ暗号化鍵Kを用いて、送信データmの暗復号化が行なわれる。つまり、送信者側装置１００は、データ暗号化鍵Kにより暗号化した暗号文cを、データ暗号化鍵Kに対する公開鍵暗号結果と共に、受信者側装置２００へ送信する。受信者側装置２００は、公開鍵暗号結果の復号結果（つまりデータ暗号化鍵K）を用いて暗号文cを復号化して送信データmを得る。
【０１２２】
（第２実施形態）
次に、本発明の第２実施形態について、送信者が受信者に対して、送信データとなるメッセージを暗号通信によって送信する場合を例にとり説明する。本実施形態は、上記の第１実施形態の変形例である。図６は、本発明の第２実施形態の動作手順を説明するための図である。
【０１２３】
１．鍵生成処理
受信者側装置２００において、鍵生成部２０１は、操作者（受信者）よりの指示に従い、受信者の秘密鍵(p,q)と、受信者の公開鍵(N,k,G,H,H')とを、それぞれ数１９７、数１９８により生成する。そして、生成情報を記憶部２０５に記憶する（ＳＴ２１００）。
【０１２４】
【数１９７】
0004230162.tif 000038
【０１２５】
【数１９８】
0004230162.tif 000039
【０１２６】
ここで、n+k0+k1=kである。また、dの値は、本システムの管理者あるいは受信者が、予めまたは必要に応じて決定するものとし、鍵生成部２０１は、この決定されたｄの値を取り込んで、受信者の秘密鍵および公開鍵の生成を行なうものとする。
【０１２７】
次に、受信者は、受信者側装置２００の鍵生成部２０１が生成した受信者の公開鍵(N,k,G,H,H')を含む公開情報を、送信者（送信者側装置１００の操作者）に知らせる（ＳＴ２１０１）。例えば、受信者側装置２００において、鍵生成部２０１は、受信者よりの指示に従い、公開情報を、通信部２０６を介して送信者側装置１００へ送信する。あるいは、受信者は、例えば第３者(公開情報管理機関)への登録などの周知の方法により、公開情報を公開する。この公開情報は、送信者側装置１００の記憶部１０５に記憶される。
【０１２８】
なお、秘密鍵（p,q）は、これらとは別の素数p',q'から、p=2p'+1,q=2q'+1となる素数を選ぶことにより作成することも可能である。
【０１２９】
２．暗号化処理
送信者側装置１００において、入力部１０７は、操作者（送信者）よりメッセージx(x∈{0,1}n)の入力を受け付ける（ＳＴ２２００）。これを受けて、乱数生成部１０１は、メッセージxに対して乱数ｒ∈{0,1}k0を選ぶ。それから、演算部１０３は、この乱数ｒと、予め記憶部１０５に記憶しておいた受信者の公開鍵(N,k,G,H,H')とを用いて、数１９９を計算する（ＳＴ２２０１）。
【０１３０】
【数１９９】
0004230162.tif 000040
【０１３１】
次に、演算部１０３は、数１９９の計算結果s,tを用いて、数２００を計算する（ＳＴ２２０２）。
【０１３２】
【数２００】
0004230162.tif 000041
【０１３３】
さらに、演算部１０３は、数２００の計算結果wと受信者の公開鍵とを用いて、べき乗算部１０２および剰余演算部１０４を利用して数２０１を計算する（ＳＴ２２０３）。
【０１３４】
【数２０１】
0004230162.tif 000042
【０１３５】
通信部１０６は、数２０１の計算結果yを、メッセージxの暗号文として、通信回線３００を介して、受信者側装置２００に送信する（ＳＴ２２０４）。
【０１３６】
３．復号化処理
受信者側装置２００において、通信部２０６は、通信回線３００を介して送信者側装置１００より暗号文yを受け取り、これを記憶部２０５に記憶する。さて、演算部２０３は、操作者（送信者）よりの指示に従い、べき乗算部２０２および剰余演算部２０４を利用して、記憶部２０５に記憶されている受信者の秘密鍵(p,q)を用いて、記憶部２０５に記憶されている暗号文yから数２０２を計算する。
【０１３７】
【数２０２】
0004230162.tif 000043
【０１３８】
次に、演算部２０３は、数２０２の計算結果を用いて、べき乗算部２０２および剰余演算部２０４を利用して、数２０３および数２０４を計算する（ＳＴ２３００）。
【０１３９】
【数２０３】
0004230162.tif 000044
【０１４０】
【数２０４】
0004230162.tif 000045
【０１４１】
それから、演算部２０３は、φ(xp,xq),φ(-xp,xq),φ(xp,-xq),φ(-xp,-xq)の各々(但し、φは中国人の剰余定理によるZ/(p)×Z/(q)からZ/(pq)への環同型写像を表す)について、数２０５に示すように置く（ＳＴ２３０１、ＳＴ２３０２）。
【０１４２】
【数２０５】
0004230162.tif 000046
【０１４３】
次に、演算部２０３は、数２０６を計算することで（ＳＴ２３０３）、数２０７に示す暗号文yの復号結果x'（つまりメッセージx）を算出する（ＳＴ２３０４）。
【０１４４】
【数２０６】
0004230162.tif 000047
【０１４５】
【数２０７】
0004230162.tif 000048
【０１４６】
それから、演算部２０３は、復号結果x'を出力部２０７から出力する。但し、復号化結果が「*」の場合、演算部２０３は、この暗号文yの復号を拒否し、その旨を出力部２０７から出力する（ＳＴ２３０５）。
【０１４７】
本実施形態において、上述のd(d≧1)の値は変更可能である。例えば、メッセージのビット長が常に小さい場合、上述のNの素因数分解が困難である範囲においてdの値を大きくすることにより、復号化処理を高速にすることが可能である。
【０１４８】
また、本実施形態は、上述の第１実施形態と同様に、Nの素因数分解問題の困難性を前提にしてIND-CCA2であることが証明できる。
【０１４９】
また、本実施形態は、上記の第１実施形態の場合と同様に、復号化処理において、φ(xp,xq),φ(-xp,xq),φ(xp,-xq),φ(-xp,-xq)を限定することを目的として、Jacobi記号(w/N)の値を公開または送信したり、あるいは、wの値とN/2の値との大小関係を表わす情報を公開または送信することも可能である。
【０１５０】
また、本実施形態の公開鍵暗号通信方法は、上記の第１実施形態と同様に、共通鍵暗号におけるデータ暗号化鍵の配送を目的として、共通鍵暗号と一緒に使用することも可能である。
【０１５１】
（第３実施形態）
次に、本発明の第３実施形態について、送信者が受信者に対して、送信データとなるメッセージを暗号通信によって送信する場合を例にとり説明する。図７は、本発明の第３実施形態の動作手順を説明するための図である。
【０１５２】
１．鍵生成処理
受信者側装置２００において、鍵生成部２０１は、操作者（受信者）よりの指示に従い、受信者の公開鍵(f,G,H)と受信者の秘密鍵とを、それぞれ数２０８、数２０９により生成する。そして、生成情報を記憶部２０５に記憶する（ＳＴ３１００）。
【０１５３】
【数２０８】
0004230162.tif 000049
【０１５４】
【数２０９】
0004230162.tif 000050
【０１５５】
ここで、n+k0+k1=kである。
【０１５６】
次に、受信者は、受信者側装置２００の鍵生成部２０１が生成した受信者の公開鍵(f,G,H)を含む公開情報を、送信者（送信者側装置１００の操作者）に知らせる（ＳＴ３１０１）。例えば、受信者側装置２００において、鍵生成部２０１は、受信者よりの指示に従い、公開情報を、通信部２０６を介して送信者側装置１００へ送信する。あるいは、受信者は、例えば第３者(公開情報管理機関)への登録などの周知の方法により、公開情報を公開する。この公開情報は、送信者側装置１００の記憶部１０５に記憶される。
【０１５７】
２．暗号化処理
送信者側装置１００において、入力部１０７は、操作者（送信者）よりメッセージx(x∈{0,1}n)の入力を受け付ける（ＳＴ３２００）。これを受けて、乱数生成部１０１は、メッセージxに対して乱数ｒ∈{0,1}k0を選ぶ。それから、演算部１０３は、この乱数ｒと、予め記憶部１０５に記憶しておいた受信者の公開鍵(f,G,H)とを用いて、べき乗算部１０２を利用して数２１０を計算する（ＳＴ３２０１）。
【０１５８】
【数２１０】
0004230162.tif 000051
【０１５９】
次に、演算部１０３は、数２１０の計算結果s,tを用いて、数２１１を計算する（ＳＴ３２０２）。
【０１６０】
【数２１１】
0004230162.tif 000052
【０１６１】
通信部１０６は、数２１１の計算結果y1,y2を、メッセージxの暗号文として、通信回線３００を介して、受信者側装置２００に送信する（ＳＴ３２０４）。
【０１６２】
３．復号化処理
受信者側装置２００において、通信部２０６は、通信回線３００を介して送信者側装置１００より暗号文y1,y2を受け取り、これを記憶部２０５に記憶する。さて、演算部２０３は、操作者（送信者）よりの指示に従い、べき乗算部２０２および剰余演算部２０４を利用して、記憶部２０５に記憶されている受信者の秘密鍵を用いて、記憶部２０５に記憶されている暗号文y1,y2から数２１２を計算する（ＳＴ３３００）。
【０１６３】
【数２１２】
0004230162.tif 000053
【０１６４】
次に、演算部２０３は、数２１２の計算結果を用いて、数２１３を計算する（ＳＴ３３０１）。
【０１６５】
【数２１３】
0004230162.tif 000054
【０１６６】
次に、演算部２０３は、数２１３の計算結果を用いて、べき乗算部２０２を利用して数２１４に示す復号化結果を計算する。なお、[a]nおよび[a]nは、それぞれaの上位および下位nビットを表す（Ｓ３３０２）。
【０１６７】
【数２１４】
0004230162.tif 000055
【０１６８】
それから、演算部２０３は、復号結果x'を出力部２０７から出力する。但し、復号化結果が「*」の場合、演算部２０３はこの暗号文y1,y2の復号を拒否し、その旨を出力部２０７から出力する（ＳＴ３３０３）。
【０１６９】
本実施形態では、一方向性置換ｆの逆関数を求めることが困難であることを前提にして、選択暗号文攻撃に対して強秘匿であることが証明できる（IND-CCA2）。証明のアウトラインを以下に示す。
【０１７０】
適応的選択暗号文攻撃における強秘匿性の意味において、本実施形態の公開鍵暗号通信方法を破ろうとする敵(この定義は、例えば文献１５に記載されている)が、復号化オラクルから情報を得るためには、質問である暗号文y1,y2に対する元のメッセージxを知る必要がある。すなわち、敵は、復号化オラクルから新たな情報を得ることができない。また、文献１４に記載の公開鍵暗号方法と同様の方法ににより、本実施形態の公開鍵暗号通信方法がIND-CPA（選択平文攻撃に対して強秘匿）であること容易に示せる。これより、本実施形態の公開鍵暗号通信方法は、IND-CCA2であることが証明できる。
【０１７１】
また、本実施形態によれば、文献１５にて指摘されている文献１４の問題点(ｆの逆関数を計算することの困難性を前提として安全性の証明が不十分)を解決できる。また、本実施形態によると、安全性を保ちつつも、平文空間を大きくとることが可能となる。
【０１７２】
（第４実施形態）
次に、上記の第３実施形態の具体例を、本発明の第４実施形態として説明する。図８は、本発明の第４実施形態の動作手順を説明するための図である。
【０１７３】
１．鍵生成処理
受信者側装置２００において、鍵生成部２０１は、操作者（受信者）よりの指示に従い、受信者の秘密鍵(p,q)と、受信者の公開鍵(N,k,G,H)とを、それぞれ数２１５、数２１６により生成する。そして、生成情報を記憶部２０５に記憶する（ＳＴ４１００）。
【０１７４】
【数２１５】
0004230162.tif 000056
【０１７５】
【数２１６】
0004230162.tif 000057
【０１７６】
ここで、dの値は、本システムの管理者あるいは受信者が、予めまたは必要に応じて決定するものとし、鍵生成部２０１は、この決定されたｄの値を取り込んで、受信者の秘密鍵および公開鍵の生成を行なうものとする。
【０１７７】
次に、受信者は、受信者側装置２００の鍵生成部２０１が生成した受信者の公開鍵(N,k,G,H)を含む公開情報を、送信者（送信者側装置１００の操作者）に知らせる（ＳＴ４１０１）。例えば、受信者側装置２００において、鍵生成部２０１は、受信者よりの指示に従い、公開情報を、通信部２０６を介して送信者側装置１００へ送信する。あるいは、受信者は、例えば第３者(公開情報管理機関)への登録などの周知の方法により、公開情報を公開する。この公開情報は、送信者側装置１００の記憶部１０５に記憶される。
【０１７８】
なお、秘密鍵（p,q）は、これらとは別の素数p',q'から、p=2p'+1,q=2q'+1となる素数を選ぶことにより作成することも可能である。
【０１７９】
２．暗号化処理
送信者側装置１００において、入力部１０７は、操作者（送信者）よりメッセージx(x∈{0,1}n)の入力を受け付ける（ＳＴ４２００）。これを受けて、乱数生成部１０１は、メッセージxに対して乱数ｒ∈{0,1}k0を選ぶ。それから、演算部１０３は、この乱数ｒと、予め記憶部１０５に記憶しておいた受信者の公開鍵(N,k,G,H)とを用いて、べき乗算部１０２を利用して数２１７を計算する（ＳＴ４２０１）。
【０１８０】
【数２１７】
0004230162.tif 000058
【０１８１】
ここで、n+k0+k1<k-2である。次に、演算部１０３は、数２１７の計算結果s,tを用いて、べき乗算部１０２および剰余演算部１０４を利用して数２１８を計算する（ＳＴ４２０２）。
【０１８２】
【数２１８】
0004230162.tif 000059
【０１８３】
ここで、a=(m/N)はJacobi記号を表す。次に、通信部１０６は、数２１８の計算結果y1,y2,y3を、メッセージxの暗号文として、通信回線３００を介して、受信者側装置２００に送信する（ＳＴ４２０３）。
【０１８４】
３．復号化処理
受信者側装置２００において、通信部２０６は、通信回線３００を介して送信者側装置１００より暗号文y1,y2,y3を受け取って記憶部２０５に記憶する。さて、演算部２０３は、操作者（送信者）よりの指示に従い、べき乗算部２０２および剰余演算部２０４を利用して、記憶部２０５に記憶されている受信者の秘密鍵(p,q)を用いて、記憶部２０５に記憶されている暗号文y1,y2,y3から数２１９を計算する（ＳＴ４３００）。
【０１８５】
【数２１９】
0004230162.tif 000060
【０１８６】
それから、演算部２０３は、φ(x1,p,x1,q),φ(-x1,p,x1,q),φ(x1,p,-x1,q),φ(-x1,p,-x1,q)のうち(但し、φは中国人の剰余定理によるZ/(p)×Z/(q)からZ/(pq)への環同型写像を表す)、(x/N)=y3かつ0<x<2k-2を満たすものをs'として、数２２０を計算する（ＳＴ４３０１〜ＳＴ４３０３）。
【０１８７】
【数２２０】
0004230162.tif 000061
【０１８８】
次に、演算部２０３は、数２２１に示す暗号文y1,y2,y3の復号結果x'（つまりメッセージx）を算出する（ＳＴ４３０４）。
【０１８９】
【数２２１】
0004230162.tif 000062
【０１９０】
ここで、[a]nおよび[a]nは、それぞれaの上位および下位nビットを表している。それから、演算部２０３は、復号結果x'を出力部２０７から出力する。但し、復号化結果が「*」の場合、演算部２０３は、この暗号文y1,y2,y3の復号を拒否し、その旨を出力部２０７から出力する（ＳＴ４３０５）。
【０１９１】
本実施形態において、上述のd(d≧1)の値は変更可能である。例えば、メッセージのビット長が常に小さい場合、上述のNの素因数分解が困難である範囲においてｄの値を大きくすることで、復号化処理を高速にすることが可能である。
【０１９２】
また、本実施形態の公開鍵暗号通信方法では、例えばd=3の場合、Nの素因数分解問題の困難性を前提として完全解読が不可能なことを示すことができる。すなわち、Nの素因数分解問題を解くアルゴリズムが存在すれば、そのアルゴリズムを利用して、本実施形態の公開鍵暗号通信方法の完全解読を行うアルゴリズムを構成することができる。また、本実施形態の公開鍵暗号通信方法の完全解読を行うアルゴリズムが存在すれば、そのアルゴリズムを利用して、Nの素因数分解問題を解くアルゴリズムを構成することができる。
【０１９３】
図９は、本実施形態（第４実施形態）による公開鍵暗号通信方法と、従来技術の暗号方法(楕円曲線暗号，RSA，OAEP+RSA)との平文空間の大きさ、および、安全性の比較を表す図である(但し、k1=k0=128)。本実施形態によれば、従来技術に比較して、安全性を保ちつつも、平文空間を大きくとることが可能となることが判る。
【０１９４】
（第５実施形態）
次に、上記の第４実施形態の変形例を、本発明の第５実施形態として説明する。図１０は、本発明の第５実施形態の動作手順を説明するための図である。
【０１９５】
１．鍵生成処理
受信者側装置２００において、鍵生成部２０１は、操作者（受信者）よりの指示に従い、受信者の秘密鍵(p,q)と、受信者の公開鍵(N,k,G,H)とを、それぞれ数２２２、数２２３により生成する。そして、生成情報を記憶部２０５に記憶する（ＳＴ５１００）。
【０１９６】
【数２２２】
0004230162.tif 000063
【０１９７】
【数２２３】
0004230162.tif 000064
【０１９８】
ここで、dの値は、本システムの管理者あるいは受信者が、予めまたは必要に応じて決定するものとし、鍵生成部２０１は、この決定されたｄの値を取り込んで、受信者の秘密鍵および公開鍵の生成を行なうものとする。
【０１９９】
次に、受信者は、受信者側装置２００の鍵生成部２０１が生成した受信者の公開鍵(N,k,G,H)を含む公開情報を、送信者（送信者側装置１００の操作者）に知らせる（ＳＴ５１０１）。例えば、受信者側装置２００において、鍵生成部２０１は、受信者よりの指示に従い、公開情報を、通信部２０６を介して送信者側装置１００へ送信する。あるいは、受信者は、例えば第３者(公開情報管理機関)への登録などの周知の方法により、公開情報を公開する。この公開情報は、送信者側装置１００の記憶部１０５に記憶される。
【０２００】
なお、秘密鍵（p,q）は、これらとは別の素数p',q'から、p=2p'+1,q=2q'+1となる素数を選ぶことにより作成することも可能である。
【０２０１】
２．暗号化処理
送信者側装置１００において、入力部１０７は、操作者（送信者）よりメッセージx(x∈{0,1}n)の入力を受け付ける（ＳＴ５２００）。これを受けて、乱数生成部１０１は、メッセージxに対して乱数ｒ∈{0,1}k0を選ぶ。それから、演算部１０３は、この乱数ｒと、予め記憶部１０５に記憶しておいた受信者の公開鍵(N,k,G,H)とを用いて、べき乗算部１０２を利用して数２２４を計算する（ＳＴ５２０１）。
【０２０２】
【数２２４】
0004230162.tif 000065
【０２０３】
ここで、n+k0+k1<k-2である。次に、演算部１０３は、数２２４の計算結果s,tを用いて、べき乗算部１０２および剰余演算部１０４を利用して数２２５を計算する（ＳＴ５２０２）。
【０２０４】
【数２２５】
0004230162.tif 000066
【０２０５】
次に、通信部１０６は、数２２５の計算結果y1,y2を、メッセージxの暗号文として、通信回線３００を介して、受信者側装置２００に送信する（ＳＴ５２０３）。
【０２０６】
３．復号化処理
受信者側装置２００において、通信部２０６は、通信回線３００を介して送信者側装置１００より暗号文y1,y2を受け取って記憶部２０５に記憶する。さて、演算部２０３は、操作者（送信者）よりの指示に従い、べき乗算部２０２および剰余演算部２０４を利用して、記憶部２０５に記憶されている受信者の秘密鍵(p,q)を用いて、記憶部２０５に記憶されている暗号文y1,y2から数２２６を計算する（ＳＴ５３００）。
【０２０７】
【数２２６】
0004230162.tif 000067
【０２０８】
それから、演算部２０３は、φ(x1,p,x1,q),φ(-x1,p,x1,q),φ(x1,p,-x1,q),φ(-x1,p,-x1,q)のうち(但し、φは中国人の剰余定理によるZ/(p)×Z/(q)からZ/(pq)への環同型写像を表す)、0<x<2k-2を満たすものをs'（s'は複数存在してもよい）として、数２２７を計算する（ＳＴ５３０１〜ＳＴ５３０３）。
【０２０９】
【数２２７】
0004230162.tif 000068
【０２１０】
次に、演算部２０３は、数２２８に示す暗号文y1,y2の復号結果x'（つまりメッセージx）を算出する（ＳＴ５３０４）。
【０２１１】
【数２２８】
0004230162.tif 000069
【０２１２】
ここで、[a]nおよび[a]nは、それぞれaの上位および下位nビットを表している。それから、演算部２０３は、復号結果x'を出力部２０７から出力する。但し、復号化結果が「*」の場合、演算部２０３は、この暗号文y1,y2の復号を拒否し、その旨を出力部２０７から出力する（ＳＴ５３０５）。
【０２１３】
本実施形態において、上述のd(d≧1)の値は変更可能である。例えば、メッセージのビット長が常に小さい場合、上述のNの素因数分解が困難である範囲においてｄの値を大きくすることで、復号化処理を高速にすることが可能である。
【０２１４】
また、本実施形態の公開鍵暗号通信方法では、例えばd=3の場合、Nの素因数分解問題の困難性を前提として完全解読が不可能なことを示すことができる。すなわち、Nの素因数分解問題を解くアルゴリズムが存在すれば、そのアルゴリズムを利用して、本実施形態の公開鍵暗号通信方法の完全解読を行うアルゴリズムを構成することができる。また、本実施形態の公開鍵暗号通信方法の完全解読を行うアルゴリズムが存在すれば、そのアルゴリズムを利用して、Nの素因数分解問題を解くアルゴリズムを構成することができる。
【０２１５】
（第６実施形態）
次に、上記の第４実施形態の他の変形例を、本発明の第６実施形態として説明する。図１１は、本発明の第６実施形態の動作手順を説明するための図である。
【０２１６】
１．鍵生成処理
受信者側装置２００において、鍵生成部２０１は、操作者（受信者）よりの指示に従い、受信者の秘密鍵pi(1≦i≦d)と、受信者の公開鍵(N,k,G,H)とを、それぞれ数２２９、数２３０により生成する。そして、生成情報を記憶部２０５に記憶する（ＳＴ６１００）。
【０２１７】
【数２２９】
0004230162.tif 000070
【０２１８】
【数２３０】
0004230162.tif 000071
【０２１９】
ここで、dの値は、本システムの管理者あるいは受信者が、予めまたは必要に応じて決定するものとし、鍵生成部２０１は、この決定されたｄの値を取り込んで、受信者の秘密鍵および公開鍵の生成を行なうものとする。
【０２２０】
次に、受信者は、受信者側装置２００の鍵生成部２０１が生成した受信者の公開鍵(N,k,G,H)を含む公開情報を、送信者（送信者側装置１００の操作者）に知らせる（ＳＴ６１０１）。例えば、受信者側装置２００において、鍵生成部２０１は、受信者よりの指示に従い、公開情報を、通信部２０６を介して送信者側装置１００へ送信する。あるいは、受信者は、例えば第３者(公開情報管理機関)への登録などの周知の方法により、公開情報を公開する。この公開情報は、送信者側装置１００の記憶部１０５に記憶される。
【０２２１】
なお、秘密鍵piは、これらとは別の素数p'から、p=2p'+1となる素数を選ぶことにより作成することも可能である。
【０２２２】
２．暗号化処理
送信者側装置１００において、入力部１０７は、操作者（送信者）よりメッセージx(x∈{0,1}n)の入力を受け付ける（ＳＴ６２００）。これを受けて、乱数生成部１０１は、メッセージxに対して乱数ｒ∈{0,1}k0を選ぶ。それから、演算部１０３は、この乱数ｒと、予め記憶部１０５に記憶しておいた受信者の公開鍵(N,k,G,H)とを用いて、べき乗算部１０２を利用して数２３１を計算する（ＳＴ６２０１）。
【０２２３】
【数２３１】
0004230162.tif 000072
【０２２４】
ここで、n+k0+k1≦log2(N+1)である。次に、演算部１０３は、数２３１の計算結果s,tを用いて、べき乗算部１０２および剰余演算部１０４を利用して数２３２を計算する（ＳＴ６２０２）。
【０２２５】
【数２３２】
0004230162.tif 000073
【０２２６】
次に、通信部１０６は、数２３２の計算結果y1,y2を、メッセージxの暗号文として、通信回線３００を介して、受信者側装置２００に送信する（ＳＴ６２０３）。
【０２２７】
３．復号化処理
受信者側装置２００において、通信部２０６は、通信回線３００を介して送信者側装置１００より暗号文y1,y2を受け取って記憶部２０５に記憶する。さて、演算部２０３は、操作者（送信者）よりの指示に従い、べき乗算部２０２および剰余演算部２０４を利用して、記憶部２０５に記憶されている受信者の秘密鍵piを用いて、記憶部２０５に記憶されている暗号文y1,y2から数２３３を計算する（ＳＴ６３００）。
【０２２８】
【数２３３】
0004230162.tif 000074
【０２２９】
それから、演算部２０３は、2d個のφ(±x1,p1,±x1,p2,．．．,±x1,pd)のうち(但し、φは中国人の剰余定理によるZ/(p1)×Z/(q2)×．．．×Z/(qd)からZ/(N)への環同型写像を表す)、0＜s'＜N/2を満たすものをs'（s'は複数存在してもよい）として、数２３４を計算する。
【０２３０】
【数２３４】
0004230162.tif 000075
【０２３１】
次に、演算部２０３は、数２３５に示す暗号文y1,y2の復号結果x'（つまりメッセージx）を算出する（ＳＴ６３０３）。
【０２３２】
【数２３５】
0004230162.tif 000076
【０２３３】
ここで、[a]nおよび[a]nは、それぞれaの上位および下位nビットを表している。それから、演算部２０３は、復号結果x'を出力部２０７から出力する。但し、復号化結果が「*」の場合、演算部２０３は、この暗号文y1,y2の復号を拒否し、その旨を出力部２０７から出力する（ＳＴ６３０４）。
【０２３４】
本実施形態において、上述のd(d＞1)の値は変更可能である。また、本実施形態の公開鍵暗号通信方法では、Nの素因数分解問題の困難性を前提として完全解読が不可能なことを示すことができる。すなわち、Nの素因数分解問題を解くアルゴリズムが存在すれば、そのアルゴリズムを利用して、本実施形態の公開鍵暗号通信方法の完全解読を行うアルゴリズムを構成することができる。また、本実施形態の公開鍵暗号通信方法の完全解読を行うアルゴリズムが存在すれば、そのアルゴリズムを利用して、Nの素因数分解問題を解くアルゴリズムを構成することができる。
【０２３５】
（第７実施形態）
上記の第３実施形態の公開鍵暗号通信方法を、共通鍵暗号におけるデータ暗号化鍵の配送を目的として、既存の暗号方法（例えば共通鍵暗号）と一緒に使用するようにした場合を、本発明の第７実施形態として説明する。
【０２３６】
１．鍵生成処理
受信者側装置２００において、鍵生成部２０１は、操作者（受信者）よりの指示に従い、受信者の公開鍵(f,G,H)と受信者の秘密鍵とを、それぞれ数２３６、数２３７により生成する。そして、生成情報を記憶部２０５に記憶する。
【０２３７】
【数２３６】
0004230162.tif 000077
【０２３８】
【数２３７】
0004230162.tif 000078
【０２３９】
ここで、n+k0+k1=kである。
【０２４０】
次に、受信者は、受信者側装置２００の鍵生成部２０１が生成した受信者の公開鍵(f,G,H)を含む公開情報を、送信者（送信者側装置１００の操作者）に知らせる。例えば、受信者側装置２００において、鍵生成部２０１は、受信者よりの指示に従い、公開情報を、通信部２０６を介して送信者側装置１００へ送信する。あるいは、受信者は、例えば第３者(公開情報管理機関)への登録などの周知の方法により、公開情報を公開する。この公開情報は送信者側装置１００の記憶部１０５に記憶される。
【０２４１】
２．暗号化処理
送信者側装置１００において、入力部１０７は、操作者（送信者）より送信メッセージmの入力を受け付けると、暗号化部１０８は、データ暗復号化鍵K(K∈{0,1}n)を用いて、既存の暗号化方法によりメッセージmを暗号化し、暗号文cを作成する。次に、乱数生成部１０１は、データ暗復号化鍵Kに対して乱数ｒ∈{0,1}k0を選ぶ。それから、演算部１０３は、この乱数ｒと、予め記憶部１０５に記憶しておいた受信者の公開鍵(f,G,H)とを用いて、べき乗算部１０２を利用して数２３８を計算する。
【０２４２】
【数２３８】
0004230162.tif 000079
【０２４３】
次に、演算部１０３は、数２３８の計算結果s,tを用いて、数２３９を計算する。
【０２４４】
【数２３９】
0004230162.tif 000080
【０２４５】
通信部１０６は、数２３９の暗号結果y1,y2を、メッセージmの暗号文cと共に、通信回線３００を介して、受信者側装置２００に送信する。
【０２４６】
３．復号化処理
受信者側装置２００において、通信部２０６は、通信回線３００を介して送信者側装置１００より暗号結果y1,y2を暗号文cと共に受け取り、これを記憶部２０５に記憶する。さて、演算部２０３は、操作者（送信者）よりの指示に従い、べき乗算部２０２を利用して、記憶部２０５に記憶されている受信者の秘密鍵を用いて、記憶部２０５に記憶されている暗号結果y1,y2から数２４０を計算する。
【０２４７】
【数２４０】
0004230162.tif 000081
【０２４８】
次に、演算部２０３は、数２４０の計算結果を用いて、数２４１を計算する。
【０２４９】
【数２４１】
0004230162.tif 000082
【０２５０】
次に、演算部２０３は、数２４１の計算結果を用いて、べき乗算部２０２を利用して数２４２に示す復号化結果を計算する。なお、[a]nおよび[a]nは、それぞれaの上位および下位nビットを表す。
【０２５１】
【数２４２】
0004230162.tif 000083
【０２５２】
但し、復号化結果が「*」の場合、演算部２０３はこの暗号結果y1,y2の復号を拒否し、その旨を出力部２０７から出力する。
【０２５３】
次に、復号化部２０８は、数２４２による復号結果K'（つまり、データ暗復号化鍵K）を用いて、記憶部２０５に記憶されている暗号文cを既存の暗号方法により復号化する。そして、その復号結果（つまりメッセージm）を出力部２０７から出力する。
【０２５４】
（第８実施形態）
上記の第４実施形態の公開鍵暗号通信方法を、共通鍵暗号におけるデータ暗号化鍵の配送を目的として、既存の暗号方法（例えば共通鍵暗号）と一緒に使用するようにした場合を、本発明の第８実施形態として説明する。
【０２５５】
１．鍵生成処理
受信者側装置２００において、鍵生成部２０１は、操作者（受信者）よりの指示に従い、受信者の秘密鍵(p,q)と、受信者の公開鍵(N,k,G,H)とを、それぞれ数２４３、数２４４により生成する。そして、生成情報を記憶部２０５に記憶する。
【０２５６】
【数２４３】
0004230162.tif 000084
【０２５７】
【数２４４】
0004230162.tif 000085
【０２５８】
次に、受信者は、受信者側装置２００の鍵生成部２０１が生成した受信者の公開鍵(N,k,G,H)を含む公開情報を、送信者（送信者側装置１００の操作者）に知らせる。例えば、受信者側装置２００において、鍵生成部２０１は、受信者よりの指示に従い、公開情報を、通信部２０６を介して送信者側装置１００へ送信する。あるいは、受信者は、例えば第３者(公開情報管理機関)への登録などの周知の方法により、公開情報を公開する。この公開情報は送信者側装置１００の記憶部１０５に記憶される。
【０２５９】
２．暗号化処理
送信者側装置１００において、入力部１０７は、操作者（送信者）より送信メッセージmの入力を受け付けると、暗号化部１０８は、データ暗復号化鍵K(K∈{0,1}n)を用いて、既存の暗号化方法によりメッセージmを暗号化し、暗号文cを作成する。次に、乱数生成部１０１は、データ暗復号化鍵Kに対して乱数ｒ∈{0,1}k0を選ぶ。それから、演算部１０３は、この乱数ｒと、予め記憶部１０５に記憶しておいた受信者の公開鍵(N,k,G,H)とを用いて、べき乗算部１０２を利用して数２４５を計算する。
【０２６０】
【数２４５】
0004230162.tif 000086
【０２６１】
ここで、n+k0+k1<k-2である。
【０２６２】
次に、演算部１０３は、数２４５の計算結果s,tを用いて、数２４６を計算する。
【０２６３】
【数２４６】
0004230162.tif 000087
【０２６４】
ここで、a=(m/N)はJacobi記号を表す。
【０２６５】
次に、通信部１０６は、数２４６の暗号結果y1,y2,y3を、メッセージmの暗号文cと共に、通信回線３００を介して、受信者側装置２００に送信する。
【０２６６】
３．復号化処理
受信者側装置２００において、通信部２０６は、通信回線３００を介して送信者側装置１００より暗号結果y1,y2,y3を暗号文cと共に受け取り、これを記憶部２０５に記憶する。さて、演算部２０３は、操作者（送信者）よりの指示に従い、べき乗算部２０２および剰余演算部２０４を利用し、記憶部２０５に記憶されている受信者の秘密鍵を用いて、記憶部２０５に記憶されている暗号結果y1,y2,y3から数２４７を計算する。
【０２６７】
【数２４７】
0004230162.tif 000088
【０２６８】
それから、演算部２０３は、φ(x1,p,x1,q),φ(-x1,p,x1,q),φ(x1,p,-x1,q),φ(-x1,p,-x1,q)のうち(但し、φは中国人の剰余定理によるZ/(p)×Z/(q)からZ/(pq)への環同型写像を表す)、(x/N)=y3かつ0<x<2k-2を満たすものをs'として、数２４８を計算する。
【０２６９】
【数２４８】
0004230162.tif 000089
【０２７０】
次に、演算部２０３は、数２４８の計算結果を用いて、べき乗算部２０２を利用して数２４９に示す復号化結果を計算する。なお、[a]nおよび[a]nは、それぞれaの上位および下位nビットを表す。
【０２７１】
【数２４９】
0004230162.tif 000090
【０２７２】
但し、復号化結果が「*」の場合、演算部２０３はこの暗号結果y1,y2,y3の復号を拒否し、その旨を出力部２０７から出力する。
【０２７３】
次に、復号化部２０８は、数２４９による復号結果K'（つまり、データ暗復号化鍵K）を用いて、記憶部２０５に記憶されている暗号文cを既存の暗号方法により復号化する。そして、その復号結果（つまりメッセージm）を出力部２０７から出力する。
【０２７４】
（第９実施形態）
上記の第５実施形態の公開鍵暗号通信方法を、共通鍵暗号におけるデータ暗号化鍵の配送を目的として、既存の暗号方法（例えば共通鍵暗号）と一緒に使用するようにした場合を、本発明の第９実施形態として説明する。
【０２７５】
１．鍵生成処理
受信者側装置２００において、鍵生成部２０１は、操作者（受信者）よりの指示に従い、受信者の秘密鍵(p,q)と、受信者の公開鍵(N,k,G,H)とを、それぞれ数２５０、数２５１により生成する。そして、生成情報を記憶部２０５に記憶する。
【０２７６】
【数２５０】
0004230162.tif 000091
【０２７７】
【数２５１】
0004230162.tif 000092
【０２７８】
次に、受信者は、受信者側装置２００の鍵生成部２０１が生成した受信者の公開鍵(N,k,G,H)を含む公開情報を、送信者（送信者側装置１００の操作者）に知らせる。例えば、受信者側装置２００において、鍵生成部２０１は、受信者よりの指示に従い、公開情報を、通信部２０６を介して送信者側装置１００へ送信する。あるいは、受信者は、例えば第３者(公開情報管理機関)への登録などの周知の方法により、公開情報を公開する。この公開情報は送信者側装置１００の記憶部１０５に記憶される。
【０２７９】
２．暗号化処理
送信者側装置１００において、入力部１０７は、操作者（送信者）より送信メッセージmの入力を受け付けると、暗号化部１０８は、データ暗復号化鍵K(K∈{0,1}n)を用いて、既存の暗号化方法によりメッセージmを暗号化し、暗号文cを作成する。次に、乱数生成部１０１は、データ暗復号化鍵Kに対して乱数ｒ∈{0,1}k0を選ぶ。それから、演算部１０３は、この乱数ｒと、予め記憶部１０５に記憶しておいた受信者の公開鍵(N,k,G,H)とを用いて、べき乗算部１０２を利用して数２５２を計算する。
【０２８０】
【数２５２】
0004230162.tif 000093
【０２８１】
ここで、n+k0+k1<k-2である。
【０２８２】
次に、演算部１０３は、数２５２の計算結果s,tを用いて、べき乗算部１０２および剰余演算部１０４を利用して、数２５３を計算する。
【０２８３】
【数２５３】
0004230162.tif 000094
【０２８４】
次に、通信部１０６は、数２５３の暗号結果y1,y2をメッセージmの暗号文cと共に、通信回線３００を介して、受信者側装置２００に送信する。
【０２８５】
３．復号化処理
受信者側装置２００において、通信部２０６は、通信回線３００を介して送信者側装置１００より暗号結果y1,y2を暗号文cと共に受け取り、これを記憶部２０５に記憶する。さて、演算部２０３は、操作者（送信者）よりの指示に従い、べき乗算部２０２および剰余演算部２０４を利用し、記憶部２０５に記憶されている受信者の秘密鍵を用いて、記憶部２０５に記憶されている暗号結果y1,y2から数２５４を計算する。
【０２８６】
【数２５４】
0004230162.tif 000095
【０２８７】
それから、演算部２０３は、φ(x1,p,x1,q),φ(-x1,p,x1,q),φ(x1,p,-x1,q),φ(-x1,p,-x1,q)のうち(但し、φは中国人の剰余定理によるZ/(p)×Z/(q)からZ/(pq)への環同型写像を表す)、0<x<2k-2を満たすものをs'（s'は複数存在してもよい）として、数２５５を計算する。
【０２８８】
【数２５５】
0004230162.tif 000096
【０２８９】
次に、演算部２０３は、数２５５の計算結果を用いて、べき乗算部２０２を利用して数２５６に示す復号化結果を計算する。なお、[a]nおよび[a]nは、それぞれaの上位および下位nビットを表す。
【０２９０】
【数２５６】
0004230162.tif 000097
【０２９１】
但し、復号化結果が「*」の場合、演算部２０３はこの暗号結果y1,y2の復号を拒否し、その旨を出力部２０７から出力する。
【０２９２】
次に、復号化部２０８は、数２５６による復号結果K'（つまり、データ暗復号化鍵K）を用いて、記憶部２０５に記憶されている暗号文cを既存の暗号方法により復号化する。そして、その復号結果（つまりメッセージm）を出力部２０７から出力する。
【０２９３】
（第１０実施形態）
次に、上記の第４実施形態の変形例を、共通鍵暗号におけるデータ暗号化鍵の配送を目的として、既存の暗号方法（例えば共通鍵暗号）と一緒に使用するようにした場合を、本発明の第１０実施形態として説明する。
【０２９４】
１．鍵生成処理
受信者側装置２００において、鍵生成部２０１は、操作者（受信者）よりの指示に従い、受信者の秘密鍵pi(1≦i≦d)と、受信者の公開鍵(N,k,G,H)とを、それぞれ数２５７、数２５８により生成する。そして、生成情報を記憶部２０５に記憶する。
【０２９５】
【数２５７】
0004230162.tif 000098
【０２９６】
【数２５８】
0004230162.tif 000099
【０２９７】
ここで、dの値は、本システムの管理者あるいは受信者が、予めまたは必要に応じて決定するものとし、鍵生成部２０１は、この決定されたｄの値を取り込んで、受信者の秘密鍵および公開鍵の生成を行なうものとする。
【０２９８】
次に、受信者は、受信者側装置２００の鍵生成部２０１が生成した受信者の公開鍵(N,k,G,H)を含む公開情報を、送信者（送信者側装置１００の操作者）に知らせる。例えば、受信者側装置２００において、鍵生成部２０１は、受信者よりの指示に従い、公開情報を、通信部２０６を介して送信者側装置１００へ送信する。あるいは、受信者は、例えば第３者(公開情報管理機関)への登録などの周知の方法により、公開情報を公開する。この公開情報は、送信者側装置１００の記憶部１０５に記憶される。
【０２９９】
２．暗号化処理
送信者側装置１００において、入力部１０７は、操作者（送信者）より送信メッセージmの入力を受け付けると、暗号化部１０８は、データ暗復号化鍵K(K∈{0,1}n)を用いて、既存の暗号化方法によりメッセージmを暗号化し、暗号文cを作成する。次に、乱数生成部１０１は、データ暗復号化鍵Kに対して乱数ｒ∈{0,1}k0を選ぶ。それから、演算部１０３は、この乱数ｒと、予め記憶部１０５に記憶しておいた受信者の公開鍵(N,k,G,H)とを用いて、べき乗算部１０２を利用して数２５９を計算する。
【０３００】
【数２５９】
0004230162.tif 000100
【０３０１】
ここで、n+k0+k1≦log2(N+1)である。
【０３０２】
次に、演算部１０３は、数２５９の計算結果s,tを用いて、べき乗算部１０２および剰余演算部１０４を利用して、数２６０を計算する。
【０３０３】
【数２６０】
0004230162.tif 000101
【０３０４】
次に、通信部１０６は、数２６０の暗号結果y1,y2をメッセージmの暗号文cと共に、通信回線３００を介して受信者側装置２００に送信する。
【０３０５】
３．復号化処理
受信者側装置２００において、通信部２０６は、通信回線３００を介して送信者側装置１００より暗号結果y1,y2を暗号文cと共に受け取り、これを記憶部２０５に記憶する。さて、演算部２０３は、操作者（送信者）よりの指示に従い、べき乗算部２０２および剰余演算部２０４を利用し、記憶部２０５に記憶されている受信者の秘密鍵を用いて、記憶部２０５に記憶されている暗号結果y1,y2から数２６１を計算する。
【０３０６】
【数２６１】
0004230162.tif 000102
【０３０７】
それから、演算部２０３は、2d個のφ(±x1,p1,±x1,p2,．．．,±x1,pd)のうち(但し、φは中国人の剰余定理によるZ/(p1)×Z/(q2)×．．．×Z/(qd)からZ/(N)への環同型写像を表す)、0＜s'＜N/2を満たすものをs'（s'は複数存在してもよい）として、数２６２を計算する。
【０３０８】
【数２６２】
0004230162.tif 000103
【０３０９】
次に、演算部２０３は、数２６２の計算結果を用いて、べき乗算部２０２を利用して数２６３に示す復号化結果を計算する。なお、[a]nおよび[a]nは、それぞれaの上位および下位nビットを表す。
【０３１０】
【数２６３】
0004230162.tif 000104
【０３１１】
但し、復号化結果が「*」の場合、演算部２０３はこの暗号結果y1,y2の復号を拒否し、その旨を出力部２０７から出力する。
【０３１２】
次に、復号化部２０８は、数２６３による復号結果K'（つまり、データ暗復号化鍵K）を用いて、記憶部２０５に記憶されている暗号文cを既存の暗号方法により復号化する。そして、その復号結果（つまりメッセージm）を出力部２０７から出力する。
【０３１３】
（第１１実施形態）
次に、本発明の第１１実施形態について、送信者が受信者に対して、送信データとなるメッセージを暗号通信によって送信する場合を例にとり説明する。図１２は、本発明の第１１実施形態の動作手順を説明するための図である。
【０３１４】
１．鍵生成処理
受信者側装置２００において、鍵生成部２０１は、操作者（受信者）よりの指示に従い、受信者の公開鍵(f,G,H)と受信者の秘密鍵とを、それぞれ数２６４、数２６５により生成する。そして、生成情報を記憶部２０５に記憶する（ＳＴ７１００）。
【０３１５】
【数２６４】
0004230162.tif 000105
【０３１６】
【数２６５】
0004230162.tif 000106
【０３１７】
次に、受信者は、受信者側装置２００の鍵生成部２０１が生成した受信者の公開鍵(f,G,H)を含む公開情報を、送信者（送信者側装置１００の操作者）に知らせる（ＳＴ７１０１）。例えば、受信者側装置２００において、鍵生成部２０１は、受信者よりの指示に従い、公開情報を、通信部２０６を介して送信者側装置１００へ送信する。あるいは、受信者は、例えば第３者(公開情報管理機関)への登録などの周知の方法により、公開情報を公開する。この公開情報は、送信者側装置１００の記憶部１０５に記憶される。
【０３１８】
２．暗号化処理
送信者側装置１００において、入力部１０７は、操作者（送信者）よりメッセージx(x∈{0,1}n)の入力を受け付ける（ＳＴ７２００）。これを受けて、乱数生成部１０１は、メッセージxに対して乱数ｒ∈{0,1}k0を選ぶ。それから、演算部１０３は、この乱数ｒと、予め記憶部１０５に記憶しておいた受信者の公開鍵(f,G,H)とを用いて、数２６６を計算する（ＳＴ７２０１）。
【０３１９】
【数２６６】
0004230162.tif 000107
【０３２０】
次に、演算部１０３は、数２６６の計算結果s,tを用いて、数２６７を計算する（ＳＴ７２０２）。
【０３２１】
【数２６７】
0004230162.tif 000108
【０３２２】
通信部１０６は、数２６７の計算結果y1,y2を、メッセージxの暗号文として、通信回線３００を介して、受信者側装置２００に送信する（ＳＴ７２０３）。
【０３２３】
３．復号化処理
受信者側装置２００において、通信部２０６は、通信回線３００を介して送信者側装置１００より暗号文y1,y2を受け取り、これを記憶部２０５に記憶する。さて、演算部２０３は、操作者（送信者）よりの指示に従い、記憶部２０５に記憶されている受信者の秘密鍵を用いて、記憶部２０５に記憶されている暗号文y1,y2から数２６８を計算する（ＳＴ７３００）。
【０３２４】
【数２６８】
0004230162.tif 000109
【０３２５】
次に、演算部２０３は、数２６８の計算結果を用いて、数２６９を計算する（ＳＴ７３０１）。
【０３２６】
【数２６９】
0004230162.tif 000110
【０３２７】
但し、x'∈{0,1}n，r'∈{0,1}k0である。
【０３２８】
次に、演算部２０３は、数２６９の計算結果を用いて、数２７０に示す復号化結果を計算する（ＳＴ７３０２）。
【０３２９】
【数２７０】
0004230162.tif 000111
【０３３０】
それから、演算部２０３は、復号結果x'を出力部２０７から出力する。但し、復号化結果が「*」の場合、演算部２０３はこの暗号文y1,y2の復号を拒否し、その旨を出力部２０７から出力する（ＳＴ７３０３）。
【０３３１】
本実施形態の公開鍵暗号通信方法によれば、上記の第３実施形態と同様に、一方向性置換ｆの逆関数を求めることが困難であることを前提にして、選択暗号文攻撃に対して強秘匿であることが証明できる。
【０３３２】
なお、本実施形態は、上記の第３実施形態と比較して、メッセージの長さnを関数ｆに依らずに設定することができる特徴を持つ。すなわち、nの値を送信したいメッセージの長さに応じて、ユーザが勝手に設定することが可能である。
【０３３３】
（第１２実施形態）
次に、上記の第１１実施形態の具体例を、本発明の第１２実施形態として説明する。図１３は、本発明の第１２実施形態の動作手順を説明するための図である。
【０３３４】
１．鍵生成処理
受信者側装置２００において、鍵生成部２０１は、操作者（受信者）よりの指示に従い、受信者の秘密鍵(p,q)と受信者の公開鍵(N,k,G,H)とを、それぞれ数２７１、数２７２により生成する。そして、生成情報を記憶部２０５に記憶する（ＳＴ８１００）。
【０３３５】
【数２７１】
0004230162.tif 000112
【０３３６】
【数２７２】
0004230162.tif 000113
【０３３７】
ここで、dの値は、本システムの管理者あるいは受信者が、予めまたは必要に応じて決定するものとし、鍵生成部２０１は、この決定されたｄの値を取り込んで、受信者の秘密鍵および公開鍵の生成を行なうものとする。
【０３３８】
次に、受信者は、受信者側装置２００の鍵生成部２０１が生成した受信者の公開鍵(N,k,G,H)を含む公開情報を、送信者（送信者側装置１００の操作者）に知らせる（ＳＴ８１０１）。例えば、受信者側装置２００において、鍵生成部２０１は、受信者よりの指示に従い、公開情報を、通信部２０６を介して送信者側装置１００へ送信する。あるいは、受信者は、例えば第３者(公開情報管理機関)への登録などの周知の方法により、公開情報を公開する。この公開情報は、送信者側装置１００の記憶部１０５に記憶される。
【０３３９】
なお、秘密鍵（p,q）は、これらとは別の素数p',q'から、p=2p'+1,q=2q'+1となる素数を選ぶことにより作成することも可能である。
【０３４０】
２．暗号化処理
送信者側装置１００において、入力部１０７は、操作者（送信者）よりメッセージx(x∈{0,1}n)の入力を受け付ける（ＳＴ８２００）。これを受けて、乱数生成部１０１は、メッセージxに対して乱数ｒ∈{0,1}k0を選ぶ。それから、演算部１０３は、この乱数ｒと、予め記憶部１０５に記憶しておいた受信者の公開鍵(N,k,G,H)とを用いて、数２７３を計算する（ＳＴ８２０１）。
【０３４１】
【数２７３】
0004230162.tif 000114
【０３４２】
次に、演算部１０３は、数２７３の計算結果s,tを用いて、べき乗算部１０２および剰余演算部１０４を利用して数２７４を計算する（ＳＴ８２０２）。
【０３４３】
【数２７４】
0004230162.tif 000115
【０３４４】
ここで、a=(m/N)はJacobi記号を表す。次に、通信部１０６は、数２７４の計算結果y1,y2,y3を、メッセージxの暗号文として、通信回線３００を介して、受信者側装置２００に送信する（ＳＴ８２０３）。
【０３４５】
３．復号化処理
受信者側装置２００において、通信部２０６は、通信回線３００を介して送信者側装置１００より暗号文y1,y2,y3を受け取り、これを記憶部２０５に記憶する。さて、演算部２０３は、操作者（送信者）よりの指示に従い、記憶部２０５に記憶されている受信者の秘密鍵を用いて、べき乗算部１０２および剰余演算部１０４を利用して、記憶部２０５に記憶されている暗号文y1,y2,y3から数２７５を計算する（ＳＴ８３００）。
【０３４６】
【数２７５】
0004230162.tif 000116
【０３４７】
それから、演算部２０３は、φ(x1,p,x1,q),φ(-x1,p,x1,q),φ(x1,p,-x1,q),φ(-x1,p,-x1,q)のうち(但し、φは中国人の剰余定理によるZ/(p)×Z/(q)からZ/(pq)への環同型写像を表す)、(x/N)=y3かつ0<x<2k-2を満たすものをs'として、数２７６を計算する（ＳＴ８３０１〜ＳＴ８３０３）。
【０３４８】
【数２７６】
0004230162.tif 000117
【０３４９】
ここで、x'∈{0,1}n，r'∈{0,1}k0である。
【０３５０】
次に、演算部２０３は、数２７６の計算結果を用いて、数２７７に示す復号化結果を計算する（ＳＴ８３０４）。
【０３５１】
【数２７７】
0004230162.tif 000118
【０３５２】
それから、演算部２０３は、復号結果x'を出力部２０７から出力する。但し、復号化結果が「*」の場合、演算部２０３はこの暗号文y1,y2,y3の復号を拒否しその旨を出力部２０７から出力する（ＳＴ８３０５）。
【０３５３】
本実施形態において、上述のd(d≧1)の値は変更可能である。例えば、メッセージのビット長が常に小さい場合、上述のNの素因数分解が困難である範囲においてｄの値を大きくすることで、復号化処理を高速にすることが可能である。
【０３５４】
また、本実施形態の公開鍵暗号通信方法では、例えばd=3の場合、Nの素因数分解問題の困難性を前提として完全解読が不可能なことを示すことができる。すなわち、Nの素因数分解問題を解くアルゴリズムが存在すれば、そのアルゴリズムを利用して、本実施形態の公開鍵暗号通信方法の完全解読を行うアルゴリズムを構成することができる。また、本実施形態の公開鍵暗号通信方法の完全解読を行うアルゴリズムが存在すれば、そのアルゴリズムを利用して、Nの素因数分解問題を解くアルゴリズムを構成することができる。
【０３５５】
（第１３実施形態）
次に、上記の第１２実施形態の変形例を、本発明の第１３実施形態として説明する。図１４は、本発明の第１３実施形態の動作手順を説明するための図である。
【０３５６】
１．鍵生成処理
受信者側装置２００において、鍵生成部２０１は、操作者（受信者）よりの指示に従い、受信者の秘密鍵(p,q)と受信者の公開鍵(N,k,G,H)とを、それぞれ数２７８、数２７９により生成する。そして、生成情報を記憶部２０５に記憶する（ＳＴ９１００）。
【０３５７】
【数２７８】
0004230162.tif 000119
【０３５８】
【数２７９】
0004230162.tif 000120
【０３５９】
ここで、dの値は、本システムの管理者あるいは受信者が、予めまたは必要に応じて決定するものとし、鍵生成部２０１は、この決定されたｄの値を取り込んで、受信者の秘密鍵および公開鍵の生成を行なうものとする。
【０３６０】
次に、受信者は、受信者側装置２００の鍵生成部２０１が生成した受信者の公開鍵(N,k,G,H)を含む公開情報を、送信者（送信者側装置１００の操作者）に知らせる（ＳＴ９１０１）。例えば、受信者側装置２００において、鍵生成部２０１は、受信者よりの指示に従い、公開情報を、通信部２０６を介して送信者側装置１００へ送信する。あるいは、受信者は、例えば第３者(公開情報管理機関)への登録などの周知の方法により、公開情報を公開する。この公開情報は、送信者側装置１００の記憶部１０５に記憶される。
【０３６１】
なお、秘密鍵（p,q）は、これらとは別の素数p',q'から、p=2p'+1,q=2q'+1となる素数を選ぶことにより作成することも可能である。
【０３６２】
２．暗号化処理
送信者側装置１００において、入力部１０７は、操作者（送信者）よりメッセージx(x∈{0,1}n)の入力を受け付ける（ＳＴ９２００）。これを受けて、乱数生成部１０１は、メッセージxに対して乱数ｒ∈{0,1}k0を選ぶ。それから、演算部１０３は、この乱数ｒと、予め記憶部１０５に記憶しておいた受信者の公開鍵(N,k,G,H)とを用いて、数２８０を計算する（ＳＴ９２０１）。
【０３６３】
【数２８０】
0004230162.tif 000121
【０３６４】
次に、演算部１０３は、数２８０の計算結果s,tを用いて、べき乗算部１０２および剰余演算部１０４を利用して数２８１を計算する（ＳＴ９２０２）。
【０３６５】
【数２８１】
0004230162.tif 000122
【０３６６】
次に、通信部１０６は、数２８１の計算結果y1,y2を、メッセージxの暗号文として、通信回線３００を介して、受信者側装置２００に送信する（ＳＴ９２０３）。
【０３６７】
３．復号化処理
受信者側装置２００において、通信部２０６は、通信回線３００を介して送信者側装置１００より暗号文y1,y2を受け取り、これを記憶部２０５に記憶する。さて、演算部２０３は、操作者（送信者）よりの指示に従い、記憶部２０５に記憶されている受信者の秘密鍵を用いて、べき乗算部１０２および剰余演算部１０４を利用して、記憶部２０５に記憶されている暗号文y1,y2から数２８２を計算する（ＳＴ９３００）。
【０３６８】
【数２８２】
0004230162.tif 000123
【０３６９】
それから、演算部２０３は、φ(x1,p,x1,q),φ(-x1,p,x1,q),φ(x1,p,-x1,q),φ(-x1,p,-x1,q)のうち(但し、φは中国人の剰余定理によるZ/(p)×Z/(q)からZ/(pq)への環同型写像を表す)、0<x<2k-2を満たすものをs'（s'は複数存在してもよい）として、数２８３を計算する（ＳＴ９３０１〜ＳＴ９３０３）。
【０３７０】
【数２８３】
0004230162.tif 000124
【０３７１】
ここで、x'∈{0,1}n，r'∈{0,1}k0である。
【０３７２】
次に、演算部２０３は、数２８３の計算結果を用いて、数２８４に示す復号化結果を計算する（ＳＴ９３０４）。
【０３７３】
【数２８４】
0004230162.tif 000125
【０３７４】
それから、演算部２０３は、復号結果x'を出力部２０７から出力する。但し、復号化結果が「*」の場合、演算部２０３はこの暗号文y1,y2の復号を拒否しその旨を出力部２０７から出力する（ＳＴ９３０５）。
【０３７５】
本実施形態において、上述のd(d≧1)の値は変更可能である。例えば、メッセージのビット長が常に小さい場合、上述のNの素因数分解が困難である範囲においてｄの値を大きくすることで、復号化処理を高速にすることが可能である。
【０３７６】
また、本実施形態の公開鍵暗号通信方法では、例えばd=3の場合、Nの素因数分解問題の困難性を前提として完全解読が不可能なことを示すことができる。すなわち、Nの素因数分解問題を解くアルゴリズムが存在すれば、そのアルゴリズムを利用して、本実施形態の公開鍵暗号通信方法の完全解読を行うアルゴリズムを構成することができる。また、本実施形態の公開鍵暗号通信方法の完全解読を行うアルゴリズムが存在すれば、そのアルゴリズムを利用して、Nの素因数分解問題を解くアルゴリズムを構成することができる。
【０３７７】
（第１４実施形態）
次に、上記の第１２実施形態の変形例を、本発明の第１４実施形態として説明する。図１５は、本発明の第１４実施形態の動作手順を説明するための図である。
【０３７８】
１．鍵生成処理
受信者側装置２００において、鍵生成部２０１は、操作者（受信者）よりの指示に従い、受信者の秘密鍵pi(1≦i≦d)と受信者の公開鍵(N,k,G,H)とを、それぞれ数２８５、数２８６により生成する。そして、生成情報を記憶部２０５に記憶する（ＳＴ１０１００）。
【０３７９】
【数２８５】
0004230162.tif 000126
【０３８０】
【数２８６】
0004230162.tif 000127
【０３８１】
ここで、dの値は、本システムの管理者あるいは受信者が、予めまたは必要に応じて決定するものとし、鍵生成部２０１は、この決定されたｄの値を取り込んで、受信者の秘密鍵および公開鍵の生成を行なうものとする。
【０３８２】
次に、受信者は、受信者側装置２００の鍵生成部２０１が生成した受信者の公開鍵(N,k,G,H)を含む公開情報を、送信者（送信者側装置１００の操作者）に知らせる（ＳＴ１０１０１）。例えば、受信者側装置２００において、鍵生成部２０１は、受信者よりの指示に従い、公開情報を、通信部２０６を介して送信者側装置１００へ送信する。あるいは、受信者は、例えば第３者(公開情報管理機関)への登録などの周知の方法により、公開情報を公開する。この公開情報は、送信者側装置１００の記憶部１０５に記憶される。
【０３８３】
なお、秘密鍵piは、これらとは別の素数p'から、p=2p'+1となる素数を選ぶことにより作成することも可能である。
【０３８４】
２．暗号化処理
送信者側装置１００において、入力部１０７は、操作者（送信者）よりメッセージx(x∈{0,1}n)の入力を受け付ける（ＳＴ１０２００）。これを受けて、乱数生成部１０１は、メッセージxに対して乱数ｒ∈{0,1}k0を選ぶ。それから、演算部１０３は、この乱数ｒと、予め記憶部１０５に記憶しておいた受信者の公開鍵(N,k,G,H)とを用いて、数２８７を計算する（ＳＴ１０２０１）。
【０３８５】
【数２８７】
0004230162.tif 000128
【０３８６】
ここで、k-1≦log2(N+1)である。
【０３８７】
次に、演算部１０３は、数２８７の計算結果s,tを用いて、べき乗算部１０２および剰余演算部１０４を利用して数２８８を計算する（ＳＴ１０２０２）。
【０３８８】
【数２８８】
0004230162.tif 000129
【０３８９】
次に、通信部１０６は、数２８８の計算結果y1,y2を、メッセージxの暗号文として、通信回線３００を介して、受信者側装置２００に送信する（ＳＴ１０２０３）。
【０３９０】
３．復号化処理
受信者側装置２００において、通信部２０６は、通信回線３００を介して送信者側装置１００より暗号文y1,y2を受け取り、これを記憶部２０５に記憶する。さて、演算部２０３は、操作者（送信者）よりの指示に従い、記憶部２０５に記憶されている受信者の秘密鍵を用いて、べき乗算部１０２および剰余演算部１０４を利用して、記憶部２０５に記憶されている暗号文y1,y2から数２８９を計算する（ＳＴ１０３００）。
【０３９１】
【数２８９】
0004230162.tif 000130
【０３９２】
それから、演算部２０３は、2d個のφ(±x1,p1,±x1,p2,．．．,±x1,pd)のうち(但し、φは中国人の剰余定理によるZ/(p1)×Z/(q2)×．．．×Z/(qd)からZ/(N)への環同型写像を表す)、0＜s'＜N/2を満たすものをs'（s'は複数存在してもよい）として、数２９０を計算する（ＳＴ１０３０１、ＳＴ１０３０２）。
【０３９３】
【数２９０】
0004230162.tif 000131
【０３９４】
ここで、x'∈{0,1}n，r'∈{0,1}k0である。
【０３９５】
次に、演算部２０３は、数２９０の計算結果を用いて、数２９１に示す復号化結果を計算する（ＳＴ１０３０３）。
【０３９６】
【数２９１】
0004230162.tif 000132
【０３９７】
それから、演算部２０３は、復号結果x'を出力部２０７から出力する。但し、復号化結果が「*」の場合、演算部２０３はこの暗号文y1,y2の復号を拒否しその旨を出力部２０７から出力する（ＳＴ１０３０４）。
【０３９８】
本実施形態において、上述のd(d＞1)の値は変更可能である。本実施形態の公開鍵暗号通信方法では、例えばd=3の場合、Nの素因数分解問題の困難性を前提として完全解読が不可能なことを示すことができる。すなわち、Nの素因数分解問題を解くアルゴリズムが存在すれば、そのアルゴリズムを利用して、本実施形態の公開鍵暗号通信方法の完全解読を行うアルゴリズムを構成することができる。また、本実施形態の公開鍵暗号通信方法の完全解読を行うアルゴリズムが存在すれば、そのアルゴリズムを利用して、Nの素因数分解問題を解くアルゴリズムを構成することができる。
【０３９９】
（第１５実施形態）
次に、上記の第１１実施形態を、共通鍵暗号におけるデータ暗号化鍵の配送を目的として、既存の暗号方法（例えば共通鍵暗号）と一緒に使用するようにした場合を、本発明の第１５実施形態として説明する。
【０４００】
１．鍵生成処理
受信者側装置２００において、鍵生成部２０１は、操作者（受信者）よりの指示に従い、受信者の公開鍵(f,G,H)と受信者の秘密鍵とを、それぞれ数２９２、数２９３により生成する。そして、生成情報を記憶部２０５に記憶する。
【０４０１】
【数２９２】
0004230162.tif 000133
【０４０２】
【数２９３】
0004230162.tif 000134
【０４０３】
次に、受信者は、受信者側装置２００の鍵生成部２０１が生成した受信者の公開鍵(f,G,H)を含む公開情報を、送信者（送信者側装置１００の操作者）に知らせる。例えば受信者側装置２００において、鍵生成部２０１は、受信者よりの指示に従い、公開情報を通信部２０６を介して送信者側装置１００へ送信する。あるいは、受信者は、例えば第３者(公開情報管理機関)への登録などの周知の方法により、公開情報を公開する。この公開情報は、送信者側装置１００の記憶部１０５に記憶される。
【０４０４】
２．暗号化処理
送信者側装置１００において、入力部１０７は、操作者（送信者）より送信メッセージmの入力を受け付けると、暗号化部１０８は、データ暗復号化鍵K(K∈{0,1}n)を用いて、既存の暗号化方法によりメッセージmを暗号化し、暗号文cを作成する。次に、乱数生成部１０１は、データ暗復号化鍵Kに対して乱数ｒ∈{0,1}k0を選ぶ。それから、演算部１０３は、この乱数ｒと、予め記憶部１０５に記憶しておいた受信者の公開鍵(f,G,H)とを用いて、数２９４を計算する。
【０４０５】
【数２９４】
0004230162.tif 000135
【０４０６】
次に、演算部１０３は、数２９４の計算結果s,tを用いて、数２９５を計算する。
【０４０７】
【数２９５】
0004230162.tif 000136
【０４０８】
次に、通信部１０６は、数２９５の暗号結果y1,y2をメッセージmの暗号文cと共に、通信回線３００を介して受信者側装置２００に送信する。
【０４０９】
３．復号化処理
受信者側装置２００において、通信部２０６は、通信回線３００を介して送信者側装置１００より暗号結果y1,y2を暗号文cと共に受け取り、これを記憶部２０５に記憶する。さて、演算部２０３は、操作者（送信者）よりの指示に従い、記憶部２０５に記憶されている受信者の秘密鍵を用いて、記憶部２０５に記憶されている暗号結果y1,y2から数２９６を計算する。
【０４１０】
【数２９６】
0004230162.tif 000137
【０４１１】
次に、演算部２０３は、数２９６の計算結果を用いて、数２９７を計算する。
【０４１２】
【数２９７】
0004230162.tif 000138
【０４１３】
ここで、K'∈{0,1}n，r'∈{0,1}k0である。次に、演算部２０３は、数２９７の計算結果を用いて、数２９８に示す復号化結果を計算する。
【０４１４】
【数２９８】
0004230162.tif 000139
【０４１５】
但し、復号化結果が「*」の場合、演算部２０３はこの暗号結果y1,y2の復号を拒否し、その旨を出力部２０７から出力する。
【０４１６】
次に、復号化部２０８は、数２９８による復号結果K'（つまり、データ暗復号化鍵K）を用いて、記憶部２０５に記憶されている暗号文cを既存の暗号方法により復号化する。そして、その復号結果（つまりメッセージm）を出力部２０７から出力する。
【０４１７】
（第１６実施形態）
次に、上記の第１２実施形態を、共通鍵暗号におけるデータ暗号化鍵の配送を目的として、既存の暗号方法（例えば共通鍵暗号）と一緒に使用するようにした場合を、本発明の第１６実施形態として説明する。
【０４１８】
１．鍵生成処理
受信者側装置２００において、鍵生成部２０１は、操作者（受信者）よりの指示に従い、受信者の秘密鍵(p,q)と受信者の公開鍵(N,k,G,H)とを、それぞれ数２９９、数３００により生成する。そして、生成情報を記憶部２０５に記憶する。
【０４１９】
【数２９９】
0004230162.tif 000140
【０４２０】
【数３００】
0004230162.tif 000141
【０４２１】
次に、受信者は、受信者側装置２００の鍵生成部２０１が生成した受信者の公開鍵(N,k,G,H)を含む公開情報を、送信者（送信者側装置１００の操作者）に知らせる。例えば受信者側装置２００において、鍵生成部２０１は、受信者よりの指示に従い、公開情報を通信部２０６を介して送信者側装置１００へ送信する。あるいは、受信者は、例えば第３者(公開情報管理機関)への登録などの周知の方法により、公開情報を公開する。この公開情報は送信者側装置１００の記憶部１０５に記憶される。
【０４２２】
２．暗号化処理
送信者側装置１００において、入力部１０７は、操作者（送信者）より送信メッセージmの入力を受け付けると、暗号化部１０８は、データ暗復号化鍵K(K∈{0,1}n)を用いて、既存の暗号化方法によりメッセージmを暗号化し、暗号文cを作成する。次に、乱数生成部１０１は、データ暗復号化鍵Kに対して乱数ｒ∈{0,1}k0を選ぶ。それから、演算部１０３は、この乱数ｒと、予め記憶部１０５に記憶しておいた受信者の公開鍵(N,k,G,H)とを用いて、数３０１を計算する。
【０４２３】
【数３０１】
0004230162.tif 000142
【０４２４】
次に、演算部１０３は、数３０１の計算結果s,tを用いて、べき乗算部１０２および剰余演算部１０４を利用して数３０２を計算する。
【０４２５】
【数３０２】
0004230162.tif 000143
【０４２６】
ここで、a=(m/N)はJacobi記号を表す。次に、通信部１０６は、数３０２の暗号結果y1,y2,y3を、メッセージmの暗号文cと共に、通信回線３００を介して受信者側装置２００に送信する。
【０４２７】
３．復号化処理
受信者側装置２００において、通信部２０６は、通信回線３００を介して送信者側装置１００より暗号結果y1,y2,y3を暗号文cと共に受け取り、これを記憶部２０５に記憶する。さて、演算部２０３は、操作者（送信者）よりの指示に従い、記憶部２０５に記憶されている受信者の秘密鍵を用いて、記憶部２０５に記憶されている暗号結果y1,y2,y3から数３０３を計算する。
【０４２８】
【数３０３】
0004230162.tif 000144
【０４２９】
それから、演算部２０３は、φ(x1,p,x1,q),φ(-x1,p,x1,q),φ(x1,p,-x1,q),φ(-x1,p,-x1,q)のうち(但し、φは中国人の剰余定理によるZ/(p)×Z/(q)からZ/(pq)への環同型写像を表す)、(x/N)=y3かつ0<x<2k-2を満たすものをs'として、数３０４を計算する。
【０４３０】
【数３０４】
0004230162.tif 000145
【０４３１】
ここで、k'∈{0,1}n，r'∈{0,1}k0である。次に、演算部２０３は、数３０４の計算結果を用いて、数３０５に示す復号化結果を計算する。
【０４３２】
【数３０５】
0004230162.tif 000146
【０４３３】
但し、復号化結果が「*」の場合、演算部２０３はこの暗号結果y1,y2,y3の復号を拒否し、その旨を出力部２０７から出力する。
【０４３４】
次に、復号化部２０８は、数３０５による復号結果K'（つまり、データ暗復号化鍵K）を用いて、記憶部２０５に記憶されている暗号文cを既存の暗号方法により復号化する。そして、その復号結果（つまりメッセージm）を出力部２０７から出力する。
【０４３５】
（第１７実施形態）
次に、上記の第１３実施形態を、共通鍵暗号におけるデータ暗号化鍵の配送を目的として、既存の暗号方法（例えば共通鍵暗号）と一緒に使用するようにした場合を、本発明の第１７実施形態として説明する。
【０４３６】
１．鍵生成処理
受信者側装置２００において、鍵生成部２０１は、操作者（受信者）よりの指示に従い、受信者の秘密鍵(p,q)と受信者の公開鍵(N,k,G,H)とを、それぞれ数３０６、数３０７により生成する。そして、生成情報を記憶部２０５に記憶する。
【０４３７】
【数３０６】
0004230162.tif 000147
【０４３８】
【数３０７】
0004230162.tif 000148
【０４３９】
次に、受信者は、受信者側装置２００の鍵生成部２０１が生成した受信者の公開鍵(N,k,G,H)を含む公開情報を、送信者（送信者側装置１００の操作者）に知らせる。例えば受信者側装置２００において、鍵生成部２０１は、受信者よりの指示に従い、公開情報を通信部２０６を介して送信者側装置１００へ送信する。あるいは、受信者は、例えば第３者(公開情報管理機関)への登録などの周知の方法により、公開情報を公開する。この公開情報は送信者側装置１００の記憶部１０５に記憶される。
【０４４０】
２．暗号化処理
送信者側装置１００において、入力部１０７は、操作者（送信者）より送信メッセージmの入力を受け付けると、暗号化部１０８は、データ暗復号化鍵K(K∈{0,1}n)を用いて、既存の暗号化方法によりメッセージmを暗号化し、暗号文cを作成する。次に、乱数生成部１０１は、データ暗復号化鍵Kに対して乱数ｒ∈{0,1}k0を選ぶ。それから、演算部１０３は、この乱数ｒと、予め記憶部１０５に記憶しておいた受信者の公開鍵(N,k,G,H)とを用いて、数３０８を計算する。
【０４４１】
【数３０８】
0004230162.tif 000149
【０４４２】
次に、演算部１０３は、数３０８の計算結果s,tを用いて、べき乗算部１０２および剰余演算部１０４を利用して数３０９を計算する。
【０４４３】
【数３０９】
0004230162.tif 000150
【０４４４】
次に、通信部１０６は、数３０９の暗号結果y1,y2を、メッセージmの暗号文cと共に、通信回線３００を介して受信者側装置２００に送信する。
【０４４５】
３．復号化処理
受信者側装置２００において、通信部２０６は、通信回線３００を介して送信者側装置１００より暗号結果y1,y2を暗号文cと共に受け取り、これを記憶部２０５に記憶する。さて、演算部２０３は、操作者（送信者）よりの指示に従い、記憶部２０５に記憶されている受信者の秘密鍵を用いて、べき乗算部２０２および剰余演算部２０４を利用して、記憶部２０５に記憶されている暗号結果y1,y2から数３１０を計算する。
【０４４６】
【数３１０】
0004230162.tif 000151
【０４４７】
それから、演算部２０３は、φ(x1,p,x1,q),φ(-x1,p,x1,q),φ(x1,p,-x1,q),φ(-x1,p,-x1,q)のうち(但し、φは中国人の剰余定理によるZ/(p)×Z/(q)からZ/(pq)への環同型写像を表す)、0<x<2k-2を満たすものをs'（s'は複数存在してもよい）として、数３１１を計算する。
【０４４８】
【数３１１】
0004230162.tif 000152
【０４４９】
ここで、k'∈{0,1}n，r'∈{0,1}k0である。次に、演算部２０３は、数３１１の計算結果を用いて、数３１２に示す復号化結果を計算する。
【０４５０】
【数３１２】
0004230162.tif 000153
【０４５１】
但し、復号化結果が「*」の場合、演算部２０３はこの暗号結果y1,y2の復号を拒否し、その旨を出力部２０７から出力する。
【０４５２】
次に、復号化部２０８は、数３１２による復号結果K'（つまり、データ暗復号化鍵K）を用いて、記憶部２０５に記憶されている暗号文cを既存の暗号方法により復号化する。そして、その復号結果（つまりメッセージm）を出力部２０７から出力する。
【０４５３】
（第１８実施形態）
次に、上記の第１２実施形態の変形例を、共通鍵暗号におけるデータ暗号化鍵の配送を目的として、既存の暗号方法（例えば共通鍵暗号）と一緒に使用するようにした場合を、本発明の第１８実施形態として説明する。
【０４５４】
１．鍵生成処理
受信者側装置２００において、鍵生成部２０１は、操作者（受信者）よりの指示に従い、受信者の秘密鍵pi(1≦d)と受信者の公開鍵(N,k,G,H)とを、それぞれ数３１３、数３１４により生成する。そして、生成情報を記憶部２０５に記憶する。
【０４５５】
【数３１３】
0004230162.tif 000154
【０４５６】
【数３１４】
0004230162.tif 000155
【０４５７】
次に、受信者は、受信者側装置２００の鍵生成部２０１が生成した受信者の公開鍵(N,k,G,H)を含む公開情報を、送信者（送信者側装置１００の操作者）に知らせる。例えば受信者側装置２００において、鍵生成部２０１は、受信者よりの指示に従い、公開情報を通信部２０６を介して送信者側装置１００へ送信する。あるいは、受信者は、例えば第３者(公開情報管理機関)への登録などの周知の方法により、公開情報を公開する。この公開情報は送信者側装置１００の記憶部１０５に記憶される。
【０４５８】
２．暗号化処理
送信者側装置１００において、入力部１０７は、操作者（送信者）より送信メッセージmの入力を受け付けると、暗号化部１０８は、データ暗復号化鍵K(K∈{0,1}n)を用いて、既存の暗号化方法によりメッセージmを暗号化し、暗号文cを作成する。次に、乱数生成部１０１は、データ暗復号化鍵Kに対して乱数ｒ∈{0,1}k0を選ぶ。それから、演算部１０３は、この乱数ｒと、予め記憶部１０５に記憶しておいた受信者の公開鍵(N,k,G,H)とを用いて、数３１５を計算する。
【０４５９】
【数３１５】
0004230162.tif 000156
【０４６０】
ここで、k-1≦log2(N+1)である。次に、演算部１０３は、数３１５の計算結果s,tを用いて、べき乗算部１０２および剰余演算部１０４を利用して数３１６を計算する。
【０４６１】
【数３１６】
0004230162.tif 000157
【０４６２】
次に、通信部１０６は、数３１６の暗号結果y1,y2を、メッセージmの暗号文cと共に、通信回線３００を介して受信者側装置２００に送信する。
【０４６３】
３．復号化処理
受信者側装置２００において、通信部２０６は、通信回線３００を介して送信者側装置１００より暗号結果y1,y2を暗号文cと共に受け取り、これを記憶部２０５に記憶する。さて、演算部２０３は、操作者（送信者）よりの指示に従い、記憶部２０５に記憶されている受信者の秘密鍵を用いて、べき乗算部２０２および剰余演算部２０４を利用して、記憶部２０５に記憶されている暗号結果y1,y2から数３１７を計算する。
【０４６４】
【数３１７】
0004230162.tif 000158
【０４６５】
それから、演算部２０３は、2d個のφ(±x1,p1,±x1,p2,．．．,±x1,pd)のうち(但し、φは中国人の剰余定理によるZ/(p1)×Z/(q2)×．．．×Z/(qd)からZ/(N)への環同型写像を表す)、0＜s'＜N/2を満たすものをs'（s'は複数存在してもよい）として、数３１８を計算する。
【０４６６】
【数３１８】
0004230162.tif 000159
【０４６７】
ここで、K'∈{0,1}n，r'∈{0,1}k0である。次に、演算部２０３は、数３１８の計算結果を用いて、数３１９に示す復号化結果を計算する。
【０４６８】
【数３１９】
0004230162.tif 000160
【０４６９】
但し、復号化結果が「*」の場合、演算部２０３はこの暗号結果y1,y2の復号を拒否し、その旨を出力部２０７から出力する。
【０４７０】
次に、復号化部２０８は、数３１９による復号結果K'（つまり、データ暗復号化鍵K）を用いて、記憶部２０５に記憶されている暗号文cを既存の暗号方法により復号化する。そして、その復号結果（つまりメッセージm）を出力部２０７から出力する。
【０４７１】
（第１９実施形態）
次に、本発明の第１９実施形態について、送信者が受信者に対して、送信データとなるメッセージを暗号通信によって送信する場合を例にとり説明する。図１６は、本発明の第１９実施形態の動作手順を説明するための図である。
【０４７２】
１．鍵生成処理
受信者側装置２００において、鍵生成部２０１は、操作者（受信者）よりの指示に従い、受信者の公開鍵(f,G,H)と受信者の秘密鍵とを、それぞれ数３２０、数３２１により生成する。そして、生成情報を記憶部２０５に記憶する（ＳＴ１１１００）。
【０４７３】
【数３２０】
0004230162.tif 000161
【０４７４】
【数３２１】
0004230162.tif 000162
【０４７５】
次に、受信者は、受信者側装置２００の鍵生成部２０１が生成した受信者の公開鍵(f,G,H)を含む公開情報を、送信者（送信者側装置１００の操作者）に知らせる（ＳＴ１１１０１）。例えば、受信者側装置２００において、鍵生成部２０１は、受信者よりの指示に従い、公開情報を、通信部２０６を介して送信者側装置１００へ送信する。あるいは、受信者は、例えば第３者(公開情報管理機関)への登録などの周知の方法により、公開情報を公開する。この公開情報は、送信者側装置１００の記憶部１０５に記憶される。
【０４７６】
２．暗号化処理
送信者側装置１００において、入力部１０７は、操作者（送信者）よりメッセージx(x∈{0,1}n)の入力を受け付ける（ＳＴ１１２００）。これを受けて、乱数生成部１０１は、メッセージxに対して乱数ｒ∈{0,1}kを選ぶ。それから、演算部１０３は、この乱数ｒと、予め記憶部１０５に記憶しておいた受信者の公開鍵(f,G,H)とを用いて、数３２２を計算する（ＳＴ７２０１）。
【０４７７】
【数３２２】
0004230162.tif 000163
【０４７８】
通信部１０６は、数３２２の計算結果y1,y2を、メッセージxの暗号文として、通信回線３００を介して、受信者側装置２００に送信する（ＳＴ１１２０２）。
【０４７９】
３．復号化処理
受信者側装置２００において、通信部２０６は、通信回線３００を介して送信者側装置１００より暗号文y1,y2を受け取り、これを記憶部２０５に記憶する。さて、演算部２０３は、操作者（送信者）よりの指示に従い、記憶部２０５に記憶されている受信者の秘密鍵を用いて、記憶部２０５に記憶されている暗号文y1,y2から数３２３を計算する（ＳＴ１１３００）。
【０４８０】
【数３２３】
0004230162.tif 000164
【０４８１】
次に、演算部２０３は、数３２３の計算結果を用いて、数３２４を計算する（ＳＴ１１３０１）。
【０４８２】
【数３２４】
0004230162.tif 000165
【０４８３】
但し、x'∈{0,1}n，w'∈{0,1}k0である。
【０４８４】
次に、演算部２０３は、数３２４の計算結果を用いて、数３２５に示す復号化結果を計算する（ＳＴ１１３０２）。
【０４８５】
【数３２５】
0004230162.tif 000166
【０４８６】
それから、演算部２０３は、復号結果x'を出力部２０７から出力する。但し、復号化結果が「*」の場合、演算部２０３はこの暗号文y1,y2の復号を拒否し、その旨を出力部２０７から出力する（ＳＴ１１３０３）。
【０４８７】
本実施形態の公開鍵暗号通信方法によれば、上記の第３実施形態と同様に、一方向性置換ｆの逆関数を求めることが困難であることを前提にして、選択暗号文攻撃に対して強秘匿であることが証明できる。
【０４８８】
なお、本実施形態は、上記の第３実施形態および第１１実施形態と比較して、暗号文の一部であるy1を前処理計算できる利点がある。すなわち、メッセージxとは無関係にy1を計算できるため、前もって計算しておくことにより高速な暗号化処理が可能となる。
【０４８９】
また、本実施形態は、上記の第１１実施形態と同様に、メッセージの長さnを関数ｆに依らずに設定することができる利点がある。すなわち、nの値を送信したいメッセージの長さに応じて、ユーザが勝手に設定することが可能である。
【０４９０】
（第２０実施形態）
次に、上記の第１９実施形態の具体例を、本発明の第２０実施形態として説明する。図１７は、本発明の第２０実施形態の動作手順を説明するための図である。
【０４９１】
１．鍵生成処理
受信者側装置２００において、鍵生成部２０１は、操作者（受信者）よりの指示に従い、受信者の秘密鍵(p,q)と受信者の公開鍵(N,k,G,H)とを、それぞれ数３２６、数３２７により生成する。そして、生成情報を記憶部２０５に記憶する（ＳＴ１２１００）。
【０４９２】
【数３２６】
0004230162.tif 000167
【０４９３】
【数３２７】
0004230162.tif 000168
【０４９４】
次に、受信者は、受信者側装置２００の鍵生成部２０１が生成した受信者の公開鍵(N,k,G,H)を含む公開情報を、送信者（送信者側装置１００の操作者）に知らせる（ＳＴ１２１０１）。例えば、受信者側装置２００において、鍵生成部２０１は、受信者よりの指示に従い、公開情報を、通信部２０６を介して送信者側装置１００へ送信する。あるいは、受信者は、例えば第３者(公開情報管理機関)への登録などの周知の方法により、公開情報を公開する。この公開情報は、送信者側装置１００の記憶部１０５に記憶される。
【０４９５】
なお、秘密鍵p,qは、これらとは別の素数p',q'からp=2p'+1,q=2q'+1により作成することも可能である。
【０４９６】
２．暗号化処理
送信者側装置１００において、入力部１０７は、操作者（送信者）よりメッセージx(x∈{0,1}n)の入力を受け付ける（ＳＴ１２２００）。これを受けて、乱数生成部１０１は、メッセージxに対して乱数ｒ∈{0,1}k-2を選ぶ。それから、演算部１０３は、この乱数ｒと、予め記憶部１０５に記憶しておいた受信者の公開鍵(N,k,G,H)とを用いて、べき乗算部１０２および剰余演算部１０４を利用して、数３２８を計算する（ＳＴ１２２０１）。
【０４９７】
【数３２８】
0004230162.tif 000169
【０４９８】
ここで、a=(m/N)はJacobi記号を表す。通信部１０６は、数３２８の計算結果y1,y2,y3を、メッセージxの暗号文として、通信回線３００を介して、受信者側装置２００に送信する（ＳＴ１２２０２）。
【０４９９】
３．復号化処理
受信者側装置２００において、通信部２０６は、通信回線３００を介して送信者側装置１００より暗号文y1,y2,y3を受け取り、これを記憶部２０５に記憶する。さて、演算部２０３は、操作者（送信者）よりの指示に従い、記憶部２０５に記憶されている受信者の秘密鍵を用いて、記憶部２０５に記憶されている暗号文y1,y2,y3から数３２９を計算する（ＳＴ１２３００）。
【０５００】
【数３２９】
0004230162.tif 000170
【０５０１】
それから、演算部２０３は、φ(r1,p,r1,q),φ(-r1,p,r1,q),φ(r1,p,-r1,q),φ(-r1,p,-r1,q)のうち(但し、φは中国人の剰余定理によるZ/(p)×Z/(q)からZ/(pq)への環同型写像を表す)、(r/N)=y3かつ0<r<2k-2を満たすものをr'として数３３０を計算する（ＳＴ１２３０１〜ＳＴ１２３０３）。
【０５０２】
【数３３０】
0004230162.tif 000171
【０５０３】
ここで、x'∈{0,1}n，w'∈{0,1}k0である。次に、演算部２０３は、数３３０の計算結果を用いて、数３３１に示す復号化結果を計算する。
【０５０４】
【数３３１】
0004230162.tif 000172
【０５０５】
但し、復号化結果が「*」の場合、演算部２０３はこの暗号結果y1,y2,y3の復号を拒否し、その旨を出力部２０７から出力する。
【０５０６】
本実施形態において、上述のｄ(ｄ≧１)の値は変更可能である。例えば、メッセージのビット長が常に小さい場合、上述のNの素因数分解が困難である範囲においてｄの値を大きくすることで、復号化処理を高速にすることが可能である。
【０５０７】
本実施形態の公開鍵暗号通信方法では、例えばd=3の場合、Nの素因数分解問題の困難性を前提として完全解読が不可能なことを示すことができる。すなわち、Nの素因数分解問題を解くアルゴリズムが存在すれば、そのアルゴリズムを利用して、本実施形態の公開鍵暗号通信方法の完全解読を行うアルゴリズムを構成することができる。また、本実施形態の公開鍵暗号通信方法の完全解読を行うアルゴリズムが存在すれば、そのアルゴリズムを利用して、Nの素因数分解問題を解くアルゴリズムを構成することができる。
【０５０８】
（第２１実施形態）
次に、上記の第１９実施形態の変形例を、本発明の第２１実施形態として説明する。図１８は、本発明の第２１実施形態の動作手順を説明するための図である。
【０５０９】
１．鍵生成処理
受信者側装置２００において、鍵生成部２０１は、操作者（受信者）よりの指示に従い、受信者の秘密鍵(p,q)と受信者の公開鍵(N,k,G,H)とを、それぞれ数３３２、数３３３により生成する。そして、生成情報を記憶部２０５に記憶する（ＳＴ１３１００）。
【０５１０】
【数３３２】
0004230162.tif 000173
【０５１１】
【数３３３】
0004230162.tif 000174
【０５１２】
次に、受信者は、受信者側装置２００の鍵生成部２０１が生成した受信者の公開鍵(N,k,G,H)を含む公開情報を、送信者（送信者側装置１００の操作者）に知らせる（ＳＴ１３１０１）。例えば、受信者側装置２００において、鍵生成部２０１は、受信者よりの指示に従い、公開情報を、通信部２０６を介して送信者側装置１００へ送信する。あるいは、受信者は、例えば第３者(公開情報管理機関)への登録などの周知の方法により、公開情報を公開する。この公開情報は、送信者側装置１００の記憶部１０５に記憶される。
【０５１３】
なお、秘密鍵p,qは、これらとは別の素数p',q'からp=2p'+1,q=2q'+1により作成することも可能である。
【０５１４】
２．暗号化処理
送信者側装置１００において、入力部１０７は、操作者（送信者）よりメッセージx(x∈{0,1}n)の入力を受け付ける（ＳＴ１３２００）。これを受けて、乱数生成部１０１は、メッセージxに対して乱数ｒ∈{0,1}k-2を選ぶ。それから、演算部１０３は、この乱数ｒと、予め記憶部１０５に記憶しておいた受信者の公開鍵(N,k,G,H)とを用いて、べき乗算部１０２および剰余演算部１０４を利用して、数３３４を計算する（ＳＴ１３２０１）。
【０５１５】
【数３３４】
0004230162.tif 000175
【０５１６】
通信部１０６は、数３３４の計算結果y1,y2を、メッセージxの暗号文として、通信回線３００を介して、受信者側装置２００に送信する（ＳＴ１３２０２）。
【０５１７】
３．復号化処理
受信者側装置２００において、通信部２０６は、通信回線３００を介して送信者側装置１００より暗号文y1,y2を受け取り、これを記憶部２０５に記憶する。さて、演算部２０３は、操作者（送信者）よりの指示に従い、記憶部２０５に記憶されている受信者の秘密鍵を用いて、記憶部２０５に記憶されている暗号文y1,y2から数３３５を計算する（ＳＴ１３３００）。
【０５１８】
【数３３５】
0004230162.tif 000176
【０５１９】
それから、演算部２０３は、φ(r1,p,r1,q),φ(-r1,p,r1,q),φ(r1,p,-r1,q),φ(-r1,p,-r1,q)のうち(但し、φは中国人の剰余定理によるZ/(p)×Z/(q)からZ/(pq)への環同型写像を表す)、0<r<2k-2を満たすものをr'（r'は複数存在してもよい）として数３３６を計算する（ＳＴ１３３０１〜ＳＴ１３３０３）。
【０５２０】
【数３３６】
0004230162.tif 000177
【０５２１】
ここで、x'∈{0,1}n，w'∈{0,1}k0である。次に、演算部２０３は、数３３６の計算結果を用いて、数３３７に示す復号化結果を計算する。
【０５２２】
【数３３７】
0004230162.tif 000178
【０５２３】
但し、復号化結果が「*」の場合、演算部２０３はこの暗号結果y1,y2の復号を拒否し、その旨を出力部２０７から出力する。
【０５２４】
本実施形態において、上述のd(d≧1)の値は変更可能である。例えば、メッセージのビット長が常に小さい場合、上述のNの素因数分解が困難である範囲においてｄの値を大きくすることで、復号化処理を高速にすることが可能である。
【０５２５】
本実施形態の公開鍵暗号通信方法では、例えばd=3の場合、Nの素因数分解問題の困難性を前提として完全解読が不可能なことを示すことができる。すなわち、Nの素因数分解問題を解くアルゴリズムが存在すれば、そのアルゴリズムを利用して、本実施形態の公開鍵暗号通信方法の完全解読を行うアルゴリズムを構成することができる。また、本実施形態の公開鍵暗号通信方法の完全解読を行うアルゴリズムが存在すれば、そのアルゴリズムを利用して、Nの素因数分解問題を解くアルゴリズムを構成することができる。
【０５２６】
（第２２実施形態）
次に、上記の第６実施形態の変形例を、本発明の第２２実施形態として説明する。
【０５２７】
１．鍵生成処理
受信者側装置２００において、鍵生成部２０１は、操作者（受信者）よりの指示に従い、受信者の秘密鍵pi(1≦i≦d)と受信者の公開鍵(N,k,H1,H2)とを、それぞれ数３３８、数３３９により生成する。そして、生成情報を記憶部２０５に記憶する。
【０５２８】
【数３３８】
0004230162.tif 000179
【０５２９】
【数３３９】
0004230162.tif 000180
【０５３０】
次に、受信者は、受信者側装置２００の鍵生成部２０１が生成した受信者の公開鍵(N,k,H1,H2)を含む公開情報を、送信者（送信者側装置１００の操作者）に知らせる。例えば、受信者側装置２００において、鍵生成部２０１は、受信者よりの指示に従い、公開情報を、通信部２０６を介して送信者側装置１００へ送信する。あるいは、受信者は、例えば第３者(公開情報管理機関)への登録などの周知の方法により、公開情報を公開する。この公開情報は、送信者側装置１００の記憶部１０５に記憶される。
【０５３１】
なお、秘密鍵piは、これらとは別の素数p'からp=2p'+1により作成することも可能である。
【０５３２】
２．暗号化処理
送信者側装置１００において、入力部１０７は、操作者（送信者）よりメッセージx(x∈{0,1}n)の入力を受け付ける。これを受けて、乱数生成部１０１は、メッセージxに対して乱数ｒ∈{0,1}k0を選ぶ。それから、演算部１０３は、この乱数ｒと、予め記憶部１０５に記憶しておいた受信者の公開鍵(N,k,H1,H2)とを用いて、数３４０を計算する。
【０５３３】
【数３４０】
0004230162.tif 000181
【０５３４】
ここで、n+k0+k1≦log2(N+1)である。次に、演算部１０３は、数３４０の計算結果s,tを用いて、べき乗算部１０２および剰余演算部１０４を利用して、数３４１を計算する。
【０５３５】
【数３４１】
0004230162.tif 000182
【０５３６】
通信部１０６は、数３４１の計算結果y1を、メッセージxの暗号文として、通信回線３００を介して、受信者側装置２００に送信する。
【０５３７】
３．復号化処理
受信者側装置２００において、通信部２０６は、通信回線３００を介して送信者側装置１００より暗号文y1を受け取り、これを記憶部２０５に記憶する。さて、演算部２０３は、操作者（送信者）よりの指示に従い、記憶部２０５に記憶されている受信者の秘密鍵を用いて、記憶部２０５に記憶されている暗号文y1から数３４２を計算する。
【０５３８】
【数３４２】
0004230162.tif 000183
【０５３９】
それから、演算部２０３は、2d個のφ(±x1,p1,±x1,p2,．．．,±x1,pd)のうち(但し、φは中国人の剰余定理によるZ/(p1)×Z/(q2)×．．．×Z/(qd)からZ/(N)への環同型写像を表す)、0＜w'＜N/2を満たすものをw'（w'は複数存在してもよい）とし、さらに、w'=s1'||s2'||t'(s1'∈{0,1}n，s2'∈{0,1}k1，t'∈{0,1}k0)として、数３４３を計算する。
【０５４０】
【数３４３】
0004230162.tif 000184
【０５４１】
次に、演算部２０３は、数３４３の計算結果を用いて、数３４４に示す復号化結果を計算する。
【０５４２】
【数３４４】
0004230162.tif 000185
【０５４３】
但し、復号化結果が「*」の場合、演算部２０３はこの暗号結果y1の復号を拒否し、その旨を出力部２０７から出力する。
【０５４４】
本実施形態において、上述のｄ(ｄ＞１)の値は変更可能である。本実施形態の公開鍵暗号通信方法では、Nの素因数分解問題の困難性を前提として完全解読が不可能なことを示すことができる。すなわち、Nの素因数分解問題を解くアルゴリズムが存在すれば、そのアルゴリズムを利用して、本実施形態の公開鍵暗号通信方法の完全解読を行うアルゴリズムを構成することができる。また、本実施形態の公開鍵暗号通信方法の完全解読を行うアルゴリズムが存在すれば、そのアルゴリズムを利用して、Nの素因数分解問題を解くアルゴリズムを構成することができる。
【０５４５】
以上、本発明の実施の形態について説明した。
【０５４６】
なお、本発明は、上記の各実施形態に限定されるものではなく、その要旨の範囲内で数々の変形が可能である。
【０５４７】
例えば、上記の各実施形態では、送信者と受信者とが各々の装置を利用して暗号通信を行うという一般的な通信システムを例にとり説明したが、本発明は、様々なシステムに適用可能である。
【０５４８】
例えば、電子ショッピングシステムでは、送信者はユーザであり、送信者側装置はパソコンなどの計算機であり、受信者は小売店であり、受信者側装置はパソコンなどの計算機となる。この場合、ユーザの商品等の注文書は、共通鍵暗号で暗号化されることが多く、その際の暗号化鍵が本発明の公開鍵暗号通信方法により暗号化されて、小売店側装置に送信される。
【０５４９】
また、電子メールシステムでは、各々の装置はパソコンなどの計算機であり、送信文(メール)は共通鍵暗号で暗号化されることが多い。この場合は、共通鍵が本発明の公開鍵暗号通信方法により暗号化されて、受信者の計算機に送信される。
【０５５０】
その他にも、従来の公開鍵暗号が使われている様々なシステムに適用することが可能である。
【０５５１】
また、上記の各実施形態での各計算は、ＣＰＵがメモリ上にロードされたプログラムを実行することにより行われるものとして説明した。しかし、プログラムだけではない。いずれかの計算を行なう装置は、ハードウエア化された演算装置であって、他の演算装置やＣＰＵとデータのやりとりを行うものであってもよい。
【０５５２】
【発明の効果】
以上説明したように、本発明によれば、安全性を証明可能な公開鍵暗号通信技術を提供できる。
【図面の簡単な説明】
【図１】本発明の各実施形態に共通する公開鍵暗号通信システムの概略構成図である。
【図２】図１に示す送信者側装置１００の概略構成図である。
【図３】図１に示す受信者側装置２００の概略構成図である。
【図４】送信者側装置１００および受信者側装置２００のハードウエア構成例を示す図である。
【図５】本発明の第１実施形態の動作手順を説明するための図である。
【図６】本発明の第２実施形態の動作手順を説明するための図である。
【図７】本発明の第３実施形態の動作手順を説明するための図である。
【図８】本発明の第４実施形態の動作手順を説明するための図である。
【図９】本発明の第４実施形態による公開鍵暗号通信方法と、従来技術の暗号方法(楕円曲線暗号，RSA，OAEP+RSA)との平文空間の大きさ、および、安全性の比較を表す図である
【図１０】本発明の第５実施形態の動作手順を説明するための図である。
【図１１】本発明の第６実施形態の動作手順を説明するための図である。
【図１２】本発明の第１１実施形態の動作手順を説明するための図である。
【図１３】本発明の第１２実施形態の動作手順を説明するための図である。
【図１４】本発明の第１３実施形態の動作手順を説明するための図である。
【図１５】本発明の第１４実施形態の動作手順を説明するための図である。
【図１６】本発明の第１９実施形態の動作手順を説明するための図である。
【図１７】本発明の第２０実施形態の動作手順を説明するための図である。
【図１８】本発明の第２１実施形態の動作手順を説明するための図である。
【符号の説明】
１００…送信者側装置、１０１…乱数生成部、１０２…べき乗算部、１０３…演算部、１０４…剰余演算部、１０５…記憶部、１０６…通信部、１０７…入力部、１０８…暗号化部、２００…受信者側装置、２０１…鍵生成部、２０２…べき乗算部、２０３…剰余演算部、２０４…演算部、２０５…記憶部、２０６…通信部、２０７…復号化部、３００…通信回線、４０１…ＣＰＵ、４０２…メモリ、４０３…外部記憶装置、４０４…記憶媒体、４０５…読取装置、４０６…入力装置、４０７…出力装置、４０８…通信装置、４０９…バス
【図１】
0004230162.tif 000197
【図２】
0004230162.tif 000198
【図３】
0004230162.tif 000199
【図４】
0004230162.tif 000200
【図５】
0004230162.tif 000201
【図６】
0004230162.tif 000202
【図７】
0004230162.tif 000203
【図８】
0004230162.tif 000204
【図９】
0004230162.tif 000205
【図１０】
0004230162.tif 000206
【図１１】
0004230162.tif 000207
【図１２】
0004230162.tif 000208
【図１３】
0004230162.tif 000209
【図１４】
0004230162.tif 000210
【図１５】
0004230162.tif 000211
【図１６】
0004230162.tif 000212
【図１７】
0004230162.tif 000213
【図１８】
0004230162.tif 000214