ＲＳＡ暗号

質問

Ｓ＝a^d modN
データのビット長をn、dのバイナリ表現を、d=(d[n-1]d[n-2]...d[0])とする。

; monobit method
S=1
For j=n-1 downto 0
S=S^2 modN
If d[j]=1 then
S=S*a modN
EndIf
EndFor
Return S

このときは、S=a^11 modNなどの計算の仕方は分かるのですが、
a(j)=a^j modN, j=0,1,2,...,2^(w)-1
簡単のため、wは、nを割り切るものと仮定。データのビット長をn,dの表現を、d=(d[n/w-1]d[n/w-2]...d[0])(d[j]は、wビットブロック）とする。

; monobit method
S=1
For j=n/w-1 downto 0
S=S^(2^w) modN
S=S*a(d[j]) modN
EndFor
Return S

このときは、どういう計算式になるのですか。どういう計算が出来るのですか。s=a^11 modN みたいな計算も出来るのですか。教えてください。

回答No.1

uyama33

同じ値です。

例えば、

１０進の１5＝２進の１1１１
１5＝２＾３＋2^2+２＾１＋２＾０

ｗ＝２

として、
a^15=a^(２＾３＋2^2+２＾１＋２＾０)
=a^(２＾３+2^2)*a^(２＾１＋２＾０)
=a^((2^1+1)*(2^2)) * a^(2^1+2^0)
=(a^(2^1+1))^(2^2) * a^(2^1+2^0)

最初に、
S=S*a(d[j])
が計算されて、

それが
(2^2)乗されます。 （S=S^(2^w) modN）

最後に、ｓ=(a^(2^1+1))^(2^2)

a(d[j]) ＝a^(d[0]) ＝a^(2^1+2^0)

なので、

S=S*a(d[j]) modN

で、a^d

が計算できます。

結局同じです。

適当に切っても良いと思いますが、
ループが面倒です。

計算しやすい長さにするのがよい。

１１＝