0%

加密原理和常见算法

散列算法

散列算法不属于加密算法,目前经常使用的有两种:

1. MD5

对任意长度的数据计算生成128位固定长度的MD5值,主要的特定:

  • 生成的MD5值一定是128位,不管输入数据多大

  • 原始数据只要有修改,MD5值就会发生很大的改变

  • 容易计算,也就是算法不会很耗时

  • 很少会发生碰撞

MD5的算法过程主要为:填充 –> 分组进行位运算 –> 得到MD5值

具体的计算过程可以参考:https://zhuanlan.zhihu.com/p/37257569

2. SHA1

对于长度小于2^64位的数据计算生成160位固定长度的SHA1值,可以看到它与MD5的区别有:

  • 输入数据长度必须小于2^64位

  • 生成的信息摘要值为160位

因此相对于MD5,SHA的安全性更高,但运算速度大概会慢1/4。

SHA1的算法过程主要位:填充 –> 分组进行位运算 –> 得到SHA1值

总结

散列算法主要用于以下三中场景:

  • 防修改:比如服务端动态下发文件,需要对其进行完整性校验,保证文件没有被修改或者传输过程损坏。

  • 数字签名:如Apk安装时的签名校验,保证Apk文件没有被修改过。

  • 防明文存储:密码存储(还要加盐),不直接存储明文,这也就是为什么密码只能重置不能找回的原因。

散列算法的破解,有三种方法:

  • 暴力枚举:这种计算量巨大,不太靠谱。

  • 字典法:字典里存储常见的明文密文键值对,比如常见密码等,空间占用会比较大。

  • 彩虹表:对字典法进行改进,通过运算减少一部分的空间占用,也就是空间和时间相结合实现破解,具体破解过程可以参考:https://www.jianshu.com/p/732d9d960411

对称加密

加密和解密都是用同一个密钥,常见的DES和AES都是对称加密算法,对称加密的优点就是加解密速度快,缺点就是安全性不高,密钥需要给到加密方,容易泄露。

非对称加密

非对称加密采用公钥加密,私钥解密,加密方无需拿到私钥,安全性高,但加密速度慢,适用于关键环节的加密,比如https建立连接的握手过程等。

原理

核心就是:公钥大家都知道,但还是很难破解计算出私钥,因为大素数的分解很难。

具体地,如下:

选定两个质数P、Q,计算N = P * Q,欧拉函数w(N) = (P - 1) * (Q - 1)
然后就可以得到公钥和私钥了,假设初始公钥为G,则公钥的取值必须满足1 < G < w(N),而且还必须跟w(N)互质,最终G和N组成真正的公钥,我们表示为(G, N),而私钥必须满足G * S % w(N) = 1,其中的S就是初始私钥,最终S和N组成真正的私钥,我们表示为(S, N)。

加密过程:M * G mod N = C,其中M是明文,C是密文

解密过程:C * S mod N = M,可以看到通过密钥就能够得到明文

另外,公钥和私钥的地位是等价的,也就是可以交换,G保存起来当私钥,把S发布出去当公钥,原理上可行,但实际上G和S的选定会有一定标准,使得G更适合做公钥,S适合做私钥,因此实际上一般不能交换使用。

应用

非对称加密可用于数据加密,也可用于签名校验:

数据加密:公钥加密,私钥解密。

签名校验:私钥加密,公钥解密,验证明文是否对应得上,是的话就校验通过。

具体到实现场景,HTTPS建立连接握手过程,apk安装签名校验等。

常见算法

RSA:原理就是上面所描述的过程,密钥越长越难破解,可以采用1024位或者2048位,注意RSA本身也是会有中间人攻击的问题,实际使用中采用数字签名+RSA实现密钥交换。

ECC:跟椭圆曲线方程有关,具体原理和细节后面研究。

其它

DH密钥交换协议

用于在不安全的信道上交换密钥,其原理就是离散对数很难被计算出来,具体的算法如下:

  1. 取素数p和整数g,这里g一般为2或5,而素数要很大
  2. A端生成随机数Xa,计算Ya=g^Xa mod p,把Ya传给B端
  3. B端生成随机数Xb,计算Yb=g^Xb mod p,把Yb传给A端
  4. A端拿到Yb后,可以计算K=Yb^Xa mod p
  5. B端拿到Ya后,可以计算K=Ya^Xb mod p

可以看到,最终A和B都能计算的到密钥K,而对于其它人,它们是很难计算出来的,因为它们不知道Xa或者Xb,而在知道p,g,Ya,Yb的情况下,计算离散对数Xa或者Xb是很困难的。

由于DH算法并没有进行身份验证,因此很容易出现中间人攻击问题,解决该问题的方法就是引入签名验证。

SSH原理

解决中间人攻击的方法就是实现对公钥进行公证,HTTPS中使用签名证书进行公证,这是因为证书是权威机构CA颁发的,而SSH的公钥都是自己生成的,接收方无法确定公钥有无问题,SSH有两种认证方式:

  • 输入用户名和密码

    1. 客户端请求服务端,服务端下发公钥给客户端。

    2. 客户端会显示这个公钥指纹给用户确认是否真的来着服务端,输入yes后,用这个公钥加密密码,发生给服务端。

    3. 服务端接收到后用私钥解密,正确就登录成功。

      可以看到,这种方式每次登录都要输入密码,使用起来不方便。另外,显示公钥指纹是为了避免中间人攻击。

  • Public Key认证

    1. 生成公钥-私钥对,然后客户端保存私钥,服务端保存公钥。

    2. 客户端请求服务端,服务端生成随机串x,使用公钥加密后得到R(x)下发给客户端。

    3. 客户端用私钥解密R(x)得到x,然后用MD5算法对x和session key生成摘要D,发送给服务端。

    4. 服务端接收到摘要D后,同样用MD5算法对x和session key生成摘要D’,如果D和D’相同,就说明登录成功。

      这里涉及到一个session key,这个是在认证之前客户端和服务端协商好的一个密钥,用于后面通信时做为对称加密的密码,SSH2协商采用DH算法,在认证阶段客户端和服务端都已经拥有了这个session key。

Base64

这个不是真正的加密算法,只是按照一定的编码规则,对字节流进行编码,编码后的结果只包含英文数字和等号,编码原理为:

依次取字节流的6个bit,得到对应的数值,然后查找Base64索引表找到对应的字符,这样直到字节流结束为止,另外如果原始数据字节数不是3的倍数,会在最后加上一个或两个等号。

从上面的算法可以知道,Base64编码后的结果大小会是原始数据大小的4/3。

举个例子,比如字符串“ABCD”,对应的二进制位:01000001010000100100001101000100,然后按三个字节一组划分,010000010100001001000011 01000100,对于第一组,6bit组成一个int数组,依次为16,20,9,3,查Base64表对应为Q,U,J,D,接着看第二组,第一个6bit为17,也就是R,第二个6bit其实只剩两位,因此补4个零,最终还是0,对应A,而这组总共才8位一个字节,因此后面再补两个字节,也就是两个=,最终整个字符串的编码为:QUJDRA==,通过网上现成的编码工具验证正确。

参考资料

SSH是如何防御重放攻击的?