over 8 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}
