1

I am currently implementing Shamir's ID Based signature scheme as defined in the original paper (archive link). The sign and verify operation are defined as follows:

Sign: $s = g * r^{f(t,m)} (\mod n)$

Verification: $s^e = i * t^{f(t, m)} (\mod n)$

I have some troubles to convert this to Java code, because I am unsure about the order of evaluation, i.e., I am unsure, what the modulus refers to in this context, the hole right hand side (including the multiplication) or the exponentiation operation, only?

PS: This post is related to this question.

Community
  • 1
Kwyjibo
  • 33
  • 4

2 Answers2

1

Ok, lets look at the operations.

Sign: $s = g * r^{f(t,m)} \pmod n$

This is an assignment. You compute $(g * r^{f(t,m)}) \mod n$ and assign the resulting value to $s$. If you have a multiplication $(a \cdot b) \mod n$, this is equal to $((a \mod n)\cdot (b \mod n)) \mod n$. See for instance here.

Verification: $s^e = i * t^{f(t, m)} \pmod n$

This is no check for equality, but a check for congruence.

You can implement this by computing $s^e \mod n$ as well as $(i * t^{f(t, m)}) \mod n$ and check if these values are equal.

fgrieu has recently written an answer to a recent question on congruences which clarifies this nicely.

Community
  • 1
DrLecter
  • 12,547
  • 3
  • 43
  • 61
  • Thank you for your answer. Does (mod n) relate to the whole right hand side (i.e., [g*r^f(t,m)] mod n), or to the exponentiation, only (i.e., g * [r^f(t,m) mod n])? – Kwyjibo Feb 20 '14 at 08:18
  • @Kwyijbo you can see this from my answer (below the sign operation). This applies always to the entire side. If you have a multiplication modulo $n$ then you can reduce any of the operands modulo $n$ and then the result modulo $n$. You may also read this for a description of modular exponentiation. I would strongly suggest to read up on modular arithmetic before implementing anything. If you implement this scheme in Java, BigInteger already provides all these methods. – DrLecter Feb 20 '14 at 09:23
0

I haven't seen the Shamir ID-based signature algorithm, but I think you want to use .powMod(exponent, modulus), and not, for performance and/or OutOfMemory reasons, .pow(exponent).mod(modulus). E.g. for forming the signature
BigInteger g=???;
BigInteger r=???;
BigInteger ftm=???;
BigInteger n=???;
BigInteger s=r.powMod(ftm, n).multiply(g).mod(n);

Brock Hansen
  • 301
  • 1
  • 4