Study On Congruence-Theory-Based Probabilistic Encryption Scheme

Based on the Probabilistic cryptosystem proposed already, The Congruence--Theory-Based Probabilistic cryptosystem is proposed in this paper,. The scheme takes k-residue as encryption algorithm and random sequences generated algorithm, and the Chinese Remainder Theorem (CRT) as a combination of multi-user infor- mation.The Congruence-Theory-Based Probabilistic cryptosystem is suitable for multi-user communication. It is transfered into a probabilistic Turing machine, and as the server of the whole security communications system. When a user needs to communicate with other users, it sends an application to the server, asking for a public key and a module in the security communication system. The server selects a couple corresponding public keys and modules from key-space, according to the random number generated by the random number generator, then send them to all users by the certified public key way. After all users getting their own private keys by calculating the inversion of public key for the module, the sender encrypts messages by k-residue algorithm, combines them by CRT and sent them out. All receivers check that weather the cipher is the same as the k-residue of the module. If they are the same, it indicating that the cipher not be tampered; if not, discarding them and noticing that the cipher has being tampered. To be pointed out is that the complexity of k-residue algorithm is time-index based, so it increases the difficulty of decryption.The same as the other probabilistic cryptosystems, the Congruence-Theory--Based Probabilistic cryptosystem introduces into some random numbers, increasing uncertainty of the whole system to generate cipher. So, for a probabilistic cryptosystem, it can generate different keys everytime, and the plaintext-ciphe- rtext is also different. This strengthens the security of probabilistic cryptosystem. At the same time, the complexity of k-residue algorithm is time-index based, so it increases the security of the Congruence-Theory-Based Probabilistic Encryption Scheme.For probabilistic cryptosystem proposed in this paper,on the one hand, ran--domicity is bodied in its encrypting, on the other hand, as a encryption algorithm ,k-residue both increases the difficulty in attacking cryptosystem and tests whether the cipher is tapered. So the Congruence-Theory-Based Probabilistic cryptosystem can resist limit-searching and tamper.