在 Perl 中实现 SHA-256

Question

我正在努力实现SHA-256算法。我在消息的填充方面遇到问题。对于 SHA-256，您必须在消息末尾附加一点，到目前为止我已经通过$message .= (chr 0x80);下一步应该是用 0 填充 emtpy 空间（512 位块）。我用这个公式计算了它：l+1+k=448-l，然后将其附加到消息中。我的问题是现在来了：在最后 64 位块中附加消息长度的二进制表示，并再次用 0 填充其余部分。由于perl自己处理它们的数据类型，所以没有"字节"数据类型。如何确定应追加哪个值？

另请参阅官方规范：http://csrc.nist.gov/publications/fips/fips180-3/fips180-3_final.pdf

Answer 1

如果可能的话，从架子上拿出一些东西。您不想推出自己的SHA-256实施，因为要获得官方的认可，您必须对其进行认证。

也就是说，规范是

5.1.1 SHA-1、SHA-224和SHA-256

假设消息的长度 M 为 l 位。将位1附加到消息的末尾，后跟 k 个零位，其中 k 是方程的最小非负解

L + 1 + K ≡ 448 mod 512

然后附加等于使用二进制表示表示的数字 l 的 64 位块。例如，（8 位 ASCII） 消息"abc"的长度为 8 × 3 = 24，因此消息填充了一位，然后填充了 448 - （24 + 1） = 423 个零位，然后是消息长度，成为 512 位填充消息

                                  423       64
                                 .-^-.  .---^---.
01100001  01100010  01100011  1  00…00  00…011000
   “a”       “b”       “c”                  '-v-'
                                             l=24

然后，填充消息的长度现在应该是 512 位的倍数。

您可能会想使用vec，因为它允许您处理单个位，但您必须解决时髦的寻址问题。

如果位为 4 或更小，则字符串被分解为字节，然后每个字节的位被分成 8/位组。字节的位以小端序的方式编号，如0x01、0x02、0x04、0x08、0x10、0x20、0x40、0x80。例如，将单个输入字节chr(0x36)分成两组会给出一个列表(0x6, 0x3);将其分成 4 组给出(0x2, 0x1, 0x3, 0x0) .

相反，B*的pack模板指定

位字符串（每个字节内的降序位顺序）。

和N

按"网络"（大端序）顺序排列的无符号长（32 位）。

后者对于组装消息长度很有用。尽管pack具有 quad 的 Q 参数，但结果按本机顺序排列。

从一些准备工作开始

our($UPPER32BITS,$LOWER32BITS);
BEGIN {
  use Config;
  die "$0: $^X not configured for 64-bit ints"
    unless $Config{use64bitint};
  # create non-portable 64-bit masks as constants
  no warnings "portable";
  *UPPER32BITS = xffff_ffff_0000_0000;
  *LOWER32BITS = x0000_0000_ffff_ffff;
}

然后，您可以将pad_message定义为

sub pad_message {
  use bytes;
  my($msg) = @_;
  my $l = bytes::length($msg) * 8;
  my $extra = $l % 512;  # pad to 512-bit boundary
  my $k = 448 - ($extra + 1);
  # append 1 bit followed by $k zero bits
  $msg .= pack "B*", 1 . 0 x $k;
  # add big-endian length
  $msg .= pack "NN", (($l & $UPPER32BITS) >> 32), ($l & $LOWER32BITS);
  die "$0: bad length: ", bytes::length $msg
    if (bytes::length($msg) * 8) % 512;
  $msg;
}

假设代码打印填充的消息

my $padded = pad_message "abc";
# break into multiple lines for readability
for (unpack("H*", $padded) =~ /(.{64})/g) {
  print $_, "n";
}

然后输出为

61626380000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000018

与规格相匹配。

Answer 2

首先，

我希望你这样做只是一个练习——核心中有一个Digest模块，它已经很好地计算了 SHA-256。

请注意，$message .= (chr 0x80);附加一个字节，而不是一个位。如果确实需要按位操作，请查看vec函数。

要获取 intger 的二进制表示形式，您应该使用 pack。要使其达到 64 位，请执行类似操作

$message .= pack 'Q', length($message)

请注意，"Q"格式仅在 64 位 perls 上可用;如果你的格式不是，只需将四个 0 字节与 32 位值连接起来（包格式 L ）。