대입-치환 네트워크
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
대입-치환 네트워크(SPN)는 섀넌의 혼돈과 확산 성질을 만족하는 암호 구조이다. SPN은 혼돈과 확산을 통해 키의 변화가 암호문에 복잡한 변화를 일으키고, 평문의 변화가 암호문의 여러 비트에 영향을 미치도록 설계되었다. S-box(치환 계층)와 P-box(순열 계층)를 사용하여 비선형 치환 및 순열 연산을 수행하며, 각 라운드에서는 라운드 키를 XOR 연산으로 결합한다. SPN은 병렬 연산을 통해 알고리즘의 고속화를 가능하게 하지만, 복호화 시 별도의 모듈이 필요하고, 피스텔 네트워크에 비해 분석 실적이 적다는 한계가 있다. AES, ARIA, Serpent 등 많은 블록 암호에서 SPN 구조를 채택하고 있다.
더 읽어볼만한 페이지
- 암호 알고리즘 - 이진 코드
이진 코드는 0과 1을 사용하여 정보를 표현하는 시스템으로, 고대 중국의 주역에서 기원하며, 컴퓨터 과학, 통신 등 다양한 분야에서 활용된다. - 암호 알고리즘 - 메시지 인증 코드
메시지 인증 코드(MAC)는 메시지 무결성을 보장하기 위해 사용되는 암호화 기법으로, 송신자와 수신자가 동일한 키를 공유하여 MAC 생성, 확인 과정을 거친다. - 블록 암호 - 데이터 암호화 표준
데이터 암호화 표준(DES)은 미국 국립표준기술연구소에서 개발되어 널리 사용되었던 대칭키 암호 알고리즘이지만, 짧은 키 길이와 취약점 때문에 고급 암호화 표준(AES)으로 대체되었고, 트리플 DES 형태로 일부 시스템에서 사용되며 암호학 발전에 기여한 역사적 의미가 있다. - 블록 암호 - 고급 암호화 표준
고급 암호화 표준(AES)은 미국 국립표준기술연구소에서 제정한 대칭 키 암호화 블록 암호 표준으로, 치환-순열 네트워크 구조에 기반하여 128비트 블록 크기와 다양한 키 크기를 지원하며, 빠른 속도와 효율성으로 널리 사용된다. - 순열 - 레비치비타 기호
레비치비타 기호는 n차원 공간에서 정의되는 완전 반대칭 텐서로, 순열의 부호에 따라 +1, -1, 0의 값을 가지며 벡터곱, 행렬식 계산 등 다양한 분야에서 활용된다. - 순열 - 완전순열
완전순열은 집합의 순열 중 모든 원소가 원래 위치에 있지 않은 순열, 즉 고정점이 없는 순열을 의미하며, 크기가 n인 집합의 완전순열의 수는 준계승 !n으로 나타내고, 점화식 또는 포함-배제 원리로 계산하며, 몽모르 수라고도 불린다.
| 대입-치환 네트워크 | |
|---|---|
| 대입-치환 네트워크 (SPN) | |
 | |
