Understanding Cryptography by Christof Paar and Jan Pelzl - Chapter 1 Solutions - Ex1.4
- 2 mins- Return to index
- Exercise 1.1
- Exercise 1.2
- Exercise 1.3
- Exercise 1.4
- Exercise 1.5
- Exercise 1.6
- Exercise 1.7
- Exercise 1.8
- Exercise 1.9
- Exercise 1.10
- Exercise 1.11
- Exercise 1.12
- Exercise 1.13
- Exercise 1.14
Exercise 1.4
We now consider the relation between passwords and key size. For this purpose we consider a cryptosystem where the user enters a key in the form of a password.
- Assume a password consisting of 8 letters, where each letter is encoded by the ASCII scheme (7 bits per character, i.e., 128 possible characters). What is the size of the key space which can be constructed by such passwords?
- What is the corresponding key length in bits?
- Assume that most users use only the 26 lowercase letters from the alphabet instead of the full 7 bits of the ASCII-encoding. What is the corresponding key length in bits in this case?
- At least how many characters are required for a password in order to generate a key length of 128 bits in case of letters consisting of a) 7-bit characters? b) 26 lowercase letters from the alphabet?
Solution
I haven’t yet verified this solution independently. If you spot any mistakes, please leave a comment in the Disqus box at the bottom of the page.
1. There are 128 (\(2^7\)) possible characters. If the password is 8 characters long, we can calculate the number of possible 8-character passwords as follows:
2. The key length in bits is what power of two corresponds to the total number of possible passwords. We’ve already calculated that there are \(2^{56}\) possible passwords. The key length is therefore 56.
3. If the password is restricted to the lower case letters, then this reduces the number of possible characters from 127 to 26. We can then recalculate the number of possible 8-letter passwords:
We can then calculate what length key in bits this is equivalent to:
4. In order to calculate what password length corresponds to 128 bits, we need to work out what power of the number of possible characters corresponds to \(2^{128}\).
a) Since 128 is also a power of 2, the equations can be understood in a simple way, where \(i\) is the character length required to create the equivalent of a \(2^{128}\) bit key:
If we take the powers of two and do \(\log_2\) on both sides, we can solve this equation fairly trivially:
b) This isn’t as trivially solved, since 26 can’t be cleanly represented as a power of 2. However, the equations are still fairly simple:
Thomas Busby
I write about computing stuff