如何使用Java手写实现一个RSA加密算法

8到16位RSA实现

RSA这种算法非常可靠,密钥越长,它就越难破解。

  • 第一步,随机选择两个不相等的质数p和q。
  • 第二步,计算p和q的乘积n。
  • 第三步,计算n的欧拉函数φ(n)。
  • 第四步,随机选择一个整数e,条件是1< e < φ(n),且e与φ(n) 互质。
  • 第五步,计算e对于φ(n)的模反元素d。
  • 第六步,将n和e封装成公钥,n和d封装成私钥。

实现效果

代码

密钥的父类:

public class Key {
    private int n;

    public int getN() {
        return n;
    }

    public void setN(int n) {
        this.n = n;
    }
}

私钥:

public class PrivateKey extends Key {
    private int d;

    public int getD() {
        return d;
    }

    public void setD(int d) {
        this.d = d;
    }

    PrivateKey(int n, int d) {
        setN(n);
        this.d = d;
    }
}

公钥:

public class PublicKey extends Key {
    private int e;

    public int getE() {
        return e;
    }

    public void setE(int e) {
        this.e = e;
    }

    PublicKey(int n, int e) {
        setN(n);
        this.e = e;

    }
}

密钥对:

public class KeyPair {

    private PrivateKey privateKey;
    private PublicKey publicKey;

    public KeyPair(PublicKey publicKey, PrivateKey privateKey) {
        this.publicKey = publicKey;
        this.privateKey = privateKey;
    }

    public PrivateKey getPrivateKey() {
        return privateKey;
    }


    public PublicKey getPublicKey() {
        return publicKey;
    }

}

密钥生成器:

public class KeyGenerator {

    private int keyLength;
    private final int DEFAULT_KEY_LENGTH = 8;

    public KeyGenerator() {
        keyLength = DEFAULT_KEY_LENGTH;
    }

    public KeyGenerator(int keyLength) {
        this.keyLength = keyLength;
    }

    public PublicKey generatePublicKey(int n, int e) {
        return new PublicKey(n, e);
    }

    public PrivateKey generatePrivateKey(int n, int d) {
        return new PrivateKey(n, d);
    }

    public KeyPair generateKeys() {
        int maxN = (1 << keyLength) - 1;
        int minN = 1 << keyLength - 1;

        //p, q两个质数
        int p, q, n;

        //利用二分法,求合适的素数索引最大值
        int pivot;
        int start = 0;
        int end = PrimeTable.primes.length;
        do {
            //防止直接加和平均溢出
            pivot = start + (end - start) >> 1;
            if (PrimeTable.primes[pivot] > maxN) {
                end = pivot - 1;
            } else if (PrimeTable.primes[pivot] < maxN) {
                start = pivot + 1;
            }else {
                break;
            }
        } while (PrimeTable.primes[pivot + 1] > maxN);

        //利用循环,从合适的素数中,挑选两个乘积在maxN和minN之内的数
        do {
            p = PrimeTable.primes[(int) (Math.random() * (pivot - 1))];
            q = PrimeTable.primes[(int) (Math.random() * (pivot - 1))];
            n = p * q;
        } while (n > maxN || n < minN);

        int phiN = (p - 1) * (q - 1);
        int e;

        do {
            e = (int) (1 + Math.random() * (phiN - 1));
        } while (e == 1 || !coprime(e, phiN));

        int y = 0;
        while ((++y * phiN + 1) % e != 0) {}
        int d = (y * phiN + 1) / e;

        PrivateKey prik = generatePrivateKey(n, d);
        PublicKey pubk = generatePublicKey(n, e);
        return new KeyPair(pubk, prik);
    }

    /**
     * 判断两个数是否互质
     * 用大数除以小数,如果除得的余数与其中较小数互质
     * 则原来两个数是互质数。
     * 如:317和52,317÷52=6……5,因余数5与52互质,则317和52是互质数。
     * @param smallNumber 小的数
     * @param largeNumber 大的数
     * @return 如果是质数返回true,否则返回false
     */
    public boolean coprime(int smallNumber, int largeNumber) {
        while (largeNumber % smallNumber > 0) {
            int temp = smallNumber;
            smallNumber = largeNumber % smallNumber;
            largeNumber = temp;
        }
        return smallNumber == 1;
    }
}

RSA的实现:

public class Rsa {

