[알고리즘]Hash (알고리즘,암호에서의 해쉬) 책한권분량리포트

소개글

해시에 대해 조사한 내용이며 암호에 관련된 해시 함수 까지 다루고 있다

목차

Part Ⅰ

1 해싱(Hashing)이란 무엇인가?

2. 해싱(Hashing)의 필요성

3. 해싱 알고리즘 (Hashing Algorithm)
3.1 완전 해싱 (Perfect Hashing)
3.2 정형 해싱 (Conventional Hashing)
3.3 동적 해싱 (Dynamic Hashing)

4. 해시함수 (Hash Function)
4.1 좋은 해쉬함수
4.2 해쉬함수의 몇 가지 예

5. 정형 해싱 (Conventional Hashing)
5.1 나눗셈법 (Division)
5.2 중간 제곱법 (Mid Square)
5.3 폴딩법 (Folding)
5.4 기수 변환법 (Radix-Exchange)
5.5 자릿수 분석법 (Digit-Analysis)
5.6 무작위 방법 (Pseudo-Random)

6. 충돌해결전략(Collision Resolution Strategy)

7. Open Addressing
7.1 선형 검색법 (Linear Probing)
7.2 2차 검색법 (Qudratic Probing)
7.3 무작위 검색법 (Random Probing)
7.4 Double Hashing
7.5 비교(Comparing linear probing and random)

8. Closed Addressing
8.1 해시 체이닝 (Hash Chaining)
8.2 Chaining with Coalescing Lists
8.3 Chanining with Separate Overflow Area
8.4 Using Buckets

9. 동적 해슁 (Dynamic Hashing)
9.1 확장 해슁 (Extendible Hashing)
9.2 동적 해슁의 장단점
9.2.1 장점
9.2.2 단점

10. External Searching
10.1 Chaining with Separate Lists
10.2 Open Addressing

11. 해슁(Hashing)과 데이터베이스(Database)

12. Sorce Code
12.1 C
12.2 Java

Part Ⅱ
1. 암호학에서의 해쉬함수란?
2. 해쉬 함수의 정의 및 분류
3. 해쉬 함수의 응용
3.1 데이터 무결성 (Data integrity)
3.2 메시지 인증 (Massage authentication)

4. 해쉬 함수의 안전성
5. 해쉬 함수의 설계 방법
5.1 패딩(padding)
5.2 초기치()
6. 해쉬 함수의 종류
6.1 블록 암호 알고리즘을 이용한 해쉬 함수
6.1.1 Single-length MDCs
6.1.2 Double-length MDCs
6.2 전용 해쉬 함수
6.3 모듈러 연산을 이용한 해쉬 함수
7. 다양한 Hash Algorithm
7.1 소개(Intorduction)
7.1.1 블록암호 알고리즘
7.1.2 전용해쉬 알고리즘
7.2 해쉬함수(Hash fuction)
7.2.1 Notation and Preliminaries
7.2.2 Definitions
7.2.3 해쉬함수의 형태(Type of Hash Functions)
7.2.3.1 Hash Functions Based on Block Ciphers
7.2.3.2 Hash Functions Based on Modular Arithmetic
7.2.3.3 Hash Functions Based on Cellular Automaton
7.2.3.4 Hash Functions Based on KnapsackProblem
7.2.3.5 Hash Functions Based on Algebraic Matrices
7.2.3.6 Dedicated Hash Functions
7.3 실제 해쉬가 사용되는 보안 알고리즘
7.3.1 MD2
7.3.2 MD4
7.3.3 MD5
7.3.4 SHA
7.3.5 HAVAL
8. Methods of Attack on Hash Functions
8.1. General <font color=aaaaff<font color=aaaaff>..</font>

본문내용

