RSA暗号
公開した暗号(e,n)で、暗号化してもらう。これは秘密キーでｄで復号できる。暗号化キーを公開できるため、不特定の人との暗号通信に利用できます。公開鍵暗号とも呼ばれます。
PGPツール
公開キー、秘密キーを取得できます。これを利用した暗号化メッセージの作成、解読ができます。
例
p=5,q=11,n=55、
e=17,d=13
x=3を暗号化する
34(mod55)=26
手順
二つの大きな素数p,qを選びます。n=p・q とします。
p-1とq-1の最小公倍数をrとし、rと互いに素な数dを選択し、秘密キーとします。
e・d=1（モードr）となる数eを求め、e,nを公開します
送りたいメッセージをｘとして、
xe=c (mod n)
で暗号化します。
cd=x(mod n) で復号できます。
オイラーの定理
を利用しています。
((xe)d)=x (mod n)
nが十分大きいとき、これを素因数分解することが困難であることを利用しています。