해시함수
유일한 식별값을 만드는 함수
해시맵을 통해 대상을 찾기 위한 키값으로 사용된다
수학적 정의
- 적은 비용: 어떤 입력 x 에 대해 hash(x)를 계산하기 쉬워야 함.
- 일방향(단방향)성: hash(x)=y 에서 x 값을 찾기 어려워야 한다.
- 약한 충돌 방지: hash(a)=hash(b) 이면서 a 와 다른 b 를 찾기 어려워야 한다.
존 스미스와 산드라 디의 해시값이 02로 동일한 문제가 발생한다. - 강한 충돌 방지: hash(a)=hash(b) 이면서 a!=b 인 a 와 b 를 찾기 어려워야 한다.
비암호학적 해시
암호학적 해시함수보다 덜 안전해서
안전하지 않아도 되는 곳에서 많이 사용한다
예시: XOR연산을 사용하는 CRC(Cyclic Redundancy Check) 체크섬
체크섬을 통해 원본 데이터를 보장한다.
XOR은 다르면 참을 리턴한다
패킷전송에서 봤던 개념같다
암호학적 해시
MD5(Message-Digest), SHA-1(Secure Hash Alogorithm)은 보안상 안전하지 못하다고 해서 SHA-2를 많이 사용한다(SHA-256이 많이 익숙하당)
MD5는 128bit를 사용하는데 출력값은 16진수(4비트가 1자리)로 표현되므로 32자리의 출력값을 갖는다
출력값의 길이가 같기 때문에
입력값을 압축하는 효과가 있기도 한데 이 때문에 충돌Collision이 발생하고, 무작위 입력 공격에 취약하다
깃에서 ssh키를 생성할 때 사용했던 기억이 난다.
ssh-keygen -t rsa -b 4096 -C
현재 SSL/TLS에 가장 많이 사용되는 공개키 암호화 알고리즘이다. 현재 나무위키도 HTTPS에 RSA-2048 인증서를 사용하고 있으며, 전세계 대부분의 인터넷 뱅킹(대한민국 포함)이 이 RSA-2048 암호화를 사용한다.
암호화
데이터 전송에 필요한 암호호와 복호화
대칭키 암호화
암호화와 복호화에 같은 키를 사용한다
DES(Data Encryption Standard), AES(Andvanced Ecryption Standard)
대칭키 통신은 대칭키가 노출될 수 있다
비대칭키 암호화(공개키+개인키)
암호화에 공개키를 복호화에 비밀키를 사용한다
RSA는 암호화에 비밀키를 사용하고 복호화에 공개키를 사용하기 때문에 전자서명에 사용할 수 있다
서버에서 공개키를 공유하고(복호화) 유저들이 비밀키를 사용하면서(암호화) 서버만 데이터를 볼 수 있게 설정한다
비대칭키 통신은 속도가 느리다
대칭키+공개키
SSL(Secure Sockets Layer) 암호화방식
대칭키+공개키 방식에 인증기관이 더해져 공개키의 유효성을 검토하는 과정을 추가한 것이다
SSL 인증서 파일 종류로 .pem, .crt, .cer, .csr, .der, .pfx, .p12, .key, .jks 등의 형태가 있다
SSL은 보안상 결함이 있어 사실상 사용하는 것은 TLS방식이다
HTTP + SSL -> HTTPS: 웹에 ssl소켓을 달면 https
FTP + SSL -> SFTP: 파일전송에 ssl소켓을 달면 sftp
스위프트의 해시테이블
시간복잡도 O(1)
Dictionary타입으로 정의되어 있고
Hashable프로토콜을 따라야 한다
modulo(mod) 모듈러 연산 %: 나머지 구하는 거
25 % 7 = 4
+-----+
| 0 |
+-----+ +----------------------------+
| 1 |---> | hobbies: Programming Swift |
+-----+ +----------------------------+
| 2 |
+-----+ +------------------+ +----------------+
| 3 |---> | firstName: Steve |---> | lastName: Jobs |
+-----+ +------------------+ +----------------+
| 4 |
+-----+
hashTable["firstName"] = "Steve"
hashTable["hobbies"] = "Programming Swift"
print("firstName".hashValue) //-4799450059917011053
//"firstName"(키)은 Hashable하다
//array size로 mod한 값이 index가 된다
//예시에서 array의 사이즈가 5이므로 "firstName"의 인덱스는 abs(-4799450059917011053) % 5 = 3 이 된다.
let x = hashTable["lastName"] //충돌Collision발생
//3번 bucket에 연결리스트로 chain을 만든다
//3번 bucket에 접근한 후 선형탐색을 한번 더 실행하게 된다Hashable이라는 말은
Dictionary자료구조에서 (key-value)
key값이 index를 가질 수 있다는 말인건가
Hashable...Hashable... 대충 알 거 같다
-
장점
평균 시간복잡도가 O(1)으로
입력, 삭제, 검색이 모두 일반적인 배열보다 빠르다 -
단점
충돌이 발생하고 chain이 많아지면 속도가 느려지고
공간복잡도가 커진다
서브스크립트 (Subscripts)
클래스, 구조체 그리고 열거형에서 스크립트를 정의해 사용할 수 있습니다.
콜렉션, 리스트, 시퀀스 등 집합의 특정 멤버 엘리먼트에 간단하게 접근할 수 있는 문법
someArray[index]
someDictionary[key]
getter, setter 방식을 따른다
public struct HashTable<Key: Hashable, Value> {
private typealias Element = (key: Key, value: Value)
private typealias Bucket = [Element]
private var buckets: [Bucket] //chain
private(set) public var count = 0
public var isEmpty: Bool { return count==0 }
public init(capacity: Int) {
assert(capacity>0)
buckets = Array<Bucket>(repeating: [], count: capacity)
}
private func index(forKey key: Key) -> Int {
return abs(key.hashValue % buckets.count)
}
//subscript에 있는 value, updateValue, removeValue구현하기
public func value(forKey key: Key) -> Value? {
let index = self.index(forKey: key) // 내장함수 .index(forkey: )
for element in buckets[index] {
if element.key == key {
return element.value
}
}
return nil //key not in hash table
}
public mutating func updateValue(_ value: Value, forKey key: Key) -> Value? {
let index = self.index(forKey: key)
// Do we already have this key in the bucket?
for (i, element) in buckets[index].enumerated() {
if element.key == key {
let oldValue = element.value
buckets[index][i].value = value
return oldValue
}
}
// This key isn't in the bucket yet; add it to the chain.
buckets[index].append((key: key, value: value))
count += 1
return nil
}
public mutating func removeValue(forKey key: Key) -> Value? {
let index = self.index(forKey: key)
//Find the element in the bucket's chain and remove it
for (i, element) in buckets[index].enumerated() {
if element.key == key {
buckets[index].remove(at: i)
count -= 1
return element.value
}
}
return nil //key not in hash table
}
public subscript(key: Key) -> Value? {
get {
return value(forKey: key)
}
set {
if let value = newValue {
updateValue(value, forKey: key)
} else {
removeValue(forKey: key)
}
}
}
}
var hashTable = HashTable<String, String>(capacity: 5)
hashTable["firstName"] = "Steve"//insert
let x = hashTable["firstName"] //lookup
hashTable["firstName"] = "Tim" //update
hashTable["firstName"] = nil //remove