学习
实践
活动
专区
工具
TVP
写文章

RSA的已知高位攻击

当在比赛遇到知道p或q的高位因子时,我们就可以用这种方法分解从而得到p,q ,这里我们以WHCTF的Untitled题为例子讲解一下这种攻击方法

首先是看加密的源码

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)

这里相当于随机生成了1024位的p和q,然后给了e,跟RSA的算法一样生成私钥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

第一段验证的程度,需要我们给一段base64编码的work,然后salt+work的md5的开头要是"0000",直接用代码爆破得到合适的work

salt=p.recvline()
msg = base64.b64decode(salt)
work=""
for i in count():
    hashid = md5(msg+str(i)).hexdigest()
    if hashid.startswith('0000'):
        #print i,hashid
        work=base64.b64encode(str(i))
        break

继续看

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) #取hex(m)的前八位      t=1718378855
    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()

这里大概意思就是题目会返回给我们n,e,c,u的值,并且我们需要输入x,y使得pow(x,e,n)==y and pow(y,d,n)==t才会返回给我们s,那么仔细来看看,首先n,e,c的意思大家应该明白。看看t=int(hex(m)[2:][0:8],16)这句代码,我在后面写了备注,就是取hex(m)的前八位十六进制即4个字符,而题目给了tips,m是flag{*}形式的。所以t是固定的。然后继续看,需要我们输入一个x0,y0然后x=t+x0,y=y0使得pow(x,e,n)==y and pow(y,d,n)==t

到这里我们可以分析一下数学逻辑,根据RSA的逻辑

c=pow(m,e,n)<===>m=pow(c,d,n)
 u=pow(t,e,n)<===>t=pow(u,d,n)

而题目要求

t==pow(y,d,n) ==>y=u
 y==pow(x,e,n) <==> u==pow(x,e,n) ==>x=t

所以我们可以知道y=u,x=t结合x=t+x0,y=y0可以得出x0=空字符 y0=u, 按要求输入x0,y0就能得到s了,这里放最终代码

#coding=utf-8
from pwn import *
from itertools import count
from hashlib import md5
import base64
 
p=remote('118.31.18.75',20013)
 
salt=p.recvline()
msg = base64.b64decode(salt)
work=""
for i in count():
    hashid = md5(msg+str(i)).hexdigest()
    if hashid.startswith('0000'):
        #print i,hashid
        work=base64.b64encode(str(i))
        break
#print work
t=1718378855
p.recvuntil('work: ')
p.sendline(work)
print p.recvline()
print p.recvline()
print p.recvline()
print p.recvline()
u = int(p.recvline()[5:-2],16)   #u
print "u:",hex(u)
print p.recvline()
p.recvuntil('x: ')
#print str(hex(t))
p.sendline("")  #x
print p.recvline()
p.recvuntil('y: ')  #y
p.sendline(str(hex(u))[2:])
# p_568=int(p.recvline()[5:-2],16)
# print "p_568:",hex(p_568)
print p.recvline()

继续分析得到s,是p的前568位二进制数组成的数,这里有个小坑,直接拿去高位攻击是不行的,因为必须要已知576位才能高位攻击,所以我们要爆破568到576中的八位二进制数即两位十六进制然后再进行已知高位攻击,直接放sage代码

from sage.all import *
import binascii
n =   0x9d3a1a28ecb1bd245dd86b18dc4c5b729f23778710005118836129f08e31d6516de8ab47db1b3b7f660f50d283b1e9f2c06e7836136e4c0159f5d2b05771861d3ce6aa8715932eadc1cc0f380909a1961018340f7393142f9c177b1187151f97ac8cdc4ad17fa59a0f39d192af555f27de9cc800846eb2ca6ce78f87c0c0fbf47828328392b81771af624389fd779d130d80739bb7a608961125ba3f1800c766440fa70bfd3f834294d47d7ed9cfffd6d14ae18310f6c1d6d8f88b6c5d72a0b45608b4e21bbb8e314220ed7a2d6a8c95454e571c71b50f1d6a823778ca47131f5b889a1ed1957248bee8c4ac66872a5fd58a121560a27bad4958f1c763f2ffddL
 
 
cipher = 0x1f2deea59244b14e53c72465febc2064172a35245842fa83ebff313344bed35ee8af8c3f8f61e6f498fa1fd35e63998a573d7717905f72ec01de0b0529eaab10eb0b0c2ca06e9d6e4245e748fd74f4f756a86e379559793389a3ae6c421d51bb78331a487fc3c3e68971e3e26991ab34ce2a2c07ffd5a5a1e215e766b51fb2d6aab63c2dafa3c87d0a5eb79b634740e1fca7a727de997958839bda684e19acad93cae4abfd1c8cc3684419f83696fe4840f3253e7c038adb13a1382667cf7e17ef55c1e950ea474594102e660e36a23bfd3fd830d1c18a434d0b34bed98308399a894dcab909d68bcab7c7ac990974a4f6ed7d612abb7044f6734eaaebcdc0b5L
 
e2 = 0x10001
pbits = 1024
for i in range(0,127):
    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) #进行爆破
    #rint roots
  if roots:        #爆破成功,求根
        p = p4+int(roots[0])
        print "p: ", hex(int(p))
        assert n % p == 0
        q = n/int(p)
        print "q: ", hex(int(q))
        print gcd(p,q)
        phin = (p-1)*(q-1)
        print gcd(e2,phin)
        d = inverse_mod(e2,phin)
        flag = pow(cipher,d,n)
        flag = hex(int(flag))[2:-1]
        print binascii.unhexlify(flag)
文章分享自微信公众号:
安恒网络空间安全讲武堂

