LoginSignup
0
0
@ikiuo

MD5: RFC 1321 を実装してみる

Last updated at Posted at 2021-08-06

RFC 1321 (The MD5 Message-Digest Algorithm) を見ながら実装してみた。

以下を念頭に置いています

  • ビット単位の入力は考慮しない
  • コンパクトなものにする
  • 凝ったことはあまりしない

データの種類

データのバイト列は、リトル・エンディアンとして扱います。

種類 ビット数 バイト数 ワード数 シンボル
ワード 32 4 1
ブロック 512 64 16 X[ ]
ダイジェスト値 128 16 4 S[ ] または A,B,C,D
ダイジェスト値 A,B,C,D は配列 S と等しいものとします。
例:C++
uint32_t &A = S[0];
uint32_t &B = S[1];
uint32_t &C = S[2];
uint32_t &D = S[3];

入力データと入力の拡張

入力データの後続に、入力の拡張として、「1ビットの"1"」と「入力のビット数」が追加されます。また、ダイジェスト値の計算は、ブロック単位で行われるので、全体がブロック単位となるように "0" で埋めます。

追加されるバイト列データの並びは以下になります。

バイト数 データ
1 0x80
0 〜 55 0x00
8 入力のビット数（64ビット）

ブロック単位の計算

1ブロックに対して、64要素のテーブルを使って計算します。テーブルは

C
T[i] = int(abs(sin(i)) * 4294967296);  /* i はラジアンで 1 から 64 */

とされています。i が 1 からだと都合が悪いので、実際のプログラムでは

C
T[i] = int(abs(sin(i+1)) * 4294967296);  /* i は 0 から 63 */

にします。T に対して、4種類の関数と16ワードで、計64回の計算を実行します。

4種類の関数は

関数 計算
F(x, y, z) (y & x) | (z & ~x)
G(x, y, z) (x & z) | (y & ~z)
H(x, y, z) x ^ y ^ z
I(x, y, z) y ^ (x | ~z)

となっていて、F,G,H,I を総じて Q とします。

これと、32ビット左ローテート(大抵のCPUでは1命令)

C
uint32_t RotateLeft(uint32_t v, int n)
{
  return (v << n) | (v >> (32 - n));
}

が使われます。

ダイジェスト値の初期値

ダイジェスト値 A,B,C,D の初期値は

A = 0x67452301
B = 0xefcdab89
C = 0x98badcfe
D = 0x10325476

となっています。

ダイジェスト値の更新

テーブル T[i] の i を 0 から順に 63 まで使って、ダイジェスト値の更新します。

一回の計算は

Round
// a,b,c,d,k,s および Q は i に応じて決められている
// S[a],S[b],S[c],S[d] は A,B,C,D をシャッフルしたものに相当
S[a] = S[b] + RotateLeft(X[k] + T[i] + S[a] + Q(S[b], S[c], S[d]), s)

として更新されます。

T[i] と各要素の対応

