Page 17/24 Date 03.05.2017 Size 186.06 Kb. #18863
Variations and combinations of this technique are used in some modern encryption algos Ex. 3DES, Lucifer (BLOCK CIPHERS) These algorithms can be effective, but have a KEY DISTRIBUTION problem How can key pass between sender and receiver securely? Problem is recursive (must encrypt key; must encrypt key to decrypt key, etc). How can we prevent multiple sender/receivers from reading each other's messages? Need a different key for each user Solution is PUBLIC-KEY cryptography Key has two parts A public part, used for encryption A private part, used for decryption Only receiver should know this Solves distribution problem Each receiver has his/her own pair of keys Don't care who knows public part Since senders don't know private part , they can't read each other's messages RSA is most famous of these algorithms Public Key Cryptography How/why does RSA work? Let E = encryption (public) key operation Let D = decryption (private) key operation D(E(plaintext)) = plaintext E and D operations are inverses All E, D pairs must be distinct Knowing E, it must be VERY difficult to determine D (exponential time) E and D can be created and used in a reasonable amount of time (polynomial time) Public Key Cryptography Theory? Assume plaintext is an integer, M C = ciphertext = ME mod N So E simply is a power We may need to convert our message into an integer (or possibly many integers) first, but this is not difficult – we can simply interpret each block of bits as an integer M = CD mod N Or MED mod N = M So how do we determine E, D and N? Public Key Cryptography Not trivial by any means This is where we need our extremely large integers – 512, 1024 and more bits Process Choose random prime integers X and Y Let N = XY Let PHI = (X-1)(Y-1) Choose another random prime integer (less than PHI and relatively prime to PHI) and call this E Now all that's left is to calculate D We need some number theory to do this We will not worry too much about the theory Public Key Cryptography We must calculate D such that ED mod PHI = 1 This is equivalent to saying ED = 1 + K(PHI), for some K or, rearranging , that 1 = ED – K(PHI) or 1 = (PHI)(-K) + ED Luckily we can solve this using XGCD We know already that GCD(PHI, E) = 1 We also know, using number theory, that GCD(PHI,E) = 1 = (PHI)S + (E)T for some S and T XGCD calculates values for S and T We don't really care about S But T is the value D that we need to complete our code! Let's look at an example Public Key Cryptography X = 7, Y = 11 (random primes) XY = N = 77 (X-1)(Y-1) = PHI = 60 E = 37 (random prime < PHI) Solve the following for D: 37D mod 60 = 1 Converting to form from prev. slides and solve using XGCD: GCD(60,37) = 1 = (60)(-8)+(37)(13) So D = 13 C = M37 mod 77 M = C13 mod 77 Is RSA Feasible? In order for RSA to be useable The keys must be able to be generated in a reasonable (polynomial) amount of time The encryption and decryption must take a reasonable (polynomial) amount of time Breaking the code must take an extremely large (exponential) amount of time Let's look at these one at a time Is RSA Feasible? What things need to be done to create the keys and how long will they take? Long integer multiplication We know this takes Theta(N2), Theta(N1.58) or Theta(NlgN) depending on the algorithm Mod Similar to multiplication GCD and XGCD What is left? Random Prime Generation Random Prime Generation General algorithm: It turns out that the best (current) algorithm is a probabalistic one: Generate random integer X while (!isPrime(X)) Generate random integer X As an alternative, we could instead make sure X is odd and then add 2 at each iteration, since we know all primes other than 2 itself are odd The distribution of primes generated in this way is not as good, but for purposes of RSA it should be fine Random Prime Generation Runtime can be divided into two parts: How many iterations of the loop are necessary (or, how many numbers must be tried)? How long will it take to test the primality of a given number? Overall run-time of this process is the product of 1) and 2) Based on the distribution of primes within all integers , it is likely that a prime will be found within ln(2N) random picks This is linear in N, so it is likely that the loop will iterate N or fewer times Random Prime Generation This is much more difficult: How to determine if a number is prime or composite? Brute force algorithm: Try all possible factors Well not actually ALL need to be tried: From 2 up to square root of X But X is an N bit number, so it can have a value of up to 2N This means that we will need to test up to 2N/2 factors, which will require an excessive amount of time for very large integers If mod takes Theta(N2), our runtime is now Theta(N22N/2) – very poor! Is there a better way? Let's use a probabilistic algorithm Share with your friends:
The database is protected by copyright ©sckool.org 2023
send message
