文档库 最新最全的文档下载
当前位置:文档库 › (完整版)公开密钥加密算法RSA的Matlab实现毕业设计

(完整版)公开密钥加密算法RSA的Matlab实现毕业设计

(完整版)公开密钥加密算法RSA的Matlab实现毕业设计
(完整版)公开密钥加密算法RSA的Matlab实现毕业设计

公开密钥加密算法RSA的Matlab实现

[摘要]RSA算法是基于数论的公开密钥加密算法,它已经成为现在最流行的公钥加密算法和数字签名算法之一。其算法的安全性基于数论中大素数分解的困难性,所以RSA公钥密码体制算法的关键是如何产生大素数和进行大指数模幂运算。本文首先介绍了RSA 公开密钥加密算法的数学原理,并介绍了几种流行的产生大素数的算法。然后用matlab具体实现公钥加密算法RSA的加密和解密,从而实现了数据的安全传输。

[关键词] RSA算法;加密;素数

The Realization of RSA Algorithm for Public Key Encryption Based on Matlab

(Grade 07,Class 3,Major electronics and information engineering ,Communication

engineering Dept.,Tutor:

[abstract]:The algorithm is based on the theory of RSA public key encryption algorithm, it has become the most popular public key encryption algorithm and digital signature algorithm of one. The safety of the algorithm based on number theory cuhk the difficulty of prime decomposition, so the RSA public key cryptography algorithms is key to how to produce large prime Numbers DaZhi and transmit power operation. This paper first introduced the RSA public key encr -yption algorithm of mathematical theory, and introduces several popular produce large prime Numbers of the algorithm. Then use matlab RSA public key encryption algorithm re -alization of encryption and decryption is realized, and the safety of the data trans -mission.

[Key words]:RSA algorithm; encryption; prime number

目录

引言........................................................................................................................................... 1数据加密概述................................................................................................................

1.1基本概念..........................................

1.2 数据加密分类......................................

2 Matlab工具介绍 ....................................................................................................

2.1 MATLAB语言的主要特点 .............................

2.2 Matlab的程序设计................................. 2.2.1 脚本文件和函数文件 ........................... 2.2.2 函数调用和参数传递 ............................ 2.2.3 MATLAB的程序结构和控制流程...................

3 RSA公钥密码体制 .................................................................................................

3.1 算法简介 (1)

3.2算法的数学基础 (1)

3.3 RSA公钥密码算法 (1)

3.3.1 算法步骤 (1)

3.3.2 参数分析 (1)

3.3.3 安全性分析 (1)

3.4公钥密码体制中安全大素数的生成 ...........................................................

3.4.1 素数筛选 (1)

3.4.2 素数检测 (1)

3.5 RSA的Matlab实现 (1)

3.5.1算法原理 (1)

3.5.2 运行过程 (2)

3.5.3结论分析 (2)

4 基于RSA的数字签名 ..........................................................................................

4.1 数字签名概述 (2)

4.2 基于RSA的数字签名 (2)

4.3RSA数字签名方案的不足 (2)

5 RSA算法的实际应用和发展 ..........................................................................

5.1 算法的应用 (2)

5.2算法的改进 (2)

结论...........................................................................................................................................致谢...........................................................................................................................................参考文献 ...............................................................................................................................附录...........................................................................................................................................附录A:英文资料及翻译 . (3)

附录B:源程序 (4)

引言

随着Internet用户的激增,世界正步入网络经济的新时代。如网上购物、网上银行、网上证券等。然而,有一些人利用利用他们所掌握的技术非法侵入他人的计算机系统,窃取、篡改、破坏一些重要的数据,给社会造成巨大的损失。密码技术的发展与应用,对解决信息交换的安全问题,保障数据信息的安全,起着不可忽视的作用。

所谓密码技术,就是针对信息进行重新编码,从而达到隐藏信息的内容,使非法用户无法获取信息真实内容的一种手段。目前在网络中,一般采用两种密码体制:对称密钥体制和非对称密钥体制。对称密钥体制中的加密密钥和解秘密钥是相同的,所以又称密秘密钥密码体制。对称密钥算法运算效率高、使用方便、加密效率高,在处理大量数据时被广泛使用,但其关键是要保证密钥的安全,为安全起见,密钥要定期改变,所以,对称密钥就存在一个如何安全管理密钥的问题。与对称密钥体制相对应的非对称密钥体制又称为公开密钥密码体制,它是在1976 年由Diffe 和Hellman 发表的《密码学的新方向》一文中提出的,从此打破了长期使用单密钥体制的束缚。自此提出公约密码思想以后,涌现出很多的公约密钥算法体系,经过20多年的实践检验,公约系统的应用技术日趋完善,应用领域日趋广泛。公开密钥密码体制,加密密钥和解秘密钥是分开采用一对不同的密钥进行的,分别存在一个公钥和私钥,公钥公开,私钥保密,并且知道其中一个时并不能从中推出另一个。其典型的算法有背包密码、RSA等。其中RSA公约算法系统因为其可靠安全性,易于实现性,更是受大家的认可和欢迎。

RSA加密算法的最大优点就是不需要对密钥通信进行保密,所需传输的只有公开密钥,这样就省去了一条开销很大的密钥传输信道。其保密性强,密钥管理方便,并且具有数字签名、认证和签别等多种功能,特别适合于现代保密通信的需要。大多数使用公钥密码进行加密和数字签名的产品和标准使用的都是RSA算法。RSA的安全性

是基于大数因子分解的困难性。目前一般认为RSA需要1024位以上的字长才有安全保障。由于RSA所采用的模幂运算耗时太多,因此它通常只能用于加密少量数据或者加密密钥。需要注意的是,RSA的安全性只是一种计算安全性,绝对不是无条件的安全性,这是由它的理论基础决定的。所以,在实现RSA算法的过程中,每一步都应该尽量从安全性方面考虑。本文就RSA算法以及如何用Matlab语言实现给于了详细的分析。

1 数据加密概述

密码学是一门古老而深奥的学科,它对一般人来说是陌生的,因为长期以来,它只在很少的范围内,如军事、外交、情报等部门使用。计算机密码学是研究计算机信息加密、解密及其变换的科学,是数学和计算机的交叉学科,也是一门新兴的学科。随着计算机网络和计算机通讯技术的发展,计算机密码学得到前所未有的重视并迅速普及和发展起来。在国外,它已成为计算机安全主要的研究方向,也是计算机安全课程教学中的主要内容。

密码是实现秘密通讯的主要手段,是隐蔽语言、文字、图象的特种符号。凡是用特种符号按照通讯双方约定的方法把电文的原形隐蔽起来,不为第三者所识别的通讯方式称为密码通讯。在计算机通讯中,采用密码技术将信息隐蔽起来,再将隐蔽后的信息传输出去,使信息在传输过程中即使被窃取或载获,窃取者也不能了解信息的内容,从而保证信息传输的安全。

任何一个加密系统至少包括下面四个组成部分:

(1)未加密的报文,也称明文。

(2)加密后的报文,也称密文。

(3)加密解密设备或算法。

(4)加密解密的密钥。

发送方用加密密钥,通过加密设备或算法,将信息加密后发送出去。接收方在收到密文后,用解密密钥将密文解密,恢复为明文。如果传输中有人窃取,他只能得到无法理解的密文,从而对信息起到保密作用。

1.1 基本概念

数据加密技术就是指将一个信息或明文经过加密钥匙及加密函数转换,变成无意义的密文,而接收方则将此密文经过解密函数.解密钥匙还原成明文。加密技术是网络安全技术的基石。

明文,即加密前的真实的数据或信息,它是可以被外界所识别,它指代的含义比较广泛,比如用户A要将一份文件发送给用户B,那么我们就将用户A手里所拿的那份文件称之为明文。

密文,就是对信息经过一定的处理,使它变成无意义的乱码,非指定用户无法对它进行识别,例如A使用密钥K加密消息并将其发送给B,B收到加密的消息后,使用密钥K对其解密以恢复原始消息,那么在这一过程当中A在途中发送给B的东西我们就叫它密文,因为这个文件除B外,其他人得到它也没有任何意义,这就保证了信息传送的保密性。

完成加密和解密的算法成为为密码体制。人们一方面要把自己的信号隐蔽起来,另一方面则想把别人的隐蔽信息挖掘出来,于是就产生了密码分析的逆科学——密码分析。密码分析研究的问题是如何把密文转换成明文。把密文转换成明文的过程称为破译。破译也是进行函数变换,变换过程中使用的参数也叫密钥。

一般地,如果求解一个问题需要一定量的计算,但环境所能提供的实际资源却无法实现,则这种问题是计算上不可能的。如果一个密码体制的破译是计算上不可能的。则称该密码体制是计算上安全的。密码体制必须满足三个基本要求:(1)对所有的密钥、加密和解密都必须迅速有效;

(2)体制必须容易使用;

(3)体制的安全性必须只依赖于密钥的保密性。密码体制要实现的功能可分为保

密性和真实性两种。

保密性要求密码分析员无法从截获的密文中求出明文。一般情况下一个密码体制的保密性包括两项要求:

(1)即使截获了一段密文C,甚至知道了与它对应的明文M,密码分析要从系统中求出解密变换,仍然是计算上不可行的。

(2)密码分析员要由截获的密文C中系统的求出明文M是计算上不可能的。

数据的真实性要求密码分析员无法用虚假的密文代替真是密文而不被察觉,它也包括两个要求:

(1)对于给定的C,即使密码分析员知道了对应于它的明文M,要系统的求出加密变换仍然是计算上不可能的。

(2)密码分析员要系统地找到密文,使其是明文空间上有意义的明文,这在计算上是不可能的。

1.2 数据加密分类

专用密钥:又称为对称密钥或单密钥,加密和解密时使用同一个密钥,即同一个算法。如DES和MIT的Kerberos算法。单密钥是最简单方式,通信双方必须交换彼此密钥,当需给对方发信息时,用自己的加密密钥进行加密,而在接收方收到数据后,用对方所给的密钥进行解密。当一个文本要加密传送时,该文本用密钥加密构成密文,密文在信道上传送,收到密文后用同一个密钥将密文解出来,形成普通文体供阅读。在对称密钥中,密钥的管理极为重要,一旦密钥丢失,密文将无密可保。这种方式在与多方通信时因为需要保存很多密钥而变得很复杂,而且密钥本身的安全就是一个问题。

公开密钥:又称非对称密钥,加密和解密时使用不同的密钥,即不同的算法,虽然两者之间存在一定的关系,但不可能轻易地从一个推导出另一个。有一把公用的加密密钥,有多把解密密钥,如RSA算法。

非对称密钥由于两个密钥(加密密钥和解密密钥)各不相同,因而可以将一个密

钥公开,而将另一个密钥保密,同样可以起到加密的作用。

在这种编码过程中,一个密码用来加密消息,而另一个密码用来解密消息。在两个密钥中有一种关系,通常是数学关系。公钥和私钥都是一组十分长的、数字上相关的素数(是另一个大数字的因数)。有一个密钥不足以翻译出消息,因为用一个密钥加密的消息只能用另一个密钥才能解密。每个用户可以得到唯一的一对密钥,一个是公开的,另一个是保密的。公共密钥保存在公共区域,可在用户中传递,甚至可印在报纸上面。而私钥必须存放在安全保密的地方。任何人都可以有你的公钥,但是只有你一个人能有你的私钥。它的工作过程是:“你要我听你的吗?除非你用我的公钥加密该消息,我就可以听你的,因为我知道没有别人在偷听。只有我的私钥(其他人没有)才能解密该消息,所以我知道没有人能读到这个消息。我不必担心大家都有我的公钥,因为它不能用来解密该消息。”

公钥加密体制具有以下优点:

(1)密钥分配简单。

(2)密钥的保存量少。

(3)可以满足互不相识的人之间进行私人谈话时的保密性要求。

(4)可以完成数字签名和数字鉴别。

明文M

密文C=E(M,) M=D(C,)

(密钥本)

图1.1 公钥密码体制示意图

对称密钥:对称密钥是最古老的,一般说“密电码”采用的就是对称密钥。由于对称密钥运算量小、速度快、安全强度高,因而目前仍广泛被采用。

DES是一种数据分组的加密算法,它将数据分成长度为64位的数据块,其

中8位用作奇偶校验,剩余的56位作为密码的长度。第一步将原文进行置换,得到64位的杂乱无章的数据组;第二步将其分成均等两段;第三步用加密函数进行变换,并在给定的密钥参数条件下,进行多次迭代而得到加密密文。

非对称加密技术:数字签名一般采用非对称加密技术(如RSA),通过对整个明文进行某种变换,得到一个值,作为核实签名。接收者使用发送者的公开密钥对签名进行解密运算,如其结果为明文,则签名有效,证明对方的身份是真实的。当然,签名也可以采用多种方式,例如,将签名附在明文之后。数字签名普遍用于银行、电子贸易等。

数字签名:数字签名不同于手写签字,数字签名随文本的变化而变化,手写签字反映某个人个性特征,是不变的;数字签名与文本信息是不可分割的,而手写签字是附加在文本之后的,与文本信息是分离的。

值得注意的是,能否切实有效地发挥加密机制的作用,关键的问题在于密钥的管理,包括密钥的生存、分发、安装、保管、使用以及作废全过程。

2 Matlab工具介绍

2.1 MATLAB语言的主要特点

(1).具有丰富的数学功能。

①包括矩阵各种运算。如:正交变换、三角分解、特征值、常见的特殊矩阵等。

②包括各种特殊函数。如:贝塞尔函数、勒让德函数、伽码函数、贝塔函数、椭圆函数等。

③包括各种数学运算功能。如:数值微分、数值积分、插值、求极值、方程求根、FFT 、常微分方程的数值解等。

(2).具有很好的图视系统。

①可方便地画出两维和三维图形。

②高级图形处理。如:色彩控制、句柄图形、动画等。

③图形用户界面GUI制作工具,可以制作用户菜单和控件。使用者可以根据自己的需求编写出满意的图形界面。

(3).可以直接处理声言和图形文件。

①声言文件。如: WAV文件(例:wavread,sound等)。

②图形文件。如: bmp 、gif 、 pcx 、tif 、jpeg等文件。

(4). 具有若干功能强大的应用工具箱。

如:SIMULINK、COMM、DSP、 SIGNAL等16种工具箱。

(5). 使用方便,具有很好的扩张功能。

①使用MATLAB语言编写的程序可以直接运行,无需编译。

②可以M文件转变为独立于平台的EXE可执行文件。

③ MATLAB的应用接口程序API是MATLAB提供的十分重要的组件,由一系列接口指令组成。用户就可在FORTRAN或C中,把MATLAB当作计算引擎使用。

(6). 具有很好的帮助功能

①提供十分详细的帮助文件(PDF 、HTML 、demo文件)。

②联机查询指令:help指令(例:help elfun,help exp,help simulink),lookfor关键词(例: lookfor fourier )。

2.2 Matlab的程序设计

2.2.1 脚本文件和函数文件

M文件有两种形式:脚本文件(Script File)和函数文件(Function File )。这两种文件的扩展名,均为“ . m” 。

(1)M脚本文件:

①对于一些比较简单的问题,在指令窗中直接输入指令计算。

②对于复杂计算,采用脚本文件(Script file)最为合适。

③ MATLAB只是按文件所写的指令执行。

④ M脚本文件的特点是:

⑤脚本文件的构成比较简单,只是一串按用户意图排列而成的(包括控制流向指令在内的)MATLAB指令集合。

⑥脚本文件运行后,所产生的所有变量都驻留在 MATLAB基本工作空间(Base workspace)中。只要用户不使用清除指令(clear), MATLAB指令窗不关闭,这些变量将一直保存在基本工作空间中。

(2)M函数文件:

①与脚本文件不同,函数文件犹如一个“黑箱”,把一些数据送进并经加工处理,再把结果送出来。

② MATLAB提供的函数指令大部分都是由函数文件定义的。

③ M函数文件的特点是:

④从形式上看,与脚本文件不同,函数文件的笫一行总是以“function”引导的“函数申明行”。

⑤从运行上看,与脚本文件运行不同,每当函数文件运行, MATLAB就会专门为它开辟一个临时工作空间,称为函数工作空间( Function workspace)。当执行文件最后一条指令时,就结束该函数文件的运行,同时该临时函数空间及其所有的中间变量就立即被清除。

⑥ MATLAB允许使用比“标称数目”较少的输入输出宗量,实现对函数的调用。

(3)M文件的一般结构:

①由于从结构上看,脚本文件只是比函数文件少一个“函数申明行”,所以只须描述清楚函数文件的结构。

②典型M函数文件的结构如下:

③函数申明行:位于函数文件的首行,以关键functio开头,函数名以及函数

的输入输出宗量都在这一行被定义。

④笫一注释行:紧随函数申明行之后以%开头笫一注释行。该行供lookfor关键词查询和 help在线帮助使用。

⑤在线帮助文本区:笫一注释行及其之后的连续以%开头的所有注释行构成整个在线帮助文本。

⑥编写和修改记录:与在线帮助文本区相隔一个“空”行,也以%开头,标志编写及修改该M文件的作者和日期等。

⑦函数体:为清晰起见,它与前面的注释以“空”行相隔。

2.2.2 函数调用和参数传递

(1)局部变量和全局变量:

①局部(Local)变量:它存在于函数空间内部的中间变量,产生于该函数的运行过程中,其影响范围也仅限于该函数本身。

②全局(Global)变量:通过 global 指令,MATLAB也允许几个不同的函数空间以及基本工作空间共享同一个变量,这种被共享的变量称为全局变量。

(2)函数调用:

①在MATLAB中,调用函数的常用形式是:

[输出参数1,输出参数2,…] = 函数名(输入参数1,输入参数2, …)

②函数调用可以嵌套,一个函数可以调用别的函数,甚至调用它自己(递归调用)。

(3)参数传递:

① MATLAB在函数调用上有一个与众不同之处:函数所传递的参数具有可调性。

②传递参数数目的可调性来源于如下两个MATLAB永久变量:

③函数体内的 nargin 给出调用该函数时的输入参数数目。

④函数体内的 nargout 给出调用该函数时的输出参数数目。

⑤只要在函数文件中包括这两个变量,就可以知道该函数文件调用时的输入参数和输出参数数目。

⑥值得注意:nargin、 nargout 本身都是函数,不是变量,所以用户不能赋值,也不能显示。

⑦“变长度”输入输出宗量:varargin 、 varrgout。具有接受“任意多输入” 、返回“任意多输出”的能力。

⑧跨空间变量传递:evalin。

2.2.3 M文件的调试

(1)编写 M文件时,错误(Bug)在所难免。错误有两种:语法(Syntax)错误和运行(Run-time)错误。

(2)语法错误是指变量名、函数名的误写,标点符号的缺、漏等。对于这类错误,通常能在运行时发现,终止执行,并给出相应的错误原因以及所在行号。

(3)运行错误是算法本身引起的,发生在运行过程中。相对语法错误而言,运行错误较难处理。尤其是M函数文件,它一旦运行停止,其中间变量被删除一空,错误很难查找。

(4)有两种调试方法:直接调试法和工具调试法。

(5)直接调试法:可以用下面方法发现某些运行错误。

(6)在M文件中,将某些语句后面的分号去掉,迫使M文件输出一些中间计算结果,以便发现可能的错误。

(7)在适当的位置,添加显示某些关键变量值的语句(包括使用 disp 在内)。

(8)利用 echo 指令,使运行时在屏幕上逐行显示文件内容。echo on 能显示M脚本文件;echo FunNsme on 能显示名为FunNsme 的M函数文件。

(9)在原M脚本或函数文件的适当位置,增添指令 keyboard 。 keyboard 语句可以设置程序的断点。

(10)通过将原M函数文件的函数申明行注释掉,可使一个中间变量难于观察的

M函数文件变为一个所有变量都保留在基本工作空间中的M脚本文件。

3 RSA公钥密码体制

3.1 算法简介

公钥加密算法的典型代表是RSA (Rivest , Shamir , Adelman)算法,它是公共密钥机制中的一种比较成熟的算法。它是建立在“大数分解和素数据检测”的理论基础上的,两个大素数相乘在计算机上是容易实现的, 但将该乘积分解成两个素数因子的计算量却相当巨大, 大到甚至在计算机上不可能实现,所以就确保了RSA算法的安全性。

RSA算法是第一个既能用于数据加密又能用于数字签名的算法,它为公用网络上信息的加密和鉴别提供了一种基本的方法,因此对它的开发和研究对我们进行知识总结和积累并将所学与实际相结合都有重大的实际意义。

3.2 算法的数学基础

基于RSA算法的数学定理:

定义:设m 是正整数,1,2,3,…,m 中与m 互素的数的个数记作,称为欧拉函数。

定理1(欧拉定理)若整数a和m 互素,即gcd(a,m)=1,则

特别当p为素数时,对任意的a,有

定理2 若m1, gcd(a,m)=1,则存在c,使得 ca1(modm),称c 为a 的模m 的逆,记作 (modm)

定理3 若, , ,…, ,则有

定理4 (中国剩余定理) 设:是两两互素的正整数,则对任意的整数一次同余方程组:

(i=1,2,…,k)对模[:] 有惟一解,

11111(mod ),k k k x M M a M M a m --≡+

是满足11(mod ),1j j j M M m j k -≡≤≤ 的一个整数,即对模的逆。

3.3 RSA 公钥密码算法

3.3.1 算法步骤

首先,产生密钥

(1)随机选取两个大素数p 与q ;

(2)计算n=p*q (公开),Φ(n )=(p-1)*(q-1)(保密);

(3)随机选取正整数e,使之满足gcd(e,Φ(n))=1,且1

(4)利用欧几里得算法计算d,使之满足ed ≡1(mod Φ(n)),d 为保密的解密密钥;

(5)用E=作为公钥,用D=作为私钥。

其次,加密和解密,用RSA 公钥密码体制加密时,先将明文数字化,然后进行分组,每组的长度不超过log(n),再每组单独加密和解密。

加密过程如下:

假设要加密的明文组为m(0?m

m=D(c)= (mod n);m 就为恢复出的明文,它应该与前面输入的待加密的明文内容一致。

RSA 算法整体思路如上所示,在本文中我们就此算法过程用对应Matlab 语言实现。

3.3.2 参数分析

RSA 算法的安全性等价于分解n 的困难性,但是在实际的应用中,很多时候是因为算法实现的细节漏洞导致被攻击,所以在RSA 算法构造密码系统时,为了保证系统的安全性需要仔细地选择使用的参数。

RSA 算法主要的参数有3 个:模数n 、加密密钥e 和解密密钥d 。

(1)算法模n 的确定:

RSA 模数n =p*q 是RSA 算法安全性的核心,如果模数n 被分解,则RSA 公钥密码体制将立刻被攻破,所以选择合适的n 是实现RSA 算法的重要环节。

一般来讲,模数n 的选择可以遵守以下4个原则:

① n=p*q , 要求p 和q 为强素数(Strong Prime );

强素数定义如下:存在两个大素数使得;存在4 个大素数,使得

1112222(1),(1),(1),(1)r p s p r p s p -+-+;称为三级素数,为二级素数。

② p 和q 之差要大,相差几位以上;

③ p - 1 与q - 1 的最大公因子要小;

④ p 和q 要足够大。

这是应用R S A 算法要遵守的最基本原则,如果RSA 算法是安全的,则n=p*q 必须足够大,使得因式分解模数n 在计算上是不可行的,下面给出的是一般性使用原则:

① 临时性(Casual )384bit ,经过努力可以破译;

② 商用性(Commercial )512bit ,可由专业组织破译;

③ 军用性(Military )1024b it ,专家预测十年内不可破译。

随着计算机能力的不断提高和分布式运算的发展,没有人敢断言具体的安全密钥长度。

(2)算法e 与d 的选取原则:

在RSA算法中的条件是很容易满足的,这是因为任意两个随机数互素的概率

为,如果e ,d 比较小,加、解密的速度快,也便于存储,但这必然导致安全性问题,一般的e,d 的

选取原则如下:

① e不可过小。经验上e 选16位的素数,这样既可以有效地防止攻击,又有较快的加、解密速度。

②最好选e 为的阶数,即存在i ,使得,i 达到,可以有效地抗击攻击。

③ d 要大于。选定e 后可使用欧几里德算法在多项式时间内计算出d。

3.3.3 安全性分析

如果说RSA体制的安全性等价于因子分解,那就是说,作为公钥选择的(e,n)参数,n是不能轻易被因子分解的,否则构造单向函数的T=Φ(n)=(p-1)(q-1)就没有秘密可言了。原因很简单,RSA的安全性依赖于因子分解的困难性,目前因子分解速度最快方法的时间复杂度为:T=O(exp(sqrt(ln(n)ln ln(n))))=O(),且n因子被分解,就意味着RSA系统被攻破。反过来,能攻破RSA系统,表明可以分解n 的因子,不过这不是绝对的。所以出于安全性考虑,在设计RSA系统时,对n的选择是很重要的。

在RSA算法中,若n =p*q被因数分解,则RSA便被攻破。因为若p,q 已知,则Φ(n)=(p- 1)*(q - 1)便可以计算出,解密密钥d 便可利用欧几里得算法求出。因此RSA 的安全性是依赖于因数分解的困难性。在上一节的参数分析中我们重点讲了对各参数选取原则,这里不再重复。在许多实际应用中,人们总希望使用位数较短的密钥d,一是可降低解出或签名的时间,二是能够满足计算能力低于主机的硬件芯片的需求,比如IC卡中的CPU处理。

现在我们就分析几个RSA体制的安全性问题。

(1)弱密钥情形

类似其他密码体制一样,RSA体制也存在弱密钥现象。若已知明文组=123, =183, =72, =30,假定n=pq=17X11=187,取e=7时,可以发现,明文m经过RSA连续变换后,就能恢复原文。比如:根据=RSA()=(mod n),则有:

==183(mod187)

==72(mod187)

==30(mod187)

==123(mod187)

这时=,对加密系统来说是不可靠的,必须加以克服。

(2)同模攻击的可能性

假定两个用户,共享一个模为n的RSA算法,加密密钥分别为,,并且gcd(,)=1,如果用户A想加密同一个明文m,分别从,加密得到密文: = mod n和=mod n,分别将送给,送给。而攻击者截获两个密文后,可以通过使用扩展欧几里得算法得到r,s,使得r. +s. =1.然后按下列计算:

. mod n=()()mod n= m

其中, ==为同一明文,表明即使RSA密码系统很安全,但攻击者破获A发送的明文也是可能的。所以实际中建议不同用户不可使用公共的模n。除此之外,不同用户选用的素数也是不能相同的。否则,任何人都可以用欧几里得算法获得(,)= p,结果容易得到,的分解式。

(3)由密文泄露明文相关的部分信息量

与其他一些密码弱点一样,RSA体制同样存在将明文的部分信息由密文泄露出去的可能。比如给定密文:C=mod,由可知,其中e必为奇数情形。根据Jcaobi符号容易推出.

因此,只要给定一个密文C,不用通过解密密文就能有效的计算出结果,即反

RSA公钥加密算法及其安全性讨论

RSA公钥加密算法及其安全性讨论 RSA algorithm for public-key encryption and its security 摘要:RSA是目前最有影响力的公钥加密算法,它能够抵抗到目前为止已知的所有密码攻击,已被ISO推荐为公钥数据加密标准。RSA算法基于一个十分简单的数论事实:将两个大素数相乘十分容易,但那时想要对其乘积进行因式分解却极其困难,因此可以将乘积公开作为加密密钥。但是,RSA的安全性依赖于大数的因子分解,却并没有从理论上证明破译RSA的难度与大数分解难度等价,即RSA的重大缺陷是无法从理论上把握它的保密性能到底如何。随着计算能力的不断进步和各种攻击方法的出现,RSA算法是否真的安全。 关键词:RSA,公钥,加密,大数分解,攻击,安全性 1 RSA加密算法 1.1公钥简介 密码体制按密钥类型分为对称密钥和不对称密钥。对称密钥即加密、解密用的是同一个密钥,又称为私钥。不对称密钥即公钥加密,加密、解密用的是不同的密钥,一个密钥“公开”,即公钥,另一个自己秘密持有,即私钥,加密方用公钥加密,只有用私钥才能解密——史称公钥加密体系:PKI。 1.2 RSA算法简介 RSA加密算法是一种非对称加密算法。RSA加密算法是Ron Rivest、Adi Shamirh和Len Adleman于1977年在美国麻省理工学院开发出来的,次年首次对外公开宣布,是第一个既能用于数据加密也能用于数字签名的算法。RSA就是他们三人姓氏开头字母拼在一起组成的。RSA是建立在“大整数的素因子分解是困难问题”基础上的,其安全性取决于大数分解,也就是大数分解质因数的困难性。换言之,对一极大整数做因式分解愈困难,RSA演算法愈可靠。假如有人找到一种快速因式分解的演算法的话,那么用RSA加密的信息的可靠性肯定会急剧下降,但找到这样的演算法的可能性是非常小的,今天只有短的RSA钥匙才可能被强力方式解破。到2008年为止,世界上还没有任何可靠的攻击RSA算法的方式。只要其钥匙的长度足够长,用RSA加密的信息实际上是不能被解破的。但在分布式计算和量子计算机理论日趋成熟的今天,RSA加密安全性受到了挑战。 1.3 RSA算法 1.3.1公钥和私钥的产生 假设Alice想要通过一个不可靠的媒体接收Bob的一条私人讯息。她可以用以下的方式来产生一个公钥和一个私钥: (1)选两个保密的足够大的素数p和q。同时对p, q严加保密,不让任何人知道。 (2)计算N=p×q。 (3)计算f(n)=(p-1)(q-1)。 (4)找一个与f(n)互质的数e,且1

密码学实验-RSA公钥密码

实验报告 实验八、RSA公钥密码 实验目的: 熟练掌握RSA公钥密码算法原理及实现。 实验内容: 1、写出RSA公钥密码算法及其实现。 2、当取两素数分别为17、23,加密密钥为35时,写出其明文空间,并求出下列明文的密 文:1、15、17、23、48、235。 3、当取两素数分别为17、23,加密密钥为35时,求相应的解密密钥。 实验结果: 1.算法: Step1:选取两个大素数p和q,p和q保密 Step2:计算n=pq,f(n)=(p-1)(q-1),n公开,f(n)保密 Step3:随机选取正整数1 #include #include void main() { int i; double M,C,e,n,p,q,t; cout<<"请输入素数p:"; cin>>p; cout<<"请输入素数q:"; cin>>q;

n=p*q; t=(p-1)*(q-1); cout<<"请输入加密密钥e:"; cin>>e; cout<<"输入明文M:"; cin>>M; C=1; for(i=0;i

常见公钥加密算法有哪些

常见公钥加密算法有哪些 什么是公钥加密公钥加密,也叫非对称(密钥)加密(public key encrypTIon),属于通信科技下的网络安全二级学科,指的是由对应的一对唯一性密钥(即公开密钥和私有密钥)组成的加密方法。它解决了密钥的发布和管理问题,是目前商业密码的核心。在公钥加密体制中,没有公开的是私钥,公开的是公钥。 常见算法RSA、ElGamal、背包算法、Rabin(Rabin的加密法可以说是RSA方法的特例)、Diffie-Hellman (D-H)密钥交换协议中的公钥加密算法、EllipTIc Curve Cryptography (ECC,椭圆曲线加密算法)。使用最广泛的是RSA算法(由发明者Rivest、Shmir和Adleman 姓氏首字母缩写而来)是著名的公开金钥加密算法,ElGamal是另一种常用的非对称加密算法。 非对称是指一对加密密钥与解密密钥,这两个密钥是数学相关,用某用户密钥加密后所得的信息,只能用该用户的解密密钥才能解密。如果知道了其中一个,并不能计算出另外一个。因此如果公开了一对密钥中的一个,并不会危害到另外一个的秘密性质。称公开的密钥为公钥;不公开的密钥为私钥。 如果加密密钥是公开的,这用于客户给私钥所有者上传加密的数据,这被称作为公开密钥加密(狭义)。例如,网络银行的客户发给银行网站的账户操作的加密数据。 如果解密密钥是公开的,用私钥加密的信息,可以用公钥对其解密,用于客户验证持有私钥一方发布的数据或文件是完整准确的,接收者由此可知这条信息确实来自于拥有私钥的某人,这被称作数字签名,公钥的形式就是数字证书。例如,从网上下载的安装程序,一般都带有程序制作者的数字签名,可以证明该程序的确是该作者(公司)发布的而不是第三方伪造的且未被篡改过(身份认证/验证)。 对称密钥密码体制 所谓对称密钥密码体制,即加密密钥与解密密钥是相同的密码体制。 数据加密标准DES属于对称密钥密码体制。它是由IBM公司研制出,于1977年被美国

RSA加密算法的基本原理

RSA加密算法的基本原理 1978年RSA加密算法是最常用的非对称加密算法,CFCA 在证书服务中离不了它。但是有不少新来的同事对它不太了解,恰好看到一本书中作者用实例对它进行了简化而生动的描述,使得高深的数学理论能够被容易地理解。我们经过整理和改写特别推荐给大家阅读,希望能够对时间紧张但是又想了解它的同事有所帮助。 RSA是第一个比较完善的公开密钥算法,它既能用于加密,也能用于数字签名。RSA以它的三个发明者Ron Rivest,Adi Shamir,Leonard Adleman的名字首字母命名,这个算法经受住了多年深入的密码分析,虽然密码分析者既不能证明也不能否定RSA的安全性,但这恰恰说明该算法有一定的可信性,目前它已经成为最流行的公开密钥算法。 RSA的安全基于大数分解的难度。其公钥和私钥是一对大素数(100到200位十进制数或更大)的函数。从一个公钥和密文恢复出明文的难度,等价于分解两个大素数之积(这是公认的数学难题)。 RSA的公钥、私钥的组成,以及加密、解密的公式可见于下表: 可能各位同事好久没有接触数学了,看了这些公式不免一头雾水。别急,在没有正式讲解RSA加密算法以前,让我们先复习一下数学上的几个基本概念,它们在后面的介绍中要用到: 一、什么是“素数”? 素数是这样的整数,它除了能表示为它自己和1的乘积以外,不能表示为任何其它两个整数的乘积。例如,15=3*5,所以15不是素数;又如,12=6*2=4*3,所以12也不是素数。另一方面,13除了等于13*1以外,不能表示为其它任何两个整数的乘积,所以13是一个素数。素数也称为“质数”。 二、什么是“互质数”(或“互素数”)? 小学数学教材对互质数是这样定义的:“公约数只有1的两个数,叫做互质数。”这里所说的“两个数”是指自然数。 判别方法主要有以下几种(不限于此): (1)两个质数一定是互质数。例如,2与7、13与19。 (2)一个质数如果不能整除另一个合数,这两个数为互质数。例如,3与10、5与26。(3)1不是质数也不是合数,它和任何一个自然数在一起都是互质数。如1和9908。(4)相邻的两个自然数是互质数。如15与16。 (5)相邻的两个奇数是互质数。如49与51。 (6)大数是质数的两个数是互质数。如97与88。 (7)小数是质数,大数不是小数的倍数的两个数是互质数。如7和16。 (8)两个数都是合数(二数差又较大),小数所有的质因数,都不是大数的约数,这两个数是互质数。如357与715,357=3×7×17,而3、7和17都不是715的约数,

用实例讲解RSA加密算法(精)

可能各位同事好久没有接触数学了,看了这些公式不免一头雾水。别急,在没有正式讲解RSA加密算法以前,让我们先复习一下数学上的几个基本概念,它们在后面的介绍中要用到: 一、什么是“素数”? 素数是这样的整数,它除了能表示为它自己和1的乘积以外,不能表示为任何其它两个整数的乘积。例如,15=3*5,所以15不是素数;又如,12=6*2=4*3,所以12也不是素数。另一方面,13除了等于13*1以外,不能表示为其它任何两个整数的乘积,所以13是一个素数。素数也称为“质数”。 二、什么是“互质数”(或“互素数”)? 小学数学教材对互质数是这样定义的:“公约数只有1的两个数,叫做互质数。”这里所说的“两个数”是指自然数。 判别方法主要有以下几种(不限于此): (1)两个质数一定是互质数。例如,2与7、13与19。 (2)一个质数如果不能整除另一个合数,这两个数为互质数。例如,3与10、5与26。(3)1不是质数也不是合数,它和任何一个自然数在一起都是互质数。如1和9908。(4)相邻的两个自然数是互质数。如15与16。 (5)相邻的两个奇数是互质数。如49与51。 (6)大数是质数的两个数是互质数。如97与88。 (7)小数是质数,大数不是小数的倍数的两个数是互质数。如7和16。 (8)两个数都是合数(二数差又较大),小数所有的质因数,都不是大数的约数,这两个数是互质数。如357与715,357=3×7×17,而3、7和17都不是715的约数,这两个数为互质数。等等。 三、什么是模指数运算? 指数运算谁都懂,不必说了,先说说模运算。模运算是整数运算,有一个整数m,以n 为模做模运算,即m mod n。怎样做呢?让m去被n整除,只取所得的余数作为结果,就

公钥加密算法

实验五公钥加密算法—RSA 一、实验目的 通过使用RSA算法对实验数据进行加密和解密,掌握公钥加密算法的基本原理,熟练掌握RSA算法各功能模块的工作原理和具体运算过程。 二、实验原理 RSA公钥加密算法是1977年由Ron Rivest、Adi Shamirh和LenAdleman在(美国麻省理工学院)开发的。RSA取名来自开发他们三者的名字。RSA是目前最有影响力的公钥加密算法,它能够抵抗到目前为止已知的所有密码攻击,已被ISO推荐为公钥数据加密标准。RSA算法基于一个十分简单的数论事实:将两个大素数相乘十分容易,但那时想要对其乘积进行因式分解却极其困难,因此可以将乘积公开作为加密密钥。 1. RSA的密钥生成 RSA的算法涉及三个参数,n、e、d。 其中,n是两个大质数p、q的积,n的二进制表示时所占用的位数,就是所谓的密钥长度。鉴于现代对于大整数分解的水平不断增强,一般P、Q的取值都要求在1024位以上。 e和d是一对相关的值,e可以任意取,但要求e与(p-1)*(q-1)互质;再选择d,要求: (e*d)mod((p-1)*(q-1))=1。 就是密钥对。一般将前者当作公钥,后者作为私钥使用。 2. RSA加密/解密过程 RSA加解密和解密的算法完全相同,设A为明文,B为密文,则: A=B^e mod n;B=A^d mod n; e和d可以互换使用,即: A=B^d mod n;B=A^e mod n; 三、实验环境 运行Windows或Linux操作系统的PC机,具有gcc(Linux)、VC(Windows)等C语言编译环境。 四、 实验内容和步聚 1.根据本讲义提供的RSA程序,分析RSA算法的实现过程: (1).利用:void GenerateKey(RSA_Key& PublicKey,RSA_Key& PrivateKey,unsigned int iKeySize)函数根据实际需要生成符合要求长度的公钥和私钥,大致步骤如下: a) 随机生成两个指定长度的大素数P,Q。 b) 计算N=P*Q,以及N的欧拉函数φ(N)=(P-1)*(Q-1)。 c) 随机生成一个与φ(N)互素的大整数E(公钥)。 d) 根据公式ed≡1(modΦ(N)),利用函数multi_inverse(1, Big*, Big, Big*)计算出 私钥D。 (2).将某个大整数赋值给一个Big型变量M(明文)。 (3).调用函数powmod(..,..,..,..)对明文M加密得到密文C。 (4).调用函数powmod(..,..,..,..)对密文C解密得到明文D。 (5).比较M与D是否一致,判断实验结果是否正确。

RSA加密算法及实现

数学文化课程报告题目:RSA公钥加密算法及实现

RSA公钥加密算法及实现 摘要 公钥密码是密码学界的一项重要发明,现代计算机与互联网中所使用的密码技术都得益于公钥密码。公钥密码是基于数学的上的困难问题来保证其性。其中RSA加密算法是一项重要的密码算法,RSA利用大整数的质数分解的困难性,从而保证了其相对安全性。但如果发现了一种快速进行质数分解的算法,则RSA算法便会失效。本文利用C 语言编程技术进行了RSA算法的演示[1]。 关键词:C语言编程、RSA算法、应用数学。

RSA public key encryption algorithm Abstract Public key cryptography is an important invention in cryptography, thanks to public key cryptography, and it is used in modern computer and Internet password technology. Public key cryptography is based on the mathematics difficult problem to ensure its confidentiality. The RSA public key encryption algorithm is an important cryptographic algorithm, RSA using the difficulty that large integer is hard to be factorized into prime Numbers to ensure it safety. But if you can find a kind of fast algorithm to do the factorization, RSA algorithm will be failure. In this paper we used C language programming technology to demonstrate the RSA algorithm. Keywords:C language programming、RSA algorithm、Applied mathematics

用实例给新手讲解RSA加密算法

