(57)【特許請求の範囲】
【請求項１】
通信チャネル上でメッセージを交換するのに適した、通信インターフェースと、データ処理手段と、記憶手段とを有する装置による、公開鍵および秘密鍵の発生方法であって、秘密鍵が前記装置のプログラムメモリの保護領域内に保存され、公開鍵が一般に流布できるように、公開鍵が前記装置のアクセス保護のないメモリ領域内に保存され、前記装置のデータ処理手段が以下のデータ処理、すなわち、
・相異なる隣り合った２つの素数ｐとｑの選択
・積ｐ・ｑに等しい数ｎの計算
・数（ｐ−１）と（ｑ−１）の最小公倍数の計算：λ（ｎ）＝ＰＰＣＭ（ｐ−１，ｑ−１）
・次の２つの条件を満たす、０≦ｇ＜ｎ２である数ｇの決定
ａ）ｇはｎ２を法とする逆数になれる
ｂ）ｏｒｄ（ｇ，ｎ２）＝０ ｍｏｄ ｎ
を実行し、前記装置の公開鍵は、前記データ処理によって導き出されたパラメータｎとｇから形成され、その秘密鍵は前記データ処理によって導き出されたパラメータｐ、ｑ、及びλ（ｎ）から、あるいはパラメータｐとｑから形成されることを特徴とする、公開鍵および秘密鍵の発生方法。
【請求項２】
前記データ処理における数ｇの決定処理において、ｇ＝２が前記条件ａ）及びｂ）を満たすならばｇ＝２と決定することを特徴とする、請求項１に記載の公開鍵および秘密鍵の発生方法。
【請求項３】
請求項１または２に記載の発生方法によって発生した公開鍵および秘密鍵による暗号通信システムであって、該システムが通信チャネルと、第一および第二の通信装置（Ａ，Ｂ）とを有し、それぞれの通信装置が通信インターフェースと、データ処理手段と、記憶手段とを有し、第一の通信装置（Ａ）のデータ処理手段が、その記憶手段に記憶された数ｍ、０≦ｍ＜ｎ（数ｍはメッセージを表している）に対して次の過程からなる暗号化処理、すなわち、
・パラメータｎとｇに第二の通信装置（Ｂ）の公開鍵の値（ｎＢ，ｇＢ）を割り当てるための、第二の通信装置の公開鍵のパラメータ（ｎＢ，ｇＢ）の取得
・暗号文ｃ＝ｇｍ ｍｏｄ ｎ２の計算
を実行し、該暗号化処理によって計算された暗号文ｃが、第二の通信装置に向けて通信チャネルを介して伝送されることを特徴とする、暗号通信システム。
【請求項４】
第一の通信装置がさらにランダム整数ｒの発生器を備え、前記第一の通信装置のデータ処理手段が、
・前記発生器からランダム整数ｒを抽出し、
・前記暗号化処理における暗号文ｃ＝ｇｍ ｍｏｄ ｎ２の計算の代わりに、次の計算を実行することによって暗号文ｃを計算する：ｃ＝ｇｍ＋ｎｒ ｍｏｄ（ｎ２）
ことを特徴とする、請求項３に記載の暗号通信システム。
【請求項５】
第一の通信装置がさらにランダム整数ｒの発生器を備え、前記第一の通信装置のデータ処理手段が、
・前記発生器からランダム整数ｒを抽出し、
・前記暗号化処理における暗号文ｃ＝ｇｍ ｍｏｄ ｎ２の計算の代わりに、次の計算を実行することによって暗号文ｃを計算する：ｃ＝ｇｍｒｎ ｍｏｄ（ｎ２）
ことを特徴とする、請求項３に記載の暗号通信システム。
【請求項６】
第二の通信装置のデータ処理手段が、前記暗号文ｃを復号化するための次の計算からなる復号化処理を実行することを特徴とする、請求項５に記載の暗号通信システム。
ｍ＝ｌｏｇｎ（ｃλ（ｎ）  ｍｏｄ  ｎ２）・ｌｏｇｎ（ｇλ（ｎ）  ｍｏｄ  ｎ２）−１  ｍｏｄ  ｎ
ここで、（ｘ＝１ ｍｏｄ  ｎ）を満たす任意の整数ｘに対し、
ｌｏｇｎ（ｘ）＝（ｘ−１）／ｎである。
【請求項７】
第二の通信装置のデータ処理手段が、次の量αｎ，ｇを予め計算し、それをプログラムメモリの保護領域内に保存することを特徴とする、請求項６に記載の暗号通信システム。
αｎ，ｇ＝ｌｏｇｎ（ｇλ（ｎ）  ｍｏｄ  ｎ２）−１  ｍｏｄ  ｎ
【請求項８】
前記復号化処理の代わりに、第二の通信装置のデータ処理手段が中国剰余定理ＴＲＣを用いて下記の計算過程からなる復号化処理を実行することを特徴とする、請求項６に記載の暗号通信システム。
ｍｐ＝ｌｏｇｐ（ｃｐ−１ｍｏｄ  ｐ２）・ｌｏｇｐ（ｇｐ−１  ｍｏｄ  ｐ２）−１  ｍｏｄ  ｐ
ｍｑ＝ｌｏｇｑ（ｃｑ−１ｍｏｄ  ｑ２）・ｌｏｇｑ（ｇｑ−１  ｍｏｄ  ｑ２）−１  ｍｏｄ  ｑ
ｍ＝ＴＲＣ（ｍｐ，ｍｑ，ｐ，ｑ）
ここで、（ｘ＝１ ｍｏｄ  ｉ）を満たす任意の整数ｘに対し、ｌｏｇｐおよびｌｏｇｑは次のようなものである。
ｌｏｇｉ（ｘ）＝（ｘ−１）／ｉ
【請求項９】
第二の通信装置のデータ処理手段が、次の量αｐ，ｇおよびαｑ，ｇを予め計算し、それらをプログラムメモリの保護領域内に保存することを特徴とする、請求項８に記載の暗号通信システム。
αｐ，ｇ＝ｌｏｇｐ（ｇｐ−１  ｍｏｄ  ｐ２）−１  ｍｏｄ  ｐ
αｑ，ｇ＝ｌｏｇｑ（ｇｑ−１  ｍｏｄ  ｑ２）−１  ｍｏｄ  ｑ
【請求項１０】
請求項１または２に記載の発生方法によって発生した公開鍵および秘密鍵による暗号通信システムであって、該システムが通信チャネルと、第一および第二の通信装置（Ａ，Ｂ）とを有し、それぞれの通信装置が通信インターフェースと、データ処理手段と、記憶手段とを有し、第一の通信装置（Ａ）のデータ処理手段が、その記憶手段に記憶された数ｍ、０≦ｍ＜ｎ２（数ｍはメッセージを表している）に対して次の過程からなる暗号化処理、すなわち、
・パラメータｎとｇに第二の通信装置の公開鍵の値（ｎＢ，ｇＢ）を割り当てるための、第二の通信装置（Ｂ）の公開鍵のパラメータＫＢ＝（ｎＢ，ｇＢ）の取得
・下記の計算１から３の実行
１．  ｍ１＝ｍ  ｍｏｄ  ｎ
２．  ｍ２＝（ｍ−ｍ１）／ｎ
３．  ｃ＝ｇｍ１ｍ２ｎ  ｍｏｄ  ｎ２
を実行し、該暗号化処理によって計算された暗号文ｃが通信チャネルを介して第二の通信装置に向けて伝送されることを特徴とする、暗号通信システム。
【請求項１１】
第二の通信装置（Ｂ）が暗号文ｃを受信し、第二の通信装置のデータ処理手段が次の計算過程からなる復号化処理を実行することを特徴とする、請求項１０に記載の暗号通信システム。
１．  ｍ１＝ｌｏｇｎ（ｃλ（ｎ）  ｍｏｄ  ｎ２）・ｌｏｇｎ（ｇλ（ｎ）ｍｏｄ  ｎ２）−１  ｍｏｄ  ｎ
２．  ｗ＝ｃｇ−ｍ１  ｍｏｄ  ｎ
３．  ｍ２＝ｗ１／ｎ  ｍｏｄ  λ（ｎ）  ｍｏｄ  ｎ
４．  ｍ＝ｍ１＋ｎｍ２
【請求項１２】
第二の通信装置のデータ処理手段が、次の量αｎ，ｇおよびγｎを予め計算し、それらをプログラムメモリの保護領域内に保存することを特徴とする、請求項１１に記載の暗号通信システム。
αｎ，ｇ＝ｌｏｇｎ（ｇλ（ｎ）  ｍｏｄ  ｎ２）−１  ｍｏｄ  ｎ
γｎ＝１／ｎ  ｍｏｄ  λ（ｎ）
【請求項１３】
前記復号化処理の代わりに、第二の通信装置のデータ処理手段が中国剰余定理を用いて下記の計算過程からなる復号化処理を実行することを特徴とする、請求項１１に記載の暗号通信システム。
１．  ｍ１，ｐ＝ｌｏｇｐ（ｃｐ−１  ｍｏｄ  ｐ２）・ｌｏｇｐ（ｇｐ−１  ｍｏｄ  ｐ２）−１  ｍｏｄ  ｐ
２．  ｗｐ＝ｃｇ−ｍ１，ｐ  ｍｏｄ  ｐ
３．  ｍ２，ｐ＝ｗｐ１／ｑ  ｍｏｄ  ｐ−１  ｍｏｄ  ｐ
４．  ｍ１，ｑ＝ｌｏｇｑ（ｃｑ−１  ｍｏｄ  ｑ２）・ｌｏｇｑ（ｇｑ−１  ｍｏｄ  ｑ２）−１  ｍｏｄ  ｑ
５．  ｗｑ＝ｃｇ−ｍ１，ｑ  ｍｏｄ  ｑ
６．  ｍ２，ｑ＝ｗｑ１／ｐ  ｍｏｄ  ｑ−１  ｍｏｄ  ｑ
７．  ｍ１＝ＴＲＣ（ｍ１，ｐ，ｍ２，ｐ，ｐ，ｑ）
８．  ｍ２＝ＴＲＣ（ｍ１，ｑ，ｍ２，ｑ，ｐ，ｑ）
９．  ｍ＝ｍ１＋ｐｑｍ２
ここで、（ｘ＝１ ｍｏｄ  ｉ）を満たす任意の整数ｘに対し、ｌｏｇｐおよびｌｏｇｑは次のようなものである。
ｌｏｇｉ（ｘ）＝（ｘ−１）  ／  ｉ
【請求項１４】
第二の通信装置のデータ処理手段が、次の量αｐ，ｇ、αｑ，ｇ、γｐおよびγｑを予め計算し、それらをプログラムメモリの保護領域内に保存することを特徴とする、請求項１３に記載の暗号通信システム。
αｐ，ｇ＝ｌｏｇｐ（ｇｐ−１  ｍｏｄ  ｐ２）−１  ｍｏｄ  ｐ
αｑ，ｇ＝ｌｏｇｑ（ｇｑ−１  ｍｏｄ  ｑ２）−１  ｍｏｄ  ｑ
γｐ＝１／ｑ  ｍｏｄ  ｐ−１
γｑ＝１／ｐ  ｍｏｄ  ｑ−１
【請求項１５】
前記復号化処理がメッセージｍの署名ｓを計算するために使用され、前記暗号化処理が前記署名を検証するために使用されることを特徴とする、請求項１１から１４のいずれか一つに記載の暗号通信システム。
【請求項１６】
通信チャネル上でメッセージを交換するのに適した、通信インターフェースと、データ処理手段と、記憶手段とを有する装置による、公開鍵および秘密鍵の発生方法であって、秘密鍵が前記装置のプログラムメモリの保護領域内に保存され、公開鍵が一般に流布できるように、公開鍵が前記装置のアクセス保護のないメモリ領域内に保存され、前記装置のデータ処理手段が以下のデータ処理、すなわち、
・整数ｕと、ｕが（ｐ−１）を整除し且つ（ｑ−１）を整除するような相異なる隣り合った２つの素数ｐとｑの選択、
・積ｐ・ｑに等しい数ｎの計算、
・数（ｐ−１）と（ｑ−１）の最小公倍数の計算：λ（ｎ）＝ＰＰＣＭ（ｐ−１，ｑ−１）、
・次の２つの条件を満たす、０≦ｈ＜ｎ２である数ｈの決定、
ａ）ｈはｎ２を法とする逆数になれる
ｂ）ｏｒｄ（ｈ，ｎ２）＝０ ｍｏｄ ｎ
・数ｇ＝ｈλ（ｎ）／ｕ ｍｏｄ  ｎ２  の計算、
を実行し、前記装置の公開鍵は、前記データ処理によって導き出されたパラメータｎとｇから形成され、その秘密鍵は前記データ処理によって導き出されたパラメータｐ、ｑ、及びｕから形成されることを特徴とする、公開鍵および秘密鍵の発生方法。
【請求項１７】
前記データ処理における数ｈの決定処理において、ｈ＝２が前記条件ａ）及びｂ）を満たすならばｈ＝２と決定することを特徴とする、請求項１６に記載の公開鍵および秘密鍵の発生方法。
【請求項１８】
請求項１６または１７に記載の発生方法によって発生した公開鍵および秘密鍵による暗号通信システムであって、該システムが通信チャネルと、第一および第二の通信装置（Ａ，Ｂ）とを有し、それぞれの通信装置が通信インターフェースと、データ処理手段と、記憶手段とを有し、第一の通信装置（Ａ）のデータ処理手段が、その記憶手段に記憶された数ｍ、０≦ｍ＜ｎ（数ｍはメッセージを表している）に対して次の過程からなる暗号化処理、すなわち、
・パラメータｎとｇに第二の通信装置（Ｂ）の公開鍵の値（ｎＢ，ｇＢ）を割り当てるための、第二の通信装置（Ｂ）の公開鍵のパラメータ（ｎＢ，ｇＢ）の取得
・暗号文ｃ＝ｇｍ ｍｏｄ ｎ２の計算
を実行し、該暗号化処理によって計算された暗号文ｃが、第二の通信装置に向けて通信チャネルを介して伝送されることを特徴とする、暗号通信システム。
【請求項１９】
第一の通信装置がさらにランダム整数ｒの発生器を備え、前記第一の通信装置のデータ処理手段が、
・前記発生器からｕと同じ位数のランダム整数ｒを抽出し、
・前記暗号化処理における暗号文ｃ＝ｇｍ ｍｏｄ ｎ２の計算の代わりに、次の計算を実行することによって暗号文ｃを計算する：ｃ＝ｇｍ＋ｎｒ  ｍｏｄ（ｎ２）
ことを特徴とする、請求項１８に記載の暗号通信システム。
【請求項２０】
第二の通信装置のデータ処理手段が、次の計算からなる前記受信暗号文ｃの復号化処理を実行することを特徴とする、請求項１８または１９に記載の暗号通信システム。
ｍ＝ｌｏｇｎ（ｃｕ  ｍｏｄ  ｎ２）・ｌｏｇｎ（ｇｕ  ｍｏｄ  ｎ２）−１  ｍｏｄ  ｎ
【請求項２１】
第二の通信装置のデータ処理手段が、次の量βｎ，ｇを予め計算し、それをプログラムメモリの保護領域内に保存することを特徴とする、請求項２０に記載の暗号通信システム。
βｎ，ｇ＝ｌｏｇｎ（ｇｕ  ｍｏｄ  ｎ２）−１  ｍｏｄ  ｎ
【請求項２２】
前記復号化処理の代わりに、第二の通信装置のデータ処理手段が中国剰余定理を用いて下記の計算過程からなる復号化処理を実行することを特徴とする、請求項２０に記載の暗号通信システム。
１．  ｍｐ＝ｌｏｇｐ（ｃｕ  ｍｏｄ  ｐ２）・ｌｏｇｐ（ｇｕ  ｍｏｄ  ｐ２）−１  ｍｏｄ  ｐ
２．  ｍｑ＝ｌｏｇｑ（ｃｕ  ｍｏｄ  ｑ２）・ｌｏｇｑ（ｇｕ  ｍｏｄ  ｑ２）−１  ｍｏｄ  ｑ
３．  ｍ＝ＴＲＣ（ｍｐ，ｍｑ，ｐ，ｑ）
ここで、（ｘ＝１ ｍｏｄ  ｉ）を満たす任意の整数ｘに対し、ｌｏｇｐおよびｌｏｇｑは次のようなものである。
ｌｏｇｉ（ｘ）＝（ｘ−１）／  ｉ
【請求項２３】
第二の通信装置のデータ処理手段が、次の量βｐ，ｇおよびβｑ，ｇを予め計算し、それらをプログラムメモリの保護領域内に保存することを特徴とする、請求項２２に記載の暗号通信システム。
βｐ，ｇ＝ｌｏｇｐ（ｇｕ  ｍｏｄ  ｐ２）−１  ｍｏｄ  ｐ
βｑ，ｇ＝ｌｏｇｑ（ｇｕ  ｍｏｄ  ｑ２）−１  ｍｏｄ  ｑ
【発明の詳細な説明】
【０００１】
本発明は、公開鍵と秘密鍵による暗号化方法に関するものである。全ての用途分野、即ち任意のチャネル上での伝送メッセージの機密性を保証する必要がある分野、および／またはメッセージを交換する装置を確実に識別する必要がある分野で利用可能である。
【０００２】
２つの装置ＡとＢの間の任意の通信チャネル上で伝送されるメッセージの機密性は、伝送情報を暗号化し、受信側以外の人が情報を読めないようにすることによって得られる。装置の確実な識別は、メッセージのデジタル署名の計算に基づいている。
【０００３】
実際には、２つのタイプの暗号化方法が利用可能であり、一つは秘密鍵式の対称と呼ばれるもので、その周知の例はＤＥＳであり、もう一つは一対の公開鍵および秘密鍵を用いる非対称と呼ばれるものであり、ＤｉｆｆｉｅとＨｅｌｌｍａｎ著の"New directions in Cryptography" IEEE Transactions on Information Theory, nov. 1976の”Public_key cryptosystem”に記載されている。非対称法の周知の例にはＲＳＡがあり、名前はその発明者に由来する（Ｒｏｎａｌｄ  Ｒｉｖｅｓｔ、Ａｄｉ ＳｈａｍｉｒとＬｅｏｎａｒｄ Ａｄｌｅｍａｎ）。このＲＳＡ法は、米国特許第４，４０５，８２９号に記載されている。
【０００４】
本発明では、特に非対称暗号化方法に注目する。
【０００５】
非対称暗号化方法による暗号化方法は、主として、メッセージを受信側Ｂに秘密に送信することを望む発信側Ａが、例えばアドレス帳の中から受信側Ｂの公開鍵ＫBを調べ、伝送されるメッセージｍに暗号化方法Ｅを適用し、結果としての暗号文ｃ：ｃ＝ＥKB（ｍ）を受信側Ｂに送信することから成る。
【０００６】
この方法は主として、受信側Ｂが暗号文ｃを受信し、元のメッセージｍを得るために、復号化方法Ｄにおける、受信側だけが知るはずの秘密鍵Ｋ’ｂを暗号文ｃに適用することで暗号文を復号化する：ｍ＝ＤK'B（ｃ）。
【０００７】
この方法によれば、誰でもが暗号化されたメッセージを受信側Ｂに送信することができるが、受信側だけがそれを復号化することができる。
【０００８】
通常、署名の発生／検証には、非対称暗号化方法が使用される。この状況において、自己の身元の証明を望む使用者は、自分だけが知っている秘密鍵を利用して、メッセージｍのデジタル署名ｓを生成し、署名を受信装置に伝送する。受信装置は、使用者の公開鍵を用いて署名の検証を行う。したがって、全ての装置は、この使用者の公開鍵を調べ、かつ検証アルゴリズムにそれを適用して、使用者の署名を検証する能力を有する。しかし、当該使用者だけが、自己の秘密鍵を用いて正しい署名を発生する能力を有する。この方法は、例えば、アクセス制御または銀行取引のシステムに多く使用されている。それは一般的に、伝送前に署名を暗号化する暗号化方法の利用と組み合わされている。
【０００９】
このデジタル署名の発生／検証では、実際には、米国標準技術協会（US National Institute of Standards and Technology）が提案した米国標準に対応するＤＳＡ（Digital Signature Algorithm）などの、この用途専用の非対称暗号化方法が利用できる。さらに暗号化にも署名発生にも利用できる特性を有するＲＳＡを用いることができる。
【００１０】
本発明では、メッセージの暗号化とデジタル署名の発生に利用できる暗号化方法に注目する。従来技術において、実施のための変型が多数存在するＲＳＡだけが、この二重の機能を提供している。
【００１１】
ＲＳＡは所与の装置について公開鍵Ｋと秘密鍵Ｋ’の発生過程から成り、その過程は以下の通りである：
−相異なる２つの大きな素数ｐとｑを選択する。
−それらの積ｎ＝ｐ・ｑを計算する。
−（ｐ−１）と（ｑ−１）の最小公倍数と互いに素な数ｅを選択する。実際には、ｅは３に等しく取ることが多い。
【００１２】
このとき、公開鍵Ｋはパラメータ対（ｎ，ｅ）によって形成され、秘密鍵Ｋ’はパラメータ対（ｐ，ｑ）によって形成される。
【００１３】
大きな位数のｐとｑを選択すれば、それらの積ｎも大きな位数になる。したがって、ｎは因数分解がきわめて困難となる：ｎが分かっても、秘密鍵Ｋ’＝（ｐ，ｑ）を見つけることができないのは確実である。
【００１４】
メッセージＭを表す数ｍ、０≦ｍ＜ｎの暗号化方法は、公開鍵Ｋ＝（ｎ，ｅ）を用いて次の計算をすることから成る：
ｃ＝ＥB（ｍ）＝  ｍe ｍｏｄ ｎ
【００１５】
一方、復号化方法は、秘密にされている秘密鍵Ｋ’＝（ｐ，ｑ）を用いて次の逆計算をすることから成る：
ｍ＝ｃdｍｏｄ（ｎ）
【００１６】
ここで
ｄ＝  １／ｅ  ｍｏｄ  (ｐ−１)(ｑ−１)
【００１７】
先に見たごとく、ＲＳＡは署名の検証に用いることができるという特性がある。使用者Ａによる署名発生に対応する方法は、メッセージを表す数ｍの署名ｓを生成するための秘密鍵を用いた復号化方法を利用することから成る。したがって、ｓ＝ｍd ｍｏｄ  ｎ。
【００１８】
この署名ｓは受信側Ｂに伝送される。受信側は、ｍ（例えば、Ａがｓとｍを伝送）を知っており、逆演算を実施して、すなわち発信者Ａの公開鍵で暗号化方法を用いて署名を検証する。すなわち、ｖ＝ｓe ｍｏｄ  ｎを計算して、ｖ＝ｍを検証する。
【００１９】
一般的に、かかる署名検証法の機密性を向上させるためには、署名の計算前に、数ｍに対して、ビットの置換および／または圧縮から成ることができるハッシュ関数を前もって適用する。
【００２０】
暗号化する、あるいは署名するメッセージＭについて言うとき、それはもちろん、先行するデジタル符号化の結果であるデジタルメッセージのことである。それらは実際には、バイナリ・サイズ（ビット数）が可変のビット列である。
【００２１】
ところで、ＲＳＡなどの暗号化方法は、０からｎ−１の間の任意の数を、公開鍵（ｎ，ｅ）で暗号化することを可能にするものである。したがって、任意のサイズのメッセージＭにそれを適用するためには、実際にこのメッセージを、条件０≦ｍ＜ｎをそれぞれ満たす一連の数ｍに分割する必要がある。次に、暗号化方法をこれらの数のそれぞれに適用する。つづいて、メッセージＭを表す数ｍへの暗号化方法の適用に着目する。ｍはＭに等しいことも、その一部にすぎないこともある。したがって、以下においてはメッセージまたはメッセージを表す数を区別なくｍで示す。
【００２２】
本発明の一つの目的は、ＲＳＡに基づくものとは異なる非対称暗号化方法である。
【００２３】
本発明の一つの目的は、メッセージの暗号化にも、署名発生にも適用できる、他の特性に基づく方法である。
【００２４】
本発明の一つの目的は、特定の構成において、処理時間をより短くすることができる暗号化方法である。
【００２５】
特徴づけられたように、本発明は、請求項１に記載の暗号化方法に関するものである。
【００２６】
本発明は、付属の図面を参照して、説明のためになされた本発明を一切限定しない下記の説明を読むことによって、よりよく理解できるだろう。
−図１は、非対称型暗号通信システムの機能図である。
−図２は、本発明による暗号通信システムに使用された通信装置の機能図である。
−図３は、本発明による暗号化方法を用いるメッセージの暗号化／復号化におけるセッションの流れ図である。
−図４は、本発明による暗号化方法を用いる署名の発生／検証セッションの流れ図である。
【００２７】
本発明をよりよく理解するために、いくつかの数学的前置きをする必要がある。
【００２８】
説明において、以下の数学的記号表記を使用する。
【００２９】
（１）ａが正負の整数、ｂが正の整数であるとき、ａ  ｍｏｄ ｂ（ａ  モジュロ  ｂ）は、ｂを法とするａの剰余を示し、ｂ未満の一意の整数となり、ｂは（ａ−ａ ｍｏｄ ｂ）を整除する。
【００３０】
（２）（Ｚ／ｂＺ）は、ｂを法とする剰余の集合を示し、加算剰余についてのグループを形成する。
【００３１】
（３）（Ｚ／ｂＺ）*は、ｂを法とする逆数の集合を示し、乗算剰余についてのグループを形成する。
【００３２】
（４）（Ｚ／ｂＺ）* の要素ａの次数は、ａord(a,b)＝１ ｍｏｄ ｂとなるような最小自然数ｏｒｄ（ａ，ｂ）である。
【００３３】
（５）ＰＰＣＭ（ａ，ｂ）は、ａとｂの最小公倍数を指す。
【００３４】
（６）ＰＧＣＤ（ａ，ｂ）は、ａとｂの最大公約数を指す。
【００３５】
（７）λ（ａ）は、ａのオイラー表示を指す。
もし、ａ＝ｐ・ｑならば、λ（ａ）＝ＰＰＣＭ（ｐ−１，ｑ−１）
【００３６】
（８）下記の剰余等式系の、周知の中国剰余定理を実施して得られた一意の解を、ｘ＝ＴＲＣ（ａ1,・・・ａk，ｂ1,・・・ｂk）で表す。
ｘ＝ａ1 ｍｏｄ  ｂ1
ｘ＝ａ2 ｍｏｄ  ｂ2
・・・
ｘ＝ａk ｍｏｄ  ｂk
ここで、整数ａiとｂiは与えられ、また、ｉ≠ｊである∀ｉ，ｊについて、ＰＧＣＤ（ｂi，ｂj）＝１である。
【００３７】
（９）数ａのバイナリ・サイズは、ａが書き込まれているビット数であることに再度触れておく。
【００３８】
数ｎを、任意の大きさの整数とする。集合Ｕｎ＝｛ｘ＜ｎ2 ／ｘ＝１ ｍｏｄ ｎ｝は、（Ｚ／ｎ2Ｚ）*の乗算サブグループである。
【００３９】
集合Ｕｎに対して、次のように定義された関数をｌｏｇnとする。
【００４０】
ｌｏｇn（ｘ）＝（ｘ−１）／ｎ
【００４１】
この関数は次の特性を有する。
∀ｘ∈Ｕｎ，∀ｙ∈Ｕｎ，ｌｏｇn（ｘｙ  ｍｏｄ  ｎ2）＝ｌｏｇn（ｘ）＋ｌｏｇn（ｙ）ｍｏｄ  ｎ
【００４２】
結果として、ｇがＵｎに属する任意の整数であるとき、全ての数ｍに対して、０≦ｍ＜ｎが得られる。
ｌｏｇn（ｇm  ｍｏｄ  ｎ2）＝ｍ・ｌｏｇn（ｇ）ｍｏｄ  ｎ2
【００４３】
この数学的特性が、以下に説明する本発明の方法で実施される暗号化方法の基礎となる。
【００４４】
図１は非対称暗号化方法を用いる、暗号通信システムを示している。それは通信チャネル１上に、例ではＡとＢである通信装置を備えている。例において、双方向チャネルを示した。それぞれの装置は、一対の公開鍵Ｋおよび秘密鍵Ｋ’を含んでいる。
【００４５】
公開鍵は、アドレス帳のような公開ファイル２内で公開され、それぞれの装置が参照することができる。したがって、装置Ａの公開鍵ＫAと装置Ｂの公開鍵ＫBは、この公開ファイル内にある。
【００４６】
それぞれの装置の秘密鍵Ｋ’は、装置によって秘密の仕方で、典型的には不揮発性メモリの保護領域内に保存される。したがって、装置Ａは秘密メモリ内にその秘密鍵Ｋ’Aを保存し、また装置Ｂは秘密メモリ内にその秘密鍵Ｋ’Bを保存している。それらは公開鍵も保存しているが、特定のアクセス保護のないメモリ領域内に保存している。
【００４７】
かかるシステムでは、装置Ａは装置Ｂの公開鍵ＫBを用いてメッセージｍを暗号文ｃAに暗号化でき、そして装置Ｂは秘密に保存されている自己の秘密鍵Ｋ’Bを用いてｃAを復号化することが出来る。逆に装置Ｂは装置Ａの公開鍵ＫAを用いてメッセージｍを暗号文ｃBに暗号化でき、装置Ａは、秘密に保存している自己の秘密鍵Ｋ’Aを用いてｃBを復号化できる。
【００４８】
典型的に、それぞれの装置は図２に示したごとく、少なくとも処理手段１０、すなわち計算のために特に異なるレジスタＲを有する中央処理装置（ＣＰＵ）と、通信チャネルとの通信インターフェース１１と、記憶手段を備えている。これらの記憶手段は、一般的にプログラムメモリ１２（ＲＯＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ）と、作業メモリ（ＲＡＭ）１３を含んでいる。実際に、それぞれの装置は、それらの秘密データを、プログラムメモリ内に設けられたアクセス保護領域１２０内に保存し、それらの公開データをこのメモリ内の通常アクセス領域内に保存する。作業メモリは、計算に必要な時間、暗号化するメッセージ、復号化する暗号文、あるいはさらに中間計算結果を一時的に保存することを可能にする。
【００４９】
このように、処理および記憶手段は、アプリケーションに関連するプログラムの実行、とくに本発明によるメッセージの暗号化／解読および／または署名の発生／検証のための暗号化方法の実施に対応する計算の実行を可能にする。これらの計算は、以下に詳細に見るごとく、特に、冪乗、剰余、および剰余の逆変換を含んでいる。
【００５０】
装置はさらに、特定の変型実施態様において、上記の計算に介入することのある乱数または擬似乱数ｒの発生器１４を含むことができ、該発生器は、本発明による全ての変型実施態様を実現するために必ずしも必要ではなく、図２において点線で囲まれている。
【００５１】
装置のこれら全ての手段は、アドレス・データバス１５に接続される。
【００５２】
本発明に使用されたかかる装置は周知であり、例えば、ＲＳＡを用いる従来技術の暗号通信システムに使用されているものに相当する。暗号通信システムの実際の例は、金融取引管理のための銀行サーバーとチップカードで構成されたシステムである。しかし他にも多くの用途分野、例えば電子商取引に関連する用途分野がある。
【００５３】
次に、図３に示した流れ図に関連して、本発明の第一の実施態様を詳細に説明する。
【００５４】
この流れ図は、通信チャネル２０上の装置Ａと装置Ｂの間の通信シーケンスを示している。これらの装置は、図２との関連において説明した処理、記憶、通信手段を少なくとも備えている、
【００５５】
本発明による暗号化方法は、公開鍵Ｋおよび秘密鍵Ｋ’の発生法を有する。
【００５６】
本発明によれば、この公開鍵および秘密鍵の発生法は、１９９０年１月に日本にて発行された”Systems & Computers”の”a method for rapid RSA Key generation” （ＹＡＳＵＫＯ  ＧＯＴＨＯ著，ＸＰ０００１７７８１７，ＩＳＳＮ：０８８２−１６６６，２１巻８号１１−２０ページ）にて周知であり、次の過程を有する。
・相異なる隣り合った２つの大きな素数ｐとｑの選択
・積ｐ・ｑに等しい数ｎの計算
・数λ（ｎ）＝ＰＰＣＭ（ｐ−１，ｑ−１）、すなわち数ｎのカーマイケル関数の計算
・次の２つの条件を満たす、０≦ｇ＜ｎ２である数ｇの決定
ａ）ｇはｎ２を法とする逆数になれる。
ｂ）ｏｒｄ（ｇ，ｎ２）＝０ ｍｏｄ ｎ。
【００５７】
この条件ｂ）は、整数０からｎ2の集合（Ｚ／ｎ2Ｚ）* 内の数ｇの次数が、上述の注記に従って、数ｎのゼロでない倍数であることを示している。
【００５８】
このとき公開鍵Ｋは数ｎと数ｇで形成される。秘密鍵は数ｐ，ｑとλ（ｎ）で形成されるか、あるいは数ｐとｑだけで形成され、λ（ｎ）は秘密鍵を用いる毎に再計算することができる。
【００５９】
この方法によって、それぞれの装置の公開鍵および秘密鍵を発生させる。この発生は、当該装置と用途分野によって、装置自体によって、または外部装置によって実施できる。
【００６０】
したがって、それぞれの装置、例えば装置Ａは、メモリ内に自己の公開鍵ＫA＝（ｎA，ｇA）を保存し、自己の秘密鍵Ｋ’A＝（ｐA，ｑA）を秘密に保存する。
【００６１】
くわえて、公開鍵は一般にアクセス可能なファイル内に置かれる。
【００６２】
本発明によると、以下に示すごとく、本発明はｇに特定の値を付与することにある。実際、可能な場合、すなわちｇ＝２が本発明による署名の発生法の条件ａ）及びｂ）を満たすとき、ｇ＝２を選ぶのが有利である。
【００６３】
このとき、装置Ａで実施される本発明の暗号化方法の第一の実施態様による暗号化方法は、装置Ｂにメッセージを送信するために、０≦ｍ＜ｎで、以下の過程を実現する。
・第二の装置Ｂの公開鍵ＫBを用いて装置Ａが実施する暗号化方法のパラメータｎとｇの教示：ｎ＝ｎB，ｇ＝ｇB
・暗号文ｃ＝ｇm  ｍｏｄ  ｎ2の計算
・通信チャネル上での暗号文ｃの伝送
【００６４】
したがって、本発明の第一の実施態様による暗号化方法は、公開鍵のパラメータｇを取り、それをｍ乗し、ｎ2を法とする剰余を計算することから成る。ここで分かるように、ＲＳＡにおいては、メッセージｍが冪乗されるが、本発明においては、メッセージｍが指数として用いられる。
【００６５】
暗号化されたメッセージ、すなわち暗号文ｃを受信する装置Ｂは、このとき、自己の秘密鍵のパラメータを用いて本発明による復号化方法を実施する。この復号化方法には以下の計算が含まれる。
【００６６】
・次のような数ｍの計算
【数１】
0004137385.tif 000002
ここで
ｌｏｇn（ｘ）＝（ｘ−１）／ｎ
【００６７】
ｇ＝２のとき、ｇの冪乗計算が容易になることが分かる。したがって好ましくは、可能な限り常にｇ＝２とする。言い換えれば、鍵の発生法はｇ＝２が条件ａ）及びｂ）を満たすかどうかを試すことから始まる。
【００６８】
復号化方法の計算の異なる変型を実施することもでき、それにより、装置が多数の暗号文を解読しなければならないときに、特定の量を予め計算して、それを装置内に秘密に保存することが可能になる。反対に、装置の秘密メモリ領域（図２の領域１２０）はもっと拡張されなければならず、というのも、このとき、パラメータｐおよびｑに加えて、追加のパラメータを保存しなければならないからである。これはある変型または別の変型の選択に影響しないわけではない。実際、メモリ保護領域の実現は高価であり、したがって、（メモリ）容量は一般的に制限されるが、いわゆる低価格デバイス（例えば、幾つかのタイプのチップカード）の場合は特に制限される。
【００６９】
復号化方法の第一の変型実施態様において、装置、この場合はＢは、量：
αn,g＝ｌｏｇn（ｇλ(n)ｍｏｄ  ｎ2）-1 ｍｏｄ  ｎ
を１度だけ予め計算して、それをメモリ内に秘密に保存する。
【００７０】
このようにして、装置が受信するそれぞれのメッセージの解読に必要な時間を、それだけ短縮する。実際、装置Ｂがこの変型復号化方法の段階を実行するとき、後は次の計算するだけでよい。
ｍ＝ｌｏｇn（ｃλ(n)ｍｏｄ  ｎ2）αn,g  ｍｏｄ  ｎ
【００７１】
本発明による復号化方法の第二の変型実施態様において、効率を高めるために（計算の迅速性）、中国剰余定理の利用を考慮に入れる。
【００７２】
復号化方法のこの第二の変型の段階において、装置は下記の（復号化）計算を実行する。
【００７３】
１．  ｍp＝ｌｏｇp（ｃp-1 ｍｏｄ  ｐ2）ｌｏｇp（ｇp-1 ｍｏｄ  ｐ2）-1  ｍｏｄ  ｐ
２．  ｍq＝ｌｏｇq（ｃq-1 ｍｏｄ  ｑ2）ｌｏｇp（ｇq-1 ｍｏｄ  ｑ2）-1  ｍｏｄ  ｑ
３．  ｍ＝ＴＲＣ（ｍp，ｍq，ｐ，ｑ）
ここで
ｌｏｇp（ｘ）＝（ｘ−１）／ｐ
ｌｏｇq（ｘ）＝（ｘ−１）／ｑ
【００７４】
この場合、つまり装置が極めて多数のメッセージを復号化することになる場合、装置は、さらに、下記の量を１回だけ予め計算することになる。
αp,g＝ｌｏｇp（ｇp-1 ｍｏｄ  ｐ2）-1 ｍｏｄ  ｐ
αq,g＝ｌｏｇq（ｇq-1 ｍｏｄ  ｑ2）-1 ｍｏｄ  ｑ
【００７５】
このとき装置は、これらの量を秘密データとして保存しなければならない。
【００７６】
復号化方法の段階の際に実施された計算は次のようになる。
１．  ｍp＝ｌｏｇp（ｃp-1 ｍｏｄ  ｐ2）αp,g  ｍｏｄ  ｐ
２．  ｍq＝ｌｏｇq（ｃq-1 ｍｏｄ  ｑ2）αq,g  ｍｏｄ  ｑ
３．  ｍ＝ＴＲＣ（ｍp，ｍq，ｐ，ｑ）
【００７７】
先に明らかにしたごとく、復号化計算のこれら全ての変型は、装置が極めて多数のメッセージを復号化するようになる場合、および処理時間の節約が、全ての秘密データを保存するための保護領域の最大メモリ容量を補う場合に有利になる。どの変型を選ぶかは、実際には、対象となる用途分野、およびコストや処理時間の制約との兼ね合いになる。
【００７８】
本発明の第二の実施態様は、同一の伝送メッセージｍについて計算される暗号文ｃが毎回異なるように、乱数（または擬似乱数）発生器によって与えられる乱数を暗号化方法において使用することから成る。したがって、通信システムの安全性はより高くなる。復号化方法に変化はない。
【００７９】
本発明のこの第二の実施態様には２つの変型が含まれる。
【００８０】
第一の変型では、暗号文ｃは次の計算によって得られる：  ｃ＝ｇm+nr ｍｏｄ  ｎ2
【００８１】
第二の変型では、暗号文ｃは次の計算によって得られる：  ｃ＝ｇm ｒn ｍｏｄ  ｎ2
【００８２】
この第二の変型は、実際には、第一の変型より長い処理時間を必要とするが、より高い安全性を提供する。
【００８３】
本発明の第三の実施態様では、（Ｚ／ｎＺ）* 内のｇの次数が、小さな位数の整数になるようにし、それは別の鍵発生法を実施しすることで得られる。
【００８４】
パラメータｇの次数に対するかかる条件によって、実際には数ｎの位数に関して２次になる（ｎ2関数）復号化方法の計算の複雑さが減じられる。
【００８５】
本発明のこの第三の実施態様では、公開鍵および秘密鍵の発生方法は次のようになる。
・整数ｕと、ｕが（ｐ−１）を整除し且つ（ｑ−１）を整除するような相異なる隣り合った２つの大きな素数ｐ及びｑとを秘密に選択すること
・積ｐ・ｑに等しい数ｎの計算
・数λ（ｎ）＝ＰＰＣＭ（ｐ−１，ｑ−１）、すなわち数ｎのカーマイケル表示の計算
・次の２つの条件を満たす、０≦ｈ＜ｎ2である数ｈの決定
ａ）ｈはｎ2を法とする逆数になれる
ｂ）ｏｒｄ（ｈ，ｎ2）＝０  ｍｏｄ  ｎ
・数ｇ＝ｈλ(n)/u ｍｏｄ  ｎ2  の計算
【００８６】
このとき公開鍵Ｋは数ｎと数ｇで形成される。秘密鍵は、装置内に秘密に保存されている整数（ｐ，ｑ，ｕ）で構成される。
【００８７】
好ましくは、（ｇの計算を容易にするため、すなわちｈ＝２が条件ａ）及びｂ）を満たすとき）可能な限りｈ＝２を選択する。
【００８８】
もし、ｕ＝ＰＧＣＤ（ｐ−１，ｑ−１）であるならば、この数は装置によりｐとｑから求められるので、保存する必要はない。
【００８９】
好ましくは、方法の安全性向上のために、最初に位数の小さい、典型的には１６０ビットのｕを選択する。小さな位数のｕを選択することによって、復号化計算が容易になることが分かるだろう。
【００９０】
この第三の実施態様では、メッセージｍを暗号化するための暗号化方法は、本発明の第一の実施態様について先に述べたものと同一であり、暗号文はｃ＝ｇm ｍｏｄ  ｎ2に等しい。
【００９１】
先に述べた本発明の第二の実施態様の第一の変型にしたがって、乱数ｒを用いて暗号文ｃを計算することもできる。このときｒは、ｕと同じ位数の、ランダム整数であり、暗号文は次の計算によって得られる：ｃ＝ｇm+nr ｍｏｄ  ｎ2
【００９２】
暗号化方法の前述のいずれかの実施によって計算した暗号文ｃは、それを解読しなければならない装置Ｂに送信される。メッセージを受信する装置Ｂによる復号化方法の実施は、少し異なっている。
【００９３】
実際、暗号文ｃから数ｍを見つけるために、復号化の段階において装置内で実行される計算は、次のようになる。
【数２】
0004137385.tif 000003
【００９４】
必要な処理時間を早めることができる計算の変型は、先のように適用することができる。
【００９５】
したがって、第一の変型では、量：
βn,g＝ｌｏｇn（ｇu ｍｏｄ  ｎ2）-1  ｍｏｄ  ｎ
を１度だけ予め計算して、それをメモリ内に秘密に保存する。
【００９６】
受信した暗号文ｃの復号化の段階の場合には、装置は次の計算を実行するだけでよい。
ｍ＝ｌｏｇ（ｃu ｍｏｄ  ｎ2）βn,g  ｍｏｄ  ｎ
【００９７】
第二の変型では、復号化計算を実行するために既に見てきた関数ｌｏｇpとｌｏｇqを用いて、中国剰余定理を利用する。
【００９８】
受信した暗号文ｃの復号化方法のこの変型の段階の場合、このとき装置は次の計算を実行する。
１．  ｍp＝ｌｏｇp（ｃu ｍｏｄ  ｐ2）ｌｏｇP（ｇu ｍｏｄ  ｐ2）-1  ｍｏｄ  ｐ
２．  ｍq＝ｌｏｇq（ｃu ｍｏｄ  ｑ2）ｌｏｇq（ｇu ｍｏｄ  ｑ2）-1  ｍｏｄ  ｑ
３．  ｍ＝ＴＲＣ（ｍp，ｍq，ｐ，ｑ）
【００９９】
第三の変型では、次の量：
βp,g＝ｌｏｇ（ｇu  ｍｏｄ  ｐ2）-1 ｍｏｄ  ｐ
βq,g＝ｌｏｇ（ｇu  ｍｏｄ  ｑ2）-1 ｍｏｄ  ｑ
を予め計算し、それらを装置内に秘密に保存することによって、第二の変型による暗号文ｃの解読に必要な処理時間をさらに早める。
【０１００】
受信した暗号文ｃの復号化方法のこの第三の変型の段階の場合、このとき装置は次の計算を実行するだけでよい。
１．  ｍp＝ｌｏｇp（ｃu ｍｏｄ  ｐ2） βp,g  ｍｏｄ  ｐ
２．  ｍq＝ｌｏｇq（ｃu ｍｏｄ  ｑ2） βq,g  ｍｏｄ  ｑ
３．  ｍ＝ＴＲＣ（ｍp，ｍq，ｐ，ｑ）
【０１０１】
本発明の第四の実施態様では、暗号化方法と復号化方法は、ｎ2を法とする整数グループに対する置換であるという特性を有する。言い換えれば、メッセージｍがｋビットで表されるとき、ｍに暗号化方法を適用して得られた暗号文ｃと、ｍに復号化方法を適用して得られた署名ｓは、ｋビットになる。
【０１０２】
この特性は、暗号化方法に、暗号化／復号化にも、署名発生／検証にも使えるという追加の特性を与える。この場合、復号化方法は署名発生法として、暗号化方法は署名検証法として用いられる。
【０１０３】
この第四の実施態様では、公開鍵および秘密鍵の発生法は本発明の第一の実施態様のものと同じである：Ｋ＝（ｎ，ｇ）およびＫ’＝（ｐ，ｑ，λ（ｎ））またはＫ’＝（ｐ，ｑ）
【０１０４】
装置Ａは、暗号化したメッセージｍを装置Ｂに送信しようとするとき、装置Ｂの公開鍵（ｎ，ｇ）を取得し、次に暗号化方法の段階において０≦ｍ＜ｎ2である数ｍに適用された下記の計算を、このとき実行する。
１．  ｍ1＝ｍ  ｍｏｄ  ｎ
２．  ｍ2＝（ｍ−ｍ１）／ｎ  （ユークリッド分割）
３．  Ｃ＝ｇm1 ｍ2m  ｍｏｄ  ｎ2
【０１０５】
この暗号文ｃが装置Ｂに送信される。
【０１０６】
したがって、装置Ｂが、ｍ1，ｍ2、最終的にｍを見つけるためには、対応する復号化方法を暗号文に適用しなければならない。本発明の第四の実施態様によるこの復号化方法は下記の計算を実施することから成る。
１．  ｍ1＝ｌｏｇn（ｃλ(n)ｍｏｄ  ｎ2）・ｌｏｇn（ｇλ(n)ｍｏｄ  ｎ2）-1 ｍｏｄ  ｎ
２．  ｗ＝ｃｇ-m1 ｍｏｄ  ｎ
３．  ｍ2＝ｗ1/n mod λ(n) ｍｏｄ  ｎ
４．  ｍ＝ｍ1＋ｎｍ2
【０１０７】
先に述べたごとく、本発明のこの第四の実施態様による復号化方法の変型を適用することができ、それにより、与えられたメッセージの復号化に必要な処理時間を短縮することができる。それは装置が多数のメッセージを復号化しなければならないときに有利である。
【０１０８】
第一の変型は下記の量を予め計算することから成る。
αn,g＝ｌｏｇn（ｇλ(n) ｍｏｄ  ｎ2）-1  ｍｏｄ  ｎ
γn＝１／ｎ  ｍｏｄ  λ（ｎ）
装置Ｂは１度だけ予め計算して、それをメモリ内に秘密に保存する。
【０１０９】
この第一の変型によって受信した暗号文ｃの復号化の新たな段階ごとに、装置Ｂは次の計算をすればよい。
１．  ｍ1＝ｌｏｇn（ｃλ(n)ｍｏｄ  ｎ2）αn,g ｍｏｄ  ｎ
２．  ｗ＝ｃｇ-m1 ｍｏｄ  ｎ
３．  ｍ2＝ｗγn  ｍｏｄ  ｎ
４．  ｍ＝ｍ1＋ｎｍ2
【０１１０】
第四の実施態様による復号化方法の第二の変型実施態様では、中国剰余定理を使用する。
【０１１１】
この第二の変型に従って暗号文ｃを復号化しようとする装置は、次に、下記の連続する計算を実行する。
１．  ｍ1,p＝ｌｏｇp（ｃp-1 ｍｏｄ  ｐ2）ｌｏｇp（ｇp-1 ｍｏｄ  ｐ2）-1ｍｏｄ  ｐ
２．  ｗp＝ｃｇ-m1,p ｍｏｄ  ｐ
３．  ｍ2,p＝ｗp1/q mod p-1 ｍｏｄ  ｐ
４．  ｍ1,q＝ｌｏｇq（ｃq-1  ｍｏｄ  ｑ2）ｌｏｇq（ｇq-1  ｍｏｄ  ｑ2）-1  ｍｏｄ  ｑ
５．  ｗq＝ｃｇ-m1,q  ｍｏｄ  ｑ
６．  ｍ2,q＝ｗq1/p mod q-1 ｍｏｄ  ｑ
７．  ｍ1＝ＴＲＣ（ｍ1,p，ｍ2,p，ｐ，ｑ）
８．  ｍ2＝ＴＲＣ（ｍ1,q，ｍ2,q，ｐ，ｑ）
９．  ｍ＝ｍ1＋ｐｑｍ2
【０１１２】
第三の変型では、この第二の変型の復号化の処理時間をさらに向上させるために、装置Ｂは下記の量を１度だけ予め計算して、それらをメモリ内に秘密に保存する。
αp,g＝ｌｏｇp（ｇp-1  ｍｏｄ  ｐ2）-1  ｍｏｄ  ｐ
αq,g＝ｌｏｇq（ｇq-1  ｍｏｄ  ｑ2）-1  ｍｏｄ  ｑ
γp＝１／ｑ  ｍｏｄ  ｐ−１
γq＝１／ｐ  ｍｏｄ  ｑ−１
【０１１３】
この第三の変型によって暗号文ｃを復号化しようとする装置は、次の計算をするだけでよい。
１．  ｍ1,p＝ｌｏｇp（ｃp-1 ｍｏｄ ｐ2）αp,g ｍｏｄ  ｐ
２．  ｗp＝ｃｇ-m1,p ｍｏｄ  ｐ
３．  ｍ2,p＝ｗpγp  ｍｏｄ  ｐ
４．  ｍ1,q＝ｌｏｇq（ｃq-1  ｍｏｄ  ｑ2）αq,g  ｍｏｄ  ｑ
５．  ｗq＝ｃｇ-m1,q  ｍｏｄ  ｑ
６．  ｍ2,q＝ｗqγq  ｍｏｄ  ｑ
７．  ｍ1＝ＴＲＣ（ｍ1,p，ｍ2,p，ｐ，ｑ）
８．  ｍ2＝ＴＲＣ（ｍ1,q，ｍ2,q，ｐ，ｑ）
９．  ｍ＝ｍ1＋ｐｑｍ2
【０１１４】
上述の本発明の第四の実施態様は、署名の発生／検証を可能にする。図４の流れ図に示したごとく、装置Ｂが装置Ａへのメッセージを表す数ｍの署名ｓを発生しなければならないとき、署名発生法として、自己の秘密鍵を用いた復号化方法を適用する：ｓ＝ＤK'B（ｍ）。
【０１１５】
署名ｓを受信し、かつメッセージｍを知っている装置Ａは、署名が正しいことを検証するが、該検証は、公開鍵を用いて署名ｓに暗号化方法を適用して得られた量ｖを計算することで行われる：ｖ＝ＥKB（ｓ）。署名が正しいときｖ＝ｍになる。
【０１１６】
第四の実施態様の復号化方法の全ての変型実施態様は、処理時間を早めることができるが、この署名の発生／検証においても適用できる。
【０１１７】
上述の発明は、メッセージの暗号化および／または署名を可能にしたいと望む全てのシステムに適用できる。本発明は、より高い安全性を望むか、あるいは処理速度の高速化を求めるかによって、異なる用途分野への応用可能性が広がることを可能にする。なお、この点に関して、本発明の第三の実施態様は、計算の複雑性が２次（ｎ2関数）にすぎないが、従来技術の全ての方法がもっと高次の複雑性（ｎ3関数）を有する限りにおいて、速度の面で本当の有利さを提供するものである。かかる利点は携帯式の装置、例えば、特にチップカードを用いる全ての用途分野、また低価格の装置に特に有利である。
【０１１８】
最後に、本発明の技術における当業者には自明なごとく、形状および／または細部の様々な変更が可能である。とくに、署名を暗号化することができ、あるいはさらにメッセージｍにハッシュ関数を適用してから、その署名を計算することもできる。これにより、たとえメッセージｍが変わらないとしても、毎回署名を変えることが可能となる。
【図面の簡単な説明】
【図１】  図１は、非対称型暗号通信システムの機能図である。
【図２】  図２は、本発明による暗号通信システムに使用された通信装置の機能図である。
【図３】  図３は、本発明による暗号化方法を用いるメッセージの暗号化／復号化におけるセッションの流れ図である。
【図４】図４は、本発明による暗号化方法を用いる署名の発生／検証セッションの流れ図である。
【図１】
0004137385.tif 000004
【図２】
0004137385.tif 000005
【図３】
0004137385.tif 000006
【図４】
0004137385.tif 000007