一、数学定义

1、原根

$$设n、a为互质的正整数，令a^d\equiv 1 \pmod n，如果用\delta (n,a)表示使该式子成立的最小整数d，此时如果\delta (n,a)=\phi (n)成立，则称a为模n的原根。$$

2、离散对数

$$对整数b、指数p及其原根a，若可找到唯一指数使得b \equiv a^i \pmod p，其中i \in [0,p-1]，则称i为b的以a为基数的离散对$$

二、ELGamal

私钥与公钥****的计算

  1. 随机选取一个大素数p，要求p-1有大素数因子
  2. $$选择一个模p的原根a和整数i有i \in (1,p-1$$
  3. $$计算b \equiv a^i \pmod $$

此时公钥集合(p,a,b)，私钥i

加密过程

  1. $$随机选取证书k,k \in (1,p-1$$
  2. $$计算U \equiv b^k \pmod $$
  3. $$计算C_1\equiv a^k \pmod p$$
  4. $$计算C_2\equiv U*M \pmod p$$

$$得到密文(C_1,C_2$$

解密过程

  1. $$计算V\equiv C_1^i \pmod $$
  2. $$计算M\equiv V^{-1} \pmod $$

三、ECDH

椭圆曲线迪菲-赫尔曼密钥交换 Elliptic Curve Diffie-Hellman key exchange

流程

  1. A和B选择一个椭圆曲线E和一个基点G
  2. A选择一个私钥a，并计算公钥A=aG
  3. B选择一个私钥b，并计算公钥B=bG
  4. A和B交换公钥
  5. 各自计算共享秘密：

A：S=aB=abG B：S=bA=abG 得到同一个点S

通常不会直接把整个点当做AES key，而是取x(S)或整个编码，再过KDF/hash，生成对称密钥

1
key = SHA256(long_to_bytes(S.x)).digest()[:16]

四、ECDSA

椭圆曲线数字签名算法 Elliptic Curve Digital Signature Algorithm

签名过程

  1. $$选取一个椭圆曲线E_p(a,b),基点为G，基点的阶为n，私钥为d，公钥为Q$$
  2. $$随机选择一个随机数k \in [1,n-1]，K=kG=(x_K,y_K)$$
  3. $$计算r=x_K \ne 0 \pmod n ,对明文进行hash: e=H(m) 得到消息摘要$$
  4. $$计算s=k^{-1}(e+dr) \neq 0 \pmod n$$

最终签名为(r,s)

验证流程

  1. $$计算u_1=s^{-1}e \pmod n，u_2=s^{-1}r \pmod n$$
  2. $$计算点P=u_1G+u_2Q=(s^{-1}eG+s^{-1}rQ)=s^{-1}G(e+rd)=kG=K \pmod n $$

当$$r\equiv x_P \pmod n时，签名有效$$

malleability（可塑性）

$$若(r,s)是合法签名，则(r,n-s)通常也是合法签$$

$$因为验证中只用到了s^{-1}，而(n-s)^{-1}\equiv -s^{-1} \pmod n$$

典（k的重复使用）

$$两条不同消息m1,m2用了同一个k签名,得到：(r,s1),(r,s2）$$

由：

$$\begin {cases} s_1=k^{-1}(e_1+dr) \pmod n \ s_2=k^{-1}(e_2+dr) \pmod n \end {cases}$$

得：

$$s_1-s_2=k^{-1}(e_1-e_2) \pmod n$$

$$k=\frac{e_1-e_2}{s_1-s_2} \pmod n $$

$$d=\frac{s_1k-e_1}{r} \pmod n $$

关于hash