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



Download 186.06 Kb.
Page17/24
Date03.05.2017
Size186.06 Kb.
1   ...   13   14   15   16   17   18   19   20   ...   24

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

Download 186.06 Kb.

Share with your friends:
1   ...   13   14   15   16   17   18   19   20   ...   24




The database is protected by copyright ©sckool.org 2020
send message

    Main page