RSA算法及攻击方法(二)

发表于 | 分类于 | | 热度: ℃
字数统计: 5,356 | 阅读时长 ≈ 27

0x00 前言

上一篇文章介绍了RSA的加解密过程及相关的数学基础以及对应的基础CTF题目,下面介绍几种针对加密过程中不同参数的攻击方法.

0x01 加密指数e

Rabin加密

Rabin加密是RSA的衍生算法,e==2是Rabin加密的典型特征,加密过程可以表示为c = m^2 mod n, 解密过程为m = c^(1/2) mod n.

详细算法可以参考Rabin加密体制

python实现

1
2
3
4
5
6
7
8
9
10
11
def rabin_decrypt(c, p, q, e=2):
  n = p * q
  mp = pow(c, (p + 1) / 4, p)
  mq = pow(c, (q + 1) / 4, q)
  yp = gmpy2.invert(p, q)
  yq = gmpy2.invert(q, p)
  r = (yp * p * mq + yq * q * mp) % n
  rr = n - r
  s = (yp * p * mq - yq * q * mp) % n
  ss = n - s
  return (r, rr, s, ss)

以上函数返回四个数字，其中只有一个是我们想要的明文，需要通过其他的方法进行验证。

典型题目

题目来源： Jarvis OJ hard RSA

题目分析：题目给出了.enc文件和.pem文件,我们使用openssl命令读取后发现该加密的加密指数e=2,属于典型的Rabin加密体系，考虑使用脚本进行解密。

解题脚本: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import gmpy2，libnum
n=0xC2636AE5C3D8E43FFB97AB09028F1AAC6C0BF6CD3D70EBCA281BFFE97FBE30DD
p=275127860351348928173285174381581152299
q=319576316814478949870590164193048041239
e=2
c=int(open(filepath,'rb').read().encode('hex'),16)
mp=pow(c,(p+1)/4,p)
mq=pow(c,(q+1)/4,q)
yp=gmpy2.invert(p,q)
yq=gmpy2.invert(q,p)
r=(yp*p*mq+yq*q*mp)%n
rr=n-r
s=(yp*p*mq-yq*q*mp)%n
ss=n-s
print libnum.n2s(r)
print libnum.n2s(rr)
print libnum.n2s(s)
print libnum.n2s(ss)

低加密指数攻击

当加密指数e较小且明文m也不大时,由于m^e=k*n+m中的k很小甚至为0,我们可以爆破k或者直接开e次方即可.

python实现

1
2
3
4
5
6
def small_msg(e, n, c):
  print time.asctime(), "Let's waiting..."
  for k in xrange(200000000):
      if gmpy2.iroot(c + n * k, e)[1] == 1:
          print time.asctime(), "...done!"
          return gmpy2.iroot(c + n * k, e)[0]

典型题目

题目来源：Jarvis OJ Extremely hard RSA

题目分析：该题目提供的n为4096位,e=3.我们可以使用上述脚本进行爆破.判断停止条件为开三次方根的结果为整数,使用的开方函数为gmpy2.iroot()

解题脚本：

1
2
3
4
5
6
7
8
9
10
11
12
13
import gmpy2,binascii,libnum,time
n=given_n(hex)
e=3
res=0
c=int(open(filepath, 'rb').read().encode('hex'),16)
print time.asctime()
for i in xrange(200000000):
  if gmpy2.iroot(c+n*i,3)[1]==1:
      res=gmpy2.iroot(c+n*i,3)[0]
      print i,res
      print libnum.n2s(res)
      print time.asctime()
      break

低加密指数广播攻击

如果模数n和密文c不同,而明文m和加密指数e相同.一般取e=k,k为所给数据的数量且e较小.在题目中会得到多个形如m^e == ci (mod ni)的加密等式.取e=3,则有: 

1
2
3
c1 = m^e mod n1
c2 = m^e mod n2
c3 = m^e mod n3

对上述等式运用中国剩余定理,在e=3时,有:
cx = m^3 mod n1*n2*n3
对cx进行开方即可求得明文.

典型例题

题目来源：2018强网杯nextrsa-Level9

题目分析： 该题目给出了c1,c2,c3,n1,n2,n3,我们考虑使用中国剩余定理CRT()函数和iroot()函数进行爆破.

解题脚本： 

1
2
3
4
5
6
7
8
9
m = random.randint(0x100000000000, 0xffffffffffff)
e = 3
n1 = modulus1
n2 = modulus2
n3 = modulus3
c1 = pow(m, e, n1)
c2 = pow(m, e, n2)
c3 = pow(m, e, n3)
print m == gmpy2.iroot(CRT([n1, n2, n3], [c1, c2, c3]), e)[0]

CopperSmith Theorem

