# Tag Info

## Hot answers tagged number-theory

15

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

14

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

12

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

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 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$. ... 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 ... 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 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 ... 8 Msieve is public domain and has good reputation. For instance, a 631-bit integer was factored in late 2010 with Msieve used (at least for some parts). 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 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 ... 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 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 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 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. ... 7 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: ... 6 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. 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 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 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 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 ...

6

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

6

Actually, it does appear to be feasible to construct such a public key, with the caveats that: the public exponent $e$ will be large. While this is legal, most public keys have a small $e$ the modulus may be more vulnerable than usual to a specific (normally nonoptimal) factorization method. However, how vulnerable it is can be controlled. (Note: I'll ...

5

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

5

The discrete logarithm problem can be attacked with either a specific or a generic algorithm. A specific algorithm is one that tries to exploit structural weaknesses of the specific group in which discrete logarithm is used; e.g. Index Calculus when we are talking about exponentiation modulo a big prime. Generic algorithms only use the group law and thus ...

5

No, it's not that Fermat Theorem. It's Fermat's Little Theorem which states If $p$ is prime, then $a^p$ is congruent to $a$ modulo $p$. This theorem is needed in the proof of correctness of the RSA algorithm (the Chinese remainder theorem is needed as well). Any introductory text that covers RSA should cover this (and any introductory text that does ...

5

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

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