[암호학] 확장된 유클리드 호제법을 이용한 S-Box만들기

2010.04.25 21:26

 

 

<목표> [암호학] 확장된 유클리드 호제법을 이용한 S-Box만들기

   

 

  오늘은 Extended Euclid(유클리드 호제법)을 이용하여 GF(28)에서 곱셈에 대한 역원을 구하는 것에 대해 알아보겠습니다. GF(28)에서의 역원을 구하는 방식은 사실 일반적인 유클리드 호제법과 같은 방식입니다. 다만 GF(28)로, 필드의 특성상 일반적인 최대공약수를 구하는 것과는 조금은 다른 방식으로 구한다는 것이 차이라면 차이겠습니다. 이러한 확장된 유클리드 호제법을 배우게 된 계기는 AES(Advanced Encryption Standard) 때문입니다. 과거 DES 방식이 암호화, 복호화 방식으로 쓰이던 시절에서, 컴퓨터의 하드웨어적인 발전으로 키값을 전수조사할 수 있게 되면서 조금 더 안전하고, 효과적인 암호화 방식이 필요하게 되었고, AES가 필요하게 되었습니다. 공모를 통해 AES 알고리즘 후보 중 Rijndael이 채택이 되었고, AES로서 지정되어 있습니다. 오늘은 AES의 전체적인 구조에 대해서 간략히 알아보고, 변환 연산을 할 때 필요한 S-Box를 생성하는 방법에 대해서 알아보면서 확장된 유클리드 호제법 사용방법을 익혀보겠습니다.

  기존의 암호화 방식인 DES 방식에서도 역시 S-Box가 사용되었습니다만, 그것이 만들어진 방식이 공개되지 않아 주어진 S-Box에 대해 신뢰를 가지기가 어려웠습니다. 하지만 AES에서의 S-Box는 그 생성 방법이 공개되어 있기 때문에 암호화 방법에 조금 더 투명성이 가미되었습니다.

  간략히 AES의 구조에 대해서 알아보고, 확장된 유클리드 호제법에 대해서 알아보겠습니다.

 

 

[기본 구조]   AES(Advanced Encryption Standard)의 기본 구조

 

 

  기본적인 구조의 위의 그림과 같습니다. 암호학에 대해서 조금이라도 접해보신 분은 크게 어렵지 않으시겠지만, 처음 접해본 분은 많은 사각형들의 구조에 답답해하지 않을까 싶습니다. 의외로 구조는 간단합니다. 왼쪽에 평문(Plaintext)를 확장한 키를 이용하여 10개의 라운드를 통과하면 암호문(Ciphertext)가 나오는 구조입니다. 여기서 라운드는 마지막 라운드만 제외하면 같은 구조로 되어있습니다. 그리고 이 암호문을 다시 복호화 하는 방법은 오른쪽에 도식화 되어있는 것처럼 암호화 방식의 역방향으로 진행시키면 됩니다. 여기서 각 연산들이 조금씩 바뀌는 것에 주의해야합니다. 아래는 이 그림에 대한 간단한 수도 코드(Pseudo code)입니다.

 

 

AES의 Pseudo Code

AES(in,out,key)

