We are aware that a major cryptosystem element plays a crucial part in maintaining
the security and robustness of cryptography. Various researchers are focusing on creating
new forms of cryptography and improving those that already exist using the principles of
number theory and linear algebra. In this article, we have proposed a Extended generalized
Fibonacci matrix (recursive matrix of higher order) having relation with Extended generalized
Fibonacci sequences and established some properties in addition to that usual matrix algebra.
Further, we proposed a modified public key cryptography using these matrices as keys in
Affine-Hill Cipher and key agreement for encryption-decryption with the combination of
terms of Extended generalized Fibonacci sequences under prime modulo. This system has
a large key space and reduce the time complexity as well as space complexity of the key
transmission by only requiring the exchange of pair of numbers(parameters) as opposed to
the entire key matrix