JP5233473B2 - 暗号処理装置 - Google Patents

Description

本発明は、暗号処理装置に関し、特に、外部から与えられた第１の数値Ｍに対して、秘密鍵となる数値Ｄを用いた演算を行うことにより第２の数値Ｃを生成し、これを外部へ出力する処理を行う暗号処理装置に関する。

暗号は、通信の秘密性を確保するために古くから利用されてきた技術であり、近年では、デジタル機器同士の交信を行う際に不可欠の技術になりつつある。たとえば、現在、様々な用途で利用されているＩＣカードの多くには、秘密鍵を用いた暗号化プロセスが組み込まれており、外部から与えられたデータに対して、内部で暗号化もしくは復号化を行う機能が備わっている。

ＩＣカードなどで、現在、最も普及している暗号化方式の一つとして、公開鍵暗号方式の代表格であるＲＳＡ暗号方式がある。このＲＳＡ暗号方式による暗号化もしくは復号化のプロセスには、指数関数を含む剰余演算が含まれており、この演算の繁雑さにより安全性の確保が図られている。たとえば、下記の特許文献１および２には、このＲＳＡ暗号方式による暗号化もしくは復号化の演算を高速化する技術が開示されている。

一方、このような暗号方式に基づくセキュリティを脅かす「サイドチャネル攻撃」と呼ばれているセキュリティに対する脅威となる技術の存在も確認されている。一般に、ＩＣカード等のデジタル機器に組み込まれているＩＣチップは、多数のトランジスタ回路で構成されており、上述した指数関数を含む繁雑な剰余演算は、このトランジスタ回路によって実行されることになる。このため、ＩＣカード等のデジタル機器が、暗号化もしくは復号化のプロセスを実行している最中に、当該機器の消費電力を外部からモニタすることにより、内部で行われている処理を統計的な手法で推定することが可能になる。このような不正な解析方法として、単純電力解析（ＳＰＡ：Simple Power Analysis）や電力差分解析（ＤＰＡ：Differential Power Analysis）などの方法が知られている。これらの方法を用いると、不正に入手したＩＣカードに対する統計的な解析を行うことにより、内蔵されている秘密鍵の値を推定することが可能になる。

このようなサイドチャネル攻撃に対抗する方法として、たとえば、下記の特許文献３には、演算に乱数を組み込む手法が開示されており、下記の特許文献４には、より複雑な剰余演算の組み合わせを行う手法が開示されている。また、下記の特許文献５には、本来は必要のないダミー乗算を付加するとともに、乗数をべき乗の途中で更新することにより、ダミー乗算か否かの区別をしにくくする手法が開示されている。
特開平７−１２９０８５号公報 特開平８−２５４９４９号公報 特表２００２−５１９７２２号公報 特開２００６−２１７１９３号公報 特開２００７−３１６４９１号公報

上述したように、サイドチャネル攻撃に対抗する方法として、従来、暗号化や復号化に用いる演算式に工夫を施し、より複雑な演算式を用いる様々な方法が提案されている。しかしながら、複雑な演算式を用いるようにすればするほど、演算負担が重くなるという弊害が生じる。

そこで本発明は、暗号化もしくは復号化に用いる演算式自体に改変を加えることなしに、サイドチャネル攻撃を防ぐことができる暗号処理装置を提供することを目的とする。

(0) 本発明の基本態様は、外部から与えられた第１の数値Ｍに対して、秘密鍵となる数値Ｄを用いた演算を行うことにより第２の数値Ｃを生成し、これを外部へ出力する処理を行う暗号処理装置において、
第１の数値Ｍを外部から入力する入力部と、
秘密鍵となる数値Ｄを格納する秘密鍵格納部と、
乱数Ｒを発生させる乱数発生部と、
発生させた乱数Ｒを用いて、数値Ｄを、１つの桁の数値ｄが「０≦ｄ≦ｄmax（但し、ｄmax＞ｋ−１）」の範囲内の値をとる冗長なｋ進数で表現したランダムなｎ桁のデータに再符号化する再符号化部と、
少なくとも数値Ｍと再符号化された数値Ｄとを用いた所定の演算を行うことにより、第２の数値Ｃを求める演算実行部と、
演算実行部が求めた第２の数値Ｃを外部へ出力する出力部と、
を設けるようにしたものである。

(1) 本発明の第１の態様は、上述した基本態様を備えた暗号処理装置において、
再符号化部を、
乱数Ｒを用いて「０≦ｄ≦ｄmax」の範囲内の値を発生させる処理をｎ回繰り返すことによりｎ桁のランダムデータを生成するランダムデータ生成要素と、
生成されたランダムデータが数値Ｄに等しいか否かを判断する数値確認要素と、
数値確認要素が等しいとの判断を行うまで、ランダムデータ生成要素にランダムデータの生成を繰り返し実行させ、数値確認要素が等しいとの判断を行った際のランダムデータを再符号化したデータとして出力する制御要素と、
によって構成したものである。

(2) 本発明の第２の態様は、上述した基本態様を備えた暗号処理装置において、
再符号化部を、
ｎ桁のデータを保持するレジスタと、
秘密鍵となる数値Ｄを、１つの桁の数値ｄが「０≦ｄ≦ｋ−１」の範囲内の値をとる通常のｋ進数で表現することにより、ｎ桁からなるデータを用意し、用意したデータを初期データとしてレジスタに設定する初期データ設定要素と、
発生させた乱数Ｒを用いて、レジスタのｎ桁のうちの任意の１桁を選択桁として選択する桁選択要素と、
発生させた乱数Ｒを用いて、増加補正もしくは減少補正のいずれかを決定する増減決定要素と、
増減決定要素により増加補正が決定された場合には、選択桁の数値ｄについてｄ＜ｄmaxが満たされ、かつ、他の桁の調整によって所定の増加補正分δ（但し、δ≦ｄmax−ｄ）を相殺することが可能であることを条件として、選択桁に増加補正分δを加え、他の桁を調整して増加補正分δを相殺する補正を行う増加補正実行要素と、
増減決定要素により減少補正が決定された場合には、選択桁の数値ｄについてｄ≠０が満たされ、かつ、他の桁の調整によって所定の減少補正分δ（但し、δ≦ｄ）を相殺することが可能であることを条件として、選択桁から減少補正分δを減じ、他の桁を調整して減少補正分δを相殺する補正を行う減少補正実行要素と、
所定の条件が満たされるまで、桁選択要素による桁選択、増減決定要素による増減決定、増加補正実行要素もしくは減少補正実行要素による補正を繰り返し実行し、所定の条件が満たされたときのレジスタ内のｎ桁のデータを再符号化したデータとして出力する制御要素と、
によって構成したものである。

(3) 本発明の第３の態様は、上述した基本態様を備えた暗号処理装置において、
再符号化部を、
数値Ｄをｍ×ｎビット（ｍ，ｎは整数）の２進数として保持する数値Ｄ保持要素と、
乱数Ｒを用いて、「Ｅ＜Ｄ」を満足する任意の数値Ｅをｍ×ｎビットの２進数として生成する数値Ｅ生成要素と、
数値Ｅの下位ｍビットを０に置換することにより、新たな数値Ａを生成する数値Ａ生成要素と、
Ｂ＝Ｄ−Ａなる演算により、ｍ×ｎビットの２進数からなる数値Ｂを生成する数値Ｂ生成要素と、
数値Ａを構成するビットの下位側から数えて第（ｍ×（ｉ＋１））ビット目から下位に向かって連続するｍビット分の数値を上位ビット、数値Ｂを構成するビットの下位側から数えて第（ｍ×ｉ）ビット目から下位に向かって連続するｍビット分の数値を下位ビット、とする２ｍビットからなる数値（但し、ｉ＝１〜ｎとし、数値Ａについては、上位側にｍビット分の０を補う）を、下位側から数えて第ｉ番目の桁とするｎ桁のデータを生成し、これを冗長な２ ^ｍ 進数で表現した数値Ｄを示すデータとして出力する冗長データ生成要素と、
によって構成したものである。

(4) 本発明の第４の態様は、上述した第１〜第３の態様に係る暗号処理装置において、
演算実行部が、Ｍ ^Ｄ の項を含む所定の演算式もしくはＭに基づいて定まる有理点Ｐをスカラー値Ｄでスカラー倍する楕円曲線暗号の演算式に基づく演算を行うことにより、第２の数値Ｃを求めるようにしたものである。

(5) 本発明の第５の態様は、上述した第４の態様に係る暗号処理装置において、
演算実行部が、Ｍ ^Ｄ を所定の数値Ｚで除したときのべき乗剰余を示す演算式Ｃ＝Ｍ ^Ｄ modＺに基づく演算を行うことにより、第２の数値Ｃを求めるようにしたものである。

(6) 本発明の第６の態様は、上述した第５の態様に係る暗号処理装置において、
再符号化部が、数値Ｄを、上位桁側から順に、ｄ［ｎ−１］，ｄ［ｎ−２］，ｄ［ｎ−３］，... ，ｄ［２］，ｄ［１］，ｄ［０］なるｎ桁のデータに再符号化する処理を行い、
演算実行部が、演算式Ｃ＝Ｍ ^Ｄ modＺに基づく演算を、
Ｃ＝（（ .....（（（１＊Ｍ ^{ｄ［ｎ−１］} ） ^ｋ
＊Ｍ ^{ｄ［ｎ−２］} modＺ） ^ｋ
＊Ｍ ^{ｄ［ｎ−３］} modＺ） ^ｋ
.....
＊Ｍ ^ｄ［２］ modＺ） ^ｋ
＊Ｍ ^ｄ［１］ modＺ） ^ｋ
＊Ｍ ^ｄ［０］ modＺ
なる等価演算式を用いて、括弧の内側の演算から順番に実行するようにしたものである。

(7) 本発明の第７の態様は、上述した第１〜第３の態様に係る暗号処理装置において、
演算実行部が、ＲＳＡ暗号、Diffie Hellman暗号、EL Gamal暗号、もしくは楕円曲線暗号を生成するための演算を行うことにより、第２の数値Ｃを求めるようにしたものである。

(8) 本発明の第８の態様は、上述した第１〜第７の態様に係る暗号処理装置において、
演算実行部が、再符号化部によって再符号化されたｎ桁のデータの中から１桁の数値ｄを抽出して用いる演算を、順番に繰り返し実行することにより第２の数値Ｃを求めるようにしたものである。

(9) 本発明の第９の態様は、上述した第１〜第８の態様に係る暗号処理装置において、
入力部が第１の数値Ｍを外部から入力するたびに、乱数発生部が新たな乱数Ｒを発生させ、再符号化部が新たな再符号化を行い、演算実行部が新たに再符号化された数値Ｄを用いて第２の数値Ｃを求める演算を行うようにしたものである。

(10) 本発明の第１０の態様は、上述した第１〜第９の態様に係る暗号処理装置をＩＣカードに内蔵させるようにしたものである。

(11) 本発明の第１１の態様は、上述した第１〜第９の態様に係る暗号処理装置を、コンピュータに専用のプログラムを組み込むことにより構成したものである。

本発明によれば、秘密鍵となる数値Ｄは、冗長なｋ進数で表現したランダムなｎ桁のデータに再符号化された上で、暗号化もしくは復号化に用いる演算式に適用される。冗長なｋ進数を用いれば、同じ数値Ｄを複数通りの表記方法で表現することができるので、同じ数値Ｄを用いて同じ演算式に基づく演算を繰り返し行ったとしても、トランジスタ回路によって行われる具体的な演算プロセスは、毎回、異なることになる。このため、ＳＰＡやＤＰＡといった電力解析による統計的手法を施しても、秘密鍵となる数値Ｄを推定することは困難になる。したがって、暗号化もしくは復号化に用いる演算式自体に改変を加えることなしに、サイドチャネル攻撃を防ぐことができる。

以下、本発明を図示する実施形態に基づいて説明する。

＜＜＜ §１．一般的なＲＳＡ暗号演算 ＞＞＞
はじめに、説明の便宜上、一般的なＲＳＡ暗号演算を例にとって、ＩＣカード内部で行われる暗号処理を説明する。ＲＳＡ暗号は、桁数が大きい合成数の素因数分解問題が困難であることを安全性の根拠とした公開鍵暗号の一つである。図１に、一般的な公開鍵暗号方式を用いた暗号化および復号化のプロセスを示すブロック図を示す。図示のとおり、暗号化の対象となる平文Ｍは、鍵Ｄを用いて暗号化され暗号文Ｃに変換される。一方、この暗号文Ｃは別な鍵Ｅを用いて復号化され平文Ｍに戻される。通常、鍵Ｄ，Ｅの一方を公開鍵、他方を秘密鍵として用いる。

図２は、一般的なＲＳＡ暗号方式で利用されているべき乗剰余演算式を示す図である。式（１）は、平文Ｍを暗号化して暗号文Ｃを生成するための演算式を示している。平文Ｍも暗号文Ｃも実際には何らかの数値として与えられる。数値Ｄは暗号化のための鍵であり、Ｚは所定の定数である。一方、式（２）は、暗号文Ｃを復号化して平文Ｍを生成するための演算式を示している。数値Ｅは復号化のための鍵であり、数値Ｄに応じて一義的に定まる値になる。Ｚは式（１）で用いた定数である。

