기술 요약: 일반화된 루카스 행렬에 기반한 새로운 공개 키 암호 체계

문제 정의

본 논문은 더 큰 키 공간, 감소된 전송 복잡도, 그리고 수론 및 선형 대수에 기반한 강력한 보안을 제공하는 향상된 공개 키 암호 체계의 필요성을 다룬다. 행렬 이론과 재귀 수열(피보나치 및 루카스 수열 등)은 암호학(예: Hill Cipher, ElGamal)에서 활용되어 왔으나, 기존 방식들은 종종 대규모 키 행렬을 교환하거나 표준적인 수열 특성에 의존한다. 저자들은 일반화된 재귀 행렬을 사용하여 키 합의 시 교환되는 데이터를 최소화하는 동시에 암호화 키 공간의 복잡성을 극대화하는 시스템을 제안한다.

방법론

1. 수학적 기초

제안된 체계의 핵심은 **일반화된 피보나치 행렬(GFM)**로부터 유도된 **일반화된 루카스 행렬(GLM)**의 구축에 기초한다.

• 일반화된 피보나치 행렬 (GFM): 저자들은 $k$차 일반화된 피보나치 수열 $\{f_{k,n}\}$과 그에 대응하는 행렬 표현 $Q^k_n$을 활용한다. 이 행렬들은 $Q^n_k Q^l_k = Q^{n+l}_k$와 같은 표준 성질 및 차수 $k$에 따른 특정 행렬식 규칙을 만족한다.
• 일반화된 루카스 수열: 초기값들이 첫 $k$개의 GFM 행렬의 트레이스(trace)로부터 유도되는 새로운 수열 $\{l_{k,n}\}$을 정의한다 ($l_{k,r} = \text{trace}(Q^r_k)$). 재귀 관계식은 일반화된 피보나치 수열과 동일하다: $l_{k,k+n} = \sum_{i=0}^{k-1} l_{k,k+n-1-i}$.
• 일반화된 루카스 행렬 (GLM): 일반화된 루카스 수열의 항들의 선형 결합을 사용하여 재귀적 행렬 $L^{(n)}_k$를 구축한다. 저자들은 GLM과 GFM 사이의 근본적인 관계를 다음과 같이 정립한다:
  $$L^{(n)}_k = Q^n_k L^{(0)}_k = L^{(0)}_k Q^n_k$$
  여기서 $L^{(0)}_k$는 초기 루카스 행렬이다.

2. 암호 체계

제提案된 시스템은 이러한 행렬들을 수정된 **아핀-힐 암호(Affine-Hill Cipher)**와 ElGamal 공개 키 인프라와 통합한다.

• 키 교환 (ElGamal 기반):

  • 수신자 (Bob): 소수 $p$, 원시근 $\alpha$, 그리고 비밀 정수 $D$를 선택한다. 그는 $E_1 = \alpha$와 $E_2 = \alpha^D \pmod p$를 공개한다.
  • 송신자 (Alice): 무작위 정수 $e$를 선택한다. 그녀는 서명 $s = E_1^e \pmod p$와 공유 비밀 $\lambda = E_2^e \pmod p$를 계산한다.
  • 전송: Alice는 암호문과 서명 $s$를 Bob에게 보낸다. 그녀는 전체 키 행렬이나 비밀 $\lambda$를 보내지 않는다.

• 암호화 (GLM을 이용한 Affine-Hill):

  • 공유 비밀 $\lambda$ (행렬의 차수)와 서명 $s$ (지수)를 사용하여, Alice는 암호화 키 행렬 $K = L^{(s)}_\lambda \pmod p$를 구성한다.
  • 이동 벡터 $B$는 루카스 수열의 항들을 사용하여 생성된다: $B = [l_{\lambda,\lambda}, l_{\lambda,\lambda+1}, \dots, l_{\lambda,2\lambda-1}]$.
  • 평문 블록 $P$는 $C = (P \cdot K + B) \pmod p$로 암호화된다.

• 복호화:

  • Bob은 자신의 개인 키를 사용하여 $\lambda$를 복구한다: $\lambda = s^D \pmod p$.
  • 그는 역행렬 $K^* = L^{(-s)}_\lambda H^{-1} \pmod p$를 구성한다. 여기서 $H = (L^{(0)}_\lambda)^2$이다. 논문은 $L^{(s)}_\lambda L^{(-s)}_\lambda = H$임을 입증하여 역행렬의 존재를 보장한다.
  • 복호화는 $P = (C - B) \cdot K^* \pmod p$로 수행된다.

주요 기여

1. 일반화된 루카스 행렬의 정의: 본 논문은 차수 $k$인 GLM을 공식적으로 정의하고, 행렬식 공식, 곱셈 규칙 ($L^{(m)}_k L^{(n)}_k = L^{(m+n)}_k L^{(0)}_k$), 그리고 역행렬의 명시적 구성을 포함한 대수적 성질을 확립한다.
2. 파라미터 기반 키 생성: 대규모 시드로부터 전체 행렬을 생성하거나 공유해야 하는 전통적인 행렬 기반 암호와 달리, 이 체계는 두 개의 파라미터인 $\lambda$ (이산 로그 문제로부터 유도됨)와 $s$ (서명)만을 사용하여 양측이 키 행렬을 재구성할 수 있게 한다.
3. Affine-Hill 및 ElGamal과의 통합: 저자들은 ElGamal 설정에 내재된 이산 로그 문제의 어려움으로 보안이 강화된 Affine-Hill 암호(이동 벡터를 사용하는 블록 암호)를 활용하는 하이브리드 체계를 제안한다.
4. 역행렬 구성: 논문은 표준 가우스 소거법에 의존하지 않고 $Inv(L^{(n)}_k) = L^{(-n)}_k H^{-1}$ 관계를 활용하여 GLM의 역행렬을 계산하는 구체적인 방법을 제공한다.

결과 및 분석

• 구현 예시: 저자들은 $p=37$, 차수 $k=3$, 그리고 특정 정수 값 $D$와 $e$를 사용하여 체계를 시연한다. 그들은 평문 "NOBLE2022"를 암호문 블록으로 성공적으로 암호화하고 원래의 메시지를 복구함으로써, 행렬 연산과 모듈로 산술의 수학적 정확성을 검증하였다.
• 복잡도 감소: 이 체계는 키 전송의 시간 및 공간 복잡도를 줄인다고 주장한다. $n \times n$ 행렬을 전송하는 대신, $(\lambda, s)$ 쌍만을 교환한다.
• 보안 분석:
  • 이산 로그: $s$로부터 $\lambda$를 복구하는 것은 이산 로그 문제를 해결해야 하며, 이는 큰 소수에 대해 계산적으로 불가능하다.
  • 키 공간: 무차별 대입 공격에 대한 보안은 일반 선형 군 $|GL(\lambda)|$의 크기에 달려 있다. 저자들은 $p=37$이고 $\lambda=50$일 때 키 공간이 약 $3.105 \times 10^{3920}$임을 계산하였다.
  • 서명의 독립성: 분석에 따르면 서명 $s$가 알려지더라도 보안을 해치지 않는데, 이는 보안이 주로 $\lambda$를 결정하는 어려움과 $\lambda$에 의해 정의되는 방대한 행렬 공간에 의존하기 때문이다.

의의 및 주장

본 논문은 제안된 방법이 허가된 당사자에게는 수학적으로 단순하면서도 침입자에게는 강력한 장벽을 제공한다고 결론짓는다. 그 의의는 다음과 같다:

• 확장된 키 공간: 일반화된 루카스 행렬의 사용은 표준 구현에 비해 사용 가능한 키 공간을 크게 확장시킨다.
• 효율성: 키 전송을 두 숫자의 쌍으로 줄임으로써, 이 체계는 대역폭과 저장 공간 측면에서 효율성을 개선한다.
• 강건성: 키 합의(이산 로그 문제)와 암호화(행렬 구조의 복잡성)를 결합하여 다층 방어 체계를 구축한다.

저자들은 이 방법이 "허가된 당사자에게는 수학적으로 단순하지만, 침입자에게는 매우 까다로운" 방식이며, 이는 이산 로그 문제의 기성 난이도와 일반화된 루카스 행렬의 거대한 조합론적 공간에 기반하고 있다고 주장한다.