[IT개론🗃️] 보안과 암호화

출처  : 소프트웨어 세상을 여는 컴퓨터 과학

 

1. 보안과 암호화의 개요

1) 암호화 기술

(1)  암호화 기술의 등장배경

- 사이버 범죄(해킹, 바이러스), 개인정보 유출 문제 증가

- 신원 확인, 정보 비밀성 유지, 무결성 유지 등의 필요성 대두

 

(2) DES(data encryption standard)

- 1970년대 민간 분야에 사용하기 위해 암호화 표준을 마련

- 현대 암호학의 본격적인 출발

- 대칭키(비밀키) 방식

 

(3) 암호화 기술의 개념

- 전송 데이터를 암호화하여 전달하는 기술

• 암호화(encryption) : 평문(plaintext)을 암호문(ciphertext)으로 바꾸는 과정
• 복호화(decryption) : 암호문을 평문으로 바꾸는 과정

 

---

 

2. 초기 암호화 방식

1) 시저 암호

(1) 시저 암호의 원리

- 알파벳을 정해진 자리만큼 이동한 문자로 대체 (치환형 암호)

ex) 숫자키가 3인 경우

평문 문자

A

B

C

D

E

F

J

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

암호 문자

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

 

(2) 숫자키를 알 수 없는 경우 해독 방법

- 암호문을 맨 위에 쓴 다음, 각각의 암호화된 알파벳을 알파벳순에 따라 왼쪽 수만큼 더한 값으로 써 내려감

- 어느 순간 의미 있는 문장이 되는 값이 보이면, 그 문장이 해독한 결과

 

(3) 단어 키를 사용한 암호화

① 암호화에 사용할 단어에서 처음 나오는 문자 외 반복되는 문자를 모두 삭제해 단어 키를 생성한다. 

② 윗줄에 평문 문자인 알파벳을 순서대로 쓰고, 아랫줄에 단어 키를 첫 번째 위치부터 쓴다.

③ 단어 키에 속하는 문자를 제외한 알파벳의 나머지 문자를 순서대로 써서 암호화 표를 완성한다. 

 

ex) 암호화에 사용할 단어가 PYTHON PROGRAMMING 단어키 →  PYTHONRGAMI

평문 문자

A

B

C

D

E

F

J

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

암호 문자

P

Y

T

H

O

N

R

G

A

M

I

B

C

D

E

F

J

K

L

Q

S

U

V

W

X

Z

 

(4) 숫자 키와 단어 키를 동시에 사용한 암호화

① 암호화에 사용할 단어에서 처음 나오는 문자 외 반복되는 문자를 모두 삭제해 단어 키를 생성한다.

② 윗줄에 평문 문자인 알파벳을 순서대로 쓰고, 아랫줄에 숫자 키만큼 오른쪽으로 이동해 단어키를 적는다. 

③ 단어 키에서 사용한 문자를 제외한 알파벳의 나머지 문자를 순서대로 써서 암호화 표를 완성한다. 

ex) 단어키가 PYTHONRGAMI, 숫자키가 3

평문 문자

A

B

C

D

E

F

J

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

암호 문자

W

X

Z

P

Y

T

H

O

N

R

G

A

M

I

B

C

D

E

F

J

K

L

Q

S

U

V

 

(5) 시저 암호의 한계

- 아무리 암호화 표를 복잡하게 만든다 해도 해독을 위한 단어를 제공한다. 

- 시저 암호화 방법으로는 언어적인 패턴과 단어의 중복 사용을 숨길 수 없다. 

- 암호화해도 문자만 바뀔 뿐, 암호화 패턴은 똑같다. 

 

2) 트리테미우스(Trithemius) 암호

ex) PYTHON → PZVKSS

3) 비게네르(Vigenere) 암호

① 평문에 암호화 키를 적용한다. 

② 비게네르 암호화 키를 적용한다.

ex) 

암호화 키가 7,1, 11,19일 때 PYTHON 암호화  → VYDZUN

 

4) 전치형 암호

① 문장을 쪼갤 단위를 정한다. 

② 행렬에 가로 방향으로 문장을 나열한 다음, 첫 번째 열을 시작으로 세로 방향으로 읽어 암호문을 생성한다. 

③ ②번으로 생성된 암호문을 더 해독하기 어렵게 하려면, 행렬에 암호문을 다시 나열하고, 첫 번째 열을 시작으로 세로 방향으로 읽어 암호문을 생성한다.

 

ex) LINUX PROGRAMMING LANGUAGE

LINUX PROGRAMMING LANGUAGE  →  ②의 결과 : LRMNIOIGNGNUURGAXALGPMAE

②의 결과 : LRMNIOIGNGNUURGAXALGPMAE  →  ③의 결과 : LIULRGRGMNGPNGAMINXAOUAE

 

