RSA 算法

RSA 算法

RSA 算法概况

由美国 MIT 三位数学家 R.L.Rivest,A.Shamir 和 L.Aaleman 发现一种基于数论构造双钥的方法,被广泛称为 RSA 体制,是世界上第一个技能用于数据加密也能用于数字签名的非对称加密性算法。

RSA 的安全性是基于分解大整数的困难性假定。

RSA 的加密速度很慢,其硬件实现的最快速度也仅为 DES 的千分之一,所以 RSA 一般只用于密钥交换与认证。

数学基础

欧拉函数

φ(n):设 n 是一个正整数,小于 n 且与 n 互素的正整数的个数称为 n 的欧拉函数。

当 n 是素数,小于 n 的所有素数均与 n 互素,因此 φ(n) = n - 1。

对 n = pq,p 和 q 是素数,φ(n)=φ(p)φ(q) = (p-1)(q-1)。

欧拉定理

设 x 和 n 都是正整数,如果 gcd(x, n) = 1,则 \(x^{\varphi (n)}\equiv 1 (mod \ n)\)

费马小定理

设 x 和 p 都是正整数,如果 gcd(x, p) = 1,则 \(x^{p-1}\equiv 1 (mod \ p)\)

算法描述

  1. 独立地选取两大素数 \(p\)\(q\)
  2. 计算 \(n = p\times q\),及其欧拉函数值 \(\varphi (n)=(p-1)(q-1)\)
  3. 随机选择一整数 \(e\) 满足 \(1 < e < \varphi(n),gcd(e,\varphi(n))=1\)
  4. 用扩展欧几里得算法计算 e 的乘法逆元 \(d\)\(d=e^{-1} \ mod(\varphi (n))\)
  5. 将明文分组,各组对应的十进制数小于 \(n\),即分组长度小于 \(log_2 (n)\)
  6. 加密:设明文为 m,则密文为 \(c\)\(c\equiv m^e\ mod(n)\)
  7. 解密:设密文为 \(c\),则明文为 \(m\)\(m\equiv c^d\ mod(n)\)

解密正确性验证

要证:

\[c^d \equiv m\ mod(n)\]

即是要证:

\[m^{ed}\equiv m\ mod(n)\]

因为 \(e\)\(d\) 是模 \(\varphi(n)\) 的乘法逆元,所以

\[ed \equiv 1 \ mod(\varphi(n)) \Leftrightarrow ed =k\varphi(n)+1\]

所以原式等价于

\[m^{ed}\equiv m\ mod(n) \Leftrightarrow m^{k\varphi(n)+1}\equiv m \ mod(n) \Leftrightarrow m^{k\varphi(n)}\equiv1 \ mod (n)\]

现在对 \(m\)\(n\) 的情况进行讨论:

\(gcd(m,n)=1\) 时:

由欧拉定理有 \(m^{\varphi(n)}\equiv1\ mod(n)\),故

\[m^{k\varphi(n)}\equiv1^k\equiv 1\ mod(n) \]

原式得证。

\(gcd(m,n)\not=1\) 时:

因为 n 只有三个因数 1、p、q,所以 m 是 p 或 q 的倍数,m 不可能即是 p 又是 q 的倍数(\(m<n\))。设 \(m=tp\),t 是一个正整数。则:

\[\begin{align}gcd(m,q)=1 &\Rightarrow m^{\varphi(q)}\equiv 1\ mod(q)\\ &\Rightarrow m^{k\varphi(q)}\equiv 1\ mod(q) \\ &\Rightarrow m^{k\varphi(p)\varphi(q)}\equiv 1\ mod(q) \\ &\Rightarrow m^{k\varphi(n)}\equiv 1\ mod(q) \\ &\Rightarrow m^{k\varphi(n)}=rq+1,r \in Z^*\\ &\Rightarrow m^{k\varphi(n)}*m=(rq+1)*m\\ &\Rightarrow m^{k\varphi(n)+1}=(rq+1)*(tp)\\ &\Rightarrow m^{k\varphi(n)+1}=rtn+m \\ &\Rightarrow m^{k\varphi(n)+1}\equiv m \ mod(n) \end{align}\]

原式得证。

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×