(57)【要約】  本発明は、安全かつコンパクトな累乗方法に関するものである。本発明に係る方法は、暗号アルゴリズムがチップ・カードのような電子デバイスで使用される暗号技術の分野で応用することが可能である。【選択図】  なし【特許請求の範囲】
【請求項１】
メイン中央処理装置と、少なくとも３つのレジスタ（Ｒ０、Ｒ１、Ｒ２）を有するワーキング・メモリとを備える電子構成部品を対象とする、ｘのｄ乗（ｘｄ）の形をとる乗法表記による代数群において累乗計算を実行する方法であって、ｘは前記群の元であり、ｄは所定の指数であり、その２進表記は｛ｄ［ｔ−１］，ｄ［ｔ−２］，．．．，ｄ［１］，ｄ［０］｝となり、ｄ［ｉ］は０又は１と等しく、前記方法は、元ｙについて、ｙ＝ｘ＾ｄ、即ちｘ．ｘ．．．．．ｘ（ｄ回）を返し、
１）レジスタＲ０を１に初期化し、レジスタＲ１及びＲ２をｘに初期化するステップと、
２）０〜ｔ−１のｉについて、
ａ）ｂ＝１−ｄ［ｉ］；
ｂ）Ｒｂ＝Ｒｂ＊Ｒ２（１回目の乗算）；
ｃ）Ｒ２＝Ｒ０＊Ｒ１（２回目の乗算）；
を実行するステップと、
３）Ｒ０を返すステップと、
を含むことを特徴とする方法。
【請求項２】
メイン中央処理装置と、少なくとも３つのレジスタ（Ｒ０、Ｒ１、Ｒ２）を有するワーキング・メモリとを備える電子構成部品を対象とする、ｄ×Ｐ（ｄ．Ｐ）の形をとる加法表記による代数群において累乗計算を実行する方法であって、Ｐは前記群の元であり、ｄは所定の指数であり、その２進表記は｛ｄ［ｔ−１］，ｄ［ｔ−２］，．．．，ｄ［１］，ｄ［０］｝となり、ｄ［ｉ］は０又は１と等しく、前記方法は、元Ｑについて、Ｑ＝ｄ．Ｐ、即ちＰ＋Ｐ＋．．．＋Ｐ（ｄ回）を返し、
１）レジスタＲ０を０に初期化し、レジスタＲ１及びＲ２をＰに初期化するステップと、
２）０〜ｔ−１のｉについて、
ａ）ｂ＝１−ｄ［ｉ］；
ｂ）Ｒｂ＝Ｒｂ＋Ｒ２（１回目の加算）；
ｃ）Ｒ２＝Ｒ０＋Ｒ１（２回目の加算）；
を実行するステップと、
３）Ｒ０を返すステップと、
を含むことを特徴とする方法。
【請求項３】
１）レジスタＲ０をＰに初期化し、レジスタＲ１及びＲ２を２．Ｐに初期化するステップと、
２）１〜ｔ−１のｉについて、
ａ）ｂ＝１−ｄ［ｉ］；
ｂ）Ｒｂ＝Ｒｂ＋Ｒ２（１回目の加算）；
ｃ）Ｒ２＝Ｒ０＋Ｒ１（２回目の加算）；
を実行するステップと、
３）ｄ［０］＝０であれば、Ｒ０＝Ｒ０−Ｐを実行するステップと、
４）Ｒ０を返すステップと、
を含むことを特徴とする請求項２に記載の累乗方法。
【請求項４】
前記群における元Ｐの２倍（２．Ｐ）は、前記元Ｐと前記群のＰとは異なる別の既知の元Ｔとを加算することによって求められる第１の元（Ｐ＋Ｔ）と、前記元Ｐから前記元Ｔを減算することによって求められる第２の元（Ｐ−Ｔ）とを加算する加法（（Ｐ＋Ｔ）＋（Ｐ−Ｔ））だけを使用して計算されることを特徴とする請求項３に記載の累乗方法。
【請求項５】
前記代数群は、ある環又は体から成る乗法群であることを特徴とする請求項１に記載の累乗方法。
【請求項６】
前記代数群は、ある環又は体から成る加法群であることを特徴とする請求項２乃至４のいずれか一項に記載の累乗方法。
【請求項７】
前記代数群は、ある楕円曲線の各点から成る群であることを特徴とする請求項２乃至４のいずれか一項に記載の累乗方法。
【請求項８】
公開鍵暗号に適用され、前記既知の元（Ｔ）が前記公開鍵の一要素となることを特徴とする請求項４に記載の累乗方法。
【請求項９】
電子構成部品に実装されることを特徴とする請求項１乃至８のいずれか一項に記載の累乗方法。
【請求項１０】
前記電子構成部品は、チップ・カードであることを特徴とする請求項９に記載の累乗方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は特に、暗号アルゴリズムがチップ・カードのような電子デバイスに実装される暗号技術の分野で応用される安全かつコンパクトな累乗方法に関するものである。
【背景技術】
【０００２】
多くの暗号アルゴリズムは、ｘｄ（ｘ及びｄはそれぞれ所定の元及び指数）の形をとる代数群の累乗計算に基づいている。このことは特に、モジュロＮ（Ｎは２つの大きな素数の積）の整数環から成る乗法群の累乗に基づくＲＳＡ（Ｒｉｖｅｓｔ‐Ｓｈａｍｉｒ‐Ａｄｌｅｍａｎ）アルゴリズムに当てはまる。累乗の結果は、例えば暗号文又は復号文に対応することもあれば署名データ又は検証データに対応することもある。Ｅｌ  ＧａｍａｌアルゴリズムやＤｉｆｆｉｅ‐Ｈｅｌｌｍａｎアルゴリズムのような他の暗号アルゴリズムは、ある体から成る乗法群の累乗又はある楕円曲線の各点から成る群の累乗に依拠するものである。
【０００３】
そのようなアルゴリズムを実行するために提供される電子デバイスは、一方ではｘのｄ乗を実行する部分を、他方ではｘ及びｄの各値をそれ自体のメモリに収容しなければならない。
様々なタイプの累乗アルゴリズムが存在する。それらのアルゴリズムの内では特に「平方乗算」２進法（「Ｓｑｕａｒｅ  ａｎｄ  Ｍｕｌｔｉｐｌｙ」  ｂｉｎａｒｙ  ｍｅｔｈｏｄ）が知られている。
【０００４】
このアルゴリズムは元ｘ及び指数ｄを入力とし、その２進表現は次のとおりとなる。
｛ｄ［ｔ−１］，ｄ［ｔ−２］，．．．，ｄ［１］，ｄ［０］｝
上式で、ｄ［ｉ］は０又は１と等しく、元ｙ＝ｘ＾ｄ、即ちｘ．ｘ．．．．．ｘ（ｄ回）を返す。
【０００５】
「平方乗算」アルゴリズムは次のように表すことができる。
１）レジスタＲ０を１に初期化し、レジスタＲ１をｘに初期化する。
２）ｔ−１〜０のｉについて、
ａ）Ｒ０＝Ｒ０＾２（平方）；
ｂ）ｄ［ｉ］＝１であれば、
Ｒ０＝Ｒ０＊Ｒ１（乗算）；
を実行する。
３）Ｒ０を返す。
【０００６】
Ｍ，Ｍ３として知られるヤコビ法やスライディング・ウィンドウ法等の他の累乗アルゴリズムも知られている。しかしながら、これらのアルゴリズムは実装がより複雑である故に、チップ・カード・タイプの制限された電子構成部品にはあまり適さない。以下の説明において、電子構成部品は、メイン中央処理装置と、少なくとも３つのレジスタ（Ｒ０、Ｒ１、Ｒ２）を有するワーキング・メモリとを備える。
【０００７】
「平方乗算」アルゴリズム（及び上述の各アルゴリズム）は、計算デバイスによって実行される処理に含まれる操作対象データを覗き見ようとする攻撃に対抗するように適合された防護手段、換言すれば安全な防護手段を含んでいなければならない。特に、いわゆる隠れチャネルの単純攻撃又は差分攻撃（ｓｉｍｐｌｅ  ｏｒ  ｄｉｆｆｅｒｅｎｔｉａｌ  ｈｉｄｄｅｎ  ｃｈａｎｎｅｌ  ａｔｔａｃｋｓ）に対抗する防護手段が提供される。隠れチャネルの単純攻撃又は差分攻撃は、直接解析（単純攻撃）又は統計的解析（差分攻撃）を使用してデバイスの処理に含まれる操作対象データを明らかにすることで当該デバイスの外部から測定できるようになる物理量に基づいて行われる攻撃を意味するものとして理解されている。したがって、これらの攻撃によって極秘情報を明らかにすることが可能となる。これらの攻撃は特に、Ｐａｕｌ  Ｋｏｃｈｅｒの「Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ−ＣＲＹＰＴＯ’９９，  ｖｏｌ．  １９６６  ｄｅ  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ、Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ、３８８〜３９７頁（１９９９年））に開示されている。上記の物理量の内、攻撃目的で悪用される恐れがある物理量は、電流消費量や電磁界等である。これらの攻撃は、ビット操作、即ち個々の命令のビット処理がそれ自体の値に従って該当する物理量に特定のフィンガープリントを残すことを利用して行われる。
【０００８】
従来、上述の各累乗アルゴリズムは上記の各種攻撃が成功するのを防止する防護手段を含んでいる必要があった。例えば、「常時平方乗算」アルゴリズム（「Ｓｑｕａｒｅ  ａｎｄ  Ｍｕｌｔｉｐｌｙ  Ａｌｗａｙｓ」  ａｌｇｏｒｉｔｈｍ）は、「平方乗算」アルゴリズムの安全なバージョンであるが、現在処理されているビットの値を条件として演算が行われる故に、隠れチャネルの攻撃が可能となってしまう。
【０００９】
このアルゴリズムは元ｘ及び指数ｄを入力とし、その２進表現は次のとおりとなる。
｛ｄ［ｔ−１］，ｄ［ｔ−２］，．．．，ｄ［１］，ｄ［０］｝
上式で、ｄ［ｉ］は０又は１と等しく、元ｙ＝ｘ＾ｄ、即ちｘ．ｘ．．．．．ｘ（ｄ回）を返す。
【００１０】
「常時平方乗算」アルゴリズムは次のように表すことができる。
１）レジスタＲ０及びＲ１を１に初期化し、レジスタＲ２をｘに初期化する。
２）ｔ−１〜０のｉについて、
ａ）Ｒ０＝Ｒ０＾２（平方）；
ｂ）ｂ＝１−ｄ［ｉ］；Ｒｂ＝Ｒｂ＊Ｒ２（乗算）；
を実行する。
３）Ｒ０を返す。
【００１１】
「常時平方乗算」アルゴリズムは、ある種の単純攻撃（ＳＰＡ即ち単純電力解析として知られる攻撃）への耐性を有するが、追加的なレジスタが必要となる。Ｒ１レジスタは計算自体には必ずしも必要でないことに留意することが重要であり、例えば、当該レジスタは、指数ｄのビットｄ［ｉ］が繰り返しｉにおいて０と等しくなったときに（したがってｂ＝１となったときに）指数ｄのビットの値に関わらず繰り返しｉが平方算の後に乗算を行うステップから構成されるように、ダミー乗算を実行するために使用される。
【発明の開示】
【発明が解決しようとする課題】
【００１２】
残念ながら、ダミー演算の導入によってＳＰＡ攻撃への耐性がもたらされるが、別のタイプの弱点も生じる。Ｓｕｎｇ−Ｍｉｎｇ  Ｙｅｎ及びＭａｒｃ  Ｊｏｙｅの「Ｃｈｅｃｋｉｎｇ  ｂｅｆｏｒｅ  ｏｕｔｐｕｔ  ｍａｙ  ｎｏｔ  ｂｅ  ｅｎｏｕｇｈ  ａｇａｉｎｓｔ  ｆａｕｌｔ−ｂａｓｅｄ  ｃｒｙｐｔａｎａｌｙｓｉｓ」ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｃｏｍｐｕｔｅｒｓ、ｖｏｌ．４９、９６７〜９７０頁（２０００））では、あるクラスの攻撃が紹介されている（「セーフ・エラー攻撃」として知られる）。この概念を「常時平方乗算」アルゴリズムに適用すると、繰り返し１の乗法演算（ステップ２ｂ）の間にエラーが発生することになる。累乗ｙ＝ｘ＾ｄの結果が正しい場合には、当該乗法演算がダミー演算であり、したがってｄの対応ビットが０と等しい（即ちｄ［ｉ］＝０）ことを意味する。逆に、累乗の結果が正しくない場合には、ｄの対応ビットが１と等しい（即ちｄ［１］＝１）ことを意味する。したがって、攻撃者は指数ｄの値をビット単位で検索できるようになる。
【課題を解決するための手段】
【００１３】
本発明は、「常時平方乗算」アルゴリズムと同じ利点、即ちＳＰＡ攻撃への耐性を有するが、後者とは異なりいかなるダミー演算も実行しない累乗方法に関するものである。
さらに、本発明に係る方法は乗法演算だけを実行する顕著な特徴を有する。このような特徴は、ソフトウェアにおいてもハードウェアにおいても乗法演算だけを実行すれば済むので、チップ・カード等のより制限された環境では特に有益である。
【００１４】
したがって、平方演算が必要ない故に次の利点がもたらされる。
●ソフトウェア実装の場合にコード・メモリ（例えばＲＯＭやＥＥＰＲＯＭ等）のサイズが節約されること、又は
●ハードウェア実装の場合に回路サイズが節約されること。
【００１５】
ある楕円曲線の各点から成る群のように加法表記（ａｄｄｉｔｉｖｅ  ｎｏｔａｔｉｏｎ）による集合について、累乗はＱ＝ｄ．Ｐと記述され、この場合、Ｐ及びＱは加法表記（楕円曲線）による集合の元であり、ｄは指数であることに留意していただきたい。ある環又は体から成る加法群についても同じことが言える。以下では特に明記しない限り、従来の一般的な事例、即ち乗法表記（ｍｕｌｔｉｐｌｉｃａｔｉｖｅ  ｎｏｔａｔｉｏｎ）を使用する。
【発明を実施するための最良の形態】
【００１６】
より詳細には、本発明に係る累乗方法は、以下のアルゴリズムに基づいている。
このアルゴリズムは、元ｘ及び指数ｄを入力とし、その２進表現は次のとおりとなる。
｛ｄ［ｔ−１］，ｄ［ｔ−２］，．．．，ｄ［１］，ｄ［０］｝
上式で、ｄ［ｉ］は０又は１と等しく、元ｙ＝ｘ＾ｄ、即ちｘ．ｘ．．．．．ｘ（ｄ回）を返す。
【００１７】
本発明に係る方法は乗法表記で次のように表すことができる。
１）レジスタＲ０を１に初期化し、Ｒ１及びＲ２をｘに初期化する。
２）０〜ｔ−１のｉについて、
ａ）ｂ＝１−ｄ［ｉ］；
ｂ）Ｒｂ＝Ｒｂ＊Ｒ２（１回目の乗算）；
ｃ）Ｒ２＝Ｒ０＊Ｒ１（２回目の乗算）；
を実行する。
３）Ｒ０を返す。
【００１８】
言うまでもなく、前段のアルゴリズムは加法形式で記述することもできる。先述の場合と同様に、当該アルゴリズムは元Ｐ及び指数ｄを入力とし、その２進表現は次のとおりとなる。
｛ｄ［ｔ−１］，ｄ［ｔ−２］，．．．，ｄ［１］，ｄ［０］｝
上式で、ｄ［ｉ］は０又は１と等しく、元Ｑ＝ｄ．Ｐ、即ちＰ＋Ｐ．．．＋Ｐ（ｄ回）を返す。
【００１９】
この場合、本発明に係る方法は加法表記で次のように表すことができる。
１）レジスタＲ０を０に初期化し、Ｒ１及びＲ２をＰに初期化する。
２）０〜ｔ−１のｉについて、
ａ）ｂ＝１−ｄ［ｉ］；
ｂ）Ｒｂ＝Ｒｂ＋Ｒ２（１回目の加算）；
ｃ）Ｒ２＝Ｒ０＋Ｒ１（２回目の加算）；
を実行する。
３）Ｒ０を返す。
【００２０】
ある代数群において、単位元０の加算（乗法表記では単位元１の乗算と等価）は、隠れチャネル測定とは挙動が異なる可能性がある故に弱点が生じる可能性もある。この場合にも、本発明に係る方法であれば容易に適合させることができる。
加法表記による群に関する技法、例えばある楕円曲線の各点から成る集合について説明する。このアルゴリズムは、以下に示すとおりどのレジスタも値０で初期化されることがない（楕円曲線の無限遠点として知られる）繰り返しｉ＝１から開始する。
【００２１】
引き続き加法表記を使用すれば、本発明に係る変形形態を次のように表すことができる。
１）レジスタＲ０及びＲ１をＰに初期化し、レジスタＲ２を２．Ｐに初期化する。
２）１〜ｔ−１のｉについて、
ａ）ｂ＝１−ｄ［ｉ］；
ｂ）Ｒｂ＝Ｒｂ＋Ｒ２（１回目の加算）；
ｃ）Ｒ２＝Ｒ０＋Ｒ１（２回目の加算）；
を実行する。
３）ｄ［０］＝０であれば、Ｒ０＝Ｒ０−Ｐを実行する。
４）Ｒ０を返す。
【００２２】
本変形形態の初期化（上記のステップ１）では、レジスタＲ２が２．Ｐの値を含む必要があることに留意していただきたい。この値は事前に計算することも、累乗時にＱ＝ｄ．Ｐとして計算することもできる。後者の場合、２倍算ルーチンが利用可能でないときは、２．Ｐは主として（（Ｐ＋Ｔ）＋（Ｐ−Ｔ））を実行する加法によって計算することができ、この場合Ｔは、下位群のＰとは異なる既知の元であり、一般には公開鍵の一要素となる。
【００２３】
ＳＰＡ隠れチャネル攻撃及び「セーフ・エラー」攻撃に対抗する別個の防護手段を備えていなければならない従来の累乗アルゴリズムとは異なり、本発明の累乗方法及びその変形形態は、それらの攻撃への独自の耐性を有する利点がある。
さらに、特筆すべきことに、本発明の累乗方法及びその変形形態は、乗法演算（又は加法表記では加法演算）だけを実行する別の利点も有する。
【００２４】
本発明はいくつかの代替実施形態にも利用可能であることを理解していただきたい。以上、本発明をチップ・カード・タイプの環境の文脈で説明してきた。しかしながら、上記の教示はコンピュータ端末、ネットワーク通信端末、暗号計算を使用する他の任意の電子デバイス等他の応用例にも適用できることが理解されるだろう。
【国際調査報告】
2008525834.tif 000002
2008525834.tif 000003
2008525834.tif 000004
2008525834.tif 000005
2008525834.tif 000006
2008525834.tif 000007