Behold, "The World's Most Secure RSA key"®©™ : 2^1277-1

[jdcs]

Originally Posted by a1call

Is decripting-computation-cost a function of high cost of Modular-Exponentiation? Would it be easier/easy to decrypt an RSA encrypted message if you could perform significantly faster Modular-Exponentiation than is possible now, without knowing the private key?

No. The modular exponentiation for decryption does take a little longer than for encryption, but it's plenty fast on any modern computer.

The problem is figuring out WHAT the decryption exponent is. To decrypt an encrypted message c, just compute c^d mod M1277. The private key is simply d.

But the only known way to find the value of d requires factoring M1277.

[retina]

Originally Posted by jdcs

The modular exponentiation for decryption does take a little longer than for encryption ...

Sure, if you consider ~70 times longer to be "a little".

[a1call]

Originally Posted by jdcs

No. The modular exponentiation for decryption does take a little longer than for encryption, but it's plenty fast on any modern computer.

The problem is figuring out WHAT the decryption exponent is. To decrypt an encrypted message c, just compute c^d mod M1277. The private key is simply d.

But the only known way to find the value of d requires factoring M1277.

Thank you very much for the reply.
Would the algorithm for funding d also work if M1277 had more than 2 prime factors, or it would have to be a semiprime?
ThankS again.

[jdcs]

Originally Posted by a1call

Would the algorithm for funding d also work if M1277 had more than 2 prime factors, or it would have to be a semiprime?

It can work with more than 2 prime factors.

Just send me the factors of M1277, and I'll show you how to compute d.

[a1call]

Originally Posted by jdcs

It can work with more than 2 prime factors.

Just send me the factors of M1277, and I'll show you how to compute d.

Thanks Google confirmed:

Having more than two prime factors is supported by the PKCS#1 standard. This is called a "multi-prime" key. On the plus side, this may offer some performance improvement. The Chinese Remainder Theorem still applies (see for instance in section 5.1.2, the description accommodates more than two primes).

As for the factors you will be the 1st one I will let know when I find them.

ETA I can now see the wisdom of choosing such a small exponent as a public key. Very large exponents would facilitate reverse-engineering the private key.

[LaurV]

Originally Posted by a1call

Would it be easier/easy to decrypt an RSA encrypted message if you could perform significantly faster Modular-Exponentiation than is possible now, without knowing the private key?

Definitively yes. Regardless of what other posters said, if you are able to square numbers extremely fast, i.e. if you give me an algorithm that can make "instant squaring" (well, not instant, but "in a blink of an eye", you know what I mean) then I could use it for exponentiation, which in turn used for a Pollard-like algorithm to factor N and get the private key (either Pm1 with a very high B1 or some rho flavor, which are now slow exactly because squaring is slow - think about how far a Rho with a polynomial x^2+/-1 could go with "instant" squaring).


Edit (after a while): reading your question over and over (sorry, English is not my native language), if you ask if we can decrypt the message faster, without finding the key or factoring N, assuming we could do exponentiation faster, then the answer is "no", and my ante-posters were right.

[a1call]

Thank you for the reply LaurV.
I am afraid your post is a bit too advanced for my level. I had to look up Pollard-Rho factoring, but still can't quite grasp the concept.

https://en.m.wikipedia.org/wiki/Poll..._rho_algorithm

https://en.m.wikipedia.org/wiki/Poll...92_1_algorithm

Would a hypothetical rapid/instant exponentiation facilitate factoring composites by rendering factor p with p-1 powersmooth?

https://en.m.wikipedia.org/wiki/Smoo...smooth_numbers

Thanks again for the clarification.

[xilman]

Originally Posted by LaurV

Definitively yes. Regardless of what other posters said, if you are able to square numbers extremely fast, i.e. if you give me an algorithm that can make "instant squaring" (well, not instant, but "in a blink of an eye", you know what I mean) then I could use it for exponentiation, which in turn used for a Pollard-like algorithm to factor N and get the private key (either Pm1 with a very high B1 or some rho flavor, which are now slow exactly because squaring is slow - think about how far a Rho with a polynomial x^2+/-1 could go with "instant" squaring).


Edit (after a while): reading your question over and over (sorry, English is not my native language), if you ask if we can decrypt the message faster, without finding the key or factoring N, assuming we could do exponentiation faster, then the answer is "no", and my ante-posters were right.

If by "squaring" you mean modular multiplication of arbitrary values of a specific length, you might be on to something. However, overheads (loop control, modular addition, GCD, comparison, etc) would still be significant. I doubt that rho would be feasible even if multiplication took zero time. If the factors are of similiar size, rho would require 2^(1277/4) iterations. That's a large number.