NP, NP complete, NPC

01月 7th, 2009 by CoraZonado

概念:

在计算机学科中,存在多项式时间的算法的一类问题,称之为P类问题;而像梵塔问题、推销员旅行问题、(命题表达式)可满足问题这类,至今没有找到多项式时间算法解的一类问题,称之为NP类问题。
  

拿推销员旅行问题为例,假设推销员亨利有向6个城市推销公司产品的任务,并规定了一个旅行预算。他手中有一张航班票价表,他要从A城开始走遍图中的6个城市后返回A城,并且不超出预算,请你帮他找出应走的路线。如果给出的预算宽裕,则任务很简单;如果预算比较紧张,你就得认真设计路线了。你得考虑每一种可能的次序,以使旅费最少。
  
  推销员旅行问题
  
如果有3个城市A,B和C,互相之间都有往返的飞机,而且起始城市是任意的,则有6种访问每个城市的次序:ABC,ACB,,BAC,BCA,CAB,CBA。如果有4个城市,则有24种次序,可以用阶乘来表示:4!=4×3!=4×3×2×1=24;若有5个城市,则有5!=5×4!=120,类似的有6!=720等等。即使用计算机来计算,这种急剧增长的可能性的数目也远远超过计算资源的处理能力,对此,算法复杂性专家史蒂芬.库克(Stephen Cook)评论:”如果有100个城市,需要求出100!条路线的费用,没有哪一台计算机能够胜任这一任务。打个比方,让太阳系中所有的电子以它旋转的频率来计算,就算太阳烧尽了也算不完。问题的关键是某些东西在实践中行不通。”
  
而NP问题中最困难的问题称之为NP完全问题,已经证明的包括:电话网络的最优几何设计、格子棋的最佳走法。根据库克定理,任意一个NP完全问题如果能够在多项式时间内解决,则所有的NP问题都能在多项式时间内解决,而至今这一问题仍无答案。

争议:

NP并不是NON-POLYNOMIAL,把NP说成是NON-POLYNOMIAL,是望文生义,读书不求甚解。事实上,如果你能够证明某个NP问题是个NON-POLYNOMIAL的问题,你就可以去领那七个百万美元数学大奖中间的一个了。

数学上著名的NP问题,完整的叫法是NP完全问题,也即“NP COMPLETE”问题,简单的写法,是 NP=P?的问题。问题就在这个问号上,到底是NP等於P,还是NP不等於P。证明其中之一,便可以拿百万美元大奖。这个奖还没有人拿到,也就是说,NP问题到底是Polynomial,还是Non-Polynomial,尚无定论。

P代表Polynomial倒是对的。NP就是Non-deterministic Polynomial的问题,也即是多项式复杂程度的非确定性问题。

什么是非确定性问题呢?有些计算问题是确定性的,比如加减乘除之类,你只要按照公式推导,按部就班一步步来,就可以得到结果。但是,有些问题是无法按部就班直接地计算出。比如,找大质数的问题。有没有一个公式,你一套公式,就可以一步步推算出来,下一个质数应该是多少呢?这样的公式是没有的。再比如,大的合数分解质因数的问题,有没有一个公式,把合数代进去,就直接可以算出,它的因子各自是多少?也没有这样的公式。

这种问题的答案,是无法直接计算得到的,只能通过间接的“猜算”来得到结果。这也就是非确定性问题。而这些问题的通常有个算法,它不能直接告诉你答案是什么,但可以告诉你,某个可能的结果是正确的答案还是错误的。这个可以告诉你“猜算”的答案正确与否的算法,假如可以在多项式时间(多项式时间: 运行时间最多是输入量的多项式函数)内算出来,就叫做多项式非确定性问题。而如果这个问题的所有可能答案,都是可以在多项式时间内进行正确与否的验算的话,就叫完全多项式非确定问题。

完全多项式非确定性问题可以用穷举法得到答案,一个个检验下去,最终便能得到结果。但是这样算法的复杂程度,是指数关系,因此计算的时间随问题的复杂程度成指数的增长,很快便变得不可计算了。人们发现,所有的完全多项式非确定性问题,都可以转换为一类叫做满足性问题的逻辑运算问题。既然这类问题的所有可能答案,都可以在多项式时间内计算,人们於是就猜想,是否这类问题,存在一个确定性算法,可以在指数时间内,直接算出或是搜寻出正确的答案呢?这就是著名的NP=P?的猜想。

解决这个猜想,无非两种可能,一种是找到一个这样的算法,只要针对某个特定NP完全问题找到一个算法,所有这类问题都可以迎刃而解了,因为他们可以转化为同一个问题。另外的一种可能,就是这样的算法是不存在的。那么就要从数学理论上证明它为什么不存在。

前段时间轰动世界的一个数学成果,是几个印度人提出了一个新算法,可以在多项式时间内,证明某个数是或者不是质数,而在这之前,人们认为质数的证明,是个非多项式问题。可见,有些看来好象是非多项式的问题,其实是多项式问题,只是人们一时还不知道它的多项式解而已。

NP完全性问题

虽然是计算机系的学生,但自己对于什么是NP问题,什么是NPC问题也并不能很好的解答,就更不用说构造怎样的一种方式来证明一个

问题是不是NP问题了。但算法中涉及了很多这样的问题,压力之下,尽我所能弄懂了,把自己的理解记录下来。

P(Polynomial问题)。在计算机里面,对一个问题寻求一种多项式的算法是一个很好的解答。从理论上来说,如果一个问题能够有多翔

实的解法的话,就算是一个很好的算法了。这种问题总可以找到一个DTM(Deterministic Turing Machine)

NP(Nondeterministic Polynomial问题)。但是对于很多问题来说,他们找不到一个多项式的解决方法,他们只能对应一个NDTM

(Nondeterministic Turing Machine)来解决。可以这样想想:对于下一步的动作,他们也不知道确切的应该怎么办,只能“尝试”很多种方案

才能够得出一个答案,这显然是很费时的,这种问题未NP问题。

NPC(NP Complete)问题,可以这么认为,这种问题只有把解域里面的所有可能都穷举了之后才能得出答案,这样的问题是NP里面最难

的问题,这种问题就是NPC问题。

一般说来,如果要证明一个问题是NPC问题的话,可以拿已经是NPC问题的一个问题经过多项式时间的变化变成所需要证明的问题,那

么索要证明的问题就是一个NPC问题了。

NPC问题是一个问题族,如果里面任意一个问题有了多项式的解,那么所有的问题都可以有多项式的解。

电容器的基础知识及检测方法

01月 7th, 2009 by CoraZonado

电容器的基础知识及检测方法

阻抗匹配

01月 7th, 2009 by CoraZonado

   阻抗匹配是指信号源或者传输线跟负载之间的一种合适的搭配方式。
  
   阻抗匹配分为低频和高频两种情况讨论。我们先从直流电压源驱动一个负载入手。由于实际的电压源,总是有内阻的,我们可以把一个实际电压源,等效成一个理想的电压源跟一个电阻r串联的模型。假设负载电阻为R,电源电动势为U,内阻为r,那么我们可以计算出流过电阻R的电流为:I=U/(R+r),可以看出,负载电阻R越小,则输出电流越大。
   负载R上的电压为:Uo=IR=U*[1+(r/R)],可以看出,负载电阻R越大,则输出电压Uo越高。
   再来计算一下电阻R消耗的功率为: P=I*I*R=[U/(R+r)]*[U/(R+r)]*R=U*U*R/(R*R+2*R*r+r*r)=U*U*R/[(R-r)*(R-r)+4*R*r] =U*U/{[(R-r)*(R-r)/R]+4*r}
   对于一个给定的信号源,其内阻r是固定的,而负载电阻R则是由我们来选择的。注意式中[(R-r)*(R-r)/R],当R=r时,[(R-r)*(R-r)/R]可取得最小值0,这时负载电阻R上可获得最大输出功率Pmax=U*U/(4*r)。即,当负载电阻跟信号源内阻相等时,负载可获得最大输出功率,这就是我们常说的阻抗匹配之一。
   对于纯电阻电路,此结论同样适用于低频电路及高频电路。当交流电路中含有容性或感性阻抗时,结论有所改变,就是需要信号源与负载阻抗的的实部相等,虚部互为相反数,这叫做共厄匹配。
   在低频电路中,我们一般不考虑传输线的匹配问题,只考虑信号源跟负载之间的情况,因为低频信号的波长相对于传输线来说很长,传输线可以看成是“短线”,反射可以不考虑(可以这么理解:因为线短,即使反射回来,跟原信号还是一样的)。
   从以上分析我们可以得出结论:如果我们需要输出电流大,则选择小的负载R;如果我们需要输出电压大,则选择大的负载R;如果我们需要输出功率最大,则选择跟信号源内阻匹配的电阻R。
   有时阻抗不匹配还有另外一层意思,例如一些仪器输出端是在特定的负载条件下设计的,如果负载条件改变了,则可能达不到原来的性能,这时我们也会叫做阻抗失配。
   在高频电路中,我们还必须考虑反射的问题。当信号的频率很高时,则信号的波长就很短,当波长短得跟传输线长度可以比拟时,反射信号叠加在原信号上将会改变原信号的形状。如果传输线的特征阻抗跟负载阻抗不匹配(相等)时,在负载端就会产生反射。为什么阻抗不匹配时会产生反射以及特征阻抗的求解方法,牵涉到二阶偏微分方程的求解,在这里我们不细说了,有兴趣的可参看电磁场与微波方面书籍中的传输线理论。
   传输线的特征阻抗(也叫做特性阻抗)是由传输线的结构以及材料决定的,而与传输线的长度,以及信号的幅度、频率等均无关。例如,常用的闭路电视同轴电缆特性阻抗为75欧,而一些射频设备上则常用特征阻抗为50欧的同轴电缆。另外还有一种常见的传输线是特性阻抗为300欧的扁平平行线,这在农村使用的电视天线架上比较常见,用来做八木天线的馈线。因为电视机的射频输入端输入阻抗为75欧,所以300欧的馈线将与其不能匹配。实际中是如何解决这个问题的呢?不知道大家有没有留意到,电视机的附件中,有一个300欧到75欧的阻抗转换器(一个塑料包装的,一端有一个圆形的插头的那个东东,大概有两个大拇指那么大的)?它里面其实就是一个传输线变压器,将300欧的阻抗,变换成75欧的,这样就可以匹配起来了。
   这里需要强调一点的是,特性阻抗跟我们通常理解的电阻不是一个概念,它与传输线的长度无关,也不能通过使用欧姆表来测量。为了不产生反射,负载阻抗跟传输线的特征阻抗应该相等,这就是传输线的阻抗匹配。
   如果阻抗不匹配会有什么不良后果呢?如果不匹配,则会形成反射,能量传递不过去,降低效率;会在传输线上形成驻波(简单的理解,就是有些地方信号强,有些地方信号弱),导致传输线的有效功率容量降低;功率发射不出去,甚至会损坏发射设备。如果是电路板上的高速信号线与负载阻抗不匹配时,会产生震荡,辐射干扰等。
   当阻抗不匹配时,有哪些办法让它匹配呢?第一,可以考虑使用变压器来做阻抗转换,就像上面所说的电视机中的那个例子那样。第二,可以考虑使用串联/并联电容或电感的办法,这在调试射频电路时常使用。第三,可以考虑使用串联/并联电阻的办法。一些驱动器的阻抗比较低,可以串联一个合适的电阻来跟传输线匹配,例如高速信号线,有时会串联一个几十欧的电阻。而一些接收器的输入阻抗则比较高,可以使用并联电阻的方法,来跟传输线匹配,例如,485总线接收器,常在数据线终端并联120欧的匹配电阻。
   为了帮助大家理解阻抗不匹配时的反射问题,我来举两个例子:假设你在练习拳击——打沙包。如果是一个重量合适的、硬度合适的沙包,你打上去会感觉很舒服。但是,如果哪一天我把沙包做了手脚,例如,里面换成了铁沙,你还是用以前的力打上去,你的手可能就会受不了了——这就是负载过重的情况,会产生很大的反弹力。相反,如果我把里面换成了很轻很轻的东西,你一出拳,则可能会扑空,手也可能会受不了——这就是负载过轻的情况。另一个例子,不知道大家有没有过这样的经历:就是看不清楼梯时上/下楼梯,当你以为还有楼梯时,就会出现“负载不匹配”这样的感觉了。当然,也许这样的例子不太恰当,但我们可以拿它来理解负载不匹配时的反射情况。

