RSA暗号系

出典: ASCII.jpデジタル用語辞典

あーるえすえーあんごうけい 【RSA暗号系】 RSA cryptosystem

公開キー暗号システムでは、2つのキーによって暗号化と復号するが、このキーの決め方や、演算アルゴリズムによって数々のバリエーションがある。最も有名なのがRivest, Shamir, Adlemanらによって提唱されたRSA暗号系である。RSA暗号系では2つのキーは次のようにして決める。

ある2つの大きな素数pとqを選んで、その積n=pqを求める。(p-1)×(q-1)以下で(p-1)×(q-1)と互いに素な整数eを選び、

e×d ≡ 1 mod ((p-1)×(q-1))

を満たす整数dを求める。すると(e, n)が公開キー、(d, n)が秘密キーとなる。

文Mを暗号化するには、次のようにする。

C = Memod n

暗号文Cを復号するには、次のようにする。

M = Cdmod n

公開キー(e, n)から秘密キー(d, n)を求めるためには、nを素因数分解してpとqを求める必要があるが、実際にはpやqは数百bitになるように決めるので、このような長大な数の素因数分解は(現在のところ)現実的な時間内には実行不可能である。