強化された自然モンゴメリー指数マスキング
暗号化装置の非侵害的な物理的検査によって秘密指数情報を発見することを目的とする選択メッセージ攻撃を受けるセキュリティ保護された暗号化装置において、累乗されるメッセージをマスクするための方法および装置。モンゴメリー演算の使用によって、ランダムな乗算係数が入力メッセージに適用され、および、従来技術のマスキング技術において必要とされるようにランダムファクタの逆数を計算する必要なしに、容易に取り除かれることが可能である。このマスキングは、モンゴメリー演算の使用に特有である自然マスキングを補足且つ強化する。本発明の方法は、モンゴメリー演算プロセッサに理想的に適しているが、これだけには限定されず、および、他のセキュリティ保護技術と組み合わせて使用されることが可能である。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号技術の分野に関し、および、特に、公開鍵暗号システムを使用するスマートカードのような、物理的攻撃に対してセキュリティ保護されていることが意図されている暗号化アルゴリズムおよび装置に関する。
【背景技術】
【０００２】
暗号化マスキング方法が、参考文献であるダグラス・スティンソン（Douglas Stinson）著、「暗号法，理論および実践（Cryptography, Theory and Practice）」、CRC Press，1995（本明細書では「Ｓｔｉｎｓｏｎ」として示されている）に記載されている。非侵害的攻撃の技術と、秘密モジュラス（confidential moduli）のマスキングとの説明が、シャミル（Shamir）に対する米国特許第５，９９１，４１５号（本明細書では「Ｓｈａｍｉｒ」として示されている）に開示されている。マスキング方法は、さらに、コッチャー他（Kocher et al.）他に対する米国特許第６，２９８，４４２号（本明細書では「Ｋｏｃｈｅｒ」として示されている）、および、ジョー他（Joye et al.）の国際特許出願公開ＷＯ０３０１４９１６（本明細書では「Ｊｏｙｅ」として示されている）にも開示されている。
【０００３】
モンゴメリー演算（Montgomery arithmetic)が、ピーター・モンゴメリー（Peter Montgomery）によって「試行除算不要のモジュレータ乗算（Modular Multiplication Without Trial Division）」、Mathematics of Computation，44（1985）において最初に言及された。モンゴメリー演算方法および装置が米国特許第６，１８５，５９６号（本明細書では「５９６」として示されている）に開示されている。
【０００４】
上記明細書で述べられているすべての公開の開示内容と、その中で引用されている出版物の開示内容とが、本明細書に引例として組み入れられている。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
公開鍵暗号化システムの多くが、モジューロ累乗（modulo exponentiation）を使用し、および、こうした暗号化システムにおける共通の演算が、メッセージを累乗することである。例えば、暗号化が、平文メッセージを公開指数で累乗してよく、および、暗号解読が、暗号文をプライベート（秘密）指数で累乗することを含んでよい。本明細書では、術語「メッセージ」が、暗号化、暗号解読、ディジタル署名、承認、および、認証を非限定的に含む目的のための、暗号化アルゴリズムに対するあらゆる入力を意味する。本明細書では、術語「プライベートの」および「秘密の」は、公開鍵暗号システムのプライベート鍵に関連した情報を意味する。
【０００６】
累乗を行う公知の方法が、指数の「１」ビットに対応する選択的な乗算による２乗の反復を含む。この方法または類似の方法を使用して累乗を行う装置が、例えば電力消費監視のような様々な物理的手段によって秘密指数を読み出すために、累乗プロセス中にこの装置が（非侵害的に）外部から監視される可能性があるので、セキュリティ保護されていないことがある。例えば、特定の値であるようにメッセージを選択すること（「選択メッセージ攻撃」）が、累乗中に乗算演算を行っている時に、検出可能な電力差をその装置が消費することを強制する可能性があり、および、この検出可能な差が秘密指数の「１」ビットの場所を明らかにする可能性がある。秘密鍵が暗号化装置から抽出されることを可能にする電力分析の公知の方法が数多く存在する。従って、電力分析に基づいた選択メッセージ攻撃に対するこの装置の脆弱性が、セキュリティ上の危険要素である。電力分析に加えて、この装置から放出される放射の検出を含む、セキュリティ保護されていることが意図されている装置に対して攻撃を加える他の非侵害的な手法が存在する。これらの方法は、秘密鍵値がそれから推定されることが可能な情報を明らかにするあらゆる外部検出可能で測定可能な物理的現象に依拠することが可能である。
【０００７】
様々な技術が、こうした装置の内部演算を偽装または隠蔽するために使用されている。公知の技術が、（電力消費または放射放出のような）類似した物理的効果を生じさせるダミー演算を行うことであるが、このダミー演算の結果は簡単に廃棄されるか、または、出力に影響を与えない。しかし、選択メッセージ攻撃を分析することによって、ダミー演算の使用にも係わらず、挿入されたダミー演算を識別し、および、これによって秘密鍵情報を求めることが計算によって可能である。
【０００８】
選択メッセージ攻撃戦略を妨害するためには、メッセージ自体に対して直接的に重要な計算を行わず、むしろ、好ましくはランダムな入力をとるメッセージのマスキング関数によって、メッセージから得られた中間値に対して計算を行うことが、最善であると考えられる。当然であるが、このことは、このマスキング関数の効果が結果から除去可能であることを必要とする。
【０００９】
参照されるエルガマルシステム（ElGamal system）は、次のように使用される。
すなわち、ａは暗号化メッセージの受信者だけに知られている秘密鍵であり、ｘはそのシステムの送信者によって暗号化されて送信されるべきメッセージであり、且つ、公衆に知られている要素であり、ｐは法（モジュラス：modulus）であり、αは指数底であり、そして、受信者の公開鍵βは、β＝αa ｍｏｄ ｐとして与える。
【００１０】
送信者がｙ1とｙ2を秘密裏に用意して送信し、ここで、
ｙ1＝αk ｍｏｄ ｐであり、前式中で、ｋは、送信者によって生成されたランダムなマスキング指数であり、
ｙ2＝ｘβk ｍｏｄ ｐ＝ｘαakであり、メッセージｘは受信者の公開鍵を乗算されている。
【００１１】
その次に、送信されたメッセージｙ1、ｙ2を使用して、受信者が次を行い、
Ｍ1＝ｙ1a＝αak ｍｏｄ ｐ、ｙ1をａ（受信者秘密）で累乗する。
Ｍ2＝Ｍ1-1 ｍｏｄ ｐ＝(αak)-1 ｍｏｄ ｐ＝(αak)p-2 ｍｏｄ ｐ、受信者がＭ1を反転させる。
Ｍ3＝ｙ2Ｍ2＝ｘ(αak)(αak)-1 ｍｏｄ ｐ＝ｘ、リトリーブされたマスクされたメッセージ。
【００１２】
受信者が秘密ランダムマスクを知らないということに留意されたい。受信者と送信者の両方によって消費されたリソースが２つの累乗から成り、および、これは両方の場合とも典型的に冗長な演算である。
【００１３】
逆数の累乗（powers）も逆数である。例えば、
５*９ ｍｏｄ １１≡0１、従って、５と９は１１を法とした逆数である。
(５7 ｍｏｄ １１)≡３；および、((５-1)7) ｍｏｄ １１)≡(９7 ｍｏｄ １１)≡４
(３*４) ｍｏｄ １１≡１；従って、３と４も１１を法（modulo）とした逆数である。
【００１４】
計算効率を向上させるために一般的に使用される幾つかの方法も、メッセージ自体に対してではなくてメッセージの関数に対して計算を効果的に行うことによって、セキュリティ上の危険要素を低減させる働きをするだろう。特に、モンゴメリー演算の使用が、モジューロ剰余（modulo remainder）を得るために乗算の後に除算演算を行う必要を取り除くことによって、乗算の速度を向上させることが可能であるということが当業で公知である。信頼できるセキュリティ保護のためには、メッセージ自体に対して適用され且つその唯一の目的が選択メッセージ攻撃を妨害することである、モンゴメリー演算に基づいたさらに別のマスキング技術を使用することが望ましい。
【００１５】
マスキング技術はＳｈａｍｉｒの方法を含んでよく、この方法は、プライムモジュラスを複合モジュラスに変換し、これによってマシンオペランドのサイズと秘密指数とを変化させる。しかし、Ｓｈａｍｉｒの方法は、ユーザが暗号化モジュラスの素因数の知識を有することを想定しているが、これが当てはまらないこともある。さらに、オペランドのサイズを変化させることが、大半のハードウェア装置における性能に大きな悪影響を与える。攻撃に対する他の幾つかの保護方法が有効ではないことがある。例えば、Ｊｏｙｅは、Ｋｏｃｈｅｒにおいて示唆されている合同指数の使用の無効性を実証している。
【課題を解決するための手段】
【００１６】
本発明の好ましい実施態様は、反転演算を行う必要なしに、且つ、暗号化モジュラスの素因数を知る必要なしに、累乗されたメッセージが容易に復元されることを可能にする形でさらにメッセージをマスクすることによって、モンゴメリー表現の自然マスキングを強化するための方法および装置を提供することを求める。
【００１７】
本発明の好ましい実施態様は、秘密指数のような秘密鍵情報を明らかにすることが意図されている選択メッセージ攻撃を妨害するために、セキュリティ保護された装置に対する入力メッセージをランダムにマスクするための新規の方法および装置を提供する。本発明の好ましい実施態様の目的が、性能を低下させることなしに、且つ、最小限のリソースを使用して、特に、モジューロ乗算逆数（modulo multiplicative inverses）を生成する必要なしに、このマスキングを実現することである。本発明の好ましい実施態様が、逆数を明示的に生成する必要なしにマスクされたリトリーバルを維持するために、モンゴメリー演算の自然属性を新規の形で使用する。特に、自然モンゴメリー逆数２-nが存在し、前式中でｎはモジュラスのビット数であり、および、本発明の好ましい実施態様によって、この自然モンゴメリー逆数２-nから新規のマスクを構成することが可能である。
【００１８】
本発明の好ましい実施態様の方法または装置の使用は、攻撃から保護するために有効な他の保護方法または保護装置の使用を排除せず、および、典型的には、こうした方法を強化する働きをする。
【００１９】
本発明の好ましい実施態様は、ディフィーヘルマン（Diffie-Hellman）鍵交換累乗と、乱数のＤＳＳ逆数と、複合モジュラスに対するユーザ秘密鍵によるＲＳＡタイプの暗号解読とをマスクするために特に有利である。
【００２０】
従って、本発明の好ましい実施態様では、バイナリモジュラスＮを法として秘密指数ｄで暗号文メッセージを累乗する働きをする装置に入力される暗号文メッセージをマスクするための方法が提供され、このバイナリモジュラスＮはｎ個のビットを有し、および、この方法は、マスクを生成するために自然モンゴメリー逆数２-nを使用することを含む。これに加えて、本発明の好ましい実施態様では、バイナリモジュラスＮを法として秘密指数ｄで暗号文メッセージを累乗する働きをする装置に入力される暗号文メッセージをマスクするための装置も提供され、このバイナリモジュラスＮはｎ個のビットを有し、および、この装置は、自然モンゴメリー逆数２-nからマスクを生成する働きをするマスクジェネレータを含む。
【００２１】
さらに、本発明の好ましい実施態様によって、バイナリモジュラスＮを法として秘密指数ｄで暗号文メッセージを累乗する働きをする装置に入力される暗号文メッセージをマスクするための方法が提供され、このバイナリモジュラスＮはｎ個のビットを有し、および、この方法は、（ａ）ランダム整数ｘを生成することと、（ｂ）数２nx ｍｏｄ Ｎに等しいマスクを計算することと、（ｃ）数２-nxd ｍｏｄ Ｎに等しいメッセージリトリーバ（message retriever）を計算することと、（ｄ）積を形成するためにマスクを暗号文メッセージに乗算することと、（ｅ）マスクされた累乗メッセージを形成するために、その積をバイナリモジュラスＮを法として秘密指数ｄで累乗することと、（ｆ）リトリーブされた平文メッセージを形成するために、マスクされた累乗メッセージにメッセージリトリーバを乗算することとを含む。
【００２２】
さらに、本発明の好ましい実施態様によって、バイナリモジュラスＮを法として秘密指数ｄで暗号文メッセージを累乗する働きをする装置に入力される暗号文メッセージをマスクするための装置も提供され、バイナリモジュラスＮはｎ個のビットを有し、および、この装置は、（ａ）バイナリモジュラスＮを法として２つの数の積を計算し、および、バイナリモジュラスＮを法として数をｄで累乗する働きをするモジューロプロセッサと、（ｂ）ランダム整数ｘを生成するためのランダム整数ジェネレータと、（ｃ）モジューロプロセッサが、バイナリモジュラスＮを法として暗号文メッセージとマスクとの積を計算し、および、マスクされたメッセージを計算するために、バイナリモジュラスＮを法として指数ｄでその積を累乗するように、数２nx ｍｏｄ Ｎに等しいマスクを計算してモジューロプロセッサにそのマスクを送り込む働きをするマスクジェネレータと、（ｄ）モジューロプロセッサが、平文メッセージを形成するために、マスクされたメッセージとメッセージリトリーバとの積を計算するように、２-nxd ｍｏｄ Ｎに等しいメッセージリトリーバを計算して、そのメッセージリトリーバをモジューロプロセッサに送り込む働きをするメッセージリトリーバジェネレータとを含む。
【発明を実施するための最良の形態】
【００２３】
以下、本発明を、例示だけのための添付図面を参照しつつ説明する。
【実施例】
【００２４】
セキュリティ面の課題が、放射、測定された一時的な電流消費、または、他の非侵害的な物理的手段によって、ｄまたはＮを全面的または部分的に暴露（漏洩）することなしに、選択メッセージ累乗Ｍid ｍｏｄ Ｎを生成することであり、前式中で各々のＭiがメッセージであり、ｄが秘密指数であり、Ｎがｎビットのモジュラスである。数がバイナリ形式で表現されるということが理解される。
【００２５】
この装置はＮとｄの両方を含む。典型的には、攻撃者はＮの知識を有し、および、秘密ｄの１とゼロのシーケンスを知ることを望む。選択メッセージ攻撃では、攻撃者は、典型的には、検出可能な指数シーケンスを形成するために１つまたは多数のＭiを試す。
【００２６】
従来技術のモンゴメリーモジューロ演算プロセッサが、図１の単純化されたブロック図に示されている。このプロセッサの中心要素がマルチプレクサ１４０であり、このマルチプレクサ１４０は、Ａだけを含む加数１１０と、Ｎだけを含む加数１２０と、和Ａ＋Ｎを含む加数１３０との中の１つから選択された加数との入力加数Ｂを合計を行うために、ジェネレータ１５０から入力を受け取る。この演算が常にｍｏｄ Ｎ演算なので、任意の量にＮを加算することがその結果の合同を変化させないということが指摘されなければならない。しかし、（実際の適用において）Ｎが典型的には奇数なので、典型的にはＮの最下位ビットが設定されるだろう。モンゴメリー演算の特有の特徴が、結果が２nを乗算された数であるように演算を操作することである。そうすることが、モジューロ約分のために結果に対して除算を行う必要を排除する。この演算の各部分において、入力加数Ｂと入力加数Ａとが、これらの合計の最下位ビットを求めるために調べられる。Ａが偶数（最下位ビットがゼロである）である場合には、Ａ＋Ｎは奇数（最下位ビットが１である）だろうし、その逆も同様だろう。従って、マルチプレクサ１４０は、桁上げ保存加算器１６０に送られる時に和Ａ＋Ｂを偶数（最下位ビットがゼロである）にするために、どの入力が必要とされるかを選択するように設定されることが可能である。
【００２７】
本発明の好ましい実施形態によるこのマスクは、攻撃者が乗算演算と２乗計算とを区別することが不可能であるように、または、実際には、メッセージの互いに異なる電力による乗算の間を区別することが不可能であるように、統計量をバランスさせることによって、乗算および２乗プロセス中に、放射および電流消費のような外部から可視的な物理的効果を隠蔽および秘匿するように構成されている。
【００２８】
基本的なモンゴメリーモジューロ乗算関数は次のものを含む。
Ｈ＝２2n ｍｏｄ Ｎ （１）
が、モンゴメリーリトリーバル変換定数（Montgomery retrieval transformation constant）である。典型的には、Ｈは剰余除算を使用して計算される。しかし、モンゴメリー乗算が除算よりも効率的である用途においては、Ｈは次のように計算されてもよく、
Ｈ１＝２(n+n/2)、
Ｈ＝Ｐ(Ｈ１・Ｈ１)Ｎ＝２(n+n/2)・２(n+n/2)・２-n ｍｏｄ Ｎ＝２2n
である。
【００２９】
上述の手法が、Ｈの直前のＨ１、Ｈ２、．．．を計算するために、次のように反復的に使用されることが可能であり、次式中でｘが整数であり、
Ｈｘ＝２(n+n/(2∧x))であり、
一方、（ｘ＞０）、
Ｈ(ｘ−１)＝Ｐ(Ｈｘ・Ｈｘ)Ｎ＝２(n+n/x)・２(n+n/x)・２-n ｍｏｄ Ｎ＝２(n+n/(2∧(x-1))であり、
最後に、Ｈ＝２(n+n)＝２2n ｍｏｄ Ｎである。
【００３０】
Ｐフィールドにおけるモンゴメリー演算子
Ｐ(ｘ・ｙ)Ｎ＝ｘ・ｙ・２-n ｍｏｄ Ｎ （２）
が、各々のＰフィールドモンゴメリー２乗または乗算において「モンゴメリーパラサイト（Montgomery parasite）」２-n ｍｏｄ Ｎを導入する。
【００３１】
式（１）のＨ定数が、メッセージＭのための容易にリトリーブ可能なモンゴメリー乗数を生成するために使用され、
Ａ＝Ｐ(Ｍ・Ｈ)Ｎ＝Ｍ・２2n・２-n ｍｏｄ Ｎ＝Ｍ・２n （３）
Ａ、Ｈ、および、後続の結果はｎビットのオペランドである。
【００３２】
Ｐフィールドで乗算を行うこと、オペランドＡ'＝Ａ・２n ｍｏｄ ＮとオペランドＢ'＝Ｂ・２n ｍｏｄ Ｎの両方が、式（３）の通りに２n ｍｏｄ Ｎが事前に乗算されたモンゴメリーオペランドであり、
Ｐ(Ａ'・Ｂ')Ｎ＝Ａ・Ｂ・２n ｍｏｄ Ｎ （４）
である。
【００３３】
Ｘの計算、Ａ＝Ｍ・２nのｄ乗のモンゴメリー累乗であり、
Ｘ((Ａ)d)Ｎ＝Ｘ((Ｍ・２n)d)Ｎ＝(Ｍ)d・２n ｍｏｄ Ｎ （５）
および、
モジューロ自然整数のフィールドに対するモンゴメリー累乗結果の、Ｐフィールドからのオペランドのリトリーブは、
Ｐ((Ｍ)d・２n)・(１))Ｎ＝Ｍd・２n・１・２-n ｍｏｄ Ｎ＝Ｍd ｍｏｄ Ｎ （６）
である。
【００３４】
次では、２nx ｍｏｄ Ｎマスクが、典型的には、従来の方法すなわちモンゴメリーの方法を使用して累乗を行う間にオペランドの値をマスクするために使用される。
【００３５】
従来のモンゴメリー演算は、典型的には、メッセージＭをとることと、式（３）の通りにＨ＝２2n ｍｏｄ Ｎをモンゴメリー乗算することとによって開始する。本発明の好ましい実施形態では、メッセージが累乗のために用意され、および、２xn ｍｏｄ Ｎによってマスクされ、前式中でｘは乱数である。これとは対照的に、従来技術のマスクは単純に乱数ｘ自体である。しかし、上述したように、このことは、因数ｘdが累乗結果に現れ、および、逆数ｘ-dを乗算することによって取り除かれなければならないということを意味する。このことは、逆数ｘ-1を計算することが可能であることを必要とする。しかし、本発明の好ましい実施形態の新規のマスクである２xn ｍｏｄ Ｎは、典型的には、乱数ｘの逆数を計算することなしに、容易に取り除かれる。
【００３６】
本発明の好ましい実施形態では、このマスクは、典型的には、セキュリティ保護された装置の初期設定において事前計算される。さらに、ユーザの方針によって必要とされる場合には、その装置の各リセット毎にマスクを復元することも可能である。上述したように、本発明の好ましい実施形態の使用は、ダミーインサートのような他のセキュリティ保護方法を排除せず、または、こうした他のセキュリティ保護方法に干渉しない。
【００３７】
この着想はモンゴメリー演算によって容易に実証される。
【００３８】
例えば、ｄ＝７を選択して、乱数ｘ＝２によってマスクされた、マスクされたシーケンス中にＭ7 ｍｏｄ Ｎを発見する。
【００３９】
通常のモンゴメリー演算において計算する代わりに、Ｍに２xn ｍｏｄ Ｎマスクが乗算される。この最終のモンゴメリー累乗がマスクされ、および、例えば次のように、容易に導出されるマスクされた逆数によってリトリーブされることが可能であり、
（ａ）剰余除算によって、または、知的所有権があるモンゴメリー方法を使用して、Ｈ2＝２4n ｍｏｄ Ｎ −−（この場合には、ｘ＝２）を生成し、
（ｂ）マスク２xnを生成するマスクされたメッセージを用意し、および、このメッセージに関して、反転された２-yn ｍｏｄ Ｎが生成されることが可能であり、
Ｐ(Ｍ・Ｈ2)Ｎ＝Ｍ・２4n・２-n ｍｏｄ Ｎ＝Ｍ・２3n＝Ａ （７）
（ｃ）チャンドハスートラ（Chandah-sutra）法を使用してＡに対してモンゴメリー累乗を行う。チャンドハスートラ累乗法は、ドナルド・ナス（Donald Knuth）による「コンピュータプログラミング技術（The Art of Computer programming）」，２nd Edition，Volume 2，Addison Wesley，1981（本明細書では「Ｋｎｕｔｈ」として示す）の４４１ページに説明されている。
【００４０】
Ｐ(Ａ・Ａ)Ｎ＝Ｐ(Ａ12)Ｎ＝Ｍ・２3n・Ｍ・２3n・２-n ｍｏｄ Ｎ＝Ｍ2・２5n ｍｏｄ Ｎ （８）、
Ｐ(Ｐ(Ａ12)Ｎ・Ａ)Ｎ＝Ｐ(Ａ23)Ｎ＝Ｍ3・２5n・２3n・２-n＝Ｍ3・２7n （９）、
Ｐ((Ｐ(Ａ23)Ｎ)・(Ｐ(Ａ23)Ｎ))Ｎ＝Ｐ(Ａ36)Ｎ＝Ｍ3・２7n・Ｍ3・２7n・２-n ｍｏｄ Ｎ （１０）
Ｐ((Ｐ(Ａ23)Ｎ)・(Ｐ(Ａ23)Ｎ))Ｎ＝Ｍ6・２13n ｍｏｄ Ｎ （１１）
Ｐ((Ｐ(Ａ36)Ｎ)・Ａ)Ｎ＝Ｐ(Ａ47)Ｎ＝Ｍ6・２13n・Ｍ・２3n・２-n ｍｏｄ Ｎ （１２）
Ｐ((Ｐ(Ａ36)Ｎ)・Ａ)Ｎ＝Ｍ7・２15n ｍｏｄ Ｎ （１３）
【００４１】
リトリーバルマスクの生成がモンゴメリーパラサイト ２-n ｍｏｄ Ｎに基づいており、これが単一のモンゴメリー乗算によって得られることが好ましく、
Ｐ(１・１)Ｎ＝２-n ｍｏｄ Ｎ （１４）
であり、その次に、典型的には、類似の累乗手順がこのマスクリトリーバル値を２-14n ｍｏｄ Ｎ＝Ｙに累乗する。
【００４２】
次に、Ｐフィールドからのリトリーバルとマスクの除去とが、典型的には、指数量時間Ｙの単一のモンゴメリー乗算において行われ、
Ｍ7 ｍｏｄ Ｎ＝Ｐ((Ｍ7・２15n)・２-14n)Ｎ＝Ｍ7・２n・２-n ｍｏｄ Ｎ （１５）
である。
【００４３】
これは、ｅ（暗号化指数）が既知でない時にさえ、選択されたメッセージの暗号解読シーケンスが、典型的には、Ｎのトーティエント関数の知識なしに生成されるということを示す。
【００４４】
一般的に、指数乗数ｘが２xn ｍｏｄ Ｎランダムマスクにおいて９０よりも大きい場合には、攻撃者は、選択メッセージ攻撃を行うためにそのマスクを導出することもそのランダムマスクによって選択メッセージを形成することも不可能である。
【００４５】
限定されたモンゴメリー能力を有するかまたは拡張ユークリッド逆数を有する装置のためのモンゴメリーマスク法。
【００４６】
図２は、本発明の第１の実施形態によるモンゴメリーマスクとメッセージリトリーバとを用意する好ましいシーケンスを示す流れ図である。
【００４７】
ステップ２１０では、秘密指数ｄとｎビットモジュラスＮが入力され、ここでｄとＮは整数であり、および、Ｈが式（１）に従って計算される。Ｈ1/2＝２n ｍｏｄ Ｎが単一の整数減法によって計算され、
２n−Ｎ≡２n ｍｏｄ Ｎ （１６）
である。
【００４８】
その次に、ステップ２２０において、Ｈ-1/2が計算され、上述の式（１４）の通りに、
Ｈ-1/2＝２-n ｍｏｄ Ｎ≡Ｐ(１・１)Ｎ＝２-n ｍｏｄ Ｎ
である。
【００４９】
ステップ２３０では、秘密数ｘが生成される。秘密ｘを明らかにするために徹底的な探索を行うには２90のワークファクタ（work factor）が必要であるとすれば、ｘが少なくとも９０であることが好ましい。
【００５０】
ステップ２５０では、マスク逆数Ｋ1が計算され、
Ｋ1＝２nx ｍｏｄ Ｎ＝(２n)x ｍｏｄ Ｎ （１７）
である。
【００５１】
ステップ２６０では、メッセージリトリーバＫ2が計算され、
Ｋ2＝２-nxd ｍｏｄ Ｎ＝((２-n)x)d ｍｏｄ Ｎ （１８）
である。
【００５２】
Ｋ1とＫ2は、必要に応じて、次のようにｘ'によって更新されてよく、
Ｋ1'＝((Ｋ1) ｍｏｄ Ｎ)x' ｍｏｄ Ｎ （１９）
Ｋ2'＝((Ｋ2) ｍｏｄ Ｎ)x' ｍｏｄ Ｎ （２０）
であり、前式中でｘ'は、典型的には、ランダムに選択された小さい正の整数である。
【００５３】
図３は、選択メッセージ攻撃に対して抵抗性があるマスクされた累乗を暗号文Ｃに対して行うための、本発明の第２の実施形態による、入力メッセージに対するモンゴメリーマスクの使用のシーケンスを示す流れ図であり、この場合に（例えば、記憶装置内で）ｄ、Ｎ、Ｋ1、Ｋ2が使用可能である。
【００５４】
ステップ３１０では、暗号文Ｃが入力され、この暗号文ＣからＣ ｍｏｄ Ｎが計算されることが可能である。
【００５５】
ステップ３２０では、（例えば、記憶装置から）Ｎ、ｄ、Ｋ1、Ｋ2が入力される。
【００５６】
ステップ３３０では、モジューロ乗算によってマスクされた暗号文を得るために、Ａ1＝Ｃ*Ｋ1 ｍｏｄ Ｎを計算する。
【００５７】
ステップ３４０では、Ａ2＝Ａ1d ｍｏｄ Ｎを計算する。マスクされたモジューロ累乗＝(Ｃ*Ｋ1)d ｍｏｄ Ｎ＝Ｍ*２nxd ｍｏｄ Ｎ
である。
【００５８】
ステップ３５０では、平文Ｍをリトリーブする。
Ｍ＝Ｃd ｍｏｄ Ｎ＝Ａ2*Ｋ2 ｍｏｄ Ｎ＝((Ｃd)(２ndx))(２-ndx) ｍｏｄ Ｎ
【００５９】
加えられる唯一のリソースが、記憶装置内に格納されるべきｎビット定数Ｋ1、Ｋ2である。
【００６０】
好ましい装置の実施形態におけるマスクされたモンゴメリー累乗。
【００６１】
Ｈ＝２2n ｍｏｄ Ｎがモジューロ除算によって計算されることが可能である。
【００６２】
Ｈ-1/2＝２-n ｍｏｄ Ｎ≡Ｐ(１・１)Ｎ＝((１・１)２-n) ｍｏｄ Ｎ、２n ｍｏｄ Ｎの逆数。
【００６３】
秘密ｘを明らかにするために徹底的な探索を行うには２90のワークファクタが適切であると仮定する場合に、ｘ＝秘密乱数、２≦ｘ≦９５、好ましくは９０≦ｘである。その次に、Ｋ1を事前計算するために、
Ｍ1＝Ｘ((Ｈ)x)Ｎ＝Ｘ(２n・２n)x＝２nx・２n ｍｏｄ Ｎ、
Ｋ1＝Ｐ(Ｈ・Ｍ1)Ｎ＝２2n・２n・２nx・２n・２-n ｍｏｄ Ｎ＝２nx・２2n ｍｏｄ Ｎ
である。
【００６４】
Ｋ2を事前計算する時に、２-n・２n ｍｏｄ Ｎ＝１ ｍｏｄ Ｎであることに留意されたい。
【００６５】
Ｍ2＝Ｘ(１x)Ｎ＝Ｘ((２-n・２n)x)Ｎ＝２-nx・２n
Ｍ3＝Ｘ((Ｍ2)d)Ｎ＝Ｘ((２-nx・２n)d)Ｎ＝２-nxd・２n
Ｋ2＝Ｐ(Ｍ3・１)Ｎ＝２-nxd ｍｏｄ Ｎ。
【００６６】
Ｋ1とＫ2が典型的には、小さい正の整数であるｘ'によって更新される。
Ｋ1←Ｋ1'＝((Ｋ1) ｍｏｄ Ｎ)x' ｍｏｄ Ｎ
Ｍ4＝Ｘ((Ｍ3)x')Ｎ＝Ｘ(((２-nx・２n)d)x')Ｎ＝２-nxx'd・２ｎ
Ｋ2←Ｋ2'＝Ｐ(Ｍ4・１)Ｎ＝２-nxx'd ｍｏｄ Ｎ
【００６７】
図４は、選択メッセージ攻撃に対して抵抗性があるマスクされた累乗を選択された暗号文に対して行って、Ｃd ｍｏｄ Ｎを計算するために、モジューロ乗算装置上で動作可能なモンゴメリー関数を使用する、本発明の第３の実施形態における入力メッセージに対するモンゴメリーマスクの使用のシーケンスを示す流れ図である。次の演算を行う。
【００６８】
ステップ４１０では、マスクされていない暗号文メッセージＣを入力または生成する。ステップ４２０では、秘密指数ｄと、ｎビットモジュラスＮと、マスクＫ1と、メッセージリトリーバＫ2とを入力する。これらは次に詳細を示すように計算される。
【００６９】
ステップ４３０では、暗号文に対するモンゴメリーマスクを計算し、
Ａ1＝Ｐ(Ｃ・Ｋ1)Ｎ＝(Ｃ・２nx)・２n ｍｏｄ Ｎ
である。
【００７０】
ステップ４４０では、モンゴメリーマスク指数を計算し、
Ａ2＝Ｐ(((Ｃ・２nx)・２n)d)Ｎ＝Ｃd・２nxd・２n ｍｏｄ Ｎ
である。
【００７１】
ステップ４５０では、モンゴメリー Ｐフィールドから結果をリトリーブし、
Ｃd ｍｏｄ Ｎ＝Ｐ((Ａ2・Ｋ2))Ｎ＝Ｐ((Ｃd・２nxd・２n)(２-nxd))Ｎ
である。
【００７２】
セキュリティ保護の観点から、Ｋ1とＫ2は、一般的に、上述したように更新される。
【００７３】
このマスクされた累乗は各累乗の前のＨの生成を排除し、典型的には、同じ回数の乗算と２乗とによるプロセス時間の４％を節約する。
【００７４】
図５は、図４に示されている方法のような任意の適切な方法と共に使用されることが可能な、本発明の第４の実施形態によるメッセージのマスキングおよびリトリービングのための装置の単純化されたブロック図である。モジューロプロセッサ５１０がモジュラス５２０と指数５３０とを受け取る。乱数ジェネレータ５４０が、マスクジェネレータ５５０とメッセージリトリーバジェネレータ５６０とに対してランダムな整数を提供する。暗号文メッセージ５７０がモジューロプロセッサ５１０に入力され、および、このモジューロプロセッサ５１０は平文メッセージ５８０を出力する。本発明の別の実施形態では、モジューロプロセッサ５１０は従来の仕方でモジューロ演算を行う。しかし、本発明のさらに別の実施形態では、モジューロプロセッサ５１０はモンゴメリー演算を行う。
【００７５】
本発明を限られた数の実施形態に関して説明してきたが、本発明の多くの変型と変更と他の適用とが行われてよいということが理解されるだろう。
【００７６】
本発明のソフトウェア構成要素が、必要に応じて、ＲＯＭ（読み出し専用メモリ）形態で実現されてよいということが理解される。このソフトウェア構成要素は、一般的に、必要に応じて、従来の技術を使用してハードウェアの形で実現されてよい。
【００７７】
理解しやすいように別々の実施形態の文脈において説明されている本発明の様々な特徴が、単一の実施形態において組合せの形で実現されてもよいということが理解される。これとは逆に、簡潔にするために単一の実施形態の文脈において説明されている本発明の様々な特徴が、別々に、または、任意の適切な副次的な組合せの形で実現されてもよい。
【００７８】
本明細書に詳細に示され説明されているものだけに本発明が限定されないということが、当業者に理解されるだろう。むしろ、本発明の範囲は特許請求項だけによって規定される。
【図面の簡単な説明】
【００７９】
【図１】従来技術のモンゴメリーモジューロ演算プロセッサの単純化されたブロック図である。
【図２】本発明の好ましい実施形態によるモンゴメリーマスクとメッセージリトリーバとを用意するシーケンスを示す流れ図である。
【図３】本発明の好ましい実施形態による、入力メッセージに対して図２のモンゴメリーマスクを使用するシーケンスを示す流れ図である。
【図４】本発明の好ましい実施形態による、図１または図５に示されているモンゴメリーモジューロ乗算装置上において動作可能なモンゴメリー関数を使用する、入力メッセージに対してモンゴメリーマスクを使用することを含む、図３の方法の好ましい具体例を示す流れ図である。
【図５】本発明の好ましい実施形態によってメッセージをマスクおよびリトリーブするための装置の単純化されたブロック図である。
【技術分野】
【０００１】
本発明は、暗号技術の分野に関し、および、特に、公開鍵暗号システムを使用するスマートカードのような、物理的攻撃に対してセキュリティ保護されていることが意図されている暗号化アルゴリズムおよび装置に関する。
【背景技術】
【０００２】
暗号化マスキング方法が、参考文献であるダグラス・スティンソン（Douglas Stinson）著、「暗号法，理論および実践（Cryptography, Theory and Practice）」、CRC Press，1995（本明細書では「Ｓｔｉｎｓｏｎ」として示されている）に記載されている。非侵害的攻撃の技術と、秘密モジュラス（confidential moduli）のマスキングとの説明が、シャミル（Shamir）に対する米国特許第５，９９１，４１５号（本明細書では「Ｓｈａｍｉｒ」として示されている）に開示されている。マスキング方法は、さらに、コッチャー他（Kocher et al.）他に対する米国特許第６，２９８，４４２号（本明細書では「Ｋｏｃｈｅｒ」として示されている）、および、ジョー他（Joye et al.）の国際特許出願公開ＷＯ０３０１４９１６（本明細書では「Ｊｏｙｅ」として示されている）にも開示されている。
【０００３】
モンゴメリー演算（Montgomery arithmetic)が、ピーター・モンゴメリー（Peter Montgomery）によって「試行除算不要のモジュレータ乗算（Modular Multiplication Without Trial Division）」、Mathematics of Computation，44（1985）において最初に言及された。モンゴメリー演算方法および装置が米国特許第６，１８５，５９６号（本明細書では「５９６」として示されている）に開示されている。
【０００４】
上記明細書で述べられているすべての公開の開示内容と、その中で引用されている出版物の開示内容とが、本明細書に引例として組み入れられている。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
公開鍵暗号化システムの多くが、モジューロ累乗（modulo exponentiation）を使用し、および、こうした暗号化システムにおける共通の演算が、メッセージを累乗することである。例えば、暗号化が、平文メッセージを公開指数で累乗してよく、および、暗号解読が、暗号文をプライベート（秘密）指数で累乗することを含んでよい。本明細書では、術語「メッセージ」が、暗号化、暗号解読、ディジタル署名、承認、および、認証を非限定的に含む目的のための、暗号化アルゴリズムに対するあらゆる入力を意味する。本明細書では、術語「プライベートの」および「秘密の」は、公開鍵暗号システムのプライベート鍵に関連した情報を意味する。
【０００６】
累乗を行う公知の方法が、指数の「１」ビットに対応する選択的な乗算による２乗の反復を含む。この方法または類似の方法を使用して累乗を行う装置が、例えば電力消費監視のような様々な物理的手段によって秘密指数を読み出すために、累乗プロセス中にこの装置が（非侵害的に）外部から監視される可能性があるので、セキュリティ保護されていないことがある。例えば、特定の値であるようにメッセージを選択すること（「選択メッセージ攻撃」）が、累乗中に乗算演算を行っている時に、検出可能な電力差をその装置が消費することを強制する可能性があり、および、この検出可能な差が秘密指数の「１」ビットの場所を明らかにする可能性がある。秘密鍵が暗号化装置から抽出されることを可能にする電力分析の公知の方法が数多く存在する。従って、電力分析に基づいた選択メッセージ攻撃に対するこの装置の脆弱性が、セキュリティ上の危険要素である。電力分析に加えて、この装置から放出される放射の検出を含む、セキュリティ保護されていることが意図されている装置に対して攻撃を加える他の非侵害的な手法が存在する。これらの方法は、秘密鍵値がそれから推定されることが可能な情報を明らかにするあらゆる外部検出可能で測定可能な物理的現象に依拠することが可能である。
【０００７】
様々な技術が、こうした装置の内部演算を偽装または隠蔽するために使用されている。公知の技術が、（電力消費または放射放出のような）類似した物理的効果を生じさせるダミー演算を行うことであるが、このダミー演算の結果は簡単に廃棄されるか、または、出力に影響を与えない。しかし、選択メッセージ攻撃を分析することによって、ダミー演算の使用にも係わらず、挿入されたダミー演算を識別し、および、これによって秘密鍵情報を求めることが計算によって可能である。
【０００８】
選択メッセージ攻撃戦略を妨害するためには、メッセージ自体に対して直接的に重要な計算を行わず、むしろ、好ましくはランダムな入力をとるメッセージのマスキング関数によって、メッセージから得られた中間値に対して計算を行うことが、最善であると考えられる。当然であるが、このことは、このマスキング関数の効果が結果から除去可能であることを必要とする。
【０００９】
参照されるエルガマルシステム（ElGamal system）は、次のように使用される。
すなわち、ａは暗号化メッセージの受信者だけに知られている秘密鍵であり、ｘはそのシステムの送信者によって暗号化されて送信されるべきメッセージであり、且つ、公衆に知られている要素であり、ｐは法（モジュラス：modulus）であり、αは指数底であり、そして、受信者の公開鍵βは、β＝αa ｍｏｄ ｐとして与える。
【００１０】
送信者がｙ1とｙ2を秘密裏に用意して送信し、ここで、
ｙ1＝αk ｍｏｄ ｐであり、前式中で、ｋは、送信者によって生成されたランダムなマスキング指数であり、
ｙ2＝ｘβk ｍｏｄ ｐ＝ｘαakであり、メッセージｘは受信者の公開鍵を乗算されている。
【００１１】
その次に、送信されたメッセージｙ1、ｙ2を使用して、受信者が次を行い、
Ｍ1＝ｙ1a＝αak ｍｏｄ ｐ、ｙ1をａ（受信者秘密）で累乗する。
Ｍ2＝Ｍ1-1 ｍｏｄ ｐ＝(αak)-1 ｍｏｄ ｐ＝(αak)p-2 ｍｏｄ ｐ、受信者がＭ1を反転させる。
Ｍ3＝ｙ2Ｍ2＝ｘ(αak)(αak)-1 ｍｏｄ ｐ＝ｘ、リトリーブされたマスクされたメッセージ。
【００１２】
受信者が秘密ランダムマスクを知らないということに留意されたい。受信者と送信者の両方によって消費されたリソースが２つの累乗から成り、および、これは両方の場合とも典型的に冗長な演算である。
【００１３】
逆数の累乗（powers）も逆数である。例えば、
５*９ ｍｏｄ １１≡0１、従って、５と９は１１を法とした逆数である。
(５7 ｍｏｄ １１)≡３；および、((５-1)7) ｍｏｄ １１)≡(９7 ｍｏｄ １１)≡４
(３*４) ｍｏｄ １１≡１；従って、３と４も１１を法（modulo）とした逆数である。
【００１４】
計算効率を向上させるために一般的に使用される幾つかの方法も、メッセージ自体に対してではなくてメッセージの関数に対して計算を効果的に行うことによって、セキュリティ上の危険要素を低減させる働きをするだろう。特に、モンゴメリー演算の使用が、モジューロ剰余（modulo remainder）を得るために乗算の後に除算演算を行う必要を取り除くことによって、乗算の速度を向上させることが可能であるということが当業で公知である。信頼できるセキュリティ保護のためには、メッセージ自体に対して適用され且つその唯一の目的が選択メッセージ攻撃を妨害することである、モンゴメリー演算に基づいたさらに別のマスキング技術を使用することが望ましい。
【００１５】
マスキング技術はＳｈａｍｉｒの方法を含んでよく、この方法は、プライムモジュラスを複合モジュラスに変換し、これによってマシンオペランドのサイズと秘密指数とを変化させる。しかし、Ｓｈａｍｉｒの方法は、ユーザが暗号化モジュラスの素因数の知識を有することを想定しているが、これが当てはまらないこともある。さらに、オペランドのサイズを変化させることが、大半のハードウェア装置における性能に大きな悪影響を与える。攻撃に対する他の幾つかの保護方法が有効ではないことがある。例えば、Ｊｏｙｅは、Ｋｏｃｈｅｒにおいて示唆されている合同指数の使用の無効性を実証している。
【課題を解決するための手段】
【００１６】
本発明の好ましい実施態様は、反転演算を行う必要なしに、且つ、暗号化モジュラスの素因数を知る必要なしに、累乗されたメッセージが容易に復元されることを可能にする形でさらにメッセージをマスクすることによって、モンゴメリー表現の自然マスキングを強化するための方法および装置を提供することを求める。
【００１７】
本発明の好ましい実施態様は、秘密指数のような秘密鍵情報を明らかにすることが意図されている選択メッセージ攻撃を妨害するために、セキュリティ保護された装置に対する入力メッセージをランダムにマスクするための新規の方法および装置を提供する。本発明の好ましい実施態様の目的が、性能を低下させることなしに、且つ、最小限のリソースを使用して、特に、モジューロ乗算逆数（modulo multiplicative inverses）を生成する必要なしに、このマスキングを実現することである。本発明の好ましい実施態様が、逆数を明示的に生成する必要なしにマスクされたリトリーバルを維持するために、モンゴメリー演算の自然属性を新規の形で使用する。特に、自然モンゴメリー逆数２-nが存在し、前式中でｎはモジュラスのビット数であり、および、本発明の好ましい実施態様によって、この自然モンゴメリー逆数２-nから新規のマスクを構成することが可能である。
【００１８】
本発明の好ましい実施態様の方法または装置の使用は、攻撃から保護するために有効な他の保護方法または保護装置の使用を排除せず、および、典型的には、こうした方法を強化する働きをする。
【００１９】
本発明の好ましい実施態様は、ディフィーヘルマン（Diffie-Hellman）鍵交換累乗と、乱数のＤＳＳ逆数と、複合モジュラスに対するユーザ秘密鍵によるＲＳＡタイプの暗号解読とをマスクするために特に有利である。
【００２０】
従って、本発明の好ましい実施態様では、バイナリモジュラスＮを法として秘密指数ｄで暗号文メッセージを累乗する働きをする装置に入力される暗号文メッセージをマスクするための方法が提供され、このバイナリモジュラスＮはｎ個のビットを有し、および、この方法は、マスクを生成するために自然モンゴメリー逆数２-nを使用することを含む。これに加えて、本発明の好ましい実施態様では、バイナリモジュラスＮを法として秘密指数ｄで暗号文メッセージを累乗する働きをする装置に入力される暗号文メッセージをマスクするための装置も提供され、このバイナリモジュラスＮはｎ個のビットを有し、および、この装置は、自然モンゴメリー逆数２-nからマスクを生成する働きをするマスクジェネレータを含む。
【００２１】
さらに、本発明の好ましい実施態様によって、バイナリモジュラスＮを法として秘密指数ｄで暗号文メッセージを累乗する働きをする装置に入力される暗号文メッセージをマスクするための方法が提供され、このバイナリモジュラスＮはｎ個のビットを有し、および、この方法は、（ａ）ランダム整数ｘを生成することと、（ｂ）数２nx ｍｏｄ Ｎに等しいマスクを計算することと、（ｃ）数２-nxd ｍｏｄ Ｎに等しいメッセージリトリーバ（message retriever）を計算することと、（ｄ）積を形成するためにマスクを暗号文メッセージに乗算することと、（ｅ）マスクされた累乗メッセージを形成するために、その積をバイナリモジュラスＮを法として秘密指数ｄで累乗することと、（ｆ）リトリーブされた平文メッセージを形成するために、マスクされた累乗メッセージにメッセージリトリーバを乗算することとを含む。
【００２２】
さらに、本発明の好ましい実施態様によって、バイナリモジュラスＮを法として秘密指数ｄで暗号文メッセージを累乗する働きをする装置に入力される暗号文メッセージをマスクするための装置も提供され、バイナリモジュラスＮはｎ個のビットを有し、および、この装置は、（ａ）バイナリモジュラスＮを法として２つの数の積を計算し、および、バイナリモジュラスＮを法として数をｄで累乗する働きをするモジューロプロセッサと、（ｂ）ランダム整数ｘを生成するためのランダム整数ジェネレータと、（ｃ）モジューロプロセッサが、バイナリモジュラスＮを法として暗号文メッセージとマスクとの積を計算し、および、マスクされたメッセージを計算するために、バイナリモジュラスＮを法として指数ｄでその積を累乗するように、数２nx ｍｏｄ Ｎに等しいマスクを計算してモジューロプロセッサにそのマスクを送り込む働きをするマスクジェネレータと、（ｄ）モジューロプロセッサが、平文メッセージを形成するために、マスクされたメッセージとメッセージリトリーバとの積を計算するように、２-nxd ｍｏｄ Ｎに等しいメッセージリトリーバを計算して、そのメッセージリトリーバをモジューロプロセッサに送り込む働きをするメッセージリトリーバジェネレータとを含む。
【発明を実施するための最良の形態】
【００２３】
以下、本発明を、例示だけのための添付図面を参照しつつ説明する。
【実施例】
【００２４】
セキュリティ面の課題が、放射、測定された一時的な電流消費、または、他の非侵害的な物理的手段によって、ｄまたはＮを全面的または部分的に暴露（漏洩）することなしに、選択メッセージ累乗Ｍid ｍｏｄ Ｎを生成することであり、前式中で各々のＭiがメッセージであり、ｄが秘密指数であり、Ｎがｎビットのモジュラスである。数がバイナリ形式で表現されるということが理解される。
【００２５】
この装置はＮとｄの両方を含む。典型的には、攻撃者はＮの知識を有し、および、秘密ｄの１とゼロのシーケンスを知ることを望む。選択メッセージ攻撃では、攻撃者は、典型的には、検出可能な指数シーケンスを形成するために１つまたは多数のＭiを試す。
【００２６】
従来技術のモンゴメリーモジューロ演算プロセッサが、図１の単純化されたブロック図に示されている。このプロセッサの中心要素がマルチプレクサ１４０であり、このマルチプレクサ１４０は、Ａだけを含む加数１１０と、Ｎだけを含む加数１２０と、和Ａ＋Ｎを含む加数１３０との中の１つから選択された加数との入力加数Ｂを合計を行うために、ジェネレータ１５０から入力を受け取る。この演算が常にｍｏｄ Ｎ演算なので、任意の量にＮを加算することがその結果の合同を変化させないということが指摘されなければならない。しかし、（実際の適用において）Ｎが典型的には奇数なので、典型的にはＮの最下位ビットが設定されるだろう。モンゴメリー演算の特有の特徴が、結果が２nを乗算された数であるように演算を操作することである。そうすることが、モジューロ約分のために結果に対して除算を行う必要を排除する。この演算の各部分において、入力加数Ｂと入力加数Ａとが、これらの合計の最下位ビットを求めるために調べられる。Ａが偶数（最下位ビットがゼロである）である場合には、Ａ＋Ｎは奇数（最下位ビットが１である）だろうし、その逆も同様だろう。従って、マルチプレクサ１４０は、桁上げ保存加算器１６０に送られる時に和Ａ＋Ｂを偶数（最下位ビットがゼロである）にするために、どの入力が必要とされるかを選択するように設定されることが可能である。
【００２７】
本発明の好ましい実施形態によるこのマスクは、攻撃者が乗算演算と２乗計算とを区別することが不可能であるように、または、実際には、メッセージの互いに異なる電力による乗算の間を区別することが不可能であるように、統計量をバランスさせることによって、乗算および２乗プロセス中に、放射および電流消費のような外部から可視的な物理的効果を隠蔽および秘匿するように構成されている。
【００２８】
基本的なモンゴメリーモジューロ乗算関数は次のものを含む。
Ｈ＝２2n ｍｏｄ Ｎ （１）
が、モンゴメリーリトリーバル変換定数（Montgomery retrieval transformation constant）である。典型的には、Ｈは剰余除算を使用して計算される。しかし、モンゴメリー乗算が除算よりも効率的である用途においては、Ｈは次のように計算されてもよく、
Ｈ１＝２(n+n/2)、
Ｈ＝Ｐ(Ｈ１・Ｈ１)Ｎ＝２(n+n/2)・２(n+n/2)・２-n ｍｏｄ Ｎ＝２2n
である。
【００２９】
上述の手法が、Ｈの直前のＨ１、Ｈ２、．．．を計算するために、次のように反復的に使用されることが可能であり、次式中でｘが整数であり、
Ｈｘ＝２(n+n/(2∧x))であり、
一方、（ｘ＞０）、
Ｈ(ｘ−１)＝Ｐ(Ｈｘ・Ｈｘ)Ｎ＝２(n+n/x)・２(n+n/x)・２-n ｍｏｄ Ｎ＝２(n+n/(2∧(x-1))であり、
最後に、Ｈ＝２(n+n)＝２2n ｍｏｄ Ｎである。
【００３０】
Ｐフィールドにおけるモンゴメリー演算子
Ｐ(ｘ・ｙ)Ｎ＝ｘ・ｙ・２-n ｍｏｄ Ｎ （２）
が、各々のＰフィールドモンゴメリー２乗または乗算において「モンゴメリーパラサイト（Montgomery parasite）」２-n ｍｏｄ Ｎを導入する。
【００３１】
式（１）のＨ定数が、メッセージＭのための容易にリトリーブ可能なモンゴメリー乗数を生成するために使用され、
Ａ＝Ｐ(Ｍ・Ｈ)Ｎ＝Ｍ・２2n・２-n ｍｏｄ Ｎ＝Ｍ・２n （３）
Ａ、Ｈ、および、後続の結果はｎビットのオペランドである。
【００３２】
Ｐフィールドで乗算を行うこと、オペランドＡ'＝Ａ・２n ｍｏｄ ＮとオペランドＢ'＝Ｂ・２n ｍｏｄ Ｎの両方が、式（３）の通りに２n ｍｏｄ Ｎが事前に乗算されたモンゴメリーオペランドであり、
Ｐ(Ａ'・Ｂ')Ｎ＝Ａ・Ｂ・２n ｍｏｄ Ｎ （４）
である。
【００３３】
Ｘの計算、Ａ＝Ｍ・２nのｄ乗のモンゴメリー累乗であり、
Ｘ((Ａ)d)Ｎ＝Ｘ((Ｍ・２n)d)Ｎ＝(Ｍ)d・２n ｍｏｄ Ｎ （５）
および、
モジューロ自然整数のフィールドに対するモンゴメリー累乗結果の、Ｐフィールドからのオペランドのリトリーブは、
Ｐ((Ｍ)d・２n)・(１))Ｎ＝Ｍd・２n・１・２-n ｍｏｄ Ｎ＝Ｍd ｍｏｄ Ｎ （６）
である。
【００３４】
次では、２nx ｍｏｄ Ｎマスクが、典型的には、従来の方法すなわちモンゴメリーの方法を使用して累乗を行う間にオペランドの値をマスクするために使用される。
【００３５】
従来のモンゴメリー演算は、典型的には、メッセージＭをとることと、式（３）の通りにＨ＝２2n ｍｏｄ Ｎをモンゴメリー乗算することとによって開始する。本発明の好ましい実施形態では、メッセージが累乗のために用意され、および、２xn ｍｏｄ Ｎによってマスクされ、前式中でｘは乱数である。これとは対照的に、従来技術のマスクは単純に乱数ｘ自体である。しかし、上述したように、このことは、因数ｘdが累乗結果に現れ、および、逆数ｘ-dを乗算することによって取り除かれなければならないということを意味する。このことは、逆数ｘ-1を計算することが可能であることを必要とする。しかし、本発明の好ましい実施形態の新規のマスクである２xn ｍｏｄ Ｎは、典型的には、乱数ｘの逆数を計算することなしに、容易に取り除かれる。
【００３６】
本発明の好ましい実施形態では、このマスクは、典型的には、セキュリティ保護された装置の初期設定において事前計算される。さらに、ユーザの方針によって必要とされる場合には、その装置の各リセット毎にマスクを復元することも可能である。上述したように、本発明の好ましい実施形態の使用は、ダミーインサートのような他のセキュリティ保護方法を排除せず、または、こうした他のセキュリティ保護方法に干渉しない。
【００３７】
この着想はモンゴメリー演算によって容易に実証される。
【００３８】
例えば、ｄ＝７を選択して、乱数ｘ＝２によってマスクされた、マスクされたシーケンス中にＭ7 ｍｏｄ Ｎを発見する。
【００３９】
通常のモンゴメリー演算において計算する代わりに、Ｍに２xn ｍｏｄ Ｎマスクが乗算される。この最終のモンゴメリー累乗がマスクされ、および、例えば次のように、容易に導出されるマスクされた逆数によってリトリーブされることが可能であり、
（ａ）剰余除算によって、または、知的所有権があるモンゴメリー方法を使用して、Ｈ2＝２4n ｍｏｄ Ｎ −−（この場合には、ｘ＝２）を生成し、
（ｂ）マスク２xnを生成するマスクされたメッセージを用意し、および、このメッセージに関して、反転された２-yn ｍｏｄ Ｎが生成されることが可能であり、
Ｐ(Ｍ・Ｈ2)Ｎ＝Ｍ・２4n・２-n ｍｏｄ Ｎ＝Ｍ・２3n＝Ａ （７）
（ｃ）チャンドハスートラ（Chandah-sutra）法を使用してＡに対してモンゴメリー累乗を行う。チャンドハスートラ累乗法は、ドナルド・ナス（Donald Knuth）による「コンピュータプログラミング技術（The Art of Computer programming）」，２nd Edition，Volume 2，Addison Wesley，1981（本明細書では「Ｋｎｕｔｈ」として示す）の４４１ページに説明されている。
【００４０】
Ｐ(Ａ・Ａ)Ｎ＝Ｐ(Ａ12)Ｎ＝Ｍ・２3n・Ｍ・２3n・２-n ｍｏｄ Ｎ＝Ｍ2・２5n ｍｏｄ Ｎ （８）、
Ｐ(Ｐ(Ａ12)Ｎ・Ａ)Ｎ＝Ｐ(Ａ23)Ｎ＝Ｍ3・２5n・２3n・２-n＝Ｍ3・２7n （９）、
Ｐ((Ｐ(Ａ23)Ｎ)・(Ｐ(Ａ23)Ｎ))Ｎ＝Ｐ(Ａ36)Ｎ＝Ｍ3・２7n・Ｍ3・２7n・２-n ｍｏｄ Ｎ （１０）
Ｐ((Ｐ(Ａ23)Ｎ)・(Ｐ(Ａ23)Ｎ))Ｎ＝Ｍ6・２13n ｍｏｄ Ｎ （１１）
Ｐ((Ｐ(Ａ36)Ｎ)・Ａ)Ｎ＝Ｐ(Ａ47)Ｎ＝Ｍ6・２13n・Ｍ・２3n・２-n ｍｏｄ Ｎ （１２）
Ｐ((Ｐ(Ａ36)Ｎ)・Ａ)Ｎ＝Ｍ7・２15n ｍｏｄ Ｎ （１３）
【００４１】
リトリーバルマスクの生成がモンゴメリーパラサイト ２-n ｍｏｄ Ｎに基づいており、これが単一のモンゴメリー乗算によって得られることが好ましく、
Ｐ(１・１)Ｎ＝２-n ｍｏｄ Ｎ （１４）
であり、その次に、典型的には、類似の累乗手順がこのマスクリトリーバル値を２-14n ｍｏｄ Ｎ＝Ｙに累乗する。
【００４２】
次に、Ｐフィールドからのリトリーバルとマスクの除去とが、典型的には、指数量時間Ｙの単一のモンゴメリー乗算において行われ、
Ｍ7 ｍｏｄ Ｎ＝Ｐ((Ｍ7・２15n)・２-14n)Ｎ＝Ｍ7・２n・２-n ｍｏｄ Ｎ （１５）
である。
【００４３】
これは、ｅ（暗号化指数）が既知でない時にさえ、選択されたメッセージの暗号解読シーケンスが、典型的には、Ｎのトーティエント関数の知識なしに生成されるということを示す。
【００４４】
一般的に、指数乗数ｘが２xn ｍｏｄ Ｎランダムマスクにおいて９０よりも大きい場合には、攻撃者は、選択メッセージ攻撃を行うためにそのマスクを導出することもそのランダムマスクによって選択メッセージを形成することも不可能である。
【００４５】
限定されたモンゴメリー能力を有するかまたは拡張ユークリッド逆数を有する装置のためのモンゴメリーマスク法。
【００４６】
図２は、本発明の第１の実施形態によるモンゴメリーマスクとメッセージリトリーバとを用意する好ましいシーケンスを示す流れ図である。
【００４７】
ステップ２１０では、秘密指数ｄとｎビットモジュラスＮが入力され、ここでｄとＮは整数であり、および、Ｈが式（１）に従って計算される。Ｈ1/2＝２n ｍｏｄ Ｎが単一の整数減法によって計算され、
２n−Ｎ≡２n ｍｏｄ Ｎ （１６）
である。
【００４８】
その次に、ステップ２２０において、Ｈ-1/2が計算され、上述の式（１４）の通りに、
Ｈ-1/2＝２-n ｍｏｄ Ｎ≡Ｐ(１・１)Ｎ＝２-n ｍｏｄ Ｎ
である。
【００４９】
ステップ２３０では、秘密数ｘが生成される。秘密ｘを明らかにするために徹底的な探索を行うには２90のワークファクタ（work factor）が必要であるとすれば、ｘが少なくとも９０であることが好ましい。
【００５０】
ステップ２５０では、マスク逆数Ｋ1が計算され、
Ｋ1＝２nx ｍｏｄ Ｎ＝(２n)x ｍｏｄ Ｎ （１７）
である。
【００５１】
ステップ２６０では、メッセージリトリーバＫ2が計算され、
Ｋ2＝２-nxd ｍｏｄ Ｎ＝((２-n)x)d ｍｏｄ Ｎ （１８）
である。
【００５２】
Ｋ1とＫ2は、必要に応じて、次のようにｘ'によって更新されてよく、
Ｋ1'＝((Ｋ1) ｍｏｄ Ｎ)x' ｍｏｄ Ｎ （１９）
Ｋ2'＝((Ｋ2) ｍｏｄ Ｎ)x' ｍｏｄ Ｎ （２０）
であり、前式中でｘ'は、典型的には、ランダムに選択された小さい正の整数である。
【００５３】
図３は、選択メッセージ攻撃に対して抵抗性があるマスクされた累乗を暗号文Ｃに対して行うための、本発明の第２の実施形態による、入力メッセージに対するモンゴメリーマスクの使用のシーケンスを示す流れ図であり、この場合に（例えば、記憶装置内で）ｄ、Ｎ、Ｋ1、Ｋ2が使用可能である。
【００５４】
ステップ３１０では、暗号文Ｃが入力され、この暗号文ＣからＣ ｍｏｄ Ｎが計算されることが可能である。
【００５５】
ステップ３２０では、（例えば、記憶装置から）Ｎ、ｄ、Ｋ1、Ｋ2が入力される。
【００５６】
ステップ３３０では、モジューロ乗算によってマスクされた暗号文を得るために、Ａ1＝Ｃ*Ｋ1 ｍｏｄ Ｎを計算する。
【００５７】
ステップ３４０では、Ａ2＝Ａ1d ｍｏｄ Ｎを計算する。マスクされたモジューロ累乗＝(Ｃ*Ｋ1)d ｍｏｄ Ｎ＝Ｍ*２nxd ｍｏｄ Ｎ
である。
【００５８】
ステップ３５０では、平文Ｍをリトリーブする。
Ｍ＝Ｃd ｍｏｄ Ｎ＝Ａ2*Ｋ2 ｍｏｄ Ｎ＝((Ｃd)(２ndx))(２-ndx) ｍｏｄ Ｎ
【００５９】
加えられる唯一のリソースが、記憶装置内に格納されるべきｎビット定数Ｋ1、Ｋ2である。
【００６０】
好ましい装置の実施形態におけるマスクされたモンゴメリー累乗。
【００６１】
Ｈ＝２2n ｍｏｄ Ｎがモジューロ除算によって計算されることが可能である。
【００６２】
Ｈ-1/2＝２-n ｍｏｄ Ｎ≡Ｐ(１・１)Ｎ＝((１・１)２-n) ｍｏｄ Ｎ、２n ｍｏｄ Ｎの逆数。
【００６３】
秘密ｘを明らかにするために徹底的な探索を行うには２90のワークファクタが適切であると仮定する場合に、ｘ＝秘密乱数、２≦ｘ≦９５、好ましくは９０≦ｘである。その次に、Ｋ1を事前計算するために、
Ｍ1＝Ｘ((Ｈ)x)Ｎ＝Ｘ(２n・２n)x＝２nx・２n ｍｏｄ Ｎ、
Ｋ1＝Ｐ(Ｈ・Ｍ1)Ｎ＝２2n・２n・２nx・２n・２-n ｍｏｄ Ｎ＝２nx・２2n ｍｏｄ Ｎ
である。
【００６４】
Ｋ2を事前計算する時に、２-n・２n ｍｏｄ Ｎ＝１ ｍｏｄ Ｎであることに留意されたい。
【００６５】
Ｍ2＝Ｘ(１x)Ｎ＝Ｘ((２-n・２n)x)Ｎ＝２-nx・２n
Ｍ3＝Ｘ((Ｍ2)d)Ｎ＝Ｘ((２-nx・２n)d)Ｎ＝２-nxd・２n
Ｋ2＝Ｐ(Ｍ3・１)Ｎ＝２-nxd ｍｏｄ Ｎ。
【００６６】
Ｋ1とＫ2が典型的には、小さい正の整数であるｘ'によって更新される。
Ｋ1←Ｋ1'＝((Ｋ1) ｍｏｄ Ｎ)x' ｍｏｄ Ｎ
Ｍ4＝Ｘ((Ｍ3)x')Ｎ＝Ｘ(((２-nx・２n)d)x')Ｎ＝２-nxx'd・２ｎ
Ｋ2←Ｋ2'＝Ｐ(Ｍ4・１)Ｎ＝２-nxx'd ｍｏｄ Ｎ
【００６７】
図４は、選択メッセージ攻撃に対して抵抗性があるマスクされた累乗を選択された暗号文に対して行って、Ｃd ｍｏｄ Ｎを計算するために、モジューロ乗算装置上で動作可能なモンゴメリー関数を使用する、本発明の第３の実施形態における入力メッセージに対するモンゴメリーマスクの使用のシーケンスを示す流れ図である。次の演算を行う。
【００６８】
ステップ４１０では、マスクされていない暗号文メッセージＣを入力または生成する。ステップ４２０では、秘密指数ｄと、ｎビットモジュラスＮと、マスクＫ1と、メッセージリトリーバＫ2とを入力する。これらは次に詳細を示すように計算される。
【００６９】
ステップ４３０では、暗号文に対するモンゴメリーマスクを計算し、
Ａ1＝Ｐ(Ｃ・Ｋ1)Ｎ＝(Ｃ・２nx)・２n ｍｏｄ Ｎ
である。
【００７０】
ステップ４４０では、モンゴメリーマスク指数を計算し、
Ａ2＝Ｐ(((Ｃ・２nx)・２n)d)Ｎ＝Ｃd・２nxd・２n ｍｏｄ Ｎ
である。
【００７１】
ステップ４５０では、モンゴメリー Ｐフィールドから結果をリトリーブし、
Ｃd ｍｏｄ Ｎ＝Ｐ((Ａ2・Ｋ2))Ｎ＝Ｐ((Ｃd・２nxd・２n)(２-nxd))Ｎ
である。
【００７２】
セキュリティ保護の観点から、Ｋ1とＫ2は、一般的に、上述したように更新される。
【００７３】
このマスクされた累乗は各累乗の前のＨの生成を排除し、典型的には、同じ回数の乗算と２乗とによるプロセス時間の４％を節約する。
【００７４】
図５は、図４に示されている方法のような任意の適切な方法と共に使用されることが可能な、本発明の第４の実施形態によるメッセージのマスキングおよびリトリービングのための装置の単純化されたブロック図である。モジューロプロセッサ５１０がモジュラス５２０と指数５３０とを受け取る。乱数ジェネレータ５４０が、マスクジェネレータ５５０とメッセージリトリーバジェネレータ５６０とに対してランダムな整数を提供する。暗号文メッセージ５７０がモジューロプロセッサ５１０に入力され、および、このモジューロプロセッサ５１０は平文メッセージ５８０を出力する。本発明の別の実施形態では、モジューロプロセッサ５１０は従来の仕方でモジューロ演算を行う。しかし、本発明のさらに別の実施形態では、モジューロプロセッサ５１０はモンゴメリー演算を行う。
【００７５】
本発明を限られた数の実施形態に関して説明してきたが、本発明の多くの変型と変更と他の適用とが行われてよいということが理解されるだろう。
【００７６】
本発明のソフトウェア構成要素が、必要に応じて、ＲＯＭ（読み出し専用メモリ）形態で実現されてよいということが理解される。このソフトウェア構成要素は、一般的に、必要に応じて、従来の技術を使用してハードウェアの形で実現されてよい。
【００７７】
理解しやすいように別々の実施形態の文脈において説明されている本発明の様々な特徴が、単一の実施形態において組合せの形で実現されてもよいということが理解される。これとは逆に、簡潔にするために単一の実施形態の文脈において説明されている本発明の様々な特徴が、別々に、または、任意の適切な副次的な組合せの形で実現されてもよい。
【００７８】
本明細書に詳細に示され説明されているものだけに本発明が限定されないということが、当業者に理解されるだろう。むしろ、本発明の範囲は特許請求項だけによって規定される。
【図面の簡単な説明】
【００７９】
【図１】従来技術のモンゴメリーモジューロ演算プロセッサの単純化されたブロック図である。
【図２】本発明の好ましい実施形態によるモンゴメリーマスクとメッセージリトリーバとを用意するシーケンスを示す流れ図である。
【図３】本発明の好ましい実施形態による、入力メッセージに対して図２のモンゴメリーマスクを使用するシーケンスを示す流れ図である。
【図４】本発明の好ましい実施形態による、図１または図５に示されているモンゴメリーモジューロ乗算装置上において動作可能なモンゴメリー関数を使用する、入力メッセージに対してモンゴメリーマスクを使用することを含む、図３の方法の好ましい具体例を示す流れ図である。
【図５】本発明の好ましい実施形態によってメッセージをマスクおよびリトリーブするための装置の単純化されたブロック図である。
【特許請求の範囲】
【請求項１】
ｎ個のビットを有するバイナリモジュラスＮを法として秘密指数ｄで暗号文メッセージを累乗するように働く暗号化装置に入力される前記暗号文メッセージをマスクする方法であって、マスクを構成するために自然モンゴメリー逆数２-nを使用するのを備えることを特徴とする方法。
【請求項２】
ｎ個のビットを有するバイナリモジュラスＮを法として秘密指数ｄで暗号文メッセージを累乗するように働く暗号化装置に入力される前記暗号文メッセージをマスクする方法であって、
ランダム整数ｘを生成し、
数２nx ｍｏｄ Ｎに等しいマスクを計算し、および、
数２-nxd ｍｏｄ Ｎに等しいメッセージリトリーバを計算するのを備えることを特徴とする方法。
【請求項３】
ｎ個のビットを有するバイナリモジュラスＮを法として指数ｄで暗号文メッセージを累乗するように働く暗号化装置に入力される前記暗号文メッセージをマスクする装置であって、自然モンゴメリー逆数２-nからマスクを構成するように動作するマスクジェネレータを備えることを特徴とする装置。
【請求項４】
ｎ個のビットを有するバイナリモジュラスＮを法として指数ｄで暗号文メッセージを累乗するように働く暗号化装置に入力される前記暗号文メッセージをマスクする装置であって、
前記バイナリモジュラスＮを法として２つの数の積を計算し、且つ、該バイナリモジュラスＮを法として数をｄ乗するように働くモジューロプロセッサと、
ランダム整数ｘを生成するランダム整数ジェネレータと、
前記モジューロプロセッサが前記バイナリモジュラスＮを法として前記暗号文メッセージと前記マスクとの積を計算し、且つ、マスクされたメッセージを計算するために該バイナリモジュラスＮを法として指数ｄで前記積を累乗するように、前記数２nx ｍｏｄ Ｎに等しいマスクを計算して前記モジューロプロセッサに前記マスクを送り込むように働くマスクジェネレータと、
前記モジューロプロセッサが、平文メッセージを計算するために前記マスクされたメッセージと前記メッセージリトリーバとの積を計算するように、数２-nxd ｍｏｄ Ｎに等しいメッセージリトリーバを計算し、且つ、前記メッセージリトリーバを前記モジューロプロセッサに送り込むように働くメッセージリトリーバジェネレータと、を備えることを特徴とする装置。
【請求項５】
請求項４に記載の装置において、前記モジューロプロセッサはモンゴメリーモジューロプロセッサであることを特徴とする装置。
【請求項６】
ｎ個のビットを有するバイナリモジュラスＮを法として秘密指数ｄで暗号文メッセージを累乗する働きをする暗号化装置に入力される前記暗号文メッセージをマスクする方法であって、積を形成するために前記暗号文メッセージに乗算されるマスクを構成するように自然モンゴメリー逆数２-nを使用し、且つ、前記積の関数から平文メッセージをリトリーブするのを備えることを特徴とする方法。
【請求項７】
請求項２に記載の方法において、さらに、
積を形成するために前記マスクを前記暗号文メッセージに乗算し、
マスクされた累乗メッセージを形成するために、前記バイナリモジュラスＮを法として前記秘密指数ｄで前記積を累乗し、
リトリーブされた平文メッセージを形成するために、前記メッセージリトリーバを前記マスクされた累乗メッセージに乗算するのを備えることを特徴とする方法。
【請求項８】
ｎ個のビットを有するバイナリモジュラスＮを法として秘密指数ｄで暗号文メッセージを累乗する働きをする暗号化装置に入力される前記暗号文メッセージをリトリーブする方法であって、
積を形成するために、数２nx ｍｏｄ Ｎに等しい前記マスクを前記暗号文メッセージに乗算し、
マスクされた累乗メッセージを形成するために、前記バイナリモジュラスＮを法として前記秘密指数ｄで前記積を累乗し、
リトリーブされた平文メッセージを形成するために、前記メッセージリトリーバを前記マスクされた累乗メッセージに乗算するのを備えることを特徴とする方法。
【請求項１】
ｎ個のビットを有するバイナリモジュラスＮを法として秘密指数ｄで暗号文メッセージを累乗するように働く暗号化装置に入力される前記暗号文メッセージをマスクする方法であって、マスクを構成するために自然モンゴメリー逆数２-nを使用するのを備えることを特徴とする方法。
【請求項２】
ｎ個のビットを有するバイナリモジュラスＮを法として秘密指数ｄで暗号文メッセージを累乗するように働く暗号化装置に入力される前記暗号文メッセージをマスクする方法であって、
ランダム整数ｘを生成し、
数２nx ｍｏｄ Ｎに等しいマスクを計算し、および、
数２-nxd ｍｏｄ Ｎに等しいメッセージリトリーバを計算するのを備えることを特徴とする方法。
【請求項３】
ｎ個のビットを有するバイナリモジュラスＮを法として指数ｄで暗号文メッセージを累乗するように働く暗号化装置に入力される前記暗号文メッセージをマスクする装置であって、自然モンゴメリー逆数２-nからマスクを構成するように動作するマスクジェネレータを備えることを特徴とする装置。
【請求項４】
ｎ個のビットを有するバイナリモジュラスＮを法として指数ｄで暗号文メッセージを累乗するように働く暗号化装置に入力される前記暗号文メッセージをマスクする装置であって、
前記バイナリモジュラスＮを法として２つの数の積を計算し、且つ、該バイナリモジュラスＮを法として数をｄ乗するように働くモジューロプロセッサと、
ランダム整数ｘを生成するランダム整数ジェネレータと、
前記モジューロプロセッサが前記バイナリモジュラスＮを法として前記暗号文メッセージと前記マスクとの積を計算し、且つ、マスクされたメッセージを計算するために該バイナリモジュラスＮを法として指数ｄで前記積を累乗するように、前記数２nx ｍｏｄ Ｎに等しいマスクを計算して前記モジューロプロセッサに前記マスクを送り込むように働くマスクジェネレータと、
前記モジューロプロセッサが、平文メッセージを計算するために前記マスクされたメッセージと前記メッセージリトリーバとの積を計算するように、数２-nxd ｍｏｄ Ｎに等しいメッセージリトリーバを計算し、且つ、前記メッセージリトリーバを前記モジューロプロセッサに送り込むように働くメッセージリトリーバジェネレータと、を備えることを特徴とする装置。
【請求項５】
請求項４に記載の装置において、前記モジューロプロセッサはモンゴメリーモジューロプロセッサであることを特徴とする装置。
【請求項６】
ｎ個のビットを有するバイナリモジュラスＮを法として秘密指数ｄで暗号文メッセージを累乗する働きをする暗号化装置に入力される前記暗号文メッセージをマスクする方法であって、積を形成するために前記暗号文メッセージに乗算されるマスクを構成するように自然モンゴメリー逆数２-nを使用し、且つ、前記積の関数から平文メッセージをリトリーブするのを備えることを特徴とする方法。
【請求項７】
請求項２に記載の方法において、さらに、
積を形成するために前記マスクを前記暗号文メッセージに乗算し、
マスクされた累乗メッセージを形成するために、前記バイナリモジュラスＮを法として前記秘密指数ｄで前記積を累乗し、
リトリーブされた平文メッセージを形成するために、前記メッセージリトリーバを前記マスクされた累乗メッセージに乗算するのを備えることを特徴とする方法。
【請求項８】
ｎ個のビットを有するバイナリモジュラスＮを法として秘密指数ｄで暗号文メッセージを累乗する働きをする暗号化装置に入力される前記暗号文メッセージをリトリーブする方法であって、
積を形成するために、数２nx ｍｏｄ Ｎに等しい前記マスクを前記暗号文メッセージに乗算し、
マスクされた累乗メッセージを形成するために、前記バイナリモジュラスＮを法として前記秘密指数ｄで前記積を累乗し、
リトリーブされた平文メッセージを形成するために、前記メッセージリトリーバを前記マスクされた累乗メッセージに乗算するのを備えることを特徴とする方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図２】
【図３】
【図４】
【図５】
【公表番号】特表２００７−５１９３０５（Ｐ２００７−５１９３０５Ａ）
【公表日】平成１９年７月１２日（２００７．７．１２）
【国際特許分類】
【出願番号】特願２００６−５３９０７５（Ｐ２００６−５３９０７５）
【出願日】平成１６年１１月１６日（２００４．１１．１６）
【国際出願番号】ＰＣＴ／ＩＬ２００４／００１０５３
【国際公開番号】ＷＯ２００５／０４８００８
【国際公開日】平成１７年５月２６日（２００５．５．２６）
【出願人】（５０６１６５２６５）エム−システムズ フラッシュ ディスク パイオニアズ リミティド (1)
【Ｆターム（参考）】
【公表日】平成１９年７月１２日（２００７．７．１２）
【国際特許分類】
【出願日】平成１６年１１月１６日（２００４．１１．１６）
【国際出願番号】ＰＣＴ／ＩＬ２００４／００１０５３
【国際公開番号】ＷＯ２００５／０４８００８
【国際公開日】平成１７年５月２６日（２００５．５．２６）
【出願人】（５０６１６５２６５）エム−システムズ フラッシュ ディスク パイオニアズ リミティド (1)
【Ｆターム（参考）】
[ Back to top ]