其他加密算法

2020-05-13 crypto 算法 ∞ 评论

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$ 的二次剩余问题是困难的，继而保证了该加密方案的安全性。

from Crypto.Util.number import long_to_bytes
import gmpy2
plaintext = ''
with open('output.txt') as f:
	n = int(f.readline())
	for line in f:
		cipher = int(line)
		if gmpy2.jacobi(cipher,n) == -1:
			plaintext += '1'
		else:
			plaintext += '0'
		print(long_to_bytes(int(plaintext,2)))

ElGamal加密

ElGamal加密算法是一个基于迪菲-赫尔曼密钥交换的非对称加密算法。它在1985年由塔希尔·盖莫尔提出。GnuPG和PGP等很多密码学系统中都应用到了ElGamal算法。ElGamal加密算法可以定义在任何循环群G上。它的安全性取决于G上的离散对数难题。

密钥生成
1. 随机选择一个满足安全要求的大素数 $p$ ，并生成有限域 $Z_{p}$ 。的一个生成元 $g\in Z_{p}^{*}$ ；
2. 选一个随机数 $x\;(1<x<p-1)$ ，计算 $y\equiv g^{x} \pmod p$ ，则公钥为 $(y,g,p)$ ，私钥为 $x$ 。
加密
与RSA密码体制相同，加密时首先将明文比特串分组，使得每个分组对应的十进制数小于 $p$ ，即分组长度小于 $\log_2p$ ，然后对每个明文分组分别加密。具体过程分为如下几步：
1. 得到接收方的公钥 $(y,g,p)$ ；
2. 把消息 $m$ 分组为长度为 $L\;(L<\log_2 p)$ 的消息分组 $m=m_1m_2\dots m_t$ ；
3. 对第 $i$ 块消息 $(1\leq i\leq t)$ 随机选择整数 $r_i\;(1<r_i<p-1)$ ；
4. 计算 $c_i\equiv g^{r_i}\pmod p,\;c_i^\prime\equiv m_iy^{r_i} \pmod p\;(1\leq i\leq t)$ ；
5. 将密文 $C=(c_1,c_1^\prime)(c_2,c_2^\prime)\dots(c_t,c_t^\prime)$ 发送给接收方。
解密
1. 接收方收到的密文 $C=(c_1,c_1^\prime)(c_2,c_2^\prime)\dots(c_t,c_t^\prime)$ ；
2. 使用私钥 $x$ 和解密算法 $m_i \equiv ({c_i^\prime}({c_i^x})^{-1}) \pmod p \; (1\leq i\leq t)$ 进行计算；
3. 得到明文 $m=m_1m_2\dots m_t$ 。

ElGamal加密过程需要两次模指数运算和一次模乘积运算，解密过程需要模指数运算，求逆运算和模乘积运算各一次。每次加密运算需要选择一个随机数，所以密文既依赖于明文，又依赖于选择的随机数，故对于同一个明文，不同的时刻生成的密文不同。另外，ElGamal加密使得消息扩展了两倍，即密文的长度是对应明文长度的两倍。

Paillier同态加密

Paillier密码，于1999年由Pascal Paillier发明，是一种用于公钥加密的概率非对称算法。该算法具有加法同态的性质；这意味着，仅给出公钥和 $m_1,m_2$ 加密，可以计算出 $m_1 + m_2$ 。

密钥生成
1. 随机选择两个大质数 $p,q$ 满足 $\gcd(pq,(p-1)(q-1))=1$ 。此属性保证两个质数长度相等；
2. 计算 $n=pq$ 和 $\lambda=\text{lcm}(p-1,q-1)$ ；
3. 选择随机整数 $g(g\in \mathbb{Z}_{n^2}^{*})$ ，使得满足 $n$ 整除 $g$ 的阶（ $0\lt g \lt n^2$ ）；
4. 定义 $L(x)=\cfrac{x-1}{n}$ ；
5. 计算 $\mu=(L(g^\lambda \bmod n^2))^{-1} \bmod n$ ；
6. 公钥为 $(n,g)$ ，私钥为 $(\lambda,\mu)$ 。
- 简化版
  $g=n+1$
  $\lambda=\varphi(n)=(p-1)(q-1)$
  $\mu=\varphi(n)^{-1}\bmod n$
