Post : RSA (Rivest-Shamir-Adleman) Encryption
Title : RSA (Rivest-Shamir-Adleman) Encryption
RSA (Rivest-Shamir-Adleman) Encryption
What is RSA Encryption?
RSA was first described in 1977 by Ron Rivest, Adi Shamir and Leonard Adleman of the Massachusetts Institute of Technology. It is an algorithm used by modern computers to encrypt and decrypt messages. It is an asymmetric cryptographic algorithm. Asymmetric means that there are two different keys. This is also called public key cryptography, because one of them can be given to everyone. The other key must be kept private.
Cryptography relies on numerous mathematical techniques from Number Theory – which until the 1950s was thought to be a largely theoretical pursuit with few practical applications. Today RSA code is absolutely essential to keeping digital communications safe.
RSA Algorithm
RSA encrypts messages through the following algorithm, which is divided into 3 steps:
1. Key generation
2. Encryption
3. Decryption
1. Key generation
1. Choose two distinct prime numbers p and q.
2. Find n such that n = pq.
n will be used as the modulus for both the public and private keys.
3. Find the totient of n, ϕ(n)
ϕ(n)=(p-1)(q-1).
4. Choose an e such that 1 < e < ϕ(n), and such that e and ϕ(n) share no divisors other than 1 (e and ϕ(n) are relatively prime).
e is kept as the public key exponent.
5. Determined (using modular arithmetic) which satisfies the congruence relation
de ≡ 1 (mod ϕ(n)).
2. Encryption
1. Person A transmits his/her public key (modulus n and exponent e) to Person B, keeping his/her private key secret.
2. When Person B wishes to send the message "M" to Person A, he first converts M to an integer such that 0 < m < n by using agreed upon reversible protocol known as a padding scheme.
3. Person B computes, with Person A's public key information, the ciphertext c corresponding to
c ≡ me (mod n).
4. Person B now sends message "M" in ciphertext, or c, to Person A.
3. Decryption
1. Person A recovers m from c by using his/her private key exponent, d, by the computation
m ≡ cd (mod n).
2. Given m, Person A can recover the original message "M" by reversing the padding scheme.
This procedure works since
c ≡ me (mod n),
cd ≡(me)d (mod n),
cd ≡ mde (mod n).
By the symmetry property of mods we have that
mde ≡ mde (mod n).
Since de = 1 + kϕ(n), we can write
mde ≡ m1 + kϕ(n) (mod n),
mde ≡ m(mk)ϕ(n) (mod n),
mde ≡ m (mod n).
From Euler's Theorem and the Chinese Remainder Theorem, we can show that this is true for all m and the original message
cd ≡ m (mod n), is obtained.
Working Example of RSA
Alice generates her RSA keys by selecting two primes: p=11 and q=13. The modulus n=p×q=143. The totient of n ϕ(n)=(p−1)x(q−1)=120. She chooses 7 for her RSA public key e and calculates her RSA private key using the Extended Euclidean Algorithm which gives her 103.
Bob wants to send Alice an encrypted message M so he obtains her RSA public key (n, e) which in this example is (143, 7). His plaintext message is just the number 9 and is encrypted into ciphertext C as follows:
Me mod n = 97 mod 143 = 48 = C
When Alice receives Bob’s message she decrypts it by using her RSA private key (d, n) as follows:
Cd mod n = 48103 mod 143 = 9 = M
To use RSA keys to digitally sign a message, Alice would create a hash or message digest of her message to Bob, encrypt the hash value with her RSA private key and add it to the message. Bob can then verify that the message has been sent by Alice and has not been altered by decrypting the hash value with her public key. If this value matches the hash of the original message, then only Alice could have sent it (authentication and non-repudiation) and the message is exactly as she wrote it (integrity). Alice could, of course, encrypt her message with Bob’s RSA public key (confidentiality) before sending it to Bob. A digital certificate contains information that identifies the certificate's owner and also contains the owner's public key. Certificates are signed by the certificate authority that issues them, and can simplify the process of obtaining public keys and verifying the owner.
Source of example: http://searchsecurity.techtarget.com/
How secure is RSA?
The security of RSA public key encryption algorithm is mainly based on the integer factorization problem, which can be described as:
Given integer n as the product of 2 distinct prime numbers p and q, find p and q.
If the above problem could be solved, the RSA encryption is not secure at all. This is because the public key {n,e} is known to the public. Any one can use the public key {n,e} to figure out the private key {n,d} using these steps:
- Compute p and q by factorizing n.
- Compute m = (p-1)*(q-1).
- Compute d such that d*e mod m = 1 to obtain the private key {n,d}
If n is small, the integer factorization problem is easy to solve by testing all possible prime numbers in the range of (1, n).
3 Recommendation by experts
As our computers are getting more powerful, factoring n of 1024 bits will soon become reality. This is why experts are recommending us:
- Stop using RSA keys with n of 1024 bits now.
- Use RSA keys with n of 2048 bits to keep your data safe up to year 2030.
- Use RSA keys with n of 3072 bits to keep your data safe beyond year 2031.
References: http://www.di-mgt.com.au/rsa_alg.html
Message: I hope that you have enjoyed 'RSA (Rivest-Shamir-Adleman) Encryption' article. However, if you want me to deliver more articles then please share my post. You can use Social Sharing Widget provided at the end of every post. After all, Sharing is Caring!
That is the article of RSA (Rivest-Shamir-Adleman) Encryption
make a blog website free
Here Come New Ideas for how do you start your own website for free RSA (Rivest-Shamir-Adleman) Encryption, I hope my article give you benefit for you. Make a blog website free, how do you start your own website for free.
0 Response to "RSA (Rivest-Shamir-Adleman) Encryption"
Post a Comment