type
status
date
slug
summary
tags
category
icon
password
Sub-item
Last edited time
Oct 28, 2023 10:43 AM
Parent item
领域
Toeplitz矩阵
满足的矩阵就是ToePlitz矩阵。
举例：如果输入的Toeplitz密钥是，那么生成的Toeplitz矩阵是一个的矩阵：
二进制数据的分布是从到，再从到。
对称Toeplitz-Hash的计算公式
：Hash值的位数
：输入数据的位数
：Toeplitz秘钥(根据输入的随机数生成)的位数，满足
：Hash值的第位
：输入数据的第位
：Toeplitz秘钥的第位
计算Hash的伪代码如下：
= 0
也可以表示为：
= 0
展开后就是：
…
注意到在GF(2)中，“与”就是乘法(二进制 )，“异或”就是加法(二进制 )
…
所以上述代码可以表示为数学公式：
用矩阵表示就是：
使用GFNI指令计算Toeplitz Hash
GFNI指令的使用例子GFNI指令是计算[8*8]和[8*1]的乘积，不能直接用于计算Toeplitz Hash，因此可以将哈希密钥表示为具有 m/8 x n/8 个元素的矩阵，其中每个元素本身是一个 8x8 位矩阵。以同样的方式，输入值可以表示为 m/8 个元素的向量，其中每个元素是一个 8 位向量。图中就是8x8 位矩阵
计算hash的公司变为：
例子：对12字节长度数据计算4字节长度的Hash
正常是需要用48个矩阵来计算， 实际不重复的矩阵只有15个， 和k0相乘的只有t0，和k1相乘的只有t1和t0，和k2相乘的只有t2和t1和t0，依次类推，一个矩阵最多和4个ti相乘。
12个t可以用4个位来编号，因此，每个矩阵最多需要4*4=16位就能表示出和他相乘的t的索引，考虑字节对齐，直接使用32位来存储t的索引，而15个矩阵也对齐到，因此，最多只需要32*16=512位来存储矩阵k和t的关系就行，如下图：
具体实现
以DPDK中的源码为例；
LFSR-Toeplitz Hash
计算过程如下：
- 随机数是
- D是最终的Hash值
参考资料
c语言软件实现ToeplitzHash
intel内建扩展指令参考
指令中文翻译