스트림에서 SHA-1 알고리즘을 계산할 수 있습니까? 메모리 사용량이 적습니까?

Question

매우 큰 파일의 SHA-1 체크섬을 한번에 메모리에 완전히로드하지 않고 계산하는 방법을 찾고 있습니다.

SHA-1 구현의 세부 사항을 알지 못하므로이를 수행 할 수 있는지 알고 싶습니다.

SAX XML 파서를 알고 있다면 나는 비슷한 것을 발견 할 수 있습니다. 항상 작은 부분을 항상 메모리에로드하여 SHA-1 체크섬을 계산합니다.

최소한 Java에서 발견 된 모든 예제는 항상 파일/바이트 배열/문자열을 메모리에 완전히로드해야합니다.

구현 (모든 언어)을 알고 있다면 알려 주시기 바랍니다.

Answer 1

입니다. SHA-1은 블록 알고리즘이므로 한번에 한 블록 씩 동작합니다. 정확한 블록 크기는 생성중인 해시 크기에 따라 다르지만 항상 작습니다 (예 : 20-50 바이트 정도). 물론 SHA-1 256, 384 및/또는 512 (일명 SHA-256, SHA-384 및 SHA-512)를 포함한다는 것을 의미한다고 가정합니다. 원래 160 비트 버전 만 포함하는 경우 블록 크기는 항상 20 바이트 (160 비트)입니다.

편집 : oops - SHA-384 및 SHA-512의 경우 SHA-1, SHA-224, SHA-256 및 1024 비트의 경우 블록 크기가 512 비트입니다. 감사합니다 찰스!

편집 2 : 내가 조언하는 것이 아니라 소스 코드를 찾는 부분을 거의 잊어 버렸습니다. 여기에 몇 가지 코드가 있습니다. 먼저 헤더 :

// Sha.h: 
#ifndef SHA_1_H_INCLUDED 
#define SHA_1_H_INCLUDED 

// This is a relatively straightforward implementation of SHA-1. It makes no particular 
// attempt at optimization, instead aiming toward easy verification against the standard. 
// To that end, many of the variable names are identical to those used in FIPS 180-2 and 
// FIPS 180-3. 
// 
// The code should be fairly portable, within a few limitations: 
// 1. It requires that 'char' have 8 bits. In theory this is avoidable, but I don't think 
// it's worth the bother. 
// 2. It only deals with inputs in (8-bit) bytes. In theory, SHA-1 can deal with a number of 
// bits that's not a multiple of 8, but I've never needed it. Since the padding always results 
// in a byte-sized stream, the only parts that would need changing would be reading and padding 
// the input. The main hashing portion would be unaffected. 
// 
// Compiles cleanly with: 
// MS VC++ 9.0SP1 (x86 or x64): -W4 -Za 
// gc++ 3.4: -ansi -pedantic -Wall 
// comeau 4.3.3: --vc71 
// Appears to work corectly in all cases. 
// You can't use maximum warnings with Comeau though -- this code itself doesn't give problems 
// (that I know of) but Microsoft's headers give it *major* heartburn. 
// 
// 
// Written by Jerry Coffin, February 2008 
// 
// You can use this software any way you want to, with following limitations 
// (shamelessly stolen from the Boost software license): 
// 
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 
// FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT 
// SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE 
// FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE, 
// ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 
// DEALINGS IN THE SOFTWARE. 
// 
// If you put this to real use, I'd be happy to hear about it. If you find a bug, 
// I'd be interested in hearing about that too. There's even a pretty good chance 
// that I'll try to fix it, though I certainly can't guarantee that. 
// 
#include <algorithm> 
#include <vector> 
#include <string> 
#include <assert.h> 
#include <iostream> 
#include <sstream> 
#include <iomanip> 

#if defined(_MSC_VER) && _MSC_VER < 1600 
typedef unsigned int uint32_t; 
typedef unsigned __int64 uint64_t; 
#else 
#include <stdint.h> 
#endif 

namespace crypto { 
namespace { 
    struct ternary_operator { 
     virtual uint32_t operator()(uint32_t x, uint32_t y, uint32_t z) = 0; 
    }; 
} 

class sha1 { 
    static const size_t hash_size = 5; 
    static const size_t min_pad = 64; 
    static const size_t block_bits = 512; 
    static const size_t block_bytes = block_bits/8; 
    static const size_t block_words = block_bytes/4; 

