密码学算法简介

发表于 |

前言

本文主要介绍常用的加解密算法。常用的算法大致分为以下几类：

  • 哈希算法
  • 古典加密
  • 对称密钥加密
  • 非对称密钥加密

哈希算法

常用的哈希算法，可以对任意长度的报文计算出固定长度的摘要，俗称哈希值。哈希值相对于原文来说要简短的多，往往只有十几或者几十个字节，因此也称为摘要算法。这个计算过程理论上是单向不可逆的：从报文可以计算出摘要，但是从摘要无法逆向计算出原始的报文。

哈希算法的一个重要应用就是加密密码，加密后的密码无法被逆向反推，从而达到受保护的目的。在校验密码时，我们只需要比对哈希后的值即可。

此外，哈希算法还可以用来校验完整性。例如很长一段信息或者下载获得一份文件，怎么能保证就是原始的信息或者文件呢？我们只需要对比传输前后信息的哈希值或者下载文件和原始文件的哈希值即可确定是否完整。

哈希算法(信息或文件) = 摘要 或 哈希值

SHA-1

SHA-1（Secure Hash Algorithm 1）是一种密码哈希函数，美国国家安全局设计，并由美国国家标准技术研究所发布为联邦数据处理标准。SHA-1可以生成一个被称为消息摘要的160比特位( 20字节 )散列值，散列值通常的呈现形式为40个十六进制数。

SHA-1目前已经不够安全，已经有很多有效攻击的手段，因此正在被减少使用。

SHA-2

SHA-2 属于SHA-1算法的后继者。其下又可再分为六个不同的算法标准，包括了：SHA-224、SHA-256、SHA-384、SHA-512、SHA-512/224、SHA-512/256。后面的数字代表了最后摘要值的比特位数。

SHA-2的密码安全性目前还未得到广泛信任，有待进一步验证。SHA-256( 32字节 )算法目前已经被 TLS1.2标准采用。

MD5

MD5消息摘要算法（Message-Digest Algorithm），一种被广泛使用的密码散列函数，可以产生出一个128位（ 16字节 ）的散列值（hash value）。

2009年，中国科学院的谢涛和冯登国用了很小的碰撞算法复杂度，破解了MD5的碰撞抵抗，该攻击在普通计算机上运行只需要数秒钟。因此，对于需要高度安全性的数据，专家一般建议改用其他算法，如SHA-2系列算法。

暴力破解

使用哈希算法保护的密码目前已经很容易被暴力破解，其中就采用了一种称为 table 的技术。黑客们发现如果能够实现直接建立出一个数据文件，里面事先记录了采用和目标采用同样算法计算后生成的Hash散列数值，在需要破解的时候直接调用这样的文件进行比对，破解效率就可以大幅度地，甚至成百近千近万倍地提高，这样事先构造的Hash散列数据文件在安全界被称之为Table表(文件)。最出名的Tables是Rainbow Tables，即安全界中常提及的彩虹表。正是由于Rainbow Tables的存在，使得普通电脑在5分钟内破解14位长足够复杂的Windows帐户密码成为可能。

针对彩虹表之类的暴力破解方式，可以采用的方法就是添加多字节随机盐及多次哈希，增加破解建表的难度，从而提升密码相对安全性。例如

1
saltedhash(password) = hash(password || salt)

或者

1
saltedhash(password) = hash(hash(password) || salt)

推荐使用 bcrypt 或者 PBKDF2 加盐哈希算法。

古典加密

古典加密是历史上使用过的加密信息的算法，其大部分加密方式都是利用替换式密码或移项式密码，有时则是两者的混合。其于历史中经常使用，但现代已经很少使用，大部分的已经不再使用了。许多密码起源于军事上，相同立场的人常使用来寄送秘密讯息。经典的方法常攻击密码文，有时候甚至不知其密码系统，也可以使用工具，像是频率分析法。有些经典密码是使用先进的机器或是机电密码机器，像是恩尼格玛密码机。

经典密码通常很容易被破解。许多经典密码可单单经由密文而破解，用暴力破解或者频率分析可以轻而易举的攻破这些加密算法。

替换式密码

凯撒密码是广为人知的代换密码。为了用凯撒密码法加密讯息，每个密码字母集中的字母将会被其位置的后3个字母替代。因此字母A将会被字母D替代、字母B将会被字母E替代、字母C将会被字母F替代等，最后，X、Y和Z将分别的被替代成A、B和C。例如，”WIKIPEDIA”将被加密成”ZLNLSHGLD”。凯撒把字母向后移”3”位，但其他数字也可照著作。

