February 21st, 2005, 09:15 PM
Public Key Encryption
I took a basic Encryption class a few years back. We studied things like simple subsitution cyphers and such, but when it came to Modern Public Key Encryption, i was quite lost. If i recall, Public Key uses a pair of two large prime numbers. And the Encryption key itself is based off of the two prime numbers multiplied together. Further more, if i understand correctly, The only two Decryption keys will be the origional prime numbers. (or multiples of those primes). Can any one Confirm this?
The reason why i ask, is because im working on a factoring program and id like to know the average length of these keys when multiplied together. I know the RSA has some test keys avialable, but im interested what the current length being used.
Anyways any help will be apreciated, as i will use such information in an up coming Tutorial on Modern Day Factoring. Thank you.
February 22nd, 2005, 02:50 AM
The current length is well beyond 100 digits per prime number. And as you stated: If a & b are the two (different however very large nowadays) prime numbers then: ab = c
Hereís a link to the RSA Algorithm encrypt/decrypt (create your own key) and also an example of decrypting with Eulerís theorem.
Of particular note is the comments concerning factorization in polynomial time. Since you are working on a factoring program, you could become well known if...
Additionally the Diffie-Hellman/DSS PGP key is between 1024 bits and 4096 bits.
Connection refused, try again later.
February 22nd, 2005, 03:10 AM
What the keys are (taken from http://www.di-mgt.com.au/rsa_alg.html):
" 1. Generate two large random primes, p and q, of approximately equal size such that their product n = pq is of the required bit length, e.g. 1024 bits.
2. Compute n = pq and (φ) phi = (p-1)(q-1).
3. Choose an integer e, 1 < e < phi, such that gcd(e, phi) = 1.
4. Compute the secret exponent d, 1 < d < phi, such that
ed ≡ 1 (mod phi).
5. The public key is (n, e) and the private key is (n, d). The values of p, q, and phi should also be kept secret.
* n is known as the modulus.
* e is known as the public exponent or encryption exponent.
* d is known as the secret exponent or decryption exponent. "
To my knowledge one could create a key of any desired length, but I believe 1024 bits is the standard, smaller keys may be faster but consider weaker (I believe the weakest key at this time recomended to be cryptographically secure is a 640 bit mod), larger keys being potentially more secure but you will see a definite decrease in the speed making extremlely large keys pretty lame, unless you like waiting, although as hardware gets faster the overhead of course becomes less important. Because of the power required, RSA tends to be used for key-exchanges and digital-sgnatures as opposed to trying to encode big blocks of data. RSA can only operate on blocks of data the same size or smaller than the modulus -11 bits. (The actual encoding requires 11 bits) So a standard 1024 bit RSA key can encrypt 1013 bits worth of data.
\"If computers are to become smart enough to design their own successors, initiating a process that will lead to God-like omniscience after a number of ever swifter passages from one generation of computers to the next, someone is going to have to write the software that gets the process going, and humans have given absolutely no evidence of being able to write such software.\" -Jaron Lanier
February 22nd, 2005, 07:48 PM
Here is a link to a tutorial I wrote a few weeks ago. Hope it helps.
\"Common Sense, isn\'t that common\"
\"It is a lot easier to raise a child then it is to repair an adult\"