국가암호공모전 2018 (II-A)분야 3번 문제 풀이

이 문제를 보자마자 바로 Arduino uno rev3를 사러 갔던 기억이 있다.. 크흠 

문제의 가장 핵심은? 아래와 같다!

문제의 핵심

완전 심플한데, 문제는 아두이노에서 기본적으로 제공하는 변수의 최대 크기가 64bit double 또는 long long 형이다.

48비트 변수 두개를 곱하면 최대 크기가 96비트이므로 일반적으로 곱 연산을 하면 32비트가 흘러넘쳐버린다.

처음에는 multiply large numbers represented as Strings처럼 변수를 string으로 바꾸어 계산하는 문제인가? 하고 잘못 접근을 했었다. 그렇게 가능하기는 한데 아두이노 내부의 string 관련 operation(atoi) 등이 시간을 엄청 잡아먹어서 이렇게 풀면 안된다는 것을 직감하고 말았다.

 

다시 문제를 들여다보니 모듈러 연산이 있었다. 모듈러 연산이 들어가는 경우에는 가끔 직접 계산을 하지 않고도 clever하게 문제를 해결할 수 있는 경우가 있었기 때문에(python pow 3번째 인자 등), 해당 방향으로 접근하였다. 그러던 중 해당 링크를 찾아 대충 어떤 방식으로 접근할지를 생각하게 되었다. 모듈러 연산의 수학적 성질을 이용한 것이었고, 여기서 팀원쿤의 도움을 받아 답안을 작성할 수 있게 되었다. 아래에 답안을 작성하였다.

 

---------------------------------------------------------

Avr-libc의 user manual에 따르면 Arduino Uno에서 저장할 수 있는 가장 큰 자료형은 long long으로 64bit이다. 테스트 벡터들의 크기는 48bit이므로, 테스트 벡터 두 개를 단순히 곱하였을 때 최대 96bit의 결과가 나온다. Arduino Uno에서 64bit 곱셈 연산은 32bit 곱셈 연산에 비해서 시간이 약 8배 정도 더 소요된다. 이러한 문제를 해결하여 보다 빠르게 연산을 수행하기 위하여 다음과 같은 아이디어를 사용하였다.

문제에서 요구한 테스트 벡터 C는 테스트 벡터 A와 B의 곱을 2^32로 나눈 결과이다. 그러므로 테스트 벡터 A와 B를 다음과 같은 표기법을 사용하여 표현하자. 테스트 벡터 X의 하위 1 bit에서 16bit까지의 값을 x_1, 17bit에서 32bit까지의 값을 x_2, 33bit에서 48bit까지의 값을 x_3라 하자. 이 표기법을 이용하여 A와 B를 표현하면

A = a_1 + a_2 * 2^16 + a_3 * 2^32

B = b_1 + b_2 * 2^16 + b_3 * 2^32

와 같다. A와 B를 곱한 결과는 다음과 같다.

A * B = (a_3 * b_3) * 2^64 + (a_2 * b_3 + a_3 * b_2) * 2^48 + (a_1 * b_3 + a_2 * b_2 + a_3 * b_1) * 2^32 + (a_2 * b_1 + a_1 * b_2) * 2^16 + a_1 * b_1

문제에서 요구한 테스트 벡터 C를 구하기 위해 위의 식을 2^48로 나누면 다음과 같다.

C = A * B (mod 2^48) = (a_1 * b_3 + a_2 * b_2 + a_3 * b_1) * 2^32 + (a_2 * b_1 + a_1 * b_2) * 2^16 + a_1 * b_1

a_i 와 b_i는 정의에 의해 최대 2^16 - 1의 값을 가지므로, a_i * b_j 의 값은 2^32을 넘을 수 없다. 결과적으로 위 식의 우변을 계산하면 32bit 곱셈 연산만 사용하여 문제에서 제시한 테스트 벡터 C를 계산할 수 있다.

연산에 자주 쓰이는 상수 2^8k 꼴들을 미리 계산하여 소스코드에 상수로 정의하여, 연산 속도를 개선하였다.

위와 같은 구현 방식을 바탕으로 코드를 구현하여 모든 테스트 벡터 쌍을 통과하는 것을 확인하였다. 벤치마크 결과는 다음과 같으며 코드는 Crypto_3.ino에 첨부하였다.

Crypto_3.ino

0.00MB

벤치마크 결과: 711/712/712 (ms)

----------------------------------------------------------

 

나이브하게 파일을 구현해서 돌렸을 때 벤치마크 결과가 1200ms정도 나왔던 것으로 기억하는데, 자주 사용하는 상수들을 미리 계산해놓는 등의 연산을 통해 700ms까지 줄였었다. 어셈블리 레벨에서 뭔가 더 하면 더 좋게 만들 수 있었을 것 같은데, 그 당시 타원곡선 문제 때문에 고통받고 나중에 더 개선해야지... 하다가 말았던 기억이 있다.

 

궁금한 점이 있으면 댓글 주세요. 감사합니당