加密算法“MISTY”(全)

chszs

　　“时田，这是竹田部长要求的……”

　　“还要减小啊。反正要减得更小，你告诉他那个主意了吗？”

　　“还没有。能不能行还没把握……”

　　“为什么不呀。不试试怎么知道。可能性是有的，做做试试看吧。”

　　时田依然是一开口便停不下来，他的话已经成为市川和反町不可或缺的精神调剂品。艰难的讨论在时田的话语激励下被调动起来，转向了新的方向。因竹田的斥责而深感沮丧的市川和反町重新鼓起了干劲。

　　如果将MISTY的处理原封不动地安装到硬件中的话，电路规模会达到40k门～50k门。但研究小组从最初就对减少电路规模下了很大工夫。也就是让一个电路反复多次使用。

　　MISTY通过以更换数据及参数的方式反复进行8次相同操作来实现数据加密注1）。每次的操作由两部分组成，一是根据唯一密钥生成暂时使用的扩展密钥的“密钥调度表部分”；另一个是用密钥调度表转换和打乱数据的“数据随机化部分”。也就是说，如果将生成扩展密钥的电路以及打乱数据的电路各只准备一条，并依次改动数据进行8次处理，便可将电路规模减小到约1/8。后来的实际验证表明，这一手段的确能够将电路规模减小至10数k门。

注1）密码研究界将这一方式称为具有8次迭代函数的分组密码。 MISTY有MISTY1和MISTY2两种。其中MISTY1的数据随机化部分采用与DES一样的Feistel型结构。MISTY2不使用 Feistel型结构，而是采用可提高处理并行度的方式。三菱电机推荐以8次迭代来使用MISTY1，以12次迭代来使用MISTY2。

　　竹田对市川和反町的要求正是进一步小型化。下面只有向执行1次迭代处理的电路下手了。两人将目光放在了扩展密钥及打乱数据的操作也可通过反复使用一条电路来执行的部分上。电路规模为10数k门的设计通常采用多条相同电路进行并行处理来提高速度。如果改为用一条电路来依次执行上述操作的话，虽然处理时间会变长，但却可以显著减小电路规模。该想法使电路规模减少数成有了眉目。

　　竹田的底气由此大增，大声吼道：“市川，反町，过来一下！今后就别想再说不行。你们还有什么绝招没有拿出来？反正我要你们减小再减小！”

结果却是不采用

　　通过不懈努力，MISTY的处理电路最后减小到了6k门。将原本就很小的电路又减小了一半。这在密码处理电路中已经是绝无仅有的尺寸了。不过即便如此，离1k门还是很遥远。

　　在CPTWG中，只要能够防止非恶意用户复制（Casual Copy）便可的观点已成为主流。如果只是这种水平的话，所使用的密码技术就未必要有“不可破译”的安全性。MISTY的电路规模就是减得再小，离设备厂商的要求还是很远。就连最有需求的内容业界，也认为只要有扰码就足够了。

　　虽说MISTY在CPTWG中的形势不妙，但整天灰心丧气也不是个办法。需要标准版权保护技术的并非只有DVD。竹田等随即开始向IEEE1394接口标准化委员会，以及制定视频点播标准规格的DAVIC等推荐采用MISTY。但结果都是无功而返。提案时间较晚，包括系统设计在内的提案还不成熟，这些都起到了负面影响。最后，在三菱电机之外，还是没有任何MISTY得到采用的实例。

　　不知不觉中，竹田就任部长已经快两年半了。“让MISTY成为全球标准”，这仍然只是个梦想，甚至说都不敢说出口。同士及上司的目光也日趋冷峻。而有讽刺意味的是，总是说MISTY、MISTY，结果MISTY在公司内部的知名度倒是越来越高了。而MISTY在公司内部越是有名，周围的环境就愈发严酷。

　　真得一点办法都没有了吗？竹田也快要举手投降了。在形势所逼之下，竹田决定启动深藏心底的最后手段。

