2015-06-03-135259.sagews

import time

debug = True

# display matrix picture with 0 and X
def matrix_overview(BB, bound):
    for ii in range(BB.dimensions()[0]):
        a = ('%02d ' % ii)
        for jj in range(BB.dimensions()[1]):
            a += '0' if BB[ii,jj] == 0 else 'X'
            a += ' '
        if BB[ii, ii] >= bound:
            a += '~'
        print a

def coppersmith_howgrave_univariate(pol, modulus, beta, mm, tt, XX):
    """
    Coppersmith revisited by Howgrave-Graham
    
    finds a solution if:
    * b|modulus, b >= modulus^beta , 0 < beta <= 1
    * |x| < XX
    """
    #
    # init
    #
    dd = pol.degree()
    nn = dd * mm + tt

    #
    # checks
    #
    if not 0 < beta <= 1:
        raise ValueError("beta should belongs in (0, 1]")

    if not pol.is_monic():
        raise ArithmeticError("Polynomial must be monic.")

    #
    # calculate bounds and display them
    #
    """
    * we want to find g(x) such that ||g(xX)|| <= b^m / sqrt(n)
    * we know LLL will give us a short vector v such that:
    ||v|| <= 2^((n - 1)/4) * det(L)^(1/n)
    * we will use that vector as a coefficient vector for our g(x)
    
    * so we want to satisfy:
    2^((n - 1)/4) * det(L)^(1/n) < N^(beta*m) / sqrt(n)
    
    so we can obtain ||v|| < N^(beta*m) / sqrt(n) <= b^m / sqrt(n)
    (it's important to use N because we might not know b)
    """
    if debug:
        # t optimized?
        print "\n# Optimized t?\n"
        print "we want X^(n-1) < N^(beta*m) so that each vector is helpful"
        cond1 = RR(XX^(nn-1))
        print "* X^(n-1) = ", cond1
        cond2 = pow(modulus, beta*mm)
        print "* N^(beta*m) = ", cond2
        print "* X^(n-1) < N^(beta*m) \n-> GOOD" if cond1 < cond2 else "* X^(n-1) >= N^(beta*m) \n-> NOT GOOD"
        
        # bound for X
        print "\n# X bound respected?\n"
        print "we want X <= N^(((2*beta*m)/(n-1)) - ((delta*m*(m+1))/(n*(n-1)))) / 2 = M"
        print "* X =", XX
        cond2 = RR(modulus^(((2*beta*mm)/(nn-1)) - ((dd*mm*(mm+1))/(nn*(nn-1)))) / 2)
        print "* M =", cond2
        print "* X <= M \n-> GOOD" if XX <= cond2 else "* X > M \n-> NOT GOOD"

        # solution possible?
        print "\n# Solutions possible?\n"
        detL = RR(modulus^(dd * mm * (mm + 1) / 2) * XX^(nn * (nn - 1) / 2))
        print "we can find a solution if 2^((n - 1)/4) * det(L)^(1/n) < N^(beta*m) / sqrt(n)"
        cond1 = RR(2^((nn - 1)/4) * detL^(1/nn))
        print "* 2^((n - 1)/4) * det(L)^(1/n) = ", cond1
        cond2 = RR(modulus^(beta*mm) / sqrt(nn))
        print "* N^(beta*m) / sqrt(n) = ", cond2
        print "* 2^((n - 1)/4) * det(L)^(1/n) < N^(beta*m) / sqrt(n) \n-> SOLUTION WILL BE FOUND" if cond1 < cond2 else "* 2^((n - 1)/4) * det(L)^(1/n) >= N^(beta*m) / sqroot(n) \n-> NO SOLUTIONS MIGHT BE FOUND (but we never know)"

        # warning about X
        print "\n# Note that no solutions will be found _for sure_ if you don't respect:\n* |root| < X \n* b >= modulus^beta\n"
    
    #
    # Coppersmith revisited algo for univariate
    #

    # change ring of pol and x
    polZ = pol.change_ring(ZZ)
    x = polZ.parent().gen()

    # compute polynomials
    gg = []
    for ii in range(mm):
        for jj in range(dd):
            gg.append((x * XX)**jj * modulus**(mm - ii) * polZ(x * XX)**ii)
    for ii in range(tt):
        gg.append((x * XX)**ii * polZ(x * XX)**mm)
    
    # construct lattice B
    BB = Matrix(ZZ, nn)

    for ii in range(nn):
        for jj in range(ii+1):
            BB[ii, jj] = gg[ii][jj]

    # display basis matrix
    if debug:
        matrix_overview(BB, modulus^mm)

    # LLL
    BB = BB.LLL()

    # transform shortest vector in polynomial    
    new_pol = 0
    for ii in range(nn):
        new_pol += x**ii * BB[0, ii] / XX**ii

    # factor polynomial
    potential_roots = new_pol.roots()
    print "potential roots:", potential_roots

    # test roots
    roots = []
    for root in potential_roots:
        if root[0].is_integer():
            result = polZ(ZZ(root[0]))
            if gcd(modulus, result) >= modulus^beta:
                roots.append(ZZ(root[0]))

    # 
    return roots

