DH Key Agreement in Java: why generated keys are mostly equal for both parties?

Question

I'm trying to create a very simple key exchange in Java. After the code and output there are questions:

 public class Blergh {

    public static KeyPair genKeyPair512() {
        try {
            AlgorithmParameterGenerator paramGen = AlgorithmParameterGenerator
                    .getInstance("DH");
            paramGen.init(512);

            BigInteger g = new BigInteger(
                    "7961C6D7913FDF8A034593294FA52D6F8354E9EDFE3EDC8EF082D36662D69DFE8CA7DC7480121C98B9774DFF915FB710D79E1BCBA68C0D429CD6B9AD73C0EF20",
                    16);
            BigInteger p = new BigInteger(
                    "00AC86AB9A1F921B251027BD10B93D0A8D9A260364974648E2543E8CD5C48DB4FFBEF0C3843465BA8DE20FFA36FFAF840B8CF26C9EB865BA184642A5F84606AEC5",
                    16);
            final KeyPairGenerator keyGen = KeyPairGenerator.getInstance("DH");
            final DHParameterSpec dhSpec = new DHParameterSpec(p, g, 511);
            keyGen.initialize(dhSpec);
            return keyGen.generateKeyPair();

        } catch (NoSuchAlgorithmException e) {
            e.printStackTrace();
        } catch (InvalidAlgorithmParameterException e) {
            e.printStackTrace();
        }
        return null;
    }

    public static byte[] genSharedSecretKey(KeyPair keyPair,
            byte[] bytesPeerPublicKey) {
        PrivateKey privateKey = keyPair.getPrivate();

        try {
            X509EncodedKeySpec x509KeySpec = new X509EncodedKeySpec(
                    bytesPeerPublicKey);
            KeyFactory keyFact = KeyFactory.getInstance("DH");
            PublicKey peerPublicKey = keyFact.generatePublic(x509KeySpec);

            KeyAgreement ka;

            ka = KeyAgreement.getInstance("DH");
            ka.init(privateKey);
            ka.doPhase(peerPublicKey, true);
            String algorithm = "AES";

            SecretKey secretKey = ka.generateSecret(algorithm);

            return secretKey.getEncoded();

        } catch (NoSuchAlgorithmException e) {
            e.printStackTrace();
        } catch (InvalidKeyException e) {
            e.printStackTrace();
        } catch (InvalidKeySpecException e) {
            e.printStackTrace();
        }

        return null;
    }

    public static void main(String argv[]) {
            KeyPair akp = genKeyPair512();
            KeyPair bkp = genKeyPair512();

        System.out.println("Ali pub key: "
                + toRawHex(akp.getPublic().getEncoded()));
        System.out.println("Bob pub key: "
                + toRawHex(bkp.getPublic().getEncoded()));

            System.out.println("Ali pri key: "
                + toRawHex(akp.getPrivate().getEncoded()));
        System.out.println("Bob pri key: "
                + toRawHex(bkp.getPrivate().getEncoded()));

        byte[] apk = akp.getPublic().getEncoded();
        byte[] bpk = bkp.getPublic().getEncoded();

        byte[] as = genSharedSecretKey(akp, bpk);
        byte[] bs = genSharedSecretKey(bkp, apk);

    }
}

It generates, for example, the output:

Ali pub key: 3081DF30819706092A864886F70D010301308189024100AC86AB9A1F921B251027BD10B93D0A8D9A260364974648E2543E8CD5C48DB4FFBEF0C3843465BA8DE20FFA36FFAF840B8CF26C9EB865BA184642A5F84606AEC502407961C6D7913FDF8A034593294FA52D6F8354E9EDFE3EDC8EF082D36662D69DFE8CA7DC7480121C98B9774DFF915FB710D79E1BCBA68C0D429CD6B9AD73C0EF20020201FF03430002403BBCBF4052CD1CEF7A580A919AF75186CE0A624BC93AA47922C3822CE60A8CD10CE98550ABCA2D39DA2F09903C3D761B9A1C4AED185934FE5D08AD0CD097AA86
Bob pub key: 3081DF30819706092A864886F70D010301308189024100AC86AB9A1F921B251027BD10B93D0A8D9A260364974648E2543E8CD5C48DB4FFBEF0C3843465BA8DE20FFA36FFAF840B8CF26C9EB865BA184642A5F84606AEC502407961C6D7913FDF8A034593294FA52D6F8354E9EDFE3EDC8EF082D36662D69DFE8CA7DC7480121C98B9774DFF915FB710D79E1BCBA68C0D429CD6B9AD73C0EF20020201FF03430002400F119BC06E53F8C33D3F7C16473D1F9E001FABF4D619930C34945AA2C6D0A00CB9B332CEAF2C0C2FB61D3F568B9263B69A152410237F4D793F8B571C34AB37B7
Ali pri key: 3081E102010030819706092A864886F70D010301308189024100AC86AB9A1F921B251027BD10B93D0A8D9A260364974648E2543E8CD5C48DB4FFBEF0C3843465BA8DE20FFA36FFAF840B8CF26C9EB865BA184642A5F84606AEC502407961C6D7913FDF8A034593294FA52D6F8354E9EDFE3EDC8EF082D36662D69DFE8CA7DC7480121C98B9774DFF915FB710D79E1BCBA68C0D429CD6B9AD73C0EF20020201FF0442024043BA0B3C73EB7482B80DE98FA81A7E50B0DC2F5786CA62285655BD36CE012C056545DE5EED65736D9135EC9CD5148F8D68FF3C7B5CC62B2A1F7649698B26D1BE
Bob pri key: 3081E102010030819706092A864886F70D010301308189024100AC86AB9A1F921B251027BD10B93D0A8D9A260364974648E2543E8CD5C48DB4FFBEF0C3843465BA8DE20FFA36FFAF840B8CF26C9EB865BA184642A5F84606AEC502407961C6D7913FDF8A034593294FA52D6F8354E9EDFE3EDC8EF082D36662D69DFE8CA7DC7480121C98B9774DFF915FB710D79E1BCBA68C0D429CD6B9AD73C0EF20020201FF04420240485DDD7F5BDECA92FEE30D9D15211D274BC0FF7838B8B51E7894263CA65DB4E394033CE3E2146C0CD0CA74E2DB0EF95D01EE0DC4011A3EC6A8EC61CC2FDC5A44

So, I have a main question and two additional ones:

1. Why more than half of the bytes of the keys (both private and public) between Alice and Bob are equal? For instance, Alice's private starts with 3081E102010030819706092A... and Bob's private with 3081E102010030819706092A... as well.
2. Why is DHParameterSpec created with 511 and not 512 (at least in most examples on the web)?
3. Assuming there's nothing wrong with the generated keys, is there something else that I'm missing here, or this code should be safe when adpated to exchange the public keys through the internet?

Any help is welcome. Thanks in advance.

EDIT: The third question applies to the genSharedSecretKey() as well (that is, the whole code), though I'm not calling/showing output because it would be irrelevant.

Answer 1

Why more than half of the bytes of the keys (both private and public) between Alice and Bob are equal? For instance, Alice's private starts with 3081E102010030819706092A... and Bob's private with 3081E102010030819706092A... as well.

When you call getEncoded() you receive a copy of the key data in ASN.1 format. Depending upon the objects being represented, there is often a certain amount of duplicate data present in any two structures. Somewhere within the structure will be the key data, which will be different for Alice and Bob.

Indeed, as CodesInChaos stated in the comments, the first part of the ASN.1 structure contains the group parameter which is identical between both parties.

Answer 2

The reason why you receive keys with much duplicate that is - as Duncan suggested - that it is encoded in an ASN.1 format. And that does explain the amount of duplicate data as the contains the parameters p and g you've specified yourself - look for the values in the hexadecimal string. If you want to take a look at the contents, simply paste the hexadecimal output into an online ASN.1 decoder, such as the one found here.

There is a lot to be said about DH and (key) sizes. Some interesting discussions can be found on security.stackexchange.com and crypto.stackexchange.com. But in the end, we don't know; you typed in the code, so we should ask you how and why the Diffie-Hellman parameters were chosen.

As for the third question; to distribute public keys on the internet you need to establish trust. You need to trust the other party. Diffie Hellman key agreement by itself does not establish trust; only a shared secret with some other party. So you need a secure protocol (such as TLS) with trusted certificates or keys that contains an authentication component. A lot of knowledge is required to create such a protocol however; if you do not fully understand the code you just showed us, you will fail to create such a protocol yourself.

Note that if both parties have agreed upon a set of parameters, that it may not be necessary to send the whole encoded public key; you may just have to send the values that the other party does not know so the other party can reconstruct the public key.