データ処理装置
【課題】メモリ容量を消費せずに高速にフェルマーテストによって素数判定を行うことができるデータ処理装置を提供する。
【解決手段】2を元としたフェルマーテストをモンゴメリ剰余乗算コプロで実行するための高速耐タンパ手法であって、指数をmビットごとにまとめて乗算するm-ary法を実施する際に、剰余乗算に補正値を含めることで、モンゴメリ剰余乗算コプロを用いた場合に通常必要となる、事前計算や事前計算した値を格納するワークエリアの確保を不要とした。暗号鍵を生成するための素数生成を高速化する場合、大量のメモリや事前計算が必要になることや、消費電流などのリーク情報から内部で生成される暗号鍵が推定されることを解決することができる。
【解決手段】2を元としたフェルマーテストをモンゴメリ剰余乗算コプロで実行するための高速耐タンパ手法であって、指数をmビットごとにまとめて乗算するm-ary法を実施する際に、剰余乗算に補正値を含めることで、モンゴメリ剰余乗算コプロを用いた場合に通常必要となる、事前計算や事前計算した値を格納するワークエリアの確保を不要とした。暗号鍵を生成するための素数生成を高速化する場合、大量のメモリや事前計算が必要になることや、消費電流などのリーク情報から内部で生成される暗号鍵が推定されることを解決することができる。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、フェルマーテストを実行するデータ処理装置に関し、例えば機密性の高いICカードなどの耐タンパ装置向けの素数生成に関するものである。
【背景技術】
【0002】
ICカードは、主に、勝手に書き換えられない情報の保持や秘密情報である暗号鍵を使ったデータの暗号化や暗号文の復号化を行うために使われる装置である。
【0003】
ICカードは、電源を持っていないため、リーダライタに差し込まれると、電源の供給を受け、動作可能となる。動作可能になると、リーダライタからコマンドを受けて、コマンドに従い、データの転送を行う。
【0004】
ICカードチップは、プログラムや重要な情報がICカード用チップの中に密閉されており、外部からそれらの情報に直接アクセスすることはできない。外部との通信は、I/Oピンのみを介して、完全にICカードチップの制御下で行われ、通常情報は暗号化した状態で送受信され、情報の秘匿性を実現している。暗号通信を行うためには、通信する相手と暗号鍵の共有を行う必要がある。事前に鍵を通信相手と共有しておく方法もあるが、一度鍵が判明してしまうと、暗号化した通信内容が復号化されてしまう。そこで、通信に用いる暗号鍵をランダムに生成し、相手に鍵を送信し、その鍵を用いて通信するという方法がある。
【0005】
相手に鍵を送る際に、鍵を平文のまま送ってしまうと、次にその鍵を用いた暗号通信は簡単に解読されてしまう。そこで、公開鍵暗号技術を用いる。公開鍵暗号とは、暗号化に用いる鍵と、復号化に用いる鍵が異なり、暗号化に用いる鍵から複号に用いる鍵を求めることが、計算量的に困難な暗号方式である。
【0006】
公開鍵暗号方式を用いた鍵交換では、相手に自分の公開鍵を送り、相手側は通信の暗号化に用いる鍵を乱数などから生成し、送られてきた公開鍵で暗号化した後、暗号化された鍵を返信する。返信されてきた暗号化鍵を、さきほど相手に送った公開鍵に対応する秘密鍵で復号化し、次の通信に用いる。
【0007】
公開鍵暗号方式として最も広く用いられている暗号として、RSA暗号方式がある。この暗号方式は、2つの大きな素数の積からなる合成数が、容易に因数分解できないことを利用した暗号である。因数分解自体は、試行割り算法や数体篩などによって、アルゴリズム的には求めることは可能であるが、数が大きくなると、因数を求めることが時間的に困難となる。現在、1024ビットから2048ビット長の鍵が用いられている。鍵の生成はICカードの外部の計算機で行い、生成された鍵をICカードに書き込むという方法で公開鍵暗号方式の鍵をICカードに格納してきた。
【0008】
この方法では、原理的にICカードの外側に公開鍵暗号の秘密鍵が存在してしまうため、その秘密鍵が適切に管理できないと、セキュリティを確保できないという問題があった。そこで、ICカード内部で公開鍵暗号方式の秘密鍵と公開鍵のペアを生成することが行われるようになった。これにより、セキュリティは向上するが、RSA暗号の鍵生成はICカードで行うには時間の掛かる処理であり、高速化が必要となった。RSA暗号鍵の生成でもっとも時間の掛かる処理は、2つの大きな素数を生成する処理である。素数生成は、奇数乱数を生成し、次に生成された乱数が素数であるかを判定し、素数で無かった場合にはまた新たに素数を生成して素数判定を行う処理を繰り返すことで実現されている。
【0009】
素数判定には、いろいろな手法が用いられているが、2を元としたフェルマーテストにより、最初の素数判定を行い、それにパスした乱数をさらに厳密な素数判定処理に掛ける方式が高速化に向いている。これは、2倍算がシフトで行えるためである。
【0010】
しかし、指数部が1が0かにより、剰余乗算の有無などの処理の違いを消費電力の違いなどから推定し、秘密情報である素数が推定される可能性があり、セキュリティ面で不安があった。
【0011】
高速、かつセキュアにフェルマーテストを行う方法としては、一時に指数をmビットまとめて処理する、非特許文献1に記されているm−ary法(もしくはWindow法とも呼ばれる)がある。m−ary法では、指数部をm[bit]ごとに区切って,区間ごとにm回の剰余二乗算と1回の剰余乗算を行う。指数のビット数がn[bit]の場合,n回の剰余二乗算とn/m回の剰余乗算を行う必要がある。xy mod Nを計算する場合のm−ary法の手順を示す。ここで、e[i]はyをmビット毎に区切った値で、JをJ≧n/mとなる最小の整数としたときに、下記(式1)
y=2(J−1)m・e[J−1]+2(J−2)m・e[J−2]+…+2m・e[1]+e[0] (式1)
を満たす。m−ary法の手順は例えば、
result:= 1;
for i:=J−1 downTo 0 do
for j:=1 to m do
result:=result2 mod N
end for
result:=result * x^(e[i]) mod N
end for
return result
とされる。
【0012】
この方式は、ビットパタンによる処理内容に違いが発生せず、mの値を増やすことで、処理に必要な剰余乗算の回数がmに反比例して減少する。しかし、x^1〜x^(2m−1)までの値を事前に計算しておく必要があるため、mを増加させるとワークエリアが2mに比例して増加するという問題があった。これは、特にRAMのサイズに制約のあるICカードでは大きなネックとなる。
【0013】
x^(e[i])の値を必要になった際に動的に計算することも考えられるが、特にICカードでよく用いられるモンゴメリ剰余乗算アルゴリズム(非特許文献2)を用いたコプロセッサにおいては、通常の数値表現から2^n mod Nを乗じたモンゴメリ表現に変換する必要があるため、動的に剰余乗算の演算数を計算することは、速度低下をもたらすという問題があった。
【0014】
【非特許文献1】Alfred J. Menezes,Paul C. van Oorschot and Scott A. Vanstone,“HANDBOOK of APPLIED CRYPTOGRAPHY”,CRC Press,pp.615−616、ISBN 0−8493−8523−7,(1997)
【非特許文献2】Darrel Hankerson,Alfred Menezes and Scott Vanstone,“Guide to Elliptic Curve Cryptography”,Springer,pp.38,ISBN 0−387−95273−X,(2004)
【発明の開示】
【発明が解決しようとする課題】
【0015】
RSA暗号の鍵を高速に生成するには、素数を高速に生成することが必要であるが、従来手法で素数判定を高速に行う必要場合、速度と記憶容量はトレードオフの関係にあり、特にメモリ容量がICカードでは高速化が困難であった。
【0016】
本発明の目的は、メモリ容量を消費せずに高速にフェルマーテストによって素数判定を行うことができるデータ処理装置を提供することにある。
【0017】
本発明の前記並びにその他の目的と新規な特徴は本明細書の記述及び添付図面から明らかになるであろう。
【課題を解決するための手段】
【0018】
本願において開示される発明のうち代表的なものの概要を簡単に説明すれば下記の通りである。
【0019】
すなわち、本発明は、コプロセッサのビット長をnとしたときに、mをm≦log2(n)を満たす最大の整数とし、mビットごとに指数を処理することで、m−ary法での剰余乗算の回数を減らし、高速化を図る。また、m−ary法では、事前にx1からx2^m−1までの2m−1種類の値を事前計算し、メモリに格納する必要があるが、本発明ではx=2であることを利用し、処理中に剰余乗算に用いる演算数を動的に生成し、事前計算や事前計算した値を保存する記憶容量を用意しなくともよくすることで、必要な記憶容量を増やすことなく高速化を実現しようとするものである。尚、本明細書において記号^はべき乗演算を意味し、記号・は乗算演算を意味する。
【0020】
剰余乗算をモンゴメリコプロセッサで行う場合、2のベキ数にR(=2n mod N)を剰余乗算した値を用いる必要がある。Rも2のベキ数であるが、法Nよりも大きな値であるので、複雑なビットパタンとなり、事前計算を行うか、剰余乗算の都度、R2 mod Nをさらに乗じる必要がある。ここで、e[i]は(N−1)をmビット毎に区切った値で、JをJ≧n/mとなる最小の整数としたときに式(式2)
N−1=2(J−1)m・e[J−1]+…+2m・e[1]+e[0] (式2)
を満たすものとする。
【0021】
モンゴメリ剰余乗算コプロセッサを用いて、剰余乗算ごとにR2 mod Nを乗じる方法により2N−1 mod Nを計算する処理アルゴリズムは、
result:=R mod N
for i:=J−1 downTo 0 do
for j:=1 to m do
result:=result2 ・R−1mod N
end for
result:=result・2e[i]・R−1 mod N
result:=result・R2・R−1 mod N
end for
result:=result・1・R−1 mod N
return result
である。
【0022】
R2 mod Nを乗じる方式でも、必要なメモリ容量を増やすことなく、乗算回数は2・n/m回に削減することができるが、m−ary法でmビットごとに指数を扱った場合のn/m回と比べると、剰余乗算の回数が倍となる。
【0023】
この問題を解決するために、剰余乗算の演算数と被演算数それぞれにRが乗じられているのを、片方の被演算数のみにR2を乗じる方式を考える。こうすることで、乗じる値がハミングウエイト1となり、事前計算が不要となる。ただし、そのままの値を乗じると、剰余乗算後の結果にはRが乗じられているのみの形式になる。ベキ乗剰余の剰余演算の前には、剰余二乗算がm回行われることを利用し、剰余二乗算の結果、R2が乗じられる形式になるように、剰余乗算の際に補正値を乗じる。
【0024】
剰余乗算する際に、被演算数にR2=22nが乗じられるようにするには、剰余乗算後の被演算数には2nが乗じられているので、m回の剰余自乗算後に2nとなるような値を乗じればよい。すでに乗じられている2nと、追加で乗じられる2nとをあわせて、22nが常時乗じられる。したがって、演算数に次の式(3)
a^(2m)=2n (式3)
を満たす補正値aを乗ずればよい。
【0025】
これは、簡単に解くことができて、
a=2^(n/(2m)) (式4)
でaは与えられる。nが2のベキ数の場合は、mの定義より2m=nであるので、直ちに
a=2 (式5)
が求まる。
【0026】
一方、nが2のベキ数ではない場合、
a=2・2^(n・(2m)−1) (式6)
となり、2(n/(2^m)−1)は整数ではないため、そのまま補正値に用いることはできない。そこで、補正をm回の剰余自乗算の前に行う部分a’と、m回の剰余自乗算の後に行う部分bの2つに分ける。ここでは、a’=2とする。すなわち、剰余自乗算前に2で補正を行い、剰余自乗算後の補正値として(式7)
b=(2^(n/(2m)−1))^(2m) (式7)
を満たすbを考える。
【0027】
指数法則により、bは、
b=2^(n−2m) (式8)
となる。したがって、nが2のベキ数でない場合の補正値 a’・b は、
a’・b=2・2^(n−2m)=2^(1+n−2m) (式9)
となる。nが2のベキ数の場合は、n−2m=0であるので、(式9)は(式5)と等しくなる。また、(式7)はb=1となる。
【0028】
N−1をmビット毎に区切った剰余乗算では、(式9)の補正値と指数をmビット毎に区切った値を指数とした2のべき数である2^(e[i])の積である
2^(e[i]+1+n−2m) (式10)
を乗じることになる。e[i]はmビットの値なので、最大値は2m−1となる。この値を(式10)に代入すると、2nとなる。これは、n+1ビット長の値であり、コプロのビット長nを超えてしまう。こうしたビット溢れが生ずるのは、e[i]が最大値である2m−1となる場合のみで、それ以外の場合は、(式10)の値は2n未満となり、nビット以下の値であるので、nビット長のコプロセッサで計算ができる。
【0029】
したがって、e[i]の値が2m−1の場合は、演算数としてR mod Nを用い、e[i]の値が2m−1未満の場合は、演算数として(式10)の2^(e[i]+1+n−2m)を用いる。
【0030】
また、演算の最初のステップでは、あらかじめ被演算数にはR2 mod Nで初期化しておくので、補正値のbの値は不要である。したがって、指数の最上位を処理する最初のステップでは、e[i]+1の値が2nと等しいか否かを判定し、等しい場合は、演算数としてR mod Nを用い、2n未満の場合は、2^(e[i]+1)を用いる。nが2のベキ数でない場合は、e[i]+1は常に2n未満となるので、nが2のベキ数でないことが予めわかっている場合において、最初のe[i]+1が2nと等しいか否かを検査はしなくてもよい。
【0031】
モンゴメリ剰余乗算で計算を行う場合には、最終結果からRを取り除く必要があり、通常、1とのモンゴメリ剰余乗算を行うことで、R−1を乗じ、通常の表現に戻す。
【0032】
本発明では、結果にR2が乗じられているので、最後の2回の剰余乗算で補正を行う。まず、最後から2番目のe[1]を処理する際には、次の剰余乗算の際にR2が乗じられるようにするための補正は不要で、Rのみが残るように、a’・bのうちのbのみの補正値を乗ずればよい。したがって、演算数として、
2^(e[1]+n−2m) (式11)
を乗じる。e[1]+n−2^mの値は、必ず2n未満となるため、2nとの比較は必要ない。この値を乗じた後、m回の自乗演算を行うと、被演算数にはRが乗じられている状態になるので、最後の最下位の指数e[0]を処理する際に、
2^(e[0]) (式12)
を乗じることで、最終結果はモンゴメリ形式ではなく、通常の数値表現になる。以上の手順をアルゴリズム表現すると、以下の如く、
result:=R2 mod N
if e[J−1]+1<2n then
result:=result・2^(e[i]+1)・R−1mod N
else
result:=result・(R mod N)・R−1mod N
end if
for i:=J−2 downTo 2 do
for j:=1 to m do
result:=result2 ・R−1mod N
end for
if e[i]+1+n−2m<2n then
result:=result・2^(e[i]+1+n−2m)・R−1mod N
else
result:=result・(R mod N)・R−1mod N
end if
end for
for j:=1 to m do
result:=result2 ・R−1mod N
end for
result:=result・2^(e[1]+n−2m)・R−1 mod N
for j:=1 to m do
result:=result2 ・R−1mod N
end for
result:=result・2^(e[0])・R−1 mod N
return result
と、表すことができる。
【0033】
また、(式11)で示される演算数はハミングウエイトが1であり、モンゴメリ剰余乗算コプロでは通常下位側から演算が進められるため、演算数のビットが0となっている部分を処理している間は電流地が小さく、ビットが1となっている部分で大きく消費電流が増加する可能性がある。その場合、消費電流を測定して指数の値をある程度推定することが可能となる。そうした問題を解決するために、演算がNを法とする剰余乗算であることと、剰余乗算の後に剰余二乗算が行われることを利用し、演算数には(式11)の値の代わりに、
N ± 2^(e[i]+1+n−2m) (式13)
を使用することができる。しかし、(式13)では加減算によるキャリーが発生し、キャリーの伝版によるディレイや、最上位ビットからのキャリーの発生による桁あふれが発生する可能性がある。そこで、
N xor 2^(e[i]+1+n−2m) (式14)
の形式にすることで、キャリーは発生しなくなる。(式14)はNの(e[i]+1+n−2m)ビット目のビットが1であるか0であるかにより、加減算のいずれかが行われることと等価で、Nの該当ビットが1であった場合は減算、Nの該当ビットが0であった場合は加算が行われる。排他的論理和(xor)演算ではキャリーの伝播が発生せず、キャリーの伝播に伴うディレイもない上、回路も小さくて済む。
【0034】
(式14)による変形を行うと、演算数のハミングウエイトはほぼビット長の半分となり、消費電流を用いたアタック手法に対して、耐タンパ性が強化される。(式14)の変形を導入した手順をアルゴリズム表現すると、
result:=R2 mod N
if e[J−1]+1<2n then
result:=result・(N xor 2^(e[J−1]+1))・R−1mod N
else
result:=result・(R mod N)・R−1mod N
end if
for i:=J−2 downTo 2 do
for j:=1 to m do
result:=result2 ・R−1mod N
end for
if e[i]+1+n−2m<2n then
result:=result・(N xor 2^(e[i]+1+n−2m))・R−1 mod N
else
result:=result・(R mod N)・R−1 mod N
end if
end for
for j:=1 to m do
result:=result2 ・R−1mod N
end for
result:=result・2^(e[1]+n−2m)・R−1 mod N
for j:=1 to m do
result:=result2 ・R−1mod N
end for
result:=result・2^(e[0])・R−1 mod N
return result
と、表すことができる。
【0035】
この手順に従い、モンゴメリ剰余乗算コプロを用いて2を元とするフェルマーテストを高速に実装することができる。
【0036】
同様の手法は、モンゴメリ剰余乗算方式ではない通常表現を用いる剰余乗算コプロセッサを用いる場合でも用いることができる。通常の表現を用いる剰余乗算コプロセッサでは、演算数には補正値がいらないので、次の(式15)
N xor 2^(e[i]) (式15)
の値を演算数に用いる。
【0037】
(式14)であらわされる剰余乗算の演算数の変形は、剰余乗算後に剰余二乗算により負の値の符号が正となることを前提としているので、最下位のmビット分、すなわちe[0]に対しては用いることができない。したがって、e[0]の場合は(式14)の変形は行わない。以上の手順をアルゴリズム表現すると、
result:=N xor 2^(e[J−1])
for i:=J−2 downTo 1 do
for j:=1 to m do
result:=result2 mod N
end for
result:=result・(N xor 2^(e[i])) mod N
end for
for j:=1 to m do
result:=result2 mod N
end for
result:=result・2^(e[0]) mod N
return result
と、表すことができる。
【0038】
以上の手順を用いれば、モンゴメリ型剰余乗算器あるいは剰余乗算器のいずれを用いた場合でも、メモリ容量を消費せずに高速にフェルマーテストを行って素数判定が可能になる。
【発明の効果】
【0039】
本願において開示される発明のうち代表的なものによって得られる効果を簡単に説明すれば下記のとおりである。
【0040】
すなわち、メモリ容量を消費せずに高速にフェルマーテストによって素数判定を行うことができるデータ処理装置を提供することができる。
【発明を実施するための最良の形態】
【0041】
1.実施の形態の概要
先ず、本願において開示される発明の代表的な実施の形態について概要を説明する。代表的な実施の形態についての概要説明で括弧を付して参照する図面中の参照符号はそれが付された構成要素の概念に含まれるものを例示するに過ぎない。
【0042】
〔1〕本発明に係るデータ処理装置(図1、図7、図9、図10、図11)は、モンゴメリ剰余乗算を行うモンゴメリ剰余乗算器を備えたコプロセッサと、プログラムを実行し前記コプロセッサを制御する中央処理装置とを有し、前記中央処理装置の制御によってデータ処理を行なうことにより、外部より与えられた素数候補Nに対して、2(N−1)mod Nを計算してフェルマーテストを実行する。前記データ処理は、
前記素数候補Nを記憶する処理と、
Nのビット長nを記憶する処理と、
log2(n)を超えない最大の整数mを計算して(図9のステップ7010)記憶する処理と、
前記素数候補Nから、N−1を計算し、JをJ≧n/mとなる最小の整数としたときに(図9のステップ7020)、(N−1)を最下位からmビットごとにJ個の区間に区切り、(N−1)=2(J−1)m・e[J−1]+2(J−2)m・e[J−2]+…+2m・e[1]+e[0]なる式を満たすように(N−1)を部分指数e[0],e[1],…,e[J−1]に分割する指数部切り出し処理と (図9のステップ7030)、
前記指数部切り出し処理により切り出されたmビットの値e[i]から2^(e[i]+1+n−2m)を生成する2のベキ乗生成処理と(図9のステップ7060の一部分)、
前記指数部切り出し処理で切り出された部分指数の最上位の値に1を加えたe[J−1]+1が2nと等しい場合は(図9のステップ7050)、R mod N=2n mod Nの演算結果と、R2 mod N=22n mod Nの演算結果との前記素数候補Nを法とするモンゴメリ剰余乗算を行ってその演算結果を第1記憶領域に格納する第1処理と (図9のステップ7070)、
前記e[J−1]+1が2n未満の場合は、前記2のベキ乗生成手段により計算した2^(e[J−1]+1)と、前記R2modN=22n mod Nの演算結果との前記Nを法とするモンゴメリ剰余乗算を行ってその演算結果を前記第1の記憶領域に格納する第2処理と (図9のステップ7060)、
前記第1処理又は前記第2処理のいずれか一方の処理の後に内部の状態変数iをJ−2とする第3処理と(図9のステップ7080)、
前記第3処理の後に、前記素数候補Nを法とし、前記第1記憶領域に記憶された値同士のモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に書き戻す動作をm回繰り返す第4処理と(図10のステップ7090)、
前記第4処理の後に、前記指数部切り出し処理で切り出された部分指数e[i]が2m−1未満の場合は(図10のステップ7100)、前記2のベキ乗生成処理により生成された2^(e[i]+1+n−2m)と前記第1の記憶領域に格納された値との前記Nを法とするモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に格納する第5処理と(図10のステップ7110)、
前記第5処理の後に、前記内部状態変数iから1を引いた値を前記内部状態変数iに格納し(図10のステップ7130)、前記iの値が2以上の場合は前記第4処理に戻り、前記iの値が1以下になるまでそれを繰り返す第6処理と、
前記第6処理の後に、前記素数候補Nを法とし、前記第1記憶領域に記憶された値同士のモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に書き込む動作をm回繰り返す第7処理と(図11のステップ7150)、
前記第7処理の後、前記2のベキ乗生成処理により計算された2^(e[1]+n−2m)と、前記第1記憶領域に格納された値との前記素数候補Nを法とするモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に格納する第8処理と(図11のステップ7160)、
前記第8処理の後、前記モンゴメリ剰余乗算装置により、前記素数候補Nを法とし、前記第1記憶領域に格納された値同士のモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に格納する動作をm回繰り返す第9処理と(図11のステップ7170)、
前記第9処理の後、前記2のベキ乗生成処理により計算された2^(e[0])と、前記第1記憶領域に格納された値との前記素数候補Nを法とするモンゴメリ剰余乗算を行って(図11のステップ7180)、その演算結果をフェルマーテスト結果として出力する第10処理とを含む。
【0043】
〔2〕項1のデータ処理装置において、前記プログラムを格納したメモリを更に有し、1個の半導体基板に形成される。
【0044】
〔3〕別の観点によるデータ処理装置(図4、図7、図12、図13、図14)は、モンゴメリ剰余乗算を行うモンゴメリ剰余乗算器を備えたコプロセッサと、プログラムを実行し前記コプロセッサを制御する中央処理装置とを有し、前記中央処理装置の制御によってデータ処理を行なうことにより、外部より与えられた素数候補Nに対して、2(N−1)mod Nを計算してフェルマーテストを実行する。前記データ処理は、
前記素数候補Nを記憶する処理と、
Nのビット長nを記憶する処理と、
log2(n)を超えない最大の整数mを計算して(図12のステップ7010)記憶する処理と、
前記素数候補Nから、N−1を計算し、JをJ≧n/mとなる最小の整数としたときに(図12のステップ7020)、(N−1)を最下位からmビットごとにJ個の区間に区切り、(N−1)=2(J−1)m・e[J−1]+2(J−2)m・e[J−2]+…+2m・e[1]+e[0]なる式を満たすように(N−1)を部分指数e[0],e[1],…,e[J−1]に分割する指数部切り出し処理と(図12のステップ7030)、
前記指数部切り出し処理により切り出されたmビットの値e[i]から2^(e[i]+1+n−2m)
を生成する2のベキ乗生成処理と、
前記指数部切り出し処理により切り出された部分指数の最上位の値に1を加えたe[J−1]+1が2nと等しい場合は(図12のステップ7050)、R mod N=2n mod Nの演算結果と、R2 mod N=22n mod Nの演算結果との前記素数候補Nを法とするモンゴメリ剰余乗算を行って(図12のステップ7070)、その演算結果を第1記憶領域に格納する第1処理と、
前記e[J−1]+1が2n未満の場合は、前記2のベキ乗生成手段により計算した2^(e[J−1]+1)と前記素数候補Nとの排他的論理和(図4の3032)を取った値と、前記R2 mod N=22n mod Nの演算結果との前記Nを法とするモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に格納する第2処理と(図12のステップ8060)、
前記第1処理又は第2処理のいずれか一方の処理の後に内部の状態変数iをJ−2とする第3処理と (図12のステップ7080)、
前記第3処理の後に、前記素数候補Nを法とし、前記第1記憶領域に格納された値同士のモンゴメリ剰余乗算を行ってその4演算結果を前記第1記憶領域に格納する動作をm回繰り返す第4処理と(図12のステップ7090)、
前記第4処理の後に、前記指数部切り出し処理で切り出された部分指数e[i]が2m−1未満の場合は(図13のステップ7100)、前記2のベキ乗生成処理により生成された2^(e[i]+1+n−2m)と前記素数候補Nとの排他的論理和(図4の3032)が採られた値と、前記第1記憶領域に格納されている値との前記素数候補Nを法とするモンゴメリ剰余乗算を行って(図13のステップ8110)その演算結果を前記第1記憶領域に格納する第5処理と、
前記第4処理の後に、前記指数部切り出し処理で切り出された部分指数e[i]が2m−1と等しい場合は、前記R mod N=2n mod Nと、前記第1記憶領域に格納された値との前記素数候補Nを法とするモンゴメリ剰余乗算を行って(図13のステップ7120)その演算結果を前記第1記憶領域に格納する第6処理と、
前記第5処理又は第6処理のいずれか一方の処理の後に前記内部状態変数iから1を引いた値を前記内部状態変数iに格納し(図13のステップ7130)、前記iの値が2以上の場合は、前記第3処理に戻り(図13のステップ7140)、前記iの値が1以下になるまでそれを繰り返す第7処理と、
前記第7処理の後に前記素数候補Nを法とし、前記第1記憶領域に記憶された値同士のモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に格納する動作をm回繰り返す第8処理と(図14のステップ7150)、
前記第8処理の後、前記2のベキ乗生成処理で生成された2^(e[1]+n−2m)と、前記第1記憶領域に格納された値との前記素数候補Nを法とするモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に格納する第9処理と(図14のステップ7160)、
前記第9処理の後、前記素数候補Nを法とし、前記第1記憶領域に格納された値同士のモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に格納する動作をm回繰り返す第10処理と(図14のステップ7170)、
前記第10処理の後、前記2のベキ乗生成処理により生成された2^(e[0])と前記第1記憶領域に格納された値との前記Nを法とするモンゴメリ剰余乗算を行って(図14のステップ7180)、その演算結果をフェルマーテスト結果として出力する第11処理とを含む。
【0045】
〔4〕項3のデータ処理装置は、前記プログラムを格納したメモリを更に有し、1個の半導体基板に形成される。
【0046】
〔6〕別の観点によるデータ処理装置(図3、図7、図12、図13、図14)は、モンゴメリ剰余乗算を行うモンゴメリ剰余乗算器を備えたコプロセッサと、プログラムを実行し前記コプロセッサを制御する中央処理装置とを有し、前記中央処理装置の制御によってデータ処理を行なうことにより、外部より与えられた素数候補Nに対して、2(N−1)mod Nを計算してフェルマーテストを実行する。前記データ処理は、
前記素数候補Nを記憶する処理と、
Nのビット長nを記憶する処理と、
log2(n)を超えない最大の整数mを計算して(図12のステップ7010)記憶する処理と、
前記素数候補Nから、N−1を計算し、JをJ≧n/mとなる最小の整数としたときに(図12のステップ7020)、(N−1)を最下位からmビットごとにJ個の区間に区切り、(N−1)=2(J−1)m・e[J−1]+2(J−2)m・e[J−2]+…+2m・e[1]+e[0]なる式を満たすように(N−1)を部分指数e[0],e[1],…,e[J−1]に分割する指数部切り出し処理と(図12のステップ7030)、
前記指数部切り出し処理により切り出されたmビットの値e[i]から2^(e[i]+1+n−2m)を生成する2のベキ乗生成処理と、
前記指数部切り出し処理により切り出された部分指数の最上位の値に1を加えたe[J−1]+1が2nと等しい場合は(図12のステップ7050)、R mod N=2n mod Nの演算結果と、R2 mod N=22n mod Nの演算結果との前記素数候補Nを法とするモンゴメリ剰余乗算を行って(図12のステップ7070)その演算結果を第1記憶領域に格納する第1処理と、
前記e[J−1]+1が2n未満の場合は、前記Nのe[J−1]+1ビット目の値を指定ビット反転器(3020)により反転した値と前記R2 mod N=22n mod Nの演算結果との前記素数候補Nを法とするモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に格納する第2処理と(図12のステップ8086)、
前記第1処理又は第2処理のいずれか一方の処理の後に内部の状態変数iをJ−2とする第3処理と(図12のステップ7080)、
前記第3処理の後に、前記素数候補Nを法とし、前記第1記憶領域に記憶された値同士のモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に格納する動作をm回繰り返す第4処理と (図13のステップ7090)、
前記第4処理の後に、前記指数部切り出し処理によって切り出された部分指数e[i]が2m−1未満の場合は(図13のステップ7100)、前記Nのe[i]+1+n−2mビット目の値を前記指定ビット反転器(3020)により反転した値と前記第1記憶領域に格納された値との前記素数候補Nを法とするモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に記憶する第5処理と (図13のステップ8110)、
前記第4処理の後に、前記指数部切り出し処理によって切り出された部分指数e[i]が2m−1と等しい場合は、前記R mod N=2n mod Nの演算結果と前記第1記憶領域に格納された値との前記素数候補Nを法とするモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に格納する第6処理と(図13のステップ7120)、
前記第5処理又は第6処理のいずれか一方の処理の後に、前記内部状態変数iから1を引いた値を前記内部状態変数iに格納し(図13のステップ7130)、前記iの値が2以上の場合は、前記第3処理に戻り(図13のステップ7140)、前記iの値が1以下になるまでそれを繰り返す第7処理と、
前記第7処理の後に、前記素数候補Nを法とし、前記第1記憶領域に記憶された値同士のモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に格納する動作をm回繰り返す第8処理と(図14のステップ7150)、
前記第8処理の後、前記2のベキ乗生成手段により計算した2^(e[1]+n−2m)と前記第1記憶領域に格納された値との前記素数候補Nを法とするモンゴメリ剰余乗算をおこなってその演算結果を前記第1記憶領域に格納する第9処理と(図14のステップ7160)、
前記第9処理の後、前記素数候補Nを法とし、前記第1記憶領域に記憶された値同士のモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に格納する動作をm回繰り返す第10処理と(図14のステップ7170)、
前記第10処理の後、前記2のベキ乗生成処理により生成された2^(e[0])と、前記第1記憶領域に格納された値との前記素数候補Nを法とするモンゴメリ剰余乗算を行って(図14のステップ7180)その演算結果をフェルマーテスト結果として出力する第11処理とを含む、データ処理装置。
【0047】
〔6〕項5のデータ処理装置は、前記プログラムを格納したメモリを更に有し、1個の半導体基板に形成される。
【0048】
2.実施の形態の詳細
実施の形態について更に詳述する。以下、本発明を実施するための形態を図面に基づいて詳細に説明する。なお、発明を実施するための形態を説明するための全図において、同一の機能を有する要素には同一の符号を付して、その繰り返しの説明を省略する。
【0049】
<<第1の実施形態>>
図1はフェルマーテストを実行する本発明に係るデータ処理装置1を機能ブロックダイヤグラムで示すものであり、図9、図10及び図11に示される本発明によるフェルマーテスト高速演算手順を実現する。データ処理装置1は、図7に例示されるモンゴメリ剰余乗算器(6050)及び演算レジスタ(6060,6070,6080)等を備えたモンゴメリ乗算コプロセッサ(6040)と共に、プログラムを実行してモンゴメリ乗算コプロセッサ6040等を制御する中央処理装置(6010)とメモリ(6020)等を有し、相互にバス6030で接続される。メモリ(6020)はプログラム(PGM)を格納する電気的に書換え可能な不揮発性メモリと、変数やデータ(DAT)等の格納に利用されるSRAM等のランダムアクセスメモリから成る。このデータ処理装置1は例えば、図17に示されるような1個の半導体基板に形成されたICカード用マイクロコンピュータ107として実現される。図17ではICカード用マイクロコンピュータ107はICカード基板108に搭載されている。ICカード用マイクロコンピュータ107は、プログラムや重要な情報がオンチップのメモリに格納されており、外部からそれらの情報に直接アクセスすることができない。ようになっている。外部との通信は、I/Oピン(106)のみを介して、完全にICカードチップの制御下で行われ、通常情報は暗号化した状態で送受信され、情報の秘匿性が実現されている。暗号通信を行うためには、通信する相手と暗号鍵の共有を行う必要がある。事前に鍵を通信相手と共有しておく方法もあるが、一度鍵が判明してしまうと、暗号化した通信内容が復号化されてしまう。そこで、通信に用いる暗号鍵をランダムに生成し、相手に鍵を送信し、その鍵を用いて通信するという方法が一般的に用いられている。外部インタフェース端子として、Vccピン101、リセットピン102、クロック入力ピン103、グランドピン104、不揮発メモリプログラム用電源ピン105、及びI/Oピン106を有する。
【0050】
ICカード用マイクロコンピュータ107はオンチップのメモリ等の限られた演算リソースを用いて暗号通信に使用する暗号鍵を生成する機能を備える。暗号鍵にはビット数の多い素数を用いることになり、その素数性を判定する演算処理の第1の例について説明する。
【0051】
図1において法レジスタN(1000)は外部より素数候補Nを入力して格納し、ビットnレジスタ(1010)は、外部より素数候補Nのビット数nを入力して格納する。log2(n)を超えない最大の整数を与えるlog2計算装置(1030)により、log2(n)を超えない最大の整数mが得られる。1030の出力する値の種類は、log2(nの最大値)であるので、実際には計算を行わずにテーブル引きや、nの非零のビットのうちの最上位のビットの位置から求めることができる。たとえば、
n0:=n
m:=0
while n0>1
m:=m+1
n0:=n0>>1
end while
としてもよい。この処理は、図9の7010のステップに相当する。1030で求められたmはmを格納するレジスタ(1020)に格納される。整数除算器(1040)により、n/mの小数点以下を切り上げた値が求められ、セレクタ(1050)により1040の出力が選択され、カウンタi(1060)にセットされる。この処理は、図9のステップ7020に相当する。カウンタiは、mビットごとに分割された(N−1)の何番目の部分ビットを取り出すのかを指定するために用いられる。一方、演算器(1100)により、R2 mod N=22n mod Nが計算され、結果レジスタ(1160)に格納される。図1においてその格納パスは図示が省略されている。この処理は図9のステップ7040に相当する。図9の“result”は前記結果レジスタ’1160)を意味する。つぎに、R mod N=2n mod Nが計算され、レジスタ(1110)に格納される。この処理は、図9のステップ7070で用いるRmodNの準備に相当する。iの値にしたがって、指数切り出し部(1080)により、(N−1)の最上位が切り出され、演算数生成装置(1090)により、2^(e[i]+1)が生成される。つぎに、mビット長の値すべてのビットが1である値を生成する2m−1生成器(1120)の値と1090により切り出された指数との比較が比較器(1130)により行われ、等しい場合はセレクタ(1140)はレジスタ(1110)を選択し、そうでない場合は演算数生成装置(1090)の出力が選択される。モンゴメリ剰余乗算器(1150)により、結果レジスタ(1160)の値とセレクタ(1140)に選択された値とのモンゴメリ剰余乗算が行われ、結果レジスタ(1160)に格納される。この処理は、図9のステップ7050、7060,7070に相当する。減算器(1070)により、カウンタi(1060)の値はデクリメントされ、デクリメントされた結果がセレクタ(1050)に選択され、カウンタi(1070)が更新される。この処理は図9のステップ7080に相当する。
【0052】
モンゴメリ剰余乗算演算モード制御部(1200)は次にモンゴメリ剰余乗算器(1150)の演算モードを二乗算に変更し、セレクタ(1170)を介してカウンタj(1180)を初期化する。モンゴメリ剰余乗算演算モード制御部は(1200)は、カウンタj(1180)を減算器(1190)で1回デクリメントする毎に、モンゴメリ剰余乗算器(1150)を用いて、結果レジスタ(1160)の値をモンゴメリ剰余二乗算し結果レジスタ(1160)に格納する処理を、カウンタj(1180)がゼロになるまで行う。これは、図10のステップ7090に相当する。つぎに、カウンタi(1060)の値にしたがって、指数切り出し部(1080)により、(N−1)の部分ビットが切り出され、比較器(1130)により2m−1と比較される。比較結果により、セレクタ(1140)により、演算数生成装置(1090)の出力かR mod Nを格納したレジスタ(1110)が選択され、結果レジスタ(1160)の値と剰余乗算が行われる。これは、図10のステップ7100,7110,7120の処理に相当する。剰余乗算が終了したら、カウンタi(1060)の値を演算器(1070)によりデクリメントし、カウンタi(1060)の値が1以上の場合は、図9のステップ7090に相当する処理から繰り返す。
【0053】
カウンタi(1060)の値が1の場合は、モンゴメリ剰余乗算器(1150)の演算モードを二乗算に変更し、セレクタ(1170)を介してカウンタj(1180)を初期化する。モンゴメリ剰余乗算演算モード制御部は(1200)は、カウンタj(1180)を減算器(1190)で1回デクリメントする毎に、モンゴメリ剰余乗算器(1150)を用いて、結果レジスタ(1160)の値をモンゴメリ剰余二乗算し結果レジスタ(1160)に格納する処理を、カウンタj(1180)がゼロになるまで行う。これは、図11のステップ7150に相当する。
【0054】
つぎに、カウンタi(1060)の値にしたがって、指数切り出し部(1080)により、(N−1)の最下位から2番目のmビットが取り出される。カウンタi(1060)が1の場合は、演算数生成装置(1090)を常に選択し、結果レジスタ(1160)の値と剰余乗算が行われる。これは、図11のステップ7160の処理に相当する。剰余乗算が終了したら、カウンタi(1060)の値が演算器(1070)によりデクリメントされ、カウンタi(1060)に設定される。
【0055】
モンゴメリ剰余乗算器(1150)の演算モードが二乗算に変更され、セレクタ(1170)を介してカウンタj(1180)が初期化される。モンゴメリ剰余乗算演算モード制御部は(1200)は、カウンタj(1180)を減算器(1190)で1回デクリメントする毎に、モンゴメリ剰余乗算器(1150)を用いて、結果レジスタ(1160)の値をモンゴメリ剰余二乗算し結果レジスタ(1160)に格納する処理を、カウンタj(1180)がゼロになるまで行う。これは、図11のステップ7170に相当する。
【0056】
最後に、カウンタi(1060)の値にしたがって、指数切り出し部(1080)により、(N−1)の最下位のmビットを取り出す。カウンタi(1060)が0の場合は、演算数生成装置(1090)を常に選択し、結果レジスタ(1160)の値と剰余乗算が行われる。これは、図11のステップ7180の処理に相当する。剰余乗算が終了したら、結果レジスタ(1160)に2^(N−1)mod Nの値が格納され、処理が終了する。
【0057】
図2はR2mod Nを計算する演算器(1100)の詳細を示す。演算器(1100)は、法N(1000)およびビット長n(1010)が入力されると、演算器(2010)により、2RmodNが計算される。ここで、2R=2n+1である。nビット目が1になるまでNが左ビットシフトされ、2n+1から左シフトしされたNの値が減算されて2RmodNレジスタ(2020)に格納すされる。Nは素数候補であるから奇数であるので、必ずn−1ビット目以下にゼロでないビットを含む。したがって、Nを左シフトした値は2nよりも大きな値となるので、2n+1から左シフトしたNの値を減算した結果は、2nよりも小さな値となる。2RmodN(2020)に格納される値は、2n未満であれば、正確にmodNを求めなくとも良い。
【0058】
2SmodNレジスタ(2060)には、2n−N=Rを代入しておく。Rはモンゴメリ剰余乗算では1と等価である。2RmodNレジスタ(2020)に格納されている値は、2tRmodNと表記するとt=1に相当する。モンゴメリ剰余乗算器を用いて、モンゴメリ剰余二乗算を1回行うと、tが倍となる。モンゴメリ剰余二乗算を行った後は、結果は演算数レジスタ(2030)に格納される。R2modNは、2nRmodNと等しいので、R2modNを計算するには、モンゴメリ剰余二乗算を行い、tの値が変わるたびに、tとnの値の論理積(AND)を採り、ゼロでない場合は、演算数(2030)と2SmodNレジスタ(2060)を入力とし、モンゴメリ剰余乗算器(2050)で剰余乗算を行い、結果を2SmodNレジスタ(2060)に格納するという処理を行う。次に、ふたたび演算数レジスタ(2030)の値をモンゴメリ剰余二乗算する処理を行い、tとnの値のANDをとり、ゼロでない場合は、演算数(2030)と2SmodNレジスタ(2060)を入力とし、モンゴメリ剰余乗算器(2050)剰余乗算を行い、結果を2SmodNレジスタ(2060)に格納するという処理を、2t>nとなるまで繰り返す。この処理が終了すると、2SmodNレジスタ(2060)にはR2modNが格納される。
【0059】
<<第2の実施形態>>
図3はフェルマーテストを実行する本発明に係るデータ処理装置2を機能ブロックダイヤグラムで示すものであり、図12、図13及び図14に示される本発明によるフェルマーテスト高速演算手順を実現する。データ処理装置1は図7で説明したのと同様にモンゴメリ剰余乗算器(6050)及び演算レジスタ(6060,6070,6080)等を備えたモンゴメリ乗算コプロセッサ(6040)と共に、プログラムを実行してモンゴメリ乗算コプロセッサ6040等を制御する中央処理装置(6010)とメモリ(6020)等を有し、例えば図17に例示されるようなICカード用マイクロコンピュータ107として実現される。データ処理装置2で構成されたICカード用マイクロコンピュータ107はオンチップのメモリ等の限られた演算リソースを用いて暗号通信に使用する暗号鍵を生成する機能を備え、暗号鍵と種いて用いる乱数の素数性を判定する演算処理の第2の例について説明する。
【0060】
図3において、法レジスタN(1000)は外部より素数候補Nを入力し、格納し、法ビットnレジスタ(1010)は、外部より素数候補のビット数nを入力し、格納する。log2(n)を超えない最大の整数を与えるlog2計算装置(1030)により、log2(n)を超えない最大の整数mが得られる。この処理は、図12の7010のステップに相当する。1030で求められたmはmを格納するレジスタ(1020)に格納される。整数除算器(1040)により、n/mの少数点以下を切り上げた値が求められ、セレクタ(1050)により1040の出力が選択され、カウンタi(1060)にセットされる。この処理は、図12のステップ7020に相当する。カウンタiは、mビットごとに分割された(N−1)の何番目の部分ビットを取り出すのかを指定するために用いられる。一方、演算器(1100)により、R2modN=22nmodNが計算され、結果レジスタ(1160)に格納される。図3においてその格納パスは図示が省略されている。この処理は図12のステップ7040に相当する。つぎに、RmodN=2nmodNが計算され、レジスタ(1110)に格納される。この処理は、図12のステップ7070で用いるRmodNの準備を行うことに相当する。iの値にしたがって、指数切り出し部(1080)により、(N−1)の最上位e[J−1]が切り出され、セレクタ(3010)によりNが選択され、指定ビット反転器(3020)により、e[J−1]+1ビット目が反転され、演算数発生装置(1090)に格納される。指定ビット反転器(3020)ではe[J−1]+1がn以上の場合は、どのビットも反転されない。つぎに、mビット長の値すべてのビットが1である値を生成する2m−1生成器(1120)の値と1090により切り出された指数との比較が比較器(1130)により比較され、等しい場合はセレクタ(1140)がレジスタ(1110)を選択し、そうでない場合は演算数生成装置(1090)の出力が選択される。モンゴメリ剰余乗算器(1150)により、結果レジスタ(1160)の値とセレクタ(1140)に選択された値とのモンゴメリ剰余乗算が行われ、その演算結果が結果レジスタ(1160)に格納される。この処理は、図12のステップ7050、8060,7070に相当する。減算器(1070)により、カウンタi(1060)の値はデクリメントされ、デクリメントされた結果がセレクタ(1050)に選択され、カウンタi(1070)が更新される。この処理は図12のステップ7080に相当する。
【0061】
モンゴメリ剰余乗算演算モード制御部(1200)は次にモンゴメリ剰余乗算器(1150)の演算モードを二乗算に変更し、セレクタ(1170)を介してカウンタj(1180)を初期化する。モンゴメリ剰余乗算演算モード制御部は(1200)は、カウンタj(1180)を減算器(1190)で1回デクリメントする毎に、モンゴメリ剰余乗算器(1150)を用いて、結果レジスタ(1160)の値をモンゴメリ剰余二乗算し結果レジスタ(1160)に格納する処理を、カウンタj(1180)がゼロになるまで行う。これは、図13のステップ7090に相当する。つぎに、カウンタi(1060)の値にしたがって、指数切り出し部(1080)により、(N−1)の部分ビットe[i]が切り出される。セレクタ(3010)によりNが選択され、指定ビット反転器(3020)により、e[i]+1+n−2mビット目が反転され、演算数発生装置(1090)に格納される。指定ビット反転器(3020)ではe[i]+1+n−2mがn以上の場合は、どのビットも反転されない。指数切り出し部(1080)により切り出された値は比較器(1130)により2m−1と比較される。比較結果に基づいて、セレクタ(1140)により、演算数生成装置(1090)の出力又はR mod Nを格納したレジスタ(1110)が選択され、選択された値が結果レジスタ(1160)の値と剰余乗算が行われる。これは、図13のステップ7100,8110,7120の処理に相当する。剰余乗算が終了したら、カウンタi(1060)の値が演算器(1070)によりデクリメントされ、カウンタi(1060)の値が1以上の場合は、図13のステップ7090に相当する処理から繰り返される。
【0062】
カウンタi(1060)の値が1の場合は、モンゴメリ剰余乗算器(1150)の演算モードが二乗算に変更され、セレクタ(1170)を介してカウンタj(1180)が初期化される。モンゴメリ剰余乗算演算モード制御部は(1200)は、カウンタj(1180)を減算器(1190)で1回デクリメントする毎に、モンゴメリ剰余乗算器(1150)を用いて、結果レジスタ(1160)の値をモンゴメリ剰余二乗算してその演算結果を結果レジスタ(1160)に格納する処理を、カウンタj(1180)がゼロになるまで行う。これは、図14のステップ7150に相当する。
【0063】
つぎに、カウンタi(1060)の値にしたがって、指数切り出し部(1080)により、(N−1)の最下位から2番目のmビットが取り出される。カウンタi(1060)が1の場合は、セレクタ(3010)により0が選択され、指定ビット反転器(3020)により、e[1]+n−2mビット目が反転した値、すなわちe[1]+n−2mビット目がセットされた値が演算数生成装置(1090)に格納され、結果レジスタ(1160)の値と剰余乗算が行われる。これは、図14のステップ7160の処理に相当する。剰余乗算が終了したら、カウンタi(1060)の値を演算器(1070)によりデクリメントし、カウンタi(1060)に設定する。
【0064】
続いてモンゴメリ剰余乗算器(1150)の演算モードが二乗算に変更され、セレクタ(1170)を介してカウンタj(1180)が初期化される。モンゴメリ剰余乗算演算モード制御部は(1200)は、カウンタj(1180)を減算器(1190)で1回デクリメントする毎に、モンゴメリ剰余乗算器(1150)を用いて、結果レジスタ(1160)の値をモンゴメリ剰余二乗算し結果レジスタ(1160)に格納する処理を、カウンタj(1180)がゼロになるまで行う。これは、図14のステップ7170に相当する。
【0065】
最後に、カウンタi(1060)の値にしたがって、指数切り出し部(1080)により、(N−1)の最下位のmビットを取り出す。カウンタi(1060)が0の場合は、セレクタ(3010)により0が選択され、指定ビット反転器(3020)により、e[0]ビット目が反転した値、すなわちe[0]ビット目がセットされた値が演算数生成装置(1090)に格納され、その演算数生成装置(1090)が常に選択されて、結果レジスタ(1160)の値と剰余乗算が行われる。これは、図14のステップ7180の処理に相当する。剰余乗算が終了したら、結果レジスタ(1160)に2^(N−1)mod Nの値が格納され、処理が終了する。
【0066】
<<第3の実施形態>>
図4はフェルマーテストを実行する本発明に係るデータ処理装置3を機能ブロックダイヤグラムで示すものであり、図12、図13及び図14に示される本発明によるフェルマーテスト高速演算手順を実現する。図3のデータ処理装置2では指定ビット反転器(3020)を用いたが、図4ではそれに代えて2のベキ数演算器(3031)と排他的論理和回路(3032)を用いた点が相違され、その他の構成については同じ参照符号を付してその詳細な説明を省略する。2のベキ数演算器(3031)は指数切り出し部(1080)で切り出された指数を2のベキ乗に形態にする。排他的論理和回路(3032)は2のべき乗演算器(3031)の出力とセレクタ(3010)の出力に対して排他的論理和を採る。その演算結果は図3の指定ビット反転器(3020)の出力と同じである。
【0067】
<<第4の実施形態>>
図5はフェルマーテストを実行する本発明に係るデータ処理装置4を機能ブロックダイヤグラムで示すものであり、図15に示されるフェルマーテスト高速演算手順を実現する。この例ではモンゴメリ剰余乗算装置を用いない。データ処理装置4は、図8に例示される剰余乗算器(6150)及び演算レジスタ(6160,6170,6180)等を備えた剰余乗算コプロセッサ(6140)と共に、プログラムを実行して剰余乗算コプロセッサ6140等を制御する中央処理装置(6010)とメモリ(6020)等を有し、相互にバス6030で接続される。メモリ(6020)はプログラム(PGM)を格納する電気的に書換え可能な不揮発性メモリと、変数やデータ(DAT)等の格納に利用されるSRAM等のランダムアクセスメモリから成る。このデータ処理装置4は例えば、前記図17に示されるような1個の半導体基板に形成されたICカード用マイクロコンピュータ107として実現される。
【0068】
図5において、法レジスタN(1000)には外部より素数候補Nが入力されて格納され、法ビットnレジスタ(1010)には外部より素数候補Nのビット数nが入力されて格納される。log2(n)を超えない最大の整数を与えるlog2計算装置(1030)により、log2(n)を超えない最大の整数mが得られる。1030の出力する値の種類は、log2(nの最大値)であるので、実際には計算を行わずにテーブル引きや、nの非零のビットのうちの最上位のビットの位置から求めることができる。この処理は、図15の9010のステップに相当する。log2計算装置(1030)で求められた値mはレジスタ(1020)に格納される。整数除算器(1040)により、n/mの少数点以下を切り上げた値が求められ、セレクタ(1050)により1040の出力が選択され、カウンタi(1060)にセットされる。この処理は、図15のステップ9020に相当する。カウンタiは、mビットごとに分割された(N−1)の何番目の部分ビットを取り出すのかを指定するために用いられる。iの値にしたがって、指数切り出し部(1080)により、(N−1)の最上位が切り出され、演算数生成装置(1090)により、2^(e[J−1])が生成される。最初は剰余乗算器(4010)で乗算を行わずに、演算数生成装置(1090)の値をそのまま結果レジスタ(4020)に格納する。この処理は、図15のステップ9040に相当する。減算器(1070)により、カウンタi(1060)の値はデクリメントされ、デクリメントされた結果がセレクタ(1050)に選択され、これによってカウンタi(1070)が更新される。この処理は図15のステップ9050に相当する。
【0069】
剰余乗算演算モード制御部(4030)は次に剰余乗算器(4010)の演算モードを二乗算に変更し、セレクタ(1170)を介してカウンタj(1180)を初期化する。剰余乗算演算モード制御部(4030)は、カウンタj(1180)を減算器(1190)で1回デクリメントする毎に、剰余乗算器(4010)を用いて、結果レジスタ(4020)の値を剰余二乗算して結果レジスタ(4020)に格納する処理を、カウンタj(1180)がゼロになるまで行う。これは、図15のステップ9060に相当する。つぎに、カウンタi(1060)の値にしたがって、指数切り出し部(1080)により、(N−1)の部分ビットが切り出され、演算数生成装置(1090)の出力と、結果レジスタ(4020)の値との剰余乗算が行われる。これは、図15のステップ9070の処理に相当する。剰余乗算が終了したら、カウンタi(1060)の値が演算器(1070)によりデクリメントされ、カウンタi(1060)の値が0以上の場合は、図15のステップ9060に相当する処理から繰り返される。
【0070】
カウンタi(1060)の値が0の場合は、結果レジスタ(4020)に2^(N−1)mod Nの値が格納され、処理が終了する。
【0071】
<<第5の実施形態>>
図6はフェルマーテストを実行する本発明に係るデータ処理装置5を機能ブロックダイヤグラムで示すものであり、図16に示されるフェルマーテスト高速演算手順を実現する。この例ではモンゴメリ剰余乗算装置を用いない。データ処理装置4は、前記図8に例示される剰余乗算器(6150)及び演算レジスタ(6160,6170,6180)等を備えた剰余乗算コプロセッサ(6140)と共に、プログラムを実行して剰余乗算コプロセッサ6140等を制御する中央処理装置(6010)とメモリ(6020)等を有し、相互にバス6030で接続される。このデータ処理装置5は例えば、前記図17に示されるような1個の半導体基板に形成されたICカード用マイクロコンピュータ107として実現される。
【0072】
図6において、法レジスタN(1000)は外部より素数候補Nを入力して格納し、法ビットnレジスタ(1010)は、外部より素数候補のビット数nを入力して格納する。log2(n)を超えない最大の整数を与えるlog2計算装置(1030)により、log2(n)を超えない最大の整数mが得られる。1030の出力する値の種類は、log2(nの最大値)であるので、実際には計算を行わずにテーブル引きや、nの非零のビットのうちの最上位のビットの位置から求めることができる。この処理は、図16の9010のステップに相当する。1030で求められた値mはレジスタ(1020)に格納される。整数除算器(1040)により、n/mの少数点以下を切り上げた値が求められ、セレクタ(1050)により1040の出力が選択され、カウンタi(1060)にセットされる。この処理は、図16のステップ9020に相当する。カウンタiは、mビットごとに分割された(N−1)の何番目の部分ビットを取り出すのかを指定するために用いられる。iの値にしたがって、指数切り出し部(1080)により、(N−1)の最上位(e[J−1])が切り出され、セレクタ(3010)が0を選択し、指定ビット反転器(3020)が(e[J−1])ビット目を反転することにより、2^(e[J−1])が演算数生成装置(1090)にセットされる。一番最初は剰余乗算器(4010)で乗算を行わずに、演算数生成装置(1090)の値をそのまま結果レジスタ(4020)に格納する。この処理は、図16のステップ9040に相当する。減算器(1070)により、カウンタi(1060)の値はデクリメントされ、デクリメントされた結果がセレクタ(1050)に選択され、カウンタi(1070)が更新される。この処理は図16のステップ9050に相当する。
【0073】
剰余乗算演算モード制御部(4030)は次に剰余乗算器(4010)の演算モードを二乗算に変更し、セレクタ(1170)を介してカウンタj(1180)を初期化する。剰余乗算演算モード制御部(4030)は、カウンタj(1180)を減算器(1190)で1回デクリメントする毎に、剰余乗算器(4010)を用いて、結果レジスタ(4020)の値を剰余二乗算し結果レジスタ(4020)に格納する処理を、カウンタj(1180)がゼロになるまで行う。これは、図15のステップ9060に相当する。つぎに、カウンタi(1060)の値にしたがって、指数切り出し部(1080)により、(N−1)の部分ビット(e[i])が切り出され、セレクタ(3010)がNを選択し、指定ビット反転器(3020)が(e[i])ビット目を反転することにより、N xor 2^(e[i])が演算数生成装置(1090)にセットされる。演算数生成装置(1090)の出力と結果レジスタ(4020)の値との剰余乗算が行われ、演算結果が結果レジスタ(4020)に格納される。これは、図16のステップ10070の処理に相当する。剰余乗算が終了したら、カウンタi(1060)の値が演算器(1070)によりデクリメントされ、カウンタi(1060)の値が1以上の場合は、図16のステップ9060に相当する処理から繰り返される。
【0074】
カウンタi(1060)の値が0の場合は、指数切り出し部(1080)により、(N−1)の最下位の部分ビット(e[0])が切り出され、セレクタ(3010)が0を選択し、指定ビット反転器(3020)が(e[i])ビット目を反転することにより、2^(e[0])が演算数生成装置(1090)にセットされる。演算数生成装置(1090)の出力と結果レジスタ(4020)の値との剰余乗算が行われ、演算結果が結果レジスタ(4020)に格納される。結果レジスタ(4020)には2^(N−1)mod Nの値が格納されるので、処理が終了する。
【0075】
以上本発明者によってなされた発明を実施形態に基づいて具体的に説明したが、本発明はそれに限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能であることは言うまでもない。本発明の好適な例はICカード用マイクロコンピュータであるが、オンチップされる回路モジュールは上記説明に限定されず、その他の回路モジュールが追加されてもよい。また、ICカード用マイクロコンピュータはセキュリティ評価基準のISO/IEC15408の評価・認証機関によって認証済みであることに限定されない。
【図面の簡単な説明】
【0076】
【図1】図1は第1の実施形態に係るデータ処理装置を例示する機能ブロックダイヤグラムである。
【図2】図2は第1の実施形態で用いられるR2modNを演算する演算器の一例を示すブロックダイヤグラムである。
【図3】図3は第2の実施形態に係るデータ処理装置を例示する機能ブロックダイヤグラムである。
【図4】図4は第3の実施形態に係るデータ処理装置を例示する機能ブロックダイヤグラムである。
【図5】図5は第4の実施形態に係るデータ処理装置を例示する機能ブロックダイヤグラムである。
【図6】図6は第5の実施形態に係るデータ処理装置を例示する機能ブロックダイヤグラムである。
【図7】図7は第1又は第2の実施形態に係るデータ処理装置のハードウェア構成を例示するブロックダイヤグラムである。
【図8】図8は第3又は第4の実施形態に係るデータ処理装置のハードウェア構成を例示するブロックダイヤグラムである。
【図9】図9は第1および第2の実施形態に係るデータ処理装置による処理手順を例示するフローチャートである。
【図10】図10は図9の続きを示すフローチャートである。
【図11】図11は図10の続きを示すフローチャートである。
【図12】図12は第3の実施形態に係るデータ処理装置による処理手順を例示するフローチャートである。
【図13】図13は図12の続きを示すフローチャートである。
【図14】図14は図13の続きを示すフローチャートである。
【図15】図15は第4の実施形態に係るデータ処理装置による処理手順を例示するフローチャートである。
【図16】図16は第5の実施形態に係るデータ処理装置による処理手順を例示するフローチャートである。
【図17】図17はICカードの構成を例示する外観図である。
【符号の説明】
【0077】
107:ICカード用チップ
1000:法Nを格納するレジスタ
1010:法Nのビット長を格納するレジスタ
1020:指数を切り出すビット長mを格納するレジスタ
1030:入力された値のlog2を超えない最大の整数を与えるlog2計算装置
1040:整数除算器
1050:整数除算器と減算器の出力を選択するセレクタ
1060:カウンタiを格納するレジスタ
1070:減算器
1080:N−1をmビット毎に区切り、下位側からi番目の値を出力する指数切り出し部
1090:入力値のビット位置のみを1としその他のビットを0とする演算数を生成する演算数生成装置
1100:R mod NもしくはR2modNを計算する演算器
1110:演算器が計算したRもしくはR2を格納するレジスタ
1120:mビット長の値すべてのビットが1である値を生成する2m−1生成器
1130:比較器
1150:モンゴメリ剰余乗算器
1160:剰余乗算の結果を格納する結果レジスタ
1180:カウンタ値jを格納するレジスタ
1190:減算器
1200:モンゴメリ剰余乗算モード制御装置
2010:法Nと法Nのビット長Nから、2n+1modNを計算する演算器
2020:2n+1modNをか苦悩するレジスタ
2030:演算途中の値を格納する演算数レジスタ
2060:モンゴメリ剰余乗算器
3020:指定されたビットのみを反転して出力する指定ビット反転器
3032:排他的論理和回路
4010:剰余乗算器
4020:結果を格納するレジスタ
4030:剰余乗算器の演算モードを制御する制御装置
6010:CPU
6020:メモリ
6030:バス
6040:剰余乗算コプロセッサ
6050:モンゴメリ剰余乗算器
6060:演算数を格納するレジスタ
6070:演算数を格納するレジスタ
6080:法Nを格納するレジスタ
6140:剰余乗算コプロセッサ
6150:剰余乗算器
6160:演算数を格納するレジスタ
6170:演算数を格納するレジスタ
6180:法Nを格納するレジスタ
7010:log2(n)を超えない最大の整数をmに代入するステップ
7020:n/mの少数点以下を切り上げた値をJに代入するステップ
7030:N−1をmビットごとに区切りe[0]…e[J−1]に代入するステップ
7040:R2modNをresultに代入するステップ
7050:e[J−1]+1がnと等しいか条件判定するステップ
7060:最上位の指数が2m−1未満の場合に最上位の指数に相当する演算数を剰余乗算するステップ
7070:最上位の指数が2m−1と等しい場合に最上位の指数に相当する演算数を剰余乗算するステップ
7080:カウンタiにJ−2を代入するステップ
7090:resultをm回剰余二乗算してresultに代入するステップ
7100:e[i]+n−2mがnと等しいか条件判断するステップ
7110:e[i]+n−2mがn未満のときi番目のmビットの指数に相当する演算数を剰余乗算するステップ
7120:e[i]+n−2mがnと等しいときi番目のmビットの指数に相当する演算数を剰余乗算するステップ
7130:カウンタiの値を1だけ減算するステップ
7140:iが1より大きいか条件判断し条件分岐するステップ
7150:resultをm回剰余二乗算してresultに代入するステップ
7160:最下位の1つ前のmビットの指数に相当する演算数を剰余乗算するステップ
7170:resultをm回剰余二乗算してresultに代入するステップ
7180:最下位の1つ前のmビットの指数に相当する演算数を剰余乗算するステップ
7190:結果を出力するステップ
8060:最上位の指数が2m−1未満の場合に最上位の指数に相当する演算数を法Nでマスクしながら剰余乗算するステップ
8110:e[i]+n−2mがn未満の場合にi番目のmビットの指数に相当する演算数を法Nでマスクしながら剰余乗算するステップ
9010:log2(n)を超えない最大の整数をmに代入するステップ
9020:n/mの少数点以下を切り上げた値をJに代入するステップ
9030:N−1をmビットごとに区切りe[0]…e[J−1]に代入するステップ
9040:最上位の指数に相当する演算数をresultに代入するステップ
9050はカウンタiにJ−2を代入するステップ
9060:resultをm回剰余二乗算してresultに代入するステップ
9070:i番目のmビットの指数に相当する演算数を剰余乗算するステップ
9080:カウンタiの値を1だけ減算するステップ
9090:カウンタiが0以上かを判定し条件分岐するステップ
9100:結果を出力するステップ
10070:i番目のmビットの指数に相当する演算数を法Nでマスクしながら剰余乗算するステップ
10090:カウンタiが1以上かを判定し条件分岐するステップ
10100:最下位のmビットの指数に相当する演算数を剰余乗算するステップ
【技術分野】
【0001】
本発明は、フェルマーテストを実行するデータ処理装置に関し、例えば機密性の高いICカードなどの耐タンパ装置向けの素数生成に関するものである。
【背景技術】
【0002】
ICカードは、主に、勝手に書き換えられない情報の保持や秘密情報である暗号鍵を使ったデータの暗号化や暗号文の復号化を行うために使われる装置である。
【0003】
ICカードは、電源を持っていないため、リーダライタに差し込まれると、電源の供給を受け、動作可能となる。動作可能になると、リーダライタからコマンドを受けて、コマンドに従い、データの転送を行う。
【0004】
ICカードチップは、プログラムや重要な情報がICカード用チップの中に密閉されており、外部からそれらの情報に直接アクセスすることはできない。外部との通信は、I/Oピンのみを介して、完全にICカードチップの制御下で行われ、通常情報は暗号化した状態で送受信され、情報の秘匿性を実現している。暗号通信を行うためには、通信する相手と暗号鍵の共有を行う必要がある。事前に鍵を通信相手と共有しておく方法もあるが、一度鍵が判明してしまうと、暗号化した通信内容が復号化されてしまう。そこで、通信に用いる暗号鍵をランダムに生成し、相手に鍵を送信し、その鍵を用いて通信するという方法がある。
【0005】
相手に鍵を送る際に、鍵を平文のまま送ってしまうと、次にその鍵を用いた暗号通信は簡単に解読されてしまう。そこで、公開鍵暗号技術を用いる。公開鍵暗号とは、暗号化に用いる鍵と、復号化に用いる鍵が異なり、暗号化に用いる鍵から複号に用いる鍵を求めることが、計算量的に困難な暗号方式である。
【0006】
公開鍵暗号方式を用いた鍵交換では、相手に自分の公開鍵を送り、相手側は通信の暗号化に用いる鍵を乱数などから生成し、送られてきた公開鍵で暗号化した後、暗号化された鍵を返信する。返信されてきた暗号化鍵を、さきほど相手に送った公開鍵に対応する秘密鍵で復号化し、次の通信に用いる。
【0007】
公開鍵暗号方式として最も広く用いられている暗号として、RSA暗号方式がある。この暗号方式は、2つの大きな素数の積からなる合成数が、容易に因数分解できないことを利用した暗号である。因数分解自体は、試行割り算法や数体篩などによって、アルゴリズム的には求めることは可能であるが、数が大きくなると、因数を求めることが時間的に困難となる。現在、1024ビットから2048ビット長の鍵が用いられている。鍵の生成はICカードの外部の計算機で行い、生成された鍵をICカードに書き込むという方法で公開鍵暗号方式の鍵をICカードに格納してきた。
【0008】
この方法では、原理的にICカードの外側に公開鍵暗号の秘密鍵が存在してしまうため、その秘密鍵が適切に管理できないと、セキュリティを確保できないという問題があった。そこで、ICカード内部で公開鍵暗号方式の秘密鍵と公開鍵のペアを生成することが行われるようになった。これにより、セキュリティは向上するが、RSA暗号の鍵生成はICカードで行うには時間の掛かる処理であり、高速化が必要となった。RSA暗号鍵の生成でもっとも時間の掛かる処理は、2つの大きな素数を生成する処理である。素数生成は、奇数乱数を生成し、次に生成された乱数が素数であるかを判定し、素数で無かった場合にはまた新たに素数を生成して素数判定を行う処理を繰り返すことで実現されている。
【0009】
素数判定には、いろいろな手法が用いられているが、2を元としたフェルマーテストにより、最初の素数判定を行い、それにパスした乱数をさらに厳密な素数判定処理に掛ける方式が高速化に向いている。これは、2倍算がシフトで行えるためである。
【0010】
しかし、指数部が1が0かにより、剰余乗算の有無などの処理の違いを消費電力の違いなどから推定し、秘密情報である素数が推定される可能性があり、セキュリティ面で不安があった。
【0011】
高速、かつセキュアにフェルマーテストを行う方法としては、一時に指数をmビットまとめて処理する、非特許文献1に記されているm−ary法(もしくはWindow法とも呼ばれる)がある。m−ary法では、指数部をm[bit]ごとに区切って,区間ごとにm回の剰余二乗算と1回の剰余乗算を行う。指数のビット数がn[bit]の場合,n回の剰余二乗算とn/m回の剰余乗算を行う必要がある。xy mod Nを計算する場合のm−ary法の手順を示す。ここで、e[i]はyをmビット毎に区切った値で、JをJ≧n/mとなる最小の整数としたときに、下記(式1)
y=2(J−1)m・e[J−1]+2(J−2)m・e[J−2]+…+2m・e[1]+e[0] (式1)
を満たす。m−ary法の手順は例えば、
result:= 1;
for i:=J−1 downTo 0 do
for j:=1 to m do
result:=result2 mod N
end for
result:=result * x^(e[i]) mod N
end for
return result
とされる。
【0012】
この方式は、ビットパタンによる処理内容に違いが発生せず、mの値を増やすことで、処理に必要な剰余乗算の回数がmに反比例して減少する。しかし、x^1〜x^(2m−1)までの値を事前に計算しておく必要があるため、mを増加させるとワークエリアが2mに比例して増加するという問題があった。これは、特にRAMのサイズに制約のあるICカードでは大きなネックとなる。
【0013】
x^(e[i])の値を必要になった際に動的に計算することも考えられるが、特にICカードでよく用いられるモンゴメリ剰余乗算アルゴリズム(非特許文献2)を用いたコプロセッサにおいては、通常の数値表現から2^n mod Nを乗じたモンゴメリ表現に変換する必要があるため、動的に剰余乗算の演算数を計算することは、速度低下をもたらすという問題があった。
【0014】
【非特許文献1】Alfred J. Menezes,Paul C. van Oorschot and Scott A. Vanstone,“HANDBOOK of APPLIED CRYPTOGRAPHY”,CRC Press,pp.615−616、ISBN 0−8493−8523−7,(1997)
【非特許文献2】Darrel Hankerson,Alfred Menezes and Scott Vanstone,“Guide to Elliptic Curve Cryptography”,Springer,pp.38,ISBN 0−387−95273−X,(2004)
【発明の開示】
【発明が解決しようとする課題】
【0015】
RSA暗号の鍵を高速に生成するには、素数を高速に生成することが必要であるが、従来手法で素数判定を高速に行う必要場合、速度と記憶容量はトレードオフの関係にあり、特にメモリ容量がICカードでは高速化が困難であった。
【0016】
本発明の目的は、メモリ容量を消費せずに高速にフェルマーテストによって素数判定を行うことができるデータ処理装置を提供することにある。
【0017】
本発明の前記並びにその他の目的と新規な特徴は本明細書の記述及び添付図面から明らかになるであろう。
【課題を解決するための手段】
【0018】
本願において開示される発明のうち代表的なものの概要を簡単に説明すれば下記の通りである。
【0019】
すなわち、本発明は、コプロセッサのビット長をnとしたときに、mをm≦log2(n)を満たす最大の整数とし、mビットごとに指数を処理することで、m−ary法での剰余乗算の回数を減らし、高速化を図る。また、m−ary法では、事前にx1からx2^m−1までの2m−1種類の値を事前計算し、メモリに格納する必要があるが、本発明ではx=2であることを利用し、処理中に剰余乗算に用いる演算数を動的に生成し、事前計算や事前計算した値を保存する記憶容量を用意しなくともよくすることで、必要な記憶容量を増やすことなく高速化を実現しようとするものである。尚、本明細書において記号^はべき乗演算を意味し、記号・は乗算演算を意味する。
【0020】
剰余乗算をモンゴメリコプロセッサで行う場合、2のベキ数にR(=2n mod N)を剰余乗算した値を用いる必要がある。Rも2のベキ数であるが、法Nよりも大きな値であるので、複雑なビットパタンとなり、事前計算を行うか、剰余乗算の都度、R2 mod Nをさらに乗じる必要がある。ここで、e[i]は(N−1)をmビット毎に区切った値で、JをJ≧n/mとなる最小の整数としたときに式(式2)
N−1=2(J−1)m・e[J−1]+…+2m・e[1]+e[0] (式2)
を満たすものとする。
【0021】
モンゴメリ剰余乗算コプロセッサを用いて、剰余乗算ごとにR2 mod Nを乗じる方法により2N−1 mod Nを計算する処理アルゴリズムは、
result:=R mod N
for i:=J−1 downTo 0 do
for j:=1 to m do
result:=result2 ・R−1mod N
end for
result:=result・2e[i]・R−1 mod N
result:=result・R2・R−1 mod N
end for
result:=result・1・R−1 mod N
return result
である。
【0022】
R2 mod Nを乗じる方式でも、必要なメモリ容量を増やすことなく、乗算回数は2・n/m回に削減することができるが、m−ary法でmビットごとに指数を扱った場合のn/m回と比べると、剰余乗算の回数が倍となる。
【0023】
この問題を解決するために、剰余乗算の演算数と被演算数それぞれにRが乗じられているのを、片方の被演算数のみにR2を乗じる方式を考える。こうすることで、乗じる値がハミングウエイト1となり、事前計算が不要となる。ただし、そのままの値を乗じると、剰余乗算後の結果にはRが乗じられているのみの形式になる。ベキ乗剰余の剰余演算の前には、剰余二乗算がm回行われることを利用し、剰余二乗算の結果、R2が乗じられる形式になるように、剰余乗算の際に補正値を乗じる。
【0024】
剰余乗算する際に、被演算数にR2=22nが乗じられるようにするには、剰余乗算後の被演算数には2nが乗じられているので、m回の剰余自乗算後に2nとなるような値を乗じればよい。すでに乗じられている2nと、追加で乗じられる2nとをあわせて、22nが常時乗じられる。したがって、演算数に次の式(3)
a^(2m)=2n (式3)
を満たす補正値aを乗ずればよい。
【0025】
これは、簡単に解くことができて、
a=2^(n/(2m)) (式4)
でaは与えられる。nが2のベキ数の場合は、mの定義より2m=nであるので、直ちに
a=2 (式5)
が求まる。
【0026】
一方、nが2のベキ数ではない場合、
a=2・2^(n・(2m)−1) (式6)
となり、2(n/(2^m)−1)は整数ではないため、そのまま補正値に用いることはできない。そこで、補正をm回の剰余自乗算の前に行う部分a’と、m回の剰余自乗算の後に行う部分bの2つに分ける。ここでは、a’=2とする。すなわち、剰余自乗算前に2で補正を行い、剰余自乗算後の補正値として(式7)
b=(2^(n/(2m)−1))^(2m) (式7)
を満たすbを考える。
【0027】
指数法則により、bは、
b=2^(n−2m) (式8)
となる。したがって、nが2のベキ数でない場合の補正値 a’・b は、
a’・b=2・2^(n−2m)=2^(1+n−2m) (式9)
となる。nが2のベキ数の場合は、n−2m=0であるので、(式9)は(式5)と等しくなる。また、(式7)はb=1となる。
【0028】
N−1をmビット毎に区切った剰余乗算では、(式9)の補正値と指数をmビット毎に区切った値を指数とした2のべき数である2^(e[i])の積である
2^(e[i]+1+n−2m) (式10)
を乗じることになる。e[i]はmビットの値なので、最大値は2m−1となる。この値を(式10)に代入すると、2nとなる。これは、n+1ビット長の値であり、コプロのビット長nを超えてしまう。こうしたビット溢れが生ずるのは、e[i]が最大値である2m−1となる場合のみで、それ以外の場合は、(式10)の値は2n未満となり、nビット以下の値であるので、nビット長のコプロセッサで計算ができる。
【0029】
したがって、e[i]の値が2m−1の場合は、演算数としてR mod Nを用い、e[i]の値が2m−1未満の場合は、演算数として(式10)の2^(e[i]+1+n−2m)を用いる。
【0030】
また、演算の最初のステップでは、あらかじめ被演算数にはR2 mod Nで初期化しておくので、補正値のbの値は不要である。したがって、指数の最上位を処理する最初のステップでは、e[i]+1の値が2nと等しいか否かを判定し、等しい場合は、演算数としてR mod Nを用い、2n未満の場合は、2^(e[i]+1)を用いる。nが2のベキ数でない場合は、e[i]+1は常に2n未満となるので、nが2のベキ数でないことが予めわかっている場合において、最初のe[i]+1が2nと等しいか否かを検査はしなくてもよい。
【0031】
モンゴメリ剰余乗算で計算を行う場合には、最終結果からRを取り除く必要があり、通常、1とのモンゴメリ剰余乗算を行うことで、R−1を乗じ、通常の表現に戻す。
【0032】
本発明では、結果にR2が乗じられているので、最後の2回の剰余乗算で補正を行う。まず、最後から2番目のe[1]を処理する際には、次の剰余乗算の際にR2が乗じられるようにするための補正は不要で、Rのみが残るように、a’・bのうちのbのみの補正値を乗ずればよい。したがって、演算数として、
2^(e[1]+n−2m) (式11)
を乗じる。e[1]+n−2^mの値は、必ず2n未満となるため、2nとの比較は必要ない。この値を乗じた後、m回の自乗演算を行うと、被演算数にはRが乗じられている状態になるので、最後の最下位の指数e[0]を処理する際に、
2^(e[0]) (式12)
を乗じることで、最終結果はモンゴメリ形式ではなく、通常の数値表現になる。以上の手順をアルゴリズム表現すると、以下の如く、
result:=R2 mod N
if e[J−1]+1<2n then
result:=result・2^(e[i]+1)・R−1mod N
else
result:=result・(R mod N)・R−1mod N
end if
for i:=J−2 downTo 2 do
for j:=1 to m do
result:=result2 ・R−1mod N
end for
if e[i]+1+n−2m<2n then
result:=result・2^(e[i]+1+n−2m)・R−1mod N
else
result:=result・(R mod N)・R−1mod N
end if
end for
for j:=1 to m do
result:=result2 ・R−1mod N
end for
result:=result・2^(e[1]+n−2m)・R−1 mod N
for j:=1 to m do
result:=result2 ・R−1mod N
end for
result:=result・2^(e[0])・R−1 mod N
return result
と、表すことができる。
【0033】
また、(式11)で示される演算数はハミングウエイトが1であり、モンゴメリ剰余乗算コプロでは通常下位側から演算が進められるため、演算数のビットが0となっている部分を処理している間は電流地が小さく、ビットが1となっている部分で大きく消費電流が増加する可能性がある。その場合、消費電流を測定して指数の値をある程度推定することが可能となる。そうした問題を解決するために、演算がNを法とする剰余乗算であることと、剰余乗算の後に剰余二乗算が行われることを利用し、演算数には(式11)の値の代わりに、
N ± 2^(e[i]+1+n−2m) (式13)
を使用することができる。しかし、(式13)では加減算によるキャリーが発生し、キャリーの伝版によるディレイや、最上位ビットからのキャリーの発生による桁あふれが発生する可能性がある。そこで、
N xor 2^(e[i]+1+n−2m) (式14)
の形式にすることで、キャリーは発生しなくなる。(式14)はNの(e[i]+1+n−2m)ビット目のビットが1であるか0であるかにより、加減算のいずれかが行われることと等価で、Nの該当ビットが1であった場合は減算、Nの該当ビットが0であった場合は加算が行われる。排他的論理和(xor)演算ではキャリーの伝播が発生せず、キャリーの伝播に伴うディレイもない上、回路も小さくて済む。
【0034】
(式14)による変形を行うと、演算数のハミングウエイトはほぼビット長の半分となり、消費電流を用いたアタック手法に対して、耐タンパ性が強化される。(式14)の変形を導入した手順をアルゴリズム表現すると、
result:=R2 mod N
if e[J−1]+1<2n then
result:=result・(N xor 2^(e[J−1]+1))・R−1mod N
else
result:=result・(R mod N)・R−1mod N
end if
for i:=J−2 downTo 2 do
for j:=1 to m do
result:=result2 ・R−1mod N
end for
if e[i]+1+n−2m<2n then
result:=result・(N xor 2^(e[i]+1+n−2m))・R−1 mod N
else
result:=result・(R mod N)・R−1 mod N
end if
end for
for j:=1 to m do
result:=result2 ・R−1mod N
end for
result:=result・2^(e[1]+n−2m)・R−1 mod N
for j:=1 to m do
result:=result2 ・R−1mod N
end for
result:=result・2^(e[0])・R−1 mod N
return result
と、表すことができる。
【0035】
この手順に従い、モンゴメリ剰余乗算コプロを用いて2を元とするフェルマーテストを高速に実装することができる。
【0036】
同様の手法は、モンゴメリ剰余乗算方式ではない通常表現を用いる剰余乗算コプロセッサを用いる場合でも用いることができる。通常の表現を用いる剰余乗算コプロセッサでは、演算数には補正値がいらないので、次の(式15)
N xor 2^(e[i]) (式15)
の値を演算数に用いる。
【0037】
(式14)であらわされる剰余乗算の演算数の変形は、剰余乗算後に剰余二乗算により負の値の符号が正となることを前提としているので、最下位のmビット分、すなわちe[0]に対しては用いることができない。したがって、e[0]の場合は(式14)の変形は行わない。以上の手順をアルゴリズム表現すると、
result:=N xor 2^(e[J−1])
for i:=J−2 downTo 1 do
for j:=1 to m do
result:=result2 mod N
end for
result:=result・(N xor 2^(e[i])) mod N
end for
for j:=1 to m do
result:=result2 mod N
end for
result:=result・2^(e[0]) mod N
return result
と、表すことができる。
【0038】
以上の手順を用いれば、モンゴメリ型剰余乗算器あるいは剰余乗算器のいずれを用いた場合でも、メモリ容量を消費せずに高速にフェルマーテストを行って素数判定が可能になる。
【発明の効果】
【0039】
本願において開示される発明のうち代表的なものによって得られる効果を簡単に説明すれば下記のとおりである。
【0040】
すなわち、メモリ容量を消費せずに高速にフェルマーテストによって素数判定を行うことができるデータ処理装置を提供することができる。
【発明を実施するための最良の形態】
【0041】
1.実施の形態の概要
先ず、本願において開示される発明の代表的な実施の形態について概要を説明する。代表的な実施の形態についての概要説明で括弧を付して参照する図面中の参照符号はそれが付された構成要素の概念に含まれるものを例示するに過ぎない。
【0042】
〔1〕本発明に係るデータ処理装置(図1、図7、図9、図10、図11)は、モンゴメリ剰余乗算を行うモンゴメリ剰余乗算器を備えたコプロセッサと、プログラムを実行し前記コプロセッサを制御する中央処理装置とを有し、前記中央処理装置の制御によってデータ処理を行なうことにより、外部より与えられた素数候補Nに対して、2(N−1)mod Nを計算してフェルマーテストを実行する。前記データ処理は、
前記素数候補Nを記憶する処理と、
Nのビット長nを記憶する処理と、
log2(n)を超えない最大の整数mを計算して(図9のステップ7010)記憶する処理と、
前記素数候補Nから、N−1を計算し、JをJ≧n/mとなる最小の整数としたときに(図9のステップ7020)、(N−1)を最下位からmビットごとにJ個の区間に区切り、(N−1)=2(J−1)m・e[J−1]+2(J−2)m・e[J−2]+…+2m・e[1]+e[0]なる式を満たすように(N−1)を部分指数e[0],e[1],…,e[J−1]に分割する指数部切り出し処理と (図9のステップ7030)、
前記指数部切り出し処理により切り出されたmビットの値e[i]から2^(e[i]+1+n−2m)を生成する2のベキ乗生成処理と(図9のステップ7060の一部分)、
前記指数部切り出し処理で切り出された部分指数の最上位の値に1を加えたe[J−1]+1が2nと等しい場合は(図9のステップ7050)、R mod N=2n mod Nの演算結果と、R2 mod N=22n mod Nの演算結果との前記素数候補Nを法とするモンゴメリ剰余乗算を行ってその演算結果を第1記憶領域に格納する第1処理と (図9のステップ7070)、
前記e[J−1]+1が2n未満の場合は、前記2のベキ乗生成手段により計算した2^(e[J−1]+1)と、前記R2modN=22n mod Nの演算結果との前記Nを法とするモンゴメリ剰余乗算を行ってその演算結果を前記第1の記憶領域に格納する第2処理と (図9のステップ7060)、
前記第1処理又は前記第2処理のいずれか一方の処理の後に内部の状態変数iをJ−2とする第3処理と(図9のステップ7080)、
前記第3処理の後に、前記素数候補Nを法とし、前記第1記憶領域に記憶された値同士のモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に書き戻す動作をm回繰り返す第4処理と(図10のステップ7090)、
前記第4処理の後に、前記指数部切り出し処理で切り出された部分指数e[i]が2m−1未満の場合は(図10のステップ7100)、前記2のベキ乗生成処理により生成された2^(e[i]+1+n−2m)と前記第1の記憶領域に格納された値との前記Nを法とするモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に格納する第5処理と(図10のステップ7110)、
前記第5処理の後に、前記内部状態変数iから1を引いた値を前記内部状態変数iに格納し(図10のステップ7130)、前記iの値が2以上の場合は前記第4処理に戻り、前記iの値が1以下になるまでそれを繰り返す第6処理と、
前記第6処理の後に、前記素数候補Nを法とし、前記第1記憶領域に記憶された値同士のモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に書き込む動作をm回繰り返す第7処理と(図11のステップ7150)、
前記第7処理の後、前記2のベキ乗生成処理により計算された2^(e[1]+n−2m)と、前記第1記憶領域に格納された値との前記素数候補Nを法とするモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に格納する第8処理と(図11のステップ7160)、
前記第8処理の後、前記モンゴメリ剰余乗算装置により、前記素数候補Nを法とし、前記第1記憶領域に格納された値同士のモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に格納する動作をm回繰り返す第9処理と(図11のステップ7170)、
前記第9処理の後、前記2のベキ乗生成処理により計算された2^(e[0])と、前記第1記憶領域に格納された値との前記素数候補Nを法とするモンゴメリ剰余乗算を行って(図11のステップ7180)、その演算結果をフェルマーテスト結果として出力する第10処理とを含む。
【0043】
〔2〕項1のデータ処理装置において、前記プログラムを格納したメモリを更に有し、1個の半導体基板に形成される。
【0044】
〔3〕別の観点によるデータ処理装置(図4、図7、図12、図13、図14)は、モンゴメリ剰余乗算を行うモンゴメリ剰余乗算器を備えたコプロセッサと、プログラムを実行し前記コプロセッサを制御する中央処理装置とを有し、前記中央処理装置の制御によってデータ処理を行なうことにより、外部より与えられた素数候補Nに対して、2(N−1)mod Nを計算してフェルマーテストを実行する。前記データ処理は、
前記素数候補Nを記憶する処理と、
Nのビット長nを記憶する処理と、
log2(n)を超えない最大の整数mを計算して(図12のステップ7010)記憶する処理と、
前記素数候補Nから、N−1を計算し、JをJ≧n/mとなる最小の整数としたときに(図12のステップ7020)、(N−1)を最下位からmビットごとにJ個の区間に区切り、(N−1)=2(J−1)m・e[J−1]+2(J−2)m・e[J−2]+…+2m・e[1]+e[0]なる式を満たすように(N−1)を部分指数e[0],e[1],…,e[J−1]に分割する指数部切り出し処理と(図12のステップ7030)、
前記指数部切り出し処理により切り出されたmビットの値e[i]から2^(e[i]+1+n−2m)
を生成する2のベキ乗生成処理と、
前記指数部切り出し処理により切り出された部分指数の最上位の値に1を加えたe[J−1]+1が2nと等しい場合は(図12のステップ7050)、R mod N=2n mod Nの演算結果と、R2 mod N=22n mod Nの演算結果との前記素数候補Nを法とするモンゴメリ剰余乗算を行って(図12のステップ7070)、その演算結果を第1記憶領域に格納する第1処理と、
前記e[J−1]+1が2n未満の場合は、前記2のベキ乗生成手段により計算した2^(e[J−1]+1)と前記素数候補Nとの排他的論理和(図4の3032)を取った値と、前記R2 mod N=22n mod Nの演算結果との前記Nを法とするモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に格納する第2処理と(図12のステップ8060)、
前記第1処理又は第2処理のいずれか一方の処理の後に内部の状態変数iをJ−2とする第3処理と (図12のステップ7080)、
前記第3処理の後に、前記素数候補Nを法とし、前記第1記憶領域に格納された値同士のモンゴメリ剰余乗算を行ってその4演算結果を前記第1記憶領域に格納する動作をm回繰り返す第4処理と(図12のステップ7090)、
前記第4処理の後に、前記指数部切り出し処理で切り出された部分指数e[i]が2m−1未満の場合は(図13のステップ7100)、前記2のベキ乗生成処理により生成された2^(e[i]+1+n−2m)と前記素数候補Nとの排他的論理和(図4の3032)が採られた値と、前記第1記憶領域に格納されている値との前記素数候補Nを法とするモンゴメリ剰余乗算を行って(図13のステップ8110)その演算結果を前記第1記憶領域に格納する第5処理と、
前記第4処理の後に、前記指数部切り出し処理で切り出された部分指数e[i]が2m−1と等しい場合は、前記R mod N=2n mod Nと、前記第1記憶領域に格納された値との前記素数候補Nを法とするモンゴメリ剰余乗算を行って(図13のステップ7120)その演算結果を前記第1記憶領域に格納する第6処理と、
前記第5処理又は第6処理のいずれか一方の処理の後に前記内部状態変数iから1を引いた値を前記内部状態変数iに格納し(図13のステップ7130)、前記iの値が2以上の場合は、前記第3処理に戻り(図13のステップ7140)、前記iの値が1以下になるまでそれを繰り返す第7処理と、
前記第7処理の後に前記素数候補Nを法とし、前記第1記憶領域に記憶された値同士のモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に格納する動作をm回繰り返す第8処理と(図14のステップ7150)、
前記第8処理の後、前記2のベキ乗生成処理で生成された2^(e[1]+n−2m)と、前記第1記憶領域に格納された値との前記素数候補Nを法とするモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に格納する第9処理と(図14のステップ7160)、
前記第9処理の後、前記素数候補Nを法とし、前記第1記憶領域に格納された値同士のモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に格納する動作をm回繰り返す第10処理と(図14のステップ7170)、
前記第10処理の後、前記2のベキ乗生成処理により生成された2^(e[0])と前記第1記憶領域に格納された値との前記Nを法とするモンゴメリ剰余乗算を行って(図14のステップ7180)、その演算結果をフェルマーテスト結果として出力する第11処理とを含む。
【0045】
〔4〕項3のデータ処理装置は、前記プログラムを格納したメモリを更に有し、1個の半導体基板に形成される。
【0046】
〔6〕別の観点によるデータ処理装置(図3、図7、図12、図13、図14)は、モンゴメリ剰余乗算を行うモンゴメリ剰余乗算器を備えたコプロセッサと、プログラムを実行し前記コプロセッサを制御する中央処理装置とを有し、前記中央処理装置の制御によってデータ処理を行なうことにより、外部より与えられた素数候補Nに対して、2(N−1)mod Nを計算してフェルマーテストを実行する。前記データ処理は、
前記素数候補Nを記憶する処理と、
Nのビット長nを記憶する処理と、
log2(n)を超えない最大の整数mを計算して(図12のステップ7010)記憶する処理と、
前記素数候補Nから、N−1を計算し、JをJ≧n/mとなる最小の整数としたときに(図12のステップ7020)、(N−1)を最下位からmビットごとにJ個の区間に区切り、(N−1)=2(J−1)m・e[J−1]+2(J−2)m・e[J−2]+…+2m・e[1]+e[0]なる式を満たすように(N−1)を部分指数e[0],e[1],…,e[J−1]に分割する指数部切り出し処理と(図12のステップ7030)、
前記指数部切り出し処理により切り出されたmビットの値e[i]から2^(e[i]+1+n−2m)を生成する2のベキ乗生成処理と、
前記指数部切り出し処理により切り出された部分指数の最上位の値に1を加えたe[J−1]+1が2nと等しい場合は(図12のステップ7050)、R mod N=2n mod Nの演算結果と、R2 mod N=22n mod Nの演算結果との前記素数候補Nを法とするモンゴメリ剰余乗算を行って(図12のステップ7070)その演算結果を第1記憶領域に格納する第1処理と、
前記e[J−1]+1が2n未満の場合は、前記Nのe[J−1]+1ビット目の値を指定ビット反転器(3020)により反転した値と前記R2 mod N=22n mod Nの演算結果との前記素数候補Nを法とするモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に格納する第2処理と(図12のステップ8086)、
前記第1処理又は第2処理のいずれか一方の処理の後に内部の状態変数iをJ−2とする第3処理と(図12のステップ7080)、
前記第3処理の後に、前記素数候補Nを法とし、前記第1記憶領域に記憶された値同士のモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に格納する動作をm回繰り返す第4処理と (図13のステップ7090)、
前記第4処理の後に、前記指数部切り出し処理によって切り出された部分指数e[i]が2m−1未満の場合は(図13のステップ7100)、前記Nのe[i]+1+n−2mビット目の値を前記指定ビット反転器(3020)により反転した値と前記第1記憶領域に格納された値との前記素数候補Nを法とするモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に記憶する第5処理と (図13のステップ8110)、
前記第4処理の後に、前記指数部切り出し処理によって切り出された部分指数e[i]が2m−1と等しい場合は、前記R mod N=2n mod Nの演算結果と前記第1記憶領域に格納された値との前記素数候補Nを法とするモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に格納する第6処理と(図13のステップ7120)、
前記第5処理又は第6処理のいずれか一方の処理の後に、前記内部状態変数iから1を引いた値を前記内部状態変数iに格納し(図13のステップ7130)、前記iの値が2以上の場合は、前記第3処理に戻り(図13のステップ7140)、前記iの値が1以下になるまでそれを繰り返す第7処理と、
前記第7処理の後に、前記素数候補Nを法とし、前記第1記憶領域に記憶された値同士のモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に格納する動作をm回繰り返す第8処理と(図14のステップ7150)、
前記第8処理の後、前記2のベキ乗生成手段により計算した2^(e[1]+n−2m)と前記第1記憶領域に格納された値との前記素数候補Nを法とするモンゴメリ剰余乗算をおこなってその演算結果を前記第1記憶領域に格納する第9処理と(図14のステップ7160)、
前記第9処理の後、前記素数候補Nを法とし、前記第1記憶領域に記憶された値同士のモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に格納する動作をm回繰り返す第10処理と(図14のステップ7170)、
前記第10処理の後、前記2のベキ乗生成処理により生成された2^(e[0])と、前記第1記憶領域に格納された値との前記素数候補Nを法とするモンゴメリ剰余乗算を行って(図14のステップ7180)その演算結果をフェルマーテスト結果として出力する第11処理とを含む、データ処理装置。
【0047】
〔6〕項5のデータ処理装置は、前記プログラムを格納したメモリを更に有し、1個の半導体基板に形成される。
【0048】
2.実施の形態の詳細
実施の形態について更に詳述する。以下、本発明を実施するための形態を図面に基づいて詳細に説明する。なお、発明を実施するための形態を説明するための全図において、同一の機能を有する要素には同一の符号を付して、その繰り返しの説明を省略する。
【0049】
<<第1の実施形態>>
図1はフェルマーテストを実行する本発明に係るデータ処理装置1を機能ブロックダイヤグラムで示すものであり、図9、図10及び図11に示される本発明によるフェルマーテスト高速演算手順を実現する。データ処理装置1は、図7に例示されるモンゴメリ剰余乗算器(6050)及び演算レジスタ(6060,6070,6080)等を備えたモンゴメリ乗算コプロセッサ(6040)と共に、プログラムを実行してモンゴメリ乗算コプロセッサ6040等を制御する中央処理装置(6010)とメモリ(6020)等を有し、相互にバス6030で接続される。メモリ(6020)はプログラム(PGM)を格納する電気的に書換え可能な不揮発性メモリと、変数やデータ(DAT)等の格納に利用されるSRAM等のランダムアクセスメモリから成る。このデータ処理装置1は例えば、図17に示されるような1個の半導体基板に形成されたICカード用マイクロコンピュータ107として実現される。図17ではICカード用マイクロコンピュータ107はICカード基板108に搭載されている。ICカード用マイクロコンピュータ107は、プログラムや重要な情報がオンチップのメモリに格納されており、外部からそれらの情報に直接アクセスすることができない。ようになっている。外部との通信は、I/Oピン(106)のみを介して、完全にICカードチップの制御下で行われ、通常情報は暗号化した状態で送受信され、情報の秘匿性が実現されている。暗号通信を行うためには、通信する相手と暗号鍵の共有を行う必要がある。事前に鍵を通信相手と共有しておく方法もあるが、一度鍵が判明してしまうと、暗号化した通信内容が復号化されてしまう。そこで、通信に用いる暗号鍵をランダムに生成し、相手に鍵を送信し、その鍵を用いて通信するという方法が一般的に用いられている。外部インタフェース端子として、Vccピン101、リセットピン102、クロック入力ピン103、グランドピン104、不揮発メモリプログラム用電源ピン105、及びI/Oピン106を有する。
【0050】
ICカード用マイクロコンピュータ107はオンチップのメモリ等の限られた演算リソースを用いて暗号通信に使用する暗号鍵を生成する機能を備える。暗号鍵にはビット数の多い素数を用いることになり、その素数性を判定する演算処理の第1の例について説明する。
【0051】
図1において法レジスタN(1000)は外部より素数候補Nを入力して格納し、ビットnレジスタ(1010)は、外部より素数候補Nのビット数nを入力して格納する。log2(n)を超えない最大の整数を与えるlog2計算装置(1030)により、log2(n)を超えない最大の整数mが得られる。1030の出力する値の種類は、log2(nの最大値)であるので、実際には計算を行わずにテーブル引きや、nの非零のビットのうちの最上位のビットの位置から求めることができる。たとえば、
n0:=n
m:=0
while n0>1
m:=m+1
n0:=n0>>1
end while
としてもよい。この処理は、図9の7010のステップに相当する。1030で求められたmはmを格納するレジスタ(1020)に格納される。整数除算器(1040)により、n/mの小数点以下を切り上げた値が求められ、セレクタ(1050)により1040の出力が選択され、カウンタi(1060)にセットされる。この処理は、図9のステップ7020に相当する。カウンタiは、mビットごとに分割された(N−1)の何番目の部分ビットを取り出すのかを指定するために用いられる。一方、演算器(1100)により、R2 mod N=22n mod Nが計算され、結果レジスタ(1160)に格納される。図1においてその格納パスは図示が省略されている。この処理は図9のステップ7040に相当する。図9の“result”は前記結果レジスタ’1160)を意味する。つぎに、R mod N=2n mod Nが計算され、レジスタ(1110)に格納される。この処理は、図9のステップ7070で用いるRmodNの準備に相当する。iの値にしたがって、指数切り出し部(1080)により、(N−1)の最上位が切り出され、演算数生成装置(1090)により、2^(e[i]+1)が生成される。つぎに、mビット長の値すべてのビットが1である値を生成する2m−1生成器(1120)の値と1090により切り出された指数との比較が比較器(1130)により行われ、等しい場合はセレクタ(1140)はレジスタ(1110)を選択し、そうでない場合は演算数生成装置(1090)の出力が選択される。モンゴメリ剰余乗算器(1150)により、結果レジスタ(1160)の値とセレクタ(1140)に選択された値とのモンゴメリ剰余乗算が行われ、結果レジスタ(1160)に格納される。この処理は、図9のステップ7050、7060,7070に相当する。減算器(1070)により、カウンタi(1060)の値はデクリメントされ、デクリメントされた結果がセレクタ(1050)に選択され、カウンタi(1070)が更新される。この処理は図9のステップ7080に相当する。
【0052】
モンゴメリ剰余乗算演算モード制御部(1200)は次にモンゴメリ剰余乗算器(1150)の演算モードを二乗算に変更し、セレクタ(1170)を介してカウンタj(1180)を初期化する。モンゴメリ剰余乗算演算モード制御部は(1200)は、カウンタj(1180)を減算器(1190)で1回デクリメントする毎に、モンゴメリ剰余乗算器(1150)を用いて、結果レジスタ(1160)の値をモンゴメリ剰余二乗算し結果レジスタ(1160)に格納する処理を、カウンタj(1180)がゼロになるまで行う。これは、図10のステップ7090に相当する。つぎに、カウンタi(1060)の値にしたがって、指数切り出し部(1080)により、(N−1)の部分ビットが切り出され、比較器(1130)により2m−1と比較される。比較結果により、セレクタ(1140)により、演算数生成装置(1090)の出力かR mod Nを格納したレジスタ(1110)が選択され、結果レジスタ(1160)の値と剰余乗算が行われる。これは、図10のステップ7100,7110,7120の処理に相当する。剰余乗算が終了したら、カウンタi(1060)の値を演算器(1070)によりデクリメントし、カウンタi(1060)の値が1以上の場合は、図9のステップ7090に相当する処理から繰り返す。
【0053】
カウンタi(1060)の値が1の場合は、モンゴメリ剰余乗算器(1150)の演算モードを二乗算に変更し、セレクタ(1170)を介してカウンタj(1180)を初期化する。モンゴメリ剰余乗算演算モード制御部は(1200)は、カウンタj(1180)を減算器(1190)で1回デクリメントする毎に、モンゴメリ剰余乗算器(1150)を用いて、結果レジスタ(1160)の値をモンゴメリ剰余二乗算し結果レジスタ(1160)に格納する処理を、カウンタj(1180)がゼロになるまで行う。これは、図11のステップ7150に相当する。
【0054】
つぎに、カウンタi(1060)の値にしたがって、指数切り出し部(1080)により、(N−1)の最下位から2番目のmビットが取り出される。カウンタi(1060)が1の場合は、演算数生成装置(1090)を常に選択し、結果レジスタ(1160)の値と剰余乗算が行われる。これは、図11のステップ7160の処理に相当する。剰余乗算が終了したら、カウンタi(1060)の値が演算器(1070)によりデクリメントされ、カウンタi(1060)に設定される。
【0055】
モンゴメリ剰余乗算器(1150)の演算モードが二乗算に変更され、セレクタ(1170)を介してカウンタj(1180)が初期化される。モンゴメリ剰余乗算演算モード制御部は(1200)は、カウンタj(1180)を減算器(1190)で1回デクリメントする毎に、モンゴメリ剰余乗算器(1150)を用いて、結果レジスタ(1160)の値をモンゴメリ剰余二乗算し結果レジスタ(1160)に格納する処理を、カウンタj(1180)がゼロになるまで行う。これは、図11のステップ7170に相当する。
【0056】
最後に、カウンタi(1060)の値にしたがって、指数切り出し部(1080)により、(N−1)の最下位のmビットを取り出す。カウンタi(1060)が0の場合は、演算数生成装置(1090)を常に選択し、結果レジスタ(1160)の値と剰余乗算が行われる。これは、図11のステップ7180の処理に相当する。剰余乗算が終了したら、結果レジスタ(1160)に2^(N−1)mod Nの値が格納され、処理が終了する。
【0057】
図2はR2mod Nを計算する演算器(1100)の詳細を示す。演算器(1100)は、法N(1000)およびビット長n(1010)が入力されると、演算器(2010)により、2RmodNが計算される。ここで、2R=2n+1である。nビット目が1になるまでNが左ビットシフトされ、2n+1から左シフトしされたNの値が減算されて2RmodNレジスタ(2020)に格納すされる。Nは素数候補であるから奇数であるので、必ずn−1ビット目以下にゼロでないビットを含む。したがって、Nを左シフトした値は2nよりも大きな値となるので、2n+1から左シフトしたNの値を減算した結果は、2nよりも小さな値となる。2RmodN(2020)に格納される値は、2n未満であれば、正確にmodNを求めなくとも良い。
【0058】
2SmodNレジスタ(2060)には、2n−N=Rを代入しておく。Rはモンゴメリ剰余乗算では1と等価である。2RmodNレジスタ(2020)に格納されている値は、2tRmodNと表記するとt=1に相当する。モンゴメリ剰余乗算器を用いて、モンゴメリ剰余二乗算を1回行うと、tが倍となる。モンゴメリ剰余二乗算を行った後は、結果は演算数レジスタ(2030)に格納される。R2modNは、2nRmodNと等しいので、R2modNを計算するには、モンゴメリ剰余二乗算を行い、tの値が変わるたびに、tとnの値の論理積(AND)を採り、ゼロでない場合は、演算数(2030)と2SmodNレジスタ(2060)を入力とし、モンゴメリ剰余乗算器(2050)で剰余乗算を行い、結果を2SmodNレジスタ(2060)に格納するという処理を行う。次に、ふたたび演算数レジスタ(2030)の値をモンゴメリ剰余二乗算する処理を行い、tとnの値のANDをとり、ゼロでない場合は、演算数(2030)と2SmodNレジスタ(2060)を入力とし、モンゴメリ剰余乗算器(2050)剰余乗算を行い、結果を2SmodNレジスタ(2060)に格納するという処理を、2t>nとなるまで繰り返す。この処理が終了すると、2SmodNレジスタ(2060)にはR2modNが格納される。
【0059】
<<第2の実施形態>>
図3はフェルマーテストを実行する本発明に係るデータ処理装置2を機能ブロックダイヤグラムで示すものであり、図12、図13及び図14に示される本発明によるフェルマーテスト高速演算手順を実現する。データ処理装置1は図7で説明したのと同様にモンゴメリ剰余乗算器(6050)及び演算レジスタ(6060,6070,6080)等を備えたモンゴメリ乗算コプロセッサ(6040)と共に、プログラムを実行してモンゴメリ乗算コプロセッサ6040等を制御する中央処理装置(6010)とメモリ(6020)等を有し、例えば図17に例示されるようなICカード用マイクロコンピュータ107として実現される。データ処理装置2で構成されたICカード用マイクロコンピュータ107はオンチップのメモリ等の限られた演算リソースを用いて暗号通信に使用する暗号鍵を生成する機能を備え、暗号鍵と種いて用いる乱数の素数性を判定する演算処理の第2の例について説明する。
【0060】
図3において、法レジスタN(1000)は外部より素数候補Nを入力し、格納し、法ビットnレジスタ(1010)は、外部より素数候補のビット数nを入力し、格納する。log2(n)を超えない最大の整数を与えるlog2計算装置(1030)により、log2(n)を超えない最大の整数mが得られる。この処理は、図12の7010のステップに相当する。1030で求められたmはmを格納するレジスタ(1020)に格納される。整数除算器(1040)により、n/mの少数点以下を切り上げた値が求められ、セレクタ(1050)により1040の出力が選択され、カウンタi(1060)にセットされる。この処理は、図12のステップ7020に相当する。カウンタiは、mビットごとに分割された(N−1)の何番目の部分ビットを取り出すのかを指定するために用いられる。一方、演算器(1100)により、R2modN=22nmodNが計算され、結果レジスタ(1160)に格納される。図3においてその格納パスは図示が省略されている。この処理は図12のステップ7040に相当する。つぎに、RmodN=2nmodNが計算され、レジスタ(1110)に格納される。この処理は、図12のステップ7070で用いるRmodNの準備を行うことに相当する。iの値にしたがって、指数切り出し部(1080)により、(N−1)の最上位e[J−1]が切り出され、セレクタ(3010)によりNが選択され、指定ビット反転器(3020)により、e[J−1]+1ビット目が反転され、演算数発生装置(1090)に格納される。指定ビット反転器(3020)ではe[J−1]+1がn以上の場合は、どのビットも反転されない。つぎに、mビット長の値すべてのビットが1である値を生成する2m−1生成器(1120)の値と1090により切り出された指数との比較が比較器(1130)により比較され、等しい場合はセレクタ(1140)がレジスタ(1110)を選択し、そうでない場合は演算数生成装置(1090)の出力が選択される。モンゴメリ剰余乗算器(1150)により、結果レジスタ(1160)の値とセレクタ(1140)に選択された値とのモンゴメリ剰余乗算が行われ、その演算結果が結果レジスタ(1160)に格納される。この処理は、図12のステップ7050、8060,7070に相当する。減算器(1070)により、カウンタi(1060)の値はデクリメントされ、デクリメントされた結果がセレクタ(1050)に選択され、カウンタi(1070)が更新される。この処理は図12のステップ7080に相当する。
【0061】
モンゴメリ剰余乗算演算モード制御部(1200)は次にモンゴメリ剰余乗算器(1150)の演算モードを二乗算に変更し、セレクタ(1170)を介してカウンタj(1180)を初期化する。モンゴメリ剰余乗算演算モード制御部は(1200)は、カウンタj(1180)を減算器(1190)で1回デクリメントする毎に、モンゴメリ剰余乗算器(1150)を用いて、結果レジスタ(1160)の値をモンゴメリ剰余二乗算し結果レジスタ(1160)に格納する処理を、カウンタj(1180)がゼロになるまで行う。これは、図13のステップ7090に相当する。つぎに、カウンタi(1060)の値にしたがって、指数切り出し部(1080)により、(N−1)の部分ビットe[i]が切り出される。セレクタ(3010)によりNが選択され、指定ビット反転器(3020)により、e[i]+1+n−2mビット目が反転され、演算数発生装置(1090)に格納される。指定ビット反転器(3020)ではe[i]+1+n−2mがn以上の場合は、どのビットも反転されない。指数切り出し部(1080)により切り出された値は比較器(1130)により2m−1と比較される。比較結果に基づいて、セレクタ(1140)により、演算数生成装置(1090)の出力又はR mod Nを格納したレジスタ(1110)が選択され、選択された値が結果レジスタ(1160)の値と剰余乗算が行われる。これは、図13のステップ7100,8110,7120の処理に相当する。剰余乗算が終了したら、カウンタi(1060)の値が演算器(1070)によりデクリメントされ、カウンタi(1060)の値が1以上の場合は、図13のステップ7090に相当する処理から繰り返される。
【0062】
カウンタi(1060)の値が1の場合は、モンゴメリ剰余乗算器(1150)の演算モードが二乗算に変更され、セレクタ(1170)を介してカウンタj(1180)が初期化される。モンゴメリ剰余乗算演算モード制御部は(1200)は、カウンタj(1180)を減算器(1190)で1回デクリメントする毎に、モンゴメリ剰余乗算器(1150)を用いて、結果レジスタ(1160)の値をモンゴメリ剰余二乗算してその演算結果を結果レジスタ(1160)に格納する処理を、カウンタj(1180)がゼロになるまで行う。これは、図14のステップ7150に相当する。
【0063】
つぎに、カウンタi(1060)の値にしたがって、指数切り出し部(1080)により、(N−1)の最下位から2番目のmビットが取り出される。カウンタi(1060)が1の場合は、セレクタ(3010)により0が選択され、指定ビット反転器(3020)により、e[1]+n−2mビット目が反転した値、すなわちe[1]+n−2mビット目がセットされた値が演算数生成装置(1090)に格納され、結果レジスタ(1160)の値と剰余乗算が行われる。これは、図14のステップ7160の処理に相当する。剰余乗算が終了したら、カウンタi(1060)の値を演算器(1070)によりデクリメントし、カウンタi(1060)に設定する。
【0064】
続いてモンゴメリ剰余乗算器(1150)の演算モードが二乗算に変更され、セレクタ(1170)を介してカウンタj(1180)が初期化される。モンゴメリ剰余乗算演算モード制御部は(1200)は、カウンタj(1180)を減算器(1190)で1回デクリメントする毎に、モンゴメリ剰余乗算器(1150)を用いて、結果レジスタ(1160)の値をモンゴメリ剰余二乗算し結果レジスタ(1160)に格納する処理を、カウンタj(1180)がゼロになるまで行う。これは、図14のステップ7170に相当する。
【0065】
最後に、カウンタi(1060)の値にしたがって、指数切り出し部(1080)により、(N−1)の最下位のmビットを取り出す。カウンタi(1060)が0の場合は、セレクタ(3010)により0が選択され、指定ビット反転器(3020)により、e[0]ビット目が反転した値、すなわちe[0]ビット目がセットされた値が演算数生成装置(1090)に格納され、その演算数生成装置(1090)が常に選択されて、結果レジスタ(1160)の値と剰余乗算が行われる。これは、図14のステップ7180の処理に相当する。剰余乗算が終了したら、結果レジスタ(1160)に2^(N−1)mod Nの値が格納され、処理が終了する。
【0066】
<<第3の実施形態>>
図4はフェルマーテストを実行する本発明に係るデータ処理装置3を機能ブロックダイヤグラムで示すものであり、図12、図13及び図14に示される本発明によるフェルマーテスト高速演算手順を実現する。図3のデータ処理装置2では指定ビット反転器(3020)を用いたが、図4ではそれに代えて2のベキ数演算器(3031)と排他的論理和回路(3032)を用いた点が相違され、その他の構成については同じ参照符号を付してその詳細な説明を省略する。2のベキ数演算器(3031)は指数切り出し部(1080)で切り出された指数を2のベキ乗に形態にする。排他的論理和回路(3032)は2のべき乗演算器(3031)の出力とセレクタ(3010)の出力に対して排他的論理和を採る。その演算結果は図3の指定ビット反転器(3020)の出力と同じである。
【0067】
<<第4の実施形態>>
図5はフェルマーテストを実行する本発明に係るデータ処理装置4を機能ブロックダイヤグラムで示すものであり、図15に示されるフェルマーテスト高速演算手順を実現する。この例ではモンゴメリ剰余乗算装置を用いない。データ処理装置4は、図8に例示される剰余乗算器(6150)及び演算レジスタ(6160,6170,6180)等を備えた剰余乗算コプロセッサ(6140)と共に、プログラムを実行して剰余乗算コプロセッサ6140等を制御する中央処理装置(6010)とメモリ(6020)等を有し、相互にバス6030で接続される。メモリ(6020)はプログラム(PGM)を格納する電気的に書換え可能な不揮発性メモリと、変数やデータ(DAT)等の格納に利用されるSRAM等のランダムアクセスメモリから成る。このデータ処理装置4は例えば、前記図17に示されるような1個の半導体基板に形成されたICカード用マイクロコンピュータ107として実現される。
【0068】
図5において、法レジスタN(1000)には外部より素数候補Nが入力されて格納され、法ビットnレジスタ(1010)には外部より素数候補Nのビット数nが入力されて格納される。log2(n)を超えない最大の整数を与えるlog2計算装置(1030)により、log2(n)を超えない最大の整数mが得られる。1030の出力する値の種類は、log2(nの最大値)であるので、実際には計算を行わずにテーブル引きや、nの非零のビットのうちの最上位のビットの位置から求めることができる。この処理は、図15の9010のステップに相当する。log2計算装置(1030)で求められた値mはレジスタ(1020)に格納される。整数除算器(1040)により、n/mの少数点以下を切り上げた値が求められ、セレクタ(1050)により1040の出力が選択され、カウンタi(1060)にセットされる。この処理は、図15のステップ9020に相当する。カウンタiは、mビットごとに分割された(N−1)の何番目の部分ビットを取り出すのかを指定するために用いられる。iの値にしたがって、指数切り出し部(1080)により、(N−1)の最上位が切り出され、演算数生成装置(1090)により、2^(e[J−1])が生成される。最初は剰余乗算器(4010)で乗算を行わずに、演算数生成装置(1090)の値をそのまま結果レジスタ(4020)に格納する。この処理は、図15のステップ9040に相当する。減算器(1070)により、カウンタi(1060)の値はデクリメントされ、デクリメントされた結果がセレクタ(1050)に選択され、これによってカウンタi(1070)が更新される。この処理は図15のステップ9050に相当する。
【0069】
剰余乗算演算モード制御部(4030)は次に剰余乗算器(4010)の演算モードを二乗算に変更し、セレクタ(1170)を介してカウンタj(1180)を初期化する。剰余乗算演算モード制御部(4030)は、カウンタj(1180)を減算器(1190)で1回デクリメントする毎に、剰余乗算器(4010)を用いて、結果レジスタ(4020)の値を剰余二乗算して結果レジスタ(4020)に格納する処理を、カウンタj(1180)がゼロになるまで行う。これは、図15のステップ9060に相当する。つぎに、カウンタi(1060)の値にしたがって、指数切り出し部(1080)により、(N−1)の部分ビットが切り出され、演算数生成装置(1090)の出力と、結果レジスタ(4020)の値との剰余乗算が行われる。これは、図15のステップ9070の処理に相当する。剰余乗算が終了したら、カウンタi(1060)の値が演算器(1070)によりデクリメントされ、カウンタi(1060)の値が0以上の場合は、図15のステップ9060に相当する処理から繰り返される。
【0070】
カウンタi(1060)の値が0の場合は、結果レジスタ(4020)に2^(N−1)mod Nの値が格納され、処理が終了する。
【0071】
<<第5の実施形態>>
図6はフェルマーテストを実行する本発明に係るデータ処理装置5を機能ブロックダイヤグラムで示すものであり、図16に示されるフェルマーテスト高速演算手順を実現する。この例ではモンゴメリ剰余乗算装置を用いない。データ処理装置4は、前記図8に例示される剰余乗算器(6150)及び演算レジスタ(6160,6170,6180)等を備えた剰余乗算コプロセッサ(6140)と共に、プログラムを実行して剰余乗算コプロセッサ6140等を制御する中央処理装置(6010)とメモリ(6020)等を有し、相互にバス6030で接続される。このデータ処理装置5は例えば、前記図17に示されるような1個の半導体基板に形成されたICカード用マイクロコンピュータ107として実現される。
【0072】
図6において、法レジスタN(1000)は外部より素数候補Nを入力して格納し、法ビットnレジスタ(1010)は、外部より素数候補のビット数nを入力して格納する。log2(n)を超えない最大の整数を与えるlog2計算装置(1030)により、log2(n)を超えない最大の整数mが得られる。1030の出力する値の種類は、log2(nの最大値)であるので、実際には計算を行わずにテーブル引きや、nの非零のビットのうちの最上位のビットの位置から求めることができる。この処理は、図16の9010のステップに相当する。1030で求められた値mはレジスタ(1020)に格納される。整数除算器(1040)により、n/mの少数点以下を切り上げた値が求められ、セレクタ(1050)により1040の出力が選択され、カウンタi(1060)にセットされる。この処理は、図16のステップ9020に相当する。カウンタiは、mビットごとに分割された(N−1)の何番目の部分ビットを取り出すのかを指定するために用いられる。iの値にしたがって、指数切り出し部(1080)により、(N−1)の最上位(e[J−1])が切り出され、セレクタ(3010)が0を選択し、指定ビット反転器(3020)が(e[J−1])ビット目を反転することにより、2^(e[J−1])が演算数生成装置(1090)にセットされる。一番最初は剰余乗算器(4010)で乗算を行わずに、演算数生成装置(1090)の値をそのまま結果レジスタ(4020)に格納する。この処理は、図16のステップ9040に相当する。減算器(1070)により、カウンタi(1060)の値はデクリメントされ、デクリメントされた結果がセレクタ(1050)に選択され、カウンタi(1070)が更新される。この処理は図16のステップ9050に相当する。
【0073】
剰余乗算演算モード制御部(4030)は次に剰余乗算器(4010)の演算モードを二乗算に変更し、セレクタ(1170)を介してカウンタj(1180)を初期化する。剰余乗算演算モード制御部(4030)は、カウンタj(1180)を減算器(1190)で1回デクリメントする毎に、剰余乗算器(4010)を用いて、結果レジスタ(4020)の値を剰余二乗算し結果レジスタ(4020)に格納する処理を、カウンタj(1180)がゼロになるまで行う。これは、図15のステップ9060に相当する。つぎに、カウンタi(1060)の値にしたがって、指数切り出し部(1080)により、(N−1)の部分ビット(e[i])が切り出され、セレクタ(3010)がNを選択し、指定ビット反転器(3020)が(e[i])ビット目を反転することにより、N xor 2^(e[i])が演算数生成装置(1090)にセットされる。演算数生成装置(1090)の出力と結果レジスタ(4020)の値との剰余乗算が行われ、演算結果が結果レジスタ(4020)に格納される。これは、図16のステップ10070の処理に相当する。剰余乗算が終了したら、カウンタi(1060)の値が演算器(1070)によりデクリメントされ、カウンタi(1060)の値が1以上の場合は、図16のステップ9060に相当する処理から繰り返される。
【0074】
カウンタi(1060)の値が0の場合は、指数切り出し部(1080)により、(N−1)の最下位の部分ビット(e[0])が切り出され、セレクタ(3010)が0を選択し、指定ビット反転器(3020)が(e[i])ビット目を反転することにより、2^(e[0])が演算数生成装置(1090)にセットされる。演算数生成装置(1090)の出力と結果レジスタ(4020)の値との剰余乗算が行われ、演算結果が結果レジスタ(4020)に格納される。結果レジスタ(4020)には2^(N−1)mod Nの値が格納されるので、処理が終了する。
【0075】
以上本発明者によってなされた発明を実施形態に基づいて具体的に説明したが、本発明はそれに限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能であることは言うまでもない。本発明の好適な例はICカード用マイクロコンピュータであるが、オンチップされる回路モジュールは上記説明に限定されず、その他の回路モジュールが追加されてもよい。また、ICカード用マイクロコンピュータはセキュリティ評価基準のISO/IEC15408の評価・認証機関によって認証済みであることに限定されない。
【図面の簡単な説明】
【0076】
【図1】図1は第1の実施形態に係るデータ処理装置を例示する機能ブロックダイヤグラムである。
【図2】図2は第1の実施形態で用いられるR2modNを演算する演算器の一例を示すブロックダイヤグラムである。
【図3】図3は第2の実施形態に係るデータ処理装置を例示する機能ブロックダイヤグラムである。
【図4】図4は第3の実施形態に係るデータ処理装置を例示する機能ブロックダイヤグラムである。
【図5】図5は第4の実施形態に係るデータ処理装置を例示する機能ブロックダイヤグラムである。
【図6】図6は第5の実施形態に係るデータ処理装置を例示する機能ブロックダイヤグラムである。
【図7】図7は第1又は第2の実施形態に係るデータ処理装置のハードウェア構成を例示するブロックダイヤグラムである。
【図8】図8は第3又は第4の実施形態に係るデータ処理装置のハードウェア構成を例示するブロックダイヤグラムである。
【図9】図9は第1および第2の実施形態に係るデータ処理装置による処理手順を例示するフローチャートである。
【図10】図10は図9の続きを示すフローチャートである。
【図11】図11は図10の続きを示すフローチャートである。
【図12】図12は第3の実施形態に係るデータ処理装置による処理手順を例示するフローチャートである。
【図13】図13は図12の続きを示すフローチャートである。
【図14】図14は図13の続きを示すフローチャートである。
【図15】図15は第4の実施形態に係るデータ処理装置による処理手順を例示するフローチャートである。
【図16】図16は第5の実施形態に係るデータ処理装置による処理手順を例示するフローチャートである。
【図17】図17はICカードの構成を例示する外観図である。
【符号の説明】
【0077】
107:ICカード用チップ
1000:法Nを格納するレジスタ
1010:法Nのビット長を格納するレジスタ
1020:指数を切り出すビット長mを格納するレジスタ
1030:入力された値のlog2を超えない最大の整数を与えるlog2計算装置
1040:整数除算器
1050:整数除算器と減算器の出力を選択するセレクタ
1060:カウンタiを格納するレジスタ
1070:減算器
1080:N−1をmビット毎に区切り、下位側からi番目の値を出力する指数切り出し部
1090:入力値のビット位置のみを1としその他のビットを0とする演算数を生成する演算数生成装置
1100:R mod NもしくはR2modNを計算する演算器
1110:演算器が計算したRもしくはR2を格納するレジスタ
1120:mビット長の値すべてのビットが1である値を生成する2m−1生成器
1130:比較器
1150:モンゴメリ剰余乗算器
1160:剰余乗算の結果を格納する結果レジスタ
1180:カウンタ値jを格納するレジスタ
1190:減算器
1200:モンゴメリ剰余乗算モード制御装置
2010:法Nと法Nのビット長Nから、2n+1modNを計算する演算器
2020:2n+1modNをか苦悩するレジスタ
2030:演算途中の値を格納する演算数レジスタ
2060:モンゴメリ剰余乗算器
3020:指定されたビットのみを反転して出力する指定ビット反転器
3032:排他的論理和回路
4010:剰余乗算器
4020:結果を格納するレジスタ
4030:剰余乗算器の演算モードを制御する制御装置
6010:CPU
6020:メモリ
6030:バス
6040:剰余乗算コプロセッサ
6050:モンゴメリ剰余乗算器
6060:演算数を格納するレジスタ
6070:演算数を格納するレジスタ
6080:法Nを格納するレジスタ
6140:剰余乗算コプロセッサ
6150:剰余乗算器
6160:演算数を格納するレジスタ
6170:演算数を格納するレジスタ
6180:法Nを格納するレジスタ
7010:log2(n)を超えない最大の整数をmに代入するステップ
7020:n/mの少数点以下を切り上げた値をJに代入するステップ
7030:N−1をmビットごとに区切りe[0]…e[J−1]に代入するステップ
7040:R2modNをresultに代入するステップ
7050:e[J−1]+1がnと等しいか条件判定するステップ
7060:最上位の指数が2m−1未満の場合に最上位の指数に相当する演算数を剰余乗算するステップ
7070:最上位の指数が2m−1と等しい場合に最上位の指数に相当する演算数を剰余乗算するステップ
7080:カウンタiにJ−2を代入するステップ
7090:resultをm回剰余二乗算してresultに代入するステップ
7100:e[i]+n−2mがnと等しいか条件判断するステップ
7110:e[i]+n−2mがn未満のときi番目のmビットの指数に相当する演算数を剰余乗算するステップ
7120:e[i]+n−2mがnと等しいときi番目のmビットの指数に相当する演算数を剰余乗算するステップ
7130:カウンタiの値を1だけ減算するステップ
7140:iが1より大きいか条件判断し条件分岐するステップ
7150:resultをm回剰余二乗算してresultに代入するステップ
7160:最下位の1つ前のmビットの指数に相当する演算数を剰余乗算するステップ
7170:resultをm回剰余二乗算してresultに代入するステップ
7180:最下位の1つ前のmビットの指数に相当する演算数を剰余乗算するステップ
7190:結果を出力するステップ
8060:最上位の指数が2m−1未満の場合に最上位の指数に相当する演算数を法Nでマスクしながら剰余乗算するステップ
8110:e[i]+n−2mがn未満の場合にi番目のmビットの指数に相当する演算数を法Nでマスクしながら剰余乗算するステップ
9010:log2(n)を超えない最大の整数をmに代入するステップ
9020:n/mの少数点以下を切り上げた値をJに代入するステップ
9030:N−1をmビットごとに区切りe[0]…e[J−1]に代入するステップ
9040:最上位の指数に相当する演算数をresultに代入するステップ
9050はカウンタiにJ−2を代入するステップ
9060:resultをm回剰余二乗算してresultに代入するステップ
9070:i番目のmビットの指数に相当する演算数を剰余乗算するステップ
9080:カウンタiの値を1だけ減算するステップ
9090:カウンタiが0以上かを判定し条件分岐するステップ
9100:結果を出力するステップ
10070:i番目のmビットの指数に相当する演算数を法Nでマスクしながら剰余乗算するステップ
10090:カウンタiが1以上かを判定し条件分岐するステップ
10100:最下位のmビットの指数に相当する演算数を剰余乗算するステップ
【特許請求の範囲】
【請求項1】
モンゴメリ剰余乗算を行うモンゴメリ剰余乗算器を備えたコプロセッサと、プログラムを実行し前記コプロセッサを制御する中央処理装置とを有し、前記中央処理装置の制御によってデータ処理を行なうことにより、外部より与えられた素数候補Nに対して、2(N−1)mod Nを計算してフェルマーテストを実行するデータ処理装置であって、前記データ処理は、
前記素数候補Nを記憶する処理と、
Nのビット長nを記憶する処理と、
log2(n)を超えない最大の整数mを計算して記憶する処理と、
前記素数候補Nから、N−1を計算し、JをJ≧n/mとなる最小の整数としたときに、(N−1)を最下位からmビットごとにJ個の区間に区切り、(N−1)=2(J−1)m・e[J−1]+2(J−2)m・e[J−2]+…+2m・e[1]+e[0]なる式を満たすように(N−1)を部分指数e[0],e[1],…,e[J−1]に分割する指数部切り出し処理と、
前記指数部切り出し処理により切り出されたmビットの値e[i]から2^(e[i]+1+n−2m)を生成する2のベキ乗生成処理と、
前記指数部切り出し処理で切り出された部分指数の最上位の値に1を加えたe[J−1]+1が2nと等しい場合は、R mod N=2n mod Nの演算結果と、R2 mod N=22n mod Nの演算結果との前記素数候補Nを法とするモンゴメリ剰余乗算を行ってその演算結果を第1記憶領域に格納する第1処理と、
前記e[J−1]+1が2n未満の場合は、前記2のベキ乗生成手段により計算した2^(e[J−1]+1)と、前記R2modN=22n mod Nの演算結果との前記Nを法とするモンゴメリ剰余乗算を行ってその演算結果を前記第1の記憶領域に格納する第2処理と、
前記第1処理又は前記第2処理のいずれか一方の処理の後に内部の状態変数iをJ−2とする第3処理と、
前記第3処理の後に、前記素数候補Nを法とし、前記第1記憶領域に記憶された値同士のモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に書き戻す動作をm回繰り返す第4処理と、
前記第4処理の後に、前記指数部切り出し処理で切り出された部分指数e[i]が2m−1未満の場合は、前記2のベキ乗生成処理により生成された2^(e[i]+1+n−2m)と前記第1の記憶領域に格納された値との前記Nを法とするモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に格納する第5処理と、
前記第5処理の後に、前記内部状態変数iから1を引いた値を前記内部状態変数iに格納し、前記iの値が2以上の場合は前記第4処理に戻り、前記iの値が1以下になるまでそれを繰り返す第6処理と、
前記第6処理の後に、前記素数候補Nを法とし、前記第1記憶領域に記憶された値同士のモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に書き込む動作をm回繰り返す第7処理と、
前記第7処理の後、前記2のベキ乗生成処理により計算された2^(e[1]+n−2m)と、前記第1記憶領域に格納された値との前記素数候補Nを法とするモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に格納する第8処理と、
前記第8処理の後、前記モンゴメリ剰余乗算装置により、前記素数候補Nを法とし、前記第1記憶領域に格納された値同士のモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に格納する動作をm回繰り返す第9処理と、
前記第9処理の後、前記2のベキ乗生成処理により計算された2^(e[0])と、前記第1記憶領域に格納された値との前記素数候補Nを法とするモンゴメリ剰余乗算を行って、その演算結果をフェルマーテスト結果として出力する第10処理とを含む、データ処理装置。
【請求項2】
前記プログラムを格納したメモリを更に有し、1個の半導体基板に形成された、請求項1記載のデータ処理装置。
【請求項3】
モンゴメリ剰余乗算を行うモンゴメリ剰余乗算器を備えたコプロセッサと、プログラムを実行し前記コプロセッサを制御する中央処理装置とを有し、前記中央処理装置の制御によってデータ処理を行なうことにより、外部より与えられた素数候補Nに対して、2(N−1)mod Nを計算してフェルマーテストを実行するデータ処理装置であって、前記データ処理は、
前記素数候補Nを記憶する処理と、
Nのビット長nを記憶する処理と、
log2(n)を超えない最大の整数mを計算して記憶する処理と、
前記素数候補Nから、N−1を計算し、JをJ≧n/mとなる最小の整数としたときに、(N−1)を最下位からmビットごとにJ個の区間に区切り、(N−1)=2(J−1)m・e[J−1]+2(J−2)m・e[J−2]+…+2m・e[1]+e[0]なる式を満たすように(N−1)を部分指数e[0],e[1],…,e[J−1]に分割する指数部切り出し処理と、
前記指数部切り出し処理により切り出されたmビットの値e[i]から2^(e[i]+1+n−2m)
を生成する2のベキ乗生成処理と、
前記指数部切り出し処理により切り出された部分指数の最上位の値に1を加えたe[J−1]+1が2nと等しい場合は、R mod N=2n mod Nの演算結果と、R2 mod N=22n mod Nの演算結果との前記素数候補Nを法とするモンゴメリ剰余乗算を行って、その演算結果を第1記憶領域に格納する第1処理と、
前記e[J−1]+1が2n未満の場合は、前記2のベキ乗生成手段により計算した2^(e[J−1]+1)と前記素数候補Nとの排他的論理和を取った値と、前記R2 mod N=22n mod Nの演算結果との前記Nを法とするモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に格納する第2処理と、
前記第1処理又は第2処理のいずれか一方の処理の後に内部の状態変数iをJ−2とする第3処理と、
前記第3処理の後に、前記素数候補Nを法とし、前記第1記憶領域に格納された値同士のモンゴメリ剰余乗算を行ってその4演算結果を前記第1記憶領域に格納する動作をm回繰り返す第4処理と、
前記第4処理の後に、前記指数部切り出し処理で切り出された部分指数e[i]が2m−1未満の場合は、前記2のベキ乗生成処理により生成された2^(e[i]+1+n−2m)と前記素数候補Nとの排他的論理和が採られた値と、前記第1記憶領域に格納されている値との前記素数候補Nを法とするモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に格納する第5処理と、
前記第4処理の後に、前記指数部切り出し処理で切り出された部分指数e[i]が2m−1と等しい場合は、前記R mod N=2n mod Nと、前記第1記憶領域に格納された値との前記素数候補Nを法とするモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に格納する第6処理と、
前記第5処理又は第6処理のいずれか一方の処理の後に前記内部状態変数iから1を引いた値を前記内部状態変数iに格納し、前記iの値が2以上の場合は、前記第3処理に戻り、前記iの値が1以下になるまでそれを繰り返す第7処理と、
前記第7処理の後に前記素数候補Nを法とし、前記第1記憶領域に記憶された値同士のモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に格納する動作をm回繰り返す第8処理と、
前記第8処理の後、前記2のベキ乗生成処理で生成された2^(e[1]+n−2m)と、前記第1記憶領域に格納された値との前記素数候補Nを法とするモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に格納する第9処理と、
前記第9処理の後、前記素数候補Nを法とし、前記第1記憶領域に格納された値同士のモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に格納する動作をm回繰り返す第10処理と、
前記第10処理の後、前記2のベキ乗生成処理により生成された2^(e[0])と前記第1記憶領域に格納された値との前記Nを法とするモンゴメリ剰余乗算を行って、その演算結果をフェルマーテスト結果として出力する第11処理とを含む、データ処理装置。
【請求項4】
前記プログラムを格納したメモリを更に有し、1個の半導体基板に形成された、請求項2記載のデータ処理装置。
【請求項5】
モンゴメリ剰余乗算を行うモンゴメリ剰余乗算器を備えたコプロセッサと、プログラムを実行し前記コプロセッサを制御する中央処理装置とを有し、前記中央処理装置の制御によってデータ処理を行なうことにより、外部より与えられた素数候補Nに対して、2(N−1)mod Nを計算してフェルマーテストを実行するデータ処理装置であって、前記データ処理は、
前記素数候補Nを記憶する処理と、
Nのビット長nを記憶する処理と、
log2(n)を超えない最大の整数mを計算して記憶する処理と、
前記素数候補Nから、N−1を計算し、JをJ≧n/mとなる最小の整数としたときに、(N−1)を最下位からmビットごとにJ個の区間に区切り、(N−1)=2(J−1)m・e[J−1]+2(J−2)m・e[J−2]+…+2m・e[1]+e[0]なる式を満たすように(N−1)を部分指数e[0],e[1],…,e[J−1]に分割する指数部切り出し処理と、
前記指数部切り出し処理により切り出されたmビットの値e[i]から2^(e[i]+1+n−2m)を生成する2のベキ乗生成処理と、
前記指数部切り出し処理により切り出された部分指数の最上位の値に1を加えたe[J−1]+1が2nと等しい場合は、R mod N=2n mod Nの演算結果と、R2 mod N=22n mod Nの演算結果との前記素数候補Nを法とするモンゴメリ剰余乗算を行ってその演算結果を第1記憶領域に格納する第1処理と、
前記e[J−1]+1が2n未満の場合は、前記Nのe[J−1]+1ビット目の値を指定ビット反転器により反転した値と前記R2 mod N=22n mod Nの演算結果との前記素数候補Nを法とするモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に格納する第2処理と、
前記第1処理又は第2処理のいずれか一方の処理の後に内部の状態変数iをJ−2とする第3処理と、
前記第3処理の後に、前記素数候補Nを法とし、前記第1記憶領域に記憶された値同士のモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に格納する動作をm回繰り返す第4処理と、
前記第4処理の後に、前記指数部切り出し処理によって切り出された部分指数e[i]が2m−1未満の場合は、前記Nのe[i]+1+n−2mビット目の値を前記指定ビット反転器により反転した値と前記第1記憶領域に格納された値との前記素数候補Nを法とするモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に記憶する第5処理と、
前記第4処理の後に、前記指数部切り出し処理によって切り出された部分指数e[i]が2m−1と等しい場合は、前記R mod N=2n mod Nの演算結果と前記第1記憶領域に格納された値との前記素数候補Nを法とするモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に格納する第6処理と、
前記第5処理又は第6処理のいずれか一方の処理の後に、前記内部状態変数iから1を引いた値を前記内部状態変数iに格納し、前記iの値が2以上の場合は、前記第3処理に戻り、前記iの値が1以下になるまでそれを繰り返す第7処理と、
前記第7処理の後に、前記素数候補Nを法とし、前記第1記憶領域に記憶された値同士のモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に格納する動作をm回繰り返す第8処理と、
前記第8処理の後、前記2のベキ乗生成手段により計算した2^(e[1]+n−2m)と前記第1記憶領域に格納された値との前記素数候補Nを法とするモンゴメリ剰余乗算をおこなってその演算結果を前記第1記憶領域に格納する第9処理と、
前記第9処理の後、前記素数候補Nを法とし、前記第1記憶領域に記憶された値同士のモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に格納する動作をm回繰り返す第10処理と、
前記第10処理の後、前記2のベキ乗生成処理により生成された2^(e[0])と、前記第1記憶領域に格納された値との前記素数候補Nを法とするモンゴメリ剰余乗算を行ってその演算結果をフェルマーテスト結果として出力する第11処理とを含む、データ処理装置。
【請求項6】
前記プログラムを格納したメモリを更に有し、1個の半導体基板に形成された、請求項5記載のデータ処理装置。
【請求項1】
モンゴメリ剰余乗算を行うモンゴメリ剰余乗算器を備えたコプロセッサと、プログラムを実行し前記コプロセッサを制御する中央処理装置とを有し、前記中央処理装置の制御によってデータ処理を行なうことにより、外部より与えられた素数候補Nに対して、2(N−1)mod Nを計算してフェルマーテストを実行するデータ処理装置であって、前記データ処理は、
前記素数候補Nを記憶する処理と、
Nのビット長nを記憶する処理と、
log2(n)を超えない最大の整数mを計算して記憶する処理と、
前記素数候補Nから、N−1を計算し、JをJ≧n/mとなる最小の整数としたときに、(N−1)を最下位からmビットごとにJ個の区間に区切り、(N−1)=2(J−1)m・e[J−1]+2(J−2)m・e[J−2]+…+2m・e[1]+e[0]なる式を満たすように(N−1)を部分指数e[0],e[1],…,e[J−1]に分割する指数部切り出し処理と、
前記指数部切り出し処理により切り出されたmビットの値e[i]から2^(e[i]+1+n−2m)を生成する2のベキ乗生成処理と、
前記指数部切り出し処理で切り出された部分指数の最上位の値に1を加えたe[J−1]+1が2nと等しい場合は、R mod N=2n mod Nの演算結果と、R2 mod N=22n mod Nの演算結果との前記素数候補Nを法とするモンゴメリ剰余乗算を行ってその演算結果を第1記憶領域に格納する第1処理と、
前記e[J−1]+1が2n未満の場合は、前記2のベキ乗生成手段により計算した2^(e[J−1]+1)と、前記R2modN=22n mod Nの演算結果との前記Nを法とするモンゴメリ剰余乗算を行ってその演算結果を前記第1の記憶領域に格納する第2処理と、
前記第1処理又は前記第2処理のいずれか一方の処理の後に内部の状態変数iをJ−2とする第3処理と、
前記第3処理の後に、前記素数候補Nを法とし、前記第1記憶領域に記憶された値同士のモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に書き戻す動作をm回繰り返す第4処理と、
前記第4処理の後に、前記指数部切り出し処理で切り出された部分指数e[i]が2m−1未満の場合は、前記2のベキ乗生成処理により生成された2^(e[i]+1+n−2m)と前記第1の記憶領域に格納された値との前記Nを法とするモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に格納する第5処理と、
前記第5処理の後に、前記内部状態変数iから1を引いた値を前記内部状態変数iに格納し、前記iの値が2以上の場合は前記第4処理に戻り、前記iの値が1以下になるまでそれを繰り返す第6処理と、
前記第6処理の後に、前記素数候補Nを法とし、前記第1記憶領域に記憶された値同士のモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に書き込む動作をm回繰り返す第7処理と、
前記第7処理の後、前記2のベキ乗生成処理により計算された2^(e[1]+n−2m)と、前記第1記憶領域に格納された値との前記素数候補Nを法とするモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に格納する第8処理と、
前記第8処理の後、前記モンゴメリ剰余乗算装置により、前記素数候補Nを法とし、前記第1記憶領域に格納された値同士のモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に格納する動作をm回繰り返す第9処理と、
前記第9処理の後、前記2のベキ乗生成処理により計算された2^(e[0])と、前記第1記憶領域に格納された値との前記素数候補Nを法とするモンゴメリ剰余乗算を行って、その演算結果をフェルマーテスト結果として出力する第10処理とを含む、データ処理装置。
【請求項2】
前記プログラムを格納したメモリを更に有し、1個の半導体基板に形成された、請求項1記載のデータ処理装置。
【請求項3】
モンゴメリ剰余乗算を行うモンゴメリ剰余乗算器を備えたコプロセッサと、プログラムを実行し前記コプロセッサを制御する中央処理装置とを有し、前記中央処理装置の制御によってデータ処理を行なうことにより、外部より与えられた素数候補Nに対して、2(N−1)mod Nを計算してフェルマーテストを実行するデータ処理装置であって、前記データ処理は、
前記素数候補Nを記憶する処理と、
Nのビット長nを記憶する処理と、
log2(n)を超えない最大の整数mを計算して記憶する処理と、
前記素数候補Nから、N−1を計算し、JをJ≧n/mとなる最小の整数としたときに、(N−1)を最下位からmビットごとにJ個の区間に区切り、(N−1)=2(J−1)m・e[J−1]+2(J−2)m・e[J−2]+…+2m・e[1]+e[0]なる式を満たすように(N−1)を部分指数e[0],e[1],…,e[J−1]に分割する指数部切り出し処理と、
前記指数部切り出し処理により切り出されたmビットの値e[i]から2^(e[i]+1+n−2m)
を生成する2のベキ乗生成処理と、
前記指数部切り出し処理により切り出された部分指数の最上位の値に1を加えたe[J−1]+1が2nと等しい場合は、R mod N=2n mod Nの演算結果と、R2 mod N=22n mod Nの演算結果との前記素数候補Nを法とするモンゴメリ剰余乗算を行って、その演算結果を第1記憶領域に格納する第1処理と、
前記e[J−1]+1が2n未満の場合は、前記2のベキ乗生成手段により計算した2^(e[J−1]+1)と前記素数候補Nとの排他的論理和を取った値と、前記R2 mod N=22n mod Nの演算結果との前記Nを法とするモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に格納する第2処理と、
前記第1処理又は第2処理のいずれか一方の処理の後に内部の状態変数iをJ−2とする第3処理と、
前記第3処理の後に、前記素数候補Nを法とし、前記第1記憶領域に格納された値同士のモンゴメリ剰余乗算を行ってその4演算結果を前記第1記憶領域に格納する動作をm回繰り返す第4処理と、
前記第4処理の後に、前記指数部切り出し処理で切り出された部分指数e[i]が2m−1未満の場合は、前記2のベキ乗生成処理により生成された2^(e[i]+1+n−2m)と前記素数候補Nとの排他的論理和が採られた値と、前記第1記憶領域に格納されている値との前記素数候補Nを法とするモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に格納する第5処理と、
前記第4処理の後に、前記指数部切り出し処理で切り出された部分指数e[i]が2m−1と等しい場合は、前記R mod N=2n mod Nと、前記第1記憶領域に格納された値との前記素数候補Nを法とするモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に格納する第6処理と、
前記第5処理又は第6処理のいずれか一方の処理の後に前記内部状態変数iから1を引いた値を前記内部状態変数iに格納し、前記iの値が2以上の場合は、前記第3処理に戻り、前記iの値が1以下になるまでそれを繰り返す第7処理と、
前記第7処理の後に前記素数候補Nを法とし、前記第1記憶領域に記憶された値同士のモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に格納する動作をm回繰り返す第8処理と、
前記第8処理の後、前記2のベキ乗生成処理で生成された2^(e[1]+n−2m)と、前記第1記憶領域に格納された値との前記素数候補Nを法とするモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に格納する第9処理と、
前記第9処理の後、前記素数候補Nを法とし、前記第1記憶領域に格納された値同士のモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に格納する動作をm回繰り返す第10処理と、
前記第10処理の後、前記2のベキ乗生成処理により生成された2^(e[0])と前記第1記憶領域に格納された値との前記Nを法とするモンゴメリ剰余乗算を行って、その演算結果をフェルマーテスト結果として出力する第11処理とを含む、データ処理装置。
【請求項4】
前記プログラムを格納したメモリを更に有し、1個の半導体基板に形成された、請求項2記載のデータ処理装置。
【請求項5】
モンゴメリ剰余乗算を行うモンゴメリ剰余乗算器を備えたコプロセッサと、プログラムを実行し前記コプロセッサを制御する中央処理装置とを有し、前記中央処理装置の制御によってデータ処理を行なうことにより、外部より与えられた素数候補Nに対して、2(N−1)mod Nを計算してフェルマーテストを実行するデータ処理装置であって、前記データ処理は、
前記素数候補Nを記憶する処理と、
Nのビット長nを記憶する処理と、
log2(n)を超えない最大の整数mを計算して記憶する処理と、
前記素数候補Nから、N−1を計算し、JをJ≧n/mとなる最小の整数としたときに、(N−1)を最下位からmビットごとにJ個の区間に区切り、(N−1)=2(J−1)m・e[J−1]+2(J−2)m・e[J−2]+…+2m・e[1]+e[0]なる式を満たすように(N−1)を部分指数e[0],e[1],…,e[J−1]に分割する指数部切り出し処理と、
前記指数部切り出し処理により切り出されたmビットの値e[i]から2^(e[i]+1+n−2m)を生成する2のベキ乗生成処理と、
前記指数部切り出し処理により切り出された部分指数の最上位の値に1を加えたe[J−1]+1が2nと等しい場合は、R mod N=2n mod Nの演算結果と、R2 mod N=22n mod Nの演算結果との前記素数候補Nを法とするモンゴメリ剰余乗算を行ってその演算結果を第1記憶領域に格納する第1処理と、
前記e[J−1]+1が2n未満の場合は、前記Nのe[J−1]+1ビット目の値を指定ビット反転器により反転した値と前記R2 mod N=22n mod Nの演算結果との前記素数候補Nを法とするモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に格納する第2処理と、
前記第1処理又は第2処理のいずれか一方の処理の後に内部の状態変数iをJ−2とする第3処理と、
前記第3処理の後に、前記素数候補Nを法とし、前記第1記憶領域に記憶された値同士のモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に格納する動作をm回繰り返す第4処理と、
前記第4処理の後に、前記指数部切り出し処理によって切り出された部分指数e[i]が2m−1未満の場合は、前記Nのe[i]+1+n−2mビット目の値を前記指定ビット反転器により反転した値と前記第1記憶領域に格納された値との前記素数候補Nを法とするモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に記憶する第5処理と、
前記第4処理の後に、前記指数部切り出し処理によって切り出された部分指数e[i]が2m−1と等しい場合は、前記R mod N=2n mod Nの演算結果と前記第1記憶領域に格納された値との前記素数候補Nを法とするモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に格納する第6処理と、
前記第5処理又は第6処理のいずれか一方の処理の後に、前記内部状態変数iから1を引いた値を前記内部状態変数iに格納し、前記iの値が2以上の場合は、前記第3処理に戻り、前記iの値が1以下になるまでそれを繰り返す第7処理と、
前記第7処理の後に、前記素数候補Nを法とし、前記第1記憶領域に記憶された値同士のモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に格納する動作をm回繰り返す第8処理と、
前記第8処理の後、前記2のベキ乗生成手段により計算した2^(e[1]+n−2m)と前記第1記憶領域に格納された値との前記素数候補Nを法とするモンゴメリ剰余乗算をおこなってその演算結果を前記第1記憶領域に格納する第9処理と、
前記第9処理の後、前記素数候補Nを法とし、前記第1記憶領域に記憶された値同士のモンゴメリ剰余乗算を行ってその演算結果を前記第1記憶領域に格納する動作をm回繰り返す第10処理と、
前記第10処理の後、前記2のベキ乗生成処理により生成された2^(e[0])と、前記第1記憶領域に格納された値との前記素数候補Nを法とするモンゴメリ剰余乗算を行ってその演算結果をフェルマーテスト結果として出力する第11処理とを含む、データ処理装置。
【請求項6】
前記プログラムを格納したメモリを更に有し、1個の半導体基板に形成された、請求項5記載のデータ処理装置。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【公開番号】特開2009−258460(P2009−258460A)
【公開日】平成21年11月5日(2009.11.5)
【国際特許分類】
【出願番号】特願2008−108462(P2008−108462)
【出願日】平成20年4月18日(2008.4.18)
【出願人】(503121103)株式会社ルネサステクノロジ (4,790)
【Fターム(参考)】
【公開日】平成21年11月5日(2009.11.5)
【国際特許分類】
【出願日】平成20年4月18日(2008.4.18)
【出願人】(503121103)株式会社ルネサステクノロジ (4,790)
【Fターム(参考)】
[ Back to top ]