New answers tagged

1

This particular prime has been widely used in implementations of the Internet Key Exchange Protocol (IKE) and commonly referred to as Group 5. Group 5 has been in many devices for over a decade. Depending on your viewpoint this fact is either good or bad. It's good if you are implementing IKE and want to interoperate with other implementations of IKE. It ...


15

However, factoring a large integer is extremely difficult, even for a computer using known factoring algorithms. Not categorically. Factoring a large integer is trivial if it is only composed of small factors. A fairly naive algorithm for factoring N is the following: while N > 1: for p in increasing_primes: while p divides N: N = N / p ...


6

$\varphi(n)$ is a multiplicative function: it is computed by the formula $$ \varphi(n) = n \prod_{p \mid n} \frac{p-1}{p} $$ or something equivalent. This is basically the only method of computation known that remains feasible when $n$ is not small. Thus, if $N$ is the modulus you want to use for RSA, you need to know its prime factorization so that you ...


11

RSA moduli are generally of the form $N = pq$ for two primes $p$ and $q$. It is also important that $p$ and $q$ have (roughly) the same size. The main reason is that the security of RSA is related to the factoring problem. The most difficult numbers to factor are numbers that are the product of two primes of similar size. Note. There are basically two ...


14

The main reasons we usually choose $p$ an $q$ prime numbers are: For a given size of $N=pq$, that makes $N$ harder to factor, hence RSA safer. Although efficient factoring algorithms do not find factors by trial division, it remains much easier to find very small prime factors than large ones. If we chose $p$ and/or $q$ at random without consideration for ...


3

The paper is rather sloppily written, however it can be changed into the correct statement. The statement in the paper is: She takes randomly elements $f \in F^*_p$ and checks whether or not $f^{2x}=1$. With probability at least $1 − 1/\ell$ she finds $f$ of order $\ell$. As written, that's wrong. However, if we modify it to: She takes a random ...


1

Find other software that does the test, then compare over the first 10^10 or more integers, then over random large numbers (both inside 64-bit range and significantly larger assuming your software does that). Try various bases. Use the Feitsma-Galway database of all 64-bit base 2 strong pseudoprimes and make sure you produce a similar results for all those ...


6

Well, the obvious thing to do is give it a long list of integers of known primality, and see whether the algorithm reports it correctly (with it occasionally reporting a composite as "relatively-prime" not being counted as an error, as long as it reports that value as composite at least 75% of the time). However, that simple-minded test might miss ...


2

Approximately how large should p be? Current calculations say it's probablly possible to crack a 1024 bit prime today with NSA-level resources and there is speculation that the NSA has cracked some widely used 1024 bit primes. 2048 bit seems to be a common default these days. How often should p be changed, if ever? Every n handshakes, every m ...


24

Is this number specified anywhere? It was formally specified in this RFC as the 1536 bit MODP group (although its use predates that RFC). However, from what I've seen, the 2048 bit MODP group from that same document is actually more popular. Why was this particular number picked? Well, it's a safe prime; in addition, the leading 64 bits and the ...



Top 50 recent answers are included