1
$\begingroup$

Given a prime $P$ with $$P= r \cdot q+1$$ with $q$ prime as well.
I'm looking for a generator $g$ of the Schnorr subgroup with order $q$ which is small by value and has a inverse (to $\bmod P$) which is small as well: $$|\{g^i, \forall i \in [0,P-1]\}| = q$$ $$g^q = 1 \bmod P$$ $$g < m \text{ } \land \text{ } g^{-1}<m$$


To find a Schnorr group generator $g$ in general we can pick a random value $h$ until $$ h^r \not= 1 \bmod P$$ $$\rightarrow \text{ } g = h^r \bmod P$$ To find $g^{-1}$ we can use the Extended Euclidean algorithm or just compute: $$ g^{-1} = g^{q-1} \bmod P$$


Questions:

Q1.) What is the best way to find $g,g^{-1}$ which are each less than value $m$? (edit: found some with step-by-step computation. Main interest now is Q3 (edit-end))
Q2.) How small can $m$ be?
Q3.) Would a small $g,g^{-1}$ have any impact to security?


Trial for Q1: Ways to find small $g, g^{-1}$
a.) pick random $v$ number and project to Schnorr group $v_s = v^r \bmod P$
(all values but $1$ of a Schnorr group are generators)
b.) compute inverse with EEA or with $v_s^{q-1} \bmod P$ (any way faster?)
c.) check if $g, g^{-1} < m$ . If not repeat a.)b.)c.)

Another way than random picks all the time would be an initial random pick for $g$, and a 2nd random value $w$ in this group to start from. Compute the inverse of both as well and traverse through the group with new generator $g^*_j$: $$g_j^* = w \cdot (g)^j \bmod P$$ $${g_j^*}^{-1} = w^{-1} \cdot (g^{-1})^j \bmod P$$ $$w \cdot (g)^j \cdot w^{-1} \cdot (g^{-1})^j = 1 \bmod P$$ and test if $g^*_j$ and its inverse are smaller than $m$.
This computes the values faster but will it be faster in finding suitable generator? Can it be for certain values the results lay in a valley of bad values?


Trial for Q2: How small can $m$ be?
The product of $g, g^{-1}$ need to be at least $p+1$
That means $m \ge \sqrt{p-1}$
Is there another higher border for smallest $m$?

In general the equation need to hold: $$g \cdot g^{-1} = a\cdot P +1 \equiv 1 \bmod P $$ $$a \in [1,P-2]$$

Can the factorization of $(aP+1)$ be used to solve Q1 ($g,g^{-1}$ products of factor(combinations))?
Any way to guarantee its inside the Schnorr group?
Or just check again with $g^q = 1 \bmod P$?

$\endgroup$
  • 1
    $\begingroup$ As for Q2: it's unlikely that you could give significantly larger bounds on $m$; one small example I found was $p=229\cdot 698512 + 1, g = 12645, g^{-1} = 12650, ord(g) = 229$; this example has an $m=12650$ which is not much larger than $\sqrt{p-1} = 12647.4997...$. Obviously, that's much smaller than a cryptographically relevant example, however the existence of such suggests that there are likely to be much larger ones. $\endgroup$ – poncho Feb 3 at 16:37
  • $\begingroup$ @poncho also did some experiments. It tried with a prime ~69 bit. In first trial I didn't found any factor below $2^{59}$. After changing prime and factors a little (about same size) I could find some small generators (54 and 57 bit). Those are not that small as yours but they are sufficient for me. I wrote some program in C which found them quite fast (like my trial Q2 above (part II)). Now my main interest is Q3, If such small generators with small inverse have an impact to security. $\endgroup$ – J. Doe Feb 3 at 17:42
1
$\begingroup$

Q3.) Would a small $g, g^{-1}$ have any impact to security?

It would not appear so. It is easy to show that, if we had a generator $g$ that makes the Discrete Log (or the Computational Diffie-Hellman) problem easy, then the Discrete Log/CDH problem is easy with respect to any base $h$ that's within the same subgroup.

Suppose we had a way that, given $g, g^x$, gave us the value $x$. Then, what we could do, given $h, h^y$ is first find the value $z$ such that $g^z = h$ (by solving the discrete log to the base $g$), and then the value $w$ such that $g^w = h^y$ (again, solving another discrete log to the base $g$); then, we have $h^{wz^{-1}} = h^y$; since we know $w$ and $z$, that tells us the discrete log. Similar (but more complicated) logic allows us to solve the Computational Diffie-Hellman problem, given a CDH oracle with respect to base $g$.

However, this is not a complete answer to the question; it might be that the existence of a small $g, g^{-1}$ makes all discrete log/CDH problems easy.

I don't know of a way this can be disproven. However:

  • None of the known discrete log methods have significant speed-ups when given a small $g, g^{-1}$ (by significant, I mean more than speeding the operation of multiplying by $g$)

  • For just about any prime, there will be tiny $g$ values that generate groups that contain the Schnorr group as a subgroup. If there were a fast way to complete discrete logs with a tiny $g$ in this group, then you could use that to compute discrete logs in the Schnorr group (and although this argument doesn't take into account the tiny $g^{-1}$, there's no obvious way to use that).

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.