# Tag Info

## Hot answers tagged number-theory

36

The standard way to generate big prime numbers is to take a preselected random number of the desired length, apply a Fermat test (best with the base $2$ as it can be optimized for speed) and then to apply a certain number of Miller-Rabin tests (depending on the length and the allowed error rate like $2^{-100}$) to get a number which is very probably a prime ...

32

The $GF$ in $GF(p^n)$ is not a function — it just stands for "Galois field (of $p^n$ elements)". As for what a Galois field is, it's a finite set of things (which we might represent e.g. with the numbers from $0$ to $p^n-1$), with some mathematical operations (specifically, addition and multiplication, and their inverses) defined on them that let us ...

22

There are some widely used cryptographic algorithms which need a finite, cyclic group (a finite set of element with a composition law which fulfils a few characteristics), e.g. DSA or Diffie-Hellman. The group must have the following characteristics: Group elements must be representable with relatively little memory. The group size must be known and be a ...

22

FIPS 186-3 tells you how they expect you to generate primes for cryptographic applications. It is essentially Miller-Rabin but it also specify what to do when you need extra properties from your primes.

18

The extended Euclidean algorithm is essentially the Euclidean algorithm (for GCD's) ran backwards. Your goal is to find $d$ such that $ed \equiv 1 \pmod{\varphi{(n)}}$. Recall the EED calculates $x$ and $y$ such that $ax + by = \gcd{(a, b)}$. Now let $a = e$, $b = \varphi{(n)}$, and thus $\gcd{(e, \varphi{(n)})} = 1$ by definition (they need to be coprime ...

16

The three main general-purpose algorithms for factorization are the quadratic sieve (QS), the elliptic curve method (ECM) and the number field sieve (NFS). On Complexity The running time of these algorithms is expressed with the L-notation: $L_n[a,c]$ means that the asymptotic complexity of factoring a number $n$ is $O(e^{(c+o(1))(\log n)^a(\log \log n)})^{... 16 First, we are talking about multiplications, so we work in$\mathbb{Z}_p^*$, not$\mathbb{Z}_p$. By definition, any integer$g \in \mathbb{Z}_p^*$is the generator for... the subgroup generated by$g$, i.e. the set of$g^k \mod p$for all integer values$k$. The order of$g$is the smallest$k \geq 1$such that$g^k = 1 \mod p$. For soundness (Alice and ... 14 How could this allow for a backdoor? Well, if you do DH modulo a composite, an attacker can recover the shared secret if they can solve the DH problem (or the DLog problem) modulo each of the primes that make up the composite. There are a couple of ways that could be used by someone who knows the factorization to solve the DLog problem easier than ... 13 Not only does g not need to be a generator for the entire group, general practice is that it is not. As Thomas has mentioned, the order of$g$is the smallest$k \ge 1$such that$g^k = 1 \mod p$. Let$q$be the order of the value$g$we use. If$g$is a generator for the entire group, then$q = p-1$, if not, it is some proper divisor of$p-1$. Now, if$...

13

$\phi(n)$ is the order of the multiplicative group of the numbers in $\mathbb{Z}_n$. $\phi$ is known as Euler's totient function. A consequence Lagrange's theorem is that any element of a group, raised to the order of the group is equal to the identity element. So, using $\phi(n)$ ensures that decryption works. Since $ed\equiv 1\bmod{\phi(n)}$, we can say ...

12

The quoted recommendations do little to prevent fields that are subject to the recent developments. Take the $\mathbb{F}_{2^{6120}}$ example: it clearly passes the field size criterion, but also the subgroup rule, as the group order $2^{6120} - 1$ has one $1536$-bit prime factor. Not all binary fields are affected equally, however. Both Göloğlu et al and ...

12

No, there is no known test that we can run on a 2048 bit composite number that would indicate whether it was the product of two primes, or whether it was the product of more than two primes. About the closest we can get is a zero knowledge proof; we know how someone (who does know the factorization) can run an interactive proof with us that can demonstrate ...

11

The problem of generating prime numbers reduces to one of determining primality (rather than an algorithm specifically designed to generate primes) since primes are pretty common: π(n) ~ n/ln(n). Probabilistic tests are used (e.g. in java.math.BigInteger.probablePrime()) rather than deterministic tests. See Miller-Rabin. http://en.literateprograms.org/...

11

Discrete logarithms in $\mathbb{F}_{p}$ share the same asymptotic complexity as integer factorization for general numbers: $L_p[1/3,1.923]$ for general integers, $L_p[1/3,1.587]$ for special integers. Discrete logarithms in $\mathbb{F}_{p^n}$ have the same asymptotic complexity as factoring special integers, i.e. $L_{p^n}[1/3, 1.587]$, via the Function ...

11

Where does the $\phi(n)$ part come from? Well, the actual requirement is that, if $n = pq$ and both $p$ and $q$ are prime, we have: $de \equiv 1 \mod p-1$ $de \equiv 1 \mod q-1$ The first ensures that RSA encryption, followed by RSA decryption, will obtain the original value modulo $p$. The second ensures that RSA encryption, followed by RSA decryption,...

10

This procedure is known as incremental search and his described in the Handbook of Applied Cryptography (note 4.51, page 148). Although some primes are being selected with higher probability than others, this allows no known attacks on RSA; roughly speaking, incremental search selects primes which could have been selected anyway and there are still ...

10

There are two approaches to such a validation: Test: you can look at the number and decide without involving the person who gave it to you. Proof: The person who generated the number can also give you additional information that will convince you it is a correct RSA number. There are no tests for RSA numbers. There are proofs for RSA numbers, including "...

10

In RSA, the public key is $e$ and private key is $d$, if: $ed=1 \mod{\phi (n)}$ To rearrange: $d=e^{-1} \mod{\phi (n)}$ In an public key system, it should be the case that one cannot compute the private key from the public key. Therefore, at least one of the variables should be kept private. In the above equation, everyone knows $e$, everyone can ...

9

$X^n + Y^n = Z^n$ (i.e. the impossibility of this with $n > 2$ and $X,Y,Z > 1$) is known as "Fermat's (big) theorem" (the one where the margin was not big enough for the proof). But the theorem important for RSA theory is known as "Fermat's little theorem": $$a^p \equiv a \mod p \text{ (if p prime)}$$ or, equivalent (for prime $p$ and $a < p$): $... 9 I think there are some gaps and some misunderstandings in what you say. A finite field or Galois field$GF(p^n)$is a collection of$p^nn$-dimensional vectors. Here,$p$is a prime, and each coordinate in a vector is an integer in the range$[0,p-1]$; that is, an element of$GF(p)$. Thus, $$\mathbf A = (a_0, a_1, \ldots, a_{n-1}), ~~ a_i \in GF(p)$$ is ... 9 There are no known implications of the ABC Conjecture to RSA. The ABC problem doesn't have even a superficial resemblance to the security of RSA. (The only point of connection is the fact that they both relate to prime numbers, but that is extremely thin. Much of number theory can say it is somehow related to prime numbers. It'd be like assuming that ... 9 Can an attacker learn some bits of a using this information? No. In the case of multiplication modulo a prime, we have, for any possible value of$a$, there is a unique value of$b$that makes$a \cdot b \bmod p$give any particular value of$c$in the range$(1, p-1)$. That is, even if we knew all the bits of$c$, no particular value of$a$are any more ... 8 There is a reduction from DL to RSA if the DL oracle accepts composite modulus. For prime modulus, a reduction is not known. I copied the following from this wikipedia page with minor edits. Let$n = pq$be RSA modulus. Generate random number$a$co-prime to$n$and random number$x < n$but very close to$n$. Compute$b = a^x \text{ mod } n$but don'... 8 Let me try a simple explanation of NFS. I will necessarily skip lots of details, but I hope you will get the main ideas. The number field sieve algorithm (NFS) is a member of a large family: index calculus algorithms. All algorithms in the family, which can be used for factoring and discrete logarithms in finite fields, share a common structure: ... 8 The zerocoin paper mentions such a technique: implementers can use the technique of Sander for generating so-called RSA UFOs for accumulator parameters without a trapdoor and refers to: T. Sander, “Efficient accumulators without trapdoor extended abstract,” in Information and Communication Security, vol. 1726 of LNCS, 1999, pp. 252–262. I ... 7 You can have a look at the Wikipedia page on the mathematics of CRC. Among freely available resources, see also chapter 2 of the Handbook of Applied Cryptography. The two main ways to view a CRC-32 are: It is a linear operation in the vector space$\mathbb{Z}_2^{32}$. This means that the$CRC(A \oplus B) = CRC(A) \oplus CRC(B)$("$\oplus\$" is XOR). It is ...

7

For numbers over about 115 (decimal) digits, the best algorithm currently known in the General Number Field Sieve (GNFS – sometimes just called the Number Field Sieve, though there's also a Special Number Field Sieve for factoring numbers of a special form). The GNFS, unfortunately, is an exceedingly complex algorithm, and I don't know of any online ...

7

No, the fact that there's no known practical formula that produces only prime numbers doesn't really come into play; if someone found one tomorrow, that wouldn't have any cryptographical implications. You may want to go through the How does asymmetric encryption work? thread; the short answer is that for public key operations, the public and the private ...

Only top voted, non community-wiki answers of a minimum length are eligible