Programming challenge: wildcard exclusion in cartesian products

Mark Carter me at privacy.net
Mon Mar 20 19:25:37 CET 2006


I'd like to propose a coding challenge of my own. The challenge is to 
reproduce the TEA (Tiny Encryption Algorith):
http://www.simonshepherd.supanet.com/tea.htm
in your language of choice.

Here's the code, just two simple functions:

void encipher(unsigned long *const v,unsigned long *const w,
    const unsigned long *const k)
{
    register unsigned long       y=v[0],z=v[1],sum=0,delta=0x9E3779B9,
				a=k[0],b=k[1],c=k[2],d=k[3],n=32;

    while(n-->0)
       {
       sum += delta;
       y += (z << 4)+a ^ z+sum ^ (z >> 5)+b;
       z += (y << 4)+c ^ y+sum ^ (y >> 5)+d;
       }

    w[0]=y; w[1]=z;
}

void decipher(unsigned long *const v,unsigned long *const w,
    const unsigned long *const k)
{
    register unsigned long       y=v[0],z=v[1],sum=0xC6EF3720,
				delta=0x9E3779B9,a=k[0],b=k[1],
				c=k[2],d=k[3],n=32;

    /* sum = delta<<5, in general sum = delta * n */

    while(n-->0)
       {
       z -= (y << 4)+c ^ y+sum ^ (y >> 5)+d;
       y -= (z << 4)+a ^ z+sum ^ (z >> 5)+b;
       sum -= delta;
       }

    w[0]=y; w[1]=z;
}

I had a crack at it in Lisp. My version doesn't work - but of greater 
concern to me is that it doesn't appear nearly as compact as the C 
version. Anyway, here's my Lisp code (no prizes for guessing that I'm a 
noob to Lisp):

(defconstant delta 2654435769 ) ; delta= 0x9E3779B9

(defun floorn (n) (nth-value 0 (floor n)))

(defun >> (val num-bytes)
   "Right-shift positive integer val by num-bytes"
   (let* (t1 t2)
     (setf t1 (expt 2 num-bytes))
     (setf t2 (/ val t1))
     (floor t2)))

(defun << (val num-bytes)
   "Left-shift positive integer v by num-bytes"
   (* val (expt 2 num-bytes)))

(defun <<4 (i) (<< i 4))

(defun byte-n (v n)
   "Return the nth byte of a value v"
   (let* ((bits-to-shift (* 8 (1- n)))
	 (shifted-value (>> v bits-to-shift)))
     (logand shifted-value 256)))
	

(defun transform (v1 v2 v3 v4)
   (let (t1 t2 t3)
     (setf t1 (<<4 v1))
     (setf t2 (expt v2 v1))
     (setf t3 (expt v3 (>> v2 5)))
     (+ t1 t2 t3 v4)))

(defun pack64 (b1 b2) (+ (<< b1 32) b2))

(defun encipher (v k)
   (let ((sum 0)
	(a (byte-n k 3))  ; a=k[0]
	(b (byte-n k 2))  ; b=k[1]	
	(c (byte-n k 1))  ; c=k[2]	
	(d (byte-n k 0))  ; d=k[3]	
	(y (byte-n v 1))  ; y=v[4]	
	(z (byte-n v 0))) ; z=v[1]


     (loop for n from 0 to 31 do  ;n=32, while(n-->0)
	  (incf sum delta)    ;sum += delta;
	  (incf y (transform z a sum b)) ; y += (z << 4)+a ^ z+sum ^ (z >> 5)+b
	  (incf z (transform y c sum d)) ;z += (y << 4)+c ^ y+sum ^ (y >> 5)+d;
	  )

     (pack64 y z) ; w[0]=y; w[1]=z;
     ))


(defun decipher (v k)
   (let ((sum 3337565984)  ; 0xC6EF3720
	(a (byte-n k 3))  ; a=k[0]
	(b (byte-n k 2))  ; b=k[1]	
	(c (byte-n k 1))  ; c=k[2]	
	(d (byte-n k 0))  ; d=k[3]	
	(y (byte-n v 1))  ; y=v[4]	
	(z (byte-n v 0))) ; z=v[1]

     (loop for n from 0 to 31 do  ;n=32, while(n-->0)
	  (decf z (transform y c sum d)) ;z -= (y << 4)+c ^ y+sum ^ (y >> 5)+d;
	  (decf y (transform z a sum b)) ;y -= (z << 4)+a ^ z+sum ^ (z >> 5)+b;
	  (decf sum delta)    ;sum -= delta;
	  )

     (pack64 y z) ; w[0]=y; w[1]=z;
     ))



More information about the Python-list mailing list