Cryptographic Functions With Python

• Tweet
• 

        Some useful functions to perform some operations on finite fields and elliptic curves.

## Copyright (c) 2009, wisher
## All rights reserved.
##
## Redistribution and use in source and binary forms, with or without
## modification, are permitted provided that the following conditions are met:
##
## -Redistributions of source code must retain the above copyright notice,
##  this list of conditions and the following disclaimer.
## -Redistributions in binary form must reproduce the above copyright notice,
##  this list of conditions and the following disclaimer in the documentation
##  and/or other materials provided with the distribution.
## -Neither the name of wisher nor the names of its contributors may
##  be used to endorse or promote products derived from this software without
##  specific prior written permission.
##
## THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
## AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
## IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
## ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
## LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
## CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
## SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
## INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
## CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
## ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
## POSSIBILITY OF SUCH DAMAGE.

def squareAndMultiply(base,exponent,modulus):
    #Converting the exponent to its binary form
    binaryExponent = []
    while exponent != 0:
        binaryExponent.append(exponent%2)
        exponent = exponent/2
    #Appllication of the square and multiply algorithm
    result = 1
    binaryExponent.reverse()
    for i in binaryExponent:
        if i == 0:
            result = (result*result) % modulus
        else:
            result = (result*result*base) % modulus
        #print i,"\t",result
    return result

#USAGE: siege(range(2,100),[])
def siege(numbers,primes):
    if len(numbers) > 0:
        prime = numbers.pop(0)
        primes.append(prime)
        newNumbers = []
        for i in numbers:
            if i % prime != 0:
                newNumbers.append(i)
        return siege(newNumbers,primes)
    return primes

def reverse(x,p):
    x = x % p
    t2 = 0
    t1 = 1
    t = 1
    while x != 1:
        t = t2 - p/x*t1
        t1,t2 = t,t1
        x,p = p%x,x
    return t

def ellipticCurveSum((x,y),(z,t),b,c,p):
    try:
        if x=="Infinite" and y=="Infinite":
            return (z,t)
        if z=="Infinite" and t=="Infinite":
            return (x,y)
        if x==z and y==t:
            m = ((3*x*x+b)*reverse(2*y,p)) % p
        else:
            m = ((t-y)*reverse(z-x,p)) % p
        x3 = (m*m-x-z) % p
        y3 = (m*(x-x3)-y) % p
        return (x3,y3)
    except:
        return ("Infinite","Infinite")

def ellipticCurveMultiplication(a,(x,y),b,c,p):
    result = (x,y)
    while a>1:
        result = ellipticCurveSum((x,y),result,b,c,p)
        a = a-1
    return result

def orderOfAPoint((x,y),b,c,p,N):
    for i in range(1,N+1):
        if N%i == 0:
            if ellipticCurveMultiplication(i,(x,y),b,c,p) == ("Infinite","Infinite"):
                return i

def isResidual(value,p):
    return squareAndMultiply(value,(p-1)/2,p)==1

def computeRoot(value,p):
    #brute force rocks
    for i in range(0,p):
        if( ((i*i)%p) == value):
            return i

def pointsOnTheCurve(b,c,p):
    for i in range(0,p):
        rightValue = (i*i*i+b*i+c) % p
        if( isResidual(rightValue,p)):
            root = computeRoot(rightValue,p)
            print (i,root),"\t",(i,-root)
    print "Infinite"

Tags:
• Python