BCTF 超級加解密 Writeup

about 9 years ago

BCTF 超級加解密 Writeup

由於提示 1. ，把圖檔直接用純文字編輯器打開後，會發現在圖檔的最後就有明文data了。
複製下明文 data 後，我們有的是 p[3] 的最後幾位，c, d, n 的開頭 70X 位。

連上服務器後:

$ nc 218.2.197.242 1481
Welcome to our Full-Feature Technical Advanced Next Generation Multiprime RSA Encryption Decryption System!!!
Send E to encrypt, D to decrypt:

我們可以加密或解密。

加密：

Send E to encrypt, D to decrypt: E
m: 3
p[0] (just enter to choose from internal precalculated primes, -1 to end): 11
p[1] (just enter to choose from internal precalculated primes, -1 to end): 13
p[2] (just enter to choose from internal precalculated primes, -1 to end): 17
p[3] (just enter to choose from internal precalculated primes, -1 to end): 19
p[4] (just enter to choose from internal precalculated primes, -1 to end): 23
c: 734743
d: 694561
n: 1062347
Keep them safe! You will need them when you want to decrypt!

要給 m 以及五個質數 p[0], ..., p[4] ，然後他會回 c, d, n，並且 p[0], ..., p[4] 都可以選擇用它內建的質數。

解密：
```
Send E to encrypt, D to decrypt: D
c: 734743
d: 694561
n: 1062347
m: 129424
```
給 c, d, n，會回 m。稍微做嘗試可以發現 m = c ^ d (mod n)，正常的 RSA 解密方法。
稍微做些嘗試就會發現加密時 n = p[0] * p[1] * p[2] * p[3] * p[4]，且 e = d ^ -1 (mod phi(n)) 固定為 65537。

在給定的圖片中可以看出，他的 p[4] 是用內建的質數，所以第一個想法就是把這個質數給弄出來：

$ nc 218.2.197.242 1481
Welcome to our Full-Feature Technical Advanced Next Generation Multiprime RSA Encryption Decryption System!!!
Send E to encrypt, D to decrypt: E
m: 2
p[0] (just enter to choose from internal precalculated primes, -1 to end): 2
p[1] (just enter to choose from internal precalculated primes, -1 to end): 2
p[2] (just enter to choose from internal precalculated primes, -1 to end): 2
p[3] (just enter to choose from internal precalculated primes, -1 to end): 2
p[4] (just enter to choose from internal precalculated primes, -1 to end):
For safety reasons, at least 2 internal primes should be used.

居然至少要用兩個，沒關係，反正我們可以 gcd !!

$ nc 218.2.197.242 1481
Welcome to ...
Send E to encrypt, D to decrypt: E
m: 2
p[0] (just enter to choose from internal precalculated primes, -1 to end): 2
p[1] (just enter to choose from internal precalculated primes, -1 to end): 2
p[2] (just enter to choose from internal precalculated primes, -1 to end): 2
p[3] (just enter to choose from internal precalculated primes, -1 to end):
p[4] (just enter to choose from internal precalculated primes, -1 to end):
c: ...
d: ...
n: 152028909836222113959550146912734866848449992318569105798843765272643341950784059000812186573943477804026802605391246296729074193639786301538402337715819765397152098376548993239554000665217434392619244660420346797308471846003587415187504969472684287180831671452465342171753461082955443582940450809950532470906250674428419619255510160205299765589939000119405025082703958840258130283810843215057396601779564895683712534815949888086746146162919092719413288599655789022419799459399913942341189733873481545992288737838058870494834078454569381106222136104602926008066452038339812275054761841285928381879124223071638421904968
Keep them safe! You will need them when you want to decrypt!

$ nc 218.2.197.242 1481
Welcome to our Full-Feature Technical Advanced Next Generation Multiprime RSA Encryption Decryption System!!!
Send E to encrypt, D to decrypt: E
m: 2
p[0] (just enter to choose from internal precalculated primes, -1 to end): 2
p[1] (just enter to choose from internal precalculated primes, -1 to end): 2
p[2] (just enter to choose from internal precalculated primes, -1 to end):
p[3] (just enter to choose from internal precalculated primes, -1 to end): 2
p[4] (just enter to choose from internal precalculated primes, -1 to end):
c: ...
d: ...
n: 96015843946481686637114879276136845542044840790228140836663797227956932315675298864768177012643744432815920295222500857099596562630689542751573862328307675834243494110003769405008679987173422483588355200145422756352899280458539046260320020691969536675487117983627473748729422240538726362326148027934256368878228293830054287047691840429105980727256433828341801382779958698707797917999366380062371801926202280101690184155406357163981255860082059934067517711341093470089080937896315812544849677996805473953859731441138876891316303909285260267696673346402064316692108106784754162637970421382667527075181609672937034315016
Keep them safe! You will need them when you want to decrypt!