なお、平文Ｍと暗号文Ｃという区別や、暗号化や復号化という区別は、利用者サイドから見た便宜上の区別であって、数学的には、両者は全く対等である。図２の式（１）は、単に、数値Ｍに対する演算により数値Ｃが得られることを示すものであり、図２の式（２）は、単に、数値Ｃに対する演算により数値Ｍが得られることを示すものである。数値Ｃ，Ｍのいずれを平文、いずれを暗号文と呼ぶかは、利用者側の便宜であり、式（１），（２）のいずれを暗号化、いずれを復号化と呼ぶかも、利用者側の便宜である。したがって、本願明細書では、以下、便宜上、式（１）を利用して「平文Ｍを暗号化して暗号文Ｃを得る」例を述べることにするが、もちろん本発明は、式（２）を利用して「暗号文Ｃを復号化して平文Ｍを得る」例にも適用可能である。

図３は、ＩＣカード１０と外部装置２０との間の認証にＲＳＡ暗号方式を利用した一般的なシステムを示すブロック図である。図示のとおり、ＩＣカード１０内には、制御ユニット１１と暗号処理装置１２とが設けられており、外部装置２０内には、認証処理部２１と暗号処理装置２２とが設けられている。ＩＣカード１０が接触型の場合は、表面に設けられた接触端子を介して外部装置２０に対して電気的な接続が行われ、両者間での交信が行われる。また、ＩＣカード１０が非接触型の場合は、外部装置２０の交信範囲内に入れることにより、両者間で無線交信が行われる。

なお、実際には、ＩＣカード１０や外部装置２０には、図３に示されている構成要素の他にも、様々な要素が組み込まれている。図３にブロックとして示した構成要素は、外部装置２０によってＩＣカード１０の認証処理を行うのに必要な構成要素のみである。

外部装置２０は、ＩＣカード１０と交信を開始すると、ＩＣカード１０が正規のデバイスであるか否かの認証を行う。具体的には、まず、外部装置２０側の認証処理部２１によって、第１の数値Ｍを発生させ（通常は、乱数が用いられる）、これを所定の認証コマンドとともにＩＣカード１０側に送信する。この認証コマンドおよび数値Ｍを受信した制御ユニット１１は、暗号処理装置１２に数値Ｍを引き渡し、暗号化の処理を実行させる。暗号処理装置１２は、与えられた第１の数値Ｍに対して、秘密鍵となる数値Ｄを用いた演算（この例では、図２の式（１）に示す演算）を実行して第２の数値Ｃを生成する。制御ユニット１１は、外部装置２０へ、生成された数値Ｃを認証コマンドに対するレスポンスとして送信する。

一方、外部装置２０は、発生させた第１の数値Ｍを暗号処理装置２２に引き渡し、暗号化の処理を実行させる。暗号処理装置２２は、与えられた第１の数値Ｍに対して、秘密鍵となる数値Ｄを用いた演算（この例では、やはり図２の式（１）に示す演算）を実行して第２の数値Ｃを生成する。認証処理部２１は、ＩＣカード１０側から送信されてきた数値Ｃと、暗号処理装置２２によって生成された数値Ｃとを比較し、両者が一致すれば、ＩＣカード１０を正規のデバイスであると認証することができる。あるいは、ＩＣカード１０側から送信されてきた数値Ｃについて、暗号処理装置２２に、図２の式（２）に示す復号化の演算を実行させて数値Ｍを生成させ、この数値Ｍが、認証処理部２１が最初に生成した数値Ｍに一致することを確認してもよい。

同様の方法で、ＩＣカード１０側が、現在交信中の外部装置２０を正規の装置であると認証することもできる。こうして、両者間で互いに交信相手が正規の相手であることが認証できれば、両者間で様々な処理のための交信が行われる。その際、必要に応じて、交信対象となるデータに対して、秘密鍵となる数値Ｄを用いた暗号化や復号化を行うことができる。

上述した認証処理や暗号化／復号化処理は、既にＩＣカードを利用したシステムにおいて広く利用されている処理である。秘密鍵となる数値Ｄは、ＩＣカード１０内の暗号処理装置１２内に格納されており、通常、外部には決して読み出されることがない仕様になっている。したがって、たとえＩＣカード１０が不正者の手元に渡ったとしても、秘密鍵Ｄが不正者に知られることはないはずである。しかしながら、実際には、既に述べたように、単純電力解析（ＳＰＡ）や電力差分解析（ＤＰＡ）といった「サイドチャネル攻撃」により、秘密鍵Ｄの値を推定されてしまう可能性がある。

特に、暗号処理装置１２の内部で行われる演算が、第１の数値Ｍに対する秘密鍵Ｄのべき乗「Ｍ^Ｄ」の項を含む演算の場合、秘密鍵Ｄの値が推定される危険性が高くなる。これは、Ｍ^Ｄの項を含む所定の演算式に基づく演算が、実際には、数値Ｄの各桁を用いた繰り返し演算によって実行されるため、ＩＣカード１０の消費電力の時間変化を統計的に解析することにより、数値Ｄの各桁の値の推定を許してしまうためである。

たとえば、前述したＲＳＡ暗号方式の場合、暗号処理装置１２の内部では、図２の式（１）に示す演算、すなわち、Ｍ^Ｄを所定の数値Ｚで除したときのべき乗剰余を示す演算式Ｃ＝Ｍ^Ｄ modＺに基づく演算を実行する必要がある。ところが、このようなべき乗剰余演算をコンピュータで実行するには、実際には、図４に示すような等価演算式を用いた演算を行う必要がある。すなわち、演算式Ｃ＝Ｍ^Ｄ modＺに基づく数値Ｃは、実際には、
Ｃ＝（（ .....（（（１＊Ｍ^{ｄ［ｎ−１］}）^２
＊Ｍ^{ｄ［ｎ−２］}modＺ）^２
＊Ｍ^{ｄ［ｎ−３］}modＺ）^２
.....
＊Ｍ^ｄ［２］modＺ）^２
＊Ｍ^ｄ［１］modＺ）^２
＊Ｍ^ｄ［０］modＺ
なる等価演算式を用いて、括弧の内側の演算から順番に実行することによって得られる。ここで、べき乗項として記載されているｄ［ｎ−１］，ｄ［ｎ−２］，ｄ［ｎ−３］，... ，ｄ［２］，ｄ［１］，ｄ［０］は、数値Ｄを２進表現したときのｎ桁の各ビット（上位桁側から順に並べたもの）であり、「＊」は乗算記号である。

図５は、図４に示す演算式おいて、２２［１０進］なる秘密鍵Ｄを２進表記にして適用した場合の具体的な演算手順を示す図である。すなわち、２２［１０進］を２進表記すれば、「１０１１０」となるので、上の等価演算式により数値Ｃの値を求めるには、ｎ＝５として、ｄ［４］＝１，ｄ［３］＝０，ｄ［２］＝１，ｄ［１］＝１，ｄ［０］＝０を代入すればよい。

図５の下段に示す等価演算式は、このような代入を行った例である。括弧の内側の演算から順番に実行すれば、まず、（１＊Ｍ^１）^２が実行され、続いて、その演算結果をＸとして、（Ｘ＊Ｍ^０modＺ）^２が実行され、続いて、その演算結果をＸとして、（Ｘ＊Ｍ^１modＺ）^２が実行され、続いて、その演算結果をＸとして、（Ｘ＊Ｍ^１modＺ）^２が実行され、最後に、その演算結果をＸとして、（Ｘ＊Ｍ^０modＺ）が実行される。但し、Ｍ^１＝Ｍであるのに対して、Ｍ^０＝１であるから、（Ｘ＊Ｍ^０modＺ）^２を演算するときと、（Ｘ＊Ｍ^１modＺ）^２を演算するときとでは、演算負担が大きく異なり、消費電力に差が生じることになる。したがって、「サイドチャネル攻撃」により、ＩＣカード内部の消費電力をモニタし、これを統計的に解析すれば、秘密鍵Ｄを構成するビットの０と１の並び順を推定されてしまう可能性がある。

一方、数値Ｄを２進数以外の数値表記で取り扱った演算も可能であるが、「サイドチャネル攻撃」に対して脆弱性を有することに変わりはない。たとえば、図６は、４進数の秘密鍵Ｄを用いたべき乗剰余演算を暗号処理装置の内部で実行する際の実際の演算式の一例を示す図である。すなわち、数値Ｄを４進表現したときの全ｎ桁の数値列を、ｄ［ｎ−１］，ｄ［ｎ−２］，ｄ［ｎ−３］，... ，ｄ［２］，ｄ［１］，ｄ［０］とすれば、演算式Ｃ＝Ｍ^Ｄ modＺに基づく数値Ｃは、実際には、
Ｃ＝（（ .....（（（１＊Ｍ^{ｄ［ｎ−１］}）^４
＊Ｍ^{ｄ［ｎ−２］}modＺ）^４
＊Ｍ^{ｄ［ｎ−３］}modＺ）^４
.....
＊Ｍ^ｄ［２］modＺ）^４
＊Ｍ^ｄ［１］modＺ）^４
＊Ｍ^ｄ［０］modＺ
なる等価演算式を用いて、括弧の内側の演算から順番に実行することによって得られる。

図７は、図６に示す演算式おいて、２２［１０進］なる秘密鍵Ｄを４進表記にして適用した場合の具体的な演算手順を示す図である。すなわち、２２［１０進］を４進表記すれば、「１１２」となるので、上の等価演算式により数値Ｃの値を求めるには、ｎ＝３として、ｄ［２］＝１，ｄ［１］＝１，ｄ［０］＝２を代入すればよい。

図７の下段に示す等価演算式は、このような代入を行った例である。括弧の内側の演算から順番に実行すれば、まず、（１＊Ｍ^１）^４が実行され、続いて、その演算結果をＸとして、（Ｘ＊Ｍ^１modＺ）^４が実行され、最後に、その演算結果をＸとして、（Ｘ＊Ｍ^２modＺ）が実行される。４進表記の場合、秘密鍵Ｄを構成する各桁は、０〜３のいずれかの数値をとることになるが、Ｍ^３＝Ｍ＊Ｍ＊Ｍ、Ｍ^２＝Ｍ＊Ｍ、Ｍ^１＝Ｍ、Ｍ^０＝１であるから、各桁のとる数値に応じて消費電力に差が生じることになり、やはり「サイドチャネル攻撃」により、秘密鍵Ｄを構成する各桁が、０〜３のいずれであるかを推定されてしまう可能性がある。

このような「サイドチャネル攻撃」に対する脆弱性は、数値Ｄを何進法で表記したとしても、根本的には解消することはできない。図８は、一般にｋ進数の秘密鍵Ｄを用いたべき乗剰余演算を暗号処理装置の内部で実行する際の実際の演算式の一例を示す図である。すなわち、数値Ｄをｋ進表現したときの全ｎ桁の数値列を、ｄ［ｎ−１］，ｄ［ｎ−２］，ｄ［ｎ−３］，... ，ｄ［２］，ｄ［１］，ｄ［０］とすれば、演算式Ｃ＝Ｍ^Ｄ modＺに基づく数値Ｃは、実際には、
Ｃ＝（（ .....（（（１＊Ｍ^{ｄ［ｎ−１］}）^ｋ
＊Ｍ^{ｄ［ｎ−２］}modＺ）^ｋ
＊Ｍ^{ｄ［ｎ−３］}modＺ）^ｋ
.....
＊Ｍ^ｄ［２］modＺ）^ｋ
＊Ｍ^ｄ［１］modＺ）^ｋ
＊Ｍ^ｄ［０］modＺ
なる等価演算式を用いて、括弧の内側の演算から順番に実行することによって得られるが、各桁のとる数値に応じて消費電力に差が生じることに変わりはなく、「サイドチャネル攻撃」により、秘密鍵Ｄを構成する各桁が推定されてしまう可能性がある。

以上、一般的なＲＳＡ暗号方式によるべき乗剰余演算を実行する場合に、「サイドチャネル攻撃」による脆弱性が生じることを説明したが、このような問題は、Diffie Hellman暗号方式、EL Gamal暗号方式など、他のべき乗剰余演算を利用する暗号方式にも共通した問題である。また、最近では、楕円曲線暗号方式も利用されているが、この楕円曲線暗号方式に対しても、「サイドチャネル攻撃」による脆弱性が生じることに変わりはない。本発明は、このような様々な暗号方式における「サイドチャネル攻撃」に対処することが可能な新たな手法を提案するものである。

＜＜＜ §２．本発明の基本概念 ＞＞＞
本発明の重要な特徴は、秘密鍵となる数値Ｄを、冗長なｋ進数で表現した上で、実際の演算に利用する点にある。いま、図９に示すように、数値Ｄを任意のｋ進数で表現することを考えよう。図において、ｄ［ｎ−１］，ｄ［ｎ−２］，ｄ［ｎ−３］，... ，ｄ［２］，ｄ［１］，ｄ［０］は、それぞれ数値Ｄをｋ進表現したときの全ｎ桁の数値列であり、この全ｎ桁の数値列として表現される数値Ｄの値は、図示のとおり、
Ｄ＝ｄ［ｎ−１］＊ｋ^ｎ−１
＋ｄ［ｎ−２］＊ｋ^ｎ−２
＋ｄ［ｎ−３］＊ｋ^ｎ−３
.....
＋ｄ［２］＊ｋ^２
＋ｄ［１］＊ｋ^１
＋ｄ［０］＊ｋ^０
となる。

