密码学算法综述

25 11 月, 2021

密码学算法综述

算法分类

密码学是个非常庞大的学科，我们经常听见各种名词，今天就来好好梳理一下。

在密码学中，常见的算法主要有几种：

加解密算法

加解密的作用，是保护数据的隐私性。

这类算法基本流程是一方把数据加密，公开传输，另一方可以把接受到的数据还原

常见的是对称加密和非对称加密。

对称加密是双上方都持有相同的密钥，加密方采用该密钥加密，解密方也采用该密钥解密
非对称加密的数学依据是解可逆运算的难题(专业术语叫Trapdoor, 想象一个捕鼠机，进去容易，出去难)。比如a*b=c运算很简单，但拥有c，要想知道a和b就很难。专业的数学理论是hidden subgroup problem 。非对称加密则需要公私钥对，是加密方采用公钥加密，解密方采用私钥解密

2. 签名算法

签名算法的作用，是保护数据的完整性和合法性，即验证两个东西：

一是完整性。接收到数据没有被篡改，是发送者原本发送的数据
二是合法性。确保接收到的数据，的确来自合法的发送者

签名的算法和加解密的算法不同之处在于，签名算法并不保护数据的隐私，即不存在加密或者解密操作

比如有一段信息，签名方执行签名算法之后，得到信息以及签名结果。

验证方得到签名结果和信息之后，运行签名算法，能够判断该签名结果是合法的。

在这个过程中，不存在加解密动作，只需要判断签名结果是否合法

密钥交换算法

在加解密算法中提到，如果是对称加密，需要双方拥有相同的密钥。这个过程往往是通信的其中一方随机产生密钥，然后把该密钥告知对方，这就涉及了密钥交换的方式

一种方式是人工交换，这是传统的线下交换方式

但并不是总可以人工交换，在很多场景下，我们需要通过网络交换，此时就需要一种安全的密钥交换算法，来确保该密钥不可被窃取

签名算法

RSA

RSA (Rivest–Shamir–Adleman)。
RSA是一种非对称加密体系。内部包括两种算法：加解密算法，数字签名算法

意味着RSA可以用于加解密，也可以用于数字签名。

但RSA不直接使用在大部分的加解密环境中，主要是很慢，而且加密的数据有限，比如使用得最多的RSA版本 PKCS#1 v1.5。RSA的key为1024位，最多能加密117个bytes,而且加密后的数据比原数据还长，为128bytes,且RSA是固定长度，对长度不足的消息需要padding, 容易出错。

常见的加解密场景种使用RSA是用于对称加密的密钥交换，即通讯双方往往采用对称加密，但是双方通过RSA交换对称加密的密钥

RSA签名算法应用比较广泛，常常和DSA进行比较

RSA算法利用的是大数据的质数分解难题。即factoring problem

RSA从1994年开始，被广泛的使用，经受住了时间的考验

https://en.wikipedia.org/wiki/RSA_(cryptosystem)

DSA

DSA (Digital Signature Algorithm)。DSA是单纯的数字签名算法，不能用于加解密

RSA需要哈希算法辅助，得明确指定hash算法

RSA的计算基于模幂（modular exponentiation）和离散对数（Discrete logarithm）。

计算模幂很容易，但是通过模幂的结果计算离散对数则很难

DSA签名算法由 ElGamal signature scheme签名算法变化而来， ElGamal signature algorithm很少在实际种使用。在1980年的时候，Schnorr signatures签名算法产生，是一个高效简介的算法，但是受专利保护不能广泛使用，于是美国联邦政府开发了一个类似的算法，叫做ElGamal signature algorithm，进而成为后面的DSA。

https://en.wikipedia.org/wiki/Digital_Signature_Algorithm#Operation
https://crypto.stackexchange.com/questions/64826/why-ecdsa-has-its-form/64852#64852

RSA vs DSA

RSA和DSA都可以用于数据签名算法，二者都是非对称密码学，都需要产生公私钥对，技术上面：

DSA uses Discrete logarithm. DSA采用离散对数
RSA uses Integer Factorization. RSA采用大整数的质数因子分解

DSA在签名的运算快于RSA, 但是验证的运算慢于RSA，如果对签名的速度有要求，可以采用DSA。比如在一些c/s,b/s架构中，验证者往往是强大的服务器，不介意运算的代价，而签名者往往是运算能力较差的客户端，需要较快的签名速度

安全性方面，RSA的位数比DSA更长，相对而言RSA会比DSA安全

