浅谈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)