set of challenges. The primary difficulty lies in the precision required. A small mistake in calculations, a misstep in applying a formula, or an incorrect assumption can lead to
incorrect answers. Mathematics exams demand
Solution Manual For
Cryptography
Theory and Practice
Second Edition
Solution Manual
Douglas R. Stinson
, Contents
set of challenges. The primary difficulty lies in the precision required. A small mistake in calculations, a misstep in applying a formula, or an incorrect assumption can lead to
incorrect answers. Mathematics exams demand
0 Introduction 1
1 Classical Cryptography 2
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2 Shannon’s Theory 15
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3 Block Ciphers and the Advanced Encryption Standard 25
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4 Cryptographic Hash Functions 37
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
5 The RSA Cryptosystem and Factoring Integers 50
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
6 Public-key Cryptosystems Based on the Discrete Logarithm
Problem 66
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
7 Signature Schemes 78
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
, 0
Introduction
set of challenges. The primary difficulty lies in the precision required. A small mistake in calculations, a misstep in applying a formula, or an incorrect assumption can lead to
incorrect answers. Mathematics exams demand
This is the solution manual to Cryptography Theory and Practice, Second Edition,
which was published in March, 2002. I provide ―final answers‖ to computational
questions, and detailed proofs for all mathematical questions. I obtained most
answers to computational questions using Maple, which is a convenient language
for performing many calculations related to cryptography. Computer programs
are not included in this solution manual, however.
This solution manual refers to the first printing of the book. Several exercises
contained typos or other errors, which are noted in this solution manual. Also, I
maintain an up-to-date errata list for the book, which can be found on the follow-
ing web page:
www.cacr.math.uwaterloo.ca/˜dstinson/CTAP2/CTAP2.html
These errors will be fixed in later printings of the book.
I would appreciate any comments or feedback about this solution manual and
about the book in general, especially relating to its suitability as a textbook. In
particular, I will be grateful to anyone who finds errors in the book and points
them out to me.
I hope that this solution manual will be a useful resource for instructors teach-
ing courses in cryptography. Please try to prevent the distribution of this manual
to students! The usefulness of the Exercises will be severely limited if this manual
somehow escapes into the public domain.
Douglas R. Stinson
Waterloo, Ontario
June, 2002
1
, 1
Classical Cryptography
set of challenges. The primary difficulty lies in the precision required. A small mistake in calculations, a misstep in applying a formula, or an incorrect assumption can lead to
incorrect answers. Mathematics exams demand
Exercises
1.1 Evaluate the following:
(a) .
Answer: .
(b) .
Answer: .
(c) .
Answer: .
(d) .
Answer: .
1.2 Suppose that , and ....................... Prove that
Answer: We have , where and
. Then , where
....................................................................................................... Therefor
e
.
1.3 Prove that if and only if .
Answer: implies that and
, where . Then , so
.................................................................................................... Conversel
y,
suppose . Then . Let ................. Then
for some , and hence , so .
1.4 Prove that , where .
Answer: , so , and hence
.
1.5 Use exhaustive key search to decrypt the following ciphertext, which was
encrypted using a Shift Cipher:
BEEAKFYDJXUQYHYJIQRYHTYJIQFBQDUYJIIKFUHCQD
Answer: The key is , and the plaintext is the
following: Look, up in the air, it‘s a bird, it‘s a
plane, it‘s Superman!
1.6 If an encryption function is identical to the decryption function , then the key
is said to be an involutory key. Find all the involutory keys in the Shift Cipher
2
incorrect answers. Mathematics exams demand
Solution Manual For
Cryptography
Theory and Practice
Second Edition
Solution Manual
Douglas R. Stinson
, Contents
set of challenges. The primary difficulty lies in the precision required. A small mistake in calculations, a misstep in applying a formula, or an incorrect assumption can lead to
incorrect answers. Mathematics exams demand
0 Introduction 1
1 Classical Cryptography 2
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2 Shannon’s Theory 15
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3 Block Ciphers and the Advanced Encryption Standard 25
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4 Cryptographic Hash Functions 37
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
5 The RSA Cryptosystem and Factoring Integers 50
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
6 Public-key Cryptosystems Based on the Discrete Logarithm
Problem 66
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
7 Signature Schemes 78
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
, 0
Introduction
set of challenges. The primary difficulty lies in the precision required. A small mistake in calculations, a misstep in applying a formula, or an incorrect assumption can lead to
incorrect answers. Mathematics exams demand
This is the solution manual to Cryptography Theory and Practice, Second Edition,
which was published in March, 2002. I provide ―final answers‖ to computational
questions, and detailed proofs for all mathematical questions. I obtained most
answers to computational questions using Maple, which is a convenient language
for performing many calculations related to cryptography. Computer programs
are not included in this solution manual, however.
This solution manual refers to the first printing of the book. Several exercises
contained typos or other errors, which are noted in this solution manual. Also, I
maintain an up-to-date errata list for the book, which can be found on the follow-
ing web page:
www.cacr.math.uwaterloo.ca/˜dstinson/CTAP2/CTAP2.html
These errors will be fixed in later printings of the book.
I would appreciate any comments or feedback about this solution manual and
about the book in general, especially relating to its suitability as a textbook. In
particular, I will be grateful to anyone who finds errors in the book and points
them out to me.
I hope that this solution manual will be a useful resource for instructors teach-
ing courses in cryptography. Please try to prevent the distribution of this manual
to students! The usefulness of the Exercises will be severely limited if this manual
somehow escapes into the public domain.
Douglas R. Stinson
Waterloo, Ontario
June, 2002
1
, 1
Classical Cryptography
set of challenges. The primary difficulty lies in the precision required. A small mistake in calculations, a misstep in applying a formula, or an incorrect assumption can lead to
incorrect answers. Mathematics exams demand
Exercises
1.1 Evaluate the following:
(a) .
Answer: .
(b) .
Answer: .
(c) .
Answer: .
(d) .
Answer: .
1.2 Suppose that , and ....................... Prove that
Answer: We have , where and
. Then , where
....................................................................................................... Therefor
e
.
1.3 Prove that if and only if .
Answer: implies that and
, where . Then , so
.................................................................................................... Conversel
y,
suppose . Then . Let ................. Then
for some , and hence , so .
1.4 Prove that , where .
Answer: , so , and hence
.
1.5 Use exhaustive key search to decrypt the following ciphertext, which was
encrypted using a Shift Cipher:
BEEAKFYDJXUQYHYJIQRYHTYJIQFBQDUYJIIKFUHCQD
Answer: The key is , and the plaintext is the
following: Look, up in the air, it‘s a bird, it‘s a
plane, it‘s Superman!
1.6 If an encryption function is identical to the decryption function , then the key
is said to be an involutory key. Find all the involutory keys in the Shift Cipher
2
