Solutions to Odd-Numbered Exercises

Section 1.1 (In the solutions, we will violate the convention of having plaintext in

lower case in order to increase readability due to the smaller font size we use herein.)

1.1 I THINK THEREFORE I AM

This is the phrase coined by the seventeenth century philosopher-mathematician

Ren´ Descartes, and may be said to be the signature of the basis of his reasoning.

e

It was originally given in Latin as: Cogito ergo sum.

1.3 BEHOLD THE SIGN

1.5 NON SEQUITUR

This is the Latin phrase for a conclusion that does not follow logically from the

premises.

1.7 TRUTH CONQUERS ALL THINGS

1.9 WAR IS IMMINENT

1.11 NEVER SAY ANYTHING

1.13 VANITY

1.15 Since

m = (01110011010010010011010000110000100011110000000011) =

(01110)(01101)(00100)(10011)(01000)

(01100)(00100)(01111)(00000)(00011),

then the decimal equivalents are

14, 13, 4, 19, 8, 12, 4, 15, 0, 3,

to which correspond the letters O, N, E, T, I, M, E, P, A, D, to give us the En-

glish plaintext:

ONE TIME PAD

1.17 Since k + c =

(11010111101111010101111011101011010) +

(10010100111110111011010011101101001) =

(01000011010001101110101000000110011) =

(01000)(01101)(00011)(01110)

(10100)(00001)(10011),

then the decimal equivalents are 8, 13, 3, 14, 20, 1, and 19. Hence, via Table

1.2, we get the English equivalents: I, N, D, O, U, B, T , to give us the English

plaintext:

IN DOUBT

© 2003 by CRC Press LLC

Solutions to Odd-Numbered Exercises 1.19“1.47 225

1.19 Since k + c =

(11010111101111010101111011101011010) +

(11010100111110111110101011111001000) =

(00000011010001101011010000010010010) =

(00000)(01101)(00011)(01011)

(01000)(00100)(10010),

then the decimal equivalents are 0, 13, 3, 11, 8, 4, and 18. Hence, via Table

1.2, we get the English equivalents: A, N, D, L, I, E, S, to give us the English

plaintext: AND LIES

1.21 Since

k + c = (11010111101111010101111011101011010) +

(11111100000111110001010001111001011) =

(00101011101000100100101010010010001) =

(00101)(01110)(10001)(00100)

(10101)(00100)(10001),

then the decimal equivalents are 5, 14, 17, 4, 21, 4, and 17. Hence, via Table

1.2, we get the English equivalents: F, O, R, E, V, E, R, to give us the English

plaintext:

FOREVER

Section 1.2

1.23 SEARCH THE CAVES

1.25 BOMB THE CAMPS

1.27 SURROUND THE CITY

1.29 SHE CREATED A STATE

1.31 HE DESTROYED TOWNS

1.33 BOTH STRUGGLES END

1.35 FIND THE SECRET NOW

1.37 HAVE ANOTHER ONE

1.39 TRY TO REMEMBER

1.41 WHERE IS THE GOLD

Note that we discard the Z at the end since it was a ¬ller to make the last triplet.

1.43 SUMMERTIME

Note that we discard two copies of Z at the end since they were used as ¬ller to

make the last triplet.

1.45 LET™S ROLL

Note that the apostrophe is tacitly understood.

1.47 ALL EVIL DOERS FAIL

© 2003 by CRC Press LLC

226 Solutions to Odd-Numbered Exercises 1.49“1.65

1.49 TRUST HIM

1.51 SPLENDID

1.53 FORGED SIGNATURES

1.55 GOOD DEEDS PREVAIL

1.57 FILLED WITH REGRET

1.59 We use induction on n. If n = 2, then b2 > 2b1 > b1 , so S = {b1 , b2 } is a

superincreasing sequence. Assume that

S = {b1 , b2 , . . . , bn’1 },

which satis¬es

bj+1 > 2bj for 1 ¤ j ¤ n ’ 2

is a superincreasing sequence. Suppose that bn > 2bn’1 . Since S is a superin-

creasing sequence, then

n’2 n’1

bn > bn’1 + bn’1 > bn’1 + bj = bj .

j=1 j=1

Hence, by induction all such sets are superincreasing sequences.

Section 1.3

1.61 The key is MATH, and the plaintext is:

NEVER SAY NEVER AGAIN UNDER ANY

CIRCUMSTANCES WHATSOEVER

1.63 The key is FIX, and the plaintext is:

CRYPTOGRAPHERS MAKE VERY HIGH SALARIES

Note that we throw away two copies of Z tacked on the end as ¬ller to make up

the last trigram.

1.65 The key is FAIR, and the plaintext is:

JOHN NASH WAS A PIONEER OF GAME THEORY

Note that we throw away a Z tacked on the end as ¬ller to make up the last

trigram.S1

S1 John Forbes Nash (1928“) was born June 13, 1928 in Blue¬eld, West Virginia. He ¬rst

became interested in mathematics at the age of fourteen. He was inspired by Bell™s book Men

of Mathematics [18]. However, the mathematics that he learned at school bored him, and

coupled with his lack of social skills, caused his teachers to brand him as obtuse. In 1941,

Nash began the study of mathematics at Blue¬eld College where his mathematical talent

began to shine through to his educators. John won a Westinghouse scholarship and entered

Carnegie Tech (now Carnegie-Mellon University) in June 1945, where he intended to study

chemical engineering. Yet, his absorption into mathematics deepened, so he took courses in

tensor calculus and relativity, the latter being taught by the new head of department, John

Synge, who along with other professors in mathematics, saw Nash™s considerable talent and

© 2003 by CRC Press LLC

Solutions to Odd-Numbered Exercises 1.67“2.3 227

1.67 The key is GOLD, and the plaintext is:

ALL THAT GLITTERS IS NOT GOLD BUT

PLATINUM IS ALWAYS PRECIOUS

Note that we throw away a Z tacked on the end as ¬ller to make up the last

trigram.

Section 2.1

2.1 There are at most two solutions modulo a given prime. Thus, by the Chinese

Remainder Theorem there will be at most four modulo pq. We now exhibit

those four. We need only show that

±(xpa(q+1)/4 + yqa(p+1)/4 )

are square roots of a modulo pq since the other case has the same argument.

We have

(xpa(q+1)/4 + yqa(p+1)/4 )2 ≡ x2 p2 a(q+1)/2 + y 2 q 2 a(p+1)/2 ≡

x2 p2 z q+1 + y 2 q 2 z p+1 ≡ z 2 (x2 p2 z q’1 + y 2 q 2 z p’1 ) (mod n),

and since z p’1 ≡ 1 (mod p) and z q’1 ≡ 1 (mod q), then this is congruent to:

z 2 (x2 p2 + y 2 q 2 ) ≡ z 2 (xp + yq)2 ≡ z 2 ≡ a (mod n).

2.3 Alice selects m = 21 and sends w ≡ m2 ≡ 441 (mod n) to Bob. Bob selects c = 0

and sends it to Alice who computes r = 21, which gets sent back to Bob, who

computes r2 ≡ 441 ≡ w · tc (mod n). Thus we set a = 1 and execute another

A

round.

countenanced him to continue his mathematical journey. In 1948, he received a B.A. and an

M.A. in mathematics. In September 1948, he accepted a prestigious fellowship from Lefshetz,

head of the Mathematics Department at Princeton, to take up doctoral studies. During his

studies in 1949, he wrote a paper that would, forty-¬ve years later, earn him the Nobel prize

in economics. In 1950, he was granted his Ph.D. for a thesis called Non-Cooperative Games.

In the summer of that year, he was working for RAND Corporation, where he worked from

time to time over the later years. In 1952, he was teaching at MIT where he met Eleanor

Stier with whom he had a son on June 19, 1953. However, despite her persuasions, he did not

marry her. He did marry one of his students, Alicia Larde, in February 1957. By the end of

