September 14, 2022

Evaluate the history of cryptography from its origins.? Analyze how cryptography was used and describe how it grew within history.??The writing assignment requires 2 pages to evalua

Evaluate the history of cryptography from its origins. Analyze how cryptography was used and describe how it grew within history. The writing assignment requires 2 pages to evaluate the history. You must use a minimum of three scholarly articles to complete the assignment. The assignment must be properly APA formatted with a separate title and reference page.

Crptography_fullppt_Chapter-02.pdf

Cryptography and Network Security:

Principles and Practice Eighth Edition

Chapter 2

Introduction to Number Theory

Divisibility

• We say that a nonzero b divides a if a = mb for some m,

where a, b, and m are integers

• b divides a if there is no remainder on division

• The notation b | a is commonly used to mean b divides a

• If b | a we say that b is a divisor of a

The positive divisors of 24 are 1, 2, 3, 4, 6, 8, 12, and 24

13 | 182; − 5 | 30; 17 | 289; − 3 | 33; 17 | 0

Properties of Divisibility (1 of 2)

• If a | 1, then a = ±1

• If a | b and b | a, then a = ±b

• Any b ≠ 0 divides 0

• If a | b and b | c, then a | c

11 | 66 and 66 | 198 = 11 | 198

• If b | g and b | h, then b | (mg + nh) for arbitrary integers m

and n

Properties of Divisibility (2 of 2)

• To see this last point, note that:

– If b | g , then g is of the form g = b * g1 for some integer g1

– If b | h , then h is of the form h = b * h1 for some integer h1

• So:

– mg + nh = mbg1 + nbh1 = b * (mg1 + nh1 )

and therefore b divides mg + nh

b = 7; g = 14; h = 63; m = 3; n = 2

7 | 14 and 7 | 63.

To show 7 (3 * 14 + 2 * 63),

we have (3 * 14 + 2 * 63) = 7(3 * 2 + 2 * 9),

and it is obvious that 7 | (7(3 * 2 + 2 * 9)).

Division Algorithm

• Given any positive integer n and any nonnegative integer

a, if we divide a by n we get an integer quotient q and an

integer remainder r that obey the following relationship:

a = qn + r 0 ≤ r < n; q = [a/n]

Figure 2.1 The Relationship a = qn +

r; 0 ≤ r < n

Euclidean Algorithm

• One of the basic techniques of number theory

• Procedure for determining the greatest common divisor of

two positive integers

• Two integers are relatively prime if their only common

positive integer factor is 1

Greatest Common Divisor (GCD)

• The greatest common divisor of a and b is the largest

integer that divides both a and b

• We can use the notation gcd(a,b) to mean the greatest

common divisor of a and b

• We also define gcd(0,0) = 0

• Positive integer c is said to be the gcd of a and b if:

– c is a divisor of a and b

– Any divisor of a and b is a divisor of c

• An equivalent definition is:

gcd(a,b) = max[k, such that k | a and k | b]

GCD

•Because we require that the greatest common divisor be

positive, gcd(a,b) = gcd(a, −b) = gcd(−a,b) = gcd(−a, −b)

• In general, gcd(a,b) = gcd(| a |, | b |)

gcd(60, 24) = gcd(60, − 24) = 12

• Also, because all nonzero integers divide 0, we have

gcd(a,0) = | a |

• We stated that two integers a and b are relatively prime if

their only common positive integer factor is 1; this is

equivalent to saying that a and b are relatively prime if

gcd(a,b) = 1

8 and 15 are relatively prime because the positive divisors of 8 are 1, 2, 4, and 8, and the

positive divisors of 15 are 1, 3, 5, and 15. So 1 is the only integer on both lists.

Figure 2.2 Euclidean Algorithm

Figure 2.3 Euclidean Algorithm

Example: gcd(710, 310)

Table 2.1 Euclidean Algorithm

Example

Modular Arithmetic (1 of 3)

• The modulus

– If a is an integer and n is a positive integer, we define a

mod n to be the remainder when a is divided by n; the

integer n is called the modulus

– Thus, for any integer a:

a = qn + r 0 ≤ r < n; q = [a/ n]

a = [a/ n] * n + ( a mod n)

11 mod 7 = 4; – 11 mod 7 = 3

