公開鍵暗号の一種。
1977年、マサチューセッツ工科大学(MIT)にいたRivest, Shamir, Adleman という三人の研究者によって開発された。
平文をMとし、暗号化された文章をCとする。M,Cともに{0,1,...,n-1}の要素である。
暗号時は
復号時には
という関係が成り立つ。
まだ分からない。巨大な数nの素因数分解を行ないpとqを求めればφ(n)が分かるので、公開鍵から秘密鍵dを入手出来る。しかしnの素因数分解は今のところ多項式時間では解けないと予想されている。
多項式時間で素因数分解が出来れば、RSA暗号は多項式時間で解読される。しかし、RSA暗号が多項式時間で解読されれば、多項式時間で素因数分解が可能かどうかは未解決である。
1994年にShorが量子コンピュータを使うと素因数分解が確率的多項式時間で解けることを示した。したがって、量子コンピュータが開発されるとRSA暗号は暗号としての意味を失う。
リスト::数学関連