복호화
시간 제한1초메모리 제한64 MB
암호화 장치에 320번 이하로 질의해 선형 점화식의 비밀 초기값 세 개와 바이트 순열 M을 복원한다.
문제
과학 위원회가 통신을 암호화하는 특수 장치를 사용한다는 소문이 있다. 암호화를 깨면 위원회가 준비한 문제를 엿듣고 많은 점수를 받을 수 있다. 지난밤 운 좋게도 위원 중 한 명이 술집에 장치를 두고 갔다. 당신은 그것을 열어 전체 설계도를 살펴보았다.
모든 연산은 8비트로 이루어지며, XOR은 비트 단위 배타적 논리합이다(C의 ^ 연산자, Pascal의 xor 연산자).
R은 다음과 같이 정의되는 의사난수 수열이다.
- R[0], R[1], R[2]의 값은 과학 위원회만 아는 비밀 값이다.
- n = 3, 4, …에 대해 R[n] = R[n-2] XOR R[n-3]이다.
또한 함수 M, M:[0..255] → [0..255]가 있다. M은 전단사 함수이다. 즉 x ≠ y이면 M[x] ≠ M[y]이다.
과학 위원회의 장치는 한 번에 수 하나를 받아 암호화된 값을 출력한다.
장치를 N번 사용한 뒤 들어오는 다음 수 INPUT은 다음과 같이 암호화된다.
- OUTPUT = M(INPUT XOR R[N])
암호화 장치의 동작 원리는 이해했지만 비밀 값 R[0], R[1], R[2]는 알지 못한다. M도 알지 못하므로 통신을 복호화할 수 없다. 대신 주운 장치를 가지고 놀 수 있다. 장치에 입력 수를 넣고 출력을 관찰할 수 있다.
당신의 임무는 모든 비밀 값 R[0], R[1], R[2], M[0], M[1], .., M[255]을 320회 미만의 질의(입력 수)로 알아내는 것이다.
제한
- 질의 횟수가 320회 미만이어야 정답으로 인정된다.
- 모든 테스트에서 비밀 키 R[0], R[1], R[2], M[0], M[1], …, M[255]는 무작위이다.
- 0 ≤ INPUT, OUTPUT, R, M ≤ 255