点击蓝字 关注我们
日期：2023-03-27
作者：nothing
介绍：RSA已知高位算法攻击的扩展。
0x00 前言
目前，在常规CTF比赛中，一般考察RSA已知高位算法攻击主要有三种：
-
已知
P的高位 -
已知
d的高位 -
已知
m的高位
最近在某次比赛中，碰到了一个奇怪的已知高位算法攻击，并不属于以上三种，初见非常奇怪，接下来展开分析一下。
0x01 RSA已知高位算法攻击变形
1.1 题目基础分析
首先我们来看题目给的脚本：
from Crypto.Util.number import *from secret import flagp = getPrime(512)q = getPrime(512)n = p * qe = 65537assert GCD(e, (p - 1) * (q - 1)) == 1secret = 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 << 440print('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参数，那么我们是不是可以从这里入手？
1.2 中国剩余定理
在从gift入手时，我们应该先看看sage中的中国剩余定理函数求的是什么。
简单来讲，就是得到一个数值gift，使得：
根据题目情况，那么可以将公式进行转化：
联立两个式子可得：
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的表达式。
得到两个常数，由于p和q均为素数，可以通过如下式子求得。
于是，求明文的关键参数均已知，直接编写脚本求解。
#coding:utf-8import libnumimport gmpy2gift = 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))
0x02 总结
有的时候未曾见过的题目并不难，只要我们了解原理，仔细分析，依然可以得到结果。
免责声明：本文仅供安全研究与讨论之用，严禁用于非法用途，违者后果自负。
原文始发于微信公众号（宸极实验室）：『CTF』RSA 已知高位算法攻击扩展
特别标注:
本站(CN-SEC.COM)所有文章仅供技术研究，若将其信息做其他用途，由用户承担全部法律及连带责任，本站不承担任何法律及连带责任，请遵守中华人民共和国安全法.
- 我的微信
- 微信扫一扫
-
- 我的微信公众号
- 微信扫一扫
-
评论