These days, the best way to secure our data and conversations is to use message encryption techniques. Thanks to the proliferation of network and internet communications, advancements in message encryption technologies have picked up speed. When personal, sensitive information is transmitted via unsecured networks, it opens the door to possible hacking attempts, theft, and eavesdropping on conversations. In order to shorten this term, cryptographic methods are essential. Along with the conventional matrix algebra, we created a higher-order recursive matrix called an Extended generalised Lucas matrix and linked it to Extended generalised Fibonacci sequences in this paper. Elliptic curve cryptography and graph theory are the foundations of our proposed public key cryptography, which employs these matrices as keys for an affine cypher and key agreement for encryption-decryption using a mix of terms from Extended generalised Lucas sequences and residue operations. By reducing key transmission to the exchange of a small set of numbers (parameters) rather than the full key matrix, this method offers a large key space while simultaneously reducing the space and time complexity of key transmission. On top of that, it’s secure and dependable since it’s built on the challenging Elliptic Curve-Discrete Logarithm algorithm.