用PHP實作自己的sha-256哈希演算法！

Lane Wagner - How SHA-256 Works Step-By-Step：https://blog.boot.dev/cryptography/how-sha-2-works-step-by-step-sha-256/
Secure Hash Standard (SHS) - FIPS 180-4（官方文档）：https://csrc.nist.gov/publications/detail/fips/180/4/final
ASCII Table：https://www.asciitable.com/

<?php 
declare(strict_types=1);
class Algorithm
{
    public function sha256(string $str): string
    {
        // 步骤一：将字符串转化为二进制
        $this->step1_convert_str_to_bits($str);
        // 步骤二：在最后面追加一个1
        $this->step2_append_1();
        // 步骤三：在数据末尾添加0，确保二进制的个数是512的倍数，最后预留64位用于存储原始长度信息
        $this->step3_extend_to_multiple_of_512();
        // 步骤四：把原始字符串位长度，填充到预留在最后的64位（8个字节的长整型）中
        $this->step4_append_origin_length();
        // 步骤五：每一个512位切分区块，在区块末尾填充0，使得每个区块位数为2048位，需要增加48行（32位一行）
        $this->step5_split_blocks_and_append_48_lines();
        // 步骤六：针对每一个2048位区块处理：以32位为一行，总共有64行，修改【16-63】行的数据
        $this->step6_modify_blocks_appended_48_lines();
        // 步骤七：压缩数据，生成最终的哈希值
        return $this->step7_compress_to_final_hash();
    }
}

/** @var int 原始数据的二进制长度  */
private int $originLen = 0;

/** @var array 存储二进制数组 */
private array $bits;

/** @var array 二进制区块 */
private array $blocks;

/** @var array 质数平方根常量 */
private const H = [
    0x6a09e667, // 质数2的平方根取二进制小数部分前32位
    0xbb67ae85, // 质数3的平方根取二进制小数部分前32位
    0x3c6ef372, // 质数5的平方根取二进制小数部分前32位
    0xa54ff53a, // 质数7的平方根取二进制小数部分前32位
    0x510e527f, // 质数11的平方根取二进制小数部分前32位
    0x9b05688c, // 质数13的平方根取二进制小数部分前32位
    0x1f83d9ab, // 质数17的平方根取二进制小数部分前32位
    0x5be0cd19, // 质数19的平方根取二进制小数部分前32位
];

小数转二进制
                            0.
0.4142135623730950488016887242097 x 2 => 0
0.8284271247461900976033774484194 x 2 => 1
0.6568542494923801952067548968388 x 2 => 1
0.3137084989847603904135097936776 x 2 => 0
0.6274169979695207808270195873552 x 2 => 1
0.2548339959390415616540391747104 x 2 => 0
0.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ x 2 => 1
0.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ x 2 => 0
0.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ x 2 => 0
0.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ x 2 => 0
0.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ x 2 => 0
0.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ x 2 => 0
0.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ x 2 => 1
0.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ x 2 => 0
0.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ x 2 => 0
0.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ x 2 => 1
0.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ x 2 => 1
0.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ x 2 => 1
0.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ x 2 => 1
0.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ x 2 => 0
0.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ x 2 => 0
. . .

/** @var array 质数立方根常量 */
private const K = [
    0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
    0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
    0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
    0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
    0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
    0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
    0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
    0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2,
];

/**
 * 十进制整数转化为二进制数组
 * @param int $num 十进制整数
 * @param int $fillTo 填充到多少位，不够的用0来补齐
 */
public function int2bits(int $num, int $fillTo = 0): array
{
    $bits = str_split(decbin($num));
    array_walk($bits, function (&$val) {
        $val = intval($val);
    });
    for ($len = count($bits); $len < $fillTo; $len++) {
        array_unshift($bits, 0);
    }
    return $bits;
}

/**
 * 二进制数组向右移动
 * @param array $bits 二进制数组
 */
public function rightShift(array $bits, int $move): array
{
    $len = count($bits);
    $move = $move % $len;
    if ($move <= 0) return $bits;
    return array_merge(array_fill(0, $move, 0), array_slice($bits, 0, $len-$move));
}

/**
 * 二进制数组向右旋转
 * @param array $bits 二进制数组
 */