特性阻抗(Characteristic Impedance)

当某讯号方波,在传输线组合体的讯号线中,以高准位(High Level)的正压讯号向前推进时,则距其最近的参考层(如接地层)中,理论上必有被该电场所感应出来的负压讯号伴随前行(等于正压讯号反向的回归路径Return Path),如此将可完成整体性的回路(Loop)系统。该“讯号”前行中若将其飞行时间暂短加以冻结,即可想象其所遭受到来自讯号线、介质层与参考层等所共同呈现的瞬间阻抗值(Instantanious Impedance),此即所谓的“特性阻抗”。  是故该“特性阻抗”应与讯号线之线宽(w)、线厚(t)、介质厚度(h)与介质常数(Dk)都扯上了关系。

阻抗匹配不良的后果  由于高频讯号的“特性阻抗”(Z0)原词甚长,故一般均简称之为“阻抗”。读者千万要小心,此与低频AC交流电(60Hz)其电线(并非传输线)中,所出现的阻抗值(Z)并不完全相同。数位系统当整条传输线的Z0都能管理妥善,而控制在某一范围内(±10﹪或 ±5﹪)者,此品质良好的传输线,将可使得杂讯减少,而误动作也可避免。  但当上述微带线中Z0的四种变数(w、t、h、 r)有任一项发生异常,例如讯号线出现缺口时,将使得原来的Z0突然上升(见上述公式中之Z0与W成反比的事实),而无法继续维持应有的稳定均匀(Continuous)时,则其讯号的能量必然会发生部分前进,而部分却反弹反射的缺失。如此将无法避免杂讯及误动作了。例如浇花的软管突然被踩住,造成软管两端都出现异常,正好可说明上述特性阻抗匹配不良的问题。

阻抗匹配不良造成杂讯  上述部分讯号能量的反弹,将造成原来良好品质的方波讯号,立即出现异常的变形(即发生高准位向上的Overshoot,与低准位向下的Undershoot,以及二者后续的Ringing)。此等高频杂讯严重时还会引发误动作,而且当时脉速度愈快时杂讯愈多也愈容易出错。

在设计高速PCB电路时,阻抗匹配是设计的要素之一。而阻抗值跟走线方式有绝对的关系, 例如是走在表面层(microstrip)或内层(stripline/double stripline),与参考层(电源层或地层)的距离,走线宽度,PCB材质等均会影响走线的特性阻抗值。也就是说要在布线后才能确定阻抗值。一般仿真软件会因线路模型或所使用的数学算法的限制而无法考虑到一些阻抗不连续的布线情况,这时候在原理图上只能预留一些terminators(端接),如串联电阻等,来缓和走线阻抗不连续的效应。真正根本解决问题的方法还是布线时尽量注意避免阻抗不连续的发生。 IBIS模型的准确性直接影响到仿真的结果。基本上IBIS可看成是实际芯片I/O buffer等效电路的电气特性资料,一般可由SPICE模型转换而得 (亦可采用测量, 但限制较多),而SPICE的资料与芯片制造有绝对的关系,所以同样一个器件不同芯片厂商提供,其SPICE的资料是不同的,进而转换后的IBIS模型内之资料也会随之而异。也就是说,如果用了A厂商的器件,只有他们有能力提供他们器件准确模型资料,因为没有其它人会比他们更清楚他们的器件是由何种工艺做出来的。如果厂商所提供的IBIS不准确, 只能不断要求该厂商改进才是根本解决之道。

自由空间传播时的无线通信距离的计算方法

01月 7th, 2009 by CoraZonado

这里给出自由空间传播时的无线通信距离的计算方法:所谓自由空间传播系指天线周围为无限大真空时的电波传播,它是理想传播条件。电波在自由空间传播时,其能量既不会被障碍物所吸收,也不会产生反射或散射。

通信距离与发射功率、接收灵敏度和工作频率有关。

[Lfs](dB)=32.44+20lgd(km)+20lgf(MHz)

式中Lfs为传输损耗,d为传输距离,频率的单位以MHz计算。

由上式可见,自由空间中电波传播损耗(亦称衰减)只与工作频率f和传播距离d有关,当f或d增大一倍时,[Lfs]将分别增加6dB.

下面的公式说明在自由空间下电波传播的损耗

Los = 32.44 + 20lg d(Km) + 20lg f(MHz)

Los 是传播损耗,单位为dB

d是距离,单位是Km

f是工作频率,单位是MHz

下面举例说明一个工作频率为433.92MHz,发射功率为+10dBm(10mW),接收灵敏度为-105dBm的系统在自由空间的传播距离:

1. 由发射功率+10dBm,接收灵敏度为-105dBm

Los = 115dB

2. 由Los、f

计算得出d =30公里

这是理想状况下的传输距离,实际的应用中是会低于该值,这是因为无线通信要受到各种外界因素的影响,如大气、阻挡物、多径等造成的损耗,将上述损耗的参考值计入上式中,即可计算出近似通信距离。

假定大气、遮挡等造成的损耗为25dB,可以计算得出通信距离为:

d =1.7公里

结论: 无线传输损耗每增加6dB, 传送距离减小一倍。

ECC(Error Checking and Correcting)

12月 25th, 2006 by CoraZonado

ECC内存

ECC是“Error Checking and
Correcting”的简写,中文名称是“错误检查和纠正”。ECC是一种能够实现“错误检查和纠正”的技术,ECC内存就是应用了这种技术的内存,一
般多应用在服务器及图形工作站上,这将使整个电脑系统在工作时更趋于安全稳定。

   
要了解ECC技术,就不能不提到Parity(奇偶校验)。在ECC技术出现之前,内存中应用最多的是另外一种技术,就是Parity(奇偶校验)。我们
知道,在数字电路中,最小的数据单位就是叫“比特(bit)”,也叫数据“位”,“比特”也是内存中的最小单位,它是通过“1”和“0”来表示数据高、低
电平信号的。在数字电路中8个连续的比特是一个字节(byte),在内存中不带“奇偶校验”的内存中的每个字节只有8位,若它的某一位存储出了错误,就会
使其中存储的相应数据发生改变而导致应用程序发生错误。而带有“奇偶校验”的内存在每一字节(8位)外又额外增加了一位用来进行错误检测。比如一个字节中
存储了某一数值(1、0、1、0、1、0、1、1),把这每一位相加起来(1+0+1+0+1+0+1+1=5)。若其结果是奇数,对于偶校验,校验位就
定义为1,反之则为0;对于奇校验,则相反。当CPU返回读取存储的数据时,它会再次相加前8位中存储的数据,计算结果是否与校验位相一致。当CPU发现
二者不同时就作出视图纠正这些错误,但Parity有个缺点,当内存查到某个数据位有错误时,却并不一定能确定在哪一个位,也就不一定能修正错误,所以带
有奇偶校验的内存的主要功能仅仅是“发现错误”,并能纠正部分简单的错误。

   
通过上面的分析我们知道Parity内存是通过在原来数据位的基础上增加一个数据位来检查当前8位数据的正确性,但随着数据位的增加Parity用来检验
的数据位也成倍增加,就是说当数据位为16位时它需要增加2位用于检查,当数据位为32位时则需增加4位,依此类推。特别是当数据量非常大时,数据出错的
几率也就越大,对于只能纠正简单错误的奇偶检验的方法就显得力不从心了,正是基于这样一种情况,一种新的内存技术应允而生了,这就是ECC(错误检查和纠
正),这种技术也是在原来的数据位上外加校验位来实现的。不同的是两者增加的方法不一样,这也就导致了两者的主要功能不太一样。它与Parity不同的是
如果数据位是8位,则需要增加5位来进行ECC错误检查和纠正,数据位每增加一倍,ECC只增加一位检验位,也就是说当数据位为16位时ECC位为6位,
32位时ECC位为7位,数据位为64位时ECC位为8位,依此类推,数据位每增加一倍,ECC位只增加一位。总之,在内存中ECC能够容许错误,并可以
将错误更正,使系统得以持续正常的操作,不致因错误而中断,且ECC具有自动更正的能力,可以将Parity无法检查出来的错误位查出并将错误修正。

 

Secure Digital Card

12月 19th, 2006 by CoraZonado

Secure Digital [SD] is a flash based removable memory card. The card
format may also be used other device functions in addition to data
storage. Secure Digital uses a 9-Pin connector [1 rows of 9 pins]. A
compatible card format is called Secure Digital I/O [SDIO]. Refer to the SDIO page for information on that
card standard.


Secure Digital Card

The Secure Digital card dimensions are: 24mm wide x 32mm long.

The Secure Digital I/O card dimensions are: 24mm wide x 32mm long x 2.1mm
thick.

