# Tag Info

## Hot answers tagged number-theory

23 votes

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

How could this allow for a backdoor? Well, if you do DH modulo a composite, an attacker can recover the shared secret if they can solve the DH problem (or the DLog problem) modulo each of the primes ...
• 134k
16 votes
Accepted

### Is it hard to compute $g^{ab}$ when given $(g, g^a, g^b, \frac{a}{b})$?

It is indeed a hard problem - in fact, it is at least as hard as the square Diffie-Hellman problem (SDH), which states that given $(g,g^a)$, it is infeasible to compute $g^{a^2}$. It is a standard and ...
• 17.1k
12 votes
Accepted

7 votes

### PhD in cryptography using elliptic curves

I can speak to the job-market part of the question. I work as a security architect at a company that makes authentication and encryption software products (read: crypto is at the core of every product)...
• 3,437
7 votes
Accepted

### Why do algebraic proofs apply to cryptography?

Integer operations as implemented on computers are isomorphic to a theoretical definition of integers. Otherwise operations would not give the correct results. Given the terminology in your question, ...
7 votes

### Why is Approximate GCD a hard problem?

The answer is that just because your algorithm is polynomial time doesn't mean it's fast. The paper Algorithms for the Approximate Common Divisor Problem claims in section 3.1 that a lattice ...
• 418
6 votes

• 211
6 votes

### Why do algebraic proofs apply to cryptography?

We know that the number theoretic model of integers do NOT always provide a perfect or even practically suitable model for the behavior of integers as implemented in computers. Applied cryptography ...
• 126k
6 votes
Accepted

### Why does square root $\pmod n$ find $p$ and $q$ (as $n = p \cdot q$)?

If $x^2\equiv1\mod{n}$, it means that $(x+1)(x-1)\equiv0\mod n$. In other words, $(x+1)(x-1)=k\cdot n=k\cdot p\cdot q$ for some $k\in\mathbb{N}$. And there you go: if $x\neq\pm 1\mod n$, neither $x+1$ ...
• 144
5 votes

### How "hard" it is to take an e'th root mod p?

It is very easy. $gcd(e,p-1)=1$ so there exist $k,t$ where $ek+t(p-1)=1$. Let $x$ be the $e$-th root of $y$, so $x^e=y \bmod p$. $y^k=x^{ek}=x\cdot {(x^{p-1})}^{-t}=x \bmod p$. Also in decryption ...
• 2,285
5 votes
Accepted

One way to approach this problem is to first look at the simpler problem of that cardinality of $x^e \bmod p$ where $p$ is prime, and $gcd(p-1, e)$ might not be 1. In that case, we have two cases: $x ... • 134k 5 votes Accepted ### How to solve the Diffie-Hellman problem if$g$is unknown? In general, there are a huge number of possible values for$g^{ab}$, depending on what$g$is. However, in this case, whoever set up this problem took care to radically reduce the number of ... • 134k 5 votes Accepted ### Size of$E$over$\mathbb{F}_p$contains$p+1$points For every$y \in \mathbf F_p$, there is a unique$x \in \mathbf F_p$such that$(x,y)$is on the curve, namely$x = \phi^{-1}(y^2)$, where$\phi : x \mapsto x^3+1$. Adding the point at infinity, that ... • 7,934 5 votes Accepted ### Why discrete logarithm modulo composite moduli not popular and not defined in standards? Such a scheme includes factorization as an additional barrier in case discrete logarithm modulo primes is broken and so why is this not popular and defined in standards? Actually, it would not be an &... • 134k 5 votes Accepted ### Is FFT for power-of-two cyclotomic rings possible if q is not 1 modulo 2n? Yes, in a way. When$q \neq 1 \mod 2n$the ring$R_q$is not fullt splitting (into polynomials of degree one). However, it might be splitting into several smaller polynomials of degree larger than one.... 5 votes Accepted ### RSA with exponent being a factor of modulus The key idea here is that$m_1$(or$m_2$) is very small relatively to the modulus. This lets us apply the usual Coppersmith techniques. We know that$c_1 = m_1^p \bmod n$, which entails$c_1 \equiv ...
• 11.9k

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