중국인의 나머지 정리

중국의 5세기 문헌인 손자산경(孫子算經)에 나오는 문제로, 내용은 다음과 같다.

3으로 나누었을 때 2가 남고, 5로 나누었을 때 3이 남고, 7로 나누었을 때 2가 남는 수는 무엇인가?

이를 기리기 위해 이런 종류의 문제의 일반적인 해법은 중국인의 나머지 정리가 되었다고 한다.

$m_1,m_2,\cdots ,m_n$이 쌍마다 서로소 즉, $gcd(m_i,m_j)=1,i\ne j$이면, 다음 연립 합동식

$$x\equiv a_i(mod{m}_i)i=1,2,3,4\cdots n$$

를 만족하는 $x$는 $mod(n_1{n}_2\cdots n_k)$에서 유일하게 존재한다는 정리이다.

위의 경우를 만족하는 유일한 해 $x$는
$x\equiv a_1{M}_1{N}_1+a_2{M}_2{N}_2+\cdots +a_k{M}_k{N}_k(modM)$

이렇게 구할수 있는데 여기서

$M=n_1{n}_2\cdots n_k$

$M_i=M/n_i$

$N_i\equiv M_i^{-1}(mod{n}_i)$이다.

예제로 $x\equiv 2(mod3),x\equiv 3(mod5),x\equiv 2(mod7)$를 만족하는 $x$를 구해보자.
위의 공식에서 사용되는 변수 $M,M_i,N_i$를 먼저 구해보면
$M=3\times 5\times 7=105$
$M_1=M/3=35,M_2=M/5=21,M_3=M/7=15$
$N_1\equiv M_1^{-1}\equiv 2(mod3)$
$N_2\equiv M_2^{-1}\equiv 1(mod5)$
$N_3\equiv M_3^{-1}\equiv 1(mod7)$이다.
사용된 변수를 모두 계산했으니 위 공식대로 대입해보면
$x\equiv 2M_1{N}_1+3M_2{N}_2+2M_3{N}_3(modM)$

$\equiv 2\cdot 35\cdot 2+3\cdot 21\cdot 1+2\cdot 15\cdot 1(mod105)$

$\equiv 23(mod105)$

라는 해를 구할 수 있다.

증명

증명은 존재성과 유일성 두 가지로 나뉘는데 증명하기 앞서 알아두어야 할 정리부터 증명하고 시작하겠음

양의 정수 $m$과 $a_1,a_2,\cdots ,a_n$에 대하여 $m$이 $a1,a2,\cdots ,a_n$와 각각 서로소이면,
$m$과 $a_1{a}_2\cdots a_n$은 서로소이다.

$m$과 $a1,a2,\cdots ,a_n$이 서로소가 아니라고 가정하면 $m$과 $a_1{a}_2\cdots a_n$의 공약수인 소수 $p$가 존재한다. $p\mid a_1{a}_2\cdots a_n$이므로 $p\mid a_i$가 존재한다.

그러면 $p$는 $a_i$와 $m$를 모두 나누므로 가정에 모순된다.

양의 정수 $m$과 $a_1,a_2,\cdots ,a_n$에 대하여 $m$이 $a_1,a_2,\cdots ,a_n$ 의 각각의 배수이면 $m$은 $\text{lcm}(a_1,a_2,\cdots ,a_n)$의 배수이다.

나눗셈 정리에 의하여 $m=q\cdot \text{lcm}(a_1,a_2,\cdots ,a_n)+r$을 만족하는 정수 $q,r$이 유일하게 존재한다$(0\le r<\text{lcm}(a_1,a_2,\cdots ,a_n))$.

그런데 $a_i$가 $m$과 $\text{lcm}(a_1,a_2,\cdots ,a_n)$을 모두 나누므로 $a_i$는 $r$도 나눠야 한다.

이것은 모든 $i$에 대해 참이므로 $r$은 $\text{lcm}(a_1,a_2,\cdots ,a_n)$보다 작은 $a_i$​들의 공배수이다.

이걸 만족하는 값은 $r=0$밖에 없으며, 이는 곧 $m$이 $\text{lcm}(a_1,a_2,\cdots ,a_n)$의 배수이다.

​존재성

$m=m_1{m}_2\cdots m_n$라고 하자. 또, $n_k=\frac{m}{m_k}$라고 놓자. 즉, $n_k$는 $m_k$를 제외한 나머지 $m_i$들의 곱을 의미한다.
도움정리 1로부터 $gcd(n_k,m_k)=1$이다. 그럼 베주 항등식에 의해,
$s_k{n}_k+t_k{m}_k=1$을 만족하는 정수 $s_k,t_k$가 존재한다. 이를 합동식 형태로 고치면,
$s_k{n}_k\equiv 1(mod{m}_k)$이다.

