Homework2
system:sage


<h2>Problem #7: ElGamal Encryption</h2>

Here are the parameters for the ElGamal cryptosystem in the problem.

{{{id=1|
p = 2^192-2^64-1; p
///
6277101735386680763835789423207666416083908700390324961279
}}}

{{{id=2|
is_prime(p)
///
True
}}}

{{{id=3|
B = int('64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1',16); B
///
2455155546008943817740293915197451784769108058161191238065L
}}}

{{{id=4|
E = EllipticCurve(GF(p),[-3,B])
///
}}}

{{{id=5|
is_prime(E.count_points())
///
True
}}}

{{{id=6|
x0 = int('188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012',16); x0
///
602046282375688656758213480587526111916698976636884684818L
}}}

{{{id=7|
y0 = int('07192b95ffc8da78631011ed6b24cdd573f977a11e794811',16); y0
///
174050332293622031404857552280219410364023488927386650641L
}}}

{{{id=8|
P = E([x0,y0])
///
}}}

$Q = [a]P$ where $a$ is the secret key:

{{{id=11|
Q = E([3663963113969291544469926280538612298367383514202028986922,1042131040378490833378905612228666552957404825004815884320])
///
}}}

<h3>Conversion functions</h3>

{{{id=12|
def str_to_int(string):
    '''Takes a string consisting of letters and numbers and interprets it as an integer base 36.
       The function is case insensitive.
    '''
    
    return ZZ(int(string,36))
///
}}}

{{{id=13|
def int_to_str(integer):
    '''Takes an integer and returns the base 36 representation.
    '''
    
    return integer.str(36)
///
}}}

Testing the functions:

{{{id=14|
str_to_int('homework')
///
1385788861280
}}}

{{{id=15|
int_to_str(314159265358979324)
///
'2dxc5y3uvjzw'
}}}

{{{id=16|
int_to_str(str_to_int('CS259c'))
///
'cs259c'
}}}

<h3>Converting between integers and points on $E(\mathbb{F}_p)$.</h3>

(a) Write the following function.

{{{id=17|
def int_to_point(n,E):
    '''Takes an integer n and encodes it as a unique point on the elliptic curve E.
    '''
    
    return E([0,1,0])  # replace this with the point you compute
///
}}}

(b) Write the following function.

{{{id=18|
def point_to_int(P):
    '''Takes a point P on an elliptic curve and encodes it as an integer.
    '''
    
    return 0  # replace this with the integer you compute
///
}}}

Here's a procedure to test whether the functions behave appropriately.  Note that the procedure takes functions as arguments.

{{{id=19|
def test_inverses(f,g,E,n):
    '''Tests whether the functions f and g are inverses of each other on n random inputs.
       f takes as input an integer t and an elliptic curve E.
       g takes as input the output of f.
    '''
    
    for i in range(n):
        t = randint(0,36^25)
        if g(f(t,E)) != t:
            return False
    
    return True
///
}}}

We define a squaring function $f$ and a square root function $g$.  (For more on lambda forms, see <a href="http://docs.python.org/tutorial/controlflow.html#lambda-forms">Python documentation</a>.)  

Here $f$ and $g$ are inverses because <tt>test_inverses</tt> only gives positive inputs to $f$, and the <tt>sqrt</tt> function always returns the positive square root.

{{{id=26|
f = lambda x,E : x^2    # E does nothing here
g = lambda y : sqrt(y)
test_inverses(f,g,E,1000)
///
True
}}}

Over a finite field, <tt>sqrt(x^2)</tt> may not be equal to $x$.

{{{id=27|
f = lambda x,E : GF(123457)(x)^2
test_inverses(f,g,E,1000)
///
False
}}}

Use test_inverses to test your functions above.

{{{id=34|
test_inverses(int_to_point,point_to_int,E,1000)
///
}}}

(c) Write an ElGamal encryption function.

{{{id=20|
def encrypt(P,Q,s):
    '''Compute the ElGamal encryption of the string s using the public key (P,Q).'''
///
}}}

(d) Use this function to encrypt your name (or the first 25 characters thereof).

{{{id=25|

///
}}}