[SimpleDES] Simplified Data Encryption Standard-2

Simplified Data Encryption Standard (Simplified DES) Practice

Author silnex


이전 글에서 SDES에 대한 내용과 필요한 함수들에 대해서 알아 보았다.
이번엔 직접 Keygen, Encryption 및 Decryption을 해보며 SDES에 대해서 알아본다.

Key Generation

Key 1 0 1 0 0 0 0 0 1 0
P10 3 5 2 7 4 10 1 9 8 6
P8 6 3 7 4 8 5 10 9

위 함수와 Key를 사용해 subKey(k1,k2)를 생성한다.

먼저 10bit의 key인 1010000010를 함수 P10에 넣는다.
 ▶ P10(1010000010) ::= (1000001100)
P10의 결과 값을 5bit 씩 쪼개어 LS-1을 진행한 뒤 다시 하나로 합친다.
 ▶ LS-1(10000) = (00001)
        LS-1(01100) = (11000) ::= 00001 11000

subKey 1 Gen LS-1의 결과 값을 P8에 넣는다.
 ▶ P8(0000111000) ::= 10100100 (k1)

LS한 결과 값에 LS-2를 한번 더 적용한 뒤 하나로 합친다.
 ▶ LS-2(00001) = (00100)
        LS-2(11000) = (00011) ::= 00100 00011

subKey 2 Gen LS-2의 결과값을 P8에 넣는다.
 ▶ P8(0010000011) ::= 01000011 (k2)

K1 K2
10100100 01000011

Encryption

PlainText 0 1 1 0 1 1 0 1
IP 2 6 3 1 4 8 5 7
E/P 4 1 2 3 2 3 4 1
P4 2 4 3 1
IP-1 1 3 5 7 2 8 6
S0 1 0 3 2 S1 0 1 2 3
3 2 1 0 2 0 1 3
0 2 1 3 3 0 1 0
3 1 3 2 2 1 0 3

위 함수를 통해 fk를 2번 반복한다.

8bit의 PlainText를 함수 IP에 넣는다.
 ▶ IP(01101101) ::= 1110 0110
{START fk} IP의 결과 값 중 오른쪽4bit(0110)를 함수 E/P에 넣는다.
 ▶ E/P(0110) ::= 00111100
 E/P 결과 값에 subkey k1과 xor 연산을 한다.
 ▶ 00111100 ⊕ 10100100 ::= 1001 1000
k1과 Xor한 결과 값을 S-Box에 넣어 매치되는 행렬값을 구한 뒤 합친다.
 ▶ S0(11,00) = S0(3,0) = 11 (3) | S1(10,00) = S1(2,0) = 11 (3) ::= 1111
S-Box의 결과 값을 P4에 넣고 처음 IP의 결과 값 중 왼쪽4bit와 Xor 연산을한다.
 ▶ P4(1111) ::= 1111 
       1111 ⊕ 1110 ::= 0001 {END fk}
Xor의 결과 값과 처음 IP의 결과 값 중 오른쪽4bit의 순서를 바꾼다.
 ▶ SW(0001 0110) ::= {0110 0001}

SW값을 한번 더 함수 fk를 반복한다.
{START fk} ▶ E/P(0001) ::= 10000010
 ▶  10000010 ⊕ 01000011 ::= 1100 0001
 ▶ S0(10,10) = S0(2,2) = 01 (1) | S1(01,00) = S1(1,0) = 10 (2) ::= 0110
 ▶ P4(0110) ::= 1010
      1010 ⊕ 0110 ::= 1100 {END fk}
 ▶ >> {1100 0001}

두번의 fk에서 나온 결과 값을 IP-1에 넣는다.
 ▶ IP-1(1100 0001) = 01000110
이렇게 나온 결과 값 0 1 0 0 0 1 1 0가 PlainText(01101101)를 Key(1010000010)로 암호화한 CipherText(암호문)이 된다.


 

Decryption

 

CipherText 0 1 0 0 0 1 1 0
IP 2 6 3 1 4 8 5 7
E/P 4 1 2 3 2 3 4 1
P4 2 4 3 1
IP-1 1 3 5 7 2 8 6
S0 1 0 3 2 S1 0 1 2 3
3 2 1 0 2 0 1 3
0 2 1 3 3 0 1 0
3 1 3 2 2 1 0 3

위 함수를 통해 fk를 2번 반복하는데 Encryption과 과정은 동일하다.
하지만 이번엔 Decryption이기 때문에 fk에서 사용되는 key의 순서가 k2, k1순으로 사용되어야한다.

