2022. 10. 30. 16:27ㆍ책 정리 [ 내가 다시 보기위한 ]/책[코드없는 알고리즘과 데이터 구조] 정리
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 모듈은 이더넷과 와이파이를 통해 디지털 데이터를 전송하는 임베디드 시스템에서 널리 사용
출처 : 코드 없는 알고리즘과 데이터 구조
'책 정리 [ 내가 다시 보기위한 ] > 책[코드없는 알고리즘과 데이터 구조] 정리' 카테고리의 다른 글
Part 2. 알고리즘 - 7장 정렬 알고리즘 (0) | 2022.10.30 |
---|---|
Part 2. 알고리즘 - 6장 선형 및 이진 탐색 (0) | 2022.10.30 |
Part 1. 데이터 구조 - 3장 트리 데이터 구조 (0) | 2022.10.30 |
Part 1. 데이터 구조 - 2장 선형데이터 구조 (0) | 2022.10.28 |
Part 1. 데이터 구조 - 1장 데이터 구조와 알고리즘, 자료형, 빅 오 표기법 (0) | 2022.10.28 |