Jon's FOSS Blog

Anything networking, coding, crypto, or security

Quick Blog Summary

Having fun with numbers and Python

import sys,time
def hexs(s):
	o = ""
	for c in s:
		h = hex(ord(c))[2:]
		if (len(h) < 2):
			h = ("0" + h)
		if (o != ""):
			o += ":"
		o += h
	return o
def nice(s):
	o = ""
	for i in range(0, len(s)):
		if (i > 0):
			if ((i % 16) == 0):
				o += "\n  "
			else:
				o += ":"
		t = str(s[i])
		while (len(t) < 3):
			t = ("0" + t)
		o += t
	return o
def rnds():
	n = 2; s = ""
	while ((int(time.time()) % n) != 0):
		pass
	while (len(s) != 32):
		time.sleep(1)
		r = 0
		while ((int(time.time()) % n) != 0):
			r = (r + 1)
		#sys.stderr.write("r="+str(r)+"\n");break
		s = (s + chr((r >> 8) & 0xff) + chr(r & 0xff))
	return s
if (len(sys.argv) < 2):
	h = rnds()
	sys.stderr.write("k="+hexs(h)+"\n")
else:
	def keys(k):
		s = []
		for x in range(0, 256):
			s.append(x)
		for y in range(0, len(k)):
			l = ord(k[y])
			for x in range(0, 256):
				t = s[x] ; s[x] = s[l] ; s[l] = t
				l = ((l + x) % 256)
		return s
	s = keys(sys.argv[1])
	if (len(sys.argv) > 2):
		sys.stderr.write("s="+nice(s)+"\n\n")
	def ciph(m, s, z):
		j = 0; o = ""
		for y in range(0, len(m)):
			l = ord(m[y])
			c = (l ^ s[y % 256])
			o += chr(c)
			i = l
			if (z == "d"):
				i = c
			j = ((j ^ i) % 256)
			for x in range(0, 256):
				t = s[x] ; s[x] = s[j] ; s[j] = t
				j = ((j + x) % 256)
		return o
	if (len(sys.argv) < 3):
		m = sys.stdin.read()
		z = "d"
	else:
		m = sys.argv[2]
		z = "e"
	o = ciph(m, s, z)
	if (len(sys.argv) > 2):
		sys.stderr.write("m="+hexs(o)+"\n")
	sys.stdout.write(o)

$ clear ; echo ; python fun.py ; python fun.py ; echo ; python fun.py key msg | python fun.py key ; echo

k=74:ed:3c:1d:62:72:92:61:3c:27:f8:7c:c4:98:92:47:0d:18:c0:47:a6:44:b6:13:19:5c:90:30:4b:23:cf:12
k=fd:e7:4d:1d:c7:b0:a6:d9:45:0e:c9:68:95:35:46:e9:08:e9:8c:4f:53:42:9d:29:7b:30:65:f6:cd:00:ae:f6

s=054:166:020:190:252:207:029:030:042:098:156:055:041:108:058:032
  073:208:253:242:115:250:053:106:192:168:087:173:045:161:124:186
  163:049:162:067:040:096:086:039:057:023:100:216:203:123:217:175
  248:107:224:131:038:172:014:011:085:003:214:149:110:215:159:129
  046:125:144:043:077:126:150:167:200:169:097:153:188:201:071:254
  246:244:080:184:232:010:006:176:241:183:019:027:118:090:104:065
  000:033:210:220:236:234:063:205:048:155:095:133:218:050:022:158
  130:068:221:170:202:079:213:101:164:111:099:074:034:239:082:238
  031:181:092:230:088:017:007:251:083:193:051:245:237:209:064:070
  016:139:013:037:113:180:119:009:191:148:026:189:136:059:142:233
  056:160:243:135:076:165:012:035:222:212:231:084:249:061:152:093
  255:015:174:178:223:102:052:177:021:062:117:028:225:105:025:069
  121:002:227:122:143:047:134:137:146:219:194:060:005:089:044:140
  182:247:147:145:179:198:075:081:138:094:109:141:151:116:187:127
  103:128:001:132:036:154:066:112:078:196:229:004:226:211:206:199
  091:072:171:008:114:228:197:157:240:120:185:235:018:204:195:024

m=5b:c4:90
msg

Basic HTTPS TLS Proxy Server In Python

#!/usr/bin/python
# Usage: ./net.py
# Description: Proof-of-concept HTTPS proxy script to hide the domain name in a TLS connection
#              so that firewalling appliances can't see who you are trying to connect to.
# Example setup: Edit ../hosts to include "127.0.0.1 imgur.com"
# Browser: http://imgur.com
#          -> TCP 127.0.0.1 80 (Python is listening & reads headers "GET / && Host imgur.com")
#          -> UDP 4.2.2.1 53 (Python performs DNS query on "imgur.com" [non-hosts file lookup])
#          -> TCP 1.2.3.4 443 (Python connects to TLS server & sends headers over encrypted channel [non-cert verify])
#          -> HTTPS response data is proxied back to browser localhost connection
# Warning: This script is very slow and insecure

import re
import socket
import ssl
import subprocess
import SocketServer

resolv = {}

class MyTCPHandler(SocketServer.BaseRequestHandler):
    def handle(self):
        global resolv
        
        heads = self.request.recv(10024).strip().split("\n")
        
        page = ""; host = ""
        for head in heads:
            match = re.match("^get ([^ ]+).*$", head.strip(), re.I)
            if (match):
                page = match.group(1)
            match = re.match("^host: ([^ ]+).*$", head.strip(), re.I)
            if (match):
                host = match.group(1)
        
        if ((not page) or (not host)):
            print("err",heads)
        else:
            addr = ""
            if (host in resolv.keys()):
                addr = resolv[host]
            else:
                looks = subprocess.check_output(["nslookup", host]).split("\n")
                for look in looks:
                    match = re.match("^address:[ ]+([^ ]+).*$", look.strip(), re.I)
                    if (match):
                        addr = match.group(1)
                resolv[host] = addr
            
            print(page,host,addr)
            
            context = ssl.SSLContext(ssl.PROTOCOL_TLSv1_2)
            context.verify_mode = ssl.CERT_NONE
            context.check_hostname = False
            conn = context.wrap_socket(socket.socket(socket.AF_INET), server_hostname=addr)
            conn.connect((addr, 443))
            conn.sendall("GET "+page+" HTTP/1.1\r\n"+"Host: "+host+"\r\n"+"Connection: close\r\n"+"\r\n")
            
            resp = "";
            while (1):
                temp = conn.recv(10024)
                if (not temp):
                    break
                resp += temp
            self.request.sendall(resp)

if (__name__ == "__main__"):
    (HOST, PORT) = ("127.0.0.1", 80)
    server = SocketServer.TCPServer((HOST, PORT), MyTCPHandler)
    server.serve_forever()

A cool SSH auto password program – sshpass – for sys admin remote automation (probably should use keys instead tho)

#!/usr/bin/python
# Usage: ./sshpw.py <password> ssh user@host
# Description: This is a demo SSH auto password login script via a pseudo tty device (stolen from sshpass - not recommended obviously!)
# Note: This is a rough example script which assumes you have already accepted the fingerprint & have the right password

import os, sys, time

import glob, struct, termios, fcntl, pty

from ctypes import *

libc = cdll.LoadLibrary(glob.glob("/lib/*-linux-gnu/libc-*.so")[0])

(master, slave) = pty.openpty()
#fcntl.fcntl(master, fcntl.F_SETFL, os.O_NONBLOCK)

libc.ptsname.restype = c_char_p
name = libc.ptsname(c_int(master))
slavept = -10

ourtty = os.open("/dev/tty", 0)

s = struct.pack("HHHH", 0, 0, 0, 0)
t = fcntl.ioctl(ourtty, termios.TIOCGWINSZ, s)
fcntl.ioctl(master, termios.TIOCSWINSZ, t)

pidn = os.fork()

if (pidn == 0):
	os.setsid()
	slavept = os.open(name, os.O_RDWR)
	os.close(slavept)
	os.close(master)
	os.execvp(sys.argv[2], sys.argv[2:])
	os._exit(0)

else:
	slavept = os.open(name, os.O_RDWR|os.O_NOCTTY)
	print("["+os.read(master, 128)+"]")
	os.write(master, sys.argv[1] + "\r\n")
	os.wait()


Basic LinkedIn Resume Customizer

LinkedIn recently disabled it’s third party APIs which took out an auto-resume builder service based on my public profile. I wrote some JS to try and at least generate a basic resume from my LinkedIn profile now:

/* hide non-important elements */
document.getElementsByTagName("header")[0].style.display = "none";
for (var x = 0; x < 2; ++x) {
  document.getElementsByClassName("reg-upsell")[x].style.display = "none";
  document.getElementsByTagName("footer")[x].style.display = "none";
}
document.getElementById("aux").style.display = "none";
document.getElementById("directory").style.display = "none";
document.getElementById("groups").style.display = "none";
document.getElementById("volunteering").style.display = "none";
/* re-size important elements */
var wide = 945;
document.body.style.backgroundColor = "white";
document.body.style.paddingLeft = "32px";
document.getElementById("wrapper").style.backgroundColor = "white";
document.getElementById("wrapper").style.marginTop = "32px";
document.getElementById("profile").style.width = wide + "px";
document.getElementsByClassName("profile-overview")[0].style.width = (wide - 256) + "px";
/* adjust the profile picture */
document.getElementsByClassName("profile-picture")[0].style.marginTop = "8px";
document.getElementsByClassName("profile-picture")[0].style.marginBottom = "8px";
document.getElementsByClassName("profile-picture")[0].style.paddingLeft = "8px";
document.getElementsByClassName("profile-picture")[0].getElementsByTagName("img")[0].style.boxShadow = "none";
/* add a left side border to the resume sections */
var l = document.getElementsByClassName("profile-section");
for (var i = 0; i < l.length; ++i) {
  try {
    l[i].style.boxShadow = "none";
    l[i].style.borderLeft = "2px solid #444444";
    l[i].style.borderRadius = "2px";
    var hr = document.createElement("hr");
    hr.style.borderTop = "1px solid #ddd";
    hr.style.borderBottom = "0px";
    hr.style.margin = "0px 0px 0px 8px";
    hr.style.width = "97%";
    l[i].appendChild(hr);
  }
  catch(e) { }
}
/* see more skills */
document.getElementsByClassName("see-more")[0].getElementsByTagName("*")[0].click();
document.getElementsByClassName("see-less")[0].getElementsByTagName("*")[0].style.display = "none";
/* remove the box shadow on skills and interests */
var s = document.getElementsByClassName("skill");
for (var i = 0; i < s.length; ++i) {
  try {
    s[i].style.boxShadow = "none";
  }
  catch(e) { }
}
var s = document.getElementsByClassName("interest");
for (var i = 0; i < s.length; ++i) {
  try {
    s[i].style.boxShadow = "none";
  }
  catch(e) { }
}
/* load all images instead of their load delays */
var t = document.getElementsByTagName("img");
for (var i = 0; i < t.length; ++i) {
  try {
    var d = t[i].getAttribute("data-delayed-url");
    if (d && d.match(/^.*http.*$/i)) {
      t[i].parentNode.innerHTML = ("<img src='"+d+"' />");
    }
  }
  catch(e) { }
}
/* allow the user to click on a section to move it up or down */
var u = document.getElementsByTagName("li");
for (var i = 0; i < u.length; ++i) {
  try {
    u[i].onclick = function() {
      var v = this.parentNode.getElementsByTagName("li");
      for (var j = 0; j < v.length; ++j) {
        if (v[j] == this) {
          var p = parseInt(prompt("Move:"));
          if (j == 0) { v[j].parentNode.parentNode.style.marginTop = (p + "px"); }
          else { v[j-1].style.paddingBottom = (p + "px"); }
          location.href = location.href.replace(/#.*$/ig,"") + "#" + p;
        }
      }
    }
  }
  catch(e) { }
}
/* add some white space to the end so we can cut it off nicely */
for (var i = 0; i < 100; ++i) {
  var br = document.createElement("br");
  document.body.appendChild(br);
}
/* translate external links so they are visible */
var v = document.getElementsByTagName("a");
for (var i = 0; i < v.length; ++i) {
  if (v[i].href.match(/^.*redirect.*$/i)) {
    v[i].innerHTML = decodeURIComponent(v[i].href).replace(/^.*url=[^\/]*\/\//i, "").replace(/&.*$/i, "");
  }
}
/* turn stars into bullet points */
var ps = document.getElementsByTagName("p");
for (var i = 0; i < ps.length; ++i) {
  if (ps[i].innerHTML.replace(/[\t\r\n]/ig, " ").match(/^.*\*.*$/i)) {
    ps[i].innerHTML = ps[i].innerHTML.replace(/\*/ig, "&bull;");
  }
}

From LinkedIn Profile -to- Example Resume with a little bit of effort! (works best in Chrome with print-to-PDF graphics enabled & no headers/margins set)

Using a good Curve (25519) to implement a Dual_EC_DRBG based PRNG (bad) in Py

('(secret)', 'e=17211717500188099600568359980754843411619158773615107210604175251693280840607')

('(pub)', 'P', [15395204427582176828288140787842485523287609441875116301821962120815246523165L, 50972925492742860438904710940702337165443708937045978727200475339385656596802L])
('(pub)', 'Q', [54379753906375494870435841730857804485220282788952166778590221998932647140003L, 10542862410506568609831388869015874299228416047841839543681429954753256816461L])

Running first 3 prng outputs:
(1, '(pub)', 'rQ', [35085355371653225423586630859880842591953206407407058841980055259804158729190L, 17642611272178418467727837731595189739886826601909812633308152323681611088547L])
(2, '(pub)', 'rQ', [49239914602839976828302644790025511534554523065665058491590572885136905915179L, 8379389248907743775496938151971165397933498701999710225313910125914506554304L])
(3, '(pub)', 'rQ', [46183005535555809253746127552459776700939930656325949263490016267446108722393L, 39473869171813125431282259087083131250343325900631309529780555199432408899154L])

Predicting next prng output:
(4, '(pub)', 'sQ', [41709487842035263418257031106229715942424730101066821754384094668791902320545L, 47532264341329149594994883777108416347984877171111029279692175022666589952933L])
Running next prng output:
(4, '(pub)', 'rQ', [41709487842035263418257031106229715942424730101066821754384094668791902320545L, 47532264341329149594994883777108416347984877171111029279692175022666589952933L])
import sys
import random

def egcd(a, b):
	s = 0; news = 1
	r = b; newr = a
	while r != 0:
		quot = (newr / r)
		prev = s
		s = (news - (quot * prev))
		news = prev
		prev = r
		r = (newr - (quot * prev))
		newr = prev
	if (news < 0):
		news += b
	return news

def dub(p, a, b, n):
	# l = 3*x^2 + 2*a*x + 1 / 2*b*y
	xx = pow(p[0], 2, n)
	ya = (((3 * xx) + (2 * a * p[0]) + 1) % n)
	yd = ((2 * b * p[1]) % n)
	l = ((ya * egcd(yd, n)) % n)
	# xr = b*l^2 - a - 2*x
	ll = pow(l, 2, n)
	newx = (((b * ll) - a - (2 * p[0])) % n)
	# yr = ((3*x + a) * l) - b*l^3 - y
	yb = (((3 * p[0]) + a) % n)
	newy = (((yb * l) - (b * ll * l) - p[1]) % n)
	return [newx, newy]

def add(p, q, a, b, n):
	# l = (Qy - Py) / (Qx - Px)
	ya = ((q[1] - p[1]) % n)
	yd = ((q[0] - p[0]) % n)
	l = ((ya * egcd(yd, n)) % n)
	# xr = b*l^2 - a - Px - Qx
	ll = pow(l, 2, n)
	newx = (((b * ll) - a - p[0] - q[0]) % n)
	# yr = ((2*Px + Qx + a) * l) - b*l^3 - Py
	yb = (((2 * p[0]) + q[0] + a) % n)
	yc = ((b * ll * l) % n)
	newy = ((((yb * l) % n) - yc - p[1]) % n)
	return [newx, newy]

def mul(m, p, a, b, n):
	r = None
	while (m > 0):
		if ((m % 2) == 1):
			if (r == None):
				r = p
			else:
				r = add(r, p, a, b, n)
		p = dub(p, a, b, n)
		m = (m >> 1)
	return r

a = 486662
b = 1
n = 57896044618658097711785492504343953926634992332820282019728792003956564819949
try:
	p = [int(sys.argv[2]), int(sys.argv[3])]
except:
	p = [9, 43114425171068552920764898935933967039370386198203806730763910166200978582548]

# e is our secret key here
d = random.randint(3, n - 3)
e = random.randint(3, n - 3)
print("(secret)","e=%d"%e)
print("")

# let G = any base point
# calculate public point constants: P = edG & Q = dG
g = mul(d, p, a, b, n)
g = mul(e, g, a, b, n)
print("(pub)","P",g)
h = mul(d, p, a, b, n)
print("(pub)","Q",h)
print("")

# multiply random seed with the points: P' = rP & Q' = rQ
# these then equate to: P' = redG & Q' = rdG
# the 'key' to this is basing the next r' off of the output of P' and publishing the point info of Q' and repeat
r = random.randint(3, n - 3)
print("Running first 3 prng outputs:")
for x in range(1, 4):
	t = mul(r, g, a, b, n)
	u = mul(r, h, a, b, n)
	print(x,"(pub)","rQ",u)
	r = ((t[0] + t[1]) % n)
print("")

# to predict the next output then multiply: eQ' == erdQ == erdG == redG == P'
# you can now get r' and calculate the next P'' & Q''
print("Calculating next prng output (using e & latest Q):")
z = mul(e, [u[0], u[1]], a, b, n)
s = ((z[0] + z[1]) % n)
v = mul(s, z, a, b, n)
w = mul(s, h, a, b, n)
print(x+1,"(pub)","sQ",w)

# just to be sure
print("Running next prng output:")
for y in range(0, 1):
	t = mul(r, g, a, b, n)
	u = mul(r, h, a, b, n)
	print(x+1,"(pub)","rQ",u)
	r = ((t[0] + t[1]) % n)
print("")

Secure Message iOS App in Swift

Using: Curve25519-ECDH, SHA256-HMAC, AES256-CBC — [Link to the GitHub Project Repo]

 
tcpdump pcap

01:07:18.371915 IP 192.168.1.171.64115 > 31.170.162.63.80: Flags [P.], seq 258:712, ack 1, win 8192, length 454: HTTP
mode=mesg&user=bob&rcpt=jon&mesg=key,31237969521267061265339920357754601118035663355449910125550985699827426505154,7903087581924324533759768883989441673564165222638106623548350836149345932721
--
01:07:18.783449 IP 31.170.162.63.80 > 192.168.1.171.64116: Flags [P.], seq 1:353, ack 539, win 250, length 352: HTTP: HTTP/1.1 200 OK
1450084038.47668400.66932:bob:key,31237969521267061265339920357754601118035663355449910125550985699827426505154,7903087581924324533759768883989441673564165222638106623548350836149345932721
--
01:07:19.547229 IP 192.168.1.171.64117 > 31.170.162.63.80: Flags [P.], seq 258:712, ack 1, win 8192, length 454: HTTP
mode=mesg&user=jon&rcpt=bob&mesg=key,20845162869924781138108110300526986101524551329253196414272755241823588505763,3845740679180735844612211279137657051909097428357280103024866020367868787613
--
01:07:20.637809 IP 31.170.162.63.80 > 192.168.1.171.64118: Flags [P.], seq 1:353, ack 539, win 250, length 352: HTTP: HTTP/1.1 200 OK
1450084039.65591500.56627:jon:key,20845162869924781138108110300526986101524551329253196414272755241823588505763,3845740679180735844612211279137657051909097428357280103024866020367868787613
--
01:07:30.861632 IP 192.168.1.171.64123 > 31.170.162.63.80: Flags [P.], seq 258:672, ack 1, win 8192, length 414: HTTP
mode=mesg&user=bob&rcpt=jon&mesg=msg,471776850.748092,8017053b9ea82e9d52e41052cc3518cd,8bd681694098a46a6ffbb01158672929d1fc5f3859f3fc5cc5030de8e4ed6d6e
--
01:07:33.788855 IP 31.170.162.63.80 > 192.168.1.171.64124: Flags [P.], seq 1:313, ack 539, win 250, length 312: HTTP: HTTP/1.1 200 OK
1450084050.96252100.73649:bob:msg,471776850.748092,8017053b9ea82e9d52e41052cc3518cd,8bd681694098a46a6ffbb01158672929d1fc5f3859f3fc5cc5030de8e4ed6d6e

/* c helper swift functions */

bnum *getx(ecc *e) { return e->x; }
bnum *gety(ecc *e) { return e->y; }

ecc *eccryp()
{
	char *a = "486662", *b = "1", *p = "57896044618658097711785492504343953926634992332820282019728792003956564819949";
	char *x = "9", *y = "43114425171068552920764898935933967039370386198203806730763910166200978582548";
	bnum *t, *u, *v, *w;
	ecc *e;
	
	t = bndec(p);
	u = bninit(t->size); w = bndec(x); bncopy(w, u); bnfree(w);
	v = bninit(t->size); w = bndec(y); bncopy(w, v); bnfree(w);
	e = ecinit(bndec(a), bndec(b), t, u, v);
	
	return e;
}

bnum *bnrnd(int size)
{
	FILE *f;
	bnum *r;
	
	r = bninit(size);
	f = fopen("/dev/urandom", "r");
	fread(r->nums, sizeof(unsigned int), size - 1, f);
	fclose(f);
	r->leng = size;
	while ((r->leng > 1) && (r->nums[r->leng - 1] == 0)) { r->leng -= 1; }
	
	return r;
}

/*
 Curve25519: a=486662, b=1, p=2^255 - 19
 ECC DH: o * (n * P) == onP == noP == n * (o * P)
 */

char *ecdh(ecc *e, const char *n)
{
	char *r = (char *)n;
	bnum *m;
	ecc *f;
	
	if (r == NULL)
	{
		m = bnrnd((e->p)->size);
		r = bnstr(m);
	}
	
	else
	{
		m = bndec((char *)n);
	}
	
	f = ecdup(e);
	pmul(m, e, f);
	
	(f->x)->leng = min((f->x)->leng, (e->p)->size); bncopy(f->x, e->x);
	(f->y)->leng = min((f->y)->leng, (e->p)->size); bncopy(f->y, e->y);
	bnfree(m);
	ecfree(f);
	
	return r;
}

void setexy(ecc *e, const char *x, const char *y)
{
	bnum *t;
	t = bndec((char *)x); t->leng = min(t->leng, (e->p)->size);
	bncopy(t, e->x); bnfree(t);
	t = bndec((char *)y); t->leng = min(t->leng, (e->p)->size);
	bncopy(t, e->y); bnfree(t);
}

char *shash(const char *m)
{
	char *o = malloc(256);
	sha256 hobj;
	sha256init(&hobj);
	sha256update(&hobj, (unsigned char *)m, (unsigned int)strlen(m));
	sha256final(&hobj, o);
	return o;
}

char *sencr(const char *i, const char *m, const char *k, int d)
{
	int x, y, w, z = 0;
	unsigned long ilen = strlen(i), mlen = strlen(m), klen = strlen(k);
	unsigned char tmp[16], ivn[16], msg[16], key[256];
	char *hex = "0123456789abcdef";
	char *enc = malloc(3 * strlen(m));
	
	bzero(key, 256);
	for (x = 0; ((x + 1) < 64) && ((x + 1) < klen); x += 2)
	{
		for (y = 0; y < 16; ++y)
		{
			if (k[x] == hex[y]) { key[x / 2] |= (y << 4); }
			if (k[x + 1] == hex[y]) { key[x / 2] |= y; }
		}
	}
	aes256keys(key);
	
	for (x = 0; x < 16; ++x)
	{
		ivn[x] = 0;
		if (x < ilen) { ivn[x] = i[x]; }
	}
	
	x = 0;
	while (x < mlen)
	{
		if (d == 0)
		{
			for (y = 0; y < 16; ++y)
			{
				msg[y] = 0;
				if (x < mlen) { msg[y] = m[x]; ++x; }
				msg[y] ^= ivn[y];
			}
		}
		else
		{
			for (y = 0; y < 16; ++y)
			{
				msg[y] = 0;
				if ((x + 1) < mlen)
				{
					for (w = 0; w < 16; ++w)
					{
						if (m[x] == hex[w]) { msg[y] |= (w << 4); }
						if (m[x + 1] == hex[w]) { msg[y] |= w; }
					}
					x += 2;
				}
				tmp[y] = msg[y];
			}
		}
		
		aes256core(msg, key, d);
		
		if (d == 0)
		{
			for (y = 0; y < 16; ++y)
			{
				enc[z] = hex[(msg[y] >> 4) & 0xf]; ++z;
				enc[z] = hex[msg[y] & 0xf]; ++z;
				ivn[y] = msg[y];
			}
		}
		else
		{
			for (y = 0; y < 16; ++y)
			{
				enc[z] = (msg[y] ^ ivn[y]); ++z;
				ivn[y] = tmp[y];
			}
		}
	}
	enc[z] = 0;
	
	return enc;
}

char *hmac(const char *m, const char *k)
{
	int x, y, i, j, bs = 64;
	unsigned long mlen = strlen(m), klen = strlen(k);
	char *hex = "0123456789abcdef", *hmout = malloc(256);
	unsigned char key[bs], ipad[bs], opad[bs];
	sha256 hobj;
	
	bzero(key, bs);
	for (x = 0; ((x + 1) < 64) && ((x + 1) < klen); x += 2)
	{
		for (y = 0; y < 16; ++y)
		{
			if (k[x] == hex[y]) { key[x / 2] |= (y << 4); }
			if (k[x + 1] == hex[y]) { key[x / 2] |= y; }
		}
	}
	
	for (x = 0; x < bs; ++x)
	{
		ipad[x] = (0x36 ^ key[x]);
		opad[x] = (0x5C ^ key[x]);
	}
	
	sha256init(&hobj);
	sha256update(&hobj, ipad, bs);
	sha256update(&hobj, (unsigned char *)m, (unsigned int)mlen);
	sha256final(&hobj, hmout);
	
	for (x = 0; x < 8; ++x)
	{
		for (y = 0; y < 4; ++y)
		{
			i = ((x * 4) + y);
			j = (24 - (y * 8));
			key[i] = ((hobj.h[x] >> j) & 0xff);
		}
	}
	
	sha256init(&hobj);
	sha256update(&hobj, opad, bs);
	sha256update(&hobj, key, 32);
	sha256final(&hobj, hmout);
	
	return hmout;
}

//
//  ViewController.swift
//  smsg
//

import UIKit

class ViewController: UIViewController, UITableViewDelegate, UITableViewDataSource {

	let userText: UITextField = UITextField(frame: CGRect(x: 10.00, y: 32.00, width: 200.00, height: 30.00))
	let passText: UITextField = UITextField(frame: CGRect(x: 10.00, y: 64.00, width: 200.00, height: 30.00))
	let authButn: UIButton = UIButton(frame: CGRect(x: 225.00, y: 64.00, width: 100.00, height: 30.00))
	
	let frndText: UITextField = UITextField(frame: CGRect(x: 10.00, y: 96.00, width: 200.00, height: 30.00))
	let frndButn: UIButton = UIButton(frame: CGRect(x: 225.00, y: 96.00, width: 100.00, height: 30.00))
	let seckText: UILabel = UILabel(frame: CGRect(x: 10.00, y: 128.00, width: 300.00, height: 30.00))
	
	var mesgList: [String] = ["line 1", "line 2", "line 3"]
	let mesgHist: UITableView = UITableView(frame: CGRect(x: 10.00, y: 160.00, width: 300.00, height: 120.00))
	let mesgText: UITextView = UITextView(frame: CGRect(x: 10.00, y: 284.00, width: 200.00, height: 60.00))
	let mesgButn: UIButton = UIButton(frame: CGRect(x: 225.00, y: 284.00, width: 100.00, height: 30.00))
	
	let vers = "1.9.9.1"
	let serv = "http://smsg.site88.net"
	var authkey: String = ""
	var dhkey: String = ""
	var dhx: String = ""
	var dhy: String = ""
	var skey: String = ""
	var tkey: String = ""
	var ecobj = eccryp()
	
	func readReply(mode: Int, response: String) {
		if (response != "") { print("r>"+response) }
		
		if (response.characters.count > 5)
		{
			if (mode == 0)
			{
				self.authkey = response.substringWithRange(Range<String.Index>(start:response.startIndex.advancedBy(5), end:response.endIndex))
				
				dispatch_async(dispatch_get_main_queue()) { self.seckText.text = (" " + self.authkey) }
			}
			
			else if (mode == 3)
			{
				let linelist = response.characters.split{$0 == "\n"}.map(String.init)
				for line in linelist
				{
					let readlist = line.characters.split{$0 == ":"}.map(String.init)
					if (readlist.count > 2)
					{
						let infolist = readlist[2].characters.split{$0 == ","}.map(String.init)
						
						if (infolist.count == 3)
						{
							if ((readlist[1] == frndText.text) && (infolist[0] == "key"))
							{
								if (self.dhkey == "")
								{
									self.dhkey = String.fromCString(ecdh(self.ecobj, nil))!
									self.dhx = String.fromCString(bnstr(getx(self.ecobj)))!
									self.dhy = String.fromCString(bnstr(gety(self.ecobj)))!
									self.sendMesg(1, mesg: self.dhx+","+self.dhy)
								}
								
								setexy(self.ecobj, infolist[1], infolist[2])
								ecdh(self.ecobj, self.dhkey)
								let tdhx = String.fromCString(bnstr(getx(self.ecobj)))
								let tdhy = String.fromCString(bnstr(gety(self.ecobj)))
								
								print("d>"+tdhx!+","+tdhy!)
								self.skey = String.fromCString(shash(tdhx!+","+tdhy!))!
								self.tkey = String.fromCString(shash(self.skey))!
								print("k>"+self.skey+","+self.tkey)
								dispatch_async(dispatch_get_main_queue()) { self.seckText.text = (" " + self.skey) }
							}
						}
						
						else if (infolist.count == 4)
						{
							if ((readlist[1] == frndText.text) && (infolist[0] == "msg"))
							{
								let smac = String.fromCString(hmac(infolist[1]+","+infolist[2], self.tkey))
								print("v>"+smac!+"=="+infolist[3])
								if (smac == infolist[3])
								{
									let smesg = String.fromCString(sencr(infolist[1], infolist[2], self.skey, 1))
									self.mesgList.append(smesg!)
									dispatch_async(dispatch_get_main_queue()) { self.mesgHist.reloadData() }
								}
							}
						}
					}
				}
			}
		}
	}
	
	func sendMesg(mode: Int, mesg: String) {
		var postdata: String = ""
		
		if (mode == 0)
		{
			postdata = ("mode=auth&user="+self.userText.text!+"&pass="+self.passText.text!)
		}
		
		else if (mode == 1)
		{
			postdata = ("mode=mesg&user="+self.userText.text!+"&auth="+self.authkey+"&rcpt="+self.frndText.text!+"&mesg=key,"+mesg)
		}
		
		else if (mode == 2)
		{
			postdata = ("mode=mesg&user="+self.userText.text!+"&auth="+self.authkey+"&rcpt="+self.frndText.text!+"&mesg=msg,"+mesg)
		}
		
		else if (mode == 3)
		{
			postdata = ("mode=read&user="+self.userText.text!+"&auth="+self.authkey)
		}
		
		let request = NSMutableURLRequest(URL: NSURL(string: self.serv)!)
		request.HTTPMethod = "POST"
		request.HTTPBody = postdata.dataUsingEncoding(NSUTF8StringEncoding)
		let task = NSURLSession.sharedSession().dataTaskWithRequest(request) {
			data, response, error in
			let reply = NSString(data: data!, encoding: NSUTF8StringEncoding)
			self.readReply(mode, response: reply as! String)
		}
		task.resume()
	}
	
	func butnPress(butn: UIButton) {
		if (butn.titleLabel?.text == "Login") { self.sendMesg(0, mesg: "") }
		if (butn.titleLabel?.text == "Add")
		{
			if (self.dhkey == "")
			{
				self.dhkey = String.fromCString(ecdh(self.ecobj, nil))!
				self.dhx = String.fromCString(bnstr(getx(self.ecobj)))!
				self.dhy = String.fromCString(bnstr(gety(self.ecobj)))!
			}
			self.sendMesg(1, mesg: self.dhx+","+self.dhy)
		}
		if (butn.titleLabel?.text == "Send")
		{
			if (self.skey != "")
			{
				let stime = String(NSDate.timeIntervalSinceReferenceDate())
				let smesg = String.fromCString(sencr(stime, self.mesgText.text, self.skey, 0))
				let smac = String.fromCString(hmac(stime+","+smesg!, self.tkey))
				self.sendMesg(2, mesg: stime+","+smesg!+","+smac!)
			}
		}
	}
	
	func tableView(tableView: UITableView, numberOfRowsInSection section: Int) -> Int {
		return self.mesgList.count
	}
	
	func tableView(tableView: UITableView, cellForRowAtIndexPath indexPath: NSIndexPath) -> UITableViewCell {
		let cell = UITableViewCell(style: UITableViewCellStyle.Default, reuseIdentifier: "cell")
		cell.textLabel!.text = self.mesgList[indexPath.row]
		cell.textLabel!.font = cell.textLabel!.font.fontWithSize(10)
		return cell
	}
	
	func backFunc(timer: NSTimer) {
		self.sendMesg(3, mesg: "")
	}
	
	override func viewDidLoad() {
		super.viewDidLoad()
		// Do any additional setup after loading the view, typically from a nib.
		
		print("i>draw init")
		
		/* login elements */
		
		let userPadd = UIView(frame: CGRectMake(0, 0, 5, self.userText.frame.size.height))
		self.userText.leftView = userPadd
		self.userText.leftViewMode = UITextFieldViewMode.Always
		self.userText.layer.cornerRadius = 2.0
		self.userText.layer.borderColor = UIColor(red: 0/255, green: 0/255, blue: 0/255, alpha: 1.0).CGColor
		self.userText.layer.borderWidth = 2.0
		self.userText.autocorrectionType = UITextAutocorrectionType.No
		self.userText.autocapitalizationType = UITextAutocapitalizationType.None
		self.view.addSubview(self.userText)
		
		let passPadd = UIView(frame: CGRectMake(0, 0, 5, self.passText.frame.size.height))
		self.passText.leftView = passPadd
		self.passText.leftViewMode = UITextFieldViewMode.Always
		self.passText.layer.cornerRadius = 2.0
		self.passText.layer.borderColor = UIColor(red: 0/255, green: 0/255, blue: 0/255, alpha: 1.0).CGColor
		self.passText.layer.borderWidth = 2.0
		self.passText.secureTextEntry = true
		self.view.addSubview(self.passText)
		
		self.authButn.layer.cornerRadius = 2.0
		self.authButn.layer.borderColor = UIColor(red: 0/255, green: 0/255, blue: 0/255, alpha: 1.0).CGColor
		self.authButn.layer.borderWidth = 2.0
		self.authButn.setTitle("Login", forState: UIControlState.Normal)
		self.authButn.setTitleColor(UIColor.blackColor(), forState: UIControlState.Normal)
		self.authButn.addTarget(self, action: "butnPress:", forControlEvents: UIControlEvents.TouchUpInside)
		self.view.addSubview(self.authButn)
		
		/* friend elements */
		
		let frndPadd = UIView(frame: CGRectMake(0, 0, 5, self.userText.frame.size.height))
		self.frndText.leftView = frndPadd
		self.frndText.leftViewMode = UITextFieldViewMode.Always
		self.frndText.layer.cornerRadius = 2.0
		self.frndText.layer.borderColor = UIColor(red: 0/255, green: 0/255, blue: 0/255, alpha: 1.0).CGColor
		self.frndText.layer.borderWidth = 2.0
		self.frndText.autocorrectionType = UITextAutocorrectionType.No
		self.frndText.autocapitalizationType = UITextAutocapitalizationType.None
		self.view.addSubview(self.frndText)
		
		self.frndButn.layer.cornerRadius = 2.0
		self.frndButn.layer.borderColor = UIColor(red: 0/255, green: 0/255, blue: 0/255, alpha: 1.0).CGColor
		self.frndButn.layer.borderWidth = 2.0
		self.frndButn.setTitle("Add", forState: UIControlState.Normal)
		self.frndButn.setTitleColor(UIColor.blackColor(), forState: UIControlState.Normal)
		self.frndButn.addTarget(self, action: "butnPress:", forControlEvents: UIControlEvents.TouchUpInside)
		self.view.addSubview(self.frndButn)
		
		self.seckText.layer.cornerRadius = 2.0
		self.seckText.layer.borderColor = UIColor(red: 0/255, green: 0/255, blue: 0/255, alpha: 1.0).CGColor
		self.seckText.layer.borderWidth = 2.0
		self.seckText.font = self.seckText.font.fontWithSize(8)
		self.seckText.text = (" v" + self.vers)
		self.view.addSubview(self.seckText)
		
		/* message elements */
		
		self.mesgHist.layer.cornerRadius = 2.0
		self.mesgHist.layer.borderColor = UIColor(red: 0/255, green: 0/255, blue: 0/255, alpha: 1.0).CGColor
		self.mesgHist.layer.borderWidth = 2.0
		self.mesgHist.rowHeight = 20.0
		self.mesgHist.delegate = self
		self.mesgHist.dataSource = self
		self.view.addSubview(self.mesgHist)
		
		self.mesgText.layer.cornerRadius = 2.0
		self.mesgText.layer.borderColor = UIColor(red: 0/255, green: 0/255, blue: 0/255, alpha: 1.0).CGColor
		self.mesgText.layer.borderWidth = 2.0
		self.mesgText.autocorrectionType = UITextAutocorrectionType.No
		self.mesgText.autocapitalizationType = UITextAutocapitalizationType.None
		self.mesgText.text = "message string"
		self.view.addSubview(self.mesgText)
		
		self.mesgButn.layer.cornerRadius = 2.0
		self.mesgButn.layer.borderColor = UIColor(red: 0/255, green: 0/255, blue: 0/255, alpha: 1.0).CGColor
		self.mesgButn.layer.borderWidth = 2.0
		self.mesgButn.setTitle("Send", forState: UIControlState.Normal)
		self.mesgButn.setTitleColor(UIColor.blackColor(), forState: UIControlState.Normal)
		self.mesgButn.addTarget(self, action: "butnPress:", forControlEvents: UIControlEvents.TouchUpInside)
		self.view.addSubview(self.mesgButn)
		
		/* background reader */
		
		NSTimer.scheduledTimerWithTimeInterval(5.0, target: self, selector: "backFunc:", userInfo: nil, repeats: true)
	}

	override func didReceiveMemoryWarning() {
		super.didReceiveMemoryWarning()
		// Dispose of any resources that can be recreated.
	}

}

A Basic ECC Crypto C Library

$ gcc -Wall -O2 -o crypto.out crypto.c 
$ ./crypto.out pgen 

x: [0][7][8]=[4880449572248532107701327692677150037572104965674444437385142643512]
y^2: [0][8][8]=[55380869580354224246510320945966028555317502525493429017926966133843051295792]
y: [0][8][8]=[29139577269574826820926935201858599433659429201914524387051377879407947248399]

$ ./crypto.out ecdh 

  1*(y^2) = x^3 + 486662*(x^2) + x (mod 57896044618658097711785492504343953926634992332820282019728792003956564819949)
    17101372528228046186917539708449150102286202153232625914396359604563
      * P(x, y) = (9, 43114425171068552920764898935933967039370386198203806730763910166200978582548)

      = Q(x, y) = (38616894501258673852970036866543659072635089662921568068340331697101576554270, 11643169480892671629858370512120070259223559167488419079368716073871895962191)


  1*(y^2) = x^3 + 486662*(x^2) + x (mod 57896044618658097711785492504343953926634992332820282019728792003956564819949)
    12761708460950637051849206961623904377595162559992784492118523127724
      * P(x, y) = (9, 43114425171068552920764898935933967039370386198203806730763910166200978582548)

      = Q(x, y) = (32477568348650104756356831653582245276448206004887493791495532411741897328458, 28063399834915231969701720976238207473037393607389857712493721633327966471074)


  1*(y^2) = x^3 + 486662*(x^2) + x (mod 57896044618658097711785492504343953926634992332820282019728792003956564819949)
    17101372528228046186917539708449150102286202153232625914396359604563
      * P(x, y) = (32477568348650104756356831653582245276448206004887493791495532411741897328458, 28063399834915231969701720976238207473037393607389857712493721633327966471074)

      = Q(x, y) = (50351522368134241142819091458530332577142187603512687882689541070260459723459, 50221873001104206223375144395698504985316658966829066883833880358017679689691)


  1*(y^2) = x^3 + 486662*(x^2) + x (mod 57896044618658097711785492504343953926634992332820282019728792003956564819949)
    12761708460950637051849206961623904377595162559992784492118523127724
      * P(x, y) = (38616894501258673852970036866543659072635089662921568068340331697101576554270, 11643169480892671629858370512120070259223559167488419079368716073871895962191)

      = Q(x, y) = (50351522368134241142819091458530332577142187603512687882689541070260459723459, 50221873001104206223375144395698504985316658966829066883833880358017679689691)

$ ./crypto.out psig 1234
Sign:

d=[0][7][8]=[6538729008379423383518670268808646995288081785172776771199052697947]
P=(x, y) = (9, 43114425171068552920764898935933967039370386198203806730763910166200978582548)
dP=(x, y) = (14803911054618354585053684993263408691271520722671720792800356230205975217771, 11341018286853926408444620055947798723342444873304700039478772171855673884697)

h=[0][1][1]=[1234]

k=[0][7][8]=[8232207578348459001023088138872857936131335029042440438075457201646]
kP=(x, y) = (31369530948108575720266905846722071920323191212477028674668598541699791483098, 9139751042718096616566254849289158387164951389944576741553517798024823610265)
r=[0][15][40]=[149879290832663482850783820956010355668942537394521944880131051841396204961042266046319521062426903751537961621638691535228251607511236059222514]

Verify:

P=(x, y) = (9, 43114425171068552920764898935933967039370386198203806730763910166200978582548)
dP=(x, y) = (14803911054618354585053684993263408691271520722671720792800356230205975217771, 11341018286853926408444620055947798723342444873304700039478772171855673884697)

h=[0][1][1]=[1234]

kP=(x, y) = (31369530948108575720266905846722071920323191212477028674668598541699791483098, 9139751042718096616566254849289158387164951389944576741553517798024823610265)
r=[0][15][40]=[149879290832663482850783820956010355668942537394521944880131051841396204961042266046319521062426903751537961621638691535228251607511236059222514]

(ek+hd)P=(x, y) = (51608966471038425598161188547671772160458281462630354621077601757763167308540, 17341325372123419326180270058693292718501038313000707228169935748980907943680)
==
rP=(x, y) = (51608966471038425598161188547671772160458281462630354621077601757763167308540, 17341325372123419326180270058693292718501038313000707228169935748980907943680)

[GOOD]
$ ./crypto.out penc 1234
Encrypt:

P=(x, y) = (9, 43114425171068552920764898935933967039370386198203806730763910166200978582548)
dP=(x, y) = (19547865285467707344496388019666506767309887017163137556078134582670804301851, 36180672281078333342162157694938953906019362565570590334768364807054263309922)

h=[0][1][1]=[1234]

k=[0][7][8]=[3873062938517225834483697070677896532844396051944377142545351178872]
kP=(x, y) = (31307487414183777373465427652384958249613501222520858769326720798351611112341, 42327343332069595141617190350930625663948508466032477124028143798481079201841)
kdP=(x, y) = (17546014782981223520910010062776248455503090940217295620750099274078977893385, 40213720617506594547897783150731613585768378209283692064354760696398013829358)

Decrypt:

P=(x, y) = (9, 43114425171068552920764898935933967039370386198203806730763910166200978582548)
dP=(x, y) = (19547865285467707344496388019666506767309887017163137556078134582670804301851, 36180672281078333342162157694938953906019362565570590334768364807054263309922)

d=[0][7][8]=[22873181922607864299317581582398892665871088710637471622228302193764]
dkP=(x, y) = (17546014782981223520910010062776248455503090940217295620750099274078977892151, 40213720617506594547897783150731613585768378209283692064354760696398013829358)

t=[0][1][8]=[1234]

$ 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <strings.h>

#include "../lib/sha256.c"
#include "../lib/aes256.c"
#include "../lib/ec.c"

bnum *bnrnd(int size)
{
	FILE *f;
	bnum *r;
	
	r = bninit(size);
	f = fopen("/dev/urandom", "r");
	fread(r->nums, sizeof(unsigned int), size - 1, f);
	fclose(f);
	r->leng = size;
	while ((r->leng > 1) && (r->nums[r->leng - 1] == 0)) { r->leng -= 1; }
	
	return r;
}

void eccp(ecc *e, char *xs)
{
	int psiz = (e->p)->size;
	bnum *x = bninit(psiz), *y = bninit(psiz), *t;
	
	bnum *xa = bninit(psiz * 4), *xx = bninit(psiz * 4);
	bnum *yy = bninit(psiz * 4), *vv = bninit(psiz * 4);
	
	if (xs != NULL) { t = bndec(xs); }
	else { t = bnrnd(psiz); }
	bncopy(t, x);
	
	while (1)
	{
		// yy = ((x * (x * x)) + (a * (x * x)) + x) % m
		bnzero(xx); bnmul(x, x, xx);
		bnzero(xa); bnmul(xx, e->a, xa);
		bnzero(vv); bnmul(x, xx, vv);
		
		bnzero(yy); bnadd(vv, xa, yy, 1); bnadd(yy, x, vv, 1);
		bndiv(vv, e->p, xx, t);
		// todo: divide t by b?
		
		printf("\n");
		bnout("x: ", x, "\n");
		bnout("y^2: ", t, "\n");
		
		if (sqrtmod(t, e->p, y) == 0) { break; }
		
		if (x != NULL) { bnfree(x); }
		x = bnrnd(psiz);
	}
	
	bnout("y: ", y, "\n\n");
	// note: another y point == p - y
	
	bnzero(yy); bncopy(t, yy);
	bnzero(vv); bnmul(y, y, vv);
	bnzero(xx); bndiv(vv, e->p, xa, xx);
	
	bnfree(xa); bnfree(vv); bnfree(t);
	
	if (bncmp(xx, yy) != 0)
	{
		bnout("y^2: ",xx," != "); bnout("y^2: ",yy,"\n");
	}
	
	bnfree(xx); bnfree(yy);
	bnfree(x); bnfree(y);
}

/*
Curve25519: a=486662, b=1, p=2^255 - 19
ECC DH: o * (n * P) == onP == noP == n * (o * P)
*/

char *ecdh(ecc *e, char *n, int o)
{
	char *r = n;
	bnum *m;
	ecc *f;
	
	if (r == NULL)
	{
		m = bnrnd((e->p)->size);
		r = bnstr(m);
	}
	
	else
	{
		m = bndec(n);
	}
	
	f = ecdup(e);
	pmul(m, e, f);
	
	if (o == 1)
	{
		char v[2050];
		bzero(v, 2050 * sizeof(char));
		strncat(v, "    "       , max(0, 2048 - strlen(v)));
		strncat(v, r            , max(0, 2048 - strlen(v)));
		strncat(v, "\n      * P", max(0, 2048 - strlen(v)));
		printf("\n");
		ecout(1,v,e,"\n\n");
		ecout(0,"      = Q",f,"\n");
		printf("\n");
	}
	
	bnfree(e->x); e->x = bndup(f->x);
	bnfree(e->y); e->y = bndup(f->y);
	bnfree(m);
	ecfree(f);
	
	return r;
}

/*
ECC - Private Sign / Public Verify

* initialize
- generate secret key          : d
- publish                      : P, dP

* private sign
- hash message                 : h = SHA256(m)
- secret unique multiplier     : k
- calculate public multipliers : kP
                               : e = hP(x)
                               : r = ((e * k) + (h * d))
- publish                      : kP, r

* public verify
                               : e = hP(x)
-                              : (e * kP) + (h * dP) == rP
*/

int ecsig(ecc *e, bnum *d, ecc *dp, char *hh, ecc *kp, bnum *r, int o)
{
	int a = 0, psiz = (e->p)->size;
	bnum *k, *h;
	bnum *t = bninit(psiz * 5), *u = bninit(psiz * 5);
	ecc *hp = ecdup(e), *ekp = ecdup(e), *hdp = ecdup(e), *ekhdp = ecdup(e), *rp = ecdup(e);
	ect *tadd = etinit(e);
	
	if (hh != NULL)
	{
		if (((kp->x)->leng == 1) && ((kp->x)->nums[0] == 0))
		{
			if ((d->leng == 1) && (d->nums[0] == 0))
			{
				k = bnrnd(psiz); bncopy(k, d); bnfree(k);
				pmul(d, e, dp);
				
				if (o == 1) { bnout("d=", d, "\n"); }
			}
		}
		
		if (o == 1)
		{
			ecout(0, "P=", e, "\n");
			ecout(0, "dP=", dp, "\n\n");
		}
		
		h = bndec(hh);
		pmul(h, e, hp);
		
		if (o == 1) { bnout("h=", h, "\n\n"); }
		
		if (((kp->x)->leng == 1) && ((kp->x)->nums[0] == 0))
		{
			k = bnrnd(psiz);
			pmul(k, e, kp);
			
			if (o == 1) { bnout("k=", k, "\n"); }
			
			bnzero(t); bnmul(hp->x, k, t);
			bnzero(u); bnmul(h, d, u);
			bnadd(t, u, r, 1);
			
			bnfree(k);
		}
		
		if (o == 1)
		{
			ecout(0, "kP=", kp, "\n");
			bnout("r=", r, "\n\n");
		}
		
		pmul(hp->x, kp, ekp);
		pmul(h, dp, hdp);
		padd(ekp, hdp, ekhdp, tadd);
		pmul(r, e, rp);
		
		if ((d->leng == 1) && (d->nums[0] == 0))
		{
			if (o == 1)
			{
				ecout(0, "(ek+hd)P=", ekhdp, "\n==\n");
				ecout(0, "rP=", rp, "\n\n");
			}
		}
		
		if (bncmp(ekhdp->x, rp->x) == 0)
		{
			if (bncmp(ekhdp->y, rp->y) == 0)
			{
				a = 1;
			}
		}
		
		bnfree(h);
	}
	
	bnfree(t); bnfree(u);
	ecfree(hp); ecfree(ekp); ecfree(hdp); ecfree(ekhdp); ecfree(rp);
	etfree(tadd);
	
	return a;
}

/*
ECC ElGamal - Public Encrypt / Private Decrypt

* initialize
- generate secret integer  : d
- publish                  : P, dP

* public encrypt
- generate secret key      : t = (SHA256(pwd) || tmpkey)
- secret unique multiplier : k = rand()
- public key encrypt       : r = k * P        = kP
                           : s = t + (k * dP) = t + kdP = kdP(x + t, y + t)
- encrypt optional message : i = rand()
                           : e = AES256CBC(m, i, t)
- publish                  : [ (r, s) , (i, e) ]

* private decrypt
- private key decrypt      : u = s - (d * r)
                               = (t + kdP) - (d * kP)
                               = kdP(x + t, y + t) - dkP(x, y)
                               = kdP(x - x + t)
                               = t
*/

void ecenc(ecc *e, bnum *d, ecc *dp, char *hh, ecc *kp, ecc *kdp, int o)
{
	int psiz = (e->p)->size;
	bnum *k, *h, *t;
	ecc *dkp;
	
	if (hh != NULL)
	{
		if ((d->leng == 1) && (d->nums[0] == 0))
		{
			k = bnrnd(psiz); bncopy(k, d); bnfree(k); k = NULL;
			pmul(d, e, dp);
		}
		
		if (o == 1)
		{
			ecout(0, "P=", e, "\n");
			ecout(0, "dP=", dp, "\n\n");
		}
		
		h = bndec(hh);
		
		if (((kp->x)->leng == 1) && ((kp->x)->nums[0] == 0))
		{
			if (o == 1) { bnout("h=", h, "\n\n"); }
			
			k = bnrnd(psiz);
			pmul(k, e, kp);
			
			pmul(k, dp, kdp);
			t = kdp->x; kdp->x = bninit(psiz + 1); bncopy(t, kdp->x); bnfree(t);
			bnadd(kdp->x, h, kdp->x, 1);
			
			if (o == 1)
			{
				bnout("k=", k, "\n");
				ecout(0, "kP=", kp, "\n");
				ecout(0, "kdP=", kdp, "\n\n");
			}
			
			bnfree(k);
		}
		
		else
		{
			dkp = ecdup(e);
			pmul(d, kp, dkp);
			t = bninit(psiz); bnsub(kdp->x, dkp->x, t, 1);
			
			if (o == 1)
			{
				bnout("d=", d, "\n");
				ecout(0, "dkP=", dkp, "\n\n");
				bnout("t=", t, "\n\n");
			}
			
			bnfree(t);
			ecfree(dkp);
		}
		
		bnfree(h);
	}
}

int main(int argc, char **argv)
{
	char *a = "486662", *b = "1", *p = "57896044618658097711785492504343953926634992332820282019728792003956564819949";
	char *x = "9", *y = "43114425171068552920764898935933967039370386198203806730763910166200978582548";
	char *n, *m, *z = NULL;
	char hash[256];
	unsigned char msg[16], key[256];
	bnum *d, *r, *s;
	bnum *t, *u, *v, *w;
	ecc *e, *f, *dp, *kp, *kdp;
	
	if (argc > 2) { z = argv[2]; }
	
	t = bndec(p);
	u = bninit(t->size); w = bndec(x); bncopy(w, u); bnfree(w);
	v = bninit(t->size); w = bndec(y); bncopy(w, v); bnfree(w);
	e = ecinit(bndec(a), bndec(b), t, u, v);
	
	if (strcmp(argv[1], "pgen") == 0)
	{
		eccp(e, z);
	}
	
	if (strcmp(argv[1], "pmul") == 0)
	{
		ecdh(e, argv[2], 1);
	}
	
	if (strcmp(argv[1], "ecdh") == 0)
	{
		f = ecdup(e);
		
		n = ecdh(e, NULL, 1);
		m = ecdh(f, NULL, 1);
		
		t = e->x; u = e->y;
		e->x = f->x; e->y = f->y;
		f->x = t; f->y = u;
		
		ecdh(e, n, 1);
		ecdh(f, m, 1);
		
		free(n); free(m);
		ecfree(f);
	}
	
	if (strcmp(argv[1], "psig") == 0)
	{
		d = bninit((e->p)->size);
		dp = ecdup(e); kp = ecdup(e);
		r = bninit((e->p)->size * 5);
		s = bninit((e->p)->size * 5);
		
		printf("Sign:\n\n");
		(kp->x)->leng = 1; (kp->x)->nums[0] = 0;
		(kp->y)->leng = 1; (kp->y)->nums[0] = 0;
		ecsig(e, d, dp, z, kp, r, 1);
		
		printf("Verify:\n\n");
		bnzero(d);
		if (ecsig(e, d, dp, z, kp, r, 1) != 0) { printf("[GOOD]\n"); }
		else { printf("\n[FAILED]\n"); }
		
		bnfree(d); bnfree(r); bnfree(s);
		ecfree(dp); ecfree(kp);
	}
	
	if (strcmp(argv[1], "penc") == 0)
	{
		d = bninit((e->p)->size);
		dp = ecdup(e); kp = ecdup(e); kdp = ecdup(e);
		
		printf("Encrypt:\n\n");
		(kp->x)->leng = 1; (kp->x)->nums[0] = 0;
		(kp->y)->leng = 1; (kp->y)->nums[0] = 0;
		ecenc(e, d, dp, z, kp, kdp, 1);
		
		printf("Decrypt:\n\n");
		ecenc(e, d, dp, z, kp, kdp, 1);
		
		bnfree(d);
		ecfree(dp); ecfree(kp); ecfree(kdp);
	}
	
	if (strcmp(argv[1], "hash") == 0)
	{
		sha256 hobj;
		sha256init(&hobj);
		sha256update(&hobj, (unsigned char *)argv[2], strlen(argv[2]));
		sha256final(&hobj, hash);
		printf("%s\n", hash);
	}
	
	if (strcmp(argv[1], "menc") == 0)
	{
		bzero(key, 256);
		strcpy((char *)key, argv[3]);
		aes256keys(key);
		
		bzero(msg, 16);
		strcpy((char *)msg, argv[2]);
		aes256core(msg, key, 0);
		
		int i;
		for (i = 0; i < 16; ++i) { printf("%02x", msg[i]); }
		printf("\n");
	}
	
	ecfree(e);
	
	return 0;
}

Curve25519 ECDH (Using bn.c)

$ a="486662"; b="1"; p="57896044618658097711785492504343953926634992332820282019728792003956564819949"
$ x="9"; y="43114425171068552920764898935933967039370386198203806730763910166200978582548"
$ ./ec.out "$a" "$b" "$p" "$x" "$y"

  1*(y^2) = x^3 + 486662*(x^2) + x (mod 57896044618658097711785492504343953926634992332820282019728792003956564819949)
    25401056036235045220436215630227531782477232918721757282083167532085
      * P(x, y) = (9, 43114425171068552920764898935933967039370386198203806730763910166200978582548)

      = Q(x, y) = (2152181765955508802144811366391548358206596269149408838626058763387933371482, 11578758651574146923540708489424215527254544219548915855368449621649032022464)

$ ./ec.out "$a" "$b" "$p" "$x" "$y"

  1*(y^2) = x^3 + 486662*(x^2) + x (mod 57896044618658097711785492504343953926634992332820282019728792003956564819949)
    14923829837058818803507170043209691418601607100463140519943405743260
      * P(x, y) = (9, 43114425171068552920764898935933967039370386198203806730763910166200978582548)

      = Q(x, y) = (10616717952671290844210554362351196131260739681824015303968067548318407877443, 44474405861832920486283648404346377112839096552743000067399554821542048806382)

$ x="10616717952671290844210554362351196131260739681824015303968067548318407877443"; y="44474405861832920486283648404346377112839096552743000067399554821542048806382"
$ ./ec.out "$a" "$b" "$p" "$x" "$y" "25401056036235045220436215630227531782477232918721757282083167532085"

  1*(y^2) = x^3 + 486662*(x^2) + x (mod 57896044618658097711785492504343953926634992332820282019728792003956564819949)
    25401056036235045220436215630227531782477232918721757282083167532085
      * P(x, y) = (10616717952671290844210554362351196131260739681824015303968067548318407877443, 44474405861832920486283648404346377112839096552743000067399554821542048806382)

      = Q(x, y) = (5796465362698668629448044005371479448781495853974848652041497206752313461872, 30198337259834952114045673142150509214022566212693868468740722556827195886413)

$ x="2152181765955508802144811366391548358206596269149408838626058763387933371482"; y="11578758651574146923540708489424215527254544219548915855368449621649032022464"
$ ./ec.out "$a" "$b" "$p" "$x" "$y" "14923829837058818803507170043209691418601607100463140519943405743260"

  1*(y^2) = x^3 + 486662*(x^2) + x (mod 57896044618658097711785492504343953926634992332820282019728792003956564819949)
    14923829837058818803507170043209691418601607100463140519943405743260
      * P(x, y) = (2152181765955508802144811366391548358206596269149408838626058763387933371482, 11578758651574146923540708489424215527254544219548915855368449621649032022464)

      = Q(x, y) = (5796465362698668629448044005371479448781495853974848652041497206752313461872, 30198337259834952114045673142150509214022566212693868468740722556827195886413)

$ 
#include "bn.c"

struct ecurve {
	bnum *a, *b, *p, *x, *y;
};

#define ecc struct ecurve

struct ectemp {
	bnum *i, *s, *xr, *yr;
	bnum *t, *u, *v;
	bnum *w, *h, *g;
};

#define ect struct ectemp

ecc *ecinit(bnum *a, bnum *b, bnum *p, bnum *x, bnum *y)
{
	ecc *r = malloc(1 * sizeof(ecc));
	r->a = a; r->b = b; r->p = p;
	r->x = x; r->y = y;
	return r;
}

ecc *ecdup(ecc *e)
{
	ecc *r = malloc(1 * sizeof(ecc));
	r->a = bndup(e->a); r->b = bndup(e->b); r->p = bndup(e->p);
	r->x = bndup(e->x); r->y = bndup(e->y);
	return r;
}

void ecfree(ecc *e)
{
	bnfree(e->a); bnfree(e->b); bnfree(e->p);
	bnfree(e->x); bnfree(e->y);
	free(e);
}

void ecout(int d, char *s, ecc *e, char *t)
{
	char *a = bnstr(e->a), *b = bnstr(e->b), *p = bnstr(e->p);
	char *x = bnstr(e->x), *y = bnstr(e->y);
	char as[2], bs[2];
	as[0] = '+'; as[1] = '\0';
	bs[0] = '\0'; bs[1] = '\0';
	if ((e->a)->sign == 1) { as[0] = '-'; }
	if ((e->b)->sign == 1) { bs[0] = '-'; }
	if (d == 1) { printf("  %s%s*(y^2) = x^3 %s %s*(x^2) + x (mod %s)\n", bs, b, as, a, p); }
	printf("%s", s);
	printf("(x, y) = (%s, %s)", x, y);
	printf("%s", t);
	free(a); free(b); free(p);
	free(x); free(y);
}

ect *etinit(ecc *e)
{
	ect *t = malloc(1 * sizeof(ect));
	int ss = max(1, (e->b)->size);
	ss = max(((e->a)->size * 2) + 2, ((e->p)->size * 2) + 2);
	ss = max(((e->x)->size * 2) + 2, ((e->y)->size * 2) + 2);
	t->i = bninit(ss); t->s = bninit(ss); t->xr = bninit(ss); t->yr = bninit(ss);
	t->t = bninit(ss); t->u = bninit(ss); t->v = bninit(ss);
	int tt = ((ss * 2) + 2);
	t->w = bninit(tt); t->h = bninit(tt); t->g = bninit(tt + 4);
	return t;
}

void etfree(ect *t)
{
	bnfree(t->i); bnfree(t->s); bnfree(t->xr); bnfree(t->yr);
	bnfree(t->t); bnfree(t->u); bnfree(t->v);
	bnfree(t->w); bnfree(t->h); bnfree(t->g);
	free(t);
}

// modular multiplicative inverse

void egcd(bnum *a, bnum *b, bnum *g)
{
	int size = ((a->size + b->size) * 3);
	// s = 0; news = 1
	bnum *s = bninit(size);
	bnum *news = bninit(size); news->nums[0] = 1;
	// r = b; newr = a
	bnum *r = bninit(size); bncopy(b, r);
	bnum *newr = bninit(size); bncopy(a, newr);
	// init some temp vars
	bnum *prev = bninit(size), *quot = bninit(size), *temp = bninit(size);
	while ((r->leng > 1) || (r->nums[0] > 0))
	{
		// quot = (newr / r)
		if ((r->leng == 1) && (r->nums[0] < 3))
		{
			bncopy(newr, quot);
			if (r->nums[0] > 1) { bnrshift(quot, 1); }
		}
		else { bndiv(newr, r, quot, temp); }
		// prev = s
		bncopy(s, prev);
		// s = (news - (quot * prev))
		bnzero(temp); bnmul(quot, prev, temp);
		bnsub(news, temp, s, 0);
		// news = prev
		bncopy(prev, news);
		// prev = r
		bncopy(r, prev);
		// r = (newr - (quot * prev))
		bnzero(temp); bnmul(quot, prev, temp);
		bnsub(newr, temp, r, 0);
		// newr = prev
		bncopy(prev, newr);
	}
	if (news->sign == 1)
	{
		// news = news + b
		bnadd(news, b, news, 0);
	}
	bncopy(news, g);
	bnfree(s); bnfree(news);
	bnfree(r); bnfree(newr);
	bnfree(prev); bnfree(quot); bnfree(temp);
}

// modular square root

int sqrtmod(bnum *a, bnum *p, bnum *r)
{
	bnum *o = bninit(1);
	o->nums[0] = 1; o->leng = 1; o->sign = 0;
	
	// legendre symbol
	// define if a is a quadratic residue modulo odd prime
	
	// g = (p - 1) / 2
	
	// p - 1
	bnum *qq = bndup(p);
	bnsub(qq, o, qq, 1);
	// (p - 1) / 2
	bnum *g = bndup(qq);
	bnrshift(g, 1);
	
	// l = pow(a, g, p)
	
	// pow(a, g, p)
	bnum *l = bninit(max(max(a->size, g->size), p->size) * 3);
	bnpowmod(a, g, p, l);
	if (bncmp(l, qq) == 0)
	{
		bnfree(o); bnfree(qq); bnfree(g); bnfree(l);
		return -1;
	}
	
	// factor p - 1 on the form q * (2 ^ s) (with Q odd)
	// q = p - 1; s = 0
	bnum *q = bndup(qq);
	bnum *s = bninit(p->size);
	while ((q->nums[0] % 2) == 0)
	{
		// s += 1; q /= 2
		bnadd(s, o, s, 1);
		bnrshift(q, 1);
	}
	
	// select a z which is a quadratic non resudue modulo p
	// z = 1
	bnum *z = bninit(p->size);
	z->nums[0] = 1; z->leng = 1; z->sign = 0;
	while (1)
	{
		// while (lsym(z, p) != -1)
		bnpowmod(z, g, p, l);
		if (bncmp(l, qq) == 0) { break; }
		// z += 1
		bnadd(z, o, z, 1);
	}
	// c = pow(z, q, p)
	bnum *c = bninit(max(max(z->size, q->size), p->size) * 3);
	bnpowmod(z, q, p, c);
	
	// search for a solution
	// f = ((q + 1) / 2)
	bnum *f = bndup(q);
	bnadd(f, o, f, 1); bnrshift(f, 1);
	// x = pow(a, f, p)
	bnpowmod(a, f, p, r);
	// t = pow(a, q, p)
	bnum *t = bninit(max(max(a->size, q->size), p->size) * 3);
	bnpowmod(a, q, p, t);
	// m = s
	bnum *m = bninit(p->size), *i = bninit(p->size), *e = bninit(p->size);
	bncopy(s, m);
	// u = 2
	bnum *u = bninit(1);
	u->nums[0] = 2; u->leng = 1; u->sign = 0;
	bnum *b = bninit(p->size * 4), *v = bninit(p->size * 4), *w = bninit(p->size * 4);
	while ((t->leng > 1) || (t->nums[0] != 1))
	{
		// find the lowest i such that t ^ (2 ^ i) = 1
		// i = 1; e = 2
		i->nums[0] = 1; i->leng = 1; i->sign = 0;
		e->nums[0] = 2; e->leng = 1; e->sign = 0;
		while (bncmp(i, m) < 0)
		{
			bnpowmod(t, e, p, l);
			if ((l->leng == 1) && (l->nums[0] == 1)) { break; }
			bnlshift(e, 1);
			bnadd(i, o, i, 1);
		}
		// update next value to iterate
		// (m - i - 1)
		bnsub(m, i, v, 0);
		bnsub(v, o, v, 0);
		// 2 ^ (m - i - 1)
		bnpowmod(u, v, p, l);
		// b = (c ^ (2 ^ (m - i - 1))) % p
		bnpowmod(c, l, p, b);
		// x = ((x * b) % p)
		bnzero(v); bnmul(r, b, v);
		bndiv(v, p, w, r);
		// b = (b * b) % p
		bnzero(v); bnmul(b, b, v);
		bndiv(v, p, w, b);
		// t = ((t * b) % p)
		bnzero(v); bnmul(t, b, v);
		bndiv(v, p, w, t);
		// c = b; m = i
		bncopy(b, c);
		bncopy(i, m);
	}
	
	bnfree(o); bnfree(qq); bnfree(g); bnfree(l);
	bnfree(q); bnfree(s); bnfree(z); bnfree(c);
	bnfree(f); bnfree(t); bnfree(m);
	bnfree(i); bnfree(e); bnfree(b);
	bnfree(u); bnfree(v); bnfree(w);
	
	// r = [x, p - x]
	
	return 0;
}

// montgomery curve arithmetic

void nmod(bnum *a, bnum *b)
{
	if (a->sign == 1) { bnadd(b, a, a, 0); }
}

void pdub(ecc *p, ecc *r, ect *t)
{
	// printf("2P=\n");
	
	// l = 3*x^2 + 2*a*x + 1 / 2*b*y
	
	// x^2
	bnzero(t->w); bnmul(p->x, p->x, t->w); bndiv(t->w, p->p, t->t, t->v);
	// 3*x^2
	bnadd(t->v, t->v, t->w, 1); bnadd(t->w, t->v, t->w, 1);
	// 2*a*x
	bnzero(t->h); bnmul(p->a, p->x, t->h); bnlshift(t->h, 1);
	bndiv(t->h, p->p, t->t, t->u); nmod(t->u, p->p);
	// 3*x^2 + 2*a*x + 1
	bnadd(t->w, t->u, t->g, 1);
	int x, o = 1;
	for (x = 0; (x < (t->g)->leng) && (o == 1); ++x)
	{
		o = 0; if ((t->g)->nums[x] == 0xffffffff) { o = 1; } (t->g)->nums[x] += 1;
	}
	if (o == 1) { (t->g)->nums[x] = 1; (t->g)->leng += 1; }
	bndiv(t->g, p->p, t->t, t->yr);
	// 1 / 2*b*y
	bnzero(t->w); bnmul(p->b, p->y, t->w); bnlshift(t->w, 1);
	bndiv(t->w, p->p, t->t, t->u); nmod(t->u, p->p); egcd(t->u, p->p, t->i);
	// 3*x^2 + 2*a*x + 1 / 2*b*y
	bnzero(t->w); bnmul(t->yr, t->i, t->w); bndiv(t->w, p->p, t->t, t->s);
	
	// xr = b*l^2 - a - 2*x
	
	// l^2
	bnzero(t->g); bnmul(t->s, t->s, t->g);
	// b*l^2 - a
	bnzero(t->w); bnmul(p->b, t->g, t->w);
	bnsub(t->w, p->a, t->w, 0);
	// 2*x
	bnzero(t->h); bncopy(p->x, t->h); bnlshift(t->h, 1);
	// b*l^2 - a - 2*x
	bnsub(t->w, t->h, t->w, 0);
	bndiv(t->w, p->p, t->t, t->xr); nmod(t->xr, p->p);
	
	// yr = ((3*x + a) * l) - b*l^3 - y
	
	// (3*x + a) * l
	bnadd(t->h, p->x, t->w, 1); bnadd(t->w, p->a, t->w, 0);
	bndiv(t->w, p->p, t->t, t->u); nmod(t->u, p->p);
	bnzero(t->w); bnmul(t->u, t->s, t->w);
	// l^3
	bncopy(t->g, t->h);
	bnzero(t->g); bnmul(t->h, t->s, t->g); bndiv(t->g, p->p, t->t, t->u);
	// b*l^3
	bnzero(t->h); bnmul(p->b, t->u, t->h);
	bndiv(t->h, p->p, t->t, t->u); nmod(t->u, p->p);
	// ((3*x + a) * l) - b*l^3 - y
	bnsub(t->w, t->u, t->w, 0); bnsub(t->w, p->y, t->w, 0);
	bndiv(t->w, p->p, t->t, t->yr); nmod(t->yr, p->p);
	
	(t->xr)->leng = (p->p)->size; bncopy(t->xr, r->x);
	(t->yr)->leng = (p->p)->size; bncopy(t->yr, r->y);
}

void padd(ecc *p, ecc *q, ecc *r, ect *t)
{
	// printf("P+Q=\n");
	
	// l = (Qy - Py) / (Qx - Px)
	
	// Qy - Py
	bnsub(q->y, p->y, t->yr, 0);
	// Qx - Px
	bnsub(q->x, p->x, t->xr, 0);
	bndiv(t->xr, p->p, t->t, t->u); nmod(t->u, p->p);
	// 1 / (Qx - Px)
	egcd(t->u, p->p, t->i);
	// (Qy - Py) / (Qx - Px)
	bnzero(t->w); bnmul(t->yr, t->i, t->w);
	bndiv(t->w, p->p, t->t, t->s);
	
	// xr = b*l^2 - a - Px - Qx
	
	// b*l^2 - a - Px - Qx
	bnzero(t->w); bnmul(t->s, t->s, t->w);
	bnzero(t->g); bnmul(p->b, t->w, t->g);
	bnsub(t->g, p->a, t->g, 0);
	bnsub(t->g, p->x, t->g, 0);
	bnsub(t->g, q->x, t->g, 0);
	bndiv(t->g, p->p, t->t, t->xr); nmod(t->xr, p->p);
	
	// yr = ((2*Px + Qx + a) * l) - b*l^3 - Py
	
	// 2*Px + Qx + a
	bnadd(p->x, p->x, t->t, 1);
	bnadd(t->t, q->x, t->t, 1);
	bnadd(t->t, p->a, t->t, 0);
	bndiv(t->t, p->p, t->u, t->v); nmod(t->v, p->p);
	// (2*Px + Qx + a) * l
	bnzero(t->w); bnmul(t->v, t->s, t->w); bndiv(t->w, p->p, t->t, t->u);
	// b*l^3
	bnzero(t->w); bnmul(t->s, t->s, t->w);
	bnzero(t->g); bnmul(t->w, t->s, t->g); bndiv(t->g, p->p, t->t, t->v);
	bnzero(t->w); bnmul(t->v, p->b, t->w);
	// ((2*Px + Qx + a) * l) - b*l^3 - Py
	bnsub(t->u, t->w, t->v, 0);
	bnsub(t->v, p->y, t->v, 0);
	bndiv(t->v, p->p, t->t, t->yr); nmod(t->yr, p->p);
	
	(t->xr)->leng = (p->p)->size; bncopy(t->xr, r->x);
	(t->yr)->leng = (p->p)->size; bncopy(t->yr, r->y);
}

void pmul(bnum *m, ecc *p, ecc *r)
{
	int init = 0;
	bnum *mul = bndup(m);
	ecc *b = ecdup(p);
	ect *t = etinit(p);
	while ((mul->leng > 1) || (mul->nums[0] > 0))
	{
		if ((mul->nums[0] % 2) == 1)
		{
			if (init == 0)
			{
				bnfree(r->x); r->x = bndup(b->x);
				bnfree(r->y); r->y = bndup(b->y);
			}
			else
			{
				padd(r, b, r, t);
			}
			init = 1;
		}
		pdub(b, b, t);
		bnrshift(mul, 1);
	}
	bnfree(mul);
	ecfree(b);
	etfree(t);
}

bn.c – A Basic Big Number/Integer Calculator

$ time ./bn.out
35052111338673026690212423937053328511880760811579981620642802346685810623109850235943049080973386241113784040794704193978215378499765413083646438784740952306932534945195080183861574225226218879827232453912820596886440377536082465681750074417459151485407445862511023472235560823053497791518928820272257787786
^
89489425009274444368228545921773093919669586065884257445497854456487674839629818390934941973262879616797970608917283679875499331574161113854088813275488110588247193077582527278437906504015680623423550067240042466665654232383502922215493623289472138866445818789127946123407807725702626644091036502372545139713
%
145906768007583323230186939349070635292401872375357164399581871019873438799005358938369571402670149802121818086292467422828157022922076746906543401224889672472407926969987100581290103199317858753663710862357656510507883714297115637342788911463535102712032765166518411726859837988672111837205085526346618740053
=
1976620216402300889624482718775150

real	0m0.783s
user	0m0.774s
sys	0m0.005s
struct bigint {
	int sign, leng, size;
	unsigned int *nums;
};

#define bnum struct bigint

int min(int a, int b)
{
	if (a < b) { return a; }
	return b;
}

int max(int a, int b)
{
	if (a > b) { return a; }
	return b;
}

int oshift(char **a, int b, char c)
{
	// right shift string a ("234") and insert overflow char c ('1')
	int x, n = (b + 1);
	char *s = *a;
	s = realloc(s, n * sizeof(char));
	for (x = (n - 2); x > 0; --x) { s[x] = s[x - 1]; }
	s[0] = c; s[n - 1] = '\0';
	*a = s;
	return n;
}

char *bnstr(bnum *bint)
{
	int x, y, w, z, o, n;
	int r = 2, t = 2;
	char *result = malloc(r * sizeof(char));
	char *twos = malloc(t * sizeof(char));
	// result = 0
	result[0] = '0'; result[1] = '\0';
	// twos = 1
	twos[0] = '1'; twos[1] = '\0';
	// loop through the bn binary
	for (x = 0; x < bint->leng; ++x)
	{
		for (y = 0; y < 32; ++y)
		{
			// if bn binary[n] == 1 then add the 2^n to result
			if (((bint->nums[x] >> y) & 0x1) == 1)
			{
				o = 0; w = (t - 2); z = (r - 2);
				// if the length of twos is bigger than length of result then realloc result
				if (t > r)
				{
					result = realloc(result, t * sizeof(char));
					result[t - 1] = '\0';
					r = t;
				}
				// add twos to result
				while ((w > -1) || (z > -1))
				{
					int a = 0; if (w > -1) { a = (twos[w] - '0'); }
					int b = 0; if (z > -1) { b = (result[z] - '0'); }
					n = (a + b + o);
					result[w] = ('0' + (n % 10));
					o = (n / 10);
					--w; --z;
				}
				if (o > 0) { r = oshift(&result, r, '0' + o); }
			}
			// multiply twos * 2
			o = 0; w = (t - 2);
			while (w > -1)
			{
				n = (o + ((twos[w] - '0') * 2));
				twos[w] = ('0' + (n % 10));
				o = (n / 10);
				--w;
			}
			if (o > 0) { t = oshift(&twos, t, '0' + o); }
		}
	}
	free(twos);
	return result;
}

void bnout(char *s, bnum *p, char *t)
{
	char *o = bnstr(p);
	printf("%s[%d][%d][%d]=[%s]%s", s, p->sign, p->leng, p->size, o, t);
	free(o);
}

void bnzero(bnum *a)
{
	a->sign = 0;
	bzero(a->nums, a->size * sizeof(unsigned int));
	a->leng = 1;
}

void bncopy(bnum *src, bnum *dst)
{
	dst->sign = src->sign;
	bcopy(src->nums, dst->nums, src->leng * sizeof(unsigned int));
	dst->leng = src->leng;
}

void bnfree(bnum *bint)
{
	//todo:zero out all values
	free(bint->nums);
	free(bint);
}

void bndfree(bnum **bint)
{
	bnfree(bint[0]);
	bnfree(bint[1]);
	free(bint);
}

int bncmp(bnum *a, bnum *b)
{
	int x = (a->leng - 1), y = (b->leng - 1);
	while ((x > -1) && (a->nums[x] < 1)) { --x; }
	while ((y > -1) && (b->nums[y] < 1)) { --y; }
	if (x > y) { return 1; }
	if (y > x) { return -1; }
	while (x > -1)
	{
		if (a->nums[x] > b->nums[x]) { return 1; }
		if (b->nums[x] > a->nums[x]) { return -1; }
		--x;
	}
	return 0;
}

int bnhigh(bnum *a)
{
	int x, y, f = 0, hib = -1;
	for (x = (a->leng - 1); (x > -1) && (f == 0); --x)
	{
		for (y = 31; (y > -1) && (f == 0); --y)
		{
			if (((a->nums[x] >> y) & 0x1) == 1)
			{
				hib = ((x * 32) + y);
				f = 1;
			}
		}
	}
	return hib;
}

void bnrshift(bnum *a, int s)
{
	int x, leng = 0, i = (s / 32);
	s = (s % 32);
	for (x = 0; x < (a->leng - i); ++x)
	{
		if (i > 0)
		{
			a->nums[x] = a->nums[x + i];
		}
		if (s > 0)
		{
			if (x > 0)
			{
				a->nums[x - 1] = ((a->nums[x] << (32 - s)) | a->nums[x - 1]);
				if (a->nums[x - 1] > 0) { leng = x; }
			}
			a->nums[x] = (a->nums[x] >> s);
		}
		if (a->nums[x] > 0) { leng = (x + 1); }
	}
	if (leng < 1)
	{
		a->nums[0] = 0;
		leng = 1;
	}
	a->leng = leng;
}

void bnlshift(bnum *a, int s)
{
	int x, o = 0, i = (s / 32);
	unsigned int over = (a->nums[a->leng - 1] >> (32 - (s % 32)));
	s = (s % 32);
	// check to see if the left shift will have any carry over bits
	if ((s > 0) && (over > 0)) { o = 1; }
	// pre adjust the size of the bn to hold the left shift bits
	if (a->size < (a->leng + o + i))
	{
		a->size = (a->leng + o + i);
		a->nums = realloc(a->nums, a->size * sizeof(unsigned int));
	}
	a->leng += (o + i);
	// shift the bits from left to right (last to first) minus the overflow spot
	for (x = (a->leng - o - 1); x > -1; --x)
	{
		if (i > 0)
		{
			if ((x - i) > -1) { a->nums[x] = a->nums[x - i]; }
			else { a->nums[x] = 0; }
		}
		if (s > 0)
		{
			if ((x + 1) < (a->leng - o)) { a->nums[x + 1] = (a->nums[x + 1] | (a->nums[x] >> (32 - s))); }
			a->nums[x] = (a->nums[x] << s);
		}
	}
	// if we have some overflow bits then set them last now
	if (o == 1) { a->nums[a->leng - 1] = over; }
}

bnum *bninit(int ssiz)
{
	int x;
	bnum *a = malloc(1 * sizeof(bnum));
	a->sign = 0; a->leng = 1, a->size = ssiz;
	a->nums = malloc(ssiz * sizeof(unsigned int));
	for (x = 0; x < ssiz; ++x) { a->nums[x] = 0; }
	return a;
}

bnum *bndup(bnum *a)
{
	int x;
	bnum *r = malloc(1 * sizeof(bnum));
	r->sign = a->sign; r->leng = a->leng; r->size = a->size;
	r->nums = malloc(a->size * sizeof(unsigned int));
	for (x = 0; x < a->size; ++x) { r->nums[x] = a->nums[x]; }
	return r;
}

bnum *bndec(char *decstr)
{
	int x, y, r, n;
	int i = 0;
	unsigned long m, l = strlen(decstr);
	char numstr[l + 1], outstr[l + 1];
	// result = 0
	bnum *result = bninit(1);
	// copy the input decimal string into a temp num str
	strncpy(numstr, decstr, l);
	numstr[l] = '\0';
	m = l;
	// while there are numbers left to be divided by 2
	while ((m > 1) || (numstr[0] > '0'))
	{
		// if we are shifting above 32 bits then append a new bit block
		if (i > 31)
		{
			result->leng += 1; result->size += 1;
			result->nums = realloc(result->nums, result->size * sizeof(unsigned int));
			result->nums[result->leng - 1] = 0;
			i = 0;
		}
		// divide the number by 2 and store the result in a temp string
		r = 0;
		outstr[0] = '\0';
		for (x = 0, y = 0; (x < m) && (y < l); ++x, ++y)
		{
			// get the last remainder and the current digit
			n = ((r * 10) + (numstr[x] - '0'));
			// if the digit num is less than the divider 2 then add on the next digit
			if ((n < 2) && ((x + 1) < m) && ((y + 1) < l))
			{
				n = ((n * 10) + (numstr[x + 1] - '0'));
				if (y > 0) { outstr[y] = '0'; ++y; }
				++x;
			}
			// store the division and the remainder
			outstr[y] = ('0' + (n / 2));
			outstr[y + 1] = '\0';
			r = (n % 2);
		}
		// save the binary result
		result->nums[result->leng - 1] = ((r << i) | result->nums[result->leng - 1]);
		++i;
		// copy the divided result into the temp num str
		strncpy(numstr, outstr, l);
		numstr[y] = '\0';
		m = strlen(numstr);
	}
	return result;
}

int bnsub(bnum *, bnum *, bnum *, int);

int bnadd(bnum *a, bnum *b, bnum *r, int s)
{
	int x = 0, y = 0, z = 0, g = 0;
	unsigned int over = 0;
	if (s == 0)
	{
		if ((a->sign == 0) && (b->sign == 1))
		{
			b->sign = 0;
			bnsub(a, b, r, 0); g = r->sign;
			b->sign = 1;
			r->sign = g;
			return 0;
		}
		else if ((a->sign == 1) && (b->sign == 0))
		{
			a->sign = 0;
			bnsub(b, a, r, 0); g = r->sign;
			a->sign = 1;
			r->sign = g;
			return 0;
		}
	}
	while ((x < a->leng) || (y < b->leng))
	{
		unsigned int c = 0; if (x < a->leng) { c = a->nums[x]; }
		unsigned int d = 0; if (y < b->leng) { d = b->nums[y]; }
		unsigned int lo = ((c & 0xffff) + (d & 0xffff) + (over & 0xffff));
		unsigned int hi = (((c >> 16) & 0xffff) + ((d >> 16) & 0xffff) + ((over >> 16) & 0xffff) + ((lo >> 16) & 0xffff));
		over = ((hi >> 16) & 0xffff);
		r->nums[z] = (((hi << 16) & 0xffff0000) | (lo & 0xffff));
		++x; ++y; ++z;
	}
	if (over > 0) { r->nums[z] = over; ++z; }
	r->sign = (a->sign | b->sign);
	r->leng = z;
	return 1;
}

int bnsub(bnum *a, bnum *b, bnum *r, int s)
{
	int x = 0, y = 0;
	int n = 1, g = 0;
	bnum *t = a, *m = b, *temp;
	if (s == 0)
	{
		if ((a->sign == 0) && (b->sign == 1))
		{
			b->sign = 0;
			bnadd(a, b, r, 0); g = r->sign;
			b->sign = 1;
			r->sign = g;
			return 0;
		}
		else if ((a->sign == 1) && (b->sign == 0))
		{
			a->sign = 0;
			bnadd(a, b, r, 0);
			a->sign = 1;
			r->sign = 1;
			return 0;
		}
		else if ((a->sign == 1) && (b->sign == 1))
		{
			t = b; m = a;
		}
		s = bncmp(t, m);
		if (s < 0)
		{
			g = 1;
			temp = t;
			t = m;
			m = temp;
		}
		else if (s == 0)
		{
			r->sign = 0; r->leng = 1;
			r->nums[0] = 0;
			return 2;
		}
	}
	int indx = -1;
	unsigned int over = 0;
	while ((x < t->leng) || (y < m->leng))
	{
		unsigned int c = 0; if (x < t->leng) { c = t->nums[x]; }
		unsigned int d = 0; if (y < m->leng) { d = m->nums[y]; }
		if (x == indx) { c = over; indx = -1; }
		if (c < d)
		{
			int i = x, z;
			for (z = (x + 1); z < t->leng; ++z)
			{
				if (t->nums[z] > 0)
				{
					unsigned int hic = ((1 << 16) + (c >> 16)), loc = (c & 0xffff);
					unsigned int hid = (d >> 16)              , lod = (d & 0xffff);
					if (loc < lod) { hic -= 1; loc += (1 << 16); }
					r->nums[i] = (((hic - hid) << 16) + (loc - lod));
					indx = z; over = (t->nums[z] - 1);
					if (r->nums[i] > 0) { n = max(n, (i + 1)); }
					break;
				}
				++x; ++y;
				if (y < m->leng) { r->nums[z] = (0xffffffff - m->nums[y]); }
				else { r->nums[z] = 0xffffffff; }
				if (r->nums[z] > 0) { n = max(n, (z + 1)); }
			}
		}
		else { r->nums[x] = (c - d); }
		if (r->nums[x] > 0) { n = max(n, (x + 1)); }
		++x; ++y;
	}
	r->sign = g;
	r->leng = n;
	return 1;
}

void bnmul(bnum *a, bnum *b, bnum *r)
{
	int x, y;
	bnum *dub = bninit(r->size);
	bncopy(b, dub);
	for (x = 0; x < a->leng; ++x)
	{
		for (y = 0; y < 32; ++y)
		{
			if (((a->nums[x] >> y) & 0x1) == 1)
			{
				bnadd(r, dub, r, 1);
			}
			bnadd(dub, dub, dub, 1);
		}
	}
	r->sign = (a->sign ^ b->sign);
	bnfree(dub);
}

void bndiv(bnum *a, bnum *b, bnum *r, bnum *m)
{
	int s = 0, d = 0, c = bncmp(a, b);
	bnum *t = bninit(max(a->size, b->size) * 2);
	bncopy(a, t);
	r->nums[0] = 0; r->leng = 1;
	m->nums[0] = 0; m->leng = 1;
	if (c < 0)
	{
		//printf("return <\n");
		r->nums[0] = 0; r->leng = 1;
		bncopy(a, m);
	}
	else if (c == 0)
	{
		//printf("return ==\n");
		r->nums[0] = 1; r->leng = 1;
		m->nums[0] = 0; m->leng = 1;
	}
	else if ((b->leng == 1) && (b->nums[0] == 0))
	{
		//printf("return /0!\n");
	}
	else if (c > 0)
	{
		int hir = 0;
		
		//printf("> right shift the number to match the divider\n");
		int hia = bnhigh(a), hib = bnhigh(b), hid = (hia - hib - 1);
		bnrshift(t, hid + 1);
		c = bncmp(t, b);
		if (c < 0) { s = 1; }
		
		while (1)
		{
			if (s == 1)
			{
				//printf("equal bit length but number < divider\n");
				int abyte = (hid / 32), abit = (hid % 32);
				int bitv = ((a->nums[abyte] & (1 << abit)) >> abit);
				bnlshift(t, 1); t->nums[0] |= bitv;
				--hid;
				if (d > 0) { bnlshift(r, 1); ++hir; }
			}
			s = 0;
			
			//printf("substract num - div and shift 1 into result\n");
			bnsub(t, b, t, 1);
			bnlshift(r, 1); r->nums[0] |= 1; ++hir;
			
			int hit = bnhigh(t);
			d = 0;
			while ((hit < hib) && (hid > -1))
			{
				int abyte = (hid / 32), abit = (hid % 32);
				int diff = min(hib - hit, 32);
				if ((hid + 1) >= diff)
				{
					//printf("large: shift another bit into the number to match the divider\n");
					hid -= (diff - 1);
					int bbyte = (hid / 32), bbit = (hid % 32);
					--hid;
					bnlshift(t, diff);
					t->nums[0] = (t->nums[0] | ((a->nums[abyte] << (31 - abit)) >> (32 - diff)));
					if (abyte != bbyte) { t->nums[0] = (t->nums[0] | (a->nums[bbyte] >> bbit)); }
					d += diff;
				}
				else
				{
					//printf("small: shift another bit into the number to match the divider\n");
					int bitv = ((a->nums[abyte] & (1 << abit)) >> abit);
					bnlshift(t, 1); t->nums[0] |= bitv;
					--hid;
					++d;
				}
				hit = bnhigh(t);
			}
			if (d > 1) { bnlshift(r, d - 1); hir += (d - 1); }
			
			//printf("check resulting number and break if done dividing else repeat\n");
			c = bncmp(t, b);
			if (c < 0)
			{
				if (hid < 0)
				{
					//printf("exiting <\n");
					if (d > 0) { bnlshift(r, 1); ++hir; }
					bncopy(t, m);
					break;
				}
				s = 1;
			}
			else if (c == 0)
			{
				if (hid < 0)
				{
					//printf("exiting ==\n");
					bnlshift(r, 1); r->nums[0] |= 1; ++hir;
					break;
				}
			}
		}
	}
	r->sign = (a->sign ^ b->sign);
	m->sign = r->sign;
	bnfree(t);
}

void bnpowmod(bnum *b, bnum *e, bnum *m, bnum *r)
{
	int s = max(max(b->size, e->size), max(m->size, r->size));
	bnum *t = bninit(s * 3), *u = bninit(s * 3);
	bnum *base = bninit(s * 3), *exp = bninit(s * 3);
	bncopy(b, base); bncopy(e, exp);
	r->nums[0] = 1; r->leng = 1;
	while ((exp->leng > 1) || (exp->nums[0] > 0))
	{
		if ((exp->nums[0] % 2) == 1)
		{
			// r = r * base
			bnzero(t); bnmul(r, base, t);
			// r = r % m
			bndiv(t, m, u, r);
		}
		// exp = exp / 2
		bnrshift(exp, 1);
		// b = b * b
		bnzero(t); bnmul(base, base, t);
		// b = b % m
		bndiv(t, m, u, base);
	}
	// free the rest
	bnfree(base); bnfree(exp);
	bnfree(t); bnfree(u);
}

Combinatorial Craziness and Credit Card Companies…

So I was looking at my WellsFargo credit card transactions and noticed that my current outstanding balance wasn’t adding up to difference between my last payment and my current purchases + pending transactions (roughly $13.20). It was driving me crazy so I wrote a little py script to try and check all the different combinations of some of my past transactions to see if any of them added up to the difference missing. Note: turns out my efforts were ultimately unnecessary as WellsFargo was adding un-posted transactions to the outstanding balance and just pushed them now so I could see them! The script below which is a bit hacky and slow but it was able to work as intended for the most part anyway:

$ python cc.py /tmp/cc2.txt 13.20
([4.15, 5.92, 3.19, 7.92, 2.83, 5.97, 8.32, 11.28, 3.09, 4.25, 8.97, 3.13, 6.52, 6.7, 7.64], 13.2)
(0/4.15) + (1/5.92) + (11/3.13) = 13.20 == 13.20
(0/4.15) + (4/2.83) + (8/3.09) + (11/3.13) = 13.20 == 13.20
(15, 'inputs', '->', 32767, 'combinations')

import sys
numf = open(sys.argv[1], "r")
numl = numf.read().split("\n")
numf.close()
target = float(sys.argv[2])
nums = []
for num in numl:
	if (not "$" in num):
		continue
	if ("+" in num):
		continue
	numt = float(num.replace("$", ""))
	if (numt > target):
		continue
	nums.append(numt)
print(nums, target)
# x is the total number of indexes being added together
c = 0
leng = len(nums)
for x in range(1, leng + 1):
	brute = []
	for y in range(0, x):
		# set below to 0 for a full set of combinations
		brute.append(y)
	while (1):
		s = 0
		t = ""
		for i in brute:
			t += (" + (%d/%.2f)" % (i, nums[i]))
			s += nums[i]
		if (s == target):
			print("%s = %.2f == %.2f" % (t[3:], s, target))
		c += 1
		o = 1
		f = 0
		i = (x - 1)
		while (i > -1):
			brute[i] += o
			o = 0
			# set below to 0 for a full set of combinations
			if (brute[i] > (leng - (x - i))):
				brute[i] = (brute[i - 1] + 2)
				o = 1
				f += 1
			i -= 1
		if (f == x):
			break
		# remove below for a full set of combinations
		i = 0
		while (i < x):
			if (brute[i] > (leng - (x - i))):
				brute[i] = (brute[i - 1] + 1)
			i += 1
print(len(nums), "inputs", "->", c, "combinations")