8bit의 CipherText를 함수 IP에 넣는다.
 ▶ IP(01000110) ::= 1100 0001
{START fk} IP의 결과 값 중 오른쪽4bit(0001)를 함수 E/P에 넣는다.
 ▶ E/P(0001) ::= 10000010
 E/P 결과 값에 subkey k1과 xor 연산을 한다.
 ▶ 10000010 ⊕ 01000011 ::= 1100 0001
k1과 Xor한 결과 값을 S-Box에 넣어 매치되는 행렬값을 구한 뒤 합친다.
 ▶ S0(10,10) = S0(2,2) = 01 (1) | S1(01,00) = S1(1,0) = 10 (2) ::= 0110
S-Box의 결과 값을 P4에 넣고 처음 IP의 결과 값 중 왼쪽4bit와 Xor 연산을한다.
 ▶ P4(0110) ::= 1010
       1010 ⊕ 1100 ::= 0110 {END fk}
Xor의 결과 값과 처음 IP의 결과 값 중 오른쪽4bit의 순서를 바꾼다.
 ▶ SW(0110 0001) ::= {0001 0110}

SW값을 한번 더 함수 fk를 반복한다.
{START fk} ▶ E/P(0110) ::= 00111100
 ▶ 00111100 ⊕ 10100100 ::= 1001 1000
 ▶ S0(11,00) = S0(3,0) = 11 (3) | S1(10,00) = S1(2,0) = 11 (3) ::= 1111
 ▶ P4(1111) ::= 1111
       1111 ⊕ 0001 ::= 1110 {END fk}
 ▶ >> {1110 0110}

두번의 fk에서 나온 결과 값을 IP-1에 넣는다.
 ▶ IP-1(1110 0110) = 01101101
이렇게 나온 결과 값 0 1 1 0 1 1 0 1가 CipherText(01000110)를 Key(1010000010)로 복호화한 PlainText(평문)이 된다.


이미지 출처 및 참고 자료

[SimpleDES] Simplified Data Encryption Standard

Simplified Data Encryption Standard (Simplified DES)

Author silnex


Introduce S-DES

TL; DR
바로 Example로 넘어가고 싶다면,
[SimpleDES] Simplified Data Encryption Standard Practice 로…

Padding Oracle Attack을 공부하기 위해 CBC에 대해서 공부하던 중 Block Cipher에 대해 자세히 알고 싶다는 생각이 들어,
지금은 사용되지 않지만 가장 유명한 암호화 방식인 Data Encryption Standard(DES)를 공부하게 되었다.
DES알고리즘을 학습해야하지만 일반적인 DES에서 사용되는 key인 56bit는 다소 복잡해 이해 하기가 어려워,
key가 10bit로 이루어진 Simplified DES를 통해 DES알고리즘에 대해서 학습해본다.

SDES는 기존 DES와 Key의 bit수 차이와 반복되는 Round 의 차이만 있을 뿐 알고리즘은 동일하며,
SDES의 확장을 통해 DES를 이해를 위해 만들어진 SDES인 만큼 DES의 56bit키가 왜 위험한지에 대해서도 충분이 이해 할 수 있다고 한다.

Analyze DES

SDES Scheme (위 그림에 오류가 있는데 keygen을 하는 부분에서 2번째 Shift는 Shift를 2번해주어야 한다.)

DES는 대칭키 암호이기 때문에 Key를 통해 subKey인 K1과 K2를 생성하는 Key Generation()과정, (PlainText를 Block단위로 쪼개어 암호화 하기위해서다. DES가 Block Cipher라 불리는 이유)
PlainText(평문)를 암호화하는 Encryption() 과정,
암호화된 CipherText(암호문)를 복호화 하는 Decryption()과정까지 총 3개의 과정이 필요하다.

이제 필요한 함수에(P10, P8, Shift, IP, IP-1, SW, fk, E/P, S-Box, P4 )대해서 알아보자.

Functions

Key Generation에서 사용되는 함수들

Keygen for Simplified DES

 

Function P10 

input length(or bit): 10
output length(or bit): 10

P10의 P는 Permutation(순열)의 약자로, 아래와 같은 함수로 표현된다.

P10(k1, k2, k3, k4, k5, k6, k7, k8, k9, k10) = (k3, k5, k2, k7, k4, k10, k1, k9, k8, k6)

