BSides Ahmedabad CTF 2021

dlppp (151 pts/39 solves)

Problem

Can you solve DLP?

task.py

import os
from Crypto.Util.number import getPrime, getRandomNBitInteger

flag = os.getenv("FLAG", "XXXX{sample_flag}").encode()
m = int.from_bytes(flag, 'big')

p = getPrime(512)
y = pow(1 + p, m, p**3)

assert m < p
print(f"p = {hex(p)}")
print(f"y = {hex(y)}")

output.txt

p = 0xa1c8e1e9b2301cb1f5d424ec6d959d7f275e11507b2177d55f3dc1268c9a3164b72832f362975023f09623814f80fe0ffad179d0e51c40b8a1f882d1f5f28e71
y = 0x6fa0fcc8c9c5f695a5709243698d7640c27c45352375919d538137333ab3a2c748cae5e7c1294d6ffc4007476f6fec6421c992f9fe1919b381306300caa2260953e48f2ec0de7b8c6417faa42001a748b1b367f5211095ddd6bf4e681f7e7ad787e0a7f562f6f0307d6a8d7e8d18cd59bd7572f0c4f430f0fd4fc61503b203f3bcd6dd0b0f84bbdbd42126d95b525fe77e4be62c6dbd083dbcaa284b20a9ea6faf9cbaf20dd88b0180417c9021fa1dcb52b2348c4376bd6b9b38a6c860086af

Solve:

Theo nhị thức Newton, bây giờ mình gọi p là n nha, mình khai triển (n+1)^3 ra:

Gọi:

solve.py

from Crypto.Util.number import *

p = 0xa1c8e1e9b2301cb1f5d424ec6d959d7f275e11507b2177d55f3dc1268c9a3164b72832f362975023f09623814f80fe0ffad179d0e51c40b8a1f882d1f5f28e71
y = 0x6fa0fcc8c9c5f695a5709243698d7640c27c45352375919d538137333ab3a2c748cae5e7c1294d6ffc4007476f6fec6421c992f9fe1919b381306300caa2260953e48f2ec0de7b8c6417faa42001a748b1b367f5211095ddd6bf4e681f7e7ad787e0a7f562f6f0307d6a8d7e8d18cd59bd7572f0c4f430f0fd4fc61503b203f3bcd6dd0b0f84bbdbd42126d95b525fe77e4be62c6dbd083dbcaa284b20a9ea6faf9cbaf20dd88b0180417c9021fa1dcb52b2348c4376bd6b9b38a6c860086af

p = int(p)
y = int(y)

print(long_to_bytes(((y % (pow(p,2))) - 1) //p))

FLAG: Neko{b1n0m1al_th3or3m0o00oo000ooo00000ooooo00000000n}

floorsa (178 pts/27 solves)

Problem

Something about the private key is leaking but with error.

chall.py

import os
import hashlib
from Crypto.Util.number import getPrime, getRandomNBitInteger
from itertools import product

def floor_sum(n: int, m: int, a: int) -> int:
  """Fast calculation for sum([a * i // m for i in range(n)])
  """
  res, b = 0, 0
  while 0 < n:
    res += n * (n - 1) // 2 * (a // m)
    a %= m
    res += n * (b // m)
    b %= m
    last = a * n + b
    n, m, a, b = last // m, a, m, last % m
  return res

#def floor_sum_tests():
#  for n, m, a in product(range(50), range(1, 50), range(50)):
#    result = floor_sum(n, m, a) 
#    expect = sum([a * i // m for i in range(n)])
#    assert(result == expect)

if __name__ == '__main__':
  #floor_sum_tests()

  flag = os.getenv('FLAG', 'XXXX{sample_flag}').encode()
  flag += hashlib.sha512(flag).digest()
  m = int.from_bytes(flag, 'big')
  assert m.bit_length() < 2048

  p = getPrime(1024)
  q = getPrime(1024)
  n = p * q
  e = 65537
  c = pow(m, e, n)
  s = floor_sum(q, q, p)
****
  print(f"c = {c}")
  print(f"n = {n}")****
  print(f"s = {s}")

Solve:

Flow của chương trình:

Là 1 chương trình RSA bình thường
Dữ liệu cho c, n, e, s
s được tính trong hàm floor_sum()

Ở hàm floor_sum(), ta thấy nó tính toán như thế này:

với i chạy từ 0 đến n-1

Có:

và:

Gom nhóm nó lại:

Với n = m, ta được:

mà m là số nguyên tố => các phép chia đều là số không nguyên, ta rút được 1 tính chất như sau:

……………………………………..

Vậy phép toán trở thành:

Vậy là ta có phi(n) rồi? Có thể từ đó mà tìm được d ❤❤😎

Sau đó từ d lụm lại message thôi ez mà he he:

solve.py

from Crypto.Util.number import *

c = 23040235907187792043102377766239160347012425454756214402219399982044253963561544138187423569531882081170834886320190973854626011799820277883217582208960795474430615579336090533683566370889382239077437657567815790536809115842475993748108172855688647606634510990327206587307392015543017884876145469179123535144938693302707229724909443912012098405828416163212773471183275687343852756789315215914149905888864296778004572587778916842514807079884644431138433900314631727531570096879428541834626325720522038566946030094711700613155240677360427005636301342509966941323931780006792225168839057660986447452212763627881844882128
n = 25436172154773316497363731760659809627551021985352168624695689317365040018878195925779734249357382145683534839534348832631746578327288150976696513216052612085728199134879493012682967254530827617417753223998955022174337237825391634619718971640535408277659054217709169558518413217237374290054035438476060534235907848570089739603581573457194953083783917042829987113625590656741008590506988903895998008845547262465276679611851110911540261411521221317990139079888782193797945245078986517794660508171428778191152342783279365287710944280356669999624474416422142006473378042779555537142175392801014489187786764971671239717769
s = 12718086077386658248681865880329904813775510992676084312347844658682520009439097962889867124678691072841767419767174416315873289163644075488348256608026306042864099567439746506341483627265413808708876611999477511087168618912695817309859485820267704138829527108854584779259206608618687145027017719238030267117794390566380531016624830798422997060308480467087130633621890831591995264022449058406630323270130520401030807803477672651197312971884784226103671425190328967548002718406368654056897938481966140031709870266384782295285897095028680666943294657806202686252742158733266700286323555374087306844259404255328911060160
e = 65537

d = inverse(e, 2*s)
print(long_to_bytes(pow(c, d, n)))

FLAG: Neko{fl00r_func710n_1s_n0t_4n_3rr0r_ac1c29e1b5ff4fcaf0e1a0c1b36bb45c}

Hơ he he