组织：中国互动出版网（http://www.china-pub.com/）
RFC文档中文翻译计划(http://www.china-pub.com/compters/emook/aboutemook.htm）
E-mail：ouyang@china-pub.com
译者：安智平（fivestar   anzp@xanet.edu.cn）
译文发布时间：2001－4－12
版权：本翻译文档可以用于非商业用途自由转载，但必须保留本文档的翻译及组织信息。

Network Working Group                                            H. Ohta
Request for Comments: 2994                                     M. Matsui
Category: Informational                  Mitsubishi Electric Corporation
                                                           November 2000

RFC2994 MISTY1加密算法描述


本备忘录状态
   This memo provides information for the Internet community.  It does
   not specify an Internet standard of any kind.  Distribution of this
   memo is unlimited.
版权声明
   Copyright (C) The Internet Society (1999).  All Rights Reserved.
摘要
本文档描述了一个密钥加密系统MISTY1，它用128位密钥对64位数据进行不确定轮回的加密。文档分为两部分：密钥产生部分和数据随机化部分。

目录
1 简介 1
2 算法描述 2
2．1 名词 2
2．2 密钥产生部分 2
2．3 数据随机化部分 2
3 对象标识符 6
4 安全问题 7
5 法律问题 7
6 参考资料 7
7 作者联系方法 8
附录A － MISTY1加密数据举例: 8
版权说明 8
鸣谢 9

1 简介
本文档描述了一个密钥加密系统MISTY1，它用128位密钥对64位数据进行不确定轮回的加密。它在设计时就采用了经证实可以抵抗密码微分分析和线性分析的安全理论，而且它实现了在硬件环境和软件环境下都比较高的加密速度。考虑加密强度和速度的原因，建议在绝大多数加密时，使用8个轮回。
我们的实现表明MISTY1以CBC模式，在PentiumII/266MHz 和 PA-7200/120MHz上分别能以57Mbps 和 40Mbps的速度对数据进行8个轮回的加密。我们用0.8微米CMOS阵列实现了一个大规模集成电路原做了一个原型，加密速度达到了512Mbps。
2 算法描述
算法可以分为两部分，一部分是密钥产生部分，另一百分是数据随机化部分。密钥产生部分根据128位的输入密钥，产生128位的扩展密钥。数据随机化部分输入64位的数据进行混合，也就是所谓的加密。
2．1 名词
在本文档中为了描述算法，使用了一些运算符。＋表示两个元素的相加，*表示乘。/表示取相除的商，％表示取余数。&表示按位进行与运算。|表示按位进行或运算。^表示按位进行异或运算。<<表示逐位左移运算，>>表示逐位右移运算。
2．2 密钥产生部分
密钥产生部分包括以下操作。
for i = 0, ..., 7 do
       EK[i] = K[i*2]*256 + K[i*2+1];
   for i = 0, ..., 7 do
   begin
       EK[i+ 8] = FI(EK[i], EK[(i+1)%8]);
       EK[i+16] = EK[i+8] & 0x1ff;
       EK[i+24] = EK[i+8] >> 9;
   end
K为输入密钥，K[i]代表K的一个元素，分别包含了输入密钥的8位。EK表示扩展密钥，同样EK[i]代表EK的一个元素，分别包含了扩展密钥的16位。输入数据K[0]， ...， K[15]被拷贝到EK[0]， ...， EK[7]。扩展密钥由函数FI从EK[0]， ...， EK[7]中产生，并存储在EK[8]， ...， EK[15]中。函数FI在下面进行描述。
2．3 数据随机化部分
数字随机化部分使用了两种函数，FO和FL。函数FO调用函数FI。密钥扩展部分也使用函数FI。FI函数使用两个S盒，S7和S9。下面对每个函数进行描述。
函数FO有两个参数。一个是FO_IN，是32位的输入数据。另外一个是EK的下标k。FO返回一个32位的数据FO_OUT。
FO(FO_IN, k)
   begin
       var t0, t1 as 16-bit integer;
       t0 = FO_IN >> 16;
       t1 = FO_IN & 0xffff;
       t0 = t0 ^ EK[k];
       t0 = FI(t0, EK[(k+5)%8+8]);
       t0 = t0 ^ t1;
       t1 = t1 ^ EK[(k+2)%8];
       t1 = FI(t1, EK[(k+1)%8+8]);
       t1 = t1 ^ t0;
       t0 = t0 ^ EK[(k+7)%8];
       t0 = FI(t0, EK[(k+3)%8+8]);
       t0 = t0 ^ t1;
       t1 = t1 ^ EK[(k+4)%8];
       FO_OUT = (t1<<16) | t0;
       return FO_OUT;
   end.
函数FI有两个参数。一个是FI_IN，是16位的输入数据。另外一个是FI_KEY，是EK的一部分，也是16位。FI返回一个32位的数据FI_OUT。
FI(FI_IN, FI_KEY)
   begin
       var d9 as 9-bit integer;
       var d7 as 7-bit integer;
       d9 = FI_IN >> 7;
       d7 = FI_IN & 0x7f;
       d9 = S9TABLE[d9] ^ d7;
       d7 = S7TABLE[d7] ^ d9;
       ( d7 = d7 & 0x7f; )
       d7 = d7 ^ (FI_KEY >> 9);
       d9 = d9 ^ (FI_KEY & 0x1ff);
       d9 = S9TABLE[d9] ^ d7;
       FI_OUT = (d7<<9) | d9;
       return FI_OUT;
   end.
表S7和表S9分别为S盒子S7和S9的查找表。下面是表S7和表9的16进制形式。
表S7:
        0  1  2  3  4  5  6  7  8  9  a  b  c  d  e  f
   00: 1b 32 33 5a 3b 10 17 54 5b 1a 72 73 6b 2c 66 49
   10: 1f 24 13 6c 37 2e 3f 4a 5d 0f 40 56 25 51 1c 04
   20: 0b 46 20 0d 7b 35 44 42 2b 1e 41 14 4b 79 15 6f
   30: 0e 55 09 36 74 0c 67 53 28 0a 7e 38 02 07 60 29
   40: 19 12 65 2f 30 39 08 68 5f 78 2a 4c 64 45 75 3d
   50: 59 48 03 57 7c 4f 62 3c 1d 21 5e 27 6a 70 4d 3a
   60: 01 6d 6e 63 18 77 23 05 26 76 00 31 2d 7a 7f 61
   70: 50 22 11 06 47 16 52 4e 71 3e 69 43 34 5c 58 7d
表S9
0    1   2   3   4   5   6   7   8   9   a   b   c   d   e   f
   000: 1c3 0cb 153 19f 1e3 0e9 0fb 035 181 0b9 117 1eb 133 009 02d 0d3
   010: 0c7 14a 037 07e 0eb 164 193 1d8 0a3 11e 055 02c 01d 1a2 163 118
   020: 14b 152 1d2 00f 02b 030 13a 0e5 111 138 18e 063 0e3 0c8 1f4 01b
   030: 001 09d 0f8 1a0 16d 1f3 01c 146 07d 0d1 082 1ea 183 12d 0f4 19e
   040: 1d3 0dd 1e2 128 1e0 0ec 059 091 011 12f 026 0dc 0b0 18c 10f 1f7
   050: 0e7 16c 0b6 0f9 0d8 151 101 14c 103 0b8 154 12b 1ae 017 071 00c
   060: 047 058 07f 1a4 134 129 084 15d 19d 1b2 1a3 048 07c 051 1ca 023
   070: 13d 1a7 165 03b 042 0da 192 0ce 0c1 06b 09f 1f1 12c 184 0fa 196
   080: 1e1 169 17d 031 180 10a 094 1da 186 13e 11c 060 175 1cf 067 119
   090: 065 068 099 150 008 007 17c 0b7 024 019 0de 127 0db 0e4 1a9 052
   0a0: 109 090 19c 1c1 028 1b3 135 16a 176 0df 1e5 188 0c5 16e 1de 1b1
   0b0: 0c3 1df 036 0ee 1ee 0f0 093 049 09a 1b6 069 081 125 00b 05e 0b4
   0c0: 149 1c7 174 03e 13b 1b7 08e 1c6 0ae 010 095 1ef 04e 0f2 1fd 085
   0d0: 0fd 0f6 0a0 16f 083 08a 156 09b 13c 107 167 098 1d0 1e9 003 1fe
   0e0: 0bd 122 089 0d2 18f 012 033 06a 142 0ed 170 11b 0e2 14f 158 131
   0f0: 147 05d 113 1cd 079 161 1a5 179 09e 1b4 0cc 022 132 01a 0e8 004
   100: 187 1ed 197 039 1bf 1d7 027 18b 0c6 09c 0d0 14e 06c 034 1f2 06e
   110: 0ca 025 0ba 191 0fe 013 106 02f 1ad 172 1db 0c0 10b 1d6 0f5 1ec
   120: 10d 076 114 1ab 075 10c 1e4 159 054 11f 04b 0c4 1be 0f7 029 0a4
   130: 00e 1f0 077 04d 17a 086 08b 0b3 171 0bf 10e 104 097 15b 160 168
   140: 0d7 0bb 066 1ce 0fc 092 1c5 06f 016 04a 0a1 139 0af 0f1 190 00a
   150: 1aa 143 17b 056 18d 166 0d4 1fb 14d 194 19a 087 1f8 123 0a7 1b8
   160: 141 03c 1f9 140 02a 155 11a 1a1 198 0d5 126 1af 061 12e 157 1dc
   170: 072 18a 0aa 096 115 0ef 045 07b 08d 145 053 05f 178 0b2 02e 020
   180: 1d5 03f 1c9 1e7 1ac 044 038 014 0b1 16b 0ab 0b5 05a 182 1c8 1d4
   190: 018 177 064 0cf 06d 100 199 130 15a 005 120 1bb 1bd 0e0 04f 0d6
   1a0: 13f 1c4 12a 015 006 0ff 19b 0a6 043 088 050 15f 1e8 121 073 17e
   1b0: 0bc 0c2 0c9 173 189 1f5 074 1cc 1e6 1a8 195 01f 041 00d 1ba 032
   1c0: 03d 1d1 080 0a8 057 1b9 162 148 0d9 105 062 07a 021 1ff 112 108
   1d0: 1c0 0a9 11d 1b0 1a6 0cd 0f3 05c 102 05b 1d9 144 1f6 0ad 0a5 03a
   1e0: 1cb 136 17f 046 0e1 01e 1dd 0e6 137 1fa 185 08c 08f 040 1b5 0be
   1f0: 078 000 0ac 110 15e 124 002 1bc 0a2 0ea 070 1fc 116 15c 04c 1c2

函数FL有两个参数。一个是FL_IN，是32位的输入数据。另外一个是EK的下标k。FI返回一个32位的数据FL_OUT。
FL(FL_IN, k)
   begin
       var d0, d1 as 16-bit integer;
       d0 = FL_IN >> 16;
       d1 = FL_IN & 0xffff;
       if (k is an even number) then
           d1 = d1 ^ (d0 & EK[k/2]);
           d0 = d0 ^ (d1 | EK[(k/2+6)%8+8]);
       else
           d1 = d1 ^ (d0 & EK[((k-1)/2+2)%8+8]);
           d0 = d0 ^ (d1 | EK[((k-1)/2+4)%8]);
       endif
       FL_OUT = (d0<<16) | d1;
       return FL_OUT;
   end.
当用来解密时，用函数FLINV 代替函数FL。
FLINV(FL_IN, k)
   begin
       var d0, d1 as 16-bit integer;
       d0 = FL_IN >> 16;
       d1 = FL_IN & 0xffff;
       if (k is an even number) then
           d0 = d0 ^ (d1 | EK[(k/2+6)%8+8]);
           d1 = d1 ^ (d0 & EK[k/2]);
       else
           d0 = d0 ^ (d1 | EK[((k-1)/2+4)%8]);
           d1 = d1 ^ (d0 & EK[((k-1)/2+2)%8+8]);
       endif
       FL_OUT = (d0<<16) | d1;
       return FL_OUT;
   end.
大部分情况下，数据随机化部分包括8个轮回。轮回包括函数FO的调用。另外，偶数的轮回包括函数FL的调用。在最后一个轮回后，FL被再次调用。详细说明如下。
64位的明文被分为最左边的32为D0和最右边的32位D1。
   // 第0 轮回
   D0 = FL(D0, 0);
   D1 = FL(D1, 1);
   D1 = D1 ^ FO(D0, 0);
   //第1 轮回
   D0 = D0 ^ FO(D1, 1);
   //第2 轮回
   D0 = FL(D0, 2);
   D1 = FL(D1, 3);
   D1 = D1 ^ FO(D0, 2);
   //第3 轮回
   D0 = D0 ^ FO(D1, 3);
   //第4轮回
   D0 = FL(D0, 4);
   D1 = FL(D1, 5);
   D1 = D1 ^ FO(D0, 4);
   //第5轮回
   D0 = D0 ^ FO(D1, 5);
   //第6轮回
   D0 = FL(D0, 6);
   D1 = FL(D1, 7);
   D1 = D1 ^ FO(D0, 6);
   //第7轮回
   D0 = D0 ^ FO(D1, 7);
   // 最后
   D0 = FL(D0, 8);
D1 = FL(D1, 9);
64位的密文由D0和D1按照以下操作得到。
  C = (D1<<32) | D0;
当数据随机化部分用来进行解密，应该按照相反的顺序来执行。详细描述如下。
   D0 = C & 0xffffffff;
   D1 = C >> 32;
   D0 = FLINV(D0, 8);
   D1 = FLINV(D1, 9);
   D0 = D0 ^ FO(D1, 7);
   D1 = D1 ^ FO(D0, 6);
   D0 = FLINV(D0, 6);
   D1 = FLINV(D1, 7);
   D0 = D0 ^ FO(D1, 5);
   D1 = D1 ^ FO(D0, 4);
   D0 = FLINV(D0, 4);
   D1 = FLINV(D1, 5);
   D0 = D0 ^ FO(D1, 3);
   D1 = D1 ^ FO(D0, 2);
   D0 = FLINV(D0, 2);
   D1 = FLINV(D1, 3);
   D0 = D0 ^ FO(D1, 1);
   D1 = D1 ^ FO(D0, 0);
   D0 = FLINV(D0, 0);
   D1 = FLINV(D1, 1);
   P = (D0<<32) | D1;
3 对象标识符
MISTY1对象标识符的CBC模式如下：
MISTY1-CBC OBJECT IDENTIFIER ::=
     {iso(1) member-body(2) jisc(392)
      mitsubishi-electric-corporation(200011) isl(61) security(1)
      algorithm(1) symmetric-encryption-algorithm(1) misty1-cbc(1)}
MISTY1-CBC跟其它算法一样，需要初始向量IV，这样的算法还有DES-CBC，ES-EDE3-CBC，等等。为了得到IV的值，MISTY1-CBC使用一下参数：
MISTY1-CBC Parameter ::= IV
（V ::= OCTET STRING -- 8 octets）
当这种对象标识符被使用时，明文在加密之前要进行填充。至少在明文后面填充一个字节，使其长度为8字节的整倍数。这些字节的值就是所填充的字节数。（例如，如果填充了5个字节，那么这个值就是0x05）；
4 安全问题
本文档中讨论的加密算法，在设计时就采用了经证实可以抵抗密码微分分析和线性分析的安全理论。根据最新结果，如果加密轮回为8，微分特征可能性和线性特征可能性都可以达到2的140次方。而DES算法的微分特征可能性和线性特征可能性可能性本别为2的62次方和2的46次方。
5 法律问题
这个加密算法已经在好几个国家申请了专利，专利号PCT/JP96/02154。但是，可以免费地作为研究（不获利）使用。而且，如果跟Mitsubishi电子公司有合同，你也可以免费地在商业中使用这个算法。如果需要获得更多的信息，请与MISTY@isl.melco.co.jp联系。
6 参考资料
   [1]  M. Matsui, "New Block Encryption Algorithm MISTY", Fast Software
        Encryption - 4th International Workshop (FSE'97), LNCS 1267,
        Springer Verlag, 1997, pp.54-68

   [2]  K. Nyberg and L.R. Knudsen, "Provable Security Against a
        Differential Attack", Journal of Cryptology, Vol.8, No.1, 1995,
        pp. 27-37

   [3]  K. Nyberg, "Linear Approximation of Block Ciphers", Advances in
        Cryptology - Eurocrypt'94, LNCS 950, Springer Verlag, 1995,
        pp.439-444

   [4]  M. Matsui, "New Structure of Block Ciphers with Provable
        Security Against Differential and Linear Cryptanalysis", Fast
        Software Encryption - Third International Workshop, LNCS 1039,
        Springer Verlag, 1996, pp.205-218
7 作者联系方法
Hidenori Ohta
   Mitsubishi Electric Corporation, Information Technology R&D Center
   5-1-1 Ofuna, Kamakura, Kanagawa 247-8501, Japan

   Phone: +81-467-41-2183
   Fax:   +81-467-41-2185
   EMail: hidenori@iss.isl.melco.co.jp


   Mitsuru Matsui
   Mitsubishi Electric Corporation, Information Technology R&D Center
   5-1-1 Ofuna, Kamakura, Kanagawa 247-8501, Japan

   Phone: +81-467-41-2181
   Fax:   +81-467-41-2185
   EMail: matsui@iss.isl.melco.co.jp
附录A － MISTY1加密数据举例:

下面是一个密钥，明文，密文的例子：
密钥:  00 11 22 33 44 55 66 77 88 99 aa bb cc dd ee ff
明文:  01 23 45 67 89 ab cd ef fe dc ba 98 76 54 32 10
密文:  8b 1d a5 f5 6a b3 d0 7c 04 b6 82 40 b1 3b e9 5d
在上面的例子中，明文的长度为128位，对于每个64位使用了两次MISTY1，称为ECB模式。
下面的例子是 CBC模式：
密钥:  00 11 22 33 44 55 66 77 88 99 aa bb cc dd ee ff
IV:    01 02 03 04 05 06 07 08
明文:  01 23 45 67 89 ab cd ef fe dc ba 98 76 54 32 10
密文:  46 1c 1e 87 9c 18 c2 7f b9 ad f2 d8 0c 89 03 1f
版权说明
   Copyright (C) The Internet Society (1999).  All Rights Reserved.

   This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works.  However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than   English.

   The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns.

   This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION   HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF   MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
鸣谢
感谢Internet协会给予RFC编辑部门的资金。
RFC2994: A Description of the MISTY1 Encryption Algorithm            RFC2994  MISTY1加密算法描述




9
RFC中文翻译计划