加密
1. $m$ 为原文（ $0\leq m \lt n$ ）；
2. 选择随机数 $r(0 \lt r \lt n,r \in \mathbb{Z}_{n^2}^{*})$ ，且 $\gcd(r,n)=1$ ；
3. 加密： $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)$

M = 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

常规解密脚本

from sage.all import *

pk =  # public key
ct =  # ciphertext
print(ct)
print(len(pk))
n = len(pk)

# Sanity check for application of low density attack
d = n / log(max(pk), 2)
print(CDF(d))
assert CDF(d) < 0.9408

M = Matrix.identity(n) * 2

last_row = [1 for x in pk]
M_last_row = Matrix(ZZ, 1, len(last_row), last_row)

last_col = pk
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.BKZ()

sol = []
for i in range(n + 1):
    testrow = X.row(i).list()[:-1]
    if set(testrow).issubset([-1, 1]):
        for v in testrow:
            if v == 1:
                sol.append(0)
            elif v == -1:
                sol.append(1)
        break

s = sol
print(s)

泄露部分明文空间的降维处理

###Sage
pubkey = [...] 
c = 

#前缀 flag{
prefix = [int(_) for _ in bin(bytes_to_long(b'flag{'))[2:]]
for i in range(len(prefix)):
    c -= prefix[i] * pubkey[i]

#后缀 }
suffix = [int(_) for _ in bin(ord('}'))[2:].rjust(8, '0')]
n = len(pubkey)
for i in range(8):
    c -= pubkey[n - 8 + i] * suffix[i]

#中部md5范围 0-f
elements = []
for i in range(len(prefix), len(pubkey) - 8, 8):
    elements.append(pubkey[i + 1])
    c -= 1 * pubkey[i + 2]
    for j in range(3, 8):
        elements.append(pubkey[i + j])
        
n = len(elements)
A = Matrix(ZZ, n + 1, n + 1)
for i in range(n):
    A[i, 0] = elements[i]
    A[i, i + 1] = 2
A[n, 0] = c
for i in range(1, n + 1):
    A[n, i] = 1
AL = A.BKZ()
mid = None
for line in AL:
    if all(line[i] == 1 or line[i] == -1 for i in range(1, n + 1)):
        if line[1] == 1:
            line = -line
        mid = line[1:]
        break

mid_str = ''
for _ in mid:
    if _ == -1:
        mid_str += '0'
    else:
        mid_str += '1'

flag = ''
j = 0
for i in range(32):
    flag += '0'
    flag += mid_str[j]
    j += 1
    flag += '1'
    for k in range(5):
        flag += mid_str[j]
        j += 1
print(bytes.fromhex(hex(int(flag, 2))[2:]))

子集合问题转化为求解SVP/CVP+Lattice Reduction Algorithm
参考：
WMCTF 2020 - babySum + Sum
Crypto Research: Solving Subset Sum Problem by Lattice Reduction

import re
import random
import multiprocessing as mp
from functools import partial

def check(sol, A, s):
	"""Check whether *sol* is a solution to the subset-sum problem.
	"""
	return sum(x*a for x, a in zip(sol, A)) == s
	
def solve(A, n, k, s, ID=None, BS=22):
	N = ceil(sqrt(n)) # parameter used in the construction of lattice
	rand = random.Random(x=ID) # seed
	
	# 1. Construct the lattice
	# (n+1) * (n+2)
	# 1 0 ... 0 a_0*N N
	# 0 1 ... 0 a_1*N N
	# . . ... . ... .
	# 0 0 ... 1 a_n*N N
	# 0 0 ... 0 s*N k*N
	lat = []
	for i, a in enumerate(A):
		lat.append([1*(j == i) for j in range(n)] + [N*a] + [N])
	lat.append([0]*n + [N*s] + [k*N])
	
	# main loop
	itr = 0
	start_time = cputime()
	while True:
		itr += 1
		
		# 2. Randomly shuffle
		l = lat[::]
		shuffle(l, random=rand.random)
		
		# 3. BKZ!!!
		m = matrix(ZZ, l)
		t_BKZ = cputime()
		m_BKZ = m.BKZ(block_size=BS)
		print(f"n={n} {itr} runs. BKZ running time: {cputime(t_BKZ):.3f}s")
		
		# 4. Check the result
		for i, row in enumerate(m_BKZ):
			if check(row, A, s):
					if row.norm()^2 == k:
						print(f"n={n} After {itr} runs. FIND SVP!!! {row}\n"
						f"Single core time used: {cputime(start_time):.3f}s")
						return True

