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

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 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 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 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. Share with your friends:

The database is protected by copyright ©sckool.org 2022

send message