×
Crocus
공부한 내용을 정리하는 블로그로 시작한
Crocus는 2014년 1월 14일 부터 시작하여
현재 월 6만명, 총 1,683,642명의 방문자 수를 기록하고 있습니다.
Donation
이제 많은 사용자들이 이용하는 만큼
더 다양한 서비스 개발/제공을 위해 후원금을 모금하고자 합니다.
후원을 해주시는 분들은 Donators 명단에 성명, 후원금을 기입해드리며
Crocus 블로그가 아닌 다른 곳에 정리해둔 저만의 내용을 공유해 드리고자 합니다.
Account
예금주 : 고관우
신한은행 : 110-334-866541
카카오뱅크 : 3333-01-7888060

👉 후원 페이지 바로가기 Donators
익명 : 5000원(Crocus응원합니다.)
busyhuman: 5000원(유용한 지식 감사합니다.)
익명 : 5000원(알고리즘 학습러)
728x90
반응형



이 게시물의 내용은

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 암호 알고리즘  (5) 2018.03.20
RSA 암호 알고리즘  (9) 2018.03.14
2의 보수, 보수(Complements)를 이용한 값 구하기  (6) 2016.10.20
진법 변환  (2) 2016.10.20
콘솔창에서의 인터넷 창 테러  (0) 2016.08.14
  1. 아큐 2018.06.06 16:35

    예제에 틀린 부분이 너무 많은데 ...

  2. 물짝 2020.05.22 02:01

    n, p, q 값 구하는 중
    n :: 9
    p :: 3
    q :: 3
    pi :: 4
    e 값 구하는 중
    e :: 2
    d 값 구하는 중

    다음 예시에서 D값 구하는 루프가 무한 루프이네요

    • 가누 2020.05.24 12:37 신고

      p q값이 같으면안되기에 예시는 모순입니다.

  3. 2020.05.29 00:30

    비밀댓글입니다

  4. 원두먹자 2020.05.29 00:32

    혹시 n값 , p값,q값을 제가 집어넣고 d값을 구하려고해서


    bool isPrime[MAX_N + 1];
    eratosthenes(isPrime); // 소수 생성

    srand((unsigned)time(NULL)); // 랜덤 테이블 형성
    // n, p, q값 구하기
    int n = 77;
    int p = 11, q = 7;

    이렇게 고쳤는데 d값 구하는곳에서 멈추는데 잘못된 이유가 있나요?

    • 가누 2020.06.20 01:13 신고

      답변이 늦었네요
      아래내용처럼 교육을 위해 간단히 코딩하고자해서 생긴 오류같습니다.
      (RSA 알고리즘 원리는맞지만 실제로 이렇게 쉽게 만들수는 없을겁니다.)
      해당내용들에 대해 고칠수있는방법을 제시해주시면 반영하겠습니다. 감사합니다.

  5. MangBaam 2020.06.20 01:04 신고

    게시글 잘 보고 배웠습니다~
    p와 q가 작으면 확률적으로 e와 d가 같은 경우가 꽤 나오더군요.
    게시글의 결과도 e와 d가 같은 수가 나왔는데 저도 같은 문제로 e와 d가 같은 수가 나왔을 때 키를 다시 생성 하는 로직도 짜보고 했는데 결국 N이 작으면 그런 현상이 꽤 자주 발생해서 p와 q의 크기를 크게 잡았더니 그런 문제 발생 빈도가 확연히 줄었습니다. ㅎㅎ
    그리고 p와 q의 크기가 작을 때 또 하나의 문제가 입력한 M(평문)의 크기가 N보다 작아야 하는데 N의 크기가 작다보면 입력할 수 있는 평문의 크기에 영향을 많이 미칠 수밖에 없더라구요.
    물론 실제 구현에서는 M을 고정블록 크기로 쪼개서 블록단위로 암호화하지만..
    RSA에 대해서 공부하고 구현해보면서 깨달은 점들에 대해서 끄적여봤습니다. ㅎ
    좋은 글 감사합니다.

    • 가누 2020.06.20 01:13 신고

      좋은 답변감사합니다.
      코드개선가능한 방법이있다면 말씀해주세요. 반영하겠습니다!