RSA-crt签名问题

密码学 > rsa
Created At :
Views 👀 :
  1. RSA的基本内容(如果对RSA很了解的话，可以跳过这部分）
  2. RSA签名
  3. 中国剩余定理
  4. 使用CRT进行RSA签名产生的问题
  5. 推论

RSA的基本内容(如果对RSA很了解的话，可以跳过这部分）

RSA的常用参数：p,q,n,e,d,phi,c,m
p,q为两个大素数
n=p*q
e*d ≡1 (mod n)
c=m^e mod n 和 m=c^d mod n ，c和m分别代表密文与明文

RSA签名

1
2
3
4
 1、RSA签名使用与加密相同的方式，不过参数交换，使用私钥签发，公钥接收
(原因：加密是为了防止中间人获取你的内容，签名是为了让接收者确认身份)
2、s=m^d  mod n生成签名消息，m=s^e mod n获得消息
3、当明文消息过长时，签名速度会大幅度下降，为了解决这个问题，使用CRT(中国剩余定理)

中国剩余定理

  • 这里不多赘述，只涉及RSA的部分

  • 中国剩余定理主要解决同余方程组的求唯一解

  • (invert(a,b)表示a对b的逆元)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
     例子：
        三个数字，3，5，7
        有三个数字，y1余3为2，余5为0，余7为0
                             y2余3为0，余5为3，余7为0
                             y3余3为0，余5为0，余7为2
        转换为同余式：
                            y1≡    2 mod 5*7(1)
                            y2≡    3 mod 3*7(2)
                            y3≡    2 mod 3*5(3)
        继续分解，将（1）的y1=2*x1
        原因：将同余式化为结果为1的方式更容易计算与验证 

    * 问题就变成了
                            x1余3为1，余5为0，余7为0
                            x2余3为0，余5为1，余7为0
                            x3余3为0，余5为0，余7为1
        这个同余方程组的最后解为y=x1*2+x2*3+x3*2
        以x1为例:x1=(5*7)*invert(5*7,3)，就解得最终的解

    使用CRT进行RSA签名产生的问题

  • 分析两个素数的情况

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
 # coding=utf-8
from Crypto.Util.number import *
from gmpy2 import *

#求最大公因数
def gcd(a, b):
    m = max(a, b)
    n = min(a, b)
    r = m % n
    while r != 0:
        m = n
        n = r
        r = m % n
    return n


m=bytes_to_long("flag")
p=13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084171
q=13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084241
n=179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639477074095512480796227391561801824887394139579933613278628104952355769470429079061808809522886423955917442317693387325171135071792698344550223571732405562649211
phi=(p-1)*(q-1)
#e=7
e=65537
d=invert(e,phi)
#print d
dp=d %(p-1)
dq=d %(q-1)

#CRT签名
s1=pow(m,dp,p)
s2=pow(m,dq,q)
s=(s1*q*invert(q,p)+s2*p*invert(p,q))%n
#print s
#print long_to_bytes(pow(s,e,n))

# 原始签名
b=pow(m,d,n)
c=long_to_bytes(pow(b,e,n))
#print b
#print c

# 故障攻击
#print long_to_bytes(pow(s,e,p)) #与原始明文相等
s2=s2+4654
s=(s1*q*invert(q,p)+s2*p*invert(p,q))%n
#print s
#print long_to_bytes(pow(s,e,n))
#print long_to_bytes(pow(s,e,p))
#print long_to_bytes(pow(s,e,q))

print gcd(pow(s,e)-m,n)
print p

  • 分析可知

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
     在正常的RSA签名与CRT签名时，结果是相同的
    当伪造部分签名s2时，在正常解密与mod q解签时，发生乱码，也就是签名发生错误
    但对于mod p的签名验证是正常的
    原理：
            m'=s'^e mod n
            m=s'^e mod p
    这是在mod n 与mod p的情况下解密签名
            s'^e =m'+k1*n=m+k2*p
    同时由于n=p*q
    那么可得：
    		s'^e = x + k1p + k3q，s'^e = x + k2p + k3q
    两式相减且在模n下可得：
    		（k1-k2)p
    n = p * q，故能因式分解

  • 那对于多素数的情况是否成立？

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
 # coding=utf-8
from Crypto.Util.number import *
from gmpy2 import *

#求最大公因数
def gcd(a, b):
    m = max(a, b)
    n = min(a, b)
    r = m % n
    while r != 0:
        m = n
        n = r
        r = m % n
    return n

m=bytes_to_long("flag")
p = 26440615366395242196516853423447
q = 27038194053540661979045656526063
r = 32581479300404876772405716877547
n = 23292710978670380403641273270002884747060006568046290011918413375473934024039715180540887338067
e=65537
phi=(p-1)*(q-1)*(r-1)
d=invert(e,phi)
#print d
dp=d %(p-1)
dq=d %(q-1)
dr=d %(r-1)

#CRT签名
s1=pow(m,dp,p)
s2=pow(m,dq,q)
s3=pow(m,dr,r)
pinv=invert(r*q,p)
qinv=invert(p*r,q)
rinv=invert(p*q,r)
s=(s1*(r*q)*pinv+s2*(p*r)*qinv+s3*(q*p)*rinv)%n
#print s
#print long_to_bytes(pow(s,e,n))
#print (pow(m,d,n))


# 原始签名
b=pow(m,d,n)
c=long_to_bytes(pow(b,e,n))
#print b
#print c

# 故障攻击
#print long_to_bytes(pow(s,e,r)) #与原始明文相等
s2=s2+1 #在q的情况下翻转
s3=s3+1
s=(s1*(r*q)*pinv+s2*(p*r)*qinv+s3*(q*p)*rinv)%n
print s
print long_to_bytes(pow(s,e,n))
print long_to_bytes(pow(s,e,p))
print long_to_bytes(pow(s,e,q))
print long_to_bytes(pow(s,e,r))

print gcd(pow(s,e)-m,p)
print p

print gcd(pow(s,e)-m,r)
print r# coding=utf-8
from Crypto.Util.number import *
from gmpy2 import *

#求最大公因数
def gcd(a, b):
    m = max(a, b)
    n = min(a, b)
    r = m % n
    while r != 0:
        m = n
        n = r
        r = m % n
    return n

m=bytes_to_long("flag")
p = 26440615366395242196516853423447
q = 27038194053540661979045656526063
r = 32581479300404876772405716877547
n = 23292710978670380403641273270002884747060006568046290011918413375473934024039715180540887338067
e=65537
phi=(p-1)*(q-1)*(r-1)
d=invert(e,phi)
#print d
dp=d %(p-1)
dq=d %(q-1)
dr=d %(r-1)

#CRT签名
s1=pow(m,dp,p)
s2=pow(m,dq,q)
s3=pow(m,dr,r)
pinv=invert(r*q,p)
qinv=invert(p*r,q)
rinv=invert(p*q,r)
s=(s1*(r*q)*pinv+s2*(p*r)*qinv+s3*(q*p)*rinv)%n
#print s
#print long_to_bytes(pow(s,e,n))
#print (pow(m,d,n))


# 原始签名
b=pow(m,d,n)
c=long_to_bytes(pow(b,e,n))
#print b
#print c

# 故障攻击
#print long_to_bytes(pow(s,e,r)) #与原始明文相等
s2=s2+1 #在q的情况下翻转
#3=s3+1
s=(s1*(r*q)*pinv+s2*(p*r)*qinv+s3*(q*p)*rinv)%n
print s
print long_to_bytes(pow(s,e,n))
print long_to_bytes(pow(s,e,p))
print long_to_bytes(pow(s,e,q))
print long_to_bytes(pow(s,e,r))

print gcd(pow(s,e)-m,p)
print p

print gcd(pow(s,e)-m,r)
print r

1
2
3
 结果当然是成立的
同时与双素数不同的，如果只篡改一个部分签名，那么获得到的可以是其他因数的积
当篡改多个部分签名时，可以获得一个公因数

推论

1
2
3
4
对于使用CRT的RSA签名来说
当模数n的因数产生的部分签名发生比特翻转或者篡改
那么可以求得N的素因数，从而到达分解N，求得私钥
篡改的部分签名的个数越多，获得因数的可能性越大
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1259742453@qq.com

💰

©2016-2020 weichujian

Built with Hexo and 3-hexo theme

×

Help us with donation