用PHP实现自己的sha-256哈希算法!

哈希 又称作 “散列”,它接收任何一组任意长度的输入信息,通过 哈希 算法变换成固定长度的数据指纹,该指纹就是 哈希值。总体而言,哈希 可理解为一种消息摘要。

哈希 又称作 “散列”,它接收任何一组任意长度的输入信息,通过 哈希 算法变换成固定长度的数据指纹,该指纹就是 哈希值。总体而言,哈希 可理解为一种消息摘要。

在 PHP 中有这个函数 hash(),可以计算字符串的哈希值,出于好奇我 Google 了一下哈希计算的具体步骤,并使用 PHP 编写了一套计算 sha-256 哈希值的代码。当然除了 sha-256 以外还有一些别的哈希算法,只是目前 sha-256 用的多一些。下面是目前 美国国家标准与技术研究院 发布哈希算法:

哈希算法输入大小(bits)分块大小(bits)行大小(bits)生成二进制长度(bits)生成十六进制长度(chars)
sha1 < 2^64 512 32 160 40
sha-224 < 2^64 512 32 224 56
sha-256 < 2^64 512 32 256 64
sha-384 < 2^128 1024 64 384 96
sha-512 < 2^128 1024 64 512 128
sha-512/224 < 2^128 1024 64 224 56
sha-512/256 < 2^128 1024 64 256 64

在编写过程中我主要参考了以下文档和站点:

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/

本文内容较多,主要分为下面这几个部分,读者阅读时可以先跳过 准备二:助手方法 直接进入 步骤 部分,在阅读 步骤 部分需要用到指定方法时再回过头来查阅 准备二:助手方法 中的函数。

  • 准备一:代码主体

  • 准备二:助手方法(阅读时可先跳过)

  • 步骤一:字符串转二进制

  • 步骤二:追加数字 1

  • 步骤三:填充至 512 的倍数

  • 步骤四:追加原始长度信息

  • 步骤五:切分区块并填充至 2048 位

  • 步骤六:区块数据修改

  • 步骤七:压缩

准备一:代码主体

我们创建一个类 Algorithm 来存放我们计算哈希所需要用到的方法和属性。这个类中只有一个 public 的方法 sha256(),此方法传入一个字符串参数,输出此字符串的 sha-256 哈希值。要完成我们的哈希计算,总共需要经过七个步骤,我们先把这七个步骤的调用写到 sha256() 的函数体中。

<?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();
}
}

除了 sha256() 这个函数外, 我们要需要几个成员属性来保存计算过程中产生的数据。

$originLen 属性用于记录字符串被转化为二进制之后的原始长度,这个长度值后续会追加到数据中去。

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

$bits 属性用于储存字符串转化后得到的二进制数据。

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

$blocks 存放分块后的二进制数据。

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

H 哈希计所需的常量,hash-256 的 8 个哈希常量是质数 2、3、5、7、11、13、17、19 各自平方根取二进制小数部分前 32 位所得。

/** @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位
];

对于上面这几个常量,感兴趣的同学也可以自己计算得到,我这里只提供一个简单的计算示例,以质数 2 为例,我们先通过计算器得到它的平方根:1.4142135623730950488016887242097 然后只取小数部分:0.4142135623730950488016887242097,接着将这个十进制的小数转为二进制,转为流程如下:

小数转二进制
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
. . .

上面计算得到的小数部分二进制,取前 32 位:01101010 00001001 11100110 01100111,转为十六进制表示:0x6a09e667,其他几个质数的计算也是类似。当然由于是常量,值是固定不变的,所以我们只要知道其计算原理即可。

和上面的平方根常量类似,hash-256 的另外 64 个常量是质数 2、3、5、…、311 各自立方根取二进制小数部分前 32 位。

/** @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位
}

打印二进制数组,用于调试用途,每 8 位会补一个空格,每 32 位补两个空格,每 64 位换一行,每 512 位空一行,让打印的数据更容易查看。

/**
* 打印二进制数组
* @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; 字符串来演示整个哈希计算过程。我们可以先用 PHP 内置的哈希函数将结果算出来, ;hello world; 的哈希值是 ;b94d27b9934d3e08a52e52d7da7dabfac484efe37a5380ee9088f7ace2efcde9;,到最后我们计算出来的哈希值如果等于这个值则说明我们的计算逻辑是正确的。

首先我们把 ;hello world; 拆成一个个的字符,每个字符都有对应一个 ASCII 码值,这些 ASCII 码值都是 0-256 的整数。使用 PHP 的 ord() 函数可以把这些字符转为整数,再将这些整数转为对应的二进制并存储到属性 $bits 中。并将此时 $bits 的长度值保存到 $originLen 属性里。

;hello world; 转为二进制后的数据是:

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

步骤二:追加数字 1

接着在二进制数组的末尾添加一个 1。

$bits
01101000 01100101 01101100 01101100 01101111 00100000 01110111 01101111
01110010 01101100 01100100 1/**
* 步骤二:在最后面追加一个1
*/
public function step2_append_1(): void
{
$this->bits[] = 1;
}

