[node.js] crypto RSA 공개키 알고리즘 구현 예제

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 알고리즘 구현

Oline RSA Key Generator 사이트에서 RSA 키를 자동으로 생성해준다 해당 키 값을 .env 파일에 넣어서 구현하겠다.

여기서 주의할 점은 위 사이트에서 만든 KEY는 개행이 들어가있기 때문에 개행마다 '\n'을 붙여줘야한다.

RSA_PRIVATE_KEY=-----BEGIN RSA PRIVATE KEY-----\nMIICXAIBAAKBgQC41wsMRbC4M4zkWYPI85WwYttEgbLQmIiHD4g6Kjz43h0+3rgt\n8m6IJtolraHpIus+izEx03kpYgJiTLAdruQBDqXTgTyIafZpLaZxH8kYVTomfjJL\nzqTbxuHz1uLqqOaeLzvKiKbCbbCaKWolgCQOCUu+rj/qdftchEVq/LcCcwIDAQAB\nAoGAbIo6fpZd04zR6zV1YYdIGy+xumS+8Cbh5Q2F3UH4U9t6KPT4CmMV7PWDnCR9\nsz1CDpQF61BXEanv5HFL6eJNGCH20z4SctlnMZCw0CJvel4tue4mVmAORctXfcy8\nA9gXpP2D3+tWInSRjZqDZt95ca6N5htlf99a7dcebh7xQkECQQDl/KChwiHw4nBk\nGuDlRp1G7TdP5chBDccdS0655957ZJCROcrjglfJobaGNFsjhoEyWPMl+Ywbt6IZ\n1FV7Z0FbAkEAzb8rVjhuiUurkf9boO2gq1EBMhNULJJHZOB50dpXiD8LvzWcBzvm\nYPppsMYUNS35ItaqXpvQLYswyIA3Seq2yQJAPen7qHBlyL58+UYPI0oWTyDPUjAO\n8AxwfR9n6z5Ts65ICQCg8QyG654gUBLKMk8ketRdaOy8Xj3aYs+5z4XlnwJABlxE\nkLPJ5wCp2yeTw5PVBbbJXKzwSzhycJHn8i7XyeR5Dn4vxqF5a8ISBl75PPOg4gzU\n03vpoZ7N8UTVcLmK0QJBAN4B3D/iBTce6Q5q3Apza8jzMS5ZZjh4Y8/A9K6IiQ54\nkul2tfIVywHVFoxJzGm4JMkHSf7yoVjsjEDpQvKMnIk=\n-----END RSA PRIVATE KEY-----
RSA_PUBLIC_KEY=-----BEGIN PUBLIC KEY-----\nMIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQC41wsMRbC4M4zkWYPI85WwYttE\ngbLQmIiHD4g6Kjz43h0+3rgt8m6IJtolraHpIus+izEx03kpYgJiTLAdruQBDqXT\ngTyIafZpLaZxH8kYVTomfjJLzqTbxuHz1uLqqOaeLzvKiKbCbbCaKWolgCQOCUu+\nrj/qdftchEVq/LcCcwIDAQAB\n-----END PUBLIC KEY-----

.env

 

const crypto = require("crypto");
require('dotenv').config();
const privateKey = process.env.RSA_PRIVATE_KEY.replace(/\\n/g, '\n');
const publicKey = process.env.RSA_PUBLIC_KEY.replace(/\\n/g, '\n');

encodeRSA = (text) => {
    const buffer = Buffer.from(text);
    const encrypted = crypto.publicEncrypt(publicKey, buffer);
    return encrypted.toString("hex");
}

decodeRSA = (text) => {
    const buffer = Buffer.from(text, "hex");
    const decrypted = crypto.privateDecrypt(privateKey, buffer);
    return decrypted.toString("utf8");
}


//암호화
const text = 'test123123'; //사용자의 비밀번호
const encrypted = encodeRSA(text); //public key를 사용해 암호화한 값을 서버로 전송한다
console.log(encrypted);

//서버로직
//복호화
const decrypted = decodeRSA(encrypted); //서버에서 값을 private key를 이용해 복호화한다.
console.log(decrypted)

 

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 암호 알고리즘도 막을 내릴 것이다.