"それぞれK1K2...Knビットからなるn個の鍵を乱数によりランダム化するランダム化回路と、前記ランダム化されたn個の鍵から1つの鍵を生成することにより圧縮して得られる圧縮鍵を出力する圧縮化回路と、前記圧縮鍵を用いて入力データを暗号化する暗号化回路と、を含むことを特徴とする暗号処理装置。第一の乱数と第二の乱数を入力し合成し前記乱数として出力する乱数合成回路を更に含む、ことを特徴とする請求項1に記載の暗号処理装置。それぞれK1K2...Knビットからなるn個の鍵を乱数によりランダム化し、前記ランダム化されたn個の鍵から1つの鍵を生成することにより、圧縮して得られる圧縮鍵を生成し、前記圧縮鍵を用いて認証する、ことを特徴とする認証方法。第一の乱数と第二の乱数を入力し合成し前記乱数として出力する、ことを特徴とする請求項3に記載の暗号処理方法。親機に相当する第1のコンピュータと子機に相当する第2のコンピュータとで前記n個の鍵として秘密鍵Kを共有し、前記第1のコンピュータにて、乱数rを生成し、前記第1のコンピュータから前記第2のコンピュータに前記乱数rを送信し、前記第2のコンピュータにて、前記n個の秘密鍵Kと前記第1のコンピュータから受信した前記乱数rとから前記圧縮鍵の生成に従って圧縮鍵Kcmpを生成し、前記第2のコンピュータにて、前記圧縮鍵Kcmpを用いて前記第1のコンピュータから受信した前記乱数rを暗号化することで暗号化された乱数aを生成して前記第1のコンピュータに送信し、前記第1のコンピュータにて、前記n個の秘密鍵Kと前記乱数rとから前記圧縮鍵の生成に従って前記圧縮鍵Kcmpを生成し、前記第1のコンピュータにて、前記圧縮鍵Kcmpを用いて前記第2のコンピュータの認証を行う、ことを特徴とする請求項3または4のいずれか記載の認証方法。親機に相当する第1のコンピュータと子機に相当する第2のコンピュータとで前記n個の鍵としてn個の秘密鍵Kを共有し、前記第1のコンピュータにて、第1の乱数rを生成し、前記第1のコンピュータから前記第2のコンピュータに前記第1の乱数rを送信し、前記第2のコンピュータにて、第2の乱数sを生成し、前記第2のコンピュータにて、前記n個の秘密鍵Kと前記第1のコンピュータから受信した前記第1の乱数rとから前記圧縮鍵の生成に従って圧縮鍵Kcmpを生成し、前記第2のコンピュータにて、前記圧縮鍵Kcmpを用いて前記第1のコンピュータから受信した前記第1の乱数rを暗号化することで第1の暗号化された乱数aを生成して前記第2の乱数sとともに前記第1のコンピュータに送信し、前記第1のコンピュータにて、前記n個の秘密鍵Kと前記第1の乱数rとから前記圧縮鍵の生成に従って前記圧縮鍵Kcmpを生成し、前記第1のコンピュータにて、前記圧縮鍵Kcmpを用いて前記第2のコンピュータの認証を行い、前記第1のコンピュータにて、前記認証に成功した場合に、前記圧縮鍵Kcmpを用いて前記第2のコンピュータから受信した前記第2の乱数sを暗号化することで第2の暗号化された乱数bを生成して前記第2のコンピュータに送信し、前記第2のコンピュータにて、前記圧縮鍵Kcmpを用いて前記第1のコンピュータの認証を行う、ことを特徴とする請求項3または4のいずれか記載の認証方法。前記n個の秘密鍵Kをそれぞれ、前記第1の乱数rのビット値に応じて巡回シフトし、前記n個の巡回シフトの結果を、ビット値ごとに排他論理和演算して前記圧縮鍵Kcmpを生成する、ことを特徴とする請求項5または6のいずれかに記載の認証方法。前記n個の秘密鍵Kをそれぞれ、前記第1の乱数rとビット値ごとにビット結合し、前記n個のビット結合の結果を、ビット値ごとに排他論理和演算し、前記排他論理和演算の結果に対して、ガロア体GF上の剰余演算を行って前記圧縮鍵Kcmpを生成する、ことを特徴とする請求項5または6のいずれかに記載の認証方法。前記n個の秘密鍵Kをそれぞれ、前記第1の乱数rのビット値に応じて巡回シフトレジスタ処理し、前記n個の巡回シフトレジスタ処理の結果を、ビット値ごとに排他論理和演算して前記圧縮鍵Kcmpを生成する、ことを特徴とする請求項5または6のいずれかに記載の認証方法。前記n個の秘密鍵Kのそれぞれについて、前記第1の乱数rとガロア体GF上の乗算を実行し、前記n個の乗算の結果を、ビット値ごとに排他論理和演算し、前記排他論理和演算の結果に対して、ガロア体GF上の剰余演算を行って前記圧縮鍵Kcmpを生成する、ことを特徴とする請求項5または6のいずれかに記載の認証方法。親機に相当する第1のコンピュータと子機に相当する第2のコンピュータとで前記n個の鍵としてn個の秘密鍵Kを共有し、前記第1のコンピュータにて、第1の乱数rを生成し、前記第1のコンピュータから前記第2のコンピュータに前記第1の乱数rを送信し、前記第2のコンピュータにて、第2の乱数sを生成し、前記第2のコンピュータにて、前記n個の秘密鍵Kと前記第1のコンピュータから受信した前記第1の乱数rと前記第2の乱数sとから前記圧縮鍵の生成に従って圧縮鍵Kcmpを生成し、前記第2のコンピュータにて、前記圧縮鍵Kcmpを用いて前記第1のコンピュータから受信した前記第1の乱数rを暗号化することで暗号化された乱数aを生成して前記第2の乱数sとともに前記第1のコンピュータに送信し、前記第1のコンピュータにて、前記n個の秘密鍵Kと前記乱数rと前記第2のコンピュータから受信した乱数sとから前記圧縮鍵の生成に従って前記圧縮鍵Kcmpを生成し、前記第1のコンピュータにて、前記圧縮鍵Kcmpを用いて前記第2のコンピュータの認証を行う、ことを特徴とする請求項3または4のいずれか記載の認証方法。親機に相当する第1のコンピュータと子機に相当する第2のコンピュータとで前記n個の鍵としてn個の秘密鍵Kを共有し、前記第1のコンピュータにて、第1の乱数rを生成し、前記第1のコンピュータから前記第2のコンピュータに前記第1の乱数rを送信し、前記第2のコンピュータにて、第2の乱数sを生成し、前記第2のコンピュータにて、前記n個の秘密鍵Kと前記第1のコンピュータから受信した前記第1の乱数rと前記第2の乱数sとから前記圧縮鍵の生成に従って圧縮鍵Kcmpを生成し、前記第2のコンピュータにて、前記圧縮鍵Kcmpを用いて前記第1のコンピュータから受信した前記第1の乱数rを暗号化することで第1の暗号化された乱数aを生成して前記第2の乱数sとともに前記第1のコンピュータに送信し、前記第1のコンピュータにて、前記n個の秘密鍵Kと前記第1の乱数rと前記第2のコンピュータから受信した前記第2の乱数sとから前記圧縮鍵の生成に従って前記圧縮鍵Kcmpを生成し、前記第1のコンピュータにて、前記圧縮鍵Kcmpを用いて前記第2のコンピュータの認証を行い、前記第1のコンピュータにて、前記認証に成功した場合に、前記圧縮鍵Kcmpを用いて前記第2のコンピュータから受信した前記第2の乱数sを暗号化することで第2の暗号化された乱数bを生成して前記第2のコンピュータに送信し、前記第2のコンピュータにて、前記圧縮鍵Kcmpを用いて前記第1のコンピュータの認証を行う、ことを特徴とする請求項3または4のいずれか記載の認証方法。前記第1の乱数rと前記第2の乱数sをビット値ごとに排他論理和演算して合成された乱数を生成し、前記n個の秘密鍵Kをそれぞれ、前記合成された乱数のビット値に応じて巡回シフトし、前記n個の巡回シフトの結果を、ビット値ごとに排他論理和演算して前記圧縮鍵Kcmpを生成する、ことを特徴とする請求項11または12のいずれかに記載の認証方法。前記第1の乱数rと前記第2の乱数sをビット値ごとに排他論理和演算して合成された乱数を生成し、前記n個の秘密鍵Kをそれぞれ、前記合成された乱数とビット値ごとにビット結合し、前記n個のビット結合の結果を、ビット値ごとに排他論理和演算し、前記排他論理和演算の結果に対して、ガロア体GF上の剰余演算を行って前記圧縮鍵Kcmpを生成する、ことを特徴とする請求項11または12のいずれかに記載の認証方法。前記第1の乱数rと前記第2の乱数sをビット値ごとに排他論理和演算して合成された乱数を生成し、前記n個の秘密鍵Kをそれぞれ、前記合成された乱数のビット値に応じて巡回シフトレジスタ処理し、前記n個の巡回シフトレジスタ処理の結果を、ビット値ごとに排他論理和演算して前記圧縮鍵Kcmpを生成する、ことを特徴とする請求項11または12のいずれかに記載の認証方法。前記第1の乱数rと前記第2の乱数sをビット値ごとに排他論理和演算して合成された乱数を生成し、前記n個の秘密鍵Kのそれぞれについて、前記合成された乱数とガロア体GF上の乗算を実行し、前記n個の乗算の結果を、ビット値ごとに排他論理和演算し、前記排他論理和演算の結果に対して、ガロア体GF上の剰余演算を行って前記圧縮鍵Kcmpを生成する、ことを特徴とする請求項11または12のいずれかに記載の認証方法。コンピュータに、複数個の鍵のそれぞれを乱数によりランダム化し、前記ランダム化された複数個の鍵を圧縮して得られる圧縮鍵を暗号処理のための鍵として出力する、処理を実行させるためのプログラム。コンピュータに、第一の乱数と第二の乱数を入力し合成し前記乱数として出力する、処理を実行させるための請求項17に記載のプログラム。以下、本発明を実施するための形態について図面を参照しながら詳細に説明する。暗号方式は、公開鍵暗号方式と共通鍵暗号方式に大別される。公開鍵暗号方式とは、暗号化と復号で異なる鍵を用いる方式であり、暗号化を行うための鍵を一般に公開する代わりに、暗号文を復号するための鍵を受信者のみの秘密情報とすることで安全性を保つ方式である。これに対し、共通鍵暗号方式と呼ばれるものは、暗号化と復号で同一の鍵を用いる方式であり、この秘密鍵を送信者と受信者以外の第三者にわからない情報とすることで安全性を保つ方式である。いずれの暗号方式を用いた場合でも、秘密鍵が外部に漏洩しないことがセキュリティ上の大きな前提となる。セキュリティ機能を備えた組み込み機器に求められる性質として、耐タンパ性と呼ばれるものがある。耐タンパとは、覗き見防止の意味であり、組み込み機器の外部から観察された情報により、組み込み機器内部に格納された重要情報が漏洩しない性質を指す。暗号を用いた認証機器の場合、外部から観察された情報により秘密鍵が漏洩しない性質である。一般的な認証機器は、機器製造時に秘密鍵が内部に書き込まれ、製造後は鍵が外部に取り出されることは無いため、高い耐タンパ性を有すると考えられていた。しかし、1996年に発見されたサイドチャネル攻撃により、認証機器を含めた組み込み装置全般に対して、製造後は鍵を外部に取り出さない場合でも、秘密鍵が漏洩することが判明したため、サイドチャネル攻撃への対策が耐タンパ上の必須課題となった。サイドチャネル攻撃とは、組み込み機器に対する物理破壊を伴わずに、外部から観察可能な情報を用いて秘密鍵を解読する攻撃である。1996年には、処理時間を観察するタイミング攻撃が提案されたが、対策も容易であったため大きな脅威とならなかった。しかし1998年に、消費電力を観察する電力解析攻撃と呼ばれる手法が提案され、大きな脅威として現在でも注目されている。PAとは、1998年にPaulKocherによって考案された手法で、組み込み機器に様々な入力データを与えた時の電力消費データを収集解析することで、内部の鍵情報を推定する手法である。特に、組み込み機器がスマートカードチップや認証チップなどの単体のLSIチップである場合、消費電力の測定が容易であるため、PA対策は耐タンパ上の大きな課題である。PAを用いることで、公開鍵暗号、秘密鍵暗号共に暗号プロセッサから秘密鍵を推定できることが知られている。PAには、単純電力解析電力差分攻撃の2種類が存在する。SPAは暗号プロセッサにおける単一の電力消費データの特徴から秘密鍵の推定を行う方式、DPAは多数の電力消費データの差分を解析することで秘密鍵の推定を行う方式である。共通鍵に限定した場合、SPAは対策が容易であるためほとんど有効ではないが、DPAが有効な攻撃法として知られている。SPA、DPAを用いた解読技術としては代表的なものとして次のような論文が発表されている。RSAなどの公開鍵暗号に対するDPAを用いた解読法については、非特許文献2などの文献にて述べられている。また、共通鍵暗号方式において、旧来の標準として利用されているDESに対するDPAを用いた解読法については、非特許文献3で述べられている。DESの他に、現在標準的に利用されているAESについては、非特許文献4などの文献でDPAを用いた解読の可能性が指摘されている。PAを用いた解読技術は特に有効な方法として注目されており、様々な解読法が研究されている。また、解読技術のみならずPAによる解読を防ぐための対策技術も発展しており、解読技術と同様に重要な技術として注目されている。ただし、これらの対策技術を用いた場合、暗号処理を行う回路の回路規模が大きくなるという欠点も知られており、共通鍵暗号に対する専用の対策回路は、未対策の回路の2倍の回路規模が必要という問題がある。認証チップやスマートカードの小型チップにおいては、暗号回路の占める回路規模の割合は非常に大きいため、専用の対策回路を組み込むことはコスト増に直結する。本実施形態は、専用の対策回路を用いる代わりに、暗号を利用する上位レイヤの認証プロトコルの改良を行うことで、専用の対策回路によるコスト増を招くことなく、未対策の回路と同程度の回路規模による対策つき認証チップを実現することができる。<チャレンジアンドレスポンス認証プロトコル>認証チップにおいては、機器の正当性を確認するために、チャレンジアンドレスポンス認証プロトコルと呼ばれる通信プロトコルが利用される。チャレンジアンドレスポンス認証プロトコルの概要を図1に示す。チャレンジアンドレスポンス認証とは、デジタル情報を用いた合言葉であり、認証を行う側から認証される側に対し、チャンレジと呼ばれる乱数を送信する。これに対し、子機102側ではチャンレンジに対してレスポンスと呼ばれる応答を生成し、親機101に返信する。親機101は、チャレンジに対するレスポンスの値を判断し、もし正しいならば、子機102が正当な機器であると判断する。チャレンジとして乱数を用いることで、対応するレスポンスが毎回変化する。これにより、再送攻撃に対する防御が行える。再送攻撃とは、過去に外部から観察された応答を繰り返すことで、正当な機器の成りすましを行う攻撃である。つまり、乱数を用いない場合、チャンレジとレスポンスのペアが完全に固定値になる。このため、攻撃者がこのペアを観察することで、チャレンジに対応する適切なレスポンスを知ることができ、このレスポンスを返すチップを製造することでチップ偽造が容易となるからである。例えるならば、山に対する川という合言葉しか用いないシステムであることを、悪意のある第三者が知ることができれば、常に川と応答することで成りすましが可能となる。チャレンジに対するレスポンスの生成は、暗号関数を用いた方法が一般的である。どの暗号関数を用いるかによってメリットとデメリットがあるが、認証チップの場合、回路規模の小ささを優先できるメリットがある共通鍵暗号を用いる方法が広く用いられている。図2は、共通鍵暗号を用いた一般的に考えられるチャレンジアンドレスポンス認証の機能ブロックである。図2に示す認証方式は、親機101と子機102の認証チップ間で、秘密鍵Kを事前共有している。これは、チップの製造時にKの値を書き込むことで実現できる。この値が外部に漏洩しないことがセキュリティ上の重要な前提である。認証を行なう側の親機101は、乱数rを生成し、認証される側の子機102に送信する。子機102は、乱数rに対し、秘密鍵Kによる暗号処理aEncを実行し、応答aを生成し、親機101に返信する。ただし、CEncとは、共通鍵暗号を用いて、平文Pを鍵Kにより暗号化した結果が暗号文Cであることを表す。応答aを受け取った親機101は、秘密鍵Kによる復号処理r’Decを実行し、復号結果r’を得る。復号結果rがrと一致するならば、親機101は子機102を正当な機器と認定する。乱数rに対応した正当なレスポンスaを生成できるのは、秘密鍵Kを有する場合に限られるので、親機101は子機102の正当性を確認することができる。図2は暗号化と復号の両方を利用した親機101のみによる片側認証であるが、暗号化のみによるチャンレジアンドレスポンス認証も可能であり、その方法は図3に示される。図3は、共通鍵暗号を用いた一般的に考えられるチャレンジアンドレスポンス認証の機能ブロック図である。図3では、親機101と子機102の認証チップ間で、秘密鍵Kを事前共有しており、認証を行なう側の親機101は、乱数rを生成し、認証される側の子機102に送信する。子機102は、乱数rに対し、秘密鍵Kによる暗号処理aEncを実行し、応答aを生成し、親機101に返信する。ここまでは図2と同じであるが、親機101が子機102の正当性を確認するために、応答aを復号する代わりに乱数rを暗号化しa’Enc、その処理結果a’が子機102からの応答aと一致するか判定する。そして、一致するならば子機102が正当であると判断する。図2、図3は、片側認証と呼ばれる、親機101が子機102の正当性を確認するための認証プロトコルである。これでは、子機102は親機101の正当性を確認することができないため、子機102は親機101の不正を防止できない。これを防ぐために、子機102も親機101の正当性を確認する手段が必要である。これを実現するのが両側認証と呼ばれる認証プロトコルであり、子機102が親機101にチャレンジを送信し、親機101からのレスポンスを確認する処理が行われる。図2の認証プロトコルを両側認証に拡張した認証プロトコルを図4に示す。すなわち、図4は、共通鍵暗号を用いた一般的に考えられるチャレンジアンドレスポンス認証の機能ブロック図である。図2と同様、親機101が乱数rを子機102に送信し、子機102がrを秘密鍵Kで暗号化した結果aを計算する。図2との違いは、このとき子機102側でも乱数sを生成することである。次にasが親機101に送信され、親機101はaを秘密鍵Kで復号し、rと一致するなら子機102が正当であると判断し、さらに秘密鍵Kを用いてsを暗号化した結果bを生成する。このbが子機102に送られた後、子機102は親機101からの応答bを秘密鍵Kにより復号し、その結果がsと一致するならば親機101が正当であると判断する。図4は暗号化復号を用いた両側認証であるが、暗号化のみの認証も可能であり、その機能ブロック図は図5に示される。親機101が乱数rを子機102に送信し、子機102がrを秘密鍵Kで暗号化した結果aを計算しつつ、乱数sを生成し、asを親機101に送信する。親機101はrを秘密鍵Kで暗号化した結果a’が子機102からの応答aと一致するならば、子機102が正当であると判断した上で、子機102からの乱数sを秘密鍵Kにより暗号化した結果bを生成し、子機102に送信する。子機102は、乱数sを秘密鍵Kにより暗号化した結果b’を生成し、bに一致するならば親機101が正当であると判断する。<共通鍵暗号回路に対するDPAによる秘密鍵解読手法>図6は、共通鍵暗号の一般的な処理のアルゴリズムを示す図である。Mは平文などの入力データ、Kは拡大鍵である。図6に示すKは、拡大鍵と呼ばれる値であり、秘密鍵をもとに、特定の処理を行うことでビット長を拡大することで生成される値である。MとKの排他的論理和した結果を、特定のビット長データごとに分割し、それぞれの分割されたデータに対し、Sboxと呼ばれる変換テーブル演算を行う。MKは共通鍵暗号によって異なり、例えばDESの場合48bitAESの場合128bitである。Sboxのビット長は暗号に依存するが、例えばDESの場合6bit入力4bit出力、AESの場合8bit入力8bit出力である。abit入力bbit出力のSboxの回路規模は、a×b×2aに比例して大きくなるため、Sbox入出力のビット長には上限があり、8bit入出力Sboxが最も大きいものとして知られている。図6の構成においてwjの入出力に関係するビットのみを取り出した構成を図7に示す。図7において、mjは平文などの既知の値、kjは未知の値、wjは既知のSboxテーブルであると仮定する。この仮定の下で、DPAにより拡大鍵Kの部分鍵kjを推定できることを示す。DPAは電力消費データの測定と、電力差分データを用いた鍵の解析という2段階から構成される。電力消費データの測定において、ある平文を与えたときに暗号プロセッサが消費する電力消費データは、オシロスコープ等を用いれば、図8に示すような電力消費曲線として測定される。平文の値を様々に変えながらこのような測定を繰り返し、十分な回数の測定データが得られた時点で測定を終了する。この一連の測定で得られた電力消費曲線の集合をGとする。次に電力消費曲線を用いた拡大鍵の解析について説明を行う。暗号処理内部で用いられている拡大鍵の部分鍵kjについて、kjk’jであるという仮定を立てる。mjwjが既知のため、このk’jの仮定に基づき、集合Gは以下のG0G1に示す2種類の集合に分類できる。そして、以下に示す電力差分曲線DGを作成する。DGもしこの仮定が正しい、すなわちk’j=kjである場合、図9上段に示すようなスパイクが現われる。もしこの仮定が誤り、すなわちk’j≠kjである場合、図9下段に示すようにスパイクが現れない平坦な曲線となる。よって、仮定したk’jから図9上段のような電力差分曲線が得られれば、拡大鍵の部分鍵kjを解読できたことになる。このようなkjの解読を各jについて行えば、最終的に図6における鍵Kの全てを解読することができる。拡大鍵K自身は、48bitや128bitの大きなビット長をもつため総当りによる解読が困難であるが、k’jkjはSbox入力に関連する鍵のビット長であり、高々8bitであるため、上記の手法による総当り解読は容易である。この解読を、全ての拡大鍵0拡大鍵1...拡大鍵Nについて繰り返すことで、秘密鍵を解読することができる。なおAESの場合、アルゴリズムの性質上、拡大鍵の先頭の値がそのまま秘密鍵の値であるため、秘密鍵が128bitならば拡大鍵0を、秘密鍵が192bitもしくは256bitならば拡大鍵0と拡大鍵1を解読すれば、秘密鍵全体を解読することができ、拡大鍵から秘密鍵の解読が容易である事が知られている。次に、k’jkjである場合、電力差分曲線DGにスパイクが現れる理由について説明する。k’jkjの場合、式および式に従いG0G1の分類を行うことで、zjに関して式が成立する。1一方、k’j≠kjの場合式は成立せず、ランダムな分類を行うことになるので式が成立する。0ただし、ハミングウェイトとは、ある値をビット値で表現したときにビット値’1’となる個数のことであり、例えばビット値2のハミングウェイトは3である。よって、式が成立する場合はG1とG0の間でのロード値zjの平均ハミングウェイトに差が生じるが、式が成立する場合はG1とG0の間でのロード値zjの平均ハミングウェイトに差が生じない。一般的に、消費電力はデータ値のハミングウェイトに比例すると考えられており、このことが正しいことを示した実験結果が非特許文献5などの文献にて示されている。従って、k’jkjである場合、式が満たされることで消費電力の差が電力差分曲線上のスパイクという形になって現れるが、式の場合はスパイクが現れず、平坦な曲線となる。以上の説明では、最も簡単な図6の構造に対するDPAに関して述べたが、このような手法は、図10に示すように、拡大鍵の前後に線形変換を挿入しても成立することが判明している。すなわち、図10は、共通鍵暗号の一般的な処理のアルゴリズムを示す図である。図10は、図6を一般化した構造であり、鍵XOR処理の前後に2つの線形変換処理L1L2を入れた処理構造である。例えば、L1は入力をそのまま出力する関数、L2をビット転置置換関数、wjをSC2000のB関数と呼ばれるSboxにすることで、図10はSC2000と等価な構造を表す。なお、SC2000の仕様については、非特許文献6に詳細が開示されている。L2はビット置換関数であるので、wjの入出力に関係するビットのみを取りだした構造を考えることで、図11と同一の処理に変換でき、前述と同様のDPAを用いることで、拡大鍵Kを解読することができる。以上の手法では、非線形処理中のSbox出力に注目してDPAを適用しているが、そのほかにも、入力mjと鍵kjとのXOR直後の値やSboxへの入力値xjの値に注目してDPAを適用する手法が知られている。上記を整理すると、次の条件を満たす場合にDPAにより秘密鍵が推定される。図11は、DPAによる秘密鍵推定が可能な条件の説明図である。DPA1:入力Mが既知かつ制御可能、拡大鍵Kは未知で固定、Sboxwjの変換が既知の場合、図11のAの部分の電力消費曲線を測定することでDPA可能。DPA2:入力Mが既知かつ制御可能、拡大鍵Kは未知で固定の場合、図11のBの部分の電力消費曲線を測定することでDPA可能。DPA3:入力Mが既知かつ制御可能、拡大鍵Kは未知で固定の場合、図11のCの部分の電力消費曲線を測定することでDPA可能。<一般的に考えられるDPA対策手法>一般的に考えられるDPA対策法としては、暗号処理に対策を施し消費電力をランダム化する手法が存在する。この手法の代表的なものとして、maskingmethodと呼ばれている手法が知られている。DPA対策なしの暗号処理において計算されるデータをMとすると、非特許文献8に記載されているDPA対策は、データMを計算する代わりに、で表されるデータM’Rを計算することで暗号処理を行う方法である。ただしRは乱数であり、暗号処理を実行する度に発生させる値である。この方法により、暗号処理のデータをランダムな値でマスクされる。よって、データがランダム化されることで消費電力もランダム化されるため、DPAに安全な処理を実現することができる。この方法の問題点は、M’Rの両方を計算する必要があるため、対策なしの回路の2倍の回路規模を必要とすることである。AESにおける非特許文献8の応用事例として、図12のDPA未対策回路に対し、上記一般的に考えられる手法1を適用したAES回路を図13に示す。この回路においては、図12で計算しているデータMiの代わりに、乱数Riに対してを満たすMi’とRiの2つのランダムなデータを計算する。暗号化処理ごとに計算されるデータ値がランダムであるため、DPAに対して安全な処理を実現することができる。ただし、データをMi’とRiの両方について計算しなくてはならないため、回路規模が増大する。。図12ではAESのSubbyte処理を、固定データによる静的なSbox変換テーブルSxを用いたテーブル参照処理によって行う。Subbyte処理で用いられる変換テーブルSxは、Sboxと呼ばれる。これに対して、図13で用いられるSboxのテーブルデータS’xは、乱数RinRoutに応じてに従ったS’xを、x01255それぞれに対して作成する必要がある。このように一般的に考えられる手法1による対策法を、認証チップの共通鍵暗号回路に搭載することで、サイドチャネル攻撃に対する防御を実現できる。しかし、DPA対策無しの回路と比較して、回路規模が大きいという問題が発生する。そこで、以下の各実施形態は、前述した一般的に考えられる手法1に示されるような専用の対策つき暗号回路を用いる代わりに、暗号より上位層の認証プロトコルへの改良によりサイドチャネル攻撃に安全な処理を実現する。暗号回路そのものは、未対策の回路をそのまま用いるため、前述した一般的に考えられる手法1が有する問題点を回避する。認証プロトコルは、乱数を伴う処理であるため、この乱数を適切に利用することで、サイドチャネル攻撃に対して安全となる方法が考えられる。すなわち、一般的なチャレンジアンドレスポンス認証では、前述した図2~5に示されるように、固定の秘密鍵Kに対する暗号化処理が行われるが、これはサイドチャネル攻撃に対して脆弱な条件である。この欠点は、乱数を用いて秘密鍵をマスク化することで一見克服できそうであるが、発明者の分析によればこの方法もサイドチャネル攻撃に対して脆弱であることが判明した。以下、基本概念1、基本概念2に基づく各実施形態について説明する前に、乱数を用いた単純な秘密鍵のランダム化法について説明する。そして、発明者の分析によりその方法が安全でないことを示したうえで、その問題点を克服した各実施形態について説明する。<単純な秘密鍵のランダム化>図14は、単純な鍵のランダム化による認証プロトコルの例1の機能ブロック図である。これは、図2をベースとしており、片側認証かつ暗号化復号の両方を利用する認証プロトコルである。親機101側で生成した乱数rを子機102に送信し、子機102はこの乱数rと秘密鍵Kによる暗号化処理を行ことでレスポンスaを生成する。このレスポンスa生成の際、のように、鍵を乱数rでマスクした上で生成する。親機101に送信されたレスポンスは、親機101側でにより復号され、r’がrと一致するか確認する。鍵Kをランダム化することで、サイドチャネル攻撃に一見安全そうであるが、脆弱であると結論付けられる。なぜなら、乱数rは親機101と子機102の間で共有するために送信される値であり、外部から容易に観察可能であるため、この観察された値を用いて、前述した式および式に示される部分鍵kj’を、攻撃者が推定した部分鍵に乱数rをXORされた値に置き換えることで、通常のサイドチャネル攻撃と同じ手順で鍵を解読できるからである。同じ問題は、図14をさらに拡張した図15で発生する。図15は、単純な鍵のランダム化による認証プロトコルの例2の機能ブロック図である。この図15は、鍵をXORマスクする乱数rが外部から観察可能であるため脆弱であった図14の問題を解消するために、鍵をマスクする乱数の作成方法を変更し、rの代わりにを生成し、このmrを用いて秘密鍵Kをマスク化することでレスポンスを生成する。mrが外部から観察できない値であるので、レスポンス生成がサイドチャネル攻撃に対して安全そうに見えるが、レスポンス生成の前段階の処理であり、mrを生成するときの処理の消費電力を測定することで、図14と同様の手法により秘密鍵Kを解読することができる。図14、図15の事例に示されるように、乱数を用いて鍵を単純にランダム化する手法だけでは、サイドチャネル攻撃に対して安全な認証プロトコルを実現することができない。以下の各実施形態はこの問題を解決し、対策つきの専用回路を用いなくともサイドチャネル攻撃に対して安全な認証プロトコルを実現する方式を示す。各実施形態について説明する前に、なぜ乱数を用いて鍵を単純にランダム化する手法だけでは安全でないかの理由を説明する。図16に、AES暗号回路を事例として、サイドチャネル攻撃が成功する要因の図を示す。128bitの拡大鍵Kが、128bit平文とXORされた後、8bitごとに16分割され、それぞれのデータがSboxに入力される。攻撃者は、それぞれのSboxの消費電力データを利用することで、8bitごとに分割された拡大鍵Kk15...k0に対し、8bit部分鍵kjそれぞれの総当りを前述の式および式に従い実行する。つまり、128bitの鍵の総当りには本来2128の手間が必要であるのに対し、サイドチャネル攻撃を用いることで28の手間を16回28×16212に減らすことができる。すなわち、サイドチャネル攻撃に必要な手間は、Sboxの入力に関連した部分鍵のビット長によって決定する。このビット長は共通鍵暗号方式によって変動するが、既に説明したとおりAESの8bitが最大である。つまりSbox入力の部分鍵ビット長が最も長いAESに対しても図16の考えに基づいた攻撃が成功するならば、その他の共通鍵暗号ではさらに容易に成功することになる。これは、図17に示すように、チャレンジアンドレスポンスの乱数で鍵をマスク化した場合でも同じである。鍵をマスク化した乱数が外部から観察可能であるので、乱数による鍵のマスク化の有無に関係なく、Sboxの入力に関連する部分鍵のビット長の総当りにより、鍵を解読することができる。<実施形態の基本概念>以上説明したように、チャレンジアンドレスポンスで用いる乱数をそのまま秘密鍵のマスクに用いても、サイドチャネル攻撃に対して安全な処理を実現することができない。この問題を克服するために、以下の各実施形態では、単純な秘密鍵のランダム化を行う代わりに、以下の3段階の手順を実行する。秘密鍵を複数個準備し乱数を用いて1つの鍵に圧縮しで圧縮された鍵を、従来の認証プロトコルで用いられる秘密鍵Kの代わりに使用単純なランダム化を実行する代わりに、に示されるようなランダムな鍵圧縮を実行することで、サイドチャネル攻撃に対する安全性と、小規模高速な暗号処理を両立することができる。さらに、に示す乱数は、認証を行う側で生成した乱数のみならず、認証される側で生成した乱数を利用することで、さらに安全性を高めることができる。基本概念1、基本概念2に共通する基本アイデアを図18に示す。図18に示される通り、この基本アイデアでは、鍵を複数個準備し、それらを乱数を用いて1つに圧縮する。以下、乱数を用いて鍵を圧縮する処理をランダムな鍵圧縮と呼び、圧縮された鍵を圧縮鍵と呼ぶ。このアイデアは、チャレンジアンドレスポンス認証で用いる乱数は外部から観察されることは不回避であるという前提に基づくものであり、乱数が観察されたとしても、サイドチャネル攻撃における攻撃者の手間を増やすことが狙いである。ランダムな鍵圧縮は、以下の2条件を満たすものとする。n個の鍵と乱数の値が分かれば、圧縮鍵の値も分かる乱数とn個の鍵が全て分からない限り、圧縮鍵の値は分からない。サイドチャネル攻撃においては、Sboxの入力する部分鍵のビット値が全て確定しないと、前述した式および式に示す攻撃を実施することはできない。この部分鍵は、図18の圧縮鍵に相当する値である。しかし、上記のにより、全ての圧縮鍵のビット値を確定するためには、乱数が外部に観察されたとしても、n個の部分鍵全ての値がわからない限り不可能となる。つまり、サイドチャネル攻撃を成功させるためには、一般的には一つの部分鍵に関する総当りを実施すればよかったのに対し、ランダムな鍵圧縮を用いることで、n個の部分鍵全てに関する総当りを実施する必要がある。例えばAESの場合、一般的に考えられる手法ならば28の手間で解読できたのに対し、ランダムな鍵圧縮を用いることでnの手間となる。例えばn8の場合264の手間となる。サイドチャネル攻撃における264は、現実的に不可能な計算量であるため、安全となる。基本概念1は、ランダム鍵圧縮に用いる乱数として、チャレンジアンドレスポンスに用いる乱数をそのまま利用していた。チャレンジアンドレスポンスにおいては、暗号処理により応答を生成する機器と、応答生成に必要な乱数を生成するのは別の機器である。つまり、暗号処理を行う機器とは別の機器により乱数生成が行われる。もし、乱数生成をする側が不正行為を行い、常に変化すべき乱数を固定値として与えた場合、圧縮鍵が常に固定値となるため、攻撃に必要な手間が従来法と同じとなり、サイドチャネル攻撃を防ぐことができない。この攻撃を防ぐためには、応答を生成する側の機器から外部から受け取る乱数rに加えて、応答を生成する側の機器でも別の乱数sを生成し、これら2つの乱数rsを用いて鍵圧縮を行うことである。これは基本概念2のアイデアであり、概要は図19に示される。認証機器は、認証プロトコルの通信相手から乱数rを受け取り、さらに自分自身でも乱数sを生成する。鍵圧縮処理はrとsの2つの乱数を用いて行うことで、外部入力乱数rが意図的に固定化された場合でも、内部生成された乱数sがランダムに変化することで、圧縮鍵が固定化されることを防ぎ、サイドチャネル攻撃に対する安全性を実現する。内部生成された乱数sは、外部出力され通信相手の認証機器に送信される。なぜなら、通信相手の機器も同じ圧縮鍵を生成する必要があるためであり、通信相手の機器は、自分自身が送信した乱数rと受け取ったsを元に、同じ圧縮鍵を生成する。基本概念12を、チャレンジアンド認証プロトコルに応用した認証プロトコルに関する第1から第8の実施形態を図20から図27に示す。図20,図21,図22,図23は、それぞれ基本概念1を図2,図3,図4,図5の認証プロトコルに応用したものである。また、図24,図25,図26,図27は、それぞれ基本概念2を図2,図3,図4,図5の認証プロトコルに応用したものである。図20から図27の全てにおいて、親機101と子機102はn個の鍵K1K2...Knを事前共有するものとする。図20,図21,図22,図23に示す基本概念1を用いた認証プロトコルは、基本的には図2,図3,図4,図5に示す認証プロトコルと同じである。図20,図21,図22,図23において、図2,図3,図4,図5の場合と同じ処理には、同じステップ番号を付してある。図20,図21,図22,図23が、図2,図3,図4,図5と異なる点は、親機101側で生成した乱数rと、n個の鍵K1K2...Knを用いて、圧縮鍵Kcmpを生成し、この鍵を用いて暗号化処理を行う点である。子機102側では、図20のS2001、図21のS2101、図22のS2201、図23のS2301の各処理である。親機101側では、図20のS2002、図21のS2102、図22のS2202、図23のS2302の各処理である。図20,図21,図22,図23において、これらの鍵圧縮処理はKcmpCompressと表現されており、圧縮処理を行うCompress関数はさまざまな実装形態が存在する。Compress関数の具体的な構成については、後述する。図24,図25,図26,図27に示す基本概念2を用いた認証プロトコルは、基本的には図2,図3,図4,図5に示すプロトコルと同じである。図24,図25,図26,図27において、図2,図3,図4,図5の場合と同じ処理には、同じステップ番号を付してある。図24,図25,図26,図27が、図2,図3,図4,図5と異なる第一の相違点は、図2,図3では行っていなかった、子機102側の乱数sの生成処理が図24,図25で実行されている点である。図24のS2401、図25のS2501の各処理である。第二の相違点は、親機101側で生成した乱数rと、子機102側で生成した乱数s、およびn個の鍵K1K2...Knを用いて、圧縮鍵Kcmpを生成し、この鍵を用いて暗号化処理を行う点である。子機102側では、図24のS2402、図25のS2502、図26のS2601、図27のS2701の各処理である。親機101側では、図24のS2403、図25のS2503、図26のS2602、図27のS2702の各処理である。図24,図25,図26,図27において、これらの鍵圧縮処理はKcmpCompress2と表現されており、圧縮処理を行うCompress2関数はさまざまな実装形態が存在する。Compress2関数の具体的な構成については、後述する。<Compress関数の基本構造>基本概念1の鍵圧縮に用いられるCompress関数の基本構造を図28に示す。n個の鍵K1Knがそれぞれubitである。n個のubit鍵それぞれは、結線を用いたビット分割によりt個のgbitブロックに分割される。鍵圧縮は、ブロック単位での実行をt回繰り返すことで実行される。すなわち、n個の鍵K1Knの1番目のブロックであるn個のgbit値に対して、圧縮化回路2803で鍵圧縮処理を行った結果のgbit値が、圧縮鍵Kcmpの1番目のkbitブロック値となる。同様の処理を2番目からt番目のブロックについて繰り返すことで、圧縮鍵Kcmpの全てのブロック値が決定される。入力値のブロックの選択にはセレクタ2801が、出力値のブロックの選択にはデマルチプレクサ2804が用いられる。圧縮化回路2803でのそれぞれのブロックの鍵圧縮処理においては、第一の乱数rによりn個のランダム化回路2802でランダム化処理が行われた結果、それぞれhbitの中間出力値L1Lnを得る。ランダム化回路2802でのランダム化処理としては、さまざまな演算が適用可能である。回路規模が小さな演算としては、乱数と鍵の単純なビット結合乱数ビット値に応じた鍵の巡回シフト乱数ビット値に応じて鍵に対する巡回シフトレジスタ処理の実行乱数と鍵のXOR乱数と鍵のgbit加算減算乱数と鍵のGF上の乗算が挙げられる。これらの演算を用いることで、乱数と鍵の全てのビットが、演算結果Liの値に対して影響を及ぼす。次に、中間出力値L1Lnに対して、圧縮化回路2803圧縮処理を行うことで、gbitの圧縮鍵Kcmpを出力する。この圧縮処理は、L1Lnの全てのビットがKcmpに影響を及ぼす関数であれば、様々な演算が適用可能である。回路規模が小さな演算としては、全ての値のXOR全ての値のgbit加算全ての値をXOR後、GFの剰余演算全ての値を加算後、GFの剰余演算全ての値をビット結合後、GFの剰余演算が挙げられる。これらの処理を用いることで、L1Lnの全てのビットがKcmpに影響を及ぼす。以上の2段階の処理を経ることで、前述した図18および図19の基本概念12の説明で示したが満たされた、ランダム鍵圧縮処理を実現できる。なぜなら、入力から一意に出力が決定されることで、が満たされ、また入力の全てのビットが出力に影響することで、が満たされるからである。基本概念2の鍵圧縮に用いられるCompress2関数の基本構造を図29に示す。基本的には図28と同じ構造である。図29において、図28の場合と同じ機能を実行する部分には同じ番号を付してある。図29が図28と異なる点は、第一の乱数rと第二の乱数sを入力することと、これらの乱数を乱数合成回路2901により1つの乱数に変換したうえで利用する点である。乱数合成回路2901は、第一の乱数rと第二の乱数sの全てのビット情報が出力に反映されるならば、様々な演算が適用可能である。回路規模が小さな演算としては、2つの乱数のXOR2つの乱数のqbit加算減算が挙げられる。ただし、qは乱数のビット長である。図28,図29のランダム化回路2802圧縮回路2803乱数合成回路2901として用いる回路によって、様々な実施例が存在する。具体例については、後述する。以下に説明する鍵圧縮回路の第1から第8の実施例は、図28、図29のランダム化回路2802圧縮回路2803乱数合成回路2901として用いる回路に関するものである。それぞれの実施例で用いられる回路の組み合わせは以下の通りである。基本概念1を用いた実施例第1の実施例ランダム化回路2802:乱数ビット値に応じた鍵の巡回シフト圧縮化回路2803:全ての値のXOR第2の実施例ランダム化回路2802:乱数と鍵の単純なビット結合圧縮回路2803:全ての値をXOR後、GFの剰余演算第3の実施例ランダム化回路2802:乱数ビット値に応じて鍵に対するLFSR処理の実行圧縮回路2803:全ての値のXOR第4の実施例ランダム化回路2802:乱数と鍵のGF上の乗算圧縮回路2803:全ての値をXOR後、GFの剰余演算基本概念2を用いた実施例第5の実施例ランダム化回路2802:乱数ビット値に応じた鍵の巡回シフト圧縮化回路2803:全ての値のXOR乱数合成回路2901:2つの乱数のXOR第6の実施例ランダム化回路2802:乱数と鍵の単純なビット結合圧縮回路2803:全ての値をXOR後、GFの剰余演算乱数合成回路2901:2つの乱数のqbit加算第7の実施例ランダム化回路2802:乱数ビット値に応じて鍵に対するLFSR処理の実行圧縮回路2803:全ての値をXOR後、GFの剰余演算乱数合成回路2901:2つの乱数のXOR第8の実施例ランダム化回路2802:乱数と鍵のGF上の乗算圧縮回路2803:全ての値をXOR後、GFの剰余演算乱数合成回路2901:2つの乱数のXOR上記第1から第8の全ての実施例においては、128bit共通鍵ブロック暗号において128bit鍵を用いていると仮定する。すなわち、秘密鍵K1...Knのそれぞれは128bitであり、乱数rsは最大128bitであるとする。全てのrsのビットを鍵圧縮に用いる必要はない。上記第1から第8のいずれの実施例も、必要な追加回路の回路規模を48Kgateから87Kgateと小さく抑えることができ、暗号回路規模を2倍以上大きくする一般的に考えられる手法1より優れた効果を発揮する。例えば、下記文献に記されるサイドチャネル攻撃対策なしのAES回路は、176Kgateを必要とするため、この回路が2倍化される構成と比較して、第1から第8の実施例は優れた効果を発揮する。<実施例1>図30は、鍵圧縮回路の第1の実施例を示す図である。図30において、図28の基本構造図の場合と同じ機能を有する部分には同じ番号を付してある。128bit秘密鍵Kiのそれぞれは、16bitごとに8分割され、それぞれKi7...Ki0と表記される。4つのKiそれぞれは、外部から入力されるセレクト信号に従い、セレクタ2801により、8分割された16bit部分鍵のいずれかをセレクトする。セレクトされた4つの16bit部分鍵それぞれに対して、16bit乱数を4分割した4bit乱数に基づき、ランダム化回路2802である巡回シフト回路群により、巡回シフト処理が行われる。巡回シフトは16通りであるため、乱数は4bitで十分である。4つの16bit巡回シフト回路の出力は、圧縮化回路2803であるXORにてXORされることで1つの16bit値を生成する。この16bit値は、圧縮鍵Kcmpの16bit部分鍵Kcmpjである。ただし、Kcmpjは、下位ビットから数えてj番目の部分鍵を表す。セレクト信号を、8分割された部分鍵それぞれについて切り替えることで、デマルチプレクサ2804にて、j01...7全ての圧縮鍵を生成する。圧縮された部分鍵は、4つの16bit部分鍵の全てのビット情報を含みながら圧縮されるので、乱数が外部に観察されたとしても、4264の手間が攻撃者にとって必要となるため、安全である。上述の鍵圧縮回路の第1の実施例の回路規模の見積もりについて、以下に説明する。図31は、鍵圧縮回路の実施例の回路規模見積もり基準の表を示す図である。図31の表は、1bitあたりの回路規模を示したものである。ここでは、回路規模を、2入力NAND換算ゲート数として示している。図32および図33は、回路規模の算定基準となるNANDゲートおよびNORゲートの回路規模見積を示す図である。図32および図33のように、2入力NANDゲートおよび2入力NORゲートのいずれも、4つのMOSFETによって1ゲートが構成されている。図34は、NOTゲートの回路規模見積を示す図である。NOTゲートは、図34に示されるように2つのMOSFETから構成されるため、図31に示されるように、ゲート数は05ゲートとなる。図35は、1入力Dフリップフロップによって構成されるレジスタの回路規模見積を示す図である。レジスタは、図35に示されるように、4つのNANDゲートと、1つのNORゲートと、4つのNOTゲートと、それぞれ1ゲートからなる4個のゲート単位とから構成される。このため、図31に示されるように、レジスタのゲート数は、14110541411ゲートとなる。図36は、2入力XORの回路規模見積を示す図である。XORは、図36に示されるように、2つのNORゲートと、1つのNANDゲートと、1つのNOTゲートとから構成される。このため、図31に示されるように、XORのゲート数は、121105135ゲートとなる。図37は、21セレクタの回路規模見積を示す図である。図37はマルチプレクサ、図37はデマルチプレクサである。マルチプレクサは、図37に示されるように、3つのNANDゲートと、1つのNOTゲートとから構成される。このため、図31に示されるように、21セレクタのゲート数は、1305135ゲートとなる。また、デマルチプレクサは、図37に示されるように、2つのNANDゲートと3つのNOTゲートとから構成される。このため、図31に示されるように、21セレクタのゲート数はやはり、1205335ゲートとなる。図38は、加減算器の回路規模見積を示す図である。加減算器は、図38に示されるように、1つの3入力XORゲートと、4つの3入力NANDゲートとから構成される。このため、図31に示されるように、加減算器のゲート数は、712415ゲートとなる。図39は、シフト/巡回レジスタの回路規模見積を示す図である。シフト/巡回レジスタは、図39に示されるように、1つのセレクタと、1つのレジスタとから構成されると、1つのレジスタと、ビット位置に対応して0または1個のXORゲートとから構成される、16bitシフトレジスタならば145×16232gateと見積もられる。さらに、図31は、2入力1出力の演算回路の規模を表すが、これはm入力1出力となった場合は、2入力1出力の演算回路の倍の回路規模である。例えば、10bit21XOR回路は35×1035gateであるが、10bit41XOR回路は回路規模が3倍となり3×35×10105gateである。20bit41加算器の場合、×3900gateとなる。図41は、図31に示される見積もり基準に基づいて計算される、図30に示される鍵圧縮回路の第1の実施例の回路規模の見積表を示す図である。ただし、図30において、Kcmpを出力するレジスタは、暗号回路のレジスタと共用するため、評価に含まれない。図41に示されるように、図30において、鍵レジスタ部分が56Kgate、セレクタ2801の部分が16Kgate、ランダム化回路2802である巡回シフトレジスタ部分が093Kgateである。さらに、図30において、圧縮化回路2803である41XORの部分が01Kgate、デマルチプレクサ2804の部分が04Kgateである。この結果、図30の鍵圧縮回路全体の回路規模は、86Kgateとなり、従来の半分程度の回路規模で実現できることがわかる。<実施例2>図42は、鍵圧縮回路の第2の実施例を示す図である。図42において、図28の基本構造図の場合と同じ機能を有する部分には同じ番号を付してある。128bit秘密鍵Kiのそれぞれは、32bitごとに4分割され、それぞれKi3...Ki0と表記される。2つのKiそれぞれは、外部から入力されるセレクト信号に従い、セレクタ2801が、4分割された32bit部分鍵のいずれかをセレクトする。次に、ランダム化回路2802において、セレクトされた2つの32bit部分鍵それぞれに対して、32bit乱数を2分割した16bit乱数がビット結合される。さらに、圧縮化回路2803の構成として、ランダム化回路2802でのビット結合結果の2つの48bit値がXORされ、このXOR結果に対してGFの剰余演算の剰余回路が実行される。GFの剰余演算は、例えばCRC符号で用いられる多項式、x32x28x27x26x25x23x22x20x19x18x14x13x11x10x9x8x61による剰余演算が適切である。剰余演算の結果の32bitは、圧縮鍵Kcmpの32bit部分鍵Kcmpjである。ただし、Kcmpjは、下位ビットから数えてj番目の部分鍵を表す。セレクト信号を、4分割された部分鍵それぞれについて切り替えることで、デマルチプレクサ2804が、j01...3全ての圧縮鍵を生成する。圧縮された部分鍵は、2つの32bit部分鍵の全てのビット情報を含みながら圧縮されるので、乱数が外部に観察されたとしても、2264の手間が攻撃者にとって必要となるため、安全である。図43は、図31に示される見積もり基準に基づいて計算される、図42に示される鍵圧縮回路の第2の実施例の回路規模の見積表を示す図である。ただし、Kcmpを出力するレジスタは、暗号回路のレジスタと共用するため、評価に含まれない。図43に示されるように、図42において、鍵レジスタ部分が28Kgate、セレクタ2801の部分が067Kgate、圧縮化回路2803の一部である21XORの部分が012Kgateである。さらに、圧縮化回路2803の一部であるGF剰余回路の部分が086Kgate、デマルチプレクサ2804の部分が034Kgateである。この結果、図42の鍵圧縮回路全体の回路規模は、48Kgateとなり、従来の半分程度の回路規模で実現できることがわかる。<実施例3>図43は、鍵圧縮回路の第3の実施例を示す図である。図43において、図28の基本構造図の場合と同じ機能を有する部分には同じ番号を付してある。128bit秘密鍵Kiのそれぞれは、32bitごとに4分割され、それぞれKi3...Ki0と表記される。2つのKiそれぞれは、外部から入力されるセレクト信号に従い、セレクタ2801が、4分割された32bit部分鍵のいずれかをセレクトする。次に、ランダム化回路2802である32bitLFSRが、セレクトされた2つの32bit部分鍵それぞれに対して、16bit乱数を2分割した8bit乱数ビット値で与えられるシフト量に従ったLFSR処理を実行する。LFSR処理で用いられる多項式は様々なものが知られているが、例えば、x32x7x5x3x2x1が利用可能である。次に、圧縮化回路2803であるXORにて、2つのLFSR処理結果をXORすることで、圧縮鍵Kcmpの32bit部分鍵Kcmpjを得る。ただし、Kcmpjは、下位ビットから数えてj番目の部分鍵を表す。セレクト信号を、4分割された部分鍵それぞれについて切り替えることで、デマルチプレクサ2804にて、j01...3全ての圧縮鍵を生成する。圧縮された部分鍵は、2つの32bit部分鍵の全てのビット情報を含みながら圧縮されるので、乱数が外部に観察されたとしても、2264の手間が攻撃者にとって必要となるため、安全である。図45は、図31に示される見積もり基準に基づいて計算される、図44に示される鍵圧縮回路の第3の実施例の回路規模の見積表を示す図である。。ただし、Kcmpを出力するレジスタは、暗号回路のレジスタと共用するため、評価に含まれない。図45に示されるように、図44において、鍵レジスタ部分が28Kgate、セレクタ2801の部分が067Kgate、ランダム化回路2802であるLFSRの部分が115Kgateである。さらに、圧縮化回路2803である21XORの部分が01Kgate、デマルチプレクサ2804の部分が034Kgateである。この結果、図44の鍵圧縮回路全体の回路規模は、50Kgateとなり、従来の半分程度の回路規模で実現できることがわかる。<実施例4>図46は、鍵圧縮回路の第4の実施例を示す図である。図46において、図28の基本構造図の場合と同じ機能を有する部分には同じ番号を付してある。128bit秘密鍵Kiのそれぞれは、32bitごとに4分割され、それぞれKi3...Ki0と表記される。2つのKiそれぞれは、外部から入力されるセレクト信号に従い、セレクタ2801が、4分割された32bit部分鍵のいずれかをセレクトする。次に、ランダム化回路2802において、セレクトされた2つの32bit部分鍵それぞれに対して、64bit乱数を2分割した32bit乱数ビット値同士の多項式乗算を行い、2つの64bit値を生成する。多項式乗算をと記した場合、多項式乗算は、乗数aを格納するシフトレジスタ1個と、被乗数bを格納するレジスタ1個と、32bitXOR回路1個により実現できる。さらに、圧縮化回路2803の構成として、ランダム化回路2802での乗算の結果の2つの64bitがXOR演算される。このXOR結果に対してGFの剰余演算の剰余回路が実行される。GFの剰余演算は、例えばCRC符号で用いられる多項式、x32x28x27x26x25x23x22x20x19x18x14x13x11x10x9x8x61による剰余演算が適切である。剰余結果の32bit値により、圧縮鍵Kcmpの32bit部分鍵Kcmpjを得る。ただし、Kcmpjは、下位ビットから数えてj番目の部分鍵を表す。セレクト信号を、4分割された部分鍵それぞれについて切り替えることで、デマルチプレクサ2804が、j01...3全ての圧縮鍵を生成する。圧縮された部分鍵は、2つの32bit部分鍵の全てのビット情報を含みながら圧縮されるので、乱数が外部に観察されたとしても、2264の手間が攻撃者にとって必要となるため、安全である。図47は、図31に示される見積もり基準に基づいて計算される、図46に示される鍵圧縮回路の第4の実施例の回路規模の見積表を示す図である。ただし、Kcmpを出力するレジスタは、暗号回路のレジスタと共用するため、評価に含まれない。図47に示されるように、図46において、鍵レジスタ部分が28Kgate、セレクタ2801の部分が067Kgate、ランダム化回路2802である多項式乗算器の一部を構成するシフトレジスタの部分が093Kgateである。同じく上記多項式乗算器の一部を構成するレジスタの部分が07Kgate、同じく上記多項式乗算器の一部を構成する21XORの部分が02Kgateである。また、圧縮化回路2803の一部である21XORの部分が012Kgateであり、圧縮化回路2803の一部であるGF剰余回路の部分が115Kgate、デマルチプレクサ2804の部分が034Kgateである。この結果、図46の鍵圧縮回路全体の回路規模は、70Kgateとなり、従来の半分程度の回路規模で実現できることがわかる。<実施例5>図48は、鍵圧縮回路の第5の実施例を示す図である。図48において、図29の基本構造図の場合と同じ機能を有する部分には同じ番号を付してある。図48の構成は、基本的には図30の第1の実施例の場合と同じであるが、2つの16bit乱数rsを乱数合成回路2901であるXORにより合成した結果の16bit値を、ランダム化圧縮の乱数として用いるところが異なる。圧縮された部分鍵は、4つの16bit部分鍵の全てのビット情報を含みながら圧縮されるので、乱数が外部に観察されたとしても、4264の手間が攻撃者にとって必要となるため、安全である。図49は、図31に示される見積もり基準に基づいて計算される、図48に示される鍵圧縮回路の第5の実施例の回路規模の見積表を示す図である。乱数圧縮回路2901の分だけゲート数が増加しているほかは、図41に示される実施例1の場合と同じである。<実施例6>図50は、鍵圧縮回路の第6の実施例を示す図である。図50において、図29の基本構造図の場合と同じ機能を有する部分には同じ番号を付してある。2つの乱数の合成に乱数合成回路2901である加算器2901による加算を用いるほかは、図42に示される第2の実施例の場合と同じである。圧縮された部分鍵は、2つの32bit部分鍵の全てのビット情報を含みながら圧縮されるので、乱数が外部に観察されたとしても、2264の手間が攻撃者にとって必要となるため、安全である。図51は、図31に示される見積もり基準に基づいて計算される、図50に示される鍵圧縮回路の第6の実施例の回路規模の見積表を示す図である。乱数圧縮回路2901の分だけゲート数が増加しているほかは、図43に示される実施例2の場合と同じである。<実施例7>図52は、鍵圧縮回路の第7の実施例を示す図である。図52において、図29の基本構造図の場合と同じ機能を有する部分には同じ番号を付してある。2つの乱数の合成に乱数合成回路2901であるXORを用いるほかは、図44に示される第3の実施例の場合と同じである。圧縮された部分鍵は、2つの32bit部分鍵の全てのビット情報を含みながら圧縮されるので、乱数が外部に観察されたとしても、2264の手間が攻撃者にとって必要となるため、安全である。図53は、図31に示される見積もり基準に基づいて計算される、図52に示される鍵圧縮回路の第7の実施例の回路規模の見積表を示す図である。乱数圧縮回路2901の分だけ増加しているほかは、図45に示される第3の実施例の場合と同じである。<実施例8>図54は、鍵圧縮回路の第8の実施例を示す図である。図54において、図29の基本構造図の場合と同じ機能を有する部分には同じ番号を付してある。2つの乱数の合成に乱数合成回路2901であるXORを用いるほかは、図46に示される第4の実施例の場合と同じである。圧縮された部分鍵は、2つの32bit部分鍵の全てのビット情報を含みながら圧縮されるので、乱数が外部に観察されたとしても、2264の手間が攻撃者にとって必要となるため、安全である。図55は、図31に示される見積もり基準に基づいて計算される、図54に示される鍵圧縮回路の第8の実施例の回路規模の見積表を示す図である。乱数圧縮回路2901の分だけ増加しているほかは、図47に示される第4の実施例の場合と同じである。以上説明したように、各実施形態を用いることで、一般的に考えられる手法1のように、回路を2倍化することなく、小さい回路規模増ながらも、サイドチャネル攻撃に安全な暗号処理および認証処理を実現することが可能となる。なお、上述の基本概念12に基づく処理は、認証処理のみならず、暗号処理一般にも適用することが可能である。図56は、上記システムをソフトウェア処理として実現できるコンピュータのハードウェア構成の一例を示す図である。図56に示されるコンピュータは、CPU5601、メモリ5602、入力装置5603、出力装置5604、外部記憶装置5605、可搬記録媒体5609が挿入される可搬記録媒体駆動装置5606、及び通信インタフェース5607を有し、これらがバス5608によって相互に接続された構成を有する。同図に示される構成は上記システムを実現できるコンピュータの一例であり、そのようなコンピュータはこの構成に限定されるものではない。CPU5601は、当該コンピュータ全体の制御を行う。メモリ5602は、プログラムの実行、データ更新等の際に、外部記憶装置5605に記憶されているプログラム又はデータを一時的に格納するRAM等のメモリである。CUP5601は、プログラムをメモリ5602に読み出して実行することにより、全体の制御を行う。入出力装置5603は、ユーザによるキーボードやマウス等による入力操作を検出し、その検出結果をCPU5601に通知し、CPU5601の制御によって送られてくるデータを表示装置や印刷装置に出力する。外部記憶装置5605は、例えばハードディスク記憶装置である。主に各種データやプログラムの保存に用いられる。可搬記録媒体駆動装置5606は、光ディスクやSDRAM、コンパクトフラッシュ登録商標等の可搬記録媒体5609を収容するもので、外部記憶装置5605の補助の役割を有する。通信インターフェース5607は、例えばLAN又はWANの通信回線を接続するための装置である。上述した第1~第8の実施形態によるシステムは、それらの機能を搭載したプログラムをCPU5601が実行することで実現される。そのプログラムは、例えば外部記憶装置5605や可搬記録媒体5609に記録して配布してもよく、或いはネットワーク接続装置5607によりネットワークから取得できるようにしてもよい。以上のようにして実行されるプログラムにより、小さい処理量増ながらも、サイドチャネル攻撃に安全な暗号処理および認証処理を実現することが可能となる。"