[보안] RSA 암호화 알고리즘 계산 방법
A. 키 생성 방법
1. 임의의 두 소수 p,q 선택 (단 p≠q)
2. p와 q를 곱한 값 n을 생성.
n = p * q
3. Totient Function Ø(n) 값 구하기.
Ø(n) = (p-1)(q-1)
4. Ø(n)와 서로소 관계의 e 구하기. (단, 1 < e < Ø(n) )
Gcd(e, Ø(n)) = 1 ( Gcd는 최대 공약수 함수 )
5. d = e^-1(mod Ø(n))
=> e * d = 1(mod Ø(n))
=> (e * d) mod Ø(n) = 1
(단, d < Ø(n))
∴ 공개키 : e , n
개인키 : d , n
B. 암호화
C = M^e (mod n) (단, M < n, M은 정수(Plaintext))
C. 복호화
M = C^d (mod n) (단, M < n, M은 정수(Plaintext))
--
Totient Function Ø(n) 문제 풀기
1. ϕ(7) = 1 2 3 4 5 6 = 6개
2. ϕ(20) = 1 3 7 9 11 13 17 19 = 8개
값을 집어넣은 예시
A. 키 생성 방법
p, q = 5, 7 (둘 다 소수에 겹치지 않도록 예시)
n = 5 * 7 = 35
Ø(n) = (5-1)(7-1) = 4 * 6 =24
e = 1~24 사이 중 임의로 7
(e * d) mod Ø(n) = 1 (단, d < Ø(n))
7 * d mod 24 = 1 (단, d < 24)
24의 배수 + 1 = 7의 배수.
7 14 21 28 ...
49 =48 + 1
d = 7
공개키(e, n) : 7, 35
개인키(d, n) : 7, 35
B. 암호화
평문 M = 3
C = M^e (mod n) (단, M < n, M은 정수(Plaintext))
C = 3^7 (mod 35) (단, M < n, M은 정수(Plaintext))
3^7 mod 35 = C
= 2187 mod 35
= 2187 - 2170 = 17 = C
∴ 암호문 C = 17
C. 복호화
M = C^d (mod n) (단, M < n, M은 정수(Plaintext))
M = 17^7 (mod 35) (단, M < n, M은 정수(Plaintext))
410338673 mod 35 = M
= 410338673 - 410,338,670 = 3
∴ 평문 M = 3
< 문제 풀이 >
Q1) p = 3, q = 11, M = 5 일 때, e = 7을 선택했다.
올바른 선택인가? 이유도 설명하시오.
p = 3, q = 11 인데,
p와 q의 조건은 p와 q는 소수이며, p≠q 이기 때문에, 조건을 만족합니다.
e 는 Gcd(e, Ø(n)) = 1 를 만족해야하며,
1 < e < Ø(n) 라는 조건도 추가로 만족해야합니다.
n = 3 * 11 = 33
Ø(33) = (3-1)(11-1) = 2 * 10 = 20
Gcd(e, 20) = 1을 만족해야합니다.
e가 만약 7이라면,
20과의 최대 공약수는 1이기 때문에 e 또한 만족합니다.
M은 Plain text 이기 때문에,
M은 정수이여야만 하고, n보다 작아야만 합니다.
따라서, M이 5 라면, n은 33이기 때문에 ‘ M < n ’ 이라는 조건을 만족하며,
정수이기 때문에 모든 변수들의 값들은 올바른 선택입니다.
(b) p = 3, q = 11, e = 7, M = 5 일 때, C?
계산 과정도 나타내시오.
암호화 계산식 : C = M^e (mod n) (단, M < n, M은 정수(Plaintext))
n = p * q = 33
e = 7
M = 5
C = M^e (mod n) = 5^7 mod 33 = 78125 mod 33 = 14
∴ C = 14
(c) p = 3, q = 11, e = 7, C = 26 일 때, M?
복호화 계산식 : M = C^d (mod n) (단, M < n, M은 정수(Plaintext))
n = p * q = 33
Ø(33) = 20
e = 7
C = 26
(e * d) mod Ø(n) = 1 (단, d < Ø(n))
=> 7d mod 20 = 1
7d = 7, 14, 21, ...
d = 3일때, 21 mod 20 = 1 만족.
따라서 변수들의 값은,
d = 3 n = 33
e = 7 n = 33
C = 26
M = 26^3 mod 33 = 17576 mod 33 = 20
∴ M = 20