Dữ kiện đề cho file (do sever đã đóng nên mình tạm lấy file trên mạng)

          Decription: Alice and bob are close together, likely because they have a lot of things in common. This is why Alice asked him a small *q*uestion, about something cooler than a wiener.

          Sau khi extract ra ta thấy có 3 file trong đó có 1 file encrypted, 1 file pub và 1 file zip đã được đặt pass. Ta có thể đoán được đề yêu cầu từ file encrypted và public key ta phải decrypt để có được key dùng cho file zip.

          Dùng openssl để xem trong file pub có gì

openssl rsa -pubin -in almost_almost_almost_almost_there.pub -text

          Ta có:

e=65537

n=9473874079694384096182353069577870140898775728758349266591973

0017973847138345511139064596113422435977583856843887008168202003

8559067080390134873493905718011414072450390115988105422320296345

6484879799853487225154966045427733650283818564293763757612153394

5369150901808833844341421315429263207612372324026271327

          Muốn decrypt được ciphertext thì cần phải có được private key, muốn có được private key thì ta cần phải cố gắng factor được n. Ta biết nếu p và q xấp xỉ bằng nhau và xấp xỉ căn bậc 2 của n hay nói cách khác |p-q| rất nhỏ so với n thì ta có thể brute force để tìm p và q. Bằng 1 đoạn script sage nhỏ ta có thể tính được p và q dễ dàng.

a=int(pow(n,1/2))

if a%2==0:

a+=1

while 1:

if n % a == 0:

print a , “\n” , n/a

break

a+=2

          Tính được p, q ta dễ dàng tìm được d và decrypt được cipher text.

          m=XtCgoEKksjKFWlqOSxqsEhK/+tsr1k5c

         Tìm được key đem extract file .zip ta lại được 3 file tương tự 😦 nhưng tên file thì ngắn hơn.Tương tự như trên dùng openssl để xem n và e. Ta được:

e2=65537

n2=1207117430092199941993878768520527286338218232820016866826373

908528791519744581452678229118497350284847054099950935565562007

942563342817268273622370244365148320932602276326621994849273139

0160090888745608542251360416595926195898999991852624141356869798

0750606419722847183884466865579933961646797811650439499767

          Thử với cách cũ thấy brute force không thành công (qúa lâu), ta tìm cách khác. Ta tính thử GCD(n,n2). Ta thấy GCD này không bằng 1 tức n2 và n một ước chung khác 1, từ 1 ước đã biết của n2 ta có thể tìm ước còn lại của n2 1 cách dễ dàng bằng cách lấy n2 chia cho GCD (n , n2)

p2=973338280337025689313610984097159097146009477924233491943234

780149164161744361585622116861113893357611819679528244350360966316

8324106758595642231987246769

q2=12401828372292379853813876769631673931562555174641979554254424

4580382430586384170652843012668812424330178286638188116065565592

56084249679274024474025282343

         Có p, q ta có thể tính được m tương tự như trên. Ta được:

m2=rlSpJ6HbP+cZXaOuSPOe4pgfevGnXtLt

          Extract ta lại được 3 file, với file .pub ta được:

e3=65537

n3=859765629786054510709140349760823881041588485778835462364954

5462584626186357491015183008751788834205126626170046660764709588

72116943297480465011062429953197177411454325442255841630557883504

090074585678296578526833375040418484176613454408962791730859146

5828618442384534122739386366913053748919149466237339278512341

         Thử với 2 cách ở trên đều không thành công, ta thử factor n với 1 tool online. Bingo! N3 được cấu thành từ 2 số nguyên tố trong đó có 1 số nguyên tố nhỏ nên dễ dàng được factor theo kiểu truyền thống. Ta được:

p3=54311

q3=158304142767773473275973624083670689370769915077762416888835

51145411843247882548682924285599213481992831334665255032617167035

63029484446024681944840695168929272912401402003748488576085661

291616936874073938205017092992285942965838621005705957893853656

06706350802643746830710894411204232176703046334374939501731

         Từ p3, q3 ta được:

m3=hQdK+dKleMJqth/dofWyFaiWp3PW7jil

         Ta lại được 3 file, ban tổ chức ra đề nhây thật 😦 nhưng có vẻ đây là file cuối cùng rồi vì trong file .zip là 1 file mang tên flag 🙂 Hi vọng.

e4=494466786000513792287609062860311555097422398326597057315592

49988210578539211813543612425990507831160407165259046991194935262

2005659538425671487860530404501989197538343973781889325245998400

27093290217612285214105791999673535556558448523448336314401414644

879827127064929878383237432895170442176211946286617205

n4=1096769317767533941413945645147207342367965840228428205076139

45978304098920529412415619708851314423671483225500317195833435789

1744914178718642603750662788855742326532564254342961137739738745

42733322600365156233965235292281146938652303374751525426102732530

711430473466903656428846184387282528950095967567885381

         Ta thấy e4 có đến 1023 bits trong khi n chỉ có 1024 bits – Ta biết với số e càng lớn thì số d sẽ càng nhỏ, và nếu số d nhỏ hơn (n^0.25)/3 thì ta có thể tấn công bằng phương pháp Wiener attack, trên phần mô tả đề bài lại có  đề cập đến Wiener nên cơ hội cao ta đang đi đúng hướng.Viết 1 đoạn code sage nhỏ để tính, ta thu được

p4=10843221374140991753173625949764386011485161421520044246309105

0534895005192579412727966814174970617340540814782805188355823533

21569961722963922828311576983

q4=101147922736606568746185687124064203441762204577905631780922

22929337786916374923318745284718351487926620784106195715878875311

958793629905453919697155685507

         Từ p4, q4 ta được:

m4=/3aAP5dF2zmrPh9K6A4AqMLsIiYDk2C2

         Extract ra ta được flag: BKPCTF{Its_not_you,_its_rsa_(that_is_broken)}