There are two types of SDIO cards; a full-speed version, and a slow-speed
version. The full-speed version will operate with a 1-bit and 4-bit SD
transfer mode, both with a clock ranging from 0Hz to 25MHz. The 4-bit
version operating at 25MHz has a transfer rate of 100Mbps. The slow-speed
version will use the 1-bit mode and may have the 4-bit mode, but only
operates at a transfer rate of between 0Hz and 400kHz. The slow-speed
version is not intended for memory functions. The SDIO card support the
SPI bus interface. The SDIO mechanical form factor is shown above;
however a few gaps "lock notches" are not shown. The SDIO card may exceed
24mm in width after 37mm in length, and the width may be thicker then
2.1mm after 37mm in length

Secure Digital Pinout
Pin # Pin Name SD Signal Function SD Mode SPI Signal Function SPI Mode
1 DAT3/CS Data Line 3 Chip Select/Slave Select [SS]
2 CMD/DI Command Line Master Out/Slave In [MOSI]
3 VSS1 Ground Ground
4 Vdd Voltage Supply [2.7v or 3.6v] Voltage Supply [2.7v or 3.6v]
5 Clock Clock Clock [SCK]
6 Vss2 Ground Ground
7 DAT0/D0 Data Line 0 Master In Slave Out [MISO]
8 DAT1/IRQ Data Line 1 Unused or IRQ
9 DAT2/NC Data Line 2 Unused
Secure Digital I/O Pinout
Pin #

SD 4-bit Mode

SD 1-bit Mode

SPI Mode
1 CD/DAT[3] Data Line 3 N/C Not Used CS Card Select
2 CMD Command Line CMD Command Line DI Data Input
3 VSS1 Ground VSS1 Ground VSS1 Ground
4 VDD Supply Voltage VDD Supply Voltage VDD Supply Voltage
5 CLK Clock CLK Clock SCLK Clock
6 Vss2 Ground Vss2 Ground Vss2 Ground
7 DAT[0] Data Line 0 DATA Data Line DO Data Output
8 DAT[1] Data Line 1 / Interrupt IRQ Interrupt IRQ Interrupt
9 DAT[2] Data Line 2 /Read Wait RW Read Wait NC Not Used

The graphic below provides a comparison of the different Removable memory
Card standards. Many of the different Memory Card standards have
descriptions listed on this web site. The different standards based on
card size are provided. Refer to the Personal Computer Buses page
for more information for different memory types, as listed here.


Memory Board Dimension

Refer to this page for a list of different Flash Memory Stick Formats.

NandFlash和NorFlash的异同

12月 13th, 2006 by CoraZonado

Nand-Flash于NOR-Flash的最大差别在于它是以页面(Page)的形式进行读写访问的;而NOR-Flash是线性空间访问的。通常的
Nand-Flash的结构如下:512Bytes=1Page;32Pages=1Block;N个Blocks构成单颗IC。看到这样的结构,如果您
熟悉FAT16文件系统,您会发现怎么
Nand-Flash的结构同FAT16分区的硬盘如此相似!(在FAT16分区的硬盘中:512Bytes=1Sector;32Sectors=
1Cluster;N个Clusters构成此FAT16分区),这也就是为何Nand-Flash会被列为SSFD(Solid-State
Flash Disk)的原因。

CF卡有TrueIDE、Memory Map等工作模式。当CF卡定义为TrueIDE模式时,CF卡就等同与IDE硬盘,对CF卡的驱动与IDE硬盘的方式完全一样。唯一的不同在于CF卡的50PIN引脚中有一些需要进行特殊处理罢了。

from: http://www.dz863.com/Embedded-Systems-Design/Embedded-Design/NandFlash-NorFlash.htm
一. NAND和NOR的比较
NOR和NAND是现在市场上两种主要的非易失闪存技术。Intel于1988年首先开发出NOR
flash技术,彻底改变了原先由EPROM 和EEPROM一统天下的局面。紧接着,1989年,东芝公司发表了NAND
flash结构,强调降低每比特的成本,更高的性能,并且象磁盘一样可以通过接口轻松升级。但是经过了十多年之后,仍然有相当多的硬件工程师分不清NOR
和NAND闪存。相"flash存储器"经常可以与相"NOR存储器"互换使用。许多业内人士也搞不清楚NAND闪存技术相对于NOR技术的优越之处,因
为大多数情况下闪存只是用来存储少量的代码,这时NOR闪存更适合一些。而
NAND则是高数据存储密度的理想解决方案。NOR的特点是芯片内执行(XIP, eXecute In Place),这样应用程序可以直接在
flash闪存内运行,不必再把代码读到系统RAM中。NOR的传输效率很高,在1~4MB的小容量时具有很高的成本效益,但是很低的写入和擦除速度大大
影响了它的性能。NAND结构能提供极高的单元密度,可以达到高存储密度,并且写入和擦除的速度也很快。应用NAND的困难在于flash的管理和需要特
殊的系统接口。

二.性能比较
flash闪存是非易失存储器,可以对称为块的存储器单元块进行擦写和再编程。任何flash
器件的写入操作只能在空或已擦除的单元内进行,所以大多数情况下,在进行写入操作之前必须先执行擦除。NAND器件执行擦除操作是十分简单的,而NOR则
要求在进行擦除前先要将目标块内所有的位都写为0
。由于擦除NOR器件时是以64~128KB的块进行的,执行一个写入/擦除操作的时间为5s,与此相
反,擦除NAND器件是以8~32KB的块进行的,执行相同的操作最多只需要4ms。执行擦除时块尺寸的不同进一步拉大了NOR和NADN之间的性能差
距,统计表明,对于给定的一套写入操作(尤其是更新小文件时),更多的擦除操作必须在基于NOR的单元中进行。这样,当选择存储解决方案时,设计师必须权
衡以下的各项因素。
☆ NOR的读速度比NAND稍快一些;
☆ NAND的写入速度比NOR快很多;
☆ 大多数写入操作需要先进行擦除操作;
☆ NAND的擦除单元更小,相应的擦除电路更少

三.接口差别
NOR
flash带有SRAM接口
,有足够的地址引脚来寻址,可以很容易地存取其内部的每一个字节。NAND器件使用复杂的I/O口来串行地存取数据,各个产品
或厂商的方法可能各不相同。8个引脚用来传送控制、地址和数据信息。NAND读和写操作采用512字节的块,这一点有点像硬盘管理此类操作,很自然地,基
于NAND的存储器就可以取代硬盘或其他块设备。

四.容量和成本
NAND
flash的单元尺寸几乎是NOR器件的一半
,由于生产过程更为简单,NAND结构可以在给定的模具尺寸内提供更高的容量,也就相应地降低了价格。NOR
flash占据了容量为1~16MB闪存市场的大部分,而NAND
flash只是用在8~128MB的产品当中,这也说明NOR主要应用在代码存储介质中,NAND适合于数据存储,NAND在CompactFlash、
Secure Digital、PC Cards和MMC存储卡市场上所占份额最大。
五.可靠性和耐用性
采用flahs介质时一个
需要重点考虑的问题是可靠性。对于需要扩展MTBF的系统来说,Flash是非常合适的存储方案。可以从寿命(耐用性)、位交换和坏块处理三个方面来比较
NOR和NAND的可靠性。寿命(耐用性)
NAND闪存中每个块的最大擦写次数是一百万次,而NOR的擦写次数是十万次。NAND存储器除了具有10比1的块擦除周期优势,典型的NAND块尺寸
要比NOR器件小8倍,每个NAND存储器块在给定的时间内的删除次数要少一些。位交换所有flash器件都受位交换现象的困扰。在某些情况下(很少见,
NAND发生的次数要比NOR多),一个比特位会发生反转或被报告反转了。一位的变化可能不很明显,但是如果发生在一个关键文件上,这个小小的故障可能导
致系统停机。如果只是报告有问题,多读几次就可能解决了。当然,如果这个位真的改变了,就必须采用错误探测/错误更正(EDC/ECC)算法。位反转的问
题更多见于NAND闪存,NAND的供应商建议使用NAND闪存的时候,同时使用EDC/ECC算法。这个问题对于用NAND存储多媒体信息时倒不是致命
的。当然,如果用本地存储设备来存储操作系统、配置文件或其他敏感信息时,必须使用EDC/ECC系统以确保可靠性。坏块处理NAND器件中的坏块是随机
分布的。以前也曾有过消除坏块的努力,但发现成品率太低,代价太高,根本不划算。NAND器件需要对介质进行初始化扫描以发现坏块,并将坏块标记为不可
用。在已制成的器件中,如果通过可靠的方法不能进行这项处理,将导致高故障率。易于使用可以非常直接地使用基于NOR的闪存,可以像其他存储器那样连接,
并可以在上面直接运行代码。由于需要I/O接口,NAND要复杂得多。各种NAND器件的存取方法因厂家而异。在使用NAND器件时,必须先写入驱动程
序,才能继续执行其他操作。向NAND器件写入信息需要相当的技巧,因为设计师绝不能向坏块写入,这就意味着在NAND器件上自始至终都必须进行虚拟映
射。

六.软件支持
当讨论软件支持的时候,应该区别基本的读/写/擦操作和高一级的用于磁盘仿真和闪存管理算法的软件,包括
性能优化。在NOR器件上运行代码不需要任何的软件支持,在NAND器件上进行同样操作时,通常需要驱动程序,也就是内存技术驱动程序(MTD),
NAND和NOR器件在进行写入和擦除操作时都需要MTD。使用NOR器件时所需要的MTD要相对少一些,许多厂商都提供用于NOR器件的更高级软件,这
其中包括M-System的TrueFFS驱动,该驱动被Wind River System、Microsoft、QNX Software
System、Symbian和Intel等厂商所采用。驱动还用于对DiskOnChip产品进行仿真和NAND闪存的管理,包括纠错、坏块处理和损耗
平衡。
本文在介绍NandFlash和NorFlash的异同的同时,也回答了什么是NandFlash,什么是NorFlash

NAND是高密度数据存储的理想方案,而NOR则最适合代码存储――这通常是低密度的。


表1 NOR闪存和NAND闪存的比较

从SLC到MLC(Multi-Level Cell)

为了适应对低成本、高性能的嵌入式存储不断增长的需求,NAND密度的增长已经超过摩尔定律,每12个月翻一番。2003年MLC的出现使NAND
闪存技术的发展产生了飞跃。由于SLC每个单元只能存储1b,而MLC中每个单元可存储2b,这使得在给定的闪存裸片上,MLC
NAND的密度提高了近80%。因此,MLC NAND有优越的成本结构,但是,它也有固有的缺陷:性能和可靠性都不如SLC NAND。

虽然MLC NAND在成本结构上有所突破,但该技术固有的局限性使它很难集成到现实的应用当中。MLC NAND需要更先进的闪存管理算法和控制来正确处理该技术的以下几个缺陷。

  • 写入速度慢

    尽管其读取速度与SLC NAND相当,MLC NAND的写入速度较慢。

  • 可靠性低

    SLC NAND的出错率为每页(512字节)1b,而目前MLC NAND的出错率是其4倍,未来产品的出错率还有可能更高。另外,MLC NAND产生坏块(bad block)的平均水平也较高,将近5%,因此它需要更有效的管理机制。

  • 闪存管理不兼容

    MLC NAND和SLC NAND的基本机制不同。例如,MLC NAND需要顺序写入,而SLC NAND的写入是无序的。

嵌入式闪存

NAND闪存技术和工艺的进展比芯片组更快。以智能手机的芯片组为例,它从2003年底开始支持small-block SLC
NAND闪存。同年的早些时候large-block SLC和MLC
NAND就已经出现了。到2005年底为止,终于有一些支持large-block NAND闪存的芯片组出现了,但仍没有能够支持MLC
NAND闪存的芯片组。NAND闪存最初是在2001年随EFD(嵌入式闪存驱动)一起进入手机市场的。EFD在同一个芯片上集成了闪存介质和闪存控制,
还带有闪存管理软件。

EFD对NAND闪存的存取是通过像NOR一样的接口,使得它很容易集成到芯片组。EFD还提供了芯片内执行启动区(XIP boot block),使得将NOR闪存完全从主机系统转移成为可能,这显著缩小了材料的尺寸。

由于工艺上不断的压缩,并转向MLC NAND闪存技术,NAND闪存技术的质量降低了,这使EFD变得更加重要。它使得手机设计师不再需要克服利用NAND闪存的障碍了。

很多NAND闪存制造商目前都提供EFD方案,包括Sandisk的iNAND、Samsung的OneNAND以及M-Systems的DiskOnChip,Toshiba也销售DiskOnChip。

迎接挑战

除了不断适应可靠性下降这一技术挑战,其他挑战也相继出现了。首先,是对NAND闪存可靠的分配,这个需求不但很高而且在不断增长。第二个挑战就是最新闪存工艺的实现,这可以从每年NAND闪存价格的大幅下降中受益。

EFD的标准化

为实现开发成本最小化,OEM设计出支持多个方案的平台。由于一个平台的使用寿命大约两年,设计出能够支持最新NAND技术的平台几乎是不可能的。对在主机上运行的闪存管理软件的更新和考察是个费时费力的工作。很多时候,设计师不得不推迟使用最新的NAND技术。

新一代的EFD采用了新的手段,例如M-Systems的DOC H3,它将闪存管理软件作为EFD控制的固件,如图1所示。这一改进的构造使得在已有的平台上使用最先进的NAND技术时能实现即插即用的集成。


图1 闪存管理软件成为EFD控制的固件

从现在到未来

由于手机市场不断提供更多的服务,越来越复杂,对存储容量指数级的增长证明了从基于NOR闪存的手机向基于NAND闪存手机的转变。第二代EFD将使手机制造商支持新的能实现即插即用的NAND技术,帮助他们更快的将新型的、高密度的手机推向市场。

测量温度

12月 10th, 2006 by CoraZonado

热电偶和热电阻的区别

热电偶与热电阻均属于温度测量中的接触式测温,尽管其作用相同都是测量物体的温度,但是他们的原理与特点却不尽相同.

首先,介绍一下热电偶,热电偶是温度测量中应用最广泛的温度器件,他的主要特点就是测吻范围宽,性能比较稳定,同时结构简单,动态响应好,更能够远传4-20mA电信号,便于自动控制和集中控制。热电偶的测温原理是基于热电效应。将两种不同的导体或半导体连接成闭合回路,当两个接点处的温度不同时,回路中将产生热电势,这种现象称为热电效应,又称为塞贝克效应。闭合回路中产生的热电势有两种电势组成;温差电势和接触电势。温差电势是指同一导体的两端因温度不同而产生的电势,不同的导体具有不同的电子密度,所以他们产生的电势也不相同,而接触电势顾名思义就是指两种不同的导体相接触时,因为他们的电子密度不同所以产生一定的电子扩散,当他们达到一定的平衡后所形成的电势,接触电势的大小取决于两种不同导体的材料性质以及他们接触点的温度。目前国际上应用的热电偶具有一个标准规范,国际上规定热电偶分为八个不同的分度,分别为B,R,S,K,N,E,J和T,其测量温度的最低可测零下270摄氏度,最高可达1800摄氏度,其中B,R,S属于铂系列的热电偶,由于铂属于贵重金属,所以他们又被称为贵金属热电偶而剩下的几个则称为廉价金属热电偶。热电偶的结构有两种,普通型和铠装型。普通性热电偶一般由热电极,绝缘管,保护套管和接线盒等部分组成,而铠装型热电偶则是将热电偶丝,绝缘材料和金属保护套管三者组合装配后,经过拉伸加工而成的一种坚实的组合体。但是热电偶的电信号却需要一种特殊的导线来进行传递,这种导线我们称为补偿导线。不同的热电偶需要不同的补偿导线,其主要作用就是与热电偶连接,使热电偶的参比端远离电源,从而使参比端温度稳定。补偿导线又分为补偿型和延长型两种,延长导线的化学成分与被补偿的热电偶相同,但是实际中,延长型的导线也并不是用和热电偶相同材质的金属,一般采用和热电偶具有相同电子密度的导线代替。补偿导线的与热电偶的连线一般都是很明了,热电偶的正极连接补偿导线的红色线,而负极则连接剩下的颜色。一般的补偿导线的材质大部分都采用铜镍合金。
    其次我们介绍一下热电阻,热电阻虽然在工业中应用也比较广泛,但是由于他的测温范围使他的应用受到了一定的限制,热电阻的测温原理是基于导体或半导体的电阻值随着温度的变化而变化的特性。其优点也很多,也可以远传电信号,灵敏度高,稳定性强,互换性以及准确性都比较好,但是需要电源激励,不能够瞬时测量温度的变化。工业用热电阻一般采用Pt100,Pt10,Cu50,Cu100,铂热电阻的测温的范围一般为零下200-800摄氏度,铜热电阻为零下40到140摄氏度。热电阻和热电偶一样的区分类型,但是他却不需要补偿导线,而且比热点偶便宜。

DES算法

11月 8th, 2006 by CoraZonado

一、DES算法

  美国国家标准局1973年开始研究除国防部外的其它部门的计算机系统的数据加密标准,于1973年5月15日和1974年8月27日先后两次向公众发出了征求加密算法的公告。加密算法要达到的目的(通常称为DES
密码算法要求)主要为以下四点:

 

☆提供高质量的数据保护,防止数据未经授权的泄露和未被察觉的修改;

☆具有相当高的复杂性,使得破译的开销超过可能获得的利益,同时又要便于理解和掌握;

☆DES密码体制的安全性应该不依赖于算法的保密,其安全性仅以加密密钥的保密为基础

☆实现经济,运行有效,并且适用于多种完全不同的应用。


   
1977年1月,美国政府颁布:采纳IBM公司设计的方案作为非机密数据的正式数据加密标准(DES?Data Encryption Standard)。

 
 目前在国内,随着三金工程尤其是金卡工程的启动,DES算法在POS、ATM、磁卡及智能卡(IC卡)、加油站、高速公路收费站等领域被广泛应用,以此
来实现关键数据的保密,如信用卡持卡人的PIN的加密传输,IC卡与POS间的双向认证、金融交易数据包的MAC校验等,均用到DES算法。

  DES算法的入口参数有三个:Key、Data、Mode。其中Key为8个字节共64位,是DES算法的工作密钥;Data也为8个字节64位,是要被加密或被解密的数据;Mode为DES的工作方式,有两种:加密或解密。
  DES算法是这样工作的:如Mode为加密,则用Key 去把数据Data进行加密,
生成Data的密码形式(64位)作为DES的输出结果;如Mode为解密,则用Key去把密码形式的数据Data解密,还原为Data的明码形式(64
位)作为DES的输出结果。在通信网络的两端,双方约定一致的Key,在通信的源点用Key对核心数据进行DES加密,然后以密码形式在公共通信网(如电
话网)中传输到通信网络的终点,数据到达目的地后,用同样的Key对密码数据进行解密,便再现了明码形式的核心数据。这样,便保证了核心数据(如PIN、
MAC等)在公共通信网中传输的安全性和可靠性。

  通过定期在通信网络的源端和目的端同时改用新的Key,便能更进一步提高数据的保密性,这正是现在金融交易网络的流行做法。
  DES算法详述

  DES算法把64位的明文输入块变为64位的密文输出块,它所使用的密钥也是64位,整个算法的主流程图如下:
其功能是把输入的64位数据块按位重新组合,并把输出分为L0、R0两部分,每部分各长32位,其置换规则见下表:

58,50,12,34,26,18,10,2,60,52,44,36,28,20,12,4,
  62,54,46,38,30,22,14,6,64,56,48,40,32,24,16,8,

  57,49,41,33,25,17, 9,1,59,51,43,35,27,19,11,3,
  61,53,45,37,29,21,13,5,63,55,47,39,31,23,15,7,

  即将输入的第58位换到第一位,第50位换到第2位,…,依此类推,最后一位是原来的第7位。L0、R0则是换位输出后的两部分,L0是输出的左32位,R0
是右32位,例:设置换前的输入值为D1D2D3……D64,则经过初始置换后的结果为:L0=D58D50…D8;R0=D57D49…D7。

  经过16次迭代运算后。得到L16、R16,将此作为输入,进行逆置换,即得到密文输出。逆置换正好是初始置的逆运算,例如,第1位经过初始置换后,处于第40位,而通过逆置换,又将第40位换回到第1位,其逆置换规则如下表所示:

  40,8,48,16,56,24,64,32,39,7,47,15,55,23,63,31,
  38,6,46,14,54,22,62,30,37,5,45,13,53,21,61,29,

  36,4,44,12,52,20,60,28,35,3,43,11,51,19,59,27,
  34,2,42,10,50,18,58 26,33,1,41,
9,49,17,57,25,
放大换位表
  32, 1, 2, 3, 4, 5, 4, 5, 6, 7, 8, 9, 8, 9, 10,11,

  12,13,12,13,14,15,16,17,16,17,18,19,20,21,20,21,
  22,23,24,25,24,25,26,27,28,29,28,29,30,31,32,
