[精品]浅谈同余中的某些应用

1、隐学术论文题目：浅谈同余中的rsa体制学号：学校：专业：班级：姓名：指导老师：时间:摘要：同余理论是初等数论的一个重要的组成部分，即有理 论价值乂有实际应用、同余可除性的符号语言，在西方是由 高斯最先引进的，本文将首先给出同余的概念和理论，然后 给出一些重要而有趣的应用。关键字：同余密码学 rsa体制subject: talk about rsaauthor: mathematics and computer college the professional of mathliu wanpostal code: 330038abstract: the theory of congruence

2、is a important part of the primary theory , in other words, it has theory value and realistic use and it is the symbel language of congruence that is divided it is the first to bring up by gaosi in the western. this passage will introduce the difination and theory of congruence,then it will also sho

3、w some important and interesting practical key words: congruence ; code ; rsa一、同余的定义若两个整数a、b被自然数m除有相同的余数，那么称a、b对于模m同余，用式了表 示为：a=b (mod m) .(*)上式可读作：a同余于b,模mo同余式(*)意味着(我们假设ab):a-b=mk, k是整数,即ml (a-b)例如：©15=365 (mod 7),因为 365-15=350=7x50。%1 56=20 (mod 9),因为 56-20二36 = 9x4。%1 90=0 (mod 10),因为 90-0

4、= 9010x9。由例我们得到启发，a可被m整除，可用同余式表示为:a三0 (mod m)。 例如，表示a是一个偶数，可以写 a=0 (mod 2) 表示b是一个奇数，可以写 b=l (mod 2)补充定义：若n (a-b),就说a、b对模ni不同余，用式子表示是：a 圭b (mod m)二、同余的rsa应用同余理论在密码学上有很重要的应用。密码作为军事斗争和政治斗争的一种手段在历史 上早就产牛。信息化社会的到來，使密码学更加有川。现在往來也需要保密。通过公共渠道, 如电话，电报，电了网络传递信息，希望不被窃取或修改，安全的送到接受者手中，就需要 用密文形式传递。先讲几个名词，甲方通过公共向乙

5、方传输信息，为了防止窃取，甚至篡改，需要将信息改变成 密文形式。原信息称为明文，明文的秘密形式称为密文。把明文变为密文的过程叫做加密。 知道了秘密把密文译为明文的过程叫做解密。密码屮的关键信息叫密钥。密钥在保密通讯屮 占有极重要的地位。一切密码系统都冇两部分：1一套构成棊木密码的通讯方法或程序的规则，称为通用系统； 2.个可变换的密钥，它由数字、单诃、词组或句子构成。在加密吋，密钥控制通用系统的 步骤，并决定密文的组成。在解密时，密钥同样地控制着解密的步骤；尽管密码的外部形式 和内部构成千差万别，但只有两种基本类型，一是位移式，一是代换式。位移式只重新排列 或调整明文字母的顺序，而不是改变字母

6、木身。代换式密码则用其他字母代替明文屮的字母 而不改变字母顺序。冇的密码系统同时使用者两种密码系统。现在广泛事业的密码机20世纪40年代以来产生出各种密码机。许多电子密码机都有类似打 字机的键盘，并使用一种电转子的装置产牛-系列不同的混合的字母，另外类似的机器也研 制出來了，用它來对众多电码进行加密和解密。在现在社会屮，计算机技术和网络如此发达，通讯的保密更是多方血的需要.例如单单一个 公司就冇销售、进货、财务等方面和很多公司、客户联系，其中多数冇保密的必要。如果按 照传统的办法，对每一个客户都要约定保密的方案，这样会不胜其数，甚至可以说是达到没 有办法的程度，因此今年來提出一个非常重要的问题

