Re: [PATCH resend][CRYPTO]: RSA algorithm patch

["Satyam Sharma" <satyam.sharma@gmail.com>]

Hi Indan,

On 4/12/07, Indan Zupancic <indan@nul.nu> wrote:
> I prefer clear, simple code that is easily audited to be correct or at least
> not cause problems, which is small enough to not add much bloat. I don't care
> about "very slow" or merely "slow" code. RSA/DSA isn't used as a symmetric block
> cipher, where it does make sense to optimize it to death.
>
> From the kernel's point of view it's all new and unused code, so it should be
> judged by its quality, not by its heritage.

Agreed, the GPG MPI library *is* significantly larger -- I'm looking
at the Fedora 4 kernel source here and their crypto/mpi/ comes to
about 5000 lines (not including comments). But there are reasons for
this -- they export far too many MPI operations. I suspect they just
ported the *entire* GNU MP lib.

For example, there's crypto/mpi/longlong.h, worth 1500 lines of
ugliness in itself. I see arch-specific assembly there for processors
that Linux doesn't even support. Wow.

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.

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.

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.

> I know you didn't want to talk about the user versus kernel space question,
> but I think it's a very important and interesting one. As you said, GPG is
> there around for years and tested, why making a new implementation in the kernel?
> Your argument holds for the whole as much as for parts of the infrastructure.
[...]
> And whether they can agree on a common implementation. If they all just want to do
> their own thing, and not combine resources, then it doesn't make any sense to merge
> anything at all, as it would be ignored anyway.

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.

> As for the userspace issue, I get the impression that they didn't consider it very
> well, ignoring things like initramfs versus main filesystem and so on. It's also a
> gradual thing, some things can be done best in the kernel, and others in user space.
> Another alternative is to push it up into the boot loader. ;-)

Very true, it does make sense to explore userspace possibilities first.

Cheers,
S

> Greetings,
>
> Indan