Schnorr signature

Schnorr signature algorithm是一种签名算法，以简单和高效出名，签名的字数更短，基于离散对数问题

https://en.wikipedia.org/wiki/Schnorr_signature

Schnorr signature是高效的签名算法，2008前一直受到版权保护，因此没有大规模应用。

DSA签名算法就是对标Schnorr signature，可以理解为DSA是弱化版Schnorr signature

该算法和椭圆曲线的结合是EdDSA，EdDSA是一个scheme，即一种算法思想，并不是某种具体的实现，广泛使用的具体的实现是Ed25519。采用的哈希算法是SHA-512 (SHA-2) ，椭圆曲线是Curve25519曲线

EdDSA

EdDSA是Schnorr signature签名算法基于ECC的变种，属于ECC椭圆曲线加密范畴，采用的椭圆曲线类型为twisted Edwards curves

EdDSA是一个scheme，即一种算法思想，并不是某种具体的实现，广泛使用的具体的实现是Ed25519。采用的哈希算法是SHA-512 (SHA-2) ，椭圆曲线是Curve25519曲线

EdDSA另一个实现是Ed448。

EdDSA从效率和安全性上来说，据说都胜过ECDSA，是最佳选择

https://en.wikipedia.org/wiki/EdDSA

ECDSA

椭圆曲线数字签名算法（ECDSA）中的EC指的是Elliptic Curve,即底层理论以ECC密码学为基础，DSA 指的是数字签名算法。即DSA数字签名流程算法在ECC上的实现

ECDSA是ECC与DSA的结合，整个签名过程与DSA类似，所不一样的是签名中采取的底层数学为ECC

ECDSA比RSA有明显的优势就是在同等安全等级下，所需要的位数更少

ECDSA vs RSA vs EdDSA

当今数字签名算法的主流就是这三种。

RSA最为古老，使用广泛，缺点就是密钥位数随着安全等级而增加，优点也一样，随着位数增加，安全等级增加，如果不想冒任何风险，使用很长位数的RSA是好的选择

ECDSA是DSA的变种，也就是ElGamal的变种，基于ECC，所需要的位数比RSA更少，被比特币使用。ECDSA曾经在PlayStation 3上面被hack，比特币也经常被盗，ECDSA和DSA一样，会因为随机数问题RNG受到攻击，不推荐使用

EdDSA也基于ECC, 是Schnorr signature的变种，而由于ElGamal是Schnorr signature的山寨版，显然EdDSA会高效简洁，EdDSA的安全性也比ECDSA更高。但EdDSA也被爆出了攻击问题

总的来说，选择RSA或者EdDSA，抛弃DSA和ECDSA。

https://crypto.stackexchange.com/questions/64826/why-ecdsa-has-its-form/64852#64852
https://crypto.stackexchange.com/questions/58380/ecdsa-eddsa-and-ed25519-relationship-compatibility
https://research.kudelskisecurity.com/2017/10/04/defeating-eddsa-with-faults/
https://www.anquanke.com/post/id/167018
https://xz.aliyun.com/t/2718
https://goteleport.com/blog/comparing-ssh-keys/
https://askubuntu.com/questions/363207/what-is-the-difference-between-the-rsa-dsa-and-ecdsa-keys-that-ssh-uses

数学理论基础

各种密码学算法都是基于一定的数学理论基础，下面大致描述对应的概念

Integer factorization

大数据的质数分解难题:把质数相乘得到结果简单，但从结果推算质数因子则很难

https://en.wikipedia.org/wiki/Integer_factorization

discrete logarithm

Discrete Logarithm Problem & Modular Exponentiation

离散对数和模幂问题在于，计算模幂很容易，但是通过模幂的结果计算离散对数则很难

https://en.wikipedia.org/wiki/Discrete_logarithm

ECC以及Elliptic Curve Discrete Logarithm Problem

ECC指Elliptic-curve cryptography。是基于椭圆曲线数学理论的密码学。和前面的大质数因子和离散对数问题一样，也是Trapdoor function

简单的说，前面的算法，一开始都是以自然数为基础进行研究的，研究其离散对数特性，质数特性。后来人们发现，不只是自然数，某些特定的数字群体，也具备类似的加法特性，离散对数特性，于是把原本基于自然数的算法迁移到该特定群体上，形成新的变种。目前比较主流的数字群体是椭圆曲线

