(57)【要約】【課題】  本発明は、圧縮ＲＳＡ係数の計算方法を提供する。【解決手段】  圧縮ＲＳＡ係数を生成する方法であって、係数Ｎのビットの最大３分の２を決定する。Ｎは所定部分ＮＨを有する。ＮＨは２つの部分Ｎｈ及びＮｍを有する。Ｎｈ部分を共有するＲＳＡ係数の候補が生成される。当該候補は次にユークリッドの計算を用い、Ｎｈ及びＮｍの両方を共有するまで変更される。また、前記方法に従い圧縮ＲＳＡ係数を計算する装置（３０）、及びコンピューター・プログラム（３５）が提供される。【選択図】  図１
2008299335.tif 000002
【特許請求の範囲】
【請求項１】
ＲＳＡ係数の２分の１より大きい所定部分を有するＲＳＡ係数の因数を生成する方法であって、前記ＲＳＡ係数は少なくとも２つの因数を有し、前記方法は、
前記ＲＳＡ係数が共有する所定部分の値（ＮＨ）を受信する段階、
積が少なくとも前記所定部分（ＮＨ）の第１の部分（Ｎｈ）を共有する少なくとも２つの因数を生成する段階、
結果として生じる因数が素数であり且つ前記結果として生じる因数の積が前記所定部分（ＮＨ）を完全に共有するまで、
少なくとも２つの因数のそれぞれの補正値を評価するために拡張されたユークリッドの互除法の拡張を用いることにより、及び
それぞれ補正値を少なくとも２つの因数候補に加算し少なくとも２つの結果として生じる因数を得ることにより、
ユークリッドの計算を用い前記少なくとも２つの因数候補を変更する段階、を有し、
結果として生じる因数の積は前記第１の共有部分（Ｎｈ）を有し、前記所定部分の第２の部分（Ｎｍ）を共有し、
前記方法は、
前記結果として生じる因数を用い暗号化処理を可能にするために、前記結果として生じる因数を出力する段階、を更に有する方法。
【請求項２】
前記ＲＳＡ係数は３素数のＲＳＡ係数である、請求項１記載の方法。
【請求項３】
前記ＲＳＡ係数はＮ＝ｐｒｑの形式である、請求項１記載の方法。
【請求項４】
前記生成する段階は、
第１の因数候補を選択する段階、及び
ある値と前記第１の因数候補との除算の整数の結果として第２の因数候補を計算する段階、を有し、
前記因数候補の積は少なくとも所定部分の第１の部分（Ｎｈ）を共有し、前記値はＲＳＡ係数と同数のビットを有し、及び前記所定部分（ＮＨ）を共有する、請求項１記載の方法。
【請求項５】
拡張されたユークリッドの互除法の拡張は、ａ＝ｑ０且つｂ＝ｐ０としてａｕｉ＋ｂｖｉ＝ｄｉを満たす拡張されたユークリッドの互除法により得られた数列｛ｕｉ，ｖｉ，ｄｉ｝を用い、ｚ０＝ｃ且つｚｉ＝ｚｉ−１  ｍｏｄ  ｄｉ、ｃ＝２ｌ−１＋（ＮＨ２ｌ  ｍｏｄ  ｐ０）として、
【数１】
2008299335.tif 000010
の場合に、２つ数列対｛ｘｉ｝及び｛ｙｉ｝を導出する、請求項１記載の方法。
【請求項６】
ＲＳＡ係数の２分の１より大きい所定部分（ＮＨ）を有するＲＳＡ係数の因数を生成する装置であって、前記ＲＳＡ係数は少なくとも２つの因数を有し、前記装置はプロセッサーを有し、前記プロセッサーは、
前記ＲＳＡ係数が共有する所定部分の値（ＮＨ）を受信し、
積が少なくとも前記所定部分（ＮＨ）の第１の部分（Ｎｈ）を共有する少なくとも２つの因数を生成し、
結果として生じる因数が素数であり且つ前記結果として生じる因数の積が前記所定部分（ＮＨ）を完全に共有するまで、
少なくとも２つの因数のそれぞれの補正値を評価するために拡張されたユークリッドの互除法の拡張を用いることにより、及び
それぞれ補正値を少なくとも２つの因数候補に加算し少なくとも２つの結果として生じる因数を得ることにより、
ユークリッドの計算を用い前記少なくとも２つの因数候補を変更し、
結果として生じる因数の積は前記第１の共有部分（Ｎｈ）を有し、前記所定部分の第２の部分（Ｎｍ）を共有し、
前記プロセッサーは、
前記結果として生じる因数を用い暗号化処理を可能にするために、前記結果として生じる因数を更に出力する、装置。
【請求項７】
コンピューター・プログラムであって、前記プログラムは、前記プログラムがプロセッサーで実行されると、請求項１乃至５の何れか１項記載の方法の段階を実行するプログラム・コード命令を有する、コンピューター・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に暗号化、及び特に圧縮ＲＳＡ係数に関する。
【背景技術】
【０００２】
本章では読者に、以下に記載され及び／又は請求される本発明の種々の態様に関連し得る技術の種々の態様を紹介する。この記載は読者に背景情報を提供し本発明の種々の態様を一層理解するために有用であろう。従って、理解されるべき点は、これらの記述がこの観点から読まれるべきであり、従来技術の承認ではないことである。
【０００３】
公開暗号法で用いる所謂リベスト−シャミア−エーデルマン（ＲＳＡ）係数を生成するには次のように処理する。
【０００４】
Ｎ＝ｐｑを２つの大きい素数の積とする。ｅ及びｄは公開及び秘密の指数の対を示し、以下を満たすとする。
ｅｄ≡１（ｍｏｄλ（Ｎ））
ここでｇｃｄ（ｅ，λ（Ｎ））＝１、λはカーマイケル関数である。Ｎ＝ｐｑなので、λ（Ｎ）＝ｌｃｍ（ｐ−１，ｑ−１）を得る。ｘ＜Ｎの場合、公開処理（例えば、メッセージの暗号化又は署名検証）はｘのｅ乗のモジュロＮ、つまりｙ＝ｘｅ  ｍｏｄ  Ｎの計算を含む。次に、ｙが与えられると、対応する秘密処理（例えば、暗号文の復号化又は署名生成）はｙｄ  ｍｏｄ  Ｎの計算を含む。ｅ及びｄの定義から、明らかにｙｄ≡ｘ（ｍｏｄＮ）である。秘密処理は中国剰余定理（ＣＲＴモード）を通じて高速に実行され得る。計算はモジュロｐ及びｑと独立に実行され、再結合される。この場合、秘密パラメーターは｛ｐ，ｑ，ｄｐ，ｄｑ，ｉｑ｝である。ここで、
ｄｐ＝ｄ  ｍｏｄ  （ｐ−１）
ｄｑ＝ｄ  ｍｏｄ  （ｑ−１）
ｉｑ＝ｑ−１  ｍｏｄ  ｐ
次にｙｄ≡ｘ（ｍｏｄ  Ｎ）が次のように得られる。ＣＲＴ（ｘｐ，ｘｑ）＝ｘｑ＋ｑ［ｉｑ（ｘｐ−ｘｑ）ｍｏｄ  ｐ］ここでｘｐ＝ｙｄｐ  ｍｏｄ  ｐ、且つｘｑ＝ｙｄｑ  ｍｏｄ  ｑである。
【０００５】
纏めると、ＲＳＡ係数Ｎ＝ｐｑは２つの大きな素数ｐとｑの積であり、ｇｃｄ（λ（Ｎ），ｅ）＝１を満たす。ｎがＮのビット・サイズを示すならば、１＜ｎ０＜ｎでは、ｐは［２ｎ−ｎ０−１／２，２ｎ−ｎ０−１］の範囲であり、ｑは［２ｎ０−１／２，２ｎ０−１］の範囲である。従って２ｎ−１＜Ｎ＝ｐｑ＜２ｎである。セキュリティを理由に、所謂、ｎ＝２ｎ０の平衡係数が一般的に望ましい。
【０００６】
標準的に今日のＲＳＡ係数範囲は１０２４乃至４０９６ビットの長さであり、少なくとも２０４８ビットの係数を必要とするアプリケーションで一般的になってきている。しかしながら、依然として、１０２４ビットの係数のみに対応したＲＳＡを使用可能なアプリケーションを実行するプログラム及び／又は装置が存在する。
【０００７】
従って圧縮係数をより短いバッファ又は帯域に適合させる解決手段は非常に有効である。ＲＳＡ係数全体を格納／送信するのではなく、可逆圧縮表現が用いられる。これはまた、プログラム及び／又は装置の異なるリリース間の互換性の問題を解決する。更に、このような技術は効率を向上し、つまりメモリー及び／又は帯域を節約し得る。
【０００８】
このような解決法の１つは非特許文献１に記載されている。この解決法の仕様では、最大Ｎ／２の上位ビットであるが、比較的複雑であり、例えば指定ビットにより与えられる数の因数分解を必要とする。更に、結果として得られる係数は比較的簡単に因数分解される。
【０００９】
このような解決法の別の例は、非特許文献２に記載されている。この解決法は、Vanstone及びZuccheratoの解決法の改良であり、複雑さが少なく、結果として生じる計数は因数分解が困難である。
【非特許文献１】Vanstone、Zuccherato、Short  RSA  Keys  and  Their  Generation、Journal  of  Cryptology、米国、１９９５年、ｖｏｌ．８、ｎｏ．８、ｐ．１０１−１１４、XP０００８５３６７１
【非特許文献２】Lenstra、ArjenK、Generating  RSA  moduli  with  a  predetermined  portion、米国、Advances  in  Cryptology-ASIACRYPT'９８、１９９８年、講義録ｖｏｌ．１５１４、ｐ．１−１０
【発明の開示】
【発明が解決しようとする課題】
【００１０】
しかしながら、従来の方法の何れもＲＳＡ係数のビットの半分より多くを先に決定できない。
【００１１】
本発明は、Lenstraの生成法を改良し、例えば更なる圧縮を実現した。
【課題を解決するための手段】
【００１２】
本発明の第１の態様は、ＲＳＡ係数の２分の１より大きい所定部分を有するＲＳＡ係数の因数を生成する方法である。当該ＲＳＡ係数は少なくとも２つの因数を有する。ＲＳＡ係数が共有すべき所定部分の第１の値が受信される。少なくとも２つの因数候補が生成される。当該２つの候補因数の積は少なくとも所定部分の第１の部分を共有する。少なくとも２つの因数候補は、ユークリッドの計算を用い、結果として生じる因数が素数であり且つ結果として生じる因数の積が所定部分を完全に共有するまで、少なくとも２つの因数のそれぞれの補正値を評価するために拡張されたユークリッドの互除法の拡張を用いることにより、及びそれぞれ補正値を少なくとも２つの因数候補に加算し少なくとも２つの結果として生じる因数を得ることにより、変更される。ここで、結果として生じる因数の積は第１の共有部分を有し、所定部分の第２の部分を共有する。最終的に、結果として生じる因数は、結果として生じる因数を用いる暗号処理を可能にするために出力される。
【００１３】
第１の好適な実施例では、ＲＳＡ係数は３素数のＲＳＡ係数である。
【００１４】
第２の好適な実施例では、ＲＳＡ係数はＮ＝ｐｒｑの形式である。
【００１５】
第３の好適な実施例では、生成する段階は、第１の因数候補を選択する段階、及びある値と前記第１の因数候補との除算の整数の結果として第２の因数候補を計算する段階、を有し、従って因数候補の積は少なくとも所定部分の第１の部分を共有し、前記値はＲＳＡ係数と同数のビットを有し、及び前記所定部分を共有する。
【００１６】
本発明の第４の好適な実施例では、拡張されたユークリッドの互除法の拡張は、ａ＝ｑ０且つｂ＝ｐ０としてａｕｉ＋ｂｖｉ＝ｄｉを満たす拡張されたユークリッドの互除法により得られた数列｛ｕｉ，ｖｉ，ｄｉ｝を用い、
【数２】
2008299335.tif 000003
の場合に、２つ数列対｛ｘｉ｝及び｛ｙｉ｝を導出する。
ここでｚ０＝ｃ且つｚｉ＝ｚｉ−１  ｍｏｄ  ｄｉ、ｃ＝２ｌ−１＋（ＮＨ２ｌ  ｍｏｄ  ｐ０）である。
本発明の第２の態様は、ＲＳＡ係数の２分の１より大きい所定部分を有するＲＳＡ係数の因数を生成する装置である。当該ＲＳＡ係数は少なくとも２つの因数を有する。当該装置はプロセッサーを有し、当該プロセッサーは、ＲＳＡ係数が共有する所定部分の値を受信し、積が少なくとも前記所定部分の第１の部分を共有する少なくとも２つの因数を生成し、ユークリッドの計算を用い結果として生じる因数が素数であり且つ前記結果として生じる因数の積が前記所定部分を完全に共有するまで、少なくとも２つの因数のそれぞれの補正値を評価するために拡張されたユークリッドの互除法の拡張を用いることにより、及びそれぞれ補正値を少なくとも２つの因数候補に加算し少なくとも２つの結果として生じる因数を得ることにより、当該少なくとも２つの因数を変更するよう構成される。ここで、結果として生じる因数の積は第１の共有部分を有し、所定部分の第２の部分を共有する。プロセッサーは、結果として生じる因数を、結果として生じる因数を用いる暗号処理を可能にするために出力する。
【００１７】
本発明の第３の態様は、コンピューター・プログラムであって、前記プログラムは、前記プログラムがプロセッサーで実行されると、第１の態様の方法の段階を実行するプログラム・コード命令を有する。
【００１８】
「共有する」は、共有される部分が同一値を有することを意味する。例えば１６進数１２３４５６７８９０ａｂｃｄｅｆと１２３４５６７８９ａｂｃｄｅｆ０は最初の数字部分で１２３４５６７８９を共有している。
【発明を実施するための最良の形態】
【００１９】
本発明の好適な特徴は、単なる例として添付の図面を参照し説明される。
【００２０】
本発明の主要な考えは、ＲＳＡ型の暗号化方式で鍵を生成するために用いられるｎビットのＲＳＡ係数Ｎを提供する方法である。ここでＮのｎビットの最大約３分の２が予め決定される。
【００２１】
図１は、本発明による例であるＲＳＡ係数１０を示す。ｌはＮｌのビット長を示す。従ってｎ＝ｎ０＋ｋ’＋ｌである。
【００２２】
Ｎ＝ｐｑは２つの大きな素数の積であるとする。ここでｐは（ｎ−ｎ０）ビットの整数であり、ｑはｎ０ビットの整数である。従ってＮはｎビットのＲＳＡ係数である。
【００２３】
最初に、ｐ０とｑ０を次の通り計算する。
（１）疑似乱数生成器を用い、乱数種ｓ０から（ｎ０＋ｋ’）ビットの整数ＮＨを生成する。
【数３】
2008299335.tif 000004
（２）次の整数ｐ０をランダムに選択する。
【数４】
2008299335.tif 000005
（３）
【数５】
2008299335.tif 000006
を定める。当業者はｐ０及びｑ０に関する上記の選択が、ＮＨ２ｌ−ｐ０ｑ０＝ＮＨ２ｌ  ｍｏｄ  ｐ０を示すことを理解するだろう。
【００２４】
次に、ｐ＝ｐ０＋ｘ及びｑ＝ｑ０＋ｙ、及びｚ＝ｘｙ＋２ｌ−１−Ｎｌである。従って、以下を得る。
【数６】
2008299335.tif 000007
当業者は、この値を選択することが必然的に可能であることを理解するだろう。
【００２５】
｜ｘｙ−ｚ｜＝｜Ｎｌ−２ｌ−１｜＜２ｌ−１を満たす後者の式の整数解（ｘ，ｙ，ｚ）を求める。この目的のため、ａ＝ｑ０、ｂ＝ｐ０としてａｕｉ＋ｂｖｉ＝ｄｉ拡張されたユークリッドの互除法により得られた数列｛ｕｉ，ｖｉ，ｄｉ｝を考える。
【００２６】
拡張されたユークリッドの互除法は３個の数列を生成する。つまり｛ｕｉ｝、｛ｖｉ｝、｛ｄｉ｝である。以下は拡張されたユークリッドの互除法の拡張であり、自動的に又は明示的に拡張されたユークリッドの互除法の少なくとも１つの数列に基づき、少なくとも１つの異なる数列を生成する。
【００２７】
ここでｚ０＝ｃ且つｚｉ＝ｚｉ−１  ｍｏｄ  ｄｉ、ｃ＝２ｌ−１＋（ＮＨ２ｌ  ｍｏｄ  ｐ０）とする。また２つの数列対｛ｘｉ｝、｛ｙｉ｝、は次のように与えられる。
【数７】
2008299335.tif 000008
ここで以下を得る。
【数８】
2008299335.tif 000009
これが所望の範囲の解である。
【００２８】
図２は本発明の方法をＲＳＡ−２０４８問題に適用した例を示す。図から分かるように、本発明の方法により生成された素数ｐとｑは、対応するＲＳＡ係数Ｎ＝ｐｑが上位３分の２に関するＲＳＡ−２０４８問題に適合する（下線の１６進数により示される）。
図３はＲＳＡ係数を計算する装置を示す。装置３０は、単一のプロセッサー又は複数のプロセッサーの組合せであって良いプロセッサー３１、メモリー３２、記憶媒体３５から方法を実行するための格納されたプログラム・コードを受信して良い通信インターフェース３３、及びユーザー・インターフェース３４を有する。
【００２９】
プロセッサー３１は、望ましくは本発明の好適な方法に従いＲＳＡ係数を生成する。メモリー３２はデータを格納する。通信インターフェース３３は他の装置と通信する。
【００３０】
装置３０は通信インターフェース３３又はユーザー・インターフェース３４の何れかを介し所定部分ＮＨを、所定部分ＮＨを共有する１又は複数のＲＳＡ係数を計算するための入力として受信する。係数が計算されると、装置は係数をユーザー・インターフェースを通じて又は望ましくはＲＳＡ暗号化で用いられる他の装置へ出力する。
【００３１】
理解されるべき点は、本発明の好適な実施例による方法は係数の上位ビットを決定するが、係数Ｎの下位ビットを決定することも可能であることである。更に一般的には、Ｎの特定の上位ビット及び特定の下位ビット、又はＮ全体に散在している多数のビットを決定することも可能である。
【００３２】
本発明の方法は、２個以上の因数を有するＲＳＡ係数、例えば３素数のＲＳＡ係数又はＮ＝ｐｒｑの形式のＲＳＡに対応するために適応されて良い。
【００３３】
本発明の方法はまた、ＲＳＡ係数Ｎの共通部分、つまりＮＨがユーザーの間で共有される場合に、又は所与のアプリケーションの全てのユーザーに共通である場合にも適用できる。このような場合、当該共通部分又は当該共通部分を再構成するために必要なデータを送信する必要がない。
【００３４】
当業者は、本発明を用いて生成されたＲＳＡ係数が、データ通信システム内で通信する団体に、Ｎのビットの約３分の１だけを当該所定部分を復元するために必要なデータ（好適な実施例ではシード）と一緒に交換することを可能にする。
【００３５】
更に、当該ＲＳＡ暗号化方式で団体が生成する鍵はまた、Ｎのビットの約３分の１だけを当該所定部分を復元するために必要なデータ（好適な実施例ではシード）と一緒に交換することを可能にする。
【００３６】
本発明の新たな方法は、ＲＳＡ暗号化方式で用いられる鍵生成に必要な送信及び／又は記憶封建を有意に低減する。
【００３７】
当業者は、本発明が例えば圧縮ＲＳＡ係数の生成を可能にすることを理解するだろう。
本発明は単に例として記載されたことが理解されるだろう。
本願明細書に開示された各特長及び（必要に応じて）請求項及び図面は、独立に又は如何なる適切な組み合わせで提供されても良い。ハードウェアで実施されるとして記載された特徴はまた、ソフトウェアで実施されても良い。逆も同様である。
【００３８】
請求項内の参照符合は、単に説明のためであり、請求項の範囲を制限するものではない。
【図面の簡単な説明】
【００３９】
【図１】本発明による例であるＲＳＡ係数１０を示す。
【図２】本発明の方法をＲＳＡ−２０４８問題に適用した例を示す。
【図３】圧縮ＲＳＡ係数を計算する装置を示す。
【符号の説明】
【００４０】
１０  ＲＳＡ係数
３０  ＲＳＡ発生器
３１  プロセッサー
３２  メモリー
３３  インターフェース
３４  ユーザー・インターフェース
３５  コンピュータープログラム
ＮＨ  所定部分
Ｎｈ  第１の部分
Ｎｍ  第２の部分
【図１】
2008299335.tif 000011
【図２】
2008299335.tif 000012
【図３】
2008299335.tif 000013