{

    KeyExpansion(Key,RoundKey)

    state = in

    AddRoundKey (state,RoundKey[0])

    for round=1 step 1 to Nr-1

          SubBytes(stats)

          ShiftRows(stats)

          MixColumns(stats)

          AddRoundKey(stats,RoundKey[i]

    end for

 

    SubBytes(stats)

    ShiftRows(stats)

    AddRoundKey(stats,RoundKeyp[Nr])

    out = stats

}

 

 

  오늘 알아볼 것은 Substitute Bytes 부분입니다. S-Box를 이용하여 들어온 문자를 다른 문자로 변환하는 기능을 담당합니다. 아래의 그림은 S-Box의 모습입니다. 간단한 예로 들자면, xy의 조합에 의해서 다른 문자로 변환이 가능합니다. 예를 들어 '4E'라는 문자를 변환시킨다고 하면, 행 부분의 4와 열 부분의 E부분의 행렬값으로 치환합니다. 즉 '2F' 로 변환합니다.

 

 

  이렇게 변환한 값들은 비선형적인 값들을 나타냅니다. 즉, 암호를 풀기 어렵도록 선형성을 제거하는 것이죠. 이러한 것이 가능하게 하는 것은 GF(28) 필드에서의 곱셈에 대한 역원을 이용하기 때문입니다.

 

 

 

[핵심코드]  Extended Euclid를 이용하여 곱셈에 대한 역원 찾기

   

곱셈에 대한 역원 찾기 - Extended Euclid(d, f)

만약 GCD(d, f)=1이라면 그때 d는 modulo f 상에서 곱셈에 대한 역원을 갖습니다.

양의 정수 d < f에 대해, d-1 = 1 mod f인 d-1 < f가 존재합니다.

 

1. (X1, X2, X3) (1, 0, f); (Y1, Y2, Y3) (0, 1, d)

2. If X3= 0 return X3 = GCD(d, f); no inverse

3. If X3 = 1 return Y3 = GCD(d, f); Y2=d-1 mod f

4. Q = X3 / Y3

5. (T1, T2, T3) (X1-QY1, X2-QY2, X3-QY3)

6. (X1, X2, X3) (Y1, Y2, Y3)

7. (Y1, Y2, Y3) (T1, T2, T3)

8. Goto 2

 

    자, 이제 확장된 유클리드 호제법에 대해서 알아봅시다. 유클리드 호제법을 보신 분들이라면 기본 구조는 비슷하다고 생각하실 겁니다. 유클리드 호제법을 이용해서 최대 공약수 구하는 방식과 같습니다. 위의 코드 보시면 그렇게 어렵지 않다는 것을 확인하실 수 있습니다.

 

 

[예제]  Extended Euclid를 이용하여 GF(28)의 95곱셈에 대한 역원 찾기

 

  이제 이것을 이용하여 GF(28)의 95의 곱셈에 대한 역을 구해봅시다.

 

GF(28) 에서 95의 곱셈에 대한 역구하기


GCD(95,m(x)) = 1

m(x) = x8 +x4 +x3+x+1

b(x) = x7 +x4 +x2+1

A1(x) = 1

A2(x) = 0

A3(x) = x8 +x4 +x3+x+1

(x) = 0

B2(x) = 1

B3(x) = x7 +x4 +x2+1

  1. Q(x) = (x8 +x4 +x3+x+1) / (x7 +x4 +x2+1) = x

[T1,T2,T3] [1-x·0 ,0-x·1 , (x8 +x4 +x3+x+1) – x·(x7 +x4 +x2+1)]

A1(x)=0

A2(x)=1

A3(x)=x7 +x4 +x2+1

B1(x)=1

B2(x)=x

B3(x)=x5 +x4+1

  1. Q(x) = (x7 +x4 +x2+1) / (x5 +x4+1) = x2 +x+1

[T1,T2,T3] [0-(x2 +x+1)·1, 1-(x2 +x+1)·x , (x7 +x4 +x2+1) – (x2 +x+1)·(x5 +x4 +1)]

A1(x) = 1

A2(x) = x

A3(x) = x5 +x4 +1

B1(x) = x2 +x+1

B2(x) = x3+x2 +x+1

B3(x) = x

  1. Q(x) = (x5+x4 +1) / x = x4 +x3

[T1,T2,T3][1-(x4+x3)·(x2+x+1),x-(x4+x3)·(x3+x2+x+1), (x5+x4+1) –(x4+x3)·x][x6 +x3 , x7+x3 +x ,1]

A1(x) = x2 +x+1

A2(x) = x3+x2 +x+1

A3(x) = x

B1(x) = x6 +x3

B2(x) = x7+x3 +x

B3(x) = 1

B3(x)=1 이므로 B2(x) = B(x)-1 mod m(x)

B2(x)=x7+x3 +x = 8A

∴ 95-1 = 8A

 

  위와 같은 식을 이용해서 간략하게 도식화 해보면 아래의 표와 같습니다.

 

Q

A1

A2

A3

B1

B2

B3

-

1

0

x8 +x4+x3+x+1

0

1

x7 +x4 +x2+1

x

0

1

x7 +x4 +x2+1

1

x

x5 +x4+1

x2 +x+1

1

x

x5 +x4+1

x2 +x+1

x3+x2 +x+1

x

x4 +x3

x2 +x+1

x3+x2 +x+1

x

x6 +x3

x7+x3 +x

1

 

  이를 조작하기 위해서 비트로 표현합니다.

   

Q

A1

A2

A3

B1

B2

B3

-

000000001

000000000

100011011

000000000

000000001

010010101

000000010

000000000

000000001

010010101

000000001

000000010

000110001

000000111

000000001

000000010

000110001

000000111

000001111

000000010

000011000

000000111

000001111

000000010

001001000

010001010

000000001

 

 GF(28)의 특성상 나누는 것은 쉬프트 연산으로 처리가 가능합니다. 그리고 빼기 연산은 XOR연산으로 가능합니다. 즉 몫을 구할 때, 나누어 지는 수와 나누는 수의 최초 비트의 거리차만큼 쉬프트를 하게 되면 가장 큰 수와 맞출 수 있어서 빼기가 가능합니다. 그리고 빼기 연산은 0아니면 1로 결과가 나누어지기 때문에 XOR연산으로도 구할 수 있습니다.

 

 

  이제 역원을 구했으니, 마지막으로 S-Box를 만들어봅시다. 위의 그림처럼 행렬곱을 이용하여 S-Box를 만들어 냅니다. x8 +x4 +x3+x+1 필드에서의 S-Box를 구하기 위해서 정해진 행렬로 곱해야 합니다. 그리고 마지막에 특정한 값과 XOR을 시켜줘야 합니다. 이것 역시 정해진 값입니다. 위의 그림처럼 정해진 행렬과 변환하고 싶은 값을 비트 순서대로 [b7, b6, b5, b4, b3, b2, b1, b0] 에 넣고, 행렬곱을 한다음에 XOR시켜 줍니다. 그러면 우리가 원하던 S-Box를 구할 수 있습니다. 이러한 방식으로 00 ~ FF 까지 모두 구해서 행렬로 만들어 내면 위에서 살펴본 S-Box가 됩니다.

   

 

 < 마무리 > 확장된 유클리드 호제법을 이용하여 S-Box구하기

   

  이번 포스팅에서는 AES 인 Rijndael 알고리즘을 이용하여 간단히 암호화 하는 방식의 개요에 대해 알아보고, 그 중 S-Box를 만들기 위해서 확장된 유클리드 호제법을 이용하는 방법에 대해서 알아보았습니다. AES는 공개된 암호화 방식으로 키 값의 크기가 크기 상당하기 때문에 전수 조사를 통한 암호해독은 시간제약상 불가능에 가깝습니다. 이러한 방법이 어려운 이유는 비선형성에 기초한 변환 기술 때문입니다. 이것이 S-Box가 필요한 이유이며, S-Box를 만드는 방법은 공개가 되어 있기 때문에 x8 +x4+x3+x+1의 GF(28)에서의 서로소를 이용하여 곱셈에 대한 역원을 이용하여 만들어 냅니다. 이 때 필요한 방법이 확장된 유클리드 호제법이며, 이것에 한 예를 오늘 다루어 봄으로써 어떻게 구현해야할지에 대해 알아보았습니다.

     

 

 

[참고자료]  

   

   

Created by 맥박

     

     


맥박 IT 기타/보안 , , , , , ,

  1. Blog Icon

    비밀댓글입니다

  2. Blog Icon

    비밀댓글입니다