第2章密码技术9.24

第2章密码技术2.1密码技术的基本概念2.2古典密码体制2.3对称密码体系2.4公钥（非对称）密码体制2.5椭圆曲线密码体制学习目标知识点：密码技术的基本概念，古典密码体制如置换密码、代换密码，对称密码体制如流密码、分组密码、数据加密标准（DES）、高级加密标准（AES），公钥密码体制如公钥密码体制的基本原理、RSA算法、RSA算法与数字签名、RSA算法与DES算法的特点等重点：古典密码体制，数据加密标准（DES），高级加密标准（AES），公钥加密体制的基本原理，RSA算法难点：AES算法、RSA算法2.1密码技术的基本概念图2.1传统加密体制的基本过程加密过程：c=E（m，ke）解密过程：m=D（c，kd），所以有m=D（E（m，ke），kd）如果ke=kd，称为单钥或对称密码体制如果ke≠kd，称为双钥或非对称密码体制于1976年由Diffie和Hellman等人所开创的新体制2.2古典加密技术2.2.1置换密码置换密码亦称换位密码。置换只是简单的换位可用一个置换矩阵来Ek表示且都有一个与之对应的逆置换Dk特点采用一个仅有发送方和接收方知道加密置换（用于加密）及对应的逆置换（用于解密）只对明文中的字母位置进行重新排列，而每个字母本身并不改变令明文m=m0,m1,…,mL-1。令置换矩阵所决定的置换为π，则加密置换c=Ek(m)=(c0,c1,…,cL-1)=mπ(0),mπ(1),…,mπ(L-1)

解密置换举例给定明文thesimplestpossibletranspositionciphers，将明文分为L=5的段，置换密码如下举例最后一段长不足5，加添一个字母x。将各段的字母序号按下述置换矩阵进行换位得到密文为:histepsemlpsstobteilapsrnsitoinpiocexshr利用下述置换矩阵：可将密文恢复为明文L=5时可能的置换矩阵总数为5！=120。一般为L!个。可以证明，在给定L下所有的置换矩阵构成一个L!对称群2.2.2代换密码令Γ表示明文字母表，内有q个“字母”或“字符”。设其顺序号为：0,1,...,q-1，可以将Γ映射为一个整数集Zq={0,1,2,…,q-1}，在加密时常将明文信息划分为长为L的信息单元，称为明文组。以m表示，如m=(m0,m1,…,mL-1),mi∈Zq令Γ′表示明文字母表，内有q′个“字母”或“字符”。设其顺序号为：0,1,...,q′-1，可以将Γ′映射为一个整数集Zq′={0,1,2,...,q′-1}，密文组为c=(c0,c1,…,cL′-1),ci∈Zq′，代换密码的加密变换是由明文空间到密文空间的映射f:m→c,m∈Γ,c∈Γ′假定函数f是一对一的映射，那么，给定密文c，有且仅有一个对应的明文组m，即对于f存在逆映射f-1，使f-1(c)=f-1f(m)=m加密变换通常是在密钥控制下进行的，即c=f(m,k)=Ek(m)

1．单表代换密码单表代换密码是对明文的所有字母都用同一个固定的明文字母表到密文字母表的映射，即f:Zq→Zq'若明文为m=m0,m1,……,则相应的密文为c=c0,c1,….=f(m0),f(m1),…1）位移代换密码位移代换密码是最简单的一种代换密码，其加密变换为Ek(i)=(i+k)≡jmodq0≤i,j<q,0≤k<q密钥空间元素个数为q，其中有一恒等变换，k=0，解密变换为D(j)≡imodq举例如凯撒密码变换是对英文26个字母进行位移代换的密码，即将每一字母向前推移k位。若q=26，如选择密钥k=5，则有下述变换:

明文：abcdefghijklmno

密文：fghIjklmnopqrst2）乘数密码--也称采样密码其加密变换为

