GM（Goldwasser-Micali）同态加密
Goldwasser-Micali (GM) 加密方案是第一个证明为 CPA 安全的公钥加密方案，其安全性依赖于从合数模的二次非剩余中区分二次剩余困难性假设。
密钥生成
用户随机生成两个大素数 $p$ 和 $q$，计算 $n=pq$，$z$ 是模 $n$ 的二次非剩余中的随机数。系统公钥 $pk=(n,z)$，系统私钥 $sk=(p,q)$。
加密
明文空间是 $\{0,1\}$，对于明文 $x\in\{0,1\}$，加密方选取秘密随机数 $r\in Z_n^{*}$，利用系统公钥 $pk$ 计算密文$E(x)=r^2z^x\bmod n$。
解密
对于密文 $E(x)$，判断 $E(x)$ 是否为模 $n$ 的二次剩余，若 $E(x)$ 是模 $n$ 的二次剩余，则明文 $D(E(x))=0$； 若 $E(x)$ 不是模 $n$ 的二次剩余，则 $D(E(x))=1$。
GM加密系统的安全性是基于模 $n$ 的二次剩余问题。对于私钥的拥有者，知道大整数 $n$ 的因子分解，求解模 $n$ 的二次剩余问题是容易的；而对于攻击者，无法获知 $n$ 的因子分解，求解模 $n$ 的二次剩余问题是困难的，继而保证了该加密方案的安全性。
1 | from Crypto.Util.number import long_to_bytes |
ElGamal加密
ElGamal加密算法是一个基于迪菲-赫尔曼密钥交换的非对称加密算法。它在1985年由塔希尔·盖莫尔提出。GnuPG和PGP等很多密码学系统中都应用到了ElGamal算法。ElGamal加密算法可以定义在任何循环群G上。它的安全性取决于G上的离散对数难题。
密钥生成
随机选择一个满足安全要求的大素数 $p$，并生成有限域 $Z_{p}$。的一个生成元 $g\in Z_{p}^{*}$；
选一个随机数 $x\;(1<x<p-1)$，计算 $y\equiv g^{x} \pmod p$，则公钥为 $(y,g,p)$，私钥为 $x$。
加密
与RSA密码体制相同，加密时首先将明文比特串分组，使得每个分组对应的十进制数小于$p$，即分组长度小于$\log_2p$，然后对每个明文分组分别加密。具体过程分为如下几步：
- 得到接收方的公钥 $(y,g,p)$；
- 把消息 $m$ 分组为长度为 $L\;(L<\log_2 p)$ 的消息分组 $m=m_1m_2\dots m_t$；
- 对第 $i$ 块消息 $(1\leq i\leq t)$ 随机选择整数 $r_i\;(1<r_i<p-1)$；
- 计算 $c_i\equiv g^{r_i}\pmod p,\;c_i^\prime\equiv m_iy^{r_i} \pmod p\;(1\leq i\leq t)$；
- 将密文 $C=(c_1,c_1^\prime)(c_2,c_2^\prime)\dots(c_t,c_t^\prime)$ 发送给接收方。
解密
- 接收方收到的密文 $C=(c_1,c_1^\prime)(c_2,c_2^\prime)\dots(c_t,c_t^\prime)$；
- 使用私钥 $x$ 和解密算法 $m_i \equiv ({c_i^\prime}({c_i^x})^{-1}) \pmod p \; (1\leq i\leq t)$ 进行计算；
- 得到明文 $m=m_1m_2\dots m_t$。
ElGamal加密过程需要两次模指数运算和一次模乘积运算，解密过程需要模指数运算，求逆运算和模乘积运算各一次。每次加密运算需要选择一个随机数，所以密文既依赖于明文，又依赖于选择的随机数，故对于同一个明文，不同的时刻生成的密文不同。另外，ElGamal加密使得消息扩展了两倍，即密文的长度是对应明文长度的两倍。
Paillier同态加密
Paillier密码，于1999年由Pascal Paillier发明，是一种用于公钥加密的概率非对称算法。该算法具有加法同态的性质；这意味着，仅给出公钥和 $m_1,m_2$ 加密，可以计算出 $m_1 + m_2$ 。
密钥生成
- 随机选择两个大质数 $p,q$ 满足 $\gcd(pq,(p-1)(q-1))=1$。此属性保证两个质数长度相等；
- 计算 $n=pq$ 和 $\lambda=\text{lcm}(p-1,q-1)$；
- 选择随机整数 $g(g\in \mathbb{Z}_{n^2}^{*}) $，使得满足 $n$ 整除 $g$ 的阶（$0\lt g \lt n^2$）；
- 定义 $L(x)=\cfrac{x-1}{n}$；
- 计算 $\mu=(L(g^\lambda \bmod n^2))^{-1} \bmod n$；
- 公钥为 $(n,g)$，私钥为 $(\lambda,\mu)$。
简化版
$g=n+1$
$\lambda=\varphi(n)=(p-1)(q-1)$
$\mu=\varphi(n)^{-1}\bmod n$
加密
- $m$ 为原文（$0\leq m \lt n$）；
选择随机数 $r(0 \lt r \lt n,r \in \mathbb{Z}_{n^2}^{*})$，且 $\gcd(r,n)=1$；
加密：$c=g^m \cdot r^n\bmod n^2$。
解密
解密：$m=L(c^\lambda \bmod n^2)\cdot \mu \bmod n$。
性质
$D(E(m_1,r_1) \cdot E(m_2,r_2) \bmod {n^2})=m_1+m_2 \bmod n$
$D(E(m_1,r_1) \cdot g^{m_2} \bmod {n^2})=m_1+m_2 \bmod n$
$D(E(m_1,r_1)^{m_2} \bmod {n^2})=m_1m_2 \bmod n$
$D(E(m_2,r_2)^{m_1} \bmod {n^2})=m_1m_2 \bmod n$
$D(E(m,r)^{k} \bmod {n^2})=km \bmod n$
$D(E(m,r) \cdot (1+n)^k \bmod {n^2})=m+k \bmod n$
Merkle-Hellman背包加密（Knapsack）
1977年，Merkle与Hellman合作设计了使用背包算法，该算法提出后密码学界提出了很多背包型加密算法。
其工作原理是：假定甲想加密，则先产生一个较易求解的背包问题，并用它的解作为专用密钥；然后从这个问题出发，生成另一个难解的背包问题，并作为公共密钥。如果乙想向甲发送报文，乙就可以使用难解的背包问题对报文进行加密，由于这个问题十分难解，所以一般没有人能够破译密文；甲收到密文后，可以使用易解的专用密钥解密。
但是，在它发表几年后，就找到了攻破它的方法。即使如此，它仍然代表着一类很难问题的算法。
加密
选择任何一个超递增集 $\{s_1,s_2,…,s_n\}$。
陷门由任意大于 $\sum_{i}s_i$ 的素数 $p$ 和任意小于 $p$ 的整数 $a$ 组成，这两个数和集合 $\{s_1,s_2,…,s_n\}$ 都是保密的。
公开的整数集是 $\{t_1,t_2,…,t_n\}$ ，其中 $t_i=a_i \cdot s_i \pmod p$。
二进制明文 $(b_1,b_2,…,b_n)$ 的加密操作为 $y=\sum_{i}b_it_i$，整数 $y$ 是密文。
解密
找到 $a^{-1} \pmod p$。因为 $p$ 是质数， $a^{-1} \pmod p$ 一定存在。计算 $a^{-1}y \pmod p$。
得到 $a^{-1}y \pmod p$ 这使得：
$a^{-1}y=a^{-1}\sum_{i}b_it_i \pmod p=\sum_{i}b_i(a^{-1}as_i) \pmod p=\sum_{i}b_is_i$
因为集合 $\{s_1,s_2,…,s_n\}$是超递增集，所以很容易定位明文位。
★注：
Knapsack系统的密度为：
$d = \cfrac{n}{\log_2(max\{a_i\})}$
基于子集和问题，MH密码系统是最开始出现的一种密度比较低的Knapsack密码系统。很快Shamir等人提出了一系列的攻击方式，包括丢番图逼近，LLL等方法（$d<0.9408$）。虽然这个密码系统被攻破了，新的Knapsack系统诞生了，这种密码系统的密度变高了，$a_i$ 值变小了，而且加密的明文的二进制位中1的数量也很小。
新的密码系统更加难以破解，也称之为HardKnapsack系统，不过后来密码学家们还是发现了攻击方法，我们称之为low-weight attack。
Schroeppel-Shamir Algorithm
时间复杂度,空间复杂度均为 $O(\cfrac{n}{2})$
The Howgrave-Graham–Joux Algorithm
时间复杂度 $O(0.337n)$，空间复杂度 $O(0.256n)$
总体来说，这两种算法是基于分治和mitm的思想进行攻击的。
Lagarias and Odlyzko’s Method / CJLOSS Method
参考：Lattice Reduction Attack on the Knapsack Type Cryptosystem
构造格：
$\left(\begin {array}{c} b_0 \newline b_1 \newline \vdots \newline b_n \newline b_{n+1} \end{array} \right) =\left(\begin {array}{c} 1 & 0 & \cdots & 0 & Nk_0 \newline 0 & 1 & \cdots & 0 & Nk_1 \newline \vdots & \vdots & \ddots & \vdots & \vdots \newline 0 & 0 & \cdots & 1 & Nk_n \newline 0 & 0 & \cdots & 0 & Nk_{n+1} \end{array} \right) $
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16M = Matrix.identity(n)
last_row = [0 for x in keys]
M_last_row = Matrix(ZZ, 1, len(last_row), last_row)
ct =
last_col = keys[:]
last_col.append(ct)
M_last_col = Matrix(ZZ, len(last_col), 1, last_col)
M = M.stack(M_last_row)
M = M.augment(M_last_col)
X = M.LLL()
target = X[0][:-1]
ans = [-k for k in target]
对于密度比较高的Knapsack密码系统，在1的数量确定情况下，可以尝试分段爆破。
参考论文：Improved Generic Algorithms for Hard Knapsacks
- 常规解密脚本
1 | from sage.all import * |
- 泄露部分明文空间的降维处理
1 | ###Sage |
子集合问题 转化为 求解SVP/CVP+Lattice Reduction Algorithm
参考：
Crypto Research: Solving Subset Sum Problem by Lattice Reduction
1 | import re |
Benaloh加密
密钥生成
假定块大小为 $r$，每个明文信息块大小在 $[0,r)$ 范围内。
- 选择两个大质数 $p=rp’+1$ 和 $q$ ，满足 $\gcd(p’,r)=\gcd(q-1,r)=1$；
- 计算 $n=pq$ 及 $\varphi(n)=(p-1)(q-1)$；
- 选择 $0 \leq y \lt n$，满足 $y^{\varphi(n)/r} \not\equiv 1 \pmod n$；
- 计算 $x=y^{\varphi(n)/r} \bmod n$，公钥为 $(y,n)$，私钥为 $(\varphi,x)$。
加密
假设要加密的信息 $m \in [0,r)$：
- 选择一个数 $u \in [0,n)$；
- 计算 $c=y^mu^r \bmod n$ 即为 $m$ 的密文。
解密
假设要解密的信息 $c$：
- 计算 $a=c^{\varphi(n)/r} \bmod n$；
- DLP求解满足 $x^m \equiv a \pmod n$ 的 $m$，即 $m=\log_x(a)$。
参考
1 | from Crypto.Util.number import long_to_bytes |
LUC-RSA加密
Lucas数列（卢卡斯数列）
递推关系
给定两个整数 $P$ 和 $Q$，满足：$P^2-4Q \ne 0$，
第一类卢卡斯数列 $U_n(P,Q)$ 定义：
$U_0(P,Q)=0 \\ U_1(P,Q)=1 \\ U_n(P,Q)=P \cdot U_{n-1}(P,Q) - Q \cdot U_{n-2}(P,Q), n>1$
第二类卢卡斯数列 $V_n(P,Q)$ 定义：
$V_0(P,Q)=2 \\ V_1(P,Q)=P \\ V_n(P,Q)=P \cdot V_{n-1}(P,Q) - Q \cdot V_{n-2}(P,Q), n>1$
代数关系
特征方程：$x^2-Px+Q=0$，判别式：$D=P^2-4Q$，根：$a=\cfrac{P+\sqrt{D}}{2},b=\cfrac{P-\sqrt{D}}{2}$。
卢卡斯数列的项可用 $a$ 和 $b$ 的项定义：
$U_n = \cfrac{a^n-b^n}{a-b} = \cfrac{a^n-b^n}{\sqrt{D}}$
$V_n = a^n + b^n$
密钥生成
设 $p,q$ 是两个奇素数，$N=pq$。
$e \in \mathbb{Z}_N$，且 $\gcd(e,(p-1)(p+1)(q-1)(q-1))=1$。
卢卡斯数列 $V_n(M,1) = M \cdot V_{n-1} - V_{n-2}$，即 $P=M,Q=1$。（更一般情况见paper）
公钥为：$(N,e)$。
加密
$C=V_e(M,1) \pmod N$，对任意信息 $M \in \mathbb{Z}_N$。
解密
解密密钥 $d$，$ed \equiv 1 \pmod {S(N)}$，
$S(N)=\text{lcm}\left(p-\left (\cfrac{D}{p} \right),p-\left (\cfrac{D}{q} \right)\right)$，$D=C^2-4$，
其中 $\left(\cfrac{D}{p} \right)= \begin{cases} 1,& \exists x, x^2 \equiv D \pmod {p} \\ 0,& p \mid D \\ -1, & \text{other} \end{cases}$ 为勒让德(Legendre)符号。
$M=V_d(C,1) \pmod N$。
参考
LUC-RSA:
A new attack on three variants of the RSA cryptosystem
Cryptanalysis of RSA-type cryptosystems based on Lucas sequences, Gaussian integers and elliptic curves
1 | #法1，快速矩阵幂 |
1 | #法2，存储vd |
1 | #法3，William's p+1算法优化vd |
DSA数字签名
密钥生成
- 选择一个合适的哈希函数，目前一般选择SHA1，也可以选择强度更高的哈希函数 $H$；
- 选择密钥的长度 $L$ 和 $N$，这两个值决定了签名的安全程度。在最初的DSS（Digital Signature Standard ）中建议 $L$ 必须为64的倍数，并且 $512≤L≤1024$，当然也可以更大。$N$ 大小必须不大于哈希函数 $H$ 输出的长度。FIPS 186-3给出了一些建议的 $L$ 和 $N$ 的取值例子：$(1024, 160),(2048, 224), (2048, 256),(3072, 256)$。
- 选择 $N$ 比特的素数 $q$；
- 选择 $L$ 比特的素数 $p$，使得 $p-1$ 是 $q$ 的倍数；
- 选择满足 $g^k \equiv 1 \pmod p$ 的最小正整数 $k$ 为 $q$ 的 $g$，即在模 $p$ 的背景下，$\mathrm{ord}(g)=q$ 的 $g$。即 $g$ 在模 $p$ 的意义下，其指数次幂可以生成具有 $q$ 个元素的子群。这里可以通过计算 $g \equiv h^{\frac{p−1}{q}} \pmod p$ 来得到 $g$，其中 $h \in (1,p−1)$ 。
- 选择私钥 $x \in (0,q)$，计算 $y \equiv g^x \pmod p$。
- 公钥为 $(p,q,g,y)$，私钥为 $(x)$。
签名
选择随机整数数 $k \in (0,q)$ 作为临时密钥；
计算 $r \equiv (g^k \bmod p) \pmod q$；
计算 $s \equiv (H(m)+xr)k^{-1} \pmod q$。
签名结果为 $(r,s)$。需要注意的是，这里使用了哈希函数对消息进行了哈希处理。
验证
- 计算辅助值 $w \equiv s^{-1} \pmod q$；
- 计算辅助值 $u_1 \equiv H(m)\cdot w \pmod q$；
- 计算辅助值 $u_2 \equiv r\cdot w \pmod q$；
- 计算 $v \equiv (g^{u_1}y^{u_2} \bmod p) \pmod q$；
- 如果 $v$ 与 $r$ 相等，则校验成功。
攻击
$k$ 复用（共享 $k$）
如果在两次签名的过程中共享了 $k$，就可以进行攻击。
假设签名的消息为 $m_1,m_2$，显然两者的 $r$ 的值一样，此外
$s_1 \equiv (H(m_1)+xr)k^{-1} \pmod q$
$s_2 \equiv (H(m_2)+xr)k^{-1} \pmod q$
这里除了 $x$ 和 $k$ 不知道剩下的均知道，联立有 $k(s_1-s_2) \equiv (H(m_1)-H(m_2)) \pmod q$，
此时即可解出 $k$，进一步可以解出 $x$。
$k$ 部分泄露
参考：Recovering cryptographic keys from partial information, by example
Elgamal数字签名
密钥生成
- 选取一个足够大的素数 $p$（十进制位数不低于160），便于在 $\mathbb{Z}_p$ 上求解DLP是困难的；
- 选取生成元 $g \in (0,p)$；
- 随机选取整数 $d \in [0,p-2]$，并计算 $g^d \equiv y \pmod p$；
- 公钥为 $(p,g,y)$，私钥为 $(d)$。
签名
A选取随机数 $k \in (0,p-1)$，且 $\gcd(k,p-1)=1$，对消息进行签名：
$\mathrm{sig}(m,k)=(r,s)$
其中：
$r \equiv g^k \pmod p$
$s \equiv (m-dr)k^{-1} \pmod {p-1}$。
验证
如果 $g^m \equiv y^rr^s \pmod p$，那么验证成功，否则验证失败。
攻击
$k$ 复用（共享 $k$）
如果签名者复用了随机数 $k$ ，那么攻击者就可以轻而易举地计算出私钥。
假设目前有两个签名都是使用同一个随机数进行签名的。那么有：
$r \equiv g^k \pmod p$
$s_1 \equiv (m_1-dr)k^{-1} \pmod {p-1}$
$s_2 \equiv (m_2-dr)k^{-1} \pmod {p-1}$,
进而有 $k(s_1-s_2) \equiv (m_1-m_2) \pmod {p-1}$，
$s_1,s_2,m_1,m_2,p$ 均已知，容易算出 $k$，进而根据 $s$ 的计算方法得到私钥 $d \equiv (m-ks)r^{-1} \pmod {p-1}$。
构造验证
单参数
选择 $e \in (1,p-1)$，令 $r=g^ey \bmod p$，$s=-r \bmod (p-1)$，有 $m=es \bmod (p-1)$ 满足验证。
双参数
选择 $e,v \in (1,p-1),\gcd(v,p-1)=1$，令 $r=g^ey^v \bmod p$，$s=-rv^{-1} \bmod (p-1)$，有 $m=es \bmod (p-1)$ 满足验证。
Shamir密钥分享算法
Shamir 密钥分享算法最早是由 Shamir 和 Blackly 在 1970 年基于 Lagrange 插值和矢量方法提出的。
算法有 2 个重要参数：$k$ 和 $n$。$n$ 表示将明文加密为 $n$ 个 $\text{Shadow}$，$k$ 表示 至少需要 $k$ 个 $\text{Shadow}$ 才可以恢复出明文。
加密
若明文为 $s$，$s \in \mathbb{Z}_p$，$p$ 为一个大素数。在 $\text{GF}(p)$ 任取 $k-1$ 个随机数： $a_1,a_2,\cdots,a_{k-1}$，构造如下多项式：
$f(x)=s+a_1x+a_2x^2+\cdots+a_{k-1}x^{k-1} \pmod p$
任取 $n$ 个不同的数：$x_1,x_2,\cdots,x_n$，分别代入多项式得到 $n$ 个密钥对：
$(x_1,f(x_1)),(x_2,f(x_2)),\cdots,(x_n,f(x_n))$
将这 $n$ 个密钥对分发给 $n$ 个持有者。
解密
得到了 $n$ 个密钥对 $(x_1,f(x_1)),(x_2,f(x_2)),\cdots,(x_n,f(x_n))$ 后，可以列出以下在 $\text{GF}(p)$ 上的方程组：
$\left\{\begin{array}{c} s+a_1x_1+a_2x_1^2+\cdots+a_{k-1}x_1^{k-1}=f(x_1) \\ s+a_1x_2+a_2x_2^2+\cdots+a_{k-1}x_2^{k-1}=f(x_2) \\ \vdots \\ s+a_1x_n+a_2x_n^2+\cdots+a_{k-1}x_n^{k-1}=f(x_n) \end{array}\right.$
然后就可用 Lagrange 插值算法求出 $s$ 了。
1
2
3
4
5#python-1
from sslib import shamir
data = {'required_shares': 2, 'prime_mod': 'AQAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAEp', 'shares': ['1-MEwx7cz+C01rL8H0Hhz2EIgHjWYXVcL81uITmRha674=', '2-YJhj22+ntS1s80CT9b6Y7ayc52baTFGNRpPUyLxtaf8=', '3-4SRZDcshiZTVRJ7nVY8NDq83JOsnZtPm', '4-wTDHtrT7CO1wej3TpQHep/XHm2hgOW6uJfdXKASSZoE=', '5-8Xz5pFekss1yPbxzfKOBhRpc9WkjL/0+lakYV6ik5MI=']}
print(shamir.recover_secret(shamir.from_base64(data)).decode('ascii'))1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51#python-2
from Crypto.Util.number import *
import gmpy2
def product(vals, p):
return reduce(lambda x, y: x * y % p, vals)
def lagrange_interpolate(x, x_s, y_s, p):
n = len(x_s)
assert n == len(set(x_s)) # x_s must be distinct
num = []
den = []
for i in range(n):
others = x_s[:i] + x_s[i+1:]
num.append(product((x - o for o in others), p))
den.append(product((x_s[i] - o for o in others), p))
dens = product(den, p)
res = 0
for i in range(n):
tmp1 = ((num[i] * dens % p) * y_s[i]) % p
tmp2 = tmp1 * gmpy2.invert(den[i], p) % p
res = (res + tmp2) % p
res = res * gmpy2.invert(dens, p) % p
return res
def shamir_sharing_encode(s, k, n, p):
a = [getRandomInteger(Nbits) for _ in range(k-1)]
res = []
for _ in range(n):
x = getRandomInteger(Nbits)
fx = s
for i in range(k-1):
fx = (fx + a[i] * pow(x, i+1, p)) % p
res.append((x, fx))
return res
def shamir_sharing_decode(shares, p):
x_s, y_s = zip(*shares)
return lagrange_interpolate(0, x_s, y_s, p)
Nbits = 1024
secret = bytes_to_long('it_is_the_top_secret')
p = getPrime(Nbits)
k = 513
n = 513
shares = shamir_sharing_encode(secret, k, n, p)
s = shamir_sharing_decode(shares, p)
print long_to_bytes(s)
# 2s1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23#Sage
P = PolynomialRing(GF(p), 'x')
ret = P(0)
for x, y in shares:
r = P(1) * y
for xx, yy in shares:
if x != xx:
r = r * P((0 - xx) / (x - xx))
ret = ret + r
print ret
# 19s
#Sage算系数
P = PolynomialRing(GF(p), 'x')
ret = P(0)
for x, y in shares:
r = P(1) * y
for xx, yy in shares:
if x != xx:
r = r * P('(x - %d) / (%d - %d)' % (xx, x, xx))
ret = ret + r
print ret[0]
# 154s除了 Lagrange 插值，也可以用矩阵。
可以将上面的方程组化为以下在 $\text{GF}(p)$ 上的矩阵乘法：
$\left(\begin {array}{c} 1 & x_1 & x_1^2 & \cdots & x_1^{k-1} \\ 1 & x_2 & x_2^2 & \cdots & x_2^{k-1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & x_n & x_n^2 & \cdots & x_n^{k-1} \end{array} \right) \times \left(\begin {array}{c} s \\ a_1 \\ \vdots \\ a_{k-1} \end{array} \right) = \left(\begin {array}{c} f(x_1) \\ f(x_2) \\ \vdots \\ f{x_n} \end{array} \right)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20#Sage矩阵乘法
k = 513
n = 513
x, y = zip(*shares)
array_1 = []
for i in range(n):
for j in range(k):
array_1.append(pow(x[i], j, p))
A = matrix(GF(p), n, k, array_1)
array_2 = []
for i in range(n):
array_2.append(y[i])
B = matrix(GF(p), n, 1, array_2)
a = A.solve_right(B)
print a[0][0]
# 266s也可以将之视为多元同余方程组：
$\left\{\begin{array}{c} s+a_1x_1+a_2x_1^2+\cdots+a_{k-1}x_1^{k-1} \equiv f(x_1) \pmod p \\ s+a_1x_2+a_2x_2^2+\cdots+a_{k-1}x_2^{k-1} \equiv f(x_2) \pmod p \\ \vdots \\ s+a_1x_n+a_2x_n^2+\cdots+a_{k-1}x_n^{k-1} \equiv f(x_n) \pmod p \end{array}\right.$
记系数矩阵的行列式为：
$\Delta = \left \vert \begin {array}{c} 1 & x_1 & x_1^2 & \cdots & x_1^{k-1} \\ 1 & x_2 & x_2^2 & \cdots & x_2^{k-1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & x_n & x_n^2 & \cdots & x_n^{k-1} \end{array} \right \vert \neq 0$
要求的是 $s$，因此将行列式第一列换为同余方程的值：
$\Delta_0 = \left \vert \begin {array}{c} f(x_1) & x_1 & x_1^2 & \cdots & x_1^{k-1} \\ f(x_2) & x_2 & x_2^2 & \cdots & x_2^{k-1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ f(x_n) & x_n & x_n^2 & \cdots & x_n^{k-1} \end{array} \right \vert \neq 0$
由克拉默法则得：
$s \equiv \Delta^{-1}\Delta_0 \pmod p$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20#Sage
fx_num = 513
x, y = zip(*shares)
array_1 = []
for i in range(fx_num):
for j in range(fx_num):
array_1.append(pow(x[i], j, p))
delta = matrix(GF(p), fx_num, fx_num, array_1).determinant()
array_2 = [_ for _ in array_1]
for i in range(fx_num):
array_2[i*fx_num] = y[i]
delta_0 = matrix(GF(p), fx_num, fx_num, array_2).determinant() % p
delta_inverse = inverse_mod(int(delta), p)
res = delta_inverse * delta_0 % p
print res
# 1200s但是如果维数很大，直接解行列式会很慢。观察发现 $\Delta$ 其实是旋转后的范德蒙行列式。$\Delta_0$ 是旋转后的范德蒙行列式的变形，第一行不是全 1，而是 $f(x)$。可以按第一行展开，余子式中将每一列除以该列元的一次方，可化为范德蒙行列式。计算速度会快非常多。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28#Sage
fx_num = 513
x, y = zip(*shares)
delta = 1
for i in range(1, fx_num):
for j in range(0, i):
t = x[i] - x[j]
delta = (delta * t) % p
delta_0 = 0
for i in range(fx_num):
tmp_x = [_ for _ in x]
tmp_x.pop(i)
yuzishi = -y[i] if (i+1+1) % 2 else y[i]
for j in range(fx_num-1):
yuzishi = (yuzishi * tmp_x[j]) % p
for j in range(1, fx_num-1):
for k in range(0, j):
t = tmp_x[j] - tmp_x[k]
yuzishi = (yuzishi * t) % p
delta_0 = (delta_0 + yuzishi) % p
delta_inverse = gmpy2.invert(delta, p)
res = delta_inverse * delta_0 % p
print res
# 224s攻击
如果在加密 2 段明文 $s_1,s_2$ 过程中，使用相同的随机数 $a$ 以及大素数 $p$，还能得到同一个 $x$ 对应的两个 $f(x)$，如果知道一个明文 $s_1$ 的情况下，可以算出另一个明文。
在 $\text{GF}(p)$ 上：$s_1 + a_1x + a_2x^2 + a_3x^3 + … + a_{k-1}x^{k-1} = f(x)_1$
设：$A = a_1x + a_2x^2 + a_3x^3 + … + a_{k-1}x^{k-1}$
即：
$s_1 + A = f(x)_1 \\ s_2 + A = f(x)_2$
因此： $s_2 = f(x)_2 - f(x)_1 + s_1$
如果不知道两个明文的情况下，但两明文有一定的线性关系，也可以算出两明文。
若 $s_2 = as_1 + b$，则有同余方程组：
$\left\{ \begin{array}{c} s_1 + A - f(x)_1 \equiv 0 \pmod p \\ s_2 + A - f(x)_2 \equiv 0 \pmod p\\ as_1 + b - s_2 \equiv 0 \pmod p \end{array}\right.$
1
2
3
4
5
6
7
8
9
10
11
12
13#Sage
a = 99999999
b = 123456
PR.<s1,s2,A> = PolynomialRing(Zmod(p))
f1 = s1 + A - y1
f2 = s2 + A - y2
f3 = a * s1 + b - s2
Fs = [f1, f2, f3]
I = Ideal(Fs)
B = I.groebner_basis()
print 's1 =', ZZ(-B[0](0, 0, 0))
print 's2 =', ZZ(-B[1](0, 0, 0))
Okamoto-Uchiyama密码系统
1998年由Tatsuaki Okamoto和Shigenori Uchiyama提出的公钥加密算法。
条件：$n=p^2q$
密钥生成
- 生成两个大素数 $p$ 和 $q$；
- 计算 $n=p^2q$；
- 选择一个随机整数 $g \in \{2, \cdots ,n-1\}$ 满足 $g^{p-1} \not\equiv 1 \pmod {p^2}$；
- 计算 $h=g^n \bmod n$。
公钥为 $(n,g,h)$，私钥为 $(p,q)$。
加密
明文 $m<p$ 可以通过公钥 $(n,g,h)$ 加密：
- 选择一个随机整数 $r \in \{1,\cdots,n-1\}$；
- 计算 $c=g^m h^r \bmod n$。
$c$ 即为 $m$ 的密文。
解密
密文 $c$ 可以通过私钥 $(p,q)$ 解密：
- 计算 $a=\cfrac{(c^{p-1} \bmod {p^2})-1}{p}$；
- 计算 $b=\cfrac{(g^{p-1} \bmod {p^2})-1}{p}$；
- 使用扩展欧几里得算法计算 $b$ 的模 $p$ 逆元 $b’=b^{-1} \bmod p$；
- 计算 $m=ab’ \bmod p$。
$m$ 即为 $c$ 的明文。
参考：PoseidonCTF 1st Edition 2020 - discrete log
Schmidt-Samoa密码系统
2005年，Katja Schmidt-Samoa 创建了 Schmidt-Samoa 公钥密码体系。
与 Rabin 类似，它的安全性基于大整数分解的困难性。但 Rabin 解密时会得到四个解，而 Schmidt-Samor 得到的是唯一解。
密钥生成
选取大整数 $p,q$，计算 $N=p^2q$ 作为公钥。
计算 $d=\text{inv}(N,\varphi(pq))$ 作为私钥。
加密
对于小于 $pq$ 的明文 $m$，计算 $c=m^N \bmod N$ 作为密文。
解密
对于密文 $c$，计算 $c^d \bmod pq$，得到密文。
对于 $d$，当 $d=\text{inv}(N,\text{lcm}(p-1,q-1))$ 时，可以证明仍然有极大概率 $2^{N \cdot d} \equiv 2 \pmod {pq}$。
因为 $\text{lcm}(p-1,q-1)$ 已经是 $(p-1)(q-1)$ 非常大的因子，由拉格朗日定理，2生成的子群的阶应该是 $(p-1)(q-1)$ 的因数，所有概率还挺高的。
证明
首先，计算 $\varphi(N)$，由欧拉函数的性质，显然有 $\varphi(N)=\varphi(p^2q)=p(p-1)(q-1)$
于是 $x^{p(p-1)(q-1)} \equiv 1 \pmod N$
尽管公钥、私钥都不包含 $pq$，但可以通过 $(N,d)$ 推出 $pq$，有 $N \cdot d \equiv 1 \pmod {\big((p-1)(q-1)\big)}$
随便选一个数2，来考察 $2^{N \cdot d}$ 在模 $pq$ 时的表现，有 $2^{N \cdot d} \equiv 2^{N \cdot d \bmod {\big((p-1)(q-1)\big)}} \equiv 2 \pmod {pq}$
从而 $pq \mid 2^{N \cdot d}-2$，于是计算 $\gcd(2^{N \cdot d}-2,N)$，即得到 $pq$。
容易发现，这些幂可以在模 $N$ 意义下计算，以节省复杂度。现在 $pq$ 到手，在模 $pq$ 意义下计算 $c^d$，即
$c^d \equiv m^{N \cdot d} \equiv m^{N \cdot d \bmod {\big((p-1)(q-1)\big)}} \equiv m \pmod {pq}$
至此完成解密。
参考：A New Rabin-type Trapdoor Permutation Equivalent to Factoring and Its Applications
