LINUX.ORG.RU

Помoгите с md5

 ,


0

1

Пытаюсь написать реализацию md5 согласно RFC:

//Note: All variables are unsigned 32 bit and wrap modulo 2^32 when calculating
var int[64] s, K

//s specifies the per-round shift amounts
s[ 0..15] := { 7, 12, 17, 22,  7, 12, 17, 22,  7, 12, 17, 22,  7, 12, 17, 22 }
s[16..31] := { 5,  9, 14, 20,  5,  9, 14, 20,  5,  9, 14, 20,  5,  9, 14, 20 }
s[32..47] := { 4, 11, 16, 23,  4, 11, 16, 23,  4, 11, 16, 23,  4, 11, 16, 23 }
s[48..63] := { 6, 10, 15, 21,  6, 10, 15, 21,  6, 10, 15, 21,  6, 10, 15, 21 }

//Use binary integer part of the sines of integers (Radians) as constants:
for i from 0 to 63
    K[i] := floor(232 × abs(sin(i + 1)))
end for
//(Or just use the following precomputed table):
K[ 0.. 3] := { 0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee }
K[ 4.. 7] := { 0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501 }
K[ 8..11] := { 0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be }
K[12..15] := { 0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821 }
K[16..19] := { 0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa }
K[20..23] := { 0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8 }
K[24..27] := { 0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed }
K[28..31] := { 0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a }
K[32..35] := { 0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c }
K[36..39] := { 0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70 }
K[40..43] := { 0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x04881d05 }
K[44..47] := { 0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665 }
K[48..51] := { 0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039 }
K[52..55] := { 0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1 }
K[56..59] := { 0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1 }
K[60..63] := { 0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391 }

//Initialize variables:
var int a0 := 0x67452301   //A
var int b0 := 0xefcdab89   //B
var int c0 := 0x98badcfe   //C
var int d0 := 0x10325476   //D

