Modular or “clock” arithmetic

CS 207m: Discrete Structures (Minor)

Abstract algebra and Number theory –

Lecture 24 Apr 20 2018

Modular or “clock” arithmetic

Definition

For integersa, band positive integer m, we say ais congruent to bmodulo m, denoted a≡b mod m, ifm|(a−b).

Modular or “clock” arithmetic

Definition

For integersa, band positive integer m, we say ais congruent to bmodulo m, denoted a≡b mod m, ifm|(a−b).

i.e.,a &bmay not be same, but modulom, they are the same:

Modular or “clock” arithmetic

Definition

For integersa, band positive integer m, we say ais congruent to bmodulo m, denoted a≡b mod m, ifm|(a−b).

i.e.,a&bmay not be same, but modulom, they are the same:

I Formally,a≡b mod miff a mod m=b mod m.

Modular or “clock” arithmetic

Definition

For integersa, band positive integer m, we say ais congruent to bmodulo m, denoted a≡b mod m, ifm|(a−b).

i.e.,a&bmay not be same, but modulom, they are the same:

I Formally,a≡b mod miff a mod m=b mod m.

I What other properties does this “congruence” have?

Modular or “clock” arithmetic

Definition

For integersa, band positive integer m, we say ais congruent to bmodulo m, denoted a≡b mod m, ifm|(a−b).

i.e.,a&bmay not be same, but modulom, they are the same:

I Formally,a≡b mod miff a mod m=b mod m.

I What other properties does this “congruence” have?

I Equivalence?

I Ifa≡b modm,c≡d modm, thena+c≡b+d modm andac≡bd modm.

I c≡ab modmiffc≡(a(b modm)) modm

Modular or “clock” arithmetic

Definition

For integersa, band positive integer m, we say ais congruent to bmodulo m, denoted a≡b mod m, ifm|(a−b).

i.e.,a&bmay not be same, but modulom, they are the same:

I Formally,a≡b mod miff a mod m=b mod m.

I What other properties does this “congruence” have?

I Equivalence?

I Ifa≡b modm,c≡d modm, thena+c≡b+d modm andac≡bd modm.

I c≡ab modmiffc≡(a(b modm)) modm iffc≡(a modm)(b modm) mod m.

I Corollary: Modular exponentiation is easy!

I What is 5¹⁵ mod 23?

Modular or “clock” arithmetic

Definition

For integersa, band positive integer m, we say ais congruent to bmodulo m, denoted a≡b mod m, ifm|(a−b).

i.e.,a&bmay not be same, but modulom, they are the same:

I Formally,a≡b mod miff a mod m=b mod m.

I What other properties does this “congruence” have?

I Equivalence?

I Ifa≡b modm,c≡d modm, thena+c≡b+d modm andac≡bd modm.

I c≡ab modmiffc≡(a(b modm)) modm iffc≡(a modm)(b modm) mod m.

I Corollary: Modular exponentiation is easy!

I What is 5¹⁵ mod 23?

I = (5 mod 23)(5² mod 23)(5⁴ mod 23)(5⁸ mod 23)

Modular or “clock” arithmetic

Definition

For integersa, band positive integer m, we say ais congruent to bmodulo m, denoted a≡b mod m, ifm|(a−b).

i.e.,a&bmay not be same, but modulom, they are the same:

I Formally,a≡b mod miff a mod m=b mod m.

I What other properties does this “congruence” have?

I Equivalence?

I Ifa≡b modm,c≡d modm, thena+c≡b+d modm andac≡bd modm.

I c≡ab modmiffc≡(a(b modm)) modm

I Corollary: Modular exponentiation is easy!

I What is 5¹⁵ mod 23?

I = (5 mod 23)(5² mod 23)(5⁴ mod 23)(5⁸ mod 23) mod 23 = (5·2·4·16) mod 23 = 65 mod 23 = 19.

I What is the worst case no. of steps?

Modular or “clock” arithmetic

Definition

For integersa, band positive integer m, we say ais congruent to bmodulo m, denoted a≡b mod m, ifm|(a−b).

i.e.,a&bmay not be same, but modulom, they are the same:

I Formally,a≡b mod miff a mod m=b mod m.

I What other properties does this “congruence” have?

I Equivalence?

I Ifa≡b modm,c≡d modm, thena+c≡b+d modm andac≡bd modm.

I c≡ab modmiffc≡(a(b modm)) modm

A math application: Fermat’s little theorem

I For any prime p, ifgcd(a, p) = 1, thenp|(a^p−1−1).

Modular or “clock” arithmetic

Definition

For integersa, band positive integer m, we say ais congruent to bmodulo m, denoted a≡b mod m, ifm|(a−b).

i.e.,a&bmay not be same, but modulom, they are the same:

I Formally,a≡b mod miff a mod m=b mod m.

I What other properties does this “congruence” have?

I Equivalence?

I Ifa≡b modm,c≡d modm, thena+c≡b+d modm andac≡bd modm.

I c≡ab modmiffc≡(a(b modm)) modm

A math application: Fermat’s little theorem

I For any prime p, ifgcd(a, p) = 1, thenp|(a^p−1−1).

I For any prime p, ifgcd(a, p) = 1, thena^p−1 ≡1 mod p.

Modular or “clock” arithmetic

Definition

For integersa, band positive integer m, we say ais congruent to bmodulo m, denoted a≡b mod m, ifm|(a−b).

i.e.,a&bmay not be same, but modulom, they are the same:

I Formally,a≡b mod miff a mod m=b mod m.

I What other properties does this “congruence” have?

I Equivalence?

