Score:0

Crypto

Solving a discrete log with BsGs

arsenne lupulupin

2/25/23, 2:45 PM

If we consider a group G with modulus p, order q with $p=2*q+1$, and generator $g=2$ ($ p$, $q$ huge prime numbers), is there a way to solve the discrete log problem $ g^x = y $ for a y given, using the baby steps giant step algorithm AND the fact that $x$ is of the form: $ x = \sum_{i=0}^{10} \alpha_i * 2^i $ $:\alpha_i \in \mathbb{N} $ without requiring to store all small steps in a hashtable, which is impossible with the magnitude of the numbers $p$ and $q$.

edit: The $ \alpha_i $ values are unknown to the attacker.

edit 2: $\alpha_i \in [0,\infty] $

0 + 0

discrete-logarithm

poncho

2/25/23, 3:10 PM

Does the attacker know the $\alpha_i$ values?

kelalaka

2/25/23, 9:50 PM

Does actually $\alpha_i \in \{0,1\}$? Does $\mathbb{N} = \mathbb{Z}^+$ or $\mathbb{N} = \mathbb{Z}^+ \cup \{0\}$, there is no common agreement on this.

Score:0

Crypto

poncho

2/25/23, 3:22 PM

is there a way to solve the discrete log problem $g^x=y$ for a $y$ given, using the baby steps giant step algorithm

No practical way if $p, q$ are large.

Even if $x$ is known to be in the form $ x = \sum_{i=0}^{10} \alpha_i * 2^i $ $:\alpha_i \in \mathbb{N} $ ?

Every potential $x$ can be expressed in that form; consider $\alpha_1 = \alpha_2 = ... = \alpha_{10} = 0$ and $\alpha_{0} = x$. Hence, knowing that $x$ is expressable in that form does not provide any additional information; BsGs is usable only if the modulus is small enough (and the question assumes it is not)

0 + 0

Ievgeni

2/25/23, 4:04 PM

No $x< 2048$. The problem is much easier, you can do Bruteforce attack (but without babystep/giant step).

poncho

2/25/23, 4:36 PM

@levgeni: if we're talking about values that **can** be expressed in that form, we have $x \ge 2047$ (and that's with the convention that $0 \not\in \mathbb{N}$; otherwise, all $x$ values can be expressed in that form).

poncho

2/25/23, 4:38 PM

@levgeni: and, if $x < 2048$ and $p$ is cryptographically sized (i.e. at least 2048 bits), the discrete log can be extracted directly from the value $2^x$; that has bit $x$ as 1, and all the other bits as 0...

kelalaka

2/25/23, 8:40 PM

@poncho I think levgeni argues that even if $x>2046$, it doesn't imply that $x$ is not trivially small. The large is clear, however the small need a metric.

poncho

2/25/23, 9:33 PM

@kelalaka: I don't understand your argument; if we interpret the question of "is DLog solvable if we assume the exponent is random, conditioned by being expressable in the given form?" With that understanding, my answer is correct - how do you interpret the question?

kelalaka

2/25/23, 9:54 PM

@poncho if $x$ is small ( no metric here ) but we know the bound, then BsGs can be parametrized to solve faster, right? And again, if $x$ is small then actually we don't need BsGs, we can brute-force it like we can brute-force from 1 to $2^{48}$ for possible $x$'. Or, are you implicitly assuming $x$ uniform random?

Ievgeni

2/26/23, 12:26 PM

@poncho Ok, I thought the $\alpha$'s were bits. I'm a little bit lost with all the edits. I still do not understand why you spoke about $2046$. I would like to delete my $-1$, but I can only if you edit your message.

poncho

2/26/23, 12:39 PM

@levgeni: if $0 \not\in \mathbb{N}$, then the minimum $\sum_1^{10} 2^i\alpha_i$ can be is 2046. Some definitions of $\mathbb{N}$ do not include 0, others do.

Ievgeni

2/26/23, 12:57 PM

But the sum in the question begins to zero, so it should be $2047$?

poncho

2/26/23, 1:00 PM

@levgeni: I'm using $\alpha_0$ as the value that changes, and so we effectively have $x = \alpha_0 + 2046$ - $\alpha_0 = 0$ is not allowed, so we have $x > 2046$

Ievgeni

2/26/23, 6:35 PM

@Ievgeni : Okay, Thx for the explanation. I understood. But it seems that finally the $alpha$'s can be equal to zero.

Elon Musk

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

EN: Solving a discrete log with BsGs

TH: การแก้ไขบันทึกแยกด้วย BsGs

RO: Rezolvarea unui jurnal discret cu BsGs

RU: Решение дискретного журнала с помощью BsG

VI: Giải quyết một bản ghi rời rạc với BsGs

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.