加密与签名算法

背景

1976 年以前, 所有的加密方法都是同一种模式:

  • 甲方选择某一种加密规则, 对信息进行加密.
  • 乙方使用同一种规则, 对信息进行解密.

由于加密和解密使用同样规则(简称"密钥"), 这被称为"对称加密算法"(Symmetric-key algorithm)

这种加密模式有一个最大弱点:甲方必须把加密规则告诉乙方, 否则无法解密。保存和传递密钥, 就成了最头疼的问题。

1976 年, 两位美国计算机学家 Whitfield Diffie 和 Martin Hellman, 提出了一种崭新构思, 可以在不直接传递密钥的情况下, 完成解密。这被称为 "Diffie-Hellman密钥交换算法"

这个算法启发了其他科学家。人们认识到, 加密和解密可以使用不同的规则, 只要这两种规则之间存在某种对应关系即可, 这样就避免了直接传递密钥。

这种新的加密模式被称为"非对称加密算法":

  • 乙方生成两把密钥(公钥和私钥)。公钥是公开的, 任何人都可以获得, 私钥则是保密的。
  • 甲方获取乙方的公钥, 然后用它对信息加密。
  • 乙方得到加密后的信息, 用私钥解密。

如果公钥加密的信息只有私钥解得开, 那么只要私钥不泄漏, 通信就是安全的。

对称加密

DES

数据加密标准 DES, 采用数据加密算法(Data Encryption Algorithm, DEA), 这是一种对称加密算法, 对称性带来的一个很大的好处在于硬件实现。DES 的加密和解密可以用完全相同的硬件来实现, 所以 DES 的应用很广泛。

DES 的输入分组 64 位, 输出密文 64 位, 密钥的有效位数是 56 位, 加上校验位共 64 位。

具体流程:

  • 输入明文
  • 初始置换, 得到 L 和 R 部分
  • L 和 R 经过 16 次迭代, 得到 64 位中间数据
  • 逆初始置换, 输出 64 位密文

主要缺点:

  • 输入少, 64 位效率略低
  • 加密强度略差, 加密单位 64 位, 穷举法破解有可能

AES

高级加密标准(Advanced Encryption Standard, AES), 又称 Rijndael 加密法, 是美国联邦政府采用的一种区块加密标准。这个标准用来替代原先的 DES, 被广泛使用。

分组长度和密钥长度可以被指定为 128、192 或者 256 bit。

AES 的加密算法的数据处理单位是字节, 128 位的比特信息被分成 16 个字节, 按顺序复制到一个 4×4 的矩阵中, 称为状态(state)。

AES 的所有变换都是基于状态矩阵的变换.

用 Nr 表示对一个数据分组加密的轮数, 在轮函数的每一轮迭代中, 包括 4 步变换:

  • 字节代换运算 (ByteSub())
  • 行变换 (ShiftRows())
  • 列混合 (MixColumns())
  • 轮密钥的添加变换 (AddRoundKey())

其作用就是通过重复简单的非线形变换、混合函数变换将字节代换运算产生的非线性扩散达到充分的混合, 在每轮迭代中引入不同的密钥, 从而实现加密的有效性.

AES 在一定程度上解决了 DES 的问题, 并且应用中占内存较低, 使用比较广泛.

TEA

TEA 算法由剑桥大学计算机实验室的 David Wheeler 和 Roger Needham 于 1994 年发明.

它是一种分组密码算法, 其明文密文块为 64 比特, 密钥长度为 128 比特。

TEA算法利用不断增加的 Delta(黄金分割率) 值作为变化, 使得每轮的加密是不同, 该加密算法的迭代次数可以改变, 建议的迭代次数为 32 轮。

虽然 TEA 算法比 DES(Data Encryption Standard) 要简单得多, 但有很强的抗差分分析能力, 加密速度也比 DES 快得多, 而且对 64 位数据加密的密钥长达 128 位, 安全性相当好。

TEA 的可靠性是通过加密轮数而不是算法的复杂度来保证的。

非对称加密

RSA

1977 年, 三位数学家 Rivest、Shamir 和 Adleman 设计了一种算法, 可以实现非对称加密。这种算法用他们三个人的名字命名, 叫做 RSA 算法。从那时直到现在, RSA算法一直是最广为使用的"非对称加密算法"。

1983 年麻省理工学院在美国为 RSA 算法申请了专利。这个专利 2000 年 9 月 21 日失效。由于该算法在申请专利前就已经被发表了, 在世界上大多数其它地区这个专利权不被承认。

