RSA

RSA란?

현재 SSL/TLS에 가장 많이 사용되는 공개키 암호화 알고리즘

전세계 대부분의 인터넷 뱅킹에서 사용

대칭키가 아닌

공개키와 개인키가 한 쌍을 이룸

공개키로 암호화한 내용은 개인키로만 복호화가능 (일반적으로 민감만 정보 보호하려고 사용)

개인키로 암호화한 내용은 공개키로만 복호화가능 (공인인증서처럼 본인을 인증하는 용도로 사용)

 

공개키와 개인키를 만드는 과정

1. 두 소수 p와 q를 만든다

2. p-1, q-1과 각각 서로소인 정수 e를 준비한다.

3. ed를 (p-1)(q-1)로 나눴을때 나머지가 1인 d를 찾는다. ((p-1)(q-1)과 e가 서로소가 아니면 만족하는 d가 없음 그래서 2번과정 필요)

4. N = pd (N은 평문인 a보다 커야한다), N과 e는 공개키, d는 개인키

5. p, q, p-1, q-1는 보안상의 이유로 파기

서로소 : 1이외의 공통된 약수가 없는 수

이것 저것하다가 깨달았는데 2번에서 서로소인 정수 e를 찾기가 힘들면 p-1 그리고 q-1 모두보다 큰 소수를 쓰면 된다.

그러면 e는 소수이므로 애초에 약수가 1과 본인뿐이며

p-1과 q-1은 p와 q가 소수이므로

2를 제외하고는 홀수이다

즉, p-1과 q-1을 짝수로 볼 수 있으며 

e와 서로소이다

하지만 e가 p-1이나 q-1보다 작다면

예를들어 e = 3, p = 7일때

p-1 = 6 이므로 3을 공통된 약수로 가질 수 있다.

 

라이브러리 사용

내가 쓴 openssl로 키 발급하고 JSencrypt 라이브러리로 암호화, 복호화하기

JSencrypt 라이브러리를 암호화, 복호화

위 내용대로 라이브러리로 RSA를 할 수있다

그러나 라이브러리를 사용하지 않았는데

왜냐하면

1. 직접 알고리즘을 만들어보고 싶었다

2. 유저 각각에 키를 발급 할것인데 회원가입시 한번에 키 발급 -> 회원가입을 구현하고자 했다 라이브러리를 사용한다면 openssl로 키 발급을 먼저 받아야하기에 회원가입 버튼한번에 모든것이 되지 않음

 

RSA코드화 하기

우선 js로 RSA를 하는 블로그가 없다시피하고 구현하는 도중에 숫자가 안맞는거 같았다

예를 들어

console.log(193 ** 7);
// 9974730326005056

가 나오는데 1의 자리 숫자가 3이라면 몇 제곱을 하던 1의 자리 숫자가 1, 3, 7, 9중 하나가 나와야하는데

6이 나와서 정확한 수가 아님을 알았다

찾아보니 js는 큰 수의 표현에 치중했지 정확함에는 덜 치중했다고 한다

또한 Number 타입이 안정적으로 나타낼 수 있는 최대값은 2^53-1(9007199254740991)까지 이다

그래서 js로는 구현이 안되나 싶었는데 BigInt 타입은 더 큰 수의 표현이 가능하다

 

아까 알고리즘의 순서인

1. 두 소수 p와 q를 만든다

2. p-1, q-1과 각각 서로소인 정수 e를 준비한다.

3. ed를 (p-1)(q-1)로 나눴을때 나머지가 1인 d를 찾는다. ((p-1)(q-1)과 e가 서로소가 아니면 만족하는 d가 없음 그래서 2번과정 필요)

4. N = pd (N은 평문인 a보다 커야한다)

5. N과 e는 공개키, d는 개인키

6. p, q, p-1, q-1는 보안상의 이유로 파기

대로 코드를 쳐보자면

//1. 두 소수 p와 q를 만든다
let p = BigInt(decimalArr[index]);
decimalArr.splice(index, 1);
let q = BigInt(decimalArr[Math.floor(Math.random() * decimalArr.length)]);
//2. p-1, q-1과 각각 서로소인 정수 e를 준비한다.
const e = BigInt(eArr[Math.floor(Math.random() * eArr.length)]);
//3. ed를 (p-1)(q-1)로 나눴을때 나머지가 1인 d를 찾는다. ((p-1)(q-1)과 e가 서로소가 아니면 만족하는 d가 없음 그래서 2번과정 필요)
let d = 0;
while (!((e * d) % ((p - 1n) * (q - 1n)) === 1n)) {
  d++;
}
//4. N = pd (N은 평문인 a보다 커야한다), N과 e는 공개키, d는 개인키
const N = p * q;
//5. p, q, p-1, q-1는 보안상의 이유로 파기
p = null;
q = null;

