RSA
読み：アーエスエイ
外語：RSA: Rivest-Shamir-Adleman
公開鍵暗号方式アルゴリズムの一つで、電子署名に用いられる。
概要
1977(昭和52)年に、ロナルド・リベスト(Ronald Lorin Rivest)、アディ・シャミア(Adi Shamir)、レオナルド・エーデルマン(Leonard Max Adleman)らにより発明された。RSAという名は、この三人の名字の頭文字が取られた。
RSAは、この前年にスタンフォード大学のデフィーとヘルマンが発案したばかりの公開鍵暗号方式を使い、機密性や電子署名の機能を実現するアルゴリズムとして発表された。
RSA暗号は1983(昭和58)年9月20日にアメリカで特許(4,405,829号)
が成立した。この特許は2000(平成12)年9月20日に期限切れとなったが、期限切れに先だって同年2000(平成12)年9月6日にRSAは特許を放棄した。
また、Rivest、Shamir、Adlemanはこの発明の功績を称えられ、2003(平成15)年4月にA.M.チューリング賞を受賞している。
特徴
暗号的強度
RSA暗号の暗号的強度は、大きな数の素因数分解が難しいという点に依存している。
まず公開鍵が作られる。適当な整数eと二つの大きな素数{p, q}を作り、素数の積をnとする(n=pq)。この{e, n}が公開鍵となり、公開される。
また、復号に使うdを秘密鍵といい、{p, q}とeから計算される。これは機密に保持される。
平文をm、暗号文をcとすると、次のように表現できる。
c = me mod n
m = cd mod n
暗号化は、{e, n}が公開されているので簡単にでき、速度も速い。
一方、復号するためにはd、つまりnの素因数{p, q}が分からなければならない。しかし大きな数の素因数分解は難しいことからnから{p, q}を導くことは容易ではなく、もって秘密鍵なしに復号することは難しい。
小さい数を掛け合わせて大きな数にすることはコンピューターなら一瞬でできるが、大きな数を素因数分解するには、どんな高速なコンピューターを使用しても膨大な時間を要するのである。
これが、RSAの暗号としての根拠である。
特許問題
PGPで、セッション鍵の暗号化に使われていたが、特許の問題が存在した。
PGPのRSAに対する特許問題が一応の解決を見たのは、RSAの特許を持つRSADSIが非商用利用でのみ無償利用できるとして配布したツールキットRSAREF 2.0を使うようになったPGP 2.6からである。
OpenSSH始め、暗号通信に関する分野で使われることもあったが、いずれも特許の問題があった。
現在は特許が切れてパブリックドメインになっていることから、広く使われるようになっている。
SSL/TLSも、認証としてRSAとDSAが併用され、TLS 1.0ではDSAを必須としたが、TLS 1.1/1.2では逆にRSAを必須とするようになった。
再検索