ここで、第ｉ桁目の数値をｄ［ｉ］とすれば、
０≦ｄ［ｉ］≦ｄmax
であり、通常のｋ進表現の場合は、ｄmax＝ｋ−１に設定される。たとえば、２進表現の場合であれば、ｄmax＝１に設定されるので、各桁の数値ｄ［ｉ］は０または１のいずれかである。４進表現の場合は、ｄmax＝３に設定されるので、各桁の数値ｄ［ｉ］は０〜３のいずれかになり、７進表現の場合は、ｄmax＝６に設定されるので、各桁の数値ｄ［ｉ］は０〜６のいずれかになる。

これに対して、冗長ｋ進表現の場合は、ｄmax＞ｋ−１に設定される。たとえば、冗長２進表現の場合であれば、ｄmax＝２以上に設定されることになる。図１０(a) に示すとおり、通常２進表現の場合、ｄmax＝１であるから、各桁の数値ｄ［ｉ］は、
０≦ｄ［ｉ］≦１（各桁の値は０〜１）
であるが、冗長２進表現の場合、ｄmax＝３に設定すれば、図１０(a) に示すとおり、
０≦ｄ［ｉ］≦３（各桁の値は０〜３）
となる。

もちろん、冗長２進表現におけるｄmaxは２以上であればいくつに設定してもよい。ｄmax＝５に設定すれば、各桁の数値ｄ［ｉ］は０〜５のいずれかになる。同様に、冗長４進表現の場合であれば、ｄmax＝４以上に設定すればよいので、たとえば、ｄmax＝７に設定すれば、各桁の数値ｄ［ｉ］は０〜７のいずれかになり、ｄmax＝９に設定すれば、各桁の数値ｄ［ｉ］は０〜９のいずれかになる。

ここで重要な点は、冗長ｋ進表現を用いると、同じ数値Ｄを複数通りの表記方法で表現することができる点である。図１１は、数値Ｄ＝２２［１０進］を、通常２進表現および冗長２進表現で表した例を示す図である。図１１(a) の「１０１１０」が、通常２進表現による表記方法を示しているのに対して、図１１(b1)の「１００２２」、図１１(b2)の「０１２２２」、図１１(b3)の「０２０３０」は、いずれも冗長２進表現による表記方法を示している（この他にも、数値Ｄ＝２２［１０進］の冗長２進表記方法は存在する。もちろん、図１１(a) の「１０１１０」も、冗長２進表現の一形態に含まれることになる）。各表記方法を比較すると、５桁の数字の構成は互いに異なっているが、右側の計算結果を見れば明らかなように、いずれも同一の数値Ｄ＝２２［１０進］を示す点では共通している。

図１２は、４進数の例である。図１２(a) に示すとおり、通常４進表現の場合、ｄmax＝３であるから、各桁の数値ｄ［ｉ］は、
０≦ｄ［ｉ］≦３（各桁の値は０〜３）
であるが、冗長４進表現の場合、たとえばｄmax＝７に設定すれば、図１２(b) に示すとおり、
０≦ｄ［ｉ］≦７（各桁の値は０〜７）
となる。

図１３は、数値Ｄ＝２２［１０進］を、通常４進表現および冗長４進表現で表した例を示す図である。図１３(a) の「１１２」が、通常４進表現による表記方法を示しているのに対して、図１３(b1)の「１０６」、図１３(b2)の「０５２」は、いずれも冗長４進表現による表記方法を示している（この他にも、数値Ｄ＝２２［１０進］の冗長４進表記方法は存在する。もちろん、図１３(a) の「１１２」も、冗長４進表現の一形態に含まれることになる）。各表記方法を比較すると、３桁の数字の構成は互いに異なっているが、右側の計算結果を見れば明らかなように、いずれも同一の数値Ｄ＝２２［１０進］を示す点では共通している。

このように、同一の数値Ｄ＝２２［１０進］であっても、冗長ｋ進数を用いた表記を行えば、複数通りの表記方法で表現することができるので、演算を行う際に、複数通りの表記方法のいずれかを選択して用いるようにすれば、同じ数値Ｄを用いて同じ演算式に基づく演算を繰り返し行ったとしても、トランジスタ回路によって行われる具体的な演算プロセスは、毎回、異なることになる。このため、ＳＰＡやＤＰＡといった電力解析による統計的手法を施しても、秘密鍵となる数値Ｄを推定することは困難になる。これが本発明の基本原理である。

§１で述べたとおり、図５は、２２［１０進］なる秘密鍵Ｄの通常２進表記「１０１１０」を用いて、数値Ｃを求める演算を行う手順を示す図である。これに対して、図１４は、２２［１０進］なる秘密鍵Ｄの冗長２進表記の１つである「１００２２」を用いて、数値Ｃを求める演算を行う手順を示す図である。両者は、全く同じ演算式であり、秘密鍵Ｄの数値も全く同一であるから、得られる数値Ｃの演算結果も両者では全く同じになる。したがって、図５に示す演算の代わりに、図１４に示す演算を実行しても、暗号処理演算としては何ら支障は生じない。

ところが、全く同じ数値Ｍ，Ｄ，Ｚを与えて、全く同じ演算式に基づく演算を実行しているにもかかわらず、図５に示す演算と図１４に示す演算とでは、個々の括弧内の演算時の消費電力は異なってくる。すなわち、図５の場合、（１＊Ｍ^１）^２が実行され、その演算結果をＸとして（Ｘ＊Ｍ^０modＺ）^２が実行され、その演算結果をＸとして（Ｘ＊Ｍ^１modＺ）^２が実行され、その演算結果をＸとして（Ｘ＊Ｍ^１modＺ）^２が実行され、その演算結果をＸとして（Ｘ＊Ｍ^０modＺ）が実行されるのに対して、図１４の場合、（１＊Ｍ^１）^２が実行され、その演算結果をＸとして（Ｘ＊Ｍ^０modＺ）^２が実行され、その演算結果をＸとして（Ｘ＊Ｍ^０modＺ）^２が実行され、その演算結果をＸとして（Ｘ＊Ｍ^２modＺ）^２が実行され、その演算結果をＸとして（Ｘ＊Ｍ^２modＺ）が実行される。

もちろん、２２［１０進］なる秘密鍵Ｄの冗長２進表記は、図１１に示すとおり、他にも「０１２２２」，「０２０３０」等があるので、これら複数の冗長２進表記をランダムに選択して演算に利用するようにすれば、全く同じ数値Ｍ，Ｄ，Ｚを与えて、全く同じ演算式に基づく演算を実行しているにもかかわらず、消費電力のパターンは毎回異なることになる。したがって、ＩＣカード内部の消費電力をモニタし、これを統計的に解析する手法を採る「サイドチャネル攻撃」が行われたとしても、得られる消費電力のパターンには画一性が失われるため、統計的な解析によって数値Ｄの値を推定することは困難になる。

もちろん、本発明は冗長２進表記を用いる例に限定されるものではない。§１で述べたとおり、図７には、２２［１０進］なる秘密鍵Ｄの通常４進表記「１１２」を用いて、数値Ｃを求める演算を行う手順が示されている。これに対して、図１５は、２２［１０進］なる秘密鍵Ｄの冗長４進表記の１つである「１０６」を用いて、数値Ｃを求める演算を行う手順を示す図である。両者は、全く同じ演算式であり、秘密鍵Ｄの数値も全く同一であるから、得られる数値Ｃの演算結果も両者では全く同じになる。したがって、図７に示す演算の代わりに、図１５に示す演算を実行しても、暗号処理演算としては何ら支障は生じない。

ところが、全く同じ数値Ｍ，Ｄ，Ｚを与えて、全く同じ演算式に基づく演算を実行しているにもかかわらず、図７に示す演算と図１５に示す演算とでは、個々の括弧内の演算時の消費電力は異なってくる。すなわち、図７の場合、（１＊Ｍ^１）^４が実行され、その演算結果をＸとして（Ｘ＊Ｍ^１modＺ）^４が実行され、その演算結果をＸとして（Ｘ＊Ｍ^２modＺ）^２が実行されるのに対して、図１５の場合、（１＊Ｍ^１）^４が実行され、その演算結果をＸとして（Ｘ＊Ｍ^０modＺ）^４が実行され、その演算結果をＸとして（Ｘ＊Ｍ^６modＺ）^２が実行される。

もちろん、２２［１０進］なる秘密鍵Ｄの冗長４進表記は、図１３に示すとおり、他にも「１０６」，「０５２」等があるので、これら複数の冗長４進表記をランダムに選択して演算に利用するようにすれば、全く同じ数値Ｍ，Ｄ，Ｚを与えて、全く同じ演算式に基づく演算を実行しているにもかかわらず、消費電力のパターンは毎回異なることになり、「サイドチャネル攻撃」への対策は有効になる。しかも、暗号処理に用いる演算式は、あくまでも「Ｃ＝Ｍ^Ｄ modＺ」という同一の演算式ですむ。このように、暗号化もしくは復号化に用いる演算式自体に改変を加えることなしに、サイドチャネル攻撃を防ぐことができる点が、本発明の重要な特徴である。

結局、本発明の本質的な技術思想は、秘密鍵となる数値Ｄを内蔵している演算処理装置に対して、外部から第１の数値Ｍを与え、当該演算処理装置の内部で、少なくとも数値Ｍと数値Ｄとを用いた演算を実行させることにより第２の数値Ｃを生成させ、これを外部へ出力させる暗号処理方法において、当該演算処理装置の内部で、数値Ｄを、１つの桁の数値ｄが「０≦ｄ≦ｄmax（但し、ｄmax＞ｋ−１）」の範囲内の値をとる冗長なｋ進数で表現したランダムデータを生成させ、このランダムデータを用いて第２の数値Ｃを生成する演算を実行させる点にある。

特に、演算処理装置としてＩＣカードを用いる場合であれば、秘密鍵となる数値Ｄを内蔵し、演算処理機能および乱数発生機能を有するＩＣカードに対して、外部から第１の数値Ｍを与え、当該ＩＣカードの内部で、少なくとも数値Ｍと数値Ｄとを用いた演算を実行させることにより第２の数値Ｃを生成させ、これを外部へ出力させる暗号処理方法において、当該ＩＣカードの内部で、数値Ｄを、１つの桁の数値ｄが「０≦ｄ≦ｄmax（但し、ｄmax＞ｋ−１）」の範囲内の値をとる冗長なｋ進数で表現したランダムデータを、乱数発生機能を用いて生成させ、このランダムデータを用いて第２の数値Ｃを生成する演算を実行させるようにすればよい。

＜＜＜ §３．本発明に係る暗号処理装置 ＞＞＞
図１６は、本発明に係る暗号処理装置１００の構成を示すブロック図である。この暗号処理装置１００は、たとえば、図３に示す暗号処理装置１２としてＩＣカード１０に組み込むことができる。もっとも、この図１６に示す個々のブロックは、実際には、コンピュータ用のハードウエアおよびこのコンピュータに組み込まれたプログラムによって実現可能な構成要素であり、たとえば、ＩＣカード１０に、ＯＳプログラムやアプリケーションプログラムを組み込むことによって実現されることになる。

この図３に示す暗号処理装置１００の基本機能は、外部から与えられた第１の数値Ｍに対して、秘密鍵となる数値Ｄを用いた演算を行うことにより第２の数値Ｃを生成し、これを外部へ出力する処理を行うことである。そのため、この暗号処理装置１００は、図示のとおり、第１の数値Ｍを外部から入力する入力部１１０と、生成した第２の数値Ｃを外部へ出力する出力部１２０と、第２の数値Ｃを生成する演算実行部１３０と、再符号化部１４０と、秘密鍵となる数値Ｄを格納する秘密鍵格納部１５０と、乱数Ｒを発生させる乱数発生部１６０と、を有している。

ここで、再符号化部１４０は、乱数発生部１６０が発生させた乱数Ｒを用いて、秘密鍵格納部１５０に格納されている数値Ｄを再符号化する構成要素である。再符号化は、数値Ｄを、１つの桁の数値ｄが「０≦ｄ≦ｄmax（但し、ｄmax＞ｋ−１）」の範囲内の値をとる冗長なｋ進数で表現したランダムなｎ桁のデータとして表現することによって行われる。

たとえば、秘密鍵格納部１５０に格納されている数値Ｄが、Ｄ＝２２［１０進］であり（図示の例では、通常の２進数「１０１１０」の形で、秘密鍵格納部１５０に格納されていることになる）、これを冗長な２進数で表現した形に再符号化する場合（演算実行部１３０が、２進表記された秘密鍵Ｄを用いて演算を行う場合）であれば、再符号化部１４０は、乱数Ｒを利用して、図１１(b1)の「１００２２」、図１１(b2)の「０１２２２」、図１１(b3)の「０２０３０」等の複数通りの「Ｄ＝２２［１０進］に対応する冗長２進表記」（通常２進表記の「１０１１０」を含む）の中の１つをランダムに選択することにより、冗長２進表記されたｎ桁の数値からなるデータを生成する処理を行う。このような再符号化の具体的な方法については、§４で述べる。

