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^(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;
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^(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;
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电子公司有合同，你也可以免费地在商业中使用这个算法。如果需要获得更多的信息，请与[e-mail]联系。
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:[phone]
Fax:[phone]
EMail:[e-mail]


MitsuruMatsui
MitsubishiElectricCorporation,InformationTechnologyR&DCenter
5-1-1Ofuna,Kamakura,Kanagawa247-8501,Japan

Phone:[phone]
Fax:[phone]
EMail:[e-mail]
附录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协会给予编辑部门的资金。