RSA-CRT签名的问题

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

中国剩余定理

• 这里不多赘述，只涉及RSA的部分
• 中国剩余定理主要解决同余方程组的求唯一解
  (invert(a,b)表示a对b的逆元)

例子：
    三个数字，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签名产生的问题

• 分析两个素数的情况

# 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

• 分析可知

在正常的RSA签名与CRT签名时，结果是相同的
当伪造部分签名s2时，在正常解密与mod q解签时，发生乱码，也就是签名发生错误
但对于mod q的签名验证是正常的
原理：
        m=s^e mod n
        m=s^e mod p
这是在mod n 与mod p的情况下解密签名
        s^e =m+k1*n=m+k2*p
那么
        k1*n=k2*p=s^e -m
我们知道k1与k2是不相等的，同时n=p*q，所以k1*n与s^e -m 有公因数p
所以可以求得p，此时分解了n，就可以求得私钥d

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

# 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

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

推论

• 对于使用CRT的RSA签名来说，当模数n的因数产生的部分签名发生比特翻转或者篡改，那么可以求得N的素因数，从而到达分解N，求得私钥。篡改的部分签名的个数越多，获得因数的可能性越大。

如果那里有问题，欢迎师傅们指出。