Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I would like to know if there is an algorithm to generate a RSA key at the state of the art of the present cryptanalysis.

Beside the key lenght I know there are some weakness in the choice of prime numbers that could help an attacker to factor the modulus $N$.

The standard key generation, as far as I know, generate a random number of the right lenght, tries to factorise it dividing it by small factors (say $\leq 10000$) and then one or more primality test (as Fermat and Miller-Rabin) until the confidence level is high enough.

But what about risks that $p-1, q-1$ are with small factors?

share|improve this question
    
If you have some refs I'd be happy if you share them: crypto.stanford.edu/~dabo/abstracts/RSAattack-survey.html –  ddddavidee Apr 23 at 8:08
    
A, maybe, similar question but about a generic generation crypto.stackexchange.com/questions/1970/… –  ddddavidee Apr 23 at 8:19

2 Answers 2

up vote 6 down vote accepted

There is consensus that it is safe to use random primes $p$ and $q$ when generating 2048-bit (or wider) RSA public moduli which two prime factors $p$ and $q$ are about half the key size. That is sanctioned by FIPS 186-4, appendix B.3; specifically, wording in B.3.1 item A:

Using methods 1 and 2 [yielding provable (1) and probable (2) random primes], $p$ and $q$ with lengths of 1024 or 1536 bits may be generated; $p$ and $q$ with lengths of 512 bits shall not be generated using these methods. Instead, $p$ and $q$ with lengths of 512 bits shall be generated using the conditions based on auxiliary primes.

Even though FIPS 186-4 requires (in the second part of this quote) that $p-1$, $q-1$, $p+1$, $q+1$ have at least one known large prime factor when generating a 1024-bit key which two prime factors $p$ and $q$ are 512-bit, many regard this as an unnecessary complication.

The rationale about requiring that $p-1$ (and $q-1$) has at least one large factor is to insure resistance against Pollard's p-1 factoring. The standard rationale that such precautions become pointless past a certain size is that we have factoring algorithms (including GNFS and ECM) with a much better asymptotic run time; that becomes rigorous (thus true) if we add: for any fixed odds of success [Pretty much the same applies to requiring that $p+1$ (and $q+1$) has at least one large factor, which would be in order to guard against Williams' p+1 factoring; and when we do not need to guard against Pollard's p-1, we do not need to guard against Williams' p+1, thus I disregard the later].

Determining quantitatively when we can dispense of precautions against Pollard's p-1 is not trivial!

  • There's a line of thought that if parameters make us safe enough from ECM, we are also safe from Pollard's p-1. This argument is wrong (which does not preclude that it leads to correct conclusions), at least when we consider generation of many keys in a context where an adversary would be content with factoring any of $k$ keys, rather than a certain key (e.g. the adversary's objective is to pass some signature check, and she knows many public key certificates of entities that can emit valid signatures, which is common in machine-to-machine applications). Counter-argument: Pollard's p-1 is better than ECM from the standpoint of the ratio $\text{odds to factor}\over\text{computing effort}$ for low computing effort when factoring random integers (for this reason, in GMP-ECM, a significant time is spent in Pollard's p-1, with great success); that extends (with comparable advantage) to factoring integers that are product of random primes of specified size; and that ratio is what matters as long a the number $k$ of keys does not become the limiting factor.
  • There's a line of thought that GNFS is so much better than ECM that it transcends any advantage Pollard's p-1 may have over ECM for parameters of cryptographic interest. That argument works (past some point depending on the previous consideration) for RSA modulus $N$ with two prime factors of about equal size. But it does not apply when $N$ has one factor $p$ much smaller than half of $N$, which is the case in multi-prime RSA (see PKCS#1), and unbalanced RSA as in RSAP and SPAKE/ALIKE, which e.g. consider a 1248-bit $N$ with a 352-bit $p$, expected to provide 80-bit security [for some definition of that; these parameters are supposed to balance GNFS and ECM].
share|improve this answer
    
I saw you experiments in the edited answer. I think it is interesting, feel free to add them when you have more data... I'll try on my side, too. –  ddddavidee Apr 24 at 9:32
1  
@dddavidee: I removed that part because it contained a serious error. The B1 parameter (maximum size of the second largest prime in p) is extremely critical for both the runtime and the odds that a factor is found. The parameters in the reference I quoted and successfully reproduced leads to a fast runtime, but odds of finding a 352-bit random prime p VERY much lower than what I estimated. It will take me time to sort this out. –  fgrieu Apr 24 at 11:48

RSA is one of the first practicable public key cryptosystems and it is widely used for secure data transmission.

There are two keys involved:

  1. Public Key
  2. Private Key

Choose two distinct prime number a and b
compute n=ab
compute φ(n) = φ(p)φ(q) = (p − 1)(q − 1) = n - (p + q -1)
Determine d as d ≡ e−1 (mod φ(n))
d⋅e ≡ 1 (mod φ(n))

This is one of the finest algorithm to send the information in a secure manner.

share|improve this answer
2  
This doesn't answer the question at all. It isn't asking for a basic explanation of RSA, it's asking about what constraints on the two primes must be checked to avoid security pitfalls. –  Gilles Apr 25 at 9:09
    
Welcome to crypto.SE! A few other critics if you feel like improving this answer: the prime factors undergo an unexpected name change; more than two prime factors is now often considered to still be RSA, that's in PKCS#1; the formula given to "Determine d" is miss-typeset (or wrong), does not determine a (single) $d$, and is not the most general $d\equiv e^{−1}\pmod{\lambda(n)}$ used by PKCS#1, which on our nice website can be entered here as $d\equiv e^{−1}\pmod{\lambda(n)}$. –  fgrieu Apr 25 at 11:21
2  
I know how RSA works, I asked about the secure generation of primes numbers involved in it. Imagine that I want, hypotetically, write an implementation of RSA that is secure, how must I generate $p$ and $q$? –  ddddavidee Apr 25 at 15:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.