CTF中RSA加密的简单学习

素数（质数）：一个数如果除了1和它本身外不能再被其他整数整除，那么这个数就是素数比如17。

互质数（互素数）：公约数只有1的两个整数称为互质数比如13和17.

该工具是一款命令行工具，包含32和64两个版本，可以将n直接输入到命令行中，也可以在文件中读取，使用参数-v可以看到运行的详细信息。但当n较长的时候还是不适用。[dl href=’https://sourceforge.net/projects/msieve/’]下载Msieve[/dl]

这个就是神器了，就算n较长也是可以分解的（相对于msieve）而言个人感觉比较强大，非常推荐。

[dl href=’https://sourceforge.net/projects/yafu/’]下载yafu[/dl]
下面讲解一个简单的例子：

题目链接：http://ctf5.shiyanbar.com/crypto/RSAROLL.txt

{920139713,19}
 
704796792
752211152
274704164
18414022
368270835
483295235
263072905
459788476
483295235
459788476
663551792
......
......

大括号中应该对应的是n和e，因为n不大，所以我们只需要分解出p和q即可求出密钥d。然后下面的每一行应该是一个密文，等我们拿到密钥，然后按行解密即可，下面是解题脚本。

#coding:utf-8

def crackN(n):
i = 2
while i < n :
if n % i == 0:
break
i = i+1
return i

n = 920139713
e = 19

p = crackN(n)
q = n / p

fn = (p-1)*(q-1)

i = 1
d = 0
while (True):
if (fn * i +1) % e == 0 :
d = (fn * i +1) / e
break
i = i+1

print "d:%s" % d

c = open("c.txt")
m = ''
for line  in c:
line = line.replace('\n','')
m += chr(pow(int(line), d , n))
print m

运行结果如下：

这道题目算是常规题了，题目中的n非常小，但是我们通常遇到的n因该是比较大的，普通的脚本跑出来是非常慢的，需要借助工具，但是本题就直接写了个小函数分解n了。

还有一类题目也是类似分解n的，只不过是采用了文件的形式，公钥和私钥都是文件，通常是key和pem为扩展名的文件。这类题目需要借助openssl工具分析出公钥中的n和e，然后套路就和上面差不多了，分解n，然后计算出私钥，但是要使写脚本自己生产私钥，并且解密密文文件也需要openssl命令来执行，下面介绍一下这个流程的命令和脚本。

假如有一个公钥文件public.pem，密文文件flag.enc

使用下面的命令分析公钥：

运行结果中将拿到n值和加密指数e

如果n不大，我们可以使用工具yafu分解n，命令如下

我们到这里已经拿到了p和q的值，下面我们来生产私钥文件，脚本如下：

import math
import sys
from Crypto.PublicKey import RSA

keypair = RSA.generate(1024)

keypair.p = 0xD7DB8F68BCEC6D7684B37201385D298B
keypair.q = 0xC292A272E8339B145D9DF674B9A875D5
keypair.e = 65537

keypair.n = keypair.p * keypair.q
Qn = long((keypair.p-1) * (keypair.q-1))

i = 1
while (True):
    x = (Qn * i ) + 1
    if (x % keypair.e == 0):
        keypair.d = x / keypair.e
        break
    i += 1

private = open('private.pem','w')
private.write(keypair.exportKey())
private.close()

请自行修改脚本中的p、q、e的值，我们将拿到私钥文件private.pem，下一步将进行解密，命令如下：

此命令的含义是采用私钥文件private.pem来解密文件flag.enc，结果保存到flag.txt中，到此位置，我们就完整的解出了这道题目。如需要题目文件请留言。

0x07 RSA共享素数攻击

这类题目其实还不是很常见，但也简单的介绍一下。当我们生成p和q的时候，难免有重复的，比如我们使用了p、q1和p、q2生成了n1和n2，就可以说我们的q被n1和n2共享了，如果我们能拿到这两个n，那么我们很容易就可以得到q1和q2，为什么呢？因为我们可以使用最大公约数gcd算法很快的计算出q，那么q1和q2也就很容易计算出来了，后面就不用再说了，直接计算d然后用私钥解密即可。

0x08 RSA共模攻击

这种攻击方式还是很常见了，该攻击的基本条件如下：

• 同一份明文m使用不同的秘钥加密了两次
• 两次生成秘钥时模数n相同但加密指数e不相同
• 我们能拿到两个不同的密文c1、c2和模数n、加密指数n1、n2

在满足上面条件的情况下我们可以在不用获得秘钥d的情况下解密出明文m，基本的数学原理这里不做赘述，可自行百度研究，下面直接给出解密脚本。

#coding=utf-8
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
def main():
n = int(raw_input("input n:"))
c1 = int(raw_input("input c1:"))
c2 = int(raw_input("input c2:"))
e1 = int(raw_input("input e1:"))
e2 = int(raw_input("input e2:"))
s = egcd(e1, e2)
s1 = s[1]
s2 = s[2]
# 求模反元素
if s1<0:
s1 = - s1
c1 = modinv(c1, n)
elif s2<0:
s2 = - s2
c2 = modinv(c2, n)
m = (c1**s1)*(c2**s2)%n
print m
if __name__ == '__main__':
main()

脚本来自互联网，非原创并未测试，若有问题还请留言。

0x09 RSA低加密指数攻击

所谓低加密指数指的就是e非常小的情况下，通常为3，再CTF中也是有可能出现着用题目的，这种题目通常有两种类型，一种直接爆破，另外一种是低指数广播攻击。

首先介绍比较简单的情况，比如我们的e为3，n很淡，但是明文缺很小。这种情况下回出现什么呢？我们先看一下加密公式：c = m^e mod n , 当我们的 m^e < n 的情况下 c将等于m^e ，又因为e很小，所以我们可以直接对c开方求得明文m。 上面说的是m^e < n 的情况，那如果m^e > n 呢? 注意 m^e不能太大，否则将很难爆破。我们可以尝试进行爆破，假设我们 m^e / n 商 k 余数为c ,这里的k就是我们的商了，c就是模值，所已m^e =n*k+c , 我们可以对k进行爆破然，只要n*k+c的结果可以开方就可以求得明文m。

0x0A RSA低加密指数广播攻击

首先介绍什么是广播，加入我们需要将一份明文进行多份加密，但是每份使用不同的密钥，密钥中的模数n不同但指数e相同且很小，我们只要拿到多份密文和对应的n就可以利用中国剩余定理进行解密。关于中国剩余定理请参考文章：点击查看 。

只要满足一下情况，我们便可以考虑使用低加密指数广播攻击：

• 加密指数e非常小
• 一份明文使用不同的模数n，相同的加密指数e进行多次加密
• 可以拿到每一份加密后的密文和对应的模数n、加密指数e

攻击脚本如下：

# coding:utf8

from struct import pack,unpack
import zlib
import gmpy
def my_parse_number(number):
    string = "%x" % number
    #if len(string) != 64:
    #    return ""
    erg = []
    while string != '':
        erg = erg + [chr(int(string[:2], 16))]
        string = string[2:]
    return ''.join(erg)
def extended_gcd(a, b):
    x,y = 0, 1
    lastx, lasty = 1, 0
    while b:
        a, (q, b) = b, divmod(a,b)
        x, lastx = lastx-q*x, x
        y, lasty = lasty-q*y, y
    return (lastx, lasty, a)
def chinese_remainder_theorem(items):
  N = 1
  for a, n in items:
    N *= n
  result = 0
  for a, n in items:
    m = N/n
    r, s, d = extended_gcd(n, m)
    if d != 1:
      N=N/n
      continue
      #raise "Input not pairwise co-prime"
    result += a*s*m
  return result % N, N
sessions=[
{"c": 18547562724906720577486693684739489152547099593770967227662477478402201412715, "e": 7, "n": 53005661126534868602318707133611899019730819612971397126467405275805291247593},
{"c": 38080214796844206733759849504393184114911570888290711280913147447511559455673, "e": 7, "n": 84080528857266683438885394596690106809484104855460348347690627904896317465537},
{"c": 64341186257788012263409881160841287235929197643049077877015427200375821245501, "e": 7, "n": 84173503532728082763432007316428245924416536365662064681543769793438063575441}
]

data = []
for session in sessions:
    e=session['e']
    n=session['n']
    msg=session['c']
    data = data + [(msg, n)]
print "Please wait, performing CRT"
x, n = chinese_remainder_theorem(data)
e=session['e']
realnum = gmpy.mpz(x).root(e)[0].digits()
print my_parse_number(int(realnum))

ps：以上脚本来自互联网，使用时请自行修改脚本中的参数。

运行结果如下图：