(57)【特許請求の範囲】
【請求項１】
ＲＳＡ暗号システムのための鍵ペア決定装置により、第１数（ｅ）および第２数（ｄ）を含む一組の数を決定する方法であって、上記第２数（ｄ）は、第１数（ｅ）の係数（Ｎ）に関する逆数であり、上記係数（Ｎ）は、第１素数（ｐ）と第２素数（ｑ）との積に等しくなっている方法において、
上記鍵ペア決定装置に設けられている第１手段により、上記第１数（ｅ）を選択するステップと、
上記鍵ペア決定装置に設けられている第２手段により、上記第１手段から第１数（ｅ）を受信し、上記第２数（ｄ）のために、第１サブ係数に対する上記第１数（ｅ）の逆数としての第１サブ数（ｄp）を演算するステップであって、上記第１サブ係数は上記第１素数（ｐ）引く１を上記第１素数（ｐ）引く１と上記第２素数（ｑ）引く１との最大公約数によって割り算したものに等しいステップと、
上記鍵ペア決定装置に設けられている第３手段により、上記第１手段から第１数（ｅ）を受信し、上記第２数（ｄ）のために、第２サブ係数に対する上記第１数（ｅ）の逆数としての第２サブ数（ｄq）を演算するステップであって、上記第２サブ係数は上記第２素数（ｑ）引く１に等しく、かつ上記第１サブ係数と第２サブ係数とは互いに素であるステップと、
上記鍵ペア決定装置に設けられている第４手段により、上記第２手段から上記第１サブ数（ｄp）を受信する一方、上記第３手段から第２サブ数（ｄq）を受信し、これらの第１サブ数（ｄp）および上記第２サブ数（ｄq）を使用し、中国人の剰余定理を用いて第２数（ｄ）を決定するステップとを含む方法。
【請求項２】
上記第１数（ｅ）および上記第２数（ｄ）が鍵ペアであり、１つの鍵（ｅ）が、公開鍵の役割を果たしており、第２鍵（ｄ）が、ＲＳＡ暗号システムの秘密鍵の役割を果たしている請求項１に記載の方法。
【請求項３】
上記第２手段による上記第１サブ数（ｄp）の演算ステップ、および上記第３手段による上記第２サブ数（ｄq）の演算ステップのそれぞれが、拡張されたユークリッドのアルゴリズムを利用している請求項１または２に記載の方法。
【請求項４】
上記第４手段による上記決定ステップが、以下の数式：
ｘp ＝（ｄp−ｄq ）×［（ｑ−１）-1ｍｏｄ（ｐ−１）／ｇｇＴ（ｐ−１，ｑ−１）］ｍｏｄ（ｐ−１）／ｇｇＴ（ｐ−１，ｑ−１）
ｄ＝ｄq＋ｘp×（ｑ−１）
ｄp は、第１サブ数
ｄq は、第２サブ数
ｑは、第１素数
ｐは、第２素数
ｇｇＴは、「最大公約数」の算法を指定する
ｍｏｄは、係数算法を指定する
ｘp は、補助数量である
を利用している請求項１〜３のいずれか１項に記載の方法。
【請求項５】
ＲＳＡ暗号システムのための鍵生成装置により、ＲＳＡ暗号システムに用いる公開鍵および秘密鍵を生成する方法であって、
上記鍵生成装置に設けられている第５手段により、２つの素数（ｐ，ｑ）を選択するステップと、
上記鍵生成装置に設けられている第６手段により、上記第５手段から２つの素数（ｐ，ｑ）を受信するとともに、これらの素数の積（Ｎ）を演算するステップと、
請求項１に記載の鍵ペア決定装置により、上記第５手段から２つの素数（ｐ，ｑ）を受信するとともに、一組の数を決定するステップと、
上記鍵生成装置に設けられている第７手段により、上記鍵ペア決定装置から上記第１数（ｅ）を受信し、上記素数の積と上記一組の数の第１数とを、公開鍵として出力するステップと、
上記鍵生成装置に設けられている第８手段により、上記鍵ペア決定装置から上記第２数（ｄ）を受信し、上記第２数（ｄ）を、秘密鍵として格納するステップとを含む方法。
【発明の詳細な説明】
本発明は、ＲＳＡ暗号アルゴリズム、特に、ＲＳＡ鍵の生成に関するものである。発明者であるR. Rivest, A. ShamirおよびL.Adlemanに因んで名付けられたＲＳＡ暗号システムは、最も普及している鍵暗号化システムの１つである。これは、安全性を確保するためにも、デジタル署名を生成するためにも使用できる。その安全性は、いわゆる、整数因数分解問題を、アルゴリズムに基づいて効果的な方法で解くことができないということを基礎としている。
【０００１】
ＲＳＡ暗号システムについてより詳しく説明する前に、暗号化のいくつかの基本的な用語について、まず概要を説明する。秘密鍵暗号化システムとも称される対称暗号化システムと公開鍵暗号化システムとは、一般的に区別されている。
【０００２】
対称鍵による暗号化を用いた２者による通信システムを、次のように説明できる。第１者は、その暗号化鍵を、安全なチャンネルを介して第２者に通信する。次に、第１者は、その鍵を用いて秘密のメッセージを暗号化し、暗号化されたメッセージを、公開または安全ではないチャンネルを介して第２者に伝送する。次に、第２者は、暗号化されたメッセージを、安全なチャンネルを介して第２者へ通信された対称鍵を用いて復号する。このような暗号化システムの本質的な問題は、秘密鍵を交換する、すなわち、安全なチャンネルを見出す効果的な方法を提供することである。
【０００３】
これに対して、非対称暗号化は、次のように行われる。秘密メッセージを受信しようとする者は、その公開鍵を他者、すなわち、その人からの秘密メッセージを受信したいと思う者へ通信する。公開鍵は、安全ではないチャンネル、すなわち、「公開」チャンネルを介して通信される。
【０００４】
秘密メッセージを送信しようとする者は、他者の公開鍵を受け取り、この公開鍵を用いてメッセージを暗号化し、暗号化されたメッセージを、安全ではないチャンネル、つまり、公開チャンネルを介して、公開鍵を送信した者へ再び伝送する。公開鍵を生成した者だけが、暗号化されたメッセージを復号するための秘密鍵を使用できる。公開鍵を使用してそのメッセージを暗号化した者も、メッセージを復号できない。この構想の長所は、安全なチャンネル、すなわち、鍵の秘密交換が、２者の間に不要なことである。メッセージを暗号化した者は、メッセージ受信者の秘密鍵を知る必要はないし、知ってはならない。
【０００５】
非対称符号化構想または公開鍵符号化構想の物理的なアナログ図式を次のように概要説明できる。組み合わせ錠により施錠される蓋付きの金属製の箱を例として考える。組み合わせは、暗号化されたメッセージを受け取ろうとする者だけが知っている。鍵は開いたままで、一般の人々がこれを使用できる場合、秘密メッセージを通信しようとする者は、そのメッセージを金属製の箱に入れて蓋を閉める。しかし、箱を提供している者だけが、組み合わせ錠の組み合わせを知っている。この提供者だけが、メッセージを復号する、すなわち、箱を再び開ける立場にある。メッセージを箱に入れた者でさえ、そのメッセージを再び取り出すことはできない。
【０００６】
非対称または公開鍵符号化構想の基本は、数学的な問題を基礎としており、復号するための公開鍵を使用して、この数学的な問題を解決することは、ほぼ不可能であるが、秘密鍵を知ることにより、これを簡単に解決できる。最も一般的な公開鍵復号システムの１つは、ＲＳＡ暗号システムである。ＲＳＡ暗号システムは、「応用暗号法の手引き」（“Handbook of Applied Cryptography" Menezes, van Oorschot, Vanstone, CRC Press １９９７年、 ２８５〜２９１頁）に記載されている。
【０００７】
第１タスクは、ＲＳＡ暗号システムのための鍵を生成することである。このため、図３を参照する。暗号化されたメッセージを受信できる実体は、第１ステップ３００において、好ましくはほぼ同じ数量の、最初の２つの大きな素数ｐとｑとを生成する必要がある。次に、ステップ３１０において、係数Ｎとも称される、２つの素数の積が計算される。さらに、（ｐ−１）と（ｑ−１）との積に等しい、オイラーのφ関数が演算される。次に、ステップ３２０では、ランダムな整数ｅが選択される。ただし、ｅは、１よりも大きく、φよりも小さいように選択されており、ｅとφとの最大公約数(groesste gemeinsame Teiler)ｇｃｄ（英語ではｇｃｄ＝greatest cocmmon divisor）は１、すなわち、ｅおよびφは、互いに素であるという更なる条件がある。その後、ステップ３３０において、数ｄを演算して、以下の数式：
ｅ×ｄ＝１ｍｏｄφ
を満たす必要がある。ｄは、係数φに対する逆数とも称され、通常、拡張されたユークリッドのアルゴリズム（互助法）を用いて演算される。このアルゴリズムは、「応用暗号法の手引き」の６７頁にも記載されている。従って、ｄは、１よりも大きくφよりも小さい唯一の整数であり、それゆえ、上記数式を満たす。
【０００８】
次に、ステップ３４０において、公開鍵が出力される。ただし、公開鍵は、係数Ｎと数ｅとを含んでいる。これに対し、秘密鍵ｄは、出力されない。しかし、鍵を生成する実体が、ステップ３４０において出力される公開鍵を使用して暗号化されたメッセージを受信した場合、秘密鍵ｄを復号に使用できるように、秘密鍵ｄは、ステップ３５０に格納されている。
【０００９】
以下に、ＲＳＡアルゴリズムを説明するため、図２を参照する。初期状態では、一人の通信相手が、他方の通信相手によって復号される必要のあるメッセージＭを暗号化する。暗号化された実体は、暗号化されたメッセージを他者にとにかく送信できるように、ステップ２００において、公開鍵（Ｎ，ｅ）をまず受け取る必要がある。これに続いて、暗号化する者は、ステップ２１０において、暗号化されるメッセージを整数Ｍの形状で表す必要がある。ただし、Ｍは、０〜Ｎ−１の区間にある必要がある。暗号化ステップ自体であるステップ２２０では、暗号化実体が、以下の数式を演算する必要がある。
【００１０】
Ｃ＝ＭeｍｏｄＮ
Ｃは、暗号化されたメッセージである。次に、このメッセージは、ステップ２３０において出力され、暗号化されたメッセージの受信者へ、図２において指定されている公開チャンネルを介して伝送される。受信者は、暗号化されたメッセージＣをステップ２５０において受信し、以下の演算が、復号ステップ自体であるステップ２６０において行われる。
【００１１】
Ｍ＝ＣdｍｏｄＮ
図２から、暗号化のためには、公開鍵（Ｎ，ｅ）だけが必要であり、秘密鍵ｄは不要であるのに対し、復号のためには、秘密鍵ｄが必要であるということが分かる。
【００１２】
さて、問題は、攻撃者がどのようにしてＲＳＡ暗号システムを打ち破れるかである。攻撃者は、公開鍵、すなわち、Ｎおよびｅを知っている。このとき、攻撃者は、図３に示すのと同じように、係数Ｎを２つの素数の積に因数分解し、次に、鍵を生成する承認者（authentische Partei）が行ったのと同じ方法で、秘密鍵ｄを演算できることもある。このため、攻撃者は、ｅを考慮した秘密鍵ｄにいつかは該当するように、全ての考えられる素数の組ｐ’、ｑ’を試す必要がある。素数ｐおよびｑが小さい場合、この問題は比較的簡単に、ただ試行してみるだけで解決される。しかし、ｐおよびｑ、すなわち、ｐとｑとの積である係数Ｎが、より一層大きくなると、係数Ｎの因数分解のための様々な可能性が、桁外れに大きな範囲に広がる。ＲＳＡシステムの安全性は、このことを基礎としている。このことから、安全性暗号化システムは、例えば５１２、１０２４、または２０４８ビットにさえなる非常に長い数を使用する必要がある。
【００１３】
しかし、素数ｐおよびｑの長さが長くなるのに伴い、逆数、すなわち、図３のステップ３３０における秘密鍵ｄの演算も、時間が問題となる（zeitkritisch）。このため、拡張されたユークリッドのアルゴリズムが使用される。当該数の長さが長くなるのに伴って、このアルゴリズムが演算に必要な時間も、かなりかかると考えられる。
【００１４】
本発明の目的は、秘密鍵を決定するためのより効果的な構想を提供することである。
【００１５】
この目的は、請求項１に記載の鍵ペア決定方法、請求項４に記載のＲＳＡ暗号プロセスの鍵生成方法、請求項５に記載の鍵ペア決定用装置、および、請求項６に記載のＲＳＡ暗号プロセスのための鍵生成用装置により達成される。
【００１６】
本発明は、オイラーのφ関数を使用して逆数の演算するときに、オイラーのφ関数の２つの因数、すなわち、（ｐ−１）および（ｑ−１）が、互いに素でないという問題があるという事項を基礎としている。このことは、素数が、奇数であるということから分かる。「１」の値が、素数から引かれると、２つの因数（ｐ−１）および（ｑ−１）が、この効果に対してもはや互いに素でないように偶数が生じる。なぜなら、これらは、このとき、少なくとも公約数「２」を有しているからである。従って、ユークリッドのアルゴリズムは、従来技術に関連して、総ビット長の数（ｐ−１）（ｑ−１）を用いて、図３に示すように演算される必要があり、その結果、このステップは、時間が問題となる。
【００１７】
本発明では、逆数を演算するために、オイラーのφ関数をもはや用いず、カーマイケルのλ関数を使用する。
【００１８】
カーマイケルのλ関数の使用は、逆数を演算するための数式の右側にある２つの因数は、互いに素であり、その結果、ＣＲＴ（ＣＲＴ＝Chinese Remainder Theorem）とも称される中国人の剰余定理（中国の剰余定理）を使用してもよいという効果がある。中国人の剰余定理およびガーナーのアルゴリズムは、例えば、「応用暗号法の手引き」の６８頁、６１２頁および６１３頁に記載されている。しかし、中国人の剰余定理は、互いに素である素数が存在する場合にのみ使用できる。
【００１９】
秘密鍵、すなわち、逆数を演算するとき、中国人の剰余定理により、総ビット長について１回だけ演算する代わりに、半ビット長について２回の演算ができる。ただし、半ビット長についての２回の演算の結果を迅速に組み合わせる必要もある。
【００２０】
この手順は、従来技術のようにオイラーのφ関数を使用する場合よりも、秘密鍵を４倍まで速く演算できるという効果がある。
【００２１】
本発明の長所は、同じ演算時間で、かなりより長い素数を利用でき、それゆえ、ＲＳＡ暗号システムの安全性が、かなり上昇するということである。
【００２２】
これに対して、従来技術と同じ安全性標準を維持して、演算時間効率を４倍上げることは、ちょうど臨界点において、つまり、逆数の演算において達成される。従って、本発明に基づき実施されている暗号処理機は、例えばＴＰＭ係数（ＴＰＭ＝Trusted Platform Module）、または安全性ＩＣの効率を非常に上昇するために使用されることもある。あるいは、本発明に基づく方法を、スマートカードに使用してもよい。このスマートカードでは、スマートカードにおいて使用できる演算容量が限られているので、素数の長さ、すなわち、安全性についての妥協がなされる。本発明により、演算時間は同じままで、安全性標準をかなり上昇できる。
【００２３】
２つのＣＲＴ項を、相互に別々に演算できるので、２つのＣＲＴ項は、２つの別々の算術演算装置によって並行して演算され、最後に「一緒に合わせ」られてもよい。その結果、並行な実施により、演算時間が一層短くなる。
【００２４】
本発明の好ましい形態を、添付の図を参照して、以下に説明する。
【００２５】
図１は、本発明に基づく方法の好ましい形態のブロック図である。図２は、ＲＳＡアルゴリズムの概要図である。図３は、ＲＳＡ鍵を生成するための概略的なフローチャートである。
【００２６】
図１は、本発明に基づく、鍵ペアｅ、ｄの決定方法の好ましい形態を示す。この図では、２つの素数ｐ、ｑがまず生成され、通常のように、これらは相互に掛算され、結果として係数Ｎになる。次に、ステップ１００において、第１鍵ｅが選択される。しかし、従来技術とは異なり、第２鍵ｄは、もはやオイラーのφ関数を使用して演算されず、カーマイケルのλ関数を用いて演算される。カーマイケルのλ関数は、以下のように規定される。
【００２７】
λ（Ｎ）＝（ｐ−１）（ｑ−１）／ｇｇＴ（ｐ−１，ｑ−１）
カーマイケルのλ関数には、以下の関係がある。
【００２８】
Ｍλ(N)＝１ｍｏｄＮ
そして、第２鍵、すなわち、秘密鍵ｄは、既知のデータｅ、ｐおよびｑを基にして以下のように演算される。
【００２９】
ｅ×ｄ＝１ｍｏｄλ（Ｎ）
上記の数式を解くため、すなわち、逆数ｄを演算するために、中国人の剰余定理（ＣＲＴ）をこのとき使用してもよい。なぜなら、因数
（ｐ−１）／ｇｇＴ（ｐ−１，ｑ−１）、および、（ｑ−１）は、このとき、互いに素だからである。
【００３０】
中国人の剰余定理を用いて、逆数ｄの演算の問題は、このとき、２つの逆数ｄpおよびｄqの演算と、組み合せステップとに分割されてもよい。
【００３１】
このため、ｄpがまず演算されて、以下の定義方程式が満たされる。
【００３２】
ｅ×ｄp＝１ｍｏｄ[（ｐ−１）／ｇｇＴ（ｐ−１，ｑ−１）]
これと同じく、ｄｑを以下の定義方程式を用いて演算できる。
【００３３】
ｅ×ｄq＝１ｍｏｄ（ｑ−１）
あるいは、互いに素である因数が、逆のやり方、すなわち
（ｐ−１）、および、（ｑ−１）／ｇｇＴ（ｐ−１，ｑ−１）のようにも得られるであろう。
【００３４】
ＣＲＴから知られているように、２つのサブ鍵ｄpおよびｄqは、第２鍵ｄ自体の半分の長さであるということを指摘できる。
【００３５】
図１のステップ１１０および１２０は、２つの異なるサブ係数を利用するということを指摘できる。ステップ１１０における第１サブ係数は、
（ｐ−１）／ｇｇＴ（ｐ−１，ｑ−１）となっている。
ステップ１２０における第２サブ係数は、（ｑ−１）だけである。
【００３６】
２つのサブ係数は、ｇｇＴ（最大公約数）関数により互いに素であり、それゆえ、ＣＲＴが効果があるということが分かる。次に、２つのサブ鍵ｄpおよびｄqは、第２または秘密鍵ｄを生成するため、中国人の剰余定理（ＣＲＴ）を用いてステップ１３０において組み合わされる。
【００３７】
このため、以下の数式によって定義される補助数量（Hilfsgroesse）ｘpがまず演算される。
【００３８】
ｘp ＝（ｄp−ｄq ）×［（ｑ−１）-1ｍｏｄ（ｐ−１）／ｇｇＴ（ｐ−１，ｑ−１）］ｍｏｄ（ｐ−１）／ｇｇＴ（ｐ−１，ｑ−１）
上記引用部における逆演算およびｇｇＴ（最大公約数）演算は、半分の長さの数を使用して行われる。このことは、これらステップにあまり時間がかからないという効果を有している。
【００３９】
次に、第２鍵または秘密鍵ｄが以下のように生じる。
【００４０】
ｄ＝ｄq＋ｘp×（ｑ−１）ｍｏｄλ（Ｎ）
上記数式におけるｍｏｄλ（Ｎ）による係数減少をもはや行う必要がないことを指摘できる。なぜなら、ｄは、減少しなくても、既に剰余の範囲にあるからである。
【００４１】
本発明を、ＲＳＡ鍵の生成に使用すると、これは、その時間の複雑性（Zeitkomplexitaet）を改善する。なぜなら、逆数の演算は、拡張されたユークリッドのアルゴリズムにより、係数Ｎに関して、半ビット長について行われる必要があるからである。秘密鍵ｄを、中国人の剰余定理を用いて演算することは、中国人の剰余定理を用いない場合と比べて４倍速い。なぜなら、鍵ペアｅおよびｄを演算するためにオイラーのφ関数を用いる代わりに、中国人の剰余定理のための２つのサブ係数を形成しており、互いに素である２つの素数の積と同じように表すことができる、カーマイケルのλ関数が使用されるためである。
【００４２】
本発明に基づく構想が、ＲＳＡ鍵生成のためにしか使用できないのではなく、ある数に対する逆数が演算される全ての場合に使用されるということを指摘できる。ただし、係数は、相互について、互いに素ではない２つまたは複数の因数により構成されている。カーマイケルのλ関数は、係数に関する逆数を、中国人の剰余（中国人の剰余）定理を用いて得られるという効果を常に有している。なぜなら、サブ係数として使用される互いに素の因数が、このとき存在しているからである。
【図面の簡単な説明】
【図１】  図１は、本発明に基づく方法の好ましい形態のブロック図である。
【図２】  図２は、ＲＳＡアルゴリズムの概要図である。
【図３】  図３は、ＲＳＡ鍵を生成するための概略的なフローチャートである。
【符号の説明】
１００  ｅの選択
１１０  ｄpの演算
１２０  ｄqの演算
１３０  ｄの決定
２００  公開鍵の受信
２１０  数としてのメッセージ表示
２２０  Ｃの演算
２３０  Ｃの出力
２４０  チャンネル
２５０  Ｃの受信
２６０  Ｍの演算
３００  ｐ，ｑの生成
３１０  Ｎの演算
３２０  ｅの選択
３３０  ｄの演算
３４０  公開鍵の出力
３５０  秘密鍵の格納
【図１】
0003854226.tif 000002
【図２】
0003854226.tif 000003
【図３】
0003854226.tif 000004