Announcements

Values for In-Class Activities

Thank you, University of Toronto - Mississauga Primes Pages, for the primes!

  1. EC Activity
    • p =1332297598440044874827085558802491743757193798159
    • A = 297190522446607939568481567949428902921613329152
    • B =173245649450172891208247283053495198538671808088
    • x =1089473557631435284577962539738532515920566082499
    • y =127912481829969033206777085249718746721365418785
  2. RSA Practice Activity
    • 22953686867719691230002707821868552601124472329079
    • 30762542250301270692051460539586166927291732754961
    • 29927402397991286489627837734179186385188296382227
    • 46484729803540183101830167875623788794533441216779
    • 95647806479275528135733781266203904794419563064407
    • 64495327731887693539738558691066839103388567300449
    • 58645563317564309847334478714939069495243200674793
    • 48705091355238882778842909230056712140813460157899
    • 15452417011775787851951047309563159388840946309807
    • 53542885039615245271174355315623704334284773568199
  3. DHKE Activity: \(p=4669523849932130508876392554713407521319117239637943224980015676156491\)
  4. Other Activity: \(p=1078834318169\)

\begin{tabular}{|l|l|} \hline ID & Key $K($ID$)$\\ \hline 2 & 14303931085 \\ \hline 4 & 56782759477 \\ \hline 6 & 127536359613 \\ \hline 8 & 226564731541 \\ \hline 10 & 353867875309 \\ \hline 12 & 509445790965 \\ \hline 14 & 693298478557 \\ \hline 16 & 905425938133 \\ \hline 18 & 1145828169741 \\ \hline 20 & 1414505173429 \\ \hline 22 & 1711456949245 \\ \hline 24 & 2036683497237 \\ \hline 26 & 2390184817453 \\ \hline 28 & 2771960909941 \\ \hline 30 & 3182011774749 \\ \hline 32 & 3620337411925 \\ \hline 34 & 4086937821517 \\ \hline 36 & 4581813003573 \\ \hline 38 & 5104962958141 \\ \hline 40 & 5656387685269 \\ \hline 42 & 6236087185005 \\ \hline 44 & 6844061457397 \\ \hline 46 & 7480310502493 \\ \hline 48 & 8144834320341 \\ \hline 50 & 8837632910989 \\ \hline 52 & 9558706274485 \\ \hline 54 & 10308054410877 \\ \hline 56 & 11085677320213 \\ \hline 58 & 11891575002541 \\ \hline 60 & 12725747457909 \\ \hline 62 & 13588194686365 \\ \hline 64 & 14478916687957 \\ \hline 66 & 15397913462733 \\ \hline 68 & 16345185010741 \\ \hline 70 & 17320731332029 \\ \hline \end{tabular}

Due Dates, Exam Dates, Etc.

Problem set due dates will be added as problem sets arise. The plan is to have more problem sets at the start of the semester, so that you can work on your projects more as the semester progresses.

Getting in touch with your instructor...

Useful Resources

LaTeX Fun

You can exchange the commands in the box below for your own and render it on demand. It's kind of fun! Press the Render! button when you're ready.

Let’s roll that beautiful math footage!

\({}\)

SageMath and Tiny SageMath Programs

SageMath is free open source mathematics software that can do some pretty amazing calculations, and the software has a ton of useful libraries and built-in functions. You can download and install Sage for use on your computer through a terminal window or Juypter notebook, or you can use Sage online through CoCalc or SageMathCell. The SageMath language is built on Python, so if you know a bit of Python then you can often logic your way around SageMath. I will often use SageMathCell in class for quick examples and calculations but I prefer to use SageMath in a Juypter notebook on my computer so you might see both during the class meetings.

For really quick things, here's a SageCell box that you can try out! Change the input area to be whatever code you need, press Evaluate, and ta da!

You may prefer a different language or different software and that's great! Go ahead and use whatever you wish that will complete the same operations. SageMath has a lot of built-in programs and functions that make the programming easier, but there's something to be said for figuring out how to get the same results yourself and for learning how to do the same computations in your preferred programming language.

A few good SageMath commands to know:

  • mod(x,n) returns the remainder of \(x\) modulo \(n\)
  • factor(n) factors \(n\) ... but this can time out if \(n\) is big and hard enough to factor
  • inverse_mod(x,n) calculates the inverse of \(x\) modulo \(n\)
  • power_mod(x,i,n) gives \(x^i\) modulo \(n\)
  • euler_phi(n) produces \(\varphi(n)\), the Euler totient of \(n\)
  • g=mod(primitive_root(p),p) instructs Sage to select a primitive root modulo \(p\) and call it \(g\)
  • p= random_prime(a, True) will return a random prime between 2 and \(a\)
  • CRT_list([a1,a2,...,ak],[m1,m2,...,mk]) will solve a system of linear congruences, \(\{x \equiv a_1 \textrm{ mod } m_i \mid 1 \leq i \leq k\}\), provided that the moduli are pairwise relatively prime
  • Mod(x,p).nth_root(n,all=True) asks Sage to produce a list of all remainders modulo \(p\) that, when squared, produce \(x\)
  • Mod(x,p).sqrt(all=True) asks for all square roots of \(x\) modulo \(p\)

