r1ngs's blog

Rabin加密算法

2019-05-28

先知已投,戳我跳转

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

加密

选择两个大素数$p$和$q$做为私钥

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

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

解密

  • 计算出$r$和$s$,目的是满足:

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

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

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

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

  • 解出四个明文:

验证:

$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+c$和$r^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)$

其余的也是同理可证

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

由于

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

那么

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

等价于

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

代码验证

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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_1$和$C_2$均有两个不同的解,然后再用CRT就能得到$m\equiv M\;(mod\;pq)$了

demo

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
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)$,其中$p$、$q$已知但是$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比较大的时候计算也是很难的,而且也不是一定有原根的:

1
2
3
4
5
6
7
8
9
10
11
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
Tags: 分析

1000000