i と Q,a,b,c,d,k,s の対応表（長いので折りたたみ）
i Q a b c d k s
0 F 0 1 2 3 0 7
1 F 3 0 1 2 1 12
2 F 2 3 0 1 2 17
3 F 1 2 3 0 3 22
4 F 0 1 2 3 4 7
5 F 3 0 1 2 5 12
6 F 2 3 0 1 6 17
7 F 1 2 3 0 7 22
8 F 0 1 2 3 8 7
9 F 3 0 1 2 9 12
10 F 2 3 0 1 10 17
11 F 1 2 3 0 11 22
12 F 0 1 2 3 12 7
13 F 3 0 1 2 13 12
14 F 2 3 0 1 14 17
15 F 1 2 3 0 15 22
16 G 0 1 2 3 1 5
17 G 3 0 1 2 6 9
18 G 2 3 0 1 11 14
19 G 1 2 3 0 0 20
20 G 0 1 2 3 5 5
21 G 3 0 1 2 10 9
22 G 2 3 0 1 15 14
23 G 1 2 3 0 4 20
24 G 0 1 2 3 9 5
25 G 3 0 1 2 14 9
26 G 2 3 0 1 3 14
27 G 1 2 3 0 8 20
28 G 0 1 2 3 13 5
29 G 3 0 1 2 2 9
30 G 2 3 0 1 7 14
31 G 1 2 3 0 12 20
32 H 0 1 2 3 5 4
33 H 3 0 1 2 8 11
34 H 2 3 0 1 11 16
35 H 1 2 3 0 14 23
36 H 0 1 2 3 1 4
37 H 3 0 1 2 4 11
38 H 2 3 0 1 7 16
39 H 1 2 3 0 10 23
40 H 0 1 2 3 13 4
41 H 3 0 1 2 0 11
42 H 2 3 0 1 3 16
43 H 1 2 3 0 6 23
44 H 0 1 2 3 9 4
45 H 3 0 1 2 12 11
46 H 2 3 0 1 15 16
47 H 1 2 3 0 2 23
48 I 0 1 2 3 0 6
49 I 3 0 1 2 7 10
50 I 2 3 0 1 14 15
51 I 1 2 3 0 5 21
52 I 0 1 2 3 12 6
53 I 3 0 1 2 3 10
54 I 2 3 0 1 10 15
55 I 1 2 3 0 1 21
56 I 0 1 2 3 8 6
57 I 3 0 1 2 15 10
58 I 2 3 0 1 6 15
59 I 1 2 3 0 13 21
60 I 0 1 2 3 4 6
61 I 3 0 1 2 11 10
62 I 2 3 0 1 2 15
63 I 1 2 3 0 9 21

i と Q（関数）の対応

i の範囲 i >> 4 Q
00 〜 15 0 F
16 〜 31 1 G
32 〜 47 2 H
48 〜 63 3 I

i と a,b,c,d（ダイジェスト値）の対応

i a b c d 備考
4n+0 0 1 2 3 a = 0 % 4
4n+1 3 0 1 2 a = 3 % 4
4n+2 2 3 0 1 a = 6 % 4
4n+3 1 2 3 0 a = 9 % 4

i と k（ブロック）の対応

i 0 1 2 3 4 5 6 7
0x00 0 1 2 3 4 5 6 7
0x10 1 6 11 0 5 10 15 4
0x20 5 8 11 14 1 4 7 10
0x30 0 7 14 5 12 3 10 1
i 8 9 A B C D E F
0x00 8 9 10 11 12 13 14 15
0x10 9 14 3 8 13 2 7 12
0x20 13 0 3 6 9 12 15 2
0x30 8 15 6 13 4 11 2 9

i の範囲 k
0x00 〜 0x0f ((i * 1) + 0) % 16
0x10 〜 0x1f ((i * 5) + 1) % 16
0x20 〜 0x2f ((i * 3) + 5) % 16
0x30 〜 0x3f ((i * 7) + 0) % 16

i と s（ローテート ビット数）の対応

i 0 1 2 3 4 5 6 7
0x00 7 12 17 22 7 12 17 22
0x10 5 9 14 20 5 9 14 20
0x20 4 11 16 23 4 11 16 23
0x30 6 10 15 21 6 10 15 21
i 8 9 A B C D E F
0x00 7 12 17 22 7 12 17 22
0x10 5 9 14 20 5 9 14 20
0x20 4 11 16 23 4 11 16 23
0x30 6 10 15 21 6 10 15 21

横の 4 以降は、0〜3の繰り返しなので

i 0 1 2 3
0x00 7 12 17 22
0x10 5 9 14 20
0x20 4 11 16 23
0x30 6 10 15 21

に注目します。これを

