TSG CTF 2020 Writeups

• Beginners Crypto
  • Category : Crypto
  • Files : beginner.py
  • Points : 107
  • Solves : 86
• Modulus Amittendus
  • Category : Crypto
  • Files : rsa.rb, pubkey.json, output.txt
  • Points : 365
  • Solves : 5
  • solution code : solve.py

Beginners Crypto challenge writeup [Crypto]

We were given a single file (beginner.py) which contains two assert conditions.

assert(len(open('flag.txt', 'rb').read()) <= 50)
assert(str(int.from_bytes(open('flag.txt', 'rb').read(), byteorder='big') << 10000).endswith('1002773875431658367671665822006771085816631054109509173556585546508965236428620487083647585179992085437922318783218149808537210712780660412301729655917441546549321914516504576'))

First condition checks that length of the flag is less than or equal to 50.
Second condition reads and converts the flag to an integer then left shifts it to 10000, and then converts the resultant to string and checks that strings ends with given value.

Rephrasing the two conditions :
len(flag) <= 50 implies when converted to integer it will be less than 2**(8*50) = 2**400
left shift in the second condition can be written as flag * 2**10000 as str function represents the integer in base 10 and endswith parameter contains number of 175 digits. So,

flag <= 2**400
flag * 2**10000 % 10**175 = 1002773875431658367671665822006771085816631054109509173556585546508965236428620487083647585179992085437922318783218149808537210712780660412301729655917441546549321914516504576

multiplying the inverse of 2**10000 modulo 10**175 would give the flag modulo 10**175 which would give original flag value but the problem is that inverse doesn’t for 2**10000 modulo 10**175 as gcd of both values is not equal to 1.
In order to get the flag we can use 5**175 as the modulus as it is a factor of 10**175.

((flag * 2**10000) % 10**175) % 5**175 == (flag * 2**10000) % 5**175
(flag * 2**10000) * inverse(2**10000, 5**175) == flag
As 5**175 > 2**400 resultant of above computation will give us the Original Flag.

Flag :: TSGCTF{0K4y_Y0U_are_r3aDy_t0_Go_aNd_dO_M0r3_CryPt} —

Modulus Amittendus challenge writeup [Crypto]

Luckily, I got First Blood for this Challenge.
In this challenge we were given rsa.rb, output.txt, pubkey.json.
rsa.rb contains the implementation of Textbook rsa encryption.
rsa.rb generates two random primes p and q each 1024 bits long.
output.txt contains rsa encrypted flag with e = 65537.
pubkey.json contains json data with keys e, n, cf.

Even though pubkey.json contains n as key but its value is d.

  def pubkey
    privkey.to_a[..2].to_h
  end

  def privkey
    {
      e: @e,
      n: @d,
      cf: @cf,
      p: @p,
      q: @q,
      exp1: @exp1,
      exp2: @exp2,
    }
  end

In order to solve the challenge we have to calculate the value of n = p * q. so, we have values of e, d and cf.

e = 65537
d = 27451162557471435115589774083548548295656504741540442329428952622804866596982747294930359990602468139076296433114830591568558281638895221175730257057177963017177029796952153436494826699802526267315286199047856818119832831065330607262567182123834935483241720327760312585050990828017966534872294866865933062292893033455722786996125448961180665396831710915882697366767203858387536850040283296013681157070419459208544201363726008380145444214578735817521392863391376821427153094146080055636026442795625833039248405951946367504865008639190248509000950429593990524808051779361516918410348680313371657111798761410501793645137
cf = q**-1 mod p = 113350138578125471637271827037682321496361317426731366252238155037440385105997423113671392038498349668206564266165641194668802966439465128197299073392773586475372002967691512324151673246253769186679521811837698540632534357656221715752733588763108463093085549826122278822507051740839450621887847679420115044512

As

e * d = 1 mod phi(n)
e * d - 1 = k * phi(n) , k < min(e, d)
phi(n) = (e * d - 1) // k
phi(n) < (n = p*q) < 2**2048

Trying the k values from 2 to e - 1 and checking two conditions (e * d - 1) % k == 0 and phi(n) < 2**2048 gives only single possible value for k, k = 62676. Calculating (e * d - 1) // k gives us the value of phi(n)

Using the values of cf = q**-1 mod p, phi(n) and their formulas gives us

cf = q**-1 mod p
cf * q = 1 mod p
cf * q - 1 = 0 mod p
phi(n) = (p - 1) * (q - 1) = p * q - p - q + 1 = n - p - q + 1
cf * phi(n) = cf * (n - p - q + 1) = cf * n - cf * p - cf * q + cf
cf * phi(n) mod p = (cf * n - cf * p - cf * q + cf) mod p
                  = 0 - 0 - (cf * q) + cf mod p
                  = - (1) + cf mod p
                  = cf - 1 mod p
cf * phi(n) - cf + 1 = 0 mod p
cf * phi(n) - cf + 1 = kp * p

cf * phi(n) - cf + 1 gives us a multiple of p. let pmul = cf * phi(n) - cf + 1.

And

from fermat theorem
r**(p-1) = 1 mod p , r is a random integer. 
r**phi(n) = (r**(p-1))**(q-1) = (1)**(q-1) mod p = 1 mod p

For any random integer r, k1, k2
r mod k2 == (r mod k1) mod k2 is True if k2 is a factor of k1.

Therefore,
r**phi(n) mod p = (r**phi(n) mod pmul) mod p = 1
we cannot calculate r**phi(n) directly but we can calculate r**phi(n) mod pmul using square and multiply algorithm.
(r**phi(n) mod pmul) mod p = 1 mod p
pow(r, phi(n), pmul) - 1 = k * p
In this way we can obtain any number of p multiples. Calculating the gcd of multiples of p gives the value of p.
Given p we can calculate the value of q using cf (qInv mod p).

After obtaining the value of n = p * q, decrypting the ciphertext gives us the flag.

Solution Script :: solve.py

FLAG :: TSGCTF{Okay_this_flag_will_be_quite_long_so_listen_carefully_Happiness_is_our_bodys_default_setting_Please_dont_feel_SAd_in_all_sense_Be_happy!_Anyway_this_challenge_is_simple_rewrite_of_HITCON_CTF_2019_Lost_Modulus_Again_so_Im_very_thankful_to_the_author}