（计算机软件与理论专业论文）密码分析中几种方法的研究及其设计与实现.pdf

摘要 密码学包括两部分，即密码编码学和密码分析学，这两个部分即对立又 统一，正是由于其对立性才促进了密码学的发展。一个密码系统的安全性 只有通过对该系统抵抗当前各类攻击能力的考查和全面分析才能做出定 论。密码体制的安全性分析是一个相当复杂的问题，但有一点是清楚的， 那就是掌握现有的分析方法并使用这些方法对相应的体制进行分析以考察 其安全强度。 本文主要讨论密码分析的方法，大体上从古典密码、对称密码、非对称密码 这三种加密方法方面进行分类，并重点对穷举密码分析法、线性密码分析法、因 式分解法进行探讨。目前，密码分析在理论上已有了很深的发展，但将密码分析 方法实现并用于实践中还有一定的局限性。在我们的设计中，综合了多种当前比 较典型且常用的密码分析方法，每一种方法分别针对某一种加密方法，而且可根 据不同的加密方法及收集到的密文信息量进行判断、选择合适的解密方法进行解 密。我们主要设计实现了穷举密钥分析法、穷举明文分析法、线性分析法、因式 分解法这四种密码破译方法。穷举密钥分析法主要是用k a s i s k i 测试法和重合指 数法对v i g e n e r e 加密方法进行解密，对h i l l 密码加密方法则用的是穷举明文法， 线性分析法是对d e s 加密方法进行破译的主要方法，本系统能成功的破译五轮 d e s 加密方法，因式分解法是利用数学中因式分解原理对r s a 加密方法中大数 n 进行强性分解，将其分解为两个质数p ，q ，结合加密密钥e 勰出解密密钥d 。 由于时间的原因，其它的方法还有待于进一步完成。 本设计的实现不但为其理论研究提供了一种手段，而且为密码分析提供了实 践上的应用，既可以进行破译分析也可以作为一个密码分析的( 辅助) 工具。 关键词：密码学，密码分析，密码编码 a b s t r a c t c r y p t o g r a p h yc o n s i s t so fe n c r y p t i o na n dc r y p t a n a l y s i s ，t h e ya r ec o n t r a d i c t i o n b u tu n i f i c a t i o n , j u s tt h e i rc o n t r a d i c t i o ni m p r o v e dc r y p t o g r a p h y sd e v e l o p m e n t o n l y b yr e v i e w i n ga n da n a l y z i n gc o m p l e t e l yt h ec a p a b i l i t yt h a tt h es y s t e mk e e p sf r o m a l lk i n d so fa t t a c k s ，c a ni t s s e c u r i t y b e c o n c l u d e d s e c u r i t ya n a l y s i s o fa c r y p t o g r a p h i cs y s t e mi sr a t h e rc o m p l i c a t e d ，b u ti ti sv e r yi n t e l l i g i b l ef o rm a s t e r i n g e x i s t i n ga n a l y s i sm e t h o d sa n da p p l y i n gt h e m t or i g h ts y s t e mt or e v i e wi t ss e c u r i t y i n t e n s i t y t h i s p a p e r f i r s ti n t r o d u c et h e d e v e l o p m e n t ，c o n c e p t ，n e c e s s i t y a n d t h e o r y f o u n d a t i o no fe n c r y p t i o na n d c r y p t a n a l y s i s o n t h i s b a s e ，w em a i n l yd i s c u s st h e m e t h o d so f c r y p t a n a l y s i s ，t h e nc l a s s i f yt h em e t h o d sa p p r o x i m a t e l yb y t h r e ea s p e c t so f c l a s s i c a l c r y p t o g r a m ，s y m m e t r yc r y p t o g r a m a n d a s y m m e t r yc r y p t o g r a m i n t h i s p a p e r , w em a i n l ys t u d yl i n e a rc r y p t a n a l y s i sm e t h o d ，e n u m e r a t i o nk e yc r y p t a n a l y s i s m e t h o da n df a c t o r i z a t i o nm e t h o d a t p r e s e n t ，c r y p t a n a l y s i sh a sd e e p l yd e v e l o p e d ，b u t i t i sl i m i tt h a tr e a l i z ec r y p t a n a l y s i sm e t h o da n da p p l y i n gi ti np r a c t i c e i nt h i sd e s i g n ，w e i n t e g r a t e af e wt y p i c a la n du s e dc o m m o n l ym e t h o d s ，e v e r yo n ec o r r e s p o n dt oo n e e n c r y p t i o n ，a n dc a nj u d g ea n ds e l e c tp r o p e rm e t h o dt od e c r y p ta c c o r d i n gt od i f f e r e n t e n c r y p t i o n m e t h o da n dt h e q u a n t i t y o f c r y p t o g r a p h t h a th a sc o l l e c t e d f o u r c r y p t a n a l y s i sm e t h o d s h a v eb e e nr e a l i z e d ：e n u r n e m t i o nk e y c r y p t a n a l y s i s ，e n u m e r a t i o n p l a i n t e x tc r y p t a n a l y s i s ，l i n e a rc r y p t a n a l y s i sa n d f a c t o r i z a t i o nm e t h o d e n u m e r a t i o nk e y c r y p t a n a l y s i sm a i n l yd e c r y p tv i g e n e r ec r y p t o g r a p ht h r o u g h k a s i s k i t e s t i n g a n d r e - i n d e x ，w ea p p l ye n u m e r a t i o np l a i n t e x tc r y p t a n a l y s i sm e t h o dt oh i l lc r y p t o g r a p h ， l i n e a rc r y p t a n a l y s i sm e t h o dc a n d e c r y p td e s ，i n t h es y s t e m ，i tc a ns u c c e s s f u l l yd e c r y p t 5 - d e s ，g r e a tn u m b e r no fr s ai sf a c t o r i z e dt ot w op r i m en u m b e r spa n dq b yf o r c e t h r o u g hf a c t o r i z a t i o np r i n c i p l e ，t h e n 、i t l le n c r y p t i n gk e ye ，d e c r y p t i n gk e ydc a nb e a b t a i n e d d u et ot i m eb e i n g l i m i t e d ，o t h e rm e t h o d s i sh o p e dt or e a l i z ef u t u r e r e a l i z i n gt h i sd e s i g np r o v i d en o to n l yo n ew a y f o rs t u d y i n gi nt h e o r y , b u ta l s o a p p l i c a t i o nf o rc r y p t a n a l y s i si np r a c t i c e ，i t c ：a n a n a l y s ec i p h e ra n db er e g a r d e da sa ( a s s i s t a n t ) t o o lo fc r y p t a n a l y s i s t t k e y w o r d ：c r y p t o g r a p h y , c r y p t a n a l y s i s ，e n c r y p t i o n i y 6 2 3 7 8 4 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。据我所知，除了本文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的成果，也不包含为获 得西北大学或其他教育机构的学位或证书而使用过的材料。与我一同 工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明 并表示谢意。 西北大学计算机系硕士论文 学位论文作者签名：t 躬豫 签字日期： 如畸、6 叶 前言 密码学用于保护军事、外交通信等领域可追溯到几千年前。在当今的信息时 代，大量的敏感信息，如病例、法庭纪录、私人财产等，常常通过公共通信设施 或计算机网络来进行交换，而这些信息的秘密性和真实性是人们迫切需要的。因 此，现代密码学的应用已不再局限于军事、政治和外交，其商用价值和社会价值 已得到了广泛的重视。但在网络的大量应用中，网络信息的安全受到各种威胁， 如黑客攻击、计算机病毒、拒绝服务等，人们不得不加强网络信息的安全性，而 加密与解密是相辅相成的，相互促进的，因此密码分析学在密码学中也越来越受 到人们的重视。 在我国密码分析还处于初级阶段，由于软、硬件及技术等各种原因，大部分 密码分析方法还处于理论阶段。目前，已经出现了各种各样的密码分析系统，都 是针对某种加密方法进行分析的，功能和方法上还具有一定的局限性。在本设计 中综合了多种当前典型且常用的分析方法，进行密码分析时，可根据获得的密文 信息量，进行判断采用其中的某一种进行分析。由于时间关系，本系统只完成了 最常用的四种解密方法，穷举明文法、穷举密钥法、线性分析法、因式分解法。 其中穷举明文法采用k a s i s k i 测试法和重合指数法进行密钥位数的判断，然后再 在系统中利用密钥字典进行解密；穷举明文法的设计适合于解口令类密码：线性 分析法理论上可以破译1 6 轮d e s 加密，实践中单机是很难实现的，本系统中由 于开发环境所限，在单机上采用大数处理方法，用线性密码分析法实现了对五轮 d e s 密码的破译；在用因式分解法解密r s a 密码时，分解n 时不是对每个质数 进行尝试，而是采用取质数随机数法，这样使因式分解的速度提高了一倍。 在本文中介绍了密码分析的发展、概念、理论基础、分类等，并且对穷举法、 线性分析法、因式分解法进行了主要研究，并且在设计中得到了实现。 本文结构安排如下： 第一章主要介绍密码分析学的基础知识。 第二章对密码分析方法进行分类并重点对几种方法进行研究。 第三章对几种分析方法的设计与实现过程进行具体介绍。 第四章介绍密码分析方法的技术应用。 筻一章密码分析的基础知识 密码编码学和密码分析学是经典密码学的两个主要分支，两者相反相成，即 对立又统一，正是由于两者的对立性才促进了密码学的发展。本章主要介绍密码 分析的一些基础知识：密码学，密码分析学及其数学理论。 1 1 密码学 密码学是研究密码系统或通信安全的- - i q 学科，随着先进科学技术的应用， 已成为一门综合性尖端技术科学。 1 1 1 密码学中的基本概念【1 1 密码学主要包括密码编码学和密码分析学两个分支，密码编码学的主要目的 是寻求保证消息保密性和可认证性的方法，密码分析学的主要目的是研究加密消 息的破译和消息的伪造。 采用密码技术可以隐蔽和保护需要保密的消息，使未授权者不能提取信息也 不能篡改信息。被隐蔽的消息称作明文，隐蔽后的消息称作密文。将明文变换成 密文的过程称作加密，其逆过程，即由密文恢复出原名文的过程称作解密。对明 文进行加密操作的人员称作密码员。密码员对明文进行加密时所采用的一组规则 称作加密算法，传送消息的易定对象称作接收者，他对密文进行解密时所采用的 一组规则称作解密算法。加密和解密算法的操作通常都是在一组密钥控制下进行 的，分别称作加密密钥和解密密钥。在如图l - 1 模型所示： 图1 1 加密一解密的简化模型 在加密一解密的简化模型中，加密过程由加密算法和加密密钥组成，算法根 据所使用的密钥对发送方输入的明文进行加密，密文产生后就被传送出去。在解 密过程中，接收方通过使用解密算法和解密密钥，该密文被转换成最初的明文。 1 1 2 密码体制的分类 根据密钥的特点，s i m m o n s 将密码体制分为对称和非对称密码体制两种【2 】。 对称密码体制又称为单钥或私钥或传统密码体制，非对称密码体制又称双钥或公 钥密码体制。在本文中采用对称密码和非对称密码体制这两个术语。在对称密码 体制中，加密密钥和解密密钥是一样的。按加密方式又可将其分为序列( 流) 密 码和分组密码两种。在序列密码中，将明文消息按字符逐位加密，既一次加密一 个比特或一个字节。在分组密码中，将明文消息分组( 每组含有多个比特位或字 节) ，将明文消息逐组进行加密。在公钥密码体制中，加密密钥和解密密钥不同， 从一个难于推出另一个。现在大多数公钥密码属于分组密码。只有极少数公钥密 码属于序列密码，如概率加密体制就属于序列密码。下面分别对经典加密技术及 当今对称加密技术和非对称密码技术的加密原理进行介绍。 1 1 2 1 经典对称加密技术 经典加密技术虽然在当今的密码编码技术中已不太使用，但它还是密码学发 展的基础，研究这些技术有助于我们理解今天的对称加密基本方法、预料密码分 析攻击的类型。 有两个经典加密技术【3 】：替代和置换。替代技术是将明文的字母由其它字母 或数字或符号来替代，例如： 明文：m e e tm ea f t e rt h et o g ap a r t y 密文：p h h wp hd i w h uw k hw r j ds d u w b 替代公式为：密文字目= ( 明文字母+ 3 ) m o d ( 2 6 ) 当然替代公式多种多样，一般替代技术比这要复杂的多。如果明文是一个比特序 列，则替代也是用比特序列模式。采用替代技术的古典加密方法主要有：凯撒密 码，p l a y f a i e 密码，h i l l 密码、v i g e n e r e 密码等。 置换技术是对明文字母执行某种置换，取得一种类型与明文完全不同的映 射。这样得到的密码称为置换密码。例如：将明文“m e e tm ea f t e rt h et o g ap a r t y ” 以对角线顺序写下来，写成如下形式： me ma tr h t g p r y e t e f e t eoa a t 然后以行的顺序读出，既为密文： m e m a t r h t g p r y e ，r e f e t e o a a t 置换方法很多，这是一次置换，且简单，还可以执行多次置换的阶段，使用更复 杂的、不易被重构的排列，使被置换密码的安全性有很大的改观。置换加密技术 的古典方法有：栅栏技术，转子机加密技术等。 1 1 2 2 现代对称加密技术 常规密码编码学是对称的，加密与解密的密钥相同，其算法是基于替代与置 换技术。最常用的对称加密技术有：数据加密标准d e s 、国际数据加密算法i d e a 、 b l o w f i s h 加密算法、r c 5 、c a s t - 1 2 8 、r c 2 等。在加密解密方面分组密码比序 列密码的应用广泛，绝大部分的基于网络的对称加密应用都使用分组密码，以后 我们主要对分组密码进行讨论。 上面提到的几种对称加密算法原理 都是基于被称为f e i s t e l 分组密码【3 1 的结 构，f e i s t e l 密码结构如图1 2 所示： 第1 轮 加密算法的输入是一个长度2 w 比特 的明文分组和一个密钥k ，明文分组被 分为两个部分l 。和i 0 。数据的这两个部 分经过n 轮的处理后组合起来产生密文第i 轮 分组。每一轮i 以从前一轮得到的l 。 和r 。为输入，另外的输入还有从总的密 钥k 生成的子密钥k 。一般来说，予密 钥k ，不同于k ，它们彼此之间也不相同。 第蹴 每一轮的结构都一样。对数据的左边 一半进行替代操作，替代的方法是对数 据右边一半应用r o u n d 函数f ，然后用这 个函数的输出和数据的左边一半做异 l 或。r o u n d 函数在每一轮中有者相同的结 构，但是以各轮的子密钥k 。为参数形成 区分。在这个替代之后，算法做一个置 明文( 2 w 比特) 囝卜2h i = t e r 密l 骈构 4 换操作把数据的两个部分进行互换。 f e i s t e l 密码结构在具体实现时，对分组大小、密钥大小、循环次数、子密钥 产生算法、r o u n d 函数等的选择依赖性很大【4 卜 1 1 2 3 非对称加密技术 非对称加密技术【3 】与以前的所有方法都不同。其算法是基于数学函数，且非 对称密码编码学是非对称的，用到两个不同的密钥，一个密钥( 即公开密钥) 是 公开的，用于加密，另一个不同但有关的密钥( 即私有密钥) 是保密的，用于进 行解密，如图1 - 3 所示： 图1 3 非对称密码简化模型 终点b 产生一对密钥：私钥l ( i b ，公钥k u b ，并将k u b 公开。源点a 产生明文， 结合加密算法用k u b 对明文进行加密，产生密文并通过通信通道传送给b ，b 接收到密文后用匹配的私钥k r b 解密得到明文。 非对称密码技术不但可以用于加密，还可以用于鉴别，也可以通过两次使用 公开密钥方案既提供鉴别功能又提供保密功能。 在非对称密码系统中，产生两个密钥的相关算法很重要，算法必须满足这样 几个条牛：( 1 ) b 容易产生密钥k u b 和k r s ；( 2 ) 在已知k u b 和明文m 情况下， a 很容易产生通过计算产生对应密文c ：c = e k 。( m ) ；( 3 ) b 用k r b 很容易通过 计算解密密文恢复出原来名文m ；( 4 ) 攻击者在己知k u b 情况下，要确定出 k r b 在计算上是不可能的；( 5 ) 攻击者在已知k u b 和密文c 的情况下，要恢复 出明文m 在计算上是不可能的：( 6 ) 加密和解密函数可以以两个次序中的任何 一个来使用：m = e 。【d m ( m ) 】= d m 【e m ( m ) 】。这些条件一般很难达到，但 在设计密码系统时，要尽可能的达刭或接近这些条件，这样密码系统才能达到真 正的保密。 1 2 密码分析学 密码分析学作为密码学的一个重要分支，日益受到人们的重视。密码编码学 主要是研究密码变化的规律，并用于编制密码以保护秘密信息的科学。而密码分 析学是研究密码变化规律并用之于密码以获取信息情报的科学。密码分析学也称 作密码破译学。 1 2 1 密码分析学的发展背景 几千年前密码学就已经用于保护军事和外交通信，在当今信息时代，大量的 敏感信息，如病例、法庭纪录、私人财产等，常通过公共通信设施或计算机网络 来进行交换，而这些信息的秘密性和真实性是人们迫切需要的。因此，随之而来 的信息安全问题日益突出，信息的安全威胁主要来自黑客攻击、计算机病毒、拒 绝服务等。这就要加强信息系统的安全性，而一个系统是否安全以及如何加强系 统的安全性，只有通过对该系统抵抗当前各类攻击能力的考查和全面分析才能做 出定论 5 1 。目前人们越来越重视信息的安全威胁，因此密码分析也越来越受到广 泛重视。 1 2 2 密码分析学研究的必要性 对密码进行分析主要是为了发现加密算法、密钥或密码系统的弱点，以完善 加密过程，更有利于信息的安全。另方面，是为了掌握密码分析者或破译者攻 击密码的方法，找出其方法的漏洞，便于预防他们的攻击。同时也是为了更进一 步提高广大计算机用户的安全意识和知识水平，减少针对系统的非法入侵和攻击 带来的损失。因此，进行密码分析是非常必要的。 1 2 3 密码分析的定义 在消息传输和处理系统中，除了易定的接收者外，还有非授权者。他们通过 各种办法，如搭线窃听、电磁窃听、声音窃听等来取机密信息，称其为接收者。 他们虽然不知道系统所用的密钥，但通过分析可能从截获的密文推断出原来的名 文甚至密钥，这一过程称作密码分析【6 】。从事这一工作的人称作密码分析员或密 码分析者。所谓一个密码是可破的，是指通过密文能够迅速地确定明文或密钥， 或通过明文密文对能够迅速地确定密钥。 密码分析的实质就是在不知道密钥的情况下，对截获的有关密文材料进行分 6 析、假设、推断和证实等步骤后恢复出明文，或者是试图找出密钥，结合从加密 算法( 加密算法一般比较容易获得) 转换而来的解密算法恢复出明文，如图1 4 所示。 图1 - 4 密码分析简化模型 破译密码往往不是件容易的事，密码设计是用数学方法设计出算法和密钥来 构造密码，而密码分析除了依靠数学、工程背景、语言等知识外、还要靠经验、 统计、测试、眼力、直觉判断能力有时还靠点运气。因此密码分析更具挑战性。 在密码学中，“分析( a n a l y s i s ) ”和“攻击( a t t a c k ) ”这两个术语含义相同， 本文中交替使用这两个术语。 1 3 密码分析的理论基础 密码分析涉及到很多数学理论知识，如组合论、算法复杂性理论、概率统计， 系统学等【7 】。数论、信息论更是近代密码学研究所必不可少的。这一节介绍一些 必要的理论概念。 1 3 1 系统学9 一个系统s y s t e m 可以用一个对子s = 来表示，e 是系统s 的元素集，r 是e 上的二元关系集，即r c _ e x e ，表示系统s 中元素e 之间的关系。 例如，加密解密及密码破译过程就是一个完整的系统，如图1 ，5 所示，此常 规密码系统可定义为系统s = ，其中e = 消息源，加密算法，密码破译者， 明文，密文，解密算法，目的地，密钥源，密钥通道) ；e 上的二元关系r = ( 消 息源，加密算法) ，( 加密算法，解密算法) ，( 加密算法，密码破译者) ，( 密码破 译者，明文) ，( 密码破译者，密钥) ，( 解密算法，目的地) ，( 密钥源，加密算法) ， ( 密钥源，密钥通道) ，( 密钥通道，解密算法) 。 系统无所不在，我们设计的密码分析系统其实就是一个系统。 图1 5 常规密码系统 1 3 2 信息论 s h a n n o n 的信息论【l o 】是密码学重要的理论基础。下面主要介绍信息论的基本 概念及与密码学有关的理论。 一、熵概念 随机事件的一个特性在于它的不确定性。对密码的分析可以看出，明文是毫 无不确定性可言的，密文则不然，随着分析的进行，不确定性程度逐渐减小，最 后完全确定。不同的密码，他们的强度也不一样。密码分析者如何能够进行成功 的密文攻击，这涉及熵的思想。 假设有一随机变量x ，它根据概率分布在一个有限集合上取值，即 p x - - - x i = p i ，i = l ，2 ，n 。根据分布发生的事件来获得的信息是什么? 等价地， 如果一个事件还没有发生，有关这个结果的不确定性是什么? 这个量称为x 的 熵并表示为h f x ) 。 熵定义：设x 是一个随机变量，它根据概率分布在一个有限集合上取值，即 p x - - x i = p i ，i = l ，2 ，n 。那么这个概率分布的熵定义为 即沪一鼻l o g p j i = 1 随机变量x 的熵有基本性质：o h l o g n 。当p 1 = p 2 - = 告时熵取最大 值，即当n 个结果等概率时不确定性达到最大，最难做出预测。 二、条件熵 密码分析中研究更感兴趣的是在已获得某些密文的条件下，对发送某些消息 或使用某一密钥的不确定性测度。为此定义下面的条件熵( 既暖昧度) 。 条件熵定义：设x 与y 是两个随机变量，那么对y 的任何一个固定值y ， 都得到一个( 条件) 概率分布p ( x y ) ，显然 h ( x y ) = 一p ( x y ) l o g p ( x y ) 定义条件熵h ( x y ) 是所有可能值y 的熵h ( x y ) 的加权平均( 关于概率p ) ， 既 h ( x v ) = 一p ( y ) p ( x y ) l o g p ( x y ) 条件熵测度通过y 来泄漏有关x 的信息的平均数。 定理l ：设( m ，c ，k ，e ，d ) 是一个密码体制( m 、c 、k 、e 、d 分别表 示明文空间、密文空间、密钥空间、加密变换、解密变换) ，那么有 h ( k c ) = h ( k ) + h ( m ) 一h ( c ) 成立( 证明略) 。条件熵h ( k c ) 称为密钥暖昧度，它是密文能泄漏多少有关密钥 的信息的一种测度。 三、多余度和唯一解码量 i l l 假定k 中的密钥都是等概率的，设k = k l ，k 2 ，k n ) ，n 是密钥数量。所 以 p 2 古，h ( k ) 2 - - n p l o g pn 古l o g 古2 l o g n 再假定长度为n 的字符串共有t n = 2 ”，其中有意义的明文数s 。= 2 ”。所以 h ( m ) = r 。n ，h ( c ) = r n h ( k c ) = h ( k ) + h ( m ) - - h ( c ) = 0 表达了给定了密文，密钥k 不存在不确定性，也 就是给定了密文c 后，密钥k 便确定了。这个字符数n 使 h ( k ) + h ( m ) 一h ( c ) 2 0 称之为唯一码量。所以 h ( k ) = ( r r n ) n 这个方程的解便是唯一码量，用l l d 表示。令，= r r n 是语言的多余度。则 h ( k ) = r u , t ，l l d = 粤 u d 给出破译一密码的最少字符数，也就是确定密钥的最少密文字符数目。 1 3 - 3 数论 9 数论在密码学，尤其是现代密码学的研究中有着重要的作用，其中许多概念 及函数是密码编码及密码分析算法的基础，本节介绍我们将要涉及到的一些概念 和函数 1 2 1 。 一、因子 如果a _ m b ，其中a 、b 、m 为整数，则当b ：o 时，可以说b 能整除a 。换 句话说，a 除以b 余数为0 ，用符号b i a 表示。当b i a 时，b 是a 的一个因子。 二、素数 素数p 是大于1 且因子仅为1 和- i - p 的整数。素数在数论中起着至关重要 的作用。 任何大于1 的整数a 能被因式分解为唯一形式： a l口2a a i p 。p l p l 其中p 1 p 2 p 都是素数且每个口 o 。 三、互为素数 符号g o d ( a ，b ) 表示a 和b 的最大公因子。正整数c 是a 和b 的最大公因 子，如果满足条件：( 1 ) c 是a 和b 的因子；( 2 ) 任何a 和b 的因子也是c 的因 子。如果g c d ( a ，b ) ；1 ，则a 与b 互素。 四、模运算 给定任一正整数n 和任一整数a ，如果用a 除以n ，得到的商q 和余数r 将满 足如下关系： a = q n + r o r n ：q = l a n 其中l x j 表示小于或等于x 的最大整数。用a m o dn 表示a 除以n 的余数，则任 一正整数a 可表示为： a = l a n j x n + ( a m o d n ) 如果( a m o d n ) = ( b m o d n ) ，则称整数a 和b 模n 同余，可写为 a = b m o d a 注意：如果a i o m o d n ，则n l a 。 模运算有如下一些性质： i o ( 1 ) 【( am o dn ) + ( b r o o dn ) m o dn 2 ( a + b ) m o dn ( 2 ) 【( a m o d n ) - - ( bm o dn ) m o dn 2 ( a - - b ) m o d n ( 3 ) 【( am o dn ) ( bm o dn ) m o dn = ( a b ) m o d n 五、乘法逆元 定义集合z 1 1 为小于n 的所有非负整数集合： 厶= 0 ，1 ，2 ，( n 一1 ) 该集合也被当作模n 的余数集合。如果p 是一个素数，对每一个w z p ，存在 一个z ，使得w x z = i m o d p ，则称z 为w 的模p 乘法逆元，命名为w 。 六、费马定理 费马定理表述为：如果p 是素数，a 是不能被p 整除的正整数，则： a p 1 = 1m o d p 营a p ：a m o d p 七、欧拉函数 欧拉函数记为由( n ) 由( n ) 表示小于n 的且与n 互素的正整数个数。对于任一 个素数p ，有 中( p ) = p 一1 对两个不同的素数p 和q ，对n = p q ，有 由( n ) = 巾( p q ) = 巾( p ) x 中( 0 3 = ( p 1 ) ( q 一1 ) 欧拉定理可表述为对于任何互素的整数a 和n ，有： a ( “) i 1m o d n 给定两个素数p 和q ，以及整数唧q 和m ，其中0 m 时，猜定 世h 晡 】2 0 ；当p 时，猜定丘k 知 1 2 1 ； 当p i k - n 2 1 ，则将k 所对应的密钥候选者作为k 。并猜定 k 吣：，t 】2 0 ( 当p 时) 或1 ( 当p m r ) 。 如果p 是使得等式( 3 ) 成立的概率。对一个子密钥候选者k 。和一个随机 变量z ，设q 。( 净1 ，2 ，) 是使得下列等式成立的概率 f ( x ，k 。) k 。，e ：，p 。】= ，( x ，e 。) k 。，e ：，】 ( 4 ) 文献 1 5 中指出：当j p - 充分小时，如果g ( i 1 ，2 ，) 是相互独立的，那 么算法( 2 5 2 ) 的成功率为 k 川删 。及麟搿“面1e v 锄 去e l 喙 这里的积是除了k 。外取遍所有的子密钥候选者。由( 5 ) 式知，算法2 5 2 的成 功率只依赖q ，e ：，和万l p - i 。它给出了成功率的一个比较好的估计。 2 5