i 0 1 2 3
0x00 4+(5*0)+0+3 4+(5*1)+0+3 4+(5*2)+0+3 4+(5*3)+1+2
0x10 4+(5*0)+0+1 4+(5*1)+0+0 4+(5*2)+0+0 4+(5*3)+1+0
0x20 4+(5*0)+0+0 4+(5*1)+0+2 4+(5*2)+0+2 4+(5*3)+1+3
0x30 4+(5*0)+0+2 4+(5*1)+0+1 4+(5*2)+0+1 4+(5*3)+1+1

に分解すると、最後の加算値は

i 0 1 2 3
0x00 3 3 3 2
0x10 1 0 0 0
0x20 0 2 2 3
0x30 2 1 1 1

となるので、2ビット値にして逆順にすると

i 3 2 1 0 2進数 16進数
0x30 1 1 1 2 01_01_01_10 56
0x20 3 2 2 0 11_10_10_00 e8
0x10 0 0 0 1 00_00_00_01 01
0x00 2 3 3 3 10_11_11_11 bf

2ビット×16 の参照テーブル（0x56e801bf）が出来上がります。

プログラム

C++版
//
// ヘッダ用
//

#include <cstddef>
#include <cstdint>

/*
 * MD5ByteSum
 */

class MD5ByteSum
{
public:
    typedef uint32_t State[4];
    typedef uint32_t Block[16];
    typedef uint8_t Digest[16];
    typedef char HexDigest[33];

protected:
    static const uint8_t padding[64];

    State state;
    uint32_t bytes;
    Block input;
    bool active;

public:
    MD5ByteSum();
    MD5ByteSum(const void *message, size_t size);

    void digest(Digest &out);
    void hexdigest(HexDigest &out);

    void initialize();
    void update(const void *message, size_t size);
    void finalize();

protected:
    void update_state();
};

/*
 * MD5ByteSum - inline
 */

inline MD5ByteSum::MD5ByteSum()
{
    initialize();
}

//
// コンパイル用
//

/*
 * MD5ByteSum::State - update 16-Word block
 */

inline static uint32_t ROL(uint32_t x, int s)
{
    return ((x << s) | (x >> (32 - s)));
}

inline static uint32_t get_block_index(uint32_t index)
{
    /*
     * [y|y|x|x|x|x]
     *  (index * 1 + 0) & 15
     *  (index * 5 + 1) & 15
     *  (index * 3 + 5) & 15
     *  (index * 7 + 0) & 15
     */
    uint32_t x = index & 0x0f;
    uint32_t y = index & 0x30;
    uint32_t y1 = index & 0x10;
    uint32_t y2 = index & 0x20;
    uint32_t xmul = (y1 >> 2) | (y2 >> 4) | 1;
    uint32_t offs = (0x0510 >> (y >> 2)) & 7;
    return (x * xmul + offs) & 15;
}

inline static int get_rotate_bits(uint32_t index)
{
    /*
     * [y|y|.|.|x|x]
     *  7 12 17 22 : 3 8 13 18 : 3 3 3 3 : 3 3 3 2
     *  5  9 14 20 : 1 5 10 16 : 1 0 0 1 : 1 0 0 0
     *  4 11 16 23 : 0 7 12 19 : 0 2 2 4 : 0 2 2 3
     *  6 10 15 21 : 2 6 11 17 : 2 1 1 2 : 2 1 1 1
     *              -4          -(x*5)    -(x==3)
     *
     *  11 11 11 10 : 10_11_11_11 = bf
     *  01 00 00 00 : 00_00_00_01 = 01
     *  00 10 10 11 : 11_10_10_00 = e8
     *  10 01 01 01 : 01_01_01_10 = 56
     */
    uint32_t x = index & 0x03;
    uint32_t y = index & 0x30;
    uint32_t p = x | (y >> 2);
    uint32_t x0 = (0x56e801bf >> (p << 1)) & 3;
    uint32_t x3 = (x + 1) >> 2; // (x == 3) ? 1 : 0;
    uint32_t x5 = x * 5;
    return x0 + x3 + x5 + 4;
}

inline static uint32_t get_state_index(uint32_t index, uint32_t element)
{
    /*
     *  0 1 2 3
     *  3 0 1 2
     *  2 3 0 1
     *  1 2 3 0
     */
    return ((index * 3) + element) & 3;
}

