Nghịch lý Birthday là 1 trong những nghịch lý được áp dụng rất nhiều khi dùng để giải mã trong Crypto. Câu hỏi: "Cần ít nhất bao nhiêu người để xác suất có 1 cặp trong số đó trùng ngày-tháng sinh với nhau là > 50%?" Câu trả lời là 23 người. Nghe qua thì hơi khó tin, lần đầu nghe mình cũng không tin lắm :)) nhưng để chứng minh nó bằng các giải ngược thì khá đơn giản: Gọi A là biến cố không có ai trong 23 người cùng ngày sinh, ta cần tính 1- P(A). Ta có: Với mỗi người ta có cách chọn ngày sinh lần lượt là: 365, 365 - 1, ..., 365 - 22 Không gian mẫu: 365^23 Suy ra: 1- P(A) = 50.73% Vậy nên trong 1 lớp họp có hơn 30 người, xác suất có 2 người trùng ngày sinh lên tới gần 70%, nên thường trong 1 lớp sẽ có 2 người trung ngày sinh. Phát biểu: Chỉ cần thử 1.2 * sqrt(n) thì sẽ có tới 50% là có 1 cặp giống nhau. Áp dụng định lý này với phương pháp Brute-force:
Bài này mình chỉ đọc mã nguồn chứ chưa biết cách debug khác tiện dụng hơn :)) Trình độ đọc Assembly của mình đang khá kém nên mọi người không nên tin 100% phần giải thích là đúng hoàn toàn :)
Từ main: ta hiểu đoạn code này để tạo không gian lưu trữ và nhập input người dùng được lưu vào w0
Tiếp sau đó là lệnh "bl func" nên ta xem đoạn mã nhãn "func":
Sau đoạn code này ta biết w0 sẽ là 1813 - a và quay về main:
Sau khi quay về main ta thấy lệnh "cmp w0, 0" là lệnh so sánh w0 với 0. Nếu w0 = 0 thì trả về 1, w0 != 0 thì trả về 0. Bên dưới có "bne .L4" (branch if not equal) tức là nếu w0 != 0 thì thực hiện L4 mà L4 sẽ dẫn ta đến LC1 trả về "You lose" nên mục đích của ta là vượt qua mà không nhảy đến L4 để thực hiện lệnh tiếp theo là nhảy để LC0 trả về "You win" hay nói cách khác ta cần w0 = 0. Vậy 1813 - a = 0 hay a = 1813.
Vậy đáp án là picoCTF{00000715} //nhớ ghi đủ 8 chữ số nhé :))
Nhận xét
Đăng nhận xét