导航菜单

密码学学习笔记 之 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)*(q-1))。
  2. 计算n=p*q,λ = lcm(p-1, q-1) = (p-1)*(q-1) / gcd(p-1,q-1)
  3. 选择随机整数g,0<g<n^2
  4. 定义L(x) = (x-1) / n
  5. 计算μ = (L(g^λ mod n^2 ))^(-1) mod n
  6. 公钥为(n,g)
  7. 私钥为(λ,μ)

The second pattern(a simpler variant):

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

  1. g = n+1
  2. λ = φ(n) = (p-1)*(q-1)
  3. μ = φ(n)^(-1) (mod n)

 

Encryption

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

 

Decryption

  1. m = ( L( c^λ mod n^2 ) * μ ) mod n

Proof

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

The first pattern

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

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

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

所以①式=> $L(g^{mλ}r^{nλ} pmod{n^2})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 1pmod{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 1pmod{n^2}$

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

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

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

证毕截图:

密码学学习笔记 之 paillier cryptosystem

The second pattern

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

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

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

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

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

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

∵$g = n+1$

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

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

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

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

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

∴③式: $(mλ*μ) equiv mpmod{n}$

证毕截图:

密码学学习笔记 之 paillier cryptosystem

 

DASCTF四月月赛 not RSA

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)*(q-1) ,需要用到p和q

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

所以构造解密脚本

# -*- 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(m1, r1)*E(m2,r2) mod n^2)≡ m1+m2 (mod n)

proof

C = (g^m1) * (r1^n) * (g^m2) *(r2^n) mod n^2

= g^(m1+m2)*(r1r2)^n mod n^2

首先我们可以将m1+m2看作一个整体M,然后由于r1、r2是随机选的,所以r1*r2可以看作一个整体R,

故C = g^M * R^n mod n^2

由于gcd(r1,n) = 1; gcd(r2,n) = 1; => gcd(r1*r2, n) = 1,故R符合要求

所以D(C) = M ≡ m1 + m2 (mod n)

Homomorphic multiplication of plaintexts

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

即:D(E(m1, r1)^k mod n^2)≡ km1 (mod n)

proof

C = (g^m1) * (r1^n)^k (mod n^2 )

=(g^km1)*(r1^(kn) ) (mod n^2)

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

故C = g^M * R^n mod n^2

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

所以D(C) = M ≡ km1 (mod n)

 

Reference

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

本文由安全客原创发布转载,请参考转载声明,注明出处: https://www.anquanke.com/post/id/204720

相关推荐

国外某工业SCADA软件漏洞复现

  概述 近年来随着网络安全形势的日渐严峻,国内外越来越重视工业信息安全的研究。“等保2.0”专门加入了工业控制系统扩展要求,呼之欲出的“关保”中,大多数涉及国计民生的关键信息基础设施也属于工业控制系统...

微软轻量级系统监控工具sysmon原理与实现完全分析——ProcessGuid的生成

  Sysmon的众多事件看起来都是独立存在的,但是它们确实都是由每个进程的产生的,而关联这些信息的东西正是ProC++essGuid,这个对进程是唯一的。如下图 Event 23 都会有个ProcessGuid 字段,今天的这篇文章...