《2022年数学在密码中的某些应用整理 .pdf》由会员分享，可在线阅读，更多相关《2022年数学在密码中的某些应用整理 .pdf（3页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、盐城师范学院第 1 页 共 3 页数学在密码中的某些应用数学在密码学的发展过程中占有愈来愈重要的地位, 数学的许多分支在密码学中都有重要的应用 , 本文主要介绍代数（包括线性代数和抽象代数）、数论和组合数学在密码学中的某些应用。一 . 什么是密码学密码学是由保密通讯的需要而发展起来的一门科学。在保密通讯中 , 信息从发送到接收要经过如下过程： 发送者先将要发出的原始信息 （即真实的消息内容）一称为明文，进行某种方式的变化或变换一称为加密, 将加密后的信息一称为密文发送出去； 接收者收到密文后 , 将密文还原为明文一称为脱密， 脱密后得到明文 , 即原始信息。密文在传输的过程中（包括有线与无线的
2、传输方式）可能被窃取者截取 , 窃取者无法从截取的密文直接读出原始信息, 他在不知道加密算法的前提下 , 想方设法从密文中恢复出明文一种为破译或解密；破译的可能性取决于加密算法的好坏（这是有一定标准的）破译者水平( 包括破译者掌握的知识和他具有的经验 ) 以及科学技术发展的水平。实际上 , 在保密通讯中存在着两个重要的方面：一方面是提供通讯的保密方法, 即研究如何将发送的原始信息加密, 才能使窃取者不易破密；另一方面是对截取的别人的密文信息进行破译 , 以得到有用的原始信息。第一个方面称为密码编码学, 或简称为编码学； 第二个方面称为密码分析学或密码破译。这两个方面合起来构成密码学。编码学和密
3、码分析学有时称为孪生科学, 或称为互逆科学。在功能上 , 两者相互反映 , 其一所作为另一所解, 但两者所具有的特性基本上是不同的。下面我们主要谈数论、代数和组合数学在序列密码体制和公开密钥密码体制中的某些应用。二 . 有限域和组合数学在序列密码体制中的应用由于微电子学和数字通讯的发展, 序列密码体制至今仍广泛使用。 它的加密方法, 简单地说 , 是将明文二元序列和伪随机序列作模2 加法, 即在二元域F2中作加法 , 从而得到密文二元序列 , 这可用图 2 表示， 脱密方法是密文二元序列和同一伪随机序列作模2 加法, 在序列密码体制中 , 伪随机序列的研究占有非常重要的地位。明文二元序列伪随机
4、序列所谓伪随机序列 , 粗略地说 , 它是期序列 , 但具有较好的随机特性。因而在周期很大时 , 可以将它作为一个随机序列使用。 为给出精确描述 , 下面引出自相关函数的概念。+ 密文二序列图 2 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 3 页 - - - - - - - - - 盐城师范学院第 2 页 共 3 页设有二元域 F2上的周期序列012(,)aa a aa的周期P( a)=v, a的自相关函数( )aCt 是定义在非负整数J 上而取整数值的函数。110
5、( ),vaiiiCttJ，其中是从 F2的加法群到十 1, 一 l 这两个整数所组成的乘法解的同构(0)=1 ，（1）= -1 由此我们有定义 1. 设12( ,)aa a a是 F2 上的一个周期等于v 的周期序列 , 如果 a 的自相关函数( )aCt =-1 , 对一切 , t0(mod v), 我们就说 a 是个伪随机序列。反馈移位寄存器是产生伪随机序列的一种简单、有效的装置。n 级反馈移位寄存器的构造可用图3 表示。上面一排小方块代表n个寄存器。每个寄存器有两种可能的状态 , 分别用 0 和 1 看作二元域 F2的元素。下面的长方块是代表有n个输人端和 1 个输出端的开关电路 ,
6、它实现的开关函数是12(,)nf x xx，称 f 为反馈函数。若在某一时刻 , 个寄存器的内容是12(,)nx xx，称12(,)nx xx为此时刻的状态。 n 级反馈移位寄存器的状态集合是2nF =12/(,)/01nifx xxx或，2nF =2n。设在某一时刻 , 这个, 级移位寄存器的状态是12(,)na aa，个移位脉冲后, 状态就由12(,)na aa变为231(,)nna aa a, 其中12(,)nnaf a aa，nx1nx1x12(,)nf x xx图 3 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名
7、师精心整理 - - - - - - - 第 2 页，共 3 页 - - - - - - - - - 盐城师范学院第 3 页 共 3 页输出是1a 。 我们称2nF 中的映射 T1：12(,)na aa212(,(,)nnaaf a aa为以f 为反馈函数的 n级反馈移位寄存器的状态转移变换。一个n 级反馈移位寄存器的功能由它的状态转移变换完全确定，也就是由它的反馈函数完全确定, 易知, n 级反馈移位寄存器一共有 2 2n个不同的反馈函数。下面简单介绍一下组合数学, 确切地说 , 主要是 deBruijn 一Good 图对移位寄存器序列的应用。我们已经知道 ,n 级线性移位寄存器产生的最长周期
8、序列的周期是2n 一1。但是,n 级移位寄存器产生的可能的最长周期序列的周期是2n, 当然它不可能用 n级LSR 产生。通常称 n 级移位寄存器产生的周期为2n的序列为 M 一序列。于是 , 自然地提出： M 一序列是否存在 , M 一序列的计数间题 ,M一序列的性质及如何构造的问题。关于存在性问题和计数问题 , 利用图论的知识 , 特别是关于 doBruin 一Good 的结果很快被解决。所谓n级deBruiin 一Good 图G n是具有 2n个顶点 , 用A=122(,) /F nia aaa表示有2n+1条弧，用A=122312(,)(,) /F nnnia aaa aa aa表示的有
9、向图。 图二不难证明 , G n是一个连通图 , 而且每个顶点都有 2 条入弧 ,2 条出弧 , 利用Good 在19 46 年关于连通有向图的结果 , 知道G n有一条完备回路。进而 , 可以证明 G n有一个极大圈, 即H amilton 回路。而产生 M 一序列的 , 级移位寄存器的状态图就是n 级deBruijn 一Good 图的一个极大圈。因此研究 M 一序列的存在与计数问题就化为研究n级 deBruijn一Good 图中极大圈的存在与计数问题19 4 6 年deBruijn 用图论的方法证明了一共有122nn个 M-序列。当 n很大时，这是一个天文数字, 由于M-序列也具有较好的伪
10、随机性质及存在的 M一序列数量之大 , 使得构造对一序列的问题得到人们的重视。目前已经构造出的M 一序列与122nn相比还是很少的 , 因此这个问题现在有许多人研究。更一般地说, 重要的一类 n级移位寄存器的状态图都是 n级 deBruijn一Good 图的一个因子。由此可见 , 移位寄存器与deBruijn 一Good 图之间的密切关系 , 进而可以想像 , 图论、计数、生成函数等组合数学分支对研究移位寄存器序列, 特别是非线性移位寄存器序列的重要作用。数论(包括解析数论和代数数论)和代数方面的知识和技巧在密码中的应用还有很多例子, 这里不详细介绍了。除了数论和代数外 , 数学中的许多分支 , 如快速富利叶变换 , 群论等在密码学中都有重要的应用。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 3 页 - - - - - - - - -