I Ifa≡b modm,c≡d modm, thena+c≡b+d modm andac≡bd modm.

I c≡ab modmiffc≡(a(b modm)) modm

A math application: Fermat’s little theorem

I For any prime p, ifgcd(a, p) = 1, thenp|(a^p−1−1).

I For any prime p, ifgcd(a, p) = 1, thena^p−1 ≡1 mod p.

Sharing secrets in plain sight!

I Suppose two of you want to share a secret...

I But you can only shout messages.. can you still get something private?

I which others will not be able to figure out at once?

A game of spies...

Start by choosing a prime 13, a generator for (Z13\ {0},×₁₃)=6.

I A and B pick two secret numbers from 1 to 13, saya,b.

I A computes 6^a mod 13 =M.

I B computes 6^b mod 13 =N.

I Shout/send M and N over.

I A computes N^a mod 13 =s.

I B computes M^b mod 13 =t.

I s=t!

Why does this work?

I Because M^b mod 13 = 6^ab mod 13 =N^a mod 13.

I And computing this from just 6, 13, 6^a mod 13 and 6^b mod 13 is hard without knowing aand b.

A game of spies...

Start by choosing a prime 13, a generator for (Z13\ {0},×₁₃)=6.

I A and B pick two secret numbers from 1 to 13, saya,b.

I A computes 6^a mod 13 =M.

I B computes 6^b mod 13 =N.

I Shout/send M and N over.

I A computes N^a mod 13 =s.

I B computes M^b mod 13 =t.

I s=t!

Why does this work?

I Because M^b mod 13 = 6^ab mod 13 =N^a mod 13.

I And computing this from just 6, 13, 6^a mod 13 and 6^b mod 13 is hard without knowing aand b.

A game of spies...

Start by choosing a prime 13, a generator for (Z13\ {0},×₁₃)=6.

I A and B pick two secret numbers from 1 to 13, saya,b.

I A computes 6^a mod 13 =M.

I B computes 6^b mod 13 =N.

I Shout/send M and N over.

I A computes N^a mod 13 =s.

I B computes M^b mod 13 =t.

I s=t!

Why does this work?

I Because M^b mod 13 = 6^ab mod 13 =N^a mod 13.

I And computing this from just 6, 13, 6^a mod 13 and 6^b mod 13 is hard without knowing aand b.

A game of spies...

Start by choosing a prime 13, a generator for (Z13\ {0},×₁₃)=6.

I A and B pick two secret numbers from 1 to 13, saya,b.

I A computes 6^a mod 13 =M.

I B computes 6^b mod 13 =N.

I Shout/send M and N over.

I A computes N^a mod 13 =s.

I B computes M^b mod 13 =t.

I s=t!

Why does this work?

I Because M^b mod 13 = 6^ab mod 13 =N^a mod 13.

I And computing this from just 6, 13, 6^a mod 13 and 6^b mod 13 is hard without knowing aand b.

A game of spies...

Start by choosing a prime 13, a generator for (Z13\ {0},×₁₃)=6.

I A and B pick two secret numbers from 1 to 13, saya,b.

I A computes 6^a mod 13 =M.

I B computes 6^b mod 13 =N.

I Shout/send M and N over.

I A computes N^a mod 13 =s.

I B computes M^b mod 13 =t.

I s=t!

Why does this work?

I Because M^b mod 13 = 6^ab mod 13 =N^a mod 13.

I And computing this from just 6, 13, 6^a mod 13 and 6^b mod 13 is hard without knowing aand b.

A game of spies...

Start by choosing a prime 13, a generator for (Z13\ {0},×₁₃)=6.

I A and B pick two secret numbers from 1 to 13, saya,b.

I A computes 6^a mod 13 =M.

I B computes 6^b mod 13 =N.

I Shout/send M and N over.

I A computes N^a mod 13 =s.

I B computes M^b mod 13 =t.

I s=t!

Why does this work?

I Because M^b mod 13 = 6^ab mod 13 =N^a mod 13.

I And computing this from just 6, 13, 6^a mod 13 and 6^b mod 13 is hard without knowing aand b.

A game of spies...

Start by choosing a prime 13, a generator for (Z13\ {0},×₁₃)=6.

I A and B pick two secret numbers from 1 to 13, saya,b.

I A computes 6^a mod 13 =M.

I B computes 6^b mod 13 =N.

I Shout/send M and N over.

I A computes N^a mod 13 =s.

I B computes M^b mod 13 =t.

I s=t!

Why does this work?

I Because M^b mod 13 = 6^ab mod 13 =N^a mod 13.

I And computing this from just 6, 13, 6^a mod 13 and 6^b mod 13 is hard without knowing aand b.

A game of spies...

Start by choosing a prime 13, a generator for (Z13\ {0},×₁₃)=6.

I A and B pick two secret numbers from 1 to 13, saya,b.

I A computes 6^a mod 13 =M.

I B computes 6^b mod 13 =N.

I Shout/send M and N over.

I A computes N^a mod 13 =s.

I B computes M^b mod 13 =t.

I s=t!

Why does this work?

I Because M^b mod 13 = 6^ab mod 13 =N^a mod 13.

I And computing this from just 6, 13, 6^a mod 13 and 6^b mod 13 is hard without knowing aand b.

A game of spies...

Start by choosing a prime 13, a generator for (Z13\ {0},×₁₃)=6.

I A and B pick two secret numbers from 1 to 13, saya,b.

I A computes 6^a mod 13 =M.

I B computes 6^b mod 13 =N.

I Shout/send M and N over.

I A computes N^a mod 13 =s.

I B computes M^b mod 13 =t.

I s=t!

Why does this work?

