记录一些很久之前零零散散的学习笔记，总有一天得发出来的，择日不如撞日。

• Paillier cryptosystem
  • Key Generation
  • Encryption
  • Decryption
  • Correctness
  • Homomorphic properties
  • Attack
    • 分析
• DSA System
  • Generate Key
  • Signing
  • Verify
  • Correctness
  • Code Part
  • Attack
    • MSB Leaked Attack 1
    • MSB Leaked Attack 2
• Shamir’s Secret Sharing Algorithm
  • 插值
    • 拉格朗日插值法
  • 算法
    • 具体实现
• 密码协议
  • OT
    • vulnerability

Paillier cryptosystem

Key Generation

1. 随机地选择两个大素数 p, q，保证 gcd(pq, (p - 1)(q - 1)) = 1。（当 p, q 长度相等时一定有该性质，详见 Introduction to Modern Cryptography: Principles and Protocols）
2. 计算 n = pq 和 λ = lcm(p - 1, q - 1)
3. 选取 $g \in Z_{n^2} ^* $ 使得 $n \arrowvert ord_{n^2}(g)$ 这里可以使用 $gcd(L(g^{\lambda}\ mod\ n^2),n )=1$ 来检查
   • 这里的限制条件是为了保证 $gcd(L(g^{\lambda}\ mod\ n^2),n )=1$（可以假设一波带到 Correctness 里面证明，可能是防止选择密文攻击）

公钥为 (n, g) 私钥为 λ

• 对于长度相等的 p, q，一个简单的变体是： $g=n+1,\lambda = \phi(n), u=\phi(n)^{-1}\ mod\ n$

Encryption

1. 对于 $0 \le m < n$，选择随机的 0 < r < n，保证gcd(r, n) = 1
2. 计算密文 $c = g^m·r^n\ (mod\ n^2)$

Decryption

$m = L(c^{\lambda}\ mod\ n^2)·L(g^{\lambda}\ mod\ n^2)^{-1}\ (mod\ n)$，其中 $L(a) ={ {a-1}\over n}$

Correctness

由：$x^{\lambda} \equiv 1\ (mod\ p),x^{\lambda} \equiv 1\ (mod\ q)$

而 $gcd(p,q)=1$ 故 $x^{\lambda} \equiv 1\ (mod\ n)$

那么可以得到 $x^{\lambda} \equiv kn+1\ (mod\ n^2)$，$0 <k < n$

由二项式定理可知 $(x^{\lambda})^i\equiv ikn+1\ (mod\ n^2)$，$0< i,k < n$

故而该解密法是正确的。

Homomorphic properties

同态性

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

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

Attack

条件：选择密文攻击

若 $g^{\lambda} = 1+ n\ (mod\ n^2)$，那么解密时只需 $m = L(c^{\lambda}\ mod\ n^2)\ (mod\ n^2)$

对于这样的 g 及解密方式，我们有 Chosen Ciphertext Attack

我们选择 $c’ = (g+n)^m\ (mod\ n^2)$ 回传拿到 $m’$

那么 $\lambda = g(m’m^{-1}-1)\ (mod\ n)$

分析

故：$((g+n)^{\lambda})^m \equiv (1+(\lambda g^{-1} + 1)n)^m\equiv m(\lambda g^{-1} + 1)n + 1\ (mod\ n^2)$

得到 $m’=m(\lambda g^{-1} + 1)\ (mod\ n^2)$

从而拿到 $\lambda $

DSA System

Generate Key

1. Choose a hash function H (commonly SHA-1/SHA-2)
2. Choose key length L (original DSS choose a multiple of 64 between 512 and 1024, while NIST 800-57 recommends 2048/3072)
3. Choose modulus length N < L and len(Hm),
4. Choose an N-bit prime q
5. Choose an L-bit prime p where p - 1 is a multiple of q
6. Choose an interger h randomly from 2, …, p - 2 (commonly 2)
7. Compute $g=h^{ (p-1)\over q}\ (mod\ p)$ (if g=1, try again with a different h)
8. Choose an interger x randomly from 1, …, q - 1
9. Compute $y=g^x\ (mod\ p)$