只有“免费”

　　“……是不是只好无偿提供了？”

　　1997年傍晚。就好象是突然想起来的一样，竹田不动声色地向山岸笃弘和松井充试探到。对于这一问题，竹田并没有直问的把握。

　　“是呀，看来是要这么做了。”

　　出乎竹田的意料，山岸回答得很干脆。松井也表示同意。无论山岸还是松井，似乎早就有同样的想法了。竹田一下子变得如释重负。最后也只有这样了。

　　竹田的打算是向其他公司无偿提供MISTY基本专利的使用权。也就是效仿DES的做法。实际上，这一想法本身在MISTY诞生之初就已经产生了。当时在启动业务时也曾咨询过美国的咨询师，得到的结论是应该与DES一样进行无偿提供。

　　虽说如此，DES和MISTY的诞生背景完全不同。DES是美国行政机构以确立标准密码方式为目的开发而成，因此而无偿提供。而MISTY是民营企业以营利为目的开发而成，不会轻易进行无偿提供。实际上，日立制作所的“Multi”及NTT的“FEAL”等其他竞争对手的密码技术都是有偿的，而且业务开展得非常顺利。因此，单单MISTY无偿提供公司方面是很难通过的。

加密算法“MISTY”的开发经过


靠产品取胜

　　2年半后，让竹田跨越免费底线的是嵌入MISTY的自主产品的开发情况。

　　虽然在向其他公司推销时不断触礁，但利用MISTY的应用软件及信息系统却被竹田统管的信息安全技术部不断开发出来。带来契机的是面向电子商务认证实验“JapanNet”的系统。JapanNet是当时日本通商产业省为培育电子商务市场而设立的项目，有多家厂商享受到了国家预算拨款。在三菱电机，以信息安全技术部的胜山光太郎等为中心的开发团队构筑起了用户认证和结算的基础。通过该项目，开发出了可保护隐私性的通信技术，以及对电子邮件加密后进行交流的软件。

竹田荣作和胜山光太郎
为启动三菱电机信息安全业务而奔走的竹田荣作（左）。为“MISTY”成为业界标准发挥了带头作用。1995年6月在三菱电机创立“信息安全系统开发中心”的同时就任该中心负责人。该中心于1996年4月更名为“信息安全技术部”，竹田仍以部长之职统一管辖。之后，2002年4月起由胜山光太郎担任三菱电机信息技术综合研究所信息安全技术部长（右）。胜山于“MISTY”刚刚公开报道过后的1995年10月调入信息安全系统开发中心。负责日本通商产业省（当时）推进的电子商务实证实验技术开发项目。在从事信息安全业务之前，一直负责研发大型计算机的分散处理系统。（摄影：福田一郎）


　　即使MISTY的基本专利可以无偿使用，其他公司仍需要时间来开发产品。三菱电机拥有开发者独有的优势。现在比什么都重要的是开拓市场。以此为目的进行无偿提供的话，也许任何人都不会有意见。

最终决定无偿提供基本专利
三菱电机1998年8月宣布将无偿提供“MISTY”的基本专利。企业拥有的密码技术无偿提供专利使用权尚属首次，引起了大众媒体的广泛关注。图为1998年8月6日发行的《日经产业新闻》。
　　竹田又立即展开了行动。他敲开了公司知识产权部的大门，对无偿专利授权的做法进行了咨询。没想到的是，以前一直担心的无偿方式并没遭到多少反对。在公司知识财产部的协助下，竹田只用了不到两周时间便确立了无偿提供的基本方针。竹田将方案提交给了已成为开发本部长的野间口。对于使MISTY变为业界标准，竹田坚信非此招莫属了。

　　半年后，三菱电机于1998年8月宣布将无偿提供MISTY的基本专利。

chszs