演算実行部１３０は、少なくとも、入力部１１０が入力した数値Ｍと、再符号化部１４０によって再符号化された数値Ｄ（冗長ｋ進表記されたｎ桁の数値）と、を用いた所定の演算を行うことにより、第２の数値Ｃを生成する構成要素である。ここでは、前述したとおり、ＲＳＡ暗号方式の実施例が示されているので、演算実行部１３０は、予め設定されている所定の定数Ｚを用いて、演算式Ｃ＝Ｍ^Ｄ modＺに基づく演算を行うことにより、第２の数値Ｃを求めることになる。

既に述べたとおり、この演算は、実際には、図８に示すような等価演算式を用いた繰り返し演算によって行われる。すなわち、演算実行部１３０は、再符号化部１４０によって再符号化されたｎ桁のデータの中から１桁の数値ｄを抽出して用いる演算を、順番に繰り返し実行することにより第２の数値Ｃを求めることになる。

なお、ここに示す実施形態の場合、入力部１１０が第１の数値Ｍを外部から入力するたびに、乱数発生部１６０が新たな乱数Ｒを発生させ、再符号化部１４０が新たな再符号化を行い、演算実行部１３０が新たに再符号化された数値Ｄを用いて第２の数値Ｃを求める演算を行うようにしている。したがって、第１の数値Ｍが与えられるたびに、数値Ｄを構成するｎ桁の数値の組み合わせは一新されることになり、演算実行部１３０は、この一新された数値Ｄを用いて演算を行うことになる。

もちろん、数値Ｄを構成するｎ桁の数値の組み合わせは、必ずしも第１の数値Ｍを外部から入力するたびに毎回更新する必要はなく、たとえば、第１の数値Ｍを３回入力する度に一新する、という方法を採ってもかまわないが、「サイドチャネル攻撃」への対策を効果的にする上では、上述したように、第１の数値Ｍを外部から入力するたびに毎回更新するのが好ましい。

＜＜＜ §４．再符号化の具体的な方法 ＞＞＞
最後に、図１６に示す再符号化部１４０の具体的な構成例をいくつか示すことにより、再符号化処理の具体的な手順を例示する。もっとも、以下に述べる具体例は、あくまでも実施例として示すものであり、本発明に用いる再符号化部１４０の構成は、これらの実施例に限定されるものではない。

＜実施例１＞
図１７は、図１６に示す暗号処理装置の再符号化部１４０の第１の構成例を示すブロック図である。図示のとおり、この例の場合、再符号化部１４０Ａは、制御要素１４１Ａ、数値確認要素１４２Ａ、ランダムデータ生成要素１４３Ａによって構成されている。

ランダムデータ生成要素１４３Ａは、乱数発生部１６０から与えられる乱数Ｒを用いて「０≦ｄ≦ｄmax」の範囲内の値を発生させる処理をｎ回繰り返すことによりｎ桁のランダムデータを生成する機能を果たす。ここで生成されたランダムデータは、数値確認要素１４２Ａに与えられる。数値確認要素１４２Ａは、ランダムデータ生成要素１４３Ａが生成したランダムデータが、秘密鍵格納部１５０から読み出された数値Ｄと等しいか否かの判定を行い、その結果を制御要素１４１Ａに報告する。制御要素１４１Ａは、数値確認要素１４２Ａが等しいとの判断を行うまで、ランダムデータ生成要素１４３Ａにランダムデータの生成を繰り返し実行させ、数値確認要素１４２Ａが等しいとの判断を行った際のランダムデータを再符号化したデータ（数値Ｄを冗長ｋ進表記したｎ桁の数値）として出力する。

図１８は、図１７に示す再符号化部１４０Ａの動作を説明する流れ図である。まず、ステップＳ１１において、ランダムデータ生成要素１４３Ａによるｎ桁のランダムデータ生成処理が行われる。たとえば、図１１に示すように、各桁の数値が０〜３の範囲をとる５桁の数値からなるランダムデータを生成するのであれば、０〜３の範囲内の整数値をとる乱数を発生させる処理を５回繰り返して実行し、発生させた５つの整数を並べ、これをランダムデータとして出力すればよい。いわば、０〜ｄmaxまでの整数の目をもつｎ個のサイコロを振って、出た目をそのまま並べることにより、ランダムデータが生成されることになる。

続いて、ステップＳ１２では、数値確認要素１４２による比較処理が行われる。すなわち、生成されたランダムデータが示す数値と、秘密鍵格納部１５０から読み出された数値Ｄとが比較される（図９に示す加算によって値が決定される）。そして、制御要素１４１Ａが、ステップＳ１３において等しいと判断されるまで、ステップＳ１１の処理が繰り返されるような制御を行い、等しいと判断されたときには、ステップＳ１４へと進み、そのときのランダムデータを、再符号化データとして出力することになる。

要するに、この実施例１として例示する方法は、所望の数値Ｄと等しくなるランダムデータが得られるまで、繰り返しサイコロを振り続ける方法ということができる。この方法は、非常に単純な方法であるが、桁数ｎの値やｋの値が大きい場合には、数値Ｄに等しくなるランダムデータが得られるまで長時間を要することになるため、あまり好ましくない。

＜実施例２＞
図１９は、図１６に示す暗号処理装置の再符号化部１４０の第２の構成例を示すブロック図である。図示のとおり、この例の場合、再符号化部１４０Ｂは、制御要素１４１Ｂ、レジスタ１４２Ｂ、初期データ設定要素１４３Ｂ、増加補正実行要素１４４Ｂ、減少補正実行要素１４５Ｂ、桁選択要素１４６Ｂ、増減決定要素１４７Ｂによって構成されている。

レジスタ１４２Ｂは、再符号化プロセスの対象となるｋ進ｎ桁からなるデータを一時的に保持するための構成要素である。このレジスタ１４２Ｂには、初期データ設定要素１４３Ｂによって初期値の設定が行われる。すなわち、初期データ設定要素１４３Ｂは、秘密鍵格納部１５０から読み出した秘密鍵Ｄ（図示の例では、２進数の数値Ｄ）を、１つの桁の数値ｄが「０≦ｄ≦ｋ−１」の範囲内の値をとる通常のｋ進数で表現することにより、ｎ桁からなるデータを用意し、用意したデータを初期データとしてレジスタ１４２Ｂに設定する機能を果たす。

一方、桁選択要素１４６Ｂは、乱数発生部１６０が発生させた乱数Ｒを用いて、レジスタ１４２Ｂのｎ桁のうちの任意の１桁を選択桁として選択する機能を果たす。乱数Ｒを用いているため、ｎ桁のうちの任意の１桁がランダムに選択されることになる。また、増減決定要素１４７Ｂは、乱数発生部１６０が発生させた乱数Ｒを用いて、増加補正もしくは減少補正のいずれかを決定する機能を果たす。こちらも乱数Ｒを用いているため、増加補正もしくは減少補正がランダムに選択されることになる。増加補正と減少補正との選択比率は、１：１にする必要はない。実用上は、増加補正の選択頻度が減少補正の選択頻度より高くなるような設定を行うのが好ましい。

増加補正実行要素１４４Ｂは、増減決定要素１４７Ｂにより増加補正が決定された場合に、桁選択要素１４６Ｂが選択した選択桁の数値ｄについてｄ＜ｄmaxが満たされ、かつ、他の桁の調整によって所定の増加補正分δ（但し、δ≦ｄmax−ｄ）を相殺することが可能であることを条件として、選択桁に増加補正分δを加え、他の桁を調整して増加補正分δを相殺する補正を行う構成要素である。

これに対して、減少補正実行要素１４５Ｂは、増減決定要素１４７Ｂにより減少補正が決定された場合に、桁選択要素１４６Ｂが選択した選択桁の数値ｄについてｄ≠０が満たされ、かつ、他の桁の調整によって所定の減少補正分δ（但し、δ≦ｄ）を相殺することが可能であることを条件として、選択桁から減少補正分δを減じ、他の桁を調整して減少補正分δを相殺する補正を行う構成要素である。

そして、制御要素１４１Ｂは、所定の条件が満たされるまで、桁選択要素１４６Ｂによる桁選択、増減決定要素１４７Ｂによる増減決定、増加補正実行要素１４４Ｂもしくは減少補正実行要素１４５Ｂによる補正を繰り返し実行し、上記所定の条件が満たされたときのレジスタ１４２Ｂ内のｎ桁のデータを、再符号化したデータとして出力する構成要素である。

ここに示す再符号化部１４０Ｂによる再符号化処理の基本方針は、まず、通常のｋ進数で数値Ｄを表現したｎ桁のデータをレジスタ１４２Ｂに用意し、このレジスタ内のランダムに選択された桁の数値を、冗長ｋ進表現で許容可能な範囲内で増減補正し、当該増減分を別な桁の数値の増減で相殺するような調整を繰り返し実行する、というものである。選択桁の数値の増減は、別な桁の数値の増減で相殺されるため、レジスタ内に保持されているデータの値は常に数値Ｄに維持される。

図２０は、図１９に示す再符号化部１４０Ｂの動作を説明する流れ図である。まず、ステップＳ２１では、初期データ設定要素１４３Ｂによって初期値の設定が行われる。すなわち、秘密鍵としての数値Ｄに対応する通常ｋ進表現によるｎ桁のデータがレジスタ１４２Ｂに設定される。

続いて、ステップＳ２２では、桁選択要素１４６Ｂによる桁選択が行われ、続くステップＳ２３では、増減決定要素１４７Ｂによって、増加補正もしくは減少補正のいずれかが決定される。増加補正が決定された場合は、増加補正実行要素１４４Ｂによって、ステップＳ２４〜Ｓ２６の処理が実行され、減少補正が決定された場合は、減少補正実行要素１４５Ｂによって、ステップＳ２７〜Ｓ２９の処理が実行される。

すなわち、増加補正が決定された場合は、ステップＳ２４において、増加補正が可能か否かの条件判断が行われ、可能と判断された場合には、ステップＳ２５を経てステップＳ２６へと進み増加補正が実行される。不可能と判断された場合には、ステップＳ２５を経て増加補正を実行せずにステップＳ３０へ進むことになる。一方、減少補正が決定された場合は、ステップＳ２７において、減少補正が可能か否かの条件判断が行われ、可能と判断された場合には、ステップＳ２８を経てステップＳ２９へと進み減少補正が実行される。不可能と判断された場合には、ステップＳ２８を経て減少補正を実行せずにステップＳ３０へ進むことになる。

ステップＳ３０では、この手順をここで終了するか否かの判断がなされる。すなわち、予め設定しておいた所定の終了条件が満たされたときには、手順終了との判断がなされ、ステップＳ３１へと進むことになる。終了条件が満たされていないときには、再びステップＳ２２からの手順が繰り返し実行される。終了条件としては、たとえば、「ステップＳ２２からの手順が、Ｑ回繰り返して行われること」という繰り返し回数に基づく条件を設定しておくことができる。この場合、ステップＳ２２を実行するたびにカウンタの計数値を更新してゆき、カウンタの値がＱに等しくなったら、「終了条件を満足した」との判断がなされることになる。終了条件を満足してステップＳ３１へと進んだ場合には、その時点でレジスタに格納されているｎ桁の数値が、再符号化した数値Ｄ（冗長ｋ進表記）を示すデータとして出力されることになる。

これに対して、ステップＳ２４における条件判断はやや複雑である。基本的には、選択桁の数値ｄについてｄ＜ｄmaxが満たされ、かつ、他の桁の調整によって所定の増加補正分δ（但し、δ≦ｄmax−ｄ）を相殺することが可能である、との判断を行えばよい。前者の条件は、選択桁の数値を増加させることが可能か否かを判定するための条件である。１つの桁の数値ｄが「０≦ｄ≦ｄmax（但し、ｄmax＞ｋ−１）」の範囲内の値をとる冗長ｋ進表現を行う場合、ｄ＜ｄmaxでなければ、選択桁の数値をこれ以上増加させることはできない。一方、後者の条件は、選択桁の数値をδだけ増加させた場合、当該増加補正分δに対応する値を、他の桁に対する減少補正で相殺するための条件である。

図２０の流れ図には、このような条件判断のより具体的な一例が示されている。すなわち、図示の例では、常に増加補正分δ＝ｋに設定する単純な例であり、選択桁の数値ｄについては、ｄ＋ｋ≦ｄmaxというより厳しい条件を課している。これは、選択桁の数値に増加補正分ｋを加えても、ｄmaxを越えないようにするための条件である。一方、「他の桁の調整によって増加補正分ｋを相殺することが可能であるか否か」という条件判断については、「選択桁の上位に０でない桁があるか否か」という条件判断を代用している。これは、ｋ進表記されたデータの場合、選択桁の数値にｋを加算する補正は、選択桁のすぐ上位の桁（隣接上位桁）の数値から１を減じる補正によって必ず相殺できるためである（ｋ進表記では、選択桁の数値ｋは、隣接上位桁の数値１に対応する）。

このような条件を満足していると判断された場合には、ステップＳ２６に示す増加補正が実行される。具体的には、選択桁にｋを加える増加補正が行われ、隣接上位桁から１を減じる相殺処理が行われることになる（隣接上位桁が０の場合でも、更にその上位に存在する０でない桁を利用した減算が行われる）。

