Cryptography Reference
In-Depth Information
otherwise we could only sum to 16
+
7
=
23. Hence the coefficient of 8 must
be 1. Thus:
25
10
=
(1
×
16)
+
(1
×
8)
+
(?
×
4)
+
(?
×
2)
+
(?
×
1)
.
Now the remaining three powers of 2 must add to 25
−
16
−
8
=
1. Consider
the ? coefficient next to 4. If 4 was included in our sum of powers of 2 then our
sum of powers of 2 would be greater than 25, since 16
+
8
+
4
=
28. Hence
the coefficient of 4 must be 0. Thus:
25
10
=
.
Now the remaining two powers of 2 must add to 25
−
16
−
8
=
1. Consider
the ? coefficient next to 2. If 2 was included in our sum of powers of 2 then our
sum of powers of 2 would be greater than 25, since 16
+
8
+
2
=
26. Hence
the coefficient of 2 must be 0. Thus:
25
10
=
(1
×
16)
+
(1
×
8)
+
(0
×
4)
+
(?
×
2)
+
(?
×
1)
(1
×
16)
+
(1
×
8)
+
(0
×
4)
+
(0
×
2)
+
(?
×
1)
.
Now the remaining power of 2 must add to 25
−
16
−
8
=
1. Consider the ?
coefficient next to 1. Clearly in order to complete our sum the coefficient of 1
must be 1. So:
25
10
=
(1
×
16)
+
(1
×
8)
+
(0
×
4)
+
(0
×
2)
+
(1
×
1)
.
Thus we have determined all the coefficients and so:
25
10
=
11001
2
.
This is a simple algorithm, although a bit awkward to perform by hand. It should
be clear, however, that this conversion algorithm is very easily performed on
a computer.
THE 3.3 TRICK
We tend to have an intuitive feel for decimal numbers because we use them every
day without thought or question. In cryptography we often represent keys in
binary. For example, an AES key can be 128 bits long, which means that it consists
of 128 binary bits. This means that there are 2
128
possible keys in the keyspace, but
what does this mean in terms of our more familiar decimal numbers? Fortunately,
there is a quick and easy way to get a fairly rough, but good, approximation to this
relationship. It is known as the
3.3 trick
:
• To change a power of 2 into a power of 10, divide the power of 2 by 3.3.
• To change a power of 10 into a power of 2, multiply the power of 10 by 3.3.
Thus, knowing that there are are 2
128
possible AES keys, we need to divide 128 by
3.3. The answer is close to 39, so 2
128
is approximately 10
39
.
Similarly, if we want to know how many bits long a symmetric key should be
in order to guarantee a keyspace of at least one million, we need to determine
what power of 2 is approximately equal to 10
6
. We thus need to multiply 6 by 3.3,
which is almost 20, so 10
6
is approximately 2
20
. Thus around 20 bits will suffice.
