『CTF』RSA 已知高位算法攻击扩展

admin
admin
admin
100990
文章
86
评论
2023年3月27日20:32:23评论52 views字数 5983阅读19分56秒阅读模式

点击蓝字 关注我们


日期：2023-03-27

作者：nothing

介绍：RSA已知高位算法攻击的扩展。

0x00 前言

目前，在常规CTF比赛中，一般考察RSA已知高位算法攻击主要有三种：

  • 已知P的高位

  • 已知d的高位

  • 已知m的高位

最近在某次比赛中，碰到了一个奇怪的已知高位算法攻击，并不属于以上三种，初见非常奇怪，接下来展开分析一下。

0x01 RSA已知高位算法攻击变形

1.1 题目基础分析

首先我们来看题目给的脚本：

from Crypto.Util.number import *from secret import flag
p = getPrime(512)q = getPrime(512)n = p * qe = 65537assert GCD(e, (p - 1) * (q - 1)) == 1
secret = bytes_to_long(flag)
c = pow(secret, e, n)
x = bytes_to_long(urandom(64))y = bytes_to_long(urandom(64))gift = crt([x, y], [p, q])
n = n >> 440 << 440
print('n = 0x{:x}'.format(n))print('e = 0x{:x}'.format(e))print('c = 0x{:x}'.format(int(c)))print('gift = 0x{:x}, 0x{:x}, 0x{:x}'.format(x, y, gift))
'''n = 0x96ec5a787fe02affea57b535d2ca3475612722967c8d67d2dc950ee7a67dcb432690bbf3ebbab64f1676956ed022d4c3e6fa075cc8f3e83dbb69e17aa8298f21e0fb03f5f119522ce800000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000e = 0x10001c = 0x45ed5cfedd662bc76cae0ec229b3d81328cffd1237640f1866fe4f33cd78ef7a2a3d8566e189cc284d9a901fc2de361ef50910df0830cec7fc02a34a6917107e2926a006fb38db9d2c8f5031c4445e0819a07632e19020f3076b2e1e311ee11f961204016464f7c8cb7a3c87b7571690f25db6bc7427b4156117776f16f6faefgift = 0x44b13cd3bccf0839cf7a4570f320a3588b7a6177a8b30237e2d3ccad6966db732e019a9e23312ff35171c2da9f1464f3249b77e67fff76c3f2e9b6390f6b5ec, 0xb168b2fcab63103ee619f387a20bbfcfeb0a87bf7f339dd6f84d5f93187c27a0bafa1e0317dc5a02055a6867810fdb0c1976fa9e0101278cafa8e778f4f6cf95, 0x648019c4947179187e1b091941e1b02579e6553935cd4a062a518e3a887e63f7bf7fae48f8aae6920349d0bfc2e43a3bb6dc0fa65fd9f8200e87b7c349313fd8ccbc5ed9397a15cf5f7e10634d9bebc62ddaca921fc91879d1c51c14f03231ca037bcb0858f0dfe5a0cabdd3a83cff3012babaf4792b8906291bfccfe4ec3e43'''


一眼望去，可以简单判断出是个RSA算法的攻击，在第19行的位置，对n的低位进行了处理。


此时，我们可以看出来题目其中一个考察点是考察已知n的高位，进行攻击。


一般来讲，n都会在题目中给出，因为n e c是题目基础，也是可以公开的公钥。但在常规的已知高位算法攻击中，常见的目标P d m都属于不可公开的范畴，是需要选手去求解的。


一开始看到n被隐藏了一部分，从未见过这种题目，一时之间就不知道该如何去解题了，但是看到题目还给了gift，使用了sage中的中国剩余定理（CRT）算法对p q进行处理后得到了gift参数，那么我们是不是可以从这里入手？


『CTF』RSA 已知高位算法攻击扩展


1.2 中国剩余定理


在从gift入手时，我们应该先看看sage中的中国剩余定理函数求的是什么。


『CTF』RSA 已知高位算法攻击扩展


简单来讲，就是得到一个数值gift，使得：


『CTF』RSA 已知高位算法攻击扩展


根据题目情况，那么可以将公式进行转化：


『CTF』RSA 已知高位算法攻击扩展


联立两个式子可得：


『CTF』RSA 已知高位算法攻击扩展


1.3 已知高位算法攻击扩展


由于x y gift已知，那么kn的值也已知，既然kn和n的高位已知，那么可以进行转化，此时的场景就跟p高位已知非常相似了，p高位已知的条件是已知n(p*q)和p的高位。


此时使用p高位已知攻击的方式代入：




    

  • 



gift = 0x648019c4947179187e1b091941e1b02579e6553935cd4a062a518e3a887e63f7bf7fae48f8aae6920349d0bfc2e43a3bb6dc0fa65fd9f8200e87b7c349313fd8ccbc5ed9397a15cf5f7e10634d9bebc62ddaca921fc91879d1c51c14f03231ca037bcb0858f0dfe5a0cabdd3a83cff3012babaf4792b8906291bfccfe4ec3e43x = 0x44b13cd3bccf0839cf7a4570f320a3588b7a6177a8b30237e2d3ccad6966db732e019a9e23312ff35171c2da9f1464f3249b77e67fff76c3f2e9b6390f6b5ecy = 0xb168b2fcab63103ee619f387a20bbfcfeb0a87bf7f339dd6f84d5f93187c27a0bafa1e0317dc5a02055a6867810fdb0c1976fa9e0101278cafa8e778f4f6cf95kn=(gift-x)*(gift-y)n4= 0x96ec5a787fe02affea57b535d2ca3475612722967c8d67d2dc950ee7a67dcb432690bbf3ebbab64f1676956ed022d4c3e6fa075cc8f3e83dbb69e17aa8298f21e0fb03f5f119522ce8e=0x10001pbits= 1024         #P原本的位数
kbits=pbits - n4.nbits()print(n4.nbits())n4 = n4 << kbitsPR.<x> = PolynomialRing(Zmod(kn))f = x + n4roots = f.small_roots(X=2^kbits,beta=0.4)if roots:    n = n4 + int(roots[0])    print("kn",kn)    print("n",n)    print("k",kn/n)




