💻 computer science

New Ideas on a New Old Type of Cipher:The Mixed-Radix One-Time Pad

이 논문은 일회용 패드(one-time pad)를 비균등 기수(non-uniform bases)로 정식화 및 일반화하여 혼합 기수 일회용 패드(Mixed-Radix One-Time Pad, MR-OTP)를 정의하고, 이것이 섀넌의 완전 비밀성(Shannon perfect secrecy)을 달성함을 증명하며, 고전적 변형들을 특수 사례로서 복구하고, 비밀 기수가 요구되는 키 엔트로피를 줄일 수 없음을 입증하는 동시에 안전한 세션 프로토콜을 제안한다.

원저자: Fabio F. G. Buono

게시일 2026-06-16

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Fabio F. G. Buono

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

핵심 아이디어: 더 나은 방식의 여행 가방 싸기

당신이 친구에게 보내고 싶은 여행 가방(메시지)이 있다고 상상해 보세요. 하지만 아무도 그 가방을 열 수 없게 만들고 싶습니다. 이를 위한 황금 표준은 **일회용 패드(One-Time Pad, OTP)**입니다. OTP를 아주 특별한 자물쇠라고 생각한다면, 그 자물쇠를 열기 위해서는 가방과 정확히 같은 크기의 열쇠가 필요합니다. 만약 그 열쇠가 진정으로 무작위적이고 단 한 번만 사용된다면, 그 자물쇠는 결코 깨뜨릴 수 없습니다.

하지만 전통적인 OTP는 보통 모든 것을 표준적인 "이진수(binary)" 가방(0과 1만 사용하는 방식)에 담도록 강요합니다. 만약 편지를 보낸다면, 모든 글자를 길고 복잡한 0과 1의 문자열로 변환해야 합니다. 이는 비효율적일 수 있습니다.

이 논문은 **혼합 기수 일회용 패드(Mixed-Radix One-Time Pad, MR-OTP)**라는 새로운 버전을 소개합니다. 모든 것을 이진수 가방에 억지로 구겨 넣는 대신, 이 방식은 각 칸의 크기를 다르게 설정할 수 있는 맞춤형 가방을 만들 수 있게 해줍니다.

작동 원리: 맞춤형 여행 가방

세 가지 서로 다른 아이템이 들어있는 여행 가방을 싸고 있다고 상상해 봅시다:

편지 (26가지 가능성: A–Z).
2.의 교통 신호 색상 (3가지 가능성: 빨강, 노랑, 초록).
동전 던지기 (2가지 가능성: 앞면, 뒷면).

기존의 이진수 시스템에서는 이 모든 것을 길고 지저분한 0과 1의 문자열로 변환해야 했습니다.
MR-OTP에서는 "혼합 기수(mixed-radix)" 시스템을 만듭니다. 당신은 가방에 세 개의 슬롯을 가집니다:

슬롯 1: 26개의 옵션을 담습니다.
슬롯 2: 3개의 옵션을 담습니다.
슬롯 3: 2개의 옵션을 담습니다.

이를 잠그기 위해, 당신은 단순히 하나의 키만 사용하는 것이 아닙니다. 당신은 각 슬롯을 위한 키를 사용합니다:

편지를 위한 0~25 사이의 무작위 숫자.
신호등을 위한 0~2 사이의 무작위 숫자.
동전 던지기를 위한 0~1 사이의 무작위 숫자.

당신의 비밀 메시지를 이 무작위 숫자들에 더합니다(마치 볼에 재료를 섞는 것처럼) 그러면 "암호문(ciphertext)"(잠긴 가방)이 만들어집니다. 친구가 이를 풀기 위해서는 동일한 무작위 숫자들을 뺍니다. 각 슬롯의 특정 "기수(base)" 내에서 수학적 연산(mod 26, mod 3, mod 2)이 이루어지기 때문에, 메시지는 완벽하게 복원됩니다.

위대한 발견: 이렇게 하면 키가 더 짧아질까?

저자는 매우 유혹적인 질문을 던집니다. "만약 슬롯의 크기(기수)를 비밀로 유지한다면, 더 짧은 키를 사용할 수 있을까?"

