From digex.com!lynx.unm.edu!umn.edu!zip.eecs.umich.edu!caen!uwm.edu!cs.utexas.edu!swrinde!elroy.jpl.nasa.gov!news.aero.org!usasoc.soc.mil!usasoc.soc.mil!rbrand Wed May 19 18:15:40 1993
Newsgroups: sci.crypt
Path: digex.com!lynx.unm.edu!umn.edu!zip.eecs.umich.edu!caen!uwm.edu!cs.utexas.edu!swrinde!elroy.jpl.nasa.gov!news.aero.org!usasoc.soc.mil!usasoc.soc.mil!rbrand
From: [email protected] (Raymond S. Brand)
Subject: LUC Public Key Encryption Made Easy
Message-ID: <[email protected]>
Keywords: source crypt LUC bc
Sender: [email protected]
Organization: is a nice thing...
Date: Wed, 19 May 1993 14:43:17 GMT
Lines: 539

#! /bin/sh
# This is a shell archive, meaning:
# 1. Remove everything above the #! /bin/sh line.
# 2. Save the resulting text in a file.
# 3. Execute the file with /bin/sh (not csh) to create the files:
#luc_func.gbc
#math_func.gbc
#luc_demo.gbc
# This archive created: Wed May 19 10:37:18 1993
export PATH; PATH=/bin:$PATH
if test -f 'luc_func.gbc'
then
echo shar: will not over-write existing file "'luc_func.gbc'"
else
sed 's/^X//' << \HI_MOM > 'luc_func.gbc'
X/*
X * LUC Public Key Encryption Made Easy
X *
X * Copyright 1993 Raymond S. Brand, All Rights Reserved
X *
X *
X * NOTE: This file conforms to the syntax of GNU bc (tested with GNU bc
X *version 1.02). If you don't have GNU bc, think of the functions
X *defined below as pseudo code.
X *
X *
X * Setup:
X *
X *Each user selects 2 large prime numbers, Prime1 and Prime2, and
X *multiplies them together to create the Modulus. Each user then
X *selects another number as the PublicKey and makes the PublicKey
X *and the Modulus known to all that wish to communicate with the
X *user.
X *
X *The chosen PublicKey must meet the following conditions:
X *
X *0 < PublicKey < Modulus
X *GCD(PublicKey, Prime1-1) = 1
X *GCD(PublicKey, Prime1+1) = 1
X *GCD(PublicKey, Prime2-1) = 1
X *GCD(PublicKey, Prime2+1) = 1
X *
X *and a good PublicKey will also meet the following conditions:
X *
X *LogBase2(Modulus) < PublicKey < Modulus-1
X *GCD(PublicKey, Prime1) = 1
X *GCD(PublicKey, Prime2) = 1
X *
X *LogBase2(Modulus) < Private1 < Modulus-1
X *LogBase2(Modulus) < Private2 < Modulus-1
X *LogBase2(Modulus) < Private3 < Modulus-1
X *LogBase2(Modulus) < Private4 < Modulus-1
X *
X *where
X *
X *Private1 = Inv_Mod_N(PublicKey, LCM(Prime1-1, Prime2-1))
X *Private2 = Inv_Mod_N(PublicKey, LCM(Prime1+1, Prime2-1))
X *Private3 = Inv_Mod_N(PublicKey, LCM(Prime1-1, Prime2+1))
X *Private4 = Inv_Mod_N(PublicKey, LCM(Prime1+1, Prime2+1))
X *
X *
X * Encrypting a message:
X *
X *To send a LUC encrypted message, PlainText, to user A, user B
X *calculates the cipher text, CipherText, as follows and sends it
X *user A.
X *
X *PlainText < Modulus_A
X *CipherText = LUC(PlainText, PublicKey_A, Modulus_A)
X *
X *
X * Decrypting a message:
X *
X *To decrypt a LUC encrypted message, CipherText, user A does the
X *following:
X *
X *CipherText < Modulus_A
X *MessageText = LUC(PrivateKey_A, CipherText, Modulus_A)
X *
X *where
X *
X *PrivateKey_A = PrivateFromMessage(CipherText, PublicKey_A,
X *Prime1_A, Prime2_A)
X *
X *or
X *
X *PrivateKey_A = PrivateFromPrimes(PublicKey_A,
X *Prime1_A, Prime2_A)
X *
X *The first method of calculating the private key has the advantage
X *of calculating a short key, and the disadvantage of having to
X *do the calculation for every message decrypted.
X *
X *The second method has the advantage of not having to do the
X *calculation for every message to be decrypted, and the disadvantage
X *of calculating a long key.
X *
X *
X * Sending a signed a message:
X *
X *To send a signed a message, MessageText, to user A, user B
X *calculates the signed message, SignedText, as follows and sends
X *it to user A:
X *
X *MessageText < Modulus_B
X *SignedText = LUC(PrivateKey_B, MessageText, Modulus_B)
X *
X *where
X *
X *PrivateKey_B = PrivateFromMessage(CipherText, PublicKey_B,
X *Prime1_B, Prime2_B)
X *
X *or
X *
X *PrivateKey_B = PrivateFromPrimes(PublicKey_B,
X *Prime1_B, Prime2_B)
X *
X *
X * Decrypting a signed message:
X *
X *Decoding a signed message, SignedText, from user B is done as
X *follows:
X *
X *SignedText < Modulus_B
X *MessageText = LUC(Public_B, SignedText, Modulus_B)
X */
X
X
X
X/*
X * LUC encryption/decryption function
X */
Xdefine luc(message, key, modulus) {
Xreturn (v_p1_n(key, message, modulus));
X}
X
X
X/*
X * Calculates LUC private key from message, public key, primes.
X */
Xdefine private_from_message(message, public, p, q) {
Xreturn (inv_mod_n(public, s(message, p, q)));
X}
X
X
X/*
X * Calculates LUC private key from public key, primes. Can be used with any
X *message but will be VERY big (slow).
X */
Xdefine private_from_primes(public, p, q) {
Xreturn (inv_mod_n(public, r(p, q)));
X}
X
X
X/*
X * Lucas function. Calculates V sub e (p, q) mod n
X */
Xdefine v_pq_n(subscript, p, q, mod) {
Xauto vm1, v, vm1_n, v_n, testbit, qek, qekm1, qek_n, qekm1_n;
X
Xif (0 == subscript) {
Xreturn (2);
X}
X
Xp = p%mod;
Xvm1 = 2;
Xv = p;
Xqek = q;
Xqekm1 = 1;
X
Xtestbit = 1;
Xwhile (testbit <= subscript) {
Xtestbit *= 2;
X}
Xtestbit /= 2;
Xsubscript -= testbit;
Xtestbit /= 2;
X
Xwhile (testbit >= 1) {
Xif (testbit > subscript) {
Xvm1_n = (v*vm1)%mod;
Xvm1_n += (mod-((p*qekm1)%mod))%mod;
Xvm1_n %= mod;
Xv_n = (v*v)%mod;
Xv_n += (mod-((2*qek)%mod))%mod;
Xv_n %= mod;
Xqek_n = qek*qek;
Xqekm1_n = qek*qekm1;
X} else {
Xvm1_n = (v*v)%mod;
Xvm1_n += (mod-((2*qek)%mod))%mod;
Xvm1_n %= mod;
Xv_n = (p*((v*v)%mod))%mod;
Xv_n += (mod-((q*v*vm1)%mod))%mod;
Xv_n += (mod-((p*qek)%mod))%mod;
Xv_n %= mod;
Xqek_n = q*qek*qek;
Xqekm1_n = qek*qek;
X
Xsubscript -= testbit;
X}
X
Xvm1 = vm1_n;
Xv = v_n;
Xqek = qek_n;
Xqekm1 = qekm1_n;
X
Xtestbit /= 2;
X}
X
Xreturn (v);
X}
X
X
X/*
X * Lucas function. Calculates V sub e (p, 1) mod n
X */
Xdefine v_p1_n(subscript, p, mod) {
Xauto vm1, v, vm1_next, v_next, testbit;
X
Xif (0 == subscript) {
Xreturn (2);
X}
X
Xp = p%mod;
Xvm1 = 2;
Xv = p;
X
Xtestbit = 1;
Xwhile (testbit <= subscript) {
Xtestbit *= 2;
X}
Xtestbit /= 2;
Xsubscript -= testbit;
Xtestbit /= 2;
X
Xwhile (testbit >= 1) {
Xif (testbit > subscript) {
Xvm1_next = (v*vm1)%mod;
Xvm1_next += (mod-p)%mod;
Xvm1_next %= mod;
Xv_next = (v*v)%mod;
Xv_next += (mod-2)%mod;
Xv_next %= mod;
X} else {
Xvm1_next = (v*v)%mod;
Xvm1_next += (mod-2)%mod;
Xvm1_next %= mod;
Xv_next = (p*((v*v)%mod))%mod;
Xv_next += (mod-((v*vm1)%mod))%mod;
Xv_next += (mod-p)%mod;
Xv_next %= mod;
X
Xsubscript -= testbit;
X}
X
Xvm1 = vm1_next;
Xv = v_next;
X
Xtestbit /= 2;
X}
X
Xreturn (v);

X}
X
X
X/*
X * Used in calculating private key from public key, message, and primes.
X */
Xdefine s(m, p, q) {
Xauto d;
X
Xd = (m*m)-4;
X
Xreturn (lcm(p-jacobi(d, p), q-jacobi(d, q)));
X}
X
X
X/*
X * Used in calculating private key from public key and primes.
X */
Xdefine r(p, q) {
Xreturn (lcm(p-1, lcm(p+1, lcm(q-1, q+1))));
X}
HI_MOM
chmod +x 'luc_func.gbc'
fi # end of overwriting check
if test -f 'math_func.gbc'
then
echo shar: will not over-write existing file "'math_func.gbc'"
else
sed 's/^X//' << \HI_MOM > 'math_func.gbc'
X/*
X * Some generally useful functions
X *
X * Copyright 1993 Raymond S. Brand, All Rights Reserved
X */
X
X
X/*
X * GCD(a, b)
X */
Xdefine gcd(a, b) {
Xauto temp;
X
Xwhile (0 != b) {
Xtemp = a%b;
Xa = b;
Xb = temp;
X}
X
Xreturn (a);
X}
X
X
X/*
X * LCM(a, b)
X */
Xdefine lcm(a, b) {
Xreturn (a*(b/gcd(a, b)));
X}
X
X
X/*
X * Inverse of a modulo n. Finds x such that (a*x)%mod = 1 using the
X *extended Euclidean algorithm.
X */
Xdefine inv_mod_n(a, mod) {
Xauto g, g_prev, g_next, v, v_prev, v_next, quot;
X
Xg_prev = mod;
Xg = a;
Xv_prev = 0;
Xv = 1;
X
Xwhile (0 != g) {
Xg_next = g_prev%g;
Xquot = (g_prev-g_next)/g;
Xv_next = (v_prev+(mod-((quot*v)%mod)))%mod;
Xg_prev = g;
Xg = g_next;
Xv_prev = v;
Xv = v_next;
X}
X
Xreturn (v_prev);
X}
X
X
X/*
X * (x^y)%n
X */
Xdefine pow_mod_n(x, power, modulus) {
Xauto bit, result;
X
Xx %= modulus;
Xresult = 1;
X
Xwhile (power) {
Xbit = power%2;
Xpower = (power-bit)/2;
X
Xif (1 == bit) {
Xresult = (result*x)%modulus;
X}
X
Xx = (x*x)%modulus;
X}
X
Xreturn (result);
X}
X
X
X/*
X * Calculates J(a,b), the Jacobi symbol, of a and b. b should be odd.
X */
Xdefine jacobi(a, b) {
Xauto sign, temp, test, bit;
X
Xsign = 1;
X
Xwhile (a > 1) {
Xbit = a%2;
X
Xif (0 == bit) {
X/*
X * test will be != 0 only if 3 = b%8 or
X *5 = b%8
X *
X * there are much better ways of doing the
X *following
X */
Xtest = (((b*b)-1)/8)%2;
X
Xa /= 2;
X
Xif (0 != test) {
Xsign = -sign;
X}
X} else {
X/*
X * test will be != 0 only if 3 = a%4 = b%4
X *
X * there are much better ways of doing the
X *following
X */
Xtest = (((a-1)*(b-1))/4)%2;
X
Xtemp = a;
Xa = b%temp;
Xb = temp;
X
Xif (0 != test) {
Xsign = -sign;
X}
X}
X}
X
Xif (0 == a) {
Xsign = 0;
X}
X
Xreturn (sign);
X}
X
X
X/*
X * Calculates the ceiling of log base 2 of x. To calculate the number of
X *bits in the representation of a number x, use logbase2(x+1).
X */
Xdefine logbase2(x) {
Xauto log;
X
Xlog = 0;
Xx -= 1;
X
Xwhile (x > 0) {
Xlog += 1;
Xx /=2;
X}
X
Xreturn (log);
X}
HI_MOM
chmod +x 'math_func.gbc'
fi # end of overwriting check
if test -f 'luc_demo.gbc'
then
echo shar: will not over-write existing file "'luc_demo.gbc'"
else
sed 's/^X//' << \HI_MOM > 'luc_demo.gbc'
X/*
X * LUC Public Key Encryption Demo
X *
X * Copyright 1993 Raymond S. Brand, All Rights Reserved
X */
X
Xprint "
XLUC Public Key Encryption System Demonstration
X
X"
X
X/*
X * these parameters are from Dr. Dobbs Journal, Jan '93
X */
Xprime1 = 1949
Xprime2 = 2089
Xmodulus = prime1*prime2
Xpublic = 1103
Xplain = 11111
Xcipher = luc(plain, public, modulus)
Xprivate1 = private_from_message(cipher, public, prime1, prime2)
Xprivate2 = private_from_primes(public, prime1, prime2)
Xsigned = luc(plain, private1, modulus)
X
X
Xprint "Prime1 = ", prime1, "
X"
Xprint "Prime2 = ", prime2, "
X"
Xprint "Modulus = ", modulus, "
X"
Xprint "PublicKey = ", public, "
X"
Xprint "PlainText = ", plain, "
X"
Xprint "CipherText = ", cipher, "
X"
Xprint "SignedText = ", signed, "
X"
X
X
Xprint "
X
XMessage Encryption
X
X"
Xprint "LUC(PlainText, PublicKey, Modulus) = ", luc(plain, public, modulus), "
X
X"
Xprint "PrivateKey calculated with CipherText = ", private_from_message(cipher, public, prime1, prime2), "
X"
Xprint "LUC(CipherText, PrivateKey, Modulus) = ", luc(cipher, private1, modulus), "
X
X"
Xprint "PrivateKey calculated without CipherText = ", private_from_primes(public, prime1, prime2), "
X"
Xprint "LUC(CipherText, PrivateKey, Modulus) = ", luc(cipher, private2, modulus), "
X"
Xprint "
X
XMessage Signing
X
X"
Xprint "PrivateKey calculated with PlainText = ", private_from_message(plain, public, prime1, prime2), "
X"
Xprint "LUC(PlainText, PrivateKey, Modulus) = ", luc(plain, private1, modulus), "
X
X"
Xprint "PrivateKey calculated without PlainText = ", private_from_primes(public, prime1, prime2), "
X"
Xprint "LUC(PlainText, PrivateKey, Modulus) = ", luc(plain, private2, modulus), "
X
X"
X
Xprint "LUC(SignedText, PublicKey, Modulus) = ", luc(signed, public, modulus), "
X
X"
X
X
Xhalt
HI_MOM
chmod +x 'luc_demo.gbc'
fi # end of overwriting check
#End of shell archive
exit 0