　　1998年夏天，三菱电机推出了无偿提供“MISTY”基本专利使用权的方针，这是一条稍有差池就会使研究成果毁于一旦的道路。但这一赌注同时也带来了巨大的机会。探讨3G移动电话标准规格的3GPP，作为用于无线通信区的加密方式看中了MISTY技术。由此诞生了手机国际标准密码 “KASUMI”。至此，距离MISTY公开报道已过去了4年半的时间。

　　1999年2月。严冬季节的英国伦敦，干冷的空气刺痛着面颊。

　　“嗯——。还真到英国来了。”

　　近泽武的口中一直念叨个不停。身为三菱电机信息安全技术部的一员，没想到一直从事的密码工作还能为其带来到世界各地转转的机会。

　　近泽进入三菱电机是在1986年。他一进公司就主动要求加入了刚刚启动的密码研究。然而，与“将密码研究视为核心”的口号相反，当时公司内外几乎没有任何密码需求。在进入公司后的前一两年里，他每天几乎都是阅读文献及论文来打发时间。

近泽武
在1986年三菱电机启动密码研究后不久进入该公司，参与密码研究工作。1998年在日本电波产业会（ARIB）有关新一代手机的研究会所设立的安全相关工作组中担任主管。以此为契机参加了3G国际标准化组织“3GPP”。最近多在从事加密技术标准化等工作。目前在三菱电机信息技术综合研究所信息安全技术部任专职。（摄影：福田一郎）
　　实际上，近泽曾一度想过改行。工作少得让人感到寂寞，这不禁让他想去寻找有乐趣的职业。当时他看中的是旅行社。虽说旅行也算不上自己的爱好，但幻想一下在遥远的异国他乡，似乎能够把自己从单调的日子中解放出来。为此，近泽一直在阅读密码论文的空闲时间为考旅行社做准备，以便获取旅游从业资格证书。

　　时光转眼过了10年。当近泽蓦然回首的时候发现，自己其实已经在为密码工作飞奔于世界各地了，真可谓人生无常。

尽管来时心情轻松

　　近泽来到遥远的欧洲，是为了参加3G国际标准化组织“3GPP（3rd Generation Partnership Project）”举行的会议。该会由3GPP中推进安全标准化的工作组“TSG SA WG3”主办，在伦敦国际大酒店召开。

　　近泽所属的三菱电机信息安全技术部原本与手机没有任何关系。说起这件事的起因，还需追溯到1年前来自手机事业部的要求。当时手机事业部希望派人参加日本国内的新一代手机标准研究会。

　　手机事业部接到了来自负责管理新一代手机研讨会的日本电波产业会（ARIB）的咨询。为了新设安全分会，ARIB希望从三菱电机选出一名主管。当时正是三菱电机到处推销安全业务的时期。ARIB好象也听说了这一消息。要论安全技术，当然非研究所莫属了。在研究所担任信息安全技术部部长的竹田荣作将这一任务分配给了近泽。

　　近泽没有多想就应承下来，而当其发现有难度时却已骑虎难下了。专攻密码研究，几乎没有任何手机知识的近泽要负责汇总通信运营商及手机厂商技术人员的讨论内容。为此，近泽一边推进探讨在手机上配备IC卡系统，一边从手机的基础知识起步开始拼命学习。

　　在担任安全分会主管一年后，近泽总算习惯了手机行业的情况。1998年12月，3GPP开始活动。鉴于对第二代手机标准各国各自为政的反思，新一代手机以制定全球通用标准为目标。欧洲、美国、韩国、中国及日本，3GPP向各国标准化团体发出加盟邀请。确立与3GPP合作方针的ARIB也要求日本国内的安全分会派遣人才。在分会内部，应该向3GPP报告活动内容的意见成为主流。不过，这一任务由谁承担，不由分说就落在了近泽的身上。

请说一下密码部分

　　“这下糟了……”

　　面对着一屋子的工作组与会人员，近泽有些忐忑不安。近30名与会人员多半是欧洲人。不用说日本，就连整个亚洲也只有近泽一人与会。这让人颇感沮丧。

