[Day 17] 題目(Modular-10)

2024 iThome 鐵人賽

DAY 17

Security

密碼學小白的學習之路系列第 17 篇

16th鐵人賽

yunn

2024-08-23 22:56:48

64 瀏覽

分享至

Adrien's Signs

https://cryptohack.org/courses/modular/adrien/

題意:

題目本身沒給什麼解題線索，只告訴我們Adrien一直在尋找可以藉由符號和減號來加密訊息的方法。並問我們能夠找到解開flag的方法嗎?
而題目給了我們一個source.py和output.txt，從source code我們能發現這是加密flag的過程，而output檔則是加密後所得到的密文。

題目給的source code

小說明:

bin(i)[2:]: 將每個字節 i 轉換為二進位字串，並移除 0b 前綴。
zfill(8): 確保每個字節的二進位表示是8位數，不足8位的前面補零。

完整source code:

from random import randint

a = 288260533169915
p = 1007621497415251

FLAG = b'crypto{????????????????????}' # flag為未知

def encrypt_flag(flag):
    ciphertext = []
    # 將flag轉換為二進位字串形式，每個字元轉換為8位的二進位表示
    plaintext = ''.join([bin(i)[2:].zfill(8) for i in flag])
    
    for b in plaintext: # 逐次處理二進位字串
        # 隨機生成一個 1 到 p-1 之間的整數 e
        e = randint(1, p)

        # 計算 n = a^e mod p
        n = pow(a, e, p)

        # 如果位元 b 為 '1'
        if b == '1':
            ciphertext.append(n)  # n = a^e mod p 是二次剩餘（因為 a 的任何次方都是二次剩餘）
        else:  # 如果位元 b 為 '0'

            n = -n % p   # n = -a^e mod p ，這將 n 轉換為非二次剩餘
            ciphertext.append(n)

    return ciphertext

print(encrypt_flag(FLAG))

解題思路:

觀察後可發現這個加密過程是將將flag轉換為二進位格式，並根據每個位元來生成密文。

1 被加密成 a^e mod p
0 則被加密為-a^e mod p
其中e是一個隨機產生的整數

由於加密過程使用了隨機數加密，因此每次加密的結果都不同，導致很難從原始碼逆推回flag。

在看了他人的解題過程後，發現了解題的思路，也就是

1 會被加密成 a^e mod p
0 會被加密為-a^e mod p

這兩個加密結果有什麼不同呢? 沒錯，差了個負號。

還記得勒讓得符號嗎?先來簡單回顧一下勒讓得符號的定義與性質。

簡單寫個程式利用勒讓得符號判斷a是否為二次剩餘

def GCD(a,p):
    #如果p>a，兩者數值交換
    if a < p:
        a, p = p, a
    #如果p=0，則a為最大公因數，返回 a
    if(p==0):
        return(a)
    #如果p!=0，則需要繼續找出最大公因數，返回 GCD(p,a%p)
    else:
        return(GCD(p,a%p))

