总结一下最近几年比赛中的 RSA，这个算法是基本上被研究透了，题目来源于各大 CTF 比赛及复现平台

github: https://github.com/peri0d/RSA_Attack

工具&环境

RSATool
msieve
yafu
rsa-wiener-attack
求 d 的脚本 d.py
生成私钥文件的脚本 private.py
欧几里得算法求公约数 divisor.py
共模攻击脚本 common_mode.py
小明文攻击脚本 small_plaintext.py
dp 泄露求 p q 脚本 dp_divulge.py
dp dq 泄露求明文脚本 dpdq_divulge.py
python2
- binascii
- gmpy2
- pycrypto(Crypto)

RSA 算法概述

RSA 涉及到的几个变量

明文：m
模数：n
大质数：p，q
欧拉函数值：r
密钥：d，e
密文：c

RSA 的流程

生成两个大质数 p，q
求 n : n = p*q
求 r : r = (p-1)*(q-1)
求 e : 1<e<r 且 gcd(e,r)=1
求 d : 1<d<r 且 e*d mod r = 1
加密 : c = m的e次方 mod n 即 c = pow(m,e,n) ，注意一点，这里在进行加密的时候，m<n
解密 : m = c的d次方 mod n 即 c = pow(c,d,n)

小素数的例子

生成质数 p = 7，q = 17
n = 7 * 17 = 119
r = (7-1)*(17-1) = 96
1<e<96，且 gcd(e,96)=1，可取 e = 5
1<d<96 且 5*d mod 96 = 1 可得 5d = 96k + 1
k = 4，可得 d = 77
假设明文为 iLOVEu ，可以将每个字符转化为 ASCII 码再进行加密，加密结果为 56 111 95 18 69 87 ，解密反过来即可

RSA攻击

0. 对模数 n 的分解

msieve
yafu
http://factordb.com/
利用公约数，对 2 个 n 有相同的公约数使用欧几里得算法

1. 已知p、q、e 求d

在一次RSA密钥对生成中，假设p=473398607161，q=4511491，e=17，求解出 d

可用脚本，也可用 gmpy2.invert(e,(p-1)*(q-1))

2. 已知n、e、密文求明文

已知n=920139713，e=19，密文如下

n 分解结果为 p=18443，q=49891 ，可求 d，再利用 c = pow(c,d,n) 可求明文

3. 已知私钥文件、密文求明文

给出私钥文件 private 和密文 encdata

可在 kali 或 Ubuntu 使用 openssl 直接解密
openssl rsautl -decrypt -in endata -inkey private -out flag.txt

4. 已知公钥文件、密文求明文

给出公钥文件 public.pem 和密文 flag.enc

先分析公钥文件是否可以攻击，如果可以攻击会返回公钥信息
openssl rsa -pubin -text -modulus -in public.pem

获取模数 n=CA00F5ED7B33B9BD421E77318AA178E75DEDE3CB1BC7D47A7D143BE7491C9025

获取 e=65537

msieve 分解n
msieve153.exe 0xCA00F5ED7B33B9BD421E77318AA178E75DEDE3CB1BC7D47A7D143BE7491C9025 -v

可以得到
p=290579950064240059571837821251441436997
q=314436328879392457343835667929324128609

利用 private.py 生成私钥文件，使用 openssl 即可
openssl rsautl -decrypt -in flag.enc -inkey private.pem -out res.txt

5. 利用n的公约数

给出两个 n，共同密钥 e，两个密文，且两个 n 有公因子

假设 n1 和 n2 的公因子为 q，由 q 和 n1 求得 p1，已知 p1 和 q，可以求得 d1，已知enc1，d1，n1可以求得明文

6. 共模攻击

收到两份密文c1、c2，是一个明文 m 由相同的 n 和不同的2个 e(e1，e2) 进行加密的，此时无需求解出 d 即可破解出明文

7. 小明文攻击

即明文过小，导致明文的 e 次方仍然小于 n ，在 e=3 或 e 较小时可以首先尝试这种方法

给出 flag.enc 和 pubkey.pem，flag.enc 可以参照上一种情况读取内容，pubkey.pem 可以使用 openssl 获取内容

8. 低解密指数攻击(RSA-wiener-attack)

