import numpy
import itertools
def ASCIIPad(Mess,Mod):
    K = []
    for letter in Mess:
        K.append(ord(letter))
    L = Mod.ndigits()
    l = len(K)
    y = ZZ(math.floor(L/3))
    count = 0
    padded = []
    buffer = ""
    for numChar in K:
        numChar+=100
        buffer+=str(numChar)
        count+=1
        if count==y:
            padded.append(ZZ(buffer))
            buffer = ""
            count = 0
    if len(buffer)>0:
        padded.append(ZZ(buffer))
    return padded

def ASCIIDepad(Number):
    N = "";
    n = Number.ndigits() % 3;
    if (n > 0):
        print("This is not a padded ASCII string\n");
    else:
        L = [((Number - (Number % (1000^i)))/1000^i)%1000 - 100 for i in range(Number.ndigits()/3)];
        for i in range(Number.ndigits()/3):
            N = chr(L[i]) + N;
    return(N);
def ECRAdd(Point1,Point2,Group):
    a = Group[0]
    b = Group[1]
    p = Group[2]
    if Point1!=[]:
        x1 = Point1[0]
        y1 = Point1[1]
    if Point2!=[]:
        x2 = Point2[0]
        y2 = Point2[1]
    if ZZ(mod(4*a^3 + 27*b^2, p)) == 0:
        print ("This is not an ellitpic curve")
    elif Point1!=[] and ZZ(mod(y1^2, p)) != ZZ(mod(x1^3 + a*x1 + b,p)):
        print ("Point 1 is not on the elliptic curve.")
    elif Point2!=[] and ZZ(mod(y2^2, p)) != ZZ(mod(x2^3 + a*x2 + b,p)):
        print ("Point 2 is not on the elliptic curve.")
    else:
        if Point1==[]:
            R=Point2
        elif Point2=={}:
            R=Point1
        else:
            if x1==x2 and 0==ZZ(mod(y1+y2,p)):
                R=[]
            elif x1==x2 and y1==y2:
                R=ECRDouble(Point1,Group)
                if R==True:
                    return(True)
            else:
                g=gcd(x1-x2,p)
                if (g>1):
                    print ("factor is {0}".format(g))
                    return(True)
                s=ZZ(mod((y1-y2)/(x1-x2),p))
                x=ZZ(mod(s^2-(x1+x2),p))
                y=ZZ(mod(s*(x1-x)-y1,p))
                R=[x,y]
    return R
def ECRDouble(Point,Group):
    a = Group[0]
    b = Group[1]
    p = Group[2]
    if Point!=[]:
        x1 = Point[0]
        y1 = Point[1]
        if ZZ(mod(4*a^3 + 27*b^2, p)) == 0:
            print ("This is not an ellptic curve")
        elif Point!= [] and ZZ(mod(y1^2,p))!= ZZ(mod(x1^3+a*x1+b,p)):
            print ("point to double not on elliptic curve")
        elif y1==0:
            R=[]
        else:
            g = gcd(y1,p)
            if g>1:
                print ("Factor is {0}".format(g))
                return True
            s = ZZ(mod((3*x1^2+a)/(2*y1),p))
            x = ZZ(mod(s^2-(x1+x1),p))
            y = ZZ(mod(s*(x1-x)-y1,p))
            R = [x,y]
    else:
        R=[]
    return R
def ECRTimes(Point,scalar,Group):
    ECIDENTITY = []
    if Point==ECIDENTITY or scalar ==0:
        return ECIDENTITY
    else:
        m = scalar
        pt = Point
        x = ECIDENTITY
        j=1
        while j<(scalar +1):
            if m%2==0:
                m = m/2
            else:
                m=(m-1)/2
                x=ECRAdd(x,pt,Group)
                if x==True:
                    return true
            if m==0:
                return x
            pt = ECRDouble(pt,Group)
            if pt==True:
                return true
            j+=1
def ECRInverse (Point, Group):
    if Point == []:
        return(Point)
    else:
        p = Group[2]
        x = Point[0]
        y = Point[1]
        return([x,(p - y) % p])
def isquare (n):
    if isqrt(n) ** 2 == n:
        return(True)
    return(False)
def isqrt(n):
    return int(floor(sqrt(n)))

def usqrt (n):
    ur = isqrt(n)
    if ur ** 2 < n:
        ur = ur + 1
    return(ur)

def FermatAttack (n, rounds):
    st = usqrt(n)
    for x in range(st, st + rounds + 1):
        #print (x-st)
        sq = x ** 2 - n
        y = isqrt(sq)
        if y ** 2 == sq:
            print ("Factor found in round", (x-st+1))
            return(x + y)
    print ("No factor found in rounds", (rounds))