수식으로 표현하니 이해하기 여러울 수 도있지만, 단순히 순서를 바꾸는 역할을 할 뿐이다.
예를들어 P10(1,2,3,4,5,6,7,9,0) = (3,5,2,7,4,10,1,9,8,6) 처럼 순서만 바꾸는 역할을 한다.
다만, P10에서 사용되는 바뀌는 순서에 대한 값은 임의의 값이 아닌 SDES에서 고정적인 값이다.

P10을 표로써 표현하면 아래와 같이 표현할 수 있다.

P10
3 5 2 7 4 10 1 9 8 6

 

Function P8 

input length(or bit): 10
output length(or bit): 8

또한 P10과 같은 의미이나 10개의 인자값을 받아 8개만 선택해 출력하는 함수이다.
수식으로 표현하면,

P8(k1, k2, k3, k4, k5, k6, k7, k8, k9, k10) = (k6, k3, k7, k4, k8, k5, k10, k9)

즉, 결과 값에 없는 k1, k2는 버려진다. 이를 표로 표현하면 아래와 같이 표현 할 수 있다.

P8
3 7 4 8 5 10 9

 

Function Shift

input length(or bit): 5
output length(or bit): 5

Shift는 BitShift연산자중에서 Left Shift를 의미하는데, 왼쪽으로 넘어간 bit는 오른쪽에서 나오게 된다.
즉, 10011(2)을 Shift 2번 이라고 한다면, 00111(2)이 되는것이다.
대게 줄여서 LS라고 하며 Shift횟수에 따라 한번이면 LS-1 두번이면 LS-2라고 한다.

수식으로 표현하자면,

LS-1(10110(2)) = 01101(2); LS-2(11011(2)) = 01111(2)

 

Encryption, Decryption에서 사용되는 함수들

XOR(⊕)은 따로 설명하지 않는다.

Simplified DES Encryption Detail

 

Function IP and IP-1

input length(or bit): 8
output length(or bit): 8

IP는 Initial and Final Permutations의 약자로, 처음과 끝에 순서를 바꾸어 주는 역할을 한다.
즉 P10 과 크게 다르지 않다. 다만 IP는 ‘역’인 IP-1 가 존재한다. 
수식으로 표현하면,

IP(k1, k2, k3, k4, k5, k6, k7, k8) = (k2, k6, k3, k1, k4, k8, k5, k7)
IP-1(k2, k6, k3, k1, k4, k8, k5, k7) = (k1, k2, k3, k4, k5, k6, k7, k8)

으로 표현된다. 즉, IP-1(IP(X)) = X란 뜻이다.
이를 간단히 표를 통해 표현하면 아래와 같다.

IP
2 6 3 1 4 8 5 7
IP-1
4 1 3 5 7 2 8 6

 

Function fk

input length(or bit): 8
output length(or bit): 8

fk에서 k는 keygen에서 생성된 key의 종류를 의미한다.
fk는 입력받은 8bit의 값을 4bit/4bit 으로 쪼개어 왼쪽bit/오른쪽bit라고 부르며 나누어 사용한다.

중요한건 오른쪽bit인데 순서데로 E/P를 거쳐 Xor후에 S0, S1로 나누어져 동작 하고,
이를 다시 P4의 넣어 출력후 왼쪽bit와 Xor한다.
말로 표현하니 이해가 힘들수도 있지만, DES에서 가장 핵심이기에 잘 알아두자.

 

Function E/P

input length(or bit): 4
output length(or bit): 8

E/P는 Expansion/Permutation의 약자로 말 그대로 확장하고 순서를 바꾼단 뜻이다.
이도 IP나 P10과 같이 순서를 바꾸는 것은 동일하지만 4자리의 bit를 8bit로 확장 한다는 점이다르다.

E/P를 수식으로 나타내면 다음과 같고,

E/P(k1, k2, k3, k4) = (k4, k1, k2, k3, k2, k3, k4, k1)

이를 표로 나타내면 아래와 같다.

E/P
4 1 2 3 2 3 4 1

 

Function S0 S1(S-Box)

S0, S1 각각 input length(or bit): 4
output length(or bit): 2

S0와 S1는 S-Box라고 불리며, 기존의 E/P, IP, P10과는 달리 행렬을 이용한 연산이지만,
그렇게 복잡한 연산은 아니다.
다만, 이를 위해선 고정된 S-box 행렬이 필요한데 두 행렬은 아래와 같다.

S0 1 0 3 2 S1 0 1 2 3
3 2 1 0 2 0 1 3
0 2 1 3 3 0 1 0
3 1 3 2 2 1 0 3

입력(4bit)에대하여 위의 행렬을 참고해 다음과 같은 연산을 진행한다.

