# Shamir's ID based signatures - Notation issues

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

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.

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