Solve for two variables within to linear modulus equations

I am currently working on a project to break a text file encoded with the Affine Cipher using unknown keys. The text file contains the extended ASCII so my modulus will be 256 (given in project instructions).

I am trying to avoid brute forcing this, and I will like algebraically solve for my key using frequency analysis of the cipher text. The problem I am running into is I am not super familiar with Matlab, but it is what we use in the course.

So this is what I have tried, using a known key of (251,69)

S = solve(32*a+b==165, 101*a+b==76)
S.a = -89/69
S.b = 14233/69

What I would like to some how do is this:

S = solve(mod(32*a+b,256)==165, mod(101*a+b,256)==76)
S.a = 251
S.b = 69

However, this does not work. I've searched and attempt MuPAD and the lincongruence, but it does not seem appropriate for two variables. I've also tried linsolve and setting the Domain = Dom::IntegerMod(256). But that threw the following error:

Error: 'Domain = R', where R is a domain of category 'Cat::Field', expected. [linsolve]

Thank you in advance!

(Using Matlab R2018b Academic Use)

Answer 1

[John D'Errico]

Pretty easy, really. You have a linear system of modular equations.

mod(32*a+b,256)==165

mod(101*a+b,256)==76

Just subtract the two, which is entirely valid. Then we learn that

mod((101 - 32)*a,256) == 76 - 165

This reduces to the univariate problem

mod(69*a,256) == 167

The modular inverse of 69, mod 256 exists, since gcd(69,256)==1. I.e., they are relatively prime.

[g,a,b] = gcd(69,256)
g =
     1
a =
  -115
b =
    31
    
mod(a,256)
ans =
   141

So as long as gcd returns 1 for the gcd, then the modular inverse of 69 is mod(a,256)==141. (Read the help for gcd, where you will learn what the second and thid outputs of GCD mean.)

That tells us we can solve for a simply as...

a = mod(167*141,256)
a =
   251

And we find b as:

b = mod(165 - 32*a,256)
b =
    69

Verification step:

mod(32*a + b,256)
ans =
   165
mod(101*a + b,256)
ans =
    76

Had the problem been more general, it still would have been as easy, as long as it was a linear system. Lets see, I think I posted rrefgf on the file exchange just recently. It can do the work.

A = [32 1;101 1];
Ared = rrefgf([A,eye(2)],256)
Ared =
     1     0   115   141
     0     1   161    96
rhs = [165 ; 76];
ab = mod(Ared(:,3:4)*rhs,256)
ab =
   251
    69

So a is ab(1), b = ab(2).

(Drat, I thought I had posted rrefgf on the FEX. I'll attach it to this answer.)

[Stephen Comstock]

Thank you for this! I was trying to get so down in the weeds on this being my first real project with MatLab I didn't take a step back and work it out on paper first.

[John D'Errico]

:)