    std::vector<uint32_t> K; 
    std::vector<uint32_t> H; 
    std::vector<uint32_t> W; 
    std::vector<ternary_operator *> fs; 
    uint32_t a, b, c, d, e, T; 
    static const size_t block_size = 16; 
    static const size_t bytes_per_word = 4; 
    size_t total_size; 

    // hash a 512-bit block of input. 
    // 
    void hash_block(std::vector<uint32_t> const &block); 

    // Pad the input to a multiple of 512 bits, and add the length 
    // in binary to the end. 
    static std::string pad(std::string const &input, size_t size); 

    // Turn 64 bytes into a block of 16 uint32_t's. 
    std::vector<uint32_t> make_block(std::string const &in); 

public: 

    // Construct a SHA-1 object. More expensive that typical 
    // ctor, but not expected to be copied a lot or anything 
    // like that, so it should be fairly harmless. 
    sha1(); 

    // The two ways to provide input for hashing: as a stream or a string. 
    // Either way, you get the result as a vector<uint32_t>. It's a fairly 
    // small vector, so even if your compiler doesn't do return-value 
    // optimization, the time taken for copying it isn't like to be 
    // significant. 
    // 
    std::vector<uint32_t> operator()(std::istream &in); 
    std::vector<uint32_t> operator()(std::string const &input); 

    friend std::ostream &operator<<(std::ostream &os, sha1 const &s); 
}; 
} 

#endif 

및 구현 :

// Sha1.cpp: 
#include "sha.h" 
// Please see comments in sha.h for licensing information, etc. 
// 