inline static uint32_t md5bs_state_func(uint32_t index, uint32_t x, uint32_t y, uint32_t z)
{
    switch ((index >> 4) & 3)
    {
    case 0: return (y & x) | (z & ~x);
    case 1: return (x & z) | (y & ~z);
    case 2: return x ^ y ^ z;
    case 3: return y ^ (x | ~z);
    }
    return 0;
}

inline static void md5bs_state_update(uint32_t index, uint32_t *S, const MD5ByteSum::Block &X, uint32_t T)
{
    uint32_t a = get_state_index(index, 0);
    uint32_t b = get_state_index(index, 1);
    uint32_t c = get_state_index(index, 2);
    uint32_t d = get_state_index(index, 3);
    uint32_t x = get_block_index(index);
    uint32_t r = get_rotate_bits(index);

    S[a] = S[b] + ROL(X[x] + T + S[a] + md5bs_state_func(index, S[b], S[c], S[d]), r);
}

inline static void md5bs_state_update(uint32_t index, uint32_t *S,
                                      const MD5ByteSum::Block &X,
                                      uint32_t T1, uint32_t T2,
                                      uint32_t T3, uint32_t T4)
{
    md5bs_state_update(index + 0, S, X, T1);
    md5bs_state_update(index + 1, S, X, T2);
    md5bs_state_update(index + 2, S, X, T3);
    md5bs_state_update(index + 3, S, X, T4);
}

void MD5ByteSum::update_state()
{
    State p;

    p[0] = state[0];
    p[1] = state[1];
    p[2] = state[2];
    p[3] = state[3];

    // Round 1.
    md5bs_state_update( 0 * 4, state, input, 0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee);
    md5bs_state_update( 1 * 4, state, input, 0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501);
    md5bs_state_update( 2 * 4, state, input, 0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be);
    md5bs_state_update( 3 * 4, state, input, 0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821);

    // Round 2.
    md5bs_state_update( 4 * 4, state, input, 0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa);
    md5bs_state_update( 5 * 4, state, input, 0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8);
    md5bs_state_update( 6 * 4, state, input, 0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed);
    md5bs_state_update( 7 * 4, state, input, 0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a);

    // Round 3.
    md5bs_state_update( 8 * 4, state, input, 0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c);
    md5bs_state_update( 9 * 4, state, input, 0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70);
    md5bs_state_update(10 * 4, state, input, 0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x04881d05);
    md5bs_state_update(11 * 4, state, input, 0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665);

    // Round 4.
    md5bs_state_update(12 * 4, state, input, 0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039);
    md5bs_state_update(13 * 4, state, input, 0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1);
    md5bs_state_update(14 * 4, state, input, 0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1);
    md5bs_state_update(15 * 4, state, input, 0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391);

    state[0] += p[0];
    state[1] += p[1];
    state[2] += p[2];
    state[3] += p[3];
}

/*
 * MD5ByteSum
 */

const uint8_t MD5ByteSum::padding[64] = { 0x80 };

MD5ByteSum::MD5ByteSum(const void *message, size_t size)
{
    initialize();
    update(message, size);
    // finalize();
}

void MD5ByteSum::initialize()
{
    state[0] = 0x67452301;
    state[1] = 0xefcdab89;
    state[2] = 0x98badcfe;
    state[3] = 0x10325476;
    bytes = 0;
    for (int i = 0; i < 16; i++)
        input[i] = 0;
    active = true;
}

void MD5ByteSum::finalize()
{
    if (!active)
        return;

    uint32_t l = bytes;
    uint32_t i = l & 0x3f;
    uint32_t n = ((i >= 56) ? 64 : 0) + 56 - i;

    update(padding, n);

    input[14] = l << 3;
    input[15] = l >> 29;
    update_state();

    active = false;
}

