neighbors - Writeup by AI题目信息项目内容题目来源BugKu CTF题目类型Crypto (密码学)题目名称neighbors考点RSA 相邻素数攻击题目描述给定 RSA 加密参数 N、e 和密文 C要求解密得到 flag。已知参数N: 262420780152597333698039900767940320110926001063611834222223935272233917586717817241241980476469295297770230962211064415375076352352402900252000601836692825013694387846914121404292230841763831332391815318452440874507285274278330781709313119976870933068292863367403123898410422525745209914263542477770418569824670451755583709443862248574660774352806444679043218130714546519174834221165277250236122060646172369023283085178560696659331828881461084507523512566437766408499674167607009484258981353696963928550533083687867035415613914431177746631860216050411485397051202984514522290692004239076425941380549671322275440116417323972801213615176600079770646252791706478662597536261827724795850288807054217613325267018094543813353995795071093392212248123864324510946508181475569738110148654529115407702149372555131365975117215159562802664529474022295519414336745835804314758894305606500546758492507352606373800383745919678854045582193560519914064015183428703364363090004322439846572640848060621496799241955579429075757085841996959787438332103581061458106268551351626688864844301858482855783288056959370819928149033614203731943820368777997506217823194522164025537530209543668719825177331971369323090100356263754530575057478659460643919563066431e: 65537C: 219816901321562291911575140776864567928747963331207674106436836756904762282945320476903790119347107242931375050548719411350997548616458951554837736849716037166794776326231311286467074941587722461315144687432296544567479640675640723205743718067809483824011516198995336356916999348823260580954477473961823827214363560235292117280397583069322920458699289386166228137316039166276143361085333156347839757264771096695526014104059059614286034869595031442695731239270819032230737167369092226721275120957150914104520190846238012549850274857247032369491871454870653495405873929633017439267997698438996125999328567832891604117320323518188379737667195322510716018077693075379175578611930009107853260007366665316181698662873400672816553698247325079206815500612064568422274388888198891778626716012936039047613573541758380712496035855568942356862418959109766496195086322223604837451946047067583680525273984331165778891119946572601392787145972361935141010444041925311955353392731146207322394555341662964364804182237024925511655062590048032550261231029124485148177623163843823413772348564678748509834413860685400856912215702081703918004976590918375377385883400248063202372328255796167029699923788825086393378274628306851728459890047030096492603208361考点分析核心漏洞通过分析challenge.py发现pnumber.getPrime(2048)qnext_prime(p)# q 是 p 的下一个素数这是一个典型的 RSA 相邻素数攻击场景。考点分值权重表考点分值占比重要程度识别相邻素数攻击40%⭐⭐⭐⭐⭐大数开方运算20%⭐⭐⭐⭐RSA 解密流程30%⭐⭐⭐⭐⭐Python gmpy2 库使用10%⭐⭐⭐解题思路1. 数学原理当q next_prime(p)时p 和 q 非常接近满足p √N qN p × q ≈ p²p ≈ √N2. 攻击步骤对 N 开平方根使用gmpy2.isqrt(N)得到近似值向下搜索 p从√N开始递减找到第一个能整除 N 的数计算 qq N // p验证关系确认q next_prime(p)常规 RSA 解密计算欧拉函数φ(N) (p-1)(q-1)计算私钥d e⁻¹ mod φ(N)解密m C^d mod N转字节flag long_to_bytes(m)详细步骤步骤 1对 N 开方importgmpy2 sqrt_Ngmpy2.isqrt(N)print(f√N ≈{sqrt_N})输出√N ≈ 16199406783971977709737568977858836641657922664000067967821674214522413834696919346471334462809542458580215660810886769605760499796145206676599257271144070133918270477355265658803835667028151086410174787976036056874642312725310471314917095594520807811974657416648651613827058534831532563591883471396375727827034936486836755780412475763226765564890324456516505496493404979673734723075172366995688611109468400952443130770886694694396021502093267180390692918067812923611158690569176483524787471635254268915729074462520130478796517882171640731943548607663642805224620747888666656538146579211625678185124560874144745189639步骤 2寻找因子 ppsqrt_NwhileTrue:ifN%p0:print(f[] 找到因子 p:{p})breakp-1由于 p 略小于 √N只需向下搜索几次即可找到。步骤 3验证 qqN//p next_pgmpy2.next_prime(p)print(fq next_prime(p):{qnext_p})# True步骤 4RSA 解密phi(p-1)*(q-1)dgmpy2.invert(e,phi)mpow(C,d,N)flagnumber.long_to_bytes(m)完整代码#!/usr/bin/env python3# -*- coding: utf-8 -*- 题目neighbors - RSA 相邻素数攻击 考点当 q next_prime(p) 时p 和 q 非常接近可通过对 N 开方快速分解 importgmpy2fromCrypto.Utilimportnumber# 从 chall 文件读取数据N262420780152597333698039900767940320110926001063611834222223935272233917586717817241241980476469295297770230962211064415375076352352402900252000601836692825013694387846914121404292230841763831332391815318452440874507285274278330781709313119976870933068292863367403123898410422525745209914263542477770418569824670451755583709443862248574660774352806444679043218130714546519174834221165277250236122060646172369023283085178560696659331828881461084507523512566437766408499674167607009484258981353696963928550533083687867035415613914431177746631860216050411485397051202984514522290692004239076425941380549671322275440116417323972801213615176600079770646252791706478662597536261827724795850288807054217613325267018094543813353995795071093392212248123864324510946508181475569738110148654529115407702149372555131365975117215159562802664529474022295519414336745835804314758894305606500546758492507352606373800383745919678854045582193560519914064015183428703364363090004322439846572640848060621496799241955579429075757085841996959787438332103581061458106268551351626688864844301858482855783288056959370819928149033614203731943820368777997506217823194522164025537530209543668719825177331971369323090100356263754530575057478659460643919563066431e65537C219816901321562291911575140776864567928747963331207674106436836756904762282945320476903790119347107242931375050548719411350997548616458951554837736849716037166794776326231311286467074941587722461315144687432296544567479640675640723205743718067809483824011516198995336356916999348823260580954477473961823827214363560235292117280397583069322920458699289386166228137316039166276143361085333156347839757264771096695526014104059059614286034869595031442695731239270819032230737167369092226721275120957150914104520190846238012549850274857247032369491871454870653495405873929633017439267997698438996125999328567832891604117320323518188379737667195322510716018077693075379175578611930009107853260007366665316181698662873400672816553698247325079206815500612064568422274388888198891778626716012936039047613573541758380712496035855568942356862418959109766496195086322223604837451946047067583680525273984331165778891119946572601392787145972361935141010444041925311955353392731146207322394555341662964364804182237024925511655062590048032550261231029124485148177623163843823413772348564678748509834413860685400856912215702081703918004976590918375377385883400248063202372328255796167029699923788825086393378274628306851728459890047030096492603208361print([*] 开始分解 N...)# 方法对 N 开平方根因为 p ≈ q ≈ √Nsqrt_Ngmpy2.isqrt(N)print(f[*] √N ≈{sqrt_N})# 从 sqrt_N 开始向下搜索找到第一个能整除 N 的数即为 ppsqrt_NwhileTrue:ifN%p0:print(f[] 找到因子 p:{p})breakp-1qN//pprint(f[] 找到因子 q:{q})# 验证 q 确实是 p 的下一个素数next_pgmpy2.next_prime(p)print(f[*] 验证next_prime(p) {next_p})print(f[*] q next_prime(p):{qnext_p})# 计算欧拉函数phi(p-1)*(q-1)# 计算私钥 ddgmpy2.invert(e,phi)print(f[*] 计算私钥 d:{d})# 解密得到明文mpow(C,d,N)print(f[*] 解密得到明文整数{m})# 将整数转换为字节串flag_bytesnumber.long_to_bytes(m)print(f[] Flag:{flag_bytes.decode()})运行结果[*] 开始分解 N... [*] √N ≈ 16199406783971977709737568977858836641657922664000067967821674214522413834696919346471334462809542458580215660810886769605760499796145206676599257271144070133918270477355265658803835667028151086410174787976036056874642312725310471314917095594520807811974657416648651613827058534831532563591883471396375727827034936486836755780412475763226765564890324456516505496493404979673734723075172366995688611109468400952443130770886694694396021502093267180390692918067812923611158690569176483524787471635254268915729074462520130478796517882171640731943548607663642805224620747888666656538146579211625678185124560874144745189639 [] 找到因子 p: 16199406783971977709737568977858836641657922664000067967821674214522413834696919346471334462809542458580215660810886769605760499796145206676599257271144070133918270477355265658803835667028151086410174787976036056874642312725310471314917095594520807811974657416648651613827058534831532563591883471396375727827034936486836755780412475763226765564890324456516505496493404979673734723075172366995688611109468400952443130770886694694396021502093267180390692918067812923611158690556917648352478747163525426891572907446252013047879651788217164073194354860766364280522462074788866656538146579211625678185124560874144745189639127 [] 找到因子 q: 161994067839719777097375689778588366416579226640000679967821674214522413834696919346471334462809542458580215660810886769605766049979614520667659925727114407013391827047735526565880383566702815108664101747879760360568746423127253104713149170955945208078119744657416648651613827058534831532563591883471396375727827034936486836755778041247576632267655648903244565165054964934049796737347230751723669956888611109468840095244313077088669469439602150209326718039069291806781292361115869056917648352478747163525426891572907446252013047879651788217166407319435486076636428052246207478886666565381465792116256781851245608774144745190153 [*] 验证next_prime(p) q [*] q next_prime(p): True [] Flag: shellmates{XXX}攻击链图谱┌─────────────────────┐ │ 分析 challenge.py │ │ 发现 qnext_prime(p)│ └──────────┬──────────┘ ↓ ┌─────────────────────┐ │ 数学特性p ≈ q │ │ N p×q ≈ p² │ │ p ≈ √N │ └──────────┬──────────┘ ↓ ┌─────────────────────┐ │ gmpy2.isqrt(N) │ │ 得到 √N 的近似值 │ └──────────┬──────────┘ ↓ ┌─────────────────────┐ │ 从 √N 向下搜索 │ │ 找到第一个整除 N 的数│ └──────────┬──────────┘ ↓ ┌─────────────────────┐ │ 成功分解 N │ │ p ...127 │ │ q ...153 │ └──────────┬──────────┘ ↓ ┌─────────────────────┐ │ 标准 RSA 解密流程 │ │ φ (p-1)(q-1) │ │ d e⁻¹ mod φ │ │ m C^d mod N │ └──────────┬──────────┘ ↓ ┌─────────────────────┐ │ Flag: │ │ shellmates{...} │ └─────────────────────┘总结本题是一道经典的 RSA 相邻素数攻击题目核心在于识别特征通过源码发现q next_prime(p)这一关键信息数学利用利用 p ≈ q ≈ √N 的特性快速分解大数工具使用熟练使用gmpy2库进行大数运算这种攻击方式在现实中也有实际意义提醒我们在使用 RSA 时必须确保 p 和 q 是独立随机生成的避免选择过于接近的素数。原始提问请阅读目录下的文件解出这道 CTF 题目。