RSA 알고리즘은 가장 널리 사용되는 암호화 알고리즘 중 하나이며 가장 안전한 대안 중 하나로 간주됩니다. 절차는 다음과 같습니다.
두 개의 홀수 소수 P와 Q를 선택하고 N = PQ를 계산합니다. 다음으로, 오일러 피 함수 φ(N) = (P - 1)(Q - 1)을 계산하고, φ(N)과 서로소이면서 1 < E < φ(N)을 만족하는 정수 E를 선택합니다. 마지막으로 φ(N)에 대한 E의 모듈러 역원, 즉 DE = 1(mod φ(N))을 만족하는 정수 D를 계산합니다.
이를 통해 공개키(N, E)와 비밀키(N, D)를 얻을 수 있습니다.
0 < M < N을 만족하는 메시지 M을 암호화하려면 C = ME (mod N)을 계산하여 암호화된 메시지 C를 구할 수 있습니다. 원래 메시지로 복호화하려면 M =CD(mod n)을 계산하면 됩니다. 이를 위해서는 공개키를 아는 것만으로는 충분하지 않으므로 비밀키를 알아야 합니다. 앞서 사용된 x = 1(mod y)이라는 표현은 x를 y로 나눈 나머지가1이라는 것과 같습니다.
RSA 암호를 해독하는 프로그램을 작성해야 합니다.
입력
세 정수 N, E, C가 입력으로 주어지고, 15 ≤ N ≤ 109, 1 ≤ E < N 및 1 ≤ C < N을 만족합니다. N과 E는 RSA 알고리즘의 공개키입니다. C는 해당 공개키로 암호화된 메시지입니다.
w8385 3년 전 11
문제
RSA 알고리즘은 가장 널리 사용되는 암호화 알고리즘 중 하나이며 가장 안전한 대안 중 하나로 간주됩니다. 절차는 다음과 같습니다.
두 개의 홀수 소수 P와 Q를 선택하고 N = PQ를 계산합니다. 다음으로, 오일러 피 함수 φ(N) = (P - 1)(Q - 1)을 계산하고, φ(N)과 서로소이면서 1 < E < φ(N)을 만족하는 정수 E를 선택합니다. 마지막으로 φ(N)에 대한 E의 모듈러 역원, 즉 DE = 1(mod φ(N))을 만족하는 정수 D를 계산합니다.
이를 통해 공개키(N, E)와 비밀키(N, D)를 얻을 수 있습니다.
0 < M < N을 만족하는 메시지 M을 암호화하려면 C = ME (mod N)을 계산하여 암호화된 메시지 C를 구할 수 있습니다. 원래 메시지로 복호화하려면 M =CD(mod n)을 계산하면 됩니다. 이를 위해서는 공개키를 아는 것만으로는 충분하지 않으므로 비밀키를 알아야 합니다. 앞서 사용된 x = 1(mod y)이라는 표현은 x를 y로 나눈 나머지가1이라는 것과 같습니다.
RSA 암호를 해독하는 프로그램을 작성해야 합니다.
입력
세 정수 N, E, C가 입력으로 주어지고, 15 ≤ N ≤ 109, 1 ≤ E < N 및 1 ≤ C < N을 만족합니다. N과 E는 RSA 알고리즘의 공개키입니다. C는 해당 공개키로 암호화된 메시지입니다.
출력
원래 메시지인 정수 M, 1 ≤ M < N을 출력해야 합니다.