Shared Public Key using Multidimensional PRNGs

Previously I showed how to find a matrix $bar A$, that would generate all possible tuples of a given rank $d$ using the recurrence relation:

1. $bar X_i = bar A . bar X_(i-1) mod p$

Using matrix $bar A$, we can securely establish a shared key for encrypting further communication with all communication being public.

Imagine there are two individuals that want to establish a secure channel, Bill and Sally. Here is a mechanism for them to establish a secure channel with each other. This is an adaptation of the Diffie-Hellman key-exchange to matrices instead of prime numbers.

• Sally creates matrix $bar A$ of rank $d$ with prime $p$, which produces a maximum length sequence of all possible tuples when used with equations [1].
• Sally comes up with a random number $x$ between 0 and $p^d-1$. This is kept private.
• Sally sends Bill the set of information $(bar A, bar A^x mod p, p)$
• Bill comes up with a random number $y$ between 0 and $p^d-1$. This is kept private.
• Bill sends Sally $bar A^y mod p$
• Using $bar A^x mod p$ matrix Sally sent him, Bill calculates $(bar A^x)^y mod p =bar A^(xy) mod p$
• Using the $A^y mod p$ matrix Bill sent her, Sally calculates $(bar A^y)^x mod p =bar A^(xy) mod p$
• Sally and Bill now have the same matrix $bar A^(xy) mod p$ that only they know.

Why is this Secure?

Someone intercepting Bill and Sally's communication sees [$bar A, p, bar A^x mod p, bar A^y mod p$]. It is very difficult to calculate $bar A^(xy)$ from this because $bar A^x mod p$ and $bar A^y mod p$ are not invertible. One would need to solve for $x$ and $y$ which would involve doing a discrete logarithm of $bar A^x mod p$ and $bar A^y mod p$. There is no known way to do this other than the brute force method of calculating $A^i mod p$ for all $i$ values from 0 to $p^d-1$. Since $p^d-1$ will in practice be extremely large, then the inversion will take an unacceptably long time and for large enough $p^d-1$, will be theoretically impossible.

Example

Sally generates matrix $bar A$, with rank $d=3$ and prime $p=227$

$bar A = [[52,18,218],[16,123,98],[25,169,205]]$

Sally comes up with a random number $x$ between 0 and $p^d-1=11697082$ of $x=8382731$

She calculates $bar A^x mod p$ as

$bar A^x = [[16,131,208],[6,43,162],[185,134,195]]$

She sends Bill $(bar A, bar A^x mod p, p)$

Bill comes up with random number $y=1988867$

Bill calculates $bar A^y mod p$ as

$bar A^y=[[82,62,20],[222,14,104],[26,210,82]]$

and $bar A^(yx) mod p$ as

$bar A^(yx)=[[191,43,153],[132,34,160],[40,131,191]]$

He sends Sally $bar A^y$ and she calculates $bar A^(xy) mod p$ as

$bar A^(xy)=[[191,43,153],[132,34,160],[40,131,191]]$

Sally and Bill now have the same shared key $(bar A^(yx) mod p)=(bar A^(xy) mod p)$