分享
 
 
 

RFC2994 - A Description of the MISTY1 Encryption Algorithm

王朝other·作者佚名  2008-05-31
窄屏简体版  字體: |||超大  

Network Working Group H. Ohta

Request for Comments: 2994 M. Matsui

Category: Informational Mitsubishi Electric Corporation

November 2000

A Description of the MISTY1 Encryption Algorithm

Status of this Memo

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 Notice

Copyright (C) The Internet Society (2000). All Rights Reserved.

Abstract

This document describes a secret-key cryptosystem MISTY1, which is

block cipher with a 128-bit key, a 64-bit block and a variable number

of rounds. It documents the algorithm description including key

scheduling part and data randomizing part.

1. IntrodUCtion

This document describes a secret-key cryptosystem MISTY1, which is

block cipher with a 128-bit key, a 64-bit block and a variable number

of rounds. It is designed on the basis of the theory of provable

security against differential and linear cryptanalysis, and moreover

it realizes high-speed encryption on hardware platforms as well as on

software environments. As the result of weighing strength and speed,

8-rounds of MISTY1 is recommended and used in most cases.

Our implementation shows that MISTY1 with eight rounds can encrypt a

data stream in CBC mode at a speed of 57Mbps and 40Mbps on Pentium

II/266MHz and PA-7200/120MHz, respectively. For its hardware

performance, we have produced a prototype LSI by a process of 0.8-

micron CMOS gate-array and confirmed a speed of 512Mbps.

2. Algorithm Description

Algorithm [1] could be divided into two parts, namely "key scheduling

part" and "data randomizing part". Key scheduling part takes a 128-

bit input key and produces a 128-bit eXPanded key. Data randomizing

part takes a 64-bit input data and mixes it, namely encryption. If

data randomizing part is processed in reverse order, mixed data is

transformed to input data, namely decryption.

2.1 Terminology

Some operators are used in this document to describe the algorithm.

The operator `+' indicates two's complement addition. The operator

`*' indicates multiplication. The operator `/' yields the quotient,

and the operator `%' yields the remainder from the division. The

operator `&' indicates bitwise AND operation. The operator `'

indicates bitwise inclusive OR operation. The operator `^' indicates

bitwise exclusive OR operation. The operator `<<' indicates bitwise