1,
单纯换位表
  16,7,20,21,29,12,28,17, 1,15,23,26, 5,18,31,10,
  2,8,24,14,32,27,
3, 9,19,13,30, 6,22,11, 4,25,
  在f(Ri,Ki)算法描述图中,S1,S2…S8为选择函数,其功能是把6bit数据变为4bit数据。下面给出选择函数Si(i=1,2……8)的功能表:

选择函数Si
S1:
  14,4,13,1,2,15,11,8,3,10,6,12,5,9,0,7,
  0,15,7,4,14,2,13,1,10,6,12,11,9,5,3,8,

  4,1,14,8,13,6,2,11,15,12,9,7,3,10,5,0,
  15,12,8,2,4,9,1,7,5,11,3,14,10,0,6,13,

S2:
  15,1,8,14,6,11,3,4,9,7,2,13,12,0,5,10,
  3,13,4,7,15,2,8,14,12,0,1,10,6,9,11,5,

  0,14,7,11,10,4,13,1,5,8,12,6,9,3,2,15,
  13,8,10,1,3,15,4,2,11,6,7,12,0,5,14,9,

S3:
  10,0,9,14,6,3,15,5,1,13,12,7,11,4,2,8,
  13,7,0,9,3,4,6,10,2,8,5,14,12,11,15,1,

  13,6,4,9,8,15,3,0,11,1,2,12,5,10,14,7,
  1,10,13,0,6,9,8,7,4,15,14,3,11,5,2,12,

S4:
  7,13,14,3,0,6,9,10,1,2,8,5,11,12,4,15,
  13,8,11,5,6,15,0,3,4,7,2,12,1,10,14,9,

  10,6,9,0,12,11,7,13,15,1,3,14,5,2,8,4,
  3,15,0,6,10,1,13,8,9,4,5,11,12,7,2,14,

S5:
  2,12,4,1,7,10,11,6,8,5,3,15,13,0,14,9,
  14,11,2,12,4,7,13,1,5,0,15,10,3,9,8,6,

  4,2,1,11,10,13,7,8,15,9,12,5,6,3,0,14,
  11,8,12,7,1,14,2,13,6,15,0,9,10,4,5,3,

S6:
  12,1,10,15,9,2,6,8,0,13,3,4,14,7,5,11,
  10,15,4,2,7,12,9,5,6,1,13,14,0,11,3,8,

  9,14,15,5,2,8,12,3,7,0,4,10,1,13,11,6,
  4,3,2,12,9,5,15,10,11,14,1,7,6,0,8,13,

S7:
  4,11,2,14,15,0,8,13,3,12,9,7,5,10,6,1,
  13,0,11,7,4,9,1,10,14,3,5,12,2,15,8,6,

  1,4,11,13,12,3,7,14,10,15,6,8,0,5,9,2,
  6,11,13,8,1,4,10,7,9,5,0,15,14,2,3,12,

S8:
  13,2,8,4,6,15,11,1,10,9,3,14,5,0,12,7,
  1,15,13,8,10,3,7,4,12,5,6,11,0,14,9,2,

  7,11,4,1,9,12,14,2,0,6,10,13,15,3,5,8,
  2,1,14,7,4,10,8,13,15,12,9,0,3,5,6,11,

在此以S1为例说明其功能,我们可以看到:在S1中,共有4行数据,命名为0,1、2、3行;每行有16列,命名为0、1、2、3,……,14、15列。

  现设输入为: D=D1D2D3D4D5D6
令:列=D2D3D4D5
  行=D1D6
  然后在S1表中查得对应的数,以4位二进制表示,此即为选择函数S1的输出。下面给出子密钥Ki(48bit)的生成算法
  从子密钥Ki的生成算法描述图中我们可以看到:初始Key值为64位,但DES算法规定,其中第8、16、……64位是奇偶校验位,不参与
DES运算。故Key 实际可用位数便只有56位。即:经过缩小选择换位表1的变换后,Key 的位数由64
位变成了56位,此56位分为C0、D0两部分,各28位,然后分别进行第1次循环左移,得到C1、D1,将C1(28位)、D1(28位)合并得到56
位,再经过缩小选择换位2,从而便得到了密钥K0(48位)。依此类推,便可得到K1、K2、……、K15,不过需要注意的是,16次循环左移对
应的左移位数要依据下述规则进行:

循环左移位数
1,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1
  以上介绍了DES算法的加密过程。DES算法的解密过程是一样的,区别仅仅在于第一次迭代时用子密钥K15,第二次K14、……,最后一次用K0,算法本身并没有任何变化。

 

二、DES算法理论图解

 

DES的算法是对称的,既可用于加密又可用于解密。下图是它的算法粗框图。其具体运算过程有如下七步。

 

三、DES算法的应用误区 

  DES算法具有极高安全性,到目前为止,除了用穷举搜索法对DES
算法进行攻击外,还没有发现更有效的办法。而56位长的密钥的穷举空间为256,这意味着如果一台计算机的速度是每一秒种检测一百万个密钥,则它搜索完全
部密钥就需要将近2285年的时间,可见,这是难以实现的,当然,随着科学技术的发展,当出现超高速计算机后,我们可考虑把DES密钥的长度再增长一些,
以此来达到更高的保密程度。
  由上述DES算法介绍我们可以看到:DES算法中只用到64位密钥中的其中56位,而第8、16、24、……64位8个位并未参与DES运
算,这一点,向我们提出了一个应用上的要求,即DES的安全性是基于除了8,16,24,……64位外的其余56位的组合变化256才得以保证
的。因此,在实际应用中,我们应避开使用第8,16,24,……64位作为有效数据位,而使用其它的56位作为有效数据位,才能保证DES算法安
全可靠地发挥作用。如果不了解这一点,把密钥Key的8,16,24,…..
.64位作为有效数据使用,将不能保证DES加密数据的安全性,对运用DES来达到保密作用的系统产生数据被破译的危险,这正是DES算法在应用上的误
区,留下了被人攻击、被人破译的极大隐患。

AES算法介绍

11月 7th, 2006 by CoraZonado

AES算法应用的理解

比如IPOD播放器,mp3数据采用AES的ECB模式加密,由于是对成密钥,加密和解密使用同一个密码,每次下载MP3文件的对应Key可能不一样。Key的传输可以采用非对称,比如公钥私钥模式。用私钥解开比较少的数据Key,用Key来解开Mp3这个比较多的数据。

AES算法介绍
dayulang 发表于 2006-8-24 10:12:00

高级加密标准(Advanced Encryption Standard)美国国家技术标准委员会(NIST)在2000年10月选定了比利时的研究成果"Rijndael"作为AES的基础。 "Rijndael"是经过三年漫长的过程,最终从进入候选的五种方案中挑选出来的。Rijndael这个名字是从它的两个发明者Rijmen和 Daemen的名字得来的。
结合昨天提供的AES算法的Flash演示动画,可以更好的理解AES算法。
以下是中文原文:

原著:James McCaffrey
翻译:小刀人
 
原文出处:MSDN Magazine November 2003 (Encrypt It)
本文的代码下载:msdnmag200311AES.exe (143KB)
本文假设你熟悉 C# 和 位(bit)操作。
摘要
  AES(The Advanced Encryption Standard)是美国国家标准与技术研究所用于加密电子数据的规范。它被预期能成为人们公认的加密包括金融、电信和政府数字信息的方法。本文展示了 AES的概貌并解析了它使用的算法。包括一个完整的C#实现和加密.NET数据的举例。在读完本文后你将能用AES加密、测试基于AES的软件并能在你的系统中使用AES加密。
  美国国家标准与技术研究所(NIST)在2002年5月26日建立了新的高级数据加密标准(AES)规范。本文中我将提供一个用C#编写的的能运行的 AES 实现,并详细解释到底什么是 AES 以及编码是如何工作的。我将向您展示如何用 AES 加密数据并扩展本文给出的代码来开发一个商业级质量的 AES 类。我 还将解释怎样把 AES 结合到你的软件系统中去和为什么要这么做,以及如何测试基于 AES 的软件。
  注意本文提供的代码和基于本文的任何其它的实现都在联邦加密模块出口控制的适用范围之内(详情请参看 Commercial Encryption Export Controls )。
  AES 是一个新的可以用于保护电子数据的加密算法。明确地说,AES 是一个迭代的、对称密钥分组的密码,它可以使用128、192 和 256 位密钥,并且用 128 位(16字节)分组加密和解密数据。与公共密钥密码使用密钥对不同,对称密钥密码使用相同的密钥加密和解密数据。通过分组密码返回的加密数据的位数与输入数据相同。迭代加密使用一个循环结构,在该循环中重复置换(permutations )和替换(substitutions)输入数据。Figure 1 显示了 AES 用192位密钥对一个16位字节数据块进行加密和解密的情形。
Figure 1 部分数据
AES算法概述
  AES 算法是基于置换和代替的。置换是数据的重新排列,而代替是用一个单元数据替换另一个。AES 使用了几种不同的技术来实现置换和替换。为了阐明这些技术,让我们用 Figure 1 所示的数据讨论一个具体的 AES 加密例子。下面是你要加密的128位值以及它们对应的索引数组:
00 11 22 33 44 55 66 77 88 99 aa bb cc dd ee ff 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
192位密钥的值是:
00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f 10 11 12 13 14 15 16 17 0 1 2 3 4 5 6 7 8 9 10 1112 13 14 15 16 17 18 19 20 21 22 23

Figure 2 S-盒( Sbox )
当 AES 的构造函数(constructor)被调用时,用于加密方法的两个表被初始化。第一个表是代替盒称为S-盒。它是一个16×16的矩阵。S-盒的前五行和前五列如 Figure 2 所示。在幕后,加密例程获取该密钥数组并用它来生成一个名为w[]的密钥调度表,Figure 3 所示。
Figure 3 密钥调度表(Key Sched)
w[] 最初的 Nk (6) 行被作为种子,用原始密钥值(0×00 到0×17)。剩余行从种子密钥来产生。变量 Nk 代表以 32 位字为单位的种子密钥长度。稍后我分析 AES 实现时你将清楚地看到 w[] 是怎样产生的。关键是这里现在有许多密钥使用而不只是一个。这些新的密钥被称为轮密钥(round keys)以将它们与原始种子密钥区别开来。
Figure 4 State (态)数组
AES 加密例程开始是拷贝 16 字节的输入数组到一个名为 State (态)的 4×4 字节矩阵中。(参见 Figure 4)。AES 加密算法 取名为 Cipher,它操作 State[],其过程描述的伪代码参见 Figure 5 。
  在规范中,加密算法实现的一个预备的处理步骤被称为 AddRoundKey(轮密钥加)。AddRoundKey 用密钥调度表中的前四行对 State 矩阵实行一个字节一个字节的异或(XOR)操作,并用轮密钥表 w[c,r] 异或 输入 State[r,c]。
  举个例子,如果 State 矩阵的第一行保存的字节是{ 00, 44, 88, cc },第一列密钥调度表是{ 00, 04, 08, 0c },那么新的 State[0,2] 值是用 w[2,0]( 0×08 或 0×80 )异或 State[0,2](0×88)的结果:
1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 XOR 1 0 0 0 0 0 0 0
AES 算法的主循环对 State 矩阵执行四个不同的操作,在规范中被称为 SubBytes(字节替换)、ShiftRows(行位移变换)、MixColumns(列混合变换) 和 AddRoundKey。除了每次循环 AddRoundKey 都被调用并使用密钥调度表的下面四行外,AddRoundKey 与预备处理步骤中的 AddRoundKey 相同。SubBytes 例程是一个代替操作,它将 State 矩阵中的每个字节替换成一个由 Sbox 决定的新字节。比如,如果 State[0,1]的值是 0×40 如果你想找到它的代替者,你取 State[0,1] 的值 (0×40) 并让 x 等于左边的数字(4)并让 y 等于右边的数字(0)。然后你用 x 和 y 作为索引 进到 Sbox 表中寻找代替值,如 Figure 2 所示。
  ShiftRows 是一个置换操作,它将 State 矩阵中的字节向左旋转。Figure 6 示范了 ShiftRows 如何操作 State[]。State 的第0行被向左旋转0个位置,State 的第1行被向左旋转1个位置,State 的第2行被向左旋转2个位置,而 State 的第3行被向左旋转3个 位置。
Figure 6 对 State 进行 ShiftRows 操作
MixColumns 是一个代替操作,它是理解 AES 算法时最具技巧(或者说是最需要动脑筋的部分)的部分。它用 State 字节列的值进行数学域加和域乘的结果代替每个字节。我将在下一节中 详细解释专门的域加和域乘细节。
  假设 State[0,1] 的值是0×09,并且列1上的其它值分别为 0×60,0xe1 和 0×04,那么State[0,1]的新值计算如下:
State[0,1] = (State[0,1] * 0×01) + (State[1,1] * 0×02) +(State[2,1] * 0×03) +(State[3,1] * 0×01) = (0×09 * 0×01) + (0×60 * 0×02) + (0xe1 * 0×03) +(0×04 * 0×01) = 0×57
此处加法和乘法是专门的数学域操作,而不是平常整数的加法和乘法。
  SubBytes、ShiftRows、MixColumns 和 AddRoundKey 四个操作在一个执行 Nr 次的循环里被调用,Nr 为给定密钥大小的轮数减 1。加密算法使用的轮数要么是10,12,要么是14,这依赖于种子密钥长度是128位、192 位还是 256 位。在这个例子中,因为 Nr 等于12, 则这四个操作被调用11次。该迭代完成后,在拷贝 State 矩阵到输出参数前,加密算法调用 SubBytes、ShiftRows 和 AddRoundKey 后结束。
  大致说来,AES 加密算法的核心有四个操作。AddRoundKey 使用从种子密钥值中生成的轮密钥代替 4 组字节。SubBytes 替换用一个代替表替换单个字节。ShiftRows 通过旋转 4字节行 的 4 组字节进行序列置换。MixColumns 用域加和域乘的组合来替换字节。
有限域GF(28)的加法和乘法
  正如你所看到的,AES 加密算法使用相当简单明了的技术来代替和置换,除 MixColumns 例程以外。MixColumns 使用特殊的加法和乘法。AES 所用的加法和乘法是基于数学(译者注:近世代数)的域论。尤其是 AES 基于有限域GF(28)。
  GF(28)由一组从 0×00 到 0xff 的256个值组成,加上加法和乘法,因此是(28)。GF代表伽罗瓦域,以发明这一理论的数学家的名字命名。GF(28) 的一个特性是一个加法或乘法的操作的结果必须是在{0×00 … 0xff}这组数中。虽然域论是相当深奥的,但GF(28)加法的最终结果却很简单。GF(28) 加法就是异或(XOR)操作。
  然而,GF (28)的乘法有点繁难。正如你稍后将在 C# 实现中所看到的,AES的加密和解密例程需要知道怎样只用七个常量 0×01、0×02、0×03、0×09、0×0b、0×0d 和 0×0e 来相乘。所以我不全面介绍GF(28)的乘法,而只是针对这七种特殊情况进行说明。
  在GF(28)中用0×01的乘法是特殊的;它相当于普通算术中用1做乘法并且结果也同样―任何值乘0×01等于其自身。
  现在让我们看看用0×02做乘法。和加法的情况相同,理论是深奥的,但最终结果十分简单。只要被乘的值小于0×80,这时乘法的结果就是该值左移1比特位。如果被乘的值大于或等于0×80,这时乘法的结果就是用值0×1b异或后的值再左移1比特位。它防止了“域溢出”并保持乘法的乘积在范围以内。
一旦你在GF(28)中用0×02建立了加法和乘法,你就可以用任何常量去定义乘法。用0×03做乘法时,你可以将 0×03 分解为2的幂之和。为了用 0×03 乘以任意字节b, 因为 0×03 = 0×02 + 0×01,因此:
b * 0×03 = b * (0×02 + 0×01) = (b * 0×02) + (b * 0×01)
这是可以行得通的,因为你知道如何用 0×02 和 0×01 相乘和相加,同哩,用0×0d去乘以任意字节b可以这样做:
b * 0×0d = b * (0×08 + 0×04 + 0×01) = (b * 0×08) + (b * 0×04) + (b * 0×01) = (b * 0×02 * 0×02 * 0×02) + (b * 0×02 * 0×02) + (b * 0×01)
在加解密算法中,AES MixColumns 例程的其它乘法遵循大体相同的模式,如下所示:
b * 0×09 = b * (0×08 + 0×01) = (b * 0×02 * 0×02 * 0×02) + (b * 0×01) b * 0×0b = b * (0×08 + 0×02 + 0×01) = (b * 0×02 * 0×02 * 0×02) + (b * 0×02) + (b * 0×01) b * 0×0e = b * (0×08 + 0×04 + 0×02) = (b * 0×02 * 0×02 * 0×02) + (b * 0×02 * 0×02) + (b * 0×02)
  总之,在GF(28)中,加法是异或操作。其乘法将分解成加法和用0×02做的乘法,而用0×02做的乘法是一个有条件的左移1比特位。AES规范中包括大量 有关GF(28)操作的附加信息。
密钥扩展
  AES加密和解密算法使用了一个由种子密钥字节数组生成的密钥调度表。AES规范中称之为密钥扩展例程(KeyExpansion)。从本质上讲,从一个原始密钥中生成多重密钥以代替使用单个密钥大大增加了比特位的扩散。虽然不是无法抵御的困难,但理解 KeyExpansion 仍是 AES 算法中的一个难点。KeyExpansion 例程高级伪代码如下所示:
KeyExpansion(byte[] key, byte[][4] w) { copy the seed key into the first rows of w for each remaining row of w { use two of the previous rows to create a new row } }
“用前面两行来产生一个新行”(“use two of the previous rows to create a new row”)的例程用到了两个子 例程,RotWord 和 SubWord 以及一个名为“Rcon”的常数表(作为“轮常数”)。让我们先来逐个看一下这三东西,然后再回到整个 KeyExpansion 的讨论中来。
  RotWord 例程很简单。它接受一个4个字节的数组并将它们向左旋转一个位置。因为轮调度表 w[] 有四列,RotWord 将 w[]的1行左旋。注意 KeyExpansion 使用的这个 RotWord 函数与加密算法使用的 ShiftRows (行位移变换)例程非常相似,只是它 处理的是单行密钥调度 w[],而不是整个加密状态表 State[]。
  SubWord 例程使用替换表 Sbox 对一给定的一行密钥调度表 w[] 进行逐字节替换。KeyExpansion 操作中的替换实际上就像在加密算法中的替换一样。被代替的输入字节被分成 (x,y) 对,它被当作进入替换表 Sbox 的索引。举例来说,0×27的代替结果是 x=2 和 y=7,并且 Sbox[2,7] 返回 0xcc。
  KeyExpansion 例程使用一个被称为轮常数表的数组 Rcon[]。这些常数都是4个字节,每一个与密钥调度表的某一行相匹配。AES 的 KeyExpansion 例程需要11个轮常数。你可以在 Figure 7 中看到这些常数清单。
  每个轮常数的最左边的字节是GF(28)域中2的幂次方。它的另一个表示方法是其每个值是前一个值乘上0×02,正如前一部分讨论 GF(28) 乘法 时所描述的那样。注意 0×80 × 0×02 = 0×36 是 0×80 左移1个比特位后紧接着与 0×1b 进行异或,如前所述。
  现在让我们更进一步看看 KeyExpansion 内幕中的循环。这里所用的伪码比以前更为详细,这个循环是:
for (row = Nk; row < (4 * Nr+1); ++row) { temp = w[row-1] if (row % Nk == 0) temp = SubWord(RotWord(temp)) xor Rcon[row/Nk] else if (Nk == 8 and row % Nk == 4) temp = SubWord(temp) w[row] = w[row-Nk] xor temp }
先不要去看if子句,你将看到密钥调度表 w[] 的每一行都是前面一行与行 Nk 异或的结果(4, 6, 或 8 取决于密钥的长度)。if条件的第一部分用 SubWord、RotWord 以及与轮常数的异或修改密钥调度表的每个第4、第6或第8行,取决于是否密钥的长度是128、192或256位。这个条件的第二部分将修改行 12、20 和 28 等等――对于256位密钥而言――每 一个第8行都将添加密钥调度额外的可变性。
  让我们用本文开头所举的例子来考察 KeyExpansion 是如何开始的。种子密钥是192-bit / 6-word 值:
00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f 10 11 12 13 14 15 16 17
  密钥调度字节表 w[] 的维数是 4 列并且 Nb × (Nr + 1) 等于 4 × (12 + 1),或 52 行。KeyExpansion 将种子密钥的值拷贝到密钥调度字节表 w[] 的第一行。因为我的种子密钥是 192 位(24字节),并且 w[] 表总是 4 列,在这种情况下KeyExapansion 将种子密钥拷贝到 w[] 的前面 6 行。现在让我们看看 KeyExapansion 例程是如何填充密钥调度表其余部分的。在我的例子里,第一个被计算的行是第 6 行 ,因为第0-5行已被种子密钥的值填上了:
temp = w[row-1] = 14 15 16 17
条件 (row % Nk == 0)为真,因此首先 RotWord 子程序被应用:
temp = 15 16 17 14
这时 SubWord 被应用:
temp = 59 47 f0 fa
用 Rcon[row / Nk] = Rcon[6 / 6] = 01 00 00 00 进行异或:
temp = 58 47 f0 fa
这时用 w[row-Nk] = w[6-6] = 00 01 02 03 异或,产生了下面结果:
w[6] = 58 46 f2 f9
密钥调度表 w[] 中其余所有行来重复这个过程本身。
  总而言之,AES 加密和解密的一个重要部分就是从最初的种子密钥中生成多重轮密钥。这个 KeyExapansion 算法生成一个密钥调度并 以某种方式进行替代和置换,在这种方式中,加密和解密算法极其相似。
用 C# 编写 AES 类构造函数
  现在我已研究了构成 AES 加密算法的各个成分,我将用 C# 来实现它。官方的 AES 算法规范包含在联邦信息处理标准出版物197 (Federal Information Processing Standards Publication 197)中。我决定尽可能贴切地以它作为我的实现的基础,但是我很快发现这个规范更是一个理论文献而非一个实现的向导。为了将这个官方规范作为资源来使用,我使用 的变量名与标准出版物中所用的相同。(即便它们是那么晦涩,如“Nr”和“W”)。
我的设计使用9个数据成员和一个枚举类型,如下所示:
public enum KeySize { Bits128, Bits192, Bits256 }; private int Nb; private int Nk; private int Nr; private byte[] key; private byte[,] Sbox; private byte[,] iSbox; private byte[,] w; private byte[,] Rcon; private byte[,] State;
因为密钥长度只能是128位、192位或256位比特,它是非常适于用枚举类型:
public enum KeySize { Bits128, Bits192, Bits256 };
  该规范文档一般用字节作为基本储存单元而不是用4字节的字作为两个重要数据成员的长度。这两个成员 Nb 和 Nk 代表以字为单位的块长以及以字为单位的密钥长度。Nr代表轮数。块长度总是16字节(或这说是 128 位,即为 AES 的 4个字),因此它可以被声明为一个常量。密钥长度 依照枚举参数 KeySize 的值被赋值为 4、6 或 8。AES 算法强调通过大量轮数来增加加密数据的复杂性。轮数是10、12或14中的任意一个并且是基于密码分析学理论的。它直接取决于密钥长度。
  当设计一个类接口时,我喜欢向后来做。我设想从应用程序中调用构造函数和方法。使用这个办法,我决定象下面这样来实例化一个 AES 对象:
Aes a = new Aes(the key size, the seed key)
我调用的加密和解密例程如下:
a.Cipher(plainText, cipherText); a.InvCipher(cipherText, decipheredText);
我选择少许笨拙的方法来命名 Cipher 和 InvCipher,因为它们是用在 AES 规范文档中的。这里是 AES 类构造函数的代码为:
public Aes(KeySize keySize, byte[] keyBytes) { SetNbNkNr(keySize); this.key = new byte[this.Nk * 4]; keyBytes.CopyTo(this.key, 0); BuildSbox(); BuildInvSbox(); BuildRcon(); KeyExpansion(); }
  该构造函数首先调用一个辅助方法 SetNbNkNr 给 Nb、Nk 和 Nr 赋值,如 Figure 8 所示。如果考虑到效率,你可能将这些代码直接放入构造函数 以避免方法调用的开销。
  接下来,你必须将传入构造函数的字节拷贝到类域变量中。密钥用其它的类域声明,并且用如下方法获得它的值:
this.key = new byte[this.Nk * 4]; keyBytes.CopyTo(this.key, 0);
  我决定在构造函数中调用私有辅助方法 BuildSbox 和 BuildInvSbox 来初始化替换表 Sbox[] 和 iSbox[] 。现在密钥扩展例程 、Cipher 方法和 InvCipher 方法各自都需要 Sbox[] 和 iSbox[],因此我本来可以在 Cipher 和 InvCipher 两个方法中初始化 Sbox[] 并调用 KeyExpansion 方法,但是将它们放入构造函数会代码结构更加清晰。在 Figure 9 中 sBox[] 被填充。填充 iSbox[] 代码类似。为了可读性对代码进行了结构化处理。正如后面你将看到的,还有另外一个可供选择的令人惊讶的方法为 Sbox 和 iSbox 表提供值。
  在构造函数中声明密钥调度表 w[]、轮常数表 Rcon[] 和状态矩阵 State[],并用私有辅助方法来给 Rcon[] 和 w[] 赋值在我看来似乎是组织它们的最好办法,但那主要还是个风格问题。置换轮常数表 Rcon 的赋值代码参见 Figure 7。
回想一下,GF(28)中,Rcon[] 每一行左边的字节都 2 的幂,因此这个表可用下面的方法建立:
newVal = prevVal * 0×02;
  AES 构造函数在建立完密钥调度表 w[] 后结束,而 w[] 是在 KeyExpansion 方法中完成的(参见 Figure 10)。其代码相当简单。规范文档使用一个假设的 4-字节的字数据类型。因为 C# 没有那样的类型,但可以用一个4个字节的数组来模拟。在用 new 操作符为密钥调度 表 w[] 分配空间后,w[] 最初的 Nk(4, 6, 或 8) 行从被传递到构造函数的种子密钥 key[] 数组中获值。
this.w[row,0] = this.key[4*row]; this.w[row,1] = this.key[4*row+1]; this.w[row,2] = this.key[4*row+2]; this.w[row,3] = this.key[4*row+3];
  两个字节相互的异或操作在这个代码中频频发生。它需要一些从 byte 到 int 的强制类型转换并转回到 byte,因为异或操作“^”是不能定义在 C# 的 byte 类型上,例如:
temp[0] = (byte)( (int)temp[0] ^ (int)this.Rcon[row/Nk,0] );
用来替代:
temp[0] = temp[0] ^ this.Rcon[row/Nk,0];
  KeyExpansion 方法有条件地调用私有方法 SubWord 和 RotWord 以保持同规范命名的一致性。此外,因为在C#中没有 word类型,我用 4字节数组实现了一个字。SubWord 和 RotWord 的代码是相当简单,参见本文附带的 AesLib 源代码,它应该很容易理解。
  稍微具备有些技巧的部分是在 SubWord 中查找替代值。回想一下,为了寻找代替值,你将输入字节分成最左边的4位比特和最右边的4位比特。对于一个给定字节,用 >> 操作符右移 4 位将得到 x 索引,并且与 0000 1111 进行逻辑与得到 y 值。虽然有些长,但比实际代码更可读,我可以象下面这样:
int x = word[0] >> 4; int y = word[0] & 0×0f; byte substitute = this.Sbox[x,y]; result[0] = substitute;
代替我原来用的代码:
result[0] = this.Sbox[ word[0] >> 4, word[0] & 0×0f ];
  总的来说,AES 构造函数接受一个密钥的长度为128,192 或 256 位和一个字节数组种子密钥值。构造函数为输入块长度,种子密钥长度以及加密算法的轮数赋值,并将种子密钥拷贝到一个名为 key 的数据成员中。构造函数还创建了四个表:两个由加密和解密方法使用的替换表,一个轮常数表,和一个轮密钥的密钥调度表。
用C#编写的 AES Cipher 方法
  Cipher方法如 Figure 11 所示。它真的非常简单,因为它分出了大部分的工作给私有方法AddRoundKey, SubBytes, ShiftRows 和 MixColumns。
  Cipher 方法以拷贝明文输入数组到状态矩阵 State[] 为开始。最初调用 AddRoundKey 之后,Cipher 方法比总轮数少迭代一次。在最后一轮时,正如规范中所说的那样,MixColumns 调用被省略了。
  AddRoundKey 和 SubBytes 私有方法的代码如 Figure 12 所示。AddRoundKey 方法需要知道它处在那一轮,以便它正确引用4行密钥调度数组 w[]。请注意 State[r,c] 是用 w[c,r] 来异或并不是w[r,c]。SubBytes 方法从输入字节中提取索引,与 KeyExpansion 方法中所用的右移4位和 0×0f 屏蔽技术相同。
  ShiftRows 方法的代码如 Figure 13 所示。回想一下,ShiftRows(可能叫做 RotateRows 更好)将 row[0] 向左旋转 0 个位置,将 row[1] 向左旋转 1 位置等等。
把 State[] 拷贝到 temp[] 矩阵之后,然后用下面的这行代码实现转换:
this.State[r, (c + r) % Nb ] = temp[r,c];
这里利用%操作符的优点抱合一行。
  MixColumns 方法(Figure 14)用GF(28)加和乘,以字节列中所有其它值的线性组合对每一个字节进行替换。
乘法所用的常量系数基于域论的,并且是0×01, 0×02或 0×03中的任意一个值。给定某一列 c ,其替代式如下:
State[0,c] = 0×02 * State[0,c] + 0×03 * State[1,c] + 0×01 * State[2,c] + 0×01 * State[3,c] State[1,c] = 0×01 * State[0,c] + 0×02 * State[1,c] + 0×03 * State[2,c] + 0×01 * State[3,c] State[2,c] = 0×01 * State[0,c] + 0×01 * State[1,c] + 0×02 * State[2,c] + 0×03 * State[3,c] State[3,c] = 0×03 * State[0,c] + 0×01 * State[1,c] + 0×01 * State[2,c] + 0×02 * State[3,c]
  这些表达式稍微有些长,因此我决定编写返回 GF(28)与 0×01,0×02 和 0×03 之乘积的私有辅助函数。这些辅助函数非常短。例如,一个字节 b 被 0×03 域乘的代码如下:
return (byte) ( (int)gfmultby02(b) ^ (int)b );
  正如我前面讨论的,被 0×02 乘是所有 GF(28) 乘法的基本操作。我调用了我的 gfmultby02 方法,我改变了使用与规范相同的方法命名惯例,规范上称此例程为 xtime。
  Cipher 方法其输入反复应用四个操作来产生加密的输出。AddRoundKey 用源于单个原始种子密钥的多重轮密钥来替代字节。SubBytes 用某个替换表中的值替代字节。ShiftRows 用移动字节行置换字节,而 MixColumns 用某一列的域加和乘法值来替代字节。