RSA加密算法是最常用的非对称加密算法,CFCA在证书服务中离不了它。但是有不少新来的同事对它不太了解,恰好看到一本书中作者用实例对它进行了简化而生动的描述,使得高深的数学理论能够被容易地理解。我们经过整理和改写特别推荐给大家阅读,希望能够对时间紧张但是又想了解它的同事有所帮助。 RSA是第一个比较完善的公开密钥算法,它既能用于加密,也能用于数字签名。RSA以它的三个发明者Ron Rivest, Adi Shamir, Leonard Adleman的名字首字母命名,这个算法经受住了多年深入的密码分析,虽然密码分析者既不能证明也不能否定RSA的安全性,但这恰恰说明该算法有一定的可信性,目前它已经成为最流行的公开密钥算法。 RSA的安全基于大数分解的难度。其公钥和私钥是一对大素数(100到200位十进制数或更大)的函数。从一个公钥和密文恢复出明文的难度,等价于分解两个大素数之积(这是公认的数学难题)。 RSA的公钥、私钥的组成,以及加密、解密的公式可见于下表: 可能各位同事好久没有接触数学了,看了这些公式不免一头雾水。别急,在没有正式讲解RSA加密算法以前,让我们先复习一下数学上的几个基本概念,它们在后面的介绍中要用到: 一、什么是“素数”? 素数是这样的整数,它除了能表示为它自己和1的乘积以外,不能表示为任何其它两个整数的乘积。例如,15=3*5,所以15不是素数;又如,12=6*2=4*3,所以12也不是素数。另一方面,13除了等于13*1以外,不能表示为其它任何两个整数的乘积,所以13是一个素数。素数也称为“质数”。 二、什么是“互质数”(或“互素数”)? 小学数学教材对互质数是这样定义的:“公约数只有1的两个数,叫做互质数。”这里所说的“两个数”是指自然数。 判别方法主要有以下几种(不限于此): (1)两个质数一定是互质数。例如,2与7、13与19。 (2)一个质数如果不能整除另一个合数,这两个数为互质数。例如,3与10、5与26。 (3)1不是质数也不是合数,它和任何一个自然数在一起都是互质数。如1和9908。 (4)相邻的两个自然数是互质数。如15与16。 (5)相邻的两个奇数是互质数。如49与51。 (6)大数是质数的两个数是互质数。如97与88。 (7)小数是质数,大数不是小数的倍数的两个数是互质数。如7和16。 (8)两个数都是合数(二数差又较大),小数所有的质因数,都不是大数的约数,这两个数是互质数。如357与715,357=3×7×17,而3、7和17都不是715的约数,这两个数为互质数。等等。 三、什么是模指数运算? 指数运算谁都懂,不必说了,先说说模运算。模运算是整数运算,有一个整数m,以n为模做模运算,即m mod n。怎样做呢?让m去被n整除,只取所得的余数作为结果,就叫做模运算。例如,10 mod 3=1; 26 mod 6=2;28 mod 2 =0等等。

