Blinding twice in RSA

I understand that if you have a message $m$, you can blind it by selecting a random $r$ and then multiplying $r^e\times m \pmod{n}$ Someone else then signs it with $d$, raising to the power of $d$: $(r^{ed}\times m^d) \bmod n = r \times m^d$. Finally to unblind: $r^{-1}\times r \times m^d = m^d$ and $\left(m^d\right)^e = m$. I understand that.

However, what if I wanted to blind twice? So after the first blind: $r_1^e\times m \pmod{n_1}$.
After the second blind: $r_2^e \times [(r_1^e \times m) \bmod n_1] \bmod n_2$.
Then someone signs it with $d_2$: $\big(r_2^e \times [(r_1^e \times m) \bmod n_1] \bmod n_2\big)^{d_2} = r_2 \times [(r_1^e \times m) \bmod n_1]^{d_2}$.
Then to unblind the first round: $r_2^{-1}\times r_2 \times [(r_1^e \times m) \bmod n_1]^{d_2} = [(r_1^e \times m) \bmod n_1]^{d_2}$.
Next: $[(r_1^e \times m) \bmod n_1]^{d_2e_2} = (r_1^e \times m) \bmod n_1$.
Finally to unblind the second round: $[(r_1^e)^{-1} \times r_1^e \times m] \bmod n_1 = m$

Am I going wrong somewhere in my math? Because I wrote a program to do this and the strangest thing — sometimes it gives me the original message and sometimes it does not. However, it does work perfectly when I comment out either round 1 or round 2. So my program doesn't work for both rounds, but works for a single round. I know this isn't the place to ask for programming help, but I'm thinking my math is off somewhere. Does it have to be the case: $\gcd(r_1, n_1) = \gcd(r_1, n_2) = \gcd(r_2, n_1) = \gcd(r_2, n_2)$ that both values of $r$ cannot have a common factor with both values of $n$? Or did I make a mistake somewhere else?

• Your math is good when $n_1=n_2$; when not, all hells break loose.
– fgrieu
Nov 14 '13 at 8:17
• So you think it will only work when $n_1 = n_2$? Do you see any way with it working if $n_1 != n_2$? In general, it's a bad idea to share moduli, right?
– SJR
Nov 14 '13 at 8:32
• @fgrieu Should'nt it work as long as $n1\leq n2$? As then you can treat $r^{e_1}m\pmod {n_1}$ simply always as an element $a$ of $Z_{n_2}$ and the operations that you perform in $Z_{n_2}$ do not change the element $a$. In the last step you clearly have to make the operation in $Z_{n_1}$, i.e., taking the output of the previous operation and see it as an element of $Z_{n_1}$. As you ensure that $n_1\leq n_2$ this is ok. Apart from that, I do not see what you construction should be used for. Or is it simply "playing around with blinding"? Nov 14 '13 at 8:56
• @DrLecter It's for a digital cash protocol I'm writing for a University project. My thinking is that once the customer turns the money order over to a merchant, the merchant may cheat and try to reveal the customer's identity. If the customer blinds his id strings only he can reveal them after the bank's signature has been verified. Thus, the first blind corresponds to the customer hiding his id strings and the second blind corresponds to the money order being hidden from the bank. I will try your suggestion and enforce $n_1 \le n2$ Thank you.
– SJR
Nov 14 '13 at 9:04
• Thinking about it again, yes than should work when $n_1\le n_2$ as suggested by DrLecter, with two separate unblinding steps using $n_2$ then $n_1$. When cascading signatures, there is a standard trick to make that work with $n_1/2\le n_2\le 2n_1$: replace signature $s_1=m_1^{e_1}\bmod n_1$ with $\hat s_1=\min(s_1,n_1-s_1)$, which is such that $\hat s_1<n_2$, but still allows recovering $m_1$ from $\hat s_1$, as either $\hat s_1^{e_1}\bmod n_1$ or $n_1-(\hat s_1^{e_1}\bmod n_1)$, assuming parity of $m_1$ is fixed; the same can work here.
– fgrieu
Nov 14 '13 at 10:23

As long as you ensure that $n_1\leq n_2$ is guaranteed, the value $r^em\pmod {n_1}$ can be treated as an element in $Z_{n_2}$ and the "outer blinding" and "outer unlinding" in $Z_{n_2}$ does not change this value. Consequently, if you compute the "inner unblinding" in $Z_{n_1}$ after the "outer unblinding" your proposal works.

fgrieu – in his comment – also provided a trick for cascading signatures when working with different RSA moduli. This, however, does not apply to your setting since you are not cascading signatures (maybe you want to do that?)

As CodesinChaos noted in his comment in response to your desired application, your approach still raises some questions.

A simple eCash protocol on blind signatures does not really require you to do that. There, you can assign different values for coins by setting up different signing key pairs for the bank (one for each value) and the coin (value $m$ in your case is simply a random element). If the merchant blacklists the unblinded value and signature pairs, then you can prevent doublespending. Although you will not achieve anonymity revocation in case of this event.

It is not clear for what purpose you want to include customers identites into the coins - maybe you want to have something like anonymity revocation? (why you therefore require another modulus $n_1$ - as well as use blinding without signing this part)? I think there is still potential for discussion.

• Here's the basics of the protocol - it comes from pages 142-3 of Bruce Schneier's "Applied Cryptography." The customer makes $n$ money orders out for a certain amount. Each money order has an amount, uniqueness string, and $n$ pairs of identity strings, where each pair is obtained via secret splitting.*** The customer blinds all $n$ money orders by picking a random $r$, calculating $r_b^e$, and then multiplying each money order. The bank then asks the customer to unblind $n-1$ money orders and then verifies that all amounts are same, all uniqueness strings are different,...
– SJR
Nov 14 '13 at 16:27
• ...and the XOR of both halves of each pair of ID strings reveal the id. If the bank finds that the $n-1$ show no signs of deception, it will sign the final one without unblinding it. The customer unblinds the money order and spends it with a merchant. The merchant gives the customer an $n$ bit challenge where in the $i$ position 0 means reveal the left half and 1 means reveal the right half of $i$. So then the merchant verifies the bank signed the money order and takes the money order. If the uniqueness string is in the db, somebody cheated. If the $n$ bit challenge sequence is the...
– SJR
Nov 14 '13 at 16:33
• ...same, the merchant cheated and the bank has him. If different, the customer cheated because the probability of two different merchants using the same $n$ bit challenge is astronomically low. The bank looks at its db, finds the old n-bit challenge, sees where they differ, XORs the two halves together, and exposes the customer. ***My observation. When the money order is unblinded after signed by the bank, the id strings are in plain view. After the merchant takes possession of the money order, he could XOR any pair to destroy anonymity. That's why I think it's a good idea...
– SJR
Nov 14 '13 at 16:38
• ...for the customer to blind his/her identity so if the merchant were to attempt to XOR the identity strings, he would get garbage and anonymity is preserved. As for two different $n$s, generally it is a bad idea to have duplicate moduli when dealing with RSA because it makes cryptanalysis easier. <fin>
– SJR
Nov 14 '13 at 16:42
• After considering everybody's input, I've rethought my approach. I can blind twice, but I can do it with one $n$ value since all I really need to blind is a value of $r$, not an entire new set of keys. The merchant will not be able to expose the customer's id without the customer's r value. Thanks again.
– SJR
Nov 14 '13 at 23:05