[CryptoHack] MISC(Bit by Bit)

Bit by Bit

문제(및 설명)

당신이 ElGamal에 대해 들었는데, 이것은 몇 가지 멋진 특성을 가지고 있다고 들었습니다. 저는 모든 비트를 다른 비밀로 암호화했으므로 당신은 제 플래그값을 복구할 수 못합니다.

풀이

from Crypto.Random import random
from Crypto.Util.number import getPrime, bytes_to_long

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


def get_padding():
    seed = 256
    e = random.randint(2, q)
    padding = pow(seed, e, q)
    return padding


def public_key():
    x = random.randint(2, q)
    return pow(g, x, q)


def encrypt(m, h):
    y = random.randint(2, q)
    s = pow(h, y, q)
    c1 = pow(g, y, q)
    c2 = (s * m) % q
    return (c1, c2)


m = bytes_to_long(FLAG)
q = 117477667918738952579183719876352811442282667176975299658506388983916794266542270944999203435163206062215810775822922421123910464455461286519153688505926472313006014806485076205663018026742480181999336912300022514436004673587192018846621666145334296696433207116469994110066128730623149834083870252895489152123
g = 104831378861792918406603185872102963672377675787070244288476520132867186367073243128721932355048896327567834691503031058630891431160772435946803430038048387919820523845278192892527138537973452950296897433212693740878617106403233353998322359462259883977147097970627584785653515124418036488904398507208057206926

while m:
    padding = get_padding()
    me = padding << 1 + m % 2
    h = public_key()
    (c1, c2) = encrypt(me, h)
    print(f'(public_key={hex(h)})')
    print(f'(c1={hex(c1)}, c2={hex(c2)})')
    m //= 2

output.txt

코드를 g가 르장드르 심볼을 보고 mod q에서 이차잉여값 인 것을 알았다.

그런 다음 암호화할 메시지를 생성하는 실제 작업 순서가 padding << (1 + (m % 2))임을 알아내면 padding∗2 또는padding∗4로 동일함을 알 수 있습니다.

패딩으로 사용되는 생성 변수 e도 이차잉여이므로 m∈QR, m=1이다.

2가 이차잉여인지 빠르게 테스트 후, 하나씩 모든 비트를 수집하고 복호화를 하게 되면

from Crypto.Util.number import long_to_bytes

q = 117477667918738952579183719876352811442282667176975299658506388983916794266542270944999203435163206062215810775822922421123910464455461286519153688505926472313006014806485076205663018026742480181999336912300022514436004673587192018846621666145334296696433207116469994110066128730623149834083870252895489152123
g = 104831378861792918406603185872102963672377675787070244288476520132867186367073243128721932355048896327567834691503031058630891431160772435946803430038048387919820523845278192892527138537973452950296897433212693740878617106403233353998322359462259883977147097970627584785653515124418036488904398507208057206926

def legendre_symbol(a, p):
    return pow(a, (p - 1) // 2, p)

assert(legendre_symbol(g, q) == 1)
f = open('output_1078aca02f2ab796a8c51773f3c332ee.txt')

lines = f.readlines()

flag = ""

for i in range(0, len(lines), 2):
    public_key = lines[i][1:-2]
    ciphertexts = lines[i + 1][1:-2]

    public_key = int(public_key.split("=")[1], 16)
    c1, c2 = ciphertexts.split(", ")
    c1 = int(c1.split("=")[1], 16) 
    c2 = int(c2.split("=")[1], 16)

    if legendre_symbol(c2, q) == 1: 
        flag += "1"
    else:
        flag += "0"

flag = flag[::-1]
print(long_to_bytes(int(flag, 2)))

플래그 값은 crypto{s0m3_th1ng5_4r3_pr3served_4ft3r_encrypti0n}이다.