RSA-CRT签名的问题

阅读量    244497 |

分享到: QQ空间 新浪微博 微信 QQ facebook twitter

 

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,求得私钥。篡改的部分签名的个数越多,获得因数的可能性越大。

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

分享到: QQ空间 新浪微博 微信 QQ facebook twitter
|推荐阅读
|发表评论
|评论列表
加载更多