移位式密码

移位式密码，它们字母本身不变，但它们在讯息中顺序是依照一个定义明确的计划改变。许多移位式密码是基于几何而设计的。一个简单的加密（也易被破解），可以将字母向右移1位。例如，明文”Hello my name is Alice.”将变成”olleH ym eman si ecilA.”

加解密算法

加解密的过程和哈希是不同的，它在计算的过程中需要提供一种称为密钥的参数：

加密算法(报文, 加密密钥) = 密文

解密算法(密文, 解密密钥) = 报文

如果加密密钥 == 解密密钥，则称为对称加密算法

如果加密密钥 != 解密密钥，则称为非对称加密算法

此外，根据加密计算的规则不同，还可以分为流加密算法和块加密算法 block

对称加密算法

对称密钥加密（Symmetric-key algorithm）又称为对称加密、私钥加密、共享密钥加密，是密码学中的一类加密算法。这类算法在加密和解密时使用相同的密钥，或是使用两个可以简单地相互推算的密钥。
常见的对称加密算法有XOR、DES、3DES、AES、Blowfish、IDEA、RC4等。

我们可以看下 openssl 命令下支持的对称加密方式

image-20180802130404943

Base64

Base64编码在 web 编程中比较常用，可以简单的加密和解密，对安全性要求不高的可以使用。该加密算法不需要密钥。

1
2
3
4
5
6
7
8
9
10
import (
	"encoding/base64"
)
func base64Encode(src []byte) []byte {
	return []byte(base64.StdEncoding.EncodeToString(src))
}

func base64Decode(src []byte) ([]byte, error) {
	return base64.StdEncoding.DecodeString(string(src))
}

XOR 异或算法

异或算法是一种非常简单高效的算法。

XOR运算的定义是：两个值相同时，返回false，否则返回true。也就是说，XOR可以用来判断两个值是否不同。它还有个奇妙的特性：如果对一个值连续做两次 XOR，则会返回该值本身。

1
2
3
4
5
// 第一次 XOR
1010 ^ 1111 // 0101

// 第二次 XOR
0101 ^ 1111 // 1010

这个特性可以用户信息的加解密：

1
2
cipherText	= message XOR key     //加密
message 	= cipherText XOR key  //解密

从上面的公式我们可以看出：

  1. 异或加密使用的加密密钥和解密密钥都是同一个，因此它属于对称加密算法。
  2. 由于异或加密是对信息的每个字节逐个比特进行异或运算，因此它属于流加密算法。
  3. 异或加密是通过比特位一个个的进行异或运算来进行的，对于密钥key 的长度有一定的要求。如果密钥 key 比信息 message 短，则 key 高位需要补齐0，这会导致 message 的高位与0异或后没有发生改变，也就是说多出来的部分没有被加密。因此要保证异或加密的安全性，密钥 key 必须长于要加密的信息，这限制了异或加密的使用场景。

AES 算法

AES 高级解密算法，是当年美国联邦政府采用的加密标准，其本质算法名称叫Rijndael加密算法，被 AES 标准采用。这个标准用来替代原先的DES算法，已经被多方分析且广为全世界所使用。

AES 算法基于排列和置换运算。排列是对数据位置重排，置换是将一个数据单元替换为另一个。AES 使用几种不同的方法来执行排列和置换运算。它可以使用128、192 和 256 位密钥，并且用 128 位（16字节）分组加密和解密数据。迭代加密使用一个循环结构，在该循环中重复置换和替换输入数据。

下面我们看看 golang 中的 AES 包的使用。

1
func NewCipher(key []byte) (cipher.Block, error)

该函数返回称为 Block 的结构(可以看出 AES 是块加密算法)，key 可以是16字节、24字节、32字节，分别对应了 AES-128、AES-192、AES-256。Block 的结构如下

1
2
3
4
5
6
7
8
9
10
11
12
type Block interface {
        // BlockSize returns the cipher's block size.
        BlockSize() int

        // Encrypt encrypts the first block in src into dst.
        // Dst and src must overlap entirely or not at all.
        Encrypt(dst, src []byte)

        // Decrypt decrypts the first block in src into dst.
        // Dst and src must overlap entirely or not at all.
        Decrypt(dst, src []byte)
}

