RSA解密-第十届Java研究生组E题_rsa解密『更新』章节步骤报告讨论题目描述本题为填空题,只需要算出结果后,-CSDN博客

本文链接：https://blog.csdn.net/qq_43753724/article/details/129903231

文章介绍了RSA加密算法的基本原理，包括如何生成公钥和私钥，以及加密和解密的过程。在给定的编程题中，通过寻找两个质数p和q，利用BigInteger类计算乘法逆元来确定e，然后进行解密操作，最终得出原始明文。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

RSA解密-第十届Java研究生组E题

1、题目描述
2、解题思路
3、完整代码

1、题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

RSA 是一种经典的加密算法。它的基本加密过程如下。

首先生成两个质数 p,q，令 n=p⋅q，设 d 与 (p−1)⋅(q−1) 互质，则可找到 e 使得 $d * e$ 除(p−1)⋅(q−1) 的余数为11。

n,d,e 组成了私钥，n,d 组成了公钥。

当使用公钥加密一个整数 X 时（小于 n），计算 $C=X^dmod\ n$ ，则C是加密后的密文。

当收到密文C 时，可使用私钥解开，计算公式为 $X=C^emod\ n$ 。

例如，当 p=5,q=11,d=3 时，n=55,e=27。

若加密数字 24，得 $24^3mod\ 55=19$ 。解密数字 19，得 $19^{27}mod\ 55=24$ 。

现在你知道公钥中 n*=1001733993063167141,d=212353，同时你截获了别人发送的密文 C=20190324，请问，原文是多少？

运行限制

最大运行时间：1s
最大运行内存: 128M

2、解题思路

牵扯到数论的东西想证明都很难，我们掌握结论即可。

这道题应该把除改为除以才对，由于 $(d*e)\%(p-1)(q-1)=1$ ,则e是d模 $(p - 1) (q - 1)$ 的乘法逆元(前提是d与 $(p - 1) (q - 1) 互质$ )，Java中的BigInteger类型提供了求乘法逆元的API，我们直接调用就行。

我们最终的目的是求出e,然后利用公式 $X=C^emod\ n$ 求解出原文，但是想求出e就得先求出p和q。

由于p和q是两个质数，且d与 $(p - 1) * (q - 1)$ 互质(互质的意思是最大公约数是1)，这里我用暴力遍历出p和q,由于是填空题，n的数字很大，这个遍历求p和q花费了几秒钟的时间。

//p=891234941   q=1123984201
//找p和q   其中d与(p-1)(q-1)互质：也就是最大公约数是1
public static List<Long> findPQ(long n,long d){
    ArrayList<Long> list = new ArrayList<>();
    for (long i = 2L; i <=Math.sqrt(n); i++) {
        if(n%i==0&&gcd(d,(n/i-1)*(i-1))==1&&isPrime(i)&&isPrime(n/i)){
            list.add(i);
            list.add(n/i);
        }
    }
    return list;
}

然后根据p和q的值求e,这个直接调用惩罚逆元的API即可

//由于d.e%(p-1)(q-1)==1,利用逆元求解e的值
BigInteger e = d.modInverse(p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE)));

现在C、e、n都是已知的，我们直接利用公式 $X=C^emod\ n$ 计算出最终结果即可。

  BigInteger res = c.modPow(e, n);

3、完整代码

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {

//        System.out.println(findPQ(1001733993063167141L,212353L));
        BigInteger n = new BigInteger("1001733993063167141");
        BigInteger d = new BigInteger("212353");
        BigInteger c = new BigInteger("20190324");

        BigInteger p = new BigInteger("891234941");
        BigInteger q = new BigInteger("1123984201");
        //由于d.e%(p-1)(q-1)==1,利用逆元求解e的值
        BigInteger e = d.modInverse(p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE)));

        //原文:X=C^e %n
        BigInteger res = c.modPow(e, n);
        System.out.println(res);
    }
    //p=891234941   q=1123984201
    //找p和q   其中d与(p-1)(q-1)互质：也就是最大公约数是1
    public static List<Long> findPQ(long n,long d){
        ArrayList<Long> list = new ArrayList<>();
        for (long i = 2L; i <=Math.sqrt(n); i++) {
            if(n%i==0&&gcd(d,(n/i-1)*(i-1))==1&&isPrime(i)&&isPrime(n/i)){
                list.add(i);
                list.add(n/i);
            }
        }
        return list;
    }
    public static boolean isPrime(long n){
        if(n==0||n==1){
            return false;
        }
        for (int i = 2; i <=Math.sqrt(n) ; i++) {
            if(n%i==0){
                return false;
            }
        }
        return true;
    }
    //求gcd
    public static long gcd(long a,long b){
        if(b==0){
            return a;
        }
        long min = Math.min(a, b);
        long max = Math.max(a, b);
        return gcd(min,max%min);
    }
}