정보보안 과정 Day86: 공개 키 암호2 (이론)

 

 

 

 

[목차]

 

 

1. 정수론

2. RSA

3. RSA에 대한 공격

4. 공개 키 암호 요점 정리

 

 

 

 

---

 

 

 

[정수론]

 

 

■ 소수와 서로소

■ 모들러 연산

■ 페르마와 오일러의 정리

■ 이산대수

 

 

 

1. 약수/공약수/최대공약수/소수/서로소

 

■ 약수(Divisors) - https://namu.wiki/w/약수(수학)

 

24의 양의 약수 = 1, 2, 3, 4, 6, 8, 12, 24

 

어떤 수를 나누었을 때 나머지가 0이 되는 수

즉, 나누어 떨어지는 수(단, 약수는 정수이다.)

모든 자연수는 1과 자기 자신을 약수로 갖는다.

1 보다 큰 자연수 중 1과 자기 자신밖에 약수가 존재하지 않는 자연수를 소수라 한다.

'a는 b의 약수이다'를 a|b라고 표현하기도 한다.

예를 들어 4|20은 참이지만 5|21은 거짓이다.

 

 

■ 최대 공약수(GCD) - https://ko.wikipedia.org/wiki/최대공약수

 

8, 12의 공약수는 1, 2, 4 이다.

* 8의 약수 = 1, 2, 4, 8

* 12의 약수 = 1, 2, 3, 4, 6, 12

따라서, 최대 공약수는 4이다.

 

GCD(Greatest Common Divisor, GCD)

두 수의 공통된 약수

두 수의 최대 공약수는 공약수 중 가장 큰 값

 

[참고] 공약수, 최대 공약수, 최소 공약수

[참고] 공배수, 최소 공배수, 최대 공배수

 

 

 

■ 소수(Prime Numbers) - https://ko.wikipedia.org/wiki/소수_(수론)

 

5는 소수이다.(1 x 5, 5 x 1)

 

자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다.

즉, 소수는 1과 자신의 수만을 약수로 갖는다.

 

 

 

■ 서로소(Relatively Prime Number) - https://ko.wikipedia.org/wiki/서로소_아이디얼

 

8과 15는 서로소이다.

* 8의 약수 : 1, 2, 4, 8

* 15의 약수: 1, 3, 5, 15

 

어떤 두 수가 공통적인 소인수를 갖지 못할 때 두수를 서로소라고 한다.

 

 

 

[참고] 수학기호표

[출처] http://blog.naver.com/PostView.nhn?blogId=lan2980&logNo=150178847390

 

 

2. 모듈러 연산 - https://johngrib.github.io/wiki/discrete-math-modular/

 

어떤 양의 정수 n과 어떤 정수 a가 주어지고

만약 a를 n으로 나눈다면 다음과 같은 관계를 가지고 몫(Quotient) q와 나머지r(Remainder)을 얻는다.

 

a = q / n

a = qn + r (0 <= r < n) a ≡ r mod n

q = a div n

r = a mod n

 

[python]

---------------------------------

(예)7 = 2 x 3 + 1

2 = 7 div 3 7 // 3 = 2 (몫)

1 = 7 mod 2 7 % 2 = 1 (나머지)

---------------------------------

 

모듈러 산술연산

[(a mod n) + (b mod n)] mod n = (a + b) mod n

(예): [(5 mod 3)+(4 mod 3)] mod 3 = (5 + 4) mod 3

[(a mod n) - (b mod n)] mod n = (a - b) mod n

(예): [(5 mod 3)-(4 mod 3)] mod 3 = (5 - 4) mod 3

[(a mod n) * (b mod n)] mod n = (a * b) mod n

(예): [(5 mod 3)*(4 mod 3)] mod 3 = (5 * 4) mod 3

 

 

 

3. 페르마와 오일러의 정리

 

1) 페르마 정리(Fermat Theorem)

만약 p가 소수라면, a는 p에 의해 나누어지지 않는 양의 정수이다.

그때,

ap-1 ≡ 1 mod p

성립한다.

 

(예) a=3, p=5

ap-1 = 1 mod p

34 = 1 mod 5

 

2) 페르마의 다른 유용한 형태

만약 p가 소수이고 a가 양의 정수라면

