盒子
盒子
文章目录
  1. 算法原理简介
    1. 加密
    2. 解密
  2. 相关工具
  3. CTF示例
    1. 安恒CTF
    2. SCTF
      1. level0
      2. level1
      3. level2
      4. level5
      5. level3
      6. level4
  4. 总结

CTF中的RSA算法

密码算法有很多种,要讲就要讲久了,自行脑补一本厚厚的密码学书。

我们经常用到的算法包括对称加密算法和非对称加密算法。本文主要介绍CTF中经常遇到的RSA加密题的一些解法

算法原理简介

  • 随机选择大素数p,q,并计算:
1
n = p*q

\phi(n) = (p-1)(q-1)
  • 选择一个随机数e,1 < e < ϕ(n),且 gcd(e, ϕ(n)) = 1,并计算:

    1
    
    d = e^{-1}mod(\phi(n))
  • 选择(e,n)为公钥,d为私钥

加密

对明文m < n,其对应的密文为:

1
c=m^e mod n

解密

对于密文c,对应的明文为:

1
m = c^d mod n

相关工具

首先介绍下我自己改写的一个工具>>rsatools<<, 该项目主要代码源于RsaCtfTool,我只是对其进行了改写。参加了几次CTF之后,只是想让这个工具能够适用于更多的情况。

  • RSA大数分解网站 http://www.factordb.com/index.php
  • 大数分解平台 https://cloud.sagemath.com/

    1
    2
    factor(0x123)
    factor(123)
  • RSA-Tool 2

  • yafu 如果两个素数相差很近,可采用费马分解

    1
    2
    factor(0x123)
    factor(123)
  • rsatool.py 标准工具 用于已有p,q生成私钥

    1
    ./rsatool.py -p num1 -q num2 -o priv.key
  • openssl

    1
    2
    3
    4
    输出公钥信息
    openssl rsa -noout -text -inform PEM -in public.key -pubin

    openssl rsautl -decrypt -in level1bin.passwd.enc -inkey ../priv.key -out level1.passwd -oaep

CTF示例

安恒CTF

给出的文件>>在这里<<),这里就比较直白能看出是RSA加密,然后分解大数直接暴力跑就行了,当时也是专门搞了个脚本处理这种加密。>>代码戳这里<<,直接看代码就能明白了

SCTF

SCTF的RSA加解密难度较大,我也是在其中学到很多技巧。

level0

第一个压缩包中包含密文,以及公钥证书.我们需要从公钥证书中找到大数N,然后去分解大素数
采用我自己改写的脚本可直接输出公钥中的N和E:

1
python RsaCtfTool.py --pkey ../sctf/rsa1/level0/public.key

N = 18762288330807505336471569952368628968038915032364773203018829070696227411217877868952724842039756288121734420378039301563905037169196320417706839549744629044465352679919380329435329653365900312498712121432190200717072138327379844913608851715404086200984072727408758802012147296753317519612628629535373054730645471938738605688629618951071483635716677866010394704066696480858977560809007683074249820225609075518509112704549293147063971302640066331096645041521401155565628466857211261242132897152403975836705170916276159246187173035660820037820087171748591660487636434105623595720788169970861783452500198572918584010881
e = 65537
直接在sagemath中跑:

1
2
3
factor(18762288330807505336471569952368628968038915032364773203018829070696227411217877868952724842039756288121734420378039301563905037169196320417706839549744629044465352679919380329435329653365900312498712121432190200717072138327379844913608851715404086200984072727408758802012147296753317519612628629535373054730645471938738605688629618951071483635716677866010394704066696480858977560809007683074249820225609075518509112704549293147063971302640066331096645041521401155565628466857211261242132897152403975836705170916276159246187173035660820037820087171748591660487636434105623595720788169970861783452500198572918584010881)
#output
250527704258269 * 74891071972884336452892671945839935839027130680745292701175368094445819328761543101567760612778187287503041052186054409602799660254304070752542327616415127619185118484301676127655806327719998855075907042722072624352495417865982621374198943186383488123852345021090112675763096388320624127451586578874243946255833495297552979177208715296225146999614483257176865867572412311362252398105201644557511678179053171328641678681062496129308882700731534684329411768904920421185529144505494827908706070460177001921614692189821267467546120600239688527687872217881231173729468019623441005792563703237475678063375349

这个实测RSA-Tool 2 中还要快一些,然后还是用脚本解密

1
python RsaCtfTool.py --pqne 250527704258269,74891071972884336452892671945839935839027130680745292701175368094445819328761543101567760612778187287503041052186054409602799660254304070752542327616415127619185118484301676127655806327719998855075907042722072624352495417865982621374198943186383488123852345021090112675763096388320624127451586578874243946255833495297552979177208715296225146999614483257176865867572412311362252398105201644557511678179053171328641678681062496129308882700731534684329411768904920421185529144505494827908706070460177001921614692189821267467546120600239688527687872217881231173729468019623441005792563703237475678063375349,18762288330807505336471569952368628968038915032364773203018829070696227411217877868952724842039756288121734420378039301563905037169196320417706839549744629044465352679919380329435329653365900312498712121432190200717072138327379844913608851715404086200984072727408758802012147296753317519612628629535373054730645471938738605688629618951071483635716677866010394704066696480858977560809007683074249820225609075518509112704549293147063971302640066331096645041521401155565628466857211261242132897152403975836705170916276159246187173035660820037820087171748591660487636434105623595720788169970861783452500198572918584010881,65537 --crypto ../sctf/rsa1/level0/level1.passwd.enc --format base64

