2017-11-14

CTF中RSA套路

以前一直用的是http://bobao.360.cn/learning/detail/3058.html这里的，可是发现这里面好久没更新了，想了想还是自己在整理一下吧。

具体RSA加解密算法就不介绍了，先看数据提取吧。

需要注意的是，代码中很多地方用到了gmpy2库，安装方法参考https://www.cnblogs.com/pcat/p/5746821.html

数据提取

一般来说，RSA基本围绕着c,m,e,d,p,q,n这几个参数展开，但是题目一般不会直接给参数，需要我们自己手工提取。

pem文件：针对这类文件可以直接使用openssl提取，大概使用过的方式有：

1 2	openssl rsautl -encrypt -in FLAG -inkey public.pem -pubin -out flag.enc openssl rsa -pubin -text -modulus -in warmup -in public.pem

pcap文件：针对这类文件可以使用wireshake follow一下。这种问题一般都是写了一个交互式crypto系统，可能产生多轮交互
ppc模式：这种模式是上述pcap文件的交互版，会给一个端口进行一些crypto的交互，参数会在交互中给出。

模数分解

已知e,p,q求d

1	d = gmpy2.invert(e, (p-1)*(q-1))

已知e,d,n求p,q

import random  
  
def gcd(a, b):  
   if a < b:  
     a, b = b, a  
   while b != 0:  
     temp = a % b  
     a = b  
     b = temp  
   return a  
  
def getpq(n,e,d):  
    p = 1  
    q = 1  
    while p==1 and q==1:  
        k = d * e - 1  
        g = random.randint ( 0 , n )  
        while p==1 and q==1 and k % 2 == 0:  
            k /= 2  
            y = pow(g,k,n)  
            if y!=1 and gcd(y-1,n)>1:  
                p = gcd(y-1,n)  
                q = n/p  
    return p,q  
  
def main():  
 
    n = 0xa66791dc6988168de7ab77419bb7fb0c001c62710270075142942e19a8d8c51d053b3e3782a1de5dc5af4ebe99468170114a1dfe67cdc9a9af55d655620bbab  
    e =  0x10001
    d =  0x123c5b61ba36edb1d3679904199a89ea80c09b9122e1400c09adcf7784676d01d23356a7d44d6bd8bd50e94bfc723fa87d8862b75177691c11d757692df8881
    p,q = getpq(n,e,d)  
    print "p: "+hex(p)
    print "q: "+hex(q)  
  
if __name__ == '__main__':  
    main()

在线分解n

http://factordb.com
通过在此类网站上查询n，如果可以分解或者之前分解成功过，那么可以直接得到p和q

yafu分解n

直接打开程序，然后输入factor($n)，$n为模数，此方法比上面的在线要好用很多

公约数分解n

识别此类题目，通常会发现题目给了多个n，均不相同，并且都是2048bit，4096bit级别，无法正面硬杠，并且明文都没什么联系，e也一般取65537。可以直接gcd(n1,n2)求出一个因数。如下:

1
2

n1=9051013965404084482870087864821455535159008696042953021965631089095795348830954383127323853272528967729311045179605407693592665683311660581204886571146327720288455874927281128121117323579691204792399913106627543274457036172455814805715668293705603675386878220947722186914112990452722174363713630297685159669328951520891938403452797650685849523658191947411429068829734053745180460758604283051344339641429819373112365211739216160420494167071996438506850526168389386850499796102003625404245645796271690310748804327
n2=13225948396179603816062046418717214792668512413625091569997524364243995991961018894150059207824093837420451375240550310050209398964506318518991620142575926623780411532257230701985821629425722030608722035570690474171259238153947095310303522831971664666067542649034461621725656234869005501293423975184701929729170077280251436216167293058560030089006140224375425679571181787206982712477261432579537981278055755344573767076951793312062480275004564657590263719816033564139497109942073701755011873153205366238585665743

可以直接用公约数分解n，求得p,q

def gcd(a, b):
   if a < b:
     a, b = b, a
   while b != 0:
     temp = a % b
     a = b
     b = temp
   return a
