0

for a subject I am implementing the Hill Cipher example from wikipedia using numpy. My code so far is below:

import numpy as np

msg = np.array([0, 2, 19]) # CAT
key = np.matrix([
    [6, 24, 1],
    [13, 16, 10],
    [20, 17, 15]
])

ciphertext = np.mod(np.dot(key, msg), 26) # [5, 8, 13] # POH

# And here things go wrong
invKey = key.I
invKey2 = np.linalg.inv(key) # same as key.I

Until line 10 ("ciphertext") things work as they should. np.mod(np.dot(key, msg), 26) returns [15, 14, 7], as specified in the article. But when I try to do a matrix inverse I get drastically different results than I expected. The article suggests that the key matrix inverse should return this:

[[8, 21, 21],
 [5, 8, 12],
 [10, 21, 8]]

But instead this is returned:

[[ 0.15873016 -0.77777778  0.50793651]
 [ 0.01133787  0.15873016 -0.10657596]
 [-0.2244898   0.85714286 -0.48979592]]

Now, I can understand from various questions on this site that numpy.linalg.inv() has a problem with floating point precision. But these results are so different from the expected that there must be more going on right? I am new to numpy. Please help me understand what is going on here and how I can alleviate the problem, so the key matrix is inverted as the article specifies. Thank you for your time.

MyrionSC2
  • 1,248
  • 1
  • 14
  • 24
  • 1
    I think that your solution for the inverse is wrong. It does not satisfy `keyInv.dot(key) == eye(3)`, instead NumPy's solution does... – Tom de Geus Aug 19 '18 at 13:31
  • 1
    At the same time I don't know how to understand your Wikipedia article in terms of the proposition of the inverse – Tom de Geus Aug 19 '18 at 13:36
  • 1
    The inverse is computed correctly. To verify that, you can either do it manually, or plug in your values in mathematica's online tool. The values you see in Wiki article has a `(mod(26))` written in front of the matrix on the right hand side of the inverse equation. You can't ignore that. Check this link for the inverse: http://www.wolframalpha.com/widgets/view.jsp?id=35f68681262e42ea89b0834caa51635b – Sheldore Aug 19 '18 at 13:37
  • 1
    Numpy is calculating the correct inverse. The "inverse" that you need for Hill cipher is a mod 26 inverse (which Numpy does not calculate). The `Wikipedia` article you site gives some hints that can be combined with [matrix inversion](https://en.wikipedia.org/wiki/Invertible_matrix#Inversion_of_3_%C3%97_3_matrices) and [modular multiplicative inverse](https://en.wikipedia.org/wiki/Modular_multiplicative_inverse) in order to write your own mod 26 matrix inversion code. – John Anderson Aug 19 '18 at 14:15
  • Today I have learned that there is a difference between a matrix inverse and matrix modulo inverse. Thank you for the help :) – MyrionSC2 Aug 19 '18 at 15:19

1 Answers1

1

To answer my own question, what is needed for the Hill cipher is a matrix modulo inverse, not the matrix inverse that numpy.linalg.inv() provides. The code in Johns answer in this post was what I needed.

MyrionSC2
  • 1,248
  • 1
  • 14
  • 24
  • Or [`inv_mod`](http://docs.sympy.org/latest/modules/matrices/matrices.html#sympy.matrices.matrices.MatrixBase.inv_mod) from SymPy, which computes such inverses. –  Aug 19 '18 at 20:31