RSA算法公钥加密算法

RSA1978年,MIT的Rivest、Shamir、Adleman提出RSA算法 非对称加密(公开密钥加密)密码学的一次革命,定义:KA≠KB ,KA、E和D公开 特点: 基于数论原理(大数分解难题) 是目前应用最广泛的公钥加密算法 属于块加密算法 在数论,对正整数n,欧拉函数是少于或等于n的数中与n互质的数的数目。此函数以其首名研究者欧拉命名,它又称为Euler's totient function、φ函数、欧拉商数等。 RSA算法原理 l 定义:RSA加密算法 确定密钥: 1. 找到两个大质数,p,q 2. Let n=pq 3. let m=(p-1)(q-1);Choose e and d such that de=1(%m). 4. Publish n and e as public key. Keep d and n as secret key. 加密: C=M^e(%n) 解密: M=(C^d)%n 其中C=M^e(%n) 为C%n=(M^e)%n 存在的主要问题是大数计算和大数存储的问题。 什么是RSA RSA算法是第一个能同时用于加密和数字签名的算法,也易于理解和操作。 RSA是被研究得最广泛的公钥算法,从提出到现在已近二十年,经历了各种攻击的考验,逐渐为人们接受,普遍认为是目前最优秀的公钥方案之一。RSA的安全性依赖于大数的因子分解,但并没有从理论上证明破译RSA的难度与大数分解难度等价。即RSA的重大缺陷是无法从理论上把握它的保密性能如何,而且密码学界多数人士倾向于因子分解不是NPC问题。