1958, with Alicia pregnant, he began a decline into schizophrenia. (The term Schizophrenia

was coined by Eugene Bleuler in 1908 to mean a “speci¬c type of alteration of thinking, feeling

and relation to the external world”.) An example of his descent into mental illness is given by

the following anecdote. One winter morning at MIT in 1959 he entered the lounge carrying

the New York Times and commented that the story in the upper left-hand corner of the

front page contained an enciphered message from extra-terrestrials, a message that only he

could decrypt. He saw hidden messages in everyday life that were symptoms of his delusions.

For decades, Nash was in and out of hospitals for treatment. Amazingly, his mathematical

output and academic success continued. By the early 1990s he had made a recovery from his

battle with the disease. In 1994, he won (jointly with Harsanyi and Selten) the Nobel Prize

in Economics for his research in game theory. By 1999, he was also honoured with the I. P.

Steele Prize by the American Mathematical Society for a “seminal contribution to research”.

For more on his life, the book: A Beautiful Mind [171] is recommended as is the movie of

the same name starring Russell Crowe who won a Golden Globe award on January 20, 2002,

for his penetrating portrayal of Nash™s life.

© 2003 by CRC Press LLC

228 Solutions to Odd-Numbered Exercises 2.3“2.23

Alice selects m = 12 and sends w = 144 to Bob. Bob selects c = 1, which Alice

subsequently uses to compute r ≡ 12 · 111 ≡ 1332 (mod n) and sends r to Bob,

who then B veri¬es that

r2 ≡ 757855 ≡ 144 · 12321 ≡ w · tc (mod n).

A

Since a is now set to zero, Bob accepts Alice™s proof.

Section 2.2

2.5 First, note that we have for each i = 0, 1, . . . , aj ’ 1,

aj ’1

(j)

b k pk

xi = (S1)

j

k=i

and

βi = ±xi ,

so

(p’1)/pi+1 i+1

≡ ±(p’1)xi /pj

j

βi (mod p).

Thus, it su¬ces to prove:

(j)

i+1

±(p’1)xi /pj ≡ ±(p’1)bi /pj

(mod p),

which holds precisely when

(j)

(p ’ 1)bi

(p ’ 1)xi

≡ (mod p ’ 1)

i+1

pj

pj

by Fermat™s Little Theorem. From (S1),

(j)

(p ’ 1)(xi ’ pi bi )

(j)

(p ’ 1)bi

(p ’ 1)xi j

’ = =

i+1 i+1

pj

pj pj

« «

aj ’1 aj ’1

p’1

bk pk ’ bi pi = (p ’ 1) bk pk’i’1 ,

(j) (j) (j)

j j j

i+1

pj k=i k=i+1

which is congruent to 0 modulo p ’ 1.

2.7 log2 (19) ≡ 35 (mod 37).

2.9 log3 (31) ≡ 1176 (mod 1579).

2.11 log3 (7) ≡ 1227 (mod 1721).

2.13 log10 (3) ≡ 813 (mod 1783).

2.15 log14 (5) ≡ 718 (mod 1871).

2.17 log23 (3) ≡ 490 (mod 2161).

2.19 log13 (2) ≡ 1300 (mod 2351).

2.21 log19 (3) ≡ 1402 (mod 2689).

2.23 log22 (3) ≡ 2314 (mod 3361).

© 2003 by CRC Press LLC

Solutions to Odd-Numbered Exercises 2.25“3.11 229

Section 2.3

2.25 69.

2.27 91.

2.29 7.

2.31 First, we determine d, the deciphering key, by using the Euclidean algorithm to

solve 69d + 166x = 1, and d = 77, x = ’32 yields the least positive value of d, so

we decipher via 8577 ≡ 12 (mod 167), 5077 ≡ 4 (mod 167), 9677 ≡ 18 (mod 167),

077 ≡ 0 (mod 167), and 2777 ≡ 6 (mod 167). Thus, via Table 1.2, we get the

letter equivalents of 12, 4, 18, 18, 0, 6, 4 to be

MESSAGE.

2.33 As in Exercise 2.31, we determine that d = 1053 and decipher to get plaintext

numerical equivalents 8, 13, 19, 0, 2, 19, which decrypt to

INTACT.

2.35 k = 2245.

2.37 k = 2902.

2.39 k = 871.

2.41 k = 1876.

2.43 k = 571.

2.45 k = 637.

2.47 k = 2425.

Section 3.1

3.1 By solving 7d + 16600y = 1, where (p ’ 1)(q ’ 1) = 16600, we get that d = 4743

with y = ’2. Thus, x = 8081.

3.3 As in Exercise 3.1 above, 7d + 33820y = 1, yields d = 9663, y = ’2, and x = 723.

3.5 As above, 7d + 1082400y = 1, yields d = 773143, y = ’5, and x = 315043.

3.7 As above, 7d + 3706560y = 1, yields d = 2647543, y = ’5, and x = 168536.

3.9 As above, 5d + 4726896y = 1, yields d = 3781517, y = ’4, and x = 4598308.

3.11 Since ed ≡ 1 (mod (p ’ 1)(q ’ 1)), there exists a g ∈ Z such that

ed = 1 + g(p ’ 1)(q ’ 1).

If p x, then by Fermat™s Little Theorem, xp’1 ≡ 1 (mod p). Hence,

xed ≡ x1+g(p’1)(q’1) ≡ x(xg(q’1) )p’1 ≡ x (mod p). (S2)

If p x, then (S2) holds again since x ≡ 0 (mod p). Hence,

xed ≡ x (mod p)

for any x. Similarly, xed ≡ x (mod q). Since p = q, xed ≡ x (mod n). Thus,

(xe )d ≡ xed ≡ x (mod n).

© 2003 by CRC Press LLC

230 Solutions to Odd-Numbered Exercises 3.13“3.27

d

3.13 Since x ≡ c ≡ cd (y e )d ≡ xy (mod n), then Mallory computes

x ≡ x y ’1 (mod n).

Section 3.2

3.15 Let ∈ N be the least value such that n < N +1 . Such an must exist since

n ∈ N and N > 1. Moreover, is unique. If n < N , then this contradicts the

minimality of + 1 in this regard. Thus, N ¤ n < N +1 since n > N .

3.17 Let k > be chosen, so that N k ≥ N +1 > n, and suppose that we have a

plaintext message blocks m, m1 such that m > n. Then if

me ≡ me (mod n),

1

we get, upon decryption m ≡ med ≡ med ≡ m1 (mod n). Thus, there is a

1

nonnegative integer r such that m = m1 + nr. However, m > n, so r > 0.

Hence, the same ciphertext block c ≡ me ≡ me (mod n) will yield (at least) two

1

di¬erent plaintext messages, m and m ’ nr, only one of which will be correct.

As an illustration, if k = 3 = + 1 in Example 3.10, then POW has 3-digit

base 26 numerical equivalent 15 · 262 + 14 · 26 + 23 = 10526, which enciphers as

10526701 ≡ 1420 (mod 1943). However, deciphering yields

142029 ≡ 811 (mod 1943),

and of the values 811 + 1943j for j = 0, 1, 2, 3, 4, 5, only j = 5 yields 10526.

3.19 Using the solution of Exercise 3.14, we know that p = 3371 and q = 3449.

3.21 As in Exercise 3.19, we have p = 4651 and q = 5003.

3.23 As in Exercise 3.19, we have p = 5657 and q = 6397.

3.25 As in Exercise 3.19, we have p = 9203 and q = 9533.

3.27 We write the cryptogram as 5-digit base 26 integers since = 4:

EGSIO = 4 · 264 + 6 · 263 + 18 · 262 + 8 · 26 + 14 = 1945750,

XEWXG = 23 · 264 + 4 · 263 + 22 · 262 + 23 · 26 + 6 = 10596228,

and

DPXMA = 3 · 264 + 15 · 263 + 23 · 262 + 12 · 26 + 0 = 1650428.

Then determine the deciphering key via ed+φ(n)x = 11d+10758720 = 1, which

gives d = 1956131 (for x = ’2). Thus, deciphering:

1945750d ≡ 111414 (mod n), 10596228d ≡ 213617 (mod n),

and 1650428d ≡ 301506 (mod n).

Also, since

111414 = 6 · 263 + 8 · 262 + 21 · 26 + 4 = GIVE

213617 = 12 · 263 + 4 · 262 + 0 · 26 + 1 = MEAB,

301506 = 17 · 263 + 4 · 262 + 0 · 26 + 10 = REAK,

we have the plaintext: GIVE ME A BREAK.

© 2003 by CRC Press LLC

Solutions to Odd-Numbered Exercises 3.29“3.39 231

3.29 As in Exercise 3.27, we write:

FENFL = 5 · 264 + 4 · 263 + 13 · 262 + 5 · 26 + 11 = 2364113,

PLNMZ = 15 · 264 + 11 · 263 + 13 · 262 + 12 · 26 + 25 = 7057101,

and

XLMPS = 23 · 264 + 11 · 263 + 12 · 262 + 15 · 26 + 18 = 10712304.

Thus, deciphering:

2364113d ≡ 2122640 (mod n), 7057101d ≡ 199958 (mod n),

and 10712304d ≡ 339408 (mod n),

and since,

2122640 = 4 · 263 + 16 · 262 + 20 · 26 + 0 = EQUA

199958 = 11 · 263 + 9 · 262 + 20 · 26 + 18 = LJUS,

339408 = 19 · 263 + 8 · 262 + 2 · 26 + 4 = TICE,

we have the plaintext: EQUAL JUSTICE.

3.31 As above:

BOTDT = 1 · 264 + 14 · 263 + 19 · 262 + 3 · 26 + 19 = 715981,

and

ICBYJ = 8 · 264 + 2 · 263 + 1 · 262 + 24 · 26 + 9 = 3692269,

and deciphering:

715981d ≡ 93634 (mod n), and 3692269d ≡ 321207 (mod n).

Then,

93634 = 5 · 263 + 8 · 262 + 13 · 26 + 8 = FINI

321207 = 18 · 263 + 7 · 262 + 4 · 26 + 3 = SHED,

so the plaintext is FINISHED.

Section 3.3

3.33 (±b )p’1’a = 32409’1’6 ≡ 379 (mod 409), and

(±b )’a m±ab ≡ 379 · 12 ≡ 49 = m (mod 409).

3.35 (±b )p’1’a = 512941’1’14 ≡ 864 (mod 941), and

(±b )’a m±ab ≡ 864 · 303 ≡ 194 = m (mod 941).

3.37 (±b )’a = (3, 3, 2)’44 = (1, 4, 1), so

±’ab m±ab = (1, 4, 1)(0, 2, 1) = (4, 4, 4) = m.

3.39 (±b )’a = (0, 3, 1)’24 = (1, 0, 0), so

±’ab m±ab = (1, 0, 0)(4, 0, 4) = (0, 1, 0) = m.

© 2003 by CRC Press LLC

232 Solutions to Odd-Numbered Exercises 3.41“3.59

3.41 Mallory intercepts meA and encrypts with his own enciphering key meA eM . Then

he sends it back to Alice, impersonating Bob. Alice, thinking it is Bob, sends

back meA eM dA = meM , which Mallory intercepts. He then easily decrypts via

his deciphering key to get meM dM = m. This demonstrates how easily the

system is compromised by such an attack and why it requires more security, in

terms of authentication of communicating entities, if it is to be used.

3.43 Bob has public key (p, ±, ±a ) = (15485863, 6, 7776), which Alice obtains. She

converts the English plaintext via Table 1.2 on page 3 to the numerical equiv-

alents: 19, 14, 3, 0, 24. Since 265 < p < 266 , she can represent the plaintext

message as a single 5-digit base 26 integer:

19 · 264 + 14 · 263 + 3 · 262 + 0 · 26 + 24 = 8930660.

She ¬rst computes ±b = 669 ≡ 13733130 (mod p), then

m±ab ≡ 8930660 · 777669 ≡ 4578170 (mod p).

She sends c = (13733130, 4578170) to Bob. He uses his private key to compute

(±b )p’1’a ≡ 137331301548585863’1’5 ≡ 2620662 (mod p)

and

(±b )’a m±ab ≡ 2620662 · 4578170 ≡ 8930660 ≡ m (mod p),

and using Table 1.2, he converts back to the English plaintext.

Section 3.4

3.45 Since each entity needs both the enciphering key and deciphering key to be kept

secret, this is “n choose 2”, namely, the binomial coe¬cient:

n

= n!/((n ’ 2)!2!) = n(n ’ 1)/2.

2

3.47 Since

(k )d ≡ 4019872802607 ≡ 234561 (mod n),

then k = (2, 3, 4, 5, 6, 1), from which we deduce that k’1 = (6, 1, 2, 3, 4, 5), so

k’1 (c) = (18, 8, 11, 21, 4, 17) = SILVER.

3.49 (k )d ≡ 1525853802607 ≡ 421653 (mod n), k = (4, 2, 1, 6, 5, 3), and k’1 =

(3, 2, 6, 1, 5, 4). Thus, k’1 (c) = (1, 0, 3, 9, 14, 1) = BAD JOB.

3.51 (k )d ≡ 7155548802607 ≡ 624315 (mod n), k = (6, 2, 4, 3, 1, 5), and k’1 =

(5, 2, 4, 3, 6, 1), so k’1 (c) = (5, 17, 8, 4, 13, 3) = FRIEND.

3.53 (k )d ≡ 371155802607 ≡ 214365 (mod n), k = (2, 1, 4, 3, 6, 5), and k’1 =

(2, 1, 4, 3, 6, 5), so k’1 (c) = (12, 14, 13, 8, 4, 18) = MONIES.

3.55 (k )d ≡ 8182887802607 ≡ 462135 (mod n), k = (4, 6, 2, 1, 3, 5), and k’1 =

(4, 3, 5, 1, 6, 2), so k’1 (c) = (0, 17, 0, 1, 8, 2) = ARABIC.

3.57 (k )d ≡ 4125753802607 ≡ 246351 (mod n), k = (2, 4, 6, 3, 5, 1), and k’1 =

(6, 1, 4, 2, 5, 3), so k’1 (c) = (7, 8, 19, 12, 0, 13) = HITMAN.

3.59 (k )d ≡ 1968543802607 ≡ 613245 (mod n), k = (6, 1, 3, 2, 4, 5), and k’1 =

(2, 4, 3, 5, 6, 1), so k’1 (c) = (3, 0, 17, 10, 4, 17) = DARKER.

© 2003 by CRC Press LLC

Solutions to Odd-Numbered Exercises 3.61“4.9 233

3.61 (k )d ≡ 7066510802607 ≡ 415263 (mod n), k = (4, 1, 5, 2, 6, 3), and k’1 =

(2, 4, 6, 1, 3, 5), so k’1 (c) = (25, 4, 1, 17, 0, 18) = ZEBRAS.

Section 4.2

e

4.1 Let p|n be prime and set c = m(n’1)/q where q is a prime, e ∈ N and q e ||b. There-

e e’1

fore, since gcd(m(n’1)/q ’ 1, n) = 1, cq ≡ 1 (mod p), but cq ≡ 1 (mod p).

Thus, ordp (c) = q e , so q e (p ’ 1) by Proposition C.19. Since q was arbitrarily

√

chosen, p ≡ 1 (mod b). For the last assertion of the exercise, assume b > n ’

√

1, but n is composite. Let p be the smallest prime dividing n. Then p ¤ n, so

√ √

n ≥ p > b ≥ n, a contradiction. Hence, n is prime.

4.3 If n is prime, then by Exercise 4.1 we have the result with m = mq for all q (n’1).

Conversely, if such mq exist, then by the Chinese Remainder Theorem, we may

¬nd a solution x = m to the system of congruences

x ≡ mq (mod q e )

for all primes q such that q e ||(n ’ 1). Thus, the result now follows from Exercise

4.1.

4.5 If Fn is prime, the result follows from Exercise 4.4. Conversely, if p be a prime

