Hot answers tagged number-theory
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
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 ...
11
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 ...
10
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$.
...
9
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 ...
9
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
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 ...
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).
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
$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$):
...
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
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
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 ...
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
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
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.
5
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 ...
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 ...
5
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 ...
5
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 ...
5
I don't think there's anything to worry about here. Remarks 4.2 and 4.3 in the second paper point out that these approaches need to first find a point on a curve with a very large conductor/discriminant, and that seems to be very hard. (Harder than factoring the integer using NFS.)
There are many ways to compute factorings and discrete logarithms where you ...
4
To complete @Samuel's answer, there are a few shortcuts that can be used when n is composite; however, they only contribute small constant factors, hence they do not change the asymptotic behavior:
If n can be divided by r, then one can first solve the discrete logarithm in the subfield GF(2r). In a sieve-based algorithm, this can provide up to half the ...
4
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 ...
4
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 ...
4
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 ...
Only top voted, non community-wiki answers of a minimum length are eligible
