SubBytes (r1)

1. 개요

SubBytes는 AES 암호화 알고리즘의 핵심 구성 요소 중 하나로, 각 암호화 라운드에서 상태 배열의 각 바이트를 비선형적으로 치환하는 연산이다. 이 연산은 암호의 안전성에 결정적인 역할을 하는 비선형성을 제공하여, 선형 암호해독 및 차분 암호해독과 같은 공격에 대한 저항성을 강화한다.

SubBytes 연산은 각 암호화 라운드의 시작 부분에서 실행되며, 16바이트로 구성된 상태 배열의 모든 바이트에 독립적이고 동일하게 적용된다. 입력으로 들어오는 8비트 데이터는 사전에 정의된 치환 규칙에 따라 완전히 다른 8비트 값으로 변환되어 출력된다. 이 치환 규칙은 고정된 룩업 테이블인 S-박스에 의해 정의된다.

SubBytes의 수학적 기반은 유한체 GF(2⁸) 상의 연산이다. 구체적으로, 입력 바이트에 대해 먼저 역원을 계산한 후, 이 결과에 대해 미리 정해진 아핀 변환을 적용하는 과정으로 구성된다. 이 조합된 연산은 결과적으로 높은 비선형성을 갖는 치환 테이블을 생성한다.

이 연산은 암호화의 혼돈 성질을 구현하는 주요 수단이며, AES의 안전성 견고성에 기여하는 필수적인 단계이다. 복호화 과정에서는 이 연산의 역함수인 InvSubBytes가 동일한 위치에서 적용되어 원래의 바이트 값을 복원한다.

2. S-박스 (치환 상자)

2.1. 구성 원리

SubBytes 연산의 핵심 구성 요소는 S-박스(S-box)이며, 이는 미리 계산된 256개의 값으로 이루어진 치환 테이블입니다. 이 테이블은 0x00부터 0xFF까지의 모든 가능한 8비트 입력값에 대해 고유한 8비트 출력값을 정의합니다. 암호화 과정에서는 State 배열의 각 바이트가 이 테이블을 참조하여 새로운 값으로 일대일 대응되며, 이 과정은 전체 State에 대해 병렬적으로 수행됩니다.

S-박스의 구성은 두 단계의 수학적 연산을 결합하여 이루어집니다. 첫 번째 단계는 입력 바이트를 유한체 GF(2⁸) 상에서의 역원으로 변환하는 것입니다. 구체적으로, 입력값이 0이 아닌 경우 그에 대한 곱셈 역원을 계산하고, 입력값이 0인 경우 그 역원도 0으로 정의합니다. 이 역원 계산은 연산의 비선형성을 만드는 근본적인 원천입니다.

두 번째 단계는 이렇게 얻은 역원 값에 대해 아핀 변환을 적용하는 것입니다. 이 변환은 GF(2) 상에서의 행렬 곱셈과 벡터 덧셈(즉, XOR)으로 구성되어 있으며, 결과값에 추가적인 비선형 특성을 부여하고 S-박스의 출력에서 고정점을 제거하는 역할을 합니다. 이 두 단계의 조합은 암호학적으로 매우 안전한 비선형 치환 매핑을 생성합니다.

이러한 설계 원리로 인해 AES의 S-박스는 높은 비선형성을 가지며, 차분 균일도가 낮고 대수적 차수가 높은 특성을 보입니다. 이는 선형 암호해독 및 차분 공격과 같은 암호 분석 기법에 대한 강력한 저항성을 제공하는 데 기여합니다.

2.2. 수학적 연산

SubBytes 연산의 핵심은 유한체 갈루아 체(GF(2⁸)) 상에서의 수학적 연산이다. 이 연산은 크게 두 단계로 구성된다. 첫 번째 단계는 입력 바이트를 유한체 GF(2⁸)의 원소로 간주하여 역원을 계산하는 것이다. 여기서 0x00의 역원은 그 자체로 정의된다. 이 역원 계산은 연산의 비선형성을 결정짓는 가장 중요한 부분이다.

두 번째 단계는 계산된 역원 값에 대해 아핀 변환을 적용하는 것이다. 이 변환은 GF(2) 상에서의 행렬 곱셈과 벡터 덧셈으로 이루어지며, 특정 상수 행렬과 상수 벡터가 사용된다. 이 아핀 변환은 S-박스의 대수적 구조를 더욱 복잡하게 만들어 암호학적 안전성을 강화하는 역할을 한다. 전체 과정은 역원 계산 후 아핀 변환을 적용하는 순서로 진행되며, 이 조합이 AES의 강력한 비선형 치환 테이블을 생성한다.

역 SubBytes 연산은 이 과정을 정확히 역으로 수행한다. 먼저 주어진 출력 바이트에 역 아핀 변환을 적용한 후, GF(2⁸) 상에서 다시 역원을 구하면 원래의 입력 바이트를 복원할 수 있다. 이 수학적 구조는 암호화와 복호화 모두에 대해 명확하고 효율적인 연산을 가능하게 한다.

