南开大学盛斌-南开大学盛斌
概率论在密码学中的应用
口郑娟朱金伟曾文军
（
华中师范大学数学与统计学学院湖北?武汉４３００７９）
摘要：本文通过介绍密码学中
的保密通信系统模型，分析密码体制的安全性、可靠性来挖掘隐藏在各个
机制中的概率统
计规律，从而揭示出概率论在密码学理论中发挥的重要作用。
关键词：生日攻击统计量密
码分析
中图分类号：ＴＰ３
文献标识码：Ａ
文章编号：１ ００７－３９７３（２００８）０７－０８９－０２
１引言
三方
截取，即主要来自非法者的主动攻击（见保密通信系统
２ｌ世纪是信息时代，信息已成为
社会发展的重要战略
模型）．采用消息认证，通过基于公开函数一杂凑（Ｈａｓｈ）函数
资源．在信息化社会中，信息安全将扮演极为重要的角色，
取得认证符就 可以防止主动攻击。
它直接关系到国家安全、企业经营和人们的日常生活．密码
确切的说，Ｈａｓｈ函数（简称Ｈ）用于将任意长的消息
技术作为信息安全系统中
保障数据安全的关键技术，其体
Ｍ映射为较短的、固定长度的一个值Ⅳ彤），即杂凑值、杂凑
制的完备性在于密码在计算机有限空间和时间条件下的不
码或消息摘
要．对于定义域Ｄ和值域Ｒ，有ＨＩ
Ｄ斗Ｒ和ｌＤｌ，旧。
可破译性．而
这种不可破译性又由密钥的随机安全性决定．
它应满足以下条件：
在研究
密码学过程中，概率论无疑起着相当重要的作用，它
（ａ）已知ｈ，求使得胃（砷＝＾的Ｘ在计算 上是不可行的，
对于检测密钥的随机可靠性，分析攻击密码流，检测随机序
这一性质称为函数的单向性，称片（ｘ）为单向杂凑函数；
列的伪随机性都具有十分重
要的作用。
（６）已知ｘ，找出Ｙ（Ｙ≠，）使得Ⅳ（Ｊ，）＝日０）在计算上是不
２背景知识和概念
可行的；
密码学：密码学
是对与信息安全各方面（比如机密性、
（ｆ）找出任意两个不同的输入ｘ，），，使得Ⅳ∽＝Ⅳｏ 。在计
数据完整性、实体认证及数据源认证）有关数学技术的研
算上是不 可行的．
究。
其中条件（口）保证攻击者截获膨和ｃ＝．Ｉ：ｆ《ｓＩ肘 ）后，求不出
密码加密和解密：发送方将要发送的消息称为明文，明
ｃ的逆ＳＩ
Ｍ，也就不可求出秘密值Ｓ．条件（∞使得敌手无
文被变
换成看似无意义的随机消息，称为密文，这种变换过
法在已知某个消息时，找到与该消息
具有相同杂凑值的另
程称为加密．加密的逆过程称为解密．
一消息．条件 （ｃ）用于抵抗生日攻击。
密码分析：密码通信过程中，截收者通过分析可能从
由于该函数是多对一的，因此存在碰撞（具有同一输
截获的密文推断出原
来的明文或者密钥的过程称为密码分
出的输入对）是不可避免的．实际上，限制曰到一个
ｔ比特
析．
输入的域（，＞”），在所有输出是等概率的意义下
，假如日是
３密码学中的概率统计模型
“随机的”，则大约有２＇４个输 入对应同一个输出，且两个随
密码学的研究是基于密码通信系统的．它包括了从信
机选择的输入产生同一输出的概率为２”（与ｔ无关）．抽象
源到接收
者的加密和解密过程，也包括在此过程中的受到
成数学中的生日攻击模型就是：
的来自非法接入者的非法攻击．其模型的图解如下：
已知～杂凑函数日有胛个可能 的输出，Ⅳ∽是一个特
定的输出，如果对Ⅳ随机取ｋ个输入，则至少有一个输入
ｙ使得Ｈ（ｙ）；Ⅳ（ｘ）的概率为０．５时，ｋ有多大？
解因为Ｈ有刀
个可能的输出，所以输入ｙ产生的输
出ｔｔ（ｙ）等于特定输出Ⅳ∽的概率是ｌ／疗，反
过来说Ｈｆｙ）＃Ｈ（ｘ）
的概率是ｌ—ｌ／盯．ｙ取ｋ个随机值而函数的ｋ个输出中没
有一个等于Ⅳ（ｘ），其概率为（Ｉ—Ｉ／ｎ）?，所以ｙ取ｋ个随机
< br>值得到函数的ｋ个输出中至少有～个等于日（ｘ）的概率为
１一（１—１／－）‘
．由（１＋Ｊ）‘ｚｌ＋＿ｂ，其中Ｉ卅“１，可得：
１一（１—１／，，）‘≈１一（
１一七／，，）一七／月，
保密通信系统模型
若上述概率等于０
．５，则ｋ＝ｎ／２．特别地，如果日的输出
其中ｍ代表明文，ｃ代表密文，毛和乞均代
表密钥流．
为ｍ比特长，则可能的输出个数疗＝２”，则ｋ＝２”１．
< br>ｍ’为密码分析员解密获得的明文，ｃ’为攻击者获得的密文
４．２随机密钥构造
过程中的测试统计量
部分。
密码学中最重耍的并不是加密算法和解密算法 ，而是
４概率论在密码学中的应用
在加密过程和解密过程ｔ｝ｔ所需要用 到的加密密钥和解密密
４．１抗击主动攻击的生日攻击模型
钥．加密密钥 和解密密钥的生成又在于随机序列的获得．
密码加密的任务是为了防止通信双方的信息内
容被第
事实上，不管利用硬件还是利用软件设计随机序列都
越协斧信．’
ｎｎＲ盔笛７如ｆ下ｌ
万
方数据