[CTFlearn] Polycrypto - 암호학 / Python

 

CTFlearn에서 제공하는

 

Hard 난이도의 암호학 문제

 

다항식을 이용한 문제이다.

 

반응형

 

문제 파일이 제공되는 주소와

 

위키피디아 주소가 같이 적혀있다.

 

 

먼저 문제파일을 다운받아 열어보면

 

이런 내용이 적혀있다.

 

엄청나게 긴 다항식이 적혀있는게 보인다.

 

 

다음으로 위키피디아에 들어가보면

 

이런 내용이 적혀있다.

 

다항식을 binary로 표현하는 방법에 대해 안내한다.

 

영어랑 수식은 복잡해서 자세히 안읽었고

 

밑줄친 부분만으로도 충분히 풀 수 있을거 같아 바로 해보기로 했다.

 

핵심은 다항식에서 p^n 형태로 표현된 부분만 1로,

 

나머지 부분은 0으로 만들면 된다는 것이다.

 

 

우선 지수를 추출해야 했는데

 

귀찮아서 ChatGPT 한테 시켰다.

 

1초만에 바로 뽑아준다.

 

ChatGPT가 뽑아준 지수에서 맨 끝에 0만 더 넣으면 된다.

 

문제의 다항식 맨 뒤에 +1 이 있고, 

 

정수는 지수 표현이 없기 때문이다.

 

 

이제 binary 값을 담을 배열을 생성해 줘야하는데

 

8개가 한 세트이니 8의 배수만큼 만들어 준다.

 

가장 큰 지수가 206 이었으므로 208만큼 만들어 준다.

 

array = [0] * 208

indices = [206, 205, 202, 201, 198, 197, 195, 194, 190, 189, 184, 182, 181, 178, 177, 176,
           174, 173, 172, 171, 169, 168, 166, 165, 164, 157, 156, 150, 149, 147, 146, 142,
           141, 140, 139, 136, 134, 133, 131, 130, 129, 126, 125, 123, 122, 121, 120, 118,
           117, 115, 114, 112, 109, 108, 104, 102, 101, 96, 94, 93, 91, 90, 86, 85, 84,
           81, 80, 78, 76, 75, 74, 73, 72, 69, 68, 66, 62, 61, 60, 57, 53, 52, 49, 48,
           46, 44, 43, 42, 41, 40, 38, 37, 35, 33, 32, 29, 28, 21, 20, 14, 13, 11, 10,
           6, 5, 4, 3, 2, 0]

for index in indices:
    array[index] = 1

reversed_array = array[::-1]
output = ''.join(map(str, reversed_array))
print(output)

 

다음으로 Python을 이용해

 

위와 같이 코드를 작성하면 된다.

 

208 짜리 0으로 가득찬 배열을 만들고,

 

지수가 있는 부분만 1로 채워준 뒤

 

역순으로 출력하는 것이다.

 

 

출력된 값을

 

CyberChef(https://gchq.github.io/CyberChef/) 에서 From Binary 로 디코딩 해주면

 

플래그를 찾을 수 있다.