KR20020041815A - 대칭-키 암호에 대한 선형 변환 - Google Patents

Abstract

대칭-키 암호에 사용하기 위한 선형 변환 매트릭스(A)를 생성하는 방법은 이진 [n,k,d] 에러-정정 코드를 생성하는 단계를 포함하는데, 여기서, k<n<2k이고, d는 이진 에러-정정 코드의 최소 거리이다. 상기 코드는 표준형 G=(I_k|B)(B∈Z₂ ^k×(n-k))로 생성기 매트릭스 G∈Z₂ ^k×n로 표시된다. 결과 매트릭스(C)가 정칙 행렬이 되도록 2k-n 컬럼들로 매트릭스(B)가 확장된다. 선형 변환 매트릭스(A)는 매트릭스(C)로부터 유도된다. 바람직하게, 에러 정정 코드는 XBCH 코드에 기초한다.

Description

대칭-키 암호에 대한 선형 변환{Linear transformation for symmetric-key ciphers}

디지털 오디오 및/또는 비디오의 복제 방지 분야에서의 암호화의 응용은 점점 더 중요해지고 있다. 이러한 응용들은 컨텐츠 암호화/암호 해독 및 액세스 관리 기능들을 포함한다. 이와 같은 응용들에 있어서는 블록 암호들이 사용될 수 있다. 블록 암호들의 공지되어 있는 패밀리로는 페이스텔(Feistel) 암호들이 있다. 페이스텔 암호에서, 입력 데이터 블록은 다수의 라운드들(rounds)로 처리된다. 각 라운드에서, 블록의 2개의 서브-블록들(1/2)은 서로 다르게 동작된다. 제 1 서브-블록은 라운드 함수의 출력과 결합되고, 제 2 서브-블록은 변경되지 않는다. 라운드의 끝에서, 2개의 서브-블록들이 교환되어, 변경되지 않은 서브-블록이 다음 라운드에서 처리되도록 한다. 라운드 함수는 제 2 서브-블록과 라운드 키를 입력으로서 취한다. 정상적으로, 라운드 함수는 라운드 키와 제 2 서브-블록을, 예를 들어, XOR 연산을 사용하여 결합한다. 부가적으로, 라운드 함수는 제 2 서브-블록에서 비선형 동작과 선형 변환을 수행한다. 통상적으로, 비선형 변환은, 예를 들어, 4 내지 8 비트의 더 작은 서브-블록들에서 병렬로 동작하는 다수의 S-박스들(substitution boxes)로 이루어지는 S-박스(substitution box) 층으로 이루어진다. S-박스 층 다음에, 선형 동작은, 개개의 S-박스들에 의해 야기된 비트 변경들이 다음 라운드(들)에서 가능한 한 많은 S-박스들에 전파되도록 적절한 확산이 발생할 수 있도록 한다.

페이스텔 암호의 공지되어 있는 예로는 16 라운드들로 이루어지는 DES가 있다. 각 라운드에서, 데이터의 오른쪽 절반의 첫 번째 32비트가 48비트로 확장된다. 다음에, 키 스케쥴링 알고리즘에 의해 56비트 DES 키로부터 계산되는 48비트 라운드 키는 상기 48비트에 모듈로 2(module two) 가산된 비트형이다. 이어서, S-박스들의 층이 데이터에 대해 비선형 동작을 수행한다. DES에서, S-박스 층은 6×4비트 S-박스들이 병렬로 구성되어 있으며, S-박스들 각각은 S-박스당 하나의 고정 매핑 테이블을 사용하여 6-비트 입력 블록을 4-비트 출력 블록으로 변환한다. S-박스 층의 출력은 32비트 데이터 블록이다. 이 32비트 데이터 블록에서 수행되는 선형 변환은 비트-순열(bit-permutation)이며, S-박스에 의해 야기된 비트 변경들이 후속 라운드(들)에서 다수의 다른 것들을 통해 전파될 수 있도록 한다. DES의 결점은 오늘날의 고레벨 보안을 제공하기 위해서는 불충분한 것으로 여겨지는 56비트의 작은 키 크기이다. 그러나, 16개의 48-비트 라운드 키들을 계산하기 위한 상이한 키 스케쥴링 알고리즘과 결합된 더 긴 키를 사용함으로써 소모적인 키 탐색을 피할 수 있다. 공개된 문헌에 공개되어 있는 DES 상에서의 2개의 가장 강력한 실행들(attacks)은 차동 및 선형 암호 해독이며, 이는 광범위한 블록 암호들에 적용될 수 있는 일반적인 실행들이다. DES는 키 길이 및/또는 키-스케쥴링 알고리즘을 수정함으로써 이러한 실행들에 대해 그다지 강화될 수 없다는 것이 알려져 있다. 그러나, 알고리즘의 라운드 함수에서의 변경들은 상기 실행들에 대해 그 강도에 상당히 영향을 미칠 수 있다.

