(57)【要約】  1つの特徴は、デジタル署名を生成する際に使用するための楕円曲線(EC)点乗算に関する。一態様では、EC点乗算とともに使用するための楕円曲線上で、オーダ(n)の基点(P)のスカラー乗数(k)が選択される。整数値(r)が次いで、範囲内で取得された(r)の特定の値にかかわらず、整数乗数(r)とオーダ(n)との積と合計されたスカラー乗数(k)を使用して実施されるEC点乗算手順が、スカラー乗数(k)の値に依存せずにデバイスリソースを消費するように制約された値の範囲内からランダムに生成され、それにより、サイドチャネル漏洩が削減または排除される。これは、k+(r*n)の最上位ビットのビット位置が偶数となり、特定の楕円曲線に対して固定されるように、rについての値の範囲を決定することによって遂行されてもよい。
2017511902.tif 000002
【特許請求の範囲】
【請求項１】
デバイスによって動作可能な、楕円曲線点乗算のための方法であって、
一連のビットとして表される値に対して作用する楕円曲線点乗算手順とともに使用するための、楕円曲線上でのオーダ(n)の基点(P)のスカラー乗数(k)を取得するステップと、
値の範囲内で取得された(r)の特定の値にかかわらず、整数乗数(r)と前記オーダ(n)との積と合計された前記スカラー乗数(k)を使用して実施される楕円曲線点乗算手順が、前記スカラー乗数(k)の値に依存せずにデバイスリソースを消費するような前記整数乗数(r)についての前記値の範囲を決定するステップと、
前記値の範囲内から整数乗数(r)を取得するステップと、
前記スカラー乗数(k)、前記整数乗数(r)および前記オーダ(n)を使用して、少なくとも1つの楕円曲線点乗算手順を実施するステップと
を含む、方法。
【請求項２】
前記整数乗数(r)についての前記値の範囲を決定するステップは、前記値の範囲内で取得された(r)の前記特定の値にかかわらず、前記整数乗数(r)と前記オーダ(n)との前記積と合計された前記スカラー乗数(k)の最上位ビットのビット位置が偶数であり、かつ特定の楕円曲線に対して固定されるように、前記値の範囲を決定するステップを含む、請求項1に記載の方法。
【請求項３】
前記整数乗数(r)についての前記値の範囲を決定するステップは、
RL=floor(mrecip*2(j-m-1)+1)を決定することによって、前記値の範囲の下端(RL)を決定するステップであって、mrecipは前記オーダ(n)の近似逆数であり、mは前記オーダ(n)を表す値の中のビットの数であり、jは前記スカラー乗数(k)と、前記整数乗数(r)と前記オーダ(n)との前記積との和を表す値(k+(r*n))の中のビットの数である、ステップと、
RU=floor(mrecip*2(j-m)-2)を決定することによって、前記値の範囲の上端(RU)を決定するステップと
をさらに含む、請求項2に記載の方法。
【請求項４】
前記値の範囲内から前記整数乗数(r)を取得するステップは、ランダムおよび擬似ランダム選択のうちの1つまたは複数を使用して実施される、請求項1に記載の方法。
【請求項５】
再コード化値を生じるために前記整数乗数(r)と前記オーダ(n)との前記積と合計された前記スカラー乗数(k)を再コード化するステップをさらに含む、請求項1に記載の方法。
【請求項６】
前記再コード化値に基づいてZを処理するために、Pに基づく事前計算値を適用することによって前記再コード化値および値Zを使用する楕円曲線点乗算論理を適用するステップをさらに含む、請求項5に記載の方法。
【請求項７】
処理回路を備えるデバイスであって、前記処理回路は、
一連のビットとして表される値に対して作用する楕円曲線点乗算手順とともに使用するための、楕円曲線上でのオーダ(n)の基点(P)のスカラー乗数(k)を取得し、
値の範囲内で取得された(r)の特定の値にかかわらず、整数乗数(r)と前記オーダ(n)との積と合計された前記スカラー乗数(k)を使用して実施される楕円曲線点乗算手順が、前記スカラー乗数(k)の値に依存せずにデバイスリソースを消費するような前記整数乗数(r)についての前記値の範囲を決定し、
前記値の範囲内から整数乗数(r)を取得し、
前記スカラー乗数(k)、前記整数乗数(r)および前記オーダ(n)を使用して、少なくとも1つの楕円曲線点乗算手順を実施する
ように構成される、デバイス。
【請求項８】
前記処理回路は、前記値の範囲内で取得された(r)の前記特定の値にかかわらず、前記整数乗数(r)と前記オーダ(n)との前記積と合計された前記スカラー乗数(k)の最上位ビットのビット位置が偶数であり、かつ特定の楕円曲線に対して固定されるように、前記整数乗数(r)についての前記値の範囲を決定するようにさらに構成される、請求項7に記載のデバイス。
【請求項９】
前記処理回路は、
RL=floor(mrecip*2(j-m-1)+1)を決定することによって、前記値の範囲の下端(RL)を決定することであって、mrecipは前記オーダ(n)の近似逆数であり、mは前記オーダ(n)を表す値の中のビットの数であり、jは前記スカラー乗数(k)と、前記整数乗数(r)と前記オーダ(n)との前記積との和を表す値(k+(r*n))の中のビットの数である、決定することと、
RU=floor(mrecip*2(j-m)-2)を決定することによって、前記値の範囲の上端(RU)を決定することと
によって、前記整数乗数(r)についての前記値の範囲を決定するようにさらに構成される、請求項8に記載のデバイス。
【請求項１０】
前記処理回路は、ランダムおよび擬似ランダム選択のうちの1つまたは複数を使用して、前記整数乗数(r)を、前記値の範囲内から取得するようにさらに構成される、請求項7に記載のデバイス。
【請求項１１】
前記処理回路は、再コード化値を生じるために前記整数乗数(r)と前記オーダ(n)との前記積と合計された前記スカラー乗数(k)を再コード化するようにさらに構成される、請求項7に記載のデバイス。
【請求項１２】
前記処理回路は、前記再コード化値に基づいてZを処理するために、Pに基づく事前計算値を適用することによって前記再コード化値および値Zを使用する楕円曲線点乗算論理を適用するようにさらに構成される、請求項11に記載のデバイス。
【請求項１３】
一連のビットとして表される値に対して作用する楕円曲線点乗算手順とともに使用するための、楕円曲線上でのオーダ(n)の基点(P)のスカラー乗数(k)を取得するための手段と、
値の範囲内で取得された(r)の特定の値にかかわらず、整数乗数(r)と前記オーダ(n)との積と合計された前記スカラー乗数(k)を使用して実施される楕円曲線点乗算手順が、前記スカラー乗数(k)の値に依存せずにデバイスリソースを消費するような前記整数乗数(r)についての前記値の範囲を決定するための手段と、
前記値の範囲内から整数乗数(r)を取得するための手段と、
前記スカラー乗数(k)、前記整数乗数(r)および前記オーダ(n)を使用して、少なくとも1つの楕円曲線点乗算手順を実施するための手段と
を備える、デバイス。
【請求項１４】
前記整数乗数(r)についての前記値の範囲を決定するための前記手段は、前記値の範囲内で取得された(r)の前記特定の値にかかわらず、前記整数乗数(r)と前記オーダ(n)との前記積と合計された前記スカラー乗数(k)の最上位ビットのビット位置が偶数であり、かつ特定の楕円曲線に対して固定されるように、前記値の範囲を決定するための手段を含む、請求項13に記載のデバイス。
【請求項１５】
前記整数乗数(r)についての前記値の範囲を決定するための前記手段は、
RL=floor(mrecip*2(j-m-1)+1)を決定することによって、前記値の範囲の下端(RL)を決定するための手段であって、mrecipは前記オーダ(n)の近似逆数であり、mは前記オーダ(n)を表す値の中のビットの数であり、jは前記スカラー乗数(k)と、前記整数乗数(r)と前記オーダ(n)の前記積との和を表す値(k+(r*n))の中のビットの数である、手段と、
RU=floor(mrecip*2(j-m)-2)を決定することによって、前記値の範囲の上端(RU)を決定するための手段と
をさらに備える、請求項14に記載のデバイス。
【請求項１６】
前記値の範囲内から前記整数乗数(r)を取得するための前記手段は、ランダムおよび擬似ランダム選択のうちの1つまたは複数を実施するための手段を備える、請求項13に記載のデバイス。
【請求項１７】
再コード化値を生じるために前記整数乗数(r)と前記オーダ(n)の前記積と合計された前記スカラー乗数(k)を再コード化するための手段をさらに備える、請求項13に記載のデバイス。
【請求項１８】
前記再コード化値に基づいてZを処理するために、Pに基づく事前計算値を適用することによって前記再コード化値および値Zを使用する楕円曲線点乗算論理を適用するための手段をさらに備える、請求項17に記載のデバイス。
【請求項１９】
1つまたは複数の命令を有する機械可読記憶媒体であって、前記1つまたは複数の命令は、少なくとも1つの処理回路によって実行されると、前記少なくとも1つの処理回路に、
一連のビットとして表される値に対して作用する楕円曲線点乗算手順とともに使用するための、楕円曲線上でのオーダ(n)の基点(P)のスカラー乗数(k)を取得させ、
値の範囲内で取得された(r)の特定の値にかかわらず、整数乗数(r)と前記オーダ(n)との積と合計された前記スカラー乗数(k)を使用して実施される楕円曲線点乗算手順が、前記スカラー乗数(k)の値に依存せずにデバイスリソースを消費するような前記整数乗数(r)についての前記値の範囲を決定させ、
前記値の範囲内から整数乗数(r)を取得させ、
前記スカラー乗数(k)、前記整数乗数(r)および前記オーダ(n)を使用して、少なくとも1つの楕円曲線点乗算手順を実施させる
、機械可読記憶媒体。
【請求項２０】
前記処理回路に、前記値の範囲内で取得された(r)の前記特定の値にかかわらず、前記整数乗数(r)と前記オーダ(n)の前記積と合計された前記スカラー乗数(k)の最上位ビットのビット位置が偶数であり、かつ特定の楕円曲線に対して固定されるように、前記整数乗数(r)についての前記値の範囲を決定させるための命令をさらに含む、請求項19に記載の機械可読記憶媒体。
【請求項２１】
前記処理回路に、
RL=floor(mrecip*2(j-m-1)+1)を決定することによって、前記値の範囲の下端(RL)を決定することであって、mrecipは前記オーダ(n)の近似逆数であり、mは前記オーダ(n)を表す値の中のビットの数であり、jは前記スカラー乗数(k)と、前記整数乗数(r)と前記オーダ(n)の前記積との和を表す値(k+(r*n))の中のビットの数である、決定することと、
RU=floor(mrecip*2(j-m)-2)を決定することによって、前記値の範囲の上端(RU)を決定することと
によって、前記整数乗数(r)についての前記値の範囲を決定させるための命令をさらに含む、請求項20に記載の機械可読記憶媒体。
【請求項２２】
前記処理回路に、ランダムおよび擬似ランダム選択のうちの1つまたは複数を使用して、前記値の範囲内から前記整数乗数(r)を取得させるための命令をさらに含む、請求項19に記載の機械可読記憶媒体。
【請求項２３】
前記処理回路に、再コード化値を生じるために前記整数乗数(r)と前記オーダ(n)の前記積と合計された前記スカラー乗数(k)を再コード化させるための命令をさらに含む、請求項19に記載の機械可読記憶媒体。
【請求項２４】
前記処理回路に、前記再コード化値に基づいてZを処理するために、Pに基づく事前計算値を適用することによって前記再コード化値および値Zを使用する楕円曲線点乗算論理を適用させるための命令をさらに含む、請求項23に記載の機械可読記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願の相互参照
本出願は、内容全体が参照によって本明細書に組み込まれる、2014年4月4日に米国特許商標庁に出願された、米国非仮特許出願第14/245,732号の優先権および利益を主張する。
【０００２】
様々な特徴は楕円曲線暗号に関し、詳細には、デジタル署名などを生成する際に使用するための楕円曲線点乗算手順に関する。
【背景技術】
【０００３】
楕円曲線(EC)点乗算は、秘密にされることを意図している乗数、すなわちk(dと呼ばれることもある)を受け付ける、EC暗号において使用される手順である。EC点乗算は、たとえば、オンライン取引をセキュアにする際に使用するためのデジタル署名を作成するための手順の一部として使用することができる。攻撃者によって、サイドチャネル漏洩を悪用することによって秘密乗数kに関する情報を取得するために、様々な技法が使用され得る。たとえば、EC点乗算を実施するデバイスによって消費される電力の量または演算を実施するデバイスによって費やされる時間の量により、可能性として、kについての情報が暴露される場合がある。特に、ゼロを伴ういくつかの演算は、他の値を利用するものよりも少ないリソースを消費するので、従来のEC点乗算手順には問題が起こる場合があり、結果として、kに関する情報が漏洩する可能性がある。そのような漏洩に対処するための1つの技法は、nのランダム倍数(ここでnは、基点のオーダである)をkに加算するものである。つまり、単なるkよりもk+(r*n)が利用され、ここでrは乱数である。ただし、この技法は、ゼロを伴う演算が、他の値に対する演算と同じ時間量を消費することを保証するものではなく、したがって、情報漏洩が依然として起こり得る。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】米国標準規格X9.62-2005、Public Key Cryptography for the Financial Services Industry, The Elliptic Curve Digital Signature Algorithm (ECDSA)、2005年11月16日
【発明の概要】
【発明が解決しようとする課題】
【０００５】
したがって、デジタル署名を生成する際に使用するための、または他の目的のための、改良されたEC点乗算手順を提供する必要がある。
【課題を解決するための手段】
【０００６】
デバイスによって動作可能な、楕円曲線点乗算のための方法は、一連のビットとして表される値に対して作用する楕円曲線点乗算手順とともに使用するための、楕円曲線上でのオーダ(n)の基点(P)のスカラー乗数(k)を取得するステップと、値の範囲内で取得された(r)の特定の値にかかわらず、整数乗数(r)とオーダ(n)の積と合計されたスカラー乗数(k)を使用して実施される楕円曲線点乗算手順が、スカラー乗数(k)の値に依存せずにデバイスリソースを消費するような整数乗数(r)についての値の範囲を決定するステップと、値の範囲内から整数乗数(r)を取得するステップと、スカラー乗数(k)、整数乗数(r)およびオーダ(n)を使用して、少なくとも1つの楕円曲線点乗算手順を実施するステップとを含む。
【０００７】
別の態様では、デバイスは、一連のビットとして表される値に対して作用する楕円曲線点乗算手順とともに使用するための、楕円曲線上でのオーダ(n)の基点(P)のスカラー乗数(k)を取得し、値の範囲内で取得された(r)の特定の値にかかわらず、整数乗数(r)とオーダ(n)の積と合計されたスカラー乗数(k)を使用して実施される楕円曲線点乗算手順が、スカラー乗数(k)の値に依存せずにデバイスリソースを消費するような整数乗数(r)についての値の範囲を決定し、値の範囲内から整数乗数(r)を取得し、スカラー乗数(k)、整数乗数(r)およびオーダ(n)を使用して、少なくとも1つの楕円曲線点乗算手順を実施するように構成される処理回路を含む。
【０００８】
さらに別の態様では、デバイスは、一連のビットとして表される値に対して作用する楕円曲線点乗算手順とともに使用するための、楕円曲線上でのオーダ(n)の基点(P)のスカラー乗数(k)を取得するための手段と、値の範囲内で取得された(r)の特定の値にかかわらず、整数乗数(r)とオーダ(n)の積と合計されたスカラー乗数(k)を使用して実施される楕円曲線点乗算手順が、スカラー乗数(k)の値に依存せずにデバイスリソースを消費するような整数乗数(r)についての値の範囲を決定するための手段と、値の範囲内から整数乗数(r)を取得するための手段と、スカラー乗数(k)、整数乗数(r)およびオーダ(n)を使用して、少なくとも1つの楕円曲線点乗算手順を実施するための手段とを含む。
【０００９】
またさらに別の態様では、機械可読記憶媒体は、1つまたは複数の命令を有し、命令は、少なくとも1つの処理回路によって実行されると、少なくとも1つの処理回路に、一連のビットとして表される値に対して作用する楕円曲線点乗算手順とともに使用するための、楕円曲線上でのオーダ(n)の基点(P)のスカラー乗数(k)を取得させ、値の範囲内で取得された(r)の特定の値にかかわらず、整数乗数(r)とオーダ(n)の積と合計されたスカラー乗数(k)を使用して実施される楕円曲線点乗算手順が、スカラー乗数(k)の値に依存せずにデバイスリソースを消費するような整数乗数(r)についての値の範囲を決定させ、値の範囲内から整数乗数(r)を取得させ、スカラー乗数(k)、整数乗数(r)およびオーダ(n)を使用して、少なくとも1つの楕円曲線点乗算手順を実施させる。
【図面の簡単な説明】
【００１０】
【図１】サイドチャネル攻撃を受ける例示的な楕円曲線暗号(ECC)システムを示す図である。
【図２】システムがECCベースのスマートカードリーダを含む、サイドチャネル攻撃を受ける別の例示的なECCシステムを示す図である。
【図３】サイドチャネル攻撃に対して脆弱なEC点乗算とともに使用するための例示的な再コード化手順を示す図である。
【図４】サイドチャネル攻撃に対して脆弱なEC点乗算とともに使用するための別の例示的な再コード化手順を示す図である。
【図５】いくつかの種類のサイドチャネル攻撃を実質的に排除する、EC点乗算とともに使用するための例示的な手順の概要を示す図である。
【図６】図5の例示的な手順の態様をさらに示す図である。
【図７】図5の例示的な手順のさらなる態様をさらに示す図である。
【図８】いくつかの種類のサイドチャネル攻撃を削減するか、または実質的に排除する構成要素を利用する例示的なECC処理デバイスを示す図である。
【図９】図8のデバイスとともに使用するための例示的な手順を要約する図である。
【図１０】図8のデバイスとともに使用するための追加の例示的な手順を示す図である。
【図１１】図1〜図10の様々なシステムおよびデバイスの構成要素が組み込まれ得る例示的な処理システムを示す図である。
【発明を実施するための形態】
【００１１】
以下の説明では、本開示の様々な態様を完全に理解することが可能なように具体的な詳細を示す。しかしながら、それらの態様が、これらの具体的な詳細なしに実施でき得ることが、当業者には理解されよう。たとえば、態様を不必要に詳しく説明して曖昧にすることを避けるために、回路がブロック図で示される場合がある。他の事例では、よく知られている回路、構造、および技術は、本開示の態様を不明瞭にしないために、詳細には示されていない場合がある。
【００１２】
「例示的な」という言葉は、例、事例、または例示として機能することを意味するように本明細書で使用される。「例示的な」として本明細書において説明するいかなる実装形態または態様も、必ずしも本開示の他の態様よりも好ましいか、または有利であると解釈されるべきではない。同様に、「複数の態様」という用語は、本開示のすべての態様が、論じられる特徴、利点、または動作モードを含むことを必要としない。
【００１３】
概説
いくつかの新規性のある特徴は、楕円曲線(EC)点乗算およびEC暗号(ECC)とともに使用するためのデバイスおよび方法に関する。新規性のある特徴は、デジタル署名を生成し、処理し、または検証する際に使用するためのデバイスにおいて使用することができるが、広範なシステム、装置およびデバイスにおいて、ならびに様々な目標を達成するために適用可能である。
【００１４】
一態様では、一連のビットとして表される値に対して作用するEC点乗算手順とともに使用するための楕円曲線上で、オーダ(n)の基点(P)のスカラー乗数(k)が選択される。次いで、範囲内で取得された(r)の特定の値にかかわらず、k+(r*n)を使用して実施されるEC点乗算手順がスカラー乗数(k)の値に依存せずにデバイスリソースを消費することになる、すなわち、時間および電力消費が均一になるように制約された値の範囲内から、整数乗数(r)がランダムまたは擬似ランダムに生成される。これは、範囲内で取得されたrの特定の値にかかわらず、k'=k+(r*n)の最上位ビットのビット位置が偶数になり、かつEC点乗算手順中は特定の楕円曲線に対して固定されるように、rについての値の範囲を指定することによって遂行することができる。rについての値の範囲は、RL=floor(mrecip*2(j-m-1)+1)に基づいて値の範囲の下端(RL)を決定することであって、ここで、mrecipはEC点乗算手順の法の近似逆数であり(ここでの例では、法は基点のオーダ(n)である)、mはオーダnを表す値の中のビットの数であり、jはk'を表す値の中のビットの数である、決定すること、次いで、RU=floor(mrecip*2(j-m)-2)に基づいて値の範囲の上端(RU)を決定することによって、指定することができる。整数乗数rは次いで、たとえば、範囲内の値をランダムまたは擬似ランダムに選択することによって、この範囲内から取得される。(値rは、本明細書では、スカラー乗数(scalar multiplier)kと区別するために「整数乗数(integer multiplier)」と呼ばれることに留意されたい。他の用語または記号が代わりに使用されてもよい。)
【００１５】
EC点乗算の一連の基本演算(“DOUBLE”および“ADD”)は、これらの例において一定である(かつ、どの特定のECC曲線に対しても一定数の周期だけ適用される)ので、上記手順は、単純な電力分析およびタイミング攻撃をかなり難しくさせる。単純な電力分析が、より多くの情報を抽出するために信号加算平均と組み合わされてもよいが、これは、異なるk'値を有するほぼすべてのトレースによって阻止される。いくつかのECC手順では、ランダム値の導入が、差分電力分析を容易にし得るが、攻撃者はrを知らないので、ここでは疑わしいことに留意されたい。
【００１６】
例示的なハードウェア環境および手順
図1は、サイドチャネル攻撃を受ける例示的なECCシステム100を示す。手短に言うと、メッセージ102がECC署名デバイス106によって処理され、デバイス106は、秘密鍵104を使用するEC曲線乗算手順を利用することができる。署名付きメッセージ108が次いで、概してセキュアでないチャネル109を介して転送され、チャネル109中で、公開鍵110を使用してECC署名検証デバイス112によって、YES/NO検証114を生じるように処理される。そのようなシステムは、サイドチャネル攻撃デバイスまたはシステム116に対して脆弱な場合があり、デバイスまたはシステム116は、電力シグネチャおよびタイミング情報を取得するために、電源122によって与えられる電力信号120を監視することなどによって、ECC署名デバイス106に関連付けられた電力およびタイミング情報118を監視する。署名デバイス106によって利用されるECC手順がサイドチャネル攻撃に対して脆弱である(すなわち、ECC署名デバイスが情報を漏洩する)場合、秘密鍵は、攻撃者または他の悪意のある存在(たとえば、ハッカー)によって取得される場合がある。
【００１７】
図2は、サイドチャネル攻撃を受ける別の例示的なECCシステム200を示し、ここで、攻撃されているシステムは、1つまたは複数のスマートカード204を受理するECCベースのスマートカードリーダ206である。やはり、電力およびタイミング情報218が、サイドチャネル攻撃システムによる分析のために、電源222によって与えられる電力信号220から取得されてよく、攻撃システムは、この例では、電力測定オシロスコープ216およびサイドチャネルコンピュータ/アナライザ217を含む。またさらに、この例では、電磁誘導(EMI)信号、音響信号など219が、コンピュータ/アナライザ217による分析のために、適切なセンサーまたは検出器221によって取得され得る。ユニバーサルシリアルバス(USB)デバイス、スマートフォンなどに対して、類似した攻撃が開始される場合がある。
【００１８】
図1および図2に示すようなサイドチャネル攻撃は、部分的には、ECCシステムによって利用されるEC点乗算手順の脆弱性によって可能になる。概して、EC点乗算は、楕円曲線沿いの点の反復スカラー加算のための手順に関し、ECCにおいて、たとえば、トラップドア関数、すなわち一方の方向では容易に計算することができるが、1つもしくは複数の秘密鍵または他のタイプの特殊情報がないと、反対方向では計算するのが難しい関数をもたらすために利用することができる。EC点乗算は、ECデジタル署名アルゴリズム(ECDSA)に従って生成され、図1および図2のようなシステムによって活用される署名などのデジタル署名の生成および処理において利用することができる。さらなる情報については、たとえば、米国標準規格X9.62-2005、Public Key Cryptography for the Financial Services Industry, The Elliptic Curve Digital Signature Algorithm (ECDSA)、2005年11月16日、を参照されたい。
【００１９】
より具体的には、ECCは、有限フィールドに及ぶ楕円曲線に基づく公開鍵暗号のタイプである。この点において、楕円曲線は、等式y2=x3+ax+bを満足する点P=(x,y)のセットに関連付けることができ、ここでaおよびbは、「無限遠点」を伴う(いくつかの条件を満足する)定数値である。数kによる、点PのEC点乗算は、点Pをそれ自体にk回加算した結果、すなわち、kP=P+P+...+Pとして定義し、または表すことができる。kおよびnの値は十分に大きいので、この形式のスカラー乗算は、データに署名および検証、すなわちデジタル署名を生成する際などに使用するための暗号プロセスとして働く。この点において、EC点乗算は、QおよびPの既知の値が与えられている場合にQ=kPからkを決定するという、明らかな扱いにくさ(intractability)を活用する(本文中において、Pは生成子と呼ばれ、Gで記されることがある)。この扱いにくさにより、値kPは公開鍵として使用することができ、kは秘密鍵として使用することができる。
【００２０】
点乗算を実施するために、ECCは、点加算および点倍化を利用することができる。手短に言うと、点加算または“ADD”は、楕円曲線の投射バージョンに沿って2つの点をとること、および2つの点を通る直線が、曲線上のさらに別の場所において曲線と交差する交点を決定することを伴う。交点の負数は、加算の結果を表す。点倍化または“DOUBLE”は、投射楕円曲線上の一地点におけるタンジェントが、接線を与えるために活用されることを除いて、点加算と同様であり、接線は次いで、曲線上の別の場所において曲線と交差する。点乗算(point multiplication)は、“DOUBLE ad ADD”を実装することなどによって、必要に応じて点加算(point addition)および点倍化(point doubling)を使用することによって実施することができる。
【００２１】
したがって、EC点乗算は、乗数kおよび基点Pを受け付ける算出またはプロセスと見なすことができる。EC点乗算は通常、kの値を、バイナリ数として解釈されるとき、値が乗数に等しくなるような一連のビット(たとえば、バイナリ値、ビットストリングまたはバイナリベクトル)として表すことによって実装される。この点において、変数Zは最初に、楕円曲線にとっては上述した無限遠点である加法単位元に設定され、または最初に、第1のビットペアによって決定される値など、他の適切な値に設定されてよい。(Zは実際には、大きい整数である、xおよびy座標をもつタプルであることに留意されたい)。Zは次いで、乗数kのビットに基づいて再設定または修正されてもよい。これは、kを最上位ビットから最下位ビットまで調べることによって実施することができる。所与のビットについて、そのビットが0である場合、Z:=2Zとする。そのビットが1である場合、Z:=2Z+Pとする。kのビットすべてが処理されると、Zの現在の値は結果を表す。通常、乗数kは、ハッカーまたは他の悪意のある存在から保護されることを意図している秘密の値である。上述のように、計算についての情報、ならびに秘密鍵kが漏洩し得る、いくつかのサイドチャネル機構が存在する。
【００２２】
上述した点倍化および点加算に関する限り、kのビットが0であるケースは、DOUBLE演算のみを生じる。kのビットが1であるケースは、DOUBLEおよびADDを生じる。したがって、ADDの数は、kの中の1であるビットの数に等しい。ADD演算は、処理システム内で実施するのに時間がかかるので、演算の持続時間およびタイミングに関する情報が、kの中の1であるビットの数を、たとえば、図1および図2のサイドチャネル攻撃システムを使用して暴露する場合がある。さらに、DOUBLEおよびADD演算には一般に、処理システム内で実施するのに、異なる量の電力がかかるので、(たとえば、オシロスコープ上で)電力使用を観察すると、kのすべてのビットを直接暴露する場合がある。ADDの数を一定にする暗号技法が開発されているが、この予防措置を用いたとしても、消費される電力は、機械レベルの命令中の、1であるビットの数に依存し得る。計算が何回も繰り返される場合、kについての情報を抽出することが可能な場合があり、すなわち、情報のサイドチャネル漏洩が依然として起こり得る。
【００２３】
図3は、これらの問題のうちの少なくともいくつかに対処するための一技法を示し、ここで乗数は、漏洩を削減するように再コード化される。kのbase 4表現と見なすことができるものを生じるように、乗数kのビットを「一度に2つずつ」グループ化するように動作する、再コード化の例示的な例300が示されている。この例では、バイナリシリーズまたはバイナリベクトルであってよい入力ストリングk302が、一度に2つずつグループ化されて、"base 4"ストリング304が生じる。明快のために、このグループ化は、図において別個の"base 4"ストリング304により示されていることに留意されたいが、別個のストリングが計算または記憶される必要はないことを理解されたい。後に続く演算は、単にビットを一度に2つずつとることによって、バイナリストリング302に対して直接作用し得る。さらに、以下の例では、簡単のために、各2ビットペアは数字と見なされる。ステップ306において、ストリングk内を右から左に進んで、処理システムは、1でも2でも3でもない任意の数字から4を繰り返し減算し、次いで、数字の左に1を加えることによって、kを一度に2ビットずつ再コード化する。つまり、2ビットの数字は、1、2、または3である場合、再コード化中に取り残される。2ビットの数字が1でも2でも3でもない場合、現在の数字が-4、1、2、または3になるまで、現在の数字から4が繰り返し減算され、数字の左に1が加えられる(必要な場合、新しい数字を作成する)。kの再コード化バージョン中の結果は、図中ではk'と呼ばれる。
【００２４】
処理システムはまた、基点Pに基づいて、4つの作業値(working value)、すなわち3*P、2*P、1*P、-4*Pを事前計算し、これらはそれぞれ、値312、314、316および318として記憶される。システムはまた、320において、Zを、第1のビットペアによって決定された値に初期化する。次いで、322において、k'内を左から右に進み、処理システムは、Z:=2*(2*Z)+d*Pを使用して、k'に基づいてZの新しい値を計算し、ここでdは、k'の現在の数字である。つまり、処理は、k'内を、左から右に一度に1つの数字だけ進む。現在の数字の値がdである場合(また、dは-4、1、2または3にはなるが0にはならないことを思い起こして)、処理システムは、d*Pについての事前計算値(すなわち、3*P、2*P、1*Pおよび-4*P)を使用することによって、新しい値を計算する。最終的なストリングは、Q,324と記される。この再コード化手順は、Qのすべての数字を、2つのDOUBLEおよび1つの加算に関連付けさせ、この関連付けが次いで、攻撃者が、DOUBLEおよび加算が互いに対して異なって見える電力トレースから数字を直接読み取ることを難しくさせる。この手順は、サイドチャネル漏洩を削減する際に有用であるが、k'が生成されたときに余分な数字が作成される必要がある場合があり、したがって、手順のタイミング(たとえば、その持続時間)が、悪意のある存在が悪用するかもしれない情報を漏洩し得るので、改善の余地が残っている。さらに、この手順は、ステップごとの演算中のゼロおよび1の数に依存する統計的攻撃を妨げるものではない。
【００２５】
図4は、漏洩を削減するための別の技法を示す。図4の技法400は、nのランダム倍数、すなわち基点のオーダを、kに加算して、k'=k+r*nを生じることを伴い、ここでrは乱数である。つまり、401において、処理システムは、値rをランダムに生成し、次いで、r*nを表すバイナリストリング値403を事前計算する。入力ストリング402は、ビットストリングkに対応する。kおよびr*nの値は次いで、ブロック405において加算されて、ストリングk'=k+r*nを生じ、このストリングはやはり、示されるように、ビットのペアをグループ化することによるbase 4ストリングと見なすことができる。その後、処理は、ストリングk'404が、新しいストリングk''408を生じるように再コード化されて、図3に関連して概説したように進んでよく、ストリングk''408は次いで、410においてPを使用して事前計算され、ブロック412、414、416および418において記憶された値に基づく点乗算論理422を使用して、初期化されたZ値420からQ値424を生成するのに使用される。図4の技法は通常、ノイズからkを抽出したことに基づいて、攻撃を妨害することができ、というのは、任意の妥当な数のサンプルについて、同じk'は、(ランダム成分rを組み込むので)わずかな回数しか起こらないからである。ただし、図3を参照して上で論じた再コード化技法と同様、図4の手順は、再コード化がk''に余分な数字を加え得るので、同じサイズkをもつインスタンスが同じ時間に稼動することを保証しない。
【００２６】
図5は、図3および図4の手順を悩ませる形の漏洩を実質的に削減または排除するための、ECCデバイスによって動作可能な技法の概要を与える。図5の再コード化技法500は、nのランダム倍数、すなわち基点のオーダをkに加算することも伴うが、ランダム倍数rは、取得されたrの特定の値にかかわらず、k+r*nのバイナリシリーズ表現の最上位ビットのビット位置が偶数であり、スカラー乗数(k)の値に依存せずにデバイスリソースを消費するように、EC点乗算手順中は、特定の楕円曲線に対して固定されたままとなる、すなわち、kにかかわらず時間および電力消費が均一になるような値の範囲に制約される。つまり、ステップ502において、ECC処理システムは、たとえば、楕円曲線上でオーダ(n)を有する基点(P)のスカラー乗数(k)を選択することによって、EC点乗算手順とともに使用するための秘密鍵を生成するか、またはそうでなければ取得もしくは獲得する。本明細書では、「取得すること」が、たとえば生成すること、獲得すること、受け取ること、取り出すこと、または何らかの他の適切な対応する行動を実施することを幅広く包含することに留意されたい。ステップ504において、処理システムは、上述のように、k+r*nのベクトル表現の最上位ビットのビット位置が偶数であり、そうでなければ起こり得るサイドチャネル漏洩を実質的に排除するように、EC点乗算手順(ADDおよびDOUBLEなど)中は特定の楕円曲線に対して固定されたままとなるような、値の制約された範囲内から整数乗数rをランダムに生成する。ステップ506において、処理システムは次いで、k+r*n(またはその再コード化バージョン)を使用してEC点乗算手順を実施して、たとえば、公開鍵を生成し、かつ/またはそのような鍵を利用してデジタル署名を生成しかつ処理する。
【００２７】
図5の例示的な処理技法は、実質的に一定の稼動時間を提供し、それによって一連のDOUBLEおよびADDが一定になる。この技法を用いると、攻撃者が被害者に同じEC点乗算計算を何回も繰り返させるのに成功した場合であっても、計算の各インスタンスは、異なるk'(すなわち、k+r*nまたはその再コード化バージョン)を高い確率で使用し、したがって統計的攻撃をより難しくする。この点において、(再コード化されていないkの)最上位ビットの固定された位置、すなわちmが偶数であり、最下位ビットがゼロの数をつけられている(または一般的用語において等価には、乗数が、奇数個のビットを有する)場合、再コード化手順は常に、m/2個の数字を生成することに最初に留意されたい。図5の手順の重要態様は、k'=k+r*nの最上位ビットのビット位置が常に偶数であり、かつ特定の楕円曲線に対して固定される(k<nであると仮定する)ように、ランダム値、すなわちrを生成することである。したがって、一連のDOUBLEおよびADD演算は、kに依存することはない。さらに、非常に大きい個数の、k'の可能値があり、攻撃者はrを知らないので、攻撃者が、ノイズから信号を抽出するために統計的攻撃を仕掛けることはかなり難しくなる。
【００２８】
手順を記述する際の明快および簡潔のために、ここでの説明では、ECCの「大きな数字」がワードで表されること、およびコンピュータ算術がワードに対して作用することは無視する。その条件を念頭に置くと、大数算術を使用する暗号システムには、法(すなわち、基点のオーダ)に関連付けられた多くの態様、すなわちビット長、モンゴメリ乗算向けのいくつかの特殊な値などがある。実際、これらは概して、前もって計算され、関与する法に関連付けられたデータ構造に入れられる。事前計算された値のこのセットに、バイナリ点が最も左のビットのすぐ左であるとき、追加値、すなわち法の近似ワードサイズの逆数が加算されてよい。この値は、両端値を含む、1と2との間になる。(ここで定義される厳密な逆数は、1に等しくなくてよいが、ワードに丸められると、値が厳密な1に丸まるように、十分に近くなり得ることに留意されたい)。ここで、法のこの近似逆数は本明細書では、"mrecip"と呼ばれる。説明を簡単にするために、本明細書における説明は、mrecipを、浮動小数点値であるかのように扱うが、当業者は、値を表すのに、スケーリング情報とともに整数を使用してよい。ここで、mはバイナリ値中のビットの数またはnを表すベクトルである。したがって、n*mrecipは2mとほぼ等しい。
【００２９】
k'中の(およびしたがって、再コード化乗数中の)ビットの数は、2(j-1)≦k+r*n≦2j-1である限り、jになる(ここで、jは奇数のはずである)。この不等式は、わずかにより厳しい不等式2(j-1)≦r*n<2j-nが同様に真である場合、k<nであるので、必然的に真になる。すべての項をmrecip*2-mで乗算すると、mrecip*2-m*2(j-1)≦mrecip*2-m*r*n<mrecip*2-m*2j-mrecip*2-m*nとなる。n*mrecip*2-mは近似的に1であり、単純化すると、mrecip*2(j-m-1)≦r<mrecip*2(j-m)-1が取得されることに留意されたい。実際、ある程度の丸めエラーがあるので、安全性のために、rは、わずかにより狭い範囲、すなわちfloor(mrecip*2(j-m-1))+1..floor(mrecip*2(j-m))-2(ここで、floor(x)は、x以下の、最も大きい整数を表す関数である)内でランダムに(または擬似ランダムに)選択される。たとえば、k'がnよりも24だけ多くのビットを有する場合、j-m-1は23であり、j-mは24である。したがって、mrecipが1に近い場合であっても、rは、おおよそ223と224との間になり、約800万個の可能なr値があるので、同じr値は非常にまれにしか発生しない。
【００３０】
したがって、図6に示すように、k+(r*n)において使用するための整数乗数(r)を取得するための例示的手順では最初に、処理システムが、ステップ602において、オーダ(n)をバイナリ値として表す際に使用するためのビットの数(m)を選択するか、またはそうでなければ決定する。ステップ604において、処理システムは、k+r*nをバイナリ値として表す際に使用するためのビットの数(j)を選択または決定する。ステップ606において、処理システムは、(r)を制約するための値の範囲の下端(RL)を決定し、ここでRL=floor(mrecip*2(j-m-1)+1)であり、説明したように、mrecipは基点(P)のオーダ(n)の近似逆数である。ステップ608において、処理システムは、(r)を制約するための値の範囲の上端(RU)を決定し、ここでRU=floor(mrecip*2(j-m-1)-2)である。ステップ610において、処理システムは、範囲RL..RU内から、rをランダムまたは擬似ランダムに生成する。rの値は次いで、k'=k+(r*n)を生成するのに使用される。
【００３１】
図7は、図5〜図6の手順をさらに示す。図7の手順700は701において始まり、ここでランダム乗数rは、上述した制約された値の範囲内からランダムに生成され、r*nが次いで、計算される。つまり、rは、floor(mrecip*2(j-m-1))+1..floor(mrecip*2(j-m)-2)の範囲内からランダムまたは擬似ランダムに取得される。これを容易にするために、mrecipの値を事前計算すればよい。得られるバイナリ値r*nが、703において記憶される。入力ストリング702は、ビットストリングkに対応する。kおよびr*nの値は、ブロック705において加算されて、ストリングk'=k+r*nを生じ、このストリングはやはり、ビットのペアをグループ化することによるbase 4ストリングと見なすことができる。ただし、記載したようにrを制約または制限するおかげで、k'の最上位ビットは偶数であり、かつ特定の楕円曲線に対して固定される。実際、示されるように、2つの最上位ビット707および709は、それぞれ0および1である。その後、処理は、図4に関連して上で概説したように進んでよく、ストリングk'が、ストリングk''を生じるように再コード化される。しかしながら、やはりrを制約するおかげで、k''の最上位ビットは同様に偶数であり、かつ特定の楕円曲線に対して固定され、示されるように、2つの最上位ビット711および713は0および1である。ストリングk''は次いで、710において事前計算され、ブロック712、714、716および718において記憶された4つの値(3*P、2*P、1*Pおよび-4*P)に基づいて、点乗算論理722を使用して、初期化されたZ値720からQ724を生成するのに使用される。
【００３２】
一連の基本EC点乗算論理演算は、(任意の特定のECC曲線についての一定数の周期に対して)DOUBLE、DOUBLE、ADDであるので、図7の手順は、単純な電力分析およびタイミング攻撃を難しくする。上述したように、単純な電力分析が、より多くの情報を抽出するために信号加算平均と組み合わされてもよいが、これは、異なるk'値を有するほぼすべてのトレースによって阻止される。いくつかのECC手順では、ランダム値の導入が、差分電力分析を容易にすることができ、攻撃者はrを知らないので、ここでは疑わしいことにやはり留意されたい。
【００３３】
例示的な装置、システムおよび方法
図8は、EC点乗算コントローラ804と、少なくとも1つのデジタル署名をそこから取得することができるデジタル署名ジェネレータ806と、デジタル署名検証器808とを設ける処理回路802を有する例示的な楕円曲線暗号(ECC)処理デバイス800を示す。この例では、EC点乗算コントローラ804は、一連のビットとして表される値に対して作用するEC点乗算手順とともに使用するための、楕円曲線上の、オーダ(n)の基点(P)のスカラー乗数(k)を取得するように動作可能なスカラー乗数(k)選択コントローラを含む。整数乗数(r)範囲決定コントローラ812は、範囲内で取得された(r)の特定の値にかかわらず、整数乗数(r)とオーダ(n)の積と合計されたスカラー乗数(k)を使用して実施されるEC点乗算手順が、スカラー乗数(k)の値に依存せずに処理リソースを消費するように制限された、整数乗数(r)についての値の範囲を決定するように動作可能である。範囲決定コントローラ812は、mrecipがnの近似逆数であり、mがnを表す値の中のビットの数であり、jがk+(r*n)を表す値の中のビットの数であるRL=floor(mrecip*2(j-m-1)+1)を決定することによって、値の範囲の下端(RL)を決定するように、また、すでに説明したように、RU=floor(mrecip*2(j-m)-2)を決定することによって、値の範囲の上端(RU)を決定するように動作し得る。整数乗数(r)生成コントローラ814は、整数乗数(r)とオーダ(n)の積と合計されたスカラー乗数(k)を使用して実施されるEC点乗算手順が、スカラー乗数(k)の値に依存せずに処理リソースを消費するような整数乗数(r)を取得するように動作可能であり、これは、範囲決定コントローラ812によって決定された値の範囲内から値rをランダムまたは擬似ランダムに選択することによって遂行することができる。
【００３４】
合計コントローラ816は、整数乗数(r)をオーダ(n)に適用して、整数乗数(r)とオーダ(n)の積(r*n)を生じるように、かつ、その後スカラー乗数(k)と、整数乗数(r)とオーダ(n)の積とを合計して、スカラー乗数(k)と、整数乗数(r)とオーダ(n)の積との和、たとえば、k+r*nを生じるように動作可能である。再コード化コントローラ818は次いで、整数乗数(r)とオーダ(n)の積と合計されたスカラー乗数(k)を再コード化して、再コード化値を生じるように、たとえば、k+r*nを再コード化するように動作可能である。再コード化は、たとえば、図3のブロック306に示すとともに上述したように、ただし、選ばれた(r)の特定の値にかかわらず、k+r*nの最上位ビットのビット位置が偶数であり、再コード化中は特定の楕円曲線に対して固定されるようにrが制約されたk+r*nを使用して実施することができる。したがって、再コード化動作は、少なくとも時間および電力に関する限り、いかなるサイドチャネル漏洩も呈するはずがない。Z初期化コントローラ820は、上述したように、EC点乗算論理コントローラ822とともに使用するためのスカラー値Zを最初に設定するように動作可能である。事前計算コントローラ824は、EC点乗算論理コントローラ822を使用して、再コード化値に基づいてZを処理する際に使用するために、Pに基づいて値を事前計算するように動作可能である。たとえば、事前計算コントローラ824は、-4*P、1*P、2*Pおよび3*Pの値を、図7に示すとともに上で論じたように事前計算することができる。事前計算コントローラは、mrecipの値を、範囲決定コントローラ812によって使用するために、事前計算することもできる。EC点乗算論理コントローラ822は次いで、再コード化された和k+r*n(再コード化コントローラから取得される)の値に基づいて(Z初期化コントローラから取得される)値Zを処理して出力値Qを生じるために、(事前計算コントローラから取得される)Pに基づく事前計算値を適用してよい。Qの生成は、たとえば、概して図3のブロック322に示すとともに上述したように、ただし再コード化値に基づいて実施することができ、ここで、やはり、最上位ビットのビット位置は偶数であり、かつ特定の楕円曲線に対して固定される。
【００３５】
デジタル署名ジェネレータ806およびデジタル署名検証器808は、EC点乗算コントローラ804によって生成されるか、もしくはそうでなければ取得されたk、PおよびQ値に少なくとも部分的に基づいて、またはEC点乗算コントローラによって生成されるか、もしくはそうでなければ取得された他の値を使用することによって、デジタル署名を生成および/または検証することができる。いくつかの例では、デジタル署名ジェネレータおよびデジタル署名検証器は、EC点乗算論理コントローラ822など、EC点乗算コントローラの構成要素のうちのいくつかを使用することも、組み込むこともでき、事前計算コントローラ824によって事前計算された値のうちのいくつかを使用することができる。
【００３６】
したがって、処理デバイス800、および様々な構成要素は、一連のビットとして表される値に対して作用する楕円曲線点乗算手順とともに使用するための、楕円曲線上でのオーダ(n)の基点(P)のスカラー乗数(k)を取得するための手段と、範囲内で取得された(r)の特定の値にかかわらず、整数乗数(r)とオーダ(n)の積と合計されたスカラー乗数(k)を使用して実施される楕円曲線点乗算手順が、スカラー乗数(k)の値に依存せずにデバイスリソースを消費するような値の範囲を決定するための手段と、値の範囲内から整数乗数(r)を取得するための手段と、スカラー乗数(k)、整数乗数(r)およびオーダ(n)を使用して、少なくとも1つの楕円曲線点乗算手順を実施するための手段とを提供する。処理デバイス800は、範囲内で取得された(r)の特定の値にかかわらず、整数乗数(r)とオーダ(n)の積と合計されたスカラー乗数(k)の最上位ビットのビット位置が偶数であり、かつ特定の楕円曲線に対して固定されるように制限された、整数乗数(r)についての値の範囲を決定するための手段も提供する。
【００３７】
図9は、図8のECC処理デバイス800または他の適切に装備されたデバイスによって実施することができる方法または手順900を示す。ステップ902において、楕円曲線上でのオーダ(n)の基点(P)のスカラー乗数(k)が、一連のビットとして表される値に対して作用するEC点乗算手順とともに使用するために取得される。ステップ904において、整数乗数(r)についての値の範囲が、範囲内で取得された(r)の特定の値にかかわらず、整数乗数(r)とオーダ(n)の積と合計されたスカラー乗数(k)を使用して実施されるEC点乗算手順が、スカラー乗数(k)の値に依存せずにデバイスリソースを消費するように決定される。ステップ905において、整数乗数(r)が、値の範囲内から取得される。ステップ906において、少なくとも1つのEC点乗算手順が、スカラー乗数(k)、整数乗数(r)およびオーダ(n)を使用して実施される。
【００３８】
図10は、図8のECC処理デバイス800または他の適切に装備されたデバイスによって実施することができる追加の方法または手順1000を示す。この例では、ステップ1002において、範囲内で取得された(r)の特定の値にかかわらず、整数乗数(r)とオーダ(n)の積と合計されたスカラー乗数(k)の最上位ビットのビット位置(すなわち、k+r*n)が偶数であり、かつ特定の楕円曲線に対して固定されるように制限または制約される整数乗数(r)について、値の範囲が決定される。ステップ1004において、整数乗数(r)は、ランダムまたは擬似ランダム選択によって、範囲内から選択されるか、またはそうでなければ取得される。ステップ1006において、整数乗数(r)は、オーダ(n)に適用されて、その積(すなわち、r*n)を生じ、次いで、スカラー乗数(k)は、r*nに適用されて、その和(すなわち、k+r*n)を生じる。言い方を変えると、ステップ1006において、整数乗数(r)は、オーダ(n)に適用されて、整数乗数(r)とオーダ(n)の積(r*n)を生じ、次いで、スカラー乗数(k)は、整数乗数(r)とオーダ(n)の積に適用されて、整数乗数(r)とオーダ(n)の積と、スカラー乗数(k)との和(すなわち、k+r*n)を生じる。ステップ1008において、k+r*nは、kの再コード化値を生じるように再コード化される。言い方を変えると、ステップ1008において、整数乗数(r)とオーダ(n)の積と合計されたスカラー乗数(k)が、再コード化値を生じるように再コード化される。ステップ1010において、再コード化値および値Zを使用するEC点乗算論理が適用されて、値Qが生じ、ここで、基点(P)に基づく事前計算値が、kの再コード化値に基づいてZを処理するために適用される。ステップ1012で、k、PおよびQに基づいて少なくとも1つのデジタル署名が取得される。
【００３９】
図11は、図1〜図10の構成要素および方法を実装することができる全体的なシステムまたは装置1100を示す。本開示の様々な態様によれば、要素、要素の何らかの部分、または要素の何らかの組合せを、図8の処理回路などの1つまたは複数の処理回路1104を含む処理システム1114を用いて実装することができる。たとえば、装置1100は、インターネットに接続されたトランザクションサーバの構成要素であってもよく、モバイル通信システムのワイヤレスデバイス(たとえば、ユーザ機器(UE)やタブレットコンピュータ)の構成要素であってもよい。処理回路1104の例は、マイクロプロセッサ、マイクロコントローラ、デジタル信号プロセッサ(DSP)、フィールドプログラマブルゲートアレイ(FPGA)、プログラマブル論理デバイス(PLD)、ステートマシン、ゲート論理、個別のハードウェア回路、および本開示の全体にわたって説明される様々な機能性を実施するように構成される他の適切なハードウェアを含む。すなわち、装置1100内で利用されるような処理回路1104は、デジタル署名を生成し、または検証するためのプロセスなど、上で説明し、図3〜図7および/または図9〜図10に示すプロセスのうちのいずれか1つもしくは複数を実装するために使用され得る。特に、処理回路1104は、一連のビットとして表される値に対して作用する楕円曲線点乗算手順とともに使用するための、楕円曲線上でのオーダ(n)の基点(P)のスカラー乗数(k)を取得し、範囲内で取得された(r)の特定の値にかかわらず、整数乗数(r)とオーダ(n)の積と合計されたスカラー乗数(k)を使用して実施される楕円曲線点乗算手順が、スカラー乗数(k)の値に依存せずに処理リソースを消費するように設定された、値の範囲から整数乗数(r)を取得し、スカラー乗数(k)、整数乗数(r)およびオーダ(n)を使用して、少なくとも1つの楕円曲線点乗算手順を実施するように構成されてよい。
【００４０】
図11の例では、処理システム1114を、全般的にバス1102によって表されるバスアーキテクチャを用いて実施することができる。バス1102は、処理システム1114の特定の応用および設計制約全体に応じて任意の数の相互接続バスおよびブリッジを含むことができる。バス1102は、1つまたは複数の処理回路(概して処理回路1104によって表される)を含む様々な回路、メモリ記憶デバイス1105、および機械可読媒体またはコンピュータ可読媒体(概して機械可読媒体1106によって表される)をリンクする。バス1102は、タイミングソース、周辺装置、電圧調整器、および電力管理回路などの様々な他の回路をリンクすることもできるが、これらの回路は当技術分野でよく知られており、したがってこれ以上は説明しない。バスインターフェース1108は、バス1102とトランシーバ1110との間のインターフェースを提供する。トランシーバ1110は、送信媒体を介して様々な他の装置と通信するための手段を提供する。装置の性質に応じて、ユーザインターフェース1112(たとえば、キーパッド、ディスプレイ、スピーカー、マイクロフォン、ジョイスティック)も設けられ得る。
【００４１】
プロセッサまたは処理回路1104は、バス1102の管理と、機械可読媒体1106上に記憶されたソフトウェアの実行を含む全般的な処理とを担当する。ソフトウェアは、プロセッサ1104によって実行されると、処理システム1114に、任意の特定の装置について本明細書で説明した様々な機能を実施させる。機械可読媒体1106は、ソフトウェアを実行するときにプロセッサ1104によって操作されるデータを記憶するのにも使用され得る。特に、機械可読記憶媒体1106は、処理回路1104によって実行されると、処理回路1104に、一連のビットとして表される値に対して作用する楕円曲線点乗算手順とともに使用するための、楕円曲線上でのオーダ(n)の基点(P)のスカラー乗数(k)を取得させ、範囲内で取得された(r)の特定の値にかかわらず、整数乗数(r)とオーダ(n)の積と合計されたスカラー乗数(k)を使用して実施される楕円曲線点乗算手順が、スカラー乗数(k)の値に依存せずに処理リソースを消費するような値の範囲を決定させ、値の範囲内から整数乗数(r)を取得させ、スカラー乗数(k)、整数乗数(r)およびオーダ(n)を使用して、少なくとも1つの楕円曲線点乗算手順を実施させる1つまたは複数の命令を有し得る。
【００４２】
処理システムの1つまたは複数のプロセッサ1104は、ソフトウェアを実行することができる。ソフトウェアは、ソフトウェア、ファームウェア、ミドルウェア、マイクロコード、ハードウェア記述言語と呼ばれるか、または他の名称で呼ばれるかどうかにかかわらず、命令、命令セット、コード、コードセグメント、プログラムコード、プログラム、サブプログラム、ソフトウェアモジュール、アプリケーション、ソフトウェアアプリケーション、ソフトウェアパッケージ、ルーチン、サブルーチン、オブジェクト、実行可能ファイル、実行スレッド、手順、機能などを意味するように広く解釈されるべきである。プロセッサは、必要なタスクを実施し得る。コードセグメントは、プロシージャ、関数、サブプログラム、プログラム、ルーチン、サブルーチン、モジュール、ソフトウェアパッケージ、クラス、または命令、データ構造もしくはプログラムステートメントの任意の組合せを表す場合がある。コードセグメントは、情報、データ、引数、パラメータ、またはメモリ内容を渡すことおよび/または受け取ることによって、別のコードセグメントまたはハードウェア回路に結合され得る。情報、引数、パラメータ、データなどは、メモリ共有、メッセージパッシング、トークンパッシング、ネットワーク送信などを含む、任意の適切な手段を介して渡されてもよく、転送されてもよく、または送信され得る。
【００４３】
ソフトウェアは、コンピュータ可読または機械可読媒体1106上に存在することができる。明記したように、機械可読媒体1106は、非一時的機械可読媒体とすることができる。非一時的機械可読媒体は、例として、磁気記憶デバイス(たとえば、ハードディスク、フロッピーディスク、磁気ストリップ)、光ディスク(たとえば、コンパクトディスク(CD)もしくはデジタル多用途ディスク(DVD))、スマートカード、フラッシュメモリデバイス(たとえば、カード、スティック、もしくはキードライブ)、ランダムアクセスメモリ(RAM)、読取り専用メモリ(ROM)、プログラマブルROM(PROM)、消去可能PROM(EPROM)、電気的消去可能PROM(EEPROM)、レジスタ、リムーバブルディスク、ハードディスク、CD-ROMならびにコンピュータがアクセスし、読み取ることができるソフトウェアおよび/または命令を記憶するための任意の他の適切な媒体を含む。「機械可読媒体」、「コンピュータ可読媒体」、および/または「プロセッサ可読媒体」という用語は、限定はされないが、ポータブルもしくは固定記憶デバイス、光記憶デバイス、ならびに、命令および/もしくはデータを記憶、格納または搬送することが可能な様々な他の媒体のような、非一時的媒体を含み得る。したがって、本明細書で説明される様々な方法は、「機械可読媒体」、「コンピュータ可読媒体」および/または「プロセッサ可読媒体」に記憶され、1つもしくは複数のプロセッサ、機械および/またはデバイスによって実行され得る命令および/またはデータによって、完全にまたは部分的に実装され得る。機械可読媒体は、たとえば、搬送波、伝送線、およびコンピュータによってアクセスされ、読み取られ得るソフトウェアおよび/または命令を伝送するための任意の他の適切な媒体をも含むことができる。機械可読媒体1106は、処理システム1114内に、処理システム1114の外部に存在し、または処理システム1114を含む複数のエンティティにまたがって分散され得る。コンピュータ可読媒体1106は、コンピュータプログラム製品において具現化することができる。たとえば、コンピュータプログラム製品は、パッケージング材料内に機械可読媒体を含むことができる。当業者は、具体的な適用例および全体的なシステムに課された設計制約全体に応じて、本開示全体において提示された説明された機能性を最善の形で実装する方法を認識するであろう。
【００４４】
図面に示す構成要素、ステップ、特徴および/または機能のうちの1つもしくは複数は、単一の構成要素、ステップ、特徴、もしくは機能に再構成および/または結合されてよく、あるいは、いくつかの構成要素、ステップもしくは機能に組み込まれてもよい。追加の要素、構成要素、ステップ、および/または機能を、本開示から逸脱せずに追加してもよい。図示される装置、デバイス、および/または構成要素は、図示された方法、特徴、またはステップのうちの1つまたは複数を実施するように構成することができる。また、本明細書で説明されたアルゴリズムは、効率的にソフトウェアに実装されてもよく、かつ/またはハードウェアに組み込まれてもよい。
【００４５】
本明細書で開示する例に関して説明する様々な例示的な論理ブロック、モジュール、回路、要素、および/または構成要素は、汎用プロセッサ、デジタル信号プロセッサ(DSP)、特定用途向け集積回路(ASIC)、フィールドプログラマブルゲートアレイ(FPGA)もしくは他のプログラマブル論理構成要素、個別ゲートもしくはトランジスタ論理、個別ハードウェア構成要素、または本明細書で説明する機能を実施するように設計されたそれらの任意の組合せで実装または実施される場合がある。汎用プロセッサはマイクロプロセッサであり得るが、代替形態では、プロセッサは、任意の従来のプロセッサ、コントローラ、マイクロコントローラ、またはステートマシンであり得る。プロセッサはまた、コンピューティング構成要素の組合せ、たとえば、DSPとマイクロプロセッサとの組合せ、いくつかのマイクロプロセッサ、DSPコアと連係した1つもしくは複数のマイクロプロセッサ、または他の任意のそのような構成として実装されてもよい。
【００４６】
したがって、本開示の一態様では、たとえば図8に示す処理回路は、図3〜図7および/または図10〜図11で説明したアルゴリズム、方法、および/またはステップを実施するように特に設計および/または配線接続される専用プロセッサ(たとえば、ASIC)であり得る。したがって、そのような専用プロセッサ(たとえば、ASIC)は、図3〜図7および/または図10〜図11で説明したアルゴリズム、方法、および/またはステップを実行するための手段の一例であり得る。機械可読記憶媒体は、専用プロセッサ(たとえば、ASIC)によって実行されると、その専用プロセッサに、本明細書において説明されるアルゴリズム、方法、および/またはステップを実施させる命令を記憶することができる。
【００４７】
また、本開示の態様は、フローチャート、流れ図、構造図またはブロック図として示されるプロセスとして本明細書において説明される場合があることに留意されたい。フローチャートは、動作を順次プロセスとして説明する場合があるが、動作の多くは並列または同時に実施することができる。さらに、動作の順序は入れ替えることができる。プロセスは、その動作が完了したとき、終了する。プロセスは、方法、関数、手順、サブルーチン、サブプログラムなどに相当する場合がある。処理が関数に対応するとき、その終了は、関数が呼出し関数またはメイン関数に戻ることに対応する。
【００４８】
本明細書で開示される態様に関して説明する様々な例示的な論理ブロック、モジュール、回路、およびアルゴリズムステップは、電子ハードウェア、コンピュータソフトウェア、または両方の組合せとして実装され得ることを当業者はさらに諒解されよう。ハードウェアとソフトウェアとのこの相互交換可能性を明瞭に示すために、様々な例示的な構成要素、ブロック、モジュール、回路、およびステップが、上では全般的にその機能性に関して説明された。そのような機能性が、ハードウェアまたはソフトウェアのどちらとして実施されるのかは、具体的な適用例と、システム全体に課せられる設計制約とによって決まる。
【００４９】
本明細書で説明する本開示の様々な特徴は、本開示から逸脱することなく様々なシステムで実装され得る。本開示の前述の態様は、例にすぎず、本開示を限定するものとして解釈されるべきではないことに留意されたい。本開示の態様の説明は、例示であることを意図しており、特許請求の範囲を限定することを意図していない。したがって、本教示は、他のタイプの装置に容易に適用することが可能であり、多くの代替形態、変更形態、および変形形態が当業者には明らかであろう。
【符号の説明】
【００５０】
100  ECCシステム
106  ECC署名デバイス、署名デバイス
109  チャネル
112  ECC署名検証デバイス
116  サイドチャネル攻撃デバイスまたはシステム
122  電源
200  ECCシステム
206  ECCベースのスマートカードリーダ
222  電源
216  電力測定オシロスコープ
217  サイドチャネルコンピュータ/アナライザ、コンピュータ/アナライザ
221  センサー、検出器
422  点乗算論理
722  点乗算論理
800  楕円曲線暗号(ECC)処理デバイス、処理デバイス
802  処理回路
804  EC点乗算コントローラ
806  デジタル署名ジェネレータ
808  デジタル署名検証器
812  整数乗数(r)範囲決定コントローラ、範囲決定コントローラ
816  合計コントローラ
818  再コード化コントローラ
820  Z初期化コントローラ
822  EC点乗算論理コントローラ
1100  システム、装置
1102  バス
1104  処理回路、プロセッサ
1105  メモリ記憶デバイス
1106  機械可読媒体
1108  バスインターフェース
1110  トランシーバ
1112  ユーザインターフェース
1114  処理システム
【図１】
2017511902.tif 000003
【図２】
2017511902.tif 000004
【図３】
2017511902.tif 000005
【図４】
2017511902.tif 000006
【図５】
2017511902.tif 000007
【図６】
2017511902.tif 000008
【図７】
2017511902.tif 000009
【図８】
2017511902.tif 000010
【図９】
2017511902.tif 000011
【図１０】
2017511902.tif 000012
【図１１】
2017511902.tif 000013
【手続補正書】
【提出日】平成28年9月12日(2016.9.12)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
デバイスによって動作可能な、楕円曲線点乗算のための方法であって、
一連のビットとして表される値に対して作用する楕円曲線点乗算手順とともに使用するための、楕円曲線上でのオーダ(n)の基点(P)のスカラー乗数(k)を取得するステップと、
値の範囲内で取得された整数乗数(r)の特定の値にかかわらず、前記整数乗数(r)と前記オーダ(n)との積と合計された前記スカラー乗数(k)を使用して前記デバイスによって実施される楕円曲線点乗算手順が、前記スカラー乗数(k)の値に依存せずに前記デバイスの1つまたは複数のリソースを消費することを保証するのに十分な、前記整数乗数(r)についての前記値の範囲を決定するステップと、
前記値の範囲内から整数乗数(r)を取得するステップと、
前記スカラー乗数(k)の前記値に依存せずに、前記デバイスの前記1つまたは複数のリソースを消費しながら、前記スカラー乗数(k)、前記整数乗数(r)および前記オーダ(n)を使用して、少なくとも1つの楕円曲線点乗算手順を実施するステップと
を含む、方法。
【請求項２】
前記整数乗数(r)についての前記値の範囲を決定するステップは、前記値の範囲内で取得された前記整数乗数(r)の前記特定の値にかかわらず、前記整数乗数(r)と前記オーダ(n)との前記積と合計された前記スカラー乗数(k)の最上位ビットのビット位置が偶数であり、かつ特定の楕円曲線に対して固定されることを保証するのに十分な、前記値の範囲を決定するステップを含む、請求項1に記載の方法。
【請求項３】
前記整数乗数(r)についての前記値の範囲を決定するステップは、
RL=floor(mrecip*2(j-m-1)+1)を決定することによって、前記値の範囲の下端(RL)を決定するステップであって、mrecipは前記オーダ(n)の近似逆数であり、mは前記オーダ(n)を表す値の中のビットの数であり、jは前記スカラー乗数(k)と、前記整数乗数(r)と前記オーダ(n)との前記積との和を表す値(k+(r*n))の中のビットの数である、ステップと、
RU=floor(mrecip*2(j-m)-2)を決定することによって、前記値の範囲の上端(RU)を決定するステップと
を含む、請求項2に記載の方法。
【請求項４】
前記値の範囲内から前記整数乗数(r)を取得するステップは、ランダムおよび擬似ランダム選択のうちの1つまたは複数を使用して実施される、請求項1に記載の方法。
【請求項５】
再コード化値を生じるために前記整数乗数(r)と前記オーダ(n)との前記積と合計された前記スカラー乗数(k)を再コード化するステップをさらに含む、請求項1に記載の方法。
【請求項６】
前記再コード化値に基づいてZを処理するために、Pに基づく事前計算値を適用することによって前記再コード化値および値Zを使用する楕円曲線点乗算論理を適用するステップをさらに含む、請求項5に記載の方法。
【請求項７】
処理回路を備えるデバイスであって、前記処理回路は、
一連のビットとして表される値に対して作用する楕円曲線点乗算手順とともに使用するための、楕円曲線上でのオーダ(n)の基点(P)のスカラー乗数(k)を取得し、
値の範囲内で取得された整数乗数(r)の特定の値にかかわらず、前記整数乗数(r)と前記オーダ(n)との積と合計された前記スカラー乗数(k)を使用して前記デバイスによって実施される楕円曲線点乗算手順が、前記スカラー乗数(k)の値に依存せずに前記デバイスの1つまたは複数のリソースを消費することを保証するのに十分な、前記整数乗数(r)についての前記値の範囲を決定し、
前記値の範囲内から整数乗数(r)を取得し、
前記スカラー乗数(k)の前記値に依存せずに、前記デバイスの前記1つまたは複数のリソースを消費しながら、前記スカラー乗数(k)、前記整数乗数(r)および前記オーダ(n)を使用して、少なくとも1つの楕円曲線点乗算手順を実施する
ように構成される、デバイス。
【請求項８】
前記処理回路は、前記値の範囲内で取得された前記整数乗数(r)の前記特定の値にかかわらず、前記整数乗数(r)と前記オーダ(n)との前記積と合計された前記スカラー乗数(k)の最上位ビットのビット位置が偶数であり、かつ特定の楕円曲線に対して固定されることを保証するのに十分な、前記整数乗数(r)についての前記値の範囲を決定するようにさらに構成される、請求項7に記載のデバイス。
【請求項９】
前記処理回路は、
RL=floor(mrecip*2(j-m-1)+1)を決定することによって、前記値の範囲の下端(RL)を決定することであって、mrecipは前記オーダ(n)の近似逆数であり、mは前記オーダ(n)を表す値の中のビットの数であり、jは前記スカラー乗数(k)と、前記整数乗数(r)と前記オーダ(n)との前記積との和を表す値(k+(r*n))の中のビットの数である、決定することと、
RU=floor(mrecip*2(j-m)-2)を決定することによって、前記値の範囲の上端(RU)を決定することと
によって、前記整数乗数(r)についての前記値の範囲を決定するように構成される、請求項8に記載のデバイス。
【請求項１０】
前記処理回路は、ランダムおよび擬似ランダム選択のうちの1つまたは複数を使用して、前記整数乗数(r)を、前記値の範囲内から取得するようにさらに構成される、請求項7に記載のデバイス。
【請求項１１】
前記処理回路は、再コード化値を生じるために前記整数乗数(r)と前記オーダ(n)との前記積と合計された前記スカラー乗数(k)を再コード化するようにさらに構成される、請求項7に記載のデバイス。
【請求項１２】
前記処理回路は、前記再コード化値に基づいてZを処理するために、Pに基づく事前計算値を適用することによって前記再コード化値および値Zを使用する楕円曲線点乗算論理を適用するようにさらに構成される、請求項11に記載のデバイス。
【請求項１３】
デバイスであって、
一連のビットとして表される値に対して作用する楕円曲線点乗算手順とともに使用するための、楕円曲線上でのオーダ(n)の基点(P)のスカラー乗数(k)を取得するための手段と、
値の範囲内で取得された整数乗数(r)の特定の値にかかわらず、前記整数乗数(r)と前記オーダ(n)との積と合計された前記スカラー乗数(k)を使用して前記デバイスによって実施される楕円曲線点乗算手順が、前記スカラー乗数(k)の値に依存せずに前記デバイスの1つまたは複数のリソースを消費することを保証するのに十分な、前記整数乗数(r)についての前記値の範囲を決定するための手段と、
前記値の範囲内から整数乗数(r)を取得するための手段と、
前記スカラー乗数(k)の前記値に依存せずに、前記デバイスの前記1つまたは複数のリソースを消費しながら、前記スカラー乗数(k)、前記整数乗数(r)および前記オーダ(n)を使用して、少なくとも1つの楕円曲線点乗算手順を実施するための手段と
を備える、デバイス。
【請求項１４】
前記整数乗数(r)についての前記値の範囲を決定するための前記手段は、前記値の範囲内で取得された前記整数乗数(r)の前記特定の値にかかわらず、前記整数乗数(r)と前記オーダ(n)との前記積と合計された前記スカラー乗数(k)の最上位ビットのビット位置が偶数であり、かつ特定の楕円曲線に対して固定されることを保証するのに十分な、前記値の範囲を決定するための手段を含む、請求項13に記載のデバイス。
【請求項１５】
前記整数乗数(r)についての前記値の範囲を決定するための前記手段は、
RL=floor(mrecip*2(j-m-1)+1)を決定することによって、前記値の範囲の下端(RL)を決定するための手段であって、mrecipは前記オーダ(n)の近似逆数であり、前記オーダ(n)を表す値の中のビットの数であり、jは前記スカラー乗数(k)と、前記整数乗数(r)と前記オーダ(n)との前記積との和を表す値(k+(r*n))の中のビットの数である、手段と、
RU=floor(mrecip*2(j-m)-2)を決定することによって、前記値の範囲の上端(RU)を決定するための手段と
を備える、請求項14に記載のデバイス。
【請求項１６】
前記値の範囲内から前記整数乗数(r)を取得するための前記手段は、ランダムおよび擬似ランダム選択のうちの1つまたは複数を実施するための手段を備える、請求項13に記載のデバイス。
【請求項１７】
再コード化値を生じるために前記整数乗数(r)と前記オーダ(n)との前記積と合計された前記スカラー乗数(k)を再コード化するための手段をさらに備える、請求項13に記載のデバイス。
【請求項１８】
前記再コード化値に基づいてZを処理するために、Pに基づく事前計算値を適用することによって前記再コード化値および値Zを使用する楕円曲線点乗算論理を適用するための手段をさらに備える、請求項17に記載のデバイス。
【請求項１９】
1つまたは複数の命令を有する非一時的機械可読記憶媒体であって、前記1つまたは複数の命令は、少なくとも1つの処理回路によって実行されると、前記少なくとも1つの処理回路に、
一連のビットとして表される値に対して作用する楕円曲線点乗算手順とともに使用するための、楕円曲線上でのオーダ(n)の基点(P)のスカラー乗数(k)を取得させ、
値の範囲内で取得された整数乗数(r)の特定の値にかかわらず、前記整数乗数(r)と前記オーダ(n)との積と合計された前記スカラー乗数(k)を使用してデバイスによって実施される楕円曲線点乗算手順が、前記スカラー乗数(k)の値に依存せずに前記デバイスの1つまたは複数のリソースを消費することを保証するのに十分な、前記整数乗数(r)についての前記値の範囲を決定させ、
前記値の範囲内から整数乗数(r)を取得させ、
前記スカラー乗数(k)の前記値に依存せずに、前記デバイスの前記1つまたは複数のリソースを消費しながら、前記スカラー乗数(k)、前記整数乗数(r)および前記オーダ(n)を使用して、少なくとも1つの楕円曲線点乗算手順を実施させる
、非一時的機械可読記憶媒体。
【請求項２０】
前記処理回路に、前記値の範囲内で取得された前記整数乗数(r)の前記特定の値にかかわらず、前記整数乗数(r)と前記オーダ(n)との前記積と合計された前記スカラー乗数(k)の最上位ビットのビット位置が偶数であり、かつ特定の楕円曲線に対して固定されることを保証するのに十分な、前記整数乗数(r)についての前記値の範囲を決定させるための命令をさらに含む、請求項19に記載の非一時的機械可読記憶媒体。
【請求項２１】
前記処理回路に、
RL=floor(mrecip*2(j-m-1)+1)を決定することによって、前記値の範囲の下端(RL)を決定することであって、mrecipは前記オーダ(n)の近似逆数であり、mは前記オーダ(n)を表す値の中のビットの数であり、jは前記スカラー乗数(k)と、前記整数乗数(r)と前記オーダ(n)との前記積との和を表す値(k+(r*n))の中のビットの数である、決定することと、
RU=floor(mrecip*2(j-m)-2)を決定することによって、前記値の範囲の上端(RU)を決定することと
によって、前記整数乗数(r)についての前記値の範囲を決定させるための命令をさらに含む、請求項20に記載の非一時的機械可読記憶媒体。
【請求項２２】
前記処理回路に、ランダムおよび擬似ランダム選択のうちの1つまたは複数を使用して、前記値の範囲内から前記整数乗数(r)を取得させるための命令をさらに含む、請求項19に記載の非一時的機械可読記憶媒体。
【請求項２３】
前記処理回路に、再コード化値を生じるために前記整数乗数(r)と前記オーダ(n)との前記積と合計された前記スカラー乗数(k)を再コード化させるための命令をさらに含む、請求項19に記載の非一時的機械可読記憶媒体。
【請求項２４】
前記処理回路に、前記再コード化値に基づいてZを処理するために、Pに基づく事前計算値を適用することによって前記再コード化値および値Zを使用する楕円曲線点乗算論理を適用させるための命令をさらに含む、請求項23に記載の非一時的機械可読記憶媒体。
【請求項２５】
前記処理回路は、前記楕円曲線上で、オーダ(n)の前記基点(P)の前記スカラー乗数(k)を取得するためのスカラー乗数選択コントローラを含む、請求項7に記載のデバイス。
【請求項２６】
前記処理回路は、前記整数乗数(r)についての前記値の範囲を決定するための整数乗数範囲決定コントローラを含む、請求項7に記載のデバイス。
【請求項２７】
前記処理回路は、ランダムおよび擬似ランダム選択のうちの1つまたは複数を使用して、前記値の範囲内から前記整数乗数(r)を取得するための整数乗数生成コントローラを含む、請求項7に記載のデバイス。
【請求項２８】
前記処理回路は、前記スカラー乗数(k)、前記整数乗数(r)および前記オーダ(n)を使用して、少なくとも1つの楕円曲線点乗算手順を実施するための楕円曲線点乗算論理コントローラを含む、請求項7に記載のデバイス。
【請求項２９】
前記処理回路は、再コード化値を生じるために前記整数乗数(r)と前記オーダ(n)との前記積と合計された前記スカラー乗数(k)を再コード化するための再コード化コントローラを含む、請求項7に記載のデバイス。
【請求項３０】
前記処理回路は、前記整数乗数(r)と前記オーダ(n)との積(r*n)を生じるために前記整数乗数(r)を前記オーダ(n)に適用するため、かつ、その後、前記スカラー乗数(k)と、前記整数乗数(r)と前記オーダ(n)との前記積との和を生じるために前記スカラー乗数(k)を前記整数乗数(r)と前記オーダ(n)との前記積と合計するための合計コントローラを含む、請求項7に記載のデバイス。
【請求項３１】
前記処理回路は、前記楕円曲線点乗算とともに使用するためのスカラー値Zを設定するためのZ初期化コントローラを含む、請求項7に記載のデバイス。
【請求項３２】
前記処理回路は、前記再コード化値に基づいて、Zを処理する際に使用するためのPに基づく値を事前計算するための事前計算コントローラを含む、請求項31に記載のデバイス。
【国際調査報告】
2017511902.tif 000014
2017511902.tif 000015