This question explores an algorithm used by the FBI discussed on page 6 of the F

Question

This question explores an algorithm used by the FBI discussed on page 6 of the February/March 2016 issue of MAA Focus. Alice uses the following algorithm on an eight character message that Step 1 Map each character to a value where A, B, . .., Z correspond to 0,1,.. . , 25 respectively and # Step 2 Multiply each of these values by a weight wi where i is the position of the character in the eight consists only of the letters A to Z and the character # (representing a space). corresponds to 26. character message given by: 1 2 3 4 5 6 7 8 w2 4 57 8 10 11 13 Step 3 Add these products and find the remainder when divided by 27. This remainder is called the checksum. (It can be used to check if any characters are transmitted incorrectly.) For example, if the message is AACZBZDA, Alice computes 0(2) t. 0(4) t. 2(5) + 25(7) t-1 (8) + 25(10) .+ 3(11) t. 0(13) 476 and since 476 17 (mod 27), the checksum is 17 Let M be a message sent by Alice (a) Let N be a message formed by changing exactly one of the characters in M. Prove that the checksums of M and N are different (b) Let P be a message formed by changing exactly two of the characters in M. Prove that the checksums of M and P are not guaranteed to be different.

Explanation / Answer

a. Let M= ABCDEFGH, checksum = 0(2) + 1(4) + 2(5) +3(7) +4(8) +5(10)+ 6(11) +7(13) =274

Let N= IBCDEFGH , checksum = 8(2) + 1(4) + 2(5) + 3(7) + 4(8) + 5(10) + 6(11) + 7(13) = 290

This shows that the checksums are different for M & N.

b. Let M= IJKLMNOP, checksum = 8(2) + 9(4) + 10(5) +11(7) + 12(8) + 13(10) + 14(11) + 15(13) = 754

Let P = IJKLZNOG = 8(2) + 9(4) + 10 (5) + 11(7) + 25(8) + 13(10) + 14(11) + 7(13) = 754

Proved that checksums for M & P are not guaranteed to be different.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.