## Solve for two variables within to linear modulus equations

### Stephen Comstock (view profile)

on 11 Feb 2019
Latest activity Commented on by John D'Errico

on 11 Feb 2019

### John D'Errico (view profile)

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]

### John D'Errico (view profile)

on 11 Feb 2019
Edited by John D'Errico

### John D'Errico (view profile)

on 11 Feb 2019

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

### Stephen Comstock (view profile)

on 11 Feb 2019
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

on 11 Feb 2019
:)