モンゴメリ剰余乗算

モジュラー算術計算において、モンゴメリモジュラー乗算（モンゴメリ乗算とも呼ばれる）は、高速モジュラー乗算を実行する手法である。1985年にアメリカの数学者ピーター・L・モンゴメリによって導入された。^{[1] [2]}

モンゴメリ剰余乗算は、モンゴメリ形式と呼ばれる特殊な数値表現に依存します。アルゴリズムは、aとbのモンゴメリ形式を使用して、 ab mod Nのモンゴメリ形式を効率的に計算します。この効率性は、コストのかかる除算演算を回避することによって実現されます。従来の剰余乗算では、Nによる除算を使用して倍幅の積ab を縮小し、剰余のみを保持します。この除算では、商の桁の推定と修正が必要です。対照的に、モンゴメリ形式は、Nと互いに素な定数R > Nに依存し、モンゴメリ乗算で必要な除算はRによる除算のみです。定数R は、 Rによる除算が容易になるように選択できるため、アルゴリズムの速度が大幅に向上します。実際には、 2 の累乗による除算はビットシフトによって実装できるため、Rは常に 2 の累乗です。

aとb をモンゴメリ形式に変換し、それらの積をモンゴメリ形式から変換する必要があるため、モンゴメリ乗算による単一の積の計算は、従来のアルゴリズムやバレット削減アルゴリズムよりも遅くなります。ただし、べき乗剰余演算のように、連続して多数の乗算を実行する場合は、中間結果をモンゴメリ形式のままにすることができます。すると、最初と最後の変換は、全体の計算のごく一部になります。RSAやDiffie -Hellman 鍵交換などの多くの重要な暗号システムは、大きな奇数を法とする算術演算に基づいており、これらの暗号システムでは、Rが2 の累乗であるモンゴメリ乗算を使用した計算は、利用可能な代替手段よりも高速です。^[3]

N を正の整数の法とする。商環Z / N ZはNを法とする剰余類から成り、つまりその要素は次のような形式の集合である。

${\displaystyle \{a+kN\colon k\in \mathbf {Z} \},}$

ここで、a は整数の範囲に渡る。各剰余類は、その集合内の任意の 2 つの整数の差がNで割り切れる整数の集合である（そして、剰余類はその性質に関して最大​​である。整数は、割り切れる条件に違反しない限り、剰余類から除外されない）。a に対応する剰余類はaと表記される。剰余類の等式は合同と呼ばれ、次のように表記される。

${\displaystyle {\bar {a}}\equiv {\bar {b}}{\pmod {N}}.}$

剰余類は無限の要素を持つため、剰余類全体をコンピュータに保存することは不可能です。代わりに、剰余類は代表として保存されます。慣例的に、これらの代表は0 ≤ a ≤ N − 1となる整数aです。a が整数の場合、aの代表はa mod Nと書きます。合同式を書くときは、整数をそれが表す剰余類と同一視するのが一般的です。この慣例により、上記の等式はa ≡ b mod Nと書きます。

剰余類の算術は、まずその代表に対して整数算術を実行することによって行われます。整数演算の出力によって剰余類が決定され、剰余類の代表を計算することによってモジュラー演算の出力が決定されます。たとえば、N = 17の場合、剰余類7と15の合計は、整数の合計7 + 15 = 22を求め、次に22 mod 17 (0 と 16 の間の整数で 22 との差が 17 の倍数である整数) を決定することによって計算されます。この場合、その整数は 5 なので、7 + 15 ≡ 5 mod 17となります。

aとb が範囲[0, N − 1]の整数である場合、それらの和は範囲[0, 2 N − 2]にあり、それらの差は範囲[− N + 1, N − 1]にあるため、 [0, N − 1]の代表を決定するには、Nの減算または加算（それぞれ）を最大で 1 回実行する必要があります。ただし、積ab は範囲[0, N ² − 2 N + 1]にあります。中間の整数積abを格納するには、 aまたはbの 2 倍のビット数が必要であり、[0, N − 1]の代表を効率的に決定するには除算が必要です。数学的には、 abと合同な0 からN − 1までの整数は、ユークリッドの除算定理を適用して表すことができます。

${\displaystyle ab=qN+r,}$

ここでqは商、r は剰余で、[0, N − 1] の範囲内にあります。剰余rはab mod Nです。r は、 を計算してから qN を ab から減算することで決定できます。たとえば、 の場合、積7 ⋅ 15 は、 を計算し、 を割り、 を減算することで決定されます。 ${\displaystyle \lfloor ab/N\rfloor }$${\displaystyle N=17}$${\displaystyle 7\cdot 15=105}$${\displaystyle \lfloor 105/17\rfloor =6}$${\displaystyle 105-6\cdot 17=105-102=3}$