당신이 친구에게 이렇게 말했다고 가정해 봅시다. "나는 26개 슬롯, 3개 슬롯, 2개 슬롯을 가진 가방을 사용하고 있어." 하지만 당신은 어느 것이 어느 슬롯인지 알려주지 않습니다. 어쩌면 순서를 바꿔버릴 수도 있겠죠? 기대 효과는 이러한 비밀스러운 배치를 통해 더 작은 키를 사용할 수 있을지도 모른다는 것이었습니다.

이 논문은 이것이 불가능함을 증명합니다.
저자는 자물쇠가 수학적으로 깨지지 않는 완벽한 보안(perfect secrecy)을 유지하려면, 무작위 숫자(키)가 모든 슬롯의 모든 가능성을 여전히 커버해야 한다고 보여줍니다.

비유: 카드 덱에서 특정 카드를 숨기려고 한다고 상상해 보세요. 만약 당신이 덱을 섞고(메시지), 그 위에 무작위 카드를 놓아(키) 가린다면, 당신이 놓은 카드는 덱에 있는 어떤 카드라도 될 수 있어야 합니다. 만약 더 작은 규모의 키를 사용하려 한다면, 수학적 구조가 무너지고 비밀이 새어나가게 됩니다.
결과: 설령 가방의 "규칙"(기수)을 숨긴다 하더라도, 키는 여전히 메시지 자체만큼 길고 무작위적이어야 합니다. 당신은 정보 이론의 법칙을 속여서 더 짧은 키를 얻어낼 수 없습니다.

실제 이점: 마법이 아닌 효율성

그렇다면 키가 더 짧아지는 것도 아니라면, 왜 이 새로운 시스템을 사용해야 할까요? 논문은 이 시스템이 마법이 아니라 효율성과 적응성에 관한 것이라고 주장합니다.

자연스러운 패킹: 만약 당신이 DNA 데이터(4가지 문자: A, C, T, G)를 보내고 있다면, 이를 이진수(0과 1)로 억지로 바꿀 필요가 없습니다. 그냥 "4진법(base-4)" 슬롯을 사용하면 됩니다. 이는 데이터를 자연스럽게 담아내는 것으로, 사각형 구멍에 억지로 원형 못을 박는 대신 원형 구멍에 원형 못을 넣는 것과 같습니다.
키 롤링(Key Rolling): 논문은 앨리스와 밥이 거대한 "키 롤(roll)"을 공유하는 프로토콜을 제안합니다. 첫 번째 메시지를 보낼 때, 그들은 특정 기수 세트(예: 텍스트용)를 사용합니다. 다음 메시지를 보낼 때는, 다른 기수 세트(예: 숫자용)를 정의하는 키 롤의 새로운 섹션을 펼칩니다.
- 핵심 규칙: 그들은 절대로 키 롤의 같은 부분을 재사용하지 않습니다. 이를 통해 보안을 완벽하게 유지하면서도 형식을 자유롭게 전환할 수 있습니다.

이것이 의미하는 바 (그리고 의미하지 않는 것)

이것은 [이것]입니다: 데이터가 단순히 이진수가 아닌 경우에도 일회용 패드를 사용할 수 있는, 수학적으로 증명된 공식적인 방법입니다. 이는 기존의 이진수 OTP가 이 새로운, 더 유연한 시스템의 특수한 사례임을 확인시켜 줍니다.
이것은 [저것]이 아닙니다: "키의 길이는 최소한 메시지의 길이보다 길어야 한다"는 규칙을 깨는 방법이 아닙니다. 거대한 메시지를 잠그기 위해 아주 작은 키를 사용할 수 있는 "공짜 점심"을 제공하는 것도 아닙니다.
남겨진 질문: 논문은 수학적으로는 완벽하지만, 실무적인 질문이 남아있음을 인정합니다. 만약 공격자가 "기수"(슬롯의 크기)를 모른다면, 코드를 풀기 위해 올바른 조합을 맞추기가 충분히 어려울까요? 논문은 이 부분을 향후 연구를 위한 미스터리로 남겨두었습니다.

