（计算机系统结构专业论文）蓝光播放器系统中aacs保护机制的研究与实现.pdf

浙江大学硕士学位论文摘要 摘要 计算机科学不断发展，技术不断进步，带来了一个严峻的问题，那就是破解 技术也进一步提高，对数字媒体内容的盗版变得日益猖獗，传统的保护方法已经 不能起到保护的作用。随着下一代高清数字视频格式标准的确定，亟需一种安全 的保护机制来保护数字内容版权的安全。高级内容访问系统从c s 正是这样一种 保护机制，它采用高强度的加密方法，更有效的密钥管理，形成一个内容保护链 从内容提供、内容的录制和复制、光盘制作、内容解密播放各个环节全方面对内 容进行保护。 本文在密码学的基础上，深入分析研究了高级内容访问系统a a c s 的整个体 系，对该体系所采用的技术做了研究并完成了一些设计和实现工作。文章由六个 部分组成。第一部分对当前应用背景及从整体上对从c s 体系做了介绍。第二部 分详细分析并实现了基于高级加密算法a e s 的加解密功能。第三部分详细分析并 实现了基于椭圆曲线数字签名的功能。第四部分分析了a a c s 中关键的技术一可更 新的密钥管理机制，从子集差分技术上对它进行了研究。第五部分主要研究了驱 动器和主机之间数据传输的安全性，主要通过对驱动器证书和主机证书数字签名 的认证来实现。最后一部分则是对全文的总结，并对将来的发展做了展望。 关键词：高级内容访问系统，高级加密标准，椭圆曲线，子集差分，蓝光 浙江大学硕士学位论文 a b s t r a c t a st h ed e v e l o p m e n to fc o m p u t e rs c i e n c e , t e c h n o l o g ya d v a n c e s ，h a sb r o u g h t a b o u tas e r i o u sp r o b l e m ，w h i c hi sc r a c kt e c h n o l o g yi sf u r t h e ri m p r o v e d ，t h ep i r a c yo f d i 酉t a lm e d i ac o n t e n th a sb e c o m ei n c r e a s i n g l yr a m p a n t , t h et r a d i t i o n a lm e t h o do f p r o t e c t i o nh a sn ol o n g e rp l a y e dt h er o l eo fp r o t e c t i o n w i t ht h en e x tg e n e r a t i o no f h i g h - d e f i n i t i o nd i 百t a lv i d e of o r m a ts t a n d a r ds e t t i n g , am o r os e c u r i t yp r o t e c t i o n m e c h a n i s mt op r o t e c tt h ec o p y r i g h to fd i g i t a lc o n t e n ts e c u r i t yi sm u c h - n e e d e d a d v a n c e da c c e s sc o n t e n ts y s t e m ( a a c s ) i ss u c hap r o t e c t i o nm e c h a n i s m , w h i c h u s i n gh i g h - s t r e n g t he n c r y p t i o n , m o r ee f f e c t i v ek e ym a n a g e m e n t , f o r m i n gac h a i nt o p r o t e c tt h ew h o l ea r e ao fc o n t e n tf r o mc o n t e n tp r o v i d e r s ，c o n t e n to ft h er e c o r d i n ga n d r e p r o d u c t i o n , o p t i c a l ( 1 i s kp r o d u c t i o n ，c o n t e n td e c r y p t i o na n dp l a y b a s e do nc r y p t o g r a p h y , t h i sp a p e rd e e p l ya n a l y s i sa n dr e s e a r c ht h ee n t i r es y s t e m o f a a c s d or e s e a r c h ，d e s i g na n di m p l e m e n t a t i o no ne a c ht e c h n o l o g yt h es y s t e mu s e d t op r e t e c tt h ec o n t e n t t h ep a p e ri sc o m p o s e do fs i xp a r t s t h ef i r s tp a r tp r e s e n t sa i n t r o d u c t i o nt ot h ec u r r e n tb a c k g r o u n da n dt h ew h o l ea a c ss y s t e m t h es e c o n dp a r t a n a l y s i st h ed e t a i lo fa d v a n c e de n c r y p t i o ns t a n d a r d ( a e s ) ，t h e ni m p l e m e n tt h e c n c r y p t i o na n dd e c r y p t i o nf u n c t i o nb a s e do na e sa l g o r i t h m t h et h i r dp a r ta n a l y s i s t h ed e t a i lo fe l l i p t i cc u r v ed i g i t a ls i g n a t u r ea n dt h e ni m p l e m e n tt h ed i g i t a ls i g n a t u r e f u n c t i o n t h ef o u r t hp a r ta n a l y s i st h em o s ti m p o r t a n tt e c h n o l o g yi na a c s t h e r e n e w a b i l i t yo fk e ym a n a g e m e n t , w h i c hi sb a s e do ns u b s e t - d i f f e r e n c em e t h o d t h e f i f t hp a r ta n a l y s i st h es e c u r i t yo fd a t at r a n s m i s s i o nb e t w e e nd e i v ea n dp ch o s t ，t h e n p r o p o s e aa l g o r i t h mt oa c h i e v et h i sp u r p o s eb yv e r i f yt h es i g n a t u r eo fd r i v ec e r t i f i c a t e a n dh o s tc e r t i f i c a t e t h el a s tp a r ti sas u m m a r yo ft h ep a p e ra n dt h ee x p e c t a t i o no ft h e f u t u r ew o r k k e y w o r d s ：a a c s ，a e s ，e c c ，s u b s e t d i f f e r e n c e ，b l u - r a y 浙江大学硕士学位论文 图目录 图目录 图1 1a a c s 的保护架构4 图1 2a a c s 加密和解密过程6 图2 1s t a t e 数组的输入和输出1 4 图2 2a e s 加解密流程1 6 图2 3 加密伪码描述1 7 图2 4 对s t a t e 中的字节应用s 盒l8 图2 5 行位移变换s h i f t r o w s 18 图2 6m i x c o l u m n s 0 对s t a t e 的列操作19 图2 7s t a t e 每列按位与轮密钥异或1 9 图2 8 密钥扩展伪码描述2 0 图2 9 解密伪码描述2 1 图2 1o 行位移变换逆运算i n v s h i r r o w s 2 2 图2 1 1 等价解密过程伪码描述。2 3 图2 1 2 基于a e s 的单向函数2 5 图2 1 3 基于a e s 的哈希函数2 6 图3 - 1y 2 = 吖3 4 菇+ o 6 7 2 9 图3 - 2p + q = r 3 0 图3 - 3 尸+ ( 一p ) = 0 31 图3 4 p + p = 2 p = r ( y p o ) 。3 1 图3 5p + p = 2 p = r ( y = 0 ) 一3 2 图3 6y 2 = x 3 + 工在只，点的分布3 4 图4 1 媒体密钥块( m k b ) 处理4 l 图4 2s d 方法中的子集墨4 4 图4 3 划分查找算法4 6 图4 4 设备密钥生成器r ( a e s g 3 1 4 6 图5 1 读取卷标示符5 4 图5 2 读取只读光盘标示符：。5 4 图5 3 读取媒体标示符5 5 图5 4 保护区数据的生成、传输和写入5 5 图5 5 读保护区数据5 6 图5 6 驱动器认证算法5 9 i i i 浙江大学硕士学位论文 表目录 表目录 表2 1m 、m 和，关系表1 5 表2 2a e s 和d e s 加解密时间比较2 6 表2 3a e s 和d e s 加解密效率比较2 7 表3 - le c c 、l i s a 和d s a 安全性分析3 9 表3 2e c c 和r s a 速度比较3 9 表5 1 驱动器证书数据结构5 6 表5 2 主机证书的数据结构。5 7 i v 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得迸江盘堂或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 一徘修为 签字日期：刀谚年月日 学位论文版权使用授权书 本学位论文作者完全了解迸姿盘堂有权保留并向国家有关部门或机构 送交本论文的复印件和磁盘，允许论文被查阅和借阅。本人授权逝鎏盘堂可 以将学位论文的全部或部分内容编入有关数据库进行检索和传播，可以采用影 印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书 靴做储獬：砂仍 签字嗍刀口庐多月乡日 浙江大学硕士学位论文 第1 章绪论 1 1 课题背景 第l 章绪论 随着生活水平的日益提高，数字视频图象的内容以及品质已经成为了大家最 关心的方面，普通的光盘数字视频格式不论在清晰度以及容量上都已经逐渐不能 满足人们的要求，人们对高清数字视频的需求越来越强烈。目前较通用的d v d 技术，虽然从5 1 ( 包含a c - 3 以及d t s 及他们的后续技术) 声音方面还是图象 方面都相当不错，但随着大屏幕电视和显示器的逐渐普及，d v d 在画面分辨率上 的缺陷还是逐渐显露了出来，而且人们对于大屏幕拥有更高清晰度的画面总是有 着相当大的期待。 随着计算机及多媒体技术的发展，诞生了蓝光( b l u - r a y ) 或称蓝光盘( b l u r a y d i s c ，缩写为b d ) 和h dd v d 两种高清数字视频格式。蓝光利用波长较短( 4 0 5 n m ) 的蓝色激光读取和写入数据，并因此而得名。传统d v d 需要光头发出红色激光 ( 波长为6 5 0 n m ) 来读取或写入数据，由于波长越短的激光，能够在单位面积上 记录或读取更多的信息。因此，蓝光极大地提高了光盘的存储容量，它的光盘结 构为1 1 m m 盘片+ o 1 m m 保护层，容量单面单层为2 5 g ，单面双层课达5 0 g ，对 于光存储产品来说，蓝光提供了一个跳跃式发展的机会。h dd v d 也采用了4 0 5 n m 蓝色激光，但它更注重与d v d 标准的兼容性。t o s h i b a 利用蓝光的技术对原来 的d v d 加以改进，达到与b d 一样的影像效果。h dd v d 的容量要小于蓝光： 单面单层1 5 g b ，单面双层3 0 g b 。最近几年，这两种高清格式一直在为谁能成为 下一代高清d v d 的标准格式而斗争。而随着在2 0 0 8 年c e s 展会上华纳电影公 司宣布不再支持h dd v d 所带来的影响，蓝光终于获得了绝大部分内容发行商的 支持，而h d 的市场份额进一步萎缩。最终东芝于2 月1 9 日正式宣布撤出h dd v d 业务，历时数年的下一代高清d v d 标准之争尘埃落定，蓝光光盘成为了下一代 高清数字视频的标准载体。 浙江大学硕士学位论文第l 章绪论 蓝光战胜h dd v d ，赢得下一代高清影碟格式之争后，市场马上做出了反应， 各大硬件厂商纷纷加速推出蓝光产品，刮起了一阵蓝光旋风。明基、飞利浦、索 尼、先锋、华硕等厂商纷纷推出新款蓝光光驱。华硕、宏基与惠普等p c 厂商也 表态支持，将推出采用蓝光光驱的p c 产品。不仅仅是硬件，相应的软件厂商也 纷纷推出了他们的相关产品，特别是各大多媒体厂商，都已经发布了各自的蓝光 播放器。在游戏领域，蓝光也将会有相当大的应用。所以随着未来蓝光的普及， 由于成本的降低及竞争的激烈导致产品价格的下降，片源的增多，蓝光的应用将 会越来越广，市场前景一片光明。 目前，蓝光光盘最大的应用还是在高清电影，然而它面临着一个最大的问题， 就是盗版问题。总所周知，在目前广泛应用的d v d 光盘( 实际是影片本身) 的盗版 问题非常严重，在它背后存在着非常严重而且“完善”的知识侵权体系。因为计 算机技术和逆向工程技术的快速发展，导致以前的许多版权保护技术已经不能够 抵挡黑客和破解组织的恶意破解，曾经在设计上非常严密的d v d 内容保护技术 c s s 因为密钥流失而遭到破解，其后的c p p m 和c p r m 也相继被破解【l 】，使得 d v d 的版权保护措施形同虚设。因此使用光盘作为主要发行手段的内容所有者， 特别是电影、音乐和游戏公司都还面临着严峻的盗版现实，他们亟需一种相对安 全的保护技术，来防止再次遭遇d v d 那样的损失。 为了抵制非法拷贝和大规模盗版，充分内容保护发行商的最大利益，蓝光光 盘协会( b d a ) 在版权保护方面采用了先进的保护技术，它使用了一种全面的内容 管理系统。这种蓝光内容管理系统包括三大主要部分：a a c s ( a d v a n c e da c c e s s c o n t e n ts y s t 0 1 n ，高级内容访问系统) ，面向内容保护可更新能力的蓝光特定增强 功能b d + 技术，以及用于抵制预先录制的媒体未授权拷贝的批量盗版生产或批量 复制及销售的r o mm a r k 技术。而a a c s 技术正是这三种技术里最主要的保护机 制。 1 2 高级内容访问系统a a c s 通过技术手段实现对数字内容的安全性保护一般需要满足以下四个方面的 2 浙江大学硕士学位论文第l 苹绪论 要求【2 】。 1 机密性：确保内容仅能被合法用户使用。 2 完整性：内容不可随意篡改且可分辨。 3 可控性：访问者对内容只能进行授权所允许的行为。 4 内容的安全传播：内容在交易过程中不能被中途窃取、非法盗版。 高级内容访问系统a a c s ( a d v a n c c da c c e s sc o n t e n ts y s t e m ) 3 1 1 4 5 】是一种基于 加密、认证的数字内容保护技术，由它的授权组织a a c sl a 所开发，a a c sl a 于2 0 0 4 年7 月由内容供应商美国沃尔特迪斯尼、华纳兄弟娱乐、计算机相关企 业美国i b m 、英特尔、微软、a v 产品厂商松下电器产业、索尼和东芝8 家公司 共同成立。它旨在建立强健的、可共同操作的环境，用于管理存储下一代录制和 预录制介质上的内容。它不仅可用在b d 和h dd v d 等蓝光光盘领域，而且还会 用于p c 和互联网、家用网络和数字电视等领域【6 1 。 相比以前的内容保护系统，a a c s 改进的地方在于其不仅仅是一种加密的手 段，而是形成一个内容的保护链条，作为整体的体系来对具有版权的内容加以保 护。一个内容保护链条包含内容提供、内容的录制和复制、光盘制作、内容解密 播放4 个环节，每个环节都有相应的一整套保护措施来应对破解【1 1 。a a c s 的保 护架构如图1 1 所示【7 1 ： 3 浙江大学硕l 学位论文 第1 章绪论 内容使用规则 凰 改备密钥 图1 1a a c s 的保护架构 在内容提供的环节，内容拥有者或内容提供商( c o n t e n to w n e r ) 把内容分组成 一个或多个标题( t i t l e ) ，并附上使用规则( c o n t e n tu s a g er u l e s ) ，洋细描述数宁内 容的使用方法和使用范围，然后将他们分发到内容的录制和复制流程中，提供给 获得许可的复制设备( l i c e n s e dr e p l i c a t o r ) 。 侄录制和复制流程中，a a c sl a 组织提供给获得许1 1 j 的发行公司( l i c e n s i n g e n t i t y ) 媒体密钥块m k b ( m e d i ak e yb l o c k ) 牙h 序列密钥块s k b ( s e q u e n c ek e y b l o c k ) ，提供给授权的播放机设备密钥k a ( d e v i ck e y ) ，利用设备密钥k d 和媒体 密钥块m k b 计算出媒体密钥k 。( m e d i ak e y ) ，然后将k m 、u s a g er u l e s 和m k b 一一起灌注到媒体介质中。 在光盘制作的流程中，按照是否可重新刻录将光盘分为预录制媒体和呵录制 4 浙江大学硕士学位论文第l 章绪论 媒体两类，分别对应不可录制光盘和可重新录制的光盘。在预录制光盘中，定义 i d m ( m e d i ai d ，媒体标识符) 并绑定随机数。在可录制光盘中定义i d a ( v o l u m e i d ， 卷标识符) 和媒体序列号m s n ( m e d i as e r i a ln u m b e r ) 。这种针对不同类型的光盘定 义不同数据的做法是有其针对性的。预录制发行的光盘，防范盗版的主要途径是 保证内容不会被通过“点对点 的克隆软件全盘复制，保证光盘上的i d m 处在保 护区域中，不会被非法读取和非法使用，就达到了有效保护内容的目的。而对于 可录光盘不仅要完成这些，还要实现限制刻录次数等其他的一些功能，所以两类 介质定义的数据不完全相同。 在内容播放阶段，凡是符合a a c sl a 组织要求的播放机和播放软件( u c e n s e d p l a y e r ，授权播放机) 都会拥有不同的设备i d ( s e to f d e v i c ek e y s ) 和m a c 地址，播 放设备根据这2 个数据，对光盘上携带的经过加密变换的m k b ，k 恤等数值作反 向解密，得到加密内容的t i t l e 值和内容的使用规则后便可解密，并且根据使用规 则实现对内容数据的播放。 整个a a c s 的加密思想和其他领域中使用的一些加密方法是相似的，如数字 电视中条件接入的授权方法，两者有很多相同的地方。都是使用密钥对数据做加 密处理，然后把密钥传送给具有权限的用户，同时保证非法用户得不到解密的密 钥。 图1 2 是a a c s 的具体加密和解密的程序框图，基于预录制媒体，其中完整 地包含了各个环节：复制设备( r e p l i c a t o r ) 、预录制媒体( p r e - r e c o r d e d ) 和播放设备 ( p l a y b a c kd e v i c e ) 。 5 浙江大学硕士学位论文第l 章绪论 图1 2 a a c s 加密和解密过程 图1 2 包括三部分：合法的复制者( r e p l i c a t o r ) 、复制光盘上记录的媒体信息 ( p r e - r e c o r d e dm e d i a ) 以g t 播放设备( p l a y b a c kd e v i c e ) ，三者分别对应a a c s 加解 密过程的三个不同阶段。 1 第一阶段主要是加密及数字签名，包括生成媒体密钥块m k b ：生成密钥 转换数据k c d ( k e yc o n v e r s i o nd a t a ) ，k c d 的数据长度为1 2 8 - b i t ；分配序列密钥 块s k b ( 由a a c s 组织分配) ；生成标题密钥k ( t i u ek e y ) ，数据长度为1 2 8 - b i t ； 用a e s 算法使用磁密钥加密内容数据；根据使用规则生成m a c ；对内容数据 做数字签名，产生内容证书c c ( c o n t e n tc e r t i f i c a t e ) 。内容证书包含证书类型、内 容提供商i d 、内容序列号和复制器的i d 号等，是保证内容完整性的重要数据， a a c s 也通过验证这个数字证书来实现对复制操作的管理；转移数据是将加密后 6 浙江大学硕士学位论文第l 章绪论 的内容数据以及其他数据转移到光盘的规定区域。 2 经过第一阶段的加密之后，就进入了第二阶段。第二阶段主要是对光盘 进行批量生产的过程，将l ( m 、u s a g er u l e s 和m k b 等一起灌注到光盘中。 3 第三阶段是在播放设备端执行解码过程，也就是a a c s 中最为关键的第 三阶段，这部分的验证工作又可分为三个步骤【4 1 ： 1 ) 首先，光盘上的m k b 数据块会要求核实播放设备持有的d e v i c ek e y s ， 这些密钥是事先固化在播放设备中的；核实无误后，将该设备的序列密 钥s e q u e n c ek e y s 与m k b 进行混合处理生成新的m k b 。如果这一过程 失败，例如说光盘上m k b 发现设备的d e v i c ek e y s 无效，也会生成新的 m k b ，但是这个m k b 的内容已经无法被再次识别，验证将会失败。 2 ) 在经过第一步m k b 验证之后，k c d 将通过a e s g 算法来转换上一步得 到的m k b ，之后与原光盘的s k b 模块一起进入s k b 验证阶段。在这个 过程中，s k b 验证程序会生成一个变量d v ，这个变量用来计算媒体密钥 l ( m ，计算之后得到的k m 会与第一步得到的k m 值进行对比。如果二者不 一致，则播放设备为非法设备，产生一个新的s k b 模块，里面可能包含 有危险的破坏性数据，可导致原有的s k b 被破坏。 3 ) 在顺利经过上面两步验证过程之后，播放设备会读取光盘上的卷标识符 i d v 和标题密钥k ，开始准备下一步的解密工作。然后是第三步验证工 作通常原始内容提供商可以决定光盘的使用方法u s a g er u l e s ，这些信 息被一起装进了原始光盘中；在开始播放光盘时，这些u s a g er u l e s 需要 与a a c sl a 的公共根密钥( r o o tp u b l i ck e y ) 进行最后一次核实，符合 u s a g er u l e s 的内容才会被继续播放出来；否则仍然无法得到想要的内容。 7 浙江大学硕士学位论文第1 章绪论 1 3 论文总体结构 论文的主体分成一下几章进行； 第一章绪论，主要介绍问题的背景和我们的研究工作；第二章研究并实现了 a a c s 所采用的加密技术a e s ；第三章研究并实现了基于e c c 算法的数字签名； 第四章研究了a a c s 的基于子集差分思想的密钥管理机制；第五章介绍了基于驱 动器和主机之间数据传输的认证；第六章对全文做出总结，对将来的研究工作做 了展望。 8 浙江大学硕士学位论文第2 章基于a e s 算法的加解密 2 1 背景 第2 章基于a e s 算法的加解密 a e s ( t h e a d v a n c e de n c r y p t i o ns t a n d a r d ，高级加密标准p 是美国国家标准与技 术研究所( n i s d 筹划的。旨在取代旧的数据加密标准( d e s ) 和三重d e s 而成为一 个美国联邦信息处理标准( f i p s ) ，以保护2 l 世纪敏感政府信息。1 9 9 7 年1 月n i s t 发布公告征集a e s 算法，要求a e s 是一个非保密的、公开披露加密算法的、全 球免费使用的分组密码，算法必须采用对称密钥密码实现，最少应支持1 2 8 - b i t 分组和1 2 8 - b i t ，1 9 2 - b i t 和2 5 6 - b i t 密钥。1 9 9 8 年8 月。n i s t 在美国加州v e n t u r e 召开第一次a e s 候选算法会议( a e s l ) 。会议公布了所有被接受的候选草案。其间， 国际密码学团体被邀请对候选草案进行评议。1 9 9 9 年3 月，在意大利的罗马【9 】召 开了第二次a e s 候选算法会议( a e s 2 ) 。公开了对候选草案的讨论结果。参考a e s 2 的讨论结果，n i s t 从1 5 个候选算法中选出了5 个算法：m a r s ，r c 6 ，r i j n d a e l ， s e r p e n t 和t w o f i s h ，作为进一步讨论的主要对象。2 0 0 0 年4 月，在纽约召开了第 三次a e s 候选算法会议( a e s 3 ) ，对剩下的5 个候选算法作进一步的分析和讨论。 2 0 0 0 年l o 月2 日，n i s t 宣布r i j n d 础算法【1 0 1 1 1 】当选a e s ，成为新一代的加密标 准。 当选的a e s 算法是由比利时的j o a nd a y h e n 和v i n c e n tr i j m e n 提交的、由 j o a n d a o n c n 设计的名为r i j n d a e l 的密码算法。该算法是迭代分组密码算法，其分 组长度和密钥长度都可改变，该箅法的扩充形式允许分组长度和密钥长度3 2 - b i t 的步长，从1 2 8 - b i t 到2 5 6 - b i t 范围内进行特定的变化。 2 2 数学原理 a e s 算法使用了基于有限域g f ( 2 3 ) 中的加法和乘法，可以用多项式来表示域 中的元素。运算的基本单位是字节和4 字节字。由6 7 6 6 6 5 6 4 6 3 砬岛6 0 构成的字节可以 9 浙江大学硕士学位论文 第2 章基于a e s 算法的加解密 用g f ( 2 ) 上的多项式表示为：6 7 x 7 + b 6 x 6 + 岛矿+ b 4 x 4 + 岛，+ b 2 x 2 + b , x + b o 。有限域 及其上操作的定义如下文所示。 2 2 1 有限域 在了解有限域之前必须了解群的概念【1 2 1 。 群的定义如下： 给定一集合g = 口，6 ) 和该集合上的运算奎，满足下列四个条件的代数系统 称为群： 1 ) 封闭性：若a ，b g ，则存在c g ，使a * b - c 2 ) 结合律成立：口，b ，c g ，恒有0 6 ) c - a ( 6 c ) 3 ) 存在单位元素p ：即存在e g ，对 c a g ，恒有a 母p = e * a = a 4 ) 存在逆元素：对于 c a g ，恒有b g ，使a * b = 6 口= e ，元素b 称为a 的逆元素，用a 。1 表示，即b = a 。 若对比，b g ，有a 幸6 = 6 掌口则称 为阿贝尔群( 交换群) 。a * b 可简记 为口6 域的定义： ，是至少含有两个元素的集合，对f 定义了两种运算“+ 和“事 ，并且满 足一下三个条件的代数系统 称为域。 1 ) f 的元素关于“+ 构成阿贝尔群，设其单位元为0 2 ) ， 0 ) 关于运算“构成阿贝尔群 3 ) 对于a , b ，c f ，分配律成立。即 ( 口+ 6 ) 奎c = a 毒c + 6 c c 幸( 口+ 易) = c * a + c 幸6 若域f 的元素有限个，则称之为有限域或伽罗瓦( g a l o i s ) 域。， o ) 表示集 合f 除去元素 o ) 之后的元素。 l o 浙江大学硕士学位论文第2 章基于a e s 算法的加解密 2 2 2 加法 字节加法可定义为多项式的二元加法，即有相同指数元素的系数相加，相加 操作( o ) 为异或( 模2 ) 操作。所以1 0 1 = 0 ，1 0 0 = 1 ，0 0 0 = 0 。 或者，加法也可由字节对应位的模2 加来描述。两个字节 a ；a 6 a s a 4 a 3 a ：a l a o ) 和 6 7 6 6 6 5 6 4 6 3 6 2 6 1 6 0 ) 相加，结果为 岛c 6 g c 4 c 3 c 2 c 。c o ) ，对每一个q = 口fo 岛。举例来 说： ( ，+ 石4 + ，+ x + 1 ) + ( ，+ 工+ 1 ) = x 7 + 矿+ ，+ ，( 多项式表示法) 0 1 0 1 0 1 1 1 0 1 0 0 0 0 0 1 1 = 1 1 0 1 0 1 0 0 ( 二进制表示法) 5 7 e 8 3 ) = d 4 )( 十六进制表示法) 2 2 3 乘法 用多项式表示法，g f ( 2 8 ) 域的乘法( ) 由对一个不可化约的8 次多项式进行 模操作所确定。一个多项式是不可化约的指它的约数只有1 和它自己。对a e s 算法来说，这个不可化约的多项式为： r e ( x ) - - x $ + 工4 + z 3 + z + 1( 2 1 ) 或十六进制标示法： 0 1 ) 1 6 ) 。 举例来说： 5 7 ) 8 3 ) = c 1 ) 因为 0 6 + x 4 + x 2 + 工+ 1 ) 7 + j + 1 ) = 工1 3 + 工1 1 + ，+ j 7 + x 7 + 工5 + ，+ z 2 + x + x 6 + ，+ 工2 + x + l = x 1 3 + 工1 1 + ，+ p + + ，+ x 4 + ，+ 1 并且 x 1 3 + 石“+ p + ，+ 矿+ x 5 + ，+ ，+ 1m o d u l e ( x 8 + 石4 + ，+ x + 1 ) = ，+ x 6 + l 对m ( z ) 进行模运算可以确保结果二进制多项式的阶次低于8 ，因此它就可以 用一个字节来表示。 、对任意一个阶次低于8 的非零二进制多项式6 ( 功，它的乘法逆元素可以通过 l l 浙江大学硕士学位论文第2 章基于a e s 算法的加解密 如下方法求得：使用用扩展欧几里德算法计算多项式a ( x ) 和c ( x ) ， 6 ( 功口( 力+ m ( 曲“曲= l ( 2 2 ) 因此，口( 功b ( x ) m o d m ( x ) = l ，这意味着 6 - 1 ( 曲= 口( 曲m o dr e ( x ) ( 2 3 ) 而且，对域中的任意口( 功，d 力，下式成立： 口( 功( 6 ( 工) + c ( 功) = 口( 力6 ( 功+ 口( 力c ( 力 ( 2 _ 4 ) 下面讨论多项式6 ( z ) 乘以石的情况，得到： 岛p + 吃工7 + 岛工6 + 么工5 + 6 3 石4 + 6 2 ，+ 6 i x 2 + b o x ( 2 - 5 ) 如果6 7 = 0 ，结果已经是不可化约的。如果岛之1 ，不可化约式通过减去埘( 功来得 到。在字节级别，多项式乘以z 可以通过向左移位和有条件的与 1 辨异或来实现。 该操作表示为x t i m e o 。乘以x 的更高阶次可以通过多次重复x t i m e ( ) 实现。通过加 上中间值，对任意数的乘法都可实现。如 5 7 - 0 3 ) = f e ) ，因为： 5 7 ) 0 2 ) = x t i m e ( 5 7 ) = 和e 5 7 ) 0 4 ) = x t i m e ( a e ) = 4 7 5 7 ) 0 8 ) = x t i m e ( 4 7 ) ) = 8 e ) 5 7 ) 1 0 ) = x t i m e ( s e ) = 0 7 ) 所以 5 7 ) 1 3 ) = 5 7 ) ( 0 1 ) 0 0 2 ) o l o ) ) = 5 7 0 口e ) o 0 7 ) = f e ) 。 2 2 4 系数在g f ( 2 3 ) 域中的多项式 一个系数在有限域中的四阶多项式由下式定义： a ( x ) = a 3 x 3 + a 2 x 2 + 口i x + a o ( 2 - 6 ) 它可以表示为一个字 a oq 吒码】。这个多项式与上文定义的多项式不同的地方就 在与它的系数本身也是有限域中的元素。所以对它的乘法需要使用一个不同的不 可化约多项式，将会由下文定义。 定义b ( x ) = 6 3 ，+ 6 2 石2 + 包工+ 6 0 ，加法操作仍然是相应系数的异或操作： 口( 功+ 6 ( 曲= ( 呜06 3 ) ，+ ( 0 如) z 2 + ( qo 岛弦+ ( o 岛) ( 2 - 7 ) 1 2 浙江大学硕士学位论文第2 章基于a e s 算法的加解密 乘法操作可以分为两个步骤。对f c ( x ) - - a ( x ) b ( x ) ，第一步，扩展c ( x ) 为： c ( 功= c 6 矿+ c 5 ，+ q + c 3 x 3 + c 2 x 2 + c l 工+ c o ( 2 8 ) 其中， c o = - t o c 4 = a 3 6 io 吒6 20 口l 岛 q = q o a o 岛 c 5 = a 3 如。口2 岛 c 2 - a 2 - b oo 口t 6 io 口o 6 2 c 6 = 口3 岛 q = 呜6 0o 口2 6 io 口l 6 2o 口o 岛。 由于结果c ( 力并不能表示为一个四字节字，所以第二步是c ( 功对不可化约多 项式进行模操作。该不可化约多项式定义为：，+ l 。所以， 一m o d ( ，+ 1 ) = 一m d 4( 2 - 9 ) 模运算结果由d ( x ) = 口( 工) o b c x ) 表示，定义如下： d ( x ) = 以z 3 + 吐，+ d i x + d o ( 2 1 0 ) 其中， d o = ( a o b o ) e ( a 3 j ) o ( a 2 6 2 ) o ( a j 岛) d l = ( a l 6 0 ) o ( a o b o e ( a 3 6 2 ) 0 ( a 2 - 6 3 ) d 2 = ( a 2 b o ) e ( a l - b 1 ) e ( a o - b o e ( a 3 6 3 ) d 3 - ( a 3 - b o ) e ( a 2 岛) o ( a 1 b o e ( a o 岛) 当口( 功是一个固定多项式的时候，以砂乘以口( 功的运算可以表示为以下矩阵 形式： 毛 吐 畋 也 口。心呸口o q 口。色呸 q 吃 口3 口2q 6 l 包 岛 因为，+ 1 = ( ，+ 1 ) 2 在g f ( 2 8 ) 域上不是不可化约的，所以乘以固定多项式并 不一定是可逆的。因此，a e s 算法选择了一个有逆运算的固定多项式： 口( 功= 0 3 x 3 + 0 1 x 2 + 0 1 ) x + 0 2 ) ( 2 1 1 ) 1 3 浙江大学硕士学位论文第2 章基于a e s 算法的加解密 口- 1 ( 曲= 0 b x 3 + o d ) 矿+ 0 9 ) x + 0 0( 2 1 2 ) 另一个a e s 采用的多项式的口o = q = 口2 = o o ) 和呜= 0 1 ) ，即，。对比上文 矩阵，即可发现，它的作用是通过旋转输入字来得到输出字，即把【6 0 岛如包】转 化成 白也岛b o 。 2 3 算法实现 2 3 1s t a t e 数组 a e s 的加密算法的数据处理单位是字节，1 2 8 - b i t 的比特信息被分成1 6 个 字节，按顺序复制到一个二维4 * 4 的矩阵中，称为s t a t e 数组，a e s 的所有变换 都是基于s t a t e 矩阵的变换。s t a t e 由4 行字节所组成，每一行包含了m 个字节， 6 是由数据块长度除以3 2 得到。s t a t e 数组中的字节由符号。或趣，c 】所表示， 其中o ， 4 为行号，0 c 6 为列号。 在加密和解密开始的时候，输入数据氓，以，氓，字节数组被复制到s t a t e 数组，加密和解密操作都在s t a t e 数组上进行，操作结束之后，输出值被复制到 o u t o ，o ，口“ 5 。如图2 1 所示： ；捌tb y t e s s t a t ea r r a y 翻删b y t e s 哟z n 4确l 玎1 2 ，l ，| l鹕磅硪1 3 魄 m 6魂 l 玎l 魂m 7l 霹l ll n l $ s b 静砘l缸加 葶l 毋s 1 1葶l - 2 s l j 南膏岛j s 专螽岛。l她 图2 1s t a t e 数组的输入和输出 o u t e o u t 4铂0 1 心1 2 o t i f f lo l t t 5嗽o i g l 3 o u t 2o u t 6o t g l oo u t l 4 佣而嘶o u h l嘶j 因此，在开始阶段，输入数组切，通过如下方法被复制到s t a t e 数组： s r ，c 】= i n r + 4 c 】f o ，0 ， 4a n do c 6 在结束阶段，s t a t e 数组按如下方法被复制到输出数组o u t ： 1 4 浙江大学硕士学位论文第2 章基于a e s 算法的加解密 o u t r + 4 c 】= j 【，c 】f o ，0 ， 4a n d0 c n d e v i c e n o d e s t r s u b s e t l n d e x p o f f s e t s n o f f s e t ； | 奄e l e a r | n d e v i c e n u m = 0