Good day!
Here are some brief descriptions you can get that I noted in understanding the basic concepts of RSA.
The RSA Public-key system is one of the most popular and well known public-key system. It is widely believed that RSA gets it's security from the difficulty in factoring large numbers. The RSA algorithm involves three steps: key generation, encryption and decryption.
RSA has two algorithms: one for asymmetric encryption, and one for digital signatures -- with several variants.
The math of RSA is simple:
[+] Take two large primes, p and q.
[+] Find the product n of pq (which is the public modulus)
[+] Randomly choose a number e, such that: e<n and e is relatively prime to (p-1)(q-1)
[+] Use Euclid's algorithm to compute d [which is the inverse mod (p-1)(q-1) or ed = 1 mod (p-1)(q-1)].
[+] e is the public exponent, and d is the private one.
[+] The public-key is (n,e) and private key is d.
[+] p and q must be destroyed.
The security of public-key systems resides in the so-called trap door functions: Mathematical problems that are relatively easy to calculate in one direction, but infeasible to calculate the inverse of such problems as discrete logarithms in a finite field, knapsack problems and the most famous the RSA which gets it's security from the difficulty in factoring large numbers (a super-polynomial time problem).
The fastest algorithms are of the super-polynomial complexity class. While not easy, factoring technology has jumped LEAPS and BOUNDS in the past few years. The table below shows time estimates for factoring several keysizes using the general number field sieve(GNFS) (a MIPS-year is a 1,000,000 instruction per second computer running for one year, or 3E13 instructions.)
Key size in bits MIPS-year required to factor
512 3E5
768 2E8
1024 3E11
1280 1E14
1536 3E16
2048 3E20
A related algorithm, the special number field sieve (SNFS) is faster still then the GNFS. The SNFS is actually more efficient on special number types that are not too often used in cryptography but it is relevant to a factoring discussion. Here's some table:
Key size in bits MIPS-year required to factor
512 <200
768 1E5
1024 3E7
1280 3E99
1536 2E11
2048 4E14
If you are thinking that a 1024-bit key is unconditionally safe, here are some assumptions from the mathematicians who factored RSA-129:
"We believe that we could acquire 100 thousands machines without superhuman or unethical efforts. That is, we would not set free an Internet worm or virus to find resources for us. Many organizations have several thousand machines each on the net. Making use of their facilities would require skillful diplomacy, but should not be impossible. Assuming 5 mips average power, and one year elapsed time, it is not too unreasonable to embark on a project which would require half a million mips years."
Well, this is some overview on the RSA and it's some key on giving you idea on it. Here Ive list some references for you if you need a further reading about RSA.
References:
http://scienceblogs.com/goodmath/2008/12/01/public-key-cryptography-using/
http://en.wikipedia.org/wiki/RSA_%28cryptosystem%29
http://www.di-mgt.com.au/rsa_alg.html
Here are some brief descriptions you can get that I noted in understanding the basic concepts of RSA.
The RSA Public-key system is one of the most popular and well known public-key system. It is widely believed that RSA gets it's security from the difficulty in factoring large numbers. The RSA algorithm involves three steps: key generation, encryption and decryption.
RSA has two algorithms: one for asymmetric encryption, and one for digital signatures -- with several variants.
The math of RSA is simple:
[+] Take two large primes, p and q.
[+] Find the product n of pq (which is the public modulus)
[+] Randomly choose a number e, such that: e<n and e is relatively prime to (p-1)(q-1)
[+] Use Euclid's algorithm to compute d [which is the inverse mod (p-1)(q-1) or ed = 1 mod (p-1)(q-1)].
[+] e is the public exponent, and d is the private one.
[+] The public-key is (n,e) and private key is d.
[+] p and q must be destroyed.
The security of public-key systems resides in the so-called trap door functions: Mathematical problems that are relatively easy to calculate in one direction, but infeasible to calculate the inverse of such problems as discrete logarithms in a finite field, knapsack problems and the most famous the RSA which gets it's security from the difficulty in factoring large numbers (a super-polynomial time problem).
The fastest algorithms are of the super-polynomial complexity class. While not easy, factoring technology has jumped LEAPS and BOUNDS in the past few years. The table below shows time estimates for factoring several keysizes using the general number field sieve(GNFS) (a MIPS-year is a 1,000,000 instruction per second computer running for one year, or 3E13 instructions.)
Key size in bits MIPS-year required to factor
512 3E5
768 2E8
1024 3E11
1280 1E14
1536 3E16
2048 3E20
A related algorithm, the special number field sieve (SNFS) is faster still then the GNFS. The SNFS is actually more efficient on special number types that are not too often used in cryptography but it is relevant to a factoring discussion. Here's some table:
Key size in bits MIPS-year required to factor
512 <200
768 1E5
1024 3E7
1280 3E99
1536 2E11
2048 4E14
If you are thinking that a 1024-bit key is unconditionally safe, here are some assumptions from the mathematicians who factored RSA-129:
"We believe that we could acquire 100 thousands machines without superhuman or unethical efforts. That is, we would not set free an Internet worm or virus to find resources for us. Many organizations have several thousand machines each on the net. Making use of their facilities would require skillful diplomacy, but should not be impossible. Assuming 5 mips average power, and one year elapsed time, it is not too unreasonable to embark on a project which would require half a million mips years."
Well, this is some overview on the RSA and it's some key on giving you idea on it. Here Ive list some references for you if you need a further reading about RSA.
References:
http://scienceblogs.com/goodmath/2008/12/01/public-key-cryptography-using/
http://en.wikipedia.org/wiki/RSA_%28cryptosystem%29
http://www.di-mgt.com.au/rsa_alg.html
0 comments:
Post a Comment