1.12 MISTY算法
MISTY是日本Mitsubishi电气公司的Mitsuru Matsui于1997年提出的一个分组密码，它采用递归结构，整个结构分成了三个等级，但加密算法的主框架仍采用平衡Feistel结构。MISTY加密算法的分组长度为64比特，密钥长度为128比特，迭代层数是可变的，但要求必须是4的整数倍。MISTY加密算法采用能有效抵御差分攻击和线性攻击的理论，具有在各种硬件平台（如ATM网络）和软件环境（如IC卡）中高速运行的能力，是第一个被证明能有效抵御差分攻击和线性攻击的实用分组密码。
MISTY加密算法的递归结构如下：第一级是n层的主框架，每一层包含加乱（如按位异或操作⊕、按位或操作∪、按位与操作∩）、左右两边异或，以及层函数FO变换。第一级的层函数FO是一个由加乱（⊕）、左右两边异或和子函数FI变换构成的三层迭代过程，这个过程就是第二级。第二级的层函数FI又是一个由加乱（⊕）、左右两边扩展和压缩后异或，以及表 S9和 S7代替构成的，这个过程是第三级。从第一级到第三级，虽然结构逐渐简单，但运算次数比较繁复，每层要加乱9次（1次∪运算、1次∩运算、7次⊕运算），代替9次（6次S9代替、3次S7代替），左右两半进行16次⊕运算，但是这种递归结构能通过对简单函数的分析非常容易地估计出算法的安全程度。
MISTY加密算法有MISTY1加密算法和MISTY2加密算法两种，它们具有非常相似的结构。对于相同层数的MISTY1加密算法和MISTY2加密算法，如果不考虑并行运算，则二者在总的算法复杂度上是完全相同的；如果考虑并行计算，则二者的运行时间就有差异，因为MISTY1加密算法能同时执行2个FI函数，而MISTY2加密算法能同时执行4个FI函数。
MISTY1加密算法和MISTY2加密算法的结构如图1.12.1所示。
图1.12.1（a）和图1.12.1（b）分别给出了MISTY1加密算法和MISTY2加密算法的结构，在递归结构中的第一级，64比特的输入被均分成32比特的左右两个部分，经过异或运算，以及层函数FOi（1≤i≤n）和FLi（1≤i≤n+2）转换成64比特密文。FOi使用64比特的子密钥KOi和48比特的子密钥KIi, FLi使用32比特的子密钥KLi。
图1.12.1 MISTY1加密算法和MISTY2加密算法的结构
图1.12.2（a）是层函数FOi的结构，即递归结构中的第二级。32比特的输入被均分成16比特的左右两部分，经过⊕运算，以及层函数FIij（1≤j≤3）转换成32比特的输出。图中的KOij（1≤j≤4）和KIij（1≤j≤3）分别是子密钥KOi和KIi的从左边数的第j个16比特。
图1.12.2（b）是层函数FIij的结构，即递归结构中的第三级，16比特的输入被分成9比特和7比特的左右两部分，经过⊕运算、一个长度为27的S7代替和一个长度为29的S9代替后转换成16比特的输出。在第一和第三个⊕运算中，右边的7比特在高位添加2个“0”扩展成9比特，在第二个⊕运算中，右边的9比特去掉高位的2比特后被截短成7比特。图1.12.2（b）中的KIij1和KIij2分别是子密钥KIij的左边7比特和右边9比特。
图1.12.2 MISTY1加密算法和MISTY2加密算法层函数的结构
图1.12.3是层函数FLi的结构。32比特输入被均分成16比特的左右两部分，经过⊕操作、与操作（∩）、或操作（∪）后变成32比特的输出。KLij（1≤j≤2）是KLi从左边数第j个16比特。
图1.12.3 层函数FLi结构
MISTY的子密钥生成过程利用了前面介绍的层函数FI，记Ki为输入密钥K的从左边数的第i个16比特，分别以Ki作为层函数FIi的输入，以Ki+1作为层函数FI的密钥，FIi的16比特输出记为Ri，其中1≤i≤8，则子密钥与Ki、Ri的对应关系如下。
KOi1KOi2KOi3KOi4KIi1KIi2KIi3KLi1KLi2
KiKi+2Ki+7Ki+4Ri+5Ri+1Ri+3K(i+1)/2R(i+1)/2+6（i为奇数）
Ri/2+2Ki/2+4（i为偶数）
上面下角中的加法表示模8加。
MISTY加密算法中使用的S7和S9如下：
S7：
27 50 51 90 59 16 23 84 91 26 114 115 107 44 102 73 31 36 19 108 55 46 63 74 93 15 64 86 37 81 28 4 11 70 32 13 123 53 68 66 43 30 65 20 75 121 21 111 14 85 9 54 116 12 103 83 40 10 126 56 2 7 96 41 25 18 101 47 48 57 8 104 95 120 42 76 100 69 117 61 89 72 3 87 124 79 98 60 29 33 94 39 106 112 77 58 1 109 110 99 24 119 35 5 38 118 0 49 45 122 127 97 80 34 17 6 71 22 82 78 113 62 105 67 52 92 88 125
S9：
451 203 339 415 483 233 251 53 385 185 279 491 307 9 45 211 199 330 55 126 235 356 403 472 163 286 85 44 29 418 355 280 331 338 466 15 43 48 314 229 273 312 398 99 227 200 500 27 1 157 248 416 365 499 28 326 125 209 130 490 387 301 244 414 467 221 482 296 480 236 89 145 17 303 38 220 176 396 271 503 231 364 182 249 216 337 257 332 259 184 340 299 430 23 113 12 71 88 127 420 308 297 132 349 413 434 419 72 124 81 458 35 317 423 357 59 66 218 402 206 193 107 159 497 300 388 250 406 481 361 381 49 384 266 148 474 390 318 284 96 373 463 103 281 101 104 153 336 8 7 380 183 36 25 222 295 219 228 425 82 265 144 412 449 40 435 309 362 374 223 485 392 197 366 478 433 195 479 54 238 494 240 147 73 154 438 105 129 293 11 94 180 329 455 372 62 315 439 142 454 174 16 149 495 78 242 509 133 253 246 160 367 131 138 342 155 316 263 359 152 464 489 3 510 189 290 137 210 399 18 51 106 322 237 368 283 226 335 344 305 327 93 275 461 121 353 421 377 158 436 204 34 306 26 232 4 391 493 407 57 447 471 39 395 198 156 208 334 108 52 498 110 202 37 186 401 254 19 262 47 429 370 475 192 267 470 245 492 269 118 276 427 117 268 484 345 84 287 75 196 446 247 41 164 14 496 119 77 378 134 139 179 369 191 270 260 151 347 352 360 215 187 102 462 252 146 453 111 22 74 161 313 175 241 400 10 426 323 379 86 397 358 212 507 333 404 410 135 504 291 167 440 321 60 505 320 42 341 282 417 408 213 294 431 97 302 343 476 114 394 170 150 277 239 69 123 141 325 83 95 376 178 46 32 469 63 457 487 428 68 56 20 177 363 171 181 90 386 456 468 24 375 100 207 109 256 409 304 346 5 288 443 445 224 79 214 319 452 298 21 6 255 411 166 67 136 80 351 488 289 115 382 188 194 201 371 393 501 116 460 486 424 405 31 65 13 442 50 61 465 128 168 87 441 354 328 217 261 98 122 33 511 274 264 448 169 285 432 422 205 243 92 258 91 473 324 502 173 165 58 459 310 383 70 225 30 477 230 311 506 389 140 143 64 437 190 120 0 172 272 350 292 2 444 162 234 112 508 278 348 76 450