// 암호화
let encrypted = a ** e % N;

// 복호화
let decrypted = encrypted ** d % N;

1. 소수 p와 q는 소수로 이루어진 배열에서 랜덤으로 가져왔다

  일반적으로는 큰 홀수를 구하고 소수판별 -> 소수 아니면 +2 -> 소수판별을 반복한다고하는데 소수판별이 어려운 부분이다

  루트 r의 방법으로 찾든 아르테미스의 체로 찾든 수가 커지면 연산이 막대해져서 찾기 불가능해지며 

  페르마 소정리의 대우명제인 '임의의 정수 a에 대해 a^(p-1)를 p로 나눈 나머지가 1이 아니면 p는 소수가 아니다'라는 방법을 쓸 수 있는    에 이 방법은 100% 확실한 방법이 아니기때문에 소수 배열을 만들어주고 거기서 랜덤으로 가져오는 방법을 취했다.

  p랑 q랑 같으면 에러가 나는것을 발견해서 p를 구하고 해당 값은 배열에서 삭제후 q를 구했다

2. e는 일반적으로 65537을 많이 쓴다고 하는데 p와 q에서 가져오는 소수 배열인 decimaArr보다 e에서 가져오는 소수 배열인 eArr의

  모든 값이 더 크다

3. 1부터 d를 구했다

 

문제점

속도가 몹시 느리다

시간이 걸리는곳이 3군데가 있다

d값 생성, 암호화, 복호화

p = 9883
q = 9887
e = 65573
password = 'a123456789' 일 때
d = 23377121이며

d값 생성 : 5.052s
암호화 : 3.564s
복호화 : 2m 6.035s가 걸린다 // 이건 내가 만든 pow() 함수 쓴것. for문 썼으면 얼마나 걸릴지 감도 안온다

암호화, 복호화 시간복잡도 개선

암호화는 a**e % N

복호화는 x**d % N이다

 

암호화 개선

우선 암호화는 클라이언트단에서 하는데

클라이언트단에서는 ** 연산자를 쓸 수 없다

왜냐하면 BigInt타입이 Math 메소드들을 쓸 수 없는데 

리액트가 자동으로 ** 연산자를 Math.pow()로 바꾸기 때문이다

그래서

거듭제곱 시간복잡도 줄이기

function pow(base, exponent) {
  let mul = 1n;
  while (exponent > 1n) {
    if (exponent % 2n === 0n) {
      base *= base;
      exponent /= 2n;
    } else {
      mul *= base;
      base *= base;
      exponent /= 2n;
    }
  }
  return base * mul;
}

를 이용해서

시간 : 3.564s -> 22.115ms
횟수 : 65573 -> 17 // retrun에서 곱하는거 포함

이렇게 줄였다

 

복호화 개선 (암호화 더욱 더 개선)

그러나 복호화인 서버단에서는 

내가 만든 pow함수를 쓰든 ** 연산자를 쓰든 2분대가 걸린다

 

(pow함수보다 **연산자가 더 빠르다)

**연산자에대한 고찰

 

pow함수 내부에서 몇번 반복되는지 확인하기위해 count를 세어봤는데 

겨우 25번 반복(return에서 곱하는거 포함)을 하는데 2분대가 걸린다

그 이유는 제곱이 되면서 숫자 자체가 워낙커지다보니까 계산자체가 오래걸리게 되는것이다.

이것은 

function power(base, exponent, mod) {
  base %= mod;
  let result = 1n;

  while (exponent > 0n) {
    // 1의 자리 비트가 1이면 트루 즉, 홀수면 트루
    if (exponent & 1n) {
      result = result * base;
      result = result % mod;
    }
    exponent >>= 1n; //나누기2 비트 오른쪽꺼 삭제
    base = base * base;
    base = base % mod;
  }

  return result;
}

이렇게 해결했는데

현재 구해야할값이 base^exponent 자체가 아닌 이 값에 % mod를 한 나머지값을 구해야한다

그래서 위에서 만든 pow함수랑 알고리즘은 같지만 중간 중간에 mod를 나눠주었다

그러면 base값이 커지지않고 짧은 반복 (25번)으로 계산하는것이 가능하다

