[置顶] RSA算法及其java雏形

By | 04月15日
Advertisement

RSA算法数学概念:

素数:素数是一个比1大,其因子只有1和它本身,没有其它数可以整除它的数。素数是无限的。例如,2,3,5,7……等。

两个数互为素数:指的是它们除了1之外没有共同的因子。也可以说这两个数的最大公因子是1。例如,4和9,3和27等。

模运算:如A模N运算,它给出了A的余数,余数是从0到N-1的某个整数,这种运算称为模运算。

RSA加密算法的过程如下:

(1)取两个随机大素数p和q(保密)

(2)计算公开的模数r=pq(公开)

(3)计算秘密的欧拉函数j (r) =(p-1)(q-1)(保密),两个素数p和q不再需要,应该丢弃,不要让任何人知道。

(4)随机选取整数e,满足gcd(e, j (r))=1(公开e,加密密钥)

(5)计算d,满足de≡1(mod j (r))(保密d,解密密钥,陷门信息)

(6)将明文x(其值的范围在0到r-1之间)按模为r自乘e次幂以完成加密操作,从而产生密文y(其值也在0到r-1范围内)y=xe (mod r)

(7)将密文y按模为r自乘d次幂,完成解密操作x=yd (mod r)

下面用一个简单的例子来说明RSA公开密钥密码算法的工作原理。

取两个素数p=11,q=13,p和q的乘积为r=p×q=143,算出秘密的欧拉函数j (r)=(p-1)×(q-1)=120,再选取一个与 j (r)=120互质的数,例如e=7,作为公开密钥,e的选择不要求是素数,但不同的e的抗攻击性能力不一样,为安全起见要求选择为素数。对于这个e 值,可以算出另一个值d=103,d是私有密钥,满足e×d=1 mod j (r),其实7×103=721除以120确实余1。欧几里德算法可以迅速地找出给定的两个整数a和b的最大公因数gcd(a,b),并可判断a与b是否互素,因此该算法可用来寻找解密密钥。

120=7×17+1

1=120-7×17 mod 120=120-7×(-120+17) mod 120==120+7×103 mod 120

(n,e) 这组数公开,(n,d)这组数保密。

设想需要发送信息x=85。利用(n,e)=(143,7)计算出加密值:

y= xe (mod r)=857 mod 143=123

收到密文y=123后,利用 (n,d)=(143,103)计算明文:

x=yd (mod r) =123103mod 143=85

加密信息x(二进制表示)时,首先把x分成等长数据块 x1 ,x2,…, xi ,块长s,其中 2s ≤ n,s尽可能的大。对应的密文是:

yi = xie ( mod r )

解密时作如下计算:

xi = yid ( mod r )

RSA算法中的难点:

(1)大数的运算

(2)素数的产生

(3)高次幂剩余的运算

xe mod r <=> e = bk 2k + bk-1 2k-1 + … + bi 2i + … + b2 22 + b1 2 + b0

那么有如下的计算xe算法:

public static int colum(int y,int n,int key){ int mul; if(key==1) mul=y%n; else mul=y*colum(y,n,key-1)%n; return mul; }

RSA的安全性在理论上存在一个空白,即不能确切知道它的安全性能如何。我们能够做出的结论是:对RSA的攻击的困难程度不比大数分解更难,因为一旦分解出r的因子p、q,就可以攻破RSA密码体制。对RSA的攻击是否等同于大数分解一直未能得到理论上的证明,因为没能证明破解RSA就一定需要作大数分解。

JAVA雏形如下:

public static int colum(int y,int n,int key){ package com.fjl.util.encrypt; import java.math.BigInteger; import java.util.Random; /** * @author 房佳龙 * @date:2011-4-2 下午07:34:57 * */ public class RSAPrototypeTest { public static void main(String[] args){ int bitCount = 20; Random rdm = new Random(); long p = BigInteger.probablePrime(bitCount, rdm).longValue(); long q = BigInteger.probablePrime(bitCount, rdm).longValue(); long r=p*q; long olr = (p-1)*(q-1); long e=BigInteger.probablePrime(bitCount, rdm).longValue(); while(true){ if(gcd(e,olr)==1){ break; } e=BigInteger.probablePrime(bitCount, rdm).longValue(); } System.out.println("p:"+p); System.out.println("q:"+q); System.out.println("r:"+r); System.out.println("欧拉数字:"+olr); System.out.println("公钥:"+e); long n=1; while((n*olr+1)%e!=0){ n++; } long d = (n*olr+1)/e; System.out.println(d); System.out.println("私钥:"+d); if((d*e)%olr==1) System.out.println("私钥正确"); else{ System.out.println("私钥错误"); } long x = 123123123132L; BigInteger bi = BigInteger.valueOf(x); System.out.println(bi); BigInteger bi2 = bi.modPow(BigInteger.valueOf(e), BigInteger.valueOf(r)); System.out.println(bi2); bi=bi2.modPow(BigInteger.valueOf(d), BigInteger.valueOf(r)); System.out.println(bi); } /** * 求最小公约数*辗转相除法*欧几里德算法 */ public static long gcd(long a,long b){ long gcd; if(b==0) gcd=a; else gcd=gcd(b,a%b); return gcd; } }

运行结果如下图:

RSA JAVA雏形算法运行结果

Similar Posts:

  • [置顶] 北理工《Java程序设计》课程教学资源索引(2013版)——第21讲及Android第4讲发布

    北理工<Java程序设计> 课程教学资源索引(2013版,含<Android开发基础>) 说明: "Java程序设计"是北京理工大学计算机学院开设的选修课程,主讲教师是金旭亮. 本教学资源主要包括上课所使用之PPT(己转为PDF格式)和范例源码,以RAR格式打包上传至CSDN下载频道(请点击每讲标题下载). 2013版的课件是我经重新调整并设计的,大大增强了编程技能训练的内容,同时在内容安排上更加注重循序渐进. 这些课件在设计时力图同时支持课堂教学及课后学生自学

  • [置顶] 【算法拾遗(java描述)】--- 插入排序(直接插入排序、希尔排序)

    插入排序基本思想 每次将一个待排序的记录按其关键字大小插入到前面已经拍好序的子文件的适当位置,直到全部记录插入完成为止. 直接插入排序 基本思想 直接插入排序的基本操作是将一个记录插入到已排好序的有序表中,从而得到一个新的有序表.即假设待排序的记录存放在数组R[1······n]中,排序过程中,R被分成两个子区间R[1······i]和R[i+1······n],其中,R[1······i]是已经排好序的有序区:R[i+1······n]是当前未排序的部分.将当前无序区的第一个记录R[i+1]插

  • [置顶] 斗地主算法之发牌,洗牌

    斗地主游戏的基本算法实现 by -wojiushi3344 QQ:513670524 棋牌游戏交流群:246671414 转载请说明出处 源代码下载 PS:首先祝朋友们5,1节快乐!!闲来无事,今天来写一下斗地主游戏的基本实现,写得不好,大家别喷哈!!具体实现还得参见源代码.朋友们如果你有更好的建议可以到我博客留言讨论.谢谢! 博客地址:http://blog.csdn.net/wojiushi3344 发牌动画: 原理:没隔一段时间更新定时器,然后再更新图片到不同的位置实现地主发牌的动画. 具

  • [置顶] Viterbi算法信号处理Demo

    问题描述 问题要求 信道H长度L=3,H = (h0,h1,h2),其中h0=,h1=,h2=; 基本信号类型 x =10或-10,一个完整的信号序列为X = (x0,x1,x2,...,x9);噪声W = (w0,w1,w2,...,w11)是满足高斯分布的(0,1)范围内的随机数:按照 Y = H·X + W公式转换得到一个完整的信号序列Y = (y0,y1,y2,...,y11).信号接收端需要在已知Y,H的情况下通过Viterbi算法得到满足 min (W)即 min(Y - H·X)的

  • [置顶] 一个实际项目Java架构设计之总体设计

    1 总体架构模块图 1.1 抽象架构模块图 1.2 具体技术架构模块图 如上图示所,框架主要包括了: l MVC开发框架 l 工作流技术 l 用户.权限.角色管理 下面分别详细介绍. 2 MVC方案 2.1 视图层技术方案(view) 在常用开发框架的应用中,常用于视图层的有:Jsp ,Jsf,Freemarker,Xslt, Velocity等.JSP:常用的一种视图层,无法实现严格的MVC分离,JSP代码几乎等同于JAVA代码.表现逻辑与代码相混杂,代码重用性,系统维护性比较低.下面分别介绍

  • [置顶] prim算法改进,C语言,用堆排序找到最小边开始,可读取文件

    1.不从节点1开始找,从图中最小的边开始找.其中求最小边用堆排序的算法 2.其余与yyprim类似: 3.将下面数据保存到1.txt 6 10 1 2 10 1 4 30 1 5 45 2 3 50 2 5 50 2 6 25 3 5 35 3 6 15 4 6 20 5 6 55 #include <stdio.h> #define INFINITY 0x7fffffff #define MAX 100//最大顶点数 typedef int KeyType; typedef char Inf

  • [置顶] 【算法导论学习-24】二叉树专题2:二叉搜索树(Binary Search Tree,BST)

    一. 二叉搜索树(Binary SearchTree,BST) 对应<算法导论>第12章.相比一般二叉树,BST满足唯一的条件:任意节点的key>左孩子的key,同时<右孩子的key. 1. 节点类: public class BinarySearchTreesNode<T> { private int key; private T satelliteData; private BinarySearchTreesNode<T> parent, leftChi

  • [置顶] 【算法导论-010】快速排序(quickSort)

    1.算法思想 <算法导论>170页第7章QuickSort,不再赘述. 2.java实现 参考:<算法导论>171页伪码,注意,这里的partition(int[] array, int start, int end)函数不是原始版本 public class QuickSortTest { /** * @param args */ public static void main(String[] args) { // TODO 自动生成的方法存根 int[] array = {

  • [置顶] 黑马程序员 Java 内部类

    ----------------------ASP.Net+Android+IOS开发..Net培训.期待与您交流! ---------------------- Java 内部类学习笔记 内部类:将一个类定义在一个类的里面,对里面那个类就称为内部类(内置类.嵌套类). /* 内部类的访问规则: 1,内部类可以直接访问外部类中的成员,包括私有. 之所以可以直接访问外部类中的成员,是因为内部类中持有了一个外部类的引用,格式 外部类名.this(Outer.this.x) 2,外部类要访问内部类,必

  • [置顶] android studio、java安装及环境变量配置

    电脑重装了,顺便记录一下安装的过程,以备后续查用 1. 安装java 下载java安装包,安装完后记得配置环境变量: 在"系统变量"新建一个变量名为JAVA_HOME的变量,变量值为你本地java的安装目录,我这里为:C:\Program Files\Java\jdk1.7.0_80,设置这个的目的是作为下面两个环境变量的一个引用 在"系统变量"选项区域中查看PATH变量,如果不存在,则新建变量PATH,否则选中该变量,单击"编辑"按钮,在&qu

Tags: