法nにおけるe乗根が計算できれば、暗号文を復号できる。 当然これは（法nの素因数がわからない限り）非常に難しいと考えられていて、RSA暗号の安全性の重要な根拠の一つになっている。
しかし、まったく同一の平文を、異なる法において同一のeを用いて暗号化した暗号文をe個以上集めることで、各々の法に関して中国の剰余定理を用いれば通常の冪根演算によって平文を復元できる。これが同報通信の誤用である。
ここから中国の剰余定理によって上記式を満たす
を求めることができる。このときであり、またmはどの法nよりも小さいためであることから、c = me
このcのe乗根を求めることで平文mが求められる。
これはeとして特に3や65537が、2進数表示したときに1の個数が少ないために暗号化処理を高速化できるという理由から好んで用いられるために発生しうる問題である。実際の暗号への応用においてはフォーマットとして、mの一部に毎回生成する乱数を挿入することでこの攻撃を回避している。
RSA暗号の入力は、モジュラスをnとすると0?（n-1）の範囲の整数である。n以上の値の平文を暗号化する際には、平文を分割して処理することになる。
この時に留意しなければならない点として、例えば、nが1024ビット（=128バイト）であるとき、平文を同じ1024ビット毎に分割処理するのでは十分ではないという点がある。これは、n, mが共に1024ビットであったとしても、n<mの場合には、結果として出力されるのは、m mod nに対応する暗号文であり、復号してもmは出力されないためである。
平文をビット単位（やバイト単位）で分割する際には、まず、nの下限を定めたうえで、平文の全ビットを1に（全バイトを0xFFに）してもnより小さくなるビット数（バイト数）で分割しなければならない。例えば、nの下限をn≧2^1023とした場合、平文は1023ビットごとに分割する。こうすることでm<nの条件が常に満たされる。
一方で、出力となる暗号文は0?(n-1)の範囲の整数になるため、先の例で（nの下限より小さいビット数）1023ビット毎に分割されたmに対応する暗号文の中には、1024ビットが必要となるものがある。つまり、平文をビット単位で分割する場合には暗号化によってメッセージサイズが増加するといえる。これを回避するにはビット単位で分割するのではなく、平文mをn進数表示したときの各桁毎に分割すればよい。
暗号方式のままの方式（生RSA、教科書的RSAということがある）では、
暗号文を分解して、個々の暗号文に対応する平文を入手できる（選択暗号文攻撃）と、元の暗号文に対応する平文を求めることができてしまう、
攻撃者が暗号文を変形して、平文自体を知ることはできないが、平文を変形できてしまう（非展性がない）、
などの好ましくない性質があるため、実際に暗号として使用する際には、パディングなどのフォーマットを定義し、平文空間を限定することが必要である。パディングも含めたものとして、
RSA_PKCS
RSA_OAEP
などがある。
RSA暗号が実現した公開鍵暗号方式は、従来の暗号方式（共通鍵暗号）とは異なり、暗号化は公開鍵を使って誰でもできるが、復号は秘密鍵を持つ本人だけしかできない方式である。この復号は「本人だけしかできない」という性質を利用すると、デジタル署名（あるいは認証機能）が実現できる。
そのためには、公開鍵・秘密鍵を次のように使用する。
暗号の場合
平文 ---公開鍵（暗号化）----> 暗号文、暗号文 ---秘密鍵（復号）-----> 平文
署名の場合
文書 ---秘密鍵（署名生成）--> 署名値、署名値 --公開鍵（署名検証）--- 文書
公開鍵と秘密鍵の役割は通常の場合においては上記の通り、公開鍵は暗号化に使われ、秘密鍵は復号に用いられるが、RSA暗号においては平文と暗号文の定義域が同じ（平文空間＝暗号文空間である）ため、任意の文書（メッセージ）を暗号文とみなして復号することができる。つまり秘密鍵を用いて任意の文書について署名値を生成でき、公開鍵を用いてその署名値を暗号化して元の文書と一致するかを調べることで署名の検証ができる。
ただし、RSA暗号と同様に、生RSAでは、署名の潜在的偽造等の好ましくない性質があるため、パディングなどが必要である。また、暗号文空間よりも大きなメッセージを扱うためにハッシュ関数と組み合わせて使用する。
このようなパディングなども含めたものとして、
RSA_PSS with SHA-1
などがある。
原論文
A Method for Obtaining Digital Signature and Public-key Cryptsystems; R.L.Rivest,A.Shamir,and L.Adelman; MIT Laboratory for Computer Science; Thechnical Memo LCS/TM82; April 4,1977(Revised December 12,1977); （「日経エレクトロニクス」に翻訳が出たと思う）
関連項目
暗号
暗号理論
RSA-OAEP
RSA-OAEP＋
素因数分解
カテゴリ: 暗号
更新日時:2008年6月12日(木)06:58
取得日時:2008/10/09 20:56