1979年，Rabin在论文《与分解因子同样困难的数字签名和公开密钥函数》中提出了一种新颖的密码体制。Rabin体制有两个特点：第一，从密文恢复明文时结果是不确定的，有4种不同选择的可能性；第二，Rabin体制的保密性能是确定的，可以证明，破译Rabin体制的计算复杂性与分解因子的问题相同。

Rabin体制的建立也是基于分解因子问题是计算上困难问题的假定。在建立Rabin体制时，用户选取一对不同的大素数p和q，并计算n=pq。用户公布n（公开密钥），但将p和q（秘密密钥）保密。加密时，任何用户都可以用公开密钥n，对明文M∈Z*n通过变换公式

C=E(M)=M2(mod n)

进行加密，得到密文C。解密密文C时，知道秘密密钥p和q的用户可以分别求出C mod p的两个平方根和C mod q的两个平方根，再利用中国剩余定理求出C mod n的4个平方根。最后剩下的问题是如何判断这4个根中哪一个是明文M。其中一种方法是可以在加密前附加20个随机位在明文信息M的末尾。然后将加密结果连同这20位一起发送出去。注意，当明文M足够长时，这样做无损于整个Rabin密码系统的保密性。因为，假如给出x的最后20位以后，存在着一个可以由x2 mod n计算出x的多项式时间算法A，即使不给出这最后的20位，也可以计算出x，其运算时间仅为算法A的运行时间的220倍。

的x的简单的有效算法，即(www.daowen.com)

类似的结论对q也成立。

由Rabin方法的构造可知，Rabin加密变换是RSA加密变换当e=2时的特殊情形。但是，Rabin方法和RSA方法的解密过程却大不相同。破译Rabin密码的问题等价于“不分解n的因子计算模n的平方根”问题，其计算复杂性与分解因子的问题相同。有如下的Rabin基本定理：设n是一对不同的奇素数的乘积，ε是满足0＜ε≤1的正数。如果有一个多项式时间算法SQRT（a，n），对于二次剩余a mod n的ε部分，能够输出a mod n的一个平方根，则必定存在一个可以分解n的因子的概率算法FAC（n），其期望运行时间是log n和1/ε的多项式。

这个定理的重要性在于，它保证了只要分解因子的问题是困难的，攻破Rabin体制就不可能是容易的问题，这一重要特点是RSA体制所没有的。