이제 $x=a_1{n}_1{s}_1+a_2{n}_2{s}_2+\cdots +a_n{n}_n{s}_n$라고 놓자. $j\ne k$이면 $m_k\mid n_j$이고, 따라서
$x\equiv a_k{n}_k{s}_k\equiv a_k\cdot 1=a_k(mod{m}_k)$이다.($1<=k<=n$인 임의의 자연수)
즉, $x$는 주어진 연립 합동식의 한 해이다.

유일성

$x,y$가 주어진 연립 합동식의 해라고 하자. 그러면,
$x\equiv a_1\left(\text{mod}{m}_1\right),y\equiv a_1\left(\text{mod}{m}_1\right)$
$x\equiv a_2\left(\text{mod}{m}_2\right),y\equiv a_2\left(\text{mod}{m}_2\right)$
$x\equiv a_n\left(\text{mod}{m}_n\right),y\equiv a_n\left(\text{mod}{m}_n\right)$이다.

그러므로, 임의의 $k(1\le k\le n)$에 대하여, $x\equiv a_k\equiv y\left(\text{mod}{m}_k\right)$이고, 그래서 $x-y\equiv 0\left(\text{mod}{m}_k\right)$이다.

즉, $x-y$는 모든 $m_k$들의 배수이다. 따라서 도움정리 2에 의해, $\text{lcm}(m_1,m_2,\cdots ,m_n)\mid (x-y)$이다.

그런데 $m_1,m_2,\cdots ,m_n$들이 쌍마다 서로소이므로 $m_1{m}_2\cdots m_n\mid (x-y)$이다.

즉, $x\equiv y(\text{mod}{m}_1{m}_2\cdots m_n)$이고

이는 주어진 연립 합동식의 해가 유일함을 보인다.

RSA암호화 알고리즘에는 2개의 암호화 키가 사용됩니다. 하나는 모두에게 공개되는 공개키이고 하나는 공개하지 않는 개인만 알고 있는 개인키(비밀 키라고도 함)입니다. 공개키는 평문을 암호화할 때 사용되고 개인키는 암호문을 평문으로 복호화할 때 사용합니다.

RSA알고리즘의 안정성은 아주 큰 합성수는 인수분해하기 어렵다는 인수분해 문제의 어려움에 기반합니다.

오일러 정리

오일러 정리는 $n$과 서로소인 양의 정수 $m$이 다음 식을 만족한다는 정리입니다.

$m^{\phi \left(n\right)}\equiv 1\left(\text{mod}n\right)$

여기서 $\phi \left(n\right)$는 오일러 파이 함수라고 불리며, $n$ 이하의 양의 정수 중에서 $n$과 서로소인 수의 개수를 의미합니다.

예를 들어 6 이하의 양의 정수 중 6과 서로소인 수는 1,5로 두 개이기 때문에 $\phi \left(6\right)=2$입니다.

공개키 생성

1. 두 소수를 찾는다. $p=53,q=59$

2. 두 소수를 곱한다. $n=p\ast q=53\ast 59=3127$    $n$이 첫 번째 공개키 재료

공개키 생성을 위한 재료($e$)가 하나 더 필요하고 $e$는 아래의 조건을 만족하는 숫자들 중 하나를 정하면 됩니다.

$\phi \left(n\right)$와 서로소 관계이어야 한다.        $\text{gcd}(e,\phi \left(n\right))=1$

즉, $e$값은 $\phi \left(n\right)=(p-1)(q-1)=3016$와 서로소 관계인 3,5,7,9 중 하나를 선택하면 됩니다.

$e=3$으로 정하겠습니다.

비밀키 생성

비밀키 생성에 필요한 $d$는 $d\equiv e^{-1}\left(\text{mod}\phi \left(n\right)\right)$을 만족하는 수들 중 하나입니다. $d=2011$로 정하겠습니다.

암호화

공개키 $(n,e)$로 $n$보다 작은 평문 $m$을 암호화할 때, 암호문 $c$는 다음 식으로 구해집니다.

$c\equiv m^e\left(\text{mod}n\right)$

"melon"을 숫자로 변환했을 때 2033으로 가정하고 "melon"을 암호화 하면

$c\equiv {2033}^3\left(\text{mod}3127\right)$

암호문은 1983이 됩니다.

복호화

