Cryptography Reference
In-Depth Information
+
0123
0
0123
1
12
···
2
···
3
1. Construct the multiplication table for
4 .
2. Construct the addition and multiplication tables for
Z
Z 5 .
3. Construct the addition and multiplication tables for
Z 6 .
4. There are elements in
Z 6 without a multiplicative inverse. Which ele-
ments are these? Why does a multiplicative inverse exist for all nonzero elements
in
Z 4 and
Z 5 ?
1.8. What is the multiplicative inverse of 5 in
Z 11 ,
Z 12 , and
Z 13 ? You can do a
trial-and-error search using a calculator or a PC.
With this simple problem we want now to stress the fact that the inverse of an
integer in a given ring depends completely on the ring considered. That is, if the
modulus changes, the inverse changes. Hence, it doesn't make sense to talk about
an inverse of an element unless it is clear what the modulus is. This fact is crucial
for the RSA cryptosystem, which is introduced in Chap. 7. The extended Euclidean
algorithm, which can be used for computing inverses efficiently, is introduced in
Sect. 6.3.
1.9. Compute x as far as possible without a calculator. Where appropriate, make use
of a smart decomposition of the exponent as shown in the example in Sect. 1.4.1:
1. x = 3 2 mod 13
2. x = 7 2 mod 13
3. x = 3 10 mod 13
4. x = 7 100 mod 13
5. 7 x = 11 mod 13
The last problem is called a discrete logarithm and points to a hard problem which
we discuss in Chap. 8. The security of many public-key schemes is based on the
hardness of solving the discrete logarithm for large numbers, e.g., with more than
1000 bits.
1.10. Find all integers n between 0
n < m that are relatively prime to m for m =
4 , 5 , 9 , 26. We denote the number of integers n which fulfill the condition by
φ
( m ),
e.g.
φ
(3)=2. This function is called “Euler's phi function”. What is
φ
( m ) for m =
4 , 5 , 9 , 26?
1.11. This problem deals with the affine cipher with the key parameters a = 7, b =
22.
1. Decrypt the text below:
falszztysyjzyjkywjrztyjztyynaryjkyswarztyegyyj
2. Who wrote the line?
 
Search WWH ::




Custom Search