:Ek(i)=i*k≡jmodq0≤j<q是将明文字母表按序号每隔k位取出一个字母排列而成密文特点:当且仅当(k,q)=1，加密交换才是一一对应缺点:对于英文序列密文所对应的密钥非常有限，即q只能取:1357911151719212325举例如英文字母表q=26，选k=9，则由明文密文字母对应表明文:abcdefghijklmnopqrstuvwxyz密文:AJSBKTCLUDMVENWFOXGPYHQZIR对明文：Multiplicativercipher有密文：EYVPUFVUSAPUHKSUFLKX3）仿射密码将移位密码和乘数密码进行组合即 Ek(i)=ik1+k0≡jmodqk1,k0∈Zq，其中，(k1,q)=1,以［k1,k0］表示密钥。当k0=0时就得到乘数密码，当k1=1时就得到位移密码，q=26时可能的密钥数为26×12-1=311个2．多表代换密码多表代换密码是一系列（两个以上）代换表依次对明文信息的字母进行代换的加密方法维吉尼亚密码加密算法是多表密码的典型代表。方法如下：设密钥k=k1,k2,…,kn，明文m=m1,m2,…,mn，加密变换为Ek(m)=c1,c2,…,cn

，其中ci≡（mi+ki）modqi=1,2,…,n举例如，令q=26，明文m=polyalphabeticcipher，k=RADIO，即周期为5。首先将m分解成长为5的序列:

polyalphabeticcipher

每一段用密钥k=RADIO加密得密文：

c=GOOGOCPKTPNTLKQZPKMF2.3对称密码体系2.3.1流密码流密码也称为序列密码，其原理是对输入的明文串按比特进行连续变换，产生连续的密文输出信道ciD(ki,ci)cimiE(ki,mi)mi

密钥流生成器kiki

密钥流生成器

k

k安全信道流密码的基本思想密钥:k，产生一个密钥流为k=k1k2…ki…明文串:m=m1m2…mi…加密：密钥流发生器f：ki=f(k,σi)σi是加密器中的记忆元件（存储器）在时刻i的状态，f是由密钥k和σi产生的函数根据加密器中记忆元件的存储状态σi是否依赖于输入的明文字符，流密码可分为同步流密码：σi独立于明文字符自同步流密码：σi不独立于明文字符。由于自同步流密码的密钥流的产生与明文有关，因而较难从理论上进行分析。目前大多数研究成果都是关于同步流密码的1.同步流密码在同步流密码中，由于ki=f(k,σi)与明文字符无关，因而此时密文字符ci=Eki(mi)也不依赖于此前的明文字符同步流密码特点只要通信双方的密钥序列产生器具有相同的“种子序列”和相同的“初始状态”,就能产生相同的密钥序列通信双方必须保持精确同步,才能正确解密容易检测插入、删除、重放等主动攻击没有差错传播2.自同步流密码产生密钥序列的算法与以前的密文有关自同步流密码的特点密钥流生成器是一种有记忆变换器密钥流与明文符号有关：i时刻的密文不仅取决于i时刻的明文，而且与i时刻之前的l个明文符号有关具有自同步能力把明文每个字符扩散在密文多个字符中,强化了抗统计分析的能力3.密钥流生成器流密码的关键是密钥生成器ki序列密码系统中密钥序列设计应考虑如下因素：系统的安全保密性；密钥易于分配、保管、更换；产生密钥序列简单、快速为达到安全保密性要求，序列密码的密钥序列应满足伪随机准则：极大的周期良好的随机统计特性，即序列中每位接近均匀分布序列线性不可预测性充分大(抗线性分析)抗统计分析4．线性反馈移位寄存器产生密钥流序列的最重要部件是线性反馈移位寄存器LFSR（linearfeedbackshiftregister）,是因为:LFSR非常适合于硬件实现能产生大的周期序列能产生较好统计特性的序列其结构能应用代数方法进行很好的分析如果反馈函数f(a1,a2,…,an)是(a1,a2,…,an)的线性函数，则称之为线性反馈移位寄存器，否则称为非线性移位寄存器n级反馈移位寄存器2.3.2分组密码也称块密码分组密码加密是在密钥的控制之下，将定长的明文块转换成等长密文的技术。分组密码使用同一密钥通过逆向变换来实现解密加密算法解密算法明文m=(m0,m1,…,mn-1)

密文c=(c0,c1,…,cn-1)明文m=(m0,m1,…,mn-1)密钥k=(k0,k1,…,kt-1)

