如何不使用外部库在Java中生成公钥私钥对

核心逻辑说明 #

因为仅做概念演示，我们采用小参数简化实现RSA算法，全程仅使用Java基础语法与数学运算，不依赖任何内置密码学库或第三方工具。

分步实现流程 #

• 实现基础工具方法：质数判断、最大公约数计算、扩展欧几里得求模逆元、模幂运算
• 生成两个不相等的小质数p、q（演示用可选择100以内质数，比如p=61、q=53）
• 计算公钥私钥共用模数 n = p * q
• 计算欧拉函数值 φ(n) = (p-1) * (q-1)，该值需保密不对外公开
• 选择公钥指数e：要求e与φ(n)互质，演示场景可直接选固定值3、17等常用公钥指数
• 计算私钥指数d：d为e对φ(n)的模逆元，满足 (e * d) % φ(n) == 1
• 最终生成的密钥对：公钥为(e, n)，私钥为(d, n)

完整可运行Java代码 #

public class SimpleRSAKeyGen {
    // 基础工具：判断是否为质数
    private static boolean isPrime(int num) {
        if (num <= 1) return false;
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) return false;
        }
        return true;
    }

    // 基础工具：计算最大公约数
    private static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    // 基础工具：扩展欧几里得算法求模逆元，返回a对m的逆元，不存在则返回-1
    private static int modInverse(int a, int m) {
        int m0 = m;
        int y = 0, x = 1;
        if (m == 1) return 0;
        while (a > 1) {
            int q = a / m;
            int t = m;
            m = a % m;
            a = t;
            t = y;
            y = x - q * y;
            x = t;
        }
        if (x < 0) x += m0;
        return x;
    }

    // 基础工具：模幂运算，计算 (base^exponent) % mod，避免溢出
    private static int modPow(int base, int exponent, int mod) {
        int result = 1;
        base = base % mod;
        while (exponent > 0) {
            if (exponent % 2 == 1) {
                result = (result * base) % mod;
            }
            exponent = exponent >> 1;
            base = (base * base) % mod;
        }
        return result;
    }

    public static void main(String[] args) {
        // 1. 生成两个小质数p、q，演示用直接取固定值，也可以开启下方随机生成逻辑
        int p = 61, q = 53;
        // 随机生成p、q的逻辑示例：
        // Random random = new Random();
        // int p = 0, q = 0;
        // while (p == q || !isPrime(p) || !isPrime(q)) {
        //     p = random.nextInt(100) + 50;
        //     q = random.nextInt(100) + 50;
        // }

        // 2. 计算n和φ(n)
        int n = p * q;
        int phi = (p - 1) * (q - 1);

        // 3. 选择公钥指数e，和phi互质
        int e = 17;
        while (gcd(e, phi) != 1) {
            e++;
        }

        // 4. 计算私钥指数d
        int d = modInverse(e, phi);

        // 输出密钥对
        System.out.println("公钥（e, n）：(" + e + ", " + n + ")");
        System.out.println("私钥（d, n）：(" + d + ", " + n + ")");

        // 演示加解密验证
        int testMsg = 42; // 待加密的测试消息，必须小于n
        int encrypted = modPow(testMsg, e, n);
        int decrypted = modPow(encrypted, d, n);
        System.out.println("原始消息：" + testMsg);
        System.out.println("加密后：" + encrypted);
        System.out.println("解密后：" + decrypted);
    }
}

注意事项 #

本实现仅用于概念演示，使用小参数、简化运算逻辑，未做任何安全加固，绝对不能用于生产环境或真实敏感数据加密，仅满足作业要求的概念演示场景。

内容的提问来源于stack exchange，提问作者Luk164