SHA系のハッシュ関数を実装してみる事にする。SHAにはいくつかの種類が存在しており、初期のものから脆弱性が発見され、それに対応するように強化されてきた歴史がある。詳しくはWikipediaにまとめられている。
SHA-0
160ビットのハッシュ値を返す。SHA-0はSHAの初期バージョンである。SHAに問題が発見されたため、SHA-1が策定された。SHA-1と区別するために、SHA-0と呼ぶ事が多い。
SHA-0には脆弱性が存在する事が分かっているため使用するべきではなく、そのためSHA-0を実装しているコードは少ない。
SHA-1
SHA-0で発見された問題を解消するために策定された。SHA-0同様160ビットのハッシュ値を返す。動きを把握するためCで実装した。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#define ROTL(x, n) (((x) << (n)) | ((x) >> (32 - (n))))
int main() {
const char *message = "Hello, World!";
// -----------------------------------------------
// メッセージをパディングする
// -----------------------------------------------
uint8_t *padded_message;
size_t padded_len;
size_t message_len = strlen(message);
printf("%s\n", message);
printf("%d\n", (int)message_len);
// パディング後の長さを計算
padded_len = ((message_len + 8) + 63) & ~63;
padded_message = (uint8_t *)malloc(padded_len);
if (padded_message == NULL) {
perror("Failed to allocate memory");
exit(1);
}
memcpy(padded_message, message, message_len); // メッセージをコピー
padded_message[message_len] = 0x80; // パディング開始位
memset(padded_message + message_len + 1, 0, padded_len - message_len - 8); // 0埋め
// メッセージ長をビッグエンディアンで追加
uint64_t bit_len = (uint64_t)message_len * 8;
padded_message[padded_len - 8] = (bit_len >> 56) & 0xFF;
padded_message[padded_len - 7] = (bit_len >> 48) & 0xFF;
padded_message[padded_len - 6] = (bit_len >> 40) & 0xFF;
padded_message[padded_len - 5] = (bit_len >> 32) & 0xFF;
padded_message[padded_len - 4] = (bit_len >> 24) & 0xFF;
padded_message[padded_len - 3] = (bit_len >> 16) & 0xFF;
padded_message[padded_len - 2] = (bit_len >> 8) & 0xFF;
padded_message[padded_len - 1] = bit_len & 0xFF;
// -----------------------------------------------
// ハッシュ値を計算する
// -----------------------------------------------
// 初期値
uint32_t h0 = 0x67452301;
uint32_t h1 = 0xEFCDAB89;
uint32_t h2 = 0x98BADCFE;
uint32_t h3 = 0x10325476;
uint32_t h4 = 0xC3D2E1F0;
// ハッシュ計算
uint32_t a, b, c, d, e;
uint32_t f, k, temp;
uint32_t *w = (uint32_t *)padded_message;
for (size_t i = 0; i < padded_len; i += 64) { // 64はブロックサイズ
a = h0;
b = h1;
c = h2;
d = h3;
e = h4;
for (int t = 0; t < 80; t++) {
if (t < 20) {
f = (b & c) | ((~b) & d);
k = 0x5A827999;
} else if (t < 40) {
f = b ^ c ^ d;
k = 0x6ED9EBA1;
} else if (t < 60) {
f = (b & c) | (b & d) | (c & d);
k = 0x8F1BBCDC;
} else {
f = b ^ c ^ d;
k = 0xCA62C1D6;
}
temp = ROTL(a, 5) + f + e + k + w[t];
e = d;
d = c;
c = ROTL(b, 30);
b = a;
a = temp;
}
h0 += a;
h1 += b;
h2 += c;
h3 += d;
h4 += e;
}
free(padded_message);
// ダイジェストを設定
uint32_t digest[5];
digest[0] = h0;
digest[1] = h1;
digest[2] = h2;
digest[3] = h3;
digest[4] = h4;
unsigned char *v = (unsigned char *)digest;
printf("0a0a9f2a6772942557ab5355d76af442f8f65e01\n");
printf("0a0a9f2a6772942557ab5355d76af442f8f65e01\n");
printf("ae4ce89b86eb7de904ff2bb0fba88e122b0a430b\n");
// for (int p; p<strlen(v); p++){
// printf("%x", v[p]);
// }
printf("%08x%08x%08x%08x%08x\n",
digest[0], digest[1], digest[g2], digest[3], digest[4]);
return 0;
}SHA-1を実装するユーティリティは様々存在する。例えばPythonの標準モジュールである hashlib では hashlib.sha1 が提供されており、これを用いて次のようにハッシュ値を計算できる。
import hashlib
h = hashlib.sha1()
h.update(b"Hello, World!")
return h.hexdigest()0a0a9f2a6772942557ab5355d76af442f8f65e01
ただし現在ではSHA-1にも脆弱性がある事が確認されている。