密钥k=(k0,k1,…,kt-1)2.3.2分组密码在分组密码中，必须处理一个问题——填充在分组加密中，要求填充是可逆的假定块长度为8字节，要加密的明文数据长度为9字节。那么消息被切成两个块，第二块只有1个字节，需要填充7个字节。如果把9字节的明文数据记为：F1F2F3F4F5F6F7F8F9Zeros填充算法：需要填充的7个字节全部填充为0，分组结果为：第一个消息分组：F1F2F3F4F5F6F7F8第二个消息分组：F900000000000000Zeros填充算法无法区分第二个消息分组中F9后的0序列是否是明文中的原始序列，因此该填充算法不可逆

X923填充算法：需要填充的7个字节中前6个字节填充0，最后一个字节记录填充的总字节数，分组结果为：第一个消息分组：F1F2F3F4F5F6F7F8第二个消息分组：F900000000000007PKCS7填充算法：需要填充的7个字节中的每一个字节填充需要填充的总字节数，分组结果为：第一个消息分组：F1F2F3F4F5F6F7F8第二个消息分组：F907070707070707

ISO10126填充算法：需要填充的7个字节中前6个字节填充随机字节序列，最后一个字节记录填充的总字节数，分组结果为：第一个消息分组：F1F2F3F4F5F6F7F8第二个消息分组：F97D2A75EFF8EF07迭代的分组密码是在加密过程有多次循环的密码，因此提高了安全性。在每个循环中，可以通过使用特殊的函数从初始密钥派生出的子密钥来进行适当的变换分组密码的主流算法包括：DES、AES、IDEA、SAFER、Blowfish和Skipjack迭代密码明文：X=Y(0)密文：Y=Y(r)迭代函数:F迭代次数:r种子密钥：k迭代的子密钥：Z(i)Feistel密码结构是基于1949年Shannon提出的交替使用代换和置换方式构造密码体制的设想提出的Feistel密码Feistel加密结构子密钥产生算法

KK1,K2,…,Kh明文:m=L0||R0第i轮迭代

Li=Ri-1

Ri=Li-1F(Ri-1,Ki)F:轮函数密文:c=Lh+1||Rh+1代换-置换网络(substitution-permutationnetwork)FL1R1K1L0(w-bit)R0(w-bit)

明文:m(2w-bit)FLiRiKi….….….….FLhRhKhLh+1Rh+1

密文:c(2w-bit)Feistel分组密码的一个加密阶段示意图其中S操作通过密钥为每一个阶段生成一个子密钥，T为每一轮加密过程中的核心操作，要求为非线性运算，保证加密算法的安全性明文LRL’R’TS替换置换密钥Feistel解密结构与加密结构相同子密钥使用次序相反:

Kh,Kh-1,…,K2,K1输入：密文c输出：明文mFL1R1KhL0(w-bit)R0(w-bit)

密文:c(2w-bit)FLiRiKi….….….….FLhRhK1Lh+1Rh+1

明文:m(2w-bit)2.3.3数据加密标准（DES）数据加密标准（DataEncryptionStandard，DES）：DES算法使用了56位的密钥以及附加的8位奇偶校验位，形成的分组大小最大为64位DES算法采用一个迭代的分组密码，实现中使用Feistel技术DES算法描述分组大小:2w=64密钥大小:|K|=56

子密钥:|Ki|=48轮数:h=16对明文作置换IP后开始第1次迭代第16次迭代后，交换左、右32bit数据，再作逆置换IP-1，即得密文FL1R1K1….….….….FL16R16K16L0(32bit)R0(32bit)明文:m(64bit)

IP密文:c(64bit)

IP-1数据加密标准（DES）初始置换IP将64位明文打乱重新排列设m=m1m2…m64，则IP(m)=m58m50m42…m23m15m7IPIP15850423426181026052443628201246254463830221486456484032241665749413325179159514335271911361534537292113563554739312315740848165624643239747155523633138646145422623037545135321612936444135220602835343115119592734242105018582633141949175725轮函数F的设计轮函数F的结构

F(Ri1,Ki):{0,1}32{0,1}48{0,1}32

F

Ki(48)….….LiRi….….Li-1Ri-1Ki(48)Ri-1(32)

E

F(Ri-1,Ki)置换P

S7

S6

S5

S4

S3

S2

S1

S8

扩展变换E扩展变换E:

将32位变为48位，扩展了16位扩展变换E3212345456789891011121312131415161716171819202120212223242524252627282928293031321S-盒Sk:{0,1}6{0,1}4(k=1,2,…,8)输入:b1b2b3b4b5b6,用10进制表示:(i)10=b1b6(0i3),(j)10=b2b3b4b5(0j15)输出:Sk-盒的表中第i行j列位置元素(4位二进制)例:对于S1，输入b=101011,有i=11=3--行,j=0101=5--列,