该定理指出在一个e阶的模n多项式f(x)中,如果有一个根小于$ n^{1/e} $,就可以运用一个$ O(log n) $的算法求出这些根。当本定理运用在rsa算法中,如果e=3并且明文当中有三分之二比特是已知的,这种算法可以还原出明文中所有的比特.

sage实现的解密脚本如下：

1
2
3
4
5
6
7
8
9
10
11
n= number1(hex)
p=0xBCF6D95C9FFCA2B17FD930C743BCEA314A5F24AE06C12CE62CDB6E8306A545DE468F1A23136321EB82B4B8695ECE58B763ECF8243CBBFADE0603922C130ED143D4D3E88E483529C820F7B53E4346511EB14D4D56CB2B714D3BDC9A2F2AB655993A31E0EB196E8F63028F9B29521E9B3609218BA0000000000000000000000000
p_fake = p+0x10000000000000000000000000
pbits = 1024
kbits = pbits-576
pbar = p_fake & (2^pbits-2^kbits)
print "upper %d bits (of %d bits) is given" % (pbits-kbits, pbits)
PR.<x> = PolynomialRing(Zmod(n))
f = x + pbar
x0 = f.small_roots(X=2^kbits, beta=0.4)[0]  # find root < 2^kbits with factor >= n^0.4
print x0 + pbar

详细解释参考Coppersmith及维基百科说明

sage在线运行

e与$\phi$(n)不互素

只有当e与$\phi$(n)互素时,才能保证e的逆元d唯一存在.当二者不互素时,我们通过gcd()操作寻找与$\phi$(n)互素的数,然后进行求解.我们通过一个例题来说明.

题目描述： 

1
2
3
4
5
6
7
8
9
10
n1=0xcfc59d54b4b2e9ab1b5d90920ae88f430d39fee60d18dddbc623d15aae645e4e50db1c07a02d472b2eebb075a547618e1154a15b1657fbf66ed7e714d23ac70bdfba4c809bbb1e27687163cb09258a07ab2533568192e29a3b8e31a5de886050b28b3ed58e81952487714dd7ae012708db30eaf007620cdeb34f150836a4b723L
e1=0xfae3aL
c1=0x81523a330fb15125b6184e4461dadac7601340960840c5213b67a788c84aecfcdc3caf0bf3e27e4c95bb3c154db7055376981972b1565c22c100c47f3fa1dd2994e56090067b4e66f1c3905f9f780145cdf8d0fea88a45bae5113da37c8879c9cdb8ee9a55892bac3bae11fbbabcba0626163d0e2e12c04d99f4eeba5071cbeaL
n2=0xd45304b186dc82e40bd387afc831c32a4c7ba514a64ae051b62f483f27951065a6a04a030d285bdc1cb457b24c2f8701f574094d46d8de37b5a6d55356d1d368b89e16fa71b6603bd037c7f329a3096ce903937bb0c4f112a678c88fd5d84016f745b8281aea8fd5bcc28b68c293e4ef4a62a62e478a8b6cd46f3da73fa34c63L
e2=0x1f9eaeL
c2=0x4d7ceaadf5e662ab2e0149a8d18a4777b4cd4a7712ab825cf913206c325e6abb88954ebc37b2bda19aed16c5938ac43f43966e96a86913129e38c853ecd4ebc89e806f823ffb802e3ddef0ac6c5ba078d3983393a91cd7a1b59660d47d2045c03ff529c341f3ed994235a68c57f8195f75d61fc8cac37e936d9a6b75c4bd2347L
assert pow(flag,e1,n1)==c1
assert pow(flag,e2,n2)==c2
assert gcd(e1,(p1-1)*(q1-1))==14
assert gcd(e2,(p2-1)*(q2-1))==14

题目分析： 题目给出了n1和n2,我们联想到公约数,通过p=gcd(n1,n2)求得p,进而求出q1和q2.此时我们发现e与$\phi$(n)不互素.

如果我们需要求逆元,则需要找到与$\phi$(n)互素的数.

1.png-11.4kB

我们已知b=14,通过上面的推算我们可得a与$\phi$(n)互素,于是求出b*d = gmpy2.invert(a,phin),进而求出d.可是经测试发现明文为乱码.

根据推导的最后一个公式,b*d可作为私钥求解出m^14.我们得到一个同余方程组.

2.png-4kB

进一步推导

3.png-5.4kB

可以运用中国剩余定理计算特解m,即m=solve_crt([m1,m2,m3], [q1,q2,p]).如果模n1,n2不行那么可以转换为模q1*q2,从而有$ res \equiv m^14 mod q1*q2 $.

这样就转换成一个新的rsa问题,且e=14.此时e与$\phi (n)=(q1-1)*(q2-1) $还有公因数2.那么我们参照上述思路,可以得出m^2满足的方程,从而开方求结果.

5.png-7.9kB

