RSAアルゴリズム

メッセージの暗号化

アリスは公開鍵( n {displaystyle n,} & e {displaystyle e,} )をボブに渡し、秘密鍵を保持する。ボブはメッセージMをアリスに送りたい。

まず彼は、パディングスキームとして知られる合意された可逆プロトコルを使用して、Mをn {displaystyle n} より小さい数m {displaystyle m} に変換する。そして、それに対応する暗号文 c {displaystyle c,} を計算する。

c = m e mod n {displaystyle c=m^{e}mod {n}}}

これは、二乗による指数計算の方法を用いれば、すぐにできる。そして、Bobはc {displaystyle c,} をAliceに送信する。

メッセージの復号化

Aliceは、以下の手順で秘密鍵d {displaystyle d,} を用いて、c {displaystyle c,} から m {displaystyle m,} を復元することができる。

m = c d mod n {displaystyle m=c^{d}{bmod {n}}}.

m {displaystyle m,} を与えると、元の明瞭な素数を復元できる。この2つの合同に中国の余りの定理を適用すると、次のようになる。

m e d ≡ m mod p q {displaystyle m^{ed}equiv m{bmod {pq}}} .

このように

c d ≡ m mod n {displaystyle c^{d}equiv m{bmod {n}}} .

動作例

ここでは、RSAの暗号化と復号化の例を示します。ここで使われているパラメータは人工的に小さくしたものですが、OpenSSLを使って実際のキーペアを生成して調べることもできます。

1. ランダムに素数を2つ選びます。
2. : p = 61 {displaystyle p=61} and q = 53 ; {displaystyle q=53;}.Compute n = p q {displaystyle n=pq,} }.
3. : n = 61 ∗ 53 = 3233 {displaystyle n=61*53=3233}.
4. Totalient φ ( n ) = ( p - 1 ) ( q - 1 ) {displaystyle \phi (n)=(p-1)(q-1)\,} を計算します。
5. : ϕ ( n ) = ( 61 - 1 ) ( 53 - 1 ) = 3120 {displaystyle \phi (n)=(61-1)(53-1)=3120}.
6. Choose e > 1 {displaystyle e>1} coprime to 3120
7. : e = 17 {displaystyle e=17}.
8. Choose d {displaystyle d,} to satisfy d e mod ϕ ( n ) ≡ 1 {displaystyle de{bmod {} Neitherphi (n)}} {equiv 1,} } }.
9. : d = 2753 {displaystyle d=2753}
10. : 17 ∗ 2753 = 46801 = 1 + 15 ∗ 3120 {displaystyle 17*2753=46801=1+15*3120} .

公開鍵は( n = 3233 {displaystyle n=3233} , e = 17 {displaystyle e=17} )である。padded message m {displaystyle m,} に対して、暗号化関数c = m e mod n {displaystyle c=m^{e}{displaymod {n}}} は次のようになる。

c = m 17 mod 3 233 {displaystyle c=m^{17}{thebmod {3}}233,}}

秘密鍵は( n = 3233 {displaystyle n=3233} , d = 2753 {displaystyle d=2753} )である。復号化関数 m = c d mod n {displaystyle m=c^{d}{Thinkbmod {n}}} は次のようになる。

m = c 2753 mod 3 233 {displaystyle m=c^{2753}{thebmod {3}}233,} }.

例えば、m=123を暗号化する場合、{displaystyle m=123} とする。を計算する。

c = 123 17 mod 3 233 = 855 {displaystyle c=123^{17}{Thinkbmod {3}}233=855}.

To decrypt c = 855 {displaystyle c=855}.を計算する。

m = 855 2753 mod 3 233 = 123 {displaystyle m=855^{2753}{Threebmod {3}}233=123}.

これらの計算はいずれも、モジュラーエキスポーネーションの平方・乗算アルゴリズム[en]を用いて効率的に計算することができる。

オイラーの定理からRSA方程式を導き出す

RSAはオイラーの定理とオイラーの積分関数を用いて簡単に導出することができる。

オイラーの定理から始める。

m ϕ ( n ) ≡ 1 ( mod n ) {displaystyle m^{Copy (n)}}equiv 1{pmod {n}}}.

暗号化されたメッセージを正しい鍵で復号化すると、元のメッセージが得られることを示さなければならない。パディングされたメッセージmが与えられたとき、暗号文cは次のように計算されます。

c ≡ m e ( mod n ) {displaystyle cequiv m^{e}{pmod {n}}} 。

復号アルゴリズムに代入すると、次のようになります。

c d ≡ ( m e ) d ≡ m e d ( mod n ) {displaystyle c^{d}}equiv (m^{e})^{d}equiv m^{ed}{pod {n}}} {displaystyle c^{d}equiv (m^{d})^{ed}{pod {n}} {displaystylec^{d}}{d}}とする。

この値もmと合同であることを示したい。eとdの値は飽和するように選ばれている。

