(57)【特許請求の範囲】
【請求項１】
演算処理回路と記憶回路とそれらを接続する信号線とを含む秘密情報の処理装置において，
処理対象となるデータに対する群演算を，秘密情報によって規定された回数，繰り返し行う演算による処理結果と同一の処理結果を得るように構成された秘密情報の処理装置であって，
前記記憶回路は，プログラムと，第１の秘密情報生成情報と，第２の秘密情報生成情報と，を備え，
前記第１の秘密情報生成情報と前記第２の秘密情報生成情報は，それぞれが前記秘密情報とは異なり，かつ，法ｎにおける前記第１の秘密情報生成情報と前記第２の秘密情報生成情報との差が前記秘密情報となり，
前記演算処理回路は，前記プログラムを実行することにより，
前記第１の秘密情報生成情報と，前記第２の秘密情報生成情報と，前記処理対象となるデータと，を用いた，前記群演算を繰り返し行う演算を行い，前記秘密情報を，前記演算処理回路と，前記記憶回路と，前記信号線と，に出現させることなく，前記同一の処理結果を出力する秘密情報生成情報処理手段と，
第３の秘密情報生成情報と第４の秘密情報生成情報とを生成する変換手段と，を実現し，
前記秘密情報生成情報処理手段は，前記第１の秘密情報生成情報の一部分を構成する第１の部分ビット情報と，前記第２の秘密情報生成情報の一部分を構成し，かつ，ビット位置が前記第１の部分ビット情報と同じ第２の部分ビット情報と，を参照した前記群演算を，前記第１の秘密情報生成情報と前記第２の秘密情報生成情報の全ビットを参照するように繰り返すことにより，前記第１の秘密情報生成情報と前記第２の秘密情報生成情報とを用いた前記群演算を行い，
前記変換手段は，
前記第１の秘密情報生成情報を変換した，当該第１の秘密情報生成情報とは異なる前記第３の秘密情報生成情報と，
前記第２の秘密情報生成情報を変換した，当該第２の秘密情報生成情報とは異なる前記第４の秘密情報生成情報とを，
法ｎにおける前記第３の秘密情報生成情報と前記第４の秘密情報生成情報の差が前記秘密情報となるように，生成し，
生成した前記第３の秘密情報生成情報と前記第４の秘密情報生成情報とを，新たな第１の秘密情報生成情報と前記第２の秘密情報生成情報として前記記憶回路に格納する処理を，所定の時期に実行する
ことを特徴とする秘密情報の処理装置。
【請求項２】
請求項１記載の秘密情報の処理装置において，
前記演算処理回路が実行する前記プログラムが実現する前記秘密情報生成情報処理手段は，
前記第１の部分ビット情報と，前記第２の部分ビット情報と，を参照した前記群演算の後に，
前記第１の秘密情報生成情報に含まれ，参照した前記第１の部分ビット情報と連続するビット位置にあり，かつ，未だ参照されていない部分ビット情報を新たな第１の部分ビット情報とし，前記第２の秘密情報生成情報に含まれ，ビット位置が前記第１の部分ビット情報と同じであり，かつ参照した前記第２の部分ビット情報と連続しており，さらに，未だ参照されていない部分ビット情報を新たな第２の部分ビット情報として，前記群演算を繰り返す
ことを特徴とする秘密情報の処理装置。
【請求項３】
請求項１または２に記載の秘密情報の処理装置において，
前記所定の時期とは，前記秘密情報生成情報処理手段による処理前または処理後，または，予め定めた時期，または，ランダムに決められた時期である
ことを特徴とする秘密情報の処理装置。
【請求項４】
請求項１ないし３いずれか一に記載の秘密情報の処理装置において，
前記秘密情報は，公開鍵暗号技術における，復号化またはディジタル署名を生成するための秘密鍵である
ことを特徴とする秘密情報の処理装置。
【請求項５】
演算処理回路に実行されることにより，秘密情報の処理装置を実現させる秘密情報の処理プログラムを格納するメモリであって，
第１の秘密情報生成情報と，第２の秘密情報生成情報と，を格納しており，
前記第１の秘密情報生成情報と前記第２の秘密情報生成情報は，それぞれが前記秘密情報とは異なり，かつ，法ｎにおける前記第１の秘密情報生成情報と前記第２の秘密情報生成情報との差が前記秘密情報となり，
前記演算処理回路が前記秘密情報の処理プログラムを実行することにより実現される秘密情報の処理装置は，処理対象となるデータに対する群演算を，前記秘密情報によって規定された回数，繰り返し行う演算による処理結果と同一の処理結果を得るように構成され，
前記秘密情報の処理プログラムは，前記演算処理回路に実行されることにより，
前記第１の秘密情報生成情報と，前記第２の秘密情報生成情報と，前記処理対象となるデータと，を用いた，前記群演算を繰り返し行う演算を行い，前記秘密情報を，前記演算処理回路と，前記演算処理回路に接続された信号線と，に出現させることなく，前記同一の処理結果を出力する秘密情報生成情報処理手段と，
第３の秘密情報生成情報と第４の秘密情報生成情報とを生成する変換手段と，を実現させ，
前記秘密情報生成情報処理手段は，前記第１の秘密情報生成情報の一部分を構成する第１の部分ビット情報と，前記第２の秘密情報生成情報の一部分を構成し，かつ，ビット位置が前記第１の部分ビット情報と同じ第２の部分ビット情報と，を参照した前記群演算を，前記第１の秘密情報生成情報と前記第２の秘密情報生成情報の全ビットを参照するように繰り返すことにより，前記第１の秘密情報生成情報と前記第２の秘密情報生成情報とを用いた前記群演算を行い，
前記変換手段は，
前記第１の秘密情報生成情報を変換した，当該第１の秘密情報生成情報とは異なる前記第３の秘密情報生成情報と，
前記第２の秘密情報生成情報を変換した，当該第２の秘密情報生成情報とは異なる前記第４の秘密情報生成情報とを，
法ｎにおける前記第３の秘密情報生成情報と前記第４の秘密情報生成情報の差が前記秘密情報となるように，生成し，
生成した前記第３の秘密情報生成情報と前記第４の秘密情報生成情報とを，新たな第１の秘密情報生成情報と前記第２の秘密情報生成情報として前記記憶回路に格納する処理を，所定の時期に実行する
ことを特徴とする秘密情報の処理プログラムを格納するメモリ。
【請求項６】
請求項５に記載の秘密情報の処理プログラムを格納するメモリにおいて，
前記秘密情報の処理プログラムを実行することにより実現される前記秘密情報生成情報処理手段は，
前記第１の部分ビット情報と，前記第２の部分ビット情報と，を参照した前記群演算の後に，
前記第１の秘密情報生成情報に含まれ，参照した前記第１の部分ビット情報と連続するビット位置にあり，かつ，未だ参照されていない部分ビット情報を新たな第１の部分ビット情報とし，前記第２の秘密情報生成情報に含まれ，ビット位置が前記第１の部分ビット情報と同じであり，かつ参照した前記第２の部分ビット情報と連続しており，さらに，未だ参照されていない部分ビット情報を新たな第２の部分ビット情報として，前記群演算を繰り返す
ことを特徴とする秘密情報の処理プログラムを格納するメモリ。
【請求項７】
請求項５または６に記載の秘密情報の処理プログラムを格納するメモリにおいて，
前記所定の時期とは，前記秘密情報生成情報処理手段による処理前または処理後，または，予め定めた時期，または，ランダムに決められた時期である
ことを特徴とする秘密情報の処理プログラムを格納するメモリ。
【請求項８】
請求項５ないし７いずれか一に記載の秘密情報の処理プログラムを格納するメモリにおいて，
前記秘密情報は，公開鍵暗号技術における，復号化またはディジタル署名を生成するための秘密鍵である
ことを特徴とする秘密情報の処理プログラムを格納するメモリ。
【発明の詳細な説明】
技術分野
本発明は，情報のセキュリティを確保する技術に関する。
背景技術
ＩＣカードは，その構造上，内部に対する情報の読み書きがＩＣカード自身が持つ演算処理部の制御の下で行われるため，磁気カード等と比較して安全に情報を管理することができ，それゆえ，秘密にすべき情報を安全に管理するための手段としての利用が注目されている。今後，例えば，暗号文を復号する機能およびそのために必要な鍵情報をもったＩＣカードや，電子的なデータに対するディジタル署名を生成する機能およびそのために必要な鍵情報をもったＩＣカードなどの利用がさらに広がることが期待されている。
公開鍵やディジタル署名といった誰もが知ることができる情報から，計算によって，秘密鍵を知ることは，計算量的に，非常に困難であり，実際上不可能であることが知られている。
その一方で，ＩＣカードなどの上記暗号化，復号化，署名作成などの機能を持った装置（ｓｅｃｕｒｅ  ｃｒｙｐｔｏｇｒａｐｈｉｃ  ｄｅｖｉｃｅという）に対する新たな脅威として，内部にある重要な情報（例えば秘密鍵）を，物理的に直接解析をすることなく，通常の使用方法における処理時間，消費電流，発生する電磁波等をｄｅｖｉｃｅの外部から解析することによって，推定しようとするＴＡ（Ｔｉｍｉｎｇ  Ａｔｔａｃｋ），ＤＰＡ（Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ），ＳＰＡ（Ｓｉｍｐｌｅ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ）などの攻撃法の可能性が示唆されるようになっている。たとえば，これらの攻撃により，署名作成のための秘密鍵が解析されると，悪意のある人が正当な所有者になりすますことが可能になるなど影響が大きく，対策が求められている。
ＩＣカードについては，
文献［Ｈａｎｄｂｏｏｋ］Ｒａｎｋｌ  Ｅｆｆｉｎｇ，”Ｓｍａｒｔ  Ｃａｒｄ  Ｈａｎｄｂｏｏｋ”，Ｊｏｈｎ  Ｗｉｌｅｙ＆Ｓｏｎｓ，１９９７
に開示されている。
ｓｅｃｕｒｅ  ｃｒｙｐｔｏｇｒａｐｈｉｃ  ｄｅｖｉｃｅについては，
文献［ＩＳＯ１３４９１］ＩＳＯ１３４９１−１”Ｂａｎｋｉｎｇ  Ｓｅｃｕｒｅ  ｃｒｙｐｔｏｇｒａｐｈｉｃ  ｄｅｖｉｃｅｓ（ｒｅｔａｉｌ）  Ｐａｒｔ  １：Ｃｏｎｃｅｐｔｓ，ｒｅｑｕｉｒｅｍｅｎｔｓ  ａｎｄ  ｅｖａｌｕａｔｉｏｎ  ｍｅｔｈｏｄｓ”，Ｆｉｒｓｔ  ｅｄｉｔｉｏｎ  １９９８  ０６−１５
に開示されている。
また，ＴＡ（Ｔｉｍｉｎｇ  Ａｔｔａｃｋ），ＤＰＡ（Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ），ＳＰＡ（Ｓｉｍｐｌｅ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ）などのアタックについては，前記文献［Ｈａｎｄｂｏｏｋ］の他，
文献［ＤＰＡ］Ｐａｕｌ  Ｋｏｃｈｅｒ，Ｊｏｓｈｕａ  Ｊａｆｆｅ  ａｎｄ  Ｂｅｎｊａｍｉｎ  Ｊｕｎ，”Ｉｎｔｒｏｄｕｃｔｉｏｎ  ｔｏ  Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ  ａｎｄ  Ｒｅｌａｔｅｄ  Ａｔｔａｃｋｓ”，１９９８文献［ＴＡ］Ｐａｕｌ  Ｋｏｃｈｅｒ，”Ｔｉｍｉｎｇ  Ａｔｔａｃｋｓ  ｏｎ  Ｉｍｐｌｅｍｅｎｔａｔｉｏｎｓ  ｏｆ  Ｄｉｆ−ｆｉｅ−Ｈｅｌｌｍａｎ，ＲＳＡ，ＤＳＳ，ａпｄ  Ｏｔｈｅｒ  Ｓｙｓｔｅｍｓ”，ＣＲＹＰＴＯ’９６，１９９６
に開示されている。
上記各攻撃法は，間接的に得られる測定結果と内部情報とが相関を持つことを根拠とするものである。
ＲＳＡ暗号の復号化機能をもつＩＣカードへのＴｉｍｉｎｇ  Ａｔｔａｃｋに対する対策として，上記文献［ＴＡ］には，ブラインド署名という技術を応用した対策案が示されている。これは，Ｔｉｍｉｎｇ  Ａｔｔａｃｋを実行する際に必要となるサンプルデータを採りにくくするために，入力として与えられる暗号文を直接復号するのではなく，暗号文に乱数情報を加えたものを復号し，最後に再び乱数による影響を取り払うことにより，復号文を得る手法である。しかしながら依然として，あるデータを秘密鍵乗するという処理が含まれている点で充分でない。
発明の開示
本発明は，上記課題に鑑みてなされたものであり，ＩＣカード等のｓｅｃｕｒｅ  ｃｒｙｐｔｏｇｒａｐｈｉｃ  ｄｅｖｉｃｅ内の秘密情報を推定できないようにする手段，技術を提供することを目的とする
すなわち，本発明は，ＩＣカード等のｓｅｃｕｒｅ  ｃｒｙｐｔｏｇｒａｐｈｉｃ  ｄｅｖｉｃｅに対するＴＡ（Ｔｉｍｉｎｇ  Ａｔｔａｃｋ），ＤＰＡ（Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ），ＳＰＡ（Ｓｉｍｐｌｅ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ）等の攻撃法を無効とする手段，技術を提供することを目的とする。
さらに，これらの手段，技術を利用したＩＣカード，セキュリティモジュール，半導体チップ，システム，コンピュータ，プログラムを提供することを目的としている。
上記目的を達成するために，本発明は，演算処理回路と記憶回路とそれらを接続する信号線とで構成した秘密情報の処理装置において，秘密情報と処理対象となるデータとを既知の処理方法に基づいて処理した処理結果と同一の処理結果を得るように構成された秘密情報の処理方法であって，上記秘密情報とは異なる秘密情報生成情報と，上記秘密情報生成情報と上記処理対象となるデータとを用い同一の上記処理結果を出力する秘密情報生成情報処理手段とを用いることを特徴とするものである。
さらに，本発明の秘密情報生成情報処理手段は，上記秘密情報を上記演算処理回路や上記記憶回路や上記信号線に出現させることなく処理を行うことを特徴とするものである。
具体的な一例としては，秘密情報は，暗号文の復号や署名生成のための秘密鍵であり，秘密情報処理手段は，暗号化または署名生成の既知アルゴリズムを実現する手段であり，処理結果は，復号化された平文や生成された署名である。秘密鍵とは異なる秘密情報生成情報と，それを用いて，平文や署名を処理結果として出力する秘密情報生成情報処理手段とを用いることにより，秘密情報を外部から知ることが困難になる。
さらに，本発明は，同一の秘密情報生成情報処理手段が処理する秘密情報生成情報は，取りうる値が複数あるように構成する。
具体的には，本発明の上記記憶回路は，上記秘密情報生成情報を，その組み合わせが複数ある，複数の秘密情報部分情報として構成し，上記記憶回路に保持することを特徴とするものである。
これらの手段を採用することにより，秘密情報そのものは，内部の記憶手段に保持されているときや，記憶手段と演算手段との間を装置内部の信号線（内部バス）を介して送られるとき，演算手段において，上記処理手段によって処理されるとき，いずれの場合においても，出現することが無い。したがって秘密情報をそのものを得ることが困難になる。さらに，秘密情報生成情報は，それと組み合わせて用いる秘密情報生成情報処理手段によって所望の結果を得ることができるので，当該情報だけを得たとしても秘密情報を得たことにはならない。さらに，不正に秘密情報を入手しようとする攻撃者が秘密情報生成情報処理手段を知ったとしても，秘密情報生成情報として取りうるデータが複数通りある時には，攻撃者にとって必要な試行回数が増加するため，秘密情報を得ることがさらに困難になる。
したがって，かかる時間，発生する電磁波の強さおよび消費電流等から秘密情報そのものを得ることが困難になる。
また，上記目的を達成するために，間接的に得られる測定結果と内部情報との相関関係を少なくする手段を設ける。
より具体的には，本発明では次の手段を用いる。
（１）秘密裏に保持すべき情報を利用した演算において，前記情報を表す複数の表現を演算ごとに使い分ける
（２）ある表現方法で記憶装置内に保持された秘密にすべき情報を，その情報を利用した演算が行われる度に，あるいは，あらかじめ決められた時期に，あるいは，ランダムに決められた時期に，別の表現に変換し，変換された新たな表現により元の表現を書き換える
（３）秘密裏に保持すべき情報Ａとそれとは異なる情報Ｂを利用した演算において，前記情報Ｂを表す複数の表現を演算ごとに使い分ける
（４）秘密にすべき情報Ａを利用した演算に使われる情報であって，ある表現方法で記憶装置内に保持された前記秘密にすべき情報Ａとは異なる情報Ｂを，前記秘密にすべき情報Ａを利用した演算が行われる度に，あるいは，あらかじめ決められた時期に，あるいは，ランダムに決められた時期に，別の表現に変換し，変換された新たな表現により元の表現を書き換える
すなわち，本発明の上記記憶回路は，上記秘密情報生成情報を他の秘密情報生成情報へ変換する変換手段をさらに備え，上記他の秘密情報生成情報は，上記秘密情報生成情報処理手段が上記処理結果と同一の処理結果を出力させる情報であることを特徴とするものである。
さらに，本発明の上記演算処理回路は，上記変換手段を，所定の時期に実行することを特徴とするものである。
上記手段を採用することにより，前記秘密にすべき情報Ａを利用する演算が実行される際にかかる時間，発生する電磁波の強さおよび消費電流等が，一定にならないようにし，結果として，前記前記秘密にすべき情報Ａと，情報Ａを利用する演算にかかる時間，発生する電磁波の強さおよび消費電流との間の関連（相関関係）を少なくする。
なお，上記秘密情報生成情報処理手段や変換手段は，具体的な一例としては，プログラムであり，ディジタル信号処理プロセッサ（ＤＳＰという），中央演算処理回路（ＣＰＵという）などの演算手段によって実行されるものである。
また，本発明は，上述の秘密情報の処理装置を用いて，上記秘密情報を用いた処理結果を送受信する秘密情報の処理システムであって，上記処理結果の受信者側装置は，上記秘密情報生成情報処理手段と上記秘密情報生成情報とを，上記処理装置の上記記憶回路に設定する手段を備え，処理装置の使用者側装置は，上記処理装置に処理対象となるデータを入力する手段と，上記処理装置から上記処理結果を受け取る手段と，上記受け取った処理結果を上記受信者側装置へ送信する手段とを備えることを特徴とするものである。
発明を実施するための最良の形態
・第１の実施例
本発明を，楕円曲線暗号の一種である  Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｃｈｅｍｅ（ＥＣＥＳ）の復号化機能を持ったＩＣカードに適用した一実施例を，以下，図を用いて説明する。Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｃｈｅｍｅについては，文献［Ｘ９．６３］に述べられている。
楕円曲線暗号については，
文献［Ｘ９．６３］”Ｗｏｒｋｉｎｇ  Ｄｒａｆｔ：ＡＭＥＲＩＣＡＮ  ＮＡＴＩＯＮＡＬ  ＳＴＡＮＤＡＲＤ  Ｘ９．６３−１９９ｘ  Ｐｕｂｌｉｃ  Ｋｅｙ  Ｃｒｙｐｔｏｇｒａｐｈｙ  Ｆｏｒ  Ｔｈｅ  Ｆｉｎａｎｃｉａｌ  Ｓｅｒｖｉｃｅｓ  Ｉｎｄｕｓｔｒｙ：Ｋｅｙ  Ａｇｒｅｅｍｅｎｔ  ａｎｄ  Ｋｅｙ  Ｔｒａｎｓｐｏｒｔ  Ｕｓｉｎｇ  Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｃｒｙｐｔｏｇｒａｐｈｙ”，Ａｍｅｒｉｃａｎ  Ｎａｔｉｏｎａｌ  Ｓｔａｎｄａｒｄｓ  Ｉｎｓｔｉｔｕｔｅ，Ｊａｎｕａｒｙ  ９，１９９９
文献［ＩＥＥＥＰ１３６３］”Ｓｔａｎｄａｒｄ  Ｓｐｅｃｉｆｉｃａｔｉｏｎｓ  Ｆｏｒ  Ｐｕｂｌｉｃ  Ｋｅｙ  Ｃｒｙｐｔｏｇｒａｐｈｙ（Ｄｒａｆｔ  Ｖｅｒｓｉｏｎ  ９）”ＩＥＥＥ  Ｐ１３６３  Ｓｔａｎｄａｒｄ，ＩＥＥＥ，Ｆｅｂｒａｒｙ  ８，１９９９
に開示されている。
なお，本実施例において，上記秘密裏に保存すべき情報（秘密情報）に該当する情報は，楕円曲線暗号の復号に利用される秘密鍵である。また本実施例では，素数位数の有限体上の楕円曲線を利用するものとする。
第１図は，本実施例におけるＩＣカードのハードウェア構成図である。ＩＣカード１００１は，ＣＰＵ等で構成する演算処理部１００２，記憶回路（メモリ）で構成するデータ格納部１００４とプログラム格納部１００５，インターフェイス回路で構成するＩ／Ｏ１００６，およびこれら各構成要素を内部で接続するバス１００３とからなる。
プログラム格納部１００５には，表現変換プログラム１０１０と，楕円曲線暗号復号プログラム１０１１と，共通鍵暗号復号プログラム１０１２が保存されており，それぞれ，演算処理部１００２に読み出され，実行される。
データ格納部１００４には，楕円曲線暗号におけるシステム鍵１００９が保存されている。システム鍵は，楕円曲線暗号で利用する楕円曲線を決めるためのデータであり，あらかじめ，暗号化されたメッセージのやり取りに携わるシステム全体に対し，共通な値として，公開されている。システム鍵は次のような値を含む。すなわち，楕円曲線の定義式ｙ２＝ｘ３＋ａｘ＋ｂの係数ａおよびｂ，前記楕円曲線の定義される有限体の位数ｐ，ベースポイントと呼ばれる前記楕円曲線上の固定された点Ｐの座標，前記ベースポイントＰの位数ｎ，ｎ×ｈが前記楕円曲線上の有理点の個数と等しくなるようなコファクターと呼ばれる数ｈ，を含む。
またデータ格納部１００４には，さらに，楕円曲線暗号の復号に利用される秘密鍵ｄを表すデータ（秘密情報生成情報）が保存されている。ここで特徴的なことは，秘密鍵ｄそのものがデータ格納部に保存されているわけではない，ということである。本実施例においては，秘密情報生成部分情報である秘密鍵部分情報ｄＡ１００７と秘密鍵部分情報ｄＢ１００８の組により，秘密情報生成情報が表現されている。より具体的には，ｄＡ１００７とｄＢ１００８の法ｎにおける差が秘密鍵ｄの値と等しくなるようになっていて，さらに秘密情報生成情報処理手段に相当する楕円曲線暗号復号プログラム１０１１は，これらを正しく処理できるように構成されている。ｄＡ１００７とｄＢ１００８の組み合わせは複数あり，例えば，ｄＡ１００７の値を秘密鍵ｄそのものの値とし，ｄＢ１００８の値を０（ゼロ）とすれば，このｄＡ１００７とｄＢ１００８の組は，秘密鍵ｄの表現の一例となる。また，ｄＡ１００７の値を０（ゼロ）とし，ｄＢ１００８の値をｎ−ｄ（ｍｏｄ  ｎ）とすれば，これも秘密鍵ｄの前記とは異なる表現の一例となる。
以下，各プログラムの動作の概略を説明する。
まず，楕円曲線暗号復号プログラム１０１１による，楕円曲線暗号の復号処理について説明する。楕円曲線暗号復号プログラム１０１１は，データ格納部１００４に保存されたシステム鍵１００９によって決定される楕円曲線上の演算を含むプログラムであり，ＩＣカード１００１の外部から入力として与えられた復号用点Ｒ１０１３，および，データ格納部１００４に保存された秘密鍵を表す情報，すなわち本実施例においては，秘密鍵ｄを求めることなく，秘密鍵情報の一表現である秘密鍵部分情報ｄＡ１００７と秘密鍵部分情報ｄＢ１００８から，楕円曲線上の点ｄＲを計算し，暗号化されたメッセージｍ１０１４を共通鍵暗号復号プログラム１０１２で復号するために必要となる復号用共通鍵を計算するプログラムである。このプログラムの出力として得られた復号用共通鍵は，共通鍵暗号復号プログラム１０１２の入力の一部となる。
次に，共通鍵暗号復号プログラム１０１２による，暗号メッセージの復号処理について説明する。共通鍵暗号復号プログラム１０１２は，楕円曲線暗号復号プログラム１０１１の出力として得られた復号用共通鍵およびＩＣカード１００１の外部から入力として与えられた暗号化されたメッセージｍ１０１４を入力とし，暗号化されたメッセージｍ１０１４を復号し，その結果をＩＣカード１００１の外部へ，復号化されたメッセージｍ’１０１５として出力するプログラムである。
なお，本実施例においては，共通鍵暗号復号プログラム１０１２による共通鍵暗号復号処理はＩＣカード１００１内で行うものとしたが，この処理はＩＣカード１００１と情報のやり取りができる外部の装置，例えば，ＩＣカード１００１とＩＣカードリーダライタを通じて情報のやり取りができるＰＣ等で行ってもよい。この場合は，ＩＣカード１００１に対する入力は，復号用点Ｒ１０１３となり，ＩＣカード１００１からの出力は，楕円曲線暗号復号プログラムの出力である復号用共通鍵となる。
ＩＣカード１００１を使った時の暗号化されたメッセージｍ１０１４を復号する時の，上記の３つのプログラムによる基本的な動作の流れをまとめると次のようになる。
まず，楕円曲線暗号復号プログラム１０１１が，ＩＣカード１００１の外部からの入力である復号用点Ｒ１０１３と，データ格納部１００４に保存された秘密鍵部分情報ｄＡ１００７と秘密鍵部分情報ｄＢ１００８から，秘密鍵情報ｄを求めることなく復号用共通鍵を計算する。次に共通鍵暗号復号プログラム１０１２が，楕円曲線暗号復号プログラム１０１１によって計算された復号用共通鍵を使って，ＩＣカード１００１の外部からの入力である暗号化されたメッセージｍ１０１４を復号し，復号化されたメッセージｍ’１０１５として出力する。
これにより，暗号化されたメッセージｍを復号することができる。
このように秘密鍵ｄがデータ格納部１００４，バス１００３，演算処理部１００２に出現することなく暗号化されたメッセージｍを復号することができるので，ＴＡ（Ｔｉｍｉｎｇ  Ａｔｔａｃｋ），ＤＰＡ（Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ），ＳＰＡ（Ｓｉｍｐｌｅ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ）等によって秘密鍵の値を推定することが困難になっている。
この例では，データ格納部１００４に保存された秘密鍵部分情報ｄＡ１００７と秘密鍵部分情報ｄＢ１００８の値が固定されている。したがって，復号を行うたびに，固定値である秘密鍵部分情報ｄＡ１００７と秘密鍵部分情報ｄＢ１００８がデータ格納部１００４からバス１００３を介して演算処理部１００２に毎回流れることになり，また，楕円曲線暗号復号プログラム１０１１は，毎回同じ計算を行うことになるため，この間の計算時間や発生する電磁波の強さや消費電流等も同じになる。このことはＴＡ（Ｔｉｍｉｎｇ  Ａｔｔａｃｋ），ＤＰＡ（Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ），ＳＰＡ（Ｓｉｍｐｌｅ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ）等によって秘密鍵部分情報の値を推定される可能性があることを意味する。
本発明では，これらの攻撃に対するさらなる対策として，表現変換プログラム１０１０を利用する。
表現変換プログラム１０１０による，秘密鍵情報の表現の変換処理について説明する。表現変換プログラム１０１０は，データ格納部１００４から読み出された秘密鍵情報の一表現を，別表現に変換し，この新たな表現を，データ格納部１００４中の元の表現と置き換える（書き換える）プログラムである。本実施例においては，表現変換プログラム１０１０は，データ格納部１００４から読み出された秘密鍵情報の一表現である秘密鍵部分情報ｄＡ１００７と秘密鍵部分情報ｄＢ１００８の組から，あらたに別の表現，秘密鍵部分情報ｄＡ’と秘密鍵部分情報ｄＢ’の組を生成し，データ格納部１００４中にある元の表現ｄＡ１００７とｄＢ１００８を，新しい表現ｄＡ’とｄＢ’で書き換えるプログラムとなる。
表現変換プログラム１０１０を実行することにより，秘密鍵部分情報ｄＡ１００７と秘密鍵部分情報ｄＢ１００８の値が別の値に書き換わるため，データ格納部１００４からバス１００３を介して演算処理部１００２へ流れるデータ，楕円曲線暗号復号プログラム１０１１を演算処理部１００２で実行した時の時間，発生する電磁波の強さや消費電流等が異なったものとなる。これにより，ＴＡ（Ｔｉｍｉｎｇ  Ａｔｔａｃｋ），ＤＰＡ（Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ），ＳＰＡ（Ｓｉｍｐｌｅ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ）等による秘密鍵の値の推定をさらに困難にすることが可能となる。
表現変換プログラム１０１０は，楕円曲線暗号復号プログラム１０１１が実行される直前に毎回実行されてもよいし，楕円曲線暗号復号プログラム１０１１が実行された直後に毎回実行されてもよい。あるいは楕円曲線暗号復号プログラム１０１１が何回か実行される毎に実行されてもよい。あるいはまた楕円曲線暗号復号プログラム１０１１の実行とは無関係に，ランダムなタイミングに実行されてもよい。楕円曲線暗号復号プログラム１０１１に対するＴＡ（Ｔｉｍｉｎｇ  Ａｔｔａｃｋ）やＤＰＡ（Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ）への対策としては，表現変換プログラム１０１０の実行頻度が多いほうが望ましい。
次に各プログラムの動作の詳細を説明する。
第２図は，第１図における表現変換プログラム１０１０のフローを示す。
ステップ２００１：はじめ
ステップ２００２：０以上ｎ未満の乱数ｋを生成する
ステップ２００３：データ格納部１００４から秘密鍵部分情報ｄＡ１００７および秘密鍵部分情報ｄＢ１００８を読み込む
ステップ２００４：ｄＡ’＝ｄＡ＋ｋ（ｍｏｄ  ｎ）およびｄＢ’＝ｄＢ＋ｋ（ｍｏｄ  ｎ）を計算する
ステップ２００５：ｄＡ’およびｄＢ’をそれぞれデータ格納部１００４中の秘密鍵部分情報ｄＡ１００７および秘密鍵部分情報ｄＢ１００８が書かれていたところに書き込む
ステップ２００６：おわり
第３図は，第１図における楕円曲線暗号復号プログラム１０１１のフローを示す。
ステップ３００１：はじめ
ステップ３００２：Ｑ＝Ｏ（無限遠点）とする
ステップ３００３：ＩＣカード１００１の外部から復号用点Ｒ１０１３を読み込む
ステップ３００４：データ格納部１００４から秘密鍵部分情報ｄＡ１００７および秘密鍵部分情報ｄＢ１００８を読み込む
ステップ３００５：ｉ＝｜ｎ｜とする（｜ｎ｜はベースポイントＰの位数ｎのビット長）
ステップ３００６：（ｄＡ１００７の第ｉビット目，ｄＢ１００８の第ｉビット目）＝（１，０）ならステップ３００８へ（ここで第ｉビット目とは，最下位ビットを第１ビット目とし，上位に向かうほど大きくなるように数えるものとする）
ステップ３００７：（ｄＡ１００７の第ｉビット目，ｄＢ１００８の第ｉビット目）＝（０，１）ならステップ３０１０へ，そうでなければステップ３００９へ（ここで第ｉビット目とは，最下位ビットを第１ビット目とし，上位に向かうほど大きくなるように数えるものとする）
ステップ３００８：Ｑ＝Ｑ＋Ｒとしてステップ３０１０へ（ここで＋は楕円曲線上の点の加算を示す）
ステップ３００９：Ｑ＝Ｑ−Ｒとしてステップ３０１０へ（ここで−は楕円曲線上の点の減算を示す）
ステップ３０１０：ｉ＝ｉ−１とする
ステップ３０１１：ｉ＞０ならＱ＝２Ｑとしてステップ３００６へ（ここで２Ｑは楕円曲線上の点Ｑの２倍算を示す）
ステップ３０１２：Ｑのｘ座標ｘＱを復号用共通鍵として出力する
ステップ３０１３：おわり
なお，上記ステップ３００９における楕円曲線上の点の加算，ステップ３０１０における楕円曲線上の点の減算，および，ステップ３０１２における楕円曲線上の点の２倍算の詳細については，文献［ＩＥＥＥＰ１３６３］に詳しく述べられている。
楕円曲線暗号復号プログラム１０１１の手順は，秘密鍵ｄの表現，秘密鍵部分情報ｄＡ１００７および秘密鍵部分情報ｄＢ１００８がそれぞれｄＡ＝ｄ，ｄＢ＝０となっている時には，バイナリ法と呼ばれる楕円曲線上の点のスカラー倍ｄＲを求めるために広く使われている方法と同じ手順となる。また，秘密鍵ｄの表現，秘密鍵部分情報ｄＡ１００７および秘密鍵部分情報ｄＢ１００８が，（ｄＡ１００７の第ｉビット目，ｄＢ１００８の第ｉビット目）＝（１，０）または（０，１）となるようなビットの組が最も少なくなる表現となっている時には，楕円曲線上の点のスカラー倍ｄＲを高速に求める手法として知られている，最適なａｄｄｉｔｉｏｎ−ｓｕｂｔｒａｃｔｉｏｎ  ｃｈａｉｎを使った楕円曲線上の点のスカラー倍演算方法による演算，と同じ手順となる。
このように，秘密鍵ｄの複数の表現方法を使い分けることは，楕円曲線上の点のスカラー倍演算ｄＲを求める演算方法として，知られている様々な演算方法を使い分けて演算することを意味している。結果的に，この楕円曲線暗号復号プログラム１０１１の実行時間や発生する電磁波の強さや消費電流等はその表現方法毎に異なることになる。平均的には，バイナリ法を使った場合と同程度の処理時間となることが期待される。
ａｄｄｉｔｉｏｎ−ｓｕｂｔｒａｃｔｉｏｎ  ｃｈａｉｎを使った楕円曲線上の演算方法については，
文献［ＡＤＤ−ＳＵＢ］Ｆ．Ｍｏｒａｉｎ  ａｎｄ  Ｊ．Ｏｌｉｖａｓ“Ｓｐｅｅｄｉｎｇ  ｕｐ  ｔｈｅ  ｃｏｍｐｕｔａｔｉｏｎｓ  ｏｎ  ａｎ  ｅｌｌｉｐｔｉｃ  ｃｕｒｖｅ  ｕｓｉｎｇ  ａｄｄｉｔｉｏｎ  ｓｕｂｔｒａｃｔｉｏｎ  ｃｈａｉｎｓ”  Ｔｈｅｏｒｅｔｉｃａｌ  Ｉｎｆｏｒｍａｔｉｃｓ  ａｎｄ  Ａｐｐｌｉｃａｔｉｏｎｓ  ｖｏｌ．２４，ｎｏ．６，１９９０
に述べられている。
本実施例においては秘密鍵，それ自身を適当な機会に異なる表現方法によって保持し直すことにより，ＩＣカード内には前記秘密にすべき情報そのものや，それに関する情報の固定された値は存在しないことになる。したがって例えば，攻撃者がデータ格納部１００４に保存されたデータが演算処理部１００２へうけわたされる時に情報が流れるバス１００３の部分を解析できたとしても，流れる情報から秘密にすべき情報を推定することは困難になる。
さらに，もし何らかの手段によって，データ格納部１００４に保存されたデータの一部が攻撃者によって解析されたとしても，必ずしも，秘密にすべき情報をもらしたことにはならない。すなわち，秘密にすべき情報それ自身が固定された値としてデータ格納部１００４に保存されている場合には，その値の１ビットの情報が漏れたというのは秘密にすべき情報に関する情報の一部が漏れたことにほかならないが，本発明にしたがって，秘密にすべき情報それ自身ではなく，それを表すある表現によって保持しておく場合には，たとえ，秘密にすべき情報ｄの表現であって，実際にデータ格納部１００４に保存されているデータであるｄＡとｄＢの組のうち，その半分にあたるｄＡの値が完全に漏れたとしても，秘密にすべき情報ｄそのものに関しては，情報を漏らしていないことになる。
なぜなら，ｄをどのような部分情報で，どのように表現しているかということを知らないからであるし，たとえｄＡとｄＢの組でｄを表していることを知っているとしても，ｄＢの値やｄＡとｄＢの組でどのようにｄを表すかを知らないものにとっては，ｄとｄＡとの間には何の関係も見出すことができないからである。
加えて，本発明では秘密にすべき情報を適切な時期に異なる表現方法によって保持し直しているので，攻撃者が後に，別の時点におけるｄＢの値を知ったとしても，互いに異なる時点におけるｄＡとｄＢとの間にはやはり何の関係も見出すことができないので，ｄに関する情報は漏れることはない。
第４図は，第１図における共通鍵暗号復号プログラム１０１２のフローを示す。
ステップ４００１：はじめ
ステップ４００２：復号用共通鍵ｃおよび暗号化されたメッセージｍ１０１４を入力する。ここで復号用共通鍵ｃとは，楕円曲線暗号復号プログラム１０１１のステップ３０１１で出力された復号用共通鍵ｘＱのことである
ステップ４００３：復号用共通鍵ｃと，暗号化されたメッセージｍ１０１４のビット長Ｌを，’ｋｅｙ  ｄｅｒｉｖａｔｉｏｎ  ｆｕｎｃｔｉｏｎ’への入力とし，出力として，長さＬのマスク列Ｍを得る。ここで，’ｋｅｙ  ｄｅｒｉｖａｔｉｏｎ  ｆｕｎｃｔｉｏｎ’とは，復号用共通鍵ｃと出力されるマスク列の長さＬを入力として指定すると，長さＬのマスク列を出力するような関数であり，共通鍵暗号復号プログラム１０１２の一部として実装されているものとする。’ｋｅｙ  ｄｅｒｉｖａｔｉｏｎ  ｆｕｎｃｔｉｏｎ’の詳細については，文献［Ｘ９．６３］に述べられている
ステップ４００４：暗号化されたメッセージｍ１０１４とマスク列Ｍの排他的論理和（ｍ’ＸＯＲ  Ｍ）を計算し，結果を復号化されたメッセージｍ’１０１５としてＩＣカード１００１の外部に出力する
ステップ４００５：おわり
本実施例においては，楕円曲線暗号の一種であるＥｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｃｈｅｍｅ（ＥＣＥＳ）の復号化機能を持ったＩＣカードに適用した例を示したが，本発明は，これ以外にも広く適用可能である。
例えば，Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｃｈｅｍｅ（ＥＣＥＳ）ではなく，Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ａｕｇｍｅｎｔｅｄ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｃｈｅｍｅ（ＥＣＡＥＳ）の復号化機能を持ったＩＣカードに適用してもよい。この場合，本実施例の処理に加えて，あらかじめ暗号化されたデータと共に送られてきたＭＡＣと呼ばれるメッセージ検証用のデータを使って，復号されたデータが正しいものであるかどうかを検証する処理が加わる。Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ａｕｇｍｅｎｔｅｄ  Ｅｎｃｒｙｐ−ｔｉｏｎ  Ｓｃｈｅｍｅ（ＥＣＡＥＳ）についての詳細は，文献［Ｘ９．６３］に述べられている。
あるいはまた，本実施例では，素数位数の有限体上の楕円曲線を利用していたが，標数２の有限体上の楕円曲線であってもよい。あるいはこれ以外の任意の有限体上の楕円曲線であってもよい。また，本実施例では，式ｙ２＝ｘ３＋ａｘ＋ｂで定義された楕円曲線を利用していたが，これ以外の式，例えばｂｙ２＝ｘ３＋ａｘ２＋ｂｘで定義された楕円曲線を利用してもよい。また，本実施例では，楕円曲線上の有理点が生成する群の上の，離散対数問題の困難性を利用した暗号を使っていたが，これ以外の群，例えば，有限体の乗法群，超楕円曲線上の因子類群，Ｃａｂ曲線上の因子類群などの群の上の離散対数問題の困難性を利用した暗号であってもよい。これらの暗号を利用する場合には，上記の楕円曲線暗号復号プログラム１０１１中の楕円曲線上の点の秘密情報に基づく演算を，それぞれの群での秘密情報に基づく演算に置きかえればよい。
さらには，これら離散対数問題の困難性を利用した暗号以外の暗号であっても，より一般的には，暗号以外であっても，ある秘密にすべき数があって，群演算をその秘密にすべき数だけ繰り返し行うような演算を含む機能を持ったＩＣカードに対しても本発明は本実施例と同様にして適用可能である。すなわち，上記の楕円曲線暗号復号プログラム１０１１では，Ｒを足すという演算を秘密にすべき数（秘密鍵ｄ）回だけ行った結果であるｄＲを求めていたが，これと同様にして秘密にすべき数をある表現によって表しておき，楕円曲線暗号復号プログラム１０１１に相当するプログラムによって，演算を行えばよい。このような暗号の例としては，上記の離散対数問題の困難性を利用した暗号以外に，例えば，ＲＳＡ暗号などがある。暗号以外の機能の例としては，ＲＳＡ署名などがある。なお，ここで，群とは，集合であって，その集合に属する各元の間にある演算が定義されているようなもののことである。
ＲＳＡ暗号・署名については，
文献［ＡＰＰＬＩＥＤ］Ｂｒｕｃｅ  Ｓｃｈｎｅｉｅｒ，”Ａｐｐｌｉｅｄ  Ｃｒｙｐｔｏｇｒａｐｈｙ”，Ｊｏｈｎ  Ｗｉｌｅｙ＆Ｓｏｎｓ，Ｉｎｃ，１９９６
に開示されている。
本実施例では，ＩＣカードに適用した例を示したが，秘密にすべき情報をより安全に保存する技術としてＩＣカード以外にも広く適用可能である。例えば同じ機能を持つ，ＩＣカード以外のｓｅｃｕｒｅ  ｃｒｙｐｔｏｇｒａｐｈｉｃ  ｄｅｖｉｃｅや，半導体チップや，ＰＣやワークステーションに対しても適用可能である。
・第２の実施例
第１の実施例において，楕円曲線暗号復号プログラム１０１１を次のように変形してもよい。
第５図は，本実施例におけるＩＣカードの構成図である。この実施例においては，第１の実施例における楕円曲線暗号復号プログラム１０１１に該当するプログラムは，次の２つのプログラム，テーブルデータ計算プログラム５００１，テーブル参照型楕円曲線暗号復号プログラム５００２からなる。
以下，各プログラムの動作の概略を説明する。
テーブルデータ計算プログラム５００１は，ＩＣカード１００１の外部から与えられる復号用点Ｒ１０１３を入力とし，テーブル参照型楕円曲線暗号復号プログラム５００２で利用されるテーブルのデータを計算し，その結果をデータ格納部１００４内のテーブルデータ５００３領域に書き込むプログラムである。このプログラムは，データ格納部１００４に含まれる秘密鍵ｄを表すデータ，すなわち本実施例おける秘密鍵部分情報ｄＡ１００７と秘密鍵部分情報ｄＢ１００８，には依存しない処理をおこなう。したがって，このプログラムがＴＡ（Ｔｉｍｉｎｇ  Ａｔｔａｃｋ），ＤＰＡ（Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ），ＳＰＡ（Ｓｉｍｐｌｅ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ）などにより攻撃されても秘密鍵ｄに関するデータが漏れる心配はない。
テーブル参照型楕円曲線暗号復号プログラム５００２は，データ格納部１００４に保存されている秘密鍵部分情報ｄＡ１００７および秘密鍵部分情報ｄＢ１００８と，テーブルデータ計算プログラム５００１によって計算されたテーブルデータ５００３から，暗号化されたメッセージｍ１０１４を共通鍵暗号復号プログラム１０１２で復号するために必要となる復号用共通鍵を計算するプログラムである。
次に各プログラムの動作の詳細を説明する。
第６図は，第５図におけるテーブルデータ計算プログラム５００１のフローを示す。
ステップ６００１：はじめ
ステップ６００２：ＩＣカード１００１の外部から復号用点Ｒ１０１３を読み込む
ステップ６００３：楕円曲線上の点３Ｒ，２Ｒ，Ｒ，−Ｒ，−２Ｒ，−３Ｒを計算する
ステップ６００４：テーブルデータ５００３を，
Ｔ［００］［００］＝    Ｏ（無限遠点），
Ｔ［００］［０１］＝  −Ｒ，
Ｔ［００］［１０］＝−２Ｒ，
Ｔ［００］［１１］＝−３Ｒ，
Ｔ「０１］［００］＝    Ｒ，
Ｔ［０１］［０１］＝    Ｏ（無限遠点），
Ｔ［０１］［１０］＝  −Ｒ，
Ｔ［０１］［１１］＝−２Ｒ，
Ｔ［１０］［００］＝  ２Ｒ，
Ｔ［１０］［０１］＝    Ｒ，
Ｔ［１０］［１０］＝    Ｏ（無限遠点），
Ｔ［１０］［１１］＝  −Ｒ，
Ｔ［１１］［００］＝  ３Ｒ，
Ｔ［１１］［０１］＝  ２Ｒ，
Ｔ［１１］［１０］＝    Ｒ，
Ｔ［１１］［１１］＝    Ｏ（無限遠点），
とし，データ格納部に保存する
ステップ６００５：おわり
第７図は，第５図におけるテーブル参照型楕円曲線暗号復号プログラム５００２のフローを示す。
ステップ７００１：はじめ
ステップ７００２：Ｑ＝Ｏ（無限遠点）とする
ステップ７００３：ＩＣカード１００１の外部から復号用点Ｒ１０１３を読み込む
ステップ７００４：データ格納部１００４から秘密鍵部分情報ｄＡ１００７および秘密鍵部分情報ｄＢ１００８を読み込む
ステップ７００５：｜ｎ｜が偶数ならｉ＝｜ｎ｜，｜ｎ｜が奇数ならｉ＝｜ｎ｜＋１とする（｜ｎ｜はベースポイントＰの位数ｎのビット長）
ステップ７００６：データ格納部１００４中のテーブルデータ５００３を参照し，Ｓ＝Ｔ［ｄＡ１００７の第ｉビット目，ｄＡ１００７の第（ｉ−１）ビット目］［ｄＢ１００８の第ｉビット目，ｄＢ１００８の第（ｉ−１）ビット目］とする（ここで第ｉビット目とは，最下位ビットを第１ビット目とし，上位に向かうほど大きくなるように数えるものとする）
ステップ７００７：Ｑ＝Ｑ＋Ｓを計算する（ここで＋は楕円曲線上の点の加算を示す）
ステップ７００８：ｉ＝ｉ−２とする
ステップ７００９：ｉ＞０ならＱ＝４Ｑとしてステップ７００６へ（ここで４Ｑは楕円曲線上の点Ｑの２倍算を２回繰り返すことによって求めることができる）ステップ７０１０：Ｑのｘ座標ｘＱを復号用共通鍵として出力する
ステップ７０１１：おわり
なお，上記ステップ７００７における楕円曲線上の点の加算，および，ステップ７００９における楕円曲線上の点の２倍算の詳細については，文献［ＩＥＥＥＰ１３６３］に詳しく述べられている。
本実施例においては，秘密鍵部分情報の連続する２ビットずつに対して演算を行ったが，これとは異なるやり方でもよい。例えば，連続する３ビットずつに対して演算を行ってもよいし，一般に連続するｔビットずつを対象としてよい。あるいは，互いにｊビットはなれた（｜ｎ｜／ｊ）個のビットを対象としてもよい。なおテーブルデータ計算プログラム５００１はこれらの秘密鍵部分情報のビットの見方に応じて適切な値を計算するプログラムに変更する必要がある。
本実施例においても，ｄＲを求める演算中に，ｄ自身の値は現れない。これによりｄＲを求める演算にかかる時間や発生する電磁波の強さや消費電流はｄそのものの値には依存しなくなる。したがってＴＡ（Ｔｉｍｉｎｇ  Ａｔｔａｃｋ），ＤＰＡ（Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ）などにより攻撃によって，秘密鍵ｄの値を推定することが困難になる。
本実施例においては，楕円曲線暗号の一種であるＥｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｃｈｅｍｅ（ＥＣＥＳ）の復号化機能を持ったＩＣカードに適用した例を示したが，本発明は，第１の実施例と同様，これ以外にも広く適用可能である。特に，あるあらかじめ決まった元に対する群演算を秘密にすべき数だけ繰り返し行うような演算を含む処理を行う装置に適用する場合には，テーブルデータ計算プログラム５００１を毎回実行する必要はなく，一度だけ実行すればよいため，毎回の処理が高速に実行可能となり一層有効である。この場合には，さらに，テーブルデータの計算を装置（本実施例の場合で言えばＩＣカード１００１）の外部で行うことも可能である。このような処理を含む装置の例としては，例えば，楕円曲線暗号における鍵生成処理を行うＩＣカードが挙げられる。この場合，乱数として生成した秘密鍵情報ｄと，固定点であるベースポイントＰから楕円曲線上の点ｄＰを求める処理が含まれる。したがって，テーブルデータは，例えば，ＩＣカードの外部で計算しておき，システム鍵情報の一部としてＩＣカード内にあらかじめ保存しておくことが可能である。
・第３の実施例
第２の実施例において，テーブルデータ５００３領域へのテーブルデータの保存方法を次のようにしてもよい。
楕円曲線上の点は通常２次元ａｆｆｉｎｅ座標を用いて，ｘ座標およびｙ座標の２つの値の組によって表現されるが，点の加算や点の２倍算を行う場合に，主として高速に演算を行う目的で，ｘ座標，ｙ座標およびｚ座標の３つの値の組によって表現することも可能である。このような表現およびこの表現を使った場合の楕円曲線上の点の演算方法の一例が文献［ＩＥＥＥＰ１３６３］にｐｒｏｊｅｃｔｉｖｅ  ｃｏｏｒｄｉｎａｔｅとして述べられている。２次元ａｆｆｉｎｅ座標による表現とｐｒｏｊｅｃｔｉｖｅ  ｃｏｏｒｄｉｎａｔｅによる表現との間の相互変換は次のように行うことができる。
［２次元ａｆｆｉｎｅ座標からｐｒｏｊｅｃｔｉｖｅ  ｃｏｏｒｄｉｎａｔｅへ］（ｘ，ｙ）−＞［ｘ，ｙ，１］［ｐｒｏｊｅｃｔｉｖｅ  ｃｏｏｒｄｉｎａｔｅから２次元ａｆｆｉｎｅ座標へ］［Ｘ，Ｙ，Ｚ］−＞（Ｘ／Ｚ２，Ｙ／Ｚ３）ここで注意すべき事は，ｐｒｏｊｅｃｔｉｖｅ  ｃｏｏｒｄｉｎａｔｅによる表現では，同じ点を表す表現は一通りではないということである。すなわち，ｔを０＜ｔ＜ｐ（ｐは楕円曲線の定義される有限体の位数）となる数とすると，点［Ｘ，Ｙ，Ｚ］と点［ｔ２Ｘ，ｔ３Ｙ，ｔＺ］は，共に同じ点（Ｘ／Ｚ２，Ｙ／Ｚ３）を表している。
第２の実施例におけるテーブルデータ５００３領域へのテーブルデータの保存方法として，このｐｒｏｊｅｃｔｉｖｅ  ｃｏｏｒｄｉｎａｔｅによる表現で保存しておくことができる。この場合，同じ点を表すデータであっても，異なる表現によって保存しておくことが可能となる。例えばＴ［１０］［００］とＴ［１１］［０１］は共に点２Ｒを表すデータが保存されているが，これら２つをそれぞれ異なる表現，すなわち，Ｔ［１０］［００］＝［Ｘ，Ｙ，Ｚ］，Ｔ［１１］［０１］＝［Ｘ’，Ｙ’，Ｚ’］（ここでＸ／Ｚ２＝Ｘ’／Ｚ’２，Ｙ／Ｚ３＝Ｙ’／Ｚ’３を満たすものとする）を使って保存しておくことにより，テーブル参照型楕円曲線暗号復号プログラム５００２の実行中にＴ［１０］［００］が参照された場合とＴ［１１］［０１］が参照された場合とで，演算処理が異なることになり，その結果，実行にかかる時間，発生する電磁波の強さおよび消費電流等も異なることになる。
第８図は，本実施例におけるＩＣカードの構成図である。本実施例では，第２の実施例に点表現変換プログラム８００１が追加されている。
以下，点表現変換プログラム８００１の概略を説明する。
点表現変換プログラム８００１はデータ格納部１００４に保存されているテーブルデータ５００３中の点の表現を変換し，変換した値によってテーブルデータ５００３を書き換える。なお，テーブルデータ５００３は，テーブルデータ計算プログラム５００１によって，ｐｒｏｊｅｃｔｉｖｅ  ｃｏｏｒｄｉｎａｔｅで表されたｘ座標，ｙ座標およびｚ座標の３つの値の組によって表現され保存されているものとする。すなわち，例えば，２次元ａｆｆｉｎｅ座標によって（ｘ，ｙ）と表現されているものを［ｘ，ｙ，１］に変換して保存してもよいし，あるいは，テーブルデータ計算プログラム５００１のステップ６００３でテーブルデータ５００３を計算する際に，ｐｒｏｊｅｃｔｉｖｅ  ｃｏｏｒｄｉｎａｔｅを使って計算を行い，その結果をｐｒｏｊｅｃｔｉｖｅ  ｃｏｏｒｄｉｎａｔｅのままテーブルデータ５００３に保存してもよい。点表現変換プログラム８００１はテーブルデータ計算プログラム５００１の実行後から，最後にテーブルデータ５００３が参照されるまでの間の任意の時点に実行されてよい。また，この間に何度実行されてもよい。例えば，テーブル参照型楕円曲線暗号復号プログラム５００２が実行される直前に実行されてもよいし，あるいは，テーブルが参照される機会が一度でものこっているのならテーブル参照型楕円曲線暗号復号プログラム５００２の実行中に割り込む形で実行されてもよい。
次に，点表現変換プログラム８００１の詳細を説明する。
第９図は，第８図における点表現変換プログラム８００１のフローを示す。
ステップ９００１：はじめ
ステップ９００２：ｉ＝００とする
ステップ９００３：ｊ＝００とする
ステップ９００４：［ｘ，ｙ，ｚ］＝Ｔ［ｉ］［ｊ］を読み込む
ステップ９００５：乱数ｋを生成する（０＜ｋ＜ｐとする。ｐは楕円曲線の定義される有限体の位数）
ステップ９００６：［ｘ，ｙ，ｚ］＝［ｋ２  ｘ（ｍｏｄ  ｐ），ｋ３  ｙ（ｍｏｄ  ｐ），ｋｚ（ｍｏｄ  ｐ）］とする（ｐは楕円曲線の定義される有限体の位数）
ステップ９００７：Ｔ［ｉ］［ｊ］＝［ｘ，ｙ，ｚ］とする
ステップ９００８：ｊ＝ｊ＋１とする（ただしｊは２進法で表記されているとする）
ステップ９００９：ｊ≦１１（２進法表記）ならステップ９００５へ
ステップ９０１０：ｊ＝００とする
ステップ９０１１：ｉ＝ｉ＋１とする（ただしｉは２進法で表記されているとする）
ステップ９０１２：ｉ≦１１（２進法表記）ならステップ９００５へ
ステップ９０１３：おわり
本実施例においては，適当なタイミングで点表現変換プログラム８００１を実行することにより，同じ点を表す複数のデータ，例えばＴ［１０］［００］とＴ［１１］［０１］は，異なる表現によって保存されることになり，また，同じデータＴ［ｉ］［ｊ］であっても，それを参照するタイミングによって異なる表現になっているため，テーブルデータ５００３を参照する演算を含む処理は，たとえ入力が毎回同じであっても，異なるものとなる。したがって，処理時間や発生する電磁波の強さや処理中の消費電流等も一定ではない。これはすなわち，秘密鍵とテーブルデータ５００３を使った演算，テーブル参照型楕円曲線暗号復号プログラム５００２の実行にかかる時間や発生する電磁波の強さや，消費電流が一定ではないことを意味する。したがってＴＡ（Ｔｉｍｉｎｇ  Ａｔｔａｃｋ），ＤＰＡ（Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ）などの攻撃によって，秘密鍵の値を推定することが困難になる。
本実施例においては，点表現変換プログラム８００１によって，テーブルデータ５００３に含まれるすべての点情報の変換を行ったが，すべての点ではなく，ランダムに選んだ１つまたは複数の点のデータだけを変換してもよい。テーブル参照型楕円曲線暗号復号プログラム５００２に対するＴＡ（Ｔｉｍｉｎｇ  Ａｔｔａｃｋ）やＤＰＡ（Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ）への対策としては，多くの点データの表現を変換したほうが望ましく，また，点表現変換プログラム８００１の実行頻度が多いほうが望ましい。
本実施例においては，楕円曲線暗号の一種であるＥｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｃｈｅｍｅ（ＥＣＥＳ）の復号化機能を持ったＩＣカードに適用した例を示したが，本発明は，第２の実施例と同様，これ以外にも広く適用可能である。
・第４の実施例
第１の実施例において，秘密にすべき情報，すなわち秘密鍵ｄは，秘密鍵部分情報ｄＡ１００７と秘密鍵部分情報ｄＢ１００８の組によって表現されていた。より具体的には，ｄＡ１００７とｄＢ１００８の法ｎにおける差が秘密鍵ｄの値と等しくなるように表現されていた。また，第１の実施例においては，，ｄＡ１００７とｄＢ１００８は，０以上ｎ未満の数として表現されていた。しかしながらこれ以外の方法で表現されていてもよい。例えばｄＡ１００７は，０以上２ｎ未満の数として表現されていてもよい。あるいは，和や差が秘密鍵ｄの値と等しくなるような３つ以上の数の組として表現されていてもよい。
あるいは，別の表現として，例えば，次のように，１，０，−１の並びとしてｄの値が表現されていてもよい。すなわち表現（Ｂｎ，Ｂｎ−１，，，，Ｂ１，Ｂ０）は，数２ｎＢｎ＋２ｎ−１Ｂｎ−１＋，，，＋２１Ｂ１＋２０Ｂ０を表すものとする。ここで，Ｂｉは，１，０，−１のいずれかであるとする。この表現は通常の２進表現の拡張になっている。すなわち，この表現方法で，Ｂｉを０か１のどちらかだけであるように制限したものが通常の２進表現である。なお，１，０，−１をメモリ上で表現するためには，２ビット分を使って，００なら０，０１なら１，１１なら−１を表す，といった方法が考えられる。
この表現を使った時には，第１の実施例における表現変換プログラム１０１０は，例えば，次のように変更される。なお，データ格納部１００４には，秘密鍵部分情報ｄＡ１００７と秘密鍵部分情報ｄＢ１００８の組の代わりに，１，０，−１の並びとして表現された秘密鍵情報ｄ＿ｒｅｐが保存されているものとする。
表現変換プログラム（拡張２進表現）
ステップ１０００１：はじめ
ステップ１０００２：データ格納部１００４から秘密鍵情報ｄ＿ｒｅｐを読み込む
ステップ１０００３：乱数Ｋ，Ｌを生成する（ここで０＜Ｋ＜Ｌ＜｜ｄ＿ｒｅｐ｜とする。ただし｜ｄ＿ｒｅｐ｜はｄ＿ｒｅｐのビット長）
ステップ１０００４：秘密鍵情報ｄ＿ｒｅｐの第Ｌ＋１ビット目の値ＢＬ＋１をＢＬ＋１＝ＢＬ−１＋１とする
ステップ１０００５：Ｋ＜ｉ≦Ｌなるすべてのｉに対し，秘密鍵情報ｄ＿ｒｅｐの第ｉビット目の値ＢｉをＢｉ＝Ｂｉ−１とする
ステップ１０００６：秘密鍵情報ｄ＿ｒｅｐの第Ｋビット目の値ＢＫをＢＫ＝ＢＫ−２とする
ステップ１０００７：秘密鍵情報ｄ＿ｒｅｐの各ビットが１，０，−１のいずれかであればステップ１００１３へ
ステップ１０００８：ｊ＝｜ｄ＿ｒｅｐ｜とする
ステップ１０００９：ｄ＿ｒｅｐの第ｊビット目の値Ｂｊが２であったらＢｊ＋１＝Ｂｊ＋１＋１，Ｂｊ＝０とする
ステップ１００１０：ｄ＿ｒｅｐの第ｊビット目の値Ｂｊが−２であったらＢｊ＋１＝Ｂｊ＋１−１，Ｂｊ＝０とする
ステップ１００１１：ｊ＝ｊ−１とする
ステップ１００１２：ｊ＞０ならステップ１０００７へ
ステップ１００１３：データ格納部１００４に更新された秘密鍵情報ｄ＿ｒｅｐを書き込む
ステップ１００１４：おわり
また，第１の実施例における楕円曲線暗号復号プログラム１０１１は，次のように変更される。
楕円曲線暗号復号プログラム（拡張２進表現）
［ステップ３００４］を次のように変更
ステップ１１００４：データ格納部１００４から秘密鍵情報ｄ＿ｒｅｐを読み込む
［ステップ３００６］を次のように変更
ステップ１１００６：ｄ＿ｒｅｐ１の第ｉビット目Ｂｉが１ならステップ３００９へ
［ステップ３００７］を次のように変更
ステップ１１００７：ｄ＿ｒｅｐ１の第ｉビット目Ｂｉが−１ならステップ３０１０へ
本実施例では，１，０，−１の並びとしてｄの値が表現されていたが，同様に２進表現の拡張を使って，例えば，２，１，０，−１の並びとしてｄの値を表現してもよい。また，ｔ，ｔ−１，，，０，−１，，，−ｓ（ｓ，ｔ≧０）の並びとしてｄの値を表現してもよい。さらには，あらゆるｄの値を表現できるのであれば，必ずしも連続していないいくつかの数の並びとしてｄの値を表現してもよい。
あるいはまた，秘密鍵情報ｄの値の別の表現として，積がｄと等しくなるような２つの数の組として表現されていてもよい。すなわち，第１の実施例における秘密鍵部分情報ｄＡ１００７と秘密鍵部分情報ｄＢ１００８の組の代わりに，ｄｍＡ×ｄｍＢ（ｍｏｄ  ｎ）が秘密鍵情報ｄの値と等しくなるような２つの数の組ｄｍＡとｄｍＢがデータ格納部１００４に保存されているようにしてもよい。あるいは，積がｄと等しくなるような３つ以上の数の組によって表現されていてもよい。さらには，積とは限らず，あらかじめ決められた演算結果が秘密鍵情報ｄとなるような複数の数の組によって表現されていてもよい。なお，これら様々な秘密情報生成情報による表現方法を用いる場合には，それらを正しく処理できる秘密情報生成情報処理手段を併せて用いることで所望の結果を得られる。
積がｄと等しくなるような２つの数の組による表現を使った時には，第１の実施例における表現変換プログラム１０１０は，例えば，次のように変更される。表現変換プログラム（積表現）
ステップ１２００１：はじめ
ステップ１２００２：０より大きくｎ未満の乱数ｋを生成する
ステップ１２００３：データ格納部１００４からｄｍＡおよびｄｍＢを読み込むステップ１２００４：ｄｍＡ’＝ｋｄｍＡ（ｍｏｄ  ｎ）およびｄｍＢ’＝ｋ−１ｄｍＢ（ｍｏｄ  ｎ）を計算する
ステップ１２００５：ｄｍＡ’およびｄｍＢ’をそれぞれデータ格納部１００４中のｄｍＡおよびｄｍＢが書かれていたところに書き込む
ステップ１２００６：おわり
また，第１の実施例における楕円曲線暗号復号プログラム１０１１は，次のように変更される。
楕円曲線暗号復号プログラム（積表現）（概略）
ステップ１３００１：はじめ
ステップ１３００２：ＩＣカード１００１の外部から復号用点Ｒ１０１３を読み込む
ステップ１３００３：データ格納部１００４からｄｍＡおよびｄｍＢを読み込むステップ１３００４：Ｑ＝ｄｍＡＲを計算する
ステップ１３００５：Ｑ＝ｄｍＢＱを計算する
ステップ１３００６：Ｑのｘ座標ｘＱを復号用共通鍵として出力する
ステップ１３００７：おわり
なお，上記ステップ１３００４および１３００５における楕円曲線上の点のスカラー倍演算は，任意の方法で行ってよい。例えば，バイナリ法を使って演算してもよいし，あるいは，ｄｍＡやｄｍＢを秘密鍵の値そのものと見なして他の実施例に示した方法を利用して演算してもよい。
以上，秘密情報を表す表現方法の例をいくつか示したが，これらを組み合わせてもよい。例えば，異なる，あるいは，同じ表現方法による複数の表現をデータ格納部１００４に持っておき，実際に秘密情報を利用する演算を行う時に，これらのうちのひとつまたは複数をランダムに選び演算をおこなってもよい。また，これらの表現を処理する複数の処理手段を持っておき，実際に秘密情報を利用する演算を行う時に，これらのうちのひとつまたは複数をランダムに選び演算をおこなってもよい。
あるいは，秘密分散と呼ばれる手法により，あらかじめ秘密情報をｎ個中のｋ個がそろった時に元の情報が復元できるようなｎ個に分散しておき，これらｎ個の情報を秘密情報の表現としてもよい。
秘密分散については，
文献［Ｓｈａｍｉｒ］Ａｄｉ  Ｓｈａｍｉｒ，”Ｈｏｗ  ｔｏ  Ｓｈａｒｅ  ａ  Ｓｅｃｒｅｔ”，Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  ｏｆ  ｔｈｅ  ＡＣＭ  ｖｏｌ．２２，ｎｏ．１１，ｐｐ．６１２−６１３，１９７９
に開示されている。
これらの手段により，秘密裏に保存すべき情報を利用する演算を行った時に要する時間や発生する電磁波の強さや消費電流を一定ではないようにすることが可能となり，ＴＡ（Ｔｉｍｉｎｇ  Ａｔｔａｃｋ），ＤＰＡ（Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ），ＳＰＡ（Ｓｉｍｐｌｅ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ）等によって秘密鍵の値を推定することが困難になる。
本実施例においては，楕円曲線暗号の一種であるＥｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｃｈｅｍｅ（ＥＣＥＳ）の復号化機能を持ったＩＣカードに適用した例を示したが，本発明は，第１の実施例と同様，これ以外にも広く適用可能である。
・第５の実施例
第１から第４までの実施例においては，主として，本発明を，秘密鍵ｄと与えられた楕円曲線上の点Ｒに対し，ｄＲを計算する処理に適用した例を示したが，本発明は，これ以外の処理に対しても有効である。
本発明を，楕円曲線を利用したディジタル署名方式であるＥＣＤＳＡ署名の署名生成機能を持ったＩＣカードに適用した一実施例を，以下，図を用いて説明する。ＥＣＤＳＡ署名については，前記文献［ＩＥＥＥＰ１３６３］の他，
文献［Ｘ９．６２］”Ｗｏｒｋｉｎｇ  Ｄｒａｆｔ  ＡＭＥＲＩＣＡＮ  ＮＡＴＩＯＮＡＬ  ＳＴＡＮＤＡＲＤ  Ｘ９．６２  １９９８  Ｐｕｂｌｉｃ  Ｋｅｙ  Ｃｒｙｐｔｏｇｒａｐｈｙ  Ｆｏｒ  Ｔｈｅ  Ｆｉｎａｎｃｉａｌ  Ｓｅｒｖｉｃｅｓ  Ｉｎｄｕｓｔｒｙ：Ｔｈｅ  Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｄｉｇｉｔａｌ  Ｓｉｇｎａｔｕｒｅ  Ａｌｇｏｒｉｔｈｍ（ＥＣＤＳＡ）”，Ａｍｅｒｉｃａｎ  Ｎａｔｉｏｎａｌ  Ｓｔａｎｄａｒｄｓ  Ｉｎｓｔｉｔｕｔｅ，Ｓｅｐｔｅｍｂｅｒ  ２０．１９９８
に開示されている。
なお，本実施例において，秘密裏に保存すべき情報に該当する情報は，ＥＣＤＳＡ署名の生成に必要とされる秘密鍵である。また本実施例では，素数位数の有限体上の楕円曲線を利用するものとする。
第１０図は，本実施例におけるＩＣカードの構成図である。第１の実施例におけるＩＣカードの構成図である第１図との相違点は，第１０図には楕円曲線暗号復号プログラム１０１１と共通鍵暗号復号プログラム１０１２がないこと，第１０図にはＥＣＤＳＡ署名生成プログラム１４００１があること，ＩＣカード１００１に対する入出力が異なること，および，第１０図では秘密鍵部分情報ｄＡ１００７と秘密鍵部分情報ｄＢ１００８の組が表す情報が楕円曲線暗号復号用秘密鍵ではなくＥＣＤＳＡ署名生成用秘密鍵を意味すること，である。第１図と共通の要素については同じ番号が振ってある。
ＥＣＤＳＡ署名生成プログラム１４００１について説明する。
ＥＣＤＳＡ署名生成プログラム１４００１は，ＩＣカード１００１の外部から署名対象メッセージ１４００２を入力し，また，データ格納部１００４から秘密鍵部分情報ｄＡ１００７および秘密鍵部分情報ｄＢ１００８を入力し，ディジタル署名１４００３を計算し，ＩＣカード１００１の外部に出力する。電子的な署名対象メッセージに対するディジタル署名は，紙の書類に対する印影に相当するもので，署名対象メッセージの内容を，署名者すなわち秘密鍵の所有者が保証したことを示す証拠になる。ＥＣＤＳＡ署名の詳細については，文献［Ｘ９．６２］に詳しく述べられている。
ＩＣカード１００１を使った時の署名対象メッセージ１４００２に対する署名生成を行う時の表現変換プログラム１０１１およびＥＣＤＳＡ署名生成プログラム１４００１による基本的な動作の流れをまとめると次のようになる。
まず，ＥＣＤＳＡ署名生成プログラム１４００１が，ＩＣカード１００１の外部からの入力である署名対象メッセージ１４００２と，データ格納部１００４に保存された秘密鍵部分情報ｄＡ１００７と秘密鍵部分情報ｄＢ１００８から，秘密鍵ｄを求めることなくディジタル署名１４００３を計算し，ＩＣカード１００１の外部に出力する。
これにより，ディジタル署名を生成することができる。
このように秘密鍵ｄがデータ格納部１００４，バス１００３，演算処理部１００２に出現することなくディジタル署名１４００３を生成することができるので，ＴＡ（Ｔｉｍｉｎｇ  Ａｔｔａｃｋ），ＤＰＡ（Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ），ＳＰＡ（Ｓｉｍｐｌｅ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ）等によって秘密鍵の値を推定することが困難になっている。
この例では，データ格納部１００４に保存された秘密鍵部分情報ｄＡ１００７と秘密鍵部分情報ｄＢ１００８の値が固定されている。したがって，署名生成を行うたびに，固定値である秘密鍵部分情報ｄＡ１００７と秘密鍵部分情報ｄＢ１００８がデータ格納部１００４からバス１００３を介して演算処理部１００２に毎回流れることになり，また，ＥＣＤＳＡ署名生成プログラム１４００１は，毎回同じ値を使って計算を行うことになるため，この間の計算時間や発生する電磁波の強さや消費電流等もこの固定された値に依存する。このことはＴＡ（Ｔｉｍｉｎｇ  Ａｔｔａｃｋ），ＤＰＡ（Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ），ＳＰＡ（Ｓｉｍｐｌｅ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ）等によって秘密鍵部分情報の値を推定される可能性があることを意味する。
本発明では，これらの攻撃に対するさらなる対策として，第１の実施例と同様に，表現変換プログラム１０１０を利用する。すなわち，表現変換プログラム１０１０を実行することにより，秘密鍵部分情報ｄＡ１００７と秘密鍵部分情報ｄＢ１００８の値が別の値に書き換わるため，データ格納部１００４からバス１００３を介して演算処理部１００２へ流れるデータ，ＥＣＤＳＡ署名生成プログラム１４００１を演算処理部１００２で実行した時の時間や発生する電磁波の強さや消費電流等も異なったものとなる。これにより，ＴＡ（Ｔｉｍｉｎｇ  Ａｔｔａｃｋ），ＤＰＡ（Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ），ＳＰＡ（Ｓｉｍｐｌｅ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ）等による秘密鍵の値の推定をさらに困難にすることが可能となる。
表現変換プログラム１０１０は，ＥＣＤＳＡ署名生成プログラム１４００１が実行される直前に毎回実行されてもよいし，ＥＣＤＳＡ署名生成プログラム１４００１が実行された直後に毎回実行されてもよい。あるいはＥＣＤＳＡ署名生成プログラム１４００１が何回か実行される毎に実行されてもよい。あるいはまたＥＣＤＳＡ署名生成プログラム１４００１の実行とは無関係に，ランダムなタイミングに実行されてもよい。ＥＣＤＳＡ署名生成プログラム１４００１に対するＴＡ（Ｔｉｍｉｎｇ  Ａｔｔａｃｋ）やＤＰＡ（Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ）への対策としては，表現変換プログラム１０１０の実行頻度が多いほうが望ましい。
次にＥＣＤＳＡ署名生成プログラム１４００１の詳細について説明する。
第１１図は，第１０図におけるＥＣＤＳＡ署名生成プログラム１４００１のフローを示す。
ステップ１５００１：はじめ
ステップ１５００２：ＩＣカード１００１の外部から署名対象メッセージ１４００２を読み込む
ステップ１５００３：署名対象メッセージ１４００２をハッシュ関数の入力としメッセージのハッシュ値ｈを得る
ステップ１５００４：データ格納部１００４から秘密鍵部分情報ｄＡ１００７および秘密鍵部分情報ｄＢ１００８を読み込む
ステップ１５００５：乱数ｋを生成する（０＜ｋ＜ｎとする）
ステップ１５００６：（ｘ，ｙ）＝ｋＰを計算する
ステップ１５００７：ｒ＝ｘ（ｍｏｄ  ｎ）とする
ステップ１５００８：ｓＡ＝ｋ−１（ｄＡｒ＋ｈ）（ｍｏｄ  ｎ）を計算する
ステップ１５００９：ｓＢ＝ｋ−１（ｄＢｒ＋ｈ）（ｍｏｄ  ｎ）を計算する
ステップ１５０１０：ｓ＝ｓＡ−ｓＢ（ｍｏｄ  ｎ）を計算する
ステップ１５０１１：（ｒ，ｓ）をディジタル署名として出力する
ステップ１５０１２：おわり
ここで特徴的な事は，秘密鍵ｄの値それ自身，すなわち，ｄＡ−ｄＢ（ｍｏｄ  ｎ）はこのＥＣＤＳＡ署名生成プログラム１４００１中に一度も現れないが，結果として得られたｓは，
ｓ＝ｓＡ−ｓＢ（ｍｏｄ  ｎ）
＝ｋ−１（ｄＡｒ＋ｈ）−ｋ−１（ｄＢｒ＋ｈ）（ｍｏｄ  ｎ）
＝ｋ−１（ｄｒ＋ｈ）（ｍｏｄ  ｎ）
を満たすため，秘密鍵ｄをつかって計算したのと同じ結果が得られているということである。
このように，本実施例においても，ｄＡとｄＢにわけて保存していることを活かした処理を行うことで，上記実施例と同様の効果が得られる。なぜなら，せっかく秘密鍵を，秘密鍵部分情報に分けて保存しておいても，例えば，一旦ｄ＝ｄＡ−ｄＢという計算によって求めたｄの値を使ってＥＣＤＳＡ署名生成を行ってしまっては，効果が減少してしまうからである。
さらに，第１の実施例と同様に，表現変換プログラム１０１０によって，秘密鍵ｄの表現である秘密鍵部分情報ｄＡ１００７および秘密鍵部分情報ｄＢ１００８の組を変更することにより，ＥＣＤＳＡ署名生成プログラム１４００１，より詳しくは，ＥＣＤＳＡ署名生成プログラム１４００１のステップ１５００８中の掛け算ｄＡｒおよびステップ１５００９中の掛け算ｄＢｒの，実行にかかる時間や発生する電磁波の強さや消費電流は秘密鍵ｄそのものの値には依存しなくなる。したがってＴＡ（Ｔｉｍｉｎｇ  Ａｔｔａｃｋ），ＤＰＡ（Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ）などにより攻撃によって，秘密鍵の値を推定することがさらに困難になるという効果が得られる。
本実施例では，署名対象メッセージのメッセージダイジェストであるハッシュ値をＩＣカード１００１の内部で，ＥＣＤＳＡ署名生成プログラム１４００１のステップ１５００３で求めたが，この処理はＩＣカード１００１と情報のやり取りができる外部の装置，例えば，ＩＣカード１００１とＩＣカードリーダライタを通じて情報のやり取りができるＰＣ等で行ってもよい。この場合，ＩＣカードに対する入力は，署名対象メッセージのハッシュ値となる。
本実施例において，ＥＣＤＳＡ署名生成プログラム１４００１のステップ１５００５で生成される乱数ｋも秘密に保持すべき値である。なぜなら，ディジタル署名（ｒ，ｓ），秘密鍵ｄ，乱数ｋ，ハッシュ値ｈらの間には，ｓ＝ｋ−１（ｄｒ＋ｈ）（ｍｏｄ  ｎ）という関係があり，これらのうち，ｒ，ｓ，ｈは誰もが知ることができる値であるため，もし，乱数ｋの値が分かれば，秘密鍵ｄの値も計算によって分かってしまうからである。
ただし，秘密鍵ｄの値が一定であるのに対し，乱数ｋは署名を生成するたびごとにランダムに生成される点で異なるため，ＴＡ（Ｔｉｍｉｎｇ  Ａｔｔａｃｋ），ＤＰＡ（Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ）などの攻撃によって値が推定される可能性は秘密鍵に比べて低い。なお，ここで，秘密鍵ｄの値が一定であるというのは，具体的な表現のことではなく，本来持っている情報の内容のことである。
なお，より安全性を高める目的で，乱数ｋに対しても，本発明を適用することは可能である。例えば，第２の実施例と同様にして次のように行うことができる。すなわち，まず，第２の実施例におけるテーブルデータ計算プログラム５００１により，テーブルデータを計算しておく。本実施例においては，固定された点であるベースポイントＰに関するテーブルなので，第２の実施例中の説明中で述べたように，テーブルデータは事前に，例えばＩＣカード１００１の外部で，計算しておくことが可能である。
ＥＣＤＳＡ署名生成プログラム１４００１のステップ１５００５で乱数ｋを生成した後，これをｋＡとｋＢの組として表現してデータ格納部１００４に保存し，さらに表現変換プログラムにより変換する。その後ＥＣＤＳＡ署名生成プログラム１４００１のステップ１５００６における（ｘ，ｙ）を，第２の実施例におけるテーブル参照型楕円曲線暗号復号プログラム５００２と同様にして計算する。ＥＣＤＳＡ署名生成プログラム１４００１のステップ１５００８およびステップ１５００９で使う値ｋ−１は，例えば，次のようにして計算すればよい。まず，ｔ＝ｋＢ−１−ｋＡ−１（ｍｏｄ  ｎ）を計算する。次にｔ−１ｋＡ−１ｋＢ−１（ｍｏｄ  ｎ）を計算する。これがｋ−１と等しくなる。
ここで特徴的な事は，このｋ−１を求める演算中に，ｋ自身の値は現れないことである。これによりｋ−１を求める演算にかかる時間や発生する電磁波の強さや消費電流はｋそのものの値には依存しなくなる。したがってＴＡ（Ｔｉｍｉｎｇ  Ａｔｔａｃｋ），ＤＰＡ（Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ）などにより攻撃によって，乱数ｋの値を推定することが困難になる。
本実施例においては，ディジタル署名の一種であるＥＣＤＳＡ署名の署名生成機能を持ったＩＣカードに適用した例を示したが，本発明は，これ以外にも広く適用可能である。
例えば，利用する楕円曲線は，第１の実施例で述べた他の楕円曲線でもよい。また，楕円曲線上の離散対数問題の困難性を利用したディジタル署名にかぎらず，第１の実施例で述べた他の群の上の離散対数問題の困難性を利用したディジタル署名であってもよい。
あるいは，ディジタル署名でなくても，より一般に，群Ｇ１から群Ｇ２への準同型写像ｆがあって，秘密裏に保持すべき群Ｇ１の元ｇから群Ｇ２の元ｆ（ｇ）を計算する装置がある時，この装置に対するＴＡ（Ｔｉｍｉｎｇ  Ａｔｔａｃｋ），ＤＰＡ（Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ），ＳＰＡ（Ｓｉｍｐｌｅ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ）等によりｇが推定される可能性は，本発明によれば，例えば，次のようにして減らすことができる。
まずｇ＝ｇ１・ｇ２（・は群Ｇ１の演算を表す）となるｇ１とｇ２の組によりｇを表現し，データ保存部に保存しておく。
次に，ランダムに選んだＧ１の元ｈについて，ｇ１’＝ｈ・ｇ１，ｇ２’＝ｈ−１・ｇ２（ｈ−１は群Ｇ１の演算・に関するｈの逆元を表す）を計算し，ｇ１をｇ１’でｇ２をｇ２’でおきかえるプログラムを実行する。これを表現変換プログラムと呼ぶ。最後に，ｆ（ｇ）の値を得るために，ｆ（ｇ１）＃ｆ（ｇ２）（＃は群Ｇ２の演算を表す）を計算する。ｆは準同型写像だから，ｆ（ｇ１）＃ｆ（ｇ２）はｆ（ｇ）に等しい。
このように適宜，表現変換プログラムを実行するたびに，その後のｆ（ｇ）の値を求める処理に要する時間や発生する電磁波の強さや消費電流は異なるものになる。これにより，ＴＡ（Ｔｉｍｉｎｇ  Ａｔｔａｃｋ），ＤＰＡ（Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ），ＳＰＡ（Ｓｉｍｐｌｅ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ）等によって秘密鍵の値を推定することが困難になる。なお，ここで，準同型写像とは，群から群への写像であって，演算を保つような写像のことである。
・第６の実施例
本発明を，電子商取引におけるメッセージの送受に適用した一実施例を，以下，図を用いて説明する。
以下の実施例では，一般消費者であるカードホルダが，販売店であるマーチャントに対し，商品の購入要求を行う時の処理について説明する。図１２は，本実施例におけるシステム構成図である。図１２において，ネットワーク１６００１に，一般消費者であるカードホルダのコンピュータ１６００２，販売店であるマーチャントのコンピュータ１６００３，および，認証局１６００４が接続されている。ここで，認証局とは，公開鍵の正当性を保証する証明書を発行する機関である。
カードホルダのコンピュータ１６００２は，ＣＰＵ１６００５，メモリ１６００６からなり，ディスプレイ１６００７，キーボード１６００８，および，ＩＣカードリーダライタ１６００９が接続されており，また，ネットワーク１６００１に接続されている。カードホルダはまた署名用ＩＣカード１６０１０を所有しており，署名用ＩＣカード１６０１０とコンピュータ１６００２とは，ＩＣカードリーダライタ１６００９を通して，情報のやり取りが可能となっている。この署名用ＩＣカード１６０１０は，第５の実施例に示したＩＣカードと同じものである。
マーチャントのコンピュータ１６００３は，ＣＰＵ１６０１１，メモリ１６０１２からなり，ディスプレイ１６０１３，および，キーボード１６０１４が接続されており，また，ネットワーク１６００１に接続されている。
カードホルダのコンピュータ１６００２のメモリ１６００６内には公開鍵１６０１５が，また，カードホルダの所有する署名用ＩＣカード１６０１０のメモリ内には，公開鍵１６０１５とペアになる秘密鍵に係わる情報やプログラムが，本発明を適用した形で保存されている。これらの情報は，カード発行者，例えばクレジット会社，によって，あらかじめ秘密鍵に係わる情報やプログラムが書き込まれたＩＣカードと，公開鍵情報が入ったＦＤやＣＤ−ＲＯＭなどの記録媒体が，送られてくることにより設定されるものである。あるいは，公開鍵情報は有線無線などの伝送媒体によって送られてくるものとしてもよい。あるいは，カード発行者から送られてきたＩＣカードに鍵生成機能が組み込まれていて，それをカードホルダが実行することによって設定されるものとしてもよい。あるいはまた，カード発行者から，カードホルダのコンピュータ上で実行可能な鍵生成プログラムが，ＦＤやＣＤ−ＲＯＭなどの記録媒体や有線無線などの伝送媒体によって送られてきて，それをカードホルダが実行することによって，送られてくるＩＣカードに設定されるものとしてもよい。鍵生成機能付きのＩＣカードを利用する方法の場合は，秘密鍵に関する情報が，ＩＣカードの外部に漏れることがないため，セキュリティ上の観点からはこの方法が一番望ましい。なお，ＩＣカード内の秘密鍵は，第５の実施例と同様に，本発明を適用した保存方法によって保存されているものとする。また，上記実施例を適用した秘密情報生成情報による秘密情報の表現方法やその秘密情報生成情報を処理するプログラムは，個々のＩＣカードによって異ならせても良いし同じであっても良い。異ならせる方がより安全性が高まる。
マーチャントのコンピュータ１６００３のメモリ１６０１２内には，あらかじめ，署名検証プログラム１６０１８，および，システム鍵１６０１９が設定されている。これらは，カードホルダの所有する署名用ＩＣカード１６０１０に対応するように設定されているものとする。署名検証プログラム１６０１８の詳細については，文献［Ｘ９．６２］に述べられている。
次に，カードホルダの行う処理について説明する。
はじめにカードホルダは，認証局１６００４に公開鍵証明書１６０１６を発行してもらうため，公開鍵１６０１５を送る。認証局１６００４はカードホルダからの要求に応じ，周知の方法で，公開鍵証明書１６０１６を発行してカードホルダのコンピュータ１６００２に送る。この処理は一つの公開鍵に対し一度だけ必要な処理である。言い換えると，購入要求メッセージを送信する処理を行うたびに必要なわけではない。また，認証局が公開鍵証明書を発行する手順中には，ディジタル署名を生成する過程が含まれるため，この過程に対しても本発明を適用することは可能である。
次に，カードホルダが購入要求メッセージをマーチャントに送信する際の処理について，説明する。
カードホルダのコンピュータ１６００２は，購入要求メッセージ１６０１７を作成し，メモリ１６００６内に保存する。この購入要求メッセージ１６０１７をＩＣカードリーダライタ１６００９を通じて，署名用ＩＣカード１６０１０に送り，本発明による方法に従ってディジタル署名１６０２０を生成させ，これもメモリ１６００６内に保存する。
このディジタル署名１６０２０が，購入要求メッセージ１６０１７の内容が確かにカードホルダによって確認されたことを示す証拠となり，通常の紙の書類における印影に相当する。すなわち，通常の紙の書類に対する印鑑に相当するのが，署名用ＩＣカード１６０１０内に保存された秘密鍵になる。したがって，もし，署名用ＩＣカード１６０１０内に保存された秘密鍵を，悪意のある人が知ってしまうと，正当な所有者であるカードホルダになりすまして，購入要求を行うことができるようになってしまう。
本実施例によれば，今まで述べてきたように署名用ＩＣカードに対するこれらの攻撃法により秘密鍵を推定することが困難になる。
カードホルダのコンピュータ１６００２は，ディジタル署名１６０２０を生成した後，購入要求メッセージ１６０１７，公開鍵１６０１５，公開鍵証明書１６０１６，および，ディジタル署名１６０２０をまとめて送信文１６０２１として，ネットワーク１６００１を通じて，マーチャントに送る。
マーチャントは，送信文１６０２１を受け取ると，まず，周知の方法により，公開鍵証明書１６０１６を使って公開鍵１６０１５が正当なものであることを確認した後，署名検証プログラム１６０１８を実行することにより，購入要求メッセージ１６０１７が確かにカードホルダによって作成されたものかどうかを，ディジタル署名１６０２０，公開鍵１６０１５およびシステム鍵１６０１９などを利用して調べる。その結果，ディジタル署名１６０２０の正当性が確認されれば，購入要求メッセージ１６０１７の内容は信頼できるものであるとし，取引を継続する。一方，もしディジタル署名１６０２０の正当性が確認されなければ，ネットワーク１６００１中で改ざんされた，あるいは，正しいカードホルダでない人によって購入要求メッセージ１６０１７が作成された等，何らかの不正があったものとし，取引は中止する。
産業上の利用可能性
本発明により，各種攻撃法に対して安全な，演算方法および情報の保持方法およびこれらの方法を利用したＩＣカード，セキュリティモジュール，半導体チップ，システム，コンピュータ，プログラムを提供することができる。
【図面の簡単な説明】
第１図は，本発明の一実施例におけるＩＣカード構成図であり，第２図は，第１図のＩＣカード構成のうち表現変換プログラムのフローであり，第３図は，第１図のＩＣカード構成のうち楕円曲線暗号復号プログラムのフローであり，第４図は，第１図のＩＣカード構成のうち共通鍵暗号復号プログラムのフローであり，第５図は，本発明の一実施例におけるＩＣカード構成図であり，第６図は，第５図のＩＣカード構成のうちテーブルデータ計算プログラムのフローであり，第７図は，第５図のＩＣカード構成のうちテーブル参照型楕円曲線暗号復号プログラムのフローであり，第８図は，本発明の一実施例におけるＩＣカード構成図であり，第９図は，第８図のＩＣカード構成のうち点表現変換プログラムのフローであり，第１０図は，本発明の一実施例におけるＩＣカード構成図，第１１図は，第１０図のＩＣカード構成のうちＥＣＤＳＡ署名生成プログラムのフローである。
【図１】
0004671571.tif 000002
【図２】
0004671571.tif 000003
【図３】
0004671571.tif 000004
【図４】
0004671571.tif 000005
【図５】
0004671571.tif 000006
【図６】
0004671571.tif 000007
【図７】
0004671571.tif 000008
【図８】
0004671571.tif 000009
【図９】
0004671571.tif 000010
【図１０】
0004671571.tif 000011
【図１１】
0004671571.tif 000012
【図１２】
0004671571.tif 000013