The Functions Of The Rsa Algorithm Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

At the moment RSA seems to be extremely secure. It has survived over 20 years of scrutiny and is in widespread use throughout the world. The attack that is most often considered for RSA is the factoring of the public key. If this can be achieved, all messages written with the public key can be decrypted. The point is that with very large numbers, factoring takes an unreasonable amount of time (see the factorization section for more details of the difficulty). It has not been proven that breaking the RSA algorithm is equivalent to factoring large numbers (there may be another, easier method), but neither has it been proven that factoring is not equivalent.

The strength of the cryptographic algorithm depends on key generation, key management, the cryptographic algorithm and the cryptographic protocol. If there is a weakness in any one of these areas, it undermines the entire system. Imagine an eavesdropper was able to generate session keys in the same order that an e-commerce site web server used to get credit card details securely from customers over the Internet; this would allow the eavesdropper to read all the transactions.

There are two types of Attacks are there. Those are

Passive Attacks,

Active Attacks

Passive attacks are the attacks which will not alter the data but try to get the data.Examples for this attacks are tapping the data, packet sniffing. It is difficult to identify these attacks.

Active Attacks are the attacks which require some interaction such as altering data and can be detected; remote attacks, which do not occur on-site; a hit-and-run ping of death attack, which crashes a computer; a smurf or persistent attack, which affects the target machine for a limited amount of time and then lets it return to normal; a replay attack, which is an active attack whereby the cracker tries to capture message parts and then resend a message sometime later with changes; a brute-force attack, which is a fatiguing attempt to try all combinations until a successful break-in occurs; a man-in-the-middle attack, which involves either eavesdropping on an existing connection or interposing oneself in the middle of a connection and changing data; a hijack attack, which literally hijacks one side of a connection; and rewrite attacks, which change an encrypted message without first decrypting it.

There are so many attacks are there on RSA.The following are the some of the Attacks.

Searching the Message Space Attack:

One of the seeming weaknesses of public key cryptography is that one has to give away to everybody the algorithm that encrypts the data. If the message space is small, then one can simply try to encrypt every possible message block, until a match is found with one of the ciphertext blocks. In practice this would be an insurmountable task because the block sizes are quite large.

Guessing d Attack:

Another possible attack is a known ciphertext attack. If the attacker knows the plaintext and ciphertext then the attacker (they simply have to encrypt something) try to crack the key to discover the private exponent, d. This might involve trying every possible key in the system on the ciphertext until it returns to the original plaintext. Once d has been discovered it is easy to find the factors of n. Then the system has been broken completely and all further ciphertexts can be decrypted.

The problem with this attack is that it is slow. There are an enormous number of possible ds to try. This method is a factorizing algorithm as it allows us to factor n. Since factorizing is an intractable problem we know this is very difficult. This method is not the fastest way to factorize n. Therefore one is suggested to focus effort into using a more efficient algorithm specifically designed to factor n.

Cycle Attack

This attack is very similar to the Guessing d attack. The idea is that we encrypt the ciphertext repeatedly, counting the iterations, until the original text appears. This number of re-cycles will decrypt any ciphertext. Again this method is very slow and for a large key it is not a practical attack. A generalization of the attack allows the modulus to be factored and it works faster the majority of the time. But even this will still have difficulty when a large key is used. Also the use of p-- strong primes aids the security.

The bottom line is that the generalized form of the cipher attack is another factoring algorithm. It is not efficient, and therefore the attack is not good enough compared with modern factoring algorithms.

We can improve this algorithm by following suggestion. The suggested way is to use the public exponent of the public key to re-encrypt the text. However any exponent should work so long as it is coprime to (p-1).(q-1) (where p, q are factors of the modulus). So I suggest using an exponent such as 216 + 1. This number has only two 1s in its binary representation. Using binary fast exponentiation, we use only 16 modular squarings and 1 modular multiplication. This is likely to be faster than the actual public exponent. The trouble is that we cannot be sure that it is coprime to (p-1).(q-1). In practice, many RSA systems use 216 + 1 as the encrypting exponent for its speed.

Common Modulus Attack

One of the early weaknesses found was in a system of RSA where the users within an organization would share the public modulus. That is to say, the administration would choose the public modulus securely and generate pairs of encryption and decryption exponents (public and private keys) and distribute them all the employees/users.

