[Sharif University CTF Quals 2013] too hard? (crypto300)

Chúng ta cần tìm một số x sao cho:

(11111111111111111111112 ^ x) % 123456790123456790123454320987654320987654321 = 1173805180904286755555543817503746512689

Nội dung chính

Đây là một bài mà ngay khi đọc đề, trong trái tim nhân hậu và đầy thiện lương của mình sớm phát sinh hai luồng suy nghĩ trái chiều:

  • Một là mình có thể làm được nó emo_popo_sure
  • Hai là, nếu mình có thể làm được nó chỉ sau ánh mắt nhìn đầu tiên, thì sao nó lại có giá 300 điểm?

Một lần nữa lại buộc phải sống chậm lại để thấy được rằng, chẳng có gì là công bằng, chẳng có gì là hoàn hảo cả. Một bài 300 điểm có thể dễ, một bài 100 điểm có thể khó, sống tử tế thì thường ế mà sống khốn nạn thì nhiều người ngó…

Sau vài ba phút lang thang trên Google, đọc qua biết bao là bí kíp Toán học trên trời dưới bể, Féc Ma rồi Ơ Clít, ghi ghi chép chép trên cuốn vở ô ly chi chít chữ, đi đến một phát hiện quan trọng như đang mộng:

[python]num = 11111111111111111111112
for i in range(1, 10):
num *= 11111111111111111111112
num %= 123456790123456790123454320987654320987654321
print i, num[/python]

Output:

[sh]1 22222222222222222222223
2 33333333333333333333334
3 44444444444444444444445
4 55555555555555555555556
5 66666666666666666666667
6 77777777777777777777778
7 88888888888888888888889
8 100000000000000000000000
9 111111111111111111111111[/sh]

Tính hiệu của chúng theo từng cặp, lạ kỳ thay khi tất cả đều bằng 11111111111111111111111 surrender

Ok, case closed emo_popo_look_down

Chúng ta xác định x bằng cách:

y = (1173805180904286755555543817503746512689 - 11111111111111111111112) / 11111111111111111111111
  = 105642466281385807

x = y + 1
  = 105642466281385808

flag = md5(x) = d0cacf9701b449aae0b236f1626d5688.

You may also like...

1 Response

  1. yeuchimse says:

    Lời giải phản ánh đúng độ khó của bài toán đây :”>

    http://blog.rocco.io/ctf/Sharif-CTF-Too-Hard-300/

Leave a Reply

Your email address will not be published. Required fields are marked *