I Because M^b mod 13 = 6^ab mod 13 =N^a mod 13.

I And computing this from just 6, 13, 6^a mod 13 and 6^b mod 13 is hard without knowing aand b.

A game of spies...

Start by choosing a prime 13, a generator for (Z13\ {0},×₁₃)=6.

I A and B pick two secret numbers from 1 to 13, saya,b.

I A computes 6^a mod 13 =M.

I B computes 6^b mod 13 =N.

I Shout/send M and N over.

I A computes N^a mod 13 =s.

I B computes M^b mod 13 =t.

I s=t!

Why does this work?

I Because M^b mod 13 = 6^ab mod 13 =N^a mod 13.

I And computing this from just 6, 13, 6^a mod 13 and 6^b mod 13 is hard without knowing aand b.

A game of spies...

1. Choose a prime p and a generatorg from (Zp\ {0},×_p).

2. Alice fixes a private keyα andBob fixes β.

3. Alice computesM =g^α mod p and shouts/sends it.

4. Bob computes N =g^β mod p and sends/shouts it.

5. Alice computesM^α mod pand Bob computes N^β mod p.

Shared Key: g^αβ mod p

I Others know p, g, g^α mod p, g^β mod p.

I But computing g^αβ modp from ONLYthis info, without knowing aand bis hard!! How hard?

I Does there exist a poly-time (in size of digits) algorithm?

I This is called the Diffie-Hellmanproblem. Still open...

I In practice, choose large primes with∼300 digits.

A game of spies...

1. Choose a prime p and a generatorg from (Zp\ {0},×_p).

2. Alice fixes a private keyα andBob fixes β.

3. Alice computesM =g^α mod p and shouts/sends it.

4. Bob computes N =g^β mod p and sends/shouts it.

5. Alice computesM^α mod pand Bob computes N^β mod p.

Shared Key: g^αβ mod p

I Others know p, g, g^α mod p, g^β mod p.

I But computing g^αβ modp from ONLYthis info, without knowing aand bis hard!! How hard?

I Does there exist a poly-time (in size of digits) algorithm?

I This is called the Diffie-Hellmanproblem. Still open...

I In practice, choose large primes with∼300 digits.

A game of spies...

1. Choose a prime p and a generatorg from (Zp\ {0},×_p).

2. Alice fixes a private keyα andBob fixes β.

3. Alice computesM =g^α mod p and shouts/sends it.

4. Bob computes N =g^β mod p and sends/shouts it.

5. Alice computesM^α mod pand Bob computes N^β mod p.

Shared Key: g^αβ mod p

I Others know p, g, g^α mod p, g^β mod p.

I But computing g^αβ modp from ONLYthis info, without knowing aand bis hard!! How hard?

I Does there exist a poly-time (in size of digits) algorithm?

I This is called the Diffie-Hellmanproblem. Still open...

I In practice, choose large primes with∼300 digits.

A game of spies...

1. Choose a prime p and a generatorg from (Zp\ {0},×_p).

2. Alice fixes a private keyα andBob fixes β.

3. Alice computesM =g^α mod p and shouts/sends it.

4. Bob computes N =g^β mod p and sends/shouts it.

5. Alice computesM^α mod pand Bob computes N^β mod p.

Shared Key: g^αβ mod p

I Others know p, g, g^α mod p, g^β mod p.

I But computing g^αβ modp from ONLYthis info, without knowing aand bis hard!!

How hard?

I Does there exist a poly-time (in size of digits) algorithm?

I This is called the Diffie-Hellmanproblem. Still open...

I In practice, choose large primes with∼300 digits.

A game of spies...

1. Choose a prime p and a generatorg from (Zp\ {0},×_p).

2. Alice fixes a private keyα andBob fixes β.

3. Alice computesM =g^α mod p and shouts/sends it.

4. Bob computes N =g^β mod p and sends/shouts it.

5. Alice computesM^α mod pand Bob computes N^β mod p.

Shared Key: g^αβ mod p

I Others know p, g, g^α mod p, g^β mod p.

I But computing g^αβ modp from ONLYthis info, without knowing aand bis hard!! How hard?

I Does there exist a poly-time (in size of digits) algorithm?

I This is called the Diffie-Hellmanproblem. Still open...

I In practice, choose large primes with∼300 digits.

A game of spies...

1. Choose a prime p and a generatorg from (Zp\ {0},×_p).

2. Alice fixes a private keyα andBob fixes β.

3. Alice computesM =g^α mod p and shouts/sends it.

4. Bob computes N =g^β mod p and sends/shouts it.

5. Alice computesM^α mod pand Bob computes N^β mod p.

Shared Key: g^αβ mod p

I Others know p, g, g^α mod p, g^β mod p.

I But computing g^αβ modp from ONLYthis info, without knowing aand bis hard!! How hard?

I Does there exist a poly-time (in size of digits) algorithm?

I This is called the Diffie-Hellmanproblem. Still open...

I In practice, choose large primes with∼300 digits.

A game of spies...

1. Choose a prime p and a generatorg from (Zp\ {0},×_p).

2. Alice fixes a private keyα andBob fixes β.

3. Alice computesM =g^α mod p and shouts/sends it.

4. Bob computes N =g^β mod p and sends/shouts it.

5. Alice computesM^α mod pand Bob computes N^β mod p.

Shared Key: g^αβ mod p

I Others know p, g, g^α mod p, g^β mod p.

I But computing g^αβ modp from ONLYthis info, without knowing aand bis hard!! How hard?

I Does there exist a poly-time (in size of digits) algorithm?

I This is called the Diffie-Hellmanproblem. Still open...

