# Re: Breaking RSA & Securing RSA

**From:** Kristian Gjøsteen (*kristiag+news_at_item.ntnu.no*)

**Date:** 07/06/05

**Next message:**Unruh: "Re: Question about random numbers"**Previous message:**Mike Amling: "Re: Breaking RSA & Securing RSA"**In reply to:**(deleted message) Sebastian Gottschalk: "Re: Breaking RSA & Securing RSA"**Next in thread:**Sebastian Gottschalk: "Re: Breaking RSA & Securing RSA"**Reply:**(deleted message) Sebastian Gottschalk: "Re: Breaking RSA & Securing RSA"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

Date: Wed, 6 Jul 2005 19:31:05 +0000 (UTC)

Sebastian Gottschalk <seppi@seppig.de> wrote:

*>2. Keep p and q along with d, so you can use Chinese remainder theorem to
*

*>speed up private key operations.
*

This is useful and correct advice. Remember to use d mod p-1 and d

mod q-1 to get the best speedup.

*>- ElGamal doesn't have any sub-exponential attack known yet.
*

You meant: there are no known sub-exponential algorithms

computing discrete logarithms for carefully chosen elliptic curves.

*>- RSA over ECC can use smaller key sizes, as factoring over ECC is way
*

*>harder.
*

While there are RSA-like cryptosystems involving elliptic curves modulo

composite numbers, they are not practical, nor likely to be more secure

than RSA. (If the RSA problem turns out to be much easier than the

factoring problem, that may change.)

What you probably meant was the cryptosystems based on elliptic curves

often have small keys and ciphertexts compared to RSA or cryptosystems

based on finite fields.

*>It's called Advanced Euklid's Algorithm and is so simple that you can't
*

*>miss it.
*

Type "euclid's extended" into Google instead.

-- Kristian Gjøsteen

**Next message:**Unruh: "Re: Question about random numbers"**Previous message:**Mike Amling: "Re: Breaking RSA & Securing RSA"**In reply to:**(deleted message) Sebastian Gottschalk: "Re: Breaking RSA & Securing RSA"**Next in thread:**Sebastian Gottschalk: "Re: Breaking RSA & Securing RSA"**Reply:**(deleted message) Sebastian Gottschalk: "Re: Breaking RSA & Securing RSA"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]