步骤三:填充至 512 的倍数

在二进制数组的末尾添加 0 以使得整个二进制数组的个数刚好是 512 的倍数。需要注意的是,二进制数组的最末尾要预留 64 位用于存放原始二进制的长度。也就是一开始将字符串转换成二进制时的长度,我们在 步骤一 中将这个长度值保存到了 $originLen 属性里。

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

步骤四:追加原始长度信息

把之前记录的原始数据长度 $originLen 转换为 64 位的二进制追加到 $bits 末尾。

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

步骤五:切分区块并填充至 2048 位

经过 步骤四 之后,$bits 二进制数组的个数已经是 512 的倍数,现在以每 512 位分为一个区块,然后在每个区块末尾填充 0,让每个区块的大小变成 2048 位。每个区块的 2048 位数据以 32 位作为一行,那么就有 64 行。由于 ;hello world; 数据比较短,我们就只有一个区块。

-$blocks[0]$blocks[0]-
02468101214161820222426283032343638404244464850525456586062 01101000 01100101 01101100 0110110001110010 01101100 01100100 1000000000000000 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 00000000 01101111 00100000 01110111 0110111100000000 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 0101100000000000 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 00000000 13579111315171921232527293133353739414345474951535557596163

/**
* 步骤五:每一个512位切分区块,在区块末尾填充0,使得每个区块位数为2048位,经计算
* 每个区块还需要添加48×32个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);
}
}

步骤六:区块数据修改

上一步中我们给每一个区块末尾添加了很多 0,在这一步中,通过一些位操作将这些数据进一步调整。按 32 位为一行,我们需要修改新增加的 16-63 行的数据。修改的逻辑如下:

算法逻辑

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

其中 w 是每个区块的行数组,w[i] 就是第 i 行。

rightshift 是右移,rightrotate 是旋转右移, xor 是异或。

这里以第 16 行的处理为例:

算法详解

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】行就是上一步新增的48×32个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–;
}
}
}
}

步骤七:压缩

新建变量 $a、$b、$c、$d、$e、$f、$g、$h 值依次分别等于哈希常量 H[0-7],接着循环每一个区块的每一行,通过 与 非 异或 等操作将信息压缩到 $a、$b、$c、$d、$e、$f、$g、$h 中,最后将 $a、$b、$c、$d、$e、$f、$g、$h 的值与原始常量 H[0-7] 相加,拼接相加后的二进制结果 h0~h7 并转化为十六进制字符串得到最终的哈希值。

具体的压缩算法如下:

算法逻辑

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

这里以第 0 行的处理为例,列出了变量计算结果方便大家对照调试:

计算结果

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

至此整个哈希 sha-256 计算流程就完成了, 计算得到的哈希值也与 PHP 自带的 hash() 函数计算结果一致。

php哈希表及数组的介绍(附代码)

本篇文章给大家带来的内容是关于php哈希表及数组的介绍(附代码),有一定的参考价值,有需要的朋友可以参考一下,希望对你有所帮助。

数组是PHPer最常用的数据类型,同时php容易上手也得益于其强大的数组,但是数组在php中是如何实现的呢?

首先,我们还是先了解下相关的数据结构,为下面的内容打好基础

哈希表

哈希表,顾名思义,即将不同的关键字映射到不同单元的一种数据结构。而将不同关键字映射到不同单元的方法就叫做哈希函数

理想情况下,经过哈希函数处理,关键字和单元是会进行一一对应的;但是如果关键字值足够多的情况下,就容易出现多个关键字映射到同一单元的情况,即出现哈希冲突

哈希冲突的解决方案,要么使用链接法,要么使用开放寻址法

链接法即当不同的关键字映射到同一单元时,在同一单元内使用链表来保存这些关键字

开放寻址法即当插入数据时,如果发现关键字被映射到的单元存在数据了,说明发生了冲突,就继续寻找下一个单元,直到找到可用单元为止

而因为开放寻址法方案属于占用其他关键字映射单元的位置,所以后续的关键字更容易出现哈希冲突,因此容易出现性能下降

链表

既然上面提到了链表,这里我们简单聊一下链表的基础知识。链表分为很多种类型,常用的数据结构包括:队列,栈,双向链表等

链表,就是由不同的链表节点组成的一种数据结构。链表节点一般由元素+指向下一节点的指针组成。而双向链表,顾名思义,则是由指向上一节点的指针+元素+指向下一节点的指针组成

对于数据结构的内容,我们不过多展开,我们之后会有专门的内容去详细介绍数据结构

php数组

php解决哈希冲突的方式是使用了链接法,所以php数组是由哈希表+链表实现,准确来说,是由哈希表+双向链表实现

内部结构-哈希表

HashTable结构体主要用来存放哈希表的基本信息

typedef struct _hashtable {
uint nTableSize; // hash Bucket的大小,即哈希表的容量,最小为8,以2x增长。
uint nTableMask; // nTableSize-1 , 索引取值的优化
uint nNumOfElements; // hash Bucket中当前存在的元素个数,count()函数会直接返回此值
ulong nNextFreeElement; // 下一个可使用的数字键值
Bucket *pInternalPointer; // 当前遍历的指针(foreach比for快的原因之一)
Bucket *pListHead; // 存储整个哈希表的头元素指针
Bucket *pListTail; // 存储整个哈希表的尾元素指针
Bucket **arBuckets; // 存储hash数组
dtor_func_t pDestructor; // 在删除元素时执行的回调函数,用于资源的释放
zend_bool persistent; //指出了Bucket内存分配的方式。如果persisient为TRUE,则使用操作系统本身的内存分配函数为Bucket分配内存,否则使用PHP的内存分配函数。
unsigned char nApplyCount; // 标记当前hash Bucket被递归访问的次数(防止多次递归)
zend_bool bApplyProtection;// 标记当前hash桶允许不允许多次访问,不允许时,最多只能递归3次
#if ZEND_DEBUG
int inconsistent;
#endif
} HashTable;

Bucket结构体则用于保存数据的具体内容

typedef struct bucket {
ulong h;// 对char *key进行hash后的值,或者是用户指定的数字索引值
uint nKeyLength; // hash关键字的长度,如果数组索引为数字,此值为0
void *pData; // 指向value,一般是用户数据的副本,如果是指针数据,则指向pDataPtr
void *pDataPtr; // 如果是指针数据,此值会指向真正的value,同时上面pData会指向此值
struct bucket *pListNext; // 指向整个哈希表的该单元的下一个元素
struct bucket *pListLast; // 指向整个哈希表的该单元的上一个元素
struct bucket *pNext; // 指向由于哈希冲突导致存放在同一个单元的链表中的下一个元素
struct bucket *pLast; // 指向由于哈希冲突导致存放在同一个单元的链表中的上一个元素
// 保存当前值所对于的key字符串,这个字段只能定义在最后,实现变长结构体
char arKey[1];
} Bucket;

其中Bucket结构体内有指向用户数据的pData元素,其实是指向了之前我们介绍的变量zval结构体,这也是为什么当创建数组时,会出现数组元素+1的变量容器。

哈希表内部结构关系图

用PHP实现自己的sha-256哈希算法!

注:图片来源于网络

从上图我们可以看出,Bucket在存放数据的时候,如果存在哈希冲突,则将多个关键字映射到链表中,由此组成了双向链表

总结

今天,我们以数组作为切入点,简单了解了下基本的数据结构:哈希表和链表;并且了解了数组的底层实现,即哈希表+双向链表。其实哈希表作为php中最重要的数据结构,用处很广。

【相关推荐:PHP视频教程】

以上就是php哈希表及数组的介绍(附代码)的详细内容,更多请关注钦钦技术栈其它相关文章!

转载至:php中文网【www.php.cn】

版权声明:本文(即:原文链接:https://www.qin1qin.com/catagory/23447/)内容由互联网用户自发投稿贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至 630367839@qq.com 举报,一经查实,本站将立刻删除。

(0)
上一篇 2022-09-19 12:51:30
下一篇 2022-09-19 12:54:17

软件定制开发公司

相关阅读

发表回复

登录后才能评论
通知:禁止投稿所有关于虚拟货币,币圈类相关文章,发现立即永久封锁账户ID!