John Nguyen2034CS 265Attacks on Digital Signature Algorithm: RSAAttacks on Digital Signature Algorithm: RSADigital signatures are a means of signing electronic documents. As the world becomes more digital and people begin to move to digital workflows, such online banking and online routing of forms, digital signatures will play a more important role. It would be inconvenient to fill out all of information online, and then one has to send a piece of paper which contains his or her signature through post office. Since people will be able to digitally sign a document, digital signatures must be secure so that people can be sure that the person who signed the document was who they said they were. To sign a document a person must have some thing to uniquely identify himself or herself, that is something only he or she has it and use it. Moreover, people have to be able to verify thesignature which comes from the person who signed. Some public key cryptography offerthat need. They have 2 keys: a private key for signing and a public key for verification incase of digital signature. Some public key algorithms have already been used in implementation of the digital signature, and one of most popular public key algorithms is RSA.RSARSA is a public key algorithm. A message can be encrypted by either public key or private key of RSA. If a message is encrypted with the private key, then that act is called signing the message. Therefore, RSA is one of the Digital Signature algorithms.RSA was named after its three inventors: Ron Rivest, Adi Shamir, and Leonard Adleman.It has become very popular, people have a level of confidence in using it, and it is a de facto standard in much of the world (Schneier,474).The security of it is drawn from factoring large numbers. To generate public key and private key, choose two large prime numbers p and q with equal size (equal size for maximum security), then compute:n = pqThen choose a random number e (as a part of public key) such that e and (p-1)(q-1) are relatively prime, this will ensure the equation below has a solution.Then, private key d can be computed by using extended Euclidean algorithm:ed ≡ 1 mod (p-1)(q-1)So the public key is e and n, and the private key is d. Two prime numbers p and q are gone after finding d, and they should be discarded for security reason. To encrypt a message m, m should be broken up into numerical blocks mi smaller than n. With binary data, choose the largest power of 2 less than n. That is, if both p and q are 2100-digit primes, then n will have just under 200 digits and each message block, mi, should be just under 200 digits long.To encrypt each block mici = mie mod nTo decrypt each block of cipher text:mi = cid mod nTo verify:cid = (mie)d = mied = mik(p-1)(q-1) + 1 = mimik(p-1)(q-1) = mi *1 = mi (mod n)Note: mik(p-1)(q-1) + 1 = mik(n) = mi* 1 (Euler’s generalization of Fermat’s little theorem)This message could be encrypted with private key d, and decrypt it with public key e and n. If keys are used in this manner, the act of encrypting the message with private key d iscalled signing the message.In digital signature:Signing: ci = mi d mod nSignature verification: mi = cie mod nSecurity of RSA and Attacks against it.The first obvious attack against RSA is trying to factor the number n, which is a part of the public key. However, factoring this number is difficult, but this may be done by usingfactoring technology which can be up to 129-decimal-digit modulus. Therefore, to be secure, n must be larger than that number. Another attack is guessing the (p-1)(q-1), but this is as difficult as factoring n.Common attacks against RSA are not attacks against its basic algorithm but against its implementation and its protocol, which means attackers in this case do not try to find the weakness of the algorithm to figure out the private key, but they attacks on how people use it, how the cryptosystem is constructed. In general, the encryption is not sufficient, but the whole cryptosystem must be carefully designed. Below are some of examples of the attacks on the cryptosystem that uses RSA.Chosen Cipher Attack against RSA3Scenario: Eve is an attacker who wants to read the encrypted message c that only Alice can read it with her private key, but so far Eve only got the cipher text message c. What Eve wants is the plaintext m, so Eve does:Choose a random number, r, such that r is less than n, with Alice’s public key e and n, shecan compute:x = re mod ny = xc mod nt = r-1 mod nIf x = re mod n, then r = xd mod n.Now Eve finds away to get Alice to sign y with her private key:u = yd mod nThen Eve can compute:tu mod n = (r-1 mod n)( yd mod n) mod n= r-1 yd mod n = r-1 xd cd mod n = cd mod n = mSo Eve has m.One of possible preventions against this attack is to design the system that Alice only signs the one-way hash function of the message, not the message itself. Signing and encrypting the messages are two different things; these can be safely done by separating them. Signing is usually done first, and the message is then encrypted. This can be done by two set of keys: set 1 for signing and verification signature, set 2 for encrypting and decrypting. In this case, if someone sends Alice a message encrypted with Alice public key, then Alice use the her private key in set 2 to decrypt it; however, to sign a message, Alice will use her private key in set 1. In this scenario, if Alice has 2 set of key as described, then by asking Alice to sign y, Eve will not figure out the plaintext message m above.Common Modulus Attack on RSAA possible implementation of RSA is to give everyone the same n, but different values of e and d. This can be done by choosing different e, and then the equation below will yield different d:ed ≡ 1 mod (p-1)(q-1)4However, this implementation is not work. If the same message is encrypted with two different exponents e1 and e2 which are relatively prime (which they generally would be), then the plaintext can be recovered without knowing the decryption exponents d1 and d2.c1 = me1 mod nc2 = me2 mod nSince e1 and e2 are relatively prime, using extended Euclidean algorithm, r and s can be found such that:re1+ re2 = 1Assuming r is negative (either r or s has to be, just call the negative one r), using the extended Euclidean algorithm, c1-1 can be found:(c1-1) -r * c2s = m mod nThe solution to prevent this attack is not to use different values of e and d for the same modulus
View Full Document
Unlocking...