Ex) input : 0101 1010(2) 
(구분을 위해 색을 칠했으며, E/P와 key을 xor한 8bit 입력을 4bit로 쪼개어 각각 대입하여 사용한다.)

S0(01(2),10(2)) S1(10(2),01(2)) => S0(1,2) S1(2,2) => 1, 1 => 01 01(2)

S-box를 수식으로 표현하면 다음과 같이 표현할 수 있으나 이해가 위 예제를 통해 이해가 힘들때 참고 정도로만 사용하면된다.

i = input; n = 0, 1;
Sn(i1,4,i2,3)

Function P4

input length(or bit): 4
output length(or bit): 4

P4는 기존의 IP P10과 동일하게 4자리의 bit를 순서를 바꾸어 주는 역할을 한다.
수식으로 표현하면 다음과 같고,

P4(k1, k2, k3, k4) = (k2, k4, k3, k1)

표로 표현하면 아래와 같다.

P4
2 4 3 1

 

Function SW

input length(or bit): 8
output length(or bit): 8

SW는 단순히 왼쪽 4bit와 오른쪽4bit를 바꾸어주는 역할을 한다.
간단한 과정이니 수식으로만 표현하겠다.

SW(k1, k2, k3, k4, k5, k6, k7, k8) = (k5, k6, k7, k8, k1, k2, k3, k4)


이로써 S DES에서 암호화, 복호화와 키 생성에 필요한 함수를 모두 알아보았다.
이를 통해 다음 글에선Key를 직접 생성해 보고 Encryption과 Decryption을 직접 해본다.

 


이미지 출처 및 참고 자료

http://homepage.smc.edu/morgan_david/vpn/C-SDES.pdf

 

PushPush 순서도(알고리즘) 만들기

PUSH_PUSH Video

[onedrivefile id=”file.c18eeaaf089d2b4b.c18eeaaf089d2b4b!10735″]

Main Func

[onedrivefile id=”file.c18eeaaf089d2b4b.c18eeaaf089d2b4b!10734″]

Move Func

[onedrivefile id=”file.c18eeaaf089d2b4b.c18eeaaf089d2b4b!10732″]

AddRandomBlock Func

[onedrivefile id=”file.c18eeaaf089d2b4b.c18eeaaf089d2b4b!10731″]

Display & FinishCheck Func

[onedrivefile id=”file.c18eeaaf089d2b4b.c18eeaaf089d2b4b!10733″]

 

제 7-1강 RSA_완성(Code Only)

RSA 완성 Only Code

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define INT unsigned int 

void Find_Prime_Number(char * num_str, INT fn) {
	INT start = 3;
	int i = 2;
	for (start = 3; start < fn; start += 2) {
		if (0 == num_str[start]) {
			while (start * i < fn) {
				num_str[start*i] = 1;
				i++;
			}
			i = 2;
		}
	}
}
// 소수를 찾는 함수
INT gcd(INT a, INT b) {
	if (0 == b) return a;
	return gcd(b, a % b);
}
// 유클리드 알고리즘을 이용하여 최대공약수 구하는 함수
INT inverse(INT a, INT b) {
	int r1, r2, q, r, t, t1, t2;
	r1 = a;
	r2 = b;
	t1 = 0;
	t2 = 1;

	while (r1 != 1)
	{
		q = r2 / r1;
		r = r2 - r1*q;
		t = t1 - t2*q;
		r2 = r1;
		r1 = r;
		t1 = t2;
		t2 = t;
	}
	if (t2 < 0)
		t2 = t2 + b;
	return t2;
}
// 확장되 유클리드 알고리즘을 이용한 모듈러 연산의 역원을 구하는 함수
INT expo_algorism(INT a, INT b, INT n)
{
	INT result = 1;

	while (b)
	{
		if (b & 1)
		{
			result = (result * a) % n;
		}
		b /= 2;
		a = (a * a) % n;
	}
	return result;
}
// 고속 누승 알고리즘
INT phi(INT p, INT q) {
	return (p - (INT)1)*(q - (INT)1);
}       
// phi(n) = (p-1)*(q-1)

