書いて覚えるSwift入門

第36回ハッシュ関数の2つの

ハッシュとはぐしゃぐしゃに混ぜること

今回は、参議院予算委員会でも取り上げられたハッシュ関数(hash function)を解説します。ハッシュとは英語で「ぐしゃぐしゃに混ぜる」ことですが、なぜぐしゃぐしゃに混ぜることが現代のコンピューティングにおいて最重要な課題の1つになったのでしょうか?

まずはハッシュ関数の用途を見てみましょう。大きく2つの用途に分かれます。

  • a.データの効率的検索
  • b.データの改竄検出

無関係というより正反対に見えます。それではハッシュ関数とはどんな関数なのでしょう?

  1. あるデータを整数値に対応
  2. データが同じなら、必ず同じ数値を返す
  3. データが異なっている場合は、なるべく異なる数値を返す

これだけです。この定義どおりだとすると、

func identity<T:Numeric>(x:T)->T {
  return x
}

つまり受け取った数値をそのまま返す関数もハッシュ関数ということになります。とくに3.に関してはなるべくどころか必ず異なる数値を返すという意味で完璧です。しかし全然ハッシュしてないのにハッシュ関数とはこれいかに?

あまり混ぜない「.hashValue」

しかしこれが、言葉遊びではなく実際に使われています。もちろんSwiftでも。

SwiftにはHashableというプロトコルが用意されています。このプロトコルに準拠した型は、

var hashValue:Int

というComputed Property、つまりfunctionを必ず持っています。実際に試してみましょう。

42.hashValue // 42
Double.pi.hashValue // 4614256656552045848unsafeBitCast(Double.pi, to:Int.self) //
4614256656552045848

見てのとおり、1ビットも違わず一緒です。それが何の役に立つのか。連想配列(associative array)の実装に役立つのです。これさえあれば任意のデータ構造を作れるという意味で最も便利なこのデータ構造で、JavaScriptやPHPにいたっては連想抜きの配列さえ連想配列なのですが、その連想配列を実装する最もポピュラーな方法が、添字をハッシュ関数とする連想抜きの配列、すなわちハッシュテーブル(hash table)なのです。あまりにポピュラーなのでPerlとRubyはそれを単にハッシュ(hash)と呼んでいるのですが、筆者としては列車を全部電車と呼んでいるような違和感があります。ディーゼルカーだって蒸気機関車だってあるのに……。

それはとにかく、Swiftではこのデータ構造はPython同様Dictionaryと呼ばれています。しかしその内部実装がハッシュテーブルであることは、Hashableプロトコルが如実に示しています。

ということは、オレオレハッシュテーブルも作れるということになります。やってみましょうリスト1⁠。

リスト1 オレオレハッシュテーブル(その1)
struct NaiveHT<K:Hashable, V> {
    var table:[(K,V)?]
    init(count:Int) {
        table = [(K,V)?](repeating:nil, count:count)
    }
    func index(_ key:K) -> Int {
        return key.hashValue % table.count
    }
    subscript(key:K) -> V? {
        get {
            return table[index(key)]?.1
        }
        set {
            table[index(key)] = (key, newValue!)
        }
    }
}

名前からわかるとおり、実にナイーブな実装ですが、確かにDictionaryっぽく動いています。

var h = NaiveHT<Int,Int>(count: 3)
h[0]    // nil
h[0] = 1    // 1
h[0]    // 1

しかし、簡単に破綻します。

h[1] = 3
h[2] = 5
h[3] = 7
h[0] // 7

h[0]には1を代入したはずなのに、なぜ上書きされてしまったのでしょう? index()を見てみましょう。.hashValuetableの要素数で割っていますが、0 % 3 == 1 % 3なのでh[3] = 7で上書きされちゃったわけです。要は衝突(collision)が起きたわけです。ハッシュテーブルの実装において、最も難しいのは衝突が起きたときにどうするかですが、最もナイーブな実装としてはハッシュテーブルを作りなおすというものがあります。たとえばこんなふうにリスト2⁠。

リスト2 オレオレハッシュテーブル(その2)
    func collides(key:K)->Bool {
        if let kv = table[index(key)] {
            return kv.0 != key
        }
        return false
    }
    mutating func rehash() {
        var newHT = NaiveHT<K,V>(
            count:table.count * 2 + 1
        )
        for kv in table {
            if kv != nil {
                newHT[kv!.0] = kv!.1
            }
        }
        self = newHT
    }
    subscript(key:K) -> V? {
        get {
            return table[index(key)]?.1
        }
        set {
            if self.collides(key:key) { rehash() }
            table[index(key)] = (key, newValue!)
        }
    }

あるいははじめから衝突があり得ないぐらい大きな配列を用意しとくか。しかしそれではメモリがいくらあっても足りなくなってしまいます。しかも今回は添字がIntだからいいものの、Stringだとしたらindex()ではなく.hashValueそのものが同じ値を返すことも想定しなければなりません。Intはたかだか8バイト。それより長い文字列には必ず同じ.hashValueを返す別の文字列が存在することは鳩ノ巣原理で明らかなのですから。

