<Text-field style="Heading 1" layout="Heading 1">Problem 1</Text-field>

LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2I1EhRic=

Homework 7

Run these first. This will load the number theory package and the programs mess2num and num2mess.

QygtSSV3aXRoRzYiNiNJKm51bXRoZW9yeUc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkdGJSIiIj5JKW1lc3MybnVtR0YlZio2I0kiYUdGJTYkSSNsbEdGJUkibkdGJUYlRiVDJT44JC1JKGNvbnZlcnRHRik2JDkkSSZieXRlc0dGJT44JS1JJHN1bUdGJTYkKiYmRjY2I0kiaUdGJUYrKSIkRyIsJkZERishIiJGK0YrL0ZEO0YrLUklbm9wc0dGKTYjRjZPRj1GJUYlRiVGSD5JKW51bTJtZXNzR0YlZio2I0YzNidGMkkibUdGJUZESSJiR0YlSSJqR0YlRiVGJUMnPkY9Rjo+OCgsJi1JJmZsb29yR0YoNiMqJi1JJGxvZ0dGKDYjRj1GKy1GW282I0ZGRkhGK0YrRis+RjY3Iy1JJHNlcUdGKTYkIiIhLzgmO0YrRlo/KEZmb0YrRitGWkkldHJ1ZUdGKUMkPiZGNjYjRmZvLUkkbW9kR0YlNiRGPUZGPkY9LCZGPSNGK0ZGRl5wI0ZIRkZPLUY4NiRGNkY7RiVGJUYlRkg=

a) Convince me that 781 is a pseudoprime base 5.

b) Convince me that 781 is a strong pseudoprime base 5.

c) Find a witness for 781, thus showing that 781 is composite.

d) The number 29341 is a Carmichael number. Choose two random bases, and show that this number is a pseudoprime for each base.

LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2I1EhRic=

<Text-field style="Heading 1" layout="Heading 1">Problem 2</Text-field>

Following the book problem 3.8, factor the following number N, knowing that M = (p-1)*(q-1). You can solve a quadratic in Maple using the solve command. Syntax is: LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYmLUkjbWlHRiQ2JVEmc29sdmVGJy8lJ2l0YWxpY0dRJXRydWVGJy8lLG1hdGh2YXJpYW50R1EnaXRhbGljRictSShtZmVuY2VkR0YkNiQtRiM2Ly1JJW1zdXBHRiQ2JS1GLDYlUSJ4RidGL0YyLUYjNiQtSSNtbkdGJDYkUSIyRicvRjNRJ25vcm1hbEYnRkYvJTFzdXBlcnNjcmlwdHNoaWZ0R1EiMEYnLUkjbW9HRiQ2LVEoJm1pbnVzO0YnRkYvJSZmZW5jZUdRJmZhbHNlRicvJSpzZXBhcmF0b3JHRlEvJSlzdHJldGNoeUdGUS8lKnN5bW1ldHJpY0dGUS8lKGxhcmdlb3BHRlEvJS5tb3ZhYmxlbGltaXRzR0ZRLyUnYWNjZW50R0ZRLyUnbHNwYWNlR1EsMC4yMjIyMjIyZW1GJy8lJ3JzcGFjZUdGam4tRkM2JFEiM0YnRkYtRkw2LVEnJnNkb3Q7RidGRkZPRlJGVEZWRlhGWkZmbi9GaW5RJjAuMGVtRicvRlxvRmRvRj0tRkw2LVEiK0YnRkZGT0ZSRlRGVkZYRlpGZm5GaG5GW29GQi1GTDYtUSI9RidGRkZPRlJGVEZWRlhGWkZmbi9GaW5RLDAuMjc3Nzc3OGVtRicvRlxvRl1wLUZDNiRRIjBGJ0ZGLUZMNi1RIixGJ0ZGRk8vRlNGMUZURlZGWEZaRmZuRmNvL0Zcb1EsMC4zMzMzMzMzZW1GJy1GTDYtUSJ+RidGRkZPRlJGVEZWRlhGWkZmbkZjb0Zlb0Y9RkZGRi1GLDYjUSFGJ0ZG.

LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYmLUkjbWlHRiQ2JVEiTkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JI21vR0YkNi1RIn5GJy9GM1Enbm9ybWFsRicvJSZmZW5jZUdRJmZhbHNlRicvJSpzZXBhcmF0b3JHRj0vJSlzdHJldGNoeUdGPS8lKnN5bW1ldHJpY0dGPS8lKGxhcmdlb3BHRj0vJS5tb3ZhYmxlbGltaXRzR0Y9LyUnYWNjZW50R0Y9LyUnbHNwYWNlR1EmMC4wZW1GJy8lJ3JzcGFjZUdGTC1GNjYtUSomY29sb25lcTtGJ0Y5RjtGPkZARkJGREZGRkgvRktRLDAuMjc3Nzc3OGVtRicvRk5GUy1JI21uR0YkNiRRY3c2MjUxOTg2MDI3NDg4NjkyMTQ3NTMxNzQ5MDc1MTE0MTQ3MzAzMDM1OTE5MTEzODM2MDA0NTk0NjQzMzY1NTY1ODYzNDgxNDIxMDg5MzMxNzQxMTA2MzkzNTI5NjE0MDkxNDk2OTg0ODY4MDkzOTA4MDIwMDk3NTYxMDYwNzQ1MTg5NTI4OTgxNTA4NTQyMDAzNzg0Nzc1NDQ2OTM2NzQ2OTE1ODY5NTc2Njg2OTcyMjM4NDU5NTMzMTkzNzU1MDMyOTg3MjA5OUYnRjk=

LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2JVEiTUYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JI21vR0YkNi1RKiZjb2xvbmVxO0YnL0YzUSdub3JtYWxGJy8lJmZlbmNlR1EmZmFsc2VGJy8lKnNlcGFyYXRvckdGPS8lKXN0cmV0Y2h5R0Y9LyUqc3ltbWV0cmljR0Y9LyUobGFyZ2VvcEdGPS8lLm1vdmFibGVsaW1pdHNHRj0vJSdhY2NlbnRHRj0vJSdsc3BhY2VHUSwwLjI3Nzc3NzhlbUYnLyUncnNwYWNlR0ZMLUkjbW5HRiQ2JFFjdzYyNTE5ODYwMjc0ODg2OTIxNDc1MzE3NDkwNzUxMTQxNDczMDMwMzU5MTkxMTM4MzYwMDQ1OTQ2NDMzNjU1NjU4NjM0ODE0MjEwODkzMzE3NDExMDYzOTM1Mjk2MTQwOTE0OTUzNjQ4OTIyMzUxNDA0MjY2NDgzNDIzMzg3MDM4MTYzNTAwNTY1MDQwNzc2MDI2OTQxODA1NDk0NDA2OTg5Njc4NDQzODkzMzU5MDMxMjA2NTkxMzE3NDQ3ODAwMjI0MDg4MDY0RidGOQ==

LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2I1EhRic=

JSFH

<Text-field style="Heading 1" layout="Heading 1">Problem 3</Text-field>

3) Now we will follow book problem 3.9. For the following N, Eve has somehow figured out that the following pairs are valid encryption/decryption pairs. Use this information to factor N.

LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2JVEiTkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JI21vR0YkNi1RKiZjb2xvbmVxO0YnL0YzUSdub3JtYWxGJy8lJmZlbmNlR1EmZmFsc2VGJy8lKnNlcGFyYXRvckdGPS8lKXN0cmV0Y2h5R0Y9LyUqc3ltbWV0cmljR0Y9LyUobGFyZ2VvcEdGPS8lLm1vdmFibGVsaW1pdHNHRj0vJSdhY2NlbnRHRj0vJSdsc3BhY2VHUSwwLjI3Nzc3NzhlbUYnLyUncnNwYWNlR0ZMLUkjbW5HRiQ2JFFidzYwMjcyMTc0NTU4OTY3NzI2NTQxNjY1MjU0MTQ3NTkyNzg1ODc5OTAzNTc1MjIxODAwNDY2MzQwMjk1OTA1NTY2Nzk0OTYzMTIyMDM2NDgxMTE1ODIzMzI1NDQ1NzcyOTM4NTAxNjMxNTY2NzIyOTIzMjA5NzUxODUxNzU0MDA1OTU0MTMzNDkzNzgwMDcwNzMyNjg2NTE4ODQyODI4MjA1NzY1ODY4MDY3MzEwOTM5Mzg2ODU2Mzk0MjI2MDA2NTIwNzUxODlGJ0Y5

LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYuLUkjbWlHRiQ2JVEjZTFGJy8lJ2l0YWxpY0dRJXRydWVGJy8lLG1hdGh2YXJpYW50R1EnaXRhbGljRictSSNtb0dGJDYtUSJ+RicvRjNRJ25vcm1hbEYnLyUmZmVuY2VHUSZmYWxzZUYnLyUqc2VwYXJhdG9yR0Y9LyUpc3RyZXRjaHlHRj0vJSpzeW1tZXRyaWNHRj0vJShsYXJnZW9wR0Y9LyUubW92YWJsZWxpbWl0c0dGPS8lJ2FjY2VudEdGPS8lJ2xzcGFjZUdRJjAuMGVtRicvJSdyc3BhY2VHRkwtRjY2LVEqJmNvbG9uZXE7RidGOUY7Rj5GQEZCRkRGRkZIL0ZLUSwwLjI3Nzc3NzhlbUYnL0ZORlNGNS1JI21uR0YkNiRRJDEwMUYnRjktRjY2LVEiO0YnRjlGOy9GP0YxRkBGQkZERkZGSEZKRlQtSSdtc3BhY2VHRiQ2Ji8lJ2hlaWdodEdRJjAuMGV4RicvJSZ3aWR0aEdRJjAuMGVtRicvJSZkZXB0aEdGXG8vJSpsaW5lYnJlYWtHUShuZXdsaW5lRidGNS1GLDYlUSNkMUYnRi9GMkY1Rk8tRlY2JFFidzQ1OTUwMDczNjczNjY4NDY0Nzg5MTkwMzQyMjcwOTM3MDc0MzgzNjg4ODY0Mjc4MDA2Mjk2MTIwODE5NjUwNzc4NjQ1NjY0OTU0NDIzODUxOTM5Nzg2MDk5NTk3MjcyNDM4MjI1NzYwOTQ2OTI3NDA5NzY1OTUwMTYxMTExNjYyNjAzMjY3MDU4MzQ1MDgyODYyODQ2NjMxMDAzODY0MDUwNTk0NzY1MTQ1MTI0NjU3NzIwMjMyODgxNTIwMTEwMDU5NzQ1MjFGJ0Y5

LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYvLUkjbWlHRiQ2JVEjZTJGJy8lJ2l0YWxpY0dRJXRydWVGJy8lLG1hdGh2YXJpYW50R1EnaXRhbGljRictSSNtb0dGJDYtUSJ+RicvRjNRJ25vcm1hbEYnLyUmZmVuY2VHUSZmYWxzZUYnLyUqc2VwYXJhdG9yR0Y9LyUpc3RyZXRjaHlHRj0vJSpzeW1tZXRyaWNHRj0vJShsYXJnZW9wR0Y9LyUubW92YWJsZWxpbWl0c0dGPS8lJ2FjY2VudEdGPS8lJ2xzcGFjZUdRJjAuMGVtRicvJSdyc3BhY2VHRkwtRjY2LVEqJmNvbG9uZXE7RidGOUY7Rj5GQEZCRkRGRkZIL0ZLUSwwLjI3Nzc3NzhlbUYnL0ZORlNGNS1JI21uR0YkNiRRJTEwMDFGJ0Y5LUY2Ni1RIjtGJ0Y5RjsvRj9GMUZARkJGREZGRkhGSkZURjUtSSdtc3BhY2VHRiQ2Ji8lJ2hlaWdodEdRJjAuMGV4RicvJSZ3aWR0aEdRJjAuMGVtRicvJSZkZXB0aEdGXG8vJSpsaW5lYnJlYWtHUShuZXdsaW5lRidGNS1GLDYlUSNkMkYnRi9GMkY1Rk8tRlY2JFFidzM3OTkzNzQ4Mzk4MzEwMzI1MTIyNjY4MTA3MjU5ODcxMTc2NzEzNTA1NjUwMzE0NjQxNDUyODA3OTE4Nzk3NjE1MDMyNTg5MTQwODY0MTU1NDI4NjU1ODYyNDkzNzg4OTM1MjI3OTY2NDYwOTIzODkxMDY3MjkzMzUyMzMzNDc2NTE1Mjg3NDc3Mzk3ODAzMTgyOTQ3OTQzNDkxNjY3NTUwNzQwODgyMjAxNzQ1NTIxNTA2NjUxMjkzNzk5MTYzNjE4NDI4NjFGJ0Y5

LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYuLUkjbWlHRiQ2JVEjZTNGJy8lJ2l0YWxpY0dRJXRydWVGJy8lLG1hdGh2YXJpYW50R1EnaXRhbGljRictSSNtb0dGJDYtUSJ+RicvRjNRJ25vcm1hbEYnLyUmZmVuY2VHUSZmYWxzZUYnLyUqc2VwYXJhdG9yR0Y9LyUpc3RyZXRjaHlHRj0vJSpzeW1tZXRyaWNHRj0vJShsYXJnZW9wR0Y9LyUubW92YWJsZWxpbWl0c0dGPS8lJ2FjY2VudEdGPS8lJ2xzcGFjZUdRJjAuMGVtRicvJSdyc3BhY2VHRkwtRjY2LVEqJmNvbG9uZXE7RidGOUY7Rj5GQEZCRkRGRkZIL0ZLUSwwLjI3Nzc3NzhlbUYnL0ZORlNGNS1JI21uR0YkNiRRJjEwMDAxRidGOS1GNjYtUSI7RidGOUY7L0Y/RjFGQEZCRkRGRkZIRkpGVEY1LUknbXNwYWNlR0YkNiYvJSdoZWlnaHRHUSYwLjBleEYnLyUmd2lkdGhHUSYwLjBlbUYnLyUmZGVwdGhHRlxvLyUqbGluZWJyZWFrR1EobmV3bGluZUYnRjUtRiw2JVEjZDNGJ0YvRjJGTy1GVjYkUWF3Nzg3MDc1ODkyMTUwOTAzNDE4MjkyMzE4OTg3MjY4ODM0OTAwMTAxNTMwNTM5MzQyNzc5ODEyNDIzMDIyMjI0NDc5ODk0MjI4OTUwOTAxMzUzMjM3MzI4ODk3NDMyMDUxMzcxMDQ1NjUxNzI5MDM1Nzg2MzY3NzgxNjU3MTA2MzYzMDQ1MDY0OTIxODI4MTQxODc0OTg3NTI4NDE1NDMwMDc0ODgyNTIzNTk2MDU3NjgwMTA3OTY4MjI1MjI4MzM5MTg0MzYxRidGOQ==

JSFH

LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2I1EhRic=

<Text-field style="Heading 1" layout="Heading 1">Problem 4</Text-field>

4) The following is my public key for RSA. Use it to send me a message. As you did with ElGamal, you need to take a bit of text, convert it into a number using mess2num, encrypt the number using RSA, and then give me the number. I should be able to take your answer and decrypt it into the original piece of text.

PkkiTkc2IiJjd3ROSzUkbzdHSik0P0IoUiNbbGJIVWQpXCRSaiI+dF4oZiZHaCNcWSg+OVQ7JFE2JmUnUltdUHkieipHLCRcJ2ZfXzROYTdlPmJtNFEhUkxkZDU+dHJpSjskKlEpUj1nMDwzQmJbQnVDaCtiYVZkOg==

QyQ+SSJlRzYiIioqeWNNNyIiIg==

JSFH

<Text-field style="Heading 1" layout="Heading 1">Problem 5</Text-field>

5) Now the other way. You picked the following for your code:

QyQ+SSJwRzYiIl9xTCtxKXpSKnkhMz12anZLIls9SFImXFVAYSd5bTFta0MnUlMmUkVGbElfKjNtZEsjW1lXaWJVaiIiIg==

PkkicUc2IiJfcS5TMzIuIjNUMUFEOU9PSF0mKmVbKXBMPSUpPSNHWGlhIm9TWSZHMXpJPURqX003NjZLTS1zJikq

QyQ+SSJlRzYiIiVAViIiIg==

QyQ+SSJORzYiKiZJInBHRiUiIiJJInFHRiVGKEYo

I used your public key to encode my super secret message, and I sent to you the following. Determine the original message. Again, you will get a number that can be decoded using num2mess.

PkkiY0c2IiJidzI4QXJWXz1cRXYkZiV5Y3MxQFlHUnduMlg6Knl0NXowJlFVKTRlK1BqXUZpdzxmakhERzFiJD1OW0IrMEsqZW5OKiopbyVbaGNgRmd6WDhMPXgnKmU2YHNORjQ+NE1MXFZtJzRDW2wnRyhmIg==

JSFH