############################################
# Test on Stereotyped Messages
##########################################    

print "//////////////////////////////////"
print "// TEST 1"
print "////////////////////////////////"

# RSA gen options (for the demo)
length_N = 1024  # size of the modulus
Kbits = 200      # size of the root
e = 3

# RSA gen (for the demo)
p = next_prime(2^int(round(length_N/2)))
q = next_prime(p)
N = p*q
ZmodN = Zmod(N);

# Create problem (for the demo)
K = ZZ.random_element(0, 2^Kbits)
Kdigits = K.digits(2)
M = [0]*Kbits + [1]*(length_N-Kbits); 
for i in range(len(Kdigits)):
    M[i] = Kdigits[i]
M = ZZ(M, 2)
C = ZmodN(M)^e

# Problem to equation (default)
P.<x> = PolynomialRing(ZmodN) #, implementation='NTL')
pol = (2^length_N - 2^Kbits + x)^e - C
dd = pol.degree()

# Tweak those
beta = 1                                # b = N
epsilon = beta / 7                      # <= beta / 7
mm = ceil(beta**2 / (dd * epsilon))     # optimized value
tt = floor(dd * mm * ((1/beta) - 1))    # optimized value
XX = ceil(N**((beta**2/dd) - epsilon))  # optimized value

# Coppersmith
start_time = time.time()
roots = coppersmith_howgrave_univariate(pol, N, beta, mm, tt, XX)

# output
print "\n# Solutions"
print "we want to find:",str(K)
print "we found:", str(roots)
print("in: %s seconds " % (time.time() - start_time))
print "\n"

############################################
# Test on Factoring with High Bits Known
##########################################
print "//////////////////////////////////"
print "// TEST 2"
print "////////////////////////////////"

# RSA gen
length_N = 1024;
p = next_prime(2^int(round(length_N/2)));
q = next_prime( round(pi.n()*p) );
N = p*q;

# qbar is q + [hidden_size_random]
hidden = 200;
diff = ZZ.random_element(0, 2^hidden-1)
qbar = q + diff; 

F.<x> = PolynomialRing(Zmod(N), implementation='NTL'); 
pol = x - qbar
dd = pol.degree()

# PLAY WITH THOSE:
beta = 0.5                             # we should have q >= N^beta
epsilon = beta / 7                     # <= beta/7
mm = ceil(beta**2 / (dd * epsilon))    # optimized
tt = floor(dd * mm * ((1/beta) - 1))   # optimized
XX = ceil(N**((beta**2/dd) - epsilon)) # we should have |diff| < X

# Coppersmith
start_time = time.time()
roots = coppersmith_howgrave_univariate(pol, N, beta, mm, tt, XX)

# output
print "\n# Solutions"
print "we want to find:", qbar - q
print "we found:", roots
print("in: %s seconds " % (time.time() - start_time))

