有几种方法可以使用短密钥长度:
1. 通过RSA
一个RSA公钥由一个大数“模数”n和(通常很小的)数字e(公共指数)组成。e可以很小,例如3,并且在一个封闭的设置中,您可以强制使用传统的e,每个人都是相同的。 n的典型大小为1024位(即128字节)。
n是两个质数p和q的乘积(n = p*q)。知道p和q足以重建私钥(名义上是一个值d,它是模p-1和q-1下的e的乘法逆元)。假设已知n,则仅知道p就足够了(如果您知道n和p,则可以执行简单的除法计算q)。对于适当的安全性,p和q应具有相似的大小,因此即使取其中较小的那个,您仍然需要存储大约512位左右 - 即64字节。
还建议选择一个小的d(“私有指数”)。但这使得e基本上是随机的,因此很大;您无法再使用常规的小值e。这基本上会使公钥大小加倍。此外,强制使用小的d可能会使密钥变弱(当d的大小不超过n的29%时已经被证明是这种情况,但这并不以任何方式证明30%n的d是安全的)。这通常被认为是一个坏主意。
2. 通过DSA / Diffie-Hellman
DSA是一种数字签名算法。Diffie-Hellman是一种密钥交换算法。两者均为“非对称加密算法”,您可以根据需要使用其中之一或两者。在这两种情况下,都有一个公共数学群(基本DSA和DH的大质数模数;椭圆曲线变体使用椭圆曲线作为群);公钥是一个群元素,私钥是相对于传统生成器的离散对数。换句话说,给定一个质数p和一个模p的数字g(它们可以由所有密钥持有者共享);私钥是与公钥y = g ^ x mod p对应的数字x。私钥是模小质数q选择的。q已知且必须足够大以击败通用离散对数算法;在实践中,我们希望q为160位或更多。
这意味着私钥大约占用20个字节。这不是20个十进制数字,而是更接近的值。
使用
任何密码算法
当您生成密钥对时,需要进行以下操作:
1.确定性过程;
2.随机比特源。
例如,对于RSA,您通过创建正确大小的奇数随机数并循环直到找到质数来生成p和q。对于给定的随机源,整个过程是确定性的:给定相同的随机比特,这将找到相同的质数p和q。
因此,您可以开发一个由秘密密钥K种子生成的伪随机数生成器,并将其用作密钥生成过程的随机源。每当您需要私钥时,都要再次运行密钥生成过程,使用K作为输入。然后就完成了!您需要存储的私钥现在是K。
对于RSA来说,这使得私钥使用非常昂贵(RSA密钥生成不容易)。但是,对于DSA / Diffie-Hellman,这将非常便宜:私钥仅是模q(群顺序)的随机数,可以以比使用数字签名或非对称密钥交换的私钥更小的成本生成。
这导致以下过程:
- “私钥”存储在K中。
- DSA / Diffie-Hellman的组参数在应用程序中是硬编码的;每个人都使用相同的组,这并不是一个问题。组的阶是q,至少为160位的已知质数。如果您使用椭圆曲线变体,则q是曲线的属性,因此是给定的。
- 当您需要签名或执行密钥交换(密钥交换用于模拟非对称加密)时,您计算SHA-512(K),得到一个512位序列。您取前半部分(256位),将其解释为数字(使用大端或小端约定,只要您始终使用相同的约定即可),并对q进行模归约以获得私有DSA密钥。类似地,您使用SHA-512输出的后半部分来获取私有DH密钥。
密钥生成略带偏差,但这并不意味着安全性受到很大影响。请注意,如果您需要DSA密钥和DH密钥,则可以使用相同的组,但不应使用相同的私钥(因此使用SHA-512输出的两个部分)。
K应该有多大?对于诸如SHA-512的哈希函数,K可以是任意序列的位数。但是,K应足够宽以抵御穷举搜索。1024位RSA密钥或1024位DSA模数(DSA的p模数)提供了大致等同于80位对称密钥的安全级别。同样,DSA / DH的160位组阶提供相同的级别。80位并不多;如果您想要被认真对待,就不能低于这个水平。这意味着K应该从至少280个可能的密钥中选择;换句话说,如果K被选为均匀随机字节,则其长度必须至少为10个字节。使用十进制数字,需要至少24个数字。低于此的任何内容都是固有的弱点,这是不可避免的。
标准警告:如果以上任何内容对您来说不明显或不清晰,请不要考虑实现它。加密算法的实现很棘手,特别是因为最致命的错误无法测试(程序运行并似乎正常工作并不意味着它不包含安全漏洞)。