文章10
标签6
分类2

Rabin加密算法

先知已投

Rabin算法是一种基于计算模合数平方根困难性问题的非对称加密算法。他和RSA加密的形式类似,本文主要探讨Rabin算法的特殊情况和n次同余方程的解法。

加密

选择两个大素数pq做为私钥

计算n = p \times q做为公钥

密文为c \equiv m^2\;mod\;n

解密

  • 计算出rs,目的是满足:
r \equiv \sqrt{c}\ (mod\ p)\\ s \equiv \sqrt{c}\ (mod\ q)

这里的根号只是一种表示形式,表示r^2\equiv c\;(mod\;p)而已,一般来说p \equiv q \equiv 3 \pmod 4,那么结合欧拉判别定理,易知

r \equiv c^{\frac{1}{4}(p + 1)}\ (mod\ p)\\ s \equiv c^{\frac{1}{4}(q + 1)}\ (mod\ q)

+-都可以,只要取一个满足的就行了

  • 用扩展欧几里得计算出a和b:

a \cdot p + b \cdot q \equiv 1\;(mod\;n)

  • 解出四个明文:
x_1 = (a \cdot p \cdot s + b \cdot q \cdot r) \bmod n\\ x_2 = n - x_1\\ x_3 = (a \cdot p \cdot s - b \cdot q \cdot r) \bmod n\\ x_4 = n - x_3

验证:

x_1^2 \equiv (a \cdot p \cdot s + b \cdot q \cdot r)^2\equiv (a \cdot p \cdot s)^2+(b \cdot q \cdot r)^2\;(mod\;n)

s^2=k_1q+cr^2=k_2p+c

则:x_1^2 \equiv a^2 \cdot p^2 \cdot s^2+b^2 \cdot q^2 \cdot r^2\equiv c (a^2\cdot p^2+b^2\cdot q^2)\;(mod\;n)

则:x_1^2\equiv c((a\cdot p+b\cdot q)^2-2a\cdot p\cdot b\cdot q)\equiv c\;(mod\;n)

其余的也是同理可证

这里求ab可以不用之前的先求一个正数再由这个数算出另一个负数的方法(实际上两种方法是等效的),而直接求二者相互的逆元

由于

p^{-1}p \equiv1\;(mod\;q) q^{-1}q \equiv1\;(mod\;p)

那么

p^{-1}p+q^{-1}q\equiv c\;(mod\;pq)

等价于

\left\{\begin{matrix} p^{-1}p \equiv c\ (mod\ q)\\ q^{-1}q \equiv c\ (mod\ p)\\ \end{matrix}\right.

所以显然c\equiv1\;(mod\;pq)

代码验证

from Crypto.Util.number import getPrime
import gmpy2

p = getPrime(512)
while p % 4 != 3:
    p = getPrime(512)

q = getPrime(512)
while q % 4 != 3:
    q = getPrime(512)

n = p*q
plain = 123456789
cipher = pow(plain, 2, n)

inv_p = gmpy2.invert(p, q)
inv_q = gmpy2.invert(q, p)
assert (inv_p*p+inv_q*q)%(p*q) == 1

mp = pow(cipher, (p+1)/4, p)
mq = pow(cipher, (q+1)/4, q)

a = (inv_p * p *mq + inv_q * q * mp)%n
b = n - a
c = (inv_p * p *mq - inv_q * q * mp)%n
d = n - c

assert pow(a, 2, n) == cipher
assert pow(b, 2, n) == cipher
assert pow(c, 2, n) == cipher
assert pow(d, 2, n) == cipher

print a
print b
print c
print d

可以看到一共有四个解,而真正的解应该结合实际来筛选

如果p和q不是模4余3呢?

也不难,首先由m^2\equiv c\;(mod\;n)

得到m^2\equiv c\;(mod\;p)m^2\equiv c\;(mod\;q)

对两个式子可以用二次同余方程的通用解法得到m\equiv C_1\;(mod\;p)m\equiv C_2\;(mod\;q)

其中C_1C_2均有两个不同的解,然后再用CRT就能得到m\equiv M\;(mod\;pq)

demo

from Crypto.Util.number import getPrime
from random import randint
from libnum import *
from gmpy2 import invert

def power(s1, s2, k1, k2, w, p):
    return ((s1*k1+s2*k2*w)%p, (s1*k2+s2*k1)%p)

def Cipolla_algorithm(p, n):
    a = randint(1, p)
    w = a ** 2 - n

    while pow(w, (p-1)/2, p) !=p-1 :
        a = randint(1, p)
        w = a ** 2 - n

    times = (p+1)/2

    k1 = 1
    k2 = 0

    first = True

    sum1 = 1
    sum2 = 0
    while times != 0:
        if first:
            k1, k2=power(k1, k2, a, 1, w, p)
            first = False

        else:
            k1, k2=power(k1, k2, k1, k2, w, p)

        if times & 1:
            sum1, sum2 = power(sum1, sum2, k1, k2, w, p)
        times >>= 1

    return sum1

def CRT(c, n):
    N = reduce(lambda a, b: a*b, n)
    x = 0
    for i, j in zip(c, n):
        N_i = N/j
        N_i_1 = invert(N_i, j)
        x+=i*N_i*N_i_1
    return x % N

if __name__ == '__main__':
    p = getPrime(512)
    while p % 4 != 1:
        p = getPrime(512)

    q = getPrime(512)
    while q % 4 != 1:
        q = getPrime(512)

    n = p * q
    m = s2n('this is plaintext')
    c = pow(m, 2, n)
    print 'm is '+str(m)

    get_x1 = Cipolla_algorithm(p, c)
    get_x2 = Cipolla_algorithm(q, c)

    assert  pow(get_x1, 2, p) == c % p
    assert  pow(get_x2, 2, q) == c % q

    c11 = get_x1
    c12 = p-get_x1
    c21 = get_x2
    c22 = q-get_x2

    print CRT([c11, c21], [p, q])
    print CRT([c11, c22], [p, q])
    print CRT([c12, c21], [p, q])
    print CRT([c12, c22], [p, q])

n次同余方程

这样的话也就衍生了一个通用的解法,就是如果题目给的是m^e ≡ c (mod\;n),其中pq已知但是e\varphi(n)不互素的话,就可以利用上面的算法先解出m ≡ C_1 (mod\;p)m ≡ C_2(mod\;q)再用CRT联合

但也许你会问m^3 ≡ c (mod\;p)或者m^n ≡ c (mod\;p),这类方程如何求解,事实上这类方程的计算是困难的,针对这个问题,python有sympy库可以进行处理,算法应该是利用的原根进行计算,所以当p比较大的时候计算也是很难的,而且也不是一定有原根的:

from Crypto.Util.number import getPrime
from random import randint
from sympy.ntheory.residue_ntheory import nthroot_mod

p = getPrime(150)
x = randint(1, p)
n = pow(x, 4, p)

x1 = nthroot_mod(n,4,p,all_roots=False)
assert pow(x1, 4, p) == n
print x1

0 评论