分类归档: Algorithm

关于什么是架构

中科永联高级技术培训中心(www.itisedu.com

    软件架构software architecture)是一系列相关的抽象模式,用于指导大型软件系统各个方面的设计。 软件架构是一个系统的草图。软件架构描述的对象是直接构成系统的抽象组件。各个组件之间的连接则明确和相对细致地描述组件之间的通讯。在实现阶段,这些抽象组件被细化为实际的组件,比如具体某个或者对象。在面向对象领域中,组件之间的连接通常用接口_(计算机科学)来实现。

    软件体系结构是构建计算机软件实践的基础。与建筑师设定建筑项目的设计原则和目标,作为绘图员画图的基础一样,一个软件架构师或者系统架构师陈述软件构架以作为满足不同客户需求的实际系统设计方案的基础。

      软件构架是一个容易理解的概念,多数工程师(尤其是经验不多的工程师)会从直觉上来认识它,但要给出精确的定义很困难。特别是,很难明确地区分设计和构架:构架属于设计的一方面,它集中于某些具体的特征。

      在“软件构架简介”中,David Garlan 和 Mary Shaw 认为软件构架是有关如下问题的设计层次:“在计算的算法和数据结构之外,设计并确定系统整体结构成为了新的问题。结构问题包括总体组织结构和全局控制结 构;通信、同步和数据访问的协议;设计元素的功能分配;物理分布;设计元素的组成;定标与性能;备选设计的选择。”[GS93]

       但构架不仅是结构;IEEE Working Group on Architecture 把其定义为“系统在其环境中的最高层概念”[IEEE98]。构架还包括“符合”系统完整性、经济约束条件、审美需求和样式。它并不仅注重对内部的考虑,而且还在系统的用户环境和开发环境中对系统进行整体考虑,即同时注重对外部的考虑。

      在 Rational Unified Process 中,软件系统的构架(在某一给定点)是指系统重要构件的组织或结构,这些重要构件通过接口与不断减小的构件与接口所组成的构件进行交互。

     从和目的、主题、材料和结构的联系上来说,软件架构可以和建筑物的架构相比拟。一个软件架构师需要有广泛 的软件理论知识和相应的经验来事实和管理软件产品的高级设计。软件架构师定义和设计软件的模块化,模块之间的交互,用户界面风格,对外接口方法,创新的设 计特性,以及高层事物的对象操作、逻辑和流程。

  是一般而言,软件系统的架构(Architecture)有两个要素:

·它是一个软件系统从整体到部分的最高层次的划分。

一个系统通常是由元件组成的,而这些元件如何形成、相互之间如何发生作用,则是关于这个系统本身结构的重要信息。

详细地说,就是要包括架构元件(Architecture Component)、联结器(Connector)、任务流(Task-flow)。所谓架构元素,也就是组成系统的核心"砖瓦",而联结器则描述这些元件之间通讯的路径、通讯的机制、通讯的预期结果,任务流则描述系统如何使用这些元件和联结器完成某一项需求。

·建造一个系统所作出的最高层次的、以后难以更改的,商业的和技术的决定。

在建造一个系统之前会有很多的重要决定需要事先作出,而一旦系统开始进行详细设计甚至建造,这些决定就很难更改甚至无法更改。显然,这样的决定必定是有关系统设计成败的最重要决定,必须经过非常慎重的研究和考察。

      历史
      早在1960年代,诸如E·W·戴克斯特拉就已经涉及软件架构这个概念了。自1990年代以来,部分由于在 Rational Software Corporation 和Microsoft内部的相关活动,软件架构这个概念开始越来越流行起来。

      卡内基梅隆大学和加州大学埃尔文分校在这个领域作了很多研究。卡内基·梅隆大学的Mary Shaw和David Garlan于1996年写了一本叫做 Software Architecture perspective on an emerging discipline的书,提出了软件架构中的很多概念,例如软件组件、连接器、风格等等。 加州大学埃尔文分校的软件研究院所做的工作则主要集中于架构风格、架构描述语言以及动态架构。

计算机软件的历史开始于五十年代,历史非常短暂,而相比之下建筑工程则从石器时代就开始了,人类在几千年的建筑设计实践中积累了大量的经验和教训。建筑设计基本上包含两点,一是建筑风格,二是建筑模式。独特的建筑风格和恰当选择的建筑模式,可以使一个独一无二。