void MD5ByteSum::update(const void *message, size_t size)
{
    if (!active)
        initialize();

    const uint8_t *d = reinterpret_cast<const uint8_t *>(message);
    unsigned b = (bytes & 3) << 3;
    unsigned i = (bytes >> 2) & 0x0f;

    bytes += size;
    while (size-- > 0)
    {
        input[i] |= (*d++) << b;

        b = (b + 8) & 0x1f;
        if (b == 0)
        {
            i = (i + 1) & 0x0f;
            if (i == 0)
                update_state();
            input[i] = 0;
        }
    }
}

void MD5ByteSum::digest(Digest &out)
{
    finalize();

    for (int p = 0; p < 4; p++)
    {
        uint32_t s = state[p];

        for (int q = 0; q < 4; q++, s >>= 8)
            out[p * 4 + q] = uint8_t(s);
    }
}

void MD5ByteSum::hexdigest(HexDigest &out)
{
    finalize();

    for (int p = 0; p < 4; p++)
    {
        uint32_t s = state[p];

        for (unsigned q = 0; q < 4; q++, s >>= 8)
        {
            char h = (s >> 4) & 0x0f;
            char l = (s >> 0) & 0x0f;
            out[p * 8 + q * 2 + 0] = h + ((h < 10) ? '0' : ('a' - 10));
            out[p * 8 + q * 2 + 1] = l + ((l < 10) ? '0' : ('a' - 10));
        }
    }
    out[32] = 0;
}

//
// テスト用
//

#include <cstdio>
#include <cstring>

int main(int argc, char **argv)
{
    const char *program = argv[0];

    if (argc != 2)
    {
        printf("usage: %s message\n", program);
        return 1;
    }

    const char *message = argv[1];

    MD5ByteSum md5(message, strlen(message));
    MD5ByteSum::HexDigest res;
    md5.hexdigest(res);
    printf("MD5 (\"%s\") = %s\n", message, res);
    return 0;
}

頭の体操として python/swift でも作ってみた。python では hashlib を、 swift では CommonCrypto を使った方がよいです。

Python版
#!/usr/bin/env python3

import math


def md5s(msg, encoding='utf-8'):
    if type(msg) in (bytes, bytearray):
        inp = bytearray(msg)
    elif type(msg) == str:
        inp = bytearray(msg, encoding)
    else:
        raise Exception('unknown type: %s' % type(msg))

    U32M = 0xffffffff
    def rotate(x, r): return (((U32M >> r) & x) << r) | ((U32M & x) >> (32 - r))
    def round1(a, b, c, d, x, t, r): return U32M & (b + rotate(x + t + a + ((b & c) | (d & (U32M - b))), r))
    def round2(a, b, c, d, x, t, r): return U32M & (b + rotate(x + t + a + ((b & d) | (c & (U32M - d))), r))
    def round3(a, b, c, d, x, t, r): return U32M & (b + rotate(x + t + a + (b ^ c ^ d), r))
    def round4(a, b, c, d, x, t, r): return U32M & (b + rotate(x + t + a + (c ^ (b | (U32M - d))), r))

    dsz = len(inp)
    bsz = dsz << 3
    pos = dsz & 0x3f
    psz = ((pos + 8) & 0x40) + 56 - pos
    inp += bytearray([0x80] + [0] * (psz - 1))
    inp += bytearray([(bsz >> b) & 0xff for b in range(0, 64, 8)])
    inp = tuple([inp[i] + (inp[i + 1] << 8) + (inp[i + 2] << 16) + (inp[i + 3] << 24) for i in range(0, len(inp), 4)])

    Sn = ((0, 1, 2, 3), (3, 0, 1, 2), (2, 3, 0, 1), (1, 2, 3, 0)) * 16
    Fn = (round1, round2, round3, round4)
    X1 = (0, 1, 2, 3) * 4 + (1, 6, 11, 0) * 4 + (13, 0, 3, 6) * 4 + (0, 7, 14, 5) * 4
    X4 = (0, 4, 8, 12) * 2 + (8, 4, 0, 12) + (0, 12, 8, 4)
    T = tuple([int(abs(math.sin(i + 1)) * 0x100000000) for i in range(64)])
    Rn = (7, 12, 17, 22) * 4 + (5, 9, 14, 20) * 4 + (4, 11, 16, 23) * 4 + (6, 10, 15, 21) * 4
    Z = tuple([(Sn[i], Fn[i >> 4], (X1[i] + X4[i >> 2]) & 0x0f, T[i], Rn[i]) for i in range(64)])

    S = [0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476]
    for X in range(0, len(inp), 16):
        ss = S * 1
        for ((a, b, c, d), f, x, t, r) in Z:
            S[a] = f(S[a], S[b], S[c], S[d], inp[X + x], t, r)
        for i in range(4):
            S[i] = U32M & (S[i] + ss[i])

    return bytes([(s >> b) & 0xff for s in S for b in range(0, 32, 8)])