从注释可以看到，这个结构只能加密或者解密数据的第一个块，因此对于数据长度大于block size 的情况，还需要进一步处理。这里引入密码学中的块密码的工作模式(mode of operation)的概念，它是指使用同一个密钥对多于一块的数据进行加密，并保证其安全性；它描述了加密每一数据块的过程，并常常使用基于一个通常称为初始化向量(IV)的附加输入值以进行随机化，以保证安全。常见的模式有ECB，CBC，OFB，CFB，CTR和XTS等。

我们以常见的 CBC 和 CFB 模式为例来看看如何使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
import (
	"bytes"
	"crypto/cipher"
	"crypto/aes"
	"crypto/rand"
	"fmt"
)

//CBC 需要补齐不足的块
func AesCBCEncrypt(text, key []byte) ([]byte, error) {
	block, err := aes.NewCipher(key)
	if err != nil {
		return nil, err
	}
	text = PKCS5Padding(text, aes.BlockSize)
	// text = ZeroPadding(text, aes.BlockSize)
	
	// The IV needs to be unique, but not secure. Therefore it's common to
	// include it at the beginning of the ciphertext.
	ciphertext := make([]byte, aes.BlockSize + len(text))
	iv := ciphertext[:aes.BlockSize]
	//生成随机 iv 值
	if _, err := io.ReadFull(rand.Reader, iv); err != nil {
		panic(err)
	}
	
	mode := cipher.NewCBCEncrypter(block, iv)
	mode.CryptBlocks(ciphertext[aes.BlockSize:], text)
	//iv 和加密后的密文一起返回
	return cipherText, nil
}

//CBC 需要补齐不足的块
func AesCBCDecrypt(cipherText, key []byte) ([]byte, error) {
	block, err := aes.NewCipher(key)
	if err != nil {
		return nil, err
	}
	if len(cipherText) < aes.BlockSize {
        panic("ciphterText too short")
	}
	//密文前一部分为初始化向量 iv，无需保密
	iv := cipherText[:aes.BlockSize]
	cipherText = cipherText[aes.BlockSize:]
	
	// CBC mode always works in whole blocks.
	if len(cipherText) % aes.BlockSize != 0 {
		panic("cipherText is not a multiple of the block size")
	}
	
	mode := cipher.NewCBCDecrypter(block, iv)
	// CryptBlocks can work in-place if the two arguments are the same.
    mode.CryptBlocks(cipherText, cipherText)
	cipherText = PKCS5UnPadding(cipherText)
	// cipherText = ZeroUnPadding(cipherText)
	return cipherText, nil
}

func ZeroPadding(ciphertext []byte, blockSize int) []byte {
	padding := blockSize - len(ciphertext)%blockSize
	padtext := bytes.Repeat([]byte{0}, padding)
	return append(ciphertext, padtext...)
}

func ZeroUnPadding(origData []byte) []byte {
	length := len(origData)
	unpadding := int(origData[length-1])
	return origData[:(length - unpadding)]
}

func PKCS5Padding(ciphertext []byte, blockSize int) []byte {
	padding := blockSize - len(ciphertext)%blockSize
	padtext := bytes.Repeat([]byte{byte(padding)}, padding)
	return append(ciphertext, padtext...)
}

