Find embedded curve for BN256 snarks

gistfile1.txt

#check BN-curve from etherium
BN_p = 21888242871839275222246405745257275088696311157297823662689037894645226208583
BN_curve = EllipticCurve(GF(BN_p),[0,3])
BN_order = BN_curve.order()
# print BN_order in Primes()
# print BN_order % 4

#we are going to use algorithm described in 
#https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/NIST.pdf
#see also: http://iml.univ-mrs.fr/ati/crypto_puces/2009/slides/ivey-law.pdf
def check_twisted_Edwards_curve(d, p, check_CM_discr = True):
    assert p % 4 == 1, "Algorithm for p % 4 == 3 is not implemented"
    #every Edwards curve ax^2 + by^2 = 1 + dx^2y^2 is birationally equivalent to Montgomery curve, which is a well defined 
    #elliptic curve. We unable to use standard Sage functions (like point counting and Frobenius trace calculation) for curves
    #represented in Edwards form hence a transformation to general Weierstrass form is required
    #the form changing rool is the following: (https://orbilu.uni.lu/bitstream/10993/14765/1/ASIAPKC2013.pdf, page 41)
    #a_2 = 2(a+d), a_4 = (a-d)^2, a_1 = a_3 = a_6 = 0
    a = -1
    test_curve = EllipticCurve(GF(p),[0, 2*(a+d), 0, (a-d)^2, 0])
    curve_order = test_curve.order()
    fr_trace = p + 1 - curve_order
    x = curve_order
    y = p + 1 + fr_trace
    #check that cofactors are small: protection against Pohlig-Hellman algorithm
    if (x % 4 == 0 and y % 8 == 0):
        r = x / 4
        s = y / 8
    else:
        r = x / 8
        s = y / 4
    if r not in Primes() or s not in Primes():
        return False
    
    #there are three additional checks to ensure that constructed curve is cryptographically strong.
    #1) curve is not anomalous - Frobenius trace is not equal to 1 (protection against SMART attack)
    if fr_trace == 1:
        return False
    #2) embedding degree is large enough: k=30 or larger (protection against MOV attack)
    #   by (http://www.acrypta.com/telechargements/ell_tech_report_public.pdf, page 5) it is enough to check that 
    #   p^d != 1 (mod curve_order) for every d <= 30.
    for d in xrange(1, 31):
        if pow(p, d, curve_order) == 1:
            return False
    #3) CM field discriminant is large:  d >= 2^100. Curves with small CM discriminant posess additional set of endomorphisms -
    #   there are currently no known attacks that exploits this feature, but who knows what will be in the near future :)  
    #   It is enough to verify that the square-free part of 4p ? trace^2 is greater than 2^100. This fact follows from
    #   (http://helper.ipam.ucla.edu/publications/scws1/scws1_6224.pdf, page 24):

    #   As CM discriminant check is not currently exploitable and is more like a suggestio we provide a boolean flag 
    #   that turns on the check if it is required
    assert 4*p - fr_trace * fr_trace > 0, "Error in CM field discriminant computation"
    if (check_CM_discr and squarefree_part(4*p - fr_trace * fr_trace) < 2^100):
        return False
    return True

#check our script for Jub-Jub function from zCash that we know to be correct and secure
#info for specific BLS curve: https://github.com/zkcrypto/pairing/tree/master/src/bls12_381
#info for JUB-JUB params: https://z.cash/technology/jubjub.html
BLS_p = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
BLS_order = 0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001
#print BLS_order in Primes()
#print BLS_order % 4
R = IntegerModRing(BLS_order)
JUB_JUB_d = Integer(- R(10240) / R(10241))
print "Checking BLS-381"
print check_twisted_Edwards_curve(JUB_JUB_d, BLS_order, True)


def find_curve():
    d = -1
    found = False
    while not found:
        print d
        if d < 0:
            d = -d + 1
        else:
            d = -d
        found = check_twisted_Edwards_curve(d, BN_order, True)
    return d

attempts = 0
while True:
    d = randint(2, BN_order - 1)
    attempts = attempts + 1
    if attempts % 10 == 0:
        print "Done attempts = " + str(attempts)
#     print d
    if check_twisted_Edwards_curve(d, BN_order, False):
        print "Success: ", d