Running time for GNFS

Now I am implementing GNFS algorithm in C++.
Anyone please tell me about the runnong time for GNFS algorithm to factor 128 bit numbers in a single machine.Is it possible to factor a 256 bit number using a single machine & how much time it will take for successful factorization?

[xilman]

Originally Posted by koders333

Now I am implementing GNFS algorithm in C++.
Anyone please tell me about the runnong time for GNFS algorithm to factor 128 bit numbers in a single machine.Is it possible to factor a 256 bit number using a single machine & how much time it will take for successful factorization?

I suggest that you get hold of an existing GNFS implementation and answer those questions by experiment. A good search term for finding an implementation is "ggnfs".

I could tell you the answers but you will learn much more by following my advice.

Ok then --- the answers are:

a few seconds to a few minutes, depending on your hardware and the efficiency of your code;

yes;

a few minutes to a few hours, depending on your hardware and the efficiency of your code.



Paul

[jasonp]

Originally Posted by koders333

Now I am implementing GNFS algorithm in C++.
Anyone please tell me about the runnong time for GNFS algorithm to factor 128 bit numbers in a single machine.Is it possible to factor a 256 bit number using a single machine & how much time it will take for successful factorization?

You can use pgnfs as a baseline (www.pgnfs.org). Note that it's a *really* basic implementation.

jasonp

Originally Posted by xilman

I suggest that you get hold of an existing GNFS implementation and answer those questions by experiment. A good search term for finding an implementation is "ggnfs".

I could tell you the answers but you will learn much more by following my advice.

Ok then --- the answers are:

a few seconds to a few minutes, depending on your hardware and the efficiency of your code;

yes;

a few minutes to a few hours, depending on your hardware and the efficiency of your code.



Paul

Thank You Paul.
Why we are still using 256 bit RSA keys in PGP(email security)?.
I think PGP is secured only because of SHA (signature algorithm). Is it correct?
Can we replace RSA with ECC?.

[jasonp]

Originally Posted by koders333

Thank You Paul.
Why we are still using 256 bit RSA keys in PGP(email security)?.
I think PGP is secured only because of SHA (signature algorithm). Is it correct?
Can we replace RSA with ECC?.

(The international version of) PGP defaults to using 1024 bit Diffie Hellman, i.e. 1024 bit moduli with I think 160 bit keys, or 1024-bit RSA, or 1024-bit DSA. The default (exportable) security level in web browsers is 512-bit RSA, meaning the *factors* of the modulus are 256 bits long.

256 bits is a little over 80 digits. Msieve can do factorizations that size in about 20-25 minutes, so yes this size is not secure at all. But an RSA modulus is twice the size of its factors, and 512 bit factorizations are still hard.

SHA is the Secure Hash Algorithm, and is just a way to crunch arbitrary size messages down to a size where the entire message can be processed at once by whatever public key algorithm your copy of PGP is configured to use. Primarily it's there to prevent duplicate/forged data from being signed; it in no way affects the security of the signature process itself.

Maybe you should skim through Schneier's 'Applied Cryptography' if you have cryptographic applications in mind.

jasonp