一种节省内存的SHA1实现

Question

我正在使用一个非常严格的嵌入式处理器,它只有128字节的RAM.我想在它上面实现SHA1.RFC3174在'方法2'中描述了一种实现SHA1的方法,该方法不需要分配80个32位字的数组(320字节,显然不实用),看起来它应该可用于我的处理器.但是,我无法找到"方法2"的任何实现,并且RFC中的示例代码仅实现了默认方法.

有人知道在C或C++中使用SHA1进行内存有效的实现吗？

Answer 1

您应该能够快速调整方法1源到方法2.要更改的函数Sha1ProcessMessageBlock()在方法1中.w[0:15]从消息初始化,然后执行0到79的循环,其中您只w[]在迭代16之后进行操作,并且临时计算取决于在ts值(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数组中,添加填充并立即处理.如果没有,你将不得不两次调用进程:首先使用部分填充的输入,然后再使用其余的pad,等等.这类事情将是非常特定于应用程序的,我怀疑你是否能够找到为你做的代码.

顺便说一句,上面的代码是来自链接的类型1源的直接改编.如果你试图进一步优化它,你可能会更多地挤出它.

我想不出可以节省中间散列的方法,所以你需要总共108个字节(109,如果计数器也在RAM中),其中24个是本函数的本地,并且可以在其他地方重复使用 - 只要它们也是暂时的.所以做你想做的事很难.

编辑:如果所有消息都少于55个字节,则可以通过删除intermediate_hash[]存储来保存上下文中的另外20个字节.只需从常量初始化AE,然后在最后添加常量.最后,不要将它们存储在单独的变量中,而是在此函数结束时覆盖输入.