The advancement in cloud technology led to rapid increase of the cloud users which is causing heavy network traffic which led to various vulnerable activities and unauthorized access in the network that affects the security of the cloud storage. The existing methodologies tried to increase the cloud security but did not reach the expected target due to various factors like traditional algorithms have limited attack resisting ability that expose the encrypted data. To overcome the problem of existing algorithms, the Chebyshev Polynomial-Based Relatively Slow Algorithm (CP-RSA) algorithm was proposed for the generation of strong key that strengthen the security of cloud against multiple attacks. The double encryption process was applied using Paillier algorithm and Advance Encryption Standard (AES) algorithm were used to increase the stability of encrypted data. The performance of the proposed CP-RSA with AES was evaluated based on encryption, decryption, and key generation time. The developed CP-RSA with AES approach has obtained minimum encryption and decryption times of 2.96 ms and 2.01 ms and a lower key generation time of 251 ms. The simulated output of the proposed CP-RSA with AES approach exhibits improved results compared to the existing encryption approaches.