c++ - 一种节省内存的 SHA1 实现

Question

我正在使用一个非常严格的嵌入式处理器，它只有 128 字节的内存。我想在它上面实现 SHA1。 RFC3174在“方法 2”中描述了一种实现 SHA1 的方法，它不需要分配 80 个 32 位字的数组(这在 320 字节处显然是不切实际的)，并且似乎它应该可以在我的处理器。但是，我找不到任何“方法 2”的实现，并且 RFC 中的示例代码仅实现了默认方法。

有人知道 C 或 C++ 中 SHA1 的内存高效实现吗？

Answer 1

你应该可以快速将方法1源码适配到方法2。要改变的函数是方法1中的Sha1ProcessMessageBlock()。初始化w[0:15] 从消息中，然后执行 0 到 79 的循环，其中您仅在迭代 16 之后执行 w[] 操作，并且临时计算取决于 t 的值(0- 19 使用一个，20-39 使用另一个，等等)。重要的是要记住在寻址 w[] 数组时使用 index%16 或 index & 0x0f。

快速修改是这样的(仔细检查对 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 数组中，添加填充，并立即处理。如果没有，您将不得不调用 process 两次:首先使用部分填充的输入，然后再使用填充的其余部分，等等。这种事情将是非常特定于应用程序的，我怀疑你能找到为您执行此操作的代码。

顺便说一句，上面的代码直接改编自您链接中的类型 1 源。如果您尝试进一步优化它，您可能会从中挤出更多。

我想不出任何节省中间哈希的方法，因此您总共需要 108 个字节(如果计数器也在 RAM 中，则需要 109 个字节)，其中 24 个是此函数的本地字节，并且可以在其他地方重复使用——只要它们也是临时的。所以做自己想做的事是非常困难的。

---

编辑:如果您的所有消息都小于 55 个字节，您可以通过摆脱 intermediate_hash[] 存储在您的上下文中再节省 20 个字节。只需从常量初始化 A-E，然后在末尾添加常量。最后，不要将它们存储在单独的变量中，而是在此函数结束时覆盖您的输入。