>>分享数据结构和算法相关的知识和技术 书籍支持  卫琴直播  品书摘要  在线测试  资源下载  联系我们
发表一个新主题 开启一个新投票 回复文章 您是本文章第 19813 个阅读者 刷新本主题
 * 贴子主题:  SHA-1算法详解 回复文章 点赞(0)  收藏  
作者:Jacky    发表时间:2020-03-15 22:56:15     消息  查看  搜索  好友  邮件  复制  引用

      在信息系统中,安全目标的实现除了保密技术外,另一个重要方面就是认证技术,认证技术主要用于防止对手对系统进行主动攻击,如伪装,窜扰等,这对于开放环境中的信息安全就显得尤为重要,认证的目的有两方面,一是验证信息的发送者是合法的,二是验证信息的完整性。

      一、Hash函数和消息完整性

   Hash函数也称为杂凑函数或散列函数,其输入为一可变长度x返回一固定长度串,该串被称为输入x的Hash值,还有形象的说法就是数字指纹,因为Hash函数是多对一函数,所以一定将某些不同的输入变化成相同的输出,这就要求给定一个Hash值,求其逆是比较难,但通过给定的输入计算Hash值必须是很容易的,因此也称Hash函数为单向Hash函数。

   Hash函数一般满足以下几个基本需求:

   1、输入x可以任意长度

   2、输出数据长度固定

   3、容易计算,给定任何x,容易计算出x的Hash值

   4、单向函数,即给出一个Hash值,很难反向计算出原始输入的x

   5、唯一性,即难以找出两个不同的输入会得到相同的Hash输出值

   Hash值得长度由算法的类型决定,与输入的消息大小无关,一般为128bit或者160bit,即使两个消息的差别很小,如仅差别一两位,其Hash函数的运算结果也会截然不同,用同一个算法对某一消息进行Hash运算只能获得唯一确定的Hash值,常用的单向Hash算法有MDS, SHA-1等。

   一个安全的单向迭代函数是构造安全消息Hash值得核心和基础,有了好的单向迭代函数,就可以用合适的迭代方法来构造迭代Hash函数,Hash函数的安全设计的理论主要有以下两点:一是函数的单向性,二是函数影射的随机性。

二、常见的Hash函数

   现在常用的几种Hash算法有MD-5、SHA等,我们就侧重于SHA算法来讲解下这类算法:

   SHA(Security Hash Algorithm)是美国的NIST和NSA设计的一种标准的Hash算法,SHA用于数字签名的标准算法的DSS中,也是安全性很高的一种Hash算法,该算法的输入消息长度小于2^64bit,最终输出的结果值是160bit,SHA与MD-4相比较而言,主要增加了扩展变换,将前一轮的输出也加到了下一轮,这样增加了雪崩效应,而且由于其160bit的输出,对穷举***更具有抵抗性。

三、Sha-1算法实现的基本步骤

1、将消息摘要转换成位字符串

   因为在Sha-1算法中,它的输入必须为位,所以我们首先要将其转化为位字符串,我们以“abc”字符串来说明问题,因为'a'=97, 'b'=98, 'c'=99,所以将其转换为位串后为:

01100001 01100010 01100011

2、对转换后的位字符串进行补位操作

   Sha-1算法标准规定,必须对消息摘要进行补位操作,即将输入的数据进行填充,使得数据长度对512求余的结果为448,填充比特位的最高位补一个1,其余的位补0,如果在补位之前已经满足对512取模余数为448,也要进行补位,在其后补一位1即可。总之,补位是至少补一位,最多补512位,我们依然以“abc”为例,其补位过程如下:

初始的信息摘要:01100001 01100010 01100011

第一步补位:    01100001 01100010 01100011 1

..... ......

补位最后一位:  01100001 01100010 01100011 10.......0(后面补了423个0)

而后我们将补位操作后的信息摘要转换为十六进制,如下所示:

61626380 00000000 00000000 00000000

00000000 00000000 00000000 00000000

00000000 00000000 00000000 00000000

00000000 00000000

3、附加长度值

   在信息摘要后面附加64bit的信息,用来表示原始信息摘要的长度,在这步操作之后,信息报文便是512bit的倍数。通常来说用一个64位的数据表示原始消息的长度,如果消息长度不大于2^64,那么前32bit就为0,在进行附加长度值操作后,其“abc”数据报文即变成如下形式:

61626380 00000000 00000000 00000000

00000000 00000000 00000000 00000000

00000000 00000000 00000000 00000000

00000000 00000000 00000000 00000018

因为“abc”占3个字节,即24位 ,换算为十六进制即为0x18。

4、初始化缓存

   一个160位MD缓冲区用以保存中间和最终散列函数的结果。它可以表示为5个32位的寄存器(H0,H1,H2,H3,H4)。初始化为:

H0 = 0x67452301

H1 = 0xEFCDAB89

H2 = 0x98BADCFE

H3 = 0x10325476

H4 = 0xC3D2E1F0

如果大家对MD-5不陌生的话,会发现一个重要的现象,其前四个与MD-5一样,但不同之处为存储为big-endien format.

5、计算消息摘要

   在计算报文之前我们还要做一些基本的工作,就是在我们计算过程中要用到的方法,或定义。

(1)、循环左移操作符Sn(x),x是一个字,也就是32bit大小的变量,n是一个整数且0<=n<=32。Sn(X) = (X<<n)OR(X>>32-n)

(2)、在程序中所要用到的常量,这一系列常量字k(0)、k(1)、...k(79),将其以十六进制表示如下:

Kt = 0x5A827999  (0 <= t <= 19)

Kt = 0x6ED9EBA1 (20 <= t <= 39)

Kt = 0x8F1BBCDC (40 <= t <= 59)

Kt = 0xCA62C1D6 (60 <= t <= 79)

(3)、所要用到的一系列函数

  Ft(b,c,d)  ((b&c)|((~b)&d))    (0 <= t <= 19)

  Ft(b,c,d) (b^c^d)             (20 <= t <= 39)

  Ft(b,c,d) ((b&c)|(b&d)|(c&d))  (40 <= t <= 59)

  Ft(b,c,d) (b^c^d)               (60 <= t <= 79)

(4)、计算

计算需要一个缓冲区,由5个32位的字组成,还需要一个80个32位字的缓冲区。第一个5个字的缓冲区被标识为A,B,C,D,E。80个字的缓冲区被标识为W0, W1,..., W79

另外还需要一个一个字的TEMP缓冲区。

为了产生消息摘要,在第4部分中定义的16个字的数据块M1, M2,..., Mn

会依次进行处理,处理每个数据块Mi 包含80个步骤。

现在开始处理M1, M2, ... , Mn。为了处理 Mi,需要进行下面的步骤

(1). 将 Mi 分成 16 个字 W0, W1, ... , W15,  W0 是最左边的字

(2). 对于 t = 16 到 79 令 Wt = S1(Wt-3 XOR Wt-8 XOR 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。你也可以用相似的办法来计算消息摘要。对消息进行补位的算法完全是一样的。

                                    

----------------------------
原文链接:https://blog.51cto.com/yiluohuanghun/950450

程序猿的技术大观园:www.javathinker.net



[这个贴子最后由 flybird 在 2020-03-16 11:21:30 重新编辑]
  Java面向对象编程-->Java语言的基本语法和规范
  JavaWeb开发-->Web运作原理(Ⅰ)
  JSP与Hibernate开发-->持久化层的映射类型
  Java网络编程-->创建非阻塞的HTTP服务器
  精通Spring-->绑定CSS样式
  Vue3开发-->通过Vuex进行状态管理
  常见的调度算法
  图像基本处理算法的简单实现
  对simhash算法的一些思考
  haproxy调度算法
  Java 选择排序算法
  基于SQL的数据库算法研究
  算法之原码、补码、反码
  令牌桶算法
  LRU算法的简单实现范例
  Binary Search二分查找算法
  字节跳动面试官这样问消息队列:分布式事务、重复消费、顺序...
  为什么要学数据结构?
  小米面试算法题:搜索旋转排序数组
  浅谈常见的七种加密算法及实现
  好书推荐:《小灰的算法之旅》
  更多...
 IPIP: 已设置保密
树形列表:   
1页 1条记录 当前第1
发表一个新主题 开启一个新投票 回复文章


中文版权所有: JavaThinker技术网站 Copyright 2016-2026 沪ICP备16029593号-2
荟萃Java程序员智慧的结晶,分享交流Java前沿技术。  联系我们
如有技术文章涉及侵权,请与本站管理员联系。