Question

The message
PJXFJ SWJNX JMRTJ FVSUJ OOJWF OVAJR WHEOF JRWJO DJFFZ BJF
was encrypted using an affine transformation C=aP + b mod {26}. Use frequencies of letters
to determine the values of $a$ and $b$. What is the plain text message?

Answer 1

So I haven't done too much of this before, but the first thing we need to know is what letters are the most common in general speech. Then you need to find which letters appear the most in the ciphertext. Do you have some sort of chart for which letters are the most common?

Answer 2

Correct, i have that j is most occuring followed by f. Which gives me that j most likely equal e and f equals t.

Answer 3

This in turn gives me two equations
9=4a+b & 5= 19a+b

Answer 4

this is in modulo 26

Answer 5

Looks reasonable so far.

Answer 6

This is where I get confused because I need to somehow find the inverse and so on. Nothing is clear to me

Answer 7

I am not sure what I am finding the inverse of?

Answer 8

Well, why don't we try solving like a regular old system of equations.\[9\equiv4a+b\pmod{26}\implies b\equiv9-4a\pmod{26}\]Plug this into the other equation, and we get\[5\equiv19a+9-4a\pmod{26}\]Simplifying a bit, this means\[5\equiv15a+9\pmod{26}\implies11a\equiv4\pmod{26}\]Following this so far?

Answer 9

Yes

Answer 10

This is where we find he inverse of \(11\) modulo 26. There's a couple methods to finding it. Are you familiar with any of them?

Answer 11

Every time I find a way it is the wrong one. I am definitely having trouble with inverses but I am most comfortable with euclid algorithm

Answer 12

That's a nice straightforward way.

Answer 13

With the euclidean algorithm, we get\[26=2\cdot11+4\]\[11=2\cdot4+3\]\[4=3\cdot1+1\]Now we back-substitute.

Answer 14

We have\[1=4-3\]\[3=11-2\cdot4\]\[4=26-2\cdot11\]So\[\begin{aligned}
1&=4-3\\
&=(26-2\cdot11)-(11-2\cdot4)\\
&=26-3\cdot11+2\cdot4\\
&=26-3\cdot11+2(26-2\cdot11)\\
&=3\cdot26-7\cdot11
\end{aligned}\]So the inverse of \(11\) modulo \(26\) should be \(-7\), or \(19\).

Answer 15

That looks so much simpler and organized than what I have done when trying to do this. No wonder I am having trouble. Now, does this mean that 19 is a?

Answer 16

We have one last thing to work out. We know that\[11\cdot(-7)\equiv1\pmod{26}\]but we want to solve\[11a\equiv4\pmod{26}.\]But solving for \(x\) is easy, as we only need to multiply by 4. So\[11\cdot(-7)\cdot4\equiv1\cdot4\equiv4\pmod{26}.\]Then\[-7\cdot4=-28\equiv24\pmod{26}\]So \(a=24\), or \(-2\) since that's probably easier to work with.

Answer 17

I do not see how you get 24

Answer 18

\(24\) simply comes from the fact \(-28\equiv24\pmod{26}\) since \(-28=24-2\cdot26\).

Answer 19

Okay. So now that I have this what should I do next?

Answer 20

Now you need to plug this back into your original equations to solve for \(b\).

Answer 21

Do you I lug in 24? or -2?

Answer 22

Either will work, but \(-2\) will probably result in an easier computation.

Answer 23

Okay, so I have that b =17.

Answer 24

Right. So the affine transformation should be given by\[C=-2P+17\pmod{26}\]Or if you're only allowed to use positive numbers in the final solution, you could write\[C=24A+17\pmod{26}\]

Answer 25

Sorry, the last equation should be\[C=24P+17\pmod{26}\]

Answer 26

Okay. So now I plug in my first letter which is p =15. I have 15=24P+17, P=1?

Answer 27

You're solving for the plain text not the ciphertext.

Answer 28

C=P is the first letter of the cipher text, correct?

Answer 29

\(P=1\) seems like it works.

Answer 30

But what do I do when I get to A which is valued at 0. I would have a fraction?

Answer 31

Something seems off to me.

Answer 32

BEKGE ECK EAME GLE EG LEA FG EAE HEGGJ IEG

Answer 33

Which is clearly wrong.

Answer 34

I feel like we are on the right track just missing something. Maybe it is not the obvious? Would there be another way?

Answer 35

The missing data here is the frequency information. The idea is to use common frequencies of letters in the English language to aid solving the scale and shift constants.

Answer 36

i did this, unless i was given incorrect information

Answer 37

I believe @alchemista is probably right. In this particular case, I don't think e is sent to j, and t is sent to f. I'm afraid it has to be something else.

Answer 38

The math I worked out is definitely correct. However, at the end, we need to get a value for \(a\) that is relatively prime to \(26\).

So what's your second guess for which letters map to j and f? Note that we don't have to change both. Just one.

Answer 39

Are there many 5 letter words JMRTJ that start and end with e?

Answer 40