一方、ステップＳ２７における条件判断は、基本的には、選択桁の数値ｄについてｄ≠０が満たされ、かつ、他の桁の調整によって所定の減少補正分δ（但し、δ≦ｄ）を相殺することが可能である、との判断を行えばよい。前者の条件は、選択桁の数値を減少させることが可能か否かを判定するための条件である。選択桁の数値ｄが０である場合には、更に減少させることはできない。一方、後者の条件は、選択桁の数値をδだけ減少させた場合、当該減少補正分δに対応する値を、他の桁に対する増加補正で相殺するための条件である。

図２０の流れ図には、減少補正に関する条件判断の具体的な一例が示されている。すなわち、図示の例では、常に減少補正分δ＝１に設定する単純な例であり、「他の桁の調整によって減少補正分１を相殺することが可能であるか否か」という条件判断については、「隣接下位桁について、ｄ＋ｋ≦ｄmax」という条件判断を代用している。これは、ｋ進表記されたデータの場合、選択桁の数値から１を減じる補正は、選択桁のすぐ下位の桁（隣接下位桁）の数値にｋを加える補正によって必ず相殺できるためである（ｋ進表記では、選択桁の数値１は、隣接下位桁の数値ｋに対応する）。

このような条件を満足していると判断された場合には、ステップＳ２９に示す減少補正が実行される。具体的には、選択桁から１を減じる減少補正が行われ、隣接下位桁にｋを加える相殺処理が行われることになる。

図２１は、図２０の流れ図に基づく２進データの再符号化処理の一例を示す変遷図である。ここでは、１行目に示すとおり、Ｄ＝２２［１０進］を通常２進表記した「１０１１０」なるデータが初期データとしてレジスタに設定されているものとし、ｄmax＝３に設定して、１つの桁の数値ｄが「０≦ｄ≦３」の範囲内の値をとる冗長な２進数で表現したランダムな５桁のデータに再符号化する場合を考えてみる。なお、図において、特定桁の上に示す（＋）は、当該桁が増加補正の対象となる選択桁であることを示し、特定桁の上に示す（−）は、当該桁が減少補正の対象となる選択桁であることを示すものとする。

いま、図の２行目に示すように、右から２桁目について増加補正を行う選択が行われたとすると、当該選択は、図２０のステップＳ２４の条件を満たしている。すなわち、選択桁の数値ｄは１であり、ｋ＝２、ｄmax＝３であるから、「ｄ＋ｋ≦ｄmax」なる条件を満たし、しかも選択桁の上位には、０でない桁が存在している。そこで、ステップＳ２６の増加補正が実行され、図の３行目に示すように、第１回目の変遷が生じる。レジスタに得られている「１００３０」は、冗長２進数であり、その値はＤ＝２２［１０進］のまま変わりない。

次に、図の４行目に示すように、右から４桁目について増加補正を行う選択が行われたとすると、当該選択も、図２０のステップＳ２４の条件を満たしている。すなわち、選択桁の数値ｄは０であり、ｋ＝２、ｄmax＝３であるから、「ｄ＋ｋ≦ｄmax」なる条件を満たし、しかも選択桁の上位には、０でない桁が存在している。そこで、ステップＳ２６の増加補正が実行され、図の５行目に示すように、第２回目の変遷が生じる。レジスタに得られている「０２０３０」は、冗長２進数であり、その値はＤ＝２２［１０進］のまま変わりない。

続いて、図の６行目に示すように、右から５桁目について増加補正を行う選択が行われたとすると、当該選択は、図２０のステップＳ２４の条件を満たさない。すなわち、選択桁の数値ｄは０であり、ｋ＝２、ｄmax＝３であるから、「ｄ＋ｋ≦ｄmax」なる条件を満たすものの、選択桁の上位には、０でない桁は１つも存在しない。そこで、ステップＳ２５からステップＳ３０を経てステップＳ２２へと戻り、再度の選択が行われる。ここでは、図の７行目に示すように、右から４桁目について増加補正を行う選択が行われたとすると、当該選択は、やはり図２０のステップＳ２４の条件を満たさない。すなわち、選択桁の数値ｄは２であり、ｋ＝２、ｄmax＝３であるから、「ｄ＋ｋ≦ｄmax」なる条件を満たさず、また、選択桁の上位には、０でない桁は１つも存在しない。そこで、ステップＳ２５からステップＳ３０を経てステップＳ２２へと戻り、再度の選択が行われる。

そこで、図の８行目に示すように、右から１桁目について増加補正を行う選択が行われたとすると、当該選択は、図２０のステップＳ２４の条件を満たしている。すなわち、選択桁の数値ｄは０であり、ｋ＝２、ｄmax＝３であるから、「ｄ＋ｋ≦ｄmax」なる条件を満たし、しかも選択桁の上位には、０でない桁が存在している。そこで、ステップＳ２６の増加補正が実行され、図の９行目に示すように、第３回目の変遷が生じる。レジスタに得られている「０２０２２」は、冗長２進数であり、その値はＤ＝２２［１０進］のまま変わりない。

次に、図の１０行目に示すように、右から３桁目について減少補正を行う選択が行われたとすると、選択桁の数値ｄは０であるから、当該選択は、図２０のステップＳ２７の条件を満たさない。そこで、ステップＳ２８からステップＳ３０を経てステップＳ２２へと戻り、再度の選択が行われる。ここでは、図の１１行目に示すように、右から２桁目について減少補正を行う選択が行われたとすると、当該選択は、やはり図２０のステップＳ２７の条件を満たさない。すなわち、選択桁の数値ｄは２であるから、ｄ≠０という条件を満たすものの、隣接下位桁（すなわち、右から１桁目）の数値ｄ＝２であるあるから、隣接下位桁について「ｄ＋ｋ≦ｄmax」なる条件を満たさないことになる。そこで、ステップＳ２８からステップＳ３０を経てステップＳ２２へと戻り、再度の選択が行われる。

今度は、図の１２行目に示すように、右から４桁目について減少補正を行う選択が行われたとすると、当該選択は、図２０のステップＳ２７の条件を満たしている。すなわち、選択桁の数値ｄは２であるから、ｄ≠０という条件を満たし、隣接下位桁（すなわち、右から３桁目）の数値ｄ＝０であるあるから、隣接下位桁について「ｄ＋ｋ≦ｄmax」なる条件も満たしている。そこで、ステップＳ２９の減少補正が実行され、図の１３行目に示すように、第４回目の変遷が生じる。レジスタに得られている「０１２２２」は、冗長２進数であり、その値はＤ＝２２［１０進］のまま変わりない。

このような変遷プロセスを実行してゆき、ステップＳ３０の終了条件が満足された時点でレジスタに格納されていた５桁の数値が、再符号化した数値Ｄ（冗長２進表記）を示すデータとして出力されることになる。いずれの場合も、その値はＤ＝２２［１０進］のまま変わりない。

もうひとつ、４進の場合の実例を提示しておく。図２２は、図２０の流れ図に基づく４進データの再符号化処理の一例を示す変遷図である。ここでは、１行目に示すとおり、Ｄ＝２２［１０進］を通常４進表記した「１１２」なるデータが初期データとしてレジスタに設定されているものとし、ｄmax＝７に設定して、１つの桁の数値ｄが「０≦ｄ≦７」の範囲内の値をとる冗長な４進数で表現したランダムな３桁のデータに再符号化する場合を考えてみる。

まず、図の２行目に示すように、右から２桁目について減少補正を行う選択が行われたとすると、当該選択は、図２０のステップＳ２７の条件を満たしている。すなわち、選択桁の数値ｄは１であるから、ｄ≠０という条件を満たし、隣接下位桁（すなわち、右から１桁目）の数値ｄ＝２であるあるから、隣接下位桁について「ｄ＋ｋ≦ｄmax」なる条件も満たしている。そこで、ステップＳ２９の減少補正が実行され、図の３行目に示すように、第１回目の変遷が生じる。レジスタに得られている「１０６」は、冗長４進数であり、その値はＤ＝２２［１０進］のまま変わりない。

次に、図の４行目に示すように、再び右から２桁目について減少補正を行う選択が行われたとすると、選択桁の数値ｄは０であるから、当該選択は、図２０のステップＳ２７の条件を満たさない。そこで、ステップＳ２８からステップＳ３０を経てステップＳ２２へと戻り、再度の選択が行われる。ここでは、図の５行目に示すように、右から３桁目について増加補正を行う選択が行われたとすると、当該選択は、図２０のステップＳ２４の条件を満たさない。すなわち、選択桁の数値ｄは１であり、ｋ＝４、ｄmax＝７であるから、「ｄ＋ｋ≦ｄmax」なる条件を満たすものの、選択桁の上位には、０でない桁は１つも存在しない。そこで、ステップＳ２５からステップＳ３０を経てステップＳ２２へと戻り、再度の選択が行われる。

今度は、図の６行目に示すように、右から３桁目について減少補正を行う選択が行われたとすると、当該選択は、図２０のステップＳ２７の条件を満たしている。すなわち、選択桁の数値ｄは１であるから、ｄ≠０という条件を満たし、隣接下位桁（すなわち、右から２桁目）の数値ｄ＝０であるあるから、隣接下位桁について「ｄ＋ｋ≦ｄmax」なる条件も満たしている。そこで、ステップＳ２９の減少補正が実行され、図の７行目に示すように、第２回目の変遷が生じる。レジスタに得られている「０４６」は、冗長４進数であり、その値はＤ＝２２［１０進］のまま変わりない。

このような変遷プロセスを実行してゆき、ステップＳ３０の終了条件が満足された時点でレジスタに格納されていた３桁の数値が、再符号化した数値Ｄ（冗長４進表記）を示すデータとして出力されることになる。いずれの場合も、その値はＤ＝２２［１０進］のまま変わりない。

以上、図２０のステップＳ２４，Ｓ２７に例示された条件を用いた例を述べたが、前述したとおり、この例は、増加補正の場合の増加補正量δを常にｋとし、減少補正の場合の減少補正量δを常に１とし、しかも、隣接上位桁もしくは隣接下位桁の数値を調整することによってのみ、増減量の相殺を行う、というかなり限定的な運用を行う例である。したがって、実用上は、より柔軟な条件設定を行えば、より柔軟な増減補正を行うことも可能である。

図２２の８行目以下に示す例は、このように、より柔軟な増減補正を行った例である。たとえば、８行目には、右から２桁目について、増加補正量δ＝１とする増加補正を行う選択が行われた例が示されている。第３回目の変遷結果として９行目に示されているとおり、このような増加補正は、実際に可能である。この例では、選択桁の数値を１だけ増加させ、これを相殺するために、隣接下位桁（右から１桁目）の数値から４を減じる調整が行われている。レジスタに得られている「０５２」は、冗長４進数であり、その値はＤ＝２２［１０進］のまま変わりない。

続く１０行目には、右から３桁目について、増加補正量δ＝１とする増加補正を行う選択が行われた例が示されている。第４回目の変遷結果として１１行目に示されているとおり、このような増加補正は、実際に可能である。この例では、選択桁の数値を１だけ増加させ、これを相殺するために、隣接下位桁（右から２桁目）の数値から４を減じる調整が行われている。レジスタに得られている「１１２」は、初期データと同一のデータであり、通常４進の形式をとっているが、これも冗長４進数の表現形態の１つであることに変わりはない。

次の１２行目には、右から１桁目について、増加補正量δ＝４とする増加補正を行う選択が行われた例が示されており、第５回目の変遷結果として１３行目に示されているとおり、選択桁の数値を４だけ増加させ、これを相殺するために、隣接上位桁（右から２桁目）の数値から１を減じる調整が行われている。レジスタに得られている「１０６」は、第１回目の変遷結果と同一のデータである。ただ、第１回目の変遷結果は、右から２桁目についての減少補正の結果として得られたデータであったのに対し、第５回目の変遷結果は、右から１桁目についての増加補正の結果として得られたデータである。

＜実施例３＞
図２３は、図１６に示す暗号処理装置の再符号化部１４０の第３の構成例を示すブロック図である。図示のとおり、この例の場合、再符号化部１４０Ｃは、冗長データ生成要素１４１Ｃ、数値Ｂ生成要素１４２Ｃ、数値Ａ生成要素１４３Ｃ、数値Ｄ保持要素１４４Ｃ、数値Ｅ生成要素１４５Ｃによって構成されている。

ここに示す再符号化部１４０Ｃによる再符号化処理の基本方針は、まず、数値Ｄを、Ｄ＝Ａ＋Ｂを満たすような２つの数値Ａ，Ｂに分け、これら数値Ａ，Ｂを通常２進表記し、数値Ａの特定ビット部分と数値Ｂの特定ビット部分とを、桁を若干ずらして加え合わせることにより、冗長データの１桁の数値を決定する、というものである。

サイドチャネル攻撃を防ぐためには、統計的な解析を行っても、秘密鍵Ｄに関する手掛かりが得られないようにするのが最も効果的である。そのためには、冗長ｋ進表現によって再符号化したデータを構成するｎ桁の数値が、完全にランダムに選択された数値になるようにするのが好ましい。別言すれば、ｎ桁の数値のそれぞれについて、０〜ｄmaxの間の数値の出現頻度が一様になるようにするのが理想的である。上述した実施例２の方法は、変遷プロセスの出発点となる初期データとして、通常のｋ進データを用いているため、０〜ｄmaxの間の数値の出現頻度に偏りが生じやすい。

