CRYPTO.sagews

Cryptography

Cryptography is the study of codes. The basic idea is that we have a message we want to send to a friend. However, we don't want anyone but the our friend to see our message. So we hide it via some clever method.

Shifty business

Let's do some cryptography. Enter a message in the text box below, then use the slider to encrypt it! This is an example of a Caesar cipher, where we take a message and shift all the letters to the left or right by a fixed amount (for example a shift by 1 would send $a$ to $b$, $b$ to $c$ etc.).

Example

Can you create a secret message and pass it to the person next to you to decode?

Try to intercept someone elses message and decoding it.

@interact
def _(
        message=input_box(default='sage is cool',type=str,label='Message'),
        key=slider([0..25],0,label='Shift by:',width=35),
        method=selector(["Encrypt","Decrypt"],label="Method",buttons=True)
    ):
    S = ShiftCryptosystem(AlphabeticStrings())
    k = key
    #m = ''.join([str(S.encoding(s)) if str(S.encoding(s)) is not  "" else s for s in message])
    m = S.encoding(message)
    print "Message   = %s" % m
    print "Key       = %s" % k
    if method is "Encrypt":
        #print "Encrypted = %s" % ''.join([str(S.enciphering(k,S.encoding(s))) if str(S.encoding(s)) is not  "" else s for s in m])
        print "Encrypted = %s" % S.enciphering(k,S.encoding(message))
    if method is "Decrypt":
        #print "Decrypted = %s" % ''.join([str(S.deciphering(k,S.encoding(s))) if str(S.encoding(s)) is not  "" else s for s in m])
        print "Decrypted = %s" % S.deciphering(k,S.encoding(message))

Passphrase plz

A slightly better cryptosystem is the Vigenere cipher. This uses system uses a passphrase as the key. The pass phrase tells us how much to shift each letter by. For example if the passphrase is ABC then we shift the first letter by $0$, the second letter by $1$, and the third letter by $3$. If there are still more letters, than we simply repeat. The next letter will be shifted by $0$, the one following by $1$, and so on.

Example

This system is also already in Sage, so we can run pretty much the same application as before.

@interact
def _(
        message=input_box(default='sage is cool',type=str,label='Message'),
        key=input_box(default='catz',type=str,label='Passphrase'),
        method=selector(["Encrypt","Decrypt"],label="Method",buttons=True)
    ):
    S = VigenereCryptosystem(AlphabeticStrings(),len(key))
    k = S.encoding(key)
    m = S.encoding(message)
    print "Message   = %s" % m
    print "Key       = %s" % k
    if method is "Encrypt":
        print "Encrypted = %s" % S.enciphering(k,m)
    if method is "Decrypt":
        print "Decrypted = %s" % S.deciphering(k,m)

Subs

The next crypto system we could try is a substitution cipher. This substitutes letters via a predetermined map.

For example, suppose we declare the key to be $a\mapsto e$, $e\mapsto c$, $c\mapsto a$, and all other letters remain the same.

What is the encryption of hello there?

Example

Sage makes it easy to try out substitution ciphers.

@interact
def _(
        message=input_box(default='sage is cool',type=str,label='Message'),
        nky=input_box(default='ABCDEFGHIJKLMNOPQRSTUVWXYZ',type=str,label='Map From',width=42,readonly=True),
        key=input_box(default='ABCDEFGHIJKLMNOPQRSTUVWXYZ',type=str,label='Map To',width=42),
        method=selector(["Encrypt","Decrypt"],label="Method",buttons=True)
    ):
    S = SubstitutionCryptosystem(AlphabeticStrings())
    k = S.encoding(key)
    m = S.encoding(message)
    o = S.enciphering(k,m)
    print "Message   = %s" % m
    print "Key       = %s" % k
    if method is "Encrypt":
        print "Encrypted = %s" % S.enciphering(k,m)
    if method is "Decrypt":
        print "Decrypted = %s" % S.deciphering(k,m)

A modern approach

An example of a more modern cryptosystem is R.S.A. which stands for Rivest, Shamir and Adleman. The reason why RSA works well is because it is based off the problem of factoring. Factoring is easy to understand but hard to solve efficiently on a computer.

Recall factoring means finding the prime factors. For example $12$ factors into $2^2 \cdot 3$. The factorization of $17$ is just $17$ because it is already prime.

Side note:

The public keys used in RSA are of a very special form. They are always of the form $m = pq$ for two large primes $p$ and $q$.

Example

Evaluate the following cell to see how Sage factors integers.

factor(12218951709966191815704374298795806512376838433049)

Lag?

Did you notice a slight pause? That is because factoring an integer can be very difficult. To see this, try to find a factor of $$12218951709966191815704374298795806512376838433048.$$ It probably didn't take you too long to notice that $2$ divides this number because it is even (notice the last digit).