err, I mean I can't think of any right now.

Answer 41

It's not a 5-letter word, it's two words

Answer 42

yes its not a 5 letter word, it could be but it is most likely not

Answer 43

*PJXFJ is two words, JMRTJ is part of a longer word

Answer 44

it could be the end of the word before it or the beginning of another word. I think!

Answer 45

So to actually decrypt this, you need to take another guess at what might get sent to j, and what might get sent to f. I think it's probably a safe bet to keep e going to j. But what about f? What are some of the most common letters beside e and t?

Answer 46

R, N, I are the third most used

Answer 47

*S goes F

Answer 48

I think I'm going to agree with @eashy here. In general practice, you would have to guess and check a bunch of different possible combinations, you should probably just send S to F and E to J, and solve from there.

Answer 49

(12, 'J')
(7, 'F')
(5, 'O')
(4, 'W')

e 12.702%
t 9.056%
a 8.167%
o 7.507%
i 6.966%

Answer 50

F is the second most common. It seems very unlikely that it would be S if it followed frequencies in english.

Answer 51

actually you could do T->O instead

Answer 52

these problems are not really meant to be solved by hand though, the best way is algorithmically

Answer 53

http://ptrow.com/perl/calculator.pl ,y professor gave us this website but I cannot see how to do the affine function with this calculator

Answer 54

If you have a short message, the frequencies of letters in the message won't model the real-life frequencies very well. You need a large sample size to start seeing those.

Answer 55

It just seems like so much work to have to keep trying doing different calculations, especially since we need to find the inverses

Answer 56

KingGeorge, obviously as the sample size increase the distribution will converge toward the one listed on wikipedia. However, this is the best you have to work with. Other than that its just guess and check.

Answer 57

Well, if you do everything by hand it can get quite tedious. But plug some numbers in a calculator, and it goes by in a flash.

Answer 58

So 9, 25 does work

Answer 59

A = 9 b = 25

Answer 60

Yay for brute force: http://pastebin.com/4L2WmJTZ

Answer 61

[A=9 b=25]: WEUSE FREQU ENCIE SOFLE TTERS TODEC RYPTS ECRET MESSA GES

Answer 62

that makes sense

Answer 63

Brute forcing decryption is definitely the best way to go. Always. :P

Answer 64

Wish I could do that. But I still need an explanation because this is for a number theory class

Answer 65

Just justify it after the fact by using the original technique. Solve the system of equations setting the expected letters using our ill gotten knowledge.

Answer 66

Right. Same process as we did before, just the equations\[9=4a+b\]and\[5=20a+b\]instead.

Answer 67

so it is s not t

Answer 68

I have to say it was mean of them to throw in the spaces to possibly confuse you.

Answer 69

5=20a+b or 5=18a+b

Answer 70

Why blocks of 5 letters? Mysterious...

Answer 71

In most ciphertexts I've seen, it's usually broken up into 5 block chunks. And possibly adding some junk text at the very end to ensure that.

Right 5=18a+b. Sorry about that. It's getting late here :P

Answer 72

It makes sense to have a fixed block size for a block cipher

Answer 73

okay

Answer 74

The 5 blocks is a remnant from ciphers that require you to write out the alphabet in a 5x5 square (i and j are in the same place).

Answer 75

Ah, thanks. That makes more sense.

Answer 76

This is one of the more well-known of that form. http://en.wikipedia.org/wiki/Playfair_cipher

Answer 77

Anyway, hopefully when you solve the system you get 9, 25

Answer 78

I think polybius square is the official name.

Answer 79

Not getting a=9 or b=25

Answer 80

Solving the two equations, I am getting -4=14a (mod 26)

Answer 81

Something is wrong here

Answer 82

There is no inverse for a

Answer 83

Must get some sleep now, i have classes in a couple hours. If any of you care to try again, please let me know. I do not see how to get an inverse out of these equations. Thank you for your help. Also, alchemist I see that you programming? I need some help with a very simple program (counting characters using arrays but it starts with a string and it only counts numbers 1 - 9) If interested let me know thanks.

Answer 84

Try to continue from here:
15 = A*22 + b
9 = A*4 + b

6 = 18*a
....

Answer 85

18*9 (mod 26) = 6

Answer 86

Why 22?

Answer 87

W -> P

Answer 88

It works, doesn't it?

Answer 89

Yes but I have to show work and I cant see how I would explain that answer

Answer 90

What two equations were you using? Let me check if it is correct.

Answer 91

9=4a+b and 5=18a+b

Answer 92

9 * 14 (mod 26) = 22 = (26 - 4) == -4 (mod 26)

Answer 93

Don't you see? -4 == 22 (mod 26)

Answer 94

yes But how does that give me a=9

Answer 95

9 is a possible solution, you need to solve it using the euclidean algorithm as KingGeorge demonstrated.

Answer 96

Yes, I have tried but I did not try 4

Answer 97

You have -4 = 14*a correct?
Rewrite it as 22 = 14*a

Answer 98

ok