公开密钥加密是指什么

问题描述

精选答案

参考：

密码学之RSA加密

RSA加密：非对称密钥，公开密钥算法RSA加密利用了单向函数正向求解很简单，反向求解很复杂的特性。具体是利用了：

1. 对两个质数相乘容易，而将其合数分解很难的这个特点进行的加密算法。 n=p1*p2，已知p1、p2求n简单，已知n求p1、p2困难。

2. (m^e) mod n=c，已知m、e、n求c简单，已知e、n、c求m很难。RSA加密，实现了公开密钥，就是A可以给所有人发送锁，其他人把要加密的信息用这把锁加密后发送给A，A用自己的钥匙开锁就可以获得加密的信息了。反过来，A要发送加密信息给B，只要知道B的锁就可以了，而这个锁是公开的。公开密钥n、e的生成：随机选取两个质数p1、p2，n=p1*p2，再随机选取一个整数e，e与φ(n)互质。加密过程：(m^e) mod n=c，其中m为原信息，c为加密信息，n、e为公开密钥。解密过程：(c^d) mod n=m，其中d为解密密钥。解密密钥d的求解：(c^d) mod n=(((m^e) mod n)^d) mod n=((m^e)^d) mod n=(m^ed) mod n=m ①根据费马定理(m^φ(n)) mod n≡1，又1^k≡1，所以(m^k*φ(n)) mod n≡1，两边同乘以m得m*((m^k*φ(n)) mod n)≡1*m，化简(m^(k*φ(n)+1)) mod n≡m ②由①、②得ed=(k*φ(n)+1)，解得d=(k*φ(n)+1)/e。费马定理：若p是素数，a与p互素，则a^(p-1）≡1 （mod p）过程如下：A：有一个公钥n、e。例如：3127、3。B：有一个信息m。例如：89。C：偷听者A：第一步：随机找两个质数p1、p2，一个奇数e。例如：53、59、3。第二步：计算n=p1*p2得到n，计算欧拉函数φ(n)=(p1-1)*(p2-1)得到φ(n)，计算钥匙d=(k*φ(n)+1)/e得到d。例如：53*59=3127、(53-1)*(59-1)=3016、(k*φ(n)+1)/e=(2*3016+1)/3=2011。第三步：发送n、e给大家知道/、e就是公钥也做锁，d就是n、e的钥匙。C：获得n、eB：第一步：获得n、e第二步：加密信息m，(m^e) mod n=c，获得加密信息c。例如：(89^3) mod 3127=1394。第三步：发送c给AC：第一步：截获加密信息c第二步：破解信息c，此时C只有n、e、c，只有把n分解质因数才能破解，而此分解很困难特别是当n很大的时候。A：第一步：收到加密信息c第二步：解密信息c，(c^d) mod n=m，获得信息m。例如：(1394^2011) mod 3127=89。完成