discrete logarithm and calculating with modulo

477 Views Asked by At

I have the following scenario:

Let $p' = 3, q' = 5, p = 7, q = 11, n=pq = 77$.

Then $\mathbb{Z}_{77}^* = \{a \in \mathbb{N} \ \big\vert\ 1\leq a \leq 77, gcd(a, 77) = 1\}$.

Furthermore $QR_{77} = \{a \in \mathbb{Z}_{77}^* \ \big\vert\ \exists b \in \mathbb{Z}_{77}^* : b^2 \equiv a \mod n \}$

Obviously $16 = h \in QR_{77}$.

$\langle h\rangle = \{16^i \mod 77 \ \big\vert\ i\in \mathbb {N}\},\ |\langle h \rangle| = 15.$

Then for $g = 4$ holds that $g \in \langle h\rangle$, because $16^8 \mod 77 = 4$.

With the discrete logarithm you should be able to recalcualte the exponent ($8$) from $16, 4$ and $77$.

But actually $\log_{16} 4 = \frac{1}{2}, $ because of course $\sqrt{16} = 16^{\frac{1}{2}} = 4$.

So I guess in this case the discrete logarithm cannot be understood as the normal way logarithm is calculated? It is more about to find the smallest, natural number $i \in \mathbb{N}$ such that $a^i \mod n = b$ for some given $a,b,n \in \mathbb{N}$, right?

And that is why it is not so easy to calculate (especially for bigger numbers then the ones I used here) and is a good proof to certificate that whoever provided a public key $(g,h)$ (for which holds) $g \in \langle h \rangle$ really is the one who generated the key (and therefore is the real owner of the key)?

I find it always a bit confusing on what the modulo depends. Sometimes it is written on the right side of an equation, but is meant to be applied to the left side. Sometimes (the discrete logarithm) it doesn't really depend on the logarithm. Why is there no uniform notation?

1

There are 1 best solutions below

0
On

logarithms have in common with discrete logarithms, that they are the minimum exponent where something occurs. in the case of 16,4,77 I would do the following (yes I know more efficient ways for low values likely exist):

  • Mod 2 we have $2y=(2x+1)z+2a$ meaning we need an even multiplier for 77.

  • Mod 3 we have $3b+1=(3c+2)d+(3e+1)$ meaning the multiplier on 77 is 0 mod 3.

  • Mod 5 we have $5f+1=(5j+2)k+(5l+4)$ meaning the multiplier on 77 is 1 mod 5

  • Mod 7 we have $(7m+2)^i=(7n)r+(7s+4)$ which implies i is 2 mod 3, by order of 1 mod 7

So far, this gives us a multiplier of 77 that is 6 mod 30, and a log that is 2 mod 3.

First attempt, $6(77)=462; 7(77)= 539$ no power of 16 in there so we know the next range possibility is 2310 away up at 2772 to 2849. Clearly, our exponent help is needed, we've passed i=2, next is i=5 then i=8. which in this case would be our solution.

You can use other tricks, but this is how I might approach it if everything else was unknown.

EDIT: mod 11 shows the order is 3 mod 5, by order of 1 mod 11. this forces i=8 as a first check. A jump of 15 by CRT. And yes, mod 4 would have pushed it to 36 mod 60 for the multiplier.