int main(void) {
	INT fn = 256, i, j = 0, k;
	INT * _str;
	char * str;
	INT p, q;
	//	2	3	  4		 5		6
	INT n, phi_n, e = 3, d = 3, a, c;
	/* 1. 임의의 소수 찾기 {{ */
	str = (char*)calloc((fn + 1), sizeof(char));
	Find_Prime_Number(str, fn);
	if (str == NULL) {
		printf("메모리 영역 오류 입니다.\n");
		free(str);
		return 0;
	}
	for (i = 3; i < fn; i += 2) {
		if (str[i] == 0) {
			j++;		// 소수의 갯수 저장
		}
	}

	_str = (INT*)calloc(j + 1, sizeof(INT));
	if (_str == NULL) {
		printf("메모리 영역 오류 입니다.\n");
		free(str);
		free(_str);
		return 0;
	}
	j = 0;

	for (i = 3; i < fn; i += 2) {
		if (str[i] == 0) {
			_str[j] = i;
			j++;
		}
	}
	srand(time(NULL));
	k = rand() % j;
	p = _str[k];
	k = rand() % j;
	q = _str[k];
	/* }} */

	// 2.
	n = p * q;
	// 3.
	phi_n = phi(p, q);
	
	// 4.
	while (gcd(e, phi_n) != 1) {
		e++;
		if (e > n) {
			free(str);
			free(_str);
			return 0;
		}
	}

	// 5.
	d = inverse(e, phi_n);
	// 6.
	a = rand() % n;
	c = expo_algorism(a, e, n);
	if (expo_algorism(c, d, n) == a)
		printf("공개키: %u, 비밀키: %u\n",e,d);
	printf("p: %u, q: %u\n", p, q);

	free(str);
	free(_str);
	return 0;
}

 

[제 7강] RSA

RSA

순서

  1. 256 보다 작은 소수 p와 q를 에라토네스 체 사용해서 구하시오. (단 p > q)
  2. n =  p * q 를 계산하시오. 
  3. phi(n) = phi(p*q) = phi(p)*phi(q) = (p-1) * (q-1)을 계산하시오.
  4. 암호 키 e, (0 < e < n, gcd(e, phi(n)) = 1)을 선택하시오.
  5. 복호키 e * d = 1 mod phi(n) 인 d를 구하시오. 
  6. N 보다 작은 수 a 에 대해, a ^ e mod n = c 를 계산하시오.
  7. c ^ d mod n = a 인지 확인하시오.

코드

#include "Self_Cryptograph_Math.h"

INT phi(INT p, INT q) {
	return (p - (INT)1)*(q - (INT)1);
}

int main(void) {
	INT fn = 256, i, j = 0, k;
	INT * _str;
	char * str;
	INT p, q;
	//	2	3	  4		 5		6
	INT n, phi_n, e = 3, d = 3, a, c;
	/* 임의의 소수 찾기 {{ */
	str = (char*)calloc((fn + 1), sizeof(char));
	Find_Prime_Number(str, fn);
	if (str == NULL) {
		printf("메모리 영역 오류 입니다.\n");
		free(str);
		return 0;
	}
	for (i = 3; i < fn; i += 2) {
		if (str[i] == 0) {
			j++;		// 소수의 갯수 저장
		}
	}

	_str = (INT*)calloc(j + 1, sizeof(INT));
	if (_str == NULL) {
		printf("메모리 영역 오류 입니다.\n");
		free(str);
		free(_str);
		return 0;
	}
	j = 0;

	for (i = 3; i < fn; i += 2) {
		if (str[i] == 0) {
			_str[j] = i;
			j++;
		}
	}
	srand(time(NULL));
	k = rand() % j;
	p = _str[k];
	k = rand() % j;
	q = _str[k];
	/* }} */

	// 2.
	n = p * q;
	// 3.
	phi_n = phi(p, q);
	
	// 4.
	while (gcd(e, phi_n) != 1) {
		e++;
		if (e > n) {
			free(str);
			free(_str);
			return 0;
		}
	}

	// 5.
	d = inverse(e, phi_n);
	// 6.
	a = rand(time(NULL)) % n;
	c = expo_algorism(a, e, n);
	if (expo_algorism(c, d, n) == a)
		printf("공개키: %u, 비밀키: %u\n",e,d);
	printf("p: %u, q: %u\n", p, q);

	free(str);
	free(_str);
	return 0;
}

 

추가적 내용

inverse 코드가 잘 못 되어 답이 나오지 않았습니다.
만약 2015 / 10 / 22 일자 inverse 코드를 보고 오신 분은 아래의 코드로 바꾸어 주시면 정확한 결과가 나옵니다. 죄송합니다.

INT inverse(INT a, INT b) {
	long E, N, q, r, s, t, u;
	E = a;
	N = b;
	t = 0; u = 1;

	while (E != 1)
	{
		q = N / E;
		r = N - E*q;
		s = t - u*q;
		N = E;
		E = r;
		t = u;
		u = s;
	}
	if (u < 0)
		u = u + b;
	return u;
}

