密码学-非对称加密计算方法的简单举例

大家好，欢迎来到IT知识分享网。

假如A是司令部 B是侦查员

B需要传递侦察消息到A

传递方式可能是电报，信件等方式

明文消息传递

传递过程: A <- 传递 <- B

传递内容:123 <- 123 <- 123

消息截获直接获得内容

对称加密消息传递

传递过程: A解密 <- 传递 <- 加密B

传递内容: 123 <- 456 <- 123

加密规则 所有数字加一

这个加密规则要告诉B，B按照这个规则加密，A才能解密知晓内容

这里就存在问题

B需要在出发前就知道这个规则，因为这个规则如果通过信件等方式传递给B也会有泄露的风险。

并且这个规则一旦被破译，更换很难更换规则

非对称加密消息传递

A生成一对规则，这一对规则用其中一个加密，则另一个可以解密(下面会有计算例子)。

这对规则留给自己的叫私钥，发个对方的叫公钥。

A来生成一对公钥私钥 B可以获得公钥(其他人也可以)

此时B可以用公钥加密一个信息，此时只有A能解密这个信息

B传送到A的信息是安全的。

如果B也想得到A的加密信息，那么B也可以生成一对公钥私钥，并把公钥发送给A，A可以用公钥加密信息，B用私钥解密。

为什么A不是直接用私钥加密，发送给B，因为公钥是公开的，或者说公钥是可能被截获的，A如果用私钥加密，任何截获公钥的人都能解密。

并且A的私钥除了解密也有其他用处，比如A公开一个声明，B如何知道这个公开的声明有没有被篡改过，这个声明可以同时附上一个用私钥加密后的内容，B来解密。如果解密的内容和声明的内容一致，则说明A的声明没有被窜改。

具体算法

公钥加密 私钥解密

私钥签名 公钥验证(签名是 原文件先哈希运算计算出MD5，私钥再对MD5进行加密)

产生一对公钥私钥

1. 选择一对不同的、足够大的素数p，q，同时对p, q严加保密，不能让其他任何人知道。

2. 计算 n = p * q

3. 计算 f(n) = (p-1)(q-1)

4. 找一个与 f(n) 互质的数 e，且 1<e<f(n) 。

5. 计算 d，使得 de ≡ 1 mod f(n)。这个公式也可以表达为d ≡ e^-1 mod f(n)，找到余数为1

6. 公钥 KU=(e,n)，私钥 KR=(d,n)。

示例：

1. 令p=3，q=11，

2. n=p×q=3×11=33

3. f(n)=(p-1)(q-1)=2×10=20

4. 取e=3（3与20互质并且在1<e<f(n)范围内）

5. e×d≡1 mod f(n)，即 3×d ≡ 1 mod 20。取d=7（余数为1）

6. 加密密钥（公钥）为：KU =(e,n)=(3,33)，解密密钥（私钥）为：KR =(d,n)=(7,33)。

加密解密

假设加密内容是11，05，25（自定义的对用26个字母key）

加密后得到 11 26 16

解密

签名

签名和上面的算法一样

原文件内容可能很多，可以转换成MD5后，加密MD5的值

验证端也是先将原文件内容转换成MD5

再解密接收到的加密后的MD5进行比对

什么是“素数”？

素数也称为“质数”，是指除了能表示为它自己和1的乘积以外，不能表示为任何其它两个整数的乘积的数字。

例如，15＝3＊5，所以15不是素数；又如，12＝6＊2＝4＊3，所以12也不是素数。又例如，13除了等于13＊1以外，不能表示为其它任何两个整数的乘积，所以13是一个素数。

什么是“互质数”（或“互素数”）？

小学数学教材对互质数是这样定义的：“公约数只有1的两个数，叫做互质数。” 这里所说的“两个数”是指自然数。

判别方法主要有以下几种（不限于此）：

– 两个质数一定是互质数。例如，2与7、13与19。

– 一个质数如果不能整除另一个合数，这两个数为互质数。例如，3与10、5与 26。

– 1不是质数也不是合数，它和任何一个自然数在一起都是互质数。如1和9908。

– 相邻的两个自然数是互质数。如 15与 16。

– 相邻的两个奇数是互质数。如 49与 51。

– 大数是质数的两个数是互质数。如97与88。

– 小数是质数，大数不是小数的倍数的两个数是互质数。如 7和 16。

– 两个数都是合数（二数差又较大），小数所有的质因数，都不是大数的约数，这两个数是互质数。如357与715，357=3×7×17，而3、7和17都不是715的约数，这两个数为互质数。等等。