下面的照片显示了中美洲古代玛雅建筑,Chichen-Itza大金字塔,九个巨大的石级堆垒而上,九十一级台阶(象征着四季的天数)夺路而出,塔顶的神殿耸入云天。所有的数字都如日历般严谨,风格雄浑。难以想象这是石器时代的建筑物。


图1、位于墨西哥Chichen-Itza(在玛雅语中chi意为嘴chen意为井)的古玛雅建筑。(摄影:作者)

  软件与人类的关系是架构师必须面对的核心问题,也是自从软件进入历史舞台之后就出 现的问题。与此类似地,自从有了建筑以来,建筑与人类的关系就一直是建筑设计师必须面对的核心问题。英国首相丘吉尔说,我们构造建筑物,然后建筑物构造我 们(We shape our buildings, and afterwards our buildings shape us)。英国下议院的会议厅较狭窄,无法使所有的下议院议员面向同一个方向入座,而必须分成两侧入座。丘吉尔认为,议员们入座的时候自然会选择与自己政见 相同的人同时入座,而这就是英国政党制的起源。Party这个词的原意就是"方"、"面"。政党起源的关键就是建筑物对人的影响。

在软件设计界曾经有很多人认为功能是最为重要的,形式必须服从功能。与此类似地,在建筑学界,现代主义建筑流派的开创人之一Louis Sullivan也认为形式应当服从于功能(Forms follows function)。

几乎所有的软件设计理念都可以在浩如烟海的建筑学历史中找到更为遥远的历史回响。最为著名的,当然就是模式理论和XP理论。

架构的目标是什么

正如同软件本身有其要达到的目标一样,架构设计要达到的目标是什么呢?一般而言,软件架构设计要达到如下的目标:

·可靠性(Reliable)。软件系统对于用户的商业经营和管理来说极为重要,因此软件系统必须非常可靠。

·安全行(Secure)。软件系统所承担的交易的商业价值极高,系统的安全性非常重要。

·可扩展性(Scalable)。软件必须能够在用户的使用率、用户的数目增加很快的情况下,保持合理的性能。只有这样,才能适应用户的市场扩展得可能性。

·可定制化(Customizable)。同样的一套软件,可以根据客户群的不同和市场需求的变化进行调整。

·可扩展性(Extensible)。在新技术出现的时候,一个软件系统应当允许导入新技术,从而对现有系统进行功能和性能的扩展

·可维护性(Maintainable)。软件系统的维护包括两方面,一是排除现有的错误,二是将新的软件需求反映到现有系统中去。一个易于维护的系统可以有效地降低技术支持的花费

·客户体验(Customer Experience)。软件系统必须易于使用。

·市场时机(Time to Market)。软件用户要面临同业竞争,软件提供商也要面临同业竞争。以最快的速度争夺市场先机非常重要。

架构的种类

根据我们关注的角度不同,可以将架构分成三种:

·逻辑架构、软件系统中元件之间的关系,比如用户界面,数据库,外部系统接口,商业逻辑元件,等等。

比如下面就是笔者亲身经历过的一个软件系统的逻辑架构图


图2、一个逻辑架构的例子

  从上面这张图中可以看出,此系统被划分成三个逻辑层次,即表象层次,商业层次和数据持久层次。每一个层次都含有多个逻辑元件。比如WEB服务器层次中有HTML服务元件、Session服务元件、安全服务元件、系统管理元件等。

·物理架构、软件元件是怎样放到硬件上的。

比如下面这张物理架构图描述了一个分布于北京和上海的分布式系统的物理架构,图中所有的元件都是物理设备,包括网络分流器、代理服务器、WEB服务器、应用服务器、报表服务器、整合服务器、存储服务器、主机等等。


图3、一个物理架构的例子

  ·系统架构、系统的非功能性特征,如可扩展性、可靠性、强壮性、灵活性、性能等。

系统架构的设计要求架构师具备软件和硬件的功能和性能的过硬知识,这一工作无疑是架构设计工作中最为困难的工作。

此外,从每一个角度上看,都可以看到架构的两要素:元件划分和设计决定。

首先,一个软件系统中的元件首先是逻辑元件。这些逻辑元件如何放到硬件上,以及这些元件如何为整个系统的可扩展性、可靠性、强壮性、灵活性、性能等做出贡献,是非常重要的信息。

