I'm trying to modify an example Diffie-Hellman key exchange between three parties.
Here is the Code.
// Alice uses Carol's public key
Key ac = aliceKeyAgree.doPhase(carolKpair.getPublic(), false);
// Bob uses Alice's public key
Key ba = bobKeyAgree.doPhase(aliceKpair.getPublic(), false);
// Carol uses Bob's public key
Key cb = carolKeyAgree.doPhase(bobKpair.getPublic(), false);
Key sc = saraKeyAgree.doPhase(carolKpair.getPublic(), false);
// Alice uses Carol's result from above
aliceKeyAgree.doPhase(cb, true);
// Bob uses Alice's result from above
bobKeyAgree.doPhase(ac, true);
// Carol uses Bob's result from above
carolKeyAgree.doPhase(ba, true);
saraKeyAgree.doPhase(sc,true);
// Alice, Bob and Carol compute their secrets
byte[] aliceSharedSecret = aliceKeyAgree.generateSecret();
System.out.println("Alice secret: " + toHexString(aliceSharedSecret));
byte[] bobSharedSecret = bobKeyAgree.generateSecret();
System.out.println("Bob secret: " + toHexString(bobSharedSecret));
byte[] carolSharedSecret = carolKeyAgree.generateSecret();
System.out.println("Carol secret: " + toHexString(carolSharedSecret));
byte[] saraSharedSecret = saraKeyAgree.generateSecret();
System.out.println("Sara secret: " + toHexString(saraSharedSecret));
// Compare Alice and Bob
if (!java.util.Arrays.equals(aliceSharedSecret, bobSharedSecret))
throw new Exception("Alice and Bob differ");
System.out.println("Alice and Bob are the same");
// Compare Bob and Carol
if (!java.util.Arrays.equals(bobSharedSecret, carolSharedSecret))
throw new Exception("Bob and Carol differ");
System.out.println("Bob and Carol are the same");
At the end of this, only 3 of the results match and the fourth one is different. What've I done wrong here?
Updated Answer
I'm still no cryptographer, so I've learnt a lot doing this, thank you!
I've rewritten the logic, the entire example is posted below for anyone that stumbles across this later on. It's also been tested in the sandbox over at Compile Java
I'll attempt to explain what's happening here, although if anyone reading this notices any gaping flaws in my implementation/explanation, please let me know. I can't say I entirely understand either it or the Java API used so I'd very much appreciate any clarification.
Explanation
This uses some clever maths, most of which is taken care of by the underlying APIs, we just need to tell it what to do, in the right order with the right values.
A generator g and modulus p are chosen and shared between all participants.
Alice, Bob, Carol and Sara choose private keys, (A, B, C and S) and compute their public keys (gA, gB, gC, gS). These are worked out from g raised to the power of their private keys, modulo p.
Each party needs to send the result of their operation to the next party along, and each party needs to perform n-1 operations using a value passed from another party, where n is the number of parties.
At the end of this, every party will have raised g by the power of everyone else's private key modulo p, without ever revealing to each other what their private keys are, using a process and pass method.
On the first pass, each participant computes an intermediate value (gAB, gBC etc) by raising their public keys by the power of the public key of the participant to their left, modulo p.
On passes 2+, they repeat this process, but using the result of the previous operation from the person on their left, raising that result to the power of their own private key, modulo p.
This pass-and-compute process repeats until each person has computed gABCS, which becomes the shared secret.
Due to the way maths works (The Law of Exponents if I'm not mistaken), gABCS = gBCSA = gCSAB = gSABC etc
An evesdropper, Eve would be able to see the values of gA, gB, gC, gS, gAB, gBC, gCS, gSA, gABC, gBCS, gCSA, but cannot use any combination of these to efficiently reproduce gABCS, as they don't know the values of A, B, C or S, as these are the private keys that are never transmitted.
This in theory could scale to more participants. By following the pattern in the code below. You'd add another participant, add them to the list of operations in each pass and add one more pass to ensure that everyone was doing the required number of operations.
I've added example code for four and five participants below.
Example with four participants
import java.security.*;
import java.security.spec.*;
import javax.crypto.*;
import javax.crypto.spec.*;
import javax.crypto.interfaces.*;
/*
* This program executes the Diffie-Hellman key agreement protocol between
* 4 parties: Alice, Bob, Carol and Sara using a shared 2048-bit DH parameter.
*/
public class DHKeyAgreement4 {
private DHKeyAgreement4() {}
public static void main(String argv[]) throws Exception {
// Alice creates her own DH key pair with 2048-bit key size
KeyPairGenerator aliceKpairGen = KeyPairGenerator.getInstance("DH");
aliceKpairGen.initialize(2048);
KeyPair aliceKpair = aliceKpairGen.generateKeyPair();
// This DH parameters can also be constructed by creating a
// DHParameterSpec object using agreed-upon values
DHParameterSpec dhParamShared = ((DHPublicKey)aliceKpair.getPublic()).getParams();
// Bob creates his own DH key pair using the same params
KeyPairGenerator bobKpairGen = KeyPairGenerator.getInstance("DH");
bobKpairGen.initialize(dhParamShared);
KeyPair bobKpair = bobKpairGen.generateKeyPair();
// Carol creates her own DH key pair using the same params
KeyPairGenerator carolKpairGen = KeyPairGenerator.getInstance("DH");
carolKpairGen.initialize(dhParamShared);
KeyPair carolKpair = carolKpairGen.generateKeyPair();
// Carol creates her own DH key pair using the same params
KeyPairGenerator saraKpairGen = KeyPairGenerator.getInstance("DH");
saraKpairGen.initialize(dhParamShared);
KeyPair saraKpair = saraKpairGen.generateKeyPair();
//Alice initialize
KeyAgreement aliceKeyAgree = KeyAgreement.getInstance("DH");
//Alice computes gA
aliceKeyAgree.init(aliceKpair.getPrivate());
//Bob initialize
KeyAgreement bobKeyAgree = KeyAgreement.getInstance("DH");
//Bob computes gB
bobKeyAgree.init(bobKpair.getPrivate());
//Carol initialize
KeyAgreement carolKeyAgree = KeyAgreement.getInstance("DH");
//Carol computes gC
carolKeyAgree.init(carolKpair.getPrivate());
//Sara initialize
KeyAgreement saraKeyAgree = KeyAgreement.getInstance("DH");
//Sara computes gS
saraKeyAgree.init(saraKpair.getPrivate());
//First Pass
//Alice computes gSA
Key gSA = aliceKeyAgree.doPhase(saraKpair.getPublic(), false);
//Bob computes gAB
Key gAB = bobKeyAgree.doPhase(aliceKpair.getPublic(), false);
//Carol computes gBC
Key gBC = carolKeyAgree.doPhase(bobKpair.getPublic(), false);
//Sara computes gCS
Key gCS = saraKeyAgree.doPhase(carolKpair.getPublic(), false);
//Second Pass
//Alice computes gCSA
Key gCSA = aliceKeyAgree.doPhase(gCS, false);
//Bob computes gSAB
Key gSAB = bobKeyAgree.doPhase(gSA, false);
//Carol computes gABC
Key gABC = carolKeyAgree.doPhase(gAB, false);
//Sara computes gBCS
Key gBCS = saraKeyAgree.doPhase(gBC, false);
//Third Pass
//Alice computes gBCSA
Key gBCSA = aliceKeyAgree.doPhase(gBCS, true); //This is Alice's secret
//Bob computes gCSAB
Key gCSAB = bobKeyAgree.doPhase(gCSA, true); //This is Bob's secret
//Sara Computes gABCS
Key gABCS = saraKeyAgree.doPhase(gABC, true); //This is Sara's secret
//Carol computes gSABC
Key gSABC = carolKeyAgree.doPhase(gSAB, true); //This is Carol's secret
// Alice, Bob, Carol and Sara compute their secrets
byte[] aliceSharedSecret = aliceKeyAgree.generateSecret();
System.out.println("Alice secret: " + toHexString(aliceSharedSecret));
byte[] bobSharedSecret = bobKeyAgree.generateSecret();
System.out.println("Bob secret: " + toHexString(bobSharedSecret));
byte[] carolSharedSecret = carolKeyAgree.generateSecret();
System.out.println("Carol secret: " + toHexString(carolSharedSecret));
byte[] saraSharedSecret = saraKeyAgree.generateSecret();
System.out.println("Sara secret: " + toHexString(saraSharedSecret));
// Compare Alice and Bob
if (!java.util.Arrays.equals(aliceSharedSecret, bobSharedSecret))
System.out.println("Alice and Bob differ");// throw new Exception("Alice and Bob differ");
else
System.out.println("Alice and Bob are the same");
// Compare Bob and Carol
if (!java.util.Arrays.equals(bobSharedSecret, carolSharedSecret))
System.out.println("Bob and Carol differ");//throw new Exception("Bob and Carol differ");
else
System.out.println("Bob and Carol are the same");
//Compare Carol and Sara
if (!java.util.Arrays.equals(carolSharedSecret, saraSharedSecret))
System.out.println("Carol and Sara differ");//throw new Exception("Carol and Sara differ");
else
System.out.println("Carol and Sara are the same");
}
/*
* Converts a byte to hex digit and writes to the supplied buffer
*/
private static void byte2hex(byte b, StringBuffer buf) {
char[] hexChars = { '0', '1', '2', '3', '4', '5', '6', '7', '8',
'9', 'A', 'B', 'C', 'D', 'E', 'F' };
int high = ((b & 0xf0) >> 4);
int low = (b & 0x0f);
buf.append(hexChars[high]);
buf.append(hexChars[low]);
}
/*
* Converts a byte array to hex string
*/
private static String toHexString(byte[] block) {
StringBuffer buf = new StringBuffer();
int len = block.length;
for (int i = 0; i < len; i++) {
byte2hex(block[i], buf);
if (i < len-1) {
buf.append(":");
}
}
return buf.toString();
}
}
Example with five participants
import java.security.*;
import java.security.spec.*;
import javax.crypto.*;
import javax.crypto.spec.*;
import javax.crypto.interfaces.*;
/*
* This program executes the Diffie-Hellman key agreement protocol between
* 5 parties: Alice, Bob, Carol, Sara and Dave using a shared 2048-bit DH parameter.
*/
public class DHKeyAgreement5 {
private DHKeyAgreement5() {}
public static void main(String argv[]) throws Exception {
// Alice creates her own DH key pair with 2048-bit key size
KeyPairGenerator aliceKpairGen = KeyPairGenerator.getInstance("DH");
aliceKpairGen.initialize(2048);
KeyPair aliceKpair = aliceKpairGen.generateKeyPair();
// This DH parameters can also be constructed by creating a
// DHParameterSpec object using agreed-upon values
DHParameterSpec dhParamShared = ((DHPublicKey)aliceKpair.getPublic()).getParams();
// Bob creates his own DH key pair using the same params
KeyPairGenerator bobKpairGen = KeyPairGenerator.getInstance("DH");
bobKpairGen.initialize(dhParamShared);
KeyPair bobKpair = bobKpairGen.generateKeyPair();
// Carol creates her own DH key pair using the same params
KeyPairGenerator carolKpairGen = KeyPairGenerator.getInstance("DH");
carolKpairGen.initialize(dhParamShared);
KeyPair carolKpair = carolKpairGen.generateKeyPair();
// Sara creates her own DH key pair using the same params
KeyPairGenerator saraKpairGen = KeyPairGenerator.getInstance("DH");
saraKpairGen.initialize(dhParamShared);
KeyPair saraKpair = saraKpairGen.generateKeyPair();
// Dave creates her own DH key pair using the same params
KeyPairGenerator daveKpairGen = KeyPairGenerator.getInstance("DH");
daveKpairGen.initialize(dhParamShared);
KeyPair daveKpair = daveKpairGen.generateKeyPair();
//Alice initialize
KeyAgreement aliceKeyAgree = KeyAgreement.getInstance("DH");
//Alice computes gA
aliceKeyAgree.init(aliceKpair.getPrivate());
//Bob initialize
KeyAgreement bobKeyAgree = KeyAgreement.getInstance("DH");
//Bob computes gB
bobKeyAgree.init(bobKpair.getPrivate());
//Carol initialize
KeyAgreement carolKeyAgree = KeyAgreement.getInstance("DH");
//Carol computes gC
carolKeyAgree.init(carolKpair.getPrivate());
//Sara initialize
KeyAgreement saraKeyAgree = KeyAgreement.getInstance("DH");
//Sara computes gS
saraKeyAgree.init(saraKpair.getPrivate());
//Dave initialize
KeyAgreement daveKeyAgree = KeyAgreement.getInstance("DH");
//Sara computes gS
daveKeyAgree.init(daveKpair.getPrivate());
//First Pass
//Alice computes gDA
Key gDA = aliceKeyAgree.doPhase(daveKpair.getPublic(), false);
//Bob computes gAB
Key gAB = bobKeyAgree.doPhase(aliceKpair.getPublic(), false);
//Carol computes gBC
Key gBC = carolKeyAgree.doPhase(bobKpair.getPublic(), false);
//Sara computes gCS
Key gCS = saraKeyAgree.doPhase(carolKpair.getPublic(), false);
//Dave computed gSD
Key gSD = daveKeyAgree.doPhase(saraKpair.getPublic(), false);
//Second Pass
//Alice computes gSDA
Key gSDA = aliceKeyAgree.doPhase(gSD, false);
//Bob computes gDAB
Key gDAB = bobKeyAgree.doPhase(gDA, false);
//Carol computes gABC
Key gABC = carolKeyAgree.doPhase(gAB, false);
//Sara computes gBCS
Key gBCS = saraKeyAgree.doPhase(gBC, false);
//Dave computes gCSD
Key gCSD = daveKeyAgree.doPhase(gCS, false);
//Third Pass
//Alice computes gCSDA
Key gCSDA = aliceKeyAgree.doPhase(gCSD, false);
//Bob computes gSDAB
Key gSDAB = bobKeyAgree.doPhase(gSDA, false);
//Carol computes gDABC
Key gDABC = carolKeyAgree.doPhase(gDAB, false);
//Sara Computes gABCS
Key gABCS = saraKeyAgree.doPhase(gABC, false);
//Dave computes gBCSC
Key gBCSD = daveKeyAgree.doPhase(gBCS, false);
//Fourth Pass
//Alice computes gBCSDA
Key gBCSDA = aliceKeyAgree.doPhase(gBCSD, true); //This is Alice's secret
//Bob computes gSDABC
Key gCSDAB = bobKeyAgree.doPhase(gCSDA, true); //This is Bob's secret
//Carol computes gSABC
Key gSDABC = carolKeyAgree.doPhase(gSDAB, true); //This is Carol's secret
//Sara Computes gABCS
Key gDABCS = saraKeyAgree.doPhase(gDABC, true); //This is Sara's secret
Key gABCSD = daveKeyAgree.doPhase(gABCS, true); //This is Dave's secret
// Alice, Bob, Carol and Sara compute their secrets
byte[] aliceSharedSecret = aliceKeyAgree.generateSecret();
System.out.println("Alice secret: " + toHexString(aliceSharedSecret));
byte[] bobSharedSecret = bobKeyAgree.generateSecret();
System.out.println("Bob secret: " + toHexString(bobSharedSecret));
byte[] carolSharedSecret = carolKeyAgree.generateSecret();
System.out.println("Carol secret: " + toHexString(carolSharedSecret));
byte[] saraSharedSecret = saraKeyAgree.generateSecret();
System.out.println("Sara secret: " + toHexString(saraSharedSecret));
byte[] daveSharedSecret = daveKeyAgree.generateSecret();
System.out.println("Dave secret: " + toHexString(daveSharedSecret));
// Compare Alice and Bob
if (!java.util.Arrays.equals(aliceSharedSecret, bobSharedSecret))
System.out.println("Alice and Bob differ");// throw new Exception("Alice and Bob differ");
else
System.out.println("Alice and Bob are the same");
// Compare Bob and Carol
if (!java.util.Arrays.equals(bobSharedSecret, carolSharedSecret))
System.out.println("Bob and Carol differ");//throw new Exception("Bob and Carol differ");
else
System.out.println("Bob and Carol are the same");
//Compare Carol and Sara
if (!java.util.Arrays.equals(carolSharedSecret, saraSharedSecret))
System.out.println("Carol and Sara differ");//throw new Exception("Carol and Sara differ");
else
System.out.println("Carol and Sara are the same");
//Compare Sara and Dave
if (!java.util.Arrays.equals(saraSharedSecret, daveSharedSecret))
System.out.println("Sara and Dave differ");//throw new Exception("Carol and Sara differ");
else
System.out.println("Sara and Dave are the same");
}
/*
* Converts a byte to hex digit and writes to the supplied buffer
*/
private static void byte2hex(byte b, StringBuffer buf) {
char[] hexChars = { '0', '1', '2', '3', '4', '5', '6', '7', '8',
'9', 'A', 'B', 'C', 'D', 'E', 'F' };
int high = ((b & 0xf0) >> 4);
int low = (b & 0x0f);
buf.append(hexChars[high]);
buf.append(hexChars[low]);
}
/*
* Converts a byte array to hex string
*/
private static String toHexString(byte[] block) {
StringBuffer buf = new StringBuffer();
int len = block.length;
for (int i = 0; i < len; i++) {
byte2hex(block[i], buf);
if (i < len-1) {
buf.append(":");
}
}
return buf.toString();
}
}