Sage

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

Print

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

Computing inverse modular using Mod

s=Mod(s2-s1,n)
1/s

Computing inverse modular using inverse_mod

s=inverse_mod(s2-s1,n)

m=0x1234; print m                    # Convert hex to decimal
print hex(m)                         # Convert decimal to hex