其次,进行软件设计需要做出的决定中,必然会包括逻辑结构、物理结构,以及它们如何影响到系统的所有非功能性特征。这些决定中会有很多是一旦作出,就很难更改的。

根据作者的经验,一个基于数据库的系统架构,有多少个数据表,就会有多少页的架构设计文档。比如一个中等的数据库应用系统通常含有一百个左右的数据表,这样的一个系统设计通常需要有一百页左右的架构设计文档。

      构架描述

      为了讨论和分析软件构架,必须首先定义构架表示方式,即描述构架重要方面的方式。在 Rational Unified Process 中,软件构架文档记录有这种描述。

构架视图

      我们决定以多种构架视图来表示软件构架。每种构架视图针对于开发流程中的涉众(例如最终用户、设计人员、管理人员、系统工程师、维护人员等)所关注的特定方面。

      构架视图显示了软件构架如何分解为构件,以及构件如何由连接器连接来产生有用的形式 [PW92],由此记录主要的结构设计决策。这些设计决策必须基于需求以及功能、补充和其他方面的约束。而这些决策又会在较低层次上为需求和将来的设计决策施加进一步的约束。

典型的构架视图集

      构架由许多不同的构架视图来表示,这些视图本质上是以图形方式来摘要说明“在构架方面具有重要意义”的模型元素。在 Rational Unified Process 中,您将从一个典型的视图集开始,该视图集称为“4+1 视图模型”[KRU95]。它包括:

用例视图:包括用例和场景,这些用例和场景包括在构架方面具有重要意义的行为、类或技术风险。它是用例模型的子集。
逻辑视图:包括最重要的设计类、从这些设计类到包和子系统的组织形式,以及从这些包和子系统到层的组织形式。它还包括一些用例实现。它是设计模型的子集。
实施视图:包括实施模型及其从模块到包和层的组织形式的概览。 同时还描述了将逻辑视图中的包和类向实施视图中的包和模块分配的情况。它是实施模型的子集。
进程视图:包括所涉及任务(进程和线程)的描述,它们的交互和配置,以及将设计对象和类向任务的分配情况。只有在系统具有很高程度的并行时,才需要该视图。在 Rational Unified Process 中,它是设计模型的子集。
配置视图:包括对最典型的平台配置的各种物理节点的描述以及将任务(来自进程视图)向物理节点分配的情况。只有在分布式系统中才需要该视图。它是部署模型的一个子集。
构架视图记录在软件构架文档中。您可以构建其他视图来表达需要特别关注的不同方面:用户界面视图、安全视图、数据视图等等。对于简单系统,可以省略 4+1 视图模型中的一些视图。

      构架重点

      虽然以上视图可以表示系统的整体设计,但构架只同以下几个具体方面相关:

模型的结构,即组织模式,例如分层
基本元素,即关键用例、主类、常用机制等,它们与模型中的各元素相对。
几个关键场景,它们表示了整个系统的主要控制流程。
记录模块度、可选特征、产品线状况的服务。

      构架视图在本质上是整体设计的抽象或简化,它们通过舍弃具体细节来突出重要的特征。在考虑以下方面时,这些特征非常重要:

系统演进,即进入下一个开发周期。
在产品线环境下复用构架或构架的一部分。
评估补充质量,例如性能、可用性、可移植性和安全性。
团队或分包商分配开发工作。
决定是否包括市售构件。
插入范围更广的系统。

构架模式

      构架模式是解决复发构架问题的现成形式。构架框架或构架基础设施(中间件)是可以在其上构建某种构架的构件集。许多主要的构架困难应在框架或基础设施中进行解决,而且通常针对于特定的领域:命令和控制、MIS、控制系统等等。

构架模式示例

      [BUS96] 根据构架模式最适用的系统的特征将其分类,其中一个类别处理更普遍的结构问题。下表显示了 [BUS96] 中所提供的类别和这些类别所包含的模式。

