RSA公钥密码学（数字签名&加密）

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