Paillier加法同态加密算法

Paillier加法同态加密算法

设想场景

设想这样一个场景,天璇团建,要出去吃饭,让Rain去订个饭店,Rain得知道天璇的小伙伴一共有多少钱,来决定订什么样的饭店,但又不能让Rain知道每个人具体有多少钱,要不然Rain很有可能去打劫钱最多的那个人。所以,现在就面临既不能让Rain知道每个人各自有多少钱,但又得知道一共有多少钱的问题。

解决方式

这个问题其实有很多比较简单地解决方法,但如果将这个问题抽象到隐私保护,上升到密码层面,Paillierg公钥加密算法就是解决方式之一。

以上面的场景为例,加密的密钥分为私钥和公钥,Rain拥有公私钥,其他小伙伴只有公钥,他们用公钥将自己的钱数加密之后发给zbr,zbr没有私钥,不能解密,所以zbr也不能知道其他人各自有多少钱,没法打劫钱最多的人。zbr将收到的密文(包括自己的)做乘积运算,把结果给Rain,Rain用私钥解密之后就是大家一共拥有的钱数。

同态加密

引入

如上所见,由于zbr也是有可能打劫其他人的,所以计算钱数之和不能先对密文解密,所以就引出

在不先对加密数据解密时而执行对加密数据的计算的问题。

这里的计算主要是指加法运算乘法运算,RSA算法是满足乘法同态的,但不满足加法同态,Paillier加密算法满足加法同态而不满足乘法同态。一个加密算法如果同时满足加法和乘法的同态,就叫做全同态加密算法,在密码学中,全同态加密算法被称作密码学的圣杯

Paillier算法

密钥生成

  1. 选两个 大素数 p, q 保证 gcd ( pq , ( p − 1 ) ( q − 1 ) ) = 1, gcd(pq, (p-1)(q-1)) = 1,gcd(pq,(p−1)(q−1))=1
  2. 计算 n = p*q , λ = lcm ( p − 1 , q − 1 ) ((p-1)和(q-1)的最小公倍数)
  3. 定义 L ( x ) = ( x − 1 ) //n
  4. 随机选一个小于 n^2 的正整数 g ,并且存在L(g^λ mod n^2)存在mod n的逆元。
  5. 公钥为 ( n , g )
  6. 私钥为 λ

可快速生成密钥: 在p,q长度相同的情况下,可以快速生成密钥g, g = n+1

需要注意的是,p和q要选择强素数,这样,如果用Pollard的p-1素因数分解算法来分解n就会变得不可行。pollard算法法运用起来相当简单,所以在防止因式分解攻击时,必须考虑这一方法。

加密

  1. 明文 m 是 大于等于0 小于n的正整数
  2. 随机选择r满足 0 < r < n,并且 r和n 互质
  3. 计算密文 c = g^m*r^n mod n^2

解密

计算明文 m = L (c ^ λ mod n^2) * (L(g^λ mod n^2) mod n 的逆元)

同态性

paillier算法的同态性指:n个密文的在mod n^2意义下的乘积,解密之后是n个明文的和

同态性的证明

$$
c_1\:=\:g^{m1}*r_1^{n}\:mod\:n^2
$$

$$
c_2 = g^{m2}*r_2^n \:mod \:n^2
$$

$$
c_1c_2=g^{m_1+m_2}(r_1*r_2)^n\:mod\:n
$$

根据一些奇妙的定理,可以将上面第三个公式的
$$
(r_1*r_2)
$$
直接当做随机数r,这样第三个式子就等价于加密
$$
(m_1+m_2)
$$
多个m相加的情况也是类似的。

python实现

密钥生成:

def keygen():
    while True:
        p = getStrongPrime(512)
        q = getStrongPrime(512)
        n = p * q
        lmd = (p - 1) * (q - 1)     # 私钥
        g = n + 1
        if gcd(mpz(L(powmod(g, lmd, n ** 2), n)),mpz(n)) == 1:
            break
    pk = [n, g]
    sk = lmd
    return pk, sk

加密:

def encipher(plaintext, pk):
    m = plaintext
    n, g = pk
    while True:
        r = random.randint(1, n ** 2)
        if gcd(r, n) == 1:
            break
    c: mpz = powmod(g, m, n ** 2) * powmod(r, n, n ** 2) % (n ** 2)
    return c

解密:

def decipher(c, pk, sk):
    [n, g] = pk
    lmd = sk
    u = invert(mpz(L(powmod(g, lmd, n ** 2), n)), mpz(n)) % n
    m = L(powmod(c, lmd, n ** 2), n) * u % n
    return m

同态:

sum = 0     
multi = 1
l = len(m_list)
for i in range(l):
    data = m_list[i]
    sum += data
    cipher = int(encipher(data, [n, g]))
    multi = multi*cipher % n**2

sum = decipher(multi, [n, g], s_key)
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