e d ≡ 1 ( mod ϕ ( n ) )({displaystyle edequiv 1{pmod {phi (n)}})

つまり、以下のようなある整数kが存在する。

e d = k × ϕ ( n ) + 1 {displaystyle ed=ktimes \phi (n)+1}.

ここで、暗号化されたメッセージと復号化されたメッセージに置き換えてみます。

m e d ≡ m k ϕ ( n ) + 1 ≡ m × m k ϕ ( n ) ≡ m × ( m ϕ ( n ) ) k ( mod n ) {displaystyle {begin{aligned} m^{ed}&\Ȃ m^{kathy (n)+1} Ȃ m^{kathy (n)} Ȃ mttp(m^{kathy (n)}right)^{k}{pod {n}} end{aligned}}} ↘↘ m^{kathy (n)+1} ↘ meph!

オイラーの定理を適用し、結果を得る。

m × ( 1 ) k ≡ m ( mod n ) {displaystyle mtimes (1)^{k}equiv m}{pmod {n}}}.

パディングスキーム

実際に使用する場合、RSAは何らかのパディングスキームと組み合わせ、Mの値が安全でない暗号文にならないようにする必要がある。パディングなしで使用されるRSAには、いくつかの問題がある。

• m = 0またはm = 1は、指数の特性により、常にそれぞれ0または1に等しい暗号文を生成する。
• 暗号化指数が小さく（例えばe = 3）、かつmが小さい値で暗号化する場合、m e {displaystyle m^{e}} の（非修飾）結果が厳密に係数nより小さい場合がある。この場合、暗号文は係数を無視してethルートを取ることで容易に復号化できる可能性がある。
• RSA暗号は決定論的な暗号化アルゴリズムである。ランダムな要素を持たない。したがって、攻撃者は暗号システムに対して選択平文攻撃を成功させることができる。攻撃者は、公開鍵の下で可能性の高い平文を暗号化して辞書を作成し、その結果の暗号文を保存することができます。そして、攻撃者は通信路を監視することができる。辞書に載っている暗号文と一致するものがあれば、その辞書を使ってメッセージの内容を知ることができる。

実際には、短いASCIIメッセージを送信するときに、最初の2つの問題が発生する可能性があります。このようなメッセージでは、m は 1 つ以上の ASCII エンコード文字を連結したものである可能性があります。ASCII の NUL 文字 1 つ（数値は 0）からなるメッセージは m = 0 と符号化され、e と N がどの値であっても 0 の暗号文が生成されます。同様に、単一の ASCII SOH (数値は 1) は常に 1 の暗号文を生成します。従来 3 のような小さな e の値を使用していたシステムでは、最大の m は 255 という値になり、255³ は妥当なモジュラスよりも小さいため、この方式でコード化したすべての単一文字の ASCII メッセージは安全ではありません。このような平文は、単に暗号文の立方根を取ることで復元することができます。

これらの問題を回避するため、実用的なRSAの実装では、暗号化する前に値mに構造化されたランダムなパディングを何らかの形で埋め込むのが一般的である。このパディングにより、mが安全でない平文の範囲に入らないこと、また、あるメッセージがパディングされると、多数の異なる可能な暗号文のうちの1つに暗号化されることが保証される。後者の性質は、辞書攻撃のコストを合理的な攻撃者の能力を超えて増加させる可能性があります。

PKCSのような標準規格は、RSA暗号化の前にメッセージを安全にパッドするように慎重に設計されています。これらの方式は、平文 m にある数のビットを追加してパディングするため、パディングされないメッセージ M のサイズはいくらか小さくならざるを得ません。RSAパディング方式は、巧妙な攻撃を防ぐために慎重に設計する必要があります。これは、予測可能なメッセージ構造によって容易になる場合があります。PKCS標準の初期のバージョンでは、アドホックな構造を使用していましたが、後に実用的な適応型選択暗号文攻撃に対して脆弱であることが判明しました。最近の構成では、最適非対称暗号パディング（OAEP）のような安全な技術を使用して、これらの攻撃を防ぎつつメッセージを保護します。また、PKCS規格には、RSA署名の安全性を高めるための処理方式として、RSA-PSS（Probabilistic Signature Scheme for RSA）などがある。

メッセージの署名

アリスがボブの公開鍵を使って彼に暗号化されたメッセージを送ったとします。メッセージの中で、彼女はアリスだと主張することができますが、 誰でもボブの公開鍵を使って暗号化されたメッセージを送ることができるので、 ボブはそのメッセージが本当にアリスからのものかどうかを確認する手段がありません。ですから、メッセージの出所を確認するために、 RSA はメッセージに署名するのにも使われます。

アリスが署名されたメッセージをボブに送りたい場合を考えてみよう。アリスはメッセージのハッシュ値を生成し、（メッセージを復号するときと同じように） d mod nの累乗に上げて、それをメッセージに「署名」として添付する。署名されたメッセージを受け取ったボブは、署名をe mod nのべき乗にし（メッセージを暗号化するときと同じ）、得られたハッシュ値とメッセージの実際のハッシュ値とを比較する。もしこの二つが一致すれば、ボブはメッセージの作者がアリスの 秘密鍵を持っていて、それ以降メッセージが改竄されていないことを知ります。

RSA-PSSのような安全なパディング方式は、メッセージの暗号化と同様に署名の安全性にも不可欠であり、同じ鍵を暗号化と署名の両方の目的で使用してはならないことに注意すること。