7、一信息安全问题.1976年,美国的年轻数 学家和计算机专家隶佛和兹尔曼捉出一种全新的公开密钥体制，特点就是保密性强，加密程序 和密钥公开，而且在同一体制屮可以供很多客户使用.1997年美国麻省理工学院的里维斯沙米 尔和阿德曼依据隶佛和兹尔曼设想提出一种具体的公开密钥体制，后来人们用他们三个人的 名字的字头为它命名，称为rsa我们先来介绍这种体制.设p,q是两个大质数，例如位数超过100;n=pq,e,d满足关系：ed=l(mod# (n),其中是 (n)的欧拉函数值，这里密钥和解钥分别是e,n, do密码通讯的过程如2设有一明码是数 字a(ov=av=n-l).加密程序将数字a通过关系a &#

8、39; e三b(modn),ov=bv二n-1,转化成b,发送方将 密码b送给接受方；接受方收到密码b后，解密程序是依据e,d的定义，通过关系式b 八 d=a " ed=a 八 1+k 少(n) =a(modn) (1)将密码b还原成明码a。当(a, n) =1时，由欧拉定理知相等关系成立。否则需要证明：a " 1+k(n) =a(modp) , a * l+k f (n) =a(modq) (2) 成立由欧拉函数计算公式知f (n)= $ (pq) = (p-l) (q-1)(3)于是当p整除a时，(2)的第一式显然成立。当p不整除3时，由费马知道(2)的第一式成 立。同

9、样可以证(2)的第二式队任何a成立.特别值得注意的是：密钥c, n可以公开。这就是说，rsa的保密性很好。上述的rsa可以 同时供很多用户使用。关于rsa的保密性能在历史上有一个有趣的故事，通过它揭示了一些有关的问题,1997年里维斯和沙米尔 和阿徳曼用一个129位的数n和一个4位数e对一个关于秃鹰的消息在rsa屮加密，即所谓 的rsa-129o大概是认为要大约花23000年的俄使节破译，仍而出乎意料的是仅仅在17年以 后rsa-129就败下阵来。分解成的核心在于发明了一种新的筛法二次筛法。这个方法有一个 优点就是能将工作分散到不同的计算机上去工作。人们大约组织了六厲多人的因子分解迷， 经过八

10、个月的努力找到了 rsa-129的分别是64位和65位的两个质因数。今年來数学家们不 断的创造新的算法，例如，二次筛法，数域筛法、椭圆曲线算法，目前还不足以威胁rsa的 安全性，因为用以分解数字所盂要的计算机能力，随着数字的位数增加而飞快地增加，例如, 使用rsa-200至rsa-300,那么除非计算数论有惊人的突破，否则因子分解在一个长时期内 是个难题，不过数论学家还是相信：进展到來的期限，就像整数本身一样，一定屈指可数。 至或许足以说明指挥的创新和理论的精是高科技的核心。(2)公开密钥体制冇了 rsa这个具体的例了，我们再来介绍赫尔曼提出的公开密钥体制，也许可以理解得 貝体一些。他们提出的

11、体制的关键是使用“单向”函数e作为密钥。所谓单向函数e是一个 可逆函数，但是它的逆函数d=e-1非常难求出。在rsa中是如下地定义单向函数e：対于 owawnt,通过关系a ' e三b(modn)定义e(a)=b, 0w不wnt,其中b是昇e的摸n最小 非负剩余；逆函数则由关系式b ' d=a(modn), owa, bwnt定义。设有n各用户ai, i=l, 2, ,每个用户ai各自选取一个单向函数ei作为自己的密钥公z于众，并且将它们编 成码簿，供用户查用。但是将di二ei八-1作为口己的解3钥保存，不让他人知道。当用户ai 要将明码x保密地送给aj时，将密码y=ej(x)

12、送给aj；而aj收到y后，用dj作用于y,即 可ej之后也很难求出dj,所以不能将y恢复成明码x,这种公开密钥体制除了可供n个客户公用以外，还解决了长期存在的另一个难题，即信息 的认证和签名问题(当然ras也具有这种功能)如果ai需要通过通讯(网络)向aj要一笔 款项。当然需要ai在信息上签名，以防别人冒领。公开密钥可以解决这个问题：ai先用自 己的di作用于签名x,再将y二di (x)送给aj, aj收到后并查出ei,将ei作用于y就可恢复签 名ei(y)=eidi(x)=x.因为只有ai知道di,所以就能确认信息來自ai实际上，在公开密钥 体制屮，还可以同时进行加密和签名两种程序：ai对信

13、息x接连作用di (签名)和ej (加密), 将y二ejdi(x)传给aj,aj接到后，对y接连作用dj (解密)和ei (确认)，得到 eidj (y) =eidjejdi (x) =eidi (x) =x,从而可以读到原文。1976年赫尔曼和隶佛提出公开密钥体制以后，由于可以同时解决密钥保存、数字签名和多用 八等一系列问题，引起了通讯界河数学界的极大兴趣，一吋间纷纷设计各种各样的具体的公 开密钥方案。很多方案随后又不断受别人攻击和破解，所谓破解就算找到了单向函数ee的逆 函数e快捷算法，从而使该方案不能起保密作用。20多年來，只剩下大数分解方案，即rsa 方案，还有离散对数方案，公开密钥体

14、制说明了两个重耍的事实：（1）在现在高科技社会中， 即令像数论这样被认为是很抽象、纯粹而乂占老的数学也会起很大的作用；（2）数学的作用 己经不仅仅是自然科学的基础和工具，有些发展成可以直接开发技术，为工产总接创造价值。（3）现代密码系统你如何來设计编码系统呢？光回答多加小心是不过的。现在的密码分析员冇大量的武器 可以供使用，既有强人的计算设备，又有复杂的数学和统计技术，像凯撤使用过的那类简单 的密码肯定极其不安全。简单的字母代替被排除之示，还能试用什么办法呢？不管使用哪种办法，同样的危险一 样会出现。只耍在你编好的密文中有某种“对被辨认”的模式存在，高级的统计分析方法一 般不难破译你的密码。现

15、在，真正的因难z所以在变得明朗了，为了使信息能够安全到达接 收者那里（可能最早数千里之外），关键在于，这种隐藏着的规则埋得足够深，以防被敌人发 现。所以现代的密码体系都要使用计算机。一般都假定敌人拥有强人的计算机来分析你的密 码信息，所以你的系统必须足够复朵，以防计算机的攻击。为了使所设计的密码系统尽可能 安全，它们必须由两部分组成：一个加密程序和一把钥匙。前者若是典型的计算机程序，也 可能是一台专门设计的计算机。为了为信息加密，该系统不仅需要这些程序，还冇有一选择 好的钥匙，它是通常一个秘密选定的数。加密程序将依赖这把钥匙地信息编码，使得只有白 己才能解开。由于安全性依赖于这把钥匙可以有许多人在一段相当长的时期里，使用同一个 加密程序。这既有以为看值得花大量的时间和精力來设计这种程序。不妨看一个有助于理解 得类比。声场保险柜和锁的工厂可以设计一种类型的锁给几百个使用者，后者靠自己独特的 钥匙来保证安全。此处所说的“钥匙”可以是用于字码锁的各种字码，也是立即显示出“钥 匙”这个词的开年各种用法之间的类似。正如敌人可能知道你的锁是如何设计的，可是比知 道锁的字母一样打不开你的保险柜。所以敌人可能知道你所用的加密体系而无法破译比编码 信息：要破译就得知道你的钥匙。为了将烧计算量，常常采用传统加密方法和公开密钥相结 合的方式