# Questions tagged [number-theory]

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 in cryptography. Questions covering number theory and primes should use this tag; questions involving finite fields and groups might use this tag if relevant.

40 questions
Filter by
Sorted by
Tagged with
78k 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 ...
19k 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 ...
12k 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 ...
216 views

### Is it possible to generate backdoored DH parameters?

I know it has been already asked and answered whether it's possible to generate weak DH parameters. But "recentely" we experienced the Logjam attack, which makes use of the pre-computation ...
82k 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 ...
3k 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 ...
5k views

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

While calculating RSA encryption key we take modulo $\varphi(n)$ rather than modulo $n$. I canāt understand why itās done this way.
6k 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 ...
1k 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 ...
652 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: ...
34k 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 ...
18k 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 ...
10k views

### Is it possible to validate a Public Key in RSA?

If I have a 1024-bit number, and someone is telling me that it is in fact a valid RSA public key, is there any way I can quickly validate that it is indeed so (without cracking RSA)? (I suppose I am ...
2k 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 ...
328 views

### What is the difference between the standard representants of $\mathbb Z/q\mathbb Z$?

The symbol $\mathbb Z/q\mathbb Z$ (given that $q$ is prime) represents the prime field $\mathbb Z_q$. Basically, the elements of this field are represented by $\{0, 1, \dots, q-1\}$, let's call this ...
310 views

### How is information disclosed by modular multiplication?

Consider the case that $c = a \cdot b \mod p$ where $p$ is a known prime and $0 < a < p$ and $0 < b < p$ are unknown integers numbers. Furthermore, some bits on the value of $c$ are ...
4k views

### How does a non-prime modulus for Diffie-Hellman allow for a backdoor?

Recently someone found that a Diffie-Hellman modulus used in a unix tool (socat) was not prime. This led some people to shout "backdoor". What I don't understand ...
2k 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 ...
306 views

### Which area of Maths should I pursue?

I would like to know which area of Mathematics would be most beneficial to cryptography. Surely Algebraic Number Theory and maybe to a lesser extend, Elliptic Curves, are closely linked to ...
3k views

### Understanding CRC [closed]

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 ...
522 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)$?
1k views

### Why is Approximate GCD a hard problem?

There are many Fully Homomorphic Encryption over the Integers schemes whose security is based on the intractability of the Approximate GCD (AGCD) problem. The paper Algorithms for the Approximate ...
889 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 ...
1k 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 ...
1k 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 ...
2k 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)$? ...
248 views

### Proving the knowlege of e-th root in an non-interactive way

Just like in this question: Protocol for proof of knowledge of $l$-th root I want to prove that for $u^e = w$ I know $u$ without revealing it. Three other requirements are: e is small (65537) The ...
1k views

I know it's hard to find the $e$th root of a number mod $n=p_1*p_2$, and if it would be possible we could break RSA. But how hard it is to take an $e$th root mod $p$ where $p$ is a prime and $\gcd(e,p-... 1answer 829 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 ... 1answer 481 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 well.... 1answer 866 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 ... 2answers 411 views ### Non-commutitive and nonassociative algebraic structures in cryptography Are there any cryptographic algorithms or primitives that have been developed and studied that make use of non-commutative or non-associative algebraic structures such as quaternion integers or ... 2answers 1k views ### Is computing roots moduli a composite$N$a hard problem without knowing the factorization of$N$? Suppose that we are given$\mathbb{Z}_{N}$and an element$x^u \in \mathbb{Z}_{N}$with$u \in (0,l]$where$l$is the bit-size of$N$. Is it difficult to recover$x$by knowing$u$without knowing ... 2answers 209 views ### More general - what is the hard problem of recovering r from r*p mod q? I would like to know the cryptographic hard problem that is most closely tied to recovering integer$r$from the modular product$r\times p\mod q$. (This is a simplification of an earlier post that ... 1answer 4k 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$27^{...
In the key generation step of paillier cryptosystem , In order to satisfy $\gcd(pq,(p-1)(q-1))=1$ , we can take equal length primes. Instead of taking(length as parameter to generate $p,q$) equal ...