PART I - Identities and Inverses of Modular Systems
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
/
0
1
2
3
4
1
0
1
2
3
4
0
0
1
1
2
2
3
3
4
4
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
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: __________
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: __________
List the additive inverses for mod 5: 0 _____, 1 _____, 2 _____,
_____, 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: __________
List the additive inverses for mod 6: 0 _____, 1 _____, 2 _____
_____, 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: __________
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: __________
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).
In mod 9, what elements other than 0 have no multiplicative inverses?
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.
The key or inverse to this message is _____________________________.
Describe how you decoded the message
____________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
Write your own ciphertext using this system but with a different key.
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.
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.
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 52 mod 21h
4 mod 21
Find: 112 mod 15 h
__________ 27 mod 341h
__________
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:
211 mod 15 h
2048 mod 15 h
8 mod 15
311 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.