Diffie-Hellman algorithm is one of the first schemes proposed for the exchange of keys required in asymmetric encryption. It was developed by Whitfield Diffie and Martin Hellman in 1976. This algorithm removes the need of transferring keys between two communicating parties. It enables each party to generate a shared secret key for encryption and decryption of data. The security of this algorithm cannot be compromised because several security protocols and services depend upon Diffie- Hellman key exchange for reliable communication. In this paper, we have used a random parameter to make this algorithm more efficient. The random parameter generates new shared keys for each message that is exchanged between sender and receiver. So, different ciphertext will be produced each time even for the same message. Thus, systems using this scheme will become more tolerant to various attacks.