Rsa 알고리즘 c언어 - rsa algolijeum ceon-eo

Question

C언어로 만든 간단한 RSA.

안녕하세요.

오늘은 공개키 암호 알고리즘 중 하나인 RSA 코드입니다.

그냥 공부하면서 대충 만든 겁니다.

특정 파일/디렉토리 명을 주면 모든 정보를 출력
권한을 700으로 변경하는 프로그램

코드

코드는 다음과 같습니다.

#include<stdio.h>
/*ras*/
long pow_(long i,long j,long k){
	double l,temp,p=1;
	for(temp=0;temp < j ; temp++){
		p=(p*((double)i));
		l=(long)(p/k); //소수점 삭제.
		p=p-(l*k);
	}
	return (long)p;
}
int encryption(int input,int e, int n){
	int i=pow_(input,e,n);
	printf("입력받은 수의 rsa암호화 결과= %d\n",i);
	return i;
}
int Decryption(int input,int d, int n){
	int i=pow_(input,d,n);
	printf("암호화된 수의 rsa복호화 결과= %d\n",i);
	return i;
}
int main(){
	int input;
	scanf("%d",&input);
	int p=17,q=11;
	int e=7, d=23, N=p*q;
	input=encryption(input,e,N);
	Decryption(input,d,N);
	return 0;
}

알고리즘.

두 소수 p와 q를 선택한다.

(위의 코드에서는 17과 11을 선택.)

φ(N)=(p-1)(q-1)=160

160보다 작으면서 φ(N)과 서로소인 수 e를 선택한다.

(위의 코드에서는 7.)

d<160이면서 demodφ(N)=1인 수 d를 결정한다.

(위의 코드에서는 d*7mod160=1이므로 23이 d가 된다.)

공개키={7,187}, 개인키={23,187}이 된다.

실행결과.

그래서 위의 코드를 실행해보면 이런 결과가 나온다.

hero ・ 2019. 9. 19. 18:54

C언어 RSA 암호화 알고리즘

RSA 는 큰 소수의 소인수 분해의 어려움을 이용하는 암호화 알고리즘이다 현재 가장 많이 사용되고 있는 암호화 알고리즘 으로

key의 크기가 2046bit 이상 되면 안전하다고 판단한다. 암호화 는 알고리즘에 의존하면 안된다 수학적 계산의 시간 어려움을 이용해야

안전하다 하지만 RSA 도 양자 컴퓨터가 나온다면 수시간 내에 깨질것이다.

아무튼 C언어로 RSA알고리즘을 짜보았다.. 이론으로만 알고 있던 RSA를 코드로 짜보면서 더 기억에 남았던 것 같다.

우선 코드 설명은 큰 소수를 구하는 일 은 시간상 오래 걸리기 때문에 미리 배열에 소수를 구하였다 실제 사용되는 RSA암호에서도

큰 소수를 미리 구해두고 랜덤하게 사용 하는것 으로 알고있다.

현재는 암호화 알고리즘만 만든 상태이다, 또한 최초 알고리즘을 만들때는 문자열을 입력받을려고 해서 동적할당을 해둔 상태이다.

RSA 알고리즘

p , q 구하기

p,q는 아주 큰 소수 이여야 한다.

n 구하기

임의의 두 소수 p와 q를 정하고 n = p * q를 해주면 n을 구할 수 있다.

Φ(n) 구하기

n이 양의 정수 일 때, ϕ(n)은 n과 서로소 인 1부터 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)를 모두 구하였다. 즉, 개인키와 공개키가 생성되었다.

#include <stdio.h> #include <stdlib.h> #include <time.h> #include <math.h> //RSA Encription 알고리즘 프로그램 void Encrption(int **C, int **M, int n , int e) //M^e mod n { int i; int temp; int plus; e = 3; printf("n : %d\n",n); //plus = (unsigned long long)(pow((double)*(*M+i) , (double)e)) % n; temp = **M % n; plus = (int)pow((double)temp , (double)e) % n; //M%n ^ e %n printf("암호화 되기전 숫자 : %d\n",**M); printf("암호화 후 숫자 : %d\n",**C); } int Public_key(int ep) // 오일러 파이보다 작으면서 오일러 파이와 서로소 인 임의의 수 (공개키) { //ep = 8; int i,j,k; int randum=0; //랜덤수 int temp = ep; //int cp = 0; // encrption key temp = temp - 1; srand((unsigned)time(NULL)); //randum = rand() % temp + 1; int cp; // 서로소인 임의의 수 int count = 0; // 힙 영역에 있는 메모리 주소에 접근하기 위해 int* mathematics = (int*)malloc(sizeof(int) * ep - 1); int* cpminus; //int* tmp = (int*)malloc(sizeof(int) * randum); if(mathematics == NULL){ printf("동적 할당 실패!"); exit(1); } else{ for(i=1;i<=ep;i++) // '오일러 파이' 의 약수 구하기 155 { if(ep % i == 0) { (*(mathematics + count)) = i; //포인터 표기법 으로 4byte씩 증가 하면서 저장) //printf("ep의 %d약수 : %d \n",ep,(*(mathematics+count))); count++; } } do{ count = 0; //카운트 초기화 randum = rand() % 500 + 1; int* tmp = (int*)malloc(sizeof(int) * randum); for(k=1;k<=randum;k++) // '임의의 수' 약수 구하기 { if(randum % k == 0) { (*(tmp + count)) = k; //printf("randum %d의약수 : %d\n ",randum,(*(tmp+count))); count++; } } count = 0; for(i=0;i<ep;i++) //서로소 판별 반복문 { count = 0; for(j=0;j<randum;j++) { if(*(mathematics+i) == *(tmp+j)) { count++; if(*(mathematics+i) == 1 || *(tmp+j) == 1) { count--; } } if(count == 1) { break; } } if(count == 1) { break; } } free(tmp); }while(count != 0); //count가 0이라면 서로소 인것 //printf("[randum: %d ep: %d]\n",randum,ep); } cp = randum; printf("e : %d\n",cp); free(mathematics); //오일러 파이 함수 동적 할당 해제 //free(tmp); //key 동적 할당 해제 return cp; } int Euler_Pie(int p, int q) //오일러 파이 구하는 함수 { int ep = (p - 1) * (q - 1); return ep; } int Prime_product(int p, int q) // 두 소수의 곱 함수 { printf("p * q : %d\n",p*q); return p*q; } void Over_lap(int* p , int* q , int* arr) // p , q 중복 제거 함수 { int i,j; srand(time(NULL)); i = rand() % 53; j = rand() % 53; *p = arr[i]; *q = arr[j]; while(*p == *q) { *p = rand() % 53; } printf("p : %d\n",*p); printf("q : %d\n",*q); } int main() { int p,q; //소수 int e,d; //공개키 , 개인키 8 int n; // p,q 곱 int op; //오일러 파이 int* C = (int*)malloc(sizeof(int) * 1); int* M = (int*)malloc(sizeof(int) * 1); //int* M = (char*)malloc(sizeof(char) * 100); int arr[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, //1 ~ 256 까지의 소수 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251}; printf("암호화 할 숫자 를 입력하세요 : "); scanf("%d",M); Over_lap(&p,&q,arr); //소수의 중복 제거 - > p != q n = Prime_product(p,q); //소수의 곱 - > p * q op = Euler_Pie(p,q); // 오일러 파이 - > Φ(n) e = Public_key(n); //공개키 - > Φ(n) < (Φ(n) \ b) = 1 Encrption(&C,&M,n,e); //암호화 -> free(C); free(M); return 0; }

암호화 할 숫자 를 입력하세요 : 10 p : 73 q : 227 p * q : 16571 e : 255 n : 16571 암호화 되기전 숫자 : 10 암호화 후 숫자 : 2056064