# These notes are intended for use by students in cs1501 at the University of Pittsburgh and no one else

 Page 17/24 Date 03.05.2017 Size 186.06 Kb. #18863

## Some Encryption Background

• 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

## Public Key Cryptography

• Solution is PUBLIC-KEY cryptography
• Key has two parts
• A public part, used for encryption
• Everyone can know this
• 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
• D is also a power
• 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
• Why?
• 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
• Worst case  N mods
• 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