left shift operation. The operator `>>' indicates bitwise right

shift operation.

2.2 Key Scheduling Part

Key scheduling part consists of the following operations.

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 is an input key, and each element of K, namely K[i], holds an 8-bit

of the key, respectively. EK denotes an expanded key, and each

element of EK, namely EK[i], holds a 16-bit of the expanded key.

Input data of K[0], ..., K[15] are copied to EK[0], ..., EK[7].

Expanded key is produced from EK[0], ..., EK[7] by using function FI,

and stored in EK[8], ..., EK[15]. Function FI is described in the

following section.

2.3 Data Randomizing Part

Data randomizing part uses two kinds of function, which are called

function FO and function FL. Function FO calls another function,

namely FI. The key expansion part also uses function FI. Function

FI uses two S-boxes, namely S7, S9. Each function is described as

follows.

Function FO takes two parameters. One is a 32-bit width input data,

namely FO_IN. The other is an index of EK, namely k. And FO returns

a 32-bit width data, namely 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.

Function FI takes two parameters. One is a 16-bit width input data,

namely FI_IN. The other is a part of EK, namely FI_KEY, which is

also 16-bit width. And FI returns a 16-bit width data, namely

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.

S7TABLE and S9TABLE denote the S-boxes S7 and S9 respectively in

terms of look up table notation. Here are the description of S7TABLE

and S9TABLE in hexadecimal notation.

S7TABLE:

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

S9TABLE:

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

Function FL takes two parameters. One is a 32-bit data, namely

FL_IN. The other is an index of EK, namely k. And FL returns a 32-

bit width data, namely 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.

When the algorithm is used for decryption, function FLINV is used

instead of function 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.

In most cases, data randomizing part consists of 8 "rounds". Round

contains the call of function FO. Additionally, even-number round

includes the calls of function FL. After the final round, FLs are

called again. The detail description is as follows.

64-bit plaintext P is divided into the leftmost 32-bit D0 and the

rightmost 32-bit D1.

// 0 round

D0 = FL(D0, 0);

D1 = FL(D1, 1);

D1 = D1 ^ FO(D0, 0);

// 1 round

D0 = D0 ^ FO(D1, 1);

// 2 round

D0 = FL(D0, 2);

D1 = FL(D1, 3);

D1 = D1 ^ FO(D0, 2);

// 3 round

D0 = D0 ^ FO(D1, 3);

// 4 round

D0 = FL(D0, 4);

D1 = FL(D1, 5);

D1 = D1 ^ FO(D0, 4);

// 5 round

D0 = D0 ^ FO(D1, 5);

// 6 round

D0 = FL(D0, 6);

D1 = FL(D1, 7);

D1 = D1 ^ FO(D0, 6);

// 7 round

D0 = D0 ^ FO(D1, 7);

// final

D0 = FL(D0, 8);

D1 = FL(D1, 9);

64-bit ciphertext C is constructed from D0 and D1 as following

operation.

C = (D1<<32) D0;

When data randomizing part is used as decrypting operation, it should

be executed in reverse order. The detail description is as follows.

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. Object Identifier

The Object Identifier for MISTY1 in Cipher Block Chaining (CBC) mode

is as follows:

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 needs Initialization Vector (IV) as like as other

algorithms, such as DES-CBC, DES-EDE3-CBC and so on. To determine

the value of IV, MISTY1-CBC takes parameter as:

MISTY1-CBC Parameter ::= IV

where IV ::= OCTET STRING -- 8 octets.

When this Object Identifier is used, plaintext is padded before

encrypt it. At least 1 padding octet is appended at the end of the

plaintext to make the length of the plaintext to the multiple of 8

octets. The value of these octets is as same as the number of

appended octets. (e.g., If 5 octets are needed to pad, the value is

0x05.)

4. Security Considerations

The algorithm, which is described in this document, is designed in

consideration of the theory of provable security against differential

cryptanalysis and linear cryptanalysis [2][3][4]. According to the

recent result, when the algorithm consists of 8 rounds, both

differential characteristic probability and liner characteristic

probability are 2^-140. For reference, probabilities of DES are 2^-

62 and 2^-46, respectively.

5. Legal Issues

The algorithm description is applied for a patent in several

countries as PCT/JP96/02154. However, the algorithm is freely

available for academic (non-profit) use. Additionally, the algorithm

can be used for commercial use without paying the patent fee if you

contract with Mitsubishi Electric Corporation. For more information,

please contact at MISTY@isl.melco.co.jp.

6. References

[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. Authors' Addresses

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

Appendix A. Example Data of MISTY1

Here is an example ciphertext of MISTY1 when the key and the

plaintext are set as following value.

Key: 00 11 22 33 44 55 66 77 88 99 aa bb cc dd ee ff

Plaintext: 01 23 45 67 89 ab cd ef fe dc ba 98 76 54 32 10

Ciphertext: 8b 1d a5 f5 6a b3 d0 7c 04 b6 82 40 b1 3b e9 5d

In the above example, because the plaintext has a length of 128-bit,

MISTY1 is used two times to each 64-bit, namely ECB mode.

Following example is ciphertext of MISTY1 in CBC mode.

Key: 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

Plaintext: 01 23 45 67 89 ab cd ef fe dc ba 98 76 54 32 10

Ciphertext: 46 1c 1e 87 9c 18 c2 7f b9 ad f2 d8 0c 89 03 1f

Full Copyright Statement

Copyright (C) The Internet Society (2000). 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.

Acknowledgement

Funding for the RFCEditor function is currently provided by the

Internet Society.

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有