类别 模式
结构
管道和过滤器
黑板
分布式系统 代理
交互系统 模型-视图-控制器
表示-抽象-控制
自适应系统 反射
微核

      软件构架是一个容易理解的概念,多数工程师(尤其是经验不多的工程师)会从直觉上来认识它,但要给出精确的定义很困难。特别是,很难明确地区分设计和构架:构架属于设计的一方面,它集中于某些具体的特征。

      在“软件构架简介”中,David Garlan 和 Mary Shaw 认为软件构架是有关如下问题的设计层次:“在计算的算法和数据结构之外,设计并确定系统整体结构成为了新的问题。结构问题包括总体组织结构和全局控制结 构;通信、同步和数据访问的协议;设计元素的功能分配;物理分布;设计元素的组成;定标与性能;备选设计的选择。”[GS93]

       但构架不仅是结构;IEEE Working Group on Architecture 把其定义为“系统在其环境中的最高层概念”[IEEE98]。构架还包括“符合”系统完整性、经济约束条件、审美需求和样式。它并不仅注重对内部的考虑, 而且还在系统的用户环境和开发环境中对系统进行整体考虑,即同时注重对外部的考虑。

      在 Rational Unified Process 中,软件系统的构架(在某一给定点)是指系统重要构件的组织或结构,这些重要构件通过接口与不断减小的构件与接口所组成的构件进行交互。

为阐明其含义,下面将详述其中的两个;完整说明请参见 [BUS96]。模式以下列广泛使用的形式来表示:

模式名
环境
问题
影响,描述应考虑的不同问题方面
解决方案
基本原理
结果环境
示例
模式名

环境
需要进行结构分解的大系统。

问题
必须处理不同抽象层次的问题的系统。例如:硬件控制问题、常见服务问题和针对于不同领域的问题。最好不要编写垂直构件来处理所有抽象层次的问题。否则要在不同的构件中多次处理相同的问题(可能会不一致)。

影响

系统的某些部分应当是可替换的
构件中的变化不应波动
相似的责任应归为一组
构件大小 — 复杂构件可能要进行分解
解决办法
将系统分成构件组,并使构件组形成层叠结构。使上层只使用下层(决不使用上层)提供的服务。尽量不使用非紧邻下层提供的服务(不跳层使用服务,除非中间层只添加通过构件)。

示例:

1. 通用层


严格的分层构架规定设计元素(类、构件、包、子系统)只能使用下层提供的服务, 服务可以包括事件处理、错误处理、数据库访问等等。 相对于记录在底层的原始操作系统级调用,它包括更明显的机制。

2. 业务系统层

上图显示了另一个分层示例,其中有垂直特定应用层、水平层和基础设施层。注意:此处的目标是采用非常短的业务“烟囱”并实现各种应用程序间的通用性。 否则,就可能有多个人解决同一问题,从而导致潜在的分歧。

有关该模式的深入讨论,请参见指南:分层。

模式名
黑板

环境
没有解决问题的确定方法(算法)或方法不可行的领域。例如 AI 系统、语音识别和监视系统。

问题
多个问题解决顾问(知识顾问)必须通过协作来解决他们无法单独解决的问题。各顾问的工作结果必须可以供所有其他顾问访问,使他们可以评估自己是否可以参与解决方案的查找并发布其工作结果。

影响

知识顾问参与解决问题的顺序不是确定的,这可能取决于问题解决策略

不同顾问的输入(结果或部分解决方案)可能有不同的表示方式

各顾问并不直接知道对方的存在,但可以评估对方发布的工作

解决办法
多名知识顾问都可访问一个称为“黑板”的共享数据库。黑板提供监测和更新其内容的接口。控制模块/对象激活遵循某种策略的顾问。激活后,顾问查看黑板,以确定它是否能参与解决问题。如果顾问决定它可以参与,控制对象就可以允许顾问将其部分(或最终)解决方案放置于黑板上。

示例:

以上显示了使用 UML 建模的结构或静态视图。 它将成为参数化协作的一部分,然后会绑定到实参上对模式进行实例化。

构架风格
软件构架(或仅是构架视图)可以具有名为构架风格 的属性,该属性减少了可选的形式,并使构架具有一定程度的一致性。样式可以通过一组模式或通过选择特定构件或连接器作为基本构件来定义。对给定系统,某些 样式可作为构架描述的一部分记录在构架风格指南(Rational Unified Process 中设计指南文档的一部分)中。样式在构架的可理解性与完整性方面起着主要的作用。

构架设计图
构架视图的图形描述称为构架设计图。对于以上描述的各种视图,设计图由以下统一建模语言图组成 [UML99]:

逻辑视图:类图、状态机和对象图
进程视图:类图与对象图(包括任务 – 进程与线程)。
实施视图:构件图。
部署视图配置图
用例视图:用例图描述用例、主角和普通设计类;顺序图描述设计对象及其协作关系。
构架设计流程
在 Rational Unified Process 中,构架主要是分析设计工作流程的结果。当项目再次进行此工作流程时,构架将在一次又一次迭代中不断演化、改进、精炼。由于每次迭代都包括集成和测试,所以在交付产品时,构架就相当强壮了。构架是精化阶段各次迭代的重点,构架的基线通常会在此阶段结束时确定。

  架构师

软体设计师中有一些技术水平较高、经验较为丰富的人,他们需要承担软件系统的架构设计,也就是需要设计系统的元件如何划分、元件之间如何发生相互作用,以及系统中逻辑的、物理的、系统的重要决定的作出。

这样的人就是所谓的架构师(Architect)。在很多公司中,架构师不是一个专门的和正式的职务。通常在一个开发小组中,最有经验的程序员会负责一些架构方面的工作。在一个部门中,最有经验的项目经理会负责一些架构方面的工作。

但是,越来越多的公司体认到架构工作的重要性,并且在不同的组织层次上设置专门的架构师位置,由他们负责不同层次上的逻辑架构、物理架构、系统架构的设计、配置、维护等工作。

卡内基梅隆大学软件研究所关于软件架构的定义

Read: 760

Hash 算法及其应用

什么是 Hash
Hash 的重要特性
Hash 函数的实现
主要的 Hash 算法
Hash 算法的安全问题
Hash 算法的应用
结 论

Hash, 一般翻译做“散列”,也有直接音译为"哈希"的,就是把任意长度的输入(又叫做预映射, pre-image),通过散列算法,变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不 同的输入可能会散列成相同的输出,而不可能从散列值来唯一的确定输入值。

数学表述为:h = H(M) ,其中H( )–单向散列函数,M–任意长度明文,h–固定长度散列值。

在信息安全领域中应用的Hash算法,还需要满足其他关键特性:

第 一当然是单向性(one-way),从预映射,能够简单迅速的得到散列值,而在计算上不可能构造一个预映射,使其散列结果等于某个特定的散列值,即构造相 应的M=H-1(h)不可行。这样,散列值就能在统计上唯一的表征输入值,因此,密码学上的 Hash 又被称为"消息摘要(message digest)",就是要求能方便的将"消息"进行"摘要",但在"摘要"中无法得到比"摘要"本身更多的关于"消息"的信息。

第二是抗 冲突性(collision-resistant),即在统计上无法产生2个散列值相同的预映射。给定M,计算上无法找到M’,满足H(M)=H(M’) ,此谓弱抗冲突性;计算上也难以寻找一对任意的M和M’,使满足H(M)=H(M’) ,此谓强抗冲突性。要求"强抗冲突性"主要是为了防范所谓"生日攻击(birthday attack)",在一个10人的团体中,你能找到和你生日相同的人的概率是2.4%,而在同一团体中,有2人生日相同的概率是11.7%。类似的,当预 映射的空间很大的情况下,算法必须有足够的强度来保证不能轻易找到"相同生日"的人。

第三是映射分布均匀性和差分分布均匀性,散列结果 中,为 0 的 bit 和为 1 的 bit ,其总数应该大致相等;输入中一个 bit 的变化,散列结果中将有一半以上的 bit 改变,这又叫做"雪崩效应(avalanche effect)";要实现使散列结果中出现 1bit 的变化,则输入中至少有一半以上的 bit 必须发生变化。其实质是必须使输入中每一个 bit 的信息,尽量均匀的反映到输出的每一个 bit 上去;输出中的每一个 bit,都是输入中尽可能多 bit 的信息一起作用的结果。

Damgard 和 Merkle 定义了所谓“压缩函数(compression function)”,就是将一个固定长度输入,变换成较短的固定长度的输出,这对密码学实践上 Hash 函数的设计产生了很大的影响。Hash函数就是被设计为基于通过特定压缩函数的不断重复“压缩”输入的分组和前一次压缩处理的结果的过程,直到整个消息都 被压缩完毕,最后的输出作为整个消息的散列值。尽管还缺乏严格的证明,但绝大多数业界的研究者都同意,如果压缩函数是安全的,那么以上述形式散列任意长度 的消息也将是安全的。这就是所谓 Damgard/Merkle 结构:

在下图中,任意长度的消息被分拆成符合压缩函数输入要求的分组, 最后一个分组可能需要在末尾添上特定的填充字节,这些分组将被顺序处理,除了第一个消息分组将与散列初始化值一起作为压缩函数的输入外,当前分组将和前一 个分组的压缩函数输出一起被作为这一次压缩的输入,而其输出又将被作为下一个分组压缩函数输入的一部分,直到最后一个压缩函数的输出,将被作为整个消息散 列的结果。

MD5 和 SHA1 可以说是目前应用最广泛的Hash算法,而它们都是以 MD4 为基础设计的。

1) MD4
MD4(RFC 1320)是 MIT 的 Ronald L. Rivest 在 1990 年设计的,MD 是 Message Digest 的缩写。它适用在32位字长的处理器上用高速软件实现–它是基于 32 位操作数的位操作来实现的。它的安全性不像RSA那样基于数学假设,尽管 Den Boer、Bosselaers 和 Dobbertin 很快就用分析和差分成功的攻击了它3轮变换中的 2 轮,证明了它并不像期望的那样安全,但它的整个算法并没有真正被破解过,Rivest 也很快进行了改进。

下面是一些MD4散列结果的例子:

MD4 ("") = 31d6cfe0d16ae931b73c59d7e0c089c0
MD4 ("a") = bde52cb31de33e46245e05fbdbd6fb24
MD4 ("abc") = a448017aaf21d8525fc10ae87aa6729d
MD4 ("message digest") = d9130a8164549fe818874806e1c7014b
MD4 ("abcdefghijklmnopqrstuvwxyz") = d79e1c308aa5bbcdeea8ed63df412da9
MD4 ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789") = 043f8582f241db351ce627e153e7f0e4
MD4 ("12345678901234567890123456789012345678901234567890123456789012345678901234567890") = e33b4ddc9c38f2199c3e7b164fcc0536

2) MD5
MD5(RFC 1321)是 Rivest 于1991年对MD4的改进版本。它对输入仍以512位分组,其输出是4个32位字的级联,与 MD4 相同。它较MD4所做的改进是:

1) 加入了第四轮
2) 每一步都有唯一的加法常数;
3) 第二轮中的G函数从((X ∧ Y) ∨ (X ∧ Z) ∨ (Y ∧ Z)) 变为 ((X ∧ Z) ∨ (Y ∧ ~Z))以减小其对称性;
4) 每一步都加入了前一步的结果,以加快"雪崩效应";
5) 改变了第2轮和第3轮中访问输入子分组的顺序,减小了形式的相似程度;
6) 近似优化了每轮的循环左移位移量,以期加快"雪崩效应",各轮的循环左移都不同。
尽管MD5比MD4来得复杂,并且速度较之要慢一点,但更安全,在抗分析和抗差分方面表现更好。

消 息首先被拆成若干个512位的分组,其中最后512位一个分组是“消息尾+填充字节(100…0)+64 位消息长度”,以确保对于不同长度的消息,该分组不相同。64位消息长度的限制导致了MD5安全的输入长度必须小于264bit,因为大于64位的长度信 息将被忽略。而4个32位寄存器字初始化为A=0x01234567,B=0x89abcdef,C=0xfedcba98,D=0x76543210, 它们将始终参与运算并形成最终的散列结果。

接着各个512位消息分组以16个32位字的形式进入算法的主循环,512位消息分组的个数据决定了循环的次数。主循环有4轮,每轮分别用到了非线性函数

F(X, Y, Z) = (X ∧ Y) ∨ (~X ∧ Z)
G(X, Y, Z) = (X ∧ Z) ∨ (Y ∧ ~Z)
H(X, Y, Z) =X +Y + Z
I(X, Y, Z) = X + (Y ∨ ~Z)
这4 轮变换是对进入主循环的512位消息分组的16个32位字分别进行如下操作:将A、B、C、D的副本a、b、c、d中的3个经F、G、H、I运算后的结果 与第4个相加,再加上32位字和一个32位字的加法常数,并将所得之值循环左移若干位,最后将所得结果加上a、b、c、d之一,并回送至ABCD,由此完 成一次循环。

所用的加法常数由这样一张表T来定义,其中i为1…64,T是i的正弦绝对值之4294967296次方的整数部分,这样做是为了通过正弦函数和幂函数来进一步消除变换中的线性性。