输出:S1(b)=S1(3,5)=9=1001Sk0123456789101112131415

S1012314413121511831061259070157414213110612119538411481362111512973105015128249

17511314100613S－盒11441312151183106125907015741421311061211953841148136211151297310501512824917511314100613S—盒的输出表示设对应S－盒1的输入序列为：行号：11即3列号：0111即70123

012345689101112131415结果为7即01117置换PP：整数1-32的置换置换P1672021291228171152326518311028241432273919133062211425总结：轮函数F(Ri-1,Ki)运算过程

Ri-1e=E(Ri-1)c=eKis=S(c)P(s)=F(Ri-1,Ki)=P(S(E(Ri-1)Ki))DES子密钥生成算法

由64位密钥K产生16个48位的子密钥:

K1,K2,…,K16.DES子密钥生成算法

LS1

LS1

C1

D1

K1

PC-2….….

LS2

LS2

C2

D2

K2

PC-2

LS16

LS16

C16

D16

K16

PC-2

密钥:K(64bit)

PC-1

C0

D0

(48bit)(48bit)(48bit)(28bit)(28bit)置换选择1:PC-1

64位密钥K的第8,16,24,…,64位共8位是奇偶校验位,其余56位作为密钥用.选择K的第57,49,…位共28位作为密钥段C0;选择K的第63,55,…位共28位作为密钥段D0DES子密钥生成算法PC-157494133251791585042342618102595143352719113605244366355473931231576254463830221466153453729211352820124DES子密钥生成算法循环左移LSi

将28位的密钥段作为Ci,Di循环左移1或2位,左移位数由下表确定.

i12345678910111213141516LSi1122222212222221置换选择2:PC-2

从56位密钥段Ci||Di中选择48位作为子密钥Ki.DES子密钥生成算法PC-2

1417112415328156211023191242681672720132415231374755304051453348444939563453464250362932DES解密算法与DES加密结构相同子密钥使用次序相反:

K16

K15,…,K2,K1输入：密文c输出：明文mf1K0R1L=16K）bit密文（

