Kmftgj

Use of Linear Algebra in Cryptography

Hong-Jian Lai Department of Mathematics West Virginia University Morgantown, WV

– p. 1/??

Creating a Matrix

  Problem: To create a matrix A =  4 5 6 .   7 8 10



1 2

3



– p. 2/??

Creating a Matrix

  Problem: To create a matrix A =  4 5 6 .   7 8 10 Matlab:



1 2

3



– p. 2/??

Creating a Matrix

  Problem: To create a matrix A =  4 5 6 .   7 8 10 Matlab: A = [1 2 3; 4 5 6; 7 8 10]



1 2

3



– p. 2/??

Compute the inverse of A mod m

Output setting: Need to set the output as "rational" using a matlab comment format rat;

– p. 3/??

Compute the inverse of A mod m

Output setting: Need to set the output as "rational" using a matlab comment format rat;   1 2 3    4 5 6 , find A−1 mod 26. Problem: Given A =   7 8 10

– p. 3/??

Step 1: Compute inverse over the reals

Matlab commends:

– p. 4/??

Step 1: Compute inverse over the reals

Matlab commends: format rat;

– p. 4/??

Step 1: Compute inverse over the reals

Matlab commends: format rat; Ainv = inv(A)

– p. 4/??

Step 1: Compute inverse over the reals

Matlab commends: format rat; Ainv = inv(A)   −2/3 −4/3 1   Ainv =  −2/3 11/3 −2    1 −2 1

– p. 4/??

Step 1: Compute inverse over the reals

Matlab commends: format rat; Ainv = inv(A)   −2/3 −4/3 1   Ainv =  −2/3 11/3 −2    1 −2 1 Observation: 3 is a common denominator.

– p. 4/??

Step 2: Making it all integral

Problem: Need to rationalize this matrix before we take modulo m. As every entry of Ainv has a common denominator 3, multiply by 3 to make it an integer valued matrix.

– p. 5/??

Step 2: Making it all integral

Problem: Need to rationalize this matrix before we take modulo m. As every entry of Ainv has a common denominator 3, multiply by 3 to make it an integer valued matrix. A1=(Ainv*3)

– p. 5/??

Step 2: Making it all integral

Problem: Need...