암호문 $c$를 개인키 $d$로 복호화할 때, 평문 $m$은 다음과 같이 구해질 수 있습니다.

$m\equiv c^d\left(\text{mod}n\right)$

$c\equiv {1983}^{2011}\left(\text{mod}3127\right)$

당연히 계산 결과는 2033입니다.

참고문헌

geeks for geeks - RSA Algorithm in Cryptography

DES

DES는 미국의 국가 안보국 NSA에서 IBM의 루시퍼 알고리즘을 개량하여 만든 대칭키 암호입니다.

DES는 루시퍼에서 128비트 키를 사용했던 것과 달리 키 길이를 56비트로 줄였고, 내부에서 사용하는 알고리즘도 일부 변경하였습니다.

미국 국립표준기술연구소 NIST는 DES를 1976년부터 2002년까지 표준 블록 암호로 인정했습니다만 현대에는 DES에 대한 공격 기법이 많이 연구되어 DES를 더이상 블록 암호의 표준으로 사용하지 않습니다.

DES는 혼돈 성질을 만족하기 위해 치환을, 확산 성질을 만족하기 위해 순열을 사용합니다.

치환과 순열을 매우 단순한 연산이므로 평문에 이들을 한 번 적용한다고 해서 암호학적 효과를 기대할 수는 없습니다. 그러나 이들을 여러 번 교차해서 반복 적용하면 혼돈과 확산의 성질을 모두 만족하게 된다고 알려져 있습니다.

이런 특성을 이용하여 치환이나 순열 같은 단순한 연산들로 한 라운드로 구성하고, 각 라운드를 여러 번 반복하여 암호학적 안전성을 확보하는 암호를 곱 암호(Product Cipher)라고 합니다.

DES는 8바이트(64비트)를 한 블록으로 하는 블록 암호이며, 전체 구조는 초기 순열, 최종 순열, 페이스텔 구조의 16 라운드, 그리고 각 라운드에 사용되는 48비트의 키를 생성하는 키 생성 함수(Key Generation)로 구성되어 있습니다.

DES 구조

페이스텔 구조

DES에서 라운드 함수를 적용하는 전체 과정은 페이스텔 구조를 이루고 있습니다.

페이스텔 구조는 데이터를 두부분으로 나누어 좌, 우 두부분에 교대로 비선형 변환을 적용시키는 구조를 말하며 이를 3단계로 나누면

입력으로 들어온 블록을 동일한 길이의 왼쪽 블록과 오른쪽 블록으로 나눕니다.

각 라운드마다 오른쪽 블록은 다음 라운드의 왼쪽 블록으로 입력됩니다.

왼쪽 블록은 오른쪽 블록에 라운드 함수를 적용한 결과와 xor되어 다음 라운드의 오른쪽 블록으로 입력됩니다.

수식으로 표현하면

1. $L_0=P[:len(P)/2],R_0=P[len(P)/2:]$

2. $L_{n+1}=R_n$

3. $R_{n+1}=L_n⨁F(R_n,K_n)$

블록 암호는 평문을 복호화 할 수 있어야 하므로, 일반적으로 암호화를 구성하는 각 함수들에 역함수가 존재합니다.

그러나 페이스텔 구조를 사용하면 $⨁$의 특성상 역함수가 존재하지 않아도 됩니다.

또한 암호화와 복호화의 구조가 동일하므로, 암호화에 사용한 라운드 키를 역순으로 입력하면 복호화가 이뤄집니다.

한편, 오른쪽 블록은 다음 라운드의 왼쪽 블록으로 어떠한 처리도 없이 입력됩니다.

이런 특성으로 인해 페이스텔 암호는 비페이스텔 암호와 같은 안전성을 갖기 위해 두 배 정도 라운드를 사용해야한다는 단점이 있습니다.

Step1 초기 순열 & Step 3 최종 순열

DES는 시작할 때 초기 순열을, 마지막에는 최종 순열을 수행하며 초기 순열과 최종 순열은 서로 역관계에 있습니다.
임의의 64비트 데이터에 초기 순열을 적용하고, 최종 순열을 적용하면 입력 값이 그대로 출력됩니다.
초기 순열과 최종 순열은 정해진 테이블을 이용하여 64비트 입력을 비트 단위로 전치합니다.
테이블의 n번째 값이 m일 때, 출력의 n번째 비트는 입력의 m번째 비트가 됩니다.
초기 순열과 최종 순열은 각각 초기 순열 테이블과 최종 순열 테이블을 이용합니다.