3. 역 SubBytes (InvSubBytes)

역 SubBytes는 AES의 복호화 과정에서 사용되는 연산으로, 암호화 시 수행된 SubBytes 연산의 효과를 취소하기 위해 설계되었다. 이 연산은 암호화의 각 라운드 후반에 위치하는 InvSubBytes 단계에서 실행되며, 암호화된 State 배열의 각 바이트를 원래의 값으로 되돌리는 역할을 한다. 복호화는 암호화의 역순으로 진행되므로, InvSubBytes는 암호화 라운드의 마지막 단계들 중 하나를 구성한다.

InvSubBytes의 수학적 연산은 SubBytes와 정확히 역의 관계에 있다. SubBytes 연산이 유한체 GF(2⁸) 상에서 역원을 구한 후 아핀 변환을 적용하는 조합이라면, InvSubBytes는 먼저 역 아핀 변환(Inverse Affine Transformation)을 적용한 후, 동일한 유한체 상에서 다시 역원을 계산하는 방식으로 구성된다. 이는 SubBytes에 사용된 S-박스가 수학적으로 가역적이어야 복호화가 가능하기 때문이며, AES의 구조는 이러한 완전한 가역성을 보장한다.

구현 측면에서 InvSubBytes는 일반적으로 별도의 역 S-박스(Inverse S-Box) 룩업 테이블을 사용하여 수행된다. 암호화용 S-박스 테이블과는 다른 매핑 값을 저장한 이 테이블을 통해, 각 입력 바이트에 대한 출력 값을 즉시 얻을 수 있어 소프트웨어 및 하드웨어 구현에서 효율성을 높인다. 이는 복호화 성능을 암호화 성능에 버금가게 만드는 핵심 요소 중 하나이다.

역 SubBytes 연산은 암호화의 SubBytes와 마찬가지로 비선형성을 제공하지만, 그 목적은 복호화 과정에서의 정확한 역변환을 보장하는 데 있다. 이를 통해 AES는 대칭키 암호의 기본 요구사항인 정확한 암호화와 복호화를 완벽하게 충족시키며, 전체 알고리즘의 안전성과 구조적 일관성을 유지한다.

4. 암호학적 중요성

SubBytes 연산은 AES의 암호학적 안전성에서 가장 핵심적인 역할을 담당한다. 이 연산의 주된 목적은 암호에 강력한 비선형성을 주입하는 것이다. 대부분의 현대 블록 암호는 라운드 함수 내에 비선형 구성 요소를 포함하는데, SubBytes가 바로 AES에서 그 역할을 수행한다. 만약 암호 연산이 완전히 선형적이라면, 입력과 출력 간의 관계가 간단한 방정식으로 표현될 수 있어 암호문과 평문, 키 사이의 복잡한 관계를 쉽게 파악할 수 있게 된다. SubBytes는 이러한 선형적 관계를 단절시켜 선형 공격과 같은 대수적 공격을 효과적으로 방어한다.

또한 SubBytes는 차분 공격에 대한 저항성을 높이는 데에도 기여한다. 차분 공격은 특정 입력 차이에 따른 출력 차이의 패턴을 분석하여 키를 찾아내는 방법이다. SubBytes에서 사용되는 S-박스는 입력 차이에 따른 출력 차이의 분포가 균일하고 예측하기 어렵도록 설계되었다. 이는 차분 특성의 전파를 무작위화하고, 공격자가 유효한 차분 경로를 구성하는 것을 매우 어렵게 만든다.

요약하면, SubBytes는 AES의 안전성 기반을 형성하는 비선형 층이다. 이 연산이 제공하는 높은 비선형성과 우수한 차분 특성은 선형 공격 및 차분 공격을 포함한 다양한 암호해독 기법에 대한 강력한 방어벽이 된다. 따라서 SubBytes의 설계는 암호학적으로 신중하게 검증되었으며, AES가 널리 신뢰받는 표준 암호로 자리 잡는 데 결정적인 기여를 했다.

5. 구현

5.1. 룩업 테이블

SubBytes 연산을 소프트웨어에서 효율적으로 구현하는 가장 일반적인 방법은 룩업 테이블을 사용하는 것이다. 이는 사전 계산된 S-박스의 모든 입력값(00부터 FF까지 256개)에 대한 출력값을 메모리에 저장해 놓고, 암호화 과정에서 필요한 바이트 치환을 단순한 메모리 접근(테이블 조회)으로 수행하는 방식이다.

구현 시, 256바이트 크기의 정적 배열(예: unsigned char SBox[256])을 생성하여 상수 데이터로 포함시킨다. 암호화 과정에서는 State 배열의 각 바이트 값을 이 테이블의 인덱스로 사용하여 치환된 값을 즉시 얻는다. 이 방법은 복잡한 유한체 상의 역원 계산과 아핀 변환을 런타임에 수행하는 것에 비해 속도가 매우 빠르다는 장점이 있다.