　　这种心情一次就够了。因此近泽想打一下马虎眼，尽快了事。而且，对于与自己的研究没有直接关系的业务，无法花费过多的预算及时间，也许参加这一次就行了。近泽原以为最多只是让自己用不太流利的英语来介绍一下ARIB的活动内容。

　　“近泽先生！”

　　“嗯？我，我吗？”

　　就在会议要结束的时候，主席却喊起了近泽的名字。

　　“对，就是你。由你来负责汇总无线通信区密码要求的性能指标”

　　“啊……”

　　请稍，稍等一下。这太难了。虽然近泽想拒绝，但舌头却贴在干巴巴的喉咙上，不听使唤。越是着急，越说不出词来。

　　工作组要研究的事项堆积如山。包括手机认证方法等在内，各个事项的负责人都现场确定。由于制定的是国际标准，因此只让欧洲人负责的话，无法实现良好平衡，所以需要让日本人也参与进来。这种气氛在工作组内逐渐形成。

　　原本想参加这一次就算了。现在看来是躲不开了。近泽无论怎么拼命想办法，脑子里都是一片空白。一句话没出来，却急出了汗。怎么办？怎么办？

　　这时主席又确认了一下。

　　“近泽生先，那么就由你负责了。”

　　“……好，好的”

　　无力拒绝的近泽只好答应。

于心不忍而提供帮助

　　回国后，近泽急忙着手编写性能指标书。要说担任国际标准的汇总者，不用说近泽是头一回。尽管是顾左不顾右，但近泽最终还是写完了草案，并在1999年4月举行的第二次会议上进行了提交。

　　结果太糟糕了。看过草案的工作组委员们的反应很差。似乎是未能与欧洲现有的GSM方式很好契合。3GPP主席因看不过去为近泽提供了顾问，介绍的是身为其部下的英国沃达丰的职员。从第二次会议返回日本后，近泽参考顾问的意见对性能指标书进行了全力修改。

　　这真是一位非常有水平的顾问。但反过来他对指标容不得半点含糊。近泽编写的性能指标书一次次地被他修改。近泽毫无汇总者的面子。最后，改来改去，性能指标书总算完成了。这时近泽自己写的部分已经基本上荡然无存了。

　　这样的草案应该有望获得工作组的认可。只要在下次会议上提出，并加入其他委员的意见，最终的性能指标书即可确定下来。就象经历了一场暴风雨，从慌张中走出来的近泽平静下来，将改好的指标又重新审视了一遍，发现上面列出了多项密码要求。

　　首先跃入眼帘的是硬件安装时的电路规模。鉴于设备厂商防止成本增加的要求，草案指出加密处理电路最好能够在10k门以下。其次是加密处理性能。新一代手机的通信速度最大为2Mbit/秒。当然，加密处理电路必须要实现超出这一水平的性能。之后是密码输入输出接口的参数要求。

　　“等等。这么说那个密码不刚好……”

　　虽然性能指标书并不是为指定密码而编写的，但近泽的脑海里依然浮现出了恰好符合这些条件的密码算法。

chszs

不报希望也要试试看

　　在1999年5月德国举行的第三次会议上近泽提交了“MISTY”的技术资料。在未与同士及上司商量的情况下，近泽自行备好资料装入差旅包带到了会场。3GPP并不征集密码技术。文件收件人写的是“SAGE”。SAGE是通信标准化机构欧洲电信标准协会（ETSI）旗下专门负责密码算法的部门。密码算法本身并不是3GPP的标准化对象。按照欧洲的标准化制定惯例，3GPP委托SAGE进行密码设计。


