Cryptography Reference
In-Depth Information
be generated by a computer programyet confound this second-order
entropy calculation. Shannon defined the entropy of a stream to in-
clude all orders up to infinity. Counting this high may not be possi-
ble, but the higher order terms can usually be safely ignored. While it
may be practical to compute the first- or second-order entropy of an
information stream, the amount of space devoted to the project obvi-
ously becomes overwhelming. The number of terms in the summa-
tion grows exponentially with the order of the calculation. Shannon
created several experimental ways for estimating the entropy, but the
limits of the model are still clear.
2.3.1 RSA Encryption
The section “Encryption and White Noise” on page 20 described RSA
encryption with the metaphor of a long circle of beads. Here are
the equations. The system begins with two prime numbers
p
and
q
.
Multiplying
p
and
q
together is easy, but no one knows of an efficient
n
=
pq
p
q
way to factor
into its components
and
if the numbers are
large (i.e., about 1024 to 2048 bits).
This is the basis of the security of the system. If you take a number
x
x
x
φ(n)
mod
pq
=
x
.
4
and compute the successive powers of
,then
x
pq
That is, if you keep multiplying a number by
modulo
,thenit
returns to
)+1
steps.
Amessage is encrypted by treating it as the number
x
after
φ
(
pq
x
.Thesender
encrypts the number
x
by multiplying it by itself
e
times, that is com-
e
mod
puting
x
pq
. The receiver decrypts the message by multiplying
e
)
d
mod
it by itself
d
times, that is computing
(
x
pq
.If
d ×
3=
φ
(
x
)
,
then the result will be
x
.
)
is called the
Euler Totient
function and it is the number
of integers less than
This
φ
(
n
n
that are relatively prime to
n
.If
n
is a prime
number then
φ
(
n
)
is
n −
1
because all of the integers less than
n
are relatively prime to it. The values are commutative so
φ
(
pq
)=
φ
(
p
)
φ
(
q
)
.Thismeansthat
φ
(
pq
)=
pq − p − q
+1
.Forexample,
φ
(15) = 8
.Thenumbers
1
,
2
,
4
,
7
,
8
,
11
,
13
and
14
are relatively prime
to
15
.Thevalues
3
10
and
12
are not.
Calculating the value of
,
5
,
6
,
9
,
,but
no one knows an efficient way to do it if you don't. This is the basis for
the RSA algorithm. The circumference of this string of pearls or beads
is
φ
(
pq
)
is easy if you know both
p
and
q
)
. Moving one pearl or bead along the string is the equivalent
of multiplying by
φ
(
pq
x
.
4
x mod y
means the remainder after
x
is divided by
y
.So
9mod7
is
2
,
9mod3
is
0
.
