加密与签名算法

加密与签名算法

背景

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);
    }
}

参考文章

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏企鹅号快讯

黑客们都是如何给勒索软件加密的?

加密是计算机科学中历史最长久的一种计算了。早在二战时期,德国就制造了Enigma密码机,来传输机密信息。计算机科学的祖师爷之一图灵也参与了对Enigma密码的破...

2219
来自专栏小工匠技术圈

【Java小工匠聊密码学】--非对称加密--RSA1

  RSA加密算法是一种非对称加密算法。在公开密钥加密和电子商业中RSA被广泛使用。RSA是1977年由罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(...

833
来自专栏程序员叨叨叨

【翻译】数字签名是什么?

在写上一篇《Android Keystore漫谈》时对数字证书和数字签名的区别感觉模棱两可,于是网上找了找资料发现了一篇简单易懂的文章,对证书和签名有了一个较清...

844
来自专栏漏斗社区

CTF|玩转RSA加密算法(一)

RSA是一种非对称加密算法,它由 公钥(n/e),私钥(n/d),明文M和密文C组成。我们做CTF题目时,一般题目中会给出公钥和密文让我们推出对应的私钥或者明文...

7169
来自专栏黑白安全

如何攻破加密算法

当应用加密算法时,有许多地方可能会出错。难点在于识别和分析程序员用来加密的方法,然后寻找其中的漏洞。漏洞的种类也很多,比如弱加密算法、弱密钥生成器、服务端漏洞和...

1792
来自专栏吴伟祥

加密 原

在日常设计及开发中,为确保数据传输和数据存储的安全,可通过特定的算法,将数据明文加密成复杂的密文。目前主流加密手段大致可分为单向加密和双向加密。

773
来自专栏安恒网络空间安全讲武堂

学习分享 | Padding Oracle

0x00前言 之前写CBC翻转攻击的时候就在想什么时候能遇到Padding Oracle的题目hhhhh 想不到这么快就遇到了hhhhh ------- 0x0...

2288
来自专栏GAIAWORLD

GaiaWorld:加密技术在区块链中的意义

加密技术作为区块链技术里极其重要、不可或缺的一部分,为区块链的匿名性、不可篡改和不可伪造等特点保驾护航。如果说共识机制是区分一个公链质量的核心和灵魂,那么加密算...

970
来自专栏jouypub

区块链之非对称加密算法

非对称加密,在现在网络应用中,有这非常广泛的场景,更是加密货币的基础。本文主要介绍非对称加密、解密的原理和过程,以及在区块链中的使用。

1671
来自专栏程序猿

数据加密之加密算法RSA公钥加密系统

本来想写一下SQL注入来着,还是写一下这个可爱的算法吧。 加密算法有多中,md5等多中加密算法,但是RSA算法不知各位有没有听说...

39110

扫码关注云+社区

领取腾讯云代金券