Number Theory 5 Sem.pptx

cryptography

1. Cryptography and Network Security 2 Cryptography and Network Security Introduction Xiang-Yang Li

2. Cryptography and Network Security 3 Introduction The art of war teaches us not on the likelihood of the enemy’s not coming, but on our own readiness to receive him; not on the chance of his not attacking, but rather on the fact that we have made our position unassailable. --The art of War, Sun Tzu

3. Cryptography and Network Security 4 Cryptography Cryptography (from Greek kryptós , "hidden", and gráphein , "to write") is, traditionally, the study of means of converting information from its normal, comprehensible form into an incomprehensible format, rendering it unreadable without secret knowledge — the art of encryption . Past: Cryptography helped ensure secrecy in important communications, such as those of spies, military leaders, and diplomats. In recent decades, cryptography has expanded its remit in two ways mechanisms for more than just keeping secrets: schemes like digital signatures and digital cash, for example. in widespread use by many civilians, and users are not aware of it.

4. Cryptography and Network Security 5 Crypto-graphy, -analysis, -logy The study of how to circumvent the use of cryptography is called cryptanalysis , or codebreaking . Cryptography and cryptanalysis are sometimes grouped together under the umbrella term cryptology , encompassing the entire subject. In practice, "cryptography" is also often used to refer to the field as a whole; crypto is an informal abbreviation. Cryptography is an interdisciplinary subject, linguistics Mathematics: number theory, information theory, computational complexity, statistics and combinatorics engineering

5. Cryptography and Network Security 6 Close, but different fields Steganography the study of hiding the very existence of a message, and not necessarily the contents of the message itself (for example, microdots, or invisible ink) Traffic analysis which is the analysis of patterns of communication in order to learn secret information.

6. Cryptography and Network Security 7 Network Security Model Trusted Third Party principal principal Security transformation Security transformation attacker

7. Cryptography and Network Security 8 Attacks, Services and Mechanisms Security Attacks Action compromises the information security Security Services Enhances the security of data processing and transferring Security mechanism Detect, prevent and recover from a security attack

8. Cryptography and Network Security 9 Attacks Passive attacks Interception Release of message contents Traffic analysis Active attacks Interruption, modification, fabrication Masquerade Replay Modification Denial of service

9. Cryptography and Network Security 10 Information Transferring

10. Cryptography and Network Security 11 Attack: Interruption Cut wire lines, Jam wireless signals, Drop packets,

11. Cryptography and Network Security 12 Attack: Interception Wiring, eavesdrop

12. Cryptography and Network Security 13 Attack: Modification intercept Replaced info

13. Cryptography and Network Security 14 Attack: Fabrication Also called impersonation

14. Cryptography and Network Security 15 Important Features of Security Confidentiality, also known as secrecy: only an authorized recipient should be able to extract the contents of the message from its encrypted form. Otherwise, it should not be possible to obtain any significant information about the message contents. Integrity: the recipient should be able to determine if the message has been altered during transmission. Authentication: the recipient should be able to identify the sender, and verify that the purported sender actually did send the message. Non-repudiation: the sender should not be able to deny sending the message.

15. Cryptography and Network Security 16 Cryptography Cryptography is the study of Secret (crypto-) writing (-graphy) Concerned with developing algorithms: Conceal the context of some message from all except the sender and recipient (privacy or secrecy), and/or Verify the correctness of a message to the recipient ( authentication ) Form the basis of many technological solutions to computer and communications security problems

16. Cryptography and Network Security 17 Basic Concepts Cryptography encompassing the principles and methods of transforming an intelligible message into one that is unintelligible, and then retransforming that message back to its original form Plaintext The original intelligible message Ciphertext The transformed message Message Is treated as a non-negative integer hereafter

17. Cryptography and Network Security 18 Basic Concepts Cipher An algorithm for transforming an intelligible message into unintelligible by transposition and/or substitution Key Some critical information used by the cipher, known only to the sender & receiver Encipher (encode) The process of converting plaintext to ciphertext Decipher (decode) The process of converting ciphertext back into plaintext

18. Cryptography and Network Security 19 Basic Concepts cipher an algorithm for encryption and decryption. The exact operation of ciphers is normally controlled by a key — some secret piece of information that customizes how the ciphertext is produced Protocols specify the details of how ciphers (and other cryptographic primitives) are to be used to achieve specific tasks. A suite of protocols, ciphers, key management, user-prescribed actions implemented together as a system constitute a cryptosystem ; this is what an end-user interacts with, e.g. PGP

