(57)【要約】  ＲＳＡ暗号などの情報セキュリティ装置に対する単純電力攻撃（ＳＰＡ）に対抗する情報セキュリティ装置を提供する。情報セキュリティ装置は、モンゴメリ領域での１との乗算を用いる。モンゴメリ領域での１は、法ｐのビット数より大きな整数ｋおよび法に依存して決定されるため、ｐやｋを知らない攻撃者は解析が困難となる。また、万が一、解析者がハミング重みを予測できた場合であっても、ｋまたは法をランダムに変更することにより、さらにＳＰＡに対する安全性が向上する。
2007046402.tif 000002
【特許請求の範囲】
【請求項１】
所定の法において入力値を整数乗するべき乗剰余演算を行うために、前記整数の各桁毎に乗算を繰り返してべき乗値を算出して、前記入力値の安全又は確実な処理を行う情報セキュリティ装置であって、
前記整数の１個の桁の値が０であるか否かを判断する判断手段と、
取得した桁の値が０であると判断される場合に、値１に対するモンゴメリ変換値を用いる乗算剰余演算を行う乗算手段と
を備えることを特徴とする情報セキュリティ装置。
【請求項２】
前記情報セキュリティ装置は、ＲＳＡ方式に基づいてＲＳＡ暗号文を復号するＲＳＡ復号装置、又はＲＳＡ方式に基づいて署名対象のメッセージに対して署名データの生成を行うＲＳＡ署名装置であり、さらに、
前記入力値としてＲＳＡ暗号文を取得し、又は前記入力値として署名対象のメッセージを取得する取得手段と、
秘密鍵として前記整数を記憶している記憶手段と、
前記ＲＳＡ暗号文から復号して得られる復号文として、又は前記メッセージに対する署名データとして、算出された前記べき乗値を出力する出力手段と
を含むことを特徴とする請求項１に記載の情報セキュリティ装置。
【請求項３】
前記情報セキュリティ装置は、
入力値を取得する取得手段と、
整数を記憶している記憶手段と、
演算結果の値を格納する演算値変数に初期値を格納する初期化手段と、
前記記憶手段から前記整数の上位桁から１個の桁の値を抽出する抽出手段と、
前記演算値変数に格納されている値の少なくとも１回の二乗剰余演算に基づいて得られた値を前記演算値変数に上書きする二乗手段と、
取得した桁の値が０であるか否かを判断する前記判断手段と、
取得した桁の値が０であると判断される場合に、前記演算値変数に格納されている値と値１に対するモンゴメリ変換値との乗算剰余演算に基づいて得られた値を前記演算値変数に上書きし、０以外であると判断される場合に、前記演算値変数に格納されている値と前記入力値から定まる値との乗算剰余演算に基づいて得られた値を前記演算値変数に上書きする前記乗算手段と、
前記整数の全ての桁について、前記抽出手段、前記二乗手段、前記判断手段及び前記乗算手段に対して、値の取得と、二乗剰余演算と、判断と、乗算剰余演算とを繰り返すように制御する繰返制御手段と、
前記整数の全ての桁について前記繰返しが終了すると、前記演算値変数に格納されている値に基づく値を出力する出力手段と
を備えることを特徴とする請求項１に記載の情報セキュリティ装置。
【請求項４】
前記情報セキュリティ装置は、
入力値を取得して入力値変数に格納する取得手段と、
整数を記憶している記憶手段と、
演算結果の値を格納する演算値変数に初期値を格納する初期化手段と、
前記記憶手段から前記整数の下位桁から１個の桁の値を抽出する抽出手段と、
前記入力値変数に格納されている値の少なくとも１回の二乗剰余演算に基づいて得られた値を前記入力値変数に上書きする二乗手段と、
取得した桁の値が０であるか否かを判断する前記判断手段と、
取得した桁の値が０であると判断される場合に、前記演算値変数に格納されている値と値１に対するモンゴメリ変換値との乗算剰余演算に基づいて得られた値を前記演算値変数に上書きし、０以外であると判断される場合に、前記演算値変数に格納されている値と前記入力値変数から定まる値との乗算剰余演算に基づいて得られた値を前記演算値変数に上書きする前記乗算手段と、
前記整数の全ての桁について、前記抽出手段、前記二乗手段、前記判断手段及び前記乗算手段に対して、値の取得と、二乗剰余演算と、判断と、乗算剰余演算とを繰り返すように制御する繰返制御手段と、
前記整数の全ての桁について前記繰返しが終了すると、前記演算値変数に格納されている値に基づく値を出力する出力手段と
を備えることを特徴とする請求項１に記載の情報セキュリティ装置。
【請求項５】
前記情報セキュリティ装置は、さらに、
値１に対するモンゴメリ変換値を算出するモンゴメリ変換手段を含み、
前記乗算手段は、前記乗算剰余演算において、前記モンゴメリ変換手段により算出されたモンゴメリ変換値を用いる
ことを特徴とする請求項１に記載の情報セキュリティ装置。
【請求項６】
前記情報セキュリティ装置は、さらに、
前記法の値を設定する法設定手段と、
前記法の有効ビット数より大きい整数ｋをランダムに選択する整数設定手段とを備え、
前記モンゴメリ変換手段は、設定された前記法の値に基づいて、前記整数ｋを用いて、前記モンゴメリ変換値を算出する
ことを特徴とする請求項５に記載の情報セキュリティ装置。
【請求項７】
前記モンゴメリ変換手段は、前記モンゴメリ変換値として、前記法において値２のｋ乗値を算出する
ことを特徴とする請求項６に記載の情報セキュリティ装置。
【請求項８】
前記モンゴメリ変換手段は、前記モンゴメリ変換値として、前記法としての値の乱数倍の法において、値２のｋ乗値を算出する
ことを特徴とする請求項６に記載の情報セキュリティ装置。
【請求項９】
前記情報セキュリティ装置は、さらに、
前記法設定手段は、さらに、前記法としての値の乱数倍の法を設定し、
前記モンゴメリ変換手段は、法設定手段によりさらに設定された前記法において、値２のｋ乗値を算出する
ことを特徴とする請求項８に記載の情報セキュリティ装置。
【請求項１０】
前記整数設定手段は、入力値を取得する毎に、前記整数ｋの値をランダムに変更する
ことを特徴とする請求項６に記載の情報セキュリティ装置。
【請求項１１】
前記法設定手段は、入力値を取得する毎に、前記モンゴメリ変換手段において用いられる前記法の値をランダムに変更する
ことを特徴とする請求項６に記載の情報セキュリティ装置。
【請求項１２】
前記整数設定手段は、前記繰返しの途中に、前記整数ｋの値をランダムに変更する
ことを特徴とする請求項６に記載の情報セキュリティ装置。
【請求項１３】
前記法設定手段は、前記繰返しの途中に、前記モンゴメリ変換手段において用いられる前記法の値をランダムに変更する
ことを特徴とする請求項６に記載の情報セキュリティ装置。
【請求項１４】
前記整数設定手段は、外部からの指示により、前記整数ｋの値をランダムに変更する
ことを特徴とする請求項６に記載の情報セキュリティ装置。
【請求項１５】
前記法設定手段は、外部からの指示により、前記モンゴメリ変換手段において用いられる前記法の値をランダムに変更する
ことを特徴とする請求項６に記載の情報セキュリティ装置。
【請求項１６】
前記情報セキュリティ装置は、さらに、
前記入力値に対するモンゴメリ変換値を算出するモンゴメリ変換手段を含み、
前記乗算手段は、取得した桁の値が０以外であると判断される場合に、前記モンゴメリ変換手段により算出された前記モンゴメリ変換値を用いて乗算剰余演算を行う
ことを特徴とする請求項１に記載の情報セキュリティ装置。
【請求項１７】
前記情報セキュリティ装置は、さらに、
前記法の値を設定する法設定手段と、
前記法の有効ビット数より大きい整数ｋをランダムに選択する整数設定手段とを備え、
前記モンゴメリ変換手段は、設定された前記法の値に基づいて、前記整数ｋを用いて、前記モンゴメリ変換値を算出する
ことを特徴とする請求項１６に記載の情報セキュリティ装置。
【請求項１８】
前記モンゴメリ変換手段は、前記法において、値２のｋ乗値を算出し、前記入力値と算出された値とを乗じて得られた値を前記モンゴメリ変換値とする
ことを特徴とする請求項１７に記載の情報セキュリティ装置。
【請求項１９】
前記モンゴメリ変換手段は、前記モンゴメリ変換値として、前記法としての値の乱数倍の法において、値２のｋ乗値を算出する
ことを特徴とする請求項１７に記載の情報セキュリティ装置。
【請求項２０】
所定の法において入力値を整数乗するべき乗剰余演算を行うために、前記整数の各桁毎に乗算を繰り返してべき乗値を算出して、前記入力値の安全又は確実な処理を行う情報セキュリティ装置において用いられる情報セキュリティ方法であって、
前記整数の１個の桁の値が０であるか否かを判断する判断ステップと、
取得した桁の値が０であると判断される場合に、値１に対するモンゴメリ変換値を用いる乗算剰余演算を行う乗算ステップと
を含むことを特徴とする情報セキュリティ方法。
【請求項２１】
所定の法において入力値を整数乗するべき乗剰余演算を行うために、前記整数の各桁毎に乗算を繰り返してべき乗値を算出して、前記入力値の安全又は確実な処理を行う情報セキュリティ装置において用いられる情報セキュリティのためのコンピュータプログラムであって、
前記整数の１個の桁の値が０であるか否かを判断する判断ステップと、
取得した桁の値が０であると判断される場合に、値１に対するモンゴメリ変換値を用いる乗算剰余演算を行う乗算ステップと
を含むことを特徴とするコンピュータプログラム。
【請求項２２】
所定の法において入力値を整数乗するべき乗剰余演算を行うために、前記整数の各桁毎に乗算を繰り返してべき乗値を算出して、前記入力値の安全又は確実な処理を行う情報セキュリティ装置において用いられる情報セキュリティのためのコンピュータプログラムを記録しているコンピュータ読み取り可能な記録媒体であって、
前記コンピュータプログラムは、
前記整数の１個の桁の値が０であるか否かを判断する判断ステップと、
取得した桁の値が０であると判断される場合に、値１に対するモンゴメリ変換値を用いる乗算剰余演算を行う乗算ステップと
を含むことを特徴とする記録媒体。
【請求項２３】
所定の法において入力値を整数乗するべき乗剰余演算を行うために、前記整数の各桁毎に乗算を繰り返してべき乗値を算出して、前記入力値の安全又は確実な処理を行う集積回路であって、
前記整数の１個の桁の値が０であるか否かを判断する判断手段と、
取得した桁の値が０であると判断される場合に、値１に対するモンゴメリ変換値を用いる乗算剰余演算を行う乗算手段と
を備えることを特徴とする集積回路。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、秘密鍵を用いた公開鍵暗号処理や署名処理を行う情報セキュリティ装置における耐タンパー技術に関する。
【背景技術】
【０００２】
近年、情報通信技術の普及に伴い、情報セキュリティ技術の重要性が一段と増してきている。このような情報セキュリティ技術の一つとして、暗号技術がプライバシーの保護や通信相手の確認のために用いられる。
しかしながら、暗号技術により何かを守ろうとすると、暗号化を打ち破ってそれを入手しようとする者が現れる。例えば、秘密鍵の値により、暗号処理時の計算時間や消費電力などが異なることを利用して、秘密鍵を求めるサイドチャネル攻撃が問題となっている（例えば、非特許文献１）。【０００３】
その中でも代表的なものとして、ＲＳＡ暗号方式、より正確には、秘密鍵を用いたＲＳＡ署名の署名処理や、ＲＳＡ暗号の復号処理に対する単純電力攻撃（ＳＰＡ、Simple Power Analysis）がある。ＲＳＡ暗号方式における主要な処理は、秘密鍵をべきとするべき乗演算であり、べき乗演算は、２乗算と乗算の繰り返しで実現される。この場合、対応する秘密鍵のビットが「０」のとき乗算が行われず、「１」のときだけ乗算が行われるので、ＳＰＡでは、消費電力の波形判断により得た乗算及び２乗算のシーケンス情報から秘密鍵を求める。【０００４】
このＳＰＡに対抗するためには、秘密鍵の当該ビットが「０」の場合も乗算を行えばよい。以下、２つの具体的な従来方法について説明する。
その第１の方法では、秘密鍵の当該ビットが「０」のときには、「１」と乗算する（例えば、非特許文献２）。「１」と乗算しても結果は変わらないため、実質的に乗算を実施していないのと同じである。その上、秘密鍵のビット値に依存せずに乗算が行われるので、乗算の有無により、秘密鍵を求めることはできない。【０００５】
また、ＳＰＡに対抗する第２の方法では、ビットが「０」であろうと「１」であろうと、まず乗算を行って、ビットが「１」の場合のみ乗算結果を使い、「０」の場合は乗算結果を使わないように制御する（例えば、特許文献１、特許文献２）。この方法も、ビット値に依存せずに乗算を行うため、乗算の有無により、秘密鍵を求めることはできない。
【非特許文献１】現実の脅威「サイドチャネル解析」（１）、日経エレクトロニクス２００５．７．１８号
【非特許文献２】“ＲＳＡ暗号の電力解析法による攻撃とその対策”（Power Analysis and Countermeasure of RSA Cryptosystem)、電子情報通信学会論文誌Ａ  Ｖｏｌ．Ｊ８８−Ａ、  Ｎｏ．５  ２００５
【非特許文献３】P.L.Montgomery, “Modular Multiplication without Trial Division," Mathematics of Computation,Vol.44,No.170,pp.519-521 (1985)
【特許文献１】特開２０００−１６５３７５号公報
【特許文献２】米国特許第６４０８０７５号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、ＳＰＡに対抗する前記第１の方法については、乗算への入力の一方が、ハミング重みに偏りがある「１」であるため、これが電力変化に影響して「１」との乗算を区別でき、不正に解析される可能性がある。
また、第２の方法については、乗算のときを狙って、例えば、電源電圧にスパイクノイズを与える等の、故意にエラーを生じさせるエラー攻撃により、秘密鍵が解析される可能性がある。詳細には、乗算の際にエラーを起こし、その影響が出力に表れないと、結果を使っていない、つまり対応する秘密鍵のビットが「０」であったと解析できる。反対に、エラーの影響が出力に表れると、秘密鍵の対応するビットが「１」であったと解析できる。この解析は、エラー攻撃に対する通常の対策である検算機能を入れていたとしても、可能である。【０００７】
そこで、本発明では、第１の方法を用いる場合において、上記課題を解決し、ＳＰＡに対抗することができる情報セキュリティ装置、情報セキュリティ方法、コンピュータプログラム、記録媒体及び集積回路を提供することを目的とする。なお、本発明では、第１の方法をベースにしているので、前記第２の方法による攻撃は、意味がなくなる。
【課題を解決するための手段】
【０００８】
上記目的を達成するために、本発明は、所定の法において入力値を整数乗するべき乗剰余演算を行うために、前記整数の各桁毎に乗算を繰り返してべき乗値を算出して、前記入力値の安全又は確実な処理を行う情報セキュリティ装置であって、前記整数の１個の桁の値が０であるか否かを判断する判断手段と、取得した桁の値が０であると判断される場合に、値１に対するモンゴメリ変換値を用いる乗算剰余演算を行う乗算手段とを備えることを特徴とする。
【発明の効果】
【０００９】
この構成によると、「１」に対するモンゴメリ変換値との乗算剰余演算を用いるので、ハミング重みに偏りがある「１」の使用を避けることができ、ＳＰＡに対抗して、不正な解析を困難にすることができる。
ここで、前記情報セキュリティ装置は、ＲＳＡ方式に基づいてＲＳＡ暗号文を復号するＲＳＡ復号装置、又はＲＳＡ方式に基づいて署名対象のメッセージに対して署名データの生成を行うＲＳＡ署名装置であり、さらに、前記入力値としてＲＳＡ暗号文を取得し、又は前記入力値として署名対象のメッセージを取得する取得手段と、秘密鍵として前記整数を記憶している記憶手段と、前記ＲＳＡ暗号文から復号して得られる復号文として、又は前記メッセージに対する署名データとして、算出された前記べき乗値を出力する出力手段とを含むとしてもよい。【００１０】
この構成によると、ＲＳＡ方式に基づいてＲＳＡ暗号文を復号するＲＳＡ復号において、また、ＲＳＡ方式に基づいて署名対象のメッセージに対して署名データの生成を行うＲＳＡ署名において、ハミング重みに偏りがある「１」の使用を避けることができ、ＳＰＡによる不正な解析を困難にすることができる。
ここで、前記情報セキュリティ装置は、入力値を取得する取得手段と、整数を記憶している記憶手段と、演算結果の値を格納する演算値変数に初期値を格納する初期化手段と、前記記憶手段から前記整数の上位桁から１個の桁の値を抽出する抽出手段と、前記演算値変数に格納されている値の少なくとも１回の二乗剰余演算に基づいて得られた値を前記演算値変数に上書きする二乗手段と、取得した桁の値が０であるか否かを判断する前記判断手段と、取得した桁の値が０であると判断される場合に、前記演算値変数に格納されている値と値１に対するモンゴメリ変換値との乗算剰余演算に基づいて得られた値を前記演算値変数に上書きし、０以外であると判断される場合に、前記演算値変数に格納されている値と前記入力値から定まる値との乗算剰余演算に基づいて得られた値を前記演算値変数に上書きする前記乗算手段と、前記整数の全ての桁について、前記抽出手段、前記二乗手段、前記判断手段及び前記乗算手段に対して、値の取得と、二乗剰余演算と、判断と、乗算剰余演算とを繰り返すように制御する繰返制御手段と、前記整数の全ての桁について前記繰返しが終了すると、前記演算値変数に格納されている値に基づく値を出力する出力手段とを備えるとしてもよい。【００１１】
また、前記情報セキュリティ装置は、入力値を取得して入力値変数に格納する取得手段と、整数を記憶している記憶手段と、演算結果の値を格納する演算値変数に初期値を格納する初期化手段と、前記記憶手段から前記整数の下位桁から１個の桁の値を抽出する抽出手段と、前記入力値変数に格納されている値の少なくとも１回の二乗剰余演算に基づいて得られた値を前記入力値変数に上書きする二乗手段と、取得した桁の値が０であるか否かを判断する前記判断手段と、取得した桁の値が０であると判断される場合に、前記演算値変数に格納されている値と値１に対するモンゴメリ変換値との乗算剰余演算に基づいて得られた値を前記演算値変数に上書きし、０以外であると判断される場合に、前記演算値変数に格納されている値と前記入力値変数から定まる値との乗算剰余演算に基づいて得られた値を前記演算値変数に上書きする前記乗算手段と、前記整数の全ての桁について、前記抽出手段、前記二乗手段、前記判断手段及び前記乗算手段に対して、値の取得と、二乗剰余演算と、判断と、乗算剰余演算とを繰り返すように制御する繰返制御手段と、前記整数の全ての桁について前記繰返しが終了すると、前記演算値変数に格納されている値に基づく値を出力する出力手段とを備えるとしてもよい。【００１２】
情報セキュリティ装置は、実施の形態のＩＣカード１００に相当し、取得手段は、入出力部１０２に相当し、記憶手段は、秘密鍵格納部１１３に相当し、初期化手段は、図４のステップＳ１０２に相当し、抽出手段は、抽出部１２２に相当し、二乗手段は、二乗算部１１５に相当し、判断手段は、図４のステップＳ１０６に相当し、乗算手段は、乗算部１１６に相当し、繰返制御手段は、制御部１１４に相当し、出力手段は、モンゴメリ逆変換部１２０及び入出力部１０２に相当する。【００１３】
これらの構成によると、前記整数の上位の桁から又は下位の桁からの演算を行うことができる。
ここで、前記情報セキュリティ装置は、さらに、値１に対するモンゴメリ変換値を算出するモンゴメリ変換手段を含み、前記乗算手段は、前記乗算剰余演算において、前記モンゴメリ変換手段により算出されたモンゴメリ変換値を用いるとしてもよい。【００１４】
モンゴメリ変換手段は、第２のモンゴメリ変換部１１２に相当する。
この構成によると、モンゴメリ変換手段により値１に対するモンゴメリ変換値を算出し、乗算手段は、算出されたモンゴメリ変換値を用いるので、値１に対するモンゴメリ変換値の算出を複数回行うことなく、演算回数を削減することができる。
ここで、前記情報セキュリティ装置は、さらに、前記法の値を設定する法設定手段と、前記法の有効ビット数より大きい整数ｋをランダムに選択する整数設定手段とを備え、前記モンゴメリ変換手段は、設定された前記法の値に基づいて、前記整数ｋを用いて、前記モンゴメリ変換値を算出するとしてもよい。【００１５】
法設定手段は、法設定部１１７に相当し、整数設定手段は、整数設定部１１８に相当する。
この構成によると、前記法の有効ビット数より大きく、ランダムに選択された整数ｋをモンゴメリ変換値の算出において用いるので、「１」についてのハミング重みの偏りをさらに避けることができる。【００１６】
ここで、前記モンゴメリ変換手段は、前記モンゴメリ変換値として、前記法において値２のｋ乗値を算出するとしてもよい。
この構成によると、確実にモンゴメリ変換値を算出することができる。
ここで、前記モンゴメリ変換手段は、前記モンゴメリ変換値として、前記法としての値の乱数倍の法において、値２のｋ乗値を算出するとしてもよい。【００１７】
この構成によると、「１」についてのハミング重みの偏りをさらに避けることができるモンゴメリ変換値を算出することができる。
ここで、前記情報セキュリティ装置は、さらに、前記法設定手段は、さらに、前記法としての値の乱数倍の法を設定し、前記モンゴメリ変換手段は、法設定手段によりさらに設定された前記法において、値２のｋ乗値を算出するとしてもよい。【００１８】
この構成によると、「１」についてのハミング重みの偏りをさらに避けることができるモンゴメリ変換値を算出することができる。
ここで、前記整数設定手段は、入力値を取得する毎に、前記整数ｋの値をランダムに変更するとしてもよい。
この構成によると、最初の入力値を用いたＳＰＡの結果を、別の入力値において使用することを困難とすることができる。【００１９】
ここで、前記法設定手段は、入力値を取得する毎に、前記モンゴメリ変換手段において用いられる前記法の値をランダムに変更するとしてもよい。
この構成によると、最初の入力値を用いたＳＰＡの結果を、別の入力値において使用することを困難とすることができる。
ここで、前記整数設定手段は、前記繰返しの途中に、前記整数ｋの値をランダムに変更するとしてもよい。【００２０】
この構成によると、繰返しの途中のプロセスにおけるＳＰＡの結果を、繰返しの別のプロセスにおいて使用することを困難とすることができる。
ここで、前記法設定手段は、前記繰返しの途中に、前記モンゴメリ変換手段において用いられる前記法の値をランダムに変更するとしてもよい。
この構成によると、繰返しの途中のプロセスにおけるＳＰＡの結果を、繰返しの別のプロセスにおいて使用することを困難とすることができる。【００２１】
ここで、前記整数設定手段は、外部からの指示により、前記整数ｋの値をランダムに変更するとしてもよい。
この構成によると、外部からの指示の前におけるＳＰＡの結果を、外部からの指示の後において使用することを困難とすることができる。
ここで、前記法設定手段は、外部からの指示により、前記モンゴメリ変換手段において用いられる前記法の値をランダムに変更するとしてもよい。【００２２】
この構成によると、外部からの指示の前におけるＳＰＡの結果を、外部からの指示の後において使用することを困難とすることができる。
ここで、前記情報セキュリティ装置は、さらに、前記入力値に対するモンゴメリ変換値を算出するモンゴメリ変換手段を含み、前記乗算手段は、取得した桁の値が０以外であると判断される場合に、前記モンゴメリ変換手段により算出された前記モンゴメリ変換値を用いて乗算剰余演算を行うとしてもよい。【００２３】
モンゴメリ変換手段は、第１のモンゴメリ変換部１１１に相当する。
この構成によると、取得した桁の値が０以外であると判断される場合においても、ＳＰＡに対抗して、不正な解析を困難にすることができる。
ここで、前記情報セキュリティ装置は、さらに、前記法の値を設定する法設定手段と、前記法の有効ビット数より大きい整数ｋをランダムに選択する整数設定手段とを備え、前記モンゴメリ変換手段は、設定された前記法の値に基づいて、前記整数ｋを用いて、前記モンゴメリ変換値を算出するとしてもよい。【００２４】
法設定手段は、法設定部１１７に相当し、整数設定手段は、整数設定部１１８に相当する。
この構成によると、前記法の有効ビット数より大きく、ランダムに選択された整数ｋをモンゴメリ変換値の算出において用いるので、入力値についてのハミング重みの偏りをさらに避けることができる。【００２５】
ここで、前記モンゴメリ変換手段は、前記法において、値２のｋ乗値を算出し、前記入力値と算出された値とを乗じて得られた値を前記モンゴメリ変換値とするとしてもよい。
この構成によると、確実にモンゴメリ変換値を算出することができる。
ここで、前記モンゴメリ変換手段は、前記モンゴメリ変換値として、前記法としての値の乱数倍の法において、値２のｋ乗値を算出するとしてもよい。【００２６】
この構成によると、入力値についてのハミング重みの偏りをさらに避けることができるモンゴメリ変換値を算出することができる。
【図面の簡単な説明】
【００２７】
【図１】本発明に係る１個の実施の形態としてのコンテンツ再生システム１の構成を示すシステム構成図である。
【図２】ＩＣカード１００及びＤＶＤプレーヤ２００の構成を示すブロック図である。
【図３】公開鍵復号部１０１の構成を示すブロック図である。
【図４】公開鍵復号部１０１による高速べき乗剰余演算の動作を示すフローチャートである。
【図５】公開鍵復号部１０１による別の高速べき乗剰余演算の動作を示すフローチャートである。
【図６】秘密鍵の下位ビットから処理する場合における公開鍵復号部１０１による高速べき乗剰余演算の動作を示すフローチャートである。
【符号の説明】
【００２８】
１    コンテンツ再生システム
１０    ネットワーク
１００    ＩＣカード
１０１    公開鍵復号部
１０２    入出力部
１１１    第１モンゴメリ変換部
１１２    第２モンゴメリ変換部
１１３    秘密鍵格納部
１１４    制御部
１１５    二乗算部
１１６    乗算部
１１７    法設定部
１１８    整数設定部
１１９    設定制御部
１２０    モンゴメリ逆変換部
２００    ＤＶＤプレーヤ
２０１    モニタ
２０２    スピーカ
２１１    通信部
２１２    入出力部
２１３    復号部
２１４    復号部
２１５    再生部
２１６    ドライブ部
３００    ＤＶＤ
４００    サーバ装置
【発明を実施するための最良の形態】
【００２９】
本発明に係る１個の実施の形態としてのコンテンツ再生システム１について説明する。
１．コンテンツ再生システム１の構成
コンテンツ再生システム１は、図１に示すように、ＩＣカード１００、ＤＶＤプレーヤ２００及びサーバ装置４００から構成されている。ＤＶＤプレーヤ２００及びサーバ装置４００は、ネットワーク１０を介して相互に接続されている。【００３０】
ＤＶＤプレーヤ２００には、利用者によりＤＶＤ３００が装着される。ＤＶＤ３００は、図２に示すように、暗号化コンテンツ３０１及び暗号化コンテンツ鍵３０２を記録している。暗号化コンテンツ３０１は、コンテンツ鍵を用いて、映像及び音声からなるコンテンツに、暗号化アルゴリズムＡＥＳ（Advanced Encryption Standard）を施して生成されたものであり、暗号化コンテンツ鍵３０２は、前記コンテンツの利用の許可を示すライセンス鍵Ｌを用いて、前記コンテンツ鍵に、暗号化アルゴリズムＡＥＳを施して生成されたものである。【００３１】
サーバ装置４００は、ＤＶＤプレーヤ２００の要求により、ＩＣカード１００の利用者の公開鍵（ｅ、ｐ）を用いて、ライセンス鍵Ｌに、暗号化アルゴリズムＲＳＡを施して、暗号化ライセンス鍵Ｃを生成する。
Ｃ＝Ｌe ｍｏｄ  ｐ
なお、ＲＳＡの公開鍵の生成については、周知であるので、説明を省略する。【００３２】
次に、サーバ装置４００は、生成した暗号化ライセンス鍵Ｃを、ＤＶＤプレーヤ２００の要求により、ネットワーク１０を介して、ＤＶＤプレーヤ２００へ送信する。
ＤＶＤプレーヤ２００は、図２に示すように、通信部２１１、入出力部２１２、復号部２１３、復号部２１４、再生部２１５及びドライブ部２１６から構成されており、モニタ２０１及びスピーカ２０２がＤＶＤプレーヤ２００に接続されている。【００３３】
ＤＶＤプレーヤ２００の通信部２１１は、サーバ装置４００からネットワーク１０を介して、暗号化ライセンス鍵Ｃを受信する。ＤＶＤプレーヤ２００には、利用者によりＩＣカード１００が装着される。ＤＶＤプレーヤ２００の入出力部２１２は、受信した暗号化ライセンス鍵ＣをＩＣカード１００へ出力する。
ＩＣカード１００は、公開鍵復号部１０１及び入出力部１０２から構成されている。ＩＣカード１００の入出力部１０２は、ＤＶＤプレーヤ２００から暗号化ライセンス鍵Ｃを受け取り、公開鍵復号部１０１は、入力データとして受け取った暗号化ライセンス鍵Ｃを、後述するようにして復号して、出力データとして復号ライセンス鍵を生成し、入出力部１０２は、生成した復号ライセンス鍵をＤＶＤプレーヤ２００へ出力する。【００３４】
ＤＶＤプレーヤ２００の入出力部２１２は、ＩＣカード１００から復号ライセンス鍵を受け取り、ドライブ部２１６は、ＤＶＤ３００から暗号化コンテンツ３０１及び暗号化コンテンツ鍵３０２を読み出し、復号部２１３は、受け取った復号ライセンス鍵を用いて、暗号化コンテンツ鍵３０２を復号して復号コンテンツ鍵を生成し、復号部２１４は、生成した復号コンテンツ鍵を用いて、暗号化コンテンツ３０１を復号して復号コンテンツを生成し、再生部２１５は、復号コンテンツを再生して映像信号及び音声信号を生成し、生成した映像信号をモニタ２０１へ出力し、生成した音声信号をスピーカ２０２へ出力する。【００３５】
ここで、ＩＣカード１００及びＤＶＤプレーヤ２００は、それぞれ、具体的には、マイクロプロセッサ、ＲＯＭ、ＲＡＭなどから構成されるコンピュータシステムである。前記ＲＡＭには、コンピュータプログラムが記憶されている。前記マイクロプロセッサが、前記コンピュータプログラムに従って動作することにより、各装置は、その機能を達成する。【００３６】
なお、図２において、ＤＶＤプレーヤ２００の各構成部を示す各ブロックは、接続線により他のブロックと接続されている。ただし、一部の接続線を省略している。ここで、各接続線は、信号や情報が伝達される経路を示している。また、復号部２１３を示すブロックに接続している複数の接続線のうち、接続線上に鍵マークが描かれているものは、復号部２１３へ鍵としての情報が伝達される経路を示している。復号部２１４を示すブロックについても同様である。【００３７】
ここで、ＩＣカード１００は、所定の法において入力値を整数乗するべき乗剰余演算により、入力値の安全な処理を行う情報セキュリティ装置である。
２．公開鍵復号部１０１の構成
公開鍵復号部１０１は、図３に示すように、記憶部１２１、第１モンゴメリ変換部１１１、第２モンゴメリ変換部１１２、秘密鍵格納部１１３、制御部１１４、二乗算部１１５、乗算部１１６、法設定部１１７、整数設定部１１８、設定制御部１１９及びモンゴメリ逆変換部１２０から構成されている。【００３８】
公開鍵復号部１０１は、秘密鍵Ｓと法ｐを内部に記憶しており、入力データＣを入力として公開鍵暗号の計算を行い、計算結果の出力データＭ＝Ｃs   ｍｏｄ  ｐを出力する。ここで、出力データＭは、秘密鍵Ｓをべきとし、ｐを法とする入力データＣのべき乗剰余演算値である。ｍｏｄ  ｐは、ｐで除したときの剰余を求めることを示す。なお、本実施の形態において、前記公開鍵暗号の計算はＲＳＡ暗号の復号処理である。従って、入力データは暗号文Ｃ、出力データは復号文Ｍに相当する。具体的には、入力データは、上述した暗号化ライセンス鍵であり、出力データは、上述した復号ライセンス鍵である。【００３９】
公開鍵復号部１０１は、前述した秘密鍵Ｓの各ビットの上位から１ビットずつについて、設定された法におけるモンゴメリ領域での２乗算と乗算とを繰り返す高速べき指数演算を行う。公開鍵復号部１０１の全体の動作については後述する。
（１）  法設定部１１７、整数設定部１１８及び設定制御部１１９
法設定部１１７は、設定制御部１１９の制御により、モンゴメリ変換、２乗算、乗算で用いる法ｐを設定する。法設定部１１７は、設定した法ｐを第１モンゴメリ変換部１１１、第２モンゴメリ変換部１１２、二乗算部１１５、乗算部１１６及びモンゴメリ逆変換部１２０へ出力する。【００４０】
整数設定部１１８は、設定制御部１１９の制御により、ｐのビット数よりも大きい整数ｋを、ランダムに設定する。なお、ここでｐの「ビット数」とは、ｐのうち、値「１」がセットされている最上位のビット位置から最下位のビット位置までのビット長であり、いわゆる「有効ビット数」のことを意味する。整数設定部１１８は、整数ｋを第１モンゴメリ変換部１１１、第２モンゴメリ変換部１１２、二乗算部１１５、乗算部１１６及びモンゴメリ逆変換部１２０へ出力する。【００４１】
設定制御部１１９は、整数設定部１１８に対して、整数ｋの設定範囲や設定変更のタイミングを制御する。設定変更のタイミングの一例として、設定制御部１１９は、入力データＣの値が変わるごとに変更してもよいし、入力データＣの演算途中で変更してもよい。
ここで設定された整数ｋと法ｐとは、以降の、モンゴメリ変換、二乗算、乗算及びモンゴメリ逆変換で用いられる。【００４２】
（２）記憶部１２１、第１モンゴメリ変換部１１１及び第２モンゴメリ変換部１１２
記憶部１２１は、入出力部１０２から入力データＣを受け取り、受け取った入力データＣを記憶する。
第１モンゴメリ変換部１１１は、記憶部１２１から入力データＣを読み出し、法設定部１１７から法ｐを受け取り、整数設定部１１８から整数ｋを受け取る。次に、入力データＣ、法ｐ及び整数ｋを用いて、次式により、Ｃのモンゴメリ変換値Ｂを算出する。【００４３】
モンゴメリ変換値Ｂ＝Ｃ×（２k ）ｍｏｄ  ｐ
次に、第１モンゴメリ変換部１１１は、算出したモンゴメリ変換値Ｂを制御部１１４へ出力する。
また、第２モンゴメリ変換部１１２は、法設定部１１７から法ｐを受け取り、整数設定部１１８から整数ｋを受け取る。次に、法ｐ及び整数ｋを用いて、次式により、「１」のモンゴメリ変換値Ａを算出する。【００４４】
モンゴメリ変換値Ａ＝（２k ）ｍｏｄ  ｐ
次に、第２モンゴメリ変換部１１２は、算出したモンゴメリ変換値Ａを制御部１１４へ出力する。
なお、以降ではモンゴメリ変換をＭｏｎ＿｛ｋ，ｐ｝（Ｘ）と表記する。
Ｍｏｎ＿｛ｋ，ｐ｝（Ｘ）  ＝  Ｘ×２k   ｍｏｄ  ｐ    （式１）
なお、変換関数の｛ｋ，ｐ｝は、モンゴメリ変換値が、整数ｋ、法ｐに依存することを示す。この表記を用いると、第１モンゴメリ変換部１１１により出力されるモンゴメリ変換値Ｂは、Ｍｏｎ＿｛ｋ，ｐ｝（Ｃ）であり、第２モンゴメリ変換部１１２により出力されるモンゴメリ変換値Ａは、Ｍｏｎ＿｛ｋ，ｐ｝（１）である。【００４５】
（３）秘密鍵格納部１１３
秘密鍵格納部１１３は、公開鍵暗号の秘密鍵Ｓを格納している。秘密鍵Ｓは、安全性確保のため少なくとも２０４８ビット以上は必要とされている。
（４）抽出部１２２、制御部１１４、二乗算部１１５及び乗算部１１６
抽出部１２２は、制御部１１４の指示により、秘密鍵格納部１１３に格納されている秘密鍵Ｓの各ビットの上位から１ビットずつ抽出し、抽出したビットの値を制御部１１４へ出力する。【００４６】
制御部１１４は、秘密鍵Ｓの上位から１ビットについて、２乗算と乗算の処理を繰り返す。例えば、秘密鍵が２０４８ビットの場合は２０４８回、２乗算と乗算の処理を繰り返す。繰り返しが終了したら、モンゴメリ逆変換部１２０は、その演算結果をモンゴメリ逆変換し、公開鍵復号部１０１は、Ｍ＝ＣS ｍｏｄ  ｐを出力する。
制御部１１４は、上記繰り返し制御とともに、秘密鍵の当該ビットが「１」のときには、第１モンゴメリ変換部１１１の出力値を選択し、「０」のときには第２モンゴメリ変換部１１２の出力値を選択する。【００４７】
二乗算部１１５及び乗算部１１６は、それぞれ、モンゴメリ領域での２乗算及び乗算を実行する。
ここでのモンゴメリ領域の乗算は、モンゴメリ領域に変換された２個の入力値、例えば、Ｍｏｎ＿｛ｋ，ｐ｝（Ｘ）とＭｏｎ＿｛ｋ，ｐ｝（Ｙ）の積に対して、モンゴメリリダクション処理を行い、モンゴメリ領域の乗算結果Ｍｏｎ＿｛ｋ，ｐ｝（Ｚ）＝Ｍｏｎ＿｛ｋ，ｐ｝（Ｘ×Ｙ）を求めるものである。２乗算は、上記ＸとＹが同じ場合に相当する。【００４８】
ここで、モンゴメリリダクションは、倍長値Ｕ（上記では、Ｘ×Ｙ）に対して、Ｕ×（２k ）-1  ｍｏｄ  ｐの演算を、除算なしで高速に実装する方法である。モンゴメリリダクションの詳細については、例えば非特許文献３に詳しい。
なお、仮に法のビット数が２０４８ビットである場合、二乗算部１１５と乗算部１１６を、２０４８ビットの乗算器で実装するのは実装規模が巨大となり現実的でない。そのため、例えば３２ビット程度の乗算器を繰り返して用いる多倍長演算方法で実現するのが、一般的である。【００４９】
（５）  モンゴメリ逆変換部１２０
モンゴメリ逆変換部１２０は、モンゴメリ領域での２乗算と乗算との繰り返しの最終結果に、モンゴメリ逆変換を施して、出力データＭを求める。以降ではモンゴメリ逆変換を
Ｍｏｎ＿｛ｋ，ｐ｝-1（  ）と表記する。
Ｍｏｎ＿｛ｋ，ｐ｝-1（Ｘ）＝Ｘ×（２k ）-1  ｍｏｄ  ｐ    （式２）
なお、モンゴメリ変換とモンゴメリ逆変換について、式３が成り立つ。【００５０】
Ｍｏｎ＿｛ｋ，ｐ｝-1（Ｍｏｎ＿｛ｋ，ｐ｝（Ｘ））＝Ｘ      （式３）
モンゴメリ逆変換部１２０は、出力データＭを入出力部１０２へ出力する。
３．公開鍵復号部１０１の動作
公開鍵復号部１０１による高速べき乗剰余演算の動作について、図４に示すフローチャートを用いて説明する。【００５１】
法設定部１１７は、法ｐを定め、整数設定部１１８は、整数ｋを定め、第１モンゴメリ変換部１１１は、モンゴメリ変換値Ｂ＝Ｃ×（２k ）ｍｏｄ  ｐ  を算出し、第２モンゴメリ変換部１１２は、モンゴメリ変換値Ａ＝（２k ）ｍｏｄ  ｐ  を算出する（ステップＳ１０１）。
制御部１１４は、第２モンゴメリ変換部１１２によるモンゴメリ変換値Ａを選択し、演算結果の値を格納する演算値領域に設けられた変数としての演算結果Ｗに、初期値として選択したモンゴメリ変換値Ａを書き込む。【００５２】
Ｗ＝Ｍｏｎ＿｛ｋ，ｐ｝（１）＝（２k ）ｍｏｄ  ｐ  （ステップＳ１０２）
制御部１１４は、抽出部１２２により、秘密鍵格納部１１３に格納されている秘密鍵Ｓの最上位から１ビットずつ抽出を試みる（ステップＳ１０３）。
秘密鍵Ｓの最上位のビットから最下位のビットまで、前記抽出が完了したら（ステップＳ１０４でＹＥＳ）、制御部１１４は、モンゴメリ逆変換部１２０に対して演算結果Ｗのモンゴメリ逆変換をするように制御し、モンゴメリ逆変換部１２０は、演算結果Ｗに対して、モンゴメリ逆変換を施して、出力データＭを生成する。【００５３】
Ｍ＝Ｍｏｎ＿｛ｋ，ｐ｝-1（Ｗ）
次に、モンゴメリ逆変換部１２０は、出力データＭを入出力部１０２へ出力する。ここで、Ｍ＝ＣS   ｍｏｄ  ｐである（ステップＳ１０９）。こうして、公開鍵復号部１０１による高速べき乗剰余演算が終了する。
抽出が完了していない場合（ステップＳ１０４でＮＯ）、制御部１１４は、二乗算部１１５に対して演算結果Ｗをモンゴメリ領域で２乗するように制御し、二乗算部１１５は、演算結果Ｗをモンゴメリ領域で２乗し、その２乗値を演算結果Ｗに上書きする。【００５４】
Ｗ＝Ｍｏｎ＿｛ｋ，ｐ｝（Ｗ×Ｗ）    （ステップＳ１０５）。
次に、制御部１１４は、抽出したビットが「１」か又は「０」であるかを判断し、秘密鍵Ｓから抽出した当該ビットが「１」のときには（ステップＳ１０６）、第１モンゴメリ変換部１１１により出力されるモンゴメリ変換値Ｂを選択し、乗算部１１６に対してモンゴメリ乗算を算出するように制御し、乗算部１１６は、演算結果Ｗと第１モンゴメリ変換部１１１により出力されるモンゴメリ変換値Ｂ＝Ｍｏｎ＿｛ｋ，ｐ｝（Ｃ）とを乗算し、得られた値を演算結果Ｗへ上書きする。【００５５】
Ｗ＝Ｍｏｎ＿｛ｋ，ｐ｝（Ｗ×Ｂ）  （ステップＳ１０７）。次に、制御部１１４は、制御をステップＳ１０３へ移す。
一方、秘密鍵Ｓから抽出した当該ビットが「０」のときには、制御部１１４は、第２モンゴメリ変換部１１２の出力値を選択し、乗算部１１６に対してモンゴメリ乗算を算出するように制御し、乗算部１１６は、演算結果Ｗと第２モンゴメリ変換部１１２の出力値であるＡ＝Ｍｏｎ＿｛ｋ，ｐ｝（１）とを乗算し、得られた値を演算結果Ｗへ上書きする。【００５６】
Ｗ＝Ｍｏｎ＿｛ｋ，ｐ｝（Ｗ×Ａ）  （ステップＳ１０８）。次に、制御部１１４は、制御をステップＳ１０３へ移す。
３．実施の形態の効果
まず、図４に示すフローチャートから明らかなように、秘密鍵Ｓの当該ビットが「１」であるか又は「０」であるかにかかわらず、必ずモンゴメリの乗算部１１６は動作する。そのため、乗算の有無で解析を行う攻撃であるＳＰＡは困難である。【００５７】
本実施の形態では、秘密鍵の当該ビットが「０」である場合の乗算には、モンゴメリ領域での「１」（Ｍｏｎ＿｛ｋ，ｐ｝（１）と表記）を用いる。このモンゴメリ領域での「１」は整数ｋと法ｐに依存して定まる値であるため、ｋおよびｐを知らない攻撃者はハミング重みを予測することができない。そのためモンゴメリ領域での「１」を判別して解析をすることは困難である。【００５８】
また、万が一、ハミング重みが攻撃者により求められてしまった場合には、モンゴメリ領域での「１」を判別する解析が成功するかもしれない。本実施の形態では、さらに、法ｐのビット数以上という制限のもとに、整数ｋを任意に変更することにより、ハミング重みも変更される。これにより、いっそう、解析が困難となる。
なお、その変更タイミングは頻繁であるほど、さらに、その整数ｋの取りうるバラエティが多いほど、ダミー乗算を区別することは困難であり安全性が向上する。しかし、ｋをむやみに大きくとると１回の２乗算や乗算の処理時間が一般には増加するため、どの程度のバラエティをもったｋの大きさにするのか、あるいは変更のタイミングをどう設定するのかは、アプリケーションに必要とされる速度と安全性に依存して決定する。図３における設定制御部１１９がこれらの制御をする。【００５９】
４．その他の変形例
なお、本発明を上記の実施の形態に基づいて説明してきたが、本発明は、上記の実施の形態に限定されないのはもちろんである。以下のような場合も本発明に含まれる。
（１）公開鍵復号部１０１による上記とは別の高速べき乗剰余演算の動作について、図５に示すフローチャートを用いて説明する。【００６０】
法設定部１１７は、法ｐを定める。ここで、法ｐは、例えば、５１２ビットの秘密の素数である。また、法設定部１１７は、ｐより大きい任意の２のべき乗値Ｒを定める。例えば、乱数ｋを生成し、Ｒ＝２k とする。例えば、Ｒ＝２512 である。また、法設定部１１７は、乱数ｒを生成する（ステップＳ２０１）。
次に、第２モンゴメリ変換部１１２は、モンゴメリ変換値ｙを算出する。【００６１】
ｙ＝Ｍ（１）＝Ｒ  ｍｏｄ  ｐ  ＝Ｒ  −  ｐ
ｙは、演算結果の値を格納するための演算値領域に設けられる変数である。
なお、ここでは、「Ｍｏｎ＿｛ｋ，ｐ｝（１）」を更に簡略に「Ｍ（１）」と表現している（ステップＳ２０２）。
制御部１１４は、抽出部１２２により、秘密鍵格納部１１３に格納されている秘密鍵Ｓの最上位から１ビットずつ抽出を試みる（ステップＳ２０３）。【００６２】
秘密鍵Ｓの最上位ビットから最下位ビットまで、抽出が完了したら（ステップＳ２０４でＹＥＳ）、ｙを出力し（ステップＳ２０９）、公開鍵復号部１０１による高速べき乗剰余演算が終了する。
抽出が完了していない場合（ステップＳ２０４でＮＯ）、二乗算部１１５は、次式による二乗算を行う。【００６３】
ｙ＝｛ｙ×ｙ｝×Ｒ-1  ｍｏｄ  ｒ×ｐ          （ステップＳ２０５）。
次に、制御部１１４は、抽出したビットが「１」か又は「０」であるかを判断し、秘密鍵Ｓから抽出した当該ビットが「１」のときには（ステップＳ２０６）、乗算部１１６は、次式による乗算を行う。
ｙ＝｛ｙ×Ｍ（Ｃ）｝×Ｒ-1  ｍｏｄ  ｒ×ｐ    （ステップＳ２０７）。
次に、制御部１１４は、制御をステップＳ２０３へ移す。【００６４】
一方、秘密鍵Ｓから抽出した当該ビットが「０」のときには、乗算部１１６は、次式による乗算を行う。
ｙ＝｛ｙ×Ｍ（１）｝×Ｒ-1  ｍｏｄ  ｒ×ｐ    （ステップＳ２０８）。
次に、制御部１１４は、制御をステップＳ１０３へ移す。
この変形例では、公開鍵復号部１０１は、モンゴメリ逆変換部１２０を含んでない。【００６５】
（２）整数ｋの変更タイミングは、入力データごとであってもよい。つまり、第１の入力データを取得すると、整数ｋの値をランダムに変更し、次に第２の入力データを取得すると、整数ｋの値をさらにランダムに変更し、さらに第３の入力データを取得すると、整数ｋの値をさらにランダムに変更する。
また、複数の入力データに対して同じｋを用いてもよい。次の複数の入力データに対して、別の同じ整数を用いてもよい。【００６６】
また、ある入力データの演算の途中（繰返しの途中）でランダムに変更してもよい。また、外部よりアプリケーションやユーザが指示するタイミングでランダムに変更してもよい。
第１及び第２モンゴメリ変換部において用いられる法についても、上記と同様に、入力データごとにランダムに変更してもよいし、複数の入力データに対して同じ法を用いてもよいし、次の複数の入力データに対して、別の同じ整数を用いてもよいし、ある入力データの演算の途中（繰返しの途中）でランダムに変更してもよいし、外部よりアプリケーションやユーザが指示するタイミングでランダムに変更してもよい。【００６７】
（３）（ａ）ｐの乱数倍を法として用いて、第２モンゴメリ変換部１１２の出力を求めてもよい。つまり、法設定部１１７は、乱数ｒを生成し、生成した乱数ｒを第２モンゴメリ変換部１１２へ出力する。第２モンゴメリ変換部１１２は、
２k ｍｏｄ  （ｒ×ｐ）を出力する。
このことにより、第１モンゴメリ変換部１１１あるいは第２モンゴメリ変換部１１２のいずれを使用しているのかを区別することがよりいっそう困難となり安全性が向上する。【００６８】
このとき、第２モンゴメリ変換部１１２の法は、ｐのままでよいし、また、別の乱数倍であってもよい。
このように、第１モンゴメリ変換部１１１の法と、第２モンゴメリ変換部１１２の法とに対して独立して設定されるとしてもよい。
なお、モンゴメリ逆変換部１２０の法は、ｐのままである。【００６９】
（ｂ）また、第１モンゴメリ変換部１１１で用いる法をｐの乱数倍としてもよい。このとき、第２モンゴメリ変換部１１２の法は、ｐのままでよいし、また、別の乱数倍であってもよい。なお、モンゴメリ逆変換部１２０の法は、ｐのままとする。これにより、１つの入力データの演算中の、複数箇所の電力変化間の相関を計算する攻撃に対して安全性が向上する。【００７０】
また、まずｐの乱数倍を新たな法として求めた後、これを用いて第１モンゴメリ変換部１１１、第２モンゴメリ変換部１１２、そして二乗算部１１５や乗算部１１６での計算を行ってよい。ただし、この場合、定められた法のもとの最終出力を得るためには、出力の前に、法ｐで剰余演算をしてから、出力することが必要になる。
（ｃ）上記（ａ）（ｂ）において、第１モンゴメリ変換部１１１においてｐの乱数倍の法（第１の法）が用いられ、第２モンゴメリ変換部１１２においてｐの別の乱数倍の法（第２の法）が用いられる場合、つまり、第１の法と第２の法とが異なる場合には、二乗算部１１５と乗算部１１６とにおいて用いられる法は、第１の法と第２の法の公倍数とし、モンゴメリ逆変換部１２０において用いられる法は、ｐのままとすればよい。【００７１】
（４）入力データ及び出力データを、モンゴメリ領域の値としてもよい。この場合、実施の形態で含まれている、第１モンゴメリ変換部１１１とモンゴメリ逆変換部１２０は公開鍵復号部１０１の外に実装されてもよい。これは、例えば大きなシステムの中の一部として公開鍵復号部１０１が実装されており、公開鍵暗号の演算のみならず、すべてをモンゴメリ領域で実装する場合である。【００７２】
（５）本実施の形態では、秘密鍵を１ビットずつ処理する高速バイナリべき乗剰余演算を用いているが、何も１ビットごとの処理だけとは限らない。
例えば、２ビットごとの処理であれば、二乗算部１１５では２回の２乗算を行い、制御部１１４では、秘密鍵の２ビットに対応して４種類のモンゴメリ変換部からの出力値を選択し、選択した出力値を乗算部１１６で乗算する。【００７３】
なお、この４種類のモンゴメリ変換部のうちの１つは、「１」のモンゴメリ変換部（つまり、ダミー乗算の入力値を求める部分）となり、秘密鍵の当該２ビットが両方とも「０」である場合に選択される。
ここで、２ビットが「００」のとき、対応するモンゴメリ変換部は、「１」のモンゴメリ変換値を出力し、２ビットが「０１」のとき、対応するモンゴメリ変換部は、「Ｃ」のモンゴメリ変換値を出力する。また、２ビットが「１０」のとき、対応するモンゴメリ変換部は、「Ｃ2 」のモンゴメリ変換値を出力し、２ビットが「１１」のとき、対応するモンゴメリ変換部は、「Ｃ3 」のモンゴメリ変換値を出力する。【００７４】
もちろん秘密鍵を３ビット以上ごとに処理する場合であっても、上記を拡張して適用することで実現できる。
また、本実施の形態では、秘密鍵を上位から処理するアルゴリズムを用いているが、下位から処理するものであってもよい。この場合には、入力データに対応したモンゴメリ変換値を繰り返し２乗し、秘密鍵の対応するビットが１のときには、前記２乗演算値を乗算し、０のときには、本実施の形態と同様に、整数ｋと法ｐから求められる値を用いたダミー乗算を行う。【００７５】
この場合における公開鍵復号部１０１による高速べき乗剰余演算の動作について、図４との相違点を中心として、図６に示すフローチャートを用いて説明する。
図４に示すステップＳ１０３に代えて、ステップＳ１０３ａにおいて、制御部１１４は、抽出部１２２により、秘密鍵格納部１１３に格納されている秘密鍵Ｓの最下位から１ビットずつ抽出を試みる。【００７６】
秘密鍵Ｓの最下位のビットから最上位のビットまで、前記抽出が完了したら（ステップＳ１０４ａでＹＥＳ）、制御部１１４は、モンゴメリ逆変換部１２０に対して演算結果Ｗのモンゴメリ逆変換をするように制御する。
抽出が完了していない場合（ステップＳ１０４ａでＮＯ）、図４に示すステップＳ１０５に代えて、ステップＳ１０５ａにおいて、制御部１１４は、二乗算部１１５に対して入力データＣをモンゴメリ領域で２乗するように制御し、二乗算部１１５は、入力データＣをモンゴメリ領域で２乗し、その２乗値を入力データＣに上書きする。【００７７】
Ｃ＝Ｍｏｎ＿｛ｋ，ｐ｝（Ｃ×Ｃ）
（６）本実施の形態では、ＲＳＡ暗号の復号処理で説明したが、次に示すように、ＲＳＡ署名の署名生成に適用してもよい。
ＲＳＡの鍵生成を行う。ＲＳＡの鍵生成は、ＲＳＡ暗号の場合と同じであるので詳細を省略する。【００７８】
ここで、秘密鍵をｄとし、公開鍵をｅ、ｐとする。
署名生成装置は、次式により、文書ｍに対して、署名データｓを生成する。
ｓ＝ｈ（ｍ）d ｍｏｄ  ｐ
ここで、ｈ（  ）は、一方向性ハッシュ関数である。
本発明は、前記署名生成装置において、上記の実施の形態と同様にして適用される。前記署名生成装置は、所定の法において入力値を整数乗するべき乗剰余演算により、入力値の確実な処理を行う情報セキュリティ装置である。【００７９】
なお、署名検証装置は、次式により、署名の検証を行う。
ｈ（ｍ）＝ｓe ｍｏｄ  ｐ
また、本発明は、ＲＳＡ暗号の暗号処理において、公開鍵を秘匿するようなアプリケーションの場合に、適用することができる。
さらに、楕円曲線暗号や超楕円曲線暗号における、秘密鍵を用いた処理におけるＳＰＡ対策としても用いることができる。【００８０】
（７）上記の実施の形態及び変形例は、次に示すような場合において適用される。
（ａ）実施の形態及び変形例は、秘密のメッセージ伝送において適用される。
本実施の形態において、秘密のメッセージ伝送の一例として、ライセンス鍵を秘密に伝送する場合について説明した。
上述したように、ＩＣカード１００は、所定の法において入力値を整数乗するべき乗剰余演算により、入力値の安全な処理を行う情報セキュリティ装置である。ここで、「安全」とは、メッセージが送信者及び受信者以外の第三者に知られないように秘密にすることをいう。【００８１】
本発明は、コンテンツ暗号化装置とコンテンツ再生装置とから構成されるコンテンツ配信システムにおいて適用され、例えば、映画、動画像、音声、音楽、小説、データベースなどのデジタル情報を秘密通信の対象としてもよい。これらのコンテンツは、コンテンツ供給者から利用者に対して、これらのコンテンツを記録している記録媒体を販売したり、レンタルすることにより、提供される。また、デジタル放送やインターネットを介して、コンテンツ供給者から利用者に提供される。【００８２】
コンテンツ供給者の有するコンテンツ暗号化装置は、デジタル著作物である映画を暗号化してＤＶＤに記録する。利用者の有するコンテンツ再生装置は、ＤＶＤから暗号化デジタル著作物を読み出し、復号して、映画を生成し、生成した映画を音声及び映像として再生して、表示及び出力する。
上記の例において、コンテンツを暗号化及び復号するためのコンテンツ鍵を、実施の形態に示す秘密通信の対象としてもよい。この場合、コンテンツ鍵は、実施の形態に示す方法と同様にして、暗号化され、また復号される。【００８３】
この場合に、コンテンツは、コンテンツ鍵により、共通鍵暗号方式を用いて、暗号化され、復号される。
次に示すような金銭の決済システムに適用することもできる。
例えば、通貨の代わりに用いることができる電子マネーを秘密通信の対象とし、ＩＣカードは、電子マネーを記憶しており、利用者が、商品を購入する際に、ＩＣカードは、商品の購入額に相当する電子マネーを暗号化して送信し、また、内部に記憶している電子マネーから送信した分を減じる。商店に設置されるレジスタ装置は、暗号化電子マネーを受信し、受信した暗号化電子マネーを復号して電子マネーを再生し、記憶する。【００８４】
また、上記のＩＣカードに代えて、美術館や博物館などの各種施設を利用のためのＩＣカードタイプの電子チケットが、上記のように、電子マネーに相当する情報を記憶しているとしてもよい。各種施設の入り口に設けられた入場管理装置は、各種施設の利用料金に相当する額の電子マネーを要求し、前記電子チケットは、要求された額の電子マネーを暗号化して送信し、入場管理装置は、暗号化電子マネーを受信し、受信した暗号化電子マネーを復号して電子マネーを生成し、記憶するとしてもよい。【００８５】
また、鉄道、バスなどの交通機関を利用する際に用いられるＩＣカードタイプのＩＣカード乗車券が、上記のように、電子マネーに相当する情報を記憶しているとしてもよい。交通機関の駅の入り口に設けられた入場管理装置は、当該駅を識別する識別情報を送信し、ＩＣカード乗車券は、前記識別情報を受信し、記憶する。交通機関の駅の出口に設けられた出場管理装置は、前記識別情報をＩＣカード乗車券から受信し、受信した識別情報と当該出場管理装置が設けられた駅とを用いて、料金表により乗車料金を算出し、算出した乗車料金に相当する額の電子マネーを要求し、ＩＣカード乗車券は、要求された額の電子マネーを暗号化して送信し、出場管理装置は、暗号化電子マネーを受信し、受信した暗号化電子マネーを復号して電子マネーを生成し、記憶する。【００８６】
（ｂ）実施の形態及び変形例は、認証において適用される。認証とは、メッセージが自称どおりの人物によって送られたこと、またメッセージが改竄されなかったということの検証である。また、実施の形態及び変形例は、身分の証明において適用される。身分の証明とは、例えば、データへのアクセス権、又は施設へのアクセス権（入室権）を持つことの証明、又は自分が主張どおりの人物であることの証明である。さらに、実施の形態及び変形例は、否認防止において適用される。否認防止とは、例えば、実は何かに同意したのに、同意していないと主張する者に対抗することをいう。【００８７】
上記の変形例において、認証の一例として、ＲＳＡデジタル署名について説明した。本発明は、上述した署名生成装置において、上記の実施の形態と同様にして適用される。前記署名生成装置は、所定の法において入力値を整数乗するべき乗剰余演算により、入力値の確実な処理を行う情報セキュリティ装置である。
ここで、「確実」とは、例えば、メッセージが自称どおりの人物によって送られたこと、またメッセージが改竄されなかったことである。また、例えば、データへのアクセス権を持つこと、施設へのアクセス権（入室権）を持つこと、又は自分が主張どおりの人物であることである。【００８８】
（ｃ）実施の形態及び変形例は、鍵交換（鍵共有とも呼ぶ）において適用される。鍵交換とは、例えば、２人の人が放送電波を使ってある秘密鍵暗号方式で使うための秘密鍵に同意することである。
鍵交換の典型的な方法として、ＤＨ（ディフィーヘルマン）鍵交換という方法がある。ここでは、鍵を交換しあうそれぞれが、秘密のべき数を任意に生成し、これを用いてべき乗演算を行う。【００８９】
このときの、べき乗演算に本発明を適用し、秘密のべき数を秘匿して秘密の共通鍵を共有することができる。
（ｄ）実施の形態及び変形例は、零知識証明において適用される。零知識証明とは、例えば、ある人が、数論的あるいは組合せ論的問題を解くことに成功したことを、解が何であるかのわずかの情報さえ与えることなく、他人にこのことを納得させることを言う。【００９０】
（ｅ）上述したように、本発明は、秘密のべき値を用いたべき乗演算を用いるプロトコル方式に適用することができる。
（８）本発明は、入力データと秘密鍵を使って、定められた法における乗算を繰り返してべき乗剰余計算を行う情報セキュリティ装置である。前記情報セキュリティ装置は、前記入力データに対応したモンゴメリ変換値を求める第１のモンゴメリ変換部と、１のモンゴメリ変換値を求める第２のモンゴメリ変換部と、秘密鍵のビットが０ならば、前記第２のモンゴメリ変換部の出力を選択し、そうでなければ前記第１のモンゴメリ変換部の出力を選択する制御部と、これまで計算した結果と前記制御部で選択した値を用いて乗算を行う乗算部を備えており、前記法をｐとし、ｐの有効ビット数より大きな整数をｋとするとき、前記第２のモンゴメリ変換部は、前記ｐを法として、前記ｋをべきとする２のべき乗値を出力する。この情報セキュリティ装置によると、第２のモンゴメリ変換部の出力（モンゴメリ領域での１）は、整数ｋと法ｐに依存して決定される。そのため、ハミング重みに偏りはなく、電力変化を用いて、乗算の入力として第１のモンゴメリ変換部の出力を用いたのか、第２のモンゴメリ変換部の出力を用いたのかを区別することは困難である。【００９１】
ここで、前記ｐの有効ビット数より大きな整数ｋをランダムに選択する整数ｋ設定部を備えると構成してもよい。この構成によると、ランダムに選択される整数ｋに依存して、第２のモンゴメリ変換部の出力が変わる。そのため、複数入力データにわたり、電力変化の相関を計算する攻撃に対して安全性が向上する。
ここで、前記第２のモンゴメリ変換部は、前記ｐの乱数倍を法として、前記ｋをべきとする２のべき乗値を出力すると構成してもよい。この構成によると、ランダムに選択される法の値に依存して、第２のモンゴメリ変換部の出力が変わる。そのため、複数入力データにわたり、電力変化の相関を計算する攻撃に対して安全性が向上する。【００９２】
ここで、前記第１のモンゴメリ変換部は、前記ｐの乱数倍を法として、前記入力データに対応したモンゴメリ変換値を出力すると構成してもよい。この構成によると法の変化に依存して、第１のモンゴメリ変換部の出力が変わる。このため、１つの入力データの演算中の、複数箇所の電力変化間の相関を計算する攻撃に対して安全性が向上する。
ここで、前記ｐの乱数倍を新たに法とする法変更部を備え、設定した法を用いて前記第１のモンゴメリ変換部、第２のモンゴメリ変換部および前記乗算部にて所定の計算が処理されると構成してもよい。この構成によると法変更部で変更される法に依存して、第１のモンゴメリ変換部、第２のモンゴメリ変換部のみならず、乗算部で用いる法も変換されるため、よりいっそう電力変化と秘密鍵の相関が小さくなり安全性が向上する。【００９３】
ここで、前記整数ｋあるいは前記法は、外部からの指示により変更されると構成してもよい。この構成によると、外部のアプリケーションやユーザが指定したタイミングで整数ｋや法を変化させることで、そのタイミングに対応した性能と安全性を有した情報セキュリティ装置が実現できる。
（９）上記の各装置は、具体的には、マイクロプロセッサ、ＲＯＭ、ＲＡＭ、などから構成されるコンピュータシステムである。前記ＲＡＭには、コンピュータプログラムが記憶されている。ここで、コンピュータプログラムは、所定の機能を達成するために、コンピュータに対する指令を示す命令コードが複数個組み合わされて構成されたものである。前記マイクロプロセッサが、前記コンピュータプログラムに従って動作することにより、各装置は、その機能を達成する。つまり、前記マイクロプロセッサは、前記コンピュータプログラムに含まれる各命令を１個ずつ読み出し、読み出した命令を解読し、解読結果に従って動作する。【００９４】
（１０）上記の各装置を構成する構成要素の一部又は全部は、１個のシステムＬＳＩ（Large Scale Integration：大規模集積回路）から構成されているとしてもよい。システムＬＳＩは、複数の構成部を１個のチップ上に集積して製造された超多機能ＬＳＩであり、具体的には、マイクロプロセッサ、ＲＯＭ、ＲＡＭなどを含んで構成されるコンピュータシステムである。前記ＲＡＭには、コンピュータプログラムが記憶されている。前記マイクロプロセッサが、前記コンピュータプログラムに従って動作することにより、システムＬＳＩは、その機能を達成する。【００９５】
また、上記の各装置を構成する構成要素の各部は、個別に１チップ化されても良いし、一部又は全てを含むように１チップ化されてもよい。また、ここでは、ＬＳＩとしたが、集積度の違いにより、ＩＣ、システムＬＳＩ、スーパーＬＳＩ、ウルトラＬＳＩと呼称されることもある。
また、集積回路化の手法はＬＳＩに限るものではなく、専用回路又は汎用プロセッサで実現してもよい。ＬＳＩ製造後に、プログラムすることが可能なＦＰＧＡ（Field Programmable Gate Array）やＬＳＩ内部の回路セルの接続や設定を再構成可能なリコンフィギュラブル・プロセッサを利用しても良い。【００９６】
さらには、半導体技術の進歩又は派生する別技術によりＬＳＩに置き換わる集積回路化の技術が登場すれば、当然、その技術を用いて機能ブロックの集積化を行ってもよい。バイオ技術の適応等が可能性としてありえる。
（１１）上記の各装置を構成する構成要素の一部又は全部は、各装置に脱着可能なＩＣカード又は単体のモジュールから構成されているとしてもよい。前記ＩＣカード又は前記モジュールは、マイクロプロセッサ、ＲＯＭ、ＲＡＭ、などから構成されるコンピュータシステムである。前記ＩＣカード又は前記モジュールは、上記の超多機能ＬＳＩを含むとしてもよい。マイクロプロセッサが、コンピュータプログラムに従って動作することにより、前記ＩＣカード又は前記モジュールは、その機能を達成する。このＩＣカード又はこのモジュールは、耐タンパ性を有するとしてもよい。【００９７】
（１２）本発明は、上記に示す方法であるとしてもよい。また、これらの方法をコンピュータにより実現するコンピュータプログラムであるとしてもよいし、前記コンピュータプログラムからなるデジタル信号であるとしてもよい。
また、本発明は、前記コンピュータプログラム又は前記デジタル信号をコンピュータ読み取り可能な記録媒体、例えば、フレキシブルディスク、ハードディスク、ＣＤ―ＲＯＭ、ＭＯ、ＤＶＤ、ＤＶＤ−ＲＯＭ、ＤＶＤ−ＲＡＭ、ＢＤ（Ｂｌｕ−ｒａｙ  Ｄｉｓｃ）、半導体メモリなど、に記録したものとしてもよい。また、これらの記録媒体に記録されている前記コンピュータプログラム又は前記デジタル信号であるとしてもよい。【００９８】
また、本発明は、前記コンピュータプログラム又は前記デジタル信号を、電気通信回線、無線又は有線通信回線、インターネットを代表とするネットワーク、データ放送等を経由して伝送するものとしてもよい。
また、本発明は、マイクロプロセッサとメモリとを備えたコンピュータシステムであって、前記メモリは、上記コンピュータプログラムを記憶しており、前記マイクロプロセッサは、前記コンピュータプログラムに従って動作するとしてもよい。【００９９】
また、前記プログラム又は前記デジタル信号を前記記録媒体に記録して移送することにより、又は前記プログラム又は前記デジタル信号を前記ネットワーク等を経由して移送することにより、独立した他のコンピュータシステムにより実施するとしてもよい。
（１３）上記実施の形態及び上記変形例をそれぞれ組み合わせるとしてもよい。
【産業上の利用可能性】
【０１００】
本発明の情報セキュリティ装置および情報セキュリティ方法は、秘密鍵を用いて公開鍵暗号演算や署名演算を実現する暗号モジュールにおいて、特にＩＣカードやセキュアカードのように解読者側の手に渡って、ＳＰＡなどの攻撃が行われる懸念がある場合に利用される。
本発明を構成する各装置は、秘密のメッセージ伝送や認証を必要とするあらゆる産業において、経営的に、また継続的及び反復的に使用することができる。また、本発明を構成する各装置は、電器機器製造産業において、経営的に、また継続的及び反復的に、製造し、販売することができる。
【図１】
2007046402.tif 000003
【図２】
2007046402.tif 000004
【図３】
2007046402.tif 000005
【図４】
2007046402.tif 000006
【図５】
2007046402.tif 000007
【図６】
2007046402.tif 000008
【手続補正書】
【提出日】平成19年3月30日(2007.3.30)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
所定の法において入力値を整数乗するべき乗剰余演算を行うために、前記整数の各桁毎に乗算を繰り返してべき乗値を算出して、前記入力値の安全又は確実な処理を行う情報セキュリティ装置であって、
前記整数の１個の桁の値が０であるか否かを判断する判断手段と、
取得した桁の値が０であると判断される場合に、値１に対するモンゴメリ変換値を用いる乗算剰余演算を行う乗算手段と
を備え、
さらに、値１に対するモンゴメリ変換値を算出するモンゴメリ変換手段を含み、
前記乗算手段は、前記乗算剰余演算において、前記モンゴメリ変換手段により算出されたモンゴメリ変換値を用い、
さらに、前記法の値を設定する法設定手段と、
前記法の有効ビット数より大きい整数ｋをランダムに選択する整数設定手段とを備え、
前記モンゴメリ変換手段は、設定された前記法の値に基づいて、前記整数ｋを用いて、前記モンゴメリ変換値を算出する
ことを特徴とする情報セキュリティ装置。
【請求項２】
（削除）
【請求項３】
（削除）
【請求項４】
（削除）
【請求項５】
（削除）
【請求項６】
（削除）
【請求項７】
前記モンゴメリ変換手段は、前記モンゴメリ変換値として、前記法において値２のｋ乗値を算出する
ことを特徴とする請求項１に記載の情報セキュリティ装置。
【請求項８】
前記モンゴメリ変換手段は、前記モンゴメリ変換値として、前記法としての値の乱数倍の法において、値２のｋ乗値を算出する
ことを特徴とする請求項１に記載の情報セキュリティ装置。
【請求項９】
前記情報セキュリティ装置は、さらに、
前記法設定手段は、さらに、前記法としての値の乱数倍の法を設定し、
前記モンゴメリ変換手段は、法設定手段によりさらに設定された前記法において、値２のｋ乗値を算出する
ことを特徴とする請求項８に記載の情報セキュリティ装置。
【請求項１０】
前記整数設定手段は、入力値を取得する毎に、前記整数ｋの値をランダムに変更する
ことを特徴とする請求項１に記載の情報セキュリティ装置。
【請求項１１】
前記法設定手段は、入力値を取得する毎に、前記モンゴメリ変換手段において用いられる前記法の値をランダムに変更する
ことを特徴とする請求項１に記載の情報セキュリティ装置。
【請求項１２】
前記整数設定手段は、前記繰返しの途中に、前記整数ｋの値をランダムに変更する
ことを特徴とする請求項１に記載の情報セキュリティ装置。
【請求項１３】
前記法設定手段は、前記繰返しの途中に、前記モンゴメリ変換手段において用いられる前記法の値をランダムに変更する
ことを特徴とする請求項１に記載の情報セキュリティ装置。
【請求項１４】
前記整数設定手段は、外部からの指示により、前記整数ｋの値をランダムに変更する
ことを特徴とする請求項１に記載の情報セキュリティ装置。
【請求項１５】
前記法設定手段は、外部からの指示により、前記モンゴメリ変換手段において用いられる前記法の値をランダムに変更する
ことを特徴とする請求項１に記載の情報セキュリティ装置。
【請求項１６】
前記情報セキュリティ装置は、さらに、
前記入力値に対するモンゴメリ変換値を算出するモンゴメリ変換手段を含み、
前記乗算手段は、取得した桁の値が０以外であると判断される場合に、前記モンゴメリ変換手段により算出された前記モンゴメリ変換値を用いて乗算剰余演算を行い、
さらに、
前記法の値を設定する法設定手段と、
前記法の有効ビット数より大きい整数ｋをランダムに選択する整数設定手段とを備え、
前記モンゴメリ変換手段は、設定された前記法の値に基づいて、前記整数ｋを用いて、前記モンゴメリ変換値を算出する
ことを特徴とする請求項１に記載の情報セキュリティ装置。
【請求項１７】
（削除）
【請求項１８】
前記モンゴメリ変換手段は、前記法において、値２のｋ乗値を算出し、前記入力値と算出された値とを乗じて得られた値を前記モンゴメリ変換値とする
ことを特徴とする請求項１６に記載の情報セキュリティ装置。
【請求項１９】
前記モンゴメリ変換手段は、前記モンゴメリ変換値として、前記法としての値の乱数倍の法において、値２のｋ乗値を算出する
ことを特徴とする請求項１６に記載の情報セキュリティ装置。
【請求項２０】
所定の法において入力値を整数乗するべき乗剰余演算を行うために、前記整数の各桁毎に乗算を繰り返してべき乗値を算出して、前記入力値の安全又は確実な処理を行う情報セキュリティ装置において用いられる情報セキュリティ方法であって、
前記整数の１個の桁の値が０であるか否かを判断する判断ステップと、
取得した桁の値が０であると判断される場合に、値１に対するモンゴメリ変換値を用いる乗算剰余演算を行う乗算ステップと
を含み、
さらに、値１に対するモンゴメリ変換値を算出するモンゴメリ変換ステップを含み、
前記乗算ステップは、前記乗算剰余演算において、前記モンゴメリ変換ステップにより算出されたモンゴメリ変換値を用い、
さらに、前記法の値を設定する法設定ステップと、
前記法の有効ビット数より大きい整数ｋをランダムに選択する整数設定ステップとを含み、
前記モンゴメリ変換ステップは、設定された前記法の値に基づいて、前記整数ｋを用いて、前記モンゴメリ変換値を算出する
ことを特徴とする情報セキュリティ方法。
【請求項２１】
所定の法において入力値を整数乗するべき乗剰余演算を行うために、前記整数の各桁毎に乗算を繰り返してべき乗値を算出して、前記入力値の安全又は確実な処理を行う情報セキュリティ装置において用いられる情報セキュリティのためのコンピュータプログラムであって、
前記整数の１個の桁の値が０であるか否かを判断する判断ステップと、
取得した桁の値が０であると判断される場合に、値１に対するモンゴメリ変換値を用いる乗算剰余演算を行う乗算ステップと
を含み、
さらに、値１に対するモンゴメリ変換値を算出するモンゴメリ変換ステップを含み、
前記乗算ステップは、前記乗算剰余演算において、前記モンゴメリ変換ステップにより算出されたモンゴメリ変換値を用い、
さらに、前記法の値を設定する法設定ステップと、
前記法の有効ビット数より大きい整数ｋをランダムに選択する整数設定ステップとを含み、
前記モンゴメリ変換ステップは、設定された前記法の値に基づいて、前記整数ｋを用いて、前記モンゴメリ変換値を算出する
ことを特徴とするコンピュータプログラム。
【請求項２２】
所定の法において入力値を整数乗するべき乗剰余演算を行うために、前記整数の各桁毎に乗算を繰り返してべき乗値を算出して、前記入力値の安全又は確実な処理を行う情報セキュリティ装置において用いられる情報セキュリティのためのコンピュータプログラムを記録しているコンピュータ読み取り可能な記録媒体であって、
前記コンピュータプログラムは、
前記整数の１個の桁の値が０であるか否かを判断する判断ステップと、
取得した桁の値が０であると判断される場合に、値１に対するモンゴメリ変換値を用いる乗算剰余演算を行う乗算ステップと
を含み、
さらに、値１に対するモンゴメリ変換値を算出するモンゴメリ変換ステップを含み、
前記乗算ステップは、前記乗算剰余演算において、前記モンゴメリ変換ステップにより算出されたモンゴメリ変換値を用い、
さらに、前記法の値を設定する法設定ステップと、
前記法の有効ビット数より大きい整数ｋをランダムに選択する整数設定ステップとを含み、
前記モンゴメリ変換ステップは、設定された前記法の値に基づいて、前記整数ｋを用いて、前記モンゴメリ変換値を算出する
ことを特徴とする記録媒体。
【請求項２３】
所定の法において入力値を整数乗するべき乗剰余演算を行うために、前記整数の各桁毎に乗算を繰り返してべき乗値を算出して、前記入力値の安全又は確実な処理を行う集積回路であって、
前記整数の１個の桁の値が０であるか否かを判断する判断手段と、
取得した桁の値が０であると判断される場合に、値１に対するモンゴメリ変換値を用いる乗算剰余演算を行う乗算手段と
を備え、
さらに、値１に対するモンゴメリ変換値を算出するモンゴメリ変換手段を含み、
前記乗算手段は、前記乗算剰余演算において、前記モンゴメリ変換手段により算出されたモンゴメリ変換値を用い、
さらに、前記法の値を設定する法設定手段と、
前記法の有効ビット数より大きい整数ｋをランダムに選択する整数設定手段とを備え、
前記モンゴメリ変換手段は、設定された前記法の値に基づいて、前記整数ｋを用いて、前記モンゴメリ変換値を算出する
ことを特徴とする集積回路。
【手続補正書】
【提出日】平成20年3月24日(2008.3.24)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
所定の法において入力値を整数乗するべき乗剰余演算を行うために、前記整数の各桁毎に乗算を繰り返してべき乗値を算出して、前記入力値の安全又は確実な処理を行う情報セキュリティ装置であって、
前記整数の１個の桁の値が０であるか否かを判断する判断手段と、
取得した桁の値が０であると判断される場合に、値１に対するモンゴメリ変換値を用いる乗算剰余演算を行う乗算手段と
を備え、
さらに、値１に対するモンゴメリ変換値を算出するモンゴメリ変換手段を含み、
前記乗算手段は、前記乗算剰余演算において、前記モンゴメリ変換手段により算出されたモンゴメリ変換値を用い、
さらに、前記法の値を設定する法設定手段と、
前記法の有効ビット数より大きい整数ｋをランダムに選択する整数設定手段とを備え、
前記モンゴメリ変換手段は、設定された前記法の値に基づいて、前記整数ｋを用いて、前記モンゴメリ変換値を算出する
ことを特徴とする情報セキュリティ装置。
【請求項２】
前記モンゴメリ変換手段は、前記モンゴメリ変換値として、前記法において値２のｋ乗値を算出する
ことを特徴とする請求項１に記載の情報セキュリティ装置。
【請求項３】
前記モンゴメリ変換手段は、前記モンゴメリ変換値として、前記法としての値の乱数倍の法において、値２のｋ乗値を算出する
ことを特徴とする請求項１に記載の情報セキュリティ装置。
【請求項４】
前記情報セキュリティ装置は、さらに、
前記法設定手段は、さらに、前記法としての値の乱数倍の法を設定し、
前記モンゴメリ変換手段は、法設定手段によりさらに設定された前記法において、値２のｋ乗値を算出する
ことを特徴とする請求項３に記載の情報セキュリティ装置。
【請求項５】
前記整数設定手段は、入力値を取得する毎に、前記整数ｋの値をランダムに変更する
ことを特徴とする請求項１に記載の情報セキュリティ装置。
【請求項６】
前記法設定手段は、入力値を取得する毎に、前記モンゴメリ変換手段において用いられる前記法の値をランダムに変更する
ことを特徴とする請求項１に記載の情報セキュリティ装置。
【請求項７】
前記整数設定手段は、前記繰返しの途中に、前記整数ｋの値をランダムに変更する
ことを特徴とする請求項１に記載の情報セキュリティ装置。
【請求項８】
前記法設定手段は、前記繰返しの途中に、前記モンゴメリ変換手段において用いられる前記法の値をランダムに変更する
ことを特徴とする請求項１に記載の情報セキュリティ装置。
【請求項９】
前記整数設定手段は、外部からの指示により、前記整数ｋの値をランダムに変更する
ことを特徴とする請求項１に記載の情報セキュリティ装置。
【請求項１０】
前記法設定手段は、外部からの指示により、前記モンゴメリ変換手段において用いられる前記法の値をランダムに変更する
ことを特徴とする請求項１に記載の情報セキュリティ装置。
【請求項１１】
前記情報セキュリティ装置は、さらに、
前記入力値に対するモンゴメリ変換値を算出するモンゴメリ変換手段を含み、
前記乗算手段は、取得した桁の値が０以外であると判断される場合に、前記モンゴメリ変換手段により算出された前記モンゴメリ変換値を用いて乗算剰余演算を行い、
さらに、
前記法の値を設定する法設定手段と、
前記法の有効ビット数より大きい整数ｋをランダムに選択する整数設定手段とを備え、
前記モンゴメリ変換手段は、設定された前記法の値に基づいて、前記整数ｋを用いて、前記モンゴメリ変換値を算出する
ことを特徴とする請求項１に記載の情報セキュリティ装置。
【請求項１２】
前記モンゴメリ変換手段は、前記法において、値２のｋ乗値を算出し、前記入力値と算出された値とを乗じて得られた値を前記モンゴメリ変換値とする
ことを特徴とする請求項１１に記載の情報セキュリティ装置。
【請求項１３】
前記モンゴメリ変換手段は、前記モンゴメリ変換値として、前記法としての値の乱数倍の法において、値２のｋ乗値を算出する
ことを特徴とする請求項１１に記載の情報セキュリティ装置。
【請求項１４】
所定の法において入力値を整数乗するべき乗剰余演算を行うために、前記整数の各桁毎に乗算を繰り返してべき乗値を算出して、前記入力値の安全又は確実な処理を行う情報セキュリティ装置において用いられる情報セキュリティ方法であって、
前記整数の１個の桁の値が０であるか否かを判断する判断ステップと、
取得した桁の値が０であると判断される場合に、値１に対するモンゴメリ変換値を用いる乗算剰余演算を行う乗算ステップと
を含み、
さらに、値１に対するモンゴメリ変換値を算出するモンゴメリ変換ステップを含み、
前記乗算ステップは、前記乗算剰余演算において、前記モンゴメリ変換ステップにより算出されたモンゴメリ変換値を用い、
さらに、前記法の値を設定する法設定ステップと、
前記法の有効ビット数より大きい整数ｋをランダムに選択する整数設定ステップとを含み、
前記モンゴメリ変換ステップは、設定された前記法の値に基づいて、前記整数ｋを用いて、前記モンゴメリ変換値を算出する
ことを特徴とする情報セキュリティ方法。
【請求項１５】
所定の法において入力値を整数乗するべき乗剰余演算を行うために、前記整数の各桁毎に乗算を繰り返してべき乗値を算出して、前記入力値の安全又は確実な処理を行う情報セキュリティ装置において用いられる情報セキュリティのためのコンピュータプログラムであって、
前記整数の１個の桁の値が０であるか否かを判断する判断ステップと、
取得した桁の値が０であると判断される場合に、値１に対するモンゴメリ変換値を用いる乗算剰余演算を行う乗算ステップと
を含み、
さらに、値１に対するモンゴメリ変換値を算出するモンゴメリ変換ステップを含み、
前記乗算ステップは、前記乗算剰余演算において、前記モンゴメリ変換ステップにより算出されたモンゴメリ変換値を用い、
さらに、前記法の値を設定する法設定ステップと、
前記法の有効ビット数より大きい整数ｋをランダムに選択する整数設定ステップとを含み、
前記モンゴメリ変換ステップは、設定された前記法の値に基づいて、前記整数ｋを用いて、前記モンゴメリ変換値を算出する
ことを特徴とするコンピュータプログラム。
【請求項１６】
所定の法において入力値を整数乗するべき乗剰余演算を行うために、前記整数の各桁毎に乗算を繰り返してべき乗値を算出して、前記入力値の安全又は確実な処理を行う情報セキュリティ装置において用いられる情報セキュリティのためのコンピュータプログラムを記録しているコンピュータ読み取り可能な記録媒体であって、
前記コンピュータプログラムは、
前記整数の１個の桁の値が０であるか否かを判断する判断ステップと、
取得した桁の値が０であると判断される場合に、値１に対するモンゴメリ変換値を用いる乗算剰余演算を行う乗算ステップと
を含み、
さらに、値１に対するモンゴメリ変換値を算出するモンゴメリ変換ステップを含み、
前記乗算ステップは、前記乗算剰余演算において、前記モンゴメリ変換ステップにより算出されたモンゴメリ変換値を用い、
さらに、前記法の値を設定する法設定ステップと、
前記法の有効ビット数より大きい整数ｋをランダムに選択する整数設定ステップとを含み、
前記モンゴメリ変換ステップは、設定された前記法の値に基づいて、前記整数ｋを用いて、前記モンゴメリ変換値を算出する
ことを特徴とする記録媒体。
【請求項１７】
所定の法において入力値を整数乗するべき乗剰余演算を行うために、前記整数の各桁毎に乗算を繰り返してべき乗値を算出して、前記入力値の安全又は確実な処理を行う集積回路であって、
前記整数の１個の桁の値が０であるか否かを判断する判断手段と、
取得した桁の値が０であると判断される場合に、値１に対するモンゴメリ変換値を用いる乗算剰余演算を行う乗算手段と
を備え、
さらに、値１に対するモンゴメリ変換値を算出するモンゴメリ変換手段を含み、
前記乗算手段は、前記乗算剰余演算において、前記モンゴメリ変換手段により算出されたモンゴメリ変換値を用い、
さらに、前記法の値を設定する法設定手段と、
前記法の有効ビット数より大きい整数ｋをランダムに選択する整数設定手段とを備え、
前記モンゴメリ変換手段は、設定された前記法の値に基づいて、前記整数ｋを用いて、前記モンゴメリ変換値を算出する
ことを特徴とする集積回路。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、秘密鍵を用いた公開鍵暗号処理や署名処理を行う情報セキュリティ装置における耐タンパー技術に関する。
【背景技術】
【０００２】
近年、情報通信技術の普及に伴い、情報セキュリティ技術の重要性が一段と増してきている。このような情報セキュリティ技術の一つとして、暗号技術がプライバシーの保護や通信相手の確認のために用いられる。
【０００３】
しかしながら、暗号技術により何かを守ろうとすると、暗号化を打ち破ってそれを入手しようとする者が現れる。例えば、秘密鍵の値により、暗号処理時の計算時間や消費電力などが異なることを利用して、秘密鍵を求めるサイドチャネル攻撃が問題となっている（例えば、非特許文献１）。
【０００４】
その中でも代表的なものとして、ＲＳＡ暗号方式、より正確には、秘密鍵を用いたＲＳＡ署名の署名処理や、ＲＳＡ暗号の復号処理に対する単純電力攻撃（ＳＰＡ、SimplePower Analysis）がある。ＲＳＡ暗号方式における主要な処理は、秘密鍵をべきとするべき乗演算であり、べき乗演算は、２乗算と乗算の繰り返しで実現される。この場合、対応する秘密鍵のビットが「０」のとき乗算が行われず、「１」のときだけ乗算が行われるので、ＳＰＡでは、消費電力の波形判断により得た乗算及び２乗算のシーケンス情報から秘密鍵を求める。
【０００５】
このＳＰＡに対抗するためには、秘密鍵の当該ビットが「０」の場合も乗算を行えばよい。以下、２つの具体的な従来方法について説明する。
その第１の方法では、秘密鍵の当該ビットが「０」のときには、「１」と乗算する（例えば、非特許文献２）。「１」と乗算しても結果は変わらないため、実質的に乗算を実施していないのと同じである。その上、秘密鍵のビット値に依存せずに乗算が行われるので、乗算の有無により、秘密鍵を求めることはできない。
【０００６】
また、ＳＰＡに対抗する第２の方法では、ビットが「０」であろうと「１」であろうと、まず乗算を行って、ビットが「１」の場合のみ乗算結果を使い、「０」の場合は乗算結果を使わないように制御する（例えば、特許文献１、特許文献２）。この方法も、ビット値に依存せずに乗算を行うため、乗算の有無により、秘密鍵を求めることはできない。
【非特許文献１】現実の脅威「サイドチャネル解析」（１）、日経エレクトロニクス２００５．７．１８号
【非特許文献２】“ＲＳＡ暗号の電力解析法による攻撃とその対策”（Power Analysis and Countermeasure of RSACryptosystem)、電子情報通信学会論文誌Ａ  Ｖｏｌ．Ｊ８８−Ａ、  Ｎｏ．５  ２００５
【非特許文献３】P.L.Montgomery, “Modular Multiplicationwithout Trial Division," Mathematics ofComputation,Vol.44,No.170,pp.519-521 (1985)
【特許文献１】特開２０００−１６５３７５号公報
【特許文献２】米国特許第６４０８０７５号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかしながら、ＳＰＡに対抗する前記第１の方法については、乗算への入力の一方が、ハミング重みに偏りがある「１」であるため、これが電力変化に影響して「１」との乗算を区別でき、不正に解析される可能性がある。
【０００８】
また、第２の方法については、乗算のときを狙って、例えば、電源電圧にスパイクノイズを与える等の、故意にエラーを生じさせるエラー攻撃により、秘密鍵が解析される可能性がある。詳細には、乗算の際にエラーを起こし、その影響が出力に表れないと、結果を使っていない、つまり対応する秘密鍵のビットが「０」であったと解析できる。反対に、エラーの影響が出力に表れると、秘密鍵の対応するビットが「１」であったと解析できる。この解析は、エラー攻撃に対する通常の対策である検算機能を入れていたとしても、可能である。
【０００９】
そこで、本発明では、第１の方法を用いる場合において、上記課題を解決し、ＳＰＡに対抗することができる情報セキュリティ装置、情報セキュリティ方法、コンピュータプログラム、記録媒体及び集積回路を提供することを目的とする。なお、本発明では、第１の方法をベースにしているので、前記第２の方法による攻撃は、意味がなくなる。
【課題を解決するための手段】
【００１０】
上記目的を達成するために、本発明は、所定の法において入力値を整数乗するべき乗剰余演算を行うために、前記整数の各桁毎に乗算を繰り返してべき乗値を算出して、前記入力値の安全又は確実な処理を行う情報セキュリティ装置であって、前記整数の１個の桁の値が０であるか否かを判断する判断手段と、取得した桁の値が０であると判断される場合に、値１に対するモンゴメリ変換値を用いる乗算剰余演算を行う乗算手段とを備えることを特徴とする。
【発明の効果】
【００１１】
この構成によると、「１」に対するモンゴメリ変換値との乗算剰余演算を用いるので、ハミング重みに偏りがある「１」の使用を避けることができ、ＳＰＡに対抗して、不正な解析を困難にすることができる。
【００１２】
ここで、前記情報セキュリティ装置は、ＲＳＡ方式に基づいてＲＳＡ暗号文を復号するＲＳＡ復号装置、又はＲＳＡ方式に基づいて署名対象のメッセージに対して署名データの生成を行うＲＳＡ署名装置であり、さらに、前記入力値としてＲＳＡ暗号文を取得し、又は前記入力値として署名対象のメッセージを取得する取得手段と、秘密鍵として前記整数を記憶している記憶手段と、前記ＲＳＡ暗号文から復号して得られる復号文として、又は前記メッセージに対する署名データとして、算出された前記べき乗値を出力する出力手段とを含むとしてもよい。
【００１３】
この構成によると、ＲＳＡ方式に基づいてＲＳＡ暗号文を復号するＲＳＡ復号において、また、ＲＳＡ方式に基づいて署名対象のメッセージに対して署名データの生成を行うＲＳＡ署名において、ハミング重みに偏りがある「１」の使用を避けることができ、ＳＰＡによる不正な解析を困難にすることができる。
【００１４】
ここで、前記情報セキュリティ装置は、入力値を取得する取得手段と、整数を記憶している記憶手段と、演算結果の値を格納する演算値変数に初期値を格納する初期化手段と、前記記憶手段から前記整数の上位桁から１個の桁の値を抽出する抽出手段と、前記演算値変数に格納されている値の少なくとも１回の二乗剰余演算に基づいて得られた値を前記演算値変数に上書きする二乗手段と、取得した桁の値が０であるか否かを判断する前記判断手段と、取得した桁の値が０であると判断される場合に、前記演算値変数に格納されている値と値１に対するモンゴメリ変換値との乗算剰余演算に基づいて得られた値を前記演算値変数に上書きし、０以外であると判断される場合に、前記演算値変数に格納されている値と前記入力値から定まる値との乗算剰余演算に基づいて得られた値を前記演算値変数に上書きする前記乗算手段と、前記整数の全ての桁について、前記抽出手段、前記二乗手段、前記判断手段及び前記乗算手段に対して、値の取得と、二乗剰余演算と、判断と、乗算剰余演算とを繰り返すように制御する繰返制御手段と、前記整数の全ての桁について前記繰返しが終了すると、前記演算値変数に格納されている値に基づく値を出力する出力手段とを備えるとしてもよい。
【００１５】
また、前記情報セキュリティ装置は、入力値を取得して入力値変数に格納する取得手段と、整数を記憶している記憶手段と、演算結果の値を格納する演算値変数に初期値を格納する初期化手段と、前記記憶手段から前記整数の下位桁から１個の桁の値を抽出する抽出手段と、前記入力値変数に格納されている値の少なくとも１回の二乗剰余演算に基づいて得られた値を前記入力値変数に上書きする二乗手段と、取得した桁の値が０であるか否かを判断する前記判断手段と、取得した桁の値が０であると判断される場合に、前記演算値変数に格納されている値と値１に対するモンゴメリ変換値との乗算剰余演算に基づいて得られた値を前記演算値変数に上書きし、０以外であると判断される場合に、前記演算値変数に格納されている値と前記入力値変数から定まる値との乗算剰余演算に基づいて得られた値を前記演算値変数に上書きする前記乗算手段と、前記整数の全ての桁について、前記抽出手段、前記二乗手段、前記判断手段及び前記乗算手段に対して、値の取得と、二乗剰余演算と、判断と、乗算剰余演算とを繰り返すように制御する繰返制御手段と、前記整数の全ての桁について前記繰返しが終了すると、前記演算値変数に格納されている値に基づく値を出力する出力手段とを備えるとしてもよい。
【００１６】
情報セキュリティ装置は、実施の形態のＩＣカード１００に相当し、取得手段は、入出力部１０２に相当し、記憶手段は、秘密鍵格納部１１３に相当し、初期化手段は、図４のステップＳ１０２に相当し、抽出手段は、抽出部１２２に相当し、二乗手段は、二乗算部１１５に相当し、判断手段は、図４のステップＳ１０６に相当し、乗算手段は、乗算部１１６に相当し、繰返制御手段は、制御部１１４に相当し、出力手段は、モンゴメリ逆変換部１２０及び入出力部１０２に相当する。
【００１７】
これらの構成によると、前記整数の上位の桁から又は下位の桁からの演算を行うことができる。
ここで、前記情報セキュリティ装置は、さらに、値１に対するモンゴメリ変換値を算出するモンゴメリ変換手段を含み、前記乗算手段は、前記乗算剰余演算において、前記モンゴメリ変換手段により算出されたモンゴメリ変換値を用いるとしてもよい。
【００１８】
モンゴメリ変換手段は、第２のモンゴメリ変換部１１２に相当する。
この構成によると、モンゴメリ変換手段により値１に対するモンゴメリ変換値を算出し、乗算手段は、算出されたモンゴメリ変換値を用いるので、値１に対するモンゴメリ変換値の算出を複数回行うことなく、演算回数を削減することができる。
【００１９】
ここで、前記情報セキュリティ装置は、さらに、前記法の値を設定する法設定手段と、前記法の有効ビット数より大きい整数ｋをランダムに選択する整数設定手段とを備え、前記モンゴメリ変換手段は、設定された前記法の値に基づいて、前記整数ｋを用いて、前記モンゴメリ変換値を算出するとしてもよい。
【００２０】
法設定手段は、法設定部１１７に相当し、整数設定手段は、整数設定部１１８に相当する。
この構成によると、前記法の有効ビット数より大きく、ランダムに選択された整数ｋをモンゴメリ変換値の算出において用いるので、「１」についてのハミング重みの偏りをさらに避けることができる。
【００２１】
ここで、前記モンゴメリ変換手段は、前記モンゴメリ変換値として、前記法において値２のｋ乗値を算出するとしてもよい。
この構成によると、確実にモンゴメリ変換値を算出することができる。
【００２２】
ここで、前記モンゴメリ変換手段は、前記モンゴメリ変換値として、前記法としての値の乱数倍の法において、値２のｋ乗値を算出するとしてもよい。
この構成によると、「１」についてのハミング重みの偏りをさらに避けることができるモンゴメリ変換値を算出することができる。
【００２３】
ここで、前記情報セキュリティ装置は、さらに、前記法設定手段は、さらに、前記法としての値の乱数倍の法を設定し、前記モンゴメリ変換手段は、法設定手段によりさらに設定された前記法において、値２のｋ乗値を算出するとしてもよい。
【００２４】
この構成によると、「１」についてのハミング重みの偏りをさらに避けることができるモンゴメリ変換値を算出することができる。
ここで、前記整数設定手段は、入力値を取得する毎に、前記整数ｋの値をランダムに変更するとしてもよい。
【００２５】
この構成によると、最初の入力値を用いたＳＰＡの結果を、別の入力値において使用することを困難とすることができる。
ここで、前記法設定手段は、入力値を取得する毎に、前記モンゴメリ変換手段において用いられる前記法の値をランダムに変更するとしてもよい。
【００２６】
この構成によると、最初の入力値を用いたＳＰＡの結果を、別の入力値において使用することを困難とすることができる。
ここで、前記整数設定手段は、前記繰返しの途中に、前記整数ｋの値をランダムに変更するとしてもよい。
【００２７】
この構成によると、繰返しの途中のプロセスにおけるＳＰＡの結果を、繰返しの別のプロセスにおいて使用することを困難とすることができる。
ここで、前記法設定手段は、前記繰返しの途中に、前記モンゴメリ変換手段において用いられる前記法の値をランダムに変更するとしてもよい。
【００２８】
この構成によると、繰返しの途中のプロセスにおけるＳＰＡの結果を、繰返しの別のプロセスにおいて使用することを困難とすることができる。
ここで、前記整数設定手段は、外部からの指示により、前記整数ｋの値をランダムに変更するとしてもよい。
【００２９】
この構成によると、外部からの指示の前におけるＳＰＡの結果を、外部からの指示の後において使用することを困難とすることができる。
ここで、前記法設定手段は、外部からの指示により、前記モンゴメリ変換手段において用いられる前記法の値をランダムに変更するとしてもよい。
【００３０】
この構成によると、外部からの指示の前におけるＳＰＡの結果を、外部からの指示の後において使用することを困難とすることができる。
ここで、前記情報セキュリティ装置は、さらに、前記入力値に対するモンゴメリ変換値を算出するモンゴメリ変換手段を含み、前記乗算手段は、取得した桁の値が０以外であると判断される場合に、前記モンゴメリ変換手段により算出された前記モンゴメリ変換値を用いて乗算剰余演算を行うとしてもよい。
【００３１】
モンゴメリ変換手段は、第１のモンゴメリ変換部１１１に相当する。
この構成によると、取得した桁の値が０以外であると判断される場合においても、ＳＰＡに対抗して、不正な解析を困難にすることができる。
【００３２】
ここで、前記情報セキュリティ装置は、さらに、前記法の値を設定する法設定手段と、前記法の有効ビット数より大きい整数ｋをランダムに選択する整数設定手段とを備え、前記モンゴメリ変換手段は、設定された前記法の値に基づいて、前記整数ｋを用いて、前記モンゴメリ変換値を算出するとしてもよい。
【００３３】
法設定手段は、法設定部１１７に相当し、整数設定手段は、整数設定部１１８に相当する。
この構成によると、前記法の有効ビット数より大きく、ランダムに選択された整数ｋをモンゴメリ変換値の算出において用いるので、入力値についてのハミング重みの偏りをさらに避けることができる。
【００３４】
ここで、前記モンゴメリ変換手段は、前記法において、値２のｋ乗値を算出し、前記入力値と算出された値とを乗じて得られた値を前記モンゴメリ変換値とするとしてもよい。
この構成によると、確実にモンゴメリ変換値を算出することができる。
【００３５】
ここで、前記モンゴメリ変換手段は、前記モンゴメリ変換値として、前記法としての値の乱数倍の法において、値２のｋ乗値を算出するとしてもよい。
この構成によると、入力値についてのハミング重みの偏りをさらに避けることができるモンゴメリ変換値を算出することができる。
【発明を実施するための最良の形態】
【００３６】
本発明に係る１個の実施の形態としてのコンテンツ再生システム１について説明する。
１．コンテンツ再生システム１の構成
コンテンツ再生システム１は、図１に示すように、ＩＣカード１００、ＤＶＤプレーヤ２００及びサーバ装置４００から構成されている。ＤＶＤプレーヤ２００及びサーバ装置４００は、ネットワーク１０を介して相互に接続されている。
【００３７】
ＤＶＤプレーヤ２００には、利用者によりＤＶＤ３００が装着される。ＤＶＤ３００は、図２に示すように、暗号化コンテンツ３０１及び暗号化コンテンツ鍵３０２を記録している。暗号化コンテンツ３０１は、コンテンツ鍵を用いて、映像及び音声からなるコンテンツに、暗号化アルゴリズムＡＥＳ（AdvancedEncryption Standard）を施して生成されたものであり、暗号化コンテンツ鍵３０２は、前記コンテンツの利用の許可を示すライセンス鍵Ｌを用いて、前記コンテンツ鍵に、暗号化アルゴリズムＡＥＳを施して生成されたものである。
【００３８】
サーバ装置４００は、ＤＶＤプレーヤ２００の要求により、ＩＣカード１００の利用者の公開鍵（ｅ、ｐ）を用いて、ライセンス鍵Ｌに、暗号化アルゴリズムＲＳＡを施して、暗号化ライセンス鍵Ｃを生成する。
【００３９】
Ｃ＝Ｌe ｍｏｄ  ｐ
なお、ＲＳＡの公開鍵の生成については、周知であるので、説明を省略する。
次に、サーバ装置４００は、生成した暗号化ライセンス鍵Ｃを、ＤＶＤプレーヤ２００の要求により、ネットワーク１０を介して、ＤＶＤプレーヤ２００へ送信する。
【００４０】
ＤＶＤプレーヤ２００は、図２に示すように、通信部２１１、入出力部２１２、復号部２１３、復号部２１４、再生部２１５及びドライブ部２１６から構成されており、モニタ２０１及びスピーカ２０２がＤＶＤプレーヤ２００に接続されている。
【００４１】
ＤＶＤプレーヤ２００の通信部２１１は、サーバ装置４００からネットワーク１０を介して、暗号化ライセンス鍵Ｃを受信する。ＤＶＤプレーヤ２００には、利用者によりＩＣカード１００が装着される。ＤＶＤプレーヤ２００の入出力部２１２は、受信した暗号化ライセンス鍵ＣをＩＣカード１００へ出力する。
【００４２】
ＩＣカード１００は、公開鍵復号部１０１及び入出力部１０２から構成されている。ＩＣカード１００の入出力部１０２は、ＤＶＤプレーヤ２００から暗号化ライセンス鍵Ｃを受け取り、公開鍵復号部１０１は、入力データとして受け取った暗号化ライセンス鍵Ｃを、後述するようにして復号して、出力データとして復号ライセンス鍵を生成し、入出力部１０２は、生成した復号ライセンス鍵をＤＶＤプレーヤ２００へ出力する。
【００４３】
ＤＶＤプレーヤ２００の入出力部２１２は、ＩＣカード１００から復号ライセンス鍵を受け取り、ドライブ部２１６は、ＤＶＤ３００から暗号化コンテンツ３０１及び暗号化コンテンツ鍵３０２を読み出し、復号部２１３は、受け取った復号ライセンス鍵を用いて、暗号化コンテンツ鍵３０２を復号して復号コンテンツ鍵を生成し、復号部２１４は、生成した復号コンテンツ鍵を用いて、暗号化コンテンツ３０１を復号して復号コンテンツを生成し、再生部２１５は、復号コンテンツを再生して映像信号及び音声信号を生成し、生成した映像信号をモニタ２０１へ出力し、生成した音声信号をスピーカ２０２へ出力する。
【００４４】
ここで、ＩＣカード１００及びＤＶＤプレーヤ２００は、それぞれ、具体的には、マイクロプロセッサ、ＲＯＭ、ＲＡＭなどから構成されるコンピュータシステムである。前記ＲＡＭには、コンピュータプログラムが記憶されている。前記マイクロプロセッサが、前記コンピュータプログラムに従って動作することにより、各装置は、その機能を達成する。
【００４５】
なお、図２において、ＤＶＤプレーヤ２００の各構成部を示す各ブロックは、接続線により他のブロックと接続されている。ただし、一部の接続線を省略している。ここで、各接続線は、信号や情報が伝達される経路を示している。また、復号部２１３を示すブロックに接続している複数の接続線のうち、接続線上に鍵マークが描かれているものは、復号部２１３へ鍵としての情報が伝達される経路を示している。復号部２１４を示すブロックについても同様である。
【００４６】
ここで、ＩＣカード１００は、所定の法において入力値を整数乗するべき乗剰余演算により、入力値の安全な処理を行う情報セキュリティ装置である。
２．公開鍵復号部１０１の構成
公開鍵復号部１０１は、図３に示すように、記憶部１２１、第１モンゴメリ変換部１１１、第２モンゴメリ変換部１１２、秘密鍵格納部１１３、制御部１１４、二乗算部１１５、乗算部１１６、法設定部１１７、整数設定部１１８、設定制御部１１９及びモンゴメリ逆変換部１２０から構成されている。
【００４７】
公開鍵復号部１０１は、秘密鍵Ｓと法ｐを内部に記憶しており、入力データＣを入力として公開鍵暗号の計算を行い、計算結果の出力データＭ＝Ｃs  ｍｏｄ  ｐを出力する。ここで、出力データＭは、秘密鍵Ｓをべきとし、ｐを法とする入力データＣのべき乗剰余演算値である。ｍｏｄ  ｐは、ｐで除したときの剰余を求めることを示す。なお、本実施の形態において、前記公開鍵暗号の計算はＲＳＡ暗号の復号処理である。従って、入力データは暗号文Ｃ、出力データは復号文Ｍに相当する。具体的には、入力データは、上述した暗号化ライセンス鍵であり、出力データは、上述した復号ライセンス鍵である。
【００４８】
公開鍵復号部１０１は、前述した秘密鍵Ｓの各ビットの上位から１ビットずつについて、設定された法におけるモンゴメリ領域での２乗算と乗算とを繰り返す高速べき指数演算を行う。公開鍵復号部１０１の全体の動作については後述する。
【００４９】
（１）  法設定部１１７、整数設定部１１８及び設定制御部１１９
法設定部１１７は、設定制御部１１９の制御により、モンゴメリ変換、２乗算、乗算で用いる法ｐを設定する。法設定部１１７は、設定した法ｐを第１モンゴメリ変換部１１１、第２モンゴメリ変換部１１２、二乗算部１１５、乗算部１１６及びモンゴメリ逆変換部１２０へ出力する。
【００５０】
整数設定部１１８は、設定制御部１１９の制御により、ｐのビット数よりも大きい整数ｋを、ランダムに設定する。なお、ここでｐの「ビット数」とは、ｐのうち、値「１」がセットされている最上位のビット位置から最下位のビット位置までのビット長であり、いわゆる「有効ビット数」のことを意味する。整数設定部１１８は、整数ｋを第１モンゴメリ変換部１１１、第２モンゴメリ変換部１１２、二乗算部１１５、乗算部１１６及びモンゴメリ逆変換部１２０へ出力する。
【００５１】
設定制御部１１９は、整数設定部１１８に対して、整数ｋの設定範囲や設定変更のタイミングを制御する。設定変更のタイミングの一例として、設定制御部１１９は、入力データＣの値が変わるごとに変更してもよいし、入力データＣの演算途中で変更してもよい。
【００５２】
ここで設定された整数ｋと法ｐとは、以降の、モンゴメリ変換、二乗算、乗算及びモンゴメリ逆変換で用いられる。
（２）記憶部１２１、第１モンゴメリ変換部１１１及び第２モンゴメリ変換部１１２
記憶部１２１は、入出力部１０２から入力データＣを受け取り、受け取った入力データＣを記憶する。
【００５３】
第１モンゴメリ変換部１１１は、記憶部１２１から入力データＣを読み出し、法設定部１１７から法ｐを受け取り、整数設定部１１８から整数ｋを受け取る。次に、入力データＣ、法ｐ及び整数ｋを用いて、次式により、Ｃのモンゴメリ変換値Ｂを算出する。
【００５４】
モンゴメリ変換値Ｂ＝Ｃ×（２k ）ｍｏｄ  ｐ
次に、第１モンゴメリ変換部１１１は、算出したモンゴメリ変換値Ｂを制御部１１４へ出力する。
【００５５】
また、第２モンゴメリ変換部１１２は、法設定部１１７から法ｐを受け取り、整数設定部１１８から整数ｋを受け取る。次に、法ｐ及び整数ｋを用いて、次式により、「１」のモンゴメリ変換値Ａを算出する。
【００５６】
モンゴメリ変換値Ａ＝（２k ）ｍｏｄ  ｐ
次に、第２モンゴメリ変換部１１２は、算出したモンゴメリ変換値Ａを制御部１１４へ出力する。
【００５７】
なお、以降ではモンゴメリ変換をＭｏｎ＿｛ｋ，ｐ｝（Ｘ）と表記する。
Ｍｏｎ＿｛ｋ，ｐ｝（Ｘ）  ＝  Ｘ×２k   ｍｏｄ  ｐ    （式１）
なお、変換関数の｛ｋ，ｐ｝は、モンゴメリ変換値が、整数ｋ、法ｐに依存することを示す。この表記を用いると、第１モンゴメリ変換部１１１により出力されるモンゴメリ変換値Ｂは、Ｍｏｎ＿｛ｋ，ｐ｝（Ｃ）であり、第２モンゴメリ変換部１１２により出力されるモンゴメリ変換値Ａは、Ｍｏｎ＿｛ｋ，ｐ｝（１）である。
【００５８】
（３）秘密鍵格納部１１３
秘密鍵格納部１１３は、公開鍵暗号の秘密鍵Ｓを格納している。秘密鍵Ｓは、安全性確保のため少なくとも２０４８ビット以上は必要とされている。
【００５９】
（４）抽出部１２２、制御部１１４、二乗算部１１５及び乗算部１１６
抽出部１２２は、制御部１１４の指示により、秘密鍵格納部１１３に格納されている秘密鍵Ｓの各ビットの上位から１ビットずつ抽出し、抽出したビットの値を制御部１１４へ出力する。
【００６０】
制御部１１４は、秘密鍵Ｓの上位から１ビットについて、２乗算と乗算の処理を繰り返す。例えば、秘密鍵が２０４８ビットの場合は２０４８回、２乗算と乗算の処理を繰り返す。繰り返しが終了したら、モンゴメリ逆変換部１２０は、その演算結果をモンゴメリ逆変換し、公開鍵復号部１０１は、Ｍ＝ＣSｍｏｄ  ｐを出力する。
【００６１】
制御部１１４は、上記繰り返し制御とともに、秘密鍵の当該ビットが「１」のときには、第１モンゴメリ変換部１１１の出力値を選択し、「０」のときには第２モンゴメリ変換部１１２の出力値を選択する。
【００６２】
二乗算部１１５及び乗算部１１６は、それぞれ、モンゴメリ領域での２乗算及び乗算を実行する。
ここでのモンゴメリ領域の乗算は、モンゴメリ領域に変換された２個の入力値、例えば、Ｍｏｎ＿｛ｋ，ｐ｝（Ｘ）とＭｏｎ＿｛ｋ，ｐ｝（Ｙ）の積に対して、モンゴメリリダクション処理を行い、モンゴメリ領域の乗算結果Ｍｏｎ＿｛ｋ，ｐ｝（Ｚ）＝Ｍｏｎ＿｛ｋ，ｐ｝（Ｘ×Ｙ）を求めるものである。２乗算は、上記ＸとＹが同じ場合に相当する。
【００６３】
ここで、モンゴメリリダクションは、倍長値Ｕ（上記では、Ｘ×Ｙ）に対して、Ｕ×（２k ）-1 ｍｏｄ  ｐの演算を、除算なしで高速に実装する方法である。モンゴメリリダクションの詳細については、例えば非特許文献３に詳しい。
【００６４】
なお、仮に法のビット数が２０４８ビットである場合、二乗算部１１５と乗算部１１６を、２０４８ビットの乗算器で実装するのは実装規模が巨大となり現実的でない。そのため、例えば３２ビット程度の乗算器を繰り返して用いる多倍長演算方法で実現するのが、一般的である。
【００６５】
（５）  モンゴメリ逆変換部１２０
モンゴメリ逆変換部１２０は、モンゴメリ領域での２乗算と乗算との繰り返しの最終結果に、モンゴメリ逆変換を施して、出力データＭを求める。以降ではモンゴメリ逆変換を
Ｍｏｎ＿｛ｋ，ｐ｝-1（  ）と表記する。
【００６６】
Ｍｏｎ＿｛ｋ，ｐ｝-1（Ｘ）＝Ｘ×（２k ）-1  ｍｏｄ  ｐ    （式２）
なお、モンゴメリ変換とモンゴメリ逆変換について、式３が成り立つ。
Ｍｏｎ＿｛ｋ，ｐ｝-1（Ｍｏｎ＿｛ｋ，ｐ｝（Ｘ））＝Ｘ      （式３）
モンゴメリ逆変換部１２０は、出力データＭを入出力部１０２へ出力する。
【００６７】
３．公開鍵復号部１０１の動作
公開鍵復号部１０１による高速べき乗剰余演算の動作について、図４に示すフローチャートを用いて説明する。
【００６８】
法設定部１１７は、法ｐを定め、整数設定部１１８は、整数ｋを定め、第１モンゴメリ変換部１１１は、モンゴメリ変換値Ｂ＝Ｃ×（２k ）ｍｏｄ  ｐ  を算出し、第２モンゴメリ変換部１１２は、モンゴメリ変換値Ａ＝（２k）ｍｏｄ  ｐ  を算出する（ステップＳ１０１）。
【００６９】
制御部１１４は、第２モンゴメリ変換部１１２によるモンゴメリ変換値Ａを選択し、演算結果の値を格納する演算値領域に設けられた変数としての演算結果Ｗに、初期値として選択したモンゴメリ変換値Ａを書き込む。
【００７０】
Ｗ＝Ｍｏｎ＿｛ｋ，ｐ｝（１）＝（２k ）ｍｏｄ  ｐ  （ステップＳ１０２）
制御部１１４は、抽出部１２２により、秘密鍵格納部１１３に格納されている秘密鍵Ｓの最上位から１ビットずつ抽出を試みる（ステップＳ１０３）。
【００７１】
秘密鍵Ｓの最上位のビットから最下位のビットまで、前記抽出が完了したら（ステップＳ１０４でＹＥＳ）、制御部１１４は、モンゴメリ逆変換部１２０に対して演算結果Ｗのモンゴメリ逆変換をするように制御し、モンゴメリ逆変換部１２０は、演算結果Ｗに対して、モンゴメリ逆変換を施して、出力データＭを生成する。
【００７２】
Ｍ＝Ｍｏｎ＿｛ｋ，ｐ｝-1（Ｗ）
次に、モンゴメリ逆変換部１２０は、出力データＭを入出力部１０２へ出力する。ここで、Ｍ＝ＣS   ｍｏｄ  ｐである（ステップＳ１０９）。こうして、公開鍵復号部１０１による高速べき乗剰余演算が終了する。
【００７３】
抽出が完了していない場合（ステップＳ１０４でＮＯ）、制御部１１４は、二乗算部１１５に対して演算結果Ｗをモンゴメリ領域で２乗するように制御し、二乗算部１１５は、演算結果Ｗをモンゴメリ領域で２乗し、その２乗値を演算結果Ｗに上書きする。
【００７４】
Ｗ＝Ｍｏｎ＿｛ｋ，ｐ｝（Ｗ×Ｗ）    （ステップＳ１０５）。
次に、制御部１１４は、抽出したビットが「１」か又は「０」であるかを判断し、秘密鍵Ｓから抽出した当該ビットが「１」のときには（ステップＳ１０６）、第１モンゴメリ変換部１１１により出力されるモンゴメリ変換値Ｂを選択し、乗算部１１６に対してモンゴメリ乗算を算出するように制御し、乗算部１１６は、演算結果Ｗと第１モンゴメリ変換部１１１により出力されるモンゴメリ変換値Ｂ＝Ｍｏｎ＿｛ｋ，ｐ｝（Ｃ）とを乗算し、得られた値を演算結果Ｗへ上書きする。
【００７５】
Ｗ＝Ｍｏｎ＿｛ｋ，ｐ｝（Ｗ×Ｂ）  （ステップＳ１０７）。次に、制御部１１４は、制御をステップＳ１０３へ移す。
一方、秘密鍵Ｓから抽出した当該ビットが「０」のときには、制御部１１４は、第２モンゴメリ変換部１１２の出力値を選択し、乗算部１１６に対してモンゴメリ乗算を算出するように制御し、乗算部１１６は、演算結果Ｗと第２モンゴメリ変換部１１２の出力値であるＡ＝Ｍｏｎ＿｛ｋ，ｐ｝（１）とを乗算し、得られた値を演算結果Ｗへ上書きする。
【００７６】
Ｗ＝Ｍｏｎ＿｛ｋ，ｐ｝（Ｗ×Ａ）  （ステップＳ１０８）。次に、制御部１１４は、制御をステップＳ１０３へ移す。
３．実施の形態の効果
まず、図４に示すフローチャートから明らかなように、秘密鍵Ｓの当該ビットが「１」であるか又は「０」であるかにかかわらず、必ずモンゴメリの乗算部１１６は動作する。そのため、乗算の有無で解析を行う攻撃であるＳＰＡは困難である。
【００７７】
本実施の形態では、秘密鍵の当該ビットが「０」である場合の乗算には、モンゴメリ領域での「１」（Ｍｏｎ＿｛ｋ，ｐ｝（１）と表記）を用いる。このモンゴメリ領域での「１」は整数ｋと法ｐに依存して定まる値であるため、ｋおよびｐを知らない攻撃者はハミング重みを予測することができない。そのためモンゴメリ領域での「１」を判別して解析をすることは困難である。
【００７８】
また、万が一、ハミング重みが攻撃者により求められてしまった場合には、モンゴメリ領域での「１」を判別する解析が成功するかもしれない。本実施の形態では、さらに、法ｐのビット数以上という制限のもとに、整数ｋを任意に変更することにより、ハミング重みも変更される。これにより、いっそう、解析が困難となる。
【００７９】
なお、その変更タイミングは頻繁であるほど、さらに、その整数ｋの取りうるバラエティが多いほど、ダミー乗算を区別することは困難であり安全性が向上する。しかし、ｋをむやみに大きくとると１回の２乗算や乗算の処理時間が一般には増加するため、どの程度のバラエティをもったｋの大きさにするのか、あるいは変更のタイミングをどう設定するのかは、アプリケーションに必要とされる速度と安全性に依存して決定する。図３における設定制御部１１９がこれらの制御をする。
【００８０】
４．その他の変形例
なお、本発明を上記の実施の形態に基づいて説明してきたが、本発明は、上記の実施の形態に限定されないのはもちろんである。以下のような場合も本発明に含まれる。
【００８１】
（１）公開鍵復号部１０１による上記とは別の高速べき乗剰余演算の動作について、図５に示すフローチャートを用いて説明する。
法設定部１１７は、法ｐを定める。ここで、法ｐは、例えば、５１２ビットの秘密の素数である。また、法設定部１１７は、ｐより大きい任意の２のべき乗値Ｒを定める。例えば、乱数ｋを生成し、Ｒ＝２kとする。例えば、Ｒ＝２512 である。また、法設定部１１７は、乱数ｒを生成する（ステップＳ２０１）。
【００８２】
次に、第２モンゴメリ変換部１１２は、モンゴメリ変換値ｙを算出する。
ｙ＝Ｍ（１）＝Ｒ  ｍｏｄ  ｐ  ＝Ｒ  −  ｐ
ｙは、演算結果の値を格納するための演算値領域に設けられる変数である。
【００８３】
なお、ここでは、「Ｍｏｎ＿｛ｋ，ｐ｝（１）」を更に簡略に「Ｍ（１）」と表現している（ステップＳ２０２）。
制御部１１４は、抽出部１２２により、秘密鍵格納部１１３に格納されている秘密鍵Ｓの最上位から１ビットずつ抽出を試みる（ステップＳ２０３）。
【００８４】
秘密鍵Ｓの最上位ビットから最下位ビットまで、抽出が完了したら（ステップＳ２０４でＹＥＳ）、ｙを出力し（ステップＳ２０９）、公開鍵復号部１０１による高速べき乗剰余演算が終了する。
【００８５】
抽出が完了していない場合（ステップＳ２０４でＮＯ）、二乗算部１１５は、次式による二乗算を行う。
ｙ＝｛ｙ×ｙ｝×Ｒ-1  ｍｏｄ  ｒ×ｐ          （ステップＳ２０５）。
【００８６】
次に、制御部１１４は、抽出したビットが「１」か又は「０」であるかを判断し、秘密鍵Ｓから抽出した当該ビットが「１」のときには（ステップＳ２０６）、乗算部１１６は、次式による乗算を行う。
【００８７】
ｙ＝｛ｙ×Ｍ（Ｃ）｝×Ｒ-1  ｍｏｄ  ｒ×ｐ    （ステップＳ２０７）。
次に、制御部１１４は、制御をステップＳ２０３へ移す。
一方、秘密鍵Ｓから抽出した当該ビットが「０」のときには、乗算部１１６は、次式による乗算を行う。
【００８８】
ｙ＝｛ｙ×Ｍ（１）｝×Ｒ-1  ｍｏｄ  ｒ×ｐ    （ステップＳ２０８）。
次に、制御部１１４は、制御をステップＳ１０３へ移す。
この変形例では、公開鍵復号部１０１は、モンゴメリ逆変換部１２０を含んでない。
【００８９】
（２）整数ｋの変更タイミングは、入力データごとであってもよい。つまり、第１の入力データを取得すると、整数ｋの値をランダムに変更し、次に第２の入力データを取得すると、整数ｋの値をさらにランダムに変更し、さらに第３の入力データを取得すると、整数ｋの値をさらにランダムに変更する。
【００９０】
また、複数の入力データに対して同じｋを用いてもよい。次の複数の入力データに対して、別の同じ整数を用いてもよい。
また、ある入力データの演算の途中（繰返しの途中）でランダムに変更してもよい。また、外部よりアプリケーションやユーザが指示するタイミングでランダムに変更してもよい。
【００９１】
第１及び第２モンゴメリ変換部において用いられる法についても、上記と同様に、入力データごとにランダムに変更してもよいし、複数の入力データに対して同じ法を用いてもよいし、次の複数の入力データに対して、別の同じ整数を用いてもよいし、ある入力データの演算の途中（繰返しの途中）でランダムに変更してもよいし、外部よりアプリケーションやユーザが指示するタイミングでランダムに変更してもよい。
【００９２】
（３）（ａ）ｐの乱数倍を法として用いて、第２モンゴメリ変換部１１２の出力を求めてもよい。つまり、法設定部１１７は、乱数ｒを生成し、生成した乱数ｒを第２モンゴメリ変換部１１２へ出力する。第２モンゴメリ変換部１１２は、
２k ｍｏｄ  （ｒ×ｐ）を出力する。
【００９３】
このことにより、第１モンゴメリ変換部１１１あるいは第２モンゴメリ変換部１１２のいずれを使用しているのかを区別することがよりいっそう困難となり安全性が向上する。
このとき、第２モンゴメリ変換部１１２の法は、ｐのままでよいし、また、別の乱数倍であってもよい。
【００９４】
このように、第１モンゴメリ変換部１１１の法と、第２モンゴメリ変換部１１２の法とに対して独立して設定されるとしてもよい。
なお、モンゴメリ逆変換部１２０の法は、ｐのままである。
【００９５】
（ｂ）また、第１モンゴメリ変換部１１１で用いる法をｐの乱数倍としてもよい。このとき、第２モンゴメリ変換部１１２の法は、ｐのままでよいし、また、別の乱数倍であってもよい。なお、モンゴメリ逆変換部１２０の法は、ｐのままとする。これにより、１つの入力データの演算中の、複数箇所の電力変化間の相関を計算する攻撃に対して安全性が向上する。
【００９６】
また、まずｐの乱数倍を新たな法として求めた後、これを用いて第１モンゴメリ変換部１１１、第２モンゴメリ変換部１１２、そして二乗算部１１５や乗算部１１６での計算を行ってよい。ただし、この場合、定められた法のもとの最終出力を得るためには、出力の前に、法ｐで剰余演算をしてから、出力することが必要になる。
【００９７】
（ｃ）上記（ａ）（ｂ）において、第１モンゴメリ変換部１１１においてｐの乱数倍の法（第１の法）が用いられ、第２モンゴメリ変換部１１２においてｐの別の乱数倍の法（第２の法）が用いられる場合、つまり、第１の法と第２の法とが異なる場合には、二乗算部１１５と乗算部１１６とにおいて用いられる法は、第１の法と第２の法の公倍数とし、モンゴメリ逆変換部１２０において用いられる法は、ｐのままとすればよい。
【００９８】
（４）入力データ及び出力データを、モンゴメリ領域の値としてもよい。この場合、実施の形態で含まれている、第１モンゴメリ変換部１１１とモンゴメリ逆変換部１２０は公開鍵復号部１０１の外に実装されてもよい。これは、例えば大きなシステムの中の一部として公開鍵復号部１０１が実装されており、公開鍵暗号の演算のみならず、すべてをモンゴメリ領域で実装する場合である。
【００９９】
（５）本実施の形態では、秘密鍵を１ビットずつ処理する高速バイナリべき乗剰余演算を用いているが、何も１ビットごとの処理だけとは限らない。
例えば、２ビットごとの処理であれば、二乗算部１１５では２回の２乗算を行い、制御部１１４では、秘密鍵の２ビットに対応して４種類のモンゴメリ変換部からの出力値を選択し、選択した出力値を乗算部１１６で乗算する。
【０１００】
なお、この４種類のモンゴメリ変換部のうちの１つは、「１」のモンゴメリ変換部（つまり、ダミー乗算の入力値を求める部分）となり、秘密鍵の当該２ビットが両方とも「０」である場合に選択される。
【０１０１】
ここで、２ビットが「００」のとき、対応するモンゴメリ変換部は、「１」のモンゴメリ変換値を出力し、２ビットが「０１」のとき、対応するモンゴメリ変換部は、「Ｃ」のモンゴメリ変換値を出力する。また、２ビットが「１０」のとき、対応するモンゴメリ変換部は、「Ｃ2」のモンゴメリ変換値を出力し、２ビットが「１１」のとき、対応するモンゴメリ変換部は、「Ｃ3 」のモンゴメリ変換値を出力する。
【０１０２】
もちろん秘密鍵を３ビット以上ごとに処理する場合であっても、上記を拡張して適用することで実現できる。
また、本実施の形態では、秘密鍵を上位から処理するアルゴリズムを用いているが、下位から処理するものであってもよい。この場合には、入力データに対応したモンゴメリ変換値を繰り返し２乗し、秘密鍵の対応するビットが１のときには、前記２乗演算値を乗算し、０のときには、本実施の形態と同様に、整数ｋと法ｐから求められる値を用いたダミー乗算を行う。
【０１０３】
この場合における公開鍵復号部１０１による高速べき乗剰余演算の動作について、図４との相違点を中心として、図６に示すフローチャートを用いて説明する。
図４に示すステップＳ１０３に代えて、ステップＳ１０３ａにおいて、制御部１１４は、抽出部１２２により、秘密鍵格納部１１３に格納されている秘密鍵Ｓの最下位から１ビットずつ抽出を試みる。
【０１０４】
秘密鍵Ｓの最下位のビットから最上位のビットまで、前記抽出が完了したら（ステップＳ１０４ａでＹＥＳ）、制御部１１４は、モンゴメリ逆変換部１２０に対して演算結果Ｗのモンゴメリ逆変換をするように制御する。
【０１０５】
抽出が完了していない場合（ステップＳ１０４ａでＮＯ）、図４に示すステップＳ１０５に代えて、ステップＳ１０５ａにおいて、制御部１１４は、二乗算部１１５に対して入力データＣをモンゴメリ領域で２乗するように制御し、二乗算部１１５は、入力データＣをモンゴメリ領域で２乗し、その２乗値を入力データＣに上書きする。
【０１０６】
Ｃ＝Ｍｏｎ＿｛ｋ，ｐ｝（Ｃ×Ｃ）
（６）本実施の形態では、ＲＳＡ暗号の復号処理で説明したが、次に示すように、ＲＳＡ署名の署名生成に適用してもよい。
【０１０７】
ＲＳＡの鍵生成を行う。ＲＳＡの鍵生成は、ＲＳＡ暗号の場合と同じであるので詳細を省略する。
ここで、秘密鍵をｄとし、公開鍵をｅ、ｐとする。
【０１０８】
署名生成装置は、次式により、文書ｍに対して、署名データｓを生成する。
ｓ＝ｈ（ｍ）d ｍｏｄ  ｐ
ここで、ｈ（  ）は、一方向性ハッシュ関数である。
【０１０９】
本発明は、前記署名生成装置において、上記の実施の形態と同様にして適用される。前記署名生成装置は、所定の法において入力値を整数乗するべき乗剰余演算により、入力値の確実な処理を行う情報セキュリティ装置である。
【０１１０】
なお、署名検証装置は、次式により、署名の検証を行う。
ｈ（ｍ）＝ｓe ｍｏｄ  ｐ
また、本発明は、ＲＳＡ暗号の暗号処理において、公開鍵を秘匿するようなアプリケーションの場合に、適用することができる。
【０１１１】
さらに、楕円曲線暗号や超楕円曲線暗号における、秘密鍵を用いた処理におけるＳＰＡ対策としても用いることができる。
（７）上記の実施の形態及び変形例は、次に示すような場合において適用される。
【０１１２】
（ａ）実施の形態及び変形例は、秘密のメッセージ伝送において適用される。
本実施の形態において、秘密のメッセージ伝送の一例として、ライセンス鍵を秘密に伝送する場合について説明した。
【０１１３】
上述したように、ＩＣカード１００は、所定の法において入力値を整数乗するべき乗剰余演算により、入力値の安全な処理を行う情報セキュリティ装置である。ここで、「安全」とは、メッセージが送信者及び受信者以外の第三者に知られないように秘密にすることをいう。
【０１１４】
本発明は、コンテンツ暗号化装置とコンテンツ再生装置とから構成されるコンテンツ配信システムにおいて適用され、例えば、映画、動画像、音声、音楽、小説、データベースなどのデジタル情報を秘密通信の対象としてもよい。これらのコンテンツは、コンテンツ供給者から利用者に対して、これらのコンテンツを記録している記録媒体を販売したり、レンタルすることにより、提供される。また、デジタル放送やインターネットを介して、コンテンツ供給者から利用者に提供される。
【０１１５】
コンテンツ供給者の有するコンテンツ暗号化装置は、デジタル著作物である映画を暗号化してＤＶＤに記録する。利用者の有するコンテンツ再生装置は、ＤＶＤから暗号化デジタル著作物を読み出し、復号して、映画を生成し、生成した映画を音声及び映像として再生して、表示及び出力する。
【０１１６】
上記の例において、コンテンツを暗号化及び復号するためのコンテンツ鍵を、実施の形態に示す秘密通信の対象としてもよい。この場合、コンテンツ鍵は、実施の形態に示す方法と同様にして、暗号化され、また復号される。
【０１１７】
この場合に、コンテンツは、コンテンツ鍵により、共通鍵暗号方式を用いて、暗号化され、復号される。
次に示すような金銭の決済システムに適用することもできる。
【０１１８】
例えば、通貨の代わりに用いることができる電子マネーを秘密通信の対象とし、ＩＣカードは、電子マネーを記憶しており、利用者が、商品を購入する際に、ＩＣカードは、商品の購入額に相当する電子マネーを暗号化して送信し、また、内部に記憶している電子マネーから送信した分を減じる。商店に設置されるレジスタ装置は、暗号化電子マネーを受信し、受信した暗号化電子マネーを復号して電子マネーを再生し、記憶する。
【０１１９】
また、上記のＩＣカードに代えて、美術館や博物館などの各種施設を利用のためのＩＣカードタイプの電子チケットが、上記のように、電子マネーに相当する情報を記憶しているとしてもよい。各種施設の入り口に設けられた入場管理装置は、各種施設の利用料金に相当する額の電子マネーを要求し、前記電子チケットは、要求された額の電子マネーを暗号化して送信し、入場管理装置は、暗号化電子マネーを受信し、受信した暗号化電子マネーを復号して電子マネーを生成し、記憶するとしてもよい。
【０１２０】
また、鉄道、バスなどの交通機関を利用する際に用いられるＩＣカードタイプのＩＣカード乗車券が、上記のように、電子マネーに相当する情報を記憶しているとしてもよい。交通機関の駅の入り口に設けられた入場管理装置は、当該駅を識別する識別情報を送信し、ＩＣカード乗車券は、前記識別情報を受信し、記憶する。交通機関の駅の出口に設けられた出場管理装置は、前記識別情報をＩＣカード乗車券から受信し、受信した識別情報と当該出場管理装置が設けられた駅とを用いて、料金表により乗車料金を算出し、算出した乗車料金に相当する額の電子マネーを要求し、ＩＣカード乗車券は、要求された額の電子マネーを暗号化して送信し、出場管理装置は、暗号化電子マネーを受信し、受信した暗号化電子マネーを復号して電子マネーを生成し、記憶する。
【０１２１】
（ｂ）実施の形態及び変形例は、認証において適用される。認証とは、メッセージが自称どおりの人物によって送られたこと、またメッセージが改竄されなかったということの検証である。また、実施の形態及び変形例は、身分の証明において適用される。身分の証明とは、例えば、データへのアクセス権、又は施設へのアクセス権（入室権）を持つことの証明、又は自分が主張どおりの人物であることの証明である。さらに、実施の形態及び変形例は、否認防止において適用される。否認防止とは、例えば、実は何かに同意したのに、同意していないと主張する者に対抗することをいう。
【０１２２】
上記の変形例において、認証の一例として、ＲＳＡデジタル署名について説明した。本発明は、上述した署名生成装置において、上記の実施の形態と同様にして適用される。前記署名生成装置は、所定の法において入力値を整数乗するべき乗剰余演算により、入力値の確実な処理を行う情報セキュリティ装置である。
【０１２３】
ここで、「確実」とは、例えば、メッセージが自称どおりの人物によって送られたこと、またメッセージが改竄されなかったことである。また、例えば、データへのアクセス権を持つこと、施設へのアクセス権（入室権）を持つこと、又は自分が主張どおりの人物であることである。
【０１２４】
（ｃ）実施の形態及び変形例は、鍵交換（鍵共有とも呼ぶ）において適用される。鍵交換とは、例えば、２人の人が放送電波を使ってある秘密鍵暗号方式で使うための秘密鍵に同意することである。
【０１２５】
鍵交換の典型的な方法として、ＤＨ（ディフィーヘルマン）鍵交換という方法がある。ここでは、鍵を交換しあうそれぞれが、秘密のべき数を任意に生成し、これを用いてべき乗演算を行う。
【０１２６】
このときの、べき乗演算に本発明を適用し、秘密のべき数を秘匿して秘密の共通鍵を共有することができる。
（ｄ）実施の形態及び変形例は、零知識証明において適用される。零知識証明とは、例えば、ある人が、数論的あるいは組合せ論的問題を解くことに成功したことを、解が何であるかのわずかの情報さえ与えることなく、他人にこのことを納得させることを言う。
【０１２７】
（ｅ）上述したように、本発明は、秘密のべき値を用いたべき乗演算を用いるプロトコル方式に適用することができる。
（８）本発明は、入力データと秘密鍵を使って、定められた法における乗算を繰り返してべき乗剰余計算を行う情報セキュリティ装置である。前記情報セキュリティ装置は、前記入力データに対応したモンゴメリ変換値を求める第１のモンゴメリ変換部と、１のモンゴメリ変換値を求める第２のモンゴメリ変換部と、秘密鍵のビットが０ならば、前記第２のモンゴメリ変換部の出力を選択し、そうでなければ前記第１のモンゴメリ変換部の出力を選択する制御部と、これまで計算した結果と前記制御部で選択した値を用いて乗算を行う乗算部を備えており、前記法をｐとし、ｐの有効ビット数より大きな整数をｋとするとき、前記第２のモンゴメリ変換部は、前記ｐを法として、前記ｋをべきとする２のべき乗値を出力する。この情報セキュリティ装置によると、第２のモンゴメリ変換部の出力（モンゴメリ領域での１）は、整数ｋと法ｐに依存して決定される。そのため、ハミング重みに偏りはなく、電力変化を用いて、乗算の入力として第１のモンゴメリ変換部の出力を用いたのか、第２のモンゴメリ変換部の出力を用いたのかを区別することは困難である。
【０１２８】
ここで、前記ｐの有効ビット数より大きな整数ｋをランダムに選択する整数ｋ設定部を備えると構成してもよい。この構成によると、ランダムに選択される整数ｋに依存して、第２のモンゴメリ変換部の出力が変わる。そのため、複数入力データにわたり、電力変化の相関を計算する攻撃に対して安全性が向上する。
【０１２９】
ここで、前記第２のモンゴメリ変換部は、前記ｐの乱数倍を法として、前記ｋをべきとする２のべき乗値を出力すると構成してもよい。この構成によると、ランダムに選択される法の値に依存して、第２のモンゴメリ変換部の出力が変わる。そのため、複数入力データにわたり、電力変化の相関を計算する攻撃に対して安全性が向上する。
【０１３０】
ここで、前記第１のモンゴメリ変換部は、前記ｐの乱数倍を法として、前記入力データに対応したモンゴメリ変換値を出力すると構成してもよい。この構成によると法の変化に依存して、第１のモンゴメリ変換部の出力が変わる。このため、１つの入力データの演算中の、複数箇所の電力変化間の相関を計算する攻撃に対して安全性が向上する。
【０１３１】
ここで、前記ｐの乱数倍を新たに法とする法変更部を備え、設定した法を用いて前記第１のモンゴメリ変換部、第２のモンゴメリ変換部および前記乗算部にて所定の計算が処理されると構成してもよい。この構成によると法変更部で変更される法に依存して、第１のモンゴメリ変換部、第２のモンゴメリ変換部のみならず、乗算部で用いる法も変換されるため、よりいっそう電力変化と秘密鍵の相関が小さくなり安全性が向上する。
【０１３２】
ここで、前記整数ｋあるいは前記法は、外部からの指示により変更されると構成してもよい。この構成によると、外部のアプリケーションやユーザが指定したタイミングで整数ｋや法を変化させることで、そのタイミングに対応した性能と安全性を有した情報セキュリティ装置が実現できる。
【０１３３】
（９）上記の各装置は、具体的には、マイクロプロセッサ、ＲＯＭ、ＲＡＭ、などから構成されるコンピュータシステムである。前記ＲＡＭには、コンピュータプログラムが記憶されている。ここで、コンピュータプログラムは、所定の機能を達成するために、コンピュータに対する指令を示す命令コードが複数個組み合わされて構成されたものである。前記マイクロプロセッサが、前記コンピュータプログラムに従って動作することにより、各装置は、その機能を達成する。つまり、前記マイクロプロセッサは、前記コンピュータプログラムに含まれる各命令を１個ずつ読み出し、読み出した命令を解読し、解読結果に従って動作する。
【０１３４】
（１０）上記の各装置を構成する構成要素の一部又は全部は、１個のシステムＬＳＩ（Large Scale Integration：大規模集積回路）から構成されているとしてもよい。システムＬＳＩは、複数の構成部を１個のチップ上に集積して製造された超多機能ＬＳＩであり、具体的には、マイクロプロセッサ、ＲＯＭ、ＲＡＭなどを含んで構成されるコンピュータシステムである。前記ＲＡＭには、コンピュータプログラムが記憶されている。前記マイクロプロセッサが、前記コンピュータプログラムに従って動作することにより、システムＬＳＩは、その機能を達成する。
【０１３５】
また、上記の各装置を構成する構成要素の各部は、個別に１チップ化されても良いし、一部又は全てを含むように１チップ化されてもよい。また、ここでは、ＬＳＩとしたが、集積度の違いにより、ＩＣ、システムＬＳＩ、スーパーＬＳＩ、ウルトラＬＳＩと呼称されることもある。
【０１３６】
また、集積回路化の手法はＬＳＩに限るものではなく、専用回路又は汎用プロセッサで実現してもよい。ＬＳＩ製造後に、プログラムすることが可能なＦＰＧＡ（FieldProgrammable Gate Array）やＬＳＩ内部の回路セルの接続や設定を再構成可能なリコンフィギュラブル・プロセッサを利用しても良い。
【０１３７】
さらには、半導体技術の進歩又は派生する別技術によりＬＳＩに置き換わる集積回路化の技術が登場すれば、当然、その技術を用いて機能ブロックの集積化を行ってもよい。バイオ技術の適応等が可能性としてありえる。
【０１３８】
（１１）上記の各装置を構成する構成要素の一部又は全部は、各装置に脱着可能なＩＣカード又は単体のモジュールから構成されているとしてもよい。前記ＩＣカード又は前記モジュールは、マイクロプロセッサ、ＲＯＭ、ＲＡＭ、などから構成されるコンピュータシステムである。前記ＩＣカード又は前記モジュールは、上記の超多機能ＬＳＩを含むとしてもよい。マイクロプロセッサが、コンピュータプログラムに従って動作することにより、前記ＩＣカード又は前記モジュールは、その機能を達成する。このＩＣカード又はこのモジュールは、耐タンパ性を有するとしてもよい。
【０１３９】
（１２）本発明は、上記に示す方法であるとしてもよい。また、これらの方法をコンピュータにより実現するコンピュータプログラムであるとしてもよいし、前記コンピュータプログラムからなるデジタル信号であるとしてもよい。
【０１４０】
また、本発明は、前記コンピュータプログラム又は前記デジタル信号をコンピュータ読み取り可能な記録媒体、例えば、フレキシブルディスク、ハードディスク、ＣＤ―ＲＯＭ、ＭＯ、ＤＶＤ、ＤＶＤ−ＲＯＭ、ＤＶＤ−ＲＡＭ、ＢＤ（Ｂｌｕ−ｒａｙ  Ｄｉｓｃ）、半導体メモリなど、に記録したものとしてもよい。また、これらの記録媒体に記録されている前記コンピュータプログラム又は前記デジタル信号であるとしてもよい。
【０１４１】
また、本発明は、前記コンピュータプログラム又は前記デジタル信号を、電気通信回線、無線又は有線通信回線、インターネットを代表とするネットワーク、データ放送等を経由して伝送するものとしてもよい。
【０１４２】
また、本発明は、マイクロプロセッサとメモリとを備えたコンピュータシステムであって、前記メモリは、上記コンピュータプログラムを記憶しており、前記マイクロプロセッサは、前記コンピュータプログラムに従って動作するとしてもよい。
【０１４３】
また、前記プログラム又は前記デジタル信号を前記記録媒体に記録して移送することにより、又は前記プログラム又は前記デジタル信号を前記ネットワーク等を経由して移送することにより、独立した他のコンピュータシステムにより実施するとしてもよい。
【０１４４】
（１３）上記実施の形態及び上記変形例をそれぞれ組み合わせるとしてもよい。
【産業上の利用可能性】
【０１４５】
本発明の情報セキュリティ装置および情報セキュリティ方法は、秘密鍵を用いて公開鍵暗号演算や署名演算を実現する暗号モジュールにおいて、特にＩＣカードやセキュアカードのように解読者側の手に渡って、ＳＰＡなどの攻撃が行われる懸念がある場合に利用される。
【０１４６】
本発明を構成する各装置は、秘密のメッセージ伝送や認証を必要とするあらゆる産業において、経営的に、また継続的及び反復的に使用することができる。また、本発明を構成する各装置は、電器機器製造産業において、経営的に、また継続的及び反復的に、製造し、販売することができる。
【図面の簡単な説明】
【０１４７】
【図１】本発明に係る１個の実施の形態としてのコンテンツ再生システム１の構成を示すシステム構成図である。
【図２】ＩＣカード１００及びＤＶＤプレーヤ２００の構成を示すブロック図である。
【図３】公開鍵復号部１０１の構成を示すブロック図である。
【図４】公開鍵復号部１０１による高速べき乗剰余演算の動作を示すフローチャートである。
【図５】公開鍵復号部１０１による別の高速べき乗剰余演算の動作を示すフローチャートである。
【図６】秘密鍵の下位ビットから処理する場合における公開鍵復号部１０１による高速べき乗剰余演算の動作を示すフローチャートである。
【符号の説明】
【０１４８】
１    コンテンツ再生システム
１０    ネットワーク
１００    ＩＣカード
１０１    公開鍵復号部
１０２    入出力部
１１１    第１モンゴメリ変換部
１１２    第２モンゴメリ変換部
１１３    秘密鍵格納部
１１４    制御部
１１５    二乗算部
１１６    乗算部
１１７    法設定部
１１８    整数設定部
１１９    設定制御部
１２０    モンゴメリ逆変換部
２００    ＤＶＤプレーヤ
２０１    モニタ
２０２    スピーカ
２１１    通信部
２１２    入出力部
２１３    復号部
２１４    復号部
２１５    再生部
２１６    ドライブ部
３００    ＤＶＤ
４００    サーバ装置
【手続補正３】
【補正対象書類名】図面
【補正対象項目名】全図
【補正方法】変更
【補正の内容】
【図１】
2007046402.tif 000009
【図２】
2007046402.tif 000010
【図３】
2007046402.tif 000011
【図４】
2007046402.tif 000012
【図５】
2007046402.tif 000013
【図６】
2007046402.tif 000014
【国際調査報告】
2007046402.tif 000015
2007046402.tif 000016