密码学小白必知必会

一 背景介绍

本文是以介绍密码学基本概念为目的，面向密码学小白或者新人的文章。包含的内容主要是一些课本知识，个人理解，还有一些实例及代码。下面，将从密码学的基础，应用，及实例等几个方面对密码学进行简单的介绍。

二 什么是密码学

1 简介

首先来一段维基百科上面对密码学的定义：

密码学（英语：Cryptography）可分为古典密码学和现代密码学。在西方语文中，密码学一词源于希腊语kryptós“隐藏的”，和gráphein“书写”。古典密码学主要关注信息的保密书写和传递，以及与其相对应的破译方法。而现代密码学不只关注信息保密问题，还同时涉及信息完整性验证（消息验证码）、信息发布的不可抵赖性（数字签名）、以及在分布式计算中产生的来源于内部和外部的攻击的所有信息安全问题。古典密码学与现代密码学的重要区别在于，古典密码学的编码和破译通常依赖于设计者和敌手的创造力与技巧，作为一种实用性艺术存在，并没有对于密码学原件的清晰定义。而现代密码学则起源于20世纪末出现的大量相关理论，这些理论使得现代密码学成为了一种可以系统而严格地学习的科学。 最早的密码可能要追溯到公元前2000年，当时古埃及还在使用象形文字，可见，在远古时代，用户就已经开始注重个人隐私了。密码使用的相关工具也在逐步演进，比如最早古希腊会使用斯巴达密码棒：

发信和收信两端只有使用相同直径的棍子，将密码羊皮条进行缠绕才能得到密码。到后来的密码盘，再到二十世纪的各种加密机械。到而今，加密的形式也从原来的语言学模式，转变为了结合信息论，数论，统计学等学科的一门工程科学，其中香农定理有着奠基作用。

2 基础概念

下面先介绍几个基本概念，明文指的是加密前的报文，密文指的是机密后的报文，加密需要的串叫密钥，全部可能密钥组成的集合叫密钥空间。在现代的密码学中，对密码学的严格定义应为：密码编码学，旗下有两个分支，不精确的定义如下：

• 密码使用学：负责用各种手段加密。
• 密码分析学：负责研究加密，包括怎么解密。 我们日常接触到的应该都只是密码使用学，其本身包含下面的三个主要分支：
• 对称算法：加密和解密双方共用同一个密钥
• 非对称算法：有一对密钥，公开的密钥为公钥，不公开的密钥为私钥。
• 密码协议：密码学算法的应用，例如协商如何使用这些加密算法，比如TLS。 绝大多数的实际加密应用都是对称加密，非对称加密以及哈希函数混用的混合方案。

2.1 Kerckhoffs定理

Kerckhoffs假设：

如果你的新的密码系统的强度依赖于攻击者不知道算法的内部机理，你注定会失败。如果你相信保持算法的内部秘密比让研究团体公开分析它更能改进你的密码系统的安全性，那你就错了。如果你认为别人不能反汇编你的代码和逆向设计你的算法，那你就太天真了（比如RC4算法的例子）。最好的算法是那些已经公开的，并经过世界上最好的密码分析家们多年的攻击，但还是不能破译的算法

Kerckhoffs定理 ：即使整个系统出了密钥之外都是公开的，这个密码体制也必须是安全的。也就是说，加密算法和解密算法即使暴露了，这个系统也要保证安全。

PS：但也有例外，在政府或者军事领域，加密算法通常也是保密的：不过，国家安全局对外保持他们的算法的秘密，但他们有世界上最好的密码分析家在内部工作。另外，他们也会互相讨论他们的算法，通过执著的审查，去发现他们工作中的弱点。

2.2 加密的演化进程

首先说明一下如何衡量算法的安全性呢？主要是以下几点规则：

• 破译的代价大于加密数据的价值，则安全。
• 破译所需时间大于数据保密期，则安全。
• 加密所需数据量显著小于破译所需数据量，则安全。

加密的手段是多种多样的，比如隐写术：将加密的数据藏在暴露的数据中，具体的用隐形墨水，藏头诗等；字母换位：典型的比如凯撒密码；轮转机：进行多次轮转，每一次轮转对应不同的字母映射关系，遗憾的是，即使是很复杂的轮转机在二战中还是被破解了；乱码本：可以做到每次一个不同的密钥。