s = 
A = []
#choose k numbers from n
k = 
n = 
solve_n = partial(solve, A, n, k, s)
CPU_CORE_NUM = 8
with mp.Pool(CPU_CORE_NUM) as pool:
	reslist = pool.imap_unordered(solve_n, range(CPU_CORE_NUM))
	# terminate all processes once one process returns
	for res in reslist:
		if res:
			pool.terminate()
			break

Benaloh加密

密钥生成
假定块大小为 $r$ ，每个明文信息块大小在 $[0,r)$ 范围内。
1. 选择两个大质数 $p=rp’+1$ 和 $q$ ，满足 $\gcd(p’,r)=\gcd(q-1,r)=1$ ；
2. 计算 $n=pq$ 及 $\varphi(n)=(p-1)(q-1)$ ；
3. 选择 $0 \leq y \lt n$ ，满足 $y^{\varphi(n)/r} \not\equiv 1 \pmod n$ ；
4. 计算 $x=y^{\varphi(n)/r} \bmod n$ ，公钥为 $(y,n)$ ，私钥为 $(\varphi,x)$ 。
加密
假设要加密的信息 $m \in [0,r)$ ：
1. 选择一个数 $u \in [0,n)$ ；
2. 计算 $c=y^mu^r \bmod n$ 即为 $m$ 的密文。
解密
假设要解密的信息 $c$ ：
1. 计算 $a=c^{\varphi(n)/r} \bmod n$ ；
2. DLP求解满足 $x^m \equiv a \pmod n$ 的 $m$ ，即 $m=\log_x(a)$ 。
参考
https://mystiz.hk/posts/2021-02-15-dicectf-1/

from Crypto.Util.number import long_to_bytes
from tqdm import tqdm

n = 
y = 
e = 
C = []

p = 
q = 

phi = (p-1) * (q-1)
tmp = phi // e

bounds = (1, e)
F = IntegerModRing(n)
result = []

x = F(pow(y, tmp, n))

for c in tqdm(C):
    a = F(pow(c, tmp, n))
    result.append(bsgs(x, a, bounds))

flag = 0
for i in result[::-1]:
    flag = flag*e + i
flag = long_to_bytes(flag)

print(flag)

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$ 。
参考
一种新的基于 Lucas 序列的公钥密码体制
LUC: A New Public Key System
UMassCTF 2021 - Weird RSA
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
HFCTF 2022 - RRSSAA
RCTF 2022 - easyRSA

#法1，快速矩阵幂
from Crypto.Util.number import long_to_bytes

N=
C=

def ffm(num): # Fermat's Factorization Method.
    if num%2==0: return (2,num/2)
    a=ceil(sqrt(num))
    c=a**2-num
    while is_square(c)==0: a+=1
    b=sqrt(c)
    return (a-b,a+b)

def matpow(mat,power): # Matrix Square-And-Multiply Exponentiation.
    power_rep=bin(power)[3:]
    result=mat
    pcnt=1
    for i in power_rep:     
        result=result*result
        pcnt*=2
        if i=='1':
            result=mat*result
            pcnt+=1
    print(pcnt)
    return result

def decrypt(d): # Decryption.
    Mat=Matrix(Zmod(N),[[C,-1],[1,0]])
    ori=vector(Zmod(N),[C,2])
    return matpow(Mat,d-1)*ori

p,q=ffm(N) 
assert p*q==N
D=(C**2-4)%N
p_leg,q_leg=int((p-kronecker(D,p))%N),int((q-kronecker(D,q))%N)
tn=lcm((p_leg),(q_leg))
d=inverse_mod(0x10001,tn)
assert (0x10001*d)%tn==1
decc,_=decrypt(d)
print(long_to_bytes(decc))

