Part 1. 데이터 구조 - 4장 해시 데이터 구조

4장에서 다루는 것은 

해시 함수를 사용하여 사용하는 동작하는 해시 테이블 이다. 

특히 컴퓨터 보안의 암호화와 체크섬은 해싱에 크게 의존한다. 

 

<해시, 해시함수>

해시는 어떤 길이의 임의 데이터를 고정 길이의 데이터로 매핑하는 것이다. 

해시 함수는 이 해시를 실행하려고 하나의 값을 다른 값으로 변환하는 상자를 뜻한다. 

해시 함수 특징 :  입력되는 데이터가 무엇이든지 출력되는 해시의 값의 길이가 항상 고정되어 있다. 

일반 함수는 정의역 요소 하나에 정확히 하나의 치역 요소가 대응 되지만 해시함수는 서로다른 입력 2개가 같은 

해시값을 생성할 가능성 ( 해시 충돌 ) 이 있다. 다만 흔치않은 일이다. 

 

 

< 해시 테이블 > 

해싱 ( 해시 테이블을 이용하는 탐색) 할대 사용하며, 이때 해시 함수는 해시 테이블 데이터 구조에서 중요한 부분이다. 

 - 해시 데이블은 키와 값으로 구성된 검색 시스템 이다. 

 각 키는 값 하나와 연결되어 있으므로 키를 알면 연결된 값을 즉시 찾을 수 있다. 즉 시간 복잡도 O(1) 임

해시 테이블은 해시 함수를 사용해 검색을 수행한다. 문자열인 키를 해시 함수에 입력하면 저장을 위한 데이터 구조의 인덱스에 매핑된 해시값이 생성 된다. 즉 생성된 해시값을 사용하면 테이블에서 검색이나 추가하려는 요소가 저장된 배열의 인덱스를 계산 할 수 있다. 

 

해시 충돌의 발생을 방지하기 위해 체이닝 이라는 방식으로 해시 테이블을 구현 한다. 

체이닝은 요소를 단순한 배열이 아닌 연결 리스트( 링크드 리스트 ) 인 배열에 저장하는 방식으로, 연결 리스트가 길어졌을 때, 해시 테이블 검색의 시간 복잡도가 증가할 가능성이 있다. 

 

<컴퓨터 보안 기초>

 

스푸핑 : 누군가 다른 사람으로 행세하여 정보를 탈취하는 것. 

컴퓨터 보안의 암호 시스템은 평문 입력을 암호문 출력으로 변환하는 것. 

평문 -> 암호문 : 암호화 encryption 

암호문 -> 평문 : 복호화 decryption 

대칭키 암호 시스템 ( symmetric key) : 암호화 및 복호화에 같은 키를 사용. (문제점 : 네트워크를 통해 키를 가르챈다면 메세지를 복호화 할수 있음 ) 

공개 키 암호 시스템 : 암호화및 복호화에 서로 다른 키를 사용. 암호화에 사용 하는 키를 공개키, 복호화에 사용 하는 키를 비밀 키라고 함

 

해싱 vs 암호화

암호화는 정보를 뒤죽박죽 섞어 읽을 수 없게 만든 후, 키가 있는 사람만 정보를 사용할 수 있게 하는 과정.  (양방향 ) 

해싱은 데이터를 입력으로 받아 고정 길이의 출력 생성, 이후에는 원래의 데이터가 필요하지 않다. (단방향) 

 

<컴퓨터 보안에서 해시의 역할 >

디지털 서명 ( 디지털 데이터의 유효성을 검증하는데 사용) 

 

일반적으로 사용 하는 디지털 서명방식

두 방식 모두 디지털 서명의 보안을 보장하기 위해 해시를 사용 

RSA ( Rivest - Shanmir-Adleman) : 디지털 서명과 암호화에 모두 사용할 수 있다. / 암호화 하기전의 데이터에 해시 함수를 사용 

DSA (digital signature algorithm) : 디지털 서명의 생성 및 검증에만 사용할 수 있고 암호화에는 사용할 수 없다. / SHA  (secure hash algorithm ) 기반의 암호화 해시 함수를 사용 

 

이외에도 난수 생성, 메세지 인증 코드, 단방향 함수, 암호 기술자 전용 응용 프로그램에서도 해시를 사용한다. 

 

 

< 해시와 순환 중복 검사 > 

사물 인터넷 시대 (Internet of Things, IoT ) 로 인해 마이크로컨트롤러 내장한 임베디드 시스템이 만연, 

마이크로컨트롤러 시스템에는 해싱을 사용하여 동작하는 순환 중복 검사 (cyclic redundancy check, CRC) 모듈이 있다. 

CRC 는 디지털 데이터의 오류를 감지하는 방식으로, 해시함수의 원리를 사용하여 데이터의 유효성을 검증. 

보통 해시 함수를 통해 고정된 비트수의 체크섬을 찾아 발신할 데이터에 첨부하는 방식으로 동작.

수신 데이터의 CRC가 발신 데이터의 CRC 와 일치하지 않는다면 데이터가 손상되었을 가능성 있음. 

CRC 모듈은 이더넷과 와이파이를 통해 디지털 데이터를 전송하는 임베디드 시스템에서 널리 사용

 

 

출처 : 코드 없는 알고리즘과 데이터 구조