(57)【要約】ＩＣチップの消費電力の変化から秘密情報を取り出すことを困難にして耐タンパー性を高める際に、計算量の肥大化を回避して処理を高速化する。ＩＣチップの内部で実行される冪乗剰余計算や楕円曲線上の点のスカラー倍計算を行うにあたって、データを乱数に基づいてブラインド化し、計算終了後にアンブラインド化するが、ブラインドに用いるデータが計算の繰り返しを通じて一定となるように、ブラインドの方式を変更する。このことにより、アンブラインド時の計算量を少なくすることができる。
2004047052.tif 000002
【特許請求の範囲】
【請求項１】
信号を入力する信号入力部と、処理プログラムを格納すると共に、処理中のデータを格納する格納部と、乱数の信号を発生する乱数発生装置と、上記処理プログラムに従って、上記信号入力部より入力された信号に対して所定のデータ処理を行なう演算部と、処理結果の信号を出力する信号出力部とを有し、
前記格納部に格納された処理プログラムは、所望の演算を＃で表したときの信号Ａと信号Ｂとを以って行なう演算Ａ＃Ｂに関わり、与えられた整数列Ｘ［ｈ］，Ｘ［ｈ−１］，…，Ｘ［ｋ］，…，Ｘ［１］（但し、ｈは整数）を対象にするプログラムであり、
該処理プログラムは、上記演算部に、
ｋ＝ｈとする第１の手順と、
前記乱数発生装置が発生する乱数の信号に基づいて信号Ｗを定める第２の手順と、
Ｌ＝Ｗとして、Ｌの格納部にＷを格納する第３の手順と、
Ｌ＃Ｌを計算し、再びＬの格納部に書き戻す操作をＪ回（但し、Ｊは負でない整数）実行する第４の手順と、
Ｘ［ｋ］とＷに基づいて一意的に決まる信号Ｂ［ｋ］＃Ｗ＾（（２＾Ｊ）−１）に対して、Ｌ＃Ｂ［ｋ］＃Ｗ＾（（２＾Ｊ）−１）を計算し、再びＬの格納部に書き戻す操作を実行する第５の手順と、
ｋから１を減ずる第６の手順と、
ｋ＞０ならば第４の手順に戻り、ｋ＝０であれば処理結果Ｔを出力する第７の手順と、
上記処理結果Ｔに対して、Ｔ＃Ｗ＾（−１）を出力結果Ｓとする第８の手順とを実行させることを特徴とする情報処理装置。
【請求項２】
上記演算Ａ＃Ｂが剰余乗算の整数演算＃である、
Ａ＃Ｂ＝Ａ＊Ｂ  ｍｏｄ  Ｎ
であり、上記ＷがＮと互いに素な整数であることを特徴とする請求の範囲第１項に記載の情報処理装置。
【請求項３】
上記演算部は、中央処理装置とコプロセッサからなり、該コプロセッサが上記演算Ａ＊Ｂ  ｍｏｄ  Ｎを実行することを特徴とする請求の範囲第２項に記載の情報処理装置。
【請求項４】
上記Ｗのビット数が８，１６，３２，６４のいずれかであることを特徴とする請求の範囲第２項に記載の情報処理装置。
【請求項５】
上記演算Ａ＃Ｂが有限体上で定義された代数曲線Ｅ上のモーデル・ヴェイユ群の和演算であることを特徴とする請求の範囲第１項に記載の情報処理装置。
【請求項６】
上記モーデル・ヴェイユ群による有限群が素体ＧＦ（Ｐ）（Ｐは素数）であることを特徴とする請求の範囲第５項に記載の情報処理装置。
【請求項７】
上記モーデル・ヴェイユ群による有限群がガロア標数２のガロア体ＧＦ（２＾ｎ）（ｎは正の整数）であることを特徴とする請求の範囲第５項に記載の情報処理装置。
【請求項８】
請求の範囲第２項に記載の情報処理装置を実装してなることを特徴とするＩＣカード。
【請求項９】
請求の範囲第５項に記載の情報処理装置を実装してなることを特徴とするＩＣカード。
【請求項１０】
ＧＳＭモバイルホンにおけるＳＩＭモジュールあって、請求の範囲第２項に記載の情報処理装置を実装してなることを特徴とするＳＩＭモジュール。
【請求項１１】
ＧＳＭモバイルホンにおけるＳＩＭモジュールであって、請求の範囲第５項に記載の情報処理装置を実装してなることを特徴とするＳＩＭモジュール。
【発明の詳細な説明】
【技術分野】  本発明は、暗号を用いて情報の安全性及び信頼性を確保する技術に係り、特に暗号への攻撃を防ぐ耐タンパー情報処理装置に関する。
【背景技術】  現在、市場が拡大しつつあるＩＣ（Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）カードや、ヨーロッパで広く利用されているＧＳＭ（Ｇｌｏｂａｌ  Ｓｙｓｔｅｍｓ  ｆｏｒ  Ｍｏｂｉｌｅ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ）規格のモバイルホンは、利用者認証や、電子商取引を行なうことができる携帯端末である。更にＩＣカードは、特に信頼性や安全性が重視される電子マネーとしても利用される。一方、ＧＳＭモバイルホンでは、同様の利用のためのＳＩＭ（Ｓｕｂｓｃｒｉｂｅｒ  Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ  Ｍｏｄｕｌｅ）モジュールとよばれる形態が採用されている。
ＩＣカード及びＳＩＭモジュールとも、カード形態の情報処理装置であり、端子付きの半導体チップをプラスティックの板に張り付けた構造をしている。両者の構造が基本的に同じであるので、以下ＩＣカードについて説明する。
上記のように利用されるＩＣカードは、勝手に書き換えることが許されない個人情報の保持を行なうほか、秘密情報である暗号鍵を用いたデータの暗号化や暗号文の復号を行なう。
ＩＣカード自体は電源を持っておらず、ＩＣカードを制御するリーダライタから電力の供給を受けて、動作可能となる。接触式のＩＣカードでは、半導体チップの端子を介して直接的に電力が供給される。一方、非接触式のＩＣカードでは、内蔵するアンテナコイルがリーダライタの発する電波を受信し、その共振出力を検波整流することにより、半導体チップを動作させる電力が取り出される。
ＩＣカードは、動作可能になると、リーダライタから送信されるコマンドを受信し、そのコマンドに従って、データの転送等の処理を行なう。
ＩＣカードは、第１０図に示すように、カード１０１の上に、ＩＣ（半導体集積回路）である半導体チップ１０２を搭載したものである。一般にＩＣカードは、ＩＳＯ７８１６の規格に定められた位置に供給電圧端子Ｖｃｃ、グランド端子ＧＮＤ、リセット端子ＲＳＴ、入出力端子Ｉ／Ｏ、クロック端子ＣＬＫを持ち、これらの端子を通して、リーダライタ（図示せず）から電源の供給やリーダライタとのデータの通信を行なう。
情報処理を行なう半導体チップ１０２の構成は、基本的には通常のマイクロコンピュータと同じである。その構成は、第１１図に示すように、ＣＰＵ（中央処理装置）２０１、記憶装置（ＭＥＭ）２０４、入出力ポート（Ｉ／Ｏ）２０７、コプロセッサ（ＣＯＰＲＯ）２０２からなる。
ＣＰＵ２０１は、論理演算や算術演算などを行なう装置であり、記憶装置２０４は、プログラム格納部（ＰＳ）２０５及びデータ格納部（ＤＳ）２０６を備えている。入出力ポート２０７は、リーダライタと通信を行なう装置である。コプロセッサ２０２は、暗号処理そのもの、又は暗号処理に必要な演算を高速に行なう装置であり、例えば、広く用いられているＲＳＡ暗号を対象とした剰余演算を行なうための特別な演算装置や、ＤＥＳ（米国のデータ暗号化規格）暗号のラウンド処理を行なう暗号装置などがある。ＩＣカード用プロセッサの中には、コプロセッサ２０２を持たないものも多くある。各装置は、データバス２０３によって相互に接続されている。
記憶装置２０４は、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）やＲＡＭ（Ｒａｎｄｏｍ  ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、ＥＥＰＲＯＭ（Ｅｌｅｃｔｒｉｃ  Ｅｒａｓａｂｌｅ  Ｐｒｏｇｒａｍｍａｂｌｅ  Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）などからなる。近年は、ＥＥＰＲＯＭの代わりにＦｅＲＡＭ（Ｆｅｒｒｏｅｌｅｃｔｒｉｃ  ＲＡＭ）を使うものもある。
書換えることができないメモリであるＲＯＭには、主にプログラムが格納される。書き換えが可能なＥＥＰＲＯＭには、ＩＣカードがリーダライタから抜かれた状態で保持することが要求されるデータが格納される。例えば、プリペイドカードでのプリペイドの度数などは、使用するたびに書き換えられ、ＥＥＰＲＯＭに保持される。
このように、ＩＣカードにおいては、プログラムや重要な情報が半導体チップの中に密閉される。即ち、ＩＣカードは、重要な情報を格納したり、内部で暗号処理を行なうために用いられる。
従来、ＩＣカードでの暗号を外部から解読する難しさは、暗号アルゴリズムの解読の困難さと同じと考えられていた。しかし、ＩＣカードが暗号処理を行なっている際の消費電流（リーダライタから供給される）を観測し、解析することにより、暗号アルゴリズムの解読よりも容易に暗号処理の内容や暗号鍵を推定することが可能であるとの示唆がなされるようになった。このような危険性が、例えば、文献１：１９９７年Ｊｏｈｎ  ｗｉｌｅｙ  ＆  Ｓｏｎｓ出版社発行“ＳＭＡＲＴＣＡＲＤ  ＨＡＮＤＢＯＯＫ”（Ｗ．Ｒａｎｋｌ及びＥｆｆｉｎｇ共著）の第２６３頁（８．５．１．１“Ｐａｓｓｉｖｅ  Ｐｒｏｔｅｃｔｉｖｅ  Ｍｅｃｈａｎｉｓｍ”）に記載されている。
特に、ＣＭＯＳ（Ｃｏｍｐｌｅｍｅｎｔａｒｙ  Ｍｅｔａｌ  Ｏｘｉｄｅ  Ｔｒａｎｓｉｓｔｏｒ）トランジスタによって構成される半導体チップ１０２のデータバス２０３においては、配線の持つ静電容量や配線に接続されているトランジスタの静電容量のため、バスドライバーによってバスの値が１から０又は０から１に変わるときに電力を消費する。一方、トランジスタのレベルが固定の状態では殆ど電力を消費しない。そのため、消費電力を観測すれば、半導体チップ１０２の中で、何が動作しているかが分かる可能性がある。
第１２図は、半導体チップ１０２の１サイクルでの消費電力の波形の例を示したものである。処理しているデータに依存して、消費電力波形が曲線３０１や曲線３０２のように異なる。このような差は、バス２０３を流れるデータやＣＰＵ２０１で処理しているデータに依存して生じる。そのため、消費電流を観測すれば、半導体チップ１０２の中で、何が動作しているか分かる可能性がある。
コプロセッサ２０２は、ＣＰＵ２０１と並列に、例えば、５１２ビットの剰余演算を行なう場合がある。その場合は、ＣＰＵ２０１の消費電流とは異なった消費電流波形が長時間に渡って継続する。従って、その特徴的な波形を観測することにより、コプロセッサ２０２の動作回数を容易に測定することができる。コプロセッサ２０２の動作回数が暗号鍵と何らかの関係があるならば、コプロセッサ２０２の動作回数から暗号鍵を推定できる可能性がある。
例えば、ＲＳＡ暗号の処理である、
Ｙ＾Ｘ  ｍｏｄ  Ｎ（＾は、冪乗を表す）
でよく用いられる実装においては、秘密指数であるＸのバイナリ表現の各項が０であるか１であるかに従い、剰余乗算である、
Ａ＊Ｂ  ｍｏｄ  Ｎ（＊は、乗算を表す）
の実行回数が変化する。なお、ＲＳＡ暗号の処理（復号）については後で述べるが、Ｙは暗号文、ＸはそのＩＣカードのみが知る秘密指数、Ｎは公開されている法（モジュラス）、Ｚ  ｍｏｄ  Ｎは、ＺをＮで割った余りを意味する。
通常のＩＣカードには、当該剰余演算を実行するコプロセッサ２０２が内蔵されており、このコプロセッサの動作電流は比較的大きく、ＣＰＵ２０１とは異なる電力消費パターンを示す場合がある。この場合は、コプロセッサ２０２の動作回数を数えることは容易であり、従って、秘密鍵Ｘの情報、即ち、１の個数を消費電力パターンから同定することができる。
また、コプロセッサ２０２での演算内容が、暗号鍵（秘相指数）に依存した偏りを持つ場合、その偏りが消費電流に反映し、暗号鍵が推定される可能性がある。偏りが著しい場合には、Ｘの全てのビットパターンを同定できる可能性もある。ＣＰＵ２０１でも同様の事情が存在する。暗号鍵は一定であるため、処理するデータを変更して、消費電流を観測することにより、暗号鍵のビット値の影響が観測できる可能性がある。これらの消費電流の波形を統計的に処理することにより、暗号鍵を同定することができる可能性がある〔（例えば文献２：Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ出版社発行「クリプト（Ｃｒｙｐｔｏ）’９９」論文集（Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  Ｃｒｙｐｔｏ’９９）の第１頁〜第１０頁（Ｐ．Ｋｏｃｈｅｒ，Ｊ．Ｊａｆｆｅ及びＢ．Ｊｕｎ“Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ”）参照）。
上記のような攻撃（タンパー）から内部データを守るために、即ち耐タンパーを備えるために、ＩＣチップ１０２でのデータ処理と消費電流との関連性を減らすことが行なわれる。消費電流とチップの処理との関連性が減れば、観測した消費電流の波形からＩＣチップ１０２内での処理や暗号鍵の推測が困難になる。
さて、暗号方式には、暗号・復号のための鍵を共通にしないで復号を可能にする公開鍵方式があり、多く用いられる。この場合、暗号鍵は公開され、復号鍵は、復号側でのみ知るものとなる。公開鍵方式を採用する暗号法の代表として、ＲＳＡ暗号や楕円曲線暗号がある。
ここで、上記のデータ処理と消費電流との関連性を減らす耐タンパーの代表的な従来例を、特にＲＳＡ暗号を例に取って説明する。その説明に先立ってＲＳＡ暗号の処理について以下に述べる。
ＲＳＡ暗号暗号処理は、単位となる処理の組み合せで実行されることが多い（このことは、楕円曲線暗号に共通している）。ＲＳＡ暗号の復号処理は、例えば、
Ｓ＝Ｙ＾Ｘ  ｍｏｄ  Ｎ
による復号結果Ｓを求める冪乗剰余計算によって行なわれる。計算機上で通常実装される、この冪乗剰余計算の例をフローチャートで第１３図に示す。この冪乗剰余計算は、アディション・チェイン・アルゴリズムに基づいて行なわれる〔例えば文献３：１９９７年ＣＲＣ  Ｐｒｅｓｓ出版社発行“ＨＡＮＤＢＯＯＫ  ＯＦ  ＡＰＰＬＩＥＤ  ＣＲＹＰＴＯＧＲＡＰＨＹ”（Ｍｅｎｅｚｅｓ，ｖａｎ  Ｏｏｒｓｃｈｏｔ及びＶａｎｓｔｏｎｅ共著）の第６１５頁“Ａｌｇｏｒｉｔｈｍ  １４．８２”参照〕。この復号結果Ｓを求める計算の手順の骨子は、次ぎの通りである。
本例の暗号化の計算をスタートして、まず、
（１）秘密指数Ｘのｎビットを、所望ビットＪ毎に、例えば２ビット（Ｊ＝２）毎に区切り、上位から読んでいき、それが、００，０１，１０，１１のいずれであるかに応じて、
ＴＢＬ［０］＝１
ＴＢＬ［１］＝Ｙ
ＴＢＬ［２］＝Ｙ＾２  ｍｏｄ  Ｎ
ＴＢＬ［３］＝Ｙ＾３  ｍｏｄ  Ｎ
を対応させ（ステップ０６０１）、続いて、
（２）これらの乗算剰余計算を行なう。
上述のように秘密鍵Ｘのビットを２ビット毎に区切ることは説明の便宜のための一例である。実際には秘密鍵Ｘのビットを１ビット、３ビット、４ビットにまとめて計算することもある。その際も計算手法の基本的な考え方は同じである。
このようなアディション・チェイン方式を用いて計算を行なう際、２回の二乗の計算を行なうステップ０６０２及びステップ０６１１は、Ｘのビットと無関係に行なわれる。
一方、その次に行なわれる乗算剰余計算においては、Ｘのビット（この例では、２ビット分を指す）値に応じて、条件分岐（ステップ０６０３、ステップ０６０４、ステップ０６０５及びステップ０６０６）が行なわれる。そして、それぞれのビットに応じて、ステップ０６０７、ステップ０６０８、ステップ０６０９及びステップ０６１０の乗算剰余計算が行なわれる。ステップ０６０２，０６１１及びステップ０６０７〜０６１０の演算は、カウンタｋがｎ／Ｊから１になるまで、区切ったＸ毎にｎ／Ｊ回行なわれる。即ち、１回の演算が終わる毎にｋから１を減じ、ｋ＝０になったときに演算が終了し、そのときの演算結果が最終結果になる。
なお、実装面からは、この乗算剰余計算は処理が重いので、多くのＩＣカードでは、乗算剰余計算には、ＣＰＵではなく、専用のコプロセッサが用いられることが多い。
この乗算剰余計算の際、各ビットによって異なるのは、ステップ０６０１において生成するテーブルの値、即ち、ＴＢＬ［０］，ＴＢＬ［１］，ＴＢＬ［２］，ＴＢＬ［３］である。
一般に、上述のように乗算剰余計算は処理が重く、その際、発生する電流は非常に大きい。特に、多桁計算の際に、ＴＢＬ［０］，ＴＢＬ［１］，ＴＢＬ［２］，ＴＢＬ［３］のうち、どれが処理されているかが判ることがある。
このような電流波形の違いから、例えば、電流波形パターンを４種類に分類することができれば、秘密鍵のビットパターンを見つけることができる。即ち、４種類の電流波形に基づき、その４つの順列のパターン数４！＝２４通りを試せば良い。法Ｎのビット数が増えた場合も、事情は同様である。
この秘密鍵のビットパターンを見つける攻撃の方法は、特にＮのビット数が増加したときに、著しい効果を発揮する。例えば、Ｎが２０４８ビットの場合、現在のところ、事実上因数分解を行なうのは不可能である。しかし、オシロスコープを用いてＩＣチップの消費電流を見ることができれば、秘密鍵のビットパターンを見つけることができる。
例えば、Ｘ（２０００ビット程度）の値を知るには、次のような手順がある。先ず、２０００ビット程度の消費電流の波形の塊（２ビット毎に区切っていれば、約１０００個の塊）を４通りに分類する。分類された４通りそれぞれについて、別の計算機を用いて、冪乗剰余計算を実行する。そして、この各冪乗剰余計算の結果をＩＣチップから出力される結果と比較して、その両者が一致しているものを探し出せばよい。この検証は、高々２４通りに過ぎない。従って、第１３図に示したようなＲＳＡ暗号の通常の処理は、データが解読される高い可能性を有することとなる。
このような解析を撹乱する基本的な考えは、データを変形して、暗号処理を行ない、最後に逆変形することである。共通鍵を採用しているＤＥＳ暗号に対してこの考えを適用した、攻撃から守る方法の例が、例えば、文献４：特開２０００−１８２０１２号公報に記載されている。
解析を撹乱する方法、即ち、データ処理と消費電流との関連性を減らすことによって耐タンパーを得る、ＲＳＡ暗号を対象にした従来の代表的な方法として、Ｙの代わりに、ＫＹ  ｍｏｄ  Ｎ（Ｋは、法Ｎの下で逆数を持つ乱数）を用いて処理を行ない、最後に修正処理を行なう従来の（方法Ａ）がある。（方法Ａ）が例えば文献５：Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ出版社発行「クリプト（Ｃｒｙｐｔｏ）’９６」論文集（Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  Ｃｒｙｐｔｏ’９６）の第１０４頁〜第１１３頁（Ｐ．Ｋｏｃｈｅｒ“Ｔｉｍｉｎｇ  Ａｔｔａｃｋｓ  ｏｎ  Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ  ｏｆ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ，ＲＳＡ，ＤＳＳ，ａｎｄ  Ｏｔｈｅｒ  Ｓｙｔｅｍｓ”）に記載されている。
（方法Ａ）においては、入力データＹ自身ではなく、乱数Ｋに対して、ＫＹが演算されるので、剰余乗算を行なうコプロセッサにおいて消費される電流が異なる。Ｋは乱数であり、外部から判らないため、ＫＹの値がどうなるか判らず、従って対応する電流も本来のものとの相関がなくなる。これにより、電流から秘密鍵を知ることが困難になる。
【発明の開示】
（方法Ａ）では、得られる結果は、
（ＫＹ）＾Ｘ  ｍｏｄ  Ｎ
であり、正しい結果を得るためには、
Ｋ＾（−Ｘ）ｍｏｄ  Ｎ
を乗じて修正する必要がある。計算時間の増加は、このようにデータを本来とは異なるものに変形し、最後に逆変形を一括して行なうことによって生じる。本発明者は、計算時間の増加を抑えるために、上記の変形と一括逆変形による計算の構成を変えて処理を軽くすることに着目した。
本発明は、情報処理装置をそのようにして計算の肥大化を避けるように構成したものであるが、本発明の内容を説明するために、以下に先ず（方法Ａ）を分解し、問題点を明らかにしておく。
（方法Ａ）を第１４図から第１７図に示す。第１４図に示す事前処理においては、まず乱数Ｋ（Ｋ＜Ｎ）を発生する（ステップ０７０１）。そして、入力Ｙと当該乱数Ｋを用いて、
ＴＢＬ［Ｋ，ｊ］＝（Ｋ＊Ｙ）＾ｊ  ｍｏｄ  Ｎ
（ｊ＝０、１、２、３）
を作成する（ステップ０７０２）。
その上で、ＫのＮに関する逆数（Ｋは、Ｎと互いに素でなければならない）をユークリッド互除法を用いて計算し（例えば文献３の第６７頁（Ａｌｇｏｒｉｔｈｍ  ２．１０７）参照）、これをＣとする（ステップ０７０３）。
Ｃを用いて、
Ｂ［ｊ］＝Ｃ＾ｊ  ｍｏｄ  Ｎ（ｊ＝０、１、２、３）
を作成する（ステップ０７０４）。
次に、第１５図に示す冪乗剰余計算の処理に移る。第１５図の処理は、第１３図における処理と同じであるが、ステップ０８０１，０８０２，０８０３，０８０４において、ＴＢＬ［Ｋ，ｊ］を用いている点が異なる。この処理で、
Ｓ＝（Ｋ＊Ｙ）＾Ｘ  ｍｏｄ  Ｎ
が計算される。
続いて、第１６図に示す乱数Ｋに対する冪乗剰余計算の処理に移る。第１６図の処理は、
Ｔ＝Ｃ＾Ｘ  ｍｏｄ  Ｎ＝Ｋ＾（−Ｘ）ｍｏｄ  Ｎ
の計算を行なうものであって、第１３図の処理と同じであるが、ステップ０９０１，０９０２，０９０３，０９０４において、Ｂ［ｊ］を用いている点が異なる。
次いで、第１７図に示す修正処理に移る。第１７図の処理においては、  Ｓ＊Ｔ  ｍｏｄ  Ｎ
を計算し、再びＳとし、処理を終了する。
この際、第１５図に示した、剰余二乗算２回と剰余乗算１回の処理が単位処理に相当する。（ここでは、１を乗ずる処理も敢えて行なっているが、これは説明のためであって、実際には処理を行なわないことが多い。）単位処理は、中間結果Ｓと乱数Ｋ、指数Ｘ［ｋ］によって決まるので、以下、これを、
Ｕ（Ｓ、Ｋ、Ｘ［ｋ］）
と書くものとする。言い換えれば、この表記では、（方法Ａ）の処理は、第１８図、第１９図に示すようになる。
第１８図の事前処理は、事前計算のステップ０７０１，０７０２，０７０３，０７０４と、Ｓ，Ｔの初期化の処理であるステップ０７０５を行なうものである。
第１９図の冪乗剰余計算と乱数Ｋに対する冪乗剰余計算の処理は、第１８図の処理に引き続いて、ＳとＴの計算を行なうものである。ここで、ステップ１２０１，１２０２の処理が、先に示した単位処理である。最後にステップ１２０３の処理を行なって、冪乗剰余計算の処理が終了する。
（方法Ａ）の場合、この単位処理Ｕ（Ｓ，Ｋ，Ｘ［ｋ］）において、途中処理結果Ｓは、乱数Ｋと指数の２ビットブロックＸ［ｋ］に対し、
Ｓ＊（Ｙ＊Ｋ）＾（４＋Ｘ［ｋ］）ｍｏｄ  Ｎ
＝（Ｓ＊Ｙ＾（４＋Ｘ［ｋ］））＊Ｋ＾（４＋Ｘ［ｋ］）ｍｏｄ  Ｎ
と変形される。従って、この計算は、指数の２ビットブロックＸ［ｋ］の影響を受け、指数が尽きるまで影響を受ける。このことが、最終的な処理が大きなものになる原因になる。この問題は、データ隠蔽に用いた乱数Ｋの指数が変化してしまうことによって生ずる。もし、各２ビット処理毎にＫの指数が変化しなければ、処理の肥大化を避けることができる。
この事情は、楕円曲線暗号においても同様である。以下に、楕円曲線暗号の演算処理の概要を説明する。
楕円曲線暗号においては、有限体（有限個の元の間に四則演算が定義された代数系）Ｆ上で定義された楕円曲線（３次曲線）Ｅの上の点ＰとＱに対し、これらの和であるＥ上の点Ｐ＋Ｑが定義される。更に、通常の０（ゼロ）に相当する点（無限遠点）Ｏが定義される。即ち、いかなるＥ上の点Ｐに対しても、Ｐ＋Ｏ＝Ｏ＋Ｐ＝Ｐとなるような点Ｏが唯一つ存在する。更に、任意のＥ上の点Ｐに対して、Ｐ＋Ｑ＝Ｏとなるような点Ｑ（−Ｐと書かれる）が存在し、Ｅ上の点全体は、一つの加法群（アーベル群）を形成する。Ｐをｍ個加えたものをｍＰと書き、負の数ｍに関しては、−Ｐを−ｍ個加えたものをｍＰと書くことにする。ｍ＝０に対しては、ｍＰ＝Ｏ（無限遠点）とする。これをＰのスカラー倍演算と呼ぶ。ｍは、現在、１６０ビット程度の整数を用いることが多い。
楕円曲線暗号は、等式ｍＰ＝Ｑにおいて、ＰとＱが与えられた場合にｍを決定する問題（楕円曲線上の離散対数問題）が、多大な計算時間を必要とすることを利用した公開鍵暗号である。
暗号処理の本体は、適当なＥの点Ｐのスカラー倍ｍＰの計算である。この計算にもＲＳＡ暗号の処理に用いたアディション・チェイン・アルゴリズムを適用することができる。これまでの例に倣い、ＲＳＡ暗号の指数２ビットを処理単位とするアディション・チェイン・アルゴリズムを楕円曲線暗号の処理におけるスカラー倍の計算を行なうように変形したものを第２０図に示す。
容易に分かるように、第１３図の処理と第２０図の処理の違いは、データと、その間の演算の違いだけである。即ち、
Ａ＊Ｂ  ｍｏｄ  Ｎ
がＡ＋Ｂ（楕円曲線上の加算）に対応し、１がＯ（無限遠点）に対応する。
このことは、アディション・チェイン・アルゴリズムが、個々の演算の種類によらない、より一般的なものであることを示している。
従って、楕円曲線暗号におけるスカラー倍の処理においても、ＲＳＡ暗号で生ずるのと同様のセキュリティ上の問題即ち攻撃（タンパー）を受ける問題が発生する。また、楕円曲線暗号のデータを隠蔽するための処理のうち、ＲＳＡ暗号の処理における（方法Ａ）に類似する、以下の（方法Ｂ）においても計算量の増大という問題が発生する。
（方法Ｂ）は、ｍの代わりにｍ＋Ｋ（Ｋは乱数）を用いてスカラー倍の処理（ｍ＋Ｋ）Ｐを行ない、最後に−ＫＰを加える処理である。この（方法Ｂ）においても、（方法Ａ）と同様に計算量の増大という問題が発生する。
即ち、−ＫＰを求める処理は、Ｋがｍと同程度以上のビット長を持てば、ｍＰを計算するのと同様の処理時間を必要とする。Ｋがｍと同程度以上のビット長を必要とする理由は、もしも、ｍがＫと比較して小さい場合（例えば半分の長さのとき）、ｍの上位は、殆どそのままの生の値で処理されることになるからである。
ここで挙げた演算は一例であって、それ以外にも種々のデータを隠蔽する従来方法がある。説明を省略するが、いずれも同様の問題が発生する。
本発明者は、逐次的に逆変換を行なうようにすれば、処理が軽くなり、消費電力と内部処理との関連を減らすことが可能になることを見出した。この方法においは、単位処理の前後で、データの形式が変化しないので、従来の（方法Ａ）や（方法Ｂ）のように、本来のデータとは異なるものに変形し、最後に逆変形を一括して行なうことによって発生する処理の肥大化を避けることができる。なお、単位処理とは、例えば、第１９図におけるＵに相当するものである。
以下、本発明の処理手順を第１図を用いて説明する。今、所望の演算を＃で表したときの信号Ａと信号Ｂとを以って行なうＡ＃Ｂに関して、多くの公開鍵暗号で用いられる一般的な演算は、
Ｙ＾Ｘ＝Ｙ＃Ｙ＃…＃Ｙ（Ｘ個）
となり、Ａ＃Ｂの形式を含んでいる。本発明は、このような演算を対象とする。演算では、Ｘのビット長がｎであるとし、Ｊビット単位のアディション・チェイン方式による処理が採用される。Ｊは、負でない整数である。
説明の煩雑さを避けるために、ｎは、Ｊの倍数であると仮定する。以下、Ｘを上位からＪビット毎に区切っていったものを、Ｘ＝（Ｘ［ｎ／Ｊ］Ｘ［ｎ／Ｊ−１］…Ｘ［ｋ］…Ｘ［１］）と表現する。（ｋ＝１，２，…，ｎ／Ｊ−１，ｎ／Ｊ）
ステップＳ１で、ｋ＝ｎ／Ｊとし、
ステップＳ２で、乱数発生源が発生する信号に基づいて信号Ｗを定め、
ステップＳ３で、Ｌ＝Ｗとする。即ち、Ｌの格納部に信号Ｗを入力し、
ステップＳ４で、Ｌ＃Ｌを計算し、再びＬの格納部に書き戻す操作をＪ回行ない、
ステップＳ５で、Ｘ［ｋ］とＷに基づいて一意的に決まる信号
Ｂ［ｋ］＊Ｗ＾（（２＾Ｊ）−１）
に対して、
Ａ＃Ｂ［ｋ］＃Ｗ＾（（２＾Ｊ）−１）
を計算し、再びＡの格納部に書き戻す操作を実行し、
ステップＳ６で、ｋから１を減じ、
ステップＳ７で、ｋ＝０であればステップＳ７に進み、ｋ＞０であれば、再びステップＳ４に戻り、
ステップＳ８で、ｋ＝０になったときの処理結果Ｔに対して、
Ｔ＃Ｗ＾（−１）
を出力結果Ｓとする。但し、Ｗ＾（−１）は、Ｗ＃Ｙ＝ＩとなるＹのことである。
以下、これら一連の処理によって、Ｓの値がどのように変化するかを説明する。
最初、ステップＳ３によってＬ＝Ｗとなる。ステップＳ４によって、値は、
Ｌ＝Ｗ＾（２＾Ｊ）
となる。ステップＳ５によって、Ｌの値は、
Ｗ＾（２＾Ｊ）＃Ｂ［ｋ］＃Ｗ＾（−（２＾Ｊ−１））
＝Ｂ［ｋ］＃Ｗ
となる。この段階で、ｋが０でなければ、ステップＳ７によって再びステップＳ４に戻るので、同様に、ステップＳ４及びステップＳ５を経て、Ｌの値は、
Ｂ［ｋ］＾（２＾Ｊ）＃Ｗ
となる。このとき、Ｌの値が、単位処理の前後で、Ｗ＝Ｉ（単位元）であるときの値に、Ｗを掛けるという形式を崩していないことが重要である。以下、全く同様に、単位処理の前後で、
「Ｗ＝Ｉの場合の途中結果」＃Ｗ
が維持され続ける。Ｗの値が未知であるので、処理データが不明のままであり、従って、ＩＣチップの消費電力から、不正に内部情報を読み取ることが困難となる。
以上の演算は、言い換えると、ｋの値を定めるカウンタｋが０となって、ステップＳ４からステップＳ７への演算が終了したときに、結果は、
Ｙ＾Ｘ＃Ｗ
の形式となることであり、この場合にステップＳ８で、
Ｗ＾（−１）ｍｏｄ  Ｎ
を乗ずることによって、所望の値、Ｙ＾Ｘを得ることができるのである。この際、所望の値に修正するのに必要な処理は、ステップＳ８であって、従来の（方法Ａ）のときのように、Ｗ＾（−Ｘ）を乗ずるという重い修正処理の必要がない。
なお、取り上げるＸの順番は、上記では、ｎ／Ｊからとしたが、これを１からの逆順としても良く、或いは、番号が２ずつ変化するようにしても良い。従って、単純に順番を表すためのｈを用いて上記のＸの表現を改め、Ｘ＝（Ｘ［ｈ］Ｘ［ｈ−１］…Ｘ［ｋ］…Ｘ［１］）としてｋをｈから順に定めるようにすることができる。
【図面の簡単な説明】  第１図は、本発明に係る情報処理装置が実行する手順を説明するためのフローチャートであり、第２図は、本発明の情報処理装置を説明するための構成図であり、第３図は、乱数発生装置の例を説明するための構成図であり、第４図は、本発明の第１の実施例の事前処理を説明するためのフローチャートであり、第５図は、第１の実施例の冪乗剰余計算部を説明するためのフローチャートであり、第６図は、第１の実施例の修正処理部を説明するためのフローチャートであり、第７図は、本発明の第２の実施例の事前処理部を説明するためのフローチャートであり、第８図は、第２の実施例のスカラー倍処理部を説明するためのフローチャートであり、第９図は、第２の実施例の修正処理部を説明するためのフローチャートであり、第１０図は、ＩＣカードの概観及び各種端子を説明するための平面図であり、第１１図は、従来の情報処理装置の例を説明するための構成図であり、第１２図は、データによる消費電力の違いを説明するための曲線図であり、第１３図は、アディション・チェイン方式によるＲＳＡ復号の例を説明するためのフローチャートであり、第１４図は、従来の耐タンパーＲＳＡ復号の事前処理の例を説明するためのフローチャートであり、第１５図は、従来の耐タンパーＲＳＡ復号の冪乗剰余計算部の例を説明するためのフローチャートであり、第１６図は、従来の耐タンパー復号処理の乱数Ｋに対する冪乗剰余計算部の例を説明するためのフローチャートであり、第１７図は、従来の耐タンパー復号処理の修正処理部の例を説明するためのフローチャートであり、第１８図は、従来の耐タンパー復号処理の事前処理の例を説明するための別のフローチャートであり、第１９図は、従来の耐タンパー復号処理の冪乗剰余計算部と乱数Ｋの冪乗剰余計算部の例を説明するための別のフローチャートであり、第２０図は、従来の別の耐タンパー暗号処理を説明するためのフローチャートである。
【発明を実施するための最良の形態】  以下、本発明に係る耐タンパー情報処理装置を図面に示した実施例を参照して更に詳細に説明する。
本実施例の情報処理装置の構成を第２図に示す。同図において、２０１は、論理演算や算術演算などを行なうＣＰＵ（中央処理装置）、２０４は、プログラム格納部（ＰＳ）２０５及びデータ格納部（ＤＳ）２０６を備えた記憶装置（ＭＥＭ）、２０７は、リーダライタ（図示せず）と通信を行なう入出力ポート（Ｉ／Ｏ）、２０２は、暗号処理そのもの又は暗号処理に必要な演算を高速に行なうコプロセッサ（ＣＯＰＲＯ）、２０８は、乱数発生源となる乱数発生装置（ＲＮＧ）、２０３は、各装置を相互に接続するデータバスを示す。以上の各装置がＩＣチップに内蔵されている。
ＣＰＵ２０１及びコプロセッサ２０２は、以下に述べる暗号処理の各ステップをプログラム格納部２０５に格納された暗号処理プログラムに従って実行する。
乱数発生装置２０８の構成を第３図に示す。第３図において、１４０２は、一方の端子が接地された抵抗、１４０７は、抵抗１４０２の他方の端子を接続した入力端子を持つ増幅器（オペアンプ）、１４０４は、増幅器１４０７の出力端子を接続した入力端子１４０６と基準電源を入力する入力端子１４０３を持つ比較器である。
増幅器１４０７の他方の入力端子は接地される。また、基準電源の電位はＶｔｈに固定されており、比較器１４０４は、端子１４０６の電位とＶｔｈとを比較して、端子１４０６の電位がＶｔｈよりも高いときは、出力端子１４０５より、１を出力し、低い場合は、０を出力する。出力端子１４０５の出力信号は、バス２０３に供給される。
抵抗１４０２は、熱によって揺らぎ、振幅変化がランダムな熱雑音を発生する。これを増幅器１４０７が増幅し、その出力電位を比較器１４０４が適当な電位Ｖｔｈと比較することによって、予測できないビット列が生成される。
以上の情報処理装置がＩＣカードやＧＳＭモバイルホンで用いられるＳＩＭモジュールにＩＣチップとして実装される。
はじめに第１の実施例として、ＲＳＡ暗号を取り上げる。本実施例は、演算＃を、
Ａ＃Ｂ＝Ａ＊Ｂ  ｍｏｄ  Ｎ
で定義することによって構成される。ここで、データＡ，Ｂ，Ｎは、１０２４ビットの正の整数とする。上記のＡ＊Ｂ  ｍｏｄ  Ｎは、ＡとＢの通常の積をＮで割った余りを意味する。例えば、
５＊３  ｍｏｄ  ７＝１
である。
ＲＳＡ暗号の復号演算は、
Ｙ＾Ｘ  ｍｏｄ  Ｎ
の計算を行なうことによって実行される。ここで、Ｙは暗号文、Ｘは秘密指数，Ｎは公開モジュラスである。計算は、
Ｙ＾Ｘ＝Ｙ＃Ｙ＃…＃Ｙ（Ｘ個）
として行なわれる。
アタッカーのターゲットは、Ｘである。Ｘはｎ＝１０２４ビットであるものとし、演算は、２ビット単位の、即ちＪ＝２のアディション・チェイン方式で処理される。以下、Ｘを上位から２ビット毎に区切っていったものを、Ｘ＝（Ｘ［５１２］Ｘ［５１１］…Ｘ［１］）と表現する。
本実施例では、コプロセッサ２０２がＡ＊Ｂ  ｍｏｄ  Ｎを計算する。当該コプロセッサは、データ格納部２０６にレジスタＡ，Ｂ，Ｎを持ち、Ａ＊Ｂ  ｍｏｄ  Ｎを計算して、その結果を再びＡレジスタに格納するものとする。一般に、Ａ，Ｂ，Ｎは、１０２４ビット程度の大きな整数であるので、Ａ＊Ｂ  ｍｏｄ  Ｎの計算に時間がかかるため、通常、専用のコプロセッサが用意される。
以下、説明のため、ＣＰＵのレジスタサイズは、３２ビットとしておく。
第４図、第５図、第６図に基づいて本発明の説明を行なう。まず、第４図に示すフローチャートの処理を開始する。ステップ１５０１の処理は、先に述べたステップＳ２に相当し、内蔵されている乱数発生装置２０８が乱数Ｗを発生する。Ｗは、Ｎよりも小さいもので、かつＮと互いに素であるものとする。ＲＳＡ暗号では、Ｎは、大きな素数ＰとＱ（両者は、Ｎのほぼ半分のビット長を持つ）の積であるので、Ｗを、Ｐ，Ｑのうちの小さい方よりも小さくとれば、確実に互いに素となる。ここでは、高速処理を考慮して、Ｗを３２ビット以下とする。なお、本発明は、３２ビットに限定されるものではなく、６４ビット、或いは、１６ビット、８ビット等の他の値を採用することが可能である。
ここで、ＲＳＡ暗号の処理のために、事前処理として、レジスタＡ，Ｂを持つコプロセッサ２０２を用いて、ステップＳ５に相当する演算で用いるＹ０，Ｙ１，Ｙ２，Ｙ３が以下において算出される。
ステップ１５０２にて、
Ｍ＝Ｗ＾（−１）ｍｏｄ  Ｎ
が計算される。この計算は、拡張されたユークリッド互除法を用いてなされる（例えば文献３の第６７頁（Ａｌｇｏｒｉｔｈｍ２．１０７）参照）。Ｍを求める計算は、数学的には、不定方程式（ディオフンタス方程式）である
Ｍ＊Ｗ−Ｈ＊Ｎ＝１
を解いて、Ｍを求めることに等しい。
この際、Ｗが３２ビットであり、Ｎのビット数（１０２４ビット）よりもずっと小さいので、拡張されたユークリッド互除法のアルゴリズムにおける最初のステップ、即ち、ＮをＷで割る処理を行なった段階で、ＮをＷで割った余りは、３２ビット以下になる。従って、最初のステップを高速に実行できれば、その後の処理が軽い。最初のステップを高速化する方法は、よく知られているように、引き離し法（Ｎｏｎ  Ｒｅｓｔｏｒｉｎｇ  Ｍｅｔｈｏｄ）があり、本実施例で採用した。この方法では、除算の中間処理である減算を、正負にかかわらず計算して、最後に値の調節が行なわれる。
次に、ステップ１５０３にて、
Ｗ＾（−３）ｍｏｄ  Ｎ＝Ｍ＾３  ｍｏｄ  Ｎ
が計算される。具体的には、ＭをＡレジスタに格納して、コプロセッサ２０２を用いて、
Ａ＊Ａ  ｍｏｄ  Ｎ
を計算し、次に、Ｂレジスタに、Ｍを格納して、コプロセッサ２０２で、
Ａ＊Ｂ  ｍｏｄ  Ｎ
を実行することにより、Ａレジスタに、Ｗ＾（−３）ｍｏｄ  Ｎが格納される。これは、続いてデータ格納部２０６のＲＡＭの領域に転送される。これがステップ１５０４におけるＹ０となる。
次に、ＢレジスタにＹ０を格納して、Ａ＊Ｂ  ｍｏｄ  Ｎを実行することにより、Ａレジスタに
Ｙ１＝Ｙ＊Ｗ＾（−３）ｍｏｄ  Ｎ
の値が格納される。この値は、上記ＲＡＭの領域（Ｙ０とは重複しない領域）に転送される。
次に、もう一度、Ａ＊Ｂ  ｍｏｄ  Ｎを実行することにより、Ａレジスタには、
Ｙ２＝Ｙ＾２＊Ｗ＾（−３）ｍｏｄ  Ｎ
が格納される。この値は、上記ＲＡＭの領域（Ｙ０，Ｙ１とは重複しない）に転送される。
次に、更にもう一度、Ａ＊Ｂ  ｍｏｄ  Ｎを実行することにより、Ａレジスタには、
Ｙ３＝Ｙ＾３  ｍｏｄ  Ｎ
が格納される。この値は、上記ＲＡＭの領域（Ｙ０，Ｙ１，Ｙ２とは重複しない）に転送される。これによって、ステップ１５０４の処理が終了し、Ｙ０〜Ｙ３の値が全て求められたことになる。
ステップ１５０５の処理は、カウンタをｋ＝５１２に初期化するもので、ステップＳ１に相当する。
次に、ステップ１５０６で、Ａレジスタに乱数Ｗが格納される（ステップＳ３に相当する）。そして、第５図の処理に移る。
ステップ１６０１では、まず最初に、カウンタｋの値が０であるかどうかが調べられる（ステップＳ６に相当）。ｋが０でなければ、ステップＳ４に相当するステップ１６０２，１６０３によって、Ａレジスタの値が４乗される。
次に、ステップ１６０４，１６０５，１６０６，１６０７によって、指数Ｘの２ビットブロックＸ［ｋ］の値に応じて、Ｙ０〜Ｙ３のうちの一つが選ばれ、ステップ１６０８，１６０９，１６１０，１６１１において、これがＢレジスタに転送される。続いて、ステップ１６１２で、Ａ＊Ｂ  ｍｏｄ  Ｎが計算される。ステップ１６０４〜１６１２がステップＳ５に相当する。
次に、ｋから１が減算される（ステップＳ６に相当するステップ１６１３）。そして、処理は再びステップ１６０１へと移り、カウンタｋの値が０になるまで同様の処理が続けられる。カウンタｋの値が０になったときに、第６図の処理に移る。
第６図の処理はステップＳ７に相当する修正処理であって、ＢレジスタにＭが格納され（ステップ１７０１）、Ａ＊Ｂ  ｍｏｄ  Ｎが計算され、結果がＡレジスタに格納される（ステップ１７０２）。
この処理によって、
Ｙ＾Ｘ＊Ｗ＊Ｍ  ｍｏｄ  Ｎ
＝Ｙ＾Ｘ＊Ｗ＊Ｗ＾（−１）ｍｏｄ  Ｎ
＝Ｙ＾Ｘ  ｍｏｄ  Ｎ
となり、所望の結果が得られる。
第５図に示した処理の過程では、全てのデータに乱数が掛けられているため、外部から当該ＩＣチップの消費電力を基に秘密情報を取り出すことが困難になる。更に、第６図に示した処理の過程では、従来に行なわれていたＷ＾（−Ｘ）を乗ずるという重い修正処理の必要がなく、従って、処理の肥大化が回避され、処理が高速化される。なお、ここでは、データ長が１０２４ビットである場合を扱ったが、これ以外の場合も同様に処理可能であることは言うまでもない。
次に、第２の実施例として、楕円曲線暗号に対する処理を取り上げる。説明に先立って、楕円曲線暗号について述べる。
楕円曲線は、（曲線Ｅ）を表す
Ｙ＾２＝ａ＊Ｘ＾３＋ｂ＊Ｘ＋ｃ
という形の標準形を持つ３次曲線に、無限遠点と呼ばれる特殊な元Ｏを加えたものである。但し、（曲線Ｅ）は非特異なもの、即ち、右辺が重根を持たないように選ばれる。ここで、ａ，ｂ，ｃは、定数であり、有限体Ｆの元である。又、Ｘ，ＹもまたＦの元であるが、これらは変数であるものとする。
有限体は、有限個の元からなる代数系であって、四則演算が可能なものをいう。最も簡単な有限体は、素体ＧＦ（Ｐ）である。ここで、Ｐは素数であって、ＧＦ（Ｐ）は、集合としては、
ＧＦ（Ｐ）＝｛０，１，２，…，Ｐ−１｝
である。
ＧＦ（Ｐ）における四則演算は、
（和）Ａ＋Ｂ  ｍｏｄ  Ｐ
（差）Ａ−Ｂ  ｍｏｄ  Ｐ
（積）Ａ＊Ｂ  ｍｏｄ  Ｐ
（商）Ａ＊Ｂ＾（−１）ｍｏｄ  Ｐ
である。（商）の定義において、Ｂは０でないものとする。
ＧＦ（Ｐ）の元を係数に持つＺの多項式のうち、ｎ−１次以下のもの全体からなる集合に対して、既約なｎ次多項式Φ（Ｚ）を取って、
（和）Ａ（Ｚ）＋Ｂ（Ｚ）ｍｏｄ  Φ（Ｚ）
（差）Ａ（Ｚ）−Ｂ（Ｚ）ｍｏｄ  Φ（Ｚ）
（積）Ａ（Ｚ）＊Ｂ（Ｚ）ｍｏｄ  Φ（Ｚ）
（商）Ａ（Ｚ）＊Ｂ（Ｚ）＾（−１）ｍｏｄ  Φ（Ｚ）
によって四則演算を定義したものも体となり、その代数的な構造は、Φ（Ｚ）の選び方に依存しない。これをＧＦ（Ｐ）のｎ次拡大体と呼ぶ。暗号処理においては、計算量を軽減する立場から、素体ＧＦ（Ｐ）と、標数２のガロア体ＧＦ（２＾ｎ）がよく用いられる。
（曲線Ｅ）の二つの点ＲとＳをとると、ＲとＳを通る直線が１本定まる（Ｒ＝Ｓのときは接線を取る）。（曲線Ｅ）は３次曲線であるので、ＲとＳを通る直線がＹ軸に平行になる場合を除けば、必ず、もう１点で交わる。この点をＴとし、ＴとＸ軸に関して対称の位置にある点がＲとＳの和であり、
Ｒ＋Ｓ
と書かれる。ＲとＳを通る直線がＹ軸に平行になる場合は、Ｒ＋Ｓは無限遠点Ｏであるものとする。又、Ｒ＋Ｖ＝Ｏとなるような点ＶをＲの逆元といい、−Ｒで表す。このような規則の下で、（曲線Ｅ）の点全体は、可換群という代数系、即ち、Ｅのモーデル・ヴェイユ群が構成される。
楕円曲線上の和の計算は、Ｘ，Ｙの四則演算で達成される〔例えば文献６：１９９４年シュプリンガー・フェアラーク東京出版社発行「楕円曲線論入門」（Ｊ．Ｈ．シルバーマン及びテイト著、足立恒雄他訳）参照〕。
本実施例は、演算＃を、
Ｒ＃Ｓ＝Ｒ＋Ｓ（楕円曲線Ｅ上の和）
で定義することによって構成される。ここでは、楕円曲線としては、素体ＧＦ（Ｐ）の上で定義されたものを考える。
楕円曲線暗号の処理は、スカラー倍演算である
ｍＲ（ｍは整数、ＰはＥの点）
の計算によって行なわれる。アタッカーのターゲットは、整数ｍである。ｍが１６０ビットであるものとし、２ビット単位のアディション・チェイン方式で処理する場合を考える。以下、Ｘを上位から２ビット毎に区切っていったものを、ｍ＝（ｍ［８０］ｍ［７９］…ｍ［１］）と表現する。
また、本実施例においても、第１にの実施例の場合と同様に、ＩＣチップに内蔵した乱数発生装置２０８を用い、Ａ＊Ｂ  ｍｏｄ  Ｎを計算するコプロセッサ２０２を用いる。コプロセッサ２０２により、ＧＦ（Ｐ）上の積と商の演算ができる。和と差については、ＣＰＵ２０１でも容易に処理することができる。演算は、具体的には、
Ｒ１（Ｘ１，Ｙ１），Ｒ２（Ｘ２，Ｙ２）
に対し、
Ｒ１＋Ｒ２＝（Ｘ３，Ｙ３）
とすると、
Ｘ３＝Ｈ＾２−Ｘ１−Ｘ２  ｍｏｄ  Ｐ
Ｙ３＝−（Ｈ＊Ｘ３＋Ｙ２−Ｈ＊Ｘ２）ｍｏｄ  Ｐ
Ｈ＝（Ｙ２−Ｙ１）＊（Ｘ２−Ｘ１）＾（−１）ｍｏｄ  Ｐ
と書くことができる。
第７図、第８図、第９図を用いて本実施例を説明する。まず、第７図の処理を開始する。ステップ１８０１の処理は、乱数発生装置２０８が乱数Ｗ１，Ｗ２を発生する。Ｗ＝（Ｗ１，Ｗ２）とする。
次に、ステップ１８０２にて、
−Ｗ＝（Ｗ１，Ｐ−Ｗ２）
が計算される。計算結果の値は、データ格納部２０６のＲＡＭの領域に転送される。
次に、ステップ１８０３にて、−３Ｗが計算される。この値は、上記ＲＡＭの領域（−Ｗとは重複しない領域）に転送される。
ステップ１８０４においては、ＲＳＡ暗号の場合と同様の処理が剰余乗算の代わりに、楕円曲線上の和で行なわれ、
Ｒ０＝３Ｗ
Ｒ１＝Ｒ−３Ｗ
Ｒ２＝２Ｒ−３Ｗ
Ｒ３＝３Ｒ−３Ｗ
が求められ、これらを格納したテーブルが作成される。これらの値は、全て、互いに重複しないように配置される。
ステップ１８０５の処理は、カウンタをｋ＝８０に初期化するものである。
次に、ＲＡＭ上の領域ＳにＷが格納され（ステップ１８０６）、第８図の処理に移る。
ステップ１９０１では、まず最初に、カウンタｋの値が０であるかどうかが調べられる。ｋが０でなければ、ステップ１９０２，１９０３によってＳの４倍点が計算される。
次に、ステップ１９０４，１９０５，１９０６，１９０７によって、ｍの２ビットブロックｍ［ｋ］の値に応じて、Ｒ０〜Ｒ３のうちの一つが選ばれ、ステップ１９０８，１９０９，１９１０，１９１１において、Ｓ＋（Ｒ０〜Ｒ３のいずれか）が計算される。
次に、ｋから１が減算される（ステップ１９１２）。そして、処理は再びステップ１９０１へと移り、カウンタｋの値が０になるまで同様の処理が続けられる。
カウンタｋの値が０になったとき、第９図に示す処理に移る。
第９図に示した処理は修正処理であって、Ｓ−Ｗが計算され、結果の値がＳレジスタに格納される（ステップ２００１）。
この処理によって、
ｍＲ＋Ｗ−Ｗ＝ｍＲ
となり、所望の結果が得られる。
第９図までの処理の過程では、全てのデータに乱数が加算されているため、外部から当該ＩＣチップの消費電力に基づいて秘密情報を取り出すことが困難になる。更に、第９図に示した処理の過程では、従来に行なわれていたＷ＾（−Ｘ）を乗ずるという重い修正処理の必要がなく、従って、処理の肥大化が回避され、処理が高速化される。
以上に示した二つの実施例は、本質的に、演算＃の意味を置換えただけで得られるものであり、言うまでもなく、これを一般化することが可能である。
本発明により、処理の肥大化を伴うことなく高いセキュリティを維持することができる、ＩＣカードなどの耐タンパー情報処理装置を提供することができる。
【産業上の利用可能性】  本願発明は、ＩＣカードやＧＳＭモバイルホンなどで用いられるＩＣチップが有する情報を安全に守るために利用される。
【図１】
2004047052.tif 000003
【図２】
2004047052.tif 000004
【図３】
2004047052.tif 000005
【図４】
2004047052.tif 000006
【図５】
2004047052.tif 000007
【図６】
2004047052.tif 000008
【図７】
2004047052.tif 000009
【図８】
2004047052.tif 000010
【図９】
2004047052.tif 000011
【図１０】
2004047052.tif 000012
【図１１】
2004047052.tif 000013
【図１２】
2004047052.tif 000014
【図１３】
2004047052.tif 000015
【図１４】
2004047052.tif 000016
【図１５】
2004047052.tif 000017
【図１６】
2004047052.tif 000018
【図１７】
2004047052.tif 000019
【図１８】
2004047052.tif 000020
【図１９】
2004047052.tif 000021
【図２０】
2004047052.tif 000022
【国際調査報告】
2004047052.tif 000023
2004047052.tif 000024