- 281 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/21 00:49]
- 6/12
補足
復号した時
M'=(M1*a)+(M2*x) < n
でないとまずいので
nのビット数をNとすると
a,xのビット数はN/2より小さくなければならない。
M1,M2個々のビット数はN/2より小さいけれど、
一度に二つ平文を送れるので
大体一度に送れる平文はNビット位になる
正確には・・・
M1,M2のビット数をbとする。
M1,M2が小さな値の時に
e*((a*M1)+(x*M2))<nとなるのを防ぎたいので
a,xのビット数を(b+2ビット)として、
M1,M2で表現できる値は
0<=M1,M2<=(2^b)-1だから
↑のときM1,M2に2^bを加算してやって
2^b<=M1,M2<=(2^(b+1))-1としてやれば
e*((a*M1)+(x*M2))<nとなる心配はなくなる
復号する時は出てきたM1,M2から2^bを減算してやればよい