public function rightRotate(array $bits, int $move): array
{
    $len = count($bits);
    $move = $move % $len;
    if ($move <= 0) return $bits;
    return array_merge(array_slice($bits, $len-$move, $move), array_slice($bits, 0, $len-$move));
}

/**
 * 二进制数组求非
 * @param array $bits 二进制数组
 */
public function not(array $bits): array
{
    for ($i = count($bits)-1; $i >= 0; $i--) {
        $bits[$i] = ($bits[$i] == 0) ? 1 : 0;
    }
    return $bits;
}

/**
 * 二进制数组求与
 * @param array $args 二进制数组
 */
public function and(array ...$args): array
{
    $argc = count($args);
    if ($argc == 0) return [];
    for ($i = 1; $i < $argc; $i++) {
        $j = count($args[0]) - 1;
        $k = count($args[$i]) - 1;
        while ($j >= 0 || $k >= 0) {
            $j < 0 and array_unshift($args[0], 0) and $j = 0; // 如果是$args[0]不够长就头插补齐
            ($args[$i][$k] ?? 0) == 0 and $args[0][$j] = 0;
            $j--;
            $k--;
        }
    }
    return $args[0];
}

/**
 * 二进制数组求异或
 * @param array $args 二进制数组
 */
public function xor(array ...$args): array
{
    $argc = count($args);
    if ($argc == 0) return [];
    for ($i = 1; $i < $argc; $i++) {
        $j = count($args[0]) - 1;
        $k = count($args[$i]) - 1;
        while ($j >= 0 || $k >= 0) {
            $j < 0 and array_unshift($args[0], 0) and $j = 0; // 如果是$args[0]不够长就头插补齐
            $args[0][$j] = intval($args[0][$j] != ($args[$i][$k] ?? 0));
            $j--;
            $k--;
        }
    }
    return $args[0];
}

/**
 * 二进制数组相加
 * @param array $args 二进制数组
 */
public function add(array ...$args): array
{
    $argc = count($args);
    if ($argc == 0) return [];
    for ($i = 1; $i < $argc; $i++) {
        $carry = 0;
        $j = count($args[0]) - 1;
        $k = count($args[$i]) - 1;
        while ($j >= 0 || $k >= 0) {
            $j < 0 and array_unshift($args[0], 0) and $j = 0; // 如果是$args[0]不够长就头插补齐
            $carry += $args[0][$j] + ($args[$i][$k] ?? 0);
            switch ($carry) {
                case 1: $carry = 0; $args[0][$j] = 1; break;
                case 2: $carry = 1; $args[0][$j] = 0; break;
                case 3: $carry = 1; $args[0][$j] = 1; break;
            }
            $j--;
            $k--;
        }
        $carry == 1 and array_unshift($args[0], $carry); // 计算完后还有进位则加长存放
    }
    return array_slice($args[0], -32); // 计算结果只保留32位
}

/**
 * 打印二进制数组
 * @param array $bits 二进制数组
 */
public function printBits(array $bits): void
{
    $len = 0;
    foreach ($bits as $bit) {
        if ($len > 0) {
            if ($len % 512 == 0) echo PHP_EOL;
            if ($len % 64 == 0) {
                echo PHP_EOL;   
            } else {
                if ($len % 32 == 0) echo ' ';
                if ($len % 8 == 0) echo ' ';
            }
        }
        echo $bit;
        $len++;
    }
    echo PHP_EOL;
}

/**
 * 二进制数组转化为十六进制
 * @param array $bits 二进制数组
 */
public function bits2hex(array $bits): string
{
    $str = '';
    for ($i = count($bits)-1; $i >= 0; $i -= 4) {
        $dec = $bits[$i] + ($bits[$i-1] ?? 0)*2 + ($bits[$i-2] ?? 0)*4 + ($bits[$i-3] ?? 0)*8;
        switch ($dec) {
            case 0:  $str = '0' . $str; break;
            case 1:  $str = '1' . $str; break;
            case 2:  $str = '2' . $str; break;
            case 3:  $str = '3' . $str; break;
            case 4:  $str = '4' . $str; break;
            case 5:  $str = '5' . $str; break;
            case 6:  $str = '6' . $str; break;
            case 7:  $str = '7' . $str; break;
            case 8:  $str = '8' . $str; break;
            case 9:  $str = '9' . $str; break;
            case 10: $str = 'a' . $str; break;
            case 11: $str = 'b' . $str; break;
            case 12: $str = 'c' . $str; break;
            case 13: $str = 'd' . $str; break;
            case 14: $str = 'e' . $str; break;
            case 15: $str = 'f' . $str; break;
        }
    }
    return $str;
}

