常见加密算法

GPT摘要

文章主要介绍了非可逆加密算法和可逆加密算法的原理和应用。在非可逆加密算法部分，介绍了MD5和SHA系列算法，以及它们在密码保存、文件完整性校验等方面的应用。同时提到了MAC和HMAC-SHA-256在确认消息完整性和身份认证中的作用。在可逆加密算法部分，介绍了凯撒密码和enigma机的原理，以及对称加密算法AES和非对称加密算法RSA的基本原理和应用场景。文章还简要讨论了密码攻击方法和SSL/TLS中非对称加密的应用。

引入

  • 非可逆加密（hash function）：密码保存、文件完整性正确性校验、文件秒上传
    • hash
    • md5（Message Digest Algorithm 5） 128bit
    • SHA（Secure Hash Algorithm）
  • 可逆加密
    • 对称加密
      • DES (Data Encryption Standard) 不安全
      • AES (Advanced Encryption Standard)
    • 非对称加密
      • RSA（Rivest-Shamir-Adleman）

可逆加密是从传统意义上的加密，而非可逆加密通常用于签名

非可逆加密算法

  • 并不是真正意义上的加密，通常被称作hash算法（加密）或者摘要digest算法

    • 非加密哈希函数：用于散列（Hash）数据，速度快；hash表、长链转短链：MurmurHash
    • 加密哈希函数：并具有一些特性，如抗碰撞性（即难以找到两个不同的输入，它们的哈希值相同）、困难性（难以计算出满足特定条件的输入，例如找到一个特定哈希值的输入），以及提供杂凑（Hash）的伪随机性。

  • 主要用一个较短的字符串（数字指纹）代表原来的信息，不可逆

密码保存、文件完整性正确性校验、文件秒上传（该文件MD5存在，说明大概率上传过）

MD5

将任意长度消息 转为 32个16进制数（16B），4个幻数 （信息是减少的，不可逆）

  1. 补齐到512bit（64B）整数，并且最后64位存放原始长度

  2. 每512bit为一个块，再拆分成4B一小块（16块）X[i]，更新幻数64次；更新函数每次更新第一个数

  3. 重复N轮512bit，最后4个幻数就是结果

    image-20240227194554575

攻击

  1. 原像攻击：给出一个MD5，如何得到生成该MD5的消息
  2. 第二原像攻击：给出消息，如何得到生成MD5相同的消息
  3. 扛碰撞性：找出两个MD相同的消息
    • 王小云2004年已经被打破，消息内容是乱码
    • MarcStevens：
      • 相同前缀碰撞：从内容 生成两个内容不同但MD5相同的数据（前缀保留图片或程序但后缀不同）；
      • 选择前缀碰撞：前缀不一样（一个正常程序一个死循环）然后构造后缀使得MD5相同
    • 至此签名并不安全：攻击者可以创造出两个内容不同但签名相同的支票；文件校验从用户端是正常的，但如果用MD5检测软件，会导致正常版本通过检测，然后替换异常版本上架软件商店

SHA系列：

  • SHA-1：产生160位的哈希值，比MD5更安全，但它也已被发现有安全弱点。
  • SHA-2：包含多个版本（如SHA-224, SHA-256, SHA-384, 和SHA-512），相比于SHA-1提供了更高的安全性。
  • SHA-3：最新的SHA版本，使用不同的哈希算法（Keccak），提供了与SHA-2不同的安全性和效率。

MAC

message authentication code：确认完整性并进行身份认证，密钥+hash

HMAC：Hash-based

image-20240408212345680

  • 非可逆加密可以验证文件的完整性，例如从官网下载文件，但前提是官网提供了正确文件的md5
  • a、b之间通信，如果a发送的消息被替换了，单纯使用hash b并不知道消息是否被替换，因为hash也能同时被替换
  • 如果ab之间提前约定了一个密钥，基于该密钥生成HMAC，别人就无法生成替换后的hash值，这就实现了签名。因此想要实现数据不被篡改，需要提前约定一个密钥
  • 在ssl/tls握手时，CA就会用私钥对内容进行签名，用户用公钥解密并对比来查看内容是否被篡改
  • https中，除了生成一个密钥用于加密通信以外，还可以生成一个密钥用于生成HMAC确认消息防止被篡改（其实就算被篡改了，由于中间人不知道加密密钥，篡改的内容也是无意义的）

HMAC-SHA-256