得到n的值：




    

  • 



kn = 4980657876699979171037727431278044516353490609371125174519293297098282433690593289401930064007588603689564177597240834964391532306337932535590613648694206711075180084681131198400803597775402715146865546731147403254594549791798461856203570920806815552181437521385568795460037641234232850430166518088024438087884211976734484230979447669349182529135400619745193769628574735307612155883922165946087004780512144296690832411055310283775913656306029411040811113026204689805591170712484533370570003981893694681641194170159970226096209166281005271783843096959549784001540388982470829784621136778886110874191314008094308764962n = 105981914162307114164284436984430654776409199486917174473845337951715428267158526999335634555199007925379849834074656222492454748642920817621993924080829754103593161926834903990161629519246472354278791202648634115011525364509904179452272295541923173693032458104746954821241105963000775859493241833292023026947k = 46995356859400542814009905638934191789002752381978296276073602002537436792274070516783000559359918906157861335138529914250085625138315010573455473024554293589779506551096300703135107597372366567783630393648549108696631189766926684735447793729755212395141596463860318974772091328393583169274619820464802488246






1.4 题目求解


我们得到n以后，无法直接进行分解获得p和q的值，但是根据上面的中国剩余定理的式子，可以得到关于k1*p和k2*q的表达式。


『CTF』RSA 已知高位算法攻击扩展


得到两个常数，由于p和q均为素数，可以通过如下式子求得。


『CTF』RSA 已知高位算法攻击扩展


于是，求明文的关键参数均已知，直接编写脚本求解。




    

  • 



#coding:utf-8import libnum import gmpy2
gift = 0x648019c4947179187e1b091941e1b02579e6553935cd4a062a518e3a887e63f7bf7fae48f8aae6920349d0bfc2e43a3bb6dc0fa65fd9f8200e87b7c349313fd8ccbc5ed9397a15cf5f7e10634d9bebc62ddaca921fc91879d1c51c14f03231ca037bcb0858f0dfe5a0cabdd3a83cff3012babaf4792b8906291bfccfe4ec3e43x = 0x44b13cd3bccf0839cf7a4570f320a3588b7a6177a8b30237e2d3ccad6966db732e019a9e23312ff35171c2da9f1464f3249b77e67fff76c3f2e9b6390f6b5ecy = 0xb168b2fcab63103ee619f387a20bbfcfeb0a87bf7f339dd6f84d5f93187c27a0bafa1e0317dc5a02055a6867810fdb0c1976fa9e0101278cafa8e778f4f6cf95k1p = gift - xk2q = gift - ye = 0x10001n = 0x96ec5a787fe02affea57b535d2ca3475612722967c8d67d2dc950ee7a67dcb432690bbf3ebbab64f1676956ed022d4c3e6fa075cc8f3e83dbb69e17aa8298f21e0fb03f5f119522ce80b02b89d83343cba4d9da3f4b79f34473d28768400bd1704d6b65b9add858801cdb00880ad123024d68263360bb0374d95da3f8f595503p = gmpy2.gcd(n,k1p)q = gmpy2.gcd(n,k2q)phi = (p-1)*(q-1)d = gmpy2.invert(e, phi)c = 0x45ed5cfedd662bc76cae0ec229b3d81328cffd1237640f1866fe4f33cd78ef7a2a3d8566e189cc284d9a901fc2de361ef50910df0830cec7fc02a34a6917107e2926a006fb38db9d2c8f5031c4445e0819a07632e19020f3076b2e1e311ee11f961204016464f7c8cb7a3c87b7571690f25db6bc7427b4156117776f16f6faefm=pow(c,d,n)print("p: ", p)print("q: ", q)print(libnum.n2s(m))






『CTF』RSA 已知高位算法攻击扩展




0x02 总结


有的时候未曾见过的题目并不难，只要我们了解原理，仔细分析，依然可以得到结果。




『CTF』RSA 已知高位算法攻击扩展








免责声明：本文仅供安全研究与讨论之用，严禁用于非法用途，违者后果自负。

































点此亲启












ABOUT US




























































































宸极实验室隶属山东九州信泰信息科技股份有限公司，致力于网络安全对抗技术研究，是山东省发改委认定的“网络安全对抗关键技术山东省工程实验室”。团队成员专注于 Web 安全、移动安全、红蓝对抗等领域，善于利用黑客视角发现和解决网络安全问题。










团队自成立以来，圆满完成了多次国家级、省部级重要网络安全保障和攻防演习活动，并积极参加各类网络安全竞赛，屡获殊荣。










对信息安全感兴趣的小伙伴欢迎加入宸极实验室，关注公众号，回复『招聘』，获取联系方式。




































『CTF』RSA 已知高位算法攻击扩展










原文始发于微信公众号（宸极实验室）：『CTF』RSA 已知高位算法攻击扩展






 


 



    

  • 
左青龙

    • 

  • 微信扫一扫
    • 

  • 
weinxin

    • 



    

  • 
右白虎

    • 

  • 微信扫一扫
    • 

  • 
weinxin

    • 
























admin 
    

  • 本文由  发表于 2023年3月27日20:32:23
    • 

  • 转载请保留本文链接(CN-SEC中文网:感谢原作者辛苦付出)：
                  
『CTF』RSA 已知高位算法攻击扩展https://cn-sec.com/archives/1633609.html

    • 














 











 















发表评论

匿名网友
填写信息