This eliminates B. Dividing both sides of this new equation by 3 tells Art that A = 14, and then substituting this back into the first equation, 57 = 3 × 14 + B, gives B = 15.
Art now knows that the line passing through (3, 57) and (6, 99) is described by the equation y = 14x + 15. But he also knows that in a Reed-Solomon code, the secret message is hiding in the coefficients. He decodes Zeke’s message using their simple agreed-upon alphabet cipher: 14 is “N” and 15 is “O,” which tells Art that, no, Zeke can’t play video games after school today.
The secret to this simple Reed-Solomon code starts with two basic facts of geometry. First, through any two points there is a unique line. Second, for coefficients A and B, every (non-vertical) line can be written in the form y = Ax + B. Together, these two facts guarantee that if you know two points on a line you can find A and B, and if you know A and B, you know all the points on the line. In short, possessing either set of information is equivalent to knowing the line.
Reed-Solomon codes leverage these equivalent sets of information. The secret message is encoded as the coefficients A and B, and the line’s points are broken up into pieces, some of which are transmitted publicly, and some of which are kept private. To decode the message, you just collect the pieces and put them back together. And all that this requires is some simple algebra.
Zeke’s pieces were the numbers 57 and 99, which he sent to Art. These numbers are the public part of the message. Art put those together with his own pieces, 3 and 6, to reconstruct the points (3, 57) and (6, 99). Here, the 3 and the 6 constitute the private part of the message, which Art and Zeke agreed upon beforehand.
The two points lie on a line, and to decode the message, you just need to find that line’s equation. Plugging each point into y = Ax + B gives you a system of two equations about the line that must both be true. Now the strategy is straightforward: Solve the system, determine the line and decode the message.
In algebra class you probably learned many methods of solving systems of equations, such as graphing, guessing and checking, and substitution. Art used elimination, a method where you manipulate the equations algebraically in order to eliminate the variables one at a time. Each time you eliminate a variable, the system becomes a little easier to solve.
As with other encryption schemes, it’s the clever combination of public and private information that keeps messages secure. Zeke could shout his numbers 57 and 99 across the classroom and it wouldn’t jeopardize the security of his message to Art (though it might get him in trouble with Ms. Al-Jabr). That’s because without the corresponding private information — the x-coordinates 3 and 6 — it’s impossible to identify the equation of the line. As long as they keep those values to themselves, they can safely pass their secret messages in public.
The line y = 14x + 15 is fine for transmitting the two-letter word “no,” but what if the students want to share a longer secret? Here’s where the full power of algebra, geometry, and systems of linear equations comes into play.
Suppose Zeke wants to know how Art thinks he’ll do on tomorrow’s English test. Art converts his three-letter answer into the numbers 14, 59 and 82 and passes those to Zeke. The students agreed beforehand that when using Reed-Solomon codes of length 3, their private numbers are 2, 5 and 6, so Zeke puts the pieces together to reconstruct the points (2, 14), (5, 59) and (6, 82).
Now, there is no linear function that passes through these three points. But there is a unique quadratic function that does. And since every quadratic function can be written in the form y = Ax2 + Bx + C, the same general method can be applied. The only difference is the size of the system.
Plugging each point into y = Ax2 + Bx + C yields one equation, so the three points produce the following system of three equations:
(2, 14): 14 = 4A + 2B + C
(5, 59): 59 = 25A + 5B + C
(6, 82): 82 = 36A + 6B + C
A system of three equations with three unknowns requires a little more work to solve than a system of two equations with two unknowns, but the goal is the same: Cleverly combine pairs of equations to eliminate variables.
For example, if you subtract the first equation from the second, you get the new equation 45 = 21A + 3B. Likewise, if you subtract the second equation from the third, you get 23 = 11A + B. These algebraic manipulations produce a new system:
45 = 21A + 3B
23 = 11A + B
Now you have a “two-by-two” system: two equations with two unknowns. To solve it, you can multiply the second equation by −3 and add it to the first equation:
