1 常见的几种密码体制

• 公钥密码体制（非对称密码体制）：

  • RSA
  • 背包密码体制（提出两年即被破解）
  • Rabin
  • NTRU 基于环的公钥密码系统
  • ECC 基于椭圆曲线
  • SM2
  • DSA（Digital Signature Algorithm）
  • DH（Diffie-Hellman密钥交换）

• 私钥密码体制（对称密码体制）

  • 流密码：RC4
  • 分组密码：DES、RC2、IDEA、3DES、AES、SM4
• 哈希函数：MD5、SHA-1、SHA-2、SM3

2 几个重要的定理

费马小定理

若$p$是素数，$a$是正整数且$gcd(a,p)=1$，则$a^{p-1} \equiv1 \mod{p}$

欧拉函数，设$n$是一正整数，小于$n$且与$n$互素的正整数的个数称为$n$的欧拉函数，记为$\varphi(n)$，

• 若$n$是素数，则$\varphi(n)=n-1$；
• 若$n$是两个素数$p$和$q$的成绩，则$\varphi(n)=\varphi(p) \times \varphi(q)=(p-1)(q-1)$；
• 若$n$有标准分解式$n=p_1^{a_1}p_2^{a_2}\cdots p_t^{a_t}$，则$\varphi(n)=n(1-\frac{1}{p_1})\cdots(1-\frac{1}{p_t})$。

欧拉定理

若 $a$ 和 $n$ 互素，则 $a^{\varphi(n)} \equiv 1 \bmod{n}$

3 RSA

3.1 算法描述

密钥的产生

1. 选择两个大素数$p,q$
2. 计算$n=p \times q,z=(p-1) \times (q-1)$
3. 选取一个整数$e$，满足$1<e<\varphi(n)$，且$gcd(\varphi(n),e)=1$
4. 计算$d$，满足$d\cdot e = \equiv 1 \bmod {\varphi(n)}$，即$d$是$e$在模$\varphi(n)$下的乘法逆元，因$e$与$\varphi(n)$互素，由模运算可知，它的乘法逆元一定存在
5. 公钥为$\{e,n\}$，密钥为$\{d,n\}$

加密

加密时首先将明文比特串分组，使得每个分组对应的十进制数小于$n$，即分组长度小于$\log_2 n$。然后对每个明文分组$m$，做加密运算$c \equiv m^e \bmod{n}$

解密

对密文分组的解密运算为$m = \equiv c^d \bmod{n}$

证明

...

3.2 RSA的安全性

人类的计算能力的提高和分解算法的不断改进是威胁RSA安全性重要的两个因素。

随着人类计算能力的不断提高....满足安全要求的RSA的密钥长度会越来越长。

当前（2024年），RSA的安全密钥长度应不低于2048比特，1024比特长度的密钥已经认为是不安全的了。

需要注意的是，为了保证算法的安全性，$p$和$q$的选取有如下要求：

• $|p-q|$要大

• $p-1$和$q-1$都应该要有大素数的因子。

  • 这是因为RSA算法存在着可能的重复加密攻击法

3.3 对RSA的攻击

RSA存在以下两种攻击，共模攻击和低指数攻击并不是因为算法本身存在缺陷，而是由于参数选择不当造成的。

共模攻击

实现RSA时，为了方便，我们可能会给每个用户共同的模数$n$，虽然加解密密钥不同，然而这样做是不行的。设两个用户的公钥为$e_1$和$e_2$，且$e_1$和$e_2$互素（一般情况下都成立），明文消息为$m$，密文分别是

$$ c_1 \equiv m^{e_1} \pmod n \\ c_2 \equiv m^{e_2} \pmod n $$

敌手截获$c_1$和$c_2$后，可如下恢复$m$。用推广的Euclid算法求出满足

$$ re_1 + se_2 = 1 $$

的两个整数$r$和$s$，其中一个为负，设为$r$。再次用推广的Euclid算法求出$c_1^{-1}$，由此得$(c_1^{-1})^{-r}c_2^s \equiv m \pmod n$

低指数攻击

假定将RSA算法同时用于多个用户（为讨论方便，以下假定3个），然而每个用户的加密指数（即公钥）都很小。设3个用户的模数分别为$n_i(i=1,2,3)$，当$i \neq j$时，$gcd(n_i,n_j)=1$，否则通过$gcd(n_i,n_j)$有可能得出$n_i$和$n_j$的分解。设明文消息是$m$，密文分别是

