散列算法

Ⅰ 单向散列算法的介绍

单向散列算法，又称hash函数，Hash函数（也称杂凑函数或杂凑算法）就是把任意长的输入消息串变化成固定长的输出串的一种函数。这个输出串称为该消息的杂凑值。一般用于产生消息摘要，密钥加密等。

Ⅱ 散列法的散列算法

也称为哈希函数——哈希的英文意思为“无用信息”，因此哈希函数一词的由来可能是因为最终形成的哈希表里面是各种看起来毫无意义的描述值的混合。除用来快速搜索数据外，散列法还用来完成签名的加密解密工作，这种签名可以用来对收发消息时的用户签名进行鉴权。先用哈希函数对数据签名进行转换，然后将数字签名本身和转换后的信息摘要分别独立的发送给接收人。通过利用和发送人一样的哈希函数，接收人可以从数字签名获得一个信息摘要，然后将此摘要同传送过来的摘要进行比较，这两个值相等则表示数字签名有效。
利用哈希函数对数据库中的原始值建立索引，以后每获取一次数据时都要利用哈希函数进行重新转换。因此，哈希函数始终是单向操作。没有必要通过分析哈希值来试图逆推哈希函数。实际上，一个典型的哈希函数是不可能逆推出来的。好的哈希函数还应该避免对于不同输入产生相同的哈希值的情况发生。如果产生了哈希值相同的情况，称为冲突。可接受的哈希函数应该将冲突情况的可能性降到非常小。

Ⅲ 散列算法是怎么实现的

散列函数把消息或数据压缩成摘要，使得数据量变小，将数据的格式固定下来。该函数将数据打乱混合，重新创建一个叫做散列值的指纹。散列值通常用来代表一个短的随机字母和数字组成的字符串。好的散列函数在输入域中很少出现散列冲突。在散列表和数据处理中，不抑制冲突来区别数据，会使得数据库记录更难找到。

Ⅳ 单向散列算法的应用

在如今广泛使用的以太网中，报文的发送方会在以太网消息的末尾加上一个CRC（Cyclic Rendancy Check，循环冗余校验）字段，用来给接收方验证该消息的完整性，具体做法是：
1、消息发送方计算出消息的校验和并将其随消息一起发送。
2、接收方根据收到的消息重新计算校验和，并将其与直接收到的校验和相比较。如果两者不同，接收方就认为消息在传送过程中受损（如电信号受干扰出错），要求发送方重新发送。
这种方式被广泛使用到基于TCP/IP的多种通信协议中。大多数情况下，我们可以简单地将CRC看成是单向散列算法（函数）的一种应用。 经常在网站下载软件的人会留意这样一件事儿，在下载页面，网站会提供这个下载数据包的MD5值。这样的一个值就是网站使用MD5算法对下载的目标数据进行计算得到的一个散列值。如果攻击者攻破这个网站，在给用户下载的数据包中插入一些恶意代码或病毒，那么使用MD5算法计算得到的MD5散列值肯定发生了变化。
当这些被篡改的数据包被用户下载之后，用户只要执行MD5算法得到下载数据包的MD5散列值，与网站上公布的正常的MD5值对比。如果MD5值两者不同，表示正常的数据包被篡改了，就不要使用该数据包；如果两者一致，表示数据包没有被篡改，就能放心使用该数据包。
那么攻击者必须能调整代码的其他部分，使MD5的输出与以前相同。但MD5是专门为防止这种攻击而设计的，因此任何人下载了修改过的文件后，通过检查MD5散列值都将发现文件已不是原来的。

Ⅳ 散列算法和加密算法的区别

对称加密算法是应用较早的加密算法，技术成熟。在对称加密算法中，数据发信方将明文（原始数据）和加密密钥一起经过特殊加密算法处理后，使其变成复杂的加密密文发送出去。收信方收到密文后，若想解读原文，则需要使用加密用过的密钥及相同算法的逆算法对密文进行解密，才能使其恢复成可读明文。在对称加密算法中，使用的密钥只有一个，发收信双方都使用这个密钥对数据进行加密和解密，这就要求解密方事先必须知道加密密钥。对称加密算法的特点是算法公开、计算量小、加密速度快、加密效率高。不足之处是，交易双方都使用同样钥匙，安全性得不到保证。此外，每对用户每次使用对称加密算法时，都需要使用其他人不知道的惟一钥匙，这会使得发收信双方所拥有的钥匙数量成几何级数增长，密钥管理成为用户的负担。对称加密算法在分布式网络系统上使用较为困难，主要是因为密钥管理困难，使用成本较高。在计算机专网系统中广泛使用的对称加密算法有DES、IDEA和AES。

Ⅵ 散列算法的概念

在信息安全技术中，经常需要验证消息的完整性，散列（Hash）函数提供了这一服务，它对不同长度的输入消息，产生固定长度的输出。这个固定长度的输出称为原输入消息的“散列”或“消息摘要”（Message digest）。一个安全的哈希函数H必须具有以下属性：
l）H能够应用到大小不一的数据上。
2）H能够生成大小固定的输出。
3）对于任意给定的x，H（x）的计算相对简单。
4）对于任意给定的代码h，要发现满足H（x）=h的x在计算上是不可行的。
5) 对于任意给定的块x，要发现满足H（y）=H（x）而y=x在计算上是不可行的。
6）要发现满足H（X）=H（y）的（X，y）对在计算上是不可行的

Ⅶ 散列算法可以做哪些事

查找并判断状态是否出现过，出现过几次
比如说一个物品a有四个特征,为a[1],a[2],a[3],a[4]
那么令f(a)=a[1]*(p^1)+a[2]*(p^2)+a[3]*(p^3)+a[4]*(p^4)
hash[f(a)]=a;
若又有一个物品b，特征b[1],b[2],b[3],b[4]
f(b)=b[1]*(p^1)+b[2]*(p^2)+b[3]*(p^3)+b[4]*(p^4)
那么a=b时，f(a)=f(b)
反过来f(a)=f(b)时，a很有可能等于b （只要p设定的足够大，a不等于b的几率也很小）
为了节省内存，我们可以让f(a)=f(a)%q;
这样hash数组只需要开q的大小
就算在mod了之后a不等于b的概率也是非常小的（所以出题人一般不怎么能卡Hash，反而还天天考Hash）
像这样一个题：
有n个图，每个图都有m个点，有一些带权的边，询问每个图中的u点能否都不经过权值小于w的边到达v点（n*m<=200000，边数<=300000）
首先，你可以dfs，O（n*m）可以过，
但是如果改成q<=200000次询问，你就不能dfs了
实际上对于一个询问，当权值大于等于w的边全部放完之后就转化为判断此时uv是否都联通，
所以我们考虑离线，将询问按w从大到小，边也是按权值从大到小，边放边，边判断联通，
动态判断联通可以用并查集的按大小启发式合并，id[i][k]表示在第i个图中k所在并查集的头，
i图中u，v联通等价于id[i][u]==id[i][v](表示第i个图，需要枚举n次)。所以可以枚举i判断是不是都联通，总复杂度=O（边数 * log2(n*m) +边数 * n）log2（n*m）为启发式合并的时间复杂度。最后一个n为枚举i的耗费，如果n>500这方法就炸了，想办法优化，这时候就可以用哈希。
设f(u)=id[1][u]*(p^1)+id[2][u]*(p^2)+...+id[n][u]*(p^n) % q
如果id[i][u]=id[i][v](i=1~n) 则f(u)==f(v)
如果f(u)==f(v)则很大可能 id[i][u]=id[i][v](i=1~n)
令Hash[u]=f(u)
则在每次修改id[i][u]时顺便O(1)修改Hash(u)即可O（1）查询,判断Hash[u]是否等于Hash[v].
这样时间复杂度优化为O(边数*log2(n*m)+边数)是一个非常优秀的算法，散列的魅力就在于此，空间换时间，效率高，比赛时只要p和q设的大一些，一些考算法的题可以水个八九十分，还特别好写，不会写炸。

Ⅷ 什么是安全散列算法SHA256

