Sage

References

• Sage website

Manual

• Use command search_src(...) from Sage
• Use command hg_sage.serve() from Sage console
• Sage reference documentation

Tutorials

• http://www-rohan.sdsu.edu/~mosulliv/sagetutorial/sagecalc.html
• http://www.sagemath.org/doc/reference/calculus/sage/calculus/calculus.html

Examples

• small_roots documentation — Nice example on how to manipulate polynomials, primes, etc.

Installation

Upgrading — Upgrade sage with:

sage -upgrade

Sage 6.0

Installing Sage 6.0 compiled for Ubuntu 10.04 (also works on Ubuntu 12.04):

#better install it as standard user (or create a custom user for sage)
tar -xv --lzma -f ~/tmp/sage/sage-6.0-x86_64-Linux-Ubuntu_10.04_x86_64.tar.lzma
mv sage-6.0-x86_64-Linux sage-6.0
sudo ln -s /data/sage-6.0 /sage

Sage 4.2.1

• Installing Sage 4.2.1, Ubuntu 9.10 32bit i686, on Ubuntu Jaunty 9.04.

#better install it as standard user (or create a custom user for sage)
tar -xv --lzma -f sage-4.2.1-linux-Ubuntu_9.10-i686-Linux.tar.lzma
mv sage-4.2.1-linux-Ubuntu_9.10-i686-Linux sage-4.2.1
sudo ln -s /mnt/data/sage-4.2.1 /sage

