前言

今天繼續來解題，解以下兩題，文章內容也主要是writeup，題目為勒讓德符號跟一點sagemath的使用

Writeup

Legendre Symbol

題目

網址 : https://cryptohack.org/courses/modular/root1/

思路

• 成立時 : d為模p的二次剩餘
• 不成立時 : d為模p的二次非剩餘
  (在此題d以a表示)

題目給了p跟很多個a，題目要我們找出是二次剩餘的a，之後求出比較大的X

解法

可以先利用Legendre's Symbol判斷a是否為二次剩餘

• Legendre's Symbol : (a / p) ≡ a^((p-1)/2) mod p
  

由此可知，如果pow(a,(p-1)//2,p)為1的話，代表a是二次剩餘
因為p = 3 mod 4(題目得知)
上網查後發現

所以pow(quadratic_residues, (p + 1) // 4, p))即可求x的平方根

• code

p = 101524035174539890485408575671085261788758965189060164484385690801466167356667036677932998889725476582421738788500738738503134356158197247473850273565349249573867251280253564698939768700489401960767007716413932851838937641880157263936985954881657889497583485535527613578457628399173971810541670838543309159139
ints = [25081841204695904475894082974192007718642931811040324543182130088804239047149283334700530600468528298920930150221871666297194395061462592781551275161695411167049544771049769000895119729307495913024360169904315078028798025169985966732789207320203861858234048872508633514498384390497048416012928086480326832803, 45471765180330439060504647480621449634904192839383897212809808339619841633826534856109999027962620381874878086991125854247108359699799913776917227058286090426484548349388138935504299609200377899052716663351188664096302672712078508601311725863678223874157861163196340391008634419348573975841578359355931590555, 17364140182001694956465593533200623738590196990236340894554145562517924989208719245429557645254953527658049246737589538280332010533027062477684237933221198639948938784244510469138826808187365678322547992099715229218615475923754896960363138890331502811292427146595752813297603265829581292183917027983351121325, 14388109104985808487337749876058284426747816961971581447380608277949200244660381570568531129775053684256071819837294436069133592772543582735985855506250660938574234958754211349215293281645205354069970790155237033436065434572020652955666855773232074749487007626050323967496732359278657193580493324467258802863, 4379499308310772821004090447650785095356643590411706358119239166662089428685562719233435615196994728767593223519226235062647670077854687031681041462632566890129595506430188602238753450337691441293042716909901692570971955078924699306873191983953501093343423248482960643055943413031768521782634679536276233318, 85256449776780591202928235662805033201684571648990042997557084658000067050672130152734911919581661523957075992761662315262685030115255938352540032297113615687815976039390537716707854569980516690246592112936796917504034711418465442893323439490171095447109457355598873230115172636184525449905022174536414781771, 50576597458517451578431293746926099486388286246142012476814190030935689430726042810458344828563913001012415702876199708216875020997112089693759638454900092580746638631062117961876611545851157613835724635005253792316142379239047654392970415343694657580353333217547079551304961116837545648785312490665576832987, 96868738830341112368094632337476840272563704408573054404213766500407517251810212494515862176356916912627172280446141202661640191237336568731069327906100896178776245311689857997012187599140875912026589672629935267844696976980890380730867520071059572350667913710344648377601017758188404474812654737363275994871, 4881261656846638800623549662943393234361061827128610120046315649707078244180313661063004390750821317096754282796876479695558644108492317407662131441224257537276274962372021273583478509416358764706098471849536036184924640593888902859441388472856822541452041181244337124767666161645827145408781917658423571721, 18237936726367556664171427575475596460727369368246286138804284742124256700367133250078608537129877968287885457417957868580553371999414227484737603688992620953200143688061024092623556471053006464123205133894607923801371986027458274343737860395496260538663183193877539815179246700525865152165600985105257601565]

for quadratic_residues in ints :
    num = pow(quadratic_residues,(p-1)//2,p)
    if num == 1 :
        print(pow(quadratic_residues, (p + 1) // 4, p))

• output
  

flag : 93291799125366706806545638475797430512104976066103610269938025709952247020061090804870186195285998727680200979853848718589126765742550855954805290253592144209552123062161458584575060939481368210688629862036958857604707468372384278049741369153506182660264876115428251983455344219194133033177700490981696141526

Modular Square Root

題目

網址 : https://cryptohack.org/courses/modular/tonelli-shanks/

思路

r^2 ≡ a mod p，之後題目給了a跟p，要求r
因為提示提到了"sage"上網查後發現是一個有很多數學功能的軟體，其中就有直接求出r的指令可以使用

解法

• 開啟sage後把a跟p的值輸入進去(顏色為預設顏色，有點亮且不清楚非常抱歉)
  
• 打指令 mod(a, p).sqrt() 等一段時間後便會跳出答案
  

flag = 2362339307683048638327773298580489298932137505520500388338271052053734747862351779647314176817953359071871560041125289919247146074907151612762640868199621186559522068338032600991311882224016021222672243139362180461232646732465848840425458257930887856583379600967761738596782877851318489355679822813155123045705285112099448146426755110160002515592418850432103641815811071548456284263507805589445073657565381850521367969675699760755310784623577076440037747681760302434924932113640061738777601194622244192758024180853916244427254065441962557282572849162772740798989647948645207349737457445440405057156897508368531939120

統整

• 勒讓德符號(Legendre symbol)
  • 
    • (a|p) = 1，a 為二次剩餘(mod p)
    • (a|p) = −1， a 為二次非剩餘(mod p)
• sagemath
  • 下載(這裡以載在kali為例)&開啟方式
    • 搜尋關鍵字"sagemath"之後根據步驟在系統上下載sage

    sudo apt-get update
    sudo apt-get -y install sagemath
    
    

    • 下載完後打指令"sage"開啟
      
  • mod(a, p).sqrt()
  • 

小結

今天解了這兩題，學到更快判斷是不是二次剩餘的方法，跟發現原來有sagemath這個數學軟體的存在，然後也了解其實自己對於模運算還是沒很熟，對於第一題求平方根(p + 1) // 4還是有一點卡卡的，悲慘的數學能力qwq明天繼續努力!

參考資料

• 勒讓德符號 : https://zh.wikipedia.org/wiki/%E5%8B%92%E8%AE%A9%E5%BE%B7%E7%AC%A6%E5%8F%B7
• Significance of 3mod4 in squares and square roots mod n?https://crypto.stackexchange.com/questions/20993/significance-of-3mod4-in-squares-and-square-roots-mod-n
• How To Install sagemath on Kali Linux : https://installati.one/install-sagemath-kalilinux/
• sage指令 https://doc.sagemath.org/html/en/reference/finite_rings/sage/rings/finite_rings/integer_mod.html