1、 数论与信息安全 王晓峰深圳大学数学与计算科学学院 目录1.引言2.历史背景与若干基本概念3.1.引言 研究秘密通信 保证通信安全 1)分组密码分组密码（block ciphers）-第一类第一类对称密码对称密码 2)流密码流密码（stream ciphers）-第二类第二类对称密码对称密码密码分类密码分类（asymmetric ciphers）1)秘密密钥秘密密钥密码密码 2)公开密钥公开密钥密码密码（symmetric ciphers）1)分组密码（b l o c k c i p h e r s）-第一类对 1)数论知识数论知识2)群论基础群论基础 3)有限域有限域 4)信息论信息论 5)
2、概率论概率论 6)可计算理论可计算理论数学基础 1)数论知识 2)群论基础 3)有限域 4 2.历史背景与密码学基本概念 传输密文的发明地-古希 两次世界大战扮演重要角色 A r t h u r S c h .1 9 7 0-1 9 7 7：近代密码学与计算机技术、1 9 7 6:1 9 7 6 年W.D i f f i e 和M.H 2 0 0 0-?混沌密码？量子密码？密码学基本概念 如何达成秘密通信-密码编码学 如何 m:明文(Plaintext)c:密文(Ciphertext)加密(算法)：把明文经某种方式处理成他人难以 理解的密文.解密(算法)：将密文用特定的变换还原成明文.基本概念
3、 m:明文(P l a i n t e x t)加密(算法 )(mEc )(cDm 信道 m 加密 c c 解密 m 加密密钥 解密密钥 密钥(K):用以控制加密和解密的一定长度的符号串.采用密钥后，保密通信过程则为：密钥(K):用以控制加密和解密的一定长度的符号串.采用 例如：明文为during the last twenty years there has been an explosion of public academic research in cryptography K=5 例如：明文为K=5 加密算法：加密算法：1.将明文m按每5个字符分组：durin gthel asttw
4、 entyy earst hereh asbee nanex plosi onofp ublic acade micre searc hincr yptog raphy 2.每组反序得密文c：nirudlehtgwttsayytnetsraehereheebsaxenanisolppfonocilbuedacaercimcraesrcnihgotpyyhpar 加密算法：1.将明文m 按每5 个字符分组：1949年，Shannon 提出如下的安全问题：1.当破译者有无限制的时间和无限制的计算能力 时一个密码系统的安全性；2.当破译者在有限的时间和有限的计算能力时，一个密码系统的安全性.理论安全
5、与实际安全 1 9 4 9 年，S h a n n o n 提Turing machine&computability Turing machine:一个有限控制器；一条右端无限延长的输入带；一个能左右移动的读写头.计算复杂性T u r i n g m a c h i n e&c o m p u t a数论与信息安全课件Turing machine 的特点：的特点：非常简单的数学模型非常简单的数学模型；本质上类似于现代计算机本质上类似于现代计算机定义定义：一数论函数称为可计算当且仅当它是：一数论函数称为可计算当且仅当它是 Turing machine可计算可计算.T u r i n g m a
6、 c h i n e 的特点：非常简单的数学模型；计算问题分类 记一可计算问题的输入数据的二进制数串的长度为n,则计算此问题的时间(Turing machine 操作的次数)是一个n的函数f(n).如果 f(n)=a0+a1n+aknk则记f(n)=O(nk)，并称此问题是k次多项式时间内可计算的现实可计算的.计算问题的时间复杂性 记一可计算问题的输入数据的二进P问题：多项式时间内可计算；NP问题：在不确定性Turing machine上多项式时间内可计算,不确定性Turing machine能进行猜测,即不确定性Turing machine如能猜出一个解的话,则确定性Turing machi
7、ne在多项式时间内可校验解的正确性.显然：NPP P 与N P 问题P 问题：多项式时间内可计算；N P 问题：在不确定 3.1 3.1 带余除法带余除法:设a,b是整数，b0.则a可唯一地表为 a=bq+r其中q,r为整数并且0r1为整数，a,b为任意整数.如果 m|(ab)则称a和和b模模m同余同余，记为（称为同余式同余式）ab mod m3.3 同余类 设m 1 为整数，a,b 为任意整数.如果定理定理 3.7 若(a,m)=1,则a1 mod m 存在.例例3.2 求求 51 mod 13,和 111 mod 13.设m1为整数,a为任意整数.如果存在整数b 使得 ab 1 mod m
8、则称b为为a 模模m的的逆元逆元，记为 b a1 mod m习题习题 求求 51 mod 17.定理 3.7 若(a,m)=1,则a 1 m o d m 定理 3.8 模m 的同余关系是等价关系.定理 3.例例3.4 已知 427 mod 5,且1=(7,5),则 61 mod 5例例3.5 例3.4 已知 4 2 7 m o d 5,且1=(7,来自孙子算经的问题：“今有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二,问物几何?”如设x为其数，则有：725332modmodmodxxx 一般地，称 axb mod m 为线性同余式线性同余式.3.4 线性同余式 来自孙子算经的问题：如果
9、x1是线性同余式axb mod m的解，则对模m与x1同余的每一整数也是axb mod m的解.例例 易知x=5是 定理 3.1 2 如果x 1 是线性同余式a x b m o d 定理 3.1 3 设(a,m)=d.同余式 2211mbxmbxmodmod 有解的充分必要条件为 b1b2 mod d,d=gcdm1,m2 3.5 联立的线性同余式和中国剩余定理 定理 3.1 4 nnmbxmbxmbxmodmodmod2211 有解的充分必要条件为 mod gcd,ijijbbm m nji,21 定理定理 3.15 联立的线性同余式 定理 3.1 5 联立的线性同余式 中国剩余定理 5mo
10、d33mod22mod1xxx 例例 3.6 求解例 3.6 求解联立的线性同余式 习题1.求(937,576),并求整数p和q使得 (937,576)=937p+576q2.将23456表为16进制数.3.求求 51 mod 17.4.求解:习题1.求(9 3 7,5 7 6),并求整数p 和q 使得2 :3.6 欧拉定理和费尔玛定理 模m 的完全剩余集:设m0为一正整数,记(m)为小于m且与m互素的正整数的个数,并称其为m的欧拉函数.若m1，m2互素，则 (m1m2)=(m1)(m2)(1)欧拉函数 定理3.1 7 若m 1，m 2(2)欧拉定理定理3.1 9 (E u l e r)若a
11、与m例子：例子：例例3.9 求21 mod 11.例子：例3.9 求2 1 m o d 1 1.同余类方程 mbaxmod 有解的充分必要条件为 gcda,m|b，并且解为 mbaxmod 其中，a 为 a 模 m 的逆.(3)应用应用(3)应用例例3.11 解方程：7x22 mod 31习题习题 1.解方程：7x5 mod 23 2.求 31 mod 13.例3.1 1 解方程：习题 (Wilson)若p是素数，则 (p1)!1 mod p 反之，如果整数p满足上式，则p是素数.3.7 威尔森定理 定理 3.2 1(Wi l s o n)例子例子 设有下列同余式:x21,x22,x23,x2
12、4 mod 5求解?3.1.8 平方剩余 例子 设有下列同余式:若p是奇素数,p与a互素,则 x2a mod p 或无解,或有两个模p不同余的解.并且,如果1xp是一解,则 另一解为px.若p是奇素数,则1,2,.,p1正好有(p1)/2个是模p的平方剩余.即为：1,2,.,p1中模p与12,22,1/2(p1)2同余的数.引理 若p 是奇素数,p 与a 互素,则 例如例如：取p=11，求模11的平方剩余(1ap).例如：取p=1 1，求模1 1 的平方剩余(1 a p).4.公钥密码 4.1 引言 公开密钥密码学是密 原理：加密密钥和解密密钥不同，而且加密密钥公开，需要澄清的问题：l 不要误
13、认为公钥密码加密在防止例如利用求 mod p(素数)的离散对数的困难度:l 甲和乙在1，2，3，p1各中选取一 数作为x甲和x乙并计算 pbypbyxx mod mod 乙甲乙甲和 l 乙将y乙通知甲,而且甲将y甲通知乙;l 双方得到通信密钥:pbkxxmod 乙甲甲乙采用的技术的核心：基于单向陷门函数:加密容易,但解密却相（Rivest,Shamir&Adleman）基于：数论中的Euler 定理和因子分解问题是计算上困难的问题.4.2 RSA公钥密码（R i v e s t,S h a m i r&A d l e m a n）4.2 4.2.1 RSA 加密算法 操作过程：操作过程：1.取
14、两个充分大的素数p,q;2.计算n=pq(公开),和(n)=(p1)(q1)(保密)；3.随机选取整数e(公开)，满足 gcd(e,(n)=1；4.计算d(保密),满足de 1 mod(n)4.2.1 R S A 加密算法 操作过程：1.取两个充 4.2.2 R S A 加密算法对明文的加密过程：对明文的解例例 4.3 取p=43,q=59，并取e=13.则 n=pq=2537，(n)=4258=2436.解方程：de 1 mod 2436得 d=937.取m=73,则 7e=713=78747 2172=c mod 2436例 4.3 解方程：取m=7 3,则 7 e =7 1 3 =7 8
15、 4.2.3 RSA 的安全性 关键：关键：在于数n的因子分解)2(O222loglog)(lognn 目前最快的因子分解算法的计算复杂度为：即，如果数n=pq的因子分解被破，则可得 (n)=(p1)(q1),从而由加密密钥e可由下式解 得解密密钥：de1 mod(n)4.2.3 R S A 的安全性 关键：在于数n 的因子 从而，R S A 建议：这样的p,q 称为安全素数.注：1.知道n与(n)容易破解p,q:2.如果pq=k 较小,容易破解p,q:(n)=(p1)(q1)=pq(p+q)+1=n(p+q)(pq)2=(p+q)2 4pq (p+q)2(pq)2=4pq=4n (p+q)2
16、=4n+k2 p+q=(4n+k2)1/2,pq=k注：1.知道n 与(n)容易破解p,q:其它的公钥密码：1）Rabin公钥密码 2）Elgamal公钥密码 3）McEliece公钥密码 4）椭圆曲线(ECC)公钥密码其它的公钥密码：1）R a b i n 公钥密码 2）E 5.各种协议 5.1 数字签名协议 在文件上手RSA 数字签名数字签名:回忆回忆 RSA 加密加密 R S A 数字签名:回忆 R S A 加密 取两个充分大的素数pRSA 签名过程签名过程:R S A 签名过程:1.A 计算:S m d A m o d DSA(Digital Signature Algorithm)数
17、字签名数字签名:D S A(D i g i t a l S i g n a t u r e A l g o r i t hDSA(Digital Signature Algorithm)数字签名数字签名:D S A(D i g i t a l S i g n a t u r e A l g o r i t hDSA数字签名数字签名(继续继续):D S A 数字签名(继续):签名：1()()()()()()()()mod ()mod ()mod)mod (mod)mod H m trtH mrtH mxrtH mxrtH mxrk H mxrkgygyggpgpgpqgpqr 验证：6.量子计算
18、与量子密码学 爱因斯坦說 上 R.F e y n m a n 在八十年代提出利用量子现象來增加计光的偏振现象实验：准备一个强光源，三个分别为水平、4 3.(最奇异的一步):现在在偏光板A 和偏光板C 之 量子论对这些现象的解释是一个电子是可以“同時”出現在 我们知道,目前两个位元的存贮器，在一時刻只能表示 我们通过二维复向量空间中的一个单位向量来描述一个光子 对光子偏振的解释:.而当插入偏光板C 时 当我们再插入偏光板B(例如它测量状态|的光 6.2 量子密码学 量子通信利用量子力学的 6.2.1 量子密码学的产生 量子特性在信息领域中有 6.2.2 量子状态与编码 A l i c e 有两个
19、正交基选 A B A B A A B A A A A B B A B B B A A A B B A B B B A 6.2.3 A p r a c t i c a l e x a m p l e 1.Example contd 4.在另一个公共频道中A l i c e 告诉B o b 他的f i6.2.4 量子密码学的弱点目前此方法受到物理上的限制 6.实用例子：P G P 与电子邮件加密 由P h i P G P 的使用成爆炸性地增长,其原因为:P G P 提供如下五种服务:(1)认证.认证过程:(1)A l i c e 创建消 保密:(1)A l i c e 创建消息M 密钥 P G P 使用的密钥:P G P 中 密钥环:为了有效存储和组织密钥,同 密钥环:P G P 要求用户保持一个密1.公钥环 存放公钥.私钥环是PGP中存放个人私密的地方.当你产生一个密钥时，不能泄露的部分就存放在私钥环中.因为私钥不在人们中间传送，用户的钥环中唯一可能的密钥就是他自己和私钥.因为私钥环受到通过短语的保护，简单的密钥环内容传送不允许对密钥资料的访问.无论何时PGP需要选择一个私钥时，它都会选择密钥环的第一个密钥，这个密钥通常是最近创建的.你可以使用-u选项向PGP提供userid来修改它，这样PGP就会使用相应userid的密钥.2.私钥环 私钥环是P G P 中存放个人私密的地方.