ap ≡ a mod p

성립한다.

 

(예) a=3, p=5

ap = a mod p

35 = 3 mod 5

 

3) 오일러의 정리

 

■ 오일러의 totient 함수

정수론에서 오일러의 totient 함수는 φ(n)라고 표기한다.

 

φ(n) : n보다 작고 n과 서로 소인 양의 정수의 개수

 

n 1 2 3 4 5 6 7 8 9 10 11 12

---------------------------------------------

φ(n) 1 1 2 2 4 2 6 4 6 4 10 4

 

n=1 1

n=2 1

n=3 1,2

n=4 1,3

n=5 1,2,3,4

n=6 1,5

n=7 1,2,3,4,5,6

n=8 1,3,5,7

n=9 1,2,4,5,7,8

n=10 1,3,7,9

n=11 1,2,3,4,5,6,7,8,9,10

n=12 1,5,7,10

 

 

■ 오일러 정리

서로소인 모든 a와 n에 대한 관계를 나타낸다.

 

aφ(n) ≡ 1 mod n

 

a = 3, n = 10, φ(n) = 4

34 = 81 ≡ 1 mod 10

 

a = 2, n = 11, φ(n) = 10

310 = 1024 ≡ 1 mod 11

 

 

■ 오일러 정리의 추가적인 특성

 

aφ(n)+1 ≡ a mod n

 

 

 

4. 이산 대수

 

다음과 같은 등식을 고려해 보자.

 

y = gx mod p

 

g, x, p 주어지면, y를 계산하는 것은 쉬운 문제이다. 최악의 경우, 반복적인 곱셈과정을 x번 수행해야만 하며, 효율적인 계산을 위한 알고리즘이 존재한다.

 

그러나, y, g, p가 주어진다고 하더라도 x를 계산하는 것은 매우 어려운 문제이다.그 어려움은 RSA 알고리즘을 풀기 위해 요구되는 인수분해의 어려움과 같은 어려움을 가진다.

 

 

  

 

---

 

 

 

[RSA]

 

 

■ RSA에 의한 암호화

 ■ RSA에 의한 복호화

 ■ 키 쌍의 생성 

■ 구체적 계산

 

 

1. RSA란 무엇인가?

 

RSA(Rivest-Shamir-Adleman)

https://ko.wikipedia.org/wiki/RSA_암호

RSA는 공개 키 암호 알고리즘의 하나

개발자 3명의 이름(Ron Rivest, Adi Shamir, Leonard Adleman)

* 로널드 라이베스트, 아디 샤므르, 레너드 애들먼

 

RSA 응용

공개 키 암호

디지털 서명(공개 키 서명)

키 교환(공개 키 전송/교환 방식)

 

 

 

2. RSA에 의한 암호화

 

RSA에서 평문도 키도 암호문도 숫자로 변환한 뒤 실행

RSA의 암호화는 다음 식으로 표현

 

암호문 = (평문)E mod N

평문을 E 제곱해서 N으로 나눈 나머지

 

■ E와 N은 무엇일까?

 

(E, N) : 공개 키

E와 N이라는 한쌍의 수를 알면 누구라도 암호화를 행할 수 있다.

E와 N이 RSA 암호화에 사용되는 키

E와 N은 면밀한 계산을 통해 생성

 

 

 

3. RSA에 의한 복호화

 

복호화도 단순하다.

RSA 복호화는 다음 식으로 표현

 

평문 = (암호문)D mod N

암호문을 D 제곱해서 N으로 나눈 나머지

 

■ D와 N은 무엇일까?

 

(D, N): 개인 키

D와 N이라는 한쌍의 수를 알면 누구라도 복호화를 행할 수 있다.

D와 N이 RSA 복호화에 사용되는 키

D와 N도 면밀한 계산을 통해 생성

E와 D는 밀접한 연관관계

 

 

 

 

4. 키 쌍의 생성

-----------------------------------------------------------------------------

암호문 = (평문)E mod N 평문 = (암호문)D mod N

-----------------------------------------------------------------------------

public key(E, N), private key(D, N) => 숫자 : E, D, N

 

① N을 구한다.

* 큰 소수를 2개 준비(p & q)

* N = p × q (p, q : 소수)