I In practice, choose large primes with∼300 digits.

A game of spies...

1. Choose a prime p and a generatorg from (Zp\ {0},×_p).

2. Alice fixes a private keyα andBob fixes β.

3. Alice computesM =g^α mod p and shouts/sends it.

4. Bob computes N =g^β mod p and sends/shouts it.

5. Alice computesM^α mod pand Bob computes N^β mod p.

Shared Key: g^αβ mod p

I Others know p, g, g^α mod p, g^β mod p.

I But computing g^αβ modp from ONLYthis info, without knowing aand bis hard!! How hard?

I Does there exist a poly-time (in size of digits) algorithm?

I This is called the Diffie-Hellmanproblem. Still open...

I In practice, choose large primes with∼300 digits.

More generally...

Start with any finite cyclic groupG and generator g ∈G 1. Alice picks a randoma∈Nand sends g^a toBob.

2. Bob picks a random b∈Nand sends g^b toAlice.

3. Alice computes (g^b)^a andBob computes (g^a)^b. 4. Shared key is g^ab.

I Of course, if we know modular logarithm we could do it!

I i.e., if g^a=g⁰ and g andg⁰ are given, what is a?

I Called thediscrete logarithm problem and it is also open!

I What is a naive algorithm? Why does it not work?

I But there exists aquantum algorithm which runs in poly time!

Sending messages with Diffie-Hellman

Start with any finite cyclic groupG and generator g ∈G 1. Alice picks a randoma∈Nand sends g^a toBob.

2. Bob picks a random b∈Nand sends g^b toAlice.

3. Alice computes (g^b)^a andBob computes (g^a)^b. 4. Shared key is g^ab.

I Alice encrypts messagemasmg^ab and sends it.

I So to decrypt it Bob needs to compute (g^ab)⁻¹.

I So Bob computes:

(g^a)^|G|−b=g^a|G|−ab= (g^|G|)^a(g^−ab) =e^a(g^−ab) = (g^ab)⁻¹ – Application of Lagrange’s theorem!

I Then Bob just applies this on msg received.

I That is, mg^ab(g^ab)⁻¹=m·e=m.

Sending messages with Diffie-Hellman

Start with any finite cyclic groupG and generator g ∈G 1. Alice picks a randoma∈Nand sends g^a toBob.

2. Bob picks a random b∈Nand sends g^b toAlice.

3. Alice computes (g^b)^a andBob computes (g^a)^b. 4. Shared key is g^ab.

I Alice encrypts messagem asmg^ab and sends it.

I So to decrypt it Bob needs to compute (g^ab)⁻¹.

I So Bob computes:

(g^a)^|G|−b=g^a|G|−ab= (g^|G|)^a(g^−ab) =e^a(g^−ab) = (g^ab)⁻¹ – Application of Lagrange’s theorem!

I Then Bob just applies this on msg received.

I That is, mg^ab(g^ab)⁻¹=m·e=m.

Sending messages with Diffie-Hellman

Start with any finite cyclic groupG and generator g ∈G 1. Alice picks a randoma∈Nand sends g^a toBob.

2. Bob picks a random b∈Nand sends g^b toAlice.

3. Alice computes (g^b)^a andBob computes (g^a)^b. 4. Shared key is g^ab.

I Alice encrypts messagem asmg^ab and sends it.

I So to decrypt it Bob needs to compute (g^ab)⁻¹.

I So Bob computes:

(g^a)^|G|−b=g^a|G|−ab= (g^|G|)^a(g^−ab) =e^a(g^−ab) = (g^ab)⁻¹ – Application of Lagrange’s theorem!

I Then Bob just applies this on msg received.

I That is, mg^ab(g^ab)⁻¹=m·e=m.

Sending messages with Diffie-Hellman

Start with any finite cyclic groupG and generator g ∈G 1. Alice picks a randoma∈Nand sends g^a toBob.

2. Bob picks a random b∈Nand sends g^b toAlice.

3. Alice computes (g^b)^a andBob computes (g^a)^b. 4. Shared key is g^ab.

I Alice encrypts messagem asmg^ab and sends it.

I So to decrypt it Bob needs to compute (g^ab)⁻¹.

I So Bob computes:

(g^a)^|G|−b=g^a|G|−ab= (g^|G|)^a(g^−ab) =e^a(g^−ab) = (g^ab)⁻¹ – Application of Lagrange’s theorem!

I Then Bob just applies this on msg received.

I That is, mg^ab(g^ab)⁻¹=m·e=m.

Sending messages with Diffie-Hellman

Start with any finite cyclic groupG and generator g ∈G 1. Alice picks a randoma∈Nand sends g^a toBob.

2. Bob picks a random b∈Nand sends g^b toAlice.

3. Alice computes (g^b)^a andBob computes (g^a)^b. 4. Shared key is g^ab.

I Alice encrypts messagem asmg^ab and sends it.

I So to decrypt it Bob needs to compute (g^ab)⁻¹.

I So Bob computes:

(g^a)^|G|−b=

g^a|G|−ab= (g^|G|)^a(g^−ab) =e^a(g^−ab) = (g^ab)⁻¹ – Application of Lagrange’s theorem!

I Then Bob just applies this on msg received.

I That is, mg^ab(g^ab)⁻¹=m·e=m.

Sending messages with Diffie-Hellman

Start with any finite cyclic groupG and generator g ∈G 1. Alice picks a randoma∈Nand sends g^a toBob.

2. Bob picks a random b∈Nand sends g^b toAlice.

3. Alice computes (g^b)^a andBob computes (g^a)^b. 4. Shared key is g^ab.

I Alice encrypts messagem asmg^ab and sends it.