Fn ’1 Fn ’1

≡ ’1 (mod p), so 3 2 ≡ ’1 (mod p). If b =

divisor of Fn , then 3 2

ordp (3), then b (Fn ’ 1) by Proposition C.19. Thus b = 2m for some integer

m with 1 ¤ m ¤ 2n . Suppose that m = 2n . Then

2n ’1 2n ’m’1

m

’1 ≡ 32 = (32 )2 ≡ 1 (mod p),

so p = 2, a contradiction. Hence,

n

ordp (3) = 22 = Fn ’ 1.

By Fermat™s Little Theorem and Proposition C.19, ordp (3)|p’1. Hence, p = Fn .

4.7 Assume ¬rst that (pj ’ 1) (n ’ 1) for all j = 1, 2, . . . , r. If gcd(a, n) = 1, then

gcd(a, pj ) = 1 for all j = 1, 2, . . . , r. Thus, apj ’1 ≡ 1 (mod pj ), by Fermat™s

Little Theorem. Since n ’ 1 = mj (pj ’ 1) for some mj ∈ N,

an’1 ≡ amj (pj ’1) ≡ (apj ’1 )mj ≡ 1 (mod pj ).

r

Hence, an’1 ≡ 1 (mod namely, an’1 ≡ 1 (mod n).

j=1 pj ),

≡ 1 (mod n) for each a with gcd(a, n) = 1. In

n’1

Conversely, suppose that a

particular, if a is a primitive root modulo p, for any prime divisor p of n, then

(p ’ 1) (n ’ 1), by Proposition C.19 on page 216.

Section 4.3

4.9 If b2 ≡ 1 (mod pa ), then pa (b + 1)(b ’ 1). Notice that p cannot divide both

(b’1) and b+1 since that would mean b’1 ≡ b+1 (mod p). so ’1 ≡ 1 (mod p),

forcing p = 2, a contradiction. Thus, either pa (b ’ 1) or pa (b + 1). In other

words, b ≡ ±1 (mod pa ). Conversely, if b ≡ ±1 (mod pa ), then b2 ≡ 1 (mod pa ).

© 2003 by CRC Press LLC

234 Solutions to Odd-Numbered Exercises 4.11“4.27

4.11 They are both Carmichael numbers for the following reasons, using Exercise 4.7.

For n = 8911 = 7 · 19 · 67, each of 6, 18 and 66 divide n ’ 1. For n = 10585 =

5 · 29 · 73, all of 4, 28, and 72 divide n ’ 1. Also, 10585 is an Euler pseudoprime

to base 2 since

2

≡ 25292 (mod 10585).

10585

4.13 By Exercise 4.8, E(n) is a subgroup of (Z/nZ)— . Since the cardinality of (Z/nZ)—

is φ(n) by Example C.17, and since n is composite, then E(n) = (Z/nZ)— by

Exercise 4.12, so E(n) is a proper subgroup of (Z/nZ)— . Thus, by Example

C.17, |E(n)| φ(n). Hence, |E(n)| ¤ φ(n)/2 since |E(n)| = φ(n) and φ(n) is

even when n > 2.

4.15 Since, by repeated squaring, we get 214670 ≡ ’1 (mod 29341) and ( 29341 ) = ’1,

2

then 29341 is an Euler pseudoprime to base 2 since 29341 = 13 · 37 · 61.

4.17 As above, we get, 231372 ≡ 1 ≡ ( 62745 ) (mod 62745), and since 62745 = 3 · 5 ·

2

47 · 89, then 62745 is an Euler pseudoprime to base 2.

4.19 Let n = 2821. Then by the repeated squaring method, we determine that

31410 ≡ 1 ≡ ( 2821 ) (mod 2821). Since 2821 = 7 · 13 · 31, then 2821 is an Euler

3

pseudoprime to base 3. Moreover, since 6, 12, and 30 all divide n ’ 1 = 2820,

then by Exercise 4.7, 2821 is a Carmichael number.

Section 4.4

4.21 If n ∈ spsp(a), then ad ≡ 1 (mod n) for some divisor d of n ’ 1. Thus,

(ad )(n’1)/d ≡ 1(n’1)/d ≡ 1 (mod n), whence n ∈ psp(a).

4.23 Let g = gcd((x ’ y), n). We need only show that g = 1, n. If g = 1, then

since n (x ’ y)(x + y), we must have n (x + y), contradicting the hypothesis

that x ≡ ’y (mod n). If g = n, then x ≡ y (mod n), a contradiction to the

hypothesis that x ≡ y (mod n). Hence, since g n, it is a nontrivial factor of it.

4.25 Each is a strong pseudoprime to base 2 for the following reasons. For n = 15841,

n ’ 1 = 25 · 495 and 2495 ≡ 1 (mod n). For n = 29341, n ’ 1 = 22 · 7335 and

22·7335 ≡ ’1 (mod n), while 27335 ≡ ±1 (mod n). For n = 52633, n ’ 1 = 23 ·

6579 and 26579 ≡ 1 (mod n). For n = 252601, n ’ 1 = 23 · 31575, and we have

both 22·31575 ≡ ’1 (mod n) and 231575 ≡ ±1 (mod n).

They are all Carmichael numbers for the following reasons, using Exercise 4.7.

For n = 15841 = 7 · 31 · 73, all of 6, 30, and 72 divide n ’ 1. For n = 29341 =

13 · 67 · 61, all of 12, 66, and 60 divide n ’ 1. For n = 52633 = 7 · 73 · 103, all

of 6, 72, and 102 divide n ’ 1. For n = 252601 = 41 · 61 · 101, all of 40, 60, and

100 divide n ’ 1.

4.27 Let n be a Carmichael number that is a strong pseudoprime to every base a

prime to n. Furthermore, suppose that n ’ 1 = 2t m where t ∈ N and m is odd.

Let a be a primitive root modulo any prime p dividing n. If am ≡ 1 (mod n),

then am ≡ 1 (mod p). However, since a is a primitive root modulo p, then by

Proposition C.19, (p ’ 1) m, a contradiction. Suppose that there exists a

j j+1

value of j such that 0 ¤ j ¤ t ’ 1, and a2 ≡ ’1 (mod n). Then a2 ≡1

m m

(mod p), so (p ’ 1) (2j+1 m) as above. Thus,

j j+1 j+1

’1 ≡ a2 m

≡ (a(p’1)/2 )(2 m)/(p’1)

≡ (’1)2 m

≡ 1 (mod p),

© 2003 by CRC Press LLC

Solutions to Odd-Numbered Exercises 4.27“5.5 235

a contradiction since p is odd. Hence, no such Carmichael number can exist.

4.29 For a = 2 we have n ’ 1 = 24 · 35; 235 ≡ 263 (mod 561); 22·35 ≡ 166 (mod 561);

24·35 ≡ 67 (mod 561); and 28·35 ≡ 1 (mod 561). Hence, 561 is composite by the

strong pseudoprimality test.

4.31 Since 120 = 23 · 15 and 315 ≡ 1 (mod 121), then 121 is a strong pseudoprime to

base 3.

4.33 Since 24 = 23 · 3; 73 ≡ 18 (mod 25); and 182 ≡ ’1 (mod 25), then 25 is a strong

pseudoprime to base 7.

4.35 Since a(n’1)/2 ≡ ( n ) (mod n), then an’1 ≡ 1 (mod n).

a

4.37 If n = pb ∈ psp(a), and n ’ 1 = 2t m where m is odd, then

(a(n’1)/2 )2 ≡ 1 (mod n),

so by Exercise 4.9, a(n’1)/2 ≡ ±1 (mod n). If a(n’1)/2 ≡ 1 (mod n), and n ’ 1

is even we repeat the above argument to get a(n’1)/4 ≡ ±1 (mod n) and keep

repeating it which ultimately achieves that n ∈ spsp(a). The converse follows

from Exercise 4.21.

Section 5.1

a

