Discrete Mathematics for ECE 14:332:202 Spring 2004 Recitation 3: Modular Arithmetic and Basic Cryptography Introduction: Modular arithmetic plays an important part in cryptography. Modular arithmetic can be thought of as circular arithmetic, or clock arithmetic in that multiples of the base are equivalent, as noon and midnight appear the same on a clock. We will use the notation ~n to be an equivalence relationship between numbers in a given base in. For example, 1 ~5 6. This can be stated “1 is equivalent to 6 in modulo 5”. In general, a ~n b if and only if n | (a-b). In the previous example, 1 ~5 6 because 5 | (6-1). A simple application of modular arithmetic to cryptography is the shift cipher. A typical modular scheme is a base 26 (letters in the alphabet), such that when a number is added to the message, the letters are shifted around. For example, shift of 1 would change an A into a B, and a Z into and A. (Each letter must be assigned a number, such that A = 0 and Z = 25 in mod 26). More complicated schemes use modular multiplication as well, which follows logically as p*m (mod b). A more difficult task lies in modular division, finding a number m-1 (mod b) which when multiplied through: p*m*m-1 (mod b) reverses the multiplication by m. The requirement for a multiplicative inverse to exist is for gcd(m,b) = 1; m and b cannot share any common factors. This can be found through trial and error as a number such that m*m-1 = 1 (mod b). The simplest way for our purposes of this lab is through the extended Euclidean algorithm. Take gcd(m,b), and remember that the requirement is that gcd(m,b) = 1. This means that an equation can be written of the form s*m + t*b = 1, where s and t are integers that satisfy the equation. The simple answer to the multiplicative inverse problem is that m-1 = s. An affine cipher combines modular addition and modular multiplication to encrypt a message (let’s consider a single number at this point). Consider a number p (plaintext), and its corresponding ciphertext, c. We will encrypt a number by the following formula: c = p*m + s (mod b) where m is a multiplier and s is a shift. In the case of the alphabet, b = 26. For example, consider m = 3, and s = 12. If we wish to encrypt the letter O (p = 14), we apply the formula mod 26. c = 14*3 + 12 (mod 26) = 54 (mod 26) = 2 (mod 26) Now, to decrypt we need to find the multiplicative inverse of m = 3. We would use the backwards Euclidean algorithm for gcd(3,26), and find 9*3 + (-1)*26 = 1 = s*m + t*b, thus s = 9 = m-1. When working with an affine cipher, it is important to make sure all calculations are done in the modular base. So, to decrypt, we first subtract c-s (mod 26) = 2 – 12 = -10 (mod 26) = 16 (mod 26) Now, we multiply by our inverse: 16*9 (mod 26) = 144 (mod 26) = 14 (mod 26) = 0 To summarize: -- To encrypt: c = p*m + s; To decrypt: p = (c – s (mod b) )*m-1 (mod b)Exercise: 1. Create a function isequiv.m that takes three input variables: two numbers a and b, and the base n, and returns a 1 if the two numbers are equivalent in the given base, and a zero if they are not. function iseq = isequiv(a,b,n) 2. Create a function that finds a-1 mod n, and returns a 0 if a-1 does not exist. function a_inv = modinv(a,n) This function modinv.m is given on the webpage, download into your J:/discmat directory 3. Implement a simple shift cipher in modulo 26 Use the functions given on the webpage: str_mod26.m, mod26_str.m, described below function ciphertext = shiftcipher(message,s) An example of how this would run from your matlab command line: >> message = ‘THISMESSAGEISENCRYPTED’; >> ciphertext = shiftcipher(message,5) ciphertext = YMNXRJXXFLJNXJSHWDUYJI >> plaintext = shiftcipher(ciphertext,-5) plaintext = THISMESSAGEISENCRYPTED 4. Consider a cipher of the form p*m + s = c (mod 26), where m is a multiplier and s is a shift. Implement this scheme as a MATLAB function. Use the function modinv.m, as well as str_mod26 and mod26_str function ciphertext = affencrypt(message,m,s) where m is your multiplier and s is your shift, [m,s] comprising your key. Likewise, create a function to decrypt the ciphertext function message = affdecrypt(ciphertext,m,s) Now, create a script msencdec.m that will use the message ‘DISCRETEMATHEXAMCOMINGVERYSOON’ and encrypt, display the ciphertext to the screen, and then decrypt, and display the decrypted message to the screen. Additional Excercises: 1. On a sheet of notebook paper, perform the following calculation a. d = gcd(1180,482) b. find the numbers m and n such that d = m*1180 + n*482 2. List all the numbers m in mod 26 that can be used as multipliers in the affine cipher as described above. 3. Take a look at the supplied function modinv.m, and note your observations.How this is all done in MATLAB: A little guidance on doing modular arithmetic in MATLAB …. Apart from the built-in MATLAB mod function, we have provided a few useful functions to help in these cryptography exercises: str_mod26.m: Takes in a string argument (a vector of letters is what it actually is), and returns a vector of integers corresponding to the letters converted to mod 26. String arguments are entered with single quotes. Do not use spaces for your ciphers! Ex. >> message = ‘meetmeatnoon’; Note on vector indices: in this example, message(1) = m, and message(4) = t. The string is just a vector of letters! >> pt = str_mod26(message) pt = 12 4 4 19 12 4 0 19 13 14 14 13 mod26_str.m: As you can expect, the reverse of the previous conversion Ex. >> message = mod26_str(pt) message = MEETMEATNOON modinv.m: An implementation of the extended Euclidean algorithm to find the multiplicative inverse of a number a mod n. Syntax: a_inv = modinv(a,n) Ex. >> a_inv = modinv(3,26) a_inv = 9 as in the example above. MATLAB Examples: For the case of the shift cipher, say we had a message, message = ‘abcd’, and wish to create a shift of 4. >> message = 'abcxyz'; >> pt = str_mod26(message) pt = 0 1 2 23 24 25 hint: MATLAB can perform operations such as mod on entire vectors: >> ct = mod(pt+4,26)ct = 4 5 6 1 2 3 >> mod26_str(ct) ans = EFGBCD Now, to decrypt: >> pt = mod(ct-4,26) pt = 0 1 2 23 24 25 >> message = mod26_str(pt) message = ABCXYZ This follows