선형 변환에 있어서, 이 변환은 양호한 확산 속성들을 갖는 것이 바람직하다. 최근에, 선형 변환들을 구성하기 위한 선형 에러-정정 코드들에 사용하기 위해 제안된 에스. 바우데네이(S. Vaudenay)의 기술은 "멀티-순열들에 대한 필요성에 대하여 : MD4 및 SAFER의 암호 해독(On the Need for Multi-Permutations: Cryptanalysis of MD4 and SAFER)", 신속한 소프트웨어 암호화(2^nd), LNCS 1008, 스프링거(Springer), 1995, pp.286-297에서 알 수 있다. 선형 변환의 확산 속성들은 대응 에러-정정 코드의 최소 해밍 거리(minimum Hamming distance), 최고의 해밍 거리 및 연관된 선형 변환 매트릭스의 최상의 확산 속성들과 관련된다. 바우데네이는 한정된 필드들 상에서의 MDS(Maximum Distance Separable) 코드들의 사용을 제안하고 있으며, 이는 소위 싱글톤(Singleton) 경계에 도달하여 최적의 확산을 제공한다. 그러나, 이 구성은 결과 선형 변환이, 암호 해독에 부당하게 이용될 수 있는 부가적인 수학적 구조, 예를 들어, 구성을 위해 사용된 한정된 필드(및 모든 그 서브-필드들) 상의 선형성을 포함한다는 결점을 갖는다.

본 발명은 이진 에러-정정 코드에 기초한 대칭-키 암호에 사용하기 위한 선형 변환을 발생시키는 방법에 관한 것이다.

도 1은 암호화 시스템의 블록도.

도 2a 및 도 2b는 선형 변환을 포함하는 암호의 한 라운드를 도시하는 도면.

도 3은 라운드 함수의 단계들을 도시하는 도면.

도 4는 S-박스 구성의 바람직한 배치를 도시하는 도면.

도 5는 선형 변환 매트릭스를 생성하는 단계들을 도시하는 도면.

본 발명의 목적은 최적의 이진 선형 에러-정정 코드에 기초한 비트-레벨에 대한 보장된 최적의 확산 특징들을 갖는 대칭-키 암호들에 사용하기 위한, 정칙 행렬(non-singular) 이진 매트릭스로 표시되는 반전가능한(invertible) 선형 변환을 제공하는 것이다. 이 변환은, 암호 해독시 부당하게 사용될 수 있는 결과 선형 변환의 부가적인 수학적 구조가 회피된다는 점에서, 더 불규칙적인 MDS 구성에 대해 이점을 갖는다.

본 발명의 목적을 달성하기 위해서, 에러-정정 코드로부터 유도된 매트릭스가 다수의 컬럼들로 확장되어, 코드의 길이가 2배의 치수와 같아지도록 하며, 선형 변환에 대한 기초로서 사용될 수 있는 결과 매트릭스가 정칙 행렬이 되도록 한다. 이것은 라운드 함수의 비균일성에 기초한 실행들을 회피한다.

종속항인 2항에 한정된 바와 같이, 적절한 컬럼들을 찾기 위해서 새로운 컬럼들이 (의사-)랜덤하게((pseudo-)randomly) 생성될 수 있다.

종속항인 3항에 한정된 바와 같이, 매트릭스(C)는 미리 결정된 멀티-비트 가중치를 갖는 관련된 선형 에러-정정 코드를 갖는 선형 변환 매트릭스를 찾기 위해 순열 배치된다. 종속항인 4항에 한정된 바와 같이, 이 멀티-비트 가중치는 암호의 S-박스들에서의 적절한 확산을 보장한다. 예를 들어, 각 S-박스가 m-비트 출력을 제공하는, 병렬로 동작하는 다수의 S-박스들로 구성되는 S-박스 층에 있어서, 이는 관련된 이진 에러-정정 코드에서 워드들의 m-비트 부분들의 확산을 찾는 것과 관련되며, 모든 0이 아닌 코드워드들에 관한 최소 m-비트 가중치로 표현될 수 있다.

본 발명의 상기 및 다른 특징들은 도면에 도시된 실시예들을 참조하여 설명되며, 그로부터 명백해질 것이다.

설명된 본 발명의 목적을 위해서, 선형 변환이 사용되는 암호화 시스템은 전자 코드북(ECB, Electronic Codebook) 모드에서 블록 암호로서 설명된다. 이 기술분야에 숙련된 사람들은 다른 모드들에서도 암호화 시스템을 사용할 수 있을 것이다. 이것은 DES에 대한 동작들의 표준 FIPS 모드들, 즉, 동작의 암호 블록 체이닝(CBC, Cipher Block Chaining) 모드, 암호 피드백(CFB, Chipher Feedback) 모드 및 출력 피드백(OFB, Output Feedback) 모드를 포함한다. 또한, 이 시스템은 의사-랜덤 번호 생성기들, 메시지 인증 코드들(MACs, Message Authentication codes) 및 조작 검출 코드들(MDCs, Manipulation Detection Codes)에 대한 공지되어 있는 구성들에 사용될 수도 있다.

