可以在流上计算 SHA-1 算法吗?内存占用低? [英] Can SHA-1 algorithm be computed on a stream? With low memory footprint?
本文介绍了可以在流上计算 SHA-1 算法吗?内存占用低?的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我正在寻找一种方法来计算非常大文件的 SHA-1 校验和，而不必立即将它们完全加载到内存中.
I am looking for a way to compute SHA-1 checksums of very large files without having to fully load them into memory at once.
我不知道 SHA-1 实现的细节，因此想知道是否有可能做到这一点.
I don't know the details of the SHA-1 implementation and therefore would like to know if it is even possible to do that.
如果您知道 SAX XML 解析器，那么我会寻找类似的东西:通过每次只将一小部分加载到内存中来计算 SHA-1 校验和.
If you know the SAX XML parser, then what I look for would be something similar: Computing the SHA-1 checksum by only always loading a small part into memory at a time.
我发现的所有示例，至少在 Java 中，总是依赖于将文件/字节数组/字符串完全加载到内存中.
All the examples I found, at least in Java, always depend on fully loading the file/byte array/string into memory.
如果您甚至知道实现(任何语言)，请告诉我！
If you even know implementations (any language), then please let me know!
推荐答案
是的，完全有可能.SHA-1 是一种块算法，因此它一次对一个块进行操作.确切的块大小随您生成的散列大小而变化，但它总是很小(例如，20 - 50 字节左右).当然，那是假设您打算包含 SHA-1 256、384 和/或 512(又名 SHA-256、SHA-384 和 SHA-512).如果您只包含原始 160 位版本，则块大小始终为 20 字节(160 位).
Yes, it's entirely possible. SHA-1 is a block algorithm, so it operates on one block at a time. The exact block size varies with the size of hash you're producing, but it's always quite small (e.g., 20 - 50 bytes or so). That, of course, is assuming you mean to include SHA-1 256, 384 and/or 512 (aka SHA-256, SHA-384 and SHA-512). If you're only including the original 160-bit version, then the block size is always 20 bytes (160 bits).
哎呀——重新阅读规范，SHA-1、SHA-224、SHA-256 的块大小为 512 位，SHA-384 和 SHA-512 的块大小为 1024 位.谢谢查尔斯！
oops -- rereading the spec, the block sizes are 512 bits for SHA-1, SHA-224, SHA-256, and 1024 bits for SHA-384 and SHA-512. Thanks Charles!
Edit2:我几乎忘记了他在寻找源代码的部分，而不仅仅是建议.这是一些代码.首先是标题:
I almost forgot about the part where he's looking for source code, not just advice. Here's some code. First a header:
// 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, ' ');
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(' ') << "
";
}
}
#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] << "
";
return false;
}
os << "Message digest Verified.
";
return true;
}
public:
bool operator()(uint32_t *test_val, std::string const &input) {
std::cout << "Testing hashing from string:
"" << input << ""
";
crypto::sha1 hasher1;
std::vector<uint32_t> hash = hasher1(input);
std::cout << "Message digest is:
" << hasher1;
bool verified = verify(test_val, hash, std::cerr);
crypto::sha1 hasher2;
std::cout << "Testing hashing from Stream:
";
std::istringstream buf(input);
hash = hasher2(buf);
std::cout << "Message digest is:
" << 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!
";
else
std::cerr << "Test Failed!
";
}
#elif defined(MAIN)
#include <sstream>
#include <fstream>
#include <iostream>
int main(int argc, char **argv) {
if (argc < 2) {
std::cerr << "Usage: sha1 [filename]
";
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 << "
";
}
}
return 0;
}
#endif
这篇关于可以在流上计算 SHA-1 算法吗?内存占用低?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
