# What exactly does a key do?

I am getting to grips with cryptography as a total newbie, and am struggling with encryption "keys" and how to visualize them. From http://computer.howstuffworks.com/encryption.htm/printable:

Symmetric-key encryption is essentially the same as a secret code that each of the two computers must know in order to decode the information. The code provides the key to decoding the message.

Think of it like this: You create a coded message to send to a friend in which each letter is substituted with the letter that is two down from it in the alphabet. So "A" becomes "C," and "B" becomes "D". You have already told a trusted friend that the code is "Shift by 2". Your friend gets the message and decodes it. Anyone else who sees the message will see only nonsense.

The same goes for computers, but, of course, the keys are usually much longer. [...] The DES uses a 56-bit key.

This doesn't make sense to me because the process of "shifting by 2" sounds like the algorithm that is being used, yet it is referred to as a "key"? If this is the key, then what is the algorithm?

I also don't completely understand what it means the key is "56 bit" in length. The linked article mentions

56-bit key offers more than 70 quadrillion possible combinations

Now, this huge number is just under $2^{56}$, so each of those $56$ bits can be either a $1$ or a $0$, but I don't see how this fits into it all.

Can someone please clarify this for me?

-
In that sample you could consider "Shift by $x$" the algorithm (Caesar encryption) and $x=2$ the key. This would be a $\log_2{26}\approx4.7$ bit key. – CodesInChaos Jul 8 '14 at 15:09
OK, that makes a bit more sense. thanks. Could you please tell me where the log calculation comes from? – Wad Jul 8 '14 at 15:12
If you have an $b$ bit key, there are $2^b$ possibilities. The base 2 logarithm $\log_2$ is the inverse of the exponential function $2^x$. So with 26 possible keys, you get $\log_2{26} \approx 4.7$ or equivalently $2^{4.7} \approx 26$. – CodesInChaos Jul 8 '14 at 15:36
OK, just thinking about why you say there are 26 keys: I assume it is the number added to the input character to get the output character: in this case, wouldn't there actually be 25 keys: since if there were 26, adding 26 to a letter would result in the same letter, assuming we 'cycle' around? Or have I misunderstood where you get 26 from? – Wad Jul 8 '14 at 16:36
@Wad: yes, one of the 26 keys (the "shifting by 0" one) would be a weak key, which doesn't change anything. If you are encrypting only a single letter, then this is just a valid key as all other ones. – Paŭlo Ebermann Jul 8 '14 at 20:48

Picking up what has been said in the comments:

to simplify: symmetric ciphers are like mathematical operations with 2 operands and 1 result. There is The plaintext message $m$ and $k$ as the key and they result in the ciphertext $c$. In your example, the algorithm can be cut down to a addition and modulo:

$c = (m + k) \mod k_{max}$

And of course there is a reverse algorithm (or more simply operation) that will turn $c$ into $m$ again:

$m = \begin{cases} c - k,& \text{if } c\geq k\\ c + k_{max} - k,& \text{otherwise} \end{cases}$

To sum it up: The way of calculation (the algorithm) never changes. Instead, the parameter(s) to it, the key, are different.

In the computer world these operations are much more complex and involve operations that are easy to compute in the binary system (e.g. XOR or bit-shiftig) that are rather complex to express mathematically.

-
Thanks; how do we decide what the maximum value of k can be though in this case? – Wad Jul 8 '14 at 16:39
The alphabet has 26 letters so the index ranges from 0 to 25 (lets call that interval $[0, 25]$ $I$). We have to choose $k_{max}$ such that $(x \mod k_{max}) \in I$. That yields $k_{max} = 26$. To put it more simple: $x \mod y \gt 0$ for all $x$ and $y$ greater than $0$. Concerning that condition $x \mod y \leq y - 1$. So if $m + k \mod k_{max}$ has to be less than or equal to 25, $k_{max} = 26$. – marstato Jul 8 '14 at 16:51
Thanks. I am still not getting though how we can have keys that are 128 bits in length; the only way I can visualize this is to imagine that we have in fact $2^{128}$ letters instead of 26, meaning that the key could be any value between 0 and $2^{128}$-1 (which would make it harder to decipher). Is this about right? – Wad Jul 11 '14 at 10:09
No. In real use there are bytes ($[0 ... 2^8-1]$). A 128-bit key has $128 : 8 = 16$ bytes. In most symmteric ciphers the bytes are operated on isolated; the 128bit portion of key is never used as a whole for one operation. Take a look at this explanation of AES, it will clear things up: moserware.com/2009/09/stick-figure-guide-to-advanced.html In asymmetric cryptography (RSA, DSA, ElGamal ...) the keys (in RSA up to 4096 bits in everyday-use) the plaintext and key are both used as one number. And yes, in these cases the sheer length makes deciphering without key impossible. – marstato Jul 12 '14 at 8:35

Put another way, you can say that the key is whatever information the recipient possesses which allows him to decrypt the message, and which must be kept secret from everybody else. Thus, "algorithm" and "key" are not mutually exclusive: if knowledge of the algorithm allows one to decrypt a message, then the algorithm is the key.

-