1、信息安全数学基础信息安全数学基础余纯武 副教授武汉大学计算机学院什么是信息安全?通信保密通信保密（COMSEC）：60-70年代 信息保密信息安全信息安全（INFOSEC）：80-90年代 机密性、完整性、可用性、不可否认性 等信息保障信息保障（IA）：90年代- 基本的通讯模型 通信的保密模型通信安全-60年代（COMSEC）发方收方信源编码(纠错码)信道编码信道传输通信协议发方收方敌人信源编码信道编码信道传输通信协议密码60-70年代 这一时期主要关注“机密性” 40年代以前“通信安全（COMSEC）” 也称“通信保密” 40年代增加了“电子安全” 50年代欧美国家将“通信安全”和 “电子
2、安全”合称为“信号安全（SIGSEC）” 密码学是解决“通信安全”的重要技术 密码学是解决密码学是解决“机密性机密性”的核心技的核心技术，术， 这一时期密码学得到了很好的发展这一时期密码学得到了很好的发展。 ShannonShannon于于19491949年发表的论文保年发表的论文保密密 系统的信息理论为对称密码学建系统的信息理论为对称密码学建立立 了理论基础，从此密码学从了理论基础，从此密码学从非科学非科学发发 展成为一门科学。展成为一门科学。 19651965年美国率先提出了年美国率先提出了计算机安全（计算机安全（COMPUSECCOMPUSEC） 这一时期主要关注这一时期主要关注“机密性
3、、访问控制、认证机密性、访问控制、认证” 6060年代出现了多用户系统，从而引入了受控共享的问年代出现了多用户系统，从而引入了受控共享的问题。此时计算机主要用于军方，题。此时计算机主要用于军方，19691969年年的的WareWare报告初报告初步的提出了计算机安全及其评估问题。研究方面，出步的提出了计算机安全及其评估问题。研究方面，出现了现了Adept50Adept50和和multicsmultics操作系统上的安全研究工作。操作系统上的安全研究工作。 70年代是计算机安全的奠基时代。1972年Anderson带领的小组完成了著名的Anderson报告，这个报告可以看作是计算机安全发展的里程
4、碑。其中提出了计算机安全的主要问题以及相关的范型（如访问监控机）。在这一阶段计算机主要用于军方与科研，而访问控制方面关注信息的机密性，这时提出了强制访问控制策略和自主访问控制策略。其间进行的重要工作包括访问控制矩阵的提出、BLP模型、BIBA模型、HRU模型。其中，BLP模型是影响深远的强制访问控制模型，BIBA模型是提出较早的完整性模型，而HRU模型给出了形式化的访问控制矩阵的描述，并提出了安全模型领域中著名的SAFTY问题（授权传播的可判定性问题）。 这一时期现代密码学得到了快速发展，最有影响的两个大事件是：一件是Diffiee和Hellman于1976年发表的论文密码编码学新方向，该文导
5、致了密码学上的一场革命，他们首次证明了在发送者和接收者之间无密钥传输的保密通信是可能的，从而开创了公钥密码学的新纪元；另一件是美国于1977年制定的数据加密准DES。两个事件志着代密学的生。 信息安全的三个基本方面保密性Confidentiality即保证信息为授权者享用而不泄漏给未经授权者。完整性Integrity 数据完整性，未被未授权篡改或者损坏 系统完整性，系统未被非授权操纵，按既定的功能运行可用性Availability即保证信息和信息系统随时为授权者提供服务，而不要出现非授权者滥用却对授权者拒绝服务的情况信息安全的含义(80-90年代) 8080年代的一个标志性特征就是计算机安全的
6、标准化工作。美国年代的一个标志性特征就是计算机安全的标准化工作。美国军方提出了著名的军方提出了著名的TCSECTCSEC标准，为计算机安全评估奠定了基础。标准，为计算机安全评估奠定了基础。在这之后又陆续发表了在这之后又陆续发表了TNITNI、TDITDI等等TCSECTCSEC解释性评估标准。标准解释性评估标准。标准化的工作带动了安全产品的大量出现。化的工作带动了安全产品的大量出现。 8080年代的另一个标志性特征就是计算机在商业环境中得到了应年代的另一个标志性特征就是计算机在商业环境中得到了应用，所以访问控制的研究也不可避免的要涉及到商业安全策略用，所以访问控制的研究也不可避免的要涉及到商业
7、安全策略。而。而Clark-Clark-wilsonwilson和和Chinese wallChinese wall策略模型是典型的代表。策略模型是典型的代表。 入侵检测系统（入侵检测系统（IDSIDS）概念最早出自于概念最早出自于AndersonAnderson在在19721972年的一项年的一项报告。报告。19801980年，年，AndersonAnderson为美国空军做的题为计算机安全威为美国空军做的题为计算机安全威胁监控与监视胁监控与监视的技术报告，第一次详细地阐述了入侵检测的的技术报告，第一次详细地阐述了入侵检测的概念，并首次为入侵和入侵检测提出了一个统一的架构。概念，并首次为入侵
8、和入侵检测提出了一个统一的架构。 8080年代初，安全协议理论如安全多方计算、形式化分析和可证年代初，安全协议理论如安全多方计算、形式化分析和可证明安全性等相继问世明安全性等相继问世 这一时期主要关注这一时期主要关注“ “机密性、完整性、可用性、可控性、非否认机密性、完整性、可用性、可控性、非否认性性” ” 8080年代中期，美国和欧洲先后在学术界和军事领域开始使用年代中期，美国和欧洲先后在学术界和军事领域开始使用“ “信信息安全（息安全（INFOSECINFOSEC）”和和“信息系统安全（信息系统安全（INFO SYS SECINFO SYS SEC或或ISSECISSEC）”。 主要内容包
9、括：主要内容包括： 通信安全通信安全 计算机安全计算机安全 发射安全（发射安全（EMSECEMSEC） 传输安全（传输安全（TRANSECTRANSEC） 物理安全物理安全（PHYSICALSECPHYSICALSEC） 人事安全（人事安全（PERSONNEL SECPERSONNEL SEC） 密码技术得到了空前的发展，密码技术得到了空前的发展，提出了很多新观点和新方法如ECC、密钥托管、盲签名、零知识证明协议 涌现了大量的实用安全协议，如互联网密钥交换（涌现了大量的实用安全协议，如互联网密钥交换（IKEIKE）协议协议、分布式认证安全服务（、分布式认证安全服务（DASSDASS）协议、协议
10、、KerberosKerberos认证协议、认证协议、X.509X.509协议、协议、SETSET协议、协议、iKPiKP协议协议 安全协议的三大理论（安全协议的三大理论（安全多方计算、形式化分析和可证明安安全多方计算、形式化分析和可证明安全性全性）取得了突破性进展）取得了突破性进展 IDSIDS的研究进入了多样化发展时期的研究进入了多样化发展时期 19891989年提出了异常检测概念年提出了异常检测概念 19901990年形成了基于网络的年形成了基于网络的IDSIDS和基于主机的和基于主机的IDSIDS两大检测概念两大检测概念 19921992年形成了分布式入侵检测系统（年形成了分布式入侵检
11、测系统（DIDSDIDS） 19941994年，将自治代理（年，将自治代理（Autonomous AgentsAutonomous Agents）技术用于技术用于IDSIDS的的设设计计 19961996年为了解决入侵检测系统的可扩展性提出了年为了解决入侵检测系统的可扩展性提出了GRIDS(Graph-GRIDS(Graph-based Intrusion Detection System)based Intrusion Detection System) 安全评估标准得到高度重视。从美国国防部安全评估标准得到高度重视。从美国国防部19851985年发布著名的可信计年发布著名的可信计算机系统评
12、估准则（算机系统评估准则（TCSECTCSEC）起，世界各国根据自己的研究进展和实起，世界各国根据自己的研究进展和实际情况，相继发布了一系列有关安全评估的准则和标准，如美国的际情况，相继发布了一系列有关安全评估的准则和标准，如美国的TCSECTCSEC；英、法、德、荷等四国英、法、德、荷等四国9090年代初发布的信息技术安全评估准年代初发布的信息技术安全评估准则则( (ITSEC)ITSEC)；加拿大加拿大19931993年发布的可信计算机产品评价准则（年发布的可信计算机产品评价准则（CTCPECCTCPEC）；）；美国美国19931993年制定的信息技术安全联邦标准年制定的信息技术安全联邦标
13、准（FCFC）；）；6 6国国7 7方（加拿方（加拿大、法国、德国、荷兰、英国、美国大、法国、德国、荷兰、英国、美国NISTNIST及美国及美国NSANSA）于于9090年代中期年代中期提出的信息技术安全性评估通用准则（提出的信息技术安全性评估通用准则（CCCC）计算机应急响应受到重视。计算机应急响应受到重视。19881988年，美国康乃尔大学研究生莫里斯，首次利用计算机病毒（蠕虫）程序成功攻击了美年，美国康乃尔大学研究生莫里斯，首次利用计算机病毒（蠕虫）程序成功攻击了美国国防军事科研单位与有关大专院校联入因特网的国国防军事科研单位与有关大专院校联入因特网的60006000台计算机（占当时因特
14、网联机的台计算机（占当时因特网联机的1/101/10），使其瘫痪数日，造成近亿元损失），使其瘫痪数日，造成近亿元损失19891989年，美国、西德联手破获了前苏联收买西德大学生中的黑客，渗入欧美十余个国家的年，美国、西德联手破获了前苏联收买西德大学生中的黑客，渗入欧美十余个国家的计算机，获取大量敏感信息的计算机间谍案。计算机，获取大量敏感信息的计算机间谍案。这两起案件，极大地震动了西方世界。许多有识之士认为：随着网络技术及有关技术的发这两起案件，极大地震动了西方世界。许多有识之士认为：随着网络技术及有关技术的发展展, , 传统的、静态的安全保密措施已不足以抵御计算机黑客入侵及有组织的信息手段的
15、攻传统的、静态的安全保密措施已不足以抵御计算机黑客入侵及有组织的信息手段的攻击（信息战、网络战），必须建立新的安全机制击（信息战、网络战），必须建立新的安全机制于是在于是在19891989年美国国防部资助卡内基年美国国防部资助卡内基梅隆大学为其建立了世界上第一个梅隆大学为其建立了世界上第一个“ “计算机应急小组计算机应急小组（CERTCERT）” ”及其协调中心（及其协调中心（CERT/CCCERT/CC）。）。CERTCERT的成立标志着信息安全由静态保护向动态防护的成立标志着信息安全由静态保护向动态防护的转变。的转变。 美国人提出的概念美国人提出的概念: :InformationAssur
16、ance 保护保护（P Protect） 检测检测（D Detect） 反应反应（R React） 恢复恢复（R Restore）保护Protect检测Detect反应React恢复Restore信息保障 这一时期主要关注这一时期主要关注“ “预警、保护、检测、响应、恢复、反击预警、保护、检测、响应、恢复、反击” ”整整个过程个过程 信息安全保障强调保护、检测、反应和恢复这四种能力，围绕信息安全保障强调保护、检测、反应和恢复这四种能力，围绕人、技术和管理这三个层面，以支持机构的任务和职能为目标人、技术和管理这三个层面，以支持机构的任务和职能为目标，注重体系建设，强化组织与协调功能。，注重体系建
17、设，强化组织与协调功能。 19951995年，在研究信息安全及网络战防御理论过程中，美国国防年，在研究信息安全及网络战防御理论过程中，美国国防部提出了部提出了“ “信息安全保障体系信息安全保障体系” ”（IAIA）概念，并给出了概念，并给出了“ “保护（保护（ProtectionProtection）监测（监测（detectiondetection）响应（响应（ResponseResponse）” ”三环节三环节动态模型，即动态模型，即“ “PDRPDR” ”模型。后来增加了恢复（模型。后来增加了恢复（RestoreRestore）, ,变为变为“ “PDRR”PDRR”模型。其中模型。其中“
18、 “响应响应” ”包括平时事件响应和应急响应，而包括平时事件响应和应急响应，而重点在应急处理。重点在应急处理。 我国专家在我国专家在19991999年提出了更为完善的年提出了更为完善的“ “保护保护预警（预警（WarningWarning）监测监测应急应急恢复恢复反击反击（Counter-attackCounter-attack）” ”即即“ “PWDRRC”PWDRRC”模型，使信息安全保障技术体系立于更坚实的基础上。模型，使信息安全保障技术体系立于更坚实的基础上。 信息安全保障体系的建设是一项长期而艰巨的任务信息安全保障体系的建设是一项长期而艰巨的任务 当前，人们从以下几个方面致力于建立信
19、息安全保障当前，人们从以下几个方面致力于建立信息安全保障体系体系 组织管理体系：做顶层设计组织管理体系：做顶层设计 技术与产品体系技术与产品体系：密码、安全监控、安全审计、内容安全、授：密码、安全监控、安全审计、内容安全、授权认证、检测、可信计算、病毒防范、网络攻击、安全评估、权认证、检测、可信计算、病毒防范、网络攻击、安全评估、应急处理应急处理 标准体系标准体系 法规体系法规体系 人才培养、培训与服务咨询体系人才培养、培训与服务咨询体系 应急处理体系应急处理体系 美国：美国： 19981998年年1010月，月，NSANSA颁布了信息保障技术框架（颁布了信息保障技术框架（IATFIATF）1
20、.11.1版，版，19991999年年9 9月，月，20002000年年9 9月分别颁布了月分别颁布了2.02.0和和3.03.0版。本来版。本来4.04.0版应在版应在20012001年年9 9月出台，可能受到月出台，可能受到“911”“911”事件影响，到事件影响，到20022002年年9 9月，才颁月，才颁布了布了3.13.1版本。信息保障技术框架的研究和不断完善表明了美国版本。信息保障技术框架的研究和不断完善表明了美国军政各方对信息保障的认识逐步趋于一致。军政各方对信息保障的认识逐步趋于一致。 美国国防部美国国防部20022002年年1010月月2424日颁布了信息保障训令日颁布了信息
21、保障训令8500.18500.1，并于，并于20032003年年2 2月月6 6日颁布了信息保障的实施的指令日颁布了信息保障的实施的指令8500.28500.2。 美国：美国： 19981998年年1010月，月，NSANSA颁布了信息保障技术框架（颁布了信息保障技术框架（IATFIATF）1.11.1版，版，19991999年年9 9月，月，20002000年年9 9月分别颁布了月分别颁布了2.02.0和和3.03.0版。本来版。本来4.04.0版应在版应在20012001年年9 9月出台，可能受到月出台，可能受到“911”“911”事件影响，到事件影响，到20022002年年9 9月，才颁
22、月，才颁布了布了3.13.1版本。信息保障技术框架的研究和不断完善表明了美国版本。信息保障技术框架的研究和不断完善表明了美国军政各方对信息保障的认识逐步趋于一致。军政各方对信息保障的认识逐步趋于一致。 美国国防部美国国防部20022002年年1010月月2424日颁布了信息保障训令日颁布了信息保障训令8500.18500.1，并于，并于20032003年年2 2月月6 6日颁布了信息保障的实施的指令日颁布了信息保障的实施的指令8500.28500.2。 电子邮件 自动提款机 电话卡:IP卡、201电话卡 银行取钱 信用卡购物密码从军事走向生活 密码学(Cryptology):是研究信息系统安全
23、保密的科学.密码编码学(Cryptography):主要研究对信息进行编码,实现对信息的隐蔽.密码分析学(Cryptanalytics):主要研究加密消息的破译或消息的伪造.基本概念 消息被称为明文(Plaintext)。用某种方法伪装消息以隐藏它的内容的过程称为加密(Encrtption)，被加密的消息称为密文(Ciphertext)，而把密文转变为明文的过程称为解密(Decryption)。 对明文进行加密操作的人员称作加密员或密码员(Cryptographer). 密码算法(Cryptography Algorithm):是用于加密和解密的数学函数。 密码员对明文进行加密操作时所采用的一
24、组规则称作加密算法(Encryption Algorithm). 所传送消息的预定对象称为接收者(Receiver). 接收者对密文解密所采用的一组规则称为解密算法(Decryption Algorithm).基本术语加解密过程示意图 加密和解密算法的操作通常都是在一组密钥的控制下进行的,分别称为加密密钥(EncryptionKey)和解密密钥(DecryptionKey).明文明文密文加密算法解密算法密钥密钥密码学的目的：Alice和Bob两个人在不安全的信道上进行通信，而破译者Oscar不能理解他们通信的内容。加密通信的模型Alice加密机解密机Bob安全信道密钥源Oscarxyxk 密码
25、体制：它是一个五元组（P,C,K,E,D)满足条件：（1）P是可能明文的有限集；（明文空间）（2）C是可能密文的有限集；（密文空间）（3）K是一切可能密钥构成的有限集；（密钥空间）*（4）任意kK,有一个加密算法和相应的解密算法，使得和分别为加密解密函数，满足dk(ek(x)=x,这里xP。密码体制 按照保密的内容分:受限制的（restricted)算法:算法的保密性基于保持算法的秘密。基于密钥（key-based)的算法:算法的保密性基于对密钥的保密。-现代密码理论密码算法分类-i 基于密钥的算法，按照密钥的特点分类： 对称密码算法（symmetriccipher)：又称传统密码算法（con
26、ventionalcipher)，就是加密密钥和解密密钥相同，或实质上等同，即从一个易于推出另一个。又称秘密密钥算法或单密钥算法。 非对称密钥算法（asymmetriccipher):加密密钥和解密密钥不相同，从一个很难推出另一个。又称公开密钥算法（public-keycipher)。 公开密钥算法用一个密钥进行加密,而用另一个进行解密.其中的加密密钥可以公开,又称公开密钥（publickey)，简称公钥.解密密钥必须保密,又称私人密钥（privatekey)私钥.简称私钥。密码算法分类-ii 按照明文的处理方法：分组密码（blockcipher):将明文分成固定长度的组，用同一密钥和算法对每
27、一块加密，输出也是固定长度的密文。流密码（streamcipher):又称序列密码.序列密码每次加密一位或一字节的明文，也可以称为流密码。序列密码是手工和机械密码时代的主流密码算法分类-iii 对称密钥密码又可分为：分组密码 每次对一块数据加密 多数网络加密应用 DES,IDEA,RC6,Rijndael流密码 每次对一位或一字节加密 One-time padding,Vigenre,Vernam密码算法分类-iv 公开密钥密码: 大部分是分组密码，只有概率密码体制属于流密码 每次对一块数据加密 数字签名,身份认证 RSA,ECC,ElGamal 加密解密速度慢密码算法分类-v三个阶段： 19
28、49年之前 密码学是一门艺术 19491975年 密码学成为科学 1976年以后 密码学的新方向公钥密码学密码学的起源和发展-i密码学的起源 隐写术(steganography):通过隐藏消息的存在来保护消息. 隐形墨水 字符格式的变化 图象图像 (象形文字的修改)ModifiedHieroglyphics,c.1900B.C.密码学的第一个例子是对标准书写符号的修改例如:古埃及法老坟墓上的文字思想:代替(substitution)example-i SpartanScytale,c.500B.C.斯巴达人用于加解密的一种军事设备发送者把一条羊皮螺旋形地缠在一个圆柱形棒上思想：置换（permu
29、tation)example-ii PolybiusCheckerboard,205123B.C. 明文:POLYBIUS 密文:3534315412244543123451ABCDE2FGHIJK3LMNOP4QRSTU5VWXYZexample-iii CaesarCipher,c.50B.C.ABCDEFGXYZDEFGHIJABC明文:Caesarcipherisashiftsubstitution密文:FDHVDUFLSKHULVDVKLIWVXEVWLWXWLRQexample-iV Nomenclator代码本c.1400字母、符号、单词、短语代码代码字母、符号、单词、短语应用：
30、WorldWarIIExample-VExampleCont 网格加密法：中国例：密文：王先生：来信收悉，你的盛情难以报答。我已在昨天抵达广州。秋雨连绵，每天需备伞一把。大约本月中旬即可返回，再谈。弟：李明2001年11月7日 网格加密法：中国例：密文：王先生：来信收悉，你的盛情难以报答。我已在昨天抵达广州。秋雨连绵，每天需备伞一把。大约本月中旬即可返回，再谈。弟：李明2001年11月7日明文：情报在雨伞把中。 兽栏法：明文：System密文：ABCDEFGHIJ.K.LM.N.OP.Q.RS:T:UV:W:XY:Z:.：.密文字母表： 1949年之前: 古典密码（classical cryp
31、tography) 密码学还不是科学,而是艺术 出现一些密码算法和加密设备 密码算法的基本手段(substitution & permutation)出现，针对的是字符 简单的密码分析手段出现密码学的起源和发展-ii 19491975年: 计算机使得基于复杂计算的密码成为可能 1949年Shannon的“The Communication Theory of Secret Systems” 1967年David Kahn的The Codebreakers 1971-73年IBM Watson实验室的Horst Feistel等的几篇技术报告Smith,J.L.,TheDesignofLucif
32、er,ACryptographicDeviceforDataCommunication,1971Smith,J.L.,AnExprementalApplicationofCryptogrphytoaremotelyAccessedDataSystem,Aug.1972Feistel,H.,CryptographyandComputerPrivacy,May1973数据的安全基于密钥而不是算法的保密密码学的起源和发展-iii 1976年以后: 1976年Diffie & Hellman的“New Directions in Cryptography”提出了不对称密钥密码1977年Rivest,S
33、hamir & Adleman提出了RSA公钥算法90年代逐步出现椭圆曲线等其他公钥算法 公钥密码使得发送端和接收端无密钥传输的保密通信成为可能！密码学的起源和发展-iv 1976年以后: 对称密钥密码算法进一步发展1977年DES正式成为标准80年代出现“过渡性”的“post DES”算法,如IDEA,RCx,CAST等90年代对称密钥密码进一步成熟 Rijndael,RC6, MARS, Twofish, Serpent等出现2001年Rijndael成为DES的替代者密码学的起源和发展-v 假设破译者Oscar是在已知密码体制的前提下来破译Bob使用的密钥。这个假设称为Kerckhoff
34、原则。最常见的破解类型如下：1.唯密文攻击：Oscar具有密文串y.2.已知明文攻击:Oscar具有明文串x和相应的密文y.3.选择明文攻击：Oscar可获得对加密机的暂时访问，因此他能选择明文串x并构造出相应的密文串y。4.选择密文攻击:Oscar可暂时接近密码机,可选择密文串y，并构造出相应的明文x.这一切的目的在于破译出密钥或密文密码分析 密码破译的原则:遵循观察与经验 方法:采用归纳与演绎 步骤:分析、假设、推测和证实 三大要素：语言的频率特征：e连接特征:qu,Iex,重复特征:th,tion,tious密码破译无条件安全（Unconditionally secure） 无论破译者有
35、多少密文,他也无法解出对应的明文,即使他解出了,他也无法验证结果的正确性. Onetime pad计算上安全（Computationally secure）破译的代价超出信息本身的价值破译的时间超出了信息的有效期破译需要的存储空间超过了目前的资源密码算法的安全性攻击方法的复杂性（1）数据复杂性（2）时间复杂性（3）空间复杂性 RSA算法 1977年由RonRivest、AdiShamir和LenAdleman发明，1978年公布 是一种分组加密算法。 明文和密文在0n-1之间,n是一个正整数 应用最广泛的公钥密码算法 只在美国申请专利，且已于2000年9月到期RSA算法描述RSA加、解密算法(
36、1978Rivest,Shamir,Adelman) 分组大小为k, 2k n 2k+1公开密钥n（两素数p和q的乘积）（推荐p,q等长）e（与(p-1)(q-1)互素）ed1(mod(p-1)(q-1)私人密钥d（e-1mod(p-1)(q-1)加密c=memodn解密m=cdmodnRSA密钥生成原理 令n=pq,pq都是素数,(n)=(p-1)(q-1)是n的Euler数 Euler定理推论:若n=pq,pq都是素数,k是任意整数,则mk(p-1)(q-1)+1mmodn,对任意0mn 只要选择e,d,满足ed=k(n)+1,即ed1mod(n)de-1mod(n) 公钥:KU=e,n,
37、私钥:KR=d,nexample（1）若Bob选择了p=101和q113（2）那么，n=11413,(n)=10011211200；（3）然而1120026527，一个正整数e能用作加密指数，当且仅当e不能被2，5，7所整除。假设Bob选择了e=3533，（4）那么用Euclidean算法将求得：d=e-16597(mod11200),于是Bob的解密密钥d=6597.（5）Bob在一个目录中公开n=11413和e=3533（6）现假设Alice想发送明文9726给Bob，她计算：97263533(mod11413)=5761，且在一个信道上发送密文5761。（7）当Bob接收到密文5761时
38、，他用他的秘密解密指数（私钥）d6597进行解密：57616597（mod11413)=9726RSA安全性依据RSA的安全性是基于加密函数ek(x)=xe(modn)是一个单向函数，所以对攻击的人来说求逆计算不可行。而Bob能解密的陷门是分解n=pq，知(n)=(p-1)(q-1)。从而用欧氏算法解出解密私钥d.（猜想：攻破RSA与分解n是多项式等价的。然而，这个猜想至今没有给出可信的证明！）每个合数都可以唯一地分解出素数因子6=23999999=333711133727641=131121从2开始试验每一个小于等于27641的素数。素数：只能被1和它本身整除的自然数；否则为合数。整数n的十
39、进制位数因子分解的运算次数所需计算时间（每微秒一次）501.4x10103.9小时759.0 x1012104天1002.3x101574年2001.2x10233.8x109年3001.5x10294.0 x1015年5001.3x10394.2x1025年对RSA的攻击方法1、强力攻击（穷举法）：尝试所有可能的私有密钥2、数学分析攻击：各种数学方法，等价与两个素数乘积的因子分解3、对RSA实现的攻击90年代大数分解的进程分解数尺寸bits分解日期分解算法RSA-1003301991.4二次筛法RSA-1103641992.4二次筛法RSA-1203971993.6二次筛法RSA-12942
40、51994.4二次筛法RSA-1304301996.4数域筛法RSA-1404631999.2数域筛法RSA-1555121999.8数域筛法RSA-155的分解 1999.8.22，荷兰H.Riele领导的来自6个国家的研究人员组成的团队找到了一个512-bitRSA密钥的一个素因子 512-bitRSA在电子商务中所占的比例为95% 用了5个月的时间，计算机时间估计为8000mipsyears对RSA的攻击 对RSA的具体实现存在一些攻击方法，但不是针对基本算法的，而是针对协议的。 对RSA的选择密文攻击 对RSA的公共模攻击 对RSA的小加密指数攻击 对RSA的小解密指数攻击 时间性攻击
41、：取决于解密算法的运算时间对RSA的选择密文攻击 例1：E监听A的通信，收集由A的公开密钥加密的密文c，E想知道消息的明文m,使m=cdmodn 他首先选择随机数r,使rn.然后用A的公开密钥e计算x=remodny=xcmodnt=r-1modn 如果x=remodn，则r=xdmodn现在E让A对y签名，即解密y,A向E发送u=ydmodn而E计算tumodn=r-1ydmodn=r-1xdcdmodn=cdmodn=m对RSA的选择密文攻击 例2：E让A对m3签名。他产生两个消息m1和m2，满足m3=m1m2(modn) 如果E能让A分别对m1和m2签名，则可以计算m3：m3d=(m1d
42、modn)(m2dmodn)注意：不要用RSA对陌生人的随机文件签名，签名前先使用一个散列函数对RSA的公共模攻击 一种可能的RSA实现方法是给每个人相同的n,但指数d和e不同。 问题：如果相同的消息曾用两个不同的指数加密，而这两个指数是互素的，则明文可以不用任何一个解密密钥来恢复。 令m为明文消息，两个加密密钥为e1，e2,两个密文消息为c1,c2c1=me1modnc2=me2modn由于e1和e2互素，所以可以用扩展的Euclid算法找到r,s使re1+se2=1,假设r是负数，可以用扩展的Euclid算法计算c1-1,而(c1-1)-r*c2s=mmodn注意:不要让一群用户共享一个模
43、n对RSA的小加密指数攻击 如果使用一个较小的e值，则进行RSA签名和加密会很快，但也不安全。 如果用相同e值的不同公开密钥加密e(e+1)/2个线性相关的消息，则系统是可破的。如果有少于这些的消息或消息不相关，则无问题。 比如：消息为mj,使用同样的指数e,模数分别为q1,q2,qs（两两互素）,则密文为mjemodq1，mjemodq2，mjemodqs，根据中国剩余定理，m=mjemodq1q2qs.可以计算出来，对于较小的e，可以解出mj。 解决办法：加密前将消息与随机值混合，并保证m与n有相同的长度。对RSA的小解密指数攻击 使用较小的d会产生穷尽解密攻击的可能 当d为n的1/4长度
44、时，而e小于n时，可以恢复d，当e,d是随机选择的时，这种情况很少发生，当e很小时不会发生。 注意：应选择一个大的d值RSA密码体制的实现实现的步骤如下：Bob为实现者(1)Bob寻找出两个大素数p和q(2)Bob计算出n=pq和(n)=(p-1)(q-1).(3)Bob选择一个随机数e(0e(n)，满足（e，(n)）1(4)Bob使用辗转相除法计算d=e-1(mod(n)(5)Bob在目录中公开n和e作为她的公开钥。选好这些参数后，将明文划分成块，使得每个明文报文P长度m满足0mn。加密P时，计算CPe(modn)，解密C时计算PCd(modn)。由于模运算的对称性，可以证明，在确定的范围内
45、，加密和解密函数是互逆的。为实现加密，需要公开(e,n)，为实现解密需要(d,n)。实现要求 于是要求：若使RSA安全，p与q必为足够大的素数，使分析者没有办法在多项式时间内将n分解出来。建议选择p和q大约是100位的十进制素数。模n的长度要求至少是512比特。EDI攻击标准使用的RSA算法中规定n的长度为512至1024比特位之间，但必须是128的倍数。国际数字签名标准ISO/IEC9796中规定n的长度位512比特位.至1996年，建议使用768位的模n。素数的选取 为了抵抗现有的整数分解算法，对RSA模n的素因子p和q还有如下要求：(1)|p-q|很大，通常p和q的长度相同；(2)p-1
46、和q-1分别含有大素因子p1和q1(3)P1-1和q1-1分别含有大素因子p2和q2(4)p+1和q+1分别含有大素因子p3和q3加密指数e的选取 为了提高加密速度，通常取e为特定的小整数，如EDI国际标准中规定e2161，ISO/IEC9796中甚至允许取e3。这时加密速度一般比解密速度快10倍以上。e2161优于e3之处在于它能够抵抗对RSA的小加密指数攻击实现中的问题（1）如何计算abmodn（2）如何判定一个给定的整数是素数？（3）如何找到足够大的素数p和q?(1)要点1：(axb)modn=(amodn)x(bmodn)modn要点2：a16=aaaaaaaaaaaaaaaa=a2,
47、a4,a8,a16更一般性的问题：amm的二进制表示为bkbk-1b0,则m=2ii0c0;d1forikdownto0doc2xcd(dd)modnifbi=1thencc+1d(da)modnreturnd计算ammodnammodn=a(2i)modn=a(2i)modnbi0bi0检测素数 直接判断一个整数是否为素数是困难的 命题:如果p是素数,则方程x21modp只有平凡解x1modp. 证明:x21modpp|(x2-1)p|(x+1)(x-1)p|(x+1),或者p|(x-1)x+1=kp,或者x-1=jp,k,j是整数x=kp-1,或者x=jp+1x1modp,或者x-1mod
48、p 若方程x21modp存在的解不是x1，则P不是素数。(2)目前还没有一个高效的办法，实际中应用最多MillerandRabin,WITNESS算法WITNESS(a,n)判定n是否为素数，a是某些小于n的整数1.令bkbk-1b0为(n-1)的二进制表示，2.d13.forikdownto04.doxd5.d(dd)modn6.ifd=1andx1andxn-17.thenreturnTRUE8.ifbi=19.thend(da)modn10.ifd111.thenreturnTRUE12.returnFALSE返回值：TRUE:n一定不是素数FALSE:n可能是素数应用：随机选择an,计算s次，如果每次都返回FALSE，则这时n是素数的概率为(1-1/2s)(3)通常的办法是随机选取一个大的奇数，然后进行素性检验1.随机选一个奇数n(如:可使用伪随机数发生器)2.随机选择一个整数an3.执行概率素数判定测试(如:用WITNESS(a,n),如果n未测试通过,则拒绝数值n,转向步骤14.如果n已通过足够的测试,则接受n,否则转向步骤2;说明：随机选取大约用ln(N)/2的次数，如ln(2200)/2=70好在生成密钥对时才用到，慢一点还可忍受。确定素数p和q以后，只需选取e,满足gcd(e,(n)=1,计算d=e-1mod(n)（sieve扩展的欧拉算法）