これに対して、ここで述べる実施例３の方法によれば、０〜ｄmaxの間の数値の出現頻度を一様にできるメリットが得られる。この点において、ここで述べる実施例３の方法は、本願発明者が最も好ましい実施例と考えている方法である。但し、この方法は、任意の整数ｍについて、ｋ＝２^ｍ、ｄmax＝２^２ｍ−１という条件下での再符号化が前提となるので、冗長２^ｍ進数において、各桁の数値が０〜２^２ｍ−１の範囲の値をとる、という前提条件が必要になる。たとえば、ｍ＝１に設定した場合、各桁の数値が０〜３の範囲の値をとる冗長２進数による再符号化を前提としたものになり、ｍ＝２に設定した場合、各桁の数値が０〜１５の範囲の値をとる冗長４進数による再符号化を前提としたものになる。

図２３において、数値Ｄ保持要素１４４Ｃは、秘密鍵格納部１５０から読み出した数値Ｄを、ｍ×ｎビット（ｍ，ｎは整数）の２進数として保持する構成要素であり、数値Ｅ生成要素１４５Ｃは、乱数発生部１６０が発生した乱数Ｒを用いて、「Ｅ＜Ｄ」を満足する任意の数値Ｅをｍ×ｎビットの２進数として生成する構成要素である。また、数値Ａ生成要素１４３Ｃは、数値Ｅの下位ｍビット（最下位側のｍビット）を０に置換することにより、新たな数値Ａを生成する構成要素であり、数値Ｂ生成要素１４２Ｃは、Ｂ＝Ｄ−Ａなる演算により、ｍ×ｎビットの２進数からなる数値Ｂを生成する構成要素である。

一方、冗長データ生成要素１４１Ｃは、数値Ａを構成するビットの下位側から数えて第（ｍ×（ｉ＋１））ビット目から下位に向かって連続するｍビット分の数値を上位ビット、数値Ｂを構成するビットの下位側から数えて第（ｍ×ｉ）ビット目から下位に向かって連続するｍビット分の数値を下位ビット、とする２ｍビットからなる数値（但し、ｉ＝１〜ｎとし、数値Ａについては、上位側にｍビット分の０を補う）を、下位側から数えて第ｉ番目の桁とするｎ桁のデータを生成し、これを冗長な２^ｍ進数で表現した数値Ｄを示すデータとして出力する構成要素である。

図２４は、図２３に示す再符号化部１４０Ｃの動作を説明する流れ図である。ステップＳ４１は、数値Ｄ保持要素１４４Ｃが行う処理を示しており、数値Ｄが、ｍ×ｎビット（ｍ，ｎは整数）の２進数として用意される。ステップＳ４２は、数値Ｅ生成要素１４５Ｃが行う処理を示しており、乱数Ｒを用いて、「Ｅ＜Ｄ」を満足する任意の数値Ｅが、ｍ×ｎビットの２進数として生成される。なお、ここに示す数値Ｅと、図１，図２に示す鍵Ｅとは、たまたま同じ符号を用いているが、両者は全く無関係な値である。ステップＳ４３は、数値Ａ生成要素１４３Ｃが行う処理を示しており、数値Ｅの下位ｍビット（最下位側のｍビット）を０に置換することにより、新たな数値Ａが生成される。ステップＳ４４は、数値Ｂ生成要素１４２Ｃが行う処理を示しており、Ｂ＝Ｄ−Ａなる演算により、ｍ×ｎビットの２進数からなる数値Ｂが生成される。

更に、ステップＳ４５は、冗長データ生成要素１４１Ｃが行う処理を示しており、数値Ａ，Ｂの各ビットを組み合わせることにより、ｎ桁の冗長２^ｍ進数からなるデータが生成される。具体的には、上述したとおり、数値Ａを構成するビットの下位側から数えて第（ｍ×（ｉ＋１））ビット目から下位に向かって連続するｍビット分の数値を上位ビット、数値Ｂを構成するビットの下位側から数えて第（ｍ×ｉ）ビット目から下位に向かって連続するｍビット分の数値を下位ビット、とする２ｍビットからなる数値（但し、ｉ＝１〜ｎとし、数値Ａについては、上位側にｍビット分の０を補う）を、下位側から数えて第ｉ番目の桁とするｎ桁のデータが生成される。

以上、一般論として、図２３に示す再符号化部１４０Ｃの動作を説明したが、続いて、具体的な数値Ｄを例示して、この動作を詳細に説明する。

図２５は、図２４の流れ図に基づく２進データの再符号化処理の一例を示す変遷図である。ここでは、ｍ＝１，ｎ＝４に設定した例が示されている。ｍ＝１の例であるため、ｋ＝２、ｄmax＝３という設定が前提となる（すなわち、各桁が０〜３の値をとる冗長２進表記による再符号化が前提となる）。

まず、ステップＳ４１では、数値Ｄが、ｍ×ｎビットの２進数として用意される。ここでは、Ｄ＝１１［１０進］なる数値が、「１０１１」という４ビットの通常２進数で用意されている場合を考える。続くステップＳ４２では、乱数Ｒを用いて、「Ｅ＜Ｄ」を満足するｍ×ｎビットの２進数として、数値Ｅが生成される。ここでは、図示のとおり、「０１１１」なる通常２進数で表現された数値Ｅが生成されたものとしよう。次のステップＳ４３では、数値Ｅの下位ｍビットを０に置換することにより、新たな数値Ａが生成される。この例では、ｍ＝１であるから、数値Ｅ「０１１１」の下位１ビットを０に置換することにより、数値Ａ「０１１０」が生成されることになる。そして、ステップＳ４４では、Ｂ＝Ｄ−Ａなる演算により、ｍ×ｎビットの２進数からなる数値Ｂが生成される。この例では、Ｂ＝Ｄ−Ａなる演算により、４ビットの２進数からなる数値Ｂ「０１０１」が生成されることになる。

かくして、２つの数値Ａ「０１１０」，数値Ｂ「０１０１」が生成されたが、これら２つの数値Ａ，Ｂは、元の数値Ｄを２つに分割した値になっている。別言すれば、Ａ＋Ｂ＝Ｄである。また、数値Ａの下位ｍビット（１ビット）が０である点も留意すべきである。

図２５の下段には、このような具体的な数値Ａ「０１１０」，数値Ｂ「０１０１」を用いた場合のステップＳ４５の処理が模式的に示されている。ステップＳ４５の処理は、前述したとおり、数値Ａを構成するビットの下位側から数えて第（ｍ×（ｉ＋１））ビット目から下位に向かって連続するｍビット分の数値を上位ビット、数値Ｂを構成するビットの下位側から数えて第（ｍ×ｉ）ビット目から下位に向かって連続するｍビット分の数値を下位ビット、とする２ｍビットからなる数値（但し、ｉ＝１〜ｎとし、数値Ａについては、上位側にｍビット分の０を補う）を、下位側から数えて第ｉ番目の桁とするｎ桁のデータを生成する、というものである。

この処理を、ｍ＝１，ｉ＝１という具体的な事例に適用すれば、数値Ａを構成するビットの下位側から数えて第２ビット目から下位に向かって連続する１ビット分の数値を上位ビット、数値Ｂを構成するビットの下位側から数えて第１ビット目から下位に向かって連続する１ビット分の数値を下位ビット、とする２ビットからなる数値を、下位側から数えて第１番目の桁とする、ことになる。図示のとおり、この場合、上位ビットは「１」、下位ビットは「１」となるので、「１１」なる２ビットからなる数値「３」が、下位側から数えて第１番目の桁の数値になる。

同様に、ｍ＝１，ｉ＝２という具体的な事例に適用すれば、数値Ａを構成するビットの下位側から数えて第３ビット目から下位に向かって連続する１ビット分の数値を上位ビット、数値Ｂを構成するビットの下位側から数えて第２ビット目から下位に向かって連続する１ビット分の数値を下位ビット、とする２ビットからなる数値を、下位側から数えて第２番目の桁とする、ことになる。図示のとおり、この場合、上位ビットは「１」、下位ビットは「０」となるので、「１０」なる２ビットからなる数値「２」が、下位側から数えて第２番目の桁の数値になる。

更に、ｍ＝１，ｉ＝３という具体的な事例に適用すれば、数値Ａを構成するビットの下位側から数えて第４ビット目から下位に向かって連続する１ビット分の数値を上位ビット、数値Ｂを構成するビットの下位側から数えて第３ビット目から下位に向かって連続する１ビット分の数値を下位ビット、とする２ビットからなる数値を、下位側から数えて第３番目の桁とする、ことになる。図示のとおり、この場合、上位ビットは「０」、下位ビットは「１」となるので、「０１」なる２ビットからなる数値「１」が、下位側から数えて第３番目の桁の数値になる。

最後に、ｍ＝１，ｉ＝４という具体的な事例に適用すれば、数値Ａを構成するビットの下位側から数えて第５ビット目（数値Ａについては、上位側に１ビット分の０を補う）から下位に向かって連続する１ビット分の数値を上位ビット、数値Ｂを構成するビットの下位側から数えて第４ビット目から下位に向かって連続する１ビット分の数値を下位ビット、とする２ビットからなる数値を、下位側から数えて第４番目の桁とする、ことになる。図示のとおり、この場合、上位ビットは補われた「０」、下位ビットは「０」となるので、「００」なる２ビットからなる数値「０」が、下位側から数えて第４番目の桁の数値になる。

かくして、ステップＳ４５の処理では、「０１２３」という冗長２進データが生成されることになる。このデータの値は、Ｄ＝１１［１０進］に一致する。これは、図２５の下段に示されているとおり、「０１２３」という冗長２進データが、数値Ａと数値Ｂとの加算（ビットをずらした合成加算）によって得られたデータであることを考えれば当然のことである。なお、数値Ａの一番右のビットは加算には利用されないが、もともと数値Ａの下位１ビットは０になるように設定されているので、このビットは加算対象にならなくても問題はない（ステップＳ４３で、下位ｍビットを０に置換するのは、このためである）。

図２６は、図２４の流れ図に基づく２進データの再符号化処理の別な一例を示す変遷図である。ここでも、ｍ＝１，ｎ＝４に設定した例が示されており、ｋ＝２、ｄmax＝３という設定が前提となる。

この例では、Ｄ＝５［１０進］なる数値が、「０１０１」という４ビットの通常２進数で用意され、「００１０」なる通常２進数で表現された数値Ｅが生成された場合が例示されている。この場合、数値Ｅの下位１ビットを０に置換することにより、数値Ａ「００１０」が生成されることになる。もっとも、数値Ｅの下位１ビットは、もともと０であったため、実際には、数値Ａは数値Ｅと変わりない。一方、Ｂ＝Ｄ−Ａなる演算により、数値Ｂ「００１１」が生成されることになる。かくして、２つの数値Ａ「００１０」，数値Ｂ「００１１」が生成されたが、Ａ＋Ｂ＝Ｄになっている。

図２６の下段には、このような具体的な数値Ａ「００１０」，数値Ｂ「００１１」を用いた場合のステップＳ４５の処理が模式的に示されている。最終的に、「００１３」という冗長２進データが生成されることになる。このデータの値は、もとの数値Ｄ＝５［１０進］に一致する。

図２７は、図２４の流れ図に基づく４進データの再符号化処理の一例を示す変遷図である。ここでは、ｍ＝２，ｎ＝３に設定した例が示されている。ｍ＝２の例であるため、ｋ＝４、ｄmax＝１５という設定が前提となる（すなわち、各桁が０〜１５の値をとる冗長４進表記による再符号化が前提となる）。

まず、ステップＳ４１では、数値Ｄが、ｍ×ｎビットの２進数として用意される。ここでは、Ｄ＝５３［１０進］なる数値が、「１１０１０１」という６ビットの通常２進数で用意されている場合を考える。続くステップＳ４２では、乱数Ｒを用いて、「Ｅ＜Ｄ」を満足するｍ×ｎビットの２進数として、数値Ｅが生成される。ここでは、図示のとおり、「０１１０１０」なる通常２進数で表現された数値Ｅが生成されたものとしよう。次のステップＳ４３では、数値Ｅの下位ｍビットを０に置換することにより、新たな数値Ａが生成される。この例では、ｍ＝２であるから、数値Ｅ「０１１０１０」の下位２ビットを０に置換することにより、数値Ａ「０１１０００」が生成されることになる。そして、ステップＳ４４では、Ｂ＝Ｄ−Ａなる演算により、ｍ×ｎビットの２進数からなる数値Ｂが生成される。この例では、Ｂ＝Ｄ−Ａなる演算により、６ビットの２進数からなる数値Ｂ「０１１１０１」が生成されることになる。

かくして、２つの数値Ａ「０１１０００」，数値Ｂ「０１１１０１」が生成される。ここでも、やはりＡ＋Ｂ＝Ｄである。また、数値Ａの下位ｍビット（２ビット）が０である点も留意すべきである。