(p, q, g) are parameters, y is pubkey and x is prikey.

Signing

1. Choose an interger k randomly from 1, …, q - 1
2. Compute $r\equiv (g^k (mod\ p))\ (mod\ q)$ (if r=0,try again with a different k)
3. Compute $s\equiv k^{-1}(H(m)+rx)\ (mod\ q) $ (if s=0,try again with a different k)

(r, s) is the signature.

Verify

1. Compute $w=s^{-1}\ (mod\ q)$
2. Compute $u_1 = H(m)·w\ (mod\ q)$
3. Compute $u_2=r·w\ (mod\ q)$
4. Compute $v=(g^{u_1} y^{u_2}(mod\ p))\ (mod\ q)$
5. if v == r, then the signature is valid.

(r,s should be in (0, q))

Correctness

易证。

注意这里 $k$ 的不可知性非常重要。

Code Part

摘录于某题目

def genkey():
    # DSA
    q = number.getPrime(128)

    while True:
        t = random.getrandbits(1024-128-1)
        p = (t * 2*q + 1)
        if number.isPrime(p):
            break

    e = (p-1) // q
    g = pow(2, e, p)

    x = random.randint(1, q-1)
    y = pow(g, x, p)

    return {'y':y, 'g':g, 'p':p, 'q':q, 'x':x}

def sign(m, key):
    g, p, q, x = key['g'], key['p'], key['q'], key['x']

    k = random.randint(1, q-1)

    Hm = int.from_bytes(sha256(m.encode()).digest(), 'big')
    # Here can be replaced by another hash function
    r = pow(g, k, p) % q
    s = (number.inverse(k, q) * (Hm + x*r)) % q
    sig = name.encode() + r.to_bytes(20, 'big') + s.to_bytes(20, 'big')
    print(f"Here is your signature in hex: {sig.hex().upper()}")

def verify(data, key):
    (name, r, s) = (data[:-40].decode(), data[-40:-20], data[-20:])
    sig = map(lambda x: int.from_bytes(x, 'big'), (r, s))
    r, s = sig
    y, g, p, q = key['y'], key['g'], key['p'], key['q']
    if not (0 < r < q) or not (0 < s < q):
        return False

    Hm = int.from_bytes(sha256(m.encode()).digest(), 'big')
    w = number.inverse(s, q)
    u1 = (w * Hm) % q
    u2 = (w * r) % q
    v = ( (pow(g, u1, p) * pow(y, u2, p)) % p ) % q
    return v == r

Attack

MSB Leaked Attack 1

在另一篇博文中讲到利用 LLL 来拿到 HNP 的方法，这里将之应用于 DSA。

条件：已知多组 k 的高位。k 越小于 q，成功率越高。一般来说需要 $MSB_{log^2q}$

假设我们已知 $u,l$ 满足 $\arrowvert k-u\arrowvert < {q\over 2^{l+1}}$

那么由 DSA 的生成过程我们知道： \(\begin{align} \arrowvert k-u\arrowvert &= \arrowvert \lfloor s^{-1}(H(m)+rx)\rfloor_q-u\arrowvert_q \\ &=\arrowvert \lfloor \lfloor s^{-1}r\rfloor_q·x\rfloor_q - \lfloor u-s^{-1}H(m)\rfloor_q \arrowvert \end{align}\) 那么拿得到 $s,r,q,u,H(m)$，解得 $x$ 自然不在话下。

MSB Leaked Attack 2

上面是通过 CVP 直接求得私钥 $x$，那么这里再介绍一种通过 SVP 求得 $k$ 再拿到私钥 $x$ 的方法。

由：($n$ 就是 $q$) \(s=k^{-1}(H(m)+dr)\ (mod\ n)\\ k-s^{-1}(H(m)+dr)=k-s^{-1}rd-s^{-1}H(m)\equiv 0\ (mod\ n)\\ k+Ad+B\equiv 0\ (mod\ n)\) 其中 $A\equiv s^{-1}d\ (mod\ n),B\equiv -s^{-1}H(m)\ (mod\ n)$