RSA 的大素数基础:n = p * q, p 和 q 都是大素数, 由 n 反推 p 和 q 是一件很困难的事情, n 就是加密的密钥。在实际应用中, n 一般长度在 1024 位以上。

一个简单的流程示意:

  • 服务器选择两个不同素数:p = 61, q = 53
  • 密钥 n = p * q = 3233
  • 欧拉公式 φ(n) = (p-1) * (q-1) = 3120
  • 随机数 e, 1 < e < φ(n), 且 e 与 φ(n) 互质, 随机选择 17
  • 模反数 d, 有 e * d mod φ(n) = 1, 得到 d = 2753
  • 公钥:(n, e)即(3233, 17);私钥:(n, d)即(3233, 2753)
  • 服务器下发公钥 (n, e) 给客户端
  • 公钥加密的过程: 输入 m, 输出 c = m ^ e mod (n), 以 m = 65 为例, 得到 c = 2790.
  • 私钥的解密过程:输入 c, 输出 m = c ^ d mod (n), 以 c = 2790 为例, 得到 m = 65.

D-H 密钥交换

离散对数基础:F(a) = g ^ a mod N, N 是一个大质数(一般要求至少 1024 位长度), g 是一个比较小的质数, 已知 g, a, N 可以很容易的得出 F(a), 但是从 F(a), g, N 推导 a 是一件比较困难的事情.

基于离散对数的 D-H 密钥交换的一个简单流程示意:

  • 客户端生成质数 N 和 g, 假设 g = 5, N = 23. (实际上, N 至少 1024 位)
  • 客户端生成随机因子 a = 6. (a < N)
  • 客户端计算:A = F(a) = 5 ^ 6 mod 23 = 8
  • 客户端发送 g = 5, N = 23, A = 8 到服务器
  • 服务器生成随机因子 b = 15
  • 服务器计算:B = F(b) = 5 ^ 15 mod 23 = 19
  • 服务器发送 B = 19 给客户端
  • 服务器计算 key = A ^ b mod N = 8 ^ 15 mod 23 = 2
  • 客户端计算 key = B ^ a mod N = 19 ^ 6 mod 23 = 2
  • 双方通过交换 (g, N, A) 和 B 达到了交换密钥 key 的效果, 随机因子 a 和 b 在 D-H 交换之后被客户端与服务器丢弃, 具有前置安全性

基于 D-H 交换的一个鉴权协议简化版本:

  • 服务器原始数据:g, N, uin, sault
  • 客户端原始数据:g, N, uin, password
  • 同上面过程的 1-6 步, 第 7 步时同时下发 sault
  • x = hash(password, sault), 假设计算得到 x = 16
  • 服务器计算: s = { A F(x) } ^ b mod N = (8 (5 ^ 16 mod 23)) ^ 15 mod 23 = 1 key = hash(s)
  • 客户端计算: s = (B) ^ (a + x) mod N = 19 ^ (6 + 16) mod 23 = 1 key = hash(s)
  • 客户端计算 M1 = hash(A, B, key), 发送至服务器校验
  • 服务器计算 M2 = hash(A, M1, key), 发送至客户端校验
  • 校验完成之后, 鉴权通过

这个简化版本有字典攻击和拖库的风险.

基于 D-H 交换的SRP协议(secure remote password protocol, 由 Stanford 提出), 一个简单的流程示意:

  • 参数都同上;g = 5, N = 23, x = 16;随机因子 a = 6, b = 15
  • 客户端计算:A = F(a) = 8, 发送至服务器
  • 服务器计算:BX = F(b) + F(x) = 19 + 3 = 22, 发送 BX 和随机数 u 到客户端, 假设 u = 17
  • 客户端计算: s = (BX – X) ^ (a + ux) mod N = (22 - 3) ^ (6 + 17 16) mod 23 = 18 key = hash(s)
  • 服务器计算: s = (A (X^u mod N)) ^ b mod N = (8 (3^17 mod 23)) ^ 15 mod 23 = 18 key = hash(s)
  • 客户端计算:M1 = hash(A, BX, key), 发送到服务器校验
  • 服务器计算:M2 = hash(A, M1, key), 发送到客户端校验

ECC

椭圆曲线加密, 这个专利现在在黑莓手里, 就不考虑了……

签名算法

MD5

MD5 即 Message-Digest Algorithm 5(消息摘要算法第五版)的简称, 是当前计算机领域用于确保信息传输完整一致而广泛使用的散列算法之一(又译哈希算法、摘要算法等), 前身还有 MD2, MD3, MD4.

MD5 算法较老, 散列长度固定为 128 比特, 随着计算机运算能力提高, 更快地找到“碰撞”是有可能的。因此, 在安全要求高的场合不应再使用 MD5.

