cgit.sxemacs.org Git - packages/blob - xemacs-packages/ecrypto/rijndael.el

   1 ;;; rijndael.el --- Rijndael (AES) block cipher implementation
   2 ;; Copyright (C) 2001 Simon Josefsson
   3
   4 ;; Author: Simon Josefsson <jas@pdc.kth.se>
   5 ;; Keywords: rijndael aes block cipher symmetric encryption cryptography
   6
   7 ;; This software is provided as-is, without express or implied
   8 ;; warranty.  Permission to use, copy, modify, distribute or sell this
   9 ;; software, without fee, for any purpose and by any individual or
  10 ;; organization, is hereby granted, provided that the above copyright
  11 ;; notice and this paragraph appear in all copies.
  12
  13 ;;; Commentary:
  14
  15 ;; This is a implementation of the Rijndael block cipher algorithm in
  16 ;; Emacs Lisp.  Rijndael has been chosen as the Advanced Encryption
  17 ;; Standard (AES) by NIST.
  18 ;;
  19 ;; This package also have functionality to generate (some of) NIST's
  20 ;; Rijndael test vectors.  However, they will take a very long time to
  21 ;; generate in elisp.  You can customize `rijndael-monte-carlo-limit'
  22 ;; from the default of 10,000 into something more sensible as, say, 1
  23 ;; to make it faster.  It is also possible to customize the loop
  24 ;; length defined by `rijndael-monte-carlo-loop' from the default 400.
  25 ;; Of course, you need to modify the reference implementation as well
  26 ;; if you want to make useful comparisons of the test vectors.
  27 ;;
  28 ;; Rijndael home page is at:
  29 ;; http://www.esat.kuleuven.ac.be/~rijmen/rijndael/
  30 ;;
  31 ;; Any updated releases of this file will be located at:
  32 ;; http://josefsson.org/aes/
  33
  34 ;;; Instructions:
  35
  36 ;; Call functions in Emacs Lisp programs, or use this package
  37 ;; interactively in the *scratch* buffer in emacs.
  38 ;;
  39 ;; Here's how you could do a simple encryption interactively (press
  40 ;; C-j to evaluate each line):
  41 ;;
  42 ;; (setq key (rijndael-make-key 128 (rijndael-hexstring-to-bitstring
  43 ;;                                   "00000000000000000000000000000000")))
  44 ;;
  45 ;; (setq data (rijndael-hexstring-to-bitstring
  46 ;;             "00000000000000000000000000000000"))
  47 ;;
  48 ;; (rijndael-bitstring-to-hexstring
  49 ;;  (rijndael-block-encrypt data key 'ecb 128))
  50 ;;
  51 ;; Or more compact as:
  52 ;;
  53 ;; (rijndael-bitstring-to-hexstring
  54 ;;  (rijndael-block-encrypt
  55 ;;   (rijndael-hexstring-to-bitstring "00000000000000000000000000000000")
  56 ;;   (rijndael-make-key 128 (rijndael-hexstring-to-bitstring
  57 ;;                           "00000000000000000000000000000000"))
  58 ;;   'ecb 128))
  59 ;;
  60 ;; For reference, correct output is "66e94bd4ef8a2c3b884cfa59ca342b2e".
  61 ;;
  62 ;; NB! `data' will be destructively modified.
  63
  64 ;;; Todo:
  65
  66 ;; Other modes than ECB.
  67
  68 ;;; Revision history:
  69
  70 ;; 2001-03-31  Posted to gnu.emacs.sources.
  71 ;; 2001-04-04  Ported to (X)Emacs 19.
  72 ;; 2001-05-10  Supports 160 and 224 key and block sizes.
  73 ;; 2001-09-27  Posted to gnu.emacs.sources.
  74
  75 \f
  76 ;;; Code:
  77
  78 ;; User variables:
  79
  80 (eval-and-compile
  81   ;; Provide dummy customize functions for emacsen that doesn't have them.
  82   (if (not (and (or (featurep 'custom) (load "custom" t))
  83                 (fboundp 'defcustom) (fboundp 'defgroup)))
  84       (progn
  85         (if (not (fboundp 'defcustom))
  86             (defmacro defcustom (var value doc &rest args)
  87               (list 'defvar var value doc)))
  88         (if (not (fboundp 'defgroup))
  89             (defmacro defgroup (&rest args))))))
  90
  91 (defgroup rijndael nil
  92   "Rijndael cryptographic functions")
  93
  94 (defcustom rijndael-monte-carlo-limit 10000
  95   "How many iterations to do in the Monte-Carlo tests.
  96 NIST uses 10000 (the default), but this will be very slow, so you may
  97 change this to a lower value (like, say, 1).  Of course, you must
  98 modify the Rijndael reference implementation to be able to compare the
  99 output."
 100   :group 'rijndael
 101   :type 'integer)
 102
 103 (defcustom rijndael-monte-carlo-loop 400
 104   "How many iterations to do in the Monte-Carlo tests.
 105 NIST uses 400 (the default), but this will be very slow, so you may
 106 change this to a lower value (like, say, 1).  Of course, you must
 107 modify the Rijndael reference implementation to be able to compare the
 108 output."
 109   :group 'rijndael
 110   :type 'integer)
 111
 112 \f
 113 ;; Internal constants:
 114
 115 (defconst rijndael-Logtable
 116   [  0   0  25   1  50   2  26 198  75 199  27 104  51 238 223   3
 117    100   4 224  14  52 141 129 239  76 113   8 200 248 105  28 193
 118    125 194  29 181 249 185  39 106  77 228 166 114 154 201   9 120
 119    101  47 138   5  33  15 225  36  18 240 130  69  53 147 218 142
 120    150 143 219 189  54 208 206 148  19  92 210 241  64  70 131  56
 121    102 221 253  48 191   6 139  98 179  37 226 152  34 136 145  16
 122    126 110  72 195 163 182  30  66  58 107  40  84 250 133  61 186
 123     43 121  10  21 155 159  94 202  78 212 172 229 243 115 167  87
 124    175  88 168  80 244 234 214 116  79 174 233 213 231 230 173 232
 125     44 215 117 122 235  22  11 245  89 203  95 176 156 169  81 160
 126    127  12 246 111  23 196  73 236 216  67  31  45 164 118 123 183
 127    204 187  62  90 251  96 177 134  59  82 161 108 170  85  41 157
 128    151 178 135 144  97 190 220 252 188 149 207 205  55  63  91 209
 129     83  57 132  60  65 162 109  71  20  42 158  93  86 242 211 171
 130     68  17 146 217  35  32  46 137 180 124 184  38 119 153 227 165
 131    103  74 237 222 197  49 254  24  13  99 140 128 192 247 112   7]
 132   "Multiplication in GF(2^8) lookup table.")
 133
 134 (defconst rijndael-Alogtable
 135   [  1   3   5  15  17  51  85 255  26  46 114 150 161 248  19  53
 136     95 225  56  72 216 115 149 164 247   2   6  10  30  34 102 170
 137    229  52  92 228  55  89 235  38 106 190 217 112 144 171 230  49
 138     83 245   4  12  20  60  68 204  79 209 104 184 211 110 178 205
 139     76 212 103 169 224  59  77 215  98 166 241   8  24  40 120 136
 140    131 158 185 208 107 189 220 127 129 152 179 206  73 219 118 154
 141    181 196  87 249  16  48  80 240  11  29  39 105 187 214  97 163
 142    254  25  43 125 135 146 173 236  47 113 147 174 233  32  96 160
 143    251  22  58  78 210 109 183 194  93 231  50  86 250  21  63  65
 144    195  94 226  61  71 201  64 192  91 237  44 116 156 191 218 117
 145    159 186 213 100 172 239  42 126 130 157 188 223 122 142 137 128
 146    155 182 193  88 232  35 101 175 234  37 111 177 200  67 197  84
 147    252  31  33  99 165 244   7   9  27  45 119 153 176 203  70 202
 148     69 207  74 222 121 139 134 145 168 227  62  66 198  81 243  14
 149     18  54  90 238  41 123 141 140 143 138 133 148 167 242  13  23
 150     57  75 221 124 132 151 162 253  28  36 108 180 199  82 246   1]
 151   "Multiplication in GF(2^8) lookup table.")
 152
 153 (defconst rijndael-S
 154   [ 99 124 119 123 242 107 111 197  48   1 103  43 254 215 171 118
 155    202 130 201 125 250  89  71 240 173 212 162 175 156 164 114 192
 156    183 253 147  38  54  63 247 204  52 165 229 241 113 216  49  21
 157      4 199  35 195  24 150   5 154   7  18 128 226 235  39 178 117
 158      9 131  44  26  27 110  90 160  82  59 214 179  41 227  47 132
 159     83 209   0 237  32 252 177  91 106 203 190  57  74  76  88 207
 160    208 239 170 251  67  77  51 133  69 249   2 127  80  60 159 168
 161     81 163  64 143 146 157  56 245 188 182 218  33  16 255 243 210
 162    205  12  19 236  95 151  68  23 196 167 126  61 100  93  25 115
 163     96 129  79 220  34  42 144 136  70 238 184  20 222  94  11 219
 164    224  50  58  10  73   6  36  92 194 211 172  98 145 149 228 121
 165    231 200  55 109 141 213  78 169 108  86 244 234 101 122 174   8
 166    186 120  37  46  28 166 180 198 232 221 116  31  75 189 139 138
 167    112  62 181 102  72   3 246  14  97  53  87 185 134 193  29 158
 168    225 248 152  17 105 217 142 148 155  30 135 233 206  85  40 223
 169    140 161 137  13 191 230  66 104  65 153  45  15 176  84 187  22]
 170   "Rijndael S-box.")
 171
 172 (defconst rijndael-Si
 173   [ 82   9 106 213  48  54 165  56 191  64 163 158 129 243 215 251
 174    124 227  57 130 155  47 255 135  52 142  67  68 196 222 233 203
 175     84 123 148  50 166 194  35  61 238  76 149  11  66 250 195  78
 176      8  46 161 102  40 217  36 178 118  91 162  73 109 139 209  37
 177    114 248 246 100 134 104 152  22 212 164  92 204  93 101 182 146
 178    108 112  72  80 253 237 185 218  94  21  70  87 167 141 157 132
 179    144 216 171   0 140 188 211  10 247 228  88   5 184 179  69   6
 180    208  44  30 143 202  63  15   2 193 175 189   3   1  19 138 107
 181     58 145  17  65  79 103 220 234 151 242 207 206 240 180 230 115
 182    150 172 116  34 231 173  53 133 226 249  55 232  28 117 223 110
 183     71 241  26 113  29  41 197 137 111 183  98  14 170  24 190  27
 184    252  86  62  75 198 210 121  32 154 219 192 254 120 205  90 244
 185     31 221 168  51 136   7 199  49 177  18  16  89  39 128 236  95
 186     96  81 127 169  25 181  74  13  45 229 122 159 147 201 156 239
 187    160 224  59  77 174  42 245 176 200 235 187  60 131  83 153  97
 188     23  43   4 126 186 119 214  38 225 105  20  99  85  33  12 125]
 189   "Rijndael inverted S-box.")
 190
 191 (defconst rijndael-rcon [ ?\x01 ?\x02 ?\x04 ?\x08 ?\x10 ?\x20 ?\x40 ?\x80
 192                           ?\x1b ?\x36 ?\x6c ?\xd8 ?\xab ?\x4d ?\x9a ?\x2f
 193                           ?\x5e ?\xbc ?\x63 ?\xc6 ?\x97 ?\x35 ?\x6a ?\xd4
 194                           ?\xb3 ?\x7d ?\xfa ?\xef ?\xc5 ?\x91]
 195   "Rijndael round constants used in key scheduling.")
 196
 197 (defconst rijndael-shifts [[[0 0]
 198                             [1 3]
 199                             [2 2]
 200                             [3 1]]
 201
 202                            [[0 0]
 203                             [1 4]
 204                             [2 3]
 205                             [3 2]]
 206
 207                            [[0 0]
 208                             [1 5]
 209                             [2 4]
 210                             [3 3]]
 211
 212                            [[0 0]
 213                             [1 6]
 214                             [2 5]
 215                             [4 3]]
 216
 217                            [[0 0]
 218                             [1 7]
 219                             [3 5]
 220                             [4 4]]]
 221   "Rijndael shift offsets.
 222 Element M is used when blocksizes match M=Nb-4.
 223 Element N inside a shift amount for each blocksize corresponds with
 224 the row to shift.
 225 The first element O1 of each row corresponds with encryption offset,
 226 the second element O2 to decryption offset. (O2 inverse of O1 under mod Nb.)")
 227
 228 (defconst rijndael-maxbc (/ 256 32)
 229   "Rijndael maximum size of data blocks.")
 230
 231 (defconst rijndael-maxkc (/ 256 32)
 232   "Rijndael maximum size of key blocks.")
 233
 234 (defconst rijndael-maxrounds 14
 235   "Rijndael maximum number of rounds.")
 236
 237 (defconst rijndael-hex-alist
 238   '((?0 . 0)          (?a . 10)       (?A . 10)
 239     (?1 . 1)          (?b . 11)       (?B . 11)
 240     (?2 . 2)          (?c . 12)       (?C . 12)
 241     (?3 . 3)          (?d . 13)       (?D . 13)
 242     (?4 . 4)          (?e . 14)       (?E . 14)
 243     (?5 . 5)          (?f . 15)       (?F . 15)
 244     (?6 . 6)
 245     (?7 . 7)
 246     (?8 . 8)
 247     (?9 . 9))
 248   "Hex table for use in base conversions.")
 249
 250 \f
 251 ;; Basic low-level cryptograhic primitives:
 252
 253 (defsubst rijndael-mul (a b)
 254   "Rijndael MUL primitive.
 255 Multiply two elements of GF(2^m).
 256 needed for MixColumn and InvMixColumn."
 257   (if (and (not (= a 0))
 258            (not (= b 0)))
 259       (aref rijndael-Alogtable (% (+ (aref rijndael-Logtable a)
 260                                      (aref rijndael-Logtable b))
 261                                   255))
 262     0))
 263
 264 (defsubst rijndael-key-addition (a rk bc)
 265   "Rijndael keyAddition primitive.
 266 Exor corresponding text input and round key input bytes."
 267   (let ((i 0) j)
 268     (while (< i 4)
 269       (setq j 0)
 270       (while (< j bc)
 271         (aset (aref a i) j
 272               (logxor (aref (aref a i) j)
 273                       (aref (aref rk i) j)))
 274         (setq j (1+ j)))
 275       (setq i (1+ i)))))
 276
 277 (defsubst rijndael-shift-row (a d bc)
 278   "Rijndael ShiftRow primitive.
 279 Row 0 remains unchanged.
 280 The other three rows are shifted a variable amount."
 281   (let (i j (tmp (make-vector rijndael-maxbc 0)))
 282     (setq i 1)
 283     (while (< i 4)
 284       (setq j 0)
 285       (while (< j bc)
 286         (aset tmp j
 287               (aref (aref a i)
 288                     (% (+ j (aref (aref (aref rijndael-shifts
 289                                               (- bc 4))
 290                                         i)
 291                                   d))
 292                        bc)))
 293         (setq j (1+ j)))
 294       (setq j 0)
 295       (while (< j bc)
 296         (aset (aref a i) j (aref tmp j))
 297         (setq j (1+ j)))
 298       (setq i (1+ i)))))
 299
 300 (defsubst rijndael-substitution (a box bc)
 301   "Rijndael substitution primitive.
 302 Replace every byte of the input by the byte at that place
 303 in the nonlinear S-box."
 304   (let ((i 0) j)
 305     (while (< i 4)
 306       (setq j 0)
 307       (while (< j bc)
 308         (aset (aref a i) j (aref box (aref (aref a i) j)))
 309         (setq j (1+ j)))
 310       (setq i (1+ i)))))
 311
 312 (defsubst rijndael-mix-column (a bc)
 313   "Rijndael MixColumn primitive.
 314 Mix the four bytes of every column in a linear way."
 315   (let ((b (make-vector 4 0)) i j)
 316     ;; init b
 317     (setq i 0)
 318     (while (< i 4)
 319       (aset b i (make-vector rijndael-maxbc 0))
 320       (setq i (1+ i)))
 321     ;; do it
 322     (setq j 0)
 323     (while (< j bc)
 324       (setq i 0)
 325       (while (< i 4)
 326         (aset (aref b i)
 327               j
 328               (logxor (rijndael-mul 2 (aref (aref a i) j))
 329                       (rijndael-mul 3 (aref (aref a (% (+ i 1) 4)) j))
 330                       (aref (aref a (% (+ i 2) 4)) j)
 331                       (aref (aref a (% (+ i 3) 4)) j)))
 332         (setq i (1+ i)))
 333       (setq j (1+ j)))
 334     ;; copy b back into a
 335     (setq i 0)
 336     (while (< i 4)
 337       (setq j 0)
 338       (while (< j bc)
 339         (aset (aref a i) j (aref (aref b i) j))
 340         (setq j (1+ j)))
 341       (setq i (1+ i)))))
 342
 343 (defsubst rijndael-inv-mix-column (a bc)
 344   "Rijndael inverted MixColumn primitive.
 345 Mix the four bytes of every column in a linear way.
 346 This is the opposite operation of Mixcolumn."
 347   (let ((b (make-vector 4 0)) i j)
 348     ;; init b
 349     (setq i 0)
 350     (while (< i 4)
 351       (aset b i (make-vector rijndael-maxbc 0))
 352       (setq i (1+ i)))
 353     ;; do it
 354     (setq j 0)
 355     (while (< j bc)
 356       (setq i 0)
 357       (while (< i 4)
 358         (aset (aref b i)
 359               j
 360               (logxor (rijndael-mul ?\x0E (aref (aref a i) j))
 361                       (rijndael-mul ?\x0B (aref (aref a (% (+ i 1) 4)) j))
 362                       (rijndael-mul ?\x0D (aref (aref a (% (+ i 2) 4)) j))
 363                       (rijndael-mul ?\x09 (aref (aref a (% (+ i 3) 4)) j))))
 364         (setq i (1+ i)))
 365       (setq j (1+ j)))
 366     ;; copy b back into a
 367     (setq i 0)
 368     (while (< i 4)
 369       (setq j 0)
 370       (while (< j bc)
 371         (aset (aref a i) j (aref (aref b i) j))
 372         (setq j (1+ j)))
 373       (setq i (1+ i)))))
 374
 375 \f
 376 ;; Internal functions:
 377
 378 (defun rijndael-bc (blockBits)
 379   "Determine BC given block size."
 380   (if (or (< blockBits 128) (> blockBits 256))
 381       (error "Invalid block size %d bits" blockBits)
 382     (/ blockBits 32)))
 383
 384 (defun rijndael-rounds (keyBits blockBits)
 385   "Determine Rijndael rounds given key and block sizes."
 386   (if (or (< keyBits 128) (> keyBits 256) (< blockBits 128) (> blockBits 256))
 387       (error "Invalid key/block size combination (key size %d block size %d)"
 388              keyBits blockBits)
 389     (+ (/ (max keyBits blockBits) 32) 6)))
 390
 391 (defun rijndael-print-key-schedule (key-schedule)
 392   (let (i j k str)
 393     (setq i 0)
 394     (while (< i (1+ rijndael-maxrounds))
 395       (setq j 0)
 396       (while (< j 4)
 397         (setq k 0)
 398         (while (< k rijndael-maxbc)
 399           (setq str (concat str (format "%3d "
 400                                         (aref (aref (aref key-schedule i)
 401                                                     j)
 402                                               k))))
 403           (setq k (1+ k)))
 404         (setq str (concat str "\n"))
 405         (setq j (1+ j)))
 406       (setq str (concat str "\n"))
 407       (setq i (1+ i)))
 408     (setq str (concat str "\n"))))
 409
 410 (defun rijndael-key-schedule (k keyBits blockBits)
 411   "Rijndael KeySchedule function (internal).
 412 Calculate the necessary round keys.
 413 The number of calculations depends on keyBits and blockBits."
 414   (let ((rconpointer 0) i j T
 415         (kc (rijndael-bc keyBits))
 416         (bc (rijndael-bc blockBits))
 417         (rounds (rijndael-rounds keyBits blockBits))
 418         (tk (make-vector 4 0))
 419         (W (make-vector (1+ rijndael-maxrounds) 0))
 420         (mid 4))
 421     ;; init tk
 422     (setq i 0)
 423     (while (< i 4)
 424       (aset tk i (make-vector rijndael-maxkc 0))
 425       (setq i (1+ i)))
 426     ;; init W
 427     (setq i 0)
 428     (while (< i (1+ rijndael-maxrounds))
 429       (aset W i (make-vector 4 0))
 430       (setq j 0)
 431       (while (< j 4)
 432         (aset (aref W i) j (make-vector rijndael-maxbc 0))
 433         (setq j (1+ j)))
 434       (setq i (1+ i)))
 435     ;; start
 436     (setq j 0)
 437     (while (< j kc)
 438       (setq i 0)
 439       (while (< i 4)
 440         (aset (aref tk i) j
 441               (aref (aref k i) j))
 442         (setq i (1+ i)))
 443       (setq j (1+ j)))
 444     ;; copy values into round key array
 445     (setq j 0
 446           T 0)
 447     (while (and (< j kc) (< T (* (1+ rounds) bc)))
 448       (setq i 0)
 449       (while (< i 4)
 450         (aset (aref (aref W (/ T bc)) i) (% T bc)
 451               (aref (aref tk i) j))
 452         (setq i (1+ i)))
 453       (setq j (1+ j))
 454       (setq T (1+ T)))
 455     ;; while not enough round key material calculated
 456     (while (< T (* (1+ rounds) bc))
 457       ;; calculate new values
 458       (setq i 0)
 459       (while (< i 4)
 460         (aset (aref tk i) 0
 461               (logxor (aref (aref tk i) 0)
 462                       (aref rijndael-S
 463                             (aref (aref tk (% (1+ i) 4)) (1- kc)))))
 464         (setq i (1+ i)))
 465       (aset (aref tk 0) 0
 466             (logxor (aref (aref tk 0) 0)
 467                     (aref rijndael-rcon rconpointer)))
 468       (setq rconpointer (1+ rconpointer))
 469       (setq j 1)
 470       (if (<= kc 6)
 471           (while (< j kc)
 472             (setq i 0)
 473             (while (< i mid)
 474               (aset (aref tk i) j
 475                     (logxor (aref (aref tk i) j)
 476                             (aref (aref tk i) (1- j))))
 477               (setq i (1+ i)))
 478             (setq j (1+ j)))
 479         (while (< j mid)
 480           (setq i 0)
 481           (while (< i 4)
 482             (aset (aref tk i) j
 483                   (logxor (aref (aref tk i) j)
 484                           (aref (aref tk i) (1- j))))
 485             (setq i (1+ i)))
 486           (setq j (1+ j)))
 487         (setq i 0)
 488         (while (< i 4)
 489           (aset (aref tk i) mid
 490                 (logxor (aref (aref tk i) mid)
 491                         (aref rijndael-S (aref (aref tk i) (1- mid)))))
 492           (setq i (1+ i)))
 493         (setq j (1+ mid) i 0)
 494         (while (< j kc)
 495           (setq i 0)
 496           (while (< i mid)
 497             (aset (aref tk i) j
 498                   (logxor (aref (aref tk i) j)
 499                           (aref (aref tk i) (1- j))))
 500             (setq i (1+ i)))
 501           (setq j (1+ j))))
 502       ;; copy values into round key array
 503       (setq j 0)
 504       (while (and (< j kc) (< T (* (1+ rounds) bc)))
 505         (setq i 0)
 506         (while (< i 4)
 507           (aset (aref (aref W (/ T bc)) i) (% T bc)
 508                 (aref (aref tk i) j))
 509           (setq i (1+ i)))
 510         (setq j (1+ j))
 511         (setq T (1+ T))))
 512     W))
 513
 514 (defun rijndael-encrypt (a keyBits blockBits rk &optional rounds)
 515   "Rijndael block encryption (internal).
 516 Encryption of one block.  If optional argument rounds is non-null,
 517 encrypt only a certain number of rounds (for debugging only)."
 518   (let ((r 1)
 519         (bc (rijndael-bc blockBits))
 520         (ROUNDS (rijndael-rounds keyBits blockBits)))
 521     ;; make number of rounds sane
 522     (if (or (null rounds) (> rounds ROUNDS))
 523         (setq rounds ROUNDS))
 524     ;; begin with a key addition
 525     (rijndael-key-addition a (aref rk 0) bc)
 526     ;; ROUNDS-1 ordinary rounds
 527     (while (and (<= r rounds) (< r ROUNDS))
 528       (rijndael-substitution a rijndael-S bc)
 529       (rijndael-shift-row a 0 bc)
 530       (rijndael-mix-column a bc)
 531       (rijndael-key-addition a (aref rk r) bc)
 532       (setq r (1+ r)))
 533     ;; Last round is special: there is no MixColumn
 534     (if (= rounds ROUNDS)
 535         (progn
 536           (rijndael-substitution a rijndael-S bc)
 537           (rijndael-shift-row a 0 bc)
 538           (rijndael-key-addition a (aref rk rounds) bc)))))
 539
 540 (defun rijndael-decrypt (a keyBits blockBits rk &optional rounds)
 541   "Rijndael block decryption (internal).
 542 Decryption of one block.  If optional argument rounds is non-null,
 543 decrypt only a certain number of rounds (for debugging only)."
 544   (let* ((bc (rijndael-bc blockBits))
 545         (ROUNDS (rijndael-rounds keyBits blockBits))
 546         (r (1- ROUNDS)))
 547     ;; make number of rounds sane
 548     (if (or (null rounds) (> rounds ROUNDS))
 549         (setq rounds 0))
 550     ;; First the special round:
 551     ;;   without InvMixColumn
 552     ;;   with extra KeyAddition
 553     (rijndael-key-addition a (aref rk ROUNDS) bc)
 554     (rijndael-substitution a rijndael-Si bc)
 555     (rijndael-shift-row a 1 bc)
 556     (while (> r rounds)
 557       (rijndael-key-addition a (aref rk r) bc)
 558       (rijndael-inv-mix-column a bc)
 559       (rijndael-substitution a rijndael-Si bc)
 560       (rijndael-shift-row a 1 bc)
 561       (setq r (1- r)))
 562     ;; End with the extra key addition
 563     (if (= rounds 0)
 564         (rijndael-key-addition a (aref rk 0) bc))))
 565
 566 \f
 567 ;; Rijndael API functions:
 568
 569 (defun rijndael-make-key (blockbits keymaterial)
 570   "Generate Key Schedule given keying material KEYMATERIAL.
 571 KEYMATERIAL must be of length multiple of 32 bits.
 572 BLOCKBITS is size of blocks in bits (valid values 128, 160, 192, 224 and 256)."
 573   (let ((k (make-vector 4 0)) i
 574         (keybits (* (length keymaterial) 8)))
 575     ;; init k
 576     (setq i 0)
 577     (while (< i 4)
 578       (aset k i (make-vector rijndael-maxkc 0))
 579       (setq i (1+ i)))
 580     (setq i 0)
 581     (while (< i (/ keybits 8))
 582       (aset (aref k (% i 4)) (/ i 4) (aref (vconcat keymaterial) i))
 583       (setq i (1+ i)))
 584     (list keybits keymaterial (rijndael-key-schedule k keybits blockbits))))
 585
 586 (defun rijndael-block-encrypt (data key mode blockbits &optional iv)
 587   "Perform Rijndael encryption of DATA with key KEY.
 588 DATA is a vector with data to encrypt (the block).
 589 KEY is a Rijndael Key Schedule (see `rijndael-make-key').
 590 MODE is a symbol, `ecb', `cbc' or `cfb1', for the encryption mode to use.
 591 BLOCKBITS is size of blocks in bits (valid values 128, 160, 192, 224 and 256).
 592 Optional variable IV is a string containing initialization vectors."
 593   (let ((numBlocks (/ (length data) (/ blockbits 8)))
 594         (blk (make-vector 4 0))
 595         i j l)
 596     ;; init blk
 597     (setq i 0)
 598     (while (< i 4)
 599       (aset blk i (make-vector rijndael-maxbc 0))
 600       (setq i (1+ i)))
 601     (cond ((eq mode 'ecb)
 602            (setq i 0)
 603            (while (< i numBlocks)
 604              (setq j 0)
 605              (while (< j (/ blockbits 32))
 606                (setq l 0)
 607                (while (< l 4)
 608                  (aset (aref blk l) j (aref data (+ (* (/ blockbits 8) i)
 609                                                     (* 4 j)
 610                                                     l)))
 611                  (setq l (1+ l)))
 612                (setq j (1+ j)))
 613              (rijndael-encrypt blk (nth 0 key) blockbits (nth 2 key))
 614              (setq j 0)
 615              (while (< j (/ blockbits 32))
 616                (setq l 0)
 617                (while (< l 4)
 618                  (aset data (+ (* (/ blockbits 8) i)
 619                                (* 4 j)
 620                                l)
 621                        (aref (aref blk l) j))
 622                  (setq l (1+ l)))
 623                (setq j (1+ j)))
 624              (setq i (1+ i))))
 625           (t
 626            (error "Unknown encryption mode: %s" mode)))
 627     data))
 628
 629 (defun rijndael-block-decrypt (data key mode blockbits &optional iv)
 630   "Perform Rijndael encryption of DATA with key KEY.
 631 DATA is a vector with data to encrypt (the block).
 632 KEY is a Rijndael Key Schedule (see `rijndael-make-key').
 633 MODE is a symbol, `ecb', `cbc' or `cfb1', for the decryption mode to use.
 634 BLOCKBITS is size of block in bits (valid values 128, 160, 192, 224 and 256).
 635 Optional variable IV is a string containing initialization vectors."
 636   (let ((numBlocks (/ (length data) (/ blockbits 8)))
 637         (blk (make-vector 4 0))
 638         i j l)
 639     ;; init blk
 640     (setq i 0)
 641     (while (< i 4)
 642       (aset blk i (make-vector rijndael-maxbc 0))
 643       (setq i (1+ i)))
 644     (cond ((eq mode 'ecb)
 645            (setq i 0)
 646            (while (< i numBlocks)
 647              (setq j 0)
 648              (while (< j (/ blockbits 32))
 649                (setq l 0)
 650                (while (< l 4)
 651                  (aset (aref blk l) j (aref data (+ (* (/ blockbits 8) i)
 652                                                     (* 4 j)
 653                                                     l)))
 654                  (setq l (1+ l)))
 655                (setq j (1+ j)))
 656              (rijndael-decrypt blk (nth 0 key) blockbits (nth 2 key))
 657              (setq j 0)
 658              (while (< j (/ blockbits 32))
 659                (setq l 0)
 660                (while (< l 4)
 661                  (aset data (+ (* (/ blockbits 8) i)
 662                                (* 4 j)
 663                                l)
 664                        (aref (aref blk l) j))
 665                  (setq l (1+ l)))
 666                (setq j (1+ j)))
 667              (setq i (1+ i))))
 668           (t
 669            (error "Unknown decryption mode: %s" mode)))
 670     data))
 671
 672 \f
 673 ;; Conversion functions:
 674
 675 (defun rijndael-hex-to-int (str)
 676   (if str
 677       (if (listp str)
 678           (+ (* 16 (rijndael-hex-to-int (cdr str)))
 679              (cdr (assoc (car str) rijndael-hex-alist)))
 680         (rijndael-hex-to-int (reverse (append str nil))))
 681     0))
 682
 683 (defun rijndael-hexstring-to-bitstring (str)
 684   (let (out)
 685     (while (< 0 (length str))
 686       (setq out (cons (rijndael-hex-to-int (substring str -2)) out))
 687       (setq str (substring str 0 -2)))
 688     (concat out)))
 689
 690 (defun rijndael-vector-to-hexstring (vec)
 691   (mapconcat (lambda (el)
 692                (format "%02x" el))
 693              vec
 694              ""))
 695
 696 (defun rijndael-vector-to-bitstring (vec)
 697   (rijndael-hexstring-to-bitstring (rijndael-vector-to-hexstring vec)))
 698
 699 (defun rijndael-bitstring-to-vector (str)
 700   (let ((out (make-vector (length str) 0))
 701         (i (1- (length str))))
 702     (while (< 0 (length str))
 703       (aset out i (string-to-char (substring str -1)))
 704       (setq i (1- i))
 705       (setq str (substring str 0 -1)))
 706     out))
 707
 708 (defun rijndael-bitstring-to-hexstring (str)
 709   (let ((out ""))
 710     (while (< 0 (length str))
 711       (setq out (format "%02x%s" (string-to-char (substring str -1)) out))
 712       (setq str (substring str 0 -1)))
 713     out))
 714
 715 \f
 716 ;; NIST test value generator
 717
 718 (defun rijndael-nist ()
 719   "Generate NIST test values.
 720 The output is to be compared with the NIST tabulated values."
 721   (interactive)
 722   (switch-to-buffer (generate-new-buffer "*NIST Rijndael test values"))
 723   (erase-buffer)
 724   (insert "\n\n\nElectronic Codebook (ECB) Mode - ENCRYPTION\n")
 725   ;; ECB encrypt keysize 128
 726   (rijndael-nist-ecb-mct
 727    "00000000000000000000000000000000" 128
 728    "00000000000000000000000000000000" 128 'encrypt)
 729   ;; ECB encrypt keysize 160
 730   (rijndael-nist-ecb-mct
 731    "0000000000000000000000000000000000000000" 160
 732    "00000000000000000000000000000000" 128 'encrypt)
 733   ;; ECB encrypt keysize 192
 734   (rijndael-nist-ecb-mct
 735    "000000000000000000000000000000000000000000000000" 192
 736    "00000000000000000000000000000000" 128 'encrypt)
 737   ;; ECB encrypt keysize 224
 738   (rijndael-nist-ecb-mct
 739    "00000000000000000000000000000000000000000000000000000000" 224
 740    "00000000000000000000000000000000" 128 'encrypt)
 741   ;; ECB encrypt keysize 256
 742   (rijndael-nist-ecb-mct
 743    "0000000000000000000000000000000000000000000000000000000000000000" 256
 744    "00000000000000000000000000000000" 128 'encrypt)
 745   (insert "\n\n\nElectronic Codebook (ECB) Mode - DECRYPTION\n")
 746   ;; ECB decrypt keysize 128
 747   (rijndael-nist-ecb-mct
 748    "00000000000000000000000000000000" 128
 749    "00000000000000000000000000000000" 128 'decrypt)
 750   ;; ECB decrypt keysize 160
 751   (rijndael-nist-ecb-mct
 752    "0000000000000000000000000000000000000000" 160
 753    "00000000000000000000000000000000" 128 'decrypt)
 754   ;; ECB decrypt keysize 192
 755   (rijndael-nist-ecb-mct
 756    "000000000000000000000000000000000000000000000000" 192
 757    "00000000000000000000000000000000" 128 'decrypt)
 758   ;; ECB decrypt keysize 224
 759   (rijndael-nist-ecb-mct
 760    "00000000000000000000000000000000000000000000000000000000" 224
 761    "00000000000000000000000000000000" 128 'decrypt)
 762   ;; ECB decrypt keysize 256
 763   (rijndael-nist-ecb-mct
 764    "0000000000000000000000000000000000000000000000000000000000000000" 256
 765    "00000000000000000000000000000000" 128 'decrypt)
 766   (message "NIST Rijndael tables generation...done"))
 767
 768 (defun rijndael-nist-ecb-mct (initKey keyLength initBlock blockLength dir)
 769   (let ((binKey (rijndael-bitstring-to-vector
 770                  (rijndael-hexstring-to-bitstring initKey)))
 771         (outBlock (rijndael-hexstring-to-bitstring initBlock))
 772         (i 0) j keyInst inBlock)
 773     (insert "\n=========================\n\n")
 774     (insert (format "KEYSIZE=%d\n" keyLength))
 775     (while (< i rijndael-monte-carlo-loop)
 776       (sit-for 0)
 777       (insert (format "\nI=%d\n" i))
 778       (insert "KEY=" (rijndael-vector-to-hexstring binKey) "\n")
 779       (setq keyInst (rijndael-make-key blockLength
 780                                        (rijndael-vector-to-bitstring binKey)))
 781       (insert (if (eq dir 'encrypt) "PT=" "CT=")
 782               (rijndael-bitstring-to-hexstring outBlock) "\n")
 783       (setq j 0)
 784       (while (< j rijndael-monte-carlo-limit)
 785         (if (eq (% j 100) 0)
 786             (message (concat "Rijndael NIST ECB MCT %sion (%db keys, "
 787                              "%db blocks) loop %d of %d%s")
 788                      dir keyLength blockLength i
 789                      rijndael-monte-carlo-loop
 790                      (if (> rijndael-monte-carlo-limit 1)
 791                          (format " iteration %d of %d" j
 792                                  rijndael-monte-carlo-limit)
 793                        "")))
 794         (setq inBlock (copy-sequence outBlock))
 795         (if (eq dir 'encrypt)
 796             (rijndael-block-encrypt outBlock keyInst 'ecb blockLength)
 797           (rijndael-block-decrypt outBlock keyInst 'ecb blockLength))
 798         (setq j (1+ j)))
 799       (insert (if (eq dir 'encrypt) "CT=" "PT=")
 800               (rijndael-bitstring-to-hexstring outBlock) "\n")
 801       (cond ((eq keyLength 128)
 802              (setq j 0)
 803              (while (< j (/ 128 8))
 804                (aset binKey j (logxor (aref binKey j)
 805                                       (aref
 806                                        (rijndael-bitstring-to-vector outBlock)
 807                                        j)))
 808                (setq j (1+ j))))
 809             ((eq keyLength 192)
 810              (setq j 0)
 811              (while (< j (/ 64 8))
 812                (aset binKey j (logxor (aref binKey j)
 813                                       (aref
 814                                        (rijndael-bitstring-to-vector inBlock)
 815                                        (+ j (/ 64 8)))))
 816                (setq j (1+ j)))
 817              (setq j 0)
 818              (while (< j (/ 128 8))
 819                (aset binKey (+ j (/ 64 8))
 820                      (logxor (aref binKey (+ j (/ 64 8)))
 821                              (aref (rijndael-bitstring-to-vector outBlock) j)))
 822                (setq j (1+ j))))
 823             ((eq keyLength 256)
 824              (setq j 0)
 825              (while (< j (/ 128 8))
 826                (aset binKey j (logxor (aref binKey j)
 827                                       (aref
 828                                        (rijndael-bitstring-to-vector inBlock)
 829                                        j)))
 830                (setq j (1+ j)))
 831              (setq j 0)
 832              (while (< j (/ 128 8))
 833                (aset binKey (+ j (/ 128 8))
 834                      (logxor (aref binKey j)
 835                              (aref
 836                               (rijndael-bitstring-to-vector outBlock)
 837                               j)))
 838                (setq j (1+ j)))))
 839       (setq i (1+ i)))))
 840
 841 (provide 'rijndael)
 842
 843 ;; rijndael.el ends here