安全散列算法SHA（Secure Hash Algorithm）是美国国家安全局 （NSA） 设计，美国国家标准与技术研究院（NIST） 发布的一系列密码散列函数，包括 SHA-1、SHA-224、SHA-256、SHA-384 和 SHA-512 等变体。主要适用于数字签名标准（DigitalSignature Standard DSS）里面定义的数字签名算法（Digital Signature Algorithm DSA）。下面以 SHA-1为例，介绍该算法计算消息摘要的原理。
对于长度小于2^64位的消息，SHA1会产生一个160位的消息摘要。当接收到消息的时候，这个消息摘要可以用来验证数据的完整性。在传输的过程中，数据很可能会发生变化，那么这时候就会产生不同的消息摘要。
SHA1有如下特性：不可以从消息摘要中复原信息；两个不同的消息不会产生同样的消息摘要。
一、术语和概念
（一）位(Bit)，字节（Byte）和字（Word）
SHA1始终把消息当成一个位（bit）字符串来处理。本文中，一个“字”（Word）是32位，而一个“字节”（Byte）是8位。比如，字符串“abc”可以被转换成一个位字符串：01100001 01100010 01100011。它也可以被表示成16进制字符串:0x616263.
（二）运算符和符号
下面的逻辑运算符都被运用于“字”（Word）
X^Y = X，Y逻辑与
X \/ Y = X，Y逻辑或
X XOR Y= X，Y逻辑异或
~X = X逻辑取反
X+Y定义如下：
字 X 和Y 代表两个整数 x 和y, 其中0 <= x < 2^32 且 0 <= y < 2^32. 令整数z= (x + y) mod 2^32. 这时候 0 <= z < 2^32. 将z转换成字Z,那么就是 Z = X + Y.
循环左移位操作符Sn(X)。X是一个字，n是一个整数，0<=n<=32。Sn(X)= (X<>32-n)
X<定义如下：抛弃最左边的n位数字，将各个位依次向左移动n位，然后用0填补右边的n位（最后结果还是32位）。X>>n是抛弃右边的n位，将各个位依次向右移动n位，然后在左边的n位填0。因此可以叫Sn(X)位循环移位运算
二、SHA1算法描述
在SHA1算法中，我们必须把原始消息（字符串，文件等）转换成位字符串。SHA1算法只接受位作为输入。假设我们对字符串“abc”产生消息摘要。首先，我们将它转换成位字符串如下：
01100001 0110001001100011
―――――――――――――
‘a’=97 ‘b’=98‘c’=99
这个位字符串的长度为24。下面我们需要5个步骤来计算MD5。
（一）补位
消息必须进行补位，以使其长度在对512取模以后的余数是448。也就是说，（补位后的消息长度）%512 = 448。即使长度已经满足对512取模后余数是448，补位也必须要进行。
补位是这样进行的：先补一个1，然后再补0，直到长度满足对512取模后余数是448。总而言之，补位是至少补一位，最多补512位。还是以前面的“abc”为例显示补位的过程。
原始信息：01100001 01100010 01100011
补位第一步：0110000101100010 01100011 1
首先补一个“1”
补位第二步：0110000101100010 01100011 10…..0
然后补423个“0”
我们可以把最后补位完成后的数据用16进制写成下面的样子
61626380 0000000000000000 00000000
00000000 0000000000000000 00000000
00000000 0000000000000000 00000000
00000000 00000000
现在，数据的长度是448了，我们可以进行下一步操作。
（二）补长度
所谓的补长度是将原始数据的长度补到已经进行了补位操作的消息后面。通常用一个64位的数据来表示原始消息的长度。如果消息长度不大于2^64，那么第一个字就是0。在进行了补长度的操作以后，整个消息就变成下面这样了（16进制格式）
61626380 0000000000000000 00000000
00000000 0000000000000000 00000000
00000000 0000000000000000 00000000
00000000 0000000000000000 00000018
如果原始的消息长度超过了512，我们需要将它补成512的倍数。然后我们把整个消息分成一个一个512位的数据块，分别处理每一个数据块，从而得到消息摘要。
（三）使用的常量
一系列的常量字K(0),K(1), ... , K(79)，如果以16进制给出。它们如下：
Kt = 0x5A827999 (0<= t <= 19)
Kt = 0x6ED9EBA1 (20<= t <= 39)
Kt = 0x8F1BBCDC (40<= t <= 59)
Kt = 0xCA62C1D6 (60<= t <= 79).
（四）需要使用的函数
在SHA1中我们需要一系列的函数。每个函数ft (0 <= t <= 79)都操作32位字B，C，D并且产生32位字作为输出。ft(B,C,D)可以如下定义
ft(B,C,D) = (B ANDC) or ((NOT B) AND D) ( 0 <= t <= 19)
ft(B,C,D) = B XOR CXOR D (20 <= t <= 39)
ft(B,C,D) = (B ANDC) or (B AND D) or (C AND D) (40 <= t <= 59)
ft(B,C,D) = B XOR CXOR D (60 <= t <= 79).
（五）计算消息摘要
必须使用进行了补位和补长度后的消息来计算消息摘要。计算需要两个缓冲区，每个都由5个32位的字组成，还需要一个80个32位字的缓冲区。第一个5个字的缓冲区被标识为A，B，C，D，E。第二个5个字的缓冲区被标识为H0,H1, H2, H3, H4。80个字的缓冲区被标识为W0,W1,..., W79
另外还需要一个一个字的TEMP缓冲区。
为了产生消息摘要，在第4部分中定义的16个字的数据块M1,M2,..., Mn
会依次进行处理，处理每个数据块Mi 包含80个步骤。
在处理每个数据块之前，缓冲区{Hi} 被初始化为下面的值（16进制）
H0 = 0x67452301
H1 = 0xEFCDAB89
H2 = 0x98BADCFE
H3 = 0x10325476
H4 = 0xC3D2E1F0.
现在开始处理M1, M2,... , Mn。为了处理 Mi,需要进行下面的步骤
(1). 将Mi 分成 16 个字 W0, W1, ... , W15,W0 是最左边的字
(2). 对于t = 16 到 79 令 Wt = S1(Wt-3 XOR Wt-8XOR Wt- 14 XOR Wt-16).
(3). 令A = H0, B = H1, C = H2, D = H3, E = H4.
(4) 对于t = 0 到 79，执行下面的循环
TEMP = S5(A) +ft(B,C,D) + E + Wt + Kt;
E = D; D = C; C =S30(B); B = A; A = TEMP;
(5). 令H0 = H0 + A, H1 = H1 + B, H2 = H2 + C, H3 = H3 + D, H4 = H4 + E.
在处理完所有的 Mn, 后，消息摘要是一个160位的字符串，以下面的顺序标识
H0 H1 H2 H3 H4.
对于SHA256、SHA384、SHA512。你也可以用相似的办法来计算消息摘要。对消息进行补位的算法完全是一样的。
三、SHA算法被破解了吗？
2013年9月10日美国约翰霍普金斯大学的计算机科学教授，知名的加密算法专家，Matthew Green被NSA要求删除他的一份关于破解加密算法的与NSA有关的博客。 同时约翰霍普金斯大学服务器上的该博客镜像也被要求删除。