도 1은 예시적인 암호화 장치(100)의 블록도를 도시한다. 암호화 장치(100)는 디지털 입력 블록(X)을 얻기 위한 입력(110)을 포함한다. 디지털 입력 블록(X)은 임의의 적절한 크기일 수도 있다. 암호화 장치는 디지털 입력 블록(X)을 디지털 출력 블록(E(X))으로 변환하기 위한 암호화 처리기(120)를 더 포함한다. 유리하게, 디지털 출력 블록은 디지털 입력 블록과 실질적으로 같은 길이를 갖는다.암호화 장치(100)는 디지털 출력 블록을 출력하기 위한 출력(130)을 포함한다. 바람직한 실시예에서, 암호화 처리기는 디지털 입력 블록과 키 비트들(K)을 병합함으로써 디지털 입력 블록을 디지털 출력 블록으로 변환하여, 입력 블록(X)과 키(K)에 비선형적으로 의존하는 출력 블록(E(X, K))을 생성한다. 키(또는 키 스케쥴러를 공급하는 초기 키)를 얻기 위해서, 암호화 장치는 제 2 입력(140)을 포함한다. 암호화 장치는 PC와 같은 종래의 컴퓨터를 사용하여, 또는 전용 암호화/암호 해독 장치를 사용하여 구현될 수도 있다는 것이 인식될 것이다. 디지털 입력 블록은 통신 네트워크를 통해서 하드디스크 또는 플로피디스크와 같은 데이터 저장 매체로부터 다양한 방식들로 얻어지거나, 또는 사용자에 의해 직접 입력될 수도 있다. 마찬가지로, 디지털 출력 블록은 통신 네트워크를 통해 다양한 방식들로 데이터 저장 매체 상에 저장되도록 출력되거나, 또는 사용자에게 디스플레이될 수도 있다. 바람직하게, 보안 수단이 이 종단에 사용된다. 암호화 처리기는, 예를 들어, 퍼스널 컴퓨터들에 사용되는 것과 같은 종래의 처리기일 수도 있지만, 전용 암호화 처리기일 수도 있다. 처리기는 일반적으로 본 발명에 따른 알고리즘의 단계들을 수행하기에 적절한 프로그램(펌웨어)의 제어 하에서 동작된다. 이 컴퓨터 프로그램 제품은 일반적으로 하드디스크 또는 ROM과 같은 백그라운드 저장 장치로부터 로딩된다. 컴퓨터 프로그램 제품은 공개 인터넷과 같은 네트워크를 통해서 CD-ROM과 같은 저장 매체 상에 분배된 후에 백그라운드 저장 장치 상에 저장될 수 있다. 암호화 키와 같은 민감한 정보는 안전한 방법으로 분배되고 저장되는 것이 바람직하다. 이를 행하기 위한 기술들은 일반적으로 공지되어 있으며 더 설명되지는 않는다. 암호화 장치는 전체적으로 또는 부분적으로 스마트-카드(smart-card) 상에 구현된다.

암호화 처리기에 의해 수행되는 본 발명에 따른 선형 변환은 예시적인 응용인 블록 암호에서 라운드 함수(f)의 형태로 설명될 것이다. 본질적으로, 이 기술분야에 숙련된 사람들은 다른 암호화 시스템들에서 및 이하 설명되는 것 외의 다른 암호들에서 선형 변환을 사용할 수 있을 것이다.

표기법 및 정의

