xman排位赛-Crypto第一弹-RSA

前话

闲下来把之前没做完(出来)的排位赛的crypto做了下，这里分享两道xman夏令营排位赛的RSA的题目，认真学习!

 

0x01 RSA-Generator

这题算是三题里面最简单的一题了。

import gmpy2
import random
from Crypto.Util.number import getPrime
from Crypto.PublicKey import RSA


def generate_public_key():
    part1 = 754000048691689305453579906499719865997162108647179376656384000000000000001232324121
    part1bits = part1.bit_length()
    lastbits = 512 - part1.bit_length()
    part1 = part1 << lastbits
    part2 = random.randrange(1, 2**lastbits)
    p = part1 + part2
    while not gmpy2.is_prime(p):
        p = part1 + random.randrange(1, 2**lastbits)
    q = getPrime(512)
    n = p * q
    print p
    print q
    e = 0x10001
    key = RSA.construct((long(n), long(e)))
    key = key.exportKey()
    with open('public.pem', 'w') as f:
        f.write(key)


def encrypt():
    flag = open('./flag.txt').read().strip('n')
    flag = flag.encode('hex')
    flag = int(flag, 16)
    with open('./public.pem') as f:
        key = RSA.importKey(f)
        enc = gmpy2.powmod(flag, key.e, key.n)
    with open('flag.enc', 'w') as f:
        f.write(hex(enc)[2:])


generate_public_key()
encrypt()

提取出有用的条件

我们来看看我们有的条件

1. 题目给出了pblic.pem,我们用python的RSA库提取出n和e

   from Crypto.PublicKey import RSA
   pub = RSA.importKey(open('public.pem').read())
   n = long(pub.n)
   e = long(pub.e)
   print "n:"+str(n)
   print "e:"+str(e)
   

   能够得到:

   n=0x639386F4941D1511D89A9D19DC4731188D3F4D2D04623FB26F5A85BB3A54747BCBADCDBD8E4A75747DB4072A90F62DCA08F11AC276D7588042BEFA504DCD87CD3B0810F1CB28168A53F9196CDAF9FD1D12DCD4C375EB68B67A8EFCCEC605C57C736943170FEF177175F696A0F6123B993E56FFBF1B62435F728A0BAC018D0113
   e=0x10001
   

2. 代码逻辑大致为：随机生成的q和已知p的高位为part1，p的低位part2是完全随机的不可控的。
3. p和q的位数都是512位，part2的位数是279位

coppersmith高位已知攻击

根据已知的的条件，可以联想到coopersmith的高位攻击。
我们来关注一下coppersmith的一些定理:

1. 定理3.3 对任意的a > 0 ， 给定N = PQR及PQ的高位(1/5)(logN,2)比特，我们可以在多项式时间logN内得到N的分解式。
   这是三个因式的分解。也就是说我们现在是由理论依据的，已知高位是可以在一定时间内分解N。具体的算法的推导这里没法给出。
2. 那么在已知p高位多少位才可以进行攻击呢，保证哥在做题的时候给出了定理的提示

这个定理是在《Mathematics_of_Public_Key_Cryptography》这本数里面提到的，我们将我们上面得到的N的值带入上图的式子中。
计算(1/根号2)*N
根据上式子我们得出:

if p.bit_length == 1024 ,p的高位需已知约576位
if p.bit_length == 1024 ,p的高位需已知约288位

1. sage里面的small_roots能实现上述的给出已知的p高位进行分解N的函数方法，利用了LLL算法求解非线性低维度多项式方程小根的方法。
   Coppersmith证明了在已知p和q部分比特的情况下，若q和p的未知部分的上界X和Y满足XY <= N ^ (0.5)则Ｎ的多项式可以被分解。
   这里的0.5可以替换成其他的数，具体原因不详。
2. 我们已知的part1的比特位为279位，距离我们的条件还差9位左右，所以这里不能直接让上述的条件成立，所以我们还需要爆破9位左右的数据。
   由于9位左右的bit需要至少3位十六进制(3*4 > 9)

攻击脚本

sage里small_roots具体用法

#!/usr/bin/env sage -python
# -*- coding: utf-8 -*-
from sage.all import *
import binascii
n = 0x639386F4941D1511D89A9D19DC4731188D3F4D2D04623FB26F5A85BB3A54747BCBADCDBD8E4A75747DB4072A90F62DCA08F11AC276D7588042BEFA504DCD87CD3B0810F1CB28168A53F9196CDAF9FD1D12DCD4C375EB68B67A8EFCCEC605C57C736943170FEF177175F696A0F6123B993E56FFBF1B62435F728A0BAC018D0113

cipher = 0x56c5afbc956157241f2d4ea90fd24ad58d788ca1fa2fddb9084197cfc526386d223f88be38ec2e1820c419cb3dad133c158d4b004ae0943b790f0719b40e58007ba730346943884ddc36467e876ca7a3afb0e5a10127d18e3080edc18f9fbe590457352dca398b61eff93eec745c0e49de20bba1dd77df6de86052ffff41247d

e2 = 0x10001

pbits = 512

for i in range(0,4095):
  p4 = 0x635c3782d43a73d70465979599f65622c7b4242a2d623459337100000000004973c619000
  p4 = p4 + int(hex(i),16)
  kbits = pbits - p4.nbits()  #未知需要爆破的比特位数
  p4 = p4 << kbits 
  PR.<x> = PolynomialRing(Zmod(n))
  f = x + p4
  roots = f.small_roots(X=2^kbits, beta=0.4) #进行爆破

  #print roots
  if roots:        #爆破成功，求根
    p = p4+int(roots[0])
    assert n % p == 0
    q = n/int(p)
    phin = (p-1)*(q-1)
    d = inverse_mod(e2,phin)
    flag = pow(cipher,d,n)
    flag = hex(int(flag))[2:-1]
    print binascii.unhexlify(flag)

