MITのRivest, Shamir, Adlemanの3人によって提唱された 代表的な公開鍵暗号方式.
公開鍵暗号方式とは, 「暗号化鍵」と「復号化鍵」という2つの鍵をペアで利用し, そのうち「暗号化鍵」は公開して構わないという特徴を持っている. 通信文を送信する場合には, 公開されている「暗号化鍵」によって暗号化し, 受信者は, 各自で秘密にしている「復号化鍵」で元に戻すことができる. これらの鍵は数学的な関係に基づいて決められており, 鍵の決め方や演算アルゴリズムによって様々なバリエーションが存在するが, それらの中で最も有名なものがこのRSA暗号である. RSA暗号の基本的なアルゴリズムは以下の通り.
まず, ある2つの大きな素数pとqを選んで, その積n=pqを求める. 次に (p-1)×(q-1) 以下で (p-1)×(q-1) と互いに素な整数eを選び,