SHA 算法

SHA 即 Secure Hash Algorithm, 是一种能计算出一个数字信息所对应到的, 长度固定的字符串(又称信息摘要)的算法。SHA 家族的五个算法, 分别是 SHA-1、SHA-224、SHA-256、SHA-384, 和SHA-512, 由美国国家安全局(NSA)所设计。

SHA1 比 MD5 具有更强的安全性, 但是相应的, 计算复杂度也略高。

游戏业务中的通信加密

游戏业务中的通信底层, 需要对数据包进行加密, 加密算法可以采用对称性加密, 例如 AES 或者 TEA 加密, 16 轮或者 32 轮, 视 CPU 情况而定。这个加密的密钥, 可以通过非对称的 DH 密钥交换获取, 防止网络监听。

具体的代码可以基于 OpenSSL 开源来开发 (1.0.2 stable 以上版本, 避免 Heartbleed), 一份简单 C 代码示例如下.

void test_dh(int save_pem)
{
    DH *server, *client;
    int i, ret, errcode;
    uint8_t* key;
    FILE* pem;

    pem = fopen(DH_PEM_FILE, "r");
    if (pem) {
        server = PEM_read_DHparams(pem, NULL, NULL, NULL);
    } else {
        server = DH_new();

        // generator dh parameters
        ret = DH_generate_parameters_ex(server, DH_PARAMETER_LEN,
            DH_GENERATOR_2, NULL);
        if (ret != 1) {
            printf("server generate parameters fail: %d\n", ret);
            goto DH_FAIL;
        }

        // check parameters
        ret = DH_check(server, &errcode);
        if (ret != 1) {
            printf("server parameters check fail: %d\n", errcode);
            goto DH_FAIL;
        }
    }

    // 实际上, 这里的P和G就是客户端和服务器需要提前约定的大质数参数
    printf("P: %s\n", BN_bn2hex(server->p));
    printf("G: %s\n\n", BN_bn2hex(server->g));

    // generator key
    ret = DH_generate_key(server);
    if (ret != 1) {
        printf("server generate key fail: %d\n", ret);
        goto DH_FAIL;
    }

    // check public key
    ret = DH_check_pub_key(server, server->pub_key, &errcode);
    if (ret != 1) {
        printf("server check public key fail: %d\n", errcode);
        goto DH_FAIL;
    }

    // duplicate client for test
    client = DH_new();
    client->p = BN_dup(server->p);
    client->g = BN_dup(server->g);

    // client generate key
    ret = DH_generate_key(client);
    if (ret != 1) {
        printf("client generate key fail: %d\n", ret);
        goto DH_FAIL;
    }

    // check client public key
    ret = DH_check_pub_key(client, client->pub_key, &errcode);
    if (ret != 1) {
        printf("client check public key fail: %d\n", errcode);
        goto DH_FAIL;
    }

    // client compute key: params(server public key, p, g)
    key = (uint8_t*)calloc(DH_size(server), sizeof(uint8_t));
    DH_compute_key(key, server->pub_key, client);
    if (ret <= 0) {
        printf("client compute key fail: %d\n", ret);
        goto DH_KEY_FAIL;
    }
    printf("server public key: %s\n", BN_bn2hex(server->pub_key));
    printf("client calculate key: ");
    for (i = 0; i < DH_size(server); ++ i) {
        printf("%X%X", (key[i] >> 4) & 0xf, key[i] & 0xf);
    }
    printf("\n\n");

    // server compute key: params(client public key, p, g)
    free(key);
    key = (uint8_t*)calloc(DH_size(client), sizeof(uint8_t));
    DH_compute_key(key, client->pub_key, server);
    if (ret <= 0) {
        printf("server compute key fail: %d\n", ret);
        goto DH_KEY_FAIL;
    }
    printf("client public key: %s\n", BN_bn2hex(client->pub_key));
    printf("server calculate key: ");
    for (i = 0; i < DH_size(server); ++ i) {
        printf("%X%X", (key[i] >> 4) & 0xf, key[i] & 0xf);
    }
    printf("\n\n");

    // save pem file if first time
    if (!pem && save_pem == 0) {
        pem = fopen(DH_PEM_FILE, "w");
        if (pem) {
            PEM_write_DHparams(pem, server);
            printf("save dh pem for first time\n");
        }
    }

DH_KEY_FAIL:
    free(key);
DH_FAIL:
    DH_free(server);
    DH_free(client);
    if (pem) {
        fclose(pem);
    }
}

参考文章