zer0pts CTF 2020 writeup

The English version is here:
- https://hackmd.io/@hakatashi/BkG7zhfSU

Overview

2020-03-07 00:00 - 2020-03-09 00:00 に48時間開催された zer0pts CTF 2020 にチームTSGのメンバーとして参加しました。結果は8847ptsで12位です。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

凄まじい実力で近年頭角を現しつつあるチームzer0ptsによる初めてのCTFです。事前の宣言通り、「No boring guess」な最高のクオリティのCTFでした。ありがとうございます!

ROR (Crypto, 260pts)

平文
$m$ を右に
$i (0 \leq i < l e n (m))$ bit回転シフトした値をRSAで暗号化した値が与えられる
$N = 2^{n_{1}} 3^{n_{2}} 7^{n_{3}}, e$ は不明

Solution

$N$ は偶数なので、奇数を暗号化すると奇数に、偶数を暗号化すると偶数になる。

zer0pts{0h_1t_l34ks_th3_l34st_s1gn1f1c4nt_b1t}


    
      
        
  
    
    

        


  


  
        
          
          ans = File.read('chall.txt').lines.map do |line|
        
        
          
            (line.to_i % 2).to_s
        
        
          
          end.to_a.join.reverse.to_i(2).to_s(16)
        
        
          
          puts [ans].pack("H*")
        
  



    

  


      
      
        view raw
        
          solve.rb
        
        hosted with ❤ by GitHub

nibelung (Crypto, 525pts)

$F_{p}$ (
$p$ : 512bit) 上の6次一般線形群
$G L_{6} (F_{p})$ 上の演算で暗号化、復号化が定義される
- $p$ は接続のたびにランダムな素数に設定される
$U$ を秘密鍵として
$U \cdot X \cdot U^{- 1}$ で暗号化、
$U^{- 1} \cdot X \cdot U$ で復号化
行列のすべての要素が256以下であるような任意の値
$X$ に対して暗号化・復号化を行うことができる
暗号化されたフラグが与えられる

Solution

一般線形群は名前のとおり線形なので、36個ある各要素について単位ベクトルを暗号化して取得すれば線形合同方程式に帰着して解ける

zer0pts{r1ng_h0m0m0rph1sm_1s_c00l}


    
      
        
  
    
    

        


  


  
        
          
          from socket import socket
        
        
          
          import os
        
        
          
          import re
        
        
          
          import json
        
        
          
          import base64
        
        
          
          

        
        
          
          conn = socket()
        
        
          
          conn.connect(('13.231.224.102', 3002))
        
        
          
          

        
        
          
          str = ''
        
        
          
          while '>' not in str:
        
        
          
            str += conn.recv(1024).decode('UTF-8')
        
        
          
          print(str)
        
        
          
          

        
        
          
          lines = str.split('\n')
        
        
          
          X = []
        
        
          
          for line in lines[1:7]:
        
        
          
            X.extend(list(map(int, re.findall(r'\d+', line))))
        
        
          
          p = int(re.search(r'\d+', lines[7]).group(0))
        
        
          
          

        
        
          
          print(X, p)
        
        
          
          

        
        
          
          Ps = []
        
        
          
          

        
        
          
          for i in range(36):
        
        
          
            data = b'1\n'
        
        
          
            conn.send(data)
        
        
          
            print('<== {}'.format(data))
        
        
          
          

        
        
          
            b = bytes(map(lambda j: 1 if j == i else 0, range(36)))
        
        
          
            data = base64.b64encode(b) + b'\n'
        
        
          
            conn.send(data)
        
        
          
            print('<== {}'.format(data))
        
        
          
          

        
        
          
            str = ''
        
        
          
            while '>' not in str:
        
        
          
              str += conn.recv(1024).decode('UTF-8')
        
        
          
            print(str)
        
        
          
          

        
        
          
            lines = str.split('\n')
        
        
          
            P = []
        
        
          
            for line in lines[1:7]:
        
        
          
              P.extend(list(map(int, re.findall(r'\d+', line))))
        
        
          
            Ps.append(P)
        
        
          
          

        
        
          
          print('Solving...')
        
        
          
          R = IntegerModRing(p)
        
        
          
          M = Matrix(R, Ps)
        
        
          
          target = vector(R, X)
        
        
          
          result = M.T.solve_right(target)
        
        
          
          print(''.join(list(map(chr, result))))
        
  



    

  


      
      
        view raw
        
          solve.sage
        
        hosted with ❤ by GitHub

diysig (Crypto, 394pts)

RSAと、謎のハッシュ関数が実装されている
任意のデータを暗号化したデータとそのハッシュ値を得ることができる
任意のデータの復号後のデータのハッシュ値を得ることができる
$N, e$ は既知、
$N$ : 1024bit、
$e = 65537$
ハッシュ関数は以下の通り

    def _hash(self, m):
        """ DIY Hash Function """
        H = 0xcafebabe
        M = m
        # Stage 1
        while M > 0:
            H = (((H << 5) + H) + (M & 0xFFFFFFFF)) & 0xFFFFFFFF
            M >>= 32
        # Stage 2
        M = H
        while M > 0:
            H = ((M & 0xFF) + (H << 6) + (H << 16) - H) & 0xFFFFFFFF
            M >>= 8
        # Stage 3
        H = H | 1 if m & 1 else H & 0xfffffffe
        return H