I So to decrypt it Bob needs to compute (g^ab)⁻¹.

I So Bob computes:

(g^a)^|G|−b=g^a|G|−ab= (g^|G|)^a(g^−ab) =e^a(g^−ab) = (g^ab)⁻¹ – Application of Lagrange’s theorem!

I Then Bob just applies this on msg received.

I That is, mg^ab(g^ab)⁻¹=m·e=m.

Sending messages with Diffie-Hellman

Start with any finite cyclic groupG and generator g ∈G 1. Alice picks a randoma∈Nand sends g^a toBob.

2. Bob picks a random b∈Nand sends g^b toAlice.

3. Alice computes (g^b)^a andBob computes (g^a)^b. 4. Shared key is g^ab.

I Alice encrypts messagem asmg^ab and sends it.

I So to decrypt it Bob needs to compute (g^ab)⁻¹.

I So Bob computes:

(g^a)^|G|−b=g^a|G|−ab= (g^|G|)^a(g^−ab) =e^a(g^−ab) = (g^ab)⁻¹ – Application of Lagrange’s theorem!

I Then Bob just applies this on msg received.

I That is, mg^ab(g^ab)⁻¹=m·e=m.

Sending messages with Diffie-Hellman

Start with any finite cyclic groupG and generator g ∈G 1. Alice picks a randoma∈Nand sends g^a toBob.

2. Bob picks a random b∈Nand sends g^b toAlice.

3. Alice computes (g^b)^a andBob computes (g^a)^b. 4. Shared key is g^ab.

I Alice encrypts messagem asmg^ab and sends it.

I So to decrypt it Bob needs to compute (g^ab)⁻¹.

I So Bob computes:

(g^a)^|G|−b=g^a|G|−ab= (g^|G|)^a(g^−ab) =e^a(g^−ab) = (g^ab)⁻¹ – Application of Lagrange’s theorem!

I Then Bob just applies this on msg received.

I That is, mg^ab(g^ab)⁻¹=m·e=m.

Diffie-Hellman Key Exchange protocol

I This was discovered by Diffie & Hellman in 1976.

I Considered to be first cryptographic protocol.

I Variants of this are still used everywhere!

I Digital signatures for Sony Playstations.

I GNU Privacy guard, PGP (pretty good privacy)...

I Which cyclic group?

I Replace (Zp\ {0},×_p) by cyclic group of points ofelliptic curves.

– Elliptic Curve Diffie-HellmanCyptography.

More properties of modular arithmetic & group theory

Definition

For integersa, b and positive integerm, ifm|(a−b), then we say thatais congruent to bmodulo m, denoted a≡b mod m.

I (Zp\ {0},×_p) is a group.

I What are its elements? Zp\ {0}={1,2, . . . , p−1}

I What is the order of this group? p−1.

I What about (Zn\ {0},×_n)? Which elements have inverses?

I Only those co-prime to n(i.e.,a|gcd(a, n) = 1) because,

I ifgcd(a, n) = 1 then∃r, ss.t., ar+ns=gcd(a, n) = 1. Again impliesar≡1 modn, i.e., ris inverse ofa modn.

I Thus, numbers co-prime to n, denoted Coprime(Zn) form a group under ×_n. Check!

I The number of elements co-prime ton, i.e., |Coprime(Z_n)| is denoted φ(n) – called theEuler totient no./function.

More properties of modular arithmetic & group theory

Definition

For integersa, b and positive integerm, ifm|(a−b), then we say thatais congruent to bmodulo m, denoted a≡b mod m.

I (Zp\ {0},×_p) is a group.

I What are its elements?

Zp\ {0}={1,2, . . . , p−1}

I What is the order of this group? p−1.

I What about (Zn\ {0},×_n)? Which elements have inverses?

I Only those co-prime to n(i.e.,a|gcd(a, n) = 1) because,

I ifgcd(a, n) = 1 then∃r, ss.t., ar+ns=gcd(a, n) = 1. Again impliesar≡1 modn, i.e., ris inverse ofa modn.

I Thus, numbers co-prime to n, denoted Coprime(Zn) form a group under ×_n. Check!

I The number of elements co-prime ton, i.e., |Coprime(Z_n)| is denoted φ(n) – called theEuler totient no./function.

More properties of modular arithmetic & group theory

Definition

For integersa, b and positive integerm, ifm|(a−b), then we say thatais congruent to bmodulo m, denoted a≡b mod m.

I (Zp\ {0},×_p) is a group.

I What are its elements? Zp\ {0}={1,2, . . . , p−1}

I What is the order of this group?

p−1.

I What about (Zn\ {0},×_n)? Which elements have inverses?

I Only those co-prime to n(i.e.,a|gcd(a, n) = 1) because,

I ifgcd(a, n) = 1 then∃r, ss.t., ar+ns=gcd(a, n) = 1. Again impliesar≡1 modn, i.e., ris inverse ofa modn.

I Thus, numbers co-prime to n, denoted Coprime(Zn) form a group under ×_n. Check!

I The number of elements co-prime ton, i.e., |Coprime(Z_n)| is denoted φ(n) – called theEuler totient no./function.

More properties of modular arithmetic & group theory

Definition

For integersa, b and positive integerm, ifm|(a−b), then we say thatais congruent to bmodulo m, denoted a≡b mod m.

I (Zp\ {0},×_p) is a group.

I What are its elements? Zp\ {0}={1,2, . . . , p−1}

I What is the order of this group? p−1.

I What about (Zn\ {0},×_n)? Which elements have inverses?

I Only those co-prime to n(i.e.,a|gcd(a, n) = 1) because,