最后的flag:
flag:xman{RSA-is-fun???!!!!}

后话

分享一个在线sage的网站，tql,http://sagecell.sagemath.org/

 

0x02

题目源码

from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long, long_to_bytes
import socketserver

class PUB():
        def __init__(self):
                self.rsa = RSA.generate(2048)

        def get_n(self):
                return self.rsa.n

        def get_e(self):
                return self.rsa.e

        def encrypt(self, plaintext):
                return self.rsa.encrypt(plaintext, None)[0]

        def decrypt(self, ciphertext):
                return (self.rsa.decrypt(ciphertext) % 2 == 0)

class process(socketserver.BaseRequestHandler):
    def handle(self):
        #self.justWaite()    
        pub = PUB()
        e, n = pub.get_e(), pub.get_n()
        self.request.send(bytes(hex(e), 'utf-8'))
        self.request.send(b'nn')
        self.request.send(bytes(hex(n), 'utf-8'))

        while True:
            self.request.send(b"n'f'lag or 'e'ncrypt or 'd'ecrypt_detectn")
            c = self.request.recv(2)[:-1]
            if c == b'f':
                flag = b'xman{*********************}'
                flag = bytes_to_long(flag)

                self.request.send(long_to_bytes(pub.encrypt(flag)))

            elif c == b'd':
                c = self.request.recv(2048)[:-1]
                c = bytes_to_long(c)
                self.request.send(bytes(str(pub.decrypt(c)), 'utf-8'))

        self.request.close()


class ThreadedServer(socketserver.ThreadingMixIn, socketserver.TCPServer):
    pass

if __name__ == "__main__":
    HOST, PORT = '0.0.0.0', 10093
    server = ThreadedServer((HOST, PORT), process)
    server.allow_reuse_address = True
    server.serve_forever()

提取有用信息

1. self.request.send(long_to_bytes(pub.encrypt(flag))) ==> 我们如果输入f，能得到flag的byte值，实际上就相当于给了我们flag的加密值。

2. def decrypt(self, ciphertext):
    return (self.rsa.decrypt(ciphertext) % 2 == 0)
   

   ==> 如果我们输入d,就能得到返回值的ciphertext是否位偶数，是则返回True否则返回false

能得到的消息是已知n和e，c以及返回值的奇偶性，这些条件，马上能联想到LSB Oracle攻击。

LSB oracle

LSB oracle实际上是原理是一种二分逼近的方法。
我们来假设正常的加密为:
ct = pt^e mod n
那么我们假设存在c':
ct' = ct * 2^e mod n
则有:
ct' = pt^e * 2^e mod n
则有:
ct' = (2*pt)^e mod n
那么:
ct'^d = (2pt^e)^d mod n
则有:
ct'^d = 2pt^ed mod n
又因为在rsa的体系里面
ed = 1 mod n
则有
ct' ^ d = 2pt mod n

那么就有下面几个情况:

1. 如果返回值是True即LSB是0即解密出来明文是偶数）,那么数字小于模数, 因此2*pt < n意味着pt < n/2
2. 如果返回值是False即LSB是1即解密出来明文大于模数，因此2*pt > n意味着pt > n/2
3. 如果我们再询问LSB，4*pt mod n我们可以再次得到两个可能的结果之一：

• 如果LSB 0那么4pt < n意味着Pt < n/4是否pt < n/2为真，或者在前一步中pt < 3n/4是否pt > n/2为真
• 如果LSB 1那么4pt > n意味着pt > n/4是否pt < n/2为真，或者在前一步中pt > 3n/4是否pt > n/2为真
  ….以此类推

攻击脚本

故而最后可以用上下限逼近的方法进行解密，最后的代码如下：

from Crypto.Util.number import bytes_to_long, long_to_bytes
from hashlib import sha1
import itertools
import socket
import time
import math
import binascii

e=0x10001

def encrypt(m, N):
    return pow(m, 2, N)


s = socket.create_connection(('202.112.51.184', 10093))
r1 = s.recv(4096)
r2 = s.recv(4096)
n = int(r2[r2.find('0x'):r2.find(''f'')-1],16)
s.send('fn')
r3 = s.recv(4096)
r3 = bytes(r3)
c =  bytes_to_long(r3)
upper = n
lower = 0
iter_count = math.log(n, 2)
r = s.recv(4096)
print long(math.ceil(long(iter_count)))
for i in xrange(0, long(math.ceil(long(iter_count)))):
    s.send('dn')
    print 'Round', i
    power = pow(2, i+1, n)
    ct = (pow(power, e, n) * c) % n
    s.send(str(hex(ct))[2:-1]+'n')
    r = s.recv(4096)
    # even
    if upper-lower <= 2:
        break
    if 'True' in r:
        upper = (upper + lower)/2
    # odd
    elif 'False' in r:
        lower = (upper + lower)/2


print 'nFlag:'
print str(long_to_bytes(upper))

tips: 服务器好像出了点问题，flag跑不出来，大家有兴趣的可以本地搭一下试试。
最后的flag:`xman{adsfklhuyuy709877*.ho}

后话

LSB Oracle还是挺简单的,如果上述有问题，请指出大家多xiao习xiao习。