Message-ID: <1574.81.207.0.53.1176404759.squirrel@secure.samage.net>
Date:	Thu, 12 Apr 2007 21:05:59 +0200 (CEST)
From:	"Indan Zupancic" <indan@....nu>
To:	"Satyam Sharma" <satyam.sharma@...il.com>
Cc:	"Tasos Parisinos" <t.parisinos@...ensis.com>,
	"Bill Davidsen" <davidsen@....com>,
	"Andi Kleen" <andi@...stfloor.org>, herbert@...dor.apana.org.au,
	linux-kernel@...r.kernel.org, randy.dunlap@...cle.com
Subject: Re: [PATCH resend][CRYPTO]: RSA algorithm patch

Hello,

On Thu, April 12, 2007 20:38, Satyam Sharma wrote:
> There are some other better reasons for the bloat in the GNU MP lib,
> though. Tasos' code uses the rsa_cipher() as a dual-purpose primitive.
> Feed it the plaintext (p), public exponent (e) and public modulus (n),
> and you get the ciphertext (c = p^e mod n). Feed it the ciphertext,
> private exponent (d) and public modulus, and you get the plaintext (p
> = c^d mod n) back. All modern RSA implementations, however, prefer
> preserving the prime numbers (p, q, and their other derivatives such
> as d mod (p-1), d mod (q-1) and inverse of q modulo p) generated at
> the time of key generation along with the private exponent as the
> complete "private key" (this is what is recommended by PKCS#1 too)
> which enables us to use the chinese remainder theorem to decrypt
> faster than simply do an (expensive) modulo exponentiation again.

Which, according to the Wikipedia page on RSA, is susceptible to timing
attacks, which requires measures to counter that (that might be needed in
Tasos' implementation too though).

Doing MPI well is already tricky. Doing it in such way that most side-channel
attacks don't work is challenging, and brings already code bloat and complexity
with it.  Doing all the previous with compact and simple code is hard. Speed is
the last thing I'm worried about.

I'd rather start with good and simple code, and speed it up without adding too
much complexity gradually, case by case.
(Though I'm not the one with any interests here, so my opinion isn't worth much.)


> Also, DSA signature generation and verification (which is what the
> modsign guys use) doesn't exactly utilize the same MPI operations as
> RSA does. If we really don't care about speed and DSA, we could strip
> that library down to the basic and RSA-only operations Tasos' code
> provides, and I'm quite sure we'd end up somewhere close to 1000 lines
> there too.

That's nice. But then you lose more or less all advantages of using an existing
implementation, don't you? Anyway, how much different would that code be from
Tasos'?

> Of course, that would then *force* other users such as modsign to
> re-implement their own library for their needs again, thus defeating
> the exercise of merging this bare-bones MPI library into the kernel in
> the first place, as you have mentioned.

Not if they go the other way round and strip everything except DSA functionality.
The question is, is an MPI library wanted, or do people just want RSA or DSA?

> Yes, that "common implementation" bit is definitely crucial, which is
> why merging a solid, feature-rich and fast MPI library could become
> all the more important, in my opinion.

You want feature-rich and fast, I prefer dense, clean and spartan, what would
others prefer? Perhaps deciding on a common implementation is harder than it looks.

Greetings,

Indan


-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Powered by blists - more mailing lists