1
$\begingroup$

I need to create program that makes signature for selected file. I simplified algorithm a little, because I draw max 64 bit prime numbers instead of 512 bit - like its recommended in Applied Cryptography book.

I have already drew private key which is for example: $1848661337$, and now I need to calculate public key. I need to choose an $a \not = 1$, such that $a^q = 1 \bmod p$, where $q$ and $p$ are prime numbers. I have tried a lot of examples and it seems that the second part of this expression always is going to be $1$? If it is true, $a$ must be $1$?

I thought in the book is mistake but, I found other resources that confirm version from book.

I cant handle it. What should I do to solve this problem?

Numbers from trial:

  • $a^{1034069683} = 1 \bmod 3465190093$
  • $a^{45900161} = 1 \bmod 95899459$
  • $a^{200001283} = 1 \bmod 490810459$
  • $a^{390810929} = 1 \bmod 890811619$
$\endgroup$
  • $\begingroup$ @kelalaka Done. As You can see, 1 mod x is always 1. $\endgroup$ – KonradDos Jan 20 at 21:31
  • $\begingroup$ Hint: for 1) the mod prime, power is prime and gcd(power,mod−1)=1, then $a$ must be? $\endgroup$ – kelalaka Jan 20 at 22:50
  • $\begingroup$ Hint: what you want is parameters for a Schnorr group. You need to choose $p$ and $q$ together, since $q$ must divide $p-1$. $\endgroup$ – fgrieu Jan 21 at 9:07
  • $\begingroup$ Ok, so I tried to calculate the group generator. I followed the steps from source: p = qr + 1 917794499 = 917794489*r + 1 p/q - 1/q = r 917794499/917794489 - 1/917794489 = r r = 1.00000000981 h is any number gt then 1, so lets say its 2 in this example g = h^r mod p g = 2^1.00000000981 mod 917794499 g = 2.0000000136 $\endgroup$ – KonradDos Jan 21 at 22:54
  • $\begingroup$ @kelalaka Next hint please :/ $\endgroup$ – KonradDos Jan 21 at 23:03

Your Answer

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

Browse other questions tagged or ask your own question.