반응형



이 게시물의 내용은

https://www.youtube.com/watch?v=kGUlfVpIfaQ

위의 링크를 기반으로 제작하였습니다.


문제가 된다면 삭제조치 하겠습니다.




1. RSA 암호 알고리즘이란?


Rivet, Shamir, Adelman 세사람의 첫이름을 따 RSA라고 만든 암호 알고리즘을 보고자 한다.



RSA 암호 체계는 미국 MIT에서 개발한 공개키 암호 시스템이다.


암호 알고리즘의 핵심큰 정수의 소인수 분해가 어렵다는 점을 이용하여 암호화를 시킨다.


이러한 RSA 암호 알고리즘은 전자상거래에서 가장 흔히 쓰고있는 공개키 알고리즘이다.




2. RSA 암호 알고리즘 방식


1. A가 B에게 정보를 안전하게 보내고 싶어한다. 이때 RSA 알고리즘을 이용하고자 한다.

2. B가 공개키와 개인키를 만들어 A에게 공개키를 보낸다. (개인키는 B만 가지고 있다.)

3. A가 B로부터 받은 공개키를 이용하여 보낼 정보를 암호화한다.

4. A가 암호화된 정보를 B에게 보낸다.

5. B가 암호화된 정보를 받고 개인키를 이용하여 암호를 해독한다. 





3. RSA 암호 알고리즘 원리


STEP 1. 개인키와 공개키 만들기

RSA 암호 알고리즘 첫 단계는 공개키와 개인키를 만드는 것이다.

공개키는 n,e라는 두 정수로 이루어져있고 개인키는 n,d라는 두 정수로 이루어져있다.


n 구하기

임의의 두 소수 p와 q를 정하고 n = p * q를 해주면 n을 구할 수 있다.


e 구하기

Φ(n) = (p - 1) * (q - 1)식을 이용하여 Φ(n)을 구한다.


e는 1 < e < Φ(n)로써 1과 Φ(n) 사이에 있고 Φ(n)와 서로소인 e를 정해주면 된다.


이러한 e는 공개키에 이용이 될 것이다.


** 서로소란 1 이외에 공약수를 가지지 않는 수를 의미한다.


d 구하기

(e * d) mod Φ(n) = 1


즉, e*d를 Φ(n)으로 나누었을 때 나머지가 1인 d를 구하면 된다. 이때 d는 개인키에 사용될 숫자이다. 


이제 공개키에 이용될 (n, e)와 개인키에 이용될 (n, d)를 모두 구하였다. 즉, 개인키와 공개키가 생성되었다.



STEP 2. 암호화하기

STEP 1에서 구한 공개키를 이용해서 정보를 암호화 한다.

원래 정보를 M이라 하고 암호화된 정보를 C라 하자.

위의 식을 이용하여 M을 C로 암호화 하면 된다.


이때 암호화를 할 때 e와 n의 값을 알아야 하므로 공개키(n, e)가 있어야 암호화 할 수 있다는 것은 자명하다.



STEP 3. 복호화하기(해독하기)

이제 암호화되어 온 정보 C를 복호화(해독)할 순서이다.

 


페르마의 소정리에 의해 1번식이 성립하면 2번식도 성립하게 된다.



암호화 할때는 1번식을 사용했으므로 복호화 할때는 위의 식 즉, 2번식을 이용하여 복호화를 한다.


이때 암호화된 정보 C를 M으로 복호화(해독)할 때는 n과 d값을 알아야 한다.


이때 이 값을 아는 사람은 개인키(n, d)를 가진 사람 B 뿐이다. 


이전에 말한 내용 중 

' 1. A가 B에게 정보를 안전하게 보내고 싶어한다. 이때 RSA 알고리즘을 이용하고자 한다. ' 

' 2. B가 공개키와 개인키를 만들어 A에게 공개키를 보낸다. (개인키는 B만 가지고 있다.) '

내용을 참고해보자.



4. RSA 알고리즘 구현


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
#include <iostream>
#include <cstdio>
#include <time.h>
#include <stdlib.h>
#include <memory.h>
#include <string>
#include <cmath>
 
#define MAX_N 10
 
using namespace std;
 
