Crypto方向 · RSA已知部分明文攻击（Coppersmith方法）
前言
RSA是现代密码学中最重要的公钥加密算法之一，也是CTF Crypto方向的绝对核心。基础题通常考察小指数攻击或模数分解，而中高难度题目则会引入“部分信息已知”的场景。本文记录一道利用Coppersmith定理进行已知部分明文攻击的RSA题目，涉及数学原理和SageMath的实际运用。
题目信息
题目类型：Crypto（密码学）
难度：中等偏上
考点：RSA低指数攻击、Coppersmith部分明文恢复、位运算组合
题目分析
题目提供了以下参数：
text
n = 27370629712265847736600046177005821691581086495342396405013603830032804068080902752646178713706534768393355277275788966190461414605728435199450646068466647183172585100315139289446443960705795169960597815998175190063349195716401357223150874800762603349462517459494645747760164366023005377564249219716490566541374404444803532553420389551761430687421437780343368250869426515948406473053176630355236531331652399712078496738764049767639892679165481038891140604066186174810524142615143841912987971244756321683636512499203687944097019471103580795695352255275690262703115882483587558248551096959297111698969768592580242084097 c = 1557974293836686620479803297055981255173294887334078630167778856434167424264007810073143778756176642455402946297784187215981544835841313138937511628513130192377025667873401296499371446604428582115859563468102950851848672098173056097329133454833145574558610013188609296949103186869418815764434710595779246977750075810798366405667912758762265393444005476827380083156638727759312811623706003861931646420680997699407702311574089758537358249515031928646591476403757371490160098423576492108256338277317069383138208259273136089223027770021437032357274935019014966953079095700750633954829613345454780253561362366575661875972 m2 = 109523686857584638682616948754368399421717367895768942835664937 hint = 15939899833541126262111172880473230205865802039037676959882528789415258862035357464871013500168468232573646139002622197659262180255514894193358745612585078460884305691357549352923832310106473762537849167447998941166146474639826807780168716207323503421827070595661272793064952671083638515691513856540332014480428529309924994303622400622921137814828287596594004980550818478382681627952640415470996625330833550504934455847133834046936668521187854573702254127450009317320632947000887127902725365843056703969480240603563039551642381484375512409405173696904562545347457898439153234798724542562229895730486778784948713986987
关键线索
e = 3（低加密指数，这是Coppersmith攻击的前提）
已知
m2 = m & hint（m与hint按位与的结果）已知
hint本身加密对象是
m | hint（m与hint按位或的结果）的3次方模n
数学原理
根据位运算性质：
当
m2的某一位为1时，说明m的该位必然为1当
hint的某一位为0且m|hint的某一位为1时，说明m的该位必然为1
因此，hint和m2可以恢复m的大部分比特位，只剩下那些hint为1且m2为0的比特位未知。
解题步骤
第一步：还原已知比特
将hint转换为二进制，长度为h_l。将m2填充到相同长度：
python
h = [int(i) for i in bin(hint)[2:]] h_l = len(bin(hint)[2:]) m_1 = [int(i) for i in bin(m2)[2:].zfill(h_l)]
利用已知比特构造mbar（m的近似值，未知比特置0）：
python
mbar = 0 for i in range(len(h)): mbar += h[i] * pow(2, len(h) - i - 1)
第二步：Coppersmith恢复未知比特
未知比特的数量为kbits。由于mbar已经接近真实的m，且e=3，可以使用Coppersmith的小根方法求解：
python
def decrypt(n, e, c, mbar, kbits): nbits = n.nbits() PR.<x> = PolynomialRing(Zmod(n)) f = (mbar + x) ^ e - c x0 = f.small_roots(X=2^kbits, beta=0.4)[0] return x0
这里small_roots是SageMath中实现Coppersmith定理的函数，可以在模n下找到小根x0，即未知比特的数值。
第三步：组合还原完整m
得到x0后，m = mbar + x0。但为了确保准确性，还可以利用m2和hint进行二次验证：
python
# hh为 m|hint 的按位表示 hh = [int(i) for i in bin(mbar + x0)[2:].zfill(h_l)] m = [0 for i in range(h_l)] for i in range(h_l): if m_1[i] == 1: # m2为1 → m的该位为1 m[i] = 1 if h[i] == 0 and hh[i] == 1: # hint为0但m|hint为1 → m的该位为1 m[i] = 1 flag = long_to_bytes(int(''.join(map(str, m)), 2)) print(flag)最终Flag
text
flag{llsa_jdjlksajldjsdjk1}知识点总结
Coppersmith定理：当已知RSA明文的大部分比特时，可以通过小根方法恢复剩余未知比特，尤其适用于低加密指数（e=3）场景。
位运算特性：利用
&和|的性质，可以从部分信息反推完整明文——当m&hint为1时m必为1，当hint为0且m|hint为1时m必为1。SageMath：处理数论和密码学问题的利器，内置了Coppersmith、LLL格基约简等高级算法。