요약

**혼합 기수 일회용 패드(Mixed-Radix One-Time Pad)**는 경직된 단일 크기의 컨테이너에서 다양한 크기의 모듈형 상자로 업그레이드하는 것과 같습니다. 이는 다양한 유형의 데이터를 더 자연스럽게 담고 형식을 쉽게 전환할 수 있게 해줍니다. 그러나 논문은 단호하게 명시합니다. 보안에는 여전히 동일한 비용이 듭니다. 즉, 당신은 여전히 메시지만큼 길고 무작위적인 키가 필요합니다. 당신은 유연성을 얻는 것이지, 완벽한 보안을 위한 지름길을 얻는 것이 아닙니다.

기술 요약: 혼합 진법 일회용 패드 (Mixed-Radix One-Time Pad, MR-OTP)

문제 정의
본 논문은 비균등 기수(혼합 진법 수 체계)를 이용한 데이터 표현 및 암호화 문제를 다룬다. 2012년의 한 프리프린트(preprint)에서 감소하는 제수(divisor)를 통해 정수를 분해하는 암호 방식을 소개했으나, 이는 분석적 제약이 까다로운 미완성된 스케치에 불과했다. 핵심 문제는 이 개념을 엄밀한 암호학적 프리미티브로 공식화하고, 비밀 기수(secret bases)를 사용하는 것이 완전한 비밀성(perfect secrecy)을 위한 정보 이론적 키 요구량을 줄일 수 있는지 여부를 결정하는 것이다.

방법론
저자는 기초가 되는 혼합 진법 표현을 공식화하고 **혼합 진법 일회용 패드(MR-OTP)**를 정의한다.

