c - 应用哈希函数 n 次

Question

我需要高效地实现特定哈希函数的迭代应用，例如 SHA1，输入 x n 次，即 SHA1(...SHA1(SHA1(x)))。我正在尝试使用下面的代码来实现这一点，但是对于 n=2^16，这太慢了 2 秒。在下面的代码中，$n$ 是应用 SHA1 的次数，x=seedj1 和 temp=SHA1(...SHA1(SHA1(x)))。你能帮帮我吗？

int hashcwe_n1(int n, unsigned char * seedj1, unsigned char * temp) {
int i, j;
int r = 160;
memcpy(temp, seedj1, r);
for (i = 0; i < n; i++) {
    SHA1(seedj1, r, temp);
    if (n % 2 != 0)
        swapStrings(&temp, &seedj1);
    else {
        if (i == n - 1) {
            memcpy(seedj1, R, r);
        } else {
         swapStrings(&temp, &seedj1);
        }
    }
}
return 1;
}

void swapStrings(unsigned char** a, unsigned char** b) {
unsigned char *temp = *a;
*a = *b;
*b = temp;
}

Answer 1

我不相信你的算法是正确的，所以衡量它的性能有点类似于在母鸡下蛋之前数小鸡，更不用说在鸡蛋孵化之前了。

迭代工作负载函数没有理由表现出如此糟糕的性能，除非......

• 您的 SHA 实现效率极低
• 您的测试平台是在 Windows 3.11 刚刚推出且令人兴奋的时候制作的。

以下是一个应该正确的夹具，并且表现出可接受的性能(至少在我看来是这样)。所用试验机的相关数据:

• MacBook Air (2011)，Intel Core i7 Duo，4GB 1333mhz 内存
• Apple LLVM 版本 6.1.0 (clang-602.0.53)(基于 LLVM 3.6.0svn)
• OpenSSL libcrypto 版本 0.9.8zd 2015 年 1 月 8 日

来源

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <openssl/sha.h>

// simple hex-print utility
void hex_print(const void *buf, size_t n)
{
    const unsigned char *beg = buf, *end = beg+n;
    while (beg != end)
        printf("%02x", *beg++);
    fputc('\n', stdout);
}


// iterate n-times
void hashcwe_n
(
    unsigned short n,   // iteration count
    void *src,          // source bytes
    size_t slen,        // souce length
    void *dst           // target buffer
)
{
    unsigned char md1[SHA_DIGEST_LENGTH];
    unsigned char md2[SHA_DIGEST_LENGTH];
    unsigned char *p1 = md1, *p2 = md2;
    unsigned short i;

    if (n == 0)
        return;

    // perform initial digest
    SHA1(src, slen, md1);

    // iterate the remainder of the loop
    for (i=0; i<(n-1); ++i)
    {
        unsigned char *tmp = p1;
        SHA1(p1, SHA_DIGEST_LENGTH, p2);
        p1 = p2;
        p2 = tmp;
    }
    memcpy(dst, p1, SHA_DIGEST_LENGTH);
}

// main entry point
int main()
{
    unsigned char data[] = {0x61,0x62,0x63}; // "abc"
    unsigned char md[SHA_DIGEST_LENGTH] = {0};

    hashcwe_n(USHRT_MAX, data, sizeof(data), md);
    hex_print(md, SHA_DIGEST_LENGTH);

    return 0;
}

构建命令

clang -std=c11 -O2 -Wall -Wextra -pedantic -lcrypto -o sample sample.c

输出控制台

$ time ./sample
a21b4b42e20066a1046d3c81b42b7cd8a6403bf2

real  0m0.031s
user  0m0.026s
sys   0m0.003s

See here对于在 Coliru 上实时运行的相同样本。

祝你好运