“hello world”
01101000 01100101 01101100 01101100  01101111 00100000 01110111 01101111
01110010 01101100 01100100

/**
 * 步骤一：将字符串转化为二进制
 * @param string $str 原始字符串
 */
public function step1_convert_str_to_bits(string $str): void
{
    $this->bits = [];
    $chars = str_split($str);
    foreach ($chars as $char) {
        $this->bits = array_merge($this->bits, $this->int2bits(ord($char), 8));
    }
    $this->originLen = count($this->bits);
}

$bits
01101000 01100101 01101100 01101100  01101111 00100000 01110111 01101111
01110010 01101100 01100100 1

$bits
01101000 01100101 01101100 01101100  01101111 00100000 01110111 01101111
01110010 01101100 01100100 10000000  00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000  00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000  00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000  00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000  00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000  00000000 00000000 00000000 00000000
[    预留 64 位用于存储原始字符串的长度    ]

/**
 * 步骤三：在数据末尾添加0，确保二进制的个数是512的倍数，最后预留64位用于存储原始长度信息
 */
public function step3_extend_to_multiple_of_512(): void
{
    $rem = (count($this->bits) + 64) % 512;
    if ($rem > 0) {
        while ($rem < 512) {
            $this->bits[] = 0;
            $rem++;
        }
    }
}

$bits
01101000 01100101 01101100 01101100  01101111 00100000 01110111 01101111
01110010 01101100 01100100 10000000  00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000  00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000  00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000  00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000  00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000  00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000  00000000 00000000 00000000 01011000

/**
 * 步骤四：把原始字符串位长度，填充到预留在最后的64位（8个字节的长整型）中
 */
public function step4_append_origin_length(): void
{
    $this->bits = array_merge($this->bits, $this->int2bits($this->originLen, 64));
}

/**
 * 步骤五：每一个512位切分区块，在区块末尾填充0，使得每个区块位数为2048位，经计算
 * 每个区块还需要添加48x32个0
 */
public function step5_split_blocks_and_append_48_lines(): void
{
    $this->blocks = [];
    $append = $this->int2bits(0, 48 * 32);
    $len = count($this->bits);
    for ($i = 0; $i < $len; $i += 512) {
        $this->blocks[] = array_merge(array_slice($this->bits, $i, 512), $append);
    }
}

For i from w[16…63]:
    s0 = (w[i-15] rightrotate 7) xor (w[i-15] rightrotate 18) xor (w[i-15] rightshift 3)
    s1 = (w[i-2] rightrotate 17) xor (w[i- 2] rightrotate 19) xor (w[i- 2] rightshift 10)
    w[i] = w[i-16] + s0 + w[i-7] + s1

i = 16
(w[1] rightrotate 7) = 01101111001000000111011101101111 -> 11011110110111100100000011101110
(w[1] rightrotate 18) = 01101111001000000111011101101111 -> 00011101110110111101101111001000
(w[1] rightshift 3) = 01101111001000000111011101101111 -> 00001101111001000000111011101101
s0 = (w[1] rightrotate 7) xor (w[1] rightrotate 18) xor (w[1] rightshift 3)
 = 11001110111000011001010111001011
(w[14] rightrotate 17) = 00000000000000000000000000000000 -> 00000000000000000000000000000000
(w[14] rightrotate 19) = 00000000000000000000000000000000 -> 00000000000000000000000000000000
(w[14] rightshift 10) = 00000000000000000000000000000000 -> 00000000000000000000000000000000
s1 = (w[14] rightrotate 17) xor (w[14] rightrotate 19) xor (w[14] rightshift 10)
= 00000000000000000000000000000000
w[i] = w[0] + s0 + w[9] + s1
= 00110111010001110000001000110111（相加得到的值如果超过 32 位，则抹去高位）
/**
 * 步骤六：针对每一个2048位区块处理：以32位为一行，总共有64行，修改【16-63】行的数据，
 * 这【16-63】行就是上一步新增的48x32个0
 */
