Cannot Connect to App Store (Or iTunes)
Your user profile on your Mac might be compromised.

To test, create new user and try to access iTunes or App Store.

If it works lets try repair your user profile with permissions repair.

Restoring the OSX from backup will not fix that, it will keep your user profile as is.

Just as safety and unexpected problems, create second Administrator (full access) account.

Launch Disk Utility, located at /Applications/Utilities/.
Select the 'First Aid' tab.
In the left-hand pane, select a volume you wish to run Repair Permissions on. ...
Click the 'Repair Disk Permissions' button.


Also see this article to restore/reset permissions

But your problem might be even deeper. The certificates reside in KeyChain.

Repairing keychain it might be tricky so follow the instructions carefully (like FIRST make BACKUP).