7
$\begingroup$

To get some certain properties for my use case I need a prime $P$ which has the form:

$P=2\cdot Q \cdot R \cdot S \cdot t+1$ with $Q,R,S,t$ primes as well.


Why that form - Use case

Together with this three factors $q,r,s$ are used. The values $v$ of interest have the form
$v(a,b,c) = q^ar^bs^c\bmod P$,

Those factors have the following properties:
$q^Q \equiv 1 \bmod P$
$r^R \equiv 1 \bmod P$
$s^S \equiv 1 \bmod P$

and the equation holds:
$q^{a+dQ}r^{b+eR}s^{c+fS} \equiv q^{a}r^{b}s^{c} \bmod P$, with any $d,e,f \in \mathbb{N}$

so

$|\{v(a,b,c), \forall a,b,c \in \mathbb{N}\}| = QRS = \frac{P-1}{2t}$

If another factor is added:

$v(a,b,c,T) = q^ar^bs^c T\bmod P$, with any $T\in\mathbb{N} < P$

you can achive:

$|\{v(a,b,c,T), \forall a,b,c,T <P \in \mathbb{N}\}| = P-1$
Two different $T$ have $0$ or all values equal.

That those properties work the prime $P$ need to have the form:

$P=2QRSt+1$

(constructed myself, there might be better options)

It also works with $t=1, T=1$. With this half of all values ($(P-1)/2$) can get generated.


How safe is such a prime?

A user and also possible attacker has access to the source code and all runtime variables. For a given $v$, which is not computed at the local PC (its just a random number) the attacker should not be able to determine the values $a,b,c$ and $T$ in:

$v(a,b,c,T) \equiv q^ar^bs^c T\bmod P$

or to be more exact, he should not be able to derive one $v'$ out of another $v$

$v'(a',b',c',T') \equiv v \cdot q^{a'}r^{b'}s^{c'} T'\bmod P$

The attacker knows all other values $P,Q,R,S,q,r,s,t$

$Q,R,S$ need to be about the same size, $t$ is much smaller $t\ll Q,R,S$, in use case less than $t<1000$;

I read about safe and strong primes. Both don't hold for that kind of prime form. How much safety get lost with that form? Would it help if

$Q,R,S$ are safe/strong primes

if $P+1$ has a large prime factor

You know about other enhancements?


Comparison to normal discrete logarithm

The form above is different to the normal discrete logarithm problem form like:

$v'\equiv g^x \bmod P'$ and finding $x$ for a given $v'$

I'm not familiar with all discrete log. solving algorithms. Does it make a difference if there is only one base ($g$) or three of it ($q,r,s$)? Three harder or faster solving?

Assuming $S$ is a safe prime and largest out of $Q,R,S,t$. Could you compare the mean solving time complexity of

finding $a,b,c,T$ for a given v solving:

$v \equiv q^ar^bs^c T\bmod P$

with finding d for a given $v'$

$v'\equiv g^d \bmod S$, with g prime root of $S$

Or is it harder/faster? How would a normal form look like which has about the same solving time (to get an idea how much worse my form is)?


(toy) example

$P=35531=2 \cdot 7 \cdot 11 \cdot 19 \cdot 5+1$
$r=4999, q=21433, s=3181$

$\endgroup$
  • $\begingroup$ I should point out that Pohlig-Hellman causes you some trouble. I think that if you choose $ Q, R, S $ large enough, you may get out of cryptographic problems, but you don't gain any security over storing info as separate discrete logarithms (unless your use case really requires that). $\endgroup$ – theREALyumdub May 4 at 15:35
  • $\begingroup$ Thanks for response. The use case need three of it with about equal size. What would be large enough $Q,R,S$? Assuming a prime $U$ would be large enough for a single disc. problem: $g^a \mod U$. How large $Q,R,S$ need to be to get same security? $Q,R,S$ need to be as large as $U$? As large as $U^2$? As large as $U^3$? As large as $\sqrt[2]U$? As large as $\sqrt[3]U$?As large as $\sqrt[4]U$? $\endgroup$ – J. Doe May 4 at 19:31
  • $\begingroup$ It was more of a guess than an answer, if I knew the answer to what you were asking I probably would have posted below! But you may want to see the Silver-Pohlig-Hellman algorithm if that helps at all, over here on this site: crypto.stackexchange.com/questions/10380/…. My guess is Q, R, and S need to be about the same size as U, but I'm not sure you haven't introduced something fatal also. $\endgroup$ – theREALyumdub May 4 at 23:04
2
$\begingroup$

It does work with Silver-Pohlig-Hellman algorithm

As theREALyumdub pointed out in comments that Silver-Pohlig-Hellman might be an option I did some test and it did work. Thanks for that hint.

In case $t=1$ we get the results $a,b,c$ right out of the algorithm. For other $t$ the results $a,b,c$ aren't correct. Some extra work need to be done there. It does work if you multiply value $v$ with the inverse of used $T$ first. However this $T$ is unknown in use case. Chances are high there is a better way but the naive way is good enough for my case. As I wrote in post $t<1000$ so we could just multiply with a random number and get the correct result with chance $\frac{1}{t}$.

So it is not harder than: finding d for a given $v'$

$v'\equiv g^d \bmod P$, with $g$ generator of a subgroup with size $G=\max(Q,R,S)$

Remaining questions:

Does it make a difference if you solving only for a subgroup? Or is equation above, as hard as
$v'\equiv g^d \bmod G$

Is there any way to speed up finding the correct $T$ factor? While a constant factor of 1000 is asymptotically equal but in real world it can make a huge difference.

However this transition used in Silver-Pohlig-Hellman algorithm destroys the idea of hiding the dimensions in one number. Three separate equations with big prime factors would do the same job.

Although the question is not fully answered it's enough for me. The remaining questions above are not specific to this case. I might create some new threads about those. If so, I will link them here.

$v = T\cdot g^a\mod P$
proof if same factor $T$ was used --> $v_{T_1}^{QRS} \equiv v_{T_2}^{QRS} \mod P$ iff same group

links show easy to do -> this kind of prime and usage has not benefits :(

$\endgroup$
  • 1
    $\begingroup$ Good job on answering your own question! But please remember that stackexchange is a question and answer site, rather than a forum. Replies to questions are required to be an answer to the question, and including more questions in an answer is not how our site works. You can ask a new question and point back to this Q/A as context for the new question(s). $\endgroup$ – Ella Rose May 5 at 20:09
  • $\begingroup$ It's only a partly answer. Only an upper border. Did some edit. $\endgroup$ – J. Doe May 5 at 21:33

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.