We use the Internet every day. The Internet relies on its very foundations on DNS, the Domain Name System. DNS continues to be a nice target for hackers. The possibilities a hacker can expect should he succeed in taking over a server or simply use DNS implementation to reorientate traffic, are some of the things which make DNS a source of security issues. In the last many years, several security flaws have been discovered in the protocol and its specific implementations. DNS spoofing one of the major threat to DNS Server. DNS cache poisoning, also known as DNS spoofing, is a type of attack that exploits vulnerabilities in the domain name system (DNS) to divert Internet traffic away from legitimate servers and towards fake ones. In our work, we have developed a robust algorithm that is combination of (RSA + bit stuffing), i.e. RSA accounts for legacy of user by providing the Digital signature, while bit stuffing is used digesting the message so that it remain confidential for the intruders, if any changes persist (violation of integrity) destination can’t decipher the message with the help of public key of sender. So this way we can provide more robustness for DNS.