bmx 포맷 만든다고 별 개짓을 하면서 온갖 알고리즘을 다 들쳐 보고 있다. 주로 이미지/사운드 프로세싱(...하지만 논문에 도움은 안 된다)과 암호화 알고리즘들인데, 이미지 프로세싱 같은 건 사실 primitive하게 만들까 하고 있어서... (1차 변환을 행렬로 때려 맞춘다던지 등등등) 한편 고급 암호화는 결국 128bit RSA 정도로 잡기로 하고 초급 암호화 부분을 만들려 했는데... 이게 골때린다.

처음에 초급 암호화를 구상할 때는 의사 난수 생성기 두 개(아마도 LCG 정도로)를 잡고 rot/xor 연산의 파라미터로 그 두 의사 난수를 넣어서 암호화하는 걸 생각하고 있었는데, 의사 난수 생성기의 파라미터(LCG 같은 경우 의사 난수 생성 식이 x' = (ax + b) mod c인데 여기서 a, b, c와 초기 씨수 x0를 의미한다)를 고칠 수 있게 하려 했는데 갑자기 스치는 생각. 파라미터 잘못 정하면 trivial한 것만 나오는 거 아닌가-_-

아무튼 그래서 알고리즘 탐색은 시작되었다. 근데 LCG에서 일정 수준의 randomness를 확보하려 하니까 온갖 곤란한 것들이 많아서 다른 알고리즘을 한참 찾고 또 찾고 위키백과와 구글을 전전하면서 열댓개 정도 찾아 댕겼는데 그리 쓸 만한 것을 못 찾았다. (그리고 괜찮은 게 있어도 대부분 파라미터가 고정되어 있다. OTL) 그러다가 위키백과에서 결국 괜찮은 걸 찾고 말았는데.. 오호호호....

Linear feedback shift register라고, 예전에 생성된 비트 값 중 일부를 적당히 선택해서 연산한 후 (보통 x¹⁷+x¹⁵+1 처럼 다항식으로 표현한다) 다음 비트에 넣고 나머지 비트들은 쉬프트하는 것이다. 하드웨어적으로 구현 가능해서 빠르다고 하는데 소프트웨어적으로 구현하면 좀 느릴 것 같아 보이지만 파라미터 선택이 상당히 자유로운 편이기 때문에 :) 이걸로 결정했다. 거기에 Berlekamp-Massey algorithm이라고 해서 어떤 output sequence를 생성하기 위해서 필요한 최소 길이의 LFSR 다항식을 구해 주는 것도 있는데 이걸 쓰면 아주 효과적으로 의사 난수 생성기 데이터를 저장할 수 있을 것 같다. (적당히 긴 -- 32비트 정도로도 충분 -- output sequence를 랜덤하게 만들고 그걸 가지고 LFSR을 만들 수 있으니까, output sequence만 저장하면 간단하게 해결된다.) 오. 좋았어!

음냐... 파일 포맷 하나 설계하는데 온갖 문제에 부닥치니 역시 어렵다는 생각이 팍팍 든다. 누구 도와 주실 분 -_-;;;