MozhuCY's blog.

RSA

字数统计: 1.1k阅读时长: 4 min
2019/07/30 Share

前置数论知识

欧拉函数

通式

$\phi(x)=x\prod{i=1}^n(1-\frac{1}{p{i}})$

其中 $p_{i}$ 为x所有的质因数

既有对于一个x可以被分解出p1,p2,p3则 $\phi(x) = (p1-1)(p2-1)(p3-1)$

同样若 $x = p1 p1 p2$

则 $\phi(x) = (p1-1)p1^{2-1}(p2-1)$

性质及证明

欧拉函数: $\phi(x)$ ,即小于x的正整数中与x互质的整数的个数

欧拉函数是一个积性函数对于 $\phi(N)$ ,若 $N = m * n$ 且 $m$ $n$ 互质

则有 $\phi(N) = \phi(m) \phi(n)$

对于任意一个质数,易得$\phi(p) = p-1$

故 $\phi(N) = (m - 1)(n - 1)$

若对于 $\phi(N)$ 有 $N = p^k$

即一个$N$为一个质数的$k$次幂,则有: $\phi(N) = p^{k} - p^{k-1} = (p-1)p^{k-1}$

因为$N$为一个质数的$k$次幂时,$\phi(N) = N - 1 - x$,其中x为与N互为合数的个数

由于 $N=p^k$,$[0,p)$ 不存在与 $p^k$ 为合数的数字,所以从 $[p,p^2)$ ,存在 $p,2p…,(p-1)p$ , $[p^2,p^3)$ , 存在一个 $p,2p…,(p-1)pp$ , 递推到 $[p^{k-1},p^k)$

其实就是一个首项为$p-1$,公比为$p$的等比数列求和,最后计算得有 $p^{k-1}-1$ 与其满足条件,故推出上式.

$\phi(p) = p-1$同样在这里成立

欧拉定理

欧拉定理: $a ^ {\phi(N)} = 1 mod N$,当且仅当$a$与$N$互质的时候成立

模逆元:若有 $a = kN + b$ ,则称 b 为 a 的模逆元,一般记为 $a^{-1} = b \ mod \ N$或 $ab = 1 \ mod \ N$
整数 a 对模数 n 之模逆元存在的充分必要条件是 a 和 n 互素,若此模逆元存在,在模数 n 下的除法可以用和对应模逆元的乘法来达成,此概念和实数除法的概念相同

非平凡因子:$x$可以整除$N$且$1< x <N$,则称x为N的非平凡因子

RSA加密过程

首先选取两个大质数$m$,$n$
计算 $N = m n$ ,计算$\phi(N) = (m - 1)(n - 1)$,在 1 和 $\phi(N)$ 之间选择一个 e ,要求 e 与 $\phi(N)$ 互质,一般情况选择65537,然后计算 $ed = 1mod \phi(N)$ ,即计算 e 对于 N 的模逆元 $e^{-1}$ ,计算出 $d$ , $(e,N)$作为公钥 $(d,N)$作为私钥

加密时,将密文按照约定的格式化为m,则有:

$m^e = c \ mod \ N$,加密
$c^d = m \ mod \ N$,解密

RSA证明

证明RSA的正确性即证明m^ed = m(mod N)的正确性,由于ed = 1(mod phi(N)),ed = kphi(N) + 1
即证明m ^ (k \
phi(N) + 1) = m(mod N)成立
当m与N互质的时候,即m * m^(k * phi(N)) = m (mod N),由于 m 与 N 互素,则对于m (mod N)的运算可以直接对于m运算,即有如下等式成立,m ^ (k * phi(N)) = 1(mod N),即欧拉定理,故正确性成立

当m与N不为互质的时候,那么m一定是p或者q的倍数,我们可以假设m = x * p,由于q为素数,则有m^phi(q) = 1 (mod q)
m^(k * phi(N)) = m ^(k(p-1)(q-1)) = (m^phi(q))^(k(p-1)) = 1 (mod q)

m^(k*phi(N)) = 1 + uq,两边同乘m得,m^(kphi(N) + 1) = m + uqm,又因为m = xp,所以有
m^(k
phi(N) + 1) = m + uqxp = m + uxN,即rsa成立

RSA攻击方法

首先来说一下rsa的破解难度,在已知公钥和密文的时候,我们已知的条件有,c,N,e,若要解密c的话,则需要
c^d = m(mod N),需要计算d,而d的计算需要e*d = 1(mod phi(N)),我们需要phi(N),而phi(N) = (p - 1)(q - 1),即需要我们分解大数N才能进行计算,在1024bit的长度下,对于当前的算力来说是不可能破解的,所以rsa的安全性就是利用了加密与解密之间的运算量不对等关系

下面总结一些常见的攻击方法

d泄露

私钥泄露,很明显我们可以直接用c^d = m(mod N)对密文进行解密,一般情况下,有了d我们还可以计算出p和q,对于ed = 1(mod phi(N)),当我们得知d的时候,一定会有:
ed - 1 = kphi(N)成立,

原文作者:MozhuCY

原文链接:http://mozhucy.com/2019/07/30/rsa/

发表日期:July 30th 2019, 12:00:00 am

更新日期:August 12th 2019, 12:31:01 pm

版权声明:本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 前置数论知识
    1. 1.1. 欧拉函数
      1. 1.1.1. 通式
      2. 1.1.2. 性质及证明
    2. 1.2. 欧拉定理
  2. 2. RSA加密过程
  3. 3. RSA证明
  4. 4. RSA攻击方法
    1. 4.1. d泄露