Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Java: Общие вопросы > Реализация md5


Автор: BHYCHIK 9.3.2013, 00:25
Приветствую. Пишу реализацию md5 на Java. Вроде все делаю по описанию алгоритма, но выходит что-то не так. Такое чувство, что от входных данных вобще ничего не зависит.
Есть подозрение, что проблема из-за отсутствия беззнаковых ТД, либо что где-то косячу с обратным порядком байт в слове. Убил весь день прежде, чем просить о помощи. Помогите, пожалуйста, исправить.

md5.java
Код

package security;

import java.util.ArrayList;
import java.util.List;

public final class md5 
{
    private static final int initialA = 0x01234567;
    private static final int initialB = 0x89abcdef;
    private static final int initialC = 0xfedcba98;
    private static final int initialD = 0x76543210;
    
    private static int getT(int i)
    {
        return (int)Math.floor((4294967296L * Math.abs(Math.sin(i))));
    }
    
    private static byte[] getWordBytes(int word)
    {
        byte[] bytes = new byte[4];
        
        bytes[0] = (byte)(word & 0xFF);
        bytes[1] = (byte)((word & 0xFF00) >> 8);
        bytes[2] = (byte)((word & 0xFF0000) >> 16);
        bytes[3] = (byte)((word & 0xFF000000) >> 24);
        
        return bytes;
    }
    
    private static int F(int x, int y, int z)
    {
        return (x & y) | (~x & z);
    }
    
    private static int G(int x, int y, int z)
    {
        return (x & z) | (y & ~z);
    }
    
    private static int H(int x, int y, int z)
    {
        return x ^ y ^ z;
    }
    
    private static int I(int x, int y, int z)
    {
        return (x & y) | (~x & z);
    }
    
    private static List<Byte> normilze(byte[] input)
    {
        List<Byte> message = new ArrayList<Byte>();
        
        for(int i = 0; i < input.length; ++i)
        {
            message.add(input[i]);
        }    
        
        message.add((byte) 0x80);
        while(message.size() % (512 / 8) != (448 / 8))
        {
            message.add((byte)0x00);
        }
        
        long msgSize = input.length * 8;
        int lowWord = (int)(msgSize & 0xFFFFFFFFL);
        int highWord = (int)((msgSize & 0xFFFFFFFF00000000L) >> 32);
        
        byte[] sizeBytes = getWordBytes(lowWord);
        for(int i = 0; i < 4; ++i)
        {
            message.add(sizeBytes[i]);
        }    
        sizeBytes = getWordBytes(highWord);
        for(int i = 0; i < 4; ++i)
        {
            message.add(sizeBytes[i]);
        }    
        
        return message;
    }
    
    private static int rol1(int word)
    {
        byte tmp = (byte)((word & 0x80000000) >> 32);
        word = word << 1;
        if(tmp == 1)
        {
            word |= 1;
        }
        else
        {
            word &= 0;
        }
        return word;
    }
    
    private static int rol(int word, int n)
    {
        for(int i = 0; i < n; ++i)
        {
            word = rol1(word);
        }
        return word;
    }
    
    private static int getWord(List<Byte> message, int n, int k)
    {
        byte[] bytes = new byte[4];
        bytes[0] = message.get(n * 16 + k * 4 + 0);
        bytes[1] = message.get(n * 16 + k * 4 + 1);
        bytes[2] = message.get(n * 16 + k * 4 + 2);
        bytes[3] = message.get(n * 16 + k * 4 + 3);
        int result = (bytes[3] << 24) + (bytes[2] << 16) + (bytes[1] << 8) + bytes[0];
        return result;
    }
    
    private static int nextRound(int A, int B, int C, int D, int k, int s, int i, List<Byte> message, int n)
    {
        int tmp;
        if(i < 16)
        {
            tmp = F(B, C, D);
        }
        else if(i < 32)
        {
            tmp = G(B, C, D);
        }
        else if(i < 48)
        {
            tmp = H(B, C, D);
        }
        else
        {
            tmp = I(B, C, D);
        }
        
        return B + rol((A + tmp + getWord(message, n, k) + getT(i)), s);
    }
    