本文参与 腾讯云自媒体分享计划 ,欢迎热爱写作的你一起参与!

作者:hacker_mao
原始发表时间:2018-01-12
如有侵权,请联系 cloudcommunity@tencent.com 删除。
登录 后参与评论
0 条评论

相关文章

  • RSA的常见攻击

    上文我们介绍了RSA算法原理,只要我们设置得当,我们有足够多的理由相信我们的RSA系统是安全的,但是粗心的我们,能否禁得住黑客的攻城掠池?下面介绍一些RSA的常...

    耶鲁信
  • 目前已知的最强加密算法RSA

    前面有人让我讲解一下RSA算法,今天我就用我所学的知识讲解一下,首先我们先了解一下RSA

    IT大咖说
  • RSA大会趋势聚焦:最危险的新型攻击手段

    SANS研究所的研究员兼主任Ed Skoudis指出,破坏软件完整性是他在如今看到的最大攻击载体之一。软件完整性包括构成现代应用程序的所有嵌入式库和组件的供应链...

    FB客服
  • 国内黑客论坛已出现自动攻击已知Struts漏洞的工具

    中国黑客现在正是用一个自动工具利用Apache Struts中的已知漏洞,目的是在用这个框架开发的用于托管应用的服务器上安装后门。 Ap...

    安恒信息
  • RSA算法及一种"旁门左道"的攻击方式

    RSA 算法一种常见的非对称加密算法, 常用来对一些在网络上传输的敏感信息进行加密, 本文将概述RSA算法的流程以及一种意想不到的”旁门左道”的攻击方式.

    程序猿石头
  • RSA创新沙盒盘点|Lightspin——攻击者视角下的DevOps安全

    RSAConference2022将于旧金山时间6月6日召开。大会的Innovation Sandbox(沙盒)大赛作为“安全圈的奥斯卡”,每年都备受瞩目,成为...

    绿盟科技研究通讯
  • Dan Boneh密码学笔记11

    11.Public Key Encryption from trapdoor permutations

    安包
  • 【RSA2019创新沙盒】Salt Security:探测与防御API攻击的解决方案及平台

    Salt Security是一家起源于以色列的安全服务公司,公司于2016年成立,总部设在硅谷和以色列,创始人有以色列国防军校友、网络安全领域专家等。该公司致力...

    绿盟科技研究通讯
  • RSA 创新沙盒盘点| Tala Security—高效检测和防护各种针对WEB客户端的攻击

    2020年2月24日-28日,网络安全行业盛会RSA Conference将在旧金山拉开帷幕。已经相继向大家介绍了入选今年创新沙盒的十强初创公司:Elevate...

    绿盟科技研究通讯
  • 现代密码系列:RSA密码详解

    1977年,三位数学家Rivest、Shamir 和 Adleman 设计了一种算法,可以实现非对称加密。这种算法用他们三个人的名字命名,叫做RSA算法

    红客突击队
  • RSA 背后的算法

    这篇文章我本来是想写了放到极客时间上我写的专栏里面的,但是专栏的内容是需要仔细斟酌的。这篇文章我认为还是偏难,不适合整个专栏的内容和难度的定位,因此我把它稍微加...

    四火
  • RSA常见解题思路及技巧

    1977年,麻省理工学院的 Ron Rivest、Adi Shamir 和 Leonard Adleman 共同提出了一种非对称加密算法,用他们三人的姓氏缩写命...

    tinyfisher
  • “历史遗留”漏洞:浅析新型SSL/TLS漏洞FREAK

    最近安全研究人员发现一种新型SSL/TLS漏洞。预计在十年内,数以百万计的苹果、安卓用户访问HTTPS网站时将可能遭受中间人进而被窃取账号和密码,即使这些网站使...

    FB客服
  • 攻击者使用“非恶意软件”也能识别,来看看这个即将在RSA 2017上发布的新技术

    常见的黑客攻击往往以病毒程序或恶意文件为载体,通过网络进行传播——这种攻击方式较容易被端点防护程序所检测到。但是如果黑客不走寻常路呢?在下周即将到来的RSA C...

    FB客服
  • 非对称密钥沉思系列(1):RSA专题之PKCSv1.5填充模式下的选择性密文攻击概述

    本文主要梳理RSA 在PKCSv1.5 Padding模式下的 Oracle攻击。

    bowenerchen
  • 密码体制如何应对“量子霸权”?

    量子计算是目前全世界范围内的前沿研究热点,并可能正以量子体积每年翻倍的“量子摩尔定律”向前发展。然而,由于量子计算机的强大运算能力,一旦“量子霸权”成为现实,现...

    FB客服
  • 技术分享 | 浅谈 RAS

    一 首先介绍一下什么是RSA RSA算法是一种非对称密码算法,所谓非对称,就是指该算法需要一对密钥,使用其中一个加密,则需要用另一个才能解密。 RSA的算法涉及...

    安恒网络空间安全讲武堂
  • CCERT月报:物联网安全需从网络层加强控制

    2017年12月教育网运行正常,未发现影响严重的安全事件。近期一个存在于TLS加密协议中的漏洞被披露,漏洞是因为TLS协议在使用RSA算法协商加密密钥的过程中存...

    企鹅号小编
  • 【愚公系列】2021年12月 攻防世界-简单题-CRYPTO-008(easy_RSA)

    题目描述:解答出来了上一个题目的你现在可是春风得意,你们走向了下一个题目所处的地方 你一看这个题目傻眼了,这明明是一个数学题啊!!!可是你的数学并不好。扭头看向...

    愚公搬代码

扫码关注腾讯云开发者

领取腾讯云代金券