[Figure: FiveStudy logo]
FiveStudy
Cybersecurity · Unit 5 · 5.4.b
AP Cybersecurity · Securing Applications and Data
Why Key Length Matters
An n-bit key has a keyspace of 2ⁿ — and guessing it takes half that, on average.
key ideaAn n-bit key has a keyspace of 2ⁿ, and guessing takes 2ⁿ⁻¹ attempts on average.
The mechanism
Longer keys result in larger keyspaces. For binary keys, an n-bit key has a keyspace of 2ⁿ — so each additional bit doubles the number of candidates an adversary must work through.
The third box is the whole argument. One extra bit doubles the attacker’s work and adds almost nothing to yours — until the key gets long enough that encryption and decryption time becomes noticeable.| Key length | Keyspace | Average guesses to find the key |
|---|
8 bits | 2⁸ = 256 | 2⁷ = 128 |
16 bits | 2¹⁶ = 65,536 | 2¹⁵ = 32,768 |
128 bits | 2¹²⁸ | 2¹²⁷ |
256 bits | 2²⁵⁶ | 2²⁵⁵ |
The average is half the keyspace — an adversary guessing randomly expects to hit the right key after trying half of them, which is 2ⁿ⁻¹.
Keys and who holds them
| Claim | True? | Why |
|---|
an AES 256-bit key is more secure than an AES 128-bit key | yes | same algorithm, larger keyspace |
an RSA 4096-bit key is more secure than an RSA 2048-bit key | yes | same algorithm, larger keyspace |
an RSA 2048-bit key is more secure than an AES 256-bit key | cannot be concluded | key-length comparison is only valid within the same algorithm |
| longer keys are always the right choice | no | they require more time to encrypt and decrypt |
| a key length recommended ten years ago is still adequate | not necessarily | processing power and efficiency continue to improve, so recommendations change |
Row 3 is the one exams test. Comparing key lengths across different algorithms is meaningless — RSA and AES keys do fundamentally different work, and their bit counts are not on the same scale.
four facts about key length
- An n-bit binary key has a keyspace of 2ⁿ.
- Random guessing finds the key in 2ⁿ / 2 = 2ⁿ⁻¹ attempts on average.
- Longer keys are more secure but require more time to encrypt and decrypt messages.
- Recommendations change over time as processing power and efficiency improve.
Worked analysis
EX 1
Compute the expected work
How many guesses, on average, to find a 16-bit key by random search?
1
Find the keyspace
An n-bit key has 2ⁿ possible values, so 2¹⁶ = 65,536.
2
Apply the averaging step
Random guessing expects to succeed after half the keyspace.
3
Compute it
65,536 ÷ 2 = 32,768 — that is 2¹⁵, or 2ⁿ⁻¹.
4
State the general formula
2ⁿ / 2 = 2ⁿ⁻¹ guesses on average.
5
Note the scale
At 128 bits the same arithmetic gives 2¹²⁷ — a number no amount of hardware reaches.
EX 2
Compare two keys correctly
Is an RSA 2048-bit key more secure than an AES 256-bit key?
1
Note the difference in algorithm
RSA is asymmetric; AES is symmetric. They work in different ways.
2
Apply the CED rule
Key-length comparison is only valid when comparing keys for the same cryptographic algorithm.
3
State the conclusion
The comparison cannot be made from the bit counts alone.
4
Give a valid comparison instead
AES 256 is more secure than AES 128; RSA 4096 is more secure than RSA 2048.
5
Note why the intuition misleads
2048 looks far larger than 256, but the numbers are not measuring the same thing.
EX 3
Why recommendations change
A standard from a decade ago recommends a key length now considered inadequate. Explain.
1
State what has changed
Computational processing power and efficiency continue to improve.
2
State the effect
Software can guess keys faster than it could when the recommendation was written.
3
Note what has not changed
The keyspace of that key length is exactly the same — only the time to search it has fallen.
4
Give the consequence
Key-length recommendations change over time for both symmetric and asymmetric algorithms.
5
Give the practical rule
Treat a key length as a decision with an expiry date, and revisit it against current guidance.
Watch out
The average is half the keyspace, not all of it
An adversary guessing randomly expects success after 2ⁿ⁻¹ attempts. Quoting 2ⁿ as the expected work overstates the difficulty by a factor of two.
Never compare key lengths across algorithms
Key-length comparison is only valid within the same cryptographic algorithm. An RSA bit and an AES bit do not buy the same thing.
Longer is not free
Longer keys require more time to encrypt and decrypt. On high-volume or constrained systems that cost is real.
Recommendations expire
Processing power keeps improving, so key-length recommendations change over time. A length that was adequate is not permanently adequate.
Check yourself
What is the keyspace of an n-bit binary key?
Show answer
2ⁿ — longer keys result in larger keyspaces.
How many guesses does random searching take on average?
Show answer
2ⁿ / 2, which is 2ⁿ⁻¹ — on average an adversary finds the correct key after searching half the keyspace.
What is the cost of a longer key?
Show answer
Longer keys require more time to encrypt and decrypt messages, even though they are more secure.
Why is comparing an RSA key length with an AES key length invalid?
Show answer
Key-length comparison is only valid when comparing keys for the same cryptographic algorithm. Valid comparisons are AES 256 against AES 128, or RSA 4096 against RSA 2048.