//Pre-processing: adding a single 1 bit
append "1" bit to message    
/* Notice: the input bytes are considered as bits strings,
  where the first bit is the most significant bit of the byte.[46]
  

//Pre-processing: padding with zeros
append "0" bit until message length in bits ≡ 448 (mod 512)
append original length in bits mod (2 pow 64) to message


//Process the message in successive 512-bit chunks:
for each 512-bit chunk of message
    break chunk into sixteen 32-bit words M[j], 0 ≤ j ≤ 15
//Initialize hash value for this chunk:
    var int A := a0
    var int B := b0
    var int C := c0
    var int D := d0
//Main loop:
    for i from 0 to 63
        if 0 ≤ i ≤ 15 then
            F := (B and C) or ((not B) and D)
            g := i
        else if 16 ≤ i ≤ 31
            F := (D and B) or ((not D) and C)
            g := (5×i + 1) mod 16
        else if 32 ≤ i ≤ 47
            F := B xor C xor D
            g := (3×i + 5) mod 16
        else if 48 ≤ i ≤ 63
            F := C xor (B or (not D))
            g := (7×i) mod 16
        dTemp := D
        D := C
        C := B
        B := B + leftrotate((A + F + K[i] + M[g]), s[i])
        A := dTemp
    end for
//Add this chunk's hash to result so far:
    a0 := a0 + A
    b0 := b0 + B
    c0 := c0 + C
    d0 := d0 + D
end for

var char digest[16] := a0 append b0 append c0 append d0 //(Output is in little-endian)

//leftrotate function definition
leftrotate (x, c)
    return (x << c) binary or (x >> (32-c));

Мой вариант (сначала хочу для пустого сообщения, так что на вход идет `memset(data, 0, 64)`):

typedef struct
{
    UInt32 abcd[4];
} md5_t;

static const UInt8 md5_shifts[64] = {
    7, 12, 17, 22,  7, 12, 17, 22,  7, 12, 17, 22,  7, 12, 17, 22,
    5,  9, 14, 20,  5,  9, 14, 20,  5,  9, 14, 20,  5,  9, 14, 20,
    4, 11, 16, 23,  4, 11, 16, 23,  4, 11, 16, 23,  4, 11, 16, 23,
    6, 10, 15, 21,  6, 10, 15, 21,  6, 10, 15, 21,  6, 10, 15, 21
};

static const UInt32 md5_sins[64] = {
    0xD76AA478U, 0xE8C7B756U, 0x242070DBU, 0xC1BDCEEEU,
    0xF57C0FAFU, 0x4787C62AU, 0xA8304613U, 0xFD469501U,
    0x698098D8U, 0x8B44F7AFU, 0xFFFF5BB1U, 0x895CD7BEU,
    0x6B901122U, 0xFD987193U, 0xA679438EU, 0x49B40821U,
    0xF61E2562U, 0xC040B340U, 0x265E5A51U, 0xE9B6C7AAU,
    0xD62F105DU, 0x02441453U, 0xD8A1E681U, 0xE7D3FBC8U,
    0x21E1CDE6U, 0xC33707D6U, 0xF4D50D87U, 0x455A14EDU,
    0xA9E3E905U, 0xFCEFA3F8U, 0x676F02D9U, 0x8D2A4C8AU,
    0xFFFA3942U, 0x8771F681U, 0x6D9D6122U, 0xFDE5380CU,
    0xA4BEEA44U, 0x4BDECFA9U, 0xF6BB4B60U, 0xBEBFBC70U,
    0x289B7EC6U, 0xEAA127FAU, 0xD4EF3085U, 0x04881D05U,
    0xD9D4D039U, 0xE6DB99E5U, 0x1FA27CF8U, 0xC4AC5665U,
    0xF4292244U, 0x432AFF97U, 0xAB9423A7U, 0xFC93A039U,
    0x655B59C3U, 0x8F0CCC92U, 0xFFEFF47DU, 0x85845DD1U,
    0x6FA87E4FU, 0xFE2CE6E0U, 0xA3014314U, 0x4E0811A1U,
    0xF7537E82U, 0xBD3AF235U, 0x2AD7D2BBU, 0xEB86D391U
};

static const UInt32 md5_inits[4] = {
    0x67452301U, 0xEFCDAB89U, 0x98BADCFEU, 0x10325476
};

typedef UInt32 (*md5_func_fghi)(UInt32, UInt32, UInt32);

static UInt32 md5_func_F(UInt32 x, UInt32 y, UInt32 z) { return ((x & y) | (~x & z)); }
static UInt32 md5_func_G(UInt32 x, UInt32 y, UInt32 z) { return ((x & z) | (y & ~z)); }
static UInt32 md5_func_H(UInt32 x, UInt32 y, UInt32 z) { return (x ^ y ^ z);          }
static UInt32 md5_func_I(UInt32 x, UInt32 y, UInt32 z) { return (y ^ (x | ~z));       }

static md5_func_fghi md5_fghi[4] = {
    md5_func_F, md5_func_G, md5_func_H, md5_func_I
};

typedef UInt32 (*md5_func_g1234)(UInt32);

static UInt32 md5_func_g1(UInt32 i) { return      i          ; }
static UInt32 md5_func_g2(UInt32 i) { return (5 * i + 1) % 16; }
static UInt32 md5_func_g3(UInt32 i) { return (3 * i + 5) % 16; }
static UInt32 md5_func_g4(UInt32 i) { return (7 * i    ) % 16; }

static md5_func_g1234 md5_g1234[4] = {
    md5_func_g1, md5_func_g2, md5_func_g3, md5_func_g4
};

void md5_init(md5_t * md5)
{
    memcpy(md5->abcd, md5_inits, sizeof(UInt32) * 4);
}

static void md5_process(md5_t * md5, UInt8 * data)
{
    UInt32 abcd[4];
    UInt32 block[16];
    UInt32 i, dt;

    memcpy(block, data, 16 * sizeof(UInt32));
    memcpy(abcd, md5->abcd, sizeof(UInt32) * 4);

    for (i = 0; i < 64; i++)
    {
        dt = abcd[3];
        abcd[3] = abcd[2];
        abcd[2] = abcd[1];
        abcd[1] = abcd[1] +
                  RRotationLeft32(abcd[0] +
                                  md5_fghi[i / 16](abcd[1], abcd[2], abcd[3]) +
                                  md5_sins[i] +
                                  block[md5_g1234[i / 16](i)],
                    md5_shifts[i]);
        abcd[0] = dt;
    }

    for (i = 0; i < 4; i++)
        md5->abcd[i] += abcd[i];
}

void md5_append(md5_t * md5, UInt8 * data, UInt32 length)
{
    /* test for empty message - no preprocessing */

    /* for every 512 bit chunk, no more than 1 chunk for the test */
    md5_process(md5, data);
}

