"暗号化処理装置であって、共有鍵を記憶するメモリと、整数である乱数を発生する乱数発生器と、前記共有鍵に対して、少なくとも前記乱数によって定まるビット転置を施し、第1のランダム化鍵を生成するビット転置器と、前記乱数を、別の暗号化処理装置に送信し、前記別の暗号化処理装置に記憶されている共有鍵と、前記乱数によって定まるビット転置を施して生成される第2のランダム化鍵を用いた暗号化によって得られるレスポンスを前記別の暗号化処理装置から受信する通信器と、前記レスポンスを前記共有鍵を用いて復号して前記乱数と比較する、または前記乱数を前記共有鍵を用いて暗号化して前記レスポンスと比較することによって前記別の暗号化処理装置を認証する認証器と、を含む暗号化処理装置。前記ビット転置器は、セレクタ回路、線形帰還シフトレジスタ回路、および結線回路の少なくとも一つを含む、請求項1の暗号化処理装置。前記ビット転置器は、前記共有鍵を分割して得られる部分鍵に対して、少なくとも前記乱数によって定まるビット転置を施し、ランダム化部分鍵を生成し、前記ランダム化部分鍵を一つに圧縮して、前記第1のランダム化鍵を生成する、請求項1の暗号化処理装置。前記別の暗号化処理装置の前記ビット転置器は、前記共有鍵を分割して得られる部分鍵に対して、前記ビット転置の入力値として前記乱数によって定まるビット転置を施し、ランダム化部分鍵を生成し、前記ランダム化部分鍵を一つに圧縮して、前記第1のランダム化鍵を生成する、請求項1または2の暗号化処理装置。前記ランダム化部分鍵の圧縮は、XOR回路、セレクタ回路、および加算または減算回路の少なくとも一つを用いて行われる、請求項4の暗号化処理装置。共有鍵を有する第1の暗号化処理装置を含む第1のデバイスによる、前記共有鍵と同一の鍵を有する第2の暗号化処理装置を含む第2のデバイスの認証方法であって、乱数を発生することと、前記共有鍵に対して、少なくとも前記乱数によって定まるビット転置を施し、第1のランダム化鍵を生成することと、前記乱数を、前記第2の暗号化処理装置に送信することと、前記第2の暗号化処理装置から、前記第2の暗号化処理装置に記憶されている前記鍵と前記乱数によって定まるビット転置を施して生成される第2のランダム化鍵を用いた暗号化によって得られるレスポンスを受信することと、前記レスポンスを前記共有鍵を用いて復号して前記乱数と比較する、または前記乱数を前記共有鍵を用いて暗号化して前記レスポンスと比較すること、を含む認証方法。前記第1の暗号化処理装置では、前記共有鍵を分割して得られる部分鍵に対して、少なくとも前記乱数によって定まるビット転置を施し、ランダム化部分鍵を生成し、前記ランダム化部分鍵を一つに圧縮して、前記第1のランダム化鍵を生成する、請求項6の認証方法。前記前記第2の暗号化処理装置では、前記整数の入力値を分割して得られる部分鍵に対して、前記ビット転置の入力値として前記乱数によって定まるビット転置を施し、ランダム化部分鍵を生成し、前記ランダム化部分鍵を一つに圧縮して、前記第1のランダム化鍵を生成する、請求項7または8の認証方法。共有鍵を記憶するメモリと、整数である乱数を発生する乱数発生器と、前記共有鍵に対して、少なくとも前記乱数によって定まるビット転置を施し、前記メモリに記憶された共有鍵の代わりに用いられる第1のランダム化鍵を生成するビット転置器と、を含む共有鍵暗号方式で用いられる鍵生成装置。前記ビット転置器は、セレクタ回路、線形帰還シフトレジスタ回路、および結線回路の少なくとも一つを含む、請求項9の鍵生成装置。前記ビット転置器は、前記共有鍵を分割して得られる部分鍵に対して、少なくとも前記乱数によって定まるビット転置を施し、ランダム化部分鍵を生成し、前記ランダム化部分鍵を一つに圧縮して、前記第1のランダム化鍵を生成する、請求項10または11の鍵生成装置。前記ランダム化部分鍵の圧縮は、XOR回路、セレクタ回路、および加算または減算回路の少なくとも一つを用いて行われる、請求項11の鍵生成装置。しかし、製造後は鍵を外部に取り出さない認証機器を含めた組み込み装置であっても、サイドチャネル攻撃と呼ばれる組み込み機器に対する物理破壊を伴わずに、外部から観察可能な情報を用いて秘密鍵を解読する攻撃に対して脆弱性を有することが知られている。つまり、製造後は鍵を外部に取り出さない機器であっても、秘密鍵が漏洩することが判明している。よって、回路規模を抑えつつ、サイドチャネル攻撃対策を施すことが耐タンパ上の課題の一つとなっている。暗号化処理装置は、共有鍵を記憶するメモリと、整数である乱数を発生する乱数発生器と、前記共有鍵に対して、少なくとも前記乱数によって定まるビット転置を施し、第1のランダム化鍵を生成するビット転置器と、前記乱数を、別の暗号化処理装置に送信し、前記別の暗号化処理装置に記憶されている共有鍵と、前記乱数によって定まるビット転置を施して生成される第2のランダム化鍵を用いた暗号化によって得られるレスポンスを前記別の暗号化処理装置から受信する通信器と、前記レスポンスを前記共有鍵を用いて復号して前記乱数と比較する、または前記乱数を前記共有鍵を用いて暗号化して前記レスポンスと比較することによって前記別の暗号化処理装置を認証する認証器と、を含む暗号化処理装置、を含むことを特徴とする。また、共有鍵を有する第1の暗号化処理装置を含む第1のデバイスによる、前記共有鍵と同一の鍵を有する第2の暗号化処理装置を含む第2のデバイスの認証方法は:乱数を発生すること;前記共有鍵に対して、少なくとも前記乱数によって定まるビット転置を施し、第1のランダム化鍵を生成すること;前記乱数を、前記第2の暗号化処理装置に送信すること;前記第2の暗号化処理装置から、前記第2の暗号化処理装置に記憶されている前記鍵と前記乱数によって定まるビット転置を施して生成される第2のランダム化鍵を用いた暗号化によって得られるレスポンスを受信すること;前記レスポンスを前記共有鍵を用いて復号して前記乱数と比較する、または前記乱数を前記共有鍵を用いて暗号化して前記レスポンスと比較すること、を含むことを特徴とする。秘密鍵をビット転置条件が乱数によって変化する回路を用いてビット転置を行いランダム化鍵を生成し、ランダム化されたランダム化鍵を、秘密鍵の代わりに使用することによって、サイドチャネル攻撃に対する安全性と、小規模高速な暗号処理を両立する暗号化処理装置を得ることができる。以下、図面を参照しながら、共通鍵暗号方式を用いる暗号化処理装置および認証方法を説明する。最初に比較例を説明するが、その後、本発明の第1から第6の実施形態を、比較例に対する利点を含めて説明する。尚、以下の説明において、複数の図面にわたり類似の構成要素または類似の機能を有する構成要素には、類似の参照符号を付して初出時以外、詳細な説明を省略する。認証チップは、複数の電子機器間で通信を行い、通信相手が正規の機器であることを確認するためのシステムにおいて利用される。例えば、プリンタとインクカートリッジ間でカートリッジがメーカの純正品であることを確認するようなシステムにおいては必須となる。認証機能で用いられる暗号方式の代表例としては、公開鍵暗号方式と共通鍵暗号方式が知られている。公開鍵暗号方式とは、暗号化と復号で異なる鍵を用いる方式であり、暗号化を行うための鍵公開鍵を一般に公開する代わりに、暗号文を復号するための鍵秘密鍵を受信者のみの秘密情報とすることで安全性を保つ方式である。これに対し、共通鍵暗号方式と呼ばれるものは、暗号化と復号で同一の鍵秘密鍵を用いる方式であり、この秘密鍵を送信者と受信者以外の第三者にわからない情報とすることで安全性を保つ方式である。いずれの暗号方式を用いた場合でも、秘密鍵が外部に漏洩しないことがセキュリティ上、最も重要な前提である。この前提が守られる限りは、公開鍵暗号、共通鍵暗号のいずれを用いた認証も安全となる。しかし、共通鍵暗号の方が公開鍵暗号より回路規模が小さく、低コスト化には適しているため、特に組み込み機器においては共通鍵暗号を用いた認証が広く普及している。セキュリティ機能を備えた組み込み機器に求められる性質として、耐タンパ性と呼ばれるものがある。耐タンパとは、覗き見防止の意味であり、組み込み機器の外部から観察された情報により、組み込み機器内部に格納された重要情報が漏洩しない性質を指す。耐タンパ性を実現するためには、組み込み機器が備える正規の入出力端子からのアクセスによる情報漏洩防止はもちろんのこと、マイクロプローブを用いて内部回路を直接覗き込む非正規アクセスに対する情報漏洩防止も実現しなければならない。通常のICチップのハードウェア構成では、マイクロプローブを用いて内部回路を直接覗き込む攻撃に耐えることはできない。よって、耐タンパ性を実現するには、外部からの物理的論理的な不正アクセスを防ぐための専用のハードウェア構成をもったICチップとして製造する必要がある。安全な認証を実現するための一般的な方法としては、耐タンパ性をもつ認証機器に対して、機器製造時に認証に用いる秘密鍵を内部に書き込み、製造後は鍵を外部に取り出さない方法が用いられる。こうすることで、不正な第三者が秘密鍵を入手し、認証機器の偽造を防止することができると考えられていた。しかし、製造後は鍵を外部に取り出さない認証機器を含めた組み込み装置であっても、サイドチャネル攻撃と呼ばれる組み込み機器に対する物理破壊を伴わずに、外部から観察可能な情報を用いて秘密鍵を解読する攻撃に対して脆弱性を有することが知られている。つまり、製造後は鍵を外部に取り出さない機器であっても、秘密鍵が漏洩することが判明している。よって、コスト上昇を抑えつつ、サイドチャネル攻撃対策を施すことが耐タンパ上の課題の一つとなった。サイドチャネル攻撃とは、組み込み機器に対する物理破壊を伴わずに、外部から観察可能な情報を用いて秘密鍵を解読する攻撃である。1996年には、処理時間を観察するタイミング攻撃が提案されたが、対策も容易であったため大きな脅威とならなかった。しかし1998年に、1998年に消費電力を観察する電力解析攻撃PowerAnalysisと呼ばれる手法が提案され、大きな脅威として現在でも注目されている。電力解析攻撃とは、組み込み機器に様々な入力データを与えた時の電力消費データを収集解析することで、内部の鍵情報を推定する手法である。特に、組み込み機器がスマートカードチップや認証チップなどの単体のLSIチップである場合、消費電力の測定が容易であるため、PA対策は耐タンパ上の大きな課題である。電力解析攻撃を用いることで、公開鍵暗号、秘密鍵暗号共に暗号プロセッサから秘密鍵を推定できることが知られている。電力解析攻撃には、単純電力解析SinglePowerAnalysisと差分電力解析DifferentialPowerAnalysisの2種類が存在する。単純電力解析は暗号プロセッサにおける単一の電力消費データの特徴から秘密鍵の推定を行う方式、差分電力解析は多数の電力消費データの差分を解析することで秘密鍵の推定を行う方式である。共通鍵暗号方式に限定した場合、単純電力解析は対策が容易であるためほとんど有効ではないが、差分電力解析が有効な攻撃法として知られている。たとえば、RSAなどの公開鍵暗号に対する差分電力解析を用いた解読法については、非特許文献2などの文献にて述べられている。また、共通鍵暗号方式において、旧来の標準として利用されているDESDataEncryptionStandardsに対する差分電力解析を用いた解読法については、非特許文献3などで述べられている。DESの他に、現在標準的に利用されているAESAdvancedEncryptionStandardについては、非特許文献4などの文献で差分電力解析を用いた解読の可能性が指摘されている。電力解析攻撃を用いた解読技術は特に有効な方法として注目されており、様々な解読法が研究されている。また、解読技術のみならずPAによる解読を防ぐための対策技術も発展しており、解読技術と同様に重要な技術として注目されている。ただし、これらの対策技術を用いた場合、暗号処理を行う回路の回路規模が大きくなるという欠点が知られており、共通鍵暗号方式に対する専用の対策回路は、未対策の回路のおよそ2倍の回路規模が必要となる問題がある。認証チップやスマートカードなどの小型チップにおいては、暗号回路の占める回路規模の割合が非常に大きく、専用の対策回路を組み込むことはコスト増に直結するため、好ましくない。以下の実施形態では、専用の対策回路を用いる代わりに、暗号を利用する上位レイヤの認証プロトコルの改良を行うことで、専用の対策回路によるコスト増を招くことなく、未対策の回路と同程度の回路規模による対策つき認証チップを実現するものである。<チャレンジアンドレスポンス認証プロトコル>認証に際しては、機器の正当性を確認するためにチャレンジアンドレスポンス認証プロトコルと呼ばれる通信プロトコルが利用される。図1は、チャレンジアンドレスポンス認証プロトコルの概要を示す図である。チャレンジアンドレスポンス認証とは、デジタル情報を用いた合言葉であり、認証を行う側親機101から認証される側子機102に対し、チャンレジと呼ばれる乱数を送信する。これに対し、子機102側ではチャンレンジに対してレスポンスと呼ばれる応答を生成し、親機101に返信する。親機101は、チャレンジに対するレスポンスの値を判断し、もし正しいならば、子機102が正当な機器であると判断する。チャレンジとして乱数を用いることで、対応するレスポンスが毎回変化する。これにより、再送攻撃Replayattackに対する防止措置である。再送攻撃とは、過去に外部から観察された応答を繰り返すことで、正当な機器の成りすましを行う攻撃である。つまり、乱数を用いない場合、チャンレジとレスポンスのペアが完全に固定値になるため、攻撃者がこのペアを観察することで、チャレンジに対応する適切なレスポンスを知ることができ、このレスポンスを返すチップを製造することでチップ偽造が容易となるからである。図2は、共通鍵暗号方式を用いたチャレンジアンドレスポンス認証方法プロトコルを示す図である。チャレンジに対するレスポンスの生成は、暗号関数を用いた方法が一般的である。どの暗号関数を用いるかによってメリットとデメリットがあるが、認証チップの場合には、公開鍵暗号よりも小規模な回路で実現可能な共通鍵暗号を用いる方法が広く用いられている。図2に示すプロトコルは、親機101と子機102の認証チップ間で、秘密鍵Kを事前共有している。これは、親機101および子機102に搭載されるチップの製造時に秘密鍵共有鍵Kの値を書き込むことで実現できる。この秘密鍵Kの値が外部に漏洩しないことがセキュリティ上の最も重要な前提である。S301で、認証を行う側の親機101は、乱数rを生成し、認証される側の子機102に送信する。S302では、まず、子機102は親機101から乱数rを受け取る。さらに、子機102は、親機101から受け取った乱数rに対し、秘密鍵Kを用いて暗号処理Encr,Kを実行し、暗号処理によって得られた値を応答a=Encr、Kとして親機101に返信する。ただし、C=EncP,Kとは、共有鍵Kを用いて、平文Pを鍵Kにより暗号化した結果が暗号文Cであることを表す。S303で、応答aを受け取った親機101は、秘密鍵Kを用いて復号処理Deca,Kを実行し、復号処理によって得られる値を復号結果r’=Deca,Kとする。そして、復号結果r’と、S301で生成した乱数rを比較する。復号結果r’と乱数rが一致するならば、親機101は子機102を正当な機器と認定する。子機102が、乱数rに対応した正当な応答aを生成できるのは、親機101が有している秘密鍵Kと同じ鍵Kを有する場合に限られるからである。図2に示されているプロトコルは、暗号化と復号の両方を利用したものであるが、暗号化のみを利用する方法もある。その場合は、親機101と子機102の双方で乱数rに対し秘密鍵Kによる暗号処理Encr,Kを実行し、親機101側で双方の暗号文が一致することを確認することでチャレンジアンドレスポンス認証を実現することも可能である。図3は、共通鍵暗号方式を用いた別の一般的なチャレンジアンドレスポンス認証プロトコル両側認証、暗号化復号の処理を示す図である。図2で示した方式は片側認証と呼ばれ、親機101が子機102の正当性を確認するための認証プロトコルである。これでは、子機102は親機101の正当性を確認することができないため、子機102は親機101の不正を防止できない。これを防ぐために、子機102も親機101の正当性を確認する手段が必要である。これを実現するのが両側認証と呼ばれる認証プロトコルである。両側認証プロトコルでは、子機102が親機101にチャレンジを送信し、親機101からの応答を確認する処理が行われる。図2の認証プロトコルを両側認証に拡張した認証プロトコルを図3に示す。S401では、図2のS301と同様、親機101が乱数rを生成し、子機102に送信する。乱数rを受け取った子機102は、S403で秘密鍵Kを用いた暗号処理Encr,Kを実行する。また子機102は、S402で乱数sを生成する。S402とS403を処理する順番はどちらが先でも良いし、またはパラレルに処理がされても良い。そして、暗号処理によって得られた値を応答a=Encr、Kとして、乱数sと共に親機101に返信する。S404で、応答aを受け取った親機101は、秘密鍵Kを用いた復号処理Deca,Kを実行し、復号処理によって得られる値を復号結果r’=Deca,Kとする。そして、復号結果r’と、S401で生成した乱数rを比較する。復号結果r’と乱数rが一致するならば、親機101は子機102を正当な機器と認定する。S404では、さらに、秘密鍵Kを用いた暗号処理Encs,Kを実行する、暗号処理によって得られた値b=Encs,Kは子機102に送信される。S405で、親機101から値bを受け取った子機102は、秘密鍵Kを用いて復号処理Decb,Kを実行し、復号処理によって得られる値を復号結果s’=Decb,Kとする。そして、復号結果s’と、S402で生成した乱数sを比較する。復号結果s’と乱数sが一致するならば、子機102は親機101を正当な機器と認定する。またこの場合も、片側認証の場合と同様に、暗号化のみを利用して認証を実行することが可能である。<共通鍵暗号回路に対する差分電力解析による秘密鍵解読手法>図4は、共通鍵暗号方式の一般的な処理鍵XOR処理とテーブル変換の組み合わせを示す図である。Mは平文もしくは暗号文などの入力データ、Kは拡大鍵である。図4のKは、秘密鍵をもとに特定の処理を行うことでビット長を拡大することで生成される値である。MとKの排他的論理和XORを取った結果を、特定のビット長データごとに分割し、それぞれの分割されたデータに対し、Sboxと呼ばれる変換テーブル演算を行う。MとKは共有鍵によって異なり、例えばDataEncryptionStandardDES、データ暗号化標準の場合は48ビット、AdvancedEncryptionStandardAES、新暗号化標準の場合は128ビットである。Sboxのビット長は暗号の種類に依存するが、例えばDESの場合、6ビット入力4ビット出力である。AESの場合、88ビット入力8ビット出力である。aビット入力bビット出力のSboxの回路規模は、1ビット入力1出力に比べて、a×b×2a倍となるため、入出力のビット長が大きくなるにつれ、急速に増大する。そのため、Sbox入出力のビット長としては、8ビット入力8ビット出力が最も大きいものとして知られている。図4に示されているSboxの一つのテーブル変換wjに関連する平文M、拡大鍵K、Sboxの入力、およびSboxの出力の所定のビットをそれぞれ、mi、ki、xi、およびziとする。外部から暗号を解読しようとする攻撃者にとって、これらのうち、平文と変換テーブルの所定のビット、miとwiは測定可能量として既知であると仮定して、拡大鍵kiの所定のビットを推測することを考える。一般的に、暗号デバイスの消費電力は入出力データ値のハミングウェイトに比例すると考えられている。このことが正しいことを示す実験結果は、非特許文献5などの文献に示されている。差分電力解析では暗号デバイスの消費電力波形を多数取得し、それらを解析することで秘密鍵を推定する。たとえば、非特許文献6では、ノイズ除去のため少なくとも100以上の電力波形が必要であることが指摘されている。以下では、差分電力解析による秘密鍵解読について説明する。差分電力解析は、電力消費データの測定と、電力差分データの解析という2段階から構成される。電力消費データの測定は、攻撃者が既に知っている情報に依存して、図4のA、B、またはCで行うことができる。たとえば、入力Mが既知で制御可能、Sboxの変換テーブルwjも既知、拡大鍵Kは未知であるが固定されている状況では、図4のA点で電力消費データを測定する。また、入力Mが既知で制御可能、拡大鍵Kは未知であるが固定されている状況では、図4のB点またはC点で電力消費データを測定する。攻撃者は、入力データ平文を秘密鍵Kによって暗号化される際の消費電力波形をオシロスコープなどで観測する。図5はそのようにして得られる電力消費曲線の例である。相違なる入力平文に対してそのような測定を統計的に十分な回数だけ行う。その測定で得られた複数の電力消費曲線の集合をGとする。次に、電力消費曲線の解析について説明する。秘密鍵Kは未知であるが、平文と暗号アルゴリズムは既知としているため、秘密鍵をK’と仮定し、秘密鍵K’の今、問題にしているビットをki’とする。既知のmiとwiと、仮定されたki’からSboxの出力zi’=wimiXORki’を演算して、ki’に対する集合Gki’を、次の部分集合G0ki’とG1ki’に分ける。ここで、eは自然数であり、第e桁目のビット値とは、e番目の最下位ビットLSBを表す。式1および2の二つの集合G0ki’およびG1ki’の差分DGki’を次のように定義する。図5は、集合G0ki’またはG1ki’に属する電力消費曲線を平均して得られる平均電力消費曲線の例である。このような平均電力消費曲線が二つの集合G0ki’およびG1ki’に対して得られる。差分DGki’は両者の差である。差分DGki’がどのような曲線になるのか考える。ki’=ki、即ち、仮定された鍵の要素値ki’と真の鍵の要素値kiが一致している場合、集合Gki’の部分集合G0ki’に属するSboxの出力ziのハミングウェイトは0である。なぜなら、仮定されたzi’=wimiXORki’は、これに対応する真のzi=wimiXORkiと全てのmiに関して一致するからである。また、集合Gki’の部分集合G1ki’に属するSboxの出力ziのハミングウェイトは1となる。結局、ki’=kiの場合、となる。この結果は、図6に例が示されているように、差分電力消費曲線中のスパイクの出現をもたらす。一方、ki’≠ki、即ち、仮定された鍵の要素値ki’と真の鍵の要素値kiが一致していない場合、仮定されたzi’=wimiXORki’と、これに対応する真のzi=wimiXORkiとは無関係になる。よって、G0ki’においても、G1ki’においても、仮定されたzi’と、これに対応する真のziは無関係になり、となる。図7は、ki’≠kiの場合の差分電力消費曲線の例である。ki’≠kiの場合の差分電力消費曲線は概ね平坦な曲線となる。上述のように鍵の要素値ki’を仮定した解析を各iについて行えば、最終的に秘密鍵Kの要素全てを解読することができる。図8は、AESにおいてサイドチャンネル攻撃が成功する要因を説明する図である。一般的なAESにおける暗号処理においては、128ビットの拡大鍵Kは、128ビットの平文と排他的論理和XORを取った後、8ビットごとに16分割され、16分割されたそれぞれのデータがSboxに入力される。攻撃者は、それぞれのSboxの消費電力データを利用することで、8ビットごとに分割された拡大鍵K=k15k14k0に対し、8ビット部分鍵kiについて、それぞれの総当りを実行する。つまり、128ビットの鍵の総当りには本来2128の手間が必要であるのに対し、サイドチャネル攻撃を用いることで28の手間を16回、つまり28×16212に減らすことができる。すなわち、サイドチャネル攻撃に必要な手間は、Sboxの入力に関連した部分鍵のビット長に依存する。このビット長は共通鍵暗号方式によって変動するが、既に述べたとおりAESの8ビットが最大である。以上の説明では、図4に示されているような、共通鍵暗号回路としては最も単純なものに対するDPAに関して述べた。このような手法は、図4の鍵XOR処理の前もしくが後、または前後の両方に線形変換を挿入しても成立する。<共通鍵暗号回路に対する差分電力解析対策手法としてのマスク法>従来のDPA対策法としては、暗号処理に対策を施し消費電力をランダム化する手法が存在する。この手法の代表的なものとして、マスク法maskingmethodと呼ばれている手法が知られているたとえば、非特許文献7を参照。以下、比較例1と呼ぶ。電力解析攻撃対策なしの暗号処理において計算されるデータをMとすると、比較例1に記載されているDPA対策は、データMを計算する代わりに、で表されるデータM’、Rを計算することで暗号処理を行う方法である。ここで、Rは乱数であり、暗号処理を実行する度に発生させる値である。この方法により、暗号処理のデータをランダムな値でマスクされる。よって、データがランダム化されることで消費電力もランダム化されるため、DPAに安全な処理を実現することができる。この方法の問題点は、M’およびRの両方を計算する必要があるため、対策なしの回路の2倍の回路規模を必要とすることである。上の方法をAESにおけるDPA対策に適用する際には、部分鍵kiに関連する平文Mおよび乱数Rの部分をそれぞれ、MiおよびRiとして、6式の代わりに、で表されるデータMi’、Riを計算することで暗号処理を行う。この場合も、暗号処理ごとに計算されるデータ値がランダムであるため、DPAに対して安全な処理を実現することができる。しかしながら、Mi’およびRiの両方を計算する必要があるため、対策なしの回路の2倍の回路規模を必要とすることである。比較例1に示されるような専用の対策つき暗号回路を用いると、消費電力のランダム化がなされる代わりに、回路規模が、対策なしの回路より大きくなる。比較例1では、ラインダールアルゴリズムを実行する回路を構成している。その回路規模は、17.6Kゲートであると評価されている。また、鍵長を128ビット専用にした場合には、回路規模は2.2Kゲートほど減少する。それでも、サイドチャンネル攻撃対策を施すことによって、10Kゲート以上の回路規模の増大が見込まれる。そこで、暗号より上位層の認証プロトコルへの改良によりサイドチャネル攻撃に安全な処理を実現する方法への要望が存在する。この場合、暗号回路そのものは、対策なしの回路をそのまま用いるため、電力解析攻撃対策によって回路規模が極端に大きくなることを回避することができる。認証プロトコルは、乱数を伴う処理であるため、この乱数を適切に利用することで、サイドチャネル攻撃に対して安全となる方法が考えられる。すなわち、一般的なチャレンジアンドレスポンス認証では、図2~3に示されるように、固定の秘密鍵Kに対する暗号化処理が行われるが、これはサイドチャネル攻撃に対して脆弱である。この欠点は、乱数を用いて秘密鍵をマスク化することで一見克服できそうである。<単純な秘密鍵のランダム化による電力解析対策手法の比較例>図9は、単純な鍵のランダム化による認証プロトコル片側認証、暗号化復号の例の機能ブロック図である。図9に示されている方法では、図2に示した共通鍵暗号を用いたチャレンジアンドレスポンス認証方法において、マスク法を適用して鍵Kの代わりに、を用いる。S451で、認証を行う側の親機101は、乱数rを生成し、認証される側の子機102に送信する。S452では、まず、子機102は親機101から乱数rを受け取る。さらに、子機102は、親機101から受け取った乱数rに対し、秘密鍵Kを用いて暗号処理Encr,K’を実行し、暗号処理によって得られた値を応答a=Encr、K’として親機101に返信する。この応答aの生成は、鍵Kを乱数rでマスクした上で生成する。S453で、応答aを受け取った親機101は、秘密鍵K’を用いて復号処理Deca,K’を実行し、復号処理によって得られる値を復号結果r’=Deca,K’とする。そして、復号結果r’と、S501で生成した乱数rを比較する。復号結果r’と乱数rが一致するならば、親機101は子機102を正当な機器と認定する。子機102が、乱数rに対応した正当な応答aを生成できるのは、秘密鍵Kを有する場合に限られるからである。このような方法は、鍵Kをランダム化することで、サイドチャンネル攻撃に対して安全であるように見えるが、次のような理由で必ずしもそうではなく、脆弱であることが分かる。この方法において、乱数rは、親機101と子機102の間で送受信され、その結果、共有される。つまり、乱数rは、外部から容易に観測できると考えるべきである。もし、乱数rが攻撃者によって観測されれば、差分電力解析を用いて、鍵Kを解読することが可能である。また、この方法には幾つかの変形例が考えられる。上の方法では、乱数rが親機101と子機102の間で送受信されることによって、外部から観測され得る。そこでたとえば、マスク化のために用いる変数を、乱数rではなく、さらに別の変数にすることが考えられる。たとえば、乱数rと式8のK’を用いて、mr=Encを除いて評価しており、対策に伴う回路規模の増加分を以降では回路規模と表記する。図22は回路規模の算定基準となるNANDゲートの回路の例を示す図であり、図23はNORゲートの回路の例を示す図である。図22および図23のように、2入力NANDゲートおよび2入力NORゲートのいずれも、4つの電界効果トランジスタFET、たとえば金属酸化物半導体電界効果トランジスタMOSFETによって1ゲートが構成される。図24はNOTゲートの回路の例を示す図である。NOTゲートは、2つのFETから構成される。よって、図19中の表に示されているように、回路規模としては、0.5ゲートとなる。図25は、1入力Dフリップフロップによって構成されるレジスタの回路の例を示す図である。レジスタは図23に示されているように、4つのNANDゲートと、1つのNORゲートと、4つのNOTゲートと、それぞれ1ゲートからなる4つのゲート単位から構成される。よって、レジスタのゲート数は11ゲートとなる。図26は、2入力1出力2-1XOR排他論理和ゲートの回路の例を示す図である。2-1XORゲート回路は、2つのNORゲートと1つのNANDゲートとから構成される。よって、2-1XORゲート回路の回路規模は3.5ゲートとなる。図27Aおよび図27Bは、2-1セレクタの回路の例を示す図である。図27Aがマルチプレクサ、図27Bはデマルチプレクサの例を示す図である。図27Aに示されているように、2-1マルチプレクサは、3つのNANDゲートと、1つのNOTゲートから構成される。よって、2-1マルチプレクサの回路規模は、3.5ゲートとなる。また、図27Bに示されているように、デマルチプレクサは、2つのNANDゲートと3つのNOTゲートから構成され、回路規模は3.5ゲートとなる。図28は、シフト/巡回レジスタの回路の例である。図28では、3段分のシフト/巡回レジスタが示されている。1段分のシフト/巡回レジスタは、1つのセレクタMUXと1つのレジスタから構成される。よって、シフト/巡回レジスタの回路規模は14.5ゲートとなる。図29は、線形帰還シフトレジスタLSFR/剰余演算回路の例を示す図である。図28では、3段分のLSFR/剰余演算回路が示されている。図29に示されているように、1段分のLSFR/剰余演算回路は、1つのセレクタMUXと、1つのレジスタと、ビット一に対応して0または1個のXORゲートから構成される。よって、LSFR/剰余演算回路の回路規模は、高々18ゲートとなる。本実施例の回路規模の見積もりは次のようになる。本実施例の回路は、ランダム化鍵を保存するための128ビット鍵レジスタが1つと、128入力1出力128-1セレクタ回路が1つと、128入力1出力128-1マルチプレクサ1つとから構成される。よって、本実施例の回路規模は、2.3kゲートとなる。この結果は、図30にまとめられている。なお、対策回路規模増加分の見積もりに際しては、暗号回路および対策なしの場合と共通な回路128ビット鍵レジスタ、および乱数生成回路を除いて評価しており、対策に伴う回路規模の増加分を以降では回路規模と表記する。このように、本実施例では、上述のランダム化鍵を生成方法を実施するための回路であって、回路規模が小さな回路が提供された。本実施例の回路を使ったランダム化鍵の生成方法を、上述の実施形態1~6のいずれか一つに用いることによって、サイドチャネル攻撃に対する安全性と、小規模高速な暗号処理を両立する暗号化処理装置を得ることができる。<ランダム化鍵生成方法の第2の実施例>図31を参照しながら、秘密鍵KMASTからランダム化鍵KENCを生成する方法の第2の実施例を説明する。図31は、ランダム化鍵の生成の処理の第2の実施例を示す図である。128ビット秘密鍵KMASTと、乱数発生回路によって生成された乱数rとが128入力LFSR回路に入力され、r回数だけビットシフトを繰り返して、ランダム化鍵KENCが生成される。乱数rの最大値は、LFSR回路の最大周期2128-1以下で構わない。本実施例の回路規模の見積もりは次のようになる。本実施例の回路は、128ビット鍵レジスタが1つと、128ビットLSFR回路1つとから構成されている。よって、図21中の表を参照すれば、3.7kビットとなる。<ランダム化鍵生成方法の第3の実施例>図32は、ランダム化鍵の生成の処理の第3の実施例を示す図である。128ビット秘密鍵KMASTの各ビットの値kMAST,1、kMAST,2、...、kMAST,127は、結線回路の接続先のあるビットに入力され、秘密鍵は最上位ビットから、k’MAST,1、k’MAST,2、...、k’MAST,127と値が再配列される。このような再配列は、乱数発生回路によって生成された乱数rの回数だけ繰り返され、ランダム化鍵KENCが生成される。繰り返しの回数はリソースに応じて設定すればよいが、十分大きな値が必要となる。この実施例では結線回路は配線だけであるため回路規模に含める必要はなく、回路規模としては128ビットランダム化鍵レジスタのみの1.4kゲートとなる。<ランダム化鍵生成方法の第4の実施例>図33は、ランダム化鍵の生成の処理の第4の実施例を示す図である。本実施例ではまず、128ビット秘密鍵KMASTの各ビットの値kMAST,1、kMAST,2、...、kMAST,127は、結線回路1および2の接続先のセレクタ回路に入力される。セレクタ回路には、乱数発生回路によって生成された1ビットの乱数がセレクタ信号として入力され、結線回路1または2のどちらを介して入力されたものをkMAST,nとするか選択する。このようにして秘密鍵は最上位ビットから、k’MAST,1、k’MAST,2、...、k’MAST,127と値が再配列される。このような再配列は、乱数発生回路によって生成された乱数rの回数だけ繰り返され、ランダム化鍵KENCが生成される。結線回路のパターンは2通り以上としてもよく、繰り返し回数はリソースに応じて設定することができる。本実施例の回路規模の見積もりは次のようになる。本実施例の回路は、128ビット鍵レジスタが1つと、128ビット2-1セレクタ回路1つとから構成されている。よって、図21中の表を参照すれば、1.8kビットとなる。<ランダム化鍵生成方法の第5の実施例>図34は、ランダム化鍵の生成の処理の第5の実施例を示す図である。本実施例ではまず、128ビット秘密鍵KMASTを8ビットごとに16分割する。16分割された秘密鍵KMASTのそれぞれと、乱数発生回路によって生成された乱数とは、8ビットのLFSR回路に入力され、r回だけ帰還シフトを行う。シフトした16個の8ビット部分鍵をXOR回路に入力し、ランダム化された8ビット部分鍵とする。この処理を16回繰り返し、128ビットのランダム化鍵KENCが生成される。本実施例の回路規模の見積もりは次のようになる。本実施例の回路は、128ビット鍵レジスタが2個と、8ビットLFSR回路16個と、8ビット16入力XOR回路1個と、8ビット16-1デマルチプレクサ回路2個から構成される。よって、図21中の表を参照すれば、4.5kビットとなる。<ランダム化鍵生成方法の第6の実施例>図35は、ランダム化鍵の生成の処理の第6の実施例を示す図である。本実施例ではまず、128ビット秘密鍵KMASTを8ビットごとに16分割する。16分割された秘密鍵KMASTのi番目の部分鍵と、乱数発生回路で発生された4ビットの乱数r1は、セレクタ回路に入力され、16個の部分鍵のうちの一つが選択される。次に、選択された8ビットの部分鍵の一つと、乱数発生回路で発生された4ビットの乱数r2がLFSR回路に入力され、r2回だけ帰還シフトを行う。その結果は、一旦、データレジスタに、kMAST,iと保存される。これをi=1から16まで、16回繰り返し、16個のkMAST,ii=1~16を得る。次に、16個のkMAST,iをXOR回路に入力し、ランダム化された8ビット部分鍵とする。この処理を16回繰り返し、128ビットのランダム化鍵KENCが生成される。本実施例の回路規模の見積もりは次のようになる。本実施例の回路は、128ビット鍵レジスタが2個と、8ビット16入力1出力16-1セレクタ回路1個と、8ビットLFSR回路1個と、8ビット16入力1出力XOR回路1個と、8ビット16-1デマルチプレクサ回路2個から構成される。よって、図21中の表を参照すれば、4.6kビットとなる。<ランダム化鍵生成方法の第7の実施例>図36Aおよび図36Bは、ランダム化鍵の生成の処理の第7の実施例を示す図である。本実施例ではまず、128ビット秘密鍵KMASTを8ビットごとに16分割する。16分割された秘密鍵KMASTのi番目の部分鍵kMAST,iは、i番目のビット転置回路であるビット転置回路iに入力される。図36Bは、ビット転置回路iを示す図である。秘密鍵KMASTのi番目の8ビット部分鍵kMAST,iと、乱数発生回路で発生された0~2までの整数である乱数r1と、が3入力1出力セレクタに入力される。残りの2つの入力は、前回のセレクタの出力k’MAST,iと、k’MAST,iをさらに結線回路に入力した結果得られる出力の2つである。このセレクタによる選択を、乱数発生回路で発生された乱数r2の回数だけ繰り返し、出力kMAST,iを得る。ビット転置回路1~16の出力、kMAST,1~kMAST,16は、XOR回路に入力され圧縮され、8ビットランダム化鍵kENC,iを得る。これを16回繰り返し、16個の8ビットランダム化鍵kENC,ii=1~16を結合することで、128ビットのランダム化鍵KENCを得る。本実施例の回路規模の見積もりは次のようになる。本実施例の回路は、128ビット鍵レジスタが2個と、8ビット3入力1出力3-1セレクタ回路16個と、8ビット16入力1出力XOR回路1個と、8ビット16-1デマルチプレクサ回路1個から構成される。よって、図21中の表を参照すれば、4.5kビットとなる。<作用効果>図37は、比較例1のラインダールアルゴリズムを実行する回路の回路規模と、上記実施例1~7の回路の回路規模を比較した表を示している。実施例1~7の回路を用いることで、従来法1のように回路を肥大化することなく、小規模な回路構成によりサイドチャネル攻撃に対して安全な認証を実現することができる。上記では、圧縮回路として、XOR回路またはセレクタ回路を用いたが、加算または減算回路を用いても良い。加算または減算回路の回路規模は約10ゲート/ビットである。"