向SAGE提交“MISTY”技术资料
左侧为近泽武向3GPP讨论安全相关性能指标的工作组“TSG System Aspects WG3”提交的“MISTY”技术文件。该文件在1999年5月于德国波恩举行的第三次会议上提交。文件中介绍，MISTY的电路规模最小为6k门，该规模下55MHz工作时处理性能为100Mbit/秒。收件人写的是“ETSI SAGE”。SAGE是欧洲电信标准协会（ETSI）旗下专门负责密码算法的部门。该部门还讨论3G移动电话系统采用的加密方式。右侧为近泽在参加3GPP于1999年8月举行的会议时使用的名片。这次会议最终决定采用基于MISTY的加密技术。


　　对于身属信息安全技术部门的近泽而言，向标准化团体推销MISTY似乎已成为固定的习惯。总之近4年里，在竹田的带领下大家饱受了艰辛。近泽本人也在到处推销的过程中屡屡体验辛酸。明显的成果没有获得，获得的总是落选的打击。

　　这次肯定也一样——近泽并未抱多大希望。

SAGE发来电子邮件

　　近泽的这个想法被向好的方向发展的事态所推翻。

　　“请告知MISTY专利的授权条件。”

　　1999年夏天，MISTY研究小组收到一封电子邮件。发件人是SAGE。正是从那个欧洲电信标准协会（ETSI）旗下专门负责密码算法的部门直接发来的。

　　真没想到这么快就有了回音。而且，更可喜的是还在询问具体的授权条件。说不定MISTY就要被认可了呢……。近泽抱着一线希望回复了邮件，告诉对方MISTY专利可无偿使用。而这正是后来得以成功的关键。

　　当时，SAGE从3GPP得到近泽等编写的性能指标书后，对3G移动电话可使用的加密方式进行了仔细讨论。SAGE设定了苛刻的限制条件——必须在短短的半年里开发出加密算法。这样，放弃新的开发、对现有算法加以改进就成了必然的选择。

　　但能够满足所有要求的加密算法却怎么也找不到。性能高而又电路规模小，要同时满足这两个相反条件极为困难。正在此时，近泽提交的MISTY的技术资料引起了SAGE的注意。

　　至此，距离竹田接到“要让MISTY成为全球标准”的业务命令已有4年，松井充着手开发密码也足足5年后，这么长的时间辛苦积累起来的成果终于遇到了伯乐。其中，无论是松井倾尽心血的高于DES的安全性，还是市川哲也、反町亨、时田俊雄协手实现的6k门极小硬件，从哪方面看，MISTY都符合3GPP的要求，就像量身订做的一样。

　　尽管如此，有一点仍然要向SAGE确认一下。也就是近泽等收到的电子邮件所问及的条件。而竹田所下的决定正好拿来作突破口。因此最后承诺“可无偿使用专利”。

用日语怎么说?

　　一旦抓住头绪，交涉进程就象决堤之水势不可挡。耽误多年的时间似乎一下子得以挽回，计划顺利决定下来。3GPP在1999年8月的会议上迅速做出内部决定，准备采用基于MISTY的算法作为3G移动电话的加密方式。SAGE聘请松井在欧洲启动了以3G移动电话为应用对象的密码优化工作。为了能够缩短处理的开销时间、频繁变更秘钥，还进一步简化了密钥调度表部分。


移动电话配备“KASUMI”
3GPP于2000年3月认定“KASUMI”为W-CDMA无线通信区使用的唯一国际标准密码。所有W-CDMA方式的移动电话均开始配备KASUMI加密处理电路。移动电话和基站使用KASUMI来保护无线通信所交换的语音数据及用户数据。另外，GSM协会2002年7月宣布，目前在欧洲及亚洲仍为主流的GSM方式也采用KASUMI作为标准密码。左侧为NTT DoCoMo推出的3G移动电话服务“FOMA”使用的手机，右侧为GSM/GPRS方式的手机。均为三菱电机产品。
　　“松井先生，MISTY用日语怎么说？”

　　在商议后成员共进晚餐是SAGE会议的习惯。在优化工作接近尾声时，新密码的名称成为了话题。

　　“MISTY就是‘雾’（发音KIRI）。”

　　“是KIRI呀……。”

　　成员们反应平平。

