Security/암호학(Cryptography)

[CryptoHack] Adrien's Signs

그믐​ 2023. 3. 9. 20:31
반응형

 

 

문제 설명

애드리언은 symbol(아마 르장드르 기호)와 마이너스 기호를 통해 메시지를 암호화 하는 방법을 찾고 있어요. flag를 복구할 방법을 알고 있나요?

 

 

문제 풀이

문제는 그냥 이전 개념들을 사용해서 푸는 것으로 보인다.

from random import randint

a = 288260533169915
p = 1007621497415251

FLAG = b'crypto{????????????????????}'


def encrypt_flag(flag):
    ciphertext = []
    plaintext = ''.join([bin(i)[2:].zfill(8) for i in flag])
    for b in plaintext:
        e = randint(1, p)
        n = pow(a, e, p)
        if b == '1':
            ciphertext.append(n)
        else:
            n = -n % p
            ciphertext.append(n)
    return ciphertext

print(len(encrypt_flag(FLAG)))

 

bin이라는 함수는 숫자가 들어오면 이를 0b~~를 앞에 붙여서 이진수(binary)로 변환해준다.

zfill은 ljust같은 느낌인데. 자릿수를 채워준다. 자릿수가 맞지 않으면 왼쪽을 0으로 채운다.

 

a와 p가 주어지고

for문에서 flag를 이진수로 변환한 값을 plaintext에 저장한다.

 

이진수 변환한 값을 b를 가지고 돌면서

1이면 1부터p까지 중에서 (1, p 포함) 랜덤한 수 e를 고르고

$a ^ e \bmod p$를 계산하여 ciphertext라는 list에 append한다.

 

0이라면 $-a^e \bmod p$를 넣는다.

 

다시 복구하기 위해서 우리는 이게 $a ^ e \bmod p$가 들어간 것인지, $-a^e \bmod p$가 들어간 것인지 알아야 한다.

우선, 익숙한 르장드르 기호를 통해서 a가 p의 이차 잉여인지 확인한다.

 

def is_qr(a, p) :
    if (pow(a, (p - 1)//2, p) == 1) :
        return True
    else :
        return False

해당 함수를 작성하고 a, p를 넣으면 True가 나온다.

a는 모듈러 p에 대한 이차잉여이다.

 

이차 잉여의 특징으로 1, -1을 대입해 생각한 것이 있다.

이차 잉여 * 이차 잉여 = 이차 잉여
이차 잉여 * 이차 비잉여 = 이차 비잉여
이차 비잉여 * 이차 비잉여 = 이차 잉여

 

이차 잉여를 n제곱 한다고 해도 이것은 이차 잉여이다.

 

따라서 $a ^ e \bmod p$는 a/p를 계산하면 1이다.

 

이제, $-a^e \bmod p$에 대해서

이것은 $a ^ e \bmod p$ 인 이차 잉여에 -1이 곱해졌다고 볼 수 있다.

 

-1은 이차 잉여일까? $-1 \equiv p-1 \bmod p$이므로 이걸 넣어보면

 

 

-1은 이차 비잉여이다.

따라서 1일때는 이차 잉여인 숫자가 리스트에 있고, 0일 때는 이차 비잉여인 숫자가 리스트에 있다.

 

이걸 토대로 이진수를 복구하고 원문을 구할 수 있으리라 생각된다.

 

from Crypto.Util.number import *

def is_qr(a, p) :
    if (pow(a, (p - 1)//2, p) == 1) :
        return True
    else :
        return False

a = 288260533169915
p = 1007621497415251

cipher = [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]

plainnum = ''

for c in cipher :
    if is_qr(c, p) :
        plainnum += '1'
    else :
        plainnum += '0'
plainnum = int(plainnum, 2)
print(long_to_bytes(plainnum))

 

반응형