解题脚本如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
from libnum import *
import gmpy2
p=gcd(n1,n2)
q1=n1/p
q2=n2/p
assert(p*q1==n1)
assert(p*q2==n2)
f1=(p-1)*(q1-1)
f2=(p-1)*(q2-1)
tmp=14

e1=e1/tmp
e2=e2/tmp
bd1=invmod(e1,f1)
bd2=invmod(e2,f2)

m1=pow(c1,bd1,n1)
m2=pow(c2,bd2,n2)
m3=m1%p
m2=m2%q2
m1=m1%q1

m=solve_crt([m1,m2,m3], [q1,q2,p]) 
print m
n=q1*q2
f=(q1-1)*(q2-1)
m=m%n
2d=invmod(7,f)
m=pow(m,2d,n)
print n2s(gmpy2.iroot(m, 2)[0])

0x02 解密指数d

低解密指数攻击

如果满足条件d < (1/3)*n^(1/4),那么一种基于连分数的特殊攻击类型就可以危害RSA的安全.此时需要满足q<p<2*q,则可以通过Wiener Attack在多项式时间中分解n.常适用于e过大或过小的情况.为了理解这个过程,我们讲解维纳定理相关知识.

Wiener’s Theorem

  • 连分数展开: [a0,a1,a2,....,an]

    1.png-5kB)

    举例如下:
    3.png-28.3kB

  • 渐近分数

    2.png-0.8kB

  • 定理内容
    如果N = p*q, q<p<2*q, d<(1/3)*N^(1/4),且已知(e,N)满足$ e*d \equiv 1 mod \phi(N) $,攻击者可以从e/N的连分数的渐近分数中找到正确的k/d从而获得密钥d.

  • 举例

    已知(N,e)=(90581,17993),首先求e/N的连分数的渐近分数: 4.png-88.2kB

    循环k,d的值,求解方程:

    5.png-38.5kB

    如果方程有两个有效解则分别为p和q.本例中当k=1,d=5时,$\phi$(N)=89964,方程存在两解x1=379,x2=293.

python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.PublicKey import RSA
import ContinuedFractions, Arithmetic
def wiener_hack(e, n):
  # firstly git clone https://github.com/pablocelayes/rsa-wiener-attack.git !
  frac = ContinuedFractions.rational_to_contfrac(e, n)
  convergents = ContinuedFractions.convergents_from_contfrac(frac)
  for (k, d) in convergents:
      if k != 0 and (e * d - 1) % k == 0:
          phi = (e * d - 1) // k
          s = n - phi + 1
          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
  return False

典型例题

题目来源: 2018强网杯nextrsa-Level2

解题脚本:

1
2
3
4
5
# e与n的差距过小,考虑使用wiener's attack
n = 0x92411fa0c93c1b27f89e436d8c4698bcf554938396803a5b62bd10c9bfcbf85a483bd87bb2d6a8dc00c32d8a7caf30d8899d90cb8f5838cae95f7ff5358847db1244006c140edfcc36adbdcaa16cd27432b4d50d2348b5c15c209364d7914ef50425e4c3da07612cc34e9b93b98d394b43f3eb0a5a806c70f06697b6189606eb9707104a7b6ff059011bac957e2aae9ec406a4ff8f8062400d2312a207a9e018f4b4e961c943dfc410a26828d2e88b24e4100162228a5bbf0824cf2f1c8e7b915efa385efeb505a9746e5d19967766618007ddf0d99525e9a41997217484d64c6a879d762098b9807bee46a219be76941b9ff31465463981e230eecec69691d1L
e = 0x6f6b385dd0f06043c20a7d8e5920802265e1baab9d692e7c20b69391cc5635dbcaae59726ec5882f168b3a292bd52c976533d3ad498b7f561c3dc01a76597e47cfe60614f247551b3dbe200e2196eaa001a1d183886eeacddfe82d80b38aea24de1a337177683ed802942827ce4d28e20efef92f38f1b1a18c66f9b45f5148cceabfd736de8ac4a49e63a8d35a83b664f9f3b00f822b6f11ff13257ee6e0c00ca5c98e661ea594a9e66f2bd56b33d9a13f5c997e67a37fcf9a0c7f04d119fe1ba261127357e64a4b069aefed3049c1c1fe4f964fd078b88bedd064abea385cfebd65e563f93c12d34eb6426e8aa321033cfd8fe8855b9e74d07fe4f9d70de46fL
d = wiener_hack(e, n)
print d  #42043

d泄露攻击

如果我们知道一组过期的(N, e1, d1)和一组由新的e2组成的公钥及其加密的密文(N, e2, c),我们可以由(e1, d1)得到模数N的两个因子p和q,然后再反解d2即可求出明文.

private.pem修复攻击

当题目提供的模数N过大不可分解且同时提供破损的私钥文件时,可以考虑private.pem修复.

