RSA

RSA暗号の暗号的強度は、大きな数の素因数分解が難しいという点に依存している。

まず公開鍵が作られる。適当な整数eと二つの大きな素数{p, q}を作り、素数の積をnとする(n=pq)。この{e, n}が公開鍵となり、公開される。

また、復号に使うdを秘密鍵といい、{p, q}とeから計算される。これは機密に保持される。

平文をm、暗号文をcとすると、次のように表現できる。

c = m^e mod n

m = c^d 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を必須とするようになった。