信息安全数学基础余纯武 副教授武汉大学计算机学院
yuchunwu99@hotmail.com
什么是信息安全?
通信保密 （ COMSEC）,60-70年代信息保密信息安全 （ INFOSEC）,80-90年代机密性、完整性、可用性、不可否认性 等信息保障 （ IA）,90年代 -
基本的通讯模型
通信的保密模型通信安全 -60年代（ COMSEC）
发方 收方信源编码 (纠错码 )
信道编码信道传输通信协议发方 收方敌人 信源编码信道编码信道传输通信协议密码
60-70年代
这一时期主要关注,机密性,
40年代以前,通信安全（ COMSEC）,
也称,通信保密,
40年代增加了,电子安全,
50年代欧美国家将,通信安全,和
,电子安全,合称为,信号安全
（ SIGSEC）,
密码学是解决,通信安全,的重要技术
密码学是解决,机密性,的核心技术，
这一时期密码学得到了很好的发展。
Shannon于 1949年发表的论文,保密系统的信息理论,为对称密码学建立了理论基础，从此密码学从 非科学 发展成为一门科学。
1965年美国率先提出了 计算机安全（ COMPUSEC）
这一时期主要关注,机密性、访问控制、认证,
60年代出现了多用户系统，从而引入了受控共享的问题。此时计算机主要用于军方,1969年的 Ware报告初步的提出了计算机安全及其评估问题。研究方面，出现了
Adept50和 multics操作系统上的安全研究工作。
70年代是计算机安全的奠基时代。 1972年 Anderson带领的小组完成了著名的 Anderson报告，这个报告可以看作是计算机安全发展的里程碑。其中提出了计算机安全的主要问题以及相关的范型（如访问监控机）。在这一阶段计算机主要用于军方与科研，而访问控制方面关注信息的机密性，这时提出了强制访问控制策略和自主访问控制策略。其间进行的重要工作包括访问控制矩阵的提出,BLP模型,BIBA模型,HRU模型。其中,BLP模型是影响深远的强制访问控制模型,BIBA模型是提出较早的完整性模型，而 HRU模型给出了形式化的访问控制矩阵的描述，并提出了安全模型领域中著名的 SAFTY问题（授权传播的可判定性问题）。
这一时期现代密码学得到了快速发展，最有影响的两个大事件是：一件是 Diffiee和 Hellman于 1976年发表的论文,密码编码学新方向,,该文导致了密码学上的一场革命，他们首次证明了在发送者和接收者之间无密钥传输的保密通信是可能的，从而开创了公钥密码学的新纪元；另一件是 美国于 1977年制定的数据加密标准 DES。
这两个事件标志着现代密码学的诞生。
信息安全的三个基本方面
– 保密性 Confidentiality
即保证信息为授权者享用而不泄漏给未经授权者 。
– 完整性 Integrity
数据完整性，未被未授权篡改或者损坏
系统完整性，系统未被非授权操纵，按既定的功能运行
– 可用性 Availability
即保证信息和信息系统随时为授权者提供服务，而不要出现非授权者滥用却对授权者拒绝服务的情况信息安全的含义
(80-90年代 )
80年代的一个标志性特征就是计算机安全的标准化工作。美国军方提出了著名的 TCSEC标准，为计算机安全评估奠定了基础。在这之后又陆续发表了 TNI,TDI等 TCSEC解释性评估标准。标准化的工作带动了安全产品的大量出现。
80年代的另一个标志性特征就是计算机在商业环境中得到了应用，
所以访问控制的研究也不可避免的要涉及到商业安全策略。而
Clark-wilson和 Chinese wall策略模型是典型的代表。
入侵检测系统（ IDS）概念最早出自于 Anderson在 1972年的一项报告。 1980年,Anderson为美国空军做的题为,计算机安全威胁监控与监视,的技术报告，第一次详细地阐述了入侵检测的概念，
并首次为入侵和入侵检测提出了一个统一的架构。
80年代初，安全协议理论如安全多方计算、形式化分析和可证明安全性等相继问世
这一时期主要关注“机密性、完整性、可用性、可控性、非否认性”
80年代中期，美国和欧洲先后在学术界和军事领域开始使用,信息安全（ INFOSEC）,和,信息系统安全（ INFO SYS SEC或
ISSEC）,。
主要内容包括：
通信安全
计算机安全
发射安全（ EMSEC）
传输安全（ TRANSEC）
物理安全（ PHYSICALSEC）
人事安全（ PERSONNEL SEC）
密码技术得到了空前的发展,提出了很多新观点和新方法如 ECC、
密钥托管、盲签名、零知识证明协议
涌现了大量的实用安全协议，如互联网密钥交换（ IKE）协议、分布式认证安全服务（ DASS）协议,Kerberos认证协议,X.509协议,SET协议,iKP协议
安全协议的三大理论（ 安全多方计算、形式化分析和可证明安全性 ）取得了突破性进展
IDS的研究进入了多样化发展时期
1989年提出了异常检测概念
1990年形成了基于网络的 IDS和基于主机的 IDS两大检测概念
1992年形成了分布式入侵检测系统（ DIDS）
1994年，将自治代理（ Autonomous Agents）技术用于 IDS的设计
1996年为了解决入侵检测系统的可扩展性提出了 GRIDS(Graph-
based Intrusion Detection System)
安全评估标准得到高度重视。从美国国防部 1985年发布著名的可信计算机系统评估准则（ TCSEC）起，世界各国根据自己的研究进展和实际情况，
相继发布了一系列有关安全评估的准则和标准，如美国的 TCSEC；英、
法、德、荷等四国 90年代初发布的信息技术安全评估准则 (ITSEC)；加拿大 1993年发布的可信计算机产品评价准则（ CTCPEC）；美国 1993年制定的信息技术安全联邦标准（ FC）； 6国 7方（加拿大、法国、德国、荷兰、
英国、美国 NIST及美国 NSA）于 90年代中期提出的信息技术安全性评估通用准则（ CC）
计算机应急响应受到重视。
1988年，美国康乃尔大学研究生莫里斯，首次利用计算机病毒（蠕虫）程序成功攻击了美国国防军事科研单位与有关大专院校联入因特网的 6000台计算机（占当时因特网联机的 1/10），使其瘫痪数日，造成近亿元损失
1989年，美国、西德联手破获了前苏联收买西德大学生中的黑客，渗入欧美十余个国家的计算机，获取大量敏感信息的计算机间谍案。
这两起案件，极大地震动了西方世界。许多有识之士认为：随着网络技术及有关技术的发展,
传统的、静态的安全保密措施已不足以抵御计算机黑客入侵及有组织的信息手段的攻击（信息战、网络战），必须建立新的安全机制
于是在 1989年美国国防部资助卡内基 —梅隆大学为其建立了世界上第一个“计算机应急小组
（ CERT）”及其协调中心（ CERT/CC）。 CERT的成立标志着信息安全由静态保护向动态防护的转变。
美国人提出的概念,
Information Assurance
保护 （ Protect）
检测 （ Detect）
反应 （ React）
恢复 （ Restore）
保护
Protect
检测
Detect
反应
React
恢复
Restore
信息保障
这一时期主要关注“预警、保护、检测、响应、恢复、反击”整个过程
信息安全保障强调保护、检测、反应和恢复这四种能力，围绕人、
技术和管理这三个层面，以支持机构的任务和职能为目标，注重体系建设，强化组织与协调功能。
1995年，在研究信息安全及网络战防御理论过程中，美国国防部提出了“信息安全保障体系”（ IA）概念，并给出了“保护
（ Protection） —监测（ detection） —响应（ Response）”三环节动态模型，即,PDR”模型。后来增加了恢复（ Restore）,变为
,PDRR”模型。其中“响应”包括平时事件响应和应急响应，而重点在应急处理。
我国专家在 1999年提出了更为完善的“保护 —预警（ Warning） —
监测 —应急 —恢复 —反击（ Counter-attack）”即,PWDRRC”模型，使信息安全保障技术体系立于更坚实的基础上。
信息安全保障体系的建设是一项长期而艰巨的任务
当前，人们从以下几个方面致力于建立信息安全保障体系
组织管理体系：做顶层设计
技术与产品体系,密码、安全监控、安全审计、内容安全、授权认证、检测、可信计算、病毒防范、网络攻击、安全评估、应急处理
标准体系
法规体系
人才培养、培训与服务咨询体系
应急处理体系
美国：
1998年 10月,NSA颁布了信息保障技术框架（ IATF） 1.1版,1999
年 9月,2000年 9月分别颁布了 2.0和 3.0版。本来 4.0版应在 2001年 9
月出台，可能受到,911”事件影响，到 2002年 9月，才颁布了 3.1
版本。信息保障技术框架的研究和不断完善表明了美国军政各方对信息保障的认识逐步趋于一致。
美国国防部 2002年 10月 24日颁布了信息保障训令 8500.1，并于
2003年 2月 6日颁布了信息保障的实施的指令 8500.2 。
美国：
1998年 10月,NSA颁布了信息保障技术框架（ IATF） 1.1版,1999
年 9月,2000年 9月分别颁布了 2.0和 3.0版。本来 4.0版应在 2001年 9
月出台，可能受到,911”事件影响，到 2002年 9月，才颁布了 3.1
版本。信息保障技术框架的研究和不断完善表明了美国军政各方对信息保障的认识逐步趋于一致。
美国国防部 2002年 10月 24日颁布了信息保障训令 8500.1，并于
2003年 2月 6日颁布了信息保障的实施的指令 8500.2 。
电子邮件 @263.net @x263.net
自动提款机
电话卡,IP卡,201电话卡
银行取钱
信用卡购物密码从军事走向生活
密码学 (Cryptology),是研究信息系统安全保密的科学,
密码编码学 (Cryptography),主要研究对信息进行编码,实现对信息的隐蔽,
密码分析学 (Cryptanalytics):主要研究加密消息的破译或消息的伪造,
基本概念
消息被称为 明文 (Plaintext)。用某种方法伪装消息以隐藏它的内容的过程称为 加密 (Encrtption)，被加密的消息称为 密文 (Ciphertext)，而把密文转变为明文的过程称为 解密 (Decryption)。
对明文进行加密操作的人员称作 加密员 或 密码员
(Cryptographer).
密码算法 (Cryptography Algorithm):是用于加密和解密的数学函数。
密码员对明文进行加密操作时所采用的一组规则称作加密算法 (Encryption Algorithm).
所传送消息的预定对象称为 接收者 (Receiver).
接收者对密文解密所采用的一组规则称为 解密算法
(Decryption Algorithm).
基本术语加解密过程示意图
加密和解密算法的操作通常都是在一组密钥的控制下进行的,分别称为 加密密钥 (Encryption
Key) 和 解密密钥 (Decryption Key),
明文 明文密文加密算法 解密算法密钥 密钥密码学的目的,Alice和 Bob两个人在不安全的信道上进行通信，而破译者 Oscar不能理解他们通信的内容。
加密通信的模型
Alice 加密机 解密机 Bob
安全信道密钥源
Oscar
x y x
k
密码体制,它是一个五元组（ P,C,K,E,D)满足条件：
（ 1） P是可能明文的有限集；（明文空间）
（ 2） C是可能密文的有限集；（密文空间）
（ 3） K是一切可能密钥构成的有限集；（密钥空间）
*（ 4）任意 k∈ K,有一个加密算法 和相应的解密算法,使得 和 分别为加密解密函数，满足 dk(ek(x))=x,这里 x ∈ P。
Eek?
Ddk? CPek?,PCd
k?:
密码体制
按照保密的内容分,
受限制的（ restricted)算法,算法的保密性基于保持算法的秘密。
基于密钥（ key-based)的算法,算法的保密性基于对密钥的保密。 ----现代密码理论密码算法分类 -i
基于密钥的算法，按照密钥的特点分类：
对称密码算法（ symmetric cipher)：又称 传统密码算法（ conventional cipher)，就是加密密钥和解密密钥相同，或实质上等同，即从一个易于推出另一个。又称 秘密密钥算法 或 单密钥算法 。
非对称密钥算法（ asymmetric cipher):加密密钥和解密密钥不相同，从一个很难推出另一个。又称 公开密钥算法（ public-key cipher) 。
公开密钥算法用一个密钥进行加密,而用另一个进行解密,其中的加密密钥可以公开,又称公开密钥（ public
key)，简称公钥,解密密钥必须保密,又称私人密钥
（ private key)私钥,简称 私钥 。
密码算法分类 -ii
按照明文的处理方法：
分组密码（ block cipher):将明文分成固定长度的组，用同一密钥和算法对每一块加密，输出也是固定长度的密文。
流密码（ stream cipher):又称 序列密码,序列密码每次加密一位或一字节的明文，也可以称为流密码。
序列密码是手工和机械密码时代的主流密码算法分类 -iii
对称密钥密码又可分为：
分组密码每次对一块数据加密多数网络加密应用
DES,IDEA,RC6,Rijndael
流密码每次对一位或一字节加密
One-time padding,Vigenére,Vernam
密码算法分类 -iv
公开密钥密码,
大部分是分组密码，只有概率密码体制属于流密码每次对一块数据加密数字签名,身份认证
RSA,ECC,ElGamal
加密解密速度慢密码算法分类 -v
三个阶段：
1949年之前密码学是一门艺术
1949～ 1975年密码学成为科学
1976年以后密码学的新方向 —— 公钥密码学密码学的起源和发展 -i
密码学的起源
隐写术 (steganography):
通过隐藏消息的 存在 来保护消息,
a,隐形墨水
b,字符格式的变化
c,图象图像
(象形文字的修改 )Modified Hieroglyphics,
c,1900 B.C.
密码学的第一个例子是对标准书写符号的修改例如,古埃及法老坟墓上的文字思想,代替 (substitution)
example-i
Spartan Scytale,c,500 B.C.
斯巴达人用于加解密的一种军事设备发送者把一条羊皮螺旋形地缠在一个圆柱形棒上思想：置换（ permutation)
example-ii
Polybius’ Checkerboard,205~123 B.C.
明文,POLYBIUS
密文,3534315412244543
1 2 3 4 5
1 A B C D E
2 F G H IJ K
3 L M N O P
4 Q R S T U
5 V W X Y Z
example-iii
Caesar Cipher,c,50 B.C.
A B C D E F G …… X Y Z
D E F G H I J …… A B C
明文,Caesar cipher is a shift substitution
密文,FDHVDU FLSKHU LV D VKLIW
VXEVWLWXWLRQ
example-iV
Nomenclator 代码本 c.1400
字母、符号、单词、短语 代码
代码 字母、符号、单词、短语
应用,World War II
Example -V
Example –Con’t
网格加密法：中国
– 例：密文：
王先生：
来信收悉，你的盛情难以报答。我已在昨天抵达广州。秋雨连绵，每天需备伞一把。大约本月中旬即可返回，再谈。
弟：李明
2001年 11月 7日
网格加密法：中国
– 例：密文：
王先生：
来信收悉，你的盛情难以报答。我已在昨天抵达广州。秋雨连绵，每天需备伞一把。大约本月中旬即可返回，再谈。
弟：李明
2001年 11月 7日明文：情报在雨伞把中。
兽栏法：
– 明文,System
– 密文：
A B C
D E F
G H I
J,K.,L
M,N.,O
P,Q.,R
S,T:,U
V,W:,X
Y,Z:,.
：,,,,
密文字母表：
1949年之前,
古典密码（ classical cryptography)
密码学还不是科学,而是艺术
出现一些密码算法和加密设备
密码算法的基本手段 (substitution &
permutation)出现,针对的是字符
简单的密码分析手段出现密码学的起源和发展 -ii
1949～ 1975年,
计算机使得基于复杂计算的密码成为可能
1949年 Shannon的,The Communication Theory of
Secret Systems”
1967年 David Kahn的,The Codebreakers》
1971-73年 IBM Watson实验室 的 Horst Feistel等的几篇技术报告
Smith,J.L.,The Design of Lucifer,A Cryptographic Device for Data
Communication,1971
Smith,J.L.,…,An Expremental Application of Cryptogrphy to a
remotely Accessed Data System,Aug.1972
Feistel,H.,Cryptography and Computer Privacy,May 1973
数据的安全基于密钥而不是算法的保密密码学的起源和发展 -iii
1976年以后,
1976年 Diffie & Hellman的,New Directions
in Cryptography”提出了不对称密钥密码
1977年 Rivest,Shamir & 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
原则。最常见的破解类型如下：
1.唯密文攻击,Oscar具有密文串 y.
2.已知明文攻击,Oscar具有明文串 x和相应的密文 y.
3.选择明文攻击,Oscar可获得对加密机的暂时访问,因此他能选择明文串 x并构造出相应的密文串 y。
4.选择密文攻击,Oscar可暂时接近密码机,可选择密文串 y，并构造出相应的明文 x.
这一切的目的在于 破译出密钥或密文密码分析
密码破译的原则,遵循观察与经验
方法,采用归纳与演绎
步骤,分析、假设、推测和证实
三大要素：
– 语言的频率特征,e
– 连接特征,q …u,I e x,
– 重复特征,th,tion,tious
密码破译
无条件安全（ Unconditionally secure）
无论破译者有多少密文,他也无法解出对应的明文,即使他解出了,他也无法验证结果的正确性,
Onetime pad
计算上安全（ Computationally secure）
破译的代价超出信息本身的价值
破译的时间超出了信息的有效期
破译需要的存储空间超过了目前的资源密码算法的安全性攻击方法的复杂性
（ 1） 数据复杂性
（ 2） 时间复杂性
（ 3） 空间复杂性
RSA算法
1977年由 Ron Rivest,Adi Shamir和 Len Adleman
发明,1978年公布
是一种分组加密算法。
– 明文和密文在 0~n-1之间,n是一个正整数
应用最广泛的公钥密码算法
只在美国申请专利，且已于 2000年 9月到期
RSA算法描述
RSA加,解密算法 (1978 Rivest,Shamir,Adelman)
分组大小为 k,2k < n? 2k+1
公开密钥 n（ 两素数 p和 q的乘积 ） （ 推荐 p,q等长 ）
e（ 与 (p-1)(q-1)互素 ）
ed?1(mod(p-1)(q-1))
私人密钥 d（ e-1 mod(p-1)(q-1) )
加密 c=me mod n
解密 m=cdmod n
)( m o d
)( m o d1
)(
)1)(1(
nm
nm
mm
mmc
i
i
qpk
i
ed
i
de
i
d
i
i
RSA密钥生成原理
令 n=pq,p?q都是素数,?(n)=(p-1)(q-1)是 n的 Euler
数
Euler定理推论,
若 n=pq,p?q都是素数,k是任意整数,则
mk(p-1)(q-1)+1? m mod n,对任意 0?m?n
只要选择 e,d,满足 ed=k?(n)+1,即
ed? 1 mod?(n)? d? e-1 mod?(n)
公钥,KU={e,n},私钥,KR={d,n}
example
（ 1）若 Bob选择了 p=101和 q＝ 113
（ 2）那么,n=11413,? (n)=100× 112＝ 11200；
（ 3）然而 11200＝ 26× 52× 7，一个正整数 e能用作加密指数，
当且仅当 e不能被 2,5,7所整除。假设 Bob选择了 e=3533，
（ 4）那么用 Euclidean算法将求得：
d=e -1? 6597(mod 11200),于是 Bob的解密密钥 d=6597.
（ 5） Bob在一个目录中公开 n=11413和 e=3533
（ 6）现假设 Alice想发送明文 9726给 Bob，她计算：
97263533(mod 11413)=5761，且在一个信道上发送密文 5761。
（ 7）当 Bob接收到密文 5761时，他用他的秘密解密指数
（私钥） d＝ 6597进行解密,57616597（ mod 11413)=9726
RSA安全性依据
RSA的安全性是基于加密函数 ek(x)=xe(mod n)是一个单向函数，所以对攻击的人来说求逆计算不可行。
而 Bob能解密的陷门是分解 n=pq，知? (n)=(p-1)(q-1)。
从而用欧氏算法解出解密私钥 d.
（猜想：攻破 RSA与分解 n是多项式等价的。然而，这个猜想至今没有给出可信的证明！！！）
每个合数都可以唯一地分解出素数因子
6 = 2 ·3
999999 = 3·3·3·7·11·13·37
27641 = 131·121
从 2 开始试验每一个小于等于 √27641 的素数。
素数：只能被 1和它本身整除的自然数；否则为合数。
整数 n的十进制位数 因子分解的运算次数 所需计算时间（每微秒一次）
50 1.4x1010 3.9小时
75 9.0x1012 104天
100 2.3x1015 74年
200 1.2x1023 3.8x109年
300 1.5x1029 4.0x1015年
500 1.3x1039 4.2x1025年对 RSA的攻击方法
1,强力攻击（穷举法）：尝试所有可能的私有密钥
2、数学分析攻击：各种数学方法，等价与两个素数乘积的因子分解
3,对 RSA实现的攻击
90年代大数分解的进程分解数 尺寸 bits 分解日期 分解算法
RSA-100 330 1991.4 二次筛法
RSA-110 364 1992.4 二次筛法
RSA-120 397 1993.6 二次筛法
RSA-129 425 1994.4 二次筛法
RSA-130 430 1996.4 数域筛法
RSA-140 463 1999.2 数域筛法
RSA-155 512 1999.8 数域筛法
RSA-155的分解
1999.8.22，荷兰 H.Riele领导的来自 6个国家的研究人员组成的团队找到了一个 512-bit RSA
密钥的一个素因子
512-bit RSA在电子商务中所占的比例为 95%
用了 5个月的时间，计算机时间估计为
8000mips years
对 RSA的攻击
对 RSA的具体实现存在一些攻击方法，但不是针对基本算法的，而是针对协议的。
对 RSA的选择密文攻击
对 RSA的公共模攻击
对 RSA的小加密指数攻击
对 RSA的小解密指数攻击
时间性攻击：取决于解密算法的运算时间对 RSA的选择密文攻击
例 1,E监听 A的通信，
收集由 A的公开密钥加密的密文 c,E想知道消息的明文 m,使
m=cd mod n
他首先选择随机数 r,使
r<n,然后用 A的公开密钥 e计算
x=re mod n
y=xc mod n
t=r-1 mod n
如果 x=re mod n，则
r=xd mod n
现在 E让 A对 y签名，即解密 y,A
向 E发送 u=yd mod n
而 E计算
tu mod n=r-1yd mod n
=r-1xdcd mod n
=cd mod n
=m
对 RSA的选择密文攻击
例 2,E 让 A对 m3签名。他产生两个消息 m1和
m2，满足
m3=m1m2(mod n)
如果 E能让 A分别对 m1和 m2签名，则可以计算
m3：
m3d=(m1d mod n)( m2d mod n)
注意：不要用 RSA对陌生人的随机文件签名，签名前先使用一个散列函数对 RSA的公共模攻击
一种可能的 RSA实现方法是给每个人相同的 n,但指数 d和 e不同。
问题：如果相同的消息曾用两个不同的指数加密，而这两个指数是互素的，则明文可以不用任何一个解密密钥来恢复。
令 m为明文消息，两个加密密钥为 e1,e2,两个密文消息为 c1,c2
c1=me1 mod n
c2=me2 mod n
由于 e1和 e2互素，所以可以用扩展的 Euclid算法找到 r,s使
re1+se2=1,
假设 r是负数，可以用扩展的 Euclid算法计算 c1-1,而
(c1-1)-r*c2s= m mod n
注意,不要让一群用户共享一个模 n
对 RSA的小加密指数攻击
如果使用一个较小的 e值，则进行 RSA签名和加密会很快，但也不安全。
如果用相同 e值的不同公开密钥加密 e(e+1)/2个线性相关的消息，则系统是可破的。如果有少于这些的消息或消息不相关，则无问题。
比如：消息为 mj,使用同样的指数 e,模数分别为
q1,q2,…q s（两两互素）,则密文为 mjemod q1,mjemod
q2,… m jemod qs，根据中国剩余定理,m'= mjemod
q1 q2… q s.可以计算出来，对于较小的 e，可以解出 mj。
解决办法：加密前将消息与随机值混合，并保证 m与 n
有相同的长度。
对 RSA的小解密指数攻击
使用较小的 d会产生穷尽解密攻击的可能
当 d为 n的 1/4长度时，而 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(0<e<? (n))，满足（ e,? (n)）＝ 1
(4)Bob使用辗转相除法计算 d=e-1(mod? (n))
(5)Bob在目录中公开 n和 e作为她的公开钥。
选好这些参数后，将明文划分成块，使得每个明文报文 P长度 m满足 0<m<n。加密 P时，计算 C＝ Pe(mod n)，解密 C时计算 P＝ Cd(mod n)。由于模运算的对称性，可以证明，
在确定的范围内，加密和解密函数是互逆的。
为实现加密，需要公开 (e,n)，为实现解密需要 (d,n)。
实现要求
于是要求：若使 RSA安全,p与 q必为足够大的素数，使分析者没有办法在多项式时间内将 n分解出来。建议选择 p和 q大约是 100位的十进制素数。 模 n的长度要求至少是 512比特。 EDI攻击标准使用的 RSA算法中规定 n的长度为 512至
1024比特位之间，但必须是 128的倍数。国际数字签名标准 ISO/IEC 9796中规定 n的长度位 512
比特位,至 1996年，建议使用 768位的模 n。
素数的选取
为了抵抗现有的整数分解算法，对 RSA模 n的素因子
p和 q还有如下要求：
(1)|p-q|很大，通常 p和 q的长度相同；
(2)p-1 和 q-1分别含有大素因子 p1和 q1
(3)P1-1和 q1-1分别含有大素因子 p2和 q2
(4)p+1和 q+1分别含有大素因子 p3和 q3
加密指数 e的选取
为了提高加密速度，通常取 e为特定的小整数，
如 EDI国际标准中规定 e＝ 216＋ 1，
ISO/IEC9796中甚至允许取 e＝ 3。这时加密速度一般比解密速度快 10倍以上。
e＝ 216＋ 1优于 e＝ 3之处在于它能够抵抗对 RSA
的小加密指数攻击实现中的问题
（ 1）如何计算 ab mod n
（ 2）如何判定一个给定的整数是素数？
（ 3）如何找到足够大的素数 p和 q?
(1)
要点 1,(a x b) mod n = [(a mod n) x (b mod n)] mod n]
要点 2,a16=aaaaaaaaaaaaaaaa
=a2,a4,a8,a16
更一般性的问题,am
m的二进制表示为 bkbk-1…b 0,则 m=?2ii?0
c?0; d?1
for i?k downto 0
do c?2 x c
d?(d? d) mod n
if bi = 1
then c? c + 1
d? (d? a) mod n
return d
计算 am mod n
am mod n = [? a(2i)] mod n
=?[ a(2i) mod n]
bi?0
bi?0
检测素数
直接判断一个整数是否为素数是困难的
命题,如果 p是素数,则方程
x2? 1 mod p
只有平凡解 x1 mod p.
证明,x2? 1 mod p
p|(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+1
x? 1 mod p,或者 x? -1 mod p
若方程 x2? 1 mod p存在的解不是 x1,则 P不是素数。
(2)目前还没有一个高效的办法，实际中应用最多
Miller and Rabin,WITNESS算法
WITNESS(a,n) 判定 n 是否为素数,a是某些小于 n的整数
1,令 bkbk-1…b 0 为 (n-1)的二进制表示，
2,d? 1
3,for i? k downto 0
4,do x?d
5,d? (d? d) mod n
6,if d = 1 and x? 1 and x? n-1
7,then return TRUE
8,if bi = 1
9,then d? (d? a) mod n
10,if d? 1
11,then return TRUE
12,return FALSE
返回值：
TRUE,n一定 不是素数
FALSE,n可能是素数应用：
随机选择 a < n,计算 s次，
如果每次都返回 FALSE，
则这时 n是素数的概率为
(1 - 1/2s)
(3)通常的办法是随机选取一个大的奇数，然后进行素性检验
1,随机选一个奇数 n (如,可使用伪随机数发生器 )
2,随机选择一个整数 a < n
3,执行概率素数判定测试 (如,用 WITNESS(a,n)),如果 n 未测试通过,则拒绝数值 n,转向步骤 1
4,如果 n已通过足够的测试,则接受 n,否则转向步骤 2;
说明：① 随机选取大约用 ln(N)/2的次数，如 ln(2200)/2=70
② 好在生成密钥对时才用到，慢一点还可忍受。
③ 确定素数 p和 q以后，只需选取 e,满足 gcd(e,?(n))=1,计算
d = e-1 mod?(n) （ sieve扩展的欧拉算法）
yuchunwu99@hotmail.com
什么是信息安全?
通信保密 （ COMSEC）,60-70年代信息保密信息安全 （ INFOSEC）,80-90年代机密性、完整性、可用性、不可否认性 等信息保障 （ IA）,90年代 -
基本的通讯模型
通信的保密模型通信安全 -60年代（ COMSEC）
发方 收方信源编码 (纠错码 )
信道编码信道传输通信协议发方 收方敌人 信源编码信道编码信道传输通信协议密码
60-70年代
这一时期主要关注,机密性,
40年代以前,通信安全（ COMSEC）,
也称,通信保密,
40年代增加了,电子安全,
50年代欧美国家将,通信安全,和
,电子安全,合称为,信号安全
（ SIGSEC）,
密码学是解决,通信安全,的重要技术
密码学是解决,机密性,的核心技术，
这一时期密码学得到了很好的发展。
Shannon于 1949年发表的论文,保密系统的信息理论,为对称密码学建立了理论基础，从此密码学从 非科学 发展成为一门科学。
1965年美国率先提出了 计算机安全（ COMPUSEC）
这一时期主要关注,机密性、访问控制、认证,
60年代出现了多用户系统，从而引入了受控共享的问题。此时计算机主要用于军方,1969年的 Ware报告初步的提出了计算机安全及其评估问题。研究方面，出现了
Adept50和 multics操作系统上的安全研究工作。
70年代是计算机安全的奠基时代。 1972年 Anderson带领的小组完成了著名的 Anderson报告，这个报告可以看作是计算机安全发展的里程碑。其中提出了计算机安全的主要问题以及相关的范型（如访问监控机）。在这一阶段计算机主要用于军方与科研，而访问控制方面关注信息的机密性，这时提出了强制访问控制策略和自主访问控制策略。其间进行的重要工作包括访问控制矩阵的提出,BLP模型,BIBA模型,HRU模型。其中,BLP模型是影响深远的强制访问控制模型,BIBA模型是提出较早的完整性模型，而 HRU模型给出了形式化的访问控制矩阵的描述，并提出了安全模型领域中著名的 SAFTY问题（授权传播的可判定性问题）。
这一时期现代密码学得到了快速发展，最有影响的两个大事件是：一件是 Diffiee和 Hellman于 1976年发表的论文,密码编码学新方向,,该文导致了密码学上的一场革命，他们首次证明了在发送者和接收者之间无密钥传输的保密通信是可能的，从而开创了公钥密码学的新纪元；另一件是 美国于 1977年制定的数据加密标准 DES。
这两个事件标志着现代密码学的诞生。
信息安全的三个基本方面
– 保密性 Confidentiality
即保证信息为授权者享用而不泄漏给未经授权者 。
– 完整性 Integrity
数据完整性，未被未授权篡改或者损坏
系统完整性，系统未被非授权操纵，按既定的功能运行
– 可用性 Availability
即保证信息和信息系统随时为授权者提供服务，而不要出现非授权者滥用却对授权者拒绝服务的情况信息安全的含义
(80-90年代 )
80年代的一个标志性特征就是计算机安全的标准化工作。美国军方提出了著名的 TCSEC标准，为计算机安全评估奠定了基础。在这之后又陆续发表了 TNI,TDI等 TCSEC解释性评估标准。标准化的工作带动了安全产品的大量出现。
80年代的另一个标志性特征就是计算机在商业环境中得到了应用，
所以访问控制的研究也不可避免的要涉及到商业安全策略。而
Clark-wilson和 Chinese wall策略模型是典型的代表。
入侵检测系统（ IDS）概念最早出自于 Anderson在 1972年的一项报告。 1980年,Anderson为美国空军做的题为,计算机安全威胁监控与监视,的技术报告，第一次详细地阐述了入侵检测的概念，
并首次为入侵和入侵检测提出了一个统一的架构。
80年代初，安全协议理论如安全多方计算、形式化分析和可证明安全性等相继问世
这一时期主要关注“机密性、完整性、可用性、可控性、非否认性”
80年代中期，美国和欧洲先后在学术界和军事领域开始使用,信息安全（ INFOSEC）,和,信息系统安全（ INFO SYS SEC或
ISSEC）,。
主要内容包括：
通信安全
计算机安全
发射安全（ EMSEC）
传输安全（ TRANSEC）
物理安全（ PHYSICALSEC）
人事安全（ PERSONNEL SEC）
密码技术得到了空前的发展,提出了很多新观点和新方法如 ECC、
密钥托管、盲签名、零知识证明协议
涌现了大量的实用安全协议，如互联网密钥交换（ IKE）协议、分布式认证安全服务（ DASS）协议,Kerberos认证协议,X.509协议,SET协议,iKP协议
安全协议的三大理论（ 安全多方计算、形式化分析和可证明安全性 ）取得了突破性进展
IDS的研究进入了多样化发展时期
1989年提出了异常检测概念
1990年形成了基于网络的 IDS和基于主机的 IDS两大检测概念
1992年形成了分布式入侵检测系统（ DIDS）
1994年，将自治代理（ Autonomous Agents）技术用于 IDS的设计
1996年为了解决入侵检测系统的可扩展性提出了 GRIDS(Graph-
based Intrusion Detection System)
安全评估标准得到高度重视。从美国国防部 1985年发布著名的可信计算机系统评估准则（ TCSEC）起，世界各国根据自己的研究进展和实际情况，
相继发布了一系列有关安全评估的准则和标准，如美国的 TCSEC；英、
法、德、荷等四国 90年代初发布的信息技术安全评估准则 (ITSEC)；加拿大 1993年发布的可信计算机产品评价准则（ CTCPEC）；美国 1993年制定的信息技术安全联邦标准（ FC）； 6国 7方（加拿大、法国、德国、荷兰、
英国、美国 NIST及美国 NSA）于 90年代中期提出的信息技术安全性评估通用准则（ CC）
计算机应急响应受到重视。
1988年，美国康乃尔大学研究生莫里斯，首次利用计算机病毒（蠕虫）程序成功攻击了美国国防军事科研单位与有关大专院校联入因特网的 6000台计算机（占当时因特网联机的 1/10），使其瘫痪数日，造成近亿元损失
1989年，美国、西德联手破获了前苏联收买西德大学生中的黑客，渗入欧美十余个国家的计算机，获取大量敏感信息的计算机间谍案。
这两起案件，极大地震动了西方世界。许多有识之士认为：随着网络技术及有关技术的发展,
传统的、静态的安全保密措施已不足以抵御计算机黑客入侵及有组织的信息手段的攻击（信息战、网络战），必须建立新的安全机制
于是在 1989年美国国防部资助卡内基 —梅隆大学为其建立了世界上第一个“计算机应急小组
（ CERT）”及其协调中心（ CERT/CC）。 CERT的成立标志着信息安全由静态保护向动态防护的转变。
美国人提出的概念,
Information Assurance
保护 （ Protect）
检测 （ Detect）
反应 （ React）
恢复 （ Restore）
保护
Protect
检测
Detect
反应
React
恢复
Restore
信息保障
这一时期主要关注“预警、保护、检测、响应、恢复、反击”整个过程
信息安全保障强调保护、检测、反应和恢复这四种能力，围绕人、
技术和管理这三个层面，以支持机构的任务和职能为目标，注重体系建设，强化组织与协调功能。
1995年，在研究信息安全及网络战防御理论过程中，美国国防部提出了“信息安全保障体系”（ IA）概念，并给出了“保护
（ Protection） —监测（ detection） —响应（ Response）”三环节动态模型，即,PDR”模型。后来增加了恢复（ Restore）,变为
,PDRR”模型。其中“响应”包括平时事件响应和应急响应，而重点在应急处理。
我国专家在 1999年提出了更为完善的“保护 —预警（ Warning） —
监测 —应急 —恢复 —反击（ Counter-attack）”即,PWDRRC”模型，使信息安全保障技术体系立于更坚实的基础上。
信息安全保障体系的建设是一项长期而艰巨的任务
当前，人们从以下几个方面致力于建立信息安全保障体系
组织管理体系：做顶层设计
技术与产品体系,密码、安全监控、安全审计、内容安全、授权认证、检测、可信计算、病毒防范、网络攻击、安全评估、应急处理
标准体系
法规体系
人才培养、培训与服务咨询体系
应急处理体系
美国：
1998年 10月,NSA颁布了信息保障技术框架（ IATF） 1.1版,1999
年 9月,2000年 9月分别颁布了 2.0和 3.0版。本来 4.0版应在 2001年 9
月出台，可能受到,911”事件影响，到 2002年 9月，才颁布了 3.1
版本。信息保障技术框架的研究和不断完善表明了美国军政各方对信息保障的认识逐步趋于一致。
美国国防部 2002年 10月 24日颁布了信息保障训令 8500.1，并于
2003年 2月 6日颁布了信息保障的实施的指令 8500.2 。
美国：
1998年 10月,NSA颁布了信息保障技术框架（ IATF） 1.1版,1999
年 9月,2000年 9月分别颁布了 2.0和 3.0版。本来 4.0版应在 2001年 9
月出台，可能受到,911”事件影响，到 2002年 9月，才颁布了 3.1
版本。信息保障技术框架的研究和不断完善表明了美国军政各方对信息保障的认识逐步趋于一致。
美国国防部 2002年 10月 24日颁布了信息保障训令 8500.1，并于
2003年 2月 6日颁布了信息保障的实施的指令 8500.2 。
电子邮件 @263.net @x263.net
自动提款机
电话卡,IP卡,201电话卡
银行取钱
信用卡购物密码从军事走向生活
密码学 (Cryptology),是研究信息系统安全保密的科学,
密码编码学 (Cryptography),主要研究对信息进行编码,实现对信息的隐蔽,
密码分析学 (Cryptanalytics):主要研究加密消息的破译或消息的伪造,
基本概念
消息被称为 明文 (Plaintext)。用某种方法伪装消息以隐藏它的内容的过程称为 加密 (Encrtption)，被加密的消息称为 密文 (Ciphertext)，而把密文转变为明文的过程称为 解密 (Decryption)。
对明文进行加密操作的人员称作 加密员 或 密码员
(Cryptographer).
密码算法 (Cryptography Algorithm):是用于加密和解密的数学函数。
密码员对明文进行加密操作时所采用的一组规则称作加密算法 (Encryption Algorithm).
所传送消息的预定对象称为 接收者 (Receiver).
接收者对密文解密所采用的一组规则称为 解密算法
(Decryption Algorithm).
基本术语加解密过程示意图
加密和解密算法的操作通常都是在一组密钥的控制下进行的,分别称为 加密密钥 (Encryption
Key) 和 解密密钥 (Decryption Key),
明文 明文密文加密算法 解密算法密钥 密钥密码学的目的,Alice和 Bob两个人在不安全的信道上进行通信，而破译者 Oscar不能理解他们通信的内容。
加密通信的模型
Alice 加密机 解密机 Bob
安全信道密钥源
Oscar
x y x
k
密码体制,它是一个五元组（ P,C,K,E,D)满足条件：
（ 1） P是可能明文的有限集；（明文空间）
（ 2） C是可能密文的有限集；（密文空间）
（ 3） K是一切可能密钥构成的有限集；（密钥空间）
*（ 4）任意 k∈ K,有一个加密算法 和相应的解密算法,使得 和 分别为加密解密函数，满足 dk(ek(x))=x,这里 x ∈ P。
Eek?
Ddk? CPek?,PCd
k?:
密码体制
按照保密的内容分,
受限制的（ restricted)算法,算法的保密性基于保持算法的秘密。
基于密钥（ key-based)的算法,算法的保密性基于对密钥的保密。 ----现代密码理论密码算法分类 -i
基于密钥的算法，按照密钥的特点分类：
对称密码算法（ symmetric cipher)：又称 传统密码算法（ conventional cipher)，就是加密密钥和解密密钥相同，或实质上等同，即从一个易于推出另一个。又称 秘密密钥算法 或 单密钥算法 。
非对称密钥算法（ asymmetric cipher):加密密钥和解密密钥不相同，从一个很难推出另一个。又称 公开密钥算法（ public-key cipher) 。
公开密钥算法用一个密钥进行加密,而用另一个进行解密,其中的加密密钥可以公开,又称公开密钥（ public
key)，简称公钥,解密密钥必须保密,又称私人密钥
（ private key)私钥,简称 私钥 。
密码算法分类 -ii
按照明文的处理方法：
分组密码（ block cipher):将明文分成固定长度的组，用同一密钥和算法对每一块加密，输出也是固定长度的密文。
流密码（ stream cipher):又称 序列密码,序列密码每次加密一位或一字节的明文，也可以称为流密码。
序列密码是手工和机械密码时代的主流密码算法分类 -iii
对称密钥密码又可分为：
分组密码每次对一块数据加密多数网络加密应用
DES,IDEA,RC6,Rijndael
流密码每次对一位或一字节加密
One-time padding,Vigenére,Vernam
密码算法分类 -iv
公开密钥密码,
大部分是分组密码，只有概率密码体制属于流密码每次对一块数据加密数字签名,身份认证
RSA,ECC,ElGamal
加密解密速度慢密码算法分类 -v
三个阶段：
1949年之前密码学是一门艺术
1949～ 1975年密码学成为科学
1976年以后密码学的新方向 —— 公钥密码学密码学的起源和发展 -i
密码学的起源
隐写术 (steganography):
通过隐藏消息的 存在 来保护消息,
a,隐形墨水
b,字符格式的变化
c,图象图像
(象形文字的修改 )Modified Hieroglyphics,
c,1900 B.C.
密码学的第一个例子是对标准书写符号的修改例如,古埃及法老坟墓上的文字思想,代替 (substitution)
example-i
Spartan Scytale,c,500 B.C.
斯巴达人用于加解密的一种军事设备发送者把一条羊皮螺旋形地缠在一个圆柱形棒上思想：置换（ permutation)
example-ii
Polybius’ Checkerboard,205~123 B.C.
明文,POLYBIUS
密文,3534315412244543
1 2 3 4 5
1 A B C D E
2 F G H IJ K
3 L M N O P
4 Q R S T U
5 V W X Y Z
example-iii
Caesar Cipher,c,50 B.C.
A B C D E F G …… X Y Z
D E F G H I J …… A B C
明文,Caesar cipher is a shift substitution
密文,FDHVDU FLSKHU LV D VKLIW
VXEVWLWXWLRQ
example-iV
Nomenclator 代码本 c.1400
字母、符号、单词、短语 代码
代码 字母、符号、单词、短语
应用,World War II
Example -V
Example –Con’t
网格加密法：中国
– 例：密文：
王先生：
来信收悉，你的盛情难以报答。我已在昨天抵达广州。秋雨连绵，每天需备伞一把。大约本月中旬即可返回，再谈。
弟：李明
2001年 11月 7日
网格加密法：中国
– 例：密文：
王先生：
来信收悉，你的盛情难以报答。我已在昨天抵达广州。秋雨连绵，每天需备伞一把。大约本月中旬即可返回，再谈。
弟：李明
2001年 11月 7日明文：情报在雨伞把中。
兽栏法：
– 明文,System
– 密文：
A B C
D E F
G H I
J,K.,L
M,N.,O
P,Q.,R
S,T:,U
V,W:,X
Y,Z:,.
：,,,,
密文字母表：
1949年之前,
古典密码（ classical cryptography)
密码学还不是科学,而是艺术
出现一些密码算法和加密设备
密码算法的基本手段 (substitution &
permutation)出现,针对的是字符
简单的密码分析手段出现密码学的起源和发展 -ii
1949～ 1975年,
计算机使得基于复杂计算的密码成为可能
1949年 Shannon的,The Communication Theory of
Secret Systems”
1967年 David Kahn的,The Codebreakers》
1971-73年 IBM Watson实验室 的 Horst Feistel等的几篇技术报告
Smith,J.L.,The Design of Lucifer,A Cryptographic Device for Data
Communication,1971
Smith,J.L.,…,An Expremental Application of Cryptogrphy to a
remotely Accessed Data System,Aug.1972
Feistel,H.,Cryptography and Computer Privacy,May 1973
数据的安全基于密钥而不是算法的保密密码学的起源和发展 -iii
1976年以后,
1976年 Diffie & Hellman的,New Directions
in Cryptography”提出了不对称密钥密码
1977年 Rivest,Shamir & 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
原则。最常见的破解类型如下：
1.唯密文攻击,Oscar具有密文串 y.
2.已知明文攻击,Oscar具有明文串 x和相应的密文 y.
3.选择明文攻击,Oscar可获得对加密机的暂时访问,因此他能选择明文串 x并构造出相应的密文串 y。
4.选择密文攻击,Oscar可暂时接近密码机,可选择密文串 y，并构造出相应的明文 x.
这一切的目的在于 破译出密钥或密文密码分析
密码破译的原则,遵循观察与经验
方法,采用归纳与演绎
步骤,分析、假设、推测和证实
三大要素：
– 语言的频率特征,e
– 连接特征,q …u,I e x,
– 重复特征,th,tion,tious
密码破译
无条件安全（ Unconditionally secure）
无论破译者有多少密文,他也无法解出对应的明文,即使他解出了,他也无法验证结果的正确性,
Onetime pad
计算上安全（ Computationally secure）
破译的代价超出信息本身的价值
破译的时间超出了信息的有效期
破译需要的存储空间超过了目前的资源密码算法的安全性攻击方法的复杂性
（ 1） 数据复杂性
（ 2） 时间复杂性
（ 3） 空间复杂性
RSA算法
1977年由 Ron Rivest,Adi Shamir和 Len Adleman
发明,1978年公布
是一种分组加密算法。
– 明文和密文在 0~n-1之间,n是一个正整数
应用最广泛的公钥密码算法
只在美国申请专利，且已于 2000年 9月到期
RSA算法描述
RSA加,解密算法 (1978 Rivest,Shamir,Adelman)
分组大小为 k,2k < n? 2k+1
公开密钥 n（ 两素数 p和 q的乘积 ） （ 推荐 p,q等长 ）
e（ 与 (p-1)(q-1)互素 ）
ed?1(mod(p-1)(q-1))
私人密钥 d（ e-1 mod(p-1)(q-1) )
加密 c=me mod n
解密 m=cdmod n
)( m o d
)( m o d1
)(
)1)(1(
nm
nm
mm
mmc
i
i
qpk
i
ed
i
de
i
d
i
i
RSA密钥生成原理
令 n=pq,p?q都是素数,?(n)=(p-1)(q-1)是 n的 Euler
数
Euler定理推论,
若 n=pq,p?q都是素数,k是任意整数,则
mk(p-1)(q-1)+1? m mod n,对任意 0?m?n
只要选择 e,d,满足 ed=k?(n)+1,即
ed? 1 mod?(n)? d? e-1 mod?(n)
公钥,KU={e,n},私钥,KR={d,n}
example
（ 1）若 Bob选择了 p=101和 q＝ 113
（ 2）那么,n=11413,? (n)=100× 112＝ 11200；
（ 3）然而 11200＝ 26× 52× 7，一个正整数 e能用作加密指数，
当且仅当 e不能被 2,5,7所整除。假设 Bob选择了 e=3533，
（ 4）那么用 Euclidean算法将求得：
d=e -1? 6597(mod 11200),于是 Bob的解密密钥 d=6597.
（ 5） Bob在一个目录中公开 n=11413和 e=3533
（ 6）现假设 Alice想发送明文 9726给 Bob，她计算：
97263533(mod 11413)=5761，且在一个信道上发送密文 5761。
（ 7）当 Bob接收到密文 5761时，他用他的秘密解密指数
（私钥） d＝ 6597进行解密,57616597（ mod 11413)=9726
RSA安全性依据
RSA的安全性是基于加密函数 ek(x)=xe(mod n)是一个单向函数，所以对攻击的人来说求逆计算不可行。
而 Bob能解密的陷门是分解 n=pq，知? (n)=(p-1)(q-1)。
从而用欧氏算法解出解密私钥 d.
（猜想：攻破 RSA与分解 n是多项式等价的。然而，这个猜想至今没有给出可信的证明！！！）
每个合数都可以唯一地分解出素数因子
6 = 2 ·3
999999 = 3·3·3·7·11·13·37
27641 = 131·121
从 2 开始试验每一个小于等于 √27641 的素数。
素数：只能被 1和它本身整除的自然数；否则为合数。
整数 n的十进制位数 因子分解的运算次数 所需计算时间（每微秒一次）
50 1.4x1010 3.9小时
75 9.0x1012 104天
100 2.3x1015 74年
200 1.2x1023 3.8x109年
300 1.5x1029 4.0x1015年
500 1.3x1039 4.2x1025年对 RSA的攻击方法
1,强力攻击（穷举法）：尝试所有可能的私有密钥
2、数学分析攻击：各种数学方法，等价与两个素数乘积的因子分解
3,对 RSA实现的攻击
90年代大数分解的进程分解数 尺寸 bits 分解日期 分解算法
RSA-100 330 1991.4 二次筛法
RSA-110 364 1992.4 二次筛法
RSA-120 397 1993.6 二次筛法
RSA-129 425 1994.4 二次筛法
RSA-130 430 1996.4 数域筛法
RSA-140 463 1999.2 数域筛法
RSA-155 512 1999.8 数域筛法
RSA-155的分解
1999.8.22，荷兰 H.Riele领导的来自 6个国家的研究人员组成的团队找到了一个 512-bit RSA
密钥的一个素因子
512-bit RSA在电子商务中所占的比例为 95%
用了 5个月的时间，计算机时间估计为
8000mips years
对 RSA的攻击
对 RSA的具体实现存在一些攻击方法，但不是针对基本算法的，而是针对协议的。
对 RSA的选择密文攻击
对 RSA的公共模攻击
对 RSA的小加密指数攻击
对 RSA的小解密指数攻击
时间性攻击：取决于解密算法的运算时间对 RSA的选择密文攻击
例 1,E监听 A的通信，
收集由 A的公开密钥加密的密文 c,E想知道消息的明文 m,使
m=cd mod n
他首先选择随机数 r,使
r<n,然后用 A的公开密钥 e计算
x=re mod n
y=xc mod n
t=r-1 mod n
如果 x=re mod n，则
r=xd mod n
现在 E让 A对 y签名，即解密 y,A
向 E发送 u=yd mod n
而 E计算
tu mod n=r-1yd mod n
=r-1xdcd mod n
=cd mod n
=m
对 RSA的选择密文攻击
例 2,E 让 A对 m3签名。他产生两个消息 m1和
m2，满足
m3=m1m2(mod n)
如果 E能让 A分别对 m1和 m2签名，则可以计算
m3：
m3d=(m1d mod n)( m2d mod n)
注意：不要用 RSA对陌生人的随机文件签名，签名前先使用一个散列函数对 RSA的公共模攻击
一种可能的 RSA实现方法是给每个人相同的 n,但指数 d和 e不同。
问题：如果相同的消息曾用两个不同的指数加密，而这两个指数是互素的，则明文可以不用任何一个解密密钥来恢复。
令 m为明文消息，两个加密密钥为 e1,e2,两个密文消息为 c1,c2
c1=me1 mod n
c2=me2 mod n
由于 e1和 e2互素，所以可以用扩展的 Euclid算法找到 r,s使
re1+se2=1,
假设 r是负数，可以用扩展的 Euclid算法计算 c1-1,而
(c1-1)-r*c2s= m mod n
注意,不要让一群用户共享一个模 n
对 RSA的小加密指数攻击
如果使用一个较小的 e值，则进行 RSA签名和加密会很快，但也不安全。
如果用相同 e值的不同公开密钥加密 e(e+1)/2个线性相关的消息，则系统是可破的。如果有少于这些的消息或消息不相关，则无问题。
比如：消息为 mj,使用同样的指数 e,模数分别为
q1,q2,…q s（两两互素）,则密文为 mjemod q1,mjemod
q2,… m jemod qs，根据中国剩余定理,m'= mjemod
q1 q2… q s.可以计算出来，对于较小的 e，可以解出 mj。
解决办法：加密前将消息与随机值混合，并保证 m与 n
有相同的长度。
对 RSA的小解密指数攻击
使用较小的 d会产生穷尽解密攻击的可能
当 d为 n的 1/4长度时，而 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(0<e<? (n))，满足（ e,? (n)）＝ 1
(4)Bob使用辗转相除法计算 d=e-1(mod? (n))
(5)Bob在目录中公开 n和 e作为她的公开钥。
选好这些参数后，将明文划分成块，使得每个明文报文 P长度 m满足 0<m<n。加密 P时，计算 C＝ Pe(mod n)，解密 C时计算 P＝ Cd(mod n)。由于模运算的对称性，可以证明，
在确定的范围内，加密和解密函数是互逆的。
为实现加密，需要公开 (e,n)，为实现解密需要 (d,n)。
实现要求
于是要求：若使 RSA安全,p与 q必为足够大的素数，使分析者没有办法在多项式时间内将 n分解出来。建议选择 p和 q大约是 100位的十进制素数。 模 n的长度要求至少是 512比特。 EDI攻击标准使用的 RSA算法中规定 n的长度为 512至
1024比特位之间，但必须是 128的倍数。国际数字签名标准 ISO/IEC 9796中规定 n的长度位 512
比特位,至 1996年，建议使用 768位的模 n。
素数的选取
为了抵抗现有的整数分解算法，对 RSA模 n的素因子
p和 q还有如下要求：
(1)|p-q|很大，通常 p和 q的长度相同；
(2)p-1 和 q-1分别含有大素因子 p1和 q1
(3)P1-1和 q1-1分别含有大素因子 p2和 q2
(4)p+1和 q+1分别含有大素因子 p3和 q3
加密指数 e的选取
为了提高加密速度，通常取 e为特定的小整数，
如 EDI国际标准中规定 e＝ 216＋ 1，
ISO/IEC9796中甚至允许取 e＝ 3。这时加密速度一般比解密速度快 10倍以上。
e＝ 216＋ 1优于 e＝ 3之处在于它能够抵抗对 RSA
的小加密指数攻击实现中的问题
（ 1）如何计算 ab mod n
（ 2）如何判定一个给定的整数是素数？
（ 3）如何找到足够大的素数 p和 q?
(1)
要点 1,(a x b) mod n = [(a mod n) x (b mod n)] mod n]
要点 2,a16=aaaaaaaaaaaaaaaa
=a2,a4,a8,a16
更一般性的问题,am
m的二进制表示为 bkbk-1…b 0,则 m=?2ii?0
c?0; d?1
for i?k downto 0
do c?2 x c
d?(d? d) mod n
if bi = 1
then c? c + 1
d? (d? a) mod n
return d
计算 am mod n
am mod n = [? a(2i)] mod n
=?[ a(2i) mod n]
bi?0
bi?0
检测素数
直接判断一个整数是否为素数是困难的
命题,如果 p是素数,则方程
x2? 1 mod p
只有平凡解 x1 mod p.
证明,x2? 1 mod p
p|(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+1
x? 1 mod p,或者 x? -1 mod p
若方程 x2? 1 mod p存在的解不是 x1,则 P不是素数。
(2)目前还没有一个高效的办法，实际中应用最多
Miller and Rabin,WITNESS算法
WITNESS(a,n) 判定 n 是否为素数,a是某些小于 n的整数
1,令 bkbk-1…b 0 为 (n-1)的二进制表示，
2,d? 1
3,for i? k downto 0
4,do x?d
5,d? (d? d) mod n
6,if d = 1 and x? 1 and x? n-1
7,then return TRUE
8,if bi = 1
9,then d? (d? a) mod n
10,if d? 1
11,then return TRUE
12,return FALSE
返回值：
TRUE,n一定 不是素数
FALSE,n可能是素数应用：
随机选择 a < n,计算 s次，
如果每次都返回 FALSE，
则这时 n是素数的概率为
(1 - 1/2s)
(3)通常的办法是随机选取一个大的奇数，然后进行素性检验
1,随机选一个奇数 n (如,可使用伪随机数发生器 )
2,随机选择一个整数 a < n
3,执行概率素数判定测试 (如,用 WITNESS(a,n)),如果 n 未测试通过,则拒绝数值 n,转向步骤 1
4,如果 n已通过足够的测试,则接受 n,否则转向步骤 2;
说明：① 随机选取大约用 ln(N)/2的次数，如 ln(2200)/2=70
② 好在生成密钥对时才用到，慢一点还可忍受。
③ 确定素数 p和 q以后，只需选取 e,满足 gcd(e,?(n))=1,计算
d = e-1 mod?(n) （ sieve扩展的欧拉算法）
