세상의 모든 암호와 보안은 **'완전한 무작위성'**을 기반으로 합니다. 마치 도박에서 공정한 주사위처럼, 다음에 나올 숫자가 전혀 예측할 수 있어야 합니다. 하지만 현실에서는 완벽한 무작위성을 만들기 어렵습니다. 그래서 컴퓨터 알고리즘을 이용해 '거의 랜덤한' 숫자 (의사 난수) 를 만드는데, 이때 이 숫자가 진짜 랜덤한지, 아니면 패턴이 숨겨져 있는지를 확인하는 '측정 도구'가 필요합니다.
2. 주요 측정 도구들 (복잡도 지표)
이 논문은 이 '예측 게임'에서 상대방이 내 숫자 패턴을 찾아내려면 얼마나 많은 정보와 노력이 필요한지를 측정하는 여러 가지 '복잡도 (Complexity)'를 소개합니다.
① 선형 복잡도 (Linear Complexity): "가장 간단한 규칙 찾기"
비유: 친구가 숫자 나열을 했을 때, "이건 그냥 1, 2, 3, 4, 5... 하는 거야"라고 말하면 너무 쉽죠. 하지만 "이건 1, 3, 5, 7... 홀수만 나열한 거야"라고 하면 조금 더 복잡합니다.
의미: 숫자 나열을 만들어내는 **가장 간단한 공식 (규칙)**이 얼마나 복잡한지를 재는 척도입니다.
현실: 이 논문은 이 '가장 간단한 규칙'을 찾는 데는 이미 잘 정립된 방법 (베를레캄프 - 매시 알고리즘) 이 있다는 것을 설명합니다. 하지만 이 규칙이 너무 간단하면 암호는 쉽게 뚫립니다.
② 2 차 복잡도 (Quadratic Complexity): "규칙이 조금 더 꼬여있을 때"
비유: 선형 복잡도가 "A+B=C" 같은 단순한 사칙연산이라면, 2 차 복잡도는 "A×B+C=D"처럼 숫자끼리 곱해지거나 섞이는 더 복잡한 규칙을 다룹니다.
의미: 단순한 덧셈/뺄셈 규칙으로는 설명이 안 되고, 곱셈이나 제곱 같은 더 복잡한 수학 공식이 필요한지 확인합니다.
현실: 이걸 계산하는 것은 선형 복잡도보다 훨씬 어렵고, 아직 연구가 덜 된 분야입니다.
③ 최대 차수 복잡도 (Maximum-order Complexity): "완벽한 예측 불가능성"
비유: 친구가 숫자를 말하는데, "이 숫자는 앞의 숫자들만 보고는 절대 다음 숫자를 맞출 수 없어"라고 선언하는 수준입니다.
의미: 숫자 나열을 만들어내는 데 필요한 **가장 짧은 기계 (장치)**의 크기를 재는 것입니다. 이 기계가 클수록, 그리고 규칙이 복잡할수록 암호는 안전합니다.
현실: 이 논문은 이 '최대 복잡도'를 계산하는 새로운 알고리즘과, 어떤 숫자 나열이 가장 복잡한지 (예측하기 가장 어려운지) 를 수학적으로 규명한 내용을 담고 있습니다.
3. 이 논문이 밝혀낸 핵심 내용
이 연구는 단순히 도구를 나열하는 것을 넘어, 다음과 같은 중요한 통찰을 제공합니다:
도구들의 관계: 위 세 가지 복잡도 (선형, 2 차, 최대) 는 서로 연결되어 있습니다. 보통은 선형 < 2 차 < 최대 순서로 복잡도가 높아집니다. 즉, 가장 간단한 규칙으로 설명할 수 없으면, 더 복잡한 규칙을 찾아야 하고, 결국엔 가장 복잡한 기계가 필요하다는 뜻입니다.
완벽한 랜덤은 없다?: 흥미롭게도, 수학적으로 '가장 복잡한 (예측하기 가장 어려운)' 숫자 나열을 만들 수는 있습니다. 하지만 그런 숫자들은 **너무 규칙적인 패턴 (예: 000...01)**을 가지고 있어, 오히려 암호학적으로는 '안전하지 않음'을 의미할 수도 있습니다. 즉, 복잡도가 높다고 해서 무조건 좋은 건 아닙니다.
새로운 측정법: 이 논문은 기존에 잘 알려지지 않았던 '2 차 복잡도'나 '최대 차수 복잡도'를 계산하는 효율적인 방법들을 정리하고, 아직 풀리지 않은 문제들 (예: "어떤 숫자 나열이 2 차 복잡도가 가장 높을까?") 을 제시했습니다.
4. 결론: 이 연구가 우리에게 주는 메시지
이 논문은 **"암호를 뚫는 해커는 얼마나 많은 정보를 모아야 내 숫자 패턴을 맞출 수 있을까?"**를 수학적으로 계산하는 방법들을 정리한 것입니다.
선형 복잡도는 이미 잘 알려진 '기본기'입니다.
최대 차수 복잡도는 더 강력한 '고급 기술'로, 암호의 안전성을 판단하는 새로운 기준이 될 수 있습니다.
하지만 완벽한 무작위성을 찾기 위해서는 단순히 숫자가 복잡하기만 한 게 아니라, 그 숫자가 가진 **내부적인 구조 (균형, 안정성)**도 함께 고려해야 합니다.
한 줄 요약:
"이 논문은 암호를 만드는 숫자들이 얼마나 '미스터리한지' 측정하는 여러 가지 자 (자, 저울, 계산기) 를 소개하고, 어떤 자를 써야 가장 안전한 암호를 만들 수 있는지 연구한 보고서입니다."
이러한 연구는 우리가 사용하는 스마트폰 암호, 인터넷 뱅킹 보안, 그리고 미래의 양자 암호 기술이 뚫리지 않도록 지키는 데 핵심적인 역할을 합니다.
논문 요약: 의사난수 시퀀스를 위한 복잡도 측정 지표에 대한 조사
1. 문제 제기 (Problem)
암호학 및 보안 응용 분야에서는 키 (keys), 초기화 벡터 (IVs), 논스 (nonces) 등 무작위 비트의 생성이 필수적입니다. 이상적인 무작위 소스는 완전한 엔트로피를 가진 균일 분포의 독립적인 비트를 생성해야 하지만, 실제로는 이를 달성하기 어렵습니다.
현실적 문제: 무작위 비트 생성기 (RBG) 의 결함으로 인해 실제 시스템이 해킹당하는 사례가 빈번하게 발생하고 있습니다.
핵심 질문: 의사난수 시퀀스 (Pseudo-Random Sequences) 의 무작위성을 어떻게 평가할 것인가?
배경: Kolmogorov 복잡도 (1960 년대) 가 제안된 이후, 다양한 복잡도 측정 지표가 개발되었으나, 피드백 시프트 레지스터 (FSR) 기반의 시퀀스 생성 및 분석에 초점을 맞춘 체계적인 조사가 필요했습니다. 특히 선형 복잡도뿐만 아니라 비선형 복잡도 (2 차, 최대 차수 등) 와 다른 지표들 간의 관계를 규명하는 것이 중요합니다.
2. 방법론 (Methodology)
이 논문은 피드백 시프트 레지스터 (FSR) 를 기반으로 한 시퀀스 복잡도 측정 지표들의 이론적 발전, 계산 알고리즘, 통계적 행동, 그리고 서로 다른 지표 간의 관계를 체계적으로 조사합니다.
범위: 선형 복잡도 (Linear), 2 차 복잡도 (Quadratic), 최대 차수 복잡도 (Maximum-order/Nonlinear) 를 중심으로, Lempel-Ziv 복잡도, 2-adic 복잡도, 확장 복잡도 (Expansion complexity), 상관관계 측정 (Correlation measure) 등과의 관계를 다룹니다.
접근 방식:
알고리즘적 분석: Berlekamp-Massey 알고리즘, DAWG(Direct Acyclic Word Graph) 기반 계산, 행렬 계수 (Rank) 분석 등을 통해 복잡도를 계산하는 효율적인 방법을 검토합니다.
대수적 분석: 유한체 (Finite Field) 상의 다항식, 디스크리트 푸리에 변환 (DFT), 사이클로토믹 코스 (Cyclotomic cosets) 등을 활용하여 주기 시퀀스의 복잡도를 분석합니다.
통계적 분석: 무작위 시퀀스에 대한 복잡도 분포의 기대값과 분산을 이론적 정리와 수치적 시뮬레이션을 통해 규명합니다.
3. 주요 기여 및 핵심 내용 (Key Contributions & Results)
가. 선형 복잡도 (Linear Complexity)
정의: 시퀀스를 생성하는 가장 짧은 선형 피드백 시프트 레지스터 (LFSR) 의 길이.
계산: Berlekamp-Massey 알고리즘으로 O(n2) 시간에 효율적으로 계산 가능.
통계적 행동: 무작위 이진 시퀀스의 기대 선형 복잡도는 약 n/2이며, 분산은 약 86/81로 수렴합니다 (Rueppel, Niederreiter 의 연구).
주기 시퀀스:n-주기 시퀀스의 선형 복잡도는 L(s)=n−deg(gcd(xn−1,sn(x)))로 표현되며, DFT 를 통해 계산 가능합니다.
완벽한 시퀀스 (Perfect Sequences): 선형 복잡도 프로파일이 무작위 시퀀스와 매우 유사한 d-perfect 시퀀스 구성이 연구되었습니다.
나. 2 차 복잡도 (Quadratic Complexity)
정의: 2 차 피드백 함수를 가진 가장 짧은 FSR 의 길이.
계산: 선형 방정식 시스템 M(n,m)F(m)=E(n,m)의 해 존재 여부와 행렬의 계수 (Rank) 를 통해 결정됩니다.
알고리즘: Rizomiliotis 등 (2005) 은 행렬의 중첩 구조 (nesting structure) 를 이용하여 Berlekamp-Massey 와 유사한 재귀 알고리즘을 제안했습니다.
통계적 행동: 무작위 시퀀스의 2 차 복잡도 기대값은 약 2n으로 추정되지만, 선형 복잡도만큼 이론적으로 완전히 규명되지는 않았습니다.
암호학적 의미: 2 차 복잡도가 낮은 시퀀스는 알려진 일부 비트로부터 전체 시퀀스를 복원할 수 있어 암호학적으로 부적합합니다.
다. 최대 차수 복잡도 (Maximum-order Complexity / Nonlinear Complexity)
정의: 시퀀스를 생성하는 가장 짧은 FSR 의 길이 (비선형 피드백 함수 포함).
계산:
DAWG 기반: Jansen 은 직접 비순환 단어 그래프 (DAWG) 의 최대 깊이를 통해 복잡도를 계산하는 방법을 제시했습니다.
재귀 알고리즘: Rizomiliotis 등은 선형 복잡도 업데이트와 유사한 재귀적 업데이트 규칙을 제안하여 O(n2logn) 또는 O(n3) 복잡도로 계산하는 효율적인 알고리즘을 개발했습니다.
통계적 행동: 무작위 시퀀스의 기대 최대 차수 복잡도는 약 2logqn입니다.
고복잡도 시퀀스: 최대 복잡도 (n−1) 를 갖는 시퀀스는 (0,…,0,1) 형태와 같이 강한 재귀적 구조를 가지므로, 오히려 무작위성이 낮아 암호학에 부적합할 수 있음을 지적했습니다.