# How to generate $k$ random numbers that add upto a number $d$ and are coprime with respect to $p-1$

This is something that is needed while generating additive shares ($$D_i$$) for decryption key (represented by $$d$$) where each additive share must be coprime with respect to $$p-1$$ i.e $$\gcd(D_i , p-1) = 1$$

• The decryption key of the RSA consists of a (public) modulus and a (secret) exponent. The modulus is often called $m$ or $n$, the secret exponent is often called $d$. The modulus is a product of two primes, often called $p$ and $q$. What is your $n$? The modulus or the exponent? I ask, as I've seen in the context of RSA the requirement to be coprime to the modulus $m$ and the requirement to be coprime to $\phi(m) = (p-1)\cdot(q-1)$, but I haven't seen the need to be coprime to either the modulus minus one or the secret exponent minus one. – j.p. Jan 29 '19 at 7:35
• This is slightly different approach from the normal RSA setting. Threshold and proactive RSA implementation requires the decryption key ,d to be divided into k additive shares(di) and those additive shares must be co-prime to p-1( large prime used in RSA setting). This is needed because we need to find the inverse of di mod p. – Zaid Bhat Jan 29 '19 at 9:13
• If you just want to generate $k$ shares of $d$, why not just sample $d$ first, then choose $k-1$ random integers $d_1,\ldots,d_{k-1}$ that are coprime to $p-1$, and then let $d_k$ be $d - \sum_{i=1}^{k-1}d_i$ (perhaps with some modulus, I guess $\phi(n)$? If $d_k$ is coprime to $p-1$ then you're fine, and otherwise you try again. I don't think this is going to fail many times. – Daniel Jan 29 '19 at 9:33
• I still wonder why you need to invert the shares $D_i$ modulo $p-1$ (in your last comment you write $p$ instead of $p-1$ at the end and in your question you write "with respect to $d-1$" instead, but I now go with the assumption that you mean $p-1$). Knowing $d_i$ and the corresponding inverse modulo $p-1$ (or modulo $(p-1)(q-1)$) allows to factor the modulus, which breaks RSA. So normally you do not want to give someone both except maybe for preventing differential fault attacks. Instead of inverting each $d_i$ one could in many scenarios simply share also the public exponent additively. – j.p. Jan 29 '19 at 12:26
• @j.p. , this is an implementation of slightly modified form of RSA where we need to verify the additive shares before we can actually add the various additive shares to form the decryption key back. The verification of additive shares has a partial signature and a witness signature and during the verification we need the inverses of di’s – Zaid Bhat Jan 30 '19 at 5:39

My guess is that the actual requirement is: given

• RSA modulus $$n$$ (odd and square-free)
• $$\lambda(n)$$ per Carmichael's function
Note: $$\lambda(n)=\dfrac{(p-1)(q-1)}{\gcd(p-1,q-1)}$$ if $$n$$ is the product of distinct primes $$p$$, $$q$$
• an RSA private exponent $$d$$, thus with $$\gcd(d,\lambda(n))=1$$
• moderate $$k>1$$

draw $$k$$ positive integers $$d_i$$ less than $$\lambda(n)$$ at random except they are such that

1. $$\gcd(d_i,\lambda(n))=1$$ for all $$i$$
2. $$x^d\bmod n\ =\ \left(\displaystyle\prod_{i=0}^{k-1}x^{d_i}\bmod n\right)\bmod n$$ holds for all $$x$$

The condition 1 is equivalent to $$\gcd(d_i,p-1)=1$$ of the question applied to all primes $$p$$ dividing $$n$$. It insures that $$x\mapsto x^{d_i}\bmod n$$ is a bijection of $$[0,n)$$, which possibly is desirable in the context of 2.

The question requires $$d=\displaystyle\sum_{i=0}^{k-1}d_i$$. That's not necessary for 2 to hold. We'll relax that requirement to $$d\equiv\displaystyle\sum_{i=0}^{k-1}d_i\pmod{\lambda(n)}$$, which is equivalent to 2, gives more choices for the $$d_i$$, makes the selection simpler.

Update: no matter what, we still must restrict to odd $$k$$: since $$\lambda(n)$$ is even, $$d$$ and all $$d_i$$ must be odd.

The limit $$\lambda(n)$$ for the $$d_i$$ is usual in modern expositions of RSA. It is pointless to choose a larger upper limit, for RSA exponents are equivalent modulo $$\lambda(n)$$.

Following closely the approach suggested in Daniel's comment, we can

1. for $$i$$ from $$1$$ to $$k-1$$
• pick $$r$$ random in $$[0,\lambda(n)/2-1]$$ and set $$d_i\gets2r+1$$ until $$\gcd(d_i,\lambda(n))=1$$
2. compute $$d_0=\left(d-\displaystyle\sum_{i=1}^{k-1}d_i\right)\bmod\lambda(n)$$
3. if $$\gcd(d_0,\lambda(n))\ne 1$$
• pick a random $$i$$ in $$[1, k-1]$$
• pick $$r$$ random in $$[0,\lambda(n)/2-1]$$ and set $$d_i\gets2r+1$$ until $$\gcd(d_i,\lambda(n))=1$$
• proceed at 2

Note: if we fixed $$i=1$$ in step 3, we'd end up with a slightly biased, but probably tolerable choice.

A comment states

we need to find the inverse of $$d_i\bmod p$$

Perhaps that really means computing $$e_i={d_i}^{-1}\bmod\lambda(n)$$, which allows to verify $$y_i=x^{d_i}\bmod n$$ because for all $$x$$ in $$[0,n)$$ that's equivalent to $$x={y_i}^{e_i}\bmod n$$.

Beware however that we can't distribute public-key encryption in this way, for knowledge of $$n$$, $$e_0$$, $$e_1$$, $$x^{e_0}\bmod n$$ and $$x^{e_1}\bmod n$$ allows recovery of $$x\bmod n$$ when $$\gcd(e_0,e_1)=1$$, which is not unlikely.