almost 9 years ago

題目給的是一份 python source,是一個 RSA 加解密系統。
有固定的公鑰 N, e 和私鑰 p, q, d,但都是未知的,並且有一個固定的目標密文 C 需要解密。
系統提供任意數字加密和任意數字解密的功能,但是解密不能給目標密文 C

反正解密其實就是求 C^d (mod N),不能給 C 的話我們給 -C 就好了呀,反正答案頂多差個負號。
但是因為輸入的數字要在 [1, N-1] 之間,要先找出 N 是多少。

因為輸入的數字超出範圍時會報錯,可以直接二分搜尋 N 的大小。
一次連線的時間最多為一分鐘,但是因為 N 是固定的可以多次連線搜完。

來 code:

require_relative 'zocket' # custom library

$z = Zocket.new '202.120.7.76', 43434

def cmd(x)
  $z.gets "Command:\n", do_log: false
  $z.puts x
end

def is_valid(n)
  cmd(1)
  $z.gets "Input Plaintext:\n", do_log: false
  $z.puts n, do_log: false
  res = $z.gets.strip
  if res == 'Invalid Plaintext'
    return false
  else
    $z.gets(do_log: false)
    return true
  end
end

def binary_search_n
  l = 0
  r = 0
  unless File.exist? 'binary_search_n'
    n = 2 ** 1024
    while is_valid(n)
      n *= 2
    end
    l = 1
    r = n
  else
    open('binary_search_n', 'r') do |f|
      l = f.gets.to_i
      r = f.gets.to_i
    end
  end
  while l < r
    m = (l + r + 1) / 2
    if is_valid(m)
      l = m
    else
      r = m - 1
    end
    open('binary_search_n', 'w') do |f|
      f.puts l
      f.puts r
    end
  end
  return l + 1
end

n = binary_search_n
puts "n = #{n}"

cmd(3)
$z.gets "I have no bug\n"
secret = $z.gets.to_i

cmd(2)
$z.gets "Input Ciphertext:\n"
$z.puts (n - secret)
$z.gets "Your plaintext:\n"
p = $z.gets.to_i

require 'openssl'
puts p.to_bn.to_s(2).inspect
puts (n-p).to_bn.to_s(2).inspect

Flag: ISG{chosen_ciphertext_attack_breaks_textbook_RSA}

← ISG2014 Checkin ISG2014 AFERE →