0x03 模数N

N的特殊分解

针对大整数的分解有很多种算法,包括Fermat方法,Pollard rho p-1方法,试除法,以及椭圆曲线法,连分数法,二次筛选法,数域分析法等等.这里具体介绍Pollard rho和Fermat分解方法.

Pollard rho p-1分解

适用于p和q相差较大的情况.脚本如下:

1
2
3
4
5
6
7
8
9
from gmpy2 import *
def PollardRho_p_1(Q,N):
  a = i = 2
  while 1:
      a = pow(a, i, N)
      d = gcd(a - 1, N)
      if d != 1:
          return d
      i += 1

Fermat分解

适用于p和q相差不大的情况.脚本如下:

1
2
3
4
5
6
7
8
9
10
from gmpy2 import *
def Fermat(Q,n):
  a = isqrt_rem(n)[0]+1
  b = a ** 2 - n
  while 1:
      q = isqrt_rem(b)
      if q[1] == 0:
          return a - q[0]
      a += 1
      b = a ** 2 - n

典型题目

分解n = 0x4333AF6B43F36028D8D9650EC3EED3238541EE5C15E626C58C9EC33674A6D08D5B1F2580A1A0B07E9D853536CD994E197889D122701A62BB2A9E79559F3D5281014535F6C54F83CA8D9700EEB67D99AF318D20A5150AD46D622A6A12DE0A758EE7DF75F5D10F2FE2585F2348537787063321FFDAC91BB3C3D1D88CBD04A824ED.

分解脚本如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
from random import randint
from gmpy2 import *
n = given_n
x2 = 1
c = 7
while 1:
  x1 = randint(1, n)
  x2 = pow(x2,2,n)+c%n
  fac = gcd(abs(x1-x2),n)
  if fac>1 and is_prime(fac):
      print fac
      break
print n/fac

共模攻击

当明文m、模数n相同,公钥指数e、密文c不同且gcd(e1,e2)==1时,我们可以采取共模攻击来直接还原出明文.下面简单进行证明:

python实现

1
2
3
4
5
6
7
def common_modulus(n, e1, e2, c1, c2):
assert (libnum.gcd(e1, e2) == 1)
_, s1, s2 = gmpy2.gcdext(e1, e2)
# 若s1<0，则c1^s1==(c1^-1)^(-s1)，其中c1^-1为c1模n的逆元。
m = pow(c1, s1, n) if s1 > 0 else pow(gmpy2.invert(c1, n), -s1, n)
m *= pow(c2, s2, n) if s2 > 0 else pow(gmpy2.invert(c2, n), -s2, n)
return m % n

典型例题

题目来源: buuctf RSA3

题目分析: 该题给出了c1,c2,e1,e2和n,显然使用共模攻击.

