Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I am a newbie here, this is my first post.

I have searched the forum but I haven't found a clear answer to this.

In general. What is the relationship between key length and the keyspace? (if there is any at all)

For example, with the Simple Substitution Cipher, I understand that the keyspace is 26! (because there are 26 characters in the English alphabet)

The key length is 26? (due to 26 characters in the english alphabet) Is it?

The keyspace seems to be quite long, isn't it? so looking at the keyspace the 'Simple Substitution Cipher' would be quite secure. But looking at the keylengh, being only 26 long, how could this be considered secure by today standards?

Could anyone shed some light here? Again, sorry for my naivity if I am missing something important here.

Thanks in advance

share|improve this question

2 Answers 2

up vote 5 down vote accepted

Key length is the length of the key. It's a term whose meaning has evolved over time; these days, it typically means length in bits. With digital symmetric ciphers, it's fairly simple, because those tend to have a key that's just a string of some number of bits, and any string of that length is a valid key. With RSA, it's more complicated - the key has a bunch of elements, and can be written in various formats or with more or less info. With algorithms like that, there's generally some standard thing whose length is the key length (with RSA, it's the modulus).

The key space is the set of all possible keys. With symmetric ciphers, where any string of $n$ bits is a valid key, the key space has $2^n$ elements. With asymmetric ciphers, it's more complicated.

With monoalphabetic substitution ciphers, you have $26!$ keys, but key length depends on how you're expressing the key. If you compress the key as much as possible, you can fit it in 89 bits ($2^{88}<26!<2^{89}$), so if you want to directly compare key length with other symmetric algorithms (to talk about brute-forcing) you'd say it has an 89-bit key. Expressed another way, it has a 26-letter key, but not all 26-letter keys are valid keys (AA...AA isn't, for instance). But letters are not bits; if each letter is encoded in 5 bits, this is a 130-bit key, but very few of the 130-bit keys are valid. That's why you'd look at the smallest you could possibly make the key, which is 89 bits.

This is actually reasonably long; it's weak by modern standards, but in the 1980s and 1990s would have been fine. The issue is that you don't attack it by brute-force, but by cryptanalysis; that means key length is a bit beside the point.

share|improve this answer

Assuming the Alphabet is only 26 values, you have: 26! or 403,291,461,126,606,000,000,000,000 ways of rearranging it.

This is not key space for a single substitution alpha. You would need to be able to create, or at least have the means of creating, n random Alphas for the number to be relevant.

An encryption of 3 characters (say abc) over a random 26 character alphabet has 3^26 possible outcomes (17,576). Key Length in this scenario is 3. Key space is 17,576.

In this regard, and Per conventional wisdom, all basic substitution ciphers substitute in sequential order. Thus, A=B, B=C etc. If this is the case, abc resolves to a key space of 650 (26 x 25).

If you were to create Random Alphabets using the full ANSI character set, the key space is much larger 256!, but you would not be able to create all of them in memory on any computer known to exist.

Assume you only create 256 Alphabets, in random order, where each alphabet has all of the ansi characters, and each alphabet is fully random. The Key space is still the same, but you would need to invoke a PRNG to create the Alphas.

Then, you would then need a method of choosing each alphabet for each character or byte to be encrypted. (PRNGs are handy for this too). It naturally follows that you need sufficient index values to match the length of the original message. This is key length.

So, now it seems like we have some really big numbers to play with but, the reality is this;

A PRNG created on a default RND generator is usually flawed since repetion invokes at very low numbers. Take for example the original Visual Basic RNG. Repetition kicks in at 2^21 (about 2 million). So, you may think 'so what', 2 million times the keyspace is big.

But no. While it is true that the available maximum seeds of the RNG are now part of the key space, Kaspersky Labs operating at around 300 billion attempts per second would require approx 63 minutes to exhaust the key space. The NSA are at least 100,000 times faster.

Why is this? Although the keyspace of 26! is massive, this assumes full randomness of that keyspace and every character or byte to be encrypted has access to that entire keyspace.. In Practical terms, not achievable.

Using PRNGs that work to 2^31 seeds, such as Mersenne, would make a significant impact and increase the discovery time substantially, although still not out of scope for the NSA (a few days).

Ideally, you would need to invoke multiple independent RNGs, all capable of at least 2^31 and Xor the alphas in a random manner. In the next few months, I'll publish a paper explaining how to do this.

In the mean time, study PRNGs and consider how these can be used to create replicable numeric sequences. For example, how can a PRNG turn a string password into a useable numeric seed of 1 to 2^31?

Avoid discussions about TRNGs vs PRNGs, since anyone who advocates either doesn't know how they are used. CSPRNG discussions are useful, but pedantic.

And, avoid bull crap from people who tell you that 'rolling your own' is dangerous, or who spout 'leave it to the professionals'. Those guys are big on re-quoting formulas to make themselves seem smart, but they lack original thought.

(apologies for spelling errs, it be Friday, me be drinking).

G.

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.