浅谈加密

缘起


一次作业,写一个后端登录系统,涉及到了对用户密码进行加密传输

脑子里突然蹦出来这个RSA 非对称加密算法(也是我接触的第一个加密算法

浅谈


目前加密算法大概可以分为三类

种类加密规则破解方式
对称加密根据一个固定的规则(密钥)进行加密和解密根据密文可以破解密钥,密钥传输时截获密钥
非对称加密两个密钥:公钥和私钥,私钥只保留给自己,公钥交给他人;公钥私钥可以互相加密解密,通常公钥破解难度比私钥小,加密速度比私钥快难以破解
Hash明文到密文不可逆(很难破解)不带盐 hash 可以用彩虹表和碰撞破解,带盐的难以破解

对称加密

对称加密应用很广泛,大多数古典加密也属于对称加密(古典加密通常使用移位置换,例如凯撒密码

缺点也十分明显,双方必须保证密钥严格安全,毕竟加密方式都泄露了那密文就和明文差不多了

甲方制定的密钥必须给乙方才能通信,密钥的传输和保存很难保证安全

非对称加密

这也是本文的重点 RSA 非对称加密

1976 年,两位美国计算机学家 Whitfield Diffie 和 Martin Hellman,提出了一种崭新构思,可以在不直接传递密钥的情况下,完成解密。这被称为Diffie-Hellman密钥交换算法。这个算法启发了其他科学家。人们认识到,加密和解密可以使用不同的规则,只要这两种规则之间存在某种对应关系即可,这样就避免了直接传递密钥。

这种加密方法被称为非对称加密

1977 年,三位数学家 Rivest、Shamir 和 Adleman 设计了一种算法,可以实现非对称加密。这种算法用他们三个人的名字命名,叫做RSA算法。从那时直到现在,RSA 算法一直是最广为使用的"非对称加密算法"。毫不夸张地说,只要有计算机网络的地方,就有 RSA 算法。

你可以发现目前 OpenSSH 使用的就是 RSA 密钥认证,Github,Gitee 等代码托管平台都可以添加 SSH 公钥认证权限

还有语雀的 SSL 证书

Hash

Hash 就是散列函数,加密后的密文长度固定,根据排列组合知识,也就是说密文对应的原文不唯一,也就是说无法被解密

这种加密典型的原文加密到密文容易,密文解密到原文不可能实现(如果能实现就说明宇宙所有事物都能用一串 hash 码表达,也就是无穷可以被定量,这是不可能的)

通常应用场景就是在数据库里储存隐私的 Hash 码

常见的有 SHA 系列,MD5(1996 年后被专家证明出有缺点,对数据安全性较高的建议使用 SHA-2),

根据上文,既然 hash 的输入有无限种可能,而输出只有有限的可能,那么绝对会存在两个明文对应的密文一样,如果两个明文对应的密文一样,这就发生了碰撞

所以,根据这个,破密者可以预先存储一个密文->明文的表,当发现其中某个密文和要破解密文一样,那么即使这个密文对应的明文和破解的密文对应的明文不是一样的,这个明文也能完成真正的明文大多数作用(比如作为密码进行登陆)

储存一个完完整整的密文->明文的散列表是不合理的,这样会占用很多数据库的空间,而且检索起来会变得非常慢

彩虹表采用的就是以时间复杂度来换取空间复杂度的思路

彩虹表前身: 预计算的哈希链 > 约简函数(Reduction Function)

约简函数的定义域和值域刚好和要破译的 Hash 函数相反。也就是说它可以将密文转换成和明文相同格式的内容,但得出来的这个明文不一定计算 Hash 后就和密文一样

过程

储存的时候只需要储存 aaaaaa 和 kiebgt 就可以了,剩下的都可以计算 Hash 和约简来得到 这样就可以省下很大的空间了

和 Hash 一样,约减函数也会发生碰撞,当发生碰撞的时候,两条链就重叠了

如:

A 链: aaa --> 3A8GH --> ehg --> 6J94BD

B 链: bbb --> 4CG8D --> ehg --> 6J94BD

在对 3A8GH 和 4CG8D 计算约简结果时发生了碰撞,得到了相同的 ehg,那么这两条链能储存的信息就变少了,也就浪费了空间

彩虹表

看起来像一个预计算哈希链组成的一个集合

相比于纯预计算哈希链集合

如何使用它们

带盐(salt)

咱吃饭的时候总不能不放盐吧,虽然这里的盐(salt)和真实的盐(NaCl)没有关系,但在某些方面有点类似,(比如都是附加成分?)

计算 Hash 的时候不仅仅就只针对这串明文,给明文带一点其他的元素,比如密码明文加上用户年龄求一次 Hash,这个盐就是年龄 (当然前提你得保密)

盐值就是不确定因素,对每个 Hash 计算可能都不一样

带上了盐值,Hash 规则就变了,破译者还不知道它是按照什么规则变的,自然就无法用彩虹表等方法破译了

RSA 加密过程


浅要分析

RSA 加密原理主要基于目前数学领域对质数的研究匮乏,分解一个很大的数的质因数远远比从质因数得出这个数复杂得多

下面的过程中,P 和 Q 很大时,从 N 分解出 P 和 Q 将非常困难,分解不出来这样就得不到私钥,得不到私钥就破解不了(默认没有其他不用私钥就能破解的方法,至少目前没有)

RSA 从问世这么多年以来,经过无数次验证,攻击考验,始终表现出优异的安全性,所以在非对称加密方向上被广泛使用

简单加密过程

例子

找出 P=3 Q=11 计算得出 N = 33,Φ(N) = 2*10 = 20 公钥 E∈(1,20),不妨取其为 3 计算可得私钥 D=7

加密过程 (以 2 为例) C = 2^3 % 33 = 8 解密过程 M = 8^7 % 33 = 2

代码实现(Golang 为例)

import (
	"crypto/rsa"
	"crypto/rand"
	"crypto/x509"
	"os"
	"encoding/pem"
	"fmt"
)

//生成RSA私钥和公钥,保存到文件中

func GenerateRSAKey(bits int){

	//GenerateKey函数使用随机数据生成器random生成一对具有指定字位数的RSA密钥
	//Reader是一个全局、共享的密码用强随机数生成器
	privateKey, err := rsa.GenerateKey(rand.Reader, bits)

	if err!=nil{
		panic(err)
	}

	//保存私钥
	//通过x509标准将得到的ras私钥序列化为ASN.1 的 DER编码字符串
	X509PrivateKey := x509.MarshalPKCS1PrivateKey(privateKey)

	//使用pem格式对x509输出的内容进行编码
	//创建文件保存私钥
	privateFile, err := os.Create("private.pem")

	if err!=nil{
		panic(err)
	}

	defer privateFile.Close()

	//构建一个pem.Block结构体对象
	privateBlock:= pem.Block{Type: "RSA Private Key",Bytes:X509PrivateKey}

	//将数据保存到文件

	pem.Encode(privateFile,&privateBlock)

	//保存公钥
	//获取公钥的数据
	publicKey:=privateKey.PublicKey

	//X509对公钥编码
	X509PublicKey,err:=x509.MarshalPKIXPublicKey(&publicKey)

	if err!=nil{
		panic(err)
	}

	//pem格式编码
	//创建用于保存公钥的文件
	publicFile, err := os.Create("public.pem")

	if err!=nil{
		panic(err)
	}

	defer publicFile.Close()

	//创建一个pem.Block结构体对象
	publicBlock:= pem.Block{Type: "RSA Public Key",Bytes:X509PublicKey}

	//保存到文件
	pem.Encode(publicFile,&publicBlock)

}

//RSA加密

func RSA_Encrypt(plainText []byte,path string)[]byte{

	//打开文件
	file,err:=os.Open(path)
	if err!=nil{
		panic(err)
	}

	defer file.Close()

	//读取文件的内容
	info, _ := file.Stat()
	buf:=make([]byte,info.Size())
	file.Read(buf)

	//pem解码
	block, _ := pem.Decode(buf)

	//x509解码
	publicKeyInterface, err := x509.ParsePKIXPublicKey(block.Bytes)

	if err!=nil{
		panic(err)
	}

	//类型断言
	publicKey:=publicKeyInterface.(*rsa.PublicKey)

	//对明文进行加密
	cipherText, err := rsa.EncryptPKCS1v15(rand.Reader, publicKey, plainText)

	if err!=nil{
		panic(err)
	}

	//返回密文
	return cipherText

}

//RSA解密

func RSA_Decrypt(cipherText []byte,path string) []byte{

	//打开文件
	file,err:=os.Open(path)
	if err!=nil{
		panic(err)
	}
	defer file.Close()

	//获取文件内容
	info, _ := file.Stat()
	buf:=make([]byte,info.Size())
	file.Read(buf)

	//pem解码
	block, _ := pem.Decode(buf)

	//X509解码
	privateKey, err := x509.ParsePKCS1PrivateKey(block.Bytes)

	if err!=nil{
		panic(err)
	}

	//对密文进行解密
	plainText,_:=rsa.DecryptPKCS1v15(rand.Reader,privateKey,cipherText)

	//返回明文
	return plainText

}

测试

func main(){

 //生成密钥对,保存到文件
 GenerateRSAKey(2048)
 message:=[]byte("hello world")

 //加密
 cipherText:=RSA_Encrypt(message,"public.pem")
 fmt.Println("加密后为:",string(cipherText))

 //解密
 plainText := RSA_Decrypt(cipherText, "private.pem")
 fmt.Println("解密后为:",string(plainText))

}

测试结果

密文,签名,密钥的字符串加密方式

以密文为例,加密后的结果看起来是一团乱码,有很多无法表示的符号,储存时一般对其字符串加密 一般常用 Hex 和 Base64

Hex 字符串加密

hex.DecodeString(s string) // 解密
hex.EncodeToString(src []byte) string // 加密

Base64 字符串加密

base64.StdEncoding.DecodeString(s string) ([]byte, error) // 解密
base64.StdEncoding.EncodeToString(src []byte) string // 加密

AES&DES


非对称加密固然安全,但加密解密开销是很大的,通常上就使用非对称加密来传输对称加密的密钥 key,然后再使用对称加密来加密交流的信息

AES 和 DES 是对称加密中常用的算法 至于具体原理就不能深入了(我不会

贴个链接 AES 原作者论文: https://csrc.nist.gov/csrc/media/projects/cryptographic-standards-and-guidelines/documents/aes-development/rijndael-ammended.pdf

代码实现

可以看到在 golang 中实现 aes 和 des 基本上没区别


// PKCS7Padding 把 ciphertext 补成 blockSize 整数倍
func PKCS7Padding(ciphertext []byte, blockSize int) []byte {
	padding := blockSize - len(ciphertext)%blockSize
	padtext := bytes.Repeat([]byte{byte(padding)}, padding) // 缺多少个字节就补多少个 例:缺5个补5个5
	return append(ciphertext, padtext...)
}

func PKCS7UnPadding(origData []byte) []byte {
	length := len(origData)
	unpadding := int(origData[length-1])   // 拿到最后一个字节(数字),从而得知之前补了多少个字节
	return origData[:(length - unpadding)] // 获取原本未补齐的 origData
}

// AesEncrypt AES加密
func AesEncrypt(origData, key []byte) ([]byte, error) {
	block, err := aes.NewCipher(key) // 通过 key 确定 BlockSize
	if err != nil {
		return nil, err
	}
	blockSize := block.BlockSize()
	origData = PKCS7Padding(origData, blockSize)                // 把 origData 补齐
	blockMode := cipher.NewCBCEncrypter(block, key[:blockSize]) // 通过 BlockSize 确定 BlockMode
	encrypted := make([]byte, len(origData))
	blockMode.CryptBlocks(encrypted, origData)
	return encrypted, nil
}

// AesDecrypt AES解密
func AesDecrypt(encrypted, key []byte) ([]byte, error) {
	block, err := aes.NewCipher(key)
	if err != nil {
		return nil, err
	}
	blockSize := block.BlockSize()
	blockMode := cipher.NewCBCDecrypter(block, key[:blockSize])
	origData := make([]byte, len(encrypted))
	blockMode.CryptBlocks(origData, encrypted)
	origData = PKCS7UnPadding(origData)
	return origData, nil
}

// DesEncrypt DES加密
func DesEncrypt(origData, key []byte) ([]byte, error) {
	block, err := des.NewCipher(key)
	if err != nil {
		return nil, err
	}
	blockSize := block.BlockSize()
	origData = PKCS7Padding(origData, blockSize)
	blockMode := cipher.NewCBCEncrypter(block, key[:blockSize])
	encrypted := make([]byte, len(origData))
	blockMode.CryptBlocks(encrypted, origData)
	return encrypted, nil
}

// DesDecrypt DES解密
func DesDecrypt(encrypted, key []byte) ([]byte, error) {
	block, err := des.NewCipher(key)
	if err != nil {
		return nil, err
	}
	blockSize := block.BlockSize()
	blockMode := cipher.NewCBCDecrypter(block, key[:blockSize])
	origData := make([]byte, len(encrypted))
	blockMode.CryptBlocks(origData, encrypted)
	origData = PKCS7UnPadding(origData)
	return origData, nil
}

速度对比


func TestEncrypt(t *testing.T) {
	aesKey := []byte("1234567812345678") // 密钥是 16 的整数倍
	desKey := []byte("12345678")
	text := []byte("Hello World!")

	start := time.Now()

	aesEncrypt, err := AesEncrypt(text, aesKey)
	if err != nil {
		return
	}
	end1 := time.Now().Sub(start)

	desEncrypt, err := DesEncrypt(text, desKey)
	if err != nil {
		return
	}
	end2 := time.Now().Sub(start)

	fmt.Println(string(aesEncrypt), "用时", end1.Nanoseconds())
	fmt.Println(string(desEncrypt), "用时", end2.Nanoseconds())

	fmt.Println("加密对比", "AES 加密速度是 DES 的", float64(end2.Nanoseconds()) / float64(end1.Nanoseconds()), "")

	aesDecrypt, err := AesDecrypt(aesEncrypt, aesKey)
	if err != nil {
		return
	}
	end3 := time.Now().Sub(start)

	desDecrypt, err := DesDecrypt(desEncrypt, desKey)
	if err != nil {
		return
	}
	end4 := time.Now().Sub(start)

	fmt.Println(string(aesDecrypt), "用时", end3.Nanoseconds())
	fmt.Println(string(desDecrypt), "用时", end4.Nanoseconds())

	fmt.Println("解密对比", "AES 解密速度是 DES 的", float64(end4.Nanoseconds()) / float64(end3.Nanoseconds()), "")

}

咳咳咳,不要在意壁纸

多次加密测试后,AES 的加密速度一般是 DES 的 1.5 ~ 2.5 倍,解密速度倒是没啥区别

参考&引用