ECC以椭圆曲线理论为基础，利用有限域上椭圆曲线的点构成的Abel群离散对数难解性，实现加密、解密和数字签名。将椭圆曲线中的加法运算与离散对数中的模乘运算相对应，就可以建立基于椭圆曲线的对应密码体制

ECC中参与运算的数据，是椭圆曲线上的点，这也是为什么叫做Elliptic Curve。ECC以离散对数问题位基础，其中的难题，在于该阿贝尔群的加法运算：

Q=n*p

已知n和p，计算Q很容易，但是已知Q和p，很难计算n

ECC是一种数学密码学基础，如果上层算法是基于离散对数难题的，就可以把离散对数算法替换为ECC，比如ECC和DSA结合，成为ECDSA数字签名算法，ECC和DH组合，形成ECDH密钥交换算法

由于在安全性、加解密性能、网络消耗方面有较大优点，ECC加密算法大有取代RSA成为下一代主流加密算法的趋势。现在ECC应用范围很广，在TLS、区块链（比特币、以太坊等等）、SM2国密算法、证书、银行政府机构等许多方面都有大量应用

Elliptic-curve

ECC(Elliptic-curve cryptography)需要选择一条曲线作为基础，知名的椭圆曲线有：

secp256r1
secp384r1
secp521r1

密钥交换算法

Diffie–Hellman

DH算法是一种密钥交换算法。基本思路是乘积之和相等：

A, B明文传输一个共享值
A产生自己的随机数a，B产生随机数b
A把a*c发送给B，B把b*c发送给A
A把收到的结果乘以a,得到b*c*a。B同理，最终的结果b*c*a就是双方协商的私钥

但这只是基本思路，实际的DH算法采用了离散对数的运算。

但DH算法的弱点在于共享值v, 这个共享值是当作明文传输的，当被第三方截获后，就会遭受中间人攻击。

中间人攻击(Man-in-the-middle active attack)是指有一个中间人T,他收到了v之后，冒充B和A通信，再冒充A和B通信。中间人攻击的根源在于A,B之间没有身份认证，无法知道自己通讯的对象是否合法，解决方案是采用证书。

ECDH

基于ECC的密钥交换算法。ECDH是DH算法在ECC基础上的实现.

注意的是ECC为基础的算法不能直接进行加解密运算，因此基于ECC加解密常见的做法位混合型加解密（hybrid encryption schemes ），即首先通过ECDH交换密钥，然后进行对称加密

https://cryptobook.nakov.com/asymmetric-key-ciphers/ecc-encryption-decryption

PSK

Pre-Shared Key。

就是【预先】让通讯双方共享一些密钥（通常是【对称加密】的密钥）的算法。所谓的【预先】，就是说，这些密钥在 TLS 连接尚未建立之前，就已经部署在通讯双方的系统内了。
这种算法用的不多，它的好处是：

不需要依赖公钥体系，不需要部属 CA 证书。
不需要涉及非对称加密，TLS 协议握手（初始化）时的性能好于前述的 RSA 和 DH。
更多介绍可以参见维基百科 https://en.wikipedia.org/wiki/Pre-shared_key

密钥协商的步骤：

在通讯【之前】，通讯双方已经预先部署了若干个共享的密钥。
为了标识多个密钥，给每一个密钥定义一个唯一的 ID
协商的过程很简单：客户端把自己选好的密钥的 ID 告诉服务端。
如果服务端在自己的密钥池子中找到这个 ID，就用对应的密钥与客户端通讯；否则就报错并中断连接。

PSK 与 RSA 具有某种相似性 — — 既可以用来搞“密钥协商”，也可以用来搞“身份认证”。
所以，PSK 可以跟 DH（及其变种）进行组合。例如：DHE-PSK、ECDHE-PSK。

关于 PSK 的更多细节，可以参见 RFC4279

https://www.cnblogs.com/yungyu16/p/13332882.html

SRP

Secure Remote Password.

这个算法有点类似PSK — — 只不过 client/server 双方共享的是密码（password）而不是密钥（key）。该算法采用了一些机制（盐/salt、随机数）来防范“嗅探/sniffer”或“字典猜解攻击”或“重放攻击”。
这个算法应该用得很少 — — OpenSSL 直到2012年才开始支持该算法。

具体可见RFC2945

前向保密（perfect forward secrecy FPS）

假设有一天，攻击者拿到了 RSA 的私钥，就可以用这个私钥解开历史通讯数据。这是个问题，人们希望有种解决方案，即便是私钥被盗，历史数据也不应该被泄露。这种安全机制叫做perfect forward secrecy FPS。

