圧縮されたＲＳＡモジュラスを生成する方法及び装置
少なくとも２つの係数を有するＲＳＡモジュラスの係数を所定の部分Ｎｈにより生成する方法及び装置。第１素数ｐが生成され、モジュラスＮの一部を構成するＮｈの値が取得され、ｐｑがＮｈを共有するＲＳＡモジュラスとなるように、第２素数ｑがｐ及びＮｈに依存した区間において生成され、モジュラスＮの計算を可能にする情報が出力される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に公開鍵暗号化アルゴリズムに関し、特にＲＳＡ（Ｒｉｖｅｓｔ−Ｓｈａｍｉｒ−Ａｄｌｅｍａｎ）モジュラスの圧縮表現に関する。
【背景技術】
【０００２】
本セクションは、以下に説明及び／又は請求される本発明の各種態様に関連しうる様々な技術を読者に紹介するためのものである。この説明は、読者が本発明の各種態様のより良い理解を容易にするための背景情報を読者に提供するのに役立つと考えられる。従って、これらの説明はこの観点から参照されるべきであると理解され、従来技術の自認とみなされるべきでない。
【０００３】
Ｎ＝ｐｑを２つの大きな素数の積とする。ｅ，ｄをｅｄ≡１（ｍｏｄ λ（Ｎ））（ただし、ｇｃｄ（ｅ，λ（Ｎ））＝１及びλはＣａｒｍｉｃｈａｅｌの関数である）を充足する公開指数と秘密指数とする。Ｎ＝ｐｑであるため、λ（Ｎ）＝ｌｃｍ（ｐ−１，ｑ−１）となる。ｘ＜Ｎが与えられると、公開演算（メッセージ暗号化や署名検証など）は、ｘのｅ乗をＮで割った剰余、すなわち、ｙ＝ｘｅ ｍｏｄ Ｎを計算することからなる。その後、ｙが与えられると、対応する秘密演算（暗号文の解読や署名生成など）は、ｙｄ ｍｏｄ Ｎを計算することからなる。ｅ，ｄの定義から、ｙｄ≡ｘ（ｍｏｄ Ｎ）となることは明らかである。秘密演算は、中国の剰余処理（ＣＲＴモード）により高速に実行可能である。モジュロｐ及びｑの計算は独立に実行され、その後に合成される。この場合、秘密パラメータは、ｄｐ＝ｄ ｍｏｄ （ｐ−１），ｄｑ＝ｄ ｍｏｄ （ｑ−１），及びｉｑ＝ｑ―１ ｍｏｄ ｐによる｛ｐ，ｑ，ｄｐ，ｄｑ，ｉｑ｝である。このとき、ＣＲＴ（ｘｐ，ｘｑ）＝ｘｑ＋ｑ［ｉｑ（ｘｐ−ｘｑ） ｍｏｄ ｐ］としてｙｄ ｍｏｄ Ｎが得られる。ただし、ｘｐ＝ｙｄｐ ｍｏｄ ｐ及びｘｑ＝ｙｄｑ ｍｏｄ ｑである。すなわち、（２係数）ＲＳＡモジュラスＮ＝ｐｑは、ｇｃｄ（λ（Ｎ），ｅ）＝１を充足する２つの大きな素数の積である。ｎがＮのビットサイズを示す場合、ある１＜ｎ０＜ｎに対して、ｐは［２ｎ−ｎ０−１／２，２ｎ−ｎ０−１］の範囲内にあり、ｑは［２ｎ０−１／２，２ｎ０−１］の範囲内にあるはずであり、この結果、２ｎ−１＜Ｎ＝ｐｑ＜２ｎとなる。セキュリティの理由のため、いわゆるバランスされたモジュラスが一般に好まれ、これは、ｎ＝２ｎ０を意味する。
【０００４】
典型的なＲＳＡモジュラスは、１０２４〜４０９６ビットの範囲内である。現在、アプリケーションが少なくとも２０４８ビットのモジュラスを要求することが慣例となっている。しかしながら、ＲＳＡ対応アプリケーションを実行するプログラム及び／又は装置は、１０２４ビットモジュラスしかサポートしないよう設計されているかもしれない。より短い帯域幅やバッファに適合しうるように、モジュラスを圧縮するというアイデアがある。すなわち、ＲＳＡモジュラス全体を格納／送信するのでなく、可逆圧縮された表現が用いられる。これはまた、異なるリリースのプログラム及び／又は装置の間の互換性の問題も解決する。独立した興味として、このような技術は、メモリ及び／又は帯域幅の節約による効率性の向上に利用可能である。
【０００５】
Ａｒｊｅｎ Ｋ．Ｌｅｎｓｔｒａ（“Ｇｅｎｅｒａｔｉｎｇ ＲＳＡ ｍｏｄｕｌｉ ｗｉｔｈ ａ ｐｒｅｄｅｔｅｒｍｉｎｅｄ ｐｏｒｔｉｏｎ”Ａｄｖａｎｃｅｓ ｉｎ Ｃｒｙｐｔｏｌｏｇｙ−ＡＳＩＡＣＲＹＰＴ‘９８，ｖｏｌｕｍｅ １５１４ ｏｆ Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，ｐａｇｅｓ １−１０．Ｓｐｒｉｎｇｅｒ，１９９８）が生成方法を提案しているが、Ｌｅｎｓｔｒａの方法は、第２素数ｑが増分的に構成され、かなり過大な実行回数をもたらすため、スマートカードなどの限定的な装置には適さない。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
本発明は、圧縮されたＲＳＡモジュラスが所定の区間における２つの素数を生成することにより実行されるという点で、従来技術の問題を解決する。この結果、Ｍａｒｃ Ｊｏｙｅ，Ｐａｓｃａｌ Ｐａｉｌｌｉｅｒ，ａｎｄ Ｓｅｒｇｅ Ｖａｕｄｅｎａｙ（“Ｅｆｆｉｃｉｅｎｔ ｇｅｎｅｒａｔｉｏｎ ｏｆ ｐｒｉｍｅ ｎｕｍｂｅｒ”Ｃｒｙｐｔｏｇｒａｐｈｉｃ Ｈａｒｄｗａｒｅ ａｎｄ Ｅｍｂｅｄｄｅｄ Ｓｙｓｔｅｍｓ−ＣＨＥＳ ２０００，ｖｏｌｕｍｅ １９６５ ｏｆ Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，ｐａｇｅｓ ３４０−３５４．Ｓｐｒｉｎｇｅｒ，２０００）により提案され、Ｍａｒｃ Ｊｏｙｅ ａｎｄ Ｐａｓｃａｌ Ｐａｉｌｌｉｅｒ（“Ｆａｓｔ ｇｅｎｅｒａｔｉｏｎ ｏｆ ｐｒｉｍｅ ｎｕｍｂｅｒｓ ｏｎ ｐｏｒｔａｂｌｅ ｄｅｖｉｃｅｓ：Ａｎ ｕｐｄａｔｅ”
Ｃｒｙｐｔｏｇｒａｐｈｉｃ Ｈａｒｄｗａｒｅ ａｎｄ Ｅｍｂｅｄｄｅｄ Ｓｙｓｔｅｍｓ−ＣＨＥＳ ２００６，ｖｏｌｕｍｅ ４２４９ ｏｆ Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，ｐａｇｅｓ １６０−１７３．Ｓｐｒｉｎｇｅｒ，２００６）により改良されたものなど、効率的な素数生成アルゴリズムの利益を享受することができる。特に、それらは、固定された公開指数ｅ＝２１６＋１によるＮを法とする２０４８ビットのＲＳＡ（すなわち、ｎ＝２０４８）を生成し、Ｎ又はＮの表現を格納するため、２０４８ビット未満しか必要としないことを目的とする状況において極めて適している。
【課題を解決するための手段】
【０００７】
第１の態様では、本発明は、ＲＳＡモジュラスの係数を所定の部分Ｎｈにより生成する方法に関する。ＲＳＡモジュラスは、少なくとも２つの係数を有する。まず、第１素数ｐが生成され、モジュラスＮの一部を構成するＮｈの値が取得され、第２素数ｑが生成され、モジュラスＮの明確な復元を可能にするモジュラスＮの可逆圧縮表現が少なくとも出力される。第２素数ｑは、ｐｑがＮｈを共有するＲＳＡモジュラスとなるように、ｐとＮｈに依存した区間において生成される。
【０００８】
第１の好適な実施例では、所定の部分ＮｈはＲＳＡモジュラスの先頭にある。ＲＳＡモジュラスはｎビットのモジュラスであり、所定の部分Ｎｈはκビットを有し、第１素数ｐは、ｇｃｄ（ｐ−１，ｅ）＝１となるように区間
【数１】
において生成され、第２素数ｑは、ｇｃｄ（ｑ−１，ｅ）＝１となるように区間
【数２】
において生成され、
【数３】
である（ただし、Ｎｌ＝（ｐｑ） ｍｏｄ ２ｎ−κである）。
【０００９】
第２の好適な実施例では、所定の部分ＮｈはＲＳＡモジュラスの後尾にある。第１素数は、ｇｃｄ（ｐ−１，ｅ）＝１となるように区間
【数４】
において生成され、第２素数ｑは、ｑ＝Ｃ＋ｑ’２κ（ただし、
【数５】
である）を計算することによって生成され、ｑ’は、ｇｃｄ（ｑ−１，ｅ）＝１となるよう区間
【数６】
において生成され、
【数７】
が定義され、
【数８】
が出力される。
【００１０】
第３の好適な実施例では、Ｎｈは第１素数ｐの少なくとも一部を暗号化することにより得られる。
【００１１】
第２の態様では、本発明は、ＲＳＡモジュラスの係数を所定の部分Ｎｈにより生成する装置に関する。ＲＳＡモジュラスは、少なくとも２つの係数を有する。本装置は、第１素数ｐを生成し、モジュラスＮの一部を構成するＮｈの値を取得し、ｐｑがＮｈを共有するＲＳＡモジュラスとなるように、ｐとＮｈに依存した区間において第２素数ｑを生成するプロセッサを有する。本装置はさらに、モジュラスＮの明確な復元を可能にするモジュラスＮの可逆圧縮表現を少なくとも出力するインタフェースを有する。
【００１２】
第１の好適な実施例では、本装置はスマートカードである。
【００１３】
“共有”とは、共有される部分について同一の値を有することとして解釈される。例えば、１６進数１２３４５６７８９０ａｂｃｄｅｆと１２３４５６７８９ａｂｃｄｅｆ０は、これらの数字の先頭部分において１２３４５６７８９を共有している。
【図面の簡単な説明】
【００１４】
【図１】図１は、本発明の好適な実施例によるＲＳＡモジュラス生成のための装置を示す。
【発明を実施するための形態】
【００１５】
［全体的なアイデア］
本発明の全体的なアイデアは、Ｎを構成する各素数がある区間から任意の抽出可能となるように（かつ、従来提案に示唆された増分的な試行でなく）、ＲＳＡモジュラスＮの大部分を固定することから構成される。このＲＳＡモジュラスの大部分は、（公開）擬似乱数生成手段を用いたランダムな短いシードから評価されるか、又は各ユーザ間に共有される。
【００１６】
これは、ＲＳＡモジュラスのための高速（かつ実現容易）な圧縮技術をもたらす。さらに、このように生成されたＲＳＡモジュラスは、通常のＲＳＡモジュラスと区別することはできない（すなわち、出力分布に相違がない）。最後に、それらは、最新の素数生成技術に互換的である（この場合、追加的なコストがない）。
［好適な実施例］
１＜κ≦ｎ０とする。２つの大きな素数ｐ，ｑの積であるｎビットのＲＳＡモジュラスＮは、以下のように生成することができる。
１．擬似乱数生成手段を用いて、ランダムシードｓ０からκビットの整数Ｎｈを生成する。
【００１７】
【数９】
ここで、２κ−１によるＯＲ演算は、Ｎｈの最上位ビットが１であることを保証することに留意されたい。
２．ｇｃｄ（ｐ−１，ｅ）＝１となるように、ランダムな素数
【数１０】
を生成する。
３．ｇｃｄ（ｑ−１，ｅ）＝１となるように、ランダムな素数
【数１１】
を生成する。このような素数が見つからない場合、処理が繰り返される。
４．Ｎｌ＝（ｐｑ） ｍｏｄ ２ｎ−κを定義し、
【数１２】
を出力する。
【００１８】
【数１３】
が与えられると、対応するｎビットのＲＳＡモジュラスＮ、すなわち、
【数１４】
を公開復元することは容易となる。ただし、Ｎｈは、
【数１５】
として得られるκビットの整数である。
【００１９】
２ｎ−κ≦ｐである場合、ｑが選ばれる範囲は空になるかもしれないことが留意されるべきである。これは、κが高々ｎ０となるべき理由を説明する。このため、上記方法は、最も良い場合にはｎ０ビットまでｎビットＲＳＡモジュラスを圧縮する。ワーストケースはバランスされたＲＳＡモジュラスについてであり（すなわち、ｎ＝２ｎ０）、１÷２の（最も良い場合に）圧縮比をもたらす。
［第１の代替的実施例］
他の実施例では、モジュラスＮのトレイリングビットが固定される。
１．シードｓ０から、
【数１６】
を生成する。Ｎｈもまた当然選ばれてもよい。
２．第１素数
【数１７】
と、ｇｃｄ（ｐ−１，ｅ）＝１を生成する。
３．存在する場合には、
【数１８】
により第２素数
【数１９】
と、ｇｃｄ（ｑ−１，ｅ）＝１を生成する。
４．
【数２０】
を定義し、
【数２１】
を出力する。
【００２０】
１であることが確信されるＮｌの最上位ビットを
【数２２】
に含めることは必要でないことが理解されるであろう。
【００２１】
より一般に、Ｎのリーディングビットとトレイリングビットを固定することもまた可能である。
［第２の代替的実施例］
提案された方法は、３素数ＲＳＡモジュラスやＮ＝ｐｒｑの形式のＲＳＡモジュラスなど、２より多い係数のＲＳＡモジュラスを受け入れるよう適応可能である。これのさらなる説明について、Ｔｓｕｙｏｓｈｉ Ｔａｌａｇｉの論文（“Ｆａｓｔ ＲＳＡ−ｔｙｐｅ ｃｒｙｐｏｓｙｓｔｅｍ ｍｏｄｕｌｏ ｐｋｑ”Ａｄｖａｎｃｅｓ ｉｎ Ｃｒｙｐｔｏｌｏｇｙ−ＣＲＹＰＴＯ‘９８，ｖｏｌｕｍｅ １４６２ ｏｆ Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，ｐａｇｅｓ３１８−３２６．Ｓｐｒｉｎｇｅｒ，１９９８）が効果的に参照できる。
［第３の代替的実施例］
提案された方法はまた、ＲＳＡモジュラスの共通部分、すなわち、Ｎｈがユーザ間に共有されるか、又は所与のアプリケーションについてすべてのユーザに共通であるときにも適用される。このようなケースでは、ランダムシードｓ０（κ及びｎの値と共に）を送信する必要はない。
［装置］
図１は、本発明の好適な実施例によるＲＳＡモジュラス生成装置を示す。生成装置１００は、少なくとも１つのプロセッサ１１０と、少なくとも１つのメモリ１２０と、個別の入力部と出力部とを有する通信手段１３０と、おそらくユーザインタフェース１４０とを有する。処理手段は、上述した方法の何れかを実行するよう適合される。
［鍵供託］
本発明は、鍵供託用に効果的に用いることが可能であることが理解されるであろう。ＲＳＡモジュラスＮ＝ｐｑの場合、ｐ（又はｑ）のビットの約１／２が分かっていれば、格子低減技術などを用いて秘密鍵を復元するのに十分である。このため、ｐのビットの約１／２（又はそれ以上）が、秘密鍵Ｋを用いて暗号化され、公開ＲＳＡモジュラスＮの表現に埋め込まれる場合、Ｋを知っている“当局”は、Ｎからｐを再構成し、対応する秘密ＲＳＡ鍵を計算することができるであろう。ｐの暗号化されたビットは、ＲＳＡモジュラスの所定部分に構成されるかもしれない。
【００２２】
さらに、本発明による方法は、相対的に少ないリソースしか私用しないスマートカードや他のリソース制限のある装置に使用するのに特に効果的であることが理解されるであろう。
【００２３】
明細書、請求項及び図面（必要に応じて）に開示された各特徴は、独立して又は何れか適切な組み合わせにより提供されるかもしれない。各特徴は、必要に応じて、ハードウェア、ソフトウェア又はこれらの組み合わせにより実現されてもよい。
【００２４】
“一実施例”又は“ある実施例”という表現は、当該実施例に関して説明される特定の特徴又は構成が本発明の少なくとも１つの実現形態に含めることができることを意味する。明細書の各箇所における“一実施例では”という表現は、その全てが必ずしも同一の実施例を参照するとは限らず、相互に排他的な他の又は異なる実施例を参照してるとも限らない。
【００２５】
請求項に記載される参照番号は、例示的なものであり、請求項の範囲に対する効果を制限するものでない。
【技術分野】
【０００１】
本発明は、一般に公開鍵暗号化アルゴリズムに関し、特にＲＳＡ（Ｒｉｖｅｓｔ−Ｓｈａｍｉｒ−Ａｄｌｅｍａｎ）モジュラスの圧縮表現に関する。
【背景技術】
【０００２】
本セクションは、以下に説明及び／又は請求される本発明の各種態様に関連しうる様々な技術を読者に紹介するためのものである。この説明は、読者が本発明の各種態様のより良い理解を容易にするための背景情報を読者に提供するのに役立つと考えられる。従って、これらの説明はこの観点から参照されるべきであると理解され、従来技術の自認とみなされるべきでない。
【０００３】
Ｎ＝ｐｑを２つの大きな素数の積とする。ｅ，ｄをｅｄ≡１（ｍｏｄ λ（Ｎ））（ただし、ｇｃｄ（ｅ，λ（Ｎ））＝１及びλはＣａｒｍｉｃｈａｅｌの関数である）を充足する公開指数と秘密指数とする。Ｎ＝ｐｑであるため、λ（Ｎ）＝ｌｃｍ（ｐ−１，ｑ−１）となる。ｘ＜Ｎが与えられると、公開演算（メッセージ暗号化や署名検証など）は、ｘのｅ乗をＮで割った剰余、すなわち、ｙ＝ｘｅ ｍｏｄ Ｎを計算することからなる。その後、ｙが与えられると、対応する秘密演算（暗号文の解読や署名生成など）は、ｙｄ ｍｏｄ Ｎを計算することからなる。ｅ，ｄの定義から、ｙｄ≡ｘ（ｍｏｄ Ｎ）となることは明らかである。秘密演算は、中国の剰余処理（ＣＲＴモード）により高速に実行可能である。モジュロｐ及びｑの計算は独立に実行され、その後に合成される。この場合、秘密パラメータは、ｄｐ＝ｄ ｍｏｄ （ｐ−１），ｄｑ＝ｄ ｍｏｄ （ｑ−１），及びｉｑ＝ｑ―１ ｍｏｄ ｐによる｛ｐ，ｑ，ｄｐ，ｄｑ，ｉｑ｝である。このとき、ＣＲＴ（ｘｐ，ｘｑ）＝ｘｑ＋ｑ［ｉｑ（ｘｐ−ｘｑ） ｍｏｄ ｐ］としてｙｄ ｍｏｄ Ｎが得られる。ただし、ｘｐ＝ｙｄｐ ｍｏｄ ｐ及びｘｑ＝ｙｄｑ ｍｏｄ ｑである。すなわち、（２係数）ＲＳＡモジュラスＮ＝ｐｑは、ｇｃｄ（λ（Ｎ），ｅ）＝１を充足する２つの大きな素数の積である。ｎがＮのビットサイズを示す場合、ある１＜ｎ０＜ｎに対して、ｐは［２ｎ−ｎ０−１／２，２ｎ−ｎ０−１］の範囲内にあり、ｑは［２ｎ０−１／２，２ｎ０−１］の範囲内にあるはずであり、この結果、２ｎ−１＜Ｎ＝ｐｑ＜２ｎとなる。セキュリティの理由のため、いわゆるバランスされたモジュラスが一般に好まれ、これは、ｎ＝２ｎ０を意味する。
【０００４】
典型的なＲＳＡモジュラスは、１０２４〜４０９６ビットの範囲内である。現在、アプリケーションが少なくとも２０４８ビットのモジュラスを要求することが慣例となっている。しかしながら、ＲＳＡ対応アプリケーションを実行するプログラム及び／又は装置は、１０２４ビットモジュラスしかサポートしないよう設計されているかもしれない。より短い帯域幅やバッファに適合しうるように、モジュラスを圧縮するというアイデアがある。すなわち、ＲＳＡモジュラス全体を格納／送信するのでなく、可逆圧縮された表現が用いられる。これはまた、異なるリリースのプログラム及び／又は装置の間の互換性の問題も解決する。独立した興味として、このような技術は、メモリ及び／又は帯域幅の節約による効率性の向上に利用可能である。
【０００５】
Ａｒｊｅｎ Ｋ．Ｌｅｎｓｔｒａ（“Ｇｅｎｅｒａｔｉｎｇ ＲＳＡ ｍｏｄｕｌｉ ｗｉｔｈ ａ ｐｒｅｄｅｔｅｒｍｉｎｅｄ ｐｏｒｔｉｏｎ”Ａｄｖａｎｃｅｓ ｉｎ Ｃｒｙｐｔｏｌｏｇｙ−ＡＳＩＡＣＲＹＰＴ‘９８，ｖｏｌｕｍｅ １５１４ ｏｆ Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，ｐａｇｅｓ １−１０．Ｓｐｒｉｎｇｅｒ，１９９８）が生成方法を提案しているが、Ｌｅｎｓｔｒａの方法は、第２素数ｑが増分的に構成され、かなり過大な実行回数をもたらすため、スマートカードなどの限定的な装置には適さない。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
本発明は、圧縮されたＲＳＡモジュラスが所定の区間における２つの素数を生成することにより実行されるという点で、従来技術の問題を解決する。この結果、Ｍａｒｃ Ｊｏｙｅ，Ｐａｓｃａｌ Ｐａｉｌｌｉｅｒ，ａｎｄ Ｓｅｒｇｅ Ｖａｕｄｅｎａｙ（“Ｅｆｆｉｃｉｅｎｔ ｇｅｎｅｒａｔｉｏｎ ｏｆ ｐｒｉｍｅ ｎｕｍｂｅｒ”Ｃｒｙｐｔｏｇｒａｐｈｉｃ Ｈａｒｄｗａｒｅ ａｎｄ Ｅｍｂｅｄｄｅｄ Ｓｙｓｔｅｍｓ−ＣＨＥＳ ２０００，ｖｏｌｕｍｅ １９６５ ｏｆ Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，ｐａｇｅｓ ３４０−３５４．Ｓｐｒｉｎｇｅｒ，２０００）により提案され、Ｍａｒｃ Ｊｏｙｅ ａｎｄ Ｐａｓｃａｌ Ｐａｉｌｌｉｅｒ（“Ｆａｓｔ ｇｅｎｅｒａｔｉｏｎ ｏｆ ｐｒｉｍｅ ｎｕｍｂｅｒｓ ｏｎ ｐｏｒｔａｂｌｅ ｄｅｖｉｃｅｓ：Ａｎ ｕｐｄａｔｅ”
Ｃｒｙｐｔｏｇｒａｐｈｉｃ Ｈａｒｄｗａｒｅ ａｎｄ Ｅｍｂｅｄｄｅｄ Ｓｙｓｔｅｍｓ−ＣＨＥＳ ２００６，ｖｏｌｕｍｅ ４２４９ ｏｆ Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，ｐａｇｅｓ １６０−１７３．Ｓｐｒｉｎｇｅｒ，２００６）により改良されたものなど、効率的な素数生成アルゴリズムの利益を享受することができる。特に、それらは、固定された公開指数ｅ＝２１６＋１によるＮを法とする２０４８ビットのＲＳＡ（すなわち、ｎ＝２０４８）を生成し、Ｎ又はＮの表現を格納するため、２０４８ビット未満しか必要としないことを目的とする状況において極めて適している。
【課題を解決するための手段】
【０００７】
第１の態様では、本発明は、ＲＳＡモジュラスの係数を所定の部分Ｎｈにより生成する方法に関する。ＲＳＡモジュラスは、少なくとも２つの係数を有する。まず、第１素数ｐが生成され、モジュラスＮの一部を構成するＮｈの値が取得され、第２素数ｑが生成され、モジュラスＮの明確な復元を可能にするモジュラスＮの可逆圧縮表現が少なくとも出力される。第２素数ｑは、ｐｑがＮｈを共有するＲＳＡモジュラスとなるように、ｐとＮｈに依存した区間において生成される。
【０００８】
第１の好適な実施例では、所定の部分ＮｈはＲＳＡモジュラスの先頭にある。ＲＳＡモジュラスはｎビットのモジュラスであり、所定の部分Ｎｈはκビットを有し、第１素数ｐは、ｇｃｄ（ｐ−１，ｅ）＝１となるように区間
【数１】
において生成され、第２素数ｑは、ｇｃｄ（ｑ−１，ｅ）＝１となるように区間
【数２】
において生成され、
【数３】
である（ただし、Ｎｌ＝（ｐｑ） ｍｏｄ ２ｎ−κである）。
【０００９】
第２の好適な実施例では、所定の部分ＮｈはＲＳＡモジュラスの後尾にある。第１素数は、ｇｃｄ（ｐ−１，ｅ）＝１となるように区間
【数４】
において生成され、第２素数ｑは、ｑ＝Ｃ＋ｑ’２κ（ただし、
【数５】
である）を計算することによって生成され、ｑ’は、ｇｃｄ（ｑ−１，ｅ）＝１となるよう区間
【数６】
において生成され、
【数７】
が定義され、
【数８】
が出力される。
【００１０】
第３の好適な実施例では、Ｎｈは第１素数ｐの少なくとも一部を暗号化することにより得られる。
【００１１】
第２の態様では、本発明は、ＲＳＡモジュラスの係数を所定の部分Ｎｈにより生成する装置に関する。ＲＳＡモジュラスは、少なくとも２つの係数を有する。本装置は、第１素数ｐを生成し、モジュラスＮの一部を構成するＮｈの値を取得し、ｐｑがＮｈを共有するＲＳＡモジュラスとなるように、ｐとＮｈに依存した区間において第２素数ｑを生成するプロセッサを有する。本装置はさらに、モジュラスＮの明確な復元を可能にするモジュラスＮの可逆圧縮表現を少なくとも出力するインタフェースを有する。
【００１２】
第１の好適な実施例では、本装置はスマートカードである。
【００１３】
“共有”とは、共有される部分について同一の値を有することとして解釈される。例えば、１６進数１２３４５６７８９０ａｂｃｄｅｆと１２３４５６７８９ａｂｃｄｅｆ０は、これらの数字の先頭部分において１２３４５６７８９を共有している。
【図面の簡単な説明】
【００１４】
【図１】図１は、本発明の好適な実施例によるＲＳＡモジュラス生成のための装置を示す。
【発明を実施するための形態】
【００１５】
［全体的なアイデア］
本発明の全体的なアイデアは、Ｎを構成する各素数がある区間から任意の抽出可能となるように（かつ、従来提案に示唆された増分的な試行でなく）、ＲＳＡモジュラスＮの大部分を固定することから構成される。このＲＳＡモジュラスの大部分は、（公開）擬似乱数生成手段を用いたランダムな短いシードから評価されるか、又は各ユーザ間に共有される。
【００１６】
これは、ＲＳＡモジュラスのための高速（かつ実現容易）な圧縮技術をもたらす。さらに、このように生成されたＲＳＡモジュラスは、通常のＲＳＡモジュラスと区別することはできない（すなわち、出力分布に相違がない）。最後に、それらは、最新の素数生成技術に互換的である（この場合、追加的なコストがない）。
［好適な実施例］
１＜κ≦ｎ０とする。２つの大きな素数ｐ，ｑの積であるｎビットのＲＳＡモジュラスＮは、以下のように生成することができる。
１．擬似乱数生成手段を用いて、ランダムシードｓ０からκビットの整数Ｎｈを生成する。
【００１７】
【数９】
ここで、２κ−１によるＯＲ演算は、Ｎｈの最上位ビットが１であることを保証することに留意されたい。
２．ｇｃｄ（ｐ−１，ｅ）＝１となるように、ランダムな素数
【数１０】
を生成する。
３．ｇｃｄ（ｑ−１，ｅ）＝１となるように、ランダムな素数
【数１１】
を生成する。このような素数が見つからない場合、処理が繰り返される。
４．Ｎｌ＝（ｐｑ） ｍｏｄ ２ｎ−κを定義し、
【数１２】
を出力する。
【００１８】
【数１３】
が与えられると、対応するｎビットのＲＳＡモジュラスＮ、すなわち、
【数１４】
を公開復元することは容易となる。ただし、Ｎｈは、
【数１５】
として得られるκビットの整数である。
【００１９】
２ｎ−κ≦ｐである場合、ｑが選ばれる範囲は空になるかもしれないことが留意されるべきである。これは、κが高々ｎ０となるべき理由を説明する。このため、上記方法は、最も良い場合にはｎ０ビットまでｎビットＲＳＡモジュラスを圧縮する。ワーストケースはバランスされたＲＳＡモジュラスについてであり（すなわち、ｎ＝２ｎ０）、１÷２の（最も良い場合に）圧縮比をもたらす。
［第１の代替的実施例］
他の実施例では、モジュラスＮのトレイリングビットが固定される。
１．シードｓ０から、
【数１６】
を生成する。Ｎｈもまた当然選ばれてもよい。
２．第１素数
【数１７】
と、ｇｃｄ（ｐ−１，ｅ）＝１を生成する。
３．存在する場合には、
【数１８】
により第２素数
【数１９】
と、ｇｃｄ（ｑ−１，ｅ）＝１を生成する。
４．
【数２０】
を定義し、
【数２１】
を出力する。
【００２０】
１であることが確信されるＮｌの最上位ビットを
【数２２】
に含めることは必要でないことが理解されるであろう。
【００２１】
より一般に、Ｎのリーディングビットとトレイリングビットを固定することもまた可能である。
［第２の代替的実施例］
提案された方法は、３素数ＲＳＡモジュラスやＮ＝ｐｒｑの形式のＲＳＡモジュラスなど、２より多い係数のＲＳＡモジュラスを受け入れるよう適応可能である。これのさらなる説明について、Ｔｓｕｙｏｓｈｉ Ｔａｌａｇｉの論文（“Ｆａｓｔ ＲＳＡ−ｔｙｐｅ ｃｒｙｐｏｓｙｓｔｅｍ ｍｏｄｕｌｏ ｐｋｑ”Ａｄｖａｎｃｅｓ ｉｎ Ｃｒｙｐｔｏｌｏｇｙ−ＣＲＹＰＴＯ‘９８，ｖｏｌｕｍｅ １４６２ ｏｆ Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，ｐａｇｅｓ３１８−３２６．Ｓｐｒｉｎｇｅｒ，１９９８）が効果的に参照できる。
［第３の代替的実施例］
提案された方法はまた、ＲＳＡモジュラスの共通部分、すなわち、Ｎｈがユーザ間に共有されるか、又は所与のアプリケーションについてすべてのユーザに共通であるときにも適用される。このようなケースでは、ランダムシードｓ０（κ及びｎの値と共に）を送信する必要はない。
［装置］
図１は、本発明の好適な実施例によるＲＳＡモジュラス生成装置を示す。生成装置１００は、少なくとも１つのプロセッサ１１０と、少なくとも１つのメモリ１２０と、個別の入力部と出力部とを有する通信手段１３０と、おそらくユーザインタフェース１４０とを有する。処理手段は、上述した方法の何れかを実行するよう適合される。
［鍵供託］
本発明は、鍵供託用に効果的に用いることが可能であることが理解されるであろう。ＲＳＡモジュラスＮ＝ｐｑの場合、ｐ（又はｑ）のビットの約１／２が分かっていれば、格子低減技術などを用いて秘密鍵を復元するのに十分である。このため、ｐのビットの約１／２（又はそれ以上）が、秘密鍵Ｋを用いて暗号化され、公開ＲＳＡモジュラスＮの表現に埋め込まれる場合、Ｋを知っている“当局”は、Ｎからｐを再構成し、対応する秘密ＲＳＡ鍵を計算することができるであろう。ｐの暗号化されたビットは、ＲＳＡモジュラスの所定部分に構成されるかもしれない。
【００２２】
さらに、本発明による方法は、相対的に少ないリソースしか私用しないスマートカードや他のリソース制限のある装置に使用するのに特に効果的であることが理解されるであろう。
【００２３】
明細書、請求項及び図面（必要に応じて）に開示された各特徴は、独立して又は何れか適切な組み合わせにより提供されるかもしれない。各特徴は、必要に応じて、ハードウェア、ソフトウェア又はこれらの組み合わせにより実現されてもよい。
【００２４】
“一実施例”又は“ある実施例”という表現は、当該実施例に関して説明される特定の特徴又は構成が本発明の少なくとも１つの実現形態に含めることができることを意味する。明細書の各箇所における“一実施例では”という表現は、その全てが必ずしも同一の実施例を参照するとは限らず、相互に排他的な他の又は異なる実施例を参照してるとも限らない。
【００２５】
請求項に記載される参照番号は、例示的なものであり、請求項の範囲に対する効果を制限するものでない。
【特許請求の範囲】
【請求項１】
少なくとも２つの係数を有するＲＳＡモジュラスＮの係数を所定の部分Ｎｈにより生成する方法であって、
第１素数ｐを生成するステップと、
モジュラスＮの一部を構成するＮｈの値を取得するステップと、
第２素数ｑを生成するステップと、
前記モジュラスＮの明確な復元を可能にするモジュラスＮの可逆圧縮された表現を少なくとも出力するステップと、
を有し、
当該方法は、ｐｑがＮｈを共有するＲＳＡモジュラスとなるように、前記第２素数ｑがｐ及びＮｈに依存した所定の区間においてランダムに生成されることを特徴とする方法。
【請求項２】
前記所定の部分Ｎｈは、ＲＳＡモジュラスの先頭にある、請求項１記載の方法。
【請求項３】
前記ＲＳＡモジュラスは、ｎビットのモジュラスであり、
前記所定の部分Ｎｈは、κビットを有し、
前記第１素数ｐは、ｇｃｄ（ｐ−１，ｅ）＝１となるように、区間
【数２３】
において生成され、
前記第２素数ｑは、ｇｃｄ（ｑ−１，ｅ）＝１となるように、区間
【数２４】
において生成され、
【数２５】
である（ただし、Ｎｌ＝（ｐｑ） ｍｏｄ ２ｎ−κである）、請求項２記載の方法。
【請求項４】
前記所定の部分Ｎｈは、前記ＲＳＡモジュラスの後尾にある、請求項１記載の方法。
【請求項５】
前記第１素数ｐは、ｇｃｄ（ｐ−１，ｅ）＝１となるように、区間
【数２６】
において生成され、
前記第２素数ｑは、ｑ＝Ｃ＋ｑ’２κを計算することにより生成され（ただし、
【数２７】
である）、
ｑ’は、ｇｃｄ（ｑ−１，ｅ）＝１となるように、区間
【数２８】
において生成され、
【数２９】
が定義され、
【数３０】
が出力される、請求項４記載の方法。
【請求項６】
Ｎｈは、前記第１素数ｐの少なくとも一部を暗号化することによって取得される、請求項１乃至５何れか一項記載の方法。
【請求項７】
少なくとも２つの係数を有するＲＳＡモジュラスＮの係数を所定の部分Ｎｈにより生成する装置であって、
第１素数ｐを生成し、モジュラスＮの一部を構成するＮｈの値を取得し、ｐｑがＮｈを共有するＲＳＡモジュラスとなるように、ｐ及びＮｈに依存した所定の区間において第２素数ｑをランダムに生成するプロセッサと、
前記モジュラスＮの明確な復元を可能にするモジュラスＮの可逆圧縮された表現を少なくとも出力するインタフェースと、
を有する装置。
【請求項８】
当該装置は、スマートカードである、請求項７記載の装置。
【請求項１】
少なくとも２つの係数を有するＲＳＡモジュラスＮの係数を所定の部分Ｎｈにより生成する方法であって、
第１素数ｐを生成するステップと、
モジュラスＮの一部を構成するＮｈの値を取得するステップと、
第２素数ｑを生成するステップと、
前記モジュラスＮの明確な復元を可能にするモジュラスＮの可逆圧縮された表現を少なくとも出力するステップと、
を有し、
当該方法は、ｐｑがＮｈを共有するＲＳＡモジュラスとなるように、前記第２素数ｑがｐ及びＮｈに依存した所定の区間においてランダムに生成されることを特徴とする方法。
【請求項２】
前記所定の部分Ｎｈは、ＲＳＡモジュラスの先頭にある、請求項１記載の方法。
【請求項３】
前記ＲＳＡモジュラスは、ｎビットのモジュラスであり、
前記所定の部分Ｎｈは、κビットを有し、
前記第１素数ｐは、ｇｃｄ（ｐ−１，ｅ）＝１となるように、区間
【数２３】
において生成され、
前記第２素数ｑは、ｇｃｄ（ｑ−１，ｅ）＝１となるように、区間
【数２４】
において生成され、
【数２５】
である（ただし、Ｎｌ＝（ｐｑ） ｍｏｄ ２ｎ−κである）、請求項２記載の方法。
【請求項４】
前記所定の部分Ｎｈは、前記ＲＳＡモジュラスの後尾にある、請求項１記載の方法。
【請求項５】
前記第１素数ｐは、ｇｃｄ（ｐ−１，ｅ）＝１となるように、区間
【数２６】
において生成され、
前記第２素数ｑは、ｑ＝Ｃ＋ｑ’２κを計算することにより生成され（ただし、
【数２７】
である）、
ｑ’は、ｇｃｄ（ｑ−１，ｅ）＝１となるように、区間
【数２８】
において生成され、
【数２９】
が定義され、
【数３０】
が出力される、請求項４記載の方法。
【請求項６】
Ｎｈは、前記第１素数ｐの少なくとも一部を暗号化することによって取得される、請求項１乃至５何れか一項記載の方法。
【請求項７】
少なくとも２つの係数を有するＲＳＡモジュラスＮの係数を所定の部分Ｎｈにより生成する装置であって、
第１素数ｐを生成し、モジュラスＮの一部を構成するＮｈの値を取得し、ｐｑがＮｈを共有するＲＳＡモジュラスとなるように、ｐ及びＮｈに依存した所定の区間において第２素数ｑをランダムに生成するプロセッサと、
前記モジュラスＮの明確な復元を可能にするモジュラスＮの可逆圧縮された表現を少なくとも出力するインタフェースと、
を有する装置。
【請求項８】
当該装置は、スマートカードである、請求項７記載の装置。
【図１】
【公表番号】特表２０１０−５１９５９８（Ｐ２０１０−５１９５９８Ａ）
【公表日】平成２２年６月３日（２０１０．６．３）
【国際特許分類】
【出願番号】特願２００９−５５１１７２（Ｐ２００９−５５１１７２）
【出願日】平成２０年２月１９日（２００８．２．１９）
【国際出願番号】ＰＣＴ／ＥＰ２００８／０５２０１７
【国際公開番号】ＷＯ２００８／１０４４８２
【国際公開日】平成２０年９月４日（２００８．９．４）
【出願人】（５０１２６３８１０）トムソン ライセンシング (2,848)
【氏名又は名称原語表記】Ｔｈｏｍｓｏｎ Ｌｉｃｅｎｓｉｎｇ
【住所又は居所原語表記】１−５， ｒｕｅ Ｊｅａｎｎｅ ｄ’Ａｒｃ， ９２１３０ ＩＳＳＹ ＬＥＳ ＭＯＵＬＩＮＥＡＵＸ， Ｆｒａｎｃｅ
【Ｆターム（参考）】
【公表日】平成２２年６月３日（２０１０．６．３）
【国際特許分類】
【出願日】平成２０年２月１９日（２００８．２．１９）
【国際出願番号】ＰＣＴ／ＥＰ２００８／０５２０１７
【国際公開番号】ＷＯ２００８／１０４４８２
【国際公開日】平成２０年９月４日（２００８．９．４）
【出願人】（５０１２６３８１０）トムソン ライセンシング (2,848)
【氏名又は名称原語表記】Ｔｈｏｍｓｏｎ Ｌｉｃｅｎｓｉｎｇ
【住所又は居所原語表記】１−５， ｒｕｅ Ｊｅａｎｎｅ ｄ’Ａｒｃ， ９２１３０ ＩＳＳＹ ＬＥＳ ＭＯＵＬＩＮＥＡＵＸ， Ｆｒａｎｃｅ
【Ｆターム（参考）】
[ Back to top ]