Modular Arithmetic (2 of 3)

• Congruent modulo n

– Two integers a and b are said to be congruent

modulo n if (a mod n) = (b mod n)

– This is written as a = b(mod n)2

– Note that if a = 0(mod n), then n | a

73 = 4 (mod 23); 21 = −9 (mod 10)

Properties of Congruences

• Congruences have the following properties:

1. a = b (mod n) if n (a – b)

2. a = b (mod n) implies b = a (mod n)

3. a = b (mod n) and b = c (mod n) imply a = c (mod n)

• To demonstrate the first point, if n (a − b), then (a − b) = kn for some k

– So we can write a = b + kn

– Therefore, (a mod n) = (remainder when b + kn is divided by n) =

(remainder when b is divided by n) = (b mod n)

23 = 8 (mod 5) because 23 − 8 = 15 = 5 * 3

−11 = 5 (mod 8) because − 11 − 5 = −16 = 8 * (−2)

81 = 0 (mod 27) because 81 − 0 = 81 = 27 * 3

Modular Arithmetic (3 of 3)

• Modular arithmetic exhibits the following properties:

1. [(a mod n) + (b mod n)] mod n = (a + b) mod n

2. [(a mod n) − (b mod n)] mod n = (a – b) mod n

3. [(a mod n) * (b mod n)] mod n = (a * b) mod n

• We demonstrate the first property:

– Define (a mod n) = ra and (b mod n) = rb. Then we can write a = ra + jn for

some integer j and b = rb + kn for some integer k

– Then:

(a + b) mod n = (ra + jn + rb + kn) mod n

= (ra + rb + (k + j)n) mod n

= (ra + rb) mod n

= [(a mod n) + (b mod n)] mod n

Remaining Properties

• Examples of the three remaining properties:

11 mod 8 = 3; 15 mod 8 = 7

[(11 mod 8) + (15 mod 8)] mod 8 = 10 mod 8 = 2

(11 + 15) mod 8 = 26 mod 8 = 2

[(11 mod 8) − (15 mod 8)] mod 8 = − 4 mod 8 = 4

(11 − 15) mod 8 = − 4 mod 8 = 4

[(11 mod 8) * (15 mod 8)] mod 8 = 21 mod 8 = 5

(11 * 15) mod 8 = 165 mod 8 = 5

Table 2.2 (a) Arithmetic Modulo 8

Table 2.2 (b) Multiplication Modulo 8

Table 2.2 (c) Additive and

Multiplicative Inverse Modulo 8

Table 2.3 Properties of Modular

Arithmetic for Integers in Zn

Property Expression

Commutative Laws (w + x) mod n = (x + w) mod n

(w × x) mod n = (x × w) mod n

Associative Laws [(w + x) + y] mod n = [w + (x + y)] mod n

[(w × x) × y] mod n = [w × (x × y)] mod n

Distributive Law [w × (x + y)] mod n = [(w × x) + (w × y)] mod n

Identities (0 + w) mod n = w mod n

(1 × w) mod n = w mod n

Additive Inverse (−w) For each w  Zn, there exists a z such that w + z  0 mod n

Table 2.4 Extended Euclidean

Algorithm Example

i ri qi xi yi

−1 1759 Blank 1 0

0 550 Blank 0 1

1 109 3 1 −3

2 5 5 −5 16

3 4 21 106 −339

4 1 1 −111 355

5 0 4 Blank Blank

Result: d = 1; x = −111; y = 355

Prime Numbers • Prime numbers only have divisors of 1 and itself

– They cannot be written as a product of other numbers

• Prime numbers are central to number theory

• Any integer a > 1 can be factored in a unique way as

a = p1 a1 * p2

a2 * . . . * pp1 a1

where p1 < p2 < . . . < pt are prime numbers and where each ai is a

positive integer

• This is known as the fundamental theorem of arithmetic

Table 2.5 Primes Under 2000

Fermat’s Theorem

• States the following:

– If p is prime and a is a positive integer not divisible by p

then

ap−1 = 1 (mod p)

• An alternate form is:

– If p is prime and a is a positive integer then

ap = a (mod p)

Table 2.6 Some Values of Euler’s

Totient Function ø(n)

n ɸ (n)

1 1

2 1

