ALL OF RSA

---

---

• Concept of RSA
• what is asymmetric key?
• what is RSA?
• Caculation of RSA key
• Why RSA believe in?
• Decoding/Encoding
• code RSA key calculation program
• structure of code
• sample
• source code
• code RSA encoding/decoding program
• square & multiply algorithm
• source code

---

Concept of RSA (RSA의 개념)

what is asymmetric key?

RSA의 정의와 그 원리에 관해 관심이 있다면,(애초에 이 문서를 읽는 이라면,) 비대칭 키라는 말은 한 번쯤 들어보았을 것이다. 이는 “암호화 키와 복호화 키가 다른 암호화 방식”을 뜻한다. 전하고자 하는 메시지와 암호문이 있다면, 메시지를 암호문으로 암호화할 때 사용하는 키와, 암호문을 메시지로 해석할 때 사용하는 키가 서로 다르다는 뜻이다.

Yesica의 비대칭 금고

그 예시로, 하나의 금고를 생각해보자. 은행장인 Yesica씨는 매일 이용고객한테 이자를 현물로 걷는다. 그는 매일 밤 고객들이 자신의 금고에 그 이자를 넣어두기를 바란다.

이러한 상황에서 Yesica는 문제에 빠질 수밖에 없다. 고객들이 Yesica의 금고에 이자를 넣어주기 위해서는 Yesica씨 금고의 비밀번호를 알고 있어야 하는데, 고객이 금고의 비밀번호를 알게 되면 역으로 다른 고객이 넣어둔 이자를 빼갈 수도 있기 때문이다.

우리는 Yesica에게 '비대칭 금고'를 만들어 줌으로써 이 문제를 해결해 줄 수 있다. 이 금고는 물건을 금고에 넣을 때 사용하는 비밀번호와, 물건을 금고에서 빼낼 때 사용하는 비밀번호가 다르다.

Yesica는 고객들에게 이자를 금고에 넣을 때 사용하는 비밀번호를 알려주고, 금고에서 이자를 빼내기 위한 비밀번호는 Yesica만 알고 있음으로써 Yesica가 원하는 금고 시스템을 구축하였다.

비대칭 키 알고리즘에서는, “공개키”(Public key)가 이 금고에 물건을 넣기 위한 비밀번호의 역할을 가지고, “개인키”(Private key)가 물건을 빼내기 위한 비밀번호의 역할을 가진다. Yesica에게 보내는 이자들은 Yesica에게 보낼 메시지라 할 수 있고, 그 메시지들은 금고 안에 들어가거나, 빠져나가는 순간 공개키로 암호화 또는 개인키로 복호화 된다.

 

이러한 비대칭 키 알고리즘을 사용한 시스템은, 위에서 설명한 Yesica의 사례처럼 다수가 보낸 메시지를 특정한 사람만 알아낼 수 있을 때 사용한다. 실제로 은행에서는 다수의 고객들이 보낸 암호화된 거래내역 같은 정보를 은행 자신만 알아낼 수 있도록 하기 위해 비대칭 키 중 하나인 RSA를 사용한다.

---

what is RSA?

RSA가 위의 비대칭키 알고리즘의 대표적인 예로써, 1977년 론 리베스트(Ron Rivest)와 아디 셰미르(Adi Shamir), 레오나드로 아델만(Leonard Adelman)등 3명의 수학자에 의해 개발된 암호화 알고리즘이다. (이들의 이름의 첫 글자를 따서 알고리즘의 이름을 RSA라 붙였다.) 페르마 소정리와 소인수 분해의 복잡성을 이용하여 공개키와 개인키를 효과적으로 계산할 수 있게 해주는 알고리즘 중 하나이다.

RSA에서 처음 예시에서 비밀번호라 부르던 키의 크기는 마음대로 지정할 수 있으나, 현재는 이진법으로 나타내었을 때 4096자리가 되는 수 즉 4096bit의 수를 키로 사용하는 RSA2048의 방식이 널리 사용되고 있다.

참고로 말하자면 이 수는 십진법으로 약 1233자리이며, 키의 길이가 길어질수록 보안 능력은 더욱 강화된다.

현재 RSA는 윈도우를 비롯한 수많은 프로그램에서 사용 중이며, 높은 위상을 가지는 암호화 알고리즘이다.

---

Calculation of RSA key