5) 폴리비우스(Polybius) 암호

(1) 폴리비우스 암호

① 5*5행렬에 알파벳을 차례대로 나열한 암호표를 작성한다. 

② 이 암호표를 이용해 문장을 숫자 형태의 암호문으로 변현환다. 

ex) PYTHON → 35 54 44 23 34 33

 

(2) 폴리비우스 암호 응용

- 암호표를 알파벳순에 상관없이 나열하면 해독하기 어렵다.

 

---

3. 공개키 암호화 방식

1) 공개키 암호화 방식의 개념

(1) 비밀키 암호화 방식의 문제

- 비밀키 암호화 방식은 암호화키를 여러 사람이 공유하므로 유출의 가능성이 높다. 

- 임의의 사용자 c에게 암호문과 암호화키가 유츨되면 암호문이 해독되는 문제가 발생

 

(2) 공개키 암호화 방식

- 공개키를 이용해서 암호화하고 비밀키를 사용해서 복호화

- 암호문을 해독하려면 비밀키를 알아야 한다. 

- 여러 사람이 공유하는 공개키가 유출되어도 아무 문제가 없다. 

 

2) DH 비밀키 교환 방식

(1) DH 비밀키 교환 방식

- 스탠포드 대학의 디피(Diffie)와 헬만(Hellman)이 고안

- 암호화에는 공개키(public key)를, 복호화에는 그와 다른 비밀키(private key)를 이용하는 공개키 암호(PKC, public key crytography) 개념을 제안 → 구현은 하지 않았다. 

- 비밀키는 두 사용자가 동일한 키를 사용하는데, 만나지 않고도서 비밀키를 교환하여 공유할 수 있는 방식을 개발하였고, 이를 DH 비밀키 교환 방식이라고 한다. 

 

(2) DH 비밀키 교환 방식의 동작 과정

① A가 DH 비밀키 교환 방식에 필요한 값을 정하는데, 이 값 중 개인적인 값과 공개해도 좋은 값으로 나눈다. A는 B에게 공개 DH 값을 B에게 보낸다. 

② B는 전송받은 공개 DH 값과 자신만의 개인적인 값을 이용해서 새로운 DH 값과 암호화키를 만든다. B는 공개 DH값을 A에게 보낸다. 

③ A는 B에게서 받은 공개 DH 값과 개인적인 값을 이용해 암호화키를 만든다. 

④ A와 B가 주고받는 공개 DH 값이 누출되어도 제3자가 암호화키를 생성할 수 없다. 

 

(3) DH 비밀키 교환 방식의 상세 동작 과정

; (g^x1 mod p)^x2 mod p = (g^x2 mod p)^x1 mod p 라는 사실을 이용해 같은 수를 공유한다. 

(mod는 나머지 연산)

①  A는 큰 소수 p, 베이스 g, 지수 x1의 세 수를 선택한다. 

② g^x1 mod p = y1 를 적용해 y1을 생성한다. (x1는 노출하면 안 되는 개인적인 값이고, p,g,y1은 공개해도 되는 값이다.)

③  A는 p,g,y1을 B에게 보낸다. 

④ B는 자신만의 x2를 선택한다. g^x2 mod p = y2를 이용해 y2를 생성한다. 

⑤ B는 s = y1^x2  mod  p 를 이용해 비밀키인 s를 생성한다.

⑥ B는 y2를 A에게 보낸다.

⑦ A는 s = y2^x1 mod p 를 이용해 비밀키인 s를 생성한다. 

⑧ A와 B는 s라는 비밀키를 사용해 암호문을 만들고 해독한다.

 

ex)

① A가 p는 43, g는 17, x1은 4로 정함

② 17^4 mod 43 = 15 = y1

③ A는 p, g, y1을 B에게 보낸다.

④ B는 x2를 6으로 정한다. 그리고 y2를 생성한다. 17^6 mod 43 = 35 = y2

⑤ B는 15^6 mod 43 = 11 = s를 생성한다. 

⑥ B는 y2를 A에게 보낸다.

⑦ A는 35^4 mod 43 = 11을 계산해 비밀키 11를 구한다. 

 

 

3) RSA 암호화 방식

(1) RSA 암호화 방식

- 디피와 헬만의 공개키 암호화 개념을 기반으로  MIT 공대의 리베스트(Rivest), 셰미르(Shamir), 아델만(Adelman)이 공개키로 암호화하고 비밀키로 복호하는 알고리즘을 제안

 

(2) RSA 암호화 방식의 동작원리

① A는 누구에게나 공개된 B의 공개키를 이용해 보내고자 하는 메시지를 암호화한 후 B에게 암호화된 메세지를 보낸다. 

