over 9 years ago
亂試了一陣,觀察並猜測的結論如下
- 第一次 mix 的兩個數字,第一個當 1,第二個當 g (base)
- mix 是模某個質數 P 下的乘法
- 題目問 how much A in B,意思是求出 x 使 A^x = B
- inv x = x^(-1)
所以這是一個離散對數問題,題目的數字範圍卡得很緊 (它其實會故意生成最差的情況),所以要小心處理。
限制 mix + guess 總共 251 次,inv 不計次數,我們可以用 Pollard's rho algorithm,最差情況下花 O(sqrt(P)) 步解出。
#include <bits/stdc++.h>
#include <openssl/sha.h> // man 3 sha1
// g++ sha1prefix.cpp -o sha1prefix -Ofast -lcrypto
// ./sha1prefix bedca4b89c129c89
int main(int argc, char *argv[]) {
int n = strlen(argv[1]) / 2, x;
unsigned char s[64] = {}, h[64];
for (int i = 0; i < n; i++) {
sscanf(argv[1] + 2*i, "%2x", &x);
s[i] = x;
}
while (true) {
for (int i = n; ++s[i] == 0; i++);
SHA1(s, n + 4, h);
if (!h[0] && !h[1] && !h[2]) break;
}
for (int i = 0; i < n + 4; i++) printf("%02x", s[i]);
puts("");
}
#!/usr/bin/env ruby
require 'socket'
$sock = TCPSocket.new('109.233.61.11', 3126)
def send(s)
puts s
$sock.puts s
res = $sock.gets
puts res
res.split.first
end
def mix(x, y)
send "mix #{x} #{y}"
end
def inv(x)
send "inv #{x}"
end
def guess(x)
send "guess #{x}"
end
lines = 4.times.map { $sock.gets }
puts lines
prefix = lines[1].split.last
s = `./sha1prefix #{prefix}`
puts s
$sock.puts s
lines = 5.times.map { $sock.gets }
puts lines
a, b = lines[1].scan(/'(.*?)'/).flatten
inv('one')
Q = 120 # Q + P / (2Q) <= 251
pow_of_a = {
0 => 'one',
+1 => a,
-1 => inv(a)
}
(2..Q).each do |i|
pow_of_a[+i] = mix(a, pow_of_a[i-1])
pow_of_a[-i] = inv(pow_of_a[i])
end
step = mix(pow_of_a[-Q], pow_of_a[-Q]) # a ^ (-2Q)
k = 0
now = b
until pow_of_a.has_value?(now) do
now = mix(now, step)
k += 1
end
t = pow_of_a.rassoc(now).first
guess(t + k * 2 * Q) # b * a^(k * -2Q) = a^t