现代用的多是计算机密码：比如DES, AES, RSA, 数字签名等等。

2.3 几种破译密码的方式

有多种破译密码的方式，下面举几个例子：

• 经典码分析的方式：意图通过密文恢复明文或者密钥，这种一般可以通过对加密的本身构造原理进行分析，或者通过黑盒测试进行分析。
• 通过旁路分析获得密钥：比如通过测量私钥处理器的功耗，通过信号处理恢复密钥，还有比如通过电磁辐射等分东西密钥信息。听着比较玄幻，但是搜了一下，相关的论文还是不少的。
• 再比如说社会攻击：意思就是说通过勒索，绑架，贿赂等方式获得密钥，小伙伴们千万小心。

还有一些比较通用的手段，比如词频分析等，通过分析密文的字母频率寻找明文的映射关系，破译甲骨文，象形文字估计主要用的就是类似的方法。下面列了一下英文字母的出现频率：

3 学术上的破解定义

在密码学的学术理论中，任何攻击方式，其计算复杂度若少于暴力搜索法所需要的计算复杂度，就能被视为针对该密码系统的一种破密法；但这并不表示该破密法已经可以进入实际应用的阶段。

三 现代数据加密算法

首先要在这里明确一个概念，下文出现的DES,AES,RSA等严格来说不能算是加密算法，而是一种加密标准，与广大程序员熟知的http协议一样，协议定义的是标准，大家可以有不同的实现手段。

1 对称加密

对称加密的基本前提是：双方使用同一个密钥，并使用相同的加解密算法。在1976年之前，所有的加密算法都是基于对称加密的。常见的对称加密算法有DES,3DES,AES等。

1.1 DES加密

DES是 Data Encryption Standard 的简写，翻译为数据加密标准，是一种对称加密算法。DES算法起源于美国的美国标准局（NBS），其呼吁找到一个可以应用于多个领域，保证安全的密码学算法。最终NBS采用了IBM提交的基于Lucifer密码的方案，这方案后被命名为DES，直到1990年人们都没有发现DES的安全隐患，直到1999年才被更高级的加密标准AES(Advanced Encryption Standard: 高级加密标准)所取代。

强加密算法基本都是基于以下两个属性：

• 混淆：模糊密文和密钥之间的关系。
• 扩散：隐藏密文的统计属性。

1.1.1 加密方式

DES使用56位密钥（还有8位校验位）对64位长分组进行加密 (江湖传言：这个56位密钥据说是在NBS的要求下从128位修改来的，由于NBS掌握一定的破译原理，这样会使其破解难度降低)，有关DES的详细内容可以查看des详细介绍这篇文章。DES整体流程如下：

具体的流程是：

1. 先对明文进行初始置换，和对种子密钥进行PC-1置换，置换需要按照置换表进行。
2. 进行十六轮迭代运算。
3. 进行逆初始置换，得到密文。

具体过程还是很复杂的，这里只列出了最基本的步骤。对密文进行解密时，需要按照相反的步骤重新进行一次即可。

1.1.2 安全性

即使经过了这么多复杂的步骤，DES的安全性还是得不到保障：

• 1997年6月，DESCHAL计划第一次公开破解了DES加密的信息；
• 1998年7月，EFF的DES破解机（Deep Crack）在56小时内破解了DES密钥；
• 1999年1月，Deep Crack和distributed.net合作在22小时15分钟内破解了一个DES密钥
• 2006年4月，德国鲁尔大学和基尔大学合作的并行计算机9天内破解了DES，一年内将平均时间缩短到6.4天
• 2008年11月，RIVYERA计算机将平均破解时间降低到了一天内；

为了化解风险，现在金融系统普遍使用3DES，也就是将DES做了三次，可以理解成密钥的长度也增加了三倍，这种目前还无法被暴力破解；还有一种标准就是下面要讲的，现在也被普遍应用的AES。

1.2 AES加密

AES出现是在3DES后，DES的缺陷在于软件实现并不高效，而3DES更是加剧了这一过程，而且DES的分组较小，在某些领域有着比较大的缺陷。经讨论后，NIST经过重重选拔后选择了Rijndael算法成为了新的标准：AES。AES是目前使用最为广泛的一种对称加密标准，到目前为止，已知的针对AES最为有效的攻击就是蛮力攻击。可以看下当初AES标准的候选要求：

