Introduction to Cryptography - C839 Unit 3: Number Theory and Asymmetric Cryptography updated

Introduction to Cryptography - C839 Unit 3: Number Theory and Asymmetric Cryptography updatedAsymmetric Cryptography ○ Cryptographic systems that use key pairs which consist of a public key and private key § The public key is made public( for example by publishing it in a directory) and the private key is kept secret. § does not involve exchanging a secret key. § The public key can be used to encrypt messages and only the recipient's private key can decrypt them. Disadvantage of Asymmetric Cryptography Slower than symmetric algorithms advantages of asymmetric encryption § Provides secure way to communicate; § Provides method of validation; § Non-repudiation N ○ denotes the natural numbers. § These are also sometimes called counting numbers. They are 1, 2, 3, etc. Z ○ denotes the integers. § These are whole numbers -1, 0, 1, 2, etc. The natural numbers combined with Zero and the negative numbers. Q ○denotes the rational numbers (ratios of integers). § Any number that can be expressed as a ratio of two integers. § Examples are: 3/2, 17/4, 1/5. R denotes imaginary numbers. § These are numbers whose square is a negative. § √(−1)=1i Information Theory Developed by Claude Shannon in 1984 with the publication of his article "A mathematical Theory of communication". Diffusion literally means having changes to one character in plaintext affect multiple characters in the ciphertext. Confusion Attempts to make the relationship between the statistical frequencies of the ciphertext and the actual key as complex as possible. ® This occurs by using a complex substitution algorithm. Avalanche This term means that a small change yields large effects in the output ® This is a Fiestel's variation on Claude Shannon's concept of diffusion. ® A high _________ impact is desirable in any cryptographic algorithm. ®Ideally, a change in one bit in the plaintext would affect all the bits of the ciphertext. This would be a complete ____________. Entropy a measure of the uncertainty associated with a random variable Prime Numbers ○ Any number whose factors are 1 and itself. § For example; 2, 3, 5, 7, 11, 13, 17, 23, etc. § Used in some public key cryptography algorithms such as RSA. Prime Number Theorem If a random number N is selected, the chance of it being prime is approximately 1/ln⁡(N) where ln(N) denotes the natural logarithm of N. § Basically tells you that the larger the number you select at random, the less likely it is to be prime. There have been many proposed methods for generating prime Numbers - not an easy thing to do as all methods so far have failed. Mersenne primes § M_(n )−2^n −1 § Where n is a prime number Works for n 2, 3, 5, 7 but fails on n = 11 and on many other n values. Co-prime numbers A number that has no factors in common with another number ( 3 & 7 ) Euler's Totient Counts the positive integers up to a given integer n that are relatively prime to n. For example, 7 has six numbers that are co-prime to it. modulus operator An operator, denoted with a percent sign ( %), that works on integers and yields the remainder when one number is divided by another.