RSA加密原理&密码学&HASH

密码学是研究编制密码和破译密码的技术科学。研究密码变化的客观规律，应用于编制密码以保守通信秘密的，称为编码学；应用于破译密码以获取通信情报的，称为破译学，总称密码学。

密码学的起源可追溯到2000年前。而当今的密码学是以数学为基础的。

密码学溯源

密码学的历史大致可以追溯到两千年前，相传古罗马名将凯撒大帝为了防止敌方截获情报，用密码传送情报。凯撒的做法很简单，就是对二十几个罗马字母建立一张对应表。这样，如果不知道密码本，即使截获一段信息也看不懂。

从凯撒大帝时代到上世纪70年代这段很长的时间里，密码学的发展非常的缓慢，因为设计者基本上靠经验。没有运用数学原理。

重要节点:

• 在 1976 年以前，所有的加密方法都是同一种模式：加密、解密使用同一种算法。在交互数据的时候，彼此通信的双方就必须将规则告诉对方，否则没法解密。那么加密和解密的规则（简称密钥），它保护就显得尤其重要。传递密钥就成为了最大的隐患。这种加密方式被成为 对称加密算法 （ symmetric encryption algorithm ）
• 1976 年，两位美国计算机学家 迪菲（ W.Diffie ）、赫尔曼（ M.Hellman ） 提出了一种崭新构思，可以在不直接传递密钥的情况下，完成密钥交换。这被称为“ 迪菲赫尔曼密钥交换 ”算法。开创了密码学研究的新方向.
• 1977 年三位麻省理工学院的数学家 罗纳德·李维斯特（ Ron Rivest ）、阿迪·萨莫尔（ Adi Shamir ）和伦纳德·阿德曼（ Leonard Adleman ）一起设计了一种算法，可以实现非对称加密。这个算法用他们三个人的名字命名，叫做 RSA 算法。

RSA 加密算法

RSA

上世纪 70 年代产生的一种加密算法。其加密方式比较特殊，需要两个密钥：公开密钥简称公钥（ publickey ）和私有密钥简称私钥（ privatekey ）。公钥加密，私钥解密；私钥加密，公钥解密。这个加密算法就是伟大的 RSA .

这种算法非常可靠，密钥越长，它就越难破解。根据已经披露的文献，目前被破解的最长 RSA 密钥是 768 个二进制位。也就是说，长度超过 768 位的密钥，还无法破解（至少没人公开宣布）。因此可以认为， 1024 位的 RSA 密钥基本安全， 2048 位的密钥极其安全。

( 当然 RSA 的缺陷也很容易想到 : 效率相对较低 , 字节长度限制等 . 因此实际应用中我们往往会结合对称性加密一起使用 , 关键内容使用 RSA )

RSA 数学原理

本小节内容了解即可

1. 离散对数问题

问: 三的多少次方模 17 等于 12 ?

• 显然 , 对于离散对数问题 , 其正向计算得到右边 12 很简单. 但是反向运算时 , 就无从下手. 只能穷举 .
• 而且当模数使用质数 17 时 , 结果固定在 1 ~ 17 之间. 而当 17 这个模数足够大时 , 就算知道采用的是这个算法 , 也知道 17 这个质数和答案 , 想要再计算出来上图中这个问号值 , 可以想象到其难度和计算量有多大 .

2. 欧拉函数 φ

欧拉函数 :

给定任意正整数 n , 在小于等于 n 的正整数中 , 能与 n 构成互质关系的正整数个数.
复制代码

计算这个值的方式叫做欧拉函数，使用： φ(n) 表示

• 例 :chestnut::

φ(8) 有 1,3,5,7 即是 φ(8) = 4

φ(7) 有 1,2,3,4,5,6 即是 φ(8) = 6

• 问 :

那么 φ(56) 是多少 ?

先别急着一个个去数 , 我们来看下 欧拉函数的特点 .

1. 当 n 是质数的时候， φ(n) = n-1
2. 当 n 可以分解成两个互质的整数之积，如 n = A*B 则 ： φ(A*B)=φ(A)* φ(B)

因此 :

如果 N 是两个质数 P1 和 P2 的乘积则 φ(N) = φ(P1) * φ(P2) = (P1-1)*(P2-1)