加密算法专家，美国约翰霍普金斯大学教授Matthew Green
但当记者向该大学求证时，该校称从未收到来自NSA的要求要删除博客或镜像的资料，但记者却无法在原网址再找到该博客。幸运的是，从谷歌的缓存可以找到该博客。该博客提到NSA每年花费2.5亿美元来为自己在解密信息方面获取优势，并列举了NSA的一系列见不得人的做法。

在BitcoinTalk上，已经掀起了一轮争论：到底SHA-2是否安全？
部分认为不安全的观点包括：
NSA制造了sha-2, 我们不相信NSA，他们不可能不留后门。
棱镜事件已经明白的告诉我们，政府会用一切可能的手段来监视与解密。
虽然有很多人会研究SHA-2，且目前没有公开的证据表明有漏洞。但没有公开这并不能代表就没有，因为发现漏洞的人一定更倾向于保留这个秘密来自己利用，而不是公布。
部分认为安全的观点包括：
SHA-2是应用广泛的算法，应该已经经历了实践的检验。
美国的对头中国和俄国都有很多杰出的数学家，如果有问题的话，他们肯定已经发现了。
如果真的不安全，世界上安全的东西就太少了，我不能生活在提心吊胆里，所以我选择相信安全。

Ⅸ 一个安全的散列算法需要具备哪些属性

一个安全的散列算法需要具备的属性：
1、能对抗野蛮的攻击，能够抵御穷举法的攻势。
2、具有无限定义域，如任意长度的字节字符串和有限的值域或者固定长度的比特串。
3、具备应用的多样性，对于给定的散列值，没有实用的方法可以计算出一个原始输入，也就是说很难伪造。
4、能够因为环境因素的变化，如机器配置或者IP地址的改变而有变动。以保证源文件的安全性。
5、方便错误监测和修复函数。当散列函数被用于校验和的时候可以用相对较短的散列值来验证任意长度的数据是否被更改过。
6、安全散列算法接受的输入文档小于2的64次方 位，产生160位的报文摘要。该算法实际的目标使得找出一个能够匹配给定的散列值的文本是不可能的计算。