FPS的基本思路是，每一次交流的数据，都采用临时密钥，Ephemeral。

RSA很难应用在FPS场景，It’s very expensive to generate a new RSA key-pair for each connection. RSA用于保存长期密钥比较好使。

相反DH系列产生临时算法就表现很好。DH算法天生就是密钥交换的，每次都采用不同的公共值，沟通临时密钥即可。

满足FPS场景的DH算法叫做DHE, ECC版本的叫做ECDHE

DH vs DHE vs ECDH vs ECDHE vs RSA

这几种都可以用于做密钥交换，DH系列是正儿八经做密钥交换的，RSA是通过加解密的方式可以交换密钥，也就说不是专业做密钥交换的，且RSA应对FPS比较吃力，RSA用于专业做签名比较靠谱。

因此，实际场景中，常见的密钥交换选择是：

ECDHE > DHE > ECDH > DH > RSA

但众所周知，DH系列不进行身份验证，会遭受中间人攻击，因此常常配合签名算法使用。当 DH 与 RSA 配合使用，称之为“DH-RSA”，与 DSA 配合则称为“DH-DSA”，以此类推。比如ECDHE-RSA，就是RSA用于签名，ECDHE用于密钥交换的组合

常见的组合为：

Ephemeral Diffie Hellman with RSA (DHE-RSA) key exchange
Elliptic Curve Ephemeral Diffie Hellman with RSA (ECDHE-RSA) key exchange
Elliptic Curve Ephemeral Diffie Hellman with ECDSA (ECDHE-ECDSA) key exchange
Pre Shared Key with Diffie Hellman (DHE-PSK) key exchange
Pre Shared Key with Elliptic Curve Diffie Hellman (ECDHE-PSK) key exchange
https://crypto.stackexchange.com/questions/59417/why-is-rsa-preferred-over-diffie-hellman-if-theyre-both-used-to-establish-share

哈希算法

哈希算法最为简单，用于保证数据的完整性，基本思路是把消息，通过算法把输入变为固定长度的输出，该输出结果有唯一性，且不可回溯。

常见的哈希算法为MD系列和SHA系列

对称加密算法

对称加密道理很好理解，即加密和解密，都使用相同的密钥

DES

对称加密的一种标准。Data Encryption Standard – designed at IBM

DES只是一种标准，具体的实现也叫做DES或者叫做DEA (Digital Encryption Algorithm). DES现在并不认为是安全的，被淘汰

Triple DES

Triple DES (3DES or TDES。即在加密过程中，把DES算法重复三次。因为一次DES不够安全，重复三次加密增加复杂度

https://en.wikipedia.org/wiki/Triple_DES

AES

AES – Advanced Encryption Standard,用于取代DES

其他概念

MAC

Message authentication code,和数字签名作用类似，都是为了保证消息的完整性和合法性

但是不同之处在于，数字签名使用公私钥。MAC要求签名方和验证方都使用相同的私钥，也就是私钥要共享。但MAC有Non-repudiable问题，也就是双方都有私钥，无法确定消息到底是哪一方签发的

MAC的实现有HMAC，OMAC, CCM, GCM等

MAC,hash和数字签名都是保证信息的完整性，比较如下：

ryptographic primitive | Hash |    MAC    | Digital
Security Goal           |      |           | signature
------------------------+------+-----------+-------------
Integrity               |  Yes |    Yes    |   Yes
Authentication          |  No  |    Yes    |   Yes
Non-repudiation         |  No  |    No     |   Yes
------------------------+------+-----------+-------------
Kind of keys            | none | symmetric | asymmetric
                        |      |    keys   |    keys

Digital Signature = Hash of the message is encrypted with the private key of the sender.
HMAC = Hash of the message is encrypted with the symmetric key.

Ref

https://stackoverflow.com/questions/2841094/what-is-the-difference-between-dsa-and-rsa
https://stackoverflow.com/questions/1722181/how-to-determine-certificate-type-from-file
https://rakhesh.com/infrastructure/notes-on-cryptography-ciphers-rsa-dsa-aes-rc4-ecc-ecdsa-sha-and-so-on/
https://stackoverflow.com/questions/10471009/how-does-the-man-in-the-middle-attack-work-in-diffie-hellman
https://www.ssl2buy.com/wiki/diffie-hellman-rsa-dsa-ecc-and-ecdsa-asymmetric-key-algorithms
https://www.tutorialspoint.com/cryptography/index.htm

其他

Posted by:

李无知