IPT = [58, 50, 42, 34, 26, 18, 10, 2,
       60, 52, 44, 36, 28, 20, 12, 4,
       62, 54, 46, 38, 30, 22, 14, 6,
       64, 56, 48, 40, 32, 24, 16, 8,
       57, 49, 41, 33, 25, 17, 9, 1,
       59, 51, 43, 35, 27, 19, 11, 3,
       61, 53, 45, 37, 29, 21, 13, 5,
       63, 55, 47, 39, 31, 23, 15, 7]
FPT = [40, 8, 48, 16, 56, 24, 64, 32,
       39, 7, 47, 15, 55, 23, 63, 31,
       38, 6, 46, 14, 54, 22, 62, 30,
       37, 5, 45, 13, 53, 21, 61, 29,
       36, 4, 44, 12, 52, 20, 60, 28,
       35, 3, 43, 11, 51, 19, 59, 27,
       34, 2, 42, 10, 50, 18, 58, 26,
       33, 1, 41, 9, 49, 17, 57, 25]

Step2. 라운드 함수

라운드 함수에는 오른쪽 블록만 입력되므로, 입력의 길이는 32비트입니다. 라운드 함수는 확장 순열, 라운드 키 결합, 치환 테이블 그리고 고정 순열로 이루어져 있습니다.

Step 2.1. 확장 순열과 라운드 키 결합

확장 순열은 입력을 비트 단위로 전치하는 동시에, 전체 길이를 48비트로 확장합니다.

이 과정에서 32비트의 입력값을 4비트씩 8개의 부분으로 나누고, 테이블을 참조하여 각각을 6비트로 확장합니다.
이 과정은 테이블만 다를 뿐, 초기 순열, 최종 순열과 같은 방식으로 이뤄집니다.

라운드 키 결합은 확장 순열로 나온 출력을 라운드 키와 $⨁$ xor 하는 것입니다.

Step2.2. S-Box와 고정 순열

S-Box는 라운드 키 결합에서 출력된 48비트 결과 값을 32비트로 축소합니다.

S-Box는 4개의 행과 16개의 열로 이루어진 표를 사용하는데, 표의 각 값은 4비트로 표현되는 수입니다.

S-Box가 적용되는 과정은 다음과 같습니다.

먼저, 입력을 6비트씩 8개의 부분으로 나눕니다. 여섯 비트 중 첫 번째와 마지막 비트로 행을 결정하고, 나머지 네 개의 비트로 열을 결정합니다. 그 뒤, S-Box의 표에서 행과 열을 참조하여 값을 반환합니다. DES에서는 여섯 비트로 자른 부분마다 다른 S-Box를 사용합니다.

S-Box로 길이를 축소하고 나면, 고정 순열(Straight P-Box)로 다시 비트 단위 전치가 이뤄집니다.

키 생성 함수

키 생성 함수는 64비트의 입력을 받아 각 라운드에 필요한 48비트 라운드 키를 생성하는 함수입니다. 

이 함수는 패리티 비트 제거, 쉬프트, 압축 순열로 구성되어 있습니다.

패리티 비트 제거

패리티 비트 제거는 입력에서 패리티 비트를 제거하고, 남은 56비트에 순열을 적용하는 과정입니다.

DES의 비밀키에서 각 바이트의 가장 오른쪽 비트는 자신이 속한 바이트의 나머지 7비트에 대한 홀수 패리티 비트입니다. 홀수 패리티 비트란 한 바이트를 이진수로 표현했을 때, 1의 개수가 홀수가 되도록 덧붙인 비트를 말합니다. 예를 들어, 1010101에는 1이 4개 있습니다. 홀수 패리티 비트를 적용하면 끝에 비트 1을 덧붙여서, 10101011을 전송해야 합니다.

패리티 비트는 통신 중에 비트 반전이 일어나지 않았음을 보증하는 역할을 합니다. 홀수 패리티 비트를 사용하여 통신할 때, 수신한 바이트 중 1의 갯수가 짝수인 바이트가 있다면 그 바이트에서 임의의 비트에 반전이 일어났음을 수신자가 알 수 있습니다. 이를 확인한 수신자는 손상되지 않은 데이터를 얻기 위해 재전송을 요구할 수 있습니다.

쉬프트

쉬프트는 입력을 왼쪽 28비트와 오른쪽 28비트로 나누어 각각을 1비트나 2비트만큼 왼쪽으로 순환 쉬프트하는 과정입니다. 1, 2, 9, 16 라운드에서는 1비트, 나머지 라운드에서는 2비트만큼 쉬프트합니다.