I ifgcd(a, n) = 1 then∃r, ss.t., ar+ns=gcd(a, n) = 1. Again impliesar≡1 modn, i.e., ris inverse ofa modn.

I Thus, numbers co-prime to n, denoted Coprime(Zn) form a group under ×_n. Check!

I The number of elements co-prime ton, i.e., |Coprime(Z_n)| is denoted φ(n) – called theEuler totient no./function.

More properties of modular arithmetic & group theory

Definition

For integersa, b and positive integerm, ifm|(a−b), then we say thatais congruent to bmodulo m, denoted a≡b mod m.

I (Zp\ {0},×_p) is a group.

I What are its elements? Zp\ {0}={1,2, . . . , p−1}

I What is the order of this group? p−1.

I What about (Zn\ {0},×_n)? Which elements have inverses?

I Only those co-prime to n(i.e.,a|gcd(a, n) = 1) because,

I ifgcd(a, n) = 1 then∃r, ss.t., ar+ns=gcd(a, n) = 1. Again impliesar≡1 modn, i.e., ris inverse ofa modn.

I Thus, numbers co-prime to n, denoted Coprime(Zn) form a group under ×_n. Check!

I The number of elements co-prime ton, i.e., |Coprime(Z_n)| is denoted φ(n) – called theEuler totient no./function.

More properties of modular arithmetic & group theory

Definition

For integersa, b and positive integerm, ifm|(a−b), then we say thatais congruent to bmodulo m, denoted a≡b mod m.

I (Zp\ {0},×_p) is a group.

I What are its elements? Zp\ {0}={1,2, . . . , p−1}

I What is the order of this group? p−1.

I What about (Zn\ {0},×_n)? Which elements have inverses?

I Only those co-prime to n(i.e.,a|gcd(a, n) = 1)

because,

I ifgcd(a, n) = 1 then∃r, ss.t., ar+ns=gcd(a, n) = 1. Again impliesar≡1 modn, i.e., ris inverse ofa modn.

I Thus, numbers co-prime to n, denoted Coprime(Zn) form a group under ×_n. Check!

I The number of elements co-prime ton, i.e., |Coprime(Z_n)| is denoted φ(n) – called theEuler totient no./function.

More properties of modular arithmetic & group theory

Definition

For integersa, b and positive integerm, ifm|(a−b), then we say thatais congruent to bmodulo m, denoted a≡b mod m.

I (Zp\ {0},×_p) is a group.

I What are its elements? Zp\ {0}={1,2, . . . , p−1}

I What is the order of this group? p−1.

I What about (Zn\ {0},×_n)? Which elements have inverses?

I Only those co-prime to n(i.e.,a|gcd(a, n) = 1) because,

I ifgcd(a, n) = 1 then∃r, ss.t., ar+ns=gcd(a, n) = 1.

Again impliesar≡1 modn, i.e., ris inverse ofa modn.

I Thus, numbers co-prime to n, denoted Coprime(Zn) form a group under ×_n. Check!

I The number of elements co-prime ton, i.e., |Coprime(Z_n)| is denoted φ(n) – called theEuler totient no./function.

More properties of modular arithmetic & group theory

Definition

For integersa, b and positive integerm, ifm|(a−b), then we say thatais congruent to bmodulo m, denoted a≡b mod m.

I (Zp\ {0},×_p) is a group.

I What are its elements? Zp\ {0}={1,2, . . . , p−1}

I What is the order of this group? p−1.

I What about (Zn\ {0},×_n)? Which elements have inverses?

I Only those co-prime to n(i.e.,a|gcd(a, n) = 1) because,

I ifgcd(a, n) = 1 then∃r, ss.t., ar+ns=gcd(a, n) = 1.

Again impliesar≡1 modn, i.e., ris inverse ofa modn.

I Thus, numbers co-prime to n, denoted Coprime(Zn) form a group under ×_n. Check!

I The number of elements co-prime ton, i.e., |Coprime(Z_n)| is denoted φ(n) – called theEuler totient no./function.

More properties of modular arithmetic & group theory

Definition

For integersa, b and positive integerm, ifm|(a−b), then we say thatais congruent to bmodulo m, denoted a≡b mod m.

I (Zp\ {0},×_p) is a group.

I What are its elements? Zp\ {0}={1,2, . . . , p−1}

I What is the order of this group? p−1.

I What about (Zn\ {0},×_n)? Which elements have inverses?

I Only those co-prime to n(i.e.,a|gcd(a, n) = 1) because,

I ifgcd(a, n) = 1 then∃r, ss.t., ar+ns=gcd(a, n) = 1.

Again impliesar≡1 modn, i.e., ris inverse ofa modn.

I Thus, numbers co-prime to n, denoted Coprime(Zn) form a group under ×_n. Check!

I The number of elements co-prime ton, i.e., |Coprime(Z_n)|

Properties of the Euler Totient function

I ∀n∈Z⁺,Coprime(Zn) denotes numbers coprime ton.

I (Coprime(Zn),×_n)is a group, where a×_nb=ab mod n.

I Order of this group is

Properties of the Euler Totient function

I ∀n∈Z⁺,Coprime(Zn) denotes numbers coprime ton.

I (Coprime(Zn),×_n)is a group, where a×_nb=ab mod n.

I Order of this group is φ(n), no. of elements co-prime to n.

Properties of the Euler Totient function

I ∀n∈Z⁺,Coprime(Zn) denotes numbers coprime ton.

I (Coprime(Zn),×_n)is a group, where a×_nb=ab mod n.

I Order of this group is φ(n), no. of elements co-prime to n.

Exercises

