Tag Info

Hot answers tagged

22

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


20

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


17

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.


16

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


15

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


15

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

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


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

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

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


10

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


10

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


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


9

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


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


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

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


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^n$ $n$-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 ...


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

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

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

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

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


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



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