随笔-144  评论-223  文章-30  trackbacks-0
1. 对于RSA,给定大整数n分解的一对素因子p和q,p或q是否素数决定不了安全性,但决定算法的正确性,也就是说p或q不能为合数,而安全性取决于n的位数及p、q的距离,n越大则难于素因子分解(因为素数测试是一个P问题,而因子分解是一个NP问题,其耗时是关于n的指数),|p - q|要大是为抵抗一种特殊因子分解攻击,论证如下:由(p+q)2/4 - n = (p+q)2/4 - pq = (p-q)2/4,若|p - q|小,则(p-q)2/4也小,因此(p+q)2/4稍大于n,(p+q)/2稍大于n1/2即根号n。可得n的如下分解法:a) 先顺序检查大于n1/2的每一整数x,直至找到一个x使得x2 - n是某一整数y的平方;b) 再由x2 - n = y2 得 n = (x+y)(x-y)。另外,p - 1和q - 1都应有大素因子(所有因子皆是大素数),以抵抗可能的重复加密攻击(重复加密较少步后可恢复出明文)

2. 对于DH密钥交换,通常选择阶为素数的有限循环(子)群,这时素数决定了安全性。因素数不能再因子分解,故避免了针对阶为合数的质因子分解且利用中国剩余定理求离散对数的(已知最好)攻击。具体讲就是为了防index-calculus方法求解离散对数,底层循环群G的素数模p要足够大,长度1024位可实现80位安全等级,长度3072位可实现128位安全等级;另为了防Pohlig-Hellman攻击,G的阶p-1必须不能因式分解为全部都是小整数的素数因子,且为了p-1的每个因子构成的子群防baby-step giant-stepPollards's rho攻击,要求对80位安全等级而言,p-1的最小素因子必须至少为160位,而对128位安全等级,其至少为256位

3. 对于Hash函数,安全性要求有三点:第一是单向性,由于压缩函数理论上存在碰撞,因此单向性是指计算不可行,为什么要单向性?因为若不单向,则可从结果比如签名逆出原文消息;第二是抗弱冲突性即第1类生日攻击,计算不可行;第三是抗强冲突性即第2类生日攻击,计算不可行。这三点要求,取决于压缩函数是否能抗差分、线性等密码分析

4. 周知Shamir门限方案基于多项式的拉格朗日插值公式,普遍的设计采用GF(q)域上的多项式,秘密s为f(0),q是一个大于n的大素数(n是s被分成的部分数)。正常来讲,参与者个数必须至少是设计时的k,才能恢复出正确的s。如果个数少于k比如k-1,则只能猜测s0=f(0)以构建第k个方程,那么恢复得到的多项式g(x)等同设计时的多项式f(x)的概率是1/q。因为g(x)的项系数可以看作关于s0的同余式即h(s0)=(a+b*s0)mod q的形式,因q为素数,故依模剩余系遍历定理,当s0取GF(q)一值时,则h(s0)唯一对应另一值。所以h(s0)等于f(0)的概率为1/q。由此可见,当q取80位以上,敌手攻击概率不大于1/280,这已经很低了。这种门限方案如同RSA加密,再次佐证了素数越大安全性越高

5. PGP是密码学经典应用,体现在首先支持保密与认证业务的正交,即独立或组合,且组合时按认证、压缩、加密的顺序,这个顺序是经考究有优势的;其次会话密钥是一次性的,由安全伪随机数生成器生成,且按公钥加密;最后使用自研的密钥环与信任网解决公钥管理问题。理论本质上,PGP提供的是一种保密认证业务的通用框架,因为具体的对称加密算法、随机数生成、公钥算法,都可依需要灵活选配扩展。PGP有两个问题跟组合与概率相关,一个是算密钥环N个公钥中,密钥ID(64位)至少有两个重复的概率?设所求概率为p,先算任意两个不重复的概率q,令m=264,则q=m!/((m-N)!*mN),则p=1-q,不难看出,N越小则q越大则p越小,因实际应用N<<m,故p非常小可忽略,即PGP取公钥中最低64有效位作密钥ID,是可行的。另一个是签名摘要暴露了前16位明文,对哈希函数安全的影响有多大?这问题意思应该是敌手拿到消息后但没发送方的私钥作签名,只能穷举变换原消息并求哈希值,使之与消息摘要剩余位组相等。这本质是求两类生日攻击碰撞概率大于0.5时所需的输入量。在仅认证模式中,抗弱碰撞计算量降低为原来的1/216,抗强碰撞计算量至少降低为原来的1/28。另外,考虑到这16位明文可能的特殊性,有没更快的代数攻击,需进一步研究
posted on 2023-09-28 08:04 春秋十二月 阅读(1309) 评论(0)  编辑 收藏 引用 所属分类: Algorithm

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理