Так вот получаю неверный хеш:

Data is    A4850585, B3833027, 5B4C60B2, 4835C01D
Should be: D41D8CD9, 8F00B204, E9800998, ECF8427E

Где у меня косяк? В русской википедии гвоорится что-то об установке 0х80 в конце данных, в английской такого нет. Есть тут эксперты?

В русской википедии гвоорится что-то об установке 0х80 в конце данных, в английской такого нет.

4.2:

Algorithm

MD5 processes a variable-length message into a fixed-length output of 128 bits. The input message is broken up into chunks of 512-bit blocks (sixteen 32-bit words); the message is padded so that its length is divisible by 512. The padding works as follows: first a single bit, 1, is appended to the end of the message. This is followed by as many zeros as are required to bring the length of the message up to 64 bits fewer than a multiple of 512. The remaining bits are filled up with 64 bits representing the length of the original message, modulo 264.

И вообще, см. пункт 3.1 RFC 1321.

ilammy ★★★ ()
Последнее исправление: ilammy (всего исправлений: 1)
Ответ на: комментарий от ilammy

Оно даже в псевдокоде выше есть:

//Pre-processing: adding a single 1 bit
append "1" bit to message

xaizek ★★★★★ ()

Тебя учить как алгоритмы отлаживать?

Берешь пример, считаешь ручками по алгоритму. Напичкиваешь свою имплементацию логами и смотришь результаты на каждом шаге алгоритма.

За тебя это никто не сделает, если ты решил сам импоементировать алгоритмы.

invy ★★★★★ ()

Главная ошибка в том, что ты считаешь F после того, как изменишь C и D, в то время, как в псевдокоде сначала вычисляется F, а потом уже тасуются C и D.

Вторая ошибка - то, что ты не добавляешь бит 1 к данным (и, кстати, не считаешь «длину данных в битах» % (1<<64)). В случае «пустых» данных начальная data будет равна UInt8 data[64] = {0x80};.

Пиши проще, кстати. Массивы из указателей на функции тут себя никак не оправдывают, а только забивают светлую головушку.

anonymous ()
Ответ на: комментарий от anonymous
static void md5_process(md5_t * md5, UInt8 * data)
{
    UInt32 abcd[4];
    UInt32 block[16];
    UInt32 i, dt, F;

    memcpy(block, data, 16 * sizeof(UInt32));
    memcpy(abcd, md5->abcd, sizeof(UInt32) * 4);

    for (i = 0; i < 64; i++)
    {
        F = md5_fghi[i / 16](abcd[1], abcd[2], abcd[3]);

        dt = abcd[3];
        abcd[3] = abcd[2];
        abcd[2] = abcd[1];
        abcd[1] = abcd[1] +
                  RRotationLeft32(abcd[0] + F + md5_sins[i] +
                                  block[md5_g1234[i / 16](i)],
                    md5_shifts[i]);
        abcd[0] = dt;
    }

    for (i = 0; i < 4; i++)
        md5->abcd[i] += abcd[i];
}

void md5_append(md5_t * md5, UInt8 * data, UInt32 length)
{
    /* test for empty message - no preprocessing */
    data[0] = 0x80;
    /* for every 512 bit chunk, no more than 1 chunk for the test */
    md5_process(md5, data);
}

Не особо помогло.

someoneelsenotme ()
Ответ на: комментарий от someoneelsenotme

А у меня с немного переделанным твоим кодом попадает.

data[0] = 0x80;

- это не тоже самое, что я выше писал. Кроме того учитывай порядок байт при выводе. Если ты выводишь int'ы, то результат будет d98c1dd4 04b2008f 980980e9 7e42f8ec, а если байты подряд, то d4 1d 8c d9 8f 00 b2 04 e9 80 09 98 ec f8 42 7e.

anonymous ()
Ответ на: комментарий от anonymous

Блин, чет я про порядок байт забыл %)

Спасибо, с 0х80 пошло как по маслу

это не тоже самое, что я выше писал

Я понимаю, просто у меня ж нулевое сообщение. Для других буду ставить бит.

someoneelsenotme ()
Ответ на: комментарий от i_gnatenko_brain

Да, давайте вообще не развиваться и использовать только все готовое.

someoneelsenotme ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.