The best method for exponentiation is highly dependant on the algebraic set employed. Block upper triangular matrices defined in Zp, have very interesting properties for multiple applications, in which exponentiation is very important in order to achieve adequate performance. We analyze the usage of quick exponentiation methods with these matrices and, as a practical application, we propose a new public-key cryptosystem and digital signature scheme based on a generalization of the well known discrete logarithm problem to block upper triangular matrices.