# Tag Info

### 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 ...
• 133k
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 ...
• 16.8k
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,427
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 ...
• 125k
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$ ...
• 134

### Non-commutitive and nonassociative algebraic structures in cryptography

People have proposed schemes for building cryptographic hash functions using $SL_2$ (a non-commutative group over matrices). See, e.g., "Hashing with SL2", http://www.cerias.purdue.edu/apps/...
• 35.4k
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 ...