RSA 随记

刺骨的言语ヽ痛彻心扉 2022-01-20 05:21 436阅读 0赞

先前弄SSL接触了RSA算法，有点好奇其中的实现，毕竟之前的Cipher类到计算那部分就看不懂只能放弃了。所以今天补课了一下RSA的算法。

### 简介 ###

RSA加密算法是一种非对称加密算法。在公开密钥加密和电子商业中RSA被广泛使用。RSA是1977年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。

对极大整数做因数分解的难度决定了RSA算法的可靠性。

> 也就是说RSA算法的数学基础涉及到了因数分解。

### 相关计算 ###

RSA算法由公钥(PublicKey)和私钥(PrivateKey)组成。

而密钥主要由四个因子构成：N、L、E、D；而这四个因子的计算由两个基础的质数q和p组成。

这四个因子的计算方式分别是：

*  N : q \* p
 *  L : (q - 1)和(p - 1)的最小公倍数
 *  E : E和L的最大公约数为1(1 < E < L)。
 *  D : D \* E mod L = 1。即D和E的乘积除以L的余数为1。

然后是加密和解密的过程：

*  加密：密文 = 明文^E mod N。(RSA加密是对明文的E次方后除以N后求余数的过程。)
 *  解密：明文 = 密文^D mod N。(RSA加密是对明文的D次方后除以N后求余数的过程。)

### 验证 ###

知道了计算方法，那么就开始写个最简单的Demo来验证。

//p = 3, q = 11
        private void rsa(int p, int q, String d) {
            int N = p * q;
            int L = IntStream
                .iterate(Math.max(p - 1, q - 1), i -> i + 1)
                .filter(i -> i % (p - 1) == 0 && i % (q - 1) == 0)
                .findFirst()
                .getAsInt();
            int E = IntStream
                .iterate(1, i -> i + 1)
                .filter(i -> L % i != 0)
                .findFirst()
                .getAsInt();
            int D = IntStream
                .iterate(1, i -> i + 1)
                .filter(i -> (E * i) % L == 1 && i < L)
                .findFirst()
                .getAsInt();
    
            // System.out.println("N:" + N + ";L:" + L + ";E:" + E + ";D:" + D);
    
            IntFunction<Byte> encode = (int data) -> Byte.valueOf(String.valueOf((int) (Math.pow((double) data, (double) E) % N)));
            IntFunction<Byte> decode = (int data) -> Byte.valueOf(String.valueOf((int) (Math.pow((double) data, (double) D) % N)));
    
            byte[] bytes = d.getBytes();
            byte[] encodeBytes = new byte[bytes.length];
            byte[] decodeBytes = new byte[bytes.length];
            for (int i = 0; i < bytes.length; i++) {
                encodeBytes[i] = encode.apply(bytes[i]);
            }
    
            for (int i = 0; i < bytes.length; i++) {
                decodeBytes[i] = decode.apply(encodeBytes[i]);
            }
    
            System.out.println(Arrays.toString(bytes));
            System.out.println(Arrays.toString(encodeBytes));
            System.out.println(Arrays.toString(decodeBytes));
        }
    复制代码

程序写好就开始测试了，其中我的p=3，q=11。

但是这里却出现了问题，当我传入字符串"key"的时候计算的结果如下：

但是我Demo就是根据原理来的，那是哪里出问题了呢？

可以发现，加密并解密出来的数字都没有超过33，然后将数据直接修改成\{32, 33, 34\}可以发现当明文数字小于33的时候运算结果正确。那就可以得出结论N(Number)决定了RSA能加密的最大数字。

其实细心点研究公式就可以早早发现这个问题：公式中最后的计算结果需要mod N，那么最终的结果自然是小于N了。

也就是说取的q和p的大小直接决定了加密的明文的大小范围。所以网上许多资料都是直接说这两个取值最好往大了取。

当然，当值取的过大的时候就会增加计算的时间开销，目前PKCS\#1给的建议是E=65537,该值是除了1、3、5、17、257之外的最小素数。

### 补充 ###

当前提及RSA密钥的长度的时候都是指的它的模值的位长度。目前主流的由1024、2048、3072、4096等。低于1024的由于安全问题已不建议使用。

那么我这个Demo中的模值为33，位长度为6bits，最大加密1Byte不到2Byte，小的可怜。

那么如果加密的时候位数不到怎么办，就需要进行padding，因为如果没有padding，用户无法确分解密后内容的真实长度，字符串之类的内容问题还不大，以0作为结束符，但对二进制数据就很难理解，因为不确定后面的0是内容还是内容结束符。其中PKCS\#1建议的padding就占用了11个字节。因此在使用RSA1024的时候加密数据只有117字节。这是为了防止加密的数据为二进制的时候无法区分位的结尾。

其实我这个Demo是有很多错误的。由于直接从byte转化所以位数最大位8bits，否则就会出错。

欢迎捉虫