Hello, actually I tried everything that you said but it didn't work. As it turns out it was a software glitch in iPhone 5s with the model number: A1429 that apple had fixed in iOS 6.1 beta 2 which is for developers only. But I could get my hands on it after googling for half an hour. Now my problem is fixed. Here is how it is done.
Download the latest version of iTunes here
Restore your iPhone to iOS 6.0.1 using iTunes.
Download iOS 6.1 beta 2 for iPhone 5 CDMA
Press shift (option key on mac) + update and choose the ipsw for iOS 6.1 beta 2
Done, the problem is solved