Question

from Crypto.Util.number import *
from Crypto.Random import get_random_bytes

FLAG = b"ZH{" + get_random_bytes(218) + b'}'
print(long_to_bytes((bytes_to_long(FLAG + b" is secret") >> 80) + (bytes_to_long(b"My last flag is ") << 1776)))

해당 코드를 통해 M1, M2의 선형 관계를 찾아냈는데 이것을 통해 Franklin-Reiter Related Message Attack을 해도 정답이 나오지 않습니다 ㅠㅠ 왜 그럴까요

#crypto

Answer 1

해당 코드로 선형 관계를 찾아냈다는 것인지 잘 모르겠습니다
bytes_to_long(FLAG + b" is secret") >> 80 는 bytes_to_long(FLAG)와 동일한 코드입니다.
bytes_to_long(FLAG) + (bytes_to_long(b"My last flag is ") << 1776)는 bytes_to_long(b"My last flag is " + FLAG)와 동일한 코드입니다.
즉 출력물은
print(long_to_bytes(bytes_to_long(b"My last flag is " + FLAG)))
print(b"My last flag is " + FLAG)와 다름이 없는 코드로 의미가 없는 코드 같습니다.

bytes_to_long(FLAG)에 해당하는 정수를 $x$ 라고 합시다. 그러면 $x$ 를 구해야 합니다.
bytes_to_long(b"My last flag is " + FLAG)에 해당하는 정수를 $m_1$ 이라 하면 $m_1 = x + a$ 꼴입니다.
bytes_to_long(FLAG + b" is secret")에 해당하는 정수를 $m_2$ 이라 하면 $m_2 = bx + c$ 꼴입니다.

$m_1,\;m_2$ 사이에는 $m_2 = b(m_1-a)+c = bm_1-ab+c$ 라는 알려진 선형 관계가 있다는 것을 확인할 수 있습니다.
따라서 이 문제는 Franklin-Reiter Related Message Attack을 사용할 수 있다는 것이고, 실제로 사용해보면 답이 나옵니다.
Franklin-Reiter Related Message Attack을 이해하고 코드로 구현하실 때 SageMath를 사용하여 두 다항식의 최대 공약수를 구하는 것이 편리합니다. 근데 두 다항식의 최대 공약수를 구할 때 gcd(f1, f2) 처럼 이미 구현된 함수를 사용하면 에러가 나므로 최대 공약수를 구하는 것은 직접 구현하셔야 합니다. 아니면 구글링해서 다른 코드를 참고해 사용해도 좋습니다.

2024.04.17. 00:08