func PKCS5UnPadding(origData []byte) []byte {
	length := len(origData)
	// 去掉最后一个字节 unpadding 次
	unpadding := int(origData[length-1])
	return origData[:(length - unpadding)]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
import (
	"bytes"
	"crypto/cipher"
	"crypto/aes"
	"crypto/rand"
	"fmt"
)

func AesCFBEncrypt(text, key []byte) ([]byte, error) {
	block, err := aes.NewCipher(key)
	if err != nil {
		return nil, err
	}
	
	// The IV needs to be unique, but not secure. Therefore it's common to
	// include it at the beginning of the ciphertext.
	ciphertext := make([]byte, aes.BlockSize + len(text))
	iv := ciphertext[:aes.BlockSize]
	//生成随机 iv 值
	if _, err := io.ReadFull(rand.Reader, iv); err != nil {
		panic(err)
	}
	
	stream := cipher.NewCFBEncrypter(block, iv)
	stream.XORKeyStream(ciphertext[aes.BlockSize:], text)
	//iv 和加密后的密文一起返回
	return ciphertext, nil
}

func AesCFBDecrypt(cipherText, key []byte) ([]byte, error) {
	block, err := aes.NewCipher(key)
	if err != nil {
		return nil, err
	}
	if len(cipherText) < aes.BlockSize {
        panic("ciphterText too short")
	}
	//密文前一部分为初始化向量 iv，无需保密
	iv := cipherText[:aes.BlockSize]
	cipherText = cipherText[aes.BlockSize:]
	
	stream := cipher.NewCFBDecrypter(block, iv)

	// XORKeyStream can work in-place if the two arguments are the same.
	stream.XORKeyStream(cipherText, cipherText)
	return cipherText, nil
}

从上面代码可知，如果待加密的长度正好被整除，即不需要padding，实际处理时其实是做了全补足，否则是没法去去掉padding内容，因为补的长度被放置在最后一个字节，前面最少补1个字节，最多补blockSize个字节。

RC4算法

RC4（来自Rivest Cipher 4的缩写）是一种流加密算法，密钥长度可变。 它加解密使用相同的密钥，因此也属于对称加密算法。 RC4是有线等效加密（WEP）中采用的加密算法，也曾经是TLS可采用的算法之一。

RC4算法的基本原理是先根据 key 和伪随机算法得到辅助加密用的和明文等长的 SBox，然后将 SBox 和明文进行逐字节异或XOR得来。由于RC4算法加密是采用的XOR，所以，一旦子密钥序列出现了重复，密文就有可能被破解。

目前 RC4算法已经被破解，不再推荐使用。

非对称加密算法

非对称加密算法使用两把完全不同但又是完全匹配的一对钥匙：公钥和私钥。在使用不对称加密算法时，只有使用匹配的一对公钥和私钥，才能完成对明文的加密和解密过程。这对于对称加密算法来说，又安全了一步。除了加解密之外，非对称算法还可以用于数字签名，数字签名是一种用于验证对方身份的技术。

具体使用时，遵循以下规则

  • 加密应用，使用公钥加密，私钥解密
  • 签名应用，使用私钥签名，公钥验证

下面介绍下常用的非对称加密算法。

RSA 算法

RSA算法基于大数因子分解难题，其核心问题是欧拉定理，是目前唯一被广泛接受并实现的通用公开加密算法。这种算法非常可靠，密钥越长，它就越难破解。根据已经披露的文献，目前被破解的最长RSA密钥是768个二进制位。也就是说，长度超过768位的密钥，还无法破解（至少没人公开宣布）。因此可以认为，1024位的RSA密钥基本安全，2048位的密钥极其安全。

RSA加密的大致流程是

  1. 乙方生成两把密钥（公钥和私钥）。公钥是公开的，任何人都可以获得，私钥则是保密的。

  2. 甲方获取乙方的公钥，然后用它对信息加密。

  3. 乙方得到加密后的信息，用私钥解密。

如果公钥加密的信息只有私钥解得开，那么只要私钥不泄漏，通信就是安全的。在实际使用中，一般选择 1024 位的密钥即可。

ECC 算法

ECC，全称 Elliptic-curve cryptography，基于解决椭圆曲线离散对数问题的困难性上。ECC 相对于其他非对称加密方式的主要优势是其密钥更小(最小密钥长度 RSA1024位，ECC 160位)，并且提供更高的安全性，但是其加解密花费的时间相对其他要长。

下面是基于 golang 官方 elliptic 库封装的 ECC 算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
type GoECDH struct {
    elliptic.Curve
}

func NewGoECDH(curve elliptic.Curve) *GoECDH {
    if curve == nil {
        curve = elliptic.P256()
    }
    return &GoECDH{
        Curve: curve,
    }
}

func (ge *GoECDH) GenerateKeys() (pub []byte, priv []byte, err error) {
    p, x, y, e := elliptic.GenerateKey(ge.Curve, rand.Reader)
    if e != nil {
        err = e
        return
    }
    pub = elliptic.Marshal(ge.Curve, x, y)
    priv = p
    return
}

func (ge *GoECDH) MakeSecret(pub []byte, priv []byte) []byte {
    x, y := elliptic.Unmarshal(ge.Curve, pub)
    secret, _ := ge.Curve.ScalarMult(x, y, priv)
    return secret.Bytes()
}
参考资料

维基百科经典密码

XOR 加密简介

golang中 AES 加密详解

密码学简介与Golang的加密库Crypto的使用