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.


2 Answers 2


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.

  • $\begingroup$ 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])? $\endgroup$
    – Kwyjibo
    Commented Feb 20, 2014 at 8:18
  • $\begingroup$ @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. $\endgroup$
    – DrLecter
    Commented Feb 20, 2014 at 9:23

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);


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.