Rabin公钥密码系统

实现描述

1. 密钥产生：随机生成两个大的素数，p和q，满足 $p\equiv q\equiv 3mod4$ ,计算 n=pq, n 为公钥，p，q作为私钥。
2. 加密： $c=m^{2}modn$
3. 解密：就是求c模n的平方根，即解$x^2\equiv cmodn$,该方程等价于方程组
   $$\{\begin{array}{r}{x}^2\equiv cmodp\\ x^2\equiv cmodq\end{array}$$
   

由于$p\equiv q\equiv 3mod4$,可以容易地求出c在模p下的两个方程根，即

$x\equiv c^{\frac{p+1}{4}}modp$;$x\equiv p-c^{\frac{p+1}{4}}modp$

和c在模q下的两个方程根，即

$x\equiv c^{\frac{q+1}{4}}modq$;$x\equiv q-c^{\frac{q+1}{4}}modq$

两两组合即可得到四个方程组，即可解出4个解，其中一个解为明文。

解密算法

输入：密文c，私钥p，q（p,q均为4k+3的素数，n=pq）

输出：明文

RabinDecrypt(c,p,q){

1. 利用拓展欧几里得算法求出，s，t，使得，sp+tq = 1
2. 计算 $u\leftarrow c^{\frac{p+1}{4}}modp$
3. 计算 $v\leftarrow c^{\frac{q+1}{4}}modq$
4. 计算 $m_1\leftarrow (utq+vsp)modn$
5. 计算 $m_2\leftarrow (utq-vsp)modn$
6. 结果为，m1,n-m1,m2,n-m2,其中一个给明文

}

算法实现

import random
import time

# 判断是否为素数
# rabin_miller 法判定是否为素数
def rabin_miller(num):
    s = num - 1
    t = 0
    while s % 2 == 0:
        s = s // 2
        t += 1

    for trials in range(5):
        a = random.randrange(2, num - 1)
        v = pow(a, s, num)
        if v != 1:
            i = 0
            while v != (num - 1):
                if i == t - 1:
                    return False
                else:
                    i = i + 1
                    v = (v ** 2) % num
    return True


# 判断是否为素数
# 判断可能失效，因为该方法有伪素数存在
def is_prime(n):
    if n == 0:
        return False
    return 1 == square_and_multiply(17, n - 1, n)


# 莫重复平方运算 b^n%m
def square_and_multiply(b, n, m):
    bi = b
    ai = 1
    k = len("{0:b}".format(n))
    for i in range(0, k):
        if (n >> i & 1) == 1:
            ai = ai * bi % m
        bi = bi ** 2 % m
    return ai


# 拓展欧几里得 ， 求逆
def ex_gcd(a, b):
    if b == 0:
        return 1, 0, a
    else:
        s, t, r = ex_gcd(b, a % b)
        s, t = t, (s - (a // b) * t)
        return s, t, r


# 密钥生成
# return p,q,n, (p,q) is private key, n is public key
def key_generator():
    p = 0
    q = 0
    n = 0
    while (p - 3) % 4 != 0 or (q - 3) % 4 != 0 or p == q:
        random.seed(time.time())
        # 可以取非常大的值
        p = random.randint(2 ** 300, 2 ** 400)
        q = random.randint(2 ** 300, 2 ** 400)
    while not is_prime(p) or not is_prime(q):
        p += 4
        q += 4
    n = p * q
    return p, q, n


# 加密
# m is plaintext, n is public key
# 该算法通过重复明文方法来区分四个解
def encode(m, n):
    m1 = str(m)
    m1 = int(m1 + m1)
    c = m1 ** 2 % n
    return c


# 处理4个解的子方法
def sub_handle_decode_res(m):
    if len(m) % 2 != 0:
        return False
    i = 0
    while i < len(m) // 2:
        if m[i] != m[len(m) // 2 + i]:
            return False
        i = i + 1
    return m[:len(m) // 2]


# 处理4个解的情况
def handle_decode_res(m1, m2, m3, m4):
    m1_str = sub_handle_decode_res(str(m1))
    m2_str = sub_handle_decode_res(str(m2))
    m3_str = sub_handle_decode_res(str(m3))
    m4_str = sub_handle_decode_res(str(m4))
    if m1_str:
        return m1_str
    if m2_str:
        return m2_str
    if m3_str:
        return m3_str
    if m4_str:
        return m4_str


# 解密
def decode(c, p, q, n):
    s, t, r = ex_gcd(p, q)
    u = square_and_multiply(c, (p + 1) // 4, p)
    v = square_and_multiply(c, (q + 1) // 4, q)
    m1 = int(u * t * q + v * s * p) % n
    m2 = int(u * t * q - v * s * p) % n
    return handle_decode_res(m1, n - m1, m2, n - m2)


if __name__ == '__main__':
    p, q, n = key_generator()
    # 处理公钥私钥。
    print("p is {},q is {}, n is {}".format(p, q, n))
    m = input("请输入明文：")
    c = encode(int(m), n)
    print("密文为 {}".format(c))
    m = decode(c, p, q, n)
    print("明文为 {}".format(m))

思考

1. 该密钥系统相当于单工通信，需要两对密钥才能实现双方通信
2. 对于明文流应该进行处理，使其平方后应该大于m，