Differences between revisions 121 and 122
Revision 121 as of 2019-08-09 22:04:04
Size: 61191
Editor: amy
Comment:
Revision 122 as of 2019-08-09 22:18:51
Size: 61970
Editor: amy
Comment:
Deletions are marked like this. Additions are marked like this.
Line 80: Line 80:
print "Put your message in between the provided quotes (with no additional quotes or apostrophes!), and select your desired a and b: " pretty_print(html("<h>Put your message in between the provided quotes (with no additional quotes or apostrophes!), and select your desired a and b:<h>"))
Line 100: Line 100:
print "Enter the encrypted text in quotes, and enter a guess for the a and b:" pretty_print(html("<h>Enter the encrypted text in quotes, and enter a guess for the a and b:<h>"))
Line 124: Line 124:
print "Select your letter substitutions and enter your message in quotes." pretty_print(html("<h>Select your letter substitutions and enter your message inside the quotes.<h>"))
Line 359: Line 359:
print('Enter your message and the key to construct you polybius square. Warning: both the message and the key must be in quotes.') pretty_print(html("<h>Enter your message and the key to construct you polybius square. Warning: both the message and the key must be in quotes.<h>"))
Line 473: Line 473:
print 'Enter your ciphertext and a guess for the key to construct you polybius square.'
print
'Warning: both the message and the key must be in quotes.'
pretty_print(html("<h>Enter your ciphertext and a guess for the key to construct you polybius square. Warning: both the message and the key must be in quotes.<h>"))
Line 500: Line 499:
print "This interact prints a bar graph showing the distribution of letters in the input text. Warning: the smaller the input text the less accurate the distribution will be. Letters that do not occur will not appear in the graph." pretty_print(html("<h>This interact prints a bar graph showing the distribution of letters in the input text. Warning: the smaller the input text the less accurate the distribution will be. Letters that do not occur will not appear in the graph.<h>"))
Line 504: Line 503:
def frequencyAnalysis(text = input_box('"Nyllappppunz tf uhtl pz Dlllnilya Klbjl aol Aybl Lhaly vm aol Avbwll. Olhy fl, olhy fl! Kll kll kll. H olhk vm aolzl spnly jbiz jhyyfpun aol aypwwf avthohdrz hyl jvtpun mv aoll. Ahrl zolsalyz pu aol avtiz. Ahttf yhu av aol vaoly avduzwlvwsl huk hhykchyrz. Doha pz oly LAH? Oly LAH wslhzl! Avps, iypun fvby mvvk jbwz huk vps huk il zdpma. Aol dvtlu huk aol jopsk Vjjvapvu JPPP zovbsk wpjr ihtivv ha Hapapzvapun. Zll.Uhuuh Db Zohjho z puuly uvvksl jbwz: uva ubbaaf zlzhtl uvapvuz."', width = 150)): def frequencyAnalysis(text = input_box('"Nyllappppunz tf uhtl pz Dlllnilya Klbjl aol Aybl Lhaly vm aol Avbwll. Olhy fl, olhy fl! Kll kll kll. H olhk vm aolzl spnly jbiz jhyyfpun aol aypwwf avthohdrz hyl jvtpun mv aoll. Ahrl zolsalyz pu aol avtiz. Ahttf yhu av aol vaoly avduzwlvwsl huk hhykchyrz. Doha pz oly LAH? Oly LAH wslhzl! Avps, iypun fvby mvvk jbwz huk vps huk il zdpma. Aol dvtlu huk aol jopsk Vjjvapvu JPPP zovbsk wpjr ihtivv ha Hapapzvapun. Zll.Uhuuh Db Zohjho z puuly uvvksl jbwz: uva ubbaaf zlzhtl uvapvuz."', width = 150,label = "Message:")):
Line 536: Line 535:
print "Warning: the shorter the input text is, the less accurate the distribution will be." pretty_print(html("<h>Warning: the shorter the input text is, the less accurate the distribution will be.<h>"))
Line 571: Line 570:
print "Put your message and codeword inside the quotes: " pretty_print(html("<h>"Put your message and codeword inside the quotes:<h>"))
Line 573: Line 572:
def vigenere_cipher(message = input_box(default ="'secrets hi'", width = 50), code_word = input_box(default="'cat'", width = 50)): def vigenere_cipher(message = input_box(default ="'secrets hi'",label="Message:"), code_word = input_box(default="'cat'",label="Key:")):
Line 592: Line 591:
print "Put your encrypted message and codeword inside the quotes: " pretty_print(html("<h>Put your encrypted message and codeword inside the quotes:<h>"))
Line 594: Line 593:
def vigenere_cipher(message = input_box(default ="'UEVTEMUHB'", width = 50), code_word = input_box(default="'cat'", width = 50)): def vigenere_cipher(message = input_box(default ="'UEVTEMUHB'",label = "Message:"), code_word = input_box(default="'cat'", label = "Key:")):
Line 619: Line 618:
print "Enter your message to be encrypted via one-time pad in the Plain Text box below:"
@interact
def one_time_pad(plain_text = input_box("'message'",label="Plain Text:")):
pretty_print(html("<h>Enter your message to be encrypted via one-time pad in the Plain Text box below:<h>"))
@interact
def one_time_pad(plain_text = input_box("'message'",label="Message:")):
Line 656: Line 655:
print "Please select the size of your key:"
print " "
pretty_print(html("<h>Please select the size of your key:<h>"))
Line 663: Line 661:
        def two_matrix(message=input_box(default='"Alexis smells"'), a=input_box(default=1), b=input_box(default=3), c=input_box(default=3), d=input_box(default=4)):         def two_matrix(message=input_box(default='"Alexis smells"',label = "Message:"), a=input_box(default=1), b=input_box(default=3), c=input_box(default=3), d=input_box(default=4)):
Line 679: Line 677:
        print "Please input your message (in quotes) and the numbers in your square matrix key:"         pretty_print(html("<h>Please input your message (in quotes) and the numbers in your square matrix key:<h>"))
Line 681: Line 679:
        def three_matrix(message=input_box(default='"Alexis smells"'), a=input_box(default=1), b=input_box(default=2), c=input_box(default=3), d=input_box(default=5), e=input_box(default=2), f=input_box(default=6), g=input_box(default=7), h=input_box(default=9), i=input_box(default=9)):         def three_matrix(message=input_box(default='"Alexis smells"',label = "Message:"), a=input_box(default=1), b=input_box(default=2), c=input_box(default=3), d=input_box(default=5), e=input_box(default=2), f=input_box(default=6), g=input_box(default=7), h=input_box(default=9), i=input_box(default=9)):
Line 697: Line 695:
        print "Please input your message (in quotes) and the numbers in your square matrix key:"         pretty_print(html("<h>Please input your message (in quotes) and the numbers in your square matrix key:<h>"))
Line 699: Line 697:
        def four_matrix(message=input_box(default='"Alexis smells"'), a=input_box(default=17), b=input_box(default=8), c=input_box(default=7), d=input_box(default=10), e=input_box(default=0), f=input_box(default=17), g=input_box(default=5), h=input_box(default=8), i=input_box(default=18), j=input_box(default=12), k=input_box(default=6), l=input_box(default=17), m=input_box(default=0), n=input_box(default=15), o=input_box(default=0), p=input_box(default=17)):         def four_matrix(message=input_box(default='"Alexis smells"',label="Message:"), a=input_box(default=17), b=input_box(default=8), c=input_box(default=7), d=input_box(default=10), e=input_box(default=0), f=input_box(default=17), g=input_box(default=5), h=input_box(default=8), i=input_box(default=18), j=input_box(default=12), k=input_box(default=6), l=input_box(default=17), m=input_box(default=0), n=input_box(default=15), o=input_box(default=0), p=input_box(default=17)):
Line 728: Line 726:
print "Please select the size of your key:"
print "
"
pretty_print(html("<h>Please select the size of your key:<h>")) "
Line 735: Line 732:
        def two_decrypt(coded_text=input_box(default='"HSVAKSCYLENB"'), a=input_box(default=1), b=input_box(default=3), c=input_box(default=3), d=input_box(default=4)):         def two_decrypt(coded_text=input_box(default='"HSVAKSCYLENB"',label="Message:"), a=input_box(default=1), b=input_box(default=3), c=input_box(default=3), d=input_box(default=4)):
Line 763: Line 760:
        print "Please input your encrypted message and your key:"         pretty_print(html("<h>Please input your encrypted message and your key:<h>"))
Line 765: Line 762:
        def three_decrypt(coded_text=input_box(default='"FGYHQTCSGKYB"'), a=input_box(default=1), b=input_box(default=2), c=input_box(default=3), d=input_box(default=5), e=input_box(default=2), f=input_box(default=6), g=input_box(default=7), h=input_box(default=9), i=input_box(default=9)):         def three_decrypt(coded_text=input_box(default='"FGYHQTCSGKYB"',label = "Message:"), a=input_box(default=1), b=input_box(default=2), c=input_box(default=3), d=input_box(default=5), e=input_box(default=2), f=input_box(default=6), g=input_box(default=7), h=input_box(default=9), i=input_box(default=9)):
Line 793: Line 790:
            print "Please input your encrypted message (In quotes) and your key:"             pretty_print(html("<h>Please input your encrypted message (In quotes) and your key:<h>"))
Line 795: Line 792:
            def four_decrypt(coded_text=input_box(default='"UIBBSMUGGXTX"'), a=input_box(default=17), b=input_box(default=8), c=input_box(default=7), d=input_box(default=10), e=input_box(default=0), f=input_box(default=17), g=input_box(default=5), h=input_box(default=8), i=input_box(default=18), j=input_box(default=12), k=input_box(default=6), l=input_box(default=17), m=input_box(default=0), n=input_box(default=15), o=input_box(default=0), p=input_box(default=17)):             def four_decrypt(coded_text=input_box(default='"UIBBSMUGGXTX"',label="Message:"), a=input_box(default=17), b=input_box(default=8), c=input_box(default=7), d=input_box(default=10), e=input_box(default=0), f=input_box(default=17), g=input_box(default=5), h=input_box(default=8), i=input_box(default=18), j=input_box(default=12), k=input_box(default=6), l=input_box(default=17), m=input_box(default=0), n=input_box(default=15), o=input_box(default=0), p=input_box(default=17)):
Line 839: Line 836:
print "This tool creates a multiplication table modulo 𝑛." pretty_print(html("<h>This tool creates a multiplication table modulo 𝑛.<h>"))
Line 857: Line 854:
print "Input your modulus, 𝑛, and an integer, 𝑎. The output will be an arrow diagram picture of 𝑥↦𝑎𝑥 on the ring ℤ/𝑛ℤ, i.e. the elements modulo 𝑛." pretty_print(html("<h>Input your modulus, 𝑛, and an integer, 𝑎. The output will be an arrow diagram picture of 𝑥↦𝑎𝑥 on the ring ℤ/𝑛ℤ, i.e. the elements modulo 𝑛.<h>"))
Line 886: Line 883:
print('This will evaluate x=a^b (mod m). Choose your base (a), exponent (b), and modulus (m). These should all be positive integers.') pretty_print(html("<h>This will evaluate x=a^b (mod m). Choose your base (a), exponent (b), and modulus (m). These should all be positive integers.<h>'))
Line 948: Line 945:
print('This will solve for the exponent, b, in x=a^b (mod m) assuming an integer solution exists. Choose your base (a), modulus (m), and solution (x). These should all be positive integers.') pretty_print(html("<h>This will solve for the exponent, b, in x=a^b (mod m) assuming an integer solution exists. Choose your base (a), modulus (m), and solution (x). These should all be positive integers.<h>"))
Line 966: Line 963:
                print "This process took",i,"steps to determine that","b="+str(i)
                break
                print "This process took",i+1,"steps to determine that b="+str(i),"by evaluating",str(a)+"^i for i=0,...,"+str(i)+"."
                print
                print "NOTE: Without restricting the size of b, there is not a unique solution for b. However, the solution above is the small possible solution."
Line 971: Line 969:
            print "*********** ERROR: No integer solution for b.***********"             print "*********** ERROR: This process took",m,"steps to determine that there is no integer solution for b.***********"

Sage Interactions - Cryptography

This page was first created at Sage Days 103, 7-9 August 2019 by Sarah Arpin, Catalina Camacho-Navarro, Holly Paige Chaos, Amy Feaver, Eva Goedhart, Sara Lapan, Rebecca Lauren Miller, Alexis Newton, and Nandita Sahajpal. Text edited by Holly Paige Chaos, Amy Feaver, Eva Goedhart, and Alexis Newton. This project was led by Amy Feaver and Eva Goedhart.

We acknowledge Katherine Stange, who allowed us to use code from her cryptography course as a starting point for many of these interacts. Dr. Stange's original code and course page can be found at http://crypto.katestange.net/

If you have cryptography-related interactions that you are interested in adding to this page, please do so. You can also contact Amy Feaver at [email protected]

goto interact main page

Shift Cipher

The shift cipher is a classical cryptosystem that takes plaintext and shifts it through the alphabet by a given number of letters. For example, a shift of 2 would replace all A's with C's, all B's with D's, etc. When the end of the alphabet is reached, the letters are shifted cyclically back to the beginning. Thus, a shift of 2 would replace Y's with A's and Z's with B's.

Shift Cipher Encryption

by Sarah Arpin, Alexis Newton

You can use this interact to encrypt a message with a shift cipher.

Shift Cipher Decryption

by Sarah Arpin, Alexis Newton

If you know that your message was encrypted using a shift cipher, you can use the known shift value to decrypt. If this is not known, brute force can be used to get 26 possible decrypted messages. The chi-squared function ranks the brute force results by likelihood according to letter frequency.

Affine Cipher

An affine cipher combines the idea of a shift cipher with a multiplicative cipher. In this particular example, we map consecutive letters of the alphabet to consecutive numbers, starting with A=0 (you can also do this cipher differently, and starting with A=1). The user selects two values, a and b. The value a is the multiplier and must be relatively prime to 26 in order to guarantee that each letter is encoded uniquely. The value b is the addend. Each letter's value is multiplied by a, and the product is added to b. This is then replaced with a new letter, corresponding to the result modulo 26.

Affine Cipher Encryption

by Sarah Arpin, Alexis Newton

You can use this interact to encrypt a message with the affine cipher. Notice that the only choices for a can be numbers that are relatively prime to 26. This cipher will encipher a letter m of your message as a*m + b.

Affine Cipher Decryption

by Sarah Arpin, Alexis Newton

If you know that your message was encrypted using an affine cipher, you can use the known a and b values to decrypt. If these are not known, brute force can be used to get a list of possible decrypted messages. The chi-squared function ranks these results by likelihood according to letter frequency.

Substitution Cipher

by Catalina Camacho-Navarro

A substitution cipher encrypts messages by assigning each letter of the alphabet to another letter. For instance, if A is assigned to F, then all A's in the original message will be substituted with F's in the encrypted message. Brute force or frequency analysis can be used to decrypt a message encrypted with a substitution cipher.

Playfair Cipher

by Catalina Camacho-Navarro

Based on code from Alasdair McAndrew at trac.sagemath.org/ticket/8559.

A playfair cipher is a special type of substitution cipher in which the plaintext is broken up into two-letter digraphs with some restrictions. Those digraphs are encrypted using a Polybius square, (i.e. a 5x5 grid in which each letter of the alphabet is its own entry with the exception of ij which are placed together). The positions of the letters in the digraph determine how the digraph is encrypted.

Playfair Encryption

Use this interact to encrypt a message using the playfair cipher.

Playfair Decryption

Frequency Analysis Tools

Frequency analysis is a technique for breaking a substitution cipher that utilizes the frequencies of letters appearing in the English language. For example, E is the most common letter in the English language, so if a piece of encrypted text had many instances of the letter Q, you would guess that Q had been substituted in for E. The next two interacts create a couple of basic tools that could be useful in cracking a substitution cipher.

Letter Frequency Counter

by Rebecca Lauren Miller, Katherine Stange

This tool looks at the percentage of appearances of each letter in the input text and plots these percentages. The encrypted input text is a bit strange, but was constructed by Amy Feaver to give a short block of text that matched the frequencies of letters in the English language relatively well, to make this message easier to decrypt.

Frequency Analysis Decryption Guesser

by Rebecca Lauren Miller, Katherine Stange

This interact prints a suggested translation of the input text by matching frequencies of letters in the input to frequencies of letters in the English language. With the output you will see that some letters were substituted incorrectly, and others were not. Usually frequency analysis requires additional work and some trial and error to discover the original message, especially if the input text is not long enough.

Vigenère Cipher

A Vigenère cipher is an example of a polyalphabetic cipher. Using a secret codeword as the key, the Vigenère encrypts each letter of a message by shifting it according to the corresponding letter in the key. For example, we will use the key "CAT" to encrypt our default text "secrets hi". To do this the message is first broken up into three-letter chunks, because the key is three letters long, to be "SEC RET SHI". Next each letter of the chunk is shifted by the value of the corresponding letter in the key. The standard shifts are A=0, B=1, C=2, etc. So in our example, S shifts by C=2 letters to U, E shifts by A=0 letters and remains at E, and C shifts by T=19 letters to V. Thus "SECRETSHI" becomes UEVTEMUHB when encrypted. To decrypt the message, simply use the keyword to undo the encryption process. Cryptography by Simon Rubinstein-Salzedo was used as reference for this interact.

Vigenère Cipher Encryption

by Holly Paige Chaos, Rebecca Lauren Miller, Katherine Stange

Use this interact to encrypt a message using the Vigenère Cipher.

Vigenère Cipher Decryption

by Holly Paige Chaos, Rebecca Lauren Miller, Katherine Stange

If you used the Vigenère Cipher to encrypt a message, you can use this interact to decrypt by inputting your key and encrypted text.

One-Time Pad

by Sarah Arpin, Alexis Newton

One-time pad is an encryption method that cannot be cracked. It requires a single-use shared key (known as a one-time pad) the length of the message or longer. In this method, every letter is first converted to numbers using the standard A=0, B=1, C=2, etc. Then each character in the message is multiplied modulo 26 by the number in the corresponding position in the key. This is then converted back to letters to produce the encrypted text.

Hill Cipher

The Hill cipher requires some basic knowledge of Linear Algebra. In this encryption method, an invertible n x n matrix of integers modulo 26 is used as the key. The message is first converted to numbers and spit into chunks size n. These chunks are then converted to n x 1 vectors and multiplied by the key modulo 26 to produce 1 x n vectors. The integers from these vectors are converted back letters to produce the encrypted text.

Hill Cipher Encryption

by Holly Paige Chaos, Alexis Newton

Use this interact to encrypt a message with the Hill cipher. Be sure to use an invertible matrix so that your message can be decrypted!

Hill Cipher Decryption

by Holly Paige Chaos, Alexis Newton

Use this interact to decrypt messages encrypted by the Hill cipher. Remember that this only works if the message was encrypted using an invertible matrix as the key!

Modular Arithmetic (Preliminaries for RSA, Diffie-Hellman, El Gamal)

This section gives visual representations of the modular arithmetic necessary for RSA, Diffie-Hellman, and El Gamal.

Modular Arithmetic Multiplication Table

by Rebecca Lauren Miller, Kate Stange

Given a positive integer n, this prints the multiplication mod n. Each entry in this table corresponds to the product of the row number by the column number, modulo n.

Modular Exponentiation

by Rebecca Lauren Miller, Kate Stange

Given a modulus n and a nonnegative exponent a, this displays a graph where each integer between 0 and n-1 is mapped to its a-th power, mod n.

Discrete Log Problem

by Sara Lapan

The discrete logarithm, log(x) with base a, is an integer b such that ab = x. Computing logarithms is computationally difficult, and there are no efficient algorithms known for the worst case scenarios. However, the discrete exponentiation is comparatively simple (for instance, it can be done efficiently using squaring). This asymmetry in complexity has been exploited in constructing cryptographic systems. Typically, it is much easier to solve for x in x = ab (mod m) when a, b, and m are known, than it is to solve for b when x, a, and m are known.

Solving for x

Interact to find x when a, b, and m are known:

Solving for b

Interact to find b when a, x, and m are known:

RSA

Named for the authors Rivest, Shamir, and Aldeman, RSA uses exponentiation and modular arithmetic to encrypt and decrypt messages between two parties. Each of those parties has their own secret and public key. To see how it works, following along while Alice and Babette share a message.

RSA, From Alice's Perspective

by Sarah Arpin, Eva Goedhart

Babette sent Alice an encrypted message. You, as Alice, will provide information so that you can read Babette's message.

RSA, From Babette's Perspective

by Sarah Arpin, Eva Goedhart

RSA With Digital Signatures

by Sarah Arpin, Eva Goedhart

interact/cryptography (last edited 2019-11-14 19:53:51 by chapoton)