qの計算には除算が必要なので、ほとんどのコンピュータ ハードウェアでは望ましくないほどコストがかかります。モンゴメリ形式は、リングの要素を表現する別の方法で、コストのかかる除算をせずにモジュラー積を計算できます。除算は依然として必要ですが、別の除数Rに関して行うことができます。この除数は 2 の累乗に選択できます。この場合、除算はシフトに置き換えられます。または、マシン ワードの整数に選択できます。この場合、除算はワードの省略に置き換えられます。これらの除算は高速であるため、モンゴメリ形式を使用してモジュラー積を計算するコストのほとんどは、通常の積を計算するコストです。

補助法R は、gcd( R , N ) = 1となる正の整数でなければなりません。計算上、 R を法とする除算と減算が低コストであることも必要であり、法はR > Nでない限りモジュラー乗算には役立ちません。Rに関する剰余類aのモンゴメリ形式はaR mod Nです。つまり、剰余類aRの代表です。たとえば、N = 17でR = 100とします。3、5、7、15 のモンゴメリ形式は、 300 mod 17 = 11、500 mod 17 = 7、700 mod 17 = 3、1500 mod 17 = 4です。

モンゴメリ形式の加算と減算は、分配法則により、通常のモジュラー加算と減算と同じです。

${\displaystyle aR+bR=(a+b)R,}$

${\displaystyle aR-bR=(ab)R.}$

モンゴメリ形式で演算を行うと、商環Z / N Zで演算を行う場合と比べて情報が失われないことに注意してください。これは、 gcd( R、N ) = 1であるため、 Rによる乗算は加法群Z / N Z上の同型であるという事実の結果です。たとえば、(7 + 15) mod 17 = 5は、モンゴメリ形式では(3 + 4) mod 17 = 7になります。

しかし、モンゴメリ形式での乗算は、一見するとより複雑です。通常のaRとbRの積は、 Rという余分な因数があるため、aとbの積を表しません。

${\displaystyle (aR{\bmod {N}})(bR{\bmod {N}}){\bmod {N}}=(abR)R{\bmod {N}}.}$

モンゴメリ形式で積を計算するには、 Rの余分な因数を除去する必要があります。Rによる除算は簡単ですが、中間積( aR mod N )( bR mod N )は、モジュロ演算によってその特性が破壊されているため、 Rで割り切れません。したがって、たとえば、 R = 100の場合、 7 と 15 のモンゴメリ形式の積を 17 で割った値は、 3 と 4 の積、つまり 12 になります。 12 は 100 で割り切れないため、 Rの余分な因数を除去するには追加の作業が必要です。

Rの余分な因数を取り除くには、 RR ′ ≡ 1 (mod N )となる整数R ′を掛ける。 つまり、剰余類がR mod Nのモジュラー逆であるR ′ を掛ける。すると、 N を法として、

