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 ...
user avatar
  • 133k
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 ...
user avatar
12 votes
Accepted

How is information disclosed by modular multiplication?

Can an attacker learn some bits of a using this information? No. In the case of multiplication modulo a prime, we have, for any possible value of $a$, there is a unique value of $b$ that makes $a \...
user avatar
  • 133k
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[...
user avatar
11 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 (...
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 (...
user avatar
  • 133k
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 ...
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 ...
user avatar
  • 10.6k
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$. ...
user avatar
  • 10.6k
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 ...
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)$ ...
user avatar
7 votes
Accepted

Non adjacent form of an integer is unique

Non-Adjacent Form (NAF), also called Balanced Binary Representation (BBR), is a representation of integers reminiscent of binary, but with an extra $-1$ value for digits, and such that at least one of ...
user avatar
  • 125k
7 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 ...
user avatar
  • 125k
7 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, $\...
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)...
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, ...
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 ...
user avatar
  • 418
6 votes

What if the p and q used in keys generation of Pailler cryptosystem are composite?

For starters: Paillier and RSA are based on very similar assumptions, and both systems would be broken immediately by an algorithm to factor large composites. Additionally, knowing $\phi(n)$ or $\...
user avatar
  • 12.3k
6 votes
Accepted

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

When decrypting in lattice-based cryptosystems, one computes a value $v \in \mathbb{Z}_q$ that is guaranteed to be congruent to a "small" integer $e \in \mathbb{Z}$, where $e$ encodes the message (e.g....
user avatar
6 votes

Is it possible to validate a Public Key in RSA?

No, we do not know an algorithm running in linear time (or even polynomial time, relative to the number of digits in $n$) that outputs 'true' if $n$ is the product of exactly two prime numbers, and '...
user avatar
  • 125k
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{...
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 ...
user avatar
  • 125k
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$ ...
user avatar
  • 134
5 votes

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/...
user avatar
  • 35.4k
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 ...
user avatar
5 votes
Accepted

Computing the cardinality of the co-domain of specific modular exponentiations

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 ...
user avatar
  • 133k
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 ...
user avatar
  • 133k
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 ...
user avatar
  • 7,914
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 &...
user avatar
  • 133k
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....
user avatar

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