To see how much easier it is to factor this number, try factoring it in sage below.

factor(12218951709966191815704374298795806512376838433048)

Form matters!

Did you notice how much faster it was? The numbers used in RSA are of a special form. They are always the product of two large primes, i.e. $m = pq$ for some primes $p$ and $q$. The $m$ is sometimes referred to as the modulus. The special form makes factoring take longer. In the following we will mostly consider numbers of this form.

A first try

Let's say we have a number $n$. If we want to find a factor of $n$, one thing you might try is testing if a smaller number divides $n$. So you check: Does $2$ divide $n$? Does $3$ divide $n$? Does $4$ divide $n$? ...

This will eventually find a factor. In fact, you will have to try at most $\sqrt{n}$ different numbers (can you see why?). So this method will factor $n$ in about $\sqrt{n}$ steps.

I live at 45-45

What is the maximum number of steps it take to factor a number with $45$ digits?

A number with $45$ digits is at least as large as $10^{44}$ (notice $10^1$ is the smallest number with $2$ digits, $10^2$ is the smallest number with $3$ digits, ...)

So factoring should take at least $$\sqrt{10^{44}} = \left(10^{44}\right)^{1/2} = 10^{22}$$ number of steps.

Till the end of the universe

How long would it take a computer to do this? Remember computers are fast. A modern day PC processor runs at about $4$ gigahertz, or about $4000000000$ operations per second. So a fast computer could perform one of our steps in about $\frac{1}{10000000000} = 10^{-10}$ seconds (I added a zero).

So $10^{22}$ steps at $10^{-10}$ seconds each is a total of $10^{22}\times 10^{-10} = 10^{12}$ seconds.

How long is this? We can have Sage convert the units. Make sure to take a guess before evaluating the next cell!

@interact
def _(
    n=slider([1..100],10,label="Number of digits"),
    u=selector(['second','minute','hour','day','week','month','year','millenium'],label="Units of time")
    ):
    conv = {"second":1, "minute":60, "hour":60*60, "day":60*60*24, "week":60*60*24*7, "month":60*60*24*7, "year":60*60*24*365, "millenium":60*60*24*365*1000}
    print "Time to factor %s digit number on a single machine: roughly %f %ss" % (n, (10^(n/2 - 10) / conv[u]), u )

Same but with a picture

We can also plot the same information in Sage. Note that this plot represents the time it would take our niave algorithm to factor an integer $n$ with some number of digits.

plot(10^(x/2 - 10),(x,1,40),axes_labels=["The number of digits in $n$","Days"],title="Time to factor $n$ with niave approach")

But we just did this...

So you might notice we just factored a $50$ digit number with Sage earlier in a few seconds. This is because Sage uses a very clever algorithm to factor large numbers.

Currently, the fastest algorithm for large numbers (over $100$ digits) is the number field sieve. It's much faster than our method above.

In the real world

Common implementations of RSA use key sizes of $2048$ bits. This means the modulus is about $2^{2048}$, i.e. $2048$ bits, or equivalently about $600$ digits.

##!!!WARNING!!!

We have NOT made a claim about security. The larger the key size generally means the more computational resources it will take to factor. However, with the computational power of the cloud and giant clusters of computers, some numbers are within reach of direct factorizing.

###A recent crisis

Web security commonly uses RSA encryption to keep your credit cards and personal information safe when you send it to stores and buisnesses over the internet. You can even see what kind of encryption a particular site is using from your browser. Most web servers will use key sizes from $1024$ to $2048$ bits. However, a recent security bug named "FREAK" allowed adverseries to downgrade to a very insecure $512$ bit key.

An RSA modulus of $512$ bits was factored in 1999. It took $6$ months with advanced hardware at the time. In 2015, with relatively small cost (probably less than $$1000$) you can have a cluster of computers in the cloud factor a $512$ bit modulus in less than a day.

For more on the current state of factoring, see RSA Factoring Challenge

Beyond factoring

Often RSA keys are broken through methods besides factoring. Suppose two people have RSA keys given by $$M = 20741579857257684926979740247743706928783897708345333800893$$ and $$N = 721889008479921001060900078102867246663074108349982730322849.$$

Normally these would be hard to factor. But there was a mistake in generating these keys. Remember all RSA moduli are the product of two primes. These keys happen to share a prime. Since we can compute the greatest common divisor very quickly, we can quickly break both keys:

M = 20741579857257684926979740247743706928783897708345333800893
N = 721889008479921001060900078102867246663074108349982730322849
d = gcd(20741579857257684926979740247743706928783897708345333800893,
   721889008479921001060900078102867246663074108349982730322849)
print "M = %s x %s" % (d,M/d)
print "N = %s x %s" % (d,N/d)

︠507a9720-818f-4913-8520-e147d02f1fd8︠