Differences between revisions 51 and 64 (spanning 13 versions)
⇤ ← Revision 51 as of 2019-08-09 03:57:31 →
Size: 29402
Editor: amy
Comment:
← Revision 64 as of 2019-08-09 16:45:57 → ⇥
Size: 29871
Editor: amy
Comment:
Deletions are marked like this. Additions are marked like this.
Line 5: Line 5:
This page was first created at Sage Days 103, 7-10 August 2019 by Sarah Arpin, Catalina Camacho-Navarro, Holly Paige Chaos, Amy Feaver, Eva Goedhart, Rebecca Lauren Miller, Alexis Newton, and Nandita Sahajpal.

We would also like to 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/		 This page was first created at Sage Days 103, 7-10 August 2019 by Sarah Arpin, Catalina Camacho-Navarro, Holly Paige Chaos, Amy Feaver, Eva Goedhart, Rebecca Lauren Miller, Alexis Newton, and Nandita Sahajpal. Text edited by Amy Feaver, Eva Goedhart, and Alexis Newton. This project was led by Amy Feaver.

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/
Line 18: Line 18:

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 ===
Line 20: Line 24:
The shift cipher is a classical cryptosystem that takes plaintext and shifts it through the alphabet by a given number of letters. -EG

For example, a shift of 2 would replace all A's with C's, all B's with D's, etc. When you reach the end of the alphabet, 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. -AF

=== Shift Cipher Encryption ===		 You can use this interact to encrypt a message with the a shift cipher.
Line 28: Line 28:
print "Put your message in between the provided quotes (with no additional quotes or apostrophes!), and select your desired shift: " print "Put your message inside the provided quotes (with no additional quotes or apostrophes!), and select your desired shift: "
Line 41: Line 41:

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. 		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.
Line 52: Line 53:
    decrypt = S.deciphering(shift_by,ciphertext)     decrypt = S.deciphering(shift_by%26,ciphertext)
Line 64: Line 65:


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 ===
Line 66: Line 72:
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. -AF

=== Affine Cipher Encryption ===		 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.
Line 72: Line 76:
print "Put your message in between the provided quotes (with no additional quotes or apostrophes!), and select your desired a,b: "
print "Notice that the only choices for a can be numbers that are relatively prime to 26"
print "This cipher will encipher the letters m of your message as a*m + b"		 print "Put your message in between the provided quotes (with no additional quotes or apostrophes!), and select your desired a and b: "
Line 87: Line 89:
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.
Line 90: Line 95:
print "Enter the encrypted text in quotes, and enter a guess for the a and the b:" print "Enter the encrypted text in quotes, and enter a guess for the a and b:"
Line 110: Line 115:
A simple cipher to encrypt messages in which each letter is assigned to another letter. Brute force or frequency analysis can be used to decrypt. -EG 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.
Line 217: Line 222:
Line 253: Line 257:
Line 283: Line 286:

 A Vigenère cipher is an example of a polyalpha- betic cipher. Using a secret code word, encrypt each letter by shifting it the corresponding letter in the code word.

 For our default text ‘ SECRETS HI’ we use the code word ‘CAT’.

We will breaks up the message into three-letter chunks, because our codeword is three letters. So SEC RET SHI.

The standard is that a=0 b=1, c=2,…etc. So S shift by C=2 letters to U. E will shift by A= 0 letters and remain at E. C will shift by T=19 letters to V, and so on.

 
To decrypt the message, simply undo the encryption process. The keyword must be known. Cryptography by Simon Rubinstein-Salzedo used as reference.- RLM

=== Vigenère Cipher Encryption ===
Line 284: Line 300:

Using a secret code word, encrypt each letter by shifting it the corresponding letter in the code word. -EG

=== Vigenère Cipher Encryption ===
Line 304: Line 316:

{{{#!sagecell
#This decrypts your message: Final 8/7/19. Written by Rebecca Lauren Miller, Holly Paige Chaos, Katherine Stange.		 by Holly Paige Chaos, Rebecca Lauren Miller, Katherine Stange

{{{#!sagecell
#Last edited 8/7/19 at 12:00pm
Line 358: Line 371:


=== Hill Cipher Encryption ===
Line 359: Line 375:

=== Hill Cipher Encryption ===
Line 425: Line 439:
by Holly Paige Chaos, Alexis Newton
Line 530: Line 545:
Named for the authors Rivest, Shamir, 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 Alicia and Bernadette share a message. -EG Named for the authors Rivest, Shamir, 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. -EG
Line 533: Line 548:
Line 536: Line 550:
{{{#!sagecell
#Last edited 8/8/19 at 11:42am		 Babette sent Alice an encrypted message. You , as Alice, will provide information so that you can read Babette's message.

{{{#!sagecell
#Last edited 8/9/19 at 11:16am
Line 539: Line 555:
go = True
while go:
    p = ZZ(raw_input("Provide a SECRET decently large prime (>10): "))
    if p.is_prime() and p>10:
        go = False
    elif p<=10:
        print "Larger prime, please."
    elif not p.is_prime():
        print "Prime, please."
go = True
while go:
    q = ZZ(raw_input("Provide a SECRET different decently large prime (>10): "))
    if q.is_prime() and p!=q and q>10:
        go = False
    elif p<=10:
        print "Larger prime, please."
    elif not p.is_prime():
        print "Prime, please."
    elif p == q:
        print "Different prime, please."
phi = (p-1)*(q-1)
print "So far, you can compute:"
print "N = pq =",p*q
print "phi(N) = (p-1)(q-1) =",phi.factor()
go = True
while go:
    e = ZZ(raw_input("Provide a PUBLIC exponent that is relatively prime to phi(N):"))
    if gcd(e,phi) == 1:
        go = False
@interact
def rsa():		 @interact
def rsa(p = input_box(default = 11,label = "p (>10): "), q = input_box(default = 23,label = "q (>10): "),e = input_box(default = 7,label = "e:")):
    print "************************************************************************************************"
    print "WARNINGS: p and q should be different primes, both larger than 10."
    print "e should be relatively prime to phi(pq). To check this, see the factorization of phi(pq) below."
    print "************************************************************************************************"
    print ""
    p = ZZ(p)
    q = ZZ(q)
    e = ZZ(e)
    phi = (p-1)*(q-1)
    print "phi(pq) = ",phi.factor()
    print ""
Line 601: Line 599:
Line 605: Line 602:

}}}


=== RSA With Digital Signatures ===

by Sarah Arpin, Eva Goedhart

{{{#!sagecell
#Last edited 8/8/19 at 1:30pm
print "Hi, Alice! Let's set up RSA with a digital signature to Babette."

go = True
while go:
    p = ZZ(raw_input("Provide a SECRET decently large prime (>10): "))
    if p.is_prime() and p>10:
        go = False
    elif p<=10:
        print "Larger prime, please."
    elif not p.is_prime():
        print "Prime, please."
go = True
while go:
    q = ZZ(raw_input("Provide a SECRET different decently large prime (>10): "))
    if q.is_prime() and p!=q and q>10:
        go = False
    elif p<=10:
        print "Larger prime, please."
    elif not p.is_prime():
        print "Prime, please."
    elif p == q:
        print "Different prime, please."		 #Last edited 8/8/19 at 12:30pm
print "Hi, Babette! Let's send a message to Alice using RSA."
p = next_prime(100)
q = next_prime(p)
Line 638: Line 607:
print "So far, you can compute:"
print "N = pq =",p*q
print "phi(N) = (p-1)(q-1) =",phi.factor()
go = True
while go:
    e = ZZ(raw_input("Provide a PUBLIC exponent that is relatively prime to phi(N):"))
    if gcd(e,phi) == 1:
        go = False		 e = 13
N = p*q
R = IntegerModRing(phi)
d = (e^(R(e).multiplicative_order()-1)).mod(phi)
print "Alice's public key is: N =",N,", e =",e,"."
message = raw_input("Type a message for Alice:")
ascii_secret = []
for char in message:
    ascii_secret.append(ord(char))
print "We turn these characters into ascii:"
print ascii_secret
print ""
print "Then we encode them by raising each ascii number to the e-th power modulo N."
encrypted_ascii = []
for ascii in ascii_secret:
    encrypted_ascii.append(power_mod(ascii,e,N))
print encrypted_ascii
print ""
Line 648: Line 627:
    N = p*q
    R = IntegerModRing(phi)
    d = (e^(R(e).multiplicative_order()-1)).mod(phi)
    print "Alice's public key is: N = pq =",N,", e =",e,"."
    print "Alice's private key is: p =",p,", q = ",q,", d = ",d,", where the decryption key d is the inverse of e modulo phi(N)."
    secret_message_from_babette = "Hi Dr. Strange!"
    ascii_secret = []
    for char in secret_message_from_babette:
        ascii_secret.append(ord(char))
    encrypted_ascii = []
    for ascii in ascii_secret:
        encrypted_ascii.append(power_mod(ascii,e,N))		     print "Alice receives our secret and uses her private key to decrypt the message."
Line 663: Line 631:
    print "Babette's encrypted message to you is: ", encrypted_ascii
    print ""
    print "To decrypt, we raise each one of these to the ",d,", modulo ",N,":"
Line 671: Line 636:
    print "Going from ascii to letters, we figure out the secret is: "     print "Going from ascii to letters, she figures out your message was: "
Line 673: Line 638:

}}}


=== RSA With Digital Signatures ===
by Sarah Arpin, Eva Goedhart

{{{#!sagecell

Sage Interactions - Cryptography

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

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

Contents

  1. Sage Interactions - Cryptography
    1. Shift Cipher
      1. Shift Cipher Encryption
      2. Shift Cipher Decryption
    2. Affine Cipher
      1. Affine Cipher Encryption
      2. Affine Cipher Decryption
    3. Substitution Cipher
    4. Playfair Cipher
    5. Frequency Analysis Tools
      1. Letter Frequency Counter
      2. Frequency Analysis Decryption Guesser
    6. Vigenère Cipher
      1. Vigenère Cipher Encryption
      2. Vigenère Cipher Decryption
    7. One-Time Pad
    8. Hill Cipher
      1. Hill Cipher Encryption
      2. Hill Cipher Decryption
    9. RSA
      1. RSA, From Alice's Perspective
      2. RSA, From Babette's Perspective
      3. RSA With Digital Signatures
    10. Diffe-Hellman Key Exchange

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 the 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 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. -EF

Frequency Analysis Tools

Frequency analysis is a technique for breaking a substitution cipher that is based on the frequencies that letters appear (in large chunks of text) 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. -AF

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 text that matched the frequencies of letters in English relatively well, to make this message easier to decrypt. -AF

Frequency Analysis Decryption Guesser

by Rebecca Lauren Miller, Katherine Stange

This interact prints suggested translation of the input text, by matching frequencies of letters in the input to letter frequencies in the English language. With the output you will see that some letters were substituted in correctly, 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. -AF

Vigenère Cipher

  • A Vigenère cipher is an example of a polyalpha- betic cipher. Using a secret code word, encrypt each letter by shifting it the corresponding letter in the code word. For our default text ‘ SECRETS HI’ we use the code word ‘CAT’.

We will breaks up the message into three-letter chunks, because our codeword is three letters. So SEC RET SHI.

The standard is that a=0 b=1, c=2,…etc. So S shift by C=2 letters to U. E will shift by A= 0 letters and remain at E. C will shift by T=19 letters to V, and so on.

To decrypt the message, simply undo the encryption process. The keyword must be known. Cryptography by Simon Rubinstein-Salzedo used as reference.- RLM

Vigenère Cipher Encryption

by Holly Paige Chaos, Rebecca Lauren Miller, Katherine Stange

Vigenère Cipher Decryption

by Holly Paige Chaos, Rebecca Lauren Miller, Katherine Stange

One-Time Pad

by Sarah Arpin, Alexis Newton

Hill Cipher

Hill Cipher Encryption

by Holly Paige Chaos, Alexis Newton

Hill Cipher Decryption

by Holly Paige Chaos, Alexis Newton

RSA

Named for the authors Rivest, Shamir, 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. -EG

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

Diffe-Hellman Key Exchange

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