モンゴメリ乗算回路、ＲＳＡ暗号回路、及び、ＩＣカード
【課題】 回路規模及び消費電力を増大させることなく外部からの消費電力解析が困難なセキュリティ性の高いモンゴメリ乗算回路を提供する。
【解決手段】 モンゴメリ乗算回路１は、メモリ回路１１、算術回路１０、及び、メモリ回路１１と算術回路１０間のデータの入出力を所定のアルゴリズムに基づいて制御してモンゴメリ乗算を実現する制御回路１２を備えて構成され、制御回路１２が、アルゴリズムを２以上有し、２以上のアルゴリズムの内の１つをランダムに選択して、選択した１つのアルゴリズムに基づいてモンゴメリ乗算の実行に係る制御を行う。
【解決手段】 モンゴメリ乗算回路１は、メモリ回路１１、算術回路１０、及び、メモリ回路１１と算術回路１０間のデータの入出力を所定のアルゴリズムに基づいて制御してモンゴメリ乗算を実現する制御回路１２を備えて構成され、制御回路１２が、アルゴリズムを２以上有し、２以上のアルゴリズムの内の１つをランダムに選択して、選択した１つのアルゴリズムに基づいてモンゴメリ乗算の実行に係る制御を行う。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、モンゴメリ乗算回路、及び、モンゴメリ乗算回路を用いて暗号化処理及び復号化処理を行う暗号回路に関し、特に、消費電力解析による秘密情報を暴露する攻撃から情報を守るセキュリティ機能を向上させたモンゴメリ乗算回路及び暗号回路に関する。
【背景技術】
【０００２】
近年、ネットワーク技術の進歩により様々なことがネットワーク上で実現可能となってきた。例えば、インターネット等のネットワークを利用して契約や決済を行う電子商取引として、ネットワーク上で商品を販売する電子商店による商取引（企業と消費者間の商取引）があり、消費者は、自宅のパソコンからインターネットを経由して電子商店のＷｅｂサイトを閲覧して商品を選択し、決済方法を指定して購入することができる。
【０００３】
このような電子商取引では、成りすましや盗聴、改ざんの防止等のセキュリティの確保が課題となっており、例えば、成りすましを防止するための認証技術の一つとして、公開鍵暗号が利用されている。ここで、公開鍵暗号は、暗号化のための暗号化鍵と復号化のための復号化鍵の異なる２つの鍵を用いるものであり、暗号化鍵からの復号化鍵の推測、及び、暗号文の解読は、極めて困難、或いは、不可能となっている。鍵の所有者は、暗号化鍵（公開鍵）を公開し、復号化鍵（秘密鍵）を第三者に知られないように管理することにより、公開鍵を利用する相手側の情報が第三者に知られないようにすることができる。
【０００４】
例えば、上述した電子商店と消費者の間の商取引では、電子商店が、暗号化鍵（公開鍵）を一般に公開し、復号化鍵（秘密鍵）を第三者に知られないように管理する。消費者は、電子商店側が公開している暗号化鍵（公開鍵）を利用して、商取引に関する情報を暗号化して電子商店に送信する。電子商店は、消費者から受け取った暗号文を復号化鍵（秘密鍵）で復号化し、消費者に対し商品の販売を行う。鍵の所有者である電子商店は、復号化鍵（秘密鍵）を第三者に知られないように管理することにより、商取引に関する情報が第三者に知られるのを防止でき、消費者の個人情報等が第三者に知られるのを防止することができる。
【０００５】
公開鍵暗号としては、例えば、ＲＳＡ（Ｒｉｖｅｓｔ Ｓｈａｍｉｒ Ａｄｌｅｍａｎ）暗号がある。ＲＳＡ暗号は、解読するために、非常に大きな整数の合成体の素因数分解が必要であり、コンピュータによる解読であっても、現実的な計算時間での解読が困難であり、非常に大きな整数の合成体の素因数分解が困難であることに安全性の根拠を置く暗号方式である。
【０００６】
以下、ＲＳＡ暗号の暗号化方法及び復号化方法について簡単に説明する。公開鍵（ｅ、ｎ）を用いて平文Ｍを暗号化し、暗号文Ｃを生成する場合、暗号文Ｃは、以下の数１により生成される。
【０００７】
［数１］
Ｃ＝Ｍｅｍｏｄｎ
（但し、０≦Ｍ＜ｎ）
【０００８】
秘密鍵（ｄ、ｎ）を用いて暗号文Ｃを復号化し、平文Ｍを生成する場合、平文Ｍは、以下の数２により生成される。
【０００９】
［数２］
Ｍ＝Ｃｄｍｏｄｎ
【００１０】
尚、公開鍵（ｅ、ｎ）、秘密鍵（ｄ、ｎ）には、以下の数３の関係がある。
【００１１】
［数３］
ｎ＝ｐ×ｑ （ｐ、ｑは素数）
ｅ×ｄ≡１ｍｏｄ（ｐ−１）（ｑ−１）
【００１２】
具体的には、例えば、ｐ＝３、ｑ＝１１、ｅ＝３、ｄ＝７とすると、平文Ｍ＝７を暗号化して得られる暗号文Ｃは、数１より、Ｃ＝７3ｍｏｄ（３×１１）＝３４３ｍｏｄ３３＝１３となる。
【００１３】
また、暗号文Ｃ＝１３を復号化して得られる平文Ｍは、数２より、Ｍ＝１３７ｍｏｄ３３＝６２７４８５１７ｍｏｄ３３＝７となる。従って、数１及び数２による暗号化及び復号化は、正しく行われることが分かる。
【００１４】
ところで、上述したＲＳＡ暗号では、数１及び数２に示すように、べき乗演算、剰余演算を行っている。一般的に、鍵や平文は、１０２４ビット以上の非常に大きな桁数となるため、演算装置上で数１及び数２をそのまま用いて暗号化及び復号化を行うと、桁あふれを起こす可能性がある。
【００１５】
このため、ＲＳＡ暗号の暗号化及び復号化では、例えば、桁あふれしない剰余演算の手法の一例であるモンゴメリ乗算が用いられる。モンゴメリ乗算では、Ｎビットの剰余算をＮビットのメモリ空間で行うことができる。
【００１６】
以下、モンゴメリ乗算について簡単に説明する。ＲＳＡ暗号の数１に示す暗号文Ｃの生成式の右辺（Ｍｅｍｏｄｎ）は、以下の数４に示す逐次計算で求められる。即ち、数５に示す演算を繰り返し行うことで計算できる。
【００１７】
［数４］
Ｍ２ｍｏｄｎ＝Ｍ×Ｍｍｏｄｎ，
Ｍ３ｍｏｄｎ＝Ｍ×Ｍ２ｍｏｄｎ，
…
Ｍｅｍｏｄｎ＝Ｍ×Ｍｅ−１ｍｏｄｎ
【００１８】
［数５］
γ＝α×βｍｏｄｎ
【００１９】
ここで、モンゴメリ乗算では、コンピュータ上における乗算のため、定数Ｒ＝２Ｎを用いる。数５の両辺にＲを掛けてｍｏｄｎをとると、数６となる。ここで、数７に示すように、Ｚ、Ａ、Ｂを夫々規定すると、モンゴメリ乗算の演算式は、以下の数８で表される。尚、モンゴメリ乗算の演算アルゴリズムについては、下記の非特許文献１に詳細な記載がある。
【００２０】
［数６］
γＲｍｏｄｎ＝αＲ×βＲ×Ｒ−１ｍｏｄｎ
【００２１】
［数７］
Ｚ＝γＲｍｏｄｎ，
Ａ＝αＲｍｏｄｎ，
Ｂ＝βＲｍｏｄｎ
【００２２】
［数８］
Ｚ（Ａ，Ｂ）＝Ａ×Ｂ×Ｒ−１ｍｏｄｎ
【００２３】
数８に示すモンゴメリ乗算を繰り返し実行しながら、数１に示す暗号文Ｃの生成式を実現する方法を左バイナリ法と言い、以下に示すＳｔｅｐ１乃至Ｓｔｅｐ４の処理工程となる。尚、以下の処理工程において、Ｎ桁の２進数ｅを、ｅ＝｛ｅＮ−１，ｅＮ−２，…，ｅ１，ｅ０｝と表現する。ｅｉ（ｉ＝０〜Ｎ−１）はＬＳＢ側（左側）から（ｉ＋１）桁目のビット値である。
【００２４】
Ｓｔｅｐ１： Ａ：＝Ｍ×Ｒｍｏｄｎ
Ｓｔｅｐ２： Ｘ：＝１×Ｒｍｏｄｎ
Ｓｔｅｐ３： ｆｏｒ ｉ＝Ｎ−１ ｄｏｗｎ ｔｏ ０
Ｘ：＝Ｚ（Ｘ，Ｘ）
ｉｆ ｅｉ＝１ ｔｈｅｎ Ｘ：＝Ｚ（Ｘ，Ａ）
Ｓｔｅｐ４： Ｃ：＝Ｚ（Ｘ，１）
【００２５】
ここで、上記Ｓｔｅｐ３において、ｅｉ＝０の時は、Ｚ（Ｘ，Ｘ）だけの演算が行われ、ｅｉ＝１の時は、Ｚ（Ｘ，Ｘ）とＺ（Ｘ，Ａ）の２回の演算が行われる点が重要となる。
【００２６】
もし、Ｚ（Ｘ，Ｘ）とＺ（Ｘ，Ａ）の２種類の演算が消費電力波形から判別可能となると、暗号鍵Ｅのビット系列が解読できることになる。つまり、如何にしてＺ（Ｘ，Ｘ）とＺ（Ｘ，Ａ）の２種類の演算を消費電力波形から判別できないようにすることがセキュリティ上重要となる。
【００２７】
Ｚ（Ｘ，Ｘ）とＺ（Ｘ，Ａ）の２種類の演算を判別する攻撃法としては、Ｚ（Ｘ，Ｘ）とＺ（Ｘ，Ａ）の入力値をメモリからロードする時間を見分ける方法がある。Ｚ（Ｘ，Ｘ）はＸという値を１つだけをメモリからロードするのに対して、Ｚ（Ｘ，Ａ）はＸとＡの２つの値をメモリからロードする。このロード時間に差があれば容易に鍵情報を推測することができる。当該攻撃法に対しては、Ｚ（Ｘ，Ｘ）の演算でもＸのロードを２回行うことにより容易に対処できる。
【００２８】
しかし、解析装置の進歩により、Ｚ（Ｘ，Ｘ）とＺ（Ｘ，Ａ）のデータを多数取り、消費電力の僅かな違いを判別し秘密情報を割り出すＤＰＡ（電力差分解析）と呼ばれる攻撃が行われる可能性がある。
【００２９】
下記の特許文献１では、左バイナリ法において、Ｚ（Ｘ，Ｘ）を実行する乗算剰余演算部と、Ｚ（Ｘ，Ａ）を実行する乗算剰余演算部を２つ設けた場合に、Ｚ（Ｘ，Ｘ）の演算はべき指数のビット値に関係なく常時実行されるのに対して、Ｚ（Ｘ，Ａ）の演算はべき指数のビット値が１の桁のみで実行されるので、Ｚ（Ｘ，Ｘ）とＺ（Ｘ，Ａ）の２つの乗算剰余演算部の回路動作を外部から観測することで、べき指数の値が推測でき、暗号演算回路として耐タンパー性が低い点を指摘し、その対策として、異なる２つの底のべき乗剰余演算を並列に実行する際に、図１３に示すように、夫々のべき乗剰余演算に係るＺ（Ｘ，Ｘ）を実行する乗算剰余演算部を１つずつ設け、夫々のべき乗剰余演算に係るＺ（Ｘ，Ａ）を実行する乗算剰余演算部を１つだけ設けて、２つのべき乗剰余演算で、夫々の演算のべき指数のビット値が１の桁のみで実行するように、交互或いはランダムな順番で共用する構成とすることで、夫々のべき乗剰余演算におけるべき指数の値の推測を困難にしている。
【先行技術文献】
【特許文献】
【００３０】
【特許文献１】特開２００１−２０２０１５号公報
【非特許文献】
【００３１】
【非特許文献１】C. K. Koc, "Analyzing and Computing MontgomeryMultiplication Algorithms", IEEE Micro, 16(3): 26-33, June 1996.
【発明の概要】
【発明が解決しようとする課題】
【００３２】
上記特許文献１による対策は、Ｚ（Ｘ，Ｘ）とＺ（Ｘ，Ａ）の２つの演算に対して、乗算剰余演算部を夫々設け、異なる２つの底のべき乗剰余演算を並列に実行する際には有効な手段と考えられるが、Ｚ（Ｘ，Ｘ）とＺ（Ｘ，Ａ）の２つの演算に対して、乗算剰余演算部を夫々設けない場合や、１つのべき乗剰余演算だけを行う場合には、乗算剰余演算部を３つ設ける必要がないため、回路規模が大きくなり、消費電力も増大し、ＩＣカード用ＬＳＩのように小さなチップで非常に少ない消費電力で動作する必要がある場合には、有効な手段とは言えない。
【００３３】
本発明は、モンゴメリ乗算を繰り返し実行する左バイナリ法による暗号処理における上記問題点に鑑みてなされたものであり、その目的は、回路規模及び消費電力を増大させることなく外部からの消費電力解析が困難なセキュリティ性の高いモンゴメリ乗算回路及びＲＳＡ暗号回路を提供することにある。
【課題を解決するための手段】
【００３４】
上記目的を達成するため、本発明では、メモリ回路、算術回路、及び、前記メモリ回路と前記算術回路間のデータの入出力を所定のアルゴリズムに基づいて制御してモンゴメリ乗算を実現する制御回路を備えてなるモンゴメリ乗算回路であって、前記制御回路が、前記アルゴリズムを２以上有し、２以上の前記アルゴリズムの内の１つをランダムに選択して、選択した１つの前記アルゴリズムに基づいて前記モンゴメリ乗算の実行に係る制御を行うことを特徴とするモンゴメリ乗算回路を提供する。
【００３５】
上記特徴のモンゴメリ乗算回路によれば、２以上のアルゴリズムの内の１つをランダムに選択して、選択したアルゴリズムに基づいてモンゴメリ乗算が実行されるので、実行毎に、アルゴリズムがランダムに異なるため、当該アルゴリズムの違いに応じて当該実行に係る消費電力も異なる結果、上記特徴のモンゴメリ乗算回路を用いてモンゴメリ乗算を繰り返し実行した場合に、被乗数と消費電力の関係が都度ランダムに変化し、消費電力の変化が複雑化し、外部からの消費電力解析が極めて困難となる。また、１つのモンゴメリ乗算回路に２以上のアルゴリズムを設け、それらをランダム選択するだけの構成で良いので、回路規模及び消費電力を大幅に増大させることなくセキュリティ性を向上させることが可能となる。
【００３６】
更に好ましくは、上記特徴のモンゴメリ乗算回路は、前記制御回路が、前記２以上のアルゴリズムの各別に規定するマイクロコードを格納するコードメモリと、前記メモリ回路に対するデータの入出力制御と前記算術回路で行う算術演算の選択を行うシーケンサ回路と、乱数発生回路を備え、前記乱数発生回路が発生した乱数値に基づいて前記マイクロコードの１つを選択し、選択されたマイクロコードに沿って、前記シーケンサ回路が、前記メモリ回路と前記算術回路に対する制御を実行するように構成される。
【００３７】
斯かる構成のモンゴメリ乗算回路によれば、マイクロコードを格納するコードメモリの記憶容量を、追加されたアルゴリズムのマイクロコード分だけ大きく確保するだけで、アルゴリズム毎に専用のハードウェア回路を設ける場合に比べて回路規模を小さく抑制できるとともに、簡単な回路構成で、２以上のアルゴリズムの内の１つをランダムに選択して、選択したアルゴリズムに基づいてモンゴメリ乗算が実行できるようになる。
【００３８】
更に好ましくは、上記特徴のモンゴメリ乗算回路は、前記算術回路が、乗算器と加算器からなる積和演算回路で構成されている。
【００３９】
斯かる構成のモンゴメリ乗算回路によれば、モンゴメリ乗算を積和演算の繰り返しで実現するＣＩＯＳ（Ｃｏａｒｓｅｌｙ Ｉｎｔｅｇｒａｔｅｄ Ｏｐｅｒａｎｄ Ｓｃａｎｎｉｎｇ）法、及び、ＦＩＯＳ（Ｆｉｎｅｌｙ Ｉｎｔｅｇｒａｔｅｄ Ｏｐｅｒａｎｄ Ｓｃａｎｎｉｎｇ）法等の複数のアルゴリズムを利用して、２以上のアルゴリズムの内の１つをランダムに選択して、選択したアルゴリズムに基づいてモンゴメリ乗算が実行できるようになる。また、モンゴメリ乗算を積和演算の繰り返しで実現するアルゴリズムでは、除算を用いずに剰余演算を実行できるため、計算コストを大幅に削減できる。
【００４０】
更に、上記目的を達成するため、本発明では、上記特徴のモンゴメリ乗算回路を備え、左バイナリ法による暗号処理過程で実行するモンゴメリ乗算を、前記モンゴメリ乗算回路を用い、モンゴメリ乗算のアルゴリズムを２以上の前記アルゴリズムの中からランダムに選択して実行することを特徴とするＲＳＡ暗号回路を提供する。
【００４１】
上記特徴のＲＳＡ暗号回路によれば、左バイナリ法による暗号処理過程で実行するモンゴメリ乗算が、実行の都度、被乗数と消費電力の関係がランダムに変化するため、消費電力の変化が複雑化し、外部からの消費電力解析が極めて困難となり、回路規模及び消費電力を大幅に増大させることなくセキュリティ性を向上させることが可能となる。
【００４２】
更に、上記目的を達成するため、本発明では、上記特徴のＲＳＡ暗号回路を備えてなることを特徴とするＩＣカードを提供する。これにより、ＩＣカードに搭載するＬＳＩの回路規模及び消費電力を増大させることなく、消費電力解析が極めて困難なＲＳＡ暗号回路を搭載したセキュリティ性の高いＩＣカードが実現できる。
【００４３】
更に、上記目的を達成するため、本発明では、左バイナリ法によるＲＳＡ暗号処理過程で繰り返し実行するモンゴメリ乗算を、モンゴメリ乗算のアルゴリズムを２以上の前記アルゴリズムの中からランダムに選択して実行することを特徴とするＲＳＡ暗号処理方法を提供する。
【００４４】
上記特徴のＲＳＡ暗号処理方法によれば、左バイナリ法によるＲＳＡ暗号処理過程で繰り返し実行するモンゴメリ乗算が、実行の都度、被乗数と消費電力の関係がランダムに変化するため、消費電力の変化が複雑化し、外部からの消費電力解析が極めて困難となり、回路規模及び消費電力を大幅に増大させることなくセキュリティ性を向上させることが可能となる。
【図面の簡単な説明】
【００４５】
【図１】本発明に係るモンゴメリ乗算回路の一実施形態における一回路構成例を示すブロック図である。
【図２】ＣＩＯＳ法によるモンゴメリ乗算アルゴリズムのプログラムコードを示す図である。
【図３】ＦＩＯＳ法によるモンゴメリ乗算アルゴリズムのプログラムコードを示す図である。
【図４】ＣＩＯＳ法によるモンゴメリ乗算アルゴリズムの演算処理を簡略的に図解して説明する図である。
【図５】ＦＩＯＳ法によるモンゴメリ乗算アルゴリズムの演算処理を簡略的に図解して説明する図である。
【図６】同期式１ポートＲＡＭの概略構成例を示す概略ブロック図である。
【図７】同期式１ポートＲＡＭの読み出し処理と書き込み処理の各動作を説明するためのタイミング図である。
【図８】本発明に係るＲＳＡ暗号回路の一実施形態における一回路構成例を示すブロック図である。
【図９】本発明に係るＲＳＡ暗号回路の処理アルゴリズムを示すフローチャートである。
【図１０】本発明に係るモンゴメリ乗算回路を用いて構成されたＲＳＡ暗号回路を搭載したＩＣカードの概略部分構成例を示す概略部分ブロック図である。
【図１１】本発明に係るモンゴメリ乗算回路の別実施形態における一回路構成例を示すブロック図である。
【図１２】本発明に係るＲＳＡ暗号回路の別実施形態における一回路構成例を示すブロック図である。
【図１３】従来技術における左バイナリ法によるＲＳＡ暗号処理の乗算剰余演算に係る回路構成例を示すブロック図である。
【発明を実施するための形態】
【００４６】
本発明に係るモンゴメリ乗算回路の実施の形態につき、図面に基づいて説明する。
【００４７】
図１に、モンゴメリ乗算回路１の回路構成を示す。モンゴメリ乗算回路１は、図１に示すように、積和演算回路からなる算術回路１０と、第１メモリＭ１と第２メモリＭ２と被乗数格納用レジスタＲ１とキャリーレジスタＲ２からなるメモリ回路１１と、算術回路１０とメモリ回路１１間のデータの入出力を制御してモンゴメリ乗算を実現する制御回路１２を備えて構成されている。
【００４８】
算術回路１０は、ビット幅ｒの第１変数Ｘ、第２変数Ｙ、第３変数Ｚ、第４変数Ｃを受け付け、第３変数Ｚと、第１変数Ｘと第２変数Ｙの積算結果（Ｘ×Ｙ）と、第４変数Ｃの和（Ｆ＝Ｚ＋Ｘ×Ｙ＋Ｃ）を演算してビット幅２ｒの演算結果データＦを出力する積和演算処理を行う。つまり、算術回路１０は、第１変数Ｘと第２変数Ｙの乗算を行う乗算器と、第３変数Ｚと、第１変数Ｘと第２変数Ｙの積算結果（Ｘ×Ｙ）と、第４変数Ｃの加算を行う加算器で構成されている。
【００４９】
第１メモリＭ１は、ビット幅ｒ、要素数ｓ＋１の中間結果格納用配列ｔを格納する記憶領域を備えた同期式１ポートＲＡＭで構成され、中間結果格納用配列ｔの各要素を第３変数Ｚとして積和演算回路１０に出力する。
【００５０】
第２メモリＭ２は、ビット幅ｒ、要素数ｓの第１配列ａ［ｓ−１：０］、第２配列ｂ［ｓ−１：０］、及び、第３配列ｎ［ｓ−１：０］と、ビット幅ｒの被乗算変数ｍを格納する記憶領域を備えた同期式１ポートＲＡＭで構成され、第１配列ａ［ｓ−１：０］の各要素または被乗算変数ｍを第１変数Ｘとして積和演算回路１０に出力する。
【００５１】
被乗数格納用レジスタＲ１は、第２メモリＭ２から第２配列ｂ［ｓ−１：０］または第３配列ｎ［ｓ−１：０］を要素単位で受け付けて記憶し、第２変数Ｙとして積和演算回路１０に出力する。また、キャリーレジスタＲ２は、演算結果データＦの内の上位ｒビットからなる上位ビット側データＦＨを受け付けて記憶し、第４変数Ｃとして積和演算回路１０に出力する。
【００５２】
制御回路１２は、２以上のアルゴリズムの各別に規定するマイクロコードを格納するコードメモリ１３と、メモリ回路１１に対するデータの入出力制御と算術回路１０で行う算術演算の選択を行うシーケンサ回路１４と、乱数発生回路１５を備えて構成される。モンゴメリ乗算が起動されると、制御回路１２において、乱数発生回路１５が乱数値を発生し、当該乱数値に基づいてマイクロコードの１つが選択され、選択されたマイクロコードに沿って、シーケンサ回路１４が、メモリ回路１１と算術回路１０に対する制御を実行する。
【００５３】
本実施形態では、シーケンサ回路１４は、図２及び図３に示すプログラムコードで用いられるカウント値の内、メインループ処理の処理回数を制御する第１ループカウント値ｉを生成する第１ループカウンタ回路１６と、図２及び図３に示すプログラムコードで用いられるカウント値の内、サブループ処理の処理回数を制御する第２ループカウント値ｊを生成する第２ループカウンタ回路１７を備えて構成されている。
【００５４】
算術回路１０、第１メモリＭ１、第２メモリＭ２、被乗数格納用レジスタＲ１、キャリーレジスタＲ２の各バス幅は、第１配列ａ、第２配列ｂ、第３配列ｎ、被乗算変数ｍの各ビット幅と同じｒビットで、一般的には１６ビット或いは３２ビットである。
【００５５】
図２及び図３に、コードメモリ１３に格納されるＣＩＯＳ法とＦＩＯＳ法の２つのアルゴリズムの各プログラムコードを示す。
【００５６】
図２及び図３に示すプログラムコードにおける変数ｔ［ｊ］が第１メモリＭ１の中間結果格納用配列ｔに格納される各要素であり、各変数ａ［ｊ］，ｂ［ｉ］，ｎ［ｊ］が第１メモリＭ１の第１配列ａ、第２配列ｂ、及び、第３配列ｎに格納される各要素である。変数ａ［ｊ］をｊ＝ｓ−１からｊ＝０まで順番に連接した変数が数８に示すモンゴメリ乗算の変数Ａに相当し、変数ｂ［ｉ］をｉ＝ｓ−１からｉ＝０まで順番に連接した変数が数８に示すモンゴメリ乗算の変数Ｂに相当し、変数ｎ［ｊ］をｊ＝ｓ−１からｊ＝０まで順番に連接した変数が数８に示すモンゴメリ乗算の変数ｎに相当する。更に、図２及び図３に示すプログラムコード中のＷは２ｒ（但しｒはバス幅）で定義される定数であり、ｎ’［０］は変数ｎの最下位ワードｎ［０］の２ｒを法とする逆数（−ｎ［０］−１）を意味する定数である。
【００５７】
図４に、図２に示すプログラムコードによるＣＩＯＳ法のモンゴメリ乗算を、ｓ＝４の場合を例に、簡略的に図解する。図４において、左側の乗算（ａ×ｂ［ｉ］）が、図２に示すプログラムコードの第１のサブループ内の（Ｃ，Ｓ）：＝ｔ［ｊ］＋ａ［ｊ］×ｂ［ｉ］＋Ｃを、中央の乗算（ｔ［０］×ｎ’［０］）が、図２に示すプログラムコードのメインループ内のｍ：＝ｔ［０］×ｎ’［０］ｍｏｄＷを、右側のｎ×ｍが、図２に示すプログラムコードのメインループ内の（Ｃ，Ｓ）：＝ｔ［０］＋ｍ×ｎ［０］を、夫々表現している。
【００５８】
図５に、図３に示すプログラムコードによるＦＩＯＳ法のモンゴメリ乗算を、ｓ＝４の場合を例に、簡略的に図解する。図５において、左側に、図３に示すプログラムコードの部分的な乗算（ｔ［ｉ］＝ａ×ｂ［ｉ］）によりｍ［ｉ］が得られる様子が図示されており、右側に、ｎ×ｍ［ｉ］の乗算結果と上記部分的な乗算結果ｔ［ｉ］の加算により、中間結果ｔ［ｉ＋１］が得られる様子が図示されている。
【００５９】
図２及び図３に示すように、当該各プログラムコードでは、モンゴメリ乗算が乗算と加算の繰り返しで実現されており、図１に示す回路構成の積和演算処理を行う算術回路１０を備えたモンゴメリ乗算回路１で処理可能である。
【００６０】
尚、コードメモリ１３に格納するアルゴリズムは、図１に示す回路構成のモンゴメリ乗算回路１で処理可能な、つまり、モンゴメリ乗算を乗算と加算の繰り返しで実現するアルゴリズムであれば、上記２つのアルゴリズムに限定されるものではなく、また、格納するアルゴリズム数も３以上であっても良い。尚、図２及び図３に示す各プログラムコードでモンゴメリ乗算が実現できることは、上記非特許文献１において説明されており公知であるので、詳細な説明は割愛する。
【００６１】
ところで、図２及び図３に示すプログラムコードの２つのアルゴリズムを比較すると、何れもｉループ（メインループ）とその内側にｊループ（サブループ）を備えた構造となっているが、ＣＩＯＳ法とＦＩＯＳ法では、サブループの個数及びその処理内容が異なっており、当該処理において実行されるメモリ回路１１の読み出し動作や書き込み動作におけるメモリ番地や読み出し及び書き込みに係るデータも異なり、それらのデータを用いた積和演算の入力値も異なるため、２つのアルゴリズム間では、実行中の消費電力波形が異なる。つまり、同じ結果が得られる演算を行っても外部に現れる消費電力波形が異なる。
【００６２】
本実施形態では、モンゴメリ乗算が起動されると、制御回路１２が、乱数発生回路１５が発生した乱数値に基づいて、２つのアルゴリズムの何れか一方をランダムに選択して実行する構成となっているため、外部から消費電力波形を観察しても、消費電力波形の違いが入力データの違いに依るものか、アルゴリズムの違いに依るものかを区別できない。従って、本実施形態のモンゴメリ乗算回路１を用いることで、モンゴメリ乗算を繰り返し実行しながら暗号文を生成する際に、多くの入力値に対する消費電力から統計的にデータの違いにより消費電力の違いを解析するＤＰＡ等の攻撃法に対して、有効な防御策となる。
【００６３】
次に、図１に示す回路構成のモンゴメリ乗算回路１の回路動作について、図２に示すＣＩＯＳ法のプログラムコードの実行を例に、簡単に説明する。
【００６４】
図６は、本実施形態の第１メモリＭ１及び第２メモリＭ２の概略構成例を示している。また、図７（ａ）は、本実施形態の第１メモリＭ１及び第２メモリＭ２の読み出し処理における動作タイミングを、図７（ｂ）は、本実施形態の第１メモリＭ１及び第２メモリＭ２の書き込み処理における動作タイミングを、夫々示している。同期式１ポートＲＡＭである第１メモリＭ１は、図７（ａ）に示すように、読み出し処理において、クロック信号ＣＬＫに同期して動作し、チップイネーブル信号ＣＥ＃がＬレベルの場合に、アドレス信号ＡＤによって示される記憶領域に記憶されたデータＤを、出力端子ＤＯＵＴから出力する。同様に、第１メモリＭ１は、図７（ｂ）に示すように、書き込み処理において、クロック信号ＣＬＫに同期して動作し、チップイネーブル信号ＣＥ＃がＬレベルの場合に、アドレス信号ＡＤによって示される記憶領域に、データ入力端子ＤＩＮから入力されたデータＤを書き込む。
【００６５】
モンゴメリ乗算回路１は、第２メモリＭ２から、第１ループカウンタ値ｉで示される第２配列ｂ［ｓ−１：０］の要素を読み出して被乗数格納用レジスタＲ１に格納する第１読み出し処理と、第２メモリＭ２から第２ループカウンタ値ｊで示される第１配列ａ［ｓ−１：０］の要素を読み出し、第１メモリＭ１から第２ループカウンタ値ｊで示される中間結果格納用配列ｔの要素を読み出し、被乗数格納用レジスタＲ１の値ＲＸを読み出し、キャリーレジスタＲ２の値ＲＣを読み出し、夫々、積和演算回路１０に入力する第２読み出し処理と、キャリーレジスタＲ２に上位ビット側データＦＨを書き込むと共に、第１メモリＭ１に、演算結果データＦの内の下位ｒビットからなる下位ビット側データＦＬを、第２ループカウンタ値ｊで示される中間結果格納用配列ｔの要素として書き込む書き込み処理と、を実行可能に構成され、第２読み出し処理、積和演算処理、書き込み処理、及び、第２ループカウンタ値ｊの更新を繰り返し実行する第１サブループ処理を、第１読み出し処理の実行後に実行する。
【００６６】
更に、モンゴメリ乗算回路１は、第３配列ｎ［ｓ−１：０］の各要素を対応する第１配列ａ［ｓ−１：０］の各要素として用いた第２読み出し処理、積和演算処理、書き込み処理、及び、第２ループカウンタ値ｊの更新を繰り返し実行する第２サブループ処理を実行する。
【００６７】
モンゴメリ乗算回路１は、図２に示すプログラムコードの実行のために、少なくとも、通常の第１読み出し処理、第１サブループ処理、被乗算変数ｍを第２配列ｂ［ｓ−１：０］の各要素として用いた第１読み出し処理、第２サブループ処理、及び、第１ループカウンタ値ｉの更新を、この順に繰り返し実行するメインループ処理を実行する。
【００６８】
次に、図１に示すモンゴメリ乗算回路１を用いた本発明に係るＲＳＡ暗号回路について説明する。図８に、ＲＳＡ暗号回路２の概略の回路構成を示す。本実施形態では、ＲＳＡ暗号回路２は、図９に示す左バイナリ法による暗号処理アルゴリズムを実行するＡＳＩＣ回路２０とモンゴメリ乗算回路１を備えて構成される。
【００６９】
図９は、本実施形態におけるＲＳＡ暗号回路２の左バイナリ法による処理アルゴリズムを示している。具体的には、ＲＳＡ暗号回路２は、先ず、平文Ｍ、定数Ｒ＝２Ｎを用いてモンゴメリ変換を行い（ステップ＃１０１）、暗号化鍵ｅ＝Ｋ［ｋ−１：０］を読み出し（＃１０２）、変数ｉの値をｋ−１に初期化する（ステップ＃１０３）。その後、モンゴメリ乗算回路１が、Ａ＝ＡＡＲ−１ｍｏｄｎで表される１つの入力値Ａの二乗のモンゴメリ乗算を行い（ステップ＃１０４）、Ｋ［ｉ］＝１の場合は（ステップ＃１０５で「ＹＥＳ」分岐）、モンゴメリ乗算回路１が、Ａ＝ＡＢＲ−１ｍｏｄｎで表される２つの入力値ＡとＢのモンゴメリ乗算を行う（ステップ＃１０６）。変数ｉ≠０の場合は（ステップ＃１０７で「ＮＯ」分岐）、ｉを１減算して（ステップ＃１０８）ステップ＃１０４に移行する。変数ｉ＝０の場合は（ステップ＃１０７で「ＹＥＳ」分岐）、Ｃ＝ＡＲ−１ｍｏｄｎで表されるモンゴメリ逆変換を行い（ステップ＃１０９）、処理を終了する。
【００７０】
図９に示す左バイナリ法による処理アルゴリズムでは、ステップ＃１０４とステップ＃１０６の２種類のモンゴメリ乗算が繰り返し実行されるが、本実施形態では、モンゴメリ乗算回路１が、ステップ＃１０４またはステップ＃１０６のモンゴメリ乗算を実行する毎に、そのモンゴメリ乗算を実行するためのアルゴリズムをランダムに選択するので、ステップ＃１０４とステップ＃１０６のモンゴメリ乗算実行時の消費電力波形がランダムに変化する。従って、同じＲＳＡ暗号処理を行っても、処理毎に消費電力波形が異なるため、ＤＰＡ等の電力波形解析による攻撃に対する防御が可能となる。
【００７１】
次に、図８に示すＲＳＡ暗号回路２を用いた本発明に係るＩＣカード３について説明する。図１０に、ＩＣカード３の概略の回路構成を示す。
【００７２】
ＩＣカード３は、本実施形態では、接触型ＩＣカードであり、図１０に示すように、ＩＣカードリーダとデータ通信を行うためのＩ／Ｏ（Ｉｎｐｕｔ／Ｏｕｔｐｕｔ）３０、ＩＣカード３内の各機能を制御するＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）３１、ＩＣカード３の各種機能を実現するプログラム等を格納したＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）３２、ＲＡＭ３３、フラッシュメモリ等の不揮発性メモリ３４、及び、ＲＳＡ暗号による暗号化処理等を行うＲＳＡ暗号回路２を備えて構成されている。尚、ＲＯＭ３２は、フラッシュメモリ等の不揮発性メモリで構成することも可能である。また、本実施形態では、接触型ＩＣカードを想定しているが、非接触型ＩＣカード、或いは、接触型及び非接触型Ｉ／Ｏの両方を備えたコンビ型ＩＣカードであっても良い。
【００７３】
図１０に示す構成のＩＣカード３において、ＲＳＡ暗号回路２を搭載しているため、ＲＳＡ暗号処理を用いた暗号通信や電子署名を使用することができる。ここで、ＲＳＡ暗号回路２は、上述のように、ＤＰＡ等の電力波形解析による攻撃に対する防御性能が高いため、本実施形態では、セキュリティ度の高いＩＣカードが実現できる。
【００７４】
次に、本発明装置の別実施形態について説明する。
【００７５】
〈１〉上記実施形態では、モンゴメリ乗算回路１を構成するメモリ回路１１は、同期式１ポートＲＡＭで構成される第１メモリＭ１と第２メモリＭ２、及び、被乗数格納用レジスタＲ１とキャリーレジスタＲ２を備えて構成される場合を説明したが、メモリ回路１１の回路構成は、必ずしも図１に示す回路構成に限定されるものではない。例えば、第２メモリＭ２を２つに分割して、一方を第１配列ａ［ｓ−１：０］と被乗算変数ｍの格納用として、他方を第２配列ｂ［ｓ−１：０］と第３配列ｎ［ｓ−１：０］の格納用とし、被乗数格納用レジスタＲ１を省略しても構わない。
【００７６】
更に、上記実施形態では、第１メモリＭ１と第２メモリＭ２を同期式１ポートＲＡＭで構成する場合を例示したが、１ポートＲＡＭでは、読み出し処理と書き込み処理を同時に実行できないので、第１メモリＭ１と第２メモリＭ２を読み出し処理と書き込み処理を同時に実行可能な同期式２ポートＲＡＭで構成するようにしても良い。
【００７７】
〈２〉上記実施形態では、モンゴメリ乗算回路１を構成する制御回路１２が、乱数発生回路１５を備え、モンゴメリ乗算が起動されると、制御回路１２において、乱数発生回路１５が乱数値を発生し、当該乱数値に基づいてマイクロコードの１つを選択する構成としたが、図１１に示すように、制御回路１２が乱数発生回路１５を備えるのではなく、外部から、マイクロコードの１つをランダムに選択するための選択信号ＲＳを受信し、当該選択信号の信号値に応じてマイクロコードの１つを選択して、モンゴメリ乗算を開始する構成としても良い。
【００７８】
この場合、外部から当該選択信号を受信する構成のモンゴメリ乗算回路１を用いてＲＳＡ暗号回路を構成する場合、図１２に示すように、ＲＳＡ暗号回路２内に乱数発生回路１５を備え、図９に示す処理アルゴリズムを実行する際に、ステップ＃１０４とステップ＃１０６の各モンゴメリ乗算の実行前に、乱数発生回路による乱数値の発生処理を行い、当該乱数値に応じた選択信号ＲＳをモンゴメリ乗算回路１に出力することにより、モンゴメリ乗算を起動するようにしても良い。
【００７９】
更に、上記実施形態では、モンゴメリ乗算回路１は、モンゴメリ乗算が起動される毎にマイクロコードの１つを毎回ランダムに選択する構成としたが、マイクロコードの選択を起動毎に実行せず、間欠的にマイクロコードの選択を行うようにしても良い。これにより、乱数発生回路が動作する場合と動作しない場合で消費電力波形に差が生じることになる。
【産業上の利用可能性】
【００８０】
本発明に係るモンゴメリ乗算回路は、モンゴメリ乗算回路、及び、モンゴメリ乗算回路を用いて暗号化処理及び復号化処理を行う暗号回路に利用可能であり、特に、消費電力解析による秘密情報を暴露する攻撃から情報を守るセキュリティ機能を向上させたモンゴメリ乗算回路及び暗号回路に有効である。
【符号の説明】
【００８１】
１： モンゴメリ乗算回路
２： ＲＳＡ暗号回路
３： ＩＣカード
１０： 算術回路
１１： メモリ回路
１２： 制御回路
１３： コードメモリ
１４： シーケンサ回路
１５： 乱数発生回路
１６： 第１ループカウンタ回路
１７： 第２ループカウンタ回路
２０： ＡＳＩＣ回路
３０： Ｉ／Ｏ
３１： ＣＰＵ
３２： ＲＯＭ
３３： ＲＡＭ
３４： 不揮発性メモリ
Ｍ１： 第１メモリ
Ｍ２： 第２メモリ
Ｒ１： 被乗数格納用レジスタ
Ｒ２： キャリーレジスタ
ＲＳ： 選択信号
【技術分野】
【０００１】
本発明は、モンゴメリ乗算回路、及び、モンゴメリ乗算回路を用いて暗号化処理及び復号化処理を行う暗号回路に関し、特に、消費電力解析による秘密情報を暴露する攻撃から情報を守るセキュリティ機能を向上させたモンゴメリ乗算回路及び暗号回路に関する。
【背景技術】
【０００２】
近年、ネットワーク技術の進歩により様々なことがネットワーク上で実現可能となってきた。例えば、インターネット等のネットワークを利用して契約や決済を行う電子商取引として、ネットワーク上で商品を販売する電子商店による商取引（企業と消費者間の商取引）があり、消費者は、自宅のパソコンからインターネットを経由して電子商店のＷｅｂサイトを閲覧して商品を選択し、決済方法を指定して購入することができる。
【０００３】
このような電子商取引では、成りすましや盗聴、改ざんの防止等のセキュリティの確保が課題となっており、例えば、成りすましを防止するための認証技術の一つとして、公開鍵暗号が利用されている。ここで、公開鍵暗号は、暗号化のための暗号化鍵と復号化のための復号化鍵の異なる２つの鍵を用いるものであり、暗号化鍵からの復号化鍵の推測、及び、暗号文の解読は、極めて困難、或いは、不可能となっている。鍵の所有者は、暗号化鍵（公開鍵）を公開し、復号化鍵（秘密鍵）を第三者に知られないように管理することにより、公開鍵を利用する相手側の情報が第三者に知られないようにすることができる。
【０００４】
例えば、上述した電子商店と消費者の間の商取引では、電子商店が、暗号化鍵（公開鍵）を一般に公開し、復号化鍵（秘密鍵）を第三者に知られないように管理する。消費者は、電子商店側が公開している暗号化鍵（公開鍵）を利用して、商取引に関する情報を暗号化して電子商店に送信する。電子商店は、消費者から受け取った暗号文を復号化鍵（秘密鍵）で復号化し、消費者に対し商品の販売を行う。鍵の所有者である電子商店は、復号化鍵（秘密鍵）を第三者に知られないように管理することにより、商取引に関する情報が第三者に知られるのを防止でき、消費者の個人情報等が第三者に知られるのを防止することができる。
【０００５】
公開鍵暗号としては、例えば、ＲＳＡ（Ｒｉｖｅｓｔ Ｓｈａｍｉｒ Ａｄｌｅｍａｎ）暗号がある。ＲＳＡ暗号は、解読するために、非常に大きな整数の合成体の素因数分解が必要であり、コンピュータによる解読であっても、現実的な計算時間での解読が困難であり、非常に大きな整数の合成体の素因数分解が困難であることに安全性の根拠を置く暗号方式である。
【０００６】
以下、ＲＳＡ暗号の暗号化方法及び復号化方法について簡単に説明する。公開鍵（ｅ、ｎ）を用いて平文Ｍを暗号化し、暗号文Ｃを生成する場合、暗号文Ｃは、以下の数１により生成される。
【０００７】
［数１］
Ｃ＝Ｍｅｍｏｄｎ
（但し、０≦Ｍ＜ｎ）
【０００８】
秘密鍵（ｄ、ｎ）を用いて暗号文Ｃを復号化し、平文Ｍを生成する場合、平文Ｍは、以下の数２により生成される。
【０００９】
［数２］
Ｍ＝Ｃｄｍｏｄｎ
【００１０】
尚、公開鍵（ｅ、ｎ）、秘密鍵（ｄ、ｎ）には、以下の数３の関係がある。
【００１１】
［数３］
ｎ＝ｐ×ｑ （ｐ、ｑは素数）
ｅ×ｄ≡１ｍｏｄ（ｐ−１）（ｑ−１）
【００１２】
具体的には、例えば、ｐ＝３、ｑ＝１１、ｅ＝３、ｄ＝７とすると、平文Ｍ＝７を暗号化して得られる暗号文Ｃは、数１より、Ｃ＝７3ｍｏｄ（３×１１）＝３４３ｍｏｄ３３＝１３となる。
【００１３】
また、暗号文Ｃ＝１３を復号化して得られる平文Ｍは、数２より、Ｍ＝１３７ｍｏｄ３３＝６２７４８５１７ｍｏｄ３３＝７となる。従って、数１及び数２による暗号化及び復号化は、正しく行われることが分かる。
【００１４】
ところで、上述したＲＳＡ暗号では、数１及び数２に示すように、べき乗演算、剰余演算を行っている。一般的に、鍵や平文は、１０２４ビット以上の非常に大きな桁数となるため、演算装置上で数１及び数２をそのまま用いて暗号化及び復号化を行うと、桁あふれを起こす可能性がある。
【００１５】
このため、ＲＳＡ暗号の暗号化及び復号化では、例えば、桁あふれしない剰余演算の手法の一例であるモンゴメリ乗算が用いられる。モンゴメリ乗算では、Ｎビットの剰余算をＮビットのメモリ空間で行うことができる。
【００１６】
以下、モンゴメリ乗算について簡単に説明する。ＲＳＡ暗号の数１に示す暗号文Ｃの生成式の右辺（Ｍｅｍｏｄｎ）は、以下の数４に示す逐次計算で求められる。即ち、数５に示す演算を繰り返し行うことで計算できる。
【００１７】
［数４］
Ｍ２ｍｏｄｎ＝Ｍ×Ｍｍｏｄｎ，
Ｍ３ｍｏｄｎ＝Ｍ×Ｍ２ｍｏｄｎ，
…
Ｍｅｍｏｄｎ＝Ｍ×Ｍｅ−１ｍｏｄｎ
【００１８】
［数５］
γ＝α×βｍｏｄｎ
【００１９】
ここで、モンゴメリ乗算では、コンピュータ上における乗算のため、定数Ｒ＝２Ｎを用いる。数５の両辺にＲを掛けてｍｏｄｎをとると、数６となる。ここで、数７に示すように、Ｚ、Ａ、Ｂを夫々規定すると、モンゴメリ乗算の演算式は、以下の数８で表される。尚、モンゴメリ乗算の演算アルゴリズムについては、下記の非特許文献１に詳細な記載がある。
【００２０】
［数６］
γＲｍｏｄｎ＝αＲ×βＲ×Ｒ−１ｍｏｄｎ
【００２１】
［数７］
Ｚ＝γＲｍｏｄｎ，
Ａ＝αＲｍｏｄｎ，
Ｂ＝βＲｍｏｄｎ
【００２２】
［数８］
Ｚ（Ａ，Ｂ）＝Ａ×Ｂ×Ｒ−１ｍｏｄｎ
【００２３】
数８に示すモンゴメリ乗算を繰り返し実行しながら、数１に示す暗号文Ｃの生成式を実現する方法を左バイナリ法と言い、以下に示すＳｔｅｐ１乃至Ｓｔｅｐ４の処理工程となる。尚、以下の処理工程において、Ｎ桁の２進数ｅを、ｅ＝｛ｅＮ−１，ｅＮ−２，…，ｅ１，ｅ０｝と表現する。ｅｉ（ｉ＝０〜Ｎ−１）はＬＳＢ側（左側）から（ｉ＋１）桁目のビット値である。
【００２４】
Ｓｔｅｐ１： Ａ：＝Ｍ×Ｒｍｏｄｎ
Ｓｔｅｐ２： Ｘ：＝１×Ｒｍｏｄｎ
Ｓｔｅｐ３： ｆｏｒ ｉ＝Ｎ−１ ｄｏｗｎ ｔｏ ０
Ｘ：＝Ｚ（Ｘ，Ｘ）
ｉｆ ｅｉ＝１ ｔｈｅｎ Ｘ：＝Ｚ（Ｘ，Ａ）
Ｓｔｅｐ４： Ｃ：＝Ｚ（Ｘ，１）
【００２５】
ここで、上記Ｓｔｅｐ３において、ｅｉ＝０の時は、Ｚ（Ｘ，Ｘ）だけの演算が行われ、ｅｉ＝１の時は、Ｚ（Ｘ，Ｘ）とＺ（Ｘ，Ａ）の２回の演算が行われる点が重要となる。
【００２６】
もし、Ｚ（Ｘ，Ｘ）とＺ（Ｘ，Ａ）の２種類の演算が消費電力波形から判別可能となると、暗号鍵Ｅのビット系列が解読できることになる。つまり、如何にしてＺ（Ｘ，Ｘ）とＺ（Ｘ，Ａ）の２種類の演算を消費電力波形から判別できないようにすることがセキュリティ上重要となる。
【００２７】
Ｚ（Ｘ，Ｘ）とＺ（Ｘ，Ａ）の２種類の演算を判別する攻撃法としては、Ｚ（Ｘ，Ｘ）とＺ（Ｘ，Ａ）の入力値をメモリからロードする時間を見分ける方法がある。Ｚ（Ｘ，Ｘ）はＸという値を１つだけをメモリからロードするのに対して、Ｚ（Ｘ，Ａ）はＸとＡの２つの値をメモリからロードする。このロード時間に差があれば容易に鍵情報を推測することができる。当該攻撃法に対しては、Ｚ（Ｘ，Ｘ）の演算でもＸのロードを２回行うことにより容易に対処できる。
【００２８】
しかし、解析装置の進歩により、Ｚ（Ｘ，Ｘ）とＺ（Ｘ，Ａ）のデータを多数取り、消費電力の僅かな違いを判別し秘密情報を割り出すＤＰＡ（電力差分解析）と呼ばれる攻撃が行われる可能性がある。
【００２９】
下記の特許文献１では、左バイナリ法において、Ｚ（Ｘ，Ｘ）を実行する乗算剰余演算部と、Ｚ（Ｘ，Ａ）を実行する乗算剰余演算部を２つ設けた場合に、Ｚ（Ｘ，Ｘ）の演算はべき指数のビット値に関係なく常時実行されるのに対して、Ｚ（Ｘ，Ａ）の演算はべき指数のビット値が１の桁のみで実行されるので、Ｚ（Ｘ，Ｘ）とＺ（Ｘ，Ａ）の２つの乗算剰余演算部の回路動作を外部から観測することで、べき指数の値が推測でき、暗号演算回路として耐タンパー性が低い点を指摘し、その対策として、異なる２つの底のべき乗剰余演算を並列に実行する際に、図１３に示すように、夫々のべき乗剰余演算に係るＺ（Ｘ，Ｘ）を実行する乗算剰余演算部を１つずつ設け、夫々のべき乗剰余演算に係るＺ（Ｘ，Ａ）を実行する乗算剰余演算部を１つだけ設けて、２つのべき乗剰余演算で、夫々の演算のべき指数のビット値が１の桁のみで実行するように、交互或いはランダムな順番で共用する構成とすることで、夫々のべき乗剰余演算におけるべき指数の値の推測を困難にしている。
【先行技術文献】
【特許文献】
【００３０】
【特許文献１】特開２００１−２０２０１５号公報
【非特許文献】
【００３１】
【非特許文献１】C. K. Koc, "Analyzing and Computing MontgomeryMultiplication Algorithms", IEEE Micro, 16(3): 26-33, June 1996.
【発明の概要】
【発明が解決しようとする課題】
【００３２】
上記特許文献１による対策は、Ｚ（Ｘ，Ｘ）とＺ（Ｘ，Ａ）の２つの演算に対して、乗算剰余演算部を夫々設け、異なる２つの底のべき乗剰余演算を並列に実行する際には有効な手段と考えられるが、Ｚ（Ｘ，Ｘ）とＺ（Ｘ，Ａ）の２つの演算に対して、乗算剰余演算部を夫々設けない場合や、１つのべき乗剰余演算だけを行う場合には、乗算剰余演算部を３つ設ける必要がないため、回路規模が大きくなり、消費電力も増大し、ＩＣカード用ＬＳＩのように小さなチップで非常に少ない消費電力で動作する必要がある場合には、有効な手段とは言えない。
【００３３】
本発明は、モンゴメリ乗算を繰り返し実行する左バイナリ法による暗号処理における上記問題点に鑑みてなされたものであり、その目的は、回路規模及び消費電力を増大させることなく外部からの消費電力解析が困難なセキュリティ性の高いモンゴメリ乗算回路及びＲＳＡ暗号回路を提供することにある。
【課題を解決するための手段】
【００３４】
上記目的を達成するため、本発明では、メモリ回路、算術回路、及び、前記メモリ回路と前記算術回路間のデータの入出力を所定のアルゴリズムに基づいて制御してモンゴメリ乗算を実現する制御回路を備えてなるモンゴメリ乗算回路であって、前記制御回路が、前記アルゴリズムを２以上有し、２以上の前記アルゴリズムの内の１つをランダムに選択して、選択した１つの前記アルゴリズムに基づいて前記モンゴメリ乗算の実行に係る制御を行うことを特徴とするモンゴメリ乗算回路を提供する。
【００３５】
上記特徴のモンゴメリ乗算回路によれば、２以上のアルゴリズムの内の１つをランダムに選択して、選択したアルゴリズムに基づいてモンゴメリ乗算が実行されるので、実行毎に、アルゴリズムがランダムに異なるため、当該アルゴリズムの違いに応じて当該実行に係る消費電力も異なる結果、上記特徴のモンゴメリ乗算回路を用いてモンゴメリ乗算を繰り返し実行した場合に、被乗数と消費電力の関係が都度ランダムに変化し、消費電力の変化が複雑化し、外部からの消費電力解析が極めて困難となる。また、１つのモンゴメリ乗算回路に２以上のアルゴリズムを設け、それらをランダム選択するだけの構成で良いので、回路規模及び消費電力を大幅に増大させることなくセキュリティ性を向上させることが可能となる。
【００３６】
更に好ましくは、上記特徴のモンゴメリ乗算回路は、前記制御回路が、前記２以上のアルゴリズムの各別に規定するマイクロコードを格納するコードメモリと、前記メモリ回路に対するデータの入出力制御と前記算術回路で行う算術演算の選択を行うシーケンサ回路と、乱数発生回路を備え、前記乱数発生回路が発生した乱数値に基づいて前記マイクロコードの１つを選択し、選択されたマイクロコードに沿って、前記シーケンサ回路が、前記メモリ回路と前記算術回路に対する制御を実行するように構成される。
【００３７】
斯かる構成のモンゴメリ乗算回路によれば、マイクロコードを格納するコードメモリの記憶容量を、追加されたアルゴリズムのマイクロコード分だけ大きく確保するだけで、アルゴリズム毎に専用のハードウェア回路を設ける場合に比べて回路規模を小さく抑制できるとともに、簡単な回路構成で、２以上のアルゴリズムの内の１つをランダムに選択して、選択したアルゴリズムに基づいてモンゴメリ乗算が実行できるようになる。
【００３８】
更に好ましくは、上記特徴のモンゴメリ乗算回路は、前記算術回路が、乗算器と加算器からなる積和演算回路で構成されている。
【００３９】
斯かる構成のモンゴメリ乗算回路によれば、モンゴメリ乗算を積和演算の繰り返しで実現するＣＩＯＳ（Ｃｏａｒｓｅｌｙ Ｉｎｔｅｇｒａｔｅｄ Ｏｐｅｒａｎｄ Ｓｃａｎｎｉｎｇ）法、及び、ＦＩＯＳ（Ｆｉｎｅｌｙ Ｉｎｔｅｇｒａｔｅｄ Ｏｐｅｒａｎｄ Ｓｃａｎｎｉｎｇ）法等の複数のアルゴリズムを利用して、２以上のアルゴリズムの内の１つをランダムに選択して、選択したアルゴリズムに基づいてモンゴメリ乗算が実行できるようになる。また、モンゴメリ乗算を積和演算の繰り返しで実現するアルゴリズムでは、除算を用いずに剰余演算を実行できるため、計算コストを大幅に削減できる。
【００４０】
更に、上記目的を達成するため、本発明では、上記特徴のモンゴメリ乗算回路を備え、左バイナリ法による暗号処理過程で実行するモンゴメリ乗算を、前記モンゴメリ乗算回路を用い、モンゴメリ乗算のアルゴリズムを２以上の前記アルゴリズムの中からランダムに選択して実行することを特徴とするＲＳＡ暗号回路を提供する。
【００４１】
上記特徴のＲＳＡ暗号回路によれば、左バイナリ法による暗号処理過程で実行するモンゴメリ乗算が、実行の都度、被乗数と消費電力の関係がランダムに変化するため、消費電力の変化が複雑化し、外部からの消費電力解析が極めて困難となり、回路規模及び消費電力を大幅に増大させることなくセキュリティ性を向上させることが可能となる。
【００４２】
更に、上記目的を達成するため、本発明では、上記特徴のＲＳＡ暗号回路を備えてなることを特徴とするＩＣカードを提供する。これにより、ＩＣカードに搭載するＬＳＩの回路規模及び消費電力を増大させることなく、消費電力解析が極めて困難なＲＳＡ暗号回路を搭載したセキュリティ性の高いＩＣカードが実現できる。
【００４３】
更に、上記目的を達成するため、本発明では、左バイナリ法によるＲＳＡ暗号処理過程で繰り返し実行するモンゴメリ乗算を、モンゴメリ乗算のアルゴリズムを２以上の前記アルゴリズムの中からランダムに選択して実行することを特徴とするＲＳＡ暗号処理方法を提供する。
【００４４】
上記特徴のＲＳＡ暗号処理方法によれば、左バイナリ法によるＲＳＡ暗号処理過程で繰り返し実行するモンゴメリ乗算が、実行の都度、被乗数と消費電力の関係がランダムに変化するため、消費電力の変化が複雑化し、外部からの消費電力解析が極めて困難となり、回路規模及び消費電力を大幅に増大させることなくセキュリティ性を向上させることが可能となる。
【図面の簡単な説明】
【００４５】
【図１】本発明に係るモンゴメリ乗算回路の一実施形態における一回路構成例を示すブロック図である。
【図２】ＣＩＯＳ法によるモンゴメリ乗算アルゴリズムのプログラムコードを示す図である。
【図３】ＦＩＯＳ法によるモンゴメリ乗算アルゴリズムのプログラムコードを示す図である。
【図４】ＣＩＯＳ法によるモンゴメリ乗算アルゴリズムの演算処理を簡略的に図解して説明する図である。
【図５】ＦＩＯＳ法によるモンゴメリ乗算アルゴリズムの演算処理を簡略的に図解して説明する図である。
【図６】同期式１ポートＲＡＭの概略構成例を示す概略ブロック図である。
【図７】同期式１ポートＲＡＭの読み出し処理と書き込み処理の各動作を説明するためのタイミング図である。
【図８】本発明に係るＲＳＡ暗号回路の一実施形態における一回路構成例を示すブロック図である。
【図９】本発明に係るＲＳＡ暗号回路の処理アルゴリズムを示すフローチャートである。
【図１０】本発明に係るモンゴメリ乗算回路を用いて構成されたＲＳＡ暗号回路を搭載したＩＣカードの概略部分構成例を示す概略部分ブロック図である。
【図１１】本発明に係るモンゴメリ乗算回路の別実施形態における一回路構成例を示すブロック図である。
【図１２】本発明に係るＲＳＡ暗号回路の別実施形態における一回路構成例を示すブロック図である。
【図１３】従来技術における左バイナリ法によるＲＳＡ暗号処理の乗算剰余演算に係る回路構成例を示すブロック図である。
【発明を実施するための形態】
【００４６】
本発明に係るモンゴメリ乗算回路の実施の形態につき、図面に基づいて説明する。
【００４７】
図１に、モンゴメリ乗算回路１の回路構成を示す。モンゴメリ乗算回路１は、図１に示すように、積和演算回路からなる算術回路１０と、第１メモリＭ１と第２メモリＭ２と被乗数格納用レジスタＲ１とキャリーレジスタＲ２からなるメモリ回路１１と、算術回路１０とメモリ回路１１間のデータの入出力を制御してモンゴメリ乗算を実現する制御回路１２を備えて構成されている。
【００４８】
算術回路１０は、ビット幅ｒの第１変数Ｘ、第２変数Ｙ、第３変数Ｚ、第４変数Ｃを受け付け、第３変数Ｚと、第１変数Ｘと第２変数Ｙの積算結果（Ｘ×Ｙ）と、第４変数Ｃの和（Ｆ＝Ｚ＋Ｘ×Ｙ＋Ｃ）を演算してビット幅２ｒの演算結果データＦを出力する積和演算処理を行う。つまり、算術回路１０は、第１変数Ｘと第２変数Ｙの乗算を行う乗算器と、第３変数Ｚと、第１変数Ｘと第２変数Ｙの積算結果（Ｘ×Ｙ）と、第４変数Ｃの加算を行う加算器で構成されている。
【００４９】
第１メモリＭ１は、ビット幅ｒ、要素数ｓ＋１の中間結果格納用配列ｔを格納する記憶領域を備えた同期式１ポートＲＡＭで構成され、中間結果格納用配列ｔの各要素を第３変数Ｚとして積和演算回路１０に出力する。
【００５０】
第２メモリＭ２は、ビット幅ｒ、要素数ｓの第１配列ａ［ｓ−１：０］、第２配列ｂ［ｓ−１：０］、及び、第３配列ｎ［ｓ−１：０］と、ビット幅ｒの被乗算変数ｍを格納する記憶領域を備えた同期式１ポートＲＡＭで構成され、第１配列ａ［ｓ−１：０］の各要素または被乗算変数ｍを第１変数Ｘとして積和演算回路１０に出力する。
【００５１】
被乗数格納用レジスタＲ１は、第２メモリＭ２から第２配列ｂ［ｓ−１：０］または第３配列ｎ［ｓ−１：０］を要素単位で受け付けて記憶し、第２変数Ｙとして積和演算回路１０に出力する。また、キャリーレジスタＲ２は、演算結果データＦの内の上位ｒビットからなる上位ビット側データＦＨを受け付けて記憶し、第４変数Ｃとして積和演算回路１０に出力する。
【００５２】
制御回路１２は、２以上のアルゴリズムの各別に規定するマイクロコードを格納するコードメモリ１３と、メモリ回路１１に対するデータの入出力制御と算術回路１０で行う算術演算の選択を行うシーケンサ回路１４と、乱数発生回路１５を備えて構成される。モンゴメリ乗算が起動されると、制御回路１２において、乱数発生回路１５が乱数値を発生し、当該乱数値に基づいてマイクロコードの１つが選択され、選択されたマイクロコードに沿って、シーケンサ回路１４が、メモリ回路１１と算術回路１０に対する制御を実行する。
【００５３】
本実施形態では、シーケンサ回路１４は、図２及び図３に示すプログラムコードで用いられるカウント値の内、メインループ処理の処理回数を制御する第１ループカウント値ｉを生成する第１ループカウンタ回路１６と、図２及び図３に示すプログラムコードで用いられるカウント値の内、サブループ処理の処理回数を制御する第２ループカウント値ｊを生成する第２ループカウンタ回路１７を備えて構成されている。
【００５４】
算術回路１０、第１メモリＭ１、第２メモリＭ２、被乗数格納用レジスタＲ１、キャリーレジスタＲ２の各バス幅は、第１配列ａ、第２配列ｂ、第３配列ｎ、被乗算変数ｍの各ビット幅と同じｒビットで、一般的には１６ビット或いは３２ビットである。
【００５５】
図２及び図３に、コードメモリ１３に格納されるＣＩＯＳ法とＦＩＯＳ法の２つのアルゴリズムの各プログラムコードを示す。
【００５６】
図２及び図３に示すプログラムコードにおける変数ｔ［ｊ］が第１メモリＭ１の中間結果格納用配列ｔに格納される各要素であり、各変数ａ［ｊ］，ｂ［ｉ］，ｎ［ｊ］が第１メモリＭ１の第１配列ａ、第２配列ｂ、及び、第３配列ｎに格納される各要素である。変数ａ［ｊ］をｊ＝ｓ−１からｊ＝０まで順番に連接した変数が数８に示すモンゴメリ乗算の変数Ａに相当し、変数ｂ［ｉ］をｉ＝ｓ−１からｉ＝０まで順番に連接した変数が数８に示すモンゴメリ乗算の変数Ｂに相当し、変数ｎ［ｊ］をｊ＝ｓ−１からｊ＝０まで順番に連接した変数が数８に示すモンゴメリ乗算の変数ｎに相当する。更に、図２及び図３に示すプログラムコード中のＷは２ｒ（但しｒはバス幅）で定義される定数であり、ｎ’［０］は変数ｎの最下位ワードｎ［０］の２ｒを法とする逆数（−ｎ［０］−１）を意味する定数である。
【００５７】
図４に、図２に示すプログラムコードによるＣＩＯＳ法のモンゴメリ乗算を、ｓ＝４の場合を例に、簡略的に図解する。図４において、左側の乗算（ａ×ｂ［ｉ］）が、図２に示すプログラムコードの第１のサブループ内の（Ｃ，Ｓ）：＝ｔ［ｊ］＋ａ［ｊ］×ｂ［ｉ］＋Ｃを、中央の乗算（ｔ［０］×ｎ’［０］）が、図２に示すプログラムコードのメインループ内のｍ：＝ｔ［０］×ｎ’［０］ｍｏｄＷを、右側のｎ×ｍが、図２に示すプログラムコードのメインループ内の（Ｃ，Ｓ）：＝ｔ［０］＋ｍ×ｎ［０］を、夫々表現している。
【００５８】
図５に、図３に示すプログラムコードによるＦＩＯＳ法のモンゴメリ乗算を、ｓ＝４の場合を例に、簡略的に図解する。図５において、左側に、図３に示すプログラムコードの部分的な乗算（ｔ［ｉ］＝ａ×ｂ［ｉ］）によりｍ［ｉ］が得られる様子が図示されており、右側に、ｎ×ｍ［ｉ］の乗算結果と上記部分的な乗算結果ｔ［ｉ］の加算により、中間結果ｔ［ｉ＋１］が得られる様子が図示されている。
【００５９】
図２及び図３に示すように、当該各プログラムコードでは、モンゴメリ乗算が乗算と加算の繰り返しで実現されており、図１に示す回路構成の積和演算処理を行う算術回路１０を備えたモンゴメリ乗算回路１で処理可能である。
【００６０】
尚、コードメモリ１３に格納するアルゴリズムは、図１に示す回路構成のモンゴメリ乗算回路１で処理可能な、つまり、モンゴメリ乗算を乗算と加算の繰り返しで実現するアルゴリズムであれば、上記２つのアルゴリズムに限定されるものではなく、また、格納するアルゴリズム数も３以上であっても良い。尚、図２及び図３に示す各プログラムコードでモンゴメリ乗算が実現できることは、上記非特許文献１において説明されており公知であるので、詳細な説明は割愛する。
【００６１】
ところで、図２及び図３に示すプログラムコードの２つのアルゴリズムを比較すると、何れもｉループ（メインループ）とその内側にｊループ（サブループ）を備えた構造となっているが、ＣＩＯＳ法とＦＩＯＳ法では、サブループの個数及びその処理内容が異なっており、当該処理において実行されるメモリ回路１１の読み出し動作や書き込み動作におけるメモリ番地や読み出し及び書き込みに係るデータも異なり、それらのデータを用いた積和演算の入力値も異なるため、２つのアルゴリズム間では、実行中の消費電力波形が異なる。つまり、同じ結果が得られる演算を行っても外部に現れる消費電力波形が異なる。
【００６２】
本実施形態では、モンゴメリ乗算が起動されると、制御回路１２が、乱数発生回路１５が発生した乱数値に基づいて、２つのアルゴリズムの何れか一方をランダムに選択して実行する構成となっているため、外部から消費電力波形を観察しても、消費電力波形の違いが入力データの違いに依るものか、アルゴリズムの違いに依るものかを区別できない。従って、本実施形態のモンゴメリ乗算回路１を用いることで、モンゴメリ乗算を繰り返し実行しながら暗号文を生成する際に、多くの入力値に対する消費電力から統計的にデータの違いにより消費電力の違いを解析するＤＰＡ等の攻撃法に対して、有効な防御策となる。
【００６３】
次に、図１に示す回路構成のモンゴメリ乗算回路１の回路動作について、図２に示すＣＩＯＳ法のプログラムコードの実行を例に、簡単に説明する。
【００６４】
図６は、本実施形態の第１メモリＭ１及び第２メモリＭ２の概略構成例を示している。また、図７（ａ）は、本実施形態の第１メモリＭ１及び第２メモリＭ２の読み出し処理における動作タイミングを、図７（ｂ）は、本実施形態の第１メモリＭ１及び第２メモリＭ２の書き込み処理における動作タイミングを、夫々示している。同期式１ポートＲＡＭである第１メモリＭ１は、図７（ａ）に示すように、読み出し処理において、クロック信号ＣＬＫに同期して動作し、チップイネーブル信号ＣＥ＃がＬレベルの場合に、アドレス信号ＡＤによって示される記憶領域に記憶されたデータＤを、出力端子ＤＯＵＴから出力する。同様に、第１メモリＭ１は、図７（ｂ）に示すように、書き込み処理において、クロック信号ＣＬＫに同期して動作し、チップイネーブル信号ＣＥ＃がＬレベルの場合に、アドレス信号ＡＤによって示される記憶領域に、データ入力端子ＤＩＮから入力されたデータＤを書き込む。
【００６５】
モンゴメリ乗算回路１は、第２メモリＭ２から、第１ループカウンタ値ｉで示される第２配列ｂ［ｓ−１：０］の要素を読み出して被乗数格納用レジスタＲ１に格納する第１読み出し処理と、第２メモリＭ２から第２ループカウンタ値ｊで示される第１配列ａ［ｓ−１：０］の要素を読み出し、第１メモリＭ１から第２ループカウンタ値ｊで示される中間結果格納用配列ｔの要素を読み出し、被乗数格納用レジスタＲ１の値ＲＸを読み出し、キャリーレジスタＲ２の値ＲＣを読み出し、夫々、積和演算回路１０に入力する第２読み出し処理と、キャリーレジスタＲ２に上位ビット側データＦＨを書き込むと共に、第１メモリＭ１に、演算結果データＦの内の下位ｒビットからなる下位ビット側データＦＬを、第２ループカウンタ値ｊで示される中間結果格納用配列ｔの要素として書き込む書き込み処理と、を実行可能に構成され、第２読み出し処理、積和演算処理、書き込み処理、及び、第２ループカウンタ値ｊの更新を繰り返し実行する第１サブループ処理を、第１読み出し処理の実行後に実行する。
【００６６】
更に、モンゴメリ乗算回路１は、第３配列ｎ［ｓ−１：０］の各要素を対応する第１配列ａ［ｓ−１：０］の各要素として用いた第２読み出し処理、積和演算処理、書き込み処理、及び、第２ループカウンタ値ｊの更新を繰り返し実行する第２サブループ処理を実行する。
【００６７】
モンゴメリ乗算回路１は、図２に示すプログラムコードの実行のために、少なくとも、通常の第１読み出し処理、第１サブループ処理、被乗算変数ｍを第２配列ｂ［ｓ−１：０］の各要素として用いた第１読み出し処理、第２サブループ処理、及び、第１ループカウンタ値ｉの更新を、この順に繰り返し実行するメインループ処理を実行する。
【００６８】
次に、図１に示すモンゴメリ乗算回路１を用いた本発明に係るＲＳＡ暗号回路について説明する。図８に、ＲＳＡ暗号回路２の概略の回路構成を示す。本実施形態では、ＲＳＡ暗号回路２は、図９に示す左バイナリ法による暗号処理アルゴリズムを実行するＡＳＩＣ回路２０とモンゴメリ乗算回路１を備えて構成される。
【００６９】
図９は、本実施形態におけるＲＳＡ暗号回路２の左バイナリ法による処理アルゴリズムを示している。具体的には、ＲＳＡ暗号回路２は、先ず、平文Ｍ、定数Ｒ＝２Ｎを用いてモンゴメリ変換を行い（ステップ＃１０１）、暗号化鍵ｅ＝Ｋ［ｋ−１：０］を読み出し（＃１０２）、変数ｉの値をｋ−１に初期化する（ステップ＃１０３）。その後、モンゴメリ乗算回路１が、Ａ＝ＡＡＲ−１ｍｏｄｎで表される１つの入力値Ａの二乗のモンゴメリ乗算を行い（ステップ＃１０４）、Ｋ［ｉ］＝１の場合は（ステップ＃１０５で「ＹＥＳ」分岐）、モンゴメリ乗算回路１が、Ａ＝ＡＢＲ−１ｍｏｄｎで表される２つの入力値ＡとＢのモンゴメリ乗算を行う（ステップ＃１０６）。変数ｉ≠０の場合は（ステップ＃１０７で「ＮＯ」分岐）、ｉを１減算して（ステップ＃１０８）ステップ＃１０４に移行する。変数ｉ＝０の場合は（ステップ＃１０７で「ＹＥＳ」分岐）、Ｃ＝ＡＲ−１ｍｏｄｎで表されるモンゴメリ逆変換を行い（ステップ＃１０９）、処理を終了する。
【００７０】
図９に示す左バイナリ法による処理アルゴリズムでは、ステップ＃１０４とステップ＃１０６の２種類のモンゴメリ乗算が繰り返し実行されるが、本実施形態では、モンゴメリ乗算回路１が、ステップ＃１０４またはステップ＃１０６のモンゴメリ乗算を実行する毎に、そのモンゴメリ乗算を実行するためのアルゴリズムをランダムに選択するので、ステップ＃１０４とステップ＃１０６のモンゴメリ乗算実行時の消費電力波形がランダムに変化する。従って、同じＲＳＡ暗号処理を行っても、処理毎に消費電力波形が異なるため、ＤＰＡ等の電力波形解析による攻撃に対する防御が可能となる。
【００７１】
次に、図８に示すＲＳＡ暗号回路２を用いた本発明に係るＩＣカード３について説明する。図１０に、ＩＣカード３の概略の回路構成を示す。
【００７２】
ＩＣカード３は、本実施形態では、接触型ＩＣカードであり、図１０に示すように、ＩＣカードリーダとデータ通信を行うためのＩ／Ｏ（Ｉｎｐｕｔ／Ｏｕｔｐｕｔ）３０、ＩＣカード３内の各機能を制御するＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）３１、ＩＣカード３の各種機能を実現するプログラム等を格納したＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）３２、ＲＡＭ３３、フラッシュメモリ等の不揮発性メモリ３４、及び、ＲＳＡ暗号による暗号化処理等を行うＲＳＡ暗号回路２を備えて構成されている。尚、ＲＯＭ３２は、フラッシュメモリ等の不揮発性メモリで構成することも可能である。また、本実施形態では、接触型ＩＣカードを想定しているが、非接触型ＩＣカード、或いは、接触型及び非接触型Ｉ／Ｏの両方を備えたコンビ型ＩＣカードであっても良い。
【００７３】
図１０に示す構成のＩＣカード３において、ＲＳＡ暗号回路２を搭載しているため、ＲＳＡ暗号処理を用いた暗号通信や電子署名を使用することができる。ここで、ＲＳＡ暗号回路２は、上述のように、ＤＰＡ等の電力波形解析による攻撃に対する防御性能が高いため、本実施形態では、セキュリティ度の高いＩＣカードが実現できる。
【００７４】
次に、本発明装置の別実施形態について説明する。
【００７５】
〈１〉上記実施形態では、モンゴメリ乗算回路１を構成するメモリ回路１１は、同期式１ポートＲＡＭで構成される第１メモリＭ１と第２メモリＭ２、及び、被乗数格納用レジスタＲ１とキャリーレジスタＲ２を備えて構成される場合を説明したが、メモリ回路１１の回路構成は、必ずしも図１に示す回路構成に限定されるものではない。例えば、第２メモリＭ２を２つに分割して、一方を第１配列ａ［ｓ−１：０］と被乗算変数ｍの格納用として、他方を第２配列ｂ［ｓ−１：０］と第３配列ｎ［ｓ−１：０］の格納用とし、被乗数格納用レジスタＲ１を省略しても構わない。
【００７６】
更に、上記実施形態では、第１メモリＭ１と第２メモリＭ２を同期式１ポートＲＡＭで構成する場合を例示したが、１ポートＲＡＭでは、読み出し処理と書き込み処理を同時に実行できないので、第１メモリＭ１と第２メモリＭ２を読み出し処理と書き込み処理を同時に実行可能な同期式２ポートＲＡＭで構成するようにしても良い。
【００７７】
〈２〉上記実施形態では、モンゴメリ乗算回路１を構成する制御回路１２が、乱数発生回路１５を備え、モンゴメリ乗算が起動されると、制御回路１２において、乱数発生回路１５が乱数値を発生し、当該乱数値に基づいてマイクロコードの１つを選択する構成としたが、図１１に示すように、制御回路１２が乱数発生回路１５を備えるのではなく、外部から、マイクロコードの１つをランダムに選択するための選択信号ＲＳを受信し、当該選択信号の信号値に応じてマイクロコードの１つを選択して、モンゴメリ乗算を開始する構成としても良い。
【００７８】
この場合、外部から当該選択信号を受信する構成のモンゴメリ乗算回路１を用いてＲＳＡ暗号回路を構成する場合、図１２に示すように、ＲＳＡ暗号回路２内に乱数発生回路１５を備え、図９に示す処理アルゴリズムを実行する際に、ステップ＃１０４とステップ＃１０６の各モンゴメリ乗算の実行前に、乱数発生回路による乱数値の発生処理を行い、当該乱数値に応じた選択信号ＲＳをモンゴメリ乗算回路１に出力することにより、モンゴメリ乗算を起動するようにしても良い。
【００７９】
更に、上記実施形態では、モンゴメリ乗算回路１は、モンゴメリ乗算が起動される毎にマイクロコードの１つを毎回ランダムに選択する構成としたが、マイクロコードの選択を起動毎に実行せず、間欠的にマイクロコードの選択を行うようにしても良い。これにより、乱数発生回路が動作する場合と動作しない場合で消費電力波形に差が生じることになる。
【産業上の利用可能性】
【００８０】
本発明に係るモンゴメリ乗算回路は、モンゴメリ乗算回路、及び、モンゴメリ乗算回路を用いて暗号化処理及び復号化処理を行う暗号回路に利用可能であり、特に、消費電力解析による秘密情報を暴露する攻撃から情報を守るセキュリティ機能を向上させたモンゴメリ乗算回路及び暗号回路に有効である。
【符号の説明】
【００８１】
１： モンゴメリ乗算回路
２： ＲＳＡ暗号回路
３： ＩＣカード
１０： 算術回路
１１： メモリ回路
１２： 制御回路
１３： コードメモリ
１４： シーケンサ回路
１５： 乱数発生回路
１６： 第１ループカウンタ回路
１７： 第２ループカウンタ回路
２０： ＡＳＩＣ回路
３０： Ｉ／Ｏ
３１： ＣＰＵ
３２： ＲＯＭ
３３： ＲＡＭ
３４： 不揮発性メモリ
Ｍ１： 第１メモリ
Ｍ２： 第２メモリ
Ｒ１： 被乗数格納用レジスタ
Ｒ２： キャリーレジスタ
ＲＳ： 選択信号
【特許請求の範囲】
【請求項１】
メモリ回路、算術回路、及び、前記メモリ回路と前記算術回路間のデータの入出力を所定のアルゴリズムに基づいて制御してモンゴメリ乗算を実現する制御回路を備えてなるモンゴメリ乗算回路であって、
前記制御回路は、前記アルゴリズムを２以上有し、２以上の前記アルゴリズムの内の１つをランダムに選択して、選択した１つの前記アルゴリズムに基づいて前記モンゴメリ乗算の実行に係る制御を行うことを特徴とするモンゴメリ乗算回路。
【請求項２】
前記制御回路は、前記２以上のアルゴリズムの各別に規定するマイクロコードを格納するコードメモリと、前記メモリ回路に対するデータの入出力制御と前記算術回路で行う算術演算の選択を行うシーケンサ回路と、乱数発生回路を備え、前記乱数発生回路が発生した乱数値に基づいて前記マイクロコードの１つを選択し、選択されたマイクロコードに沿って、前記シーケンサ回路が、前記メモリ回路と前記算術回路に対する制御を実行することを特徴とする請求項１に記載のモンゴメリ乗算回路。
【請求項３】
前記算術回路は、乗算器と加算器からなる積和演算回路であることを特徴とする請求項１または２に記載のモンゴメリ乗算回路。
【請求項４】
請求項１〜３の何れか１項に記載のモンゴメリ乗算回路を備え、左バイナリ法による暗号処理過程で実行するモンゴメリ乗算を、前記モンゴメリ乗算回路を用い、モンゴメリ乗算のアルゴリズムを２以上の前記アルゴリズムの中からランダムに選択して実行することを特徴とするＲＳＡ暗号回路。
【請求項５】
請求項４に記載のＲＳＡ暗号回路を備えてなることを特徴とするＩＣカード。
【請求項６】
左バイナリ法によるＲＳＡ暗号処理過程で繰り返し実行するモンゴメリ乗算を、モンゴメリ乗算のアルゴリズムを２以上の前記アルゴリズムの中からランダムに選択して実行することを特徴とするＲＳＡ暗号処理方法。
【請求項１】
メモリ回路、算術回路、及び、前記メモリ回路と前記算術回路間のデータの入出力を所定のアルゴリズムに基づいて制御してモンゴメリ乗算を実現する制御回路を備えてなるモンゴメリ乗算回路であって、
前記制御回路は、前記アルゴリズムを２以上有し、２以上の前記アルゴリズムの内の１つをランダムに選択して、選択した１つの前記アルゴリズムに基づいて前記モンゴメリ乗算の実行に係る制御を行うことを特徴とするモンゴメリ乗算回路。
【請求項２】
前記制御回路は、前記２以上のアルゴリズムの各別に規定するマイクロコードを格納するコードメモリと、前記メモリ回路に対するデータの入出力制御と前記算術回路で行う算術演算の選択を行うシーケンサ回路と、乱数発生回路を備え、前記乱数発生回路が発生した乱数値に基づいて前記マイクロコードの１つを選択し、選択されたマイクロコードに沿って、前記シーケンサ回路が、前記メモリ回路と前記算術回路に対する制御を実行することを特徴とする請求項１に記載のモンゴメリ乗算回路。
【請求項３】
前記算術回路は、乗算器と加算器からなる積和演算回路であることを特徴とする請求項１または２に記載のモンゴメリ乗算回路。
【請求項４】
請求項１〜３の何れか１項に記載のモンゴメリ乗算回路を備え、左バイナリ法による暗号処理過程で実行するモンゴメリ乗算を、前記モンゴメリ乗算回路を用い、モンゴメリ乗算のアルゴリズムを２以上の前記アルゴリズムの中からランダムに選択して実行することを特徴とするＲＳＡ暗号回路。
【請求項５】
請求項４に記載のＲＳＡ暗号回路を備えてなることを特徴とするＩＣカード。
【請求項６】
左バイナリ法によるＲＳＡ暗号処理過程で繰り返し実行するモンゴメリ乗算を、モンゴメリ乗算のアルゴリズムを２以上の前記アルゴリズムの中からランダムに選択して実行することを特徴とするＲＳＡ暗号処理方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【公開番号】特開２０１０−２７１３６３（Ｐ２０１０−２７１３６３Ａ）
【公開日】平成２２年１２月２日（２０１０．１２．２）
【国際特許分類】
【出願番号】特願２００９−１２０７２１（Ｐ２００９−１２０７２１）
【出願日】平成２１年５月１９日（２００９．５．１９）
【出願人】（０００００５０４９）シャープ株式会社 (33,933)
【Ｆターム（参考）】
【公開日】平成２２年１２月２日（２０１０．１２．２）
【国際特許分類】
【出願日】平成２１年５月１９日（２００９．５．１９）
【出願人】（０００００５０４９）シャープ株式会社 (33,933)
【Ｆターム（参考）】
[ Back to top ]