RSA의 두 키값을 계산하기 위해서는 두 소수가 필요하다. 요구되는 소수의 크기는 다를 수 있는데, 보통 2048bit 의 소수가 요구된다. 각 소수를 p, q라 정의한다면

<그림B1>과 같은 방법으로 계산이 가능하다.

ϕ(Pub)가 의미하는 바는 “Pub보다 작은 수중 서로소의 개수”이고, (p-1)(q-1)로 생각한다. 개인키를 계산하기 위한 마지막 식은 e*S를 n으로 나눈 나머지가 1이라는 뜻이다.

<그림 B2>는 p, q가 각 29, 11일 때의 연산이다.

이때, 이러한 과정 중에서 보아야 할 또다른 것은 공개할 정보와 공개하지 않을 정보의 구분이다. 그림에서 빨간색 화살표 표시가 된 공개키(Pub)와 e값만이 공개되어야 하며, 그 외의 값이 공개되어서는 아니 된다.

만약, 공개되면 안 되는 정보에 해당하는 p, q, n, 개인키(Pri)중 어느 하나라도 노출될 경우, 노출된 정보를 기반으로 개인키를 알아내거나 계산해낼 수 있으며, 이는 다시 말해 RSA보안에 허점이 생기게 되는 것이다.

---

Why RSA can believe in?

RSA 키를 신뢰할 수 있는 이유는 소인수 분해의 복잡성 때문이다. 2개의 큰 소수를 곱하는 것은 매우 쉽다. 그러나, 반대로 두 소수의 곱을 소인수 분해하기 위해서는, 효율적인 알고리즘을 사용한다 하여도 매우 많은 시간을 요구한다.

 

예를 들어 두 소수 26,731과 89,477을 곱한 값은 2,391,809,687이다. 이 연산은 인간도 수행할 수 있는 연산이며 계산기로는 더욱 간단하게 할 수 있다. 하지만 2,391,809,686을 소인수 분해 하기 위해서는 꽤나 많은 시간이 필요할 것이다. 17자리 소수에서도 이렇게 복잡해지는데, 2048bit로 이루어진 두 소수의 곱을 소인수분해 하는 것은 불가능에 가까울 것이다. (슈퍼 컴퓨터가 RSA2048공개키를 이용해 두 소수를 계산하는 데는 수 천 년이 걸린다!)
이러한 이유로, 공개키를 이용해서 그 공개키를 이루고 있는 두 소수 p, q를 얻는 것은 불가능에 가깝다.

 

그런데, 위의 과정을 보면 이해할 수 있듯이, 공개키로부터 개인키를 얻기 위해서는 개인키를 이루고 있는 두 소수 p와 q의 연산이 필연적이다. 이에 따라 공개키로 개인키를 얻는 것이 매우 매우 어렵다(사실상 불가능)고 말할 수 있겠다.

---

Decoding / Encoding

이제 키를 계산하는 하였으니 암호화와 복호화를 할 필요가 있다. 이를 하기 위해서는 간단한 지수식을 사용한다. 

아래 식은 어떠한 숫자 A를 암호화 / 복호화 하기 위한 식이다. 윗글에서 사용한 이름들(Pub, n, e, Pri)을 그대로 사용한다.

 

Decode = M ≡ A^e (mod Pub)

Encod = A ≡ M^Pri (mod Pub)

 

이 식을 기반으로 이전에 계산한 값들을 이용해 71을 암호화 / 복호화 해보자면

 

M = 71^17 ≡ 80(mod 319)

A = 80^33 ≡ 71(mod 319)

 

으로, 실제 사용에도 문제가 없음을 확인할 수 있다. 이것의 정상작동을 증명하는 데는 수학적인 부분이 사용된다.

페르마 소정리를 생각해보자.

 

a^(p-1)≡1 (mod p)

(p is prime, not dividing a)

 

그러면 다음이 성립한다는 것을 알 수 있을 것이다.

 

A^(p-1)(q-1)=A^u(q-1)=A^(p-1)v≡1(mod pq)

 

그리고 암호화 문을 복호화 한 수는 다음과 같을 것이다.

 

M^Pri=(A^e)^Pri=A^(e×Pri)

 

그리고 Pri의 정의에 따라 e * Pri는 n으로 나누었을 때의 나머지가 1, 즉 아래가 성립한다.

 

e×Pri=αn+1=α(p-1)(q-1)+1 (α is particulat number)

 

위 두 문장을 연립하면

 

M^Pri=A^(e×Pri)=A^(α(p-1)(q-1)+1)=(A^(p-1)(q-1))α×A≡1α×A=A (mod pq=Pub)

 

