文档章节

RSA算法的基本原理及实现

o
 osc_isezqdgg
发布于 2019/09/18 16:00
字数 770
阅读 26
收藏 0

精选30+云产品,助力企业轻松上云!>>>

1、准备步骤:

1)取 8-bit 的两个素数(质数)p、q

2)n = p * q,计算 n 的欧拉函数 m(表示在小于等于 n 的正整数之中,与 n 构成互质关系的数的个数),当 p 和 q 均为质数时,m = (p - 1) * (q - 1)

3)随机选取一个整数 e,满足条件 1 < e < m 且 e 与 m 互质(但不能选择 m - 1,否则公钥和私钥将相同)

4)找出一个整数 d,使得 e * d mod m = 1,即找出 e 模 m 的逆元(扩展欧几里得算法求逆元,之前的一篇随笔有说明)

5)公钥为(n, e),私钥为(n, d)

 

2、加密过程

对明文的 e 次方后除以 n 求余数,即求:(mingwen)^e mod n

 

3、解密过程

对密文进行 d 次方后除以 n 求余数,即求:(miwen)^d mod n

 

4、加密及解密实现(对学号+姓名加密):

import java.util.ArrayList;

public class Main {
    static ArrayList<Integer> suArr = new ArrayList<>();
    static int[] xy = new int[2];

    public static void main(String[] args) {
        // 由于题目要求取8-bit的两个素数 p,q 因此素数集合的最大值不超过255
        int max = 255, p = 0, q = 0, n, m, e = -1, index = 0;
        char[] myInfo = "1700802067GJQ".toCharArray();
        int[] miwen = new int[myInfo.length];
        char[] mingwen = new char[myInfo.length];
        suArr.add(2);

        for (int i = 3; i <= max; i++) {
            if (isSuShu(i))
                suArr.add(i);
        }

        // 保证取到的两个素数不相等
        while (p == q) {
            p = getRanNum(suArr.size());
            q = getRanNum(suArr.size());
        }

        n = p * q;
        m = (p - 1) * (q - 1);

        // 求得公钥为(n, e)
        for (int i = 2; i < m; i++) {
            if (isHuZhi(m, i) == 1) {
                e = i;
                break;
            }
        }

        if (e != -1) {
            exGcd(e, m);
            /*
            根据要求(e*d)%m=1求得的d(即xy[0])可能为负数,因此当其为负数时要将其转化为正数,转换的原理为:
            a%b=(a%b+b)%b
            当a为负数且b为正数时可使用上述公式将a转换为正数
            */
            if (xy[0] < 0) xy[0] = (xy[0] % m + m) % m;
            System.out.println("p为" + String.valueOf(p) + ",q为" + String.valueOf(q));
            System.out.println("公钥为(" + String.valueOf(n) + ", " + String.valueOf(e) + "),私钥为(" + String.valueOf(n) + ", " + String.valueOf(xy[0]) + ")");

            // 公钥进行加密(mingwen)^e mod n
            for (char c : myInfo) {
                miwen[index++] = myPow((int) c, e, n);
            }
            System.out.print("加密后的密文:");
            for (int c : miwen) {
                System.out.print(c + " ");
            }
            System.out.println();

            index = 0;
            // 私钥进行解密(miwen)^d mod n
            for (int i : miwen) {
                mingwen[index] = (char) myPow(miwen[index], xy[0], n);
                index++;
            }

            System.out.print("解密后的明文:");
            for (char c : mingwen) {
                System.out.print(c);
            }

        }

    }

    // 判断一个数是否为素数
    public static boolean isSuShu(int num) {
        int max = (int) Math.sqrt(num);
        for (int i = 2; i <= max; i++) {
            if (num % i == 0)
                return false;
        }
        return true;
    }

    // 在素数数组中随机取一个数
    public static int getRanNum(int size) {
        return suArr.get((int) (Math.random() * (size)));
    }

    // 判断两个数是否互质
    public static int isHuZhi(int a, int b) {
        return b == 0 ? a : isHuZhi(b, a % b);
    }

    // 扩展欧几里得算法求得私钥(n, xy[0])即(n, d)
    public static void exGcd(int a, int b) {
        if (b == 0) {
            xy[0] = 1;
            xy[1] = 0;
        } else {
            exGcd(b, a % b);
            int x = xy[0];
            xy[0] = xy[1];
            xy[1] = x - (a / b) * xy[1];
        }
    }