解出来时乱码,我们就要考虑填充的问题,我写的脚本还没支持不同的填充,尝试用openssl解密,成功解密

1
2
cat ../sctf/rsa1/level0/level1.passwd.enc | base64 -d > ../sctf/rsa1/level0/level1bin.passwd.enc
openssl rsautl -decrypt -in ../sctf/rsa1/level0/level1bin.passwd.enc -inkey ../sctf/rsa1/priv.key -out ../sctf/rsa1/level0/level1.passwd -oaep

level1

这一层还是查看N&e,N&e,然后分解大数,sage很久都没分出来,RSA-Tool 2也是,最终发现是P和Q相近,可采用费马分解。我们可以采用yafu这个工具进行分解。

1
2
3
4
5
factor(24635380199162576175626733825654993088774186468424341251485528171539392839329146412615013362980283492199482296250229443925899183941601282092332843476617277156184507685928193519623765855782976047363883665283424473545877969718710272046261654326391840252190462805782777380937446430987284386172226304759726517529843564412091984328980979115111158624673855166379221415935217206920980564900414671064827167187417932475583509599802648238573603298428445177957392893928492353538844661418085667022331283805225000341955464473332333141637604132197773189903937879276873131228814365139541968760521539920817629563995110317306270531197)

# output
P309 = 156956618844706820397012891168512561016172926274406409351605204875848894134762425857160007206769208250966468865321072899370821460169563046304363342283383730448855887559714662438206600780443071125634394511976108979417302078289773847706397371335621757603520669919857006339473738564640521800108990424511408496383
P309 = 156956618844706820397012891168512561016172926274406409351605204875848894134762425857160007206769208250966468865321072899370821460169563046304363342283383730448855887559714662438206600780443071125634394511976108979417302078289773847706397371335621757603520669919857006339473738564640521800108990424511408496259

然后同level0的方式进入level2

1
2
python RsaCtfTool.py --pqne 156956618844706820397012891168512561016172926274406409351605204875848894134762425857160007206769208250966468865321072899370821460169563046304363342283383730448855887559714662438206600780443071125634394511976108979417302078289773847706397371335621757603520669919857006339473738564640521800108990424511408496383,156956618844706820397012891168512561016172926274406409351605204875848894134762425857160007206769208250966468865321072899370821460169563046304363342283383730448855887559714662438206600780443071125634394511976108979417302078289773847706397371335621757603520669919857006339473738564640521800108990424511408496259,24635380199162576175626733825654993088774186468424341251485528171539392839329146412615013362980283492199482296250229443925899183941601282092332843476617277156184507685928193519623765855782976047363883665283424473545877969718710272046261654326391840252190462805782777380937446430987284386172226304759726517529843564412091984328980979115111158624673855166379221415935217206920980564900414671064827167187417932475583509599802648238573603298428445177957392893928492353538844661418085667022331283805225000341955464473332333141637604132197773189903937879276873131228814365139541968760521539920817629563995110317306270531197,65537 --pri
openssl rsautl -decrypt -in ../sctf/rsa1/level0/level1/level2.passwd.enc -inkey ../sctf/rsa1/level0/level1/pri.key -out ../sctf/rsa1/level0/level1/level2.passwd

level2

这一题用同样的方法可以看到E很大,存在低解密指数攻击(Wiener’s Attack),e太大,可直接算出d

1
2
"n" is:310417953704722170730847224402877983815425243802949146921747155554873214220856824312098961643471840575991636613043700912852694476430642621109657293199766030858364981594359341335457943511388291654144608627164424697545853589150385759857708455254761227678476750080293606809444462895661894497915336651794981901683
"e" is:180160219817657029643391514538629205160228298622505654076129556003630962924040643558658232436259668646427759588151297967578950689360985724312726411880635697242206899247553123368979139238838216404056134080086977722515560207477455248034027633490880147280702252198966243510960816978036425871522668587833586334027

1
2
python RsaCtfTool.py --pkey ../sctf/rsa1/level0/level1/level2/public.key --pri
openssl rsautl -decrypt -in ../sctf/rsa1/level0/level1/level2/level3.passwd.enc -inkey ../sctf/rsa1/level0/level1/level2/pri.key -out ../sctf/rsa1/level0/level1/level2/level3.passwd

至此rsa第一题通关

level5

这个也是RSA第二题,下面的题都是针对RSA特定情形下的攻击,该题考察共享素数攻击,两个模共享一个素因子,可以用gcd快速算出模的共享素因子。题目给了一个流量包syc_security_system_traffic2.pcap,分析流量包,可以看到10个明文TCP会话,会话中包含加密的公钥(n,e)和加密后的level5的密码。其中e都是65537。所以随机选取两个n,这里我们选取第4个和第5个会话,写个sage脚本得到p和q。事实上你会发现这里所有的n都不是互素的。
>>sage脚本<<

level3

这题可以使用相关消息攻击(Franklin-Reiter related-message attack),也可以采用Hastad attack。最后看writeup,有好多种解法。通信过程中有一组还使用了同一个公钥,解法非常多。
最后,我用改写的脚本直接解密,解密脚本

level4

这题考察广播攻击(Hastad’s Broadcast Attack),e较小,用相同的e和不同的n加密线性相关的消息,可以用多个密文m和模n算出明文。我也是找到了类似的题,改了改别人的脚本解出该题>>code<<。详细分析可以看这里

总结

本文是在做了几个CTF题之后总结了下RSA相关题的解法,希望能对大家有所帮助,这类题还是比较简单,一般问题现在网上都能搜到答案。我想去做一个通用的工具,但是偶尔又感觉没什么意义,一直未果。