• Sage complains that version `GLIBCXX_3.4.11' not found (required by /sage/local/lib/libgmpxx.so.3). Fix is to install locally a more up-to-date version of libstdc++ (see [1]):

cd /sage/local/lib
wget http://sage.math.washington.edu/home/wstein/tmp/fedora11/libstdc++.so.6.0.12
ln -s libstdc++.so.6.0.12 libstdc++.so.6

Sage 3.2.1

Install instruction for Ubuntu - using binary image sage-3.2.1-ubuntu_32bit-xeon-i686-Linux.tar.gz. Script below will install sage in /usr/local/sage-3.2.1, and create a copy of sage in path /usr/local/bin.

# (as root)

% cd /usr/local
% tar -xvzf .../sage-3.2.1-ubuntu_32bit-xeon-i686-Linux.tar.gz
% mv sage-3.2.1-Ubuntu-x86_64-opteron-x86_64-Linux sage-3.2.1
% chmod a+rX -R sage-3.2.1     
% cp /usr/local/sage-3.2.1/sage /usr/local/bin
% vi /usr/local/bin/sage
#  --> change SAGE_ROOT to /usr/local/sage-3.2.1

After installation, launch sage from root again because Sage needs to update some links, create files, etc...

% sage

Notebook

Notebook is the html interface to Sage. It is launched with the command notebook (see also (The Sage Notebook object).

Sage 6.0

% sage
sage> notebook(interface='',port=8000)                       # To make notebook available on port 8000, even to remote computer
sage> notebook(interface='',port=8000, require_login=False)  # No login necessary
sage> notebook?                                            # Get help on notebook

% sage -notebook "interface=localhost" "port=8000" "open_viewer=False"   # Launch notebook from command-line
% sage -notebook "interface=''" "port=8000" "open_viewer=False"          # Launch notebook from command-line, even to remote computer - BEWARE no security!

Sage 4.1

% sage
sage> notebook(address='',port=8000)                       # To make notebook available on port 8000, even to remote computer
sage> notebook(address='',port=8000, require_login=False)  # No login necessary
sage> notebook?                                            # Get help on notebook

% sage -notebook "address=localhost" "port=8000" "open_viewer=False"   # Launch notebook from command-line
% sage -notebook "address=''" "port=8000" "open_viewer=False"          # Launch notebook from command-line, even to remote computer - BEWARE no security!

To run Sage with a non-standard browser:

env SAGE_BROWSER=opera /usr/bin/sage -notebook

Example of use

Breaking ECDSA

# This sheet is an attempt to break the hack-lu 2011 challenge (helping Phil Teuwen)
# We can ask an Oracle server to sign arbitrary message using ECDSA.
# Here are two requests:

# 87.64.72.220 connected at Tue Sep 13 19:59:39 2011.
# Your message is 0.
# (r, s) = (0x794be184a2e180978baadfa0561ec7870ce5849bad28ed6a, 0xdb8ddb3018aad092b27aa3f5cd1b47583625e32c4a0ce7d8)

# This is the signature generation machine.
# Using secp192r1, SHA-1.
# 87.64.72.220 connected at Tue Sep 13 19:59:39 2011.
# Your message is 1.
# (r, s) = (0x794be184a2e180978baadfa0561ec7870ce5849bad28ed6a, 0x8036ff32c0d04a924b9c19d2489285a15876cc7e3817cfa)


# This is the signature generation machine.
# Using secp192r1, SHA-1.
# 87.64.72.220 connected at Tue Sep 13 19:59:39 2011.
# Your message is 2.
# (r, s) = (0x794be184a2e180978baadfa0561ec7870ce5849bad28ed6a, 0xa923210c2bd3d5e97cc1ab6021230f6fb49f9b42bee19e4a)

# We see that both messages have the same r, which is bad for the security of secp192r1
# See ECDSA page on Wikipedia:
# - First compute k=(z2-z1)/(s2-s1) mod n, 
# - then da=(s1.k-z1)/r1 mod n
#
# On Wikipedia page on ECC, we have a link to NIST's recommended curve
# http://csrc.nist.gov/groups/ST/toolkit/documents/dss/NISTReCur.pdf
# We can get the value of the curve order (value r in the PDF document, but value n above)

(r1, s1) = (0x794be184a2e180978baadfa0561ec7870ce5849bad28ed6a, 0x8036ff32c0d04a924b9c19d2489285a15876cc7e3817cfa)
(r2, s2) = (0x794be184a2e180978baadfa0561ec7870ce5849bad28ed6a, 0xa923210c2bd3d5e97cc1ab6021230f6fb49f9b42bee19e4a)
# n is the order of the curve (from NIST doc)
n = 6277101735386680763835789423176059013767194773182842284081L
#1st message is "1", 2nd message is "2"
#SHA-1, without Carriage return
z1=0x356a192b7913b04c54574d18c28d46e6395428ab
z2=0xda4b9237bacccdf19c0760cab7aec4a8359010b0

s_inv=inverse_mod(s2-s1,n)
k=Mod((z2-z1)*s_inv,n)
k

#Compute private key from (r1,s1)
dA=Mod(Mod(s1*k-z1,n)*inverse_mod(r1,n),n)
dA

#Compute private key from (r2,s2)
Mod(Mod(s2*k-z2,n)*inverse_mod(r2,n),n)

Quick Reference

Basic

Basic stuff

range

print "a<b:",bool(a<b)              # Don't add surrounding parenthesis
print "n=",hex(n)

# Using expression
a=sqrt(2)
print a                             # 'sqrt(2)'
print type(a)                       # '<type 'sage.symbolic.expression.Expression'>'
print a.n()                         # Print numerical value of a

# Hexadecimal
m=0x1234; print m                   # Convert hex to decimal
print hex(m)                        # Convert decimal to hex (only for Integers)

# Conversion
K = ZZ.random_element(0, 2^128)
print "K   = ",hex(K)               # Member of ZZ are <type 'sage.rings.integer.Integer'>
Rho = [0]*Rhobits                   # This is a <type 'list'>
Rho = ZZ(Rho,2)                     # ... now convert it to <type 'sage.rings.integer.Integer'>
Rho = list(Integer.binary(Rho))     # ... and back to list
ZmodN = Zmod(128)
R = ZmodN.random_element()          # A '<type 'sage.rings.finite_rings.integer_mod.IntegerMod_gmp'>)
Integer(R)                          # ... convert to standard Integer

# Range
range(10)                           # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
range(5, 10)                        # [5, 6, 7, 8, 9]
range(0, 10, 3)                     # [0, 3, 6, 9]

Modular arithmetics

                                    # ----- INVERSE modular
s=Mod(s2-s1,n)
1/s                                 # Using 'Mod'
s=inverse_mod(s2-s1,n)              # Using 'inverse_mod'

                                    # ----- Modular EXPONENTATION
ZmodN = Zmod(N)
C = ZmodN(M)^e                      # Using 'Zmod' ring
print "C   = ",hex(Integer(C))

C=power_mod(M,e,N)                  # Using 'power_mod' builtin

def modexp(a, b, n):
    d=1
    for i in list(Integer.binary(b)):
            d = mod(d*d,n)
            if Integer(i)== 1:
                d = mod(d*a,n)
    return Integer(d)
SIGN = modexp(m, d, n)               # Using own function

Polynomials

ZmodN = Zmod(N)
P.<x> = PolynomialRing(ZmodN)
f = (ZmodN(Rho)*2^Kbits + x)^e - ZmodN(C)   # Define our polynomial - must use elt from the ring
time Kbar = f.small_roots()[0]

Structures

Ring Z of Integers (elements of Z)

Z = IntegerRing(); Z                    # Integer Ring
ZZ==IntegerRing()                       # true - 'ZZ' is already defined

Ring Z/nZ of integers modulo n (Elements of Z/nZ)

IntegerModRing(15)                          # Ring of integers modulo 15
Integers(15)                                # ... idem (synomym)
Zmod(15)                                    # ... idem (synomym)
Integers() is Integers(0) is ZZ             # Integers() is the Ring Z of Integers
type(IntegerModRing(2^31-1).an_element())   # type of an element