void eratosthenes(bool *isPrime)
{
    memset(isPrime, 1sizeof(isPrime));
 
    isPrime[0= isPrime[1= false;
 
    int sqrtn = int(sqrt(MAX_N));
 
    for (int i = 2; i <= sqrtn; i++)
        if (isPrime[i])
            for (int j = i*i; j <= MAX_N; j += i)
                isPrime[j] = false;
}
 
int main()
{
    cout << "A라는 사람이 B라는 사람에게 정보를 암호화해서 보내고 싶다." << endl;
    cout << "이때 RSA 암호화 알고리즘을 이용하고자 한다." << endl;
 
    cout << "B는 A에게 정보를 받기 위해 공개키(n,e), 개인키(n,d)를 형성한다." << endl;
 
    bool isPrime[MAX_N + 1];
    eratosthenes(isPrime); // 소수 생성
    
srand((unsigned)time(NULL)); // 랜덤 테이블 형성
    // n, p, q값 구하기
    int n = 0;
    int p = 0, q = 0;
 
    cout << endl;
    cout << "n, p, q 값 구하는 중" << endl;
    while (!n)
    {
        //
 
        // p를 만들고
        while (!p)
        {
            int randVal = (rand() % MAX_N) + 1;
            if (isPrime[randVal])
                p = randVal;
        }
 
        // q를 만들고
        while (!&& q != p)
        {
            int randVal = (rand() % MAX_N) + 1;
            if (isPrime[randVal])
                q = randVal;
        }
 
        // pi가 2가 되면 안된다.
        if ((p - 1* (q - 1== 2)
        {
            p = 0, q = 0;
            continue;
        }
        // n을 만들어준다.
        n = p * q;
    }
 
 
    // e 구하기
    // Φ(n) = (p - 1) * (q - 1)
    // 1 < e < Φ(n), e와 Φ(n)은 서로소
    int pi = (p - 1* (q - 1);
    int e = 0;
 
    cout << "n :: " << n << endl;
    cout << "p :: " << p << endl;
    cout << "q :: " << q << endl;
    cout << "pi :: " << pi << endl;
 
    cout << "e 값 구하는 중" << endl;
 
    while (!e)
    {
        //srand((unsigned)time(NULL)); // 랜덤 테이블 형성
 
        int randVal = rand() % pi;
 
        // 1 < e < Φ(n) 
        if (< randVal && randVal < pi)
        {
            e = randVal;
 
            // e와 Φ(n)이 서로소인지 검사
            int cnt = 0;
            for (int i = 1; i < e; i++)
                if (e % i == && pi % i == 0)
                    cnt++;
 
            // 서로소가 아니라면(1 이외의 공약수를 가진다면) e = 0 초기화
            if (cnt >= 2)
                e = 0;
        }
    }
 
    cout << "e :: " << e << endl;
 
    // d 구하기
    // (e * d) mod Φ(n) = 1
    int d = 0;
 
    cout << "d 값 구하는 중" << endl;
 
    while (!d)
    {
 
        int randVal = rand() % MAX_N + 1;
    //    cout << "randVal :: " << randVal << endl;
        if ((e * randVal) % pi == 1)
            d = randVal;
    }
 
    cout << "<< 최종 >> " << endl;
    cout << "n :: " << n << endl;
    cout << "p :: " << p << endl;
    cout << "q :: " << q << endl;
    cout << "pi :: " << pi << endl;
    cout << "e :: " << e << endl;
    cout << "d :: " << d << endl;
 
    cout << endl;
    cout << "공개키(n, e) :: " << "(" << n << "," << e << ")" << endl;
    cout << "개인키(n, d) :: " << "(" << n << "," << d << ")" << endl;
    cout << endl;
 
    cout << "공개키를 A에게 주고 B는 개인키만 가지고 있는다." << endl;
 
    long long M = 347 % n;
    cout << "이제 A가 '" << M << "'이라는 정보를 암호화해서 보내고자 한다." << endl;
    
    cout << "A가 보낼 정보를 C로 암호화 한다." << endl;
 
    long long C = ((long long)pow(M, e) % n);
    
    cout << "암호화 된 값 :: " << C << endl;
    cout << "암호화된 C정보를 받은 B는 이제 해독하고자 한다." << endl;
 
    M = ((long long)pow(C, d) % n);
    
    cout << "B가 받은 해독 결과 :: " << M << endl;
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus


모든 것을 rand로 나타내고 있기에 e, d값이 빨리 도출되지 못 할 수도 있다.

빠른 결과를 보고 싶다면 e, d를 rand로 설정하지말고 for문으로 설정하면 결과를 빨리 얻을 수 있다.








5. RSA 암호 알고리즘 안정성


공개키(n,e)를 가지고 있는 사람 C가 암호화된 정보를 중간에 빼돌렸다 생각해보자.


c는 공개키를 가지고 있으므로 공개키(n,e) 값을 알고 있다.


n = p * q이고 Φ(n) = (p - 1) * (q - 1)이기에 소인수분해를 통해 p, q를 구할 수 있고 Φ(n)를 구할 수 있다.


또한 (e * d) mod Φ(n) = 1이 되는 식에서 e와 Φ(n)을 알고있으니 d도 구할 수 있게 된다.


결국 n,e,d를 모두 알게되니 복호화에 성공할 수 있다.


결국 이 암호 알고리즘은 풀린다는 의미가 된다.


우선 결론부터 말하자면 RSA 알고리즘은 개인키를 알아낼 수 없는 안정성을 갖추고 있다.


1. 큰수 소인수분해의 어려움

2. 나머지 연산의 역연산이 어려움

이 두가지 때문이다.


하지만 위의 내용에서 모순을 찾아내보자.


n = p * q라 했는데 n이 작은 숫자일때는 p, q를 찾기가 쉬운데

n이 엄청 커지는 수라면 p와 q 소수를 찾아내기 어려워지게 되고


(e * d) mod Φ(n) = 1이 되는 식에서 e와 Φ(n)을 알고있으니 d도 구할 수 있게 된다.

에서 d를 구하기에도 나머지가 1인 수가 무수히 많기 때문에 개인키에 해당하는 d를 구하기가 어렵다.



하지만 컴퓨터의 속도가 훨씬 더 빨라지거나 

어떤 수든 소인수분해 하는 알고리즘이 나온다면 

RSA 암호 알고리즘도 막을 내릴 것이다.



반응형

'Applied > Hacking and Security' 카테고리의 다른 글

일방향 해시 함수  (0) 2018.03.24
DES 암호 알고리즘  (7) 2018.03.20
2의 보수, 보수(Complements)를 이용한 값 구하기  (6) 2016.10.20
진법 변환  (2) 2016.10.20
콘솔창에서의 인터넷 창 테러  (0) 2016.08.14