（电路与系统专业论文）1024位高频rsa专用集成电路的设计.pdf

捕要 摘要 随着数据通讯的日益增长以及身份认证、电子商务等网络服务的迅猛发展， 网络的安全问题变得越来越为重要。保障网络安全的一种有效的解决方案是公钥 密码系统。r s a 是最为流行的公钥加密方案，被人们广泛地应用。r s a 的主要 操作是通过反复的模乘运算来计算模幂。然而，像】0 2 4 位的大位数模运算使得 r s a 密码系统难于实现。为了解决这一问题，在进行模乘运算的时候通常采用 m o n t g o m e r y 模乘算法。 出于性能、以及物理安全的原因，通常利用硬件实现r s a 密码系统。但是， 在r s a 算法的硬件实现过程中，出现了许多难以解决的问题：其一，由于硬件 运算速度的限制，r s a 算法现在只能用来交换通信密钥，而无法对通信中的所 有消息进行加解密；其二，r s a 算法中需要对大位数进行模乘运算，而为了在 未来一段时间内保证信息的安全，要求公钥n 具有多达1 0 2 4 位( 二进制) 的位 数，这样就需要大量的存储器件和运算单元，致使芯片面积增大、功耗上升。 为了减少运算时间、提高芯片的有效性，我们做了以下工作： a 1 对m o n t g o m e r y 模乘算法作了进一步的改进，提出了适合硬件实现的 具有较小面积的方案； b )并用以s r c m o s ( s e l f - r e s e t t i n gc m o s ) 电路实现的6 4 - b i t 并行二进制 先行进位加法器( c l a ) 取代了以日口的实现方案中所必需的进位传播 加法器( c p a ) 和两个进位存储加法器( c s a ) 中的一个，这样就减 少了m o n t g o m e r y 模乘器的面积； c )与此同时，使r 比大两位，从而在循环结束后不经过最后的比较就 可以得到模乘的结果，极大的简化了电路的复杂度： d )并且，我们利用r l ( r i g h t t o l e f t ) = 进制方法设计了一个1 0 2 4 位豹 r s a 专用集成电路。 此外，s r c m o s 电路具有较低的功耗、较快的开关速率、以及与等效静态 电路相比具有较小的面积等特点，所以我们可以得到具有较高性能的r s a 专用 集成电路。 本文的前两章简要介绍了r s a 公钥密码算法的相关背景知识及其理论基 m 摘要 础。从第三章开始到第五章，详细介绍了我们是如何利用上面的方案设计一个 1 0 2 4 一b i tr s a 专用集成电路的。最后一章给出了s r c m o s 电路单元的相关特性、 6 4 _ b i t 先行进位加法器的相关电路参数，以及所实现的r s a 专用集成电路的一些 主要仿真数据。仿真结果表明：我们所设计的r s a 专用集成电路完全达到了预 期的性能。 a b s t r a c t a b s t r a c t w i t ht h ei n c r e a s ei nd a t ac o m m u n i c a t i o na n dt h ee x p a n s i o no fi n t e r n e ts e r v i c e s l i k e p e r s o n i d e n t i f i c a t i o na n de l e c t r o n i cc o m m e r c e ，s e c u r i t yp r o b l e mh a sb e c o m e i m p o r t a n to v e rt h en e t w o r k o n ee f f i c i e n ts o l u t i o nt og u a r a n t e ei t ss e c u r i t yi sp u b l i c k e yc r y p t o s y s t e m r s ai s t h em o s tp o p u l a rp u b l i ck e ye n c r y p t i o ns c h e m ea n di s w i d e l yu s e d i ti st h em a i no p e r a t i o no ft h er s ac r y p t o s y s t e mt oc o m p u t em o d u l a r e x p o n e n t i a t i o nb yr e p e a t e dm o d u l a rm u l t i p l i c a t i o n s h o w e v e r , t h el a r g e b i to v e r 10 2 4 一b i tm o d u l a ro p e r a t i o nm a k e st h er s a c r y p t o s y s t e md i f f i c u l tt oi m p l e m e n t f o r s o l v i n gt h i sp r o b l e m ，m o n t g o m e r y sm o d u l a rr e d u c t i o na l g o r i t h mi su s u a l l ya d o p t e d f o rm o d u l a r m u l t i p l i c a t i o n f o rp e r f o r m a n c ea sw e l la sf o rp h y s i c a ls e c u r i t yr e a s o n s ，i ti so f t e na d v a n t a g e o u s t or e a l i z et h er s ac r y p t o s y s t e mi nh a r d w a r e b u ts o m ep r o b l e m sa p p e a ri nt h e h a r d w a r ei m p l e m e n t a t i o no fr s a a l g o r i t h m ：f i r s t ，f o rt h el i m i to ft h ec o m p u t a t i o n s p e e d i ti so n l yu s e dt oe x c h a n g et h ec o m m u n i c a t i o nk e y s ，n o tt oe n c r y p to rd e c r y p t a l lt h em e s s a g ed u r i n gt h ec o m m t i n i c a t i o n s ；s e c o n d ，r s aa l g o r i t h mn e e dt od ol a r g e b i tm o d u l a r c o m p u t a t i o n ，s o t h ep u b l i ck e y so v e r10 2 4 一b i ta r en e e d e dt og u a r a n t e et h e b u s i n e s ss e c u r i t yi nt h ef u t u r e t or e d u c et h eo p e r a t i o nt i m ea n dt oi m p r o v et h ee f f i c i e n c yo ft h ec h i p ，w ed o s o m e i m p o r t a n tw o r k ： a ) w ep r e s e n t an e wv e r s i o no f m o n t g o m e r y s m o d u l a r m u l t i p l i c a t i o n a l g o r i t h ma d a p t t oh a r d w a r ei m p l e m e n t a t i o n b 1a n ds u b s t i t u t ea6 4 - b i tp a r a l l e lc a r r yl o o k a h e a db i n a r ya d d e ri m p l e m e n t e d b ys r c m o s ( s e l f - r e s e t t i n gc m o s ) c i r c u i t sf o rt h ec p a a n do n eo ft h et w o c s a s ，w h i c ha r en e e d e di nt h ep r e v i o u si m p l e m e n t a t i o n t h i sr e d u c e st h e a r e ao f m o n t g o m e r y m o d u l a r m u l t i p l i e r c ) t h u sw e c a n g e tt h em o d u l a rm u l t i p l i c a t i o nr e s u l ta f t e rt h el o o pw i t h o u tt h e v a b s t r a c t f i n a lc o m p a r i s o na c h i e v e db ym a k i n gt h es i z eo f ，t w ob i t sl a r g e rt h a nt h a t o fn t tm a k e sag r e a to fr e d u c t i o ni nt h ec o m p l i c a t i o no fr s a h a r d w a r e i m p l e m e n t a t i o n d ) a n da l s ow ed e s i g na10 2 4 - b i tr s a a s i cb a s e do nt h er l ( r i g h t t o l e f t ) b i n a r ym e t h o d i na d d i t i o n ，s r c m o sc i r c u i t sh a v el o w e r p o w e r ，f a s t e rs w i t c h i n gs p e e da n dl e s s a r e at h a ne q u i v a l e n ts t a t i cc m o s i m p l e m e n t a t i o n s ，s o w ec a ng e ta h i g hp e r f o r m a n c e r s aa s i c t h i sp a p e ri s o r g a n i z e da sf o l l o w s t h eb a c k g r o u n da n df u n d a m e n t a lo fr s a c r y p t o s y s t e ma r ep r e s e n t e di nt h ef i r s tt w os e c t i o n s i nt h et h i r dt of i f t hs e c t i o n ，i t i s i l l u m i n a t e dh o ww e d e s i g na10 2 4 一b i tr s a a s i ci nt h ea b o v ea r c h i t e c t u r e t h ef i n a l s e c t i o n p r e s e n t s t h ef e a t u r e so ft h es r c m o sc i r c u i t s ，t h e6 4 一b i t p a r a l l e lc a r r y l o o k a h e a da d d e ra n dt h er s aa s i c t h ee x p e r i m e n tr e s u l t ss h o wt h a tt h er s aa s i c d e s i g n e db y u sh a st h ep r o p o s e df e a t u r e s v 1 第一章绪论 第一章绪论 随着通信网络的迅猛发展以及因特网的同益普及，它们在不同领域的应用 几乎涵盖了人类生活的方方面面，其中包括一些非常重要的领域，例如：个人 身份认证和电子商务。因此，网络安全成为越来越重要的课题。基本的安全要 求包括认证、鉴别、数据完整性和不可否认性。此外，由于电子身份证和银行 信用卡正在得到同益普及，也向科研人员提出了一个难题：如何i 能以较低的 成本有效地保护用户的个人信息不被他人非法获取，同时又能能用户方便快捷 地完成同常生活中的各项事务? 一种有效的安全解决方案是公钥密码算法。在 各种公钥密码算法中，r s a 公钥密码系统是现在最有效、用途最多、并被广泛 使用的公钥密码系统之一。 由于性能、以及物理安全的原因，通常利用硬件实现r s a 密码系统。臼j u ， r s a 算法硬件实现的主要瓶颈是芯片的速度和芯片的面积。由于速度的限制， r s a 算法现在只用来交换通信密钥，而无法对通信中的所有消息进行加解密： 这样，通信系统中还必须增加对称加密模块，利用公钥加密模块传送的密钥对 所传递的消息进i ? d i i 解密，这就增加了系统的成本。如果能够加快r s a 算法 的硬件实现速度，简化系统的设计，则可以极大的降低系统的成本。酊儿， 片面积的减小，同样会降低整个系统的成本。r s a 芯片一在向高速、低功耗、 小面积的方向发展。 第一节r s a 算法的提出 公丌密钥密码( 简称公钥密码，又称非对称公钥密码) 是现代密码学中最 重要的研究内容之一。密码学，其一般理解就是保护信息传递的机密性，但这 仪仅是密码学研究的一个方面。对信息发送人的身份认证以及信息完整性的检 验是密码学研究的另一个方面。公钥密码很好地解决了这两方面的问题，并j f 在产生许多新的思想和方案。与公钥密码相对应的是传统密码( 又称对称密钥 密码) 。在传统密码中，用于加密的密钥与用于解密的密钥完全相同。因此，通 第一章结论 常使用的传统加密算法比较简便、高效，密钥简短、安全性高。但是传送和保 管密钥是一个严峻的问题。 公钥密码的观点是由d i f i l e 和h e l l m a n 于1 9 7 6 年在他们的论文“n e w d i r e c t i o n si nc r y p t o g r a p h y 【1 1 ”一文中首次提出的，它使密码学发生了一场变 革。d i f i l e 和h e l l m a n 为解决密钥管理问题，提出了种密钥交换协议，允许在 不安全媒体上通信的双方交换信息，安全地达成一致的密钥。在此新思想的基 础土，很快出现了公钥密码。在公钥密码中，加密密钥不同于解密密钥，加密 密钥公之于众，谁都可以使用。解密密钥只有解密人自己知道，分别称为公丌 密钥( 简称公钥) 和解密密钥( 简称私钥) 。在至今为止的所有公钥密码中，最 著名的是由r r i v e s t ，a s h a m i r 和l a d l e m a n 于1 9 7 8 年提出的r s a 1 2 1 ( r s a 的耿名就是来自这三位发明者的姓的第一个字母) 。r s a 之所以具有安全性， 是基于数论中的一个事实：将两个大的素数合成一个大数很容易，f | j 相反过程 则j 常困难。由此可见，r s a 的安全性依赖于作为公钥的大数的位数。 第二节国内外研究的概况和发展趋势 由于性能、以及物理安全的原因，通常利用硬件实现r s a 密码系统。在 r s a 的加密过程中，其主要操作是通过重复的模乘运算来计算模幂。然而，大 到1 0 2 4 b i t 的大位数模操作使得r s a 硬件密码系统很难实现。为了解决这问 题，通常采用m o n t g o m e r y 算法进行模乘运算。目前，对m o n t g o m e r y 模乘算法 的改进及相应的硬件实现主要有= i 种方案 1 3 1 1 1 4 1 1 5 ：l - r 模、r - l 模、 脉动阵列。( 我们将在第三章详细介绍m o n t g o m e r y 模乘算法以及各种对 m o n t g o m e r y 算法的改进和实现方案。) 表1 1 三种方案在”= 1 0 2 4 时的基本指标 指标l r 模式r l 模式脉动阵列 等效门数 9 2 k1 5 6 k1 0 m 时钟周期数1 6 m ( 平均) 1 1 m 2 2 m ( 最坏) 第一章绪论 在月= 1 0 2 4 的情况下，上述三种方案的基本指标如表1 1 所示。通过这三种 实现方案的基本指标来看：对于1 0 2 4 b i t 的r s a 算法，脉动阵列方案需要的门 数太多，面积太大：对于l r 和r l 两种模式，r l 模式平均运算速度快，但 是芯片面积大，而l r 模式则相反。综合考虑运算时| 匐r 与芯片面积a ( 即a t 值) ，r l 模式具有一定的优势，并且实现速度较快；因此，我们倾向于选择 r l 模式的m o n t g o m e r y 模幂算法。 目前，根据上述三种对m o n t g o m e r y 模乘运算的改进算法，已经提出了多 种r s a 密码系统的硬件实现方案，如表】2 所示。 表1 2 最近发表的r s a 芯片实现情况 时钟 门电路数( 等每芯片时钟周期数比特率 没汁年份f ：艺频率 效r 与1 f fj )位数 ( 5 1 2t , 7 )( b i t s s e c ) ( h z ) v i c t o r 6 】 1 9 9 47 5 k5 1 20 2 5 m“n2 5 m1 0 0 k 0 5 u m n 下丁 】7 】 】9 9 41 0 5 k1 0 2 41 m4 0 m2 0 k fj 阵列 c h e n 【1 5 】 1 9 9 57 7 k 5 1 2l0 5 m 0 8 t t m5 0 m2 43 k y a n g m 8 】 1 9 9 8 7 4 k5j 205 4 m0 6 “m1 2 5 m8 k g u o 【1 9 】 1 9 9 91 3 2 k5 1 20 6 9 m1 4 3 m2 7 8 k f a n g 1 0 】 2 0 0 】9 6 k 5 1 20 】8 m 0 6 1 2 m 4 0 m1 1 3 k o8 m ( 平均)3 l3 k 9 2 k ( l r )05 9 m k v o n 3 】 2 0 0 l1 0 2 4i j m ( 最埘、)5 0 m2 27 k s o g l5 6 k ( r l )0 5 5 m4 55 k 从表中可以看出：由于大位数模运算的难于实现，r s a 密码系统的硬件实 现基本上都是5 1 2 b i t 的：而出于商业安全的考虑，为了保证未来一段时间内的 信息安全，至少应采用1 0 2 4 b i t 的r s a 密码系统。为此，我们希望：通过对现 有的r s a 实现方案作进一步的改进( 其中，m o n t g o m e r y 模幂运算拟采用r - l 模式) ，在实现1 0 2 4 一b i t 的r s a 专用集成电路的同时，进一步降低芯片的a t 值。 3 第一帝绪论 第三节选题依据和拟解决的问题 随着通信网络的迅猛发展以及因特网的日益普及，它们在不同领域的应用 几乎涵盖了人类生活的方方面面，其中包括一些非常重要的领域，例如：保密 通信、个人身份认证和电子商务。因此，网络安全成为越来越重要的课题。一 种有效的网络安全解决方案是公钥加密算法。在各种公钥加密算法中，r s a 公 钥密码系统是现在最有效、用途最多、并被广泛使用的公钥加密体系之一。出 于商业安全的考虑，为了保证未来一段时间内的信息安全，至少应采用1 0 2 4 一b i t 的r s a 密码系统。 此外，由于电子身份证和银行信用卡正在得到日益普及，也向科研人员提 出了一个难题：如何爿+ 能以较低的成本有效地保护用户的个人信息不被他人非 法获取，同时又能能用户方便快捷地完成同常生活中的各项事务? 以上这些都对r s a 密码芯片的研制提出了更高的要求。但是，在r s a 算 法的硬件实现过程中，出现了许多难以解决的问题：其一，由于硬件运算速度 的限制，r s a 算法现在只能用来交换通信密钥，而无法对通信中的所有消息进 行加解密，使得通信系统中还必须增加对称加密模块( 它利用公钥加密模块传 送的密钥对所传递的消息进行加解密) ；其二，r s a 算法中需要对大位数进行 模乘运算，而为了在未来一段时i 目内保证信息的安全，要求公钥n 具有多达1 0 2 4 位二二进制) 的位数，这样就需要大量的存储器件和运算单元，致使芯片面积 增人、功耗上升。这些都极大的增加了整个系统的成本。 为了解决这些问题，在进f j ：模乘运算的时候通常采用m o n t g o m e r y 模乘算 i i 。通过对已有的几种硬件实现方案的综合比较，我们改进了其中的一些不足 之处：利用一个并行前缀结构的先行进位加法器取代以f ；i 的实现方案中所必需 的进位传播加法器( c p a ) 和两个进位存储加法器( c s a ) 中的一个，并利用 具有高速、低功耗的s r c m o s ( s e l f - r e s e t t i n gc m o s ) 电路设计了该加法器。我 们希望通过以上改进，使得所设计的r s a 专用集成电路具有较小的面积、较低 的功耗和较高的工作频率。 第一章绪论 第四节研究方案和内容安排 一、研究方案 为了减少运算时间、提高芯片的有效性，我们将对m o n t g o m e r y 模乘算法 作进一步的改进，同时利用s r c m o s ( s e l f - r e s e t t i n gc m o s ) 电路实现的6 4 七i t 并行二进制先行进位加法器( c l a ) 取代以前的实现方案中所必需的进位传播 加法器( c p a ) 和两个进位存储加法器( c s a ) 中的一个。这样，当计算 肼。r o o d n 的时候，我们可以在进行循环c ，s = c + s + q 之前预计算j ，+ v 的 值，然后根据一，y o ，岛，s o 的真实值从】，y + 和0 中选择9 的值；同时使，比 火两位，从而在循环结束后不经过最后的比较就可以得到模乘的结果。此外， s r c m o s 电路具有低功耗、较快的开关速率、以及与同等的静态电路相比具有 较小的面积等特点。因此，我们可以利用r l ( r i g h t t o l e f t ) 二进制模式设计一 个】0 2 4 一b i t 的具有较高性能的r s a 密码系统。 为了验证设计的币确性，我们将采用0 6 1 a mc s m ( 新加坡特许半导体公司) 工艺在s u n 工作站上利用c a d e n ce d a 软件完成相关电路的绘制，同时利用 h s p i c e 仿真软件对所绘制的电路进行仿真，以便检测我们所设计的r s a 专用 集成电路是否达到了预期的效果。 二、主要内容及安排 本章简要介绍了r s a 公钥密码算法及其产生的背景。r s a 公钥密码算法 被广泛地使用在信息安全的各个领域，因此产生了各种不同的应用。通过对现 有的r s a 公钥密码系统实现方案的比较，我们提出了相应的改进方案，希望能 够在功快芯片速度的同时，尽可能减少芯片的面积，以获得较优的a t 值。 下一章将通过对其理论基础的阐述进而证明了该算法的正确性。 第三章将详细介绍m o n t g o m e r y 模乘算法以及到目前为止人们对该算法所 做的一些主要改进。通过对几种改进方案的比较，我们指出了其存在的不足， 并对其做了进一步的改进，从而提出了我们实现m o n t g o m e r y 模乘运算的新方 法。同时，我们也详细介绍了r s a 算法硬件实现时所采用的几种方案，通过对 5 第一章绪论 这几种方案的比较，我们选择了运算速度较快的r l 模式。 第四章详细介绍了s r c m o s ( s e l f - r e s e t t i n gc m o s ) 电路单元的构成以及利 用这种电路实现的6 4 - b i t 并行二进制先行进位加法器( c l a ) 。第五章阐述了如 何利用第二章提出的改进后的m o n t g o m e r y 模乘算法实现r s a 专用集成电路。 最后一章给出了s r c m o s 电路单元的相关特性、6 4 _ b i t 先行进位加法器的 相关电路参数，以及所实现的r s a 专用集成电路的一些主要仿真数据。通过对 仿真结果的分析可以看出：我们所设计的r s a 专用集成电路完全达到了预期的 性能。 6 第二章r s 算法的理论基础及其证明 第二章r s a 算法的理论基础及其证明 r r i v e s t ，a s h a m i r 和l a d l e m a n 三位教授在他们的论文“am e t h o df o r o b t a i n i n gd i g i t a ls i g n a t u r e sa n dp u b l i c k e yc r y p t o s y s t e m s 1 2 】”中详细介绍了 r s a 算法的具体实现过程。这一章我们将简要介绍r s a 算法的基本原理，并通 过对其理论基础的阐述进一步证明了该算法的正确性。 第一节r s a 算法简介 一、r s a 算法简介 为了采用r s a 算法加密消息m ，需要使用公开加密密钥对0 ，n ) ( 此处，p 和是一对正整数) ，加密过程如下。 首先，将消息表示为o 和n l 之间的一个整数( 将长文件分割成一系列的 模块，把每个模块表示成一个这样的整数) 。这样做的目的不是加密消息而是将 消息转化成加密所需的数值形式。 然后，通过将所得整数的e 次幂对取模来加密消息。也就是说，结果( 密 文c ) 是膨。除以的余数。 为了解密密文，先求密文的d 次幂，再模。 加密算法e 和解密算法d 分别为： c z e ( m ) s m ( m o d n ) ( 1 1 ) m ；d ( c ) ；c 。( m o d n ) ( 1 2 ) 此处，m 指消息，c 指密文。 注意：加密过程并不增加消息的大小，消息和密文都是0 到n 一1 之间的整 数。 这样，加密密钥是正整数对0 ，) 。同理，解密密钥是正整数对0 ，n ) 。每 个用户公开他的加密密钥，并对相应的解密密钥进行保密。( 因为每个用户都有 7 第二章r s a 算法的理论基础及其证明 自己的整数集，所以这些整数应该被正确地描述为n 。，和叱。然而，我们将 仅仅考虑典型的整数集，而忽略下标。) 在r s a 算法中，加密密钥和解密密钥的选择方法如下： 首先要计算，它是两个素数p 和g 的乘积： n = p + q ( 1 3 ) 这些素数是大的、“随机”的素数。尽管必须公开，但是分解的极端困 难性使得因子p 和g 对其他人具有良好的隐藏性。这同时也隐藏了从p 中求出d 的途径。 然后，挑选一个大的、随机”的整数d ，使它与妒( ) 互质。 妒( ) = 0 一1 ) ( j 一1 ) ( 1 4 ) 即检测d 是否满足： g c d ( d ，0 1 ) 0 1 ) ) = 1 ( 1 5 ) 其中，妒( ) 是欧拉中函数，g o d 意即最大公约数。 最后，整数e 从p ，g 和d 中计算得到，即d 的“乘法逆元”( 计算方法详见 第二章) 对0 1 ) q 1 ) 取模。这样，我们得到 p + d z l ( m o d ( p 1 ) + ( g 一1 ) ) ( 1 6 ) 二、算法举例 这里，我们举一个简单的例子来解释r s a 算法的计算过程【1 2 】。 假定p = 4 7 ，g = 5 9 ，n = p + g = 4 7 * 5 9 = 2 7 7 3 ，d = 1 5 7 。贝0 ( o ( 2 7 7 3 ) = 4 6 * 5 8 = 2 6 6 8 ，可以通过求乘法逆元的方法计算出p ( 详见第二节) ： x o = 2 6 6 8 ，a o = 1 ，6 0 = 0 ， 而= 1 5 7 ，口l = 0 ，b l = 1 ， z 2 = 1 5 6 ，a 2 = l ，b 2 ；一1 6 ，( 1 酗2 6 6 8 = 1 5 7 + 1 6 + 1 5 6 ) x 3 = 1 ，a 3 = 一i ，6 j = 1 7 ，( 因为1 5 7 = 1 1 5 6 + 1 ) 0 第二章脚算法的理论基础及其证明 因此，d = 1 5 7 的乘法逆元e = 1 7 。 利用n = 2 7 7 3 ，我们可以一次加密一个含有两个字母的模块。利用两位十 进制数分别表示每个字母：b l a n k = 0 0 ，a = 0 1 ，b = 0 2 ，z = 2 6 。这样， 消息“i t s a l l g r e e k t o m e ”可以编码为： 0 9 2 01 9 0 00 11 21 2 0 00 7 1 80 5 0 5l1 0 02 0 1 50 0 1 30 5 0 0 由于利用二进制表示时，p = 1 0 0 0 1 ，第一个模块( m = 9 2 0 ) 可以加密为： m ”= ( ( ( “1 ) 2 m ) 2 ) 2 ) 2 ) 2 m = 9 4 8 ( m o d 2 7 7 3 ) 整个消息可以加密为： 0 9 4 82 3 4 210 8 41 4 4 42 6 6 32 3 9 00 7 7 80 7 7 40 2 1916 5 5 第二节r s a 的理论基础 、同余及模运算 2 1 2 2 同余：假定有三个整数a ，b 及，| ( ”0 ) ，我们称a 在模n 时与b 同余，当 且仅当a 与b 的差为玎的整数倍，即a b = m ，其中七为任一整数。若a 与b 在 模”中同余，我们可写为a ；b r o o d n 或n 0 一b ) 。 剩余类( r e s i d u ec l a s s ) ：很明显地，利用同余概念，所有整数在模n 中被 分成n 个不同的剩余类；为n 所整除的数为一剩余类，被n 除余数为i 的数为一 类，余2 的数为一剩余类，以此类推。若将每一剩余类中取一数为代表，形成一 个集合，则此集合称为模，l 的完全剩余类( c o m p l e t e s e to f r e s i d u e s ) ，以z 。表示。 很明显的，集合f 0 ，1 ，2 ，n 一1 为模n 的一个完全剩余类。 从0 到n l 的整数缀成的集合构成了模一的“完全剩余系”。这意味着，对 每一个整数a ，它的模月剩余是从o 到n l 之间的某个整数。运算口m o d n 表示求 口被n 除的余数，称为模撑运算。 0 + b ) m o d n = ( ( 口r o o d n ) + ( b m o d n ) ) m o d n 舢( a - b ) m o d n c ) m o d n 二( 怖( a b r o 幽o d n 卜) + 翟m 幽o d 舳n ) ) m m o d n ( 2 1 ) a ( 6 + = “ a b m o d n = ( a m o d n x b m o d n ) m o d n 9 第二章r s a 算法的理论基础及其证明 模算术同普通的算术一样，是可交换的、可结合的和可分配的。而且，模行 运算的每一个中间结果，与先进行全部运算，再对最后的结果模一，其作用是一 样的。 即约剩余类( r e d u c e ds e to f r e s i d u e s ) ：在模一的完全剩余类中，若将所有 与n 互素的剩余类形成一集合，则此集合称为模一的即约剩余类，以乏表示。 二、素数 2 1 素数是指一个大于1 且因子只有1 和它本身的整数。没有其它数可以整除它。 素数有无限多个。密码学，特别是公钥密码学，要用到大素数( 5 1 2 b i t ，甚至更 大) 。 三、最大公因子 2 1 如果有两个数，它们除l 之外没有其它共同的因子，则称这两个数是互素的。 换言之，如果整数a 和玎的最大公因子( g c d ) 等于l ，则记为g c d ( a ，月) = 1 。 一个素数与它的倍数以外的任何其它数都是互素的。计算两个数的最大公因 子最容易的方法是古老的e u c l i d e a n 算法。k n u t h 在参考文献【2 3 】中描述了这个 算法及现代所做的一些改进。 四、单向函数和单向t l f i f - 函数 2 2 公钥密码的思想与单向函数的概念密切相关。d i f f i e 和h e l l m a n 提出公钥密 码系统的概念时，他们并未能提出一个真正可以实现的公钥密码系统，只是推测 公钥密码系统“可能”存在。为了说明公钥密码系统可能存在，d i f f i e 和h e l l m a n 提出了单向函数及单向陷门函数的定义。 单向函数( o n e - w a y f u n c t i o n ) ： 定义：一函数若满足下列二条件，则厂称为单向函数。 ( 1 ) 对于所有属于，定义域的任意x ，可以很容易算出i ( x ) = y 。 ( 2 ) 对于几乎所有( a l m o s ta 1 1 ) 属于，值域的任意y ，则在计算上 l o 第二章r s a 算法的理论基础及其证明 不可能( c o m p u t a t i o n a l l y i n f e a s i b l e ) 求出x 使得y = z ( x ) 。 单向陷门函数( o n e - w a yt r a p d o o r f u n c t i o n ) ： 定义：一“可逆”函数f 若满足下列二条件，则f 被称为单向陷门函数。 ( 1 ) 对于所有属于f 定义域的任意x ，可以很容易算出f g ) = y 。 ( 2 ) 对于几乎所有属于f 值域的任意j ，则在计算上除非获得陷门， 否则不可能求出x ，使得x = f 。c v ) ，f 。1 为f 的反函数。但若 有一额外数据z ( 称为陷门) ，则可以很容易求出x = f “( y ) 。 公钥密码的原理就是基于单向陷门函数的，加密是容易的方向，加密指令是 公钥，任何人都能加密信息。而解密是难的方向，它设计得非常困难，以至于若 没有秘密信息，使用最快的计算机几百万年的时间都不能揭开加密信息。秘密信 息即陷门就是私钥。 五、欧拉函数( e u l o rp h i f u n c t i o n ) 2 4 定义：假定玎是一个正整数。欧拉中函数伊0 ) 定义为小于 并与拧互质的非 负整数6 的个数：妒o ) 云6 ”i g c d ( 6 ，甩) = 1 1 。 容易看出：伊( 1 ) = 1 ，对任何素数p 有妒) = p i 。我们也可以得出：对于 任何素数幂，有妒0 4 ) = p 。一p ”l = p 8 ( 一吉) 。 为了证实这一点，我们可以注意到从0 到p 。一1 的不与p 4 互质的数正好是 能被p 整除的数，共有p ”1 个。 欧拉d 函数有一个乘法特性：如果给定一的素数因子，则可以快速计算伊o ) 。 也就是，如果，l 写为明显的素数幂的形式p a ，则可以证明妒o ) 等价于矿0 8 ) 。 六、费尔玛小定理( f o r m a t sl i t t i et h e o r e m ) 2 4 假定p 是素数。任何整数口满足：a s a m o d p ；任何不被p 整除的整数口满 第二章r s 算法的理论基础及其证明 足：a 川i l m o d p 。 证： 首先，假定p 不能整除口。我们首先声明：整数。口，l a ，2 a ，3 a ，0 1 k 是对p 取模所得余数的全集。为了证明这一点，我们发现：另一方面，全集中的两个， 假定为蛔和归，不得不在相同的余数类里，例如，蛔；j a m o d p 。但是，这就 意味着p l ( 一，k ，因为a 不能被p 整除，我们就得到p f 一- ，。因为ij 释j j 都小于 p ，唯一能够使其发生的情况是：i = - ，。我们得出结论：整数a 仅仅是考虑对p 取模时l 2 ，p 一1 的重新排列。这样，接着可以证明：第一序列的数字对p 取模 的产物恰好是第二序列数字的产物，例如，a p - 1 0 一l ，s 0 1 ) m o d p 。这样， p i b 一1 ) 0 川一1 ) ) 。因为0 一l ，不能被p 整除，我们得到所需要的p i g 川一1 ) ， 最后，如果我们在等式a 川si m o d p 两边同时乘上口，我们得到命题描述的第一 个一致性，此时a 不能被p 整除。但是如果a 能被p 整除，则这个一致性 a ”= a m o d p 是微不足道的，因为两边是a z o m o d p 。 证毕。 七、乘法逆元的求法 2 2 求解乘法逆元即求解问题：已给疗及胆，且( 口， ) = 1 ，如何求伽= 1 m o d n 7 方法一：若伊0 ) 已知，则由欧拉定理可知册，加卜j = i m o d n 。 因此，口p ( “ 1 = a 一1 m o d n ( 注意：若以为素数，则妒o ) = 疗一1 为已知。若n 为 合数，则缈o ) 不一定为己知) 。 方法二：利用欧几里德算法( e u c l i d e a n a l g o r i t h m ) 首先，利用欧几里德算法求g c d 的方法： 令r o = 行，= 口，h a ，利用辗转相除法可得 第二章r s a 算法的理论基础及其证明 0 s 吩 0 r 2 0 22 ，：一i g i + ，：0 r j ，：，一1 0 2 = 一1 9 _ - 1 + 0 ，m ，m 一1 一i2 g m 则0 为a 及栉的最大公因子。欧几里德算法求g c d 的主要概念在于；若 c = 幽+ ， ， 则( c ，d ) - - 0 ，) 。因此在上述算法中， 0 ，胛) = ( ，0 ，) = “，吒) 一一“+ ) = 以，o ) = 。欧几里德算法也可以求出两个 整数s 及f 使得s 口+ t n = ( 口，行) ( 注意j 及，并非唯一) 满足上述者我们称为( 口，盯) 为 口和n 的线性组合。 其方法为= 0 ，行) = 一：一。一g 。，因此q ，h ) 为，埘：及_ 一，的线性组合。 由于0 一j = 一3 0 2 岛一2 ，代入上式得 a ，n ) = ，：，卜2 一眈一3 一，_ 一2 9 。一2 k 。一i = ( 1 + g ，一i g ，一2 h 一2 一g 。一i _ 一3 因此g ，聍) 为一：及。的线性组合。以此反推回去，我们可得( a ，n ) = s o + t n 。 若0 ， ) = 1 ，则1 = s 口+ m 。所以s 口= i m o d n ，因此5 = 0 m o d n 。 k n u t h 已证明：利用欧凡里德算法求模珂的乘法逆元，平均约需 0 8 4 3 i n ( n ) + 1 4 7 次除法。而利用方法一的欧拉定理，平均约需1 5 l o g ：行一2 次乘 法。因此，求乘法逆元以方法二为较佳。 第三节r s a 算法的证明 1 2 现在，我们利用欧拉中函数和费尔玛小定理来阐述r s a 解密算法的正确性。 对于任意一个与互质的整数( 消息) m ，有 m 9 ( ) l ( m o d n ) 。 ( 2 2 ) 1 3 第二章r s a 算法的理论基础及其证明 其中，矿( ) 是欧拉中函数。对于素数p ，伊( p ) = p - 1 。 利用西函数的基元特性，我们可以得到： 妒0 v ) = 妒0 ) 矿( g ) = 如一1 ) ( g i ) = 一0 + g ) + l ( 2 3 ) 因为d 与尹( ) 互质，在对妒( ) 取模的整数中，它有一个乘法逆元p ： p + d ；l ( m o d 口o ( n ) ) ( 2 4 ) 我们现在证明等式( 1 1 ) 和( 1 2 ) 成立( 即：如果如上选择e 和d ，则解 密能够正确工作) 。我们可以得到如下等式： d 陋似) ) s 仁妒z 似。，sm “( r o o d n ) ( 2 5 ) e ( d ( m ) ) ；( d 妒= 似4 ，sm 9 4 ( m o d n ) ( 2 6 ) 以及 m “= m 尹似h ( r o o d n ) ( k 是整数) ( 2 7 ) 从等式( 2 2 ) 我们可以看出：对于所有不能被p 整除的m ，m 川= l ( m o d p ) ； 并且，因为0 1 ) 能整除妒( ) ，有 m p 似sm ( m o d p 、( 2 8 ) 当m ；o ( m o d p l ，这同样是正确的，所以这个等式对所有肘都成立。 总之，最后两个等式意味着对于所有的m ，有m “= m ”，竹 ；m ( m o d n ) 。 这表明：对所有的m ，0 m n ，( 1 1 ) 和( 1 2 ) 都成立。因此，e 和d 互为逆置换。 第四节r s a 密码系统的参数选择 2 1 r s a 公钥密码系统是第一个将安全性植基于因子分解的系统。很明显的，在 公丌密钥0 ，) 中，若n 能被因子分解，则在模中所有元素阶的最小公倍数( 即 所谓陷