////////////////////////////////// // TEST 1 //////////////////////////////// # Optimized t? we want X^(n-1) < N^(beta*m) so that each vector is helpful * X^(n-1) = 5.26588450218277e469 * N^(beta*m) = 5809605995369958062859502533304574370686975176362895236661486152287203730997110225737336044533118407251326157754980517443990529594540047121662885672187318379170893091380779314421226637138275349470290853160784521096650764992953261892033155088964701773548941402064393684794946750211086736290671577104533659642057118917143584402358425763453268564512919742021495562856804237181830944118597652633110777860501395758734009382103277519347965512270318311650775740609245712375989187523162575910893401371870662641830320681166427150335438145263362770625995772981051308652613471165711681334529841626638582686839433337262143010780233438621153258840860120619228367830876704643942342141894676446795044841146659969772821383582256097597403390152196838898111302490307579997628617454989618216755310133769183576086459390337713555959065986325737177623859347069743089552382311434116472575356994213750090774944532102495872113514499697576541330780931 * X^(n-1) < N^(beta*m) -> GOOD # X bound respected? we want X <= N^(((2*beta*m)/(n-1)) - ((delta*m*(m+1))/(n*(n-1)))) / 2 = M * X = 51901978826686593576182134394350049796327272495710410629191 * M = 5.78960446186581e76 * X <= M -> GOOD # Solutions possible? we can find a solution if 2^((n - 1)/4) * det(L)^(1/n) < N^(beta*m) / sqrt(n) * 2^((n - 1)/4) * det(L)^(1/n) = 9.38051702189965e851 * N^(beta*m) / sqrt(n) = 1.93653533178999e924 * 2^((n - 1)/4) * det(L)^(1/n) < N^(beta*m) / sqrt(n) -> SOLUTION WILL BE FOUND # Note that no solutions will be found _for sure_ if you don't respect: * |root| < X * b >= modulus^beta 00 X 0 0 0 0 0 0 0 0 ~ 01 0 X 0 0 0 0 0 0 0 ~ 02 0 0 X 0 0 0 0 0 0 ~ 03 X X X X 0 0 0 0 0 04 0 X X X X 0 0 0 0 05 0 0 X X X X 0 0 0 06 X X X X X X X 0 0 07 0 X X X X X X X 0 08 0 0 X X X X X X X potential roots: [(1461575241394679079988298392736422006399143063728450204656611, 1)] # Solutions we want to find: 1461575241394679079988298392736422006399143063728450204656611 we found: [1461575241394679079988298392736422006399143063728450204656611] in: 0.0915811061859 seconds ////////////////////////////////// // TEST 2 //////////////////////////////// # Optimized t? we want X^(n-1) < N^(beta*m) so that each vector is helpful * X^(n-1) = 8.70626317072222e385 * N^(beta*m) = 3.18956065351443e617 * X^(n-1) < N^(beta*m) -> GOOD # X bound respected? we want X <= N^(((2*beta*m)/(n-1)) - ((delta*m*(m+1))/(n*(n-1)))) / 2 = M * X = 13622652689555162275328740864963325782847721740190089216 * M = 7.24576134690965e65 * X <= M -> GOOD # Solutions possible? we can find a solution if 2^((n - 1)/4) * det(L)^(1/n) < N^(beta*m) / sqrt(n) * 2^((n - 1)/4) * det(L)^(1/n) = 2.73243713251504e579 * N^(beta*m) / sqrt(n) = 1.12767998355292e617 * 2^((n - 1)/4) * det(L)^(1/n) < N^(beta*m) / sqrt(n) -> SOLUTION WILL BE FOUND # Note that no solutions will be found _for sure_ if you don't respect: * |root| < X * b >= modulus^beta 00 X 0 0 0 0 0 0 0 ~ 01 X X 0 0 0 0 0 0 02 X X X 0 0 0 0 0 03 X X X X 0 0 0 0 04 X X X X X 0 0 0 05 0 X X X X X 0 0 06 0 0 X X X X X 0 07 0 0 0 X X X X X potential roots: [(42121870893450634577463914985889299119866228583627912396576170307551916037987547771260822964332702400259781612006436828755439640357041448542242280376705050, 1), (161390549720322056745237586276083576139400748999244182790049, 3), (45427401223847620136681579269702116080448448363866259049743266771925784895/281474976710656, 3)] # Solutions we want to find: 161390549720322056745237586276083576139400748999244182790049 we found: [42121870893450634577463914985889299119866228583627912396576170307551916037987547771260822964332702400259781612006436828755439640357041448542242280376705050, 161390549720322056745237586276083576139400748999244182790049] in: 0.0241799354553 seconds