| 유형 | |
| 암호 | 블록 암호 |
| 설계 원칙 | |
| 기본 원리 | '혼돈' '확산' |
| 구성 요소 | |
| 구성 요소 | 대입 단계 (S-box) 치환 단계 (P-box) |
| 예시 | |
| 예시 | AES 3-Way KHAZAD Square |
2. SPN의 특성
작은 비선형 치환(Substitution)과 이를 처리 블록 단위로 확대하는 전치(Permutation)로 구성된 구조를 SPN 구조라고 부른다. 잘 설계된 SP 네트워크는 S-box와 P-box의 여러 교대 라운드를 통해 섀넌의 혼돈과 확산 속성을 만족시킨다.
- '''혼돈'''은 키의 한 비트 변화가 암호문에 복잡한 변화를 일으키는 성질이다. SPN에서 혼돈은 키의 한 비트를 변경하면 여러 라운드 키가 변경되고, 모든 라운드 키의 변경 사항이 모든 비트에 확산되어 암호문을 매우 복잡한 방식으로 변경하기 때문에 나타난다.
- '''확산'''은 평문의 한 비트 변화가 암호문의 여러 비트에 영향을 미치는 성질이다. 평문의 통계적 성질을 암호문에 분산시켜 암호 해독을 어렵게 만든다. SPN에서 확산은 평문의 한 비트를 변경하면, 이 비트는 S-box에 입력되어 여러 비트에서 출력이 변경되고, 이 변경 사항은 P-box에 의해 여러 S-box로 분산되어 S-box들의 출력도 다시 여러 비트에서 변경되고, 이 과정이 반복되기 때문에 나타난다. 여러 라운드를 거치면서 각 비트는 여러 번 앞뒤로 변경되므로, 결국 암호문은 의사 난수 방식으로 완전히 변경된다.
AES, 하이로크립트, Serpent 등 많은 블록 암호에서 SPN 구조가 채택되고 있다. SPN은 다음과 같은 특성을 갖는다.
- 병렬 연산을 통해 알고리즘을 고속화할 수 있다.
- 한 라운드당 블록 전체가 섞인다.
- 피스텔 구조와 같은 교반성을 얻기 위한 라운드 수가 적게 소요된다.
- 복호화시 별도의 복호화 모듈을 생성해야 한다. 즉, 암호화와 복호화 루틴을 공통화할 수 없어, 코드 사이즈 및 회로 규모 면에서 Feistel 구조보다 구현성이 떨어진다.
- 분석 실적이 적다.
- 라운드 함수의 선택의 자유도가 적다.
공격자가 기지 평문 공격, 선택 평문 공격, 선택 암호문 공격등을 통해 하나의 암호문에 해당하는 평문을 얻더라도, 혼돈과 확산 때문에 공격자가 키를 복구하기는 어렵다.[1]
2. 1. S-box (치환 계층)
S-box는 작은 비트 블록(S-box의 입력)을 다른 비트 블록(S-box의 출력)으로 대체한다. 이 치환은 가역성(따라서 해독)을 보장하기 위해 일대일이어야 한다. 특히, 출력의 길이는 입력의 길이와 같아야 한다.[1] 이는 예를 들어 데이터 암호화 표준 (DES)에서와 같이 길이를 변경할 수도 있는 일반적인 S-box와는 다르다. S-box는 일반적으로 단순한 비트의 순열이 아니다. 오히려, 좋은 S-box에서는 각 출력 비트가 모든 입력 비트의 영향을 받는다. 더 정확하게는, 좋은 S-box에서 각 출력 비트는 모든 입력 비트에 의해 50%의 확률로 변경된다. 각 출력 비트가 50%의 확률로 변경되므로, 실제로 입력 비트 변경에 따라 출력 비트의 약 절반이 변경된다(엄격한 눈사태 기준).[1]암호에 요구되는 성질 중 하나는 암호문에서 평문을 복호화할 수 있다는 것(복호 가능성)인데, 작은 비선형 치환(Substitution)은 전단사 함수여야 한다. (이 때문에 치환의 입력 비트 수와 출력 비트 수는 동일해야 한다.)
2. 2. P-box (순열 계층)
P-box(순열 상자)는 모든 비트의 순열이다. P-box는 한 라운드의 모든 S-box의 출력을 받아 비트를 섞어 다음 라운드의 S-box 입력으로 전달한다. 좋은 P-box는 각 S-box의 출력 비트가 가능한 한 많은 S-box 입력에 분산되도록 설계된다.[1]2. 3. 라운드 키
각 라운드에서 라운드 키는 주 키에서 얻어지며, 일반적으로 XOR 연산을 통해 S-box 및 P-box의 출력과 결합된다. 라운드 키는 주 키로부터 S-box와 P-box를 사용하는 등의 간단한 연산을 거쳐 생성된다.[1]3. 관련 알고리즘
SPN 구조는 AES, ARIA, 3-Way, SAFER, SHARK, 하이로크립트, Serpent 등 많은 블록 암호에서 채택되고 있다.
4. 피스텔 네트워크와의 비교
피스텔 네트워크(DES)는 S-box를 사용하여 대입-치환 네트워크(SPN)와 매우 유사하지만, 몇 가지 차이점이 있다. 주어진 양의 혼돈과 확산에 대해 SPN은 더 많은 "내재적 병렬성"[2]을 가지므로, 많은 실행 유닛을 가진 CPU에서는 피스텔 네트워크보다 더 빠르게 계산할 수 있다.[3] 그러나 대부분의 스마트 카드와 같이 실행 유닛이 적은 CPU는 이러한 내재적 병렬성을 활용할 수 없다. 또한 SPN은 S-box가 가역적이어야 하지만, 피스텔 내부 함수는 그러한 제약이 없으며 일방향 함수로 구성될 수 있다.
5. 한계
Feistel 구조에 비해 분석 실적이 적다.[1] 라운드 함수 선택의 자유도가 낮으며,[1] 암호화와 복호화 루틴을 공통화할 수 없어 코드 크기나 회로 규모 면에서 소프트웨어나 하드웨어 구현성이 떨어진다.[1]
참조
[1]
서적
Advances in Cryptology – Crypto '85
Springer-Verlag New York, Inc.
[2]
웹사이트
Principles and Performance of Cryptographic Algorithms
http://www.ddj.com/1[...]
[3]
간행물
The Skein Hash Function Family
http://www.schneier.[...]
2009-01-15
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com