[SVATT2017 Qualifitation Round] - Crypto1 - 100pts
Đề bài :
Và đương nhiên là cùng ciphertext: cipher.txt
Ý tưởng của bài thì cũng không gì quá phức tạp, đơn giản như này thôi:
Plaintext --> chia thành các chunk[i:i+32] --> (to_int(chunk) + lamda)³ mod N = ciphertext
Rõ ràng thì đề bài ra thì đây là một bài về RSA với N không quá lớn và e rất nhỏ ( có thể nói là vô vùng nhỏ cũng đc ).
Theo thói quen thì RSA thì nghĩ tới ngay Prime Factorization, thử với factordb cái nhẹ:
Không factor đc, và thường thì bih sẽ chả ai cho cái N dễ đến như thế :v, cơ mà đời mà, nhỡ đầu trời thương kẻ bất lương :v.
Nghĩ ngợi vẽ vời 1 lúc, mới chợt nghĩ ra 1 lỗi cơ bản của RSA với e rất bé, cụ thể trong bài là e = 3.
What if m³ < N, ==> m³ mod N = m³ ==> m = cuberoot(ciphertext)
Thử ngay với đoạn ciphertext đầu tiên:
và kết quả đúng như mong đợi, có ngay chunk đầu tiên của plaintext:
What I’m trying to say here is..
Có thể khẳng định hướng đi là đúng, vậy chúng ta có thể lặp đi lặp lại bước này cho tới khi hết ciphertext và thu được plaintext. Tuy nhiên trong khi giải, các trường hợp đằng sau không đơn giản như vậy làm mình rất tốn thời gian ngồi debug và lại tiếp tục vẽ vời, mình suy nghĩ như này:
M³ mod N = C --> M³ = k*N + C
Có thể với sự "vô ý" của tác giả, trường hợp đầu tiên rơi trúng ngay k=0. Mà tác giả đã "vô ý" như thế này, khả năng rất cao là k trong bài này nhỏ, đủ để chúng ta bruteforce.
Cụ thể hóa lời nói bằng hành động cho nó sợ:
PLAINTEXT: What I’m trying to say here is… sometimes that *thing* you’re searching for your whole life… is right there by your side all along. The flag is {Old_RSA_close_factor_problem}. And you don’t even know it.
Bingo, đúng hướng tác giả ra đề luôn, cầm flag và chạy đi submit kiếm ngay 100pts, khệnh khạng ngồi lên top 6 dù chỉ được 1 tiếng đồng hồ. Cơ mà đời mà, thà 1 phút huy hoàng còn hơn ngàn năm le lói.
FLAG: SVATTT2017{Old_RSA_close_factor_problem}
P/S: Có thể nhiều người sẽ hỏi là tại sao không viết tiếp vô bài của ToTop, tách ra làm màu câu fame này nọ blah blah...
Cơ mà câu trả lời là méo, méo baoh vì nó viết sai tên mình =.=, h3xX0r, who dafuq is hexor ToT.
--Thanks you for ur attention--
Author: H3xX0r
