1
$\begingroup$

I am writing a high-school paper on textbook RSA (the mathematical aspect only). Many definitions of the RSA method start off with saying that one should:

Generate two large random (and distinct) primes p and q, each roughly the same size

(http://cacr.uwaterloo.ca/hac/about/chap8.pdf, page 286)

My question is: what does 'large' imply? How many digits - is there a 'limit' to the amount of digits for an suitable prime? In some books they talk about 'bits' and 'strings': I still do not understand what they mean. Please clarify.

Another question: What does distinct mean? What does it imply.

Thank you in advance

$\endgroup$
6
$\begingroup$

My question is: what does 'large' imply? How many digits - is there a 'limit' to the amount of digits for an suitable prime?

A prime $p$ is called large in this case if factoring the multiplication $pq$ with a similar-sized prime $q$ prime is considered infeasible.
Usual sizes of the primes include $2^{1024}$ up until $2^{2048}$. For the recommended size of the modulus (which is roughly twice as long as the primes) refer to keylength.com. There's no hard limit to the size of the RSA-primes, as there are infinitely many primes and any two will do.
The soft limit is the amount of computation you want to invest to use these parameters. The larger your primes, the longer you'll take to encrypt, decrypt, verify and sign data which is undesirable in many cases. Usually this makes people chose the lowest reasonably secure size (e.g. 1024-2048 bit primes).

In some books they talk about 'bits' and 'strings': I still do not understand what they mean.

Computers represent numbers as a sequence of bits ($0$ or $1$). The bitlength of a number is said to be the amount of bits ($0$s and $1$s) required to represent said number or equivalently: The bitlength of $n$ is $\lfloor \log_2(n)\rfloor +1$.
A string is generally said to be an arbitrary sequence of bits without any interpretation of its contents (f.ex. as number).

What does distinct mean?

It means what it says: Two primes $p,q$ are said to be distinct if and only if $p\neq q$. The reason for this requirement in RSA is obviously that $n=p^2$ is easy to factor.

$\endgroup$
  • 1
    $\begingroup$ The bitlength of $n$ is actually $\lfloor \log_2n\rfloor + 1$. $\endgroup$ – fkraiem Nov 1 '15 at 14:42
  • $\begingroup$ Your answers were very helpful, thanks. Another question: what amount of time is considered infeasible? CompSci is not an area I am very familiar with but I'm assuming that infeasibility is related to the 'system' used to 'crack the code'? Is there a function for time that is RSA-related, with a limit? $\endgroup$ – user9750060 Nov 1 '15 at 22:35
  • $\begingroup$ We can calculate how many CPU/GPU/whatever hours it would take to crack a given length of modulus given the current best known factoring agorithm, the current best known hardware etc. However we can only guess how both computer hardware and factoring algorithms will change over time. $\endgroup$ – Peter Green Nov 1 '15 at 23:03
  • $\begingroup$ @Evelyn, Infeasible means that it is likely for the key not to be recovered within a given time frame, usually defaulting to 10, 30 and 200 years using reasonable extrapolations. RSA is based on the hardness of factoring the modulus ($pq$) and finding $p$ and $q$ is the best attack known for RSA. A further reading is the original Lenstra and Verheul paper and the simplified version. $\endgroup$ – SEJPM Nov 2 '15 at 17:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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