// Many people don't like the names I usually use for namespaces, so I've kept this one 
// short and simple. 
// 
namespace crypto { 
namespace { 
uint32_t ROTL(uint32_t const &value, unsigned bits) { 
    uint32_t mask = (1 << bits) - 1; 
    return value << bits | (value >> (32-bits))&mask; 
} 

struct f1 : ternary_operator { 
    uint32_t operator()(uint32_t x, uint32_t y, uint32_t z) { 
     return (x & y)^(~x&z); 
    } 
}; 

struct f2 : ternary_operator { 
    uint32_t operator()(uint32_t x, uint32_t y, uint32_t z) { 
     return x^y^z; 
    } 
}; 

struct f3 : ternary_operator { 
    uint32_t operator()(uint32_t x, uint32_t y, uint32_t z) { 
     return (x&y)^(x&z)^(y&z); 
    } 
}; 

uint32_t word(int a, int b, int c, int d) { 
    a &= 0xff; 
    b &= 0xff; 
    c &= 0xff; 
    d &= 0xff; 
    int val = a << 24 | b << 16 | c << 8 | d; 
    return val; 
} 
} 

// hash a 512-bit block of input. 
// 
void sha1::hash_block(std::vector<uint32_t> const &block) { 
    assert(block.size() == block_words); 

    int t; 
    std::copy(block.begin(), block.end(), W.begin()); 
    for (t=16; t<80; t++) { 
     W[t] = ROTL(W[t-3]^W[t-8]^W[t-14]^W[t-16], 1); 
    } 

    a = H[0]; b = H[1]; c = H[2]; d = H[3]; e = H[4]; 

    for (t=0; t<80; t++) { 
     T = ROTL(a, 5) + (*fs[t])(b, c, d) + e + K[t] + W[t]; 
     e = d; 
     d = c; 
     c = ROTL(b, 30); 
     b = a; 
     a = T; 
    } 
    H[0] += a; H[1] += b; H[2] += c; H[3] += d; H[4] += e; 
} 

// Pad the input to a multiple of 512 bits, and put the length 
// in binary at the end. 
std::string sha1::pad(std::string const &input, size_t size) { 
    size_t length = size * 8 + 1; 
    size_t remainder = length % block_bits; 
    size_t pad_len = block_bits-remainder; 

    if (pad_len < min_pad) 
     pad_len += block_bits; 
    ++pad_len; 

    pad_len &= ~7; 
    std::string padding(pad_len/8, '\0'); 

    for (size_t i=0; i<sizeof(padding.size()); i++) 
     padding[padding.size()-i-1] = (length-1) >> (i*8) & 0xff; 
    padding[0] |= (unsigned char)0x80; 

    std::string ret(input+padding); 
    return ret; 
} 

// Turn 64 bytes into a block of 16 uint32_t's. 
std::vector<uint32_t> sha1::make_block(std::string const &in) { 
    assert(in.size() >= block_bytes); 

    std::vector<uint32_t> ret(block_words); 

    for (size_t i=0; i<block_words; i++) { 
     size_t s = i*4; 
     ret[i] = word(in[s], in[s+1], in[s+2], in[s+3]); 
    } 
    return ret; 
} 


// Construct a SHA-1 object. More expensive that typical 
// ctor, but not expected to be copied a lot or anything 
// like that, so it should be fairly harmless. 
sha1::sha1() : K(80), H(5), W(80), fs(80), total_size(0) { 
    static const uint32_t H0[] = { 
     0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476, 0xc3d2e1f0 
    }; 
    static const uint32_t Ks[] = { 
     0x5a827999, 0x6ed9eba1, 0x8f1bbcdc, 0xca62c1d6 
    }; 

    std::copy(H0, H0+hash_size, H.begin()); 

    std::fill_n(K.begin()+00, 20, Ks[0]); 
    std::fill_n(K.begin()+20, 20, Ks[1]); 
    std::fill_n(K.begin()+40, 20, Ks[2]); 
    std::fill_n(K.begin()+60, 20, Ks[3]); 

    static f1 sf1; 
    static f2 sf2; 
    static f3 sf3; 

    std::fill_n(fs.begin()+00, 20, &sf1); 
    std::fill_n(fs.begin()+20, 20, &sf2); 
    std::fill_n(fs.begin()+40, 20, &sf3); 
    std::fill_n(fs.begin()+60, 20, &sf2); 
} 

// The two ways to provide input for hashing: as a stream or a string. 
// Either way, you get the result as a vector<uint32_t>. It's a fairly 
// small vector, so even if your compiler doesn't do return-value 
// optimization, the time taken for copying it isn't like to be 
// significant. 
// 
std::vector<uint32_t> sha1::operator()(std::string const &input) { 
    std::string temp(pad(input, total_size + input.size())); 
    std::vector<uint32_t> block(block_size); 

    size_t num = temp.size()/block_bytes; 

    for (unsigned block_num=0; block_num<num; block_num++) { 
     size_t s; 
     for (size_t i=0; i<block_size; i++) { 
      s = block_num*block_bytes+i*4; 
      block[i] = word(temp[s], temp[s+1], temp[s+2], temp[s+3]); 
     } 
     hash_block(block); 
    } 
    return H; 
} 

std::vector<uint32_t> sha1::operator()(std::istream &in) { 
    char raw_block[65]; 

    while (in.read(raw_block, block_bytes)) { 
     total_size += block_bytes; 
     std::string b(raw_block, in.gcount()); 
     hash_block(make_block(b)); 
    } 
    std::string x(raw_block, in.gcount()); 
    return operator()(x); 
} 

std::ostream &operator<<(std::ostream &os, sha1 const &s) { 
    // Display a SHA-1 result in hex. 
    for (size_t i=0; i<(s.H).size(); i++) 
     os << std::fixed << std::setprecision(8) << std::hex << std::setfill('0') << (s.H)[i] << " "; 
    return os << std::dec << std::setfill(' ') << "\n"; 
} 

} 

#ifdef TEST 
#include <iostream> 
#include <iomanip> 
#include <string> 
#include <sstream> 

// A minimal test harness to check that it's working correctly. Strictly black-box 
// testing, with no attempt at things like coverage analysis. Nonetheless, I believe 
// it should cover most of the code -- the core hashing code all gets used for every 
// possible value. The padding code should be tested fairly thoroughly as well -- the 
// first test is a fairly simple case, and the second the more complex one (where the 
// padding requires adding another block). 
class tester { 
    bool verify(uint32_t *test_val, std::vector<uint32_t> const &hash, std::ostream &os) { 
     // Verify that a result matches a test value and report result. 
     for (size_t i=0; i<hash.size(); i++) 
      if (hash[i] != test_val[i]) { 
       os << "Mismatch. Expected: " << test_val[i] << ", but found: " << hash[i] << "\n"; 
       return false; 
      } 
      os << "Message digest Verified.\n\n"; 
      return true; 
    } 

public: 

