Message-Id: <199511291224.MAA02151@orchard.medford.ma.us>
To: "Richard Basch" <basch@lehman.com>
Cc: Mark Eichin <eichin@cygnus.com>, cvs-krb5@MIT.EDU, krbdev@MIT.EDU,
        tytso@MIT.EDU
Subject: Re: 3-DES string-to-key algorithm 
In-Reply-To: Your message of "Wed, 29 Nov 1995 00:36:41 -0500 ."
             <199511290536.AAA10321@badger.lehman.com> 
Date: Wed, 29 Nov 1995 07:24:01 -0500
From: Bill Sommerfeld <sommerfeld@orchard.medford.ma.us>

-----BEGIN PGP SIGNED MESSAGE-----

Out of curiosity, what was the nature of your bug?

Here's my implementation of n-fold, in scheme (the only non-standard
usage here is char->ascii, which seems to be in every scheme
implementation anyway..).  The following is coded for simplicity, not
efficiency, as it a) uses bignums and b) completely expands the input
to lcm(n,l) bits long before reducing it.

I got the same result (modulo the case of the hex digits) in both scsh
and MIT Scheme so I musta done something right...

						- Bill

(define *debug* #f)

(define (string->bignum s)
  (let ((len (string-length s)))
    (let loop ((i 0) (n 0))
      (if (>= i len) n
	  (loop (+ i 1)
		(+ (* n 256)
		   (char->ascii (string-ref s i))))))))

(define (n-fold n)
  (define 2n (expt 2 n))
  (define 2to13 (expt 2 13))
  (define (oc-+ x y)
    (let ((tsum (+ x y)))
      (+ (modulo tsum 2n)
	 (quotient tsum 2n))))

  (lambda (X l)				; v is value; l is length in bits.
    (define 2l (expt 2 l))
    (define 2tol-13 (expt 2 (- l 13)))
    (define (l-rotr-13 v)
      (+ (quotient v 2to13)
	 (* 2tol-13 (modulo v 2to13))))

;;;	replicate the input value to a length that is the
;;;     least common multiple of n and the length of X
;;;	Before each repetition,
;;;     the input X is rotated to the right by 13 bit positions.  
;;;	The successive
;;;     n-bit chunks are added together using 1's-complement addition (addition
;;;     with end-around carry) to yield a n-bit result.

    (define (expand)
      (let loop ((i l)
		 (nX (l-rotr-13 X))
		 (sum X))
	(if *debug*
	    (begin
	      (display (string-append "expand -> "
				      (number->string i)
				      " #x" (number->string nX 16)
				      " #x" (number->string sum 16)))
	      (newline)))
	(if (= i 0)
	    sum				; done..
	    (loop (modulo (+ i l) n)
		  (l-rotr-13 nX)
		  (+ (* sum 2l) nX)))))
    (let loop ((residue (expand))
	       (sum 0))
      (if *debug* 
	  (begin
	    (display (string-append  "reduce -> "
				     " #x" (number->string residue 16)
				     " #x" (number->string sum 16)))
	    (newline)))
      (if (= residue 0)
	  sum
	  (loop (quotient residue 2n)
		(oc-+ sum (remainder residue 2n)))))))
			
(define 192-fold (n-fold 192))
(define 128-fold (n-fold 128))
(define 64-fold (n-fold 64))
(define 32-fold (n-fold 32))

(define (test-case string)
  (let ((val (number->string (192-fold (string->bignum string)
				       (* 8 (string-length string)))
			     16)))
    (display (string-append "192-fold(" string ") = "))
    (newline)
    (display (string-append "    " val))
    (newline)))

(define (test-case-1)
  (test-case "basch"))

(define (test-case-2)
  (test-case "eichin"))

(define (test-case-3)
  (test-case "sommerfeld"))

(define (test-case-4)
  (test-case "MASSACHVSETTS INSTITVTE OF TECHNOLOGY"))


-----BEGIN PGP SIGNATURE-----
Version: 2.6.1

iQCVAwUBMLxQ3bT+rHlVUGpxAQF38AQAqIhgqv+MJxXOQ/P/nRNFRvIuvt3Xav/9
YWwDPf4cp03KD0hpvR8DKnXx9KEwvn+SrloXTZgOqj8Io6BOF1biZmFc5DrzGmrG
pS0sJoc9Rvx+eQVzN2cvjizIvwqV2i6GnKINMk4qtxKoE7nZgxjkk0BYRmrJtei1
R6AGXTrQxqg=
=nfs3
-----END PGP SIGNATURE-----