(in-package :hmac-sha1)
;;;
;;; SHA1 encryption
;;;

(defconstant +sha1-H0+ #x67452301)
(defconstant +sha1-H1+ #xefcdab89)
(defconstant +sha1-H2+ #x98badcfe)
(defconstant +sha1-H3+ #x10325476)
(defconstant +sha1-H4+ #xc3d2e1f0)

(defconstant +sha1-K0+ #x5a827999)
(defconstant +sha1-K1+ #x6ed9eba1) 
(defconstant +sha1-K2+ #x8f1bbcdc)
(defconstant +sha1-K3+ #xca62c1d6)
(defconstant +K+ (make-array 80 
                             :element-type '(unsigned-byte 32)
                             :initial-contents (nconc (make-list 20 :initial-element +sha1-K0+)
                                                      (make-list 20 :initial-element +sha1-K1+)
                                                      (make-list 20 :initial-element +sha1-K2+)
                                                      (make-list 20 :initial-element +sha1-K3+))))
(defconstant +eod-marker-size+ 1)
(defconstant +data-length-field-size+ 64)

(defun rotate-left (value n)
  (let ((top (ldb (byte n (- 32 n)) value)))
    (+ (* (logand (dpb 0
                       (byte n (- 32 n))
                       #xFFFFFFFF)
                  value)
          (expt 2 n))
       top)))
      
(defun sha1-fun (x y z iter)
  (cond ((< iter 20)
         (logxor (logand x y)
                 (logand (ldb (byte 32 0) (lognand x #xFFFFFFFF))
                         z)))
        ((< iter 40)
         (logxor x y z))
        ((< iter 60)
         (logxor (logand x y)
                 (logand x z)
                 (logand y z)))
        (t
         (logxor x y z))))

(defun convert-to-word (data buffer)
  (loop with data-conversion = (if (stringp data) #'char-code #'identity)
        with data-len = (length data)
        for i below data-len by 4
        for j from 0
        for byte1 = (funcall data-conversion (aref data i))
        for byte2 = (if (< (1+ i) data-len)
                        (funcall data-conversion (aref data (1+ i)))
                      0)
        for byte3 = (if (< (+ i 2) data-len)
                        (funcall data-conversion (aref data (+ i 2)))
                      0)
        for byte4 = (if (< (+ i 3) data-len)
                        (funcall data-conversion (aref data (+ i 3)))
                      0)
        do (setf (aref buffer j)
                 (dpb byte1 (byte 8 24)
                      (dpb byte2 (byte 8 16)
                           (dpb byte3 (byte 8 8)
                                byte4))))
        finally (return j)))

(defun preprocess-data (data)
  (let* ((data-len (length data))
         (message-bit-size (* data-len 8))
         (data-size (+ message-bit-size +eod-marker-size+ +data-length-field-size+))
         (hash-data-size (* 512 (ceiling data-size 512)))
         (padding-size (- 512 (mod (+ data-size 1 64) 512))))
    (when (= 512 padding-size)
      (setq padding-size 0))
    (let ((message-buffer (make-array (/ hash-data-size 32) :element-type '(unsigned-byte 32) :initial-element 0)))
      (let ((last-byte (convert-to-word data message-buffer)))
        (if (zerop (mod data-len 4))
            (setf (aref message-buffer (1+ last-byte)) #x80000000)
          (setf (aref message-buffer last-byte)
                (dpb #x80
                     (byte 8 (* (- 3 (mod data-len 4))
                                8))
                     (aref message-buffer last-byte)))))
      (setf (aref message-buffer (- (length message-buffer) 2))
            (ldb (byte 32 32) message-bit-size))
      (setf (aref message-buffer (1- (length message-buffer)))
            (ldb (byte 32 0) message-bit-size))
      message-buffer)))

(defun sha1 (data &optional (debug nil))
  (let ((message-buffer (preprocess-data data))
        (hash (make-array 5 :element-type '(unsigned-byte 32) :initial-contents (list +sha1-H0+ +sha1-H1+ +sha1-H2+ +sha1-H3+ +sha1-H4+)))
        (*print-base* 16))
    (loop with W = (make-array 80 :element-type '(unsigned-byte 32))
          for message-block-start from 0 by 16 below (length message-buffer)
          do (progn 
               (when debug
                 (print message-buffer) (print message-block-start))
               (replace W message-buffer :start2 message-block-start :end2 (+ message-block-start 16))
               (when debug
                 (print W))
               (loop for i from 16 to 79
                     for base-val = (logxor (aref W (- i 3)) (aref W (- i 8)) (aref W (- i 14)) (aref W (- i 16)))
                     for rotated-val = (rotate-left base-val 1)
                     do (setf (aref W i) rotated-val))
               (when debug
                 (print W))
               (let ((a (aref hash 0))
                     (b (aref hash 1))
                     (c (aref hash 2))
                     (d (aref hash 3))
                     (e (aref hash 4))
                     temp)
                 (loop for i from 0 below 80
                       do (progn
                            (setq temp (rotate-left a 5))
                            (setq temp (mod (+ temp (sha1-fun b c d i)) #.(expt 2 32)))
                            (setq temp (mod (+ temp e) #.(expt 2 32)))
                            (setq temp (mod (+ temp (aref +K+ i)) #.(expt 2 32)))
                            (setq temp (mod (+ temp (aref W i)) #.(expt 2 32)))

                            (setq e d
                                  d c
                                  c (rotate-left b 30)
                                  b a
                                  a temp)
                            (when debug
                              (format t "~2,'0d:~{ ~8,'0X~}~%" i (list a b c d e)))))
                 (setf (aref hash 0) (mod (+ (aref hash 0) a) #.(expt 2 32))
                       (aref hash 1) (mod (+ (aref hash 1) b) #.(expt 2 32))
                       (aref hash 2) (mod (+ (aref hash 2) c) #.(expt 2 32))
                       (aref hash 3) (mod (+ (aref hash 3) d) #.(expt 2 32))
                       (aref hash 4) (mod (+ (aref hash 4) e) #.(expt 2 32))))))
    (values (format nil "~8,'0X~8,'0X~8,'0X~8,'0X~8,'0X" (aref hash 0) (aref hash 1) (aref hash 2) (aref hash 3) (aref hash 4))
            (list (aref hash 0) (aref hash 1) (aref hash 2) (aref hash 3) (aref hash 4)))))


;;;
;;; HMAC signing with sha1 encryption
;;;

(defconstant +hmac-sha1-ipad+ #x36363636)
(defconstant +hmac-sha1-opad+ #x5c5c5c5c)

(defun create-hmac-sha1-signature (key data &optional debug)
  ;; sha1(K XOR opad, sha1(K XOR ipad, data))
  ;; where K is an n byte key
  ;; ipad is the byte 0x36 repeated 64 times
  ;; opad is the byte 0x5c repeated 64 times
  ;; and data is the data being protected
  (let ((*print-base* 16)
        ;; if length(key) < hash blocksize K = key else K = sha1(key)
        (hmac-key (if (> (length key) +data-length-field-size+)
                      (make-array 5 
                                  :element-type '(unsigned-byte 32)
                                  :initial-contents (second (multiple-value-list (sha1 key))))
                    (let ((buffer (make-array (ceiling (length key) 4) :element-type '(unsigned-byte 32) :initial-element 0)))
                      (convert-to-word key buffer)
                      buffer)))
        (zero-padded-key-buffer (make-array (/ +data-length-field-size+ 4) ;; 64 bytes = 16 words
                                            :element-type '(unsigned-byte 32)
                                            :initial-element 0))
        (ipad-xor-key (make-array 16 :element-type '(unsigned-byte 32)))
        (opad-xor-key (make-array 16 :element-type '(unsigned-byte 32)))
        (inner-hashed-byte-value (make-array (+ +data-length-field-size+
                                                (length data))
                                             :element-type '(unsigned-byte 8)))
        (outer-hashed-byte-value (make-array (+ +data-length-field-size+ 20) ; 64 byte buffer to 20 byte hash value
                                             :element-type '(unsigned-byte 8))))
    ;; step 1: create 0 padded value of K (64 bytes = 16 words)
    (replace zero-padded-key-buffer hmac-key :start2 0 :end2 (length hmac-key))
    (when debug
      (format t "K = ~A~%" zero-padded-key-buffer))
    ;; step 2: XOR with ipad
    (loop for i below (/ +data-length-field-size+ 4)
          do (setf (aref ipad-xor-key i)
                   (logxor (aref zero-padded-key-buffer i)
                           +hmac-sha1-ipad+)))
    (when debug
      (format t "ipad-xor = ~A~%" ipad-xor-key))
    ;; step 3: append 'text' to step 2
    ;; first copy step 2 to inner hash value buffer as bytes
    (loop for i below (/ +data-length-field-size+ 4)
          for ipad-xor = (aref ipad-xor-key i)
          for j = (* i 4)
          do (setf (aref inner-hashed-byte-value j) (ldb (byte 8 24) ipad-xor)
                   (aref inner-hashed-byte-value (1+ j)) (ldb (byte 8 16) ipad-xor)
                   (aref inner-hashed-byte-value (+ j 2)) (ldb (byte 8 8) ipad-xor)
                   (aref inner-hashed-byte-value (+ j 3)) (ldb (byte 8 0) ipad-xor)))
    ;; then copy the data after that
    (loop with data-conv = (if (stringp data) #'char-code #'identity)
          for i below (length data)
          for j from +data-length-field-size+ 
          do (setf (aref inner-hashed-byte-value j) (funcall data-conv (aref data i))))
    (when debug
      (format t "inner-hash = ~A~%" inner-hashed-byte-value))
    ;; step 4: hash result of step 3
    (multiple-value-bind (str hash-words)
      (sha1 inner-hashed-byte-value)
      (declare (ignore str))
      (when debug
        (format t "sha1 = ~A~%" hash-words))
      ;; step 5: xor step 4 result with opad
      (loop for i below (/ +data-length-field-size+ 4)
            do (setf (aref opad-xor-key i)
                     (logxor (aref zero-padded-key-buffer i)
                             +hmac-sha1-opad+)))
      (when debug
        (format t "opad-xor = ~A~%" opad-xor-key))
      ;; step 6: append step 4 result to opad-buffer from step 5
      (loop for i below (/ +data-length-field-size+ 4)
            for opad-xor = (aref opad-xor-key i)
            for j = (* i 4)
            do (setf (aref outer-hashed-byte-value j) (ldb (byte 8 24) opad-xor)
                     (aref outer-hashed-byte-value (1+ j)) (ldb (byte 8 16) opad-xor)
                     (aref outer-hashed-byte-value (+ j 2)) (ldb (byte 8 8) opad-xor)
                     (aref outer-hashed-byte-value (+ j 3)) (ldb (byte 8 0) opad-xor)))
      (loop for hash-word in hash-words
            for j from +data-length-field-size+ by 4
            do (setf (aref outer-hashed-byte-value j) (ldb (byte 8 24) hash-word)
                     (aref outer-hashed-byte-value (1+ j)) (ldb (byte 8 16) hash-word)
                     (aref outer-hashed-byte-value (+ j 2)) (ldb (byte 8 8) hash-word)
                     (aref outer-hashed-byte-value (+ j 3)) (ldb (byte 8 0) hash-word)))
      (when debug
        (format t "outer hash = ~A~%" outer-hashed-byte-value))
      ;; step 7: hash step 6 result and return
      (sha1 outer-hashed-byte-value debug))))

(defun test-hmac-sha1 ()
  (flet ((compare (i result expected)
           (if (string-equal result expected)
               (format t "Test ~D: success~%" i)
             (format t "Test ~D: Mismatch ~A ~A~%" i result expected))))
    (compare 1 (create-hmac-sha1-signature (make-array 20 :element-type '(unsigned-byte 8) :initial-element #x0b) 
                                           "Hi There")
             "b617318655057264e28bc0b6fb378c8ef146be00")
    (compare 2 (create-hmac-sha1-signature "Jefe" "what do ya want for nothing?")
             "effcdf6ae5eb2fa2d27416d5f184df9c259a7c79")
    (compare 3 (create-hmac-sha1-signature (make-array 20 :element-type '(unsigned-byte 8) :initial-element #xaa) 
                                           (make-array 50 :element-type '(unsigned-byte 8) 
                                                       :initial-element #xdd))
             "125d7342b9ac11cd91a39af48aa17b4f63f175d3")
    (compare 4 (create-hmac-sha1-signature (make-array 25 :element-type '(unsigned-byte 8) 
                                                       :initial-contents (loop for i below 25 collect (1+ i)))
                                           (make-array 50 :element-type '(unsigned-byte 8) 
                                                       :initial-element #xcd))
             "4c9007f4026250c6bc8414f9bf50c86c2d7235da")
    (compare 5 (create-hmac-sha1-signature (make-array 20 :element-type '(unsigned-byte 8) :initial-element #x0c) 
                                           "Test With Truncation")
             "4c1a03424b55e07fe7f27be1d58bb9324a9a5a04") ;; digest-96 = 0x4c1a03424b55e07fe7f27be1
    (compare 6 (create-hmac-sha1-signature (make-array 80 :element-type '(unsigned-byte 8) :initial-element #xaa) 
                                           "Test Using Larger Than Block-Size Key - Hash Key First")
             "aa4ae5e15272d00e95705637ce8a3b55ed402112")
    (compare 7 (create-hmac-sha1-signature (make-array 80 :element-type '(unsigned-byte 8) :initial-element #xaa) 
                                           "Test Using Larger Than Block-Size Key and Larger Than One Block-Size Data")
             "e8e99d0f45237d786d6bbaa7965c7808bbff1a91")))