게시물은 차후 수정하겠습니다.

[제 6강] 고속 누승 알고리즘과 모듈러

고속 누승 알고리즘과 모듈러 연산

누승 알고리즘이란 거듭 제곱을 의미하고 모듈러 연산이란 % 연산자이다.

거듭 제곱은 while 문으로 계속 a를 곱하면 되고
모듈러는 % 연산자로 해결 하면 되니 바로 코드를 짜보자.

int expo_algorism(int a, int b, int n)
{
    int result = 1;

    while( b > 0 )
   {
      result  = (result * a) % n ;
      b--;
    }
     return result;
}

a ^ b mod n 의 값을 계산 해주는 코드가 바로 완성 됬다.

하지만 여기서 문제가 하나 있다. 암호 수학 에서 쓰는 수는 매우 큰 숫자를 사용한다.
그렇기에 a ^ b 에서 b=1000이 넘어가 버리면 약 10^300 년 정도 걸리기에 실 사용이 불가능하다.

 

그렇기에 위와 같은 문제점을 해결한 알고리즘을 짜보도록 하자.

a ^ 30 = (a ^ 15) ^2          : 제곱셈 1회
a ^ 15 =  (a ^ 7 )^2 *  a    : 제곱셈 1회 + 곱셈 1회
a ^ 7   = (a ^3 ) ^ 2 * a     : 제곱셈 1회 + 곱셈 1회
a ^ 3   = (a ^ 2 ) ^ a          : 제곱셈 1회 + 곱셈 1회

               총                        : 제곱셈 4회 + 곱셈 3회 = 7회

이렇게 계산 한다면 계산 횟수가 확실히 적어지게 된다.

 

그럼 위의 알고리즘을 이용하여 코드를 만들어 보도록 하자.

INT expo_algorism(INT a, INT b, INT n)
{
    INT result = 1;

    while(b)
   {
      if(b & 1)
      {
         result = (result * a) % n ;
      }
       b /= 2;   
       a  = (a * a) % n ;
   }
   return result;
}

이 코드도 a ^ b mod n 을 계산해 주는 프로그램이지만 개선된 알고리즘을 사용해 더 빠른 속도로 연산을 해낼 수 있게 되었다.

간단히 분석해보자면

1.

 if(b & 1)
      {
         result = (result * a) % n ;
      }

이 부분은 b&1(=b가 홀수) 일 때 × a를 하고 mod n 값을 구한다.

2.

       b /= 2;   
       a  = (a * a) % n ;

지수 (b)를 절반씩 줄이고 a에 a^2을 한 뒤 mod n 의 값을 넣는다.

 

이것으로 RSA를 만들기 위한 준비는 끝이 났다.

다음 글에선 부가적인 설명 없이 바로 RSA를 만들도록 하겠다.

[제 5강][수정됨] 확장 유클리드 알고리즘.function

확장 유클리드 알고리즘

m, n이 gcd(m,n) = 1인 경우 유용한데, 그럼 위의 식은 am + bn = 1이 되고, 여기서 a모듈로 연산의 곱의 역원(modular multiplicative inverse)이 되기 때문이다.
출처 : 위키백과

확장 유클리드 알고리즘은 RSA를 만들기 위한 과정 중 복호키(또는 비밀키 라고도 부른다)를 구하기 위해 필요한 알고리즘이다.
일단 지금은 이 정도만 알고 넘어가도록 하자.

확장 유클리드 알고리즘은 정말 단순히 유클리드 알고리즘(gcd)연산을 거꾸로 한 것이다.
수식으로 설명을 들어보자,

a , b = 서로소인 두 정수(알기 쉽게 설명하기 위해서 서로소로 정했다\\ 원래는 어떤 수 라도 상관 없다.)
r(1),r(2),r(3)… = 나머지
q(1),q(2),q(3)… = 몫

라고 하면, 유클리드 알고리즘은

gcd(a,b)
=> a = b*q(1) + r(1)           >> gcd(b,r(1))
=> b = r(1)*q(2) + r(2)       >> gcd(r(1),r(2))
=> r(1) = r(2)*q(3) + r(3)   >> gcd(r(2),r(3))
……
=> r(n-1) = r(n)*q(n+1) + r(n+1)     >> gcd(r(n),r(n+1))
=> r(n) = r(n+1)*q(n+2) + 1             >> gcd(r(n+1),r(n+2))
=> r(n+1) = 1*r(n+1) + 0                  >> gcd(1,0)
∴ gcd(a,b) = 1

이렇게 진행 된다.

=====================================================

