其他加密算法

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
2
3
4
5
6
7
8
9
10
11
12
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$ 的整数 $p$ 组成,这两个数和集合 $\{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
    16
    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

  • 常规解密脚本
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
###Sage###
import binascii
# open the public key and strip the spaces so we have a decent array
fileKey = open("pub.Key", 'rb')
pubKey = fileKey.read().replace(' ', '').replace('L', '').strip('[]').split(',')
nbit = len(pubKey)
# open the encoded message
fileEnc = open("enc.txt", 'rb')
encoded = fileEnc.read().replace('L', '')
print("start")
# create a large matrix of 0's (dimensions are public key length +1)
A = Matrix(ZZ, nbit + 1, nbit + 1)
# fill in the identity matrix
for i in range(nbit):
A[i, i] = 1
# replace the bottom row with your public key
for i in range(nbit):
A[i, nbit] = pubKey[i]
# last element is the encoded message
A[nbit, nbit] = -int(encoded)

res = A.LLL()
for i in range(0, nbit + 1):
# print solution
M = res.row(i).list()
flag = True
for m in M:
if m != 0 and m != 1:
flag = False
break
if flag:
print(i, M)
M = ''.join(str(j) for j in M)
# remove the last bit
M = M[:-1]
M = hex(int(M, 2))[2:-1]
print(bytes.fromhex(M))
  • 泄露部分明文空间的降维处理
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
52
53
54
55
56
57
58
###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:]))
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
52
53
54
55
56
57
58
59
60
61
62
63
64
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/

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

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
#法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))
1
2
3
4
5
6
7
8
9
10
11
#法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
1
2
3
4
5
6
7
8
9
10
11
12
13
#法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$。

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$ 了。

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