公钥密码体制专题课件.ppt

d的选择 e选定后可用Euclidean算法在多项式时间内求出d d小，签字和解密快，在IC卡中尤为重要(复杂的加密和验证签字可由主机来做) d要大于n1/4：类似于加密下的情况，d不能太小 否则由已知明文攻击，构造y=xe mod n，猜测d的值： 做yd mod n，直到试凑出yd?x mod n Wiener给出对小d的系统攻击法， 证明了当d长度小于n的1/4时， 由连分式算法，可在多项式时间内求出d值 二、RSA密码体制 RSA参数的选择 不可用公共模 由一密钥产生中心(KGC)采用一公共模，分发多对密钥，公布相应公钥ei 这当然使密钥管理简化，存储空间小，且无重新分组问题 但如前所述，它在安全上会带来问题。 明文熵要尽可能地大 明文熵要尽可能地大，以使在已知密文下， 要猜测明文无异于完全随机等概情况。 用于签字时，要采用Hash函数 二、RSA密码体制 RSA体制实用中的其它问题 Set-up of the Rabin System Choose two distinct primes p, q s.t.  and put n=pq. Encryption function 三、Rabin密码体制 Encryption algorithm: Decryption algorithm: step 1: Find a, b s.t. ap+bq=1 using the Euclidean algorithm. step 2: put step 3: Compute 三、Rabin密码体制 Claim: are four roots of and m is one of these four. Chose one which makes sense! Theorem. Let n=pq be the product of two distinct odd primes p, q. If , then has no solutions or exactly four solutions (ii)Let r, s be a solution of , respectively, then the four solutions of are (aps+bqr); -(aps+bqr); (aps-bqr); -(aps-bqr), where a, b satisfy ap+bq=1. (iii) If , then is a solution of 三、Rabin密码体制 c=x2 mod p cp-1=1 mod p c(p-1)/2=xp-1=1 mod p c=x2 mod n c=x2 mod q cq-1=1 mod q c(q-1)/2=xq-1=1 mod q c(p-1)/2c=x2 mod p x=±c(p+1)/4 mod p CRT: c(q-1)/2c=x2 mod q x=±c(q+1)/4 mod q x =±c(p+1)/4 bq ±c(q+1)/4 ap mod n Theorem : Solving for all is equivalent to factoring n. Cryptanalysis 三、Rabin密码体制 四、离散对数 The discrete logarithm problem applies to mathematical structures called groups. Given an element g in a f