Score:0

Crypto

Is the base equally well protected by the discrete logarithm problem as the exponent?

Balazs F

4/2/23, 6:55 AM

I'd like to ask if in case of modular exponentiation, reverse engineering the base would be equally difficult, when knowing the exponent as determining the exponent is hard when the base is provided? The modulus should be considered to be safe and the same in both cases.

In equations:

secret  ^ public1 mod public_prime = public2a
public1 ^ secret  mod public_prime = public2b

Is the secret equally well protected in both cases?

0 + 0

discrete-logarithm

Daniel S

4/2/23, 7:02 AM

HINT: Why does RSA not just use prime moduli? Can you invert $x\mapsto x^3\bmod p$?

Balazs F

4/2/23, 10:21 AM

Okay, so RSA uses the base as the secret message, thus it must be protected well... Right?

Score:-1

Crypto

Balazs F

4/2/23, 10:25 AM

secret  ^ public1 mod public_prime = public2a // this is the case of RSA
public1 ^ secret  mod public_prime = public2b // this is used in Diffie-Hellman

EDIT: The RSA style version is only safe if a multiple of two large secret primes are used, because otherwise Fermat's little theorem can be used to reverse engineer the base. In case of the Diffie-Hellman version safe primes are required, whose Euler totient (prime-1 in this case) has to be a product of 2 and another large prime, in order to be sure that sufficiently large groups are being generated if raising the base to the same power multiple times.

0 + 0

kodlu

4/2/23, 11:51 AM

how do you conclude they're equally protected from what you wrote?

fgrieu

4/2/23, 11:53 AM

Hint: In RSA, the public modulus is a composite of unknown factorization.

Balazs F

4/2/23, 12:30 PM

By their respective safety conditions I meant, like a safe prime in case of DH of size N bits, or the product of two primes of sizes N. Don't both require average 2^(N -1) brute force steps in a most primitive cracking scenarios (not considering advanced cracking methods)? So I got to that conclusion by in DH it is the exponent that is kept secret, while in RSA it is the base that holds the secret, while both are based on the irreversibility of the discrete logarithm.

Balazs F

4/2/23, 12:56 PM

Ah, I got it... The Fermat theorem provides the modexp's inverse, if a single prime is used instead of a product, whose multiplicads were kept secret! This is for the case when the exponent would be public.

fgrieu

4/2/23, 1:15 PM

Yes. Now it's best to [edit your answer](https://crypto.stackexchange.com/posts/96412/edit), which might allow some of the negative votes to be reversed (that's impossible otherwise).

fgrieu

4/2/23, 4:58 PM

The stated conditions on `public_prime`$=p$ and $p-1$ for the DH case are common, and sufficient for security (as far as conditions on $p$ go). However it's not necessary, thus "… _has to be_ a product of 2 and another large prime" is technically incorrect. [Dr. Spock](https://en.wikipedia.org/wiki/Spock) suggests _can be_ . As far as we know, it's sufficient that $p$ is a huge haphazard prime (like 3072-bit) with $p-1$ having a large prime factor $q$ (like 256-bit), and `public1`$=g$ is such that $g^q\equiv1\pmod p$ and $g\not\equiv1\pmod p$.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Is the base equally well protected by the discrete logarithm problem as the exponent?

TH: ฐานได้รับการปกป้องอย่างดีพอ ๆ กันโดยปัญหาลอการิทึมแยกเป็นเลขชี้กำลังหรือไม่

RO: Este baza la fel de bine protejată de problema logaritmului discret ca și exponentul?

RU: Основание так же хорошо защищено задачей дискретного логарифмирования, как показатель степени?

VI: Cơ số có được bảo vệ tốt như nhau bởi bài toán logarit rời rạc như số mũ không?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.