解题脚本:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import gmpy2 as gp
def exgcd(a, b):
  if b==0:
      return 1, 0, a
  x2, y2, r = exgcd(b, a%b)
  x1 = y2
  y1 = x2-(a//b)*y2
  return x1, y1, r
c1=gp.mpz(c1)
n=gp.mpz(n)
e1=gp.mpz(e1)
c2=gp.mpz(c2)
e2=gp.mpz(e2)
r1, r2, t = exgcd(e1, e2)
m = gp.powmod(c1, r1, n) * gp.powmod(c2, r2, n) % n
print(m)
print(hex(m)[2:])
print(bytes.fromhex(str(hex(m)[2:])))

公共因子攻击

当题目给出同一个(m,e)使用较多组N加密后的多组(N,c)时,可以循环求解这些N的最大公因数.如果存在gcd(Ni,Nj)!= 1,则可以顺利分解Ni和Nj,从而还原明文.

python实现

1
2
3
4
5
6
7
8
9
10
11
12
def common_primes(data):
	# 按照data[0]=n1,data[1]=e1,data[2]=n2,....的顺序构造数组data
	for i in range(len(data)//2):
		for j in range(i+1,len(data)//2):
			if math.gcd(data[2*i],data[2*j]) != 1:
				print("[+]Successfully found!")
				print("    [-]n1 =" + str(data[2*i]))
				print("    [-]n2 =" + str(data[2*j]))
				print("[+]One possible decomposition:")
				print("    [!]p = " + str(math.gcd(data[2*i],data[2*j])))
				print("    [!]q = " + str(data[2*i]//math.gcd(data[2*i],data[2*j])))
				exit()

典型题目

题目来源: buuctf RSA5

题目分析: 题目给出了e=65537,以及二十组对应的(n,c).由于所给的信息数量较多,考虑公共因子攻击.构造符合上文所给脚本的数组data,然后寻找拥有公共因子的模数对,最后还原明文.

解题脚本: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import gmpy2 as gp
import math
import binascii
data = [given_n_and_e_combinations]
e = gp.mpz(65537)
common_primes(data)
# then we get the results as follows:
n = gp.mpz(n)
c = gp.mpz(c)
d = gp.mpz(d)
m = gp.powmod(c,d,n)
print(m)
print(binascii.a2b_hex(str(m))[2:])
# flag = flag{abdcbe5fd94e23b3de429223ab9c2fdf}

0x04 密文c

选择密文攻击

该类攻击适用于可以构造任意密文并获得对应明文的情况.

在一个RSA加密过程中,明文为m,密文为c,模数为n,加密指数为e,选取x以满足gcd(x,n)==1从而使x模n的逆存在,构造密文c'=c*(x^e),使解密后的明文为m'=(m*x)%n,则m=m'*x^(-1)(mod n).

LSB Oracle Attack

假如用户知道公钥中N, e, c,并且可以任意构造密文c1,返回此密文解密后p1的末尾某些比特位的性质(记为函数f).最简单的函数f是表示p1的奇偶性.

攻击者构造密文c'=((2^e)*c)%n=((2^e)*(m^e))%n=((2*m)^e)%n,返回明文m'=(2*m)%n及m’的lsb.下面继续分析,因为n是奇数,而2*m是偶数,所以如果lsb=0,则(2\*m)%n是偶数,没有超过n,从而确定m<n/2.0,反之则m>n/2.0.

以此类推,构造密文c''=((4^e)*c)%n使其解密后有m''=(4*m)%n,判断m’’的奇偶性就可以知道m和n/4的大小关系.此时我们得到一个在对数时间内将m的范围逼近到一个足够小范围的二分算法.

python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import decimal
def oracle():
    return lsb == 'odd'
def partial(c, e, n):
    k = n.bit_length()
    decimal.getcontext().prec = k  # for 'precise enough' floats
    lo = decimal.Decimal(0)
    hi = decimal.Decimal(n)
    for i in range(k):
        if not oracle(c):
            hi = (lo + hi) / 2
        else:
            lo = (lo + hi) / 2
        c = (c * pow(2, e, n)) % n
        # print i, int(hi - lo)
    return int(hi)

题目一 QCTF 2018-XMan选拔赛/Baby RSA

题目描述: 

1
2
3
4
5
6
7
8
9
10
e = 0x10001
n = 0x0b765daa79117afe1a77da7ff8122872bbcbddb322bb078fe0786dc40c9033fadd639adc48c3f2627fb7cb59bb0658707fe516967464439bdec2d6479fa3745f57c0a5ca255812f0884978b2a8aaeb750e0228cbe28a1e5a63bf0309b32a577eecea66f7610a9a4e720649129e9dc2115db9d4f34dc17f8b0806213c035e22f2c5054ae584b440def00afbccd458d020cae5fd1138be6507bc0b1a10da7e75def484c5fc1fcb13d11be691670cf38b487de9c4bde6c2c689be5adab08b486599b619a0790c0b2d70c9c461346966bcbae53c5007d0146fc520fa6e3106fbfc89905220778870a7119831c17f98628563ca020652d18d72203529a784ca73716db
c = 0x4f377296a19b3a25078d614e1c92ff632d3e3ded772c4445b75e468a9405de05d15c77532964120ae11f8655b68a630607df0568a7439bc694486ae50b5c0c8507e5eecdea4654eeff3e75fb8396e505a36b0af40bd5011990663a7655b91c9e6ed2d770525e4698dec9455db17db38fa4b99b53438b9e09000187949327980ca903d0eef114afc42b771657ea5458a4cb399212e943d139b7ceb6d5721f546b75cd53d65e025f4df7eb8637152ecbb6725962c7f66b714556d754f41555c691a34a798515f1e2a69c129047cb29a9eef466c206a7f4dbc2cea1a46a39ad3349a7db56c1c997dc181b1afcb76fa1bbbf118a4ab5c515e274ab2250dba1872be0
λ nc 47.96.239.28 23333
----------------------------- baby rsa -----------------------------
Come and Decode your data
If you give me ciphertext, I can tell you whether decoded data is even or odd
You can input ciphertext(hexdecimal) now
1
odd

解题脚本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
solve.py
# -*- coding: utf-8 -*-
import libnum, gmpy2, socket, time, decimal
def oracle(c1):
    s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    hostname = '47.96.239.28'
    port = 23333
    s.connect((hostname, port))
    s.recv(1024)
    s.send(hex(c1)[2:].strip("lL") + '\n')
    res = s.recv(1024).strip()
    s.close()
    if res == 'even': return 0
    if res == 'odd':
        return 1
    else:
        assert (0)
def partial(c, n):
    global c_of_2
    k = n.bit_length()
    decimal.getcontext().prec = k  # allows for 'precise enough' floats
    lower = decimal.Decimal(0)
    upper = decimal.Decimal(n)
    for i in range(k):
        possible_plaintext = (lower + upper) / 2
        # lower==0 when i<1809
        flag = oracle(c)
        if not flag:
            upper = possible_plaintext  # plaintext is in the lower half
        else:
            lower = possible_plaintext  # plaintext is in the upper half
        c = (c * c_of_2) % n  # multiply y by the encryption of 2 again
        print i, flag, int(upper - lower)
        # time.sleep(0.2)
    # By now, our plaintext is revealed!
    return int(upper)
def main():
    print "[*] Conducting Oracle attack..."
    return partial((c * c_of_2) % n, n)
if __name__ == '__main__':
    e = given_e
    n = given_n
    c = given_c
    c_of_2 = pow(2, e, n)
    m = main()
    # m = 560856645743734814774953158390773525781916094468093308691660509501812349
    print libnum.n2s(m)
    # QCTF{RSA_parity_oracle_is_fun}

题目二:Backdoor CTF2018 BIT-LEAKER

题目描述：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
server.py
#!/usr/bin/python -u
from Crypto.Util.number import *
from Crypto.PublicKey import RSA
import random
#from SECRET import flag
flag = "CTF{this_is_my_test_flag}"
m = bytes_to_long(flag)
key = RSA.generate(1024)
c = pow(m, key.e, key.n)
print("Welcome to BACKDOORCTF17\n")
print("PublicKey:\n")
print("N = " + str(key.n) + "\n")
print("e = " + str(key.e) + "\n")
print("c = " + str(c) + "\n")
while True:
    try:
        temp_c = int(raw_input("temp_c = "))
        temp_m = pow(temp_c, key.d, key.n)
    except:
        break
    l = str(((temp_m&5) * random.randint(1,10000))%(2*(random.randint(1,10000))))
    print "l = "+l

解题脚本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
solve.py
# -*- coding: utf-8 -*-
#/usr/bin/env python
from pwn import *
import libnum
import Crypto
import re
from binascii import hexlify,unhexlify
if len(sys.argv)>1:
    p=remote("127.0.0.1",2334)
else:
    p=remote('127.0.0.1',2333)
#context.log_level = 'debug'
def oracle(c):
    l = []
    for i in range(20):
        p.sendline(str(c))
        s = p.recvuntil("temp_c")
        l.append(int(re.findall("l\s*=\s*([0-9]*)",s)[0]))
    flag0 = 0
    flag2 = 0
    for i in range(20):
        if l[i]%2 != 0:
            flag0 = 1
        if l[i] > 10000:
            flag2 = 1
    return [flag2,flag0]
def main():
    ss = p.recvuntil("temp_c")
    N = int(re.findall("N\s*=\s*(\d+)",ss)[0])
    e = int(re.findall("e\s*=\s*(\d+)",ss)[0])
    c = int(re.findall("c\s*=\s*(\d+)",ss)[0])
    size = libnum.len_in_bits(N)
    print "N=",N
    print "e=",e
    print "c=",c
    c = (pow(2,e,N)*c)%N
    LB = 0
    UB = N
    i = 1
    while LB!=UB:
        flag = oracle(c)
        print i,flag
        if flag[1]%2==0:
            UB = (LB+UB)/2
        else:
            LB = (LB+UB)/2
        c = (pow(2,e,N)*c)%N
        i += 1
    print LB
    print UB
    for i in range(-128,128,0):
        LB += i
        if pow(LB,e,N)==C:
            print unhexlify(hex(LB)[2:-1])
            exit(0)
if __name__ == '__main__':
    main()
    p.interactive()

参考链接: RSA Least-Significant-Bit Oracle Attack

0x05 综合应用

通过一道题目分析说明RSA的综合应用.

题目来源: 2019De1CTF BabyRSA

题目描述: 题目提供的脚本如下.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import binascii
from data import e1,e2,p,q1p,q1q,hint,flag

n =  [n1, n2, n3, n4]
c =  [c1, c2, c3, c4]
f=lambda m,e,n,c:pow(m,e,n)==c
assert(sum(map(f,[p]*4,[4]*4,n,c))==4)

ee1 = 42
ee2 = 3
ce1 =  45722651786340123946960815003059322528810481841378247280642868553607692149509126962872583037142461398806689489141741494974836882341505234255325683219092163052843461632338442529011502378931140356111756932712822516814023166068902569458299933391973504078898958921809723346229893913662577294963528318424676803942288386430172430880307619748186863890050113934573820505570928109017842647598266634344447182347849367714564686341871007505886728393751147033556889217604647355628557502208364412269944908011305064122941446516990168924709684092200183860653173856272384
ce2 =  13908468332333567158469136439932325992349696889129103935400760239319454409539725389747059213835238373047899198211128689374049729578146875309231962936554403287882999967840346216695208424582739777034261079550395918048421086843927009452479936045850799096750074359160775182238980989229190157551197830879877097703347301072427149474991803868325769967332356950863518504965486565464059770451458557744949735282131727956056279292800694203866167270268988437389945703117070604488999247750139568614939965885211276821987586882908159585863514561191905040244967655444219603287214405014887994238259270716355378069726760953320025828158
tmp =  864078778078609835167779565982540757684070450697854309005171742813414963447462554999012718960925081621571487444725528982424037419052194840720949809891134854871222612682162490991065015935449289960707882463387
n  =  15911581555796798614711625288508309704791837516232122410440958830726078821069050404012820896260071751380436992710638364294658173571101596931605797509712839622479368850251206419748090059752427303611760004621378226431226983665746837779056271530181865648115862947527212787824629516204832313026456390047768174765687040950636530480549014401279054346098030395100387004111574278813749630986724706263655166289586230453975953773791945408589484679371854113457758157492241225180907090235116325034822993748409011554673180494306003272836905082473475046277554085737627846557240367696214081276345071055578169299060706794192776825039
assert(pow(e1,ee1,n)==ce1)
assert(pow(e2+tmp,ee2,n)==ce2)

e = 46531
n = 16278524034278364842964386062476113517067911891699789991355982121084973951738324063305190630865511554888330215827724887964565979607808294168282995825864982603759381323048907814961279012375346497781046417204954101076457350988751188332353062731641153547102721113593787978587135707313755661153376485647168543680503160420091693269984008764444291289486805840439906620313162344057956594836197521501755378387944609246120662335790110901623740990451586621846212047950084207251595169141015645449217847180683357626383565631317253913942886396494396189837432429078251573229378917400841832190737518763297323901586866664595327850603
c = 14992132140996160330967307558503117255626925777426611978518339050671013041490724616892634911030918360867974894371539160853827180596100892180735770688723270765387697604426715670445270819626709364566478781273676115921657967761494619448095207169386364541164659123273236874649888236433399127407801843412677293516986398190165291102109310458304626261648346825196743539220198199366711858135271877662410355585767124059539217274691606825103355310348607611233052725805236763220343249873849646219850954945346791015858261715967952461021650307307454434510851869862964236227932964442289459508441345652423088404453536608812799355469
hint=int(binascii.hexlify(hint),16)
assert(q1p*q1q==n)
assert(q1p<q1q)
assert(c==pow(hint,e,n))

flag=int(binascii.hexlify(flag),16)
q1=q1p
q2 =  114401188227479584680884046151299704656920536168767132916589182357583461053336386996123783294932566567773695426689447410311969456458574731187512974868297092638677515283584994416382872450167046416573472658841627690987228528798356894803559278308702635288537653192098514966089168123710854679638671424978221959513
c1 =  262739975753930281690942784321252339035906196846340713237510382364557685379543498765074448825799342194332681181129770046075018122033421983227887719610112028230603166527303021036386350781414447347150383783816869784006598225583375458609586450854602862569022571672049158809874763812834044257419199631217527367046624888837755311215081173386523806086783266198390289097231168172692326653657393522561741947951887577156666663584249108899327053951891486355179939770150550995812478327735917006194574412518819299303783243886962455399783601229227718787081785391010424030509937403600351414176138124705168002288620664809270046124
c2 =  7395591129228876649030819616685821899204832684995757724924450812977470787822266387122334722132760470911599176362617225218345404468270014548817267727669872896838106451520392806497466576907063295603746660003188440170919490157250829308173310715318925771643105064882620746171266499859049038016902162599261409050907140823352990750298239508355767238575709803167676810456559665476121149766947851911064706646506705397091626648713684511780456955453552020460909638016134124590438425738826828694773960514221910109473941451471431637903182205738738109429736425025621308300895473186381826756650667842656050416299166317372707709596
assert(c1==pow(flag,e1,p*q1))
assert(c2==pow(flag,e2,p*q2))

(由于数组n和c中的数字较多,故使用n1-n4,c1-c4代替表示)

题目分析:本题思路非常明确,空行将脚本分成四个部分,我们逐个部分解决.

第一部分: 给出了n1-n4和c1-c4,且sum()函数返回的结果为4,我们可以得到如下同余方程组:

1
2
3
4
c1 = p^4 mod n1
c2 = p^4 mod n2
c3 = p^4 mod n3
c4 = p^4 mod n4

联想到使用中国剩余定理解决,我们得到大素数p.

第二部分: 给出了两个较小的加密指数e1=42,e2=3,联想到使用低加密指数攻击.分别使用gmpy2.iroot()函数进行爆破处理,可以得到e1和e2.

第三部分: 该加密过程没有其他的办法,只能使用yafu进行模数分解.分解结果可以看出,p,q的差距不大,所以使用了Fermat分解法.

第四部分: 经过前三部分的解密,我们得到了如下参数:

1
2
加密指数e1,e2
大素数p,q1,q2

再加上第四部分所给的c1,c2,我们有如下rsa问题: 

1
2
c1 % p*q1 = flag^e1 % p*q1
c2 % p*q2 = flag^e2 % p*q2

通过观察发现e1,e2与$\phi(pq1), \phi (pq2) $不互素,属于e与$\phi$(n)不互素的情况.而且我们发现gcd(e1,p*q1)=gcd(e2,p*q2)=14,按照上面的推导步骤,最终得到$ m^2 \equiv c^(2d) (mod q1q2) $.进行开方爆破,最终得到flag.

解密脚本如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#coding:utf8
import binascii,gmpy2
# from data import e1,e2,p,q1p,q1q,hint,flag,q2

n =  [n1, n2, n3, n4]
c =  [c1, c2, c3, c4]

# 中国剩余定理解决低加密指数广播攻击
def CRT(mi, ai):
    assert(reduce(gmpy2.gcd,mi)==1)
    assert (isinstance(mi, list) and isinstance(ai, list))
    M = reduce(lambda x, y: x * y, mi)
    ai_ti_Mi = [a * (M / m) * gmpy2.invert(M / m, m) for (m, a) in zip(mi, ai)]
    return reduce(lambda x, y: x + y, ai_ti_Mi) % M

p=gmpy2.iroot(CRT(n, c), 4)[0]
print "p = ",p
# ====================got p
ee1 = 42
ee2 = 3
ce1 =  number_ce1
ce2 =  number_ce2
tmp =  number_tmp1
n  =  number_n

# 使用gmpy2.iroot()函数直接爆破
for i in xrange(200000):
	if gmpy2.iroot(ce1+n*i,42)[1]==1:
		res=gmpy2.iroot(ce1+n*i,42)[0]
		e1=res
		break

for i in xrange(200000):
	if gmpy2.iroot(ce2+n*i,3)[1]==1:
		res=gmpy2.iroot(ce2+n*i,3)[0]
		e2=res-tmp
		break
print "e1 = ",e1
print "e2 = ",e2
# ====================got e1,e2
e = number_e
n = number_n
c = number_c

# yafu got q1p,q1q
q1p = result_q1p
q1q = result_q1q
if q1p>q1q:
	q1p,q1q=q1q,q1p

# below is not necessary
phi=(q1p-1)*(q1q-1)
assert(gmpy2.gcd(e,phi)==1)
d=gmpy2.invert(e,phi)
hint=pow(c,d,n)
hint=binascii.unhexlify(hex(hint)[2:])
print "hint = ",hint
# ====================got  q1p as q1
# flag=int(binascii.hexlify(flag),16)
q1 = q1p
print "q1 = ",q1
q2 =  number_q2
c1 =  number_c1
c2 =  number_c2
assert(14==gmpy2.gcd(e1,(p-1)*(q1-1)))
assert(14== gmpy2.gcd(e2,(p-1)*(q2-1)))
e1=e1//14;e2=e2//14
n1=p*q1;n2=p*q2
phi1=(p-1)*(q1-1);phi2=(p-1)*(q2-1)
d1=gmpy2.invert(e1,phi1);d2=gmpy2.invert(e2,phi2)
f1=pow(c1,d1,n1);f2=pow(c2,d2,n2)

# 当模数与加密次方不互素时使用中国剩余定理合并
def GCRT(mi, ai):
    assert (isinstance(mi, list) and isinstance(ai, list))
    curm, cura = mi[0], ai[0]
    for (m, a) in zip(mi[1:], ai[1:]):
        d = gmpy2.gcd(curm, m)
        c = a - cura
        assert (c % d == 0)
        K = c // d * gmpy2.invert(curm // d, m // d)
        cura += curm * K
        curm = curm * m // d
        cura %= curm
    return (cura % curm, curm) 

f3,lcm = GCRT([n1,n2],[f1,f2])
assert(f3%n1==f1);assert(f3%n2==f2);assert(lcm==q1*q2*p)
n3=q1*q2
c3=f3%n3
phi3=(q1-1)*(q2-1)
assert(gmpy2.gcd(7,phi3)==1)
d3=gmpy2.invert(7,phi3)
m3=pow(c3,d3,n3)
if gmpy2.iroot(m3,2)[1] == 1:
    flag=gmpy2.iroot(m3,2)[0]
    print(binascii.unhexlify(hex(flag)[2:]))

# de1ctf{9b10a98b-71bb-4bdf-a6ff-f319943de21f}
请作者吃个小鱼饼干吧
分享到： 收藏夹 复制网址 邮件 微信 QQ空间 腾讯微博 豆瓣 一键分享 更多