def OneLine (n, iter):
    for x in range(1, iter + 1):
        sq = usqrt(x * n)
        y = sq ** 2 % n
        if isquare(y) == True:
            t = isqrt(y)
            u = gcd(n, sq - t)
            print("Factor found in round {0} rounds".format(x))
            return(u)
    print("No factors found")
def ISAttack (R):
    R = ZZ(R)
    n = R.ndigits()
    for j in range(1, n + 1):
        x=(R-(R % 10^j))/10^j
        p = gcd(x, R)
        if ((1 < p)and (p<R)):
            return(p)
    print("no factor found")
def RhoAttack(R,rounds):
    a=2
    b=2
    for i in range (1,rounds):
        a=(a^2+1)% R ######## Floyd's Cycle Finding
        c=(b^2+1)% R ######## Floyd's Cycle Finding
        b=(c^2+1)% R ######## Floyd's Cycle Finding
        g=gcd(a-b,R)
        if (1<g and g<R):
                print ("Factor found in round {0}".format(i))
                return(g)
    print("The Pollard rho failed in {0}rounds".format(rounds))
def Dirichlet (q):
    j=0
    while True:
        j+=1
        p = 2 * j * q + 1
        if is_prime(p) == True:
            return(p)
def ECTimes (Point, scalar, Group):
    ECIdentity=[]
    if Point == ECIdentity or scalar == 0:
        return(ECIdentity)
    else:
        E=EllipticCurve(GF(Group[2]),[Group[0],Group[1]])
        EPoint = E(Point[0],Point[1])
        cgret = scalar*EPoint
        if(cgret[0]==0 and cgret[1]==1 and cgret[2]==0):
            return ECIdentity
        return([cgret[0],cgret[1]])
import itertools
def ECSearch (lowerbound, upperbound, Group):
    p = Group[2]
    a = Group[0]
    b = Group[1]
    if (4 * a ** 3 + 27 * b ** 2) % p == 0:
        print ("This is not an elliptic curve.")
    else:
        for j in itertools.count(lowerbound):
            if j==lowerbound-1 or j>upperbound or j>upperbound:
                return "not found"
            j=j%p
            if kronecker(j ** 3 + a * j + b, p) == 1:
                x = (j ** 3 + a * j + b) % p
                var('z')
                L=TonSh(x,p)
                y = L
                return([j,y])
import numpy
import itertools
import math
import sympy.ntheory
import random
def TonSh (a, Prime):
    if kronecker(a, Prime) == -1:
        pass
        print ("{0} does not have a square root mod {1}".format(a, Prime))
        return None
    elif Prime % 4 == 3:
        x = power_mod(ZZ(a), ZZ((Prime+1)/4),ZZ(Prime))
        return(x)
    else:
        #################################################################################
        # Determine e so that Prime-1 = (2^e)*q for some odd number q                   #
        #################################################################################

        e = ZZ(0)
        q = ZZ(Prime - 1)
        for j in itertools.count(1):
            if q % 2 == 0:
                e = ZZ(e + 1)
                q = ZZ(q / 2)
            else:
                break
        for i in range(1, 101):
            n = i
            if kronecker(n, Prime) == -1:
                break
        z = power_mod(ZZ(n),ZZ(q),ZZ(Prime))
        y = ZZ(z)
        r = ZZ(e)
        x = power_mod(ZZ(a),ZZ( (q-1)/2),ZZ( Prime))
        b = (a * x ** 2) % Prime
        x = (a * x) % Prime
        #for i in range(1, e + 1):
        for i in itertools.count(1):
            if b == 1:
                break
            else:
                for m in itertools.count(1):
                    t = power_mod(ZZ(b), ZZ(2^m) ,  ZZ(Prime))
                    if t == 1:
                        mm = m
                        break
                t = power_mod(ZZ(y), ZZ(2^(r - mm - 1)),ZZ(Prime))
                y = power_mod(ZZ(t), ZZ(2),ZZ(Prime))
                r = mm
                x = (x * t) % Prime
                b = (b * y) % Prime
        return(x)
def findptOrder(point,group):
    E = EllipticCurve(GF(group[2]),[group[0],group[1]])
    Ep = E(point[0],point[1])
    return Ep.additive_order()

while True:
    p1 = randint(10^29, 10^30-1)
    p1 += 2 - p1 % 3

    if is_prime(p1):
        break

while True:
    q1 = randint(10^29, 10^30-1)
    q1 += 2 - q1 % 3

    if is_prime(q1):
        break

m = (p1+1)*(q1+1)

while True:
    s1 = randint(2, m-1)
    if gcd(s1, m) == 1:
        break

