Instructor: Elizabeth Wilcox
Class: MWF 11:45 EST - 12:35 EST
Office Hours: MW 1 - 3, Th. 10 - 12, F. immediately after class
Course Document Folder (LakerApps log-in required) with Project Information
This describes some of the practicalities of the course this semester.
Students will ...
You may or may not know that I appreciate \(\LaTeX\). 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.
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. 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!
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.
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.
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.
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 integersMarcello 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):
breakThis 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 np=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]:
# 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 i, j
# undo takes in the ciphertext from students and produces the number string
def undo(cOne,cTwo):
#b = 19, p = 433026689 -- could be generalized easy
#first calculate multiplicative inverse of cOne^b
inv=inverse_mod(power_mod(cOne,19,433026689),433026689)
#now do the multiplication with cTwo
m=mod(inv*cTwo,433026689)
#make Sage think it's a number
m=N(m)
#now start up a list to hold the plaintext numbers
#which were used as coefficients in a base-27 expansion
quots=[]
i=6
while i>0:
q=floor(m/(27^(i-1)))
quots.append(q)
h=m-q*27^(i-1)
m=h
i=i-1
return quots
#this tells sage the alphabet I'm using
letters = [
" ", "A", "B", "C", "D", "E",
"F", "G", "H", "I", "J",
"K", "L", "M", "N", "O",
"P", "Q", "R", "S", "T",
"U", "V", "W", "X", "Y", "Z"
]
#now we have to turn the list of plaintext numbers
#into alphabet numbers. Yuck.
def revert(list):
string = ""
for i in list:
if type(i) == sage.rings.integer.Integer or type(i) == int:
string += letters[i]
else:
string += i
return string
Dumb Version: Really clumsy, but you can see the job getting done here.
#Set the parameters, let a for loop do the calculations, and sort yourself visually
p = 23
g = 5
h = 21
n = floor(sqrt(p-1))+1
ginv = inverse_mod(g,p)
for i in [0..n]:
powerg = power_mod(g,i,p)
hpowerg = Mod(h*ginv^(i*n),p)
print (i, powerg, hpowerg)This isn't going to work for large values of \(n\), which is common for large primes \(p\). Well, it works but the printout is gross. I didn't bother with sorting, etc -- that's something you can program in.
The following program I swiped off of Github, and adapted to work in Sage using the built-in Sage math functions. I'm not super familiar with Github so I'm not sure how to tell the author of the original code. Here's the site that I got the program from, at least, and I accessed it on Oct. 8, 2018.
Be aware that this program isn't perfect -- the answer is not always the smallest value of \(x\) that solves the discrete log problem. For example, this program tells us that the solution to \(5029^x\) congruent to 10724 modulo 11251 is \(x = 103\), but the smallest positive value of \(x\) would be less than 10!
def bsgs(g, h, p):
n = floor(sqrt(p-1))+1 # phi(p) is p-1 if p is prime
# Store hashmap of g^{1...m} (mod p). Baby step.
tbl = {power_mod(g, i, p):i for i in range(n)}
# Precompute via Fermat's Little Theorem
d = inverse_mod(g,p)
c = power_mod(d, n, p)
# Search for an equivalence in the table. Giant step.
for j in range(N):
y = Mod(h * power_mod(c, j, p), p)
if y in tbl: return j * n + tbl[y]
# Solution not found
return NoneOk, this is rough. I can't figure out how to get Sage to treat the coefficients like integers, so there's some nasty hijinks. But also, I don't know how to evaluate polynomials in Sage. You'd think it was just \(p(2)\) or whatever, but it's not ... and the documentation doesn't use English.
So here's how I make it work. I use the program below to calculate the personal polynomials \(p_i(x)\) for each employee that approaches the safe and the master polynomial \(p(x)\), as well as \(p(0)\). Then I copy \(p(0)\) over to a different SageCell and mod out by the prime. To use the program, you have to enter the list of employee numbers, then the list of safe keys, and then the prime modulus.
def poly(empl,safekey,p):
R=PolynomialRing(IntegerModRing(p),"x")
noemplys=len(empl)
polylist=[]
masterpoly=0
#mastercoefflist=[]
guts=[]
for i in [1..noemplys]:
realperson=empl[i-1]
poly=1
coeff=1
j=1
while j < noemplys+1:
ephemperson=empl[j-1]
if j != i:
coeff=coeff*(realperson-ephemperson)
poly=poly*(x-ephemperson)
j=j+1
#each personal poly has denom coeff, coeff
#so here we find the inverse to put it in the num
invcoeff=inverse_mod(coeff,p)
#now we build the personal poly,
#multiplying poly with the coeff just calculated
polynew=invcoeff*poly
#here's where the shit happens
#to build the master poly, we need the safe keys
#but the safe keys have a weird type
#so we do stupid crap, invertible, to fix the type
t=inverse_mod(safekey[i-1],p)
s=inverse_mod(t,p)
#so now s has the right type, and we multiply that
#by the coeff of the personal poly
mstrcoeff=s*invcoeff
#stupid type-fixing nonsense again
a=inverse_mod(mstrcoeff,p)
b=inverse_mod(a,p)
#finally! f is the contribution the person
#makes to the master poly
f=b*poly
masterpoly=masterpoly + f
polylist.append(polynew)
w=masterpoly(0)
return polylist,masterpoly,wOK, so we have an EC \(E\) modulo some prime \(p\) and a message \(m\) ... how do we find a point on \(E\) that corresponds to \(m\)? The chances that \(m\) is an \(x\)-coordinate for a point on the curve are small. To increase the chances, we used Koblitz' method. And, thanks to Ben Groman, we have a program that you can pop into SageMathCell to get a list of possible points.
def ben(p,A,B,m,k):
x=m*k
j=0
while j < k:
x0=x+j
z0 = mod(x0^3+x0A+B, p)
i = 1
while i < p:
y = power_mod(i, 2, p)
if y == z0:
print(x0, i)
i=i+1
j=j+1The example we worked on in class can be reproduced with ben(227,2,7,5,10). Give it a shot! Just be sure to check that \(m\) is permissible with the choice of prime and \(K\).