https://nsucrypto.nsu.ru/archive/2021/round/2/task/4/#data
Ý chính của bài tập: Tìm chìa khóa bí mật $k$, có quyền truy cập vào $Enc(x, d) = Enc(x^d \bmod n), n = 1060105447831$.
tôi sẽ giả sử $0 < k < n.$
$Enc$ là một hàm băm thông thường, nó trả về đầu ra giống như đầu vào tương ứng của nó.
Tôi muốn tìm một vụ va chạm sao cho $hash(k, 1) = hash(x, d)$, điều này có nghĩa là tôi đã tìm thấy $k = x^d \bmod n.$
Ý tưởng đầu tiên của tôi là tìm kiếm trình tạo nhóm tuần hoàn của $Z_{1060105447831}$, nhưng tôi phát hiện ra rằng 2 và 3 và không có gì trong 20000 số đầu tiên hoạt động. Tôi sẽ sử dụng trình tạo để kiểm tra va chạm cho $k$. Tôi biết $2^{40} > n$. Nó cũng sẽ giúp sử dụng trình tạo để tính logarit rời rạc và tìm giá trị của k nhanh hơn. Tôi muốn kiểm tra nó nhưng có vẻ như vấn đề đã được tạo ra khi kiểm tra thủ công.
Một cuộc tấn công sinh nhật không hoạt động đối với hàm băm 128 bit nếu tôi muốn có xác suất và hiệu quả tốt.
Tôi cũng đã thử lấy giá trị băm của các giá trị nhỏ Enc(2,1), Enc(3,1) ... Enc(10, 1) để xem liệu hàm băm có bất kỳ mối quan hệ ẩn nào giữa các đầu ra của nó hay không.
Ngoài ra, $\phi(n)$ có một yếu tố tốt đẹp của số lượng nhỏ.
Tôi sẽ thêm bất kỳ chi tiết quan trọng mới.
Những giá trị nào nên được chọn để giúp tìm k? Họ có quan trọng không? Trình tạo không hữu ích, tôi không thể áp dụng bất kỳ thuật toán nào nhanh hơn cho lũy thừa mô-đun vì tất cả những gì tôi nhận được là một chuỗi 128 bit. Tất cả những gì tôi có thể làm là kiểm tra xem một số hoặc lũy thừa của một số có mã hóa bằng với mã của số bí mật hay không $k$
