4

Could we fix this by choosing an element $g$ that generates a large subgroup (of $\Bbb Z_p^*\ $), all of whose elements are quadratic residues? Concretely, we could take $p=2q+1$ for a large prime $p$ and then find an element which generates the order $q$ subgroup.Now, if Diffie–Hellman is done with this group element, any eavesdropper knows the lowest order ...


3

The straight-forward method you outlined doesn't work, because $G^a$ is not monotonic in $a$; we can have $G^{r_a} < G^a$ even though $r_a > a$. This happens because we're working modulo $n$, rather than doing exponentiation in the real numbers or integers. For example, if we have $n=101$ and $G=2$ (for a toy example), then we have: $$G^8 = 54 > ...


2

For x25519, can multiple PK's resolve to a single SK, or is there ever only one unique PK-SK pair? If I wasn't mistaken, there can be atmost 2 PK corresponding to 1 SK in x25519, depending on whether the implicit y-coordinate is internally positive or negative. As for ECDH on the other hand, the mapping is 1:1. I'm wondering whether it's rational to ...


2

It's multiplication of 2^894 and pi. (2^1024 - 2^960 - 1 + 2^64 * ( (2^894 * pi) + 129093)) Wolfram Alpha


2

In cryptography, strong primes have been used (with various definitions of that) for RSA, in order to defeat the factorization of the public modulus by Pollard's p-1 and p+1 algorithms, and various other attacks. For this reason, there is no list of standard large strong primes, for that would defeat the purpose in RSA, where the prime factors of the public ...


1

A reduction here would mean showing that if you had an efficient algorithm A to solve the discrete logarithm problem, then you could use that to construct an efficient algorithm B solving the computational Diffie-Hellman problem. (For starters, assume A always works and construct B that always works. For full credit, given A that works with some probability [...


1

So, why do the NIST/TLS standards not allow for cofactors greater than 2? Actually, NIST does allow larger cofactors - see table 1 in SP800-56A - they allow the subgroup (q) to be significantly smaller than the modulus (p). As for TLS, previous versions of TLS (1.2 and earlier) did allow the server to specify the group (and made no requirements about the ...


1

TL;DR: $a$ and $b$. For DHE in the multiplicative group modulo $p$, it is agreed on a large prime $p$ and an element $g$. This is typically long term, and there are standard public parameters, e.g. the 3072-bit MODP group of RFC 3526 After this, each time two parties A and B want a shared secret party A draws a random $a$ and sends $h_A = g^a\bmod p$ ...


1

What exactly do you doubt about the CDH or DDH problems? Is it possible to send a message to someone using only the Diffie–Hellman key exchange? You cannot "send" a message using DHKE but you may use its resulting shared secret as a one-time-pad (by multiplication; not XOR) to "encrypt" a message encoded as a group element. When the sender uses a unique ...


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