# Test

sample = (
    ('', 'd41d8cd98f00b204e9800998ecf8427e'),
    ('a', '0cc175b9c0f1b6a831c399e269772661'),
    ('abc', '900150983cd24fb0d6963f7d28e17f72'),
    ('message digest', 'f96b697d7cb7938d525a2f31aaf161d0'),
    ('abcdefghijklmnopqrstuvwxyz', 'c3fcd3d76192e4007dfb496cca67e13b'),
    ('ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789', 'd174ab98d277d9f5a5611c2c9f419d9f'),
    ('12345678901234567890123456789012345678901234567890123456789012345678901234567890', '57edf4a22be3c955ac49da2e2107b67a'),
)

for (message, digest) in sample:
    res = md5s(message)
    if res.hex() != digest:
        raise Exception('message "%s":\n   %s != %s' % (message, digest, res.hex()))
    print('MD5 ("%s") = %s' % (message, res.hex()))
Python（縦短横長）版

Sn, X1, X4, Rn は Z 中の計算で求めるようにするなどして、改行を減らして短くなったように見えるもの。

#!/usr/bin/env python3

import math


def md5s(msg, encoding='utf-8'):
    if type(msg) in (bytes, bytearray):
        inp = bytearray(msg)
    elif type(msg) == str:
        inp = bytearray(msg, encoding)
    else:
        raise Exception('unknown type: %s' % type(msg))

    psz = (((len(inp) & 0x3f) + 8) & 0x40) + 56 - (len(inp) & 0x3f)
    inp += bytearray([0x80] + [0] * (psz - 1)) + bytearray([((len(inp) << 3) >> b) & 0xff for b in range(0, 64, 8)])
    inp = tuple([inp[i] + (inp[i + 1] << 8) + (inp[i + 2] << 16) + (inp[i + 3] << 24) for i in range(0, len(inp), 4)])

    Z = tuple([(tuple([(i * 3 + j) & 3 for j in range(4)]), (lambda x, y, z: (x & y) | (z & (0xffffffff - x)), lambda x, y, z: (x & z) | (y & (0xffffffff - z)), lambda x, y, z: x ^ y ^ z, lambda x, y, z: y ^ (x | (0xffffffff - z)))[i >> 4], ((((i >> 2) & 4) | ((i >> 4) & 2) | 1) * (i & 15) + ((0x0510 >> ((i >> 2) & 12)) & 15)) & 15, int(abs(math.sin(i + 1)) * 0x100000000), ((0x56e801bf >> ((((i >> 2) & 12) | (i & 3)) << 1)) & 3) + (((i & 3) + 1) >> 2) + ((i & 3) * 5) + 4) for i in range(64)])

    S = [0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476]
    for X in range(0, len(inp), 16):
        ss = S * 1
        for ((a, b, c, d), f, x, t, r) in Z:
            S[a] = 0xffffffff & (S[b] + (lambda x, r: (((0xffffffff >> r) & x) << r) | ((0xffffffff & x) >> (32 - r)))(inp[X + x] + t + S[a] + f(S[b], S[c], S[d]), r))
        for i in range(4):
            S[i] = 0xffffffff & (S[i] + ss[i])
    return bytes([(s >> b) & 0xff for s in S for b in range(0, 32, 8)])