図２７の下段には、このような具体的な数値Ａ「０１１０００」，数値Ｂ「０１１１０１」を用いた場合のステップＳ４５の処理が模式的に示されている。ステップＳ４５の処理は、前述したとおり、数値Ａを構成するビットの下位側から数えて第（ｍ×（ｉ＋１））ビット目から下位に向かって連続するｍビット分の数値を上位ビット、数値Ｂを構成するビットの下位側から数えて第（ｍ×ｉ）ビット目から下位に向かって連続するｍビット分の数値を下位ビット、とする２ｍビットからなる数値（但し、ｉ＝１〜ｎとし、数値Ａについては、上位側にｍビット分の０を補う）を、下位側から数えて第ｉ番目の桁とするｎ桁のデータを生成する、というものである。

この処理を、ｍ＝２，ｉ＝１という具体的な事例に適用すれば、数値Ａを構成するビットの下位側から数えて第４ビット目から下位に向かって連続する２ビット分の数値を上位ビット、数値Ｂを構成するビットの下位側から数えて第２ビット目から下位に向かって連続する２ビット分の数値を下位ビット、とする４ビットからなる数値を、下位側から数えて第１番目の桁とする、ことになる。図示のとおり、この場合、上位ビットは「１０」、下位ビットは「０１」となるので、「１００１」なる４ビットからなる数値「９」が、下位側から数えて第１番目の桁の数値になる。

同様に、ｍ＝１，ｉ＝２という具体的な事例に適用すれば、数値Ａを構成するビットの下位側から数えて第６ビット目から下位に向かって連続する２ビット分の数値を上位ビット、数値Ｂを構成するビットの下位側から数えて第４ビット目から下位に向かって連続する２ビット分の数値を下位ビット、とする４ビットからなる数値を、下位側から数えて第２番目の桁とする、ことになる。図示のとおり、この場合、上位ビットは「０１」、下位ビットは「１１」となるので、「０１１１」なる４ビットからなる数値「７」が、下位側から数えて第２番目の桁の数値になる。

最後に、ｍ＝１，ｉ＝３という具体的な事例に適用すれば、数値Ａを構成するビットの下位側から数えて第８ビット目（数値Ａについては、上位側に２ビット分の０を補う）から下位に向かって連続する２ビット分の数値を上位ビット、数値Ｂを構成するビットの下位側から数えて第６ビット目から下位に向かって連続する２ビット分の数値を下位ビット、とする４ビットからなる数値を、下位側から数えて第３番目の桁とする、ことになる。図示のとおり、この場合、上位ビットは補われた「００」、下位ビットは「０１」となるので、「０００１」なる４ビットからなる数値「１」が、下位側から数えて第３番目の桁の数値になる。

かくして、ステップＳ４５の処理では、「１７９」という冗長４進データが生成されることになる。このデータの値は、Ｄ＝５３［１０進］に一致する。これは、図２７の下段に示されているとおり、「１７９」という冗長４進データが、数値Ａと数値Ｂとの加算（ビットをずらした合成加算）によって得られたデータであることを考えれば当然のことである。なお、数値Ａの下位２ビットは加算には利用されないが、もともと数値Ａの下位２ビットは０になるように設定されているので、このビットは加算対象にならなくても問題はない（ステップＳ４３で、下位ｍビットを０に置換するのは、このためである）。

＜その他の実施例＞
以上、図１６に示す再符号化部１４０の具体的な構成例をいくつか例示したが、本発明に用いる再符号化部１４０の構成は、これらの実施例に限定されるものではなく、この他にも様々な構成例を利用することが可能である。

また、これまで述べた構成例は、その都度、新たな再符号化処理を実行する例であったが、冗長ｋ進法で秘密鍵Ｄを表記する複数通りのバリエーションを事前にリストとして保管しておき、乱数を用いて、このリストの中からランダムに１つを選択して用いるようなことも可能である。たとえば、冗長２進法でＤ＝２２［１０進］を表現する形態は、図１１に一例が示されているとおり、「１０１１０」，「１００２２」，「０１２２２」，「０２０３０」，... など、いくつかのバリエーションが存在するので、秘密鍵Ｄとして、Ｄ＝２２［１０進］なる値を格納している暗号処理装置の場合、上記バリエーションに対応するデータをリストとして格納しておき、再符号化部１４０では、乱数Ｒに基づいて、リスト上のいずれか１つのデータをランダムに選択して演算実行部１３０に引き渡す処理を行えばよい。

ただ、サイドチャネル攻撃の１つとして、暗号処理装置の内部で行われているアドレッシング処理を統計的に解析する手法が知られている。すなわち、ＣＰＵがメモリをアクセスする際に、アドレス値が異なると消費電力も異なる現象を利用し、消費電力を統計的に解析することによって、アクセスしたアドレスを推定することが可能になる。したがって、上述したように、冗長ｋ進法で秘密鍵Ｄを表記する複数通りのバリエーションを事前にリストとして保管しておき、このリストの中からランダムに１つを選択して用いる方法をとると、リスト上のどのデータが用いられたかという情報が、消費電力の統計的解析によって推定されてしまう可能性がある。このようなサイドチャネル攻撃にも対抗するためには、これまで述べた実施例のように、その都度、新たな再符号化処理を実行するのが好ましい。

＜＜＜ §５．様々な変形例 ＞＞＞
以上、本発明をいくつかの具体的な実施例に基づいて説明したが、もちろん、本発明はこれらの実施例に限定されるものではない。たとえば、§１，§２で説明したべき乗剰余演算の方法は、一般に「Left to Right Exponentiation」と呼ばれている演算方法（指数を左から右へと順々に処理してゆく演算方法）であるが、この方法の代りに、指数を右から左へと順々に処理してゆく「Right to Left Exponentiation」と呼ばれる演算方法を採ることも可能である。更に、これまで述べた実施例では、ＭのＤ乗の項を含むべき乗剰余演算式に本発明を適用した例を述べたが、もちろん、本発明に係る暗号処理装置は、実施例で述べた具体的な演算式への適用に限定されるものではなく、数値Ｍおよび数値Ｄが含まれるいかなる演算式にも適用可能である。

たとえば、本発明は、楕円曲線暗号の演算にも適応可能である。楕円曲線暗号は、次世代公開鍵暗号として最近注目を浴びている暗号であり、「楕円曲線」という２変数の３次方程式を満たす数字（ｘ，ｙ）（「有理点」と呼ぶ）の集合を扱う演算式で実現できる多種多様な暗号すべてのことを指す（ただし、この式の数字ｘ，ｙの部分には、実数ではなく、ガロアー体ＧＦ（ｐ）という離散的な数字が入る）。有理点を扱うこの演算式では、二つの有理点を入力とし一つの別の有理点を出力する「点加算」が定義され、また、一つの有理点を複数回点加算する「有理点のスカラー倍算」という処理が含まれる。

有理点のスカラー倍算は、全ての楕円曲線暗号に使われている基本的な処理であり、楕円曲線暗号では、スカラー倍算を実施する際、有理点を何個加算するか決定するスカラー数が秘密情報となる。この観点では、スカラー数は、ＲＳＡ暗号などべき乗剰余を行う際の指数に相当する秘密情報である。

本発明は、上述した楕円曲線暗号の演算における秘密情報であるスカラー数を、電力解析から守るのにも有効である。この楕円曲線暗号の演算におけるスカラー倍算の処理は、前述したべき乗剰余を求める演算処理と極めて類似しており、その根本的な考え方は共通する。すなわち、本発明を楕円曲線暗号に適応する場合は、まず、数値Ｍに基づいて定まる入力点（有理点）をＰとし、スカラー数をＤとし、前述した再符号化方法をスカラー数Ｄに適用し、スカラー倍算演算の入力として利用すればよい。

一般に、有理点Ｐをスカラー値［Ｄ］でスカラー倍する演算は、
［Ｄ］＊Ｐ＝Ｐ＋Ｐ＋ ... ＋Ｐ（但し、右辺のＰはＤ個）
なる式により、有理点ＰをＤ個複写して点加算することによって行われる。具体的には、スカラー値［Ｄ］を（ｎ＋１）ビットの２進数を用いて、
［Ｄ］＝ｄ［ｎ］＊２^ｎ＋ｄ［ｎ−１］＊２^{（ｎ−１）}＋ ...
＋ｄ［１］＊２＋ｄ［０］
なる形で表現し（ｉビット目の数値ｄ［ｉ］は、０もしくは１）、ｄ［ｎ］＝１とし、前述したＲＳＡと類似した方法を採用すれば、
［Ｄ］＊Ｐ＝［２］＊（［２］ ... ＊（［２］＊（［２］＊（［２］＊Ｐ
＋ｄ［ｎ−１］＊Ｐ）
＋ｄ［ｎ−２］＊Ｐ）
＋ｄ［ｎ−３］＊Ｐ）
＋ ........................
＋ｄ［１］＊Ｐ）
＋ｄ［０］＊Ｐ
なる繰り返し演算によって、有理点ＰをＤ倍するスカラー倍算が実行できる。

そこで、上記繰り返し演算に、本発明を適用するのであれば、スカラー値［Ｄ］を冗長ｋ進数で再符号化する方法を採ればよい。冗長２進数を用いるのであれば、［Ｄ］を示す第ｉ番目のビットをｄ［ｉ］として、たとえば、ｄ［ｉ］∈０，１，２，３となるような再符号化を行えばよい。この場合、［２］＊Ｐ，［３］＊Ｐ等の値を予め演算によって求めておき、保存しておくようにすれば、実際の演算時には、これらの保存値を利用することができる。

なお、有理点Ｐの２倍を求める処理や、異なる二つの有理点を加算する処理には様々な演算方法が知られている。たとえば、第１の有理点ＰをＰ＝（ｘ_１，ｙ_１）とし、第２の有理点ＱをＱ＝（ｘ_２，ｙ_２）とし、両者の和を（ｘ_３，ｙ_３）とすれば、次のような演算により、和「Ｐ＋Ｑ」＝（ｘ_３，ｙ_３）が得られることが知られている。
ｘ_３＝λ^２−ｘ_１−ｘ_２
ｙ_３＝λ（ｘ_１−ｘ_３）−ｙ_１
λ＝（ｙ_２−ｙ_１）／（ｘ_２−ｘ_１） （Ｐ≠Ｑのとき）
λ＝（３ｘ_１ ^２＋ａ）／（２ｙ_１） （Ｐ＝Ｑのとき）
ｘｉ，ｙｉ，ａ∈ＧＦ（ｐ） （但し、ｉ＝１，２，or ３）
Char（ＧＦ（ｐ））≠２，３
このような楕円曲線暗号の具体的な演算方法としては、この他にも種々の方法が知られているが、ここでは詳しい説明は省略する。

楕円曲線暗号に本発明を適用する上で重要な点は、スカラー値［Ｄ］を冗長ｋ進数で再符号化した後、再符号化された［Ｄ］を構成する各ビットｄ［ｉ］についての演算を繰り返し実行してゆく点にある。したがって、具体的な演算式は、上例に限定されるものではない。