10101111을 왼쪽으로 1비트 순환 쉬프트하면, 왼쪽 끝의 비트가 오른쪽 끝으로 이동하여 01011111이 됩니다. 마찬가지로 2비트를 왼쪽으로 순환 쉬프트하면 왼쪽 끝의 '10'이 오른쪽으로 이동하여 10111110이 됩니다.

압축 순열

압축 순열은 56비트의 입력을 48비트 길이로 압축하는 과정입니다. 수행 방법은 앞서 설명한 순열들과 같습니다.

AES

AES는 연산 능력의 향상으로 DES가 더 이상 안전하지 않게 되자, 새롭게 표준으로 선정된 블록 암호 알고리즘입니다.
내부적인 논의만으로 표준으로 선정된 DES와 달리, AES는 전세계에서 암호 알고리즘을 공모받고, 전문가들의 심사를 거쳐 그 중에서 가장 뛰어난 알고리즘이 선정되었습니다.

당시 공모에 제안된 21개의 암호 알고리즘들 중, 보안성, 효율성, 하드웨어 이식의 적합성, 유연성 등을 고려하여 심사한 결과, Vincent Rijmen, Joan Daemen이 제안한 Rijndael 구조가 채택되었습니다.

표준으로 선정된 이후부터 지금까지, AES에는 기밀성을 위협하는 치명적인 취약점이 발견되지 않았습니다. 또한 CPU 제조사들이 AES 연산을 위한 명령어를 따로 정의해 주어서 암호화, 복호화의 성능도 뛰어납니다. 이런 이유로 현대에는 대칭키 암호 알고리즘을 사용할 때, 일반적으로 AES가 사용됩니다.

AES는 SPN(Substitution Permutation Network)이라는 암호 구조를 사용합니다. SPN은 곱 암호의 일종으로,

S-Box를 사용하는 치환(Substitution)과 P-Box를 사용하는 순열(Permutation)을 여러 라운드에 걸쳐 반복합니다.

페이스텔 구조와 달리 라운드마다 입력 전체에 라운드 함수를 적용하므로,

같은 수의 라운드를 사용할 때 SPN이 페이스텔 구조에 비해 암호학적으로 두 배 더 안전합니다.

AES 구조

AES는 라운드마다 128비트 크기의 블록을 암호화하는 블록 암호입니다.

키의 길이는 128, 192, 256비트 중 하나를 선택할 수 있고, 라운드 수는 키의 길이에 따라 10, 12, 14로 결정됩니다.

키의 길이가 128비트이면 AES-128, 192비트이면 AES-192, 256비트이면 AES-256이라고 부릅니다.

AES는 암호화를 할 때, 가장 먼저 각 블록을 4행 4열의 상태 배열(State)로 재구성합니다.

State의 각 칸에는 8비트(1바이트)가 저장됩니다.

입력 1F3CF203B211C5AA6EB27A45E4D98130은 다음과 같은 state로 재구성됩니다.

$$\left[\begin{array}{cccc}1F& 3C& F2& 03\\ B2& 11& C5& AA\\ 6E& B2& 7A& 45\\ E4& D9& 81& 30\end{array}\right]$$

이후에는 재구성된 입력에 대해 AddRoundKey 함수를 적용하고,

마지막 라운드 전까지 매 라운드마다 SubBytes, ShiftRows, MixColumns, AddRoundKey 함수를 반복하여 적용합니다.

마지막 라운드에서는 MixColumns를 제외한 나머지 함수들만 적용합니다.

AES의 라운드 함수들은 역함수가 존재하므로, 역함수를 이용하여 AES 복호화가 이뤄집니다.

이제부터는 라운드를 구성하는 각 함수들에 대해 알아보겠습니다.

AES 라운드 함수

SubBytes

SubBytes는 State의 각 바이트를 S-Box를 참조하여 치환하는 함수입니다. 바이트의 상위 4비트가 행, 하위 4비트가 열을 결정합니다. 예를 들어 어떤 바이트가 2A라면, 해당 바이트는 S-box의 2행 A열을 참조하여 E5로 치환됩니다.

$$SubBytes\left(\begin{array}{c}\left[\begin{array}{cccc}D7& 32& 97& 71\\ 12& AA& F2& EC\\ 04& 00& CA& F9\\ 5E& 13& B1& 16\end{array}\right]\end{array}\right)=\left[\begin{array}{cccc}0E& C9& F2& 58\\ 23& AC& 63& 7D\\ 88& 89& 74& C8\\ A3& CE& 99& 47\end{array}\right]$$

ShiftRows

