IPhone – Restored iPhone 5s asks to set up as new iPhone or restore from backup

The password used to encrypt the backup file might have been saved to the user's keychain.

1. from /Application/Utilities open the Keychain Access utility
2. make sure that on the left side "All items" is selected under categories
3. in the upper right search field enter "iphone" and then look for a keychain item named "iPhone Backup" of kind "application password". If there is no such item, you´re mostly out of luck
4. double click on the "iPhone Backup" entry and in the new window that will open, click on the "show password" checkbox
5. you will now be prompted to enter your password (the one your user has on your Mac) to show the iPhone backup password; click Allow (once). You should now see the iPhone Backup password in clear text.

I don't think windows has an equivalent store for saving the password. If not, you will have to try brute forcing it in iTunes - just me methodical - write down all sorts of passwords that may have been used - brainstorm a bit. Then try them one by one. Hopefully with the pressure off a bit you will stumble upon the pass phrase that was used.

When you restored your phone, did you do the configuration steps in iTunes or on the iPhone itself? Try restoring again, and follow the steps on the iPhone, not in iTunes. I've seen some reports claiming that iCloud restores can only be started from the device itself.