RSA暗号
RSA暗号の入力は、公開鍵の法を n とすると 0 から n − 1 の範囲の整数である。n 以上の値の平文を暗号化する際には、平文を分割して処理することになる。
この時に留意しなければならない点として、例えば、n が1024ビット(= 128バイト)であるとき、平文を同じ 1024ビット毎に分割処理するのでは十分ではないという点がある。これは、n と m が共に 1024ビットであったとしても、n < m の場合には、結果として出力されるのは、 m mod n {\displaystyle m{\bmod {n}}} に対応する暗号文であり、復号しても m は出力されないためである。
平文をビット単位(やバイト単位)で分割する際には、まず、n の下限を定めた上で、平文の全ビットを 1 に(全バイトを F F 16 {\displaystyle \mathrm {FF_{16}} } に)しても n より小さくなるビット数(バイト数)で分割しなければならない。例えば、n の下限を n ≥ 2 1023 {\displaystyle n\geq 2^{1023}} とした場合、平文は 1023 ビットごとに分割する。こうすることで m < n の条件が常に満たされる。
一方で、出力となる暗号文は 0 から n − 1 の範囲の整数になるため、先の例で(n の下限より小さいビット数)1023ビット毎に分割された m に対応する暗号文の中には、1024ビットが必要となるものがある。つまり、平文をビット単位で分割する場合には暗号化によってメッセージサイズが増加するといえる。これを回避するにはビット単位で分割するのではなく、平文 m を n 進数表示したときの各桁毎に分割すればよい。