『シーザー暗号』と呼ばれる暗号は、アルファベットの文字を何文字かず らして暗号文を作り、受信者がずらした分だけアルファベットを逆にずら して復号するものです。例えば、
この様に送信者と受信者がお互いに暗号化・復号化の方法（『鍵』と呼び ます）を打ち合わせておく暗号は、今では『古典的暗号』と呼ばれていま す。シーザー暗号は簡単過ぎてすぐに破られてしまいますが、実用的な古 典的暗号は一般的に非常に複雑な『鍵』を必要とします。 更に古典的暗号には次の様な欠点があります。
古典的暗号は送信者と受信者の間で『鍵』を受け渡しする必要があります が、この受け渡しの過程で『鍵』を盗まれる危険があります。例えば通信 で『鍵』を送る場合、通信を盗聴されればおしまいです。
また、利害の一致しない多人数が通信し合う場合、その中の「ふたりの組 み合わせ」の全てに対してひとつずつ異なる『鍵』を必要とします。現代 の情報化社会では『鍵』を作るだけでも大変な時間とコストが掛かってし まいます。
『公開鍵暗号』とは、受信者が『暗号化鍵』を公開してしまい、自分だけ が持っている『復号化鍵』を使って暗号文を復号するという暗号です。公 開鍵暗号は古典的暗号に比べて必要な鍵の個数が遥に少なく、また復号化 鍵を受け渡しする必要がないので、鍵の管理の面でも安全です。
公開鍵暗号を設計するには、「暗号化鍵と暗号文からは復号化鍵が計算で きない」ような鍵を作る必要があります。 ここで「計算できない」ということは、「理論的には計算可能であるが、 どんな優秀なコンピュータを用いても天文学的時間が掛かってしまう」と いうことを意味します。
代表的な公開鍵暗号として RSA 暗号を紹介しましょう。
受信者はふたつの大きな素数 p, q を用意し、更に f = ( p - 1 ) ( q - 1 ) とは互いに素な自然数 e を選んで
送信者は送信文を整数 w に変換し、さらに w から
計算できる限界に近い大きな素数をふたつ（ p, q とします）作ると、 それらの積 n = p q を素因数分解するには膨大な時間が掛かると考え られています。復号化鍵 d を計算する為には p も q もわから ないといけないので、その意味で RSA 暗号は安全だと考えられているの です。
上で述べたとおり、公開鍵 n を素因数分解すると RSA 暗号を破るこ とができます。高速な素因数分解のテクニックとして最近注目されている ものとしては、