データ処理システム及びデータ処理方法
【課題】ＩＣカードのように限られた記憶資源しか持たなくても効率的な暗号化処理の実現に資することができる技術を提供する。
【解決手段】暗号鍵の生成システムは、多数の小さい素数を再構成するための演算ユニット、小さい素数によって整数が割り切れるかを点検するための篩ユニット、整数の表現を変えるための再符号化ユニット、及び素数性判定テストユニットを備える。篩ユニットは最初に演算ユニットによって再構成される小さい素数によって整数が割り切れることを点検し、これによって「不適当な」素数候補を取り除く。その後、残りの素数候補は素数性判定テストユニットを使用してテストされる。このとき、再構成ユニットを使用して素数候補の表現が変換され、変換された表現形態を用いて素数性判定テストユニットが判定する。これにより、大きなメモリ容量を必要とすることなく、素数性判定のための演算処理数を減少することができる。
【解決手段】暗号鍵の生成システムは、多数の小さい素数を再構成するための演算ユニット、小さい素数によって整数が割り切れるかを点検するための篩ユニット、整数の表現を変えるための再符号化ユニット、及び素数性判定テストユニットを備える。篩ユニットは最初に演算ユニットによって再構成される小さい素数によって整数が割り切れることを点検し、これによって「不適当な」素数候補を取り除く。その後、残りの素数候補は素数性判定テストユニットを使用してテストされる。このとき、再構成ユニットを使用して素数候補の表現が変換され、変換された表現形態を用いて素数性判定テストユニットが判定する。これにより、大きなメモリ容量を必要とすることなく、素数性判定のための演算処理数を減少することができる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、素数判定のためのデータ処理システム及びデータ処理方法に関し、例えば公開鍵暗号方式のシステム構成等において使用される暗号鍵の効果的な生成に適用して有効な技術に関する。
【背景技術】
【０００２】
公開鍵暗号方式は広く認識され、現在多くのアプリケーション、例えば銀行業務または電子商業のために用いられている。そこでは、安全ではないネットワークを介してユーザ間でデジタル署名書類、暗号化データ、変換鍵キー等が用いられている。ＲＳＡは、公開鍵暗号法のための事実上の標準であって、デジタル署名または公開鍵暗号化が必要とされるアプリケーションにおいて一般化している。たとえば、ＲＳＡの活用は、クレジットカードのためのＥＭＶ（Europay-Mastercard-Visa）コンソーシアムによって推薦され、より正確に言うと、２０１０年までは、１０２４ビットのキー長さをもつＲＳＡがＥＭＶにより推奨され、それ以降は２０４８ビットのキーが推奨される。
【０００３】
ＲＳＡにおいて、メッセージはnビット整数としてコード化される。ＲＳＡ公開鍵はベキ指数E（それは概して小さい）、ｎビットの法数Ｎから成る。ＲＳＡ秘密鍵はｎビット整数Ｄであり、E*D = 1 mod(P-1)*(Q-1)の関係がある。記号*は乗算を意味する。ここで、ＰとＱは秘密の素数であり、それはP*Q＝Nの関係を満足する。任意のメッセージ0＜=M＜N、（ＭE）D mod N＝Mに関して説明する。例えばアリスがＲＳＡ鍵となる（E,N）,Dの保有者であると仮定する、そして、ボブはアリスに暗号化されたメッセージＭを送りたいと仮定する。ボブはC=ME mod Nを計算し、アリスに暗号文を送る。次に、アリスはCD=(ME)D=M mod Nを計算して元の文を回復する。これにより、ＲＳＡの中心的な動作が累乗の剰余乗算XY mod N.であることが解る。Nが大きいとき、例えば２０４８ビットのようなとき、その累乗計算には時間がかかる。ＲＳＡの演算を高速化するには、中国の剰余定理を利用することができる。それは累乗の剰余乗算CD mod Nが２つの累乗の法PとＱに交換できることを言及する。N=P*QでありP及びQは法Ｎの約半分のデータサイズであるから、その中国の剰余定理によるアプローチ（ＲＳＡ−ＣＲＴ）によれば実際に演算を早く行うことができる。ＲＳＡ−ＣＲＴにおいて、その暗号化の手順は標準のＲＳＡと同様に、C=ME mod Nである。相違点は暗号からの復号手続きである。例えば、DP = D mod P-1 = E-1 mod P-1、DQ = D mod Q-1 = E-1 mod Q-1、Qinv =Q-1 mod P と定義されているとする。これにおいて、Z=X-1 mod YがZ*X=1 mod Y を満足する整数が1＜=Z＜Yであるとき、コンピュータによるＲＳＡ−ＣＲＴの復号処理は、MP = C^DP mod P、MQ = C^DQ mod Q、M = MQ + Q*[Qinv *（MP−MQ））mod P ]とされる。したがって、そのときのＲＳＡの鍵の対は、公開鍵であるE、N、標準ＲＳＡのための秘密鍵であるＤ及びＲＳＡ−ＣＲＴのためのＰ，Ｑ，ＤQ，ＤP，Ｑinvである。
【０００４】
ＲＳＡ鍵の長さは例えば、公開鍵Nのビット数のサイズに関係する。例えば２０４８ビットＲＳＡにおいて、公開鍵Nは２０４８ビットを持ち、素数Ｐ、Ｑは概してそれぞれ１０２４ビットを有する。その結果、N=P*Qになる。ＲＳＡ鍵を発行するためには２つのランダムな素数PおよびQが選択され、他の鍵素子は２つの素数に由来する。ランダムな素数を生成するには、一つには次のように処理が進行する。第１に、ランダムな整数は選ばれ、そして、この任意の数は素数判定、例えばフェルマー判定が行われる。その数が素数判定をパスしない場合には、新たな素数候補に更新されて処理が行なわれる。更新の処理は方法によって異なり、例えば新たな任意の整数とし、又は最初のランダムな整数を増加させる。任意の素数を生成するステップは、ＲＳＡ鍵を生成するコンピュータ処理において最もコンピュータリソースを費やしている。
【０００５】
過去においては、そのようなコストの大きな処理を行なうにはコンピュータ処理能力があまりにも低く、ＩＣカードにおいてＲＳＡ鍵を生成する場合については疑いなくそうだった。結果として、ＲＳＡ鍵は、パワフルなワークステーションを用いて生成され、ＩＣカードにコピーされた。しかしながら、最近のＩＣカードは、公開鍵暗号処理に特化したハードウェア・アクセラレータによる利益を享受する。前記ハードウェア・アクセラレータは暗号処理用のコプロセッサであり、ＩＣカードが暗号鍵を生成することは現実的になっている。これには、２つの効果がある。第１は、ワークステーションで鍵を生成する場合のように、もしもワークステーションに障害が発生すればそれによって生成された全ての鍵が危うくなるというような、単一障害点にはならない、と言うことである。第２は、カード発行者は秘密鍵を知らなくてもよい、という点である。即ち、カード発行者にとってみれば秘密鍵を漏らすかまたはそれらを誤用する責任があるとみなされることはない。
【０００６】
【特許文献１】米国特許第７１１３５９５号明細書
【非特許文献１】Alfred Menezes, Paul van Oorschot, Scott Vanstone:"Handbook of Applied Cryptography", Chapter 4, Public-Key Parameters. CRC Press, ISBN 0-8493-8523-7
【非特許文献２】Katsuyuki Okeya, Katja Schmidt-Samoa, Christian Spahn and Tsuyoshi Takagi: "Signed Binary Representations Revisited", Proceedings of Advances in Cryptology, CRYPTO 2004, LNCS 3152, Springer-Verlag, 2004
【発明の開示】
【発明が解決しようとする課題】
【０００７】
暗号化処理用のコプロセッサによってその計算処理が促進されても、ＩＣカードのような携帯デバイスは低い計算能力および不十分な記憶資源という非常に圧迫された環境のままであることが多い。しかしながら、そのエンドユーザは暗号鍵が発生されるのに長時間待たされることを欲しないのが通例である。したがって、多くのコンピュータリソースを要せず効率的にその種の暗号鍵を生成することができる技術の開発が要望される。
【０００８】
また、非特許文献１において、ランダムな素数を生成するいくつかの方法が記載されている。しかしながら、それに記載の技術は、不十分なメモリ資源しか備えていないＩＣカードではほとんど実現することができない。非特許文献２においては、ランダムな素数を生成するコンパクトな技術が詳述されているが効率的な方法を提供するものではない。
【０００９】
本発明は上記事情に鑑みてなされたものであり、例えばＩＣカードのように限られた記憶資源しか持たなくても効率的な暗号化処理の実現に資することができる素数判定技術を提供することを目的とする。換言すれば、本発明の目的は、携帯機器のように不十分な記憶資源であっても高速にランダムな素数を生成することができる技術を提供することにある。
【００１０】
本発明の前記並びにその他の目的と新規な特徴は本明細書の記述及び添付図面から明らかになるであろう。
【課題を解決するための手段】
【００１１】
本願において開示される発明のうち代表的なものの概要を簡単に説明すれば下記の通りである。
【００１２】
すなわち、本発明は少ないコンピュータリソースで効率的な処理を可能とするために、データの符号化と再符号化に適用される。特に、素数生成ステップの間、予め定められたコンパクトなテーブルが、多数の小さい素数を再生成するのに用いられる。加えて、素数判定で処理される素数候補が再符号化され、それらの表現形式をバイナリ符号から適当な符号に変える。
【００１３】
例えば、暗号鍵を生成するデータ処理システムは、多数の小さい素数を再構成するための演算ユニット、小さい素数によって整数が割り切れるかを点検するための篩ユニット、整数の表現を変えるための再符号化ユニット、及び素数性判定テストユニットを備える。篩ユニットは最初に演算ユニットによって再構成される小さい素数によって整数が割り切れることを点検し、これによって「不適当な」素数候補を取り除く。その後、残りの素数候補は素数性判定テストユニットを使用してテストされる。このとき、再構成ユニットを使用して素数候補の表現が変換され、変換された表現形態を用いて素数性判定テストユニットが判定動作を行う。これにより、大きなメモリ容量を必要とすることなく、素数性判定のための演算処理数を減少することができる。
【発明の効果】
【００１４】
本願において開示される発明のうち代表的なものによって得られる効果を簡単に説明すれば下記のとおりである。
【００１５】
すなわち、ＩＣカード等のように限られた記憶資源しか持たなくても素数判定若しくは素数生成において効率的な暗号化処理の実現に資することができる。
【００１６】
また、携帯機器のように不十分な記憶資源であっても高速にランダムな素数を生成することができる。
【発明を実施するための最良の形態】
【００１７】
１．定義
先ず、以下の説明で使用する語の定義と表記法について述べる。AまたはBのような大文字の変数は、例えば１０２４ビットの整数のように、大きな整数を意味する。xまたはyのような小文字で示される変数は、一般的に３２ビットよりも小さなビット長の小さな整数を意味する。
【００１８】
R=A*B mod Nは古典的な剰余乗算式を示すものである。ここで、P=A*Bは通常の乗算である、そして、Rは除算P/Nの剰余である。換言すれば、Rは整数0＜=R＜Nであり、R+Q*N = A*Bとなり、Qはある整数である。AD mod Nはべき乗の剰余乗算であり、D-1を伴なうA*A*…*A mod Nの剰余乗算に対応する。それは、同様にA^D mod Nとも記述される。記号^はべき乗若しくは累乗を意味する。
【００１９】
gcd(A,B)は、AとBの最大公約数である。例えば3は6および15の最大公約数である。6=3*2、15=3*5だからである。
【００２０】
A-1 mod Nは、A*B=1 mod Nのような整数Bを参照する。gcd(A,N)=1ならば Bは存在する。
【００２１】
素数とは、それ自身と１との２つの除数を有する整数である。例えば整数2、3、5、7、11は素数である。
【００２２】
合成整数（合成数）は、少なくとも2つの素数に因数分解されることができる整数である。21は21=3*7であるから合成整数であり、4は4=2*2であるから合成数である。
【００２３】
MontMult(A,B,N)はモンゴメリー乗算であり、Ｎをｎビットの法数とする剰余乗算A*B*2-n mod Nに等しい。
【００２４】
２．実施の形態１
先ず素数生成回路を主眼に説明する。
【００２５】
《ＩＣカード》
図１にはＩＣカードのブロックダイヤグラムが示される。ＩＣカード901は、少なくとも以下の部品を備えている。即ち、入出力インタフェース931、鍵生成ユニット912及び署名生ユニット913を含む暗号化ユニット911、そして、少なくとも秘密鍵922、公開鍵923及びデジタル証明書924が記憶されるメモリ921を備える。特に制限されないが、実施の形態１では暗号化ユニット911をハードウェアロジックで構成することを想定している。
【００２６】
前記ＩＣカードはネットワーク９４１を介して例えばＡＴＭ９０４及びカードリーダ９０５に接続可能にされるＡＴＭ９０４は銀行のホストシステム（銀行ホスト）９０２に、カードリーダ９０５はカード発行元のホストシステム（カード発行元ホスト）９０３に接続される。９４２はＩＣカード９０１からネットワーク９４１に送信されるデータ、９４３はＩＣカードがネットワーク９４１から受信するデータである。
【００２７】
ＩＣカード９０１に、事実上の標準であるＲＳＡを有するデジタル署名が実装されている場合、ＩＣカード９０１で直接暗号鍵を生成することは有利であることが先に示された。これを実現するために、鍵生成ユニット912は素数を生成するための専用の回路である素数生成ユニット914を利用することができる。ＲＳＡにおける鍵生成において、素数生成にはデータ処理上最もコストを要するから、素数生成ユニット914を利用することによってそれを低減するものである。
【００２８】
《ＩＣカードの動作》
図２は、ＲＳＡ対応のＩＣカード902の典型的な使用例が示される。最初に、ＲＳＡの鍵は、ＩＣカード９０１のステップ1011において発生する。ＲＳＡの鍵は秘密鍵922および公開鍵923から成る。そして、それらはメモリ921に保存される。その後、ＩＣカード901はステップ1012でカード発行元ホスト903に、公開鍵923を送る。その後、デジタル証明書924が発行されることによって公開鍵が確認される。デジタル証明書９２４は、ステップ1013でＩＣカードに送り返されて、メモリ921に保存される。
【００２９】
ＲＳＡの鍵はＩＣカードの認証動作の初めに少なくとも発生しなければならない、そして、おそらくデジタル証明書の有効性日付以後、デジタル証明書924が発給される。デジタル証明書924が有効なときに、ＩＣカードは認証されたトークンカード（認証トークン）として利用可能にされる。ＩＣカードはステップ1021で銀行ホスト902に処理要求を送る。銀行ホストはステップ1022の認証要求を出して応答する。ステップ1023において、ＩＣカード901は署名生成ユニット913およびその秘密鍵922を使用しているデジタル署名を生成し、生成したデジタル署名、その公開鍵923及びカード発行元ホスト903から発行されたデジタル証明書924を送る。署名およびデジタル証明書が有効な場合、銀行ホスト902によって認証が付与される。証明書が有効なときは、ステップ１０２１から１０２３の処理は必要に応じて何回も実行される。それは殆ど無制限のデジタル処理回数を許容していることになる。
【００３０】
《素数生成ユニット》
図３には素数生成ユニット914の具体例が示される。図１の鍵生成ユニット912は素数Ｐ，Ｑを生成するために素数生成ユニット914を有する。Ｐ，Ｑに関してはＰ*Ｑが公開法数Ｎに等しい、という関係を持っている。素数Ｐ又はＱを生成するために素数生成ユニット９１４は最初のランダムな候補Ｐinitを採り、候補Ｐinitよりも大きな第1の素数Pを見つける。素数生成ユニット９１４は３つのサブユニット、即ち、フェルマーテストユニット1111、ビット配列ユニット1131および小さい素数生成ユニット1161を有し、それらは素数生成制御ユニット1102によって起動され制御される。素数生成制御ユニット１１０２の詳細な機能については図4を参照しながら後述する。
【００３１】
フェルマーテストユニット1111は素数候補の素数性を検査する。フェルマーテストユニット1111は３つのメモリレジスタ、即ち、素数候補P1123を格納する一つのレジスタ、レジスタA1121、及びレジスタＢ1122を有する。３つのレジスタは剰余乗算ユニット1113に接続され、剰余乗算ユニット1113はA*B mod P（またはA*A mod P）を計算し、その結果をレジスタA 1121に格納する。この例において、レジスタA、BおよびPを格納するレジスタのサイズは、1024ビットに限られている。結果として、生成された素数は、最大で1024ビットを有する。
【００３２】
フェルマーテスト制御ユニット1102は剰余乗算ユニット１１１３を起動して当該ユニット1113への信号経路を制御し、当該ユニット1113にフェルマーテストを実行させて、素数候補P1123の素数性を判定させる。この機能の詳細については図5を参照しながら後述する。
【００３３】
ビット配列ユニット1113はビットアレイ1141を有し、これはB[0],…,B[b-1]のbビットから成る。ビットアレイ１１４１において各々のビットB[i]は素数候補Pinit+2iを表す。B[i]=0である場合、Pinit+2iは不適当候補であって、拒絶される。しかし、B[i]=1である場合、Pinit+2iは正しい候補であって、更にフェルマーテストユニット1111でテストされなければならない。ビット配列は、ビットアレイフィルユニット1132に従ってフィルされる（満たされる）。ビットアレイフィルユニット1132は、入力として最初の素数候補Pinitおよび小さい素数を採り、ビット配列の適当な位置でゼロを書き込む。ビットアレイフィルユニット1132の詳細については図７を参照しながら後述する。
【００３４】
小さい素数生成ユニット1161は16ビットよりも少ないビット数の小さい素数（スモール素数）を生成し、それは前記不適当は整数を識別するために使用可能にされる。小さい素数生成ユニット１１６１は第1のｔ小さい素数を格納する小さい素数テーブル１１６３を有するが、ミラーラビンユニット１１６２のためのｔ素数よりも多くを生成することができる。その機能についての詳細は図６を参照しながら後述する。生成された小さい素数は16ビットのメモリレジスタ１１７１に格納される。
【００３５】
《素数生成制御ユニット》
図４には素数生成制御ユニット1102の詳細が例示される。初期候補PinitはレジスタP1123にコピーされ、最初にビット配列B[0],…,B[b-1]は全て１にセットされる。ステップ1202、1203および1204において、ビット配列は、テーブルT 1163に格納された第1のt素数によって初期化される。より正確には、ステップ1204で、1つの小さい素数zは、テーブルTから読み出されて、小さい素数レジスタ1171へコピーされる。それから、小さい素数zがビットアレイフィルユニット１１３２によって使用されることにより、ビット配列1141が更新され、適当な位置に０が書き込まれ、不適当な候補が除去される。このビットアレイフィルユニットの詳細は図７に示される。
【００３６】
テーブルT 1163から小さい素数を使用してビット配列が初期化された後、素数生成制御ユニットはビットアレイ1141を調べ、ステップ1213において対応するエントリB[i]が１を含むようにインデックスiを探す。そのようなエントリは整数Pinit+2iを参照しており、その整数は正しい候補であって、更にフェルマーテストユニット1111で更にテストされなければならない。このように、値Pinit+2iはステップ1221でレジスタP1123に書き込まれ、ステップ1222でフェルマーテストの対象にされる。フェルマーテストユニットの機能は図５に記載されている。
【００３７】
ところで、ハードウェア・サイズの限界により、テーブルTは多くの小さい素数を含まず、その結果として、ビットアレイはB[i]=1のようなエントリをまだ多く保有し、そして、素数Pが見つかるまでフェルマーテストは何回も呼び出されなければならない。フェルマーテストの呼出し回数を減らし、素数生成を加速するために、フェルマーテストユニットはステップ1222でアクティブにされたとき、これと同時に新しい小さい素数ｚが生成され、ビットアレイはその新しい小さい素数で更新される。結果として、より多くのエントリはビット配列において0にクリアされ、フェルマーテストの呼出しはより少なくされる。
【００３８】
ステップ1223、1224および1225はそのような新しい小さい素数を生成して、zでビット配列を更新する。それらは、小さい素数生成ユニット１１６１及びビットアレイイニット１１３１によって実行され、素数生成装置1161およびビット配列装置1131によって処理されて、フェルマーテストに並行して実行される。図４において、そのような並列コンピュータ処理は破線の矢印で示されている。
【００３９】
ステップ1223において、小さい素数zの１６ビットのレジスタ1171は、z+2によって更新される。実際、zは奇数であり、偶数の整数は２で割り切れるから明らかに素数でないからである。次に、zはミラーラビンユニット1162を使用して素数性のテストの対象にされる。ミラーラビンユニット1162の機能の詳細は図6に記載されている。ミラーラビンユニットは１６ビット整数の素数性を判定する回路であって、フェルマーテストユニットよりも非常に高速であり、より大きな整数を扱うために構成されている。その結果として、一つのフェルマーテストが実行されている間に複数のミラーラビンテストを行うことが可能にされる。ミラーラビンテストユニットで16ビットの小さい素数が見つかったときビットアレイ1141はビットアレイフィルユニット1132によって更新される（ステップ1225）。これらの３つのステップ1223、1224および1225はフェルマーテストが行われている間繰り返される。
【００４０】
フェルマーテストが終わって、成功したときに、その見込み素数（probable prime）Pは素数生成ユニットによりステップ1231の戻され、他方で、素数生成ユニットは、ビット配列1233のアクティブインデックスをインクリメントし、再びステップ1212から始めることによって、ビット配列の次の正しい候補を探す。ビット配列の全てのインデックスが走査され、素数が見つからなかったときには、素数生成ユニットはステップ1232で失敗を返す。
【００４１】
《フェルマーテスト》
フェルマーテストについて説明する。フェルマーテストは基数Bおよび素数候補Pを入力し、BP-1 mod Pを演算する。仮に演算結果が１でなければ、素数候補Pは合成整数ということになる。演算結果が１であれば、Pはほぼ間違いなく素数ということになる。BP-1 mod Pはデータ処理上高コストの処理であり、ビット配列で多くの不適当な候補が除去されるときでも、フェルマーテストの対象にされるべき多くの正しい候補がまだ残っている。その意味で、フェルマーテストにおける処理速度の改善は非常に魅力的である。
【００４２】
累乗演算のパフォーマンスを向上させる周知の方法は、ウインドウ方法を使用することである。ウィンドウ・サイズwを有するウインドウ方法において、ベキ指数からのwビットが同時に走査される。換言すれば、ベキ指数（それは通常メモリのそのバイナリの表現に保存される）は2wベースで再符号化（recoded）される。これらのwビットは整数ｊ（0＜=j＜2w）を表し、データBj mod Pが予め計算され、そしてウインドウ累乗技術ではA2 mod PおよびA*Bj mod Pが演算される。その代わりに標準のバイナリ法を用いると、A2の演算は同じであるが、w/2 の乗算が新たに必要になる。従ってウインドウ方法は乗算回数を減少させることができる。
【００４３】
しかしながら、ウインドウ方法によって必要な予め演算された値は、RAMに保存されなければならない。ICカードにおいて、RAMの記憶容量は制限される。そして、1024ビットの累乗の場合、上記予め演算された1つの値は128バイトを占める。そして、最適化されたウインドウ方法はしばしばこの種の幾つもの予めコンピュータ演算された値を使用する。これはICカードにとて現実的ではない。たとえば、ウィンドウ・サイズw=5の場合、予めコンピュータ演算された必要な値はRAM上で約4キロバイトを占有することになる。
【００４４】
本発明に係るフェルマーテストは、コンピュータ演算されたデータを記憶するためにメモリが要求されることなく大きなウインドウのウインドウ法を利用可能にするものである。フェルマーテストでは、BP-1 mod Pの演算においてBに特別な基数、特にB=2、を用いることが一般的である。この場合、大きなwのためでさえ、Bj mod P. の値を予めコンピュータ演算したり保持したりすることを要しない。例えば、w=10、j＜210=1024、およびBj =2j ＜ 21024、と仮定する。さらに、Bj =2jが、二進数表記で（1000…000)2として与えられ、その二進数表記においてビットポジションｊで“１”になっている。その結果、予め演算されたテーブルが必要とされない。すなわち、ビット位置ｊに“１”を立て、残りのビット位置を“０”で埋めればよい。
【００４５】
図５にはウィンドウ・サイズをw=10としたときにその考え方の詳細が例示される。これに基づいて説明を続ける。
【００４６】
ステップ1302において、ベキ指数P-1の最初の10のビットが走査されて、バッファjに書き込まれる。カウンタiはp-11に初期化される。そのカウンタの値は次に読むべきビット、即ちPp-11に一致されている。ステップ1303において、アキュムレータA（レジスタA）1121は、2jにセットされる。即ち、Aには最初0が書かれ、ｊ番目のビットは1にセットされる。
【００４７】
その後、べき乗演算が開始される。ステップ1312において、剰余乗算ユニット1113で10回連続してA2 mod Pが演算される。ウィンドウ・サイズがw=10だからである。ステップ1313では連続する10ビットPi,…,Pi-9がべき指数P-1から読み込まれる。ここで、Pはレジスタ1123に格納されており、整数値（Pi…Pi-9)2はバッファjに書き込まれる。jがゼロである場合、乗算は必要とはされず、フェルマーテストでは次の処理を続けることができる。ｊ＞0である場合、レジスタB 1122はステップ1322において2jにセットされる。すなわち、レジスタB1122はゼロにクリアされそのｊ番目のビット位置には1がセットされる。一旦レジスタB 1122がセットされると、A*B mod Pの剰余乗算がステップ1323で剰余付き演算操作ユニット1113を用いて実行される。最後に、ステップ1331で、ベキ指数の走査されたビットPiの位置を表しているインデックスiから10が減じられる。iが9より大きい限り（最も右の走査されたビットPi-9かP1以上であることを保証する）、上記のステップは繰り返される。
【００４８】
iが9より小さくなるときに、フェルマー試験は別に最後の残りのビットを扱う。ステップ1341において残りのビットの値（Pi…P10)2は、バッファjに書き込まれる。Pは奇数であるから、P-1は偶数でありその最下位ビットは0であることに着目する。次に、i+1回A2 mod Pが剰余乗算ユニット1113で演算される（ステップ1342,134）。その後、レジスタB 1122は、最後の乗算の準備ができている。即ち、それは0までクリアされ、そして、そのｊ番目のビットはステップ1351で1にセットされる。その結果、レジスタB 1122にはそのステップ後に値2jが格納される。最終的な剰余乗算A*B mod Pは、ステップ1352で計算される。ステップ1361においてアキュムレータレジスタA 1221が値1を含む場合、Pが見込み素数（probable prime）であるので、フェルマー試験は「成功」を出力して処理を終了する。もしもレジスタAが他の値も含む場合には、Pは合成数であるから「失敗」を出力して処理を終了する。
【００４９】
《フェルマーテストの具体例》
この例では整数P=1971577が素数定判テストに供されるものとする。ここで、Pの値は16進法で表される。二進数において、Pは21ビットでP=(111100001010101111001)2とする。jの第1の値は、Pの最上位側の10ビット、すなわち、j=(1111000010)2=962となる。Aは2962即ち2進標記で末尾に962個のゼロを伴った(1000…000)2に初期化される。カウンタiは10にされる。この後、10回連続的にA2 mod Pの演算が行われ、これによってAは値824444を含むことになる。
【００５０】
次の10ビットは、j=(1010111100)2=700である、したがって、2700がレジスタBに書き込まれ、そして、A*B mod Pが計算される。ここでA=824444、B=2700およびP=1971577である。この演算結果は1であり、そして、その後にもう一度二乗演算が行われる。したがって、累乗の最終結果は1であり、それは実際に1971577が素数であることを意味する。
【００５１】
これにより上記フェルマーテストでは乗算に関して11回の二乗演算（squares）と1回の乗算(multiplication)だけしか要求されないことが明らかであり、これに比べてバイナリ法では20回の二乗演算と11回の乗算が要求されることになるであろう。
【００５２】
今度は整数P=1686499=(110011011101111100011)2について考える。j=(1100110111)=823なので、Aは2823に初期化される。10回連続的にA2 mod Pの演算が行われると、Aは値129007を含み、、次の10ビットはj=(0111110001)2=497である。値2497はBに書き込まれ、そして、剰余乗算A*B mod Pが計算される。その演算結果はA=217983である。そして、最後にもう一度二乗演算が行われる。最終結果は1165463であり、1とは異なり、Pは素数ではない。実際に、P=1686499=1093*1543であり、Pは合成数である。
【００５３】
《ミラーラビンテスト》
ミラーラビンテストとフェルマーテストの両方が素数性の確率的な判定テストである。仮のそれらのテスト結果が失敗あるなら、テストされた整数は絶対的に合成数であるといえる。しかしながら、テスト結果が成功ある場合は、テストされた整数は多分素数であると推定されるだけであり、絶対的に素数であるとは言えない。両方のテストにとって、その結果を失敗とする多くの整数、即ち合成数が存在するが、それには時々そのテストで成功の結果を出す合成数を含んでいる。幸いにも、そのような合成数は多くは無い。特にミラー-ラビンテストの場合には非常に少ない。特に、基数２を用いるミラーラビンテストでそのような誤りを生ずる１６ビット整数ｚは2047, 3277, 4033, 4681, 8321, 15841, 29341, 42799, 49141, 52633である。結果として、ミラーラビンテストが上記の整数の一つでもない１６ビット整数zに対して「成功」のテスト結果を返すならば、そのｚは絶対的な確実性を持って素数であるといえる。
【００５４】
本質的には、ミラーラビンテストはフェルマーテストと類似している、しかし、重要な違いがある。テストする整数はzであり、z-1は2j+1*dと記述され。ここで、j+1はz-1のバイナリ標記における下位側のビットゼロの個数である。基数２を用いるミラーラビンテストのために、剰余累乗乗算x=2d mod zが計算される。もしも、その演算結果が1又はz-1であるならば、テスト結果は「成功」であり、ｚはたぶん素数と言える。そうでない場合にはxはj回乗算され、それぞれの乗算後にｘは再びz-1と比較される。それらが一致する場合は、テストは「成功」を返す。もしもj回乗算後、xがz-1に決して等しくない場合は、テストは「失敗」を返し、zは合成数となる。
【００５５】
図６にはレジスタ1171に保存される16ビットの整数z=(z15…z0)2の素数判定にミラーラビンテストを適用した場合が示される。zが2047、3277、4033、4681、8321、15841、29341、42799、49141、52633のいずれかである場合、zは合成数であり、ステップ1403で「失敗」を返す。さもなければ、z-1の2進表現における末尾のゼロの個数であるjがステップ1404から1406で算出される。累乗の剰余乗算2dのmod z（そこでz-1=2j+1*d）がステップ1411から1416で実行され。アキュムレータxは１に初期化され、ステップ1411でループカウンタiは１５に初期化される。次に、ループカウンタiがjより大きい間、次のステップが実行される。先ず、ステップ1413で剰余乗算x2 mod zが実行される。ここで、xおよびzは１６ビット整数である。その後、zのビットziが1である場合、演算2*x mod zは、左シフトx << 1および法数zの減算を使用してステップ1415で計算される。
【００５６】
累乗計算の後、アキュムレータxが値1を含む場合、アルゴリズムは動作を停止してステップ1441でテスト結果「成功」を返す。そうでない場合には、xはステップ1431でz-1と比較される。それらが等しい場合、アルゴリズムは動作を停止してステップ1443でテスト結果「成功」を返す。等しくない場合、剰余乗算x2 mod zがステップ1432で演算され、ループカウンタは減算される。上記操作はカウンタiが1になるまで繰り返される。アキュムレータがz-1に決して等しくなかった時は、アルゴリズムはステップ1442でテスト結果「失敗」を返す。
【００５７】
《ミラーラビンテストの具体例》
小さい素数テーブルT 1163には、17個の第1小さい素数T[0]=3、T[1]=5、T[2]=7、T[3]=11、T[4]=13、T[5]=17、T[6]=23、T[7]=29、T[8]=31、T[9]=37、T[10]=41、T[11]=43、T[12]=47、T[13]=53、T[14]=59、T[15]=61、T[16]=67が格納されていると仮定する。小さい素数かもしれいな整数はｚ=69=(0000000001000101)2である。ｚは基数2を用いるミラーラビンテストを欺くことができる16ビット整数の一つでは無いから、テストは、z-1=(0000000001000100)2における末尾の０の数から1を引いた数であるｊ、即ちj=1を伴った計算から始めることができる。次に、アキュムレータxは１に初期化され、カウンタiは15に初期化される。i=6までは、z-1の走査されたビットが全てゼロであり、アキュムレータの値は修正されない。繰り返しi=6において、xはステップ1415の左シフトの後に2になり、その後、4回二乗演算と1回の左シフトが行われる。その結果として、ステップ1422では、xは値41を採る。xが1または68と異なるので、もう1回二乗演算が行われ、xは25になり、まだ68とは異なる。この時点で、テストは「失敗」を返す。これは、z=69=3*23が合成数だからであると予想される。
【００５８】
次の奇数は、z=71=(0000000001000111)であり、この場合、j=0である。i=6までは、xは同じままにされ、即ちx=1のままであるが、i=6の1ビット左シフトの後、xは2になる。その後、4回の二乗演算が行われてx=3、1ビットシフトが行われてx=6、1回二乗演算が行われてx=36、そして、1ビットシフトが行われ、最後に、xは1になる。結果として、試験はステップ1422で停止され、x=1、z=71で素数とされる。
【００５９】
《ビット配列の更新》
ビット配列は、小さい素数によって割り切れた候補P=Pinit+2iである合成数を除去するためのエラトステネス（Eratosthenes）のふるいによって示唆される周知の方法である。ビット配列法の大まかな考えは、小さい素数ｚのためにPinit mod zを計算して、P=Pinit+2i mod z = 0（Pはｚによって割り切れる）のような全ての位置iのためのビット配列においてB[i]に0を書き込むことである。図7にはビット配列の適当な位置でゼロを書く方法が説明されている。
【００６０】
ビットアレイフィルユニット1132への入力は、ビット配列1141、初期候補Pinit 1103および小さい素数z 1171から成る。最初に、バッファxはステップ1513で値Pinit mod zによって初期化される。この演算は計算が容易である。その理由は、次のことにある。Pinitが大きな整数であるにもかかわらず、zは単に16ビットだからである。次に、ビットアレイフィルユニットは、Pが奇数でP mod z=0であるような第1の整数P=Pinit+2iを計算する。Pinit mod z=0である場合、Pinitは全ての状態を満足しインデックスiがステップ1515で0にセットされる。一方、xはゼロでなく、Pinit=x mod z、Pinit+z-x=0 mod zだからそれを分かることは容易である。一方、xが奇数なら、z-xは偶数であり、Pinit+z-xは奇数であり、要求される全ての状態を満たす。その結果、ステップ1522では、値（z-x）/2は、減算と右シフト（z-x)>>1を用いてバッファiに書き込まれる。他方、xが偶数の場合、Pinit+z-xは同様に偶数であるが、Pinit+2z-xは奇数である。したがって、ステップ1523で、減算と右シフトz-x>>1を用いて値（2z-x）/2=z-x/2がバッファに書き込まれる。
【００６１】
次に、奇数のPinit+2iがPinit+2=0 mod zを満足するだけでなく、Pinit+2(i+z)、Pinit+2(i+2z)、Pinit+2(i+3z)もそうである。したがって、ステップ1532では、配列において最も大きな可能性のあるインデックスbよりi+k*zが小さいというような全てのインデックスi+k*zのために、ビットB[i]はゼロにクリアされる。最後に、ビットアレイフィルユニットはステップ1551でビット配列を返す。
【００６２】
《ビット配列更新の具体例》
この例では、ビット配列1141はサイズb=64を有し、そして、小さい素数テーブル1163は16の小さい素数、すなわち、T[0]=3、T[1]=5、T[2]=7、T[3]=11、T[4]=13、T[5]=17、T[6]=23、T[7]=29、T[8]=31、T[9]=37、T[10]=41、T[11]=43、T[12]=47、T[13]=53、T[14]=59、T[15]=61）を格納する。最初の候補1103の入力は512ビットの奇数であると仮定する。例えば、
Pinit=7256779693106507655490693859171076267003739588425074050256021409526725926274029082141310206427691245639055995711774350480838509929519895128627108485116697、
である。
【００６３】
まず最初に、ビット配列は、ビット1だけを含む。換言すれば、Bが整数として表現される場合、そのバイナリの表現は、
B=(1111111111111111111111111111111111111111111111111111111111111111)2
となる。Bは64ビットから成る。最初に、素数生成制御ユニットは、小さい素数テーブルT[0],…,T[15]を使用しているビット配列の適当な位置にゼロを書き込む。例えば、T[0]=3およびPinit mod 3 = 1である。1は奇数であり、それ故に、そのビットアレイにおいて(3-1)/2=1の位置で０を書き、そして、位置1+3=4および4+3=7の位置でそうする。T[0]=3によって篩にかけた後に、ビット配列は、
B=(1011011011011011011011011011011011011011011011011011011011011011)2
になる。テーブルTの全ての小さい素数のためにその手順を繰り返して、ビット配列は、
B=(1001011000000001010011000010000001010010000001011001000010000010)2
になる。これによって、フェルマーテストで18ビットだけはまだ1にセットされることが確かめられる整数Pinit+2iに対応する、より小さいインデックスiの値があることが解る。B[0]=1だから、Pinitはフェルマーテストで確かめられなければならない。
【００６４】
同時に小さい素数生成ユニット1161は次の小さい素数を探す。１６ビットレジスタz 1171は、そのテーブルにおいて最後の小さい素数（すなわち、61）を格納する。次の奇数の整数63はミラーラビンユニット1162で照合される。そして、63は素数でないと結論する。63=3*21だかである。同様に、65は素数でない。65=13*5だからである。しかしながら、ミラーラビンユニットは、67が素数であると結論する。
【００６５】
その後、ビット配列は、z=67によって更新される。Pinit mod 67=24であり、ビットアレイにおいて67-24/2=55の位置で０が書き込まれる。残念ながら、B[55]はすでに0である。したがって、67によって篩にかけることはこの例でいかなる好転にもならない。事実、これは次の小さい素数71、73、79、83、89、97および101と同じことである。しかしながら、小さい素数z=103がミラーラビンユニット1162によって生成されるとき、演算Pinit mod 103は13を与え、これはインデックス（103-13）/2=45に対応する。したがって、その前に1であったB[45]に0が書き込まれる。ビットアレイは、
B=(1001011000000001010011000010000001010010000000011001000010000010)2
になる。
【００６６】
フェルマーテスト1111がステップ1222で行われている限り、その手順は継続される。ミラーラビンテストは短い整数（16ビット）で処理するのに対して、フェルマーテストは長い整数（この例では512ビット）を処理するから、多くの小さい素数はフェルマーテストが行われている間に生成可能にされ、追加されたものが除外可能にされる。例えば、フェルマーテストで512ビットのそれぞれの剰余乗算のために一つの小さい素数が生成可能にされることを仮定すると、そのフェルマーテストの間に512の小さい素数が追加して生成可能にされる。その場合、ビット配列は、
B=(0001011000000000000000000000000001000010000000011000000010000000)2
になる。その果として、最初のフェルマーテストの後、ビットアレイには８個が残されるだけとなる。
【００６７】
最初のフェルマーテストは入力としてPinitを採る。しかしながら、累乗の演算2^(Pinit-1) mod Pinitの結果は1ではない、したがって、Pinitは素数ではない。次のビットアレイのゼロ以外のエントリはB[3]であり、次の素数候補はPinit+6である。即ち
P=7256779693106507655490693859171076267003739588425074050256021409526725926274029082141310206427691245639055995711774350480838509929519895128627108485116703
である。値Pinit+6はレジスタP 1123に格納される、そして、フェルマーテストは2^(Pinit+5) mod Pinit+6の計算を始める。累乗計算の間、新規な小さい素数がビット配列における多くのゼロ以外のエントリを除去するために生成されることができる。しかし、この例では、512の追加的な小さい素数についてさえ、どんなゼロも配列には書かれない。幸いにも、第２のフェルマーテスト2^(Pinit+5) mod Pinit+6の結果は1であり、実際に、Pinit+6は素数である。この点で、素数生成ユニット914は、Pinit+6の値を返す。
【００６８】
《拡張》
本発明は、上記の実施の形態１で説明した内容に限定されない。例えば、上記システムは、携帯電話、ＰＤＡ、そして公開鍵暗号方式を利用して限られた計算機リソースやメモリリソースを用いる如何なる電子デバイスにも使用されることが可能である。累乗のタイプは異なることがありえる。例えば、累乗の剰余乗算ユニットの代わりに、モンゴメリー乗算装置が利用されることも可能である。小さい素数の再構成の方法は、上記の例で説明した内容に限定されない。例えば、２とは異なる基数を伴ったミラーラビンテストを利用したり、フェルマーテストやその他のコンビネーションテストのような異なったテストを利用したりすることも可能である。同様に、ミラーラビンやスロベイストラーゼン(Solovay-Strassen)テストのように、素数候補に対する異なった素数性判定テストも採用可能である。、更に、再構成の種類はウインドウ方法に限定されず、NAF（Non Adjacement Form）又はFANの再構成法、或いは、その他の適当な再構成法を用いることも可能である。
【００６９】
３．実施の形態２
オンボードの暗号生成に着目した説明を行う。
【００７０】
《携帯機器》
図８には携帯式電子装置（携帯機器）101が示され、例えばICカード、或いはセキュリティ機能が強化されたデバイスである。携帯機器101は、その入出力インタフェース131を介してネットワーク141に接続され、データ142を送り、データ143を受信することができる。このネットワーク141を通して、携帯機器10はATM 151、コンピュータ153又は他の携帯機器154と通信することができる。ネットワーク141の上の通信路でのセキュリティがなければ、メッセージは悪意のあるユーザによって横取りされることがある。したがって、携帯機器にはセキュリティ機構が搭載される必要がある。これらのセキュリティ機構は、メッセージ暗号化およびデジタル署名を含み、そして、実施の形態２では、事実上の標準であるRSAと称される公開鍵暗号法が適用される。
【００７１】
携帯機器101は、3種類のユニットとして、入出力インタフェース131、計算ユニット121およびメモリ111を含む。
【００７２】
入出力インタフェース131によって携帯機器は1または幾つかのネットワークに接続可能である。実施の形態2では、携帯機器101は2つの入出力インタフェース132および133を含む。それは接触インタフェースと非接触インタフェースを実現する。データ処理部121はＣＰＵ 122、モンゴメリー乗算コプロセッサ123および乱数発生器124を含む。ＣＰＵ（央演算処理装置）は、32ビット命令が適用され、それはメモリ操作命令、加算、減算、乗算または除算などのような算術命令、シフト、ANDまたはOR等の論理演算命令、そして制御命令を含む。ＣＰＵは、32ビット命令からなるプログラムを実行することが可能である。概して、ＲＳＡ関連の動作は、512ビット以上のかなり大きな整数を操作する。この種の大きい整数算術演算処理がＣＰＵ 122によって実行されるプログラムとして適用されることについては、実際的ではない。携帯機器は非常に限られた計算機処理能力しか持たないからである。そういうわけで、携帯機器は、モンゴメリー乗算コプロセッサ123のような専用の計算ユニットをＲＳＡのために備えている。モンゴメリー乗算コプロセッサはレジスタA 115、B 116およびN 117にインタフェースされ、そのレジスタ117がn-ビット奇数の整数を保有する場合、モンゴメリー乗算A*B*2-n mod Nまたはモントゴメリー乗算A*A*2-n mod Nを計算する。ここで、それぞれ、整数AおよびBはレジスタ115および116に保存される。乱数発生器124はランダムなビットを連続的に生成することができる。そして、それはＲＳＡを含む暗号アプリケーションのために使用可能にされる。
【００７３】
3種類のメモリ111は次のように区別される。バッファデータ及びテンポラリデータを格納するための揮発性メモリ112、ユーザデータの格納に利用される書き込み可能な不揮発性メモリ113、プログラムの格納に利用されるリードオンリ不揮発性メモリ114である。3つのモンゴメリー乗算レジスタA 115、B 116およびN 117は、モンゴメリー乗算コプロセッサ123と接続される基本的に揮発性メモリである。実施の形態２において、揮発性メモリにはRAM（ランダム・アクセス・メモリ）が適用され、書き込み可能な不揮発性メモリにはEEPROM（電気的に消去可能ＰＲＯＭ）が適用され、リードオンリの不揮発性メモリにはマスクＲＯＭ（読出し専用メモリ）が適用される。
【００７４】
特に制限されないが、実施の形態２では実施の形態１で説明した暗号化ユニット911に対応する構成をソフトウェア的に実現することを想定している。即ち、不揮発性メモリ114等に必要なプログラムが格納され、これをデータ処理部121のCPU122等が実行することによって、後述するフローチャートに示される処理が行われる。
【００７５】
《ＲＳＡの鍵ペアの生成》
メッセージをデジタル的に署名するかまたは解読するために携帯機器101上のＲＳＡ暗号システムを使用する前に、ＲＳＡ 鍵ペア（keypair）を発生しなければならない。上記したように、携帯機器上で鍵ペアを生成することは有意義である。図9にはその手順が詳細に記載されている。鍵ペア生成の入力201は、n（公開法数Nのビット長）、p（秘密素数Pのビット長）、q（秘密素数Qのビット長）、E（公開べき定数）、b（1ビットアレイのサイズ）、予め定められたテーブルT[0],…,T[t-1]）、及びmri（ミラーラビン繰り返しの数）を含む。
【００７６】
ビット配列B[0],…,B[b-1]、テーブルT[0],…,T[t-1]およびミラーラビン繰り返しの数の役割は、後で説明する。ステップ202において、2つの最初の奇数の乱数PinitおよびQinitが乱数発生器124によって発生される。鍵ペアの生成手順は、[ Pinit,…,Pinit+2(b-1)]と[ Qinit,…,Qinit+2(b-1）]の間で素数PおよびQを探しそうとすることである。したがって、ステップ203は、検索間隔が常に正しい範囲であることを保証し、それぞれ、PおよびQはｐビットとqビットを有することを保証する。ステップ204において、結果Pinit*Qinitが正確にnビットを有することが確かめられる。これが正しいなら、法数N=P*Qは確実にnビットを有する。ステップ203または204のいずれかが失敗の場合、新たに最初の乱数PinitおよびQinitがステップ202で発生される。
【００７７】
一旦最初の乱数PinitおよびQinitが全ての要求される状態を満たすと、素数生成手順が始まる。bビットのビットアレイB[0],…,B[b-1]はRAM 112に保存され、ステップ211で初期化される。ビットB[i]は、整数Pinit+2iに対応する。整数Pinit+2iが全て奇数である。Pinitが奇数で、2iが偶数だからである。実際、素数生成手順のゴールは、間隔[ Pinit,…,Pinit+2(b-1)）]で素数を見つけることである。偶数は明白に素数ではなく、問題なく無視することができる。ビット配列で1にセットされるビットB[i]は正しい候補であり、それは更に素数性が判定されなければならない。ゼロにクリアされるビットB[i]は素数で無いことが知れた不適な候補に対応される。まず最初に、全ての候補はステップ211で「正しい」にセットされ、そして、ステップ212では、不適な候補にはビットアレイでゼロが書き込まれ、それらの処理は図１１に記載されている手順で行われる。ステップ212で不適な候補が除外された後、残りの正しい候補はステップ213で素数性が判定され、それによって、素数P及びDP*E =1mod P-1のような逆元DPが出力され、又は「失敗」が返される。ステップ213は図１０にその詳細が示される。素数Pが見つかる場合、ステップ221からステップ224で最初の候補Qinitに対して同じ手順が繰りお返される。ステップ214または224において「失敗」の場合には、新たな初期乱数PinitおよびQinitがステップ202で発生される。
【００７８】
2個の素数PおよびQが見つかった後、D*E=1 mod（P-1)*(Q-1)を満足する秘密鍵Dと、公開法数N =P*Qがステップ231において算出される。公開法数Nはモンゴメリー乗算コプロセッサ（単にコプロセッサとも記す）123で計算されることができ、公開鍵Dは非特許文献1に記載されている周知のバイナリ拡張GCDアルゴリズムによって計算されることができる。RSA-CRT Qinvの秘密鍵要素は、Pが素数だからQ-1=QP-2 mod Pになるという事実を用いてステップ232で算出される。べき乗の剰余乗算QP-2 mod Pはモンゴメリー乗算コプロセッサ123を使用して算出されることができる。例えば、特許文献１に記載されているモンゴメリー累乗アルゴリズムを使用する。最後に、公開法数N、秘密鍵D、秘密鍵要素RSA-CRT P, Q,DP,DQおよびQinvを含む全ての鍵素子は、ステップ233でEEPROM 113に書き込まれる。
【００７９】
《素数生成》
図9において、ステップ213および223では、素数P及びQ、秘密鍵素子DP =E-1mod P-1、DQ =E-1mod Q-1が発生される。この素数生成手順に対する入力301は、最初の偶数乱数Pinit（またはQinit）、公開ベキ指数E、ビット配列B[0],…,B[b-1]）、及びmri（ミラーラビンテストのための繰り返しの数）である。
【００８０】
ステップ302において、RAM 112に格納されたカウンタiは0に初期化される。このカウンタは、ビット配列B[i]の要素をアドレシングし、素数候補Pinit+2iを表すために用いられる。ステップ311および312において、ビット配列B[i]のエントリが、走査される。B[i]=1のとき、候補Pinit+2iは「正しい」とされ、更に次のステップでの素数性が判定されなければならない。B[i]=0のときは、候補は「不適」とされ、次の候補がテスト対象にされる。
【００８１】
ステップ321において、候補P=Pinit+2iがＣＰＵ 122で演算されて、演算結果がコプロセッサレジスタ117に格納される。次に、ステップ322でフェルマーテストを用いてPの素数性が判定される。フェルマーテストに付いては図6に記載される。Pがフェルマーテストをパスすることができる場合、Pは実際に素数であるという十分な可能性がある。
【００８２】
しかしながら、Pは更なる状態を満たさなければならない。すなわち、P-1と公開ベキ指数Eの最大公約数は、逆元DP=E-1 mod P-1が存在することを確実にするために、1（gcd(P-1,E)=1）でなければならない。したがって、ステップ331で、例えば非特許文献1に記載のバイナリ拡張GCDアルゴリズムを使用してDPが算出される。手順が「失敗」の場合は、gcd(P-1,E)が1でなく、Pは拒絶され、次の候補がテストされる。
【００８３】
フェルマーテストは合成数とされる候補を早く除外するために有用であるにもかかわらず、それは良好な確実性をもってそれらの素数を確立するには十分でない。例えば、カーマイケル番号と呼ばれている合成数が存在し、それは多くの場合フェルマー試験にパスすることができる。高い信頼性をもってPの素数性を保証するために、実施の形態２はフェルマーテストがうまく行った後でさ、数回、ミラー-ラビンテストを繰り返す。繰り返し数（mri）は、適切に選択されなければならない。非特許文献１は、繰り返し3回ミラーラビンテストをうまくパスすることができる1024ビットのランダム整数が素数でないという確率は2-80であると述べている。換言すれば、3回のミラーラビンテストをパスする候補を選んだときエラーが起きる確率は2-80である。それはごくわずかである。ステップ341において、カウンタjが、RAM 112上で0に初期化される。jが繰り返し数mriより小さい限り、図14に記載のミラーラビンテストがステップ342で実行され、カウンタjがステップ343でＣＰＵ 122によりインクリメントされる。Pがミラーラビンテストをmriで示される回数成功したならば、Pは多分素数であり、素数生成手順によってステップ351で、逆元DPとともに選ばれる。しかしながら、ビット配列、フェルマーテスト、逆、ミラーラビンテストのいずれかが失敗する場合、iはステップ361でインクリメントされ、次の候補Pinit+2i+2がテストされる。間[ Pinit,…,Pinit+2(b-1)]における手順で満足な素数が見つからなかった場合には、手順はステップ352で失敗となる。
【００８４】
《ビットアレイ》
tのための最適値があり、それは、素数生成手順の速度を最大にするように篩にかけるために使われる小さい素数の数である。即ち、一方において、より小さな素数で、ビットアレイからより多くの要素が篩にかけられることができ、それはより洗練された素数判定テストを呼び出す回数を減らし、他方において、より小さな素数ｚを使用することはビットアレイにおけるP mod zと書き込み操作の減少に帰結する。しかしながら、小さな素数の最適数は、典型的に大きく、1,000以上である。
【００８５】
多くの小さい素数が篩にかけるために使われるときに、大きなテーブルはそれらを格納するために必要である。簡潔に説明するために、素数ビット長に従い、それぞれの小さい素数は、1バイト（8ビット）または2バイト（16ビット）で格納されることができる。残念なことに、8ビットの素数は多くない。小さい素数テーブルにおける要素のほとんどはROM 114の2バイトを占める。例えば、2,048の素数が篩にかけるために使われる場合、テーブルはROM 114に4キロバイトを占める。それはICカードにとって非常に大きなサイズである。
【００８６】
さらに、zが小さい素数のオペレーションPinit mod zはコプロセッサ123で計算される、しかし、zが小さいにもかかわらず、Pinitは大きい。したがって、コプロセッサ123で計算されるモンゴメリー乗算のビットサイズは、Pinitのビットサイズであるｐによって決まる。その結果として、モンゴメリー乗算の結果は、MontMult(Pinit,1,z)=Pinit*2-p mod zである。そして、それは所望の結果Pinit mod zとは異なる。その代わりに、操作MontMult(Pinit,2p mod z、z)=Pinit*2p*2-p = Pinit mod zが計算されなければならない。結果として、モンゴメリー定数の表が必要になり、それは全ての小さな素数zのための全てのモンゴメリー定数2p mod zを保有する。2,048の小さい素数の場合、これは小さい素数のために４キロバイトおよびモンゴメリー定数のための4キロバイトのメモリを必要とする。更に悪いことに、モンゴメリー定数は素数候補Pのビット長ｐに依存する。例えばプログラムが1024ビットおよび2048ビットのＲＳＡをサポートしなければならない場合、モンゴメリー定数のために2個の異なったテーブルが必要になる。
【００８７】
上述の説明より、篩いがけのために多数の小さい素数を用いることが必要とされることは容易に理解されるとところであるが、このアプローチはICカードの不十分なメモリ資源に殆ど適合しない。実施の形態2では、多数の小さい素数が使われるが、必要なメモリ量をICカードにとっても合理的であるようにする。課題を解決するポイントは二つある。第1は、それらの全値よりもむしろ連続する小さい素数の間の相違を格納することである。第2は、それらを格納することよりもむしろ実行時にモンゴメリー定数2p mod zを演算することである。
【００８８】
上記第１ポイントにより、小さい素数を格納するためのメモリ容量は半減する。何故ならば、2個の連続する小さい素数の間の相違は通常小さく、2バイトではなく1バイトで格納可能にされるからである。実際に、1バイトで格納されることができる2つの連続的な素数間の最大の差はΔ=118であり、z1=1,349,533とz2= 1,349,651の間で生ずる。換言すれば、z1=1,349,533より小さい素数間での違いは、常に1バイトに格納可能である。
【００８９】
第2ポイントによる利点は、メモリの要求容量がモンゴメリー定数に対して全く除去されるということである。加えて、充分なスケジューリングを伴って、CPU122によって計算されるモンゴメリー定数の演算が、コプロセッサ123によって演算されるモンゴメリー乗算 MontMult(Pinit,2p mod z,z)の処理に並列化できる。
【００９０】
したがって、実施の形態２のアプローチとt=2,048の小さい素数を用いることは、小さい素数間の差のテーブルT[0],…,T[t-1]をＲＯＭ114に格納するのに必要なメモリ容量を２キロバイトとし、篩い操作に対して動作速度上のペナルティーを課すことはなく、また、処理コストの大きな素数判定処理の呼出し回数の減少に起因して処理効率を好転させることができる。
【００９１】
次に、図１１にはビットアレイフィルの操作手順の詳細が例示される。ステップ401の入力は、pビットの初期奇数乱数Pinit（またはqビットのQinit）、最初に１で満たされたビット配列B[0],…,B[b-1]）、及び、連続する小さい素数間の相違を格納するテーブルT[0],…,T[t-1]、から成る。例えば、テーブルTがt=4の小さい素数に関する情報を格納すると仮定する。T[0]=3は、2より大きな第1素数例えば３をを格納する。次の素数は5=3+2であるからT[1]=2である。次の素数は7=5+2であるからT[2]=2である。次の素数は11=7+4であるからT[3]=4である。ステップ402において2個のバッファz1とrはRAM112において初期化される。前記バッファｚ１は第1素数T[0]の値を格納し、バッファrは第1のモンゴメリー定数2p mod T[0]である。r=2p mod z1の計算は、図12に記載されている。次に、z1はコプロセッサレジスタN 117にコピーされ、rはレジスタA 11５に、PinitはレジスタB116に、コピーされる。その後、コプロセッサ123はMontMult(r,Pinit,z1)の演算を開始する。計算が終わると、演算結果Pinit mod z1がRAM 112のバッファx1に書き戻される。コプロセッサ123がMontMult(r,Pinit,z1)の演算を処理中には、第2の小さい素数およびモンゴメリー定数がＣＰＵ 122によって用意される。第2の小さい素数はz1+T[1]であり、ここで、T[1]は第1素数と第2素数の間の差を格納する。
【００９２】
この次のステップにおいて、ビット配列はテーブルT[0] …,T[t-1]によって再構成された全ての小さい素数を使用して更新される。テーブルT[0] …,T[t-1]はその構成要素をインデックスするカウンタiを使用する。ビット配列の更新手順の基本的な考え方は以下の通りである。即ち、第1に、コプロセッサ123でx2 = Pinit mod z2を計算し、ここで、z2はテーブルTでインデックスiを有するアクティブな小さい素数に対応する。第2に、第1の処理と同時に、CPU122がインデックスi+1に対応する次の小さい素数z3を演算する。第3に、ビットアレイはx1 = Pinit mod z1で更新され、ここで、z1はインデックスi-1に対応する前の小さい素数である。
【００９３】
ステップ412において、Pinit mod z2はコプロセッサ123で計算される。ここで、z2はインデックスiに対応する小さい素数である。より正確に言うと、小さい素数z2はコプロセッサレジスタ117へコピーされ、モンゴメリー定数がコプロセッサレジスタ115へコピーされ、レジスタ116はすでにPinitを保持している。次に、コプロセッサはMontMult(r,Pinit,z2)の演算を開始し、その演算結果はRAM 112のバッファx2に格納される。同時に、ステップ414において、CPU12による演算z3=z2+T[i+1]のためにテーブル要素T[i+1]がアクセスされる。ここで、z3はインデックスi+1に対応する次の小さい素数ある。そのモンゴメリー定数2p mod z3は同様に計算される。i=t-1又はi=tのときステップ414の処理はスキップされる。テーブルTはt要素だけを有するからである。
【００９４】
この状態で、ビットアレイは前のステップi-1で演算された値x1=Pinit mod z1で更新される。x1=0である場合、Pinitはz1で割り切れ、そして、ステップ432でゼロが直接B[0]に書き込まれる。x1が奇数の場合、P=Pinit + z1 - x1はP=0 mod z1を満足する。加えて、Pinit、x1およびz1は奇数であり、それゆえにｐは奇数である。そして、Pに対応するインデックスjはj=(z1-x1)/2であり、これは、ステップ423で、２による割り算に代えて右シフトを用いてCPU122により演算される。X1が偶数なら、Pinit + z1 - x1は偶数であり、ビットアレイの要素ではない。その代わりに、次の奇数が選ばれる。すなわち、P = Pinit + 2z1 - x1である。対応するインデックスはステップ423でＣＰＵ 122による右シフトを用いてj=z1 - x1/2として計算される。
【００９５】
ステップ422または423が実行された後、Pinit +2j= 0mod z1のような第１のインデックスjは既に有効になっている。しかし、実際には、整数Pinit+2j+2z1、Pinit+2j+4z1、Pinit+2j+6z1およびその他もz1で割り切れる。したがって、ステップ432で、ゼロがビットB[j]に書かれ、jが範囲[ 0,…,b-1]にある限りＣＰＵ 122によってz1がインデックスjに追加される。そのように、Pkにような全ての奇数Pk=Pinit+2*k*(j+z1)はビットアレイに存在し、Pk mod z1=0が「不適当」な候補として識別される。
【００９６】
上記手順はテーブルT[2],T[3],…,T[t-1]の全ての要素のために繰り返される。ステップ441において、値z2およびx2= Pinit mod z2がz1およびx1にコピーされ、ステップ442で、z3がz2にコピーされ、且つテーブルT[i]の要素を指すカウンタiはインクリメントされる。
【００９７】
《モンゴメリ定数の演算》
図１１において、小さい素数zと関連するモンゴメリー定数r=2p mod zの計算は、ステップ402および414で実行される。図１２はその手順を詳細に例示する。この手順への入力は、素数候補Pのビット長ｐ、および小さい素数zである。小さい素数zは小さいので、そのビット長は通常16ビット未満であり、小さい素数zに関連した全ての演算はＣＰＵ 122によって容易に処理することができる。ここではモンゴメリー乗算コプロセッサ123の使用は必要ではない。結果として、モンゴメリー定数の計算は、コプロセッサ動作に並列させることが可能になる。
【００９８】
実施の形態２ではモンゴメリー定数の計算にはRAM 112に配置された3個のバッファを使用し、バッファはステップ502で初期化される。バッファは2の累乗を格納し、xは部分的な結果を格納するアキュムレータであり、iは計算2p mod zの演算におけるベキ指数pのスキャンに使われる。実施の形態２で使用される技術は、右から左へのバイナリの累乗である。基本的な考えは、y=2^(2^0)=21=2 mod z、y=2^(2^1)=22=4 mod z、y=2^(2^2)=24=16 mod z、y=2^(2^3)=28=256 mod zおよびその他を計算し、ｐのバイナリ表現を右から左にスキャンし、スキャンされたビットが１のとき、x=x*y mod zを計算するというものである。
【００９９】
p=0である場合、x=1はステップ542に返される。そうでない場合には、ステップ512でＣＰＵ 122を使用してiが右に1ビットシフトされる。iの最下位ビットが1であるとき、右シフト動作はキャリーを生成する。この場合、xはステップ522でx*y mod zに更新される。実施の形態２において、ＣＰＵはx*y mod zのような剰余乗算を直接サポートしない。したがって、動作は2つの部分に分けられる。一つは古典的乗算x*yであり、もう一つは剰余演算x mod zであり、双方共にCPUによってサポートされる。
【０１００】
次に、バッファiがゼロでない限り、次に要求される２の累乗が計算される。その手順がｋ番目の繰り返しを実行していると仮定すると、y=2^(2^k)である。次に要求される２の累乗は、2^2^(k+1) = 2^(2^k)*2^(2^k) = y*y mod zであり、ステップ532で演算され、それには1つの乗算y*yと一つの剰余を持つ除算y mod zが利用され、それはＣＰＵ 122によって演算される。
【０１０１】
バッファiは繰り返し毎に右シフトされるので、結局、iは0になる。この点で、べき乗の剰余乗算2p mod zは完了され、演算結果x=2p mod zを返すことができる。
【０１０２】
《フェルマーテスト》
楕円曲線暗号の場合、累乗演算の速度を改善することが良く知られている。例えばNon-Adjacent Form（NAF））のようなべき乗数のための符号表現を使用する。NAFは、単純なバイナリの累乗より高速で、再計算を必要としない。しかしながら、楕円曲線累乗とＲＳＡ累乗との間には大きな違いがある。すなわち、前者の場合、位置の逆転を殆ど演算コスト無く得ることができるが、後者の場合、若干の整数の反転演算に大きな演算コストを要する。符号表現における負数に反転演算が必要になるから、この方法は通常、ＲＳＡのためには不適当と考えられる。
【０１０３】
通常それらがＲＳＡのために魅力的でないという事実にもかかわらず、実施の形態２はフェルマーテストのためには符号表現を使用する。実際、A*B-1 mod Pは一般に大きな演算コストを要する動作である、しかし、B=2である場合、動作はA/2 mod Pになる。さらに、2による除算は単なる右シフトにり、おそらくPの加算の後になる。要するに、Aが偶数の場合A>>1（1ビット右シフト）、Aが奇数の場合は（A+P)>>1（1ビット右シフト）を行う。
【０１０４】
NAF再符号化は右から左に行われ、べき乗は左から右に行われるから、双方の処理を結合することはできない。即ち、最初に、ベキ指数（exponent）が再構成され、その新な表現の数が異なるRAM域に格納され、第２に、べき乗計算が行われる。この方法の欠点はベキ指数が非常に大きいということであり、RAMにその再構成されたフォームを格納するための領域を予約しておかなければならない。再構成されたフォームは、少なくともオリジナルのベキ指数に比べて大きい。前記再構成とべき乗演算が共に左から右に行われるとするなら、新たな表現を格納するためにRAMを割当てることを要しないであろう。前記双方の処理を一つに結合することが可能に成るからである。
【０１０５】
実施の形態２におけるフェルマーテストは次の結果を得ることができる。即ち、再構成とべき乗演算を一つの固有の処理フェーズに統合することができ、それゆえに、再構成された指数を格納するためのメモリの追加が必要とされない。これを達成するために、フェルマーテストはFAN表現を利用し、これは通常楕円曲線で使われ、楕円曲線については例えば特許文献２に記載があり、ここでは、wMOFと呼ばれている。FANはその生い立ちの点ではNAFと同様であるが、FAN再構成は左から右に実行され、べき乗演算フェーズと統合することはできない。
【０１０６】
FANべき乗演算における1つの繰り返しは、多くてもPi+1,Pi,Pi-1の3ビットのベキ指数をスキャンすることである。その内容はケース１〜ケース6に分類できる。
[ケース1 ]：（Pi+1Pi)=(11)2は（Si)=(0)に再構成され、iは i-1にセットされる。
[ケース2 ]：（Pi+1PiPi-1)=(011)2は（SiSi-1)=(1)に再構成され、iは i-1にセットされる。
[ケース3 ]：（Pi+1PiPi-1)=(010)2は（Si)=(01)に再構成され、iは i-2にセットされる。
[ケース4 ]：（Pi+1Pi)=(00)2は（Si)=(0)に再構成され、iは i-1にセットされる。
[ケース5 ]：（Pi+1PiPi-1)=(100)2は（SiSi-1)=(-1)に再構成され、iは i-1にセットされる。
[ケース6 ]：（Pi+1PiPi-1)=(101)2は（Si)=(0-1)に再構成され、iは i-2にセットされる。
ケース1および4の場合、1回の二乗演算（square）がコプロセッサ123で行われる。ケース2の場合、1回の二乗演算がコプロセッサ123で行われ、CPUで1回の左シフト演算が行われる。ケース5の場合、1回の二乗演算がコプロセッサ123で行われ、CPUで1回の右シフト演算が行われる。ケース3の場合、2回の二乗演算がコプロセッサ123で行われ、CPUで1回の左シフトが行われる。ケース６の場合、2回の二乗演算がコプロセッサ123で行われ、CPUで1回の右シフトが行われる。
【０１０７】
図１３に基づいてその内容を詳述する。ステップ601におけるフェルマーテストへの入力はpビットの奇数の整数Pから成り、それが素数性の判定対象になる。ICカードのメモリ112において、Pは一連のpビット（Pp-1…P0)2として格納される。モンゴメリー乗算コプロセッサはMontMult(A,A,P)=A*A*2-p mod Pを演算するので、コプロセッサレジスタA 115は２で初期化されず、2*2p mod Pで初期化される。この方法はMontMult(A,A,P)=2*2*22p*2-p=2*2*2p-mod Pとなる。モンゴメリー乗算の後にも要素2pがまだあることが分かる。ステップ602において、コプロセッサレジスタ115は2p+1 mod Pによって初期化され、これはpがあまり大きくないからであり、通常はp=512又はp=1024であり、バイナリでは、2p+1は１と後続するp+1個の０という形式で単純に表現される。次に、２p+1がPよりも小さくなるまで必要に応じて何回もPは減算される。さらに、カウンタiはRAM 112でp-2に初期化される。
【０１０８】
ケース1、2、3、4、5および6の全てにおいて、常に二乗演算が行われる。それゆえに、モンゴメリ乗算がステップ612で計算される。より正確に言うと、コプロセッサレジスタA 115がモントゴメリー乗算MontMult(A,A,P)によって更新され、ここで、素数候補Pの入力はコプロセッサレジスタN 117に格納される。次に、Pの値に依存する異なったパターンがあり、ここで、各々のパターンはケース1、2、3、4、5または6のうちの1つに対応される。Pのi番目のビット即ちPiはステップ613で判定され、Pがコプロセッサレジスタ117に格納され、カウンタiはRAM112にある。Pi=1なら、ケース1,2,又は3に対応する操作が実行されなければならない。Pi=0のときは、ケース4,5,又は6に対応する操作が実行されなければならない。
【０１０９】
Pi=1である場合、ビットPi+1の値はステップ612において点検される。それによる点検内容は以下の通りである。
[ ケース1 ] Pi+1=0なら、検出されたケース１に対応するビット処理が行われる。ケース1は1つのモントゴメリー乗算処理だけを要求し、他の処理は必要とされず、次のビットの値がチェックされる。Pi+1=0である場合、ビットPi-1はケース2および3を区別するために点検されなければならない。したがって、ステップ622で、ビットPi-1の値が点検される。
[ケース2 ] Pi-1=0の場合、検出されたケース２に対応されるビット処理が行われる。それゆえに、ステップ623でコプロセッサレジスタA 115のデータがCPU12により1ビットが右にシフトされる。シフト操作の後、レジスタA 115のデータはｐビットよりも多くなる。すなわち、この場合、ステップ625で必要に応じて何回もPはAから減じられなければならない。
[ケース3 ] Pi-1=1の場合、検出されたケース３に対応されるビット処理が行われる。ステップ641で更にモンゴメリ乗算が行われ、カウンタiがもう1回デクリメントとされる。その後、コプロセッサレジスタA 115のデータがステップ623で左に1ビットシフトされ、ステップ625においてAがpビットよりも多いならば、PがAから減算される。しかしながら、i=1である場合、代わりにケース2が実行される。Pi=0である場合、ビットPi+1の値はステップ631において点検される。それによる点検内容は以下の通りである。
[ケース4 ] Pi+1=0の場合、更なる動作は必要とされない。Pi+1=1である場合、ケース5および6を区別するためにPi-1が点検されなければならない。
[ケース5 ] Pi-1=0の場合、Aは1ビット右へシフトされる。Aが偶数の場合、その最下位ビットは0であり、Aはステップ635でＣＰＵ122によって直接シフトされる。しかし、Aが奇数の場合、Pはステップ634でＣＰＵ 122によってAに加算される。AとPの両方とも奇数だから、A+Pは偶数であり、ステップ635で右へシフトされる。
[ケース6 ] Pi-1=1の場合、モントゴメリー乗算が行われ、カウンタiはステップ642でデクリメントされ、その後、ステップ633に続く右シフトが行われる。
【０１１０】
上記のステップは繰り返され、カウンタiは０になるまでステップ614でデクリメントされる。P-1の2つの最下位ビットはそれぞれに処理される。P-1の最後から二番目のビットはP1である。P1=0である場合、モントゴメリー乗算はステップ651で演算され、P1=1の場合は、必要に応じてステップ654のPを加えた後に、モンゴメリー乗算の後にステップ655の右シフトが続く。P-1は偶数だから、P-1の最後のビットは常に0であり、したがって、モントゴメリー乗算はステップ661で計算される。この点で、全てのビットは計算されたが、モンゴメリー定数の2p mod Pは削除されなければならない。したがって、ステップ663で、データ1はコプロセッサレジスタB 116に書き込まれ、モンゴメリー乗算MontMult(A,1,P)=A*2-p mod Pはコプロセッサ123によって演算される。この最後の乗算はモンゴメリー定数の2p mod Pをキャンセルし、そして、コプロセッサレジスタAに格納されているデータはステップ662に戻される。Aが1である場合、Pは多分素数であり、Aが1でない場合、Pは合成数である。
【０１１１】
《フェルマーテストの具体例》
この例では、整数P=109が素数性の判定対象であると仮定する。ベキ乗の剰余乗算2108 mod 109は、図13によるフェルマーテストを使用して計算される。二進数で、108=(1101100)2、であり、、二進法に基づく左シフトを備えたフェルマーテストは3つの左シフトを行い、これはその最上位ビットの１に加えて1の桁が更に3桁あるからである。他方、108のFAN表現は108=(100-10-100)であり、2つの右シフトだけがある。
【０１１２】
詳しく説明する。P=109のビット長はp=7である。最初に、Aは2p+1 mod P = 28 mod 109で初期化される。28から= 256、28-2*109=38、レジスタA=38、カウンタiはp-2 = 5だからである。
[ i=5 ]の場合、レジスタAはMontMult(A,A,P)=MontMult(38,38,109)=76によって更新される。次のP5=1、P6=1、そして、対応する再符号は0であり、したがって、更なる操作は必要とされない。
[ i=4 ]の場合、レジスタAは、MontMult(76,76,109)=86によって更新される。次のP4=0、P5=1、P3=1、そして、対応する再符号が0-1である。レジスタAはMontMult(86,86,109)=68で更新され、カウンタiはデクリメントされる。68は偶数であるから、直接右シフトA>>1が実行され、レジスタAは34に更新される。
[ i=2 ]の場合、Aは、MontMult(34,34,109)=101に更新される。次のP2=1、P3=1、そして、対応する再符号は0である。
[ i=1 ]の場合、Aは、MontMult(101,101,109)=55によって更新される。次のP1=0、P2=1、P0=0、そして、対応する再符号は-1にある。レジスタAは偶数であるから、109がAに加えられ、右シフトが計算され、その結果、A=82を得る。
【０１１３】
そこから、フェルマーテストの最終ステップが実行される。P1=0、2つのモントゴメリー乗算が実行される。即ち、MontMult(82,82,109)=90およびMontMult(90,90,109)=19。MontMult(19,1,109)=1であるから、フェルマーテストは1を出力する。それは109が素数であるという事実と整合している。
【０１１４】
《ミラーラビンテスト》
ミラーラビンテストにおいてP-1は2j+1*Dと書かれる。ここで、j+1はP-1のバイナリの表現における末尾の０の数である。第１に、ある基数Bのために、累乗B←XD mod Pが計算される。XD mod P=1である場合、Pは多分素数であるだろう。他方、B=XD mod Pが1でない場合、Bは-1と比較される。Bが-1でない場合、Bはj回二乗演算され、各々の二乗演算の後、再び演算結果が-1と比較される。それら二乗演算を1つ行った後、B=-1のとき、フェルマーテストは停止され、Pはたぶん素数であるとい結果が得られる。そうでなければPは合成数である。
【０１１５】
フェルマーテストのように、ミラーラビンテストへの入力は、ステップ701のp-ビットの奇数P=(Pp-1…P0)から成る。RAM 112に配置されたカウンタjは、P-1における末尾の０の数から1を引いた数を格納する。ステップ703および704において、1にセットされるビットが見つかるまで、Pの最下位ビットがスキャンされる。各々の０のために、カウンタjはCPUでインクリメント操作される。
【０１１６】
一旦jが決定されると、累乗の基数がステップ711でランダムに選ばれる。乱数発生器124は[p-ビット]のランダムな整数Xを生成し、それはコプロセッサレジスタA 115に格納され、同様にコプロセッサレジスタB 116にコピーされる。カウンタiはRAM 112においてp-2に初期化される。このカウンタiは、次のステップで累乗の剰余乗算BD mod Pが演算されている間に、P-1のどのビットがスキャンされるかについて指す。累乗の剰余乗算は、左から右にバイナリの方法を用い、モンゴメリー乗算とモンゴメリー二乗演算の手順で演算される。ステップ713において、モントゴメリー二乗演算が行われ、演算結果がコプロセッサレジスタ115に格納される。即ち、MontMult(A,A,P)=A*A*2-p mod Pが格納される。さらに、ビットPiが1である場合、ステップ715でモンゴメリー乗算が行われる。即ちMontMult(A,B,P)=A*B*2-p mod Pが行われる。 最後に、ステップ716でカウンタiがデクリメントされる。
【０１１７】
モンゴメリー乗算コプロセッサ123がステップ713および715で用いられるので、要素2-p mod Pが各々の乗算または二乗演算の後で導かれる。しかしながら、Xを、ステップ711において生成された初期ランダムビットXと称する場合、XはX=Y*2p mod Pと考えられる。ここで、Yは他の[p-ビット]の整数である。今、MontMult(Y,Y,P)=Y*Y*2p mod Pであり、モンゴメリー乗算の後、要素2p mod Pは安定している。結果として、累乗結果はXD mod PでなくXD*2p mod P.である。しかしながら、XD mod Pはステップ721において容易に回復されることができる。ここで、前のステップの結果はモンゴメリー乗算コプロセッサを使用した1の乗算とされる。即ち、MontMult(A,1,P)=YD*2p*1*2-p mod P = YD mod Pである。ステップ721の後、コプロセッサレジスタA 115がデータ1を格納するなら、ミラーラビンテストはステップ741で「成功」を出力する。そうでない場合には、すでに説明されるように、コプロセッサレジスタA 115に格納されるデータが二乗され、-1と比較される。
【０１１８】
モントゴメリー二乗演算はステップ733でj回繰り返される。一つのモンゴメリー乗算の後、レジスタAはY2D*2p mod Pを格納しており、再び、要素2p mod Pがモンゴメリー乗算の後に安定する、即ち変わらないことが分かる。しかしながら、モントゴメリー二乗演算の結果は-1と比較されるから、要因2pはステップ733における操作MontMult(A,1,P)=Y2D mod Pで取り除かれなければならなず、その結果データはコプロセッサレジスタB 116に格納される。-1=P-1mod Pに着目すると、ステップ731でコプロセッサレジスタBに格納されたデータはP-1と比較される。それが一致であれば、Pはたぶん素数であるから、ミラーラビンテストはステップ742で「成功」を返す。レジスタBのデータがP-1とは異なる場合、上記した手順が全体でj回繰り返される。j回繰り返された後なら、レジスタBの値は決してP-1には一致せず、Pは合成数だからミラー-ラビンテストはステップ743で「失敗」を出力する。
【０１１９】
《拡張》
本発明は、上記の実施の形態２で説明した内容に限定されない。例えば、図8の携帯機器は携帯電話、PDA、および公開鍵暗号を使用し且つコンピュータリソースとメモリリソースが限られたその他種々の電子デバイスであってよい。特に、携帯機器はモンゴメリー乗算コプロセッサを備えている必要はない。種類の異なるコプロセッサであってもよい。例えば古典的な剰余乗算コプロセッサであってもよいし、コプロセッサを用いずにソフトウェアによりCPUが実現する剰余乗算処理であてもよい。
【０１２０】
小さい素数の差を格納する代わりに、小さい素数を再構成するためには適切な他のいかなる方法も用いることができる。フェルマーテストにおける再符号化はNAF法、ウインドウ法、またはスライディングウインドウ法のように、異なる再符号化法であってもよい。
【０１２１】
実施の形態2がRSA鍵の生成に着目しているが、本発明がRSAに限定されず、DSAまたはDiffie-Hellmanのような他の公開鍵暗号方式でも、効率的に素数を生成するための上述の発明の効果を得ることができる。加えて、本発明は、素数判定テストの構成や種類に限定されない。たとえば、フェルマーテストの代わりにミラーラビンテストが使用されてもよいし、フロベーニウス（Frobenius）、Solovay-StrassenまたはAKSテスト等のその他のテストを採用してもよい。また本発明は特定のRSAパラメータに限られていない。例えば、DP、DQおよびQinvのようなCRTパラメータを省略することが可能であり、また、Dを省略することも可能であり、また、強い素数（strong primes）をPおよびQの追加的状態で使用することも可能である。
【０１２２】
実施の形態1で説明した図１の暗号化ユニットはソフトウェア的に実現されることも可能であり、また、図８の構成で実現される機能をハードウェアロジックで構成することも可能である。
【図面の簡単な説明】
【０１２３】
【図１】図１はＩＣカードのブロックダイヤグラムである。
【図２】図２はＲＳＡ対応のＩＣカードの典型的な動作工程を例示するタイミングチャートである。
【図３】図３は素数生成ユニットの具体例を示すブロックダイヤグラムである。
【図４】図４は素数生成制御ユニットの詳細を例示する説明図である。
【図５】図５はフェルマーテスト制御ユニットの機能を示す説明図である。
【図６】図６はミラーラビンユニットの機能を示す説明である。
【図７】図7はビットアレイのアップデータ機能を示す説明図である。
【図８】図８は携帯式電子装置（携帯機器）のブロックダイヤグラムである。
【図９】図９はＲＳＡ鍵ペア（keypair）の生成機能を示す説明図である。
【図１０】図１０は素数生成機能についての説明図である。
【図１１】図１１はビットアレイフィルの操作手順の詳細を例示する説明図である。
【図１２】図１２はモンゴメリー定数の演算機能を示す説明図である。
【図１３】図１３はフェルマーテストの機能を示す説明図である。
【図１４】図１４はミラーラビンテストの機能を示す説明図である。
【符号の説明】
【０１２４】
901 ＩＣカード
931 入出力インタフェース
912 鍵生成ユニット
911 暗号化ユニット
922 秘密鍵
924 デジタル証明書
921 メモリ
941 ネットワーク
904 ＡＴＭ
905 カードリーダ
902 ホストシステム（銀行ホスト）
903 ホストシステム（カード発行元ホスト）
923 公開鍵
914 素数生成ユニット
1111 フェルマーテストユニット
1131 ビット配列ユニット
1161 小さい素数生成ユニット
1102 素数生成制御ユニット
1123 素数候補P
1121 レジスタA
1122 レジスタＢ
1113 剰余乗算ユニット
1102 フェルマーテスト制御ユニット
1113 ビット配列ユニット
1141 ビットアレイ
1132 ビットアレイフィルユニット
1163 小さい素数テーブル
1162 ミラーラビンユニット
1171 メモリレジスタ
101 携帯式電子装置（携帯機器）
131 入出力インタフェース
141 ネットワーク
151 ATM
153 コンピュータ
154 携帯機器
111 メモリ
132,133入出力インタフェース
121 データ処理部
122 ＣＰＵ
123 モンゴメリー乗算コプロセッサ
124 RNG
【技術分野】
【０００１】
本発明は、素数判定のためのデータ処理システム及びデータ処理方法に関し、例えば公開鍵暗号方式のシステム構成等において使用される暗号鍵の効果的な生成に適用して有効な技術に関する。
【背景技術】
【０００２】
公開鍵暗号方式は広く認識され、現在多くのアプリケーション、例えば銀行業務または電子商業のために用いられている。そこでは、安全ではないネットワークを介してユーザ間でデジタル署名書類、暗号化データ、変換鍵キー等が用いられている。ＲＳＡは、公開鍵暗号法のための事実上の標準であって、デジタル署名または公開鍵暗号化が必要とされるアプリケーションにおいて一般化している。たとえば、ＲＳＡの活用は、クレジットカードのためのＥＭＶ（Europay-Mastercard-Visa）コンソーシアムによって推薦され、より正確に言うと、２０１０年までは、１０２４ビットのキー長さをもつＲＳＡがＥＭＶにより推奨され、それ以降は２０４８ビットのキーが推奨される。
【０００３】
ＲＳＡにおいて、メッセージはnビット整数としてコード化される。ＲＳＡ公開鍵はベキ指数E（それは概して小さい）、ｎビットの法数Ｎから成る。ＲＳＡ秘密鍵はｎビット整数Ｄであり、E*D = 1 mod(P-1)*(Q-1)の関係がある。記号*は乗算を意味する。ここで、ＰとＱは秘密の素数であり、それはP*Q＝Nの関係を満足する。任意のメッセージ0＜=M＜N、（ＭE）D mod N＝Mに関して説明する。例えばアリスがＲＳＡ鍵となる（E,N）,Dの保有者であると仮定する、そして、ボブはアリスに暗号化されたメッセージＭを送りたいと仮定する。ボブはC=ME mod Nを計算し、アリスに暗号文を送る。次に、アリスはCD=(ME)D=M mod Nを計算して元の文を回復する。これにより、ＲＳＡの中心的な動作が累乗の剰余乗算XY mod N.であることが解る。Nが大きいとき、例えば２０４８ビットのようなとき、その累乗計算には時間がかかる。ＲＳＡの演算を高速化するには、中国の剰余定理を利用することができる。それは累乗の剰余乗算CD mod Nが２つの累乗の法PとＱに交換できることを言及する。N=P*QでありP及びQは法Ｎの約半分のデータサイズであるから、その中国の剰余定理によるアプローチ（ＲＳＡ−ＣＲＴ）によれば実際に演算を早く行うことができる。ＲＳＡ−ＣＲＴにおいて、その暗号化の手順は標準のＲＳＡと同様に、C=ME mod Nである。相違点は暗号からの復号手続きである。例えば、DP = D mod P-1 = E-1 mod P-1、DQ = D mod Q-1 = E-1 mod Q-1、Qinv =Q-1 mod P と定義されているとする。これにおいて、Z=X-1 mod YがZ*X=1 mod Y を満足する整数が1＜=Z＜Yであるとき、コンピュータによるＲＳＡ−ＣＲＴの復号処理は、MP = C^DP mod P、MQ = C^DQ mod Q、M = MQ + Q*[Qinv *（MP−MQ））mod P ]とされる。したがって、そのときのＲＳＡの鍵の対は、公開鍵であるE、N、標準ＲＳＡのための秘密鍵であるＤ及びＲＳＡ−ＣＲＴのためのＰ，Ｑ，ＤQ，ＤP，Ｑinvである。
【０００４】
ＲＳＡ鍵の長さは例えば、公開鍵Nのビット数のサイズに関係する。例えば２０４８ビットＲＳＡにおいて、公開鍵Nは２０４８ビットを持ち、素数Ｐ、Ｑは概してそれぞれ１０２４ビットを有する。その結果、N=P*Qになる。ＲＳＡ鍵を発行するためには２つのランダムな素数PおよびQが選択され、他の鍵素子は２つの素数に由来する。ランダムな素数を生成するには、一つには次のように処理が進行する。第１に、ランダムな整数は選ばれ、そして、この任意の数は素数判定、例えばフェルマー判定が行われる。その数が素数判定をパスしない場合には、新たな素数候補に更新されて処理が行なわれる。更新の処理は方法によって異なり、例えば新たな任意の整数とし、又は最初のランダムな整数を増加させる。任意の素数を生成するステップは、ＲＳＡ鍵を生成するコンピュータ処理において最もコンピュータリソースを費やしている。
【０００５】
過去においては、そのようなコストの大きな処理を行なうにはコンピュータ処理能力があまりにも低く、ＩＣカードにおいてＲＳＡ鍵を生成する場合については疑いなくそうだった。結果として、ＲＳＡ鍵は、パワフルなワークステーションを用いて生成され、ＩＣカードにコピーされた。しかしながら、最近のＩＣカードは、公開鍵暗号処理に特化したハードウェア・アクセラレータによる利益を享受する。前記ハードウェア・アクセラレータは暗号処理用のコプロセッサであり、ＩＣカードが暗号鍵を生成することは現実的になっている。これには、２つの効果がある。第１は、ワークステーションで鍵を生成する場合のように、もしもワークステーションに障害が発生すればそれによって生成された全ての鍵が危うくなるというような、単一障害点にはならない、と言うことである。第２は、カード発行者は秘密鍵を知らなくてもよい、という点である。即ち、カード発行者にとってみれば秘密鍵を漏らすかまたはそれらを誤用する責任があるとみなされることはない。
【０００６】
【特許文献１】米国特許第７１１３５９５号明細書
【非特許文献１】Alfred Menezes, Paul van Oorschot, Scott Vanstone:"Handbook of Applied Cryptography", Chapter 4, Public-Key Parameters. CRC Press, ISBN 0-8493-8523-7
【非特許文献２】Katsuyuki Okeya, Katja Schmidt-Samoa, Christian Spahn and Tsuyoshi Takagi: "Signed Binary Representations Revisited", Proceedings of Advances in Cryptology, CRYPTO 2004, LNCS 3152, Springer-Verlag, 2004
【発明の開示】
【発明が解決しようとする課題】
【０００７】
暗号化処理用のコプロセッサによってその計算処理が促進されても、ＩＣカードのような携帯デバイスは低い計算能力および不十分な記憶資源という非常に圧迫された環境のままであることが多い。しかしながら、そのエンドユーザは暗号鍵が発生されるのに長時間待たされることを欲しないのが通例である。したがって、多くのコンピュータリソースを要せず効率的にその種の暗号鍵を生成することができる技術の開発が要望される。
【０００８】
また、非特許文献１において、ランダムな素数を生成するいくつかの方法が記載されている。しかしながら、それに記載の技術は、不十分なメモリ資源しか備えていないＩＣカードではほとんど実現することができない。非特許文献２においては、ランダムな素数を生成するコンパクトな技術が詳述されているが効率的な方法を提供するものではない。
【０００９】
本発明は上記事情に鑑みてなされたものであり、例えばＩＣカードのように限られた記憶資源しか持たなくても効率的な暗号化処理の実現に資することができる素数判定技術を提供することを目的とする。換言すれば、本発明の目的は、携帯機器のように不十分な記憶資源であっても高速にランダムな素数を生成することができる技術を提供することにある。
【００１０】
本発明の前記並びにその他の目的と新規な特徴は本明細書の記述及び添付図面から明らかになるであろう。
【課題を解決するための手段】
【００１１】
本願において開示される発明のうち代表的なものの概要を簡単に説明すれば下記の通りである。
【００１２】
すなわち、本発明は少ないコンピュータリソースで効率的な処理を可能とするために、データの符号化と再符号化に適用される。特に、素数生成ステップの間、予め定められたコンパクトなテーブルが、多数の小さい素数を再生成するのに用いられる。加えて、素数判定で処理される素数候補が再符号化され、それらの表現形式をバイナリ符号から適当な符号に変える。
【００１３】
例えば、暗号鍵を生成するデータ処理システムは、多数の小さい素数を再構成するための演算ユニット、小さい素数によって整数が割り切れるかを点検するための篩ユニット、整数の表現を変えるための再符号化ユニット、及び素数性判定テストユニットを備える。篩ユニットは最初に演算ユニットによって再構成される小さい素数によって整数が割り切れることを点検し、これによって「不適当な」素数候補を取り除く。その後、残りの素数候補は素数性判定テストユニットを使用してテストされる。このとき、再構成ユニットを使用して素数候補の表現が変換され、変換された表現形態を用いて素数性判定テストユニットが判定動作を行う。これにより、大きなメモリ容量を必要とすることなく、素数性判定のための演算処理数を減少することができる。
【発明の効果】
【００１４】
本願において開示される発明のうち代表的なものによって得られる効果を簡単に説明すれば下記のとおりである。
【００１５】
すなわち、ＩＣカード等のように限られた記憶資源しか持たなくても素数判定若しくは素数生成において効率的な暗号化処理の実現に資することができる。
【００１６】
また、携帯機器のように不十分な記憶資源であっても高速にランダムな素数を生成することができる。
【発明を実施するための最良の形態】
【００１７】
１．定義
先ず、以下の説明で使用する語の定義と表記法について述べる。AまたはBのような大文字の変数は、例えば１０２４ビットの整数のように、大きな整数を意味する。xまたはyのような小文字で示される変数は、一般的に３２ビットよりも小さなビット長の小さな整数を意味する。
【００１８】
R=A*B mod Nは古典的な剰余乗算式を示すものである。ここで、P=A*Bは通常の乗算である、そして、Rは除算P/Nの剰余である。換言すれば、Rは整数0＜=R＜Nであり、R+Q*N = A*Bとなり、Qはある整数である。AD mod Nはべき乗の剰余乗算であり、D-1を伴なうA*A*…*A mod Nの剰余乗算に対応する。それは、同様にA^D mod Nとも記述される。記号^はべき乗若しくは累乗を意味する。
【００１９】
gcd(A,B)は、AとBの最大公約数である。例えば3は6および15の最大公約数である。6=3*2、15=3*5だからである。
【００２０】
A-1 mod Nは、A*B=1 mod Nのような整数Bを参照する。gcd(A,N)=1ならば Bは存在する。
【００２１】
素数とは、それ自身と１との２つの除数を有する整数である。例えば整数2、3、5、7、11は素数である。
【００２２】
合成整数（合成数）は、少なくとも2つの素数に因数分解されることができる整数である。21は21=3*7であるから合成整数であり、4は4=2*2であるから合成数である。
【００２３】
MontMult(A,B,N)はモンゴメリー乗算であり、Ｎをｎビットの法数とする剰余乗算A*B*2-n mod Nに等しい。
【００２４】
２．実施の形態１
先ず素数生成回路を主眼に説明する。
【００２５】
《ＩＣカード》
図１にはＩＣカードのブロックダイヤグラムが示される。ＩＣカード901は、少なくとも以下の部品を備えている。即ち、入出力インタフェース931、鍵生成ユニット912及び署名生ユニット913を含む暗号化ユニット911、そして、少なくとも秘密鍵922、公開鍵923及びデジタル証明書924が記憶されるメモリ921を備える。特に制限されないが、実施の形態１では暗号化ユニット911をハードウェアロジックで構成することを想定している。
【００２６】
前記ＩＣカードはネットワーク９４１を介して例えばＡＴＭ９０４及びカードリーダ９０５に接続可能にされるＡＴＭ９０４は銀行のホストシステム（銀行ホスト）９０２に、カードリーダ９０５はカード発行元のホストシステム（カード発行元ホスト）９０３に接続される。９４２はＩＣカード９０１からネットワーク９４１に送信されるデータ、９４３はＩＣカードがネットワーク９４１から受信するデータである。
【００２７】
ＩＣカード９０１に、事実上の標準であるＲＳＡを有するデジタル署名が実装されている場合、ＩＣカード９０１で直接暗号鍵を生成することは有利であることが先に示された。これを実現するために、鍵生成ユニット912は素数を生成するための専用の回路である素数生成ユニット914を利用することができる。ＲＳＡにおける鍵生成において、素数生成にはデータ処理上最もコストを要するから、素数生成ユニット914を利用することによってそれを低減するものである。
【００２８】
《ＩＣカードの動作》
図２は、ＲＳＡ対応のＩＣカード902の典型的な使用例が示される。最初に、ＲＳＡの鍵は、ＩＣカード９０１のステップ1011において発生する。ＲＳＡの鍵は秘密鍵922および公開鍵923から成る。そして、それらはメモリ921に保存される。その後、ＩＣカード901はステップ1012でカード発行元ホスト903に、公開鍵923を送る。その後、デジタル証明書924が発行されることによって公開鍵が確認される。デジタル証明書９２４は、ステップ1013でＩＣカードに送り返されて、メモリ921に保存される。
【００２９】
ＲＳＡの鍵はＩＣカードの認証動作の初めに少なくとも発生しなければならない、そして、おそらくデジタル証明書の有効性日付以後、デジタル証明書924が発給される。デジタル証明書924が有効なときに、ＩＣカードは認証されたトークンカード（認証トークン）として利用可能にされる。ＩＣカードはステップ1021で銀行ホスト902に処理要求を送る。銀行ホストはステップ1022の認証要求を出して応答する。ステップ1023において、ＩＣカード901は署名生成ユニット913およびその秘密鍵922を使用しているデジタル署名を生成し、生成したデジタル署名、その公開鍵923及びカード発行元ホスト903から発行されたデジタル証明書924を送る。署名およびデジタル証明書が有効な場合、銀行ホスト902によって認証が付与される。証明書が有効なときは、ステップ１０２１から１０２３の処理は必要に応じて何回も実行される。それは殆ど無制限のデジタル処理回数を許容していることになる。
【００３０】
《素数生成ユニット》
図３には素数生成ユニット914の具体例が示される。図１の鍵生成ユニット912は素数Ｐ，Ｑを生成するために素数生成ユニット914を有する。Ｐ，Ｑに関してはＰ*Ｑが公開法数Ｎに等しい、という関係を持っている。素数Ｐ又はＱを生成するために素数生成ユニット９１４は最初のランダムな候補Ｐinitを採り、候補Ｐinitよりも大きな第1の素数Pを見つける。素数生成ユニット９１４は３つのサブユニット、即ち、フェルマーテストユニット1111、ビット配列ユニット1131および小さい素数生成ユニット1161を有し、それらは素数生成制御ユニット1102によって起動され制御される。素数生成制御ユニット１１０２の詳細な機能については図4を参照しながら後述する。
【００３１】
フェルマーテストユニット1111は素数候補の素数性を検査する。フェルマーテストユニット1111は３つのメモリレジスタ、即ち、素数候補P1123を格納する一つのレジスタ、レジスタA1121、及びレジスタＢ1122を有する。３つのレジスタは剰余乗算ユニット1113に接続され、剰余乗算ユニット1113はA*B mod P（またはA*A mod P）を計算し、その結果をレジスタA 1121に格納する。この例において、レジスタA、BおよびPを格納するレジスタのサイズは、1024ビットに限られている。結果として、生成された素数は、最大で1024ビットを有する。
【００３２】
フェルマーテスト制御ユニット1102は剰余乗算ユニット１１１３を起動して当該ユニット1113への信号経路を制御し、当該ユニット1113にフェルマーテストを実行させて、素数候補P1123の素数性を判定させる。この機能の詳細については図5を参照しながら後述する。
【００３３】
ビット配列ユニット1113はビットアレイ1141を有し、これはB[0],…,B[b-1]のbビットから成る。ビットアレイ１１４１において各々のビットB[i]は素数候補Pinit+2iを表す。B[i]=0である場合、Pinit+2iは不適当候補であって、拒絶される。しかし、B[i]=1である場合、Pinit+2iは正しい候補であって、更にフェルマーテストユニット1111でテストされなければならない。ビット配列は、ビットアレイフィルユニット1132に従ってフィルされる（満たされる）。ビットアレイフィルユニット1132は、入力として最初の素数候補Pinitおよび小さい素数を採り、ビット配列の適当な位置でゼロを書き込む。ビットアレイフィルユニット1132の詳細については図７を参照しながら後述する。
【００３４】
小さい素数生成ユニット1161は16ビットよりも少ないビット数の小さい素数（スモール素数）を生成し、それは前記不適当は整数を識別するために使用可能にされる。小さい素数生成ユニット１１６１は第1のｔ小さい素数を格納する小さい素数テーブル１１６３を有するが、ミラーラビンユニット１１６２のためのｔ素数よりも多くを生成することができる。その機能についての詳細は図６を参照しながら後述する。生成された小さい素数は16ビットのメモリレジスタ１１７１に格納される。
【００３５】
《素数生成制御ユニット》
図４には素数生成制御ユニット1102の詳細が例示される。初期候補PinitはレジスタP1123にコピーされ、最初にビット配列B[0],…,B[b-1]は全て１にセットされる。ステップ1202、1203および1204において、ビット配列は、テーブルT 1163に格納された第1のt素数によって初期化される。より正確には、ステップ1204で、1つの小さい素数zは、テーブルTから読み出されて、小さい素数レジスタ1171へコピーされる。それから、小さい素数zがビットアレイフィルユニット１１３２によって使用されることにより、ビット配列1141が更新され、適当な位置に０が書き込まれ、不適当な候補が除去される。このビットアレイフィルユニットの詳細は図７に示される。
【００３６】
テーブルT 1163から小さい素数を使用してビット配列が初期化された後、素数生成制御ユニットはビットアレイ1141を調べ、ステップ1213において対応するエントリB[i]が１を含むようにインデックスiを探す。そのようなエントリは整数Pinit+2iを参照しており、その整数は正しい候補であって、更にフェルマーテストユニット1111で更にテストされなければならない。このように、値Pinit+2iはステップ1221でレジスタP1123に書き込まれ、ステップ1222でフェルマーテストの対象にされる。フェルマーテストユニットの機能は図５に記載されている。
【００３７】
ところで、ハードウェア・サイズの限界により、テーブルTは多くの小さい素数を含まず、その結果として、ビットアレイはB[i]=1のようなエントリをまだ多く保有し、そして、素数Pが見つかるまでフェルマーテストは何回も呼び出されなければならない。フェルマーテストの呼出し回数を減らし、素数生成を加速するために、フェルマーテストユニットはステップ1222でアクティブにされたとき、これと同時に新しい小さい素数ｚが生成され、ビットアレイはその新しい小さい素数で更新される。結果として、より多くのエントリはビット配列において0にクリアされ、フェルマーテストの呼出しはより少なくされる。
【００３８】
ステップ1223、1224および1225はそのような新しい小さい素数を生成して、zでビット配列を更新する。それらは、小さい素数生成ユニット１１６１及びビットアレイイニット１１３１によって実行され、素数生成装置1161およびビット配列装置1131によって処理されて、フェルマーテストに並行して実行される。図４において、そのような並列コンピュータ処理は破線の矢印で示されている。
【００３９】
ステップ1223において、小さい素数zの１６ビットのレジスタ1171は、z+2によって更新される。実際、zは奇数であり、偶数の整数は２で割り切れるから明らかに素数でないからである。次に、zはミラーラビンユニット1162を使用して素数性のテストの対象にされる。ミラーラビンユニット1162の機能の詳細は図6に記載されている。ミラーラビンユニットは１６ビット整数の素数性を判定する回路であって、フェルマーテストユニットよりも非常に高速であり、より大きな整数を扱うために構成されている。その結果として、一つのフェルマーテストが実行されている間に複数のミラーラビンテストを行うことが可能にされる。ミラーラビンテストユニットで16ビットの小さい素数が見つかったときビットアレイ1141はビットアレイフィルユニット1132によって更新される（ステップ1225）。これらの３つのステップ1223、1224および1225はフェルマーテストが行われている間繰り返される。
【００４０】
フェルマーテストが終わって、成功したときに、その見込み素数（probable prime）Pは素数生成ユニットによりステップ1231の戻され、他方で、素数生成ユニットは、ビット配列1233のアクティブインデックスをインクリメントし、再びステップ1212から始めることによって、ビット配列の次の正しい候補を探す。ビット配列の全てのインデックスが走査され、素数が見つからなかったときには、素数生成ユニットはステップ1232で失敗を返す。
【００４１】
《フェルマーテスト》
フェルマーテストについて説明する。フェルマーテストは基数Bおよび素数候補Pを入力し、BP-1 mod Pを演算する。仮に演算結果が１でなければ、素数候補Pは合成整数ということになる。演算結果が１であれば、Pはほぼ間違いなく素数ということになる。BP-1 mod Pはデータ処理上高コストの処理であり、ビット配列で多くの不適当な候補が除去されるときでも、フェルマーテストの対象にされるべき多くの正しい候補がまだ残っている。その意味で、フェルマーテストにおける処理速度の改善は非常に魅力的である。
【００４２】
累乗演算のパフォーマンスを向上させる周知の方法は、ウインドウ方法を使用することである。ウィンドウ・サイズwを有するウインドウ方法において、ベキ指数からのwビットが同時に走査される。換言すれば、ベキ指数（それは通常メモリのそのバイナリの表現に保存される）は2wベースで再符号化（recoded）される。これらのwビットは整数ｊ（0＜=j＜2w）を表し、データBj mod Pが予め計算され、そしてウインドウ累乗技術ではA2 mod PおよびA*Bj mod Pが演算される。その代わりに標準のバイナリ法を用いると、A2の演算は同じであるが、w/2 の乗算が新たに必要になる。従ってウインドウ方法は乗算回数を減少させることができる。
【００４３】
しかしながら、ウインドウ方法によって必要な予め演算された値は、RAMに保存されなければならない。ICカードにおいて、RAMの記憶容量は制限される。そして、1024ビットの累乗の場合、上記予め演算された1つの値は128バイトを占める。そして、最適化されたウインドウ方法はしばしばこの種の幾つもの予めコンピュータ演算された値を使用する。これはICカードにとて現実的ではない。たとえば、ウィンドウ・サイズw=5の場合、予めコンピュータ演算された必要な値はRAM上で約4キロバイトを占有することになる。
【００４４】
本発明に係るフェルマーテストは、コンピュータ演算されたデータを記憶するためにメモリが要求されることなく大きなウインドウのウインドウ法を利用可能にするものである。フェルマーテストでは、BP-1 mod Pの演算においてBに特別な基数、特にB=2、を用いることが一般的である。この場合、大きなwのためでさえ、Bj mod P. の値を予めコンピュータ演算したり保持したりすることを要しない。例えば、w=10、j＜210=1024、およびBj =2j ＜ 21024、と仮定する。さらに、Bj =2jが、二進数表記で（1000…000)2として与えられ、その二進数表記においてビットポジションｊで“１”になっている。その結果、予め演算されたテーブルが必要とされない。すなわち、ビット位置ｊに“１”を立て、残りのビット位置を“０”で埋めればよい。
【００４５】
図５にはウィンドウ・サイズをw=10としたときにその考え方の詳細が例示される。これに基づいて説明を続ける。
【００４６】
ステップ1302において、ベキ指数P-1の最初の10のビットが走査されて、バッファjに書き込まれる。カウンタiはp-11に初期化される。そのカウンタの値は次に読むべきビット、即ちPp-11に一致されている。ステップ1303において、アキュムレータA（レジスタA）1121は、2jにセットされる。即ち、Aには最初0が書かれ、ｊ番目のビットは1にセットされる。
【００４７】
その後、べき乗演算が開始される。ステップ1312において、剰余乗算ユニット1113で10回連続してA2 mod Pが演算される。ウィンドウ・サイズがw=10だからである。ステップ1313では連続する10ビットPi,…,Pi-9がべき指数P-1から読み込まれる。ここで、Pはレジスタ1123に格納されており、整数値（Pi…Pi-9)2はバッファjに書き込まれる。jがゼロである場合、乗算は必要とはされず、フェルマーテストでは次の処理を続けることができる。ｊ＞0である場合、レジスタB 1122はステップ1322において2jにセットされる。すなわち、レジスタB1122はゼロにクリアされそのｊ番目のビット位置には1がセットされる。一旦レジスタB 1122がセットされると、A*B mod Pの剰余乗算がステップ1323で剰余付き演算操作ユニット1113を用いて実行される。最後に、ステップ1331で、ベキ指数の走査されたビットPiの位置を表しているインデックスiから10が減じられる。iが9より大きい限り（最も右の走査されたビットPi-9かP1以上であることを保証する）、上記のステップは繰り返される。
【００４８】
iが9より小さくなるときに、フェルマー試験は別に最後の残りのビットを扱う。ステップ1341において残りのビットの値（Pi…P10)2は、バッファjに書き込まれる。Pは奇数であるから、P-1は偶数でありその最下位ビットは0であることに着目する。次に、i+1回A2 mod Pが剰余乗算ユニット1113で演算される（ステップ1342,134）。その後、レジスタB 1122は、最後の乗算の準備ができている。即ち、それは0までクリアされ、そして、そのｊ番目のビットはステップ1351で1にセットされる。その結果、レジスタB 1122にはそのステップ後に値2jが格納される。最終的な剰余乗算A*B mod Pは、ステップ1352で計算される。ステップ1361においてアキュムレータレジスタA 1221が値1を含む場合、Pが見込み素数（probable prime）であるので、フェルマー試験は「成功」を出力して処理を終了する。もしもレジスタAが他の値も含む場合には、Pは合成数であるから「失敗」を出力して処理を終了する。
【００４９】
《フェルマーテストの具体例》
この例では整数P=1971577が素数定判テストに供されるものとする。ここで、Pの値は16進法で表される。二進数において、Pは21ビットでP=(111100001010101111001)2とする。jの第1の値は、Pの最上位側の10ビット、すなわち、j=(1111000010)2=962となる。Aは2962即ち2進標記で末尾に962個のゼロを伴った(1000…000)2に初期化される。カウンタiは10にされる。この後、10回連続的にA2 mod Pの演算が行われ、これによってAは値824444を含むことになる。
【００５０】
次の10ビットは、j=(1010111100)2=700である、したがって、2700がレジスタBに書き込まれ、そして、A*B mod Pが計算される。ここでA=824444、B=2700およびP=1971577である。この演算結果は1であり、そして、その後にもう一度二乗演算が行われる。したがって、累乗の最終結果は1であり、それは実際に1971577が素数であることを意味する。
【００５１】
これにより上記フェルマーテストでは乗算に関して11回の二乗演算（squares）と1回の乗算(multiplication)だけしか要求されないことが明らかであり、これに比べてバイナリ法では20回の二乗演算と11回の乗算が要求されることになるであろう。
【００５２】
今度は整数P=1686499=(110011011101111100011)2について考える。j=(1100110111)=823なので、Aは2823に初期化される。10回連続的にA2 mod Pの演算が行われると、Aは値129007を含み、、次の10ビットはj=(0111110001)2=497である。値2497はBに書き込まれ、そして、剰余乗算A*B mod Pが計算される。その演算結果はA=217983である。そして、最後にもう一度二乗演算が行われる。最終結果は1165463であり、1とは異なり、Pは素数ではない。実際に、P=1686499=1093*1543であり、Pは合成数である。
【００５３】
《ミラーラビンテスト》
ミラーラビンテストとフェルマーテストの両方が素数性の確率的な判定テストである。仮のそれらのテスト結果が失敗あるなら、テストされた整数は絶対的に合成数であるといえる。しかしながら、テスト結果が成功ある場合は、テストされた整数は多分素数であると推定されるだけであり、絶対的に素数であるとは言えない。両方のテストにとって、その結果を失敗とする多くの整数、即ち合成数が存在するが、それには時々そのテストで成功の結果を出す合成数を含んでいる。幸いにも、そのような合成数は多くは無い。特にミラー-ラビンテストの場合には非常に少ない。特に、基数２を用いるミラーラビンテストでそのような誤りを生ずる１６ビット整数ｚは2047, 3277, 4033, 4681, 8321, 15841, 29341, 42799, 49141, 52633である。結果として、ミラーラビンテストが上記の整数の一つでもない１６ビット整数zに対して「成功」のテスト結果を返すならば、そのｚは絶対的な確実性を持って素数であるといえる。
【００５４】
本質的には、ミラーラビンテストはフェルマーテストと類似している、しかし、重要な違いがある。テストする整数はzであり、z-1は2j+1*dと記述され。ここで、j+1はz-1のバイナリ標記における下位側のビットゼロの個数である。基数２を用いるミラーラビンテストのために、剰余累乗乗算x=2d mod zが計算される。もしも、その演算結果が1又はz-1であるならば、テスト結果は「成功」であり、ｚはたぶん素数と言える。そうでない場合にはxはj回乗算され、それぞれの乗算後にｘは再びz-1と比較される。それらが一致する場合は、テストは「成功」を返す。もしもj回乗算後、xがz-1に決して等しくない場合は、テストは「失敗」を返し、zは合成数となる。
【００５５】
図６にはレジスタ1171に保存される16ビットの整数z=(z15…z0)2の素数判定にミラーラビンテストを適用した場合が示される。zが2047、3277、4033、4681、8321、15841、29341、42799、49141、52633のいずれかである場合、zは合成数であり、ステップ1403で「失敗」を返す。さもなければ、z-1の2進表現における末尾のゼロの個数であるjがステップ1404から1406で算出される。累乗の剰余乗算2dのmod z（そこでz-1=2j+1*d）がステップ1411から1416で実行され。アキュムレータxは１に初期化され、ステップ1411でループカウンタiは１５に初期化される。次に、ループカウンタiがjより大きい間、次のステップが実行される。先ず、ステップ1413で剰余乗算x2 mod zが実行される。ここで、xおよびzは１６ビット整数である。その後、zのビットziが1である場合、演算2*x mod zは、左シフトx << 1および法数zの減算を使用してステップ1415で計算される。
【００５６】
累乗計算の後、アキュムレータxが値1を含む場合、アルゴリズムは動作を停止してステップ1441でテスト結果「成功」を返す。そうでない場合には、xはステップ1431でz-1と比較される。それらが等しい場合、アルゴリズムは動作を停止してステップ1443でテスト結果「成功」を返す。等しくない場合、剰余乗算x2 mod zがステップ1432で演算され、ループカウンタは減算される。上記操作はカウンタiが1になるまで繰り返される。アキュムレータがz-1に決して等しくなかった時は、アルゴリズムはステップ1442でテスト結果「失敗」を返す。
【００５７】
《ミラーラビンテストの具体例》
小さい素数テーブルT 1163には、17個の第1小さい素数T[0]=3、T[1]=5、T[2]=7、T[3]=11、T[4]=13、T[5]=17、T[6]=23、T[7]=29、T[8]=31、T[9]=37、T[10]=41、T[11]=43、T[12]=47、T[13]=53、T[14]=59、T[15]=61、T[16]=67が格納されていると仮定する。小さい素数かもしれいな整数はｚ=69=(0000000001000101)2である。ｚは基数2を用いるミラーラビンテストを欺くことができる16ビット整数の一つでは無いから、テストは、z-1=(0000000001000100)2における末尾の０の数から1を引いた数であるｊ、即ちj=1を伴った計算から始めることができる。次に、アキュムレータxは１に初期化され、カウンタiは15に初期化される。i=6までは、z-1の走査されたビットが全てゼロであり、アキュムレータの値は修正されない。繰り返しi=6において、xはステップ1415の左シフトの後に2になり、その後、4回二乗演算と1回の左シフトが行われる。その結果として、ステップ1422では、xは値41を採る。xが1または68と異なるので、もう1回二乗演算が行われ、xは25になり、まだ68とは異なる。この時点で、テストは「失敗」を返す。これは、z=69=3*23が合成数だからであると予想される。
【００５８】
次の奇数は、z=71=(0000000001000111)であり、この場合、j=0である。i=6までは、xは同じままにされ、即ちx=1のままであるが、i=6の1ビット左シフトの後、xは2になる。その後、4回の二乗演算が行われてx=3、1ビットシフトが行われてx=6、1回二乗演算が行われてx=36、そして、1ビットシフトが行われ、最後に、xは1になる。結果として、試験はステップ1422で停止され、x=1、z=71で素数とされる。
【００５９】
《ビット配列の更新》
ビット配列は、小さい素数によって割り切れた候補P=Pinit+2iである合成数を除去するためのエラトステネス（Eratosthenes）のふるいによって示唆される周知の方法である。ビット配列法の大まかな考えは、小さい素数ｚのためにPinit mod zを計算して、P=Pinit+2i mod z = 0（Pはｚによって割り切れる）のような全ての位置iのためのビット配列においてB[i]に0を書き込むことである。図7にはビット配列の適当な位置でゼロを書く方法が説明されている。
【００６０】
ビットアレイフィルユニット1132への入力は、ビット配列1141、初期候補Pinit 1103および小さい素数z 1171から成る。最初に、バッファxはステップ1513で値Pinit mod zによって初期化される。この演算は計算が容易である。その理由は、次のことにある。Pinitが大きな整数であるにもかかわらず、zは単に16ビットだからである。次に、ビットアレイフィルユニットは、Pが奇数でP mod z=0であるような第1の整数P=Pinit+2iを計算する。Pinit mod z=0である場合、Pinitは全ての状態を満足しインデックスiがステップ1515で0にセットされる。一方、xはゼロでなく、Pinit=x mod z、Pinit+z-x=0 mod zだからそれを分かることは容易である。一方、xが奇数なら、z-xは偶数であり、Pinit+z-xは奇数であり、要求される全ての状態を満たす。その結果、ステップ1522では、値（z-x）/2は、減算と右シフト（z-x)>>1を用いてバッファiに書き込まれる。他方、xが偶数の場合、Pinit+z-xは同様に偶数であるが、Pinit+2z-xは奇数である。したがって、ステップ1523で、減算と右シフトz-x>>1を用いて値（2z-x）/2=z-x/2がバッファに書き込まれる。
【００６１】
次に、奇数のPinit+2iがPinit+2=0 mod zを満足するだけでなく、Pinit+2(i+z)、Pinit+2(i+2z)、Pinit+2(i+3z)もそうである。したがって、ステップ1532では、配列において最も大きな可能性のあるインデックスbよりi+k*zが小さいというような全てのインデックスi+k*zのために、ビットB[i]はゼロにクリアされる。最後に、ビットアレイフィルユニットはステップ1551でビット配列を返す。
【００６２】
《ビット配列更新の具体例》
この例では、ビット配列1141はサイズb=64を有し、そして、小さい素数テーブル1163は16の小さい素数、すなわち、T[0]=3、T[1]=5、T[2]=7、T[3]=11、T[4]=13、T[5]=17、T[6]=23、T[7]=29、T[8]=31、T[9]=37、T[10]=41、T[11]=43、T[12]=47、T[13]=53、T[14]=59、T[15]=61）を格納する。最初の候補1103の入力は512ビットの奇数であると仮定する。例えば、
Pinit=7256779693106507655490693859171076267003739588425074050256021409526725926274029082141310206427691245639055995711774350480838509929519895128627108485116697、
である。
【００６３】
まず最初に、ビット配列は、ビット1だけを含む。換言すれば、Bが整数として表現される場合、そのバイナリの表現は、
B=(1111111111111111111111111111111111111111111111111111111111111111)2
となる。Bは64ビットから成る。最初に、素数生成制御ユニットは、小さい素数テーブルT[0],…,T[15]を使用しているビット配列の適当な位置にゼロを書き込む。例えば、T[0]=3およびPinit mod 3 = 1である。1は奇数であり、それ故に、そのビットアレイにおいて(3-1)/2=1の位置で０を書き、そして、位置1+3=4および4+3=7の位置でそうする。T[0]=3によって篩にかけた後に、ビット配列は、
B=(1011011011011011011011011011011011011011011011011011011011011011)2
になる。テーブルTの全ての小さい素数のためにその手順を繰り返して、ビット配列は、
B=(1001011000000001010011000010000001010010000001011001000010000010)2
になる。これによって、フェルマーテストで18ビットだけはまだ1にセットされることが確かめられる整数Pinit+2iに対応する、より小さいインデックスiの値があることが解る。B[0]=1だから、Pinitはフェルマーテストで確かめられなければならない。
【００６４】
同時に小さい素数生成ユニット1161は次の小さい素数を探す。１６ビットレジスタz 1171は、そのテーブルにおいて最後の小さい素数（すなわち、61）を格納する。次の奇数の整数63はミラーラビンユニット1162で照合される。そして、63は素数でないと結論する。63=3*21だかである。同様に、65は素数でない。65=13*5だからである。しかしながら、ミラーラビンユニットは、67が素数であると結論する。
【００６５】
その後、ビット配列は、z=67によって更新される。Pinit mod 67=24であり、ビットアレイにおいて67-24/2=55の位置で０が書き込まれる。残念ながら、B[55]はすでに0である。したがって、67によって篩にかけることはこの例でいかなる好転にもならない。事実、これは次の小さい素数71、73、79、83、89、97および101と同じことである。しかしながら、小さい素数z=103がミラーラビンユニット1162によって生成されるとき、演算Pinit mod 103は13を与え、これはインデックス（103-13）/2=45に対応する。したがって、その前に1であったB[45]に0が書き込まれる。ビットアレイは、
B=(1001011000000001010011000010000001010010000000011001000010000010)2
になる。
【００６６】
フェルマーテスト1111がステップ1222で行われている限り、その手順は継続される。ミラーラビンテストは短い整数（16ビット）で処理するのに対して、フェルマーテストは長い整数（この例では512ビット）を処理するから、多くの小さい素数はフェルマーテストが行われている間に生成可能にされ、追加されたものが除外可能にされる。例えば、フェルマーテストで512ビットのそれぞれの剰余乗算のために一つの小さい素数が生成可能にされることを仮定すると、そのフェルマーテストの間に512の小さい素数が追加して生成可能にされる。その場合、ビット配列は、
B=(0001011000000000000000000000000001000010000000011000000010000000)2
になる。その果として、最初のフェルマーテストの後、ビットアレイには８個が残されるだけとなる。
【００６７】
最初のフェルマーテストは入力としてPinitを採る。しかしながら、累乗の演算2^(Pinit-1) mod Pinitの結果は1ではない、したがって、Pinitは素数ではない。次のビットアレイのゼロ以外のエントリはB[3]であり、次の素数候補はPinit+6である。即ち
P=7256779693106507655490693859171076267003739588425074050256021409526725926274029082141310206427691245639055995711774350480838509929519895128627108485116703
である。値Pinit+6はレジスタP 1123に格納される、そして、フェルマーテストは2^(Pinit+5) mod Pinit+6の計算を始める。累乗計算の間、新規な小さい素数がビット配列における多くのゼロ以外のエントリを除去するために生成されることができる。しかし、この例では、512の追加的な小さい素数についてさえ、どんなゼロも配列には書かれない。幸いにも、第２のフェルマーテスト2^(Pinit+5) mod Pinit+6の結果は1であり、実際に、Pinit+6は素数である。この点で、素数生成ユニット914は、Pinit+6の値を返す。
【００６８】
《拡張》
本発明は、上記の実施の形態１で説明した内容に限定されない。例えば、上記システムは、携帯電話、ＰＤＡ、そして公開鍵暗号方式を利用して限られた計算機リソースやメモリリソースを用いる如何なる電子デバイスにも使用されることが可能である。累乗のタイプは異なることがありえる。例えば、累乗の剰余乗算ユニットの代わりに、モンゴメリー乗算装置が利用されることも可能である。小さい素数の再構成の方法は、上記の例で説明した内容に限定されない。例えば、２とは異なる基数を伴ったミラーラビンテストを利用したり、フェルマーテストやその他のコンビネーションテストのような異なったテストを利用したりすることも可能である。同様に、ミラーラビンやスロベイストラーゼン(Solovay-Strassen)テストのように、素数候補に対する異なった素数性判定テストも採用可能である。、更に、再構成の種類はウインドウ方法に限定されず、NAF（Non Adjacement Form）又はFANの再構成法、或いは、その他の適当な再構成法を用いることも可能である。
【００６９】
３．実施の形態２
オンボードの暗号生成に着目した説明を行う。
【００７０】
《携帯機器》
図８には携帯式電子装置（携帯機器）101が示され、例えばICカード、或いはセキュリティ機能が強化されたデバイスである。携帯機器101は、その入出力インタフェース131を介してネットワーク141に接続され、データ142を送り、データ143を受信することができる。このネットワーク141を通して、携帯機器10はATM 151、コンピュータ153又は他の携帯機器154と通信することができる。ネットワーク141の上の通信路でのセキュリティがなければ、メッセージは悪意のあるユーザによって横取りされることがある。したがって、携帯機器にはセキュリティ機構が搭載される必要がある。これらのセキュリティ機構は、メッセージ暗号化およびデジタル署名を含み、そして、実施の形態２では、事実上の標準であるRSAと称される公開鍵暗号法が適用される。
【００７１】
携帯機器101は、3種類のユニットとして、入出力インタフェース131、計算ユニット121およびメモリ111を含む。
【００７２】
入出力インタフェース131によって携帯機器は1または幾つかのネットワークに接続可能である。実施の形態2では、携帯機器101は2つの入出力インタフェース132および133を含む。それは接触インタフェースと非接触インタフェースを実現する。データ処理部121はＣＰＵ 122、モンゴメリー乗算コプロセッサ123および乱数発生器124を含む。ＣＰＵ（央演算処理装置）は、32ビット命令が適用され、それはメモリ操作命令、加算、減算、乗算または除算などのような算術命令、シフト、ANDまたはOR等の論理演算命令、そして制御命令を含む。ＣＰＵは、32ビット命令からなるプログラムを実行することが可能である。概して、ＲＳＡ関連の動作は、512ビット以上のかなり大きな整数を操作する。この種の大きい整数算術演算処理がＣＰＵ 122によって実行されるプログラムとして適用されることについては、実際的ではない。携帯機器は非常に限られた計算機処理能力しか持たないからである。そういうわけで、携帯機器は、モンゴメリー乗算コプロセッサ123のような専用の計算ユニットをＲＳＡのために備えている。モンゴメリー乗算コプロセッサはレジスタA 115、B 116およびN 117にインタフェースされ、そのレジスタ117がn-ビット奇数の整数を保有する場合、モンゴメリー乗算A*B*2-n mod Nまたはモントゴメリー乗算A*A*2-n mod Nを計算する。ここで、それぞれ、整数AおよびBはレジスタ115および116に保存される。乱数発生器124はランダムなビットを連続的に生成することができる。そして、それはＲＳＡを含む暗号アプリケーションのために使用可能にされる。
【００７３】
3種類のメモリ111は次のように区別される。バッファデータ及びテンポラリデータを格納するための揮発性メモリ112、ユーザデータの格納に利用される書き込み可能な不揮発性メモリ113、プログラムの格納に利用されるリードオンリ不揮発性メモリ114である。3つのモンゴメリー乗算レジスタA 115、B 116およびN 117は、モンゴメリー乗算コプロセッサ123と接続される基本的に揮発性メモリである。実施の形態２において、揮発性メモリにはRAM（ランダム・アクセス・メモリ）が適用され、書き込み可能な不揮発性メモリにはEEPROM（電気的に消去可能ＰＲＯＭ）が適用され、リードオンリの不揮発性メモリにはマスクＲＯＭ（読出し専用メモリ）が適用される。
【００７４】
特に制限されないが、実施の形態２では実施の形態１で説明した暗号化ユニット911に対応する構成をソフトウェア的に実現することを想定している。即ち、不揮発性メモリ114等に必要なプログラムが格納され、これをデータ処理部121のCPU122等が実行することによって、後述するフローチャートに示される処理が行われる。
【００７５】
《ＲＳＡの鍵ペアの生成》
メッセージをデジタル的に署名するかまたは解読するために携帯機器101上のＲＳＡ暗号システムを使用する前に、ＲＳＡ 鍵ペア（keypair）を発生しなければならない。上記したように、携帯機器上で鍵ペアを生成することは有意義である。図9にはその手順が詳細に記載されている。鍵ペア生成の入力201は、n（公開法数Nのビット長）、p（秘密素数Pのビット長）、q（秘密素数Qのビット長）、E（公開べき定数）、b（1ビットアレイのサイズ）、予め定められたテーブルT[0],…,T[t-1]）、及びmri（ミラーラビン繰り返しの数）を含む。
【００７６】
ビット配列B[0],…,B[b-1]、テーブルT[0],…,T[t-1]およびミラーラビン繰り返しの数の役割は、後で説明する。ステップ202において、2つの最初の奇数の乱数PinitおよびQinitが乱数発生器124によって発生される。鍵ペアの生成手順は、[ Pinit,…,Pinit+2(b-1)]と[ Qinit,…,Qinit+2(b-1）]の間で素数PおよびQを探しそうとすることである。したがって、ステップ203は、検索間隔が常に正しい範囲であることを保証し、それぞれ、PおよびQはｐビットとqビットを有することを保証する。ステップ204において、結果Pinit*Qinitが正確にnビットを有することが確かめられる。これが正しいなら、法数N=P*Qは確実にnビットを有する。ステップ203または204のいずれかが失敗の場合、新たに最初の乱数PinitおよびQinitがステップ202で発生される。
【００７７】
一旦最初の乱数PinitおよびQinitが全ての要求される状態を満たすと、素数生成手順が始まる。bビットのビットアレイB[0],…,B[b-1]はRAM 112に保存され、ステップ211で初期化される。ビットB[i]は、整数Pinit+2iに対応する。整数Pinit+2iが全て奇数である。Pinitが奇数で、2iが偶数だからである。実際、素数生成手順のゴールは、間隔[ Pinit,…,Pinit+2(b-1)）]で素数を見つけることである。偶数は明白に素数ではなく、問題なく無視することができる。ビット配列で1にセットされるビットB[i]は正しい候補であり、それは更に素数性が判定されなければならない。ゼロにクリアされるビットB[i]は素数で無いことが知れた不適な候補に対応される。まず最初に、全ての候補はステップ211で「正しい」にセットされ、そして、ステップ212では、不適な候補にはビットアレイでゼロが書き込まれ、それらの処理は図１１に記載されている手順で行われる。ステップ212で不適な候補が除外された後、残りの正しい候補はステップ213で素数性が判定され、それによって、素数P及びDP*E =1mod P-1のような逆元DPが出力され、又は「失敗」が返される。ステップ213は図１０にその詳細が示される。素数Pが見つかる場合、ステップ221からステップ224で最初の候補Qinitに対して同じ手順が繰りお返される。ステップ214または224において「失敗」の場合には、新たな初期乱数PinitおよびQinitがステップ202で発生される。
【００７８】
2個の素数PおよびQが見つかった後、D*E=1 mod（P-1)*(Q-1)を満足する秘密鍵Dと、公開法数N =P*Qがステップ231において算出される。公開法数Nはモンゴメリー乗算コプロセッサ（単にコプロセッサとも記す）123で計算されることができ、公開鍵Dは非特許文献1に記載されている周知のバイナリ拡張GCDアルゴリズムによって計算されることができる。RSA-CRT Qinvの秘密鍵要素は、Pが素数だからQ-1=QP-2 mod Pになるという事実を用いてステップ232で算出される。べき乗の剰余乗算QP-2 mod Pはモンゴメリー乗算コプロセッサ123を使用して算出されることができる。例えば、特許文献１に記載されているモンゴメリー累乗アルゴリズムを使用する。最後に、公開法数N、秘密鍵D、秘密鍵要素RSA-CRT P, Q,DP,DQおよびQinvを含む全ての鍵素子は、ステップ233でEEPROM 113に書き込まれる。
【００７９】
《素数生成》
図9において、ステップ213および223では、素数P及びQ、秘密鍵素子DP =E-1mod P-1、DQ =E-1mod Q-1が発生される。この素数生成手順に対する入力301は、最初の偶数乱数Pinit（またはQinit）、公開ベキ指数E、ビット配列B[0],…,B[b-1]）、及びmri（ミラーラビンテストのための繰り返しの数）である。
【００８０】
ステップ302において、RAM 112に格納されたカウンタiは0に初期化される。このカウンタは、ビット配列B[i]の要素をアドレシングし、素数候補Pinit+2iを表すために用いられる。ステップ311および312において、ビット配列B[i]のエントリが、走査される。B[i]=1のとき、候補Pinit+2iは「正しい」とされ、更に次のステップでの素数性が判定されなければならない。B[i]=0のときは、候補は「不適」とされ、次の候補がテスト対象にされる。
【００８１】
ステップ321において、候補P=Pinit+2iがＣＰＵ 122で演算されて、演算結果がコプロセッサレジスタ117に格納される。次に、ステップ322でフェルマーテストを用いてPの素数性が判定される。フェルマーテストに付いては図6に記載される。Pがフェルマーテストをパスすることができる場合、Pは実際に素数であるという十分な可能性がある。
【００８２】
しかしながら、Pは更なる状態を満たさなければならない。すなわち、P-1と公開ベキ指数Eの最大公約数は、逆元DP=E-1 mod P-1が存在することを確実にするために、1（gcd(P-1,E)=1）でなければならない。したがって、ステップ331で、例えば非特許文献1に記載のバイナリ拡張GCDアルゴリズムを使用してDPが算出される。手順が「失敗」の場合は、gcd(P-1,E)が1でなく、Pは拒絶され、次の候補がテストされる。
【００８３】
フェルマーテストは合成数とされる候補を早く除外するために有用であるにもかかわらず、それは良好な確実性をもってそれらの素数を確立するには十分でない。例えば、カーマイケル番号と呼ばれている合成数が存在し、それは多くの場合フェルマー試験にパスすることができる。高い信頼性をもってPの素数性を保証するために、実施の形態２はフェルマーテストがうまく行った後でさ、数回、ミラー-ラビンテストを繰り返す。繰り返し数（mri）は、適切に選択されなければならない。非特許文献１は、繰り返し3回ミラーラビンテストをうまくパスすることができる1024ビットのランダム整数が素数でないという確率は2-80であると述べている。換言すれば、3回のミラーラビンテストをパスする候補を選んだときエラーが起きる確率は2-80である。それはごくわずかである。ステップ341において、カウンタjが、RAM 112上で0に初期化される。jが繰り返し数mriより小さい限り、図14に記載のミラーラビンテストがステップ342で実行され、カウンタjがステップ343でＣＰＵ 122によりインクリメントされる。Pがミラーラビンテストをmriで示される回数成功したならば、Pは多分素数であり、素数生成手順によってステップ351で、逆元DPとともに選ばれる。しかしながら、ビット配列、フェルマーテスト、逆、ミラーラビンテストのいずれかが失敗する場合、iはステップ361でインクリメントされ、次の候補Pinit+2i+2がテストされる。間[ Pinit,…,Pinit+2(b-1)]における手順で満足な素数が見つからなかった場合には、手順はステップ352で失敗となる。
【００８４】
《ビットアレイ》
tのための最適値があり、それは、素数生成手順の速度を最大にするように篩にかけるために使われる小さい素数の数である。即ち、一方において、より小さな素数で、ビットアレイからより多くの要素が篩にかけられることができ、それはより洗練された素数判定テストを呼び出す回数を減らし、他方において、より小さな素数ｚを使用することはビットアレイにおけるP mod zと書き込み操作の減少に帰結する。しかしながら、小さな素数の最適数は、典型的に大きく、1,000以上である。
【００８５】
多くの小さい素数が篩にかけるために使われるときに、大きなテーブルはそれらを格納するために必要である。簡潔に説明するために、素数ビット長に従い、それぞれの小さい素数は、1バイト（8ビット）または2バイト（16ビット）で格納されることができる。残念なことに、8ビットの素数は多くない。小さい素数テーブルにおける要素のほとんどはROM 114の2バイトを占める。例えば、2,048の素数が篩にかけるために使われる場合、テーブルはROM 114に4キロバイトを占める。それはICカードにとって非常に大きなサイズである。
【００８６】
さらに、zが小さい素数のオペレーションPinit mod zはコプロセッサ123で計算される、しかし、zが小さいにもかかわらず、Pinitは大きい。したがって、コプロセッサ123で計算されるモンゴメリー乗算のビットサイズは、Pinitのビットサイズであるｐによって決まる。その結果として、モンゴメリー乗算の結果は、MontMult(Pinit,1,z)=Pinit*2-p mod zである。そして、それは所望の結果Pinit mod zとは異なる。その代わりに、操作MontMult(Pinit,2p mod z、z)=Pinit*2p*2-p = Pinit mod zが計算されなければならない。結果として、モンゴメリー定数の表が必要になり、それは全ての小さな素数zのための全てのモンゴメリー定数2p mod zを保有する。2,048の小さい素数の場合、これは小さい素数のために４キロバイトおよびモンゴメリー定数のための4キロバイトのメモリを必要とする。更に悪いことに、モンゴメリー定数は素数候補Pのビット長ｐに依存する。例えばプログラムが1024ビットおよび2048ビットのＲＳＡをサポートしなければならない場合、モンゴメリー定数のために2個の異なったテーブルが必要になる。
【００８７】
上述の説明より、篩いがけのために多数の小さい素数を用いることが必要とされることは容易に理解されるとところであるが、このアプローチはICカードの不十分なメモリ資源に殆ど適合しない。実施の形態2では、多数の小さい素数が使われるが、必要なメモリ量をICカードにとっても合理的であるようにする。課題を解決するポイントは二つある。第1は、それらの全値よりもむしろ連続する小さい素数の間の相違を格納することである。第2は、それらを格納することよりもむしろ実行時にモンゴメリー定数2p mod zを演算することである。
【００８８】
上記第１ポイントにより、小さい素数を格納するためのメモリ容量は半減する。何故ならば、2個の連続する小さい素数の間の相違は通常小さく、2バイトではなく1バイトで格納可能にされるからである。実際に、1バイトで格納されることができる2つの連続的な素数間の最大の差はΔ=118であり、z1=1,349,533とz2= 1,349,651の間で生ずる。換言すれば、z1=1,349,533より小さい素数間での違いは、常に1バイトに格納可能である。
【００８９】
第2ポイントによる利点は、メモリの要求容量がモンゴメリー定数に対して全く除去されるということである。加えて、充分なスケジューリングを伴って、CPU122によって計算されるモンゴメリー定数の演算が、コプロセッサ123によって演算されるモンゴメリー乗算 MontMult(Pinit,2p mod z,z)の処理に並列化できる。
【００９０】
したがって、実施の形態２のアプローチとt=2,048の小さい素数を用いることは、小さい素数間の差のテーブルT[0],…,T[t-1]をＲＯＭ114に格納するのに必要なメモリ容量を２キロバイトとし、篩い操作に対して動作速度上のペナルティーを課すことはなく、また、処理コストの大きな素数判定処理の呼出し回数の減少に起因して処理効率を好転させることができる。
【００９１】
次に、図１１にはビットアレイフィルの操作手順の詳細が例示される。ステップ401の入力は、pビットの初期奇数乱数Pinit（またはqビットのQinit）、最初に１で満たされたビット配列B[0],…,B[b-1]）、及び、連続する小さい素数間の相違を格納するテーブルT[0],…,T[t-1]、から成る。例えば、テーブルTがt=4の小さい素数に関する情報を格納すると仮定する。T[0]=3は、2より大きな第1素数例えば３をを格納する。次の素数は5=3+2であるからT[1]=2である。次の素数は7=5+2であるからT[2]=2である。次の素数は11=7+4であるからT[3]=4である。ステップ402において2個のバッファz1とrはRAM112において初期化される。前記バッファｚ１は第1素数T[0]の値を格納し、バッファrは第1のモンゴメリー定数2p mod T[0]である。r=2p mod z1の計算は、図12に記載されている。次に、z1はコプロセッサレジスタN 117にコピーされ、rはレジスタA 11５に、PinitはレジスタB116に、コピーされる。その後、コプロセッサ123はMontMult(r,Pinit,z1)の演算を開始する。計算が終わると、演算結果Pinit mod z1がRAM 112のバッファx1に書き戻される。コプロセッサ123がMontMult(r,Pinit,z1)の演算を処理中には、第2の小さい素数およびモンゴメリー定数がＣＰＵ 122によって用意される。第2の小さい素数はz1+T[1]であり、ここで、T[1]は第1素数と第2素数の間の差を格納する。
【００９２】
この次のステップにおいて、ビット配列はテーブルT[0] …,T[t-1]によって再構成された全ての小さい素数を使用して更新される。テーブルT[0] …,T[t-1]はその構成要素をインデックスするカウンタiを使用する。ビット配列の更新手順の基本的な考え方は以下の通りである。即ち、第1に、コプロセッサ123でx2 = Pinit mod z2を計算し、ここで、z2はテーブルTでインデックスiを有するアクティブな小さい素数に対応する。第2に、第1の処理と同時に、CPU122がインデックスi+1に対応する次の小さい素数z3を演算する。第3に、ビットアレイはx1 = Pinit mod z1で更新され、ここで、z1はインデックスi-1に対応する前の小さい素数である。
【００９３】
ステップ412において、Pinit mod z2はコプロセッサ123で計算される。ここで、z2はインデックスiに対応する小さい素数である。より正確に言うと、小さい素数z2はコプロセッサレジスタ117へコピーされ、モンゴメリー定数がコプロセッサレジスタ115へコピーされ、レジスタ116はすでにPinitを保持している。次に、コプロセッサはMontMult(r,Pinit,z2)の演算を開始し、その演算結果はRAM 112のバッファx2に格納される。同時に、ステップ414において、CPU12による演算z3=z2+T[i+1]のためにテーブル要素T[i+1]がアクセスされる。ここで、z3はインデックスi+1に対応する次の小さい素数ある。そのモンゴメリー定数2p mod z3は同様に計算される。i=t-1又はi=tのときステップ414の処理はスキップされる。テーブルTはt要素だけを有するからである。
【００９４】
この状態で、ビットアレイは前のステップi-1で演算された値x1=Pinit mod z1で更新される。x1=0である場合、Pinitはz1で割り切れ、そして、ステップ432でゼロが直接B[0]に書き込まれる。x1が奇数の場合、P=Pinit + z1 - x1はP=0 mod z1を満足する。加えて、Pinit、x1およびz1は奇数であり、それゆえにｐは奇数である。そして、Pに対応するインデックスjはj=(z1-x1)/2であり、これは、ステップ423で、２による割り算に代えて右シフトを用いてCPU122により演算される。X1が偶数なら、Pinit + z1 - x1は偶数であり、ビットアレイの要素ではない。その代わりに、次の奇数が選ばれる。すなわち、P = Pinit + 2z1 - x1である。対応するインデックスはステップ423でＣＰＵ 122による右シフトを用いてj=z1 - x1/2として計算される。
【００９５】
ステップ422または423が実行された後、Pinit +2j= 0mod z1のような第１のインデックスjは既に有効になっている。しかし、実際には、整数Pinit+2j+2z1、Pinit+2j+4z1、Pinit+2j+6z1およびその他もz1で割り切れる。したがって、ステップ432で、ゼロがビットB[j]に書かれ、jが範囲[ 0,…,b-1]にある限りＣＰＵ 122によってz1がインデックスjに追加される。そのように、Pkにような全ての奇数Pk=Pinit+2*k*(j+z1)はビットアレイに存在し、Pk mod z1=0が「不適当」な候補として識別される。
【００９６】
上記手順はテーブルT[2],T[3],…,T[t-1]の全ての要素のために繰り返される。ステップ441において、値z2およびx2= Pinit mod z2がz1およびx1にコピーされ、ステップ442で、z3がz2にコピーされ、且つテーブルT[i]の要素を指すカウンタiはインクリメントされる。
【００９７】
《モンゴメリ定数の演算》
図１１において、小さい素数zと関連するモンゴメリー定数r=2p mod zの計算は、ステップ402および414で実行される。図１２はその手順を詳細に例示する。この手順への入力は、素数候補Pのビット長ｐ、および小さい素数zである。小さい素数zは小さいので、そのビット長は通常16ビット未満であり、小さい素数zに関連した全ての演算はＣＰＵ 122によって容易に処理することができる。ここではモンゴメリー乗算コプロセッサ123の使用は必要ではない。結果として、モンゴメリー定数の計算は、コプロセッサ動作に並列させることが可能になる。
【００９８】
実施の形態２ではモンゴメリー定数の計算にはRAM 112に配置された3個のバッファを使用し、バッファはステップ502で初期化される。バッファは2の累乗を格納し、xは部分的な結果を格納するアキュムレータであり、iは計算2p mod zの演算におけるベキ指数pのスキャンに使われる。実施の形態２で使用される技術は、右から左へのバイナリの累乗である。基本的な考えは、y=2^(2^0)=21=2 mod z、y=2^(2^1)=22=4 mod z、y=2^(2^2)=24=16 mod z、y=2^(2^3)=28=256 mod zおよびその他を計算し、ｐのバイナリ表現を右から左にスキャンし、スキャンされたビットが１のとき、x=x*y mod zを計算するというものである。
【００９９】
p=0である場合、x=1はステップ542に返される。そうでない場合には、ステップ512でＣＰＵ 122を使用してiが右に1ビットシフトされる。iの最下位ビットが1であるとき、右シフト動作はキャリーを生成する。この場合、xはステップ522でx*y mod zに更新される。実施の形態２において、ＣＰＵはx*y mod zのような剰余乗算を直接サポートしない。したがって、動作は2つの部分に分けられる。一つは古典的乗算x*yであり、もう一つは剰余演算x mod zであり、双方共にCPUによってサポートされる。
【０１００】
次に、バッファiがゼロでない限り、次に要求される２の累乗が計算される。その手順がｋ番目の繰り返しを実行していると仮定すると、y=2^(2^k)である。次に要求される２の累乗は、2^2^(k+1) = 2^(2^k)*2^(2^k) = y*y mod zであり、ステップ532で演算され、それには1つの乗算y*yと一つの剰余を持つ除算y mod zが利用され、それはＣＰＵ 122によって演算される。
【０１０１】
バッファiは繰り返し毎に右シフトされるので、結局、iは0になる。この点で、べき乗の剰余乗算2p mod zは完了され、演算結果x=2p mod zを返すことができる。
【０１０２】
《フェルマーテスト》
楕円曲線暗号の場合、累乗演算の速度を改善することが良く知られている。例えばNon-Adjacent Form（NAF））のようなべき乗数のための符号表現を使用する。NAFは、単純なバイナリの累乗より高速で、再計算を必要としない。しかしながら、楕円曲線累乗とＲＳＡ累乗との間には大きな違いがある。すなわち、前者の場合、位置の逆転を殆ど演算コスト無く得ることができるが、後者の場合、若干の整数の反転演算に大きな演算コストを要する。符号表現における負数に反転演算が必要になるから、この方法は通常、ＲＳＡのためには不適当と考えられる。
【０１０３】
通常それらがＲＳＡのために魅力的でないという事実にもかかわらず、実施の形態２はフェルマーテストのためには符号表現を使用する。実際、A*B-1 mod Pは一般に大きな演算コストを要する動作である、しかし、B=2である場合、動作はA/2 mod Pになる。さらに、2による除算は単なる右シフトにり、おそらくPの加算の後になる。要するに、Aが偶数の場合A>>1（1ビット右シフト）、Aが奇数の場合は（A+P)>>1（1ビット右シフト）を行う。
【０１０４】
NAF再符号化は右から左に行われ、べき乗は左から右に行われるから、双方の処理を結合することはできない。即ち、最初に、ベキ指数（exponent）が再構成され、その新な表現の数が異なるRAM域に格納され、第２に、べき乗計算が行われる。この方法の欠点はベキ指数が非常に大きいということであり、RAMにその再構成されたフォームを格納するための領域を予約しておかなければならない。再構成されたフォームは、少なくともオリジナルのベキ指数に比べて大きい。前記再構成とべき乗演算が共に左から右に行われるとするなら、新たな表現を格納するためにRAMを割当てることを要しないであろう。前記双方の処理を一つに結合することが可能に成るからである。
【０１０５】
実施の形態２におけるフェルマーテストは次の結果を得ることができる。即ち、再構成とべき乗演算を一つの固有の処理フェーズに統合することができ、それゆえに、再構成された指数を格納するためのメモリの追加が必要とされない。これを達成するために、フェルマーテストはFAN表現を利用し、これは通常楕円曲線で使われ、楕円曲線については例えば特許文献２に記載があり、ここでは、wMOFと呼ばれている。FANはその生い立ちの点ではNAFと同様であるが、FAN再構成は左から右に実行され、べき乗演算フェーズと統合することはできない。
【０１０６】
FANべき乗演算における1つの繰り返しは、多くてもPi+1,Pi,Pi-1の3ビットのベキ指数をスキャンすることである。その内容はケース１〜ケース6に分類できる。
[ケース1 ]：（Pi+1Pi)=(11)2は（Si)=(0)に再構成され、iは i-1にセットされる。
[ケース2 ]：（Pi+1PiPi-1)=(011)2は（SiSi-1)=(1)に再構成され、iは i-1にセットされる。
[ケース3 ]：（Pi+1PiPi-1)=(010)2は（Si)=(01)に再構成され、iは i-2にセットされる。
[ケース4 ]：（Pi+1Pi)=(00)2は（Si)=(0)に再構成され、iは i-1にセットされる。
[ケース5 ]：（Pi+1PiPi-1)=(100)2は（SiSi-1)=(-1)に再構成され、iは i-1にセットされる。
[ケース6 ]：（Pi+1PiPi-1)=(101)2は（Si)=(0-1)に再構成され、iは i-2にセットされる。
ケース1および4の場合、1回の二乗演算（square）がコプロセッサ123で行われる。ケース2の場合、1回の二乗演算がコプロセッサ123で行われ、CPUで1回の左シフト演算が行われる。ケース5の場合、1回の二乗演算がコプロセッサ123で行われ、CPUで1回の右シフト演算が行われる。ケース3の場合、2回の二乗演算がコプロセッサ123で行われ、CPUで1回の左シフトが行われる。ケース６の場合、2回の二乗演算がコプロセッサ123で行われ、CPUで1回の右シフトが行われる。
【０１０７】
図１３に基づいてその内容を詳述する。ステップ601におけるフェルマーテストへの入力はpビットの奇数の整数Pから成り、それが素数性の判定対象になる。ICカードのメモリ112において、Pは一連のpビット（Pp-1…P0)2として格納される。モンゴメリー乗算コプロセッサはMontMult(A,A,P)=A*A*2-p mod Pを演算するので、コプロセッサレジスタA 115は２で初期化されず、2*2p mod Pで初期化される。この方法はMontMult(A,A,P)=2*2*22p*2-p=2*2*2p-mod Pとなる。モンゴメリー乗算の後にも要素2pがまだあることが分かる。ステップ602において、コプロセッサレジスタ115は2p+1 mod Pによって初期化され、これはpがあまり大きくないからであり、通常はp=512又はp=1024であり、バイナリでは、2p+1は１と後続するp+1個の０という形式で単純に表現される。次に、２p+1がPよりも小さくなるまで必要に応じて何回もPは減算される。さらに、カウンタiはRAM 112でp-2に初期化される。
【０１０８】
ケース1、2、3、4、5および6の全てにおいて、常に二乗演算が行われる。それゆえに、モンゴメリ乗算がステップ612で計算される。より正確に言うと、コプロセッサレジスタA 115がモントゴメリー乗算MontMult(A,A,P)によって更新され、ここで、素数候補Pの入力はコプロセッサレジスタN 117に格納される。次に、Pの値に依存する異なったパターンがあり、ここで、各々のパターンはケース1、2、3、4、5または6のうちの1つに対応される。Pのi番目のビット即ちPiはステップ613で判定され、Pがコプロセッサレジスタ117に格納され、カウンタiはRAM112にある。Pi=1なら、ケース1,2,又は3に対応する操作が実行されなければならない。Pi=0のときは、ケース4,5,又は6に対応する操作が実行されなければならない。
【０１０９】
Pi=1である場合、ビットPi+1の値はステップ612において点検される。それによる点検内容は以下の通りである。
[ ケース1 ] Pi+1=0なら、検出されたケース１に対応するビット処理が行われる。ケース1は1つのモントゴメリー乗算処理だけを要求し、他の処理は必要とされず、次のビットの値がチェックされる。Pi+1=0である場合、ビットPi-1はケース2および3を区別するために点検されなければならない。したがって、ステップ622で、ビットPi-1の値が点検される。
[ケース2 ] Pi-1=0の場合、検出されたケース２に対応されるビット処理が行われる。それゆえに、ステップ623でコプロセッサレジスタA 115のデータがCPU12により1ビットが右にシフトされる。シフト操作の後、レジスタA 115のデータはｐビットよりも多くなる。すなわち、この場合、ステップ625で必要に応じて何回もPはAから減じられなければならない。
[ケース3 ] Pi-1=1の場合、検出されたケース３に対応されるビット処理が行われる。ステップ641で更にモンゴメリ乗算が行われ、カウンタiがもう1回デクリメントとされる。その後、コプロセッサレジスタA 115のデータがステップ623で左に1ビットシフトされ、ステップ625においてAがpビットよりも多いならば、PがAから減算される。しかしながら、i=1である場合、代わりにケース2が実行される。Pi=0である場合、ビットPi+1の値はステップ631において点検される。それによる点検内容は以下の通りである。
[ケース4 ] Pi+1=0の場合、更なる動作は必要とされない。Pi+1=1である場合、ケース5および6を区別するためにPi-1が点検されなければならない。
[ケース5 ] Pi-1=0の場合、Aは1ビット右へシフトされる。Aが偶数の場合、その最下位ビットは0であり、Aはステップ635でＣＰＵ122によって直接シフトされる。しかし、Aが奇数の場合、Pはステップ634でＣＰＵ 122によってAに加算される。AとPの両方とも奇数だから、A+Pは偶数であり、ステップ635で右へシフトされる。
[ケース6 ] Pi-1=1の場合、モントゴメリー乗算が行われ、カウンタiはステップ642でデクリメントされ、その後、ステップ633に続く右シフトが行われる。
【０１１０】
上記のステップは繰り返され、カウンタiは０になるまでステップ614でデクリメントされる。P-1の2つの最下位ビットはそれぞれに処理される。P-1の最後から二番目のビットはP1である。P1=0である場合、モントゴメリー乗算はステップ651で演算され、P1=1の場合は、必要に応じてステップ654のPを加えた後に、モンゴメリー乗算の後にステップ655の右シフトが続く。P-1は偶数だから、P-1の最後のビットは常に0であり、したがって、モントゴメリー乗算はステップ661で計算される。この点で、全てのビットは計算されたが、モンゴメリー定数の2p mod Pは削除されなければならない。したがって、ステップ663で、データ1はコプロセッサレジスタB 116に書き込まれ、モンゴメリー乗算MontMult(A,1,P)=A*2-p mod Pはコプロセッサ123によって演算される。この最後の乗算はモンゴメリー定数の2p mod Pをキャンセルし、そして、コプロセッサレジスタAに格納されているデータはステップ662に戻される。Aが1である場合、Pは多分素数であり、Aが1でない場合、Pは合成数である。
【０１１１】
《フェルマーテストの具体例》
この例では、整数P=109が素数性の判定対象であると仮定する。ベキ乗の剰余乗算2108 mod 109は、図13によるフェルマーテストを使用して計算される。二進数で、108=(1101100)2、であり、、二進法に基づく左シフトを備えたフェルマーテストは3つの左シフトを行い、これはその最上位ビットの１に加えて1の桁が更に3桁あるからである。他方、108のFAN表現は108=(100-10-100)であり、2つの右シフトだけがある。
【０１１２】
詳しく説明する。P=109のビット長はp=7である。最初に、Aは2p+1 mod P = 28 mod 109で初期化される。28から= 256、28-2*109=38、レジスタA=38、カウンタiはp-2 = 5だからである。
[ i=5 ]の場合、レジスタAはMontMult(A,A,P)=MontMult(38,38,109)=76によって更新される。次のP5=1、P6=1、そして、対応する再符号は0であり、したがって、更なる操作は必要とされない。
[ i=4 ]の場合、レジスタAは、MontMult(76,76,109)=86によって更新される。次のP4=0、P5=1、P3=1、そして、対応する再符号が0-1である。レジスタAはMontMult(86,86,109)=68で更新され、カウンタiはデクリメントされる。68は偶数であるから、直接右シフトA>>1が実行され、レジスタAは34に更新される。
[ i=2 ]の場合、Aは、MontMult(34,34,109)=101に更新される。次のP2=1、P3=1、そして、対応する再符号は0である。
[ i=1 ]の場合、Aは、MontMult(101,101,109)=55によって更新される。次のP1=0、P2=1、P0=0、そして、対応する再符号は-1にある。レジスタAは偶数であるから、109がAに加えられ、右シフトが計算され、その結果、A=82を得る。
【０１１３】
そこから、フェルマーテストの最終ステップが実行される。P1=0、2つのモントゴメリー乗算が実行される。即ち、MontMult(82,82,109)=90およびMontMult(90,90,109)=19。MontMult(19,1,109)=1であるから、フェルマーテストは1を出力する。それは109が素数であるという事実と整合している。
【０１１４】
《ミラーラビンテスト》
ミラーラビンテストにおいてP-1は2j+1*Dと書かれる。ここで、j+1はP-1のバイナリの表現における末尾の０の数である。第１に、ある基数Bのために、累乗B←XD mod Pが計算される。XD mod P=1である場合、Pは多分素数であるだろう。他方、B=XD mod Pが1でない場合、Bは-1と比較される。Bが-1でない場合、Bはj回二乗演算され、各々の二乗演算の後、再び演算結果が-1と比較される。それら二乗演算を1つ行った後、B=-1のとき、フェルマーテストは停止され、Pはたぶん素数であるとい結果が得られる。そうでなければPは合成数である。
【０１１５】
フェルマーテストのように、ミラーラビンテストへの入力は、ステップ701のp-ビットの奇数P=(Pp-1…P0)から成る。RAM 112に配置されたカウンタjは、P-1における末尾の０の数から1を引いた数を格納する。ステップ703および704において、1にセットされるビットが見つかるまで、Pの最下位ビットがスキャンされる。各々の０のために、カウンタjはCPUでインクリメント操作される。
【０１１６】
一旦jが決定されると、累乗の基数がステップ711でランダムに選ばれる。乱数発生器124は[p-ビット]のランダムな整数Xを生成し、それはコプロセッサレジスタA 115に格納され、同様にコプロセッサレジスタB 116にコピーされる。カウンタiはRAM 112においてp-2に初期化される。このカウンタiは、次のステップで累乗の剰余乗算BD mod Pが演算されている間に、P-1のどのビットがスキャンされるかについて指す。累乗の剰余乗算は、左から右にバイナリの方法を用い、モンゴメリー乗算とモンゴメリー二乗演算の手順で演算される。ステップ713において、モントゴメリー二乗演算が行われ、演算結果がコプロセッサレジスタ115に格納される。即ち、MontMult(A,A,P)=A*A*2-p mod Pが格納される。さらに、ビットPiが1である場合、ステップ715でモンゴメリー乗算が行われる。即ちMontMult(A,B,P)=A*B*2-p mod Pが行われる。 最後に、ステップ716でカウンタiがデクリメントされる。
【０１１７】
モンゴメリー乗算コプロセッサ123がステップ713および715で用いられるので、要素2-p mod Pが各々の乗算または二乗演算の後で導かれる。しかしながら、Xを、ステップ711において生成された初期ランダムビットXと称する場合、XはX=Y*2p mod Pと考えられる。ここで、Yは他の[p-ビット]の整数である。今、MontMult(Y,Y,P)=Y*Y*2p mod Pであり、モンゴメリー乗算の後、要素2p mod Pは安定している。結果として、累乗結果はXD mod PでなくXD*2p mod P.である。しかしながら、XD mod Pはステップ721において容易に回復されることができる。ここで、前のステップの結果はモンゴメリー乗算コプロセッサを使用した1の乗算とされる。即ち、MontMult(A,1,P)=YD*2p*1*2-p mod P = YD mod Pである。ステップ721の後、コプロセッサレジスタA 115がデータ1を格納するなら、ミラーラビンテストはステップ741で「成功」を出力する。そうでない場合には、すでに説明されるように、コプロセッサレジスタA 115に格納されるデータが二乗され、-1と比較される。
【０１１８】
モントゴメリー二乗演算はステップ733でj回繰り返される。一つのモンゴメリー乗算の後、レジスタAはY2D*2p mod Pを格納しており、再び、要素2p mod Pがモンゴメリー乗算の後に安定する、即ち変わらないことが分かる。しかしながら、モントゴメリー二乗演算の結果は-1と比較されるから、要因2pはステップ733における操作MontMult(A,1,P)=Y2D mod Pで取り除かれなければならなず、その結果データはコプロセッサレジスタB 116に格納される。-1=P-1mod Pに着目すると、ステップ731でコプロセッサレジスタBに格納されたデータはP-1と比較される。それが一致であれば、Pはたぶん素数であるから、ミラーラビンテストはステップ742で「成功」を返す。レジスタBのデータがP-1とは異なる場合、上記した手順が全体でj回繰り返される。j回繰り返された後なら、レジスタBの値は決してP-1には一致せず、Pは合成数だからミラー-ラビンテストはステップ743で「失敗」を出力する。
【０１１９】
《拡張》
本発明は、上記の実施の形態２で説明した内容に限定されない。例えば、図8の携帯機器は携帯電話、PDA、および公開鍵暗号を使用し且つコンピュータリソースとメモリリソースが限られたその他種々の電子デバイスであってよい。特に、携帯機器はモンゴメリー乗算コプロセッサを備えている必要はない。種類の異なるコプロセッサであってもよい。例えば古典的な剰余乗算コプロセッサであってもよいし、コプロセッサを用いずにソフトウェアによりCPUが実現する剰余乗算処理であてもよい。
【０１２０】
小さい素数の差を格納する代わりに、小さい素数を再構成するためには適切な他のいかなる方法も用いることができる。フェルマーテストにおける再符号化はNAF法、ウインドウ法、またはスライディングウインドウ法のように、異なる再符号化法であってもよい。
【０１２１】
実施の形態2がRSA鍵の生成に着目しているが、本発明がRSAに限定されず、DSAまたはDiffie-Hellmanのような他の公開鍵暗号方式でも、効率的に素数を生成するための上述の発明の効果を得ることができる。加えて、本発明は、素数判定テストの構成や種類に限定されない。たとえば、フェルマーテストの代わりにミラーラビンテストが使用されてもよいし、フロベーニウス（Frobenius）、Solovay-StrassenまたはAKSテスト等のその他のテストを採用してもよい。また本発明は特定のRSAパラメータに限られていない。例えば、DP、DQおよびQinvのようなCRTパラメータを省略することが可能であり、また、Dを省略することも可能であり、また、強い素数（strong primes）をPおよびQの追加的状態で使用することも可能である。
【０１２２】
実施の形態1で説明した図１の暗号化ユニットはソフトウェア的に実現されることも可能であり、また、図８の構成で実現される機能をハードウェアロジックで構成することも可能である。
【図面の簡単な説明】
【０１２３】
【図１】図１はＩＣカードのブロックダイヤグラムである。
【図２】図２はＲＳＡ対応のＩＣカードの典型的な動作工程を例示するタイミングチャートである。
【図３】図３は素数生成ユニットの具体例を示すブロックダイヤグラムである。
【図４】図４は素数生成制御ユニットの詳細を例示する説明図である。
【図５】図５はフェルマーテスト制御ユニットの機能を示す説明図である。
【図６】図６はミラーラビンユニットの機能を示す説明である。
【図７】図7はビットアレイのアップデータ機能を示す説明図である。
【図８】図８は携帯式電子装置（携帯機器）のブロックダイヤグラムである。
【図９】図９はＲＳＡ鍵ペア（keypair）の生成機能を示す説明図である。
【図１０】図１０は素数生成機能についての説明図である。
【図１１】図１１はビットアレイフィルの操作手順の詳細を例示する説明図である。
【図１２】図１２はモンゴメリー定数の演算機能を示す説明図である。
【図１３】図１３はフェルマーテストの機能を示す説明図である。
【図１４】図１４はミラーラビンテストの機能を示す説明図である。
【符号の説明】
【０１２４】
901 ＩＣカード
931 入出力インタフェース
912 鍵生成ユニット
911 暗号化ユニット
922 秘密鍵
924 デジタル証明書
921 メモリ
941 ネットワーク
904 ＡＴＭ
905 カードリーダ
902 ホストシステム（銀行ホスト）
903 ホストシステム（カード発行元ホスト）
923 公開鍵
914 素数生成ユニット
1111 フェルマーテストユニット
1131 ビット配列ユニット
1161 小さい素数生成ユニット
1102 素数生成制御ユニット
1123 素数候補P
1121 レジスタA
1122 レジスタＢ
1113 剰余乗算ユニット
1102 フェルマーテスト制御ユニット
1113 ビット配列ユニット
1141 ビットアレイ
1132 ビットアレイフィルユニット
1163 小さい素数テーブル
1162 ミラーラビンユニット
1171 メモリレジスタ
101 携帯式電子装置（携帯機器）
131 入出力インタフェース
141 ネットワーク
151 ATM
153 コンピュータ
154 携帯機器
111 メモリ
132,133入出力インタフェース
121 データ処理部
122 ＣＰＵ
123 モンゴメリー乗算コプロセッサ
124 RNG
【特許請求の範囲】
【請求項１】
整数の素数を判定するデータ処理システムであって、
前記整数の新たな表現を生成する再符号化ユニット、
複数の剰余演算操作を行うための剰余演算操作ユニット、
ループ制御ユニット、及び
入力整数の合成数又は素数を判定する判定ユニットを有し、
前記再符号化ユニットは、入力整数の複数のビットをスキャンし、前記スキャンされたビットにしたがって前記剰余演算操作ユニットによって演算される剰余演算操作を選択する、データ処理システム。
【請求項２】
前記剰余演算操作ユニットは剰余乗算ユニットを含む、請求１記載のデータ処理システム。
【請求項３】
前記剰余演算操作ユニットはモンゴメリー乗算ユニットである、請求項２記載のデータ処理システム。
【請求項４】
前記剰余演算操作ユニットは古典的な乗算ユニットである、請求項２記載のデータ処理システム。
【請求項５】
前記再符号化ユニットは、２ｗ（Ｗは正の整数）の表現形態に整数を再符号化する、請求項２記載のデータ処理システム。
【請求項６】
前記剰余演算操作ユニットは更に、左シフト回路、減算回路、右シフト回路、及び加算回路を有する、請求項２記載のデータ処理処システム。
【請求項７】
前記再符号化ユニットは、ＮＡＦの表現形態に整数を再符号化する、請求項６記載のデータ処理システム。
【請求項８】
前記再符号化ユニットは、ＦＡＮの表現形態に整数を再符号化する、請求項６記載のデータ処理システム。
【請求項９】
整数の素数を判定するためのデータ処理方法であって、コンピュータ装置を用いて実行される第１乃至第４処理を含み、
第１処理は、前記整数の複数ビットをスキャンする処理であり、
前記第２処理は、前記スキャンされたビットに従って少なくとも一つの剰余演算処理を選択する処理であり、
前記第３処理は選択された剰余演算処理を実行する処理であり、
前記第４処理は前記剰余演算処理の結果に基づいて前記整数の素数を決める処理である、データ処理方法。
【請求項１０】
前記スキャンされるビット数は予め決定され、
前記第３処理は、前記整数の全ビットに対して、剰余二乗演算と剰余乗算とを繰り返し行う処理を含む、請求項９記載のデータ処理方法。
【請求項１１】
前記剰余乗算の一つの乗算は２の累乗である、請求項１０記載のデータ処理方法。
【請求項１２】
前記スキャンされるビットは符号付きで表現され、
前記第３処理は、前記整数の前記符号付き表現の全ての桁に対して、前記整数の符号付き表現の桁をスキャンし、剰余二乗演算を行ない、１の桁の場合には剰余左シフト、−１の桁の場合には剰余右シフトする処理を繰り返し行なう処理を含む、請求項９記載のデータ処理方法。
【請求項１３】
前記整数の少なくとも３ビットイがスキャンされ、
前記整数の全ビットに対して、前記第１処理、前記第２処理及び前記第３処理が繰り返される、請求項９記載のデータ処理方法。
【請求項１４】
前記第３処理は、
前記スキャンされたビットの最初の2ビットが０１又は１０のとき剰余二乗演算を1回行い、
前記スキャンされたビットが０１１のとき剰余二乗演算と剰余左シフトをそれぞれ1回行い、
前記スキャンされたビットが０１０のとき剰余二乗演算を２回行い且つ剰余左シフトを1回行い、
前記スキャンされたビットが１００のとき剰余二乗演算と剰余右シフトをそれぞれ1回行い、
前記スキャンされたビットが１０１のとき剰余二乗演算を２回行い且つ剰余右シフトを1回行う、処理を含む、請求項１３記載のデータ処理方法。
【請求項１５】
複数の小さい素数による整数の割算の剰余を計算するデータ処理システムであって、
前記小さい素数を生成する計算ユニットと、
前記整数と前記生成された小さい素数とから前記剰余を計算する剰余演算ユニットとを含み、
前記小さい素数は前記計算ユニットによって再構成される、データ処理システム。
【請求項１６】
前記剰余演算ユニットは古典的な剰余乗算ユニットである、請求項１５記載のデータ処理システム。
【請求項１７】
前記剰余演算ユニットはモンゴメリー乗算ユニットである、請求項１５記載のデータ処理システム。
【請求項１８】
前記小さい素数モンゴメリー定数を演算するためのモンゴメリ定数演算ユニットを更に含む請求項１７記載のデータ処理システム。
【請求項１９】
前記計算ユニットは、連続する素数の間の差のテーブルを格納するためのメモリユニットと、
小さい素数を格納するためのメモリユニットと、
追加ユニットとを有し、
前記追加ユニットは前記小さい素数と前記差のテーブルの要素とを加算する演算を行う、請求項１5記載のデータ処理システム。
【請求項２０】
前記計算ユニットは、
小整数を格納するメモリユニットと、
素数性のテストユニットと、
更新ユニットとを有し、
前記小整数は前記素数性テストユニットイによって素数性がテストされ前記、小整数は当該小整数が素数でなない場合に前記更新ユニットによって更新される、請求項１５記載のデータ処理システム。
【請求項２１】
前記素数性テストユニットはミラーラビンテストユニットを含む、請求項２０記載のデータ処理システム。
【請求項２２】
前記素数性テストユニットはフェルマーテストニットを含む、請求項２０記載のデータ処理システム。
【請求項２３】
複数の小さい素数による整数の割算の剰余を計算するデータ処理方法であって、
一つの小さい素数を再構成する処理と、
前記再構成された小さい素数によって前記整数の割算の剰余を計算する処理とを含む、データ処理方法。
【請求項２４】
モンゴメリー定数を算出するステップをさらに含む、請求項２３記載のデータ処理方法。
【請求項２５】
少なくとも一つの小さい素数を再構成するステップと剰余を算出するステップとが並列的に実行される。請求項２３記載のデータ処理方法。
【請求項２６】
少なくとも一つの小さい素数を再構成するステップ、剰余を算出するステップ及びモンゴメリ定数を算出するステップが並列的に実行される請求項２４記載のデータ処理方法。
【請求項２７】
少なくとも一つの小さい素数を再構成するステップは、
連続する小さい素数間の差のテーブルを格納する処理と、
小さい素数を格納する処理と、
前記小さい素数の追加と前記差のテーブルの要素とを算出する処理と、を含む請求項２３記載のデータ処理方法。
【請求項２８】
少なくとも一つの小さい素数を再構成するステップは、
小整数を格納する処理と、
前記小整数の素数性を判定する処理と、
前記小整数が素数でない場合に当該小整数を更新する処理と、を含む請求項２３記載のデータ処理方法。
【請求項２９】
前記小整数の素数性を判定する処理はミラーラビンテストを行なう処理を含む請求項２８記載のデータ処理方法。
【請求項３０】
前記小整数の素数性を判定する処理はフェルマーテストを行なう処理を含む請求項２８記載のデータ処理方法。
【請求項１】
整数の素数を判定するデータ処理システムであって、
前記整数の新たな表現を生成する再符号化ユニット、
複数の剰余演算操作を行うための剰余演算操作ユニット、
ループ制御ユニット、及び
入力整数の合成数又は素数を判定する判定ユニットを有し、
前記再符号化ユニットは、入力整数の複数のビットをスキャンし、前記スキャンされたビットにしたがって前記剰余演算操作ユニットによって演算される剰余演算操作を選択する、データ処理システム。
【請求項２】
前記剰余演算操作ユニットは剰余乗算ユニットを含む、請求１記載のデータ処理システム。
【請求項３】
前記剰余演算操作ユニットはモンゴメリー乗算ユニットである、請求項２記載のデータ処理システム。
【請求項４】
前記剰余演算操作ユニットは古典的な乗算ユニットである、請求項２記載のデータ処理システム。
【請求項５】
前記再符号化ユニットは、２ｗ（Ｗは正の整数）の表現形態に整数を再符号化する、請求項２記載のデータ処理システム。
【請求項６】
前記剰余演算操作ユニットは更に、左シフト回路、減算回路、右シフト回路、及び加算回路を有する、請求項２記載のデータ処理処システム。
【請求項７】
前記再符号化ユニットは、ＮＡＦの表現形態に整数を再符号化する、請求項６記載のデータ処理システム。
【請求項８】
前記再符号化ユニットは、ＦＡＮの表現形態に整数を再符号化する、請求項６記載のデータ処理システム。
【請求項９】
整数の素数を判定するためのデータ処理方法であって、コンピュータ装置を用いて実行される第１乃至第４処理を含み、
第１処理は、前記整数の複数ビットをスキャンする処理であり、
前記第２処理は、前記スキャンされたビットに従って少なくとも一つの剰余演算処理を選択する処理であり、
前記第３処理は選択された剰余演算処理を実行する処理であり、
前記第４処理は前記剰余演算処理の結果に基づいて前記整数の素数を決める処理である、データ処理方法。
【請求項１０】
前記スキャンされるビット数は予め決定され、
前記第３処理は、前記整数の全ビットに対して、剰余二乗演算と剰余乗算とを繰り返し行う処理を含む、請求項９記載のデータ処理方法。
【請求項１１】
前記剰余乗算の一つの乗算は２の累乗である、請求項１０記載のデータ処理方法。
【請求項１２】
前記スキャンされるビットは符号付きで表現され、
前記第３処理は、前記整数の前記符号付き表現の全ての桁に対して、前記整数の符号付き表現の桁をスキャンし、剰余二乗演算を行ない、１の桁の場合には剰余左シフト、−１の桁の場合には剰余右シフトする処理を繰り返し行なう処理を含む、請求項９記載のデータ処理方法。
【請求項１３】
前記整数の少なくとも３ビットイがスキャンされ、
前記整数の全ビットに対して、前記第１処理、前記第２処理及び前記第３処理が繰り返される、請求項９記載のデータ処理方法。
【請求項１４】
前記第３処理は、
前記スキャンされたビットの最初の2ビットが０１又は１０のとき剰余二乗演算を1回行い、
前記スキャンされたビットが０１１のとき剰余二乗演算と剰余左シフトをそれぞれ1回行い、
前記スキャンされたビットが０１０のとき剰余二乗演算を２回行い且つ剰余左シフトを1回行い、
前記スキャンされたビットが１００のとき剰余二乗演算と剰余右シフトをそれぞれ1回行い、
前記スキャンされたビットが１０１のとき剰余二乗演算を２回行い且つ剰余右シフトを1回行う、処理を含む、請求項１３記載のデータ処理方法。
【請求項１５】
複数の小さい素数による整数の割算の剰余を計算するデータ処理システムであって、
前記小さい素数を生成する計算ユニットと、
前記整数と前記生成された小さい素数とから前記剰余を計算する剰余演算ユニットとを含み、
前記小さい素数は前記計算ユニットによって再構成される、データ処理システム。
【請求項１６】
前記剰余演算ユニットは古典的な剰余乗算ユニットである、請求項１５記載のデータ処理システム。
【請求項１７】
前記剰余演算ユニットはモンゴメリー乗算ユニットである、請求項１５記載のデータ処理システム。
【請求項１８】
前記小さい素数モンゴメリー定数を演算するためのモンゴメリ定数演算ユニットを更に含む請求項１７記載のデータ処理システム。
【請求項１９】
前記計算ユニットは、連続する素数の間の差のテーブルを格納するためのメモリユニットと、
小さい素数を格納するためのメモリユニットと、
追加ユニットとを有し、
前記追加ユニットは前記小さい素数と前記差のテーブルの要素とを加算する演算を行う、請求項１5記載のデータ処理システム。
【請求項２０】
前記計算ユニットは、
小整数を格納するメモリユニットと、
素数性のテストユニットと、
更新ユニットとを有し、
前記小整数は前記素数性テストユニットイによって素数性がテストされ前記、小整数は当該小整数が素数でなない場合に前記更新ユニットによって更新される、請求項１５記載のデータ処理システム。
【請求項２１】
前記素数性テストユニットはミラーラビンテストユニットを含む、請求項２０記載のデータ処理システム。
【請求項２２】
前記素数性テストユニットはフェルマーテストニットを含む、請求項２０記載のデータ処理システム。
【請求項２３】
複数の小さい素数による整数の割算の剰余を計算するデータ処理方法であって、
一つの小さい素数を再構成する処理と、
前記再構成された小さい素数によって前記整数の割算の剰余を計算する処理とを含む、データ処理方法。
【請求項２４】
モンゴメリー定数を算出するステップをさらに含む、請求項２３記載のデータ処理方法。
【請求項２５】
少なくとも一つの小さい素数を再構成するステップと剰余を算出するステップとが並列的に実行される。請求項２３記載のデータ処理方法。
【請求項２６】
少なくとも一つの小さい素数を再構成するステップ、剰余を算出するステップ及びモンゴメリ定数を算出するステップが並列的に実行される請求項２４記載のデータ処理方法。
【請求項２７】
少なくとも一つの小さい素数を再構成するステップは、
連続する小さい素数間の差のテーブルを格納する処理と、
小さい素数を格納する処理と、
前記小さい素数の追加と前記差のテーブルの要素とを算出する処理と、を含む請求項２３記載のデータ処理方法。
【請求項２８】
少なくとも一つの小さい素数を再構成するステップは、
小整数を格納する処理と、
前記小整数の素数性を判定する処理と、
前記小整数が素数でない場合に当該小整数を更新する処理と、を含む請求項２３記載のデータ処理方法。
【請求項２９】
前記小整数の素数性を判定する処理はミラーラビンテストを行なう処理を含む請求項２８記載のデータ処理方法。
【請求項３０】
前記小整数の素数性を判定する処理はフェルマーテストを行なう処理を含む請求項２８記載のデータ処理方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【公開番号】特開２００９−２２９６１５（Ｐ２００９−２２９６１５Ａ）
【公開日】平成２１年１０月８日（２００９．１０．８）
【国際特許分類】
【出願番号】特願２００８−７２７２３（Ｐ２００８−７２７２３）
【出願日】平成２０年３月２１日（２００８．３．２１）
【出願人】（５０３１２１１０３）株式会社ルネサステクノロジ (4,790)
【Ｆターム（参考）】
【公開日】平成２１年１０月８日（２００９．１０．８）
【国際特許分類】
【出願日】平成２０年３月２１日（２００８．３．２１）
【出願人】（５０３１２１１０３）株式会社ルネサステクノロジ (4,790)
【Ｆターム（参考）】
[ Back to top ]