幸い再発明をしなくても、Swiftには最初からDictionaryが組み込まれていますし、Hashableでなければならないのはキーだけで値はなんでもありなので、ハッシュ関数を自作する必要はあまりないでしょう。どうしても必要なときは.descriptionを実装してから.description.hashValueを返すという逃げもあります。

きちんと混ぜなければダメなダイジェスト

ハッシュテーブルで使うハッシュ関数は「あまり被らない」程度にかき混ぜればOKで、被る心配がなければかき混ぜそのものすら不要だというのは見てのとおりですが、国会でも取り上げられたもう1つの用途、つまりデータの指紋として使う場合はそうもいきません。別のデータから同じ指紋を簡単に作れたら指紋として役に立たないのですから。.hashValueはたかだか64ビットの数値ですが、⁠指紋」用のハッシュ関数がこれよりずっと大きな値を返すのは「天文学的に被らない」ようにするためにも必須と言えるでしょう。この目的ではもはや安全とは言えないMD5でも128ビットありますし、現在主流のSHA-256にいたっては256ビットもあります。32バイト、16進数表記にすれば64文字にもなる巨大数値は「数値」というよりむしろ「要約」⁠digest)というにふさわしく、⁠ハッシュ値」⁠hash value)より「ダイジェスト」と呼んだほうが良いでしょう。ダイジェスト用の関数を実装するのはハッシュテーブル用の関数を実装するよりも難しそうなことは暗号学者でなくとも想像できます。

幸いにして暗号学者たちの検証を経た、プロのお墨付きのダイジェスト関数の実装は主要OSには標準装備されていますが、Swift から使うにはちょっと工夫が必要です。方法は記事の終わりにまとめたのでそちらを参照していただくとして、実例を見てみましょう。

let 財務省が = "財務省が、"
let 財務省は = "財務省は、"
print("・"・(財務省が)・".sha256 = ", 財務省が.sha256)
print("・"・(財務省は)・".sha256 = ", 財務省は.sha256)
実行例
"財務省が、".sha256 = 7fc4759cd0ab74fb209de5201b1255aaf94d9cc32ace460974c589a481727b77
"財務省は、".sha256 = af9a6819ee4e981ab3a83e35abb9147d9859079db076995a68890294ef17d152

ダイジェスト、もといまとめ

記録改竄とその防止の歴史は、おそらく人類が文字を発明したのと同じ長さがあるでしょう。バビロニアの契約書は、契約を刻んだ粘土板にさらに粘土をかぶせて同じ文言を刻んだそうです。データは粘土板や紙といった媒体から解放されましたが、黒歴史を書き換えたい誘惑から我々が解放される日は来るのでしょうか?

その日が来るまで、我々はデータをハッシュし続けるのでしょう……。

[付録]module.mapを使ってimport CommonCryptoする方法

XcodeのターゲットであるmacOS、iOS、tvOSにはすでにCommonCryptoライブラリが搭載されているので、md5やsha256などの暗号学的ハッシュ関数を実装し直す必要はありません。ただしCライブラリなのでSwiftからそのまま使えません。

こういった場合、SwiftではBridging Headerを追加して対処していたのですが、module.mapファイルを使うとBridging HeaderなしでSwiftのFrameworkを作れます。今回はこれを利用してCommonCryptoをSwiftから使ってみることにします。

まずは新規プロジェクトを作成したあと、プロジェクトフォルダの中にCommonCryptoという名のフォルダを作成し、その中にmodule.mapファイルを作成しますリスト3⁠。

リスト3 CommonCrypto/module.map
module CommonCrypto [system] {
    header "/usr/include/CommonCrypto/CommonCrypto.h"
    export *
}

次にプロジェクト設定で[Build Setting]→[Swift Compiler - Search Paths]CommonCryptoを追加します図1⁠。

図1 プロジェクト設定
図1 プロジェクト設定

この時点でimport CommonCryptoできるようになったのですが、Cライブラリのままでは使いにくいのでリスト4のように拡張してみます。

リスト4 digest.swift
import Foundation
import CommonCrypto