② L을 구한다.(L은 키 쌍을 생성할 때만 등장하는 수이다.)

* L은 RSA의 암호화나 복호화에 사용안함

* 키 쌍을 만들 때 임시로 사용

* L=LCM(p-1, q-1) : L은 p-1과 q-1의 최소공배수(Least Common Multiple)

③ E을 구한다.

* 다음 두 식을 만족하는 수 E를 하나 찾아낸다.

* (조건1) 1 < E < L

* (조건2) GCD(E, L) = 1 : E와 L은 서로소

④ D를 구한다

* 다음 두 식을 만족하는 수 E를 하나 찾아낸다.

* (조건1) 1 < D < L

* (조건2) E×D mod L = 1 : E×D와 L은 서로소

 

 

 

 

5. 구체적 계산 - 키 쌍(공개 키, 개인 키)의 생성

 

https://ko.wikipedia.org/wiki/RSA_암호

구체적인 수를 써서 RSA의 키 쌍 생성, 암호화/복호화를 실제로 구현

너무 큰 수(p와 q)를 사용하면 계산이 힘들기 때문에 작은 수를 이용하여 계산

 

■ RSA 공개키/개인키 구하기 예 (구할려고 하는 값 => N, E, D)

 

① p와 q 선택하기(2r의 큰 소수 p, q 선택)

* 2개의 소수 p=17, q=19 선택

② N 구하기 (2개의 큰 소수 곱하기)

* N = p × q = 17 × 19 = 323

③ L 구하기

* L = LCM(p-1, q-1) = LCM(16, 18) = 144 (16과 18의 최소공배수)

④ E 구하기(선택하기)

* (조건1) L < E < 144 조건을 만족하는 E 값을 하나 선택한다

* (조건2) GCD(E, L) = 1 되는 수 E를 선택하자

* E가 될수 있는 수는 다음과 같은 수이다.

=> 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, ...

* E=5 선택(다른 수를 선택해도 무방)

⑤ D 구하기

* (조건1) 1 < D < 144 조건을 만족하는 D 값을 하나 선택한다

* (조건2) E × D mod L

=> 5 × χ mod 144 = 1

=> 145 mod 144 = 1 이므로 D=29

⑥ 따라서, 공개키, 개인키

* 공개키: (E, N) = (5, 323)

* 개인키: (D, N) = (29, 323)

 

 

■ RSA 암호화/복호화 예

 

평문은 N=323 보다 작은 수

예를 평문(P)=123이라 하고 암호화를 해 보자.

 

암호문 = (평문)E mod N (P=123 --> C=225)

= 1235 mod 323

= 225

 

평문 = (암호문)D mod N (C=225 --> P=123)

= 22529 mod 323

= 123

 

[참고] "22529 mod 323"의 계산

29 = 10+10+9

 

22529 = 22510+10+9 = 22510 × 22510 × 2259

22510 = 332525673007965087890625

2259 = 1477891880035400390625

 

22510 mod 323 = 332525673007965087890625 mod 323 = 16

2259 mod 323 = 1477891880035400390625 mod 323 = 191

 

22529 mod 323 = 22510 × 22510 × 2259 mod 323

= (22510 mod 323) × (22510 mod 323) × (2259 mod 323) mod 323

= (16 × 16 × 191) mod 323

= 48896 mod 323

= 123

 

따라서, 22529 mod 323 = 123

 

 

개인키는 숫자가 크고

공개해도 되는 공개키는 숫자가 작다.

 

 

 

---

 

 

 

 

[공개 키 암호 요점 정리]

 

 

비대칭 암호

공개 키 암호화 방식: RSA, Rabin, ElGamal, ECC

공개 키 서명 방식: RSA(PKCS#1 v1.5, PKCS#1 PSS), DSA, ECDSA, EdDSA/Ed25519

 

 

키 배송 문제 해결

키의 사전 공유에 의한 해결

키 배포 센터에 의한 해결

Diffie-Hellman 키 교환

공개 키 암호에 의한 해결

 

 

RSA 암호화, 복호화

C = P^E mod N (E, N) 공개 키

P = C^D mod N (D, N) 개인 키

 

 

RSA-OAEP(Optimal Asymmetric Encryption Padding)

ECC(Elliptic Curve Cryptosystems)

 

 

 

---