RSA

RSA为一种加密算法，公钥加密，私钥解密。
算法涉及三个参数，n、e1、e2。其中n为两个大质数p、q的积，n的二进制表示密钥所占用位数，就是密钥长度。e1可以随意取，但条件是e1与(p-1)*(q-1)互质，然后e2要求(e2*e1)mod((p-1)*(q-1))=1。

加解密算法：
A为明文，B为密文，则：B=A^e2 mod n; B=A^e1 mod n。

共模攻击

假设 有一条信息m，用公钥加密信息(使用了相同的模数n)：

c1 = m^e1 mod n
c2 = m^e2 mod n

可以利用密钥d1，d2来解密：

m = c1^d1 mod n
m = c2^d2 mod n

此时如果有一个攻击者，得到了密文c1、c2，因为公钥公开，而模数相同，攻击者姐可以破解密文获得信息。
此时已知信息：
c1, c2, e1, e2, n 

gcd(e1, e2) = 1
m = c1^d1 mod n
m = c2^d2 mod n

求出m。

接下来就到了高数时间。
e1,e2互质

gcd(e1,e2)=1

则有 

e1*s1 + e2*s2 = 1

这里涉及到欧几里德扩展算法，可以看我另一篇文章： 欧几里德算法及扩展算法
因为 

c1 = m^e1 mod n
c2 = m^e2 mod n

所以

(c1^s1*c2^s2) mod n = ((m^e1 mod n)^s1*(m^e2 mod n)^s2) mod n

即

(c1^s1*c2^s2) mod n = (m^(e1^s1 + e2^s2)) mod n

所以

(c1^s1*c2^s2) mod n = (m^(1)) mod n

即

c1^s1*c2^s2= m

得证，可求出m。

  • 注意：
    从前面的式子e1*s1 + e2*s2 = 1可以知道，s1、s2中有一个为负数，而负数次幂运算，比如这里求c2的s2次幂，需要先计算c2的模反元素c2r，然后再求c2r的-s2次幂。

例子

这里我找一个CTF的例子
http://www.shiyanbar.com/ctf/1834
首先分析一下数据，发现n都是相同的，由此联想到共模攻击。
先写一个脚本找出两组e互质的数据： 

# coding=utf-8
# author : 1ABlades

import re, os

base_dir = os.path.dirname(__file__)
f = open(base_dir + "\data.txt", 'r')
str = f.read()

reobj = re.compile("\: 0x(\w+)L* \:")
e = reobj.findall(str)

n = 0
for i in e:
n = n+1
m = 0
for j in e:
    m = m + 1
    for p in i:
        if p=='L':
            i = i[:-1]
    for q in j:
        if q=='L':
            j = j[:-1]
    a = int(i,16)
    b = int(j,16)
    if(a<=0 or b<=0 or a==b):
        continue
    elif(a==1 or b==1):
        print i + "and" + j
    else:
        if a < b:
            t = a
            a = b
            b = t
        while 1:
            t = a%b
            if t==0:
                break
            else:
                a = b
                b = t
        if b>1:
            continue
        else:
            print 'group',n ,'and', m ,': ' + i + "  " + j

找出第9和19组数据，写脚本进行破解：

# -*- coding: utf-8 -*-
# author ：Swing   bolg: www.wing3.cn

from libnum import n2s,s2n
from gmpy2 import invert

def egcd(a, b):
if a == 0:
    return (b, 0, 1)
else:
    g, y, x = egcd(b % a, a)
    return (g, x - (b // a) * y, y)

def main():
    n = int('a5f7f8aaa82921f70aad9ece4eb77b62112f51ac2be75910b3137a28d22d7ef3be3d734dabb9d853221f1a17b1afb956a50236a7e858569cdfec3edf350e1f88ad13c1efdd1e98b151ce2a207e5d8b6ab31c2b66e6114b1d5384c5fa0aad92cc079965d4127339847477877d0a057335e2a761562d2d56f1bebb21374b729743',16)
    c1 = int('6fdcbfb5cd2cacd032ef7200fd49b9f304a6dbd8399f4a91a72d1d9150f97b3b513f44dfc56f6f7c8ec41a8ef9b93a80230a1e65e29d2ef519bb83931d4b0c7a589059cfdf2d571660ab790a9c7e085e3018bf19748abd6d521952b68bc9594c1ad34726658bd9bd445d3b6381ceee57328838e8a129867e505be0ca0d1a1da5',16)
    c2 = int('8caeaa7d272f9606fee9222efd1d922143db738b95bd64746b27bc4c0fd979a2c57b4735131a4391a81bf5f0c0c8eea41d4f91bed4d17784b1956fd89882b97c98009051ac3a03964499c864524d3ddc10299c0290e91707b62ce89b118afe558151be39d61de0483def52c6cb546132ecab85143715bc593a2892b1e41b37b9',16)
    e1 = int('6b8a5ae7',16)
    e2 = int('4042c3955',16)
    s = egcd(e1, e2)
    s1 = s[1]
    s2 = s[2]
    # 求模反元素
    if s1<0:
        s1 = - s1
        c1 = invert(c1, n)
    elif s2<0:
        s2 = - s2
        c2 = invert(c2, n)

    m = pow(c1,s1,n)*pow(c2,s2,n) % n
    print n2s(m)

if __name__ == '__main__':
  main()
referer: