ハッシュとはぐしゃぐしゃに混ぜること
今回は、
まずはハッシュ関数の用途を見てみましょう。大きく2つの用途に分かれます。
- a.データの効率的検索
- b.データの改竄検出
無関係というより正反対に見えます。それではハッシュ関数とはどんな関数なのでしょう？
- あるデータを整数値に対応
- データが同じなら、
必ず同じ数値を返す - データが異なっている場合は、
なるべく異なる数値を返す
これだけです。この定義どおりだとすると、
func identity<T:Numeric>(x:T)->T {
return x
}つまり受け取った数値をそのまま返す関数もハッシュ関数ということになります。とくに3.に関してはなるべくどころか必ず異なる数値を返すという意味で完璧です。しかし全然ハッシュしてないのにハッシュ関数とはこれいかに？
あまり混ぜない「.hashValue」
しかしこれが、
SwiftにはHashableというプロトコルが用意されています。このプロトコルに準拠した型は、
var hashValue:IntというComputed Property、
42.hashValue // 42 Double.pi.hashValue // 4614256656552045848unsafeBitCast(Double.pi, to:Int.self) // 4614256656552045848
見てのとおり、
それはとにかく、Dictionaryと呼ばれています。しかしその内部実装がハッシュテーブルであることは、Hashableプロトコルが如実に示しています。
ということは、
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()を見てみましょう。.hashValueをtableの要素数で割っていますが、0 % 3 == 1 % 3なのでh[3] = 7で上書きされちゃったわけです。要は衝突
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を返す別の文字列が存在することは鳩ノ巣原理で明らかなのですから。
幸い再発明をしなくても、Dictionaryが組み込まれていますし、Hashableでなければならないのはキーだけで値はなんでもありなので、.descriptionを実装してから.description.を返すという逃げもあります。
きちんと混ぜなければダメなダイジェスト
ハッシュテーブルで使うハッシュ関数は.hashValueはたかだか64ビットの数値ですが、
幸いにして暗号学者たちの検証を経た、
let 財務省が = "財務省が、"
let 財務省は = "財務省は、"
print("･"･(財務省が)･".sha256 = ", 財務省が.sha256)
print("･"･(財務省は)･".sha256 = ", 財務省は.sha256)"財務省が、".sha256 = 7fc4759cd0ab74fb209de5201b1255aaf94d9cc32ace460974c589a481727b77 "財務省は、".sha256 = af9a6819ee4e981ab3a83e35abb9147d9859079db076995a68890294ef17d152
ダイジェスト、もといまとめ
記録改竄とその防止の歴史は、 その日が来るまで、 XcodeのターゲットであるmacOS、 こういった場合、 まずは新規プロジェクトを作成したあと、 次にプロジェクト設定で この時点で これで なお、 2022年8月18日発売［付録］
CommonCryptoライブラリが搭載されているので、module.ファイルを使うとBridging HeaderなしでSwiftのFrameworkを作れます。今回はこれを利用してCommonCryptoをSwiftから使ってみることにします。CommonCryptoという名のフォルダを作成し、module.ファイルを作成しますmodule CommonCrypto [system] {
header "/usr/include/CommonCrypto/CommonCrypto.h"
export *
}[Build Setting]→[Swift Compiler - Search Paths]にCommonCryptoを追加します
import CommonCryptoできるようになったのですが、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のようにしてハッシュ値を取れるようになりました。やってみましょう。let str = "Hello, World!"
print(str)
print(str.md5)
print(str.sha256)
Makefileを用意すればREPLでも使えるようになります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)% 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 2022年9月号
B5判／
定価1,342円
MySQL アプリ開発者の必修5科目
不意なトラブルに困らないためのRDB基礎知識
OSSソースコードリーディングのススメ
企業のシステムを支えるOSとエコシステムの全貌
今さら聞けないSSH
MySQLで学ぶ文字コード
新生