Mathematical Cryptography

import random as rand
from math import gcd, log

#this function factors all of the available powers
#of 2 out of n-1
def twofactor(n):
  m = n -1
  i, q, r = 0,0,0
  while True:
    q, r = divmod(m, 2)
    if r == 1:
      break
    m = q
    i = i + 1
  return m,i

#this function performs one round of the Miller-Rabin test
#for compositeness. The witnesses are randomly generated.
def millerrabin(n):
  if n%2 == 0:
    return True
  else:
    a = rand.randint(1, n-1)
    if gcd(a,n) != 1:
      return True

    q,k = twofactor(n)
    i = 0
    a = pow(a,q,n)
    if a ==1%n:
      return False

    while i < k:
      if a == -1 %n:
        return False
      a = a**2%n
      i = i + 1
    else:
      return True


#main function to run the Miller-Rabin test N times --
#uses a float to calculate probability of primaility given N loops
def main():
  n = int(input("Input an integer to test:"))
  N = int(input("Enter number of witnesses to test:"))
  for i in range(1,N):
    if millerrabin(n) == True:
      print("Composite")
      break
    else:
      prob = 1 - log(n)/4**N
      print("Prime likelihood is approx %f" %prob)
      break

from math import floor

def mixer(g,h,x,p, a, b):
    x = x%p
    if x < floor(p/3):
        return g*x%p, a+1%(p-1), b%(p-1)
    elif x < floor(2*p/3):
        return x**2%p, 2*a%(p-1), 2*b%(p-1)
    else:
        return x*h, a%(p-1), b+1%(p-1)

def xgcd(a, b):
    """return (g, x, y) such that a*x + b*y = g = gcd(a, b)"""
    x0, x1, y0, y1 = 0, 1, 1, 0
    while a != 0:
        q, b, a = b // a, a, b % a
        y0, y1 = y1, y0 - q * y1
        x0, x1 = x1, x0 - q * x1
    return b, x0, y0

def collision():
    x = 1
    y = 1
    g = 19
    h = 24717
    p = 48611
    ax = 0
    bx = 0
    ay = 0
    by = 0
    while True:
        x, ax, bx = mixer(g,h,x,p,ax,bx)
        y, ay, by = mixer(g,h,y,p,ay,by)
        y, ay, by = mixer(g,h,y,p,ay,by)
        if x == y:
            break
    print(x,y, ax, bx, ay, by)
    u = (ax - ay)%(p-1)
    v = (by - bx)%(p-1)
    print(u,v)
    d, s, t = xgcd(v,p-1)
    print(d, s, t)
    s = abs(s)
    print(s)
    w = s*u %(p-1)
    print(w)
    powers = [int(w/d + k*(p-1)/d) for k in range(0,d-1)]
    print(powers)
    for i in powers:
        if pow(g,i,p) == h%p:
            log = i
            break
    print(i)
    print(pow(g,log,p))

def modinv(x,p):
    return pow(x,p-2,p)

def elliptic_add(P, Q, A, p):
    if P == (0,0):
        return Q
    elif Q == (0,0):
        return P
    else:
        xP, yP = P[0], P[1]
        xQ, yQ = Q[0], Q[1]
    if xP == xQ and yP == (-yQ)%p:
        return (0,0)
    else:
        if xP == xQ and yP == yQ:
            m = ((3*xP**2 + A) * pow(2*yP, p-2, p) )%p
        else:
            m = ((yQ - yP)*pow(xQ - xP, p-2, p)) %p
        xR = (m**2 - xP - xQ) %p
        yR = (m*(xP - xR) - yP) %p
        return (xR, yR)

from math import floor
def double_add(P, n, A, p):
    Q = P
    R = (0,0)
    while n > 0:
        if 1 == n %2:
            R = elliptic_add(R, Q, A, p)
        Q = elliptic_add(Q, Q, A, p)
        n = floor(n/2)
    return R

def elliptic_point_order(P, A, p):
    Q = elliptic_add(P,P, A, p)
    count = 1
    while Q != P:
        Q = elliptic_add(Q, P, A, p)
        count = count + 1
    return count

def elliptic_dsa_keygen(G, s, q, A, p):
    s = s % (q - 1)
    V = double_add(G, s, A, p)
    return V

from random import randint

def elliptic_dsa_sign(d, s, G, q, A, p):
    d = d % q
    e = randint(1,q-1)
    einv = pow(e, q-2, q)
    rand_point = double_add(G, e, A, p)
    s1 = rand_point[0] %q
    s2 = ((d + s*s1)*einv) %q
    return (s1,s2)

def elliptic_dsa_verify(d, V, sig, G, q, A, p):
    s1, s2 = sig[0], sig[1]
    v1 = (d*modinv(s2,q))%q
    v2 = (s1*modinv(s2,q))%q
    print(v1, v2)
    check1 = double_add(G, v1, A, p)
    print(check1)
    check2 = double_add(V, v2, A, p)
    print(check2)
    check = elliptic_add(check1, check2, A, p)
    print(s1)
    print(check[0] %q)