#法2，存储vd
#vd(2n)=vd(n)^2-2
#vd(2n+1)=c*vd(n)^2-vd(n)*vd(n-1)+c
def v(n):
    if n == 0: return 2
    if n == 1: return c
    if n in v_dict.keys(): return v_dict[n]
    if(n % 2 == 0): ret = (pow(v(n // 2), 2, N) - 2) % N
    else: ret = (c * pow(v(n // 2), 2, N) -  v(n // 2) * v((n // 2) - 1) - c) % N
    v_dict[n] = ret
    return ret

#法3，William's p+1算法优化vd
# Williams's p + 1 algorithm
def LUC(c, d, N):
	x = c
	y = (c**2 - 2) % N
	for bit in bin(d)[3:]:
		if bit == '1':
			x = (x*y - c) % N
			y = (y**2 - 2) % N
		else:
			y = (x*y - c) % N
			x = (x**2 - 2) % N
	return x

DSA数字签名

密钥生成
1. 选择一个合适的哈希函数，目前一般选择SHA1，也可以选择强度更高的哈希函数 $H$ ；
2. 选择密钥的长度 $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)$ 。
3. 选择 $N$ 比特的素数 $q$ ；
4. 选择 $L$ 比特的素数 $p$ ，使得 $p-1$ 是 $q$ 的倍数；
5. 选择满足 $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)$ 。
6. 选择私钥 $x \in (0,q)$ ，计算 $y \equiv g^x \pmod p$ 。
7. 公钥为 $(p,q,g,y)$ ，私钥为 $(x)$ 。
签名
1. 选择随机整数数 $k \in (0,q)$ 作为临时密钥；
2. 计算 $r \equiv (g^k \bmod p) \pmod q$ ；
3. 计算 $s \equiv (H(m)+xr)k^{-1} \pmod q$ 。
签名结果为 $(r,s)$ 。需要注意的是，这里使用了哈希函数对消息进行了哈希处理。
验证
1. 计算辅助值 $w \equiv s^{-1} \pmod q$ ；
2. 计算辅助值 $u_1 \equiv H(m)\cdot w \pmod q$ ；
3. 计算辅助值 $u_2 \equiv r\cdot w \pmod q$ ；
4. 计算 $v \equiv (g^{u_1}y^{u_2} \bmod p) \pmod q$ ；
5. 如果 $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数字签名

密钥生成
1. 选取一个足够大的素数 $p$ （十进制位数不低于160），便于在 $\mathbb{Z}_p$ 上求解DLP是困难的；
2. 选取生成元 $g \in (0,p)$ ；
3. 随机选取整数 $d \in [0,p-2]$ ，并计算 $g^d \equiv y \pmod p$ ；
4. 公钥为 $(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$ 了。

#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'))

#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)
# 2s

#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)$

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

#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)$ 。可以按第一行展开，余子式中将每一列除以该列元的一次方，可化为范德蒙行列式。计算速度会快非常多。

#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.$

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

密钥生成
1. 生成两个大素数 $p$ 和 $q$ ；
2. 计算 $n=p^2q$ ；
3. 选择一个随机整数 $g \in \{2, \cdots ,n-1\}$ 满足 $g^{p-1} \not\equiv 1 \pmod {p^2}$ ；
4. 计算 $h=g^n \bmod n$ 。
公钥为 $(n,g,h)$ ，私钥为 $(p,q)$ 。
加密
明文 $m<p$ 可以通过公钥 $(n,g,h)$ 加密：
1. 选择一个随机整数 $r \in \{1,\cdots,n-1\}$ ；
2. 计算 $c=g^m h^r \bmod n$ 。
$c$ 即为 $m$ 的密文。
解密
密文 $c$ 可以通过私钥 $(p,q)$ 解密：
1. 计算 $a=\cfrac{(c^{p-1} \bmod {p^2})-1}{p}$ ；
2. 计算 $b=\cfrac{(g^{p-1} \bmod {p^2})-1}{p}$ ；
3. 使用扩展欧几里得算法计算 $b$ 的模 $p$ 逆元 $b’=b^{-1} \bmod p$ ；
4. 计算 $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

Lazzaro

CTF弱鸡自进阶