    public static int[] getMD5(byte[] input)
    {
        int A = initialA;
        int B = initialB;
        int C = initialC;
        int D = initialD;
        
        int oldA = A;
        int oldB = B;
        int oldC = C;
        int oldD = D;
        
        List<Byte> message = normilze(input);
        
        for(int i = 0; i < (message.size() / (512 / 8)); ++i)
        {
            oldA = A;
            oldB = B;
            oldC = C;
            oldD = D;
            
            A = nextRound(A, B, C, D, 0, 7, 1, message, i);
            D = nextRound(D, A, B, C, 1, 12, 2, message, i);
            C = nextRound(C, D, A, B, 2, 17, 3, message, i);
            B = nextRound(B, C, D, A, 3, 22, 4, message, i);
            A = nextRound(A, B, C, D, 4, 7, 5, message, i);
            D = nextRound(D, A, B, C, 5, 12, 6, message, i);
            C = nextRound(C, D, A, B, 6, 17, 7, message, i);
            D = nextRound(B, C, D, A, 7, 22, 8, message, i);
            A = nextRound(A, B, C, D, 8, 7, 9, message, i);
            D = nextRound(D, A, B, C, 9, 12, 10, message, i);
            C = nextRound(C, D, A, B, 10, 17, 11, message, i);
            B = nextRound(B, C, D, A, 11, 22, 12, message, i);
            A = nextRound(A, B, C, D, 12, 7, 13, message, i);
            D = nextRound(D, A, B, C, 13, 12, 14, message, i);
            C = nextRound(C, D, A, B, 14, 17, 15, message, i);
            B = nextRound(B, C, D, A, 15, 22, 16, message, i);
            
            A = nextRound(A,B,C,D,1,5,17, message, i);
            D = nextRound(D,A,B,C,6,9,18, message, i);
            C = nextRound(C,D,A,B,11,14,19, message, i);
            B = nextRound(B,C,D,A,0,20,20, message, i);
            A = nextRound(A,B,C,D,5, 5, 21, message, i);
            D = nextRound(D,A,B,C,10,9,22, message, i);
            C = nextRound(C,D,A,B,15,14,23, message, i);
            B = nextRound(B,C,D,A,4,20,24, message, i);
            C = nextRound(A,B,C,D,9,5,25, message, i);
            D = nextRound(D,A,B,C,14, 9, 26, message, i);
            C = nextRound(C,D,A,B,3, 14, 27, message, i);
            B = nextRound(B,C,D,A,8,20,28, message, i);
            A = nextRound(A,B,C,D, 13, 5, 29, message, i);
            D = nextRound(D,A,B,C,2,9,30, message, i);
            C = nextRound(C,D,A,B,7,14,31, message, i);
            B = nextRound(B,C,D,A,12,20,32, message, i);
            
            A = nextRound(A,B,C,D, 5, 4, 33, message, i);
            D = nextRound(D,A,B,C,8,11,34, message, i);
            C = nextRound(C,D,A,B, 11, 16, 35, message, i);
            B = nextRound(B,C,D,A, 14, 23, 36, message, i);
            A = nextRound(A,B,C,D,  1, 4, 37, message, i);
            D = nextRound(D,A,B,C,  4, 11, 38, message, i);
            C = nextRound(C,D,A,B,7, 16, 39, message, i);
            B = nextRound(B,C,D,A, 10, 23, 40, message, i);
            A = nextRound(A,B,C,D, 13, 4, 41, message, i);
            D = nextRound(D,A,B,C,  0, 11, 42, message, i);
            C = nextRound(C,D,A,B,  3, 16, 43, message, i);
            B = nextRound(B,C,D,A,  6, 23, 44, message, i);
            A = nextRound(A,B,C,D,  9, 4, 45, message, i);
            D = nextRound(D,A,B,C, 12, 11, 46, message, i);
            C = nextRound(C,D,A,B, 15, 16, 47, message, i);
            B = nextRound(B,C,D,A,  2, 23, 48, message, i);
            
            A = nextRound(A,B,C,D,  0, 6, 49, message, i);
            D = nextRound(D,A,B,C,  7, 10, 50, message, i);
            C = nextRound(C,D,A,B, 14, 15, 51, message, i);
            B = nextRound(B,C,D,A,  5, 21, 52, message, i);
            A = nextRound(A,B,C,D, 12, 6, 53, message, i);
            D = nextRound(D,A,B,C,  3, 10, 54, message, i);
            C = nextRound(C,D,A,B, 10, 15, 55, message, i);
            B = nextRound(B,C,D,A,  1, 21, 56, message, i);
            A = nextRound(A,B,C,D, 8, 6, 57, message, i);
            D = nextRound(D,A,B,C, 15, 10, 58, message, i);
            C = nextRound(C,D,A,B,  6, 15, 59, message, i);
            B = nextRound(B,C,D,A, 13, 21, 60, message, i);
            A = nextRound(A,B,C,D, 4, 6, 61, message, i);
            D = nextRound(D,A,B,C, 11, 10, 62, message, i);
            C = nextRound(C,D,A,B, 2, 15, 63, message, i);
            B = nextRound(B,C,D,A,  9, 21, 64, message, i);
            
            A += oldA;
            B += oldB;
            C += oldC;
            D += oldD;
        }
        
        int[] result = new int[4];
        result[3] = A;
        result[2] = B;
        result[1] = C;
        result[0] = D;
        return result;
    }

}