ShiftRows는 State의 각 행을 구성하는 바이트들을 쉬프트하는 함수입니다. 이 함수는 4가지 함수 중에서 유일하게 순열의 역할을 수행합니다. 아래와 같이 2행은 왼쪽으로 1칸, 3행은 왼쪽으로 2칸, 4행은 왼쪽으로 3칸을 밉니다. 복호화할 때는 반대로 2행, 3행, 4행을 각각 오른쪽으로 1칸, 2칸, 3칸씩 밉니다.

$$ShiftRows\left(\begin{array}{c}\left[\begin{array}{cccc}AE& 72& 3C& 7E\\ 83& 1A& 32& D3\\ 97& 18& 6A& C1\\ 56& 0C& 29& 86\end{array}\right]\end{array}\right)=\left[\begin{array}{cccc}AE& 72& 3C& 7E\\ 1A& 32& D3& 83\\ 6A& C1& 97& 18\\ 86& 56& 0C& 29\end{array}\right]$$

MixColumns

MixColumns는 열 단위로 치환을 수행하는 함수입니다.

$$\left[\begin{array}{c}{b}_0\\ b_1\\ b_2\\ b_3\end{array}\right]=\left[\begin{array}{cccc}02& 03& 01& 01\\ 01& 02& 03& 01\\ 01& 01& 02& 03\\ 03& 01& 01& 02\end{array}\right]\left[\begin{array}{c}{a}_0\\ a_1\\ a_2\\ a_3\end{array}\right]$$

AddRoundKey

이 함수는 키 생성 함수(Key Schedule)로 생성된 라운드 키의 state를 각 바이트별로 XOR합니다. 복호화할 때는 XOR의 성질을 이용하여 동일한 키를 state에 XOR합니다.

$$AddRoundKey\left(\begin{array}{c}state=\left[\begin{array}{cccc}63& A9& 24& 0D\\ 5C& 2A& 74& B6\\ A3& 30& 5D& 11\\ C5& 2C& 34& 7C\end{array}\right],key=\left[\begin{array}{cccc}21& 3C& C5& 71\\ CC& 6A& 82& C1\\ 75& 20& 53& 9C\\ 15& 7C& 63& 1E\end{array}\right]\end{array}\right)=\left[\begin{array}{cccc}42& 95& E1& 7C\\ 90& 40& F6& 77\\ D6& 10& 0E& 8D\\ D0& 50& 57& 62\end{array}\right]$$

키 생성 함수는 입력된 키로부터 각 라운드에 쓰일 라운드 키를 생성합니다. AES는 암복호화를 시작할 때와 매 라운드마다 AddRoundKey를 적용합니다. 따라서 AES-128에서는 라운드 키가 11개 필요합 합니다.
각 라운드 키는 4행 4열의 행렬이므로, 4행 44열의 키 행렬을 하나 만들고, 이를 4열씩 나눠서 매 AddRoundKey마다 사용하면 됩니다.

첫번째 AddRoundKey에서는 입력된 키를 그대로 사용합니다.

$w_{i\ge 4}$는 $W_{i-1}$에 RotWord, SubWord, Rcon을 적용하고, 이를 $W_{i-4}$와 XOR하여 생성합니다.

참고문헌

wikipedia - Advanced Encryption Standard

educative - What is the AES algorithm?

암호화 종류

암호화는 크게 3가지로 나눌 수 있다.

1. 대칭키 암호화

암호화 키가 1개이며 엑셀이나 ZIP파일을 암호화할 때 사용한다.

암호화 로직을 공개하고 암호화 키를 비공개하여 암호화 키를 모를 경우에 풀이 난이도가 상승하는 암호화 방식

암호화 키를 하나씩 대입하여 암호를 푸는 경우 몇백 년 정도의 시간이 걸리기 때문에 짧은 시간 내에 암호를 풀어야 할 경우에는 암호화 방식 특성상 안전하다고 생각한다.

종류에는 DES, AES, SEED 등이 있다.

2. 비대칭키 암호화

비대칭키는 공개키와 개인키로 2개의 암호화 키가 있다. 공개키는 말 그대로 공개된 키이며 개인키는 사용자만 알고 있는 키이다. 공개키로 암호화를 할 경우 개인키로 복호화할 수 있고 반대로 개인키로 암호화한 경우 공개키로 복호화할 수 있다. 비대칭키 암호화 방식은 공개키로 암호화하는 경우와 개인키로 암호화하는 경우로 나눌 수 있는데 공개키로 암호화했다면 데이터 보안에 중점을 둔 것이고, 개인키로 암호화했다면 안전한 전자서명을 통한 인증 과정에 중점을 둔 것으로 해석할 수 있다. 비대칭키의 대표 알고리즘은 RSA, 디피-헬만, 타원곡선 암호 등이 있다.

