前话
闲下来把之前没做完(出来)的排位赛的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()
提取出有用的条件
我们来看看我们有的条件
- 题目给出了
pblic.pem,我们用python的RSA库提取出n和efrom 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 - 代码逻辑大致为：随机生成的
q和已知p的高位为part1，p的低位part2是完全随机的不可控的。 -
p和q的位数都是512位，part2的位数是279位
coppersmith高位已知攻击
根据已知的的条件，可以联想到coopersmith的高位攻击。
我们来关注一下coppersmith的一些定理:
- 定理3.3 对任意的a > 0 ， 给定N = PQR及PQ的高位
(1/5)(logN,2)比特，我们可以在多项式时间logN内得到N的分解式。
这是三个因式的分解。也就是说我们现在是由理论依据的，已知高位是可以在一定时间内分解N。具体的算法的推导这里没法给出。 - 那么在已知p高位多少位才可以进行攻击呢，保证哥在做题的时候给出了定理的提示
这个定理是在《Mathematics_of_Public_Key_Cryptography》这本数里面提到的，我们将我们上面得到的N的值带入上图的式子中。
计算(1/根号2)*N
根据上式子我们得出:
if p.bit_length == 1024 ,p的高位需已知约576位
if p.bit_length == 1024 ,p的高位需已知约288位
-
sage里面的small_roots能实现上述的给出已知的p高位进行分解N的函数方法，利用了LLL算法求解非线性低维度多项式方程小根的方法。
Coppersmith证明了在已知p和q部分比特的情况下，若q和p的未知部分的上界X和Y满足XY <= N ^ (0.5)则Ｎ的多项式可以被分解。
这里的0.5可以替换成其他的数，具体原因不详。 - 我们已知的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()
提取有用信息
-
self.request.send(long_to_bytes(pub.encrypt(flag)))==> 我们如果输入f，能得到flag的byte值，实际上就相当于给了我们flag的加密值。 -
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
那么就有下面几个情况:
- 如果返回值是
True即LSB是0即解密出来明文是偶数）,那么数字小于模数, 因此2*pt < n意味着pt < n/2 - 如果返回值是
False即LSB是1即解密出来明文大于模数，因此2*pt > n意味着pt > n/2 - 如果我们再询问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习。