3 2

4 2

5 4

6 2

7 6

8 4

9 6

10 4

n ɸ (n)

11 10

12 4

13 12

14 6

15 8

16 8

17 16

18 6

19 18

20 8

n ɸ (n)

21 12

22 10

23 22

24 8

25 20

26 12

27 18

28 12

29 28

30 8

Euler’s Theorem

• States that for every a and n that are relatively prime:

aø(n) = 1(mod n)

• An alternate form is:

aø(n)+1 = a(mod n)

Miller-Rabin Algorithm • Typically used to test a large number for primality

• Algorithm is:

TEST (n)

1. Find integers k, q, with k > 0, q odd, so that (n – 1)=2kq ;

2. Select a random integer a, 1 < a < n – 1 ;

3. if aq mod n = 1 then return (“inconclusive") ;

4. for j = 0 to k – 1 do

5. if (a2jq mod n = n – 1) then return (“inconclusive") ;

6. return (“composite”) ;

Deterministic Primality Algorithm

• Prior to 2002 there was no known method of efficiently

proving the primality of very large numbers

• All of the algorithms in use produced a probabilistic result

• In 2002 Agrawal, Kayal, and Saxena developed an

algorithm that efficiently determines whether a given large

number is prime

– Known as the AKS algorithm

– Does not appear to be as efficient as the Miller-Rabin

algorithm

Chinese Remainder Theorem (CRT)

• Believed to have been

discovered by the Chinese

mathematician Sun-Tsu in

around 100 A.D.

• One of the most useful

results of number theory

• Says it is possible to

reconstruct integers in a

certain range from their

residues modulo a set of

pairwise relatively prime

moduli

• Can be stated in several

ways

• Provides a way to manipulate

(potentially very large)

numbers mod M in terms of

tuples of smaller numbers

– This can be useful when

M is 150 digits or more

– However, it is necessary

to know beforehand the

factorization of M

Table 2.7 Powers of Integers, Modulo 19

Table 2.8 Tables of Discrete

Logarithms, Modulo 19 (1 of 2)

Table 2.8 Tables of Discrete

Logarithms, Modulo 19 (2 of 2)

Summary

• Understand the concept of

divisibility and the division algorithm

• Understand how to use the

Euclidean algorithm to find the

greatest common divisor

• Present an overview of the

concepts of modular arithmetic

• Explain the operation of the

extended Euclidean algorithm

• Discuss key concepts relating to

prime numbers

• Understand Fermat’s theorem

• Understand Euler’s theorem

• Define Euler’s totient function

• Make a presentation on the topic of

testing for primality

• Explain the Chinese remainder theorem

• Define discrete logarithms

This work is protected by United States copyright laws and is

provided solely for the use of instructors in teaching their

courses and assessing student learning. Dissemination or sale of

any part of this work (including on the World Wide Web) will

destroy the integrity of the work and is not permitted. The work

and materials from it should never be made available to students

except by instructors using the accompanying text in their

classes. All recipients of this work are expected to abide by these

restrictions and to honor the intended pedagogical purposes and

the needs of other instructors who rely on these materials.

Collepals.com Plagiarism Free Papers

Are you looking for custom essay writing service or even dissertation writing services? Just request for our write my paper service, and we'll match you with the best essay writer in your subject! With an exceptional team of professional academic experts in a wide range of subjects, we can guarantee you an unrivaled quality of custom-written papers.

Get ZERO PLAGIARISM, HUMAN WRITTEN ESSAYS

Why Hire Collepals.com writers to do your paper?

Quality- We are experienced and have access to ample research materials.

We write plagiarism Free Content

Confidential- We never share or sell your personal information to third parties.

Support-Chat with us today! We are always waiting to answer all your questions.

Evaluate the history of cryptography from its origins.? Analyze how cryptography was used and describe how it grew within history.??The writing assignment requires 2 pages to evalua

Related Posts

With Lulubox Pro APK, users can access premium game features for free. More than 500 million gamers are connected to the service. https://thelulubox

Welcome to NamesBoom, your ultimate destination for all things name-related! Today, we are thrilled to introduce you to our innovative Pokemon Name G

We have rated this property as ‘Low’, because the land value is less than 70% of the property value. This is probably not a great investment in terms