SHA-256 by hand, calculating the SHA-256 initial words

Question

I am reading the publication FIPS 180-4 and trying to implement SHA-256 on my own. On the page 15, title 5.3.3 SHA-256 we have an initialization of initial hash values:

5.3.3 SHA-256

For SHA-256, the initial hash value, H(0), shall consist of the following eight 32-bit words, in hex:

H0 = 6a09e667
H1 = bb67ae85
H2 = 3c6ef372
H3 = a54ff53a
H4 = 510e527f
H5 = 9b05688c
H6 = 1f83d9ab
H7 = 5be0cd19

These words were obtained by taking the first thirty-two bits of the fractional parts of the 
square roots of the first eight prime numbers.

So, I am starting to calculate these numbers on my own and then my question appears. According to Wikipedia : Double-precision floating-point format the number represented in binary as fractional part by 0-51 bits, exponent part by 52-62 bits and sign part by 63 bit. So in order to initialize initial hash values we take first 32 bits of fractional part or in other words 20-51 bits:

H0 = 6a09e667 (hex)
sqrt(2) = 1.4142135623730951 = [0][01111111111][01101010000010011110011001100111|11110011101111001101]
H0 = 01101010000010011110011001100111 (binary)
H0'= 01101010000010011110011001100111 (binary)
H0 == H0' ->  OK 
-------------------
H1 = bb67ae85 (hex)
sqrt(3) = 1.7320508075688772 = [0][01111111111][10111011011001111010111010000101|10000100110010101010]
H1 = 10111011011001111010111010000101 (binary)
H1'= 10111011011001111010111010000101 (binary)
H1 == H1' ->  OK 
-------------------
H2 = 3c6ef372 (hex)
sqrt(5) = 2.23606797749979 = [0][10000000000][00011110001101110111100110111001|01111111010010101000]
H2 = 00111100011011101111001101110010 (binary)
H2'= 00011110001101110111100110111001 (binary)
H2 != H2' ->  SHIFTED! 
-------------------
H3 = a54ff53a (hex)
sqrt(7) = 2.6457513110645907 = [0][10000000000][01010010101001111111101010011101|00101111100011101010]
H3 = 10100101010011111111010100111010 (binary)
H3'= 01010010101001111111101010011101 (binary)
H3 != H3' ->  SHIFTED! 
-------------------
H4 = 510e527f (hex)
sqrt(11) = 3.3166247903554 = [0][10000000000][10101000100001110010100100111111|11010110111100110100]
H4 = 01010001000011100101001001111111 (binary)
H4'= 10101000100001110010100100111111 (binary)
H4 != H4' ->  SHIFTED! 
-------------------
H5 = 9b05688c (hex)
sqrt(13) = 3.605551275463989 = [0][10000000000][11001101100000101011010001000110|00010101100111110011]
H5 = 10011011000001010110100010001100 (binary)
H5'= 11001101100000101011010001000110 (binary)
H5 != H5' ->  SHIFTED! 
-------------------
H6 = 1f83d9ab (hex)
sqrt(17) = 4.123105625617661 = [0][10000000001][00000111111000001111011001101010|11111110110100000111]
H6 = 00011111100000111101100110101011 (binary)
H6'= 00000111111000001111011001101010 (binary)
H6 != H6' ->  SHIFTED! 
-------------------
H7 = 5be0cd19 (hex)
sqrt(19) = 4.358898943540674 = [0][10000000001][00010110111110000011001101000110|01000100110111111001]
H7 = 01011011111000001100110100011001 (binary)
H7'= 00010110111110000011001101000110 (binary)
H7 != H7' ->  SHIFTED! 
-------------------

The question is why some of given binary representations of H in FIPS 180-4 are (seems like) shifted somehow or, I think I am taking fractional parts correctly, but if not - what I am doing wrong?

The code I wrote is below:

package ru.iulgutlin.sha256;

import java.util.Arrays;
import java.util.Objects;

/**
 * Test
 *
 * @author Rail Iulgutlin 1/9/22
 */
public class Test {

    private static final long[] PRIMES = new long[64];

