数论与信息安全课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《数论与信息安全课件.ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数论 信息 安全 课件
- 资源描述:
-
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
展开阅读全文