해슁(hashing)이란 한마디로 말해서 많은 양의 데이터(data)들을 그보다는 작은 크기의 테이블(table)로 대응(mapping)시켜 저장할 수 있도록 하는 일종의 데이터 관리 기법이다. 데이터들을 저장하거나 찾을 때 인덱스(index)라는 또다른 데이터 스트럭쳐(data structure)를 이용하는 대신, 각 데이터들이 테이블의 어느 영역에 위치할 것인가를 결정해주는 해쉬함수(hash function)를 사용하여 일정한 시간 내에 데이터들을 효과적으로 찾을 수 있도록 해주는 것이 바로 해슁이다. 따라서 데이터들은 순차적으로 저장되는 것이 아니라 테이블 전 영역에 걸쳐서 고루 분포하게 되며, 저장된 데이터를 찾을 때에도 해쉬함수를 사용하면 곧바로 그 위치를 알 수가 있기 때문에 빠르게 데이터를 검색할 수가 있게 된다.
그러나 해슁은 그 기본 개념으로 인하여 매우 치명적인 약점을 지니고 있는데, 해쉬함수가 이상적(ideal)이지 않은 이상 서로 다른 키(key)들이 테이블의 같은 위치로 결정될 소지가 다분하다는 것이 바로 그것이다. 이런 현상을 충돌(collision)이라 하며, 따라서 해슁에서는 이 충돌을 어떻게 해결할 것인가가 매우 커다란 이슈(issue)가 된다. 결국 해슁 알고리즘(hashing algorithm)은 해쉬함수와 충돌해결전략(collision resolution strategy)으로 나뉘게 된다.

참고 자료

References

[1] Mark Allen Weiss, Data Structure and Algorithm Analysis in C, The Benjamin/Cummings Publishing Company, 1993.
[2] Henry F.Korth and Abraham Silberschatz, Database System Concept, McGraw-Hill Book Company, 1986.
[3] Fred R.McFadden and Jeffrey A.Hoffer, Database Management, The Benjamin/Cummings Publishing Company, 1985.
[4] Jean-Paul Tremblay and Paul G.Sorenson, An Introduction to Datastructures with Application, McGraw-Hill Book Company, 1984.
[5] William J.Collins, Data Structures - An Object Oriented Approach, Addison-Wesley Publishing Company, 1992.
[6] Donald E.Knuth, Sorting and Searching, Addison-Wesley Publishing Company, 1973.
[7] AAron M.Tenenbaum and Moshe J.Augenstein, Data Structures Using Pascal, Prentice-Hall International, 1986.
[8] R.Kenneth Walter, Introduction to Data Management & File Design, Prentice-Hall, Englewood Cliffs, New Jersey, 1986.
[9] 양근호, 권유종, 김용하, Hashing, CS421 REPORT 자료, 1996.
[10] Tables and Hashing, http://orange.mcs.dundee.ac.uk:8080/CS202/notes/mosaic/chap11.htm
[11] The Wonderful World of Hashing, http://sparky.elec.uq.oz.au/people/eddy/hash.html
[12] 정보통신단체표준 TTAS.KO-12.0011/R1. 해쉬함수표준-제2부 해쉬함수알고리즘표준(HAS-160) (HASH FUNCTION STANDARD PART 2 : HASH FUNCTION ALGORITHM STANDARD(HAS-160))
[12] S.Bakhtiari and R. Safavi-Naini and J.Pieprzyk. Cryptographic Hash Functions : A Survey
[13] Stephen Prata , Artificial Life Playhouse
http://www.aistudy.co.kr/branch/alife/concept_prata.htm#_bookmark_2497d30
[14] CryptoClub , http://www.cipher.or.kr/faq.htm#5
[15] B.S. Kaliski. The MD2 Message-Digest Algorithm. RFC 1319, Aprial 1992. Network Working Group, RSA Laboratories.

[16] R.L. Rivest. The MD4 Messag-Digest Algorithm. RFC 1320, April 1992. Network Working Group, MIT Laboratory for Computer Science and RSA Data Security, Inc.
[17] R.L. Rivest. The MD5 Message-Digest Algorithm. RFC 1321, April 1992. Network Working Group, MIT Laboratory for Computer Science and RSA Data Security, Inc.
[18] RSA Security FAQ, http://www.rsasecurity.com/rsalabs/faq/3-6-6.html
[19] 최용랑외3인, 컴퓨터통신보안 (번역본)
[20] B. Preneel. Analysis and Design of Cryptographic Hash Functions. PhD thesis, Katholieke University Leuven, January 1993.