가 성립한다는 사실을 알 수 있고, 이를 통해서 우리는 RSA의 암호화/복호화를 제곱의 방법으로 정상적이게 할 수 있다는 것을 깨닫게 되었다.

---

code RSA key calculation program

structure of code

RSA 키를 만드는 과정을 크게 나누어보면 아래와 같다.

 

1. 소수 p와 소수 q가 주어졌을 때 Pub=p*q를 계산하는 함수

2. 소수 p와 소수 q가 주어졌을 때 n=(p-1)*(q-1)=Pub-p-q+1을 계산하는 함수

2.5. e의 값 설정

3. e와 n그리고 Pub가 주어졌을 때, e*S=1(mod n)을 만족하는 Pri값을 찾아내는 함수

//process1 process2

우선적으로 1번과 2번의 과정은 그다지 어렵지 않은 과정이다.

단순하게 곱셈을 수행하면 되고, 계산한 값에서 뺄셈과 덧셈을 수행하면 되며, 이를 구현하는 것 또한 어렵지 않다.

 

//process2.5

e의 값은 관용적으로 2^16 + 1을 사용한다.

 

//process3

연산을 효율적으로 진행하기 위해서, 우선적으로 개인키 계산을 위한 식을 변형 할 필요가 있다. 식을 변형하면 아래와 같다.

 

e×S≡1mod n   ↔   eS+nk=1 (k는 임의의 정수)

 

변형된 식에서 S해를 구하기 위해 코드는 확장유클리드호제법(Extended Euclidian algorithm)을 사용할 필요가 있다. 사용하는 확장유클리드알고리즘의 기원인 유클리드호제법은, 두 양의 정수가 주어졌을 때, 두 수의 최대공약수를 구하는 알고리즘이라 할 수 있다. 호제법의 구현은 아래와 같이 재귀적으로 구현된다. (x>y라고 하자.)

 

GCD(x, y)= GCD(y, x mod y) (y≠0)

                   x(y=0)

 

GCD(423, 153) = GCD(153, 117) = GCD(117, 36) = GCD(36, 9) = GCD(9, 0) = 9

 

이것을 응용하여 만들어진 확장유클리드알고리즘은, 더 구체적인 값을 도출하게 만든다.

 

ax + by = GCD(a, b)를 만족하는 x, y의 해

 

여기서 a와 b에 각각 n과 e를 대입하면 n과 e가 서로 서로소라 정의되었으므로, GCD(a, b)는 1이고

해의 값은 nx+ey=1을 만족하는 (x, y)가 된다. 이 식은 처음 유도한 개인키의 계산 식과 같기에, 확장 유클리드 호제법에 (a, b) = (n, e)이라 가정하고 계산한 (x, y)값 중 y값이 개인키 값이 된다. 따라서, 유클리드호제법의 해를 구함으로써 연산을 구현할 수 있다.

 

아래 표는 (a, b)=(37, 8)일 때 (x, y)의 연산 방법을 나타낸 표이다. 모든 나눗셈은 나머지를 버리고 몫만을 따진다

단계	α	β	γ	.
초기값	1	0	37	(37 * 1) + (8 * 0) = 37
초기값	0	1	8	(37 * 0) + (8 * 1) = 8
1	1-(0*(37/8)) = 1	0-(1*37/8)) = -4	37 % 8 = 5	(37 * 1) + (8 * -4) = 5
2	0-(1*(8/5)) = -1	1-(-4*(8/5)) = 5	8 % 5 = 3	(37 * -1) + (8 * 5) = 3
3	1-(-1*(5/3)) = 2	-4-(5*(5/3)) = -9	5 % 3 = 2	(37 * 2) + (8 * -9) 2
4	-1-(2*(3/2)) = -3	5-(-9*(3/2)) = 14	3 % 2 = 1	(37 * -3) + (8 * 14) = 1
5	2-(-3*(2/1)) = 8	-9-(14*(2/1)) = -37	2 % 1 = 0	(37 * 8) + (8 * -37) = 0
...	...	...	...	...
n	α_n-2 -(α_n-1 *(γ_n-2/γ_n-1))	β(n-2) -(β_n-1 *(γ_n-2/γ_n-1))	γ_n-2 % γ_n-1	(α * a_n)+(b * β_n) = γ_n

