A Matrix-Based Polyalphabetic Algorithm for Information Encoding and Decoding Using Number Sequences

기술 요약: 수열을 이용한 정보 인코딩 및 디코딩을 위한 행렬 기반 다중 치환 알고리즘

문제 정의
본 논문은 표준 단일 치환 암호(monoalphabetic substitution ciphers)가 빈도 분석에 취약하다는 점을 다룬다. 단일 치환 체계에서는 동일한 평문 문자가 항상 동일한 암호 기호로 매핑되므로, 소스 언어의 통계적 분포가 보존되어 공격자가 빈도 계산을 통해 키를 추론할 수 있다. 다중 치환 암호(Vigenère 등)는 여러 개의 치환 알파벳을 사용하여 이를 완화하지만, 저자들은 다중 치환과 호모포닉(homophonic) 특성을 결합한 새로운 접근 방식을 제안한다. 목표는 위치와 발생 횟수에 따라 반복되는 평문 기호를 서로 다른 수치 표현으로 분산시킴으로써, 암호문의 빈도 분포를 평탄하게 만들고 통계적 암호 해독에 대한 저항성을 높이는 것이다.

방법론
제안된 방식인 FLLJ-POLY는 피보나치(Fibonacci), 루카스(Lucas), 레오나르도(Leonardo), 야코브스탈(Jacobsthal)이라는 네 가지 특정 정수 수열을 활용하는 행렬 기반 다중 치환 암호 알고리즘이다. 방법론은 다음 단계로 진행된다:

1. 이론적 기초 및 수열 분리:
   저자들은 충분히 큰 인덱스에 대해 레오나르도, 피보나치, 야코브스탈 수열이 서로 겹치지 않는 정수 집합을 생성한다는 것을 입증한다. 루카스 수는 단어 구분자를 인코딩하기 위해 별도로 예약된다. 이 세 가지 서로 다른 수열 값들의 모듈러 축소가 단사 함수(injective)로서 기능하여 기호를 고유하게 디코딩할 수 있도록 하기 위해, 충돌이 없는 공공 소수 모듈러스 $P$(예: $P=10159$)를 선택한다.

2. 메시지 준비 및 치환:
   평문은 크기가 $3m \times 3m$인 정사각 행렬 $M$으로 변환되며, 단어 구분자는 특정 기호(예: $\ast$)로 표시된다.

• 문자 치환: 각 문자는 세 가지 수열 기반 알파벳(피보나치, 레오나르도, 또는 야코브스탈) 중 하나의 값으로 교체된다. 알파벳의 선택은 위치 의존적 선택 함수에 의해 결정된다:
  $$\sigma = (v^2 + (i - 1) + (j - 1)) \pmod 3$$
  여기서 $v$는 해당 문자의 발생 횟수이며, $(i, j)$는 행과 열의 인덱스이다. 이 메커니즘은 동일한 문자가 위치와 빈도에 따라 서로 다른 수치 값으로 매핑되도록 보장하여 호모포닉 동작을 도입한다.
• 구분자 인코딩: 단어 구분자는 키에 의존하는 파라미터 $a_0$에 의해 인덱스가 이동된 루카스 수를 사용하여 인코딩되며, 이를 통해 예측 가능한 패턴을 방지한다.

3. 행렬 변환 및 암호화:
   치환된 행렬은 $3 \times 3$ 부 행렬들로 나뉜다. 비밀 키 수열 $a_0, a_1, \dots, a_{k-1}$은 사전 공유된 시드 $s$와 소수 $p$를 사용하여 레오나르도 수를 포함하는 비선형 재귀 관계를 통해 생성된다:
   $$a_{i+1} = (L_s a_i + a_i^2 + i) \pmod p$$
   각 $3 \times 3$ 블록은 레오나르도 $Q$-행렬의 거듭제곱($Q^{a_{j-1}}$)을 $P$에 대해 곱함으로써 암호화된다.

