encryption of a single character

Question

What is the minimum number of bits needed to represent a single character of encrypted text.

eg, if I wanted to encrypt the letter 'a', how many bits would I require. (assume there are many singly encrypted characters using the same key.)

Am I right in thinking that it would be the size of the key. eg 256 bits?

Answer 1

I'm afraid all the answers you've had so far are quite wrong! It seems I can't reply to them, but do ask if you need more information on why they are wrong. Here is the correct answer:

About 80 bits.

You need a few bits for the "nonce" (sometimes called the IV). When you encrypt, you combine key, plaintext and nonce to produce the ciphertext, and you must never use the same nonce twice. So how big the nonce needs to be depends on how often you plan on using the same key; if you won't be using the key more than 256 times, you can use an 8 bit nonce. Note that it's only the encrypting side that needs to ensure it doesn't use a nonce twice; the decrypting side only needs to care if it cares about preventing replay attacks.

You need 8 bits for the payload, since that's how many bits of plaintext you have.

Finally, you need about 64 bits for the authentication tag. At this length, an attacker has to try on average 2^63 bogus messages minimum before they get one accepted by the remote end. Do not think that you can do without the authentication tag; this is essential for the security of the whole mode.

Put these together using AES in a chaining mode such as EAX or GCM, and you get 80 bits of ciphertext.

The key size isn't a consideration.

Answer 2

Though the question is somewhat fuzzy, first of all it would depend on whether you use a stream cipher or a block cipher.

For the stream cipher, you would get the same number of bits out that you put in - so the binary logarithm of your input alphabet size would make sense. The block cipher requires input blocks of a fixed size, so you might pad your 'a' with zeroes and encrypt that, effectively having the block size as a minimum, like you already proposed.

Answer 3

You can have the same number of bits as the plaintext if you use a one-time pad.

Answer 4

This is hard to answer. You should definitely first read up on some fundamentals. You can 'encrypt' an 'a' with a single bit (Huffman encoding-style), and of course you could use more bits too. A number like 256 bits without any context is meaningless.

Here's something to get you started: Information Theory -- esp. check out Shannon's seminal paper One Time Pad -- infamous secure, but impractical, encryption scheme Huffman encoding -- not encryption, but demonstrates the above point