표현: 메시지 $M$ 은 각 위치의 기수가 $b_i \ge 2$ 인 기수 시퀀스 $B = (b_1, \dots, b_L)$ 에 의해 정의된 자릿수 공간 내의 튜플 $(m_1, \dots, m_L)$ 로 취급된다. 메시지는 후속 기수들의 곱으로부터 유도된 위치 가중치를 통해 정수에 대응된다.
암호화: 암호는 자릿수별로 동작한다. 키 $K = (k_1, \dots, k_L)$ 이 키 공간에서 균등하게 무작위로 추출되었을 때, 암호화는 $c_i = (m_i + k_i) \mod b_i$ 로 수행된다.
복호화: 역연산은 $m_i = (c_i - k_i) \mod b_i$ 이다.
분석: 본 논문은 베이즈 정리(Bayes' rule)를 사용하여 메시지에 대한 암호문의 조건부 확률을 분석함으로써 섀넌(Shannon)의 완전한 비밀성 정의를 채택한다. 또한, 기수 $B$ 를 비밀로 취급할 때와 고정된 값으로 취급할 때의 키 공간 엔트로피를 조사한다.

주요 기여

MR-OTP의 공식화: 본 논문은 비트 단위 XOR를 자릿수 단위의 모듈로 $b_i$ 덧셈으로 대체하여, MR-OTP를 혼합 진법 시스템으로의 자연스러운 확장으로 정의한다.
완전한 비밀성 및 정당성 증명:
- 정당성(Correctness): 각 위치에 대해 암호화 맵이 유한 순환 군 $\mathbb{Z}_{b_i}$ 상의 전단사 함수임을 보임으로써 증명된다.
- 완전한 비밀성(Perfect Secrecy): 무작위 키 $K$ 에 대해 메시지 $m$ 에 대한 암호문 $c$ 의 조건부 확률이 $m$ 에 독립적임을 입증함으로써 증명된다. 결과적으로 암호문이 주어졌을 때 메시지의 사후 확률은 사전 확률과 동일하다.
고전적 OTP의 일반화: 본 논문은 모든 $b_i = 2$ 인 경우가 고전적인 이진 OTP의 특수한 사례임을 확립하며, 고정 기수 변형이 임의의 알파벳(예: 라틴 텍스트를 위한 진법 26)에 대한 OTP를 복구함을 보여준다.
"짧은 키" 가설의 해결: 기수 $B$ $B$ 를 비밀 키의 일부로 취급하면 가산 패드(additive pad) $k$ $k$ 를 메시지보다 짧게 유지하면서도 완전한 비밀성을 유지할 수 있다는 가설을 조사한다. 본 논문은 이것이 거짓임을 증명한다.
- 근거: 완전한 비밀성을 위해서는 가산 패드 $k$ 가 모든 위치에서 $\{0, \dots, b_i-1\}$ 전체에 대해 균등하게 분포되어야 한다. 만약 패드가 단축된다면(즉, 메시지 공간의 전체 엔트로피를 커버하지 못한다면), 조건부 확률 $P[C|M]$ 은 $M$ 에 의존하게 되어 완전한 비밀성이 깨진다. 비밀 기수의 엔트로피 $H(B)$ 는 전체 키 엔트로피에 더해질 뿐, 가산 패드에 필요한 엔트로피를 대체할 수 없다.
키 롤링 세션 프로토콜: 공유된 초기 키를 서로 겹치지 않는 세그먼트로 분할하는 실용적인 프로토콜을 제안한다. 각 세션은 가산 패드를 위한 새로운 세그먼트와 다음 세션의 기수를 정의하기 위한 새로운 세그먼트를 사용한다. 이는 완전한 비밀성을 유지하면서도, 데이터의 구조(예: 텍스트를 위한 진법 26)에 맞춰 기수를 조정하여 인코딩 효율성을 높이는 동시에, 소비되는 총 키 재료를 줄이지 않는다.

결과

이론적 경계: MR-OTP는 섀넌의 경계 $|K| \ge |M|$ 를 만족한다. 키 공간과 메시지 공간은 일치하며( $K = D_B = M$ ), 키 재료가 낭비되지 않는다.
엔트로피 계산: 총 키 엔트로피 요구량은 $H(K) = H(B) + H(k|B)$ 이다. 완전한 비밀성을 위해 $H(k|B) \ge H(M)$ 이 요구되므로, 비밀 기수의 포함은서 가산 패드의 엔트로피를 줄이는 것이 아니라 오히려 총 키 엔트로피 요구량을 엄격하게 증가시킨다.
오버헤드: 제안된 세션 프로토콜에서, 기수를 전달하는 오버헤드는 기수 자체를 표현하는 데 필요한 비트에 비해 평균 기수 크기가 클 때 무시할 수 있는 수준이다. 이진 기수( $b_i=2$ )의 퇴보적인 경우, 오버헤드는 패드 길이와 같아 표준 이진 OTP 대비 표현상의 이득이 없다.

의의 및 주장
본 논문은 OTP를 대수적 군론(유한 아벨 군 상의 OTP)과 수 체계와 연결하는 "깔끔한 일반화"를 제공한다고 주장한다. 주요 의의는 다음과 같다:

명확화: 이전의 스케치 형태였던 개념을 엄밀하게 공식화하여, 기존의 "측면 제약(side constraints)"을 제거하였다.
오해의 해소: 비밀 기수가 완전한 비밀성을 위한 정보 이론적 키 요구량을 낮출 수 있다는 생각을 명시적으로 반박하며, 그러한 감소는 섀넌의 증명에 필수적인 균등 분포 가설을 위반한다는 점을 명확히 하였다.
실용적 유용성: 혼합 진법 구조를 키 압축 방법이 아닌 인코딩 효율성 및 적응성을 위한 도구로 위치시킨다. 소스 알파벳(예: DNA 또는 텍스트)에 맞춰 기수를 조정함으로써, 인위적인 이진 변환과 패딩을 피하고, 엄격한 정보 이론적 보안을 유지하면서도 표현 측면에서 더 효율적인 OTP를 구현할 수 있다.

본 논문은 결론에서 비밀 기수를 복구하는 평균 사례의 어려움(average-case hardness)과 구조화된 소스에 대한 최적의 기수 선택에 관한 미결 과제들을 식별하며, 기수 선택 자체의 보안은 정보 이론적이라기보다 계산적(computational) 문제임을 언급한다.