密码学学习笔记 之 paillier cryptosystem

首发于安全客

Preface

  现代公钥密码系统中,其实远远不止RSA、DSA、ECC等众所周知的公钥密码系统,最近还学习到了一种比较年轻的公钥密码系统 —— paillier cryptosystem 但是wiki上并没有给出该方案的解密的proof。

Introduce

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

Key generation

The frist pattern:

  1. 随机选择两个大质数p、q满足$gcd(pq, (p-1)\cdot (q-1))$。
  2. 计算$n=p\cdot q,λ = lcm(p-1, q-1) = \frac{(p-1)\cdot (q-1) }{ gcd(p-1,q-1)}$
  3. 选择随机整数g,$0<g<n^2$
  4. 定义$L(x) = \frac{(x-1)} { n}$
  5. 计算$μ = (L(g^λ \pmod {n^2} ))^{-1} \pmod n$
  6. 公钥为$(n,g)$
  7. 私钥为$(λ,μ)$

The second pattern(a simpler variant):

其余参数不变,主要改变了g,λ,μ的定义

  1. $g = n+1$
  2. $λ = φ(n) = (p-1)\cdot (q-1) $
  3. $μ = φ(n)^{-1} \pmod n$

Encryption

  1. 设$m$为要加密的消息,显然需要满足,$0 ≤ m < n$
  2. 选择随机 $r$,保证$gcd(r, n) = 1$
  3. 密文$c$:$c = g^m\cdot r^n \pmod {n^2}$

Decryption

  1. $m = ( L( c^λ \pmod {n^2} ) \cdot μ ) \pmod n$

Proof

以下推理过程就用数学公式记录了,如果平台显示不出来的话,建议复制进typora等此类编辑器中食用,下面也会给出截图

The first pattern

由 $L(c^λ \pmod{n^2}\cdot μ) \pmod{n}$

有 $L(g^{mλ}\cdot r^{nλ}\pmod{n^2})\cdot μ \pmod{n}$ ①

其中$λ = \frac{(p-1) \cdot (q-1)}{gcd((p-1)\cdot (q-1))}, μ = L(g^λ \pmod{n^2})^{-1} \pmod{n}$

所以①式=> $L(g^{mλ}\cdot r^{nλ} \pmod{n^2})\cdot L(g^λ \pmod{n^2})^{-1} \pmod{n}$ ②

∵$(p-1)|λ, (q-1)|λ$

∴$λ = k_1(p-1) = k_2(q-1)$

∴$g^λ = g^{k_1(p-1)}\equiv 1 \pmod{p},即 (g^λ -1) | p$

$ g^λ = g^{k_2(q-1)}\equiv 1 \pmod{q}, 即 (g^λ -1) | q$

∴$ (g^λ -1) | lcm(p,q) ,即 (g^λ -1) | pq,即g^λ \equiv 1 \pmod{n} $

∴$g^λ \pmod{n^2} \equiv 1\pmod{n}$

∴$g^λ\pmod{n^2} = k_gn+1; k<n$

∴$L(g^λ\pmod{n^2}) = k_g$

且有

  1. $1+kn \equiv 1+kn \pmod{m^2}$

  2. $(1+kn)^2 \equiv 1+2kn+(kn)^2 \equiv 1+2kn \pmod{m^2}$

  3. $(1+kn)^3 \equiv 1+3(kn)^2+3kn+(kn)^3 \equiv 1+3kn \pmod{m^2}$

    这里我们就不用数学分析法了,就直接易得了

    => $(1+kn)^{m} \equiv knm+1 \pmod{n^2}$

∴$g^{mλ} = (1+k_gn)^{m} \equiv k_gnm+1 \pmod{n^2}$

∴$r^{nλ} = (1+k_nn)^{n} \equiv k_nn^2+1 \equiv 1\pmod{n^2}$

∴$L(g^{mλ}\cdot r^{nλ}\pmod{n^2}) = L(k_gnm+1)=mk_g$

又∴$L(g^λ\pmod{n^2}) = k_g$

∴②式: $L(g^{mλ} \cdot r^{nλ} \pmod{n^2})\cdot L(g^λ \pmod{n^2})^{-1} \pmod{n}$ => $mk_g\cdot k_g^{-1} \equiv m \pmod n$

证毕

The second pattern

由 $L(c^λ \pmod{n^2} \cdot μ) \pmod{n}$

有 $L(g^{mλ}\cdot r^{nλ} \pmod{n^2} \cdot μ) \pmod{n}$ ①

