RSA 암호 화 알고리즘

알고리즘 설명:
1. 소수 p, q 두 개 선택
2. 계산 n = p * q, fn = (p - 1) * (q - 1)
3. 정수 e 를 선택 하여 e 와 fn 의 최대 공약수 가 1 이 고 e 는 데 이 터 를 암호 화 하 는 데 사 용 됩 니 다.
4. 정수 d 를 계산 하여 d * e 가 fn 을 제외 한 나머지 를 1 로 한다.d. 비밀문 을 복호화 하고 명문 을 복원 하 는 데 사용 합 니 다.
5. 명문 은 m 이 고 밀 문 은 c 라 고 가정 한다.
원문 을 암호 화 할 필요 가 있다 면 다음 과 같은 계산 을 한다.
c= me mod n
밀 문 을 명문 으로 복원 하려 면 다음 과 같이 계산한다.
m=cd mod n
6. 가설 p = 101, q = 103, n = 101 * 103 = 10403, fn = 100 * 102 = 10200
e=7。7 과 10200 의 최대 공약수 가 1 이기 때문이다.
d=8743。8743 * 7 mod 10200 = 1 때문에
(1) 명문 을 하나의 정수 로 가정한다 73
RSA 를 통 해 암호 화 된 후
73^7%10403=7716
(2) 7716 의 원문 복원
7716^8743%10403=73。
다음은 항 전 OJ 의 이전 RSA 에 관 한 문제 입 니 다. 문제 에서 p, q 와 e 의 값 을 제시 하고 암호 화 된 밀 문 을 드 립 니 다.원문의 복원 을 요구 하 다.문제 설명 은 참고 할 수 있다.http://acm.hdu.edu.cn/showproblem.php?pid=1211
다음은 RSA 알고리즘 암호 화 된 밀 문 을 복원 하 는 C 코드 입 니 다.
#include<stdio.h>

int main(){
    int p,q,e;
    int l,ch,i;
    while(scanf("%d%d%d%d",&p,&q,&e,&l)!=EOF){
        long long n=p*q;
        long long fn=(p-1)*(q-1);
        int d=1;
        //     d  。  d*e%fn=1
        while((d*e)%fn!=1){
            d++;
        }
        while(l--){
            scanf("%d",&ch);
            int result=1;
            //   m^d%n  ,   
            for(i=1;i<=d;i++){
                result=(result*ch)%n;
            }
            printf("%c",result);
        }
        printf("
"); } return 0; }

위의 프로그램 에서 알 수 있 듯 이 명문 복원 에서 가장 중요 한 것 은 d 의 값 을 계산 하 는 것 이다.RSA 알고리즘 은 복호화 과정 에서 모두 멱 연산 을 해 야 합 니 다. 현재 RSA 알고리즘 의 안전 을 위해 p 와 q 의 값 은 보통 100 비트 이상 의 소수 이 고 해당 d 와 e 의 값 도 크게 변 하기 때문에 RSA 알고리즘 의 연산 속 도 는 매우 느 릴 것 입 니 다.

좋은 웹페이지 즐겨찾기