Diffie-Hellman

Diffie-Hellman密钥交换。

基于离散对数困难问题。

ElGamal

基于离散对数问题。

密钥生成

1.选取足够大的素数p保证p-1存在很大的素因子，使得在$Z_p$上求解离散对数问题是困难的

2.选取$Z_p ^*$的生成元g

3.随机选取整数k满足$0≤k≤p-2$，并计算$g^k\equiv y\ (mod\ p)$

公钥为{$p,g,y$}，私钥为{$k$}。

加密

选取一个随机整数$r\in Z_{p-1}$，得到密文$(y_1,y_2)=(g^rmod\ p,my^rmod\ p)$，其中m为要发送的消息（明文）。

解密

解密时，通过私钥k计算$(y_1^k)^{-1}y_2mod\ p=(g^{rk})^{-1}my^rmod\ p=m$.

参考CTF WIKI

Paillier Cryptosystem

密钥生成

一般过程：

1.随机选择两个大素数p,q满足$gcd(pq,(p-1)(q-1))=1$，当p,q长度相同时一定有该结论

2.计算$n=pq，\lambda=lcm(p-1,q-1)=(p-1)(q-1)/gcd(p-1,q-1)$

3.随机选取整数$g,0<g<n^2$

4.$L(x)=(x-1)/n$

5.计算$\mu=(L(g^\lambda(mod\ n^2)))^{-1}\ (mod\ n)$

6.公钥为（n，g），私钥为（$\lambda，\mu$）

特殊情况：

通常，为简便，我们参数选取如下：

1.$g=n+1$

2.$\lambda=\varphi(n)$

3.$\mu=\varphi(n)^{-1}\ (mod\ n)$

加密

1.m为要发送的消息（明文），满足$0≤m<n$

2.随机选取r，使得$gcd(r,n)=1$

3.密文$c:c=g^m\cdot r^n\ (mod\ n)$

解密

$m=(L(c^\lambda\ (mod\ n^2))\cdot\mu)\ (mod\ n)$

同态性质

$D(E(m_1,r_1)\cdot E(m_2,r_2))\ (mod\ n^2)=m_1+m2\ (mod\ n$)

$D(E(m,r)^k\ mod\ n^2)=km\ mod\ n$

攻击方法

• 同态性质攻击

• 选择明文攻击

  参考：一些密码系统 - Coinc1dens’ Diary

DSA System

与前面的不同，DSA算法是一种数字签名算法，一般不用于加解密

密钥生成

1.选择合适的哈希函数，一般选择SHA-1

2.选择密钥的长度L和N，这两个值决定了签名的安全程度。一般来说L为64的倍数，且$512≤L≤1024$，N必须不大于哈希函数H输出的长度

3.选择N比特的素数q

4.选择L比特的素数p，使得$q|p-1$

5.选择满足$g^k\equiv1\ mod\ p$的最小正整数k为q的g（即g的阶为q）。在这里，我们可以通过计算$g\equiv h^{p-1\over q}\ mod\ p$来得到g，其中$1<h<p-1$.

6.选择私钥x，$0<x<q$，计算$y\equiv g^x\ mod\ p$

公钥为（p,q,g,y)，私钥为(x).

签名

签名步骤：

1.选择随机整数k作为临时密钥,$0<k<q$

2.计算$r\equiv(g^k\ mod\ p)\ mod\ q$

3.计算$s\equiv(H(m)+xr)k^{-1}\ mod\ q$

签名结果为（r，s）

验证

验证步骤：

1.计算辅助量，$w\equiv s^{-1}\ mod\ q$

2.计算辅助量，$u_1\equiv H(m)w\ mod\ q$

3.计算辅助量，$u_2\equiv rw\ mod\ q$

4.计算$v\equiv (g^{u_1}y^{u_2}\ mod\ p)\ mod\ q$

5.如果有$v=r$，则验证成功

攻击方法

k泄露

如果我们知道了k，那么我们可以获取私钥为：

$$x\equiv r^{-1}(ks-H(m))\ mod\ q$$

k共享

如果在两次签名过程使用了同一个k，这时我们可以攻击。

假设签名的消息为$m_1,m_2$，显然，两者的r值相同，我们还有：

$$s_1\equiv (H(m_1)+xr)k^{-1}\ mod\ q$$ $$s_2\equiv (H(m_2)+xr)k^{-1}\ mod\ q$$

化为：

$$s_1k\equiv H(m_1)+xr$$ $$s_2k\equiv H(m_2)+xr$$

两式相减

$$k(s_1-s_2)\equiv H(m_1)-H(m_2)\ mod\ q$$

此时我们可以解出k，进一步可以解出x

进阶攻击方法

MSB泄露攻击（HNP问题的方法），借助格和LLL算法，待补充

Shamir’s Secret Sharing Algorithm

基于拉格朗日插值法（也可理解为方程组的秩）

(m,n)门限方案指的是任意持有一部分密钥的m个人都能解密，而任何少于m个人都不能解密

参考链接：一些密码系统 - Coinc1dens’ Diary

参考

本文参考：

CTF WIKI

一些密码系统 - Coinc1dens’ Diary