Re: Breaking RSA & Securing RSA

From: Sebastian Gottschalk (seppi_at_seppig.de)
Date: 07/05/05 

Date: Tue, 5 Jul 2005 21:59:58 +0200

Galathas wrote:

> Is there any recommendation about how large primes P and Q (which
> creates modulus) should be ?

Very large. Usually >512 Bits in size. Or >80 Bits for RSA on ECC.

> And what about so called "strong primes" ?

P-1 and Q-1 should not contain too many small factors. At best, their only
small factor should be 2, so with (p-1)/2 and (q-1)/2 also being primes
you're going pretty fine. Formally known as Sophie-Germain primes and
conjectured to be pretty dense, these are your "string primes".

> Are there any usefull mathematical algorithms for finding it ?

Pick random numbers, test them for primalty, if not, pick the next
candidates. Usually for will find one within O(x*ln(n)). For "strong
primes", just take an additional tests after you found a prime - you will
still be fast.

> And definitely are there any "good(eg.> 99%)" prime proof algorithms ?

Trial factoring and little Fermat with a = 2,3,5,7 afterwards should be
pretty fine - the chances, that little Fermat will not spot a composite, is
exponentially small, just like the chances to pick such a number are.

> What about Rabbin-Miller test ??

Well, no need for that, little Fermat is already sufficient - it would be
simply a waste of time. And if you want 100% correctness, you can still use
extended versions of Agramal test.

BTW, could you please stop plenking (putting a whitespace in front of
sentence marks, which is simply ugly and also messes up quoting sometimes)
? <- see? 

-- 
Dieser Schrieb stellt eine private Meinungsäußerung des Verfassers im
Sinne der gesetzlich garantierten Meinungsfreiheit dar. Wem das nicht
passt, der wende sich an das Bundesverfassungsgericht. Viel Erfolg!
Key: 0xA0E28D18 FP: 83AE 1136 1E2B 9767 8FB2 7594 4128 1A9E A0E2 8D18

Relevant Pages

  • Re: Primes of the form 2^(2^n)+1
    ... a heuristic reason for believing there are only finitely many Fermat ... primes and composites among the Fermat numbers was exactly the pattern ... argument for their finiteness, ... what the community thinks about the undecidability alternative. ...
    (sci.math)
  • Re: Primes of the form 2^(2^n)+1
    ... a heuristic reason for believing there are only finitely many Fermat ... primes and composites among the Fermat numbers was exactly the pattern ... simple" means "can be concisely expressed in ZFC." ...
    (sci.math)
  • Re: Fermats Last Theorem approach?
    ... it's easy for the Sophie Germaine primes? ... Fermat apparently did not have to prove n=3, 5 etc., ... to Wiles' Secret Attic Project. ... including in withdrawing his assertion ...
    (sci.math)
  • Re: PRODUCING HYDROGEN FROM SEA WATER
    ... F"L"T is easy for the Sophie Germaine primes? ... Fermat apparently did not have to prove n=3, 5 etc., ... nor any other composite power (the "easy lemma" ... to Wiles' Secret Attic Project. ...
    (sci.physics)
  • Re: Fermats Polygonal Number theorem vs FLT?
    ... in developing a model of n-dimensional figurate numbers, ... that could be used to make the contradiction. ... F"L"T is easy for the Sophie Germaine primes? ... Fermat apparently did not have to prove n=3, 5 etc., ...
    (sci.math)