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



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

Random Prime Generation

      • Miller-Rabin Witness algorithm:
      • Do K times
      • Test a (special) random value (a "witness")
      • If it produces a special equality – return true
      • If no value produces the equality – return false
        • If true is ever returned – number is definitely NOT prime, since a factor was found
        • If false is returned all K times, probability that the number is NOT prime is 2-K
          • If we choose K to be reasonably large, there is very little chance of an incorrect answer
      • Run-time?
        • Each test requires  N multiplications
        • Assuming GS algorithm
          • KN3 in the worst case

Random Prime Generation

    • Multiplying 1) and 2) as we stated we get
      • N * KN3 = KN4 if Gradeschool mult is use
      • This is not outstanding, since N4 grows quickly, but in reality the algorithm will usually run much more quickly:
        • A better multiplication alg. (Karatsuba or FFT) can be used
        • A prime may be found in fewer than N tries
        • The Miller-Rabin test may find a factor quickly for some of the numbers, not requiring the full K tests

Time to Use RSA

  • How long does it take to use RSA encryption and decryption?
    • Power-mod operation – raising a very large integer to a very large integer power mod a very large integer
      • Same run-time as the regular power function, and can be done in the same way using the divide and conquer approach
      • Requires Theta(N) multiplications, for a total of Theta(N3) assuming Gradeschool is used
    • This is the dominant time for both encryption and decryption

Time to Break RSA

  • How easily can RSA be broken?
  • Recall that we have 3 values: E, D and N
    • Most obvious way of breaking RSA is to factor N
      • Factoring N gives us X and Y (since N = XY)
      • But PHI = (X-1)(Y-1)
        • Once he/she knows PHI, cryptanalyst can determine D in the same way we generated D
      • So is it feasible to factor N?
        • There is no known polynomial-time factoring algorithm
        • Thus, it will require exponential time to factor N
        • But, with fast computers, it can be done
          • Team from Germany factored 200-decimal digit RSA number last year – but computation was considerable

Time to Break RSA

        • However, if we make N large enough, we can be pretty sure that factoring will not be possible
        • RSA Security recommends 768 bits for moderate security, 1024 bits for normal corporate use and 2048 bits for extremely valuable keys that may be targeted
        • An important thing to remember, is that since the factoring time is still exponential, doubling the size of the key will increase the time to factor it by many thousands/millions/billions of times
          • Yet no one has proven that factoring requires exponential time (although it is widely believed). If someone finds a polynomial factoring algorithm, RSA would be useless!
        • But we should still be careful in choosing keys, and in how long we keep a key
          • See RSA Security FAQ for more info

Time to Break RSA

    • Indirectly breaking a code:
      • If we just want to break one message, and not the keys, there are simple tricks that can be tried
        • For example, say you know all of the possible messages that may be sent
        • We can combat this by padding messages with extra bits (random is best) before sending them
    • Other techniques exist as well
    • Generally, if we are careful and use large keys, RSA is quite secure

RSA Applications

  • Applications
    • Regular data encryption, as we discussed
      • But RSA is relatively slow compared to block ciphers
      • Block ciphers are faster, but have key-distribution problem
      • How can we get the "best of both"?
    • RSA (Digital) Envelope
        • Sender encrypts message using block cipher
        • Sender encrypts block cipher key using RSA
        • Sender sends whole package to receiver
        • Receiver decrypts block cipher key using RSA
        • Receiver uses key to decrypt rest of message

RSA Applications

    • Digital Signatures
      • Notice that E and D are inverses
      • It doesn't matter mathematically which we do first
      • If I DECRYPT my message (with signature appended) and send it, anyone who then ENCRYPTS it can see the original message and verify authenticity
        • Mostly, but there are a few issues to resolve
  • MESSAGE
  • Sender
  • Receiver
  • "DECRYPTED"
  • MESSAGE
  • MESSAGE
  • DECRYPT
  • ENCRYPT

RSA Applications

      • Note in this case that we are NOT trying to keep anyone from reading the message
        • Everyone can get the public key and can thus successfully "encrypt" the message
      • What about the issues to resolve?
        • As with regular encryption, RSA used in this way is a bit slow
        • Can we avoid decrypting and encrypting the entire message?
          • Yes, instead of decrypting the whole message, the sender processes the message using a technique similar to hashing (but more complex). This produces a "signature" for the message and the signature is what we actually "decrypt" using the private key. Then the message and signature are sent to the receiver.

Download 186.06 Kb.

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




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

    Main page