19. Cryptography and Network Security 20 Encryption and Decryption Plaintext ciphertext Encipher C = E (K1) (P) Decipher P = D (K2) (C) K1, K2: from keyspace

20. Cryptography and Network Security 21 Security Two fundamentally different securities Unconditional security No matter how much computer power is available, the cipher cannot be broken Using Shannon’s information theory Computational security Given limited computing resources (e.G time needed for calculations is greater than age of universe), the cipher cannot be broken Proved by some complexity equivalence approach

21. Cryptography and Network Security 22 Cryptography and Network Security Elementary Number Theory Xiang-Yang Li

22. Cryptography and Network Security 23 Number theory Elementary number theory Main topic of this course divisibility, the Euclidean algorithm to compute greatest common divisors, factorization Fermat's little theorem and Euler's theorem, the Chinese remainder theorem and Euler's φ function are investigated; Analytic number theory Algebraic number theory Geometric number theory Computational number theory

23. Cryptography and Network Security 24 Introduction to Number Theory Divisors b|a if a=mb for an integer m b|a and c|b then c|a b|g and b|h then b|(mg+nh) for any integer m,n Prime number P has only positive divisors 1 and p Relatively prime numbers No common divisors for p and q except 1

24. Cryptography and Network Security 25 GCD Greatest common divisor gcd(a,b) The largest number that divides both a and b Euclid's algorithm Find the GCD of two numbers a and b, a<b Use fact if a and b have divisor d so does a-b, a-2b …

25. Cryptography and Network Security 26 Cont. GCD (a,b) is given by: let g =b g 1 =a g i+1 = g i-1 mod g i when g i =0 then gcd(a,b) = g i-1 The algorithm terminates in O( log b) rounds Why? Every round, the total number of bits of a and b is decreased by at least one What is a more precise complexity bound?

26. Cryptography and Network Security 27 Properties For any two integers a and b Exist integers m and n : gcd(a,b) = ma + bn Example: a=2, b=3; we choose m=-1, n=1 so –2+3=1 a=6, b=11; we choose m=2, n=-1 so 2*6-11=1 Simple proof? Integer n can be factored as n = p 1 a 1 p 2 a 2 p 3 a 3…. p n a n where p i is prime number

27. Cryptography and Network Security 28 Extended Euclidean Algorithm input are two integers a and b, computes their greatest common divisor (gcd) as well as integers x and y such that ax  +  by  = gcd( a ,  b ). It later can also be used to compute the inverse of an integer

28. Cryptography and Network Security 29 Proof Assume we compute gcd(x ,y ), x >y Let X i =(x i ,y i ); 0  x i -q i+1 y i+1 <|y i | Then X i =M i X i-1 , where M i =(0,1; 1,-q i ) Assume the gcd algorithm terminates in n steps We have M n M n-1 … M 1 X =(gcd(x ,y ), 0) T Assume M n M n-1 … M 1 =( ) Then ax +by =gcd(x ,y ) The above algorithm is to keep track of a,b,c,d, and x i ,y i values. a b c d

29. Cryptography and Network Security 30 Modular Arithmetic Congruence a  b mod n says when divided by n that a and b have the same remainder It defines a relationship between all integers a  a a  b then b  a a  b, b  c then a  c

30. Cryptography and Network Security 31 Cont. addition (a+b) mod n  (a mod n) + (b mod n) subtraction a-b mod n  a+(-b) mod n multiplication a b mod n derived from repeated addition Possible: a*b  0 where neither a, b  0 mod n Example: 2*3 =0 mod 6

31. Cryptography and Network Security 32 Addition and Multiplication Integers modulo n with addition and multiplication form a commutative ring with the laws of Associativity (a+b)+c  a+(b+c) mod n Commutativity a+b  b+a mod n Distributivity (a+b)*c  (a*c)+(b*c) mod n

32. Cryptography and Network Security 33 Cont. Division b/a mod n multiplied by inverse of a: b/a = b*a -1 mod n a -1* a  1 mod n 3 -1 7 mod 10 because 3*7  1 mod 10 Inverse does not always exist! Only when gcd(a,n)=1

33. Cryptography and Network Security 34 Euclid's Extended GCD Routine If (a,n)=1 then the inverse always exists Can extend Euclid's algorithm to find inverse by keeping track of g i = u i .n + v i .a Extended Euclid's (or binary GCD) algorithm to find inverse of a number a mod n (where (a,n)=1) is:

34. Cryptography and Network Security 35 Inverse Inverse(a,n) is given by: X=(x1,x2,x3)=(1,0,n); Y=(y1,y2,y3)=(0,1,a) If y3=0 return x3=gcd(a,n); no inverse If y3=1 return y3=gcd(a,n); y2=a -1 mod n Q=[x3/y3] T=X-Q*Y X=Y; Y=T Goto 2 nd step

35. Cryptography and Network Security 36 When inverse exists If gcd(a,n)=1  inverse exists We can find x, y such that ax+ny=1 Then x= a -1 mod n If inverse exists gcd(a,n)=1 Let x be the inverse of a, i.e., ax =1 mod n Then x a=1+q n for some integer q Let gcd(a,n)=d. Then d | ( x a-q n ) Obviously d=1 since x a-q n =1

36. Cryptography and Network Security 37 Galois Field If n is constrained to be a prime number p then this forms a Galois field modulo p denoted GF(p) and all the normal laws associated with integer arithmetic work Exponentiation b = a e mod p Discrete Logarithms find x where a x = b mod p

37. Cryptography and Network Security 38 Relative primes Two numbers a and n are relative primes if gcd(a,n)=1 Consider all integers 0<a <n How many are relative prime to n? Equivalently, how many a such that a -1 mod n exists Typically Z n ={0,1,2,….,n-1} : all integers 0<= a < n Z n * ={a| 0<= a < n, gcd(a,n)=1} All integers in Z n that are co-prime with n Also called reduced residue set mod n

38. Cryptography and Network Security 39 Euler Totient Function If consider arithmetic modulo n, then a reduced set of residues is a subset of the complete set of residues modulo n which are relatively prime to n eg for n=10, the complete set of residues is {0,1,2,3,4,5,6,7,8,9} the reduced set of residues is {1,3,7,9} The number of elements in the reduced set of residues is called the Euler Totient function  (n)

39. Cryptography and Network Security 40 cont Compute ( n) If factoring of n is known ( n)= n  (1-1/p i ) where p i is its prime factor Otherwise It is expensive! But not proved yet computing ( n) when knowing fact n =pq but not the number p and q Conjectured to be a hard question But not proved yet. Equivalent to find p and q

40. Cryptography and Network Security 41 cont Equivalency: finding p,q  computing ( n) Proof  If we found p and q, then ( n)=(p-1)(q-1) if we found ( n), then solve p, q from equations

41. Cryptography and Network Security 42 Euler's Theorem Let gcd(a,n)=1 then a ( n) mod n = 1 Proof: consider all reduced residues x i in Z n * ={x| 0<= x < n, gcd(x,n)=1} Then a x i ,1<=i <= ( n) also form reduced residues set Using  a x i =  x i mod n Using Z n * and aZ n * are same sets! We have a ( n)  x i =  x i mod n Thus, a ( n) =1 mod n Using the fact that  x i has inverse

42. Cryptography and Network Security 43 Fermat's Little Theorem Let p be a prime and gcd(a,p)=1 then a p-1 mod p = 1 Proof: similar to the proof of Euler’s theorem But consider all integers in Z p Generally, for any prime number p a p mod p = a (true for any number a) Generally, for any number n=pq a ( n) mod n = a (true for any number a) Need to prove for the case gcd(a,n)>1 Do it yourself

43. Cryptography and Network Security 44 Efficient computing of exponential Compute a b mod n efficiently when b, n large? Example: compute a 1024 mod 2 1024 +1 Simple approach: repetitively time a 1024 times? Efficient computation: Write number b in binary format as x k x k-1 x k-2 …. x 2 x 1 x Let t 1 =a mod n. Then compute t i+1 = t i * t i mod n for i<k Then Time complexity?

44. Cryptography and Network Security 45 Chinese Remainder Theorem By Qin Jiushao Let m 1 ,m 2 ,….m k be pair-wise relative prime numbers Assume integer x= a i mod m i for 1<= I <= k Then x=  a i e i mod M Where M=  m i ; M i =M/ m i e i = M i * (M i -1 mod m i ) Proof For each i , the integers m i and M / m i are coprime, and using the extended Euclidean algorithm we can find integers r and s such that r m i + s M / m i = 1. If we set e i = s M / m i , then we have e i =1 mod m i and e i =1 mod m j for j<>i.

