Yêu cầu:

-Tạo chữ ký cho 1 message cho trước, m = “Without The Jedi, There Can Be No Balance In The Force.”

Dữ liệu:

-Một file gồm các dòng có cấu trúc {N, e, sig}, file Resistance.txt : link

 Hình thức submit:

matesctf{ 70 kí tự cuối cùng của chữ ký}

Xem nào, đề cho hơn 1000 sig bao gồm (N, e, sig).Tuy nhiên, để ý thì ta thấy tất cả các sig đều dùng chung n,e tức là tất cả các chữ kí trên đều được kí bằng một khóa duy nhất.

Việc đầu tiên bây giờ là lọc lại dữ liệu chỉ giữ lại các sig cho tiện xử lý (màu mè thôi, khỏi cũng được 😀 😀 )

Bây giờ chúng ta chú ý đến công thức tạo sig.

sig1 = m1^d    (mod N)   (1)

sig2 = m2^d   (mod N)   (2)

Đem nhân (1) và (2) ta có:

sig1*sig2=(m1*m2 mod N)^d    (mod N)

Với:

mi=sigi^e   (mod N)

Nếu tìm được tập mi,mj,…mk nào đó từ dữ liệu đề cho thỏa mi*mj*…*mk mod N = m hoặc m*mi*…*mj mod N =mk thì ta có thể dễ dàng tạo được chữ kí cho m dựa trên sigi, sigj và sigk

Đem factor m ta được:

m=969457664526644963386491791990085406240528515023155299905536628919618670679378434348506759835876485253945071466552911562690479220014

 =2*3*29*157*179*25854682829*7668098843497148512472180297388255767421045885182110878907906635727943153295999098515175881989802106263953029194003

Dễ dàng tìm được:

m372=2

m520=3

m726=29

m630=157

m442-179

m573=198256263500040483955877372275076249936201132660839027678874351967090409761010182646779797271996666869930659725564725073874487

thỏa tích của các số trên bằng m hay nói cách khác ta có tích của các sig tương ứng sẽ là sig của m:

sig=(sig372*sig442*sig520*sig573*sig630*sig726)   (mod N)

OK tính thôi, qúa đơn giản, ta được sig:

Đề kiu lấy 70 ký tự cuối cùng, ok submit thôi:

matesctf{7389414647091786236068498333699980659901331179129675515686928818905130}

Wrong!!!!! WTF? Are you kidding me?

Khoan đã, “70 ký tự”.Hex chăng? Thử lại nào

matesctf{ebf5b1031e1a2df05ac548447f8ba2bbf273c2807d4bb82c3145d9495d1cc7e5dc202a}

OK 200points! 😀 😀