$$ c_1 \equiv m^3 \pmod {n_1} \\ c_2 \equiv m^3 \pmod {n_2} \\ c_3 \equiv m^3 \pmod {n_3} $$

由中国剩余定理可求出$m^3 \pmod {n_1n_2n_3}$。由于$m^3 < n_1n_2n_3$，可直接由$m^3$开立方根得到$m$。

4 Diffie-Hellman密钥交换

5 椭圆曲线

什么是椭圆曲线

5.1 椭圆曲线上的运算

无穷远点$O$

无穷远点是椭圆曲线运算的单位元（Identity Element），任何点与$O$相加都会的得到自身，即

$$ O + O = O \\ P + O = P $$

加法运算

图一展示了椭圆曲线上的加法运算是如何进行的，连接$P$和$Q$，交于椭圆曲线的$R$点，然后找关于$x$轴与$R$点对称的点$-R$，即$P+Q=-R$。图二展示了两个相同的点如何运算，我们让图一的$P$点无限地趋近于$Q$点，我们会得到一条经过$Q$的切线，如图二所示，与椭圆曲线交于$P$点，找关于$x$轴对称的点$-R$即为所求，$Q+Q=-P$。图三中的$Q=-P$，$P+(-P)=O$，得到无穷远点$O$，说明连接$P$与$-P$会得到一条垂直于$x$轴的直线，该直线与椭圆曲线在无穷远处相交，这个无穷远处相交就自己想象吧。图四说明两个相同的点相加有可能会得到无穷远点$O$。

多倍点运算

多倍点运算其实就是加法运算的延伸，即$nP$定义为$n$个点$P$相加

$$ nP = P + P + \dots + P $$

• RSA密码体制基于有限域上的大素数的分解问题
• Diffie-Hellmen密钥交换和ElGamal密码体制是基于有限域上的离散对数问题
• ECC椭圆曲线密码体制是基于椭圆曲线上的离散对数问题

考虑方程$Q=kP$，其中$P,Q \in E_p(a,b),k<p$，即$P,Q$是椭圆曲线$E_p(a,b)$上的点，则由$k$和$P$易求得$Q$，但由$Q$、$P$求$k$是困难的，这就是椭圆曲线上的离散对数问题。

5.2 椭圆曲线的签名算法（ECDSA - Elliptic Curve Digital Signature Algorithm）

Parameter	meaning
CURVE	the elliptic curve field and equation used
$G$	elliptic curve base point, a point on the curve that generates a subgroup of large prime order n
$n$	integer order of G, means that $n\times G=O$, where $O$ is the identity element.
$d_A$	the private key (randomly selected)
$Q_A$	the public key (calculated by elliptic curve)
m	the message to send

签名生成

The order $n$ of the base point $G$ must be prime. Indeed, we assume that every nonzero element of the ring $\mathbb{Z} /n\mathbb{Z}$ is invertible, so that $\mathbb {Z} /n\mathbb {Z}$ must be a field. It implies that $n$ must be prime.

Alice creates a key pair, consisting of a private key integer $d_{A}$, randomly selected in the interval $[1,n-1]$; and a public key curve point $Q_{A}=d_{A}\times G$. We use $\times$ to denote elliptic curve point multiplication by a scalar.

For Alice to sign a message $m$, she follows these steps:

1. Calculate $e={\textrm {HASH}}(m)$. (Here HASH is a cryptographic hash function, such as SHA-2, with the output converted to an integer.)
   Let $z$ be the $L_{n}$ leftmost bits of $e$, where $L_{n}$ is the bit length of the group order $n$. (Note that $z$ can be greater than $n$ but not longer.)
2. Select a cryptographically secure random integer $k$ from $[1,n-1]$.
3. Calculate the curve point $(x_{1},y_{1})=k\times G$.
4. Calculate $r=x_{1}\,{\bmod {\,}}n$. If $r=0$, go back to step 3.
5. Calculate $s=k^{-1}(z+rd_{A})\,{\bmod {\,}}n$. If $s=0$, go back to step 3.
6. The signature is the pair $(r,s)$. (And $(r,-s \mod n)$ is also a valid signature.)

验证签名

For Bob to authenticate Alice's signature, he must have a copy of her public-key curve point $Q_{A}$. Bob can verify $Q_{A}$ is a valid curve point as follows:

1. Check that $Q_{A}$ is not equal to the identity element $O$, and its coordinates are otherwise valid
2. Check that $Q_{A}$ lies on the curve
3. Check that $n\times Q_{A}=O$

