RSA暗号の方法

　　　　2006/03/20 早稲田大学　後保範 (Waseda University, Ushiro Yasunori )
　　　　2006/11/15 指摘修正(1.(2)(b)の(n,e)のeの値)

1. RSA暗号鍵の作成

　(1) RSA鍵の作成法
　　　下記に従い作成し、(e,n)は公開暗号鍵でdが秘密復号鍵となる。
　　(a) 素数p,q及びeを選ぶ。
　　(b) n=p×q及びf=(p-1)×(q-1)を計算する。
　　(c) d=1/e mod(f)となる整数dを計算する。
　(2) RSA鍵の作成例
　　(a) 素数p,q及びeを選ぶ。
　　　　p=239,q=547,e=43291
　　(b) n=p×q及びf=(p-1)×(q-1)を計算する。
　　　　n=239×547=130733, f=(p-1)×(q-1)=129948
　　　　(n,e)=(130733,43291)を公開する。
　　(c) d=1/e mod(f)となる整数dを計算する。
　　　　d=1/e=(43291)^-1=105691 mod f
　　　　この計算はユークリッド互除法で行う。

2. RSA暗号化と復号化

　(1) RSA暗号化
　　(a) 送信する文章を一定桁単位に数字(M_k), k=1,2,...に変換する。
　　(b) 数字の列(M_k)を下記で暗号化し数字の列C_kに変換。
　　　　　C_k=M_k^e mod n
　　(c) 暗号変換後の数字の列C_k, k=1,2,...を送信する。
　(2) RSA復号化
　　(a) 数字の列C_k, k=1,2,...を受信する。
　　(b) 数字の列(C_k)を下記で暗号化前の数字の列M_kに変換。
　　　　　M_k=C_k^d mod n
　　(c) 一定桁の数字の列(M_k), k=1,2,...を文字に逆変換する。
　(3) RSA暗号変換例
　　(a) 鍵とメッセージ(文章)
　　　　公開暗号鍵：e=43291, n=130733
　　　　秘密復号鍵：d=105691
　　　　英数字変換：A=0, B=1,..., E=4, S=18, Y=24
　　　　メッセージ：YES <---> M₁=24*26²+4*26+18=16346
　　(b) 暗号化
　　　　C₁=M₁^e=16346⁴³²⁹¹=49616 mod n
　　(c)　復号化
　　　　M₁=C₁^d=49616¹⁰⁵⁶⁹¹=16346 mod n

3. 復号化の数学的理論

　(1) オイラーの定理
　　　n=p×qとMが互いに素ならオイラーの定理により下記が成立する。
　　　　M^(p-1)(q-1)=1 mod n
　(2) C^d mod nがMに戻る原理
　　　ed=1 mod fのためed=af+1=a(p-1)(q-1)+1を使用すると下記が成立する。
　　　　C^d=(M^e)^d=M^af+1=(M^(p-1)(q-1)) ^a×M=M mod n