24 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 ...
poncho's user avatar
  • 147k
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 ...
Geoffroy Couteau's user avatar
12 votes
Accepted

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

I've since then wrote a paper to answer this question (of course with a huge help from Poncho) I found many ways to implement a backdoor, some are Nobody-But-Us (NOBUS) backdoors, while some are not (...
David 天宇 Wong's user avatar
11 votes
Accepted

Is it possible to generate backdoored DH parameters?

A trapdoor in a discrete log group was first suggested in 1992 by Daniel M. Gordon[1] in response to the recently proposal by NIST for the Digital Signature Standard (among hundreds of other responses[...
Squeamish Ossifrage's user avatar
11 votes
Accepted

Which properties of a group are used in the steps of Diffie Hellman?

I’m trying to understand which properties of a group are used in DHKE at each step. Actually, you can implement a DH-style operation in any semigroup; you need closure, and you need associativity (...
poncho's user avatar
  • 147k
9 votes

Non-commutitive and nonassociative algebraic structures in cryptography

A self-distributive algebra is an algebra $(X,*)$ that satisfies the identity $x*(y*z)=(x*y)*(x*z)$. There are several cryptosystems that use self-distributive algebras as platforms and these ...
Joseph Van Name's user avatar
9 votes

PhD in cryptography using elliptic curves

If you want to end up in the industry, I strongly doubt a PhD is a good investment of your time, regardless of the rest of this discussion. I believe a general purpose quantum computer, the kind that ...
Meir Maor's user avatar
  • 11.8k
9 votes

Why can every prime number be written as 6k±1?

I am not sure if this question should be considered on topic here, but I will answer anyway. Theorem: All prime numbers larger than $3$ can be written as $6k+1$ or $6k-1$ for some natural number $k$. ...
Meir Maor's user avatar
  • 11.8k
9 votes
Accepted

Concrete example of Montgomery Multiplication

In this answer we study modular multiplications using Montgomery arithmetic, illustrated with the example $7510\cdot 8431\cdot 2143\bmod9137$, working in base $\beta=10$ because the question does. ...
fgrieu's user avatar
  • 141k
8 votes

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

A useful way to understand the extended Euclidean algorithm is in terms of linear algebra. (This is somewhat redundant to fgrieu's answer, but I decided to post this anyway, since I started writing ...
Ilmari Karonen's user avatar
8 votes

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

The method in the other answer is didactic, but requires backtracking earlier calculations, and thus having kept these or use of recursion, which is undesirable in constrained environments as often ...
fgrieu's user avatar
  • 141k
8 votes
Accepted

Difference between $Z^*_n$ and $Z_n$

$\mathbb{Z}_n^*$ doesn't mean $\mathbb{Z}_n - \{0\}$. You must remove all elements that are not invertible mod $n$, which is equivalent to keeping only the elements that are coprimes to $n$. So, $\...
Hilder Vitor Lima Pereira's user avatar
8 votes
Accepted

Why is Approximate GCD a hard problem?

TL;DR The AGCD problem does require asymptotic exponential time to be solved. In general, LLL cannot solve the AGCD problem The parameters $(\gamma, \eta, \rho) = (\lambda^5, \lambda^2, \lambda)$ ...
Hilder Vitor Lima Pereira's user avatar
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)...
Mike Ounsworth's user avatar
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, ...
Gilles 'SO- stop being evil''s user avatar
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 ...
robertkin's user avatar
  • 428
6 votes

Is there a security problem with this prime generation algorithm?

This is the approach that finally let us factor $N$ for the competition. I believe it completely breaks the given scheme. Let's write down the formula for $N$: $N = pq = \frac{3s^4+1}{4}\cdot\frac{...
Niklas B.'s user avatar
  • 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 ...
fgrieu's user avatar
  • 141k
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$ ...
zajic's user avatar
  • 154
5 votes

Is it possible to fool Miller-Rabin test?

If you test really random numbers then the Miller-Rabin test works as well as described by user4982. But if someone evil is giving you the "prime numbers" to test, they can be composite and ...
j.p.'s user avatar
  • 1,568
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 ...
poncho's user avatar
  • 147k
5 votes
Accepted

Why are some group representations much easier to compute discrete logarithm for?

Well, the group being isomorphic doesn't imply that the isomorphism is efficiently computable. If $G \simeq H$ via $\phi : G \rightarrow H$ and $\phi$ is computable, then indeed, DLOG is no harder in $...
LeoDucas's user avatar
  • 1,213
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 ...
fkraiem's user avatar
  • 8,122
5 votes

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

Bad news is that what you ask for is impossible to achieve with the proposed Guillou-Quisquater (GQ) identification protocol. Unfortunately, $\Sigma$-protocols for group-homomorphisms are not ...
István András Seres's user avatar
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 &...
poncho's user avatar
  • 147k
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....
Tjerand Silde's user avatar
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 ...
Samuel Neves's user avatar
  • 12.5k
5 votes
Accepted

Discrete Logarithm Challenges and Records

For discrete log over $\mathbb{Z}_p^{*}$, as of 2019, a discrete logarithm was computed over a 795 bit safe prime [1]. In practice, no one uses generic discrete logarithm algorithms (such as pollard ...
Wilson's user avatar
  • 929
4 votes

Is there a security problem with this prime generation algorithm?

It would appear that the $p-1$ factorization method can be adapted to factor numbers of this form with nontrivial probability. We have $4n = (3*r_p^4 + 1)q = (11*r_q^4 + 1)p$ (where $r_p$ is the ...
poncho's user avatar
  • 147k
4 votes

Strange modular expression in paper on group signatures

In this context $1/e_i$ (more commonly written as $e_i^{-1}$) stands for the multiplicative inverse of $e_i$ modulo the relevant modulus, which in this case is $\lambda(n) = \text{lcm}(p-1,q-1)$. ...
poncho's user avatar
  • 147k

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