Эффективная реализация SHA1 с использованием памяти

Ответ 1

Вы должны иметь возможность быстро адаптировать источник метода 1 к методу 2. Функция изменения Sha1ProcessMessageBlock() в методе 1. Инициализируйте w[0:15] из сообщения, затем выполните цикл от 0 до 79, где вы делаете w[] манипуляция после итерации 16, а расчет темпа зависит от значения t (0-19 использует один, 20-39 использует другой и т.д.). Важно помнить, что используется index%16 или index & 0x0f всякий раз, когда вы обращаетесь к массиву w[].

Быстрая модификация будет примерно такой (дважды проверьте все обращения к w, чтобы убедиться, что я не пропустил t & 0x0f):

void SHA1ProcessMessageBlock(SHA1Context *context)
{
    const uint32_t K[] =    {       /* Constants defined in SHA-1   */
                            0x5A827999,
                            0x6ED9EBA1,
                            0x8F1BBCDC,
                            0xCA62C1D6
                            };
    int           t;                 /* Loop counter                */
    uint32_t      temp;              /* Temporary word value        */
    uint32_t      W[16];             /* Word sequence               */
    uint32_t      A, B, C, D, E;     /* Word buffers                */

    /*
     *  Initialize the first 16 words in the array W. You can move this to your
     *  context.
     */
    for(t = 0; t < 16; t++)
    {
        W[t] = context->Message_Block[t * 4] << 24;
        W[t] |= context->Message_Block[t * 4 + 1] << 16;
        W[t] |= context->Message_Block[t * 4 + 2] << 8;
        W[t] |= context->Message_Block[t * 4 + 3];
    }


    A = context->Intermediate_Hash[0];
    B = context->Intermediate_Hash[1];
    C = context->Intermediate_Hash[2];
    D = context->Intermediate_Hash[3];
    E = context->Intermediate_Hash[4];

    for(t = 0; t < 80; t++) {
        if (t >= 16) {
            W[t&0xf] = SHA1CircularShift(1,W[(t-3)&0xf] ^ W[(t-8)&0xf] ^ W[(t-14)&0xf] ^ W[t&0xf]);

        }

        if (t<20) {
            temp =  SHA1CircularShift(5,A) +
                    ((B & C) | ((~B) & D)) + E + W[t&0xf] + K[0];
        }
        else if (t<40) {
            temp = SHA1CircularShift(5,A) + (B ^ C ^ D) + E + W[t&0xf] + K[1];
        }
        else if (t < 60) {
            temp = SHA1CircularShift(5,A) +
                   ((B & C) | (B & D) | (C & D)) + E + W[t&0xf] + K[2];
        }
        else {
            temp = SHA1CircularShift(5,A) + (B ^ C ^ D) + E + W[t&0xf] + K[3];
        }
        E = D;
        D = C;
        C = SHA1CircularShift(30,B);
        B = A;
        A = temp;
    }

    context->Intermediate_Hash[0] += A;
    context->Intermediate_Hash[1] += B;
    context->Intermediate_Hash[2] += C;
    context->Intermediate_Hash[3] += D;
    context->Intermediate_Hash[4] += E;

    context->Message_Block_Index = 0;
}

По-прежнему сохраняются сбережения: избавиться от массива w[] в стеке и поместить его в контекст, предварительно инициализированный данными, которые вы получаете.

Кроме того, перед вызовом этой функции вам нужно много предварительной обработки. Например, если все ваши сообщения составляют менее 55 байт, вы можете поместить их в массив W, добавить дополнение и обработать немедленно. Если нет, вам придется дважды вызвать процесс: сначала с частично заполненным вводом, и снова с остальной частью пэда и т.д. Подобная вещь будет очень специфичной для приложения, и я сомневаюсь, что вы сможете найти код, чтобы сделать это для вас.

Кстати, приведенный выше код является прямой адаптацией от источника 1-го типа из вашей ссылки. Вы можете, вероятно, сжать немного больше, если попытаетесь оптимизировать его дальше.

Я не мог придумать способ получения экономии на промежуточном хэше, так что для этого вам понадобится в общей сложности 108 байт (109, если счетчик также находится в ОЗУ), и 24 из которых являются локальными для этой функции, и их можно использовать повторно в других местах, если они также временны. Поэтому очень сложно делать то, что вы хотите сделать.

EDIT: если все ваши сообщения составляют менее 55 байт, вы можете сохранить еще 20 байт в своем контексте, избавившись от хранилища intermediate_hash[]. Просто инициализируйте A-E из констант и добавьте константы в конец. Наконец, вместо сохранения их в отдельной переменной перезапишите свой вход, когда эта функция закончится.

Ответ 2

Я реализовал SHA-1 для нескольких сред с ограничением памяти. Вы можете пройти через

DWORD W[16] ;        // instead of H[80]
DWORD H[5] ;         // Intermediate hash value
DWORD BitCount[2] ;  // Probably a single DWORD is enough here

