RSA

1977年、MITのRivest、Shamir、Adlemanが発表した。前年にDiffieとHellmanが非対称暗号の可能性を示していたが、具体的な方式までは示していなかった。鍵は2つの秘密の素数 p と q から作られ、公開鍵にはその積 n = pq が入る。掛け算は簡単だが、n から p と q を素早く求める方法は誰も知らない。なお英GCHQのClifford Cocksは1973年にほぼ同じ方式を見つけていたが、機密扱いで1997年まで公表されなかった。

RSAは退場しつつある。256ビットの楕円曲線と同等の強度を得るのに2048〜3072ビットの鍵が必要で、署名は遅く、素朴な実装はパディングの誤りから漏えいする。1998年のBleichenbacher攻撃は、今でも新製品で再発する。TLS 1.3はRSA鍵交換を完全に廃止し、署名用にだけ残した。実用的な量子コンピューターが完成すればShorのアルゴリズムで破られるため、これが耐量子暗号の動機そのものになっている。