　　“在有的季节也说成‘霞’”

　　“噢!KASUMI！”

　　“KASUMI，KASUMI！”

　　也许是受到了东方式发音的吸引，除了深感疑惑的松井之外，所有成员都无一例外地连呼“KASUMI”。于是，全场一致决定用“KASUMI”作为密码的名称。

　　2000年3月，这一天终于来到了。3GPP宣布采用KASUMI作为3G移动电话无线通信区唯一的国际标准密码。


留名密码研究史
在破解美国标准密码“DES”的实验上取得成功的“线性破解法”现在被公认为密码领域的重要研究成果之一。照片上是1997年举行的密码相关国际会议“CRYPTO’97”作为小礼品发给与会者的T恤。上面列出了在长达3000年的密码史中已知的代表性事件及研究成果。最新成果就是松井充开发的线性破解法，被记述为“1994....Linear cryptanalysis”。其中，最古老的研究题目为“1900BC....Non-standard hieroglyphics”。在古埃及，人们经常会将以形状表现动植物及身边事物的象形文字刻成碑文。公元前1900年前后的某记录中采用了非标准的象形文字。这些文字被视为有史以来最古老的密文。（摄影：福田一郎）
MISTY华丽变身

　　KASUMI被采用为3G移动电话的标准后，三菱电机密码研究的外部环境发生了巨大变化。

　　三菱电机的信息安全业务迅速被全球广泛认可。客户的信任感得到以往无法相比的提高。当初在竹田启动业务时，三菱电机从事信息安全业务的人员只有13名。而现在不同，在继竹田之后不断拓展业务的胜山光太郎手下，包括关联公司在内，相关人才已达到70～80名。

　　KASUMI本身也迎来了实用期。NTT DoCoMo从2001年10月开始推出3G移动电话服务“FOMA”，该服务的手机无一例外都配备了KASUMI加密处理电路。而且，采用KASUMI的不只是新一代移动电话。2002年7月，欧洲GSM协会决定在GSM方式的移动电话上采用KASUMI。GSM方式在欧洲及亚洲依然在广泛使用。继承MISTY血统的产品，其范围有望不断扩大。

　　“MISTY唯一的缺点就是太年轻”——。在竹田及松井等艰苦推销MISTY时，缺乏实际业绩的MISTY曾遭受过如此嘲讽。MISTY的性能指标确定下来才6年。虽然现在仍然是资历尚浅，但却获得了与这一点并不相称的成功。如今再也没有人怀疑MISTY的业绩了。在密码学会上，MISTY很快就成为了破解实验的对象。就像松井力求攻克DES一样，许多研究人员都在为破解MISTY的密钥而切磋琢磨。

　　直到今天，松井仍未停止脚步。鉴于MISTY早晚会有一天被人破解，松井又与NTT共同开发出了新一代加密算法“Camellia”。该算法是继DES之后的美国标准密码“AES”的强大对手。在进入三菱电机十多年后，松井已从曾一度放弃数学家之路的失意青年，成为了无可否认的密码研究权威。

　　参与MISTY开发的研究人员，每个人都经历了难以想像的人生。为启动MISTY业务而牵头奔走的竹田跳槽到了从事信息安全认证业务的企业，开始了新的挑战。因向往纠错码研究而转行至三菱电机的山岸笃弘现在正忙于日本信息处理振兴事业协会（IPA）的工作，每天都在为评测密码技术而奔波。梦想通过旅行社工作周游各国的近泽一直在为密码标准化业务而辗转全球。市川和反町如今仍在日夜致力于减小电路规模的开发。而时田则依然承担着提供咨询的角色……。

　　回头想想的话，这一切都只是源于当时松井心里产生的一个疑问。

　　“密码破解？究竟是怎么回事呢？”（全文完）

[ 本帖最后由 chszs 于 2010-3-9 08:45 编辑 ]

chszs

misty

justforregister

nice job

justforregister

小日本是强