4. 암호문 구성:
   전송 크기를 줄이면서 무결성을 유지하기 위해, 알고리즘은 각 암호화된 블록의 행렬 성분 9개 중 8개와 함께 행렬식(determinant)을 전송한다. 누락된 "숨겨진" 성분은 대응하는 여인수(cofactor)가 모듈로 $P$에 대해 0이 아닌 경우, 수신자가 행렬식 조건을 사용하여 복구할 수 있다.

주요 기여

• 새로운 수열 통합: 본 논문은 피보나치, 레오나르도, 야코브스탈, 루카스 수열을 동시에 사용하는 통합 프레임워크를 도입하며, 특정 인덱스 범위에서 이들의 상호 배타성(disjointness)을 입증하는 엄격한 증명(정리 2.1–2.5)을 제시한다.
• 호모포닉-다중 치환 하이브리드: 본 방식은 이차 선택 함수를 통해 다중 치환(알파벳 변경)과 호모포닉 치환(하나의 기호에 대한 다중 표현)을 결합하여 빈도 집중도를 효과적으로 낮춘다.
• 비선형 키 생성: 블록 키는 이차 및 비자율적(non-autonomous) 재귀 관계를 통해 유도되며, 이는 선형 합동 생성기(linear congruential generator)에 비해 복잡성을 더한다.
• 효율적인 모듈러 구현: 충돌이 없는 소수 $P$를 사용함으로써, 모든 연산이 네이티브 정수 산술 범위 내에서 수행되도록 하여 대형 정수 산술(large-integer arithmetic)이 요구되는 미축소 수열 값의 계산 오버헤드를 방지한다.

결과
저자들은 576자의 영어 텍스트를 사용한 작업 예시와 예비 통계 분석을 제시한다:

• 통계적 보안: 본 방식은 표준 영어의 일치 지수(I.C.)인 0.0667 및 짧은 키를 가진 비즈네르(Vigenère) 암호의 0.0450에 비해, I.C.를 약 0.0153으로 크게 낮춘다. 정규화된 카이제곱 통계량($\chi^2/c$)은 단일 치환 대비 약 70.6% 감소한다. 섀넌 엔트로피 효율은 **87.8%**에 도달하여 암호문 기호의 거의 균등한 분포를 나타낸다.
• 쇄신 효과(Avalanche Effect): 비밀 키 파라미터($s$ 또는 $p$)의 미세한 변화는 평균적으로 약 **48.5%**의 비트 변화를 일으키며, 이는 이상적인 엄격 쇄신 기준(Strict Avalanche Criterion)인 50%에 근접한다.
• 계산 성능: 모듈러 구현은 대형 정수 산술(GMP)을 사용하는 미축소 구현에 비해 인코딩 및 디코딩 시간에서 7~8배의 속도 향상을 달로한다. 500자 메시지의 인코딩 시간은 약 1.47 ms에서 약 0.21 ms로 단축되었다.

의의 및 주장
본 논문은 FLLJ-POLY를 표준 치환 암호에 대한 수학적으로 근거 있는 대안으로 포지셔닝한다. 저자들은 이 구조가 개선된 분포 동작과 계산 효율성을 제공한다고 주장한다. 이들은 주요 기여가 정수 수열의 상호 배타적 특성을 활용하여 서로 다른 수치 알파벳을 정당화함으로써 인코딩 절차의 엄격한 수론적 기초를 확립한 데 있음을 강조한다.

저자들은 본 연구가 광범위한 암호 해독적 처리가 아닌, 체계의 수학적 구조를 개발하고 정당화하는 데 초점을 맞추고 있음을 명시적으로 밝힌다. 따라서 이 시스템이 해독 불가능하다고 주장하지 않으며, 대신 알려진 평문, 선택 평문 및 대수적 공격과 같은 고급 공격에 대한 엄격한 분석은 향후 과제로 남아 있다고 언급한다. 본 연구의 의의는 효과적으로 빈도 분포를 평탄하게 만드는 재현 가능한 행렬 기반 프레임워크와 효율적인 모듈러 구현 전략을 입증하는 데 있다.