[알고리즘] RSA 암복호화 알고리즘 C로 구현하기?

** 아래 코드는 검증되지 않았음(개인 학습용), 문제점 발견 시 댓글로 적어주시면 감사하겠습니다.

1. 이론 찾아보기

• 이론과 원리에 대해서 설명
  https://kevin0960.tistory.com/entry/RSA-%EC%95%94%ED%98%B8%EC%99%80-%EA%B7%B8-%ED%95%B4%EB%8F%85

RSA 암호와 그 원리

 

• 구글링 중 찾은 사이트. RSA뿐만 아니라 ECC, 디피헬만 등 다양한 알고리즘들이 설명되어 있다. (C로 구현된 예제가 있음)
  https://www.crocus.co.kr/1203

RSA 암호 알고리즘

• 나무위키, 이론 이해를 위해 참고 (설명 좀 더 디테일)
  https://namu.wiki/w/RSA%20%EC%95%94%ED%98%B8%ED%99%94

 

• 빠른 모듈로 거듭 제곱법
  https://ko.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/fast-modular-exponentiation

빠른 모듈로 거듭제곱법 (개념 이해하기) | 암호학이란? | Khan Academy

 

---

2. 코드

#include "stdafx.h"
#include <ctype.h>
#include <math.h>

int gcd(int a, int b);
int RSA(int n, int m, int d); 

int main(){
    // 키 생성
    //int p = 13, q = 37;
    //int p = 11, q = 13;
    int p = 17, q = 13;

    int n, e, d, f;

    n = p * q;
    f = (p-1) * (q-1);

    // e 결정
    for (int i = 2; i < f; i++) {
        // 서로소 판단
        if (gcd(p - 1, i) == 1 && gcd(q - 1, i) == 1) {
            e = i;
            break;
        } 
    }

    //d 결정
    for (int i = 1; i < n; i++) {
        if ((1 + f * i) % e == 0) {
            d = (1 + f * i) / e; 
            break;
        }
    }

    // 소수에 따라 자동 계산된 변수 값
    printf("p\tq\tn\te\td\tf\n");
    printf("%d\t%d\t%d\t%d\t%d\t%d\n\n", p, q, n, e, d, f);

    // 암호화
    int msg = 'b';
    printf("msg : %c\n", msg);

    int c = RSA(n, msg, e);
    printf("c : %c\n", c);

    // 복호화
    int msg2 = RSA(n, c, d);
    printf("msg : %c\n", msg2);

    return 0;
}

// 암복호화를 위한 모듈로 연산을 수행 (n, d는 공개키/ 개인키, m은 메시지)
int RSA(int n, int m, int d) {
    int bin1[10] = { 0, };
    int tmp, j = 1;
    unsigned long long x_tmp = 1; 
    int x[10]; // m^2^0~9 mod n

    // 거듭 제곱법 구현을 위한 값 미리 저장
    x[0] = (unsigned long long)pow(m, 1) % n;
    for (int i = 1; i < 10; i++) {
        x[i] = (x[i - 1] * x[i - 1]) % n;
    }

    // 지수를 이진수로 변환 (구현 편의성을 위해 그냥 역으로 넣음) 
    for (int i = 0; d > 0; i++) {
        tmp = d % 2;
        d /= 2;
        bin1[i] = tmp;
    }

    // 이진수가 1일 떄만 미리 계산된 값 곱셈
    for (int i = 0; i < 10; i++) {
        if (bin1[i] == 1) {
            x_tmp *= x[i];
        }
    }

    return x_tmp % n; // 곱셈 합을 모듈로해서 반환
}

// 최대 공약수
int gcd(int a, int b) {
    int tmp, n;

    if (a<b) {
        tmp = a;
        a = b;
        b = tmp;
    }

    while (b != 0) {
        n = a % b;
        a = b;
        b = n;
    }

    return a;
}

---

3. 결과

---

4. 참고 사항

 - 메르센 소수 같은 빅넘버를 처리하기엔 부적합함 (이 경우  OpenSSL 활용)

 - 거듭 제곱법 구현 함수 내 배열을 10으로 고정해두었으나 배열 크기 조정으로 어느정도 큰 소수

   (x_tmp 최대값, unsigned long long) 까지는 연산이 가능함.

- 문자를 하나씩 암호화 하면 같은 문자는 같은 값으로? 암호화됨. (블록 단위 암호화 필요)

  ex) testtest -> abcaabca 

- 자료형 크기 고려했을 때 문자를 대충 4바이트 단위까지 합쳐서 연산가능할 듯

  ex) asdf  -> 16진수변환 한번에 연산 등등

 

 

 

---

내용 수정

2024-01-21(일)

- 기존 코드에서 잘못된 부분을 확인하여 수정이 필요한 부분을 적어두었음

- e를 결정하는 부분에서 e와 f가 서로소인 부분이 확인 되어야 하기 때문에 기존 코드의 gcd(p - 1, i) == 1 && gcd(q - 1, i) == 1 부분이 제거 되고 아래처럼 수정되어야 함

f = (p-1) * (q-1);

// e 결정
for (int i = 2; i < f; i++) {
    if (gcd(i, f) == 1) {
        e = i;
        break;
    }
}