public enum CryptoAlgorithm {
    case MD5, SHA1, SHA224, SHA256, SHA384, SHA512
    public var digestLength: Int {
        switch self {
        case .MD5: return Int(CC_MD5_DIGEST_LENGTH)
        case .SHA1: return Int(CC_SHA1_DIGEST_LENGTH)
        case .SHA224: return Int(CC_SHA224_DIGEST_LENGTH)
        case .SHA256: return Int(CC_SHA256_DIGEST_LENGTH)
        case .SHA384: return Int(CC_SHA384_DIGEST_LENGTH)
        case .SHA512: return Int(CC_SHA512_DIGEST_LENGTH)
        }
    }
    public func rawDigest(data: UnsafeRawPointer!, length:Int) -> [CUnsignedChar] {
        let clen = CC_LONG(length)
        var result = [CUnsignedChar](repeating: 0, count: self.digestLength)
        switch self {
        case .MD5: CC_MD5(data, clen, &result)
        case .SHA1: CC_SHA1(data, clen, &result)
        case .SHA224: CC_SHA224(data, clen, &result)
        case .SHA256: CC_SHA256(data, clen, &result)
        case .SHA384: CC_SHA384(data, clen, &result)
        case .SHA512: CC_SHA512(data, clen, &result)
        }
        return result
    }
    public func hexDigest(data: UnsafeRawPointer!, length:Int) -> String {
        return self.rawDigest(data:data, length:length)
            .map{ String(format:"%02hhx", $0) }.joined()
    }
}
extension String {
    public func hexDigest(algorithm: CryptoAlgorithm) -> String {
        guard let cstr = self.cString(using: String.Encoding.utf8) else {
            fatalError("UTF-8 conversion failed!")
        }
        return algorithm.hexDigest(data: cstr, length: cstr.count - 1)
    }
    public var md5: String { return self.hexDigest(algorithm: .MD5) }
    public var sha1: String { return self.hexDigest(algorithm: .SHA1) }
    public var sha224: String { return self.hexDigest(algorithm: .SHA224) }
    public var sha256: String { return self.hexDigest(algorithm: .SHA256) }
    public var sha384: String { return self.hexDigest(algorithm: .SHA384) }
    public var sha512: String { return self.hexDigest(algorithm: .SHA512) }
}

これで"Hello, World!".sha256のようにしてハッシュ値を取れるようになりました。やってみましょう。

main.swiftの実行例
let str = "Hello, World!"
print(str)
print(str.md5)
print(str.sha256)

なお、リスト5のようなMakefileを用意すればREPLでも使えるようになります図2⁠。

リスト5 Makefile
MOD=CryptoDigest
BIN=main
MODSRC=$(MOD)/digest.swift
BINSRC=$(MOD)/main.swift
MODULE=$(MOD).swiftmodule
DOC=$(MOD).swiftdoc
SWIFTC=swiftc
SWIFTCFLAGS=-O -ICommonCrypto
SWIFT=swift
ifdef SWIFTPATH
        SWIFTC=$(SWIFTPATH)/swiftc
        SWIFT=$(SWIFTPATH)/swift
endif
OS := $(shell uname)
ifeq ($(OS),Darwin)
        SWIFTC=xcrun -sdk macosx swiftc
endif
COMPILE=$(SWIFTC) $(SWIFTCFLAGS)

all: $(BIN)
module: $(MODULE)
clean:

        -rm $(BIN) $(MODULE) $(DOC) lib$(MOD).*
$(BIN): $(BINSRC) $(MODSRC)
        $(COMPILE) $(MODSRC) $(BINSRC)
$(MODULE): $(MODSRC)
        $(COMPILE) -emit-library -emit-module
$(MODSRC) -module-name $(MOD)
repl: $(MODULE)
        $(SWIFT) -I. -L. -ICommonCrypto
-lCommonCrypto -l$(MOD)
図2 REPLでの実行例
% make repl
xcrun -sdk macosx swiftc -O -ICommonCrypto
-emit-library -emit-module CryptoDigest/digest.swift -module-name CryptoDigest
swift -I. -L. -ICommonCrypto -lCommonCrypto
-lCryptoDigest
Welcome to Apple Swift version 4.0.3
(swiftlang-900.0.74.1 clang-900.0.39.2). Type
:help for assistance.
  1> import CryptoDigest
  2> "Hello, World!"
$R0: String = "Hello, World!"
  3> "Hello, World!".md5
$R1: String = "65a8e27d8879283831b664bd8b7f0ad4"
  4> "Hello, World!".sha256
$R2: String = "dffd6021bb2bd5b0af676290809ec3a53191dd81c7f70a4b28688a362182986f"
  5>
Software Design

本誌最新号をチェック!
Software Design 2022年9月号

2022年8月18日発売
B5判/192ページ
定価1,342円
(本体1,220円+税10%)

  • 第1特集
    MySQL アプリ開発者の必修5科目
    不意なトラブルに困らないためのRDB基礎知識
  • 第2特集
    「知りたい」⁠使いたい」⁠発信したい」をかなえる
    OSSソースコードリーディングのススメ
  • 特別企画
    企業のシステムを支えるOSとエコシステムの全貌
    [特別企画]Red Hat Enterprise Linux 9最新ガイド
  • 短期連載
    今さら聞けないSSH
    [前編]リモートログインとコマンドの実行
  • 短期連載
    MySQLで学ぶ文字コード
    [最終回]文字コードのハマりどころTips集
  • 短期連載
    新生「Ansible」徹底解説
    [4]Playbookの実行環境(基礎編)

おすすめ記事

記事・ニュース一覧