当所有512位分组都运算完毕后,ABCD的级联将被输出为MD5散列的结果。下面是一些MD5散列结果的例子:

MD5 ("") = d41d8cd98f00b204e9800998ecf8427e
MD5 ("a") = 0cc175b9c0f1b6a831c399e269772661
MD5 ("abc") = 900150983cd24fb0d6963f7d28e17f72
MD5 ("message digest") = f96b697d7cb7938d525a2f31aaf161d0
MD5 ("abcdefghijklmnopqrstuvwxyz") = c3fcd3d76192e4007dfb496cca67e13b
MD5 ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789") = d174ab98d277d9f5a5611c2c9f419d9f
MD5 ("12345678901234567890123456789012345678901234567890123456789012345678901234567890") = 57edf4a22be3c955ac49da2e2107b67a
参考相应RFC文档可以得到MD4、MD5算法的详细描述和算法的C源代码。

3) SHA1 及其他
SHA1是由NIST NSA设计为同DSA一起使用的,访问http://www.itl.nist.gov/fipspubs可以得到它的详细规范–"FIPS PUB 180-1 SECURE HASH STANDARD"。它对长度小于264的输入,产生长度为160bit的散列值,因此抗穷举(brute-force)性更好。SHA-1 设计时基于和MD4相同原理,并且模仿了该算法。因为它将产生160bit的散列值,因此它有5个参与运算的32位寄存器字,消息分组和填充方式与MD5 相同,主循环也同样是4轮,但每轮进行20次操作,非线性运算、移位和加法运算也与MD5类似,但非线性函数、加法常数和循环左移操作的设计有一些区别, 可以参考上面提到的规范来了解这些细节。下面是一些SHA1散列结果的例子:

SHA1 ("abc") = a9993e36 4706816a ba3e2571 7850c26c 9cd0d89d
SHA1 ("abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq") = 84983e44 1c3bd26e baae4aa1 f95129e5 e54670f1
其 他一些知名的Hash算法还有MD2、N-Hash、RIPE-MD、HAVAL等等。上面提到的这些都属于"纯"Hash算法。还有另2类Hash算 法,一类就是基于对称分组算法的单向散列算法,典型的例子是基于DES的所谓Davies-Meyer算法,另外还有经IDEA改进的Davies- Meyer算法,它们两者目前都被认为是安全的算法。另一类是基于模运算/离散对数的,也就是基于公开密钥算法的,但因为其运算开销太大,而缺乏很好的应 用前景。

没有通过分析和差分攻击考验的算法,大多都已经夭折在实验室里了,因此,如果目前流行的Hash算法能完全符合 密码学意义上的单向性和抗冲突性,就保证了只有穷举,才是破坏Hash运算安全特性的唯一方法。为了对抗弱抗冲突性,我们可能要穷举个数和散列值空间长度 一样大的输入,即尝试2128或2160个不同的输入,目前一台高档个人电脑可能需要1025年才能完成这一艰巨的工作,即使是最高端的并行系统,这也不 是在几千年里的干得完的事。而因为"生日攻击"有效的降低了需要穷举的空间,将其降低为大约1.2*264或1.2*280,所以,强抗冲突性是决定 Hash算法安全性的关键。

在NIST新的 Advanced Encryption Standard (AES)中,使用了长度为128、192、256bit 的密钥,因此相应的设计了 SHA256、SHA384、SHA512,它们将提供更好的安全性。

Hash算法在信息安全方面的应用主要体现在以下的3个方面:

1) 文件校验
我们比较熟悉的校验算法有奇偶校验和CRC校验,这2种校验并没有抗数据篡改的能力,它们一定程度上能检测并纠正数据传输中的信道误码,但却不能防止对数据的恶意破坏。

MD5 Hash算法的"数字指纹"特性,使它成为目前应用最广泛的一种文件完整性校验和(Checksum)算法,不少Unix系统有提供计算md5 checksum的命令。它常被用在下面的2种情况下:

第 一是文件传送后的校验,将得到的目标文件计算 md5 checksum,与源文件的md5 checksum 比对,由两者 md5 checksum 的一致性,可以从统计上保证2个文件的每一个码元也是完全相同的。这可以检验文件传输过程中是否出现错误,更重要的是可以保证文件在传输过程中未被恶意篡 改。一个很典型的应用是ftp服务,用户可以用来保证多次断点续传,特别是从镜像站点下载的文件的正确性。