其中$λ = (p-1)*(q-1), μ = φ(n)^{-1} \pmod{n}$

∵$r^{nλ} = r^{n(p-1) \cdot (q-1)} = r^{φ(n^2)}$

由欧拉定理:$r^{φ(n^2)} \equiv 1 \pmod{n^2}$

①式 => $L(g^{mλ} \pmod{n^2} \cdot μ) \pmod{n}$ ②

∵$g = n+1$

∴$g^{mλ} = (1+n)^{mλ} \equiv nmλ+1 \pmod{n^2}$

②式=> $L((nmλ+1) \cdot μ) \pmod{n}$

=> $ \frac{(nmλ+1)-1}{n} \cdot μ \pmod{n}$

=>$(mλ \cdot μ) \pmod{n}$ ③

∵$λ = φ(n),μ = φ(n)^{-1} \pmod{n}$

∴③式: $(mλ \cdot μ) \equiv m\pmod{n}$

证毕

DASCTF四月月赛 not RSA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import getPrime as bytes_to_long
from secret import flag,p,q
from sympy import isprime,nextprime
import random

m=bytes_to_long(flag)
n=p*q
g=n+1
r=random.randint(1,n)

c=(pow(g,m,n*n)*pow(r,n,n*n))%(n*n)

print "c=%d"%(c)
print "n=%d"%(n)

可以看到,这一题就是用的paillier cryptosystem,且参数用的是上文中的The second pattern

但是我们计算$λ = φ(n) = (p-1)\cdot (q-1)$ ,需要用到p和q

这里我们直接上yafu分解n发现可以成功分解,原因是p与q其实非常接近,所以其实直接对n开根然后再在附近寻找素数就能找到p、q了。

所以构造解密脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# -*- coding: utf-8 -*-
from Crypto.Util.number import long_to_bytes,inverse
from sympy import nextprime
from gmpy2 import iroot

def L(x,n):
return (x-1)/n


c=
n=

#factor(n)
a = iroot(n,2)[0]
p = nextprime(a)
q = n//p
assert p*q == n

#根据解密公式,计算所需私钥对(λ,μ)
Lambda=(p-1)*(q-1)
miu=inverse(Lambda,n*n)
m=(L(pow(c,Lambda,n**2),n)*miu)%n

print long_to_bytes(m)

Homomorphic properties

Homomorphic addition of plaintexts

设D为解密函数,E为加密函数

即:$D(E(m_1, r_1)\cdot E(m_2,r_2) \pmod {n^2})≡ m_1+m_2 \pmod n$

proof

$C = (g^{m_1}) \cdot (r_1^n) \cdot (g^{m_2}) \cdot (r_2^n) \pmod {n^2} $

 $= g^{m_1+m_2}\cdot (r_1\cdot r_2)^n \pmod {n^2}$

首先我们可以将$m_1+m_2$看作一个整体$M$,然后由于$r_1、r_2$是随机选的,所以$r_1\cdot r_2$可以看作一个整体$R$

故$C = g^M \cdot R^n \pmod {n^2}$

由于$gcd(r_1,n) = 1; gcd(r_2,n) = 1; => gcd(r_1\cdot r_2, n) = 1$,故$R$符合要求

所以$D(C) = M ≡ m_1 + m_2 \pmod n$

Homomorphic multiplication of plaintexts

设D为解密函数,E为加密函数

即:$D(E(m_1, r_1)^k \pmod {n^2})≡ km_1 \pmod n$

proof

$C = (g^{m_1}) \cdot (r_1^n)^k\pmod {n^2} $

 $=(g^{km_1}\cdot (r_1^{kn} )\pmod {n^2}$

首先我们可以将$km_1$看作一个整体$M$,然后由于$r_1$是随机选的,所以$r_1^k$可以看作一个整体R,

故$C = g^M \cdot R^n \pmod {n^2}$

由于$gcd(r_1,n) = 1 => gcd(r_1^k, n) = 1$,故$R$符合要求

所以$D(C) = M ≡ km_1 \pmod n$

Reference

https://en.wikipedia.org/wiki/Paillier_cryptosystem


转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 643713081@qq.com

文章标题:密码学学习笔记 之 paillier cryptosystem

文章字数:1.3k

本文作者:Van1sh

发布时间:2020-05-14, 11:00:19

最后更新:2020-07-19, 13:53:43

原始链接:http://jayxv.github.io/2020/05/14/密码学学习笔记之 paillier cryptosystem/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

目录
×

喜欢就点赞,疼爱就打赏