# Tag Info

## Hot answers tagged number-theory

16

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 ...

16

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 ...

13

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 ...

13

Firstly, a number theory textbook might well help here. I own An Introduction to the theory of numbers which will give you a grounding in this and many other number theory topics which crop up in crypto. It's not my favourite book notation-wise, but in terms of topics covered it is very thorough. Now, on to what you need help with. There exists a theorem ...

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

To walk you through RSA from start to end, here's how it works. Choose two large distinct primes $p$, $q$. Calculate $n=pq$. Calculate $\phi(pq)$. This happens to be $(p-1)(q-1)$. Choose $e$ such that $gcd(e, \phi(pq)) = 1$ and $1 < e < \phi(pq)$. Compute $d$ such that $de = 1 \mod \phi(pq)$. Do some crypto; $c = t^e \mod n$ and $t = c^d \mod n$. ...

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 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 ... 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 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 ... 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 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-1de \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 ... 9 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 ... 9 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 ... 8$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$): ... 8 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. ... 8 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 ... 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: ... 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 In addition to Msieve factor is a public-domain integer factorization program for Windows. Qsieve, a suite of programs for integer factorization. Factorization source code and other related code is here There is a database of prime numbers here like List of all saved primes (500 digits+) and here is a list of factorization software and libraries. 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 ... 7 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 ... 6 256-bit discrete logarithms on a prime field are definitely not of the order of magnitude used in cryptographic applications. Secure sizes for this problem are in the thousands of bits, very much like integer factorization. To break that example discrete logarithm, you probably want to use Index Calculus, more specifically the Linear Sieve. Resorting to the ... 6 Antoine Joux very kindly sent me the following on the topic: People worry that [logarithms over fields with composite exponent] might be easier, this is why they use prime exponent. For some factorization of the exponent, viewing the finite field as a tower of extensions$(p^{n_1})^{n_2}$indeed makes things easier. See "The function field sieve ... 6 Checking for smoothness can be computationally expensive, depending on the size of the "small" primes (there is no "natural" definition of "small", one has to define an arbitrary limit). Also, it is not really useful. The need for non-smooth integers comes from the$p-1$factorization method. Let$n = pq$be a RSA modulus that we wish to factor. Now suppose ... 6 Factor the modulus,$n$which was given as 33, to yield$p = 3$and$q = 11$. The totient,$\phi$is$(p - 1)(q - 1) = 20$. The public exponent,$e$is given as$13$. Now compute the private exponent$d$as the multiplicative inverse of$e \mod \phi$, so$e^{-1}\mod \phi \equiv 17$. The cipher text,$c$is given as 8. Finally compute the message,$M$as ... 6 Pure nonsense. For choosing the random$\Delta$between$\sqrt{\min(N, Ň)}$and$\sqrt{\max(N, Ň)}$there are too many possibilities for it to work. For example whenever the first and last digits of$N$differ, you get something like$\frac{1}{10} \cdot \sqrt N$possibilities (the exact formula doesn't matter). So you can replace the first formula$gcd[N, ...

6

Notice that the result says 67 mod 257. All calculations here are being done modulo 257. So, 101^-1 is actually the modular inverse of 101 mod 257, which is 28. Similarly, 85 * 28 is also done modulo 257.

6

Well, the reason that a specific cryptographical object needs to work in a specific subgroup probably has to do with the details of that object, and the cryptographical properties it needs from the subgroup. One obvious possibility is that they need to avoid leaking information via the Jacobi symbol; that is an easily computed function that maps values in ...

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