本文在研究前人概率密码体制的基础上,讨论一种基于同余理论的概率密码体制。该密码体制中,以k次剩余作为加密算法和随机序列产生算法,以中国剩余定理作为多用户信息组合方式。本文基于同余理论的概率密码体制,是适合于多用户间通信的密码体制。我们将基于同余理论的密码体制模型化为一个概率图灵机,并作为整个安全通信系统的服务器。当某一用户与其他用户进行通信时。首先,通信发起方向服务器申请,索要安全通信公钥及模数,服务器根据随机数产生器产生的随机数从密钥空间随机选取公钥及模数(每组密钥将对应于一组模数),然后采用带认证的公钥分发方式将公钥及模数发送给各用户。用户通过求该公钥关于对应模数的逆,计算出自己的私钥。然后,发起方将要发送给每个用户的信息利用k次剩余进行加密,再将加密后的信息根据中国剩余定理(CRT)进行信息组合,并发送给与其通信的每一个用户。k次剩余算法的复杂度是指数时间的,在复杂性方面增加了破译的难度。最后,接收方收到密文后,验证密文是否是模数的k次剩余,若是,则说明密文在传输过程中没有被篡改。若不是,则丢弃此密文,并通知通信发起方密文被篡改。基于同余理论的概率密码体制与其它概率密码体制相比,都是通过引入一定的随机数,增加整个系统产生密文的不确定性,使对于同一个密码体制,同样的明文,在不同的时间进行加密时,密钥都是不同的,由此产生的明-密文的对应关系也不是固定的。但是不同的是本文采用k次剩余做为加密算法,它的计算复杂性,在很大程度上提高了密码体制的安全性。本文的概率密码体制,一方面利用随机数体现了它加密的随机性,另一方面用k次剩余作为加密算法,即增加了破译难度又可以检验密文在传输过程中是否被篡改。因此可以用来抗击穷举攻击法、篡改等安全威胁。