이제 확장된 유클리드 알고리즘 이용해 보자.
방법은 단순히 위에 연산을 거꾸로하고 대입하여 한 식으로 계산하면 된다, 아래를 참고하자.

[원래는 1 부터지만 거꾸로 계산했다는 것을 보여주기 위해 0부터 시작하겠다.]
0 = r(n+1) – 1*r(n+1) <=> r(n+1) = 1*r(n+1) + 0
1 = r(n) – r(n+1)*q(n+2) <=> r(n) = r(n+1)*q(n+2) + 1
r(n+1) = r(n-1) – r(n)*q(n+1) <=> r(n-1) = r(n)*q(n+1) + r(n+1)
……
r(3) = r(1) – r(2)*q(3) <=> r(1) = r(2)*q(3) + r(3)
r(2) = b – r(1)*q(2) <=> b = r(1)*q(2) + r(2)
r(1) = a – b*q(1)  <=> a = b*q(1) + r(1)

이제 거꾸로 구한 식을 한 식에 모두 대입하자. (복잡하니 n = 2 라고 두자)  (a, b, q(),r() 은 모두 상수 이다. )

[“0 = ~”은 양변이 모두 0 이므로 사용 할 수 없으니 “1 = ~”를 사용했다]
1 = r(2) – [r(1) – [b – [a – b*q(1)]*q(2)]*q(3)]*q(4)

이렇게 식을 만들고 정리 하면 1 = ☆×a + ★×b  이런 모양이 된다.

∴   1 ≡ ☆×a + ★×b (mod a) 라면, ★값이 역원(우리가 찾는 값) 이고
   1 ≡ ☆×a + ★×b (mod b) 라면, ☆ 값이 역원 이다.

즉, mod a 라면 b에 곱해진 수가 역원 mod b라면 그 반대 라는 것이다.

(∵  A≡R (mod P) 이면. A = A*X + R 양변에 P를 더해 준다면 => A + P = P* (X + 1) + R이다.
따라서 나머지(다른)값은 변화가 없음으로, 위에서 mod a 일때, ☆×a 값을 무시 할 수 있다.)

자 이렇게 확장 유클리드 알고리즘에 대한 기본 설명은 끝났다.

이해가 잘 가지 않을 수도 있으니 간단한 예를 들어보자.

a = 576, b = 31

유클리드 알고리즘

576 = 31 × 18 + 18
31 = 18 × 1 + 13
18 = 13 × 1 + 5
13 = 5 × 2 + 3
5 = 3 × 1 + 2
3 = 2 × 1 + 1         ∴ gcd(576,31) = 1, 서로소 이다.

확장 유클리드 알고리즘(빠르게 계산 하기 위해 바로 “1 = ~”으로 시작하겠다.)

1 = 3 – 2 × 1
   = 3 – [5 – 3 × 1] × 1
   = 3 – [5 – [13 – 5 × 2] × 1] × 1
   = 3 – [5 – [13 – [18 – 13 × 1] × 2] × 1] × 1
   = 3 – [5 – [13 – [18 – [31 – 18 × 1] × 1] × 2] × 1] × 1
   = 3 – [5 – [13 – [18 – [31 – [576 – 31 × 18] × 1] × 1] × 2] × 1] × 1
──────────이해를 위한 순서──────────┘
   = 1 = 3 – 2
   = 3 – (5 – 3)
=> 2 * 3 – 5                                   << 정리를 해야 나중에 원하는 모양이 나옴
   = 2 * ( 13 – 5 * 2 ) – 5
=> 2 * ( 13 ) – 5 * 5
   = 2 * 13 – 5 * ( 18 – 13 )
=> -5 * ( 18 ) + 7 * 13
   = -5 * 18 + 7 * ( 31 – 18 )
=> 7 * 31 – 12 * ( 18 )
   = 7 * 31 – 12 * ( 576 – (31 * 18) )
=> -12 * 576 + 223 * 31
──────────실제 계산 순서──────────┘

   => -12 × 576 + 223 × 31 ≡ 1 (mod 576)
∴ 역원(우리가 찾는 값)은 223 이다.

 

위 알고리즘을 이용해 C언어로 코딩 하기전에 잠깐 생각해야 되는 부분이 있다.
우리가 필요한 값은 결과로 나오는 1 = ☆×a + ★×b 중에서 ☆or★이라는 점을 기억 해야 한다.

이제 한번 코딩해 보자.

#include <stdio.h>
#include <stdlib.h>
#define INT unsigned int 

