Encryption And Decryption Using Vigenere With Cipher Block Chaining: Up To 50 Dollars Will Be Given
Modular Arithmetic Dr. Y. Chu CIS3360: Security in Computing 0R02 Spring 2018
1
Information
Reading: Appendix B.2 in textbook (will be posted in Webcourses)
Reference: online tutorials
2
Modulo Operation
Given any positive integer n and any integer a, when a is divided by n, we get an integer quotient, q, and integer remainder, b, that obey the following relationship:
a = q · n + b, where 0 <= b <= n-1
Then we define b= a modulo n or b= a mod n.
Note: b (modular value) is always non-negative
Examples:
5 mod 11 = 5, 5=0x11+5, so q=0 and b=5
17 mod 11 = 6, 17=1×11+6, so q=1 and b=6
-11 mod 7 = 3. (-11)=(-2)x7+3, so q=-2 and b=3
3
b is always non-negative
Congruent Modulo
Two integers, a and b, are congruent modulo n if and only if a mod n = b mod n
When a and b are divided by n, they have the same remainder
a ≡ b (mod n) ⇔ a mod n = b mod n
Example:
100 mod 11 = 1; 34 mod 11 = 1
So 100 ≡ 34 (mod 11)
In arithmetic modulo n, a and b are equivalent if their difference, (a – b), is a multiple of n
n | (a – b)
Example:
10 ≡ 2 (mod 4) because 4 | (10 − 2)
4
Modular Arithmetic
Modular arithmetic is ‘clock arithmetic’
For clock, time goes from 1 to 12, and back to 1 again
For modulo arithmetic, we start with 0, go up to n-1, and then go back to 0
Modular arithmetic uses a finite number of values, and loops back from either end
When we do modular arithmetic, we can first perform the operation and then modulo reduce the answer
Examples:
( 12 + 8 ) mod 5 = 20 mod 5 = 0
( 12 x 8 ) mod 5 = 96 mod 5 = 1
5
Modulo Reduction
The results of modular computations must remain within Zn = {0, 1, 2, … n-1}
For large values, modulo reduction is used to simplify modular computations.
Modulo properties:
Reducing each intermediate result modulo n yields the same result as doing the entire calculation, and then reducing the result to modulo n
For integers a, b, and c, and for positive n, we have:
( a + b ) mod n = ( ( a mod n ) + ( b mod n ) ) mod n
( a – b ) mod n = ( ( a mod n ) – ( b mod n ) ) mod n
( a · b ) mod n = ( ( a mod n ) · ( b mod n ) ) mod n
a (b+c) mod n = ( ( a b mod n ) · ( a c mod n ) ) mod n
Examples
( 12 + 8 ) mod 5 = ( ( 12 mod 5 ) + ( 8 mod 5 ) ) mod 5 = ( 2 + 3 ) mod 5 = 5 mod 5 = 0
(12 – 8) mod 5 = ( (12 mod 5 ) – ( 8 mod 5) ) mod 5 = ( 2 – 3 ) mod 5 = -1 mod 5 = 4
( 12 · 8 ) mod 5 = ( ( 12 mod 5 ) · ( 8 mod 5 ) ) mod 5 = ( 2 · 3 ) mod 5 = 6 mod 5 = 1
26 mod 5 = ( ( 22 mod 5 ) · ( 24 mod 5 ) ) mod 5 = (( 4 mod 5 ) · ( 16 mod 5 ) ) mod 5= (4*1) mod 5 = 4
Other properties:
Transitive law: a ≡ b ≡ c, then a ≡ c
Commutative: a + b = b + a
Associative: (a + b) + c = a + (b + c)
Distributive: a(b + c) = ab + ac
6
Modular Inverse
Given two positive integers x and y, both less than some other positive integer n, we say that y is the modular inverse of x, modulo n, and x is the modular inverse of y, modulo n,
if and only if (x · y) mod n = 1, for 0 < x < n and 0 < y < n
x-1 = y (mod n)
Example:
Prove 7 and 3 are inverses modulo 10
Steps:
Compute the multiplication
Compute the modulo value of the result
If the modulo value is 1, the numbers are inverses
7 · 3 = 21
21 mod 10 = 1
Since the modulo value is 1, 7 and 3 are inverses modulo 10
7
Properties of Modular Inverse
The number 1 is always the modular inverse of 1 for any modulus.
Not all values less than a particular modulus have inverses
Inverse of 2, mod 14 does not exist
Look at the row of 2
This row does not have 1
For the number a and modulo n, the inverse can be found if a and n are relatively prime
Relatively prime: two numbers a, n are relatively prime if gcd(a,n) = 1, where gcd is greatest common divisor
In the table, we can see 1, 3, 5, 9, 11 and 13 are relatively prime to 14.
So those rows contains 1, indicating modular inverses
8
Mod 14 multiplication table
Summary
What is Modulo Operation
Concept of Congruent Modulo
Modular Arithmetic
Modulo Reduction
Modular Inverse
Properties of Modular Inverse
9
Do you need a similar assignment done for you from scratch? Order now!
Use Discount Code "Newclient" for a 15% Discount!
