Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question

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.

share|improve this answer
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 8: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 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);

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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