${\displaystyle (aR{\bmod {N}})(bR{\bmod {N}})R'\equiv (aR)(bR)R^{-1}\equiv (ab)R{\pmod {N }}.}$

整数R ′ は、 RとNが互いに素であるという仮定に基づいて存在します。これは、拡張ユークリッドの互除法を使用して構築できます。拡張ユークリッドの互除法は、ベズーの恒等式0 < R ′ < N、0 < N ′ < R を満たす 整数R ′とN ′ を効率的に決定します。

${\displaystyle RR'-NN'=1.}$

これは、モンゴメリ形式で乗算が可能であることを示しています。したがって、モンゴメリ形式で数を乗算する簡単なアルゴリズムは、aR mod N、bR mod N、およびR ′ を整数として乗算し、 Nを法として減算することです。

たとえば、モンゴメリ形式で 7 と 15 を 17 を法として掛け合わせるには、R = 100として、上記のように 3 と 4 の積を計算して 12 を得ます。拡張ユークリッドの互除法では、8⋅100 − 47⋅17 = 1 となるため、R ′ = 8となります。12 に 8 を掛けて 96 を得て、これを 17 を法として減算すると 11 が得られます。これは予想どおり 3 のモンゴメリ形式です。

上記のアルゴリズムは正しいのですが、 R ′で乗算してNで除算する必要があるため、標準表現での乗算よりも遅くなります。 モンゴメリ減算(REDC とも呼ばれる) は、 R ′による積とNを法とする減算を同時に計算するアルゴリズムで、ナイーブな方法よりも高速です。 数をNより小さくすることに重点を置く従来のモジュラー減算とは異なり、モンゴメリ減算は数をRで割り切れるようにすることに重点を置いています。これは、 R を法とする剰余をキャンセルするように巧みに選択されたNの小さな倍数を加算することによって行われます。結果をRで割ると、はるかに小さな数になります。 この数は非常に小さく、 N を法とする減算とほぼ同じであり、 Nを法とする減算の計算には最後の条件付き減算のみが必要です。 すべての計算はNではなくRに関する減算と除算のみを使用して行われるため、このアルゴリズムは除算による単純なモジュラー減算よりも高速に実行されます。

関数REDCの
    入力: gcd( R , N ) = 1となる整数RとN、[0, R − 1]の
           整数N ′でNN ′ ≡ −1 mod Rを満たすもの、範囲[0, RN − 1]の
           整数T。
    出力:範囲[0, N − 1]の整数Sで、 S ≡ TR −1 mod Nとなるもの

    m ← (( T mod R ) N ′) mod R 
    t ← ( T + mN ) / R 
    t ≥ Nの場合 t − Nを返し、それ以外の場合はtを返す。終了if終了関数 
         
    
         
    

このアルゴリズムが正しいことを確認するには、まずm がT + mN がRで割り切れるように正確に選択されていることを確認します。数がRで割り切れるのは、それがR を法としてゼロに一致する場合のみであり、次の式が成り立ちます。

${\displaystyle T+mN\equiv T+(((T{\bmod {R}})N'){\bmod {R}})N\equiv T+TN'N\equiv TT\equiv 0{\pmod {R}}.}$

したがって、tは整数です。次に、出力はtまたはt − N のいずれかであり、どちらもt mod Nと合同です。したがって、出力がTR ⁻¹ mod Nと合同であることを証明するには、 tがTR ⁻¹ mod Nであり、t が次を満たすことを証明すれば十分です。

${\displaystyle t\equiv (T+mN)R^{-1}\equiv TR^{-1}+(mR^{-1})N\equiv TR^{-1}{\pmod {N}}.}$

したがって、出力は正しい剰余クラスを持ちます。3番目に、m は[0, R − 1]にあるため、T + mNは 0 と( RN − 1) + ( R − 1) N < 2 RNの間です。したがってt は2 N未満であり、整数であるため、t は[0, 2 N − 1] の範囲になります。したがって、t を目的の範囲に減らすには最大で1回の減算が必要であり、アルゴリズムの出力は正しい範囲にあります。

REDC を使用して 7 と 15 の積を 17 で割ったものを計算するには、まずモンゴメリ形式に変換し、整数として乗算して上記のように 12 を取得します。次に、 R = 100 、 N = 17 、 N ′ = 47 、および T = 12 で REDC を適用します。最初のステップでは、mを12 ⋅ 47 mod 100 = 64 に設定します。2番目のステップでは、 t を(12 + 64 ⋅ 17) / 100に設定します。12 + 64 ⋅ 17は 1100 であり、予想どおり 100 の倍数である ことに注意してください。 tは 17 未満の 11 に設定されているため、最終結果は 11 となり、前のセクションの計算と一致します。

別の例として、積7 ⋅ 15 mod 17でR = 10の場合を考えます。拡張ユークリッドの互除法を使用して、−5 ⋅ 10 + 3 ⋅ 17 = 1 を計算すると、N ′ は−3 mod 10 = 7になります。 7 と 15 のモンゴメリ形式は、それぞれ70 mod 17 = 2と150 mod 17 = 14です。それらの積 28 は REDC への入力Tであり、28 < RN = 170なので、 REDC の仮定は満たされます。 REDC を実行するには、m を(28 mod 10) ⋅ 7 mod 10 = 196 mod 10 = 6に設定します。すると、28 + 6 ⋅ 17 = 130なので、t = 13 になります。30 mod 17 = 13なので、これは3 = 7 ⋅ 15 mod 17のモンゴメリ形式です。

N を法とする多くの興味深い演算は、モンゴメリ形式でも同様に表現できます。加算、減算、否定、等号の比較、モンゴメリ形式ではない整数による乗算、およびNとの最大公約数はすべて、標準アルゴリズムで実行できます。ヤコビ記号は、が保存されている限り計算できます。 ${\displaystyle {\big (}{\tfrac {a}{N}}{\big )}={\big (}{\tfrac {aR}{N}}{\big )}/{\big (}{\tfrac {R}{N}}{\big )}}$${\displaystyle {\big (}{\tfrac {R}{N}}{\big )}}$

R > Nの場合、他のほとんどの算術演算は REDC で表現できます。この仮定は、 2 つの代表値の mod Nの積がRNより小さいことを意味し、これは REDC が正しい出力を生成するために必要な正確な仮定です。特に、aR mod NとbR mod Nの積はREDC(( aR mod N )( bR mod N ))です。乗算と REDC を組み合わせた演算は、しばしばモンゴメリ乗算と呼ばれます。

モンゴメリ形式への変換は、REDC(( a mod N )( R ² mod N ))を計算することによって行われます。モンゴメリ形式からの変換は、REDC( aR mod N )を計算することによって行われます。 aR mod Nのモジュラー逆は、REDC(( aR mod N ) ⁻¹ ( R ³ mod N ))です。モジュラー指数は、最初の積を 1 のモンゴメリ表現、つまりR mod Nに初期化し、乗算手順と平方手順をモンゴメリ乗算に置き換えることによって、 平方による指数を使用して実行できます。

これらの操作を実行するには、少なくともN ′とR ² mod N を知っている必要があります。R が小さな正の整数bの累乗である場合、N ′はヘンゼルの補題によって計算できます。 b を法とするNの逆数は単純なアルゴリズムで計算され (たとえば、b = 2の場合、逆数は 1)、ヘンゼルの補題はbのより高い累乗を法とする逆数を見つけるために繰り返し使用され、 R を法とする逆数がわかった時点で停止します。 N ′ はこの逆数の否定です。定数R mod NとR ³ mod N は、 REDC( R ² mod N )とREDC(( R ² mod N )( R ² mod N ))として生成できます。基本的な操作は、積の REDC を計算することです。スタンドアロンの REDC が必要な場合は、 1 mod Nの積の REDC として計算できます。N を法とする直接的な縮約が必要となる唯一の場所は、R ² mod Nの事前計算です。

ほとんどの暗号化アプリケーションでは、数百または数千ビットの長さの数値が必要です。このような数値は、単一のマシンワードに格納するには大きすぎます。通常、ハードウェアはB を底とする乗算を実行するため、より大きな乗算を実行するには、いくつかの小さな乗算を組み合わせる必要があります。B の底は通常、マイクロエレクトロニクスアプリケーションの場合は2、8 ビットファームウェアの場合は2 ^{8 、 [4]}、ソフトウェアアプリケーションの場合は 2 ³²または 2 ⁶⁴です。

REDC アルゴリズムでは、積を法とするR の積が必要で、通常はR > N であるため、 REDC を使用して積を計算できます。ただし、R がBの累乗である場合は、マシン ワード サイズの整数の積のみを必要とする REDC のバリエーションがあります。正の多倍長整数がリトルエンディアンで格納されているとします。つまり、x は、すべてのiについて0 ≤ x [ i ] < Bかつx = ∑ x [ i ] B ⁱとなる配列x [0], ..., x [ℓ - 1]として格納されます。アルゴリズムは多倍長整数Tから開始し、一度に 1 ワードずつ減らします。最初に、Nの適切な倍数を追加して、T がBで割り切れるようにします。次に、 Nの倍数を追加して、 T がB ²で割り切れるようにします。これを繰り返します。最終的に、T はRで割り切れるようになり、Rで割った後、アルゴリズムはtの計算後の REDC と同じ状態になります。

関数MultiPrecisionREDCは
    入力: gcd( B , N ) = 1の整数N 、 pワードの配列として保存されます。
           整数R = B r、したがってr = log B  R
           整数N ′ は[0, B − 1]の範囲内にあり、 NN ′ ≡ −1 (mod B )となる。0 ≤ T < RNの範囲の
           整数T は、 r + pワードの配列として格納されます。

    出力: TR −1 ≡ S (mod N )となる[0, N − 1]の整数Sがpワードの配列として格納されます。
T [ r + p ] = 0   （余分なキャリーワード）
    に 
    設定し、 0 ≤ i < rを 実行し、 --loop1- Tを
        B i+1で割り切れるようにする

        c ← 0
         m ← T [ i ] ⋅ N ′ mod B
         for  0 ≤ j < p  do 
            --loop2- m ⋅ N[j]と先ほどの繰り上がりを加算し、新しい繰り上がりを求める

            x ← T [ i + j ] + m ⋅ N [ j ] + c
             T [ i + j ] ← x mod B
             c ← ⌊ x / B ⌋ 
        end for 
        for  p ≤ j ≤ r + p − i  do 
            --loop3- 繰り上がりを続ける

            x ← T [ i + j ] + c
             T [ i + j ] ← x mod B
             c ← ⌊ x / B ⌋
        終了
    終了

     0 ≤ i ≤ p の場合、 S [ i ] ← T [ i + r ]
    を実行し
        、終了する。

     S ≥ N の場合、
        S − Nを返し 、そうでない場合はSを返す。終了、終了関数
    
         
    

最終的な比較と減算は標準アルゴリズムによって実行されます。

上記のアルゴリズムは、 REDC が正しいのと本質的に同じ理由で正しいです。 iループを通過するたびに、 T [ i ] + mN [0]がBで割り切れるようにmが選択されます。次に、mNB ⁱがTに加算されます。この量はゼロ mod Nであるため、これを追加してもT mod Nの値には影響しません。m _{i が}ループのi回目の反復で計算されたmの値を表す場合、アルゴリズムはSをT + (∑ m _i B ⁱ ) Nに設定します。MultiPrecisionREDC と REDC は同じ出力を生成するため、この合計は REDC アルゴリズムが行うmの選択と同じです。

Tの最後のワードT [ r + p ] (および結果的にS [ p ] )は、最初の縮約結果が0 ≤ S < 2Nの範囲の結果にバインドされているため、キャリーを保持するためにのみ使用されます。したがって、 R ≥ 2Nであることが事前にわかっている場合は、この余分なキャリーワードを完全に回避できます。一般的なバイナリ実装では、これは、 Nのビット数がRのビット数よりも小さい場合はこのキャリーワードを回避できると言うことと同じです。それ以外の場合、キャリーは 0 または 1 になります。プロセッサによっては、このワードをフルサイズのワードではなくキャリーフラグとして格納できる場合があります。

多倍長乗算とREDCを1つのアルゴリズムに組み合わせることが可能です。この組み合わせたアルゴリズムは通常、モンゴメリ乗算と呼ばれます。Koç、Acar、Kaliskiによっていくつかの異なる実装が説明されています。^{[5]アルゴリズムは}p + 2ワード（およびキャリービット）のストレージ しか使用しません。

例として、B = 10、N = 997、R = 1000とします。a = 314、b = 271とします。 aとbのモンゴメリ表現は、314000 mod 997 = 942、271000 mod 997 = 813です。942 ⋅ 813 = 765846を計算します。 MultiPrecisionREDC への初期入力T は[6, 4, 8, 5, 6, 7] になります。数値Nは [7, 9, 9] と表されます。拡張ユークリッドの互除法によれば、−299 ⋅ 10 + 3 ⋅ 997 = 1なので、N ′ は7 になります。

私 ← 0
m ← 6 ⋅ 7 を 10 で割った値 = 2

jTc
- ------- -
0 0485670 2     (最初のループの最初の反復後)
1 0485670 2
2 0485670 2
3 0487670 0     (2番目のループの最初の反復後)
4 0487670 0
5 0487670 0
6 0487670 0

私 ← 1
m ← 4 ⋅ 7 を 10 で割ると 8 になる

jTc
- ------- -
0 0087670 6     (最初のループの最初の反復後)
1 0067670 8
2 0067670 8
3 0067470 1     (2番目のループの最初の反復後)
4 0067480 0
5 0067480 0

私 ← 2
m ← 6 ⋅ 7 を 10 で割った値 = 2

jTc
- ------- -
0 0007480 2     (最初のループの最初の反復後)
1 0007480 2
2 0007480 2
3 0007400 1     (2番目のループの最初の反復後)
4 0007401 0

したがって、最終的な比較と減算を行う前は、S = 1047です。最終的な減算の結果は 50 になります。314 ⋅ 271 mod 997 = 349のモンゴメリ表現は349000 mod 997 = 50なので、これが予想される結果です。

2 進数で作業する場合、各段階で正しいm を決定するのは特に簡単です。現在作業中のビットが偶数の場合、m は0 になり、奇数の場合、m は1 になります。さらに、MultiPrecisionREDC の各ステップでは最下位ビットのみを知る必要があるため、モンゴメリ乗算はキャリー保存加算器と簡単に組み合わせることができます。

モンゴメリ減算は、商の桁の推定値が不正確な場合に従来の除算で必要な修正手順を回避するため、タイミングと電力のサイドチャネル攻撃の主なターゲットである条件分岐がほとんどありません。実行される命令のシーケンスは、入力オペランドの値とは無関係です。唯一の例外は、最後のモジュラスの条件付き減算ですが、簡単に変更して（常にモジュラスまたはゼロのいずれかを減算するように）耐性を持たせることができます。^[4] もちろん、乗算プリミティブに基づいて構築された累乗アルゴリズムも耐性があることを保証する必要があります。^{[4] [6]}

• バレット縮小

• Henry S. Warren ,  Jr. (2012 年 7 月)。「モンゴメリ乗算の理論と実践」。CiteSeerX 10.1.1.450.6124。