tags:

views:

132

answers:

4

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?

+1  A: 

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

Matthew Flaschen
That has possibilities, although it would involve the generation and swapping of many one time pads using an independent process.
SystemicPlural
+1  A: 

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

Frank
256 bits is just an example of the key size. I am asking if that is also the minimum encrypted message size. Eg if I encrypt 'a' with a 256 bit key, would the encrypted message be a minimum of 256 bits long.
SystemicPlural
+3  A: 

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.

hermannloose
Thanks a stream cipher is what I was looking for.
SystemicPlural
A: 

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.

Paul Crowley
That was very clearly explained. So a 16 bit nonce would allow a reuse of 65,536, which gives me 88 bits of ciphertext. A little over 11 times the number of bits for the unencrypted character. Thanks.
SystemicPlural
I think what Frank was saying, is that if you then encode the cipher text, it will then shrink it down a bit further. Meaning 88bits is a worst case.
SystemicPlural
Nonces, authentication tags - none of those are implicit if the question only targets "encrypting a character", as all of them depend on your chosen mode of encryption, algorithms, etc as I tried to point out. Thus there is now *wrong* answers ... without any further clarification of the question, you can be arbitrarily specific without being useful. Just my 2 cents.
hermannloose
What do you mean "encode the cipher text"? Do you mean compress? It's not compressible.
Paul Crowley
@hermannloose The overhead I describe is necessary to meet the normal definition of security; it's not just a quirk of a particular mode. Unless your application is very unusual, a mode that doesn't impose such overhead will be the Wrong Thing, and unless you're a cryptographer you should assume that you do need the overhead.In general the crypto advice given here on stackoverflow.com is very bad; a lot of people speak with a great deal more authority than expertise.
Paul Crowley
@PaulCrowley What is your "normal definition" of security? Also, he was not asking for Good Things but rather some lower limit to what information and coding theory paired with abstract encryption mechanisms (abstract as in: "generic" block and stream ciphers) requires. OTP on an ASCII plaintext would give you 8 bits of ciphertext *AND* information theoretical security, being nowhere near a Wrong Thing nor an unusual application.
hermannloose