RFC2994 MISTY1加密算法描述

本备忘录状态
ThismemoprovidesinformationfortheInternetcommunity.Itdoes
notspecifyanInternetstandardofanykind.Distributionofthis
memoisunlimited.
版权声明
Copyright(C)TheInternetSociety(1999).AllRightsReserved.
摘要
本文档描述了一个密钥加密系统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密钥产生部分
密钥产生部分包括以下操作。
fori=0,...,7do
EK[i]=K[i*2]*256+K[i*2+1];
fori=0,...,7do
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
vart0,t1as16-bitinteger;
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;
returnFO_OUT;
end.
函数FI有两个参数。一个是FI_IN，是16位的输入数据。另外一个是FI_KEY，是EK的一部分，也是16位。FI返回一个32位的数据FI_OUT。
FI(FI_IN,FI_KEY)
begin
vard9as9-bitinteger;
vard7as7-bitinteger;
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;
returnFI_OUT;
end.
表S7和表S9分别为S盒子S7和S9的查找表。下面是表S7和表9的16进制形式。
表S7:
0123456789abcdef
00:1b32335a3b1017545b1a72736b2c6649
10:1f24136c372e3f4a5d0f405625511c04
20:0b46200d7b3544422b1e41144b79156f
30:0e550936740c6753280a7e3802076029
40:1912652f303908685f782a4c6445753d
50:594803577c4f623c1d215e276a704d3a
60:016d6e6318772305267600312d7a7f61
70:502211064716524e713e6943345c587d
表S9
0123456789abcdef
000:1c30cb15319f1e30e90fb0351810b91171eb13300902d0d3
010:0c714a03707e0eb1641931d80a311e05502c01d1a2163118
020:14b1521d200f02b03013a0e511113818e0630e30c81f401b
030:00109d0f81a016d1f301c14607d0d10821ea18312d0f419e
040:1d30dd1e21281e00ec05909101112f0260dc0b018c10f1f7
050:0e716c0b60f90d815110114c1030b815412b1ae01707100c
060:04705807f1a413412908415d19d1b21a304807c0511ca023
070:13d1a716503b0420da1920ce0c106b09f1f112c1840fa196
080:1e116917d03118010a0941da18613e11c0601751cf067119
090:06506809915000800717c0b70240190de1270db0e41a9052
0a0:10909019c1c10281b313516a1760df1e51880c516e1de1b1
0b0:0c31df0360ee1ee0f009304909a1b606908112500b05e0b4
0c0:1491c717403e13b1b708e1c60ae0100951ef04e0f21fd085
0d0:0fd0f60a016f08308a15609b13c1071670981d01e90031fe
0e0:0bd1220890d218f01203306a1420ed17011b0e214f158131
0f0:14705d1131cd0791611a517909e1b40cc02213201a0e8004
100:1871ed1970391bf1d702718b0c609c0d014e06c0341f206e
110:0ca0250ba1910fe01310602f1ad1721db0c010b1d60f51ec
120:10d0761141ab07510c1e415905411f04b0c41be0f70290a4
130:00e1f007704d17a08608b0b31710bf10e10409715b160168
140:0d70bb0661ce0fc0921c506f01604a0a11390af0f119000a
150:1aa14317b05618d1660d41fb14d19419a0871f81230a71b8
160:14103c1f914002a15511a1a11980d51261af06112e1571dc
170:07218a0aa0961150ef04507b08d14505305f1780b202e020
180:1d503f1c91e71ac0440380140b116b0ab0b505a1821c81d4
190:0181770640cf06d10019913015a0051201bb1bd0e004f0d6
1a0:13f1c412a0150060ff19b0a604308805015f1e812107317e
1b0:0bc0c20c91731891f50741cc1e61a819501f04100d1ba032
1c0:03d1d10800a80571b91621480d910506207a0211ff112108
1d0:1c00a911d1b01a60cd0f305c10205b1d91441f60ad0a503a
1e0:1cb13617f0460e101e1dd0e61371fa18508c08f0401b50be
1f0:0780000ac11015e1240021bc0a20ea0701fc11615c04c1c2
函数FL有两个参数。一个是FL_IN，是32位的输入数据。另外一个是EK的下标k。FI返回一个32位的数据FL_OUT。
FL(FL_IN,k)
begin
vard0,d1as16-bitinteger;
d0=FL_IN>>16;
d1=FL_IN&0xffff;
if(kisanevennumber)then
d1=d1^(d0&EK[k/2]);
d0=d0^(d1EK[(k/2+6)%8+8]);
else
d1=d1^(d0&EK[((k-1)/2+2)%8+8]);
d0=d0^(d1EK[((k-1)/2+4)%8]);
endif
FL_OUT=(d0<<16)d1;
returnFL_OUT;
end.
当用来解密时，用函数FLINV代替函数FL。
FLINV(FL_IN,k)
begin
vard0,d1as16-bitinteger;
d0=FL_IN>>16;
d1=FL_IN&0xffff;
if(kisanevennumber)then
d0=d0^(d1EK[(k/2+6)%8+8]);
d1=d1^(d0&EK[k/2]);
else
d0=d0^(d1EK[((k-1)/2+4)%8]);
d1=d1^(d0&EK[((k-1)/2+2)%8+8]);
endif
FL_OUT=(d0<<16)d1;
returnFL_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-CBCOBJECTIDENTIFIER::=
{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-CBCParameter::=IV
（V::=OCTETSTRING--8octets）
当这种对象标识符被使用时，明文在加密之前要进行填充。至少在明文后面填充一个字节，使其长度为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,"NewBlockEncryptionAlgorithmMISTY",FastSoftware
Encryption-4thInternationalWorkshop(FSE"97),LNCS1267,
SpringerVerlag,1997,pp.54-68
[2]K.NybergandL.R.Knudsen,"ProvableSecurityAgainsta
DifferentialAttack",JournalofCryptology,Vol.8,No.1,1995,
pp.27-37
[3]K.Nyberg,"LinearApproximationofBlockCiphers",Advancesin
Cryptology-Eurocrypt"94,LNCS950,SpringerVerlag,1995,
pp.439-444
[4]M.Matsui,"NewStrUCtureofBlockCipherswithProvable
SecurityAgainstDifferentialandLinearCryptanalysis",Fast
SoftwareEncryption-ThirdInternationalWorkshop,LNCS1039,
SpringerVerlag,1996,pp.205-218
7作者联系方法
HidenoriOhta
MitsubishiElectricCorporation,InformationTechnologyR&DCenter
5-1-1Ofuna,Kamakura,Kanagawa247-8501,Japan
Phone:+81-467-41-2183
Fax:+81-467-41-2185
EMail:hidenori@iss.isl.melco.co.jp

MitsuruMatsui
MitsubishiElectricCorporation,InformationTechnologyR&DCenter
5-1-1Ofuna,Kamakura,Kanagawa247-8501,Japan
Phone:+81-467-41-2181
Fax:+81-467-41-2185
EMail:matsui@iss.isl.melco.co.jp
附录A－MISTY1加密数据举例:
下面是一个密钥，明文，密文的例子：
密钥:00112233445566778899aabbccddeeff
明文:0123456789abcdeffedcba9876543210
密文:8b1da5f56ab3d07c04b68240b13be95d
在上面的例子中，明文的长度为128位，对于每个64位使用了两次MISTY1，称为ECB模式。
下面的例子是CBC模式：
密钥:00112233445566778899aabbccddeeff
IV:0102030405060708
明文:0123456789abcdeffedcba9876543210
密文:461c1e879c18c27fb9adf2d80c89031f
版权说明
Copyright(C)TheInternetSociety(1999).AllRightsReserved.
Thisdocumentandtranslationsofitmaybecopiedandfurnishedtoothers,andderivativeworksthatcommentonorotherwiseeXPlainitorassistinitsimplementationmaybeprepared,copied,publishedanddistributed,inwholeorinpart,withoutrestrictionofanykind,providedthattheabovecopyrightnoticeandthisparagraphareincludedonallsuchcopiesandderivativeworks.However,thisdocumentitselfmaynotbemodifiedinanyway,suchasbyremovingthecopyrightnoticeorreferencestotheInternetSocietyorotherInternetorganizations,exceptasneededforthepurposeofdevelopingInternetstandardsinwhichcasetheproceduresforcopyrightsdefinedintheInternetStandardsprocessmustbefollowed,orasrequiredtotranslateitintolanguagesotherthanEnglish.
ThelimitedpermissionsgrantedaboveareperpetualandwillnotberevokedbytheInternetSocietyoritssuccessorsorassigns.
Thisdocumentandtheinformationcontainedhereinisprovidedonan"ASIS"basisandTHEINTERNETSOCIETYANDTHEINTERNETENGINEERINGTASKFORCEDISCLAIMSALLWARRANTIES,EXPRESSORIMPLIED,INCLUDINGBUTNOTLIMITEDTOANYWARRANTYTHATTHEUSEOFTHEINFORMATIONHEREINWILLNOTINFRINGEANYRIGHTSORANYIMPLIEDWARRANTIESOFMERCHANTABILITYORFITNESSFORAPARTICULARPURPOSE.
鸣谢
感谢Internet协会给予RFC编辑部门的资金。