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

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

## 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

## 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
• "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.