# Test

sample = (
    ('', 'd41d8cd98f00b204e9800998ecf8427e'),
    ('a', '0cc175b9c0f1b6a831c399e269772661'),
    ('abc', '900150983cd24fb0d6963f7d28e17f72'),
    ('message digest', 'f96b697d7cb7938d525a2f31aaf161d0'),
    ('abcdefghijklmnopqrstuvwxyz', 'c3fcd3d76192e4007dfb496cca67e13b'),
    ('ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789', 'd174ab98d277d9f5a5611c2c9f419d9f'),
    ('12345678901234567890123456789012345678901234567890123456789012345678901234567890', '57edf4a22be3c955ac49da2e2107b67a'),
)

for (message, digest) in sample:
    res = md5s(message)
    if res.hex() != digest:
        raise Exception('message "%s":\n   %s != %s' % (message, digest, res.hex()))
    print('MD5 ("%s") = %s' % (message, res.hex()))
Swift版

Xcode 12.5.1 での Console アプリとして作っています。

main.swift
import Foundation

// ############

infix operator <<<
func <<< (x: UInt32, s: Int) -> UInt32 {
    return (x &<< s) | (x >> (32 - s))
}

extension Data {
    func ToArrayU8() -> [UInt8] {
        return [UInt8](unsafeUninitializedCapacity: count)
        { buffer, initializedCount in
            copyBytes(to: buffer, from: 0..<count)
            initializedCount = count
        }
    }
}