用C#编写 AES InvCipher 方法
  AES 解密算法背后的基本原则很简单:解密一个加密块,也就是以反向顺序还原(Undo)每个操作。尽管这是基本概念,但仍有几个细节要处理。
  AES规范称解密例程为 InvCipher,而不是 Decipher 或 Decrypt 中的一个。这是 AES 背后的数学基础的反映,它基于可逆的数学操作。
  如果你将这个代码和 Cipher 代码比较的话,你会看到它比你预期的漂亮很多,但是有两点例外。首先,在 InvCipher 方法中逆方法调用(如 InvSubBytes)顺序并不完全与在 Cipher 方法中相应调用(如 SubBytes)的逆向顺序正好相同。其次,InvCipher 调用的是一个 AddRoundKey 方法而不是 InvAddRoundKey 方法。值得注意的是 InvCipher 算法用密钥调度表并不是从较高编号的索引处开始向下处理至第0行。
  InvSubBytes, InvShiftRows 和 InvMixColumns 方法的代码和与之有关的 SubBytes,ShiftRows和 MixColumns 方法的代码非常接近。InvSubBytes 方法几乎就是 SubBytes 方法,只是它用逆替换表 iSbox[] 而不是 Sbox[] 表。
  正如你可能猜测到的,iSbox[] 就是还原任何被 Sbox[] 处理的对应操作。比如,如果你有字节 b 等于 0×20,并在 Sbox[] 中找到其代替值,你得到 0xb7。如果你在 iSbox[] 中找到 0xb7的替代值,你便可得到 0×20。
  相似地,InvShiftRows 方法还原 ShiftRows 方法―― row[0] 被右移了 0 个位置,row[1] 被右移了 1个位置,row[2] 被右移了 2 个位置,而 row[3] 被右移了 3个位置。
  InvMixColumns 方法还原 MixColumns 的工作,但没有用显而易见的方法。回想一下,MixColumns 用原始字节列中的字节线性组合替换状态矩阵中的每个字节,并且系数是 0×01,0×02,和 0×03,域论再一次得到应用。它证明逆运算是相似的,只是被 0×09,0×0b,0×0d 和 0×0e 乘,如下所示:
State[0,c] = 0×0e * State[0,c] + 0×0b * State[1,c] + 0×0d * State[2,c] + 0×09 * State[3,c] State[1,c] = 0×09 * State[0,c] + 0×0e * State[1,c] + 0×0b * State[2,c] + 0×0d * State[3,c] State[2,c] = 0×0d * State[0,c] + 0×09 * State[1,c] + 0×0e * State[2,c] + 0×0b * State[3,c] State[3,c] = 0×0b * State[0,c] + 0×0d * State[1,c] + 0×09 * State[2,c] + 0×0e * State[3,c]
  对于 MixColumns 方法,我决定专门写一个辅助函数,而不是内联展开已经较长的表达式或写一个普通的乘法辅助函数。让我向你展示一下我示如何编写这个任何字节 b 被常数 0×0e (在10进制中的14)乘的函数,像任何数字一样,数字 14 可以被表示成 2 的幂的和,因此,14 等于 2 + 4 + 8。并且 4 等于 2 的平方,8 等于 2 的立方,你可以将14表示为 2 + 22 + 23。记住加法就是 GF(28)中上的异或(^),既然我已经有了 gfmultby02 函数,我可以用它得到我的结果:
return (byte)( (int)gfmultby02(gfmultby02(gfmultby02(b))) ^ /* 23 + */ (int)gfmultby02(gfmultby02(b)) ^ /* 22 + */ (int)gfmultby02(b) ); /* 2 */
用于 AES 加密算法的所有的操作都是可逆的,因此解密算法本质上是加密的所有操作的倒转。
使用 AES 类
  用C#实现 AES 的特色之一就简单。看看 Figure 15,它是我用来生成输出 Figure 1 的代码。声明了 16 字节明文输入硬代码值和 24 字节(192位)的种子密钥后,一个 AES 对象被初始化,加密 Cipher 方法 将明文加密成为密文,然后再用 InvCipher 将密文解密。非常清楚和简单。
  因为 AES 对象针对字节数组进行处理,你可以轻松地用它处理.NET的其它数据类型。我创建了一个基于 Windows 的小Demo程序,它接受一个单纯的字符串――有 8 个字符 (16-byte) ,对它进行加密和解密处理。运行画面如 Figure 16。
Figure 16 加密 Demo 程序
因为加密和解密例程都需要知道用户定义的密钥长度,我把它当作一个类范围的变量来声明,像这样:
private Aes.KeySize keysize;
  注意种子密钥并不是由用户定义的。这个 demo 程序用一个“空密钥”(null key)作为种子密钥,通过为构造函数提供一个哑参数 new byte[16] 使得它全部由零字节组成。哑参数的长度是不相关的,因为种子密钥还是要被初始化为零。空密钥加密和解密是一个容易和有效的办法来阻止外界对数据偶然的检查。在 System.Text 中的 Encoding.Unicode.GetBytes和Encoding.Unicode.GetString 方法使得将一个.NET 字符串转换成一个字节数组变得非常容易,反之亦然。

实现选择
  现在让我们看看本文 AES 实现中出现的一些重要的变量,本文提供的代码可能出现的扩展,以及针对 AES 的密码分析学攻击。
  和我曾经处理的任何代码一样,AES 算法也可以用其它可选的途径来实现。为什么这很重要呢?AES 被试图广泛应用于各种系统,从只有很少内存容量的智能卡(smart cards)到大型的多处理器主机系统。在许多情况下,性能是关键因素,并且有时内存或处理器资源是有限的。事实上,AES 的每个例程都能针对非常昂贵的内存资源进行性能优化,反之亦然。比如,为替换表Sbox[] 分配 256 个值看起来好像很简单直白。但是,这些值是基于 GF(28) 理论的,它们都可以用编程方式来生成。逆向替换表和轮常数表也是如此。
  可选实现另外一个有趣的可能性是 Cipher 和 InvCipher 方法所用的 GF(28) 乘法。我的实现代码是一个被 0×02 乘的基本函数,而后是六个调用 gfmultby02 的附加函数。另一个可能性应该是写一个一般的乘法函数,并用它代替我目前实现的七个单独函数。另一个极端是你可以用被 0×01, 0×02, 0×03, 0×09, 0×0b, 0×0d 和 0×0e 乘好的所有 256 个可能的字节值构成的一个完整乘积表。此外,实现 GF(28) 乘法另一途径是通过在两个 256 个字节的数组里查找,通常称为 alog[] 和 log[],因为它们在 GF(28)中基于某些类似对数的方法。
  虽然这里给出的 AES 类完全能用于加密任何形式的.NET数据,你可能考虑想用各种方法扩展它。首先,因为本文的重点在于清楚地解释 AES,所有错误检查被剥离掉,以我的经验,为某个象 AES 这样的类添加合理数量的错误检查将会产生三倍的代码量膨胀。因为 AES 使用了这么多的数组,需要做很多索引 边界检查。例如,所给出的构造函数甚至都不检查种子密钥参数的长度。
  你可能还考虑通过添加更多的特性来扩展 AES 类。最明显的一个地方是添加加密和解密.NET基本数据类型的方法,比如:System.String 和 System.Int32。更加雄心勃勃的扩展可能会是实现一个 流数据加密类。
  AES 的安全性怎样呢?这是一个很难回答的问题,但是一般多数人的意见是:它是目前可获得的最安全的加密算法。AES 已被列为比任何现今其它加密算法更 安全的一种算法。在理论和实践基础上,AES 被认为是“安全的”,因为要破解它的话,唯一有效的方法是强行(brute-force)生成所有可能的密钥。 如果密钥长度为 256 位,还没有已知的攻击可以在一个可接受的时间内破解 AES(即便在当今最快的系统上,它也要花费数年时间)。
  注意针对 AES 密码最可能成功的攻击来自一个允许时间选择攻击的弱实现。攻击者用不同的密钥并精确地测量出加密例程所需的时间。如果加密例程被粗心编码,因此执行时间便依赖于密钥值,它就有可能推导出有关密钥的信息。在 AES 中,这种事情最可能发生在 MixColumns 例程中,因为有域乘。针对这种攻击的两个安全措施是加入虚指令,以便所以所有乘法都需要相同数量的指令,或者将域乘实现为一个查询表,就象我前面描述的那样。
  AES 有许多种可能的实现,尤其是是使用查询表而不是计算。本文提供的 AES 基本类可以被用于加解密任何形式的.NET数据或 被扩展成一个具有更多功能的类。
结束语
  新的 AES 将无疑成为加密所有形式电子信息的事实上的标准,取代 DES。AES 加密的数据在某种意义上是牢不可破的,因为没有已知的密码分析攻击可以解密 AES 密文,除非强行遍历搜索所有可能的 256 位密钥。
  我发现在 Microsoft .NET Framework 上实现 AES 类的主要的障碍是官方文档是以一个数学家的观点,而不是以一个软件开发者的观点来写的。尤其是该规范假定读者十分熟悉 GF(28) 域,并省略了几个正确实现 AES 所必需的关于 GF(28) 乘法的关键事实。我在本文中试图努力去掉 AES 的神秘面纱,特别是围绕在 GF(28) 域乘法部分的。
  以 .NET Framework 库的形式从 Microsoft 以及第三方供应商处获得对 AES 的广泛支持只是一个时间问题。然而,处于种种理由,让本文代码作为你的技能储备仍然是有价值的。这个实现尤其简单,并且是低资源开销。另外,阅读并理解源代码将使你能定制 AES 类且更有效地使用它的任何实现。
  在任何软件设计过程中安全已不再是后顾之忧。AES 是一个重大进步,使用并理解它将大大增加软件系统的可靠性和安全性。
相关文章
* Security: Protect Private Data with the Cryptography Namespaces of the .NET Framework
* Exploring Kerberos, the Protocol for Distributed Security in Windows 2000
背景信息
  The Design of Rijndael: AES - The Advanced Encryption Standard by Joan Daemen and Vincent Rijmen. (Springer-Verlag, 2002)
  Announcing the Advanced Encryption Standard (AES): Federal Information Processing Standards Pub 197
作者简介
  James McCaffrey 在Volt Information Sciences Inc公司工作,在那里他管理为 Microsoft 的软件工程师技术培训。他作为一些 Microsoft 产品的承包人工作包括 Internet Explorer 和 MSN Search。可通过 jmccaffrey@volt.com 或
v-jammc@microsoft.com与他联系。

转自:http://mapcat.spaces.live.com/blog/


登录 | 访问数79996 | 水木BLOG | 水木社区 | 关于我们 | Blog论坛 | 法律声明 | 隐私权保护 | 京ICP证050249号
水木社区Blog系统是基于KBS系统WordPress MU架构的