在 e 过大时使用，可以直接使用 RSAwienerHacker.py 求出 d

9. n 可被分解为多个素数

求 d 时，再修改一下欧拉函数值即可

10. dp 泄露攻击

给出 n、e、dp、c 时，可求 d

11. dp、dq 泄露攻击

给出 dp、dq、p、q、c，可直接求出明文

12. 低加密指数广播攻击

待补充

一点点个人见解

个人发现的趋势

最近的比赛中有一个很明显的趋势，就是不再是单纯的考 RSA，而是结合其他数学问题，利用其他的数学问题求出 RSA 涉及到的变量

一个 RSA 对文件加密的代码

# -*- coding: utf-8 -*-
# python2
# author: peri0d
import gmpy2
import random
import binascii

# 欧几里得算法
def gcd(a,b):
    while a != 0:
        a, b = b%a, a
    return b

# 根据 p q d 求 d
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 modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
      raise Exception('modular inverse does not exist')
    else:
      return x % m

# hex 字符串转化为大整数
def hex2int(s):
    dict = {'a': 10, 'c': 12, 'b': 11, 'e': 14, 'd': 13, 'f': 15, '1': 1, '0': 0, '3': 3, '2': 2, '5': 5, '4': 4, '7': 7, '6': 6, '9': 9, '8': 8}
    t = len(s)-1
    sum = 0
    for i in range(len(s)):
        sum = sum + (dict[s[t-i]]*(16**i))
    return sum

# 生成 p q [e, d]
def init():

    # 初始化
    p = 0
    q = 0

    # 随机生成素数
    while (p-1)*(q-1)<65536:
        p = gmpy2.next_prime(random.randint(9000,10000))
        q = gmpy2.next_prime(random.randint(9000,10000))

        print u'随机生成的 p={0} q={1}'.format(p,q)

    # 随机生成 10 组 [e,d]
    key = []
    r = (p-1)*(q-1)

    while len(key)!=10:
        t = random.randint(65537, r)
        if gcd(t,r)==1 :
            e = t
            d = modinv(e, r)
            key.append([e,d])


    print u'生成的10组密钥为: '
    print key
    return p,q,key

# 明文处理, 每 3 个字符一组
def div_m(path):
    f = open(path,'r')
    s = ''
    for line in f:
        line = line.strip()
        s = s +  line
    s = binascii.b2a_hex(s)
    r = [s[i:i+6] for i in range(0,len(s),6)]
    f.close()
    return r
    # print r

# 加密
def rsa_encrypto(path,enc_path):
    global p,q,e

    r = div_m(path)

    # 加密，将密文输出到 enc_path
    for i in range(len(r)):
        r[i] = pow(hex2int(r[i]),e,int(p*q))

    f = open(enc_path, 'w')
    for i in r:
        f.write(str(i))
        f.write('\n')
    f.close()

# 解密
def rsa_decrypto(enc_path, dec_path):
    global p,q,d
    f1 = open(enc_path, 'r')
    f2 = open(dec_path, 'w')
    m = []
    for line in f1:
        line = line.strip()
        m.append(binascii.unhexlify(hex(pow(int(line),d,p*q))[2:]))

    f2.write(''.join(m))
    f1.close()
    f2.close()

# RSA 初始化
p,q,key = init()
choice = input('Select the key, enter sequence number from 0: ')
e = key[int(choice)][0]
d = key[int(choice)][1]
print u'选择的 p={0} q={1} e={2} d={3}'.format(p,q,e,d)

# rsa_encrypto('C:\Users\peri0d\Desktop\test.txt','C:\Users\peri0d\Desktop\test2.txt')
path = str(raw_input('Please enter the file path you want to encrypto: '))
enc_path = str(raw_input('Please enter path you want to save the ciphertext: '))
try:
    rsa_encrypto(path,enc_path)
except Exception as e:
    print 'somethin error'

dec_path = str(raw_input('Please enter path you want to save the plaintext: '))

# rsa_decrypto('C:\Users\peri0d\Desktop\test2.txt','C:\Users\peri0d\Desktop\test3.txt')
try:
    rsa_decrypto(enc_path,dec_path)
except Exception as e:
    print 'somethin error'

明文

RSA 总结