【알고리즘】 26강. RSA 알고리즘

26강. RSA 알고리즘 

 

추천글 : 【알고리즘】 알고리즘 목차

---

a. 국가암호공모전 II-A 분야 문제 01 (2016)

---

 

RSA 알고리즘

 

20131126_RSA AtoZ2.pptx

다운로드

 

// C 언어로 쓰여진 코드이다.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <string.h>
#include <conio.h>
#define FALSE 0
#define TRUE 1

int n; // n은 암호에 이용되는 두 소수의 곱이다. 
int Make_Public_Key(long EulerPi);
int Make_Private_Key(int e, long EulerPi);
int IsNotPrime(int n);  //소수인지검사 
long Make_Random_Prime_Number();// 랜덤 소수(2개) 생성기 
long mod(long n, long exponent, long m);
int Make_PassWord(int* Message, int* PassWord, int* public_key);  //평문을 암호문으로 만드는 함수 
int Make_SolveWord(int* PassWord, int* SolveWord, int* private_key);  //암호문을 평문으로 만드는 함수
int GCD(int x, int y){  return y == 0 ? x : GCD(y, x % y) ;  } //최대 공약수 검사 

void main(void){
    int public_key, private_key;
    long EulerPi;
    EulerPi = Make_Random_Prime_Number(); // 두 개의 소수를 만들고 전역변수 n값을 구한다. 
    public_key = Make_Public_Key (EulerPi);  // 공개키를 만든다.
    private_key = Make_Private_Key (public_key, EulerPi);  //개인키를 만든다. 
    printf("EulerPi=%d, public_key=%d, private_key=%d\n\n", EulerPi, public_key, private_key); //출력 
    long long Message, PassWord, SolveWord;

    printf("\t평문을 입력하세요 = ");
    scanf("%d", &Message);

    PassWord = mod(Message, public_key, n);
    printf("====================================================\n\n");
    printf(" 암호화된 데이터 = %ld = message^(public key)(mod n) ", PassWord); 
    SolveWord = mod(PassWord, private_key, n);
    printf("\n\n 복호화된 데이터 = %ld = password^(private key)(mod n)\n", SolveWord);
}

long Make_Random_Prime_Number() { // 랜덤 소수(2개) 생성기
    int i;
    int Prime[2]; // P와 Q 두개의 소수는 공개키, 비밀키의 기본 소수
    time_t t;
    srand((unsigned int) time(&t)); //난수생성
    for (i=0; i<2; i++){   // 2개의 임의의 솟수 P와 Q를 생성한다. 
        do{
            Prime[i]=rand()%100; // 2자리수로 고정  
        } while(IsNotPrime(Prime[i]));  //소수가 아니면 반복한다.
    }

    n=Prime[0]*Prime[1];  // 두개의 소수 p,q를 이용해 n값 생성
    printf("\nP=%d, Q=%d, n=%d\t(n은 두 소수의 곱)\n", Prime[0], Prime[1], n);
    return (Prime[0]-1)*(Prime[1]-1);  // 오일러 파이값;
}

int Make_Public_Key(long EulerPi){
    long e;
    do {
        e=rand()%100; //3자리로 제한 
        if ( (e < EulerPi) && (GCD(e, EulerPi)==1) ) return e; // 오일러 파이와 서로 소인 e를 리턴. 
    }while(1);
}

int Make_Private_Key(int e, long e_pi){
    int d=0;
    while (((e*d)%e_pi)!=1) d++;  //개인키 생성
    return d; //개인키를 리턴한다. 
}

int IsNotPrime(int n) {  //소수가 아닌지 검사
    int  i, limit;
    if (!(n%2))  return (TRUE);  //짝수이면 소수가 아니다.
    limit = (int)sqrt(n) + 1;  //n제곱+1을 하여 보다 빨리 소수를 찾는다.
    for (i = 3; i <= limit; i += 2)  //3부터 홀수 단위로 나머지 연산을 한다. 
        if (!(n%i))  return (TRUE); 
    return (FALSE);
}

long mod(long n, long exponent, long m) { // residue = n^exponencial (mod m)을 수행한다.
    long i, residue = 1;
    for(i=1; i<=exponent; i++) {
        residue = residue%m; 
        residue = residue*n;
     }   //residue=residue%n 오버플로를 방지하고자 mod연산을 이용하여 자릿수를 줄인다.
    return residue%m;
}

 

입력: 2013.11.27 13:08

수정: 2023.10.07 01:53