RSA的缺点主要有:A)产生密钥很麻烦,受到素数产生技术的限制,因而难以做到一次一密。B)分组长度太大,为保证安全性,n 至少也要600 bits以上,使运算代价很高,尤其是速度较慢,较对称密码算法慢几个数量级;且随着大数分解技术的发展,这个长度还在增加,不利于数据格式的标准化。目前,SET(Secure Electronic Transaction)协议中要求CA采用2048比特长的密钥,其他实体使用1024比特的密钥。 这种算法1978年就出现了,它是第一个既能用于数据加密也能用于数字签名的算法。它易于理解和操作,也很流行。算法的名字以发明者的名字命名:Ron Rivest, AdiShamir 和Leonard Adleman。 RSA算法是一种非对称密码算法,所谓非对称,就是指该算法需要一对密钥,使用其中一个加密,则需要用另一个才能解密。 RSA的算法涉及三个参数,n、e1、e2。 其中,n是两个大质数p、q的积,n的二进制表示时所占用的位数,就是所谓的密钥长度。 e1和e2是一对相关的值,e1可以任意取,但要求e1与(p-1)*(q-1)互质;再选择e2,要求(e2*e1)mod((p-1)*(q-1))=1。 (n及e1),(n及e2)就是密钥对。 RSA加解密的算法完全相同,设A为明文,B为密文,则:A=B^e1 mod n;B=A^e2 mod n; e1和e2可以互换使用,即: A=B^e2 mod n;B=A^e1 mod n; 一、RSA 的安全性 RSA的安全性依赖于大数分解,但是否等同于大数分解一直未能得到理论上的证明,因为没有证明破解RSA就一定需要作大数分解。假设存在一种无须分解大数的算法,那它肯定可以修改成为大数分解算法。目前,RSA 的一些变种算法已被证明等价于大数分解。不管怎样,分解n是最显然的攻击方法。现在,人们已能分解多个十进制位的大素数。因此,模数n 必须选大一些,因具体适用情况而定。 二、RSA的速度 由于进行的都是大数计算,使得RSA最快的情况也比DES慢上倍,无论是软件还是硬件实现。速度一直是RSA的缺陷。一般来说只用于少量数据加密。 三、RSA的选择密文攻击 RSA在选择密文攻击面前很脆弱。一般攻击者是将某一信息作一下伪装( Blind),让拥有私钥的实体签署。然后,经过计算就可得到它所想要的信息。实际上,攻击利用的都是同一个弱点,即存在这样一个事实:乘幂保留了输入的乘法结构:

公钥密码系统及RSA公钥算法

公钥密码系统及RSA公钥算法 摘要: 本文简单介绍了公开密钥密码系统的思想和特点,并具体介绍了RSA算法的理论基础,工作原理和具体实现过程,并通过一个简单例子说明了该算法是如何实现。在本文的最后,概括说明了RSA算法目前存在的一些缺点和解决方法。 关键词:公钥密码体制,公钥,私钥, RSA 中图分类号:TP309.7 §1引言 随着计算机联网的逐步实现,Internet前景越来越美好,全球经济发展正在进入信息经济时代,知识经济初见端倪。计算机信息的保密问题显得越来越重要,无论是个人信息通信还是电子商务发展,都迫切需要保证Internet网上信息传输的安全,需要保证信息安全。信息安全技术是一门综合学科,它涉及信息论、计算机科学和密码学等多方面知识,它的主要任务是研究计算机系统和通信网络内信息的保护方法以实现系统内信息的安全、保密、真实和完整。其中,信息安全的核心是密码技术。密码技术是集数学、计算机科学、电子与通信等诸多学科于一身的交叉学科。它不仅能够保证机密性信息的加密,而且能够实现数字签名、身份验证、系统安全等功能。是现代化发展的重要科学之一。本文将对公钥密码系统及该系统中目前最广泛流行的RSA 算法做一些简单介绍。 §2公钥密码系统 要说明公钥密码系统,首先来了解一下不同的加密算法:目前的加密算法按密钥方式可分为单钥密码算法和公钥密码算法。 2.1. 单钥密码 又称对称式密码,是一种比较传统的加密方式,其加密运算、解密运算使用的是同样的密钥,信息的发送者和信息的接收者在进行信息的传输与处理时,必须共同持有该密码(称为对称密码)。因此,通信双方都必须获得这把钥匙,并保持钥匙的秘密。 单钥密码系统的安全性依赖于以下两个因素:第一,加密算法必须是足够强的,仅仅基于密文本身去解密信息在实践上是不可能的;第二,加密方法的安全性依赖于密钥的秘密性,而不是算法的秘密性,因此,我们没有必要确保算法的秘密性(事实上,现实中使用的很多单钥密码系统的算法都是公开的),但是我们一定要保证密钥的秘密性。 从单钥密码的这些特点我们容易看出它的主要问题有两点:第一,密钥量问题。在单钥密码系统中,每一对通信者就需要一对密钥,当用户增加时,必然会带来密钥量的成倍增长,因此在网络通信中,大量密钥的产生﹑存放和分配将是一个难以解决的问题。第二,密钥分发问题。单钥密码系统中,加密的安全性完