那么可以构造如下格基：

易知有短向量 $v_k=(k_1,k_2,…,Kx/n,K)$ 在该 lattice 中。其中 $K$ 为 $k_i$ 的一个上限。

这里通过规约后，目标向量一般为 $SVP_2$。原因是：有一个极短向量 $v = (0,…,0,K,0)$ 也在该格上。多次测试发现目标向量总会出现在规约后的第二行。

• 例题：XCTF 2020战疫赛 HNP

Shamir’s Secret Sharing Algorithm

插值

插值是数学领域数值分析中的通过已知的离散数据求未知数据的过程或方法。

拉格朗日插值法

设有 一元n次多项式 $f(x)=\sum\limits_{i=0}^na_ix^i$，我们已知该多项式曲线上任意 n+1 个不同的点 $(x_0,y_0),…,(x_n,y_n)$，则可求出该多项式。

显然如果可以构造 $f_i(x):f_i(x_j) = 1,j=i\ 0,j\ne i$，则知 $f(x)=\sum y_if_i(x)$ 满足上述条件。

那么我们可以构造 $f_i(x)$ 如下： \(f_i(x) := {\prod\limits_{j\ne i}(x-x_j)\over \prod\limits_{j\ne i}(x_i-x_j)}=\prod\limits_{j\ne i}{(x-x_j)\over (x_i-x_j)}\) 显然这是一个满足上述已知条件的 一元n次多项式，且反客为主地由这不同 n+1 个点构成方程组的系数矩阵秩为 n+1 等于其增广矩阵的秩，故仅有唯一解。

算法

referred to https://www.bilibili.com/read/cv6674795/

Shamir 的 (m,n) 门限方案：指秘密分割成 n 份，当至少有 m 份被聚合起来时可以恢复出秘密。

结合前面的插值法，我们显然可以发现，构造一个 m-1 次的多项式是可行的、且当少于 m 份秘密时，容易发现矩阵存在自由变量，故多项式不唯一，无法得到唯一秘密。

具体实现

• 秘密分割算法

  1. 选择一个随机素数 p，并产生一个随机的 m-1 次多项式

     $f(x)=\sum\limits_{i=0}^{m-1}a_ix^i\ (mod\ p)$，其中令 a_0 = s；

  2. 选择 n 个互不相同的整数 1 ~ p-1；

  3. 第 i 个参与者获得 k_i = f(x_i) 作为他的 share，并保密；（x_i 无需保密）

  4. 销毁 f(x)。

• 秘密重构算法

  按拉格朗日插值法计算即可。

密码协议

OT

参考自 Wikipedia，这里介绍的是基于 RSA 的 1-2 OT 方案。

Alice 希望仅将 $m_0, m_1$ 中的一条信息发送给 Bob，且 Bob 也不希望 Alice 知道他获得了哪一条消息，则有方案如下：

1. Alice 生成一对 RSA key，并将 PubKey 发送给 Bob；
2. Alice 生成两个随机的 $x_0, x_1$，并将其发送给 Bob；
3. Bob 选择一个 $b\in {0, 1}$，生成随机 $k$ 并计算 $v=(x_b+k^e)\ mod\ N$ 发送给 Alice；
4. Alice 计算 $k_i=(v - x_i)^d\ mod\ N$，并计算出 $m_i’ = m_i + k_i$，将 $m_i’$ 都发给 Bob；
5. Bob 最后计算得到 $m_b=m_b’-k$。

vulnerability

精心构造 $v$，可以得到 $m_0 + i * m_1$。

知：若能使 $k_0 = -ik_1$，则 $m_0’ + i * m_1’ = (m_0 + k_0) + i * (m_1 + k_1) = m_0 + i * m_1$；即，$k_0^e=v-x_0,k_1^e=v-x_1$，带入 $k_0 = -ik_1$ 即可得到 $v={[(-1)^ei^ex_1-x_e]\over [(-1)^ei^e-1]}$。