$ irb --simple-prompt --noecho
>> p 152028909836222113959550146912734866848449992318569105798843765272643341950784059000812186573943477804026802605391246296729074193639786301538402337715819765397152098376548993239554000665217434392619244660420346797308471846003587415187504969472684287180831671452465342171753461082955443582940450809950532470906250674428419619255510160205299765589939000119405025082703958840258130283810843215057396601779564895683712534815949888086746146162919092719413288599655789022419799459399913942341189733873481545992288737838058870494834078454569381106222136104602926008066452038339812275054761841285928381879124223071638421904968.gcd(96015843946481686637114879276136845542044840790228140836663797227956932315675298864768177012643744432815920295222500857099596562630689542751573862328307675834243494110003769405008679987173422483588355200145422756352899280458539046260320020691969536675487117983627473748729422240538726362326148027934256368878228293830054287047691840429105980727256433828341801382779958698707797917999366380062371801926202280101690184155406357163981255860082059934067517711341093470089080937896315812544849677996805473953859731441138876891316303909285260267696673346402064316692108106784754162637970421382667527075181609672937034315016)
8

居然沒有 gcd ?!?!
(備註：其實當初運氣很好，在這邊有找到 gcd 所以一下子就確信的接下來的步驟。)

猜測應該是 internal precalculated primes 不只一個，反正也沒很大問題，多跑幾次取個 gcd 就好了嘛。
寫個 code:

require 'socket'
require 'set'
def send(msg)
  if !msg.end_with?("\n")
    msg << "\n"
  end
  $sock.puts msg
end
def f(msk)
  $sock = TCPSocket.new('218.2.197.242', 1481)
  $sock.readpartial(1000)
  send("E")
  $sock.readpartial(1000)
  send("2")
  a = 1
  (0..4).each do |i|
    $sock.readpartial(1000)
    if (msk & (1<<i)) != 0

      send("")
    else
      send("2")
      a *= 2
    end
  end
  2.times { $sock.gets }
  res = $sock.gets
  res.split.last.to_i / a
end
arr = []
prs = Set.new
100.times do |i|
  puts "i = #{i+1}"
  x = f(3)
  arr.each do |y|
    d = x.gcd(y)
    if x != y && d != 1
      if !prs.include?(d)
        prs << d
        puts "NEW!! #{prs.size} #{d}"
      end
      if !prs.include?(x/d)
        prs << x/d
        puts "NEW!! #{prs.size} #{x/d}"
      end
      if !prs.include?(y/d)
        prs << y/d
        puts "NEW!! #{prs.size} #{y/d}"
      end
    end
  end
  arr << x
end
File.open('primes.out', 'a') do |f|
  prs.each do |x|
    puts x
    f.puts x
  end
end

好呀，跑起來後大概 i = 40 左右就再也沒有找到新質數了，而且恰好找到了 20 個，感覺很好。
那我們要怎麼找出他用的 p[4] 是哪個呢?
反正我們知道 c, d, e 呀，而且 d * e = 1 (mod phi(n))，所以 d * e - 1 = 0 (mod p[4] - 1)。
再來寫點 code:

d = 104466343164729087857924433717120123026730345025496572931042729663280318332180201519089750547537033938031455617897881516094517777275472471958201971537515433606466378472927835746478394277274335131412557789270799764329039705481501785483498339440868338393442585095851195962652200500234673782591233520625438685029015759533598925357134261417036905888463009235413899315272889559176852036275265397811056374955100854876181160191819592386343114118564802721722543826454950667590196976027734654747903097930961234629331591248890805354981062509339001243417076985330052677577268459337389198642060462627790212276935817184089469412790871781453230934753628441673082327589657983062385021517502178692305602169426049605523210692307358226555979513497019015184500519142840969643972048560555580697162010947981169710611611950052624614665237552299775033261536729851959011165573920081722650964743920271258212239618325731253753648870324309322610138826118085856098561213518495328041115201952343510507600284151247753941884151840764304445433386559797702557090624854317046308814938880338048441331510647996933282819505770330293877324603923862108533946770000826346932912111766264413161263776344962785353355939178512371452254092861476682898741006579721786355221169465262747469206955933405183390054212205397384324334630503270038538801146133206134529293517467045269375439710074643957703552931399250244401960912957519498749770331566978742243561343913351811029603543887955317334570806642551975172888500131577049245452199491882818902853651477792230381277739300528906828493317634145
e = 65537

