DH鍵交換アルゴリズムが提唱されて間もなく考案されたのが、RSAアルゴリズムである。この名前は、発明者であるロナルド・リベスト（Ronald Rivest）、アディ・シャミア（Adi Shamir）、レオナルド・エーデルマン（Leonard Adleman）の頭文字に由来する。
RSAには、2つのプリミティブが使われている。公開鍵暗号アルゴリズム（非対称暗号）と、デジタル署名方式である。どちらも、暗号アルゴリズムとしては非対称暗号に分類される。これらのプリミティブのしくみと、それが有益な理由について説明する。
非対称暗号化と対称暗号化の違い
まず、非対称暗号は、目的だけを見れば前述した対称暗号アルゴリズムと似ている。秘密を守るためにメッセージを暗号化するという目的だ。だが、対称暗号では2人の参加者が共通の対称鍵を使ってメッセージの暗号化と復号を行ったのに対して、非対称暗号は次の点でまったく異なっている。
- 公開鍵と秘密鍵という2種類の鍵を使う
- 立場が非対称的。公開鍵による暗号化は誰にでもできるが、秘密鍵をもっていなければそれを復号できない。
非対称暗号の使い方を、またシンプルな比喩で説明しよう。おなじみのアリス女王が、秘密鍵と、それに対応する公開鍵をもっている。ここでは、女王の公開鍵を宝箱で表す。誰でも使えるように、蓋が開いた宝箱だ（図9）。
これで、どこの誰でも、公開鍵を使ってアリス女王宛てのメッセージを暗号化できるようになった。この比喩では、メッセージを宝箱に入れて蓋を閉めることに当たる。
いったん蓋を閉めた宝箱は、アリスしか開けなくなるので、人の目からメッセージの秘密が正しく保護されたことになる。蓋を閉めた宝箱（つまり暗号化されたメッセージ）がアリス女王のもとに運ばれると、アリスは秘密鍵（アリスしか知らない）を使ってそれを復号できる（図10を参照）。
ここまでに学んだ暗号プリミティブを、図11にまとめてみよう。現実世界の暗号をめぐる旅の終点までに必要なのは、あともうひとつだけだ。
デジタル署名：紙とペンを使う署名にかわるもの
RSA暗号では、以上に見てきたように非対称暗号アルゴリズムを用いるが、前述したようにデジタル署名というアルゴリズムも用意されている。暗号プリミティブとしてデジタル署名が登場したことによって、世界中の当事者間で、信頼の確立は大きく進んだ。デジタル署名は、アパートを借りるとき契約書に書く現実の署名とほぼ同じようなものだ。
「署名を捏造されたらどうしよう？」と不安を覚えるのはもっともで、現実の世界では署名が確実にセキュリティを保証するとはかぎらない。それに対して、暗号学的な署名は、使い方こそ似ているが、ユーザーの名前が記された証明書を伴う点が異なる。
暗号学的な署名は捏造できないうえに、他者が簡単に検証できるようになっている。小切手に書くような、昔ながらの署名と比べてはるかに実用的なのだ。