    /**
     * Given H values
     */
    private static final long h0 = 0x6a09e667L;
    private static final long h1 = 0xbb67ae85L;
    private static final long h2 = 0x3c6ef372L;
    private static final long h3 = 0xa54ff53aL;
    private static final long h4 = 0x510e527fL;
    private static final long h5 = 0x9b05688cL;
    private static final long h6 = 0x1f83d9abL;
    private static final long h7 = 0x5be0cd19L;
    private static final long[] h = {h0, h1, h2, h3, h4, h5, h6, h7};

    static {
        initPrimes();
    }

    public static void main(String[] args) {
        long[] s = new long[8];
        for (int i = 0; i < s.length; i++) {
            /**
             * Calculating my own H' values and comparing with given
             */
            double sqrt = Math.sqrt(PRIMES[i]);
            s[i] = firstFractionalParts(sqrt, 32);
            String h = binary(CustomSha256.h[i], 32); // h given binary string representation
            String h_ = binary(s[i], 32); // h' calculated binary string representation
            boolean eq = Objects.equals(h, h_);

            // print result pretty formatted
            print("    H" + i + " = " + Long.toHexString(CustomSha256.h[i]) + " (hex)");
            print("    sqrt(" + PRIMES[i] + ") = " + sqrt +
                    " = " + new StringBuilder(binary(Double.doubleToRawLongBits(sqrt), 64))
                    .insert(0, '[')
                    .insert(2, "][")
                    .insert(15, "][")
                    .insert(49, '|')
                    .insert(70, ']'));
            print("    H" + i + " = " + h + " (binary)");
            print("    H" + i + "'= " + h_ + " (binary)");
            print("    H" + i + (eq ? " == " : " != ") + "H" + i + "' -> " + (eq ? " OK " : " SHIFTED! "));
            print("    -------------------");
        }
    }

    /**
     * Returns first k bits of fractional part bits of d.
     * 
     * Example calling with d = 1.7320508075688772 and k = 32:
     * d = [0][01111111111][10111011011001111010111010000101|10000100110010101010]
     * Returns:
     * [10111011011001111010111010000101]
     *
     * @param d double number
     * @param k number of bits
     * @return first k bits of fractional part bits of d
     */
    private static long firstFractionalParts(double d, int k) {
        // first 12 bits are not fractional
        // Example: given d = [0][01111111111][10111011011001111010111010000101][10000100110010101010] and k = 32
        // first rotate bits to right so that first bit we need will stay in the rightest position
        // we get [10000100110010101010][0][01111111111][10111011011001111010111010000101]
        // second cut everything redundant and return
        // [00000000000000000000][0][00000000000][10111011011001111010111010000101]
        return cut(rotate(Double.doubleToRawLongBits(d), Double.SIZE - 12 - k), k);
    }

    /**
     * Cuts(turns to 0) every bit of b except right k bits.
     * 
     * Example calling with b = 10111011001 = 1497 and k = 4
     * Returns 00000001001 (only 4 right bits remain)
     *
     * @param b bits
     * @param k nuber of bits to remain
     * @return cutted bits
     */
    private static long cut(long b, int k) {
        return b & (-1L >>> (Long.SIZE - k));
    }

    /**
     * Rotates bits right to a given k positions within 64 bits.
     * Example calling with b = 0000000000000000000000000000000000000000000000000000010111011001 = 1497 and k = 3
     * Returns 0010000000000000000000000000000000000000000000000000000010111011 (rotated right to 3 positions)
     *
     * @param bits bits to rotate
     * @param k positions
     * @return rotated value
     */
    private static long rotate(long bits, int k) {
        return ((bits >>> k) | (bits << (Long.SIZE - k)));
    }

    private static String binary(long b, int k) {
        return String.format("%" + k + "s", Long.toBinaryString(b & (-1L >>> (Long.SIZE - k)))).replace(' ', '0');
    }

    private static void initPrimes() {
        int i = 0;
        long k = 0;
        while (i < 64) {
            if (isPrime(k)) {
                PRIMES[i] = k;
                i++;
            }
            k++;
        }
        print("PRIMES : " + Arrays.toString(PRIMES));
    }

    private static boolean isPrime(long a) {
        if (a < 2) return false;
        if (a == 2) return true;
        if (a % 2 == 0) return false;
        for (long i = 3; i * i <= a; i += 2)
            if (a % i == 0) return false;
        return true;
    }

    private static void print(Object o) {
        System.out.println(o);
    }
}

SHA-256 by hand, calculating the SHA-256 initial words

Answers (1)

Related Questions