Rns-based cryptographic system and method

Abstract

The RNS-based cryptographic system and method uses a symmetric residue number system (RNS) for encryption and decryption of messages, i.e., the sender and receiver agree upon a set of relatively prime numbers, referred to as the basis, whose product is an integer, and both the RNS and the integer are kept secret. To break the cipher, an attacker must factor the secret integer, which is unknown to the attacker, given only the upper bound of the unknown integer, a problem referred to as blind factorization of the unknown integer, which is a computationally hard problem. The method may be combined with a discrete logarithm problem, and the ciphertext may be padded with random values to hide the upper bound of the unknown integer. When the ciphertext requires multiple blocks, subsets of the basis and/or the random number padding may be used to prevent collision attacks.