概率论在密码学中的应用
口郑娟朱金伟曾文军
（华中师范大学数学与统计学学院湖北・武汉４３００７９）
摘要：本文通过介绍密码学中的保密通信系统模型，分析密码体制的安全性、可靠性来挖掘隐藏在各个机制中的概率统计规律，从而揭示出概率论在密码学理论中发挥的重要作用。
关键词：生日攻击统计量密码分析中图分类号：ＴＰ３
文献标识码：Ａ
文章编号：１００７－３９７３（２００８）０７－０８９－０２
１引言三方截取，即主要来自非法者的主动攻击（见保密通信系统
２ｌ世纪是信息时代，信息已成为社会发展的重要战略模型）．采用消息认证，通过基于公开函数一杂凑（Ｈａｓｈ）函数
资源．在信息化社会中，信息安全将扮演极为重要的角色，取得认证符就可以防止主动攻击。
它直接关系到国家安全、企业经营和人们的日常生活．密码确切的说，Ｈａｓｈ函数（简称Ｈ）用于将任意长的消息技术作为信息安全系统中保障数据安全的关键技术，其体Ｍ映射为较短的、固定长度的一个值Ⅳ彤），即杂凑值、杂凑制的完备性在于密码在计算机有限空间和时间条件下的不码或消息摘要．对于定义域Ｄ和值域Ｒ，有ＨＩＤ斗Ｒ和ｌＤｌ，旧。可破译性．而这种不可破译性又由密钥的随机安全性决定．它应满足以下条件：
在研究密码学过程中，概率论无疑起着相当重要的作用，它（ａ）已知ｈ，求使得胃（砷＝＾的Ｘ在计算上是不可行的，对于检测密钥的随机可靠性，分析攻击密码流，检测随机序这一性质称为函数的单向性，称片（ｘ）为单向杂凑函数；列的伪随机性都具有十分重要的作用。（６）已知ｘ，找出Ｙ（Ｙ≠，）使得Ⅳ（Ｊ，）＝日０）在计算上是不２背景知识和概念
可行的；
密码学：密码学是对与信息安全各方面（比如机密性、（ｆ）找出任意两个不同的输入ｘ，），，使得Ⅳ∽＝Ⅳｏ。在计数据完整性、实体认证及数据源认证）有关数学技术的研算上是不可行的．
究。
其中条件（口）保证攻击者截获膨和ｃ＝．Ｉ：ｆ《ｓＩ肘）后，求不出密码加密和解密：发送方将要发送的消息称为明文，明ｃ的逆ＳＩＭ，也就不可求出秘密值Ｓ．条件（∞使得敌手无文被变换成看似无意义的随机消息，称为密文，这种变换过法在已知某个消息时，找到与该消息具有相同杂凑值的另程称为加密．加密的逆过程称为解密．
一消息．条件（ｃ）用于抵抗生日攻击。
密码分析：密码通信过程中，截收者通过分析可能从由于该函数是多对一的，因此存在碰撞（具有同一输截获的密文推断出原来的明文或者密钥的过程称为密码分出的输入对）是不可避免的．实际上，限制曰到一个ｔ比特
析．
输入的域（，＞”），在所有输出是等概率的意义下，假如日是
３密码学中的概率统计模型
“随机的”，则大约有２＇４个输入对应同一个输出，且两个随密码学的研究是基于密码通信系统的．它包括了从信机选择的输入产生同一输出的概率为２”（与ｔ无关）．抽象源到接收者的加密和解密过程，也包括在此过程中的受到成数学中的生日攻击模型就是：
的来自非法接入者的非法攻击．其模型的图解如下：
已知～杂凑函数日有胛个可能的输出，Ⅳ∽是一个特定的输出，如果对Ⅳ随机取ｋ个输入，则至少有一个输入ｙ使得Ｈ（ｙ）；Ⅳ（ｘ）的概率为０．５时，ｋ有多大？
解因为Ｈ有刀个可能的输出，所以输入ｙ产生的输出ｔｔ（ｙ）等于特定输出Ⅳ∽的概率是ｌ／疗，反过来说Ｈｆｙ）＃Ｈ（ｘ）的概率是ｌ—ｌ／盯．ｙ取ｋ个随机值而函数的ｋ个输出中没有一个等于Ⅳ（ｘ），其概率为（Ｉ—Ｉ／ｎ）・，所以ｙ取ｋ个随机值得到函数的ｋ个输出中至少有～个等于日（ｘ）的概率为１一（１—１／－）‘．由（１＋Ｊ）‘ｚｌ＋＿ｂ，其中Ｉ卅“１，可得：
１一（１—１／，，）‘≈１一（１一七／，，）一七／月，
保密通信系统模型
若上述概率等于０．５，则ｋ＝ｎ／２．特别地，如果日的输出其中ｍ代表明文，ｃ代表密文，毛和乞均代表密钥流．为ｍ比特长，则可能的输出个数疗＝２”，则ｋ＝２”１．ｍ’为密码分析员解密获得的明文，ｃ’为攻击者获得的密文４．２随机密钥构造过程中的测试统计量
部分。
密码学中最重耍的并不是加密算法和解密算法，而是４概率论在密码学中的应用在加密过程和解密过程ｔ｝ｔ所需要用到的加密密钥和解密密４．１抗击主动攻击的生日攻击模型
钥．加密密钥和解密密钥的生成又在于随机序列的获得．
密码加密的任务是为了防止通信双方的信息内容被第
事实上，不管利用硬件还是利用软件设计随机序列都
越协斧信．’ｎｎＲ盔笛７如ｆ下ｌ
万
方数据
是很困难的，在多数情况下，我们需要通过已成熟的算法来获得近似的随机序列，即伪随机序列．判断序列是否具有伪随机性就需要用到概率统计测试，而这种测试对于被动攻击中的密码分析员（见密码通信系统）破解密码也同样具有重要意义：４．２．１频数检验
频数检验是最基本的检验．在进行随机性测试时，应该首先选择频数检验，频数检验通过后再选择其它检验，否则就不必选择其它检验了．有一些检验比如线性复杂度检验会耗费大量的时间，而频数检验是速度最快的一种检验方式，为了节省时间，我们有必要在进行其它检验以前，先选择频数检验．频数检验是用来检验一个位序列中Ｏ和１的个数是否近似相等。这正是随机序列所应具备的．令‰和啊分别表示待测位序列ｓ中０和１的个数．所使用的统计量为：
ｘ．一￡２２＝当２：月
若刀不小于１０，则该统计量近似地服从自由度为１的ｘ，分布．在实际使用中建议加１００００．
４．２．２跟随测试（又称序列测试或双比特测试）
该测试的目的是判定位序列ｓ的子序列００，Ｏｌ，１０，ｌｌ所出现的次数是否近似相等，这也是一个随机序列所应具备的特性．令‰和惕分别表示ｓ中０和ｌ的个数，且‰，ｎｕ。，‰，ｑ．分别表示Ｓ中子序列００，０１，１０，１１出现的次数．
Ｘ５—２（爿（ｄ）一二＝—：÷）／√拧一ｄ
二
若ｎ－ｄ＞９，则它近似地服从Ｎ（Ｏ，１）（ＸＸ边测试）．４．３其它概率模型
４．３．１关于密码学中的周期随机序列模型
我们称有限域‘上的序列ａ；（ａｏ，口ｌ，吼，一．）为周期序列，如果存在正整数，，使对一切非负整数ｋ都有口Ｉ。＝ｑ，而称满足上式的最小正整数，为序列口的周期，且记为，（口）．
Ｒｕｐｐｅｌ对周期随机序列的线性复杂度的均值进行研究发现周期为２一的２值随机序列的线性复杂度的均值接近
２”一１．
４．３．２“秘密共享方案”中的概率模型［３］
“秘密共享方案”是关于子秘密的分配规则的说明．假
设ｒ是一个访问结构，，一疑Ｅ是分配规则的集合，称
，是一个实现访问结构ｒ的完备秘密共享方案，如果它具有下列两个特性：
（１）对任意一个参与者的授权子集口ｃＭ，不存在两个分配规则ｆｅ五和ｇ毫巧，ｋ，ｊＥＫ，ｋ≠＿，，满足厶＝ｇｎ（即
在任意一个授权子集中对参与者的任何一个秘密分配将确
定密钥的值）；
（２）对任何一个参与者的未授权子集曰￡Ｍ，对任意的子秘密分配规则兀Ｅｓ（Ｂ）和每一个ｋ∈Ｋ，均有
ｐ（ｋ
Ｉ兀）＝Ｐｘ（ｋ）（即对Ｂ的子秘密分配没有关于密钥
上述讨论了概率论在密码通信系统中各个不同部分的
注意‰＋％。＋‰十啊，＝（ｎ－１），因为这些子序列允许相
交．所使用的统计量为：
值的任何信息）．
应用，揭示了概率论在密码学中的重要作用，并且将一些概
Ｘ２＝—＝了（，瑶＋玎０２＋Ｋ２＋玎；）一兰（Ｈ；＋”？）＋１
若门不小于２ｌ，则该统计量近似地服从自由度为２的
ｘ２分布．
率论在密码中的应用分析得更为透彻．众多的密码学文献也向我们展示了这种重要性的实际应用效果．深入研究概率论的方法在密码中的应用对密码分析起着及其重要的作用．
（基金项目：国家创新性实验计划项目）
４．２．３游程检验
游程是序列的一个子串，由连续的０或者１组成，并且其前导和后继元素都与其本身的元素不同．游程检验主要检验待检序列Ｓ中游程总数是否符合随机性要求．游程测试可用来判定序列Ｓ中不同长度游程的个数是否与随机序列中所期待的一样，令岛，Ｇｊ分别为ｓ中长度为ｆ的１游程和０游程的个数，所使用的统计量为：
参考文献：
［１］杨波．现代密码学［Ｈ］．北京：清华大学出版社。２００７：
５～２０．１６０—１８０．
［２］Ａ．Ｊ。Ｍｅｎｅｚｅｓ。Ｐ．Ｃ．Ｖａｎ００ｒｓｃｈｏｔ，Ｓ．Ａ．Ｖａｎｓｔｏｎｅ著，胡
ｘ，：宇！垒二竺！Ｚ＋争￡鱼＝鱼￡。篙
ｅ。々＝
ｅ‘
磊，王鹏译．应用密码学手册［Ｍ］．北京：电子工业出版社，２００５：１５０—１６０．
［３］李世取．黄晓英。刘文芳，张卫明．刘凤梅．密码学中的有关
概率模型［Ｈ］．电子工业出版社，２００５：３７０～３９５．
其中口，＝（”一ｉ＋３）／２“２，ｋ是满足ｑ２５的最大的ｉ．该统计量近似地服从自由度为２ｋ－２的ｘ２分布．４．２．４扑克测试
扑克测试用来确定每个长度为聊的序列在ｓ中出现
的次数是否近似相等，令聊是一个满足ｌ詈ｌ：５－ｃ：。，的正整
数，令ｔ一［告］将序列拆分成ｋ个不相交的部分，每部分的
长度为所，令％为第ｆ种长度为聊的序列所出现的次数．所使用的统计量为：
．ｂ一弓｝（兰，妒）一七
＾
●一■
它近似地服从自由度为２”一ｌ的ｚ２分布．ｍ＝ｌ时即频率测试．
４．２．５自相关测试
自相关测试用来检测序列ｓ与其发生（非循环）移位后形成的序列之问的相关性．
令ｄ为一个固定整数，ｏ‘ｄ‘Ｌ纠，序列ｓ与ｓ发生ｄ
移位后所形成的序列中的不同比特
数为：ｍＣｄ）一善墨。ｓ一＋一，所使用的统计量为：
冒协抡丘・２００８年第７期（下）
万方数据
概率论在密码学中的应用
口郑娟朱金伟曾文军
（华中师范大学数学与统计学学院湖北・武汉４３００７９）
摘要：本文通过介绍密码学中的保密通信系统模型，分析密码体制的安全性、可靠性来挖掘隐藏在各个机制中的概率统计规律，从而揭示出概率论在密码学理论中发挥的重要作用。
关键词：生日攻击统计量密码分析中图分类号：ＴＰ３
文献标识码：Ａ
文章编号：１００７－３９７３（２００８）０７－０８９－０２
１引言三方截取，即主要来自非法者的主动攻击（见保密通信系统
２ｌ世纪是信息时代，信息已成为社会发展的重要战略模型）．采用消息认证，通过基于公开函数一杂凑（Ｈａｓｈ）函数
资源．在信息化社会中，信息安全将扮演极为重要的角色，取得认证符就可以防止主动攻击。
它直接关系到国家安全、企业经营和人们的日常生活．密码确切的说，Ｈａｓｈ函数（简称Ｈ）用于将任意长的消息技术作为信息安全系统中保障数据安全的关键技术，其体Ｍ映射为较短的、固定长度的一个值Ⅳ彤），即杂凑值、杂凑制的完备性在于密码在计算机有限空间和时间条件下的不码或消息摘要．对于定义域Ｄ和值域Ｒ，有ＨＩＤ斗Ｒ和ｌＤｌ，旧。可破译性．而这种不可破译性又由密钥的随机安全性决定．它应满足以下条件：
在研究密码学过程中，概率论无疑起着相当重要的作用，它（ａ）已知ｈ，求使得胃（砷＝＾的Ｘ在计算上是不可行的，对于检测密钥的随机可靠性，分析攻击密码流，检测随机序这一性质称为函数的单向性，称片（ｘ）为单向杂凑函数；列的伪随机性都具有十分重要的作用。（６）已知ｘ，找出Ｙ（Ｙ≠，）使得Ⅳ（Ｊ，）＝日０）在计算上是不２背景知识和概念
可行的；
密码学：密码学是对与信息安全各方面（比如机密性、（ｆ）找出任意两个不同的输入ｘ，），，使得Ⅳ∽＝Ⅳｏ。在计数据完整性、实体认证及数据源认证）有关数学技术的研算上是不可行的．
究。
其中条件（口）保证攻击者截获膨和ｃ＝．Ｉ：ｆ《ｓＩ肘）后，求不出密码加密和解密：发送方将要发送的消息称为明文，明ｃ的逆ＳＩＭ，也就不可求出秘密值Ｓ．条件（∞使得敌手无文被变换成看似无意义的随机消息，称为密文，这种变换过法在已知某个消息时，找到与该消息具有相同杂凑值的另程称为加密．加密的逆过程称为解密．
一消息．条件（ｃ）用于抵抗生日攻击。
密码分析：密码通信过程中，截收者通过分析可能从由于该函数是多对一的，因此存在碰撞（具有同一输截获的密文推断出原来的明文或者密钥的过程称为密码分出的输入对）是不可避免的．实际上，限制曰到一个ｔ比特
析．
输入的域（，＞”），在所有输出是等概率的意义下，假如日是
３密码学中的概率统计模型
“随机的”，则大约有２＇４个输入对应同一个输出，且两个随密码学的研究是基于密码通信系统的．它包括了从信机选择的输入产生同一输出的概率为２”（与ｔ无关）．抽象源到接收者的加密和解密过程，也包括在此过程中的受到成数学中的生日攻击模型就是：
的来自非法接入者的非法攻击．其模型的图解如下：
已知～杂凑函数日有胛个可能的输出，Ⅳ∽是一个特定的输出，如果对Ⅳ随机取ｋ个输入，则至少有一个输入ｙ使得Ｈ（ｙ）；Ⅳ（ｘ）的概率为０．５时，ｋ有多大？
解因为Ｈ有刀个可能的输出，所以输入ｙ产生的输出ｔｔ（ｙ）等于特定输出Ⅳ∽的概率是ｌ／疗，反过来说Ｈｆｙ）＃Ｈ（ｘ）的概率是ｌ—ｌ／盯．ｙ取ｋ个随机值而函数的ｋ个输出中没有一个等于Ⅳ（ｘ），其概率为（Ｉ—Ｉ／ｎ）・，所以ｙ取ｋ个随机值得到函数的ｋ个输出中至少有～个等于日（ｘ）的概率为１一（１—１／－）‘．由（１＋Ｊ）‘ｚｌ＋＿ｂ，其中Ｉ卅“１，可得：
１一（１—１／，，）‘≈１一（１一七／，，）一七／月，
保密通信系统模型
若上述概率等于０．５，则ｋ＝ｎ／２．特别地，如果日的输出其中ｍ代表明文，ｃ代表密文，毛和乞均代表密钥流．为ｍ比特长，则可能的输出个数疗＝２”，则ｋ＝２”１．ｍ’为密码分析员解密获得的明文，ｃ’为攻击者获得的密文４．２随机密钥构造过程中的测试统计量
部分。
密码学中最重耍的并不是加密算法和解密算法，而是４概率论在密码学中的应用在加密过程和解密过程ｔ｝ｔ所需要用到的加密密钥和解密密４．１抗击主动攻击的生日攻击模型
钥．加密密钥和解密密钥的生成又在于随机序列的获得．
密码加密的任务是为了防止通信双方的信息内容被第
事实上，不管利用硬件还是利用软件设计随机序列都
越协斧信．’ｎｎＲ盔笛７如ｆ下ｌ
万
方数据
是很困难的，在多数情况下，我们需要通过已成熟的算法来获得近似的随机序列，即伪随机序列．判断序列是否具有伪随机性就需要用到概率统计测试，而这种测试对于被动攻击中的密码分析员（见密码通信系统）破解密码也同样具有重要意义：４．２．１频数检验
频数检验是最基本的检验．在进行随机性测试时，应该首先选择频数检验，频数检验通过后再选择其它检验，否则就不必选择其它检验了．有一些检验比如线性复杂度检验会耗费大量的时间，而频数检验是速度最快的一种检验方式，为了节省时间，我们有必要在进行其它检验以前，先选择频数检验．频数检验是用来检验一个位序列中Ｏ和１的个数是否近似相等。这正是随机序列所应具备的．令‰和啊分别表示待测位序列ｓ中０和１的个数．所使用的统计量为：
ｘ．一￡２２＝当２：月
若刀不小于１０，则该统计量近似地服从自由度为１的ｘ，分布．在实际使用中建议加１００００．
４．２．２跟随测试（又称序列测试或双比特测试）
该测试的目的是判定位序列ｓ的子序列００，Ｏｌ，１０，ｌｌ所出现的次数是否近似相等，这也是一个随机序列所应具备的特性．令‰和惕分别表示ｓ中０和ｌ的个数，且‰，ｎｕ。，‰，ｑ．分别表示Ｓ中子序列００，０１，１０，１１出现的次数．
Ｘ５—２（爿（ｄ）一二＝—：÷）／√拧一ｄ
二
若ｎ－ｄ＞９，则它近似地服从Ｎ（Ｏ，１）（ＸＸ边测试）．４．３其它概率模型
４．３．１关于密码学中的周期随机序列模型
我们称有限域‘上的序列ａ；（ａｏ，口ｌ，吼，一．）为周期序列，如果存在正整数，，使对一切非负整数ｋ都有口Ｉ。＝ｑ，而称满足上式的最小正整数，为序列口的周期，且记为，（口）．
Ｒｕｐｐｅｌ对周期随机序列的线性复杂度的均值进行研究发现周期为２一的２值随机序列的线性复杂度的均值接近
２”一１．
４．３．２“秘密共享方案”中的概率模型［３］
“秘密共享方案”是关于子秘密的分配规则的说明．假
设ｒ是一个访问结构，，一疑Ｅ是分配规则的集合，称
，是一个实现访问结构ｒ的完备秘密共享方案，如果它具有下列两个特性：
（１）对任意一个参与者的授权子集口ｃＭ，不存在两个分配规则ｆｅ五和ｇ毫巧，ｋ，ｊＥＫ，ｋ≠＿，，满足厶＝ｇｎ（即
在任意一个授权子集中对参与者的任何一个秘密分配将确
定密钥的值）；
（２）对任何一个参与者的未授权子集曰￡Ｍ，对任意的子秘密分配规则兀Ｅｓ（Ｂ）和每一个ｋ∈Ｋ，均有
ｐ（ｋ
Ｉ兀）＝Ｐｘ（ｋ）（即对Ｂ的子秘密分配没有关于密钥
上述讨论了概率论在密码通信系统中各个不同部分的
注意‰＋％。＋‰十啊，＝（ｎ－１），因为这些子序列允许相
交．所使用的统计量为：
值的任何信息）．
应用，揭示了概率论在密码学中的重要作用，并且将一些概
Ｘ２＝—＝了（，瑶＋玎０２＋Ｋ２＋玎；）一兰（Ｈ；＋”？）＋１
若门不小于２ｌ，则该统计量近似地服从自由度为２的
ｘ２分布．
率论在密码中的应用分析得更为透彻．众多的密码学文献也向我们展示了这种重要性的实际应用效果．深入研究概率论的方法在密码中的应用对密码分析起着及其重要的作用．
（基金项目：国家创新性实验计划项目）
４．２．３游程检验
游程是序列的一个子串，由连续的０或者１组成，并且其前导和后继元素都与其本身的元素不同．游程检验主要检验待检序列Ｓ中游程总数是否符合随机性要求．游程测试可用来判定序列Ｓ中不同长度游程的个数是否与随机序列中所期待的一样，令岛，Ｇｊ分别为ｓ中长度为ｆ的１游程和０游程的个数，所使用的统计量为：
参考文献：
［１］杨波．现代密码学［Ｈ］．北京：清华大学出版社。２００７：
５～２０．１６０—１８０．
［２］Ａ．Ｊ。Ｍｅｎｅｚｅｓ。Ｐ．Ｃ．Ｖａｎ００ｒｓｃｈｏｔ，Ｓ．Ａ．Ｖａｎｓｔｏｎｅ著，胡
ｘ，：宇！垒二竺！Ｚ＋争￡鱼＝鱼￡。篙
ｅ。々＝
ｅ‘
磊，王鹏译．应用密码学手册［Ｍ］．北京：电子工业出版社，２００５：１５０—１６０．
［３］李世取．黄晓英。刘文芳，张卫明．刘凤梅．密码学中的有关
概率模型［Ｈ］．电子工业出版社，２００５：３７０～３９５．
其中口，＝（”一ｉ＋３）／２“２，ｋ是满足ｑ２５的最大的ｉ．该统计量近似地服从自由度为２ｋ－２的ｘ２分布．４．２．４扑克测试
扑克测试用来确定每个长度为聊的序列在ｓ中出现
的次数是否近似相等，令聊是一个满足ｌ詈ｌ：５－ｃ：。，的正整
数，令ｔ一［告］将序列拆分成ｋ个不相交的部分，每部分的
长度为所，令％为第ｆ种长度为聊的序列所出现的次数．所使用的统计量为：
．ｂ一弓｝（兰，妒）一七
＾
●一■
它近似地服从自由度为２”一ｌ的ｚ２分布．ｍ＝ｌ时即频率测试．
４．２．５自相关测试
自相关测试用来检测序列ｓ与其发生（非循环）移位后形成的序列之问的相关性．
令ｄ为一个固定整数，ｏ‘ｄ‘Ｌ纠，序列ｓ与ｓ发生ｄ
移位后所形成的序列中的不同比特
数为：ｍＣｄ）一善墨。ｓ一＋一，所使用的统计量为：
冒协抡丘・２００８年第７期（下）
万方数据