Commutative encryption allows us to decrypt in any order. For this we can use SRA (Shamir, Rivest and Aldeman) and generate encryption keys which share p, q and N. The following uses two keys (e1, d1) and (e2, d2) with a shared N value:
Commutative encryption (SRA) |
Method
With maths, operators such as multiplication are commutative, such as:
3 x 5 x 4 = 4 x 5 x 3
In encryption, most operations are non-commutative, so we need to modify the methods. One way is to use RSA, but generate two keys which have shared p, q and N values. So we generate Bob and Alice's keys using the same two prime numbers (p and q), so that they share the same N value (modulus).
So let's start with Bob:
Let’s select: P=7, Q=13
The calculation of n and PHI is:
N = 7 x 13 = 91 PHI = (P-1)(Q-1) = 72
We need to make sure that our encryption key (e) does not share any factors with PHI (gcd(PHI,e)=1). We can select e as:
e = 5
Next we can calculate d from:
(d x 5) mod (72) = 1
The answer is 29 [Solve]
d= 29, e=5, N=91 Encryption key [91,5] Decryption key [91,29]
Now for Alice. We have:
N = 7 x 13 = 91 PHI = (P-1)(Q-1) = 72
We can select e as (and should not share any factors with PHI):
e = 7
Now we must solve:
(7 x d) mod (72) = 1
For this we get 31 [Solve]
Alice's keys are then:
d= 31, e=7, N=91 Encryption key [91,7] Decryption key [91,31]
Example
The following is a run with a message of "5":
e1 = 5 d1= 29 e2 = 7 d2= 31 N = 91 Message = 5 =================== Cipher result (after Alice encrypt): 31 Cipher result (after Bob encrypt): 73 =================== Cipher result (After Bob decrypt) 31 Cipher result (After Alice decrypt) 5 A -> B -> B -> A: 5 Cipher result (After Alice decrypt) 47 Cipher result (After Bob decrypt) 5 A -> B -> A -> B: 5
Code
An outline of the code used is:
import sys e1=5 d1=29 e2=7 d2=31 N=91 message=5 print("e1 = ",e1," d1= ",d1) print("e2 = ",e2," d2= ",d2) print("N = ",N) print("Message = ",message) print("===================") AliceCipher = (message)**e1 %N print(' Cipher result (after Alice encrypt): ',AliceCipher) BobCipher = (AliceCipher)**e2 %N print(' Cipher result (after Bob encrypt): ',BobCipher) print("===================") Decipher1= (BobCipher)**d2 %N print(' Cipher result (After Bob decrypt)',Decipher1) Decipher2= (Decipher1)**d1 %N print(' Cipher result (After Alice decrypt)',Decipher2) print('A -> B -> B -> A:', str(Decipher2)) Decipher1= (BobCipher)**d1 %N print(' Cipher result (After Alice decrypt)',Decipher1) Decipher2= (Decipher1)**d2 %N print(' Cipher result (After Bob decrypt)',Decipher2) print('A -> B -> A -> B:', str(Decipher2))
Article
An article on this is [here]