n1=9051013965404084482870087864821455535159008696042953021965631089095795348830954383127323853272528967729311045179605407693592665683311660581204886571146327720288455874927281128121117323579691204792399913106627543274457036172455814805715668293705603675386878220947722186914112990452722174363713630297685159669328951520891938403452797650685849523658191947411429068829734053745180460758604283051344339641429819373112365211739216160420494167071996438506850526168389386850499796102003625404245645796271690310748804327
n2=13225948396179603816062046418717214792668512413625091569997524364243995991961018894150059207824093837420451375240550310050209398964506318518991620142575926623780411532257230701985821629425722030608722035570690474171259238153947095310303522831971664666067542649034461621725656234869005501293423975184701929729170077280251436216167293058560030089006140224375425679571181787206982712477261432579537981278055755344573767076951793312062480275004564657590263719816033564139497109942073701755011873153205366238585665743
print "p: "+str(gcd(n1,n2))
print "q1: "+str(n1/gcd(n1,n2))
print "q2: "+str(n2/gcd(n1,n2))

低加密指数攻击

e=3时的小明文攻击

当e=3时，如果明文过小，导致明文的三次方仍然小于n，那么通过直接对密文三次开方，即可得到明文。如果明文的三次方虽然比n大，但是大不了多少，则可以爆破。如下代码:

i=0
   while 1:
   if(gmpy2.root(c+i*N, 3)[1]==1):
     print gmpy2.root(c+i*N, 3)
     break
   i=i+1

低加密指数广播攻击

如果选取的加密指数较低，并且使用了相同的加密指数给一个接受者的群发送相同的信息，那么可以进行广播攻击得到明文。
这个识别起来比较简单，一般来说都是给了三组加密的参数和明密文，其中题目很明确地能告诉你这三组的明文都是一样的，并且e都取了一个较小的数字。

低解密指数攻击

识别：e看起来特别大就行了
github上有开源的攻击代码https://github.com/pablocelayes/rsa-wiener-attack
这里注意一个细节问题，如果在运行脚本的时候报错，请在脚本前加上：

1 2	import sys sys.setrecursionlimit(10000000)

题目：

Bob is extremely paranoid, so he decided that just one RSA encryption is not enough. Before sending his message to Alice, he forced her to create 5 public keys so he could encrypt his message 5 times! Show him that he still is not secure.
Here are the 5 public keys that Bob used, each in the format of (N, e):
(9247606623523847772698953161616455664821867183571218056970099751301682205123115716089486799837447397925308887976775994817175994945760278197527909621793469, 11)
(9247606623523847772698953161616455664821867183571218056970099751301682205123115716089486799837447397925308887976775994817175994945760278197527909621793469, 41)
(9247606623523847772698953161616455664821867183571218056970099751301682205123115716089486799837447397925308887976775994817175994945760278197527909621793469, 67623079903)
(9247606623523847772698953161616455664821867183571218056970099751301682205123115716089486799837447397925308887976775994817175994945760278197527909621793469, 5161910578063)
(9247606623523847772698953161616455664821867183571218056970099751301682205123115716089486799837447397925308887976775994817175994945760278197527909621793469, 175238643578591220695210061216092361657427152135258210375005373467710731238260448371371798471959129039441888531548193154205671)
Here is his encrypted message:
7117565509436551004326380884878672285722722211683863300406979545670706419248965442464045826652880670654603049188012705474321735863639519103720255725251120

根据题意，用一样的n不同的e来加密5次，其实效果和用5个e的乘积加密一次是一样的。其实如果5个e的乘积来加密的话，e很大的话就可以用低解密指数攻击来了。

import ContinuedFractions, Arithmetic, RSAvulnerableKeyGenerator
def hack_RSA(e,n):
    '''
    Finds d knowing (e,n)
    applying the Wiener continued fraction attack
    '''
    frac = ContinuedFractions.rational_to_contfrac(e, n)
    convergents = ContinuedFractions.convergents_from_contfrac(frac)
    
    for (k,d) in convergents:
        
        #check if d is actually the key
        if k!=0 and (e*d-1)%k == 0:
            phi = (e*d-1)//k
            s = n - phi + 1
            # check if the equation x^2 - s*x + n = 0
            # has integer roots
            discr = s*s - 4*n
            if(discr>=0):
                t = Arithmetic.is_perfect_square(discr)
                if t!=-1 and (s+t)%2==0:
                    print("Hacked!")
                    return d
