Dec 142017
 
Pseudocode for LUC public key data encryption.
File LUC.ZIP from The Programmer’s Corner in
Category Tutorials + Patches
Pseudocode for LUC public key data encryption.
File Name File Size Zip Size Zip Type
LUC.TXT 12416 3260 deflated

Download File LUC.ZIP Here

Contents of the LUC.TXT file


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






 December 14, 2017  Add comments

Leave a Reply