rsa高位攻击 恢复p

结合WHCTF2017的一道密码题Untitled来讲解

核心考点在于拿到rsa中p的前568位，但是知道 e n 要利用算法破解1024位的p，至少需要576位，所以要爆破8位的二进制，达到576位了再用算法恢复完整的p

密码题目在最下方的whctf2017.py

Paste_Image.png

nc 118.31.18.75 20013 与服务器交互

第一步，过md5

Paste_Image.png
md5脚本为最下方的md5.py
之前都是用xrange生成随机长度，这次试一下生成固定长度的字符串，而且字符集合可以自己选择，没准以后哪次CTF就能用到
Paste_Image.png

第2步要求输入x和y，这里主要考rsa的原理，类似数学等价推导

Paste_Image.png

第3步爆破p

• 成功交互后返回了s，其中s是p的前部分，脚本中用p4表示

• 已知e n 要爆破1024位的p，至少需要知道前576位二进制，即前144位16进制，但是返回的s是长为142位的十六进制，需要爆破两位，凑到144位16进制

• 这里要用到sagaMath来调用强大的计算能力，但是saga有点大，这里推荐一个在线的saga运行网址 https://cocalc.com/

• 参考链接
  http://bobao.360.cn/ctf/detail/205.html partital题
  https://www.liangmlk.cn/Index-newDetail-id-10913.html Crypto So Cool题
  http://bobao.360.cn/ctf/detail/179.html Crypto So Cool题
  https://www.xctf.org.cn/library/details/c275754f6961bd9dfa83960551c1bd328246d5f5/ Crypto So Cool题
  http://inaz2.hatenablog.com/entries/2016/01/20 SageMath题有介绍saga的安装和使用
  通用的已知144位十六进制的部分p，爆破脚本为最下面的 通用144.py
  该题目中爆破两位后，才能构成144位，爆破脚本为最下面 412+2.py

144.py截图

Paste_Image.png

142+2.py截图

Paste_Image.png

第4步 p q c 都知道了，求出明文 m

so easy，脚本为最下面的 rsa.py

git clone https://github.com/hellman/libnum

Paste_Image.png Paste_Image.png

whctf2017.py：

from Crypto.Util.number import getPrime,long_to_bytes,bytes_to_long
import primefac
import time
from os import urandom
import hashlib
import sys
class Unbuffered(object):
   def __init__(self, stream):
       self.stream = stream
   def write(self, data):
       self.stream.write(data)
       self.stream.flush()
   def __getattr__(self, attr):
       return getattr(self.stream, attr)
import sys
sys.stdout = Unbuffered(sys.stdout)
def gen_args():
    p=getPrime(1024)
    q=getPrime(1024)
    n=p*q
    e=0x10001
    d=primefac.modinv(e,(p-1)*(q-1))%((p-1)*(q-1))
    return (p,q,e,n,d)
def proof():
    salt=urandom(4)
    print salt.encode("base64"),
    proof=raw_input("show me your work: ")
    if hashlib.md5(salt+proof.decode("base64")).hexdigest().startswith("0000"):
        print "checked success"
        return 1
    return 0

def run():
    if not proof():
        return
    m=int(open("/home/bibi/PycharmProjects/work/whctf/flag","r").read().encode("hex"),16)#flag{*}
    (p,q,e,n,d)=gen_args()
    c=pow(m,e,n)
    print "n:",hex(n)
    print "e:",hex(e)
    print "c:",hex(c)
    t=int(hex(m)[2:][0:8],16)
    u=pow(t,e,n)
    print "u:",hex(u)
    print "===="
    x=int(hex(m)[2:][0:8]+raw_input("x: "),16)
    print "===="
    y=int(raw_input("y: "),16)
    if (pow(x,e,n)==y and pow(y,d,n)==t):
        print "s:",hex(int(bin(p)[2:][0:568],2))
run()

md5.py

#!coding:utf-8
import string
import hashlib
from random import Random
def random_str(randomlength=8):    #这里写的是8位字符的破解，在这题目中可以不下
    str = ''    
    chars = 'AaBbCcDdEeFfGgHhIiJjKkLlMmNnOoPpQqRrSsTtUuVvWwXxYyZz0123456789'
    length = len(chars) - 1
    random = Random() 
    for i in range(randomlength):    
        str+=chars[random.randint(0, length)]
    return str

salt = 'SauTEQ=='.decode('base64')
while True:
    proof =  random_str(8).encode('base64')
    if hashlib.md5(salt+proof.decode('base64')).hexdigest().startswith("0000"):
        print proof
        print salt
        print proof.decode('base64')+salt
        print salt.encode('base64')
        print hashlib.md5(salt+proof.decode('base64')).hexdigest()
        break

144.py

