Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Is there any encryption algorithm that is not bijective function ?

Should an encryption always give the same result given same key ?

share|improve this question

5 Answers 5

up vote 6 down vote accepted

Formally a (symmetric) encryption function is a function $E$ from $\mathcal{M} \times \mathcal{K}$ to $\mathcal{M}$, where $\mathcal{M}$ is a message space (here we use, for convenience, the same for cipher and plaintext) and $\mathcal{K}$ a keyspace. For a fixed $k \in \mathcal{K}$ we want $E(.,k)$ to be a bijection from $\mathcal{M}$ to $\mathcal{M}$: this just means every message has a unique encryption under the key $k$ and every message can be decrypted too. (There are also notions of randomized encryption, etc., but this is the simplest model).

For algorithms like RSA, or cipher modes like CBC, it is true that one message, under one key, has multiple encryptions, but the decryption should always be doable in a unique way (we can filter out, so to say, the randomness we have added as an extra ingredient in encryption). It's necessary in assymetric cryptography (like RSA) in order to have a secure system, and most likely in symmetric systems too. It avoids some attacks that would exist otherwise.

[edit] To give an example, for RSA we use a large key (say a 1024 bit modulus $n$, with some encryption exponent $e$ ), so we can encrypt stuff that has size around 128 bytes (a bit less, because we consider numbers $x < n$ as messages, that can be encrypted as $x^e \mod n$). Now, if we have a message (like, say "Hello", or some 16 byte key we want to use for later communications, as RSA is often used, but say we use "Hello", in its ASCII encoding (hex) 48 65 6c 6c 6f and we want to send that as a message, we could use the string, as a big number 0x48656c6c6f which is less than $n$ (I won't give an example, but recall we chose it of size 128 bytes), so we could just encrypt it, and decrypt it uniquely. However, this leaves an attacker (who also knows $n$ and $e$, so could do the same encryption) with the option of trying out the encryption (under this key) of all words in a dictionary and so find the message, without really breaking RSA. So in practice (this is a commonly used standard; other exist but are harder to explain), we generate a number $x$ from the message by forming a 128 byte number as follows: first a byte 0x00, then a byte 0x01, then 120 random non-zero bytes, then again a byte 0x00 and then the message 0x48 65 6c 6c 6f (5 bytes), in total a number of 128 bytes, that starts with 0x00 to ensure it's less than any $n$ of that size 128 bytes and this is the $x$ we use to compute $x^e \mod n$. After decryption (uniquely, by doing another exponentiation) we strip off the random bytes (all non-zero, so we know the original message starts after the first 0x00 after the initial one. This way, the attacker cannot precompute all possible ciphertexts for a given plaintext. This is called "padding the message", and the standard requires at least non-zero random bytes.

So in a way, decryption is still unique, but we made sure that the possible ciphertexts (as number less than $n$) are not all possible such numbers, only the ones we get after a valid padding. The "actual", intended message is shorter. So RSA as a function is a bijection, but as a "real message" to "ciphertext" mapping it is not a real function. It will be if we add the randomization as a factor: given a message, a random number (for padding) and a key, the result is still uniquely decipherable, and we can, given a key, separate out the message and the randomness. But note that that we changed the encryption function a bit: message space and ciphertext space are different now, and this has added security value. The disadvantage is that we cannot directly encrypt any string anymore. But in practice, only small values are encrypted under RSA, which are then used as a new key for a faster algorithm.

For an example of this in symmetric crypto, look at cipher modes like CBC wikipedia link that also expand the ciphertext by an extra IV block to get more than one possible ciphertext for a single plaintext.

share|improve this answer
    
So the answer is YES given the same key ? –  iKid Apr 27 '11 at 9:39
1  
for the simplest systems, yes, for real life systems most often no. –  Henno Brandsma Apr 27 '11 at 9:41
    
could you give me an example with "NO" ? if an encryption can give two different results given the same key or 1 cipher text can come from 2 different encryption, how could it be decrypted ? –  iKid Apr 27 '11 at 9:43
    
Given the key, the decryption should be unique. I'll edit to give an example. –  Henno Brandsma Apr 27 '11 at 10:21
    
I think his point is that modern encryption isn't even a true function, but a "set-valued"/multi-valued function. –  Nicholas Dixon Jun 14 '11 at 12:34

Encryption algorithms will not be surjective if you want to have a checksum feature. (A checksum can be detect submission errors. For example you can add a digit that makes the number divisible by 9. If you receive a number that is not divisible by 9, you know that there has been a transmission error.)

I am not sure about your second question. Of course, the encryption can vary by time, but maybe this is not your question. (If the encryption varies by circumstances this can also be viewed as a key change, but I note that there are very simple "encryption" systems that are not injective. For example, the word "lead" encodes very different meanings that have to be reconstructed from context. This problem is also very present for alphabets without vowels.)

Clearly, if you construct modern encryption algorithms you will want to have an injective function, but there are situation (like some hash functions) where people are satisfied that the function will be almost always injective in practice.

share|improve this answer
    
could you explain more ? what is checksum feature ? If encryption with same key can give 2 different results, how can it be decrypted ? –  iKid Apr 27 '11 at 9:32

An encryption algorithm which is not guaranteed to give the same result for the same inputs (i.e. encryption key and message) is certainly possible. In fact, the initialisation vector for chained block ciphers is usually random, but we usually consider it as one of the inputs because for a fixed encryption key and initialisation vector, the algorithm will be deterministic.

As such, an encryption algorithm is not necessarily a well-defined function, in the mathematical sense. Nonetheless, it is essential that under no circumstance the algorithm map two different inputs to the same output — otherwise decryption is impossible. So, if the encryption algorithm is deterministic, it is at least an injective map. Moreover, if the decryption algorithm can accept any string as a ciphertext, then the encryption algorithm must also be surjective, and in this situation it is bijective.

share|improve this answer
    
so If I add in that the plain text and cipher text domain is any string and the encryption function including any other inputs ( key, IV ..) except plain text. The answer should be "YES" ? How could an encryption algorithm is non-deterministic algorithm? Is there any example ? –  iKid Apr 27 '11 at 9:55
    
Yes, given the rest of the encryption scheme data, the mapping from plain to cipher and back is a bijection, between appropriate sets, see the RSA example. –  Henno Brandsma Apr 27 '11 at 13:21

"Should an encryption always give the same result given same key ?"

No. If the ciphertext message is ever the same, then the system is vulnerable to replay attacks.

You probably already know several encryption algorithms that, if you cipher the same plaintext with the same key, always deterministically produce identically the same ciphertext.

There are many encryption algorithms (some listed below) that, if you cipher the same plaintext with the same key a hundred times, will (almost certainly) produce a hundred different ciphertexts.

If you decrypt those 100 ciphertexts with the right key and the appropriate decryption algorithm, they will all produce a perfect copy of the original plaintext.

These cryptosystems generally have the transmitter pull numbers from a random number generator, and somehow transmit those random numbers to the receiver inside the ciphertext message. Given exactly the same inputs -- i.e., the random number generator is broken and produces exactly the same bytes again, a bug in the software lets you keep using the same key even after the message counter rolls over to zero, and we use the same key and plaintext message -- these cryptosystems would produce the same ciphertext message.

symmetric ciphers with an IV

Every cipher that uses an initialization vector will encrypt the same plaintext in many different ways. (They are not bijective).

Typically the ciphertext is composed of a random initialization vector (sent unencrypted) concatenated with the encrypted data (generally the same length as the plaintext, or rounded up to a full block). The initialization vector is freshly generated for every message. (With TKIP and CCMP, the IV is a simple counter -- the TSC; with some other encryption algorithms, the IV is freshly pulled from a random number generator). The initialization vector is 10 bytes for CipherSaber, 3 bytes for Wired Equivalent Privacy, 6 bytes for TKIP, 6 bytes for CCMP, etc.

public-key ciphers

Hybrid cryptosystems encrypt the same plaintext in many different ways. (They are not bijective).

PGP, GPG, SSL, TLS, SSH, etc. use hybrid cryptosystems.

The ciphertext message is composed of an encrypted temporary key concatenated with the encrypted data (generally the same length as the plaintext, or rounded up to a full block).

The temporary key is freshly pulled from a random number generator for every message. So the same plaintext message, sent at another time, will almost certainly be encrypted with a different temporary key and so almost certainly will generate a different ciphertext message.

The plaintext message is encrypted with a symmetric cipher using the temporary key. The temporary key is encrypted with a public-key cipher using the public key of the recipient.

share|improve this answer

Here is a solution, given many cases.

Symmetric Key Ciphers

Encryption Alone

No, at least not encrypting under the same key. If E(k1,u) = E(k2,u) then it would not have a receiver would be confused on which one.

But with different keys this would be impossible. If M is the message space and K is the key space, E: M x K -> M. But the space of all possible (M,K) is bigger than M, so this is impossible.

Encryption with an IV

Now, we have a similar argument: EM : (M,K,I) -> M, but the set of all (M,K,I) is larger than M. Bijective functions using modes like CBC and other IV-using modes (almost all of them) cannot exist.

But with the same key, encryption is still influenced by the IV, making it still non-bijective. Same with same IV but different key. But if the we have the same key and same IV, unlike encryption alone, this is non-bijective.

Non-symmetric key ciphers

See the arguments from "encryption with IV", because there are three arguments: Message, Private key, Public key.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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