更出色的解决方法是所谓的代码 签名,文件的提供者在提供文件的同时,提供对文件Hash值用自己的代码签名密钥进行数字签名的值,及自己的代码签名证书。文件的接受者不仅能验证文件的 完整性,还可以依据自己对证书签发者和证书拥有者的信任程度,决定是否接受该文件。浏览器在下载运行插件和java小程序时,使用的就是这样的模式。

第 二是用作保存二进制文件系统的数字指纹,以便检测文件系统是否未经允许的被修改。不少系统管理/系统安全软件都提供这一文件系统完整性评估的功能,在系统 初始安装完毕后,建立对文件系统的基础校验和数据库,因为散列校验和的长度很小,它们可以方便的被存放在容量很小的存储介质上。此后,可以定期或根据需 要,再次计算文件系统的校验和,一旦发现与原来保存的值有不匹配,说明该文件已经被非法修改,或者是被病毒感染,或者被木马程序替代。TripWire就 提供了一个此类应用的典型例子。

更完美的方法是使用"MAC"。"MAC" 是一个与Hash密切相关的名词,即信息鉴权码(Message Authority Code)。它是与密钥相关的Hash值,必须拥有该密钥才能检验该Hash值。文件系统的数字指纹也许会被保存在不可信任的介质上,只对拥有该密钥者提 供可鉴别性。并且在文件的数字指纹有可能需要被修改的情况下,只有密钥的拥有者可以计算出新的散列值,而企图破坏文件完整性者却不能得逞。

2) 数字签名
Hash 算法也是现代密码体系中的一个重要组成部分。由于非对称算法的运算速度较慢,所以在数字签名协议中,单向散列函数扮演了一个重要的角色。

在这种签名协议中,双方必须事先协商好双方都支持的Hash函数和签名算法。

签名方先对该数据文件进行计算其散列值,然后再对很短的散列值结果–如Md5是16个字节,SHA1是20字节,用非对称算法进行数字签名操作。对方在验证签名时,也是先对该数据文件进行计算其散列值,然后再用非对称算法验证数字签名。

对 Hash 值,又称"数字摘要"进行数字签名,在统计上可以认为与对文件本身进行数字签名是等效的。而且这样的协议还有其他的优点:

首先,数据文件本身可以同它的散列值分开保存,签名验证也可以脱离数据文件本身的存在而进行。

再 者,有些情况下签名密钥可能与解密密钥是同一个,也就是说,如果对一个数据文件签名,与对其进行非对称的解密操作是相同的操作,这是相当危险的,恶意的破 坏者可能将一个试图骗你将其解密的文件,充当一个要求你签名的文件发送给你。因此,在对任何数据文件进行数字签名时,只有对其Hash值进行签名才是安全 的。

3) 鉴权协议
如下的鉴权协议又被称作"挑战–认证模式:在传输信道是可被侦听,但不可被篡改的情况下,这是一种简单而安全的方法。

需 要鉴权的一方,向将被鉴权的一方发送随机串(“挑战”),被鉴权方将该随机串和自己的鉴权口令字一起进行 Hash 运算后,返还鉴权方,鉴权方将收到的Hash值与在己端用该随机串和对方的鉴权口令字进行 Hash 运算的结果相比较(“认证”),如相同,则可在统计上认为对方拥有该口令字,即通过鉴权。

POP3协议中就有这一应用的典型例子:

S: +OK POP3 server ready <1896.697170952@dbc.mtview.ca.us>
C: APOP mrose c4c9334bac560ecc979e58001b3e22fb
S: +OK maildrop has 1 message (369 octets)
在 上面的一段POP3协议会话中,双方都共享的对称密钥(鉴权口令字)是tanstaaf,服务器发出的挑战是< 1896.697170952@dbc.mtview.ca.us>,客户端对挑战的应答是MD5("< 1896.697170952@dbc.mtview.ca.us>tanstaaf") = c4c9334bac560ecc979e58001b3e22fb,这个正确的应答使其通过了认证。

散列算法长期以来一直在计算机科学中大量应用,随着现代密码学的发展,单向散列函数已经成为信息安全领域中一个重要的结构模块,我们有理由深入研究其设计理论和应用方法。

(金诺 · Panzer)

Read: 651