本文介绍 RSA 加解密中必须考虑到的密钥长度、明文长度和密文长度问题,对第一次接触 RSA 的开发人员来说,RSA 算是比较复杂的算法,天缘以后还会补充几篇 RSA 基础知识专题文章,用最简单最通俗的语言描述 RSA,让各位了解 RSA 算法本身其实也很简单,RSA 的复杂度是因为数学家把效率和安全也考虑进去的缘故。
本文先只谈密钥长度、明文长度和密文长度的概念知识,RSA 的理论及示例等以后再谈。提到密钥,我们不得不提到 RSA 的三个重要大数:公钥指数 e、私钥指数 d 和模值 n。这三个大数是我们使用 RSA 时需要直接接触的,理解了本文的基础概念,即使未接触过 RSA 的开发人员也能应对自如的使用 RSA 相关函数库,无需深入了解 e、d、n 是如何生成的,只需要知道我该如何用、要注意什么。
首先我们说的 "密钥" 是指谁?由于 RSA 密钥是(公钥 + 模值)、(私钥 + 模值)分组分发的,单独给对方一个公钥或私钥是没有任何用处,所以我们说的 "密钥" 其实是它们两者中的其中一组。但我们说的 "密钥长度" 一般只是指模值的位长度。目前主流可选值:1024、2048、3072、4096...
目前主流密钥长度至少都是 1024bits 以上,低于 1024bit 的密钥已经不建议使用(安全问题)。那么上限在哪里?没有上限,多大都可以使用。所以,主流的模值是 1024 位,实际运算结果可能会略小于 1024bits,注意,这个值不是绝对的,跟素数的生成算法有关系,只是告诉素数生成器 "帮我生成一个接近 1024 位的素数而已",然后生成器 "好,给您一个,这个差不多 1024 位"。
素数生成器这么厉害?说生成 1024 位就会出个 1024 位的大整数?真实的情况是素数生成器也只是在 1024bits 对应的整数附近进行 "摸索" 而已,大家其实都不容易,又要快又要准确又要随机性,那么素数生成器也只能应付一下,找到 1024 位的算是好运,没找到 1024 位,1023 位也照样送出来:)。
公钥指数是随意选的,但目前行业上公钥指数普遍选的都是 65537(0x10001,5bits),该值是除了 1、3、5、17、257 之外的最小素数,为什么不选的大一点?当然可以,只是考虑到既要满足相对安全、又想运算的快一点(加密时),PKCS#1 的一个建议值而已。
有意的把公钥指数选的小一点,但是对应私钥指数肯定很大,意图也很明确,大家都要用公钥加密,所以大家时间很宝贵,需要快一点,您一个人私钥解密,时间长一点就多担待,少数服从多数的典型应用。
公钥指数随意选,那么私钥就不能再随意选了,只能根据算法公式(ed%k=1,k=(p-1)(q-1))进行运算出来。那么私钥指数会是多少位?根据 ed 关系,私钥 d=(x*k+1)/e,所以单看这个公式,私钥指数似乎也不是唯一结果,可能大于也可能小于 1024bits 的,但我们习惯上也是指某个小于 1024bits 的大整数。
包括前文的公钥指数,在实际运算和存储时为方便一般都是按照标准位长进行使用,前面不足部分补 0 填充,所以,使用保存和转换这些密钥需要注意统一缓冲区的长度。
网上有说明文长度小于等于密钥长度(Bytes)-11,这说法本身不太准确,会给人感觉 RSA 1024 只能加密 117 字节长度明文。实际上,RSA 算法本身要求加密内容也就是明文长度 m 必须 0
所以,RSA 实际可加密的明文长度最大也是 1024bits,但问题就来了:
如果小于这个长度怎么办?就需要进行 padding,因为如果没有 padding,用户无法确分解密后内容的真实长度,字符串之类的内容问题还不大,以 0 作为结束符,但对二进制数据就很难理解,因为不确定后面的 0 是内容还是内容结束符。
只要用到 padding,那么就要占用实际的明文长度,于是才有 117 字节的说法。我们一般使用的 padding 标准有 NoPPadding、OAEPPadding、PKCS1Padding 等,其中 PKCS#1 建议的 padding 就占用了 11 个字节。
如果大于这个长度怎么办?很多算法的 padding 往往是在后边的,但 PKCS 的 padding 则是在前面的,此为有意设计,有意的把第一个字节置 0 以确保 m 的值小于 n。
这样,128 字节(1024bits)- 减去 11 字节正好是 117 字节,但对于 RSA 加密来讲,padding 也是参与加密的,所以,依然按照 1024bits 去理解,但实际的明文只有 117 字节了。
关于 PKCS#1 padding 规范可参考:RFC2313 chapter 8.1,我们在把明文送给 RSA 加密器前,要确认这个值是不是大于 n,也就是如果接近 n 位长,那么需要先 padding 再分段加密。除非我们是 "定长定量自己可控可理解" 的加密不需要 padding。
密文长度就是给定符合条件的明文加密出来的结果位长,这个可以确定,加密后的密文位长跟密钥的位长度是相同的,因为加密公式:
C=(P^e)%n
所以,C 最大值就是 n-1,所以不可能超过 n 的位数。尽管可能小于 n 的位数,但从传输和存储角度,仍然是按照标准位长来进行的,所以,即使我们加密一字节的明文,运算出来的结果也要按照标准位长来使用(当然了,除非我们能再采取措施区分真实的位长,一般不在考虑)。
至于明文分片多次加密,自然密文长度成倍增长,但已不属于一次加密的问题,不能放到一起考虑。
来源: http://www.taocms.org/1128.html