# Tag Info

## Hot answers tagged number-theory

### 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
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
Accepted

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

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

• 211

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

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