만약 개인키로 사용되는 값 y가 음수라면, n을 더하여 수를 양수로 만든다. 추가적으로, 만약 γ가 0으로 판명되었을 때, 그 전 단계(예시에서 4단계)에서의 γ가 2^16+1이라면, n이 e의 배수이기에 식을 만족하는 적절한 값이 없다는 뜻이므로 키 연산을 종료한다.

---

sample

해당 과정을 참고하여 간단하게 구현한 RSA키 연산 프로그램은 아래와 같다.
(단, int범위에서는 e값을 2^16+1로 사용할 경우 e가 n보다 작아야 한다는 조건을 만족시키기가 어렵기 때문에, 알고리즘을 조금 변형하였다.)

// 수정필 수정필 수정필

#include <stdio.h>
#include <stdlib.h>

void RSAcndtGetRandom(int* e, int (*Rd)(void)) {
	*e = (*Rd)();
	return;
}

int RSAcndtGCD(int a, int b) {
	return b ? RSAcndtGCD(b, a % b) : a;
}

int RSAcndtEEDA(const int* a, const int* b) {
	int A1 = 1, A2 = 0;
	int B1 = 0, B2 = 1;
	int C1 = *a, C2 = *b;
	int semi_A, semi_B;
	int CDiv, CMod;
	
	for (;;) {
		CDiv = C1 / C2;
		CMod = C1 % C2;
		
		if (!CMod) { return A2; }

		semi_A = A1 - (A2 * CDiv);
		semi_B = B1 - (B2 * CDiv);

		A1 = A2; A2 = semi_A;
		B1 = B2; B2 = semi_B;
		C1 = C2; C2 = CMod;
	}
}

void RSAkeyCalcProc(const int* p, const int* q, int* Pub, int* Pri, int* e) {
	int n;
	//process1
	(*Pub) = (*p) * (*q);
	//process2
	n = (*Pub) - (*p) - (*q) + 1;
	//process3
	do {
		RSAcndtGetRandom(e, rand);
	} while (RSAcndtGCD(n, *e) != 1);
	//process4
	*Pri = RSAcndtEEDA(&n, e);
	return;
}
int main(void) {
	int p = 29, q = 11; // n bit
	int Pub, Pri; // 2n bit
	int e; // n bit
	RSAkeyCalcProc(&p, &q, &Pub, &Pri, &e);
	return 0;
}

---

soruce code

모든 코드의 저작권은 블로그주에게 있으며, 이를 사용하고자 할 경우 저작자의 허가를 맡아야 합니다.

저작자 메일: tomskang@naver.com 통보만 해도 좋으니 코드를 사용하실려면 꼭 메일을 보내주세요.

 

| 코드 보기

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define BNA3_ARR_SIZE	32
#define BNA3_DIG_SIZE	64

#define BNA3_14			62	// DIG_SIZE - 2

#define BNA3_20			2048 // ARR_SIZE * DIG_SIZE

#define DIG_SIZE		64		// the number of bit per array's one factor
#define H_DIG_SIZE		32		// half DIG_SIZE		(DIG_SIZE / 2)

#define N_ARR_SIZE		32		// normal array size
#define D_ARR_SIZE		64		// double-size array size	(N_ARR_SIZE * 2)
#define N_WHL_BITN		2048	// the number of whole bit in normal size	(N_ARR_SIZE * DIG_SIZE)
#define D_WHL_BITN		4096	// the number of whole bit in double size	(D_ARR_SIZE * DIG_SIZE)

#define UP_N_ARR_SIZE	33		// upper N_ARR_SIZE		(N_ARR_SIZE + 1)
#define UP_D_ARR_SIZE	65		// upper D_ARR_SIZE		(D_ARR_SIZE + 1)

#define UN_DIG_SIZE		63		// under DIG_SIZE		(DIG_SIZE - 1)
#define UN_N_ARR_SIZE	31		// under N_ARR_SIZE		(N_ARR_SIZE - 1)
#define UN_D_ARR_SIZE	63		// under D_ARR_SIZE		(D_ARR_SIZE - 1)

#define LG_DIG_SIZE		6		// log2 DIG_SIZE		(log2 DIG_SIZE)
#define MI_DIG_SIZE		0x3F	// DIG_SIZE - 1			(UN_DIG_SIZE)

#define FL_64BIT		0xFFFFFFFFFFFFFFFF	// full 64 bit
#define FL_32BIT		0xFFFFFFFF			// full 32 bit

