(57)【要約】【課題】従来のべき乗剰余演算器は、回路規模が増大する問題があった。【解決手段】本発明のべき乗剰余演算器は、被乗数、乗数、及び、除数に基づき乗算演算及び剰余演算を行なう乗算剰余演算器２１と、べき数を二進数で示した場合の各ビットの値を個別に格納するべき数格納部と、参照するビットの値に応じて乗算剰余演算器２１の出力と被乗数とのいずれか一方を出力する第１の選択回路２２と、第１の選択回路２２の出力値を演算結果として格納する結果格納レジスタ２６と、を有するものである。【選択図】図１
2009008993.tif 000002
【特許請求の範囲】
【請求項１】
被乗数、乗数、及び、除数に基づき乗算演算及び剰余演算を行なう乗算剰余演算器と、
べき数を二進数で示した場合の各ビットの値を個別に格納するべき数格納部と、
参照する前記ビットの値に応じて前記乗算剰余演算器の出力と前記被乗数とのいずれか一方を出力する第１の選択回路と、
前記第１の選択回路の出力値を演算結果として格納する結果格納レジスタと、
を有するべき乗剰余演算器。
【請求項２】
前記乗算剰余演算器は、前記被乗数及び前記乗数として前記結果格納レジスタに格納される前周期の前記演算結果を用いる第１の演算と、前記被乗数として前記結果格納レジスタに格納される前周期の前記演算結果を用い、前記乗数として新たに入力される入力値を用いる第２の演算と、を交互に行なう請求項１に記載のべき乗剰余演算器。
【請求項３】
前記べき乗剰余演算器は、前記ビットの値を参照して、前記第１の選択回路がいずれの値を選択するかを指定する第１の選択信号を生成する制御回路を有する請求項１又は２に記載のべき乗剰余演算器。
【請求項４】
前記制御回路は、前記べき数格納部と、前記べき数格納部のビットの値を順次参照して前記第１の選択信号を出力するシーケンス制御回路とを有する請求項３に記載のべき乗剰余演算器。
【請求項５】
前記制御回路は、前記べき数格納部として機能し、さらにプログラムが格納される記憶装置と、前記第１の選択信号の値として参照される第１の参照値の値が格納される設定レジスタと、前記プログラムに基づき前記設定レジスタに格納する値を出力する中央演算処理装置とを有する請求項３に記載のべき乗剰余演算器。
【請求項６】
前記べき乗剰余演算器は、前記第１の演算において前記乗数として前周期の前記演算結果を前記乗算剰余演算器に出力し、前記第２の演算において前記乗数として前記入力値を前記乗算剰余演算器に出力する第２の選択回路を有する請求項２に記載のべき乗剰余演算器。
【請求項７】
前記べき乗剰余演算器は、演算の経過に基づき前記第２の選択回路がいずれの値を選択するかを指定する第２の選択信号を生成する制御回路を有する請求項６に記載のべき乗剰余演算器。
【請求項８】
前記制御回路は、前記べき数格納部として機能し、さらにプログラムが格納される記憶装置と、前記第２の選択信号の値として参照される第２の参照値の値が格納される設定レジスタと、前記プログラムに基づき前記設定レジスタに格納する値を出力する中央演算処理装置とを有する請求項７に記載のべき乗剰余演算器。
【請求項９】
前記べき乗剰余演算器は、前記被乗数を格納する第１の中間レジスタと、前記乗数を格納する第２の中間レジスタとを有する請求項１乃至８のいずれか１項に記載のべき乗剰余演算器。
【請求項１０】
べき乗剰余演算器の制御方法であって、
べき数を二進数で示した場合の各ビットの値を個別に格納し、
被乗数、乗数、及び、除数に基づき乗算演算及び剰余演算を行ない、
参照する前記ビットの値に応じて前記乗算剰余演算器の出力と前記被乗数とのいずれか一方を演算結果として結果格納レジスタに格納する
べき乗剰余演算器の制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はべき乗剰余演算器及びその制御方法に関し、特に耐タンパー機能を有するべき乗剰余演算器及びその制御方法に関する。
【背景技術】
【０００２】
近年、クレジットカード等にＩＣチップを埋め込み、ＩＣチップ内にカード情報や個人情報等を格納することが行なわれている。このようなＩＣチップには、ＩＣチップに格納された情報を漏洩あるいは改竄から守る必要がある。このような情報保護機能を耐タンパー機能と称し、情報保護能力を耐タンパー性と称す。
【０００３】
また、情報を秘匿するためにＩＣチップに格納される情報は、一般的にＲＳＡ（Rivest Shamir Adleman scheme）暗号方式等を用いた暗号化処理が行なわれている。そして、情報は暗号化された状態でＩＣチップ内に格納され、読み出し時に復号化される。ＲＳＡ暗号方式など現在一般的に用いられる暗号化方式は、暗号化のアルゴリズムが公開されており安全性については十分な検討がされている。しかしながら、このアルゴリズムをハードウェアやソフトウェアに実装した場合の安全性については、その実装方法による部分もあるため十分な検討がされていない。例えば、実装されたアルゴリズムの脆弱性をついて秘密情報を入手する方法としてサイドチャネル攻撃が存在する。
【０００４】
サイドチャネル攻撃は、本来の通信経路（チャネルと称す）以外の経路から秘密情報を導き出す方法である。例えば、情報の暗号化あるいは復号化を実行中のＩＣチップの消費電力や電磁波、処理時間などのサイドチャネル情報から内部に格納された情報を導き出す。消費電力の波形から情報を導き出す方法をＳＰＡ（Simple Power Analysis）と称し、消費電力の差を統計的に処理することで演算内容の違いを判別する方法をＤＰＡ（Differential Power Analysis）と称し、演算の処理時間の変化に着目する方法をタイミングアタックと称す。
【０００５】
ここで、ＲＳＡ暗号方式で用いられる暗号化及び復号化の演算について簡単に説明する。ＲＳＡ暗号方式では、暗号化処理を（１）式に基づき行ない、復号化処理を（２）式に基づき行なう。
Ｃ＝ＭＥｍｏｄＮ      ・・・（１）
Ｍ＝ＣＤｍｏｄＮ      ・・・（２）
なお、（１）、（２）式における、Ｃは暗号文を数値化したものであり、Ｍは平文を数値化したものであり、Ｅ及びＮは公開鍵を数値化したものであり、Ｄは秘密鍵を数値化したものである。
【０００６】
つまり、ＲＳＡ暗号方式では、暗号化処理及び復号化処理をともに同じべき乗剰余演算によって行なうことが可能である。このようなことから、べき数Ｅ及びＤをともにＤ、暗号化処理における平文ＭをＸ、暗号文ＣをＹ、復号化処理における暗号文ＣをＸ、平文ＭをＹとするとＲＳＡ暗号方式の演算は（３）式であらわすことができる。
Ｙ＝ＸＤｍｏｄＮ      ・・・（３）
（３）式に示す演算を実行する演算器を以下では、べき乗剰余演算器と称す。
【０００７】
ここで、（３）式で示す演算を二進数によって表現した数値を用いて実現する方法について説明する。べき数を二進数で示し、べき数を示すビットの値が"０"である場合は二乗算を行ない、べき数を示すビットの値が"１"である場合は二乗算と乗算とを行なうことで（３）式で示すべき乗剰余演算を行なう方法をバイナリ法と称す。つまり、バイナリ法を用いた場合、（３）式は、Ａ×ＢｍｏｄＮの繰り返し演算によって実現することができる。このバイナリ法を用いたＲＳＡ暗号方式の演算アルゴリズムを以下に示す。
Ｙ＝１      ・・・（４）
ｆｏｒ（ｊ＝１０２４  ｔｏ  １）      ・・・（５）
Ｙ＝Ｙ×ＹｍｏｄＮ    ・・・（６）
ｉｆ（ｄ［ｊ］＝＝１）  ｔｈｅｎ  Ｙ＝Ｙ×ＸｍｏｄＮ      ・・・（７）
ｅｎｄ  ｆｏｒ
なお、ｄ［ｊ］はべき数Ｄのｊビット目の値を示す。
【０００８】
上記アルゴリズムによると、例えばべき数Ｄが５７であった場合、べき数Ｄは二進数表記によって"１１１００１"となる。従って、最上位ビットを含む上位３ビットの演算においては（６）式及び（７）式の演算が行なわれる。しかし、最上位ビットから４番目及び５番目のビットについては、値が"０"であるため、（６）式の演算のみが行なわれる。
【０００９】
従って、ＲＳＡ暗号方式をバイナリ法を用いてＩＣチップに実装した場合、べき数Ｄの値によって演算方法が異なるため、この違いに基づきタイミングアタック、ＳＰＡ又はＤＰＡなどのサイドチャネル攻撃を受ける可能性がある。
【００１０】
このようなサイドチャネル攻撃に対して耐タンパー性を向上させるための技術が特許文献１、２（以下、従来例１、２と称す）に開示されている。従来例１に開示されているべき乗剰余演算器のブロック図を図４に示す。従来例１では、べき数Ｄの値がｄ［ｊ］＝０であった場合、ダミー演算として（７）式の演算を行なうことで、演算の違いによる消費電力及びタイミングの差を無くす。また、従来例１では、ダミー演算の結果を格納するためのＫレジスタ１３２を設け、ダミー演算の結果をＫレジスタ１３２に書き込む。これによって、従来例１では、ｄ［ｊ］＝０のときの演算結果を（７）式が実行されないものと同一にしながら、レジスタへの書き込みによって生じる消費電力の差を低減する。つまり、従来例１のべき乗剰余演算器は、べき数の値が"０"であった場合にダミー演算及びダミーレジスタ（Ｋレジスタ１３２）への書き込みを行なうことで、べき数の値による計算時間及び消費電力の差を低減してサイドチャネル攻撃に対する耐タンパー性を向上させる。
【００１１】
また、従来例２に記載された技術では、べき数の値が"０"であった場合にダミー演算を行なう。そして、演算結果は、廃棄あるいはダミーレジスタへの書き込みが行なわれる。つまり、従来例２においても、従来例１と同様に、べき数の値による計算時間及び消費電力の差を低減してサイドチャネル攻撃に対する耐タンパー性を向上させる。
【特許文献１】特開２００４−１２５８９１号公報
【特許文献２】特開２００１−１９５５５５号公報
【発明の開示】
【発明が解決しようとする課題】
【００１２】
しかしながら、従来例１、２に示す方法では、ダミー演算の結果を格納するダミーレジスタが必要になり、このダミーレジスタによって回路規模が増大する問題がある。近年のＲＳＡ暗号方式では、公開鍵及び秘密鍵の情報として１０２４ビット〜２０４８ビットのものを用いることが一般的である。そのため、ダミーレジスタは、鍵の大きさに応じて１０２４ビット〜２０４８ビットが必要になる。情報の秘匿性は、鍵のビット数に依存するため、情報の秘匿性を高めようとした場合、鍵のビット数は更に大きくなり、ダミーレジスタの大きさも更に大きくなるため、ダミーレジスタの大きさが回路規模に与える影響は秘匿性の向上とともに更に大きくなる。
【課題を解決するための手段】
【００１３】
本発明の一態様は、被乗数、乗数、及び、除数に基づき乗算演算及び剰余演算を行なう乗算剰余演算器と、べき数を二進数で示した場合の各ビットの値を個別に格納するべき数格納部と、参照する前記ビットの値に応じて前記乗算剰余演算器の出力と前記被乗数とのいずれか一方を出力する第１の選択回路と、前記第１の選択回路の出力値を演算結果として格納する結果格納レジスタと、を有するべき乗剰余演算器である。
【００１４】
本発明の別の態様は、べき乗剰余演算器の制御方法であって、べき数を二進数で示した場合の各ビットの値を個別に格納し、被乗数、乗数、及び、除数に基づき乗算演算及び剰余演算を行ない、参照する前記ビットの値に応じて前記乗算剰余演算器の出力と前記被乗数とのいずれか一方を演算結果として結果格納レジスタに格納するべき乗剰余演算器の制御方法である。
【００１５】
本発明にかかるべき乗剰余演算器によれば、べき数を示す各ビットのうち参照しているビットの値に応じて乗算剰余演算器の出力と被乗数とのいずれか一方を結果格納レジスタに格納する。これによって、乗算剰余演算器によって実行された演算を廃棄した場合であっても、結果格納レジスタに被乗数を書き込むことができる。つまり、乗算剰余演算器によってダミー演算を実行した場合であっても、本発明にかかるべき乗剰余演算器は、その結果を廃棄して被乗数を結果格納レジスタに書き込むことで、演算の整合性を保つことができる。また、ダミー演算及び結果格納レジスタの書き込みを行なうことにより、本発明にかかるべき乗剰余演算器は、べき数の値によらず消費電力及び演算時間をほぼ一定に保つことができる。
【発明の効果】
【００１６】
本発明にかかるべき乗剰余演算器は、回路規模の増加を抑制しながら耐タンパー性を向上させることができる。
【発明を実施するための最良の形態】
【００１７】
実施の形態１
本発明にかかるべき乗剰余演算器は、ＲＳＡ暗号方式で用いられるべき乗剰余演算を行なう演算器である。以下の説明では、一例として１０２４ビットのべき数を有するＲＳＡ暗号方式について説明する。本発明にかかるべき乗剰余演算器は、べき数の値を二進数によって表現した場合のべき数のビット長に応じて繰り返し演算を行ない、（８）式の演算結果を得る。また、（８）式において、Ｘは暗号化処理における平文Ｍ、復号化処理における暗号文Ｃであり、Ｙは暗号化処理おける暗号文Ｃ、復号化処理における平文Ｍであり、Ｄはべき数であって暗号化処理における公開鍵、復号化処理における秘密鍵であり、Ｎは公開鍵である。
Ｙ＝ＸＤｍｏｄＮ      ・・・（８）
【００１８】
また、本発明にかかるべき乗剰余演算器は、べき数が１０２４ビットで示される場合、以下のアルゴリズムに基づき動作する。
Ｙ＝１      ・・・（９）
ｆｏｒ（ｊ＝１０２４  ｔｏ  １）      ・・・（１０）
Ｙ＝Ｙ×ＹｍｏｄＮ    ・・・（１１）
ｉｆ（ｄ［ｊ］＝＝１）  ｔｈｅｎ  Ｙ＝Ｙ×ＸｍｏｄＮ      ・・・（１２）
ｅｎｄ  ｆｏｒ
なお、ｄ［ｊ］はべき数Ｄのｊビット目の値を示す。
【００１９】
以下、図面を参照して本発明の実施の形態について説明する。実施の形態１にかかるべき乗剰余演算器１のブロック図を図１に示す。図１に示すように、べき乗剰余演算器１は、制御回路１０、乗算剰余演算器２１、第１の選択回路２２、第２の選択回路２３、Ｘレジスタ２４、Ｎレジスタ２５、結果格納レジスタ（例えば、Ｙレジスタ）２６、第１の中間レジスタ（例えば、Ａレジスタ）２７、第２の中間レジスタ（例えば、Ｂレジスタ）２８を有している。
【００２０】
Ｘレジスタ２４には、（８）式におけるＸの値が格納され、格納された値は信号ｋとして出力される。Ｎレジスタ２５には、除数（例えば、（８）式におけるＮの値）が格納され、格納された値は信号ｌとして出力される。Ｙレジスタ２６には、（８）式におけるＹの値が格納され、格納された値は信号ｉとして出力される。Ａレジスタ２７には、被乗数（例えば、Ｙレジスタ２６に格納された前周期の演算結果をコピーした値）が信号ｉとして与えられ、この値が格納される。Ａレジスタ２７に格納された値は信号ａ及び信号ｅとして出力される。Ｂレジスタ２８には、乗数（例えば、第２の選択回路２３が信号ｎとして出力する値）が格納され、格納された値は信号ｆとして出力される。
【００２１】
第１の選択回路２２は、制御回路１０が出力するダミー演算信号ｃの値に応じて、Ａレジスタ２７が出力する信号ｄと乗算剰余演算器２１が出力する信号ｇとのいずれか一方を選択して出力する。つまり、第１の選択回路２２は、ダミー演算信号ｃの値に応じてＡレジスタ２７に格納されている前周期の演算結果と乗算剰余演算器２１の演算結果とのいずれか一方を選択して出力する。第１の選択回路２２は、例えば、ダミー演算信号ｃが"１"であった場合、信号ｄを選択してＡレジスタ２７に格納されている前周期の演算結果を出力する。一方、ダミー演算信号ｃが"０"であった場合、信号ｇを選択して乗算剰余演算器２１の演算結果を出力する。なお、第１の選択回路２２の出力は信号ｈとして出力される。
【００２２】
第２の選択回路２３は、制御回路１０が出力する演算選択信号ｍの値に応じて、信号ｋと信号ｉのいずれか一方を選択して出力する。つまり、第２の選択回路２３は、演算選択信号ｍの値に応じて（８）式におけるＸの値とＹの値とのいずれか一方を選択して出力する。第２の選択回路２３は、例えば、演算選択信号ｍが"１"であった場合、信号ｋを選択してＸレジスタ２４に格納されている新たな入力値（例えば、Ｘ）を出力する。一方、演算選択信号ｍが"０"であった場合、信号ｉを選択してＹレジスタ２６に格納されている前周期の演算結果（例えば、Ｙ）を出力する。なお、第１の選択回路２２の出力は信号ｎとして出力される。
【００２３】
乗算剰余演算器２１は、Ａレジスタ２７に格納された被乗数とＢレジスタ２８に格納された乗数との乗算結果をＮレジスタ２５に格納された除数で除して得られる剰余を計算する。つまり、乗算剰余演算器２１は、Ｂレジスタ２８に信号ｉとして与えられる前周期の演算結果が格納されている場合、（１１）式におけるＹ×ＹｍｏｄＮを計算し、Ｂレジスタ２８に信号ｋとして与えられる新たな入力値が格納されている場合、（１２）におけるＹ×ＸｍｏｄＮを計算する。以下の説明では、Ｂレジスタ２８にＹ（前周期の演算結果）が格納されている場合の乗算剰余演算器２１の計算を第１の演算と称し、Ｂレジスタ２８にＸ（新たな入力値）が格納されている場合の乗算剰余演算器２１の計算を第２の演算と称す。なお、乗算剰余演算器２１の演算結果は信号ｇとして第１の選択回路２２に対して出力される。また、乗算剰余演算器２１は、制御回路１０が出力する演算開始信号ｂが"１"である場合に演算を行ない、演算が完了すると演算か完了したことを動作ステータス信号ａとして制御回路に通知する。
【００２４】
制御回路１０は、べき数格納部（例えば、Ｄレジスタ）１１とシーケンス制御回路１２とを有している。Ｄレジスタ１１は、複数のべき数格納レジスタを有する。複数のべき数格納レジスタには、べき数を二進数で表現した各ビットの値が個別に格納される。また、シーケンス制御回路１２は、Ｐレジスタ１３を有している。Ｐレジスタ１３は、シーケンス制御回路１２がＤレジスタ１１のいずれのビットを参照しているかを確認するためのカウント値が格納される。Ｐレジスタは、例えばＤレジスタ１１が１０２４ビットであった場合、１０ビットのカウント値を格納できればよい。
【００２５】
シーケンス制御回路１２は、演算開始信号ｂの値を切り替えて乗算剰余演算器２１に演算開始を指示するとともに、乗算剰余演算器２１から動作ステータス信号ａを受けることで乗算剰余演算器２１との間で演算の経過情報を送受信する。また、経過情報に基づき演算選択信号ｍの値を切り替えることで、乗算剰余演算器２１に第１の演算と第２の演算とを交互に実行させる。更に、Ｄレジスタ１１を順次参照し、参照したＤレジスタ１１の値に基づきダミー演算信号ｃの値を切り替える。
【００２６】
シーケンス制御回路１２は、例えば、次のように演算選択信号ｍ及びダミー演算信号ｃを制御する。演算選択信号ｍは、第１の演算を行なう期間において"０"とされ、第２の演算を行なう期間においては"１"とされる。また、ダミー演算信号ｃは、乗算剰余演算器２１が第１の演算を行なっている場合、参照しているＤレジスタ１１の値に関わらず"０"とされる。一方、乗算剰余演算器２１が第２の演算を行なっている場合、ダミー演算信号ｃは、参照しているＤレジスタ１１の値が"１"であれば"０"とされ、Ｄレジスタ１１の値が"０"であれば"１"とされる。
【００２７】
次に、図２にべき乗剰余演算器１の動作を示すフローチャートを示す。図２を参照してべき乗剰余演算器１の動作について説明する。べき乗剰余演算器１は、演算の初期状態として、Ｙレジスタ２６に格納される値を１とし、Ｐレジスタ１３に格納される値を１０２４とする（ステップＳ１）。また、図示しないが、Ｘレジスタ２４には演算に用いる新たな入力値Ｘが格納され、Ｎレジスタには演算に用いる除数Ｎが格納される。
【００２８】
続いて、ステップＳ２において、制御回路１０は、演算選択信号ｍを"０"とする。これによって、第２の選択回路２３は、信号ｉを選択して出力する。これによって、Ｂレジスタ２８には、Ｙレジスタ２６に格納されている値が格納される。このとき、Ａレジスタ２７には、Ｙレジスタ２６に格納されている値が格納される。
【００２９】
Ａレジスタ２７とＢレジスタ２８に値が格納されると、制御回路１０は、ダミー演算信号ｃを"０"とし（ステップＳ３）、演算開始信号ｂを"１"とする（ステップＳ４）。そして、演算開始信号ｂが"１"となることによって、乗算剰余演算器２１は演算を開始する（ステップＳ５）。このステップＳ５では、乗算剰余演算器２１は、Ｙ×ＹｍｏｄＮを演算する。つまり、ステップＳ５で乗算剰余演算器２１が行なう演算は第１の演算である。そして、乗算剰余演算器２１は、演算が完了するまで動作ステータス信号ａを"１"のまま保持する（ステップＳ６）。
【００３０】
乗算剰余演算器２１における演算が完了すると動作ステータス信号ａが"０"となるため、制御回路１０は、演算開始信号ｂを"０"とする（ステップＳ７）。そして、ステップＳ３において、ダミー演算信号ｃが"０"とされているため、第１の選択回路２２は乗算剰余演算器２１が出力する信号ｇを選択する。そのため、Ｙレジスタ２６には、乗算剰余演算器２１の演算結果が格納され、Ｙ＝Ｙ×ＹｍｏｄＮとなる（ステップＳ８）。ステップＳ２〜ステップＳ８が第１の演算に関する処理になる。
【００３１】
続いて、制御回路１０は、演算選択信号ｍを"１"とする。これによって、第２の選択回路２３は信号ｋを選択し、Ｂレジスタ２８にはＸレジスタ２４に格納されている新たな入力値Ｘが格納される（ステップＳ９）。このとき、Ａレジスタ２７にはステップＳ８でＹレジスタ２６に格納された値のコピーが格納される。
【００３２】
次に、制御回路１０は、Ｄレジスタ１１のＰビット目に格納されているビットの値を参照する（ステップＳ１０）。制御回路１０は、ステップＳ１０にて参照したビットの値が"１"である場合、ダミー演算信号ｃを"０"とする（ステップＳ１１）。一方、制御回路１０は、ステップＳ１０で参照したビットの値が"０"であった場合、ダミー演算信号ｃを"１"とする（ステップＳ１２）。
【００３３】
制御回路１０は、ダミー演算信号ｃの値を確定した後、演算開始信号ｂの値を"１"とする（ステップＳ１３）。ステップＳ１３にて、演算開始信号ｂの値が"１"となるのに応じて、乗算剰余演算器２１は、演算を開始する（ステップＳ１４）。ステップＳ１４にて行なわれる演算は、Ｙ×ＸｍｏｄＮである。つまり、ステップＳ１４で乗算剰余演算器２１が行なう演算は第２の演算である。そして、乗算剰余演算器２１は、演算が完了するまで動作ステータス信号ａを"１"のまま保持する（ステップＳ１５）。
【００３４】
乗算剰余演算器２１における演算が完了すると動作ステータス信号ａが"０"となるため、制御回路１０は、演算開始信号ｂを"０"とする（ステップＳ１６）。そして、ステップＳ１１において、ダミー演算信号ｃが"０"とされている場合、第１の選択回路２２は乗算剰余演算器２１が出力する信号ｇを選択する。そのため、Ｙレジスタ２６には、乗算剰余演算器２１の演算結果が格納され、Ｙ＝Ｙ×ＸｍｏｄＮとなる（ステップＳ１８）。一方、ステップＳ１２において、ダミー演算信号ｃが"１"とされている場合、第１の選択回路２２はＡレジスタ２７が出力する信号ｄを選択する。そのため、Ｙレジスタ２６には、Ａレジスタ２７に格納されている前周期の演算結果（例えばステップＳ８においてＹレジスタ２６に格納された値）が書き戻され、Ｙ＝Ｙ×ＹｍｏｄＮとなる（ステップＳ１９）。ステップＳ９〜ステップＳ１８（又はステップＳ１９）が第２の演算に関する処理になる。
【００３５】
そして、Ｐレジスタ１３に格納されている値を判定する（ステップＳ２０）。ステップＳ２０において、Ｐレジスタに格納されている値が"０"よりも大きければ、Ｐレジスタ１３に格納されている値を１つ減算し再びステップＳ２の処理に戻る（ステップＳ２１）。一方、ステップＳ２０において、Ｐレジスタの値が"０"であった場合、べき乗剰余演算器１は、演算を終了する。つまり、べき乗剰余演算器１は、べき乗を示す値のビット長に応じて第１の演算と第２の演算を繰り返す。そして、第２の演算を行なった後、参照しているビットの値に応じて、第２の演算の結果をＹレジスタ２６に格納するか、前周期のＹレジスタ２６の値を再度書き戻すかを決定する。
【００３６】
上記説明より、本実施の形態にかかるべき乗剰余演算器１は、制御回路１０が参照しているビットの値に応じて第１の選択回路２２を制御することで、Ｙレジスタ２６に前周期の演算結果を書き戻すか、乗算剰余演算器２１の演算結果を書き込むか、を切り替える。つまり、べき乗剰余演算器１は、参照しているビットの値が１である場合は、Ｙレジスタ２６に乗算剰余演算器２１の演算結果を書き込む。一方、参照しているビットの値が"０"であった場合は、乗算剰余演算器２１の演算結果を廃棄して前周期の演算結果をＹレジスタ２６に書き戻す。これによって、べき乗剰余演算器１は、第２の演算において行なった演算がダミー演算であった場合であっても、前周期の演算結果をＹレジスタ２６に書き込むことでダミー演算後にＹレジスタ２６に格納されている値の整合性を保つことができる。そして、べき乗剰余演算器１は、ダミー演算後のＹレジスタへの書き込みにおける消費電力を発生させ、ダミー演算が行なわれる場合と行なわれない場合との消費電力の差を低減する。また、べき乗剰余演算器１は、参照するビットの値に関わらず第２の演算を行なうため、べき数の値の違いによる計算時間及び消費電力の差を低減することができる。これらのことより、べき乗剰余演算器１は、演算内容によらず計算時間及び消費電力をほぼ一定に保つことができるため、高い耐タンパー性を実現できる。
【００３７】
また、べき乗剰余演算器１は、第２の演算の結果を廃棄する場合、乗算剰余演算器２１の計算結果に代えて、前周期の演算結果をＹレジスタ２６に書き戻すため、ダミー演算の結果を書き込むためのダミーレジスタが必要ない。つまり、べき乗剰余演算器１は、ダミーレジスタを設けることなく、演算の整合性及び耐タンパー性の向上が可能である。このことから、べき乗剰余演算器１は、高い耐タンパー性を確保しながら、回路規模を小さくすることが可能である。
【００３８】
実施の形態２
実施の形態２にかかるべき乗剰余演算器２のブロック図を図３に示す。図３に示すように、べき乗剰余演算器２は、制御回路１０に代えて制御回路３０を有している。なお、べき乗剰余演算器２において制御回路３０以外の部分についてはべき乗剰余演算器１と同じ構成であるため説明を省略する。
【００３９】
制御回路３０は、記憶装置３１、中央演算処理装置（Central Processing Unit：ＣＰＵ）３２、動作設定レジスタ３３を有している。制御回路３０は、ＣＰＵ３２が記憶装置３１に格納されたプログラムを実行した結果に基づき乗算剰余演算器２１、第１の選択回路２２、第２の選択回路２３を制御する。なお、本実施の形態では、計算に用いられる数式はプログラムによって定義され、ＣＰＵ３２がプログラムに基づきＸレジスタ２４、Ｎレジスタ２５にそれぞれ値を格納する。また、計算に用いるべき数は、プログラム上で定義され、二進数の値として記憶装置３１に格納される。つまり、記憶装置３１は、べき数格納部として機能する。そして、ＣＰＵ３２は記憶装置３１に格納されているべき数を示すビットの値を順次参照して第１の選択回路２２を制御する。
【００４０】
また、制御回路３０は、乗算剰余演算器２１、第１の選択回路２２、第２の選択回路２３を制御する場合、動作設定レジスタ３３に制御用の値を格納する。そして、乗算剰余演算器２１、第１の選択回路２２、及び、第２の選択回路２３は、動作設定レジスタ３３に格納された値に基づき動作する。なお、動作設定レジスタ３３には、乗算剰余演算器２１、第１の選択回路２２、第２の選択回路２３が参照するレジスタが個別に定義されている。
【００４１】
上記説明より、べき乗剰余演算器２は、制御回路の別の形態を示すものであり、実施の形態１と同様の動作を行なうため、高い耐タンパー性を実現できる。また、システムにおいて記憶装置３１及びＣＰＵ３２を有している場合、べき乗剰余演算器２は、制御回路として記憶装置３１及びＣＰＵ３２を流用できるため、べき乗剰余演算器１における制御回路１０は必要ない。つまり、べき乗剰余演算器２は、べき乗剰余演算器１よりも回路規模を削減することが可能である。
【００４２】
なお、本発明は上記実施の形態に限られたものではなく、趣旨を逸脱しない範囲で適宜変更することが可能である。例えば、Ｘレジスタ２４、Ｎレジスタ２５、Ｙレジスタ２６、Ａレジスタ２７、Ｂレジスタ２８は、個別に設けられたレジスタではなく、格納する値に応じて一体に形成されたレジスタの領域をそれぞれ定義したものとして設けることも可能である。
【図面の簡単な説明】
【００４３】
【図１】実施の形態１にかかるべき乗剰余演算器のブロック図である。
【図２】実施の形態１にかかるべき乗剰余演算器の動作を示すフローチャートである。
【図３】実施の形態２にかかるべき乗剰余演算器のブロック図である。
【図４】従来例１にかかるべき乗剰余演算器のブロック図である。
【符号の説明】
【００４４】
１、２    べき乗剰余演算器
１０、３０    制御回路
１１    Ｄレジスタ
１２    シーケンス制御回路
１３    Ｐレジスタ
２１    乗算剰余演算器
２２、２３    選択回路
２４    Ｘレジスタ
２５    Ｎレジスタ
２６    Ｙレジスタ
２７    Ａレジスタ
２８    Ｂレジスタ
３１    記憶装置
３２    ＣＰＵ
３３    動作設定レジスタ
ａ    動作ステータス信号
ｂ    演算開始信号
ｃ    ダミー演算信号
ｍ    演算選択信号
ｄ〜ｌ、ｎ    信号
【図１】
2009008993.tif 000003
【図２】
2009008993.tif 000004
【図３】
2009008993.tif 000005
【図４】
2009008993.tif 000006