Number theory is the study of the properties and construction of numbers, particularly integers. Prime numbers are of particular interest to number theorists and consequently cryptographers as they are considered the "building blocks" of numbers and produce many interesting results which are useful ...
21
votes
4answers
6k views
How can I generate large prime numbers for RSA?
What is the currently industry-standard algorithm used to generate large prime numbers to be used in RSA encryption?
I'm aware that I can find any number of articles on the Internet that explain how ...
12
votes
4answers
4k views
Basic explanation of Elliptic Curve Cryptography?
I have been studying Elliptic Curve Cryptography as part of a course based on the book Cryptography and Network Security. The text for provides an excellent theoretical definition of the algorithm but ...
11
votes
3answers
1k views
For Diffie-Hellman, must g be a generator?
Due to a number of recently asked questions about Diffie-Hellman, I was thinking this morning: must $g$ in Diffie-Hellman be a generator?
Recall the mathematics of Diffie-Hellman:
Given public ...
11
votes
3answers
750 views
How robust is discrete logarithm in GF(2^n) ?
"Normal" discrete logarithm based cryptosystems (DSA, Diffie-Hellman, ElGamal) work in the finite field of integers modulo a big prime p. However, there exist other finite fields out there, in ...
9
votes
3answers
2k views
What is the relation between RSA & Fermat's little theorem?
I came across this while refreshing my cryptography brain cells.
From the RSA algorithm I understand that it somehow depends on the fact that, given a large number (A) it is computationally ...
8
votes
3answers
949 views
Which algorithms are used to factorize large integers?
Even if RSA decided to cancel the Factoring Challenge, it seems that some teams keep working on it. According to Wikipedia, RSA-768 has been factored in late 2009.
What are the current large integer ...
8
votes
3answers
372 views
Is it reasonable to assure that p-1 and q-1 aren't smooth?
I came across the requirement that, in RSA, $p-1$ and $q-1$ shouldn't be smooth, shouldn't consist of lots of small factors. Therefore my question:
How complicated is it to check whether $p-1$ is ...
7
votes
3answers
507 views
Modern integer factorization software
What are the modern software packages that can be used to factoring large numbers into primes. By modern I mean developed and made public within the last 5 years. I'm interested in things that are ...
7
votes
2answers
483 views
Selecting a large random prime
Say I want a random 1024-bit prime $p$. The obviously-correct way to do this is select a random 1024-bit number and test its primality with the usual well-known tests.
But suppose instead that I do ...
6
votes
3answers
439 views
Would the ability to efficiently find Discrete Logs have any impact on the security of RSA?
This answer makes the claim that the Discrete Log problem and RSA are independent from a security perspective.
RSA labs makes a similar statement:
The discrete logarithm problem bears the same ...
5
votes
3answers
548 views
Understanding CRC
There are zillions of articles describing CRC. What can I ready to understand more deeply what's really going on? Both from an algebraic perspective and a bit-manipulation perspective, I'd like to ...
5
votes
3answers
1k views
What place do prime numbers have in cryptography?
My understanding of hashing and encryption is rather limited. I certainly do not understand the mathematical formulas at play in these algorithms. With that said, what part do prime numbers play in ...
5
votes
1answer
173 views
Carmichael number factoring
Unsure whether this is the right forum for this question, worth a try.
The task im faced with is to implement a poly-time algorithm that finds a nontrivial factor of a carmichael number. Many ...
5
votes
1answer
120 views
Are there security issues with discrete logarithm keys not being uniformly distributed?
Generally, algorithms based on discrete logarithm specify that private keys are chosen as scalars between 1 and the order of the group (denoted q here). For instance IEEE P1363 and FIPS 186-3 both ...
5
votes
0answers
144 views
Prove that textbook RSA is susceptible to a chosen ciphertext attack
Given a ciphertext $y$, describe how to choose a ciphertext $\hat{y} \neq y$, such that knowledge of the plaintext $\hat{x}=d_K(\hat{y})$ allows $x=d_k(y)$ to be computed.
So I use the fact that the ...
4
votes
2answers
407 views
How do I solve this RSA instance for m?
How we can solve this equation and get the value of M?
$$8 = M^{13} \mod 33$$
not a computer program, but a mathematical operation.
4
votes
1answer
488 views
Do Rabin Fingerprints have any advantages over CRC?
Background
In both, bitstrings are interpreted as a polnomical over GF(2) and they each can be used to implement a hash over a sliding window. The definitions of each are as follows:
Rabin ...
3
votes
5answers
829 views
Galois fields in cryptography
I don't really understand Galois fields, but I've noticed they're used a lot in crypto. I tried to read into them, but quickly got lost in the mess of heiroglyphs and alien terms. I understand they're ...
3
votes
1answer
864 views
How to practically find solutions to a discrete logarithm?
Are there any ongoing or current practical attempts to solve instances of the discrete logarithm problem of the order of magnitude used in cryptographic applications, for example with a 256 bit ...
3
votes
1answer
128 views
Impact of algorithms for factoring using elliptic curves over $\mathbb{Q}$
Recently a few papers have appeared that describe a new approach to factoring, using elliptic curves over $\mathbb{Q}$. See, e.g.,
Factoring integers and computing elliptic curve rational points, ...
3
votes
1answer
122 views
How to find an element of high-order in an RSA group?
Is this even possible? The RSA group is not cyclic, so usually you wouldn't find a generator for accessing all group elements.
What happens if you use the RSA group in a scenario where you want that ...
3
votes
1answer
72 views
Why work in a subgroup QR(n) of an RSA group $Z^*_n$?
I sometimes read in papers that a (sub-)group generator $g$ is taken from $\mathrm{QR}(n)$ instead of $\mathbb{Z}^*_n$, where $n = p \cdot q$ and $p$ and $q$ are prime. Is there a reason for this? ...
3
votes
1answer
179 views
A discrete-log-like problem, with matrices: given $A^k x$, find $k$
Let $p$ be a large prime; we will work in $GF(p)$. Let $A$ be a $n\times n$ matrix. Also, let $x$ be a $n$-vector and $k$ a positive integer.
Suppose we are given $p$, $A$, $x$, and $y$. The goal ...
3
votes
1answer
108 views
Is there a group of prime order which could fit the CT-Computational Diffie-Hellman assumption?
I'm trying to choose a group that is hard under the Chosen-Target Computational Diffie-Hellman assumption, according to the definition in this paper, in order to implement the oblivious transfer ...
3
votes
0answers
125 views
Finding where I am in a linear recurrence relation
Suppose I have a linear recurrence relation
$$a(n) = c_1 a(n-1) + \dots + c_k a(n-k) + d,$$
where the constants $c_1,\dots,c_k,d$ are given and the initial values $a(0),\dots,a(k-1)$ are given as ...
2
votes
3answers
193 views
Discrete log problem, when we have many examples
Suppose I have many instances of the discrete log problem, all using the same unknown exponent. Is this problem easier than the standard discrete log problem?
Oh, heck, I should be more precise. ...
2
votes
2answers
312 views
Inverses in Truncated Polynomial Rings
I've been trying a long time to understand a thing which is obviously extremely simple, but I just can't get it.
Read this, please:
The NTRUEncrypt PKCS uses the ring of truncated polynomials $R$ ...
2
votes
2answers
183 views
Background for modular arithmetic function
I'm investigating this function:
$a := ((b\cdot c) \bmod k) - (b \cdot c)/k$
where $/$ indicates integer division.
Two things I've noticed:
It's equivalent to multiplying a·b, and then ...
2
votes
1answer
69 views
Discrete log analog of ECM factoring algorithm?
Anecdotally, most factoring algorithms have a corresponding variant algorithm that can be used to attack the discrete log problem using similar ideas.
Is there an analog of the elliptic curve (ECM) ...
2
votes
1answer
168 views
How to construct a zero-knowledge proof of a number of the form $n=p^a q^b$
Let $n = p^a$$q^b$ where p and q are distinct primes and a and b are positive integers. How to construct a zero knowledge proof that n is of such form?
This is actually a homework problem with a ...
1
vote
2answers
238 views
Is there an algorithm for factoring N, which is just as simple as this one, but faster?
I found a simple algorithm for factoring semiprime numbers, you can read about it in Factoring Semiprimes and Possible Implications for RSA.
It basically works like this:
You reverse the digits in ...
1
vote
1answer
145 views
What does modular inversion mean?
I'm trying to implement an e-voting algorithm, which is described at the paper "Internet Voting Protocol Based on Improved Implicit Security" by Abhishek Parakh & Subhash Kak.
At the Example 1 ...
1
vote
1answer
499 views
ABC Conjecture's Impact on RSA Encryption
A recent proof of the ABC Conjecture has been released by one Shinichi Mochizuki. Now, I'm not well versed in mathematics but it would appear that this proof implies that finding prime factors could ...
1
vote
1answer
337 views
How can I use eulers totient and the chinese remainder theorem for modular exponentiation?
I'm trying to implement modular exponentiation in Java using Lagrange and the Chinese remainder theorem.
The example we've been given is:
Let $N = 55 = 5 · 11$ and suppose we want to compute ...
1
vote
1answer
81 views
Zero-knowledge proof that a group element is a quadratic residue?
In a paper it says: "To convince a verifier that a group element is a quadratic residue, the prover executes the following proof with the verifier":
$PK \left\{ (\alpha) : y = \pm g^\alpha \right\}$
...
1
vote
1answer
78 views
How difficult is it to check if a group element is in a sub group?
I am just curious. We have a group $G$ and its subgroup $H$ with a generator element $h \in H$. How difficult is it to check for $x \in G$ that $x \in \langle h \rangle$? Is there a better way than ...
1
vote
1answer
186 views
What does $(\mathbb{Z}_n^*)^2$ mean?
In a paper they write once, $(\mathbb{Z}_n^*)^2$. Is this the group of quadratic residues or is it something else?
Here the theorem:
Under the strong RSA assumption, given a modulus $n$, along with ...
1
vote
1answer
51 views
Comprehension question on a signature protocol based on the RSA assumption
We have the following two-party protocol between Alice and Bob. Alice sends messages $m_1, m_2, \ldots \in_R \mathbb{Z}_n^*$ to Bob and Bob signs these values by calculating $v_1, v_2, \ldots \in_R ...
1
vote
1answer
125 views
Is this attack for RSA possible?
$N=p·q$ ($p$ and $q$ are prime numbers), $m_1, ..., m_x$ are the messages, $e$ and $d$ are RSA encryption and decryption exponents, respectively.
I am given $e, m_1, m_1^e, m_1^d, ..., m_x, m_x^e, ...
0
votes
1answer
104 views
How to solve the reverse of an equation that uses MOD?
I've been tasked with reverse engineering an unknown crypto function. The function uses the following constants:
$a=380951$:
I noticed that this is a prime number
$b=3182$:
I noted that this is a ...
0
votes
1answer
133 views
What are some different cryptography methods?
Some of the most effective cryptography methods and algorithms are based of factoring large prime numbers (e.g. RSA). I'm curious whether there are some other cryptography methods. Somethings that is ...
0
votes
1answer
85 views
Montgomery Exponentiation - selecting input value R for a given BigInteger
I have Montgomery exponentiation working, but it's working quite slow. I suspect there are two reasons for this - I implemented it bit size instead of word size (I didn't realize at the time that ...
0
votes
0answers
37 views
Is it possible to determine the group order by knowing the “public” and “private” key exponents in an RSA group?
I have an RSA group with modulus $n = p \cdot q$, two safe primes $p=2p'+1$ and $q=2q'+1$ and the "public" and "private" key exponents $d$ and $e$. $\phi(n) = 4p'q'$ is the order of the RSA group. If ...
-3
votes
0answers
64 views
Show that for all integers n>2, n does not divide n^2+2 [closed]
I believe this solution can be solved by induction, I just don't know how to phrase it recursively.
For all n>2, n^2+2 mod n ≠ 0
Base case n=3
3^2 + 2 =11
11 mod 3 = 2 ≠ 0.
Show that
(n-1)^2 +2 ...