typedef unsigned long long KMS10_dat;
typedef unsigned int KMS10_bitDat; // dit Datum, could store number 0 to 4096 (D_WHL_BITN)
typedef unsigned int KMS10_idxDat; // index Datum, could store numdert 0 to 64 (D_ARR_SIZE)
typedef unsigned int KMS10_logic; // logic Datum, could store 0, 1

/*
* input: DARR Pub, NARR p, NARR q
* process: Pub = p * q
*/
void OPERATOR1(KMS10_dat* Pub, const KMS10_dat* p, const KMS10_dat* q) {
	KMS10_dat* src;
	KMS10_bitDat dig, cur;
	KMS10_bitDat shA, shB;
	KMS10_idxDat idx;
	KMS10_dat sum;
	KMS10_logic sft;
	src = (KMS10_dat*)malloc(sizeof(KMS10_dat) * D_ARR_SIZE);
	memcpy(src, p, sizeof(KMS10_dat) * N_ARR_SIZE);
	memset(src + N_ARR_SIZE, 0, sizeof(KMS10_dat) * N_ARR_SIZE);
	memset(Pub, 0, sizeof(KMS10_dat) * D_ARR_SIZE);
	for (cur = dig = 0; cur < N_WHL_BITN; cur++) {
		if (q[cur >> LG_DIG_SIZE] >> (cur & MI_DIG_SIZE) & 1) {
			//src = Rshift(src, dig)
			shA = dig >> LG_DIG_SIZE; shB = dig & MI_DIG_SIZE;
			for (idx = UN_D_ARR_SIZE; idx > shA; idx--) {
				src[idx] = (src[idx - shA] << shB) | (src[idx - shA - 1] >> (DIG_SIZE - shB));
			}
			src[shA] = src[0] << shB;
			if (shA) { memset(src, 0, sizeof(KMS10_dat) * shA); }
			//Pub = add(Pub, src);
			sft = 0;
			for (idx = 0; idx < N_ARR_SIZE; idx++) {
				sum = Pub[idx] + src[idx] + sft;
				if (sum != Pub[idx]) { sft = (sum < Pub[idx]); }
				Pub[idx] = sum;
			}
			dig = 1;
		}
		else { dig++; }
	}
	return;
}

---

code RSA encoding/decoding program

square and multiple algorithm

RSA 암호화 / 복호화를 위한 제곱 연산자는 기본적인 구현은 어렵지 않으나, 최적화를 위한 수학적인 원리가 몇 가지 있다.

암호화 / 복호화에 사용되는 식 a^b(mod c)을 계산하는 방법 중 가장 먼저 떠오르는 것은 a를 b번 곱하고 c를 나누는(것의 나머지를 구하는)것 이라 할 수 있다. 그러나 이런 방법은 매우 비효율적이다. 먼저 b가 너무 크다. B가 4096bit의 수이기 때문에, 위와 같은 방식을 사용하면 곱셈을 최소 5.221e+1232번 해야 하며, 암호화를 하는데 몇 일이 소요되는 불상사가 생길 수 있다.

 

이러한 문제를 해결할 수 있는 방법으로 square and multiple 이라 이름 붙여진 알고리즘이 있다. 이 이 알고리즘을 통해 ab

을 계산하는 것을 식으로 표현해보고자 한다면 다음과 같다.

 

a^b = pi (k=0) ([log2b]-1]) {a^(2^k) * (k th bit number of b)}

 

매우 복잡하여, 이해하기도 어려운 수식이다. 이해를 쉽게 하기 위해, 마찬가지로 표로 그 예시를 보이겠다. 아래 표는 3^26(mod37)을 계산하는 과정이다. 26은 이진법으로 11010이며, 5bit수이다.

k	semi (임의의 변수)	bit	Value
-	3	-
0	3	0	1 = 1
1	9 % 37 = 9	1	1 * 9 = 9 (mod37)
2	81 % 37 = 7	0	9 = 9
3	49 % 37 = 12	1	9 * 12 = 34 (mod 37)
4	144 % 37 = 33	1	34 * 33 = 12 (mod 37)
...	...	...	...
n	Semi = Semi^2 % 37	bit	bit=1: Value = Value * semi % c
			bit=0: Value = Value

위에서 보았듯이, 곱셈 횟수가 줄어든 것을 확인할 수 있다. 수식적으로 연산 수가 n > log2n으로 변화한 것이기에, 수가 커질수록 그 효과는 상상도 할 수 없을 만큼 극대화된다.