RFC2994 MISTY1加密算法描述

本備忘錄狀態
ThismemoprovidesinformationfortheInte.netcommunity.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:14705d1131cd0791611a517909e1b40clearcase/" target="_blank" >cc02213201a0e8004
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電子公司有合同，你也可以免費地在商業中使用這個算法。如果需要獲得更多的信息，請與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編輯部門的資金。