(57)【特許請求の範囲】
【請求項１】
暗号文の受信者の公開鍵を用いて暗号文を作成する送信者側装置と，前記受信者の秘密鍵を用いて前記暗号文を復号化する受信者側装置と，からなる公開鍵暗号システムであって，
前記受信者側装置は，鍵生成手段を備え，
前記鍵生成手段は，秘密鍵として，
【数１】
0003870753.tif 000031
を作成し，
公開鍵として，
【数２】
0003870753.tif 000032
(但し，Gは有限アーベル群を表わし，Gの元と{0，1}kの元の間に1対1対応があるものとする。また，k=k1+k2とする)
を作成し，
前記送信者側装置は，乱数生成手段と，暗号演算手段と，送信側通信装置と，を備え，
前記乱数生成手段は，メッセージm∈{0，1}k1に対して，乱数r∈{0，1}k2を生成し，
前記暗号演算手段は，前記乱数rと前記公開鍵とに基づき，前記メッセージmの暗号文(u，v)を，
【数３】
0003870753.tif 000033
により計算し，
前記送信側通信装置は，前記暗号文(u，v)を，該受信者側装置に送信し，
該受信者側装置は，さらに，復号演算手段と，受信側通信装置と，を備え，
前記受信側通信装置は，前記暗号文(u，v)を受信し，
前記復号演算手段は，前記暗号文(u，v)と，前記秘密鍵と，に基づき，
【数４】
0003870753.tif 000034
なる(m'，r')を計算し，
【数５】
0003870753.tif 000035
が成立するか，否かを調べ，
成立しない場合は，前記暗号文(u，v)は不正なものとみなし，成立した場合は，前記m'を，該暗号文(u，v)を復号化した結果として出力する
ことを特徴とする公開鍵暗号システム。
【請求項２】
請求項１に記載の公開鍵暗号システムにおいて，
前記受信者側装置は，前記受信側通信装置を介して，前記公開鍵(g，h，H1，H2)を前記送信者側装置に送信するか，または公開情報管理機関に登録する手段を備える
ことを特徴とする公開鍵暗号システム。
【請求項３】
暗号文の受信者の公開鍵を用いて暗号文を作成する送信者側装置と，前記受信者の秘密鍵を用いて前記暗号文を復号化する受信者側装置と，からなる公開鍵暗号システムであって，
前記受信者側装置は，鍵生成手段を備え，
前記鍵生成手段は，秘密鍵として，
【数６】
0003870753.tif 000036
を作成し，
公開鍵として，
【数７】
0003870753.tif 000037
(但し，Zpの元と{0，1}kの元の間に1対1対応があるものとする。また，k=k1+k2とする)
を作成し，
前記送信者側装置は，乱数生成手段と，暗号演算手段と，送信側通信装置と，を備え，
前記乱数生成手段は，メッセージm∈{0，1}k1に対して，乱数r∈{0，1}k2を生成し，
前記暗号演算手段は，前記乱数rと前記公開鍵とに基づき，前記メッセージmの暗号文(u，v)を，
【数８】
0003870753.tif 000038
により計算し，
前記送信側通信装置は，前記暗号文(u，v)を，該受信者側装置に送信し，
該受信者側装置は，さらに，復号演算手段と，受信側通信装置と，を備え，
前記受信側通信装置は，前記暗号文(u，v)を受信し，
前記復号演算手段は，前記暗号文(u，v)と，前記秘密鍵と，に基づき，
【数９】
0003870753.tif 000039
なる(m'，r')を計算し，
【数１０】
0003870753.tif 000040
が成立するか，否かを調べ，
成立しない場合は，前記暗号文(u，v)は不正なものとみなし，成立した場合は，前記m'を，該暗号文(u，v)を復号化した結果として出力する
ことを特徴とする公開鍵暗号システム。
【請求項４】
請求項３に記載の公開鍵暗号システムにおいて，
前記受信者側装置は，前記受信側通信装置を介して，前記公開鍵(p，g，h，H1，H2)を前記送信者側装置に送信するか，または公開情報管理機関に登録する手段を備える
ことを特徴とする公開鍵暗号システム。
【請求項５】
暗号文の受信者の公開鍵を用いて暗号文を作成する送信者側装置と，前記受信者の秘密鍵を用いて前記暗号文を復号化する受信者側装置と，からなる公開鍵暗号システムであって，
前記受信者側装置は，鍵生成手段を備え，
前記鍵生成手段は，秘密鍵として，
【数１１】
0003870753.tif 000041
を作成し，
公開鍵として，
【数１２】
0003870753.tif 000042
(但し，Gは有限アーベル群を表わし，Gの元と{0，1}kの元の間に1対1対応があるものとする。また，k=k1+k2とする)
を作成し，
前記送信者側装置は，乱数生成手段と，暗号演算手段と，送信側通信装置と，を備え，
前記乱数生成手段は，メッセージm∈{0，1}nに対して，乱数r1∈{0，1}k1，r2∈{0，1}k2を生成し，
前記暗号演算手段は，前記乱数r1，r2と前記公開鍵とに基づき，前記メッセージmの暗号文(u，v，w)を，
【数１３】
0003870753.tif 000043
により計算し，
前記送信側通信装置は，前記暗号文(u，v，w)を，該受信者側装置に送信し，
該受信者側装置は，さらに，復号演算手段と，受信側通信装置と，を備え，
前記受信側通信装置は，前記暗号文(u，v，w)を受信し，
前記復号演算手段は，前記暗号文(u，v，w)と，前記秘密鍵と，に基づき，
【数１４】
0003870753.tif 000044
なる(r'1，r'2)を計算し，
【数１５】
0003870753.tif 000045
が成立するか，否かを調べ，
成立しない場合は，前記暗号文(u，v，w)を不正なものとみなし，成立した場合は，
【数１６】
0003870753.tif 000046
なるm'を計算し，
前記m'を該暗号文(u，v，w)を復号化した結果として出力する
ことを特徴とする公開鍵暗号システム。
【請求項６】
請求項５に記載の公開鍵暗号システムにおいて，
前記受信者側装置は，前記受信側通信装置を介して，前記公開鍵(g，h，H1，H2，G1，G2)を前記送信者側装置に送信するか，または公開情報管理機関に登録する手段を備える
ことを特徴とする公開鍵暗号システム。
【請求項７】
暗号文の受信者の公開鍵を用いて暗号文を作成する送信者側装置と，前記受信者の秘密鍵を用いて前記暗号文を復号化する受信者側装置と，からなる公開鍵暗号システムであって，
前記受信者側装置は，鍵生成手段を備え，
前記鍵生成手段は，秘密鍵として，
【数１７】
0003870753.tif 000047
を作成し，
公開鍵として，
【数１８】
0003870753.tif 000048
(但し，Zpの元と{0，1}kの元の間に1対1対応があるものとする。また，k=k1+k2とする)
を作成し，
前記送信者側装置は，乱数生成手段と，暗号演算手段と，送信側通信装置と，を備え，
前記乱数生成手段は，メッセージm∈{0，1}nに対して，乱数r1∈{0，1}k1，r2∈{0，1}k2を生成し，
前記暗号演算手段は，前記乱数r1，r2と前記公開鍵とに基づき，前記メッセージｍの暗号文(u，v，w)を，
【数１９】
0003870753.tif 000049
により計算し，
前記送信側通信装置は，前記暗号文(u，v，w)を，該受信者側装置に送信し，
該受信者側装置は，さらに，復号演算手段と，受信側通信装置と，を備え，
前記受信側通信装置は，前記暗号文(u，v，w)を受信し，
前記復号演算手段は，前記暗号文(u，v，w)と，前記秘密鍵と，に基づき，
【数２０】
0003870753.tif 000050
なる(r'1，r'2)を計算し，
【数２１】
0003870753.tif 000051
が成立するか，否かを調べ，
成立しない場合は，前記暗号文(u，v，w)を不正なものとみなし，成立した場合は，
【数２２】
0003870753.tif 000052
なるm'を計算し，
前記m'を該暗号文(u，v，w)を復号化した結果として出力する
ことを特徴とする公開鍵暗号システム。
【請求項８】
請求項７に記載の公開鍵暗号システムにおいて，
前記受信者側装置は，前記受信側通信装置を介して，前記公開鍵(p，g，h，H1，H2，G1，G2)を前記送信者側装置に送信するか，または公開情報管理機関に登録する
ことを特徴とする公開鍵暗号システム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は，強化された適応的選択暗号文攻撃に対して強秘匿であることが証明可能な公開鍵暗号を用いた暗号通信方法に関する。
【０００２】
【従来の技術】
文献１「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）であることが最も安全であると考えられている。
【０００３】
IND-CCA2であることが証明可能な公開鍵暗号方法としては，文献２「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 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」，文献７「M. Bellare and P. Rogaway : Random Oracles are Practical -- A Paradigm for Designing Efficient Protocol, First ACM Conference on Computer and Communications Security, pp.62--73 (1993)」に記載されている暗号方法，等が知られている。
【０００４】
【発明が解決しようとする課題】
ランダムオラクルモデル上において適応的選択暗号文攻撃に対して強秘匿（IND-CCA2）であるとは，簡単に言うと，「多項式時間能力の攻撃者は，ターゲットとなる暗号文，対応する公開鍵，復号化オラクル，ランダムオラクルにアクセスすることが許されている環境下で，ターゲットとなる暗号文に対応するメッセージ文のいかなる情報を計算することが困難である」ことを意味する（厳密な定義については，例えば文献１参照）。
【０００５】
しかし，攻撃者に対して，ターゲットとなる暗号文，対応する公開鍵，復号化オラクル（第１のオラクル），ランダムオラクル（第2のオラクル）以外に，第３のオラクルとしてランダムオラクルに付随する情報を与えた場合には，攻撃者はメッセージ文の部分情報を計算することが可能になる場合が存在する。
【０００６】
以下，この場合について説明する。文献７には，次の公開鍵暗号方法が記載されている：メッセージ文xに対して，その暗号文は，
【０００７】
【数２３】
0003870753.tif 000002
【０００８】
により与えられる。但し，fは公開された落し戸付き一方向性置換であり，G,Hはハッシュ関数。この公開鍵暗号方法は，G,Hを理想的ランダム関数とするとき，IND-CCA2であることが同文献の中で示されている。
【０００９】
今，ハッシュ関数Gがハッシュ関数G'に対して，G=G'・fとなるように作成されていたと仮定する。但し，(f・g)(x)=f(g(x))。G'を理想的ランダム関数とすると，Gは理想的ランダムになる点に注意する。このとき，攻撃者は（第3番目のオラクルから）関数G'を手に入れることができたとすると，
【００１０】
【数２４】
0003870753.tif 000003
【００１１】
により，メッセージ文xを計算できてしまう。
【００１２】
このように，従来の定義（IND-CCA2）の範囲内では安全である公開鍵暗号であっても，（従来の定義の範囲外である）第３のオラクルから攻撃者にランダムオラクルに付随する情報を与えてしまうと，簡単に破れてしまう場合が存在する。
【００１３】
本発明は，第１のオラクル，第2のオラクルに加えて，上記の第3のオラクルからランダムオラクルに付随する情報を攻撃者に与えた場合にも，メッセージ文に関するいかなる部分情報も計算できない公開鍵暗号方法を提供する。
【００１４】
さらに、上記方法を用いた暗号通信方法，その応用装置，またはシステムを提供する。
【００１５】
【課題を解決するための手段】
本発明による公開鍵暗号方法では，暗号文から（メッセージ文のみならず）各ハッシュ関数への入力値に関する部分情報を計算することが困難となるように暗号文を作成する。これにより，攻撃者がランダムオラクルに付随するいかなる情報を第3のオラクルから得ても，ハッシュ関数への入力値に関する情報を暗号文から計算できないため，この攻撃を無効とすることが可能になる。
【００１６】
次に，メッセージ文のみならず，ハッシュ関数への入力値に関する部分情報を秘匿にするための具体的な方法について述べる。
［鍵生成]
メッセージの受信者は，
【００１７】
【数２５】
0003870753.tif 000004
【００１８】
を公開鍵とし，
【００１９】
【数２６】
0003870753.tif 000005
【００２０】
を秘密鍵とする。但し，Ｇは有限アーベル群を表わし，Ｇの元と{0,1}kの元の間に１対１対応があるものとする。また，k=k1+k2とする。
【００２１】
［暗号化]
メッセージの送信者は，メッセージｍ∈{0,1}k1に対して，乱数ｒ∈{0,1}k2を選び，
【００２２】
【数２７】
0003870753.tif 000006
【００２３】
を計算し，（ｕ，ｖ）を暗号文として，該受信者に送信する。
【００２４】
［復号化]
受信者は，自身の秘密鍵を用いて，
【００２５】
【数２８】
0003870753.tif 000007
【００２６】
なる（ｍ'，ｒ'）を計算し，さらに，
【００２７】
【数２９】
0003870753.tif 000008
【００２８】
が成立することを確認した後（確認が失敗した場合，暗号文は不正なものとみなし拒否する），ｍ'を該暗号文（ｕ，ｖ）のメッセージ文とする。
【００２９】
【発明の実施の形態】
以下，図面を用いて，本発明の実施例について説明する。
【００３０】
図１は，本発明の各実施例のシステム構成を示す図である。このシステムは，送信者側装置100と受信者側装置200から構成されている。さらに，送信者側装置100と受信者側装置200は通信回線300で接続されている。
【００３１】
図２は，図１のシステムにおける送信者側装置100の内部構成を示す。送信者側装置100は，乱数生成手段101，べき乗算手段102，演算手段103，剰余演算手段104，メモリ105，通信装置106，入力装置107，を備えている。
【００３２】
図３は，図１のシステムにおける受信者側装置200の内部構成を示す。受信者側装置200は，鍵生成手段201，べき乗算手段202，剰余演算手段203，演算手段204，メモリ205，通信装置206，復号化装置207，を備えている。
【００３３】
（実施例１）
本実施例は，メッセージの送信者であるＡが受信者であるＢに対して，送信データｍを暗号通信によって送信する場合について説明する。図４に，本実施例の概要を示す。
【００３４】
１．鍵生成処理
受信者Ｂは，予め，受信者側装置200内の鍵生成手段201を用いて，
【００３５】
【数３０】
0003870753.tif 000009
【００３６】
なる秘密鍵，
【００３７】
【数３１】
0003870753.tif 000010
【００３８】
なる公開鍵を作成する。但し，Ｇは有限アーベル群を表わし，Ｇの元と{0,1}kの元の間に１対１対応があるものとする。また，k=k1+k2とする。また，公開情報を通信回線300などを介して出力し，送信者側装置100へ送付するか，または公開する。公開する方法として，例えば第３者（公開情報管理機関）への登録など，周知の方法を用いることが可能である。その他の情報については，メモリ205に格納する。
【００３９】
２．暗復号化処理
（１）送信者Ａは，メッセージｍ∈{0,1}k1に対して，送信者側装置100内の乱数生成手段101を用いて乱数ｒ∈{0,1}k2を選び，演算手段103を用いて，
【００４０】
【数３２】
0003870753.tif 000011
【００４１】
を計算し，（ｕ，ｖ）を暗号文として通信装置106を用いて通信回線300を介して受信者Ｂの受信者側装置200に送信する。
【００４２】
（２）受信者は，上記秘密情報と受信者側装置200内の演算手段204を用いて暗号文（ｕ，ｖ）から，
【００４３】
【数３３】
0003870753.tif 000012
【００４４】
なる（ｍ'，ｒ'）を計算し，さらに，
【００４５】
【数３４】
0003870753.tif 000013
【００４６】
が成立することを確認した後，ｍ'を該暗号文（ｕ，ｖ）のメッセージ文として出力する。確認が失敗した場合，暗号文は不正なものとみなし拒否する。
【００４７】
本実施例による公開鍵暗号方法では，群G上のDiffie-Hellman決定問題の困難性を前提にして，選択暗号文攻撃に対して強秘匿（IND-CCA2）であることが証明できる。証明のアウトラインは以下の通り
本実施例による公開鍵暗号方法を破ろうとする攻撃者（適応的選択暗号文攻撃における強秘匿性の意味において。定義については，例えば，文献14「V.Shoup. : OAEP Reconsidered. Available on the e-print library (2000/060), November 2000」に記載されている）が復号化オラクルから情報を得るためには，質問である暗号文において，元の平文を知る必要がある。すなわち，復号化オラクルから攻撃者は新たな情報を得ることができない。また，文献１２「M.Bellare and P.Rogaway, : Optimal Asymmetric Encryption - How to Encrypt with RSA, Proc. of Eurocrypt'94, LNCS950, Springer Verlag, pp.92-111 (1994)」に記載の方法と同様の方法にて，本実施例の方法がIND-CPAであること容易に示せる。これより，本実施例の公開鍵暗号方法はIND-CCA2であることが証明できる。
【００４８】
さらに，乱数rをメッセージ文とみなすと（この場合，メッセージ文mは秘密），同様の方法により，群G上のDiffie-Hellman決定問題の困難性を前提にして，選択平文攻撃に対して強秘匿（IND-CPA）であることが証明できる。すなわち，暗号文から乱数rに関する部分情報を漏らしていないことが証明できる。
【００４９】
以上のことから，攻撃者は仮に第３のオラクルからハッシュ関数に付随する情報を得ても，暗号文からメッセージに関するいかなる部分情報を計算することが困難であることが示された。
【００５０】
（実施例２）
本実施例は，実施例１において，有限アーベル群Gを体から決定される乗法群として与えた場合について述べる。
【００５１】
１．鍵生成処理
受信者Ｂは，予め，受信者側装置200内の鍵生成手段201を用いて，
【００５２】
【数３５】
0003870753.tif 000014
【００５３】
なる秘密鍵，
【００５４】
【数３６】
0003870753.tif 000015
【００５５】
なる公開鍵を作成する。但し，Z*pの元と{0,1}kの元の間に１対１対応があるものとする。また，k=k1+k2とする。また，公開情報を通信回線300などを介して出力し，送信者側装置100へ送付するか，または公開する。公開する方法として，例えば第３者（公開情報管理機関）への登録など，周知の方法を用いることが可能である。その他の情報については，メモリ205に格納する。
【００５６】
２．暗復号化処理
（１）送信者Ａは，メッセージｍ∈{0,1}k1に対して，送信者側装置100内の乱数生成手段101を用いて乱数ｒ∈{0,1}k2を選び，演算手段103を用いて，
【００５７】
【数３７】
0003870753.tif 000016
【００５８】
を計算し，（ｕ，ｖ）を暗号文として通信装置106を用いて通信回線300を介して受信者Ｂの受信者側装置200に送信する。
【００５９】
（２）受信者は，上記秘密情報と受信者側装置200内の演算手段204を用いて暗号文（ｕ，ｖ）から，
【００６０】
【数３８】
0003870753.tif 000017
【００６１】
なる（ｍ'，ｒ'）を計算し，さらに，
【００６２】
【数３９】
0003870753.tif 000018
【００６３】
が成立することを確認した後，ｍ'を該暗号文（ｕ，ｖ）のメッセージ文として出力する。確認が失敗した場合，暗号文は不正なものとみなし拒否する。
【００６４】
本実施例による公開鍵暗号方法では，実施例１の場合と同様の方法により，群Z*p上のDiffie-Hellman決定問題の困難性を前提にして，選択暗号文攻撃に対して強秘匿（IND-CCA2）であることが証明できる。さらに，乱数rをメッセージ文とみなすと（この場合，メッセージ文mは秘密），同様の方法により，群Z*p上のDiffie-Hellman決定問題の困難性を前提にして，選択平文攻撃に対して強秘匿（IND-CPA）であることが証明できる。すなわち，暗号文から乱数rに関する部分情報を漏らしていないことが証明できる。
【００６５】
以上のことから，攻撃者は仮に第３のオラクルからハッシュ関数に付随する情報を得ても，暗号文からメッセージに関するいかなる部分情報を計算することが困難であることが示された。
【００６６】
（実施例３）
本実施例は，実施例１の変形例であり，実施例１の公開鍵暗号方法よりも平文空間（メッセージの長さ）を大きく取れるメリットを有する。図５に，本実施例の概要を示す。
【００６７】
１．鍵生成処理
受信者Ｂは，予め，受信者側装置200内の鍵生成手段201を用いて，
【００６８】
【数４０】
0003870753.tif 000019
【００６９】
なる秘密鍵，
【００７０】
【数４１】
0003870753.tif 000020
【００７１】
なる公開鍵を作成する。但し，Ｇは有限アーベル群を表わし，Ｇの元と{0,1}kの元の間に１対１対応があるものとする。また，k=k1+k2とする。また，公開情報を通信回線300などを介して出力し，送信者側装置100へ送付するか，または公開する。公開する方法として，例えば第３者（公開情報管理機関）への登録など，周知の方法を用いることが可能である。その他の情報については，メモリ205に格納する。
【００７２】
２．暗復号化処理
（１）送信者Ａは，メッセージｍ∈{0,1}nに対して，送信者側装置100内の乱数生成手段101を用いて乱数ｒ1∈{0,1}k1，ｒ2∈{0,1}k2を選び，演算手段103を用いて，
【００７３】
【数４２】
0003870753.tif 000021
【００７４】
を計算し，（ｕ，ｖ，ｗ）を暗号文として通信装置106を用いて通信回線300を介して受信者Ｂの受信者側装置200に送信する。
【００７５】
（２）受信者は，上記秘密情報と受信者側装置200内の演算手段204を用いて暗号文（ｕ，ｖ，ｗ）から，
【００７６】
【数４３】
0003870753.tif 000022
【００７７】
なる（r'1，ｒ'2）を計算し，さらに，
【００７８】
【数４４】
0003870753.tif 000023
【００７９】
が成立することを確認した後，
【００８０】
【数４５】
0003870753.tif 000024
【００８１】
により，（ｕ，ｖ，ｗ）のメッセージ文を復号化する。確認が失敗した場合は，暗号文は不正なものとみなし拒否する。
【００８２】
本実施例による公開鍵暗号方法では，メッセージの長さ（ビット長）であるｎは任意に選ぶことが出来るため，実施例１の方法に比べて長いメッセージ文を暗号化することが可能である。公開鍵暗号の利用目的の中では，共通鍵暗号のデータ暗号化鍵の配送に利用することが最も多い。しかし，単にデータ暗号化鍵のみを暗号化するのではなく，ユーザのＩＤ情報等の付加情報を加えて暗号化することが少なくなく，このような場合において本実施例の公開鍵暗号方法は有効である。
【００８３】
（実施例４）
本実施例は，実施例３において，有限アーベル群Gを体から決定される乗法群として与えた場合について述べる。
【００８４】
１．鍵生成処理
受信者Ｂは，予め，受信者側装置200内の鍵生成手段201を用いて，
【００８５】
【数４６】
0003870753.tif 000025
【００８６】
なる秘密鍵，
【００８７】
【数４７】
0003870753.tif 000026
【００８８】
なる公開鍵を作成する。但し，Z*pの元と{0,1}kの元の間に１対１対応があるものとする。また，k=k1+k2とする。また，公開情報を通信回線300などを介して出力し，送信者側装置100へ送付するか，または公開する。公開する方法として，例えば第３者（公開情報管理機関）への登録など，周知の方法を用いることが可能である。その他の情報については，メモリ205に格納する。
【００８９】
２．暗復号化処理
（１）送信者Ａは，メッセージｍ∈{0,1}nに対して，送信者側装置100内の乱数生成手段101を用いて乱数ｒ1∈{0,1}k1，ｒ2∈{0,1}k2を選び，演算手段103を用いて，
【００９０】
【数４８】
0003870753.tif 000027
【００９１】
を計算し，（ｕ，ｖ，ｗ）を暗号文として通信装置106を用いて通信回線300を介して受信者Ｂの受信者側装置200に送信する。
【００９２】
（２）受信者は，上記秘密情報と受信者側装置200内の演算手段204を用いて暗号文（ｕ，ｖ，ｗ）から，
【００９３】
【数４９】
0003870753.tif 000028
【００９４】
なる（r'1，ｒ'2）を計算し，さらに，
【００９５】
【数５０】
0003870753.tif 000029
【００９６】
が成立することを確認した後，
【００９７】
【数５１】
0003870753.tif 000030
【００９８】
により，（ｕ，ｖ，ｗ）のメッセージ文を復号化する。確認が失敗した場合は，暗号文は不正なものとみなし拒否する。
【００９９】
以上，実施例では，送信者と受信者が各々の装置を利用して暗号通信を行うという一般形で述べたが，具体的には様々なシステムに適用される。
【０１００】
例えば，電子ショッピングシステムでは，送信者はユーザであり，送信者側装置はパソコンなどの計算機であり，受信者は小売店，受信者側装置はパソコンなどの計算機となる。このとき，ユーザの商品等の注文書は共通鍵暗号で暗号化されることが多く，その際の暗号化鍵を本実施例による方法により暗号化されて小売店側装置に送信される。
【０１０１】
また，電子メールシステムでは，各々の装置はパソコンなどの計算機であり，送信者のメッセージは共通鍵暗号で暗号化されることが多く，その際の暗号化鍵を本実施例による方法により暗号化されて受信者の計算機に送信される。
【０１０２】
その他にも，従来の公開鍵暗号が使われている様々なシステムに適用することが可能である。
【０１０３】
なお，本実施例における各計算は，CPUがメモリ内の各プログラムを実行することにより行われるものとして説明したが，プログラムだけではなく，いずれかがハードウエア化された演算装置であって，他の演算装置や，CPUと，データのやりとりを行うものであっても良い。
【０１０４】
【発明の効果】
本発明によれば，安全な公開鍵暗号方法を提供できる。
【０１０５】
【図面の簡単な説明】
【図１】本発明の実施例のシステム構成を示す図である。
【図２】本発明の実施例における送信者側装置の内部構成を示す図である。
【図３】本発明の実施例における受信者側装置の内部構成を示す図である。
【図４】本発明に実施例１の概要を示す図である。
【図５】本発明の実施例３の概要を示す図である。
【符号の説明】
１００…送信者側装置，１０１…送信者側装置１００内の乱数生成手段，１０２…送信者側装置１００内のべき乗算手段，１０３…送信者側装置１００内の演算手段，１０４…送信者側装置１００内の剰余演算手段，１０５…送信者側装置１００内のメモリ，１０６…送信者側装置１００内の通信装置，１０７…送信者側装置１００内の入力装置，１０８…送信者側装置１００内の暗号化装置，２００…受信者側装置，２０１…受信者側装置２００内の鍵生成手段，２０２…受信者側装置２００内のべき乗算手段，２０３…受信者側装置２００内の剰余演算手段，２０４…受信者側装置２００内の演算手段，２０５…受信者側装置２００内のメモリ，２０６…受信者側装置２００内の通信装置，２０７…受信者側装置２００内の復号化装置，３００…通信回線。
【図１】
0003870753.tif 000053
【図２】
0003870753.tif 000054
【図３】
0003870753.tif 000055
【図４】
0003870753.tif 000056
【図５】
0003870753.tif 000057