Secret Sharing with Linear Equations

Joan Funderbuk (funderbu@dimacs.rutgers.edu)



Lesson Description
This lesson uses linear equations to reveal a secret message. Each student is given some information about the "secret,,, which by itself reveals nothing about the secret. But when two students get together, they can use their information to reveal a piece of the secret.

Students will practice writing linear equations from two ordered pairs, and determining the y-intercept of the line from the equation. They will reveal a secret message from the teacher.

Prerequisites
Writing linear equations from two ordered pairs
Determining y-intercept from the equation

Preparation
Previous to the class, the teacher will write a secret message. Assign each letter an "index number" based on its location in the message. Next, each letter of the message is encoded" by changing it to a number (A = 0, B = 1, etc.). For each different number used, a linear equation is written, using the encoded number as it's y-intercept. Determine a minimum of two ordered pairs which satisfy the linear equation. At this point, each index number is associated with a minimum of two ordered pairs (equations are known only to the teacher).

Attached are equations and four ordered pairs for the message "Give me a fish, I'll eat for a day; teach me to fish, I'll eat for a lifetime." Y-intercepts of -26 to 25 are used (where Z = -1, Y = -2, etc.)

Activity Description
On the chalkboard or overhead are blank spaces representing the letters of the secret message. Beneath each blank is an index number, representing location in the message. Students are given a worksheet which contains one or several index numbers and a corresponding ordered pair (one ordered pair for each index number). Note that at least two students in the room obtain each index number, and each has a different ordered pair for that index number. Students are told that on the board or overhead is a secret message from the teacher, and that they will have to rely on each other to decode the message. Each student knows a piece of information about the message (the ordered pair they have for each index number they have), but that alone does not give them any information about the message.

Explain to the students that the message has been encoded, changing each letter to a number. (They may be told that A = 0, B = 1, etc., or be left to determine this for themselves.) The encoded number can be found by finding the y-intercept of the line associated with that index number. Each student has one point on the line, but since many lines pass through any given point, they must find another point in order to determine the line, and hence the y-intercept. They will have to work together to decode the message, as no student has all index numbers, and no student knows more than one ordered pair for their given index number.

Students' task is to find another student with their index number, and compare ordered pairs. If they are different, then together they can write an equation for that line, determine the y-intercept, and "decode" the number, back to a letter. That letter is placed in the blank space corresponding to that index number.

Possible Adaptations
If spaces and punctuation are not provided in the message, it will take most of the letters to be decoded. To save time or to make the activity simpler, spaces and/or punctuation can be provided. Note that students will try to figure out the message without having to get every single letter!

The activity can be made more difficult by using a variety of y-intercepts. Numbers larger than 25 can be used, as well as negatives. Without direct teacher instruction, students might naturally think of the alphabet circularly, assigning A = 26, B = 27, etc., and this can be extended to the negatives as well (-l comes right before 0, and Z comes right before A). This is an interesting segue into modular arithmetic: -1 = 25 mod 26).

Teaching Notes
To be sure my students completed the work I desired them to do (writing linear equations, given two points on the line) I required them to turn in the work for all index numbers they were given. Since in my class, four students had ordered pairs for each index number, it is possible that some other pair of students had already filled in the letter, but I asked students to complete theirs anyway, to serve as a check. They found and corrected each other's mistakes this way.

They also needed some encouragement to actually write the equation with the other person who shared their index number, rather than just exchange ordered pairs and work alone on writing equations. I found that several students had more than one index number in common (because of the way I set up their worksheets), so in the future I would be sure to scatter the index numbers better so they are forced to interact with more people.

They message I used "Give me a fish, I'll eat for a day; teach me to fish, I'll eat for a lifetime." took my Honors Algebra 2 students approximately 30 minutes to decode, where each student was given iO index numbers and corresponding ordered pairs. Their homework was to neatly write up the work and equations for all given index numbers, and write a brief essay describing and critiquing the lesson. Some of their comments are listed below.

Attachments
Cryptography Activity
Teacher Reference for Cryptography Activity

Student Comments
"I enjoyed this lesson because we had the chance to interact with other students."

"I thought the way all the numbers and letters matched up was vexy clever. After the work was all done, I was able to help uncode the secret message."

"Friday was a good day to have this activity since everyone thinks more of going home than learning. You kind of tricked us."

"I liked this lesson a lot, it wasn't like any other I've ever done. T had a goal to achieve and that made me look forward to doing each problem."

"I never thought of using equations to make a code. It made what we were learning really come alive."

"It was good to interact with people you don't normally talk to. After you write the equation y - y, = m(x - x-1) so many times, it gets easier to remember and use.

"I liked this activity because even if I was wrong, someone else could find my mistake, and not everyone would know it was me who made it."

"I actually enjoyed my school work, that's a surprise!"

"I quickly found out that if you didn't work with others on this assignment, nothing would be accomplished."

"Maybe if I ever write a will, Elll do it in this manner -- just to get the last laugh!"

References
This lesson was derived by Mrs. Joan Funderburk , loosely based on the presentation of Adi Shamir's secret sharing scheme using polynomial equations presented by Stephen Greenfield at DREI 1997, Rutgers University.