Notes 20110124 CIS 6650 Computer Security

From SnOwy - Ed's Wiki Notebook

Contents 1 Sieve of Erastothenes 2 The number of primes up to a certain integer 3 Group 4 Number Theory 5 Quasi-Inverses 6 Finding solutions for mod algebra 7 Example 2 8 Powers of an Element 9 Fermat's Little Theorem 10 Fast Exponentiation 11 Assignment 12 Chinese Remainder Theorem 12.1 Charlie's Method 12.2 (1, 0, 2)S(3, 5, 7) 13 Administrivia

Sieve of Erastothenes

for the assignment

• sieve only prime numbers
• start at the square of a prime
• end at square root of last number
• sieve only odd numbers
• citations

The number of primes up to a certain integer

• estimated for n given Π(n) = (n)/(ln(n))
• Π(10⁶) ~ 10⁶ / (ln(10⁶)) ~ 10⁶/(6ln(10))
• approximate this prime number: lim Π(n)_{n → ∞} ~ n / (ln(n))

Group

• Closure, Associative, Identity, Inverse
• Abelian → Commutative

Number Theory

• The phi function ...
• Φ(45) = 24 = 45 (2/3) (4/5) -- 24 is the power at which the mod is one :D
• 7²⁴mod(45) = 1 -- it's equal to one, we're multiplying by one over and over, we just pull it out instead
• 7²⁵mod(45) = 7
• ...
• 7^104513246(mod 100)
• we're looking at 40 ...
• we know that to know if something is divisible by 4, we look at the last two digits
• we look at the last three digits for 40 ...
• the above is equal to 7²⁴⁶(mod 100)
• that is equal to 7⁶(mod 100)

Quasi-Inverses

• if two numbers are mutually prime, you can get one as the inverse with respect the other
• example, GCD(3, 10) = 1;
• we can get 3^-1 (mod 10) = 7.
• what if we have (6, 10)? -- GCD is 2 -- we can get a quasi-inverse

Finding solutions for mod algebra

• 3x congruent 4 (mod 10)
• 3^-1(mod 10) = 7
• -- method 2 -- Euclid's algorithm
• 10 = 3(3) + 1
• 1 = 10 - 3(3)
• congruent 10 + 7(3) (mod 10)
• another example ...
• 15(mod 46)
• 46 = 3(15) + 1
• 1 = 46 - 3(15)
• congruent 46 + 43(15) (mod 46)
• -- going back to 3x congruent 4 (mod 10) ...
• 3^-1 (mod 10) = 7
• 7(3x) congruent 7(4) (mod 10)
• x = 8 (mod 10)

Example 2

• 4x congruent 6 (mod 10)
• it would be good to premultiply by 4
• there is none in ten
• 4^-1(mod 10) = 3/2
• x = (3/2)(6) (mod 10)
• x = 9
• because the GCD is 2, there are two solutions ...
• 10/2 = 5
• 9+5 (mod 10) = 4
• 4{x = 4, 9} = 6(mod 10)
• alternative method -- divide by GCD
• 4x congruent 6(mod 10)
• 2x congruent 3(mod 5)
• x congruent 3(3) (mod 5)
• solution is 9 congruent 4 (mod 5)

Powers of an Element

• 3ⁱ (mod 7) -- remember, phi(7) = 6 (the number of mutually prime integers under mod(7) -- if phi(prime) then return prime -1))

i     0 1 2 3 4 5 6 7
3^i%7 1 3 2 6 4 5 1 3

Fermat's Little Theorem

• Fermat's little theorem -- a ^p-1 congruent 1 (mod n) forevery a ∈ Z^*_p
• -- a^p-1 = a^Φ(p)

      1 2 3 4
1^i%5 1 1 1 1
2^i%5 2 4 3 1
3^i%5 3 4 2 1
4^i%5 4 1 4 1

• the very last column is all ones

Fast Exponentiation

• 3¹⁵⁷(mod 100)
• we take the exponent and we convert it to a binary number
• once that is done, we'll be raising it to a constant and we mod that with one hundred
• 3⁵(mod 10)
• 5 = 0b101

  | 1 | 0 | 1 |
3 | 3 | 9 | 3 |

• algorithm:
• if col is 1, square previous and multiply base
• if col is 0, square only
• 3¹⁵⁷ (mod 100) = 3³⁷(mod 100)
  • how did we know to change 157 to 37?
  • Φ(100) = 40 = 100 * (1/2) * (4/5)
  • 157 (mod 40) = 37 = 157 - 3(40)

        | 1 0  0  1  0  1
3^i%100 | 3 9 81 83 89 63

• • why does 81 turn into 83, 89 into 63 when they're supposed to be ascending values?
  • remember: we're taking the value as the mod of 100
• converting to binary -- divide by eight -- get triplet binary digit families
• solution is 63

Assignment

• big values -- a hundred digits raised by a hundred digits mod something

Chinese Remainder Theorem

• what inter x leaves a remainder of ...
• 2 when divided by 3
• 3 when divided by 5
• 2 when divided by 7
• x = (2, 3, 2)S(3, 5, 7)
• this is a system of three
• a system is pairwise relatively prime
• (3, 7)S(5, 13)
• CLR
• Solve for a, if ...
• a congruent 2 (mod 3)
• a congruent 3 (mod 5)
• a congruent 4 (mod 7)
• (a1,a2,a3)S(n1,n2,n3)

a1 = 2, a2 = 3, a3 = 4
n1 = 3, n2 = 5, n3 = 7
m1 = 35, m2 = 21, m3 = 15
m1inv = 2, m2inv = 1, m3inv = 1
c1 = 70, 21, 15
a = 70(2) + 21(3) + 15(4) (mod 105)
a = 35 + 18 + 53

• m_i = Π_{i not j}n_j
• miinv = mi inv wrt mod ni
• ci = mi(miinv mod ni)

Charlie's Method

• (1, 3, 1)S(3, 5, 7)
• 1 in terms of 7
• 1, 7 -- must continue to be happy
• we must pick a solution that is congruent to 1 mod 7.
• next -- we now want that number that is also correct for 3 mod 5.
• 1 + 2(2inv mod 7)(7) = 1 + 2(3)(7) = 43(mod 35) = 8
• 8 satisfies 3 in mod 5, 1 in mod 7.
• next iteration --
• 8 + 2(2)(35) (mod 3)
• 35^-1 (mod 3)
• 2^-1 (mod 3)
• 43

(1, 0, 2)S(3, 5, 7)

• start with 7 -- must satisfy 2 in mod 7
• = 2;
• next -- we want to add singletons that satisfies 0 in mod 5 while keeping 2 in mod 7 happy.
• 2 +
• ... reset
• we have two to begin with.
• 2 -- satisfies 2, 7
• but 2 in mod 5 is still 2 -- we need to make it zero
• we want to keep adding one to zero without affecting the 2 mod 7 ...
• 2 + 3(3)(7) = 30
• 30 + 1(2)(35) = 100

Administrivia

• http://www.uoguelph.ca/~cobimbo/Courses/CS6650/index.html