TokyoWesterns CTF 6th 2020 | circular

require "functions_framework"
require "digest/sha2"

fail unless ENV["FLAG"]

key = JSON.parse(File.read("pubkey.txt"))
n = key["n"].to_i
k = key["k"].to_i

EXPECTED_MESSAGE = 'SUNSHINE RHYTHM'

FunctionsFramework.http("index") do |request|
  if request.request_method != "POST"
    return "Bad Request"
  end

  data = JSON.parse(request.body.read)
  cmd = data["cmd"]
  if cmd == "pubkey"
    return { pubkey: { n: n.to_s, k: k.to_s } }
  elsif cmd == "verify"
    x = data["x"].to_i
    y = data["y"].to_i
    msg = data["msg"].to_s
    hash = ""
    4.times do |i|
      hash += Digest::SHA512.hexdigest(msg + i.to_s)
    end
    hash = hash.to_i(16) % n
    signature = (x ** 2 + k * y ** 2) % n

    if signature == hash
      if msg == EXPECTED_MESSAGE
        return { result: ENV["FLAG"] }
      end
      return { result: "verify success" }
    else
      return { result: "verify failed" }
    end
  else
    return "invalid command"
  end
end

を満たすをみつけよ、という問題。これは Ong-Schnorr-Shamir Digital Signature Scheme というschemeで、すでに破られていて効率よく解ける↓

https://www.researchgate.net/publication/262234058_An_efficient_solution_of_the_congruence