3. 단방향 암호화 (해시)

단방향 암호화는 보통 검증을 위해 사용하거나 평문을 모르게 하기위해 사용한다. 1비트만 달라져도(일부러 같은 해시값을 가지도록 조작하기 힘듬) 단방향 암호화 결과값이 달라지기 때문에 파일의 유효성을 검증하는데 사용한다.

해시는 암호문을 평문으로 복원할 수 없기 때문에 평문을 알아낼 필요가 없는 곳에 쓰이는데 대표적으로 사이트 비밀번호를 함호화 하는데 쓰인다.

레인보우 테이블 솔트

참고문헌

구글과 파이썬으로 시작하는 보안

암호의 역사

인류의 수천 년 속에서 위대한 왕과 장군들은 적에게 중요한 정보가 들어가지 않을까 우려했고
이에 각국 정부는 안전한 암호를 만드는 부서를 운영하였고 적국에서는 비밀을 빼내려는 암호 해독가를 양성했다.
암호의 역사는 암호를 만드는 사람들과 암호를 해독하려는 사람들이 벌여온 전쟁의 역사이다.

암호의 어원은 그리스어의 비밀이란 뜻을 가진 크립토스(Kryptos)로 알려져 있다.
이는 평문을 해독 불가능한 형태로 변형하거나 암호화된 통신문을 원래의 해독 가능한 상태로 변환하기 위한 모든 수학적인 원리, 수단, 방법 등을 취급하는 기술이나 과학을 말한다.

암호 기술의 발전 역사를 구분할 때 흔히 두 번의 큰 전환점을 기준으로

고대 암호, 근대 암호, 현대 암호 등의 세 단계로 나눠진다.
첫 번째 전환점은 1920년대, 1, 2차 세계 대전
두 번째 전환점은 컴퓨터를 이용한 암호 기술
이러한 전환점을 기준으로 고대로부터 1, 2차 세계 대전 이전가지 사용된 초보적인 암호 기술들을 고대 암호라고 하면,
1970년대까지 복잡한 기계 장치와 전자 장치들을 이용한 암호 기술을 근대 암호, 컴퓨터가 개발된 이후 컴퓨터를 이용하는 암호 기술을 현대 암호라고 부른다.

고대 암호

고대 봉건 사회에서는 지방 관리에게 보내는 비밀문서, 전쟁 중의 작전 지시와 보고, 첩자들과의 통신 등에 다양한 비밀통신 기법들이 사용되었다.
예를 들어, 멀리 기밀 정보를 전달해야 하는 경우에는 사자의 머리를 깎고 메시지를 쓴 후 머리를 길러서 보내면 받는 측에서는 사자의 머리를 깎고 메시지를 읽도록 하였다.
또 종이에 쓴 메시지가 그냥 보이지 않지만 불빛에 약품 처리를 하면 메시지가 나타나도록 하는 방법, 비밀 노출을 방지하기 위해 말로 전달하도록 하는 방법 등이 다양하게 사용되었다.
이러한 비밀 통신 방법을 스테가노그래피(Steganography)라고 하는데 적들도 이 통신 방식을 알고 있으면 비밀을 유지하기 어렵다는 한계를 갖고 있다.

스키테일 암호

기원전 500년 경 스파르타에서는 전쟁 중 왕의 명령을 전할 때 이 스키테일을 활용했다. 원리는 다음과 같다.
우선 전쟁에 나가는 군대가 왕과 굵기가 같은 원통형 막대기를 나눠 갖고, 메시지를 전달해야 될 상황이 오면 리본을 원통에 둘둘 말아 그 위에 메시지를 적는다.
이후 리본을 풀어 보면 일정한 간격으로 글자가 채워지는데, 빈 공간에 아무 글씨나 채워 넣으면 같은 지름의 원통을 가진 이들만 해당 암호를 해독할 수 있게 된다.

시저(Caesar) 암호

a를 d로 치환했으면, b는 e로, c는 f로 치환하는 방식으로 마지막 z는 c가 된다. 즉, d부터 시작하는 알파벳으로 글을 쓰고 이를 통해 중요한 내용을 전할 수 있다. 만약 Rome을 카이사르 암호를 활용해 암호화하면, ‘urph’라는 알 수 없는 단어가 등장하게 된다.

근대 암호