1. Supposep is a prime, what is (Coprime(Zp),×_p)?

2. What is φ(p)?

3. Supposen=pq is a product of primes, what is φ(pq), i.e., how many numbers are there co-prime topq in{1, . . . , pq}?

Properties of the Euler Totient function

I ∀n∈Z⁺,Coprime(Zn) denotes numbers coprime ton.

I (Coprime(Zn),×_n)is a group, where a×_nb=ab mod n.

I Order of this group is φ(n), no. of elements co-prime to n.

Exercises

1. Supposep is a prime, what is (Coprime(Zp),×_p)?

2. What is φ(p)?

3. Supposen=pq is a product of primes, what is φ(pq), i.e., how many numbers are there co-prime topq in{1, . . . , pq}?

4. (Euler’s theorem) Ifgcd(a, n) = 1, then a^φ(n)≡1 mod n.

Properties of the Euler Totient function

I ∀n∈Z⁺,Coprime(Zn) denotes numbers coprime ton.

I (Coprime(Zn),×_n)is a group, where a×_nb=ab mod n.

I Order of this group is φ(n), no. of elements co-prime to n.

Exercises

1. Supposep is a prime, what is (Coprime(Zp),×_p)?

– the usual (Zp,×_p) 2. What is φ(p)? p−1

3. Supposen=pq is a product of primes, what is φ(pq), i.e., how many numbers are there co-prime topq in{1, . . . , pq}?

φ(pq) = (p−1)(q−1)

4. (Euler’s theorem) Ifgcd(a, n) = 1, then a^φ(n)≡1 mod n.

Properties of the Euler Totient function

I ∀n∈Z⁺,Coprime(Zn) denotes numbers coprime ton.

I (Coprime(Zn),×_n)is a group, where a×_nb=ab mod n.

I Order of this group is φ(n), no. of elements co-prime to n.

Exercises

1. Supposep is a prime, what is (Coprime(Zp),×_p)?

2. What is φ(p)?

3. Supposen=pq is a product of primes, what is φ(pq), i.e., how many numbers are there co-prime topq in{1, . . . , pq}?

φ(pq) = (p−1)(q−1)

4. (Euler’s theorem) Ifgcd(a, n) = 1, then a^φ(n)≡1 mod n.

I Letgcd(a, n) = 1,φ(n) =|(Coprime(Zn),×n)|

Properties of the Euler Totient function

I ∀n∈Z⁺,Coprime(Zn) denotes numbers coprime ton.

I (Coprime(Zn),×_n)is a group, where a×_nb=ab mod n.

I Order of this group is φ(n), no. of elements co-prime to n.

Exercises

1. Supposep is a prime, what is (Coprime(Zp),×_p)?

2. What is φ(p)?

3. Supposen=pq is a product of primes, what is φ(pq), i.e., how many numbers are there co-prime topq in{1, . . . , pq}?

φ(pq) = (p−1)(q−1)

4. (Euler’s theorem) Ifgcd(a, n) = 1, then a^φ(n)≡1 mod n.

I Letgcd(a, n) = 1,φ(n) =|(Coprime(Zn),×n)|

I By Lagrange’s theorem, order of elementadivides order of this group, i.e.,a(ord.of grp)=(idof this grp).

Properties of the Euler Totient function

I ∀n∈Z⁺,Coprime(Zn) denotes numbers coprime ton.

I (Coprime(Zn),×_n)is a group, where a×_nb=ab mod n.

I Order of this group is φ(n), no. of elements co-prime to n.

Exercises

1. Supposep is a prime, what is (Coprime(Zp),×_p)?

2. What is φ(p)?

3. Supposen=pq is a product of primes, what is φ(pq), i.e., how many numbers are there co-prime topq in{1, . . . , pq}?

φ(pq) = (p−1)(q−1)

4. (Euler’s theorem) Ifgcd(a, n) = 1, then a^φ(n)≡1 mod n.

I Letgcd(a, n) = 1,φ(n) =|(Coprime(Zn),×n)|

I By Lagrange’s theorem, order of elementadivides order of

Sharing secrets in plain sight! Part 2: Redux

I Alice wants to send a message M (a number, lets say between 1 and 20000) to Bob that only he can figure out.

I But any message can be intercepted (hacker: Carol!)

I How can Bob ensure privacy of messages?

Bob starts by choosing two large primesp, q

Also chooses numbersDand E such thatED≡1 mod φ(pq) (i.e.,φ(pq)|(ED−1)).

1. Bob shouts outN =pqand E (encryptor!)... 2. But he keepsp, q and the decryptorD secret.

3. Alice wants to send messageM < p, q that onlyBob understands. What does she send?

4. Alice sendsX =M^E mod N

5. Bob can decrypt it by: X^D =M^ED mod N =M^1+mφ(pq) mod pq=M (byEuler’s theorem)

Sharing secrets in plain sight! Part 2: Redux

I Alice wants to send a message M (a number, lets say between 1 and 20000) to Bob that only he can figure out.

I But any message can be intercepted (hacker: Carol!)

I How can Bob ensure privacy of messages?

Bob starts by choosing two large primesp, q

Also chooses numbersDand E such thatED≡1 mod φ(pq) (i.e.,φ(pq)|(ED−1)).

1. Bob shouts outN =pqand E (encryptor!)... 2. But he keepsp, q and the decryptorD secret.

3. Alice wants to send messageM < p, q that onlyBob understands. What does she send?

4. Alice sendsX =M^E mod N

5. Bob can decrypt it by: X^D =M^ED mod N =M^1+mφ(pq) mod pq=M (byEuler’s theorem)

