(12)第六章 - 指数与原根

初等数论 第六章指数与原根 本章内容 1指数 1指数 2原根 3指标 二项同余方程 Diffie Hellman密钥交换 Diffie和Hellman在1976年提出的Diffie Hellman密钥交换协议 是一个典型的密钥协商协议 允许两个用户可以安全地交换一个秘密信息 用于后续的通讯过程 算法的安全性依赖于计算离散对数的难度 Diffie Hellman密钥交换 离散对数困难性回顾素数p的本原根定义 如果a是素数p的本原根 则数amodp a2modp ap 1modp是不同的并且包含1到p 1的整数的某种排列 对任意的整数b 我们可以找到唯一的幂I满足b aimodp0 i p 1 i在离散对数算法中称为模p下以a为底b的离散对数 指标 记为i inda p b 离散对数的计算 Y gXmodp 已知g x p 计算y是容易的 已知y g p 计算x是困难的 当p很大时 该算法是不可行的 Diffie Hellman密钥交换 算法 双方选择素数p以及p的一个原根a 用户A选择一个随机数Xa p 计算Ya aXamodp 用户B选择一个随机数Xb p 计算Yb aXbmodp 每一方保密X值 而将Y值交换给对方 用户A计算出K YbXamodp 用户B计算出K YaXbmodp 双方获得一个共享密钥 aXaXbmodp 素数p以及p的原根a可由一方选择后发给对方 K YbXamodp aXbmodp Xamodp aXaXbmodp aXamodp Xbmodp YaXbmodp Diffie Hellman密钥交换 Diffie Hellman密钥交换的攻击 中间人攻击图示 Diffie Hellman密钥交换的攻击 中间人攻击1双方选择素数p以及p的一个原根a 假定O知道 2A选择Xa p 计算Ya aXamodp A B Ya3O截获Ya 选Xo 计算Yo aXomodp 冒充A B Yo4B选择Xb p 计算Yb aXbmodp B A Yb5O截获Yb 冒充B A Yo6A计算 Xo Xa aXo Xa aXoXamodp7B计算 Xo Xb aXo Xb aXoXbmodp8O计算 Ya Xo aXaXomodp Yb Xo aXbXomodpO无法计算出aXaXbmodpO永远必须实时截获并冒充转发 否则会被发现 Diffie Hellman密钥交换 Diffie Hellman密钥交换协议可以容易的推广到椭圆曲线上 为了防止这种中间人攻击 必须引入相应的认证机制 为此 Diffie等人于1992年提出了端到端协议 station to stationprotocol 该协议是对Diffie Hellman密钥交换协议的一种修改 来抵抗中间人攻击 ElGamal公钥系统 基本情况算法描述算法的安全性算法的应用 ElGamal公钥系统 基本情况ElGamal密码是除了RSA密码算法外 最具有代表性的公钥密码算法 Diffie Hellmankeydistributionscheme的变形 加密的安全性建立在解离散对数的困难性上Publishedin1985byElGamal T ElGamal APublicKeyCryptosystemandaSignatureSchemeBasedonDiscreteLogarithms IEEETrans InformationTheory volIT 31 4 pp469 472 July1985缺点 增加了传送信息长度 2倍 ElGamal公钥系统 算法描述 ElGamal公钥系统 如果明文需要分组 则每个分块要有唯一的k ElGamal公钥系统 ElGamal公钥系统 算法实例 ElGamal公钥系统 RSA与ElGamal比较 ElGamal公钥系统 ElGamal算法的安全性由于ElGamal密码的安全性建立在GF p 离散对数的困难性之上 而目前尚无求解GF p 离散对数的有效算法 所以p足够大时ElGamal密码是安全的 为了安全p应该为150位以上的十进制数 而且p 1应有大素因子 为了安全加密和签名所使用的k必须是一次性的 d和k都不能太小 ElGamal公钥系统 ElGamal算法的安全性如果k不是一次性的 时间长了就可能被攻击者获得 又因为y是公开密钥 攻击者自然知道 于是攻击者就可以根据U ykmodp计算出U 进而利用Euclid算法求出U 1 又因为攻击者可以获得密文C2 于是C2 UMmodp通过计算U 1C2得到明文M 设用同一个k加密两个不同的明文M和M 相应的密文为 C1 C2 和 C1 C2 因为C2 C2 M M 如果攻击者知道M 则容易求出M ElGamal公钥系统 ElGamal算法的应用由于ElGamal密码的安全性得到世界公认 所以得到广泛的应用 著名的美国数字签名标准DSS 采用了ElGamal密码的一种变形 为适应不同的应用 人们在应用中总结出18种不同的ElG