RSA加密过程推导(QwQ)

发布于 2023-01-12  753 次阅读


公钥密码体制

•私钥密码体制存在秘钥量大:$n$个用户之间互相通信一共需要$C_n^2=\frac{n(n-1)}{2}$个 密钥。

•公钥密码体制加密密钥$P_k$公开,但解密密钥$S_k$ 是保密的。

image-20230112120622648

来看一道崭新的算法题(年龄小于24小时)

image-20230112120639557image-20230112120646846

对于两个素数$p$和$q$,可以瞬间完成$n=p*q$的运算。

但是如果想从$n$分解出$p$和$q$,则需要进行因式分解

常见的因子分解的方法有$O(\sqrt{n})$的枚举因子方法,

还有预处理素数后优化到最差$O(\frac{n}{3})$的方法

也有不保证$100\%$准确的Pallord算法$O(\sqrt[4]{n})$

举个通俗的例子,如果对于一个程序来说,输入规模 $n=10^9$的话:

$O(1)$的算法大约只用1次运算,普通电脑$ 10^{-9}$ 秒就能算完。

$O(logn)$大约会用30次计算(log的底数是2),普通电脑 $10^{-8}$秒算完。

$O(n)$大约就是 $10^9$次计算,普通电脑需要一秒左右。

$O(n^2) $大约是$ 10^{18}$次计算,普通电脑大概要30年。

$O(n!)$的话,人类所有电脑加在一起,等太阳炸了都算不完。

但是如果二进制下的n大于2048位

计算机是目前来说是基本无解的QwQ

因此就可以基于这个性质来设计密码

RSA加密原理

如何利用这个特点呢?!!!

请注意!现在神奇的事情发生了!对于一个与n互质的数a:

因为 $a^{φ(n)} ≡1 (mod n)$

所以 $a^{kφ(n)} ≡1 (mod n)$

所以 $a^{(kφ(n)+1)}≡a (mod n)$

不妨吧$kφ(n)+1$拆成两个数$e$和$d$的乘积,则可以表示为,此时有$ed=kφ(n)+1$

所以 $a^{ed}≡a (mod n)$

所以,若$ c≡a^e (mod n)$, 则$c^d≡a^{ed}≡a(mod n)$

(1)选定两个超大素数p和q。

在此需要用到大素数生成方法,方法较多。

以素数分布平均间距可逼近为$π(x)=\frac{x}{(t(x))}=\frac{x}{(ln⁡(x)-1)}$的结论来考虑,可以先生成一个随机大数,然后从其开始可以遍历连续的一部分奇数,复杂度并不大,最差的搜索长度就是$π(x)$ 。

然后通过快速判定某个数是不是素数来决定搜索的跳出

(1b)$Fermat $素性测试

我们可以根据 费马小定理 得出一种检验素数的思路:

基本思想是不断地选取在$[2,n-1]$中的基$a$,并检验是否每次都有$a^{n-1}≡1(mod n) $

那么经过$t$轮测试,$p$不是素数的概率为$\frac{1}{4^t}$

我习惯用$2,3,5,7,11,13,17,19$这几个数进行判断

在信息学范围内出错率为$0\%$(不带高精)

(2)计算$n=p∗q,ϕ(n)=(p-1)(q-1)$

我们假设上一步选定的$p=11$和$q=13$,则$n=143$

根据欧拉函数的定义,可以知道素数m的因数只有$1$和$m$,所以小于等于$m$的数,除了$m$都和他互质

即$ϕ(p)=(p-1)$ 其中$p$为素数。

根据此可知,$n=pq$中,质因子除了有$1q,2q,3q…(p-1),pq$和$1p,2p,3p…(q-1)p,pq$共有$p+q-1$个,

因此n以内和n互质的数有$pq-(p+q-1)=pq-p-q+1=(p-1)(q-1)$个

则$ϕ(n)=120$

(4)此时密钥生成完毕

根据$ a^{ed}≡a (mod n)$

$ c≡a^{e} (mod n)$

$ c^d≡a^{ed}≡a(mod n)$

可知加密方需要$e$和$n$两个数据,解密方需要$d$和$n$两个数据

由此公钥即为${e,n}$,私钥为${d,n}$


绝对不是恋爱脑!