// RSA 암호에서 키 생성 ① 두 개의 큰 소수 p, q(p≠q)를 임의로 선택한다. 소수인지 검사해야 한다. → p와 q는 적어도 512bit가 되도록 한다. 매우 큰 소수가 된다. ② 두 소수를 곱한 것을 n, 두 소수보다 1씩 작은 수를 곱한 수를 Phi(n)이라 한다. n = p × q //p, q의 보안은 매우 중요, 키 생성 후 p, q는 삭제 가능 Phi(n) = (p-1)(q-1) //Φ(n) = (p-1)(q-1) ③ 1 < e < Φ(n)인 정수 중에서 Φ(n)과 서로소 관계가 되는 임의의 수 e를 선택한다. gcd(e, Φ(n)) = 1 //e는 공개키로 사용된다. ④ d와 e를 곱하여 Φ(n)으로 나눈 나머지가 1이 되는 d를 구한다. (d × e) mod Φ(n) = 1 //d × e ≡ 1 mod Φ(n) → d는 개인키가 된다. ↓ 생성된 키 : 공개키는 (e, n)인 숫자쌍이고, 개인키는 (d, n)인 숫자쌍이다.
1. RSA 공개키 암호에서 2개의 소수 p=3와 q=7가 주어지고 복호화키(d) 5로 고정했을 때, 암호화 키(e) 값과 메시지 2에 대한 암호문 값(C)은? [2022년 군무원 9급] ① e = 3, C = 5 ② e = 4, C = 7 ③ e = 5, C =11 ④ e = 6, C =15
① 먼저, 서로 다른 임의의 두 소수를 선택한다. p = 7, q = 11 ② n = p × q를 구한다. n = p × q = 7 × 11 = 77 ③ n의 오일러 파이 함수 Φ(n) = (p-1)(q-1)을 구한다. Φ(n) = Φ(77) = (p-1)(q-1) = (7-1)(11-1) = 60 ④ 1 < e < 60인 정수 중에서 Φ(n)과 서로소 관계가 되는 임의의 수 e를 선택한다. → e = 13이 선택된 것으로 가정한다.(e는 공개키) ⑤ d와 e를 곱하여 Φ(n)으로 나눈 나머지가 1이 되는 d를 구한다. (d × e) mod Φ(n) = 1 → 즉, (d × e) mod 60 = 1로 d와 e는 서로 역원 관계이다. (d × 13) mod 60 = 1 d = 37 → 개인키 ⑥ 최종적으로 생성된 키 관계는 다음과 같다. 공개키 (e, n) = (13, 77) 개인키 (d, n) = (37, 77) ⑦ 평문 p=2에 대한 암복호화 과정은 다음과 같다. 평 문 2 암호화 c = mod n = mod 77 = 30 mod 77 암호문 30 복호화 p = mod n = mod 77 = 2 mod 77 평 문 2 •RSA 암호시스템의 메시지 암복호화는 서로 역관계에 있다.
1. 공개키 암호 알고리즘인 RSA에 대한 설명으로 가장 옳지 않은 것은? (단, N은 서로 다른 두 개의 소수를 곱한 값이다) [2022년 서울 7급] ① 공개키 암호 알고리즘은 암호화 키와 복호화 키를 사용하며, RSA는 디지털 서명에 사용할 수 있다. ② RSA의 암호문은 평문을 E제곱해서 mod N을 취하여 만들 수 있으며 여기서 E와 N으로 이뤄진 쌍이 공개키다. ③ RSA의 평문은 암호문을 D제곱해서 mod N을 취하여 만들 수 있으며, 여기서 D와 N으로 이뤄진 쌍이 개인키다. ④ 큰 수의 소인수분해를 고속으로 할 수 있는 방법이 발견되면 RSA를 해독할 수 있으며, 중간자 공격을 사용해도 RSA를 해독할 수 있다.
// RSA 암호에서 키 생성
① 두 개의 큰 소수 p, q(p≠q)를 임의로 선택한다. 소수인지 검사해야 한다.
→ p와 q는 적어도 512bit가 되도록 한다. 매우 큰 소수가 된다.
② 두 소수를 곱한 것을 n, 두 소수보다 1씩 작은 수를 곱한 수를 Phi(n)이라 한다.
n = p × q //p, q의 보안은 매우 중요, 키 생성 후 p, q는 삭제 가능
Phi(n) = (p-1)(q-1) //Φ(n) = (p-1)(q-1)
③ 1 < e < Φ(n)인 정수 중에서 Φ(n)과 서로소 관계가 되는 임의의 수 e를 선택한다.
gcd(e, Φ(n)) = 1 //e는 공개키로 사용된다.
④ d와 e를 곱하여 Φ(n)으로 나눈 나머지가 1이 되는 d를 구한다.
(d × e) mod Φ(n) = 1 //d × e ≡ 1 mod Φ(n) → d는 개인키가 된다.
↓
생성된 키 : 공개키는 (e, n)인 숫자쌍이고, 개인키는 (d, n)인 숫자쌍이다.
1. RSA 공개키 암호에서 2개의 소수 p=3와 q=7가 주어지고 복호화키(d) 5로 고정했을 때, 암호화 키(e) 값과 메시지 2에 대한 암호문 값(C)은? [2022년 군무원 9급]
① e = 3, C = 5 ② e = 4, C = 7
③ e = 5, C =11 ④ e = 6, C =15
① 먼저, 서로 다른 임의의 두 소수를 선택한다.
p = 7, q = 11
② n = p × q를 구한다.
n = p × q = 7 × 11 = 77
③ n의 오일러 파이 함수 Φ(n) = (p-1)(q-1)을 구한다.
Φ(n) = Φ(77) = (p-1)(q-1) = (7-1)(11-1) = 60
④ 1 < e < 60인 정수 중에서 Φ(n)과 서로소 관계가 되는 임의의 수 e를 선택한다.
→ e = 13이 선택된 것으로 가정한다.(e는 공개키)
⑤ d와 e를 곱하여 Φ(n)으로 나눈 나머지가 1이 되는 d를 구한다.
(d × e) mod Φ(n) = 1 → 즉, (d × e) mod 60 = 1로 d와 e는 서로 역원 관계이다.
(d × 13) mod 60 = 1
d = 37 → 개인키
⑥ 최종적으로 생성된 키 관계는 다음과 같다.
공개키 (e, n) = (13, 77)
개인키 (d, n) = (37, 77)
⑦ 평문 p=2에 대한 암복호화 과정은 다음과 같다.
평 문
2
암호화
c = mod n = mod 77 = 30 mod 77
암호문
30
복호화
p = mod n = mod 77 = 2 mod 77
평 문
2
•RSA 암호시스템의 메시지 암복호화는 서로 역관계에 있다.
1. 공개키 암호 알고리즘인 RSA에 대한 설명으로 가장 옳지 않은 것은? (단, N은 서로 다른 두 개의 소수를 곱한 값이다) [2022년 서울 7급]
① 공개키 암호 알고리즘은 암호화 키와 복호화 키를 사용하며, RSA는 디지털 서명에 사용할 수 있다.
② RSA의 암호문은 평문을 E제곱해서 mod N을 취하여 만들 수 있으며 여기서 E와 N으로 이뤄진 쌍이 공개키다.
③ RSA의 평문은 암호문을 D제곱해서 mod N을 취하여 만들 수 있으며, 여기서 D와 N으로 이뤄진 쌍이 개인키다.
④ 큰 수의 소인수분해를 고속으로 할 수 있는 방법이 발견되면 RSA를 해독할 수 있으며, 중간자 공격을 사용해도 RSA를 해독할 수 있다.