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}