もちろん、本発明は、いわゆる暗号化や復号化の処理への利用に限定されるものではなく、たとえば、DSA(Digital Signature Algorithm）などにも利用することが可能である。

本発明では、乱数Ｒを用いて数値Ｄを冗長なｋ進数で表現することが非常に重要な概念になる。ここで、冗長なｋ進数とは、１つの桁の数値ｄが「０≦ｄ≦ｄmax（但し、ｄmax＞ｋ−１）」の範囲内の値をとる数であるが、数値ｄの候補は、必ずしも０〜ｄmaxの範囲内の全整数である必要はなく、当該範囲内の一部の整数のみに制限してもかまわない。たとえば、冗長４進数において、ｄmax＝１９に設定した場合、１つの桁の数値ｄは、０〜１９の範囲内の値をとる整数になり、この範囲内の全整数を候補として用いるのであれば、数値ｄは、０〜１９の２０通りの整数のうちのいずれかになる。このとき、たとえば、「４〜１５は使用しない」というような取り決めをしておくことも可能であり、その場合は、数値ｄが、０，１，２，３，１６，１７，１８，１９という８通りの整数のうちのいずれかになるような再符号化が行われることになる。具体的には、１０進数の「１８１」を上記８通りの整数を用いた冗長４進数で表現すれば、「１／２／１７／１７」なる４桁の数値になる。このように、本発明にいう「冗長なｋ進数」とは、１つの桁の数値ｄが「０≦ｄ≦ｄmax（但し、ｄmax＞ｋ−１）」の範囲内の値をとる数である必要があるが、数値ｄの候補は、必ずしも０〜ｄmaxの範囲内の全整数である必要はなく、当該範囲内の一部の整数であってもかまわない。

一般的な公開鍵暗号方式を用いた暗号化および復号化のプロセスを示すブロック図である。 一般的なＲＳＡ暗号方式で利用されているべき乗剰余演算式を示す図である。 ＩＣカード１０と外部装置２０との間の認証にＲＳＡ暗号方式を利用した一般的なシステムを示すブロック図である。 ２進数の秘密鍵Ｄを用いたべき乗剰余演算を暗号処理装置の内部で実行する際の実際の演算式の一例を示す図である。 図４に示す演算式おいて、２２［１０進］なる秘密鍵Ｄを２進表記にして適用した場合の具体的な演算手順を示す図である。 ４進数の秘密鍵Ｄを用いたべき乗剰余演算を暗号処理装置の内部で実行する際の実際の演算式の一例を示す図である。 図６に示す演算式おいて、２２［１０進］なる秘密鍵Ｄを４進表記にして適用した場合の具体的な演算手順を示す図である。 ｋ進数の秘密鍵Ｄを用いたべき乗剰余演算を暗号処理装置の内部で実行する際の実際の演算式の一例を示す図である。 数値Ｄをｋ進表現した場合の各桁の構成を示す図である。 通常２進表現と冗長２進表現との相違を示す図である。 数値Ｄ＝２２［１０進］を、通常２進表現および冗長２進表現で表した例を示す図である。 通常４進表現と冗長４進表現との相違を示す図である。 数値Ｄ＝２２［１０進］を、通常４進表現および冗長４進表現で表した例を示す図である。 図４に示す演算式おいて、２２［１０進］なる秘密鍵Ｄを冗長２進表記にして適用した場合の具体的な演算手順を示す図である。 図６に示す演算式おいて、２２［１０進］なる秘密鍵Ｄを冗長４進表記にして適用した場合の具体的な演算手順を示す図である。 本発明に係る暗号処理装置の構成を示すブロック図である。 図１６に示す暗号処理装置の再符号化部１４０の第１の構成例を示すブロック図である。 図１７に示す再符号化部１４０Ａの動作を説明する流れ図である。 図１６に示す暗号処理装置の再符号化部１４０の第２の構成例を示すブロック図である。 図１９に示す再符号化部１４０Ｂの動作を説明する流れ図である。 図２０の流れ図に基づく２進データの再符号化処理の一例を示す変遷図である。 図２０の流れ図に基づく４進データの再符号化処理の一例を示す変遷図である。 図１６に示す暗号処理装置の再符号化部１４０の第３の構成例を示すブロック図である。 図２３に示す再符号化部１４０Ｃの動作を説明する流れ図である。 図２４の流れ図に基づく２進データの再符号化処理の一例を示す変遷図である。 図２４の流れ図に基づく２進データの再符号化処理の別な一例を示す変遷図である。 図２４の流れ図に基づく４進データの再符号化処理の一例を示す変遷図である。

符号の説明

１０：ＩＣカード
１１：制御ユニット
１２：暗号処理装置
２０：外部装置
２１：認証処理部
２２：暗号処理装置
１００：暗号処理装置
１１０：入力部
１２０：出力部
１３０：演算実行部
１４０：再符号化部
１４０Ａ：再符号化部
１４１Ａ：制御要素
１４２Ａ：数値確認要素
１４３Ａ：ランダムデータ生成要素
１４０Ｂ：再符号化部
１４１Ｂ：制御要素
１４２Ｂ：レジスタ
１４３Ｂ：初期データ設定要素
１４４Ｂ：増加補正実行要素
１４５Ｂ：減少補正実行要素
１４６Ｂ：桁選択要素
１４７Ｂ：増減決定要素
１４０Ｃ：再符号化部
１４１Ｃ：冗長データ生成要素
１４２Ｃ：数値Ｂ生成要素
１４３Ｃ：数値Ａ生成要素
１４４Ｃ：数値Ｄ保持要素
１４５Ｃ：数値Ｅ生成要素
１５０：秘密鍵格納部
１６０：乱数発生部
Ａ：再符号化に用いる数値
Ｂ：再符号化に用いる数値
Ｃ：第２の数値（暗号文）
Ｄ：秘密鍵
ｄ：秘密鍵の各桁
ｄmax：ｄの最大値
Ｅ：公開鍵
Ｍ：第１の数値（平文）
Ｒ：乱数
Ｓ１１〜Ｓ４５：流れ図の各ステップ
Ｚ：定数

Claims (11)

1. 外部から与えられた第１の数値Ｍに対して、秘密鍵となる数値Ｄを用いた演算を行うことにより第２の数値Ｃを生成し、これを外部へ出力する処理を行う暗号処理装置であって、
   第１の数値Ｍを外部から入力する入力部と、
   秘密鍵となる数値Ｄを格納する秘密鍵格納部と、
   乱数Ｒを発生させる乱数発生部と、
   発生させた乱数Ｒを用いて、前記数値Ｄを、１つの桁の数値ｄが「０≦ｄ≦ｄmax（但し、ｄmax＞ｋ−１）」の範囲内の値をとる冗長なｋ進数で表現したランダムなｎ桁のデータに再符号化する再符号化部と、
   少なくとも前記数値Ｍと再符号化された数値Ｄとを用いた所定の演算を行うことにより、第２の数値Ｃを求める演算実行部と、
   前記演算実行部が求めた第２の数値Ｃを外部へ出力する出力部と、
   を備え、
   前記再符号化部が、
   乱数Ｒを用いて「０≦ｄ≦ｄmax」の範囲内の値を発生させる処理をｎ回繰り返すことによりｎ桁のランダムデータを生成するランダムデータ生成要素と、
   生成されたランダムデータが前記数値Ｄに等しいか否かを判断する数値確認要素と、
   前記数値確認要素が等しいとの判断を行うまで、前記ランダムデータ生成要素にランダムデータの生成を繰り返し実行させ、前記数値確認要素が等しいとの判断を行った際のランダムデータを再符号化したデータとして出力する制御要素と、
   を有することを特徴とする暗号処理装置。
2. 外部から与えられた第１の数値Ｍに対して、秘密鍵となる数値Ｄを用いた演算を行うことにより第２の数値Ｃを生成し、これを外部へ出力する処理を行う暗号処理装置であって、
   第１の数値Ｍを外部から入力する入力部と、
   秘密鍵となる数値Ｄを格納する秘密鍵格納部と、
   乱数Ｒを発生させる乱数発生部と、
   発生させた乱数Ｒを用いて、前記数値Ｄを、１つの桁の数値ｄが「０≦ｄ≦ｄmax（但し、ｄmax＞ｋ−１）」の範囲内の値をとる冗長なｋ進数で表現したランダムなｎ桁のデータに再符号化する再符号化部と、
   少なくとも前記数値Ｍと再符号化された数値Ｄとを用いた所定の演算を行うことにより、第２の数値Ｃを求める演算実行部と、
   前記演算実行部が求めた第２の数値Ｃを外部へ出力する出力部と、
   を備え、
   前記再符号化部が、
   ｎ桁のデータを保持するレジスタと、
   前記数値Ｄを、１つの桁の数値ｄが「０≦ｄ≦ｋ−１」の範囲内の値をとる通常のｋ進数で表現することにより、ｎ桁からなるデータを用意し、用意したデータを初期データとして前記レジスタに設定する初期データ設定要素と、
   発生させた乱数Ｒを用いて、前記レジスタのｎ桁のうちの任意の１桁を選択桁として選択する桁選択要素と、
   発生させた乱数Ｒを用いて、増加補正もしくは減少補正のいずれかを決定する増減決定要素と、
   前記増減決定要素により増加補正が決定された場合には、前記選択桁の数値ｄについてｄ＜ｄmaxが満たされ、かつ、他の桁の調整によって所定の増加補正分δ（但し、δ≦ｄmax−ｄ）を相殺することが可能であることを条件として、前記選択桁に前記増加補正分δを加え、他の桁を調整して前記増加補正分δを相殺する補正を行う増加補正実行要素と、
   前記増減決定要素により減少補正が決定された場合には、前記選択桁の数値ｄについてｄ≠０が満たされ、かつ、他の桁の調整によって所定の減少補正分δ（但し、δ≦ｄ）を相殺することが可能であることを条件として、前記選択桁から前記減少補正分δを減じ、他の桁を調整して前記減少補正分δを相殺する補正を行う減少補正実行要素と、
   所定の条件が満たされるまで、桁選択要素による桁選択、増減決定要素による増減決定、増加補正実行要素もしくは減少補正実行要素による補正を繰り返し実行し、前記所定の条件が満たされたときの前記レジスタ内のｎ桁のデータを再符号化したデータとして出力する制御要素と、
   を有することを特徴とする暗号処理装置。
3. 外部から与えられた第１の数値Ｍに対して、秘密鍵となる数値Ｄを用いた演算を行うことにより第２の数値Ｃを生成し、これを外部へ出力する処理を行う暗号処理装置であって、
   第１の数値Ｍを外部から入力する入力部と、
   秘密鍵となる数値Ｄを格納する秘密鍵格納部と、
   乱数Ｒを発生させる乱数発生部と、
   発生させた乱数Ｒを用いて、前記数値Ｄを、１つの桁の数値ｄが「０≦ｄ≦ｄmax（但し、ｄmax＞ｋ−１）」の範囲内の値をとる冗長なｋ進数で表現したランダムなｎ桁のデータに再符号化する再符号化部と、
   少なくとも前記数値Ｍと再符号化された数値Ｄとを用いた所定の演算を行うことにより、第２の数値Ｃを求める演算実行部と、
   前記演算実行部が求めた第２の数値Ｃを外部へ出力する出力部と、
   を備え、
   前記再符号化部が、
   前記数値Ｄをｍ×ｎビット（ｍ，ｎは整数）の２進数として保持する数値Ｄ保持要素と、
   乱数Ｒを用いて、「Ｅ＜Ｄ」を満足する任意の数値Ｅをｍ×ｎビットの２進数として生成する数値Ｅ生成要素と、
   前記数値Ｅの下位ｍビットを０に置換することにより、新たな数値Ａを生成する数値Ａ生成要素と、
   Ｂ＝Ｄ−Ａなる演算により、ｍ×ｎビットの２進数からなる数値Ｂを生成する数値Ｂ生成要素と、
   数値Ａを構成するビットの下位側から数えて第（ｍ×（ｉ＋１））ビット目から下位に向かって連続するｍビット分の数値を上位ビット、数値Ｂを構成するビットの下位側から数えて第（ｍ×ｉ）ビット目から下位に向かって連続するｍビット分の数値を下位ビット、とする２ｍビットからなる数値（但し、ｉ＝１〜ｎとし、数値Ａについては、上位側にｍビット分の０を補う）を、下位側から数えて第ｉ番目の桁とするｎ桁のデータを生成し、これを冗長な２ ^ｍ 進数で表現した数値Ｄを示すデータとして出力する冗長データ生成要素と、
   を有することを特徴とする暗号処理装置。
4. 請求項１〜３のいずれかに記載の暗号処理装置において、
   演算実行部が、Ｍ^Ｄの項を含む所定の演算式もしくはＭに基づいて定まる有理点Ｐをスカラー値Ｄでスカラー倍する楕円曲線暗号の演算式に基づく演算を行うことにより、第２の数値Ｃを求めることを特徴とする暗号処理装置。
5. 請求項４に記載の暗号処理装置において、
   演算実行部が、Ｍ^Ｄを所定の数値Ｚで除したときのべき乗剰余を示す演算式Ｃ＝Ｍ^Ｄ modＺに基づく演算を行うことにより、第２の数値Ｃを求めることを特徴とする暗号処理装置。
6. 請求項５に記載の暗号処理装置において、
   再符号化部が、数値Ｄを、上位桁側から順に、ｄ［ｎ−１］，ｄ［ｎ−２］，ｄ［ｎ−３］，... ，ｄ［２］，ｄ［１］，ｄ［０］なるｎ桁のデータに再符号化する処理を行い、
   演算実行部が、演算式Ｃ＝Ｍ^ＤmodＺに基づく演算を、
   Ｃ＝（（ .....（（（１＊Ｍ^{ｄ［ｎ−１］}）^ｋ
   ＊Ｍ^{ｄ［ｎ−２］}modＺ）^ｋ
   ＊Ｍ^{ｄ［ｎ−３］}modＺ）^ｋ
   .....
   ＊Ｍ^ｄ［２］modＺ）^ｋ
   ＊Ｍ^ｄ［１］modＺ）^ｋ
   ＊Ｍ^ｄ［０］modＺ
   なる等価演算式を用いて、括弧の内側の演算から順番に実行することを特徴とする暗号処理装置。
7. 請求項１〜３のいずれかに記載の暗号処理装置において、
   演算実行部が、ＲＳＡ暗号、Diffie Hellman暗号、EL Gamal暗号、もしくは楕円曲線暗号を生成するための演算を行うことにより、第２の数値Ｃを求めることを特徴とする暗号処理装置。
8. 請求項１〜７のいずれかに記載の暗号処理装置において、
   演算実行部が、再符号化部によって再符号化されたｎ桁のデータの中から１桁の数値ｄを抽出して用いる演算を、順番に繰り返し実行することにより第２の数値Ｃを求めることを特徴とする暗号処理装置。
9. 請求項１〜８のいずれかに記載の暗号処理装置において、
   入力部が第１の数値Ｍを外部から入力するたびに、乱数発生部が新たな乱数Ｒを発生させ、再符号化部が新たな再符号化を行い、演算実行部が新たに再符号化された数値Ｄを用いて第２の数値Ｃを求める演算を行うことを特徴とする暗号処理装置。
10. 請求項１〜９のいずれかに記載の暗号処理装置を内蔵したＩＣカード。
11. 請求項１〜９のいずれかに記載の暗号処理装置としてコンピュータを機能させるためのプログラム。

Images