這裡是接著上一篇 PicoCTF write up - Cryptography (密碼學篇 - 上) 繼續寫，由於上一篇的內容在不知不覺間越寫越多，為免篇幅過大，我決定分成上、下兩篇。
la cifra de (200 points)
I found this cipher in an old book. Can you figure out what it says? Connect with nc jupiter.challenges.picoctf.org 58295.
Hints 1 : There are tools that make this easy.
Hints 2 : Perhaps looking at history will help
知識點 : 維吉尼亞密碼 (Vigenère cipher)
先用 nc 連線到伺服器去，domain 是 jupiter.challenges.picoctf.org ， port 是 58295
$ nc jupiter.challenges.picoctf.org 58295
Encrypted message:
Ne iy nytkwpsznyg nth it mtsztcy vjzprj zfzjy rkhpibj nrkitt ltc tnnygy ysee itd tte cxjltk
Ifrosr tnj noawde uk siyyzre, yse Bnretèwp Cousex mls hjpn xjtnbjytki xatd eisjd
Iz bls lfwskqj azycihzeej yz Brftsk ip Volpnèxj ls oy hay tcimnyarqj dkxnrogpd os 1553 my Mnzvgs Mazytszf Merqlsu ny hox moup Wa inqrg ipl. Ynr. Gotgat Gltzndtg Gplrfdo
Ltc tnj tmvqpmkseaznzn uk ehox nivmpr g ylbrj ts ltcmki my yqtdosr tnj wocjc hgqq ol fy oxitngwj arusahje fuw ln guaaxjytrd catizm tzxbkw zf vqlckx hizm ceyupcz yz tnj fpvjc hgqqpohzCZK{m311a50_0x_a1rn3x3_h1ah3xf966878l}
Tnj qixxe wkqw-duhfmkseej ipsiwtpznzn uk l puqjarusahjeii htpnjc hubpvkw, hay rldk fcoaso 1467 be Qpot Gltzndtg Fwbkwei.
Zmp Volpnèxj Nivmpr ox ehkwpfuwp surptorps ifwlki ehk Fwbkwei Jndc uw Llhjcto Htpnjc.
It 1508, Ozhgsyey Ycizmpmozd itapnzjo tnj do-ifwlki eahzwa xjntg (f xazwtx uk dhokeej fwpnfmezx) ehgy hoaqo lgypr hj l cxneiifw curaotjyt uk ehk Atgksèce Inahkw.
Merqlsu’x deityd htzkrje avupaxjo it 1555 fd a itytosfaznzn uk ehk ktryy. Ehk qzwkw saraps uk ehk fwpnfmezx lrk szw ymtfzjo rklflgwwy, hze tnj llvmlbkyd ati ehk nydkc wezypry fce sniej gj mkfys uk l mtjxotnn kkd ahxfde, cmtcn hln hj oilkprkse woys eghs cuwceyuznjjyt.
嘗試養成一個駭客觸覺，如果看到一篇類似”文章”的東西但經過加密，十有八九離不開 維吉尼亞密碼，因為解密的過程，需要對每個字母的出現的頻率進行統計，還有能否組合出常用字彙等分析。所以通常給出的密文都足夠長。
這裡也有我之前解維吉尼亞密碼的思路過程，這個加密法搞懂了之後會很有意思。
再來就是利用線上網站進行解密。
特別要注意，解維吉尼亞密碼之前，最好先把密文處理成只剩英文字母，這樣比較不會在解密過程遇到 bug
解密後會得到 2 項資訊
- 當初加密時用到的 key
- 明文
而這題解密後的 key 是 flag
明文 :
It is interesting how in history people often receive credit for things they did not create
During the course of history, the Vigenère Cipher has been reinvented many times
It was falsely attributed to Blaise de Vigenère as it was originally described in 1553 by Giovan Battista Bellaso in his book La cifra del. Sig. Giovan Battista Bellaso
For the implementation of this cipher a table is formed by sliding the lower half of an ordinary alphabet for an apparently random number of places with respect to the upper halfpicoCTF{b311a50_0r_v1gn3r3_c1ph3ra966878a}
The first well-documented description of a polyalphabetic cipher however, was made around 1467 by Leon Battista Alberti.
The Vigenère Cipher is therefore sometimes called the Alberti Disc or Alberti Cipher.
In 1508, Johannes Trithemius invented the so-called tabula recta (a matrix of shifted alphabets) that would later be a critical component of the Vigenère Cipher.
Bellaso’s second booklet appeared in 1555 as a continuation of the first. The lower halves of the alphabets are now shifted regularly, but the alphabets and the index letters are mixed by means of a mnemonic key phrase, which can be different with each correspondent.
Tapping (200 points)
Theres tapping coming in from the wires. What’s it saying nc jupiter.challenges.picoctf.org 9422.
Hints 1 : What kind of encoding uses dashes and dots?
Hints 2 : The flag is in the format PICOCTF{}
$ nc jupiter.challenges.picoctf.org 9422
.--. .. -.-. --- -.-. - ..-. { -- ----- .-. ... ...-- -.-. ----- -.. ...-- .---- ... ..-. ..- -. ..--- -.... ---.. ...-- ---.. ..--- ....- -.... .---- ----- }
知識點 : 摩斯電碼(Morse code)
我用了這個網站解摩斯電碼
不過注意 { 和 } 不屬於摩斯電碼
得 flag PICOCTF{M0RS3C0D31SFUN2683824610}
Flags (200 points)
What do the flags mean?
Hints : The flag is in the format PICOCTF{}
思路1 : 看起來由很多旗組成的 flag 。
思路2 : 在 { 前面有 7 面旗，應該就是對應 PICOCTF 這 7 個字母
思路3 : 由於有一些旗重覆了，可以推測出以下字母 PICOCTF{F????????T?FF} ，只剩 9 個字母未知。
思路4 : 這些到底是什麼旗呢? 會不會有 26 個不同的旗幟去表示 26 個字母
最終我找到了答案，原來這些旗叫國際信號旗，是一種船隻間的旗幟溝通系統，讓船隻快速清晰地表明自船的意圖。
字母
數字
構成 flag PICOCTF{F1AG5AND5TUFF}
Mr-Worldwide (200 points)
A musician left us a message. What’s it mean?
message :
picoCTF{(35.028309, 135.753082)(46.469391, 30.740883)(39.758949, -84.191605)(41.015137, 28.979530)(24.466667, 54.366669)(3.140853, 101.693207)_(9.005401, 38.763611)(-3.989038, -79.203560)(52.377956, 4.897070)(41.085651, -73.858467)(57.790001, -152.407227)(31.205753, 29.924526)}
思路 1 : 這個看起來是一個地圖坐標
思路 2 : 如果每一個坐標代表一個英文字母，我猜字母會是該地名的第一個字
思路 3 : 試探性的用 google map 搜尋第一個坐標 (35.028309, 135.753082)
地址的全稱是 Nakanocho, Kamigyo Ward, Kyoto, 602-0958, Japan
有可能是街名、亦有可能城市名稱，不過這題只要有耐性就能解
[K]yoto (35.028309, 135.753082)
[O]dessa (46.469391, 30.740883)
[D]ayton (39.758949, -84.191605)
[I]stanbul (41.015137, 28.979530)
[A]bu Dhabi (24.466667, 54.366669)
[K]uala Lumpur (3.140853, 101.693207)
_
[A]ddis Ababa (9.005401, 38.763611)
[L]oja (-3.989038, -79.203560)
[A]msterdam (52.377956, 4.897070)
[S]leepy Hollow (41.085651, -73.858467)
[K]odiak (57.790001, -152.407227)
[A]lexandria (31.205753, 29.924526)
---------------------------------------------
picoCTF{KODIAK_ALASKA}
rsa-pop-quiz (200 points)
Class, take your seats! It’s PRIME-time for a quiz… nc jupiter.challenges.picoctf.org 18821
Hints : RSA info
知識點 : RSA 非對稱加密法
PS : 一直以來我沒弄清楚 RSA，就是一道題讓我重新認識了 RSA，相信我，請在這道題上花一些時間，細細品嚐，你除了會發現它蘊含了數學的美妙，再回過頭來才發現 RSA 其實並沒想像中的高深艱澀，難度定在只需花一個晚上就能學習個大概。
知識點同場加映 李永樂老師 11 分鐘講 RSA 加密算法
連線後，會連續問好幾題有關於 RSA 的計算問題
$ nc jupiter.challenges.picoctf.org 18821
Q1 : 有 q 和 p ，可否求出 n ?
Good morning class! It's me Ms. Adleman-Shamir-Rivest
Today we will be taking a pop quiz, so I hope you studied. Cramming just will not do!
You will need to tell me if each example is possible, given your extensive crypto knowledge.
Inputs and outputs are in decimal. No hex here!
#### NEW PROBLEM ####
q : 60413
p : 76753
##### PRODUCE THE FOLLOWING ####
n
IS THIS POSSIBLE and FEASIBLE? (Y/N):
n = q x p
y
4636878989
Q2 : 有 p 和 n ，可否求出 q ?
#### NEW PROBLEM ####
p : 54269
n : 5051846941
##### PRODUCE THE FOLLOWING ####
q
IS THIS POSSIBLE and FEASIBLE? (Y/N):
q = n / p
y
93089
Q3 : 有 e (公讑) 和 n ，可否求出 q 和 p ?
#### NEW PROBLEM ####
e : 3
n : 12738162802910546503821920886905393316386362759567480839428456525224226445173031635306683726182522494910808518920409019414034814409330094245825749680913204566832337704700165993198897029795786969124232138869784626202501366135975223827287812326250577148625360887698930625504334325804587329905617936581116392784684334664204309771430814449606147221349888320403451637882447709796221706470239625292297988766493746209684880843111138170600039888112404411310974758532603998608057008811836384597579147244737606088756299939654265086899096359070667266167754944587948695842171915048619846282873769413489072243477764350071787327913
##### PRODUCE THE FOLLOWING ####
q
p
IS THIS POSSIBLE and FEASIBLE? (Y/N):
無法，該 n 值沒有可以分解的因數 q 和 p ( 1 和 n 自己不算 )
n
Q4 : 有 q 和 p ，可否求出 totient(n) ?
#### NEW PROBLEM ####
q : 66347
p : 12611
##### PRODUCE THE FOLLOWING ####
totient(n)
IS THIS POSSIBLE and FEASIBLE? (Y/N):
totient(n) = ( q - 1 ) * ( p - 1 )
totient(n) = r = 歐拉函數
y
836623060
Q5 : 有 plaintext (明文)、 e (公讑) 、 n 。可否求出 ciphertext (密文) ?
#### NEW PROBLEM ####
plaintext : 6357294171489311547190987615544575133581967886499484091352661406414044440475205342882841236357665973431462491355089413710392273380203038793241564304774271529108729717
e : 3
n : 29129463609326322559521123136222078780585451208149138547799121083622333250646678767769126248182207478527881025116332742616201890576280859777513414460842754045651093593251726785499360828237897586278068419875517543013545369871704159718105354690802726645710699029936754265654381929650494383622583174075805797766685192325859982797796060391271817578087472948205626257717479858369754502615173773514087437504532994142632207906501079835037052797306690891600559321673928943158514646572885986881016569647357891598545880304236145548059520898133142087545369179876065657214225826997676844000054327141666320553082128424707948750331
##### PRODUCE THE FOLLOWING ####
ciphertext
IS THIS POSSIBLE and FEASIBLE? (Y/N):
ciphertext 等於 plaintext 的 e 次方，再除以 n ，剩下的餘數
y
256931246631782714357241556582441991993437399854161372646318659020994329843524306570818293602492485385337029697819837182169818816821461486018802894936801257629375428544752970630870631166355711254848465862207765051226282541748174535990314552471546936536330397892907207943448897073772015986097770443616540466471245438117157152783246654401668267323136450122287983612851171545784168132230208726238881861407976917850248110805724300421712827401063963117423718797887144760360749619552577176382615108244813
Q6 : 有 ciphertext (密文)、 e (公讑) 、 n 。可否求出 plaintext (明文) ?
#### NEW PROBLEM ####
ciphertext : 107524013451079348539944510756143604203925717262185033799328445011792760545528944993719783392542163428637172323512252624567111110666168664743115203791510985709942366609626436995887781674651272233566303814979677507101168587739375699009734588985482369702634499544891509228440194615376339573685285125730286623323
e : 3
n : 27566996291508213932419371385141522859343226560050921196294761870500846140132385080994630946107675330189606021165260590147068785820203600882092467797813519434652632126061353583124063944373336654246386074125394368479677295167494332556053947231141336142392086767742035970752738056297057898704112912616565299451359791548536846025854378347423520104947907334451056339439706623069503088916316369813499705073573777577169392401411708920615574908593784282546154486446779246790294398198854547069593987224578333683144886242572837465834139561122101527973799583927411936200068176539747586449939559180772690007261562703222558103359
##### PRODUCE THE FOLLOWING ####
plaintext
IS THIS POSSIBLE and FEASIBLE? (Y/N):
plaintext 等於 ciphertext 的 d 次方，再除以 n ，剩下的餘數
而 d (私讑) 是來自於 e 乘 d 再除以 r 的餘數為 1
而 r (歐拉函數) 是等於 ( p- 1 ) * ( q - 1 )
該題無法，該 n 值沒有可以分解的因數 q 和 p ( 1 和 n 自己不算 )
n
Q7 : 有 q 、 p 、 e (公讑)。 可否求出 d (私讑) ?
#### NEW PROBLEM ####
q : 92092076805892533739724722602668675840671093008520241548191914215399824020372076186460768206814914423802230398410980218741906960527104568970225804374404612617736579286959865287226538692911376507934256844456333236362669879347073756238894784951597211105734179388300051579994253565459304743059533646753003894559
p : 97846775312392801037224396977012615848433199640105786119757047098757998273009741128821931277074555731813289423891389911801250326299324018557072727051765547115514791337578758859803890173153277252326496062476389498019821358465433398338364421624871010292162533041884897182597065662521825095949253625730631876637
e : 65537
##### PRODUCE THE FOLLOWING ####
d
IS THIS POSSIBLE and FEASIBLE? (Y/N):
有 p 和 q 可以求出 r (歐拉函數)
有 r (歐拉函數) 可以解出 e (公讑) 和 d (私讑)
寫成數學式子的話 e * d = r * k + 1
所以在解出 d 之前，先把 k 給找出
我用笨辦法把 k 窮舉出來
while True:
if(r*k+1)%e == 0: #k = 1,2,3..直到餘數為 0
break
k+=1
print(k)
d = (r * k + 1) / e
y
1405046269503207469140791548403639533127416416214210694972085079171787580463776820425965898174272870486015739516125786182821637006600742140682552321645503743280670839819078749092730110549881891271317396450158021688253989767145578723458252769465545504142139663476747479225923933192421405464414574786272963741656223941750084051228611576708609346787101088759062724389874160693008783334605903142528824559223515203978707969795087506678894006628296743079886244349469131831225757926844843554897638786146036869572653204735650843186722732736888918789379054050122205253165705085538743651258400390580971043144644984654914856729
Q8 : 有 p 、 ciphertext (密文) 、 e (公讑) 、 n 。可否求出 plaintext(明文) ?
#### NEW PROBLEM ####
p : 153143042272527868798412612417204434156935146874282990942386694020462861918068684561281763577034706600608387699148071015194725533394126069826857182428660427818277378724977554365910231524827258160904493774748749088477328204812171935987088715261127321911849092207070653272176072509933245978935455542420691737433
ciphertext : 13433290949680532374013867441263154634705815037382789341947905025573905974395028146503162155477260989520870175638250366834087929309236841056522311567941474209163559687755762232926539910909326834168973560610986090744435081572047926364479629414399701920441091626046861493465214197526650146669009590360242375313096062285541413327190041808752295242278877995930751460977420696964385608409717277431821765402461515639686537904799084682553530460611519251872463837425068958992042166507373556839377045616866221238932332390930404993242351071392965945718308504231468783743378794612151028803489143522912976113314577732444166162766
e : 65537
n : 23952937352643527451379227516428377705004894508566304313177880191662177061878993798938496818120987817049538365206671401938265663712351239785237507341311858383628932183083145614696585411921662992078376103990806989257289472590902167457302888198293135333083734504191910953238278860923153746261500759411620299864395158783509535039259714359526738924736952759753503357614939203434092075676169179112452620687731670534906069845965633455748606649062394293289967059348143206600765820021392608270528856238306849191113241355842396325210132358046616312901337987464473799040762271876389031455051640937681745409057246190498795697239
##### PRODUCE THE FOLLOWING ####
plaintext
IS THIS POSSIBLE and FEASIBLE? (Y/N):
從結論說起，答案是可行，RSA 的安全性建立於難以對一個大數 n 因式分解以得到兩個大質數 p , q 。
基本可以總結成，只要求得有 p , q ，就等於破解了 RSA 密碼。
這邊我記錄一下原始數學下的 python 方法，沒有使用 library。
下面基本是一步步的求出 q 、 r (歐拉函數)、 d (私讑) 、 然後 plaintext (明文)。
p = 153143042272527868798412612417204434156935146874282990942386694020462861918068684561281763577034706600608387699148071015194725533394126069826857182428660427818277378724977554365910231524827258160904493774748749088477328204812171935987088715261127321911849092207070653272176072509933245978935455542420691737433
ciphertext = 13433290949680532374013867441263154634705815037382789341947905025573905974395028146503162155477260989520870175638250366834087929309236841056522311567941474209163559687755762232926539910909326834168973560610986090744435081572047926364479629414399701920441091626046861493465214197526650146669009590360242375313096062285541413327190041808752295242278877995930751460977420696964385608409717277431821765402461515639686537904799084682553530460611519251872463837425068958992042166507373556839377045616866221238932332390930404993242351071392965945718308504231468783743378794612151028803489143522912976113314577732444166162766
e = 65537
n = 23952937352643527451379227516428377705004894508566304313177880191662177061878993798938496818120987817049538365206671401938265663712351239785237507341311858383628932183083145614696585411921662992078376103990806989257289472590902167457302888198293135333083734504191910953238278860923153746261500759411620299864395158783509535039259714359526738924736952759753503357614939203434092075676169179112452620687731670534906069845965633455748606649062394293289967059348143206600765820021392608270528856238306849191113241355842396325210132358046616312901337987464473799040762271876389031455051640937681745409057246190498795697239
q = n // p
print("q = ",q)
r = (q - 1) * (p - 1)
print("r = ",r)
k = 1
while True: #窮舉出 k ，讓 ed = kr + 1 等式成立
if(r * k + 1) % e == 0:
break
k += 1
print("k = ",k)
d = (r * k + 1) // e
print("d = ",d)
plaintext = pow(ciphertext,d,n)
print("plaintext = ",plaintext)
y
14311663942709674867122208214901970650496788151239520971623411712977120527163003942343369341
Q9 : 解讀明文
If you convert the last plaintext to a hex number, then ascii, you'll find what you need! ;)
明文 (十進位) :
14311663942709674867122208214901970650496788151239520971623411712977120527163003942343369341
明文 (十六進位) :
7069636F4354467B7741385F74683474245F696C6C336147616C2E2E6F61326432323339627D
明文 (ASCII) :
picoCTF{wA8_th4t$_ill3aGal..oa2d2239b}
college-rowing-team (250 points)
I just joined my college’s rowing team! To make a good first impression, I started sending my teammates positive automated messages every day. I even send them flags from time to time! encrypted-messages.txt encrypt.py
encrypted-messages.txt:
n: 12426348204210593270343924563278821305386892683425418957350363905840484905896816630189546938112358425679727243103082954824537007026886458498690134225705484501535835385800730412220192564706251228021192115494699150390312107794005569764411063907390563937247515046052549753641884721864426154021041082461015103337120756347692245843318676049947569653604616584167536958803278688355036036887022591104659059883622072052793378468850702811804337808760402077376453702190206077039468600466511349923882037572540505571672225260106649075841827340894515208811788428239691505001675042096850318994923571686175381862745049100863883977473
e: 3
c: 5065488652323342174251548936130018278628515304559137485528400780060697119682927936946069625772269234638180036633146283242714689277793018059046463458498115311853401434289264038408827377579534270489217094049453933816452196508276029690068611901872786195723358744119490651499187556193711866091991489262948739533990000464588752544599393
n: 19928073532667002674271126242460424264678302463110874370548818138542019092428748404842979311103440183470341730391245820461360581989271804887458051852613435204857098017249255006951581790650329570721461311276897625064269097611296994752278236116594018565111511706468113995740555227723579333780825133947488456834006391113674719045468317242000478209048237262125983164844808938206933531765230386987211125968246026721916610034981306385276396371953013685639581894384852327010462345466019070637326891690322855254242653309376909918630162231006323084408189767751387637751885504520154800908122596020421247199812233589471220112129
e: 3
c: 86893891006724995283854813014390877172735163869036169496565461737741926829273252426484138905500712279566881578262823696620415864916590651557711035982810690227377784525466265776922625254135896966472905776613722370871107640819140591627040592402867504449339363559108090452141753194477174987394954897424151839006206598186417617292433784471465084923195909989
n: 13985338100073848499962346750699011512326742990711979583786294844886470425669389469764474043289963969088280475141324734604981276497038537100708836322845411656572006418427866013918729379798636491260028396348617844015862841979175195453570117422353716544166507768864242921758225721278003979256590348823935697123804897560450268775282548700587951487598672539626282196784513553910086002350034101793371250490240347953205377022300063974640289625028728548078378424148385027286992809999596692826238954331923568004396053037776447946561133762767800447991022277806874834150264326754308297071271019402461938938062378926442519736239
e: 3
c: 86893891006724995283854813014390877172735163869036169496565461737741926829273252426484138905500712279566881578262823696620415864916590651557711035982810690227377784525466265776922625254135896966472905776613722370871107640819140591627040592402867504449339363559108090452141753194477174987394954897424151839006206598186417617292433784471465084923195909989
n: 19594695114938628314229388830603768544844132388459850777761001630275366893884362012318651705573995962720323983057152055387059580452986042765567426880931775302981922724052340073927578619711314305880220746467095847890382386552455126586101506301413099830377279091457182155755872971840333906012240683526684419808580343325425793078160255607072901213979561554799496270708954359438916048029174155327818898336335540262711330304350220907460431976899556849537752397478305745520053275803008830388002531739866400985634978857874446527750647566158509254171939570515941307939440401043123899494711660946335200589223377770449028735883
e: 3
c: 5065488652323342174251548936130018278628515304559137485528400780060697119682927936946069625772269234638180036633146283242714689277793018059046463458498115311853401434289264038408827377579534270489217094049453933816452196508276029690068611901872786195723358744119490651499187556193711866091991489262948739533990000464588752544599393
n: 12091176521446155371204073404889525876314588332922377487429571547758084816238235861014745356614376156383931349803571788181930149440902327788407963355833344633600023056350033929156610144317430277928585033022575359124565125831690297194603671159111264262415101279175084559556136660680378784536991429981314493539364539693532779328875047664128106745970757842693549568630897393185902686036462324740537748985174226434204877493901859632719320905214814513984041502139355907636120026375145132423688329342458126031078786420472123904754125728860419063694343614392723677636114665080333174626159191829467627600232520864728015961207
e: 3
c: 301927034179130315172951479434750678833634853032331571873622664841337454556713005601858152523700291841415874274186191308636935232309742600657257783870282807784519336918511713958804608229440141151963841588389502276162366733982719267670094167338480873020791643860930493832853048467543729024717103511475500012196697609001154401
n: 19121666910896626046955740146145445167107966318588247850703213187413786998275793199086039214034176975548304646377239346659251146907978120368785564098586810434787236158559918254406674657325596697756783544837638305550511428490013226728316473496958326626971971356583273462837171624519736741863228128961806679762818157523548909347743452236866043900099524145710863666750741485246383193807923839936945961137020344124667295617255208668901346925121844295216273758788088883216826744526129511322932544118330627352733356335573936803659208844366689011709371897472708945066317041109550737511825722041213430818433084278617562166603
e: 3
c: 38999477927573480744724357594313956376612559501982863881503907194813646795174312444340693051072410232762895994061399222849450325021561935979706475527169503326744567478138877010606365500800690273
n: 13418736740762596973104019538568029846047274590543735090579226390035444037972048475994990493901009703925021840496230977791241064367082248745077884860140229573097744846674464511874248586781278724368902508880232550363196125332007334060198960815141256160428342285352881398476991478501510315021684774636980366078533981139486237599681094475934234215605394201283718335229148367719703118256598858595776777681347337593280391052515991784851827621657319164805164988688658013761897959597961647960373018373955633439309271548748272976729429847477342667875183958981069315601906664672096776841682438185369260273501519542893405128843
e: 3
c: 38999477927573480744724357594313956376612559501982863881503907194813646795174312444340693051072410232762895994061399222849450325021561935979706475527169503326744567478138877010606365500800690273
n: 11464859840071386874187998795181332312728074122716799062981080421188915868236220735190397594058648588181928124991332518259177909372407829352545954794824083851124711687829216475448282589408362385114764290346196664002188337713751542277587753067638161636766297892811393667196988094100002752743054021009539962054210885806506140497869746682404059274443570436700825435628817817426475943873865847012459799284263343211713809567841907491474908123827229392305117614651611218712810815944801398564599148842933378612548977451706147596637225675719651726550873391280782279097513569748332831819616926344025355682272270297510077861213
e: 3
c: 38999477927573480744724357594313956376612559501982863881503907194813646795174312444340693051072410232762895994061399222849450325021561935979706475527169503326744567478138877010606365500800690273
n: 21079224330416020275858215994125438409920350750828528428653429418050688406373438072692061033602698683604056177670991486330201941071320198633550189417515090152728909334196025991131427459901311579710493651699048138078456234816053539436726503461851093677741327645208285078711019158565296646858341000160387962592778531522953839934806024839570625179579537606629110275080930433458691144426869886809362780063401674963129711723354189327628731665487157177939180982782708601880309816267314061257447780050575935843160596133370063252618488779123249496279022306973156821343257109347328064771311662968182821013519854248157720756807
e: 3
c: 301927034179130315172951479434750678833634853032331571873622664841337454556713005601858152523700291841415874274186191308636935232309742600657257783870282807784519336918511713958804608229440141151963841588389502276162366733982719267670094167338480873020791643860930493832853048467543729024717103511475500012196697609001154401
n: 22748076750931308662769068253035543469890821090685595609386711982925559973042348231161108618506912807763679729371432513862439311860465982816329852242689917043600909866228033526990181831690460395726449921264612636634984917361596257010708960150801970337017805161196692131098507198455206977607347463663083559561805065823088182032466514286002822511854823747204286303638719961067031142962653536148315879123067183501832837303731109779836127520626791254669462630052241934836308543513534520718206756591694480011760892620054163997231711364648699030108110266218981661196887739673466188945869132403569916138510676165684240183111
e: 3
c: 5065488652323342174251548936130018278628515304559137485528400780060697119682927936946069625772269234638180036633146283242714689277793018059046463458498115311853401434289264038408827377579534270489217094049453933816452196508276029690068611901872786195723358744119490651499187556193711866091991489262948739533990000464588752544599393
n: 15211900116336803732344592760922834443004765970450412208051966274826597749339532765578227573197330047059803101270880541680131550958687802954888961705393956657868884907645785512376642155308131397402701603803647441382916842882492267325851662873923175266777876985133649576647380094088801184772276271073029416994360658165050186847216039014659638983362906789271549086709185037174653379771757424215077386429302561993072709052028024252377809234900540361220738390360903961813364846209443618751828783578017709045913739617558501570814103979018207946181754875575107735276643521299439085628980402142940293152962612204167653199743
e: 3
c: 301927034179130315172951479434750678833634853032331571873622664841337454556713005601858152523700291841415874274186191308636935232309742600657257783870282807784519336918511713958804608229440141151963841588389502276162366733982719267670094167338480873020791643860930493832853048467543729024717103511475500012196697609001154401
n: 21920948973299458738045404295160882862610665825700737053514340871547874723791019039542757481917797517039141169591479170760066013081713286922088845787806782581624491712703646267369882590955000373469325726427872935253365913397944180186654880845126957303205539301069768887632145154046359203259250404468218889221182463744409114758635646234714383982460599605335789047488578641238793390948534816976338377433533003184622991479234157434691635609833437336353417201442828968447500119160169653140572098207587349003837774078136718264889636544528530809416097955593693611757015411563969513158773239516267786736491123281163075118193
e: 3
c: 86893891006724995283854813014390877172735163869036169496565461737741926829273252426484138905500712279566881578262823696620415864916590651557711035982810690227377784525466265776922625254135896966472905776613722370871107640819140591627040592402867504449339363559108090452141753194477174987394954897424151839006206598186417617292433784471465084923195909989
encrypt.py:
#!/usr/bin/env python3
import random
from Crypto.Util.number import getPrime, bytes_to_long
with open('flag.txt', 'rb') as f:
flag = f.read()
msgs = [
b'I just cannot wait for rowing practice today!',
b'I hope we win that big rowing match next week!',
b'Rowing is such a fun sport!'
]
msgs.append(flag)
msgs *= 3
random.shuffle(msgs)
for msg in msgs:
p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 3
m = bytes_to_long(msg)
c = pow(m, e, n)
with open('encrypted-messages.txt', 'a') as f:
f.write(f'n: {n}\n')
f.write(f'e: {e}\n')
f.write(f'c: {c}\n\n')
分析
題目給了我們 12 組的 [N, e, c] 和原加密用的腳本
msgs.append(flag)
msgs *= 3
random.shuffle(msgs)
msgs 本身含有 3 個句子，加上 flag 後共 4 句，乘 3 後一共有 12 句，再用 shuffle 打亂，因此我們得知 flag 就是這 12 組裡的其中 3 組。
解法
其實這題就是利用 e = 3 (小公鑰/低加密指數攻擊)，雖然我們不知道 flag 在 12 組裡的哪 3 組，但我們可以把 12 組全解出來。
import gmpy2,binascii,libnum,time
with open('encrypted-messages.txt', 'rb') as f:
txt = f.read().split()
txt = txt[1::2]
step = 3
rsa = [txt[i:i+step] for i in range(0,len(txt),step)]
for i in rsa:
n = int(i[0])
e = int(i[1])
c = int(i[2])
res = 0
for k in range(200000000):
if gmpy2.iroot(c+n*k,3)[1]==1:
res=gmpy2.iroot(c+n*k,3)[0]
#print(k,res)
print(libnum.n2s(int(res)))
break
output:
b'I hope we win that big rowing match next week!'
b'picoCTF{1_gu3ss_p30pl3_p4d_m3ss4g3s_f0r_4_r34s0n}'
b'picoCTF{1_gu3ss_p30pl3_p4d_m3ss4g3s_f0r_4_r34s0n}'
b'I hope we win that big rowing match next week!'
b'I just cannot wait for rowing practice today!'
b'Rowing is such a fun sport!'
b'Rowing is such a fun sport!'
b'Rowing is such a fun sport!'
b'I just cannot wait for rowing practice today!'
b'I hope we win that big rowing match next week!'
b'I just cannot wait for rowing practice today!'
b'picoCTF{1_gu3ss_p30pl3_p4d_m3ss4g3s_f0r_4_r34s0n}'
waves over lambda (300 points)
We made a lot of substitutions to encrypt this. Can you decrypt it? Connect with nc jupiter.challenges.picoctf.org 13758.
知識點: 字頻分析
$ nc jupiter.challenges.picoctf.org 13758
這題 netcat 連線後就出現類似下面的”文章”
-------------------------------------------------------------------------------
pfcvudoj qiui zj xfmu yrdv - yuismicpx_zj_p_fkiu_rdglwd_wckoyuodxm
-------------------------------------------------------------------------------
drihix yxfwfufkzopq ndudgdtfk edj oqi oqzuw jfc fy yxfwfu bdkrfkzopq ndudgdtfk, d rdcw feciu eirr ncfec zc fmu wzjouzpo zc qzj fec wdx, dcw jozrr uigigliuiw dgfcv mj fezcv of qzj vrffgx dcw oudvzp widoq, eqzpq qdbbiciw oqzuoiic xiduj dvf, dcw eqzpq z jqdrr wijpuzli zc zoj bufbiu brdpi. yfu oqi buijico z ezrr fcrx jdx oqdo oqzj rdcwfeciuyfu jf ei mjiw of pdrr qzg, droqfmvq qi qduwrx jbico d wdx fy qzj rzyi fc qzj fec ijodoiedj d joudcvi oxbi, xio fci buioox yuismicorx of li gio ezoq, d oxbi dlaipo dcw kzpzfmj dcw do oqi jdgi ozgi jicjirijj. lmo qi edj fci fy oqfji jicjirijj biujfcj eqf dui kiux eirr pdbdlri fy rffnzcv dyoiu oqizu efurwrx dyydzuj, dcw, dbbduicorx, dyoiu cfoqzcv irji. yxfwfu bdkrfkzopq, yfu zcjodcpi, livdc ezoq ciho of cfoqzcv; qzj ijodoi edj fy oqi jgdrrijo; qi udc of wzci do foqiu gic'j odlrij, dcw ydjoiciw fc oqig dj d ofdwx, xio do qzj widoq zo dbbiduiw oqdo qi qdw d qmcwuiw oqfmjdcw ufmlrij zc qduw pdjq. do oqi jdgi ozgi, qi edj drr qzj rzyi fci fy oqi gfjo jicjirijj, ydcodjozpdr yirrfej zc oqi eqfri wzjouzpo. z uibido, zo edj cfo jombzwzoxoqi gdafuzox fy oqiji ydcodjozpdr yirrfej dui jquiew dcw zcoirrzvico icfmvqlmo amjo jicjirijjcijj, dcw d bipmrzdu cdozfcdr yfug fy zo.
多做幾次的 netcat 可以發現雖然”文章”每次都不同，但格式和架構幾乎一樣，所以可以確定是字母被替換了，這時候只需要一個字頻分析的網站 quipqiup 就能還原看到”原文章”
miniRSA (300 points)
Let’s decrypt this: ciphertext? Something seems a bit small.
hint 1 : RSA tutorial
hint 2 : How could having too small an e affect the security of this 2048 bit key?
hint 3 : Make sure you don’t lose precision, the numbers are pretty big (besides the e value)
解法
這題和前面的 Mini RSA (70 points) 一樣的解法，都是利用 e = 3 的漏洞，所以這邊不再贅述。
import gmpy2,binascii,libnum,time
n = 29331922499794985782735976045591164936683059380558950386560160105740343201513369939006307531165922708949619162698623675349030430859547825708994708321803705309459438099340427770580064400911431856656901982789948285309956111848686906152664473350940486507451771223435835260168971210087470894448460745593956840586530527915802541450092946574694809584880896601317519794442862977471129319781313161842056501715040555964011899589002863730868679527184420789010551475067862907739054966183120621407246398518098981106431219207697870293412176440482900183550467375190239898455201170831410460483829448603477361305838743852756938687673
e = 3
c = 2205316413931134031074603746928247799030155221252519872649649212867614751848436763801274360463406171277838056821437115883619169702963504606017565783537203207707757768473109845162808575425972525116337319108047893250549462147185741761825125
res = 0
for k in range(200000000):
if gmpy2.iroot(c+n*k,3)[1]==1:
res=gmpy2.iroot(c+n*k,3)[0]
print(k,res)
print(libnum.n2s(int(res)))
break
It’s Not My Fault 1 (300 points)
What do you mean RSA with CRT has an attack that’s not a fault attack? Connect with nc mercury.picoctf.net 41175. not_my_fault.py
not_my_fault.py:
#!/usr/bin/python3 -u
import random
import string
import hashlib
import time
from Crypto.Util.number import inverse, getPrime, bytes_to_long, GCD
from sympy.ntheory.modular import solve_congruence
FLAG = open('flag.txt', 'r').read()
def CRT(a, m, b, n):
val, mod = solve_congruence((a, m), (b, n))
return val
def gen_key():
while True:
p = getPrime(512)
q = getPrime(512)
if GCD(p-1, q-1) == 2:
return p, q
def get_clue(p, q, BITS):
while True:
d_p = random.randint(1, 1 << BITS)
d_q = random.randint(1, q - 1)
if d_p % 2 == d_q % 2:
d = CRT(d_p, p - 1, d_q, q - 1)
e = inverse(d, (p - 1) * (q - 1))
print("Clue : ", e)
return
def get_flag(p, q):
start = time.time()
ans = int(input())
if (time.time() - start) > (15 * 60):
print("Too long!")
exit()
else:
if ans == p + q:
print(FLAG)
else:
print("oops...")
#PoW
vals1 = "".join([random.choice(string.digits) for _ in range(5)])
vals2 = "".join([random.choice(string.hexdigits.lower()) for _ in range(6)])
user_input = input("Enter a string that starts with \"{}\" (no quotes) which creates an md5 hash that ends in these six hex digits: {}\n".format(vals1, vals2))
user_hash = hashlib.md5(user_input.encode()).hexdigest()
if user_input[:5] == vals1 and user_hash[-6:] == vals2:
p, q = gen_key()
n = p * q
print("Public Modulus : ", n)
get_clue(p, q, 20)
get_flag(p, q)
解法
這題其實就是兩道題:
一、
第一個是解 MD5，給定前 5 個數字的字串，MD5 轉換後符合最後的 6 個字元。
例如 : md5(07668 + ???) = ??? + 1aaf82
md5(0766811799207) -> 7ecf1a5593e93049207f80fde51aaf82
就是暴力解而已。
二、
解出第一題後，題目會給出 n 和 e 的值，還有 $d_p < 2^{20}$ 這兩項提示，讓我們求出 p + q 的值
我在這一個部分卡關超級久，以目前的數學程式是無法理解是如何做的，所以這邊直接說方法。
先說什麼是 $d_p$
$d_p \equiv d \text{ } mod (p-1)$
主要目的是為了加速中國餘數定理運算速度。
由於
$x^{ed_p} \equiv x \text{ } (mod \text{ } p)$
x 的範圍在 [1 , N] 之間隨機選擇
所以
$x^{ed_p} = kp + x$
$kp = x^{ed_p} - x$
由於我們知道 $k * p$ 和 $p * q$ 的最大公因數一定是 $p$
$p = gcd(k * p, p * q)$
所以
$p = gcd(k*p, N)$
得
$p = gcd(x ^ {e*d_p} - x , N)$
也就是說，我弄出一個隨機數 x，有很高機率(實際跑也有找不到的可能)可以找出 $d_p$ 以滿足上面的算式，從而算出 p
$d_p$ 就在 2 至 $2^{20}$ 暴力解便可
from pwn import *
import gmpy2
import random
import time
def solve_pow(prefix,suffix):
iters = 0
while 1:
s = prefix + str(iters)
s = s.encode('utf-8')
hashed_s = hashlib.md5(s).hexdigest()
iters = iters + 1
#print("s =",s)
#print("hasheed_s =",hashed_s)
r = re.match('^[a-z0-9]{26}'+suffix, hashed_s)
if r:
print("[+] found! md5( {} ) ---> {}".format(s, hashed_s))
print("[+] in {} iterations".format(iters))
#exit(0)
break
if iters % 1000000 == 0:
print("[+] current value: {} {} iterations, continue...".format(s, iters))
return s
def find_p(e, n):
BITS = 20
x = random.randint(2, n // 2)
t = time.time()
for i in range(1, 1 << BITS):
if i % (1048576 // 20) == 0:
print(f"[+] progress: {i/1048576*100}%")
p = gmpy2.gcd((gmpy2.powmod(x, i*e, n) - x) % n, n)
if p != 1:
print("[+] done!")
print(f"[+] elapsed time: {time.time() - t}s")
return p
print("[-] oops... I couldn't find p")
return -1
conn = remote("mercury.picoctf.net", 41175)
line = conn.recvline().decode().strip()
prefix = line[33:38]
suffix = line[-6:]
print(f"md5({prefix} + ???) = ??? + {suffix}")
s = solve_pow(prefix,suffix)
conn.sendline(s)
print(conn.recvuntil("Public Modulus : "))
n = int(conn.recvline().strip())
print(n)
print(conn.recvuntil("Clue : "))
e = int(conn.recvline().strip())
print(e)
p = find_p(e,n)
q = n // p
conn.sendline(str(p + q))
print(conn.recvline())
conn.interactive()