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

learn more… | top users | synonyms

28
votes
4answers
15k 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 ...
18
votes
4answers
10k 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 ...
15
votes
3answers
2k 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 ...
15
votes
3answers
1k 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 ...
11
votes
3answers
2k 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 ...
11
votes
1answer
423 views

Do recent announcements about solving the DLP in $GF(2^{6120})$ apply to schemes proposed for cryptographic use?

A recent paper by Göloğlu, Granger, McGuire, and Zumbrägel: Solving a 6120-bit DLP on a Desktop Computer seems to "demonstrate a practical DLP break in the finite field of $2^{6120}$ elements, using ...
10
votes
4answers
2k views

Why RSA encryption key is based on modulo $\varphi(n)$ rather than modulo $n$

While calculating RSA encryption key we take modulo $\varphi(n)$ rather that modulo $n$. I couldn't understand why its so?
10
votes
1answer
4k views

Calculating RSA private exponent when given public exponent and the modulus factors using extended euclid

When given $p = 5, q = 11, N = 55$ and $e = 17$, I'm trying to compute the RSA private key $d$. I can calculate $\varphi(N) = 40$, but my lecturer then says to use the extended Euclidean algorithm to ...
9
votes
5answers
2k 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 ...
9
votes
3answers
3k 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 ...
9
votes
2answers
763 views

Can I select a large random prime using this procedure?

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 ...
8
votes
3answers
964 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 ...
8
votes
3answers
444 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 ...
8
votes
2answers
396 views

Given a message and signature, find a public key that makes the signature valid

Given a message $M$ and a signature $S$, is it feasible to find a RSA public key $(n,e)$ such that $S$ verifies as a valid signature on $M$ (using this public key)? What if we're given one public key ...
7
votes
3answers
331 views

Building a hard to factor number without knowing its factorization

It is possible to find an efficient algorithm for constructing a provably hard to factor number $N$, together with a witness that shows that it is indeed hard to factor. EDIT, since it was not clear: ...
7
votes
3answers
1k 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 ...
7
votes
3answers
983 views

Understanding CRC

There are zillions of articles describing CRC. What can I read to (more deeply) understand what's really going on? Both from an algebraic perspective and a bit-manipulation perspective, I'd like to ...
7
votes
0answers
77 views

Has the distributed project “Number Fields @ Home” project benefited cryptography in any meaningful way?

Is there any new understanding, property, or knowledge that has come from the Number Fields @Home distributed computing project? Has any outcome advanced the study of cryptography, or altered ...
6
votes
3answers
2k 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 ...
6
votes
1answer
176 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 ...
6
votes
1answer
330 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 ...
6
votes
1answer
224 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 ...
5
votes
2answers
675 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.
5
votes
5answers
459 views

Is there a technique to confirm that a given large integer value is a product of two primes?

Given a list of 2048 bit integer values in which one or few 2048 bit integer values may be product of two prime numbers and other values may be just 2048 bit odd integers numbers. My question is - ...
5
votes
1answer
130 views

Is it possible to fool Miller-Rabin test?

It is well known that it's possible to fool Fermat test with Carmichael numbers. But, is it possible to deliberately fool many-rounded Miller-Rabin test by constructing some special number without ...
5
votes
1answer
547 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
748 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 ...
4
votes
4answers
408 views

Where does the $\varphi(n)$ part of RSA come from?

$e d \equiv 1 \pmod{\varphi(n)}$ Where does the $\varphi(n)$ part come from? How did the inventors of RSA arrive at $\varphi(n)$?
4
votes
3answers
319 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. ...
4
votes
1answer
392 views

AES mixcolumn stage

I'm studying AES, and am having problems with the "mixcolumn" stage. I read about finite fields, but I still don't know. How do I construct $GF(2^8)$? ...
4
votes
1answer
171 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? ...
4
votes
1answer
1k 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 ...
4
votes
1answer
265 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 ...
4
votes
1answer
150 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 ...
4
votes
1answer
232 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 ...
3
votes
1answer
108 views

Is the strength of RSA over quadratic or other cyclotomic fields as strong as over the integers?

If we assume the strength of RSA is based on the difficulty of factoring (which I know we can't guarantee) and we compose the modulus of some other quadratic ring that is a unique factorization domain ...
3
votes
2answers
268 views

Breaking a PRNG Scheme

Assume the following scheme for a PRNG generating decimals in [0,100) Given a message and a key, compute tag := HMAC512(message, key). Take the first 5 hexadecimal characters of the tag. If the ...
3
votes
2answers
79 views

Possible to check if $a \in \mathrm{QR}_n$?

It is possible to check $a \in \mathrm{QR}_p \text{ iff } a^{(p-1)/2} \equiv 1\ (\bmod\ p)$ if $p$ is a prime. $n$ is a large RSA modulus. Is it also possible to check if $a \in \mathrm{QR}_n$ if the ...
3
votes
1answer
174 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
196 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
2answers
481 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$ ...
3
votes
1answer
158 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, ...
3
votes
2answers
199 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
166 views

How did they factor RSA-704?

I don't understand the 'Wiedemann algorithm' works. Can someone explain the factoring of RSA-704 in an easy way?
2
votes
1answer
973 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 ...
2
votes
1answer
570 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 ...
2
votes
1answer
172 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\}$ ...
2
votes
1answer
246 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 ...
2
votes
1answer
93 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 ...
2
votes
1answer
65 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 ...