first pass of zero knowledge password auth, also some rsa or whatever

javascript.js

'use strict'

function generate_base_pair() {
  const first = generate_prime()
  var second = null
  while (second === null || second === first) {
    second = generate_prime()
  }
  return [first, second]
}

function binary_exponent(base, power, mod, phi_mod) {
  var res = 1

  if (phi_mod !== undefined) {
    power %= phi_mod
  }

  while (power !== 0) {
    if (power % 2 === 1) {
      res *= base
    }
    base *= base
    if (mod !== undefined) {
      res %= mod
      base %= mod
    }
    power = Math.floor(power/2)
  }

  return res;
}

function hash(str){
  var hash = 0
  if (str.length == 0) {
    return hash;
  }
  for (var i = 0; i < str.length; i++) {
    var char = str.charCodeAt(i)
    hash = ((hash<<5)-hash)+char
    hash = hash & hash // Convert to 32bit integer
  }
  return hash
}

function generate_prime() {
  const largest_possible = 10000
  var candidate_prime = Math.floor(largest_possible * Math.random())
  while(!check_prime(candidate_prime)) {
    candidate_prime = Math.floor(largest_possible * Math.random())
  }
  return candidate_prime
}

//millar-rabin primality test
function check_prime(n) {
  //base list from https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test#Deterministic_variants_of_the_test
  const base_list = [2, 3]

  if(base_list.indexOf(n) !== -1) {
    return true
  }

  var d = n - 1
  var s = 0

  while (d % 2 === 0) {
    s += 1
    d /= 2
  }

  function check(a, s, d, n) {
    var c = binary_exponent(a, d, n)
    var r = 0

    if (c == 1) {
      return true
    }

    while (r < s) {
      if (c == n - 1) {
        return true
      }
      c = (c*c) % n
      r += 1
    }
    return false
  }

  for (var i = 0; i < base_list.length; i++) {
    if (!check(base_list[i], s, d, n)) {
      return false
    } 
  }
  return true
}


function gcd(a, b) {
  if (b === 0) {
    return a
  } else { 
    return gcd(b, a % b)
  }
}


function inverse(a, n) {
  var t = 0
  var newt = 1
  var r = n
  var newr =  a
  while (newr !== 0) {
    var quotient = Math.floor(r/newr)
    var oldt = t
    var oldr = r
    t = newt
    newt = oldt - quotient * newt
    r = newr
    newr = oldr - quotient * newr
  }
  if (r !== 1) {
    console.log(a + " not invertable mod " + n)
    return null
  }
  if (t < 0) {
    t += n
  }
  return t
}

class rsa {
  constructor() {
    const primes = generate_base_pair()
    const first_prime = primes[0]
    const second_prime = primes[1]
    this.phi_base = (first_prime - 1)*(second_prime - 1)
    this.base = first_prime*second_prime
  }

  generate_key_pair() {
    var candidate_key = Math.floor(this.base * Math.random())
    while (gcd(this.phi_base, candidate_key) !== 1) {
        candidate_key = Math.floor(this.phi_base * Math.random())
    }
    return [candidate_key, inverse(candidate_key, this.phi_base)]
  }

  encrypt(m, k) {
    return binary_exponent(m, k, this.base, this.phi_base)
  }

  decrypt(m, k) {
    return binary_exponent(m, k, this.base, this.phi_base)
  }
}


const RSA = new rsa()

const keys = RSA.generate_key_pair()
const pub_key = keys[0]
const priv_key = keys[1]
const m = Math.floor(Math.random() * RSA.base)

// start zk auth


class Server {
  constructor(user) {
    this.user = user
  }

  get_token() {
    this.token = Math.floor(Math.random() * RSA.base)
    return this.token
  }

  store(username, password_token) {
    this.user = [username, password_token]
  }

  auth(user_hash, key_exp) {
    var user_password_token = this.user[1]
    var computed_user_token = (RSA.encrypt(user_password_token, user_hash) * RSA.encrypt(pub_key, key_exp)) % RSA.base
    var computed_hash = hash(this.token) + hash(user_password_token) + hash(computed_user_token)
    return user_hash === computed_hash
  }
}

class User {
  constructor(name, password) {
    this.name = name
    this.password_hash = hash(password)
    this.password_token = RSA.encrypt(pub_key, hash(password))
  }