JWT中用的，hash(密钥1+hash(密钥2+消息))

密钥只有服务器知道，因此只有服务器能够生成 token，并验证token是否有效

密码攻击

黑客知道盐s，hash值，算法f(p,s) = hash，但不知道原密码p
他的目的是通过hash值，盐s和算法f，求得密码p，使f(p,s) = hash

暴力破解：也就是原像攻击，暴力找原密码，不可能

  • 方法一：遍历原文为 12345678，meiyoumuma，iloveyou这样的常见密码字典，使用盐和密码作为参数调用算法得到 hash，在数据库中查找 hash 相同的用户，那么他的密码就被知道了。但是如果每个用户盐值不一样，就需要每个用户生成一个字典去攻击，该方法失效
  • 查表攻击（空间大）：事先计算出所有常见密码字典(明文)的hash结果(密文)，然后将其存入数据库中，通过建立索引等方式，当我们拿到一个密文(hash)时，我们去数据库通过索引将其快速查出对应的明文，如果数据库中不存在，则破解失败。加盐后简单密码就变成了123456+salt复杂密码，不在常见密码中，失效；
  • 彩虹表：彩虹表 rainbow-tables - 知乎 (zhihu.com)

实践：强hash函数（SHA-256） + 盐 + 循环hash

现在主流密码处理方式的算法是PBKDF2，流程简述起来是随机生成一个高熵（意思是真的随机而且复杂）Salt，把你的密码和这个Salt连接在一起当作一个整体做一次哈希运算，哈希算法为安全的SHA-256，可以避免哈希碰撞，得到的这个哈希值和你的密码连接在一起再做一次哈希运算，以此类推，重复非常多次，次数越多越安全，但是服务器负担也就越重，一般在10万次以上。最后服务器存储Salt和最后一次得出的哈希值，这样服务器不知道你的密码，但是可以验证你输入的密码是否正确，即使被拖库也不用担心密码被暴力破解，因为随机Salt的引入让彩虹表攻击失效，单独针对你的密码暴力破解要付出遍历密码空间（比如说4位纯数字密码的密码空间是10000，指所有可能的密码组合的个数）所需时间的10万倍以上，比普通的算法要安全许多。在安全性更高的服务器上甚至还会结合硬件密钥来进一步增强安全性，那就是在以上的基础上得出的最后一次哈希值再和硬件密钥作为PBKDF2算法的输入，最终只存储Salt和结合了硬件密钥的最终哈希值，这样子就不给一点暴力攻击的机会了，因为硬件密钥永远不会脱离安全硬件，把相应的硬件断电就一点办法也没有了

可逆加密算法

凯撒密码

移位替换

公元前1世纪，移位替换image-20240408104931318

随机替换

image-20240408105059470

用统计的方法就可以破解，出现最多的e倍替换成了l

image-20240408105137344

多替换表

增加字母替换表，轮换使用替换表进行加密，加密表越多，统计特征慢慢消失

image-20240408105310020

image-20240408113434326

麻烦，enigma就是自动实现了字母表的替换

enigma

1926年开始，德国升级了加密系统，enigma机

  • 字母替换的加密方法，输入o，输出c；再次输入时，输出会不同
  • 解密时直接输入密码可以得到原文，也就是自反的

image-20240408104801371

内部结构

  • 一个转子相当于一个替换表，内部的接线是出厂固定的，但是按下后会转动转动，转动后替换表变了 26*26*26个

    image-20240408112159790

    image-20240408112219190

  • 反射板将信号反射回去（两两连接），使得型号可以自反 + 排己

    image-20240408111708118

  • 解密时转轮的初始位置需要一样，这个相当于是密钥（德军每天更新），也就是破解必须要密钥+同一批次机器

  • 最后是接线板，可以实现交换两个字母 如果12对 有一千多亿种

    image-20240408112439109

破解

密钥+同一批次机器+接线板 机器可以被缴获，密钥每天都更新

德军加密方法：随机密钥SCA，统一密钥DAB

  • 先用统一密钥加密随机密钥两次，放到开头，再用随机密钥加密内容
  • 解密时用统一密钥解密开头，获取随机密钥，再用随机密钥解密内容

大量的内容都是用不同的密钥加密的（减少重复），少量的无意义信息是用统一密钥加密的

image-20240408113818917

前六个字符是破译的关键！重复输入的随机密钥相当于漏洞

破解初始密钥

image-20240408140327786