Tiny SageMath Programs

I've gathered several small bits of code that have been helpful in previous iterations of Cryptology. You can copy the code and paste it into the SageCell here, or on the SageMathCell site, to test it out. This is not organized in a reasonable way, and much of it is not explained ... explanations and elaborations will happen in class, so take good notes. Worst of all, some of this needs to be updated to match SageMath's current standards!

Checking For Solutions of a Quadratic Congruence

To figure out all solutions to \((x-3)(x+2) == 0\) modulo 15, one way to do this is to let \(x\) range from 1 to 14 (all possible remainders) and calculate each factor (i.e., calculate \(x - 3\) and \(x + 2\)). Then calculate the product modulo 15 and check if you get 0. Here's a tiny program to get that done:

for x in [0..14]:
    i = Mod(x-3,15)
    j = Mod(x+2,15)
    k = Mod(i*j,15)
    print (x,k)

There are faster, more clever and conservative ways to achieve the same result, though, and you might spend some time optimizing your approach.

Fermat's Factorization Scheme

You can do these calculations by hand if your calculator has enough memory and stores enough digits, but if \(p\) and \(q\) are far apart then you have to check a lot of things .... note that this program uses \(n = 23360947609\), and it also requires that you have an idea of how many steps you'll need before you can actually find \(t, s\). If you get fancy, you can write the same output using a while loop so that the loop runs as long as "fake \(s\)" is not an integer.

for i in [0..5]:
    # Define the "potential t"
    ft = ceil(sqrt(23360947609))+i
    # "potential s" = sq rt of (ft^2 - n)
    fs = N(sqrt(ft^2-23360947609))
    # print the potentials, as well as potential p and q
    print (i, ft, fs, ft+fs,ft-fs)
    # look on the list for the integers

Marcello Cierro and Christian Sumano wrote a while loop that produces the final answer:

n=1433811615146881
i=0
while (True):
    t = ceil(sqrt(n))+i
    s = sqrt(t^2-n)
    print ("i", ":", i, ", t:", t , ", s:", s)
    i += 1
    if (s.is_integer() == True):
        break

Calculating Powers

This next tiny program runs through the powers of \(g\) (modulo \(p\)) until it gets to \(h\), and the prints out the exponent. If \(g\) is not a primitive root modulo \(p\), the program may just time out ... and if you change \(g\), \(h\), and/or \(p\) to be very large then Sage may not be able to finish the computation.

g = 2
h = 38679
p = 56509
h1 = h%p
# Now run through the powers of g to see if any equal h1
# Print n if g^n is congruent to h1 modulo p
for n in range(p-1):
    if Mod(g^n,p)==h1:
        print n
To get the picture of the discrete log function modulo \(p\), check out this tiny bit of code that produces the graph: 
p=53
R = Integers(p)
a = R.multiplicative_generator()
v = sorted([(a^n, n) for n in range(p-1)])
G = plot(point(v,pointsize=50,rgbcolor=(0,0,1)))
H = plot(line(v,rgbcolor=(0.5,0.5,0.5)))
G + H

And then, we also consider the different powers of an element modulo a prime. Here's a tiny program that will show you the order of each element in \(\mathbb{Z}/p\mathbb{Z}^*\).

# A program to print out the powers of all of the values modulo 23
# i is the base
for i in [1..22]:
    print ("The powers of ",i," are ...")
    # j is the exponent, it should start cycling at 1
    j = 1
    # as long as i^j is not congruent to 1, increase the exponent j
    while (i^j)%23 > 1:
        j1 = j + 1
        j = j1
        # once i^j is congruent to 1, print out j
        print (j, " - ", (i^j)%23)

A Serviceable Program For Decrypting Your ElGamal Messages

We practice ElGamal encryption on a worksheet, where I had a secret \(b\) and a public \(B\). Students send me a 5-letter message and I have to do some decryption ... Here's how I do it (the header is a link to a SageCell.)!

Polynomial Code!

Here's a bit of code (the header is a link to a SageCell) to calculate the polynomials on the Polynomials: Keeping it safe! worksheet -- thank your classmate, Keith Allen, for writing this for you! You can adjust this to make something more generalized, too ...