浅谈RSA公钥密码学(数字签名技术&加密，包含严格数学证明) by FORWARD
[数论—现代密码学—非对称密码体制]
①RSA加密算法 ②RSA数字签名算法 ③公共信道上的RSA数字签名算法（加密+签名）
Encrypt()加密运算 PublicKey公钥
Decrypt()解密运算 SecretKey私钥
Sign()签名运算
明文/消息M 密文C 签名S
（1）RSA加密算法
(i)算法实现
-选择两个互异大素数p，q
-计算：n=pq φ(n) =(p-1)(q-1)
-随机选择e∈N+，满足gcd(e，φ(n))=1
-找到d∈N+，使得ed≡1(mod φ(n))
记公钥PK={e，n} 私钥SK={d}
-加密算法（对明文M加密）
C=Enc(M)=M＾e(mod n)
-解密算法（对密文C解密还原）
M=Dec(C)=C＾d(mod n)
(ii)算法数学证明（解密的唯一性）
证：
C＾d(mod n)=(M＾e(mod n))＾d (mod n)=[(M＾e (mod n))(M＾e (mod n))*......*(M＾e (mod n))] (mod n)=M＾ed (mod n)
∵ed≡1 mod(φ(n))
∴ed=kφ(n)+1
By Euler Theorem:M＾φ(n)≡1 (mod n)
∴M＾(φ(n)+1)≡M (mod n)
∴M＾(kφ(n)+1)≡M (mod n)
∴M＾(kφ(n)+1)=M (mod n)
∵M＜n
∴C＾d (mod n)=M
证毕
（2）RSA数字签名算法
(i)算法实现(与加密算法相似)
-选择两个互异大素数p，q
-计算：n=pq φ(n) =(p-1)(q-1)
-随机选择e∈N+，满足gcd(e，φ(n))=1
-找到d∈N+，使得ed≡1(mod φ(n))
记公钥PK={e，n} 私钥SK={d}
-签名算法（对消息M签名）：
S=Sig(M)=M＾d (mod n)
-验证算法（对签名S的验证）：
M`=S＾e (mod n)
若M｀=M，则签名S属实/不可抵赖
(ii)算法数学证明（验证的唯一性）
证：
M｀=S＾e (mod n)=(M＾d (mod n))＾e (mod n)=[(M＾d (mod n))(M＾d (mod n)*.....*(M＾d (mod n))] (mod n)=M＾de (mod n)
∵de≡1 mod(φ(n))
∴de=kφ(n)+1
By Euler Theorem:M＾φ(n)≡1 (mod n)
∴M＾(φ(n)+1)≡M (mod n)
∴M＾(kφ(n)+1)≡M (mod n)
∴M＾(kφ(n)+1)=M (mod n)
∵M＜n
∴M｀=S＾e (mod n)=M
证毕
③在公共信道下的数字签名算法实现（签名+加密）
记发送者A， 接收者B ，消息M，密文C
记A的公钥PK1，私钥SK1
记B的公钥PK2，私钥SK2
算法实现：
-选择两个互异大素数p1，q1
-计算：n1=p1q1 φ(n) =(p1-1)(q1-1)
-随机选择e1∈N+，满足gcd(e1，φ(n1))=1
-找到d1∈N+，使得e1d1≡1(mod φ(n1))
记A的公钥PK1={e1，n1}，私钥SK1={d1}
-选择两个互异大素数p2，q2
-计算：n2=p2q2 φ(n2) =(p2-1)(q2-1)
-随机选择e2∈N+，满足gcd(e2，φ(n2))=1
-找到d2∈N+，使得e2d2≡1(mod φ(n2))
记B的公钥PK2={e2，n2}，私钥SK2={d2}
签名算法（对M签名）：
S=Sig(M)=M＾d1 (mod n1)
包装算法（对S包装）：
C=Enc(S)=S＾e2 (mod n2)
拆包算法（对C拆包）：
S=Dec(C)=C＾d2 (mod n2)
验证算法（对S验证）
M｀=S＾e1 (mod n1)
