--- /dev/null
+/* -*-c-*-
+ *
+ * $Id: mpbarrett.c,v 1.1 1999/12/10 23:21:59 mdw Exp $
+ *
+ * Barrett modular reduction
+ *
+ * (c) 1999 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: mpbarrett.c,v $
+ * Revision 1.1 1999/12/10 23:21:59 mdw
+ * Barrett reduction support: works with even moduli.
+ *
+ */
+
+/*----- Header files ------------------------------------------------------*/
+
+#include "mp.h"
+#include "mpbarrett.h"
+
+/*----- Main code ---------------------------------------------------------*/
+
+/* --- @mpbarrett_create@ --- *
+ *
+ * Arguments: @mpbarrett *mb@ = pointer to Barrett reduction context
+ * @mp *m@ = modulus to work to
+ *
+ *
+ * Returns: ---
+ *
+ * Use: Initializes a Barrett reduction context ready for use.
+ */
+
+void mpbarrett_create(mpbarrett *mb, mp *m)
+{
+ mp *b;
+
+ /* --- Validate the arguments --- */
+
+ assert(((void)"Barrett modulus must be positive", (m->f & MP_NEG) == 0));
+
+ /* --- Compute %$\mu$% --- */
+
+ mp_shrink(m);
+ mb->k = MP_LEN(m);
+ mb->m = MP_COPY(m);
+ b = mp_lsl(MP_NEW, MP_ONE, 2 * MPW_BITS * mb->k);
+ mp_div(&b, 0, b, m);
+ mb->mu = b;
+}
+
+/* --- @mpbarrett_destroy@ --- *
+ *
+ * Arguments: @mpbarrett *mb@ = pointer to Barrett reduction context
+ *
+ * Returns: ---
+ *
+ * Use: Destroys a Barrett reduction context releasing any resources
+ * claimed.
+ */
+
+void mpbarrett_destroy(mpbarrett *mb)
+{
+ mp_drop(mb->m);
+ mp_drop(mb->mu);
+}
+
+/* --- @mpbarrett_reduce@ --- *
+ *
+ * Arguments: @mpbarrett *mb@ = pointer to Barrett reduction context
+ * @mp *d@ = destination for result
+ * @mp *m@ = number to reduce
+ *
+ * Returns: The residue of @m@ modulo the number in the reduction
+ * context.
+ *
+ * Use: Performs an efficient modular reduction. The argument is
+ * assumed to be positive.
+ */
+
+mp *mpbarrett_reduce(mpbarrett *mb, mp *d, mp *m)
+{
+ mp *q;
+ size_t k = mb->k;
+
+ /* --- Special case if @m@ is too small --- */
+
+ if (MP_LEN(m) < k) {
+ m = MP_COPY(m);
+ MP_DROP(d);
+ return (m);
+ }
+
+ /* --- First stage --- */
+
+ {
+ mp qq;
+ mp_build(&qq, m->v + (k - 1), m->vl);
+ q = mp_mul(MP_NEW, &qq, mb->mu);
+ q = mp_lsr(q, q, MPW_BITS * (k + 1));
+ }
+
+ /* --- Second stage --- */
+
+ {
+ mp *r;
+ mpw *mvl;
+
+ MP_COPY(m);
+ if (MP_LEN(m) <= k + 1)
+ mvl = m->vl;
+ else
+ mvl = m->v + k + 1;
+ r = mp_create(k + 1);
+ mpx_umul(r->v, r->vl, q->v, q->vl, mb->m->v, mb->m->vl);
+ r->f = (q->f | mb->m->f) & MP_BURN;
+ MP_MODIFY(d, k + 1);
+ mpx_usub(d->v, d->vl, m->v, mvl, r->v, r->vl);
+ d->f = (m->f | r->f) & MP_BURN;
+ MP_DROP(r);
+ MP_DROP(q);
+ MP_DROP(m);
+ }
+
+ /* --- Final stage --- */
+
+ MP_SHRINK(d);
+ while (MPX_UCMP(d->v, d->vl, >=, mb->m->v, mb->m->vl))
+ mpx_usub(d->v, d->vl, d->v, d->vl, mb->m->v, mb->m->vl);
+
+ MP_SHRINK(d);
+ return (d);
+}
+
+/* --- @mpbarrett_exp@ --- *
+ *
+ * Arguments: @mpbarrett *mb@ = pointer to Barrett reduction context
+ * @mp *d@ = fake destination
+ * @mp *a@ = base
+ * @mp *e@ = exponent
+ *
+ * Returns: Result, %$a^e \bmod m$%.
+ */
+
+mp *mpbarrett_exp(mpbarrett *mb, mp *d, mp *a, mp *e)
+{
+ mpscan sc;
+ mp *x = MP_ONE;
+ mp *spare = MP_NEW;
+
+ a = MP_COPY(a);
+ mp_scan(&sc, e);
+ if (MP_STEP(&sc)) {
+ size_t sq = 0;
+ for (;;) {
+ mp *dd;
+ if (MP_BIT(&sc)) {
+ while (sq) {
+ dd = mp_sqr(spare, a);
+ dd = mpbarrett_reduce(mb, dd, dd);
+ spare = a; a = dd;
+ sq--;
+ }
+ dd = mp_mul(spare, x, a);
+ dd = mpbarrett_reduce(mb, dd, dd);
+ spare = x; x = dd;
+ }
+ sq++;
+ if (!MP_STEP(&sc))
+ break;
+ }
+ }
+
+ MP_DROP(a);
+ if (spare != MP_NEW)
+ MP_DROP(spare);
+ if (d != MP_NEW)
+ MP_DROP(d);
+ return (x);
+}
+
+/*----- Test rig ----------------------------------------------------------*/
+
+#ifdef TEST_RIG
+
+static int vmod(dstr *v)
+{
+ mp *x = *(mp **)v[0].buf;
+ mp *n = *(mp **)v[1].buf;
+ mp *r = *(mp **)v[2].buf;
+ mp *s;
+ mpbarrett mb;
+ int ok = 1;
+
+ mpbarrett_create(&mb, n);
+ s = mpbarrett_reduce(&mb, MP_NEW, x);
+
+ if (MP_CMP(s, !=, r)) {
+ fputs("\n*** barrett reduction failure\n", stderr);
+ fputs("x = ", stderr); mp_writefile(x, stderr, 10); fputc('\n', stderr);
+ fputs("n = ", stderr); mp_writefile(n, stderr, 10); fputc('\n', stderr);
+ fputs("r = ", stderr); mp_writefile(r, stderr, 10); fputc('\n', stderr);
+ fputs("s = ", stderr); mp_writefile(s, stderr, 10); fputc('\n', stderr);
+ ok = 0;
+ }
+
+ mpbarrett_destroy(&mb);
+ mp_drop(x);
+ mp_drop(n);
+ mp_drop(r);
+ mp_drop(s);
+ assert(mparena_count(MPARENA_GLOBAL) == 0);
+ return (ok);
+}
+
+static int vexp(dstr *v)
+{
+ mp *m = *(mp **)v[0].buf;
+ mp *a = *(mp **)v[1].buf;
+ mp *b = *(mp **)v[2].buf;
+ mp *r = *(mp **)v[3].buf;
+ mp *mr;
+ int ok = 1;
+
+ mpbarrett mb;
+ mpbarrett_create(&mb, m);
+
+ mr = mpbarrett_exp(&mb, MP_NEW, a, b);
+
+ if (MP_CMP(mr, !=, r)) {
+ fputs("\n*** barrett modexp failed", stderr);
+ fputs("\n m = ", stderr); mp_writefile(m, stderr, 10);
+ fputs("\n a = ", stderr); mp_writefile(a, stderr, 10);
+ fputs("\n e = ", stderr); mp_writefile(b, stderr, 10);
+ fputs("\n r = ", stderr); mp_writefile(r, stderr, 10);
+ fputs("\nmr = ", stderr); mp_writefile(mr, stderr, 10);
+ fputc('\n', stderr);
+ ok = 0;
+ }
+
+ mp_drop(m);
+ mp_drop(a);
+ mp_drop(b);
+ mp_drop(r);
+ mp_drop(mr);
+ mpbarrett_destroy(&mb);
+ assert(mparena_count(MPARENA_GLOBAL) == 0);
+ return ok;
+}
+
+static test_chunk tests[] = {
+ { "mpbarrett-reduce", vmod, { &type_mp, &type_mp, &type_mp, 0 } },
+ { "mpbarrett-exp", vexp, { &type_mp, &type_mp, &type_mp, &type_mp, 0 } },
+ { 0, 0, { 0 } }
+};
+
+int main(int argc, char *argv[])
+{
+ sub_init();
+ test_run(argc, argv, tests, SRCDIR "/tests/mpbarrett");
+ return (0);
+}
+
+#endif
+
+/*----- That's all, folks -------------------------------------------------*/
--- /dev/null
+/* -*-c-*-
+ *
+ * $Id: mpbarrett.h,v 1.1 1999/12/10 23:22:00 mdw Exp $
+ *
+ * Barrett modular reduction
+ *
+ * (c) 1999 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: mpbarrett.h,v $
+ * Revision 1.1 1999/12/10 23:22:00 mdw
+ * Barrett reduction support: works with even moduli.
+ *
+ */
+
+/*----- Notes on Barrett reduction ----------------------------------------*
+ *
+ * Barrett reduction is a technique for computing modular residues. Unlike
+ * Montgomery reduction, it doesn't have restrictions on the modulus (except
+ * that it be positive) and doesn't confuse matters by putting an extra
+ * factor all the way through your computation.
+ *
+ * It's useful for slightly less heavy-duty work than Montgomery reduction
+ * because the precomputation phase is rather simpler, involving a single
+ * division operation.
+ *
+ * Sometimes it's useful to exponentiate modulo an even number, so there's a
+ * modexp routine provided which uses Barrett reduction rather than
+ * Montgomery reduction. This is handy when you're working on indices in an
+ * even-order cyclic group or something.
+ */
+
+#ifndef CATACOMB_MPBARRETT_H
+#define CATACOMB_MPBARRETT_H
+
+#ifdef __cplusplus
+ extern "C" {
+#endif
+
+/*----- Header files ------------------------------------------------------*/
+
+#ifndef CATACOMB_MP_H
+# include "mp.h"
+#endif
+
+/*----- Data structures ---------------------------------------------------*/
+
+typedef struct mpbarrett {
+ mp *m;
+ mp *mu;
+ size_t k;
+} mpbarrett;
+
+/*----- Functions provided ------------------------------------------------*/
+
+/* --- @mpbarrett_create@ --- *
+ *
+ * Arguments: @mpbarrett *mb@ = pointer to Barrett reduction context
+ * @mp *m@ = modulus to work to
+ *
+ *
+ * Returns: ---
+ *
+ * Use: Initializes a Barrett reduction context ready for use.
+ */
+
+extern void mpbarrett_create(mpbarrett */*mb*/, mp */*m*/);
+
+/* --- @mpbarrett_destroy@ --- *
+ *
+ * Arguments: @mpbarrett *mb@ = pointer to Barrett reduction context
+ *
+ * Returns: ---
+ *
+ * Use: Destroys a Barrett reduction context releasing any resources
+ * claimed.
+ */
+
+extern void mpbarrett_destroy(mpbarrett */*mb*/);
+
+/* --- @mpbarrett_reduce@ --- *
+ *
+ * Arguments: @mpbarrett *mb@ = pointer to Barrett reduction context
+ * @mp *d@ = destination for result
+ * @mp *m@ = number to reduce
+ *
+ * Returns: The residue of @m@ modulo the number in the reduction
+ * context.
+ *
+ * Use: Performs an efficient modular reduction. The argument is
+ * assumed to be positive.
+ */
+
+extern mp *mpbarrett_reduce(mpbarrett */*mb*/, mp */*d*/, mp */*m*/);
+
+/* --- @mpbarrett_exp@ --- *
+ *
+ * Arguments: @mpbarrett *mb@ = pointer to Barrett reduction context
+ * @mp *d@ = fake destination
+ * @mp *a@ = base
+ * @mp *e@ = exponent
+ *
+ * Returns: Result, %$a^e \bmod m$%.
+ */
+
+extern mp *mpbarrett_exp(mpbarrett */*mb*/, mp */*d*/, mp */*a*/, mp */*e*/);
+
+/*----- That's all, folks -------------------------------------------------*/
+
+#ifdef __cplusplus
+ }
+#endif
+
+#endif
--- /dev/null
+# Test vectors for Barrett modular reduction
+#
+# $Id: mpbarrett,v 1.1 1999/12/10 23:25:27 mdw Exp $
+
+mpbarrett-reduce {
+ 17 11 6;
+
+ 0x8ab316d0d1a2e88535cf77c1172881ead70d592c59e9c5fbc16e4b0c4dc49481
+ 0x18ca3bf7ee3c6d7bab3f144b015ccc6c25472843d346b461
+ 0x02c1815029b766b96ad4507dc1af8151307961c6d161d065;
+
+ 0x8117d1663ee63341eb8faeff304549f0f8b32d587acc2fd5597ea6a31625881d
+ 0xdc85df77dfb61876805623bcbed325b99d00c2cd65c252c879
+ 0x395da02e8a6c66476467c4e04f328d8208cc411e3d1e96e14c;
+
+ 0x63791966f2ad44a6df11bcc87c6b7c2400c74e69f7e3ca02fcac12b3bf56238b
+ 0xa49e473b8f7539d89cdb002d73182558773eec10db93cc6049d8c5533e
+ 0x65caf6833baa118b53c7bdc44a831605ca382b5993beead59f3971d13f;
+
+ 0x9ca438db3e0f79305987292e8ec6174e6c313f7904ebb35a349a700e3ae63a37
+ 0xb24c93d499c7073b8f7aac718c1f12da1a8fc8bccdd47b49
+ 0x46393cb15e38cbbc8a85698151a113f28081b4c8f6ed232e;
+
+ 0x8214fd17858a4a913015412b5331eb9654faeb5156a674b1e5f6550a68957146
+ 0xc4f0ebaad6c0ee0111c57667ea8e0a254f3068f212949e20ededa89a7da6
+ 0x3fde916ba21d19414d4316041420ca59d8b01aa2acf3f3ef106245c1915c;
+
+ 0x367aa8f5ba9ac4e8e2ea198b8af2c3b3081deab392ffc05715783b245a62a6fa
+ 0x72e2c37447f8bca34c4a39b130ea8e5c9a7d8b54564aa88ea773
+ 0x08e8c03ebf398c63d71d8fd7ca4ece12367a8dde180ca650afb6;
+
+ 0xae2d84438ac6643fc601c1634351aa75b284fecbbe5faf3a132be9dd1a326e6c
+ 0xc33c890f030644d88cc65f8ccf99c625c9b9fa21d4eb153e52ef89df54130855
+ 0xae2d84438ac6643fc601c1634351aa75b284fecbbe5faf3a132be9dd1a326e6c;
+
+ 0x65901dcdad8dd0625d4d158f99b666fee10480d1df15e3bdac640584b9b746bc
+ 0xd8a1d326fee87d55f39f15b5b2cfe71f5146083928
+ 0x859c41164983547c03134b99530e25a0f874315964;
+}
+
+mpbarrett-exp {
+ 4325987397987458979875737589783
+ 435365332435654643667
+ 8745435676786567758678547
+ 2439674515119108242643169132064;
+
+ 8939489893434234331 1804289383 454353454354565 6139425926295484741;
+ 8939489893434234331 1804289383 8939489893434234330 1;
+
+ # --- DSA public key derivation ---
+
+ 0xc9c7feaeaedb16505389c5582df1858d0fdb3eecfe61c230d612661bef8c1bc5
+ 0x5cd41fc97d0db5322bab7d659354db2ed9f88e39d2c6fae9f29acab5a522131e
+ 0x1234
+ 0x51812af9600c89ffe0f73902eb09015c03b4e0fbf6ccf073931c12f9aad1fb47;
+
+ 0xdde5808744e1cd37c88667e7033694b2513a7429f035f11c0bafc4dff2b96a672bd0a3ca16aba2ea526df00c8571106ba4a1d83eb62605fc9274ab70bef0a111cd070cca2d8b10edf042d6c44f863c36fabea8bb0d7340eb8c169da27a4b0ba2713c166152a0244235093391c5f71aee8c03dcaf2335a2e4689ccb27ba365ec7
+ 0x65985e4c2d6027a8afdeb9b44cc619e1c4d46bde873e0d4b45325412a2f8365e51245324f888704295fe8233a6666624d9a4701172dbfcab5c9643e1caab79eb2a0c85284d1b858688b8f16804326321f53a723502a6d6ae08dcbffccf2187a799f6281c2478ef0faed5c5c80adeabc5ee435cff8b9ae0b603e47fb08d73b014
+ 0x23a252f60bae4907a8ed5b6203e2b1da32848cd9
+ 0x9720498d8ec1208585635faaf952c1204c37119acccc64ed7942867be24770e33db39ffcfa1194549ead8495a7918a20e15144e68125860ef4f8c1a3d771bad690938bdb2c8817e2b89a8fc615d067084a7a2f2f9280e15fb9ccebfe713584260d5ed30545b69745d7b22977bfd44d60d7c5e657aab1c79dc5cb33ff29ee9074;
+
+ # --- Quick RSA test ---
+
+ 905609324890967090294090970600361 # This is p
+ 3
+ 905609324890967090294090970600360 # This is (p - 1)
+ 1; # Fermat test: p is prime
+
+ 734589569806680985408670989082927 # This is q
+ 5
+ 734589569806680985408670989082926 # And this is (q - 1)
+ 1; # Fermat again: q is prime
+
+ # --- Encrypt a message ---
+ #
+ # The public and private exponents are from the GCD test. The message
+ # is just obvious. The modulus is the product of the two primes above.
+
+ 665251164384574309450646977867045404520085938543622535546005136647
+ 123456789012345678901234567890123456789012345678901234567890
+ 5945908509680983480596809586040589085680968709809890671
+ 25906467774034212974484417859588980567136610347807401817990462701;
+
+ # --- And decrypt it again ---
+
+ 665251164384574309450646977867045404520085938543622535546005136647
+ 25906467774034212974484417859588980567136610347807401817990462701
+ 514778499400157641662814932021958856708417966520837469125919104431
+ 123456789012345678901234567890123456789012345678901234567890;
+}
projects / u / mdw / catacomb / commitdiff