After that, Bob follows these steps:

1. Verify that $r$ and $s$ are integers in $[1,n-1]$. If not, the signature is invalid.
2. Calculate $e={\textrm {HASH}}(m)$, where HASH is the same function used in the signature generation.
3. Let $z$ be the $L_{n}$ leftmost bits of $e$.
4. Calculate $u_1=zs^{-1} \bmod n$ and $u_2=rs^{-1}\,{\bmod {\,}}n$
5. Calculate the curve point $(x_{1},y_{1})=u_{1}\times G+u_{2}\times Q_{A}$. If $(x_1,y_1)=O$ then the signature is invalid.
6. The signature is valid if $r\equiv x_{1}{\pmod {n}}$, invalid otherwise.

Note that an efficient implementation would compute inverse $s^{-1}\bmod n$ only once. Also, using Shamir's trick, a sum of two scalar multiplications $u_{1}\times G+u_{2}\times Q_{A}$ can be calculated faster than two scalar multiplications done independently.

证明

It is not immediately obvious why verification even functions correctly. To see why, denote as $C$ the curve point computed in step 5 of verification,

$C=u_{1}\times G+u_{2}\times Q_{A}$

From the definition of the public key as $Q_{A}=d_{A}\times G$,

$C=u_{1}\times G+u_{2}d_{A}\times G$

Because elliptic curve scalar multiplication distributes over addition,

$C=(u_{1}+u_{2}d_{A})\times G$

Expanding the definition of $u_{1}$ and $u_{2}$ from verification step 4,

$C=(zs^{-1}+rd_{A}s^{-1})\times G$

Collecting the common term $s^{-1}$,

$C=(z+rd_{A})s^{-1}\times G$

Expanding the definition of $s$ from signature generation step 5,

$C=(z+rd_{A})(z+rd_{A})^{-1}(k^{-1})^{-1}\times G$

Since the inverse of an inverse is the original element, and the product of an element's inverse and the element is the identity, we are left with

$C=k\times G$

From the definition of $r$, this is verification step 6.

This shows only that a correctly signed message will verify correctly; many other properties are required for a secure signature algorithm.

5.3 椭圆曲线的优点

与基于有限域上的离散对数问题的公钥体制（如Diffie-Hellman密钥交换和ElGamal密码体制）相比，椭圆曲线密码体制有以下优点：

• 安全性高
• 密钥量小
• 灵活性好。有限域GF(q)一定的情况下

椭圆曲线具有丰富的群结构和多选择性，并可在保持和RSA/DSA体制同样安全性能的前提下大大缩短密钥长度（目前160比特足以保证安全性），因而在密码领域有这广阔的应用前景。下表给出了ECC和RSA/DSA在保持同等安全的条件下所需的密钥长度（单位为比特）。一般情况下，建议RSA密钥长度至少取2048bits满足安全要求，即等价于ECC密钥长度211bits。

RSA/DSA密钥长度(bits)	ECC密钥长度(bits)
512	106
768	132
1024	160
2048（安全）	211（安全）
3072(推荐)	256（推荐）
21000	600

6 密钥分发（Key Distribution）

密码体制	存在的问题	解决方案
公钥密码体制	两个实体间如何通过不信任的网络建立共享密钥的通道	通过可信任的密钥分发中心（KDC - Key Distributed Center）建立密钥交换信道
私钥密码体制	当Alice想获取Bob的公钥，如何能保证得到的一定是Bob的公钥而不是假的呢	通过可信任的证书颁发机构（CA - Certification Authority）

6.1 中间人攻击

6.2 KDC与CA

KDC里面会保存每个人的私钥，即一对相同的钥匙，一把在人的手里，另一把在KDC手里，当Alice想和Bob通信时，Alice用和KDC通信的密钥加密请求 (Alice, Bob)，KDC收到请求后会随机产生一个R1与A的身份信息放在一起，用和Bob通信的密钥加密这段信息，这样Bob就能确认是Alice想和自己通信，并且大家都使用KDC生成的R1来加解密信息。

Bob将公钥提供给CA，然后CA使用自己的私钥$K_{CA}^-$加密Bob的公钥$K_B^+$，生成签名后的公钥；而Alice要想获得Bob的公钥则需要使用CA公钥$K_{CA}^+$解密Bob签名后的公钥，得到Bob的原始公钥。

7 哈希函数

本博客文章除特别声明外，均可自由转载与引用，转载请标注原文出处：http://www.yelbee.top/index.php/archives/152/