A neat data sharing technique

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.