Notes 20110117 CIS 6650 Computer Security

From SnOwy - Ed's Wiki Notebook

Jump to: navigation, search

Dr. Obimbo's Security Course

RSA Keys

Prime factorization is exponential
Do not use prime numbers from a website
Generate two prime numbers, generate a public key and a private key
Encrypt a body of text with the public key
Everyone gets the public key in the class
Your partner gets a key to decrypt it
In a single week, the class attempts to decrypt all of the blocks of text
Each successful attempt transfers five points from the target to the winner
You start with twenty points
The class will have to decide on some of the features of the encryption
RFID tags in credit cards might be a problem

Aside

DFA vs NFA
DFA -- only one transition given a seen symbol and state
NFA -- more than one transition allowed given a seen symbol and state

Definitions

{Objects, Operations}
{Strings, {Substring, Concatenate, ...}}
Prime Numbers
Non-composite, Non-unit
Even functions -- reflection on the y-axis --> f(x) = -f(x)
Odd functions -- rotation on the origin --> -f(x) = f(-x)

Caesar Shift

Caesar shifted the Latin alphabet by three characters
This was once a strong encryption, this is now vulnerable to brute force
There are only 26 possibilities per arbitrary character
CASE
DBTF
ECUG

Modulus Math

a|d <=> exists k such that d = ak
k in integers
LCM of a, b is d
iff a|d and b|d and not exists k < d such that a|k and b|k
(common multiples -- d is the smallest of such -- least)
(such that is given by the backward epsilon)

LCM of 24, 36

factorization was done last time

24
3 * 8
3 * 2^3

36
4 * 9
2^2 * 3^2

Pick the highest powers for each unique prime for LCM:
- 2^3 * 3^2 = 72 -- LCM
- LCM of 2^2 3^4 5^2, 2^3, 3^3, 5
- LCM = 2^3 * 3^4, 5^2
Pick the lowest powers for GCDs.

Theorem 2

ab = GCD(a, b) * LCM(a, b)
a, b are natural numbers
a, b are "relatively prime" if gcd(a, b) = 1
gcd(17, 22) = 1 are relatively prime
Def 5:
- for integers a1, a2, ... an
- pairwise relatively prime if gcd(ai, aj) = 1 whenever ...
- 10, 17, 21 are relatively prime

RSA

See: Chinese remainder theorem

Modular Arithmetic

a is an integer
m is a positive integer
a mod m is the remainder after a is divided by m
17(mod 5) = 2
-132(mod 7) = 1
If a and b are integers
If m is a positive integer
then a is congruent to b % m if m divides (a - b)
a congruent b(mod m)
i.e. if a, b are in the same equivalence class, then they are congruent

Theorem 3

m is a positive integer
a and b are congruent module m
iff integer k such that a = b + km
( a congruent b (mod m) then m | (a - b) )
( a - b = km )
( a = b + km ) QED

If a and b are congruent; and c and d are congruent

(that is a congruent b(mod m) and c congruent d(mod m))
then a + c is congruent to b + d (mod m)
and ac is congruent to bd(mod m)
i.e. if you are adding two numbers or multiplying them
you may as well operate on their classes
- notice -- it looks like the congruent symbol is lower on precedence than mod

Definition

a congruent b (mod m) then
a + c
= (b + k1m) + (d + k2m)
= b + d + (k1 + k2) m
= b + d + zm (since integers are closed under addition)
congruent to b + d(mod m)
- Homework is exponentiation
ac
= (b + k1m)(d + k2m)
= bd + bk2m + dk1m + k1k2m^2
= bd + m(bk2 + dk1 + k1k2m)
(since integers are closed under addition and multiplication)
= bd + mz
ac congruent bd(mod m)

Applying modular arithmetic (Gauss)

Example 8:
7 + 11 (mod 5) = 2 + 1 = 3
7 * 11 (mod 5) = 2 * 1 = 2

Corollary

Let m be a positive integer
If a congruent b (mod m)
then a^c congruent b^c (mod m)
multiplication is multiple additions
exponentiation is multiple multiplications

HOMEWORK: Do the proof for this

7^10 mod 5 = 2^10 = 1024
7^100 mod 3 = 1^1000 = 1
4^100 mod 10 ...
4 ^1 mod 10 = 4
4 ^2 mod 10 = 6
4 ^3 mod 10 = 4
4 ^4 mod 10 = 6
... = 6
a = bq + r, where a, b, q and r are integers
GCD(a, b) = GCD(b, r)
Proof ...

Proof

proof by construction
proof by contradiction
proof by induction
proof by contraposition

Statistics

-- proof by contraction -- medicine
Do a test, and look at the numbers -- medicine has good effect
let's try proof by contradiction

Constructive part

let d = gcd(a, b) -- d divides both a and b
a = k1d
b = k2d
k1d = k2dq + r
r = k1d + k2dq = d(k1-k2q) -- subtraction closed under integers
r = k1d + k2dq = dz
where z in integers
=> d|r

