zhjx922 De Blog

加密算法之非对称加密

上篇文章介绍了对称加密的原理,但是它的最大问题就是加密和解密的密钥是相同的,并且不能保证密钥能安全的送到双方手里,即使安全的送到双方手里,免不了内部会有”卧底”的存在

非对称加密

既然有对称加密,那么自然会联想到非对称加密。非对称加密的核心在于加密和解密使用的是不同的密钥,如何做到使用不同的密钥呢?
比如我有一个只能用钥匙打开的存钱罐,平时大家只能把零钱放到储钱罐中,但是只有我才有取钱的钥匙。放到储钱罐的硬币可以看成加密后的内容,而只有用钥匙才能将”加密”后的硬币取出来。
这样我们就可以把用来加密的密钥(公钥)给了任何人,我们只要自己保存好解密的密钥(私钥)就可以安全的保护我们的数据。
非对称算法有很多:RSA、Elgamal、背包算法、Rabin、D-H、ECC等,下面我们来简单介绍一下RSA算法。

RSA算法

RSA公钥加密算法是1977年由罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)一起提出的。1987年首次公布,当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的(啥时候以我名字命名一个呢)。
RSA是目前最有影响力的公钥加密算法,它能够抵抗到目前为止已知的绝大多数密码攻击,已被ISO推荐为公钥数据加密标准。

RSA加密&&RSA解密公式

1
2
3
4
//注意:明文为数字,实际计算过程我们可以通过ASCII码转换
密文 = (明文 ^ E) % N; //其中的E和N就是我们的公钥
明文 = (密文 ^ D) % N; //其中的D和N就是我们的私钥

计算公钥(E)、私钥(D)和数字(N)

公钥和私钥不是随便弄几个数字就可以的,是经过严格的数学公式计算出来的。

1、随机准备两个质数P和Q,计算乘积得到N

1
N = P * Q;

2、计算L

1
L = (P - 1) * (Q - 1); //图解密码技术中说需要计算乘积之后的最小公倍数,但是经过代码测试并不准确,哪位大侠了解麻烦留言告知一下~

3、计算E(公钥),用来给加密方使用

1
2
3
//E需要同时满足下面两个条件
1. 1 < E < L
2. E和L的最大公约数为一(欧几里得算法,这些恶魔啊,E和L必须互质,这样才能保证一定可以计算出私钥D)

4、计算D(私钥),用来给解密方使用

1
2
//D需要满足下面公式
(E * D) % L = 1; //想要保证结果为1,E和L必须互质!!!

上面就是整个计算过程,为了保证数据的安全现实中,P和Q会选用特别大的数(1024比特或者更大)

RSA的加密和解密

上面已经提到过加密和解密的方法,我们用具体的数字实践一下,加深理解吧。

1、求N(P*Q)

1
2
假设:P = 7、Q = 11(均为质数)
那么:N = P * Q = 7 * 11 = 77

2、求L ((P - 1) * (Q - 1))

1
L = (P - 1) * (Q - 1) = 6 * 10 = 60

3、求E

1
2
1 < E < 60
E和L的最大公约数为一,我们假设E=23

4、计算D ((E * D) % L = 1)

1
2
(23 * D) % 60 = 1;
D = 47;

那么我就得到了公钥(E=23,N=77),私钥(D=47,N=77)

加密&&解密

我们假设需要加密数字:12
公式:密文 = (明文 ^ E) % N;
12 ^ 23 % 77 = 6624737266949237011120128 % 77 = 45;
这个45就是我们加密后的密文

解密
公式:明文 = (密文 ^ D) % N;
45 ^ 47 % 77 = 502328880013965819626664594350710696732674427522624682751484215259552001953125 % 77 = 12;
得出原文:12

PHP示例

下面是我用PHP实现的加密&解密示例,供大家参考(因为指数运算的结果集会很大,我们必须使用PHP中提供的BC Math系列函数计算)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
/**
* 冒牌RSA算法
* @author zhjx922
*/
/**
* 判断数字是否为质数
* @param $num
* @return bool
*/
function isPrimeNumber($num) {
$k = 0;//定义次数变量
for ($i = 1; $i <= $num; $i++) {
if (bcmod($num, $i) == 0) {
$k++;//如果取模等于0,次数k自加
}
}
if ($k == 2) {
return true;
}
return false;
}
//求最小公倍数
function minMultiple($a, $b)
{
if($b==0) //一定要考虑除数不能为零
{
return $b;
} else {
$m = bccomp($a, $b) == 1 ? $a : $b;
$n = bccomp($b, $a) == 1 ? $b : $a;
for($i=2; ; $i++)
{
$mul = bcmul($m, $i);
if(bcmod($mul, $n) == 0)
{
return $mul;
}
}
}
return bcmul($a, $b);
}
//求最大公约数
function maxDivisor($a,$b)
{
$n = bccomp($a, $b) == 1 ? $b : $a;
for($i = $n; $i>1; $i--)
{
if(bcmod($a, $i) == 0 && bcmod($b, $i) == 0)
{
return $i; //此处如果用echo $i;则输出结果为432;故应区分echo、return的区别
}
}
return 1;
}
do{
//随机一个质数P
$p = mt_rand(101, 197);
} while(!isPrimeNumber($p));
do{
//随机一个质数Q
$q = mt_rand(101, 197);
} while(!isPrimeNumber($q));
$n = bcmul($p, $q);
//$l = minMultiple($p - 1, $q - 1); //经测试不可用
$l = bcmul($p - 1, $q - 1);
do {
$e = mt_rand(2, $l - 1);
}while(maxDivisor($e, $l) != 1);
$d = 1;
while(bcmod(bcmul($e,++$d), $l) != 1) {
}
echo 'p:' . $p . PHP_EOL;
echo 'q:' . $q . PHP_EOL;
echo 'n:' . $n . PHP_EOL;
echo 'l:' . $l . PHP_EOL;
echo 'e:' . $e . PHP_EOL;
echo 'd:' . $d . PHP_EOL;
echo "公钥:e={$e},n={$n}" . PHP_EOL;
echo "私钥:d={$d},n={$n}" . PHP_EOL;
//加密
function encode($e, $n, $string) {
$enString = '';
$len = strlen($string);
for($i = 0; $i < $len; $i++) {
$pow = bcpow(ord($string{$i}), $e);
$mod = bcmod($pow, $n);
$enString .= pack('L', $mod);
}
return $enString;
}
//解密
function decode($d, $n, $string) {
$deString = '';
$string = unpack('L*', $string);
$len = count($string);
for($i = 1; $i <= $len; $i++) {
$pow = bcpow($string[$i], $d);
$mod = bcmod($pow, $n);
$deString .= chr($mod);
}
return $deString;
}
$startTime = microtime(true);
$string = '欢迎关注"假装是个程序员"公众号';
echo "原文:" . $string . PHP_EOL;
$encodeString = encode($e, $n, $string);
echo "密文:" . $encodeString . PHP_EOL;
$decodeString = decode($d, $n, $encodeString);
echo "解密后:" . $decodeString . PHP_EOL;
$endTime = microtime(true);
echo "Total:" . ($endTime - $startTime) . 's.' . PHP_EOL;

没有绝对安全的加密方式

没有什么加密方式能一直保持绝对的安全,尤其常用的MD5,如果你的数据库中密码还是使用MD5的哈希结果不要笑话人家直接用明文存密码的人,五十步笑百步而已。。。
最近谷歌宣布破解了SHA-1,随着计算能力的提高,SHA-256,RSA等等也是迟早的事儿。。

zhjx922 wechat
欢迎关注二维码,一起交流学习!