点击蓝字 关注我们
日期: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 * q
e = 65537
assert 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 = 0x96ec5a787fe02affea57b535d2ca3475612722967c8d67d2dc950ee7a67dcb432690bbf3ebbab64f1676956ed022d4c3e6fa075cc8f3e83dbb69e17aa8298f21e0fb03f5f119522ce800000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
e = 0x10001
c = 0x45ed5cfedd662bc76cae0ec229b3d81328cffd1237640f1866fe4f33cd78ef7a2a3d8566e189cc284d9a901fc2de361ef50910df0830cec7fc02a34a6917107e2926a006fb38db9d2c8f5031c4445e0819a07632e19020f3076b2e1e311ee11f961204016464f7c8cb7a3c87b7571690f25db6bc7427b4156117776f16f6faef
gift = 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 = 0x648019c4947179187e1b091941e1b02579e6553935cd4a062a518e3a887e63f7bf7fae48f8aae6920349d0bfc2e43a3bb6dc0fa65fd9f8200e87b7c349313fd8ccbc5ed9397a15cf5f7e10634d9bebc62ddaca921fc91879d1c51c14f03231ca037bcb0858f0dfe5a0cabdd3a83cff3012babaf4792b8906291bfccfe4ec3e43
x = 0x44b13cd3bccf0839cf7a4570f320a3588b7a6177a8b30237e2d3ccad6966db732e019a9e23312ff35171c2da9f1464f3249b77e67fff76c3f2e9b6390f6b5ec
y = 0xb168b2fcab63103ee619f387a20bbfcfeb0a87bf7f339dd6f84d5f93187c27a0bafa1e0317dc5a02055a6867810fdb0c1976fa9e0101278cafa8e778f4f6cf95
kn=(gift-x)*(gift-y)
n4= 0x96ec5a787fe02affea57b535d2ca3475612722967c8d67d2dc950ee7a67dcb432690bbf3ebbab64f1676956ed022d4c3e6fa075cc8f3e83dbb69e17aa8298f21e0fb03f5f119522ce8
e=0x10001
pbits= 1024 #P原本的位数
kbits=pbits - n4.nbits()
print(n4.nbits())
n4 = n4 << kbits
PR.<x> = PolynomialRing(Zmod(kn))
f = x + n4
roots = 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 = 4980657876699979171037727431278044516353490609371125174519293297098282433690593289401930064007588603689564177597240834964391532306337932535590613648694206711075180084681131198400803597775402715146865546731147403254594549791798461856203570920806815552181437521385568795460037641234232850430166518088024438087884211976734484230979447669349182529135400619745193769628574735307612155883922165946087004780512144296690832411055310283775913656306029411040811113026204689805591170712484533370570003981893694681641194170159970226096209166281005271783843096959549784001540388982470829784621136778886110874191314008094308764962
n = 105981914162307114164284436984430654776409199486917174473845337951715428267158526999335634555199007925379849834074656222492454748642920817621993924080829754103593161926834903990161629519246472354278791202648634115011525364509904179452272295541923173693032458104746954821241105963000775859493241833292023026947
k = 46995356859400542814009905638934191789002752381978296276073602002537436792274070516783000559359918906157861335138529914250085625138315010573455473024554293589779506551096300703135107597372366567783630393648549108696631189766926684735447793729755212395141596463860318974772091328393583169274619820464802488246
1.4 题目求解
我们得到n
以后,无法直接进行分解获得p
和q
的值,但是根据上面的中国剩余定理的式子,可以得到关于k1*p
和k2*q
的表达式。
得到两个常数,由于p
和q
均为素数,可以通过如下式子求得。
于是,求明文的关键参数均已知,直接编写脚本求解。
#coding:utf-8
import libnum
import gmpy2
gift = 0x648019c4947179187e1b091941e1b02579e6553935cd4a062a518e3a887e63f7bf7fae48f8aae6920349d0bfc2e43a3bb6dc0fa65fd9f8200e87b7c349313fd8ccbc5ed9397a15cf5f7e10634d9bebc62ddaca921fc91879d1c51c14f03231ca037bcb0858f0dfe5a0cabdd3a83cff3012babaf4792b8906291bfccfe4ec3e43
x = 0x44b13cd3bccf0839cf7a4570f320a3588b7a6177a8b30237e2d3ccad6966db732e019a9e23312ff35171c2da9f1464f3249b77e67fff76c3f2e9b6390f6b5ec
y = 0xb168b2fcab63103ee619f387a20bbfcfeb0a87bf7f339dd6f84d5f93187c27a0bafa1e0317dc5a02055a6867810fdb0c1976fa9e0101278cafa8e778f4f6cf95
k1p = gift - x
k2q = gift - y
e = 0x10001
n = 0x96ec5a787fe02affea57b535d2ca3475612722967c8d67d2dc950ee7a67dcb432690bbf3ebbab64f1676956ed022d4c3e6fa075cc8f3e83dbb69e17aa8298f21e0fb03f5f119522ce80b02b89d83343cba4d9da3f4b79f34473d28768400bd1704d6b65b9add858801cdb00880ad123024d68263360bb0374d95da3f8f595503
p = gmpy2.gcd(n,k1p)
q = gmpy2.gcd(n,k2q)
phi = (p-1)*(q-1)
d = gmpy2.invert(e, phi)
c = 0x45ed5cfedd662bc76cae0ec229b3d81328cffd1237640f1866fe4f33cd78ef7a2a3d8566e189cc284d9a901fc2de361ef50910df0830cec7fc02a34a6917107e2926a006fb38db9d2c8f5031c4445e0819a07632e19020f3076b2e1e311ee11f961204016464f7c8cb7a3c87b7571690f25db6bc7427b4156117776f16f6faef
m=pow(c,d,n)
print("p: ", p)
print("q: ", q)
print(libnum.n2s(m))
0x02 总结
有的时候未曾见过的题目并不难,只要我们了解原理,仔细分析,依然可以得到结果。
免责声明:本文仅供安全研究与讨论之用,严禁用于非法用途,违者后果自负。
原文始发于微信公众号(宸极实验室):『CTF』RSA 已知高位算法攻击扩展
- 我的微信
- 微信扫一扫
-
- 我的微信公众号
- 微信扫一扫
-
评论