    public static List<Long> encrypt(PublicKey publicKey, String plainText) {
        char[] chars = plainText.toCharArray();
        List<Long> list = new ArrayList<>();
        for (char ch : chars) {
            int e = publicKey.getE();
            int n = publicKey.getN();

            long qw = (int)ch;
            long c = quickMod(qw, e, n);
            //此方法无效,需另辟蹊径,目前解决方案:int换成long
            /*if (c <= 0) {
                //杜绝出现负数
                c = (c + n) % n;
                System.out.println("出现了负数,ch is " + ch + ", e is " + e + ", n is " + n);
            }*/
            list.add(c);
        }
        return list;
    }

    public static String decrypt(PrivateKey privateKey, List<Long> cipher) {
        int d = privateKey.getD();
        int n = privateKey.getN();
        StringBuilder sb = new StringBuilder();
        for (long cipherUnit : cipher) {
            long m = quickMod(cipherUnit, d, n);
            sb.append((char) m);
        }
        return sb.toString();
    }

    /**
     * 快速模运算
     * m^e % n (^是次方的意思)
     * @param m 底数
     * @param e 次方
     * @param n 模
     * @return 余数
     */
    public static long quickMod(long m, long e, long n) {
        long res = 1;
        m = m % n;
        while (e > 0) {
            if (e % 2 == 1) {
                res = (res * m) % n;
            }
            m = (m * m) % n;
            e = e >> 1;
        }
        return res;
    }

}

试运行:

public class Main {

    public static void main(String[] args) {
        KeyGenerator generator = new KeyGenerator(16);
        KeyPair keyPair = generator.generateKeys();
        PublicKey publicKey = keyPair.getPublicKey();
        PrivateKey privateKey = keyPair.getPrivateKey();

        String plainText = "Hello RSA";

        System.out.println("plain text is: " + plainText);

        List<Long> cipher = Rsa.encrypt(publicKey, plainText);

        System.out.println("cipher is: " + cipher);

        String decrypt = Rsa.decrypt(privateKey, cipher);
        System.out.println("decrypt result is: " + decrypt);

    }
}

Junit Test:

public class RsaTest {

    private KeyPair keys = new KeyGenerator(16).generateKeys();
    private LinkedHashSet<String> stringSet = new LinkedHashSet<>();

    @Before
    public void setUp() {
        stringSet.add("Hello");
        stringSet.add("hello");
        stringSet.add("what are you doing");
        stringSet.add("hi!");
        stringSet.add("1234");
        stringSet.add("!@#$%^&*()_+");
        stringSet.add("hey");
        stringSet.add("我是中文");
        stringSet.add("(【pic】`・ω・【pic】)");
    }

    @Test
    public void testDecrypt1() {
        for (String str : stringSet) {
            System.out.println(str);
            assertTrue(str.equals(
                    Rsa.decrypt(keys.getPrivateKey(), Rsa.encrypt(keys.getPublicKey(), str))));
        }
    }

    @Test
    public void testEncrypt1() {
        System.out.println(
                Rsa.encrypt(keys.getPublicKey(), "hello")
        );
    }

    @Test
    public void testQuickMod() {
        assertEquals(1, Rsa.quickMod(2, 4, 3));
        assertEquals(3, Rsa.quickMod(3, 3, 6));
        System.out.println(Rsa.quickMod('A', 28107, 48367));
    }

}

代码下载

点击下载RsaImpl.rar


   转载规则


《如何使用Java手写实现一个RSA加密算法》 Harbor Zeng 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
如何使用python做syn_flood攻击的实验 如何使用python做syn_flood攻击的实验
什么是SYN_FLOOD若正常通过三次握手过程,则连接就建立了,但是恶意攻击者会刻意伪造ip地址,使得受攻击的主机得不到最后一次握手,只能不断的为到来的syn分配内存,发送syn+ack,就这样一直等不到第三次握手的ack确认。 同时开启多个线程运行即可达到攻击效果 结果任务管理器展示CPU使用率 该网段已无法访问 代码from Tools.scripts.treesync import raw_
2018-04-11
下一篇 
如何使用Java优雅的破解维吉尼亚密码 如何使用Java优雅的破解维吉尼亚密码
对包括维吉尼亚密码在内的所有多表密码的破译都是以字母频率为基础的,但直接的频率分析却并不适用。例如,如果P是密文中出现次数最多的字母,则P很有可能对应E(前提是明文的语言为英语)。原因在于E是英语中使用频率最高的字母。然而,由于在维吉尼亚密码中,E可以被加密成不同的密文,因而简单的频率分析在这里并没有用。破译维吉尼亚密码的关键在于它的密钥是循环重复的。如果我们知道了密钥的长度,那密文就可以被看作是
2018-03-17
  目录