GetAzureADAppOnlyAuthenticatedContext sometimes fails with error "Keyset does not exist"

We use this version of the method to access SPO in App Only context GetAzureADAppOnlyAuthenticatedContext(String, String, String, X509Certificate2, AzureEnvironment)

This works most of the times (80-90 % of calls succeed) but sometimes it fails with an error "Keyset does not exist". Additional details below

Our code is written in .Net 4.6 and is running on Windows Server 2016

Has anyone seen this before?

 

Message - Type = System.Security.Cryptography.CryptographicException

Message = Keyset does not exist

 

Source = mscorlib

TargetSite = System.Security.Cryptography.SafeProvHandle CreateProvHandle(System.Security.Cryptography.CspParameters, Boolean)

StackTrace =    at System.Security.Cryptography.Utils.CreateProvHandle(CspParameters parameters, Boolean randomKeyContainer)

   at System.Security.Cryptography.Utils.GetKeyPairHelper(CspAlgorithmType keyType, CspParameters parameters, Boolean randomKeyContainer, Int32 dwKeySize, SafeProvHandle& safeProvHandle, SafeKeyHandle& safeKeyHandle)

   at System.Security.Cryptography.RSACryptoServiceProvider.GetKeyPair()

   at System.Security.Cryptography.RSACryptoServiceProvider..ctor(Int32 dwKeySize, CspParameters parameters, Boolean useDefaultKeySize)

   at System.Security.Cryptography.X509Certificates.X509Certificate2.get_PrivateKey()

   at System.IdentityModel.Tokens.X509AsymmetricSecurityKey.get_PrivateKey()

   at System.IdentityModel.Tokens.X509AsymmetricSecurityKey.GetAsymmetricAlgorithm(String algorithm, Boolean privateKey)

   at Microsoft.IdentityModel.Clients.ActiveDirectory.Internal.Platform.CryptographyHelper.SignWithCertificate(String message, X509Certificate2 certificate)

   at Microsoft.IdentityModel.Clients.ActiveDirectory.ClientAssertionCertificate.Sign(String message)

   at Microsoft.IdentityModel.Clients.ActiveDirectory.Internal.ClientCreds.JsonWebToken.Sign(IClientAssertionCertificate credential, Boolean sendX5C)

   at Microsoft.IdentityModel.Clients.ActiveDirectory.Internal.ClientCreds.ClientKey.AddToParameters(IDictionary`2 parameters)

   at Microsoft.IdentityModel.Clients.ActiveDirectory.Internal.Flows.AcquireTokenHandlerBase.<SendTokenRequestAsync>d__69.MoveNext()

--- End of stack trace from previous location where exception was thrown ---

   at System.Runtime.CompilerServices.TaskAwaiter.ThrowForNonSuccess(Task task)

   at System.Runtime.CompilerServices.TaskAwaiter.HandleNonSuccessAndDebuggerNotification(Task task)

   at Microsoft.IdentityModel.Clients.ActiveDirectory.Internal.Flows.AcquireTokenHandlerBase.<CheckAndAcquireTokenUsingBrokerAsync>d__59.MoveNext()

--- End of stack trace from previous location where exception was thrown ---

   at System.Runtime.CompilerServices.TaskAwaiter.ThrowForNonSuccess(Task task)

   at System.Runtime.CompilerServices.TaskAwaiter.HandleNonSuccessAndDebuggerNotification(Task task)

   at System.Runtime.CompilerServices.TaskAwaiter.ValidateEnd(Task task)

   at Microsoft.IdentityModel.Clients.ActiveDirectory.Internal.Flows.AcquireTokenHandlerBase.<RunAsync>d__57.MoveNext()

--- End of stack trace from previous location where exception was thrown ---

   at System.Runtime.CompilerServices.TaskAwaiter.ThrowForNonSuccess(Task task)

   at System.Runtime.CompilerServices.TaskAwaiter.HandleNonSuccessAndDebuggerNotification(Task task)

   at Microsoft.IdentityModel.Clients.ActiveDirectory.AuthenticationContext.<AcquireTokenForClientCommonAsync>d__33.MoveNext()

--- End of stack trace from previous location where exception was thrown ---

   at System.Runtime.CompilerServices.TaskAwaiter.ThrowForNonSuccess(Task task)

   at System.Runtime.CompilerServices.TaskAwaiter.HandleNonSuccessAndDebuggerNotification(Task task)

   at Microsoft.IdentityModel.Clients.ActiveDirectory.AuthenticationContext.<AcquireTokenAsync>d__58.MoveNext()

--- End of stack trace from previous location where exception was thrown ---

   at System.Runtime.CompilerServices.TaskAwaiter.ThrowForNonSuccess(Task task)

   at System.Runtime.CompilerServices.TaskAwaiter.HandleNonSuccessAndDebuggerNotification(Task task)

   at OfficeDevPnP.Core.AuthenticationManager.<>c__DisplayClass46_0.<GetAzureADAppOnlyAuthenticatedContext>b__0(Object sender, WebRequestEventArgs args)