From a2a74efe4b1276b1efec12f25fd65f0df060f38a Mon Sep 17 00:00:00 2001 From: mdw Date: Sun, 8 Oct 2000 16:01:37 +0000 Subject: [PATCH] Prototypes of various bits of code. --- calc/ecp.cal | 133 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ calc/gfx-test.cal | 106 +++++++++++++++++++++++++++++++++++++++++++ calc/gfx.cal | 104 ++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 343 insertions(+) create mode 100644 calc/ecp.cal create mode 100644 calc/gfx-test.cal create mode 100644 calc/gfx.cal diff --git a/calc/ecp.cal b/calc/ecp.cal new file mode 100644 index 0000000..04971aa --- /dev/null +++ b/calc/ecp.cal @@ -0,0 +1,133 @@ +/* -*-apcalc-*- + * + * $Id: ecp.cal,v 1.1 2000/10/08 16:01:37 mdw Exp $ + * + * Testbed for elliptic curve arithmetic over prime fields + * + * (c) 2000 Straylight/Edgeware + */ + +/*----- Licensing notice --------------------------------------------------* + * + * This file is part of Catacomb. + * + * Catacomb is free software; you can redistribute it and/or modify + * it under the terms of the GNU Library General Public License as + * published by the Free Software Foundation; either version 2 of the + * License, or (at your option) any later version. + * + * Catacomb is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU Library General Public License for more details. + * + * You should have received a copy of the GNU Library General Public + * License along with Catacomb; if not, write to the Free + * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, + * MA 02111-1307, USA. + */ + +/*----- Revision history --------------------------------------------------* + * + * $Log: ecp.cal,v $ + * Revision 1.1 2000/10/08 16:01:37 mdw + * Prototypes of various bits of code. + * + */ + +/*----- Object types ------------------------------------------------------*/ + +obj ecp_curve { a, b, p }; +obj ecp_pt { x, y, e }; + +/*----- Main code ---------------------------------------------------------*/ + +define ecp_curve(a, b, p) +{ + local obj ecp_curve e; + e.a = a; + e.b = b; + e.p = p; + return (e); +} + +define ecp_pt(x, y, e) +{ + local obj ecp_pt p; + p.x = x % e.p; + p.y = y % e.p; + p.e = e; + return (p); +} + +define ecp_pt_print(a) +{ + print "(" : a.x : ", " : a.y : ")" :; +} + +define ecp_pt_add(a, b) +{ + local e, alpha; + local obj ecp_pt d; + + if (a == 0) + d = b; + else if (b == 0) + d = a; + else if (!istype(a, b)) + quit "bad type arguments to ecp_pt_add"; + else if (a.e != b.e) + quit "points from different curves in ecp_pt_add"; + else { + e = a.e; + if (a.x == b.x) { + if (a.y != b.y) { + return (0); + } + alpha = (3 * a.x^2 + e.a) * minv(2 * a.y, e.p) % e.p; + } else + alpha = (b.y - a.y) * minv(b.x - a.x, e.p) % e.p; + + d.x = (alpha^2 - a.x - b.x) % e.p; + d.y = (-a.y + alpha * (a.x - d.x)) % e.p; + d.e = e; + } + + return (d); +} + +define ecp_pt_neg(a) +{ + local obj ecp_pt d; + d.x = a.x; + d.y = -a.y; + d.e = a.e; + return (d); +} + +define ecp_pt_mul(a, b) +{ + local p, n; + local d; + + if (istype(a, 1)) { + n = a; + p = b; + } else if (istype(b, 1)) { + n = b; + p = a; + } else + return (newerror("bad arguments to ecp_pt_mul")); + + d = 0; + while (n) { + if (n & 1) + d += p; + n >>= 1; + p += p; + } + return (d); +} + +/*----- That's all, folks -------------------------------------------------*/ + diff --git a/calc/gfx-test.cal b/calc/gfx-test.cal new file mode 100644 index 0000000..4bdee42 --- /dev/null +++ b/calc/gfx-test.cal @@ -0,0 +1,106 @@ +/* -*-apcalc-*- + * + * $Id: gfx-test.cal,v 1.1 2000/10/08 16:01:37 mdw Exp $ + * + * Generate test cases for %$\gf{2}[x]$% arithmetic + * + * (c) 2000 Straylight/Edgeware + */ + +/*----- Licensing notice --------------------------------------------------* + * + * This file is part of Catacomb. + * + * Catacomb is free software; you can redistribute it and/or modify + * it under the terms of the GNU Library General Public License as + * published by the Free Software Foundation; either version 2 of the + * License, or (at your option) any later version. + * + * Catacomb is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU Library General Public License for more details. + * + * You should have received a copy of the GNU Library General Public + * License along with Catacomb; if not, write to the Free + * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, + * MA 02111-1307, USA. + */ + +/*----- Revision history --------------------------------------------------* + * + * $Log: gfx-test.cal,v $ + * Revision 1.1 2000/10/08 16:01:37 mdw + * Prototypes of various bits of code. + * + */ + +/*----- External units ----------------------------------------------------*/ + +read gfx; + +/*----- Global variables --------------------------------------------------*/ + +global op = "+", n = 40, bits = 128; + +/*----- Main code ---------------------------------------------------------*/ + +dummy = config("lib_debug", -1); + +define gfx_test() { + local i, j, x; + local a, b, l; + + for (i = 0; i < n; i++) { + + /* --- Select the inputs and produce the outputs --- */ + + switch (op) { + case '+': + case '-': + a = gf(random(1 << bits)); + b = gf(random(1 << bits)); + l = list(a, b, a + b); + break; + case '*': + a = gf(random(1 << bits)); + b = gf(random(1 << bits)); + l = list(a, b, a * b); + break; + case '2': + a = gf(random(1 << bits)); + l = list(a, a * a); + break; + case '/': + a = gf(random(1 << (bits + random(bits)))); + b = gf(random(1 << bits)); + l = list(a, b, a / b, a % b); + break; + default: + exit "unknown operator"; + break; + } + + /* --- Output the test vector --- * + * + * Be careful to ensure that it has an even number of hex digits in each + * number. + */ + + for (j = 0; j < size(l); j++) { + x = strprintf("%x", l[[j]].x); + if (strlen(x) > 1) + x = substr(x, 3, strlen(x) - 2); + if (strlen(x) % 2) + x = strcat("0", x); + x = strcat(" ", x); + if (j) + x = strcat(" ", x); + if (j == size(l) - 1) + x = strcat(x, ";"); + printf("%s\n", x); + } + } +} + +/*----- That's all, folks -------------------------------------------------*/ diff --git a/calc/gfx.cal b/calc/gfx.cal new file mode 100644 index 0000000..8d8fd00 --- /dev/null +++ b/calc/gfx.cal @@ -0,0 +1,104 @@ +/* -*-apcalc-*- + * + * $Id: gfx.cal,v 1.1 2000/10/08 16:01:37 mdw Exp $ + * + * Testbed for %$\gf{2}$% poltnomial arithmetic + * + * (c) 2000 Straylight/Edgeware + */ + +/*----- Licensing notice --------------------------------------------------* + * + * This file is part of Catacomb. + * + * Catacomb is free software; you can redistribute it and/or modify + * it under the terms of the GNU Library General Public License as + * published by the Free Software Foundation; either version 2 of the + * License, or (at your option) any later version. + * + * Catacomb is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU Library General Public License for more details. + * + * You should have received a copy of the GNU Library General Public + * License along with Catacomb; if not, write to the Free + * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, + * MA 02111-1307, USA. + */ + +/*----- Revision history --------------------------------------------------* + * + * $Log: gfx.cal,v $ + * Revision 1.1 2000/10/08 16:01:37 mdw + * Prototypes of various bits of code. + * + */ + +/*----- Object types ------------------------------------------------------*/ + +obj gf { x }; + +/*----- Static variables --------------------------------------------------*/ + +static obj gf example_gf_object; + +/*----- Main code ---------------------------------------------------------*/ + +dummy = config("lib_debug", -1); + +define gf(x) +{ + local obj gf g; + g.x = x; + return (g); +} + +define gfint(x) +{ + if (istype(x, example_gf_object)) + return (x.x); + else + return (x); +} + +define gf_add(x, y) = gf(xor(gfint(x), gfint(y))); +define gf_sub(x, y) = gf(xor(gfint(x), gfint(y))); +define gf_neg(x) = x; + +define gf_mul(x, y) +{ + local a = gfint(x), b = gfint(y), z = 0, i, bits = highbit(a); + for (i = 0; i <= bits; i++) { + if (bit(a, i)) + z = xor(z, b << i); + } + return gf(z); +} + +define gfx_div(rx, dx) +{ + local r = gfint(rx), d = gfint(dx), i; + local q = 0, dbits = highbit(d), rbits = highbit(r); + for (i = rbits - dbits; i >= 0; i--) { + if (bit(r, i + dbits)) { + r = xor(r, d << i); + q |= (1 << i); + } + } + return list(q, r); +} + +define gf_div(x, y) +{ + local l = gfx_div(x, y); + return gf(l[[0]]); +} + +define gf_mod(x, y) +{ + local l = gfx_div(x, y); + return gf(l[[1]]); +} + +/*----- That's all, folks -------------------------------------------------*/ -- 2.11.0