(n1,e1)=(9247606623523847772698953161616455664821867183571218056970099751301682205123115716089486799837447397925308887976775994817175994945760278197527909621793469, 11)
(n2,e2)=(9247606623523847772698953161616455664821867183571218056970099751301682205123115716089486799837447397925308887976775994817175994945760278197527909621793469, 41)
(n3,e3)=(9247606623523847772698953161616455664821867183571218056970099751301682205123115716089486799837447397925308887976775994817175994945760278197527909621793469, 67623079903)
(n4,e4)=(9247606623523847772698953161616455664821867183571218056970099751301682205123115716089486799837447397925308887976775994817175994945760278197527909621793469, 5161910578063)
(n5,e5)=(9247606623523847772698953161616455664821867183571218056970099751301682205123115716089486799837447397925308887976775994817175994945760278197527909621793469, 175238643578591220695210061216092361657427152135258210375005373467710731238260448371371798471959129039441888531548193154205671)
c=7117565509436551004326380884878672285722722211683863300406979545670706419248965442464045826652880670654603049188012705474321735863639519103720255725251120
e=e1*e2*e3*e4*e5%n1
d=hack_RSA(e,n1)
m=pow(c,d,n1)
print '{:x}'.format(m).decode('hex')

运行的时候如果报import包不存在，那是因为没有把https://github.com/pablocelayes/rsa-wiener-attack里面所有的py文件放在同一目录下。

共模攻击

识别：若干次加密，e不同，n相同，m相同。就可以在不分解n和求d的前提下，解出明文m。
已知e1,e2,n,c1,c2

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
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=(pow(c1,s1,n)*pow(c2,s2,n)) % n
print '{:x}'.format(m).decode('hex')

已知dp,dq求解

其实这种方法很简单，但是由于我当时做的时候查了好久dp,dq是什么，所以还是记录下来扫个坑吧。
这种参数是为了让解密的时候更快速产生的，其中:

1 2	dp=d%(p-1) dq=d%(q-1)

解密全部代码如下:

InvQ=gmpy2.invert(q,p)
mp=pow(c,dp,p)
mq=pow(c,dq,q)
m=(((mp-mq)*InvQ)%p)*q+mq
print '{:x}'.format(m).decode('hex')

隐藏小私有指数δ的RSA后门密钥生成算法

以下题目来自于hctf2016
http://0x48.pw/2016/11/28/0x28/
https://github.com/Hcamael/ctf-library/tree/master/RSA1
https://github.com/Hcamael/ctf-library/blob/master/RSA1/rsa1_payload.py
算法原理如下：

攻击方法也很简单

解题关键是在下图

根据rsa-wiener-attack我们可以知道，在rsa算法中，如果密钥d特别小，则我们可以根据e,n直接求出d，所以上图满足条件。

而当我们求出了那两个东西(原谅我打不出来…),则和已知e,d,n求p,q的情况一样了，当p,q已知的时候就可以解出d了

基于隐藏素数因子的RSA-HPβ算法(高比特位已知分解)

以下题目来自于hctf2016
https://github.com/Hcamael/ctf-library/tree/master/RSA2
payload:

1 2	https://github.com/Hcamael/ctf-library/blob/master/RSA2/rsa2_payload.py https://github.com/Hcamael/ctf-library/blob/master/RSA2/rsa2_payload.sage

该后门算法依赖于Coppersmith partial information attack算法, sage实现该算法，sage安装详细看我的另一篇关于sage的安装。

Coppersmith partial information attack算法可以理解成，当我们已知素数p或者q的前一定位数，可以根据这个算法还原完整的p，q。
算法实现代码：https://github.com/Gao-Chuan/RSA-and-LLL-attacks

例题如下：

仔细观察算法，n是靠t,u,r来拼接成，而u是根据p的前5k/16位进行des转置得到的，所以当我们已知n的前提下，相当于我们已知p的前5k/16位。这就是我们利用的点。如下图：

利用代码如下:


p4 = 0xf3a5f928e11c5901f9f4289e513f046748efb99d4f8e706e207a943e1d2c9df43feab38e20c2106d87167e5501ac41adfc4912732457103a4359e5b433da78f39ad6f206b8f170192aa0841feb501ce1
n = 0x7e7007c7c85788b9b77cda64c9b3f5d2a795fe1b1f8d3f120288a30a168c3ea932c7574700ff0f596c5ad04a703756aedc66b9b9e44911d55f0a72a1cc1a569cee02a84499cdb091b8471a8e6cc0ebca583dfd6fb8d5fecf32ff67d2ddeaaaaf9c71a10009b4218fc57743675f283d22734ac7ade2ca240772d11b5783755378f7c30988f41d4a9d62561ea6e5f2f21d3d44e8689e781d3f61356123929457d17b07a1d04741bf970afb590cd820dd12cf88f68b0e896388f433fd2adf3354353c9c56abb0cfea223387e6d0b2df10e450c621ac153e47369f888fdc0b39c842a5ddc6a11339862ccdb4be97a81445205fb8f8bde9daaad5d0dc2ea5bd3b8c43
//p的位数
pbits = 1024
//p未知的位数
kbits = pbits - p4.nbits()
print p4.nbits()
p4 = p4 << kbits
PR.<x> = PolynomialRing(Zmod(n))
//f是原始的p
f = x + p4
x0 = f.small_roots(X=2^kbits, beta=0.4)[0]
print "x: %s" %hex(int(x0))
p = p4+x0
print "p: ", hex(int(p))
assert n % p == 0
q = n/int(p)
print "q: ", hex(int(q))

第二届强网杯_nextrsa_Coppersmith

题目描述是，加密指数e=3，同时已知明文的高位，参数如下：

# n=0x79982a272b9f50b2c2bc8b862ccc617bb39720a6dc1a22dc909bbfd1243cc0a03dd406ec0b1a78fa75ce5234e8c57e0aab492050906364353b06ccd45f90b7818b04be4734eeb8e859ef92a306be105d32108a3165f96664ac1e00bba770f04627da05c3d7513f5882b2807746090cebbf74cd50c0128559a2cc9fa7d88f7b2d
# e=0x3
# c=0x381db081852c92d268b49a1b9486d724e4ecf49fc97dc5f20d1fad902b5cdfb49c8cc1e968e36f65ae9af7e8186f15ccdca798786669a3d2c9fe8767a7ae938a4f9115ae8fed4928d95ad550fddd3a9c1497785c9e2279edf43f04601980aa28b3b52afb55e2b34e5b175af25d5b3bd71db88b3b31e48a177a469116d957592c
# b=0xfedcba98765432100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
# m=b+x (x:64bit)

其中不知道的就是64比特的x，不过根据以下代码就可以算出x：

e = 0x3
b = b=0xfedcba98765432100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
n = 0x79982a272b9f50b2c2bc8b862ccc617bb39720a6dc1a22dc909bbfd1243cc0a03dd406ec0b1a78fa75ce5234e8c57e0aab492050906364353b06ccd45f90b7818b04be4734eeb8e859ef92a306be105d32108a3165f96664ac1e00bba770f04627da05c3d7513f5882b2807746090cebbf74cd50c0128559a2cc9fa7d88f7b2d
c=0x381db081852c92d268b49a1b9486d724e4ecf49fc97dc5f20d1fad902b5cdfb49c8cc1e968e36f65ae9af7e8186f15ccdca798786669a3d2c9fe8767a7ae938a4f9115ae8fed4928d95ad550fddd3a9c1497785c9e2279edf43f04601980aa28b3b52afb55e2b34e5b175af25d5b3bd71db88b3b31e48a177a469116d957592c
kbits=64
PR.<x> = PolynomialRing(Zmod(n))
f = (x + b)^e-c
x0 = f.small_roots(X=2^kbits, beta=1)[0]
print "x: %s" %hex(int(x0))

强网杯_nextrsa_nextprime

参数如下：

