密码学介绍及RSA算法概述

说来惭愧,我大学其实是信息安全专业的,但是啥都没学会,所以自学了web开始当一个搬运工。信息安全专业最重要的一门课就是密码学,下面我凭着残留的记忆还有没扔的大学教材和请教读研大学同学后总结的点,给大家介绍一下这门神奇的学科。

密码学介绍

密码编码学有两个分支,密码分析学和密码使用学,
分析学指破译一种加密方式的技巧,一个加密算法是否可靠都需要分析来证明。

使用学又分为三个分支:对称算法,非对称算法,密码协议。

对称算法是双方共享一个密钥,使用同样的方法进行加密和解密,现代的比如AES,DES,3DES等,古代的斯巴达密码棒和凯撒加密。

非对称算法用户会持有一个公私钥对儿。A想要给B发送信息,就需要A用B的公钥加密,B收到后使用私钥解密。常见的又RSA和椭圆曲线算法。
密码协议主要内容是如何搭配算法实现最优方案,对称与非对称有各自都优缺点,所以要一起使用才最好,最典型的例子就是传输层安全(TLS)方案,所有web浏览器都已使用这个方案,访问https的网站,我们发送信息时需要用服务器给的公钥进行加密,中间还涉及到CA,数字签名等等。

白话RSA算法


(这三个人目前还在世,MD5也是他们搞得)
RSA的出现并不是为了取代对称加密算法,因为RSA的执行需要很多计算,这也是为什么https的网站访问比较慢的原因,真正用来加密大量数据的还是对称加密算法,RSA为对称加密的公钥保驾护航。
RSA的底层原理就是整数的因式分解,两个大素数在乘积上很容易计算,但是对乘积的因式分解确实非常困难的,几乎是不可能完成的。

1.生成密钥

第一小步,bob选择两个质数(除了1和它本身以外不再有其他因数)
p = 5, q = 11
n = p*q = 55
计算p * q的欧拉函数 U(55) = (5-1)(11-1) = 40 (欧拉函数指的是在小于N的数环中于N互质的数字的个数 比如欧拉8 = 4 (1,3,4,7), 欧拉6 = 2 (1,5) )
欧拉函数最终可以推算出公式

点击查看推导过程

// 根据上面的公式js实现的欧拉函数
function isPrime(i) {
        for (var a = 2; a < i; a++) {
            if (i % a == 0) {
                return false;
            }
        }
        return true;
    }
    function getPrimes(n) {
        var current = n;
        for (var b = 2; b <= n; b++) {
            if (isPrime(b) && (n % b) == 0) {
                current *= (1 - 1 / b);
            }
        }
        return Math.round(current);
    }
    getPrimes(55)  // 40

第二小步,bob从1到40选择一个数字e=3

计算e对U(55)的模反逆元d( 费马小定理 ed ≡ 1 (mod φ(n)),自行搜索 )
等价于 3d – 1 = k40 —> 3x – 40y = 1 对这个二元一次方程求解。
使用 带入消元发 计算xy过程如下
40 = 3 * 13 + 1
然后把它们改写成“余数等于”的形式
1 = 40 – 3 * 13
然后一步一步替换,提取公因式得出 x=-13 y=-1 所以d=-13
在整数环{0,40}内-13对应27,所以私钥d为27。

计算出公钥为(n,e) = (55,3),私钥为(n,d) = (55, 27)
为什么说对称加密无法破解,当攻击者拿到公钥n,e,是无法推出私钥d的,因为根据公式ed ≡ 1 (mod φ(n)),算出d必须要知道n的欧拉函数是多少,φ(n)=(p-1)(q-1),如果能将n进行因数分解,就能算出d,可是大整数的因式分解是非常困难的,只有暴力破解。

2.加密与解密

加密公式为 m^e ≡ c (mod n)
解密公式为 c^d ≡ m (mod n)
已知明文m = 14,公钥(55,3)
14^3 = c(mod55)
算出 c = 49
解密
(49^27)mod55 = 14 解密成功
需要注意的一点是浏览器里计算Math.pow(49,27)%55 = 36。49的27次方已经超出了大多数语言的最大安全数值,所以我们在计算的时候需要自己想办法提公因式,结合律交换律之类的。
为了算出正确的14我自己实现了一个方法

Math.bigM = (s,n,m) => {
    let mi_gap = 1
    while(Math.pow(s,mi_gap)<Number.MAX_SAFE_INTEGER){
        mi_gap += 1
    }
    mi_gap -= 1
    let mi_gap_mi = Math.floor(n/mi_gap)
    let mi_gap_mo = n%mi_gap
    return Math.pow(Math.pow(s,mi_gap)%m, mi_gap_mi)*(Math.pow(s,mi_gap_mo)%m)%m
}