cryptography The practice of altering the form of a
message by codes and ciphers to conceal its meaning to
those who intercept it, but not to those who receive it,
is called cryptography. If letters of the alphabet and
punctuation marks are replaced by numbers, then
mathematics can be used to create effective codes.
In 1977 three mathematicians, Ron Rivest, Adi
Shamir, and Leonard Adleman, developed a public-key
cryptography method in which the method of encoding
a message can be public to all without compromising the
security of the message. The RSA encryption method, as
it is known today, is based on the mathematics of the
MODULAR ARITHMETIC and relies on the fact that it is
extraordinarily difficult to find the two factors that produce a given large product. It is the primary encryption
method used today by financial institutions to transmit
sensitive information across the globe.
The RSA encryption method is based on the following result from modular arithmetic:
Suppose p and q are distinct PRIME numbers. If
n is a number with neither p nor q a factor,
then n
(p–1)(q–1)
≡ 1(mod pq). Moreover, we have
n
m(p–1)(q–1)+1
≡ n(mod pq) for any two natural
numbers n and m, even if n is a multiple of p
or q.
(We prove this result at the end of this entry.) One proceeds as follows:
1. Encode your message as a string M of numbers.
2. Choose two large prime numbers p and q so that their
product N = pq is larger than M. Let k = (p – 1)(q – 1)
and choose a number e with no common factor to k.
The numbers N and e can be made public.
3. Raise the number M to the eth power, modulo N.
This gives the encoded message M′:
M′ ≡ M
e (mod N)
4. Since the GREATEST COMMON DIVISOR of k and e is
one, the EUCLIDEAN ALGORITHM shows that we can
find numbers d and m so that 1 = de – mk. In particular there is a number d such that ed ≡ 1(mod k).
Keep the number d secret.
5. To decode the message, raise M′ to the dth power.
By the result stated above, this does indeed return
the original message M:
M′
d = M
ed = M
km+1 = M
m(p–1)(q–1)+1
≡ M (mod N)
If one works with very large prime numbers, say,
10,000-digit primes, it is virtually impossible to factor
the public number N and find k and d. Thus the RSA
system is extremely secure. (This use of large primes
also explains the current excitement over the discovery
of larger and larger prime numbers.) On the other
hand, multiplying and raising large numbers to powers
is easy for computers to do, and so the RSA method is
also very easy to implement.
Proof of Result
Suppose first that n is not a multiple of p and consider
the numbers 1,2,…,p – 1. Multiply each by n. If, for
two numbers x and y in the list, we have nx ≡ ny(mod
p), then n(x – y) is a multiple of p. This can only happen if x and y are the same number. Thus, up to multiples of p, the products n·1,n·2,…,n·(p – 1) are distinct
and so must represent a rearrangement of the original
list, modulo p. Consequently, n·1·n·2·…·n(p – 1) ≡
1·2·…·(p – 1) (mod p), and the factor n
p–1 in the left
must be congruent to 1 modulo p: n
p–1
≡ 1(mod p).
Similarly, we have n
q–1
≡ 1(mod q) if n is not a multiple
of q. It follows from these two results that if n is not a
multiple of p or q, then:
n
(p–1)(q–1) = (n
p–1
)
q–1
≡ 1(mod p)
n
(p–1)(q–1) = (n
q–1
)
p–1
≡ 1(mod q)
which shows that n
(p–1)(q–1) – 1 is divisible by both p
and q, and hence by pq. This proves the first claim
made. The second follows by noting that n
m(p–1) (q–1)+1 =
n·(n
p–1
)
m(q–1) ≡ n (mod p) is a true statement even if n is
a multiple of p, and n
m(p–1)(q–1)+1
≡ n (mod q) is also
true for all values of n. Any quantity n
m(p–1)(q–1)+1 – n is
thus always divisible by both p and q.
cube (hexahedron) The third PLATONIC SOLID, the
cube, is the solid figure bounded by six identical square
faces that meet at right angles. It has eight vertices and
12 edges. Because the VOLUME of a cube of side-length
a is given by a
3
, any number raised to the third power
is sometimes called a cube. The “cubic numbers” are
the cubes of the counting numbers: 0, 1, 8, 27, 64,
125,…
It is possible to subdivide a large cube into 27
smaller cubes with six planar cuts. This number of cuts
cannot be improved upon even if one is permitted to
cube 111
message by codes and ciphers to conceal its meaning to
those who intercept it, but not to those who receive it,
is called cryptography. If letters of the alphabet and
punctuation marks are replaced by numbers, then
mathematics can be used to create effective codes.
In 1977 three mathematicians, Ron Rivest, Adi
Shamir, and Leonard Adleman, developed a public-key
cryptography method in which the method of encoding
a message can be public to all without compromising the
security of the message. The RSA encryption method, as
it is known today, is based on the mathematics of the
MODULAR ARITHMETIC and relies on the fact that it is
extraordinarily difficult to find the two factors that produce a given large product. It is the primary encryption
method used today by financial institutions to transmit
sensitive information across the globe.
The RSA encryption method is based on the following result from modular arithmetic:
Suppose p and q are distinct PRIME numbers. If
n is a number with neither p nor q a factor,
then n
(p–1)(q–1)
≡ 1(mod pq). Moreover, we have
n
m(p–1)(q–1)+1
≡ n(mod pq) for any two natural
numbers n and m, even if n is a multiple of p
or q.
(We prove this result at the end of this entry.) One proceeds as follows:
1. Encode your message as a string M of numbers.
2. Choose two large prime numbers p and q so that their
product N = pq is larger than M. Let k = (p – 1)(q – 1)
and choose a number e with no common factor to k.
The numbers N and e can be made public.
3. Raise the number M to the eth power, modulo N.
This gives the encoded message M′:
M′ ≡ M
e (mod N)
4. Since the GREATEST COMMON DIVISOR of k and e is
one, the EUCLIDEAN ALGORITHM shows that we can
find numbers d and m so that 1 = de – mk. In particular there is a number d such that ed ≡ 1(mod k).
Keep the number d secret.
5. To decode the message, raise M′ to the dth power.
By the result stated above, this does indeed return
the original message M:
M′
d = M
ed = M
km+1 = M
m(p–1)(q–1)+1
≡ M (mod N)
If one works with very large prime numbers, say,
10,000-digit primes, it is virtually impossible to factor
the public number N and find k and d. Thus the RSA
system is extremely secure. (This use of large primes
also explains the current excitement over the discovery
of larger and larger prime numbers.) On the other
hand, multiplying and raising large numbers to powers
is easy for computers to do, and so the RSA method is
also very easy to implement.
Proof of Result
Suppose first that n is not a multiple of p and consider
the numbers 1,2,…,p – 1. Multiply each by n. If, for
two numbers x and y in the list, we have nx ≡ ny(mod
p), then n(x – y) is a multiple of p. This can only happen if x and y are the same number. Thus, up to multiples of p, the products n·1,n·2,…,n·(p – 1) are distinct
and so must represent a rearrangement of the original
list, modulo p. Consequently, n·1·n·2·…·n(p – 1) ≡
1·2·…·(p – 1) (mod p), and the factor n
p–1 in the left
must be congruent to 1 modulo p: n
p–1
≡ 1(mod p).
Similarly, we have n
q–1
≡ 1(mod q) if n is not a multiple
of q. It follows from these two results that if n is not a
multiple of p or q, then:
n
(p–1)(q–1) = (n
p–1
)
q–1
≡ 1(mod p)
n
(p–1)(q–1) = (n
q–1
)
p–1
≡ 1(mod q)
which shows that n
(p–1)(q–1) – 1 is divisible by both p
and q, and hence by pq. This proves the first claim
made. The second follows by noting that n
m(p–1) (q–1)+1 =
n·(n
p–1
)
m(q–1) ≡ n (mod p) is a true statement even if n is
a multiple of p, and n
m(p–1)(q–1)+1
≡ n (mod q) is also
true for all values of n. Any quantity n
m(p–1)(q–1)+1 – n is
thus always divisible by both p and q.
cube (hexahedron) The third PLATONIC SOLID, the
cube, is the solid figure bounded by six identical square
faces that meet at right angles. It has eight vertices and
12 edges. Because the VOLUME of a cube of side-length
a is given by a
3
, any number raised to the third power
is sometimes called a cube. The “cubic numbers” are
the cubes of the counting numbers: 0, 1, 8, 27, 64,
125,…
It is possible to subdivide a large cube into 27
smaller cubes with six planar cuts. This number of cuts
cannot be improved upon even if one is permitted to
cube 111