728x90
반응형
** 아래 코드는 검증되지 않았음(개인 학습용), 문제점 발견 시 댓글로 적어주시면 감사하겠습니다.
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뿐만 아니라 ECC, 디피헬만 등 다양한 알고리즘들이 설명되어 있다. (C로 구현된 예제가 있음)
https://www.crocus.co.kr/1203
- 나무위키, 이론 이해를 위해 참고 (설명 좀 더 디테일)
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
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;
}
}
728x90
반응형
'코딩테스트 > 알고리즘' 카테고리의 다른 글
[자료구조] 우선순위 큐 - 작성 중 (0) | 2022.04.11 |
---|---|
[알고리즘] 하노이의 탑 (0) | 2022.03.09 |
[알고리즘] DFS/ BFS (0) | 2022.02.05 |
[알고리즘] 달팽이 배열 채우기 (0) | 2021.11.06 |
[알고리즘] 함수 (0) | 2021.10.11 |
[알고리즘] 0 ~ N 사이의 소수 개수 구하기 (2) | 2020.05.19 |
댓글