用java编程实现RSA加密算法

用java编程实现RSA加密算法 RSA加密算法是目前应用最广泛的公钥加密算法,特别适用于通过Internet传送的数据,常用于数字签名和密钥交换。那么我今天就给大家介绍一下如何利用Java编程来实现RSA 加密算法。 一、RSA加密算法描述 RSA加密算法是1978年提出的。经过多年的分析和研究,在众多的公开密钥加密算法中,RSA加密算法最受推崇,它也被推荐为公开密钥数据加密标准。 由数论知识可知,若将一个具有大素数因子的合数进行分解是很困难的,或者说这个问题的计算量是令人望而生畏的,而RSA加密算法正是建立在这个基础上的。 在RSA加密算法中,—个用户A可根据以下步骤来选择密钥和进行密码转换: (1)随机的选取两个不同的大素数p和q(一般为100位以上的十进制数),予以保密;(2)计算n=p*q,作为用户A的模数,予以公开; (3)计算欧拉(Euler)函数z=(p-1)*(q-1),予以保密; (4)随机的选取d与z互质,作为A的公开密钥; (5)利用Euclid算法计算满足同余方程e*d≡1modz的解d,作为用户A的保密密钥;(6)任何向用户A发送信息M的用户,可以用A的公开模数D和公开密钥e根据C=Me mod n得到密文C;

RSA加密算法的安全性是基于大素数分解的困难性。攻击者可以分解已知的n,得到p和q,然后可得到z;最后用Euclid算法,由e和z得到d。然而要分解200位的数,需要大约40亿年。 二、用Java语言描述RSA加密算法的原理 假设我们需要将信息从机器A传到机器B,首先由机器B随机确定一个private_kcy(我们称之为密钥),可将这个private_key始终保存在机器B中而不发出来。然后,由这个private_key计算出public_key(我们称之为公钥)。这个public_key的特性是:几乎不可能通过该public_key计算生成它的priyate_key。接下来通过网络把这个public_key传给机器A,机器A收到public_key后,利用public_key将信息加密,并把加密后的信息通过网络发送到机器B,最后机器B利用已知的pri.rate_key,就可以解开加密信息。 步骤: (1)首先选择两个大素数p和q,计算n=p*q;m=(p-1)(q一1); (2)而后随机选择加密密钥public_key,要求和m互质(比如public_key=m-1);(3)利用Euclid算法计算解密密钥priyate_key,使private_key满足public_key*private_key—1(mod m),其中public_key,n是作为公钥已知,priVate_key 是密钥; (4)加密信息text时,利用公式secretWord=texI^Public_key (mod n)得到密文8ecretword; (5)解密时利用公式word=text^priVate_key(mod n)得到原文word=text。