又因为自反性，D(A(F)) = G 把DA（EB、FG）看成一个整体函数 ，使得F->G

当天的密文有很多，可以把3个函数的26个字母的映射关系都列出

image-20240408140625913

  1. 这些映射存在环
  2. 环的数量集合就是一个**特征(指纹)**，代表着转子的初始位子
  3. 特征集合很少重复，如果构造了特征目录，就可以得到转子的初始位置

image-20240408140914606

构造目录表

一对函数的映射存在环，一次循环的数量2x代表一对环特征x,x

image-20240408141100019

循环测定仪

现在想构建AAA的特征

  1. 设置AAA，另一个设置为AAD（相差3） 用于输出DA函数的特征
    • 随便从一个开始
    • 循环后结束，点亮的数量2x就是当前两个环的数量和，也就是特征为x,x
    • 电亮没有亮过的开关，又得到一组特征y, y 循环执行
  2. 设置AAB，另一个设置为AAE 用于输出EB函数特征
  3. 设置AAC，另一个设置为AAF 用于输出FC函数特征
  4. 结合三个特征，组合成AAA转子的特征

image-20240408141257098

目录表数量
  • 三个随机排列：26*26*26 * A33 大概10w，构造需要1年
  • 五个随机选择3个：10年！
  • 要用机器打败机器，Bomba！

社会工程学

对称加密AES

image-20240408204133847

  • 对称加密用一个相同的密钥进行加密解密，适合1对1的加密方式，但浏览器和服务器之间不能单纯使用同一个密钥，否者大家都一样用户之间相当于没有加密。（握手后随机生成一个传输也不行，因为会被中间人窃取）

  • 因此双方确定密钥过程是关键

  • 预先共享密钥：面对面交换、安全信封或安全通信渠道

  • 密钥分发中心（Key Distribution Center，KDC）：KDC是一个可信的第三方实体，负责生成和分发密钥。发送方和接收方可以向KDC请求密钥，KDC会安全地将密钥发送给它们。这种方法需要发送方和接收方信任KDC的安全性。

  • 通过公钥密码体系配送共享密钥 https

  • Diffie-Hellman密钥交换协议

image-20240411161319844

image-20240411161548610

非对称加密RSA

  • 公钥加密只能私钥解密
  • 私钥加密只能公钥解密
  • 计算复杂度高

image-20240408160753423

image-20240408161058177

  1. 选择两个大质数p和q：这两个质数需要足够大，以确保其乘积n的位数可以满足安全需求。通常，p和q的位数应该在100位以上。
  2. **计算n和φ(n)**：n是p和q的乘积，φ(n)是n的欧拉函数，对于n=pq，φ(n)=(p-1)(q-1)。
  3. 选择公钥e：e需要满足1 < e < φ(n)，且e和φ(n)互质。通常，e可以选择为65537（这是一个常用的公钥，因为它有很好的性质，如二进制表示中只有两个1，计算效率高）。
  4. 计算私钥d：d是e关于φ(n)的模逆元，即满足ed ≡ 1 (mod φ(n))。这个可以通过扩展欧几里得算法来计算。
  5. 输出公钥和私钥：公钥是(n, e)，私钥是(n, d)。

n的因数分解（即找出p和q）是一个已知的困难问题，这就是所谓的”大数因数分解问题”，保证RSA的安全性

ssl/tls

有了非对称加密，就可以使得浏览器和服务器终极那的通信安全。非对称+对称加密

  • 服务器发公钥给浏览器，浏览器随机数（传输密钥）加密后传给服务器，服务器再私钥解密得到 传输密钥（非对称+对称加密 、如果只非对称加密，服务器的数据会被窃取）
  • 问题：如果中间人用窃取公钥并拦截，并生成自己的公钥发给浏览器，作为中间商，就会出问题
  • 如何确定浏览器收到的公钥是服务器给的：（域名、第三方机构、服务器公钥）给CA，CA添加数字签名（内容->hash->私钥加密）后给浏览器。浏览器解密（CA的公钥浏览器中保存了，浏览器信任的CA机构）看是否和明文hash一致

参考

  1. https://www.bilibili.com/video/BV1DS4y1R7hM ↩
  2. https://www.bilibili.com/video/BV1M34y1o7ca ↩
  3. https://www.bilibili.com/video/BV1PL4y1H77Z ↩
  4. MD5为何不再安全 ↩
  5. DH算法 ↩