However, Simmons shows how this would allow any eavesdropper to view any messages encrypted with two keys; for example when a memo is sent to several employees. DeLaurentis went further to demonstrate how the system was at even more risk from insiders, who could break the system completely, allowing them to view all messages and sign with anybody's key.

Faulty Encryption Attack

Joye and Quisquater showed how to capitalize on the common modulus weakness due to a transient error when transmitting the public key. Consider the situation where an attacker, X, has access to the communication channel used by A and B. In other words, X can listen to anything that is transmitted, and can also change what is transmitted. A wishes to talk privately to B, but does not know his public key. A requests by sending an email, to which B replies. But during transmission, X is able to see the public key and decides to flip a single bit in the public exponent of B, changing (e,n) to (e',n).

When A receives the faulty key, A encrypts the prepared message and sends it to B (X also gets it). But of course, B cannot decrypt it because the wrong key was used. So he lets A know and they agree to try again, starting with B re-sending his public key. This time X does not interfere. A sends the message again, this time encrypted with the correct public key.

X now has two ciphertexts, one encrypted with the faulty exponent and one with the correct one. She also knows both these exponents and the public modulus. Therefore she can now apply the common modulus attack to retrieve Alice's message, assuming that A was foolish enough to encrypt exactly the same message the second time.

Low Exponent Attack

In the cycle attack section above, I suggested that the encrypting exponent could be chosen to make the system more efficient. Many RSA systems use e=3 to make encrypting faster. However, there is vulnerability with this attack. If the same message is encrypted 3 times with different keys (that is same exponent, different moduli) then we can retrieve the message. The attack is based on the Chinese Remainder Theorem.

Factoring the Public Key

Factoring the public key is seen as the best way to go about cracking RSA.

Brute force attack:

Even if a symmetric cipher is currently unbreakable by exploiting structural weaknesses in its algorithm, it is possible to run through the entire space of keys in what is known as a brute force attack. Since longer symmetric keys require exponentially more work to brute force search, a sufficiently long symmetric key makes this line of attack impractical.

With a key of length n bits, there are 2n possible keys. This number grows very rapidly as n increases. Moore's law suggests that computing power doubles roughly every 18 to 24 months, but even this doubling effect leaves the larger symmetric key lengths currently considered acceptably well out of reach. The large number of operations (2128) required to try all possible 128-bit keys is widely considered to be out of reach for conventional digital computing techniques for the foreseeable future. However, alternative forms of computing technology are anticipated which may have superior processing power than classical computers. If a suitably sized quantum computer capable of running Grover's algorithm reliably becomes available, it would reduce a 128-bit key down to 64-bit security, roughly a DES equivalent. This is one of the reasons why AES supports a 256-bit key length.

Low Public Exponent Attacks:

A user of the RSA cryptosystem may wish reducing encryption or signature-verification; it is customary to use a small public exponent e. The common choices of a public exponent e are 3 or 216+1. When the value 216+1 is used, signature verification requires 17 multiplications, as opposed to roughly 1000 when a random e<=Ø (N) is used. If the public exponent is small and the plaintext m is very short, then the RSA function may be easy invert. Unlike Wiener's attack, attacks that apply when a small e is used are far from a total break. In this section, we explain some of these attacks and show how they work.

Homomorphic Attacks:

The inherent homomorphic structure of the RSA enables to mount some attacks. Let m1 and m2 be two plaintext messages, and let c1 and c2 be their respective the RSA encryptions. Observe that: (m1*m2)e ≡m1e*m2e≡c1*c2 (mod N), this is called homomorphic property of RSA. In this section, we produce some attacks depend on this property of RSA.Chosen Cipher text Attack: Given (N,e) as RSA public key, and cipher text c, then choose a cipher text and look at the plaintext, then repeat until they have figured out how to decrypt any message.

RSA Digital Signature Attacks:

A digital signature of a message is a number dependent on some secret known to the signer, and additionally on the content of the message being signed. In a digital signers environment the goal of an attacker is to forge signatures: that is, produce signatures which will be accepted as those of some other entity. In this section, we present two attacks against RSA digital signature scheme, the first is Blinding attack ( or Chosen-Message attack) which is depending on homomorphic nature of RSA, the second is Lenstra's attach which is can applicable on all Chinese Remaindering based cryptosystems.

Timing attacks:

Most of the attacks against RSA we have seen so far apply to the underlying cryptographic primitives and parameters. On the other side, implementation attacks target specific implementation leaked by the implementation of the RSA function. The attacks are usually applied against smart cards and security tokens, and are more effective when the attacker is in possession of the cryptographic module. Prevention of implementation attacks is hard, trying to reduce the amount of information leaked. In this section, we present a Timing attacks as a good example of implementation attacks. In 1996, Kocher demonstrated that an attacker can determine a private key by keeping track of how long a computer takes to decipher messages. Timing attacks are alarming for two reasons: it comes from a completely unexpected direction and it is a cipher text only attack. In order to describe this attack, we need to explain how Square-and-Multiply exponentiation is carried out. In order to compute m=C d mod N for decryption a cipher text, we show that at stage i, if d[i]=0, then the value m is not modified. However, if d[i]=1, then we multiply the previous result by C 2*I The Timing attack uses the fact that when d[i]=1, an additional multiplication takes place. Now, assume that an attacker holds a smart card that decrypts. Then, the attacker asks it to decrypt a large number of random messages C1,C2,…,Ck ÎZN and measures the time Ti that is takes to compute Ci d mod N. These timing measurements are now used to obtain d, one bit at a time. Since d is odd, we know that d[0]=1. Initially m=C 2 mod N. Thus, if d[i]=1, the smart cards computes the product m=(m*C) mod N; otherwise, it does not. Let t

i be the time that it takes to compute C *i Ci 2 where Ci is one of the random messages that was initially chosen. By measuring the correlation between t i and Ti it is possible for attacker to determine if d[1] equals 1 or 0, given d[0] and d[1], it is possible to do the same thing for d[2] and so on. In other words, the attacker can determine the particular sequence of squarings and multiplications that the program went through. Based on the outcome, he/she can simply compute the secret exponent d stored on the card. There are simple countermeasures that can be used to confuse the Timing attack such as random delay by adding a random delay to the exponentiation algorithm.

Davida's Attack:

If the attacker can get access to the bin of victim, then he/she will be able to recover the original plaintext if the transformation is done in a clever way.

Algorithm: (Davida's attack)

Input: a public key(N,e), and a cipher text c.

Output: An original message m.

Algorithm: Attacker intercepts the cipher text c, and replaces it by c-=c*ke mod N, where k is a random number. Victim receives c- and computes m-=c-d mod N, since the message m- is meaningless it will be discarded. If attacker can get access to m~, he/she van recover original message m by computing m-*k-1≡c-d*k-1≡cd≡m mod N.

Adaptive chosen ciphertext attacks

In 1998, Daniel Bleichenbacher described the first practical adaptive chosen ciphertext attack, against RSA-encrypted messages using the PKCS #1 v1 padding scheme (a padding scheme randomizes and adds structure to an RSA-encrypted message, so it is possible to determine whether a decrypted message is valid.) Due to flaws with the PKCS #1 scheme, Bleichenbacher was able to mount a practical attack against RSA implementations of the Secure Socket Layer protocol, and to recover session keys. As a result of this work, cryptographers now recommend the use of provably secure padding schemes such as Optimal Asymmetric Encryption Padding, and RSA Laboratories has released new versions of PKCS #1 that are not vulnerable to these attacks.

Side-channel analysis attacks

A side-channel attack using branch prediction analysis (BPA) has been described. Many processors use a branch predictor to determine whether a conditional branch in the instruction flow of a program is likely to be taken or not. Often these processors also implement simultaneous multithreading (SMT). Branch prediction analysis attacks use a spy process to discover (statistically) the private key when processed with these processors.

Simple Branch Prediction Analysis (SBPA) claims to improve BPA in a non-statistical way. In their paper, "On the Power of Simple Branch Prediction Analysis", the authors of SBPA (Onur Aciicmez and Cetin Kaya Koc) claim to have discovered 508 out of 512 bits of an RSA key in 10 iterations.

A power fault attack on RSA implementations has been described in 2010[13]. The authors recovered the key by varying the CPU power voltage outside limits; this caused multiple power faults on the server.

Chosen Ciphertext Attack:

RSA has the property that the product of two ciphertexts is equal to the encryption of the product of the respective plaintexts. That is me1 me2 ≡(m1m2)e(mod n)  Because of this multiplicative property a chosen-ciphertext attack is possible. E.g. an attacker, who wants to know the decryption of a ciphertext c = me (mod n) may ask the holder of the private key to decrypt an unsuspicious-looking ciphertext c' = cre (mod n) for some value r chosen by the attacker. Because of the multiplicative property c' is the encryption of mr (mod n). Hence, if the attacker is successful with the attack, he will learn mr (mod n) from which he can derive the message m by multiplying mr with the modular inverse of r modulo n.

Bleichenbacher's Attack

On PKCS 1 Let N be an n-bit RSA modulus and M be an m- bit message with m < n. Before applying RSA encryption it is natural to pad the message M to n bits by appending random bits to it. An old version of a standard known as Public Key Cryptography Standard 1 (PKCS 1) uses this approach. After padding, the message looks as follows:

02 Random 00 M

The resulting message is n bits long and is directly encrypted using RSA. The initial block containing "02" is 16 bits long and is there to indicate that a random pad has been added to the message.

When a PKCS 1 message is received by Bob's machine, an application (e.g., a Web browser) decrypts it, checks the initial block, and strips off the random pad. However, some applications check for the "02" initial block, and if it is not present, they send back an error message saying "invalid ciphertext". Bleichenbacher showed that this error message can lead to disastrous consequences: using the error message, Marvin can decrypt ciphertexts of his choice. Suppose Marvin intercepts a ciphertext C intended for Bob and wants to decrypt it. To mount the attack, Marvin picks a random r E Z*N, computes C'= r C mod N, and sends C' to Bob's machine. An application running on Bob's machine receives C'and attempts to decrypt it. It either responds with an error message or does not respond at all (if C' happens to be properly formatted). Hence, Marvin learns whether the most significant 16 bits of the decryption of C're equal to 02. In effect, Marvin has an oracle that tests for him whether the 16 most significant bits of the decryption of r C mod N are equal to 02, for any r of his choice. Bleichenbacher showed that such an oracle is sufficient for decrypting C.

Short Pad Attack

Alice sends a properly-padded message to Bob. Eve intercepts it. Not having received a reply, Alice resends, changing the padding function. Eve decrypts the message.

This result is due to a theorem of Coppersmith:

Theorem: Let (n, e) be an RSA key. Let m = [log n/e2] and let M be a message of log n - m bits. Let r1, r2 be secret random numbers with M1 = 2mM + r1and M2 = 2mM + r2. Then given C1, C2 Eve can recover M.

If e = 3 the attack can be mounted so long as the pad is less than 1/9 of the message length.

If we use the recommended value of e being at least 65337. Thus encryption exponent is fine for standard moduli sizes.

Encryption Exponent e is less than the number of recipients Attack:

Suppose B sends Me to e of his friends: A, C, ..., E. (We will do this for e = 3 but the idea holds in general.) Eve sees M3(mod ni) for i = 1, 2, 3. Now M < ni (otherwise the recipients could not decode M3 uniquely). Thus M3 < n1n2n3. But either the ni's are relatively prime, in which case by using the Chinese Remainder Theorem, Eve can compute M3(mod n1n2n3) or they are not, in which case Eve can factor some of theni's and compute M that way. In the first case, Eve has M3(mod n1n2n3), where M < ni for each i, so in M3 Eve has a perfect cube over the integers. Eve can compute the cube root, and get M back.

It better not to send the same message to as many recipients as your encryption exponent. Another way to say this: Use a large encryption exponent.

Blinding Attack:

RSA is subject to the RSA blinding attack through which it is possible to be tricked into decrypting a message by blind signing another message. Since the signing process is equivalent to decrypting with the signers secret key, an attacker can provide a blinded version of a message m encrypted with the signers public key, m' for them to sign. The encrypted message would usually be some secret information which the attacker observed being sent encrypted under the signers public key which the attacker wants to learn. When the attacker unblinds the signed version they will have the clear text:

m'' = m're(mod n)

= (me(mod n).re) (mod n)

= ( mr)e (mod n)

where m' is the encrypted version of the message. When the message is signed, the cleartext m is easily extracted:

s' = m''d (mod n)

= ((mr)e (mod n))d (mod n)

= (mr)ed (mod n)

= m.r (mod n) , since ed ≡ 1 (mod shi(n))

Note that φ(n) refers to Euler's totient function. The message is now easily obtained.

m=s'.r-1 (mod n)

This attack works because in this blind signature scheme the signer signs the message directly. By contrast, in an unblinded signature scheme the signer would typically use a padding scheme (e.g. by instead signing the result of a Cryptographic hash function applied to the message, instead of signing the message itself), however since the signer does not know the actual message, any padding scheme would produce an incorrect value when unblinded. Due to this multiplicative property of RSA, the same key should never be used for both encryption and signing purposes.