Follow the Trail to Discover How Algebraic Properties of Identity and Inverse Play Important Roles in Securing Secrecy.

PART I - Identities and Inverses of Modular Systems

1. Complete the charts for mod 2, mod 4, mod 5, mod 6 and mod 7.

Mod 2

/	0	1		1	0	1
0				0
1				1

Mod 4

/	0	1	2	3		1	0	1	2	3
0						0
1						1
2						2
3						3

Mod 5

Mod 6

/	0	1	2	3	4	5		1	0	1	2	3	4	5
0								0
1								1
2								2
3								3
4								4
5								5

Mod 7

/	0	1	2	3	4	5	6		1	0	1	2	3	4	5	6
0									0
1									1
2									2
3									3
4									4
5									5
6									6

2. A. List the additive inverses for mod 2: 0 _____, 1 _____

Do all elements have an additive inverse? _____

If not, list the exceptions: __________

List the multiplicative inverses for mod 2: 1 _____.

Do all elements except 0 have a multiplicative inverse? _____

If not, list the exceptions: __________

1. List the additive inverses for mod 4: 0 _____, 1 _____, 2 _____, 3 ___

Do all elements have an additive inverse? _____

If not, list the exceptions: __________

List the multiplicative inverses for mod 4: 1 _____, 2 _____, 3 _____

Do all elements except 0 have a multiplicative inverse? _____

If not, list the exceptions: __________

2. List the additive inverses for mod 5: 0 _____, 1 _____, 2 _____,

1. _____, 4 _____

Do all elements have an additive inverse? _____

If not, list the exceptions: __________

List the multiplicative inverses for mod 5: 1 _____, 2 _____

3 _____, 4 _____.

Do all elements except 0 have a multiplicative inverse?

If not, list the exceptions: __________

1. List the additive inverses for mod 6: 0 _____, 1 _____, 2 _____

1. _____, 4 _____, 5 _____

Do all elements have an additive inverse?

If not, list the exceptions: __________

List the multiplicative inverses for mod 6: 1 _____, 2 _____, 3 _____,

4 _____, 5 _____

Do all elements except 0 have a multiplicative inverse? _____

If not, list the exceptions: __________

1. List the additive inverses for mod 7: 0 _____, 1 _____, 2 _____

3 _____, 4 _____, 5 _____, 6 ____

Do all elements have an additive inverse?

If not, list the exceptions: __________

List the multiplicative inverses for mod 7: 1 _____, 2 _____, 3 _____,

4_____, 5 _____, 6 _____

Do all elements except 0 have a multiplicative inverse? _____

If not, list the exceptions: __________

2. In some of these systems, not all the elements other than 0 have a multiplicative inverse. Study the relationship of each of these elements to the index of the mod. (The index of mod 7 is 7).
1. In mod 9, what elements other than 0 have no multiplicative inverses?
   
   ________________________________________________________
   
2. In mod 15, what elements other than 0 have no multiplicative inverse?
   
   ________________________________________________________
   
3. Write a clear explanation of your conclusions. Give a general rule for the mod systems which other than 0, have inverses for every element and which do not.
   
   ____________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
   
2. To challenge your understanding of identity and inverse, consider the

operation J and the elements {5, 6, 7, 8, 9}.

1. Arrange the elements so that 7 is the identity of operation J .
   

J	5	6	7	8	9
5
6
7
8
9

1. According to your chart, list the inverse of 5 _____, 6 _____, 7 _____,
1. _____, 9_____.







PART II - Identities and Inverses in Cryptography


1. Solve the case of a simple crypto system.
   
1. Decode this ciphertext: GUVF VF N PNRFNE PVCURE.
   
   Plaintext: ___________________________________________________
   
2. The key or inverse to this message is _____________________________.
   
3. Describe how you decoded the message
   ____________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
   
4. Write your own ciphertext using this system but with a different key.
   
   Ciphertext: __________________________________________________
   
   Plaintext: ___________________________________________________
   
   Key: _______________________________________________________
   
2. The clues that helped you decode the above messages are the weaknesses of that coding system. Although the disguise was sufficient during the time of the Roman Empire, more sophisticated methods are needed today. Public-Key Cryptography is a method that allows anyone to encode a message, but only permits the intended receiver to decipher it. A breakthrough public-key cryptosystem is RSA named for its developers: Ronald Rivest, Adi Shamir, and Leonard Aldeman.
   
1. This concept is based on what constitutes a hard problem.
   
   Find the product of two prime numbers: 257 and 503 ________________
   
   Find two prime numbers whose product is 10,3127 __________________
   
   The reversal (factoring) or inverse of the first task is considered more difficult; especially if the product happens to be 200 digits long.
   
2. Two advantages of using modular systems in cryptography are: 1. It eliminates rounding problems. 2. It makes large numbers more manageable. For example, according to the mod 7 multiplication chart, 31 2 h 51 4, that is 6 mod 7 h 20 mod 7.
   
   Similarly: 25 mod 21 h 4 mod 21 5² mod 21h 4 mod 21
   
   Find: 11² mod 15 h __________ 2⁷ mod 341h __________
   
3. Encode and decode a message using a scaled-down version of RSA with small primes.
   
   Suppose you are an information technology criminal intending to sabotage everyone’s computers with a virus. The only person you want to spare is your friend Alice. The message you want to send is the virus’ name: BCG. Alice sets up a cryptosystem to receive private messages. She picks two primes p and q. In this case, she uses p = 3 and q = 5. It is now necessary to find two numbers whose product is congruent to 1 in the mod(p-1)(q–1) system. Since (p-1)(q-1) = 8, she might pick the pairs 3 and 11. Note that 3,11, and 8 are relatively prime. Alice makes mod 15 and 11 known to the public so that anyone may send her a message; even sociopaths such as you. She keeps 3 secret so that only she can retrieve the message.
   
   
   First convert the alphabet to number code:
   
   B d 2
   C d 3
   G d _____
   
   
   Encode as follows:
   
   2¹¹ mod 15 h 2048 mod 15 h 8 mod 15
   
   3¹¹ mod 15 h 177147 mod 15 h 12 mod 15
   
   __________________________________
   
   


You send:

8 12 _____

To decode, Alice raises a message block to the power that is the inverse of 11mod 8, namely, 3.

8³ mod 15 h 512 mod 15 h 2 mod 15 Retrieved B

12³ mod 15 h 1728 mod 15 h 3 mod 15 Retrieved C

_______________________________________________