[BOJ 13618] RSA

https://www.acmicpc.net/problem/13618

13618번: RSA

 

- 문제 요약

 

RSA 알고리즘은 가장 널리 사용되는 암호화 알고리즘 중 하나이며 가장 안전한 대안 중 하나로 간주됩니다. 

이 문제에서는 RSA 암호화를 해독하는 프로그램을 작성해야 합니다.

 

첫 번째 줄에는 세 개의 정수 N, E, C가 입력됩니다. (15 ≤ N ≤ 10^9 , 1 ≤ E < N, 1 ≤ C < N)

N과 E는 RSA 알고리즘의 공개 키를 구성합니다. C는 해당 공개 키로 암호화된 메시지입니다.

C를 복호화하여 단일 라인으로 출력하세요.

 

 

- 알고리즘 정리

 

https://namu.wiki/w/RSA%20%EC%95%94%ED%98%B8%ED%99%94

RSA 암호화 - 나무위키

기본적인 RSA 복호화 순서대로 코드를 작성해서 문제를 해결해 주면 됩니다.

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
int n,e,c;

int phi(int a){
	int result=a;
	for(int i=2;i<=a/i;i++){
		if(a%i==0){
			while(a%i==0){
				a/=i;
			}
			result-=result/i;
		}
	}
	if(a>1){
		result-=result/a;
	}
	return result;
}

int f(int a,int x,int m){
	int result=1;
	while(x>0){
		if(x%2){
			result=(ll)result*a%m;
		}
		a=(ll)a*a%m;
		x/=2;
	}
	return result;
}

int main(){
	cin>>n>>e>>c;
	int d=f(e,phi(phi(n))-1,phi(n));
	int result=f(c,d,n);
	cout<<result;
}

코드 제출 결과