구현 방식	설명	장점	단점
단일 룩업 테이블	256바이트 테이블을 조회	구현이 간단하고 속도가 빠름	메모리 접근 패턴이 예측 가능할 수 있음
결합된 테이블 (T-테이블)	MixColumns 연산과 결합된 큰 테이블 사용	라운드 연산 전체를 가속화 가능	메모리 사용량이 큼(일반적으로 4KB 또는 16KB)

룩업 테이블 방식은 AES가 널리 채택되는 데 기여한 핵심적인 구현 최적화 기법 중 하나이다. 그러나 사이드 채널 공격 중 하나인 캐시 타이밍 공격에 취약할 수 있다는 점이 지적된다. 공격자는 특정 바이트를 치환할 때 테이블의 어떤 부분이 캐시 메모리에 로드되는지를 관측하여 키 정보를 유추할 수 있기 때문이다. 이를 방지하기 위해 상수 시간에 실행되는 비트 연산 기반 구현이나 마스킹 기법이 사용되기도 한다.

5.2. 하드웨어 구현

하드웨어에서 SubBytes 연산을 구현하는 방식은 성능, 면적, 전력 소비 등 설계 목표에 따라 다양하다. 가장 일반적인 방법은 미리 계산된 S-박스 값을 저장하는 ROM(Read-Only Memory)이나 SRAM(Static RAM)을 사용하는 룩업 테이블 방식이다. 이는 높은 처리 속도를 제공하지만, 회로 면적과 메모리 용량을 차지한다는 단점이 있다.

면적 최적화가 중요한 임베디드 시스템이나 저전력 장치에서는 S-박스를 논리 회로로 합성하여 구현하기도 한다. 이는 유한체 GF(2⁸)에서의 역원 계산과 아핀 변환을 조합 논리 회로로 직접 구현하는 방식으로, 룩업 테이블에 비해 회로 면적을 줄일 수 있다. 그러나 계산에 필요한 게이트 지연으로 인해 순수 룩업 테이블 방식보다 처리 속도가 느려질 수 있다.

고성능을 요구하는 응용 분야, 예를 들어 고속 네트워크 암호화 장치나 GPU 기반 가속에서는 파이프라이닝 기법과 병렬 처리를 활용한다. 여러 개의 S-박스 유닛을 병렬로 배치하거나, SubBytes 단계를 여러 개의 파이프라인 스테이지로 분할하여 전체 AES 암호화의 처리량을 극대화한다.

구현 방식	주요 장점	주요 단점	적합한 응용 분야
룩업 테이블 (ROM/SRAM)	속도가 매우 빠름	회로 면적과 메모리 사용량이 큼	고속 암호화, 일반 목적 프로세서
조합 논리 회로	회로 면적이 작음	상대적으로 속도가 느림	임베디드 시스템, 저전력 장치
병렬 및 파이프라인 처리	처리량(Throughput)이 매우 높음	하드웨어 복잡도와 전력 소비가 증가	네트워크 장비, 암호화 가속기

SubBytes

정의	AES(Advanced Encryption Standard) 암호화 알고리즘의 라운드 함수에서 사용되는 비선형 바이트 치환 연산입니다.
역할	암호의 비선형성(Nonlinearity)을 제공하여 선형 및 차분 공격에 대한 저항성을 높입니다.
작동 위치	AES의 각 암호화 라운드 시작 시, State 배열의 각 바이트에 독립적으로 적용됩니다.
수학적 기반	유한체 GF(2⁸) 상에서의 역원 계산과 아핀 변환(Affine Transformation)의 조합입니다.
입출력	8비트 입력 바이트 하나를 8비트 출력 바이트 하나로 변환합니다.
상세 정보
연산 단계	1. 입력 바이트를 GF(2⁸)의 원소로 간주하여 곱셈에 대한 역원을 구합니다. (0x00의 역원은 그自身 0x00으로 정의) 2. 구한 역원에 대해 미리 정의된 아핀 변환을 적용합니다.
구현 방식	연산을 매번 수행하는 대신, 256개의 가능한 모든 입력(0x00~0xFF)에 대한 출력 값을 미리 계산하여 고정된 치환 테이블(S-Box)로 저장하고 참조하는 방식이 일반적입니다.
역연산	복호화 과정에서는 역 S-Box(Inverse S-Box)를 사용하며, 이는 아핀 역변환 후 역원을 구하는 과정에 해당합니다.
보안 목적	암호문과 평문, 암호키 간의 관계를 복잡하게 만들어 통계적 분석을 어렵게 합니다.
AES에서의 중요성	AES의 라운드 함수를 구성하는 네 가지 변환(SubBytes, ShiftRows, MixColumns, AddRoundKey) 중 유일한 비선형 변환입니다.