def a_p(a, p): #利用勒讓得符號判斷a是否為二次剩餘
    if GCD(a, p) != 1:
        return "a 和 p 不是互質，無法判定二次剩餘"
    if pow(a, (p-1)//2, p) == 1:
        return "a 是二次剩餘"
    else:
        return "a 不是二次剩餘"
    
a = 288260533169915
p = 1007621497415251
print(a_p(a,p))

a 是二次剩餘

a是二次剩餘,所以a的e次方也是二次剩餘(e為整數)
(上面提到的:二次剩餘 * 二次剩餘 = 二次剩餘，所以二次剩餘乘上e個二次剩餘也是二次剩餘)
回到這裡:

1 會被加密成 a^e mod p -> a^e mod p 是二次剩餘
0 會被加密為-a^e mod p -> -a^e mod p 不是二次剩餘

所以解密的過程就是判斷使否為二次剩餘，是的話就加上"1"，不是的話就加上"0"。

解題的code:


ciphertext =[67594220461269, 501237540280788, 718316769824518, 296304224247167, 48290626940198, 30829701196032, 521453693392074, 840985324383794, 770420008897119, 745131486581197, 729163531979577, 334563813238599, 289746215495432, 538664937794468, 894085795317163, 983410189487558, 863330928724430, 996272871140947, 352175210511707, 306237700811584, 631393408838583, 589243747914057, 538776819034934, 365364592128161, 454970171810424, 986711310037393, 657756453404881, 388329936724352, 90991447679370, 714742162831112, 62293519842555, 653941126489711, 448552658212336, 970169071154259, 339472870407614, 406225588145372, 205721593331090, 926225022409823, 904451547059845, 789074084078342, 886420071481685, 796827329208633, 433047156347276, 21271315846750, 719248860593631, 534059295222748, 879864647580512, 918055794962142, 635545050939893, 319549343320339, 93008646178282, 926080110625306, 385476640825005, 483740420173050, 866208659796189, 883359067574584, 913405110264883, 898864873510337, 208598541987988, 23412800024088, 911541450703474, 57446699305445, 513296484586451, 180356843554043, 756391301483653, 823695939808936, 452898981558365, 383286682802447, 381394258915860, 385482809649632, 357950424436020, 212891024562585, 906036654538589, 706766032862393, 500658491083279, 134746243085697, 240386541491998, 850341345692155, 826490944132718, 329513332018620, 41046816597282, 396581286424992, 488863267297267, 92023040998362, 529684488438507, 925328511390026, 524897846090435, 413156582909097, 840524616502482, 325719016994120, 402494835113608, 145033960690364, 43932113323388, 683561775499473, 434510534220939, 92584300328516, 763767269974656, 289837041593468, 11468527450938, 628247946152943, 8844724571683, 813851806959975, 72001988637120, 875394575395153, 70667866716476, 75304931994100, 226809172374264, 767059176444181, 45462007920789, 472607315695803, 325973946551448, 64200767729194, 534886246409921, 950408390792175, 492288777130394, 226746605380806, 944479111810431, 776057001143579, 658971626589122, 231918349590349, 699710172246548, 122457405264610, 643115611310737, 999072890586878, 203230862786955, 348112034218733, 240143417330886, 927148962961842, 661569511006072, 190334725550806, 763365444730995, 516228913786395, 846501182194443, 741210200995504, 511935604454925, 687689993302203, 631038090127480, 961606522916414, 138550017953034, 932105540686829, 215285284639233, 772628158955819, 496858298527292, 730971468815108, 896733219370353, 967083685727881, 607660822695530, 650953466617730, 133773994258132, 623283311953090, 436380836970128, 237114930094468, 115451711811481, 674593269112948, 140400921371770, 659335660634071, 536749311958781, 854645598266824, 303305169095255, 91430489108219, 573739385205188, 400604977158702, 728593782212529, 807432219147040, 893541884126828, 183964371201281, 422680633277230, 218817645778789, 313025293025224, 657253930848472, 747562211812373, 83456701182914, 470417289614736, 641146659305859, 468130225316006, 46960547227850, 875638267674897, 662661765336441, 186533085001285, 743250648436106, 451414956181714, 527954145201673, 922589993405001, 242119479617901, 865476357142231, 988987578447349, 430198555146088, 477890180119931, 844464003254807, 503374203275928, 775374254241792, 346653210679737, 789242808338116, 48503976498612, 604300186163323, 475930096252359, 860836853339514, 994513691290102, 591343659366796, 944852018048514, 82396968629164, 152776642436549, 916070996204621, 305574094667054, 981194179562189, 126174175810273, 55636640522694, 44670495393401, 74724541586529, 988608465654705, 870533906709633, 374564052429787, 486493568142979, 469485372072295, 221153171135022, 289713227465073, 952450431038075, 107298466441025, 938262809228861, 253919870663003, 835790485199226, 655456538877798, 595464842927075, 191621819564547]
a = 288260533169915
p = 1007621497415251
txt = ""
flag = ""

for t in ciphertext:
    a_p = pow(t, (p-1)//2, p)
    if a_p == 1:
        txt += "1"
    else:
        txt += "0"

for i in range(0, len(txt), 8):
    # 逐步處理 txt 字串，每次處理 8 位元的二進位數字，並將其轉換為對應的 ASCII 字符。
    # int(txt[i:i+8], 2) 將二進位字串 (txt[i:i+8]) 轉換為十進位整數。
    # chr() 函數將該整數轉換為對應的 ASCII 字符，並將結果串聯到 flag 字串中。
    flag += chr(int(txt[i:i+8], 2))

print(flag)