Two parties can establish a cryptographic key using a matrix based key exchange protocol, for secure communications without any prior distribution of secret keys or other secret data, and without revealing said key to any third party who may have access to all of the transmissions between them. The two parties use a shared secret to produce a common matrix M. The common matrix M, is multiplied by a random matrix K on the sending side, and a different random matrix N on the receiving side. The matrix product KM is sent from the sending side to the receiving side, and the matrix product MN is sent from the receiving side to the sending side. Both sides produce the common matrix product KMN, and use it for producing a symmetric key for encrypted communications, after mutually authenticating one another over an insecure network.