어차피 나머지를 구하므로

ab mod n = ((a mod n)(b mod n)) mod n

가 성립하는것이다

이 방법을 쓰면

암호화 시
기존 for문 : 3.564s / 65573번
pow함수 : 22.115ms / 17번
power함수 : 0.097ms / 17번

복호화 시
pow함수 or ** 연산자 : 2m 6.035s / 23377121번
power함수 : 0.111ms / 25번

이렇게 획기적으로 시간을 줄일 수 있다

물론 O(logN)으로 줄어든거라 값이 커질수록 더 큰 효과를 기대할 수 있다

 

d값 생성 개선

현재 d값은 

while (!((e * d) % ((p - 1n) * (q - 1n)) === 1n)) {
  d++;
}

이런식으로 ed를 (p-1)(q-1)로 나눴을때의 나머지가 1이 되는 d값을 1부터 반복해서 찾고있다

즉, 시간복잡도가 O(N)이다

시간 : 5.025s
횟수 : 23377121

 

개선 방법 1안

let phiN = (p - 1n) * (q - 1n);

let count = 1n;
while (!((e * d) % phiN === 1n)) {
  count2++;
  const newPhiN = phiN * count + 1n;
  d = newPhiN / e;
  count++;
}

d를 1씩 증가시키지 않고  나누는 수인 phiN만큼씩 증가시킨다

시간 : 5.07ms
횟수 : 15691

 

개선 방법 2안

확장된 유클리드 호제법을 사용한다

내가 쓴 확장된 유클리드 호제법

확장된 유클리드 호제법 (gcd)

function EEA(a, b) {
  let [r1, r2, s1, s2, t1, t2, q, r, s, t] = [a, b, 1, 0, 0, 1, 0, 0, 0, 0];
  while (true) {
    q = parseInt(r1 / r2);
    r = r1 - q * r2;
    s = s1 - q * s2;
    t = t1 - q * t2;
    if (r === 0) {
      console.log(`최대공약수 : ${r2}, x : ${s2}, y : ${t2}`);
      break;
    }
    r1 = r2;
    r2 = r;
    s1 = s2;
    s2 = s;
    t1 = t2;
    t2 = t;
  }
}

시간 : 3.667ms
횟수 : 13

 

개선 결과

처음
for문으로 d값 생성 : 5.052s / 23277121번
for문으로 암호화 : 3.564s / 65573번
pow함수로 복호화 : 2m 6.035s / 23277121번

개선
확장된 유클리드 호제법으로 d값 생성 : 3.667ms / 13번
power함수로 암호화 : 0.097ms / 17번
power함수로 복호화 : 0.111ms / 25번

 

확장된 유클리드 호제법의 문제점 및 개선

문제점

확장된 유클리드 호제법이 빠르게 값을 도출할 수 있지만

최대공약수를 찾는 작업이다보니까

나머지가 1인 값을 찾을 확률이 50%이다

무슨 말인지 예를 들자면

432와 7 이 두수를

확장된 유클리드 호제법을 이용한다면

최대 공약수는 1

x = 3

y = -185가 나온다

x와 y를 각 숫자에 곱해보면

432 * 3 + 7 * (-185)

= 1296 - 1295 이므로 최대 공약수는 1이 나온다

하지만 우리는 ed % (p-1)(q-1)의 나머지가 1인 d값을 찾아야하는데

->7*d % 432의 나머지가 1

구한 x와 y를 각 숫자에 곱해보면

1295 % 1296이 되어서 나머지가 1295가 된다

 

우리가 원하는 나머지가 1인 값이 나오려면

x = -4

y = 247가 되어야한다

432 * (-4) + 7 * 247

= -1728 +1729 = 1 

최대공약수가 1이며

1729 % 1728의 나머지는 1이므로 

d = 247로 구할 수 있다

하지만 확장된 유클리드 호제법은 처음 구했던 

x = 3

y = -185만을 구해낼 수 있다

 

개선

우리가 원하는 나머지가 1인 값이 나올 확률이 50%로 낮지 않은 확률이므로

while문을 돌려서 원치 않는 값이 나온다면 p, q, e의 값을 다시 생성해서 d를 구하는 방법으로 구현

어차피 d를 구하는 시간을 압도적으로 줄였기에 앞에 상수가 붙는다고 해도 의미가 없으며

확률이 50%라 상수가 붙어도 기대값이 2임

 

RSA 활용

리펙토링 및 개선 - 4 / RSA 적용