內存有效的SHA1實現

Question

我正在使用一個非常有限制的嵌入式處理器，它只有128字節的RAM。我想要在其上實現SHA1。 RFC3174在'方法2'中描述了一種實現SHA1的方法，其不需要分配80個32位字的數組（其在320字節處顯然不實用），並且似乎它應該可用於我的處理器。但是我找不到'方法2'的任何實現，而RFC中的示例代碼只實現了默認方法。

是否有人知道在C或C++中使用SHA1的內存高效實現？

Answer 1

你應該能夠很快適應方法1源方法2的功能改變是方法1.初始化w[0:15]Sha1ProcessMessageBlock()從消息，然後做的0環到79，在那裏你只能做後w[]操縱迭代16，臨時計算取決於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數組中，添加填充並立即進行處理。如果不是的話，你必須調用兩次進程：首先使用部分填充的輸入，然後再使用其餘的填充，等等。這種事情會非常專用，我懷疑你能找到代碼爲你做。

順便說一句，上面的代碼是從您的鏈接類型1來源的直接適應。如果您嘗試進一步優化，您可能會擠出更多。

我想不出有什麼辦法可以節省中間散列，所以你總共需要108個字節（如果計數器也在RAM中），其中24個是本地的功能，並且可以在其他地方重新使用 - 只要它們也是臨時的。所以很難做到你想做的事情。

---

編輯：如果你的所有消息小於55個字節，則可以擺脫intermediate_hash[]存儲的文件保存在背景中另一個20個字節。只需從常量初始化A-E，並在最後添加常量。最後，不是將它們存儲在單獨的變量中，而是在此函數結束時覆蓋輸入。

Answer 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會在運行中更新爲循環緩衝區，而不是在每輪開始時生成。

Answer 3

所有的事情都考慮到了，看你的要求，我想你將不得不改變你的規格。要麼是更大的芯片，要麼更簡單的算法。即使實施SHA-1（無HMAC）也是一項挑戰，但它應該是可行的。

Answer 4

工作示例：

#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; 


}