45. Cryptography and Network Security 46 General CRT Sometimes, the simultaneous congruences can be solved even if the m i 's are not pairwise coprime. a solution x exists if and only if a i ≡ a j ( mod gcd( n i , n j )) for all i and j . All solutions x are congruent modulo the least common multiple of the n i . Methods: successive substitution

46. Cryptography and Network Security 47 Example consider the simultaneous congruences x ≡ 3 (mod 4) x ≡ 5 (mod 6) Can be transformed to x ≡ 3 (mod 4) x ≡ 5 (mod 2)  x ≡ 1 (mod 2) x ≡ 5 (mod 3) Then transformed to x ≡ 3 (mod 4) x ≡ 2 (mod 3) Using CRT X=11 (mod 12)

47. Cryptography and Network Security 48 Primality Testing To check if exists integer a such that a|n Primary school method Test a=2,3,4,5,6,….,n-1 Test a=2,3,4,5,…, n 0.5 Test a=2,3,5,7,11,…., p, where prime number p<= n 0.5 Two slow! Check almost n numbers Check n 0.5 numbers At least around ( n/ln n) 0.5 numbers need be checked Example Number n~2 1024 , then ( n/ln n) 0.5 ~ (2 1024 /1024) 0.5 ~ 2 507 Assume 2 30 numbers per second, takes about 2 507-30*16 = 2 27 days Any improvement?

48. Cryptography and Network Security 49 Simple Fact Equation x 2  1 mod p has only solutions 1,-1 If p is prime number Simple proof: (x+1)(x-1)  0 mod p So if we find another solution, then p can not be prime number! Miller and Rabin 1975,1980 Randomly chosen integer a If a 2  1 mod p then p is not prime number Integer a is called the witness Otherwise p maybe, or maybe not a prime number

49. Cryptography and Network Security 50 Witness Algorithm Witness(a,n) Let b k b k-1 …b 1 b be the binary code of n-1 Let d=1 For i=k downto 0 x=d; d=d*d mod n If d=1 and x 1, and x n-1 return TRUE If b i =1 then d=d*a mod n Endfor If d  1 then return TRUE Return FALSE

50. Cryptography and Network Security 51 Facts Analysis the result of witness If returns TRUE, then n is not prime number Find other solutions for x 2  1 mod n Otherwise, n maybe prime number Given odd n and random a Witness fails with probability less than 0.5 Run witness algorithm s times If one time, it is TRUE Then n is not prime number Otherwise, Pr( n is prime)>1-2 -s

51. Cryptography and Network Security 52 Randomized Methods Las Vegas Method Always produces correct results Runs in expected polynomial time Monte Carlo Method Runs in polynomial time May produce incorrect results with bounded probability No-Biased Monte Carlo Method Answer yes is always correct, but the answer no may be wrong Yes-biased Monte Carlo Method Answer no is always correct, but the answer yes may be wrong

52. Cryptography and Network Security 53 Witness Algorithm Witness Algorithm is based on Monte Carlo Method It actually test compositeness, not primality When it reports yes, the number is always composite When it reports no, input may be composite, prime Probability Result Pr(input=composite | ans=composite)= 1 Pr(ans=no | input=composite)<1/2 Pr(input=composite | ans=no)  1/4

53. Cryptography and Network Security 54 Time Complexity Each round of witness cost O( log n ) Unit: integer multiplication and modular arithmetic So the primality testing cost O( s log n ) The confidence is 1-2 -s if report prime The confidence is 1 if report non-prime

54. Cryptography and Network Security 55 Primitive Root Order of integer ord n (a) The order of a modulo n is the smallest positive k such that a k  1 mod n Primitive Root Integer a is a primitive root of n if the order of a modulo n is  (n) Not all integers have primitive root Example n=pq for primes p and q Prime p has  (p-1) primitive roots

55. Cryptography and Network Security 56 cont When primitive root exists Number n in format of p, 2p, p k , 2p k for some integer k and prime number p Otherwise the primitive root does not exist Find a PR for p such that Let a=2, i=1 If i>k, a is a PR, otherwise go to step 3 If let i=i+1 and go to step 2; otherwise let i=1, and a=a+1 and repeat this step 3.

56. Cryptography and Network Security 57 Some “hard” questions Some questions that are assumed to be hard, will be used as bases for cryptography Integer factorization Given n, find all its prime factors Discrete logarithm Given g, y, and p, find x such that g x  y mod p Square root Given b, find x such that x 2  b mod n. Here n is not a prime number

