• 程序猿成长之路之密码学篇-RSA非对称分组加密算法介绍

    好久不见各位，最近事情有点多，没来得及更新博客，这两天抽空把RSA算法初步实现了一下，下面和大家分享一下经验。

    什么是非对称加密？

    非对称加密是相对于对称加密而言的，它具有加解密密钥不一致（不重复使用加密的密钥来进行解密）、安全性能高的特点，一般而言非对称加密的算法有RSA, SM2等。而对称加密的算法则主要有DES、3DES、AES、SM1等。

    什么是分组加密

    分组加密是将明文分成按照字节或字符进行分组，从而提高加解密效率的一种处理方式。大家可以查看我之前的博客去了解一下。
    https://blog.csdn.net/qq_31236027/article/details/128003587?spm=1001.2014.3001.5501

    了解RSA算法前需要掌握的内容

    1. 欧拉函数：f(n) = n -1 (n为质数) f(pq) = (p-1)(q-1) (p,q互质）f(p^n) = p^n - p^(n-1)
    2. 欧拉定理: 若 a 与 n互质，则有 a ^ f(n) = 1 mod n 必然成立。（是费马小定理的一种特殊情况）
    3. 欧几里得公式及其扩展公式：gcd(a,b) 和 gcdExtend(a,b)
      这里重点介绍一下扩展公式，它是通过逆递推的方式实现 x *a + y *b = 1 的方程式求解的一种办法。实现原理如下：
      1. 设置几个初始变量，r0,r1,r2: r0 - a与b中的较大者，r1 - a与b中的较小者，r2 - 余数
      2. 设置其余变量，q1 - r0 整除 r1 后的值
      3. 初始化公式：r0 = q1 * r1 + r0 & ri = si*r i-2 + ti * ri-1
      4. 利用数学归纳法有： si = si-2- qi-1*si-1; ti = ti-2 - qi-1*ti-1
      5. 当r2 为0 或 r1 为0的时候 退出循环，返回tn和sn的数组。
    4. Muller素性测试：这个不再赘述，大家可以自己网上查阅资料。

    RSA算法的优缺点

    优点：RSA算法安全性能好
    缺点：执行效率较低，没有对称加密效率高。

    RSA算法的实现原理

    1. 取两个互质的大素数p,q
    2. 求其乘积n，即n =p*q
    3. 利用欧拉函数求f(n) = (p-1)*(q-1)
    4. 在[2,fn-1]中取e，即其中加密参数的值，记得要和fn互质，即获得私钥（n,e)
    5. 利用欧几里得扩展公式求 d，即为公钥，有 e * d = 1 mod fn
    6. 之后利用数学特性有 (明文)^(e)^(d) = (明文）

    RSA算法总体实现代码：

    /**
	 * 测试类
	 * @param args
	 */
	public static void main(String[] args) {
		
		String send = "lalalala";
		StringBuffer sb = new StringBuffer();
		
		BigInteger b1,b2;
		//获取两个大素数
		b1 = RNG.getPrime(300);
		b2 = RNG.getPrime(300);
		for(char ch: send.toString().toCharArray()) {
			int i = (ch - '0' + 48);
			BigInteger s = BigInteger.valueOf(i);
			//求大素数的乘积
			BigInteger n = b1.multiply(b2);
			//求f(n) 欧拉函数 = (b1-1) * (b2-1) => 表示与n互质的数的个数
			BigInteger fn = (b1.subtract(BigInteger.ONE)).multiply((b2.subtract(BigInteger.ONE)));
			BigInteger e = fn.subtract(BigInteger.valueOf(2));
			//从后面出发出错概率会小
			while(e.compareTo(BigInteger.valueOf(2)) > 0) {
				if (EucleidesUtils.gcd(e, fn).compareTo(BigInteger.ONE) == 0) {
					break;
				}
				e = e.subtract(BigInteger.ONE);
			}
//			System.out.println("e = "  + e.toString());
			//求e-1,利用欧几里得扩展公式
//			System.out.println("fn = " + fn.toString());
			BigInteger d = EucleidesUtils.eucleides(e, fn)[0];
//			System.out.println("d = " + d.toString());
			s = s.modPow(e,n);
//			System.out.println("s' = " + s.toString());
			s = s.compareTo(BigInteger.ZERO) == 0 ? BigInteger.ZERO :s.modPow(d, n);
//			System.out.println("s mod = " + s.toString());
			sb.append((char)((s.intValue() - 48) + '0'));
		}
		System.out.println("result = " + sb.toString());
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41

    欧几里得扩展公式

    	/**
	 * 欧几里得扩展公式(numb1 numb2分别是)
	 * @param numb1 numb1
	 * @param numb2 numb2 
	 * @return 
	 */
	public static BigInteger[] eucleides(BigInteger numb1,BigInteger numb2) { 
		BigInteger s0 = BigInteger.ONE,t0 =BigInteger.ZERO,s1 = BigInteger.ZERO
				,t1 = BigInteger.ONE,sn = BigInteger.ZERO,tn = BigInteger.ZERO; //i-轮数
		int i = 0;
		BigInteger r0,r1,r2,q1;
		if (numb1.compareTo(numb2) < 0) {
			r0 = numb2;
			r1 = numb1;
		} else {
			r0 = numb1;
			r1 = numb2;
		}
		do{
			if (r1.compareTo(BigInteger.ZERO) == 0) {
				return new BigInteger[]{tn,sn};
			}
			r2 = r0.remainder(r1); 		//step1. 求numb1与numb2的余数
			q1 = (r0.subtract(r2)).divide(r1);	//step2. 求numb1与numb2的除数
			sn = s0.subtract(q1.multiply(s1));	//step3. 根据数学归纳法 rn = snr0 + tnr1=> sn = sn-2r0 + tn-2r1
			tn = t0.subtract(q1.multiply(t1));	//step4. 根据数学归纳法 rn = snr0 + tnr1=> tn = sn-1r0 + tn-1r
			//获取新的数据
			//第一轮
			if(i == 0) {
				BigInteger temp = sn.multiply(r0).add(tn.multiply(r1)); //gcd(r0,r1) = s*r0 + t*r1;
				r0 = r1;
				r1 = temp;
			} else {
				//后续几轮
				r0 = r1;
				r1 = r2;
				if (r1.compareTo(BigInteger.ZERO) == 0) {
					return new BigInteger[]{tn,sn};
				}
				r2 = r0.remainder(r1); 	
			}	
			//获取新数据
			s0 = s1;
			s1 = sn;
			t0 = t1;
			t1 = tn;
			i++;
		} while(r2.compareTo(BigInteger.ZERO) != 0);
		return new BigInteger[]{tn,sn};
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50

    ------------------------------------------------ 2023.11.15 --------------------------------------------------------------------
    优化了一下，支持任意字符的加解密

    /**
	 * b1,b2
	 */
	public static BigInteger b1= null, b2 = null;
	public static BigInteger fn = null, d = null, n = null, e = null;
	
	static {
		//获取两个大素数
		b1 = RNG.getPrime(300);
		b2 = RNG.getPrime(300);
		
		//求f(n) 欧拉函数 = (b1-1) * (b2-1) => 表示与n互质的数的个数
		fn = (b1.subtract(BigInteger.ONE)).multiply((b2.subtract(BigInteger.ONE)));
		//求大素数的乘积
		n = b1.multiply(b2);
		e = fn.subtract(BigInteger.valueOf(2));
		//从后面出发出错概率会小
		while(e.compareTo(BigInteger.valueOf(2)) > 0) {
			if (EucleidesUtils.gcd(e, fn).compareTo(BigInteger.ONE) == 0) {
				break;
			}
			e = e.subtract(BigInteger.ONE);
		}
		//求e-1,利用欧几里得扩展公式
		d = EucleidesUtils.eucleides(e, fn)[0];
	}
	
	
	/**
	 * 测试类
	 * @param args
	 */
	public static void main(String[] args) {
		
		String send = "{\"code\":200,\"message\":\"成功！\",\"data\":{\"id\":\"2103813902831\",\"name\":\"章鱼哥是我啊\",\"gender\":\"男\"}}";
		RsaUtil rsa = new RsaUtil();
		String encryptedText = rsa.encrypt(send, null, null);
		System.out.println(rsa.decrypt(encryptedText, null, null));
	}

	/**
	 * 加密
	 */
	@Override
	public String encrypt(String text, String iv, EncryptMode mode) {
		StringBuffer encryptedText = new StringBuffer();
		List<String> list = new ArrayList<>();
		for(char ch: text.toString().toCharArray()) {
			int i = (ch - '0' + 48);
			BigInteger s = BigInteger.valueOf(i);
			s = s.modPow(e,n);
			list.add(EncodeUtil.toBinary(s.toString(),EncodeRadix.DEC, true));
			encryptedText.append(
					EncodeUtil.binaryToHexStr(
							EncodeUtil.toBinary(s.toString(),EncodeRadix.DEC, true
					),false)
			).append("-");	
		}
		System.out.println("encryptedText = " + encryptedText.toString());
		return encryptedText.toString();
	}

	/**
	 * 解密
	 */
	@Override
	public String decrypt(String encrytedText, String iv, EncryptMode mode) {
		StringBuffer sb = new StringBuffer();
		String encyptedText = encrytedText.toString();
		for(String str: encyptedText.split("\\-+")) {
			String tmp = EncodeUtil.toBinary(str, EncodeRadix.HEX, true);
			tmp = new BigInteger(tmp).toString();
			BigInteger s = new BigInteger(EncodeUtil.binaryToDec(tmp));
			s = s.compareTo(BigInteger.ZERO) == 0 ? BigInteger.ZERO: s.modPow(d,n);
			sb.append((char)((s.intValue() - 48) + '0'));
		}
		System.out.println("result = " + sb.toString());
		return sb.toString();
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79

    其中，EncodeUtil详见前面的文章介绍。
    https://blog.csdn.net/qq_31236027/article/details/128579451?spm=1001.2014.3001.5501

  • 相关阅读:
    Python Spider学习笔记（一）：爬取B站视频基本信息
    倍福TwinCAT3--基于C++实现ADS通讯
    Selenium常见问题解析
    HTML5+CSS实现图片3D旋转效果，附音乐
    立创EDA导出元件的AD封装报错的解决方法
    设置Json序列化时字段的顺序
    基于java+SpringBoot+HTML+Mysql音乐网站
    2021.09青少年软件编程（Python）等级考试试卷（二级）
    Airflow / MWAA 细节备忘
    Vim基础用法，最常用、最实用的命令介绍（保姆级教程）
  • 原文地址：https://blog.csdn.net/qq_31236027/article/details/134399817