# 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 几个重要的定理

• 若$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})$。

# 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\}$

...

## 3.2 RSA的安全性

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

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

## 3.3 对RSA的攻击

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

### 共模攻击

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

$$re_1 + se_2 = 1$$

### 低指数攻击

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

# 5 椭圆曲线

## 5.1 椭圆曲线上的运算

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

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

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

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

Parametermeaning
CURVEthe 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)
mthe 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 椭圆曲线的优点

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

RSA/SDA5127681024204821000
ECC106132160211600

# 6 密钥分发（Key Distribution）

## 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的原始公钥。