p1
q1
s1
print("p1 % 3 =", p1 % 3)
print("q1 % 3 =", q1 % 3)
print("gcd(s1, (p1+1)*(q1+1)) =", gcd(s1, m))

while True:
    p2 = randint(10^29, 10^30-1)
    p2 += 2 - p2 % 3

    if is_prime(p2):
        break

while True:
    q2 = randint(10^29, 10^30-1)
    q2 += 2 - q1 % 3

    if is_prime(q2):
        break

j = (p2+1)*(q2+1)

while True:
    s2 = randint(2, j-1)
    if gcd(s2, j) == 1:
        break

p2
q2
s2
print("p1 % 3 =", p2 % 3)
print("q1 % 3 =", q2 % 3)
print("gcd(s1, (p1+1)*(q1+1)) =", gcd(s2, j))

R1 = p1*q1
R2 = p2*q2
t1 = (1/s1) % ((p1 + 1) * (q1 + 1))
t2 = (1/s2) % ((p2 + 1) * (q2 + 1))

M="Security"
m=ASCIIPad(M,R1)
print ('The padded ASCII version of the plaintext is:', m)

# 1st Encryption
b=(1-m[0]^3) %R1
E=[0,b,R1]
pt=[m[0],1]
c=ECRTimes(pt,s1,E)
print('The ciphertext is:', c)

# 2nd Encryption
b1=(c[1]^2 - c[0]^3) %R2
E1=[0,b1,R2]
print ('The elliptic curve group is:', E1)

c1=ECRTimes(c,s2,E1)
print('The ciphertext is:', c1)

# 1st decryption
Bd=(c1[1]^2-c1[0]^3) %R2
Bd
ED = [0,Bd,R2]
ED
ptd = ECRTimes(c1,t2,[0,Bd,R2])
print("First decryption ciphertext:")
ptd

# 2nd decryption
B2 = (ptd[1]^2-ptd[0]^3) %R1
B2
ED = [0,B2,R1]
ED
ptd1 = ECRTimes(ptd,t1,[0,B2,R1])
print("Encoded message:")
ASCIIDepad(ptd1[0])

#Problem 2
while True:
    p3 = randint(10^29, 10^30-1)
    p3 += 2 - p3 % 3

    if is_prime(p3):
        break

while True:
    q3 = randint(10^29, 10^30-1)
    q3 += 2 - q3 % 3

    if is_prime(q3):
        break

m3 = (p3+1)*(q3+1)

while True:
    s3 = randint(2, m3-1)
    if gcd(s3, m3) == 1:
        break

p3
q3
s3
print("p1 % 3 =", p3 % 3)
print("q1 % 3 =", q3 % 3)
print("gcd(s3, (p1+1)*(q1+1)) =", gcd(s3, m3))

R3 = p3 * q3
t3 = (1/s3) % ((p3 + 1) * (q3 + 1))
print("KMOV R value is =", R3)
print("KMOV S value is =", s3)
print("KMOV private key is =", t3)

#KMOV Encrypt
M = "Cryptology"
m = ASCIIPad(M, R3)
print('The padded ASCII version of the plaintext is:', m)
b = (1 - m[0] ^ 3) % R3

E = [0,b,R3]
print('The elliptic curve group is:', E)
pt = [m[0], 1]
print('The point is:', pt)

R = ECRTimes(pt,s3,E)
print(R)

#Generate an elliptic curve group
A = 74836135632164565623019856132489651147658
B = 39287349204739740210892348756132890612349
p = next_prime(8397409827340587324095872345098723450978234509)
G=[A,B,p] ############# Elliptic Curve Group
print("The elliptic curve group is\n G=",[A,B,p])

E=EllipticCurve(GF(p),[A,B])
Gp = E.order() ##### Order of the elliptic group G
print("The order of the elliptic curve group is",Gp)

g = ECSearch(78657643, 894579475973497, G)
print("The base point is g=", g)

gorder=findptOrder(g,G) ############# order of the point g
print("The order of the base point g is",gorder)

x= 3267452870001
print("The private key is x=", x)

b=ECTimes(g,x,G)
print("The public elliptic curve point is\n b=", b)

r = 538968140843431472563478573870705697113817443
test = gcd(r,gorder)
print(test)
# Step 3. Compute the point R on the elliptic curve group G using the base point g and the random number r
R = ECTimes(g,r,G)
Y=R[0] ####### this is the first coordinate of the point R

# Step 4. Compute the S using the ASCII padded message m, private key x, random number r and the elliptic curve point R.

m = ZZ(m[0])
x = ZZ(x)
Y= ZZ(Y)
r = ZZ(r)
S= mod((m+x*Y)/r,Gp)

print("The elliptic curve signature is the pair \n Y=", Y, "\n S=", S)