File.open('primes.out', 'r').each_line do |l|
  p = l.to_i
  if (d * e - 1) % (p - 1) == 0
    puts p
  end
end

好耶，找到剛好一組解

p[4] = 168989495350198471757304910164246620278618748133367672139165446394971542282791758834807455422116663508781271240060726532459335466894873529369737149899793694978740710751697223761546222188135151720364836557540052832994486319340900010305994941187266419756973586597235759828992800739396838968274798301109676918099

那剩下還可以做什麼呢? 我們發現所有的內建質數都是 1024 bits 的，所以我們的 n 會有 5000 bits 左右，根本沒辦法分解。
只好來看看知道的東西，我們會算 m mod p[4] = (c ^ d) mod p[4]，不如就來算一下

$ irb --simple-prompt --noecho
>> require 'openssl'
>> c = 71645492621016673213464976773705576598977626188054643472370723424005857135162855393495525466474057651388978394889444949437380622155523348698509489004391235019565559713627704048764179825993770410982081163073179082285952371172055471437005696074211474392152995661697527350764986910630825290938713981052953920875056274443078166660161379007899771674818002376511810428126919459728556444907124724248902780437229599609692990060701334533869156239657433452398941687755149030225719626892256525828870439455342555038998548248930571438085811465324762391516078453666561369010072939796424295777910058168525395200497857742499478507305733793176124897603297195542885744052977605697204533460276361782701335960840419409638485275251200148529855104784943375845079462500946103046167381952863473525712385535457260742220493988472038884591586844210153095905539944176519845001888595529988070630591235276520727111922413882666126523273528142846421483047055572860010802821615126164839286994359724423504094657097576680526355991297870002520097946404866876092819438073099964246959985831951741988584061391662020367882716315675046351265596111348879131403112265886951818911512290815325914332803777263106292553807010792838432697001671952904056736058809040140495768716191710729870260566039901981373982507868220670494614453505465224168491429856270213842707867705951119825424174283567151574373848855252876003957712007790956767752239650449011091020177913065971208007298633065520219790822524305072574433056282209795778043445899379702686258716714912791202892749944700857668722626288022
>> d = 104466343164729087857924433717120123026730345025496572931042729663280318332180201519089750547537033938031455617897881516094517777275472471958201971537515433606466378472927835746478394277274335131412557789270799764329039705481501785483498339440868338393442585095851195962652200500234673782591233520625438685029015759533598925357134261417036905888463009235413899315272889559176852036275265397811056374955100854876181160191819592386343114118564802721722543826454950667590196976027734654747903097930961234629331591248890805354981062509339001243417076985330052677577268459337389198642060462627790212276935817184089469412790871781453230934753628441673082327589657983062385021517502178692305602169426049605523210692307358226555979513497019015184500519142840969643972048560555580697162010947981169710611611950052624614665237552299775033261536729851959011165573920081722650964743920271258212239618325731253753648870324309322610138826118085856098561213518495328041115201952343510507600284151247753941884151840764304445433386559797702557090624854317046308814938880338048441331510647996933282819505770330293877324603923862108533946770000826346932912111766264413161263776344962785353355939178512371452254092861476682898741006579721786355221169465262747469206955933405183390054212205397384324334630503270038538801146133206134529293517467045269375439710074643957703552931399250244401960912957519498749770331566978742243561343913351811029603543887955317334570806642551975172888500131577049245452199491882818902853651477792230381277739300528906828493317634145
>> p4 = 168989495350198471757304910164246620278618748133367672139165446394971542282791758834807455422116663508781271240060726532459335466894873529369737149899793694978740710751697223761546222188135151720364836557540052832994486319340900010305994941187266419756973586597235759828992800739396838968274798301109676918099
>> n = c.to_bn.mod_exp(d, p4).to_i
>> p n
17268729816559353401470580827638778064723414957310217193471794972008753629563164273078961514354631330982290718517874393106220502014411962811717696713597
>> p n.to_s(2).length
503

這個有詐呀! 超短的說，只好來看看它到底是什麼。

>> n.to_s(16).split('').each_slice(2).map do |x| print x.join.to_i(16).chr end
The flag is BCTF{c4n-y0u-6re4k-RSA-us1n9-4c0ust1c-crypt4n41s1s}

耶!!!

備註: 其實最後一步不用這麼複雜:

>> p [n.to_s(16)].pack("H*")
"The flag is BCTF{c4n-y0u-6re4k-RSA-us1n9-4c0ust1c-crypt4n41s1s}"
>> p n.to_bn.to_s(2)
"The flag is BCTF{c4n-y0u-6re4k-RSA-us1n9-4c0ust1c-crypt4n41s1s}"

March 12, 2014 08:11
Permalink