公钥是否可以具有与私钥不同的长度(加密)？

Question

我有一个1024位的私钥,并用它来生成一个公钥.这是否自动意味着我的公钥也有1024加密？或者它的加密大小可以更小？(512,256 ......)

PS:我最感兴趣的是RSA密钥中模数("n")的大小.大小通常为1024或2048位.但我很高兴看到这引发了一场讨论,所有这些都促进了我对密码学的兴趣.

Answer 1

这取决于加密算法以及您调用公钥/私钥的精确程度.与磁盘或网络上的序列化相比,有时可以在RAM中使用不同的大小.

RSA

RSA公钥由模数n和公共指数组成e.我们通常选择一个较小的值e(3或65537是常见的).大小e对安全性影响不大.由于e通常小于四个字节且n超过一百个,因此总大小由模数控制.如果你真的想,你可以修复e作为协议规范的一部分,因此只能n存储.

RSA私钥可以以不同的形式来表示,但通常我们存储的值p,q,dp,dq,e,d,n,InvQ.它们的组合大小比公钥大.其中大多数并非严格要求,但可以方便地使用它们而不是重新生成它们.重新生成所有这些e,p并且q是直截了当的.

当我们在RSA的上下文中谈论密钥大小时,我们总是指模数的大小,忽略所有其他元素.这是一个有用的约定,因为这是影响安全性的唯一值.典型大小为n2048位.

有限域加密(Diffie-Hellman,DSA等)

私钥的标量是安全级别的两倍.典型值为256位.

公钥是一个组元素,它比私钥大得多.典型值为2048位.

因此,对于有限字段加密,公钥比私钥大得多.

椭圆曲线

私钥的标量是安全级别的两倍.典型值为256位.这部分与有限域加密相同.

公钥是一个组元素.序列化这种元素有两种形式.压缩形式略大于私钥(最多几位).未压缩的形式大约是私钥大小的两倍.对于未压缩形式,压缩形式的典型值是256位和512位.

私钥作为种子

当您自己生成公钥/私钥对时,您始终可以将它们存储为PRNG的种子.这样,无论你使用哪种方案,它们都非常小,160位左右.这样做的缺点是重新生成私钥的自然形式可能是昂贵的.要求创建密钥对的方法保持不变.

公钥的指纹

您可以经常只存储160位左右的指纹,而不是存储完整的公钥.这样做的缺点是它增加了消息/签名的大小.

摘要

对于某些算法,公钥和私钥的大小是相同的,对于一些它们不同,并且通常可以以成本(解压缩时间或消息大小)压缩它们中的一个或两个.

Answer 2

不是.密钥对中的公钥始终与私钥大小匹配,实际上它是从私钥派生的.

However, with some public key cryptographic implementations, such as OpenPGP, keys are created with subkeys assigned to different tasks. Those subkeys can be different sizes to each other and the master key used to create them. In those cases the public key data will indicate the key sizes for the master key and the subkey(s) which will match the corresponding private key data.

Whereas many other public key implementations do not utilise subkeys (e.g. TLS) so you will only ever see the single key size. Again that key size will be indicated in both the public and private key data.

The only variation in key sizes you will see is when asymmetric encryption is used in conjunction with symmetric encryption. The symmetric encryption (session key) will be smaller, but it uses entirely different algorithms (e.g. AES, TWOFISH, etc.) and is not part of the public key (except in OpenPGP, where symmetric cipher preferences can be saved because it does not utilise a live connection to establish the symmetrically encrypted communication and exchange session key data).

EDIT: More detail on the relationship between the public and private key data (also known as proving David wrong)

Pointing to RSA is all very well and good, but it depends on the key exchange protocol and for that we go to Diffie-Hellman key exchange and the original patent, which is now expired. Both of these have examples and explanations of the key exchange methods and the relationship between the public and private keys.

实现这种关系的算法,包括RSA和El-Gamal,都同时创建公钥和私钥.具体来说,通过创建一个私钥然后生成公钥.公钥继承了制作它的私钥的所有功能.在两个组件之间获得错误匹配细节的唯一方法是以某种方式生成独立于私钥的公钥.当然,那里的问题是他们不再是一对钥匙.

The key generation descriptions for both RSA and El-Gamal explain the common data between the public and private keys and specifically that all the components of the public key are a part of the private key, but the private key contains additional data necessary to decrypt data and/or sign data. In El-Gamal the public components are G, q, g and h while the private components are G, q, g, h and x.

Now, on to the lack of mention of the bit size of the key pairs in the algorithms, yes, that's true, but every practical implementation of them incorporates the selected key size as one of the constants when generating the private key. Here's the relevant code (after all the options are selected, including selecting the key size and specifying the passphrase) for generating keys in GnuPG:

static int
do_create( int algo, unsigned int nbits, KBNODE pub_root, KBNODE sec_root,
           DEK *dek, STRING2KEY *s2k, PKT_secret_key **sk, u32 timestamp,
       u32 expiredate, int is_subkey )
{
  int rc=0;

  if( !opt.batch )
    tty_printf(_(
"We need to generate a lot of random bytes. It is a good idea to perform\n"
"some other action (type on the keyboard, move the mouse, utilize the\n"
"disks) during the prime generation; this gives the random number\n"
"generator a better chance to gain enough entropy.\n") );

  if( algo == PUBKEY_ALGO_ELGAMAL_E )
    rc = gen_elg(algo, nbits, pub_root, sec_root, dek, s2k, sk, timestamp,
         expiredate, is_subkey);
  else if( algo == PUBKEY_ALGO_DSA )
    rc = gen_dsa(nbits, pub_root, sec_root, dek, s2k, sk, timestamp,
         expiredate, is_subkey);
  else if( algo == PUBKEY_ALGO_RSA )
    rc = gen_rsa(algo, nbits, pub_root, sec_root, dek, s2k, sk, timestamp,
         expiredate, is_subkey);
  else
    BUG();

  return rc;
}

The slight differences between the three algorithms relate to the values for the items referred to in the published algorithms, yet in each case the "nbits" is a constant.

You'll find the same consistency relating to the key size in the code for generating keys in OpenSSL, OpenSSH and any other system utilising public key cryptography. In every implementation in order to have a matched public and private key pair the public key must be derived from the private key. Since the private key is generated with the key size as a constant, that key size must be inherited by the public key. If the public key does not contain all the correct shared information with the private key then it will be, by definition, not matched to that key and thus the encryption/decryption processes and the signing/verifying processes will fail.