# n=0x78e2e04bdc50ea0b297fe9228f825543f2ee0ed4c0ad94b6198b672c3b005408fd8330c36f55d36fb129d308c23e5cb8f4d61aa7b058c23607cef83d63c4ed0f066fc0b3c0062a2ac68c75ca8035b3bd7a320bdf29cfcf6cc30377743d2a8cc29f7c588b8043412366ab69ec824309cb1ef3851d4fb14a1f0a58e4a1193f5518fa1d0c159621e1f832b474182593db2352ef05101bf367865ad26efe14fce977e9e48d3310a18b67991958d1a01bd0f3276a669866f4deaef2a68bfaefd35fe2ba5023a22c32ae8b2979c26923ee3f855363f18d8d58bb1bc3b7f585c9d9f6618c727f0f7b9e6f32af2864a77402803011874ed2c65545ced72b183f5c55d4d1
# e=0x10001
# nextprime(p)*nextprime(q)=0x78e2e04bdc50ea0b297fe9228f825543f2ee0ed4c0ad94b6198b672c3b005408fd8330c36f55d36fb129d308c23e5cb8f4d61aa7b058c23607cef83d63c4ed0f066fc0b3c0062a2ac68c75ca8035b3bd7a320bdf29cfcf6cc30377743d2a8cc29f7c588b8043412366ab69ec824309cb1ef3851d4fb14a1f0a58e4a1193f5a58ee70a59ac06b64dbe04b876ff69436b78cf03371f2062707897bf4e580870e42b5e62709b69f6d4939ac5641ea0f29de44aaee8f2fcd0f66aaa720b584f7c801e52ce7cd41db45ceb99ebd7b51bef8d0cd2deb5c50b59f168276c9c98d46a1c37bd3d6ef81f2c6e89028680a172e00d92dd8b392135112dd16efab57d00b26b9
# c=0x1c3588ac81ec3d1b439cfd2d5e6e8a5a95c8f95aaeff1b0ba49276ade80435323f307a17006ae2ffb4ca321e54387d9b33ed7ccda3117f7bc8d247ffd2ccdd67b7e2aad3d908d0a5187a73d13d532c1cf41758e2743bd4359bf72a99bbf0d716bb171cf636bd56acee9551cbb8af25f32583facbd25aed232659d24580c5a30a080e2860790a65422f7c442559c3042d37fdd7e8c1dd604252a2cbff8c74e5a0b6a0dfb9dcfed9eed515705ab9214dcf2dabce7b354040940613d065918079b3197da948b6d1d7daccc417069f7102fd2525e879fe69b6d5fb39e1dd6c0a9a9087dcc809294d7774efb42829f6124dff4af44f308977d1f91422c63073176026

方法一：

#!/usr/bin/env python
# -*- coding: utf-8 -*-
__Auther__ = 'M4x'
from gmpy2 import is_prime as prime
from gmpy2 import iroot
n = 15260473398916071686287752340249158279343013077145667794514717692352941873466690686288442204714585854869226872705293008837554012949598044297596015507031315006195230644722581744643756573982729344499452200116366327869178694692162014446578711956663348262932703160394101606708475725742890049311933691849747707673216322758418530420118502556719323543077771821163439824876751874675862075401986796272014746925015772045578403357300038192830197985871077621213669817380577176611560467051848951044963527185916781094981810804641387975398361694935093473717039550361644252381923994841138817152748279477868854093033234031994635408593
nn = 15260473398916071686287752340249158279343013077145667794514717692352941873466690686288442204714585854869226872705293008837554012949598044297596015507031315006195230644722581744643756573982729344499452200116366327869178694692162014446578711956663348262932703160394101606708475725742890049311933691849747707914818082716474881224336472709074679047145667796106895298086129057288449508218237679974321952279429832707229303594474494519945899481320231091983665654947081839784375373657345023890332691371443571370016623789041883821610353473726465037590414008198228956920913181526550775524028059426312173493877228564452496582329
#  print nn > n
t = nn - n
f1 = lambda x, y: pow(x * y - t, 2) - 4 * n * x * y
f2 = lambda x, y, s: (t - x * y - s) / (2 * x)
for x in xrange(1, 3000):
    for y in xrange(1, 3000):
        print x, y
        if f1(x, y) >= 0:
            s, b = iroot(f1(x, y), 2)
            if b:
                if prime(f2(x, y, int(s))):
                    print "Success"
                    print f2(x, y, int(s))
                    exit()

就是

pq = n
(p + x)(q + y) = n'
-> xy + py + qx = t(t = n' - n)
-> xq^2^ + (xy - t)q + ny = 0
则该方程有素数接即可，可爆破x，y

方法二：
因为n = p * q,nn = p1 * q1
因为n和nn很相近，所以nnn讲道理用yafu很快就能跑出来
可以得到`t1 = pq1,t2 = q*p1 `
然后gcd一下就可以了

赏

纯属好玩

扫码打赏，你说多少就多少

打开支付宝扫一扫，即可进行扫码打赏哦

本文标题:CTF中RSA套路

文章作者:Err0rzz

发布时间:2017年11月14日 - 19时16分

最后更新:2018年05月23日 - 10时15分

原始链接:http://Err0rzz.github.io/2017/11/14/CTF中RSA套路/

许可协议: "署名-非商用-相同方式共享 3.0" 转载请保留原文链接及作者。