これら共通鍵方式の欠点を克服したのが、公開鍵方式である。公開鍵方式では 鍵が二種類存在し、それぞれ秘密鍵、公開鍵と呼ばれている（資料2-2）。秘密 鍵は送信者が秘密にしたまま保持しなければならないのに対し、公開鍵は複数 の相手に渡しても構わないし、第三者に入手されても暗号文が解読される心配 が無い。なぜなら一方の鍵で暗号化された暗号文は、その鍵自体での復号化が 不可能であり、その鍵とペアをなす鍵でのみ復号化が可能だからである。
暗号化、復号化の一連の流れは以下の通りである。(1)受信者は自分の公開鍵 を公開登録する。(2)送信者はその公開鍵を入手し、それを用いて平文を暗号 化する。(3)暗号文を送信する。(4)受信者は受け取った暗号文を、公開鍵に対 応する秘密鍵を用いて復号し、平文に戻す（資料2-3）。
この場合、通信相手ごとに新たな鍵を作り直す必要が無く、相手の公開鍵を入 手しさえすればよい。よって暗号の数が少なくて済む。またネットワーク上で 配送されるのは公開鍵のみである。ここで重要なのは公開鍵を盗まれても、そ れによって秘密鍵が推定されないようにすることである。そのために暗号化、 復号化には複雑な計算が要求される。その代表例として「RSA方式」が有名で ある。
RSA方式は1977年にRivest、Shamir、Adlemanという3人の研究者によってマサ
チューセッツ工科大学で開発されたものである
。基本的には素因数分解が持つ「2つの素数を掛け合わ
せてその積を求めるのは容易であるが、掛け合わせた積から元の二つの素数を
導き出すのは、積が大きければ大きいほど非常に困難である」という性質を利
用している（資料2-4）。