public function step6_modify_blocks_appended_48_lines(): void
{
    foreach ($this->blocks as &$block) {
        for ($i = 16; $i < 64; $i++) {
            $w0 = array_slice($block, ($i-16)*32, 32);
            $w1 = array_slice($block, ($i-15)*32, 32);
            $w9 = array_slice($block, ($i-7)*32, 32);
            $w14 = array_slice($block, ($i-2)*32, 32);
            $s0 = $this->xor(                
                $this->rightRotate($w1, 7),
                $this->rightRotate($w1, 18),
                $this->rightShift($w1, 3)
            );
            $s1 = $this->xor(
                $this->rightRotate($w14, 17),
                $this->rightRotate($w14, 19),
                $this->rightShift($w14, 10)
            );
            $wi = $this->add($w0, $s0, $w9, $s1);
            // 如果$wi的长度超过了32位，则只取32位，舍弃高位
            $k = count($wi) - 1;
            for ($j = $i * 32 + 31; $j >= $i * 32; $j--) {
                $block[$j] = $wi[$k] ?? 0;
                $k--;
            }
        }
    }
}

For i from 0 to 63
    s1 = (e rightrotate 6) xor (e rightrotate 11) xor (e rightrotate 25)
    ch = (e and f) xor ((not e) and g)
    temp1 = h + s1 + ch + k[i] + w[i]
    s0 = (a rightrotate 2) xor (a rightrotate 13) xor (a rightrotate 22)
    maj = (a and b) xor (a and c) xor (b and c)
    temp2 := s0 + maj
    h = g
    g = f
    f = e
    e = d + temp1
    d = c
    c = b
    b = a
    a = temp1 + temp2

i = 0
s1 = 00110101100001110010011100101011
ch = 00011111100001011100100110001100
temp1 = 01011011110111010101100111010100
s0 = 11001110001000001011010001111110
maj = 00111010011011111110011001100111
temp2 = 00001000100100001001101011100101
h = 00011111100000111101100110101011
g = 10011011000001010110100010001100
f = 01010001000011100101001001111111
e = 00000001001011010100111100001110
d = 00111100011011101111001101110010
c = 10111011011001111010111010000101
b = 01101010000010011110011001100111
a = 01100100011011011111010010111001

/**
 * 步骤七：压缩数据
 */
public function step7_compress_to_final_hash(): string
{
    $a = $h0 = $this->int2bits(static::H[0], 32);
    $b = $h1 = $this->int2bits(static::H[1], 32);
    $c = $h2 = $this->int2bits(static::H[2], 32);
    $d = $h3 = $this->int2bits(static::H[3], 32);
    $e = $h4 = $this->int2bits(static::H[4], 32);
    $f = $h5 = $this->int2bits(static::H[5], 32);
    $g = $h6 = $this->int2bits(static::H[6], 32);
    $h = $h7 = $this->int2bits(static::H[7], 32);
    foreach ($this->blocks as $block) {
        for ($i = 0; $i < 64; $i++) {
            $s1 = $this->xor(
                $this->rightRotate($e, 6),
                $this->rightRotate($e, 11),
                $this->rightRotate($e, 25)
            );
            $ch = $this->xor(
                $this->and($e, $f),
                $this->and($this->not($e), $g)
            );
            $ki = $this->int2bits(static::K[$i], 32);
            $wi = array_slice($block, $i*32, 32);
            $temp1 = $this->add($h, $s1, $ch, $ki, $wi);
            $s0 = $this->xor(
                $this->rightRotate($a, 2),
                $this->rightRotate($a, 13),
                $this->rightRotate($a, 22),
            );
            $maj = $this->xor(
                $this->and($a, $b),
                $this->and($a, $c),
                $this->and($b, $c)
            );
            $temp2 = $this->add($s0, $maj);
            $h = $g;
            $g = $f;
            $f = $e;
            $e = $this->add($d, $temp1);
            $d = $c;
            $c = $b;
            $b = $a;
            $a = $this->add($temp1, $temp2);
        }
    }
    $h0 = $this->add($h0, $a);
    $h1 = $this->add($h1, $b);
    $h2 = $this->add($h2, $c);
    $h3 = $this->add($h3, $d);
    $h4 = $this->add($h4, $e);
    $h5 = $this->add($h5, $f);
    $h6 = $this->add($h6, $g);
    $h7 = $this->add($h7, $h);
    return $this->bits2hex(array_merge($h0, $h1, $h2, $h3, $h4, $h5, $h6, $h7));
}