class MD5ByteSum {
    static let Rmap: [[Int]] = [
        [ 7, 12, 17, 22 ],
        [ 5,  9, 14, 20 ],
        [ 4, 11, 16, 23 ],
        [ 6, 10, 15, 21 ],
    ]
    static let Smap: [[Int]] = [
        [ 0, 1, 2, 3 ],
        [ 3, 0, 1, 2 ],
        [ 2, 3, 0, 1 ],
        [ 1, 2, 3, 0 ],
    ]
    static let T: [UInt32] = [UInt32](unsafeUninitializedCapacity: 64)
    { buffer, initializedCount in
        for i in 0..<64 {
            let t = abs(sin(Double(i + 1))) * 4294967296
            buffer[i] = UInt32(UInt64(t) & 0xffffffff)
        }
        initializedCount = 64
    }
    static let state0: [UInt32] = [0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476]
    var state: [UInt32] = MD5ByteSum.state0
    var count: UInt32 = 0
    var input: [UInt32] = Array(repeating: 0, count: 16)
    var close = false
    init() {}
    init(_ message: [UInt8]) {
        update(message)
    }
    init(_ message: String) {
        update(Data(message.utf8).ToArrayU8())
    }
    func fini() {
        if !close {
            let bytes = count
            let i = Int(bytes & 0x3f)
            let n = ((i >= 56) ? 64 : 0) + 56 - i;
            update([0x80])
            if n > 1 {
                update(Array(repeating: 0, count: n - 1))
            }
            input[14] = bytes &<< 3
            input[15] = bytes >> 29
            update_state()
        }
        close = true
    }
    func clear() {
        state = MD5ByteSum.state0
        count = 0
        input[0] = 0
        close = false
    }
    func update(_ message: String) {
        update(Data(message.utf8).ToArrayU8())
    }
    func update(_ message: [UInt8]) {
        if close {
            clear()
        }
        var b = Int((count & 3) << 3)
        var i = Int((count >> 2) & 0x0f)
        count += UInt32(message.count)
        for d in message {
            input[i] |= UInt32(d) << b
            b = (b + 8) & 0x1f
            if b == 0 {
                i = (i + 1) & 0x0f
                if i == 0 {
                    update_state()
                }
                input[i] = 0
            }
        }
    }
    func update_state() {
        let p = state
        update_digest()
        for n in 0..<4 {
            state[n] &+= p[n]
        }
    }
    func update_digest() {
        var k: Int

        // Round 1.
        let R1 = MD5ByteSum.Rmap[0]
        for i in 0..<16 {
            let S = MD5ByteSum.Smap[i & 3]
            let a = S[0], A = state[a]
            let b = S[1], B = state[b]
            let c = S[2], C = state[c]
            let d = S[3], D = state[d]
            k = i
            state[a] = B &+ ((A &+ ((C & B) | (D & ~B)) &+ MD5ByteSum.T[i] &+ input[k]) <<< R1[i & 3])
        }

        // Round 2.
        k = 1
        let R2 = MD5ByteSum.Rmap[1]
        for i in 16..<32 {
            let S = MD5ByteSum.Smap[i & 3]
            let a = S[0], A = state[a]
            let b = S[1], B = state[b]
            let c = S[2], C = state[c]
            let d = S[3], D = state[d]
            state[a] = B &+ ((A &+ ((B & D) | (C & ~D)) &+ MD5ByteSum.T[i] &+ input[k]) <<< R2[i & 3])
            k = (k + 5) & 0x0f
        }

        // Round 3.
        k = 5
        let R3 = MD5ByteSum.Rmap[2]
        for i in 32..<48 {
            let S = MD5ByteSum.Smap[i & 3]
            let a = S[0], A = state[a]
            let b = S[1], B = state[b]
            let c = S[2], C = state[c]
            let d = S[3], D = state[d]
            state[a] = B &+ ((A &+ (B ^ C ^ D) &+ MD5ByteSum.T[i] &+ input[k]) <<< R3[i & 3])
            k = (k + 3) & 0x0f
        }

        // Round 4.
        k = 0
        let R4 = MD5ByteSum.Rmap[3]
        for i in 48..<64 {
            let S = MD5ByteSum.Smap[i & 3]
            let a = S[0], A = state[a]
            let b = S[1], B = state[b]
            let c = S[2], C = state[c]
            let d = S[3], D = state[d]
            state[a] = B &+ ((A &+ (C ^ (B | ~D)) &+ MD5ByteSum.T[i] &+ input[k]) <<< R4[i & 3])
            k = (k + 7) & 0x0f
        }
    }
    func digest() -> [UInt8] {
        fini()
        return [UInt8](unsafeUninitializedCapacity: 16)
        { buffer, initializedCount in
            for i in 0..<4 {
                for j in 0..<4 {
                    buffer[i * 4 + j] = UInt8((state[i] >> (j << 3)) & 0xff)
                }
            }
            initializedCount = 16
        }
    }
    func hexdigest() -> String {
        var s = ""
        for c in digest() {
            s += String(format: "%02x", c)
        }
        return s
    }
}

// ############

func test() {
    let sample: [[String]] = [
        [ "d41d8cd98f00b204e9800998ecf8427e", "" ],
        [ "0cc175b9c0f1b6a831c399e269772661", "a" ],
        [ "900150983cd24fb0d6963f7d28e17f72", "abc" ],
        [ "f96b697d7cb7938d525a2f31aaf161d0", "message digest" ],
        [ "c3fcd3d76192e4007dfb496cca67e13b", "abcdefghijklmnopqrstuvwxyz" ],
        [ "d174ab98d277d9f5a5611c2c9f419d9f", "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789" ],
        [ "57edf4a22be3c955ac49da2e2107b67a", "12345678901234567890123456789012345678901234567890123456789012345678901234567890" ],
    ]
    for t in sample {
        let md5 = MD5ByteSum(t[1])
        let res = md5.hexdigest()
        if res != t[0] {
            print("Message: \"\(t[1])\"")
            print("  Error: \(t[0]) != \(res)")
            exit(1)
        }
        print("MD5 (\"\(t[1])\") = \(res)")
    }
}
test()
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0