本文的模逆运算等都在RSA的实现中提及,不再赘述,关于Paillier的基础知识部分见下面这篇文章

 cdcq的密码学教程三——同态加密的Paillier算法 | cdcq

import math
import random
from gmpy2 import invert
from phe import paillier


# 生成m以内的素数序列
def primes_in_range(m):
    prime_list = []
    is_prime = [0 for i in range(m + 1)]
    for i in range(2):
        is_prime[i] = 1
    for n in range(2, m):
        if is_prime[n] == 0:
            if n <= math.sqrt(m):
                prime_list.append(n)
                for i in range(n, m // 2):
                    if n * i <= m:
                        is_prime[n * i] = 1
                    else:
                        break
            else:
                prime_list.append(n)
    return prime_list


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


def fun(a, n):
    if a > n:
        a = a % n
    return a


def encrypt(plainText, g, r, n):
    return int((pow(g, plainText) * pow(r, n)) % pow(n, 2))


def decrypt(cipher, ld, n, u):
    return (L(pow(cipher, ld) % pow(n, 2), n) * u) % n


if __name__ == '__main__':
    prime = primes_in_range(50)
    # 得到两个素数p,q
    p = random.choice(prime)
    while 1:
        q = random.choice(prime)
        if p != q:
            break
    # n, ld
    n = p * q
    ld = math.lcm(p - 1, q - 1)
    g = n + 1
    v = L(pow(g, ld) % pow(n, 2), n)
    u = invert(v, n)
    print("此次RSA的随机数p = {}, q = {}".format(p, q))
    print("可求得公钥为({}, {}), 私钥为({}, {})".format(n, g, ld, u))

    # 测试, 输入明文
    plaintext1 = random.randint(1, n - 1)
    plaintext2 = random.randint(1, n - 1)
    # plaintext1 = 20
    # plaintext2 = 15
    print("plaintext1 :", plaintext1)
    print("plaintext2 :", plaintext2)

    r1 = random.randint(1, n * n - 1)
    gcd1 = math.gcd(r1, n)
    while gcd1 != 1:  # 循环直到r1与n互素
        r1 = random.randint(1, n - 1)
        gcd1 = math.gcd(r1, n)
    print("随机数r1为:", r1)
    r2 = random.randint(1, n * n - 1)
    gcd2 = math.gcd(r2, n)
    while gcd2 != 1:  # 循环直到r1与n互素
        r2 = random.randint(1, n - 1)
        gcd2 = math.gcd(r2, n)
    print("随机数r2为:", r2)

    # 求密文
    cipher1 = encrypt(plaintext1, g, r1, n)
    cipher2 = encrypt(plaintext2, g, r2, n)
    print('plaintext1 加密得 cipher1 :', cipher1)
    print('plaintext2 加密得 cipher2 :', cipher2)

    # 求明文
    M1 = decrypt(cipher1, ld, n, u)
    M2 = decrypt(cipher2, ld, n, u)
    print('cipher1解密结果为 :', M1)
    print('cipher2解密结果为 :', M2)

    print("----------------------同态加法----------------------")
    cipher3 = (cipher1 * cipher2) % pow(n, 2)
    print('cipher1 * cipher2 =', cipher3)
    print('plaintext1 + plaintext2 加密得 :', encrypt(fun(plaintext1 + plaintext2, n), g, r1 * r2, n) % pow(n, 2))

    M3 = decrypt(cipher3, ld, n, u)
    print('cipher1 * cipher2解密结果为 :', M3)
    print('plaintext1 + plaintext2为 :', fun(plaintext1 + plaintext2, n))

    print("----------------------同态乘法----------------------")
    cipher4 = pow(cipher1, plaintext2) % pow(n, 2)
    print('cipher1的plaintext次方为 :', cipher4)
    print('plaintext1 * plaintext2 加密得 :', encrypt(fun(plaintext1 * plaintext2, n), g, pow(r1, plaintext2), n) % pow(n, 2))

    M4 = decrypt(cipher4, ld, n, u)
    print('cipher1的plaintext次方的解密结果=', M4)
    print('plaintext1 * plaintext2为 :', fun(plaintext1 * plaintext2, n))

点击阅读全文
Logo

腾讯云面向开发者汇聚海量精品云计算使用和开发经验,营造开放的云计算技术生态圈。

更多推荐