Re: Breaking RSA & Securing RSA

From: Kristian Gjøsteen (
Date: 07/06/05

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

Sebastian Gottschalk <> 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

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