from sage.all import *
n = 0x9d3a1a28ecb1bd245dd86b18dc4c5b729f23778710005118836129f08e31d6516de8ab47db1b3b7f660f50d283b1e9f2c06e7836136e4c0159f5d2b05771861d3ce6aa8715932eadc1cc0f380909a1961018340f7393142f9c177b1187151f97ac8cdc4ad17fa59a0f39d192af555f27de9cc800846eb2ca6ce78f87c0c0fbf47828328392b81771af624389fd779d130d80739bb7a608961125ba3f1800c766440fa70bfd3f834294d47d7ed9cfffd6d14ae18310f6c1d6d8f88b6c5d72a0b45608b4e21bbb8e314220ed7a2d6a8c95454e571c71b50f1d6a823778ca47131f5b889a1ed1957248bee8c4ac66872a5fd58a121560a27bad4958f1c763f2ffddL

p4 =0xda5df16f286dbc825cd0c8ee48aa26ac27338a75172c5b92351f14d083216f7e91b9355e27cf930646fbbda6058dec3c4ddf751f36df5556359fbe671f9b947b4c79cadfdbb27b57
#刚好144位十六进制，576位二进制

e = 0x10001
pbits = 1024

kbits = pbits - p4.nbits()
print p4.nbits()
p4 = p4 << kbits
PR.<x> = PolynomialRing(Zmod(n))
f = x + p4
roots = f.small_roots(X=2^kbits, beta=0.4)
#经过以上一些函数处理后，n和p已经被转化为10进制
if roots:        
    p = p4+int(roots[0]) 
    print "n: ", n   
    print "p: ", p
    print "q: ", n/p

运行结果

Paste_Image.png

142+2.py

from sage.all import *
n = 0x9d3a1a28ecb1bd245dd86b18dc4c5b729f23778710005118836129f08e31d6516de8ab47db1b3b7f660f50d283b1e9f2c06e7836136e4c0159f5d2b05771861d3ce6aa8715932eadc1cc0f380909a1961018340f7393142f9c177b1187151f97ac8cdc4ad17fa59a0f39d192af555f27de9cc800846eb2ca6ce78f87c0c0fbf47828328392b81771af624389fd779d130d80739bb7a608961125ba3f1800c766440fa70bfd3f834294d47d7ed9cfffd6d14ae18310f6c1d6d8f88b6c5d72a0b45608b4e21bbb8e314220ed7a2d6a8c95454e571c71b50f1d6a823778ca47131f5b889a1ed1957248bee8c4ac66872a5fd58a121560a27bad4958f1c763f2ffddL

p4 =0xda5df16f286dbc825cd0c8ee48aa26ac27338a75172c5b92351f14d083216f7e91b9355e27cf930646fbbda6058dec3c4ddf751f36df5556359fbe671f9b947b4c79cadfdbb27b00 
#最后面8位二进制，也就是两位十六进制要参与爆破运算，所以要用 00 补充
e = 0x10001
pbits = 1024

for i in range(0,256):    # 要爆破的8位二进制数，为2**8=256，表示0~255
    p4=0xda5df16f286dbc825cd0c8ee48aa26ac27338a75172c5b92351f14d083216f7e91b9355e27cf930646fbbda6058dec3c4ddf751f36df5556359fbe671f9b947b4c79cadfdbb27b00
    p4=p4+int(hex(i),16)
#    print hex(p4)
    kbits = pbits - p4.nbits()
#    print p4.nbits()
    p4 = p4 << kbits
    PR.<x> = PolynomialRing(Zmod(n))
    f = x + p4
    roots = f.small_roots(X=2^kbits, beta=0.4)
#经过以上一些函数处理后，n和p已经被转化为10进制
    if roots:
        p = p4+int(roots[0])
        print "n: ", n
        print "p: ", p
        print "q: ", n/p
        break

运行结果

Paste_Image.png

rsa.py

#!coding:utf-8
import libnum

p = 153342497773165720646471265753416937042378585974980600696228054280777067742118708748260148517704664270966750151230879697775745552153863038444052153549264336387543725044459125347571130674447630098572217293190874462747269265287826289527205379087607586543990164027856167617915226681078528645859423680436167557483
q = 129436166908331611554181128183182589454341960422674433223367230133752416435382709963204302422852744109315802741839344452057748805269289759475931297256986800620920742486276489445279916851138781600867108041340752127975698302831477903370939720026728065273734373673806527712975351406042878379903498709089420733911
n = p * q
e = 65537
c = 3936037472808777071308929516154413904323194935340248548327659414834313812796990403988095925642368079268517801058041656316181783492880322278956562595000260504254255037928037412478862828849501974686520351939250369196179274580006017942557434135384292957158484997604383679828898427028204052111920452543131945953240230799711698405726536262211948501121455918845580494839990978306064590105574542739676508765285583405238287804427122294772381588739840326134102495086948522002204793929245624099798045204501372180048163169180023176545149820275841071238390132249159995705693884766122963689536408510312667760860122892135226523829
phi = (p - 1) * (q - 1)
d = libnum.modular.invmod(e, phi)
m = libnum.n2s(pow(c, d, n))  #m是明文，也就是flag
print m   #flag{rs4_y0ok_s0_m2ch_1n_c7f_qu4ls_c0mp7t1t10n}