Re: Optimum End-To-End Throughput Of RSA Cryptosystem

On May 20, 3:09 pm, Thomas Pornin <por...@xxxxxxxxx> wrote:
According to Le Chaud Lapin  <jaibudu...@xxxxxxxxx>:

The problem I have is with the "signing" vs "verification".  It is
biased and presumptuous.

Not really. It just so happens that RSA is a cryptosystem, and as such
has some security properties to maintain; and security is not symmetric.
The private key is private while the public key is public; this might
seem obvious but what it _means_ is that the private part must be such
that it can be kept private. In particular, the private exponent cannot
be too short; the best known attack works with a size up to 29% of the
modulus, but for proper security you want some security margins, hence
it is customary to pop up the private exponent size to its "generic"
size, i.e. roughly equal to that of the modulus. Trained cryptographers
(including myself) get nervous when the private exponent is specifically
tailored to a smaller size.

The presumption comes with how it is currently used, in 2008, on the
Internet, in a quasi-specific application, which is SSL, and its
related technology, TLS. People using RSA within this context makes an
assumption that messages will be signed by a machine that has a
disproportionally large message-processing workload versus the
machines with which it communicates. While this view is certainly
valid within the context of WWW servers running SSL, it might not be
true in general - there might be a situation where rate of the
combined operation of signing/verfication must be maximized. If it
were possible to reduce the size of the "traditional" d such that both
e, and d are large, but assuming a bit pattern such that the overall
rate is reduced, then some people, I being one of them, might find
that useful. That was the original point of my post.

All of this is pretty basic stuff when one talks about RSA. It is school
stuff. It is part of what makes up RSA. It is usually assumed that
programmers who do not master these details probably do not know enough
about cryptography to be entrusted with the task of tweaking
cryptographic algorithms. In the specific security-sensitive area of
cryptography, the mere idea of optimizing aways the bits which do not
seem useful is the root of all evil. Do not do it. Part of the problem
is that you cannot test, by yourself, whether your modified system is
crackable (it compiles, it runs...).

It might turn out that an entirely different system would reverse the
relative sizes of e and d.

It might have but it turned out that it did not. And, may I point out,
it so turned out twenty years ago, not yesterday.

Same as above. Some engineers might find it useful if both d and e
were large, if making them so would reduce overall rate of signing. I
was hoping for theoretical papers toward that goal, beyond the ones by
Cetin Kaya Koc, etc.

So to take your example, I can see that n is 1024-bit, d is on order
of 1024-bit (most likely), but e? Is it 17? 65537?  Something else?
There is a significant difference in speed on my machine between e==17
and e==65537.

The 981 signatures per second are using the private key, not the
public key. The size of the public exponent is not relevant(*) for
the speed of private key operations.

I would still like to know in case of OpenSSL speed. :)

A few minutes of wading and grepping through the OpenSSL source code
brought me to the openssl-0.9.8g/apps/testrsa.h which contains the test
keys for the speed benchmark. They are encoded in ASN.1 (DER) but it so
happens that I can read that dialect. All four keys (512, 1024, 2048 and
4096 bits) use the traditional public exponent of 65537.

Aha...so I was looking at the right spot. I'd seen the hex tables a
few days ago and aborted since I was not about to go rumaging through
file to decode the format to find out where exponent was located...as
it would have been more efficient to just ask someone here (for me).

OpenSSL is a library, you could use it with a simple code of your own
to perform your own benchmarks with your own keys.

        --Thomas Pornin

(*) Well, mostly. There is the issue of masking. You may need it to
defend against timing attacks. If you do not know what timing attacks
are, and yet set out to implement and run RSA in production use, then I
do not want you to come within one mile of the computer systems which
hold my bank account.

Thank God for the Paul Kocher's of the world.

My strategy is to get everything implemented, then have implementation
reviewed by an expert. My implementation is clean and small, so
faults should be readily discovered.

-Le Chaud Lapin-

.

Relevant Pages

  • Re: Optimum End-To-End Throughput Of RSA Cryptosystem
    ... has some security properties to maintain; ... The private key is private while the public key is public; ... then you are free to use a small public exponent. ... So the "presomption" lies in noticing that asymmetric cryptography is ...
    (sci.crypt)
  • Re: For Tex, (Listening & Watching)
    ... "No Place to Hide might just do for privacy protection what Rachel ... We live in an ever more convenient society. ... O'Harrow unveils a modern world riddled with seemingly innocuous private ... Department of Homeland Security aggressively sought access to these ...
    (rec.arts.poems)
  • For Tex, (Listening & Watching)
    ... "No Place to Hide might just do for privacy protection what Rachel ... We live in an ever more convenient society. ... O'Harrow unveils a modern world riddled with seemingly innocuous private ... Department of Homeland Security aggressively sought access to these ...
    (rec.arts.poems)
  • Ind: The world of private security: Unleashed: the fat cats of war
    ... The US is finally facing up to its failures to supervise the private armies ... The killings by Blackwater's private security guards on Baghdad's Bloody ... yesterday resigned as the State Department overseer of security contractors. ... The government of Nouri al-Maliki, which had declared that they would expel ...
    (alt.politics.bush)
  • RE: NAT external/Public IP
    ... "the main contention is that private addresses are ... It doesn't make a host any more or less ... Why not Security by Design plus Security by Obscurity? ...
    (Security-Basics)
Quantcast