• 分组大小为128位的分组密码；
• 需要支持三种密码长度：128位，192位和256位；
• 比提交的其他算法更安全；
• 在软件和硬件上都可以高效实现；

1.2.1 openssl中的aes

更细节的实现就本篇就忽略了，我们来看一下openssl中的使用方式：

#include <openssl/conf.h>

#include <openssl/evp.h>

#include <openssl/err.h>

#include <string.h>

void handleErrors(void)

{

    ERR_print_errors_fp(stderr);

    abort();

}

int encrypt(unsigned char *plaintext, int plaintext_len, unsigned char *key,

            unsigned char *iv, unsigned char *ciphertext)

{

    EVP_CIPHER_CTX *ctx;

    int len;

    int ciphertext_len;

    // openssl初始化

    if(!(ctx = EVP_CIPHER_CTX_new())) handleErrors();

    // 加密初始化，指定加密方式

    if(1 != EVP_EncryptInit_ex(ctx, EVP_aes_256_cbc(), NULL, key, iv)) handleErrors();

    // 对明文加密

    if(1 != EVP_EncryptUpdate(ctx, ciphertext, &len, plaintext, plaintext_len)) handleErrors();

    ciphertext_len = len;

    // 加密完成

    if(1 != EVP_EncryptFinal_ex(ctx, ciphertext + len, &len)) handleErrors();

    ciphertext_len += len;

    // 释放资源

    EVP_CIPHER_CTX_free(ctx);

    return ciphertext_len;

}

int decrypt(unsigned char *ciphertext, int ciphertext_len, unsigned char *key,

            unsigned char *iv, unsigned char *plaintext)

{

    EVP_CIPHER_CTX *ctx;

    int len;

    int plaintext_len;

    // 与加密反向操作

    if(!(ctx = EVP_CIPHER_CTX_new())) handleErrors();

    if(1 != EVP_DecryptInit_ex(ctx, EVP_aes_256_cbc(), NULL, key, iv)) handleErrors();

    if(1 != EVP_DecryptUpdate(ctx, plaintext, &len, ciphertext, ciphertext_len))

        handleErrors();

    plaintext_len = len;

    if(1 != EVP_DecryptFinal_ex(ctx, plaintext + len, &len)) handleErrors();

    plaintext_len += len;

    EVP_CIPHER_CTX_free(ctx);

    return plaintext_len;

}

int main (void)

{

    // 256位，一个字节8位，所以长度为32

    unsigned char *key = (unsigned char *)"hello,how_are_you_i_m_fine_thx_u";

    // 128位，128/8=16

    unsigned char *iv = (unsigned char *)"i_am_fine,too...";

    // 待加密明文，这里需要注意明文不能超过指定超度

    unsigned char *plaintext =

        (unsigned char *)"大家好，我是本次加密的明文，很荣幸见到大家！";

    unsigned char ciphertext[128];

    unsigned char decryptedtext[128];

    int decryptedtext_len, ciphertext_len;

    // 加密

    ciphertext_len = encrypt (plaintext, strlen ((char *)plaintext), key, iv,

                              ciphertext);

    printf("加密后的密文为: ");

    BIO_dump_fp (stdout, (const char *)ciphertext, ciphertext_len);

    // 解密

    decryptedtext_len = decrypt(ciphertext, ciphertext_len, key, iv,

                                decryptedtext);

    decryptedtext[decryptedtext_len] = '0';

    printf("解密后得到原文: ");

    printf("%sn", decryptedtext);

    return 0;

}

编译运行后得到如下输出:

明文为: 大家好，我是本次加密的明文，很荣幸见到大家！ 公钥为: hello,how_are_you_i_m_fine_thx_u 初始向量为: i_am_fine,too...加密后的密文为: 0000 - 10 a6 b7 11 83 01 7e 70-37 01 6a 52 04 f4 6a 05 ......~p7.jR..j. 0010 - 6a 03 1c 48 7a 42 71 bc-24 d9 68 df 60 77 85 2b j..HzBq.$.h.`w.+ 0020 - d4 68 03 99 1d b2 0f 24-4c c5 65 75 1c 38 32 06 .h.....$L.eu.82. 0030 - 9e 48 7d fa ef 4f 2b 9d-22 84 d8 25 c3 c3 15 8c .H}..O+."..%.... 0040 - 51 87 16 d2 38 1a 0b 9e-38 cb 0d 41 41 bd dc aa Q...8...8..AA...解密后得到原文:

大家好，我是本次加密的明文，很荣幸见到大家！

可以看到aes加密的几个要素：

• 明文
• 加密模式（五种：CBC,ECB,CTR,OCF,CFB）
• 公钥
• 初始向量

2 非对称加密

不同于对称加密只有一个公钥，非对称加密有一对秘钥，这使得非对称加密不仅能应用于传统的数据加密中，也可以应用于诸如数字签名等领域。

2.1 RSA介绍

RSA加密是一种非对称加密，名字来源于三位创始人的名字首字母：Ron Rivest, Adi Shamir, and Leonard Adleman，广泛应用于我们所熟知的各种协议中，可以说，只要有网络的地方，就有RSA。RSA的安全性极高，RSA的加解密都是在整数环(所谓整数环指的应该是一个满足加法和乘法的线性空间)内完成的，模计算在其中发挥了核心作用，下面引用维基百科上面的RSA描述：

对极大整数做因数分解的难度决定了 RSA 算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA 算法愈可靠。假如有人找到一种快速因数分解的算法的话，那么用 RSA 加密的信息的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的 RSA 钥匙才可能被强力方式破解。到目前为止，世界上还没有任何可靠的攻击RSA算法的方式。只要其钥匙的长度足够长，用RSA加密的信息实际上是不能被破解的。

虽然RSA安全性较高，但比起AES、3DES和其它对称算法来说，其加解密速度慢得多。这就要求，在很多的实际应用中，开发者需要做取舍，比如TLS协议一般就会结合AES和RSA。

• RSA的加解密过程可以简单表示为：

E和N的组合即为公钥。

• RSA的解密过程为：

D和N的组合即为解密密钥，N在加解密中为同一个数字。当然E,D,N的生成是一个比较复杂的过程。

openssl中rsa的加解密过程和aes的api调用顺序基本是一致的，不同的是，rsa对公私钥的要求比较高，一般都是通过调用api在本地生成公私钥文件，在加解密的时候读取本地的公私钥进行。rsa的公私钥一般是要进行持久化的，这也是由其密码特性和应用特性决定的。这里就不重复列代码了。

2.2 RSA应用

RSA的应用主要是在加解密和验签上，解密和验签看起来是对称的过程，但实际上有所差别。

2.2.1 RSA加解密

如果想要解密，那么只有持有私钥的人才能解密，所以RSA的加解密过程是公钥加密，私钥解密。

• 如果被窃听，公钥泄露没关系，反正拿不到明文。
• 私钥要保管好。

2.2.2 RSA验签

验签过程是用公钥验证：通过私钥颁发的签名。RSA验签的方式和解密的方式几乎是一致的，我们看一下openssl的验签api：

int int_rsa_verify(int type, const unsigned char *m, unsigned int m_len,

                   unsigned char *rm, size_t *prm_len,

                   const unsigned char *sigbuf, size_t siglen, RSA *rsa)

若返回1代表成功。在openssl源码继续跟踪：发现了这么一段：

if (memcmp(decrypt_buf, m, SSL_SIG_LENGTH) != 0) {

  ERR_raise(ERR_LIB_RSA, RSA_R_BAD_SIGNATURE);

  goto err;

}

说明验签方案是通过公钥解出明文再去和原文进行对比的。

2.2.3 思考

前面说明了私钥能做的公钥也能做，那么为什么还要有公私钥之分呢？

答：密码学对公钥和私钥的要求是不一样的，在生成过程中参数的复杂度也大不相同，破解难度也是不一样的，所以我们的私钥一般都要比公钥大。例如为了抵挡1024bit操作数的广播攻击，rsa的私钥长度要求256bit，公钥17bit就可以了。

结论是：理论上公私钥反着来也可以，但是出于安全等因素的考虑，还是别搞事了，年轻人要讲武德。

3 秘钥交换算法

前文已经介绍了集中加解密方案，与之同等重要的是：如何在网络上进行必要的信息传输，使得双方完成加解密过程呢？

3.1 DH秘钥交换

Diffie-Hellman密钥交换(DHKE)是在公开文献中发布的第一个非对称方案，它提供了一种密钥分配问题的解决方案，使双方能够通过不安全的信道得到一个相同密钥。很多著名的协议都有DH的身影，例如SSH，TLS协议。

3.1.1 DH基本描述

DH交换步骤如下所示：

p为Alice选择的素数，g为Alice选择的底数，a为Alice生成的随机数，Alice通过p,g,a生成A，将p,g,A发送给Bob，Bob生成随机数b,再通过g,p,b生成B发送给Alice，Alice和Bob通过模运算即可得到相同的K。

为了使这个过程变得安全，必须使用非常大的a, b 以及 p，g可以比较小，实际中一般使用2和5。

3.1.2 DH安全性

DH过程可以防止窃听，但是不能防止中间人攻击，如果中间人对Alice扮演Bob，同时对Bob扮演Alice，那么就能监听Alice和Bob信道上的所有通信，为了防止中间人攻击，实际上需要引入另外一种机制：证书认证机构。这里就不展开了。

3.2 ECDH

ECDH是在保留了DH基本思想的基础上引入了椭圆曲线密码学(ECC)，ECC使用较短的操作数可以提供与RSA相同级别的安全等级，所需操作数的位数比大致为：ECC通过160 ~ 256位的操作数可产生等同于RSA1024 ~ 3072位操作数的安全等级。但是在RSA使用较短公钥时，会比ECC快很多。

3.2.1 ECDH基本描述

ECDH需要准备什么：

• 一个素数p和椭圆曲线(椭圆曲线不是椭圆)：

长这样：

• 一个本原元

ECDH的大致过程见下图：

Youtube这个视频讲的不错，推荐大家观看：ECDH

具体过程为：

Alice和Bob分别选择了自己的私钥dA,dB (为大整数,是椭圆曲线的参数)，然后通过点乘本原元G(椭圆曲线上的一个点)计算出各自的公钥QA, QB， 这两个公钥都是椭圆曲线上的点，（这里再延伸一下，椭圆曲线的点乘可以理解为累加，椭圆曲线的加法是有特殊定义的，不是我们通常理解的实数域内的加法。）Alice和Bob在收到对方公钥后再分别和各自的私钥进行点乘计算，即可得到一个联合秘钥：share 。

3.2.2 安全性

• ECDH与DH基本原理相同，所以都可以做到可防窃听，不可防中间人攻击。
• 在数学构造上，如果使用密码学健壮的椭圆曲线，安全强度有保障。

3.2.3 使用

具体的使用方式可见openssl ecdh wiki，椭圆曲线要求是非奇异的，openssl中给定了几个选项指定曲线：

> openssl ecparam -list_curves

输出: 

  secp384r1 : NIST/SECG curve over a 384 bit prime field

  secp521r1 : NIST/SECG curve over a 521 bit prime field

  prime256v1: X9.62/SECG curve over a 256 bit prime field

3 HASH

除了上述的对称加密与非对称加密，一些hash算法在日常应用中也很常见。hash函数是一个非常重要的密码学组件，严格来说，hash函数生成了一串固定长度的位字符串，形成了一个消息的摘要，也可以看做是这条消息的指纹。hash也是数字签名，验证码等应用的核心部分。

3.1 密码学中的hash背景

假设我们有hash函数: h，明文: x, 输出: z, 那么要求有：

实用性角度：

• x不限长度：h(x)可适用于任意长度x。
• 固定输出长度：c = len(h(x)) = len(z)，c 为固定长度。
• 有效性：h(x)的计算相对简单。

安全性角度：

• 单向性（不能逆向求解），不能通过z和h计算出x，术语：抗第一原性。
• 弱抗冲突性（很难发生hash冲突），给定x和h(x)，无法找到y使得h(x) = h(y)，术语：抗第二原性。
• 强抗冲突性（不发生冲突），对于任意的x,y，无法找到h(x) = h(y)，术语：抗冲突性。

3.2 MD5

目前最流行的hash算法基本都属于MD4家族，例如MD5，SHA家族，RIPEMD等。MD4使用32位变量，所有操作都是按位进行的布尔操作。基本流程为：

• 数据填充：将数据填充到512位的倍数。
• 分组处理：将每64字节(512位)分组处理。

MD5是在MD4的基础上做了改进，主要增强算法复杂度和不可逆性，不过操作都是大同小异，概述见下。

3.2.1 基本步骤

MD5算法的原理可简要的叙述为：MD5码以512位分组来处理输入的信息，且每一分组又被划分为16个32位子分组，经过了一系列的处理后，算法的输出由四个32位分组组成，将这四个32位分组级联后将生成一个128位散列值(百度百科)

处理步骤为：

其中\oplus, \wedge, \vee, \neg 是 XOR, AND, OR , NOT 的符号。

3.2.2 安全性

MD5作为一个hash函数，在hash过程中做的是有损操作，是不能通过密文恢复到原文的，因此，在我们谈MD5的安全性的时候，就要结合具体的使用场景来看，不能提到MD5就说它不安全：

• 使用md5作为文件摘要问题不大：要看文件的重要性和具体场景。
• 即使使用加盐md5做密码存储依然不安全，不过并不是因为md5密码学上的缺陷，而是因为md5的计算很快，md5通过GPU每秒可以计算10亿量级的次数。所以一般要采取SHA-2方案。

总结一下：出于安全和省心考虑，能不用md5就别用了。

3.3 SHA家族

SHA是Secure Hash Algorithm的简写，译为安全散列算法，也是经过FIPS认证的。与之前提到的AES，DES等类似，也是由NSA设计,NIST发布的。有如下几种系列：

• SHA-0: 1993年发布,很快就被撤回了，是SHA-1的前身。
• SHA-1: 1995年发布，目前仍在许多安全协议中使用，例如TLS，SSH，出现时被视为MD5的继任者，安全性在2010年后已不足。
• SHA-2: 2001年发布，包括SHA-224、SHA-256、SHA-384、SHA-512、SHA-512/224、SHA-512/256。至今尚未出现有效攻击，但其算法SHA-1基本相似。
• SHA-3: 2015年发布，出现的原因是NIST希望有一个与SHA-1算法形式不同的加密算法，作为一个可替换选项。

3.3.1 基本步骤

SHA-1允许的最大消息长度是2的64次方位，产生的输出为160位。基本步骤如下：

(1) 信息填充：使其成为512bit的整数倍，并且将每512位视为一个分组。

(2) 根据输入的512分组计算出80个32bit的值。

(3) 对每个分组进行处理，得到五个32bit的值。

(4) 单步处理：

tips:

SHA-1是专门为了良好的软件实现设计的，每轮只需要使用32的寄存器进行布尔操作。在传统FPGA上最新的硬件实现可以达到 n Gb/s。

3.3.2 安全性

• SHA-0没发布多久就被撤回了，怎么看都不会安全。
• 2017年2月23日，Google公司公告宣称他们与CWI Amsterdam合作共同创建了两个有着相同的SHA-1值但内容不同的PDF文件，这代表SHA-1算法已被正式攻破。2020年，针对SHA-1的选择前缀冲突攻击已经实际可行。
• SHA-2目前是安全的，但是基本算法与SHA-1相同，而SHA-1已被攻破，目前的安全并不代表两年后的安全。
• SHA-3目前是安全的。

值得说明的一点是，目前主流的hash还是SHA-2，影响SHA-3推广的主要原因是，现有软硬件对SHA-3的实现支持不好，在特定fpga硬件平台上SHA-3的速度会比SHA-512快一个数量级，但是在intel平台下，sha-512是sha-3计算效率的两倍。

四 总结

本文从密码学基本概念入手，介绍了对称加密方案和非对称加密方案，并由此引出了加密通信的双方需要注意的秘钥交换问题。最后列举了常见的hash方案及其用途。下面以几句话总结全文：

• DES尽量不要用，3DES起步，或者用AES。
• MD5尽量不要用，尽量用SHA-2家族的hash函数。
• 秘钥交换首选ECDH。
• RSA加密和签名要搞清，不要弄混，尤其不要把公私钥弄混。

做安全方案前要考虑周全，安全是大，一旦出问题就是大问题。