INT inverse(INT a, INT b) {
	long r1, r2, q, r, t, t1, t2;
	r1 = a;
	r2 = b;
	t1 = 0; t2 = 1;

	while (r1 != 1)
	{
		q = r2 / r1;
		r = r2 - r1*q;
		t = t1 - t2*q;
		r2 = r1;
		r1 = r;
		t1 = t2;
		t2 = t;
	}
	if (t2 < 0)
		t2 = t2 + b;
	return t2;
}

1 = ☆×a + ★×b 일때,

t1 << 우리가 찾는 값
t2
a r1
b r2
t, q, r 임시 저장 공간(단, q는 몫을 임시 저장한다)

 

이렇게 정리 할 수 있다. 이번 글은 이해하기 어려웠다. 하지만 차근차근 하다 보면 이해 할 수 있을 것이다.

다음 글에선 이것 보다 간단한 고속 누승 알고리즘에 대해 알아보도록 하자.

 

부록 _ RSA에선 어떻게 쓸까?

e × d ≡ 1 (mod (N)) 이미 알고 있는
N [= p×q, 임의의 두 소수p, q] \\ (N)[= (p-1)(q-1)] \\ e (= gcd(e,(N)) = 1이 되는 e)의 값을 대입하여 확장 유클리드 알고리즘을 이용해 비밀키 d 값을 구한다.

 

참고 글 : 123

[제 4강] 최대공약수.function

최대공약수 (유클리드 알고리즘을 이용)

gcd(a,b)로 표현 하기도 하는 이번 글에선 최대공약수를 다뤄보려고 한다.

 

우리가 보통 최대공약수를 구하는 방법음 다음과 같다.

2 │ 48  18
3 │ 24   9
   └────
         8     3
이렇게 구한 뒤에 세로로 곱한다면 최대공약수가 나오는 방식으로 여태까지 구해 왔다.

하지만 컴퓨터는 이러한 방법으로는 최대공약수를 구하지 못한다.
또한 각 수를 모두 소수로 분해해야 하기에 매우 비효율적이다.

지금부터 컴퓨터가 해결할 수 있도록 위에서 구한 식을 함수 gcd(a,b)를 이용해 풀어보자.

======================================================================

그전에 먼저 mod(모듈러)에 대해 알아야 한다.
mod 계산은 C언어의 %연산자와 같은 역할은 한다. 즉, 나머지를 구하는 연산자라는 것이다. 

예를 들어,

105 mod 10 = 5 이다.

또한 mod연산자는 양쪽에 쓰지 않고 한쪽으로 몰 수 있는데,
105 = 15 (mod 10) 이렇게쓰여 있다면,
105 mod 10 = 15 mod 10
5 = 5가 된다.

======================================================================

그럼 이제 다시 최대공약수로 돌아가서 함수 gcd(a,b)에 대해 알아보자.

함수 gcd(a,b)의 작동 방식은 gcd(a,b) = gcd(b,a mod b)로 매우 단순하다.
예를 들어, a=48, b=18 이라면,

gcd(48,18) = gcd(18,12) = gcd(12,6) = gcd(6,0) 이 된다.
그리고 b=0이므로 gcd(48,18) = gcd(6,0)= 6 이다.
즉, b자리0이되최대공약수는 a인 것이다.

 

자 이제 알고리즘을 만들어 보자 (유클리드 알고리즘)

1. gcd(a,b)에서 b값이 0이 아니라면, a mod b 연산을 실행
2. a 자리에 b를 넣고 a mod b의 결과를 b의 자리에 넣는다.
3. 1,2를 반복한다. 만약 b=0이라면 a값이 최대공약수이다.

알고리즘은 mod 만 안다면 매우 간단하다.
이제 알고리즘을 C로 코딩해보자.

#include <stdio.h>
#include <stdlib.h>
#define INT unsigned int 

INT gcd(INT a, INT b) {
	if (0 == b) return a;
	return gcd(b, a % b);
}

끝이다. 정말 이게 끝이다.
솔직히 이런 방법은 생각치도 못했었다. 하지만 누가 2줄로 완성했다는 소리를 듣고 어떻게 짜야 2줄 이내로 짤 수 있을까 고민 하던 중

“반환 값을 함수로 주면 되겠다.” 라는 생각에 실제로 해보니 결과는 성공적이였다. 여기서 한 수 알아갔다.

이로써 최대공약수와 소수를 찾을 수 있게 되었다.

이제 N=p×q, (N) = (p-1)(q-1)와 유클리드 호제법만 만들면 RSA를 만들기 위한 기본적인 함수 준비는 모두 끝나게 된다.