rsa算法实验报告（精选6篇）
rsa算法实验报告 第1篇
信息安全实验报告
题 目 RSA算法 姓 名 学 号
专业年级 计算机科学与技术2014级（1）班 指导教师
2016年 12 月 10日
一、实验目的
了解非对称加密机制 理解RSA算法的加解密原理
熟悉Java的学习以及运用Java实现RSA算法的加解密过程
二、实验背景
钥密码体制中，加密密钥(即公开密钥)PK是公开信息，而解密密钥(即秘密密钥)SK是需要保密的。加密算法E和解密算法D也都是公开的。虽然秘密密钥SK是由公开密钥PK决定的，但却不能根据PK计算出SK。正是基于这种理论，1978年出现了著名的RSA算法，它通常是先生成一对RSA 密钥，其中之一是保密密钥，由用户保存；另一个为公开密钥，可对外公开，甚至可在网络服务器中注册。为提高保密强度，RSA密钥至少为500位长，一般推荐使用1024位。这就使加密的计算量很大。为减少计算量，在传送信息时，常采用传统加密方法与公开密钥加密方法相结合的方式，即信息采用改进的DES或IDEA对话密钥加密，然后使用RSA密钥加密对话密钥和信息摘要。对方收到信息后，用不同的密钥解密并可核对信息摘要。RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。RSA是被研究得最广泛的公钥算法，从提出到现在的这么多年里，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。
三、实验原理
1.非对称密钥加解密概述
使用对称密钥加密体制进行保密通信时，任意不同的两个用户之间都应该使用互不相同的密钥。这样，如果一个网络中有n个用户，他们之间彼此都可能进行秘密通信，这时网络中将需要n(n-1)/2个密钥(其中，每个用户都需要保存n-1个密钥)，这样巨大的密钥量给密钥分配和管理带来了极大的困难。另外，随着计算机网络，特别是因特网的发展，网络上互不相识的用户可能需要进行保密的会话(例如，如果用户在进行电子商务活动时，需要保密的连接，这时的客户对象可能根本不是固定的对象)。最后，对称密钥加密机制难以解决签名验证问题。
非对称密钥加密也称为公开密钥加密，或者叫做公钥加密算法。使用公开密钥密码的每一个用户都分别拥有两个密钥：加密密钥和解密密钥，它们两者并不相同，并且由加密密钥得到解密密钥在计算机上是不可行的。每一个用户的加密密钥都是公开的。因此，加密密钥也称为公开密钥。所有用户的公开密钥都将记录在作用类似于电话号码薄的密钥本上，而它可以被所有用户访问，这样每一个用户都可以得到其他所有用户的公开密钥。同时，每一个用户的解密密钥将由用户保存并严格保密。因此，解密密钥也称为私有密钥。
非对称密码算法解决了对称密码体制中密钥管理的难题，并提供了对信息发送人的身份进行验证的手段，是现代密码学最重要的发明。公钥加密算法一般是将对密钥的求解转化为对数学上的困难问题的求解，例如RSA算法的安全性是建立在“大数分解和素性检测”这个数论难题的基础上，已知两个大素数a和b，求出a*b是容易计算的，而已知a*b，想知道其是哪两个大素数的乘积目前还没有好的计算方法，另外也有一些非对称加密算法(如ELGamal算法)的安全性是基于求“离散对数”这个数学难题上的。
在公钥密码系统中每个实体都有自己的公钥和相应的私钥。公钥密码系统的加密变换和解密变换分别用E和D表示。任何实体B要向实体A发送信息m的步骤如下：实体B首先获得实体A的真实公钥的拷贝(eA)，实体B使用eA计算密文c=E(m)并发送给实体A，实体A使用自己的私钥dA，计算m=D(c)解密密文，恢复出明文m。这里公钥不需要保密，但要保证它的真实性，即eA确实是实体A掌握的私钥dA所对应的公钥。提供真实的公钥比安全地分配密钥实现起来要容易得多。这也是公钥密码系统的主要优点之一。
公钥密码系统的主要目的是提供保密性，它不能提供数据源认证(data origin authentication)和数据完整性(data integrity)。数据源认证是指：指定的数据是在以前的某个时间确实是由真正的源创建的。数据完整性是指：真正的源创建该数据后经过传输后存储没有发生改变。数据源认证和数据完整性要由其他技术来提供(如消息认证码技术、数字签名技术等)。
从本质上来看，公钥密码比对称密钥密码加密的速度要慢，粗略的说，公钥加密算法RSA硬件实现比分组加密算法DES硬件实现的速度慢1500倍，而软件实现的速度要慢100倍。
公钥解密也可以提供认证保证(如：在实体认证协议、带认证的密钥建立协议等)。公钥加密中必须有颁发让发送消息的人得到想要发送到的那个人的公钥的真实拷贝，否则就会受到伪装攻击。在实践中有很多方法分发真实的公钥，如：使用可信的公共文件，使用在线可信服务器，使用离线服务器和认证。
2.公钥加解密的优缺点：
1)大型网络中的每个用户需要的密钥数量少。
2)对管理公钥的可信第三方的信任程度要求不高而且是离线的。3)只有私钥是保密的，而公钥只要保证它的真实性。4)多数公钥加密比对称密钥加密的速度要慢几个数量级。5)公钥加密方案的密钥长度比对称加密的密钥要长。6)公钥加密方案没有被证明是安全的。
公钥密码的概念本身就被公认为是密码学上的一块里程碑。三十多年来的研究表明，公钥密码成功地解决了计算机网络安全中的密钥管理，身份认证和数字签名等问题，已经成为信息安全技术中的重大核心技术。
四、RSA算法 1.概述
RSA加密算法于1977年由美国麻省理工学院的Ronal Rivest，Adi Shamir和Len Adleman三位年轻教授提出，并以三人的姓氏Rivest，Shamir和Adleman命名为RSA算法。这三位科学家荣获2002图灵奖，以表彰他们在算法方面的突出贡献。该算法利用了数论领域的一个事实，那就是虽然把两个大质数相乘生成一个合数是件十分容易的事情，但要把一个合数分解为两个质数的乘积却十分困难。合数分解问题目前仍然是数学领域尚未解决的一大难题，至今没有任何高效的分解方法。它无须收发双方同时参与加密过程，既可以用于保密也可以用于签名，因而非常适合于电子邮件系统的加密，互连网和信用卡安全系统。
算法概述：找两素数p和q，取n=p*q，取t=(p-1)*(q-1)，取任何一个数e，要求满足e 2.算法设计 1)publicstaticvoid GetPrime()说明：利用Java语言的中的java.math.BigInteger类的方法中随机产生大数。 2)public static boolean MillerRobin(BigInteger num)参数说明：num是由GetPrime方法产生的大数。 说明：这个方法判断GetPrime方法传过来的是否是一个素数，是就返回true,否就返回false。 3)public static BigInteger powmod(BigIntegera，BigIntegert，BigInteger num)说明：这个方法对传入的大数进行幂运算。 4)public static BigInteger invmod(BigInteger a，BigInteger b)说明：这个方法对大数进行取模运算。 5)public static String Encode(String inStr，BigInteger PrimeP，BigInteger PrimeQ，BigInteger n，int nLen，int m，JTextFieldd)方法名称：加密算法。参数说明： inStr是从界面输入的明文。 PrimeP和PrimeQ是由GetPrime方法产生的两个大素数。n是由PrimeP和PrimeQ得到的值。nLen为n的长度。d为公钥。 6)publicstatic String Decode(String inStr，BigInteger PrimeP，BigInteger PrimeQ，BigInteger n，int nLen，int m，JTextField e)方法名称：解密算法。参数说明： inStr是从界面输入的明文。 PrimeP和PrimeQ是由GetPrime方法产生的两个大素数。n是由PrimeP和PrimeQ得到的值。nLen为n的长度。e为私钥。 在对称加密中：n，d两个数构成公钥，可以告诉别人；n，e两个数构成私钥，e自己保留，不让任何人知道。给别人发送的信息使用e加密，只要别人能用d解开就证明信息是由你发送的，构成了签名机制。别人给你发送信息时使用d加密，这样只有拥有e的你能够对其解密。 RSA的安全性在于对于一个大数n，没有有效的方法能够将其分解从而在已知n，d的情况下无法获得e；同样在已知n，e的情况下无法求得d。 五、实验结果 实验结果如下图所示： 六、实验总结 本次实验对输入的任意一段明文字母，实现了输出对应密钥的密文字母。亲手实际编写RSA密码算法代码，更好的了解和掌握了RSA的相关内容。通过用Java对RSA密码体制进行编程，对RSA密码体制的加解密过程有了更深入的理解。通过这个实验更是让我获得了很多实际工作中所要具备的能力。 七、代码附录 略 关键词：DSP RSA算法 公钥密码体制 模运算 引言 在当今的电信时代，由于采用大规模的电子计算机对数据进行处理，使得信息的传递大大加速，但是，也随之出现了令人最为担心的问题，就是信息的安全性。对信息进行保护的方法就是数据加密，通过对网络上传输的数据和系统内存储的数据进行加密，可以大大提高网络和信息的安全性。以较高的安全性而被广泛采用的RSA公钥密码体制，在现代安全性制中占有重要地位。RSA算法由于在加密和解密过程中要进行大量的数值运算，存在难以实现的问题；而采用纯软件的方式实现RSA算法，虽然降低了解密的强度，但却增加了运算时间。本文采用一种软硬件相结合的方式来实现RSA算法。 DSP（Digital Signal Processor）芯片，即数字信号处理器，是一种特别适用于进行实时数字信号处理的微处理器。TMS320C54x系列是一种有特殊结构的微处理器，其内部采用程序与数据分开的哈佛结构；具有专门的硬件乘法器，广泛采用流水线操作，使用特殊的DSP指令，可以用来快速地实现各种数字信号处理算法。正因为TMS320C54x系列的这些特点，比较适合RSA算法使用，实现对串行数据的加、解密。 1 RSA算法 RSA算法是由Rivest、Shamir与Adleman三人于1978年合作开发的，并以他们的名字命名的公开密钥算法。其加密密钥是公开的，而解密密钥是保密的。它是基于一个非常简单的数论思想：“将两个素数乘起来是很容易的，但是分解该乘积是非常困难的”。 RSA算法的特别为利用素数（也就是质数）的因式不可分解性，选用很大的素数（一般为几百位到几千位），为了使政府部门与军事部门的数据保密，大多采用几千位以上的素数作为加密的密钥。RSA算法的要点与难点有二：①算法主要为求模取余运算，这给此算法的应用增添了实际的应用难度，因为给一个几千位的素数进行求模取余运算是很难的；②判断一个数是否为素数也是数学界几百年来一直讨论与研究证明的难题，虽然费马提出了著名的“费马猜想”，但一直却未得到过完全的证明，基于此要找一个几千位的素数更是难上加难。 （1）RSA算法原理 RSA算法是基于数论中的同余理论。如果用m代表明文，c代表密文，E(m)代表加密运算，D（c）代表解密运算，x=y(mode z)表示x和y模z同余，则加密和解密算法简单表示如下： 加密算法 c=E(m)=me(mod n) 解密算法 m=D(c)=cd(mod n) 其中n和密钥e是公开的，而密钥d是保密的。 下面讨论密钥的求取： ①选取两个随机大素数p和q（保密）； ②设n=p×q； ③欧拉函数φ（n）=（p-1）（q-1）（保密）； ④选取与φ（n）互素的正整数e，即满足gcd(φ(n),e)=1和0 ⑤计算d(保密)，使满足e×d=1（mod φ(n)），即d和e相对于模φ(n)互为逆元素。 由RSA算法原理可知，RSA算法的核心是求模取余运算，其安全性是建立在大合数因子分解困难的基础之上的。 （2）模运算的实现 RSA算法的核心操作也是最耗时的操作是模运算，所以开发一种快速指数和取模运算是解决运算速度的关键。通常的模运算都是利用加减法来实现的，因为加减法指令的执行速度快。但对于TMS320C54x系列芯片，内部有专用的17位×17位乘法器，使得乘法指令的执行与加减法指令的执行所用的时间完全相同，所以在此设计中采用乘法完成模运算。 在进行模运算时，一般先将指数e(长度为kbit)改写成二进制数组的形式e，即 (本网网收集整理) 其中：ei∈{0,1},i=0,1,Λ,k-1。 >这样，在计算me(mod n)时，先做一次平方运算，然后根据ei的值，再做一次乘法运算，以此来简化模运算的复杂性。 由于实际中的e值非常大，为了提高运算速度，可以将e进行分组后运算。设对e以四位一组（十六进制）的形式计算me(mod n)，那么： 其中：ei∈{0,1,2,…,15}，t=k/4； ②求出m2,m3,…，m15(mod n)； ③设置变量c:=1； ④对于i=t-1,t-2,…，1，0重复计算： c:=c2(mod n)(平方)； c:=c2(mod n)(四次方)； c:=c2(mod n)(八次方)； c:=c2(mod n)(十六次方)； e.若ei≠0,则c:=c×mei(mod n)。 ⑤所得c即为所求。 由上面的模运算方法分析可知，该算法的运算所需的平方和乘法次数是最少的，因此选择这种算法来实现模运算可提高运算速度。有了基本运算思路和步骤以后，就可以利用TMS320C54x DSP芯片来开发RSA算法了。 2 软硬件的实现 在嵌入式应用场合，对于大规模的乘法运算，采用单片机来实现显然力不从心；而TMS320C54x DSP芯片的特点恰好满足RSA算法的要求，是实现此算法的首选芯片。本课题中所选用的`是德州仪器公司生产的TMS320C5402芯片。 （1）TMS320C5402芯片概述 TMS320C54x芯片是为实现低功耗、高性能而专门设计的定点DSP芯片，主要应用在无线通信系统和远程通信嵌入式系统中。本文所用的TMS320C5402芯片是此系列的一个典型产品，除了继承老产品的优点外，还增加了更多的硬件资源，该芯片的主要特点有： ①速度快，指令周期为10ns，运算能力为100MIPS； ②强大的寻址能力，1M×16位最大可寻址外部存储空间，内置16K×16位RAM，4K×16位ROM； ③40位的算术逻辑运算单元（ALU），包括2个独立的40位累加器和1个40位的桶形移位寄存器； ④1个17位×17位的硬件乘法器和1个40位的专用加法器，乘法器/加法器单元可以在一个流水线状态周期内完成一次乘法累加（MA）运算； ⑤先进的多总线结构（3条数据总线、1条程序总线和4条地址总线），多条数据总线可以同时读取多个数据，使得指令集的功能强，效率更高。 （2）硬件设计 在本设计中，外设提供的串行数据是标准RS232电平，经过电平转换后达到可以处理的TTL电平，直接与DSP芯片的异步接收发送引脚相连；DSP将接收到的数据进行加、解密处理，并存储在外部数据存储器中，等待中断程序进行读取。 电路原理框图如图1所示。 在本DSP系统中，SRAM与DSP芯片的接口构成32K字的外部程序存储器和16字的外部数据存储器，其中外部程序存储器的地址范围是48000H～4FFFFH，外部数据存储器的地址范围是4000H～7FFFH；并行8位EPROM与DSP芯片的接口构成32KB的引导装载EPROM，可以使DSP系统成为独立运行系统，其地址范围是8000H～FFFFH。 当DSP芯片工作在微计算机方式（MP/MC=0）下，复位时，外部并行8位引导装程序从外部EPROM中读取引导装载表，并且装载程序代码到DSP片外程序存储器中。在外部并行8位引导装载模式下，可对软件等待状态寄存器（SWWER）和切换控制寄存器（BSCR）进行配置，使高速DSP芯片能从相对较慢的外部EPROM中读取数据，缺省的设置是7个等待状态。 硬件的设计是最为重要的，必须严格分析DSP工作过程中的时序问题，而且还要考虑到指令在执行时所消耗的时间；要考虑到该时间与外围器件的运行速度是否匹配等诸多因素，若单个软件设计成功而支持软件的硬件未设计成功，也就意味着整个设计等于零。 （3）软件设计 软件开发过程包括：利用任何文本编辑器编写源代码文件，然后通过编译、汇编和链接，生成DSP可执行的COFF目标代码，最后将生成的可执行目标代码通过仿真器下载到DSP目标系统中运行，再利用调试工具进行调试，达到设计要求。待程序调试通过后，就可以将所调试通过的程序代码利用Hex转换工具转换为二进制文件，再用编程器将程序写入外部EPROM中，形成独立的DSP系统。 开发语言分为汇编语言与高级语言两类。其中汇编语言编译器的效率高，但是由于生产DSP芯片的厂家开发出的DSP芯片所支持的汇编语言差异较大，其指令、寻址方式差异更大，并且可读性与可移植性不强。为克服这个缺点，厂家大都开发出支持高级语言的工具，典型的如“C语言”；而C语言的编译器效率比不上汇编语言；特别是在处理低层硬件中就显得苍白无力，所以一个优化高效的DSP应用程序都采用高级语言与汇编语言共同完成。 结语 1. RSA算法描述 我们对明文进行分组，用M表示，把密文分组用C表示，则RSA算法可以描述为： 加密：C=Memod n 解密：M=cdmod n=(Me) dmod n=Medmod n 发送方和接收方都知道n的值。发送方知道e的值，而接收方知道d的值。所以{e, n}和{d, n}构成一对密钥，通常称{e, n}是公钥，{d, n}是私钥。 参数解释： (1) p和q为两个大素数。 (2) 计算n=pq。 (3) 随机选取e，且满足1 得到公钥就是e和n。 (4) 通过ed=1 modΦ(n)，计算d。那么私钥就是d和n。 2. 大数的生成 首先将一个函数用泰勒公式的若干项去近似代替，给参数随机选取一个值，就可以得到一个数，我们选取这个值的整数和小数点后若干位组成一个数，这样我们就得到了一个不为常人所知的大数。 例如：我们取ex这个函数，其n阶麦克劳林展开式为1+x+x2/2!+xn/n!，一旦取定x和n的值就可求出它的值，取整数和小数点后若干位就得到了一个大数。如果该大数为奇数直接使用素性检测算法即可，否则将该大数加1或者重新选取参数值重新生成一个大数，然后使用素性检测算法判断是否为素数，如果在符合要求的概率范围内为素数则认为成功找到了一个素数, 否则重新生成一个大素数，再次检测。 3. 素性检测用到的数学知识 现在已经生成了大数p，要判断它是否为素数，需要以下的准备工作： (1)若p是任意的正整数，则必有p=6k±h，其中h=0, 1, 2, 3, 4, 5。 (1) 当h=0, 2, 4时，p必为偶数。 (2) 当h=3时，p为3的倍数的奇数。 (3) 当h=1, 5时，即p=6k±1不是偶数也不是3的倍数的奇数，称这种奇数为素性奇数。 因此，当k=0, 2, 3, 4时，p一定不是素数。素数不是杂乱无章地存在，而是分布在y=6x±1的两条平行斜线上。素性奇数公式p=6k+1中包含了两类奇数，一类是素数，一类是类素奇数(即除了1和本身外，还能被除2, 3之外的其它素数所整除，是素数与素数之积或乘方，可以表示为p=(6k1±1) (6k2±1)其中k1, k2∈N)。 p=6k±1, k∈N与p=(6k1±1) (6k2±1), k1, k2∈N这两个公式告诉我们：当k为任意自然数时，通过第一个公式可以计算出任意大的素性奇数，通过第二个公式可以计算出任意大的类素奇数。从素性奇数的集合中去掉类素奇数的集合，剩下的一定是素数。 (2)定理1:n是素数的充分必要条件是Φ(n)=n-1，其中Φ(n)是欧拉函数。 证明： (1) 若n是素数，则{1, 2，，n-1}中的任何一数都与n互质，由欧拉函数的定义知，Φ(n)=n-1条件是必要的。 (2) 若Φ(n)=n-1 (n>1)，可用反证法证明n是素数。如果Φ(n)=n-1并且n是合数，则n有标准分解式，可导出Φ(n) 定理2：若an-1≡1 (mod n)，且满足1x 证明：由题给条件知n-1整除Φ(n)，又Φ(n)n-1，故Φ(n)=n-1。由定理1，知n是素数。 推论：若2n-1≡1 (mod n)，并且1x 因此，2n-1≡1 (mod n)是判断n为素数的必要非充分条件。 4. 素性检测算法 (1)用泰勒公式产生一个大数p，判断该大数是否为奇数，是奇数则转(2)，如果不是奇数则将该大数加1然后转(2)。 (2)计算(p+1) mod6是否为0，为0则转(3)，不为0则计算(p-1) mod6是否为0，如果为0则转(3)，否则转(6)。 (3)计算2p-1≡1 (mod n)是否成立，如果成立则转(4)，否则转(6)。 (4)用2000以内的小素数去除p看能否除尽，不能除尽转(5)否则转(6)，这样可以排除大量的类素奇数。 (5)产生随机数a且a (6) p=p+2, 转 (2) 。 5. RSA的安全性 攻击RSA算法的方法比较多，主要是因子分解方法。 要解密密文分组C，需要获得密钥d，由于d=e-1modΦ(n)，为了求得d需要求出Φ(n)的值，为了求出Φ(n)的值需要对n进行分解，因此RSA算法的安全程度依赖于对n的分解难度。 为了增大对n的分解难度，对参数的选择需要加以限制，现就RSA算法的参数讨论如下： (1) p, q选择强素数，否则不能防御某些特殊的因子分解方法。 假设p, q不是强素数。可以假设p-1没有大的素因子，p-1=，其中pi为素数，ai是自然数(1im)。可以设pi (2)如果2B=y mod n中，y=1，则把x换成3，直到y≠1。那么，gcd (y-1, n)=p，因为y应该为p的某整数倍加1。由此可以求出p与q。 (6) e不可选择过小，否则虽然加密速度快但可以采用小指数攻击。在C=Memod n中，如果e选择过小，可能没有模n的运算，可以通过直接开平方得到。一般选择使ei=1modΦ(n)中的i尽可能大的e。 本文主要论述了RSA算法的数学表达式，并且论述了如何获得RSA算法所需的大素数，在此基础上进一步讨论了RSA算法的安全性问题。 参考文献 [1]关振胜.公钥基础设施PKI与认证机构CA[M].北京:电子工业出版社, 2002. 【关键词】无线网络 RSA 加密算法 近年来，计算机及通信科学发展突飞猛进，利用网络交流和处理信息变得越来越普遍。尤其 以无线局域网（WLAN）为代表的无线网络技术得到了高速发展和应用。无线网络作为有线网络的补充和延伸，在与日俱增的网络活动中，人们越来越关注其安全的问题。 一、无线网络的特点和存在的安全问题 （一）无线网络的特点 无线网络具有传统有线网络无法比拟的优点：灵活性，不受线缆的限制，可以随意增加和配置工作站；低成本，无线网络不需要大量的工程布线，同时节省了线路维护的费用；移动性，不受时间、空间的限制，随时随地可以上网；易安装，和有线相比，无线网络的组建、配置、维护都更容易。 （二）无线网络存在的安全问题。 1.影响WLAN的因素。IEEE 802.11的標准规定，WLAN的传输介质是无线电波。因此只要在WLAN信号覆盖范围内，入侵者可以在预期范围以外的地方访问WLAN，通过各种手段入侵WLAN，窃听网络中的数据并且对无线网络进行攻击。 其次，由于WLAN是遵循TCP/IP网络协议的一种计算机网络，所以WLAN内的计算机也会遭受来自计算机网络病毒的威胁，甚至会产生比有线网络更加严重的后果。 2.无线网络的安全问题主要表现。无线网络的安全问题主要在下面几个方面：（1）非法的AP，容易侵入。（2）未经授权使用服务和性能的限制。（3）地址欺骗和会话拦截。（4）流量分析与侦听。（5）高级入侵。基于上述特点，无线网络的通信保密能力需要一种强有效的安全机制来保障。数据加密是通过对信息进行重新编码，达到隐藏信息内容、使非法用户无法获得真实内容的一种技术，其核心就是加密算法。数据加密就是一种保障无线网络通信的有效方法。 二、无线网络的加密算法分析 数据加密的基本过程是，对明文的档或数据按某种算法进行处理，得到不可读的一段代码，通常称为“密文”，只有在输入相对应的密钥之后才能显示出本来内容，通常称“解密”。通过这样的方法来保护数据不被非法人窃取、阅读。无线网络的加密体制，按密钥方式划分，主要有对称式密钥加密和非对称式密钥加密两种。 （一）对称式密钥加密 对称式密钥又称常规密钥，是指加密的收发双方使用相同密钥的密码，且密钥是保密的，不公开，通常称之为“SessionKey”。其加密体制的特点是，收发双方具有相同的加密与解密的密钥，发送方用密钥对数据（明文）进行加密，接收方同一个密钥对收到的数据进行解密。对称密钥加密实现容易、速度快，但是为了保证密钥的安全，必须通过安全通道来传送密钥。 （二）非对称密钥加密 非对称加密算法又名“公开密钥加密算法”，需要两个密钥：公开密钥和私有密钥。如果用公开密钥对数据进行加密，只有用对应的私有密钥才能解密；如果用私有密钥对数据进行加密，那么只有用对应的公开密钥才能解密，所以这种算法叫作非对称加密算法。非对称密钥加密体制包括RSA、ELGamal、椭圆曲线加密等算法。其中RSA算法为当今世界上应用最为广泛的非对称加密算法 三、RSA算法 RSA是目前最有影响力的公钥加密算法，它能够抵抗到目前为止已知的绝大多数密码攻击。RSA公钥加密算法是在1977年提出的目前已被ISO推荐为公钥数据加密标准。 （一）RSA算法的原理 1.加密消息。假设甲想给乙送一个消息m，甲知道乙产生的N和e。那么甲使用事先与乙约定好的格式将m转换为一个小于N的整数n，比如甲首先将每一个字转换为这个字的Unicode码，然后将这些数字连在一起组成一个数字。假如甲的信息非常长的话，也可以将这个信息分为几段，然后将每一段转换为n。用下面这个公式他可以将n加密为c：。计算c并不复杂。甲算出c后就可以将它传递给乙。 2.解密消息。乙得到甲的消息c后就可以利用她的密钥d来译码。她可以用以下这个公式来将c转换为n： 得到n后，乙可以将原来的信息m重新复原。 3.签名消息。签名消息检测出数据在传播路径上有没有被篡改过，RSA也可以实现消息署名。假如甲想给乙传递一个署名的消息，那么甲为自己的消息计算一个散列值（Message digest），然后用甲自己的密钥（private key）加密这个散列值并将这个“署名”加在消息的后面。这个消息只有用甲的公钥才能被解密。乙在获得消息后首先用甲的公钥解密这个散列值，然后将这个数据与乙为这个消息计算的散列值相比较，如果两者相符，乙就知道发信人持有甲的密钥，以及这个消息在传播路径上没有被篡改过。 （二）RSA算法的攻击方法和应对 RSA算法的攻击方法主要有模数攻击、时间攻击和因子分解。解决模数攻击的办法是不共享模数。时间攻击。假如甲对乙的硬件有充分的了解，而且知道它对一些特定的消息加密时所需要的时间的话，那么甲可以很快地推导出d。因为在进行加密时所进行的模指数运算每个位元进行的，所以如果能得到多组信息和信息的加密时间，就会有机会可以反推出私钥的内容。因子分解。因子分解在RSA安全性的时候已经论述，因子分解可以成功破解RSA，也是最流行的一种攻击方法。应对方法是在一定条件下尽可能选取大数。RSA算法易于理解和操作，是第一个能同时用于加密和数字签名的算法。RSA从诞生到现在历经各种攻击的考验，是被研究的最广泛的公钥算法，也是目前最优秀的公钥算法之一。 四、总结 将基于RSA的算法用于WLAN及更多的平台，确保具有开放性与共享性的无线网络不受到外界的攻击与破坏。随着计算机网络的不断发展，更多的优秀的加密算法也会涌现出来。 参考文献： [1]杨峰，张浩军.无线局域网安全协议的研究和实现[J].计算机应用.北京邮电大学出版社 [2]贺雪晨.信息对抗.与网络安全清华大学出版社（第2版），2010，5. 开课实验室：数学实验室 指导老师：韩逢庆 时间：2011.12 学院：理学院 专业：信息与计算科学 班级：2009级2班 姓名：古 月 学号：09180230 一、实验目的 1．加深学生对贪心算法设计方法的基本思想、基本步骤、基本方法的理解与掌握； 2．提高学生利用课堂所学知识解决实际问题的能力； 3．提高学生综合应用所学知识解决实际问题的能力。 二、实验内容 题目见P143:4-16,4-23.三、实验要求 （1）用分治法求解最少加油次数和最少硬币个数问题； （2）再选择自己熟悉的其它方法求解本问题； （3）上机实现所设计的所有算法； 四、实验过程设计（算法设计过程）（1）最少加油次数 实验题目 一辆汽车加满油以后可以行使n公里，旅途中有若干个加油站，设计一个有效算法，指出应在哪些加油站停靠加油，使沿路加油次数最少。并证明算法能产生一个最优解。过程设计 贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。比如说最少加油次数的问题。在这个算法中，我采用的贪心算法的策略。首先人机互动的设定加满油以后最长能够行使的距离，然后输入了各个站点之间的距离，在程序的设计中，首先检查了程序的可行性。要是遇到当某两个站点之间的距离大于汽车一次加油以后所能够行使的最大距离时，我们认为此问题是不可行的。这个在实际情况中也是很容易理解的。然后在满足可行性条件下，依次采用贪心算法对问题得以实现。采用s这个来保存现在车里面留下的油，当此时留下的有能够行驶完这一站点到下一站点之间的距离是，在这一站点的时候就不加油。但是若不能行使完这一段路程的时候，就加满油。核心算法如下： for(i=0,s=0;i { s=s+a[i]; if(s>n) { sum++; s=a[i]; } }（2）最少硬币个数问题 实验题目 考虑下面的用最少硬币个数找出n分钱的问题： 当使用2角5分，1角，5分和1分四种硬币面值时，设计一个找n分钱的贪心算法，并证明算法能产生最优解。过程设计 贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。比如说找最少硬币个数的问题。在算法的实现过程中，当剩余的钱数大于2角5分时，我们在记录找2角5分硬币的个数的变量里面加一，同时把剩余所找的钱的总数目也减2角5分。不断重复这个过程，直到剩余所需找的钱的数目小于2角5分时，在记录找1角硬币的个数的变量里面加一，同时把剩余所找的钱的总数目也减1角，不断重复这个过程，直到剩余所需找的钱的数目小于1角。5分和1分的硬币实现过程同上述过程一样，一直执行到所剩的钱的数目为0，此时停止计算，得到最优解。 五、实验结果分析（1）最少加油次数 当加油后行驶的最大距离小于相邻站点的最小值时，此时，可行，求解结果如下： 当加油后行驶的最大距离大于相邻站点的最小值时，此时，没用可行性，为边沿情况，求解结果如下： （分析时空复杂性，设计测试用例及测试结果）时间复杂性：该算法的时间复杂度为O(n)空间复杂性分析：该算法的空间复杂度为O(1)（2）最少硬币问题 当输入的找零钱数为正常的时候的运行情况如下： 当输入的找零钱数为不正常的时候（为负）的运行情况如下： （分析时空复杂性，设计测试用例及测试结果）时间复杂性：该算法的时间复杂性为O(n)空间复杂性分析：该算法的空间复杂性为O(1) 六、实验体会 贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题，相容活动安排问题等。这样和采用动态规划的算法相比，算法的思想更加的简单，实现起来更加的容易。 但是也要明确贪心算法和动态规划的主要区别。及0-1背包问题可以用动态规划算法求解，但是贪心选择算法却不能用动态规划算法求解。因为贪心算法无法最终将背包装满，部分闲置的背包空间使得每公斤背包空间的价值降低了。 七、附录：（源代码）（1）最少加油次数 具体算法的实现如下： #include cin>>a[i];} for(i=0;i<=n;i++){ cout<<“第”< { sum=-1; break; } if(sum!=-1){ } for(i=0,s=0;i s=s+a[i]; if(s>n) { sum++; s=a[i]; } } } if(sum==-1)cout<<“没有可行性”< #include cout<<“ 您输入的数据有错!”< a++; m=m-2.5;} while(m>=1){ b++; m=m-1;} while(m>=0.5){ c++; m=m-0.5;} while(m>=0.1){ d++; 实验报告 班级：计科姓名：张华敏学号： 0902班 0909090814 FIFU算法 一，实验内容： 编写一段程序来模拟页面置换算法中的FIFU算法的实现 二，算法设计： 设置一个产生随机数的函数rand()产生随机数来模拟程序所需访问的页面的标号，如果页面需要被访问则把页面中的一个标志位设为in表示他已经被调入内存，如果再次需要访问此页面是只需检查此页面的标志位是否为in就可判断它是否已经存在在内存中了，如果已经存在则可直接使用，如果不存在则需调入，在调入新页面是先检查内存空间是否已满，如果未满则直接调入，如果已经满了则需选择一个页面将其调出，调出时就把页面的标志位设为out。选择页面的规则是：将进入内存时间最久的页面调出去，为了达到这一目的，在页面中设置一个计数器，每当有新页面调入内存时则将内存中已经存在的页面计数器自动加一，调出页面时就选择那个计数器最大值的页面，调出后重新将计数器设为零。三，遇到的问题及解决方案： 在做此实验时遇到了一些小问题,如在C语言中函数名定义为export()则会报错。在调用有返回值的函数是如果直接int s=use(pag)则会运行出错,要先分开写如：int s,s=use(pag).四，源代码 头文件.cpp #include int t;//全局变量，用来盛放rand()函数产生的随机数 enum boolean{in,out};//定义一个枚举类型 /////////如果把in，out换成 true,false则会处错误 typedef struct { int num;//页面编号 char content;//页面内容 enum boolean flog;//判断此页面是否页调入，调入为true,否则为false;int count;//页面计数器 int usebit;//使用位，被使用过值为1，否则为0 }page; FIFU.cpp #include int capacity=3;//设置内存最多可以容纳的页面数 void initialize(page p[])//初始化页面函数 { for(int i=0;i<5;i++)//初始化页面，页面内容分别为小写字母 abcde,计数器全部为0 {p[i].num=i;p[i].content=i+97;p[i].flog=out;p[i].count=0;} } int use(page p[]){ t=rand()%5;//产生一个0-5的随机数，if(p[t].flog==in){ printf(“tt%d页面命中n”,t);//for(int i=0;i<5;i++)//调入此页面后其他以在内存中存在的页面计数器加1 // { // if(p[i].flog==in)// p[i].count++;// } return(1);} else return(0);} void import(page p[])//调入页面的函数 { /* int t=rand()%5;//产生一个0-5的随机数，if(p[t].flog==in)printf(“tt%d页面命中n”,t);*/ // if(p[t].flog==out)//如果此页面未被调入内存则立即调入 p[t].flog=in;capacity--;//调入后内存空间减少一叶 for(int i=0;i<5;i++)//调入此页面后其他以在内存中存在的页面计数器加1 { if(p[i].flog==inp[i].num!=t)p[i].count++;} printf(“页面%d被调入内存n”,t);} void port(page p[])//调出页面的函数，，，，，，，，，，，如果函数名定义为export则处错误 { int x=0,y;//x用来暂时存放计数器 中的最大值，y存放此页面的页面号 for(int i=0;i<5;i++)//寻找计数器值最大的 页面 { if(p[i].count>x){ x=p[i].count;y=i;} } p[y].flog=out;//修改调入符号 p[y].count=0;capacity++;//调入后内存空间增加一叶 printf(“ttt页面%d被调出内存n”,y);} main(){ int s;long t3,t1,t2;page pag[5];//定义五个页面，，，，，，，，，，，如果这个定义在子函数之前那么不用通过参数 子函数便可以直接访问 t3=time(NULL);initialize(pag);do { t1=time(NULL);s=use(pag);//，，，，，，，，，，，，，，如果这里写成int s=use(pag)则会运行出错 //printf(“s=%d capacity=%dn”,s,capacity);if(capacity>0s==0)import(pag);else { if(capacity==0s==0){ port(pag);import(pag);} } t2=time(NULL);while(t2-t1<1){ t2=time(NULL);} }while(t2-t3<20);system(“pause”);} 五，测试结果： LFU算法 一,实验内容： 编写一段程序来模拟页面置换算法中的LFU算法的实现 二,算法设计： 设置一个产生随机数的函数rand()产生随机数来模拟程序所需访问的页面的标号，如果页面需要被访问则把页面中的一个标志位设为in表示他已经被调入内存，如果再次需要访问此页面是只需检查此页面的标志位是否为in就可判断它是否已经存在在内存中了，如果已经存在则可直接使用，如果不存在则需调入，在调入新页面是先检查内存空间是否已满，如果未满则直接调入，如果已经满了则需选择一个页面将其调出，调出时就把页面的标志位设为out。选择页面的规则是：将最近一段时间未被访问过的页面调出。为了达到这一目的在页面中设置一个标志位，如果页面在近期只要被访问过则将该标志位设置为1（默认为0），在选择调出页面时只需将标志位为0的页面调出即可。三,遇到的问题及解决方案： 未遇到什么问题 四,实验感悟： 遇到问题后上网查资料和有效,及时查不到自己想要的但是也可从相关结果中获得启发给自己灵感来想到解决问题的方法.四，源代码 FLU.cpp #include int capacity=3; //设置内存最多可以容纳的页面数 void initialize(page p[]) //初始化页面函数 { for(int i=0;i<5;i++) //初始化页面，页面内容分别为小写字母 abcde,计数器全部为0 {p[i].num=i; p[i].content=i+97; p[i].flog=out; p[i].count=0; p[i].usebit=0; } } int use(page p[]){ t=rand()%5; //产生一个0-5的随机数，if(p[t].flog==in) { printf(“tt%d页面命中n”,t); p[t].usebit=1; //for(int i=0;i<5;i++)//调入此页面后其他以在内存中存在的页面计数器加1 // { // if(p[i].flog==in) // p[i].count++; // } return(1); } else return(0); } void import(page p[])//调入页面的函数 { int t=rand()%5; //产生一个0-5的随机数，//if(p[t].flog==in) // { // printf(“tt%d页面命中n”,t); // p[t].usebit=1; // } // if(p[t].flog==out) //如果此页面未被调入内存则立即调入 p[t].flog=in; capacity--; //调入后内存空间减少一叶 for(int i=0;i<5;i++)//调入此页面后其他以在内存中存在的页面计数器加1 { if(p[i].flog==inp[i].num!=t) p[i].count++; } printf(“页面%d被调入内存n”,t); } void port(page p[]) //调出页面的函数 ////////////////////////////////如果函数名定义为export则处错误 { int x=0,y;//x用来暂时存放计数器 中的最大值，y存放此页面的页面号 int z=-1; //用来判断近期是否有未被访问过的页面 int g=0; for(int i=0;i<5;i++)//寻找计数器值最大的 页面 { if(p[i].count>x) { x=p[i].count; y=i; } } for(int i=0;i<5;i++) { if(p[i].flog==inp[i].usebit==0) { z=i; g++; } } if(z==-1||g==3)//如果所有页面均为1则按照FIFO算法置换页面 //如果g=3则表明页面使用位全为零，此时也按照FIFO算法置换页面 { p[y].flog=out;//修改调入符号 p[y].count=0; capacity++; //调入后内存空间增加一叶 p[y].usebit=0; for(int i=0;i<5;i++)//将所有页面置0 p[i].usebit=0; printf(“ttt页面%d被调出内存n”,y); } else //如果有页面为0则将此页面置换出来 { p[z].flog=out;//修改调入符号 p[z].count=0; capacity++; //调入后内存空间增加一叶 printf(“ttt页面%d被调出内存n”,z); } } main(){ int s; long t3,t1,t2; page pag[5];//定义五个页面 ///////////////////如果这个定义在子函数之前那么不用通过参数 子函数便可以直接访问 t3=time(NULL); initialize(pag); do { t1=time(NULL); s=use(pag); if(capacity>0s==0) import(pag); else { if(capacity==0s==0) { port(pag); import(pag); } } t2=time(NULL); while(t2-t1<1) { t2=time(NULL); } }while(t2-t3<20); system(“pause”);} 六,实验结果 总结rsa算法实验报告 第2篇
摘要：RSA算法是基于数论的公钥密码体制，是公钥密码体制中最优秀的加密算法。本文介绍RSA算法的基本原理以及用以TMS320C5402芯片为核心的硬件去实现RSA算法；提供了应的硬件、软件的接口设计，取得了较好的安全性和速度性能。RSA算法研究 第3篇
基于RSA的无线加密算法研究 第4篇
贪心算法实验报告 第5篇
页面置换算法实验报告 第6篇