다음 표기법은 예시적인 알고리즘의 설명에 사용된다. Z₂ ⁿ은, 가산: Z₂ ⁿx Z₂ ⁿ→ Z₂ ⁿ(좌표형(coordiate-wise) 가산 모듈로 2(XOR(exclusive-or)라고도 함)로서 정의됨)에 대한 길이 n(n≥1)의 모든 이진 벡터들의 세트라고 하자. 예를 들어, (1,0,1,0) 및 (0,1,1,0)은 Z₂ ⁴의 성분들이며, (1,0,1,0)(0,1,1,0)=(1,1,0,0)이다. 또한, 스칼라 곱 · : Z₂x Z₂ ⁿ→ Z₂ ⁿ은 모든 x∈Z₂ ⁿ에 대해서 1·x=x이고 0·x=(0,0,...,0)∈Z₂ ⁿ으로서 정의된다. n이 짝수이고 x∈Z₂ ⁿ이라면, x^(L)∈Z₂ ^n/2및 x^(R)∈Z₂ ^n/2가 각각 왼쪽 절반 및 오른쪽 절반으로서 정의된다. 예를 들어, x=(1,0,1,1,0,0,1,0)∈Z₂ ⁸이라면, x^(L)=(1,0,1,1)∈Z₂ ⁴및 x^(R)=(0,0,1,0)∈Z₂ ⁴이다. 기호 ∥는 벡터들의 연결(예를 들어, x=(x^(L)∥x^(R)))을 표시하기 위해 사용된다. 벡터 x∈Z₂ ⁿ의 성분들(비트들이라고도 함)은 왼쪽에서 오른쪽으로 0부터 n-1까지 번호가 매겨진다(즉, x=:(x₀,x₁,x₂,...,x_n-1)). 두 성분들 x∈Z₂ ⁿ와 y∈Z₂ ⁿ사이의 해밍 거리(d_H) : Z₂ ⁿx Z₂ ⁿ→ Z는 2개의 벡터들이 서로 다른 다수의 좌표들의 수로서 정의된다(즉, d_H(x,y)=#{x_i≠y_i|i=0,1,...,n-1}). 성분 x∈Z₂ ⁿ의 해밍 가중치 w_H: Z₂ ⁿ→Z는 0이 아닌 좌표들의 수로서 정의된다(즉, w_H(x)=#{x_i≠0|i=0,1,...,n-1}).

Z₂상의 k×m 매트릭스들의 세트(k, m≥1)는 Z₂ ^k×m으로 표시된다. Z₂상의 k×k 단위 매트릭스는 I_k로 표시된다. 기호 ∥는 또한 동일한 개수의 로우들을 갖는 매트릭스들의 연결을 표시하기 위해 사용된다(예를 들어, A∈Z₂ ^4×6및 B∈Z₂ ^4×8이면, C:=(A∥B)∈Z₂ ^4×14이다).

(블록) 길이(n)의 이진 에러-정정 코드(C)는 Z₂ ⁿ의 선형 서브공간이다. 이 서브공간의 성분들은 코드워드들이라고도 한다. 서브공간의 차원이 k이면, C는 [n,k] 코드라고 한다. 이와 같은 코드는, C에 대한 기초를 형성하는 로우들에 대해서, 생성기 매트릭스 G∈Z₂ ^k×n로 표시될 수 있다(즉, C={mG|∈Z₂ ^k}). 코드의 최소거리(d)는 임의의 2개의 별개의 코드워드들간의 모든 거리들에 대해 최소치로서 정의된다(즉, d=min{d_H(x,y)|x,y∈C 및 x≠y}). 또한, 최소 해밍 거리(d)를 갖는 [n,k] 코드는 [n,k,d] 코드로서 언급된다. d_H(x,y)=w_H(xy)는, 선형 코드의 최소 해밍 거리가 모든 0이 아닌 코드워드들에 대한 최소 해밍 가중치와 같다는 것을 의미한다는 것을 유념해야 한다.

블록 암호 구조

예시적인 블록 암호로서는 페이스텔 암호가 있으며, 이는 16개의 (DES와 같은) 라운드들로 이루어진다. 블록 길이는 64비트와 같으며, 키 길이는 128비트와 같다. 키 K∈Z₂ ¹²⁸하에서 플레인텍스트(plaintext) X∈Z₂ ⁶⁴의 전자 코드북(ECB) 모드의 그 암호텍스트(ciphertext) C∈Z₂ ⁶⁴로의 암호화는 C=E(K,X)로 나타낸다.

라운드 함수는 f로 나타내며, Z₂ ⁴⁰x Z₂ ³²로부터 Z₂ ³²까지의 매핑이다. 이 라운드 함수는 본 발명의 선형 변환을 포함하며, 이하 더 상세히 설명될 것이다. 라운드 함수의 제 1 입력 인자는 라운드 키 K_i∈Z₂ ⁴⁰(여기서, i는 라운드 번호를 나타내며, i=1,2,...,16)이다. 이 라운드 키들은 소위 키 스케쥴링 알고리즘에 의해 128비트의 키(K)로부터 계산된다. 임의의 적절한 키 스케쥴링 알고리즘이 사용될 수도 있으며, 설명하지는 않을 것이다. 제 2 입력 인자는 라운드 i 이후의 중간 결과의 오른쪽 절반이다. 이 중간 결과는 X_i∈X₂ ⁶⁴(i=0,1,...,16)(X=:X₀ ^(R)∥X₀ ^(L))으로 나타낸다.

이 표기에서, 암호텍스트(C∈Z₂ ⁶⁴)의 계산은 도 2에 도시된 바와 같은 다음 단계들로 이루어진다.

1. X_i ^(R)=X_i-1 ^(L) f(K_i,X_i-1 ^(R))을 계산하고, i=1,2,...,15에 대해 X_i ^(L)=X_i-1 ^(R)를 설정한다.

2. X₁₆ ^(L)=X₁₅ ^(L) f(K₁₆,X₁₅ ^(R))을 계산하고, X₁₆ ^(R)=X₁₅ ^(R)을 설정한다. 암호텍스트는 C:=(X₁₆ ^(L)∥X₁₆ ^(R))로서 정의된다.

도 2a는 처음 15개의 라운드들(i=1,2,...,15)에 대해 사용되는 암호 구조를 도시한다. 도 2b는 마지막 16번째의 라운드를 도시한다. 도 2b의 불규칙한 교환은 도 2a의 이전 라운드들과 비교된다. 이것은 일반적으로 페이스텔 구조들에서 행해지는데, 이는 이 경우에 암호 해독 알고리즘(즉, X=E^-1(K,C)의 계산)이 (반대 순서로 라운드 키들을 갖는) 암호화 알고리즘과 동일하기 때문이다. 이것은 암호화 관점에서 어떠한 의미도 갖지 않는다.

라운드 함수

도 3은 라운드 함수(f)의 바람직한 실시예의 전체 블록도를 도시한다. 먼저, 예를 들어, 32비트의 라운드 키의 일부분이 단계 310에서 데이터 비트들에 가산된다. 다음으로, 단계 320에서, S-박스들은 비선형 치환을 수행하여, 바람직하게는 차동 선형 암호 해독에 대한 최적의(로컬) 저항을 제공한다. 또한, 바람직하게, 미리 결정된 최대 확률을 갖는 비-트리비얼(non-trivial)(로컬) 특징들은 이하 더 상세히 설명되는 바와 같이 (라운드) 키 종속을 이룬다. 마지막으로, 단계 330에서, 다수의 라운드들에 대해 고 확산을 제공하기 위해 선형 변환이 사용된다. 에러-정정 코드로부터의 이러한 선형 변환을 발생시키는 방법이 이하 더 상세히 설명될 것이다.

페이스텔 구조는 주관적인 라운드 함수에 대해 어떠한 제한도 두지 않는다. 그러나, 바람직하게, 라운드 함수는 고정 (라운드) 키에 대해 매 선택마다 바이젝티브(bijective)하다. 이것은 라운드 함수의 비균일성에 기초한 실행들을 회피한다.

도 4는 S-박스들을 포함하는 더 상세한 바람직한 배치를 제공한다. 이 예시적인 시스템에서, 라운드 함수(f)는 Z₂ ⁴⁰xZ₂ ³²로부터 Z₂ ³²까지의 매핑이다. 제 1 입력 인자는 라운드 키 K_i∈Z₂ ⁴⁰이고, 제 2 입력 인자는 중간 결과 X_i-1의 오른쪽 절반이다. 출력은 f(K_i,X_i-1 ^(R))∈Z₂ ³²로 표시된다. 이 도면에서, K_i ⁽¹⁾∈Z₂ ³²및 K_i ⁽²⁾∈Z₂ ⁸은 K_i=:(K_i ⁽¹⁾∥K_i ⁽²⁾)로 정의된다. 단계 310에서, 키 가산이 발생되어, 키 종속 S-박스층에 의한 단계 320이 이어진다. 이 예에서, S-박스 층은 각각 데이터 블록의 1/8에서 동작하는 8개의 더 작은 S-박스들(S₀,S₁,S₂,...,S₇)로 이루어진다. S-박스 변환은 Z₂ ⁸x Z₂ ³²로부터 Z₂ ³²까지의 매핑이고, 라운드 i에서의 제 1 입력 인자는 라운드 키(K_i ⁽²⁾)이며, 제 2 입력 인자는 키 가산의 결과(즉, X_i-1 ^(R) K_i ⁽¹⁾)이다. S-박스 변환의 32비트 출력은 S(K_i ⁽²⁾, X_i-1 ^(R) K_i ⁽¹⁾)로 표시된다. 이 매핑의 설명은 이하 주어질 것이다. 마지막으로, 단계 330에서, Z₂ ³²로부터 Z₂ ³²까지의 선형 변환이 적용된다. 입력은 S(K_i ⁽²⁾, X_i-1 ^(R) K_i ⁽¹⁾)이고, 그 출력은 L(S(K_i ⁽²⁾, X_i-1 ^(R) K_i ⁽¹⁾))로 표시된다. 이 표기에 있어서, 함수(f)는, f(K_i, X_i-1 ^(R))=L(S(K_i ⁽²⁾, X_i-1 ^(R) K_i ⁽¹⁾))로 주어진다.

S-박스

대체로 임의의 적절한 S-박스 층이 블록 암호에 사용될 수도 있다. 본 명세서에 설명된 바람직한 실시예에서, 각 S-박스는 4-비트 서브-블록에서 동작한다. 또한, 다른 크기들의 서브-블록들이 사용될 수 있다는 것이 인식될 것이다. 바람직하게, 각 S-박스에 대해서, 적어도 2개의 미리 결정된 순열들의 세트가 사용되며, 여기서, 이 순열들 중 S-박스 하나를 사용하기 전의 각 시간은 (의사-)랜덤 방식으로 선택된다. 바람직하게, 라운드 키가 이 선택에 사용된다. 바람직한 실시예에서, 각 S-박스는 2개의 순열들과 연관되며, 여기서, 라운드 키의 하나의 미리 결정된 비트가 2개의 순열들 중 어떤 것이 사용되는지를 선택하기 위해 사용된다. 4-비트 서브-블록들에서 동작하는 것과 같은 비교적 작은 S-박스들을 사용하는 것은 일반적으로 병렬 S-박스들의 로우를 필요로 할 것이며, 병렬 S-박스 각각은 적어도 2개의 비선형 순열들의 각 세트와 관련된다.

도 4는 32-비트 블록들에서 동작하고 4-비트 S-박스들을 사용하는 블록 암호의 바람직한 실시예를 도시하는 도면으로서, 병렬로 사용된 8개의 S-박스들을 발생시키며, S-박스들 각각은 2개의 순열들로 구성된다. 이 실시예에서는 다음 표기법이 사용된다. S-박스 변환의 제 1 입력 인자(K_i ⁽²⁾)에서의 비트들은 k_j ⁽ⁱ⁾(j=0,1,...,7)(즉, K_i ⁽²⁾=:(k₀ ⁽ⁱ⁾,K₁ ⁽ⁱ⁾,...,k₇ ⁽ⁱ⁾))로 표시되는 것으로 한다. 벡터들 N_j ⁽ⁱ⁾∈Z₂ ⁴(j=0,1,...,7)은 X_i-1 ^(R) K_i ⁽¹⁾=:(N₀ ⁽ⁱ⁾∥N₁ ⁽ⁱ⁾∥...∥N₇ ⁽ⁱ⁾)로서 정의된다. S-박스 매핑은 8개의 매핑들 S_j: Z₂x Z₂ ⁴→ Z₂ ⁴(j=0,1,...,7)의 연결로 이루어진다. 제 1 입력 인자는 키 비트(k_j ⁽ⁱ⁾)이며, S_j에 대한 2개의 순열들 중 어떤 것이 사용될 지를 선택한다. 제 2 입력 인자는 N_j ⁽ⁱ⁾이며, 이는 S_j에 대한 선택된 4-비트 순열에 대한 입력이다. 이 순열의 대응하는 4-비트 출력은 또한 S-박스의 출력이며, S_j(k_j ⁽ⁱ⁾, N_j ⁽ⁱ⁾)로 나타낸다. 이 표기에 있어서, 함수 S는 다음과 같이 주어진다.

S(K_i ⁽²⁾, X_i-1 ^(R) K_i ⁽¹⁾)=(S₀(k₀ ⁽ⁱ⁾, N₀ ⁽ⁱ⁾)∥S₁(k₁ ⁽ⁱ⁾, N₁ ⁽ⁱ⁾)∥...∥S₇(k₇ ⁽ⁱ⁾, N₇ ⁽ⁱ⁾))

임의의 적절한 S-박스 층이 사용될 수도 있다. 바람직하게, 계류중인 특허 출원 PHNL000365(EP....)에 따른 S-박스들이 사용된다.

선형 변환 매트릭스

S-박스 치환 함수 후에, 선형 변환(L)이 수행된다. 32-비트 서브-블록들에 대한 바람직한 실시에에서는, L: Z₂ ³²→Z₂ ³²이다. 설명된 바람직한 S-박스 구성을 사용하면, 이 선형 변환에 대한 입력은 벡터 S(K_i ⁽²⁾, X_i-1 ^(R) K_i ⁽¹⁾)이다. 이 벡터의 좌표는 y_j ⁽ⁱ⁾(j=0,1,...,31), 즉, S(K_` ⁽²⁾, X_i-1 ^(R) K_i ⁽¹⁾)=:(y₀ ⁽ⁱ⁾, y₁ ⁽ⁱ⁾,...,y₃₁ ⁽ⁱ⁾)로 표시된다. 매핑(L)은 이하 벡터-매트릭스 곱으로서 설명될 수 있으며, 매트릭스는 A∈Z₂ ^32×32이며,

L(S(K_i ⁽²⁾, X_i-1 ^(R) K_i ⁽¹⁾))=L((y₀ ⁽ⁱ⁾, y₁ ⁽ⁱ⁾, ..., y₃₁ ⁽ⁱ⁾))=(y₀ ⁽ⁱ⁾,y₁ ⁽ⁱ⁾, ..., y₃₁ ⁽ⁱ⁾)A이다.

선형 변환 매트릭스 구성

L(x)=xA로 정의된 선형 변환(L)은 다음 설계 기준을 충족시키도록 구성된다.

1. Z₂상의 선형성

2. 반전성(invertibility), 즉, 매트릭스(A)는 Z₂상에서 정칙 행렬이다.

3. 고 확산 속성들.

함수(L)의 구성은 이진 선형 에러-정정 코드들에 기초한다. 매핑(L)은 이진 에러-정정 코드에 대해 생성기 매트릭스 G=(I_k∥A)∈Z₂ ^k×2k에 의해 식별된다. x∈Z₂ ^k에 대해 모든 코드워드들 (x∥xA)∈Z₂ ^2k에 대해서, 왼쪽 절반(x)은 L에 대한 입력에 대응하지만, 오른쪽 절반(xA)은 출력에 대응한다는 것을 유념해야 한다. 설계 기준 (ⅰ)는 모든 이진 에러-정정 코드들에 만족되지만, (ⅱ)는 A가 Z₂상에서 정칙 행렬일 경우 및 정칙 행렬일 경우에만 만족된다는 것을 유념해야 한다. 또한, 기준 (ⅲ)는 코드워드들의 최소 해밍 가중치, 더 높은 최소 거리, 더 양호한 확산 속성들의 항으로 표현될 수 있다.

A의 구성은 32비트 블록들(즉, k=32, A∈Z₂ ^32×32)에 대해 도시될 것이며, 12와 같은 최소 해밍 거리를 갖는 [64,32] 코드의 구성에 대한 시작점으로서 이진 확장된 보스-카우드후리-호켄겜(XBCH, extended Bose-Chaudhuri-Hocquenghem)를 사용한다. 이와 같은 코드는 최적인 것으로서 공지되어 있다. 즉, 임의의 이진 [64,32] 코드는 더 적은 최소 거리를 갖거나 또는 12와 같다. 이것은 코드가 선형이기 때문에 임의의 0이 아닌 코드워드의 최소 해밍 가중치가 적어도 12라는 것을 의미한다. 이것은 매핑(L)의 확산 속성들이 비트-레벨에서 최적이라는 것을 의미하며, 그 점에서 t 비트(t>0)의 입력에서의 (작은) 변경들은 출력에서 적어도 max{0, 12-t}의 변경을 수반한다.

매트릭스(A)를 포함하는 이진 [64,32,12] 코드에 대한 생성기 매트릭스는 도 5에 도시된 바와 같이 다음과 같이 구성된다.

(i) 단계 510에서, 표준형의 생성기 매트릭스(G")(즉, B∈Z₂ ^32×28에 대해 G"=(I₃₂∥B))가 이진 선형 에러-정정 코드에 대응하도록 취해진다. 이와 같은 생성기 매트릭스(G")는 BCH(Bose-Chaudhuri-Hocquenghem) 코드로부터 시작하여 다음과 같은 방식으로 구성되는 것이 바람직하다.

(a) 단계 512에서, 생성기 매트릭스 G∈Z₂ ^36×63은 생성기 다항식 g(x):=x²⁷+x²²+x²¹+x¹⁹+x¹⁸+x¹⁷+x¹⁵+x⁸+x⁴+x+1에 대해 이진 [63,36,11] BCH 코드에 대해 구성되며, 여기서, G의 로우 j(j=0,1,...,35)는 다항식 x^jg(x)에 대응한다. 더 정확하게는, g_i∈Z₂에 대해 g(x)=:∑_i=0,1,...,27g_ixⁱ이면, 매트릭스의 제 1 로우는 (g₀,g₁,g₂,...,g₂₇,0,0,...,0)∈Z₂ ⁶³으로 주어진다. 생성기 매트릭스의 로우 j(j=1,2,...,35)는 j 위치상에서 상기 제 1 열의 오른쪽으로의 순환 시프트에 의해주어진다.

(b) 단계 514에서, 이 코드는 G의 마지막 4개의 로우들과 컬럼들을 삭제함으로써 [59,32,11] 코드로 단축된다.

(c) 단계 518에서, 이 단축된 코드는 패리티 체크 기호를 각 코드워드에 가산함으로써 [60,32,12]로 확장된다. 패리티 체크를 가산함으로써, 한 컬럼의 가산은 최소 거리가 증가되도록 한다. 이 [60,32,12] 코드에 대한 32×60 생성기 매트릭스는 G'로 표시된다.

(d) 단계 520에서, 표준형의 생성기 매트릭스 G"(즉, B∈Z₂ ^32×28에 대해 G"=(I₃₂∥B))를 얻기 위해서 G' 상에서 가우스 소거가 수행된다. 이것은 단축된 [60,32,12] XBCH 코드에 대한 생성기 매트릭스라는 것을 유념해야 한다.

(ⅱ) 결과 매트릭스 C∈Z₂ ^32×32는 Z₂상에서 정칙 행렬이 되도록 4개의 컬럼들로 B를 확장한다. 바람직하게, 4개의 컬럼들은 (의사-)랜덤하게 선택된다.

(a) 각각 32개의 (의사-)랜덤하게 선택된 이진 성분들을 갖는 4개의 컬럼들을 생성한다.

(b) 4개의 새로운 컬럼들로 B를 확장함으로써 검사 매트릭스를 생성한다(본래, 새로 가산된 컬럼들의 컬럼 위치는 중요하지 않다).

(c) 검사 매트릭스가 반전될 수 있는지를 검사한다. 이 검사에 대해서, 임의의 적절한 방법이 사용될 수도 있다(예를 들어, 가우스 소거에 기초한 방법).

(d) 만약 그렇다면 처리를 중단하고(매트릭스가 발견됨), 그렇지 않으면 적어도 하나의 새로운 컬럼을 생성함으로써 처리를 재시작한다.

랜덤 생성 처리를 사용하는 대신에, 4개의 컬럼들의 성분들은 임의의 다른 적절한 방법으로 생성될 수도 있다는 것이 인식될 것이다.

멀티-비트 S-박스들을 갖는 라운드 함수의 구성으로 인해, 이 멀티-비트 레벨 상의 양호한 확산 속성들 또한 바람직하다. 4-비트 S-박스들에 있어서, 이것은 다음과 같이 표현될 수 있다(다른 수의 비트들에 대한 변동들은 이 기술분야에 숙련된 사람들의 기술들 내에 있다). 코드워드 c∈Z₂ ³²의 4-비트 벡터들 n_i(i=0, 1, ..., 7)가 c=:(n₀∥n₁∥...∥n₇)로서 정의되면, c의 니블(nibble) 가중치는 NW(c):=#{i∥n_i≠(0, 0, 0, 0), i=0, 1, ..., 7)}로서 정의된다. 니블-레벨 상의 확상 속성들은 모든 0이 아닌 코드워드들에 대한 최소 니블 가중치, 더 높은 이 최소 가중치, 니블-레벨 상의 더 양호한 확산 속성들의 항으로서 표현될 수 있다. 멀티-비트 레벨(이 예에서는 니블 레벨)에서 고 확산을 얻기 위해서, 단계 530에서, 생성기 매트릭스(I∥P₁C P₂)에 대해 [64,32,12] 코드에서의 모든 코드워드들이 높은 니블 가중치를 갖도록 2개의 순열 매트릭스들 P₁,P₂∈Z₂ ^32×32가 선택된다. 마지막으로 발견된 매트릭스 A:=P₁C P₂는 선형 변환에 사용된다. 바람직한 실시예에서, 순열 매트릭스들 P₁및 P₂는 (의사-)랜덤하게 생성된다. (I∥A)에 의해 생성된코드의 최소 니블 가중치가 7과 같다는 것이 확인될 수 있다.

이러한 방법으로 생성된 선형 변환 매트릭스(A)의 로우들이 다음 표에서 주어진다(a₀은 제 1 로우이고, a₁은 제 2 로우이며, ..., a₃₁은 마지막이다). 벡터 매트릭스 적은 y_k ⁽ⁱ⁾=1(k=0,1,...,31)에 대한 로우들(a_k)의 XOR에 해당한다.

MDS 코드와의 비교

대칭-키 암호들에서의 MDS 코드에 기초한 선형 변환들의 사용은, 에스. 바우데네이의 "멀티-순열들에 대한 필요성에 대하여: MD4 및 SAFER의 암호 해독", 신속한 소프트웨어 암호화(2^nd), LNCS 1008, 스프링거, 1995, pp.286-297로부터 알 수 있다. 다음 표는 본 발명에 따른 XBCH 기판 매트릭스에 사용된 구성의 니블 가중치 분포와 MDS 코드의 (니블) 가중치 분포가 비교된다. 엔트리들은 소정의 니블가중치를 갖는 0이 아닌 코드워드들의 수를 나타낸다.

이 표로부터 알 수 있는 바와 같이, 2개의 구성들의 니블 가중치 분포들은 매우 유사하다. XBCH 구성의 최소 니블 가중치는 MDS 구성의 최소 가중치보다 단지 2개가 적으며, 이는 이 기준에 대해 최적으로 보여질 수 있다. 그러나, MDS 구성은, 연관된 선형 변환의 F₁₆(의 서브-필드들) 상의 선형성과 같은, 블록 암호의 암호 해독에 부당하게 이용될 수 있는 부가적인 수학적 구조를 포함한다는 단점을 갖는다. 예를 들어, 한가지는 F₁₆→F₁₆의 매핑들에 의해 S-박스들(및 그에 따른 완전한 블록 암호)을 설명할 수 있다. 또한, 본 명세서에 설명된 구성은 비트-레벨 상의 최적의 확산을 보장한다.

Claims (8)

1. 대칭-키 암호(symmetric-key cipher)에 사용하기 위한 선형 변환 매트릭스(A)를 생성하는 방법에 있어서:

   - G=(I_k∥B)(B∈Z₂ ^k×(n-k))의 표준형으로 생성기 매트릭스 G∈Z₂ ^k×n에 의해 표시되는 이진 [n,k,d] 에러-정정 코드를 생성하는 단계로서, 여기서, k<n<2k이고, d는 상기 이진 에러 정정 코드의 최소 거리인, 상기 이진 에러-정정 코드 생성 단계;

   - 결과 매트릭스(C)가 정칙 행렬(non-singular)이 되도록 2k-n 컬럼들로 매트릭스(B)를 확장하는 단계; 및

   - 매트릭스(C)로부터 매트릭스(A)를 유도하는 단계를 포함하는, 선형 변환 매트릭스(A) 생성 방법.
2. 제 1 항에 있어서,

   2k-n 컬럼들로 매트릭스(B)를 확장하는 상기 단계는:

   - 각각 k개의 이진 성분들을 갖는 2k-n 컬럼들을 (의사-)랜덤하게((pseudo-)randomly) 생성하는 단계;

   - B의 n-k 컬럼들과 상기 생성된 2k-n 컬럼들로 이루어지는 검사 매트릭스를 형성하는 단계; 및

   - 정칙 행렬인 검사 매트릭스가 발견될 때까지 상기 검사 매트릭스가 정칙 행렬인지의 여부를 검사하는 단계를 반복적으로 수행하고,

   상기 발견된 검사 매트릭스를 매트릭스(C)로서 사용하는 단계를 포함하는, 선형 변환 매트릭스(A) 생성 방법.
3. 제 1 항에 있어서,

   매트릭스(C)로부터 매트릭스(A)를 유도하는 상기 단계는,

   - 상기 생성기 매트릭스(I∥P₁C P₂)에 의해 표시되는 [2k,k,d] 에러 정정 코드의 모든 코드워드들이 미리 결정된 멀티-비트 가중치를 갖도록 2개의 순열 매트릭스들(P1,P2 ∈ Z₂ ^k×k)을 결정하는 단계, 및

   - 매트릭스(A)로서 P₁C P₂를 사용하는 단계를 포함하는, 선형 변환 매트릭스(A) 생성 방법.
4. 제 3 항에 있어서,

   상기 암호는 m-비트 서브-블록들에서 동작하는 S-박스들을 갖는 S-박스 층에 대한 라운드 함수를 포함하고, 모든 0이 아닌 코드워드들에 대한 상기 최소의 미리 결정된 멀티-비트 가중치는 미리 결정된 m-비트 가중치와 같은, 선형 변환 매트릭스(A) 생성 방법.
5. 제 3 항에 있어서,

   상기 2개의 순열 매트릭스들(P₁, P₂)을 결정하는 상기 단계는 (의사-)랜덤 방식으로 상기 매트릭스들을 반복적으로 생성하는 단계를 포함하는, 선형 변환 매트릭스(A) 생성 방법.
6. 제 1 항에 있어서,

   상기 암호는 32-비트 블록들에서 동작하는 라운드 함수를 포함하고, [n,k,d] 에러-정정 코드를 생성하는 상기 단계는:

   이진 확장된 보스-카우드후리-호켄겜(XBCH, extended Bose-Chaudhuri-Hocquenghem)[64,36,12] 코드를 생성하는 단계; 및

   4개의 로우들을 삭제함으로써 상기 코드를 [60,32,12] 단축 XBCH 코드로 단축하는 단계를 포함하는, 선형 변환 매트릭스(A) 생성 방법.
7. 컴퓨터 프로그램 제품으로서,

   처리기가 청구항 1항의 방법을 수행하도록 동작하는, 컴퓨터 프로그램 제품.
8. 입력 데이터 블록을 출력 데이터 블록으로 암호화 변환하는 시스템으로서, 상기 데이터 블록들은 n개의 데이터 비트들을 포함하는, 상기 변환 시스템에 있어서:

   - 상기 입력 데이터 블록을 수신하는 입력;

   - 청구항 1항의 방법에 따라 생성된 선형 변환 매트릭스(A)를 저장하는 저장장치;

   - 상기 선형 변환 매트릭스(A)를 사용하여 상기 입력 데이터 블록 또는 상기 입력 데이터 블록의 유도물(derivative)에서 선형 변환을 수행하는 암호화 처리기; 및

   - 상기 처리된 입력 데이터 블록을 출력하는 출력을 포함하는, 변환 시스템.