64IP逆置换IP置换…明文（64bit）0R(32bit)0L1RÅ=),(0Rf1K15L16RÅ=),(15Rf16Kf…f

的扩展变换0R循环左移压缩置换密钥置换fS—盒1Kp—盒0L1RÅ=),(0Rf1K0L(32bit)15R16L=

(2)IDEA国际数据加密算法IDEA（InternationalDataEncryptionAlgorithm）:IDEA是作为迭代的分组密码实现的，使用128位的密钥和8个循环。这比DES提供了更多的安全性，但是在选择用于IDEA的密钥时，应该排除那些称为“弱密钥”的密钥。DES只有四个弱密钥和12个次弱密钥，而IDEA中的弱密钥数相当可观，有251个。但是，如果密钥的总数非常大，达到2128个，那么仍有277个密钥可供选择2.3.4高级加密标准(AES)

1.AES算法的概念

AES算法的输入和输出都是长度为128bit的序列串，序列中每个位的值为0或1。这些序列在算法中称为数据分组(block)，序列包含的位(bit)数也称为分组长度。AES算法使用128bit、192bit或256bit长度的密钥。算法不支持其他的输入、输出长度和密钥长度

1）字节(byte)

AES算法中的基本运算单位是字节(byte)，即作为一个整体的8bit二进制序列。算法的输入数据、输出数据和密钥都以字节为单位，明文、密钥和密文数据串被分割成一系列8个连续比特的分组，并形成字节数组。假设一个8字节的分组b是由字节序列{b7,b6,b5,b4,b3,b2,b1,b0}所组成的，则可将bi看做一个7次多项式b(x)的系数，即b(x)=b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x1+b0

式中，bi∈{0,1}。例如，{01010111}表示成多项式为x6+x4+x2+x+1也可以使用十六进制符号来表示字节值，将每4bit表示成一个符号便于记忆。例如，{01010111}={57}。

2）字节数组输入序列按字节划分，表示形式如下：

3）状态（State）

AES算法的运算都是在一个二维字节数组上完成的，这个数组称为状态。当输入的明文序列转换成字节数组后，进一步将一维的字节数组内容转换为二维排列，就形成了状态矩阵。一个状态矩阵由四行组成，每一行包括Nb个字节，Nb的值等于分组长度除以32。状态矩阵用s表示，每一个字节的位置由行号r(范围是0≤r<4)和列号c(范围是0≤c＜Nb)惟一确定，记为sr,c或s［r,c］。在AES标准中状态矩阵参数Nb=4，即0≤c＜4图2.4

AES加解密状态矩阵运算式中：0≤r＜4；0≤c＜Nb。在加密和解密的完成阶段，状态矩阵采用以下规则转换，结果存储在输出数组out中：其中，0≤r＜4,0≤c＜Nb

4）状态矩阵列数组状态矩阵中每一列的4个字节是一个32位长的字，行号r是这个字中每个字节的索引，因此状态矩阵可以看做32位字(列)长的一维数组，列号c是该数组的列索引。由此上例中的状态可以看做4个字组成的数组，表示如下：

2.有限域基本数学运算

AES算法的基本思想是基于置换和代替变换的演算方法。其中，置换是对数据的重新排列，而代替则是用数据替换另一个。AES算法中的所有字节按照每4位表示成有限域GF（28）中的一个元素AES密码中的运算是按字节（8位）或4字节的字（32位）定义的在AES密码中，一个字节可看作有限域GF(28)中的一个元素，对应于一个系数在GF(2)中的次数小于8的多项式--面向字节的运算GF(28)的元素8bit的字节=8维二元向量

b=b7b6b5b4b3b2b1b0=(b7,b6,b5,b4,b3,b2,b1,b0)次数不超过8的二元多项式

bb(x)=b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x1+b0.例:b=10011011=(1,0,0,1,1,0,1,1)b(x)=x7+x4+x3+x+1.GF(28)的加法:对应位mod2相加例:a=01101111a(x)=x6+x5+x3+x2+x+1,ab=0110111110011011=11110100,

a(x)b(x)=x6+x5+x3++x2+x+1x7+x4+x3+x+1

=x7+

x6+x5+x4+x2.

GF(28)的乘法“”模多项式:m(x)=x8+x4+x3+x+1.两个多项式相乘:将积按m(x)取模乘法逆元:如果a(x)与b(x)满足:a(x)b(x)=1(modm(x))

则称b(x)是a(x)的乘法逆元，记为b(x)=a(x)-1.例:设a(x)=x6+x4+x2+x+1,b(x)=x7+x+1,则

a(x)b(x)=(x6+x4+x2+x+1)(x7+x+1)=x13+x11+x9+x8+x6+x5+x4+x3+1=x7+x6+1(modm(x))又例:用16进制表示字节

(B2)(84)=(11000010)(10000100)

=(x7+x6+x)(x7+x2)=x14+x13+x9+x3=x7+x6+x5+x3+1

(modm(x))=11101001=(D9).（xtime()，乘x）将上面的结果模m(x)求余就得到xb(x)，显然有：考察GF(28)上的多项式x乘以多项式b(x)

x

上述分析说明：xtime()可用字节内左移一位和紧接着的一个与1b（十六进制）的条件比特异或来实现高次乘法可通过重复应用xtime()来实现通过将中间结果相加，任意乘法都可以利用xtime()来实现倍乘函数(x乘)(02)b(x)=xb(x)=xtime(b),

(04)b(x)=x2b(x)=x(xb(x))=x(xtime(b))=xtime(xtime(b))，

(08)b(x)=x(x2b(x))=xtime(xtime(xtime(b))).例:计算571313=00010011=x4+x+1,x57=xtime(57)=AE,

x457=xtime(xtime(xtime(xtime(57))))=xtime(xtime(xtime(AE)))=xtime(xtime(47))=xtime(8E)=07.5713=57x57x457=57AE07=FE系数在GF(28)域的特殊多项式--面向4个字节的运算设变换多项式为：输入多项式为：它们的乘积是次数不超过6的多项式

c(x)=c6x6+c5x5+c4x4+c3x3+c2x2+c1x+c0c0=a0

b0

c4=a3

b1

a2

b2

a1

b3

c1=a1

b0

a0

b1

c5=a3

b2

a2

b3

c2=a2

b0

a1

b1

a0

b2

c6=a3

b3c3=a3

b0

a2

b1

a1

b2

a0

b3取M(x)=x4

1令：两个四字节字之间的乘法变换可表示为：d0=b0a0+b1a3+b2a2+b3a1d1=b0a1+b1a0+b2a3+b3a2d2=b0a2+b1a1+b2a0+b3a3d3=b0a3+b1a2+b2a1+b3a0关于乘法的实现（xtime()，x乘法）将上面的结果模M(x)求余就得到xb(x)，显然有考察系数在GF(28)上的多项式x乘以多项式b(x)对于该变换，当输入为：(b3,b2,b1,b0)时输出为：(b2,b1,b0,

b3)因此，用x或x的方幂乘GF(28)上的多项式等价于一个字中字节的左循环移位。注：x对应一个4字节字，（00，00，01，00）AES加密算法AES加密算法结构AES的流程图加密算法结构将待加密的明文分组以字节为单位填充状态矩阵（4×Nb字节矩阵），做初始密钥加变换进行Nr轮迭代，每轮包含四个变换：（1）字节代替变换；（2）行移位变换；（3）列混叠变换；（4）轮密钥加变换（按位异或）注：最后一圈（第Nr圈）省略列混叠变换第Nr圈的输出即为密文（输出状态）AES加密算法数据长度可变明文、密文分组长度:lm=128,192,256密钥长度:

lk=128,192,256加密过程的中间结果称为“状态(state)”将每次变换的状态以字节为单位表示成一个4行Nb列的矩阵.

Nb=lm/32=4,6,8.lm=192,Nb=6时的状态表示s00s01s02s03s04s05s10s11s12s13s14s15s20s21s22s23s24s25s30s31s32s33s34s35密钥k的表示将密钥k以字节为单位表示成一个4行Nk列的矩阵.Nk=lk/32=4,6,8.lk=128,Nk=4时的密钥表示k00k01k02k03k10k11k12k13k20k21k22k23k30k31k32k33迭代轮数NrNrNb=4Nb=6Nb=8Nk=4101214Nk=6121214Nk=8141414AES的轮函数字节代换:ByteSub对状态的每个字节独立进行代换，是字节的非线性变换，也称为S盒变换。设

ByteSub(aij)=bija00a01a02a03a04a05a10a11a12a13a14a15a20a21a22a23a24a25a30a31a32a33a34a35b00b01b02b03b04b05b10b11b12b13b14b15b20b21b22b23b24b25b30b31b32b33b34b35aijbijByteSubAES的轮函数字节代换：ByteSub(aij)=bij.第1步:求乘法逆元(GF(28)中的乘法)，‘00’的逆元为自己‘00’aijaij-1第2步:

对aij-1作仿射变换

字节代替变换实际上是一个8进8出的S盒。设xy(16进制表示)为状态中的一个字节，则代替表(S盒)中第x行第y列的字节就是对应的字节代替变换的结果AESS-盒算法设x=00001001转换为16进制09行列查询S盒AES算法的“S－盒”

16BB54B00F2D99416842E6BF0D89A18CFDF2855CEE9871E9B948ED9691198F8E1E9E1DC186B95735610EF6034866B53E70D8A8BBD481F74DDE8C6B4A61C2E2578BAC08AE7A65EAF4566CA94ED58D6D37C8E7B79E4959162ACD3C25C2406490A3A32E0ADB0B5EDE14B8EE4688902A22DC4F8160973195D643D7EA7C41744975FEC130CCD8D2F3FF1021DAB6BCF5389D928F40A3517A89F3C507F02F94585334D43FBAAEFD06CF584C4A39BECB6A5BB1FC20ED00D1535842FE329B3D63B52A05A6E1B1A2C8309475B227EBE28012079A059618C323C70431531D871F1E5A534CCF73F362693FDB72C072A49CAFA2D4ADF04759FA7DC982CA176ABD7FE2B670130C56F6BF27B777C630FEDCBA9876543210y返回AES的轮函数行移位:ShiftRow将状态矩阵的每行进行循环左移:

第0行不移;第i行循环左移Ci

个字节(i=1,2,3)a00a01a02a03a04a05a10a11a12a13a14a15a20a21a22a23a24a25a30a31a32a33a34a35Nb

C1C2C3412361238134a00a01a02a03a04a05a11a12a13a14a15a10a22a23a24a25a20a21a33a34a35a30a31a31AES的轮函数列混合:MixColumn将状态矩阵每一列的4个字节表示成一个3次多项式，再与多项式c(x)相乘

c(x)=(03)x3+(01)x2+(01)x+(02)a00a01a02a03a04a05a10a11a12a13a14a15a20a21a22a23a24a25a30a31a32a33a34a35例如:对于第2列,a(x)=a31x3+a21x2+a11x+a01,

则MixColumn(a(x))=a(x)c(x)(modM(x))=b31x3+b21x2+b11x+b01b00b01b02b03b04b05b10b11b12b13b14b15b20b21b22b23b24b25b30b31b32b33b34b35依次按列进行处理，每列是一个四字节的字=AES的轮函数轮密钥加:AddRoundKey(State,RoundKey)将状态矩阵与子密钥矩阵的对应字节进行逐比特异或

AddRoundKey(aij,kij)=aij

kij例：a21

k21=b21a00a01a02a03a04a05a10a11a12a13a14a15a20a21a22a23a24a25a30a31

a32a33a34a35b00b01b02b03b04b05b10b11b12b13b14b15b20b21b22b23b24b25b30b31b32b33b34b35k00k01k02k03k04k05k10k11k12k13k14k15k20k21k22k23k24k25k30k31

k32k33k34k35AES的轮密钥生成轮密钥生成算法=密钥扩展+轮密钥选取密钥扩展:将密钥k扩展为扩展密钥W[Nb(Nr+1)]W是以4个字节为元素的一维数组,共有Nb(Nr+1)个元素W的前Nk个元素正好是密钥k,其他元素由扩展算法求出kW[1]W[Nk]W[Nk+1]W[Nb(Nr

+1)]

4.AES解密

AES的解密算法与加密算法不同，是加密过程的逆运算。解密算法中各个变换的操作顺序与加密算法不同，但是加密和解密算法中的密钥编排形式是一致的。解密算法中使用的变换依次为逆列混叠(InvMixColumns)变换、逆行位移变换(InvShiftRows)、逆字节替换变换(InvSubBytes)和轮密钥加变换(AddRoundKey)，变换作用在密文序列对应的状态矩阵上AES解密过程2.4公钥（非对称）密码体制2.4.1公钥密码体制的基本概念公钥体制下，一个用户可以将自己设计的加密公钥和加密算法对外公布，而只保留解密用的私钥。任何人都可以获取这个用户的加密公钥和加密算法，并向该用户发送加密过的信息，该用户接收后可以使用私钥还原消息。在这个公钥加解密的过程中，会涉及到公私密钥对、数字证书以及电子签证机关等主要内容

1.密钥对在基于公钥体系的安全加密系统中，密钥生成过程每次都产生一个公钥和一个私钥，形成加密和解密的密钥对。在实际应用中，私钥由用户私人保存，而公钥则通过某种手段对外公布。公钥体系的基础问题是公钥的分发与管理，这是电子商务等业务系统能够广泛应用的基础

2.数字证书公开密钥体系需要在开放环境下使用，公钥加密体系采取将公钥和公钥的主人名字联系在一起的方法，再请一个有信誉的公正权威机构对每个公钥和所有者身份进行确认，确认后的公钥信息加上这个权威机构的签名，就形成了数字证书，也称为证书。证书就是用户在网上的电子个人身份证，在电子商务中的作用同日常生活中使用的个人身份证作用一样

3.电子签证机关电子签证机关（即CA）是负责颁发数字证书的权威机构。CA自身拥有密钥对，可以使用私钥完成对其他证书的数字签名，同时也拥有一个对外开放的证书（内含公钥）。网上的公众用户通过验证CA的数字签名建立信任，任何人都可以得到CA的证书（含公钥），用以验证它所签发的其他证书通常意义上的密码学(Cryptography)技术主要用来保护信息传递的机密性。但是在电子交易环境下，对信息发送与接收人的真实身份的验证、发送及接受信息的事后不可抵赖性以及保障数据的完整性，是另一个极为重要的问题公开密钥密码体制不仅可解决信息的保密性问题，还可以完成对信息传递双方真实身份的验证和数据完整性验证RSA系统是公钥密码体系中应用最为广泛、影响力最大的一种公钥加密体制具有以下优点密钥分配相对简单，不需要复杂的流程密钥的保存量少，且私钥和公钥分别存储可以实现互不相识的人之间进行私人通信时的保密性要求可以完成通信双方的数字签名和数字身份鉴别2.4.2公钥密码体制的原理公钥密码体系中由于公钥与私钥之间存在依存关系，因此，信息使用公钥加密后，只有私钥拥有者本人才能解密该信息，任何未授权用户甚至信息的发送者都无法将此信息解密。近代公钥密码系统的研究主要基于难解的可计算问题，该方法保证了整个体系和算法的安全性。常用的难解可计算问题包括：大数分解问题计算有限域的离散对数问题平方剩余问题椭圆曲线的对数问题等2.4.3RSA算法目前最流行的公开密钥算法是1977年由RonaldL.Rivest、AdiShamir和LeonardM.Adleman共同提出的，算法名字的三个字母分别取三名数学家名字的首字母。RSA算法的理论基础是数论中的欧拉定理，该算法的安全性完全依赖于大数因子分解的困难些欧拉定理欧拉定理若整数a和m互素，则式中，φ(m)为比m小，是与m互素的正整数个数求最大公因子Euclid算法是基于下面一个基本结论：对任意非负整数a和正整数b，有gcd(a,b)=gcd(b,amodb)如：gcd(55,22)=gcd(22,55mod22)=gcd(22,11)=gcd(11,0)=11在求两个数的最大公因子时，可重复使用以上结论例如：gcd(18,12)=gcd(12,6)=gcd(6,0)=6， gcd(11,10)=gcd(10,1)=gcd(1,0)=1求gcd(1970,1066)。1970=1×1066+904, gcd(1066,904)1066=1×904+162, gcd(904,162)904=5×162+94, gcd(162,94)162=1×94+68, gcd(94,68)94=1×68+26, gcd(68,26)68=2×26+16, gcd(26,16)26=1×16+10, gcd(16,10)16=1×10+6, gcd(10,6)10=1×6+4, gcd(6,4)6=1×4+2, gcd(4,2)4=2×2+0, gcd(2,0)因此gcd(1970,1066)=2

大整数分解若已知两个大素数p、q，求n=p×q仅需一次乘法，但已知n求p、q则是几千年来数论专家的一道难题。已知的各种算法有：试除法、二次筛、数域筛、椭圆曲线。其中RSA问题是FAC问题的特例。n是两个素数p、q之积，给定n以后求p、q的问题称为RSA问题。求n=p×q分解问题有以下几种形式：分解整数n为p、q；给定整数M、C，求d使得Cd≡Mmodn；给定整数k、C，求M使得Mk≡Cmodn；给定整数x、C，决定是否存在y使得x≡y2modn（二次剩余问题）则A收到密文c以后，用只有自己才知道的解密密钥ka′对c进行解密得公钥密码体制的原理加解密模型认证模型对称密钥和公钥密钥

1.RSA密钥的产生

RSA密钥的产生过程如下：选择两个大素数p、q，选择的素数要保密计算n=pq(p、q分别为两个互异的大素数，n的长度大于512bit，这主要是因为RSA算法的安全性依赖于大数因子分解问题)。欧拉函数为φ(n)=(p-1)(q-1)随机选择加密密钥e，要求e和φ(n)互质利用Euclid算法计算解密密钥d，应满足d×e≡1modφ(n)，其中n和d也要互素。数e和n是公钥，d是私钥。两个素数p、q不再需要，应该丢弃，不要让任何人知道

2.RSA加密加密信息（二进制表示）时，首先把分成等长数据块m1,m2,m3,...,mi,块长s，其中2s≤n,s要尽可能的大对应的密文是：3.RSA解密 对加密消息进行解密计算时，计算例：RSA加解密设p=11，q＝23，则n＝pq＝11×23＝253φ(n)＝(p－1)(q－1)＝10×22＝220

选取e＝3，显然gcd(e,φ(n))＝gcd(3,220)＝1

计算d＝e-1modφ(n)–220＝22×5×11–φ(220)＝220×1/2×4/5×10/11＝80–d＝3-1mod220＝380-1mod220＝147

明文空间Zn

={0,1,2,…,251,252}

公钥(3,253)，私钥(147,253)

加密：对于明文m＝165，密文c＝1653mod253＝110

解密：对于密文c＝110，明文m＝110147mod