(57)【要約】【課題】暗号指数アルゴリズムの指数である第一の正の整数ｎを再コード化する正則な方法を提供する。【解決手段】当該方法では、ｎよりも小さい整数ｓが選択され、整数ｎ’＝ｎ−ｓが定義され、整数ｎ'のｍ変数の表現は、ある整数ｍについて桁毎にｓのｍ変数の表現に加算され、ｎの再コード化された表現が生成される。また、装置１００及びコンピュータプログラムプロダクト１４０が提供される。【選択図】図１
2010072644.tif 000002
【特許請求の範囲】
【請求項１】
暗号指数アルゴリズムの指数である第一の正の整数ｎを再コード化する正則な方法であって、
当該方法は、プロセッサにおいて、
ｎよりも小さい第二の整数ｓを選択し、
第三の整数ｎ’＝ｎ−ｓを定義し、
第四の整数ｍについて、第三の整数ｎ'のｍ変数の表現を桁毎にｓのｍ変数の表現に加算して、ｎの再コード化された表現を生成する、
ステップを含むことを特徴とする方法。
【請求項２】
前記ｍは、ｍ＝２kである、
請求項２記載の方法。
【請求項３】
【数９】
2010072644.tif 000017
であり、前記Ｉはｎのｍ変数の長さを示す、
請求項１又は２記載の方法。
【請求項４】
０＜α＜ｍについて、ｓi＝αである、
請求項３記載の方法。
【請求項５】
α＝１である、
請求項４記載の方法。
【請求項６】
α＝ｍ−１である、
請求項４記載の方法。
【請求項７】
第一の正の整数ｎを正則に再コード化する装置であって、
当該装置はプロセッサを備え、
前記このプロセッサは、ｎよりも小さい第二の整数ｓを選択し、第三の整数ｎ’＝ｎ−ｓを定義し、第四の整数ｍについて、第三の整数ｎ'のｍ変数の表現を桁毎にｓのｍ変数の表現に加算して、ｎの再コード化された表現を生成する、
ことを特徴とする装置。
【請求項８】
プロセッサにより実行されたとき、請求項１乃至６の何れか記載の方法を実行する命令を記憶するコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、デジットリコーディング（digit  recoding）に関し、より詳細には、符号なしのデジットリコーディングに関する。
【背景技術】
【０００２】
このセクションは、以下に記載及び／又は特許請求される本発明の様々な態様に関連する様々な従来の態様を読者に紹介することが意図される。この説明は、本発明の様々な態様の良好な理解を容易にするため、読者に背景技術を提供することに役立つと考えられる。したがって、これらの説明は、この観点から読まれるべきであり、従来技術の承認として読まれるべきではない。
【０００３】
暗号指数アルゴリズム（cryptographic  exponentiation  algorithms）は、サイドチャンネル攻撃（side  channel  attack）に対して脆弱であることが示されている。（M.J.  Wiener,  editor  Advances  in  Cryptography  −  CRYPTO  ’99,  volume  1666  of  Lecture  Notes  in  Computer  Science,  pages  388−398,  Springer  Verlag  1999における）  “Differential  Power  Analysis”では、Paul  Kocher,  Joshua  Jaffe及びBenjamin  Junは、電力消費の観察を使用した攻撃を記載しており、電磁気放射の観察を使用した攻撃は、Karine  Gandolfi,  Christophe  Mourtel  及びFrancis  Olivier  による（C.K.  Koc,  D.Naccache及びC.  Paar,  editors,  Cryptographic  Hardware  and  Embedded  Systems  −  CHES2001,  volume  2162  of  Lecture  Notes  in  Computer  Science,  pages  251−261,  Springer  Verlag  2001における）“Electromagnetic  Analysis:  Concrete  Results”、並びに、Jean−Jacques  Quisquater及びDavid  Samydeによる（I.Attai及びT.P.  Jensen,  editors,  Smart  Card  Programming  and  Security  (E−Smart  2001),  volume  2140  of  Lacture  Notes  in  Computer  Science,  pages  200−210,  Springer  Verlag  2001における）“Electromagnetic  Analysis  (EMA):  Measures  and  Counter−Measures  for  Smart  Cards”において記載されている。
【０００４】
これらの攻撃は、単純電力解析（SPA:  Simple  Power  Analysis）及び単純電磁波解析（SEMA:  Simple  Electromagnetic  Analysis）と呼ばれ、必要とされる演算が指数（exponent）のビット単位の表現に依存するので、素朴にインプリメントされる指数アルゴリズムにおいて使用される指数を示す。
【０００５】
リコーディングアルゴリズム（recording  algorithm）は、指数を計算するために必要とされる演算数を減少するために開発されている。最も一般的に知られる例は、非隣接形式（NAF:  Non−Adjacent  Form）リコーディングであり、Ian  Blake,  Gadiel  Seroussi及びNigel  Smartによる“Elliptic  Curves  in  Cryptography”（volume  265  of  London  Mathematical  Society  Lecture  Note  Series.  Cambridge  University  Press.  1999）に記載される。NAFリコーディングは、｛−1,0,1｝における値を使用して指数のビットをリコーディングする。これにより、その後の指数アルゴリズムで必要とされる乗算の数が低減される。Donald  E.  Knuth  in  The  Art  of  Computer  Programming  （volume  2/  Seminumerical  Algorithms.  Addison−Wesley,  2nd  edition,  1981）により記載されるｍ変数（m−ary）リコーディングに一般化することができる。しかし、これらのリコーディングアルゴリズムは、指数アルゴリズムの効率を増加するために設計されており、サイドチャネル攻撃に対する耐性を高めるために設計されていない。
【０００６】
幾つかのリコーディングアルゴリズムが提案されている。  
Bodo  Moller.  “Parallelizable  Elliptic  Curve  Point  Multiplication  Method  with  Resistance  against  Side−Channel  Attacks”,  A.H.  Chan及びV.  Gligor,  editors,  Information  Security  (ISC  2002),  volume  2433  of  Lecture  Notes  in  Computer  Science,  pages  402−413,  Springer  Verlag  2002.
Bodo  Moller.  "Fractional  Windows（登録商標）  Revisited:  Improved  Signed−Digit  Representation  for  Efficient  Exponentiation”,  C.  Park及びS.  Chee,  editors,  Information  Security  and  Cryptography  −  ICISC  2004,  volume  3506  of  Lecture  Notes  in  Computer  Science,  pages  137−153,  Springer  Verlag  2004.
Katsuyuki  Okeya及びTsuyoshi  Takagi.  “A  More  Flexible  Countermeasure  against  Side−Channel  Attacks  Using  Window  Method”,  C.D.  Walter,  C.K.  Koc及びC.  Paar,  editors,  Cryptographic  Hardware  and  Embedded  Systems  −  CHES  2003,  volume  2779  of  Lecture  Notes  in  Computer  Science,  page  397−410,  Springer  Verlag  2003.
Katsuyuki  Okeya及びTsuyoshi  Takagi.  “The  Width−w  NAF  method  Provides  Small  Memory  and  Fast  Elliptic  Scalar  Multiplications  Secure  against  Side−Channel  Attacks”,  M.  Joye,  editor,  Topics  in  Cryptology  −  CT−  RSA  2003,  volume  2612  of  Lecture  Notes  in  Computer  Science,  pages  328−342,  Springer  Verlag  2003。
【０００７】
しかし、Yasuyuki  Sakai及びKouichi  Sakuraiにより（M.  Joye及びJ.J  Quisquater,  editors,  Cryptographic  Hardware  and  Embedded  Systems  −  CHES  2004,  volume  3156  of  Lecture  Notes  in  Computer  Science,  pages  298−311,  Springer  Verlag  2004における）“A  New  Attack  with  Side  Channel  Leakage  During  Exponent  Recoding  Computations”で述べられるように、正則の指数アルゴリズム（regular  exponentiation  algorithm）を達成するため、使用されるリコーディングアルゴリズムも正則である必要がある。正則なリコーディングアルゴリズムでは、アルゴリズムの評価の間にメインループにおけるテストが存在しない。
【０００８】
指数が生成されるときにリコーディングが実行されるべきであることが議論される場合、これは、たとえば指数がランダム値と結合される場合に不可能である。それは、リコーディングは指数の直前に実行される必要があるからである。ランダム値との結合は、Jean−Sebastien  Coronにより（C.K.  Koc及びC.  Paar,  editors,  Cryptographic  Hardware  and  Embedded  Systems  −  CHES  ’99,  volume  1717  of  Lecture  Notes  in  Computer  Science,  pages  292−302,  Springer  Verlag  1999における）“Resistance  against  Differential  power  Analysis  for  Elliptic  Curve  Cryptosystems”、並びに、Paul  Kocherによる（N.  Koblitz,  editor,  Advances  in  Cryptology  −  CRYPTO  ’96,  volume  1109  of  Lecture  Notes  in  Computer  Science,  pages  104−113,  Springer  Verlag  1996における）“Timing  Attacks  on  Implementations  of  Diffie−Hellman,  RSA,  DSS,  and  Other  Systems”に記載されるように、所定のサイドチャネル解析を防止するために行われる。
【０００９】
他のリコーディングアルゴリズムは、指数を正則にするために提案されている。Bodo  Mollerは、（G.  Davida及びY.  Frankel,  editors,  Information  Security  (ISC2001),  volume  2200  of  Lecture  Notes  in  Computer  Science,  pages  324−334,  Springer  Verlag  2001における）“Securing  Elliptic  Curve  Point  Multiplication  against  Side−Channel  Attacks”において、ｍ変数の指数のリコーディングアルゴリズムを記載している。ゼロに等しいそれぞれの桁は、−ｍで置き換えられ、次の最上位桁は、１だけインクリメントされる。これにより、セット{1,…,m−1}U{−m}に含まれる桁で再コード化される指数となる。ｍ変数の指数アルゴリズムと結合され、これは、ｘ−mが予め計算されるべきであることを意味する。この計算は楕円曲線に関して「容易」であるが、有限環の乗法群については容易ではない。
【００１０】
符号なしのバージョンのMollerのアルゴリズムは、camille  Vuillaume及びKatsuyuki  Okeyaによる（J.  Zhou,  M.  Yung及びF.  Bao,  editors,  Applied  Cryptography  and  Network  Security  −  ACNS  2006,  volume  3989  of  Lecture  Notes  in  Computer  Science,  pages  268−283,  Springer  Verlag  2006における）“Flexible  Exponentiation  With  Resistance  to  Side  Channel  Attacks”で記載されている。桁はセット{1,...,m}において再コード化され、それぞれのゼロの桁は、ｍで置き換えられ、次の桁は、１だけデクリメントされる。
【特許文献１】国際特許出願WO2008/069387A明細書
【発明の開示】
【発明が解決しようとする課題】
【００１１】
符号あり及び符号なしのバージョンのMollerアルゴリズムの問題点は、正則な様式で容易に実現することができないことである。
【００１２】
したがって、指数が正則の様式で簡単に再コード化される正則の指数のためのリコーディングアルゴリズムが必要とされる。
【課題を解決するための手段】
【００１３】
第一の態様では、本発明は、暗号指数アルゴリズムの指数である第一の正の整数ｎを再コード化する正則な方法に向けられる。プロセッサは、ｎよりも小さい第二の整数ｓを選択し、第三の整数ｎ’＝ｎ−ｓを定義し、第四の整数ｍについて、第三の整数ｎ'のｍ変数（ｍ−ａｒｙ）の表現を桁毎にｓのｍ変数の表現に加算して、ｎの再コード化された表現を生成する。
【００１４】
第一の好適な実施の形態では、ｍ＝２kである。
【００１５】
第二の好適な実施の形態では、
【数１】
2010072644.tif 000003
であり、この場合、Ｉはｎのｍ変数の長さを示す。０＜α＜ｍについて、ｓi＝αであり、この場合、好ましくはα＝１又はα＝ｍ−１である。
【００１６】
第二の態様では、本発明は、第一の正の整数ｎを正則に再コード化する装置に向けられる。本装置は、プロセッサを備えており、このプロセッサは、ｎよりも小さい第二の整数ｓを選択し、第三の整数ｎ’＝ｎ−ｓを定義し、第四の整数ｍについて、第三の整数ｎ'のｍ変数（m−ary）の表現を桁毎にｓのｍ変数の表現に加算して、ｎの再コード化された表現を生成する。
【００１７】
第三の態様では、本発明は、プロセッサにより実行されたとき、本発明の第一の態様の方法を実行する命令を記憶するコンピュータプログラムプロダクトに向けられる。
【図面の簡単な説明】
【００１８】
以下、添付図面を参照して、限定するものではない例を通して、本発明の好適な特徴が記載される。
【図１】本発明の好適な実施の形態に係るデジットリコーディングの装置を示すブロック図である。  図面において、表現されたブロックは機能的なエンティティであり、これらは物理的に個別のエンティティに必ずしも対応していない場合がある。これらの機能的なエンティティは、ハードウェア、ソフトウェア、又は、ソフトウェア及びハードウェアの組み合わせとして実現され、さらに、１以上の集積回路で実現される場合がある。
【発明を実施するための最良の形態】
【００１９】
図１は、桁、特に指数アルゴリズムで使用されるべき指数の桁を再コード化する装置１００を示す。本装置１００は、以下に記載される実施の形態のリコーディングアルゴリズムの計算を実施するコンピュータプログラムを実行する少なくとも１つのプロセッサ１１０（以下、プロセッサ）を有する。なお、プロセッサ１１０は、ハードウェア、又はソフトウェアとハードウェアとの組み合わせで実現される場合もある。本装置１００は、たとえばプロセッサ１１０からの中間の計算結果のようなデータを記憶するメモリ１２０を更に有する。また、装置１００は、他の装置（図示せず）とのインタラクション用の少なくとも１つのインタフェース１３０（以下、「インタフェース」）を有する。図１は、プロセッサ１１０により実行されたとき、本発明の方法の２つの実施の形態の何れかに係るリコーディングアルゴリズムを実行するコンピュータプログラムを記憶する、たとえばＣＤ−ＲＯＭのようなコンピュータプログラムプロダクト１４０を更に例示する。
【００２０】
指数において、（乗算で書かれた）群において、整数ｎ及びエレメントｘについてｚ＝ｘnが計算される。
【００２１】
【数２】
2010072644.tif 000004
を基数ｍ（典型的に、ｍ＝２k）におけるｎの展開を示し、この場合、Ｉはｎのｍ変数の長さである。正の整数ｓ＜ｎを取り、ｎ’＝ｎ−ｓを定義する。
【００２２】
【数３】
2010072644.tif 000005
がそれぞれｎ’及びｓのｍの展開を示す場合、ｘn＝ｘn’+sに従い、この場合、
【数４】
2010072644.tif 000006
であり、この場合、ｋi＝ｄ’i＋ｓiである。
【００２３】
基数ｍにおけるｓの最上位桁をゼロと定義する場合、基数ｍにおけるｎ’の最上位桁（すあなわちｋI−1）は、ゼロよりも大きいか又はゼロに等しい。これが当てはまらない場合、再コード化は、符号なしではなく、従って、計算の反転が高価な群にとって適切ではない。
【００２４】
［第一の好適な実施の形態］
αを０＜α＜ｍを満たす整数とする。
【００２５】
【数５】
2010072644.tif 000007
を選択する。これは、ｓの全ての桁を同じ値、すなわちαに設定することとして見られる場合がある。ｎ'i∈｛０，．．．，ｍ−１｝であるので、ｋi∈｛α，．．．，α＋（ｍ−１）｝に従う。次いで、以下のアルゴリズムが再コード化のために使用される。
【００２６】
入力：ｎ≧１，ｍ＝２k，Ｉ（ｎのｍ変数の長さ）。  
出力：ｎ＝（ｋI−1，．．．，ｋ0）ｍ，ｋi∈｛α，．．．，α＋（ｍ−１）｝、０≦ｉ≦Ｉ−２．
アルゴリズム：
【００２７】
【表１】
2010072644.tif 000008
αについて第一の好適な選択は１である。これは、再コード化された桁について小さな値となるからである。αの第二の好適な値はｍ−１である。これは、ｓ＝ｍI−1−１を与えるからである（すなわち、１に設定される一連のｋ（Ｉ−１））。
【００２８】
以下、２つの例は、第一の好適な実施の形態を説明する。２つの例について、パラメータは、以下の値をとる。  
ｋ＝２
ｍ＝４
ｎ＝７３＝（1,0,2,1）4＝１・４0＋２・４1＋０・４2＋１・４3
Ｉ＝４。
【００２９】
第一の例ではα＝１であり、第二の例ではα＝ｍ−１＝３である。
【００３０】
［第一の実施の形態の第一の例（α＝１）］
【００３１】
【表２】
2010072644.tif 000009
期待されるように、再コード化されたｎは、オリジナルのｎに等しい。
【００３２】
［第一の実施の形態の第一の例（α＝ｍ−１＝３）］
【００３３】
【表３】
2010072644.tif 000010
期待されるように、再コード化されたｎは、オリジナルのｎに等しい。
【００３４】
なお、第一の実施の形態に係るアルゴリズムは実現するのが容易であるが、前もって（Ｉの）ｎのｍ変数の情報を必要とする。これは問題となる場合があるので、実現するのが僅かに複雑になるが、第二の好適な実施の形態はこの問題を克服する。
【００３５】
［第二の好適な実施の形態］
減算ステップｎ’＝ｎ−ｓを更に詳細に見る場合、以下の式を設定する。
【００３６】
【数６】
2010072644.tif 000011
この場合、“borrow”は０に初期化され、すなわちγ0＝０である。これは、学校で習得する古典的な減算アルゴリズムである。ｄi，ｓi∈｛０，．．．，ｍ−１｝であるので、これにより、ｋi＝ｄ'i+ｓiが与えられ、これはｄi＋γi≧ｓiの場合にｄi＋γiに等しく、さもなければｄi＋γi＋ｍに等しい。
【００３７】
したがって、ｓi≠０の任意の選択について、ｄi∈｛０,１｝のとき、ｋiについて非ゼロの値となる。第一の好適な実施の形態におけるように、０＜α＜ｍについて
【数７】
2010072644.tif 000012
である。さらに、符号なしの計算のみを使用するため、γ'i＝γi＋１∈｛０,１｝である。
【００３８】
【数８】
2010072644.tif 000013
入力：ｎ≧１、ｍ＝２k、０＜α＜ｍ
出力：ｎ＝（ｋl−1，．．．，ｋ0）ｍ，ｋi∈｛α，．．．，α＋（ｍ−１）｝、０≦ｉ≦Ｉ−２
アルゴリズム：
【００３９】
【表４】
2010072644.tif 000014
第一の好適な実施の形態におけるように、αの好適な選択は１及びｍ−１である。
【００４０】
以下、２つの例は、第二の好適な実施の形態を示す。２つの例について、パラメータは以下の値をとる。
【００４１】
ｋ＝２
ｍ＝４
ｎ＝７３＝（1,0,2,1）4＝１・４0＋２・４1＋０・４2＋１・４3
第一の例ではα＝１であり、第二の例ではα＝ｍ−１＝３である。
【００４２】
［第二の実施の形態の第一の例（α＝１）］
【００４３】
【表５】
2010072644.tif 000015
期待されるように、再コード化されたｎは、オリジナルのｎに等しい。
【００４４】
［第二の実施の形態の第二の例（α＝ｍ−１＝３）］
【００４５】
【表６】
2010072644.tif 000016
期待されるように、再コード化されたｎは、オリジナルのｎに等しい。
【００４６】
両方の実施の形態は、予想通りに、同じ入力について同じ再コード化された数字を与える。たとえば、第一の例は、両方の実施の形態について（４,２,１）を与え、第二の例は、両方の実施の形態について（３,５,５）を与える。
【００４７】
また、両方の実施の形態は、メインループ内でテストが存在しないので正則であり、第一の実施の形態ではｆｏｒループ内でテストが存在せず、第二の実施の形態ではｗｈｉｌｅループ内でテストが存在しない。
【００４８】
本発明は、正の整数の正則なリコーディングを可能にすることを理解されたい。
【００４９】
明細書及び（必要に応じて）特許請求の範囲及び図面で開示されるそれぞれの特徴は、独立に提供されるか、又は任意の適切な組み合わせで提供される場合がある。ハードウェアで実現されるように記載される特徴は、ソフトウェアで実現される場合もあり、逆も然りである。コネクションは、必要に応じて、ワイヤレスコネクション又はワイヤドコネクションとして実現される場合があり、必ずしもダイレクトコネクション又は専用コネクションである必要はない。
【符号の説明】
【００５０】
１００：装置
１１０：プロセッサ
１２０：メモリ
１３０：インタフェース
１４０：コンピュータプログラムプロダクト
【図１】
2010072644.tif 000018
【外国語明細書】
2010072644000001.pdf