② 암호문을 받은 B는 자신의 비밀키를 이용해 암호화된 메세지를 복호화한다. 

(이때 암호문을 제3자가 가로챈다고 해도, B의 비밀키가 없으므로 암호문을 해독하지 못한다.)

 

(3) RSA 암호화 

; 상당히 큰 두 소수의 곱을 소인수분해하는 것은 어렵다는 점을 이용한다.

① 적당히 비슷하고 큰 소수 p,q를 선택한다.

② n = p * q

③ ϕ(n) = (p-1)*(q-1)

( ϕ(n)는 오일러 파이 함수)

④ 다음 조건을 만족하는 e를 선택한다. ( ϕ(n)과 최대공약수가 1이고,  ϕ(n)보다 작은 수 e를 구하는 것)

gcd(e,  ϕ(n)) = 1 , 1 < e <  ϕ(n)

⑤ 다음 조건을 만족하는 d를 구한다. (e와 곱해서 ϕ(n)로 나눈 나머지가 1이 되는 ϕ(n)보다 작은 수 d를 구하는 것)

e*d ≡ 1 (mod ϕ(n)), 1<d<ϕ(n) 

- 유클리드 호제법으로 e와 곱해서 ϕ(n)로 나눈 나머지가 1이 되는 ϕ(n)보다 작은 수 d를 구한다. & 과정을 진행하면서 수식들과 주요 숫자들을 구한다.

- 확장된 유클리드 호제법을 사용해 주요숫자 e와 ϕ(n)의 식으로 표현한다. 

- d를 구한다. 

⑥(n,e)가 공개키이고, (n,d)가 비밀키이다. p,q,ϕ(n)은 공개되지 않도록 한다. 

⑦평문 문자가 m일 때, 공개키 [n,e]를 이용해 암호 문자 c를 구하는 수식

c = m^e mod n

⑧평문 문자가 m일 때, 비밀키 [n,d]를 이용해 복호화하는 수식

m = c^d mod n

 

ex)

① p는 13, q는 11을 선택

② n = p * q → 143 = 13 *11

③ ϕ(n) = (p-1)*(q-1) → 120 = 12 * 10

④ gcd(e,  ϕ(n)) = 1 , 1 < e <  ϕ(n)를 만족하는 e를 선택한다.  →  23 선택

⑤ e*d ≡ 1 (mod ϕ(n)), 1<d<ϕ(n)를 만족하는 d를 구한다. 

- 유클리드 호제법으로 120과 23의 최대공약수를 구하는 과정을 진행하며 수식들과 주요 숫자(원래의 두 수와 나머지 위치에 등장한 수)들을 구해 놓는다. 

120 = 5 * 23 + 5 

⦁ 5 = 120 - 5*23

23 = 4 * 5 + 3

⦁ 3 = 23 - 4*5

5 = 1*3 +2

⦁ 2 = 5 - 1*3

3 = 1*2 +1

⦁ 1 = 3 - 1*2

- 확장된 유클리드 호제법을 사용해 아래와 같이 식을 진행한다. (위에서 ⦁ 뒤에 있는 식들을 이용해 표현&치환 )

1 = 3 - 1*2

   = 3 - 1*(3-1)

   = 3*(2) + 5*(-1)

   = (23 - 4*5)*2 + 5*(-1)

   = 23*2 + 5*(-9)

   = 23*2 + (120 - 5*23)*(-9)

   = 23*(47) + 120(-9)

 

결국, 1 = 23*47 + 120*(-9)이므로 23*47 = 9*120 +1이다. 

따라서 47을 23과 곱하면 120으로 나눈 나머지가 1이 된다. d = 47

⑥(n,e)가 공개키이고, (n,d)가 비밀키이다. p,q,ϕ(n)은 공개되지 않도록 한다. 

⑦ 암호화 ; 문자 'J'를 암호화함

문자 'J'의 아스키코드  값은 1001010(74)이다.

74^23 mod 143 = 94

⑧ 복호화

94^47 mod 143 = 74

 

 

(4) 디지털 서명(digital signature)- 공개키 암호화 방식을 이용한 전자서명(electronic signature)의 한 종류; 송신자의 사설키(디지털 서명의 생성키)로 문서를 암호화하고, 송신자의 공개키(디지털 서명 검증키)로 문서를 복호화- 보낸 사람이 누구인지 확인하는 인증 ; 제3자가 잘못된 메세지(가짜 메세지)를 보내는 경우에도 원하는 송신자가 아님을 알 수 있다. - 부인 방지(non-repudiation) 기능; 보냈는데 안 보냈다고 할 수 없음

 

(5) 전자봉투(digital envelope)- 전자문서는 비밀키 암호화 방식으로 암호화하고 암호화에사용된 비밀키는 공개키 암호화 방식으로 암호화하는 것