Security is necessary today’s fast computer world during the data communications in internet and cloud environment. The cloud security is becoming very challenging task today due to the presence of huge volume of cloud users. Even though, various cloud secured storage mechanisms are available and tried to fulfill the current requirement. However, not yet fulfill the cloud user’s requirements in terms of security while storing and sharing the data in cloud. For this purpose, this work proposes a new secured storage and communication system for providing data security while storing the data in cloud database and sharing the data between the cloud users in cloud. This system consists of three different algorithms for performing prime number generation, digital signature creation for generating keys, encryption, decryption and authorization. In this paper, we propose a new technique to find a co-prime number which is used to generate keys in key generation process and also useful for performing encryption and decryption process. Moreover, a new key generation technique is also introduced for ECC and DSA using polynomial congruence for performing key generation process securely. In addition, a new Elliptic Curve and Polynomial Congruence based Encryption / Decryption algorithms for performing data encryption and decryption in the process of data storage and communication. Finally, the user authenticity is verified by the proposed digital signature algorithm in this work. The experiments have been conducted for evaluating the proposed secured storage and communication system and proved as better than others in terms of efficiency and security level.