RSA加密原理&密码学&HASH( 二 ) _加密

小提示: 关于定理 , 不需要我们去证明它 , 只用记住就好.
3.1 费马小定理
费马小定理就是在欧拉定理的基础上 , 而当 n 为质数时 (φ(n)结果就是n-1 .)
那么 :
如果两个正整数 m 和 n 互质 , 且 n 是质数，那么 m 的 n-1 次方减去 1，可以被 n 整除。

文章插图

4. 公式转换

首先根据欧拉定理

文章插图

由于 1 的 k 次方恒等于 1 , 那么

文章插图

由于 1*m ≡ m , 那么

文章插图

在接下来第四部之前 , 我们要先提一个概念 : 模反元素

如果两个正整数 e 和 x 互质，那么一定可以找到整数 d，使得 ed-1 被 x 整除。那么 d 就是 e 对于 x 的模反元素 .
那么换算成公式就是:

文章插图

转换一下写法

文章插图

注意比较第五步和第三步中红框部分. 也就是说当 x 等于 Φ(n) 时 :

文章插图

( 其中 d 是 e 相对于 φ(n) 的模反元素 , 因为 x = Φ(n) 嘛)
注意 : 公式推导第一步时我们欧拉定理的前提是 m 和 n 互质 , 但是由于模反元素的关系 , 其实只要满足 m < n 上述结果依然成立.

文章插图

重头戏来了 , 用实际场景来看下迪菲赫尔曼密钥交换过程

文章插图

原理:

文章插图

结合我们刚刚第五步之后得出的

文章插图

因此:

文章插图

( 其中 d 是 e 相对于 φ(n) 的模反元素 , 因为 x = Φ(n) , 那么同样 , e 和 φ(n) 是互质关系 )
大家可以自己去实验一下 . 例如: m = 3 , n = 15 , φ(n) = 8 , e = 3 , d = 11 .

文章插图

到了这里 , 我们就得到了RSA算法的原理 . 那么我们对应起来介绍一下
RSA算法的原理

文章插图

1、 n 会非常大，长度一般为 1024 个二进制位。（目前人类已经分解的最大整数，232 个十进制位，768 个二进制位）
2、由于需要求出 φ(n)，所以根据欧函数特点，最简单的方式 n 由两个质数相乘得到: 质数： p1 、 p2 . 那么 Φ(n) = (p1 -1) * (p2 - 1)
3、最终由 φ(n) 得到 e 和 d。总共生成 6 个数字： p1、p2、n、φ(n)、e、d
其中 n 和 e 组成公钥 .
n 和 d 组成私钥 .
m 为明文 .
c 为密文 .

( 除了公钥用到了 n 和 e 其余的 4 个数字是不公开的。)
HASH 算法
HASH 介绍
Hash，一般翻译做 “ 散列 ”，也有直接音译为“ 哈希 ”的，就是把任意长度的输入通过散列算法变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定唯一的输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数
HASH 特点