StartPoint.java
Код

package program;

import security.md5;

public final class StartPoint
{
    /**
     * @param args
     */
    public static void main(String[] args) 
    {
        int[] result = md5.getMD5(new byte[] {0x68, 0x61, 0x62, 0x72, 0x61, 0x68, 0x61, 0x62, 0x72});
        System.out.printf("%8x%8x%8x%8x", result[0], result[1], result[2], result[3]);
    }

}



Извините за убогие имена функций/переменных. Делал единообразно с документацией.

Автор: BHYCHIK 9.3.2013, 11:46
Нашел 1 ошибку. Стало лучше, но md5 не получилось еще.

Было
Код

private static int rol1(int word)
    {
        byte tmp = (byte)((word & 0x80000000) >> 32);
        word = word << 1;
        if(tmp == 1)
        {
            word |= 1;
        }
        else
        {
            word &= 0;
        }
        return word;
    }


Стало
Код

private static int rol1(int word)
    {
        byte tmp = (byte)((word & 0x80000000) >> 32);
        word = word << 1;
        if(tmp == 1)
        {
            word |= 1;
        }
    }



Туплю что-то

Автор: BHYCHIK 9.3.2013, 18:54
Задача благополучно решена.

Автор: ReFLeXive 9.3.2013, 22:01
В чем в итоге дело было?

Автор: BHYCHIK 11.3.2013, 23:49
Цитата(ReFLeXive @ 9.3.2013,  22:01)
В чем в итоге дело было?

Битовый сдвиг в яве арифметический. Это основная проблема была. Пришлось ручками написать беззнаковые обертки. Ну и было пара опечаток.

Автор: AlexeyVorotnikov 12.3.2013, 09:12
В Джаве есть и знаковый и беззнаковый сдвиг вправо:
>> (signed right shift), and >>> (unsigned right shift) 

Автор: ReFLeXive 12.3.2013, 15:03
Именно. Я когда реализовывал ГОСТ28147 тоже на это напоролся. в это время те, кто писал на языках со знаковыми типами данных, подобных проблем не испытывали.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)