RSA加密数学原理
Table of Contents
1 引言
RSA加密算法,即是目前最有影响力的咬钥加密算法, 他能够抵抗到目前为止已知的绝大多数密码攻击, 已被ISO推荐为公钥数据加密标准. 该算法基于一个十分简单的数论事实: 将两个大素数乘十分容易, 但相要对乘积进行因式分解却极其困难, 因此可以将乘积公开作为加密密钥. (选自: 百度百科)
2 RSA加密解密过程
2.1 加密
首先给出下面的公式: $$C=M^e mod n$$ 上式中M为需要加密的信息, (n=pq), p和q分别为100~200位的大素数, e与$(p-1)(q-1)$互为素数. 实际应用中, Bob将公用密钥(e, n)发送给Alice, 然后Alice利用该公用密钥根据 (C=M^{e} mod n) 进行加密, 然后将C发送给Bob
2.2 解密
Bob收到了Alice发送过来的C后, 接着就需要利用自己手上的私有密钥对加密信息C进行解密了, 他手上的私有密码是什么呢? 即d为e模(p-1)(q-1)的逆, 用算式表示为(de equiv 1pmod {(p-1)(q-1)}). 用私有密钥具体处理过程如下:
- (C^{e}pmod n = M^{ed}pmod n)
- 由于$de ≡ 1pmod {(p-1)(q-1)}$得(de=1+k(p-1)(q-1))
- 从费马小定理, 以及M与(p和q)互质成立的事件为大概率事件 – 因为RSA一般用于短信息加密, 当加密的信息庞大的时候, 速度会明显变慢, 同时p和q均是大素数 – 两个条件推得:
费马小定理:如果p为素数, a是不能被p整除的整数, 则 (a^{p-1} equiv 1pmod p)
- 于是:
- 由中国剩余定理得:
中国剩余定理: 令m1, m2, …, mn为两两互素的正整数, 则预余方程组 $$xequiv a_{1}pmod m_{1}$$ $$xequiv a_{2}pmod m_{2}$$ $$quad vdots quad$$ $$xequiv a_{n}pmod m_{n}$$ 即有一个解x, 使(0 le x le m), 且所有其他的解均与此解模m同余. (m=m_{1}m_{2}dotsi m_{n})
3 收尾
由于当解密密钥和加密密钥相同的时候, RSA算法比其他的对称加密算法而言需要更多的计算时间, RSA通常不被用来完整信息的加密.