Sharing secrets in plain sight! Part 2: Redux

I Alice wants to send a message M (a number, lets say between 1 and 20000) to Bob that only he can figure out.

I But any message can be intercepted (hacker: Carol!)

I How can Bob ensure privacy of messages?

Bob starts by choosing two large primesp, q

Also chooses numbersDand E such thatED≡1 mod φ(pq) (i.e.,φ(pq)|(ED−1)).

1. Bob shouts outN =pqand E (encryptor!)...

2. But he keepsp, q and the decryptorD secret.

3. Alice wants to send messageM < p, q that onlyBob understands. What does she send?

4. Alice sendsX =M^E mod N

5. Bob can decrypt it by: X^D =M^ED mod N =M^1+mφ(pq) mod pq=M (byEuler’s theorem)

Sharing secrets in plain sight! Part 2: Redux

I Alice wants to send a message M (a number, lets say between 1 and 20000) to Bob that only he can figure out.

I But any message can be intercepted (hacker: Carol!)

I How can Bob ensure privacy of messages?

Bob starts by choosing two large primesp, q

Also chooses numbersDand E such thatED≡1 mod φ(pq) (i.e.,φ(pq)|(ED−1)).

1. Bob shouts outN =pqand E (encryptor!)...

2. But he keepsp, q and the decryptorD secret.

3. Alice wants to send messageM < p, q that onlyBob understands. What does she send?

4. Alice sendsX =M^E mod N

5. Bob can decrypt it by: X^D =M^ED mod N =M^1+mφ(pq) mod pq=M (byEuler’s theorem)

Sharing secrets in plain sight! Part 2: Redux

I Alice wants to send a message M (a number, lets say between 1 and 20000) to Bob that only he can figure out.

I But any message can be intercepted (hacker: Carol!)

I How can Bob ensure privacy of messages?

Bob starts by choosing two large primesp, q

Also chooses numbersDand E such thatED≡1 mod φ(pq) (i.e.,φ(pq)|(ED−1)).

1. Bob shouts outN =pqand E (encryptor!)...

2. But he keepsp, q and the decryptorD secret.

3. Alice wants to send messageM < p, q that onlyBob understands. What does she send?

4. Alice sendsX =M^E mod N

5. Bob can decrypt it by: X^D =M^ED mod N =M^1+mφ(pq) mod pq=M (byEuler’s theorem)

Sharing secrets in plain sight! Part 2: Redux

I Alice wants to send a message M (a number, lets say between 1 and 20000) to Bob that only he can figure out.

I But any message can be intercepted (hacker: Carol!)

I How can Bob ensure privacy of messages?

Bob starts by choosing two large primesp, q

Also chooses numbersDand E such thatED≡1 mod φ(pq) (i.e.,φ(pq)|(ED−1)).

1. Bob shouts outN =pqand E (encryptor!)...

2. But he keepsp, q and the decryptorD secret.

3. Alice wants to send messageM < p, q that onlyBob understands. What does she send?

4. Alice sendsX =M^E mod N

X^D =M^ED mod N =M^1+mφ(pq) mod pq=M (byEuler’s theorem)

Sharing secrets in plain sight! Part 2: Redux

I Alice wants to send a message M (a number, lets say between 1 and 20000) to Bob that only he can figure out.

I But any message can be intercepted (hacker: Carol!)

I How can Bob ensure privacy of messages?

Bob starts by choosing two large primesp, q

Also chooses numbersDand E such thatED≡1 mod φ(pq) (i.e.,φ(pq)|(ED−1)).

1. Bob shouts outN =pqand E (encryptor!)...

2. But he keepsp, q and the decryptorD secret.

3. Alice wants to send messageM < p, q that onlyBob understands. What does she send?

4. Alice sendsX =M^E mod N

5. Bob can decrypt it by: X^D =M^ED mod N =M^1+mφ(pq) mod pq=M (byEuler’s theorem)

RSA cryptography

Why does this work?

I Because Carol knows only X, N, Eand has to solve ED≡1 mod φ(N) to obtain Dafter computing φ(N).

I But there is no known fastway to get φ(N) fromN.

I Only known way is to factorize N and finding a poly-time algo for this is open!

Figure:Rivest, Shamir, Addleman, 1977 - Turing Award in 2002

RSA cryptography

Why does this work?

I Because Carol knows only X, N, Eand has to solve ED≡1 mod φ(N) to obtain Dafter computing φ(N).

I But there is no known fastway to get φ(N) fromN.

I Only known way is to factorize N and finding a poly-time algo for this is open!

Figure:Rivest, Shamir, Addleman, 1977 - Turing Award in 2002

RSA cryptography

Why does this work?

I Because Carol knows only X, N, Eand has to solve ED≡1 mod φ(N) to obtain Dafter computing φ(N).

I But there is no known fastway to get φ(N) fromN.

I Only known way is to factorize N and finding a poly-time algo for this is open!

Figure:Rivest, Shamir, Addleman, 1977 - Turing Award in 2002

Compare this to Diffie-hellman

Start with any finite cyclic groupG and generator g ∈G 1. Alice picks a randoma∈Nand sends g^a toBob.

2. Bob picks a random b∈Nand sends g^b toAlice.

3. Alice computes (g^b)^a andBob computes (g^a)^b. 4. Shared key is g^ab.

I Of course, we know modular logarithm we could do it!

I i.e., if g^a=g⁰ and g andg⁰ are given, what is a?

I Called thediscrete logarithm problem and it is also open!

Summary

What we covered in this course 1. Mathematical proofs and structures 2. Counting and combinatorics

3. Introduction to graph theory

4. Elements of group theory and applications to number theory