41

The extended Euclidean algorithm is essentially the Euclidean algorithm (for GCD's) ran backwards. Your goal is to find $d$ such that $ed \equiv 1 \pmod{\varphi{(n)}}$. Recall the EED calculates $x$ and $y$ such that $ax + by = \gcd{(a, b)}$. Now let $a = e$, $b = \varphi{(n)}$, and thus $\gcd{(e, \varphi{(n)})} = 1$ by definition (they need to be coprime ...


21

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


13

$\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

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'...


8

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


7

Notice that the result says 67 mod 257. All calculations here are being done modulo 257. So, $101^{-1}$ is actually the modular inverse of $101 \bmod 257$, which is 28. Similarly, $85 \cdot 28$ is also done modulo 257.


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

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

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

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


6

As for the question "how difficult would it be to solve a random instance of a discrete log problem modulo an RSA modulus", well, it turns out that we can give a fairly solid answer; which is essentially "about as difficult as factoring the modulus". Here's is a demonstration that the discrete log problem is not drastically easier than factoring the modulus"...


6

Well, the reason that a specific cryptographical object needs to work in a specific subgroup probably has to do with the details of that object, and the cryptographical properties it needs from the subgroup. One obvious possibility is that they need to avoid leaking information via the Jacobi symbol; that is an easily computed function that maps values in $...


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

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

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