RSA算法分析与编程实现

实验二 RSA算法 实验目的: 1.深入了解RSA加密算法的加密原理 2.通过编程模拟RSA算法的加密过程 实验内容: 一. RSA概述 ①RSA加密算法是一种最常用的非对称加密算法,CFCA在证书服务中离不了它。在公钥加密标准和电子商业中,RSA被广泛使用。 ②公钥和私钥 1. 随意选择两个大的质数p和q,p不等于q,计算N=pq。 2. 根据欧拉函数,不大于N且与N互质的整数个数为(p-1)(q-1) 3. 选择一个整数e与(p-1)(q-1)互质,并且e小于(p-1)(q-1) 4. 用以下这个公式计算d:d× e≡ 1 (mod (p-1)(q-1)) 5. 将p和q的记录销毁。 (N,e)是公钥,(N,d)是私钥。(N,d)是秘密的。Alice将她的公钥(N,e)传给Bob,而将她的私钥(N,d)藏起来。 二.RSA算法的编程实现 #include #include using namespace std; void main() { int p,q;//定义存放两个质数的变量 cout<<"请输入两个较大的素数:"<>p>>q; cout<<"p="<

int e,i; float d; cin>>e;//输入e值 for(i=1;;i++)//计算d值 { d=(float)(o*i+1)/e; if(d-(int)d==0) break; } cout<<"e="<>m1[j]; if(m1[j]==-1) break; m2[j]=pow(m1[j],e); m4[j]=m2[j]/n; m3[j]=m2[j]-m4[j]*n; } cout<<"密文为:"<

RSA公钥加密算法安全性讨论

RSA公钥加密算法安全性讨论 (RSA algorithm for public-key encryption and the security) 摘要(Abstract):RSA算法是第一个能同时用于加密和数字签名的算法,也易于理解和操作。RSA是被研究得最广泛的公钥算法,从提出到现在已近二十年,经历了各种攻击的考验,逐渐为人们接受,普遍认为是目前最优秀的公钥方案之一。RSA的安全性依赖于大数的因子分解,公钥和私钥都是两个大素数(大于100个十进制位)的函数。但在分布式计算技术和量子计算机理论快速发展的今天,RSA加密安全性受到了挑战。RSA algorithm is the first one can be used for both encryption and digital signature algorithms, but also easy to understand and operate. RSA is the most widely studied public key algorithm, first put forward nearly two decades now, has undergone the test of various attacks, gradually accepted, widely considered the most outstanding public key options. RSA's security depends on a large integer factorization problem, public key and private key are two large prime numbers (greater than 100 decimal digits) of the function. However, in distributed the rapid development of computing technology and the theory of quantum computers today, RSA encryption security has been challenged. 关键字(keywords):RSA,公钥(public key) ,加密(encryption),安全性(security) 1.学习心得: 21世纪是信息时代,信息在社会中的地位和作用越来越重要,已成为社会发展的重要战略资源,信息技术改变着人们的生活和工作方式,信息产业已成为新的经济增长点,社会的信息化已成为当今世界发展的潮流和核心,而信息安全在信息社会中将扮演极为重要的角色,它直接关系到国家安全、企业经营和人们的日常生活。密码技术中的加密方法包括对称密码体制和非对称密码体制。而RSA公钥体制便为非对称密钥体制,也叫做公开密钥体系。 安全的问题是永恒的,现在信息安全领域对密码算法的需求远远大于研究。因为信息交换的数量是很大的,但是我们没有足够的安全手段去保证所有通信的安全,没有一劳永逸的工具供我们使用;同时如果我们想要做一个好的信息安全的产品,必须有密码学与信息安全专家参与,假如有些密码算法的隐患你不知道,那就很难保证你使用的是安全的情形,可能正好是不安全的情形;突破性的发展必须依赖于突破性的理论工作,IT行业不景气,很大程度上不景气的原因,决定于密码学研究的相对滞后,很多需要的密码理论成果没有,比如说现在移动通信网络的安全问题,它需要算法数据量小,还要安全性好,需要加密认证,因为手机和一台电脑是不可比的,不论是存储数量和速度,所以需要研究适合于各种场合使用的密码算法,这就需要大家共同去努力。总之,通信的安全是今后时刻要考虑的问题,是我们大家都要重视的问题,而学习《通信网的安全与保密》这门课程是一次让我们了解这些问题的很好的机会。

RSA公钥密码算法的攻击与防范

RSA算法的攻击与防范 摘要:作为对典型的公钥密码算法,RSA算法在信息安全领域得到了广泛的应用,但是其安全性却一直是学者们议论的话题。本文首先介绍RSA公钥加密算法的工作原理,对RSA 算法的缺陷以及对其所可能遭受的攻击进行分析,最后讨论了针对RSA算法攻击的防范措施。 关键词:公钥密码算法RSA算法缺陷攻击防范 Abstract:As the typical public-key algorithms,RSA algorithms has been widely applied in the field of information security,but its security has been among the scholars.This paper first introduces the theory of the RSA public-key encryption algorithm,and then,analysis the defects of the possible attacking,finally,discusses the attacking preventive measures for RSA algorithms. Keywords:Public-key algorithms;RSA algorithms;Defects;Attacking;Prevention 一、引言 计算机和互联网络的飞速发展使世界范围内信息的传递变得越来越方便,同时,也带来了保障信息安全的新问题。而密码学理论和技术的研究与应用,为保证信道中信息的安全传输奠定了基础。 现代密码体制主要分为私钥密码体制和公钥密码体制,其中私钥体制又称单钥体制或对称密码体制,其加密密钥和解密密钥相同,密钥严格保密;公钥体制又称双钥体制或非对称密码体制,其所用的加、解密钥不同,加密密钥公开,解密密钥不公开,适用于开放的使用环境。1976年Diffie和Hellman发表了《密码学的新方向》一文,首次提出了公开密钥的密码学,即公钥密码学,打破了长期使用单密钥体制的束缚。 目前比较流行的公钥密码算法主要有两种:一类是基于大素数因子分解问题的,其中最典型的代表就是RSA公钥密码算法; 1977年R.L.River,A.Shamir和L.Adleman3人共同提出了RSA算法,并很快成为了一种典型的公钥体制密码算法。另一类是基于离散对数问题的,如ELGamal公钥密码算法和椭圆曲线公钥密码算法等。 二、RSA算法简介 RSA公钥加密算法是1978年由美国麻省理工学院(MIT)的Rivest、Shamirh和Adleman 共同提出的,它是目前最有影响力的公钥加密算法。RSA算法基于一个非常简单的数学难题:将两个大素数相乘十分容易,但想要对其乘积进行因式分解却非常困难,用很简单的形式实现了非常可靠的密码算法。RSA的安全性依赖于大数的因子分解,而大整数因子分解问题是数学上的著名难题,至今没有有效的方法予以解决,因此能够确保RSA算法的安全性。 RSA算法是目前最优秀的公钥方案之一,除加密功能外,公钥系统还用于身份验证(Authentication)或数字签名(Digital Signature),因此它为公用网络上信息的加密和鉴别提供了一种基本的方法。大多数使用公

相关文档