那么显然 φ(56) = φ(7) * φ(8) = 4 * 6 = 24

而 φ(63) = φ(7) * φ(9) = (7-1) * (9-1) = 48

3. 欧拉定理

如果两个正整数 m 和 n 互质，那么 m 的 φ(n) 次方减去 1 ，可以被 n 整除。

小提示: 关于定理 , 不需要我们去证明它 , 只用记住就好.

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 特点

• 算法是公开的
• 对相同数据运算,得到的结果是一样的
• 对不同数据运算,如 MD5 得到的结果默认是 128 位, 32 个字符（ 16 进制标识）
• 这玩意没法逆运算 ( 因此 HASH 并不用于加解密 )
• 信息摘要，信息“指纹”，是用来做数据识别的

HASH 主要用途

• 用户密码的加密
• 搜索引擎 (根据 hash 值来匹配搜索内容 等)
• 版权
• 数字签名
• 云盘文件审核 / 同文件识别
• ...等等

HASH 安全性探讨

由于相同数据 hash 得到的结果是一样的 . 那么市面上大量万亿级 hash 结果记录数据库的存在 , 这个不可逆的算法 也另类的变成了可解密的存在.

因此 , 我们使用时经常有以下几种操作 :

1. 加盐 (早期比较普遍的做法)
2. 嵌套 hash
3. 动态盐
4. Hmac (也可以说成动态盐的一种吧)
5. ... 等等

HMAC 加密方案

HMAC 使用一个密钥加密 , 并且做了两次散列 . 在实际开发中 , 密钥往往来自于服务器下发给客户端 并且可能是根据账户绑定的 . 并需要结合实际业务需求来设定注册与登录逻辑 (新设备授权等方式来决定服务器是否可以下发密钥给客户端)

看到这可能大家也跟我一样 都有个疑问 .

疑问

我不管你是如何 嵌套 加盐 HMAC 等什么方式去对密码做处理. 既然你登录是一个账号一个加密后的密码. 我抓包工具抓到就可以直接调用接口实现登录.

是啊 , 那不就 GG 了?

这就牵扯到接口安全的问题 , 其处理方法有很多种, 例如所有请求用 HTTPS , 并且使用对称性加密和非对称性加密结合等等方式对数据进行加密.

当然再安全的加密算法也有被破解的风险. 因此以下这种方式 , 大家可以理解参考一下 , 它能比较有效的解决抓包问题 :

解答

1. 注册时

• 同样使用 HMAC 的模式 , 也就是注册时 , 客户端把用户名传给服务器 .
• 服务器随机生成一个密钥返回给客户端 , 并绑定这个密钥到用户表改用户里.
• 客户端拿这个 key 将用户明文密码进行 HMAC 散列后发给服务器保存.

1. 登录时

• 登录时将用户 HMAC 之后的 hash 值 加上精确到分的时间戳 ( 时间统一为服务器下发时间 , 相信大家项目也都是使用了服务器时间. ) 然后进行散列.
• 服务器收到请求 , 分别验证当前时间和前一分钟时间加上之前存储的 HMAC 后的密码进行 hash . 两次有一次成功即为登录成功.

思考:

为什么以上方式可以有效防护到接口被抓包的情况 ?

1. 用户 HMAC 之后的 hash 值 只有在注册该账户时被传输过一次 .
2. 抓到接口中 时间戳加 HMAC 之后的 hash 值进行散列 很难猜出嵌套方式.
3. 使用抓到的接口中的源数据 ( 时间戳加 HMAC 之后的 hash 值 ) 每次都不一样 , 而且有效期只有最多 1 分 59 秒,最少一分钟 (有效期可灵活控制) 也就是说抓包人员抓到请求源数据后 , 必须在两分钟以内登录 , 否则就会失效.

HASH 题外话

可能有小伙伴碰到过上传云盘的文件被和谐的情况 , 并且改了名字或者后缀名重新传还是不行. 其实这就是 HASH 的一种运用场景 . 要 理解 HASH 是对二进制数据进行散列 . 那么改名字和后缀名其文件二进制是不会变化的 .

但是压缩是可以的 .

也就是说压缩是会改变内存大小 , 其内部二进制散列之后的结果也会变化 . 同样 base64也是会改变二进制数据的.