What is the keyspace of ROT-13?

Today I was having a discussion with my cryptography lecturer about the keyspace of a ROT-13 cipher. He argues that the keyspace is 0 because it doesn't have a key.

Could anyone explain to me why the keyspace is 0 and not 1? I could understand if he said that it doesn't have a keyspace but I don't understand why it could have a keyspace of 0.

I was further confused when he said that it was possible for a cryptographic function to have a keyspace of 1. Could someone give me an example of a cryptographic function with a keyspace of 1 and explain how it is different to one with a keyspace of 0?

I feel fairly confused about something that seems like a pretty basic concept.

Thanks for any help.

I think it's better to define the keyspace of an unkeyed function as having one element.

• Computing the key size as $log_2 1$ correctly tells you it's a 0 bit key
• For encryption you pick one key from the set. You can pick an element of a single element set, but can't pick from an empty set
• Functions with multiple inputs are often defined to take the Cartesian product of their inputs. For example for encryption this could be $M \times K \to C$ where $M$ is the space of messages, $K$ the key space, and $C$ the ciphertext space. One again, this only works correctly if you use a single element set as key space.
• I also think that a keyspace of 1 is better, but didn't have any "real" reasons. This answers solves this problem. +1 – Nova Jan 7 '15 at 15:18
• Ok, makes mathematical sense. If it makes sense in a human context, I don't know. I could live with having no choice to mean choice of one. 0 would mean that the function is not even executed in that case. – Maarten Bodewes Jan 7 '15 at 16:15
• I tend to think differently on this: ROT13 isn't a cipher, in my opinion, precisely because it is unkeyed. Therefore, the question "what is the size of the keyspace of ROT13" is ill-posed, precisely because it has no key (it quite literally has no key parameter in its function signature). I would argue that ROT13 is an encoding, like Base64 or hex. If you don't consider either of those to be a keyed cipher, it makes little sense to me to consider ROT13 to be one. Of course, you can generalize ROT13 to "ROT" encryption, at which point it becomes keyed with a keyspace size of 26. – Stephen Touset Jan 7 '15 at 18:41

It depends how you look at it. If you regard it as a Caesar cipher then the key is 13 (out of a key space of 26 for uppercase ASCII, although key 0 is a very weak key, resulting in the identify function). If you consider that 13 is part of the ROT13 cipher then it indeed has no key.

Of course having a static key or no key does not make a difference in practice. It can make mathematical sense to count one key as you need to decrypt one time to "brute force" a ciphertext (as CodesInChaos has shown). However, that would mean that constants can be keys as well, and that algorithms that are not ciphers could be thought of as having keys.

So in the end it depends on context and opion.

• It seems that if you have a block cipher that uses a Feistel network with configurable S-boxes that the S-boxes are also included in the key space. So you could argue that 13 becomes a key if it is configurable. But then it has a key space of 26 again. Don't know if this is any definitive argument, but it seems to come close. – Maarten Bodewes Jan 5 '15 at 14:46
• Think of it like this. You're given a ciphertext, and no indication of the cipher used. Do you first try all the caeser ciphers, or do you try rot13? If you already know it's rot13, the knowledge of the cipher itself tells you there's no key. If you don't, but suspect it's a caeser cipher, you have to go through 26 keys. – Steve Sether Jan 6 '15 at 23:17
• @SteveSether: Talking about a keyspace is always together with a cipher. You can't argue with an unknown cipher - what if it is not caesar but vigenere? Or a really suprising result of a AES encryption? – Nova Jan 7 '15 at 15:49
• @Nova1 I think the point is a different way of explaining that Maarten was saying. Rot13 and a Caesar cipher with a key of 13 are the same thing. As Maarten points out, it depends on how you look at it. Someone trying to do the crack the cipher has no idea how the original encryptor wanted to think of it. – Steve Sether Jan 7 '15 at 17:18