We needed to share some data with another company, and this related to Credit card transactions. But we did not want to share the actual card numbers (PANs), what to do. What we came up with is quite neat, and can probably be used by others.
The external company collects the card numbers they want information on, they encrypt these with RSA with a key they generate and do not share. They send these encrypted numbers to us, we further encrypt them with our own RSA key and jumble the order of the entries, then send them back. So now they have a set of PANs double encrypted.
We perform an extract of the relevant transactions and encrypt the PANs with our RSA key, and send these as well. Now the recipients of these can encrypt these with their key and because RSA is a commutative function, can match up the two sets to see if the PANs they sent to us were used in the extracted transactions.
We have added a daily salt to these encryptions so that correlations can’t be used to work out which encrypted PANs map to the original PANs, and we bulk up the transactions so that individual transactions cannot be identified.
A friend of mine wrote up the proof of this:
Let Nv = our Key Modulus
Let E = our Operand (a number greater than 1, which is carefully chosen…)
So our Public Key, Vp = the couplet (Nv, E)
[Ignoring the Private Key as it’s not important…]
Similarly
Let Ng = their Key modulus
F = their operand
So their public key Gp = couplet (Ng, F)
Let X = a PAN
Let Encrypt(K,M) be the RSA encryption algorithm of encrypting message M using key K
To encrypt the PAN using our Public Key: Cv = Encrypt( Vp, X)
This is actually Cv = X^E mod Nv
Then encrypt again using their Public Key: Cvg = Encrypt(Gp, Cv)
This is actually Cvg = Cv^F mod Ng
Similarly, encrypt the PAN using their Public Key: Cg = Encrypt (Gp, X)
This is actually Cg = X^F mod Ng
Then encrypt again using our Public Key: Cgv = Encrypt(Vp, Cg)
This is actually Cgv = Cg^E mod Nv
So Cvg = CvF mod Ng
= (X^E mod Nv)F mod Ng
= X^EF mod Nv mod Ng
= X^FE mod Ng mod Nv
= (X^F mod Ng)^E mod Ny
= Cg^E mod Ny
= Cgv
i.e.
1. it doesn’t matter whether we encrypt with our key first or second, we get the same answer.
2. this means that the RSA algorithm is a commutative encryption algorithm
And so if we produce a value Cvg and they produce value Cgv and the values are the same, we can deduce that both organisations encrypted the same PAN, and nobody is actually sharing any PANs in the process.