SilentSpiral

RSA与Rabin

先简述一下这两个算法:

RSA

原理: 欧拉定理 (用不到用不到用不到费马小定理!!! )

aφ(n)≡1 （mod n）
φ(n)为欧拉函数, 用以表示小于n的正整数中与n互质的数的数目 (钦定 φ(1) = 1)
　　易知当n=p时 (p为素数), φ(p) = p-1
　　φ(pk) = (p-1)*pk-1
　　φ(a*b) = φ(a)*φ(b)
　　φ(p*q) = φ(p)*φ(q) = (p-1)(q-1)
对于任意的整数n, 若不能将其完全分解为质因数之积, 是无法求出φ(n)的

构造

随机生成素数 p,q, n=p*q (反复生成随机数, 能通过miller-rabin素性检测即为素数)
计算 φ(n) = φ(p*q) = φ(p)*φ(q) = (p-1)(q-1)
随机选取与φ(n)互质的加密公钥 e (为方便快速幂算法, 通常取e=65537)
用广义欧几里得算法计算 d = e-1 (mod φ(n))
公开公钥<e,n>
保存私钥<d,n> (亦需要对关键参数<p,q,φ(n)>保密)
记明文为M, 密文为C
加密: C ≡ Me (mod n)
解密: M ≡ Cd (mod n)

证明

ed ≡ 1 (mod φ(n)) => ed = 1+k*φ(n)
M ≡ Cd ≡ Med ≡ M1+k*φ(n) ≡ M*Mk*φ(n) ≡ M*(Mφ(n))k ≡ M (mod n)

Rabin:

原理:

二次剩余
若p是奇质数且p不能整除d, 则方程 x2 ≡ d (mod p)有解的充要条件是:
d(p-1)/2 ≡ 1 (mod p) (欧拉判别准则)
特殊的, 若p ≡ 3 (mod 4)
则可进一步解出来 x ≡ d(p+1)/4(mod p)
　　事实上这是一个极为精妙的构造解:
　　d(p-1)/2 ≡ 1 (mod p) ,两边同乘d得:
　　d(p+1)/2≡ d (mod p)
　　因为 p ≡ 3 (mod 4), 故(p+1)/4是一个整数
　　　　(d(p+1)/4)2 ≡ d (mod p)
　　　　观察得: x ≡ ±d(p+1)/4 (mod p)

中国剩余定理
对于一次同余方程组:
　　x ≡ a (mod p)
　　x ≡ b (mod q)
可解得 x ≡ [a*q*(q-1(mod p)) + b*p*(p-1(mod q)) ] (mod pq)

构造:

随机选取素数p≡q≡3 (mod 4)
公钥<2,n=pq>
私钥<p,q>
记明文为M, 密文为C
加密: C ≡ M2 (mod pq) (Rabin加密是真的快)
解密: 此处解同余方程组
　　x2 ≡ C (mod p)
　　x2 ≡ C (mod q) 注:有效明文一定有解
运用公式 x ≡ ±d(p+1)/4 (mod p), 可迅速解得:
　　x ≡ ±m (mod p)
　　x ≡ ±m (mod q)
随后得到了4个一次同余方程组
　　{x ≡ m (mod p), x ≡ m (mod q)}
　　{x ≡ m (mod p), x ≡ -m (mod q)}
　　{x ≡ -m (mod p), x ≡ m (mod q)}
　　{x ≡ -m (mod p), x ≡ -m (mod q)}
可由中国剩余定理解出4个解, 则明文为其中的一个, 需附加语义(或校验码)进行判断

可以看出, RSA与Rabin的保密性都取决于大整数分解问题
在量子计算时代, 大整数分解问题可由量子shor算法在多项式时间内解决
即便对于传统大规模集成电路计算机来说, 大整数分解问题也是远比离散对数弱得多的, 更比不上建立在椭圆曲线域上的离散对数问题, 后者甚至不存在亚指数时间复杂度的算法

但仅仅从数学的角度来看, 建立在大整数分解难问题的这两个算法, 无疑又比类Elgamal系列算法优雅的多, 或许是由于RSA和Rabin明文密文实质性的参与了加解密运算的缘故吧

  • Rabin比RSA安全的理由:
    Rabin已被证实安全性与大整数分解难问题等价, 想要破解密钥, 就必须分解大整数n
    而RSA的安全性仍未被证明, 个人臆测原因主要有两点:
    1. 不排除存在无需私钥d即可反求明文的方法, 譬如求周期的攻击
      (但这个攻击代价比分解n还高)
    2. 由私钥d无法反推 φ(n), 说明求出d与求出φ(n)在求解难度上并不等价
      但求出 φ(n)和分解n在难度上却是近乎等价的:
      　　φ(n) = (p-1)(q-1) = pq-(p+q)+1
      　　p+q = pq+1-φ(n) = n+1-φ(n)
      　　(p-q)2 = (p+q)2 - 4pq = [n+1-φ(n)]2 - 4n
      　　而后可开方得到(p-q); 再由(p+q)和(p-q)求出p,q是容易的
  • RSA比Rabin安全的理由:
    Rabin的素数必须满足p≡q≡3 (mod 4), 这无疑在暴力破解n的时候减小了近一半的搜索空间
    Rabin的公钥为2, 在明文较短的情况下, 可以尝试开方破解
    (在RSA取e=3的情况下同样存在此问题 )

是否可以说Rabin是RSA令e=2的特例?

我认为这个是难以说得通的
首先二者的原理差的有点远, 二次剩余算是一个比较独特的领域了
其次吧… RSA要求 e与 φ(n)互质
φ(n) = (p-1)(q-1) ,一定是个偶数
所以e=2的时候, e不存在模 φ(n)的逆
无法以RSA的方式对Rabin密文进行解密
更遑论Rabin是建立在RSA的基础上的

打赏