    public static int myPow(int a, int b, int m) {
        int res = 1;
        a %= m;
        while (b != 0) {
            if ((b & 1) == 1)
                res = (res * a) % m;
            a = (a * a) % m;
            b >>= 1;
        }
        return res;
    }
}

/*
 * 参考: https://www.jianshu.com/p/fbb8bf7baa97
 * https://www.cnblogs.com/shuaihui520/p/8954788.html
 * https://www.cnblogs.com/linkzijun/p/6151486.html
 */

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
【我的Android进阶之旅】Android采用AES+RSA的加密机制对Http请求进行加密

文章目录 前言 未加密的抓包截图 加密之后的抓包截图 基本需求及概念 AES算法 AES基本原理及算法流程 AES算法流程 RSA算法 RSA算法基本原理及流程 RSA算法实现流程 AES与RSA相结合数据加密方...

欧阳鹏
04/01
0
0
微服务统一登陆认证怎么做?JWT ?

无状态登录原理 1.1.什么是有状态? 有状态服务,即服务端需要记录每次会话的客户端信息,从而识别客户端身份,根据用户身份进行请求的处理,典型的设计如tomcat中的session。 例如登录:用户...

osc_z3m2pney
2018/11/23
9
0
nodejs crypto 加密 对称加密 非对称加密

nodejs 中的 crypto 模块提供了各种各样加密算法的 API。这篇文章记录了常用加密算法的种类、特点、用途和代码实现。其中涉及算法较多,应用面较广,每类算法都有自己适用的场景。为了使行文...

阿豪boy
02/17
0
0
🔥2020你需要知道的Nodejs实战系列:数据加密与crypto模块

nodejs 中的 crypto 模块提供了各种各样加密算法的 API。这篇文章记录了常用加密算法的种类、特点、用途和代码实现。其中涉及算法较多,应用面较广,每类算法都有自己适用的场景。为了使行文...

即将秃头的Java程序员
02/15
40
0
JWT+Interceptor实现无状态登录和鉴权

无状态登录原理 先提一下啥是有状态登录 单台tomcat的情况下:编码的流程如下 前端提交表单里用户的输入的账号密码 后台接受,查数据库, 在数据库中找到用户的信息后,把用户的信息存放到sessi...

osc_6odm1qf4
04/16
5
0

没有更多内容

加载失败,请刷新页面

加载更多

使用命名管道承载gRPC

最近GRPC很火,感觉整RPC不用GRPC都快跟不上时髦了。 gRPC设计 gRPC是一种与语言无关的高性能远程过程调用 (RPC) 框架。刚好需要使用一个的RPC应用系统,自然而然就盯上了它,但是它真能够解...

osc_nq69o22c
33分钟前
16
0
06-敏捷开发框架-apis 脚本库 引用位置无关性设计

动态引入技术的设计,对我们来说非常重要。 同时也说明动态语言的使用对我们来说也是非常重要。 没有动态语言的支撑,有些想法可能不容易实现,或者有替代方案,可能会花更大的代价。 前端开...

osc_5zg9z6t1
35分钟前
21
0
(三)学习了解OrchardCore笔记——灵魂中间件ModularTenantContainerMiddleware的第一行①的模块部分

  了解到了OrchardCore主要由两个中间件(ModularTenantContainerMiddleware和ModularTenantRouterMiddleware)构成,下面开始了解ModularTenantContainerMiddleware中间件第一行代码。   ...

osc_kdarxvx0
36分钟前
15
0
50Mn18Cr4V锻锻环件

电机无磁护环怎么锻性能才能《高高》?50Mn18Cr4V高锰无磁钢在变形温度为900~1 100℃、应变速率为0.1 ~10s-1条件下的热变形行为. 结果,VC第二相的应变诱导析出对50Mn18Cr4V的热变形行为产生...

无磁钢
37分钟前
16
0
【遇见offer】一汽-大众实习生专场来啦!成长+学习+福利,一个也不能少~

在上次一汽-大众的社招直播之后,实习生的专场招聘也终于来啦! 针对2020年暑期,我们提供了非常多的实习岗位给大家选择。 如果你想得到大厂实习的宝贵经验,如果你想得到更快速的成长,如果...

osc_b88oux8w
38分钟前
25
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部