(57)【要約】暗号システムは、ＲＳＡアルゴリズムにおける復号化速度を、Ｚｎ＊のある一定の部分群を利用することにより、向上させる。この暗号システムは、Ｚｎ＊の部分群における指数演算に基づく落とし戸転置の新たなファミリを用いる。
2004524548.tif 000002
【特許請求の範囲】
【請求項１】
メッセージをネットワークを介して第１と第２の計算ユニット間で送るシステムにおいて、方法が、
（ａ）前記第１計算ユニットにおいてメッセージＭを暗号文Ｃに暗号化するステップであって、前記暗号文Ｃが、以下の通り値Ｖと値Ｗを含む、前記の暗号化ステップであって、
（１）値Ｖが、数ｘの関数Ｖ＝ｘｅであり、ここで、ｅは整数、ｘは以下の通りであり、
【数１】
2004524548.tif 000031
ここで、
（ｉ）ｎは数ｎ＝ｐ１ｐ２であり、ここで、ｐ１，ｐ２は、素数であって、ｐ１＝ｒ１ｑ１＋１，ｐ２＝ｒ２ｑ２＋１であり、ここで、ｒ１，ｒ２は乱数、ｑ１，ｑ２は素数であり、
（ｉｉ）Ｒは、前記乱数ｒ１，ｒ２とは独立に選択した乱数であり、
（ｉｉｉ）ｇは、
【数２】
2004524548.tif 000032
であり、ここで、ｒ３は、前記乱数ｒ１，ｒ２，Ｒとは独立に選択した乱数であり、
（２）値Ｗは、値ｈ（ｘ）と前記メッセージＭの関数であり、前記値ｈ（ｘ）は、前記数ｘの一方向性関数の結果である、
前記の暗号化ステップと、
（ｂ）前記暗号文Ｃを前記第１計算ユニットから前記第２計算ユニットに送出するステップと、
（ｃ）前記暗号文Ｃを前記第２計算ユニットにおいて復号化して前記メッセージＭを再現する復号化ステップであって、ここでＭは、前記値Ｗと前記値ｈ（ｘ）の関数であり、ｘは、
【数３】
2004524548.tif 000033
として得る、前記の復号化ステップと、
から成る方法。
【請求項２】
請求項１記載の方法において、前記暗号化ステップは、値Ｗを、
【数４】
2004524548.tif 000034
として得るステップから成ること、を特徴とする方法。
【請求項３】
請求項２記載の方法において、前記復号化ステップは、前記メッセージＭを、
【数５】
2004524548.tif 000035
として得るステップから成ること、を特徴とする方法。
【請求項４】
請求項１記載の方法において、前記整数ｅは２に等しいこと、を特徴とする方法。
【請求項５】
請求項１記載の方法において、
前記暗号化ステップは、前記数ｘと前記メッセージＭのハッシュ関数ｈから、ハッシュ値ｈ（ｘ，Ｍ）を計算するステップから成り、
前記送出ステップは、前記第１計算ユニットから前記第２計算ユニットへ前記ハッシュ値ｈ（ｘ，Ｍ）を前記暗号文Ｃと共に送るステップから成り、
前記復号化ステップは、前記得た数ｘと前記再現したメッセージＭのハッシュ関数ｈから、テスト・ハッシュ値ｈ’（ｘ，Ｍ）を計算し、そして前記第１計算ユニットから受けた前記ハッシュ値ｈ（ｘ，Ｍ）を前記テスト・ハッシュ値ｈ’（ｘ，Ｍ）と比較して、前記メッセージＭが変更されているかどうか検証するステップから成ること、
を特徴とする方法。
【請求項６】
請求項１記載の方法において、前記暗号化ステップは、
前記数ｘを記憶するステップと、
古い前記数ｘに基づいて新たな数ｘを発生するステップと、
前記新たな数ｘを次にメッセージの暗号化のために使用するステップと、
から成ること、を特徴とする方法。
【請求項７】
メッセージＭを暗号文Ｃに暗号化する方法であって、
ｎは、形態ｎ＝ｐ１ｐ２にある数であり、ここで、ｐ１，ｐ２は、素数であり、
ｐ１＝ｒ１ｑ１＋１，ｐ２＝ｒ２ｑ２＋１であり、ここで、ｒ１，ｒ２は乱数、ｑ１，ｑ２は素数であり、
ｇは、
【数６】
2004524548.tif 000036
の形態にある数であり、ここで、ｒ３は、前記乱数ｒ１，ｒ２とは独立に選択した乱数であり、
前記方法が、
数ｘ＝ｇＲ ｍｏｄ ｎを計算するステップであって、ここで、Ｒは、前記乱数ｒ１，ｒ２，ｒ３とは独立に選択した乱数である、前記の計算ステップと、
前記数ｘを一方向性関数ｈにしたがって変換して値ｈ（ｘ）を発生するステップと、
前記メッセージＭを前記値ｈ（ｘ）の関数にしたがってエンコードするステップと、
から成る暗号化方法。
【請求項８】
請求項７記載の暗号化方法において、前記エンコードするステップは、
【数７】
2004524548.tif 000037
を計算するステップから成ること、を特徴とする暗号化方法。
【請求項９】
請求項７記載の暗号化方法であって、さらに、前記数ｘと前記メッセージＭのハッシュ関数ｈから、ハッシュ値ｈ（ｘ，Ｍ）を計算するステップを含むこと、を特徴とする暗号化方法。
【請求項１０】
請求項７記載の暗号化方法であって、さらに、
前記数ｘを記憶するステップと、
古い前記数ｘに基づいて新たな数ｘを発生するステップと、
前記新たな数ｘを次にメッセージの暗号化のために使用するステップと、
を含むこと、を特徴とする暗号化方法。
【請求項１１】
請求項７記載の方法における前記ステップを実行するためのコンピュータ実行可能の命令から成るコンピュータ読み取り可能媒体。
【請求項１２】
請求項７記載の方法における前記ステップを実行するためのコンピュータ実行可能の命令でプログラムしたコンピュータ。
【請求項１３】
暗号文Ｃを復号化してメッセージＭを再現する方法であって、
ｎは、形態ｎ＝ｐ１ｐ２にある数であり、ここで、ｐ１，ｐ２は、素数であり、
ｐ１＝ｒ１ｑ１＋１，ｐ２＝ｒ２ｑ２＋１であり、ここで、ｒ１，ｒ２は乱数、ｑ１，ｑ２は素数であり、
ｇは、
【数８】
2004524548.tif 000038
の形態にある数であり、ここで、ｒ３は、前記乱数ｒ１，ｒ２とは独立に選択した乱数であり、
ｘは、ｘ＝ｇＲ ｍｏｄ ｎの形態にある数であり、ここで、Ｒは、前記乱数ｒ１，ｒ２，ｒ３とは独立に選択した乱数であり、
ｅは整数であり、
ＶはＶ＝ｘｅの形態にある値であり、
前記方法が、
前記値Ｖから前記数ｘを再現するステップであって、ここで、
【数９】
2004524548.tif 000039
である、前記の再現ステップと、
前記数ｘを一方向性関数ｈにしたがって変換して値ｈ（ｘ）を発生するステップと、
前記暗号文Ｃを前記値ｈ（ｘ）の関数にしたがってデコードして、前記メッセージＭを再現するステップと、
から成る復号化方法。
【請求項１４】
請求項１３記載の復号化方法において、前記デコードするステップは、
【数１０】
2004524548.tif 000040
を計算するステップから成ること、を特徴とする復号化方法。
【請求項１５】
請求項１３記載の復号化方法であって、さらに、前記数ｘと前記再捕捉したメッセージＭとのハッシュ関数ｈから、ハッシュ値ｈ（ｘ，Ｍ）を計算するステップを含むこと、を特徴とする復号化方法。
【請求項１６】
請求項１３記載の方法における前記ステップを実行するコンピュータ実行可能の命令を含むコンピュータ読み取り可能媒体。
【請求項１７】
請求項１３記載の方法における前記ステップを実行するコンピュータ実行可能の命令でプログラムしたコンピュータ。
【請求項１８】
メッセージをネットワークを介して第１と第２の計算ユニット間で送るシステムにおいて、方法が、
（ａ）前記第１計算ユニットにおいてメッセージＭを暗号文Ｃに暗号化するステップであって、前記暗号文Ｃが、以下の通り値Ｖと値Ｗを含む、前記の暗号化ステップであって、
（１）値Ｖが、数ｘの関数Ｖ＝ｘｅであり、ここで、ｅは、最初のｂ個の奇数の素数から選択した整数であり、ｘは以下の通りであり、
【数１１】
2004524548.tif 000041
ここで、
（ｉ）ｎは数ｎ＝ｐ１ｐ２であり、ここで、ｐ１，ｐ２は、素数であって、ｐ１＝ｒ１ｑ１＋１，ｐ２＝ｒ２ｑ２＋１であり、ここで、ｑ１，ｑ２は素数、ｒ１，ｒ２は、前記最初のｂ個の奇数素数で割り切れない乱数であり、
（ｉｉ）Ｒは、前記乱数ｒ１，ｒ２とは独立に選択した乱数であり、
（ｉｉｉ）ｇは、
【数１２】
2004524548.tif 000042
の形態にある数であり、ここで、ｒ３は、前記乱数ｒ１，ｒ２，Ｒとは独立に選択した乱数であり、
（２）値Ｗは、値ｈ（ｘ）と前記メッセージＭの関数であり、前記値ｈ（ｘ）は、前記数ｘの一方向性関数の結果である、
前記の暗号化ステップと、
（ｂ）前記暗号文Ｃを前記第１計算ユニットから前記第２計算ユニットに送出するステップと、
（ｃ）前記暗号文Ｃを前記第２計算ユニットにおいて復号化して前記メッセージＭを再現する復号化ステップであって、ここでＭは、前記値Ｗと前記値ｈ（ｘ）の関数であり、ｘは、
【数１３】
2004524548.tif 000043
として得る、前記の復号化ステップと、
から成る方法。
【請求項１９】
ＲＳＡ落とし戸転置ファミリを用いるベレア−ロガウェイ暗号系において、前記ＲＳＡ落とし戸転置ファミリを、Ｚｎ＊の部分群における指数演算に基づく落とし戸転置のファミリと置き換えることにより、復号化を改善する方法。
【請求項２０】
請求項１９記載の方法における前記ステップを実行するコンピュータ実行可能の命令を含むコンピュータ読み取り可能媒体。
【請求項２１】
請求項１９記載の方法における前記ステップを実行するコンピュータ実行可能の命令でプログラムしたコンピュータ。
【請求項２２】
メッセージを通信チャンネルを介して送るシステムであって、
メッセージＭを暗号文Ｃに変換し、そして該暗号文Ｃを前記通信チャンネルを介して送信するエンコーダであって、前記暗号文Ｃが、以下の通り値Ｖと値Ｗを含む、前記のエンコーダであって、
（１）値Ｖが、数ｘの関数Ｖ＝ｘｅであり、ここで、ｅは整数、ｘは以下の通りであり、
【数１４】
2004524548.tif 000044
ここで
（ｉ）ｎは数ｎ＝ｐ１ｐ２であり、ここで、ｐ１，ｐ２は、素数であって、ｐ１＝ｒ１ｑ１＋１，ｐ２＝ｒ２ｑ２＋１であり、ここで、ｒ１，ｒ２は乱数、ｑ１，ｑ２は素数であり、
（ｉｉ）Ｒは、前記乱数ｒ１，ｒ２とは独立に選択した乱数であり、
（ｉｉｉ）ｇは、
【数１５】
2004524548.tif 000045
であり、ここで、ｒ３は、前記乱数ｒ１，ｒ２，Ｒとは独立に選択した乱数であり、
（２）値Ｗは、値ｈ（ｘ）と前記メッセージＭの関数であり、前記値ｈ（ｘ）は、前記数ｘの一方向性関数の結果である、
前記のエンコーダと、
前記暗号文Ｃと前記値Ｖを前記通信チャンネルを介して受け、そして前記暗号文Ｃを前記メッセージＭに変換し戻すように結合したデコーダであって、ここでＭは、前記値Ｗと前記値ｈ（ｘ）の関数であり、ｘは、
【数１６】
2004524548.tif 000046
として得る、前記のデコーダと、
から成るシステム。
【請求項２３】
請求項２２記載のシステムにおいて、前記エンコーダは、値Ｗを、
【数１７】
2004524548.tif 000047
として得ること、を特徴とするシステム。
【請求項２４】
請求項２３記載のシステムにおいて、前記デコーダは、前記メッセージＭを、
【数１８】
2004524548.tif 000048
として得ること、を特徴とするシステム。
【請求項２５】
請求項２２記載のシステムにおいて、前記整数ｅは２に等しいこと、を特徴とするシステム。
【請求項２６】
請求項２２記載のシステムにおいて、
前記エンコーダは、前記数ｘと前記メッセージＭのハッシュ関数ｈから、ハッシュ値ｈ（ｘ，Ｍ）を計算し、そして前記ハッシュ値ｈ（ｘ，Ｍ）を前記暗号文Ｃと共に送信し、
前記デコーダは、前記得た数ｘと前記再現したメッセージＭのハッシュ関数ｈから、テスト・ハッシュ値ｈ’（ｘ，Ｍ）を計算し、そして前記第１計算ユニットから受けた前記ハッシュ値ｈ（ｘ，Ｍ）を前記テスト・ハッシュ値ｈ’（ｘ，Ｍ）と比較して、前記メッセージＭが変更されているかどうか検証すること、
を特徴とするシステム。
【請求項２７】
請求項２２記載のシステムにおいて、前記エンコーダは、前記数ｘを記憶し、古い前記数ｘに基づいて新たな数ｘを発生し、前記新たな数ｘを使用して前記値Ｖと前記値Ｗを計算すること、を特徴とするシステム。
【請求項２８】
暗号システムのためのエンコーダであって、
ｎは、形態ｎ＝ｐ１ｐ２にある数であり、ここで、ｐ１，ｐ２は、素数であり、
ｐ１＝ｒ１ｑ１＋１，ｐ２＝ｒ２ｑ２＋１であり、ここで、ｒ１，ｒ２は乱数、ｑ１，ｑ２は素数であり、
ｇは、
【数１９】
2004524548.tif 000049
の形態にある数であり、ここで、ｒ３は、前記乱数ｒ１，ｒ２とは独立に選択した乱数であり、
前記エンコーダが、
数ｘ＝ｇＲ ｍｏｄ ｎを計算する手段であって、ここで、Ｒは、前記乱数ｒ１，ｒ２，ｒ３とは独立に選択した乱数である、前記の手段と、
前記数ｘを一方向性関数ｈにしたがって変換して値ｈ（ｘ）を発生する手段と、
メッセージＭを前記値ｈ（ｘ）の関数にしたがってエンコードする手段と、
から成るエンコーダ。
【請求項２９】
請求項２８記載のエンコーダにおいて、前記エンコードする手段は、前記メッセージＭを、
【数２０】
2004524548.tif 000050
の関数にしたがってエンコードすること、を特徴とするエンコーダ。
【請求項３０】
請求項２８記載のエンコーダであって、さらに、
前記数ｘを記憶する手段と、
古い前記数ｘに基づいて新たな数ｘを発生する手段と、
前記新たな数ｘを使用して前記値ｈ（ｘ）を得る手段と、
を含むこと、を特徴とするエンコーダ。
【請求項３１】
暗号システムのためのデコーダであって、
ｎは、形態ｎ＝ｐ１ｐ２にある数であり、ここで、ｐ１，ｐ２は、素数であり、
ｐ１＝ｒ１ｑ１＋１，ｐ２＝ｒ２ｑ２＋１であり、ここで、ｒ１，ｒ２は乱数、ｑ１，ｑ２は素数であり、
ｇは、
【数２１】
2004524548.tif 000051
の形態にある数であり、ここで、ｒ３は、前記乱数ｒ１，ｒ２とは独立に選択した乱数であり、
ｘは、ｘ＝ｇＲ ｍｏｄ ｎの形態にある数であり、ここで、Ｒは、前記乱数ｒ１，ｒ２，ｒ３とは独立に選択した乱数であり、
ｅは整数であり、
ＶはＶ＝ｘｅの形態にある値であり、
Ｗは、メッセージＭと値ｈ（ｘ）の関数から得た値であり、ここでｈ（ｘ）は、一方向性関数ｈの結果であり、
前記デコーダが、
前記値Ｖと値Ｗを受ける手段と、
前記値Ｖから前記数ｘを復元する手段であって、ここで、
【数２２】
2004524548.tif 000052
である、前記の復元手段と、
前記数ｘを一方向性関数ｈにしたがって変換して前記値ｈ（ｘ）を発生する手段と、
前記値Ｗを前記値ｈ（ｘ）の関数にしたがってデコードして、前記メッセージＭを再捕捉する手段と、
から成るデコーダ。
【請求項３２】
請求項３１記載のデコーダにおいて、前記デコードする手段は、関数
【数２３】
2004524548.tif 000053
を計算して、前記メッセージＭを再捕捉すること、を特徴とするデコーダ。
【請求項３３】
請求項３１記載のデコーダであって、さらに、前記数ｘと前記再捕捉したメッセージＭとのハッシュ関数ｈから、ハッシュ値ｈ（ｘ，Ｍ）を計算する手段を含むこと、を特徴とするデコーダ。
【請求項３４】
メッセージを通信チャンネルを介して送るシステムであって、
メッセージＭを暗号文Ｃに変換し、そして前記暗号文Ｃを前記通信チャンネルを介して送信するエンコーダであって、前記暗号文Ｃが、以下の通り値Ｖと値Ｗを含む、前記のエンコーダであって、
（１）値Ｖが、数ｘの関数Ｖ＝ｘｅであり、ここで、ｅは、最初のｂ個の奇数の素数から選択した整数であり、ｘは以下の通りであり、
【数２４】
2004524548.tif 000054
ここで、
（ｉ）ｎは数ｎ＝ｐ１ｐ２であり、ここで、ｐ１，ｐ２は、素数であって、ｐ１＝ｒ１ｑ１＋１，ｐ２＝ｒ２ｑ２＋１であり、ここで、ｑ１，ｑ２は素数、ｒ１，ｒ２は、前記最初のｂ個の奇数素数で割り切れない乱数であり、
（ｉｉ）Ｒは、前記乱数ｒ１，ｒ２とは独立に選択した乱数であり、
（ｉｉｉ）ｇは、
【数２５】
2004524548.tif 000055
の形態にある数であり、ここで、ｒ３は、前記乱数ｒ１，ｒ２，Ｒとは独立に選択した乱数であり、
（２）値Ｗは、値ｈ（ｘ）と前記メッセージＭの関数であり、前記値ｈ（ｘ）は、前記数ｘの一方向性関数の結果である、
前記のエンコーダと、
前記暗号文Ｃと前記値Ｖを前記通信チャンネルを介して受け、そして前記暗号文Ｃを前記メッセージＭに変換し戻すように結合したデコーダであって、ここでＭは、前記値Ｗと前記値ｈ（ｘ）の関数であり、ｘは、
【数２６】
2004524548.tif 000056
として得る、前記のデコーダと、
から成るシステム。
【請求項３５】
ＲＳＡ落とし戸転置ファミリを用いるベレア−ロガウェイ暗号系であって、前記ＲＳＡ落とし戸転置ファミリを、Ｚｎ＊の部分群における指数演算に基づく落とし戸転置のファミリと置き換えること、を特徴とするベレア−ロガウェイ暗号系。
【請求項３６】
メッセージＭを暗号文Ｃに暗号化するようコンピュータに指揮するコンピュータ実行可能の命令を有するコンピュータ読み取り可能媒体であって、
ｎは、形態ｎ＝ｐ１ｐ２にある数であり、ここで、ｐ１，ｐ２は、素数であり、
ｐ１＝ｒ１ｑ１＋１，ｐ２＝ｒ２ｑ２＋１であり、ここで、ｒ１，ｒ２は乱数、ｑ１，ｑ２は素数であり、
ｇは、
【数２７】
2004524548.tif 000057
の形態にある数であり、ここで、ｒ３は、前記乱数ｒ１，ｒ２とは独立に選択した乱数であり、
前記コンピュータ読み取り可能媒体が、
数ｘ＝ｇＲ ｍｏｄ ｎを計算するようコンピュータに指揮するコンピュータ実行可能の命令であって、ここで、Ｒは、前記乱数ｒ１，ｒ２，ｒ３とは独立に選択した乱数である、前記のコンピュータ実行可能の命令と、
前記数ｘを一方向性関数ｈにしたがって変換して値ｈ（ｘ）を発生するようコンピュータに指揮するコンピュータ実行可能の命令と、
前記メッセージＭを前記値ｈ（ｘ）の関数にしたがってエンコードするようコンピュータに指揮するコンピュータ実行可能の命令と、
から成るコンピュータ読み取り可能媒体。
【請求項３７】
請求項３６記載のコンピュータ読み取り可能媒体において、さらに、前記メッセージＭを、関数
【数２８】
2004524548.tif 000058
にしたがってエンコードするようコンピュータに指揮するコンピュータ実行可能の命令を含むこと、を特徴とするコンピュータ読み取り可能媒体。
【請求項３８】
請求項３６記載のコンピュータ読み取り可能媒体であって、さらに、前記数ｘを記憶し、古い前記数ｘに基づいて新たな数ｘを発生し、前記新たな数ｘを使用して前記値ｈ（ｘ）を得るように、コンピュータに指揮するコンピュータ実行可能の命令を含むこと、を特徴とするコンピュータ読み取り可能媒体。
【請求項３９】
請求項３６記載のコンピュータ読み取り可能媒体に具体化した前記コンピュータ実行可能の命令を実行するようプログラムしたプロセッサ。
【請求項４０】
暗号文Ｃを復号化してメッセージＭを復元するようコンピュータに指揮するコンピュータ実行可能の命令を有するコンピュータ読み取り可能媒体であって、
ｎは、形態ｎ＝ｐ１ｐ２にある数であり、ここで、ｐ１，ｐ２は、素数であり、
ｐ１＝ｒ１ｑ１＋１，ｐ２＝ｒ２ｑ２＋１であり、ここで、ｒ１，ｒ２は乱数、ｑ１，ｑ２は素数であり、
ｇは、
【数２９】
2004524548.tif 000059
の形態にある数であり、ここで、ｒ３は、前記乱数ｒ１，ｒ２とは独立に選択した乱数であり、
ｘは、ｘ＝ｇＲ ｍｏｄ ｎの形態にある数であり、ここで、Ｒは、前記乱数ｒ１，ｒ２，ｒ３とは独立に選択した乱数であり、
ｅは整数であり、
ＶはＶ＝ｘｅの形態にある値であり、
前記コンピュータ読み取り可能媒体が、
前記値Ｖから前記数ｘを復元するようコンピュータに指揮するコンピュータ実行可能の命令であって、ここで、
【数３０】
2004524548.tif 000060
である、前記のコンピュータ実行可能の命令と、
前記数ｘを一方向性関数ｈにしたがって変換してｈ（ｘ）を発生するようコンピュータに指揮するコンピュータ実行可能の命令と、
前記暗号文Ｃを前記値ｈ（ｘ）の関数にしたがってデコードして前記メッセージＭを再捕捉するよう、コンピュータに指揮するコンピュータ実行可能の命令と、
から成るコンピュータ読み取り可能媒体。
【請求項４１】
請求項４０記載のコンピュータ読み取り可能媒体であって、前記暗号文Ｃを前記関数
【数３１】
2004524548.tif 000061
にしたがってデコードするようコンピュータに指揮するコンピュータ実行可能の命令を含むこと、を特徴とするコンピュータ読み取り可能媒体。
【請求項４２】
請求項４０記載のコンピュータ読み取り可能媒体であって、さらに、前記数ｘと前記再捕捉したメッセージＭとのハッシュ関数ｈから、ハッシュ値ｈ（ｘ，Ｍ）を計算するよう、コンピュータに指揮するコンピュータ実行可能の命令を含むこと、を特徴とするコンピュータ読み取り可能媒体。
【請求項４３】
請求項４０記載のコンピュータ読み取り可能媒体に具体化した前記コンピュータ実行可能の命令を実行するプログラムしたプロセッサ。
【発明の詳細な説明】
【０００１】
（技術分野）
本発明は、暗号化および復号化処理を実行する暗号のシステム、コンピュータ、コンピュータ実施形方法に関するものである。詳細には、本発明は、復号化処理を実行する速度を向上させた暗号システムに関するものである。
【０００２】
（発明の背景）
公開鍵暗号法は、これがなければ安全でない通信チャンネルを介してメッセージを安全に伝送するために広く使用されているアプローチである。公開鍵暗号法は、非対称の鍵ペアを用いる。“非対称”の暗号鍵ペアは、２つの別個の鍵から成っており、データを１方向に操作する第１の鍵と、この操作したデータをその元の形態に変換し戻す第２の鍵とである。これら鍵は、一方の鍵を他方の鍵から（少なくとも法外でない時間内に）計算できないという数学的関係に基づいている。
【０００３】
暗号鍵ペアは、異なった機能のために使用することができ、例えば、暗号化、復号化、デジタル署名、署名検証、認証である。１例として、非対称の鍵ペアを使用する暗号化と復号化は、以下のように表すことができる。
【０００４】
【数３２】
2004524548.tif 000003
【０００５】
ここで、“ＥＫｐｕｂ”は、公開暗号化鍵“Ｋｐｕｂ”を使用して平文メッセージ“Ｍ”を暗号文“Ｃ”に暗号化する暗号化関数であり、“ＤＫｐｒｉ”は、秘密の復号化鍵“Ｋｐｒｉ”を使用する復号化関数である。この逆も真であって、メッセージは、その秘密鍵を使って“署名”でき、そしてこの署名は、その公開鍵を使って検証することができる。
【０００６】
公開鍵システムにおいては、公開鍵は、他の者に配布し、秘密鍵は秘密に保持される。この非対称の公開鍵と秘密鍵とは、２つの結果を保証する。第１に、秘密鍵の保有者のみが、それに対応する公開鍵で暗号化されたメッセージを復号化できることである。第２に、別の者が公開鍵を使ってメッセージを復号化した場合、そのメッセージが、その公開鍵で暗号化されたことそしておそらくその秘密鍵の保有者から生じたことを、その者に保証することができる。
【０００７】
最も知られおりかつ最も広く使われている非対称暗号の１つは、ＲＳＡ暗号式暗号であり、これは、その創作者であるＲｉｖｅｓｔ（リベスト）、Ｓｈａｍｉｒ（シャミル）およびＡｄｌｅｍａｎ（アドルマン）にちなんで名が付けられている。元のＲＳＡ暗号システムは、“暗号通信のシステムおよび方法（Ｃｒｙｐｔｏｇｒａｐｈｉｃ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ Ｓｙｓｔｅｍ ａｎｄ Ｍｅｔｈｏｄ）”と題する米国特許４，４０５，８２９に記載されており、これは、Ｒｉｖｅｓｔ（リベスト）、Ｓｈａｍｉｒ（シャミル）およびＡｄｌｅｍａｎ（アドルマン）の名で、１９８３年９月２０に出願されたものである。この特許は、背景情報として言及により本文に含めるものとする。
【０００８】
暗号化および復号化のためのこのＲＳＡ暗号は、以下で与えられる。
【０００９】
【数３３】
2004524548.tif 000004
【００１０】
ここで、ｐ１とｐ２は素数（ｐｒｉｍｅ ｎｕｍｂｅｒ）であり、ｎはｎ ＝ ｐ１ ｐ２
の形態の合成数であり、ｅは、（ｐ１−１）（ｐ２−１）と互いに素でる数である。
【００１１】
演算“ｍｏｄ”は、“還元（ｍｏｄｕｌａｒ ｒｅｄｕｃｔｉｏｎ）”演算、あるいは単に“モジュロ（ｍｏｄｕｌｏ）”演算であり、これは、大きな整数算術にとっては一般的な演算である。このモジュロ演算は、算術演算であってその結果が除算演算の剰余である算術演算である。これは、“Ａ ｍｏｄ Ｂ”として表現し、ここで、Ａは、何等かの底（ｂａｓｅ）で書かれた数であり、Ｂは“法（ｍｏｄｕｌｕｓ）”である。Ａ ｍｏｄ Ｂの結果は、数Ａを法Ｂで除算したその剰余である。簡単な例としては、モジュロ演算１７ ｍｏｄ ３は、２の結果となるが、それは、１７を３で割ると、余りが２となるからである。これは剰余を発生するため、モジュロ演算は、“除算剰余”演算とも代わりに呼ぶことがある。
【００１２】
在来のＲＳＡ暗号法では、復号化は、暗号化よりもかなり遅いものである。この不一致は、ＲＳＡ暗号が、メッセージを復号化するのに、この同じメッセージを暗号化するのに必要とするよりもより多くの計算を必要とする、ということに起因している。この不一致は、ある種の環境においては不利となることがある。例えば、クライアント・サーバの状況においては、クライアントとサーバは、暗号化したメッセージを互いに交換することが多い。個々のクライアントは、メッセージを暗号化するのに豊富な時間とリソースを有していることが多い。しかし、サーバは、そのような快適さを経験したことがなく、時には、特に高いクライアント要求量の時間の間において、入来するメッセージを迅速に復号化するその能力が制限されることがある。
【００１３】
したがって、ＲＳＡアルゴリズムにおける復号化の速度を完全することに対するニーズが存在する。
【００１４】
（発明の摘要）
本発明は、ＲＳＡ暗号における復号化速度を改善する暗号のシステムおよび方法に関係している。この暗号システムは、Ｚｎ＊の部分群における指数演算に基づく落とし戸転置の新たなファミリを用いる。
【００１５】
本システムは、メッセージＭを暗号文Ｃに変換しそして該暗号文Ｃを通信チャンネルを介して送信するエンコーダを備える。暗号文Ｃは、２つのコンポーネント、すなわち値Ｖと値Ｗを有する。値Ｖは、数ｘの関数、すなわちＶ＝ｘｅであり、ここで、ｅは整数、ｘは以下の通りであり、
【００１６】
【数３４】
2004524548.tif 000005
【００１７】
ここで、
（ｉ）ｎは数ｎ＝ｐ１ｐ２であり、ここで、ｐ１，ｐ２は、素数であって、ｐ１＝ｒ１ｑ１＋１，ｐ２＝ｒ２ｑ２＋１であり、ここで、ｒ１，ｒ２は乱数、ｑ１，ｑ２は素数であり、
（ｉｉ）Ｒは、前記乱数ｒ１，ｒ２とは独立に選択した乱数であり、
（ｉｉｉ）ｇは、
【００１８】
【数３５】
2004524548.tif 000006
【００１９】
であり、ここで、ｒ３は、前記乱数ｒ１，ｒ２，Ｒとは独立に選択した乱数である。
【００２０】
前記値Ｗは、値ｈ１（ｘ）と前記メッセージＭの関数（例えば
【００２１】
【数３６】
2004524548.tif 000007
【００２２】
である）としてエンコードし、ここで、前記値ｈ１（ｘ）は、前記数ｘの一方向性関数（例えば、ｘのハッシュ関数）の結果である。
【００２３】
また、前記エンコーダは、前記数ｘと前記メッセージＭのハッシュ関数ｈを使ってハッシュ値ｈ２（ｘ，Ｍ）を計算する。前記エンコーダは、前記暗号文Ｃ（値Ｖと値Ｗを含む）と前記ハッシュ値ｈ２（ｘ，Ｍ）を前記通信チャンネルを介して送る。
【００２４】
前記システムは、さらに、前記暗号文Ｃと前記ハッシュ値ｈ２（ｘ，Ｍ）を前記通信チャンネルを介して受け、そして前記暗号文Ｃを前記メッセージＭに変換し戻すように結合したデコーダを備える。該デコーダは、最初に、前記数ｘを前記値Ｖから、以下のように得る。
【００２５】
【数３７】
2004524548.tif 000008
【００２６】
前記デコーダは、前記値Ｗと前記値ｈ１（ｘ）（例えば、
【００２７】
【数３８】
2004524548.tif 000009
【００２８】
である）の関数を使って前記メッセージＭをデコードする。前記メッセージＭを復元した後、前記デコーダは、前記数ｘと前記復元したメッセージＭから、テスト・ハッシュ値ｈ２’（ｘ，Ｍ）を計算し、そして前記エンコーダから受けた前記ハッシュ値ｈ２（ｘ，Ｍ）を前記テスト・ハッシュ値ｈ２’（ｘ，Ｍ）と比較する。これら２つのハッシュ値が一致した場合、前記メッセージＭが変更されていないことになる。
【００２９】
（好ましい実施形態の詳細な説明）
以下の説明は、読者が暗号技術およびモジュロ演算に精通していることを仮定している。暗号法の基本的な入門として、読者は、シュナイダ（Ｂｒｕｃｅ Ｓｃｈｎｅｉｅｒ）著の“暗号の応用：プロトコル、アルゴリズム、Ｃのソースコード”と題するテキスト（ａ ｔｅｘｔ ｗｒｉｔｔｅｎ ｂｙ Ｂｒｕｃｅ Ｓｃｈｎｅｉｅｒ ａｎｄ ｅｎｔｉｔｌｅｄ， ”Ａｐｐｌｉｅｄ Ｃｒｙｐｔｏｇｒａｐｈｙ： Ｐｒｏｔｏｃｏｌｓ， Ａｌｇｏｒｉｔｈｍｓ， ａｎｄ Ｓｏｕｒｃｅ Ｃｏｄｅ ｉｎ Ｃ，” ｓｅｃｏｎｄ ｅｄｉｔｉｏｎ， ｐｕｂｌｉｓｈｅｄ ｂｙ Ｊｏｈｎ Ｗｉｌｅｙ ＆ Ｓｏｎｓ ｗｉｔｈ ｃｏｐｙｒｉｇｈｔ １９９６）を参照されたい。尚、これは、言及により本文に含めるものとする。
【００３０】
図１は、暗号システム２０を示しており、これは、エンコーダ２２がデコーダ２４に対し通信チャンネル２６を介して結合して備えている。暗号システム２０は、ＲＳＡアルゴリズムに基づく非対称暗号式暗号（ａｓｙｍｍｅｔｒｉｃ ｃｒｙｐｔｏｇｒａｐｈｉｃ ｃｉｐｈｅｒ）を用いる。詳細には、この好ましいシステムは、ベレア−ロガウェイ暗号系（ＢｅｌｌａｒｅＲｏｇａｗａｙ ｃｒｙｐｔｏｓｙｓｔｅｍ）であり、これは、ＲＳＡ落とし戸転置ファミリ（ＲＳＡ ｔｒａｐｄｏｏｒ ｐｅｒｍｕｔａｔｉｏｎ ｆａｍｉｌｙ）を用いる。
【００３１】
一般に、暗号式暗号は、４つの素数ｐ１，ｐ２，ｑ１，ｑ２から成る秘密鍵を用いる。これら素数は、以下の関係である。
【００３２】
【数３９】
2004524548.tif 000010
【００３３】
ここで、ｒ１とｒ２は、乱数であるが、上記式におけるそれらの値が素数ｐ１，ｐ２を発生するという要件で制限されている。
【００３４】
公開鍵は、秘密鍵から生成する。この公開鍵は、３つの数ｎ，ｅ，ｇから成る。数ｅは整数（ｉｎｔｅｇｅｒ）であり、数ｎ，ｇは、以下の通り計算する。
【００３５】
【数４０】
2004524548.tif 000011
【００３６】
ここで、ｒ３は、乱数ｒ１，ｒ２とは独立に選択した乱数である。この乱数ｒ３は、乱数ｒ１，ｒ２とは異なっている可能性が高いが、但しその必要はない。数ｇは、位数（ｏｒｄｅｒ）ｑ１，ｑ２のＺｎ＊のランダムな要素である。
【００３７】
エンコーダ２２は、メッセージＭを、ｎ，ｅ，ｇから成る公開鍵を使って暗号文Ｃにエンコードする。広く述べると、暗号文Ｃは、メッセージＭと数ｘの関数であり、ここで、ｘは、Ｚｎ＊における位数ｑ１ｑ２を有する。数ｘは、以下の通り得られる。
【００３８】
【数４１】
2004524548.tif 000012
【００３９】
ここで、Ｒは、ｒ１，ｒ２とは独立に選択した乱数である。この乱数Ｒは、乱数ｒ１，ｒ２とは異なっている可能性が高いが、但し、その必要はない。暗号文Ｃは、２つのコンポーネント、すなわち、値Ｖと値Ｗを有する。値Ｖは、以下の通り、数ｘの関数である。
【００４０】
【数４２】
2004524548.tif 000013
【００４１】
値Ｗは、値ｈ１（ｘ）とメッセージＭとの関数であり、ここで、値ｈ１（ｘ）は、数ｘの一方向性関数ｈ１の結果である。１つの例として、この一方向性関数は、ＳＨＡ（安全ハッシュ・アルゴリズム：Ｓｅｃｕｒｅｄ Ｈａｓｈ Ａｌｇｏｒｉｔｈｍ）のようなハッシュ関数として実施する。１つの実現例では、値Ｗは、排他的ＯＲ関数を使って以下のように計算する。
【００４２】
【数４３】
2004524548.tif 000014
【００４３】
しかし、値ｈ１（ｘ）とＭの他の論理的組合せも、この論理演算が可逆性である限り、排他的ＯＲ関数の代わりに使用することができる。
【００４４】
エンコーダ２２は、値ＶとＷを互いにパッケージして暗号文Ｃを形成し、そしてこれを、通信チャンネル２６を介してデコーダ２４に送る。デコーダ２４は、秘密鍵を使って値Ｖから数ｘを再計算するが、この秘密鍵は、以下の通り、公開鍵にｐ１，ｐ２，ｑ１，ｑ２
を足したものである。
【００４５】
【数４４】
2004524548.tif 000015
【００４６】
一旦、数ｘを復元すると、デコーダ２４は、以下の通り、値ＷからメッセージＭを再捕捉（ｒｅｃａｐｔｕｒｅ）する。
【００４７】
【数４５】
2004524548.tif 000016
【００４８】
システム２０において利用する上記の暗号式暗号は、復号化速度が、標準のＲＳＡ暗号における復号化と比べ高速であるという利点がある。この理由は、ｘの復元において使用する演算
【００４９】
【数４６】
2004524548.tif 000017
【００５０】
が、在来のＲＳＡ暗号において使用するそれに対応する演算
【００５１】
【数４７】
2004524548.tif 000018
【００５２】
よりもかなり速いからである。
【００５３】
この向上した復号化速度は、Ｚｎ＊の部分群における指数演算に基づく落とし戸転置の新たなファミリを用いることにより実現する。上記の暗号法の暗号は、Ｚｎ＊のある一定の部分群の利点を用いる。詳細には、この暗号は、ｇが発生するＺｎ＊の部分群を利用して、数ｘを計算する。これは、Ｚｎ＊内の位数ｑ１ｑ２のものである、復号化側での計算を可能にする。
【００５４】
この暗号式暗号は、暗号化プロセスが標準ＲＳＡアルゴリズムにおける暗号化と比較して低速であるという不利な点がある。これは、この新たな技法に、暗号化側で数ｘを得るための追加の計算が含まれるからである。追加の計算のこの数は、数ｘを毎回ではなく時々計算することにより最小限にすることができる。この最適化は、以下に詳細に述べる。
【００５５】
全体としては、この暗号式暗号は、ＲＳＡ暗号とは速度がほぼ等しい。しかし、ある種の状況においては、復号化プロセスの速度を向上させることが、たとえその向上が暗号化を低速にすることを犠牲にしても、利益がある。例えば、クライアント−サーバの状況においては、復号化速度をサーバにて向上させることは、たとえクライアントにおける低速の暗号化を犠牲にすることがあっても、現実に利益がある。クライアントは、メッセージを暗号化するのに十分な時間をもち、したがってより遅い速度は気がつくほどのものとはならず、サーバにおける復号化速度の向上が十分に認識されることになる。
【００５６】
図１のアーキテクチャは、暗号機能を使用する多くの異なった環境を表している。例えば、クライアント−サーバの状況においては、エンコーダ２２とデコーダ２４とは、クライアントとサーバの両方に実装して、ＬＡＮ（ローカル・エリア・ネットワーク）、ＷＡＮ（ワイド・エリア・ネットワーク）、インターネットのようなネットワークを介する安全な通信を可能にするようにできる。別の例では、スマートカードの状況においては、エンコーダ２２は、スマートカードに実装し、デコーダ２４は、通信エージェント（例えば、コンピュータ、ＡＴＭ、キオスク、販売機、カスタム機械（ｃｕｓｔｏｍ ｍａｃｈｉｎｅ）等）に実装することができる。ここでは、チャンネル２６は、そのカードとエージェントとの間の電子インターフェースを表す。
【００５７】
説明を続けるため、暗号システム２０は、パーソナル・コンピュータ、サーバ、ワークステーション、ラップトップ等の汎用コンピュータに実装したものとして説明する。
【００５８】
図２は、汎用コンピュータ３０の１例の実現例を示している。この汎用コンピュータ３０は、処理ユニット３２、システム・メモリ３４、およびシステム・メモリ３４ないし処理ユニット３２を含む種々のシステム・コンポーネントを結合するシステム・バス３６を含む。システム・バス３６は、種々のバス・アーキテクチャのいずれかを用いたメモリ・バスまたはメモリ・コントローラ、周辺バス、およびローカル・バスを含む、数種類のバス構造のいずれでもよい。システム・メモリ３４は、リード・オンリ・メモリ（ＲＯＭ）３８、およびランダム・アクセス・メモリ（ＲＡＭ）４０を含む。基本入出力システム（ＢＩＯＳ）４２は、ＲＯＭ３８に格納する。
【００５９】
また、コンピュータ３０は、ハード・ディスクの読み取りおよび書き込みを行うハード・ディスク・ドライブ４４、リムーバブル磁気ディスク４８の読み取りおよび書き込みを行う磁気ディスク・ドライブ４６、並びにＣＤ−ＲＯＭまたはその他の光媒体のようなリムーバブル光ディスク５２の読み取りおよび書き込みを行う光ディスク・ドライブ５０も含むことができる。ハード・ディスク・ドライブ４４、磁気ディスク・ドライブ４６、および光ディスク・ドライブ５０は、ハード・ディスク・ドライブ・インターフェース５４、磁気ディスク・ドライブ・インターフェース５６、および光ディスク・ドライブ・インターフェース５８によって、それぞれシステム・バス３６に接続してある。これらのドライブおよびそれに関連するコンピュータ読み取り可能媒体は、コンピュータ読み取り可能命令、データ構造、プログラム・モジュール、およびコンピュータ３０用のその他のデータの不揮発性格納を提供する。
【００６０】
ハード・ディスク、リムーバブル磁気ディスク４８およびリムーバブル光ディスク５２を記述したが、当業者には分かるように、その他のタイプのコンピュータ読み取り可能媒体もデータを格納するのに使用することができる。他のこのような媒体には、磁気カセット、フラッシュ・メモリ・カード、ディジタル・ビデオ・ディスク、ベルヌーイ・カートリッジ、ランダム・アクセス・メモリ（ＲＡＭ）、リード・オンリ・メモリ（ＲＯＭ）等が含まれる。
【００６１】
多数のプログラム・モジュールを、ハード・ディスク、磁気ディスク４８、光ディスク５２、ＲＯＭ３８またはＲＡＭ４０上に格納することができる。これらプログラムには、オペレーティング・システム６０、１つ以上のアプリケーション・プログラム６２、その他のプログラム・モジュール６４、およびプログラム・データ６６が含まれる。
【００６２】
ユーザは、キーボード６８およびマウス７０のような入力デバイスによって、コマンドおよび情報をパーソナル・コンピュータ３０に入力することができる。他の入力デバイス（図示せず）として、マイクロフォン、ジョイスティック、ゲーム・パッド、衛星パラボラアンテナ（ｓａｔｅｌｌｉｔｅ ｄｉｓｈ）、スキャナ等を含むことができる。これらおよびその他の入力デバイスは、多くの場合、システム・バス３６に結合したシリアル・ポート・インターフェース７２を介して、処理ユニット３２に接続しているが、パラレル・ポート、ゲーム・ポートまたはユニバーサル・シリアル・バス（ＵＳＢ：ｕｎｉｖｅｒｓａｌ ｓｅｒｉａｌ ｂｕｓ）のようなその他のインターフェースによって接続することも可能である。
【００６３】
モニタ７４または別のタイプのディスプレイ・デバイスも、ビデオ・アダプタ７６のようなインターフェースを介して、システム・バス３６に接続する。このモニタに加えて、パーソナル・コンピュータは、典型的に、スピーカやプリンタのような、その他の周辺出力デバイス（図示せず）を含む。
【００６４】
サーバ・コンピュータ３０は、ネットワーク・インターフェースまたはアダプタ７８、モデム８０，またはネットワーク８２（例えば、ＬＡＮ、インターネット等）を介して通信を確立するためのその他の手段を有する。モデム８０は、内蔵型でも外付け型でもよく、シリアル・ポート・インターフェース７２を介してシステム・バス３６に接続する。
【００６５】
暗号システム２０は、コンピュータ３０内に、ソフトウェア、ファームウェア、ハードウェアとして実装することができる。例えば、エンコーダ２２とデコーダ２４は、オペレーティング・システム６０、アプリケーション・プログラム６２、またはプログラム・モジュール６４（例えば、ＤＬＬ−ダイナミック・リンク・ライブラリ）内に実装することができる。代替的には、エンコーダ２２とデコーダ２４は、ＲＯＭ３８内に実装することもできる。さらに別の実施形態では、エンコーダ２２とデコーダ２４は、処理ユニット３２内に実装することができる。
【００６６】
図３は、暗号システム２０を使用して、メッセージを暗号化および復号化する方法における例示的なステップを示す。図３に模式的に示したように、ステップ１００−１０６は、エンコーダ２２により実行し、ステップ１０８−１１４は、デコーダ２４で実行する。エンコーダ２２は、秘密鍵から得られる公開鍵（すなわち、素数ｎ，ｅ，ｇ）を知っている。これら鍵は、メモリあるいはレジスタに格納することができる。デコーダ２４は、秘密鍵（すなわち、数ｐ１，ｐ２，ｑ１，ｑ２）を知っている。
【００６７】
ステップ１００において、エンコーダ２２は、数ｘを、ｇ、すなわち位数ｑ１ｑ２のＺｎ＊のランダムな要素の関数として計算する。詳細には、エンコーダ２２は、ｘを以下の通りに計算する。
【００６８】
【数４８】
2004524548.tif 000019
【００６９】
ここで、Ｒは、乱数である。
【００７０】
ステップ１０２において、エンコーダは、メッセージＭをエンコードして暗号文Ｃを生成する。このエンコーディングは、値Ｖと値Ｗの発生を含み、ここで、
【００７１】
【数４９】
2004524548.tif 000020
【００７２】
である。値ｈ１（ｘ）は、数ｘの第１のハッシュ関数ｈ１の結果である。暗号文Ｃは、値Ｖと値Ｗから成る。
【００７３】
ステップ１０４において、エンコーダ２２は、別のハッシュ値ｈ２（ｘ）を計算し、これは、数ｘとメッセージＭの第２のハッシュ関数ｈ２の結果である。デコーダ２４は、このハッシュ値を使って、メッセージＭが変更されているか、あるいはエンコーダとデコーダとの間のルートにおいて危険にさらされている（ｃｏｍｐｒｏｍｉｓｅ）かどうかチェックする。ステップ１０６において、エンコーダ２２は、暗号文Ｃ、
すなわち
【００７４】
【数５０】
2004524548.tif 000021
【００７５】
と、第２ハッシュ値ｈ２（ｘ，Ｍ）を、通信チャンネル２６を介してデコーダ２４に送信する。
【００７６】
ステップ１０８において、デコーダ２４は、暗号文Ｃと第２ハッシュ値ｈ２（ｘ，Ｍ）を受ける。ステップ１１０において、デコーダ２４は、次に、以下の通り、暗号文Ｃの値Ｖコンポーネント（すなわち、Ｖ＝ｘｅ）から数ｘを再計算する。
【００７７】
【数５１】
2004524548.tif 000022
【００７８】
一旦、数ｘを復元すると、デコーダ２４は、エンコーダ２２が用いたのと同じ第１ハッシュ関数ｈ１を使って、ハッシュ値ｈ１（ｘ）を計算する。ステップ１１２において、デコーダ２４は、以下のように、暗号文Ｃの値ＷコンポーネントからメッセージＭを復元する。
【００７９】
【数５２】
2004524548.tif 000023
【００８０】
ステップ１１４において、デコーダ２４は、この復元した数ｘと復元したメッセージＭを取り、そしてエンコーダが用いたのと同じ第２ハッシュ関数ｈ２を使ってテスト・ハッシュ値ｈ２’（ｘ，Ｍ）を計算する。このテスト・ハッシュ値ｈ２（ｘ，Ｍ）が、エンコーダ２２から受けたハッシュ値ｈ２（ｘ，Ｍ）と等しい場合、デコーダ２４に対し、メッセージＭが変更されていなかったことを保証する。
【００８１】
上記の暗号化／復号化プロセスは、以下の擬似コードにおいて表すことができる。鍵計算は、この暗号化／復号化プロセスの前に一回実行して、鍵値を確立することができる。これら鍵は、必要に応じて更新することができる。
【００８２】
鍵計算
【００８３】
【表１】
2004524548.tif 000024
【００８４】
暗号化
【００８５】
【表２】
2004524548.tif 000025
【００８６】
復号化
【００８７】
【表３】
2004524548.tif 000026
【００８８】
１つの実現例では、整数“ｅ”は、２にセットし、これにより、落とし戸転置の新ファミリがＺｎ＊の部分群における平方に基づくようにする。
【００８９】
この暗号技法の不利な点の１つは、暗号化プロセスが、在来のＲＳＡ暗号化よりも遅いことであり、これは、エンコーダが、数ｘを、Ｚｎ＊のランダムな要素であるｇの関数として計算するからである。この数ｘを得ることは、在来のＲＳＡ暗号には存在しない追加の計算を必要とする。
【００９０】
この暗号化フェーズの速度を向上させる１つの方法は、数ｘを一回計算し、そしてこの古い数ｘを使用して次の暗号化のための新たな数ｘを発生することである。特に、この改善は、各新たな暗号化に対するｇＲ ｍｏｄ ｎを再計算するよりも計算上より激しくない方法で、各新たな暗号化に対し数ｘを変化させることを含む。古い数ｘから新たな数ｘを発生することに対する１つのアプローチは、以下の通りである。
【００９１】
【数５３】
2004524548.tif 000027
【００９２】
ここで、“ｋ ｅｘｐ（ｉ）”はｋｉとして表す。
【００９３】
エンコーダは、数ｘ（すなわち、ｘ＝ｇＲ ｍｏｄ ｎ）を計算し、そしてこの数ｘを、後での使用のため、メモリまたはレジスタに格納する。後続の各暗号化に対し、エンコーダは、ｘｋ ｅｘｐ（ｉ）を計算しそして値“ｉ”を選ぶことによりｘを変化させ、これにより、ｘが変化したときに値Ｖが同じままとなるようにする。次に、エンコーダは、その値ｉを値Ｖと共に、値ｘの復元における使用のためデコーダに送る。
【００９４】
値ｘをいくつかの暗号化に渡って償却（ａｍｏｒｔｉｚｅ）するこのプロセスは、各エンコーディング手順の間における多くの計算を減らす。この暗号システムは、エンコーダに対する順方向機密（ｆｏｒｗａｒｄｓｅｃｒｅｃｙ）を保護することにより、数ｘが漏れた場合に、過去のメッセージが危険にさらされないようにするが、将来のメッセージが危険にさらされことがある。エンコーダは、数ｘを、任意のインターバルであるいは必要と考える任意の時点で完全に再計算することもできる。
【００９５】
また、上記の暗号システムは、バッチＲＳＡ（ＲＳＡの周知の変形例）における復号化速度を向上させるのに使用することができる。この暗号システムは、上述のものと同様であるが、但し、素数ｐ１，ｐ２を得るのに使用する乱数ｒ１，ｒ２を、第１のｂ素数によって割り切れないようにさらに制限する点で異なっており、ここで、ｂは復号化バッチ・サイズである。
【００９６】
このバッチＲＳＡに対しては、数ｘはやはり以下のように得られる。
【００９７】
【数５４】
2004524548.tif 000028
【００９８】
値Ｖは、以下のように計算する。
【００９９】
【数５５】
2004524548.tif 000029
【０１００】
ここで、ｅ＝（ｉ＋１）番目の奇数の素数であり、ｉはＺｂからである。
【０１０１】
復号化側では、値ｘは、次のように復元する。
【０１０２】
【数５６】
2004524548.tif 000030
【０１０３】
バッチＲＳＡの上記変更例は、より迅速な復号化を可能にするが、それは、バッチ逆演算（ｂａｔｃｈ ｉｎｖｅｒｓｅ ｏｐｅｒａｔｉｏｎ）の間において、それら指数は、モジュロｑ１ｑ２に還元できるからである。
【０１０４】
以上、本発明について、構造上および／または方法的ステップに特有の用語で説明したが、添付の特許請求の範囲に定めた本発明は、記述したこの特定の特徴またはステップに必ずしも限定される必要がないことは理解されるべきである。これら特定の特徴およびステップは、特許を請求する発明を実施する好ましい形態として開示したものである。
【図面の簡単な説明】
【図１】
図１は、暗号システムのブロック図。
【図２】
図２は、この暗号システムを実装したコンピュータ・システムのブロック図。
【図３】
メッセージを暗号化および復号化する方法における各ステップを示すフロー図。
【図１】
2004524548.tif 000062
【図２】
2004524548.tif 000063
【図３】
2004524548.tif 000064
【国際公開パンフレット】
2004524548.tif 000065
2004524548.tif 000066
2004524548.tif 000067
2004524548.tif 000068
2004524548.tif 000069
2004524548.tif 000070
2004524548.tif 000071
2004524548.tif 000072
2004524548.tif 000073
2004524548.tif 000074
2004524548.tif 000075
2004524548.tif 000076
2004524548.tif 000077
2004524548.tif 000078
2004524548.tif 000079
2004524548.tif 000080
2004524548.tif 000081
2004524548.tif 000082
2004524548.tif 000083
2004524548.tif 000084
2004524548.tif 000085
2004524548.tif 000086
2004524548.tif 000087
2004524548.tif 000088
2004524548.tif 000089
2004524548.tif 000090
2004524548.tif 000091
2004524548.tif 000092
2004524548.tif 000093
2004524548.tif 000094
2004524548.tif 000095
2004524548.tif 000096
【国際公開パンフレット（コレクトバージョン）】
2004524548.tif 000097
2004524548.tif 000098
【国際公開パンフレット（コレクトバージョン）】
2004524548.tif 000099
2004524548.tif 000100
2004524548.tif 000101
2004524548.tif 000102
2004524548.tif 000103
2004524548.tif 000104
2004524548.tif 000105
2004524548.tif 000106
2004524548.tif 000107
2004524548.tif 000108
2004524548.tif 000109
2004524548.tif 000110
2004524548.tif 000111
2004524548.tif 000112
2004524548.tif 000113
2004524548.tif 000114
2004524548.tif 000115
2004524548.tif 000116
2004524548.tif 000117
2004524548.tif 000118
2004524548.tif 000119
2004524548.tif 000120
2004524548.tif 000121
2004524548.tif 000122
2004524548.tif 000123
2004524548.tif 000124
2004524548.tif 000125
2004524548.tif 000126
2004524548.tif 000127
2004524548.tif 000128
2004524548.tif 000129
2004524548.tif 000130
【手続補正書】
【提出日】平成11年10月14日(1999.10.14)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】特許請求の範囲
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
メッセージをネットワークを介して第１と第２の計算ユニット間で送るシステムにおいて、方法が、
（ａ）前記第１計算ユニットにおいてメッセージＭを暗号文Ｃに暗号化するステップであって、前記暗号文Ｃが、以下の通り値Ｖと値Ｗを含む、前記の暗号化ステップであって、
（１）値Ｖが、数ｘの関数Ｖ＝ｘｅであり、ここで、ｅは整数、ｘは以下の通りであり、
【数１】
2004524548.tif 000131
ここで、
（ｉ）ｎは数ｎ＝ｐ１ｐ２であり、ここで、ｐ１，ｐ２は、素数であって、ｐ１＝ｒ１ｑ１＋１，ｐ２＝ｒ２ｑ２＋１であり、ここで、ｒ１，ｒ２は乱数、ｑ１，ｑ２は素数であり、
（ｉｉ）Ｒは、前記乱数ｒ１，ｒ２とは独立に選択した乱数であり、
（ｉｉｉ）ｇは、
【数２】
2004524548.tif 000132
であり、ここで、ｒ３は、前記乱数ｒ１，ｒ２，Ｒとは独立に選択した乱数であり、
（２）値Ｗは、値ｈ（ｘ）と前記メッセージＭの関数であり、前記値ｈ（ｘ）は、前記数ｘの一方向性関数の結果である、
前記の暗号化ステップと、
（ｂ）前記暗号文Ｃを前記第１計算ユニットから前記第２計算ユニットに送出するステップと、
（ｃ）前記暗号文Ｃを前記第２計算ユニットにおいて復号化して前記メッセージＭを再現する復号化ステップであって、ここでＭは、前記値Ｗと前記値ｈ（ｘ）の関数であり、ｘは、
【数３】
2004524548.tif 000133
として得る、前記の復号化ステップと、
から成る方法。
【請求項２】
請求項１記載の方法において、前記暗号化ステップは、値Ｗを、
【数４】
2004524548.tif 000134
として得るステップから成ること、を特徴とする方法。
【請求項３】
請求項２記載の方法において、前記復号化ステップは、前記メッセージＭを、
【数５】
2004524548.tif 000135
として得るステップから成ること、を特徴とする方法。
【請求項４】
請求項１記載の方法において、前記整数ｅは２に等しいこと、を特徴とする方法。
【請求項５】
請求項１記載の方法において、
前記暗号化ステップは、前記数ｘと前記メッセージＭのハッシュ関数ｈから、ハッシュ値ｈ（ｘ，Ｍ）を計算するステップから成り、
前記送出ステップは、前記第１計算ユニットから前記第２計算ユニットへ前記ハッシュ値ｈ（ｘ，Ｍ）を前記暗号文Ｃと共に送るステップから成り、
前記復号化ステップは、前記得た数ｘと前記再現したメッセージＭのハッシュ関数ｈから、テスト・ハッシュ値ｈ’（ｘ，Ｍ）を計算し、そして前記第１計算ユニットから受けた前記ハッシュ値ｈ（ｘ，Ｍ）を前記テスト・ハッシュ値ｈ’（ｘ，Ｍ）と比較して、前記メッセージＭが変更されているかどうか検証するステップから成ること、
を特徴とする方法。
【請求項６】
請求項１記載の方法において、前記暗号化ステップは、
前記数ｘを記憶するステップと、
古い前記数ｘに基づいて新たな数ｘ’を発生するステップと、
前記新たな数ｘ’を次にメッセージの暗号化のために使用するステップと、
から成ること、を特徴とする方法。
【請求項７】
メッセージＭを暗号文Ｃに暗号化するコンピュータ実施の方法であって、
ｎは、形態ｎ＝ｐ１ｐ２にある数であり、ここで、ｐ１，ｐ２は、素数であり、
ｐ１＝ｒ１ｑ１＋１，ｐ２＝ｒ２ｑ２＋１であり、ここで、ｒ１，ｒ２は乱数、ｑ１，ｑ２は素数であり、
ｇは、
【数６】
2004524548.tif 000136
の形態にある数であり、ここで、ｒ３は、前記乱数ｒ１，ｒ２とは独立に選択した乱数であり、
前記コンピュータ実施の方法が、
数ｘ＝ｇＲ ｍｏｄ ｎを計算するステップであって、ここで、Ｒは、前記乱数ｒ１，ｒ２，ｒ３とは独立に選択した乱数である、前記の計算ステップと、
前記数ｘを一方向性関数ｈにしたがって変換して値ｈ（ｘ）を発生するステップと、
前記メッセージＭを前記値ｈ（ｘ）の関数にしたがってエンコードするステップと、
から成る暗号化方法。
【請求項８】
請求項７記載の暗号化方法において、前記エンコードするステップは、
【数７】
2004524548.tif 000137
を計算するステップから成ること、を特徴とする暗号化方法。
【請求項９】
請求項７記載の暗号化方法であって、さらに、前記数ｘと前記メッセージＭのハッシュ関数ｈから、ハッシュ値ｈ（ｘ，Ｍ）を計算するステップを含むこと、を特徴とする暗号化方法。
【請求項１０】
請求項７記載の暗号化方法であって、さらに、
前記数ｘを記憶するステップと、
古い前記数ｘに基づいて新たな数ｘ’を発生するステップと、
前記新たな数ｘ’を次にメッセージの暗号化のために使用するステップと、
を含むこと、を特徴とする暗号化方法。
【請求項１１】
暗号文Ｃを復号化してメッセージＭを再現するコンピュータ実施の方法であって、
ｎは、形態ｎ＝ｐ１ｐ２にある数であり、ここで、ｐ１，ｐ２は、素数であり、
ｐ１＝ｒ１ｑ１＋１，ｐ２＝ｒ２ｑ２＋１であり、ここで、ｒ１，ｒ２は乱数、ｑ１，ｑ２は素数であり、
ｇは、
【数８】
2004524548.tif 000138
の形態にある数であり、ここで、ｒ３は、前記乱数ｒ１，ｒ２とは独立に選択した乱数であり、
ｘは、ｘ＝ｇＲ ｍｏｄ ｎの形態にある数であり、ここで、Ｒは、前記乱数ｒ１，ｒ２，ｒ３とは独立に選択した乱数であり、
ｅは整数であり、
ＶはＶ＝ｘｅの形態にある値であり、
前記コンピュータ実施の方法が、
前記値Ｖから前記数ｘを再現するステップであって、ここで、
【数９】
2004524548.tif 000139
である、前記の再現ステップと、
前記数ｘを一方向性関数ｈにしたがって変換して値ｈ（ｘ）を発生するステップと、
前記暗号文Ｃを前記値ｈ（ｘ）の関数にしたがってデコードして、前記メッセージＭを再現するステップと、
から成る復号化方法。
【請求項１２】
請求項１１記載の復号化方法において、前記デコードするステップは、
【数１０】
2004524548.tif 000140
を計算するステップから成ること、を特徴とする復号化方法。
【請求項１３】
請求項１１記載の復号化方法であって、さらに、前記数ｘと前記再捕捉したメッセージＭとのハッシュ関数ｈから、ハッシュ値ｈ（ｘ，Ｍ）を計算するステップを含むこと、を特徴とする復号化方法。
【請求項１４】
メッセージをネットワークを介して第１と第２の計算ユニット間で送るシステムにおいて、方法が、
（ａ）前記第１計算ユニットにおいてメッセージＭを暗号文Ｃに暗号化するステップであって、前記暗号文Ｃが、以下の通り値Ｖと値Ｗを含む、前記の暗号化ステップであって、
（１）前記値Ｖが、数ｘの関数Ｖ＝ｘｅであり、ここで、ｅは、最初のｂ個の奇数の素数から選択した整数であり、ｘは以下の通りであり、
【数１１】
2004524548.tif 000141
ここで、
（ｉ）ｎは数ｎ＝ｐ１ｐ２であり、ここで、ｐ１，ｐ２は、素数であって、ｐ１＝ｒ１ｑ１＋１，ｐ２＝ｒ２ｑ２＋１であり、ここで、ｑ１，ｑ２は素数、ｒ１，ｒ２は、前記最初のｂ個の奇数素数で割り切れない乱数であり、
（ｉｉ）Ｒは、前記乱数ｒ１，ｒ２とは独立に選択した乱数であり、
（ｉｉｉ）ｇは、
【数１２】
2004524548.tif 000142
の形態にある数であり、ここで、ｒ３は、前記乱数ｒ１，ｒ２，Ｒとは独立に選択した乱数であり、
（２）前記値Ｗは、値ｈ（ｘ）と前記メッセージＭの関数であり、前記値ｈ（ｘ）は、前記数ｘの一方向性関数の結果である、
前記の暗号化ステップと、
（ｂ）前記暗号文Ｃを前記第１計算ユニットから前記第２計算ユニットに送出するステップと、
（ｃ）前記暗号文Ｃを前記第２計算ユニットにおいて復号化して前記メッセージＭを再現する復号化ステップであって、ここでＭは、前記値Ｗと前記値ｈ（ｘ）の関数であり、ｘは、
【数１３】
2004524548.tif 000143
として得る、前記の復号化ステップと、
から成る方法。
【請求項１５】
メッセージを通信チャンネルを介して送るシステムであって、
メッセージＭを暗号文Ｃに変換し、そして該暗号文Ｃを前記通信チャンネルを介して送信するエンコーダであって、前記暗号文Ｃが、以下の通り値Ｖと値Ｗを含む、前記のエンコーダであって、
（１）前記値Ｖが、数ｘの関数Ｖ＝ｘｅであり、ここで、ｅは整数、ｘは以下の通りであり、
【数１４】
2004524548.tif 000144
ここで
（ｉ）ｎは数ｎ＝ｐ１ｐ２であり、ここで、ｐ１，ｐ２は、素数であって、ｐ１＝ｒ１ｑ１＋１，ｐ２＝ｒ２ｑ２＋１であり、ここで、ｒ１，ｒ２は乱数、ｑ１，ｑ２は素数であり、
（ｉｉ）Ｒは、前記乱数ｒ１，ｒ２とは独立に選択した乱数であり、
（ｉｉｉ）ｇは、
【数１５】
2004524548.tif 000145
であり、ここで、ｒ３は、前記乱数ｒ１，ｒ２，Ｒとは独立に選択した乱数であり、
（２）前記値Ｗは、値ｈ（ｘ）と前記メッセージＭの関数であり、前記値ｈ（ｘ）は、前記数ｘの一方向性関数の結果である、
前記のエンコーダと、
前記暗号文Ｃと前記値Ｖを前記通信チャンネルを介して受け、そして前記暗号文Ｃを前記メッセージＭに変換し戻すように結合したデコーダであって、ここでＭは、前記値Ｗと前記値ｈ（ｘ）の関数であり、ｘは、
【数１６】
2004524548.tif 000146
として得る、前記のデコーダと、
から成るシステム。
【請求項１６】
請求項１５記載のシステムにおいて、前記エンコーダは、前記値Ｗを、
【数１７】
2004524548.tif 000147
として得ること、を特徴とするシステム。
【請求項１７】
請求項１５記載のシステムにおいて、前記デコーダは、前記メッセージＭを、
【数１８】
2004524548.tif 000148
として得ること、を特徴とするシステム。
【請求項１８】
請求項１５記載のシステムにおいて、前記整数ｅは２に等しいこと、を特徴とするシステム。
【請求項１９】
請求項１５記載のシステムにおいて、
前記エンコーダは、前記数ｘと前記メッセージＭのハッシュ関数ｈから、ハッシュ値ｈ（ｘ，Ｍ）を計算し、そして前記ハッシュ値ｈ（ｘ，Ｍ）を前記暗号文Ｃと共に送信し、
前記デコーダは、前記得た数ｘと前記再現したメッセージＭのハッシュ関数ｈから、テスト・ハッシュ値ｈ’（ｘ，Ｍ）を計算し、そして前記第１計算ユニットから受けた前記ハッシュ値ｈ（ｘ，Ｍ）を前記テスト・ハッシュ値ｈ’（ｘ，Ｍ）と比較して、前記メッセージＭが変更されているかどうか検証すること、
を特徴とするシステム。
【請求項２０】
請求項１５記載のシステムにおいて、前記エンコーダは、前記数ｘを記憶し、古い前記数ｘに基づいて新たな数ｘ’を発生し、前記新たな数ｘ’を使用して前記値Ｖと前記値Ｗを計算すること、を特徴とするシステム。
【請求項２１】
暗号システムのためのエンコーダであって、
ｎは、形態ｎ＝ｐ１ｐ２にある数であり、ここで、ｐ１，ｐ２は、素数であり、
ｐ１＝ｒ１ｑ１＋１，ｐ２＝ｒ２ｑ２＋１であり、ここで、ｒ１，ｒ２は乱数、ｑ１，ｑ２は素数であり、
ｇは、
【数１９】
2004524548.tif 000149
の形態にある数であり、ここで、ｒ３は、前記乱数ｒ１，ｒ２とは独立に選択した乱数であり、
前記エンコーダが、
数ｘ＝ｇＲ ｍｏｄ ｎを計算する手段であって、ここで、Ｒは、前記乱数ｒ１，ｒ２，ｒ３とは独立に選択した乱数である、前記の手段と、
前記数ｘを一方向性関数ｈにしたがって変換して値ｈ（ｘ）を発生する手段と、
メッセージＭを前記値ｈ（ｘ）の関数にしたがってエンコードする手段と、
から成るエンコーダ。
【請求項２２】
請求項２１記載のエンコーダにおいて、前記エンコードする手段は、前記メッセージＭを、
【数２０】
2004524548.tif 000150
の関数にしたがってエンコードすること、を特徴とするエンコーダ。
【請求項２３】
請求項２１記載のエンコーダであって、さらに、
前記数ｘを記憶する手段と、
古い前記数ｘに基づいて新たな数ｘ’を発生する手段と、
前記新たな数ｘ’を使用して前記値ｈ（ｘ）を得る手段と、
を含むこと、を特徴とするエンコーダ。
【請求項２４】
暗号システムのためのデコーダであって、
ｎは、形態ｎ＝ｐ１ｐ２にある数であり、ここで、ｐ１，ｐ２は、素数であり、
ｐ１＝ｒ１ｑ１＋１，ｐ２＝ｒ２ｑ２＋１であり、ここで、ｒ１，ｒ２は乱数、ｑ１，ｑ２は素数であり、
ｇは、
【数２１】
2004524548.tif 000151
の形態にある数であり、ここで、ｒ３は、前記乱数ｒ１，ｒ２とは独立に選択した乱数であり、
ｘは、ｘ＝ｇＲ ｍｏｄ ｎの形態にある数であり、ここで、Ｒは、前記乱数ｒ１，ｒ２，ｒ３とは独立に選択した乱数であり、
ｅは整数であり、
ＶはＶ＝ｘｅの形態にある値であり、
Ｗは、メッセージＭと値ｈ（ｘ）の関数から得た値であり、ここでｈ（ｘ）は、一方向性関数ｈの結果であり、
前記デコーダが、
前記値Ｖと値Ｗを受ける手段と、
前記値Ｖから前記数ｘを復元する手段であって、ここで、
【数２２】
2004524548.tif 000152
である、前記の復元手段と、
前記数ｘを一方向性関数ｈにしたがって変換して前記値ｈ（ｘ）を発生する手段と、
前記値Ｗを前記値ｈ（ｘ）の関数にしたがってデコードして、前記メッセージＭを再捕捉する手段と、
から成るデコーダ。
【請求項２５】
請求項２４記載のデコーダにおいて、前記デコードする手段は、関数
【数２３】
2004524548.tif 000153
を計算して、前記メッセージＭを再捕捉すること、を特徴とするデコーダ。
【請求項２６】
請求項２４記載のデコーダであって、さらに、前記数ｘと前記再捕捉したメッセージＭとのハッシュ関数ｈから、ハッシュ値ｈ（ｘ，Ｍ）を計算する手段を含むこと、を特徴とするデコーダ。
【請求項２７】
メッセージを通信チャンネルを介して送るシステムであって、
メッセージＭを暗号文Ｃに変換し、そして前記暗号文Ｃを前記通信チャンネルを介して送信するエンコーダであって、前記暗号文Ｃが、以下の通り値Ｖと値Ｗを含む、前記のエンコーダであって、
（１）値Ｖが、数ｘの関数Ｖ＝ｘｅであり、ここで、ｅは、最初のｂ個の奇数の素数から選択した整数であり、ｘは以下の通りであり、
【数２４】
2004524548.tif 000154
ここで、
（ｉ）ｎは数ｎ＝ｐ１ｐ２であり、ここで、ｐ１，ｐ２は、素数であって、ｐ１＝ｒ１ｑ１＋１，ｐ２＝ｒ２ｑ２＋１であり、ここで、ｑ１，ｑ２は素数、ｒ１，ｒ２は、前記最初のｂ個の奇数素数で割り切れない乱数であり、
（ｉｉ）Ｒは、前記乱数ｒ１，ｒ２とは独立に選択した乱数であり、
（ｉｉｉ）ｇは、
【数２５】
2004524548.tif 000155
の形態にある数であり、ここで、ｒ３は、前記乱数ｒ１，ｒ２，Ｒとは独立に選択した乱数であり、
（２）値Ｗは、値ｈ（ｘ）と前記メッセージＭの関数であり、前記値ｈ（ｘ）は、前記数ｘの一方向性関数の結果である、
前記のエンコーダと、
前記暗号文Ｃと前記値Ｖを前記通信チャンネルを介して受け、そして前記暗号文Ｃを前記メッセージＭに変換し戻すように結合したデコーダであって、ここでＭは、前記値Ｗと前記値ｈ（ｘ）の関数であり、ｘは、
【数２６】
2004524548.tif 000156
として得る、前記のデコーダと、
から成るシステム。
【請求項２８】
コンピュータに、メッセージＭを暗号文Ｃに暗号化させるコンピュータ実行可能の命令を有するコンピュータ読み取り可能媒体であって、
ｎは、形態ｎ＝ｐ１ｐ２にある数であり、ここで、ｐ１，ｐ２は、素数であり、
ｐ１＝ｒ１ｑ１＋１，ｐ２＝ｒ２ｑ２＋１であり、ここで、ｒ１，ｒ２は乱数、ｑ１，ｑ２は素数であり、
ｇは、
【数２７】
2004524548.tif 000157
の形態にある数であり、ここで、ｒ３は、前記乱数ｒ１，ｒ２とは独立に選択した乱数であり、
前記コンピュータ読み取り可能媒体が、
コンピュータに、数ｘ＝ｇＲ ｍｏｄ ｎを計算させるコンピュータ実行可能の命令であって、ここで、Ｒは、前記乱数ｒ１，ｒ２，ｒ３とは独立に選択した乱数である、前記のコンピュータ実行可能の命令と、
コンピュータに、前記数ｘを一方向性関数ｈにしたがって変換して値ｈ（ｘ）を発生させるコンピュータ実行可能の命令と、
コンピュータに、前記メッセージＭを前記値ｈ（ｘ）の関数にしたがってエンコードさせるコンピュータ実行可能の命令と、
から成るコンピュータ読み取り可能媒体。
【請求項２９】
請求項２８記載のコンピュータ読み取り可能媒体において、さらに、コンピュータに、前記メッセージＭを、関数
【数２８】
2004524548.tif 000158
にしたがってエンコードさせるコンピュータ実行可能の命令を含むこと、を特徴とするコンピュータ読み取り可能媒体。
【請求項３０】
請求項２８記載のコンピュータ読み取り可能媒体であって、さらに、コンピュータに、前記数ｘを記憶させ、古い前記数ｘに基づいて新たな数ｘ’を発生させ、前記新たな数ｘ’を使用して前記値ｈ（ｘ）を得させる、コンピュータ実行可能の命令を含むこと、を特徴とするコンピュータ読み取り可能媒体。
【請求項３１】
コンピュータに、暗号文Ｃを復号化してメッセージＭを復元させるコンピュータ実行可能の命令を有するコンピュータ読み取り可能媒体であって、
ｎは、形態ｎ＝ｐ１ｐ２にある数であり、ここで、ｐ１，ｐ２は、素数であり、
ｐ１＝ｒ１ｑ１＋１，ｐ２＝ｒ２ｑ２＋１であり、ここで、ｒ１，ｒ２は乱数、ｑ１，ｑ２は素数であり、
ｇは、
【数２９】
2004524548.tif 000159
の形態にある数であり、ここで、ｒ３は、前記乱数ｒ１，ｒ２とは独立に選択した乱数であり、
ｘは、ｘ＝ｇＲ ｍｏｄ ｎの形態にある数であり、ここで、Ｒは、前記乱数ｒ１，ｒ２，ｒ３とは独立に選択した乱数であり、
ｅは整数であり、
ＶはＶ＝ｘｅの形態にある値であり、
前記コンピュータ読み取り可能媒体が、
コンピュータに、前記値Ｖから前記数ｘを復元させるコンピュータ実行可能の命令であって、ここで、
【数３０】
2004524548.tif 000160
である、前記のコンピュータ実行可能の命令と、
コンピュータに、前記数ｘを一方向性関数ｈにしたがって変換してｈ（ｘ）を発生させるコンピュータ実行可能の命令と、
コンピュータに、前記暗号文Ｃを前記値ｈ（ｘ）の関数にしたがってデコードして前記メッセージＭを再捕捉させる、コンピュータ実行可能の命令と、
から成るコンピュータ読み取り可能媒体。
【請求項３２】
請求項３１記載のコンピュータ読み取り可能媒体であって、コンピュータに、前記暗号文Ｃを前記関数
【数３１】
2004524548.tif 000161
にしたがってデコードさせるコンピュータ実行可能の命令を含むこと、を特徴とするコンピュータ読み取り可能媒体。
【請求項３３】
請求項３１記載のコンピュータ読み取り可能媒体であって、さらに、コンピュータに、前記数ｘと前記再捕捉したメッセージＭとのハッシュ関数ｈから、ハッシュ値ｈ（ｘ，Ｍ）を計算させる、コンピュータ実行可能の命令を含むこと、を特徴とするコンピュータ読み取り可能媒体。
【国際調査報告】
2004524548.tif 000162
2004524548.tif 000163
2004524548.tif 000164