Can a public key have a different length (encryption) than a private key?

Question

I have a private key of 1024 bits and use it to create a public key. Does this automatically mean that my public key also has 1024 encryption? Or could it be a smaller encryption? (512, 256 ...)

PS: I am most interested in and say that this is the size of the module ("n") in RSA keys. The size is usually 1024 or 2048 bits. But I am glad to see that this caused a discussion, and all this fuels my interest in cryptography.

Answer 1

No. The public key in the key pair always corresponds to the size of the private key, in fact, it is obtained from the private key.

However, with some public key cryptographic implementations, such as OpenPGP , keys are created with subsections assigned to different tasks. These subsections can be of different sizes for each other and the master key used to create them. In these cases, the public key data will indicate the key sizes for the master key and subkey (s) that will correspond to the corresponding private key data.

While many other public key implementations do not use subkeys (for example, TLS ), so you will see only one key size. Again, the key size will be indicated in both public and private keys.

The only key size change you'll see is when asymmetric encryption is used in combination with symmetric encryption. Symmetric encryption (session key) will be less, but it uses completely different algorithms (for example, AES, TWOFISH, etc.) and is not part of the public key (except for OpenPGP, where symmetric encryption settings can be saved because it is not to be used live connection for establishing symmetrically encrypted data exchange and exchange of session data).

EDIT: more information on the relationship between public and private key data (also known as David's false evidence)

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

Algorithms that implement this relationship, including RSA and El-Gamal , all simultaneously create both public and private keys. In particular, by creating a private key, which then generates a public key. The public key inherits all the functions of the private key that created it. A method only for receiving incorrectly matched data between two components will somehow generate a public key regardless of the private key. The problem there, of course, is that they will no longer be a key pair.

The key generation description for RSA and El-Gamal explains the common data between the public and private keys and, in particular, that all components of the public key are part of the private key, but the private key contains additional data necessary to decrypt the data and / or sign the data. In El-Gamal, the publicly available components are G, q, g, and h, and the private components are G, q, g, h, and x.

Now, due to the lack of mention of the bit size of key pairs in the algorithms, yes, this is true, but each practical implementation of them includes the selected key size as one of the constants when generating the private key. Here is the appropriate code (after selecting all options, including choosing a key size and determining a 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 elements mentioned in the published algorithms, but in each case, "nbits" is a constant.

You will find the same consistency associated with the key size in the code for generating keys in OpenSSL, OpenSSH and any other system that uses public key cryptography. In each implementation, in order to have a consistent pair of public and private keys, the public key must be obtained from the private key. Since the private key is generated with the key size as a constant, this key size must be inherited by the public key. If the public key does not contain all the correct general information with the private key, then by definition it will not correspond to this key and, therefore, the encryption / decryption processes and the signature / verification processes will not work.

Answer 2

It depends on the encryption algorithm and what exactly you call the public / private key. Sometimes in RAM you can use different sizes compared to serialization on disk or on the network.

RSA

The RSA public key consists of module n and public exponent e . Usually we choose a small value for e (3, or 65537). Size e little effect on safety. Since e usually less than four bytes and n more than one hundred, the module prevails in the total size. If you really want to, you can fix e as part of the protocol specification to only store n .

The RSA private key can be presented in different forms, but usually we store the values p , q , dp , dq , e , d , n , InvQ . Their total size is larger than the public key. Most of them are not strictly required, but it is convenient to use them instead of their regeneration. The regeneration of all given e , p and q is direct.

When we talk about key size in the context of RSA, we always mean the size of the module, ignoring all other elements. This is a useful convention as it is the only value that affects security. The typical size for n is 2048 bits.

End Field Curve (Diffie-Hellman, DSA, etc.)

A private key is a scalar that doubles the level of security. The typical value is 256 bits.

A public key is an element of a group that is much larger than a private key. A typical value is 2048 bits.

Thus, in final field cryptography, the public key is much larger than the private key.

Elliptical curves

A private key is a scalar that doubles the level of security. The typical value is 256 bits. This part is identical to the field field curve.

The public key is a member of the group. There are two forms of serializing such an element. The compressed form is slightly larger than the private key (no more than a few bits). The uncompressed form is about twice the size of the private key. A typical value for a compressed form is 256 bits and 512 bits for an uncompressed form.

Private key as a seed

When you create public / private key pairs yourself, you can always store them as seeds for PRNG. So they are pretty small, 160 bits or so, regardless of the circuit you use. The disadvantage of this is that restoring the natural form of the private key can be expensive. The key pair creation method is required to remain constant.

Public key fingerprint

Instead of storing a full public key, you can often only store a fingerprint of 160 bits or so. The disadvantage of this is that it increases the size of the message / signature.

Summary

For some algorithms, the size of the public and private keys is the same, for some it is different, and you can often compress them or both of them at a cost (decompression time or message size).

Answer 3

I looked from different sources, and my conclusion is that the module (n = p * q) used to generate RSA keys is the same for public and private keys. The module determines the key length for both.

Answer 4

From what I understand, there is no requirement that both keys be the same size. The following describes how to generate keys:
http://en.wikipedia.org/wiki/RSA_algorithm#Key_generation

However, I believe that if one key (or module coefficient) is much smaller, it will weaken the strength of cryptanalysis.

Edit:

This discussion has largely become irrelevant, since the OP explained that they are most interested in the size of the module, which, of course, will be the same for encryption and decryption (except for any strange unknown cryptosystems).

To clarify my point, I just say that if e <d (or d <<e) you can distribute keys as different sizes of keys. They will be generated by the same algorithm, using the same bit math (for example, 256 bits), and the same number of bits for encryption and decryption. If you look (for the sake of argument) the numbers 1 and 128, you have a choice in how to represent them. Both of them can be 8 bits, or 1 can be represented by any number of bits from 1 to 7 bits. This can be considered a cheap trick if your key generation method does not guarantee that the values ​​of d and e will differ significantly in a predictable way. However, as indicated, I do not see much sense for this.

Answer 5

For RSA, your public key may be as 2 bits. This is number 3, which can be your public key. A popular choice for an RSA public key is 17.