기계의 발달, 그리고 제 1·2차 세계대전으로 암호학은 비약적으로 발전했다.
근대 암호는 전자기계식 암호화 장치를 이용하는 기계 암호를 특징으로 한다.
이전에도 암호 대치 표나 막대 등의 보조도구를 사용하였지만,
기계를 도입함으로서 본격적으로 복잡한 수학 이론을 적용할 수 있었기에 해독에 상당한 어려움이 있었다.

에니그마

기계 암호로 가장 대표적인 것은 에니그마이다.

에니그마는 1918년 독일에서 발명된 암호화 기계로, 원래 상업적 목적으로 쓰였고 제1차 세계대전에서 독일군이 사용하면서 유명해졌다.

에니그마는 알파벳을 입력하는 타자기와 암호키가 내장된 회전자, 회전자를 연결하는 전기 배선, 그리고 반전자로 구성되어있다.

에니그마에는 각기 다른 암호키를 가진 3~5개의 회전자가 전기적으로 연결되어 있어, 타자기로 평문을 입력하면 회전자에 의해 다중으로 치환된 암호문이 출력된다.

이 암호문을 회전자와 배선, 반전자의 설정이 동일한 에니그마에 다시 입력하면 평문이 출력되면서 복호화가 이루어진다.
독일군은 에니그마의 보안성을 높이려고 반전자를 도입하고 의도적인 오·탈자까지 내었기 때문에,
똑같은 설정의 에니그마가 없으면 암호 해독은 거의 불가능하지만, 연합군의 암호 해독팀은 연산 기계를 이용해 에니그마를 해독하는 데 성공하였고, 이는 연합군의 승전에 큰 기여를 하게 된다. 이미테이션 게임연합군의 연산 기계는 컴퓨터의 시초가 되었다고 한다.

현대 암호

현대 암호는 1970년대 후반 스탠퍼드 대학과 MIT 대학에서 시작되었다. 1976년 스탠퍼드 대학의 Diffie와 Hellman은 ‘암호의 새로운 방향(New Directions in Cryptography)’이라는 논문에서 처음으로 공개키 암호의 개념을 발표하였다. 종래의 관용 암호 방식 또는 대칭키 암호 방식에서는 암호화 키와 복호화 키가 동일한 비밀키를 사용하기 때문에 송신자와 수신자는 비밀 통신을 하기 전에 비밀키를 공유하고 있어야 한다. 반면 공개키 암호 방식에서는 하나의 쌍이 되는 공개키와 비밀키를 생성하여 암호화에 사용되는 공개키는 공개하고, 복호화에 사용되는 비밀키는 사용자가 안전하게 보관하도록 한다. 공개키 암호 방식에서는 송신자와 수신자가 사전에 키를 공유할 필요가 없기 때문에 불특정 다수 사용자 간에 사전 준비가 없이도 암호 통신망을 구축하는데 유용하게 사용할 수 있다.

이어 1978년 MIT 대학의 Rivest, Shamir, Adleman은 소인수 분해 문제에 기반을 둔 RSA 공개키 암호를 개발했는데, 이것은 오늘까지도 가장 널리 사용되는 공개키 암호 방식이다. 공개키 암호의 도입은 현대 암호의 발전에 중요한 계기가 되었다.

한편, 1977년 미국 상무성 표준국(NBS, 현 NIST)은 전자계산기 데이터 보호를 위한 암호 알고리즘을 공개 모집하여, IBM 사가 제안한 DES (Data Encryption Standard)를 표준 암호 알고리즘으로 채택했다. DES의 표준화를 계기로 하여 금융 시스템을 중심으로 상업용 암호화의 이용이 증가하게 되었고 컴퓨터 통신망을 이용한 문서 전송, 전자 자금 이체 등이 활성화되었으며 암호 방식이 일반인들에게 알려지고 널리 사용되는 계기가 되었다.

이전의 암호 방식에서는 사용하는 키뿐만 아니라 암호 알고리즘도 비밀로 하여 암호문의 비밀을 지키려고 하는 경우도 있었으나, 현대 암호에서는 암호 알고리즘을 공개하도록 하고 있다. 1883년 Auguste Kerckhoff는 암호 시스템의 안전성에 대해 ‘키 이외에 암호 시스템의 모든 것이 공개되어도 안전해야 한다’고 했는데 이것을 Kerckhoff’s principle이라고 한다. 이렇게 함으로써 암호 방식의 안전성을 공개적으로 검토하게 하여 안전성을 확인하는 것이다.

참고문헌

KISA 암호 기술의 역사

STAR Library 암호이야기