（系统分析与集成专业论文）整数表示在公钥密码体制中的应用.pdf

山东大学硕士学位论文 整数表示在公钥密码体制中的应用 摘要 r s a 和椭圆曲线密码体制是保障电子商务安全的两种常用公钥密码体制。 在这两种公钥密码体制上最基本的操作是计算模幂乘法和标量乘，它可以用普通 的二进制算法实现。众所周知，具有较少非零数位的整数表示可以提高一些代数 结构上基本操作( 如计算标量乘) 的效率比如利用n a f 算法，可以比普通的二 进制算法减少大约l 6 的椭圆曲线点加运算然而利用低非零密度的整数表示计 算点乘很容易受到边带信道攻击。这种攻击充分利用密码设备在运行过程中泄漏 的计算时间、电量消耗曲线等敏感信息来获得一些秘密信息。因此本文主要研究 各种整数表示在公钥密码体制上的应用和设计抵抗边带信道攻击的编码。 本文主要的研究内容如下： 1 从左到右的最优基数r 的编码。近年来，基数r 上的编码被用于特征为， 的椭圆曲线上有效点乘计算。t a j 【a g i 等人在i s c2 0 0 4 上提出一种从左到右的窗 口为w 的基数，的非邻接表示，即w 州a f 。我们提出一种新的带符号编码，该 编码具有和w r n a f 相等的非零数位密度“p 1 ) ( ，( p l 卜1 ) ) 。在相同数位集上，新 的编码具有最小的h 姗m i i l g 重量，且可以用从左到右的编码算法实现与m n a f 相比，新的编码算法可以结合从左到右的点乘算法实现同步计算从而减少编码的 存储空间。 2 w | ，n a f 编码的安全性分析和抵抗简单功耗分析的点乘计算。基数，上的 编码被用于特征为，的椭圆曲线的有效点乘计算。但是利用密码设备在运行过程 中泄漏的计算时间、电量消耗曲线等敏感信息对一些密码体制进行攻击的边带信 道攻击已成为安全实施密码体制的巨大威胁。我们利用简单功耗攻击分析了 w 中n a f 编码的安全性，表明w 榭a f 编码不具备抵抗s 队的性质。为此我们提 l 了两种不同数位集上抵抗s p a 的固定计算模式编码( 从左到右和从右到左k 与已 有的h 锄的编码算法相比，我们的方法可以减少大约1 6 7 到3 7 5 的预存储 点个数，从而提高点乘计算的效率。 3 抵抗差错攻击的b o s 算法安全性分析。在c c s2 0 0 3 上，b 1 6 m e r 0 仕o 山东大学硕士学位论文 和s e i 勋提出一种可抵抗差错攻击的c r l ：r s a 签名算法即b o s 算法不幸地 是，一年后w h g i l e r 提出一种简单有效的真对b d s 算法的差错攻击。我们又进一 步分析了b 0 s 算法的安全性，并提出了一种新的差错攻击方法。攻击者首先在 私钥磊上引入一固定错误，然后运行b o s 算法生成四个错误的签名。最后利用 这些信息和最大公因子算法即可得到r s a 模数的分解。 关键词公钥密码体制：整数编码；密码分析；边带信遘攻击 v 山东大学硕士学位论文 e f f i c i e n t 璀t e g e rr e p r e s e n t a t i o n sf o rp u b l i c k e yc r y p t o s y s t e m s a b s t r a c t r s a 锄de n i p t i cc i 州cc 聊咖呵g 忙m ( e c c ) t l i a tm a d es 叫时i ne l h d n i c e n v i r o n m 黜i 忸a m “，oc 咖m 哆i i ，e d p u b i i ck e ya y p t o s y s t c m s t h eb a s i c m a m c m 撕co 昨讯t i o ni l ia b o 、幢c i y p 幻盯s t c m si s a l 盯m u i t i p “c a t i o nw h t c hc a nb c c 帆p u t c d 惦i i i gt h cb i n a r y “g 炳l 量i i n ni sw e l lk n d w n 协a tt h e 佗p 地s 曲协t i o f 锄 i n t e g 盯w i t l if 每wl n 砑d i g i 虹a l l o w st l l eh 船i ca l g e b m i co p e m l i 吼s ( h e i s 靶a i 对 m u l t i p l i c a t i o n ) t ob ed o n cm o 怫q u i c k i y s u c h 鼬n a fa l g o r i t i i m ，i tc a n 嵋d u a b o u t l 3p o i n ta d d 砸o nm 柚g c m ib i 哆a l g o r i t h 哪h o w c v c rt h es l 盯m u l t i p i i c a t i o n n s i n gj a wn o 暇r od e 地i | yr 印陀s e n 扭t i o ni sv u l i l e r 曲l et o b es o c a j l e ds i d ec h a n n e i 咖c l 【sw h i c bc x p i o “i e a j c a g ei i i f o 咖毗i o nb ) rc l y 肿d g m p h i cd “妇ss u c h 嬲 m p u t a l i o 舱it i t i l c ，p o w c r 仃a c e s 锄dc t c t h i sp 8 p c ri sc o n c e m e dw i t h 蚰mv a r i 伽s 托p 豫n t a t i o 鹳o fi i l t e g e 幅t l l a ta 他碍i a t e dt oe 衢c i e n t m p i e m 蚰t a t i o n so fb 粥i c a l g e b m i co p c 随t i 叫s i n p u b i i ck e yc r y p t o s y s t e m s 柚dv 孤i o u s 佗p r e n 协t i so f i n t c g e 玮t i l a ta ”辩叫r 时a g a i n s ts i d ec h 册眦la l t a c l c s t h e t o p i c so f t i i i sp a p c ri l u d e ： 1 h f h o - r i g h tm i n i m a lw e i g l l ts i 驴c d - d i g i tr a d i x rr e p 佗s 朋t a t i o n r e n t l y r a d i x ，他p f c 潮t a l i o ni su s c dt og 雕蟹d p 幽e 鲇a j a l m u j t i p j i c a t i o no fp a i r i n gb a s e d c q p t o s y s t e m sw i mc h 跏i c t c “鲥c ，a ti s c2 0 0 4 ，t a k a g i 武a 1 i n t f o d u c e d 幽ew i d t h 哪 ，n a ff o r 也cs 细e dd i g i t 姐d - ，r e p 嘲曲t i o n ，w h c hi so b 诅i n e df r o mr ；g l i tt ol e f i w bp 陀s e n tan e ws i g n 。d 脚i x - ，i - c p 旭辩n 诅t i o nw 弛t i l e 豫m ea v e f a g cw e i g h t 躯 w 州a f l a ti s ( ，l l 矾似，- l 卜1 ) 1 n h e 鹏w p 陀n t a t i o nc 孤b co b 诅m e d 惦i n ga i 曲一t o - r i g h ta l g o m h m 柚dh 鹤am i n i m a ln u m b 盯0 fn o n - z c d i g i t s 帅0 n ga t h e f 印佗n t a t i o 螂w i mt h es 跏cd i g “s c t 邪聊_ n a f w bc o m p a 坤o wa i g o r i t i i mw i m p 坪v i 叫s e s 粕di ts h o w st i l a ti l ip a i r i n gp a s s e dc i y p t o s ”t e m s ，叫ra l g o r i t i i mc 锄 捌u b o t lt i l e 谊n e 粕ds p a c 。c o m p i 懿i t yo f s l 盯m u l t i p l i c a t i o nt h a np f w i o u so n e s ， 2 s e c u 嘶柚嘶s i so f ，削”a n ds 队心s i s 协i i t 湖1 盯m u i t i p i 妇t s i g l l e d d i g i t 阳d i ) r r 佗p 托s c n t a t i o ni su 辩df o rt h ee 衔c i e n ti m p i e m e n t a t - o no ft i l e a l 盯 山东大学硕士学位论文 m u h i p i i c a t i o n h o w e v c r ，t l l es i d l l a i l n e la n kw h i c hu s e st i i ei c a k e di n f 0 咖a t i o n 鳓c h 猫c o m p u 锨i o n a lt i l n c 唧r 地蛉e sf b m ac l y p o 黟s 蛔l i ；i sa 辩r i o 璐t l l 把a t o t l l ei m p i e m e n 扭t i o n so fac l y p t o s y s t e m w bu t i l i z et l i es i m p l e 舯岬盯搬l y s i s t e c h n i q u e t o 锄l y 冲t h es u r i t yo f l ，n a f 彻d 、wc 觚s t l i a t t i l e 聊n a f sn o t a s f a 代s i s 组n tr 优o d i n g 1 no r d 盯t o s 硫a g a i n s ts i 氐w cp r e n t 咖i n t c g c r c o d i n g s ( r i g h t t o - k f ta n dl c f i t o - r i g h t ) 憾i n gt w os p e c i a ld i g i t t sr e s 非虻t i v e 耻t h e 铆or o d i n g s 啪b el ，s e dt op c 晌叽t h e a km u n i p l i c a t i o nw 汕af e ds c q n o fo p e r a t i o 粥w i t i l o u ti l l r t i n gd 啪m y 哪峙讯t i o n s c o m p a r e dt 0h a n sf i 湘dp a t t c m h e m e ，t h ep r o p o s e ds c h c m 弗强nf e d u c ea b o u t1 6 7 t o3 7 5 t a | b ks 函s ( m e n 哪b e r o f p 舢m p 删锄dn e e d e d t ob e 哟硎p 0 主n 唏f o r ，q ，5 锄d w 哟，3 ，4 5 3 f 呲h e rc f y p t a l 陋l y s i so fap m v a b i ys e c 啪c r t - r s aa l g o f i t l l i l l a tc c s2 0 0 3 ， an 哪f a u l ti i i l m u n ec r t - r s as i 驴枷f c “9 0 r i t i i m 枷i yb o sa 1 9 0 棚蛳哪 p p o db yb 1 6 m e o t t o ，a n ds e i 触u n f b 咖n 咖i y ，o 雠y e 盯l a 缸、g r i e r p 陀辩n t e das i m p l e 锄dp m c t i c a l 甜k t i l eb o sa l g o r i n 吼w bf i l r l l l e r 锄a l y 笳t i l e s c c u f j l yo fn b o sa l g o f i t l l m 卸dp 陀n tan e wf a u l ta t t a c kw h i c h nb cd c s c r i b c d 嬲矧1 0 w i n g s ：n ea d v c r s “e s 触t i n d u c eap c 哪锄e n tf a u l t t h e 雠佗tr s a k e y 彩 锄dt h e nm nt h eb o sa 1 9 0 r j t l l mt oo b t a i l lf o u ff 扎峥r s as i 髓a t i i 佗s l a s t i y t l l e a d v e r 鞠一髓u s et h eg 代a t c s tc o m m o nd i v i ra j g o f ；| h m 乇oo b 纽i nt l l ef k t o r i 臻t i 锄o f t i i er s am o d u l u s 1 ( e yw o r d 叠：p u b l i c k e yc f y 呻s y s t e m s ；i n t e g e r 他c o d i n g ；c r y p t a i l a i y s i s ；s i d e c h a n n e la t t a c k s 山东大学硕士学位论文 符号说明和缩略词 n ， 局 l 婚a 群s 乙 【j j x 聊 i i ( a ) g c d 伍g ) 删 e c c e c d s a a e s r s a n a f 彬n a f g n a f m o f g m o f n a f w 臌蟠 s c a p o w c ra n a c k sp _ a d p a f a u ha n a c k 素数 含有口个元素的有限域 有限域兄上的椭圆曲线 1 集合s 的势 模h 环 不大于x 的最大整数 整数工的相反数，即哼 工的二进制长度 串中非零位的个数，即h a m m i n gw e i g i i t ，和g 的最大公因数 工的欧拉函数 e l i i p t i cc u n r ec r y l 们g f a p h y e l l i p t i cc u r v ed i g i 诅ls i g i l 咖a 1 9 0 r 血m a d v 扑c 耐e n c r y p t 咖s t a l i 捌 剐v e s t - s h 枷* a d i e m 矾e n c r y p t i o n h e m e n 一删祁e n tf 0 椭 晰d t h wn 伽- a d j a c e n tf o m g e m l i z e dn a f m u “do p p o s hf o 加 g e n 啪l i z c dm o f r a d j x - rn a f w i d t l i ，r n a f 边带信道攻击，s i d e c l i a r i n e l a k 功耗攻击，或能量攻击 简单功耗攻击，s i l i i p i ep 0 w c r a t t a c k 差分功耗攻击，d i 疏m n t i a l 晰a t k 差错攻击 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研 究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡献的个人和集 体，均已在文中以明确方式标明。本声明的法律责任由本人承担。 论文作者签名：塞重叁 日 关于学位论文使用授权的声明 本人同意学校保留或向国家有关部门或机构送交论文的印刷件和电子版， 允许论文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段保存论文和 汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：纽导师签名讯睦日期：掣 山东大学硕士学位论文 1 1 背景和意义 第1 章绪论 目前密码技术已经广泛应用于电子商务、网上银行、电子政务等社会各个领 域，成为保障网络信息安全的核心技术如计算机网络环境下信息的保密性、完 整性、可用性和抗抵赖性，都需要采用密码技术来解决。因此密码技术已成为许 多计算机学者研究的重点。 密码体制主要分为两类：对称密码体制( 又叫私钥密码体制) 和非对称密码体 制密码体制( 又叫公钥密码体制) 。对称密码学具有古老的历史，如古典密码学在 古代军事领域有着广泛的应用而公钥密码学是以1 9 7 5 年d i 币e 和h c l l m 柚发 表的“n e wd i 州i o 越i nc i y p t o g r a p h y ”【2 5 】为开端，在现代密码学中担负起密钥 协商、数字签名、消息认证等重要角色，已成为最核心的密码。 当前主要的公钥密码体制有1 9 7 8 年r i v e s t 、s h 锄i r 和a d e l l n 粕提出的r s a 公钥密码体制【7 7 】、1 9 7 9 年r a b i i l 提出的r a b m 公钥体制【7 6 】、1 9 8 5 年e 1 g 锄a i 提出的e l g 姗a i 密码体制 2 7 】和1 9 8 5 年m i l l e r 【5 9 】和k o b l i 乜【4 5 】分别独立提出的 椭圆曲线密码体制。这些公钥密码体制主要基于数学上的一些困难问题，如大整 数因子分解困难问题，求和数的平方根困难问题，离散对数等困难问题。 在上述公钥密码体制中应用最广泛的是r s a 体制。r s a 算法基于大整数环 乙上的一个单向陷门函数，在这里月为两个大素数p 和g 的乘积。r s a 算法中 单向陷门函数定义为模一的求幂运算，其正向计算是容易的。在不知道p 和g 即 疗的分解时，其求逆运算是困难的由于一些分解因子算法【5 l ，5 3 】的提出，对 r s a 安全性提出了更高的要求。目前常用的r s a 模数的长度为1 0 2 4 比特，其 因子p 和g 的长度大约为5 1 2 比特。模”的求幂运算占用r s a 算法的主要计算 时问，因此研究如何提高r s a 算法中求幂的计算效率具有重要意义。 目前椭圆曲线密码体制( e c c ) 也得到人们的广泛关注，一个主要的原因是 e c c 密钥长度短同时具有更高的安全性，在计算效率上也要优于其它公钥密码 算法从表1 1 1e c c 和r s a 在密钥长度和安全性比较可以看出，在相同密钥 长度下，e c c 具有更好的安全性因此，对于资源空间有限的智能卡( s m a r t 山东大学硕士学位论文 c a f d s ) ，选择椭圆曲线算法更适合在椭圆曲线密码体制如e c d s a ，最基本的 运算是计算舻，在这里t 为一整数，为椭圆曲线点群鼠r ) 中一点。这种运算 通常叫作点乘或标量乘计算。因此，研究如何提高椭圆监线上的点乘计算效率同 样具有重要的意义。 t a b k l 1 1 麟a 和e c c 比较 传统观点认为一个密码体制的安全性主要取决于所在代数结构的安全性 1 9 9 6 年p 卸lk o c h e r 【4 6 】提出一个全新的密码分析方法一边带信道分析( s i d e c h 锄e la n a i y s i s ) 又叫信息泄漏分析衄f o m a t i l c a k a g ea n a j y s i s ) ，它依赖于算 法在实现过程中泄漏的物理信息如计算时间、电量消耗、电磁辐射等，而不是算 法所在的数学结构。边带信道攻击方法主要有三种：k o c h 盯在c r y p l d 1 9 9 6 上 提出的时间攻击f n m i n g a t k k ) 【4 6 】，b o n c h 在e u r o c 鼢r p l o 1 9 9 7 上提出的差 错攻击( f 叫l ta t 拓吣k ) 【l6 】和k o c h c r 在c 鼢r p l d 1 9 9 9 上提出的功耗攻击( p a 、v e r a n a c k ) 【4 7 】。近年来又提出一些新型的边带信道攻击方法如g o u b i n 【3 2 】的趾a 攻击( r e f m e dp a w 甜c k ) ，a k i s h i 协【l 】的零值攻击( z e r o - l 雌p o i i i t 眦c k ) 和 f o l | q u e 【3 0 】的倍点攻击( d o u b l i n g a t t a c k ) 等。因此从边带信道攻击角度研究算法的 安全性和设计抵抗边带信道攻击的高效安全算法具有重要意义。 1 2 研究的主要内容和创新点 i 2 1 研究的主要内容和存在的问题 本文主要研究整数的各种表示在提高公钥密码算法计算效率和安全性方面 的应用r s a 和椭圆曲线密码体制是两种重要的公钥密码体制，尤其是椭圆曲 线密码体制逐渐被应用在各种密码协议中，如椭圆曲线签名体制( e c d s a ) 。在 山东大学硕士学位论文 e c d s a 中最基本的运算是计算七p ，其定义为 ， 陋p + p + p 了一 在这里j | 为一整数，p 为椭圆曲线点群耳r ) 中一点这种运算通常叫作点乘或 标量乘计算。在实际应用中计算椭圆曲线上的点乘首先要对整数 进行编码，如 最基本的二进制表示( b i n a l yi 沁p 他s 曲僦i o n ) 。假设i 的二进制表示为： 七= 雠i ，毛卜2 ，岛卜= 毛- 1 2 卜1 + 量；卜2 2 柚+ + b 2 0 ，南 0 ，l 上面的编码通常叫作数位集 o ，l 上的二进制编码则计算点乘的基本算法如下 ( 通常叫做二进制算法( b i 船i ya l g o r i t l l m ) ) a i 驴r i t h m1 2 1b i 眦r ya i p n t h m h p m ：i = = 七f 2 。，七， o ，l ，户耳叼 o u t p u t ：七尸 1 q 扛0 2 如r 芦矾一l t o o d o 3 q - 2q 4 i f 南= l 血e n 加9 咿 5 r e t n m 9 在算法1 2 1 中9 咿和2 q 通常叫作点加和倍点计算，其具体计算为有限域 上的计算通常情况下倍点计算量要小于点加计算量约为o 8 倍。若| 的二进制 为m ，算法1 2 1 平均需要埘次倍点运算和 以次点加运算。在计算点乘算法中， 点加的计算次数与编码的h 锄m i i l g 重量即编码表示的非零数位的个数有直接关 系。由于椭圆曲线点群中元素逆的计算即计算p 几乎不需要时间，所以研究带 冗余数位集上具有最小h 锄m i l i g 重量的带符号编码是提高点乘计算效率的有效 方法之一如著名的n a f ( n o n - a d j c n tf o m ) 表示，其h 锄m i n g 重量约为口以， 这里肼为n a f 表示长度。利用整数的n a f 表示计算点乘比算法1 2 1 平均要减 少蒯6 次点加已有的其它最优带符号编码表示有w n a f ，g n a f ，n a f ，柳n a f 等。 通常我们把编码所在的数位集记作d 。假设基数为2 ，整数女在数位集d 上 山东大学硕士学位论文 的最优带符号编码表示为七= ( 毛，卜i ，七1 ，知) ，毛d 。那么可用算法1 2 2 计算舻 a l g o r i 恤m1 2 2s c a h rm u l t i p u c a t i o n i n p u t ：坷k i ，南，知) 2 ，户点f o u t p n t ：( 净舻 1 p 嗍m p 臼戗蚰：f 0 r e a c h 挺d w 血痧o ，m p 咖助卜卯 2 q b 3 f o r f l h m 胂一ld o w n t o o d o 4 q hq 5 h 岛o m e _ 6 南 0 吨e n 9 - q + 最 7 e k 妒q + 罡 8 黜佃nq 算法1 2 2 是从左到右即从编码的高位到底位计算的，这与一般从右到左即 从低位到高位编码方向相反，这就要求我们先把整数进行编码并存储，再利用算 法1 2 2 计算点乘。当存储空间有限如智能卡，密钥长度较长时，如何设计并性 计算即编码和点乘计算同步成为近年来研究的热点。这种编码也叫从左到右编码 ( l e m 缸r i g h tr e c o d i n g ) 。在文献【6 ，3 8 ，6 7 ，7 0 ，4 l 】中提出了几种基数2 上的从左 到右最优带符号编码，在文献【3 7 ，4 8 ，6 6 】提出了几种基数，上的从左到右g n a f 表示。对于设计非邻接的基数r 上的最优从左到右编码一直是个公开问题 在密码分析方面，边带信道分析( s 池c h 跏e l a l y s i s ) 对许多密码算法包括 椭圆曲线点乘算法造成巨大的威胁。目前设计抵抗边带信道攻击的算法已成为研 究的热点在已有的抵抗算法中，使用同定计算模式抵抗简单功耗攻击是一种有 效的方法。但是这种方法往往需要较大的预存储点。o k e y a 【7 l 】提出一种利用 w ，n a f 抵抗边带信道攻击的方法，该方法可以在抵抗边带信道攻击的同时有效处 理存储空间和效率的平衡最近，h a n 【3 4 】把o k e ”的方法应用到基数r 上，但 是该方法仍然需要更大的预存储点空间，研究基数，高效的抵抗简单功耗攻击的 方法仍然是个公开的问题。 4 山东大学硕士学位论文 人们通常利用中国剩余定理来提高r s a 算法的计算效率。但是差错攻击 ( f na t t a c k ) 仍然是c r t - r s a 算法的一个巨大威胁目前设计抵抗筹错攻击的 c r r s a 算法也成为人们关注的热点主要方法有利用h 嬲h 函数【3 6 】对消息m 进行杂凑防止攻击者访问消息，s h 锄i r 【8 0 ，7 9 】的检验签名正确性办法，y e n 【9 5 】 等的差错计算传播方法，避免正确性检验。但是这些方法逐渐被证明是不安全的。 最近一些新型的抵抗算法被提i i ，研究这些抵抗算法是否安全仍然是个公开的问 题 1 2 2 论文的主要创新点 ( 1 ) 本文详细分析了w n a f 编码的性能( 编码长度、h a m m i n g 重量、非零 密度、预存储点个数等) ( 2 ) 提出了一种在与w r n a f 相同数能集上从左到有的带符号编码。分析表 明这种编码具有最小的h a m m i n g 重量，结合从左到右的点乘计算可以有效减少 编码的预存储空问 ( 3 ) 提出了一种抵抗简单功耗攻击的编码安全性分析模型，并给出一种基 数，上抵抗简单功耗攻击的编码算法，该算法可以从左到右和从右到左编码。分 析表明该算法比已有的方法要减少1 6 7 - 3 7 5 的预存储点。 ( 4 ) 分析当前一种主要的抵抗差错攻击算法( b o s 算法) 的安全性，提出一 种有效的攻击方法，可以完全攻破b o s 算法。 1 2 3 论文的组织结构 本文个章节的组织结构如下： 第一章：绪论。论述了本文研究的背景和意义，介绍了本文研究领域已有的 工作和存在的问题，最后概括了本文的主要创新点 第二章：背景知识介绍了本文要用到的基本数学知识，包括同余理论、群 环和有限域、概率论和m a r i o v 链理论；同时还介绍了r s a 和椭圆曲线公钥密码 体制的相关理论。 第三章：基数2 上的整数表示。详细介绍了基数2 上几种主要的从左到右带 符号编码算法，包括n a f 、w i n a f 等，并分析了它们在编码长度，h 姗m i n g 重 5 山东大学硕士学位论文 量、非零密度、预存储点个数等方面的性能。同时还介绍了基数2 上从左到右的 m o f 编码和w m o f 编码，并分析了它们的基本性能和在椭圆曲线点乘计算上的 应用。 第四章二基数，卜的整数表示。介绍了g n a f 及其从左到右编码、，n a f 和 i ，q a f 等几种已有的基数，上最优带符号表示的概念和性能。提出了一种新的 从左到右的基数r 上最优带符号表示。 第五章：边带信道攻击及抵抗算法。介绍了几种主要的边带信道攻击的概念 和原理。提出一种商效的抵抗简单功耗攻击的基数，j ：的编码算法。最后分析了 抵抗差错攻击的b o s 算法的安全性，并给出了一种简单有效的攻击方法。 第六章：结论和将来的工作。总结了本文的内容，提出了将来研究的工作。 6 山东大学硕士学位论文 第2 章背景知识 本章简单介绍一些预备知识，包括数论和代数学理论、概率和m a r k o v 链理 论、髓a 和椭圆曲线公钥密码理论。这些预备知识将用来分析本文给出的各种 整数表示算法的性能，包括表示的长度、最优性、h a m m i n g 重量和在实际应用 中的效率等有关密码学数学基础知识和公钥密码理论更详细的内容可参考以下 文献，数论【7 2 】。代数学【6 8 】，概率论【8 l 】，m a r k o v 链理论【3 3 1 ，骼a 算法【7 7 1 和椭圆曲线密码理论【8 2 ，1 2 ，9 6 ，7 1 2 1 同余和剩余系 定理2 1 1 ( 带余除法) 设口，6 是两个给定的整数，口0 ，那么一定存在唯 一的整数g 和r ，满足扣g r怄，q 叫 定义2 1 1 ( 同余) 设若脚i 口由，即f b n ，则称口同余于6 模挑 6 是4 对模m 的剩余，记作6 ( m o d 肼) 定义2 1 2 ( 同余类) 全体整数按照模m 是否同余可分成若干两两不相交的 集合，每一个这样的集合称为模m 的同余类。通常以r m o d 坍表示，所属的模m 的同余类，即r m o d 册= 加，i e 乃。 对于给定的模胁有且恰有个不同的模m 的同余类，即： o m o d m ，l m o d m ，( m 一1 ) m o d m 。 定义2 1 3 ( 完全剩余系) 一组数，l ，n ， 称为是模的完全剩余系， 如果对任意的，有且仅有一个n 是，对模珊的剩余，即，s ，f m o d 肌 例如0 ，l ，j ，卜l 和删】，如l 例一1 等都是模肼的完全剩余系， 它们分别称为模m 的最小非负( 完全) 剩余系和绝对最小( 完全) 剩余系 定义2 1 4 ( 既约同余类) 模m 的同余类，m o d m 称为是模的既约( 或互 素) 同余类，如果( ，) = 1 模脾的所有既约同余类的个数记作币( m ) ，通常称 为e u i 盯函数 定义2 1 5 ( 既约剩余系) 一组数，。，：jn 称为是模的既约( 或互 素) 剩余系，如果( 如册) = l ，l f 如以及对任意的，( ，m ) = l ，有且仅有 一个n 是，对模m 的剩余，即，z n m o d 州。 7 山东大学硕士学位论文 定理2 1 2 ( 孙子定理) 设m l ，哟，帆是两两互素的正整数。那么， 对任意整数口l ，啦，一次同余方程组 挣口f ( m o d 珊) ，l f j | ， 必有解，且解为 j 暑 t f 1 q + + 靠1 - q ( m o d 埘) ， 在这里，口同h i 帆，”产钥，膨( 1 s j s d ，以及所1 是满足 m 圻g l ( m o d 嘲) ，l f 致 的一个整数。 孙子定理可用于提高r s a 的解密算法和签名算法的效率，我们将在第5 章 5 2 节介绍这方面的内容 2 2 群环有限域 定义2 2 1 ( 群) 设g 是一个非空集合。如果在g 上定义一个代数运算， 称为乘法，记作或称为加法。记作+ ，且满足 i ) 对于任意元素口。6 ，c g 有0 - c i 口o c ) ； 2 ) 存在p g 使得对任意d g ，有p 口= 口萨毋 3 ) 对任意口e g ，存在一元素6 g ，使得d 6 彳 那么g 称为一个群。 如果对任意口6 g ，有口6 劫口 那么群g 又称为交换群或a b c i 群。 群g 中元素的个数称为群g 的阶，记作旧。如果 q 为一有限数，则g 称为 有限群，否则称为无限群。 在群g 中h 个4 相乘记作4 | | ，即矿印伊”口个) ；对于交换群通常把其运 算记作+ ，这时 个口相加则记作h 口= 叶叶忉( n 个) 设口g ，若存在最小的有正整数使得矿印，则称口的阶为 ；否则规定口 的阶为 将在后面2 4 节中介绍的椭圆曲线密码体制就是基于一有限a b c l 群，其元 素之间的运算通常称为点加 定义2 2 2 ( 环) 设非空集合置同时具有两种运算：加法( + ) 和乘法( ) ， 山东大学硕士学位论文 且置对于加法构成一a b c l 群，其加法单位元记作o ( 称为零元) ，对于乘法满足 封闭律、结合律、交换律和分配律，则r 称为一个环 定义2 2 3 ( 域) 如果一个环中的非零元素在乘法运算下构成一个群，则该 环称为一个域，记作r 域f 中元素个数为有限个，则f 称为有限域；在加法群中，单位元素e 的 阶称为域f 的特征，通常记作x ( 即。 设p 为素数，贝l j 乙在通常的加法和乘法运算下构成一个有限域，记作昂； 有限域昂的次扩域记作= 2 3 概率和m a r k o v 链理论 在分析一个编码算法的性能时，通常要涉及计算一些概率问题，下亟就本文 涉及到的概率问题，给出相关的介绍。有关概率论更详细的内容可参考文献 8 1 定义2 3 1 ( 概率的经典定义) 假设一个试验可以从胪群。个等可能的点中 产生一个点，并且每次试验必须产生一个。令m 表示事件e 包含的点的个数， 那么称竺为事件e 发生的概率，记为，( e ) ：竺。 性质2 3 1 对于任一事件e ，怄p ( d 1 性质2 ，3 2 对于任意h 个互不相交的事件而，历，磊满足 p ( 巨ue 2 u u 瓦) = 二l 。，( 互) 定理2 3 1 烈蜀u 毋产爿局卜p 卜烈e l n 毋) 。 定理2 3 2 ( 条件概率) p ( 口i 棚= ! 鼍导产 定理2 3 3 曰( o z 口= i p ( ) 。 m a r k o v 链理论在密码分析中具有重要作用，是分析一个编码算法性能等问 题的有效手段。下面简单介绍有限状态空阃上的m 甜k o v 链问题，更详细的内容 可参考【3 3 】 定义2 3 ，2 设r 是一h 七矩阵，其元素为 l 户l ，q 。如果个 取值于有限状态空问船0 l 瞄的随机过程( 局。x ) 对于所有的n 卸， i 。斥 l ，i 和如，o l e l ，七 满足 9 山东大学硕士学位论文 p ( 五+ - = i k = ，五= ，以t = k ，邑= ) 2 以x 0 ，= l 爿j = 邑) 2 只， 则称之为具有一转移矩阵r 的m a d 【o v 链。 从上述定义可以看出，对于有限状态空间上的m a r k o 、r 链当前状态出现的概 率只与前一状态有关，并且其转移矩阵r 满足下面性质： 性质2 3 3 任意f ，忙 l ，| i ，只户o ；任意f 苣 l ，j j ，：。i 最= 1 。 如果一个m a r k o v 链的任意状态都能由其它状态经过有限步到达，则称之为 不可约的( i r r e d u c i b l e ) ，否则称之为可约的( r e d 眦i b l e ) 。如果一个m a d ( o v 链的所有 状态的周期都是l ，则称之为非周期的( a p c r i o d i c ) ，否则称之为周期的( p 两0 d i c ) 。 定义2 3 2 ( m a r k o v 链的平稳分布) 设( 蜀，x ) 是有限状态空间阳， 毗 上转移矩阵为r 的m a r k o v 链。如果向量丌= 丌l ，兀2 ，取 满足 1 ) 而卸，卢l ，七，且：。乃= l ；2 ) ”铈 2 4r s a 算法和椭圆曲线理论 公钥密码体制( p u b l i c - k e y c r y p t o g r a p h y ) 在密钥协商，数据加密，数字签名， 身份识别和验证等方面起着重要的作用，是传统对称密码体制所不能替代的。目 前流行的两种公钥体制是建立在模n 整数环上的r s a 密码体制和建立在有限域 凡上的椭圆曲线密码体制，尤其是椭圆曲线密码体制在安全性和密钥长度方面更 优越于r s a 密码体制，且在签名和解密方面较r s a 快。然而，无论是r s a 还 是椭圆曲线密码体制都要涉及大量的数据运算，例如r s a 加密或签名算法要涉 及到1 0 2 4b 趣的模指数运算，椭圆曲线签名算法( e c d s a ) 要涉及到曲线上的点 加和倍点运算，该运算消耗大量的计算时间因此，提高这些密码体制关键算法 的计算效率( 计算时间复杂性，存储空间和同步性等) ，其意义尤为重要。本文 主要研究这两种密码体制，尤其是椭圆曲线密码体制上关键算法的效率问题，因 此在这里简单介绍这两种密码体制。更详细的内容可参考文献，r s a 7 7 1 ，椭圆 曲线【8 2 ，1 2 ，9 6 ，7 】。 r s a 公钥密码体制 自1 9 7 6 年d i 衢e 和h e m a n 【2 5 】首次提出公钥密码系统观点以来，第一个比 l o 山东大学硕士学位论文 较完善的公钥密码算法由鼬v e s t ，s h a m i r 和a d l 咖柚在1 9 7 7 年提出的，即r s a 算法。r s a 算法的基础是数论的欧拉函数，它的安全性依赖于大数的因数分解 的困难性。首先介绍r s a 算法密钥，包括公钥n ，e 和私钥d 的建立过程。 密钥建立 l 、选择两个不同的大素数p 和g - 2 、计算，固叼及其欧拉函数们户( 卜1 ) ( p 1 ) ； 3 、随机选择整数p 满足g c d 0 ，q o ) 户l ； 4 、计算d 满足耐；l ( m o d 甲o ) ) ； 5 、公开加，e ) ，保密( p ，g ，吐似”) ) r s a 算法参数的选择要满足一定的条件。比如p 和g 要足够大( 约5 1 2b i 田，以 防止二次筛法( q u a d r a t i cs i e v e ) 【7 4 ，7 5 ，8 3 】、数域筛法( n u m b e rf i e l ds i e v e ) 【5 4 ，5 5 】、 椭圆曲线算法( c l l i p t i c ea l g o r i 吐瑚) f 5 2 ，6 4 】等因子分解算法：公钥# 和私钥d 不能选择太小，以防止低指数攻击【9 2 】。有关具体的r s a 参数选取问题可参考文 献【8 8 ，8 7 】。下面介绍利用公钥q ，f ) 和私钥p 对消息埘的加密和解密过程。 加密算法：c = e ( 研闻，( m o d 月) ； 解密算法：d ( c ) ；，( m o d h ) 。 r s a 算法的加密和解密运算可以看作是在乘法群z ：上的模指数运算，即计 算，m o d 月。计算模指数最基本的有效算法是“平方乘”方法。通过预存储、同 步计算等方法，可有效提高“平方乘”算法的效率，这也是本文研究的主要内 容。下面我们介绍另一种群有限域上椭圆曲线点构成的a b e l 群上的公钥密码体 制，即椭圆曲线密码体制。 椭圆曲线密码体制 1 9 8 5 年，k o b i i 乜【4 5 】和m i l i 盯( 5 9 】分别提出在椭圆曲线有理点群上构造密码 体制。密码学中使用的椭圆曲线定义在像有限域这样的代数结构上。为便于说明， 在这里只介绍特征大于3 的有限域圪上的椭圆曲线，特征为2 和3 的椭圆曲线 可参考【8 2 ，1 2 】。 岛上的椭圆曲线e 是点似力日x f 叮，且满足下述方程 e 芦叠+ 时h 。 的所有解和额外的点无穷远点印) 组成的集合，其中珥6 e ，4 矿+ 2 7 6 2 如。该集 山东大学硕士学位论文 合通常记为： 耳日产 化力i 似力局且，= ，。时6 u 细 。 上述集合中的元素在适当的运算法则下构成一有限交换群。其群中元素的运 算法则定义如下： 定义2 4 1 ( 点的加法规则) 设肛缸l ，y i ) ，q = o 兜) 联r ) ，则一辟电l ，哼1 ) ， p h ；如果q 争p ，则p + q 气如，妁) ，其中 幻= 甜一朝一匏，弦= 钺x l -