Re: 1024-Bit RSA Key Pair Generation Rate - Modest PC

On Jan 5, 11:44 pm, Jafet <ja...@xxxxxxxxx> wrote:
Le Chaud Lapin wrote:
On Jan 4, 8:13 am, Pubkeybreaker <pubkeybrea...@xxxxxxx> wrote:
The question, as asked,  is unanswerable.  You leave too many open
questions.

Good questions. :)

For example:
(1) Do you require fully proved primes, or prps?

Depends on how long it takes for full-proved prime relative to how
long it takes for prps

So the designated speed of your algorithm would depend on... the
eventual speed of the algorithm.

(1.5) How big are your keys?
Small keys can be primality-proven reasonably efficiently using the APR
or AKS tests. Large keys will have to do with probabilistic tests.

1024-bit modulus.

(3) Do you want random primes, or primes with special properties
    (e.g. so called 'strong' primes)

Strength has to be at least as good as would be found in SSL.

Why don't you just perform a speed benchmark with OpenSSL? Also, SSL
(now TLS) allows for multiple cipher strengths and two communicating
parties negotiate the highest mutual level of security.

I must have tried that a while back. Will try again. I posted here
hoping for a quick (rough) estimate so that I could have an answer in
a few hours instead of a day or two. IOW, if someone where to provide
and estimate that would give me an idea for their faster, better, CPU
written with tighter code than I would rather, even that would have
been valuable.

(5) Why do you choose such a crude division algorithm?  Why use
     division at all?

Modular reductions are usually implemented with divisions -- x % y = x -
x / y * y. Crude division algorithms are often faster at moderate sizes.

I read High-Speed RSA Implementation a while back (ftp://
ftp.rsasecurity.com/pub/pdfs/tr201.pdf), an indeed, I remember that
the more esoteric algorithms had drawbacks that made them unsuitable
for practical use until keys became extremely large (FFT).

(7) Who is writing the code?  It is probable that if I were to write
the
     code, the answer would be dramatically different from your
writing the code.

Is that an offer? ;)

I, Captain TooSloppy, would be writing the code, but I would have an
expert remove the warts and holes when finished.

If I were an "expert", I would write the whole thing myself anyway if I
had to. Debugging and refactoring someone else's code is tedious and
unpleasant.

So true.

Also, I did not mention, I need fast general-purpose primitives
exponentation/mod reduction/division on generalized big-int class in
addition to implementation against RSA.

You probably want GMP, which is by legend the fastest of its class
(assuming the developers have tuned assembly for your architecture) and
(according to their benchmarks) much faster than OpenSSL, if you really
want to implement RSA yourself.

I did look at GMP also a while back, and I'm using a PC, so
implementation is there.

But what I was really hoping for was a very rough estimateon
generation of 1024-bit key pairs as indicated in my OP, with emphasis
on the "rough" part.

I guess I will take a look myself. ;)

-Le Chaud Lapin-
.

Relevant Pages

  • Re: 1024-Bit RSA Key Pair Generation Rate - Modest PC
    ... Do you require fully proved primes, or prps? ... So the designated speed of your algorithm would depend on... ... Small keys can be primality-proven reasonably efficiently using the APR or AKS tests. ...
    (sci.crypt)
  • Re: Checking a foolproof algorithm.
    ... > We have the same interest in encryption/decryption and programming. ... > I send my friend the encrypted message along with the 2 prefixed keys. ... > then attempts to write a decryption program to break the coded message ... your keys known to your attacker but not the algorithm... ...
    (sci.crypt)
  • Re: Congruence based factoring algorithm
    ... algorithm will run faster with as small a p as possible; ...    report that T is prime ... Can you prove an upper bound on the numbers for which the effect can ... so it's equivalent to a brute force technique as a k that works gives ...
    (comp.theory)
  • Re: a few questions about AES
    ... algorithm that it uses. ... trivially insecure. ... establishes an upper bound on the cipher strength. ... few keys => a weak cipher. ...
    (sci.crypt)
  • Re: fast static alphabetic (order preserving) compression algorithms/implementations
    ... The algorithm must be unencumbered by patents. ... time required to perform key search on the compressed keys (hence the ... compression keywords and you'll be on your way. ... RDF database, where the keys are an array of three 64-bit long ...
    (comp.compression)