57. Cryptography and Network Security 58 Integer Factorization write an integer as product of prime numbers. For example, given the number 45, the prime factorization would be 3 2 ·5. The factorization is always unique, according to the fundamental theorem of arithmetic Given two large prime numbers, it is easy to multiply them. However, given their product, it appears to be difficult to find the factors. This is relevant for many modern systems in cryptography. If a fast method were found for solving the integer factorization problem, then several important cryptographic systems would be broken. Although fast factoring is one way to break these systems, there may be other ways to break them that don't involve factoring. So it is possible that the integer factorization problem is truly hard, yet these systems can still be broken quickly. A rare exception is the BBS generator. It has been proved to be exactly as hard as integer factorization: if you can break the generator in polynomial time then you can factorize integers in polynomial time, and vice versa

58. Cryptography and Network Security 59 Current state of the art If a large, n -bit number is the product of two primes that are roughly the same size, no polynomial time factoring algorithm is known the best known algorithms are sub-exponential, but super-polynomial: asymptotic running time by the general number field sieve (GNFS) algorithm, is Polynomial methods known for quantum computer!

59. Cryptography and Network Security 60 Factoring algorithms Special purpose its running time depends on the properties of unknown factors: size, special form, etc. Examples Trial division, Pollard's rho algorithm, Pollard's p-1 algorithm, Lenstra elliptic curve factorization, Congruence of squares, Special number field sieve General purpose running time depends solely on the size of the integer to be factored. This is the type of algorithm used to factor RSA numbers. Most general-purpose algorithms are based on the congruence of squares method. Examples: Quadratic sieve, General number field sieve

60. Cryptography and Network Security 61 Discrete Logarithms Y  g x mod p Given y, g, and p, compute x as log g (y) Time complexity O(e (ln p) 1/3 (ln ln p) 2/3 ) Best known until now In other words, if p is large, then it is very hard to solve the discrete logarithm problem Several protocols are based on this ElGamal discrete log cryptosystem, Diffie-Hellman key exchange and the Digital Signature Algorithm. Current methods: the Pohlig-Hellman algorithm if p -1 is a product of small primes, so this should be avoided in those applications

61. Cryptography and Network Security 62 Quadratic Residue Quadratic Residue Integer b is a quadratic residue of modulo integer n if and only if x 2 b mod n has a solution for x Number x is called the square root of b Otherwise b is called quadratic nonresidue Given odd prime p, b is quadratic residue, iff b (p-1)/2 1 mod p b is quadratic nonresidue, iff b (p-1)/2 -1 mod p These facts can be used to test primes with probability

62. Cryptography and Network Security 63 Computing Square root mod p Given number a, find number x, x 2 =a mod p If p=3 mod 4, then x=a (p+1)/4 mod p is a solution. If p=5 mod 8, a (p-1)/4 =1 mod p then x= a (p+3)/8 mod p If p=5 mod 8, a (p-1)/4 =-1 mod p then x= 2a(4a) (p-5)/8 mod p If p=1 mod 8, Here h is an odd number

63. Cryptography and Network Security 64 Compute square-root mod p Find a solution to x 2 =a mod p if exists Let r=0, s=p-1; while s even, {r=r+1; s=s/2;} Choose random n such that Let z=n s mod p; x=a (s+1)/2 mod p; b=a s mod p; If b=1, return x as a solution Let m=1, y=b 2 mod p; while y<>1 {y= y 2 mod p; m=m+1;} If r=m then a is Quadratic non-residue; exit; Let x=xz 2 r-m-1 mod p and b=bz 2 r-m mod p and z=z 2 r-m mod p Go to step 4 The expected running time is O(log 4 p)

64. Cryptography and Network Security 65 Complexity Theory The input length of a problem is the number n of symbols used to characterize it Complexity of a method Function f(n) is order O(g(n)) if f(n)<=c*|g(n)|, for all n>=N , for some c Function f(n) is order  (g(n)) if f(n)>=c*|g(n)|, for all n>=N , for some c Function f(n) is order  (g(n)) if c1*|g(n)|<=f(n)<=c2*|g(n)|, for all n>=N , for some c1 and c2 Polynomial time algorithm ( P ) solves any instance of a particular problem with input length n in time O(p(n)), where p is a polynomial

65. Cryptography and Network Security 66 Cont. Non-deterministic polynomial time algorithm ( NP ) is one for which any guess at the solution of an instance of the problem may be checked for validity in polynomial time. NP-complete problems are a subclass of NP problems for which it is known that if any such problem has a polynomial time solution, then all NP problems have polynomial solutions. Co-NP: the complements of NP problems.