3

I have noticed that when I am using GnuPG to encrypt a file for multiple recipients, the size of the encrypted message does not seem to be directly proportional to the number of recipients.

For example, a file that I tested is 836 bytes in plaintext.

  • encrypted for 1 recipient, it is 1090 bytes
  • encrypted for 2 recipients , it is 1619 bytes (810 bytes per recipient)
  • encrypted for 9 recipients, it is 4738 bytes (526 bytes per recipient)
  • encrypted for 51 recipients, 26,397 bytes (517 bytes per recipient)

Since encrypted data should look random, I am thinking that the difference is not due to compression. Not all of the 51 keys are the same key size/algorithm, but I do not see how this could account for such a dramatic average file size.

How is it that I can encrypt an 836 byte file for 51 people, so that they can all decrypt my file back to its original size without appending at least 836 bytes per recipient?

migrated from stackoverflow.com Dec 6 '14 at 2:28

This question came from our site for professional and enthusiast programmers.

6

Because the entire message is not encrypted separately for each recipient.

Instead, a single symmetric encryption key is chosen at random, the message is encrypted once using that key, and then the encryption key is itself encrypted separately for each recipient, using that recipient's public key, and appended to the encrypted message.

Each recipient decrypts the message by first using their private key to decrypt the symmetric encryption, and then decrypts the message using that key.

Since keys are typically much shorter than the plaintext, this saves a lot of space. (It also lets the recipients know they've all decrypted the same message. If the messages were encrypted separately for recipient, a devious sender could send different messages to each recipient, pretending they were all carbon copies of the same message.)

With your data, adding the second recipient added 527 bytes. That second recipient probably had a 512-byte key, plus 15 bytes to identify the recipient. Successive recipients will have had different key lengths and different identifying data, so the amount added for each will vary.

  • Thank you for this! This answers my question perfectly! – rose Dec 8 '14 at 19:57
1

Hybrid Encryption Systems

OpenPGP defines a hybrid encryption system, which combines the best of both asymmetric (public key) encryption and symmetric encryption. While asymmetric encryption is great at key management, it is very slow for encrypting large amounts of data; symmetric encryption on the other hand would require exchanging keys with everybody you want to communicate with individually, but has great performance.

Hybrid encryption systems use asymmetric encryption to encrypt a random key for symmetric encryption, while the actual message is symmetrically encrypted. In OpenPGP, this key is called the session key.

Multiple Recipients

This has another advantage: If multiple recipients should be addressed, there is no need encrypt the message multiple times. Instead, all that needs to be done is encrypting the session key for everybody. You can observe this by looking at the packets contained in a file after encrypting to multiple persons (here, pgpdump offers the better output compared to gpg --list-packets):

echo 'foo' | gpg --recipient a4ff2279 --recipient d745722b --encrypt | LANG=C pgpdump
Old: Public-Key Encrypted Session Key Packet(tag 1)(524 bytes)
    New version(3)
    Key ID - 0xCC73B287A4388025
    Pub alg - RSA Encrypt or Sign(pub 1)
    RSA m^e mod n(4093 bits) - ...
        -> m = sym alg(1 byte) + checksum(2 bytes) + PKCS-1 block type 02
Old: Public-Key Encrypted Session Key Packet(tag 1)(268 bytes)
    New version(3)
    Key ID - 0xDAA855623A5E68F7
    Pub alg - RSA Encrypt or Sign(pub 1)
    RSA m^e mod n(2046 bits) - ...
        -> m = sym alg(1 byte) + checksum(2 bytes) + PKCS-1 block type 02
New: Symmetrically Encrypted and MDC Packet(tag 18)(63 bytes)
    Ver 1
    Encrypted data [sym alg is specified in pub-key encrypted session key]
        (plain text + MDC SHA1(20 bytes))

The Public-Key Encrypted Session Key Packet is contained twize, once for each encryption (sub)key. The different size can be explained by the different key sizes (RSA 2048k vs RSA 4096k for the subkeys). The data is hidden in the Symmetrically Encrypted and MDC Packet.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.