22

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 that make up the composite. There are a couple of ways that could be used by someone who knows the factorization to solve the DLog problem easier than expected....


17

The quoted recommendations do little to prevent fields that are subject to the recent developments. Take the $\mathbb{F}_{2^{6120}}$ example: it clearly passes the field size criterion, but also the subgroup rule, as the group order $2^{6120} - 1$ has one $1536$-bit prime factor. Not all binary fields are affected equally, however. Both Göloğlu et al and ...


16

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 well-studied assumption, and it can be reduced to CDH (correcting a previous version of this answer where I said it does not - I was confusing with the ...


14

$\phi(n)$ is the order of the multiplicative group of the numbers in $\mathbb{Z}_n$. $\phi$ is known as Euler's totient function. A consequence Lagrange's theorem is that any element of a group, raised to the order of the group is equal to the identity element. So, using $\phi(n)$ ensures that decryption works. Since $ed\equiv 1\bmod{\phi(n)}$, we can say ...


12

No, there is no known test that we can run on a 2048 bit composite number that would indicate whether it was the product of two primes, or whether it was the product of more than two primes. About the closest we can get is a zero knowledge proof; we know how someone (who does know the factorization) can run an interactive proof with us that can demonstrate ...


12

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 \cdot b \bmod p$ give any particular value of $c$ in the range $(1, p-1)$. That is, even if we knew all the bits of $c$, no particular value of $a$ are any more ...


11

Where does the $\phi(n)$ part come from? Well, the actual requirement is that, if $n = pq$ and both $p$ and $q$ are prime, we have: $de \equiv 1 \mod p-1$ $de \equiv 1 \mod q-1$ The first ensures that RSA encryption, followed by RSA decryption, will obtain the original value modulo $p$. The second ensures that RSA encryption, followed by RSA decryption, ...


11

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 (so $A^3 = A\times A \times A = (A \times A) \times A = A \times (A \times A)$ is well defined), but other than that, you really don't need anything. You don't ...


10

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[2] including an objection to the now-infamous random generation of the per-signature secret). Though the computational cost was too high for an academic ...


9

What is Rijndael's finite field? Rijndaels finite field is $F=\mathrm{GF}(2^8)$ with minimal polynomial $f(x)=x^8 + x^4 + x^3 + x + 1$. Formally, we have $F=\mathbb F_2[x] / (f)$ but don't worry about that. So what does this mean? Well, elements of $F$ should be thought of as polynomials over $\mathbb{F}_2$, with the added fact that the minimal polynomial ...


9

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 cryptosystems should be thought of as non-associative versions of the more well-known non-abelian group based cryptosystems (such as the Anshel-Anshel-Goldfeld and Ko-...


9

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 (I also give some numbers of "security" for the NOBUS ones in the paper). The idea is to look at a natural way of injecting a backdoor into DH with Pohlig-...


9

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 will send us all to relearn all our algorithm theory, is far from certain in 20 years. I won't even be surprised if someone publishes tomorrow a serious proof ...


9

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$. Proof: The remainder of a number modulo $6$ is between $0$ and $5$. If it is $1$ or $5$, the above criterion holds. It remains to show that, if it is $0$, $2$,...


8

Let me try a simple explanation of NFS. I will necessarily skip lots of details, but I hope you will get the main ideas. The number field sieve algorithm (NFS) is a member of a large family: index calculus algorithms. All algorithms in the family, which can be used for factoring and discrete logarithms in finite fields, share a common structure: ...


8

The zerocoin paper mentions such a technique: implementers can use the technique of Sander for generating so-called RSA UFOs for accumulator parameters without a trapdoor and refers to: T. Sander, “Efficient accumulators without trapdoor extended abstract,” in Information and Communication Security, vol. 1726 of LNCS, 1999, pp. 252–262. I can'...


7

In fact even brute force does not work, unless you know what random numbers the Miller-Rabin test will use to test the numbers, because in case of each possible non-prime number, some Miller-Rabin test input will reveal it is composite. FIPS 186-4 C.3 contains recommended Miller-Rabin number of rounds to use to test the numbers. Those amounts of Miller-...


7

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 used for crypto. Another commonly taught method is the full extended Euclidean algorithm, which finds Bézout coefficients without recursion. However that requires ...


7

There are three distinct computational problems related to RSA. They are: FACTORIZATION: given an RSA modulus $n$, find its prime factors $p$ and $q$; ORDER: given an RSA modulus $n$, find the order $\lambda$ of the multiplicative group modulo $n$; RSA Problem: given a ring element $a \in \mathbb{Z}_n$, a public exponent $e$ and an RSA modulus, find an ...


7

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 two adjacent digits is $0$. Because the resulting representation has at least half of its digits at zero (typically about $2/3$), it can be used to speed-up ...


7

$\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, $\mathbb{Z}_n^* = \{x \in \mathbb{Z}_n : \exists x^{-1} \in \mathbb{Z}_n \} = \{x \in \mathbb{Z}_n : gcd(x, n) = 1\}$. This is necessary since all elements in a ...


7

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). Finding people to hire who can pass an interview on web dev, AWS, or even C++ and linux kernel dev is easy compared with finding people to hire who can pass ...


7

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, I suspect that when you think of integer operations on a computer, you're thinking of operations on machine words. Cryptography uses numbers that don't fit in ...


7

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 dimension $>800$ "should be large enough to prevent any practical lattice attack". As a completely non-rigorous yet enlightening demonstration, we can compare the ...


7

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)$ proposed in DGHV10 guarantee (asymptotic) security level of $2^{\Omega(\lambda)}$. Lattice attacks on the AGCD problem You are supposing that one can solve the ...


6

Actually, it does appear to be feasible to construct such a public key, with the caveats that: the public exponent $e$ will be large. While this is legal, most public keys have a small $e$ the modulus may be more vulnerable than usual to a specific (normally nonoptimal) factorization method. However, how vulnerable it is can be controlled. (Note: I'll ...


6

The relationship between recovering the decryption exponent $d$ and factoring the RSA modulus $n=pq$ is a classical question in cryptography. There are three useful answers: The first answer deals with a slightly different question but is useful to gain some insight into the problem. Assume that we given a bit more than $e$ and $d$, more precisely that ...


6

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 this before fgrieu expanded their answer. Hopefully the slightly different perspective may still be useful.) Let's say we're trying to find the inverse of $e$ ...


6

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., as the parity of $e$ modulo 2). By using the integer representatives between $-q/2$ and $q/2$, one can recover the small integer $e$ (and thereby recover ...


6

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 $\lambda(n)$ is quite essential to both systems, because the trapdoor for decryption is based on that. As you can see, the relation to RSA is quite close, and thus ...


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