7-2. 비대칭 암호화 및 해시

목표

1. 비대칭 암호화 방식을 이해함

2. 해시 암호화 방식을 이해함

3. 데이터베이스 해시를 이해함

 

비대칭 암호화

등장 배경

- 대칭 암호화 방식으로는 암호화 키 교환의 문제를 해결할 수 없었으며, 이를 위해 비대칭 암호화 방식이 연구됨

 

디피 & 헬만

- 1974년부터 암호 전달 문제를 연구

- 1975년 디피가 '비대칭 키' 개념을 떠올림

 

비대칭 키의 개념

예시)

 

- 공개된 정보는 3

- 같은 키를 공유하기 위해 철수는 자신이 정한 숫자인 5를 사용해 3**5인 243이라는 수를 영희에게 보냄

- 영희도 자신의 숫자를 7로 정하고, 3**7인 2178을 철수에게 보냄

 

- 철수와 영희는 상대에게 받은 수에 자신의 수를 제곱

- 둘은 자신이 정한 숫자를 상대방에게 전달하지 않고도 같은 키를 공유하게 됨

  (철수 : (3**7)**5 | 영희 : (3**5)**7)

 

- 암호화와 복호화에 서로 다른 키를 사용함

 

RSA (Rivest, Sharmir, Adleman) 알고리즘

: 중요 정보를 두 개의 소수로 표현한 후, 그것의 곱을 힌트와 함께 전송하여 암호로 사용할 수 있다는 아이디어

 

- 1977년 MIT의 로널드 리베스트, 아디 샤미르, 레오나르도 애들먼이 고안

 

- 모든 사람이 고유한 N의 값을 갖게 됨. N은 두 소수의 곱

 

예시) 영희가 자신의 N을 p=17159, q=10247의 곱인 175828273으로 정함

p와 q는 영희의 사설키

영희가 자신의 N 값을 모든 사람들에게 공개한다면 N은 영희의 공개키.

영희에게 메시지를 보내고 싶은 사람은 N값을 찾아 알고리즘을 통해 암호화하여 영희에게 보냄.

 

- RSA 공개 당시 p와 q의 값을 찾아보라고 N의 값을 제시하였으나, 잡지에 실린지 17년만인 1994년에 600명의 지원자로 이루어진 팀이 두 수를 발견

 

- 현재 사용되는 250 RSA 암호는 복호화하는데 우주의 나이만큼 걸림 (대략 138억년)

 

비대칭 키를 이용한 기밀성 확보

: 수신자의 공개키로 암호화하여 송신

 

- 철수는 전화번호부에서 전화번호를 찾듯, 영희의 공개키(Public Key)를 얻어 이를 이용해 편지를 암호화하여 보냄

- 영희는 자신이 가진 사설키(Private Key) 를 이용하여 철수의 편지를 복호화하여 읽음

 

공개키 : 공유하여 함께 사용하고자 하는 키

사설키 : 개인이 보유하고 있는 키

 

비대칭 키를 이용한 부인 방지 확보

: 발신자의 사설키로 암호화하여 송신

 

- 부인 방지 : 행위나 이벤트의 발생을 증명하여 부인할 수 없도록 하는 것

 

- 철수는 영희에게 편지를 보낼 때 자신의 사설키로 편지를 암호화하여 전송

- 철수의 사설키로 암호화된 편지는 철수의 공개키로만 열 수 있으므로 영희는 그 편지가 철수가 쓴 것임을 확신할 수 있음

 

해시 (Hash)

: 하나의 문자열을 그것을 상징하는 더 짧은 길이의 값이나 키로 변환하는 것

 

- 다음 이미지의 세 평문은 길이가 다르지만 해시 결과는 32개의 문자로 길이가 모두 같음

- 둘째와 셋째 평문은 단어 하나만 다를 뿐인데 해시 결과가 완전히 다름.

  (해시값으로 해시되기 전의 값을 추측하는 것이 불가능함)

 

 

데이터베이스에서의 해시

- 해시를 통해 0010이라는 라벨 값을 부여받아 해당 철수의 데이터로 직접 접근할 수 있음. 이렇게 구현된 데이터베이스 탐색 로직은 모든 참조값에 대하여 데이터를 반환함.

- 시간이 균일하고 순차 탐색보다 속도가 훨씬 빠름

 

보안에서의 해시

- 무결성(Integrity) 확인을 위한 알고리즘으로 사용.

- 무결성은 넓은 의미로 허가된 사람들에게만 정보가 개방되고, 그들에 의해서만 수정될 수 있음을 보장하는 것

 

해시 알고리즘의 종류

MD (Message Digest function 95) 5

- 32개의 16진수로 이루어짐

- 16**32 ~ 3.4 E+38 개의 결과값이 존재할 수 있음.

- 무한의 결과값은 아니지만 사실상 무한에 가까움

- 다른 데이터를 입력한다고 하지만 결과 값이 같을 가능성이 있는데, 이를 충돌(Collision)이라고 함. 충돌이 자주 일어나는 해시는 좋은 해시가 아님.

 

- MD2, MD4, MD5의 세 가지가 있음

- 미국 MIT의 로널드 리베스트 교수가 RSA와 함께 공개키 기반 구조(Public Key Instrastructure)를 만들기 위해 개발

- 1989년에 만들어진 MD2는 8비트 컴퓨터에 최적화, 1990년의 MD4와 1991년의 MD5는 32비트 컴퓨터에 최적화

- MD5는 MD4의 확장판으로, 속도가 빠르지는 않지만 데이터 보안성에 있어서 더 많은 확신을 제공함.

 

예시)

1. md5.txt 생성

 

>>> md5 md5.txt

2. md5.txt 파일에 대한 해시 생성 (같은 해시 결과값)

 

SHA (Secure Hash Algorithm)

- 160 비트의 값을 생성하는 해시 함수. MD4가 발전한 형태이며 MD5보다 조금 느리지만 좀 더 안전함.

- 입력하는 데이터는 512비트 크기의 블록이며, 크게 SHA-1과 SHA-2로 나눌 수 있음.

  (SHA-256, 384, 512는 SHA-2에 속함)

 

- 미국 NSA(미 국가 안보국)에 의해 만들어짐

 

알고리즘 동작 이미지에서 f는 계속 변하는 비선형 함수, W와 K는 상수

 

SHA-1과 SHA-2의 성능 비교

알고리즘	메시지 문자 크기	블록 크기	해시 결과값 길이	해시 강도
SHA-1	< 2**64	512 비트	160 비트	0.625
SHA-256	< 2**64	512 비트	256 비트	1
SHA-384	< 2**128	1024 비트	384 비트	1.5
SHA-512	< 2**128	1024 비트	512 비트	2