    bool operator()(uint32_t *test_val, std::string const &input) { 
     std::cout << "Testing hashing from string:\n\"" << input << "\"\n"; 
     crypto::sha1 hasher1; 
     std::vector<uint32_t> hash = hasher1(input); 
     std::cout << "Message digest is:\n\t" << hasher1; 
     bool verified = verify(test_val, hash, std::cerr); 

     crypto::sha1 hasher2; 
     std::cout << "Testing hashing from Stream:\n"; 
     std::istringstream buf(input); 
     hash = hasher2(buf); 
     std::cout << "Message digest is:\n\t" << hasher2; 

     return verified & verify(test_val, hash, std::cerr); 
    } 
}; 

int main() { 
    // These test values and results come directly from the FIPS pub. 
    // 
    char const *input1 = "abc"; 
    char const *input2 = "abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq"; 
    uint32_t result1[] = {0xA9993E36, 0x4706816A, 0xBA3E2571, 0x7850C26C, 0x9CD0D89D}; 
    uint32_t result2[] = {0x84983E44, 0x1C3BD26E, 0xBAAE4AA1, 0xF95129E5, 0xE54670F1 }; 
    bool correct = tester()(result1, input1); 
    correct &= tester()(result2, input2); 
    if (correct) 
     std::cerr << "All Tests passed!\n"; 
    else 
     std::cerr << "Test Failed!\n"; 
} 
#elif defined(MAIN) 

#include <sstream> 
#include <fstream> 
#include <iostream> 

int main(int argc, char **argv) { 
    if (argc < 2) { 
     std::cerr << "Usage: sha1 [filename]\n"; 
     return EXIT_FAILURE; 
    } 
    for (int i=1; i<argc; i++) { 
     crypto::sha1 hash; 
     std::ifstream in(argv[i], std::ios_base::binary); 
     if (in.good()) { 
      hash(in); 
      std::cout << "SHA-1(" << argv[i] << ") = " << hash << "\n"; 
     } 
    } 
    return 0; 
} 
#endif 

Answer 2

예, 반복적이므로 스트림을 해시하는 데 사용할 수 있습니다. 각 반복마다 512 비트를 사용하고 다음 512 비트 블록을 가져 와서 다음에 사용할 수 있습니다.

여기서 의사 코드 : link을 찾을 수 있습니다. Java로 구현하는 것은 꽤 쉽습니다. 마지막 블록과 비트 연산을 만날 때 약간의 패딩을해야합니다!

경고는 : 유일한 예, 그것은 전적으로 가능하다 .. 당신이 문제를 방지하기 위해 몇 가지 트릭을해야한다, 자바는 단지 하나의 서명 제공하지만 일반적으로 부호의 int이 필요하다고

Answer 3

예 그렇습니다. SHA-1 해시를 계산하려면 한 번에 512 비트 (64 바이트) 블록 만 읽을 필요가 있습니다.

스트림 길이를 추적하고 마지막 하나 또는 두 개의 블록에서 올바른 패딩을 수행해야하지만 완벽하게 실행 가능해야합니다.

이전에 C++로 작성한 적이 있지만 배포가 자유롭지 않습니다.

Answer 4

SHA-1은 블록 단위로 데이터를 처리하므로 파일을 스트림으로 처리 할 수 ​​있습니다. 탄력성이 강한 성 암호 라이브러리가 데이터를 스트리밍 할 수있을만큼 낮은 수준에서 SHA-1을 구현한다고 확신합니다. 탄탄한 성 crypto 라이브러리를 사용하여 다른 블록 cyphers를 사용하여 매우 비슷한 작업을 수행했습니다.

http://www.bouncycastle.org/

Answer 5

자바 문서는 임의의 크기의 데이터에 SHA-1을 계산하기 위해 MessageDigest 클래스를 사용 말한다.

Answer 6

DigestInputStream 또는 DigestOutputStream 클래스를 사용하면 투명하고 거의 쉽게이 작업을 수행 할 수 있습니다. 또는 수동으로 MessageDigest을 사용할 수 있으며 거의 ​​쉽습니다.