2

Zq* is a cyclic group generated by g order q. In other words, there exists g in Zq* such that Zq* = {1, g, gˆ2, gˆ3, . . . , gˆ(q-2)} mod q = {1,2,3,...,(q-1)} mod q. Such a "g" is called a generator of Z.

Example: in Z7* is generated by g=3, because: {1,3,32,33,34,35,36} mod7 = {1,3,2,6,4,5} (mod 7) = Z7*.

Trying to calculate some numbers here:

let:

g = 3;
u = 5;
x = 4;
c = 6;
q = 7;

So, in Z7*, with g=3 being its generator, we have:

g^u mod q = 3^5 mod 7 = 243 mod 7 = 5 mod 7 = K

Another thing:

g^(u-x*c) * g^(x*c) mod q = g^u mod q = 5 mod 7

but if you don't cancel the g^(x*c) member, you stay with:

g^(u-x*c) = 3^(5 - 4 * 6) mod 7 = 3 ^ (-19) mod 7 = 3 ^ 2 mod 7 = 9 mod 7 = 2 mod 7 = a

and, the second member is:

g^(x*c) = 3^(4 * 6) mod 7 = 3 ^ (24) mod 7 = 3 ^ 3 mod 7 = 9 mod 7 = 2 mod 7 = b

So, a * b = :

a * b = 2 * 2 mod 7 = 4 mod 7

which is different from k calculated.

How it's supposed to calculate numbers on a cyclic group?

janmarqz
  • 10,538
Cesar11031
  • 21
  • 2
    "3 ^ (-19) mod 7 = 3 ^ 2 mod 7" looks wrong to me, you don't reduce the indices mod 7, you reduce them mod 6 since the multipicative order of 3 is 6. – ancient mathematician Mar 07 '21 at 15:16
  • Man, you don't know how you helped me, I was trying to implement Linkable Ring Signatures from https://link.springer.com/chapter/10.1007/978-3-540-27800-9_28 and on page 6 , item 4.1.4 there's an error, where is said: "Compute sπ =u−xπcπ modq." it must say "4. Compute sπ =u−xπ*cπ mod(q-1)." because sπ will be an index of a variable. Anyway, now my code works perfectly. I don't have a religion but must say God bless you =) – Cesar11031 Mar 07 '21 at 15:57

0 Answers0