Crypto方向 · RSA已知部分明文攻击（Coppersmith方法）

前言RSA是现代密码学中最重要的公钥加密算法之一也是CTF Crypto方向的绝对核心。基础题通常考察小指数攻击或模数分解而中高难度题目则会引入“部分信息已知”的场景。本文记录一道利用Coppersmith定理进行已知部分明文攻击的RSA题目涉及数学原理和SageMath的实际运用。题目信息题目类型Crypto密码学难度中等偏上考点RSA低指数攻击、Coppersmith部分明文恢复、位运算组合题目分析题目提供了以下参数textn 27370629712265847736600046177005821691581086495342396405013603830032804068080902752646178713706534768393355277275788966190461414605728435199450646068466647183172585100315139289446443960705795169960597815998175190063349195716401357223150874800762603349462517459494645747760164366023005377564249219716490566541374404444803532553420389551761430687421437780343368250869426515948406473053176630355236531331652399712078496738764049767639892679165481038891140604066186174810524142615143841912987971244756321683636512499203687944097019471103580795695352255275690262703115882483587558248551096959297111698969768592580242084097 c 1557974293836686620479803297055981255173294887334078630167778856434167424264007810073143778756176642455402946297784187215981544835841313138937511628513130192377025667873401296499371446604428582115859563468102950851848672098173056097329133454833145574558610013188609296949103186869418815764434710595779246977750075810798366405667912758762265393444005476827380083156638727759312811623706003861931646420680997699407702311574089758537358249515031928646591476403757371490160098423576492108256338277317069383138208259273136089223027770021437032357274935019014966953079095700750633954829613345454780253561362366575661875972 m2 109523686857584638682616948754368399421717367895768942835664937 hint 15939899833541126262111172880473230205865802039037676959882528789415258862035357464871013500168468232573646139002622197659262180255514894193358745612585078460884305691357549352923832310106473762537849167447998941166146474639826807780168716207323503421827070595661272793064952671083638515691513856540332014480428529309924994303622400622921137814828287596594004980550818478382681627952640415470996625330833550504934455847133834046936668521187854573702254127450009317320632947000887127902725365843056703969480240603563039551642381484375512409405173696904562545347457898439153234798724542562229895730486778784948713986987关键线索e 3低加密指数这是Coppersmith攻击的前提已知m2 m hintm与hint按位与的结果已知hint本身加密对象是m | hintm与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填充到相同长度pythonh [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)]利用已知比特构造mbarm的近似值未知比特置0pythonmbar 0 for i in range(len(h)): mbar h[i] * pow(2, len(h) - i - 1)第二步Coppersmith恢复未知比特未知比特的数量为kbits。由于mbar已经接近真实的m且e3可以使用Coppersmith的小根方法求解pythondef decrypt(n, e, c, mbar, kbits): nbits n.nbits() PR.x PolynomialRing(Zmod(n)) f (mbar x) ^ e - c x0 f.small_roots(X2^kbits, beta0.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)最终Flagtextflag{llsa_jdjlksajldjsdjk1}知识点总结Coppersmith定理当已知RSA明文的大部分比特时可以通过小根方法恢复剩余未知比特尤其适用于低加密指数e3场景。位运算特性利用和|的性质可以从部分信息反推完整明文——当mhint为1时m必为1当hint为0且m|hint为1时m必为1。SageMath处理数论和密码学问题的利器内置了Coppersmith、LLL格基约简等高级算法。