Contradiction part ...

let's assume that there exists a factor greater than d
pt2 =><= need to prove that d is the greatest factor of b, r
assume exists d1 > d such that d1|b and d1|r
b = k3d1 and r = k4d1
a = bq + r = k3d1q + k4d1 = d1z
gcd(a, b) = d1 > d which is a contradiction =><=

Example 8 ...

GCD(979, 267) using Euclidean algorithm
979 = 3(267) + 178
267 = 1(178) + 89
178 = 2(89) + 0
GCD = 89
another example ...
GCD(3959, 1177)
3959 = 3(1177) + 428
1177 + 2(428) + 321
428 + 1(321) + 107
321 + 3(107) + 0
GCD = 107

System security

CIAA
Confidentiality
Integrity
Authentication
Availabiity

Groups

CAII
Closure
Associativity
Identity
Inverses
Finite Groups
A group (S, ⊕) is a nonempty set S together with a binary
operation ⊕ on S such that the following conditions hold
Closure: for all a, b in S, the element a ⊕ b is an element of S
Associativity: for a, b, c in S; a op (b ⊕ c) = (a ⊕ b) ⊕ c
Identity: e in G such that e ⊕ a = a and a ⊕ e = a -- for all a in S
Inverses: for a in S there exists an inverse element a^-1 in S such that...
a ⊕ ainv = e and ainv ⊕ a = e
we can write ab for the product a ⊕ b
Example group: integers under addition
If a group satisfies commutative law, then it is "an abelian group"
a ⊕ b = b ⊕ a for every a, b in s
if in a group (S, op), |S| < ∞
then it is a finite group
a group in mod six

+   0   1   2   3   4   5
 6
0   0   1   2   3   4   5
1   1   2   3   4   5   0
2   2   3   4   5   0   1
3   3   4   5   0   1   2
4   4   5   0   1   2   3
5   5   0   1   2   3   4

editor: is there something wrong with the above table?
identity = 0
inverse x^-1 = 6 - x
A multiplicative group modulo n is defined as (Z*_n, n)
the elements f this group are the set Z*_n of elements
in Z_n that are relatively prime to n
Example Z*₁₅ = {1, 2, 4, 7, 8, 11, 13, 14}
|Z*₁₅| = phi(15) = 15 (1 - 1/3) (1 - 1/5)
= n PI_p/n (1 - 1/p) (editor: transcription error?)
The size of Z* is Euler's phi function ...
phi(100) = 100(1/2)(4/5) => 40 --> |Z*_100| = 40
also called "totient" function
gcd(a, n) = 1
a^phi(n) (mod n) = 1

Example

phi(45) = 45 (1 - 1/3) (1 - 1/5)
= 45(2/3)(4/5)
= 24

Example ...

ax = b -- primitives; a, x, b are real numbers
Ax = b -- matrix algebra; A is a matrix, b is a vector
ax = b
ainv a x = ainv b
x = ainv b

Solving modular linear equations

15inv mod(47)

47 = 3(15) + 2
15 = 7(2) + 1
-----
1 = 15 - 7(2)

.
.
.

47 = 3(15) + 2 => 2 = 47 - 3(15) -->
15 = 7(2) + 1
-----
1 = 15 - 7(2) <--
  = 15 - 7(47 - 3(15))
  = 22(15) - 7(47)

.
.
.

47 = 3(15) + 2 => 2 = 47 - 3(15) -->
15 = 7(2) + 1
-----
1 = 15 - 7(2) <--
  = 15 - 7(47 - 3(15))
  = 22(15) - 7(47)
  = 22(15) + 8(47) (mod 15)

.
.
.

15inv mod(47) = 22
47inv mod(15) = 8

test ...

330 / 47 = 7 remainder 1 OK

---

New Example

15x congruent 4 (mod 47)
15inv 15x congruent 15inv 4 (mod 47)
x = 22(4) (mod 47)
x = 41

<<< 15inv (mod 47) = 22
>>> 47 - 15 = 22
<<< 88 (mod 47)
>>> 88 - 47 = 41

Read

Section 3.3 to 3.7 ROSEN Book -- Integer theory
Discrete mathematics and its applications

Notes 20110117 CIS 6650 Computer Security

From SnOwy - Ed's Wiki Notebook

Contents

RSA Keys

Aside

Definitions

Caesar Shift

Modulus Math

LCM of 24, 36

Theorem 2

RSA

Modular Arithmetic

Theorem 3

If a and b are congruent; and c and d are congruent

Definition

Applying modular arithmetic (Gauss)

Corollary

HOMEWORK: Do the proof for this

Proof

Statistics

Constructive part

Contradiction part ...

Example 8 ...

System security

Groups

Example

Example ...

Solving modular linear equations

New Example

Read

Personal tools

Namespaces

Variants

Views

Actions

Search

Navigation

Links

Toolbox