5.1 We use induction on a to show that x2 ≡ 1 (mod 2a+2 ) for all odd x ∈ Z. If

a = 1, then it is easy to see that x2 ≡ 1 (mod 8), so we may assume that

a’1

x2 ≡ 1 (mod 2a+1 ).

a

Therefore, x2 = (1 + 2a+1 t)2 for some t ∈ Z. In other words,

a

x2 ≡ 1 (mod 2a+2 ).

a

5.3 Let n = r pj j be a prime factorization of n, with p1 = 2. By Exercise 5.2,

j=1

»(n) is a universal exponent for n. We must prove that it is minimal. Let gj be

a

a primitive root modulo pj j for each j = 2, 3, . . . , r, which exist by the Primitive

Root Theorem C.21 on page 216. Thus, by the Chinese Remainder Theorem

C.13, the system of congruences

a

x ≡ 3 (mod 2a1 ), and x ≡ gj (mod pj j ), (2 ¤ j ¤ r),

has a solution x = a which is unique modulo n. If am ≡ 1 (mod n) for some

a

m ∈ N, then am ≡ 1 (mod pj j ) for each j, so ordpaj (a) m, by Proposition C.19.

j

a

Thus, since a satis¬es the r congruences above, then »(pj j ) = ordpaj (a). Hence,

j

a

»(pj j ) m for all j. Therefore, »(n) m. We have shown that »(n) = ordn (a).

5.5 We have e = 25 · 405. Choose a = 2 and compute 2405 ≡ 1 (mod n), so we go to

step (1) and choose another base, a = 3. We compute

x0 ≡ 3405 ≡ 2820 (mod n),

then x1 ≡ 28202 ≡ 218 (mod n), and x2 ≡ 2182 ≡ 1 (mod n). Since we know

that x1 ≡ ±1 (mod n), then gcd(217, 15841) = 217 is a factor of n. Indeed

n = 217 · 73.

© 2003 by CRC Press LLC

236 Solutions to Odd-Numbered Exercises 5.7“5.19

5.7 Since e = 22 · 26643, we may try a = 2 and compute,

x0 ≡ 226643 ≡ 25719 ≡ ±1 (mod n),

then x1 ≡ 257192 ≡ 1 (mod n). Hence, gcd(25718, 107381) = 167 is a factor of

n. In fact, n = 167 · 643.

5.9 Since e = 23 · 1831595, then we choose a base a = 3 and compute as follows where

all congruences are assumed modulo n.

x0 ≡ 31831595 ≡ 10750120; x1 ≡ 107501202 ≡ 13251402;

and x2 ≡ 132514022 ≡ 1. Since x1 ≡ ±1, then gcd(n, 13251401) = 3371, and

n = 3371 · 4349.

5.11 Since e = 2 · 223713, then we choose a = 2 and compute the following where all

congruences ae modulo n. Since 2223713 ≡ 1, we need a new base. We select

a = 3 and compute

x0 ≡ 3223713 ≡ 23944214; x1 ≡ 239442142 ≡ 1,

and since x0 ≡ ±1, then gcd(x0 ’ 1, n) = 7103 n. Indeed n = 6679 · 7103.

5.13 We have that e = 23 · 1600875 and we select a = 2 to compute the following

where all congruences are modulo n. Since x0 ≡ 21600875 ≡ 76859538 ≡ ’1, we

must choose a new base a = 3.Then

31600875 ≡ 44940756; x1 ≡ x2 ≡ 9649071; x2 ≡ x2 ≡ 1;

0 1

and since x1 ≡ ±1, then gcd(x1 ’ 1, n) = 8539 n, and n = 8539 · 9001.

5.15 Since 3 is a primitive root of F6 = 18446744073709551617 if n is prime,

then we know that 3e/2 ≡ ’1 (mod n) if indeed it is prime. By repeated

squaring, we calculate that 3e/2 ≡ 3653528722731049759 ≡ ±1 (mod n), so

gcd(3653528722731049758, n) = 274177 n. Indeed we now have factored the

sixth Fermat number since

F6 = 274177 · 67280421310721.

Section 5.2

5.17 We check that gcd(aj ’ 1, n) = 1 for all j = 1, 2, . . . , 6, then

a7 ≡ 86977 ≡ 4747 (mod n),

gcd(4746, n) = 113, and n = 113 · 107. Note that 112 = 24 · 7 is B-smooth.

5.19 We compute that gcd(aj ’ 1, n) = 1 for j = 1, 2, . . . , 7. Then we check that

a8 ≡ 324948 ≡ 12320 (mod n),

gcd(12319, 37151) = 97, and n = 97 · 383. Here 96 = 25 · 3 is B-smooth.

© 2003 by CRC Press LLC

Solutions to Odd-Numbered Exercises 5.21“5.23 237

5.21 Randomly select a1 = 614, then

b1 ≡ 6142 ≡ 840 ≡ 23 · 3 · 5 · 7 (mod n),

so b1 is 7-smooth, and we keep it. Randomly select a2 = 51 and compute

512 ≡ 2601 (mod n), which is not 7-smooth since it is divisible by only 3 from

S4 and is not a perfect power of 3, so we discard it. Randomly select a2 = 1009

and compute

b2 ≡ 10092 ≡ 2 · 3 · 53 (mod n),

which is then saved. Randomly select a3 = 45 and compute

b3 ≡ 452 ≡ 34 · 52 (mod n),

which is saved. Randomly select a4 = 56 and compute

b4 ≡ 562 ≡ 26 · 72 (mod n),

and it is kept. Randomly select a5 = 100 and compute 1002 ≡ 1451 (mod n),

which is not divisible by any of the primes in S4 so it is discarded. Randomly

select a5 = 983 and compute

b5 ≡ 9832 ≡ 22 · 32 · 7 (mod n),

and save it. We have reached r + 1 = 5 such bi , so we now search for the subset

T. Notice that b3 and b4 are squares themselves. However, for b3 , x = 45,

y = 32 · 5 and x ’ y = 0. Similarly for b4 , the same thing happens, so we need

another subset. We see that if we choose T = {1, 2, 5}, then we get

bi ≡ 6142 · 10092 · 9832 ≡ 26 · 34 · 54 · 72 (mod n).

i∈T

Thus,

x≡ ai ≡ 614 · 1009 · 983 ≡ 6043 (mod n),

i∈T

and

y ≡ 23 · 32 · 52 · 7 ≡ 4051 (mod n).

Thus x2 ≡ y 2 (mod n) and

gcd(x ’ y, n) = gcd(6043 ’ 4051, 8549) = gcd(1992, 8549) = 83.

In fact, 8549 = 83 · 103. Of course, sometimes luck plays a role. Suppose that

the ¬rst random choice that we made was a1 = 744. Then since

7442 ≡ 28 · 52 (mod n)

and gcd(744 ’ 24 · 5, n) = gcd(664, 8549) = 83, then we have a quick and simple

factorization. However, one cannot rely on luck alone, and this is unlikely to

happen for the large numbers that are used in practice.

Section 5.3

5.23 6P = (2238, 2448)

© 2003 by CRC Press LLC

238 Solutions to Odd-Numbered Exercises 5.25“6.1

5.25 Since each point jP = (xj , yj ) on E(Z/nZ) has at most n2 possibilities for any

j, then there exists a value k such that jP = kP .

5.27 Let = qk + s where 0 ¤ s < k. Since kP = o, then qkP = o. Therefore, by

Exercise 5.26, ( ’ qk)P = sP = o. However, since s < k and k is the least

positive such value, then s = 0, and we have proved that k .

5.29 2P ≡ (9’1 , ’82 · 27’1 ) ≡ (442, 2501) (mod n). However, to compute 6P we

must compute 4P ≡ (’26567/242064, 352876013/119095488) ≡ o (mod n) since

gcd(242064, 3977) = 41, and indeed 3977 = 41 · 97.

5.31 2P ≡ (4055, 10810) (mod n) and 4P ≡ (363, 16880) (mod n), but

18984764783665 82719639550389910598

6P ≡ ≡ o (mod n)

