Binary here!

Lưu ý khi submit:

nếu tìm được cờ có dạng matesctf{flag} thì hãy submit matesctf{lowercase(sha1(flag))}

Mở file text đề cho lên thấy được các bộ (e,n,c), đoán được ngay là flag đã được mã hóa RSA.

Tổng cộng có 128 bộ.Nếu để ý sẽ thấy có vài n trùng nhau, viết 1 đọan code nhỏ để kiểm tra thì thấy chỉ có tất cả 64 số n,ứng với mỗi n là 2 bộ.

Xét với 2 bộ ngẫu nhiên có cùng số n:

C1=m^e1  (mod n)

==> C1^a=(m^e1)^a     (mod n)

==>C1^a=m^(a*e1)       (mod n)           (1)

C2=m^e2 (mod n)

==>C2^a=m^(a*e2)       (mod n)          (2)

với m là flag và n=n1=n2.

Đem nhân phương trình (1) và (2) ta được:

C1^a*C2^b=m^(a*e1) * m^(a*e2)     (mod n)

==> C1^a*C2^b=m^(a*e1+b*e2)   (mod n)

Nhận xét: Nếu (a*e1+b*e2)=1 thì phương trình sẽ trở thành:

C1^a*C2^b=m   (mod n)

Tới đây thì khá đơn giản để tính m vì C1, C2, n đã biết trước.Vấn đề bây giờ là tìm ra a và b để a*e1+b*e2=1

Theo giải thuật Euclid mở rộng thì luôn tìm được a và b để phương trình a*e1+b*e2=1 có nghiệm nguyên nếu e1 và e2 là 2 số nguyên tố cùng nhau (UCLN(e1,e2)=1).

Tiếp theo chúng ta sẽ kiểm tra xem trong những bộ đã cho có những bộ nào thỏa 2 điều kiện

-Có cùng n

-2 số mũ nguyên tố cùng nhau

Code thôi.Khá đơn giản.Ở đây mình sẽ code bằng SAGE vì nó có khả năng tính toán mạnh và đơn giản vì nó có sẵn hàm xgcd :D.Hàm xgcd sẽ trả về 3 gía trị là UCLN(e1,e2), a, b. Code và kết qủa ở đây

2 bộ chúng ta cần tìm ở vị trí 31 và 99.Việc còn lại bây giờ là tính ra m.Đúng ra bài này chúng ta phải bruteforce len(m) nhưng trong hint BTC đã cho len(m)=9+128 nên k cần phải bruteforce. 😀

Ta tìm được flag là:

matesctf{C0mM0n_m0du1U3_+@tTAck_+_pR0b13mQzBtTTBuX20wZHUxVTNfK0B0VEFja18rX3BSMGIxM20=C0mM0n_m0du1U3_+%40tTAck_+_pR0b13m43306D4D306E5F6D3}

Sau khi SHA1 sẽ được matesctf{59c664d5911a8e810696dddfd3d77de354da64da}

Ngoài ra có 1 cách khác đơn giản hơn để tính được flag mà không cần tìm k:

😥