Sha-256 implementation in perl

Question

I am trying very hard to implement the sha-256 algorithm. I'm having problems filling out a message. for sha-256 you need to add one bit at the end of the message that I have so far done with $message .= (chr 0x80); The next step should be to fill the emtpy space (512 bits) with 0. I calculated it using this formula: l + 1 + k = 448-l and add it to the message. My problem comes now: add the binary representation of the message length in the last 64-bit block and fill in the remaining 0 again. Since perl processes its data types by itself, there is no byte type. How can I determine what value I should add?

see also the official specification: http://csrc.nist.gov/publications/fips/fips180-3/fips180-3_final.pdf

Answer 1

If at all possible, pull something off the shelf. You do not want to roll back your own implementation of SHA-256, because in order to receive an official blessing, you will need to certify it.

However, the specification

5.1.1 SHA-1, SHA-224 and SHA-256

Suppose the message length, M, is 1 bit. Add bit 1 to the end of the message, followed by k zero bits, where k is the smallest non-negative solution to the equation

l + 1 + k & equiv; 448 mod 512

Then add a 64-bit block, which is equal to the number l, expressed using a binary representation. For example, the message (8-bit ASCII) " abc " has a length of 8 × 3 = 24, so the message is filled with one bit, then 448 - (24 + 1) = 423 zero bits, and then the message length to become 512-bit padded message

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

Then the length of the filled message should be a multiple of 512 bits.

You may be tempted to use vec as it allows you to access single bits, but you will have to work with funk addresses.

If the bit is 4 or less, the string is split into bytes, then the bit of each byte is split into 8 / BITS groups. Byte bits are numbered in a small sequence, as in 0x01 , 0x02 , 0x04 , 0x08 , 0x10 , 0x20 , 0x40 , 0x80 . For example, splitting a single input byte chr(0x36) into two groups gives a list (0x6, 0x3) ; dividing it into 4 groups, we obtain (0x2, 0x1, 0x3, 0x0) .

Instead, pack template B* indicates

Bit string (descending bit order within each byte).

and N

Unfamiliar long (32-bit) in the "network" (big-endian) order.

The latter is useful for building message lengths. Although pack has the Q parameter for quad, the result is in native order.

Start with a bit of preparatory work.

 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 = \0xffff_ffff_0000_0000; *LOWER32BITS = \0x0000_0000_ffff_ffff; } 

Then you can define pad_message as

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

Say the code prints the completed message with

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

Then conclusion

  61626380000000000000000000000000000000000000000000000000000000000000
 000000000000000000000000000000000000000000000000000000000000000018 

which meets the specification.

Answer 2

First of all, I hope that you will do this as an exercise - there is a Digest module in the kernel that already calculates SHA-256 very well.

Note that $message .= (chr 0x80); adds one byte, not one bit. If you really need bitwise manipulation, look at the vec function.

To get a binary representation of intger, you must use pack . To get it up to 64 bits do something like

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

Please note that the format "Q" is available only on 64-bit perls; if yours is not alone, just connect four 0-bytes with a 32-bit value (packet format L ).