Modular exponentiation routine for PIC18F & SDCC
Wojciech Zabolotny
Submitted-by: wz...@ise.pw.edu.pl (Wojciech M. Zabolotny)
This is a source code of the modular exponentiation routine
written for the PIC18F processors (from Microchip).
The code is written for the GPL'ed SDCC compiler, however
most parts are implemented in the inline assembly.
The code of mxp_lib.c is PUBLIC DOMAIN.
(However the makefile has been obtained from the GPL'ed
PIC USB framework, so it is still under the GPL.)
To check the code, unpack it, run the gen_key.py script, then
do "make", and run the generated code under the gpsim:
$ gpsim -s boot.cod
Set the breakpoint in the loop at the end of the main function.
Then you can compare result of the calculation with the result
produced by Python and stored in the comment in the header file.
#!/bin/sh
# This is a shell archive (produced by GNU sharutils 4.6.3).
# To extract the files from this archive, save it to some FILE, remove
# everything before the `#!/bin/sh' line above, then type `sh FILE'.
#
lock_dir=_sh01493
# Made on 2008-04-27 02:23 CEST by <wzab@wzab>.
# Source directory was `/tmp/rsa'.
#
# Existing files will *not* be overwritten, unless `-c' is specified.
#
# This shar contains:
# length mode name
# ------ ---------- ------------------------------------------
# 10090 -rw-r--r-- mxp_lib.c
# 3189 -rwxr--r-- key_gen.py
# 1599 -rw-r--r-- Makefile
# 10090 -rw-r--r-- mxp_lib.c
# 2060 -rw-r--r-- mxp_test.c
#
MD5SUM=${MD5SUM-md5sum}
f=`${MD5SUM} --version | egrep '^md5sum .*(core|text)utils'`
test -n "${f}" && md5check=true || md5check=false
${md5check} || \
echo 'Note: not verifying md5sums. Consider installing GNU coreutils.'
save_IFS="${IFS}"
IFS="${IFS}:"
gettext_dir=FAILED
locale_dir=FAILED
first_param="$1"
for dir in $PATH
do
if test "$gettext_dir" = FAILED && test -f $dir/gettext \
&& ($dir/gettext --version >/dev/null 2>&1)
then
case `$dir/gettext --version 2>&1 | sed 1q` in
*GNU*) gettext_dir=$dir ;;
esac
fi
if test "$locale_dir" = FAILED && test -f $dir/shar \
&& ($dir/shar --print-text-domain-dir >/dev/null 2>&1)
then
locale_dir=`$dir/shar --print-text-domain-dir`
fi
done
IFS="$save_IFS"
if test "$locale_dir" = FAILED || test "$gettext_dir" = FAILED
then
echo=echo
else
TEXTDOMAINDIR=$locale_dir
export TEXTDOMAINDIR
TEXTDOMAIN=sharutils
export TEXTDOMAIN
echo="$gettext_dir/gettext -s"
fi
if (echo "testing\c"; echo 1,2,3) | grep c >/dev/null
then if (echo -n test; echo 1,2,3) | grep n >/dev/null
then shar_n= shar_c='
'
else shar_n=-n shar_c= ; fi
else shar_n= shar_c='\c' ; fi
f=shar-touch.$$
st1=200112312359.59
st2=123123592001.59
st2tr=123123592001.5 # old SysV 14-char limit
st3=1231235901
if touch -am -t ${st1} ${f} >/dev/null 2>&1 && \
test ! -f ${st1} && test -f ${f}; then
shar_touch='touch -am -t $1$2$3$4$5$6.$7 "$8"'
elif touch -am ${st2} ${f} >/dev/null 2>&1 && \
test ! -f ${st2} && test ! -f ${st2tr} && test -f ${f}; then
shar_touch='touch -am $3$4$5$6$1$2.$7 "$8"'
elif touch -am ${st3} ${f} >/dev/null 2>&1 && \
test ! -f ${st3} && test -f ${f}; then
shar_touch='touch -am $3$4$5$6$2 "$8"'
else
shar_touch=:
echo
${echo} 'WARNING: not restoring timestamps. Consider getting and'
${echo} 'installing GNU `touch'\'', distributed in GNU coreutils...'
echo
fi
rm -f ${st1} ${st2} ${st2tr} ${st3} ${f}
#
if test ! -d ${lock_dir}
then : ; else ${echo} 'lock directory '${lock_dir}' exists'
exit 1
fi
if mkdir ${lock_dir}
then ${echo} 'x - created lock directory `'${lock_dir}\''.'
else ${echo} 'x - failed to create lock directory `'${lock_dir}\''.'
exit 1
fi
# ============= mxp_lib.c ==============
if test -f 'mxp_lib.c' && test "$first_param" != -c; then
${echo} 'x -SKIPPING mxp_lib.c (file already exists)'
else
${echo} 'x - extracting mxp_lib.c (text)'
sed 's/^X//' << 'SHAR_EOF' > 'mxp_lib.c' &&
/* This is the implementation of the modular exponentiation
X for the PIC18F4550 microcontrollers.
X I have used it successfully for implementation of the RSA algorithm.
X The code has been tested in simulation in gpsim, and tested
X in hardware on PIC18F4550 board, described on:
X http://www.ise.pw.edu.pl/~wzab/opiclab
X
X The mxp_lib.c is a public domain code, written by Wojciech M. Zabolotny
X wzab(at)ise.pw.edu.pl
X If you improve this code, please share your modifications
*/
X
/* SDCC inline assembler does not offer a convenient method to access
X the function variables from the inline assembly code.
X Therefore I had to use a dirty trick - use the global
X variables to transfer infromation to my inline assembly code */
X
//Variables used by the library
X unsigned char mxp_uc1,mxp_uc2,mxp_uc3;
X data unsigned char * mxp_din;
X data unsigned char * mxp_res;
X code unsigned char * mxp_mod;
X unsigned char mxp_mult;
X unsigned char mxp_nbytes;
X unsigned short mxp_nbits;
X
/* the buf_mac_8bit procedure multiplies the contents of the input buffer
X by the single byte, and adds the result to the result buffer
X mxp_nbytes - length of the multiplied input buffer in bytes
X mxp_din - points on the buffer, located in the data RAM
X mxp_mult - the value of the byte, by which we multiply the buffer
X mxp_res - points to the result buffer (must be mxp_nbytes+1 long!)
*/
//Warning!!! This function adds the result to the destination buffer!!!
void mxp_mac_8bit()
{
X _asm
X movff _FSR2L, _POSTDEC1
X movff _FSR2H, _POSTDEC1
X movff r0x00, _POSTDEC1
X movff r0x01, _POSTDEC1
X movff r0x02, _POSTDEC1
X //Set the pointers
X movff _mxp_din,_FSR0L
X movff _mxp_din+1,_FSR0H
X movff _mxp_res,_FSR2L
X movff _mxp_res+1,_FSR2H
X //clear the temporary buffer, located in r0x02-r0x04 registers
X clrf r0x02,0
X movff _mxp_nbytes,r0x00
X movff _mxp_mult,r0x01
X loop1mul:
X //Multiply the byte
X movf _POSTINC0,W,0
X mulwf r0x01,0
X //Add the result to the carry registers
X MOVF _PRODL, W,0
X addwf _POSTINC2,F,0
X MOVF _PRODH, W,0
X addwfc r0x02, W,0 //r0x02 is the carry register from the previous loop
X clrf r0x02,0
X rlcf r0x02,F,0 // new carry 0 or 1
X addwf _INDF2, F,0
X CLRF _WREG,0
X addwfc r0x02, F,0 //update carry
X //Check if the loop is finished
X decfsz r0x00, F,0
X goto loop1mul
X //The r0x02 from the last iteration is always ZERO
X //we can discard it!
X //restore the saved registers
X movff _PREINC1,r0x02
X movff _PREINC1,r0x01
X movff _PREINC1,r0x00
X movff _PREINC1,_FSR2H
X movff _PREINC1,_FSR2L
X _endasm;
}
X
/* The routine mxp_mod_buf checks if the buffer is greater than
X the modulus stored in the CODE MEMORY(!) and in this case
X subtracts the modules from the buffer.
X If the subtraction was needed, the function returns non-zero.
X If the buffer contents was smaller, than the modulus,
X the function returns zero
*/
X
unsigned char mxp_mod_buf()
{
X _asm
X movff _FSR2L, _POSTDEC1
X movff _FSR2H, _POSTDEC1
X movff r0x00, _POSTDEC1
X // Load the code pointer, pointing to the highest byte of modulus
X banksel _mxp_nbytes
X decf _mxp_nbytes,W
X banksel _mxp_mod
X addwf _mxp_mod, W
X movwf _TBLPTRL, 0
X clrf _WREG, 0
X banksel _mxp_mod
X addwfc _mxp_mod+1,W
X movwf _TBLPTRH, 0
X clrf _WREG, 0
X banksel _mxp_mod
X addwfc _mxp_mod+2,W
X movwf _TBLPTRU, 0
X // load the data pointer pointing to the highest byte of the data buffer
X banksel _mxp_nbytes
X decf _mxp_nbytes,W
X banksel _mxp_res
X addwf _mxp_res,W
X movwf _FSR0L, 0
X clrf _WREG, 0
X banksel _mxp_res
X addwfc _mxp_res+1,W
X movwf _FSR0H, 0
X // start the processing
X movff _mxp_nbytes, r0x00
X mxp_loop1:
X tblrd*-
X movf _TABLAT, W, 0
X subwf _POSTDEC0, W, 0
X // subtract res[x]-mod[x]
X // if the byte in "res" is smaller, than byte in "mod" - we do not need to subtract
X bnc mxp_dont_subtract
X // if the bytes are equal - check the next byte
X bz mxp_loop1_cont
X // if the byte in "res" is greater, than byte in "mod" - we need to subtract
X goto subtract
X mxp_loop1_cont:
X decfsz r0x00, 0
X goto mxp_loop1
X // if we get there, than all bytes are equal - we subtract anyway (getting zero ;-) )
X subtract:
X //Set the pointers, now to the lowest bytes
X movff _mxp_mod, _TBLPTRL
X movff _mxp_mod+1, _TBLPTRH
X movff _mxp_mod+2, _TBLPTRU
X movff _mxp_res, _FSR0L
X movff _mxp_res+1, _FSR0H
X movff _mxp_nbytes, r0x00
X //Set the carry, so the subtraction works correctly
X bsf _STATUS,0,0
X mxp_loop2:
X tblrd*+
X movf _TABLAT, W,0
X subwfb _POSTINC0,1,0
X decfsz r0x00,F,0
X goto mxp_loop2
X banksel _mxp_mult
X setf _mxp_mult
X goto mxp_cleanup1
X mxp_dont_subtract:
X banksel _mxp_mult
X clrf _mxp_mult
X goto mxp_cleanup1
X mxp_cleanup1:
X movff _PREINC1,r0x00
X movff _PREINC1,_FSR2H
X movff _PREINC1,_FSR2L
X _endasm;
X return mxp_mult;
}
X
/* After the mxp_mac_8bit function, the result buffer may be even 254 or so times
X bigger than the modulus. Therefore to assure, that the final result is not bigger
X than the modulus, we call the mxp_mod_buf function 8 times, with different moduli:
X mod<<7, mod<<6 ... mod. For the additional protection we check if the subtraction
X of mod<<7 was performed, and in this case we call mxp_mod_buf with mod << 7 once again.
X The shifted moduli must be precalculated and stored in the CODE MEMORY(!)
*/
void mxp_mod_buf_8bit(data unsigned char * din, unsigned char nbytes)
{
X //First we subtract the modulus<<7
X do {
X mxp_mod = mxp_mod_shft_7;
X mxp_res = din;
X mxp_nbytes = nbytes;
X } while (mxp_mod_buf());
X //Then we deal with the next moduli
X mxp_mod = mxp_mod_shft_6;
X mxp_mod_buf();
X mxp_mod = mxp_mod_shft_5;
X mxp_mod_buf();
X mxp_mod = mxp_mod_shft_4;
X mxp_mod_buf();
X mxp_mod = mxp_mod_shft_3;
X mxp_mod_buf();
X mxp_mod = mxp_mod_shft_2;
X mxp_mod_buf();
X mxp_mod = mxp_mod_shft_1;
X mxp_mod_buf();
X mxp_mod = mxp_mod_shft_0;
X mxp_mod_buf();
}
X
/* The modular multiplication routine
X We multiply the buffer pointed by din1 (moved to mxp_din) - length nbytes
X by the buffer pointed by din2 - length nbytes
X The result is stored in the buffer pointed by res (moved to mxp_res) - length nbytes+1
X The buffer pointed by din1 IS DESTROYED BY THE FUNCTION!!!
X The algorithm is as follows:
X We take the least significant byte of the buffer din2, and multiply&accumulate it
X by the din1 buffer. Then we multiply the din1 buffer by 256, correct it modulo
X the modulus stored in the CODE MEMORY (mxp_mod_shft_7 .. mxp_mod_shft_0),
X and proceed with the next byte of din2
*/
X
unsigned char mxp_mul_mod(data unsigned char * din1, data unsigned char * din2,
X data unsigned char * res, unsigned char nbytes)
{
X unsigned char i;
X //First we need to zero the result buffer
X memset(res,0,nbytes+1);
X //Then we take the subsequent bytes of the din2
X for(i=0;i<nbytes;i++) {
X mxp_din = din1;
X mxp_res = res;
X mxp_mult = din2[i];
X mxp_nbytes = nbytes;
X mxp_mac_8bit();
X //Now we need to correct the result (modulo mxp_mod_...)
X mxp_mod_buf_8bit(res,nbytes+1);
X if (i==nbytes-1) break;
X //Now we multiply the din1 by 256 - simple shifting of bytes
X mxp_res = din1+nbytes;
X mxp_din = din1+nbytes-1;
X mxp_nbytes = nbytes;
X _asm
X movff _FSR2L, _POSTDEC1
X movff _FSR2H, _POSTDEC1
X movff _FSR0L, _POSTDEC1
X movff _FSR0H, _POSTDEC1
X movff r0x00, _POSTDEC1
X movff _mxp_din,_FSR2L
X movff _mxp_din+1,_FSR2H
X movff _mxp_res,_FSR0L
X movff _mxp_res+1,FSR0H
X movff _mxp_nbytes,r0x00
X mxp_loop5:
X movff _POSTDEC2,_POSTDEC0
X decfsz r0x00,F,0
X goto mxp_loop5
X movff _PREINC1,r0x00
X movff _PREINC1,_FSR0H
X movff _PREINC1,_FSR0L
X movff _PREINC1,_FSR2H
X movff _PREINC1,_FSR2L
X _endasm;
X //Check if we have already finished
X din1[0]=0;
X //Now we correct the din1 (modulo mod)
X mxp_mod_buf_8bit(din1,nbytes+1);
X }
X return 0;
}
X
X
/* The next function checks, if the particular byte in the multibyte integer
X stored in the CODE MEMORY is set */
unsigned char mxp_code_check_bit(code unsigned char * buf, unsigned short bitnr)
{
X unsigned char mask;
X mask = 1 << ((unsigned char)bitnr & 0x7);
X return mask & *(buf+(bitnr >> 3));
}
X
/* The next function checks, if the particular byte in the multibyte integer
X stored in the DATA MEMORY is set */
unsigned char mxp_data_check_bit(data unsigned char * buf, unsigned short bitnr)
{
X unsigned char mask;
X mask = 1 << ((unsigned char)bitnr & 0x7);
X return mask & *(buf+(bitnr >> 3));
}
X
/* And finally the modular exponentiation function
X the base is placed in the buffer pointed by mxp_tmp_pow (in the DATA MEMORY)
X the exponent is placed in the buffer pointed by mxp_d (in the CODE MEMORY)
X the modulus is stored as mxp_mod_shft_7 ... mxp_mod_shft_0 (in the CODE MEMORY)
X the result is placed in the buffer pointed by the mxp_tmp_res (in the DATA MEMORY)
*/
unsigned char mxp_mod_exp()
{
X unsigned short bitnr;
X //First we set the result to 1
X mxp_tmp_res[0] = 1;
X memset(mxp_tmp_res+1,0,key_len_bytes);
X for(bitnr = 0;bitnr<key_len_bits;bitnr++) {
X //if the bit in the exponent is set, we multiply the result by the temporary
X //power of din
X if (mxp_code_check_bit(mxp_d,bitnr)) {
X //First we need to copy the data to the working buffers
X memcpy(buf1,mxp_tmp_res,key_len_bytes+1);
X memcpy(buf2,mxp_tmp_pow,key_len_bytes+1);
X mxp_mul_mod(buf1,buf2,mxp_tmp_res,key_len_bytes);
X }
X if (bitnr == key_len_bits-1) break;
X //Now we update the temporary power of din
X memcpy(buf1,mxp_tmp_pow,key_len_bytes+1);
X memcpy(buf2,mxp_tmp_pow,key_len_bytes+1);
X mxp_mul_mod(buf1,buf2,mxp_tmp_pow,key_len_bytes);
X }
X return 1;
}
/*
X This library still lacks the modular subtraction routine, which
X is needed for CRT based optimized implementation of the RSA algortihm
X I'm going to added in the next release...
*/
SHAR_EOF
(set 20 08 04 27 02 22 41 'mxp_lib.c'; eval "$shar_touch") &&
chmod 0644 'mxp_lib.c'
if test $? -ne 0
then ${echo} 'restore of mxp_lib.c failed'
fi
if ${md5check}
then (
${MD5SUM} -c >/dev/null 2>&1 || ${echo} 'mxp_lib.c: MD5 check failed'
) << SHAR_EOF
3d7367ea7ed3b290487a47b929df9f46 mxp_lib.c
SHAR_EOF
else
test `LC_ALL=C wc -c < 'mxp_lib.c'` -ne 10090 && \
${echo} 'restoration warning: size of mxp_lib.c is not 10090'
fi
fi
# ============= key_gen.py ==============
if test -f 'key_gen.py' && test "$first_param" != -c; then
${echo} 'x -SKIPPING key_gen.py (file already exists)'
else
${echo} 'x - extracting key_gen.py (text)'
sed 's/^X//' << 'SHAR_EOF' > 'key_gen.py' &&
#!/usr/bin/python
# Public domain code written by Wojciech M. Zabolotny
# wzab(at)ise.pw.edu.pl
# Generates the header file for the modular exponentiation library
# mxp_lib.c
import cPickle
import Crypto
import Crypto.PublicKey.RSA as rsa
key_len=512
key_len_bytes=int((key_len+7)/8)
f=open("/dev/urandom","rb") #replace urandom with random for really random bytes
#The function below produces the random bytes for key generation
def rndb4(s):
X return f.read(s)
def write_const(val,len_bytes):
X l="["+str(len_bytes)+"]={"
X for i in xrange(0,len_bytes):
X l+=hex(val & 0xffL)+","
X val >>= 8;
X l=l[:-1]+"}"
X return l
X
#The function below generates the multibyte random integer
def rand_multibyte_int(n):
X res=0;
X for i in xrange(0,n):
X b=ord(f.read(1))
X res<<=8
X res+=b
X return res
X
#Modular exponentiation implemented in Python
def exp_mod2(c,d,n):
X w_exp=1L
X t_exp=c % n
X while d != 0:
X if d & 1L:
X t_mnoz = w_exp % n
X w_mnoz = t_exp
X w_exp = 0L
X while w_mnoz != 0:
X if w_mnoz & 1L:
X w_exp = (w_exp+t_mnoz) % n
X t_mnoz = (t_mnoz+t_mnoz) % n
X w_mnoz = w_mnoz >> 1
X t_mnoz = t_exp % n
X w_mnoz = t_mnoz
X t_exp = 0L
X while w_mnoz != 0:
X if w_mnoz & 1L:
X t_exp = (t_exp+t_mnoz) % n
X t_mnoz = (t_mnoz+t_mnoz) % n
X w_mnoz = w_mnoz >> 1
X d = d >> 1
X return w_exp
X
#Generate the key
k=rsa.generate(key_len,rndb4)
print k.n
print k.p
print k.q
X
#Now generate the header file for the mxp_lib.c
fh=open("mxp_key.h","wt")
l="#define key_len_bytes ("+hex(key_len_bytes)+")\n"
fh.write(l)
l="#define key_len_bits ("+hex(key_len)+")\n"
fh.write(l)
l="code unsigned char mxp_d"
l+=write_const(k.d,key_len_bytes)
l+=";\n"
fh.write(l)
#Modulus shifted by different amount of bits
for i in range(0,8):
X l="code unsigned char mxp_mod_shft_"+str(i)
X l+=write_const(k.n<<i,key_len_bytes+1)
X l+=";\n"
X fh.write(l)
X
c0=rand_multibyte_int(key_len_bytes) % k.n
print "c0="+hex(c0)
c1=exp_mod2(c0,k.e,k.n)
l="code unsigned char c1"
l+=write_const(c1,key_len_bytes+1)
l+=";\n"
fh.write(l)
X
#Now we generate some random numbers for regression tests
t1=rand_multibyte_int(key_len_bytes)
l="code unsigned char t1"
l+=write_const(t1,key_len_bytes+1)
l+=";\n"
fh.write(l)
t2=rand_multibyte_int(key_len_bytes)
l="code unsigned char t2"
l+=write_const(t2,key_len_bytes+1)
l+=";\n"
fh.write(l)
l="// "+hex(c1)+" ^ "+hex(k.d)+" % "+hex(k.n)+" = "+hex(exp_mod2(c1,k.d,k.n))+"\n"
fh.write(l)
#l="// "+hex(t1)+" * "+hex(t2)+" % "+hex(k.n)+" = "+hex((t1*t2) % k.n)+"\n"
#fh.write(l)
#Now we declare the results buffers used by the library
l="data unsigned char buf1["+str(key_len_bytes+1)+"];\n"
fh.write(l)
l="data unsigned char buf2["+str(key_len_bytes+1)+"];\n"
fh.write(l)
l="data unsigned char mxp_tmp_res["+str(key_len_bytes+1)+"];\n"
fh.write(l)
l="data unsigned char mxp_tmp_pow["+str(key_len_bytes+1)+"];\n"
fh.write(l)
fh.close()
#Store the generated key for later use
fp=open("key.pck","wb")
p=cPickle.Pickler(fp)
p.dump(k)
fp.close()
X
SHAR_EOF
(set 20 08 04 27 02 21 16 'key_gen.py'; eval "$shar_touch") &&
chmod 0744 'key_gen.py'
if test $? -ne 0
then ${echo} 'restore of key_gen.py failed'
fi
if ${md5check}
then (
${MD5SUM} -c >/dev/null 2>&1 || ${echo} 'key_gen.py: MD5 check failed'
) << SHAR_EOF
50dd71b61dd3b9f31a62ccc0c9c95d5f key_gen.py
SHAR_EOF
else
test `LC_ALL=C wc -c < 'key_gen.py'` -ne 3189 && \
${echo} 'restoration warning: size of key_gen.py is not 3189'
fi
fi
# ============= Makefile ==============
if test -f 'Makefile' && test "$first_param" != -c; then
${echo} 'x -SKIPPING Makefile (file already exists)'
else
${echo} 'x - extracting Makefile (text)'
sed 's/^X//' << 'SHAR_EOF' > 'Makefile' &&
# The makefile has been adapted from the GPL'ed makefile
# published as a part of the PUF framework http://vasco.gforge.enseeiht.fr/
# $Id: Makefile,v 1.2 2006/03/05 19:39:31 gaufille Exp $
X
PIC_TYPE=PIC18F452
sdcc_PIC_TYPE=18f452
#TOOLSDIR=$(shell dirname `pwd`)/tools
#TOOLSDIR=/usr/local/sdcc
TOOLSDIR=/usr
CC=$(TOOLSDIR)/bin/sdcc
#ASM=$(TOOLSDIR)/bin/gpasm
#GLNK=$(TOOLSDIR)/bin/gplink
ASM=/usr/bin/gpasm
GLNK=/usr/bin/gplink
LNK=$(TOOLSDIR)/bin/sdcc
ODYSSEY=$(TOOLSDIR)/bin/odyssey
CRT0=$(TOOLSDIR)/share/sdcc/lib/pic16/crt0.o
LIBIO=$(TOOLSDIR)/share/sdcc/lib/pic16/libio18f452.lib
LIBC18F=$(TOOLSDIR)/share/sdcc/lib/pic16/libc18f.lib
#DEBUG=-D_DEBUG
DEBUG=
#DEBUG=--optimize-df --opt-code-size --optimize-cmp --obanksel=2
#DEBUG=--ivt-loc=0x2000 --fstack --opt-code-size --obanksel=2 --optimize-df --optimize-cmp
all: boot.hex
X
X
# Link with sdcc causes an error when accessing UCFG and UCON : access bit is set
# but it should not. Using the CVS version 20050112 of gplink to link the code
# solves this issue
boot.hex: mxp_test.o
X $(GLNK) -w -s /usr/share/gputils/lkr/18f452.lkr -m $+ $(TOOLSDIR)/share/sdcc/lib/pic16/pic$(sdcc_PIC_TYPE).lib \
X $(TOOLSDIR)/share/sdcc/lib/pic16/libsdcc.lib $(CRT0) $(LIBIO) $(LIBC18F) -o $@
X
%.o: %.c
X $(CC) -mpic16 $(DEBUG) -p$(sdcc_PIC_TYPE) --obanksel=2 --optimize-df -Iinclude -c $< -o $@
X
clean:
X rm -f *.o *.rel *.lst *.cod *.hex *.map *.asm
X
prog: all
X (echo "Blanking...";\
X $(ODYSSEY) $(PIC_TYPE) erase) && \
X (echo "Writing...";\
X $(ODYSSEY) $(PIC_TYPE) write boot.hex)
X
X.PHONY: all clean prog erase
X
mxp_test.o: Makefile mxp_key.h mxp_lib.c
SHAR_EOF
(set 20 08 04 27 02 05 07 'Makefile'; eval "$shar_touch") &&
chmod 0644 'Makefile'
if test $? -ne 0
then ${echo} 'restore of Makefile failed'
fi
if ${md5check}
then (
${MD5SUM} -c >/dev/null 2>&1 || ${echo} 'Makefile: MD5 check failed'
) << SHAR_EOF
855e6ff2740a759049b5725f9cb46f81 Makefile
SHAR_EOF
else
test `LC_ALL=C wc -c < 'Makefile'` -ne 1599 && \
${echo} 'restoration warning: size of Makefile is not 1599'
fi
fi
# ============= mxp_lib.c ==============
if test -f 'mxp_lib.c' && test "$first_param" != -c; then
${echo} 'x -SKIPPING mxp_lib.c (file already exists)'
else
${echo} 'x - extracting mxp_lib.c (text)'
sed 's/^X//' << 'SHAR_EOF' > 'mxp_lib.c' &&
/* This is the implementation of the modular exponentiation
X for the PIC18F4550 microcontrollers.
X I have used it successfully for implementation of the RSA algorithm.
X The code has been tested in simulation in gpsim, and tested
X in hardware on PIC18F4550 board, described on:
X http://www.ise.pw.edu.pl/~wzab/opiclab
X
X The mxp_lib.c is a public domain code, written by Wojciech M. Zabolotny
X wzab(at)ise.pw.edu.pl
X If you improve this code, please share your modifications
*/
X
/* SDCC inline assembler does not offer a convenient method to access
X the function variables from the inline assembly code.
X Therefore I had to use a dirty trick - use the global
X variables to transfer infromation to my inline assembly code */
X
//Variables used by the library
X unsigned char mxp_uc1,mxp_uc2,mxp_uc3;
X data unsigned char * mxp_din;
X data unsigned char * mxp_res;
X code unsigned char * mxp_mod;
X unsigned char mxp_mult;
X unsigned char mxp_nbytes;
X unsigned short mxp_nbits;
X
/* the buf_mac_8bit procedure multiplies the contents of the input buffer
X by the single byte, and adds the result to the result buffer
X mxp_nbytes - length of the multiplied input buffer in bytes
X mxp_din - points on the buffer, located in the data RAM
X mxp_mult - the value of the byte, by which we multiply the buffer
X mxp_res - points to the result buffer (must be mxp_nbytes+1 long!)
*/
//Warning!!! This function adds the result to the destination buffer!!!
void mxp_mac_8bit()
{
X _asm
X movff _FSR2L, _POSTDEC1
X movff _FSR2H, _POSTDEC1
X movff r0x00, _POSTDEC1
X movff r0x01, _POSTDEC1
X movff r0x02, _POSTDEC1
X //Set the pointers
X movff _mxp_din,_FSR0L
X movff _mxp_din+1,_FSR0H
X movff _mxp_res,_FSR2L
X movff _mxp_res+1,_FSR2H
X //clear the temporary buffer, located in r0x02-r0x04 registers
X clrf r0x02,0
X movff _mxp_nbytes,r0x00
X movff _mxp_mult,r0x01
X loop1mul:
X //Multiply the byte
X movf _POSTINC0,W,0
X mulwf r0x01,0
X //Add the result to the carry registers
X MOVF _PRODL, W,0
X addwf _POSTINC2,F,0
X MOVF _PRODH, W,0
X addwfc r0x02, W,0 //r0x02 is the carry register from the previous loop
X clrf r0x02,0
X rlcf r0x02,F,0 // new carry 0 or 1
X addwf _INDF2, F,0
X CLRF _WREG,0
X addwfc r0x02, F,0 //update carry
X //Check if the loop is finished
X decfsz r0x00, F,0
X goto loop1mul
X //The r0x02 from the last iteration is always ZERO
X //we can discard it!
X //restore the saved registers
X movff _PREINC1,r0x02
X movff _PREINC1,r0x01
X movff _PREINC1,r0x00
X movff _PREINC1,_FSR2H
X movff _PREINC1,_FSR2L
X _endasm;
}
X
/* The routine mxp_mod_buf checks if the buffer is greater than
X the modulus stored in the CODE MEMORY(!) and in this case
X subtracts the modules from the buffer.
X If the subtraction was needed, the function returns non-zero.
X If the buffer contents was smaller, than the modulus,
X the function returns zero
*/
X
unsigned char mxp_mod_buf()
{
X _asm
X movff _FSR2L, _POSTDEC1
X movff _FSR2H, _POSTDEC1
X movff r0x00, _POSTDEC1
X // Load the code pointer, pointing to the highest byte of modulus
X banksel _mxp_nbytes
X decf _mxp_nbytes,W
X banksel _mxp_mod
X addwf _mxp_mod, W
X movwf _TBLPTRL, 0
X clrf _WREG, 0
X banksel _mxp_mod
X addwfc _mxp_mod+1,W
X movwf _TBLPTRH, 0
X clrf _WREG, 0
X banksel _mxp_mod
X addwfc _mxp_mod+2,W
X movwf _TBLPTRU, 0
X // load the data pointer pointing to the highest byte of the data buffer
X banksel _mxp_nbytes
X decf _mxp_nbytes,W
X banksel _mxp_res
X addwf _mxp_res,W
X movwf _FSR0L, 0
X clrf _WREG, 0
X banksel _mxp_res
X addwfc _mxp_res+1,W
X movwf _FSR0H, 0
X // start the processing
X movff _mxp_nbytes, r0x00
X mxp_loop1:
X tblrd*-
X movf _TABLAT, W, 0
X subwf _POSTDEC0, W, 0
X // subtract res[x]-mod[x]
X // if the byte in "res" is smaller, than byte in "mod" - we do not need to subtract
X bnc mxp_dont_subtract
X // if the bytes are equal - check the next byte
X bz mxp_loop1_cont
X // if the byte in "res" is greater, than byte in "mod" - we need to subtract
X goto subtract
X mxp_loop1_cont:
X decfsz r0x00, 0
X goto mxp_loop1
X // if we get there, than all bytes are equal - we subtract anyway (getting zero ;-) )
X subtract:
X //Set the pointers, now to the lowest bytes
X movff _mxp_mod, _TBLPTRL
X movff _mxp_mod+1, _TBLPTRH
X movff _mxp_mod+2, _TBLPTRU
X movff _mxp_res, _FSR0L
X movff _mxp_res+1, _FSR0H
X movff _mxp_nbytes, r0x00
X //Set the carry, so the subtraction works correctly
X bsf _STATUS,0,0
X mxp_loop2:
X tblrd*+
X movf _TABLAT, W,0
X subwfb _POSTINC0,1,0
X decfsz r0x00,F,0
X goto mxp_loop2
X banksel _mxp_mult
X setf _mxp_mult
X goto mxp_cleanup1
X mxp_dont_subtract:
X banksel _mxp_mult
X clrf _mxp_mult
X goto mxp_cleanup1
X mxp_cleanup1:
X movff _PREINC1,r0x00
X movff _PREINC1,_FSR2H
X movff _PREINC1,_FSR2L
X _endasm;
X return mxp_mult;
}
X
/* After the mxp_mac_8bit function, the result buffer may be even 254 or so times
X bigger than the modulus. Therefore to assure, that the final result is not bigger
X than the modulus, we call the mxp_mod_buf function 8 times, with different moduli:
X mod<<7, mod<<6 ... mod. For the additional protection we check if the subtraction
X of mod<<7 was performed, and in this case we call mxp_mod_buf with mod << 7 once again.
X The shifted moduli must be precalculated and stored in the CODE MEMORY(!)
*/
void mxp_mod_buf_8bit(data unsigned char * din, unsigned char nbytes)
{
X //First we subtract the modulus<<7
X do {
X mxp_mod = mxp_mod_shft_7;
X mxp_res = din;
X mxp_nbytes = nbytes;
X } while (mxp_mod_buf());
X //Then we deal with the next moduli
X mxp_mod = mxp_mod_shft_6;
X mxp_mod_buf();
X mxp_mod = mxp_mod_shft_5;
X mxp_mod_buf();
X mxp_mod = mxp_mod_shft_4;
X mxp_mod_buf();
X mxp_mod = mxp_mod_shft_3;
X mxp_mod_buf();
X mxp_mod = mxp_mod_shft_2;
X mxp_mod_buf();
X mxp_mod = mxp_mod_shft_1;
X mxp_mod_buf();
X mxp_mod = mxp_mod_shft_0;
X mxp_mod_buf();
}
X
/* The modular multiplication routine
X We multiply the buffer pointed by din1 (moved to mxp_din) - length nbytes
X by the buffer pointed by din2 - length nbytes
X The result is stored in the buffer pointed by res (moved to mxp_res) - length nbytes+1
X The buffer pointed by din1 IS DESTROYED BY THE FUNCTION!!!
X The algorithm is as follows:
X We take the least significant byte of the buffer din2, and multiply&accumulate it
X by the din1 buffer. Then we multiply the din1 buffer by 256, correct it modulo
X the modulus stored in the CODE MEMORY (mxp_mod_shft_7 .. mxp_mod_shft_0),
X and proceed with the next byte of din2
*/
X
unsigned char mxp_mul_mod(data unsigned char * din1, data unsigned char * din2,
X data unsigned char * res, unsigned char nbytes)
{
X unsigned char i;
X //First we need to zero the result buffer
X memset(res,0,nbytes+1);
X //Then we take the subsequent bytes of the din2
X for(i=0;i<nbytes;i++) {
X mxp_din = din1;
X mxp_res = res;
X mxp_mult = din2[i];
X mxp_nbytes = nbytes;
X mxp_mac_8bit();
X //Now we need to correct the result (modulo mxp_mod_...)
X mxp_mod_buf_8bit(res,nbytes+1);
X if (i==nbytes-1) break;
X //Now we multiply the din1 by 256 - simple shifting of bytes
X mxp_res = din1+nbytes;
X mxp_din = din1+nbytes-1;
X mxp_nbytes = nbytes;
X _asm
X movff _FSR2L, _POSTDEC1
X movff _FSR2H, _POSTDEC1
X movff _FSR0L, _POSTDEC1
X movff _FSR0H, _POSTDEC1
X movff r0x00, _POSTDEC1
X movff _mxp_din,_FSR2L
X movff _mxp_din+1,_FSR2H
X movff _mxp_res,_FSR0L
X movff _mxp_res+1,FSR0H
X movff _mxp_nbytes,r0x00
X mxp_loop5:
X movff _POSTDEC2,_POSTDEC0
X decfsz r0x00,F,0
X goto mxp_loop5
X movff _PREINC1,r0x00
X movff _PREINC1,_FSR0H
X movff _PREINC1,_FSR0L
X movff _PREINC1,_FSR2H
X movff _PREINC1,_FSR2L
X _endasm;
X //Check if we have already finished
X din1[0]=0;
X //Now we correct the din1 (modulo mod)
X mxp_mod_buf_8bit(din1,nbytes+1);
X }
X return 0;
}
X
X
/* The next function checks, if the particular byte in the multibyte integer
X stored in the CODE MEMORY is set */
unsigned char mxp_code_check_bit(code unsigned char * buf, unsigned short bitnr)
{
X unsigned char mask;
X mask = 1 << ((unsigned char)bitnr & 0x7);
X return mask & *(buf+(bitnr >> 3));
}
X
/* The next function checks, if the particular byte in the multibyte integer
X stored in the DATA MEMORY is set */
unsigned char mxp_data_check_bit(data unsigned char * buf, unsigned short bitnr)
{
X unsigned char mask;
X mask = 1 << ((unsigned char)bitnr & 0x7);
X return mask & *(buf+(bitnr >> 3));
}
X
/* And finally the modular exponentiation function
X the base is placed in the buffer pointed by mxp_tmp_pow (in the DATA MEMORY)
X the exponent is placed in the buffer pointed by mxp_d (in the CODE MEMORY)
X the modulus is stored as mxp_mod_shft_7 ... mxp_mod_shft_0 (in the CODE MEMORY)
X the result is placed in the buffer pointed by the mxp_tmp_res (in the DATA MEMORY)
*/
unsigned char mxp_mod_exp()
{
X unsigned short bitnr;
X //First we set the result to 1
X mxp_tmp_res[0] = 1;
X memset(mxp_tmp_res+1,0,key_len_bytes);
X for(bitnr = 0;bitnr<key_len_bits;bitnr++) {
X //if the bit in the exponent is set, we multiply the result by the temporary
X //power of din
X if (mxp_code_check_bit(mxp_d,bitnr)) {
X //First we need to copy the data to the working buffers
X memcpy(buf1,mxp_tmp_res,key_len_bytes+1);
X memcpy(buf2,mxp_tmp_pow,key_len_bytes+1);
X mxp_mul_mod(buf1,buf2,mxp_tmp_res,key_len_bytes);
X }
X if (bitnr == key_len_bits-1) break;
X //Now we update the temporary power of din
X memcpy(buf1,mxp_tmp_pow,key_len_bytes+1);
X memcpy(buf2,mxp_tmp_pow,key_len_bytes+1);
X mxp_mul_mod(buf1,buf2,mxp_tmp_pow,key_len_bytes);
X }
X return 1;
}
/*
X This library still lacks the modular subtraction routine, which
X is needed for CRT based optimized implementation of the RSA algortihm
X I'm going to added in the next release...
*/
SHAR_EOF
(set 20 08 04 27 02 22 41 'mxp_lib.c'; eval "$shar_touch") &&
chmod 0644 'mxp_lib.c'
if test $? -ne 0
then ${echo} 'restore of mxp_lib.c failed'
fi
if ${md5check}
then (
${MD5SUM} -c >/dev/null 2>&1 || ${echo} 'mxp_lib.c: MD5 check failed'
) << SHAR_EOF
3d7367ea7ed3b290487a47b929df9f46 mxp_lib.c
SHAR_EOF
else
test `LC_ALL=C wc -c < 'mxp_lib.c'` -ne 10090 && \
${echo} 'restoration warning: size of mxp_lib.c is not 10090'
fi
fi
# ============= mxp_test.c ==============
if test -f 'mxp_test.c' && test "$first_param" != -c; then
${echo} 'x -SKIPPING mxp_test.c (file already exists)'
else
${echo} 'x - extracting mxp_test.c (text)'
sed 's/^X//' << 'SHAR_EOF' > 'mxp_test.c' &&
/* This file is a simple wrapper fo the mxp_lib.c file
X It allows to test the mxp_lib.c in simulation with the gpsim
*/
X
/* Reserve 255 bytes of stack at 0x200 */
#pragma stack 0x200 255
X
#include <pic18fregs.h>
#include <string.h>
#include "mxp_key.h"
/* Set the PIC config words */
/* The settings are ONLY FOR SIMULATION!!! */
code char at __CONFIG1H _conf1 = _OSC_HS_1H;
code char at __CONFIG2L _conf2 = _BODENV_2_0V_2L &
X _BODEN_OFF_2L &
X _PUT_ON_2L;
X
code char at __CONFIG2H _conf3 = _WDT_OFF_2H ;
X
code char at __CONFIG3H _conf4 = _CCP2MUX_RB3_3H;
X
code char at __CONFIG4L _conf5 = _BACKBUG_OFF_4L &
X _LVP_OFF_4L &
X _STVR_OFF_4L;
X
code char at __CONFIG5L _conf6 = _CP_0_OFF_5L &
X _CP_1_OFF_5L &
X _CP_2_OFF_5L;// &
// 4550 specific _CP_3_OFF_5L;
X
code char at __CONFIG5H _conf7 = _CPB_OFF_5H &
X _CPD_OFF_5H;
X
code char at __CONFIG6L _conf8 = _WRT_0_ON_6L &
X _WRT_1_OFF_6L &
X _WRT_2_OFF_6L;// &
// 4550 specific _WRT_3_OFF_6L;
X
code char at __CONFIG6H _conf9 = _WRTB_ON_6H &
X _WRTC_ON_6H &
X _WRTD_OFF_6H;
X
code char at __CONFIG7L _conf10 = _EBTR_0_OFF_7L &
X _EBTR_1_OFF_7L &
X _EBTR_2_OFF_7L;// &
// 4550 specific 0 _EBTR_3_OFF_7L;
X
code char at __CONFIG7H _conf11 = _EBTRB_OFF_7H;
X
/******************************************************************/
X
#include "mxp_lib.c"
X
void main()
{
X memcpy(buf1,t1,key_len_bytes+1);
X memcpy(buf2,t2,key_len_bytes+1);
X memset(mxp_tmp_res,0,key_len_bytes+1);
X mxp_mul_mod(buf1,buf2,mxp_tmp_res,key_len_bytes);
X mxp_nbits=3;
X memcpy(mxp_tmp_pow,c1,key_len_bytes+1);
X mxp_mod_exp();
stop_tst:
X for(;;) {
X }
}
SHAR_EOF
(set 20 08 04 27 02 19 30 'mxp_test.c'; eval "$shar_touch") &&
chmod 0644 'mxp_test.c'
if test $? -ne 0
then ${echo} 'restore of mxp_test.c failed'
fi
if ${md5check}
then (
${MD5SUM} -c >/dev/null 2>&1 || ${echo} 'mxp_test.c: MD5 check failed'
) << SHAR_EOF
61c872d3065d8badea2110603cee0a36 mxp_test.c
SHAR_EOF
else
test `LC_ALL=C wc -c < 'mxp_test.c'` -ne 2060 && \
${echo} 'restoration warning: size of mxp_test.c is not 2060'
fi
fi
if rm -fr ${lock_dir}
then ${echo} 'x - removed lock directory `'${lock_dir}\''.'
else ${echo} 'x - failed to remove lock directory `'${lock_dir}\''.'
exit 1
fi
exit 0