  login(server) {
    var server_token = server.get_token()
    var token_exp = Math.floor(Math.random() * RSA.phi_base)
    var user_token = RSA.encrypt(pub_key, token_exp)
    var valid_hash = hash(user_token) + hash(server_token) + hash(this.password_token)
    return server.auth(valid_hash, token_exp - valid_hash*this.password_hash)
  }

  register(server) {
    server.store(this.name, this.password_token)
  }
}

var user = new User('Jack Balmer', 'i am awesome')
var server = new Server()
user.register(server)

console.log(user.login(server))

python.py

from random import random


def generate_base_pair():
    first = generate_prime()
    second = generate_prime(first)
    return first, second


def generate_prime(exclude=None):
    largest_possible = 1373653
    candidate_prime = int(largest_possible * random())
    while candidate_prime == exclude or not check_prime(candidate_prime):
        candidate_prime = int(largest_possible * random())
    return candidate_prime


# millar-rabin primality test
def check_prime(n):
    # base list from https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test#Deterministic_variants_of_the_test
    base_list = [2, 3]

    if n in base_list:
        return True

    d = n - 1
    s = 0
    while d % 2 == 0:
        s += 1
        d /= 2

    def check(a, s, d, n):
        c = a**d % n
        r = 0
        if c == 1:
            return True
        while r < s:
            if c == n - 1:
                return True
            c = c**2 % n
            r += 1
        return False

    return reduce(lambda x, y: x and y,
                  map(lambda x: check(x, s, d, n),
                      base_list
                      )
                  )


def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


def inverse(a, n):
    t, newt = 0, 1
    r, newr = n, a
    while newr != 0:
        quotient = r // newr
        t, newt = newt, t - quotient * newt
        r, newr = newr, r - quotient * newr
    if r != 1:
        print str(a) + " not invertable mod " + str(n)
        return None
    if t < 0:
        t += n
    return t


def binary(a):
    if not a:
        return [0]
    res = []
    while a != 0:
        res.append(a % 2)
        a = a // 2
    return res


def power(a, b, n, phi_n=None):
    if phi_n is not None:
        b %= phi_n
    elem = a % n
    if elem < 0:
        elem += n
    bucket = binary(b)
    res = elem if bucket.pop(0) else 1
    while bucket:
        elem = (elem * elem) % n
        res = (res * elem) % n if bucket.pop(0) else res
    return res


class rsa:
    def __init__(self, first_prime=None, second_prime=None):
        if first_prime is None:
            first_prime, second_prime = generate_base_pair()
        if second_prime is None:
            second_prime = generate_prime(first_prime)
        self.phi_base = (first_prime - 1)*(second_prime - 1)
        self.base = first_prime*second_prime

    def generate_key_pair(self):
        candidate_key = int(self.base * random())
        while gcd(self.phi_base, candidate_key) != 1:
            candidate_key = int(self.phi_base * random())
        return candidate_key, inverse(candidate_key, self.phi_base)

    def encrypt(self, m, k):
        return power(m, k, self.base, self.phi_base)

    def decrypt(self, m, k):
        return power(m, k, self.base, self.phi_base)


RSA = rsa()


pub_key, priv_key = RSA.generate_key_pair()
m = int(random() * RSA.base)
assert RSA.decrypt(RSA.encrypt(m, pub_key), priv_key) == m

# start zk auth


class Server:
    def __init__(self, user=None):
        self.user = user

    def get_token(self):
        self.token = int(random() * RSA.base)
        return self.token

    def store(self, username, password_token):
        self.user = (username, password_token)

    def auth(self, user_hash, key_exp):
        user_password_token = self.user[1]
        computed_user_token = (RSA.encrypt(user_password_token, user_hash) * RSA.encrypt(pub_key, key_exp)) % RSA.base
        computed_hash = hash(self.token) + hash(user_password_token) + hash(computed_user_token)
        return user_hash == computed_hash


class User:
    def __init__(self, name, password):
        self.name = name
        self.password_hash = hash(password)
        self.password_token = RSA.encrypt(pub_key, hash(password))

    def login(self, server):
        server_token = server.get_token()
        token_exp = int(random() * RSA.phi_base)
        user_token = RSA.encrypt(pub_key, token_exp)
        valid_hash = hash(user_token) + hash(server_token) + hash(self.password_token)
        return server.auth(valid_hash,
                           token_exp - valid_hash*self.password_hash
                           )

    def register(self, server):
        server.store(self.name, self.password_token)


user = User('Jack Balmer', 'i am awesome')
server = Server()
user.register(server)

assert user.login(server)