Asked by Stephen Comstock
on 11 Feb 2019

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 by John D'Errico
on 11 Feb 2019

Edited by John D'Errico
on 11 Feb 2019

Accepted Answer

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

John D'Errico
on 11 Feb 2019

:)

Sign in to comment.

Opportunities for recent engineering grads.

Apply Today
## 0 Comments

Sign in to comment.