плюс несколько байт домашнего хозяйства. W обновляется "на лету", как круговой буфер, вместо того, чтобы сгенерировать его в начале каждого раунда.

Ответ 3

рабочий пример:

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string>

using namespace std;

unsigned CircularShift(int bits, unsigned word)
{
    return ((word << bits) & 0xFFFFFFFF) | ((word & 0xFFFFFFFF) >> (32-bits));
}

int main(void)
{
    string mess;
    cin >> mess;
    unsigned int lm = mess.length();
    unsigned int lmb = lm*8;
    unsigned char *messc;
    messc=(unsigned char*)malloc((sizeof(unsigned char))*64);

    for (unsigned short int i =0;i<64;i++)
    {
        messc[i]=char(0x00);
    }
    for(int i=0;i<mess.length();i++)
    {
        messc[i]=mess[i];
    }
    messc[lm]=(unsigned char)128;
    messc[56] = (lmb >> 24) & 0xFF;
    messc[57] = (lmb >> 16) & 0xFF;
    messc[58] = (lmb >> 8) & 0xFF;
    // messc[59] = (lmb) & 0xFF;
    messc[60] = (lmb >> 24) & 0xFF;
    messc[61] = (lmb >> 16) & 0xFF;
    messc[62] = (lmb >> 8) & 0xFF;
    messc[63] = (lmb) & 0xFF;
    for(int i =0 ;i<64;i++)
    {
        cout<< hex << (int)messc[i] << " ";
    }
    unsigned *H;
    H=(unsigned*)malloc(5*sizeof(unsigned));
    H[0]        = 0x67452301;
    H[1]        = 0xEFCDAB89;
    H[2]        = 0x98BADCFE;
    H[3]        = 0x10325476;
    H[4]        = 0xC3D2E1F0;
    const unsigned K[]={0x5A827999,0x6ED9EBA1,0x8F1BBCDC,0xCA62C1D6};
    int         t;
    unsigned    temp;
    unsigned    *W;
    unsigned    A, B, C, D, E;
    W=(unsigned*)malloc(80*sizeof(unsigned));
    unsigned char *messh;
    messh=(unsigned char*)malloc(64*sizeof(unsigned char));
    int k;
    for(t = 0; t < 16; t++)
    {
        W[t] = ((unsigned) messc[t * 4])<< 24; ;
        W[t] |= ((unsigned) messc[t * 4 + 1])<< 16;
        W[t] |= ((unsigned) messc[t * 4 + 2]) << 8;
        W[t] |= ((unsigned) messc[t * 4 + 3]);
    }
    for(t = 16; t < 80; t++)
    {
        W[t] = CircularShift(1,W[t-3] ^ W[t-8] ^ W[t-14] ^ W[t-16]);
    }

    A = H[0];
    B = H[1];
    C = H[2];
    D = H[3];
    E = H[4];

    for(t = 0; t < 20; t++)
    {
        temp = CircularShift(5,A) + ((B & C) | ((~B) & D)) + E + W[t] + K[0];
        temp &= 0xFFFFFFFF;
        E = D;
        D = C;
        C = CircularShift(30,B);
        B = A;
        A = temp;
    }

    for(t = 20; t < 40; t++)
    {
        temp = CircularShift(5,A) + (B ^ C ^ D) + E + W[t] + K[1];
        temp &= 0xFFFFFFFF;
        E = D;
        D = C;
        C = CircularShift(30,B);
        B = A;
        A = temp;
    }

    for(t = 40; t < 60; t++)
    {
        temp = CircularShift(5,A) +
                ((B & C) | (B & D) | (C & D)) + E + W[t] + K[2];
        temp &= 0xFFFFFFFF;
        E = D;
        D = C;
        C = CircularShift(30,B);
        B = A;
        A = temp;
    }

    for(t = 60; t < 80; t++)
    {
        temp = CircularShift(5,A) + (B ^ C ^ D) + E + W[t] + K[3];
        temp &= 0xFFFFFFFF;
        E = D;
        D = C;
        C = CircularShift(30,B);
        B = A;
        A = temp;
    }

    H[0] = (H[0] + A) & 0xFFFFFFFF;
    H[1] = (H[1] + B) & 0xFFFFFFFF;
    H[2] = (H[2] + C) & 0xFFFFFFFF;
    H[3] = (H[3] + D) & 0xFFFFFFFF;
    H[4] = (H[4] + E) & 0xFFFFFFFF;

    cout <<"\nTHIS IS SHHHHHAAAAAAAAAAA\n";
    for(int i=0;i<5;i++)
    {
        cout << hex << H[i] << " ";
    }

    //Message_Block_Index = 0;


}

Ответ 4

Все рассмотренные вещи, глядя на ваши требования, я думаю, вам придется изменить свои спецификации. Либо крупный чип, либо более простой алгоритм. Даже внедрение SHA-1 (без HMAC) было бы проблемой, но оно должно быть выполнимым.