,

25724631321 4125947892943869

since gcd(25724631321, 18247) = 71, and 18247 = 71 · 257.

5.33 We compute that 2P ≡ (4268, 11378) (mod n) and 4P ≡ (9877, 27743) (mod n),

but 6P is as in Exercise 5.31 and gcd((25724631321, 38411) = 71. We have

factored n = 38411 = 71 · 541.

Section 5.4

5.35 Since (a) holds, then

√ √ √

k

2(1/2k) i=1 (1/k)

k

2n 2n 2n

2

a≈ = = ,

M M M

i=1

so the ¬rst condition is satis¬ed in (5.11). Since b2 ≡ n (mod a2 ) given the

solution to the system of congruences via the Chinese Remainder Theorem,

then a2 (b2 ’ n), so (b2 ’ n)/a2 = c ∈ Z, which is the second condition. If

b ≥ a2 /2, then replace b by b ’ a2 , and we have |b| < a2 /2, which is the last

condition.

For the choices given, we set a = 11 · 17 = 187, and compute b1 = 23 since

232 ≡ n (mod 112 ) and b2 = 79 since 792 ≡ n (mod 172 ). Then we use the

Chinese Remainder Theorem to solve b ≡ 23 (mod 112 ) and b ≡ 79 (mod 172 )

for b = 11639. Since b2 ≡ 31384 ≡ n (mod a2 ), then c = (b2 ’ n)/a2 = 1802.

Section 6.1

r r

6.1 Let m1 = si /r and m2 = j=1 tj /r. First we observe that,

i=1

r r r

1

var({si }r ) 2

s2 + m2 =

(si ’ m1 ) /r = ’ 2m1

= si

i=1 i 1

r

i=1 i=1 i=1

r r r r r r

1 1 1

s2 s2 s2 ’m2 ,

’ 2m1 ’ m1

si + m1 si = si =

i i i 1

r r r

i=1 i=1 i=1 i=1 i=1 i=1

var({tj }r ) var({si }i=1 +{tj }j=1 ).

r r

and a similar result holds for and for There-

j=1

fore, if we let

r r r r

1 1

m= 2 (si + tj ) = 2 r si + r tj = m1 + m2 ,

r r

i=1 j=1 i=1 j=1

© 2003 by CRC Press LLC

Solutions to Odd-Numbered Exercises 6.1“6.13 239

then

r r

1

var({si }r {tj }r ) (si + tj )2 ’ (m1 + m2 )2 =

+ =2

i=1 j=1

r i=1 j=1

r r r

1

s2 r t2 ’ (m1 + m2 )2 =

+ 2si tj +

i j

r2 i=1 j=1 j=1

r r r r

1 1 2

s2 t2 tj ’ m2 ’ m2 ’ 2m1 m2 =

+ +2 si

i j 1 2

r r r

i=1 j=1 i=1 j=1

r r

1 1

s2 ’ m2 + t2 ’ m2 = var({si }r ) + var({tj }r ).

i 1 j 2 i=1 j=1

r r

i=1 j=1

Also, var({si }r ) = 0 = var({si }r ) for {si }ri=1 = {4, 4, 4, 4, }, since

i=1 i=1

m = 4, and for {tj }r = {5, 10, 50, 100}, var({tj }r ) = 23275/16 and

j=1 j=1

var({tj }r ) = 38.14.

j=1

Section 6.2

6.3 Using the Chinese remainder theorem, there is a solution to x ≡ ci ≡ m3 (mod ni )

for each i = 1, 2, 3. Since m3 < n1 n2 n3 , then x = m3 . By computing the cube

root of the integer x, we retrieve m.

6.5 We solve 1 = ed + φ(n)x = 5d + 5903364x and get d = 1180673 for x = ’1.

6.7 As above, we solve 1 = ed + φ(n)x = 3d + 20734288x and get d = 13822859 for

x = ’2.

6.9 As above, we solve 1 = ed + φ(n)x = 3d + 56579188x and get d = 37719459 for

x = ’2.

6.11 Since d < φ(n), and 0 < m ¤ e, then Eve can multiply ed ’ m(n ’ p ’ q + 1) = 1

by p and reduce modulo 2n/4 to get

(ed)p ’ mp(n ’ p + 1) + mn ≡ p (mod 2n/4 ),

which may be rewrite as

mnp2 ’ (mn + m + 1 + ed)p + mn ≡ 0 (mod 2n/4 ).

Since Eve knows n/4 of the least signi¬cant bits of d, she knows ed modulo 2n/4 .

Now Eve can try each of the possible values of p and use Theorem 6.8 to test

each one. Hence, after at most e log2 e trials, she has factored n.

Section 6.3

6.13 By Exercise 5.2 on page 95, a»(n)+1 ≡ a (mod n) for all a prime to n. If p n,

then we need only show that p divides a»(n)+1 ’ a for each prime dividing n

since n is squarefree. However, a»(n)+1 ≡ a ≡ 0 (mod p) for each such a. This

completes the proof. However, if n is not squarefree, then this does not hold in

general. For instance, if n = 12, then »(12) = 2 and

10»(12)+1 ≡ 103 ≡ 4 ≡ 10 (mod 12).

© 2003 by CRC Press LLC

240 Solutions to Odd-Numbered Exercises 6.15“7.9

6.15 Since modular exponentiation is computationally easy using, for instance, the

repeated squaring method, but ¬nding f ’1 (y) ≡ y d (mod n) is computationally

infeasible without knowledge of d, then this is a one-way, trapdoor function with

d as the trapdoor. See the discussion in Section 5.1, especially the discussion at

the bottom of page 94.

6.17 Use the extended Euclidean algorithm C.5 on page 213 on e and 2n to ¬nd

integers d and m such that ed + 2n m = 1. Then destroy all records of p, q,

n , and m , and keep d as the private key (trapdoor). Thus, me ≡ c (mod n) is

the enciphering function and cd ≡ m (mod n) is the deciphering function where

ed ≡ 1 (mod φ(n)).

Section 6.4

6.19 We have that n = 2AB + 1 = 307 and mn’1 ≡ 2306 ≡ 1 (mod n) and

gcd(m(n’1)/p , n) = gcd(218 ’ 1, 307) = 1, so 307 is a provable prime and since

307 = (100110011)2 , it is a 9-bit prime.

6.21 Since n = 2AB + 1 = 2311, and 22310 ≡ 1 (mod n) with gcd(2462 ’ 1, n) = 1,

then 2311 is a provable prime and 2311 = (100100000111)2 , which is 12 bits so

we are done.

6.23 (a) Since f : (Z/nZ)— ’ (Z/nZ)— , then there are only ¬nitely many possibilities

for sa , so eventually sa+1 ≡ sj for some j ¤ .

j’1

(b) f (2) = (8, 512, 161, 2), so = 4 which is the answer to (c).

Section 7.1

7.1 Alice is identi¬ed since,

δ ≡ ±y v r ≡ ±k+er v r ≡ ±k+er ±’er ≡ ±k ≡ γ (mod p).

7.3 Alice computes y ≡ k + er ≡ 1001 + 151 · 512 (mod 1559), and Bob computes

δ ≡ ±y v r ≡ 49363 · 460512 ≡ 502 ≡ γ ≡ 501 (mod 3119),

so Bob rejects Alice™s proof of identity.

7.5 As above, y ≡ 4 + 8 · 3 ≡ 11 (mod 17), and

δ ≡ 366811 · 45083 ≡ 4104 ≡ γ (mod 7481),

so Bob accepts Alice™s proof of identity.

7.7 In step (9), Bob must verify Trent™s signature. However, since v = v then s = s,

so verT (k) ((IA , v , s )) = 0, and Bob rejects the proof of identity.

7.9 Alice computes

y1 ≡ k1 + e1 r ≡ 10 + 25 · 8 ≡ 1 (mod q)

y2 ≡ k2 + e2 r ≡ 9 + 27 · 8 ≡ 5 (mod q),

and sends them to Bob who computes

δ ≡ ±11 · ±22 · v r ≡ 4431 · 25415 · 17688 ≡ 2490 ≡ γ (mod p),

y y

so he accepts Alice™s proof of identity.

© 2003 by CRC Press LLC

Solutions to Odd-Numbered Exercises 7.11“7.35 241

7.11 As above,

y1 ≡ 1007 + 998 · 256 ≡ 1144 (mod q)

y2 ≡ 506 + 5 · 256 ≡ 1786 (mod q).

Then Bob computes,

δ ≡ 251144 · 11331786 · 771256 ≡ 3009 ≡ γ (mod p),

so Bob rejects Alice™s proof of identity.

Section 7.2

7.13 Since sigk (m)e ≡ 15971133 ≡ 911 ≡ m (mod 20497), then Bob accepts Alice™s

signature.

7.15 Since sigk (m)e ≡ 317905611 ≡ 116106 ≡ 1111 ≡ m (mod 58320), then Bob

rejects Alice™s signature.

7.17 We have, sd z ’1 ≡ z ed md z ’1 ≡ zmd z ’1 ≡ md (mod n), since ed ≡ 1 (mod φ(n)).

Alice does not know if she is signing away her life savings or confessing to a

murder she did not commit. Hence, for her to sign blindly requires safeguards.

7.19 δ ≡ y β β γ ≡ 11227 227207 ≡ 25 (mod p) and σ ≡ ±m ≡ 52 ≡ 25 (mod p), so it is

accepted.

7.21 As above, δ ≡ 711330 33037 ≡ 495 (mod p), and σ ≡ 11191 ≡ 495, so it is accepted.

7.23 We have,

’1

y β1 β1 1 ≡ ±aβ1 ±(r1 +ar2 )γ1 ≡ ±aβ1 ±(r1 +ar2 )(’β1 r2

γ )

≡

’1 ’1

±aβ1 ±’β1 r1 r2 ’β1 a

≡ ±’β1 r1 r2 ≡ ±γ1 r1 ≡ ±m1 (mod p).

7.25 Since β, γ, and m are known, then knowledge of r means that he may compute

a ≡ (m ’ rγ)β ’1 (mod p ’ 1).

7.27 When Alice sends her valid signature to Bob, we have:

δ ≡ ±γ y h ≡ ±r+eh ±’eh ≡ ±r ≡ β (mod p).

7.29 Bob computes δ ≡ ±γ · y h ≡ 12206 · 1456101 ≡ 913 ≡ β (mod p), so he accepts

Alice™s signature.

7.31 As above, Bob computes δ ≡ 107925 · 42721 ≡ 1217 ≡ β (mod p), so he accepts.

Section 7.3

7.33 Since we have that A is unique to Alice and

f Ak ≡ g11 g22 (g11 g22 )k ≡ g11 +ke1 g22 +ke2 ≡ g11 g22 (mod p),

f f e e f f

then Alice™s identity is indeed veri¬ed.

7.35 Since only the bank knows x, then only the bank can send a response satisfying

both

±r ≡ ±xc+w ≡ (±x )c ±w ≡ hc y2 (mod p)

and

Ar ≡ Axc+w ≡ (Ax )c Aw ≡ mc y3 (mod p).

© 2003 by CRC Press LLC

242 Solutions to Odd-Numbered Exercises 7.37“8.5

7.37 By Exercise 7.34, XY ≡ y1 (mod p), and y1 ≡ Ax (mod p) with A ≡ 1 (mod p)

by step (1) of the protocol for opening Alice™s account. Also, x ∈ (Z/qZ)— , by

step (3) of the setup stage, so x ≡ 0 (mod q), which completes the proof.

Section 8.1

8.1 First we observe that

xi ’ x

≡ 0 (mod p)

Kk (xi ) =

xk ’ x

1¤ ¤t

=k

if i = k since Kk (xi ) has a factor (xi ’ xi )/(xk ’ xi ). Also,

Kk (xk ) ≡ 1 (mod p)

since all factors are of the form (xk ’ x )/(xk ’ x ) = 1. We note that

1/(xk ’ x ) ≡ (xk ’ x )’1 (mod p),

so as long as k = , such inverses exist. Therefore,

t

f (xi ) ≡ mk Kk (xi ) ≡ mi (mod p)

k=1

for i = 1, 2, . . . , t.

8.3 Although g(x) produces the same values, it does so at only one of the three values

of xi that f (x) produces them. We have

f (1) ≡ g(1) ≡ 7 (mod p),

but

g(2) ≡ f (3) ≡ 1407 (mod p), g(3) ≡ f (5) ≡ 334 (mod p).

and

Note that

(x ’ 2)(x ’ 3) (x ’ 1)(x ’ 3) (x ’ 1)(x ’ 2)

g(x) ≡ 7 + 1407 + 334 (mod p),

(1 ’ 2)(1 ’ 3) (2 ’ 1)(2 ’ 3) (3 ’ 1)(3 ’ 2)

whereas,

(x ’ 3)(x ’ 5) (x ’ 1)(x ’ 5) (x ’ 1)(x ’ 3)

f (x) ≡ 7 + 1407 + 334 (mod p),

(1 ’ 3)(1 ’ 5) (3 ’ 1)(3 ’ 5) (5 ’ 1)(5 ’ 3)

and, of course, f (0) ≡ 3301 (mod p), while g(0) ≡ 2856, which is not the original

message.

8.5 We calculate p(x) for x = 1, 3, 5 and get (1, 488), (3, 2400), and (5, 1881). Then

we compute the Lagrange interpolation formula to get,

2431 2 4343 11037

f (x) = ’ x’

x+ .

8 2 8

Since 8’1 ≡ 529 (mod p), 2’1 ≡ 2116 (mod p), and

’2431 · 529 ≡ 225; 4343 · 2116 ≡ 56; ’11037 · 529 ≡ 207,

all modulo p, then we recover the message at f (0) ≡ p(0) ≡ 207.

© 2003 by CRC Press LLC

Solutions to Odd-Numbered Exercises 8.7“8.15 243

8.7 As above, we calculate (1, 1087), (3, 1677), (5, 2819), and plug this into the La-

grange interpolation formula to get immediately that f (x) = 69x2 + 19x + 999.

8.9 We have, m+rp = 50909 < 248605 = a1 ·a2 ·a3 . Thus we compute s1 ≡ 4 (mod 5),

s2 ≡ 5 (mod 7), and s3 ≡ 1188 (mod 7109). When the participants poll their

shares and use the Chinese Remainder Theorem, they recover

50909 ≡ 519 ≡ m (mod 5039).

8.11 As above, rp + m = 713371 < a1 · a2 · a3 = 770110;

s1 ≡ 1 (mod 10), s2 ≡ 10 (mod 11), and s3 ≡ 6270 (mod 7001).

The Chinese Remainder Theorem recovers 713371 ≡ 3071 ≡ m (mod p).

8.13 We compute,

c1 ≡ 90 ’ 15 · 59 ’ 52 · 409 ≡ 69 (mod 503),

c2 ≡ 90 ’ 11 · 59 ’ 123 · 409 ≡ 440 (mod 503),

c3 ≡ 90 ’ 308 · 59 ’ 400 · 409 ≡ 404 (mod 503),

so the distributed hyperplanes are,

≡ 69 + 15x1 + 52x2 ; ≡ 440 + 11x1 + 123x2 ; ≡ 404 + 308x1 + 400x2 ,

1 2 3

all congruences modulo 503. Plugging these values into (8.4), we get,

« « «

’1 ’69

15 52 x1

11 ’1 x2 = ’440 = C.

123

AX =

’1 ’404

308 400 x3

then solving for det(A) = 22195, and using Cramer™s rule, we get

(x1 , x2 , x3 ) = (105323/22195, ’110043/22195, ’2610936/22195).

However, 22195’1 ≡ 8 (mod 503) and

105323 · 8 ≡ 59; ’110043 · 8 ≡ 409; ’2610936 · 8 ≡ 90,

all congruences modulo 503. Thus, (m1 , m2 , m3 ) = (59, 409, 90), and the secret

message m1 = 59 is retrieved.

8.15 As above,

c1 ≡ 718 ’ 297 · 107 ’ 306 · 1 ≡ 269 (mod 719),

c2 ≡ 718 ’ 419 · 107 ’ 537 · 1 ≡ 645 (mod 719),

c3 ≡ 718 ’ 698 · 107 ’ 709 · 1 ≡ 99 (mod 719),

so the distributed hyperplanes are,

≡ 269+297x1 +306x2 ; ≡ 645+419x1 +537x2 ; ≡ 99+698x1 +709x2 ,

1 2 3

all congruences modulo 719. Thus,

© 2003 by CRC Press LLC

244 Solutions to Odd-Numbered Exercises 8.15“8.19

« « «

’1 ’269

297 306 x1

419 ’1 x2 = ’645 = C.

537

AX =

’1 ’99

698 709 x3

then solving for det(A) = 43465, we get

(x1 , x2 , x3 ) = (190798/43465, ’171516/43465, 3175039/8693).

However, 43465’1 ≡ 323 (mod 719), 8693’1 ≡ 177 (mod 719), and

190798 · 323 ≡ 107; ’171516 · 323 ≡ 1; 3175039 · 177 ≡ 718,

all congruences modulo 719. Thus, (m1 , m2 , m3 ) = (107, 1, 718), and the secret

message m1 = 107 is retrieved.

t

8.17 In matrix-theoretic terms, the equation mk ≡ m + cj xj (mod p) is written

k

j=1

as

« « «

··· xt’1

1 x1 c0 m1

1

¬ ·¬ ·¬ ·

··· xt’1 c1 m2

1 x2

¬ ·¬ ·¬ ·

2

·≡¬

AC = ¬ ·¬ · (mod p).

. .

. . . .

. .

. . . . . .

. . . .

··· t’1

ct mt

1 xt xt

We now show that

(xk ’ xi )

det(A) = (S3)

1¤i<k¤t

We use induction on t. If t = 2, then

1 x1

det(xj ) = = x2 ’ x1 .

k 1 x2

This is the induction step. Now assume that the result holds for all such n — n

matrices with n < t. If cof(Aj,k ) denotes the cofactor of the matrix A = (xj ),

k

then by (C.37),

t

det(xj ) xj cof(Aj,k ).

=

k k

i=1

By induction hypothesis, the result holds for each Aj,k , so the entire result holds.

Since we have shown that (S3) holds, it is clear that det(A) ≡ 0 (mod p) if an

only if xk ≡ xi (mod p) for some i = k.

Section 8.2

8.19 We have,

sdA (pe + IB )eA ≡ ±eB dA ((cB ’ IB )de + IB )eA ≡ ±eB dA (cB ’ IB + IB )eA ≡

B

B

±eB dA (cB )eA ≡ ±eB dA ±dB eA ≡ ±eB dA +eA dB ≡ k (mod n),

and

sdB (pe + IA )eB ≡ ±eA dB ((cA ’ IA )de + IA )eB ≡ ±eA dB (cA ’ IA + IA )eB ≡

A

A

±eA dB (cA )eB ≡ ±eA dB ±dA eB ≡ ±eA dB +dA eB ≡ k (mod n).

© 2003 by CRC Press LLC

Solutions to Odd-Numbered Exercises 8.21“8.27 245

8.21 All congruences are modulo n = 48959 = pq. We perform the calculations within

the scheme. Alice and Bob, respectively, compute, cA ≡ ±dA ≡ 310279 ≡ 38953

and cB ≡ ±dB ≡ 332773 ≡ 11653, and Trent computes

pA ≡ (cA ’ IA )d ≡ (38953 ’ 21)9701 ≡ 35736,

and

pB ≡ (cB ’ IB )d ≡ (11653 ’ 93)9701 ≡ 30197.

Then Alice and Bob compute, respectively,

sA ≡ ±eA ≡ 3151 ≡ 3211,

and

sB ≡ ±eB ≡ 337 ≡ 26897.

Lastly, Alice and Bob, respectively, compute,

k ≡ sdA (pe + IB )eA ≡ 2689710279 (301975 + 93)151 ≡ 28578,

B

B

and

k ≡ sdB (pe + IA )eB ≡ 321132773 (357365 + 21)37 ≡ 28578,

A

A

the self-certi¬ed shared key.

8.23 As above, we do the calculations. All congruences are modulo n = 295907 = pq.

cA ≡ 72021 ≡ 204856, and cB ≡ 73011 ≡ 59114,

pA ≡ (204856 ’ 156)290315 ≡ 26211,

pB ≡ (59114 ’ 1001)290315 ≡ 217630,

sA ≡ 714033 ≡ 90187, and sB ≡ 7221675 ≡ 15244,

k ≡ 152442021 (217630131 + 1001)14033 ≡ 124394,

and lastly Bob™s calculation,

k ≡ 901873011 (26211131 + 156)221675 ≡ 124394,

to establish the shared key.

8.25 Trent computes, with all congruences modulo p,

p(x, y) ≡ 11 + 13(x + y) + 200xy,

fA (x) ≡ 141 + 210x; fB (x) ≡ 122 + 380x; fC (x) ≡ 183 + 24x;

from which are computed the session keys,

kA,B ≡ 316; kA,C ≡ 423; kB,C ≡ 203.

8.27 As above,

p(x, y) ≡ 5 + 15(x + y) + 25xy,

fA (x) ≡ 287 + 485x; fB (x) ≡ 186 + 47x; fC (x) ≡ 95 + 165x;

from which we get,

kA,B ≡ 746; kA,C ≡ 770; kB,C ≡ 468.

© 2003 by CRC Press LLC

246 Solutions to Odd-Numbered Exercises 8.29“9.3

8.29 As above,

p(x, y) ≡ 5 + 808(x + y) + 700xy,

fA (x) ≡ 620 + 127x; fB (x) ≡ 524 + 883x; fC (x) ≡ 495 + 733x;

from which we get,

kA,B ≡ 21; kA,C ≡ 210; kB,C ≡ 33.

8.31 Since Mallory has

fM (x) ≡ r1 + r2 kM + (r2 + r3 kM )x (mod p),

and Eve has

fE (x) ≡ r1 + r2 kE + (r2 + r3 kE )x (mod p),

then they have the four modular equations,

aM ≡ r1 + r2 kM (mod p),

bM ≡ r2 + r3 kM (mod p),

aE ≡ r1 + r2 kE (mod p),

and

bE ≡ r2 + r3 kE (mod p).

Hence, they have four equations in three unknowns from which elementary al-

gebra will yield a unique solution for r1 , r2 , r3 .

Section 9.1

9.1 Since Monty knows e, he can easily forge messages at will, and they will go

undetected due to the RSA conjecture. If Hostvania violates the treaty by

engaging in an underground nuclear test, it can point its ¬nger at Monty as the

perpetrator, and Monty could not disavow this claim since he knows e, and is

capable of forgeries.

Section 9.2

9.3 Bob veri¬es Alice™s signature by using her public key to get,

DeA (DdA (c)) ≡ c (mod n).

Then he uses his private key to obtain,

DdB (c) ≡ m (mod n),

where

eB dB ≡ 1 (mod (p2 ’ 1)(q 2 ’ 1)).

© 2003 by CRC Press LLC

Solutions to Odd-Numbered Exercises 9.5“9.9 247

9.5 Since

e’m(m’1)/(2n) ≈ 1 ’ pc ,

then

’m(m ’ 1)/(2n) ≈ ln(1 ’ pc ).

Hence,

m2 ’ m ≈ ’2n ln(1 ’ pc ),

and so

m2 ≈ ’2n ln(1 ’ pc ) ≈ 2n ln(1/(1 ’ pc )),

since we can safely ignore the smaller factor of ’m in an approximation. Thus,

m≈ 2n ln(1/(1 ’ pc )).

If pc = 1/2, then √

m ≈ 1.17 n.