Solution

ハッシュ関数はなんかいろいろやってるが、一番やばいのは Stage 3 でハッシュ値のLSBを潰して
$m$ のLSBで塗りつぶしていること
署名の出力と合わせると任意のデータの復号後のデータの LSB 1bit が分かる
→LSB Decryption Oracle Attack が適用可能

zer0pts{n3v3r_r3v34l_7h3_LSB}


    
      
        
  
    
    

        


  


  
        
          
          import re
        
        
          
          from socket import socket
        
        
          
          from fractions import Fraction
        
        
          
          

        
        
          
          def decrypt_lsb(c):
        
        
          
              conn = socket()
        
        
          
              conn.connect(('13.231.224.102', 3001))
        
        
          
          

        
        
          
              str = ''
        
        
          
              while '>' not in str:
        
        
          
                  str += conn.recv(1024).decode('UTF-8')
        
        
          
              print(str)
        
        
          
          

        
        
          
              data = b'2\n'
        
        
          
              print('<== {}'.format(data))
        
        
          
              conn.send(data)
        
        
          
              data = hex(c)[2:].encode('ascii') + b'\n'
        
        
          
              print('<== {}'.format(data))
        
        
          
              conn.send(data)
        
        
          
              data = b'00000000\n'
        
        
          
              print('<== {}'.format(data))
        
        
          
              conn.send(data)
        
        
          
          

        
        
          
              str = ''
        
        
          
              while 'Signature' not in str:
        
        
          
                  str += conn.recv(1024).decode('UTF-8')
        
        
          
              print(str)
        
        
          
          

        
        
          
              signature = re.search(r'!= (\w{8})', str).group(1)
        
        
          
              print('Signature: {}'.format(signature))
        
        
          
          

        
        
          
              conn.close()
        
        
          
          

        
        
          
              return int(signature, 16) % 2
        
        
          
          

        
        
          
          # http://inaz2.hatenablog.com/entry/2016/11/09/220529
        
        
          
          def lsb_decryption_oracle(c):
        
        
          
              bounds = [0, Fraction(n)]
        
        
          
          

        
        
          
              i = 0
        
        
          
              while True:
        
        
          
                  print('i: {}'.format(i))
        
        
          
                  i += 1
        
        
          
          

        
        
          
                  c2 = (c * pow(2, e, n)) % n
        
        
          
                  lsb = decrypt_lsb(c2)
        
        
          
                  if lsb == 1:
        
        
          
                      bounds[0] = sum(bounds) // 2
        
        
          
                  else:
        
        
          
                      bounds[1] = sum(bounds) // 2
        
        
          
                  diff = bounds[1] - bounds[0]
        
        
          
                  diff = diff.numerator // diff.denominator
        
        
          
                  print(diff)
        
        
          
                  print('m: {}'.format(hex(bounds[1].numerator // bounds[1].denominator)))
        
        
          
                  if diff == 0:
        
        
          
                      m = bounds[1].numerator // bounds[1].denominator
        
        
          
                      return m
        
        
          
                  c = c2
        
        
          
          

        
        
          
          n = 0x6d70b5a586fcc4135f0c590e470c8d6758ce47ce88263ff4d4cf49163457c71e944e9da2b20c2ccb0936360f12c07df7e7e80cd1f38f2c449aad8adaa5c6e3d51f15878f456ceee4f61547302960d9d6a5bdfad136ed0eb7691358d36ae93aeb300c260e512faefe5cc0f41c546b959082b4714f05339621b225608da849c30f
        
        
          
          e = 0x10001
        
        
          
          c = 0x3cfa0e6ea76e899f86f9a8b50fd6e76731ca5528d59f074491ef7a6271513b2f202f4777f48a349944746e97b9e8a4521a52c86ef20e9ea354c0261ed7d73fc4ce5002c45e7b0481bb8cbe6ce1f9ef8228351dd7daa13ccc1e3febd11e8df1a99303fd2a2f789772f64cbdb847d6544393e53eee20f3076d6cdb484094ceb5c1
        
        
          
          

        
        
          
          print(lsb_decryption_oracle(c))
        
  



    

  


      
      
        view raw
        
          solve.py
        
        hosted with ❤ by GitHub

サーバーに1024回TCPコネクションを張ったのでBANされないか心配でした (まあ)。

dirty laundary (Crypto, 636pts)

シャミアの秘密分散法とPaillier暗号の複合システム
$F_{p}$ 上の2次多項式をランダムに生成し
$x = 1 \sim 5$ に対応する
$y$ の値を生成する。shareは5つ全て与えられているので本来であれば直ちに復号できるはずだが
$y$ の値にノイズが加えられた上Paillier暗号により暗号化されているため復号できない。
演算中に導入される以下の係数はランダムに生成される。
- 秘密分散を生成する多項式の係数
  $a, b, c$ および法
  $p$ (1024bit, cはフラグ)
  
  $f (x) = a x^{2} + b x + c mod p$
- 秘密分散の値に加えられるノイズ
  $e_{i}$ (256bit)
  
  $y_{i} = f (x_{i}) + e_{i} (x_{i} = 1, 2, 3, 4, 5)$
- Paillier暗号の法
  $N_{i}$ の素因数
  $p_{i}, q_{i}$ (1024bit, 512bit)
  
  $N_{i} = p_{i} q_{i} (p_{i} \approx p + e_{i})$
- Paillier暗号の暗号化係数
  $k_{i}$ (256bit)
  
  $g_{i} = 1 + k_{i} N_{i} mod N_{i}^{2}$
- Paillier暗号の乱数
  $r_{i}$ (256bit)
  
  $c_{i} = g_{i}^{y_{i}} r_{i}^{N_{i}} mod N_{i}^{2}$
このうち
$N_{i}, g_{i}, c_{i}$ が与えられる

Solution

よく見ると

p_{i} \approx p + e_{i}

であるところの

p

: 1024bit に対して

e_{i}

: 256bit とめちゃくちゃ小さい。すなわち5つの

N_{i}

の素因数

p_{i}

は上位75%が共通している。格子の匂いがする。

あいにくこのような場合に使える手法は記憶になかったが、がんばって検索するとこの論文がヒットした (2010年の論文らしい。クール)

論文によれば、

q

のサイズが

α

ビットで、

p

の上位

t

ビットが共通しているRSA公開鍵が

k

個与えられたとき、

t ≧ \frac{k}{k - 1} α

を満たす場合格子を用いて解読可能である。今回の問題では

t = 768, α = 512, k = 5

なので、きれいに条件を満たす。

論文を参考に、以下のような行ベクトルで構成される格子を考える。

L = [\begin{array}{ccccccccccccccc} K & 0 & 0 & 0 & 0 & N_{2} & N_{3} & N_{4} & N_{5} & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & K & 0 & 0 & 0 & - N_{1} & 0 & 0 & 0 & N_{3} & N_{4} & N_{5} & 0 & 0 & 0 \\ 0 & 0 & K & 0 & 0 & 0 & - N_{1} & 0 & 0 & - N_{2} & 0 & 0 & N_{4} & N_{5} & 0 \\ 0 & 0 & 0 & K & 0 & 0 & 0 & - N_{1} & 0 & 0 & - N_{2} & 0 & - N_{3} & 0 & N_{5} \\ 0 & 0 & 0 & 0 & K & 0 & 0 & 0 & - N_{1} & 0 & 0 & - N_{2} & 0 & - N_{3} & - N_{4} \end{array}]

ただし

n

を

N

のサイズとして

K = 2^{n - t}

である。このとき最短ベクトルにおける基底の係数が

q_{1}, \dots, q_{5}

となり、素因数分解可能となる。これはLLLを適用してSVPを解き、最短ベクトルの最初の5つの要素を見れば計算可能である。

これにより

N_{i}

の素因数を得た。ここからPaillier暗号が復号可能 (

k_{i}

は

g_{i} = 1 + k_{i} N_{i}

より直ちに得られる) なので、

y_{i}

を得られる。

p_{i} = p + e_{i} + δ_{i} (δ_{i} < approx 1000)

とおき、

f (x)

周辺の式を整理すると

\begin{aligned} f (1) - δ_{1} & = y_{1} - p_{1} mod p \\ f (2) - δ_{2} & = y_{2} - p_{2} mod p \\ f (3) - δ_{3} & = y_{3} - p_{3} mod p \\ f (4) - δ_{4} & = y_{4} - p_{4} mod p \\ f (5) - δ_{5} & = y_{5} - p_{5} mod p \end{aligned}

となる。

ところで

\begin{aligned} f (1) - 3 f (2) + 3 f (3) - f (4) = & (a + b + c) - 3 (4 a + 2 b + c) \\ + 3 (9 a + 3 b + c) - (16 a + 4 b + c) \\ = & 0 \end{aligned}

なので、

d_{i} := y_{i} - p_{i}

とおくと、

d_{1} - 3 d_{2} + 3 d_{3} - d_{4} = k p - δ_{1} + 3 δ_{2} - 3 δ_{3} + δ_{4} (k \in Z)

となり

p

の小さい倍数の良い近似値が得られる。なお実際には

k = 1

であった。

また、

\begin{aligned} 3 f (1) - 3 f (2) + f (3) = & 3 (a + b + c) - 3 (4 a + 2 b + c) \\ + (9 a + 3 b + c) \\ = & c \end{aligned}

より

3 d_{1} - 3 d_{2} + d_{3} mod p = c - 3 δ_{1} + 3 δ_{2} - δ_{3}

を上で計算した

p

の近似値を用いて計算すると、

c

の近似値

c = 20713161535193761558784128809506534938870667474516138291919014014508231236559472271196444472147718083977745751388526121905625505

を得る。これを文字列に直すと

"zer0pts{excellent_w0rk!y0u_are_a_master_0f_crypt0!!\x19\xA1"

下のほうはエスパーして、フラグは

zer0pts{excellent_w0rk!y0u_are_a_master_0f_crypt0!!!}

となった。


    
      
        
  
    
    

        


  


  
        
          
          N = [
        
        
          
            1341233826702376842498119940039016826282055747303464974435594326637538907180149241566365225911074218597539880291426265503244204409536388336349105099303221252199164187921036400118788488925884552440483653638244202969641876448593915624469362160298646189903056069767976491733960779483023305191435635289734365528710722401088230332490023131911734288011232016872906051832164035804891447455672110954242647111735228814935698789659541198379357658233047482430645842400366769,
        
        
          
            1411836429669183892966134560305538366838547135114531535251720851922638607907850507674940852917802242615202155607148892358461384679202044548831141295353829571829695255020484687938869019916289932148352179781631904110271902114010910086393396910500275240681423526254331492385949217178047157696773667958133033180038804263460584550022281663780195927924119675790311322672399731902027722031296853164002026620552741589967849779933976523556743919696732887883645621044361611,
        
        
          
            1827670639023479057974423662769264575893916686880865506873460556631343496594640149665454545389837639322275346518374263849034235979447405363606817187890637783196194162726024155794431981524906947485134171466324929779048499566048313669091401079263506127226379009753084566863868890271238236467261185095363669354791741608878314575987029663948818461252180763032199904220494918133642971421746749038691538192915859604276912102975568194119467980419612286906176868952703619,
        
        
          
            1402052496936016320097183149388969226815975944499402219852856803114088852450193317864886134127265736138410526536722880486066577543930136034727844243512981614084924117627899623040044660188020312540158405739267327536264551679882312483493710047604544613918162585552941665913115010517121759370648692761286982491236666306877105976920137441035714264352280173247224313429635552985171274872512067599818448065403462190853902179488909659352339753894521914217223448955215971,
        
        
          
            1342704677106999319938700388688741153377785166648218447242877900112547844266669406514804811924511017558918915960330401218483170328967889513789896923310776509048521832125539811902549091395153161067069971385687776610710438852173147435486069694433486331195576027716222479219032032167578074212853391036064686760331515843088926026790746958731708142341497399752153088465594599246790180097507576747721603670126927119225609501504821203851575717696464442894256866979152071,
        
        
          
          ]
        
        
          
          

        
        
          
          G = [
        
        
          
            26674131724614738833784434076708623929346303545393320399944409878863187402150503055207795853307211144249179748395076848334742855586049336411971031238044174387954252693537728148985955948048292029557791508049506146642880016520533230306989498523300220064692662847160710441255197572391506435448482713046019266895261344521636514739951705743608587218033949609867770113753539973249063631220635085754002655371345431327359674264770777710263422098079037291585196293197114766337658570276078577504309446984989309950901135119579313915133962619448102748,
        
        
          
            54901986783642835051699889113428335659585153809842942356885004842920465421336706391742814742564346205356241657334450930082155461145433648171896778260206136182255774717095790534292114459150791413586339545764791219429615253607065582132297246948860985575596282841990693455389149847062253133706015420405086059551754437445312366999921584484205222674268615179520174172834649126131935196501454388399695961162329114143523185659562031324488650262065740579199795214468943489727171700351304387397461071307646615194578618714043441377328663670751933627,
        
        
          
            141955627685405861596265155634043580262274251775483613944451161608579951914157317215316282492132012795129761525653914539354069858559035449093879514616280531615371142125208924414389214738475566668885506757054698120214732427844927492109681218414883961942239601431792698791724207705264637074459890882510377535948407156226101316457666689930453121343643609559536469767469803312169661110669941502466830780526471703979445391121676012137033701185329849968518454602730837677935298633914797575550202371889703865031673251813095889426000075905120210715,
        
        
          
            86436796561750399172835178406595458158200152808363576725949152209752050457844658406574932376510960241857243310231191629391788175840467781934160642603459961684570827889722817126673212897198457329009359718685889481495826330541120466944045405490044949949259866864077324005529448874478602844692164951174440203087657096219194318354305991767616656455848089449159017933275879827733328877162500978230626795632715808168172022720272496925901610663582044355831900584113960342572153829531696471382379336709069115911649499884361699625754418888357105356,
        
        
          
            151778423244836361358618726678490961359665141861531434745037765026759553125937345447572403824004985824284188179016742237419300096576909738404031925822083587101759301624897645367726786635718018753092807084873240915940763159043557284908261185169254084475196021977237239622460403373815939034200532293365581548664725892312716054043939540402460543140481578956351181169010805594314620139932866466533726652277935117332880706565744981667712583109377942817662191762058437395347618376144282145949244368040832594427185427142218601311894439404196869044,
        
        
          
          ]
        
        
          
          

        
        
          
          C = [
        
        
          
            597508787369395694379078055274758557631538862739941784216641187447047696613646680523204534254585433553841883904815873020522119769161150848487658944289025139852884425534715254212765760070437058597554314741974198161950731308938774064571532399460855957695621714795771549456243813779399463109411846725520743344118554521413815793297768851076100135443002760221642947948812785225122631701884241216019284262219988306790748365483241216049579680655534490056279281295122379176443966669667315043992274193717298501474638381448820981658485993472350525815696097401765948865514729845467484551526100202532018343011967560856014086051860031235536215643818290727062383335942089683311730283931932548912461126311217820002459492022071267001562804194559301166310110244724819006466684456151803974731484616982434451280906366032894303395363863415992620820995729046300233942195095878917887892047030748729267329243516360791348477702146680442138382721731,
        
        
          
            1456602020473336436595302182756958090511415476510657696986700623481719785551149148046222482541285365312188959543693509514194665154201380523065476755444520574235515226702501340621170242202481024616882142010693536315240074931107987736512086290237614373546387137118763177589626855206838418103751404170044959913691735814429141324338320985853997370723970242452295801714270370307506226450063833723978620621565509156414542500828358085837989711050634637181122088180962097398190523961973415973551114076986713383243786853784427170667899647985426058777600468130304251574650780445218699779580427275505399994170596637813422179447545139427789051628741760457519163521253124217051884027796849542531386743511788474207049545545002209680929220223136064442178057025754413867781284144371821327271523387818972046823739716532656252490038504917848103009173556160906958786293914926056507083575731302212603218169279706378356509037364037831069878231086,
        
        
          
            1595390928798835569336924563570335102923880736692143989367168050283822219400199743337809496383236309872055902908859973435410009867512480962418933647220942557496021772016027755153856780432756247783750165029188435931829475752098685139218491512524939261083097196175538068246302620283880442794354650203913256502298415299185414984420565985768541932846631373242689036582178180151029187744659165675733768586790929935335022733816827888717408760672442814312920814112098749134708381258920239270611481275188904733904484814532961896311957117153388398557892281039130937627251977203045005113457955326984992365109238884156875118258875576742912093629961904108637328565523791833431848861487780279931219592300441525537266970002720517825091950356133381996157142667046040400474609347986971206237389511449743320732065481903260813584781835955382208803634275373602785992176618584713593998708722680023507255977968510697362982348044089009664597010849,
        
        
          
            1011012847725577745336080393532189501492336190558468303901251128666948418862933107036802327706950463653743889588322849131239222018844807849320331335500253801822404870042943180018988070672118930708294758392176800835465940314497189212667345256623160148381248676718065742459754530766291525548914975338009832256832712589706835806517309607232698495103676951407256990497727674074485975124944372384103938197756270712242538878327377737064117888518506218677244903776303353809628478075251845418928422454505051034628606854452823018144040158582352384256981850775768889499743760124313790601039804655287368427678715298719610014768027055861100647302291703640051847379108339724116217620803865940790490720181318014407063347236752588796661376810081172579531972899972207972694482013181432385593628852052754597961311854114120889315842451116669964549895840227042765846799089720825799247881359370434521814841837587026380076995924399761319705723220,
        
        
          
            585069911394639305069783453652980853778745872799905806085352980735658699442233349825102728267563130252863283620016490723644364840781783036228871276919495247201207769697803633760636387168623971368425694237096294184568991213677440659398241600565247753979592046970818227704368395870777535026523567976874952173624307944192305292867662966386645876919788206043645183603762002422420998136405555517112532618282483706131862387809257609229574812285296154253501278056085465591743515177435365781927790199047842732048344042345351145298190659111295473008507446985055866290274758068271147032318530780490684852153963206087326840116434394159695925404604438964668680275485416592324577630006500633520246499405212932824588562414909326852417065336364436077691987208909857190371325101826958691831214195954288881703669647778463778679987622877010187433236808312183932607053247793338457198918138891876330549197934696966944916096701567755521275990739,
        
        
          
          ]
        
        
          
          

        
        
          
          n1 = N[0]
        
        
          
          n2 = N[1]
        
        
          
          n3 = N[2]
        
        
          
          n4 = N[3]
        
        
          
          n5 = N[4]
        
        
          
          

        
        
          
          n = 1536
        
        
          
          t = 768
        
        
          
          K = 2 ** (n - t)
        
        
          
          

        
        
          
          M = Matrix(ZZ, [
        
        
          
            [K, 0, 0, 0, 0,  n2,  n3,  n4,  n5,   0,   0,   0,   0,   0,   0],
        
        
          
            [0, K, 0, 0, 0, -n1,   0,   0,   0,  n3,  n4,  n5,   0,   0,   0],
        
        
          
            [0, 0, K, 0, 0,   0, -n1,   0,   0, -n2,   0,   0,  n4,  n5,   0],
        
        
          
            [0, 0, 0, K, 0,   0,   0, -n1,   0,   0, -n2,   0, -n3,   0,  n5],
        
        
          
            [0, 0, 0, 0, K,   0,   0,   0, -n1,   0,   0, -n2,   0, -n3, -n4],
        
        
          
          ])
        
        
          
          E = M.LLL()
        
        
          
          

        
        
          
          Y = []
        
        
          
          P = []
        
        
          
          for row in E:
        
        
          
            for cell, n, g, c in zip(row, N, G, C):
        
        
          
              q = abs(cell / K)
        
        
          
              if n % q == 0:
        
        
          
                p = n / q
        
        
          
                print("(p, q) = ({}, {})".format(p, q))
        
        
          
          

        
        
          
                assert((g - 1) % n == 0)
        
        
          
                k = (g - 1) / n
        
        
          
                λ = lcm(p - 1, q - 1)
        
        
          
                rm = pow(c, λ, n ** 2)
        
        
          
                m = int((rm - 1) * inverse_mod(int(λ * k), n ** 2))
        
        
          
                assert(m % n == 0)
        
        
          
                y = m / n
        
        
          
                print("y = {}".format(y))
        
        
          
          

        
        
          
                Y.append(y)
        
        
          
                P.append(p)
        
        
          
          

        
        
          
          D = [y - p for y, p in zip(Y, P)]
        
        
          
          

        
        
          
          approx_p = D[1] - 3 * D[2] + 3 * D[3] - D[4]
        
        
          
          print("p = {}".format(approx_p))
        
        
          
          

        
        
          
          approx_c = (3 * D[0] - 3 * D[1] + D[2]) % approx_p
        
        
          
          print("c = {}".format(approx_c))
        
        
          
          print(int(approx_c).to_bytes(64, 'big'))
        
  



    

  


      
      
        view raw
        
          solve.sage
        
        hosted with ❤ by GitHub

	ans = File.read('chall.txt').lines.map do \|line\|
	(line.to_i % 2).to_s
	end.to_a.join.reverse.to_i(2).to_s(16)
	puts [ans].pack("H*")

	from socket import socket
	import os
	import re
	import json
	import base64

	conn = socket()
	conn.connect(('13.231.224.102', 3002))

	str = ''
	while '>' not in str:
	str += conn.recv(1024).decode('UTF-8')
	print(str)

	lines = str.split('\n')
	X = []
	for line in lines[1:7]:
	X.extend(list(map(int, re.findall(r'\d+', line))))
	p = int(re.search(r'\d+', lines[7]).group(0))

	print(X, p)

	Ps = []

	for i in range(36):
	data = b'1\n'
	conn.send(data)
	print('<== {}'.format(data))

	b = bytes(map(lambda j: 1 if j == i else 0, range(36)))
	data = base64.b64encode(b) + b'\n'
	conn.send(data)
	print('<== {}'.format(data))

	str = ''
	while '>' not in str:
	str += conn.recv(1024).decode('UTF-8')
	print(str)

	lines = str.split('\n')
	P = []
	for line in lines[1:7]:
	P.extend(list(map(int, re.findall(r'\d+', line))))
	Ps.append(P)

	print('Solving...')
	R = IntegerModRing(p)
	M = Matrix(R, Ps)
	target = vector(R, X)
	result = M.T.solve_right(target)
	print(''.join(list(map(chr, result))))

	import re
	from socket import socket
	from fractions import Fraction

	def decrypt_lsb(c):
	conn = socket()
	conn.connect(('13.231.224.102', 3001))

	str = ''
	while '>' not in str:
	str += conn.recv(1024).decode('UTF-8')
	print(str)

	data = b'2\n'
	print('<== {}'.format(data))
	conn.send(data)
	data = hex(c)[2:].encode('ascii') + b'\n'
	print('<== {}'.format(data))
	conn.send(data)
	data = b'00000000\n'
	print('<== {}'.format(data))
	conn.send(data)

	str = ''
	while 'Signature' not in str:
	str += conn.recv(1024).decode('UTF-8')
	print(str)

	signature = re.search(r'!= (\w{8})', str).group(1)
	print('Signature: {}'.format(signature))

	conn.close()

	return int(signature, 16) % 2

	# http://inaz2.hatenablog.com/entry/2016/11/09/220529
	def lsb_decryption_oracle(c):
	bounds = [0, Fraction(n)]

	i = 0
	while True:
	print('i: {}'.format(i))
	i += 1

	c2 = (c * pow(2, e, n)) % n
	lsb = decrypt_lsb(c2)
	if lsb == 1:
	bounds[0] = sum(bounds) // 2
	else:
	bounds[1] = sum(bounds) // 2
	diff = bounds[1] - bounds[0]
	diff = diff.numerator // diff.denominator
	print(diff)
	print('m: {}'.format(hex(bounds[1].numerator // bounds[1].denominator)))
	if diff == 0:
	m = bounds[1].numerator // bounds[1].denominator
	return m
	c = c2

	n = 0x6d70b5a586fcc4135f0c590e470c8d6758ce47ce88263ff4d4cf49163457c71e944e9da2b20c2ccb0936360f12c07df7e7e80cd1f38f2c449aad8adaa5c6e3d51f15878f456ceee4f61547302960d9d6a5bdfad136ed0eb7691358d36ae93aeb300c260e512faefe5cc0f41c546b959082b4714f05339621b225608da849c30f
	e = 0x10001
	c = 0x3cfa0e6ea76e899f86f9a8b50fd6e76731ca5528d59f074491ef7a6271513b2f202f4777f48a349944746e97b9e8a4521a52c86ef20e9ea354c0261ed7d73fc4ce5002c45e7b0481bb8cbe6ce1f9ef8228351dd7daa13ccc1e3febd11e8df1a99303fd2a2f789772f64cbdb847d6544393e53eee20f3076d6cdb484094ceb5c1

	print(lsb_decryption_oracle(c))

	N = [
	1341233826702376842498119940039016826282055747303464974435594326637538907180149241566365225911074218597539880291426265503244204409536388336349105099303221252199164187921036400118788488925884552440483653638244202969641876448593915624469362160298646189903056069767976491733960779483023305191435635289734365528710722401088230332490023131911734288011232016872906051832164035804891447455672110954242647111735228814935698789659541198379357658233047482430645842400366769,
	1411836429669183892966134560305538366838547135114531535251720851922638607907850507674940852917802242615202155607148892358461384679202044548831141295353829571829695255020484687938869019916289932148352179781631904110271902114010910086393396910500275240681423526254331492385949217178047157696773667958133033180038804263460584550022281663780195927924119675790311322672399731902027722031296853164002026620552741589967849779933976523556743919696732887883645621044361611,
	1827670639023479057974423662769264575893916686880865506873460556631343496594640149665454545389837639322275346518374263849034235979447405363606817187890637783196194162726024155794431981524906947485134171466324929779048499566048313669091401079263506127226379009753084566863868890271238236467261185095363669354791741608878314575987029663948818461252180763032199904220494918133642971421746749038691538192915859604276912102975568194119467980419612286906176868952703619,
	1402052496936016320097183149388969226815975944499402219852856803114088852450193317864886134127265736138410526536722880486066577543930136034727844243512981614084924117627899623040044660188020312540158405739267327536264551679882312483493710047604544613918162585552941665913115010517121759370648692761286982491236666306877105976920137441035714264352280173247224313429635552985171274872512067599818448065403462190853902179488909659352339753894521914217223448955215971,
	1342704677106999319938700388688741153377785166648218447242877900112547844266669406514804811924511017558918915960330401218483170328967889513789896923310776509048521832125539811902549091395153161067069971385687776610710438852173147435486069694433486331195576027716222479219032032167578074212853391036064686760331515843088926026790746958731708142341497399752153088465594599246790180097507576747721603670126927119225609501504821203851575717696464442894256866979152071,
	]

	G = [
	26674131724614738833784434076708623929346303545393320399944409878863187402150503055207795853307211144249179748395076848334742855586049336411971031238044174387954252693537728148985955948048292029557791508049506146642880016520533230306989498523300220064692662847160710441255197572391506435448482713046019266895261344521636514739951705743608587218033949609867770113753539973249063631220635085754002655371345431327359674264770777710263422098079037291585196293197114766337658570276078577504309446984989309950901135119579313915133962619448102748,
	54901986783642835051699889113428335659585153809842942356885004842920465421336706391742814742564346205356241657334450930082155461145433648171896778260206136182255774717095790534292114459150791413586339545764791219429615253607065582132297246948860985575596282841990693455389149847062253133706015420405086059551754437445312366999921584484205222674268615179520174172834649126131935196501454388399695961162329114143523185659562031324488650262065740579199795214468943489727171700351304387397461071307646615194578618714043441377328663670751933627,
	141955627685405861596265155634043580262274251775483613944451161608579951914157317215316282492132012795129761525653914539354069858559035449093879514616280531615371142125208924414389214738475566668885506757054698120214732427844927492109681218414883961942239601431792698791724207705264637074459890882510377535948407156226101316457666689930453121343643609559536469767469803312169661110669941502466830780526471703979445391121676012137033701185329849968518454602730837677935298633914797575550202371889703865031673251813095889426000075905120210715,
	86436796561750399172835178406595458158200152808363576725949152209752050457844658406574932376510960241857243310231191629391788175840467781934160642603459961684570827889722817126673212897198457329009359718685889481495826330541120466944045405490044949949259866864077324005529448874478602844692164951174440203087657096219194318354305991767616656455848089449159017933275879827733328877162500978230626795632715808168172022720272496925901610663582044355831900584113960342572153829531696471382379336709069115911649499884361699625754418888357105356,
	151778423244836361358618726678490961359665141861531434745037765026759553125937345447572403824004985824284188179016742237419300096576909738404031925822083587101759301624897645367726786635718018753092807084873240915940763159043557284908261185169254084475196021977237239622460403373815939034200532293365581548664725892312716054043939540402460543140481578956351181169010805594314620139932866466533726652277935117332880706565744981667712583109377942817662191762058437395347618376144282145949244368040832594427185427142218601311894439404196869044,
	]

	C = [
	597508787369395694379078055274758557631538862739941784216641187447047696613646680523204534254585433553841883904815873020522119769161150848487658944289025139852884425534715254212765760070437058597554314741974198161950731308938774064571532399460855957695621714795771549456243813779399463109411846725520743344118554521413815793297768851076100135443002760221642947948812785225122631701884241216019284262219988306790748365483241216049579680655534490056279281295122379176443966669667315043992274193717298501474638381448820981658485993472350525815696097401765948865514729845467484551526100202532018343011967560856014086051860031235536215643818290727062383335942089683311730283931932548912461126311217820002459492022071267001562804194559301166310110244724819006466684456151803974731484616982434451280906366032894303395363863415992620820995729046300233942195095878917887892047030748729267329243516360791348477702146680442138382721731,
	1456602020473336436595302182756958090511415476510657696986700623481719785551149148046222482541285365312188959543693509514194665154201380523065476755444520574235515226702501340621170242202481024616882142010693536315240074931107987736512086290237614373546387137118763177589626855206838418103751404170044959913691735814429141324338320985853997370723970242452295801714270370307506226450063833723978620621565509156414542500828358085837989711050634637181122088180962097398190523961973415973551114076986713383243786853784427170667899647985426058777600468130304251574650780445218699779580427275505399994170596637813422179447545139427789051628741760457519163521253124217051884027796849542531386743511788474207049545545002209680929220223136064442178057025754413867781284144371821327271523387818972046823739716532656252490038504917848103009173556160906958786293914926056507083575731302212603218169279706378356509037364037831069878231086,
	1595390928798835569336924563570335102923880736692143989367168050283822219400199743337809496383236309872055902908859973435410009867512480962418933647220942557496021772016027755153856780432756247783750165029188435931829475752098685139218491512524939261083097196175538068246302620283880442794354650203913256502298415299185414984420565985768541932846631373242689036582178180151029187744659165675733768586790929935335022733816827888717408760672442814312920814112098749134708381258920239270611481275188904733904484814532961896311957117153388398557892281039130937627251977203045005113457955326984992365109238884156875118258875576742912093629961904108637328565523791833431848861487780279931219592300441525537266970002720517825091950356133381996157142667046040400474609347986971206237389511449743320732065481903260813584781835955382208803634275373602785992176618584713593998708722680023507255977968510697362982348044089009664597010849,
	1011012847725577745336080393532189501492336190558468303901251128666948418862933107036802327706950463653743889588322849131239222018844807849320331335500253801822404870042943180018988070672118930708294758392176800835465940314497189212667345256623160148381248676718065742459754530766291525548914975338009832256832712589706835806517309607232698495103676951407256990497727674074485975124944372384103938197756270712242538878327377737064117888518506218677244903776303353809628478075251845418928422454505051034628606854452823018144040158582352384256981850775768889499743760124313790601039804655287368427678715298719610014768027055861100647302291703640051847379108339724116217620803865940790490720181318014407063347236752588796661376810081172579531972899972207972694482013181432385593628852052754597961311854114120889315842451116669964549895840227042765846799089720825799247881359370434521814841837587026380076995924399761319705723220,
	585069911394639305069783453652980853778745872799905806085352980735658699442233349825102728267563130252863283620016490723644364840781783036228871276919495247201207769697803633760636387168623971368425694237096294184568991213677440659398241600565247753979592046970818227704368395870777535026523567976874952173624307944192305292867662966386645876919788206043645183603762002422420998136405555517112532618282483706131862387809257609229574812285296154253501278056085465591743515177435365781927790199047842732048344042345351145298190659111295473008507446985055866290274758068271147032318530780490684852153963206087326840116434394159695925404604438964668680275485416592324577630006500633520246499405212932824588562414909326852417065336364436077691987208909857190371325101826958691831214195954288881703669647778463778679987622877010187433236808312183932607053247793338457198918138891876330549197934696966944916096701567755521275990739,
	]

	n1 = N[0]
	n2 = N[1]
	n3 = N[2]
	n4 = N[3]
	n5 = N[4]

	n = 1536
	t = 768
	K = 2 ** (n - t)

	M = Matrix(ZZ, [
	[K, 0, 0, 0, 0, n2, n3, n4, n5, 0, 0, 0, 0, 0, 0],
	[0, K, 0, 0, 0, -n1, 0, 0, 0, n3, n4, n5, 0, 0, 0],
	[0, 0, K, 0, 0, 0, -n1, 0, 0, -n2, 0, 0, n4, n5, 0],
	[0, 0, 0, K, 0, 0, 0, -n1, 0, 0, -n2, 0, -n3, 0, n5],
	[0, 0, 0, 0, K, 0, 0, 0, -n1, 0, 0, -n2, 0, -n3, -n4],
	])
	E = M.LLL()

	Y = []
	P = []
	for row in E:
	for cell, n, g, c in zip(row, N, G, C):
	q = abs(cell / K)
	if n % q == 0:
	p = n / q
	print("(p, q) = ({}, {})".format(p, q))

	assert((g - 1) % n == 0)
	k = (g - 1) / n
	λ = lcm(p - 1, q - 1)
	rm = pow(c, λ, n ** 2)
	m = int((rm - 1) * inverse_mod(int(λ * k), n ** 2))
	assert(m % n == 0)
	y = m / n
	print("y = {}".format(y))

	Y.append(y)
	P.append(p)

	D = [y - p for y, p in zip(Y, P)]

	approx_p = D[1] - 3 * D[2] + 3 * D[3] - D[4]
	print("p = {}".format(approx_p))

	approx_c = (3 * D[0] - 3 * D[1] + D[2]) % approx_p
	print("c = {}".format(approx_c))
	print(int(approx_c).to_bytes(64, 'big'))

zer0pts CTF 2020 writeup

Overview

ROR (Crypto, 260pts)

Solution

nibelung (Crypto, 525pts)

Solution

diysig (Crypto, 394pts)

Solution

dirty laundary (Crypto, 636pts)

Solution

Read more

Learning with Exploitation author's writeup

BSides Ahmedabad CTF 2021 Writeup - SSSS.RNG, floorsa, Roda

TSG CTF 2021 Beginner's Web 2021 Writeup

TSG CTF 2021 Giita Writeup