Sage

From miki
Revision as of 15:00, 17 June 2014 by Mip (talk | contribs) (→‎Tips)
Jump to navigation Jump to search

Links

Manual
Tutorials
Examples

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

Starting Sage

The 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

Reference

Python

See Python on this wiki.

Basic

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
print a.n(digits=20)                # Print numerical value of a, with 20 accurate digits
print a.n(prec=64)                  # Print numerical value of a, with 64-bit precision

# 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]

# List
print mylist[1:10]                  # Extract a sublist
mylist = [f(i) for i in range(10)]  # Create a list

Arithmetics

http://www.sagemath.org/doc/reference/misc/sage/rings/arith.html 

                                    # ----- INVERSE modular
s=Mod(s2-s1,n); 1/s                 # Using 'Mod'
ZmodN=Zmod(n); ZmodN(1/s)           # Using inverse in the Integers modulo n ring
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

                                     # ----- Chinese Remainder Theorem
crt([13, 20], [100, 301])            # Return x s.t. x=13 mod 100, x=20 mod 301

                                     # ----- Other
next_prime(p)                        # Return smallest prime > p
random_prime(pmax,None,pmin)         # Random prime [pmin,pmax] - see doc for meaning of None
euler_phi(47*53)                     # Euler's phi function
odd_part(n)                          # Return n/2^k, with k as large as possible

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
f.small_roots()[0]                          # Find f's small roots (using Coppersmith's theorem)
g = f.monic()                               # Return f divided by its leading coef, such that g is monic

Structures

Ring Z of Integers (elements of Z)
Z = IntegerRing(); Z                    # Integer Ring
ZZ==IntegerRing()                       # true - 'ZZ' is already defined
ZZ.random_element(min,max)              # A random element min <= x < max
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

Tips

Don't print carriage return in Notebook [2]
for i in range(10):
    print i,                                 # Use comma and flush
    sys.stdout.flush()                       # might require 'import sys'
print ''
Print long output lines (>72 characters) without breaks
  • Click on the left of the line that is broken up [3]
  • Maybe there is a way to do this programmatically (see Cell.word_wrap_cols() and Cell.set_cell_output_type)
  • Or change the default word wrap settings permanently for the whole notebook.
    For this, logged in as admin, go to Settings→Notebook settings, and edit Number of word-wrap columns (default <ode>72).

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)
Retrieved from "https://miki.immie.org/mediawiki/index.php?title=Sage&oldid=6137"