ハッシュ関数

ユニークな識別値を作成する関数
ハッシュ・マッピングによるターゲットのキー値の検索

数学の定義

は低コストです.hash(x)は、任意の入力xに対して計算が容易でなければなりません.

一方向性:hash(x)=yではx値を見つけるのは難しいはずです.

弱い衝突防止:hash(a)=hash(b)ですが、aと他のbを見つけるのは難しいです.

ジョン・スミスとサンドラディのハッシュ値は02で、同じ問題が発生した.

強防衝突:hash(a)=hash(b)、同時にa!=b人aとbは見つけにくいはずです.

非暗号ハッシュ

暗号学のハッシュ関数よりも安全ではありません.
安全でない場所に多く使われる
例:XOR演算を使用したサイクル冗長チェックサム
元のデータを検証して保証します.
XORが違うと斬り返す
パケット転送で見られる概念のようです.

パスワードハッシュ

MD 5(Message-Digest)、SHA-1(セキュリティハッシュアルゴリズム)はセキュリティ上安全ではないため、SHA-2(SHA-256はよく知られている)を用いる
MD 5は128ビットを使用し、出力値は16進数(4ビットは1ビット)で32ビットの出力値を持つ
出力値の長さは同じです.
入力値を圧縮する効果もあるため、衝突衝突が発生し、ランダム入力攻撃を受けやすい
羽毛に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)暗号化方法

対称鍵+公開鍵方式に認証機構を加え,公開鍵の有効性を調べる.

SSL証明書ファイルタイプ.pem, .crt, .cer, .csr, .der, .pfx, .p12, .key, .jksなどの形態がある
SSLはセキュリティ上の欠陥があり、実際にTLS方式を使用しています
HTTPS+SSL->HTTPS:WebにSSLソケットをインストールする際にhttpsを使用
FTP+SSL->SFTP:ファイル転送中にsslスロットを追加した場合、sftp

sweetのハッシュテーブル

時間複雑度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)
入力、削除、検索は一般的な配列よりも速い

短所
衝突が発生すると、チェーンが多ければ多いほど速度が遅くなります.
スペース複雑度の増大

サブスクリプト

スクリプトは、クラス、構造、列挙で定義および使用できます.
集合、リスト、シーケンスなど、集合内の特定のメンバー・セグメントにアクセスするための簡単な構文です.
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